Pith. sign in

REVIEW 5 minor 19 references

Variable-length Gray codes for the Natural Numbers

T0 review · 0 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For every base b, a variable-length Gray code bijects the natural numbers onto all finite b-ary strings, with consecutive integers exactly one edit apart.

desk verdict A clean, correct construction of a bijective variable-length Gray code with unit edit steps; the proofs hold, and the only caveats are minor (imported standard lemmas) or explicitly self-flagged (untested ML application). read the letter →

arxiv 2607.16088 v2 pith:5RTFYPXP submitted 2026-07-17 cs.IT math.IT

Ezequiel López-Rubio This is my paper
classification cs.ITmath.IT
keywords Graycodevariable-lengthcodesbijectivenumerationLevenshteindistanceb-aryeditlargelanguagemodelsnumeracy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper constructs, for each integer base b≥2, a code V_b that assigns to every natural number a finite string over {0,…,b−1}, and proves that every finite string (including the empty string) is the codeword of exactly one number. Consecutive numbers are always one edit apart: inside a length block one symbol is substituted, and at each block boundary a single leading symbol is inserted (0^k becomes 1 0^k). Codeword length is monotone in n and equals floor(log_b((b−1)n+1)), which stays within one symbol of the information-theoretic minimum. The author proposes this as a representation for numeric tokens in language models, since no string is invalid and counting becomes a local rewrite; the paper explicitly leaves the learning benefit as a testable hypothesis rather than a proven result.

What carries the argument

The load-bearing object is the fixed-length modular b-ary Gray code G(m,w), defined by copying the most significant base-b digit and setting each lower Gray digit to the difference modulo b from the next more significant digit. Two standard properties carry the argument: consecutive offsets yield Gray words that differ in exactly one position by +1 modulo b, and the endpoints are G(0,w)=0^w and G(b^w−1,w)=(b−1)0^{w−1}. The endpoint property is what makes every length block end at 0^k and the next begin at 1 0^k, so a single leading-symbol insertion connects blocks for every base at once. The leading-digit increment operation is a bijection on each block and preserves the substitution adjacen

What would settle it

Enumerate V_b(n) for n from 0 through N_K−1 for a small base such as b=10 and K=4, checking that d_L(V_b(n),V_b(n+1))=1 for every n and that the codewords are exactly the strings of length less than K, with no duplicates or omissions. A single violation would refute the central bijection/unit-edit claim.

Watch

Extended reading notes

Core claim

The central claim is that taking the modular b-ary Gray code of the within-block offset, with the leading digit incremented modulo b, yields a bijection V_b from the natural numbers onto the full string space {0,…,b−1}^* with d_L(V_b(n), V_b(n+1))=1 for every n. The proof partitions N into blocks B_k of size b^k starting at N_k=(b^k−1)/(b−1). Within a block, the Gray-code adjacency property gives a one-symbol substitution between successors, and the common leading increment cannot create or remove a disagreement; at block boundaries, the block ends at 0^k and the next block begins at 1 0^k, so a single leading insertion joins them. Thus V_b is a Hamiltonian enumeration of the infinite string

Load-bearing premise

The proof borrows two standard facts about the modular b-ary Gray code—successive offsets differ in one position by +1 modulo b, and the code runs from 0^w to (b−1)0^{w−1}—from the literature rather than proving them, and if either fact failed the unit-edit claim between consecutive codewords would collapse.

Editorial extensions

