The three-quarter conjecture for binary fix-free codes
A set of binary words is fix-free (or bifix-free) if no word in it is a prefix or a suffix of another. By the Kraft inequality, lengths $\ell_1, \dots, \ell_N$ of a prefix-free code satisfy $\sum_i 2^{-\ell_i} \le 1$, and every such list is realised by one. For fix-free codes, Ahlswede, Balkenhol and Khachatrian proved that every list with $\sum_i 2^{-\ell_i} \le 1/2$ is realised, and that $3/4$ cannot be replaced by any larger number in the question below. Yekhanin proved that every list with $\sum_i 2^{-\ell_i} \le 5/8$ is realised, and Congero and Zeger proved the bound $3/4$ for lists with at most three distinct lengths; Gao and Shan's 2026 preprint extends the three-length case to alphabets of any size.
Problem. For every $N \ge 1$ and every list of positive integers $\ell_1, \dots, \ell_N$ with $$\sum_{i=1}^N 2^{-\ell_i} \le \frac34,$$ must there exist distinct binary words $c_1, \dots, c_N$ with $|c_i| = \ell_i$ such that no $c_i$ is a prefix or a suffix of another $c_j$? Repeated lengths are allowed, and the number of distinct lengths is unrestricted.
Source: Ahlswede, Balkenhol and Khachatrian (1996), the 3/4-conjecture; see Schnettler (2007).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- IT
- Keywords
- AIM Open Applied Problems, fix-free codes, Kraft inequality, variable-length codes
References
@inproceedings{ahlswede1996,
author = {Ahlswede, Rudolf and Balkenhol, Bernhard and Khachatrian, Levon},
title = {Some properties of fix-free codes},
booktitle = {Proceedings of the 1st International Seminar on Coding Theory and Combinatorics},
address = {Tsaghkadzor, Armenia},
year = {1996},
pages = {20--33},
}
@misc{schnettler2007,
author = {Schnettler, Holger},
title = {On the 3/4-conjecture for fix-free codes -- a survey},
year = {2007},
eprint = {0709.2598},
archivePrefix = {arXiv},
}
@article{yekhanin2004,
author = {Yekhanin, Sergey},
title = {Improved upper bound for the redundancy of fix-free codes},
journal = {IEEE Trans. Inform. Theory},
volume = {50},
number = {11},
year = {2004},
pages = {2815--2818},
doi = {10.1109/TIT.2004.836703},
eprint = {cs/0408017},
archivePrefix = {arXiv},
}
@article{congero2023,
author = {Congero, Spencer and Zeger, Kenneth},
title = {The 3/4 conjecture for fix-free codes with at most three distinct codeword lengths},
journal = {IEEE Trans. Inform. Theory},
volume = {69},
number = {3},
year = {2023},
pages = {1452--1485},
doi = {10.1109/TIT.2022.3218212},
}
@misc{gao2026,
author = {Gao, Weiguo and Shan, Zhi},
title = {The 3/4 conjecture for $q$-ary fix-free codes with at most three distinct codeword lengths},
year = {2026},
eprint = {2609.18237},
archivePrefix = {arXiv},
}
@misc{aim-fix-free-three-quarter,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The three-quarter conjecture for binary fix-free codes}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/497-fix-free-three-quarter.md},
note = {Entry 497 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00342, "The three-quarter conjecture for binary fix-free codes", clopen.solutions.