[IEEE Trans. on Information Theory, vol. 69, no. 3, pp. 1452-1485, March 2023. ]
The 3/4 Conjecture for Fix-Free Codes With at Most Three Distinct Codeword Lengths
Spencer Congero and Kenneth Zeger
Abstract
The 3/4 conjecture was posed 25 years ago by Ahlswede, Balkenhol, and Khachatrian,
and states that
if a multiset of positive integers has Kraft sum at most 3/4,
then there exists a code
that is both a prefix code and a suffix code
with these integers as codeword lengths.
We prove that the 3/4 conjecture is true whenever
the given multiset of positive integers
contains at most three distinct values.