pith. sign in

arxiv: 2507.23180 · v2 · pith:HPTUU7APnew · submitted 2025-07-31 · 💻 cs.IT · math.IT

The Construction of Near-optimal Universal Coding of Integers

Wei Yan , Yunghsiang S. Han This is my paper

Pith reviewed 2026-05-19 03:14 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords universal coding of integersprefix codesexpansion factorν codedecreasing distributionsentropyminimum expansion factor
0
0 comments X

The pith

A new construction called the ν code achieves an expansion factor of 2.0386 for universal coding of integers and narrows the optimal range to between 2 and 2.0386.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Universal coding of integers supplies prefix codes that compress sequences from any unknown decreasing probability distribution over a countably infinite alphabet. The work first derives a stricter inequality relating probabilities in such distributions and then applies it to define the ν code. This yields a minimum expansion factor of 2.0386, which improves the prior upper bound of 2.5 while a separate argument reconfirms that no universal code can fall below 2. Readers care because the result supplies a concrete, better-performing family of codes that can be used when symbol frequencies are unknown in advance.

Core claim

By establishing a tighter probability inequality for decreasing distributions, the authors construct the ν code, a class of prefix codes whose average length stays within a factor of 2.0386 of the entropy for every such distribution. They prove that this value is the smallest expansion factor attained by any known construction and supply an independent argument showing that every universal code of integers must have minimum expansion factor at least 2. The combined statements place the optimal minimum expansion factor in the interval from 2 to 2.0386.

What carries the argument

The ν code, a specific family of prefix codes for the positive integers, together with the newly proved probability inequality that bounds its average length relative to entropy for any decreasing distribution.

Load-bearing premise

The proof that the ν code reaches 2.0386 rests on the new probability inequality holding for all decreasing distributions and being strong enough to control the code lengths.

What would settle it

An explicit decreasing probability distribution for which the average length of the ν code exceeds 2.0386 times the entropy, or a counter-example showing the stated probability inequality fails.

read the original abstract

The Universal Coding of Integers~(UCI) is suitable for discrete memoryless sources with unknown probability distributions and infinitely countable alphabet sizes. A UCI is a class of prefix codes for which the ratio of the average codeword length to $\max\{1,H(P)\}$ is within a constant expansion factor \textcolor{red}{$C_{\mathcal{C}}$} for any decreasing probability distribution $P$, where $H(P)$ is the entropy of $P$. For any UCI code $\mathcal{C}$, \emph{the minimum expansion factor} \textcolor{red}{$C_{\mathcal{C}}^{*}$} is defined to represent the infimum of the set of extension factors of $\mathcal{C}$. Each $\mathcal{C}$ has a unique corresponding \textcolor{red}{$C_{\mathcal{C}}^{*}$}, and the smaller \textcolor{red}{$C_{\mathcal{C}}^{*}$} is, the better the compression performance of $\mathcal{C}$ is. The class of UCIs $\mathcal{C}$ (or a family $\{\mathcal{C}_i\}_{i=1}^{\infty}$) that achieves the smallest \textcolor{red}{$C_{\mathcal{C}}^{*}$} is defined as the \emph{optimal UCI}. The best current result is that the range of $C_{\mathcal{C}}^{*}$ for the optimal UCI is $2\leq C_{\mathcal{C}}^{*}\leq 2.5$. In this paper, we prove a tighter probability inequality for decreasing distributions, which serves as a new tool for studying the properties of UCIs. On the basis of this inequality, we prove that there exists a class of near-optimal UCIs, called the $\nu$ code, achieving \textcolor{red}{$C_\nu=2.0386$}. This narrows the range of the minimum expansion factor for the optimal UCI to $2\leq C_{\mathcal{C}}^{*}\leq 2.0386$. We show that the $\nu$ code is currently optimal in terms of the minimum expansion factor. In addition, we propose a new proof showing that the minimum expansion factor of the optimal UCI is lower bounded by $2$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript proves a new inequality for sums of probabilities under decreasing distributions P and uses it to construct a family of universal integer codes (the ν-code) for which the expansion factor satisfies C_ν = 2.0386. Combined with an independent proof that every UCI satisfies C_C^* ≥ 2, the paper narrows the range for the optimal UCI to 2 ≤ C_C^* ≤ 2.0386 and claims that the ν-code is currently best known in this metric.

Significance. If the inequality and its application to the ν-code are valid, the work improves the best explicit upper bound on the minimal expansion factor from 2.5 to 2.0386, tightening the characterization of optimal universal integer coding. The new inequality may be reusable for other analyses of prefix codes on countable alphabets, and the explicit construction plus the lower-bound proof are concrete, verifiable contributions.

