{"id":"openai-math/Unbounded-Violations-of-the-Square-Root-Degree-Bound","pdf":"https://github.com/openai/math/blob/main/preprints/Unbounded-Violations-of-the-Square-Root-Degree-Bound-September-26-2026/Unbounded-Violations-of-the-Square-Root-Degree-Bound-September-26-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/Unbounded-Violations-of-the-Square-Root-Degree-Bound-September-26-2026","tags":["boolean-functions","fourier-analysis","complexity-theory"],"score":0,"title":"Unbounded Violations of the Square-Root Degree Bound","domain":"Combinatorics","family":"192","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.CO","summary":"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 i th input, and $`\\deg(f)`$ is the degree of the real multilinear polynomial representing f .","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{},"formalized":false,"family_title":"Boolean functions violate the square-root degree bound by arbitrary factors"}