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.
released 2026-09-26 | 2 theorems · 8 lemmas · 10 proofs · 9,137 words |
PLAY LEVEL 1 »(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.