PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Universal Coding of Integers

Wei Yan, Yunghsiang S. Han, Leqian Zheng

arXiv:2610.01563v1cs.ITmath.IT

TL;DR

Universal integer coding seeks a tight expansion factor for average codeword length relative to max{1,H(P)}. The paper analyzes worst cases through one-point plus uniform-tail distributions and a UCI inequality, obtaining C*=2.000124757036101… with the first fifteen decimal digits certified.

  • Problem

    The optimal expansion factor for universal integer coding had been bounded but not determined, for a coding problem requiring average length within a constant factor of max{1,H(P)}.

    Source: §I · pp. 2–3

  • Method

    The paper establishes one-point plus uniform-tail distributions as least favorable and develops a UCI inequality that compares any real B with C*.

    Source: A. One-point plus uniform-tail… · p. 6, §V · p. 30

  • Results

    C*=2.000124757036101…, with the first fifteen decimal digits certified.

    Source: §I · p. 3, §V · p. 30

  • Takeaways & Limitations

    Once C* is determined, an optimal UCI can be obtained in theory.

    Source: §V · p. 30

Abstract

from arXiv · show

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}}^{*}$. The optimal minimum expansion factor $C^*=\inf\{C_{\mathcal{C}}^{*}\}$ 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^*\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^*$. Through the UCI inequality, we obtain an equivalent definition of $C^*$. By numerical computation, we determine $C^*=2.000124757036101\cdots$, the first fifteen decimal digits being certified. Once $C^*$ is known, we can theoretically construct the optimal UCI.

I. INTRODUCTION · II. PRELIMINARIES · A. Notations

The paper characterizes universal integer coding for nonincreasing distributions on the positive integers and presents tools for identifying the optimal minimum expansion factor. It also sets out the notation and information-theoretic results used in the paper.

I. INTRODUCTION

  • The problem considers prefix-free codes for positive integers under nonincreasing source distributions, requiring average codeword length within a constant factor of max{1, H(P)}.The source distribution is defined on N and has finite entropy.Source: §I · p. 2
  • The previously established range for the optimal minimum expansion factor was 2 ≤ C* ≤ 2.0386.Source: §I · p. 3
  • For every UCI, the worst-case ratio is attained by a one-point plus uniform-tail distribution, making this family least favorable for the problem.The family serves as a starting point for deriving bounds on C*.Source: §I · p. 3
  • The UCI inequality decides, for any real B, whether B is below or above C*, analogously to how Kraft's inequality serves prefix coding.The paper uses this inequality to obtain an equivalent definition of C*.Source: §I · p. 3
  • Numerical computation determines C* = 2.000124757036101..., certifies its first fifteen decimal digits, and enables a theoretical construction of an optimal UCI.The paper also obtains an equivalent definition of C* using the UCI inequality.Source: §I · p. 3

II. PRELIMINARIES

  • The preliminaries introduce the paper's notation and review relevant results on the minimum expansion factor; Table I summarizes the main notation.Source: §II · p. 4

A. Notations

  • The notation defines U_k as uniform on {1, ..., k}, gives H(U_k) = log2 k, and introduces the uniform distribution on {2, ..., k}, its entropy, and related coding and relative-entropy quantities.Source: A. Notations · p. 4
  • The notation extends entropy to random variables and defines conditional entropy and mutual information; the stated identity is H(X) = H(X | Y) + I(X; Y).Source: A. Notations · p. 4

B. Conventions and some results for UCI … A. One-point plus uniform-tail distributions

The section sets conventions and expansion-factor bounds for UCI, then introduces one-point plus uniform-tail distributions as a least-favorable family and derives a lower bound of 2 for every UCI.

B. Conventions and some results for UCI

MAIN NOTATIONS USED IN THIS PAPER

III. LEAST FAVORABLE DISTRIBUTIONS

A. One-point plus uniform-tail distributions

B. Least favorable distributions of PN

For any prefix code, the worst-case ratio over nonincreasing distributions is attained by a one-point plus uniform-tail distribution. The proof uses a uniform-mixture decomposition and a strictly concave auxiliary function.

B. Least favorable distributions of PN

C. Least favorable distributions of P(ε, k)