If this is right

  • Every finite string over the b-ary alphabet is a valid, unique numeral; a model never wastes probability on illegal leading-zero forms or the empty string.
  • The successor relation is a local operation: counting from n to n+1 rewrites at most one symbol, so a single-symbol corruption decodes to a neighboring integer rather than a distant one.
  • Length is self-adapting and near-optimal, so small integers—the ones dominating counters, indices, and offsets—use the fewest symbols; storing 0 through N costs less than any fixed-length Gray code covering the same range.
  • The moment the code lengthens is known exactly: the first length-k codeword appears at n=(b^k−1)/(b−1) and equals 1 0^{k−1}, which is a single insertion from the previous block's final codeword 0^{k−1}.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the unit-edit property holds in practice, a tokenizer built on V_b would make arithmetic operations like +1 purely local, allowing a language model to learn counting with fewer global rewrite rules; the paper does not test this.
  • The completeness property suggests a clean experiment: train a model on V_b-encoded numerals versus standard digit-level and sub-word encodings and compare on counting, arithmetic, and key retrieval; this would isolate the effect of surface form.
  • The construction may generalize to other combinatorial classes: any family that can be blocked by size and listed with unit-substitution adjacency inside blocks could get a variable-length Hamiltonian enumeration under edit distance, but this is our extension.
  • Because V_b is not self-delimiting, combining it with a prefix-free wrapper would give a complete, self-delimiting numeral system whose successor is still a single edit—an orthogonal design point the paper notes but does not develop.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper introduces, for every base b >= 2, a variable-length Gray code V_b that maps the natural numbers bijectively onto the set of all finite strings over the b-symbol alphabet. The construction partitions N into length blocks B_k of size b^k, starting at N_k = (b^k - 1)/(b - 1); within each block, the offset r is encoded by the modular b-ary Gray word G(r, k), with the leading digit incremented modulo b. Four theorems are proved for arbitrary b: (T1) V_b is a bijection from N onto {0,...,b-1}^*, with the empty string encoding 0; (T2) d_L(V_b(n), V_b(n+1)) = 1 for every n, via a single substitution inside a block and a single leading insertion 0^k -> 1 0^k at block boundaries; (T3) L(V_b(n)) = floor(log_b((b-1)n+1)), which is monotone non-decreasing; (T4) length k begins exactly at n = N_k with codeword 1 0^{k-1}. The paper also discusses compression relative to fixed-length Gray codes and proposes the code as a representation for numeric tokens in language models, explicitly flagging the empirical benefit as untested.

Significance. If correct, the paper gives a simple, original construction of an infinite analogue of a Gray code: a Hamiltonian enumeration of the full finite-string space under unit edit operations, with a self-adapting length profile that is within one symbol of the information-theoretic ideal. The four theorems are clean and the proofs are mostly self-contained. The construction is elegant and generalizes naturally from binary to arbitrary base, and the binary case exactly recovers the reflected binary Gray-code bijective numeration. The machine-learning motivation is plausible but explicitly declared speculative; it does not affect the mathematical content. The paper also provides worked examples, tables, and figures for b = 2, 3, 10, and includes reproducible algorithmic descriptions (Algorithms 1 and 2).

minor comments (5)
  1. [§3.2, Proposition 1(P2)] The adjacency property P2 is load-bearing for Theorem 2, but its proof only cites Knuth §7.2.1.1. Since the rest of the paper is self-contained, please include the short carry-based proof (adding 1 to m changes exactly one base-b digit by +1 mod b, and by Eq. (1) exactly one Gray digit changes by +1 mod b). This would remove the only imported ingredient.
  2. [Definition 1] The notation G(0,0) is used when k=0, but G(m,w) is defined only for w >= 1. Please state the convention G(0,0) = epsilon explicitly.
  3. [§2 and §3.2] The reflected Gray code is described as G(·, b) in Section 2, but later G(m, w) uses w as word length and b as base. This parameter collision may confuse readers; unify the notation.
  4. [Figure 4] The x-axis of Figure 4(a) ends at 30, while the caption claims the range {0,...,2^5-1} = {0,...,31}. Adjust either the axis or the caption for consistency.
  5. [§5.2] The statement that V_b attains the shortest possible length profile among monotone complete codes is true, but it is asserted without proof. A one-sentence block-filling argument (all b^k words of length k must be used before any word of length k+1) would make the near-optimality claim self-evident.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the construction and proofs are self-contained and the empirical motivation is explicitly labeled untested.

