A tagged report

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

This lesson proves the main theorem of Linear Fourier coefficients and degree. Section 1 reduces it to a single reporting rule on $m+1$ real inputs that retains more than $m$ units of variance of their sum while each of its output cells is a combination of functions of only $m$ inputs. Section 2 gives such a rule, the refined report: one input selects one of the other $m$ inputs, and on the exceptional event where only the selected input fails a short interval test, the rule reports a single tag. Section 3 chooses the intervals for Gaussian inputs, and Section 4 transfers the Gaussian gain to finite scores with the tools of Asymptotically normal scores. Section 5 gives two variants of the rule. Notation for observations, scores $T_F$, retained variance $v(F)$ and cell degree bounds is that of the first lesson.

1. Amplification

Lemma 1.1 (Boolean readout). If there are finite observations with positive cell degree bounds $D$ and arbitrarily large ratios $v(F)/D$, the theorem holds.

Proof. Fix $C>0$ and choose $F$ with $v=v(F)>4C^2D$. Take $M$ independent copies on disjoint blocks, with scores $T_1,\dots,T_M$, and $f=\operatorname{sign}(T_1+\dots+T_M)$. By Lemma 3.1 of the first lesson, $\deg f\le MD$ and $\sum_i\widehat f(\{i\})=\mathbb E|T_1+\dots+T_M|$, which is $\sqrt{Mv}\,\mathbb E|Z_M|$ with $Z_M=(T_1+\dots+T_M)/\sqrt{Mv}$. By Theorem 1.1 and Lemma 2.1 of Asymptotically normal scores, $\mathbb E|Z_M|\to\sqrt{2/\pi}>1/2$, so for large $M$ the sum exceeds $\frac12\sqrt{Mv}>C\sqrt{MD}\ge C\sqrt{\deg f}$; it is positive, so $f$ is not constant. $\square$

A rule on $r$ real inputs is a measurable map $\mathcal W$ from $\mathbb R^r$ to some set of output labels. Its coordinate cost is at most $d$ if, on every product of finite subsets of $\mathbb R$, the indicator of each output label is a finite linear combination of functions each depending on at most $d$ coordinates.

Proposition 1.2 (Amplification criterion). Let $1\le d<r$, and let $\mathcal W$ be a rule on $r$ inputs with coordinate cost at most $d$. Suppose there is $\eta>0$ such that for every sequence $Z_n$ of centered, variance-one, asymptotically standard normal random variables taking finitely many values, independent copies $\mathbf Z_n=(Z_{n,1},\dots,Z_{n,r})$ satisfy, for all large $n$, $\operatorname{Var}\Bigl(\mathbb E\Bigl[\sum_{i=1}^rZ_{n,i}\Bigm|\mathcal W(\mathbf Z_n)\Bigr]\Bigr)\ge d+\eta .$ Then finite observations have arbitrarily large ratios $v(F)/D$, and the theorem holds.

Proof. Let $F$ be a finite observation with $v=v(F)>0$ and cell degree bound $D$. Form $r$ blocks of $M$ independent copies of $F$, let $Z_{M,i}$ be the normalized sum of the scores in block $i$, and put $F'=\mathcal W(Z_{M,1},\dots,Z_{M,r})$, an observation with finitely many values. A function of one input $Z_{M,i}$ is a function of $M$ copies of $F$, of degree at most $MD$; so the coordinate cost gives the cell degree bound $dMD$ for $F'$. By Lemma 3.1 of the first lesson, the score of $F'$ is $\mathbb E[\sum_i\sqrt{Mv}Z_{M,i}\mid F']$, so $v(F')=Mv\operatorname{Var}(\mathbb E[\sum_iZ_{M,i}\mid F'])$. The variables $Z_{M,i}$ are centered, have variance one and are asymptotically standard normal as $M\to\infty$ (Theorem 1.1 of Asymptotically normal scores); so for large $M$, $v(F')\ge Mv(d+\eta)$, and $\frac{v(F')}{dMD}\ge\frac vD\Bigl(1+\frac\eta d\Bigr).$ Start with one revealed sign ($v=D=1$) and iterate; each stage uses its own finite $M$. Finitely many stages exceed any ratio, and Lemma 1.1 applies. $\square$

