Pointwise Multiple Ergodic Averages for Mixing Transformations

Proof. By telescoping and scaling, it suffices to show that the average of v_l=\prod_i G_i\circ R^{a_il} tends to zero when all functions are bounded by one and one of them, G_s, is centered over B. Induct on d. For fixed h\ge1 put F_{i,h}=\overline{G_i}(G_i\circ R^{a_ih}). Invariance gives

The induction hypothesis replaces the factors indexed by i\ne s in their average by their conditional expectations over B. The remaining product is B-measurable and bounded by one; hence

For d=1 this bound holds directly. The Hilbert-space van der Corput inequality now bounds the limiting squared norm by a constant times

Relative weak mixing for R^{a_s} and Cauchy–Schwarz make this expression tend to zero as H\to\infty.□

Proof. Add constant-one functions if necessary to have three distinct positive slopes, write them as gb_1,gb_2,gb_3 with \gcd(b_1,b_2,b_3)=1, and apply Proposition 2.2 to S=R^g. By scaling, suppose the three functions are bounded by one, and put F_l=\prod_{j=1}^3g_j\circ S^{b_jl}.

For each rational c\in[1,2], choose a sequence of profiles tending in L^1 to h_c=c^{-1}\mathbf1_{(0,c]}. On a common conull set all the corresponding smooth dyadic averages converge. For N_k=\lfloor c2^k\rfloor, the difference between the ordinary average at N_k and V_k^\varphi is at most

The last sum tends to \norm{h_c-\varphi}_1 by Riemann sums. Arbitrarily close profiles therefore give the Cauchy property on each of these scales. The L^2 limit established above identifies all their almost-everywhere limits with the same function.

For any bounded sequence |F_l|\le1, changing the averaging length from N to M changes the average by at most

For 2^k\le N<2^{k+1}, compare N with \lfloor c2^k\rfloor on a finite rational grid in [1,2]. Equation (2.3) makes the limiting error arbitrarily small as the grid mesh tends to zero. This proves convergence along all integer lengths.□

Proof. By (2.3), changing the length from L to M changes an average of a sequence bounded by one by at most 2\abs{M-L}/\max(M,L). Choose F to be a sufficiently fine finite grid in [1,2]. For every sufficiently large integer L, some c\in F and k=\lfloor\log_2L\rfloor satisfy

Equation (3.1) therefore supplies, for each x\in E_* and a, a pair (c,k) with k\ge a at which the latter average exceeds \delta. Choose the first such pair in a fixed enumeration. This is a measurable choice from a countable set and defines N_a on E_*; use 2^a elsewhere.

Choose continuous nonnegative circle functions \alpha,\beta, neither identically zero, supported respectively inside (1/4,1/2) and (0,1/(4n)). Set

For z=(x,u) and t=l+s, where l\in\Z and 0\le s<1, the phase factor is \alpha(u)\beta(s). If it is nonzero, then 0<u+is<1 for every i\in I, so \xi(S_C^{it}z)=T^{il}x. Summing complete unit intervals gives, uniformly in z and real L\ge2,

The error includes the incomplete last interval, the change from indices 0,\ldots,\lfloor L\rfloor-1 to 1,\ldots,\lfloor L\rfloor, and the normalization. On E_* the main term at L=N_a(z) has integral at least

On X\setminus E_* its integral tends to zero because N_a=2^a there and B_{2^a}\to0 in L^2(\mu). The uniform error is O(2^{-a}), proving (3.4).□

Proof. For each a the expression before the ultralimit defines a genuine probability measure \lambda_{Y,a} on Y^I, by integrating the measurable orbit map over the indicated finite time interval. We first show that each of its marginals converges against every bounded measurable test G to m_Y. The one-slot continuous-time averages

converge almost surely as L\to\infty. For example, apply Birkhoff’s theorem for S_Y^i to the function y\mapsto\int_0^1G(S_Y^{is}y)\,\dd s and discard the incomplete unit interval. Their almost-sure limit has integral \int G\,\dd m_Y, since every deterministic average has that integral. As N_a(\pi_Yy)\ge2^a, bounded convergence gives the same integral limit at the selected lengths.

