The Tu–Deng conjecture on binary Hamming weights

Let $k$ be a positive integer and let $t\in\{1,\ldots,2^k-2\}$. Define

$$S_{t,k}=\Bigl\{(a,b)\in\bigl\{0,\ldots,2^k-2\bigr\}^2:a+b\equiv t\bmod 2^k-1,\ w(a)+w(b)<k\Bigr\}$$

and let $P_{t,k}=\lvert S_{t,k}\rvert/2^k$.

Tu–Deng conjecture. For every such $k$ and $t$, one has

$$P_{t,k}\leq \frac12.$$

Here $w(n)$ denotes the Hamming weight, or number of $1$s in the binary expansion of $n$. The conjecture concerns the distribution of binary Hamming weights under addition modulo $2^k-1$; it is known in various special cases and has been checked computationally for several ranges of $k$. The paper proves that the inequality holds for a proportion of $t$ tending to $1$ as $k\to\infty$, but the full uniform assertion remains open.