REVIEW 1 major objections 4 minor 2 cited by
Proof of the TuDeng Conjecture
T0 review · 1 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read This paper proves the Tu–Deng conjecture, the 2011 bound on low-weight modular pairs that underpins optimal algebraic immunity of Boolean functions.
desk verdict A complete, self-contained proof of the Tu–Deng conjecture; the load-bearing differential decomposition survives scrutiny, and the paper deserves a serious 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 load-bearing object is $H_W(u,v)$, the unique polynomial attached to a cyclic binary word $W$ through the trace of its $2\times2$ matrix product, normalized so that $\operatorname{tr} M_W - u^r v^z = 1 + (u+v-1)H_W$. The load-bearing mechanism is the positive differential decomposition of Theorem 5.1, which expresses $H_W + D_uH_W$ as a sum of nonnegative polynomials attached to the one- and zero-positions of $W$; this is the sole source of the normalized inequalities $i h_{i,j} \le (i+j)h_{i-1,j}$ and their mirror image. The diagonal case of those inequalities enters Lemma 8.2, an exact median identity that converts the bound on the negative Laurent mass into the pair-count bound.
What would settle it
To settle the claim, search for a cyclic binary word for which $H_W + D_uH_W$ has a negative coefficient; finding one would contradict Theorem 5.1 and undo the coefficient inequalities. Alternatively, an explicit $k \ge 30$ and $t$ with $|D_{t,k}| > 2^{k-1}$ would directly falsify Theorem 8.4, since the conjecture was previously checked only through $k=29$.
Extended reading notes
Core claim
On the paper's own terms, the central claim is Theorem 8.4: for every $k \ge 2$ and $1 \le t < 2^{k-1}$, the set $D_{t,k}$ of integers $n$ in $[0,2^{k-1}]$ with $\operatorname{wt}(n \oplus_k t) < \operatorname{wt}(n)$ satisfies $|D_{t,k}| \le 2^{k-1}$. Theorem 6.1 identifies this count with the original Tu–Deng pair count $|S_{t,k}|$. The route is exact: a cyclic transfer identity expresses $2^k$ times the trace of a product of $2\times2$ matrices as a Laurent polynomial whose negative-power coefficient is $|D_{t,k}|/2^k$, and a median identity bounds that negative mass by $1/2$. The proof obtains the needed bound from a positive differential decomposition of the polynomial $H_W$, which produces the normalized coefficient inequalities (12)–(13).
Load-bearing premise
The proof depends on a single nonnegativity fact: for every cyclic binary word, a particular polynomial combination associated to that word has no negative coefficients, and all later inequalities, including the final bound, are derived from that fact.
Editorial extensions
If this is right
- The sum-of-digits density conjecture follows: for every positive integer $t$, more than half of all $n$ satisfy $\operatorname{wt}(n+t) \ge \operatorname{wt}(n)$.
- The Tu–Deng Boolean-function families become rigorously optimal in algebraic immunity, so no conjectural caveat remains attached to those constructions.
- The earlier almost-sure result is upgraded to a finite theorem: the proportion of good parameters is not merely tending to $1$, it is all of them.
- The normalized coefficient inequalities give a new structural constraint on the polynomials $H_W$ attached to cyclic binary words.
Reading between the lines
- One can use the transfer identity (35) to compute exact values of $|D_{t,k}|$ for fixed small $k$; the paper stops at the inequality.
- The same positive-differential framework may apply to other modular pair counts with different digit-weight functions; the paper makes no such claim.
- If the full normalized inequalities (12)–(13) hold beyond the diagonal case used here, they likely imply sharper information about the coefficients $h_{i,j}$ than the single diagonal bound.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper gives a complete proof of the 2011 Tu–Deng conjecture on the number of pairs (a,b) in a cyclic modular window whose binary weight sum is smaller than k. The proof proceeds by converting the original pair count into a cyclic Hamming weight-drop count (Theorem 6.1), then establishing a two-variable matrix-polynomial transfer identity (Theorem 6.2) that connects the weight-drop count to a trace of products of 2x2 matrices. The core of the proof is algebraic: the cyclic polynomial H_W is shown to satisfy normalized coefficient inequalities (12)-(14), which are derived from a positive differential decomposition (Theorem 5.1) and a six-state nonnegative recurrence (Theorem 2.2). The final deduction combines an exact median identity (Lemma 8.2) with a top-boundary coefficient formula (Theorem 8.3) for words with few ones. The argument is self-contained and does not assume the conjecture.
Significance. If the proof is correct, this resolves a well-known conjecture of Tu and Deng that has been open since 2011 and has direct cryptographic consequences for Boolean functions with optimal algebraic immunity. The proof is notable for its explicit algebraic structure: the key identities are stated concretely and are amenable to independent verification. In particular, I checked the positive differential decomposition (27), the normalized inequalities (12)-(14), the carry-consistent trace expansion (Lemma 7.3), and the median identity (41); I found no hidden sign or factor error. The proof is fully self-contained, with no circular reliance on the conjecture or on equivalent statements. The main weakness of the manuscript is a serious notational inconsistency in the definition of the modulus M, which must be corrected before the stated theorem matches the proof.
major comments (1)
- [§1, §6.1, §8.4] The integer M is defined inconsistently, and this affects the statement of the main theorem. Conjecture 1.1 and the beginning of §6.1 set M=2^{k−1}, but the proof of Theorem 6.1 uses M=∑_{i=0}^{k−1}2^i=2^k−1 and explicitly calls M the k-bit word 11...1. Section 7.4 also counts n over 'all k-bit strings, that is, over {0,1,...,M}', which is correct only for M=2^k−1. Under the literal definition M=2^{k−1}, identity (34) is false; for k=3, M=4, a=0, we have wt(M−a)=wt(4)=1 but k−wt(a)=3. Consequently Theorem 6.1, and with it the proof of the conjecture, does not apply to the modulus stated in Conjecture 1.1. The proof is coherent only if M=2^k−1 throughout; in that case the ranges in Conjecture 1.1, Theorem 8.4, and the abstract must be changed from 1≤t<2^{k−1} to 1≤t<2^k−1. This appears to be a typo rather than a structural flaw, but it is load-bearing because the theorem as currently printed is not what the proof establishes.
minor comments (4)
- [§1 and Abstract] The historical account of the Cusick sum-of-digits conjecture is confusing and likely inaccurate. The abstract and the introduction state that Cusick's conjecture was proved by K. Cheng in 2026, but reference [3] (Drmota, Kauers, and Spiegelhofer, SIAM J. Discrete Math. 30 (2016)) is a 2016 paper whose title announces a proof of a conjecture of Cusick. Please clarify exactly what [3] proves and what Cheng's proof adds, and reconcile the attribution.
- [§6.2 and Lemma 8.2] The notation 'x−1/2' appears in the definitions of B_0(x) and B_1(x) and in Lemma 8.2. If the intended substitution is v=x^{-1}/2, it should be typeset unambiguously as x^{-1}/2; the current rendering can be misread as x−1/2.
- [§8.4] In the proof of Theorem 8.4, the sentence 'Since 1≤t<2^{k−1}, we have 1≤r≤k−1' is another consequence of the M typo. With the corrected range 1≤t<2^k−1, the needed conclusion follows from t∉{0,M} and t≠0; the proof should say this explicitly.
- [§7.5] In the proof of Lemma 7.5, 'and its s equals n⊕'_k t' should read 'and its s equals n⊕'_k t'; the phrase is grammatically incomplete. This is a minor editorial issue.
Circularity Check
No significant circularity: the proof is self-contained and derives the conjectured bound from algebraic identities and nonnegativity arguments.
full rationale
The paper does not assume the Tu–Deng conjecture or any equivalent statement. Its strongest claim, Theorem 8.4, is deduced from the normalized coefficient inequalities (12)–(14), which are established in Theorem 5.2 from the positive differential decomposition (Theorem 5.1, Eq. (27)). That decomposition is proven entirely from local determinant identities (Lemma 4.1), the nonnegative six-state recurrence (Theorem 2.2), and exact differentiation in Z[u,v]; no fitted parameter or prior conjectural input appears. The equivalence between the pair-count formulation |S_{t,k}| and the cyclic weight-drop count |D_{t,k}| (Theorem 6.1) is an explicit bijection, not an assumption. The cyclic transfer identity (Theorem 6.2) is proven from a carry-consistency bookkeeping lemma (Lemmas 7.1–7.5), again self-contained. The only external result cited is Cheng's proof of Cusick's conjecture [1], and the paper explicitly states it is used only as 'the main conceptual stimulus,' not as a premise: 'Cheng's theorem does not by itself prove the stronger Tu–Deng conjecture, but its method is the main conceptual stimulus for the present proof.' This is not load-bearing in the logical derivation. All inequalities, including the top-boundary formula (Theorem 8.3) and the median identity (Lemma 8.2), are derived in the paper with explicit coefficient or combinatorial proofs. No step reduces to its own conclusion by definition or by self-citation. The central nonnegativity source, Eq. (27), is a proven algebraic identity with nonnegative coefficients following from Theorem 2.2. Therefore the derivation chain is independent of the target result.
Assumptions & free parameters
assumptions (3)
- standard math Z[u,v] is an integral domain, so the factor u+v−1 can be cancelled in polynomial identities.
- standard math Cyclic invariance of matrix trace.
- domain assumption The carry-consistency equations (36) correctly represent binary addition n+t modulo 2^k−1.
Cite this review
Pith. "Pith review of Proof of the TuDeng Conjecture." pith.science (2026). https://pith.science/paper/A4DU3Y5A
@misc{pith2026260814821,
author = {Pith},
title = {Pith review of: Proof of the TuDeng Conjecture},
year = {2026},
howpublished = {\url{https://pith.science/paper/A4DU3Y5A}},
note = {Machine review of arXiv:2608.14821}
}
read the original abstract
We give a complete proof of the 2011 Tu--Deng conjecture. We begin from its original modular pair-count formulation, prove an equivalent cyclic Hamming weight-drop formulation, and establish the exact transfer identity that connects this count with a two-variable matrix polynomial. The proof then reduces the conjecture to normalized inequalities for the coefficients of that polynomial. A 2011 conjecture by the author which came to be called the Cusick Conjecture (it is a consequence of the Tu--Deng Conjecture) was proved by K. Cheng in 2026. The proof in the present paper extends the cyclic deletion ideas of Cheng. The new ideas might be applicable to other problems.
Forward citations
Cited by 2 Pith papers
-
Sharp extremal asymptotics for Cusick's sum-of-digits bias at fixed Hamming weight
The minimal Cusick bias among numbers with exactly k ones in binary is asymptotically (1/(2*sqrt(pi))) (log_2 k / k)^(3/2).
-
Cyclic deletion rigidity and Macaulay shadows in the Tu--Deng problem
The Tu-Deng bound is attained exactly when every gap of zeros in the cyclic binary word contains at least Z-1 ones, resolving Conjecture 3.20 of Flori, Randriambololona, Cohen and Mesnager.
Reference graph
Works this paper leans on
-
[1]
Cheng,A first-exit proof of Cusick’s sum-of-digits conjecture, arXiv:2606.23398, 2026
K. Cheng,A first-exit proof of Cusick’s sum-of-digits conjecture, arXiv:2606.23398, 2026
arXiv 2026
-
[2]
T. W. Cusick, Y. Li, and P. St˘ anic˘ a,On a combinatorial conjecture, Integers11(2011), 185–203
work page 2011
- [3]
-
[4]
L. Spiegelhofer and M. Wallner,The Tu–Deng conjecture holds almost surely, Electron. J. Com- bin.26(2019), no. 1, Paper P1.28
work page 2019
- [5]
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.