View source for The Courtade–Kumar conjecture

'''The Courtade–Kumar conjecture''', also called the most informative Boolean function conjecture, concerns ''n'' independent uniform bits ''X'' observed through independent binary symmetric channels with crossover probability ''p''; call the output ''Y''. It asserts that every Boolean function ''f'' satisfies ''I''(''f''(''X''); ''Y'') ≤ 1 − ''h''(''p'') bits, where ''h'' is the binary entropy, so that a single coordinate (a dictator function) is the most informative one-bit summary. Courtade and Kumar posed it in 2013. Two manuscripts dated 24 September 2026 in OpenAI's public mathematics collection ([https://github.com/openai/math github.com/openai/math]) claim proofs of it and of the stronger Hellinger conjecture. Several other groups posted proofs of the Courtade–Kumar conjecture in the same week. This page summarizes OpenAI's published claims, lists the other proofs with their public dates and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.

== Background ==
* The Hellinger conjecture, formulated by Anantharam, Bogdanov, Chakrabarti, Jayram and Nair in a 2017 manuscript, concerns a Boolean function ''f'' on {−1, 1}<sup>''n''</sup> with mean ''m''. For every ρ in [−1, 1] it asserts that √(1 − ''m''<sup>2</sup>) − E√(1 − (''T''<sub>ρ</sub>''f'')<sup>2</sup>) ≤ 1 − √(1 − ρ<sup>2</sup>), where ''T''<sub>ρ</sub> is the noise operator. As recalled in OpenAI's Hellinger manuscript and in Ky's paper listed below, it implies the Courtade–Kumar conjecture (Proposition 1 of Anantharam et al.).
* Partial results cited in OpenAI's manuscripts include high-noise bounds of Ordentlich, Shayevitz and Weinstein and of Samorodnitsky, the work of Javanmard and Woodruff ([https://arxiv.org/abs/2601.09679 arXiv:2601.09679]) and the differential-equation approach of Chen, Gohari and Nair.

== The original results ==
* '''Claim (soft-channel contraction).''' For every finite ''n'', every function ''u'' from {−1, 1}<sup>''n''</sup> to [−1, 1] (a randomized binary summary) and every ρ in [−1, 1], the information retained after noise is at most ψ(|ρ| ψ<sup>−1</sup>(''I''(''u''))). Here ψ(''r'') = log 2 − ''H''(''r''), and ''H''(''r'') is the entropy of a sign with mean ''r''. Soft coordinate functions attain equality (Theorem 1.1). For Boolean ''f'' with mean ''m'' the manuscript derives ''I''(''f''(''X''); ''Y'') ≤ ψ(|ρ| ''r''<sub>''m''</sub>) ≤ ψ(|ρ|), with ''r''<sub>''m''</sub> = ψ<sup>−1</sup>(''H''(''m'')). The right-hand bound is the Courtade–Kumar inequality with ρ = 1 − 2''p'' (Corollary 1.2). The manuscript also states a mean-dependent entropy-production bound. Source: the manuscript [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Sharp-binary-information-contraction-on-the-discrete-cube-September-24-2026 Sharp binary-information contraction on the discrete cube], dated 24 September 2026 (repository commit <code>1581d4c</code>).
* '''Claim (Hellinger conjecture with arbitrary output bias).''' For a Boolean function of mean ''m'' and every ρ in [−1, 1], the Hellinger loss above is at most 1 − √(1 − ρ<sup>2</sup>), with equality for signed coordinates. The proof combines asymmetric dimension induction, a noise-semigroup energy estimate and finite exact arithmetic certificates. Source: the manuscript [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/Hellinger-contraction-with-arbitrary-Boolean-output-bias-September-24-2026 Hellinger contraction with arbitrary Boolean output bias], dated 24 September 2026.
* '''Formalization, as described by the repository.''' The scope note [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/docs/119.md lean/docs/119.md] lists only the soft-channel manuscript. Its comparator statements are [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/ComparatorChallenges/CourtadeKumar.lean CourtadeKumar.lean] (the inequality and its attainment, for crossover probabilities from 0 to 1/2) and [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/ComparatorChallenges/SoftChannel204.lean SoftChannel204.lean] (soft-channel contraction and entropy production). The note does not list the Hellinger manuscript.
* '''Relation to concurrent work, as stated in the manuscripts.''' The soft-channel manuscript cites the proofs by Chen et al., Ky and Tran, Mahdavifar and Beirami, and Kramer and Saglam listed below. It states that the overlap with Chen et al. "extends beyond the Boolean conjecture": their Lemma 9.2 applies to arbitrary binary channels, and retaining the initial information when integrating their production bound gives the manuscript's Theorem 1.1 and Corollary 1.2. The Hellinger manuscript describes the Hellinger inequality as a distinct functional statement, from which the ordinary Courtade–Kumar bound follows.

