Optimal bound for the polynomial Littlewood–Offord problem, 'discovered autonomously by GPT-6 Pro' (exposition by Grebennikov)
On Oct 6, 2026 Alexandr Grebennikov posted arXiv 2610.08708, an exposition of a proof he says "was discovered autonomously by GPT-6 Pro". It shows that a degree-d multilinear polynomial with r disjoint top-degree monomials vanishes on random ±1 inputs with probability O_d(r^{-1/2}). This is optimal, removes the polylog factor in the Meka–Nguyen–Vu bound, and resolves a conjecture attributed to H. Nguyen and Vu. Its key lemma bounds the total influence of bounded-degree rational functions, resolving a conjecture of Kothari, Kovacs-Deak, Wang and Yang. The ChatGPT log is public.
Key facts
- Paper: 'Optimal bound for the polynomial Littlewood–Offord problem', Alexandr Grebennikov, arXiv 2610.08708 (math.CO), 6 Oct 2026, 8 pages
- Result: P[F(ξ₁,…,ξₙ) = 0] = O_d(r^{-1/2}) for Rademacher ξᵢ, where F is degree-d multilinear with r degree-d monomials on disjoint variable sets; previously (log r)^{O_d(1)} r^{-1/2} (Meka, O. Nguyen, Vu); known before only for d = 1 (Erdős), d = 2 (Kwan–Sauermann) and bounded Chow rank (Grebennikov–Kwan)
- AI statement (quote): 'The proof was discovered autonomously by GPT-6 Pro (the chat logs can be found here), and the author does not claim any credit for the proof ideas. The argument was subsequently verified, digested, and rewritten from scratch by the author.'
- Chat log: chatgpt.com/share/6ab4f17d-7a3c-83eb-a4e6-a99920bd9384 (linked from the PDF)
- A footnote notes that a similar linear-algebra statement appears implicitly in the AI-assisted Chvátal-conjecture proof (Chang, H. Liu, M. Liu) and its follow-ups
- Not part of OpenAI's 6 Oct github.com/openai/math release
Science result
- Field
- mathematics / probabilistic combinatorics / anticoncentration / analysis of Boolean functions
- Problem
- Polynomial Littlewood–Offord problem (Nguyen–Vu conjecture); total influence of bounded-degree rational functions (Kothari–Kovacs-Deak–Wang–Yang conjecture)
- Result
- Optimal anticoncentration bound O_d(r^{-1/2}) for multilinear polynomials of fixed degree, and a total-influence estimate for bounded-degree rational functions.
- AI system
- GPT-6 Pro (ChatGPT)
- Human role
- Autonomous discovery by GPT-6 Pro per the author; the human verified it and rewrote the argument from scratch
- Verification
- Unrefereed preprint by a specialist in the area; public chat log
- Status
- pending
What happened
The Littlewood–Offord problem asks how likely a random ±1 combination is to hit a fixed value. Erdős settled the linear case, and the polynomial version has been studied since Costello, Tao and Vu's work on random symmetric matrices. Hoi Nguyen and Van Vu conjectured that a degree-d multilinear polynomial with many nonzero top-degree coefficients vanishes with probability O(m^{-1/2}). The best general bound, by Meka, Oanh Nguyen and Vu, was off by a polylogarithmic factor.
On 6 October 2026 Alexandr Grebennikov, who had earlier worked on the bounded-Chow-rank case with Matthew Kwan, posted an eight-page exposition of an argument that gives the optimal O_d(r^{-1/2}) bound. The key step is an estimate for the total influence of functions p/q with p and q of bounded degree, which also resolves a recent conjecture of Kothari, Kovacs-Deak, Wang and Yang. The author states that the proof "was discovered autonomously by GPT-6 Pro … and the author does not claim any credit for the proof ideas". He then verified it and rewrote it from scratch, and he links the full ChatGPT conversation.
Why it matters
It is another case where a consumer-tier model (ChatGPT's GPT-6 Pro) is credited with the whole idea behind an optimal bound in a well-studied area, with a public transcript. The same day, OpenAI's internal-model release dominated attention.
Changelog
- 2026-10-07: created (sweep 2026-10-07, arXiv AI-disclosure section; PDF and its chat-log link read)
Related events
- Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help (July–September catalogue) ★★★★
- 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 ★★★★
- OpenAI adds a $500/month Pro 500 plan and the Ultrafast speed tier, and halves the $200 Pro allowance ★★★
Sources (2)
- paperarXiv 2610.08708: Optimal bound for the polynomial Littlewood–Offord problem
- discussionChatGPT shared conversation (GPT-6 Pro chat log)
id: 2026-10-06-polynomial-littlewood-offord-gpt-6-pro · updated 2026-10-07 · open in the interactive timeline