The Courtade–Kumar and Hellinger conjectures

The explanation

Toss three fair coins. Send each result down a line that flips it with probability 10%. Before sending, you may also record one yes-or-no fact about the three coins. How much does that one fact reveal about what arrives? Information is measured in bits, and one fair yes-or-no answer is worth at most one bit.

The choice of fact matters. Take "what did the first coin show?" It reveals about 0.531 bits about the noisy copies. Majority vote of the three coins reveals about 0.457 bits. "Did all three land heads?" reveals about 0.257 bits. Whether the number of heads is odd reveals about 0.198 bits. Without noise, the first coin, majority and odd-or-even would each reveal a full bit. Noise erodes them at different rates.

The first coin's score has a closed form. It equals 1 − h(0.1), where h is the binary entropy. That is the uncertainty, in bits, of a coin that lands one way 10% of the time. There are 256 possible yes-or-no facts about three coins. A short program can try all 256. None beats 0.531 bits.

Gowtham Kumar and Thomas Courtade asked whether this holds in general. Their conjecture, from 2013 and 2014, says one coordinate is always best. A coordinate means a single input coin, like the first one. The claim covers every noise level and any number of coins. For thousands of coins, nobody can try every fact by computer. Earlier work settled pieces. Alex Samorodnitsky proved it in 2016 for all yes-or-no facts when the noise is high. Lei Yu's work reached a wider noise range for balanced facts, those that say yes half the time. It used a computer-assisted argument.

A second question sits beside it. In a 2017 manuscript, Anantharam, Bogdanov, Chakrabarti, Jayram and Nair posed the Hellinger conjecture. It asks how distinguishable the noisy copies are after a yes versus after a no. It scores this with Hellinger affinity, a standard measure of overlap. The conjecture says a single coin again comes out on top, even for facts that are not balanced. Those authors showed it implies the Courtade–Kumar conjecture. The score here is the loss of affinity: how much overlap the noise destroys. In our example, the first coin keeps an affinity of 0.6, a loss of 0.4. Majority vote keeps about 0.649, a loss of about 0.351. The conjecture says no fact can lose more than 0.4 at this noise level.

The obstacle was bookkeeping. A natural plan splits the coins on one coin and builds the bound from the two halves. Tracking only how much information each half holds is not enough to make that step work. The first paper says the proof must also track the bias, meaning how often a fact answers yesSource 1. It does that and closes the induction, the step-by-step build from fewer coins to more.

The first paper proves the Courtade–Kumar conjecture. It also covers facts recorded with some randomness. Among facts that start with equal information, a single noisy coin keeps the mostSource 2. For biased facts that are not constant, it gives a strictly smaller limitSource 3. This holds unless the noise scrambles the coins completely. The second paper claims to prove the Hellinger conjecture for every bias and noise levelSource 4. Its proof uses computer arithmetic, but only for fixed inequalities that do not depend on the number of coinsSource 5.

These are not the only claimed proofs. Recent preprints announce proofs of the Courtade–Kumar conjecture by other routesSource 6. Their authors include Chen and coauthors, Ky and Tran, and Mahdavifar and Beirami. The first paper says Chen and coauthors' work also gives its main contraction theoremSource 7. What the first paper adds is its own route and a stronger bound that depends on the bias.

How sure is this? A computer proof checker called Lean has checked the first paper's main results. They are the Courtade–Kumar inequality with its equality case, the sharp contraction theorem and the bias-dependent bounds. The Hellinger paper is not covered by the Lean scope note. Its finite arithmetic comes with programs to rerun. No specialists have published a review of either paper yet.

What it doesn't show. This does not cover inputs that are biased or correlated; the input bits are always fair and independent.