For every prefix code, a least-favorable distribution lies in the family {P_{ε_k,k}, U_k | k ≥ 2}, reducing the optimal UCI analysis to that family.

IV. THE OPTIMAL UCI AND THE UCI INEQUALITY

The section establishes the UCI inequality as a necessary and sufficient test for whether a code with first codeword length 1 can have minimum expansion factor at most B. It uses this criterion to bound the optimal factor between 2.0001247570 and 2.0001247571 and pursue construction of an optimal UCI.

IV. THE OPTIMAL UCI AND THE UCI INEQUALITY

  • 2.0001247570 ≤ C* ≤ 2.0001247571 bounds the optimal UCI’s minimum expansion factor.The section identifies constructing an optimal UCI as its ultimate goal.Source: §IV · p. 21
  • The UCI inequality plays a role analogous to the Kraft inequality for prefix codes.Source: §IV · p. 21
  • Yan and Lin proved that the first codeword of an optimal UCI has length 1, so the section assumes L(1) = 1 when considering optimal UCI.Source: §IV · p. 21
  • Σ(B) ≤ 7/4 is necessary and sufficient for a UCI code with L_C(1) = 1 to have minimum expansion factor at most B.The section calls this criterion the UCI inequality.Source: §IV · p. 21

A. Sufficient condition for the UCI inequality

This section proves a sufficient condition for the UCI inequality using auxiliary lemmas relating prefix-code bounds to cumulative codeword-length quantities and the Kraft sum.

A. Sufficient condition for the UCI inequality

  • For a prefix code C with L_C(1) = 1, Lemma 5 states that C*_C ≤ B exactly when S(k) ≤ c_B(k) for every k ≥ 2.Without the condition L_C(1) = 1, the bound is written c_B,C(k).Source: A. Sufficient condition for the UCI… · p. 21
  • If S(k) ≤ c_B,C(k) for every k ≥ 2, Lemma 6 gives B_n ≥ ⌈d_n+1,C(B)⌉ for every integer n ≥ 0.The bound follows from the lemma's intermediate inequality B_n−1 ≥ nk − c_B,C(k).Source: A. Sufficient condition for the UCI… · pp. 22–23
  • Lemma 7 expresses the Kraft sum using the previously defined notation for codeword lengths and their cumulative counts.The section introduces this identity before proving the sufficient condition.Source: A. Sufficient condition for the UCI… · p. 23
  • Theorem 6 presents a sufficient condition for the UCI inequality based on a prefix code C with L_C(1) = 1 and C*_C ≤ B.The proof applies Lemma 5 to obtain bounds on S(k), then uses Lemma 6 to bound B_n.Source: A. Sufficient condition for the UCI… · pp. 23–24

B. Necessary condition for the UCI inequality

The subsection proves a necessary-condition implication for the UCI inequality by constructing a prefix code with first codeword length 1 and expansion factor at most B; it also establishes that Σ(B) is nonincreasing.

B. Necessary condition for the UCI inequality

C. The optimal UCI with the minimum expansion factor C∗

The section characterizes the optimal expansion factor through the UCI inequality, narrows its value to a very tight interval, and shows how to construct an optimal UCI in theory.

C. The optimal UCI with the minimum expansion factor C∗

  • The UCI inequality characterizes C* via S = {B ≥ 1 | Σ(B) ≤ 7/4}: every B > C* lies in S, while Σ(B) > 7/4 rules out a prefix code with expansion factor ≤ B.Thus the threshold of Σ(B) yields an equivalent definition of C* as the infimum of S.Source: C. The optimal UCI with the minimum… · p. 27
  • Theorem 9(3) and Construction 1 yield an optimal UCI in theory: if the threshold infimum is attained at B0, C*=B0 and C(B0) is optimal; otherwise C*=lim bn and the sequence code is optimal.Source: C. The optimal UCI with the minimum… · p. 30
  • 2.000124757036101… is the reported numerical value of C*, narrowed to [2.0001247570, 2.0001247571].The lower and upper bounds improve from 2 and 2.0386, respectively.Source: C. The optimal UCI with the minimum… · pp. 29–30

V. CONCLUSIONS

