A Boolean function can beat the square-root degree bound by any factor

← All digests

Family 192 · Combinatorics
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

A Boolean function takes a string of binary inputs and returns one binary answer. Use signs $-1$ and $+1$ for the two values. Some functions closely follow individual inputs; others depend on complicated interactions among many inputs.

There are two different ways to measure this behavior. The function’s linear Fourier coefficients record its correlations with individual inputs. Its polynomial degree measures the largest interaction needed to express it exactly as a polynomial.

A conjecture of Gopalan and Servedio proposed a square-root relationship: the sum of the linear correlations should be at most the square root of the degree. Such a statement would replace the total number of input bits by a much more intrinsic measure of the function’s complexity.

The manuscript in this family claims that the proposed bound fails by arbitrarily large factors. For every chosen constant $C>0$, it constructs a finite Boolean function whose summed linear correlations exceed $C\sqrt{\deg(f)}$. A linear bound in the degree survives, so the question becomes how large the gap between these two scales can be.

2. Background and essential definitions

Fourier analysis on binary inputs

Let $X=(X_1,\ldots,X_n)$ be independent uniform random signs. For a subset $S\subseteq\{1,\ldots,n\}$, define

$$\widehat f(S)=\mathbb E\left[f(X)\prod_{i\in S}X_i\right].$$

The empty product is one, so $\widehat f(\varnothing)=\mathbb E[f(X)]$. These coefficients express every function on the sign cube uniquely as

$$f(x)=\sum_{S\subseteq\{1,\ldots,n\}}\widehat f(S)\prod_{i\in S}x_i.$$

Each variable appears with exponent at most one; this is the multilinear representation. Its degree is

$$\deg(f)=\max\{|S|:\widehat f(S)\ne0\}.$$

The degree is over the real numbers and represents the function exactly. It is not degree modulo two, approximate polynomial degree, or the number of input queries used by an algorithm.

For a singleton set $\{i\}$, the coefficient $\widehat f(\{i\})=\mathbb E[f(X)X_i]$ measures agreement with input $i$: it is the probability of agreement minus the probability of disagreement.

Their signed sum satisfies

$$L(f):=\sum_{i=1}^n\widehat f(\{i\}) =\mathbb E\left[f(X)\sum_{i=1}^nX_i\right].$$

Thus $L(f)$ measures correlation with the total input sum. Since a Boolean function has $f(X)^2=1$, the Cauchy–Schwarz inequality gives $L(f)\le\sqrt n$. The conjecture asks whether $\sqrt{\deg(f)}$ can replace $\sqrt n$.

A surviving general bound

The influence of coordinate $i$ is the probability that flipping only that input changes the output. Write it as $\operatorname{Inf}_i(f)$, and let $I(f)$ be the sum over coordinates.

The standard Fourier identities imply

$$\sum_i|\widehat f(\{i\})| \le I(f) =\sum_S|S|\widehat f(S)^2 \le\deg(f).$$

The last step uses $\sum_S\widehat f(S)^2=1$, the analogue of Parseval’s identity for a Boolean function. So there is already a dimension-independent linear degree bound. The disputed claim is the much smaller square-root scale.

3. Development history and previous partial results

Nisan and Szegedy’s 1994 work developed the study of Boolean functions through their exact real polynomial degree. This connects a discrete input-output rule with algebraic constraints on which interactions can occur. The influence identities above belong to that established framework.

O’Donnell’s problem list attributes the square-root conjecture to Gopalan and Servedio around 2009. It also records a stronger proposal based on majority. If $d$ independent signs are available, define

$$B_d=\mathbb E|X_1+\cdots+X_d|\le\sqrt d.$$

Majority on those signs, with a fixed output chosen at ties, has summed linear correlation $B_d$. The stronger proposal would bound a degree-$d$ function’s sum by this majority benchmark. The problem list records the two related questions.

Jha and Wang gave reformulations of the majority proposal and settled some special degree ranges. Kudin and Pašalić established additional low-degree cases and disproved the majority bound at degree four. That was a counterexample to the stronger inequality; it did not by itself contradict the weaker square-root bound. M1 carefully separates these statements despite varying terminology in the literature.

Another source of positive evidence came from decision trees. These compute a function by revealing information about the inputs. O’Donnell and Servedio related correlation to the expected amount of information revealed in ordinary decision trees; Blais, Tan, and Wan obtained a square-root bound involving parity decision-tree depth, where a query reveals a product of input signs.

M1’s construction uses a different kind of observation. It controls the polynomial degree of each possible output event rather than requiring the observation to be a sequence of simple queries. Algebraic cancellation then permits behavior that the earlier decision-tree bounds do not rule out.

4. What the new manuscripts claim

The family contains one manuscript, M1. Its main statement is that for every real $C>0$, there are a positive integer $n$ and a nonconstant Boolean function $f:\{-1,1\}^n\to\{-1,1\}$ such that

$$\sum_{i=1}^n\widehat f(\{i\})>C\sqrt{\deg(f)}.$$

This excludes every constant-factor version of the square-root conjecture. It is stronger than finding a single function that barely exceeds the proposed constant one.

The conclusion also applies to the sum of absolute values:

$$\sup_{\substack{n\ge1,\ f:\{-1,1\}^n\to\{-1,1\}\\\deg(f)>0}} \frac{\sum_i|\widehat f(\{i\})|}{\sqrt{\deg(f)}}=\infty.$$