Revealing $d$ of $r=d+1$ inputs retains variance exactly $d$. The criterion asks for a rule that beats this by a fixed margin at the same cost.

2. The refined report

Let $m\ge3$, let $I_1,\dots,I_m$ be intervals, and let $\iota:\mathbb R\to\{1,\dots,m\}$ be a selector with finitely many cut points, so that each $U_i=\{t:\iota(t)=i\}$ is a finite union of intervals; all endpoint conventions are fixed. Write the inputs as $(u,z_1,\dots,z_m)$, their sum as $L=u+\sum_jz_j$, and $\begin{gathered} B=\{z_j\in I_j\text{ for all }j\},\\ P=\{z_j\in I_j\text{ for all }j\ne\iota(u)\},\\ A=P\setminus B . \end{gathered}$ So $A$ is the event that the selected input $z_{\iota(u)}$ alone fails its test, and $A$, $B$, $P^c$ partition the inputs. The refined report $\mathcal W$ reports:

event	report
$A$	the tag $A$ only
$B$	$(B,z_1,\dots,z_m)$
$P^c$	$(P^c,u,\iota(u),(z_j)_{j\ne\iota(u)})$

Lemma 2.1 (Cost of the refined report). On every product of finite input alphabets, $\mathcal W$ has finitely many values and coordinate cost at most $m$. The key identity is $\begin{aligned} \mathbf 1_A&=\sum_{i=1}^m\mathbf 1_{U_i}(u)\prod_{j\ne i}\mathbf 1_{I_j}(z_j)\\ &\quad -\prod_{j=1}^m\mathbf 1_{I_j}(z_j). \end{aligned}\tag{2.1}$

Proof. The first sum is $\mathbf 1_P$, as exactly one $i$ has $u\in U_i$; subtracting $\mathbf 1_B\le\mathbf 1_P$ gives $\mathbf 1_A$. Each product involves $m$ coordinates: $u$ and $m-1$ leaves, or the $m$ leaves. An attained $B$ report fixes the $m$ leaves and is the product of their value tests. An attained $P^c$ report fixes $u$, $i=\iota(u)$ and the other $m-1$ leaves, one of which fails its test; so it forces $P^c$ whatever $z_i$ is, and its indicator depends on these $m$ coordinates. Unattained labels have zero indicator. $\square$

The indicator of $A$ depends on all $m+1$ inputs, but (2.1) writes it as a combination of functions of $m$ inputs: the saving comes from cancellation.

Lemma 2.2 (Retained variance). Let the inputs be independent, centered, of variance one, each taking finitely many values. For every $b\in\mathbb R$, with $\Delta_b=\mathbb E\bigl[\mathbf 1_A(1-(L-b)^2)\bigr]$, $\operatorname{Var}\bigl(\mathbb E[L\mid\mathcal W]\bigr)\ge m+\Delta_b .$

Proof. Predict $L$ by $b$ on $A$, by $\sum_jz_j$ on $B$, and by $u+\sum_{j\ne\iota(u)}z_j$ on $P^c$; this is a function of the report. On $B$ the error is $u$, and $B$ is independent of $u$, so this part contributes $\mathbb E[\mathbf 1_Bu^2]=\Pr(B)$. For each $i$, the event $E_i=P^c\cap\{u\in U_i\}$ depends only on $u$ and the leaves other than $z_i$, so the error $z_i$ contributes $\mathbb E[\mathbf 1_{E_i}z_i^2]=\Pr(E_i)$. The total squared error is $\Pr(A^c)+\mathbb E[\mathbf 1_A(L-b)^2]=1-\Delta_b$. The conditional expectation, the orthogonal projection onto functions of the report, has at most this error, so $\begin{aligned} &\operatorname{Var}(\mathbb E[L\mid\mathcal W])\\ &\quad=\operatorname{Var}(L)-\mathbb E(L-\mathbb E[L\mid\mathcal W])^2\\ &\quad\ge(m+1)-(1-\Delta_b). \end{aligned}$ $\square$

3. Gaussian intervals