major comments (3)
  1. [§3] §3 (new probability inequality): the claimed tighter bound is load-bearing for the upper estimate on C_ν. The manuscript must show explicitly how the inequality is applied to bound L_ν(P)/max{1,H(P)} uniformly over all decreasing P, and whether the resulting 2.0386 is the exact supremum or only an upper bound obtained by plugging the inequality into an expression that may still contain a gap.
  2. [§4] §4 (ν-code definition and C_ν evaluation): the constant 2.0386 is presented as achieved by the construction. Please clarify whether this value is obtained by an analytic worst-case analysis, by taking the limit of a sequence of distributions, or by numerical optimization; if the latter, state the precision and verification method used to confirm that no larger ratio occurs for any decreasing P.
  3. [§5–6] §5–6 (application to expansion factor and lower-bound proof): the headline narrowing 2 ≤ C_C^* ≤ 2.0386 requires that the inequality plus the ν-code together rigorously cap the supremum at 2.0386. If the analysis only shows C_ν ≤ 2.0386 + ε for some small ε that is not driven to zero, the stated constant does not yet close the range.
minor comments (2)
  1. [Abstract, §1] Abstract and §1: the red-highlighted symbols C_C, C_C^*, and C_ν should be introduced once with consistent notation and then used uniformly; occasional switches between script C and plain C are distracting.
  2. [Figures and tables] Figure captions and Table 1: several numerical entries for code lengths and ratios lack error bars or statements of the number of distributions sampled; add a brief note on how the tabulated values were obtained.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below, providing the requested clarifications on the application of the inequality, the derivation of the constant, and the tightness of the resulting bound. Revisions will be made to improve explicitness where needed.

read point-by-point responses

  1. Referee: [§3] §3 (new probability inequality): the claimed tighter bound is load-bearing for the upper estimate on C_ν. The manuscript must show explicitly how the inequality is applied to bound L_ν(P)/max{1,H(P)} uniformly over all decreasing P, and whether the resulting 2.0386 is the exact supremum or only an upper bound obtained by plugging the inequality into an expression that may still contain a gap.

    Authors: We will revise Section 3 to include an explicit derivation subsection. The new inequality is applied directly to the weighted sum defining L_ν(P) for the ν-code lengths, yielding L_ν(P) ≤ 2.0386 ⋅ max{1, H(P)} uniformly for every decreasing P. The constant 2.0386 is the exact supremum of the ratio under this bound, attained in the limit along a specific sequence of distributions; no residual gap remains after the substitution. revision: yes

  2. Referee: [§4] §4 (ν-code definition and C_ν evaluation): the constant 2.0386 is presented as achieved by the construction. Please clarify whether this value is obtained by an analytic worst-case analysis, by taking the limit of a sequence of distributions, or by numerical optimization; if the latter, state the precision and verification method used to confirm that no larger ratio occurs for any decreasing P.

    Authors: The value is obtained analytically by considering a one-parameter family of decreasing distributions P_θ and deriving a closed-form expression for the ratio L_ν(P_θ)/max{1,H(P_θ)}. The supremum equals 2.0386 exactly in the limit as θ approaches its critical value. No numerical optimization is performed. The revised Section 4 will contain the full analytic derivation and the verification that the family covers the worst case. revision: yes

  3. Referee: [§5–6] §5–6 (application to expansion factor and lower-bound proof): the headline narrowing 2 ≤ C_C^* ≤ 2.0386 requires that the inequality plus the ν-code together rigorously cap the supremum at 2.0386. If the analysis only shows C_ν ≤ 2.0386 + ε for some small ε that is not driven to zero, the stated constant does not yet close the range.

    Authors: The combined analysis shows C_ν = 2.0386 with no additive ε. The inequality produces a uniform upper bound whose supremum is attained asymptotically by the same sequence of distributions used in the analytic derivation; the lower bound of 2 is established independently. The range is therefore closed exactly as stated. A clarifying remark will be added to Section 6. revision: partial

Circularity Check

0 steps flagged

No significant circularity: new inequality and explicit ν-code construction are independent of inputs

full rationale

The paper introduces a new tighter probability inequality for decreasing distributions as a tool and then constructs the ν code explicitly to achieve C_ν=2.0386, narrowing the range for optimal UCI. It also provides an independent new proof for the lower bound of 2. No quoted step reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation chain; the central claims rest on the fresh inequality and construction rather than renaming or smuggling prior results. The derivation is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The paper rests on standard information-theoretic definitions of prefix codes, entropy, and decreasing distributions. The ν code is an invented construction whose performance is derived from the new inequality. No explicit free parameters are fitted to data in the abstract.

axioms (2)
  • standard math Prefix codes satisfy the Kraft inequality and average length is at least the entropy for any distribution.
    Foundational property used to define the expansion factor C_C.
  • domain assumption Probability distributions are strictly decreasing over the positive integers.
    Stated requirement for the UCI definition and the new inequality.
