For every integer k≥ 2, let N=2^k-1. For every integer t with 1≤ t≤ N-1, the number of pairs (a,b)∈0,1,…,N-1^2 satisfying a+b equiv t pmod N and operatornamewt_k(a)+operatornamewt_k(b)<k is at most 2^k-1, where operatornamewt_k(x) denotes the Hamming weight of the k-bit binary representation of x; equivalently, #(a,b)∈0,…,N-1^2:a+b equiv t pmod N, operatornamewt_k(a)+operatornamewt_k(b)<k≤ 2^k-1 for all such k and t.

Tu–Deng conjecture

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.

Tu–Deng conjecture

Primary source

Additional references

Progress summary

Solutions 0