full rationale

The paper's central claims are Theorem 1 (bijectivity), Theorem 2 (unit Levenshtein distance), Theorem 3 (monotone length), and Theorem 4 (length-increment index). These all follow from the explicit Definition 1 of V_b and from the standard modular b-ary Gray code facts collected in Proposition 1. Lemma 1 derives the length formula directly from the block partition N_k = (b^k-1)/(b-1). Lemma 2 uses only the bijection property (P1) and the fact that incrementing the leading digit modulo b is a bijection on the alphabet. Theorem 1 then combines the block bijections. Theorem 2 uses property (P2) for intra-block neighbors and property (P5) for block boundaries; both are external, independently verifiable facts about the code defined by Eq. (1), and the boundary insertion 0^k -> 1 0^k is explicitly computed in Lemma 3. Theorem 3 is a monotonicity consequence of Lemma 1, and Theorem 4 is a direct evaluation at N_k. No parameter is fitted, no quantity is defined in terms of the result it is said to predict, and no self-citation chain carries the argument. The LLM-motivation material in Section 5 is explicitly offered as a design rationale and testable hypothesis, with the paper itself noting that empirical benefits are untested and left to future work; it is not load-bearing for the mathematical theorems. Accordingly, there is no circular step to report.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The construction introduces no free parameters beyond the input base b and no postulated entities; V_b is a defined construction, not an entity pulled from a hat. Proofs rely on standard modular Gray-code facts (P1-P5) imported from Knuth/Gilbert; these are textbook facts, so risk is low but the derivation is not fully self-contained. The application section additionally assumes the NLP numeracy literature's claim that surface form affects model performance — a domain assumption clearly labeled as the basis of a hypothesis.

free parameters (1)
  • base b = arbitrary integer b ≥ 2
    Design parameter of the code family, not fitted to data; all four theorems hold for every b≥2. Listed for transparency only.
assumptions (4)
  • standard math Modular b-ary Gray code properties P1-P5 (bijectivity, unit Hamming adjacency, leading-digit preservation, zero-padding, endpoints 0^w and (b-1)0^{w-1})
    Imported from Knuth TAOCP §7.2.1.1 and Gilbert 1958 (Proposition 1). P2 is the load-bearing adjacency fact for Theorem 2; P5 is needed for the block-boundary insertion.
  • standard math Levenshtein distance definition and d_L ≤ d_H for equal-length strings
    Section 3.1; translates Hamming adjacency inside blocks into unit edit distance.
  • standard math Bijective numeration and universal code background
    Section 2 context (Salomaa, Knuth, Elias); not load-bearing for the theorems.
  • domain assumption Surface form of numerals measurably affects LLM numeracy (cites [4-8])
    Load-bearing for the Section 5.3 application argument only. The paper itself labels the benefit a testable hypothesis and lists caveats.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Variable-length Gray codes for the Natural Numbers." pith.science (2026). https://pith.science/paper/5RTFYPXP

@misc{pith2026260716088,
  author       = {Pith},
  title        = {Pith review of: Variable-length Gray codes for the Natural Numbers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5RTFYPXP}},
  note         = {Machine review of arXiv:2607.16088}
}
abstract