Lemma 3.1 (Gaussian design). There are an odd $m\ge3$, closed intervals $I_1,\dots,I_m$ and a selector $\iota$ with finitely many cut points such that, for independent standard normal inputs, with $\beta_j=\Pr(z_j\in I_j)$, conditional means $\mu_j$ and variances $s_j^2$ on $I_j$, $\begin{gathered} p_*=\prod_j\beta_j>0,\\ S=\sum_js_j^2<\tfrac14,\qquad b=\sum_j\mu_j-1, \end{gathered}$ the deficit satisfies $d_A=\mathbb E\bigl[\mathbf 1_A(1-(L-b)^2)\bigr]>\tfrac34p_* .$

Proof. An exact identity. Fix $u=t$ and $i=\iota(t)$. Given $u=t$, the event $P$ has probability $p_*/\beta_i$, restricts the leaves $j\ne i$ to their intervals and leaves $z_i$ free; then $L-b$ has mean $1+t-\mu_i$ and variance $1+\sum_{j\ne i}s_j^2$. So, with $\phi$ the normal density, $\begin{aligned} &\mathbb E\bigl[\mathbf 1_P(1-(L-b)^2)\bigr]=-p_*J,\\ &J=\int_{\mathbb R}\Bigl((1+t-\mu_{\iota(t)})^2+\sum_{j\ne\iota(t)}s_j^2\Bigr)\\ &\qquad\cdot\frac{\phi(t)}{\beta_{\iota(t)}}\,dt . \end{aligned}$ On $B$, with $u$ free, $L-b$ has mean $1$ and variance $1+S$, so $\mathbb E[\mathbf 1_B(1-(L-b)^2)]=-p_*(1+S)$. As $\mathbf 1_A=\mathbf 1_P-\mathbf 1_B$, $d_A=p_*(1+S-J). \tag{3.1}$

The intervals. For odd $m$ put $R=\sqrt{8\log m}$, $h=m^{-3/2}$, centres $a_i=1-R+\frac{2R(i-1)}{m-1}$ and $I_i=[a_i-h,a_i+h]$. For $|t|\le R$ let $\iota(t)$ be the index of a centre nearest to $1+t$ (the smaller index on ties); for $|t|>R$, the middle index, whose centre is $1$. Then $|\mu_i-a_i|\le h$, $s_i^2\le h^2$, and $\beta_i\ge2h\phi(|a_i|+h)$.

For $|t|\le R$, the spacing gives $|1+t-\mu_{\iota(t)}|\le\frac R{m-1}+h$ and $|a_{\iota(t)}|+h\le|t|+2$ for large $m$, so $\phi(t)/\beta_{\iota(t)}\le\frac1{2h}e^{2|t|+2}\le\frac{e^2}{2h}e^{2R}$, and the central part of $J$ is at most $\begin{aligned} &\frac{e^2R}he^{2R}\Bigl(\bigl(\tfrac R{m-1}+h\bigr)^2+mh^2\Bigr)\\ &\quad =O\bigl(R(R^2+1)e^{2R}m^{-1/2}\bigr)\longrightarrow0, \end{aligned}$ since $e^{2R}=e^{2\sqrt{8\log m}}$ grows more slowly than every power of $m$. For $|t|>R$, the selected interval has $\beta\ge2h\phi(2)$, the numerator is $O(1+t^2)$, and $\int_{|t|>R}(1+t^2)\phi(t)\,dt$ is $O((R+1)e^{-R^2/2})$, that is, $O((R+1)m^{-4})$, so the tail part is $O((R+1)m^{-5/2})\to0$. Also $S\le mh^2=m^{-2}$. For large odd $m$, $J<\frac14$ and $S<\frac14$, and (3.1) gives $d_A>\frac34p_*$. $\square$

The limit is reached only for very large $m$. For $|t|\le R$, $\phi(t)/\beta_{\iota(t)}$ is close to $e^{t+1/2}/(2h)$, the squared mismatch $(1+t-\mu_{\iota(t)})^2$ averages about $R^2/(3(m-1)^2)$ over a selector cell, and $S$ is close to $mh^2/3$. So to leading order $J\approx(R^2+1)e^{R+1/2}/(6\sqrt m)$, which is below $\frac14$ only when $\log m$ exceeds about $54$.

Since $\begin{aligned} d_A&=\Pr(A)\bigl(1-\operatorname{Var}(L\mid A)\\ &\qquad-(\mathbb E[L\mid A]-b)^2\bigr)>0, \end{aligned}$ the sum varies by less than one unit on $A$: this is the variance saved by the tag.

4. Transfer and the theorem