invented entities (1)
  • ν code no independent evidence
    purpose: Explicit family of prefix codes achieving the improved expansion factor.
    The code is constructed in the paper using the new inequality; no external falsifiable prediction is supplied.

pith-pipeline@v0.9.0 · 5926 in / 1480 out tokens · 42608 ms · 2026-05-19T03:14:10.767051+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    A mathematical theory of communication,

    C. E. Shannon, “A mathematical theory of communication,” The Bell System Technical Journal , vol. 27, no. 3, pp. 379–423, Jul. 1948

    work page 1948

  2. [2]

    A mathematical theory of communication,

    C. E. Shannon, “A mathematical theory of communication,” The Bell System Technical Journal , vol. 27, no. 4, pp. 623–656, Oct. 1948

    work page 1948

  3. [3]

    A method for the construction of minimum-redundancy codes,

    D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proceedings of the IRE , vol. 40, no. 9, pp. 1098–1101, Sep. 1952

    work page 1952

  4. [4]

    R. C. Pasco, Source Coding Algorithms for Fast Data Compression . Ph.D. Dissertation, Stanford University, CA, USA, May 1976

    work page 1976

  5. [5]

    Arithmetic coding,

    J. Rissanen and G. G. Langdon, “Arithmetic coding,” IBM Journal of Research and Development , vol. 23, no. 2, pp. 149–162, Mar. 1979

    work page 1979

  6. [6]

    Universal codeword sets and representations of the integers,

    P. Elias, “Universal codeword sets and representations of the integers,” IEEE Transactions on Information Theory , vol. 21, no. 2, pp. 194–203, Mar. 1975

    work page 1975

  7. [7]

    An information-theoretic analysis of deduplication,

    U. Niesen, “An information-theoretic analysis of deduplication,” IEEE Transactions on Information Theory , vol. 65, no. 9, pp. 5688–5704, Sept. 2019

    work page 2019

  8. [8]

    Data deduplication with random substitutions,

    H. Lou and F. Farnoud, “Data deduplication with random substitutions,” IEEE Transactions on Information Theory , vol. 68, no. 10, pp. 6941–6963, Oct. 2022

    work page 2022

  9. [9]

    Compressstreamdb: Fine-grained adaptive stream processing without decompression,

    Y . Zhang, F. Zhang, H. Li, S. Zhang, and X. Du, “Compressstreamdb: Fine-grained adaptive stream processing without decompression,” in 2023 IEEE 39th International Conference on Data Engineering (ICDE) . Anaheim, CA, USA: IEEE, 2023, pp. 408–422

    work page 2023

  10. [10]

    Data-aware adaptive compression for stream processing,

    Y . Zhang, F. Zhang, H. Li, S. Zhang, X. Guo, Y . Chen, A. Pan, and X. Du, “Data-aware adaptive compression for stream processing,” IEEE Transactions on Knowledge and Data Engineering , vol. 36, no. 9, pp. 4531–4549, Sept. 2024. September 11, 2025 DRAFT 45

    work page 2024

  11. [11]

    Data structures and compression algorithms for high-throughput sequencing technologies,

    K. Daily, P. Rigor, S. Christley, X. Xie, and P. Baldi, “Data structures and compression algorithms for high-throughput sequencing technologies,” BMC Bioinform., vol. 11, p. 514, Oct. 2010

    work page 2010

  12. [12]

    SRComp: Short read sequence compression using burstsort and Elias omega coding,

    J. J. Selva and X. Chen, “SRComp: Short read sequence compression using burstsort and Elias omega coding,” PLOS ONE, vol. 8, no. 12, pp. 1–7, 12 Dec. 2013

    work page 2013

  13. [13]

    Compressstreamdb: Fine-grained adaptive stream processing without decompression,

    D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. V ojnovic, “Compressstreamdb: Fine-grained adaptive stream processing without decompression,” in 31st Conference on Neural Information Processing Systems (NIPS 2017) . Long Beach, CA, USA: MIT Press, 2017, pp. 1709–1720

    work page 2017

  14. [14]

    A new metric and the construction for evolving 2-threshold secret sharing schemes based on prefix coding of integers,

    W. Yan, S.-J. Lin, and Y . S. Han, “A new metric and the construction for evolving 2-threshold secret sharing schemes based on prefix coding of integers,” IEEE Transactions on Communications , vol. 71, no. 5, pp. 2906–2915, May 2023

    work page 2023

  15. [15]

    Flag encodings related to the zeckendorf representation of integers,

    R. M. Capocelli, “Flag encodings related to the zeckendorf representation of integers,” in Sequences, Combinatorics, Compression, Security, and Transmission. New York, NY , USA: Springer-Verlag, 1990, pp. 449–466

    work page 1990

  16. [16]

    On the redundancy and delay of decodable coding of natural numbers (in Russian),

    V . I. Levenshtein, “On the redundancy and delay of decodable coding of natural numbers (in Russian),” Problems of Cybernetics, vol. 20, pp. 173–179, 1968

    work page 1968

  17. [17]

    Economical encoding of commas between strings,

    S. Even and M. Rodeh, “Economical encoding of commas between strings,” Communications of the ACM , vol. 21, no. 4, pp. 315–317, Apr. 1978

    work page 1978

  18. [18]

    Improved prefix encodings of the natural numbers (corresp.),

    Q. F. Stout, “Improved prefix encodings of the natural numbers (corresp.),” IEEE Transactions on Information Theory , vol. 26, no. 5, pp. 607–609, Sep. 1980

    work page 1980

  19. [19]

    A new recursive universal code of the positive integers,

    H. Yamamoto, “A new recursive universal code of the positive integers,” IEEE Transactions on Information Theory , vol. 46, no. 2, pp. 717–723, Mar. 2000

    work page 2000

  20. [20]

    Robust transmission of unbounded strings using Fibonacci representations,

    A. Apostolico and A. S. Fraenkel, “Robust transmission of unbounded strings using Fibonacci representations,” IEEE Transactions on Information Theory, vol. 33, no. 2, pp. 238–245, Mar. 1987

    work page 1987

  21. [21]

    On universal codeword sets,

    K. Lakshmanan, “On universal codeword sets,” IEEE Transactions on Information Theory , vol. 27, no. 5, pp. 659–662, Sep. 1981

    work page 1981

  22. [22]

    Almost asymptotically optimal flag encoding of the integers,

    M. Wang, “Almost asymptotically optimal flag encoding of the integers,” IEEE Transactions on Information Theory , vol. 34, no. 2, pp. 324–326, Mar. 1988

    work page 1988

  23. [23]

    A new asymptotically optimal code for the positive integers,

    H. Yamamoto and H. Ochi, “A new asymptotically optimal code for the positive integers,” IEEE Transactions on Information Theory , vol. 37, no. 5, pp. 1420–1429, Sep. 1991

    work page 1991

  24. [24]

    Meta-Fibonacci codes: Efficient universal coding of natural numbers,

    B. T. Ávila and R. M. C. de Souza, “Meta-Fibonacci codes: Efficient universal coding of natural numbers,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 2357–2375, Apr. 2017

    work page 2017

  25. [25]

    On universal codes for integers: Wallace tree, Elias omega and beyond,

    L. Allison, A. S. Konagurthu, and D. F. Schmidt, “On universal codes for integers: Wallace tree, Elias omega and beyond,” in Proc. 2021 Data Compression Conference (DCC) , Mar. 2021, pp. 313–322

    work page 2021

  26. [26]

    On the minimum of the expansion factor for universal coding of integers,

    W. Yan and S.-J. Lin, “On the minimum of the expansion factor for universal coding of integers,” IEEE Transactions on Communications, vol. 69, no. 11, pp. 7309–7319, Nov. 2021

    work page 2021

  27. [27]

    A tighter upper bound of the expansion factor for universal coding of integers and its code constructions,

    W. Yan and S.-J. Lin, “A tighter upper bound of the expansion factor for universal coding of integers and its code constructions,” IEEE Transactions on Communications , vol. 70, no. 7, pp. 4429–4438, Jul. 2022

    work page 2022

  28. [28]

    Generalized universal coding of integers,

    W. Yan and S.-J. Lin, “Generalized universal coding of integers,” in Proc. IEEE Inf. Theory Workshop (ITW) . Kanazawa, Japan: IEEE, 2021, pp. 1–6

    work page 2021

  29. [29]

    Generalized universal coding of integers,

    W. Yan and Y . S. Han, “Generalized universal coding of integers,” IEEE Transactions on Communications , vol. 72, no. 8, pp. 4538–4550, Aug. 2024

    work page 2024

  30. [30]

    A new class of the universal representation for the positive integers,

    T. Amemiya and H. Yamamoto, “A new class of the universal representation for the positive integers,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , vol. E76A, no. 3, pp. 447–452, Mar. 1993

    work page 1993

  31. [31]

    P. K. Hung, Secrets in Inequalities (volume 1) . GIL Publishing House, 2007

    work page 2007

  32. [32]

    T. M. Cover and J. A. Thomas, Elements of information theory, 2nd ed . NY , USA: Wiley, 2006

    work page 2006

  33. [33]

    A device for quantizing, grouping, and coding amplitude-modulated pulses,

    L. G. Kraft, “A device for quantizing, grouping, and coding amplitude-modulated pulses,” Master’s thesis, Dept. of Electrical Engineering, Massachusetts Institute of Technology, Cambridge, Mass., 1949. September 11, 2025 DRAFT

    work page 1949