The paper shows that one-point plus uniform-tail distributions are least favorable for UCI and uses them to derive the UCI inequality. This yields an equivalent definition of C* and a numerical value with fifteen certified decimal digits.

  • For every UCI, its worst-case ratio is attained by a one-point plus uniform-tail distribution, making this family least favorable.Source: §V · p. 30
  • The UCI inequality compares any real B with C* and plays the role for UCI that the Kraft inequality plays for prefix codes.The inequality provides the basis for an equivalent definition of C*.Source: §V · p. 30
  • C* = 2.000124757036101... was computed from the equivalent definition, with its first fifteen decimal digits certified; an optimal UCI can then be obtained in theory.Source: §V · p. 30
  • The theoretical optimal UCI is less concise and clear than Elias's classical γ code or the ν code, which attained expansion factor 2.0386; simpler codewords and a closed form remain future directions.Source: §V · pp. 30–31

APPENDIX A · PROOF OF EQUATION (27)

Appendix A proves Equation (27) by expressing d_n(B) through eS_n(x) and eU_n(x), interchanging sup and max, and reducing the computation to two suprema over integers. The proof analyzes the functions’ monotonicity to identify where those suprema are attained.

APPENDIX A · PROOF OF EQUATION (27)

  • The proof expresses d_n(B) using eS_n(x) and eU_n(x), interchanges sup and max, and reduces the computation to suprema over integers k ≥ 2.The reduced quantities are sup_{k≥2} eS_n(k) and sup_{k≥2} eU_n(k).Source: PROOF OF EQUATION (27) · p. 31
  • For eS_n(x), the proof differentiates after substituting y = σ_x, since the function is implicitly defined in x.It studies monotonicity over [2, ∞).Source: PROOF OF EQUATION (27) · p. 31
  • Z(y) first decreases and then increases, so Z_0 is its minimum over (2, ∞), and eS_n(x) is nonincreasing when n − 1 ≤ (B − 1)Z_0.In that case, eS_n(x) ≤ eS_n(2).Source: PROOF OF EQUATION (27) · pp. 32–33
  • When n − 1 > (B − 1)Z_0, the equation Z(y) = (n − 1)/(B − 1) has two roots, and the derivative of eS_n changes sign across them.The roots are y_1 < y_2, and x is strictly increasing in y on [2, ∞).Source: PROOF OF EQUATION (27) · p. 32
  • For eU_n(x), differentiation gives an increasing interval through x*_1 and a decreasing interval thereafter.The proof splits the integer-supremum calculation according to whether x*_1 ≤ 2 or x*_1 > 2; the threshold is n = (1 + 1/ln 2)B.Source: PROOF OF EQUATION (27) · p. 32
  • The integer supremum candidates include floor and ceiling values around x*_1 and x*_2.The proof concludes that this completes the proof of Equation (27).Source: PROOF OF EQUATION (27) · p. 33

APPENDIX B UPPER AND LOWER BOUNDS FOR C∗

This appendix describes a bisection algorithm for tightening upper and lower bounds on C∗ and reports numerical bounds that determine C∗ to 15 decimal places. Ball arithmetic is used to keep the computations rigorous.

APPENDIX B UPPER AND LOWER BOUNDS FOR C∗

  • Ball arithmetic encloses real-number computations, while rational endpoints are stored exactly and the tests use ball lower and upper bounds.If increasing the number of summed terms does not resolve the tests, the algorithm increases computation precision; it stops when the bound gap is at most 2^-ϵ.Source: Appendix B · pp. 33–34
  • Algorithm 1 bisects the current bounds on C∗, classifying each midpoint using a truncated sum and a tail upper bound, and adds terms when neither test decides.The algorithm updates the bounds based on whether the sum tests establish a lower or upper bound.Source: Appendix B · p. 33
  • Table II reports C∗ = 2.000124757036101... when 15 decimal places are kept, giving the stated value of C∗ under that decimal-place condition.For ϵ = 16, the output lower bound is B1 = 2.000122509765625; the passage also gives the output upper bound B2 = 2.00013193359375.Source: Appendix B · pp. 34–35

APPENDIX C · PROOF OF EQUATION (32)

Appendix C proves Equation (32) by bounding a quantity that decreases and then increases, applying logarithmic and sum-term inequalities, and combining the resulting bounds.

APPENDIX C · PROOF OF EQUATION (32)

Loading 2610.01563v1…