Optimal Universal Coding of Integers

Abstract

Universal coding of integers (UCI) provides prefix codes for positive integers such that, for every nonincreasing source distribution P, the average codeword length under P stays within K times max{1,H(P)}. For a given UCI 𝒞, the smallest such constant K is called the minimum expansion factor of 𝒞, denoted C_𝒞^*. Let C^*triangleq inf {C_𝒞^*} over all UCIs. A UCI attaining C^*, or a family of UCIs attaining C^* in the limit, is called optimal. It is currently known that 2≤ C^*≤ 2.0386. In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every UCI, a distribution in this family attains the worst-case ratio; thus, 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≥ 1, it decides whether B lies below or above C^*. The UCI inequality gives an equivalent definition of C^*. By numerical computation, we determine C^* = 2.00012475703610197861701176297579886254⋯, the first $38$ decimal digits being certified. Once C^* is known, we can theoretically construct the optimal UCI.

Optimal Hardy Inequalities for Fractional p-Laplacians on the Integers
Florian Fischer, Marius Nietschmann
HAL29 Sep 2026PreprintPublisher termsFull textAnalysis & PDEs Mathematical physicsHALarXiv
The optimal scale in Linnik's microsquare problem for almost all integers
Yu-Chen Sun, Lilu Zhao
arXiv12 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Variable-Length Feedback Coding With Universal Decoding and Bandit Channel Selection
Recep Can Yavas
arXiv27 Oct 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
The Exhaustive Peres Transform: Extraction and Universal Coding
Aur{é}lien Garivier
arXiv26 Oct 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
Co-Adaptive Entropy Modeling and Rate-Distortion-Optimal Bit Allocation for Perceptual Audio Coding
Soohyun Kim, Jiwon Jeong, Marina Bosi
arXiv12 Oct 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{yan2026optimal,
  title = {{Optimal Universal Coding of Integers}},
  author = {Wei Yan and Yunghsiang S. Han and Leqian Zheng},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.01563},
  eprint = {2610.01563},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.01563},
}

RIS

TY  - UNPB
TI  - Optimal Universal Coding of Integers
AU  - Wei Yan
AU  - Yunghsiang S. Han
AU  - Leqian Zheng
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.01563
UR  - https://arxiv.org/abs/2610.01563
AB  - Universal coding of integers (UCI) provides prefix codes for positive integers such that, for every nonincreasing source distribution P, the average codeword length under P stays within K times max{1,H(P)}. For a given UCI 𝒞, the smallest such constant K is called the minimum expansion factor of 𝒞, denoted C_𝒞^*. Let C^*triangleq inf {C_𝒞^*} over all UCIs. A UCI attaining C^*, or a family of UCIs attaining C^* in the limit, is called optimal. It is currently known that 2≤ C^*≤ 2.0386. In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every UCI, a distribution in this family attains the worst-case ratio; thus, 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≥ 1, it decides whether B lies below or above C^*. The UCI inequality gives an equivalent definition of C^*. By numerical computation, we determine C^* = 2.00012475703610197861701176297579886254⋯, the first $38$ decimal digits being certified. Once C^* is known, we can theoretically construct the optimal UCI.
ER  -

Abstract

Related

Cite