A
D
V
E
R
T
I
S
E
M
E
N
T
ADVERTISEMENT
The Courtade–Kumar and Hellinger conjectures
at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages
>>> Check out Coolmath's new Gaussian Moat Hopper <<<

LOADING...
0%
thinking... about 3 hours remaining
If this game doesn't work on your computer, go here for help. (Lean version available!)
expertly designed by an internal OpenAI model

Difficulty:🧠🧠🧠🧠🧠 Ages:13 - ∞
Skills:algorithms, speed Levels:2
Category:Theoretical computer science Lean version:YES! ✔
Rate this game! 4.3 out of 5 (8,015 votes)

>>> How to Play <<<
The Courtade–Kumar and Hellinger conjectures. Proves the Courtade–Kumar conjecture: among Boolean functions of independent uniform bits, a single coordinate retains the most mutual information after independent bit-flip noise. A stronger theorem treats randomized binary summaries at fixed initial information. The Hellinger conjecture is also proved for every Boolean output bias and noise correlation.

>>> Level Select <<<
released 2026-09-24  |  6 theorems · 12 lemmas · 20 proofs · 9,346 words  |  PLAY LEVEL 1 »  (pdf)
We prove sharp contraction of the information carried by a binary channel under independent symmetric noise on a uniform discrete cube. At fixed initial information, a noisy coordinate retains the most information. The Boolean specialization resolves the Courtade–Kumar conjecture and gives an output-entropy refinement. We also establish a stronger mean-dependent entropy-production bound. The proof combines an explicit three-point optimizer for the local joining problem, two entropy capacities, and a common-output thinning inequality, followed by dimension induction and integration along the noise semigroup.
released 2026-09-24  |  2 theorems · 14 lemmas · 20 proofs · 16,308 words  |  PLAY LEVEL 2 »  (pdf)
We prove the Hellinger conjecture for Boolean functions on the uniform discrete cube, with arbitrary output bias. For a Boolean function of mean m and every $\rho\in[-1,1]$, the loss $\sqrt{1-m^2}-\mathbb E\sqrt{1-(T_\rho f)^2}$ is at most $1-\sqrt{1-\rho^2}$, with equality for signed coordinates. The proof combines asymmetric dimension induction, a calibrated noise-semigroup energy estimate, and finite exact arithmetic certificates. The Hellinger inequality also yields the Courtade–Kumar information bound.

More Theoretical computer science Games!
The approximation threshold for metric $k$-medianExponential semidefinite complexity of perfect matchingThe asymptotic Gotsman–Linial conjectureA factor-two approximation for shortest common superstring
Exponential state costs for two-way automataFourier transforms below $n\log n$ HOT!Polynomial mixing of graph switches with prescribed degreesA counterexample to the quadratic sensitivity conjecture

Cool Links: openai/math   Lean   Mathlib   arXiv   the real Coolmath Games