Courtade Kumar Conjecture Solved? Two AI-Assisted Proofs End a 13-Year Wait

A one-bit summary can combine thousands of inputs, compute parity, take a threshold, or apply some elaborate Boolean rule. The Courtade Kumar conjecture says that for preserving information about a noisy copy of the input, this cleverness buys you nothing. The best one-bit summary is simply one original bit.

Mathematically, let Xbe uniform on {-ⓜ,11}^n, let Ybe formed by independently flipping every coordinate with probability p, and let g:{-ⓜ,11}^n→{0ⓜ,1}. The claim is
I(gⓜ;(X)Y)≤1-H_2 (p),
with equality attained by a dictator function, essentially a rule that outputs one coordinate and ignores the rest. That is exactly the theorem stated in a new 251-page Google, CUHK, USC and CMU manuscript.

So, is the Courtade Kumar conjecture solved? As of September 2026, two independent groups report full proofs, using substantially different mathematical routes. That is a major change from earlier this year, when the main conjecture was still explicitly open. The important caveat is timing: both manuscripts are fresh arXiv preprints, not yet the end of community scrutiny.

1. Courtade Kumar Conjecture Solved? The Key Facts

The strongest reason to take the new result seriously is not AI branding. It is mathematical redundancy. One team proves the theorem through a differential-equation and Bellman-function program. Vu Khac Ky and Tuan Tran reach the same destination through an entropy-production and spectral framework. The first paper explicitly describes the second approach as “substantially different” and says the groups coordinated simultaneous posting.

That last row matters. “Solved” is reasonable shorthand for the present research status, but “universally verified and settled” would be premature days after release.

2. What Is the Most Informative Boolean Function Conjecture?

The Most Informative Boolean Function conjecture is an extremal question about compression under noise. You start with a random n-bit vector X. You are allowed to compress it to one bit, g(X). Separately, another observer receives Y, a corrupted version of all ninput bits. Which one-bit summary remains most informative about what that observer sees?

The question is deceptively simple: can a sophisticated function of all the coordinates beat the information retained by just copying one coordinate? Courtade and Kumar conjectured that the answer is no, in every dimension and at every noise level. The new paper states the result in exactly that dimension-independent form.

2.1 The Boolean Function Mutual Information Problem

Mutual information is the right quantity because this is not asking whether g(X)predicts one particular bit of Y. It measures statistical dependence between the one-bit output and the entire noisy vector.

That distinction explains why the conjecture is surprising. A Boolean function can inspect all ncoordinates before choosing its single-bit answer. Intuition might suggest that a well-designed global summary should average away some noise. The theorem says otherwise.

3. Why a Dictator Function Is Supposed to Win

Take four input bits and define
g(x_1ⓜ,x_2ⓜ,x_3ⓜ,x_4 )=x_2.
That is a dictator function. The name is colorful but literal: one coordinate dictates the output. The other three get no vote.

For the {-ⓜ,11}encoding used in the first paper, the corresponding {0ⓜ,1}-valued version is g(x)=(1+x_2 )/2. Its mutual information with Yis exactly 1-H_2 (p). The conjecture says no parity rule, majority rule, threshold, lookup table, or other Boolean compression can do better.

There is a nice sting in that statement. The optimal compressor appears almost embarrassingly lazy. It ignores n-1inputs, yet no complicated Boolean logic extracts a more noise-resistant one-bit summary.

4. Why the Problem Stayed Open for 13 Years

The conjecture attracted tools from information theory, discrete probability, Fourier analysis and isoperimetry on the Boolean cube. High-noise regimes were proved, and balanced functions became much better understood. Related inequalities were established in special settings. What remained missing was one dimension-independent result for arbitrary Boolean functions at every noise level. The first new proof summarizes that history directly.

The chronology makes September’s jump easier to appreciate. A January 2026 paper by Javanmard and Woodruff was still titled Progress on the Courtade-Kumar Conjecture. It resolved a coordinate-wise information question for biased functions and sharpened the high-noise analysis, while explicitly stating that the main conjecture remained open.

