Boolean functions violate the square-root degree bound by arbitrary factors

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 \sum_i\widehat f(\{i\})\gt C\sqrt{\deg(f)}. Thus its total signed correlation with individual input bits can exceed the proposed bound by an arbitrary factor. (Lean)

Manuscript

Unbounded Violations of the Square-Root Degree Bound

September 26, 2026 · source · cite as \cite{OAI:Unbounded-Violations-of-the-Square-Root-Degree-Bound-September-26-2026}

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\to\{-1,1\} on a finite sign cube such that

\displaystyle \sum_{i=1}^n \widehat f(\{i\})\gt C\sqrt{\deg(f)}.

Here \widehat f(\{i\}) is the linear Fourier coefficient associated with the ith input, and \deg(f) is the degree of the real multilinear polynomial representing f.

Result 192 · Combinatorics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.