The modular $b$-ary Gray code arranges fixed-length $b$-ary representations of intervals of natural numbers so that consecutive numbers differ in a single digit. Its usefulness, however, is tied to a fixed word length. We introduce, for every integer base $b\ge 2$, a \emph{variable-length Gray code} $V_{b}$: a bijection from the natural numbers onto the set of all finite strings over the $b$-symbol alphabet $\{0,1,\dots,b-1\}$. The construction orders the natural numbers by codeword length into blocks and lists each block along the modular $b$-ary Gray code of the within-block offset, with its leading digit incremented modulo $b$. We prove four properties for arbitrary $b$. First, $V_{b}$ is a bijection, a complete code that assigns exactly one codeword to every finite string over the alphabet, including the empty string. Second, the Levenshtein (edit) distance between the codewords of two consecutive integers is always one. Third, codeword length is monotone non-decreasing in the encoded number. Fourth, the transition to codewords of length $k$ occurs exactly at $n=N_{k}=\sum_{i=0}^{k-1}b^{i}$, where $V_{b}(n)=1\,0^{k-1}$. The presented code, therefore, realizes a Hamiltonian enumeration under unit edit steps while retaining a near-optimal, self-adapting length profile. These properties suggest a use in machine learning: large language models routinely emit natural numbers as symbol strings, yet the positional notations they rely on are neither complete -- strings with leading zeros are invalid or redundant -- nor locally stable, since incrementing a number may rewrite many symbols at once. Because $V_{b}$ is a complete code and moves by a single edit between consecutive integers, it removes both obstacles and is a natural candidate representation for numeric tokens; we develop this argument and discuss the code's compression behavior relative to fixed-length Gray codes.

Figures

Figures reproduced from arXiv: 2607.16088 by the authors.

