Friedgut's 2004 influential-coalitions conjecture resolved (Chattopadhyay–Gurumukhani, ChatGPT Pro used extensively); Friedgut then has GPT-6 Astra simplify the proof
On Sept 14, 2026 Eshan Chattopadhyay and Mohit Gurumukhani (Cornell) posted a proof (arXiv 2609.16401) of Ehud Friedgut's 2004 conjecture: every monotone Boolean function on the continuous cube [0,1]^n has a coalition of O(n/√log n) coordinates that can force a fixed output with probability 1 − ε. It is the first sublinear bound independent of alphabet size for collective coin flipping. Their AI-use statement says they "used ChatGPT Pro extensively for exploring ideas, and proving several technical parts". On Oct 2 Friedgut posted a note (arXiv 2610.03086) with a simpler proof that he says ChatGPT-6 Astra wrote after two short prompts from him. He credits the breakthrough to Chattopadhyay and Gurumukhani.
Key facts
- arXiv 2609.16401 (cs.CC, Sept 14, 2026), 'A Resolution of Friedgut's Conjecture on Influential Coalitions', 15 pages; key tools: an encoding relating influence on product spaces to p-biased influence, and Hatami's pseudo-junta theorem (Annals 2012)
- Previously only the Boolean-cube case was known (Kahn–Kalai–Linial 1988, O(n/log n)); no sublinear alphabet-independent bound existed
- C–G AI use statement: 'The authors used ChatGPT Pro extensively for exploring ideas, and proving several technical parts. The authors take full responsibility for the correctness of all results in the paper.'
- arXiv 2610.03086 (Oct 2; revised Sept 30), Friedgut, 'Small Influential Coalitions in [0,1]^n via the Junta Theorem': gets O(n/(ε log n)) using Friedgut's junta theorem instead of Hatami's, plus a direct discretization from [0,1]^n to {0,1}^n
- Friedgut's account: he fed the C–G manuscript to ChatGPT-6 Astra with the prompt 'see whether it can be simplified by using Friedgut's junta theorem instead of Hatami's pseudo-junta theorem'; 'After a few minutes the bot supplied me with a simpler proof'; a second prompt produced the discretization shortcut. The proof section is ChatGPT's output, 'lightly edited'
- Friedgut: 'my mathematical contribution… was limited to my two suggestions to the bot… I did not apply any creativity to the project'; he had earlier failed to solve the conjecture with a weaker ChatGPT model; he calls the AI's perturbed-measure argument 'really a beautiful idea'
Science result
- Field
- computer-science / analysis of Boolean functions / collective coin flipping
- Problem
- Friedgut's conjecture on small influential coalitions for monotone functions on [0,1]^n (CPC 2004) (open since 2004)
- Result
- Coalitions of O(n/√log n) coordinates suffice to force either output with probability 1−ε (C–G); an AI-written simplification gives O(n/(ε log n)) via the junta theorem (Friedgut)
- AI system
- ChatGPT Pro, GPT-6 Astra
- Human role
- AI-assisted, human-led original proof (ChatGPT Pro used extensively for ideas and technical parts); the simplified proof was written by GPT-6 Astra from two prompts by the conjecture's author
- Verification
- Preprints; expert-checked by the conjecture's author (Friedgut); not formalized or refereed
- Status
- confirmed
- Why surprising
- The conjecture's own author says an AI produced a cleaner proof within minutes of being pointed at the right tool.
What happened
Friedgut had carried the conjecture for over two decades and had tried it with AI before, without success. Chattopadhyay and Gurumukhani settled it in a 15-page paper that leaned heavily on ChatGPT Pro. After reading their proof, Friedgut suspected Hatami's deep pseudo-junta theorem was more than the problem needed. He asked GPT-6 Astra to swap in his own weaker junta theorem, then to reuse the discretization from his 2004 paper. The result is a shorter proof that passes through a family of perturbed product measures, which he likens to Dinur–Safra's "Importance of Being Biased". He posted it at the Cornell authors' suggestion.
Why it matters
It follows the Chvátal pattern from the same weeks (2026-09-16-chvatal-conjecture-proved): a human-led proof with heavy model use is followed within days by an AI-written simplification, here prompted by the conjecture's author himself.
Changelog
- 2026-10-05: created (leads run; lead from Friedgut's note arXiv 2610.03086)
Related events
- Chvátal's 1972 conjecture proved (Chang–Liu–Liu, ChatGPT-assisted), then a GPT-6 Astra 'proof from The Book' and a Codex-built Lean formalization ★★★★
- Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
Sources (2)
- paperarXiv 2609.16401: A Resolution of Friedgut's Conjecture on Influential Coalitions (Chattopadhyay, Gurumukhani)
- paperarXiv 2610.03086: Small Influential Coalitions in [0,1]^n via the Junta Theorem (Friedgut)
id: 2026-09-14-friedgut-coalition-conjecture-resolved · updated 2026-10-05 · open in the interactive timeline