Tu–Deng conjecture

For every integer $k\ge 2$ , let $N=2^k-1$ . For every integer $t$ with $1\le t\le N-1$ , the number of pairs $(a,b)\in\{0,1,\ldots,N-1\}^2$ satisfying $a+b\equiv t\pmod N$ and $\operatorname{wt}_k(a)+\operatorname{wt}_k(b)<k$ is at most $2^{k-1}$ , where $\operatorname{wt}_k(x)$ denotes the Hamming weight of the $k$ -bit binary representation of $x$ ; equivalently, $\#\{(a,b)\in\{0,\ldots,N-1\}^2:a+b\equiv t\pmod N,\ \operatorname{wt}_k(a)+\operatorname{wt}_k(b)<k\}\le 2^{k-1}$ for all such $k$ and $t$ .

Progress summary

Solved

A new preprint claims the conjecture is proved, but the result has not yet been independently checked.

The Tu–Deng conjecture asserts that, for $N=2^k-1$ and $1\leq t\leq N-1$ , the number of pairs satisfying $a+b\equiv t\pmod N$ and $\operatorname{wt}(a)+\operatorname{wt}(b)<k$ is at most $2^{k-1}$ . It is connected to related binary sum-of-digits and coding-theoretic conjectures.

Known results

Tu and Deng verified the conjecture for $k\leq 29$ ; Flori extended this to $k\leq 40$ .
Spiegelhofer and Wallner proved it for a set of parameters of asymptotic density one.
A 2020 preprint proved the required bound when $\operatorname{wt}(t)\leq 10$ .

August 2026 claimed proof

An August 2026 preprint announces a complete proof via cyclic carry solutions and a negative-half-plane bound for an associated enumerator; a daily listing identifies Thomas W. Cusick with a further claimed proof. The claim is unrefereed and has no recorded independent verification. The authors also report a Lean formalization and acknowledge assistance from ChatGPT 5.6 Pro.

Current status (as of August 2026): The conjecture has a complete-proof claim in an unrefereed preprint, but no independent verification is recorded, so the claim remains unconfirmed.

Sources

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Proof of the TuDeng Conjecture — arXiv — Thomas W. Cusick

3 days ago