Figure 1
Figure 1. The enumeration V2(0), V2(1), V2(2), . . . for b = 2 as a walk on {0, 1} ∗ under unit Levenshtein steps. Each column is a length block; within a column, consecutive codewords differ by one substitution (Theorem 2, interior case), and each block boundary is a single insertion of a leading one, taking 0 k to 1 0k (Theorems 2 and 4). The walk visits every finite binary string exactly once (Theorem 1). Theorem 1 (Biject… view at source ↗
Figure 2
Figure 2. The enumeration V10(0), V10(1), . . . for b = 10 as a walk on {0, . . . , 9} ∗ , up to n = 1000; vertical ellipses compress each block. Within block 1 the ten codewords run 1, 2, . . . , 9, 0, each consecutive pair differing by a single￾digit substitution; the steps ε 7→ 1, 0 7→ 10, and 00 7→ 100 are single leading-digit insertions taking 0 k to 1 0k . The index n = 1000 lies in the length-3 block. The walk visits e… view at source ↗
Figure 3
Figure 3. The enumeration V3(0), V3(1), . . . for b = 3 as a walk on {0, 1, 2} ∗ , up to n = 1000; vertical ellipses compress each block. Block k (the length-k ternary words) runs from 1 0 k−1 to 0 k ; consecutive codewords inside a block differ by a single-digit substitution, and each boundary 0 k 7→ 1 0k is a single leading-digit insertion. Because b = 3 is small, the blocks stack quickly: n = 1000 already lies in the lengt… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Compression of the binary code V2 against a fixed-length 5-bit binary Gray code, over the range {0, . . . , 2 5− 1} = {0, . . . , 31} that such a code represents. (a) Per-integer codeword length L(V2(n)) = ⌊log2 (n + 1)⌋ (steps) versus the constant 5 bits (dashed). (b)…
Figure 5
Figure 5. Figure 5: Compression of the decimal code V10 against a fixed-length 3-digit decimal Gray code, over the range {0, . . . , 103 − 1} = {0, . . . , 999} that such a code represents. (a) Per-integer codeword length L(V10(n)) = ⌊log10(9n + 1)⌋ (steps) versus the constant 3 digits (d…
Figure 6
Figure 6. Figure 6: Compression of the ternary code V3 against a fixed-length 6-digit ternary Gray code, over the range {0, . . . , 3 6 − 1} = {0, . . . , 728} that such a code represents. (a) Per-integer codeword length L(V3(n)) = ⌊log3 (2n + 1)⌋ (steps) versus the constant 6 digits (das…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 2 linked inside Pith

  1. [1]

    Pulse code communication,

    F. Gray, “Pulse code communication,” 1953, u.S. Patent 2,632,058, filed 13 Nov. 1947, granted 17 Mar. 1953

    1953

  2. [2]

    Gray codes and paths on then-cube,

    E. N. Gilbert, “Gray codes and paths on then-cube,”Bell System Technical Journal, vol. 37, no. 3, pp. 815–826, 1958

    1958

  3. [3]

    The Gray code,

    R. W. Doran, “The Gray code,” Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, Tech. Rep. CDMTCS-304, 2007

    2007

  4. [4]

    Representing numbers in NLP: a survey and a vision,

    A. Thawani, J. Pujara, F. Ilievski, and P. Szekely, “Representing numbers in NLP: a survey and a vision,” in Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Lin- guistics: Human Language Technologies. Association for Computational Linguistics, 2021, pp. 644–656

    2021

  5. [5]

    Numeracy for language models: Evaluating and improving their ability to predict numbers,

    G. Spithourakis and S. Riedel, “Numeracy for language models: Evaluating and improving their ability to predict numbers,” inProceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Melbourne, Australia: Association for Computational Linguistics, 2018, pp. 2104–2115

    2018

  6. [6]

    Investigating the limitations of transformers with simple arithmetic tasks,

    R. Nogueira, Z. Jiang, and J. Lin, “Investigating the limitations of transformers with simple arithmetic tasks,” arXiv preprint arXiv:2102.13019, 2021

    arXiv 2021

  7. [7]

    Do NLP models know numbers? Probing numeracy in embeddings,

    E. Wallace, Y . Wang, S. Li, S. Singh, and M. Gardner, “Do NLP models know numbers? Probing numeracy in embeddings,” inProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). Hong Kong, China: Association for Computational Linguistics, ...

    2019

  8. [8]

    Tokenization counts: The impact of tokenization on arithmetic in frontier LLMs,

    A. K. Singh and D. Strouse, “Tokenization counts: The impact of tokenization on arithmetic in frontier LLMs,” arXiv preprint arXiv:2402.14903, 2024

    arXiv 2024

Show all 19 references
  1. [9]

    Binary codes capable of correcting deletions, insertions, and reversals,

    V . I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,”Soviet Physics Dok- lady, vol. 10, no. 8, pp. 707–710, 1966

    1966

  2. [10]

    A survey of combinatorial Gray codes,

    C. Savage, “A survey of combinatorial Gray codes,”SIAM Review, vol. 39, no. 4, pp. 605–629, 1997

    1997

  3. [11]

    D. E. Knuth,The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Upper Saddle River, NJ: Addison-Wesley, 2011

    2011

  4. [12]

    Error detecting and error correcting codes,

    R. W. Hamming, “Error detecting and error correcting codes,”Bell System Technical Journal, vol. 29, no. 2, pp. 147–160, 1950

    1950

  5. [13]

    Universal codeword sets and representations of the integers,

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

    1975

  6. [14]

    Run-length encodings,

    S. W. Golomb, “Run-length encodings,”IEEE Transactions on Information Theory, vol. 12, no. 3, pp. 399–401, 1966

    1966

  7. [15]

    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, 1987

    1987

  8. [16]

    Robust universal complete codes for transmission and compression,

    A. S. Fraenkel and S. T. Klein, “Robust universal complete codes for transmission and compression,”Discrete Applied Mathematics, vol. 64, no. 1, pp. 31–55, 1996

    1996

  9. [17]

    Salomaa,Jewels of Formal Language Theory

    A. Salomaa,Jewels of Formal Language Theory. Rockville, MD: Computer Science Press, 1981

    1981

  10. [18]

    T. M. Cover and J. A. Thomas,Elements of Information Theory, 2nd ed. Hoboken, NJ: Wiley-Interscience, 2006

    2006

  11. [19]

    Neural machine translation of rare words with subword units,

    R. Sennrich, B. Haddow, and A. Birch, “Neural machine translation of rare words with subword units,” inPro- ceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Berlin, Germany: Association for Computational Linguistics,...

    2016

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.