{"id":"2ad09d21-53dd-4614-ac86-962514f7d7f6","arxiv_id":"1908.08817","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every fixed k, the maximum length of a d-dimensional circuit code of spread k is 2^{d+O_k(log^2 d)}.","lead":"This paper proves that the longest cycle in a d-dimensional hypercube with a fixed spacing constraint has length about 2^d, up to a log-squared factor in the exponent. The result settles the asymptotic growth rate for every fixed spread k, a question that was open for k at least 3.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The rate proof's representation claim is unproved but true: the induction condition d_{m+1} ≤ d_1 + ∑_{i≤m} d_i holds, so the reader's main concern resolves without changing the verdict.","rationale":"The reader flagged the representation property as the weakest assumption. Stress-testing shows it is the correct spot to examine, but it is true for this specific sequence; the standard interval-induction works once the overlap inequality is checked. Other flagged issues (the −4/−1 constant mismatch, the unexpanded Preparata–Nievergelt extension) are minor exposition gaps. The superadditivity argument is coherent: the displayed a_m + b_n inequality is supported by the symmetric form of Klee's theorem, and a_m + a_n follows from a_n ≤ b_n. No load-bearing correctness flaw was found. The appropriate disposition remains conditional on adding the missing verifications, so UNCHANGED.","tokens_in":3239,"tokens_out":29202,"duration_ms":252461,"concrete_test":"Verify the complete-sequence condition for d_i = 2^i + 2i + 5k − 1: check that d_{m+1} ≤ ∑_{i=1}^m d_i + d_1 for every m ≥ 1; explicitly, compute d_{m+1} − (∑_{i=1}^m d_i + d_1) = −m(m−1+5k−1) ≤ 0. If this inequality holds, the 'by induction' representation claim in the proof of Theorem 1.1 is established, and the rate argument is sound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1.1 relies on representing every d ≥ 1 as d = p + ∑ ε_i d_i with 0 ≤ p < d_1 and d_i = 2^i + 2i + 5k − 1, asserted only by induction. This is the most load-bearing step: if false, the rate argument gives no lower bound for arbitrary d. For a generic sequence with exponential growth this kind of claim is false, so the assertion needs checking. Direct verification succeeds. Let S_m = ∑_{i=1}^m d_i = 2^{m+1} − 2 + m(m+1) + mC with C = 5k − 1 and d_1 = C + 4. Then d_{m+1} − (S_m + d_1) = −m(m−1+C) ≤ 0 for all m ≥ 1. Hence the intervals [0, S_m + d_1 − 1] and [d_{m+1}, S_{m+1} + d_1 − 1] overlap, so the standard complete-sequence induction proves the representation. The related constant mismatch (5k−4 in Proposition 3.3 versus 5k−1 in the rate proof) is also harmless because d_i − 3 equals the Proposition 3.3 dimension, and K(n,k) is monotone in n. The manuscript should include these one-line verifications, but the central claim is not undermined.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":3558,"tokens_out":23442,"duration_ms":183868,"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":[{"comment":"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.","section":"Theorem 1.1, proof of rate"},{"comment":"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.","section":"Proposition 3.1"}],"minor_comments":[{"comment":"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.","section":"Proposition 3.1"},{"comment":"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.","section":"Proposition 3.1 / Theorem 1.1"},{"comment":"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.","section":"Theorem 1.1"},{"comment":"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.","section":"Lemma 2.2"}],"recommendation":"major_revision","confidential_remarks":"The main theorem appears correct and the missing steps are one-line verifications that can be added without changing the architecture of the proof. I recommend major revision rather than rejection because the omitted representation proof and the imprecise citation in Proposition 3.1 are load-bearing as written, even though they are easily repairable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on the Byrnes–Spinu paper. The main theorem is the real thing: for every fixed spread k, the maximum length of a d-dimensional circuit code satisfies log2 K(d,k) = d + O_k(log^2 d), so the asymptotic exponent ν(k) = 1. Previous work only had weak general bounds and long codes on sparse subsequences of dimensions. The proof idea is to show that the sequence log2 K(d−3,k) is superadditive up to a constant when k is even (Proposition 3.1), apply Fekete to get the limit exists (Corollary 3.2), and then use the known Preparata–Nievergelt constructions on a carefully chosen subsequence to force the limit to be 1 (Proposition 3.3). The superadditivity transfer is a genuinely new technique and it works. The rate estimate then comes from representing every integer d as a sum of distinct terms from the subsequence.\n\nThe one load-bearing step that worried the reader was the representation claim in the proof of Theorem 1.1: 'any integer d can be written as p + ∑ ε_i d_i' with d_i = 2^i + 2i + 5k − 1, asserted only 'by induction'. I checked it, and the claim is true: because d_{m+1} ≤ d_1 + ∑_{i≤m} d_i, the intervals overlap and the complete-sequence induction goes through. The stress-test verification confirms this, so the theorem is not in jeopardy. There is also a constant mismatch: Proposition 3.3 uses 5k−4 while the rate proof uses 5k−1. That is harmless—the two sequences differ by 3 and K(n,k) is monotone in n—but the paper should say so explicitly. The same goes for the 'by induction' line, which needs a one-sentence verification.\n\nSo the central argument holds up. The soft spots are presentation-level: three unstated one-liners (the induction condition, the constant shift, and the monotonicity argument) that would make the proof self-contained. None of them undermines the theorem. The citations look appropriate: Klee, Preparata–Nievergelt, Singleton, Fekete, and the self-citation [2] is only for notation. No circularity.\n\nThis is a short, significant paper that resolves a long-open exponent for all k. I'd send it to a competent referee expecting a minor-revision decision. It should be in the literature. My reading group would enjoy the superadditivity trick.","headline":"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.","tokens_in":4050,"tokens_out":2519,"would_cite":true,"duration_ms":23802,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every fixed spread k, the longest d-dimensional circuit code has length $2^{d+O(\\log^2 d)}$.","keywords":["circuit codes","hypercube graph","spread","extremal cycle length","difference-preserving codes","superadditivity","asymptotic growth rate"],"falsifier":"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.","tokens_in":3020,"feed_emoji":"🧮","tokens_out":15839,"duration_ms":140843,"temperature":0.7,"pith_summary":"A circuit code of spread $k$ is a cycle in the $d$-dimensional hypercube whose distances along the cycle never fall below the smaller of the Hamming distance between its vertices and $k$. The paper proves that for every fixed $k$, the maximum length $K(d,k)$ of such a cycle is $2^{d+O(\\log^2 d)}$ as $d$ grows. Equivalently, the asymptotic exponent $\\nu(k)=\\lim_{d\\to\\infty} \\log_2 K(d,k)/d$ exists and equals $1$ for all $k$: in the exponent, the longest circuit code is as long as the hypercube itself, up to a log-squared correction. This closes a gap in which the exponent for $k\\ge 3$ was only known to be bounded below by a constant around $2/k$, while explicit long codes existed only in sparse dimensions. The proof gets there by showing the growth exponent is independent of $k$ and then showing it is $1$ on a specially spaced sequence of dimensions.","feed_headline":"Circuit codes reach near-maximum length in every dimension","feed_subtitle":"For fixed spread k, the longest hypercube cycle has length 2^{d+O(log^2 d)}.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the long difference-preserving code paths in dimensions $d_i=2^i+2i+5k-4$ that become the sparse-dimensional lower bound after closing them into circuit codes.","marker":"[6]"},{"why":"Gives the product inequality $K(m+n+2,k) \\ge (1/k)K(m+1,k-1,k)K(n,k)$ that produces superadditivity when combined with the dimension-lifting lemma.","marker":"[5]"},{"why":"Provides the superadditivity lemma used to conclude that the growth exponent exists.","marker":"[3]"},{"why":"Restates the superadditivity lemma, the tool cited for the limit in Corollary 3.2.","marker":"[8]"},{"why":"Provides the lower bound $K(d,k) \\ge (k+1)2^{\\lfloor 2d/(k+1)\\rfloor-1}$ used to prove $K(d,k)>2(d-1)k$ for the dimension-lifting lemma.","marker":"[7]"},{"why":"Establishes the base cases $K(d,1)=2^d$ and $K(d,2)\\ge(3/10)2^d$, which anchor $\\nu(1)=\\nu(2)=1$.","marker":"[1]"}],"fun_headline_variants":["Circuit codes reach near-maximum length in all dimensions","Circuit codes nearly as long as possible","Hypercube cycles get near-optimal length","Asymptotic order of circuit codes found","Circuit codes almost as long as a full cycle"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Circuit codes reach near-maximum length in all dimensions","Circuit codes nearly as long as possible","Hypercube cycles get near-optimal length","Asymptotic order of circuit codes found","Circuit codes almost as long as a full cycle"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000638,"raw_usage":{"total_tokens":2877,"prompt_tokens":820,"completion_tokens":2057,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":436,"completion_tokens_details":{"reasoning_tokens":1989}},"tokens_in":436,"tokens_out":2057,"duration_ms":17002,"temperature":1.0,"reasoning_tokens":1989,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:30:25.954064+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the long difference-preserving code paths in dimensions $d_i=2^i+2i+5k-4$ that become the sparse-dimensional lower bound after closing them into circuit codes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the product inequality $K(m+n+2,k) \\ge (1/k)K(m+1,k-1,k)K(n,k)$ that produces superadditivity when combined with the dimension-lifting lemma."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the superadditivity lemma used to conclude that the growth exponent exists."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Restates the superadditivity lemma, the tool cited for the limit in Corollary 3.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the lower bound $K(d,k) \\ge (k+1)2^{\\lfloor 2d/(k+1)\\rfloor-1}$ used to prove $K(d,k)>2(d-1)k$ for the dimension-lifting lemma."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the base cases $K(d,1)=2^d$ and $K(d,2)\\ge(3/10)2^d$, which anchor $\\nu(1)=\\nu(2)=1$."}],"review_version":1}