Embed Y as a Borel subset of a compact metrizable space K. Ultralimits of the \lambda_{Y,a} against continuous functions on K^I give a positive normalized functional, hence a probability measure on K^I. Its marginals are m_Y, by the preceding paragraph, so it is concentrated on Y^I. Call the resulting law \lambda_Y. To obtain (3.7) for arbitrary bounded slot functions, normalize their bounds to one and approximate each in L^1(m_Y) by continuous functions on K with the same bound. The difference between the two product integrals is bounded by the sum of the single-slot errors. Under \lambda_Y these errors are the L^1(m_Y) errors, while under \lambda_{Y,a} they converge to those errors by the marginal convergence already proved. Letting the errors tend to zero proves the formula. Product tests determine a probability measure on Y^I, giving uniqueness. In particular, all these identities depend only on the almost-everywhere classes of their slot functions.

Applying the product action at a fixed time t_0 shifts the time interval in (3.7) by t_0 without changing its length or its initial-point selector. For slot functions bounded by one the error is at most 2\abs{t_0}2^{-a}, proving invariance. For an extension \rho, substitute G_i\circ\rho in the formula. Equivariance, the equality of the selectors, and Fubini identify its right-hand side with that for Y, proving functoriality.

For a tower Y_0\leftarrow Y_1\leftarrow\cdots, take the full countable product of the underlying standard spaces, with the consistent inverse-limit probability measure and coordinatewise flow. This is a jointly Borel action. A cylinder through stage r has probability computed from m_{Y_r} by the finitely many bonding maps. At any fixed time their equivariance and preservation of m_{Y_r} leave that probability unchanged. Cylinders determine the measure, so every fixed time preserves it. The measure is concentrated on compatible sequences; using the full product avoids any need for one compatibility set invariant at all real times. The stage projections are factor maps modulo null sets, and projection through Y_0 gives the factor onto C. Functoriality now gives the asserted selected-law projections. Finally, the stage coordinates generate the inverse-limit sigma-algebra. The compatibility relations hold under the selected law slot by slot because its marginals are the inverse-limit probability measure. Thus the pulled-back stage sigma-algebras on the selected-law space are increasing and generate it modulo null sets. The usual L^2 approximation by an increasing sequence of sigma-algebras proves density.□

Proof. We first explain the passage from discrete to continuous time used in both assertions. Write t=l+s, with l\ge0 an integer and 0\le s<1. For each fixed s, a continuous-time product becomes the discrete product at slopes i for the shifted slot functions G_i\circ S_Y^{is}. Whenever the corresponding discrete averages converge almost surely, Fubini and bounded convergence show that their integrals in s converge almost surely. Starting the discrete average at l=0 rather than l=1, and dropping an incomplete final unit interval, each has an error tending to zero. The resulting continuous-time convergence holds along all real lengths L.

Apply this observation to functions from W_Y. Their shifts still belong to W_Y, and pointwise convergence on the distal factor is part of Proposition 2.3. Thus the time averages in (3.9) converge almost surely along all lengths, and therefore at the selected lengths as well. Bounded convergence and (3.7) prove that equation.

For \abs{J}\le3, Lemma 2.5 and the same continuous-time argument show that the selected J-marginal equals its deterministic-length integrated law. The extension Y\to W_Y is relatively weakly mixing. Apply Lemma 2.4 to the distinct integer slopes i\in J and the shifted functions G_i\circ S_Y^{is}, for each fixed s. Conditional expectation commutes with these shifts because W_Y is preserved. Integration in s, using the uniform norm bound and bounded convergence, gives

Indeed the difference of the deterministic averages tends to zero in L^2(m_Y), so also in their integrated values. Applying this identity to G_i multiplied by arbitrary bounded functions of P_i yields

