Courtade–Kumar conjecture
For every integer , every Boolean function , and every noise parameter , let be uniformly distributed on , let be independent random variables with and , independently of , and define . Then , where denotes mutual information and . Equality is attained by a dictator function for some .
References
- Dictators are most informative — arXiv — Vu Khac Ky, Tuan Tran
Source: arXiv
Progress summary
An unrefereed September 2026 preprint claims to settle the conjecture, but the proof has not yet been independently confirmed.
The Courtade–Kumar conjecture asserts that dictators maximize noisy information among Boolean functions on the discrete cube. Courtade and Kumar posed it in 2013; the newly announced work claims a proof in full generality.
Known results
- Verified computationally in dimensions (2015 source describing the state of the problem).
- Partial Fourier-analytic and stability results (2021).
- Dictators proved locally optimal; computer-assisted proof of the balanced case for (2024).
September 2026 claimed proof
On September 22, 2026, Vahab Mirrokni announced a claimed full proof; another announcement attributes a parallel approach to Sol/Astra. The cited arXiv preprint is unrefereed, and the retrieved evidence does not independently verify the proof.
Current status (as of September 2026): a full proof is claimed in new preprints, but the conjecture remains unverified; the earlier partial results are established.
Solutions 1
Claimed by OpenAI. For every Boolean function on the uniform n-dimensional cube and every symmetric-noise correlation rho in [0,1], the manuscript claims mutual information in bits at most 1-h2((1-rho)/2), with equality for signed coordinates. It also claims a stronger bound using the actual output entropy and sharp soft-channel contraction. This includes biased Boolean outputs and addresses the page’s Courtade–Kumar inequality.See full solution
GitHub repository: https://github.com/openai/math
- OpenAI-119-01-Sharp-binary-information-contraction-on-the-discrete-cube.pdfOpen