The Tu-Deng Conjecture, proposed in 2011, concerns a specific set of pairs of integers defined using binary arithmetic. For any integer t written in binary using k bits, the conjecture places an upper limit on how many pairs of numbers (a, b) can simultaneously satisfy two conditions: their sum equals t when computed with a particular kind of modular arithmetic, and the total count of 1s in their binary representations is less than k. The conjecture says this count of pairs can never exceed half of 2 to the power k. After sitting open for about 15 years, the conjecture was proven independently by two groups in 2026.
This paper goes a step further and asks: when does the count of pairs exactly hit that upper limit, rather than falling short of it? The answer turns out to depend entirely on how the 0 bits are arranged in the binary representation of t. Specifically, if you look at the positions of the zeros in t's binary expansion and measure the gaps between consecutive zero positions (going around in a cycle), equality holds if and only if every one of those gaps is at least as large as the total number of zeros. The authors phrase this same condition in several equivalent ways, including a forbidden pattern rule, a packing condition, and a condition about how the gaps between zeros can be broken up into smaller pieces.
The paper also provides a formula for counting exactly how many values of t achieve this maximum, among those with a given number of zeros in their binary representation. The various equivalent characterizations give different geometric and combinatorial intuitions for the same underlying structure, and the results connect back to specific coefficients appearing in a polynomial used in the original proof of the conjecture. Overall, the work completes the picture around the Tu-Deng bound by fully classifying when the bound is tight.