Pith. sign in

REVIEW 5 minor 19 references

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.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

Every finite digit string gets exactly one number, and consecutive numbers differ by a single edit — a complete, locally stable variable-length Gray code.

T0 review reviewed 2026-08-01 challenge →

load-bearing objection 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).

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

Variable-length Gray codes for the Natural Numbers

Ezequiel L\'opez-Rubio This is my paper
classification cs.IT math.IT
keywords Gray codevariable-length codesbijective numerationLevenshtein distanceb-ary codesedit distancelarge language modelsnumeracy
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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.

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

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

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.

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 this falsifier. Get emailed when new claim-graph text bears on it.

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}.

Where Pith is reading between the lines

These are 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, simulated authors' rebuttal, 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

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.

Axiom & Free-Parameter Ledger

1 free parameters · 4 axioms · 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.
axioms (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.

reviewed 2026-08-01 · 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}
}
Share X Bluesky LinkedIn Reddit HN
read the original 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 Ezequiel L\'opez-Rubio.

Figure 1
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… view at source ↗
Figure 2
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 wal… view at source ↗
Figure 3
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… view at source ↗
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) Cumulative bits to store {0, . . . , n}; the shaded gap is the saving, greatest on the small integers. 5.2 Compression Relative to Fixed-Le… view at source ↗
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 (dashed). (b) Cumulative digits to store {0, . . . , n}; the shaded gap is the saving. 0 200 400 600 n 0 1 2 3 4 5 6 codeword length (digits) … view at source ↗
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 (dashed). (b) Cumulative digits to store {0, . . . , n}; the shaded gap is the saving. The staircase has more, finer steps than at larger bases … view at source ↗

discussion (0)

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

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

    Pith/arXiv 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

    Pith/arXiv arXiv 2024

  9. [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

  10. [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

  11. [11]

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

    2011

  12. [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

  13. [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

  14. [14]

    Run-length encodings,

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

    1966

  15. [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

  16. [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

  17. [17]

    Salomaa,Jewels of Formal Language Theory

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

    1981

  18. [18]

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

    2006

  19. [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, pp. 1715–1725. 13

    2016

This paper was first reviewed by deepseek-v4-flash on August 1, 2026.