Browse › Combinatorics › 192 Boolean functions violate the square-root degree bound by arbitrary factors
Unbounded Violations of the Square-Root Degree Bound
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
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\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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Lean scope notes for result 192: Boolean functions violate the square-root degree bound by arbitrary factors (lean/docs/192.md, release of 6 October 2026). The scope note reports formalization of arbitrary-factor violations of the signed singleton Fourier-coefficient bound and of the unboundedness of the corresponding absolute-coefficient ratio, and links the comparator statement
SquareRootDegree.lean. [family-level]
Possibly relevant literature (found by the agent, not checked)
- S. Iyer, A. Rao, V. Reis, T. Rothvoss, A. Yehudayoff, Tight bounds on the Fourier growth of bounded functions on the hypercube (arXiv:2107.06309, 2021). Bounds the ℓ1 norm of level-ℓ Fourier coefficients of degree-d functions with values in [-1,1]; at level one this concerns the quantity in the paper's surviving linear bound sum_i |f̂({i})| ≤ deg(f).
- U. Girish, A. Tal, K. Wu, Fourier Growth of Parity Decision Trees (arXiv:2103.11604, 2021). Bounds level-ℓ Fourier growth of depth-d parity decision trees; at level one this relates to the paper's contrast with Blais–Tan–Wan's square-root bound in parity decision-tree depth.
Digests and expositions
- Claude Opus 5.5 / Open Mathematics Courses, The square-root degree bound (Open Mathematics Courses, October 2026). Four lessons with proofs and exercises develop the manuscript's observation calculus, asymptotically normal scores, tagged reporting rule and average degree costs; the site states that independent review is incomplete. [AI-generated per source]
- Gradient Damage, Circulant Hadamard Conjecture, Cycle–Clique Ramsey Numbers and 7 More in Combinatorics (video, 2026-10-15). The chapter beginning at 1:23 introduces the Gopalan–Servedio square-root degree bound and the manuscript's claimed disproof through a Boolean-cube illustration.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 192
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Unbounded-Violations-of-the-Square-Root-Degree-Bound-September-26-2026,
author = {{OpenAI}},
title = {{Unbounded Violations of the Square-Root Degree Bound}},
howpublished = {OpenAI Math Release preprint
\href{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}{OAI:Unbounded-Violations-of-the-Square-Root-Degree-Bound-September-26-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/192.md. The Lean statements have not been checked by people against the paper's claims.
Family 192: 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.
This is the only paper in this family.