OctoInformBeta

OpenAI preprint, September 2026 · Section 2. Finite observations and amplification

Lemma 2.2: Finite observations with sufficiently large variance per cell degree produce nonconstant Boolean functions with large signed singleton sums

Retained variance yields square-root violations.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A finite observation of a sign cube retains part of the coordinate sum through its conditional score. The relevant quantities are the second moment of that score and the Fourier degrees of the observation’s fiber indicators. The resulting Boolean functions are measured by their signed singleton Fourier sums relative to the square root of their degrees.

For a finite coordinate set II, the sign cube {−1,1}I\{-1,1\}^{I} is the set of maps from II to {−1,1}\{-1,1\}.✦ A Boolean function f:A→ℝf:A\to\mathbb R on a set AA is a function taking values in {−1,1}\{-1,1\}; a function f:A→ℝf:A\to\mathbb R is nonconstant when it takes different values at two points. All finite averages are uniform. For a real observable gg on a finite set AA, its uniform mean is 𝔼Ag=1|A|∑a∈Ag(a),𝔼⌀g=0.\mathbb E_A g=\frac{1}{|A|}\sum_{a\in A}g(a), \qquad \mathbb E_{\varnothing}g=0.(1)✦

For S⊆IS\subseteq I, the Fourier character χS\chi_S and the real Fourier-Walsh coefficient of f:{−1,1}I→ℝf:\{-1,1\}^{I}\to\mathbb R are given by χS(x)=∏i∈Sxi,fˆ(S)=𝔼x[f(x)χS(x)].\chi_S(x)=\prod_{i\in S}x_i, \qquad \widehat f(S)=\mathbb E_x[f(x)\chi_S(x)].(2) For a real function f:{−1,1}I→ℝf:\{-1,1\}^{I}\to\mathbb R on a finite sign cube, the ordinary real multilinear Fourier degree deg⁡f\deg f is the largest cardinality of a set with nonzero coefficient in (2), with degree zero for constants and the zero function. For a real function f:{−1,1}I→ℝf:\{-1,1\}^{I}\to\mathbb R on a finite sign cube, the signed singleton sum L(f)L(f) is the real number given by (3), with the signs of the coefficients retained rather than replaced by their absolute values: L(f)=∑i∈Ifˆ({i}).L(f)=\sum_{i\in I}\widehat f(\{i\}).(3)✦ The degree used with (3) is distinct from polynomial threshold degree and degree over a finite field.