== Other proofs of the conjecture ==
{| class="wikitable"
! Date !! Work !! Approach, as described in the cited sources !! Public status (checked 15 October 2026)
|-
| 2026-09-21 || Vu Khac Ky and Tuan Tran, [https://arxiv.org/abs/2609.24184 arXiv:2609.24184] (v1), Dictators are most informative; certificates and scripts in [https://github.com/vukhacky/courtade-kumar-conjecture vukhacky/courtade-kumar-conjecture] || An entropy-production and spectral framework with computer-assisted verification. || Preprint, one version.
|-
| 2026-09-21 || Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair and David P. Woodruff, [https://arxiv.org/abs/2609.24931 arXiv:2609.24931] (v1; v2 of 24 September), A proof of the most informative Boolean function conjecture; Lean code in [https://github.com/dpwoodru/general-courtade-kumar-lean dpwoodru/general-courtade-kumar-lean] || A computer-assisted Bellman inequality within the differential-equation method. || Preprint. The repository README describes an end-to-end Lean 4 proof (about 45,500 modules, mostly generated certificate data) whose final theorem depends only on Lean's three standard axioms. It reports a comparator run and acceptance by the con-leche external checker. Its formal statement was merged into Google DeepMind's Formal Conjectures repository on 15 October 2026 (follow-up table below).
|-
| 2026-09-22 || Hessam Mahdavifar and Ahmad Beirami, [https://arxiv.org/abs/2609.26444 arXiv:2609.26444] (v1; v2 of 28 September), The most informative bit and beyond || A proof of the conjecture, together with multibit extensions: counterexamples to the ''k''-bit extension for ''k'' ≥ 8 and a conjecture that it holds for 2 ≤ ''k'' ≤ 7. || Preprint. Its generative-AI disclosure states that AI systems generated the single-bit proof, including its detailed derivations, with the authors providing direction, feedback and final review. Version 2 states that the authors verified Kramer and Saglam's proof independently in Lean.
|-
| 2026-09-23 || Dimiter Kramer and Mert Saglam, [https://github.com/deepinfra/courtade-kumar deepinfra/courtade-kumar], On the most informative Boolean function under noise (PDF of 23 September; source files from 21 September) || Induction on the dimension, applied to a strengthened inequality that keeps the output mean μ: the information is at most ρ<sup>2</sup>(''h''(μ) − ν) + ν(1 − ''h''(''p'')) bits, where ν = 4μ(1 − μ). || A manuscript in a GitHub repository; OpenAI's soft-channel manuscript cites the commit of 23 September.
|-
| commits dated up to 8 September 2026 || Matthew Ho, [https://github.com/sunfishho/courtade-kumar-conjecture sunfishho/courtade-kumar-conjecture] || A Lean 4 formalization with completed numerical certificates. || The README reports a comparator statement check, an axiom whitelist check and a fresh kernel replay, and states that "the proof is in the process of being digested". The repository does not show when it became public. Version 2 of Chen et al. mentions that Ho and a collaborator shared an outline, an AI-generated document and Lean files with them privately after their posting.
|}

== Public follow-up work ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 15 October 2026)
|-
| 2026-10-07 || Vu Khac Ky, [https://arxiv.org/abs/2610.10618 arXiv:2610.10618] (v1), The Hellinger conjecture for antipodal Boolean functions || Parallel (special case) || Proves the Hellinger inequality for Boolean functions with a sign-reversing symmetry and extends the argument to arbitrary independent binary-input channels. It cites OpenAI's collection (entry 119) as an announcement of the inequality for arbitrary output bias. || Preprint.
|-
| 2026-10-15 || [https://github.com/google-deepmind/formal-conjectures/pull/6688 formal-conjectures pull request #6688] || Formal statement || Adds the Courtade–Kumar conjecture to Google DeepMind's Formal Conjectures repository, tagged as solved, with a formal-proof link to Chen et al.'s Lean repository. The description states that the definitions are definitionally equal to that repository's statement, so its final theorem implies the Formal Conjectures statement by unfolding. || Merged on 15 October 2026.
|}

== Notes ==
* Dates are those shown by arXiv, by the GitHub commit history or by the pull request. The lists cover sources found up to the date above; they make no priority or completeness claim.

[[Category:OpenAI results]]