Conditioning on the full parameter array requires one more step; it does not follow from (3.12) alone. Use the invariant transformation with speed i in slot i. By the stability under nonzero powers and conditional products in Proposition 2.3, the J-marginal system in (3.12) is relatively weakly mixing over its parameter law. The full P-system is a joining of the distal systems W_Y at these integer powers. It is distal, and is therefore relatively distal over the subarray (P_i)_{i\in J}. Their joint law under \lambda_Y is an invariant joining identifying that common subarray. Relative disjointness in Proposition 2.3 makes this joining conditionally independent over the subarray, which is precisely (3.10).□

Proof. Invariance follows from Proposition 3.2, after rescaling the time parameter by 1/b. Slot b has speed one and marginal m_Y, giving the stated factor maps. In slot i the W_Y-factor is distal for time i/b, by Proposition 2.3. The law of P is an invariant joining of these rational-time distal systems, hence is distal. Maximality of the distal factor gives the last assertion.□

Proof. Continuous functions on the compact product of circles are uniformly approximable by finite sums of products of continuous one-coordinate functions. Apply this to \Psi, use (3.7) for each resulting product, and then use the strictly positive lower limit in (3.4). Finally, time one fixes the phase on C, so the phase factor is distal and lies in W_C.□

Proof. Choose a positive integer h such that hq_\gamma is an integer for each output. The phase vector V is a factor fixed by time h, and its time-one action is distal, so V belongs to W_Y. For any spatial tuple appearing in (4.1), its joint factor with V has product law over V. At time h the spatial coordinates evolve by a product of positive integer powers of T. This product is mixing: the assertion follows first for product tests from mixing of each power, and then for all bounded tests by approximation. Consequently this factor is relatively weakly mixing over V for time h.

On the other hand, W_Y is distal for time h and relatively distal over V. Relative disjointness, in the form of [12, Proposition 2.2], makes the spatial factor and W_Y relatively independent over V. Its conditional spatial law given W_Y is therefore the product law in (4.1). Pullback to an extension preserves the joint laws of the original data, proving the channel identities there; the same argument gives their stronger conditioning.□

Proof. Each new output is probability-preserving and has positive rational speed iq_\gamma/b. It remains to prove the two conditional laws. Test them with products of bounded spatial functions and products of bounded phase functions. Such tests determine the laws. Expanding each spatial function into its mean and centered part, and scaling, reduces the proof to real spatial functions that are either 1 or centered and bounded in absolute value by 1. We may also bound every phase function by 1. Whenever at least one spatial factor is centered, the tested integral must be zero. A test using the new original coordinate uses outputs from only a proper set of groups.

Time intervals and offsets. Use the selected-law formula (3.7) and condition on the old phase vector V under m_Y. Fix an integer h>0 clearing all output-speed denominators and write t=hl+s, where l\ge0 is an integer and 0\le s<h. For fixed V,s, all phase weights in the test are independent of l. The spatial function for output \gamma at slot i is evaluated at

The offsets a_{\gamma,i} depend on V,s and range over a fixed finite set, by the suspension formula. If the original-factor test is present, its argument is T^{hbl+a_0}x_0, with the same finite-offset property. Equivariance and Fubini justify these formulas in the time integrals.

On an event where the selected length is N=c2^k, c\in F and k\ge a, put m=\lfloor c2^k/h\rfloor. Replacing the normalized time integral by the average over the m complete intervals, followed by integration against ds/h, has error at most 2h2^{-a}. For all sufficiently large a we have m\ge1.

Tests using a proper set of groups. Given V, the relevant old output coordinates have product law and are independent of x_0, by (4.1). The selector is determined by V,x_0. Suppose first that some output occurrence is centered. For fixed V,s,x_0, integrate the spatial output product at index l. The expectation factors over the old output indices \gamma. For an index having a centered occurrence, the times (4.2) in distinct slots separate as l\to\infty. Mixing of all orders makes its integral tend to the product of the means, hence to zero. A single centered occurrence already has zero integral. The convergence is uniform over the finitely many offset patterns. All other factors have absolute value at most 1. The Cesàro averages of these absolute expectations consequently tend to zero uniformly over all sufficiently large lengths. This applies to the selected lengths as well.