Google’s February Gemini work also shouldn’t be retroactively promoted into a full solution. The researchers described two AI contributions: extending a related theorem to unbalanced functions and improving high-noise entropy bounds, plus structural progress on an unsymmetrized version of the problem. Those were meaningful advances, but still partial ones.

5. What Changed in September 2026? Two Independent Proofs

The first manuscript is by Chen, Gohari, Javanmard, Lin, Mirrokni, Nair and Woodruff. Its abstract says plainly, “We give a computer-assisted proof,” and the theorem covers arbitrary Boolean functions, not just balanced ones.

The second manuscript, Dictators Are Most Informative, is by Vu Khac Ky and Tuan Tran. Its abstract likewise says it proves that a dictator retains the most information among all Boolean functions under independent binary noise.

This matters because the two groups did not merely rerun the same argument. The first extends a differential-equation program developed in earlier CUHK work. Ky and Tran instead build an entropy-production and spectral argument. Two proofs can still share background lemmas, of course, but substantially different proof architectures reduce the chance that one fragile technical idea is carrying the entire conclusion.

6. How the First Courtade Kumar Proof Works

The machinery fills 251 pages, but the proof’s high-level logic is fairly clean.

6.1 Step 1: Turn Information Into Entropy

Mutual information can be written as output entropy minus conditional entropy. The authors therefore turn the desired information upper bound into a lower bound on the uncertainty remaining about g(X)after observing Y. If that uncertainty never falls below the dictator benchmark, the conjecture follows.

6.2 Step 2: Follow Entropy as More Noise Is Added

The authors then let noise increase continuously through the Boolean noise semigroup. Rather than compare two endpoints only, they study the rate at which conditional entropy changes.

Differentiating along that noise flow turns entropy production into an average of costs on edges of the Boolean cube. In the paper’s language, the global information problem becomes an edge-energy problem.

A high-dimensional information inequality has now become a local energy problem that can be lifted back to every dimension.

6.3 Step 3: Reduce the Giant Problem to a Bellman Inequality

The next device is a Bellman inequality. The induction keeps only a small collection of statistics, including means and average entropies, rather than tracking an arbitrary Boolean function point by point.

Earlier work proposed a candidate ϕthat could handle the balanced case. The new paper proves that Bellman inequality, then introduces a hybrid candidate
B(mⓜ,e)=max⁡{ϕⓜ,(mⓜ,e)ψ(mⓜ,e) },
where ψaccounts for the entropy deficit caused by bias. That hybrid is what lets the argument move from balanced functions to full generality. The authors describe proving the balanced candidate and introducing the new hybrid candidate as the paper’s two main contributions.

6.4 Step 4: Certify the Remaining Regions

Some inequalities survive after the analytic reductions. This is where the computer-assisted part enters.

The proof partitions compact parameter regions into rational boxes. On every terminal box, outward-rounded interval arithmetic certifies a sufficient inequality across the entire feasible region, or proves that the box contains no feasible point. It is explicitly not a check at a handful of sampled values.

This is not simulation. A numerical experiment samples points. A rigorous interval certificate encloses every value in a box and proves the required sign throughout. The paper also supplies verification and reproduction records.

7. Where Gemini and Stellar Colosseum Actually Entered the Proof

Calling this a Gemini math proof is catchy and incomplete. The paper describes something closer to a research loop in which human insight, model exploration, counterexample hunting and rigorous numerical checks repeatedly changed one another’s direction.

The CUHK team already had a framework reducing the problem to finite-dimensional optimization. On Google’s side, Gemini was used inside Stellar Colosseum, a many-agent system built for long-horizon mathematical research. In that setting, the model found counterexamples near the boundary of a four-dimensional parameter domain. Those counterexamples did not disprove the Courtade Kumar conjecture. They broke an overgeneralized intermediate statement, which told the researchers their planned lower bounds were too weak.

