The Tu-Deng conjecture is a statement about binary numbers and their digit sums. If you write numbers in binary, the "weight" of a number is simply how many 1s appear in its binary representation. The conjecture concerns pairs of numbers that add up to a fixed target value (working with clock-like arithmetic on numbers up to a power of 2), where the combined count of 1-bits in both numbers is relatively small. Specifically, it claims that no matter what target you pick, at most half of all possible pairs can satisfy this low-weight condition simultaneously. This turns out to be relevant for cryptography, where such counting results help measure the resistance of certain functions used in encryption against attacks.
Previous work had confirmed the conjecture only in special cases, such as when the target number has a particularly simple binary pattern. The new proof handles every possible target value without restriction. The key move is to reframe the problem: instead of directly counting low-weight pairs, the authors translate the question into counting solutions involving carries that arise when you add binary numbers in a cyclic way. A carry is what happens when two 1-bits in the same position combine and "overflow" into the next position. By tracking how carries propagate through the binary digits, the problem becomes more structured and easier to control.
The authors then express this carry-counting problem using a compact algebraic formula involving two variables, where the formula itself encodes information about the binary structure of the target number. They analyze a particular subword language, meaning patterns that appear as contiguous pieces within the binary expansion of the target. By carefully estimating how much of this formula's "weight" falls in a certain region of the plane (corresponding to the cases where one number has more 1-bits than the other), they establish the bound the conjecture requires. The result closes a problem that had been open for roughly fifteen years.