Boolean functions violate the square-root degree bound by arbitrary factors

Boolean functions can beat the proposed square-root-of-degree bound on their linear correlations by any factor.

1 paper September 26, 2026 Explained by AI

A Boolean function turns n inputs of +1 or −1 into one output of +1 or −1. Gopalan and Servedio conjectured that its total agreement with single inputs is at most a constant times the square root of its degree. This paper proves that false. For any constant, some function exceeds the proposed bound by that factor.

First step

—

Significance

Solid

It refutes a known conjecture in the analysis of Boolean functions by an unbounded factor.

Trust

Formal proof listed

Field

Combinatorics

1 paper

The explanation

Take three yes-or-no votes, written as +1 or −1. Let f be the majority vote: it outputs whichever sign has at least two votes. How much does f agree with each single voter? On average over all 8 vote patterns, f times voter 1 equals 1/2. The same holds for voters 2 and 3. So the three agreements add up to 3/2.

A Boolean function here takes n inputs, each +1 or −1, and outputs +1 or −1. The agreement with voter i is called the i-th linear Fourier coefficient. Every such function can be written as a polynomial in its inputs. Its degree is the largest number of inputs multiplied together in any term. Majority on three votes has degree 3, because it equals (x₁ + x₂ + x₃)/2 − x₁x₂x₃/2.

A simple argument bounds the sum of the linear coefficients by √nSource 1. Gopalan and Servedio conjectured that √n could be replaced by the square root of the degreeSource 2. The conjecture is attributed to them around 2009Source 3. For majority on three votes, the sum is 1.5 and √3 is about 1.73. So that example fits. A stronger guess compared every function with majority itselfSource 4. Kudin and Pašalić refuted that stronger guess at degree 4Source 5. The square-root version stayed open.

This paper proves the square-root version false, and badly soSource 6. For any number C, however large, it finds a Boolean function whose linear sum exceeds C times the square root of its degree. No fixed multiple of the proposed bound can hold. A weaker bound does survive: the sum is never more than the degree itselfSource 7. So the truth lies somewhere between the square root and the degree.

The difficulty is to get large agreement while keeping the degree low. The paper first builds a function that reports partial information about many independent scores. Each part of its output is a polynomial of small degree. Yet together these parts keep more information about the total than their degree would suggest. The saving comes from terms cancelling, not from ignoring some inputSource 8. Repeating this step pushes the ratio up without limit.

There is a limit to what this gives. The functions exist and have finitely many inputs. But the paper does not give useful bounds on how many inputs it needsSource 9. So it does not say how fast the ratio can grow with the number of inputs.

How sure is this? A computer proof checker called Lean has checked a formal version of the main result. The Lean scope note covers every C. For each, it gives a nonconstant Boolean function whose linear sum exceeds C times the square root of its degree. It also covers the version with absolute values. No specialist review of the paper has been published.

What it doesn't show. This does not say how many inputs are needed for a given violation, or what the true growth rate is.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Solid. Lean has checked the main statement; no specialist review is published, and the size of the examples is not controlled.

Words used

Boolean function: A rule that turns inputs of +1 or −1 into an output of +1 or −1.
Linear Fourier coefficient: The average of the output times one input, measuring how much the function agrees with that input.
Degree: The largest number of inputs multiplied together in any term of the function's polynomial form.
Majority function: The function that outputs the sign held by most inputs.
Cauchy–Schwarz inequality: A basic inequality that limits how large an average of products can be.

The original paper

Unbounded Violations of the Square-Root Degree Bound (PDF, opens in a new tab)
September 26, 2026

Lean notes

All quoted lines (9)

For Boolean $f$ , taking values in $\{-1,1\}$ , Cauchy–Schwarz gives $\sum_{i=1}^n\widehat f(\{i\}) =\E\!\left[f(X)\sum_{i=1}^nX_i\right]\le\sqrt n.$
Unbounded Violations of the Square-Root Degree Bound Back to text
Gopalan and Servedio conjectured that $\sqrt{\deg(f)}$ could replace $\sqrt n$ ; see O'Donnell's problem list.
Unbounded Violations of the Square-Root Degree Bound Back to text
The conjecture is attributed to Gopalan and Servedio, circa 2009, in O'Donnell's problem list.
Unbounded Violations of the Square-Root Degree Bound Back to text
This is the signed singleton sum of majority on $d$ bits, with either fixed value at ties.
Unbounded Violations of the Square-Root Degree Bound Back to text
Kudin and Pa\vsali\'c proved the cases $d=2,3$ and refuted the majority bound at $d=4$ .
Unbounded Violations of the Square-Root Degree Bound Back to text
We show that no constant multiple of this proposed bound holds.
Unbounded Violations of the Square-Root Degree Bound Back to text
A linear degree bound does hold for every Boolean function. Let $\operatorname{Inf}_i(f)$ be the probability that flipping coordinate $i$ changes its value, and let $I(f)=\sum_i\operatorname{Inf}_i(f)$ be the total influence.
Unbounded Violations of the Square-Root Degree Bound Back to text
Such an indicator may depend on all $m+1$ inputs: the degree saving comes from cancellation, not from ignoring a fixed coordinate.
Unbounded Violations of the Square-Root Degree Bound Back to text
The dimension and all copy counts in the construction are finite; we do not obtain useful bounds on their growth.
Unbounded Violations of the Square-Root Degree Bound Back to text

Other sources

openai/math, Lean scope note for family 192 (2026) For every $C>0$ , it gives a nonconstant Boolean function on a finite sign cube for which the sum of its linear Fourier coefficients exceeds $C\sqrt{\deg f}$ , where $\deg f$ is its real multilinear degree.
openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

191A power improvement in the Heilbronn triangle lower boundCombinatorics
190Polynomial removal fails for ordered binary matricesCombinatorics
189Cycle–clique Ramsey numbersCombinatorics
188The sharp terminal leave in random triangle removalCombinatorics
187Snaky in 21 Maker movesCombinatorics

Browse Combinatorics Lean-checked results Solid results