==== TABLE OF CONTENTS ====
Unbounded-Violations-of-the-Square-Root-Degree-Bound//bibliography.tex
Unbounded-Violations-of-the-Square-Root-Degree-Bound//main.tex
Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/00-introduction.tex
Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/01-observations.tex
Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/02-reporting.tex
Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/03-alternatives.tex
Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/04-mean-cost.tex
Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/05-weighted.tex
Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/06-small-width.tex
===========================
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//bibliography.tex ====
\begin{thebibliography}{9}
\bibitem{BlaisTanWan}
E. Blais, L.-Y. Tan, and A. Wan,
\emph{An inequality for the Fourier spectrum of parity decision trees},
arXiv:1506.01055v1 (2015).
\url{https://arxiv.org/abs/1506.01055v1}.
\bibitem{Durrett}
R. Durrett, \emph{Probability: Theory and Examples}, fifth edition,
Cambridge University Press, 2019.
Author's Version~5, January~11, 2019,
\url{https://sites.math.duke.edu/~rtd/PTE/PTE5_011119.pdf}.
\bibitem{FHKL}
Y. Filmus, H. Hatami, N. Keller, and N. Lifshitz,
On the sum of the $L_1$ influences of bounded functions,
\emph{Israel Journal of Mathematics} \textbf{214} (2016), 167--192.
\url{https://doi.org/10.1007/s11856-016-1355-0}.
Preprint version: arXiv:1404.3396v3 (2015),
\url{https://arxiv.org/abs/1404.3396v3}.
\bibitem{Jha}
S. K. Jha, \emph{On the Sum of Linear Coefficients of a Boolean Valued
Function}, arXiv:1611.01029v2 (2016).
\url{https://arxiv.org/abs/1611.01029v2}.
\bibitem{KudinPasalic}
S. Kudin and E. Pa\v{s}ali\'c,
Proving the conjecture of O'Donnell in certain cases and disproving
its general validity,
\emph{Discrete Applied Mathematics} \textbf{289} (2021), 345--353.
\url{https://doi.org/10.1016/j.dam.2020.11.005}.
\bibitem{NisanSzegedy}
N. Nisan and M. Szegedy,
On the degree of Boolean functions as real polynomials,
\emph{Computational Complexity} \textbf{4} (1994), 301--313.
\url{https://doi.org/10.1007/BF01263419}.
\bibitem{ODonnell}
R. O'Donnell, \emph{Open Problems in Analysis of Boolean Functions},
arXiv:1204.6447v1 (2012), p.~9.
\url{https://arxiv.org/abs/1204.6447v1}.
\bibitem{ODonnellServedio}
R. O'Donnell and R. A. Servedio,
Learning monotone decision trees in polynomial time,
\emph{SIAM Journal on Computing} \textbf{37} (2007), 827--844.
\url{https://doi.org/10.1137/060669309}.
\bibitem{Wang}
Q. Wang, \emph{On a Conjecture of O'Donnell},
Cryptology ePrint Archive, Report 2020/002 (2020).
\url{https://eprint.iacr.org/2020/002}.
\end{thebibliography}
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//bibliography.tex ====
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//main.tex ====
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{booktabs,microtype}
\usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\hypersetup{pdftitle={Unbounded Violations of the Square-Root Degree Bound},pdfauthor={OpenAI}}
\newcommand{\E}{\mathbb E}
\newcommand{\Pp}{\mathbb P}
\newcommand{\R}{\mathbb R}
\newcommand{\one}{\mathbf 1}
\DeclareMathOperator{\Var}{Var}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\title{Unbounded Violations of the Square-Root Degree Bound}
\author{OpenAI}
\date{September 26, 2026}
\pdfinfoomitdate=1
\pdftrailerid{}
\begin{document}
\maketitle
\begin{abstract}
We disprove the Gopalan--Servedio square-root conjecture, even up to an
arbitrary constant factor. For every real \(C>0\), there is a nonconstant
Boolean function \(f:\{-1,1\}^n\to\{-1,1\}\) on a finite sign cube such that
\[
\sum_{i=1}^n \widehat f(\{i\})>C\sqrt{\deg(f)}.
\]
Here \(\widehat f(\{i\})\) is the linear Fourier coefficient associated with
the \(i\)th input, and \(\deg(f)\) is the degree of the real multilinear
polynomial representing \(f\).
\end{abstract}
\input{sections/00-introduction}
\input{sections/01-observations}
\input{sections/02-reporting}
\input{sections/03-alternatives}
\input{sections/04-mean-cost}
\appendix
\input{sections/05-weighted}
\input{sections/06-small-width}
\input{bibliography}
\end{document}
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//main.tex ====
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/00-introduction.tex ====
\section{Introduction}
The sum of the linear Fourier coefficients of a Boolean function measures
its correlation with the sum of its inputs. For a real-valued function
\(f:\{-1,1\}^n\to\mathbb R\), with \(X\) uniform on the sign cube,
write
\[
\widehat f(S)=\E\!\left[f(X)\prod_{i\in S}X_i\right],
\qquad \deg(f)=\max\{|S|:\widehat f(S)\ne0\}.
\]
Constants have degree zero. This is the degree of the real multilinear
polynomial representing \(f\), as in the work of Nisan and
Szegedy~\cite{NisanSzegedy}. 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.
\]
Gopalan and Servedio conjectured that \(\sqrt{\deg(f)}\) could replace
\(\sqrt n\); see O'Donnell's problem list~\cite[p.~9]{ODonnell}.
We show that no constant multiple of this proposed bound holds.
\begin{theorem}\label{thm:main}
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)}.
\]
Consequently,
\[
\sup_{\substack{n\ge1,\ f:\{-1,1\}^n\to\{-1,1\}\\\deg(f)>0}}
\frac{\sum_i|\widehat f(\{i\})|}{\sqrt{\deg(f)}}=\infty.
\]
\end{theorem}
The universal signed and absolute versions of the conjecture are
equivalent. Indeed, the coordinate change
\(x_i\mapsto\operatorname{sign}(\widehat f(\{i\}))x_i\), with sign
\(+1\) at zero, preserves degree and makes every linear coefficient
nonnegative. Our construction produces a large signed sum directly.
The dimension and all copy counts in the
construction are finite; we do not obtain useful bounds on their growth.
\subsection*{The square-root and majority bounds}
The conjecture is attributed to Gopalan and Servedio, circa 2009, in
O'Donnell's problem list. It also appears as Conjecture 3.17 in the
preprint of Filmus, Hatami, Keller and Lifshitz~\cite{FHKL}.
Here the singleton coefficients are summed linearly, rather than squared.
A sharper proposal in the same problem list uses the majority benchmark
\[
B_d=\E|X_1+\cdots+X_d|\le\sqrt d.
\]
This is the signed singleton sum of majority on \(d\) bits, with either
fixed value at ties. Replacing \(\sqrt{\deg(f)}\) by
\(B_{\deg(f)}\) gives a stronger inequality, so a counterexample to
that inequality need not violate the square-root bound.
Jha~\cite[Theorem 2.1]{Jha} gave discrete-derivative reformulations of
the majority proposal. Wang~\cite[Theorems 2.2, 3.2 and 3.6]{Wang}
gave another equivalent formulation and proved the cases \(d=1\) and
\(d=n-1\). Kudin and Pa\v{s}ali\'c~\cite{KudinPasalic} proved the
cases \(d=2,3\) and refuted the majority bound at \(d=4\).
Theorem~\ref{thm:main} excludes every constant multiple of the weaker
square-root bound. Stating both inequalities explicitly distinguishes
the questions despite the different names used for them in the literature.
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.
The discrete derivative in coordinate \(i\), defined as half the
difference between the values with that coordinate set to \(+1\) and
\(-1\), takes values in \(\{-1,0,1\}\). Its mean is
\(\widehat f(\{i\})\), so the absolute value of this mean is at most
its second moment, \(\operatorname{Inf}_i(f)\). The Fourier formula
for total influence and Parseval's identity therefore give
\cite[Lemma~2.4 and Corollary~2.5]{NisanSzegedy}
\[
\sum_i|\widehat f(\{i\})|
\le I(f)=\sum_{S\subseteq[n]}|S|\widehat f(S)^2
\le\deg(f).
\]
Theorem~\ref{thm:main} thus separates the conjectured square-root
scale from this surviving linear bound.
\subsection*{Retaining variance with low-degree observations}
Instead of constructing \(f\) immediately, we first construct a
finite-valued observation \(F\) of independent signs. If
\(H_N=X_1+\cdots+X_N\), the information that \(F\) retains about this
sum is measured by
\[
T_F=\E[H_N\mid F],\qquad v(F)=\E T_F^2.
\]
We call \(T_F\) the \emph{score} of \(F\) and \(v(F)\) its retained
variance. When \(v(F)>0\), its standardized score is
\(T_F/\sqrt{v(F)}\). We call a positive real number \(D\) a \emph{cell degree bound} if
every output indicator \(\one_{\{F=a\}}\) has degree at most \(D\). Every function of
\(F\) then has degree at most \(D\), including
\(f=\operatorname{sign}(T_F)\). This readout has correlation
\(\E[fH_N]=\E|T_F|\). Averaging independent copies makes its score
approximately Gaussian, so a large ratio \(v(F)/D\) gives the theorem.
Conditional coordinate sums also appear in decision-tree inequalities.
A subcube is obtained by fixing some coordinates. If the cells of
\(F\) are subcubes, the unfixed coordinates remain independent uniform
signs under conditioning, so \(v(F)\) equals the expected number of
fixed coordinates. O'Donnell and Servedio~\cite[Theorem~3 and
Lemma~3]{ODonnellServedio} bound the signed singleton sum of a Boolean
readout by the square root of this expectation. Blais, Tan and
Wan~\cite[Lemma~3.1 and Theorem~1]{BlaisTanWan} use the conditional
coordinate sum to prove square-root bounds in parity decision-tree
depth, where a query reveals the product of a specified set of inputs.
Our cells need not be subcubes: their indicators are controlled by
polynomial degree, and cancellation allows retained variance to exceed
that degree cost.
The main construction repeatedly increases this ratio. Revealing
\(m\) independent standardized scores retains variance \(m\). We use
\(m+1\) scores and design an observation retaining strictly more than
\(m\) units of variance, although each output indicator is a linear
combination of functions of at most \(m\) inputs. Such an indicator may
depend on all \(m+1\) inputs: the degree saving comes from cancellation,
not from ignoring a fixed coordinate.
Here is the reporting rule behind the gain. One score selects a leaf
among the remaining \(m\) scores, each of which has a short prescribed
interval. Usually we report all but one score. On the exceptional event
that only the selected leaf misses its interval, we report a single
tag. The intervals are chosen so that the sum of all the scores can be
predicted on this event with mean squared error less than one. Every
other report has residual error exactly one. Thus the exceptional tag
improves on the variance retained by revealing \(m\) scores.
Its indicator admits the required cancellation identity.
Section~\ref{sec:observations} proves the finite-observation calculus
and amplification criterion. Section~\ref{sec:observation} then
explains the reports and their
prediction error before choosing the Gaussian intervals. Once that
choice is fixed, the central limit theorem supplies a sufficiently large
finite average at each step. A finite number of steps gives any
prescribed ratio, and a final sign readout proves the theorem. Thus
Sections~\ref{sec:observations} and~\ref{sec:observation} contain a
complete proof of Theorem~\ref{thm:main}.
The further constructions distinguish which features of this rule are
needed for a gain. In Section~\ref{sec:alternatives}, the \emph{coarse
report} shows that the all-leaves-pass values can also be replaced by
one tag; switching to an extra independent score isolates the
conditional-variance saving on the exceptional event.
Section~\ref{sec:mean-cost} allows different degree costs for different
outputs: retained variance need only exceed their \emph{average} cost.
Reporting typical words of outputs and merging the remaining words into
one cell then gives a degree bound valid everywhere while retaining
almost all the variance.
Appendix~\ref{app:weighted-mixture} supplies an independent Gaussian
event for the average-cost criterion. Appendix~\ref{app:small-width}
gives a different Gaussian parameter schedule for the coarse report,
together with the transfer argument for its law-dependent coefficients.
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/00-introduction.tex ====
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/01-observations.tex ====
\section{Finite observations and amplification}\label{sec:observations}
We first justify the degree and conditioning identities used by every
construction. Throughout, \(F\) is a finite-valued observation,
\(T_F=\E[H_N\mid F]\) is its centered score, and \(D>0\) is a cell
degree bound. The bound \(D\) may be real; it need not equal the actual
integer degree of any indicator.
Every real function of \(F\) has degree at most \(D\), by expansion in
its finitely many value indicators. Unused labels have zero indicators.
If distinct observation labels produce the same numerical score, their
indicators add, so score collisions preserve the same bound. A function of \(r\) observations on
disjoint blocks, with bounds \(D_1,\ldots,D_r\), has degree at most
\(\sum_iD_i\). Indeed, it expands in products of their indicators, and
the degree of a product is at most the sum of the degrees: multiplication
of Fourier characters takes symmetric differences of their index sets.
Let \(F_1,\ldots,F_r\) be independent observations on disjoint bit
blocks, with scores \(T_1,\ldots,T_r\), and let \(H_{\mathrm{tot}}\)
be the total bit sum. Conditioning on their tuple gives
\(\E[H_{\mathrm{tot}}\mid F_1,\ldots,F_r]=\sum_iT_i\).
For any observation \(Q\) that is a function of this tuple, the tower
property therefore gives
\[
\E[H_{\mathrm{tot}}\mid Q]=\E\!\left[\sum_iT_i\,\middle|\,Q\right].
\]
These are instances of the conditional-expectation projection identities;
see~\cite[Theorems~4.1.13 and 4.1.15]{Durrett}. In particular, for
\(v=v(F)>0\), the numerical observation
\begin{equation}\label{eq:averaging}
Z_M=\frac{T_1+\cdots+T_M}{\sqrt{Mv}}
\end{equation}
formed from \(M\) independent copies has cell degree bound \(MD\), and
its score is exactly \(\sqrt{Mv}\,Z_M\).
The classical i.i.d.\ central limit theorem~\cite[Theorem~3.4.1]{Durrett} gives
\(Z_M\Rightarrow G\), where \(G\) is standard normal. For each fixed
initial \(F\), all moments are finite, and
\begin{equation}\label{eq:fourth}
\E Z_M^4=\frac{\E T_F^4}{Mv^2}+3\frac{M-1}{M}.
\end{equation}
Thus the fourth moments are bounded uniformly in \(M\) for this fixed
observation. The bound may change when a later amplification stage
uses a different observation.
All citations to probability results refer to the January 11, 2019 author
version of Durrett~\cite{Durrett}.
\begin{lemma}[Transfer of predictor errors]\label{lem:transfer}
Let \(Z_j\) be centered, variance-one random variables converging in
distribution to a standard normal, with \(\sup_j\E Z_j^4<\infty\).
For fixed \(r\), let \(\mathbf Z_j\) consist of \(r\) independent copies
of \(Z_j\), and let \(\mathbf G\) consist of \(r\) independent standard
normals. If \(g:\R^r\to\R\) is measurable, its discontinuities have
Gaussian measure zero, and
\[
|g(z)|\le K\left(1+\sum_{i=1}^r z_i^2\right)
\]
for some fixed \(K\), then \(\E g(\mathbf Z_j)\to\E g(\mathbf G)\).
\end{lemma}
\begin{proof}
Independence gives joint weak convergence. Clipping \(g\) to a bounded
range gives convergence of expectations by the null-discontinuity
criterion for weak convergence~\cite[Theorem~3.10.1(vi)]{Durrett}.
The fourth-moment bound and fixed \(r\)
give \(\sup_j\E[g(\mathbf Z_j)^2]<\infty\), so the clipping errors in
first moment tend to zero uniformly; this is the higher-moment
criterion for uniform integrability~\cite[Theorem~4.6.2]{Durrett}.
The Gaussian error does also.
\end{proof}
\begin{lemma}[Boolean readout]\label{lem:readout}
Suppose finite observations have positive cell degree bounds \(D\) and
arbitrarily large ratios \(v(F)/D\). Then Theorem~\ref{thm:main} holds.
\end{lemma}
\begin{proof}
Fix \(C>0\) and choose \(F\) with \(v(F)>4C^2D\).
For \(M\) independent copies, define
\(f=\operatorname{sign}(T_1+\cdots+T_M)\), with sign \(1\) at zero.
Its degree is at most \(MD\). Conditioning on the tuple of observations,
\[
\sum_i\widehat f(\{i\})
=\E[fH_{MN}]
=\E|T_1+\cdots+T_M|
=\sqrt{Mv(F)}\,\E|Z_M|.
\]
The central limit theorem and the uniform second-moment bound imply
\(\E|Z_M|\to\E|G|=\sqrt{2/\pi}>1/2\).
For a sufficiently large finite \(M\), the displayed sum exceeds
\(C\sqrt{MD}\ge C\sqrt{\deg(f)}\). It is positive, so \(f\) is
nonconstant.
\end{proof}
\begin{proposition}[Amplification criterion]\label{prop:amplification}
Let \(1\le d0\) such that, whenever centered variance-one
laws \(Z_j\) converge weakly to a standard normal with uniformly bounded
fourth moments, independent copies satisfy, for all sufficiently large \(j\),
\[
\Var\!\left(\E\!\left[\sum_{i=1}^r Z_{j,i}\,\middle|\,
\mathcal W(\mathbf Z_j)\right]\right)\ge d+\eta.
\]
\end{enumerate}
Then finite observations have arbitrarily large retained
variance-to-cell-degree ratios, and Theorem~\ref{thm:main} follows.
\end{proposition}
\begin{proof}
Fix a finite observation \(F\) with \(v=v(F)>0\) and degree bound \(D>0\).
Form \(r\) independent blocks of \(M\) copies of \(F\), and apply
\(\mathcal W\) to their normalized scores from \eqref{eq:averaging}.
The new observation \(F'\) has finite range. Its cell degree is at most
\(dMD\) by the first assumption and expansion in value indicators.
The second assumption applies by \eqref{eq:fourth}. For a sufficiently
large finite \(M\), the tower property therefore gives
\[
v(F')=Mv\,\Var\!\left(\E\!\left[\sum_{i=1}^rZ_{M,i}\mid F'\right]\right)
\ge Mv(d+\eta).
\]
The ratio increases by at least the fixed factor \(1+\eta/d>1\).
Start with the observation of one sign, for which \(v=D=1\), and
iterate. Each stage is finite and has its own sufficiently large finite
copy count. A finite number of stages exceeds any prescribed ratio.
Apply Lemma~\ref{lem:readout}.
\end{proof}
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/01-observations.tex ====
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/02-reporting.tex ====
\section{Retaining more variance than the degree cost}
\label{sec:observation}
We now construct the observation rule needed for amplification. Revealing
any fixed set of $m$ of $m+1$ independent centered variance-one inputs retains variance
$m$ from their sum: the unobserved input accounts for the remaining unit.
Our rule will retain strictly more than $m$, while every output indicator
is a linear combination of functions of at most $m$ inputs. These are
the two conclusions required by Proposition~\ref{prop:amplification},
with $r=m+1$ and $d=m$.
The rule usually leaves one input unobserved. On one specially chosen
event, it instead reports only that the event occurred. This improves
the prediction error if the sum of all the inputs is sufficiently close
to one fixed number on that event. We first describe the rule and
calculate its error for arbitrary independent inputs. We will then
choose its parameters using Gaussian inputs.
\subsection{A reporting rule and its prediction error}
Let $m\ge3$, let $I_1,\ldots,I_m$ be intervals, and let
$\iota:\mathbb R\to\{1,\ldots,m\}$ be a selector with finitely many
cut points. All endpoint and tie conventions are part of the rule.
Write its inputs as $(u,z_1,\ldots,z_m)$ and their sum as
$L=u+\sum_{j=1}^m z_j$. The coordinate $u$ selects the leaf
$z_{\iota(u)}$. Define
\[
B=\{z_j\in I_j\text{ for every }j\},\qquad
P=\{z_j\in I_j\text{ for every }j\ne\iota(u)\},\qquad
A=P\setminus B.
\]
Thus $A$ is the event that the selected leaf alone fails its interval
test. Since $B\subseteq P$, the sets $A$, $B$, and $P^c$ partition
the input space. Define the tagged observation $\mathcal W$ by
\[
\begin{array}{c|l}
\text{Event}&\text{Information reported}\\ \hline
A&\text{the tag }A\text{ only}\\
B&(B,z_1,\ldots,z_m)\\
P^c&(P^c,u,\iota(u),(z_j)_{j\ne\iota(u)}).
\end{array}
\]
On $B$, the central input is omitted. On $P^c$, the selected leaf
is omitted. Although the exceptional report on $A$ can depend on all
$m+1$ inputs, its indicator has the pointwise identity
\begin{equation}\label{eq:indicator}
\mathbf1_A=
\sum_{i=1}^m\mathbf1_{\{\iota(u)=i\}}
\prod_{j\ne i}\mathbf1_{I_j}(z_j)
-\prod_{j=1}^m\mathbf1_{I_j}(z_j).
\end{equation}
Each summand uses only $m$ coordinates. This cancellation is what
allows the exceptional report to have the same degree cost as the
ordinary reports.
\begin{lemma}\label{lem:report}
For every product of finite input alphabets, the rule $\mathcal W$
has finite range, and each output indicator is a finite linear
combination of functions of at most $m$ input coordinates.
For independent centered variance-one inputs, whose marginal laws need
not agree, and every fixed $b\in\mathbb R$, put
\[
\Delta_b=\mathbb E[\mathbf1_A(1-(L-b)^2)].
\]
Then
\begin{equation}\label{eq:retained}
\operatorname{Var}(\mathbb E[L\mid\mathcal W])\ge m+\Delta_b.
\end{equation}
\end{lemma}
\begin{proof}
Identity~\eqref{eq:indicator} gives the required decomposition
for the $A$ report. An attained $B$ report fixes the $m$ leaf values
and imposes no condition on $u$. An attained $P^c$ report fixes $u$,
its selected index $i$, and the $m-1$ unselected leaves. At least one
of these reported leaves fails its test; hence the reported values
already force $P^c$, whatever the omitted value $z_i$ may be. Its
indicator therefore depends on only the $m$ reported coordinates.
Unused output labels have zero indicators. This proves the first
assertion on every input, including interval endpoints.
To estimate the retained variance, 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 predictor is a function of the reported information. On $B$
its error is $u$; independence gives
$\mathbb E[\mathbf1_Bu^2]=\mathbb P(B)$.
For the last type of report, fix an index $i$ and let
$E_i=P^c\cap\{\iota(u)=i\}$. This event and its reported data
depend only on $u$ and the leaves other than $z_i$. Consequently
\[
\mathbb E[\mathbf1_{E_i}z_i]=0,
\qquad
\mathbb E[\mathbf1_{E_i}z_i^2]=\mathbb P(E_i).
\]
Summing the squared errors over the three types of report gives
\[
\mathbb P(A^c)+\mathbb E[\mathbf1_A(L-b)^2]=1-\Delta_b.
\]
Conditional expectation has no larger mean squared error
\cite[Theorems~4.1.13 and 4.1.15]{Durrett}. Since $L$ is centered and
$\operatorname{Var}(L)=m+1$, the conditional-variance identity gives
\eqref{eq:retained}.
\end{proof}
The remaining task is now precise: choose the intervals, selector, and
constant $b$ so that $\Delta_b>0$ for Gaussian inputs. A strict
positive margin will survive the normal approximation used in
amplification. The next calculation produces that margin by subtracting
the contribution of $B$ from that of $P$ in
\eqref{eq:indicator}.
\subsection{Choosing the intervals in the Gaussian model}
We will obtain a positive predictor deficit and also record the
conditional variance on $A$. The latter describes the event's gain
without specifying a predictor: on $A$, the sum varies less than one
unobserved variance-one input.
\begin{lemma}\label{lem:gaussian}
There are a finite odd integer $m\ge3$, closed intervals
$I_1,\ldots,I_m$, and a selector $\iota$ with finitely many cut points
such that the following holds for independent standard normal inputs.
Let $\beta_j$ be the probability of $I_j$, and let $\mu_j,s_j^2$ be
the conditional mean and variance on $I_j$. Define
\[
p_* =\prod_{j=1}^m\beta_j,\qquad
S=\sum_{j=1}^m s_j^2,\qquad
b=\sum_{j=1}^m\mu_j-1.
\]
Then $p_*>0$, $S<1/4$, and
\begin{equation}\label{eq:deficit}
d_A:=\mathbb E[\mathbf1_A(1-(L-b)^2)]>\frac34p_*.
\end{equation}
The boundary of $A$ lies in a finite union of coordinate hyperplanes.
In particular, $\mathbb P(A)>0$ and $\operatorname{Var}(L\mid A)<1$.
\end{lemma}
\begin{proof}
The shift by one in $b$ determines where to place the intervals.
Conditional on $u=t$ and $P$, the mean of $L-b$ is
$1+t-\mu_{\iota(t)}$, so selecting an interval near $1+t$ makes
this mean small. Conditional on $B$ alone, with $u$ still random,
its mean is instead one. Subtracting the contribution of $B$ will
turn that fixed squared mean into the positive term in $d_A$.
We let odd $m$ tend to infinity to choose the parameters, and then fix
one finite value. Set
\[
R=\sqrt{8\log m},\qquad h=m^{-3/2},\qquad
a_i=1-R+\frac{2R(i-1)}{m-1},\qquad I_i=[a_i-h,a_i+h].
\]
For $|t|\le R$, select a center $a_{\iota(t)}$ nearest to $1+t$,
resolving ties by the smaller index. For $|t|>R$, use the middle
index, whose center is $1$. These choices define the rule on the
whole real line. Its finitely many interval endpoints and selector
cut points also give the asserted boundary property.
Write $\phi(t)=(2\pi)^{-1/2}e^{-t^2/2}$. Every $\beta_i$ lies in
$(0,1)$. Condition first on $u=t$ and put $i=\iota(t)$. The event
$P$ then has probability $p_*/\beta_i$; it restricts the leaves
$j\ne i$ to their intervals and leaves $z_i$ unrestricted. Under
this conditioning, $L-b$ has mean $1+t-\mu_i$ and variance
$1+\sum_{j\ne i}s_j^2$. Thus
\[
\mathbb E[\mathbf1_P(1-(L-b)^2)]=-p_*J,
\qquad
J=\int_{\mathbb R}
\left((1+t-\mu_{\iota(t)})^2+
\sum_{j\ne\iota(t)}s_j^2\right)
\frac{\phi(t)}{\beta_{\iota(t)}}\,dt.
\]
On $B$, with $u$ again random, $L-b$ has mean $1$ and variance
$1+S$. Therefore
\[
\mathbb E[\mathbf1_B(1-(L-b)^2)]=-p_*(1+S).
\]
Since $\mathbf1_A=\mathbf1_P-\mathbf1_B$, we obtain the exact identity
\begin{equation}\label{eq:gaussian-identity}
d_A=p_*(1+S-J).
\end{equation}
The positive constant $1$ comes from the mean of $L-b$ on $B$.
It remains to make the nonnegative error $J$ small. Nearest-center
selection controls its central part; the fallback to the middle
interval controls the tails.
The elementary interval estimates are
\[
|\mu_i-a_i|\le h,\qquad s_i^2\le h^2,\qquad
\beta_i\ge 2h(2\pi)^{-1/2}
\exp\!\left(-\frac{(|a_i|+h)^2}{2}\right).
\]
For $|t|\le R$, the grid spacing and the selector give
\[
|1+t-\mu_{\iota(t)}|\le\frac{R}{m-1}+h,
\qquad |a_{\iota(t)}|+h\le |t|+2
\]
when $m$ is sufficiently large. Hence
$\phi(t)/\beta_{\iota(t)}\le(e^2/2h)e^{2R}$ on this range, and
\begin{align*}
J_{\mathrm{central}}
&\le\frac{e^2R}{h}e^{2R}
\left(\left(\frac{R}{m-1}+h\right)^2+mh^2\right)\\
&=O\!\left(R(R^2+1)e^{2R}m^{-1/2}\right)=o(1).
\end{align*}
Here $e^{2R}=m^{o(1)}$, while $R$ is a power of $\log m$.
On $|t|>R$, the selected interval is centered at $1$. For $h\le1$
its probability is at least $2h\phi(2)$, and the numerator in $J$
is $O(1+t^2)$. Integration by parts gives
\[
\int_{|t|>R}(1+t^2)\phi(t)\,dt
=O((R+1)e^{-R^2/2}).
\]
Consequently
\[
J_{\mathrm{tail}}
=O(h^{-1}(R+1)e^{-R^2/2})
=O((R+1)m^{-5/2})=o(1).
\]
Also $S\le mh^2=m^{-2}\to0$. Fix a sufficiently large finite odd
$m$ so that $J<1/4$ and $S<1/4$. Identity~\eqref{eq:gaussian-identity}
now proves \eqref{eq:deficit}, with $p_*>0$.
Finally, write $p_A=\mathbb P(A)$. Since $d_A>0$, we have $p_A>0$,
and
\[
d_A=p_A\bigl(1-\operatorname{Var}(L\mid A)
-(\mathbb E[L\mid A]-b)^2\bigr)>0.
\]
This also proves $\operatorname{Var}(L\mid A)<1$.
\end{proof}
\subsection{Transfer to finite inputs and amplification}
Fix all the Gaussian choices from Lemma~\ref{lem:gaussian},
including $m$, the intervals, the selector, $b$, and $p_*>0$.
Set $\eta=p_*/2$. If centered variance-one laws $Z_n$ converge
weakly to a standard normal and have uniformly bounded fourth moments,
apply Lemma~\ref{lem:transfer} to the fixed function
\[
g(u,z_1,\ldots,z_m)=\mathbf1_A(1-(L-b)^2).
\]
It has quadratic growth and discontinuities only on the finitely many
hyperplanes from Lemma~\ref{lem:gaussian}; these have Gaussian
measure zero. For independent copies of $Z_n$, therefore,
$\mathbb Eg\to d_A>3p_*/4$, and eventually $\mathbb Eg>\eta$.
Lemma~\ref{lem:report} then gives
\[
\operatorname{Var}\!\left(
\mathbb E\!\left[\sum_{i=1}^{m+1} Z_{n,i}
\,\middle|\,\mathcal W(\mathbf Z_n)\right]\right)
>m+\eta.
\]
Together with the pointwise output-indicator decomposition in that
lemma, this verifies both hypotheses of
Proposition~\ref{prop:amplification} with
$(r,d,\eta)=(m+1,m,p_*/2)$.
The Gaussian parameters and $\eta$ remain fixed throughout the iteration.
Proposition~\ref{prop:amplification} therefore increases the ratio of
retained variance to cell degree bound by at least $1+\eta/m>1$ at
each stage, using a sufficiently large finite copy count chosen for the
current observation. Starting from one revealed sign, finitely many
stages make this ratio exceed $4C^2$ for any prescribed $C>0$.
Lemma~\ref{lem:readout} then supplies a nonconstant Boolean function
with signed singleton sum greater than $C\sqrt{\deg(f)}$, proving
Theorem~\ref{thm:main}.
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/02-reporting.tex ====
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/03-alternatives.tex ====
\section{Two other reporting rules}\label{sec:alternatives}
The report in Section~\ref{sec:observation}, which we call the
\emph{refined report}, keeps every leaf value when all the leaves pass
their tests. We now ask what happens if that information is replaced by one
mark. The resulting loss can be computed exactly and is smaller than
the Gaussian gain. A second rule uses one additional independent input:
it reveals the original inputs off the exceptional event and the extra
input on that event. The first modification shows that the all-pass
leaf values are dispensable; the second isolates the conditional-variance
saving on the exceptional event.
\subsection{Merging the all-leaves-pass reports}\label{subsec:coarse-mark}
Start with any integer $m\ge3$, intervals $I_1,\ldots,I_m$, and a
selector $\iota:\R\to\{1,\ldots,m\}$ with finitely many cut points.
Fix all endpoint and tie conventions. As before, on inputs
$(u,z_1,\ldots,z_m)$ put
\[
L=u+\sum_{j=1}^m z_j,\qquad
B=\{z_j\in I_j\text{ for every }j\},
\]
\[
P=\{z_j\in I_j\text{ for }j\ne\iota(u)\},\qquad
A=P\setminus B.
\]
Define the \emph{coarse report} $\mathcal O$ by
\[
\begin{array}{c|l}
\text{Event}&\text{Information reported}\\ \hline
A&\text{the mark }X\\
B&\text{the mark }Y\\
P^c&(O,u,\iota(u),(z_j)_{j\ne\iota(u)}).
\end{array}
\]
The marks $X,Y$ and the ordinary-report tag $O$ are distinct. The rule
differs from the refined report only on $B$. The next lemma separates
its pointwise cost from the choice of an input law, so that other
interval constructions can use the same reporting rule.
\begin{lemma}[Cost and error of the coarse report]\label{lem:coarse-report}
On every product of finite input alphabets, $\mathcal O$ has finite
range, and each output indicator is a finite linear combination of
functions of at most $m$ input coordinates.
Let the inputs be independent, centered, and of variance one; their
marginal laws need not agree. For any fixed constants $b_0,b_1\in\R$,
define
\begin{equation}\label{eq:coarse-deficit}
g_{b_0,b_1}
=\one_A\bigl(1-(L-b_0)^2\bigr)
+\one_B\bigl(1-(L-b_1)^2\bigr).
\end{equation}
Then the optimal residual error
$\mathcal R=\E[(L-\E[L\mid\mathcal O])^2]$ satisfies
\begin{equation}\label{eq:coarse-residual}
1-\mathcal R\ge\E g_{b_0,b_1},\qquad
\Var(\E[L\mid\mathcal O])\ge m+\E g_{b_0,b_1}.
\end{equation}
\end{lemma}
\begin{proof}
The $X$ indicator has the pointwise expansion \eqref{eq:indicator}.
The $Y$ indicator depends only on the $m$ leaves. An ordinary output
specifies $u$, its selected index $i$, and the $m-1$ unselected leaf
values. If these data are attained, one of the reported leaves fails
its interval test. They therefore force $P^c$ for every value of the
omitted leaf $z_i$, so the indicator uses just the $m$ reported inputs.
An inconsistent or unattained output label has zero indicator. Thus
the assertion holds pointwise, including endpoints and selector ties.
Predict $L$ by $b_0$ on $X$, by $b_1$ on $Y$, and by
$u+\sum_{j\ne\iota(u)}z_j$ on an ordinary report. For each fixed
$i$, the event $E_i=P^c\cap\{\iota(u)=i\}$ and all its reported data
depend only on $u$ and the leaves other than $z_i$. Independence gives
\[
\E[\one_{E_i}z_i]=0,\qquad
\E[\one_{E_i}z_i^2]=\Pp(E_i).
\]
The ordinary reports consequently contribute exactly $\Pp(P^c)$ to
the squared prediction error. The total error of this predictor is
\[
\Pp(P^c)+\E[\one_A(L-b_0)^2]+\E[\one_B(L-b_1)^2]
=1-\E g_{b_0,b_1}.
\]
Conditional expectation minimizes squared error, proving the first
inequality in \eqref{eq:coarse-residual}. The second follows because
$L$ is centered with variance $m+1$.
\end{proof}
Now fix the Gaussian intervals and selector from
Lemma~\ref{lem:gaussian}. Write
\[
M_\mu=\sum_{j=1}^m\mu_j,\qquad b=M_\mu-1,\qquad
p_*=\Pp(B)>0,\qquad S=\sum_{j=1}^m s_j^2.
\]
The Gaussian calculation gave
$d_A=\E[\one_A(1-(L-b)^2)]=p_*(1+S-J)$ with $J<1/4$.
In Lemma~\ref{lem:coarse-report} take $b_0=b$ and $b_1=M_\mu$.
On $B$, the central Gaussian remains unrestricted and the leaves are
independently restricted to their intervals. Thus $L-M_\mu$ has
conditional mean zero and variance $1+S$, giving
\begin{equation}\label{eq:coarse-gaussian-gain}
\E g_{b,M_\mu}=d_A-p_*S=p_*(1-J)>\frac34p_*.
\end{equation}
The term $p_*S$ is precisely the added error on $B$: the refined
predictor had error $u$ there, while merging its reports leaves the
conditional leaf variance $S$ unobserved. Equation
\eqref{eq:coarse-gaussian-gain} is an identity for this predictor's
gain; \eqref{eq:coarse-residual} is the resulting lower bound for
optimal retained variance.
All these Gaussian choices are now fixed. Let centered variance-one
laws $Z_n$ converge weakly to a standard normal with uniformly bounded
fourth moments, and take $m+1$ independent copies as inputs. The fixed
function $g_{b,M_\mu}$ has quadratic growth; its discontinuities lie
on the finitely many interval and selector hyperplanes.
Lemma~\ref{lem:transfer} and \eqref{eq:coarse-gaussian-gain} imply
that eventually $\E g_{b,M_\mu}>\eta$, where $\eta=p_*/2>0$.
Lemma~\ref{lem:coarse-report} then gives retained variance greater
than $m+\eta$ and the required pointwise cell cost. Therefore
Proposition~\ref{prop:amplification} applies with
\[
(r,d,\eta)=(m+1,m,p_*/2).
\]
This criterion and Lemma~\ref{lem:readout} give
Theorem~\ref{thm:main} by the coarse rule as well.
\subsection{Switching to an independent score}\label{subsec:extra-block}
Keep the fixed Gaussian event $A$ and predictor $b$ above, and put
$q=m+1$. Add one independent centered variance-one input $w$ to the
original tuple $\mathbf z=(u,z_1,\ldots,z_m)$. Define
\[
\mathcal O_+(\mathbf z,w)=
\begin{cases}
(\mathrm{off},\mathbf z),&\mathbf z\notin A,\\
(\mathrm{on},w),&\mathbf z\in A.
\end{cases}
\]
Off $A$ the original sum $L$ is known and $w$ is omitted. On $A$
the extra input is known and the original sum must be predicted.
The rule gains variance whenever the conditional variance of $L$ on
$A$ is smaller than the one unit of residual variance of $w$.
This rule has $q+1$ inputs but cell cost at most $q$. Indeed, an
off-$A$ output fixes the first $q$ inputs and places no condition on
$w$. The indicator of an on-$A$ output $(\mathrm{on},w_0)$ is
\[
\one_A(\mathbf z)\one_{\{w=w_0\}}.
\]
Multiplying \eqref{eq:indicator} by the last value test expresses
this indicator as a sum of functions of at most $m+1=q$ inputs.
The tags keep the two types of report separate, and unattained labels
have zero indicators. These pointwise expansions also cover the
prescribed endpoints and ties. The rule has finite range on every
finite product alphabet.
To establish a gain for the approximating laws, first transfer the
unconditional deficit, before conditioning on $A$. For independent
copies of any centered variance-one law $Z_n$ tending to a standard
normal with uniformly bounded fourth moments, Lemma~\ref{lem:transfer} gives
\[
\Delta_{b,n}:=\E[\one_A(1-(L-b)^2)]
\longrightarrow d_A>\frac34p_*.
\]
Thus, for all sufficiently large $n$, $\Delta_{b,n}>\eta=p_*/2$.
Since $\Delta_{b,n}\le\Pp(A)$, these laws have positive probability
of $A$. Only now fix such an $n$, write $\Delta_b=\Delta_{b,n}$, and define
\[
p=\Pp(A)>0,\qquad c=\E[L\mid A].
\]
Independence of $w$ from the original tuple shows that
$\E[L+w\mid\mathcal O_+]$ equals $L$ off $A$ and $c+w$ on $A$.
The sum $L+w$ is centered, so its conditional mean is centered too.
Using $\E w=0$, $\E w^2=1$, and $\E L^2=q$ gives the exact identity
\begin{align}
\Var(\E[L+w\mid\mathcal O_+])
&=\E[\one_{A^c}L^2]+p(c^2+1)\notag\\
&=q+p\bigl(1-\Var(L\mid A)\bigr).
\label{eq:switching-variance}
\end{align}
The same input law satisfies
\begin{equation}\label{eq:switching-correction}
p\bigl(1-\Var(L\mid A)\bigr)
=\Delta_b+p(c-b)^2>\eta.
\end{equation}
The identities in \eqref{eq:switching-variance} and the equality in
\eqref{eq:switching-correction} hold more generally for any independent
centered variance-one original inputs and an independent centered
variance-one $w$, whenever $p>0$, with
$\Delta_b=\E[\one_A(1-(L-b)^2)]$. Their marginal laws need not agree.
The nonnegative correction $p(c-b)^2$ records the improvement from
the fixed Gaussian predictor $b$ to the actual conditional mean $c$.
For the fixed approximating law, \eqref{eq:switching-variance}
therefore exceeds $q+\eta$.
This argument uses convergence of one fixed predictor error, not
continuity of conditional variances.
The pointwise cost and the transferred gain verify
Proposition~\ref{prop:amplification} with the distinct triple
\[
(r,d,\eta)=(m+2,m+1,p_*/2).
\]
The criterion again proves Theorem~\ref{thm:main}, with ratio
multiplier at least $1+\eta/(m+1)>1$. For both rules in this section,
the Gaussian parameters and $\eta$ stay fixed throughout. Each stage
starts from one fixed finite observation and chooses its own finite
averaging count; the fourth-moment bound is uniform in that count,
not across all stages.
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/03-alternatives.tex ====
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/04-mean-cost.tex ====
\section{Amplifying an average degree saving}\label{sec:mean-cost}
A finite observation can have some inexpensive outputs and some expensive
ones. We now convert an average degree saving into a bound valid on every
input. Apply the observation independently many times, retain output
words whose total cost is controlled, and merge all other words into one
label. The indicator of the merged cell is the complement of the retained
indicators. Its degree therefore satisfies the same bound, even if
individual discarded words do not.
This operation must also retain enough variance and restore the normal
approximation needed to repeat it. We use the score $T_F$, retained
variance $v(F)$, and pointwise cell-degree calculus of
Section~\ref{sec:observations}. The new ingredient is a separate cost for
each output label. These costs measure degrees of indicator expansions,
not the number of queries required to determine an output.
\subsection{From a variance saving to an average cost saving}
\label{sec:refinement-first}
Let $q\ge2$ be an integer, and let
$\mathcal P:\R^q\to\mathcal L$ be a measurable map to a finite label
set. Give label $l$ an integer cost $\ell(l)\in\{1,\ldots,q\}$.
The relevant algebraic requirement is that, on every product of finite
input alphabets, the cell indicator for $l$ is a finite linear
combination of functions each depending on at most $\ell(l)$ input
coordinates. The indicator itself need not depend on only that many
coordinates. When the inputs are scores of observations with cell
degree bound $D$, this requirement bounds the degree of the output
cell by $D\ell(l)$.
Suppose now that a Gaussian construction supplies an event $A$ on which
one coordinate of degree cost can be saved, while the sum has conditional
variance less than one. The next lemma turns this event into an
observation whose retained variance exceeds its average cost. We keep
$A$ as one cell and refine its complement finely enough that the extra
prediction error uses less than the available variance saving.
\begin{lemma}[Refining the complement of one event]
\label{lem:refinement}
Let $q\ge2$, let $G=(G_1,\ldots,G_q)$ have independent standard normal
coordinates, and put $S_G=\sum_iG_i$. Suppose a measurable set
$A\subset\R^q$ has Gaussian-null boundary,
\[
p_A:=\Pp(G\in A)>0,\qquad
r_A:=\Var(S_G\mid G\in A)<1,
\]
and its indicator, on every product of finite alphabets, is a finite
linear combination of functions each depending on at most $q-1$
coordinates. Then there is a finite pointwise partition $\mathcal P$
with one cell $A$ of cost $q-1$ and all other cells of cost $q$ that
has Gaussian-null cell boundaries and the prescribed pointwise
coordinate bounds. Writing
\[
V=\Var(\E[S_G\mid\mathcal P(G)]),\qquad
c=\E\ell(\mathcal P(G)),
\]
we have $V>c=q-p_A$.
\end{lemma}
\begin{proof}
Partition $[-M,M)$ into finitely many half-open intervals of length
at most $h$, and add the two tail intervals. Approximate a real
coordinate by the midpoint of its bounded interval and by zero on
the tails. For a standard normal coordinate, the expected squared
error is at most
\[
h^2+\E[G_1^2\one_{\{|G_1|\ge M\}}].
\]
Let $\widetilde S_G$ be the sum of these coordinate approximations.
It is constant on each box of the resulting finite rectangular grid.
Since $(\sum_i a_i)^2\le q\sum_i a_i^2$, choosing finite $M$ large
enough and then $h>0$ small enough ensures
\[
\E(S_G-\widetilde S_G)^2q-p_A=\E\ell(\mathcal P(G))=c$.
\end{proof}
The event is fixed before the complement grid is chosen. The resulting
partition is then fixed before any normal approximation or iteration.
This gives the concrete inequality $V>c$ that the amplification theorem
below needs.
\subsection{Amplifying the average cost saving}
\begin{theorem}[Amplification from a mean cost advantage]
\label{thm:mean-cost}
Let $q\ge2$, let $\mathcal P:\R^q\to\mathcal L$ be a measurable map
to a finite label set, and let $\ell:\mathcal L\to\{1,\ldots,q\}$.
Suppose that, on every product of finite input alphabets, each cell
indicator for $l$ is a finite linear combination of functions of at
most $\ell(l)$ input coordinates. Suppose also that every cell has
boundary of standard Gaussian measure zero in $\R^q$. For independent standard
normals $G_1,\ldots,G_q$, put
\[
S_G=\sum_{i=1}^qG_i,\qquad
V=\Var(\E[S_G\mid\mathcal P(G)]),\qquad
c=\E\ell(\mathcal P(G)).
\]
If $V>c$, then finite observations on sign cubes have arbitrarily
large ratios $v(F)/D$, where $D>0$ is a cell degree bound.
The Boolean conclusion of Theorem~\ref{thm:main} follows by taking the
sign of the final score, without a further averaging step.
All partitions and observations are defined pointwise, including
cells of zero Gaussian probability.
\end{theorem}
Only restricted first moments need to pass to the Gaussian limit in
this criterion. The next lemma isolates that fact; it also explains
why zero limiting cell probabilities cause no difficulty.
\begin{lemma}[Transfer for a fixed finite partition]
\label{lem:mc-transfer}
Under the boundary hypothesis of Theorem~\ref{thm:mean-cost}, let
$Z_n$ be centered random variables of variance one converging in
distribution to a standard normal. Use $q$ independent copies to set
\[
S_n=\sum_{i=1}^qZ_{n,i},\qquad L_n=\mathcal P(\mathbf Z_n),\qquad
V_n=\Var(\E[S_n\mid L_n]),\qquad c_n=\E\ell(L_n).
\]
Then
\[
\liminf_n V_n\ge V,\qquad c_n\longrightarrow c,
\qquad \E|Z_n|\longrightarrow\sqrt{2/\pi}.
\]
No fourth-moment hypothesis is required.
\end{lemma}
\begin{proof}
Independence gives joint weak convergence of the input tuples. The
Gaussian-null boundaries imply convergence of all cell probabilities
\cite[Theorem~3.10.1(v)]{Durrett}.
For a fixed cell $E$, clip the sum continuously to $[-t,t]$.
The clipped sum times $\one_E$ is bounded and has Gaussian-null
discontinuities, so its expectations converge
\cite[Theorem~3.10.1(vi)]{Durrett}. Since $S_n$ is centered
and has variance $q$,
\[
\E\bigl[|S_n|\one_{\{|S_n|>t\}}\bigr]\le q/t.
\]
Removing the clipping therefore proves
$\E[S_n\one_{\{\mathbf Z_n\in E\}}]\to
\E[S_G\one_{\{G\in E\}}]$.
For each $n$, the centered conditional mean satisfies
\[
V_n=\sum_{l:\Pp(L_n=l)>0}
\frac{\E[S_n\one_{\{L_n=l\}}]^2}{\Pp(L_n=l)}.
\]
Every term for a cell of positive Gaussian probability converges to
the corresponding Gaussian term. All remaining terms are
nonnegative. This proves the lower limit inequality; it does not
require deleting the cells with zero limiting probability.
The cost convergence follows from the finitely many convergent cell
probabilities. Finally, weak convergence and the bound
$\E[|Z_n|\one_{\{|Z_n|>t\}}]\le1/t$ give convergence of the
absolute first moments.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:mean-cost}]
The partition and costs are fixed throughout the proof. Choose
\[
0<\delta<(V-c)/2,
\qquad 1<\lambda<\frac{V-\delta}{c+\delta}.
\]
For any centered, variance-one law $Z$, use independent copies to
define
\[
S_Z=\sum_{i=1}^q Z_i,\qquad L=\mathcal P(\mathbf Z),\qquad
V_Z=\Var(\E[S_Z\mid L]),\qquad c_Z=\E\ell(L).
\]
For a finite observation $F$ with $v=v(F)>0$, write $Z=T_F/\sqrt v$.
We will increase $v/D$ while maintaining
\begin{equation}\label{eq:invariant}
V_Z>V-\delta,\qquad c_Z1/2.
\end{equation}
Lemma~\ref{lem:mc-transfer} shows that all three inequalities hold
eventually along every sequence of centered, variance-one laws
converging to a standard normal.
To initialize, observe the bit sum itself: $F=H_N$, with score
$T_F=H_N$ and $v=D=N$. The central limit theorem for independent
uniform signs~\cite[Theorem~3.4.1]{Durrett} supplies a finite $N$ for which
\eqref{eq:invariant} holds. The initial ratio is $v/D=1$.
Now hold one such $F$ fixed. Apply $\mathcal P$ to the standardized
scores of $q$ independent copies of $F$, obtaining the group label $L$.
The algebraic assumption and the degree calculus give
\[
\deg(\one_{\{L=l\}})\le D\ell(l).
\]
The tower property identifies the group score and its variance as
\begin{equation}\label{eq:group}
T_L=\sqrt v\,\E[S_Z\mid L],\qquad
\tau^2:=v(L)=vV_Z>0.
\end{equation}
Thus this group has a variance advantage relative to its mean cost.
We next obtain a common degree bound without losing that advantage.
Take $K$ independent copies of $L$. Retain a label word
$(l_1,\ldots,l_K)$ when $\sum_{b=1}^K\ell(l_b)\le K(c+\delta)$.
Let $F'_K$ report each retained word exactly and report one failure
label for every other word. Every retained-word indicator is a product
with degree at most
\begin{equation}\label{eq:degree}
D'_K=DK(c+\delta).
\end{equation}
The failure indicator is one minus the finite sum of all retained-word
indicators, so it satisfies the same degree bound on every input.
The real upper bound $D'_K$ need not be rounded to an integer.
Since the independent costs have mean $c_Z\lambda\frac vD.
\]
One sufficiently large finite $K$ therefore restores every maintained
condition and increases the ratio by a factor greater than $\lambda$.
For any prescribed $C>0$, choose a positive integer $k$ with
$\lambda^k>4C^2$. Perform $k$ such steps, choosing a finite batch
size separately at each step. The final observation remains finite
and satisfies
\[
v(F)/D>4C^2,\qquad \E|T_F|>\tfrac12\sqrt{v(F)}.
\]
Let $N$ now denote the total number of bits underlying the final
observation. Its sign readout $f=\operatorname{sign}(T_F)$, with sign $1$ at zero,
has degree at most $D$. Conditioning the bit sum on $F$ gives the
signed identity
\[
\sum_i\widehat f(\{i\})=\E[fH_N]=\E|T_F|
>\tfrac12\sqrt{v(F)}>C\sqrt D\ge C\sqrt{\deg(f)}.
\]
The positive signed correlation excludes constant $f$. Arbitrarily
large target ratios follow from the same finite iteration.
\end{proof}
\subsection{Applying the criterion to the reporting event}
Apply the criterion first with $q=m+1$ and the reporting event $A$ of
Lemma~\ref{lem:gaussian}. That lemma gives positive probability,
conditional variance of the coordinate sum below one, and Gaussian-null
boundary. Identity~\eqref{eq:indicator} gives the required pointwise
expansion into functions of at most $m$ coordinates.
Lemma~\ref{lem:refinement} therefore supplies a finite partition with costs
$m$ and $m+1$ and with $V>c=m+1-\Pp(A)$.
Theorem~\ref{thm:mean-cost} gives the signed Boolean conclusion.
Appendix~\ref{app:weighted-mixture} supplies a second event with these
same four properties and uses the same refinement and amplification.
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/04-mean-cost.tex ====
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/05-weighted.tex ====
\section{A weighted Gaussian mixture}
\label{app:weighted-mixture}
We give an independent Gaussian construction for the mean-cost
argument of Section~\ref{sec:mean-cost}. The event again requires
exactly the selected leaf to fail its interval test, but now we first
divide the central coordinate into bins and choose each leaf interval
from its bin's conditional mean. This lets us compute the variance on
the event as a finite mixture. The relevant weights change when we
condition on the event; controlling those weights is the main estimate.
Our goal is a positive-probability event on which the sum has
conditional variance less than one, with an indicator that saves one
coordinate in each summand. Lemma~\ref{lem:refinement} will then
produce the required finite partition. The parameter choice below is
independent of the parameter choice in Lemma~\ref{lem:gaussian}.
\subsection{The event and its conditional bin weights}
\label{app:weighted-identity}
For $R>0$, put
\begin{equation}\label{app:weighted-schedule}
m=1+\lceil e^{R^2/4}\rceil,\qquad
\Delta=\frac{2R}{m-1},\qquad h=e^{-3R^2/8},\qquad q=m+1.
\end{equation}
Let $G=(G_0,\ldots,G_m)$ have independent standard normal coordinates
and set $L=\sum_{j=0}^mG_j$. Partition $[-R,R)$ into $m-1$ half-open
intervals $B_i$ of length $\Delta$, and let
$B_m=\R\setminus[-R,R)$. Define
\[
\pi_i=\Pp(G_0\in B_i),\qquad
v_i=\E[G_0\mid G_0\in B_i],\qquad
u_i=\Var(G_0\mid G_0\in B_i).
\]
Every $\pi_i$ is positive. For each leaf $j\in\{1,\ldots,m\}$,
take the half-open interval
\[
I_j=[v_j+1-h/2,v_j+1+h/2),\qquad \chi_j=\one_{I_j}.
\]
For any real input $g=(g_0,\ldots,g_m)$, define $g\in A$ when,
for the unique $i$ such that $g_0\in B_i$, all leaves other than $i$
belong to their intervals and leaf $i$ does not. The half-open
conventions assign every endpoint a definite outcome.
All unqualified bin and leaf sums below range from $1$ to $m$.
\begin{lemma}[The weighted-mixture event]\label{lem:weighted-event}
For all sufficiently large finite $R$, the event $A$ just defined
satisfies
\[
p_A:=\Pp(G\in A)>0,\qquad r_A:=\Var(L\mid G\in A)<1.
\]
Its boundary is contained in finitely many coordinate hyperplanes,
and on every real input its indicator has the expansion
\begin{equation}\label{app:weighted-cell}
\one_A(g)=
\sum_{i=1}^m\one_{B_i}(g_0)
\prod_{\substack{1\le j\le m\\j\ne i}}\chi_j(g_j)
-\prod_{j=1}^m\chi_j(g_j).
\end{equation}
Each product involves at most $m=q-1$ coordinates.
\end{lemma}
\begin{proof}
Exactly one bin contains $g_0$. The first term in
\eqref{app:weighted-cell} tests all unselected leaves; subtracting
the all-leaves-pass indicator requires the selected leaf to fail.
This proves the identity pointwise, including all endpoints.
The boundary assertion follows from the finite collections of bin
and leaf-interval endpoints. It remains to prove the variance saving.
We let $R\to\infty$ for this calculation and fix a finite value only
after the estimates.
\paragraph{Conditional moments.}
Write $\phi$ for the standard normal density. Symmetry of the two
tails gives $v_m=0$; for $i0,
\qquad \Pp(G_0\in B_i\mid G\in A)=\omega_i.
\end{equation}
Here $W$ is finite and positive for every finite $R$. Within
$A\cap\{G_0\in B_i\}$ the coordinates remain independent under
their respective bin, interval, and complementary-interval restrictions.
The conditional mean and variance of $L$ are therefore
\[
\sum_{j=1}^mt_j-1+e_i,
\qquad u_i+\sum_jr_j+b_i-r_i,
\qquad e_i=v_i+1-\frac{t_i}{1-\alpha_i}.
\]
The small mean error satisfies
\begin{equation}\label{app:weighted-mean-error}
|e_i|\le h/2+\frac{\alpha_i|t_i|}{1-\alpha_i}
=O(h(R+2)).
\end{equation}
Applying the variance decomposition with the conditional weights
$\omega_i$, not the original weights $\pi_i$, gives the exact identity
\begin{align}
W\bigl(1-\Var(L\mid G\in A)\bigr)
&=\sum_iw_i(1-b_i+r_i)-\sum_iw_iu_i\notag\\
&\quad-W\sum_jr_j-W\Var_{i\sim\omega}(e_i).
\label{app:weighted-variance-identity}
\end{align}
We next show that the first sum has lower limit at least one and
that each of the three subtracted terms tends to zero. This will
give the strict conditional variance bound despite the possibly
large total weight $W$.
The schedule in \eqref{app:weighted-schedule} makes the bin scale
$\Delta^2/h$, the aggregate leaf scale $mh$, and the tail scale
$e^{-R^2/2}/h$ tend to zero even after multiplication by $e^{3R}$
and any fixed power of $R$. The leaf intervals are narrow enough to
control their total variance, but wide enough that inverse interval
probabilities do not overwhelm the bin and tail estimates below.
\paragraph{The positive contribution.}
Substituting \eqref{app:weighted-complement} yields
\begin{equation}\label{app:weighted-positive-term}
w_i(1-b_i+r_i)
=\pi_i\left(-1+\frac{r_i}{\alpha_i}
+\frac{t_i^2}{1-\alpha_i}\right)
\ge\pi_i(t_i^2-1).
\end{equation}
Since $t_i=v_i+1+O(h)$ uniformly, we have
\[
\sum_i\pi_i(t_i^2-1)
=\sum_i\pi_i v_i^2+2\sum_i\pi_i v_i+O(h(R+2))
=1+o(1)
\]
by \eqref{app:weighted-bin-moments}. The shift of the leaf intervals
by one is important: it produces the term $t_i^2-1$, whose average
tends to one.
\paragraph{The three error terms.}
For $i0
\]
for all sufficiently large $R$. Since $W>0$, this proves the lemma.
\end{proof}
\subsection{Application to mean-cost amplification}
\label{app:weighted-transfer}
Fix one finite $R$ for which Lemma~\ref{lem:weighted-event} holds.
Thus the integer $q=m+1$, all intervals and bins, and the positive
numbers
\begin{equation}\label{app:weighted-saving}
p_A=\Pp(G\in A)>0,\qquad 1-r_A>0
\end{equation}
are fixed before further approximation. The pointwise expansion
\eqref{app:weighted-cell} uses at most $q-1$ coordinates in each
term, and the finite hyperplane boundary is Gaussian-null. These
are precisely the hypotheses of Lemma~\ref{lem:refinement}.
That lemma refines $A^c$ into a finite collection of cells, with
total squared approximation error below the actual positive quantity
$p_A(1-r_A)$. It assigns cost $m$ to $A$ and cost $q$ to every
other cell, giving a fixed partition $\mathcal P$ for which
\begin{equation}\label{app:weighted-mean-cost-gain}
V:=\Var(\E[L\mid\mathcal P(G)])>
c:=\E\ell(\mathcal P(G))=q-p_A.
\end{equation}
The partition includes its Gaussian-null cells as pointwise sets;
later discrete input laws may give those cells positive probability.
With $R$ and this partition fixed, Lemma~\ref{lem:mc-transfer}
supplies the finite-input transfer used in Theorem~\ref{thm:mean-cost}.
The costs $m$ and $q$ are positive integers, and the pointwise coordinate
bounds, Gaussian-null boundaries, and strict inequality $V>c$ verify
all its hypotheses. The theorem therefore gives arbitrarily large
ratios of retained variance to cell degree and the signed Boolean conclusion
of Theorem~\ref{thm:main}. Neither the conditional variance saving nor
the required batch sizes are asserted to be uniform in $R$.
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/05-weighted.tex ====
==== BEGIN Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/06-small-width.tex ====
\section{A small-width Gaussian calculation for the coarse report}
\label{app:small-width}
The coarse report also admits a different Gaussian parameter choice.
We balance the interval width against the spacing of the selector grid
and use the same cancellation as in \eqref{eq:coarse-gaussian-gain}
to compute the resulting predictor error. We also show how this error
transfers when the two predictor constants are recalibrated to the
input law, using convergence of restricted moments.
\subsection{The parameters and a law-dependent error bound}
\label{app:small-width-rule}
For $0T$, set $I(t)=i_*$. The grid endpoints need not
equal $\pm T$, but
\[
|t-t_{I(t)}|\le h\qquad (|t|\le T).
\]
Give leaf $j$ the closed interval
\[
A_j=[t_j+1-w/2,t_j+1+w/2].
\]
These endpoint and tie conventions define the rule on every real input.
Restrict henceforth to sufficiently small $w$ that $m\ge3$.
The choice $h=w^{2/3}$ balances two power scales: $h^2/w$ from
rounding the central input to a grid point, and $w/h$ from adding
the leaf-interval variances. The accompanying cutoff factors grow
more slowly than every power of $1/w$. The choice of $T$ makes
$e^{-T^2/2}=w^2$, so the Gaussian tail second moment is $o(w)$.
The estimates below retain all these factors.
Apply the coarse report of Lemma~\ref{lem:coarse-report} with central
input $t$, leaf inputs $u_1,\ldots,u_m$, selector $I$, and leaf
intervals $A_j$. Denote it by $\mathcal O_w$. Thus it returns $Y$
when all leaves pass, $X$ when only the selected leaf fails, and
$(O,t,I(t),(u_j)_{j\ne I(t)})$ otherwise. In the notation of that
lemma, these events are $B$, $A=P\setminus B$, and $P^c$.
For clarity, the special-cell identity here is
\begin{equation}\label{app:small-width-cell}
\one_A(t,u)=
\sum_{i=1}^m\one_{\{I(t)=i\}}\prod_{j\ne i}\one_{A_j}(u_j)
-\prod_{j=1}^m\one_{A_j}(u_j).
\end{equation}
The lemma proves that every cell has coordinate cost at most $m$:
the displayed summands use $m$ coordinates, the $Y$ cell ignores $t$,
and an ordinary report imposes no condition on its omitted leaf.
This holds pointwise on every finite product alphabet, including
unused labels. The boundaries of $A$, $B$, and $P$ lie in finitely
many coordinate hyperplanes.
Let $U$ be centered with variance one, and take independent copies
$U_0,\ldots,U_m$. Write
\[
L=\sum_{j=0}^mU_j,\qquad
\mathcal R_w(U)=\E[(L-\E[L\mid\mathcal O_w(\mathbf U)])^2].
\]
For the moment assume
\[
q_j=\Pp(U\in A_j)\in(0,1),\qquad Q=\prod_{j=1}^m q_j.
\]
Let $\mu_j,a_j$ be the conditional mean and variance on $A_j$,
and put
\[
M_\mu=\sum_j\mu_j,\qquad S_a=\sum_j a_j.
\]
The interval length gives $0\le a_j\le w^2$.
Use the predictor $M_\mu-1$ on $X$, the predictor $M_\mu$ on $Y$,
and the sum of reported coordinates on ordinary outputs. Denote this
function of the report by $\widehat L$. We will compute its deficit
$1-\E[(L-\widehat L)^2]$ exactly.
The ordinary reports contribute $\Pp(P^c)$ to the squared error,
by Lemma~\ref{lem:coarse-report}. For the exceptional reports, fix
$U_0=t$ and put $i=I(t)$. The event $P$ has conditional probability
$Q/q_i$, restricts every unselected leaf to its interval, and leaves
$U_i$ unrestricted. Under these restrictions, $L-(M_\mu-1)$ has mean
$t+1-\mu_i$ and variance $1+S_a-a_i$. Hence
\[
\E\bigl[\one_P(1-(L-(M_\mu-1))^2)\bigr]
=-Q\E_t\left[\frac{(t+1-\mu_i)^2+S_a-a_i}{q_i}\right].
\]
On $B$, the central input remains unrestricted. The two respective
predictor deficits on $B$ are therefore
\begin{align*}
\E\bigl[\one_B(1-(L-(M_\mu-1))^2)\bigr]&=-Q(1+S_a),\\
\E\bigl[\one_B(1-(L-M_\mu)^2)\bigr]&=-QS_a.
\end{align*}
Subtracting the first of these from the $P$ contribution gives the
$X$ contribution, because $A=P\setminus B$. Adding the $Y$
contribution cancels $S_a$, exactly as in the earlier Gaussian
calculation. Define
\begin{equation}\label{app:small-width-deficit}
H_w(U)=1-\E_t\left[
\frac{(t+1-\mu_{I(t)})^2+S_a-a_{I(t)}}{q_{I(t)}}\right].
\end{equation}
We have proved
\begin{equation}\label{app:small-width-residual}
1-\mathcal R_w(U)\ge
1-\E[(L-\widehat L)^2]=QH_w(U).
\end{equation}
The equality is the gain of the specified predictor; the inequality
uses optimality of conditional expectation. The calculations integrate
against the law of $t$, so they require no positive probability for
any individual central value. We next show that both subtracted
errors in \eqref{app:small-width-deficit} tend to zero for Gaussian
inputs. The product $Q$ may be extremely small; only its strict
positivity will matter after $w$ is fixed.
\subsection{Gaussian estimates, including the rare-probability factors}
\label{app:small-width-estimates}
In this subsection $U=G$ is standard normal and $w\downarrow0$.
Write $\phi$ for its density. Uniformly over the grid,
\[
q_j\le\frac{w}{\sqrt{2\pi}},\qquad
|\mu_j-(t_j+1)|\le w/2,\qquad
\sum_ja_j\le mw^2=O(Tw^{4/3})\longrightarrow0.
\]
We must control the two errors in \eqref{app:small-width-deficit}
after division by the selected interval probability. A uniform lower
bound of order $w$ for all $q_j$ is unavailable, because the grid
extends into the Gaussian tails. Instead we compare each interval's
density with the density of the central coordinate that selects it.
For $|t|\le T$ and $z\in A_{I(t)}$, we have
$|z-t|\le1+h+w/2$. Hence, for sufficiently small $w$,
\[
q_{I(t)}\ge w\inf_{z\in A_{I(t)}}\phi(z),\qquad
\frac{\phi(t)}{q_{I(t)}}
\le w^{-1}\exp(C(1+T)).
\]
The constant $C$ is absolute: the logarithm of the density ratio is
$(z^2-t^2)/2\le |t||z-t|+|z-t|^2/2$.
Since $T=2\sqrt{\log(1/w)}$, for each fixed $\varepsilon>0$,
\begin{equation}\label{app:small-width-inverse-density}
\frac{\phi(t)}{q_{I(t)}}=O(w^{-1-\varepsilon})
\qquad (|t|\le T).
\end{equation}
The fallback interval is centered at $1$, so $q_{i_*}\ge cw$ for
an absolute $c>0$ and small $w$. Integrating the central bound and
using this fallback bound on the tails gives
\begin{equation}\label{app:small-width-inverse-mean}
\E\frac1{q_{I(G)}}=O(Tw^{-1-\varepsilon}).
\end{equation}
Take $\varepsilon=1/6$. Since $0\le S_a-a_{I(G)}\le mw^2$,
the variance contribution in
\eqref{app:small-width-deficit} is at most
\[
mw^2\E\frac1{q_{I(G)}}
=O(T^2w^{1/6})\longrightarrow0.
\]
For the squared mismatch, first suppose $|t|\le T$. Then
\[
|t+1-\mu_{I(t)}|
\le |t-t_{I(t)}|+w/2\le h+w/2.
\]
Its central contribution is therefore at most
\[
O\bigl(Tw^{-7/6}(h+w)^2\bigr)
=O(Tw^{1/6})\longrightarrow0.
\]
On $|t|>T$, the fallback mean is bounded, so the contribution is
\[
O\left(w^{-1}\int_{|t|>T}(1+t^2)\phi(t)\,dt\right)
=O\bigl(w^{-1}(1+T)e^{-T^2/2}\bigr)
=O((1+T)w)\longrightarrow0.
\]
For the integral estimate, integration by parts gives
$\int_T^\infty t^2\phi(t)\,dt
=T\phi(T)+\int_T^\infty\phi(t)\,dt$, and
$\int_T^\infty\phi(t)\,dt\le\phi(T)/T$ for $T>0$.
The last equality uses $e^{-T^2/2}=w^2$.
Both subtracted errors therefore vanish, proving
\begin{equation}\label{app:small-width-limit}
H_w(G)\longrightarrow1.
\end{equation}
Thus the same coarse report has a strictly positive Gaussian
improvement for this independent choice of parameters. To use it
repeatedly on finite cubes, we now fix those parameters and transfer
the particular lower bound just proved.
\subsection{Restricted moments and the finite-score transfer}
\label{app:small-width-transfer}
Fix a sufficiently small $w>0$ with $m\ge3$ and $H_w(G)>1/2$.
All intervals, grid points, selector cells, and $m$ are fixed from
now on. Put
\[
Q_G=\prod_{j=1}^m\Pp(G\in A_j)>0,\qquad \eta=Q_G/4.
\]
Let $U_n$ be centered variance-one variables such that
$U_n\Rightarrow G$ and $\sup_n\E U_n^4<\infty$.
Write $U_{n,0},\ldots,U_{n,m}$ for independent copies. Use a
subscript $n$ for the interval moments of $U_n$ and a superscript $G$
for their Gaussian values, and put $Q_n=\prod_j q_{j,n}$.
For each bounded interval $A_j$, weak convergence off its Gaussian-null
boundary gives convergence of its probability and its restricted
first and second moments. Thus
\[
q_{j,n}\to q_j^G\in(0,1),\qquad
\mu_{j,n}\to\mu_j^G,\qquad a_{j,n}\to a_j^G.
\]
All these conditional moments are defined for sufficiently large $n$.
There are finitely many intervals, so their probabilities are then
simultaneously bounded away from zero and one. In particular, every
coefficient in \eqref{app:small-width-deficit} converges, including
the reciprocal-probability factors.
Coefficient convergence alone does not yet transfer its expectation.
Partition the line into the fixed selector cells
$E_i=\{t:I(t)=i\}$, whose boundaries are finite. The fallback cell
includes both tails as well as the central cell for the grid point
zero; it still has a finite boundary. For $k=0,1,2$,
\begin{equation}\label{app:small-width-restricted-moments}
\E[U_n^k\one_{\{U_n\in E_i\}}]
\longrightarrow\E[G^k\one_{\{G\in E_i\}}].
\end{equation}
To see this, multiply $t^k\one_{E_i}(t)$ by a continuous cutoff that
is one on $[-K,K]$ and zero outside $[-K-1,K+1]$. The resulting
function is bounded and has only Gaussian-null discontinuities, so
weak convergence applies. The cutoff errors for $k=1,2$ vanish
uniformly as $K\to\infty$, by
\[
\E[|U_n|\one_{\{|U_n|>K\}}]\le K^{-1},\qquad
\E[U_n^2\one_{\{|U_n|>K\}}]
\le K^{-2}\sup_j\E U_j^4.
\]
The corresponding Gaussian errors also vanish. The case $k=0$
follows directly from the continuity-set criterion. These are the
same weak-convergence and uniform-integrability principles used in
Lemma~\ref{lem:transfer}; see~\cite{Durrett}.
On a fixed selector cell $E_i$, the integrand in
\eqref{app:small-width-deficit} is a polynomial of degree at most two
in $t$. Expanding that polynomial expresses its expectation as a
finite sum of convergent coefficients times the restricted moments
in \eqref{app:small-width-restricted-moments}. Therefore
\[
Q_nH_w(U_n)\longrightarrow Q_GH_w(G)>Q_G/2.
\]
This proves convergence despite the moving predictor coefficients;
we have not assumed continuity of conditional variances.
For all sufficiently large $n$, \eqref{app:small-width-residual}
now gives $1-\mathcal R_w(U_n)>\eta$. Since the sum of the
$m+1$ independent inputs is centered and has variance $m+1$,
\[
\Var\!\left(\E\!\left[\sum_{j=0}^mU_{n,j}
\,\middle|\,\mathcal O_w(\mathbf U_n)\right]\right)
=m+1-\mathcal R_w(U_n)>m+\eta.
\]
The pointwise coordinate-cost bound from
Lemma~\ref{lem:coarse-report}, with the substitution specified above,
and this transferred gain verify both hypotheses of
Proposition~\ref{prop:amplification} with
$(r,d,\eta)=(m+1,m,Q_G/4)$. The criterion gives the signed
conclusion of Theorem~\ref{thm:main}. Each averaging limit uses one
fixed finite observation and fixed parameters. At that stage, the normalized
batch scores have a fourth-moment bound uniform in the batch size,
by \eqref{eq:fourth}; no uniformity across subsequent stages is required.
==== END Unbounded-Violations-of-the-Square-Root-Degree-Bound//sections/06-small-width.tex ====