← All papers
First page of A Proof of the Most Informative Boolean Function Conjecture

A Proof of the Most Informative Boolean Function Conjecture

Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, David P. Woodruff

cs.DS Sep 21, 2026 · v2 cs.IT
The full proof of the Courtade–Kumar most informative Boolean function conjecture, including all numerical certificates, was formally verified end-to-end in Lean.
Let $X$ be uniform on $\{-1,1\}^n$, let $Y$ be obtained by passing its coordinates independently through a binary symmetric channel with crossover probability $p$, and let $g:\{-1,1\}^n\to\{0,1\}$ be a Boolean function. We give a computer-assisted proof of the Courtade–Kumar conjecture $I(g(X);Y)\le1-H_2(p)$, where $H_2$ is binary entropy, with equality attained by dictator functions. The present work builds on the differential-equation method, itself a limiting form of the auxiliary-receiver approach in network information theory using a continuum of degraded receivers. The proof proceeds from a local inequality to a dimension-independent bound on entropy production. Differentiation along the Boolean noise semigroup expresses entropy production as an average of edge costs. The key estimate is therefore an unrestricted Bellman inequality with two mean constraints and two entropy constraints, allowing arbitrary couplings of the edge variables. This paper and its supplement provide the proofs and computational verification records. The document is lengthy because it is designed to be entirely self-contained, deriving all proofs from first principles and reproducing the proofs of cited results. We also give a self-contained expository note explaining the reduction to a low-dimensional inequality and the ideas behind the key lower bounds. The entire proof, including all numerical certificates, has been formally verified in Lean end-to-end, and is available online.

The Courtade–Kumar conjecture asks whether, for X uniform on the hypercube and Y its output through a binary symmetric channel, every Boolean function g satisfies I(g(X);Y) ≤ 1−H2(p), with equality for dictator functions. It had only been verified numerically up to dimension seven.

The proof uses a differential-equation method, a limiting form of the auxiliary-receiver approach, reducing a dimension-independent entropy-production bound to a local four-moment inequality. Differentiation along the Boolean noise semigroup expresses entropy production as an average of edge costs, giving an unrestricted Bellman inequality with two mean and two entropy constraints. A static induction bounds total edge energy and a scalar comparison yields the conditional entropy bound. The entire argument, including numerical certificates, is formally verified in Lean.

The conjecture is proved in full generality: every Boolean function satisfies I(g(X);Y) ≤ 1−H2(p), with equality attained by dictator functions and their complements. The complete proof and all numerical certificates were formally verified in Lean end-to-end.