Boolean functions violate the square-root degree bound by arbitrary factors
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
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\})> C\sqrt{\deg(f)}. Thus its total signed correlation with individual input bits can exceed the proposed bound by an arbitrary factor.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
Unbounded Violations of the Square-Root Degree Bound
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 \displaystyle \sum_{i=1}^n \widehat f(\{i\})> C\sqrt{\deg(f)}. Here \widehat f(\{i\}) is the linear Fourier…
Full source 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 \displaystyle \sum_{i=1}^n \widehat f(\{i\})> 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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.