Lemma 4.1 (Transfer). Fix the design of Lemma 3.1 and put $\eta=p_*/2$. If $Z_n$ are centered, variance-one, asymptotically standard normal random variables with finitely many values, then for independent copies $\mathbf Z_n$ of $m+1$ inputs and all large $n$, $\operatorname{Var}\bigl(\mathbb E[L\mid\mathcal W(\mathbf Z_n)]\bigr)>m+\eta .$

Proof. Expanding $\mathbf 1_A$ by (2.1) and $(L-b)^2$ as a polynomial of degree two writes $g=\mathbf 1_A(1-(L-b)^2)$ as a finite linear combination of functions $\prod_k\mathbf 1_{J_k}(x_k)x_k^{a_k}$ with finite unions of intervals $J_k$ (the intervals $I_j$, the sets $U_i$, or $\mathbb R$) and $a_k\le2$. By Corollary 2.2 of Asymptotically normal scores, $\mathbb Eg(\mathbf Z_n)\to d_A>\frac34p_*$, so $\Delta_b>\eta$ for large $n$, and Lemma 2.2 applies. $\square$

Theorem 4.2. The refined report satisfies the amplification criterion (Proposition 1.2) with $(r,d,\eta)=(m+1,m,p_*/2)$.

Proof. Lemma 2.1 gives the cost and Lemma 4.1 the variance. $\square$

Theorem 4.3 (OpenAI 2026). For every $C>0$ there are $n$ and a nonconstant $f:\{-1,1\}^n\to\{-1,1\}$ with $\sum_i\widehat f(\{i\})>C\sqrt{\deg f}$. Consequently $\sup_f\sum_i|\widehat f(\{i\})|/\sqrt{\deg f}=\infty$ over all nonconstant Boolean functions.

Proof. Theorem 4.2 and Proposition 1.2. $\square$

The dimension and the number of copies used are finite but grow extremely fast; the proof gives no useful bound on them.

5. Two variants

The coarse report. Replace the report on $B$ by a single mark: $\mathcal O$ reports $X$ on $A$, $Y$ on $B$, and $(O,u,\iota(u),(z_j)_{j\ne\iota(u)})$ on $P^c$.

Proposition 5.1. $\mathcal O$ has coordinate cost at most $m$. For independent centered variance-one inputs with finitely many values and constants $b_0,b_1$, with $g_{b_0,b_1}$ the sum of $\mathbf 1_A(1-(L-b_0)^2)$ and $\mathbf 1_B(1-(L-b_1)^2)$, $\operatorname{Var}\bigl(\mathbb E[L\mid\mathcal O]\bigr)\ge m+\mathbb Eg_{b_0,b_1}.$ For Gaussian inputs and the design of Lemma 3.1, $\mathbb Eg_{b,M_\mu}=p_*(1-J)>\frac34p_*$, where $M_\mu=\sum_j\mu_j$. Hence the coarse report also satisfies the amplification criterion with $(r,d,\eta)=(m+1,m,p_*/2)$.

Proof. The cost is as in Lemma 2.1; the $Y$ indicator depends on the leaves only. Predict by $b_0$ on $X$, by $b_1$ on $Y$, and by $u+\sum_{j\ne\iota(u)}z_j$ on ordinary reports; the error is $\begin{aligned} &\Pr(P^c)+\mathbb E[\mathbf 1_A(L-b_0)^2]\\ &\quad+\mathbb E[\mathbf 1_B(L-b_1)^2]=1-\mathbb Eg_{b_0,b_1}, \end{aligned}$ and the variance bound follows as in Lemma 2.2. For Gaussian inputs, on $B$ the variable $L-M_\mu$ has mean $0$ and variance $1+S$, so $\mathbb E[\mathbf 1_B(1-(L-M_\mu)^2)]=-p_*S$, and $\mathbb Eg_{b,M_\mu}=d_A-p_*S=p_*(1-J)$ by (3.1). The transfer is as in Lemma 4.1. $\square$

The coarse report loses $p_*S$ against the refined one: merging the $B$ reports leaves the small leaf variance $S$ unobserved.

Switching to an independent input. Keep $A$ and $b$, put $q=m+1$, and add a further independent input $w$. The rule $\mathcal O_+$ reports $(\mathrm{off},\mathbf z)$ if $\mathbf z=(u,z_1,\dots,z_m)\notin A$, and $(\mathrm{on},w)$ if $\mathbf z\in A$.

