Unbounded Violations of the Square-Root Degree Bound

1 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

Constants have degree zero. This is the degree of the real multilinear polynomial representing f, as in the work of Nisan and Szegedy [6]. For Boolean f, taking values in \{-1,1\}, Cauchy–Schwarz gives

Gopalan and Servedio conjectured that \sqrt{\deg(f)} could replace \sqrt n; see O’Donnell’s problem list [7, p. 9]. We show that no constant multiple of this proposed bound holds.

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.

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 [3]. Here the singleton coefficients are summed linearly, rather than squared.

A sharper proposal in the same problem list uses the majority benchmark

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 [4, Theorem 2.1] gave discrete-derivative reformulations of the majority proposal. Wang [9, Theorems 2.2, 3.2 and 3.6] gave another equivalent formulation and proved the cases d=1 and d=n-1. Kudin and Pašalić [5] proved the cases d=2,3 and refuted the majority bound at d=4. Theorem 1.1 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 [6, Lemma 2.4 and Corollary 2.5]

Theorem 1.1 thus separates the conjectured square-root scale from this surviving linear bound.

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

We call T_F the 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 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 [8, Theorem 3 and Lemma 3] bound the signed singleton sum of a Boolean readout by the square root of this expectation. Blais, Tan and Wan [1, Lemma 3.1 and Theorem 1] 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 2 proves the finite-observation calculus and amplification criterion. Section 3 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 2 and 3 contain a complete proof of Theorem 1.1.

The further constructions distinguish which features of this rule are needed for a gain. In Section 4, the 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 5 allows different degree costs for different outputs: retained variance need only exceed their 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 A supplies an independent Gaussian event for the average-cost criterion. Appendix B gives a different Gaussian parameter schedule for the coarse report, together with the transfer argument for its law-dependent coefficients.

2 Finite observations and amplification

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

These are instances of the conditional-expectation projection identities; see [2, Theorems 4.1.13 and 4.1.15]. In particular, for v=v(F)>0, the numerical observation

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 [2, Theorem 3.4.1] gives Z_M\Rightarrow G, where G is standard normal. For each fixed initial F, all moments are finite, and

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 [2].

3 Retaining more variance than the degree cost

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 2.3, 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.

3.1 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

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

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

Each summand uses only m coordinates. This cancellation is what allows the exceptional report to have the same degree cost as the ordinary reports.

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 (3).

3.2 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.

3.3 Transfer to finite inputs and amplification

Fix all the Gaussian choices from Lemma 3.2, 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 2.1 to the fixed function

It has quadratic growth and discontinuities only on the finitely many hyperplanes from Lemma 3.2; 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 3.1 then gives

Together with the pointwise output-indicator decomposition in that lemma, this verifies both hypotheses of Proposition 2.3 with (r,d,\eta)=(m+1,m,p_*/2).

The Gaussian parameters and \eta remain fixed throughout the iteration. Proposition 2.3 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 2.2 then supplies a nonconstant Boolean function with signed singleton sum greater than C\sqrt{\deg(f)}, proving Theorem 1.1.

4 Two other reporting rules

The report in Section 3, which we call the 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.

4.1 Merging the all-leaves-pass reports

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

Define the coarse report \mathcal O by

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.

Now fix the Gaussian intervals and selector from Lemma 3.2. Write

The Gaussian calculation gave d_A=\E[\one_A(1-(L-b)^2)]=p_*(1+S-J) with J<1/4. In Lemma 4.1 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

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 (9) is an identity for this predictor’s gain; (8) 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 2.1 and (9) imply that eventually \E g_{b,M_\mu}>\eta, where \eta=p_*/2>0. Lemma 4.1 then gives retained variance greater than m+\eta and the required pointwise cell cost. Therefore Proposition 2.3 applies with

This criterion and Lemma 2.2 give Theorem 1.1 by the coarse rule as well.

4.2 Switching to an independent score

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

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

Multiplying (3) 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 2.1 gives

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

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

