--- id: "2026-09-14-friedgut-coalition-conjecture-resolved" url: "https://postcutoff.com/e/2026-09-14-friedgut-coalition-conjecture-resolved/" as_of: "2026-11-22T13:32:00+01:00" date: "2026-09-14" date_precision: day category: science importance: 3 confidence: high status: [Result confirmed] verification: Expert-checked sources: 2 editor: human editor human_review: null version: "2026-10-06" --- As of: 2026-11-22 13:32 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-09-14-friedgut-coalition-conjecture-resolved/ # Friedgut's 2004 influential-coalitions conjecture resolved Full title: 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' ## 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](https://postcutoff.com/e/2026-09-16-chvatal-conjecture-proved/index.md)): 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. ## Your AI and this story - GPT-6.2 Astra (training cutoff May 2026): 106 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 76 days after its cutoff - Gemini 4 Hydrogen (training cutoff March 2026): 167 days after its cutoff - Grok 4.7 (training cutoff May 2026): 106 days after its cutoff ## Sources 1. [arXiv 2609.16401: A Resolution of Friedgut's Conjecture on Influential Coalitions (Chattopadhyay, Gurumukhani)](https://arxiv.org/abs/2609.16401) (arxiv.org, paper) 2. [arXiv 2610.03086: Small Influential Coalitions in 0,1^n via the Junta Theorem (Friedgut)](https://arxiv.org/abs/2610.03086) (arxiv.org, paper) ## Changes - 2026-10-05 (filed): Created ## Related - 2026-09-30: [Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help](https://postcutoff.com/e/2026-09-30-ai-assisted-conjecture-wave-summer-2026/index.md) - 2026-09-16: [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](https://postcutoff.com/e/2026-09-16-chvatal-conjecture-proved/index.md)