Family 192CombinatoricsNo LeanNot yet digested

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.

Manuscripts in this family · 1

Unbounded Violations of the Square-Root Degree Bound

Sep 26, 2026·Unbounded-Violations-of-the-Square-Root-Degree-Bound-September-26-2026.pdf

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.

Full abstract

PDF on GitHub LaTeX source