A Complete Proof for Tu-Deng Conjecture

Abstract

Let $N=2^k-1$ and let $\mathrm{wt}(n)$ denote the binary Hamming weight. The Tu-Deng conjecture asserts that, for every $1\le t\le N-1$, at most $2^{k-1}$ pairs $(a,b)\in \{0,\dots ,N-1{\}}^2$ satisfy $a+b\equiv t(\mathrm{mod}N)$ and $\mathrm{wt}(a)+\mathrm{wt}(b)<k$. Partial results are known. We give a complete proof of this conjecture. We first show that the Tu-Deng counts equals the number of cyclic carry solutions for which $\mathrm{wt}(B)-\mathrm{wt}(A)<0$ and $A+t\equiv B(\mathrm{mod}N)$. The enumerator of the cyclic carry solutions factors as $$C_v=1+(X+Y-1)J_v+X^{z(v)+1}{Y}^{o(v)+1},$$ where $t=10v$ is the binary expansion of $t$(least significant bits first) and $J_v$ enumerates the language $$\mathrm{Sub}(v)\dot{\cup }\{u\in {\partial }_1\mathrm{Sub}(v):u{<}_{\mathrm{lex}}v\}.$$ Estimating the strict negative half-plane mass of $C_v$ gives the desired bound.