Boolean Fourier sums beyond square-root degree

Source and verification

This article explains family 192 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Fourier degree on the sign cube

For $f:\{-1,1{\}}^n\to \mathbb{R}$, with uniform independent signs $X_i$, define

$$\hat{f}(S)=\mathbb{E}\left[f(X)\prod _{i\in S}{X}_i\right].$$

These are the coefficients of the unique real multilinear polynomial representing $f$. Its degree is the largest $|S|$ with nonzero coefficient; a constant has degree zero. This is real polynomial degree, not degree over a finite field or the depth of a decision tree.

For Boolean functions taking values $\pm 1$, the signed sum of linear coefficients is

$$\begin{array}{rl}\sum _i\hat{f}(\{i\})& =\mathbb{E}\left[f(X)\sum _i{X}_i\right]\\ & \le \sqrt{n}.\end{array}$$

The inequality is Cauchy–Schwarz and uses $\mathbb{E}{f}^2=1$ and $\mathbb{E}({\sum }_i{X}_i{)}^2=n$.

Manuscript claim

For every $C>0$, there is a nonconstant Boolean function on a finite sign cube with

$$\sum _i\hat{f}(\{i\})>C\sqrt{\mathrm{deg}f}.$$

Thus no universal constant multiple of the square root of degree controls the linear-coefficient sum. (OpenAI, 2026)

The dimension and construction sizes may depend on $C$ and are not given useful quantitative bounds.

🏷️ Absolute coefficients and the surviving linear bound

Replacing an input coordinate $x_i$ by $-x_i$ changes the sign of its linear coefficient without changing polynomial degree. Choosing these flips separately makes all linear coefficients nonnegative. Hence the universal signed and absolute-value versions of the proposed bound are equivalent.

A linear degree bound does remain true. Let ${\partial }_{i}f$ be half the difference between the values with coordinate $i$ fixed to $+1$ and $-1$. It takes values in $\{-1,0,1\}$, has mean $\hat{f}(\{i\})$, and has second moment equal to the probability that flipping $i$ changes $f$.

Therefore

$$\begin{array}{rl}\sum _i|\hat{f}(\{i\})|& \le I(f)\\ & =\sum _S|S|\hat{f}(S{)}^2\\ & \le \mathrm{deg}f,\end{array}$$

using Parseval in the last step. The theorem separates square-root growth from this valid linear ceiling; it does not assert that every possible intermediate exponent fails.

The majority benchmark $\mathbb{E}|X_1+\cdots +X_d|$ is at most $\sqrt{d}$. Refuting a bound with that smaller benchmark would not automatically refute the square-root bound. The manuscript proves the stronger unbounded-ratio conclusion directly.

🏷️ Observations retaining information about a sum

Instead of constructing $f$ immediately, take a finite-valued observation $F$ of $N$ independent signs. Put

$$\begin{array}{c}{H}_N=\sum _{i=1}^N{X}_i,\\ T_F=\mathbb{E}[H_N\mid F],\\ v(F)=\mathbb{E}{T}_F^2.\end{array}$$

The score $T_F$ is the best mean-square predictor of the coordinate sum from the observation; $v(F)$ is its retained variance.

Suppose every output-cell indicator $1_{\{F=a\}}$ has polynomial degree at most $D$. Every function of $F$ is a linear combination of these indicators and therefore has degree at most $D$. In particular, choosing $f=\mathrm{sign}(T_F)$, with either value at zero, gives

$$\mathbb{E}[f{H}_N]=\mathbb{E}|T_F|.$$

Thus a large ratio $v(F)/D$, with sufficiently well-behaved score distribution, creates a large Fourier sum relative to square-root degree.

🏷️ Independent averaging and Gaussian readout

Take $k$ independent copies of an observation on disjoint input blocks. Their joint cell indicators have degree at most $kD$, while their total score is a sum of independent mean-zero variables with variance $kv(F)$.

For large finite $k$, the central limit theorem and second-moment control give

$$\mathbb{E}\left|\sum _{j=1}^k{T}_F^{(j)}\right|\sim \sqrt{\frac{2}{\pi }}\sqrt{kv(F)}.$$

The sign readout consequently has normalized correlation approaching at least $\sqrt{2/\pi }\sqrt{v(F)/D}$. It is enough to make the retained-variance-to-degree ratio arbitrarily large. Every construction used for a fixed target ratio remains finite.

For observations whose cells are subcubes, this route cannot gain in the same way: conditioning simply fixes some coordinates and leaves the others independent, so retained variance equals the expected number of fixed coordinates. The manuscript uses cells defined by polynomial cancellation rather than by fixing coordinates.

🏷️ Gaining variance without paying full degree

The central reporting rule uses $m+1$ standardized scores. One score selects a leaf among the other $m$, each associated with a short interval. Usually the report reveals all but one score, leaving residual variance one.

On the exceptional event where only the selected leaf misses its interval, the report is replaced by a single tag. The intervals are chosen so that the sum can be predicted from this tag with mean-square error strictly below one. The average residual error therefore drops below one, so retained variance exceeds $m$.

At the same time, each report indicator is a linear combination of functions involving at most $m$ score inputs. It may still depend on all $m+1$ inputs: the reduced degree comes from cancellation, not from ignoring a fixed coordinate. This yields a strict gain in retained variance relative to the allowed degree cost.

The manuscript iterates that gain, using finite averages approximating the chosen Gaussian configuration at each stage, then applies the final sign readout. Additional constructions allow different output cells to have different degree costs, but the main theorem already follows from the finite-observation amplification described above.

🏷️ Key steps and proof outlines