Indeed, reversing any input sign changes the sign of its linear coefficient while preserving polynomial degree. A universal bound for signed sums would therefore also bound absolute sums after suitable input reversals. M1’s examples already produce a large positive signed sum directly.

Every example in the theorem has finitely many inputs. Limits enter the construction to establish that sufficiently large finite choices exist. The source explicitly does not give useful bounds on how the dimension or replication counts grow with the requested violation factor.

5. Why the advance matters

Importance: 3/5. The claimed result resolves a concrete conjecture in the analysis of Boolean functions and rules out its entire constant-factor relaxation. It clarifies that exact polynomial degree can underestimate this kind of accumulated linear correlation by more than a fixed square-root factor.

Linear Fourier information is a natural way to detect which inputs align with an output. Polynomial degree is a different structural measure, central to connections between algebra and computation. Understanding their limitations helps separate forms of complexity that initially appear closely related.

The claim is also conceptually stronger than the earlier failure of the majority benchmark. A modest violation of an exact extremal candidate might still leave a universal square-root law intact. An unbounded ratio rules out that broader law too.

At the same time, the surviving linear degree bound remains valid, and the manuscript does not determine the optimal replacement. The advance changes the range of possible answers without completing the full extremal picture.

6. The main idea

First retain information, then output a sign

Instead of immediately designing the Boolean function, M1 constructs a finite-valued observation $F$ of a block of input signs. It can have more than two possible outputs. Let

$$H_N=X_1+\cdots+X_N, \qquad T_F=\mathbb E[H_N\mid F].$$

Conditional expectation means the best mean-square prediction of the input sum when the observation is known. The random variable $T_F$ records that prediction. Since the input sum has mean zero, so does $T_F$.

Define the retained variance by

$$v(F)=\mathbb E[T_F^2].$$

A large retained variance means that observing $F$ reveals substantial information about the sum. Meanwhile, impose a degree bound $D$ on every event indicator $\mathbf1_{\{F=a\}}$, which is one when the output is $a$ and zero otherwise.

Every function of $F$ is a linear combination of those indicators, so it also has degree at most $D$. In particular, reading out the sign of $T_F$ gives a Boolean function with controlled degree and correlation $\mathbb E|T_F|$.

The construction seeks observations with $v(F)/D$ arbitrarily large.

Independent averaging turns variance into correlation

Take $M$ independent copies of the same observation on disjoint input blocks, with scores $T_1,\ldots,T_M$. Their sum has variance $Mv(F)$. The central limit theorem says that, after normalization, this sum approaches a standard Gaussian variable as $M$ grows.

Choose the final output to be the sign of that score sum, assigning either fixed sign at zero. Its degree is at most $MD$, while its linear correlation behaves asymptotically like

$$\sqrt{\frac{2}{\pi}}\sqrt{Mv(F)}.$$

Thus the correlation divided by the square root of the degree bound is governed by $\sqrt{v(F)/D}$. An arbitrarily large retained-variance ratio would give the desired Boolean counterexamples using a sufficiently large but finite number of copies.

Cancellation improves the information-to-degree ratio

The central construction starts with $m+1$ independent standardized scores, each having mean zero and variance one. Simply revealing $m$ of them retains $m$ units of variance.

M1 designs a more selective reporting rule. Usually it reports all but one score. On a specially chosen exceptional event it reports a single tag, and that tag predicts the total sum with mean-square error smaller than the one unit normally lost by hiding one score.

The source claims that this retains strictly more than $m$ units of variance. Yet each output indicator can be expressed as a linear combination of functions depending on at most $m$ of the input observations. When the observations themselves have degree bound $D$, this gives degree at most $mD$.

The crucial feature is cancellation in that indicator expansion. An output can depend on all $m+1$ scores without requiring their full combined degree. The saving does not come from permanently ignoring one fixed input.

A Gaussian model supplies intervals and reporting rules with a definite gain. Independent averaging transfers those rules to finite sign inputs. Repeating the gain a finite number of times makes the retained-variance ratio exceed any prescribed level, after which the sign readout completes the stated construction.

7. Scope, limitations, and open questions

The theorem concerns the sum of linear coefficients, not their squared sum. Parseval’s identity still bounds the total squared Fourier mass by one. A large sum of many small linear correlations is compatible with that restriction.

The degree is exact real multilinear degree. The statement does not transfer automatically to approximate degree, arithmetic over a finite field, decision-tree depth, or circuit size. Each of those measures carries different constraints.

The construction establishes arbitrarily large violations but does not supply useful dimension bounds in terms of the desired factor. It also does not claim a simple small formula giving an optimal example at every degree.

The surviving estimate $\sum_i|\widehat f(\{i\})|\le\deg(f)$ leaves substantial room above the square-root scale. Determining the true extremal growth, finding simpler examples, and identifying important subclasses where square-root behavior survives are natural further questions.

8. Sources and further reading

• Nisan and Szegedy, On the degree of Boolean functions as real polynomials, for the exact-degree framework and influence identities.
• O’Donnell, Open Problems in Analysis of Boolean Functions, for the square-root and majority proposals.
• Kudin and Pašalić, Proving the conjecture of O’Donnell in certain cases and disproving its general validity, for the earlier majority-bound counterexample.
• Blais, Tan, and Wan, An inequality for the Fourier spectrum of parity decision trees, for the distinct decision-tree setting.

M1 develops the finite-observation construction, Gaussian comparison, and repeated amplification used in its claimed counterexamples.

Source manuscripts

• M1. OpenAI, Unbounded Violations of the Square-Root Degree Bound (September 26, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.