The same input law satisfies

The identities in (10) and the equality in (11) 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, (10) 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 2.3 with the distinct triple

The criterion again proves Theorem 1.1, 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.

5 Amplifying an average degree saving

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 2. 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.

5.1 From a variance saving to an average cost saving

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.

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.

5.2 Amplifying the average cost saving

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.

5.3 Applying the criterion to the reporting event

Apply the criterion first with q=m+1 and the reporting event A of Lemma 3.2. That lemma gives positive probability, conditional variance of the coordinate sum below one, and Gaussian-null boundary. Identity (3) gives the required pointwise expansion into functions of at most m coordinates. Lemma 5.1 therefore supplies a finite partition with costs m and m+1 and with V>c=m+1-\Pp(A). Theorem 5.2 gives the signed Boolean conclusion. Appendix A supplies a second event with these same four properties and uses the same refinement and amplification.

A A weighted Gaussian mixture

We give an independent Gaussian construction for the mean-cost argument of Section 5. 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 5.1 will then produce the required finite partition. The parameter choice below is independent of the parameter choice in Lemma 3.2.

A.1 The event and its conditional bin weights

For R>0, put

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

Every \pi_i is positive. For each leaf j\in\{1,\ldots,m\}, take the half-open interval

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.

A.2 Application to mean-cost amplification

Fix one finite R for which Lemma A.1 holds. Thus the integer q=m+1, all intervals and bins, and the positive numbers

are fixed before further approximation. The pointwise expansion (17) uses at most q-1 coordinates in each term, and the finite hyperplane boundary is Gaussian-null. These are precisely the hypotheses of Lemma 5.1. 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

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 5.3 supplies the finite-input transfer used in Theorem 5.2. 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 1.1. Neither the conditional variance saving nor the required batch sizes are asserted to be uniform in R.

B A small-width Gaussian calculation for the coarse report

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 (9) 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.

B.1 The parameters and a law-dependent error bound

For 0<w<1, put

List the points of h\mathbb Z\cap[-T,T] in increasing order as t_1,\ldots,t_m, and let i_* index zero. Thus m=2\lfloor T/h\rfloor+1=O(T/h) as w\downarrow0; in particular, m\ge3 for sufficiently small w. On |t|\le T, let I(t) be the index of a nearest grid point, breaking ties by the smaller index. On |t|>T, set I(t)=i_*. The grid endpoints need not equal \pm T, but

Give leaf j the closed interval

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 4.1 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

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

For the moment assume

Let \mu_j,a_j be the conditional mean and variance on A_j, and put

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 4.1. 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

On B, the central input remains unrestricted. The two respective predictor deficits on B are therefore

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

We have proved

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 (31) tend to zero for Gaussian inputs. The product Q may be extremely small; only its strict positivity will matter after w is fixed.

B.2 Gaussian estimates, including the rare-probability factors

In this subsection U=G is standard normal and w\downarrow0. Write \phi for its density. Uniformly over the grid,

We must control the two errors in (31) 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,

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,

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

Take \varepsilon=1/6. Since 0\le S_a-a_{I(G)}\le mw^2, the variance contribution in (31) is at most

For the squared mismatch, first suppose |t|\le T. Then

Its central contribution is therefore at most

On |t|>T, the fallback mean is bounded, so the contribution is

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

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.

B.3 Restricted moments and the finite-score 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

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

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 (31) 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,

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

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 2.1; see [2].

On a fixed selector cell E_i, the integrand in (31) 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 (36). Therefore

This proves convergence despite the moving predictor coefficients; we have not assumed continuity of conditional variances. For all sufficiently large n, (32) 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,

The pointwise coordinate-cost bound from Lemma 4.1, with the substitution specified above, and this transferred gain verify both hypotheses of Proposition 2.3 with (r,d,\eta)=(m+1,m,Q_G/4). The criterion gives the signed conclusion of Theorem 1.1. 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 (2); no uniformity across subsequent stages is required.