VibeMathedMath problems solved with AI
Sign in

The Gopalan-Servedio conjecture: is ∑if^({i})=O(deg⁡f)\sum_i\widehat f(\{i\})=O(\sqrt{\deg f}) for Boolean functions?

For f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} write f^(S)=E[f(X)∏i∈SXi]\widehat f(S)=\mathbb E[f(X)\prod_{i\in S}X_i] with XX uniform, and let deg⁡f\deg f be the degree of its real multilinear representation. Cauchy-Schwarz gives ∑if^({i})=E[f(X)∑iXi]≤n\sum_i\widehat f(\{i\})=\mathbb E[f(X)\sum_iX_i]\le\sqrt n, attained up to constants by majority, while total influence gives ∑i∣f^({i})∣≤deg⁡f\sum_i|\widehat f(\{i\})|\le\deg f. Gopalan and Servedio conjectured, around 2009, that n\sqrt n can be replaced by deg⁡f\sqrt{\deg f}; the conjecture is recorded in O'Donnell's list of open problems in analysis of Boolean functions and as Conjecture 3.17 of Filmus, Hatami, Keller and Lifshitz. A sharper majority-benchmark version was refuted at degree 4 by Kudin and Pasalic, which does not decide the square-root form. Is there an absolute constant CC with ∑if^({i})≤Cdeg⁡f\sum_i\widehat f(\{i\})\le C\sqrt{\deg f} for every Boolean function ff?

Result
Disproved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Analysis of Boolean functions
Posed by
Parikshit Gopalan and Rocco Servedio (c. 2009), recorded in O'Donnell's Open Problems in Analysis of Boolean Functions (2012, p. 9)
Year posed
2009
Years open
17y
Solved
2026-09-26
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
14 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1: for every C>0C>0 there is a nonconstant f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} with ∑if^({i})>Cdeg⁡f\sum_i\widehat f(\{i\})>C\sqrt{\deg f}; equivalently ∑i∣f^({i})∣/deg⁡f\sum_i|\widehat f(\{i\})|/\sqrt{\deg f} is unbounded over Boolean functions of positive degree, so no constant multiple of the conjectured bound holds. The dimension and copy counts in the construction are finite but not usefully bounded, so no growth rate of the violation in terms of degree is given. The true order between deg⁡f\sqrt{\deg f} and the linear bound deg⁡f\deg f is left open.

What the AI did

The release README says all results in the release were produced by an unreleased internal OpenAI model with one fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This family is not among the README's exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region whose write-up was human-edited). The manuscripts are authored 'OpenAI' and name no human author. The release also formalizes the disproof in Lean.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1 and the introduction were read against the conjecture as O'Donnell's list states it. Lean: lean/docs/192.md links ComparatorChallenges/SquareRootDegree (theorem OAI.SquareRootDegree.main, solution module OAI.Combinatorics.BooleanFunctions.Main, file exists at the pinned commit), not in formalization.yaml. The statement was read: for every C>0C>0 there is a nonconstant ±1\pm1-valued function on a finite sign cube with Cdeg⁡fC\sqrt{\deg f} below the sum of its singleton Fourier coefficients, where degree is the real Fourier degree, and the ratio of the absolute singleton sum to deg⁡f\sqrt{\deg f} is unbounded. That is the headline. Not rebuilt here.

Sources

Changelog1 change

Discussion