If every output test is 1, the centered factor must be the original one. Birkhoff’s theorem for the ergodic power T^{hb} gives convergence to zero for \mu-almost every x_0, simultaneously for all the finitely many offsets a_0. Since the selected lengths tend to infinity pointwise, they have the same limit. The conditional law of x_0 given V is \mu, so bounded convergence completes this case.

Three groups and almost orthogonal vectors. It remains to treat the full output list, with no original-factor spatial test. If one group has no centered occurrence, every spatial test in that group is 1, and the preceding argument applies; the phase tests of that group were allowed throughout. Thus suppose each group contains a centered occurrence. For fixed V,s, write its spatial product at index l as

where \Omega_j carries the product measure with one copy of \mu for every old output in group j. These are real unit-ball vectors, indeed functions bounded by 1. Given V, the old spatial output law is the product of these three spaces. The vectors depend on V,s only through the finite offset patterns.

For every \eta>0, after omitting finitely many initial indices, the families (u_l) and (v_l) each have absolute pair inner products at most \eta outside a graph of bounded maximum degree L_0. All these bounds are uniform in the offset patterns. To verify this, in each of the two groups choose a centered occurrence at some output index \gamma. Its coordinate integral in a pair inner product is small by mixing of all orders whenever the times in the two copies of (4.2) are sufficiently separated. The times within each copy separate once l,l' exceed a fixed threshold. Failure of separation between copies then requires one of finitely many inequalities

For fixed l, each inequality permits only a bounded number of integers l', because e_\gamma,i'>0; the same holds with l,l' interchanged. Their union is the required bounded-degree graph. The coordinate integrals for other output indices are bounded by 1. The separation threshold and L_0 may depend on \eta, but no rate of mixing is needed.

Conditioning on a selected length. For fixed selector index a, partition into the events N_a=c2^k, c\in F, k\ge a, choosing one representation when a length has more than one. Given V, write their probabilities as p_{k,c}(V). On one such event of probability p>0, the conditional spatial law of any two groups, and of each single group, is unchanged. Indeed the event is determined by V,x_0, which is independent of any proper set of groups by (4.1). The full three-group law may change. Its density \rho relative to the product law satisfies

The reason is that the joint measure of the outputs and the event is dominated by the unconditioned product measure. These statements hold for almost every V; the length events are countable.

We choose the rank bound to meet two requirements: the packing bound must be o(m), and the reciprocal bounds must be summable over dyadic length scales. For m=\lfloor c2^k/h\rfloor set

Let \Pi_m be the orthogonal projection onto up to d_m leading eigenvectors of the positive covariance operator \sum_{l<m}z_lz_l^*, taking its full range if its rank is smaller. Fix 0<\varepsilon\le1 and then fix 0<\eta\le\varepsilon^2/10^4 in the preceding graph bound. Theorem A.1, proved in Appendix A from [12, Theorem 4.1], gives

Here the error tends to zero uniformly over the offset patterns. Indeed, after the fixed initial indices are removed, the number of projection norms at least \varepsilon is at most

The removed indices contribute o(1) to the average. Importantly, \varepsilon,\eta, and the resulting exceptional degree are fixed before m tends to infinity.

For the projected terms, Cauchy–Schwarz under the conditional event law uses its unchanged two-group and one-group marginals. Term by term, including the event probability, it gives

Thus their average contributes at most p(\varepsilon+o(1)).

