
Courtade-Kumar conjecture explained: the most informative Boolean function problem
By Himanshu Sakre·
A 2013 question in information theory asks which yes-or-no function of noisy data says the most. A September 2026 preprint claims a computer-assisted proof, checked in Lean. Here is what the conjecture means.
The Courtade-Kumar conjecture, also called the most informative Boolean function conjecture, asks a simple-sounding question about noisy data. Take some random bits, push them through a noisy channel, and then ask what single yes-or-no summary of the original bits tells you the most about what came out the other end. For 13 years the proposed answer was unproven. In September 2026 a seven-author preprint claimed to prove it.
The problem in plain terms
Picture n fair coin flips, written as bits. Each bit is then sent through a channel that flips it with probability alpha, so a bit arrives wrong a fraction alpha of the time. That setup is called a binary symmetric channel. You see the noisy outputs. The original bits are hidden.
Now someone picks a Boolean function: a rule that turns the n hidden input bits into one output bit. Majority vote is one such rule. Parity is another. Copying the first bit and ignoring the rest is a third, usually called a dictator function. The question is how much the noisy outputs can tell you about the function's answer. Information theorists measure that with mutual information, in bits.
The 2013 paper, "Which Boolean Functions are Most Informative?" by Thomas Courtade and Gowtham Kumar, states the conjecture as I(b(X^n); Y^n) ≤ 1 − H(α), where H is the binary entropy function. In words: no Boolean function can carry more than 1 minus the binary entropy of the noise level. The paper was submitted to arXiv on February 11, 2013, revised on July 15, 2013 and presented at ISIT 2013 in Istanbul. It said plainly that the conjecture remained unproven, though the authors offered substantial supporting evidence.
Why dictator functions set the bar
The right-hand side of the bound is not a guess. A dictator function reaches it. If you just copy one input bit, the noisy copy you see tells you exactly 1 − H(α) bits about it. The 2026 preprint's abstract says the bound is attained by dictator functions. So the conjecture really says that the simplest rule is also the best one, and that cleverer functions such as majority cannot beat it.
A worked example makes the size concrete. At a 10 percent bit-flip rate, the binary entropy H(0.1) is about 0.469 bits, so a dictator function carries about 0.531 bits about the output. At a 50 percent flip rate the channel is pure noise, H(0.5) is 1, and the bound falls to zero. Those numbers are our own arithmetic from the published bound, not figures from either paper.
“The entire proof, including all numerical certificates, has been formally verified in Lean end-to-end”

Four terms, defined
- Boolean function: a rule that maps the input bits to a single yes-or-no answer.
- Binary symmetric channel: a noisy link that flips each bit independently with the same probability.
- Binary entropy, H(alpha): a measure of how uncertain one bit is when it is wrong with probability alpha. It is 0 for a certain bit and 1 for a fair coin.
- Mutual information: how many bits of uncertainty about one thing disappear once you see another.
Together they turn a loose question, how much can a noisy copy tell you, into a number you can bound.
What the 2026 preprint claims
The new paper, "A Proof of the Most Informative Boolean Function Conjecture," arXiv:2609.24931, was submitted on September 21, 2026 and revised on September 24. Its authors are Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair and David P. Woodruff. It is listed under computer science (data structures and algorithms), cross-listed to information theory, and is licensed CC BY 4.0.
The abstract calls the result a computer-assisted proof. The authors use a differential-equation method, which they describe as a limiting form of auxiliary-receiver techniques from network information theory. They state that "The entire proof, including all numerical certificates, has been formally verified in Lean end-to-end." The arXiv comments say the latest version added links to the Lean formalization, an expository note and a discussion of concurrent work.
Google Research later described the effort as a collaboration between multi-agent AI systems and human experts, and said the Lean formalization ran to 50 million lines. That figure is from Google's November 13, 2026 post, not from the arXiv page. Our news report on those claims is in our coverage of the Antigravity teamwork announcement.
What "computer-assisted" and "verified in Lean" mean
Computer-assisted means the proof relies on numerical computation that a human cannot check by hand. Those computations are packaged as certificates. Lean is a proof assistant that accepts a proof only if every step follows from its axioms, so a Lean check removes the worry that a certificate was miscalculated.
It does not remove every worry. Lean checks that the stated formal theorem follows. Someone still has to confirm the formal theorem is the Courtade-Kumar conjecture and not a subtly different one. Our explainer on what a Lean check does not prove covers that gap in detail.
What would settle it
Three things would move this from a credible preprint to an accepted result. First, a referee process or public endorsement from specialists in information theory, who are best placed to judge the differential-equation method. Second, independent audits of the Lean statement against the 2013 formulation. Third, reproduction of the numerical certificates by people outside the author team.
As of November 16, 2026 the arXiv page shows no journal publication. That is normal for a paper this new, and it is the right caution for any result announced through a corporate blog.
Our take
This is a real, named, checkable claim, which is more than most AI math headlines offer. The conjecture is clean, the bound is attained by the simplest function, and the proof strategy is published. We would call the result likely correct and still unrefereed. Check the arXiv page for version updates, and read the formal statement before treating a line count as evidence.
Frequently asked questions
What is the Courtade-Kumar conjecture?
It is a 2013 conjecture by Thomas Courtade and Gowtham Kumar. It says that for fair random bits sent through a binary symmetric channel, any Boolean function of the inputs carries at most 1 minus the binary entropy of the noise level about the noisy output.
Has the Courtade-Kumar conjecture been proven?
A preprint, arXiv:2609.24931, submitted on September 21, 2026, claims a computer-assisted proof verified in Lean. As of November 16, 2026 the arXiv page lists no journal publication or peer review, so it is a claimed proof, not an accepted one.
What is a dictator function in information theory?
A dictator function is a Boolean function that copies one input bit and ignores the rest. It reaches the conjectured bound of 1 minus the binary entropy of the noise level, which is why the conjecture says nothing can do better.
What does verified in Lean mean for a proof?
Lean is a proof assistant that accepts a proof only when every step follows from its axioms. It confirms the formal statement was proved, but humans still must check that the formal statement matches the original conjecture.
Did AI prove the Courtade-Kumar conjecture?
Google Research says multi-agent AI systems worked with human experts on the proof. The arXiv paper lists seven human authors and calls the proof computer-assisted. The AI role is described in Google's November 13, 2026 post, not detailed on the arXiv page.
Sources
What each one is, and whose it is.
- 1
Which Boolean Functions are Most Informative?, arXiv (February 11, 2013)
PaperIndependent of the vendorNot peer reviewed, preprint - 2
A Proof of the Most Informative Boolean Function Conjecture, arXiv (September 21, 2026)
PaperIndependent of the vendorNot peer reviewed, preprint - 3
Advancing science and engineering with Antigravity's teamwork feature, Google Research (November 13, 2026)
Vendor announcement