{"id":"eb4ef0ed-b33a-48f0-9e47-c495606f1404","arxiv_id":"2608.14821","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves that for every k≥2 and each nonzero t below 2^k−1, the number of binary pairs with weight sum below k and sum congruent to t modulo 2^k−1 is at most 2^{k−1}.","lead":"This mathematics paper claims a complete proof of the 2011 Tu-Deng conjecture, a long-standing open problem in binary combinatorics related to Boolean functions with optimal algebraic immunity. The proof reduces the conjecture to inequalities on coefficients of a two-variable polynomial and derives those inequalities with matrix algebra.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the critical positive-differential decomposition (Eq. 27) survives re-derivation.","rationale":"The reader accepted with moderate confidence, and my independent pass found no flaw in the chain. The central mechanism is the nonnegative decomposition; it checks out. The transfer identity and its carry proof were verified on small examples, and the final case split 2r≥k versus 2r<k correctly accounts for the determinant term. The only soft spot is the absence of machine-checked or second-expert verification of a long multi-stage proof, which the reader already priced into MODERATE confidence. Hence no adjustment to the verdict is needed.","tokens_in":10982,"tokens_out":40530,"duration_ms":322043,"concrete_test":"Run a symbolic script that, for every cyclic word W of length k≤8, computes H_W via the six-state recurrence (6)–(7), forms H_W+D_uH_W, independently evaluates the RHS of Eq. (27) from the same recurrence, and asserts coefficientwise equality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I attempted to break the argument at the reader's weakest point, Theorem 5.1. The decomposition (27) is the sole source of the normalized coefficient inequalities (12)–(14), so any sign error there would be fatal. Re-deriving it: D_uC_1=e_0ρ and D_uC_0=e_1ρ give (28); (29) follows from det(S_iP_i)=u^{r−1}v^z (respectively u^rv^{z−1}) and the identity r(u−1)u^{r−1}v^z+z u^rv^{z−1}=D_u(u^rv^z). Lemma 4.1 then converts each summand into exactly sγ_{V(i)} or sδ_{V(i)}, and since D_uQ_W=s(H_W+D_uH_W) with s=u+v−1, cancellation in the integral domain Z[u,v] is valid. The RHS is nonnegative by Theorem 2.2. I also spot-checked Theorem 5.2 on small words, verified Theorem 8.3's top-boundary formula on W=1100 and W=1010 (giving h_{1,1}=1 and 2 respectively), and checked the median identity (41) coefficient-by-coefficient; no hidden sign or factor appears. The proof is long but internally consistent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11197,"tokens_out":21304,"duration_ms":177008,"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":[{"comment":"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.","section":"§1, §6.1, §8.4"}],"minor_comments":[{"comment":"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.","section":"§1 and Abstract"},{"comment":"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.","section":"§6.2 and Lemma 8.2"},{"comment":"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.","section":"§8.4"},{"comment":"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.","section":"§7.5"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Candid take: this is the real thing—a complete proof of the Tu–Deng conjecture, self-contained and internally consistent. The genuinely new pieces are the Hamming weight-drop equivalence (Theorem 6.1), the transfer identity (Theorem 6.2), and especially the positive differential decomposition (Theorem 5.1), which reduces the conjecture to a coefficient inequality for H_W. That decomposition is the one step that has to be airtight; I re-derived it and it survives. The reader's stress-test note matches my own checks: the determinant identities, the carry-consistent triple count, the median identity, and the top-boundary formula all line up. No circularity: Cheng's Cusick proof is cited as inspiration, not used as a premise. No fitting: the bounds are derived for all k and t, with no free parameters.\n\nSoft spots: the paper is long, and the main theorem rests on many moving parts. Some steps are asserted as 'direct calculation' rather than shown, so an independent verifier will need real time. That is a readability issue, not a correctness issue. The single most delicate point is nonnegativity in Eq. (27); if it failed anywhere, the median argument would collapse. I could not make it fail. A short computer check of the key identities for small k would make the paper easier to trust, but the absence of code is not a flaw in a mathematics paper.\n\nThe intended audience is people working on Boolean functions, algebraic immunity, and sum-of-digits problems; they will cite this. My recommendation is to accept it as a research claim and send it to a careful referee, with specific instructions to verify Theorem 5.1 and the top-boundary formula. I would take it.","headline":"A complete, self-contained proof of the Tu–Deng conjecture; the load-bearing differential decomposition survives scrutiny, and the paper deserves a serious referee.","tokens_in":11705,"tokens_out":1786,"would_cite":true,"duration_ms":17834,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"pith_extraction":{"msc":["05A15","11A63","68R15","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves the Tu–Deng conjecture, the 2011 bound on low-weight modular pairs that underpins optimal algebraic immunity of Boolean functions.","keywords":["Tu-Deng conjecture","Hamming weight","binary digits","Boolean functions","algebraic immunity","cyclic words","matrix polynomial","sum-of-digits conjecture"],"falsifier":"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$.","tokens_in":10768,"feed_emoji":"🧮","tokens_out":16840,"duration_ms":138957,"temperature":0.7,"pith_summary":"This paper gives a complete proof of the 2011 Tu–Deng conjecture, a finite counting statement in binary combinatorics with cryptographic roots. The conjecture bounds the number of pairs $(a,b)$ of $k$-bit integers with fixed sum modulo $2^{k-1}$ and total Hamming weight below $k$ by $2^{k-1}$, exactly the condition that underlies a construction of Boolean functions with optimal algebraic immunity. The proof converts the pair count into a cyclic word count, transfers that count into the coefficients of a two-variable matrix polynomial, and proves coefficient inequalities that force the bound. The result is uniform: the bound holds for every $k \\ge 2$ and every admissible $t$, with the associated sum-of-digits density conjecture following as a corollary.","feed_headline":"Tu–Deng conjecture proved for every k and t","feed_subtitle":"Every eligible pair count now obeys the 2^{k−1} bound, settling a cryptographic conjecture from 2011.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the cyclic deletion and first-exit method that the paper's algebraic coefficient inequalities extend.","marker":"[1]"},{"why":"Studies the pair-count formulation directly, proves the conjecture for many parameter families, and documents the computational verification up to $k=29$ that the new theorem covers uniformly.","marker":"[2]"},{"why":"Establishes the almost-sure version of the conjecture, the asymptotic baseline that Theorem 8.4 replaces with a uniform statement.","marker":"[4]"},{"why":"States the original conjecture and gives its cryptographic context of Boolean functions with optimal algebraic immunity.","marker":"[5]"}],"fun_headline_variants":["Tu–Deng conjecture is now a theorem for all k, t","Every k and t: Tu–Deng conjecture proven","2011 crypto conjecture Tu–Deng finally proved","Tu–Deng bound proven for all pair counts","Cyclic deletion proof settles Tu–Deng"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Tu–Deng conjecture is now a theorem for all k, t","Every k and t: Tu–Deng conjecture proven","2011 crypto conjecture Tu–Deng finally proved","Tu–Deng bound proven for all pair counts","Cyclic deletion proof settles Tu–Deng"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000777,"raw_usage":{"total_tokens":3397,"prompt_tokens":868,"completion_tokens":2529,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":2449}},"tokens_in":484,"tokens_out":2529,"duration_ms":16264,"temperature":1.0,"reasoning_tokens":2449,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-27T21:10:28.572753+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Studies the pair-count formulation directly, proves the conjecture for many parameter families, and documents the computational verification up to $k=29$ that the new theorem covers uniformly."},{"cited_title":"Spiegelhofer and M","cited_arxiv_id":null,"evidence_quote":"Establishes the almost-sure version of the conjecture, the asymptotic baseline that Theorem 8.4 replaces with a uniform statement."},{"cited_title":"Tu and Y","cited_arxiv_id":null,"evidence_quote":"States the original conjecture and gives its cryptographic context of Boolean functions with optimal algebraic immunity."}],"review_version":1}