For the residual vectors z_l'=(1-\Pi_m)z_l, let A=(\langle z_l',z_{l'}'\rangle)_{l,l'<m} and B=(\langle w_l,w_{l'}\rangle)_{l,l'<m}. The covariance trace is at most m, so its remaining eigenvalues, and hence the nonzero eigenvalues of A, are at most m/d_m. If its rank was at most d_m, the residual is zero. Also B is positive semidefinite with trace at most m. Consequently

By (4.3), the residual contribution, including the event probability, is at most \sqrt{p/d_m}. Multiplication by the fixed phase weight does not increase either bound.

Summing over lengths. Write m(k,c)=\lfloor c2^k/h\rfloor. For fixed h this is comparable to 2^k for all sufficiently large k, uniformly in the finite set F. Since \sum_{k,c}p_{k,c}(V)=1, Cauchy–Schwarz yields

The series converges because its summands are O(k^{-3/2}). The projected contributions have total limit superior at most \varepsilon, by (4.5) and the same probability identity. These estimates are uniform in V,s and may be integrated. There is no measurable-choice issue for the projections: choose one for each of the countably many sizes and finitely many offset patterns. Letting a tend to infinity in the selected-law formula and then letting \varepsilon tend to zero proves the required vanishing. Both laws in (4.1) follow.□

Proof. Apply Proposition 4.3 and Lemma 4.2 to \mathsf M_b(Y). By Lemma 3.4, the old parameter array P belongs to its maximal distal factor. Conditioning the resulting constant product law down to P proves the assertion.□

Proof. Test the conditional law by a product of bounded real functions, one for each designated list, and by a bounded real function of the full parameter array. Write each spatial test as its product-law mean plus a centered function. Every nonconstant term in the expansion is a correlation of the form (5.1) with fewer than k slots, and hence vanishes. Only the product of the means remains. Product tests determine the asserted conditional law on these finite products of standard spaces.□

Proof. We use a countable bounded-energy construction of the kind underlying Austin’s sated extensions [2, Theorem 3.11]; the argument below proves the assertion for the particular data (5.2). In a tower of flow extensions, for a fixed test f introduced at one stage, the quantity

at later stages is nondecreasing, by inclusion of the pulled-back data, and is bounded by \|f\|_2^2. At each stage introduce a countable dense set in the L^2 space of its selected law, retaining all previously introduced tests. Schedule all pairs consisting of a retained test and a datum index so that each pair is treated infinitely often, with positive tolerances tending to zero. A diagonal enumeration gives such a schedule even though new tests are introduced at every stage.

At a scheduled step, extend the current flow so that the corresponding energy is within the prescribed tolerance of its supremum over all standard flow extensions of that stage over C. The supremum is finite. It can be taken over a set: standard Borel spaces, their probability laws, Borel actions, and factor maps admit codes on fixed standard spaces. The identity extension is among the competitors. Let Y_* be the countable inverse limit of the resulting tower, which exists in our category by Proposition 3.2.

Fix a retained test, an index l, and a further extension Y'\to Y_*. At every scheduled optimization of this pair, Y' is also an extension of the stage just before the optimization. Its energy is therefore at most the energy achieved immediately after that optimization plus its tolerance. The latter achieved energy is at most the energy at Y_*. As the tolerances tend to zero, the energy at Y' is at most that at Y_*. The reverse inequality follows from monotonicity, so the two energies are equal.

Identify L^2(\lambda_{Y_*}) with its pullback in L^2(\lambda_{Y'}). The two conditional expectations are orthogonal projections onto nested closed subspaces. Equality of their squared norms forces equality of the projections, proving (5.3) for each retained test. Stage functions have dense span in L^2(\lambda_{Y_*}) by Proposition 3.2; the retained dense sets and the contraction property of conditional expectation extend the identity to every f in that space.□

Proof. We prove both channel laws conditional on the old full parameter array P on (Y^I,\lambda_Y). Every phase in the new channel is a function of P, so conditioning down then proves (4.1) for Z.

For the full output collection, its spatial lists are

These are allowed lists at k distinct old slots. Expand a product of tests on these lists into constant and centered parts. Every term with fewer than k centered factors has the product-law value by Lemma 5.1. The all-centered term also vanishes against every bounded parameter test. Otherwise it would give a nonzero correlation with support k and r+1 output roles: slot b now has an output role, and the other roles are unchanged. This contradicts the definition of r. If the output list at b is empty, its centered test is identically zero, with the same conclusion. Thus the full output collection has product spatial law given P.

For the second channel law, choose a proper subset H\subsetneq\{1,2,3\} of the new groups and include x_0(y_b). At slot b the resulting list is (x_0(y_b),d_{Y,H}(y_b)), an allowed input list. At any other retained slot j it is exactly Q_j, and such a slot occurs only when \tau(j)\in H. Surjectivity of \tau omits at least one of the k-1 other slots. Fewer than k old slots therefore occur, so Lemma 5.1 gives the required product law conditional on P. This proves the second channel law as well.□

Proof. Apply saturation (5.3) with datum index 0 to the extension Z\to Y. It says that the conditional law of the entire column given E is the law of (Y^I,\lambda_Y) given p. This assertion follows first for L^2 tests, and then as an identity of conditional kernels by a countable determining class. By the singleton case of (3.10), the conditional law of y_b given E is consequently m_{Y,w}. Conditioning down to E_b gives the same law for the slot-b state of row b given E_b. Since row b has marginal m_Z, this proves the last assertion of the lemma.

Saturation with datum index b gives the stronger identity

Indeed the old datum is (P,y_b) and the new datum is (E,\mathbf z_b). Multiply (6.5) by q(\mathbf z_b) and condition on E. The singleton case of (3.10), now for Z, states that the law of \mathbf z_b given E is the m_Z-fibre law over E_b. Within that fibre, (6.2) conditions q(\mathbf z_b) on its slot-b state, whose law is m_{Y,w} by the first part of the proof. This gives (6.4).□

Proof. Let F_0 be a bounded real test on W_Z. In the single-state parameter law (\omega_Z)_*m_Z, let \overline F_0 satisfy

We prove that F_0(E_b) can be replaced by \overline F_0(w) when tested against any product \prod_i H_i(p_i) of bounded real coordinate tests. All the variables are functions of E, so the deterministic parameter-law identity (3.9) on Z computes their joint integral. At each fixed averaging time t, its state integral is

Make the measure-preserving change of variable z'=S_Z^{bt}z. The product of the H_i becomes

For each fixed t, this is measurable with respect to \kappa(\omega_Z(z')). To see this, the slot-b map Z\to Y is a flow factor, and the old factor W_Y is preserved by every flow time. Hence the old parameter at time (i-b)t is a measurable function of the old parameter at time zero.

Conditional expectation in this single-state integral therefore replaces the first factor by

Reversing the change of variable and taking the deterministic averaging limit gives

The fixed-time identities suffice under the time integral by measurability and Fubini; no simultaneous pointwise model for the factor action is needed. The E_b-marginal is the single-state parameter law, so \overline F_0(w)=\E[F_0(E_b)\mid w]. Products of the H_i determine the p-law, and w=p_b is itself a coordinate of p. The displayed identity is exactly conditional independence given w.□

Completion of the proof of Theorem 1.1. If the required pointwise limit failed for a fixed tuple and a fixed n\geq2, the reduction and selectors of Section 3 would give the positive correlation (3.14). The minimum-support argument rules this out immediately when n<4, and the saturated, regrouped square argument rules it out when n\geq4. Therefore the averages converge almost everywhere to the product of the means, along all positive integer lengths. Finally, the countable-coordinate coding reduction pulls this conclusion back to the original, possibly nonstandard, probability space. The tuple and n were fixed throughout, as allowed in the statement of the theorem.□

Proof. Write H=\sum_jg_jH_j. Gaussian integration by parts, followed by differentiation of the matrix power, gives for every integer q\ge2

For a fixed self-adjoint H with eigenvalues \lambda_u and a self-adjoint matrix K, the absolute value of such a trace is at most

The inequality follows from weighted arithmetic–geometric mean and the symmetry |K_{uv}|=|K_{vu}|. Summing over j gives

Since \E\tr H^2=\tr S, iteration yields

The operator norm of H equals that of \sum_jg_jB_j. Taking a 2q-th root and using the hypotheses bounds its expectation by

Choose an integer q\ge2 comparable to \log(2+d) to obtain (A.2).□

Proof of Theorem A.1. We first record an elementary consequence of the exceptional-graph hypothesis. If unit-ball vectors v_j have absolute inner products at most \eta outside a graph of degree L, then for every nonempty set A of indices,

Indeed the expansion contains at most (1+L)|A| ordered diagonal or exceptional pairs. A lower bound on the norm of an average therefore bounds the number of vectors in that average.

It suffices to work in the finite spans of the x_j and y_j. To see this, let Q project onto their tensor product and replace the testing subspace \operatorname{Ran}P by Q(\operatorname{Ran}P). For any vector z in that tensor product, the norm of its projection onto the new subspace is at least \norm{Pz}: in the supremum defining \norm{Pz}, replace each unit testing vector by its Q-image, whose norm is at most one and whose pairing with z is unchanged. The dimension does not increase.

Identify tensors with matrices from H_2 to H_1. Choose a Hilbert–Schmidt orthonormal basis A_1,\ldots,A_r of the testing space, where r\le d. The matrices

have trace r. Let E_1,E_2 be their spectral subspaces for eigenvalues strictly greater than \sqrt d; each has dimension at most \sqrt d.

Discard indices for which the projection of x_j onto E_1 has norm greater than \varepsilon/10, and do the same for y_j,E_2. Cover either exceptional subspace’s unit ball by at most (1+80/\varepsilon)^{\sqrt d} balls of radius \varepsilon/40. If one ball contains s of the discarded projections, their average has norm at least \varepsilon/20. Applying (A.4) to the original vectors, with \eta\le\varepsilon^2/10^4, gives s\le C(1+L)\varepsilon^{-2}. The number of discarded indices is therefore at most

Let Q_1,Q_2 project onto E_1^\perp,E_2^\perp, and put B_j=Q_1A_jQ_2. The coefficient map z\mapsto(\ip{A_j}{z}_{\rm HS})_{j=1}^r is a contraction. For a remaining index,

Thus each remaining index counted in (A.1) has coefficient vector

The map from x_j\otimes y_j to v_j remains contractive. Outside the union of the two exceptional graphs, the tensor inner products have absolute value at most \eta^2, and that union has degree at most 2L. A collection of these coefficient vectors in a ball of radius \varepsilon/8 centered at one of them has average norm at least 3\varepsilon/8. Applying (A.4) to its preimage tensors bounds its size by C(1+L)\varepsilon^{-2}. A maximal \varepsilon/8-separated subset therefore has cardinality l such that the number of indices still to be counted is at most C(1+L)\varepsilon^{-2}l.

We now bound this separated set. For G=\sum_ag_aB_a, the centered Gaussian variables Z_j=\ip{x_j}{Gy_j} satisfy

Gaussian comparison gives, when l\ge2,

For completeness, the comparison of finite centered Gaussian families follows by applying Gaussian integration by parts to \beta^{-1}\log\sum_j e^{\beta z_j} along their independent Gaussian interpolation. Its derivative is

It is nonnegative when the first increment variances dominate. Letting \beta\to\infty compares the expected maxima. For (A.6), take the Z'_j to be independent normals of variance \varepsilon^2/128 and use \E\max_{j\le l}g_j\ge c\sqrt{\log l}.

Compression gives

These operators have norms at most \sqrt d and traces at most d. Lemma A.2 therefore applies. Together with (A.6) it yields

The resulting bound holds for l\le1 as well. Combine it with (A.5) and absorb \log(1+80/\varepsilon)\le C\varepsilon^{-2} to prove (A.1).

For d=d_m, the exponent is O_\varepsilon((\log m)^{3/4}\log\log m)=o(\log m), which proves the asserted o(m) bound.□