That failure was productive. CUHK researchers developed new lower bounds and supplied the Bellman structure for the full unbalanced case, reducing the target to a 14-variable optimization problem. The paper then says AI led the partitioning of the space into regions and developed theoretical ideas plus interval-arithmetic calculations. It goes unusually far in its attribution, stating that the “overwhelming majority” of the paper’s novel ideas and results were generated by AI, while also stressing crucial human insight, feedback and at least one principal lower bound.

The workflow matters more than the slogan. Humans supplied structure and corrected the target. AI explored candidate inequalities and regimes, found counterexamples and pushed regional arguments. Humans steered and checked the work. The authors also report contributions from collaborators using Anthropic and OpenAI models.

Stellar Colosseum itself is designed around this kind of long-horizon process. Its paper describes parallel strategy generation, targeted falsification, decomposition into interdependent proof tasks and routing verifier feedback back to the relevant section, rather than treating one giant prompt as a research method.

8. The Second Proof Took a Different Route and Used ChatGPT

Ky and Tran’s proof is interesting precisely because it is not a Gemini-versus-ChatGPT rematch.

Their paper develops an entropy-production and spectral framework, using tools including log-Sobolev contraction, Harris association, martingale entropy methods and Fourier analysis. The goal is still to compare every Boolean function with a dictator, but the route through the landscape is different from the Bellman program.

The authors also include a direct AI disclosure: they say they formulated the approach and used ChatGPT to help develop proofs, prepare verification code and revise the exposition, while taking responsibility for the paper’s content. Their argument includes its own computer-assisted checks in part of the parameter range.

The striking fact is therefore not which chatbot gets a trophy. Two independent mathematical programs reached the same theorem while both teams integrated modern AI into serious proof development. That is a much more useful signal about the changing research workflow.

9. Is the Courtade Kumar Conjecture Really Solved?

At the level of current mathematical claims, yes: there are now two independent preprints asserting full proofs of the theorem in generality. At the level of long-term mathematical consensus, the papers are only days old.

That distinction should not be treated as a loophole. arXiv is a distribution system, not peer review. Experts still need to inspect the analytic reductions, equality cases, dependencies and computer-assisted certificates. The first paper helps by making its computational role unusually explicit and by providing certificate and reproducibility records.

It is also important not to overstate formal verification. The 251-page manuscript documents analytic arguments plus rigorous interval-arithmetic certification for specified numerical steps. It should not be described as a fully Lean-formalized proof unless a complete formalization is separately released and checked.

Two different approaches strengthen the case, but they do not make scrutiny optional.

10. Why This Matters Beyond One Conjecture

For information theory, the theorem gives a sharp answer to a basic compression question: if a uniformly random binary vector will later be viewed through independent symmetric noise, no one-bit Boolean summary preserves more mutual information than simply retaining one coordinate.

For Boolean-function analysis, it closes an extremal problem linking entropy, Fourier structure, noise stability and hypercube geometry. The optimizer’s simplicity is the punchline: not an elaborate global statistic, just a dictator.

The AI angle matters because this work spans failed conjectures, counterexamples, reformulation, case decomposition, code and verification. The interesting unit is not “model outputs proof.” It is a research process where models explore at scale while humans supply structure and decide what counts as evidence.

11. What to Watch Next

The next phase is less glamorous and more important: independent checking, attempted simplification and replication of the computational certificates. If both proof architectures survive scrutiny, mathematicians can then ask a better question than “Did AI solve it?”

They can ask which parts of the Courtade Kumar proof reveal reusable ideas. The hybrid Bellman construction may matter beyond this single inequality. The entropy-production and spectral route may offer its own general tools. And the human-AI workflows may become templates for other long proofs where the bottleneck is not one brilliant lemma, but navigating hundreds of interacting technical cases.

For Binary Verse AI, that is the story worth following. We track the primary papers, the verification trail and what the models actually contributed, without turning every assisted calculation into an AGI headline. If the Courtade Kumar conjecture holds up under review, its legacy may be twofold: a 13-year information-theory problem finally resolved, and a much clearer picture of what AI-assisted mathematical research looks like when the work gets genuinely hard.