Combinatorics·OpenAI Math·Result 192·Lean formalisation listed
Boolean functions violate the square-root degree bound by arbitrary factors
One of the 372 results in OpenAI's public mathematics catalogue, filed under combinatorics: 1 preprint, the latest dated 26 September 2026. This page quotes OpenAI's own summary of the claim, links the paper and abstract, and embeds the animation.
In one line: OpenAI reports a proof of Boolean functions violate the square-root degree bound by arbitrary factors (combinatorics) in a preprint dated 26 September 2026. It has not been peer reviewed. The channel's animation, Every OpenAI Math Result, Part 2 of 4: PCP for PPAD, Birkhoff Conjecture and 82 More, is on YouTube.
Chapter 30 of 84 in Every OpenAI Math Result, Part 2 of 4: PCP for PPAD, Birkhoff Conjecture and 82 More · starts at 10:01 · watch from there on YouTube →
What OpenAI claims
Disproves the proposed square-root bound relating a Boolean function's linear Fourier coefficients to its polynomial degree. For every C > 0, there is a sign-valued Boolean function f with ∑if̂({i}) > C√(deg(f)). Thus its total signed correlation with individual input bits can exceed the proposed bound by an arbitrary factor. (Lean)
Paper
Unbounded Violations of the Square-Root Degree Bound
OpenAI's abstract We disprove the Gopalan–Servedio square-root conjecture, even up to an arbitrary constant factor. For every real C > 0, there is a nonconstant Boolean function f:{-1,1}n → {-1,1} on a finite sign cube such that
Status
Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.
Quick answers
- Is it proven?
- Not independently yet. OpenAI posted a preprint on 26 September 2026; it has not been peer reviewed, so treat the result as OpenAI's claim until other mathematicians have checked it.
- What exactly does OpenAI claim?
- Disproves the proposed square-root bound relating a Boolean function's linear Fourier coefficients to its polynomial degree. For every C > 0, there is a sign-valued Boolean function f with ∑if̂({i}) > C√(deg(f)). Thus its total signed correlation with individual input bits can exceed the proposed bound by an arbitrary factor. (Lean)
- Where is the proof?
- In the paper, Unbounded Violations of the Square-Root Degree Bound (PDF).
- Is there a video?
- Yes, on YouTube (29:10, chapter 30).
Also in
- Chapter 5 of 9 in Circulant Hadamard Conjecture, Cycle–Clique Ramsey Numbers and 7 More in Combinatorics · starts at 1:23 · watch from there on YouTube →
The video
Every OpenAI Math Result, Part 2 of 4: PCP for PPAD, Birkhoff Conjecture and 82 More · Compilation · 29:10 · chapter 30 from 10:01 · description, sources and chapters →
Related results in Combinatorics
- 155A counterexample to periodic tiling in dimension threeVideoLean
- 156Borsuk's conjecture fails in dimension nineVideoLean
- 157Graph coloring, clique minors, and Colin de Verdière invariantsVideoLean
- 158The Euclidean plane cannot be colored with five colorsVideoLean
- 159Erdős’s reciprocal-sum conjecture and quasipolynomial Szemerédi boundsVideoLean
- 160Superexponential van der Waerden numbersVideoLean
