A long bit string must pass through a noisy channel. You want to retain as much recoverable information about the original string as possible. Intuition says: use complex rules to weave many bits of information together. In 2013, Thomas Courtade and Gowtham Kumar proposed a counterintuitive conjecture: don't weave — keep just one original bit, and that single bit carries the most information.
This is the Courtade-Kumar conjecture, sitting at the intersection of information theory, Boolean function analysis, and theoretical computer science. For over a decade, mathematicians worldwide proved only special cases. On September 21, 2026, two teams independently closed the problem — via completely different routes.
What the Conjecture Says
Formally: among all Boolean functions, the dictator — a function depending on only one coordinate — retains the most information about a uniformly random input under independent binary noise.
- Boolean function: a map from several bits to 0 or 1, e.g., the XOR of one column.
- Dictator: "look only at column k; ignore everything else."
- Independent binary noise: each bit flips randomly with its own probability, independently of the others.
- Vu Khac Ky, Tuan Tran, *Dictators are most informative*, arXiv:2609.24184, submitted 2026-09-21 06:56 UTC, 36 pages, cs.IT / math.CO / math.PR.
- The second team: Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, David P. Woodruff, posted the same day, with computer-assisted proof and Lean formalization elements.
- Both are arXiv preprints; peer review is incomplete.
- Full texts of both arXiv papers were not obtained; method details rely on authors' public statements and reporting, without added technical content.
- Quotes come from Ky's statement to FPT University and Mirrokni's public post on X.
The conjecture sounds almost anticlimactic — a roomful of researchers spent over a decade proving that "less is more," with an answer simple enough to state in one sentence. The difficulty lies in the word "most." There are on the order of 2^n Boolean functions; proving that no function whatsoever preserves information better than the dictator is beyond conventional methods, which cover only limited cases.
Two Completely Different Routes
Route 1: Vietnamese mathematicians Vu Khac Ky (lecturer, FPT University) and Tuan Tran (professor, University of Science and Technology of China, specializing in discrete probability and combinatorics). Their paper, *Dictators are most informative*, is 36 pages, posted to arXiv on September 21 as 2609.24184, categorized under information theory, combinatorics, and probability.
Route 2: A seven-member team including Google research VP Vahab Mirrokni, plus Chen Zijie, Amin Gohari, Adel Javanmard, Honghao Lin, Chandra Nair (UC, Irvine), and David Woodruff (CMU). Their paper exceeds 250 pages and presents a computer-assisted proof claiming to resolve the conjecture in full generality, with some analytical elements formalized in Lean.
Mirrokni described Courtade-Kumar on X as a long-standing core open problem at the interface of information theory and Boolean function analysis, and publicly saluted the Vietnamese team upon learning of their independent proof. The same-day posting was not a coincidence: Ky emailed Nair before release to say he and his collaborator had a result; Nair replied that his team had also just finished, and the two sides coordinated release timing after exchanging results.
Where It Stalled for Thirteen Years
Ky first heard of the conjecture a decade ago, during a postdoc at the Chinese University of Hong Kong, introduced by Nair. He worked on it for two years without success, and returned to it intermittently after joining FPT University in January 2019, each time blocked by known obstacles.
In 2025, while doing information-geometry research, he picked the problem up again and noticed structural connections to entropy, mutual information, and how information changes under noise. Around then he began collaborating with Tran — one strong in entropy and analysis, the other in discrete probability and combinatorics — and the two gradually expanded the range of cases they could handle.
Ky told FPT University that AI helped them rapidly test ideas and search for counterexamples, cutting off dead ends and focusing on promising directions. The hardest part, he said, was that the conjecture fits in a few lines, yet standard methods prove it only in limited cases. Several times they thought they were nearly done, only to find a gap and nearly start over. Asked for the single most important thing in the process, he named the capacity to keep going after repeated failures.
A notable detail in Ky's background: he was a core member of the Flyspeck project, which produced a computer-verified proof of the Kepler conjecture — a machine-verified version of a nearly 400-year-old problem.
Why the Conjecture Deserved the Attention
The conjecture's standing is visible in who it attracted: it was of simultaneous interest to information theory, Boolean function analysis, and theoretical computer science — rare in mathematics. Problems at intersections are often the ones neither side wants to own. It asks about the theoretical limits of coding and compression: how much information can a channel actually preserve? The answer bounds estimates in communication, storage, and data processing simultaneously.
This connects to that week's other news: on October 3, Meta published six mathematics papers involving Muse Spark, and other AI-assisted proof examples appeared the same month. Conjectures like Courtade-Kumar were once chipped away case by case by humans; now people ask whether machines can take on problems that are "structurally minimal but combinatorially enormous."
To be clear: in both proofs, AI's role was assisting idea-testing and counterexample search. Ky made clear that problem selection remained with himself and Tran, and Tran's contribution was a complementary methodology. Reading this as "AI solved an information theory problem" would be wrong.
What Coexisting Proofs Mean
Seeing two different methods solve the same problem on the same day is usually good news rather than duplicated effort.
| Dimension | Route 1 | Route 2 | |---|---|---| | Authors | Ky and Tran | Seven-member team incl. Mirrokni | | Length | 36 pages | 250+ pages | | Method | Analytical proof | Computer-assisted proof | | Formalization | Not mentioned | Partial elements formalized in Lean | | Common point | Both posted to arXiv on 2026-09-21 | Same |
Two independent technical paths allow mutual checking. The size difference itself shows how deeply each route levered the same structure: the Lean formalization plus computer-assisted verification route costs far more, but its output is harder to wave through with "close enough." A common predicament in mathematics is repeated challenge of a single argument's details; two entirely different routes arriving at the same answer lowers that challenge's cost.
Limitations remain: both are arXiv preprints without completed peer review. Ky, in his statement to FPT University, left room — both methods have strengths and both still need the community's assessment. Mirrokni claimed the conjecture was resolved "in full generality"; Ky said "complete proof." The two phrasings largely agree, but neither equals peer-review confirmation.
Closing on a Question
A decade-plus conjecture was closed by a 36-page paper and a 250-page paper appearing the same day — a combination more memorable than either result alone. The next thing to watch is how the preprints fare in peer review. If both pass, information theory and Boolean function analysis textbooks gain a double-proof entry; if one route is challenged on details, the other exists as insurance.
There is also a harder question: the conjecture now belongs to information theory, which it did not thirteen years ago. That the same tools occurred to two teams simultaneously suggests the problem's mathematical skeleton had become clear enough to be attacked in parallel. Such "parallelizable" math problems will likely only multiply.
---