REVIEW 2 major objections 4 minor 8 references
On the Asymptotic Order of Circuit Codes
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For every fixed spread k, the longest d-dimensional circuit code has length $2^{d+O(\log^2 d)}$.
desk verdict The theorem holds; the paper's chief worry—the unproved representation claim—is true, and the remaining issues are cosmetic, so send it to a referee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the sequence $a_n=\log_2(K(n-3,k)/k)$ for even $k$ and the superadditivity-up-to-a-constant inequality $a_m+a_n\le a_{m+n}$, obtained by composing a product construction for circuit codes with a dimension-lifting lemma. This forces the growth exponent to exist and to be independent of $k$. The second machine is the sparse family of dimensions $d_i=2^i+2i+5k-4$ supplied by difference-preserving code constructions; closing those open paths into circuit codes gives the lower bound that fixes the common exponent at $1$. The third machine is the subset-sum representation $d=p+\sum_i \varepsilon_i d_i$ with $d_i=2^i+2i+5k-1$, used to push the rate from the subsequence to all integers $d$, with the $O(\log^2 d)$ error accumulating from summing $\log d_i$ over the $O(\log d)$ terms.
What would settle it
For a fixed small $k$ (say $k=2$), enumerate the subset sums of $d_i=2^i+2i+5k-1$ up to a large bound and test whether every integer $d$ is represented as $p$ plus such a subset sum with $0\le p<d_1$; a single counterexample would refute the asserted covering property that the $O(\log^2 d)$ rate step depends on.
Extended reading notes
Core claim
The paper's Theorem 1.1 states that $\log_2 K(d,k)=d+O(\log^2 d)$ for each integer $k\ge 1$, with the implied constant depending only on $k$, and hence $\nu(k)=1$. The proof has two load-bearing parts. First, for even $k$ the normalized sequence $\log_2 K(d-3,k)$ is superadditive up to a constant, so the standard superadditivity lemma gives existence of the limit and the inequality $a_n\le b_n\le a_{2n}-a_n$ forces the same exponent for $k-1$; thus $\nu(k-1)=\nu(k)$ for all $k$. Second, an existing construction of difference-preserving codes supplies circuit codes of length $2^{d_i-O(i)}$ in dimensions $d_i=2^i+2i+5k-4$, making the common exponent $1$ along a subsequence. Finally, the claim that every integer $d$ is a small residue plus a subset sum of the shifted dimensions $d_i=2^i+2i+5k-1$ extends the rate from the subsequence to all dimensions, at the cost of the $O(\log^2 d)$ term.
Load-bearing premise
The proof's rate step assumes, without showing the details, that every integer $d\ge 1$ can be written as $d=p+\sum_i \varepsilon_i(2^i+2i+5k-1)$ with $0\le p<d_1$ and $\varepsilon_i\in\{0,1\}$; if that 'by induction' covering property fails for the actual sequence, the $O(\log^2 d)$ rate is not established for all dimensions.
Editorial extensions
If this is right
- For every fixed $k$ and all sufficiently large $d$, a $(d,k)$ circuit code exists with at least $2^{d-C\log^2 d}$ vertices, where $C$ depends only on $k$.
- The normalized logarithm $\log_2 K(d,k)/d$ tends to $1$ for every $k$, so the earlier general lower bounds of order $2/k$ are superseded for large $d$.
- The growth exponent is independent of spread: $\nu(k)=1$ for every $k$, so changing $k$ does not change the exponential growth rate.
- Because $K(d,k)$ is trivially at most $2^d$, the theorem pins the true maximum to the interval $[2^{d-C\log^2 d},\,2^d]$, a subexponential multiplicative window.
Reading between the lines
- My inference: because the proof uses only the superadditivity inequality and the sparse lower-bound construction, the same strategy should transfer to other long-path extremal problems in hypercubes, such as codes with restricted transition sets.
- My inference: the $O(\log^2 d)$ error is an artifact of the subset-sum covering step; a construction that produced long codes in every dimension would reduce the error to $O(\log d)$.
- My inference: the theorem predicts that for fixed $k\ge 3$, computational searches at moderate $d$ should show $\log_2 K(d,k)/d$ approaching $1$ with a deficit of order $(\log^2 d)/d$; a substantially larger persistent deficit would cast doubt on the claimed rate.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies K(d,k), the maximum length of a circuit code of spread k in the d-dimensional hypercube. The main result (Theorem 1.1) is that log2 K(d,k) = d + O_k(log^2 d) as d → ∞, which determines the asymptotic order ν(k) = 1 for every fixed k. The proof combines a superadditivity property of log2 K(d−3,k) for even k (Proposition 3.1), a Fekete-type argument showing ν(k−1) = ν(k) (Corollary 3.2), and the Preparata–Nievergelt construction giving codes of length 2^{d+O(log d)} on a subsequence of dimensions (Proposition 3.3). A representation of every dimension as a small perturbation of a subset sum of the good dimensions converts the subsequence bound into the full-sequence O(log^2 d) rate.
Significance. If the proof is completed, this is a clean and strong result: for fixed spread k, the maximum length of a d-dimensional circuit code grows like 2^d, and the spread condition costs only a poly-logarithmic factor in the exponent. This substantially improves the general lower bound ν(k) ≥ 2/(k+1) and unifies the small-k results. The method is transparent, relying on Klee's product construction, Fekete's lemma, and the Preparata–Nievergelt difference-preserving codes; it does not fit constants or define the target in terms of itself. The paper is concise, but two load-bearing technical verifications are omitted and should be supplied before publication.
major comments (2)
- [Theorem 1.1, proof of rate] The representation claim that every d ≥ 1 can be written as d = p + ∑ ε_i d_i with 0 ≤ p < d_1 and ε_i ∈ {0,1} for d_i = 2^i + 2i + 5k − 1 is asserted only as '(by induction)' and is not demonstrated. This is load-bearing because for generic sequences with exponential growth the claim is false. The claim is in fact true: with S_m = ∑_{i=1}^m d_i, one has d_{m+1} − (S_m + d_1) = −m(m + 5k − 2) ≤ 0 for all m ≥ 1, so the intervals [0, S_m + d_1 − 1] and [d_{m+1}, S_{m+1} + d_1 − 1] overlap and the standard complete-sequence induction goes through. Please add this verification (or an equivalent argument) to the proof.
- [Proposition 3.1] The inequality chain K(m−3,k−1)K(n−3,k) ≤ kK(m+n−3,k) is not fully justified as written. Corollary 2.3, as stated, requires the first dimension parameter to be at most the second and contains K(m,k−1) rather than K(m−2,k−1,k). In the case n = m the ordering condition m−2 ≤ n−3 fails. The intended step is valid: Klee's theorem ([5], Theorem 1) directly gives K(m+n−4,k) ≥ (1/k)K(m−2,k−1,k)K(n−3,k), and monotonicity of K(·,k) yields the stated bound for K(m+n−3,k). The proof should spell out this use of the underlying theorem rather than citing Corollary 2.3 without comment, and should address the n = m case explicitly.
minor comments (4)
- [Proposition 3.1] The line 'That is, a_m + b_n ≤ a_{m+n}' should read b_m + a_n ≤ a_{m+n} (or a_n + b_m); the displayed product corresponds to b_m + a_n. The subsequent deduction of superadditivity is unaffected, but the notation should be corrected.
- [Proposition 3.1 / Theorem 1.1] The case k = 2 is not covered by Lemma 2.2 when that lemma is applied with spread k−1, because Lemma 2.2 requires the spread to be at least 2. This case is harmless since K(d,2) ≥ (3/10)2^d already gives the theorem (even with d+O(1)), but the proof should say so explicitly.
- [Theorem 1.1] The sequence d_i = 2^i + 2i + 5k − 1 used in the rate proof is the dimension from Proposition 3.3 plus 3, because a_n is defined via K(n−3,k). This connection is correct but should be stated explicitly to avoid the appearance of a constant mismatch with Proposition 3.3's d_i = 2^i + 2i + 5k − 4.
- [Lemma 2.2] In the last sentence of the proof, 'the condition K(d,k) > 2(d−1)k ensures there are enough such segments' could be made more precise by noting that N/2 > (d−1)k implies floor(N/(2k)) ≥ d−1 ≥ p.
Circularity Check
No circularity: the proof uses external constructions and standard lemmas; the sole self-citation is notational.
full rationale
The paper's central claim log2 K(d,k) = d + O(log^2 d) is derived from (i) Klee's product construction (external, [5]) via Corollary 2.3, (ii) the standard Fekete lemma (external, [3,8]), and (iii) the Preparata-Nievergelt difference-preserving code construction (external, [6]), extended to a circuit code by explicitly duplicating the transition sequence with k new dimensions. The superadditivity argument in Proposition 3.1 does not define K in terms of itself; it uses an inequality relating lower-dimensional circuit codes, with a small constant factor absorbed by dividing by k. Proposition 3.3 injects an external subsequence lower bound; Theorem 1.1 combines this with superadditivity and a representation of every d as a binary sum of d_i, which is asserted ('by induction') but is a checkable arithmetic fact, not a fitted or self-referential assumption. The only self-citation is [2], used solely for notation ('Our notation follows [2]'); no load-bearing premise is imported from it. No parameter is fitted to a subset of data and then called a prediction, and no uniqueness theorem is invoked from the authors' prior work. Thus no circular step is present; the unproved representation claim is a potential rigor gap, not circularity.
Assumptions & free parameters
assumptions (3)
- standard math Fekete's lemma for superadditive sequences
- domain assumption Preparata-Nievergelt construction gives difference-preserving codes of length N ≥ 2^{d_i - O(i)} in dimensions d_i = 2^i + O(i)
- ad hoc to paper Every integer d can be represented as p plus a subset sum of the sequence d_i = 2^i + 2i + 5k − 1 with 0 ≤ p < d_1
Cite this review
Pith. "Pith review of On the Asymptotic Order of Circuit Codes." pith.science (2026). https://pith.science/paper/ROEZDA3F
@misc{pith2026190808817,
author = {Pith},
title = {Pith review of: On the Asymptotic Order of Circuit Codes},
year = {2026},
howpublished = {\url{https://pith.science/paper/ROEZDA3F}},
note = {Machine review of arXiv:1908.08817}
}
abstract
In this note we prove that the maximum length of a $d$-dimensional circuit code of spread $k$ equals $2^{d+O_k(\log^2d)}$, with the implied constant depending only on $k$.
Reference graph
Works this paper leans on
-
[2]
K. M. Byrnes. The maximum length of circuit codes with lon g bit runs and a new characterization theorem. Designs, Codes and Cryptography , May 2019
work page 2019
-
[5]
V. Klee. A method for constructing circuit codes. Journal of the ACM , 14(3):520–528, 1967
work page 1967
-
[1]
H. L. Abbot and M. Katchalski. On the construction of snak e in the box codes. Utilitas Mathematica, 40:97–116, 1991
work page 1991
-
[3]
M. Fekete. ¨Uber die verteilung der wurzeln bei gewissen algebraischen gleichungen mit ganzzahligen koeffizienten. Mathematische Zeitschrift , 17(1):228–249, 1923
work page 1923
-
[4]
B. Gr¨ unbaum, G.C. Shephard, and V. Klee. Convex Polytopes . Springer-Verlag, New York, New York, 2003
work page 2003
-
[6]
F. P. Preparata and J. Nievergelt. Difference-preservin g codes. IEEE Transactions on Information Theory, 20(5):643–649, 1974
work page 1974
-
[7]
R. C. Singleton. Generalized snake-in-the-box codes. IEEE Trans. Electronic Computers, 15:596–602, 1966
work page 1966
-
[8]
J.M. Steele. Probability Theory and Combinatorial Optimization . CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and A pplied Mathematics, Philadelpha, 1997. 3
work page 1997
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.