Proposition 5.2. $\mathcal O_+$ has $q+1$ inputs and coordinate cost at most $q$. For independent centered variance-one inputs with $p=\Pr(A)>0$ and $c=\mathbb E[L\mid A]$, $\begin{aligned} &\operatorname{Var}\bigl(\mathbb E[L+w\mid\mathcal O_+]\bigr)=q\\ &\quad +p\bigl(1-\operatorname{Var}(L\mid A)\bigr)=q\\ &\quad +\Delta_b+p(c-b)^2 . \end{aligned}$ Hence $\mathcal O_+$ satisfies the amplification criterion with $(r,d,\eta)=(m+2,m+1,p_*/2)$.

Proof. An off output fixes the $q$ original inputs and ignores $w$; an on output has indicator $\mathbf 1_A(\mathbf z)\mathbf 1_{\{w=w_0\}}$, which by (2.1) is a combination of functions of $m+1=q$ inputs. The conditional mean of $L+w$ is $L$ off $A$ and $c+w$ on $A$, so its second moment $\mathbb E[\mathbf 1_{A^c}L^2]+p(c^2+1)$ equals $q-p\operatorname{Var}(L\mid A)+p$; and $\Delta_b=p-p\bigl(\operatorname{Var}(L\mid A)+(c-b)^2\bigr)$. For asymptotically normal finite-valued inputs, Lemma 4.1 gives $\Delta_b>p_*/2$ for large $n$, hence $p>0$ and a variance above $q+p_*/2$. $\square$

6. Exercises

6.1. Verify identity (2.1) at a point where $u\in U_2$, $z_2\notin I_2$ and all other leaves pass, and at a point where two leaves fail.

6.2. Show that revealing any $m$ of $m+1$ independent centered variance-one inputs retains variance exactly $m$, and that no report can retain more than $m+1$.

6.3. Why must $\eta$ in Proposition 1.2 be fixed independently of the stage? What would go wrong if the margin $\eta_k$ at stage $k$ satisfied $\sum_k\eta_k/d<\infty$?

6.4. In Lemma 3.1, why is the shift by one in $b=\sum_j\mu_j-1$ essential? Compute $d_A$ if $b$ were $\sum_j\mu_j$.

7. Solutions

6.1. At the first point, the sum in (2.1) has the single nonzero term $i=2$, equal to $1$ (all leaves $j\ne2$ pass), and the product over all leaves is $0$, so $\mathbf 1_A=1$: only the selected leaf fails. If two leaves fail, every term of the sum and the product vanish: $P$ fails for every selection.

6.2. Revealing all inputs but $z_k$ gives $\mathbb E[L\mid\cdot]=L-z_k$, with variance $m$. Any conditional expectation has variance at most $\operatorname{Var}L=m+1$.

6.3. Each stage multiplies the ratio by $1+\eta_k/d$; the product of these factors is infinite exactly when $\sum_k\eta_k=\infty$. With a fixed $\eta$, finitely many stages exceed any ratio; with summable margins the ratio would stay bounded.

6.4. With $b'=\sum_j\mu_j$, the mean of $L-b'$ given $u=t$ and $P$ is $t-\mu_i+\sum_{j\ne i}\mu_j-\sum_{j\ne i}\mu_j=t-\mu_{\iota(t)}$, and on $B$ it is $0$; the same computation gives $d_A=p_*(1+S-J')-p_*$ with $J'$ defined from $t-\mu_{\iota(t)}$, and the positive constant $1$ disappears: $d_A=p_*(S-J')\le p_*S$, too small. The shift makes the mean on $B$ equal to $1$, and subtracting the $B$ term turns its square into the gain.

References

[OpenAI-SR] OpenAI, Unbounded violations of the square-root degree bound, OpenAI Math Release preprint, 26 September 2026. https://github.com/openai/math/blob/main/preprints/Unbounded-Violations-of-the-Square-Root-Degree-Bound-September-26-2026/paper.pdf

event	report
\(A\)	the tag \(A\) only
\(B\)	\((B,z_1,\dots,z_m)\)
\(P^c\)	\((P^c,u,\iota(u),(z_j)_{j\ne\iota(u)})\)