An indicator identity pays for an exceptional report

Let the independent inputs be $(u,z_1,\dots ,z_m)$, all centered with variance one, and write $L=u+{\sum }_j{z}_j$. Choose intervals $I_j$ and a selector $\iota (u)\in \{1,\dots ,m\}$. Define $B$ to mean that all leaves lie in their intervals, and $P$ to mean that every leaf except the selected one does. The exceptional event is $A=P\setminus B$.

Report only the tag $A$ on that event. On $B$, report all leaves and omit $u$. On $P^c$, report $u$ and the unselected leaves, omitting the selected one. Although the exceptional report can depend on every input, its indicator satisfies

$$1_A=\sum _{i=1}^m{1}_{\{\iota (u)=i\}}\prod _{j\ne i}{1}_{I_j}(z_j)-\prod _{j=1}^m{1}_{I_j}(z_j).$$

Every summand uses at most $m$ inputs. This is the cancellation that limits polynomial degree. The ordinary reports also have this property: a $P^c$ report already includes an unselected leaf failing its interval, so its validity does not impose an additional hidden condition on the omitted leaf. (OpenAI, 2026)

A predictor calculation gives an exact variance gain

Predict $L$ by a fixed number $b$ on $A$, by the sum of reported leaves on $B$, and by the sum of reported coordinates on $P^c$. On $B$, the omitted independent input has mean-square error one. On a $P^c$ report, its event is determined without the selected leaf, so that omitted variable also contributes exactly one in conditional second moment.

Consequently the predictor’s total error is

$$1-{\Delta }_b,{\Delta }_b=\mathbb{E}[1_A(1-(L-b{)}^2)].$$

Conditional expectation minimizes this error. Since $\mathrm{Var}(L)=m+1$, the report $\mathcal{W}$ retains variance at least $m+{\Delta }_b$. A strictly positive ${\Delta }_b$ is therefore enough to beat the degree cost $m$.

Gaussian interval placement makes the gain positive

For standard normal inputs, let ${\beta }_j,{\mu }_j,s_j^2$ be the probability, conditional mean, and conditional variance of $I_j$. Put $p_{\ast }={\prod }_j{\beta }_j$, $S={\sum }_j{s}_j^2$, and $b={\sum }_j{\mu }_j-1$. Conditioning on $u=t$ and $P$ leaves the selected leaf unrestricted; hence the mean of $L-b$ is $1+t-{\mu }_{\iota (t)}$ and its variance is $1+{\sum }_{j\ne \iota (t)}{s}_j^2$. A direct subtraction of the $B$ contribution gives

$${\Delta }_b=p_{\ast }(1+S-J),$$

where

$$J={\int }_{\mathbb{R}}\left((1+t-{\mu }_{\iota (t)}{)}^2+\sum _{j\ne \iota (t)}{s}_j^2\right)\frac{\varphi (t)}{{\beta }_{\iota (t)}}dt,$$

and $\varphi$ is the standard normal density. The positive one comes from the deliberately shifted mean on $B$.

Take a large odd $m$, set $R=\sqrt{8\log m}$ and interval half-width $h=m^{-3/2}$, and place $m$ equally spaced centers from $1-R$ to $1+R$. For $|t|\le R$, select the center nearest $1+t$; outside that range, select the middle interval centered at one. Interval variance is at most $h^2$, so $S\le m^{-2}$. Nearest-center error is at most $R/(m-1)+h$.

The central contribution to $J$ is at most $CR(R^2+1)e^{2R}{m}^{-1/2}=o(1)$, because $e^{2R}=m^{o(1)}$. The fallback interval keeps its probability bounded below by a constant times $h$, and Gaussian tail integration gives a tail contribution at most $C(R+1)m^{-5/2}=o(1)$. Fix one finite $m$ with $J<1/4$. Then ${\Delta }_b>3p_{\ast }/4>0$; the gain may be tiny, but it is fixed and strictly positive.

Transfer the strict gain and iterate finitely

Replace Gaussian inputs by normalized sums of independent copies of the current finite observation score. The central limit theorem gives weak convergence. Uniform fourth-moment bounds control the quadratic integrand’s tails, and the reporting rule’s finitely many boundary hyperplanes have Gaussian measure zero. Thus the strict gain survives for a sufficiently large finite averaging count.

Fix $\eta =p_{\ast }/2$. Each amplification retains more than $(m+\eta )$ times the incoming variance while multiplying its degree allowance by only $m$, after accounting for the same averaging factor in both. The ratio of retained variance to degree therefore grows by at least $1+\eta /m>1$ per stage. The Gaussian intervals and this gain remain fixed throughout; only the finite averaging count changes.

Starting with one revealed sign, finitely many stages make the ratio as large as desired. A final independent average and sign readout turn retained variance into absolute expected score, with Gaussian factor $\sqrt{2/\pi }$. Because every final cell indicator has the controlled degree, the resulting Boolean function violates the proposed square-root-degree bound by the prescribed factor. The reporting section supplies the cancellation and positive-gain calculation; the observation/readout lemmas supply the final Fourier interpretation.

See Also

• Influence and threshold widths uses Fourier mass and influence under vertex symmetry; the present counterexamples impose no such symmetry.
• Circulant Hadamard matrices imposes exact flatness on a discrete Fourier transform, a different constraint from low real polynomial degree.

🏷️ Manuscripts and verification scope

• Unbounded Violations of the Square-Root Degree Bound — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects unbounded signed and absolute linear-coefficient ratios relative to the square root of positive real multilinear degree. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Unbounded Violations of the Square-Root Degree Bound.