An observation F:{−1,1}I→BF:\{-1,1\}^{I}\to B is a map into a report set BB. For an observation F:{−1,1}I→BF:\{-1,1\}^{I}\to B, a report b∈Bb\in B and a real observable gg on the sign cube, the fiber indicator 1F=b1_{F=b} is the real-valued function equal to one on the fiber over bb and zero elsewhere, while the fiber probability pF(b)p_F(b) and restricted moment mF,g(b)m_{F,g}(b) are the real numbers given by the uniform averages in (4): 1F=b(x)={1,F(x)=b,0,F(x)≠b,pF(b)=𝔼x1F=b(x),mF,g(b)=𝔼x[1F=b(x)g(x)].1_{F=b}(x)= \begin{cases}1,&F(x)=b,\\0,&F(x)\ne b,\end{cases} \qquad p_F(b)=\mathbb E_x1_{F=b}(x), \qquad m_{F,g}(b)=\mathbb E_x[1_{F=b}(x)g(x)].(4) For an observation F:{−1,1}I→BF:\{-1,1\}^{I}\to B and a real observable gg on its sign cube, the fiber conditional mean μF,g:B→ℝ\mu_{F,g}:B\to\mathbb R is the function given by the quotient of the restricted moment by the fiber probability in (4), with value zero on an empty fiber. The conditional expectation 𝔼[g∣F]\mathbb E[g\mid F] of a real observable gg under an observation F:{−1,1}I→BF:\{-1,1\}^{I}\to B is the real-valued function on the sign cube obtained by evaluating the fiber conditional mean μF,g\mu_{F,g} at the observed report: μF,g(b)={mF,g(b)/pF(b),pF(b)>0,0,pF(b)=0,𝔼[g∣F](x)=μF,g(F(x)).\mu_{F,g}(b)= \begin{cases}m_{F,g}(b)/p_F(b),&p_F(b)>0,\\0,&p_F(b)=0,\end{cases} \qquad \mathbb E[g\mid F](x)=\mu_{F,g}(F(x)).(5)

For an observation F:{−1,1}I→BF:\{-1,1\}^{I}\to B, the coordinate sum SIS_I and the centered conditional score sFs_F are real-valued functions on the sign cube, and the retained variance v(F)v(F) is the second moment of sFs_F, given using (5) by SI(x)=∑i∈Ixi,sF(x)=𝔼[SI∣F](x),v(F)=𝔼x[sF(x)2].S_I(x)=\sum_{i\in I}x_i, \qquad s_F(x)=\mathbb E[S_I\mid F](x), \qquad v(F)=\mathbb E_x[s_F(x)^2].(6) For an observation F:{−1,1}I→BF:\{-1,1\}^{I}\to B and a nonnegative integer nn, the grouped score scale an(F)a_n(F) is the nonnegative real number defined from the retained variance in (6) by an(F)=nv(F).a_n(F)=\sqrt n\,\sqrt{v(F)}.(7)

Definition 1. The sign threshold σ:ℝ→{−1,1}\sigma:\mathbb R\to\{-1,1\} is the function σ(z)={1,z≥0,−1,z<0.\sigma(z)=\begin{cases}1,&z\ge0,\\-1,&z<0.\end{cases}(8)✦

The score sign readout ρF\rho_F of an observation F:{−1,1}I→BF:\{-1,1\}^{I}\to B is the function from the sign cube to {−1,1}\{-1,1\} obtained by applying the threshold in (8) to the conditional score sFs_F: ρF(x)=σ(sF(x)).\rho_F(x)=\sigma(s_F(x)).(9)✦

The Gaussian Gain Constant

For real parameters aa and hh, the tent function τa,h:ℝ→ℝ\tau_{a,h}:\mathbb R\to\mathbb R is given by (10). τa,h(t)=max⁡{0,1−|t−a|/h}.\tau_{a,h}(t)=\max\{0,1-|t-a|/h\}.(10)✦ Let γ\gamma denote the standard Gaussian probability measure on ℝ\mathbb R. The Gaussian gain test ψ:ℝ→ℝ\psi:\mathbb R\to\mathbb R is the function and the gain constant c∈ℝc\in\mathbb R is the number defined from (10) by ψ(t)=12τ1,1/2(t),c=12∫ℝψ(t)dγ(t).\psi(t)=\tfrac12\tau_{1,1/2}(t), \qquad c=\tfrac12\int_{\mathbb R}\psi(t)\,d\gamma(t).(11)

For a real observable TT on a finite set AA and a nonnegative integer nn, the normalized sum ZT,n:An→ℝZ_{T,n}:A^n\to\mathbb R is a real-valued function on AnA^n, equal to zero when n=0n=0 and given by (12) when n>0n>0. ZT,n(x)=1n∑j=1nT(xj).Z_{T,n}(x)=\frac{1}{\sqrt n}\sum_{j=1}^{n}T(x_j).(12)✦

The Claim

Theorem 1. Let II be finite and let F:{−1,1}I→BF:\{-1,1\}^{I}\to B have v(F)>0v(F)>0. Let DD be a nonnegative integer such that every fiber indicator 1F=b1_{F=b} has degree at most DD. With the scale in (7) and the constant in (11), there exist a positive integer nn and a Boolean function f:{−1,1}{1,…,n}×I→ℝf:\{-1,1\}^{\{1,\ldots,n\}\times I}\to\mathbb R satisfying deg⁡f≤nD,can(F)<L(f).\deg f\le nD, \qquad c\,a_n(F)<L(f).(13)✦ Suppose further that D>0D>0 and that C>0C>0 satisfies (C/c)2<v(F)/D(C/c)^2<v(F)/D. There exist a positive integer mm and a nonconstant Boolean function g:{−1,1}{1,…,m}→ℝg:\{-1,1\}^{\{1,\ldots,m\}}\to\mathbb R satisfying Cdeg⁡g<L(g).C\sqrt{\deg g}<L(g).(14)✦

In the paper, the result reads: if finite observations have positive cell degree bounds DD and arbitrarily large ratios v(F)/Dv(F)/D, then Theorem 1.1 holds. The first assertion gives amplified Fourier gain: a Boolean function on a positive number of blocks has degree at most the number of blocks times the fiber degree bound, and its signed singleton sum exceeds the Gaussian gain constant times the grouped score scale.

What Is Checked

The assertions (13) and (14) are stated over uniform finite sign cubes and the ordinary real Fourier degrees of the fiber indicators of FF, with positive retained variance; (14) also assumes positive DD and CC and the stated ratio inequality.

For the readout in (9), the library states the Boolean-valuedness assertion (15) and the signed singleton identity (16): ρF(x)∈{−1,1}(x∈{−1,1}I).\rho_F(x)\in\{-1,1\} \qquad\bigl(x\in\{-1,1\}^{I}\bigr).(15)✦ L(ρF)=𝔼x|sF(x)|.L(\rho_F)=\mathbb E_x|s_F(x)|.(16)✦ When every fiber indicator of FF has degree at most a nonnegative integer DD, the readout satisfies (17): deg⁡ρF≤D.\deg\rho_F\le D.(17)✦ The score sign readout has Fourier degree at most the common Fourier degree bound for the fiber indicators.

The Gaussian constant defined in (11) satisfies (18): c>0.c>0.(18)✦ For a real observable TT on a finite set AA with 𝔼AT=0\mathbb E_A T=0 and 𝔼AT2=1\mathbb E_A T^2=1, the normalized sums in (12) satisfy (19): there exists an integer n>0 such that c<𝔼x∈An|ZT,n(x)|.\text{there exists an integer }n>0\text{ such that } c<\mathbb E_{x\in A^n}|Z_{T,n}(x)|.(19)✦ The Gaussian gain constant is strictly positive. Every real observable on a finite set with uniform mean zero and second moment one has a normalized sum over a positive number of samples whose uniform mean absolute value exceeds the Gaussian gain constant.