Optimal Universal Coding of Integers

Universal coding of integers (UCI) provides binary codewords for positive integers such that, for every nonincreasing source distribution $P$, the average codeword length stays within $K$ times $\max \{1,H(P)\}$. The smallest constant $K$ is called the minimum expansion factor of UCI $\mathcal{C}$, denoted $C_{\mathcal{C}}^{\ast }$. The optimal minimum expansion factor $C^{\ast }=\inf \{C_{\mathcal{C}}^{\ast }\}$ is the minimum expansion factor corresponding to the optimal UCI. The optimal minimum expansion factor is currently known to lie in the range $2\le C^{\ast }\le 2.0386$. In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every universal code, the worst-case ratio is attained by a distribution in this family, so that the family is least favorable for the UCI problem. We further establish an inequality, called the \emph{UCI inequality}, which plays the same role for UCI as the Kraft inequality does for prefix codes: for any real number $B$, it decides whether $B$ lies below or above $C^{\ast }$. Through the UCI inequality, we obtain an equivalent definition of $C^{\ast }$. By numerical computation, we determine $C^{\ast }=2.000124757036101\cdots$, the first fifteen decimal digits being certified. Once $C^{\ast }$ is known, we can theoretically construct the optimal UCI.