The Euclidean Steinitz–Bergström theorem

Proof of Theorem 1.2 from Theorem 1.1. Fix an indexed zero-sum family and choose an order attaining its minimum \beta; this exists because there are only finitely many permutations. Relabel the vectors in that order. Put

where the signs come from Theorem 1.1. Hence \lVert A_j\rVert_2\le\beta and \lVert B_j\rVert_2\le C\sqrt d. The positive-sign and negative-sign selections from an original prefix sum respectively to

Place all positive-sign indices in their original order, followed by all negative-sign indices in reverse original order. A partial sum in the first block is some P_j. In the second block, the unused indices are the negative-sign indices of an original prefix. Since the total sum is zero, the current partial sum is therefore some -M_j. This also covers either block being empty. Every new partial sum has norm at most (\beta+C\sqrt d)/2. By minimality,

This permutes indices and so preserves all multiplicities.□

Proof of Theorem 1.1. Write the prescribed sequence as v_1,\ldots,v_n\in\R^d, with \lVert v_i\rVert_2\le1. The hypotheses give d,n\ge1.

The symmetric contractions. For a positive absolute \sigma<1, to be chosen below, set

On the span of b_i, the matrix C_i has eigenvalue \sqrt{1-\lVert b_i\rVert_2^2}, and on its orthogonal complement it is the identity. This includes b_i=0, for which \eta_i=1/2 and C_i=I. Consequently

Use these matrices in (4), and let \mathcal D be the body in Proposition 2.2.

For x\in\R^{d+n}, let x^0 be obtained by setting its first d coordinates to zero. Define row vectors m_i by

Each row m_i is supported only on the noise coordinates d+1,\ldots,d+i-1. In particular it is unaffected by any coordinate assigned at step i or later.

The cost of the predictor constraints. Let M be the matrix with rows m_i. We claim that every column of M has squared Euclidean norm at most \sigma^2. Its initial d columns are zero. For a noise coordinate d+j, follow its contribution to the state:

The coefficient of that coordinate in m_i is zero for i\le j, and is \eta_i b_i^Tr_{i-1} for i>j. Symmetry of C_i gives the exact loss identity

Thus the losses telescope:

In particular, for every positive definite diagonal Q,

Choose an absolute dilation D_*>0 and define

This is a bounded open convex centrally symmetric set containing a neighborhood of zero. Lemma 2.3, Proposition 2.2, and (10) give

We can therefore fix, once and for all,

The same body K then satisfies (3) for every positive definite diagonal Q. These choices are independent of d, n and the vectors.

Choosing the coefficients. For u\in\R write \operatorname{clip}_\delta(u)=\max\{-\delta,\min\{u,\delta\}\}. Apply Proposition 2.1 to the distinct axes e_{d+1},\ldots,e_{d+n}. At step i prescribe the shift

By the support of m_i, this is a function of the previously assigned coordinates, as required. The proposition supplies signs and a final point x=x^{(n)}\in K. Its first d coordinates remain zero. Also, coordinates assigned before step i never change afterward, so

The final membership x\in K implies |m_ix|<\delta. Hence each shift was already within the permitted interval: clipping was inactive, and

Here x^0=x because the initial block is zero. Clipping is used only to make the application of Proposition 2.1 unconditional; causality and the final constraints subsequently remove it.

Figure 1 illustrates the identity that completes the construction.

Cancellation. For this single final coefficient vector, R_0x=0 and

Thus, simultaneously for every 0\le t\le n,

Since x\in2D_*\mathcal D, all these states have norm less than 2D_*A_0\sqrt d. Dividing (15) by \sigma proves Theorem 1.1 with the absolute constant C=2D_*A_0/\sigma.□

Proof. The generator of W is \tr(Q\nabla^2). Let \tau_D=\inf\{s\ge0:W(s)\notin D\}, and let

be its killed semigroup. The corresponding nonnegative self-adjoint operator is the Dirichlet realization of -\tr(Q\nabla^2), with form \int_D\nabla g^TQ\nabla g on H_0^1(D). These standard Dirichlet facts apply here because bounded convex domains are connected and Lipschitz; see, for example, [14, Section 2 and Appendix C], after the linear change of coordinates for Q and the time normalization above. The killed representation can also be obtained first on smooth interior domains and then by exhaustion: their compactly supported smooth functions exhaust the form domain, while any continuous path remaining in D on a compact time interval has compact image in D.

Write \lambda=\lambda_Q(D). Compactness of H_0^1(D)\hookrightarrow L^2(D) and the spectral theorem give \lVert P_s^D\rVert_{2\to2}=e^{-s\lambda} and a first eigenfunction \varphi that can be chosen nonnegative by taking the absolute value of a Rayleigh minimizer. Interior elliptic regularity and the strong maximum principle make \varphi strictly positive at every point of D. It is bounded: free heat kernel domination and \varphi=e^\lambda P_1^D\varphi give this directly by Cauchy–Schwarz. Consequently,

For the reverse bound, let p_Q denote the free heat kernel. For T\ge1, the semigroup property and free kernel domination yield

Both prefactors are finite for the fixed D,Q,x. Taking logarithms and dividing by T proves (16). Finally, a nonempty open convex set symmetric about 0 contains 0 as an interior point.□

Proof. Replace each interval by a finite grid. All the constraints are then closed centrally symmetric convex conditions on one finite-dimensional centered Gaussian vector. Represent that vector as a linear image of a standard Gaussian on its linear support; thus a possibly singular covariance creates no difficulty. Royen’s Gaussian correlation inequality [20], iterated over the finitely many events, gives the desired product bound on the grids. Now refine nested grids whose unions are dense in the respective intervals. Closedness of each K_{ij} and path continuity identify the decreasing limit with the stated event. Continuity of probability from above proves the assertion.□

Proof of Lemma 2.3. The set K is again a bounded open centrally symmetric convex neighborhood of 0. Take Brownian motion W of covariance rate 2Q started at 0. On [0,T], impose the closed constraints

Their simultaneous occurrence implies survival in K: \overline{D_*D}\subset 2D_*D, since 0 is interior to the convex set D, and the half-threshold slabs lie inside the open full-threshold slabs. By Lemma 2.5, and then by replacing each closed-event probability by its smaller open-event probability,

For a nonzero row m_i, the process m_iW is one-dimensional Brownian motion with covariance rate 2c_i, where c_i=m_iQm_i^T>0. The first Dirichlet eigenfunction of -c_i\,d^2/dx^2 on (-\delta/2,\delta/2) is \cos(\pi x/\delta), with eigenvalue \pi^2c_i/\delta^2. Lemma 2.4 gives the corresponding survival exponent. A zero row gives the identically zero process, so its probability is one and its cost is zero.

Take negative logarithms, divide by T, and let T\to\infty. Lemma 2.4 applies to K and D_*D, and the change of variables in the Rayleigh quotient gives \lambda_Q(D_*D)=D_*^{-2}\lambda_Q(D). This proves (6). The argument used only inclusions between closed and open events; it requires no assertion about equality of their survival rates.□

Proof. Let \mathcal F be the nonnegative functions in H^1(\R^m) that vanish almost everywhere outside K and have L^2 norm one, and put E_i(f)=\int|\partial_i f|^2. Consider the set of simultaneous upper bounds

It is nonempty and is closed under addition of nonnegative vectors. It is also convex. For f,g\in\mathcal F and 0\le t\le1, the function h=(tf^2+(1-t)g^2)^{1/2} belongs to \mathcal F and satisfies

This follows from the Sobolev chain rule for the Euclidean norm and Cauchy–Schwarz.

To see that \mathcal A is closed, let u^{(j)}\in\mathcal A converge to u, and choose corresponding f_j\in\mathcal F. Their H^1 norms are bounded. Since all supports lie in a fixed bounded set, weak H^1 compactness and compactness in L^2 give a subsequence converging weakly in H^1 and strongly in L^2 to a member f of \mathcal F. Lower semicontinuity gives E_i(f)\le u_i for every i.

If c=\kappa^2(1,\ldots,1) did not belong to \mathcal A, strict separation would give a nonzero w\in\R^m with

The upper-set property forces every w_i to be nonnegative. For \epsilon>0 let Q_\epsilon=\diag(w_i+\epsilon). By (17), taking absolute values and normalizing does not change the Rayleigh infimum, so

Letting \epsilon\downarrow0 contradicts separation. This argument also covers zero components of w. Thus c\in\mathcal A, as required.□

Proof. The endpoints are immediate, so suppose 0<\alpha<1 and write D_\alpha=(1-\alpha)D_0+\alpha D_1. Fix 0<\eta<1, set r=1-\eta, and put

These are compact convex sets, and A_\alpha\subset D_\alpha: indeed, A_\alpha\subset r\overline{D_\alpha}, which is compactly contained in D_\alpha.

Let W start at zero with Brownian covariance rate 2Q. On a finite grid of positive times in [0,T], its values form a Gaussian vector. Gaussian log-concavity [19, Theorem 2] shows that

Here the Minkowski average of the two grid events is contained in the grid event for A_\alpha. Increase the grids to a dense subset of [0,T]. Closedness of the A_i and continuity of Brownian paths allow passage to the decreasing limits of these events. Since rD_i\subset A_i and A_\alpha\subset D_\alpha, it follows that

Lemma 2.4, followed by the scaling of the Dirichlet quotient, now gives

Finally let \eta\downarrow0.□

Proof. Lift K to the bounded open convex set

Let P be its projection onto \R^m. For y\in P, its vertical fiber I_y=\{s:(y,s)\in B\} is a nonempty open interval. Write L(y)=|I_y|. Convexity gives

Thus L is positive, concave and continuous on the open convex set P. The vertical Steiner symmetrization of B is

This set is bounded, open and convex. Symmetry of K implies L(-y)=L(y), so B^* is symmetric separately in y and in s. For s\ge0 put

Then 0<b\le\ell. Each D_s with 0\le s<b is a nonempty bounded open convex set symmetric about zero, and these domains decrease as s increases.

The section D_1 is the target because each of its points permits the required shifted signed step. Indeed, for any y\in D_1, write I_y=(a,b_0). Its length exceeds two. Choose c\in(a+1,b_0-1); then

For |q|\le\delta, we have |c-q|<7/4<2. If q\le c, then q+1 lies in [c-1,c+1]; if q\ge c, then q-1 lies in that segment. Thus one of q+1,q-1 lies in the original open fiber, giving membership in K itself. It remains to prove that D_1 is nonempty and has the same spectral bounds as K.

Choose f from Lemma 3.1, and define

Translation invariance and Fubini give

Only derivatives in the horizontal variable y will be used.

Rearrange each nonnegative fiber \Psi(y,\cdot) into an even function nonincreasing in |s|, denoted \Psi^*(y,\cdot). A jointly measurable version is obtained from the measurable superlevel lengths \mu(y,u)=|\{s:\Psi(y,s)>u\}| by replacing each superlevel set with its centered interval of length \mu(y,u). This preserves the L^2 norm. Since \Psi vanishes almost everywhere outside B, its rearrangement vanishes almost everywhere outside B^*.

For nonnegative a,b\in L^2(\R), the layer-cake formula gives

The intersection is bounded by the smaller of the two superlevel measures, and centered intervals attain that bound. Since rearrangement preserves the individual norms, \|a^*-b^*\|_2\le\|a-b\|_2. Applying this to the fibers at y and y+he_i, then integrating over y, bounds the horizontal difference quotients of \Psi^* by those of \Psi. Their weak limits yield

Sobolev slicing and Fubini therefore imply that, for almost every s, \Psi^*(\cdot,s)\in H^1(\R^m) and vanishes almost everywhere outside D_{|s|}. Each nonzero such slice belongs to H_0^1(D_{|s|}) by (17).

We next show that the rearranged density puts enough mass at heights above one. Its mean absolute height is

Indeed, a centered interval of length u has integral of |s| equal to u^2/4. Apply this to the superlevel intervals of \Psi^{*2} and use Tonelli; the factor (2\ell)^{-1} in \Psi^2 gives the displayed normalization. For nonnegative translates u,v of f, both of norm one,

Moreover,

It follows from (20) that

Under the probability density \Psi^{*2}(y,s), we have |s|<b almost surely; hence M<b. In particular, D_1 is nonempty.

It remains to pass the derivative bounds to this particular section. Fix a positive definite diagonal Q and put h_Q(s)=\lambda_Q(D_s) for 0\le s<b. This function is finite and nondecreasing. Convexity of B^*, domain monotonicity and Lemma 3.2 give

so h_Q is convex. Give s the probability density \rho(s)=\int \Psi^*(y,s)^2\,dy. Testing the Rayleigh quotient with each nonzero slice and then integrating, we obtain

This also proves the integrability needed for Jensen’s inequality. Since 1<M<b, monotonicity and Jensen give

The construction of D_1 is independent of Q, so every required spectral bound is preserved. Taking T_e(K)=D_1 proves the lemma.□

Proof of Proposition 2.1. Write the prescribed coordinate directions as e_{j_1},\ldots,e_{j_s}. Construct domains backwards by

Lemma 3.3 preserves all domain and spectral hypotheses. Each K_i therefore contains zero, and we may start with x^{(0)}=0\in K_0. Suppose x^{(i-1)}\in K_{i-1}, and set

Since q\in[-\delta,\delta], the lemma supplies \varepsilon_i\in\{-1,1\} with

Induction gives x^{(s)}\in K_s=K and the required signs. Distinctness of the coordinate directions ensures that later steps do not alter the preceding coefficient coordinates on which a shift depends. The backwards domains may depend on the entire input sequence, as allowed in the proposition.□

Proof. The function u\mapsto\log w(e^u)=\min\{au,-u\} is a-Lipschitz. Write r=y/x. For r<1, the two endpoint lower bounds give

The two expressions cross inside [y,x], by the same Lipschitz bound. Integrating them against du/u yields

For r>1, integration of the minimum of the corresponding endpoint upper bounds on [x,y] gives

Using 2\sqrt{w(x)w(y)}\le w(x)+w(y) in either case, we obtain

If b=a/2=3/4, then B(1)=B'(1)=0 and B''(r)=(1-b)r^{b-2}>0. Moreover B(0+)=1/b-1>0 and B(r)/r\longrightarrow1 at infinity. Thus, with an absolute positive constant,

The function rB(1/r) satisfies the same bounds, after changing c. Applying (31) with the arguments reversed therefore gives these bounds for both left sides of (30).

If f_0(x)\ne f_0(y), at least one argument belongs to [1/2,4]. When 1/2\le r\le2, both arguments lie in [1/4,8], where w is bounded below and 1+y is bounded above. The Lipschitz bound |f_0(x)-f_0(y)|\le2x|r-1| applies. When r\le1/2, one w value is bounded below and y\le4. When r\ge2, one w value is again bounded below, and either y\le4 or y=rx\le4r. The preceding three bounds, together with |f_0(x)-f_0(y)|\le1, prove the result. If the cutoff values are equal, the right sides vanish and the result follows directly from (31).□

Proof. Let P_s be the coordinate projection onto the initial block and the first s new coordinates, and put

Diagonality of Q makes these nonnegative matrices with disjoint coordinate supports. Since R_tP_s=\mathcal C R_s, the support identities are

We split the right weight into I_m+Q_{\rm old} and Q_{\rm new}, and use the intermediate matrix \widetilde F=R_t^\top f_0(Z)R_t for the first part.

The old state under contraction. Choose orthonormal eigenbases of Z and Y, with eigenvalues z_i and y_j. Let m_{ij} be the squared entries of \mathcal C in these bases. Its row and column sums are at most one; denote their deficits by

The matrix n_{ij}=m_{ij}y_j/z_i has both row and column sums one. For rows this follows from Z=\mathcal C Y\mathcal C^\top; for columns it follows from the identity

which uses invertibility of \mathcal C.

Expanding the weighted squared distance with (33), its two diagonal terms are \tr(f_0(Z)^2(I_d+Z)) and \tr(f_0(Y)^2(I_d+Y)). The cross term, before multiplication by two, is \sum_{ij}m_{ij}(1+y_j)f_0(z_i)f_0(y_j). Since \sum_jm_{ij}y_j=z_i, this gives the exact expansion

Expanding \mathcal J instead, the two stochastic sums of n and the relation n_{ij}z_i/y_j=m_{ij} yield

The second inequality of Lemma 4.2 controls the double sum in (34). The remaining terms are controlled by the deficits in (35), since both f_0(u)^2 and (1+u)f_0(u)^2 are bounded by an absolute multiple of w(u). This proves the required bound for \widetilde F-F_s.

The accumulated gain. Now choose eigenbases of X and Z, with eigenvalues x_i and z_j, and let m_{ij} be the squared entries of their orthogonal change of basis. Both sums of m equal one. Set n_{ij}=m_{ij}z_j/x_i. Its row sums are at most one by Z\preceq X, and its column sums are at most one by X^{-1}\preceq Z^{-1}: explicitly, for a unit z_j-eigenvector v_j,

Write d'_i,h'_j for these row and column deficits. Expansion of \mathcal J now gives

The coisometry R_tR_t^\top=I_d and (33) show that

The first inequality of Lemma 4.2 controls this by (36).

It remains to include the new-coordinate part of the right weight. By (33), it is exactly

Here x_id'_i is the ith diagonal entry of X-Z in the X-eigenbasis. The bound u f_0(u)^2\le Cw(u) controls this term by the row deficits in (36). Finally apply the squared triangle inequality to (F_t-\widetilde F)+(\widetilde F-F_s) with the old weight, and add (37). This proves (32).□

Proof. Follow the old and new parts separately through the interval [s,t]. Start with (Z_*,V_*)=(Y,0). At each contraction, replace both matrices by their congruences under C_i. At each gain, add the positive semidefinite gain to V_* only, interpolating linearly during this addition. At every stage D=Z_*+V_* is the matrix in the original contraction-and-gain path; at the endpoint (Z_*,V_*)=(Z,V).

Define

The use of I_d+Z_* makes this quantity stable under contractions. We will show that its increases during gains are paid for by the p_1 part of the energy.

Contractions do not increase G. For a contraction C, put S'=I_d+CZ_*C^\top and T_c=(S')^{-1/2}CS^{1/2}. The new relative matrix is A'=T_cAT_c^\top. Moreover

Thus the ordered eigenvalues of A' are no larger than those of A; for example, compare the singular values of T_cA^{1/2} and A^{1/2}. Raising these nonnegative eigenvalues to the power a and summing proves \tr(A')^a\le\tr A^a. This argument uses eigenvalue comparison, not operator monotonicity of the power a.

The derivative during a gain. Here S is fixed and \dot V_*\succeq0. Introduce

Since I_d-H=J^{-1/2}SJ^{-1/2} is positive definite,

Write the polar decomposition as T=U(I_d-H)^{-1/2}, where U is orthogonal. Then

In particular, the eigenvalues of A are h/(1-h), where h ranges over the eigenvalues of H.

For a continuously differentiable scalar function g on the spectral range of a differentiable symmetric matrix path A(\xi), \frac{d}{d\xi}\tr g(A)=\tr(g'(A)\dot A). One can verify this first for polynomials by cyclicity of the trace, then approximate g' uniformly by polynomials and integrate along the path. Applied to g(u)=u^a, this gives

This formula remains valid when A is singular, because u\mapsto u^a is continuously differentiable at zero for a>1. The coefficient in this trace has the exact conjugation identity

The second equality follows from (39) and the polar decomposition. The factors on its right commute because they are functions of H; no commutation of Z_* and V_* is assumed.

As long as G\le1, every eigenvalue of A is at most one, so (39) gives H\preceq I_d/2. Since a-1=1/2, spectral calculus in H then gives

Also V_*\preceq D, and hence

The square root preserves positive semidefinite order. One direct proof is the convergent integral formula

the integrand preserves order because M(uI_d+M)^{-1}=I_d-u(uI_d+M)^{-1} and inversion reverses order. It follows that

Conjugating (41) back by J^{-1/2} yields

Pair this inequality with \dot V_*\succeq0 in (40). Since \dot D=\dot V_* during a gain, we obtain the conditional differential bound

Closing the bound. Initially G=0, and contractions cannot increase it. The sum of all increases of \tr p_1(D) during gains is at most E, by (27). If G first reached one during a gain, integration of (42) up to that point would give G\le c_aE\le1/16, a contradiction. Thus the differential bound applies throughout, and G\le c_aE at the endpoint. In particular,

If E=0, this already gives V=0 and the second conclusion in (38). Suppose now that q>0.

The ordered eigenvalues of X and Z obey

because X-Z=V\preceq q(I_d+X). For a corresponding pair x,z, if x\le4q\le1, then

If x>4q, then z\ge x/2 and x-z\le q(1+x). On [x/2,x] we have w(u)\le2^aw(x) and u^{-1}\le2/x, so

The last inequality holds for both x\le1 and x\ge1 directly from (24). Summing over the eigenvalues proves the trace bound in (38).□

Proof of Lemma 4.1. The total variation of \tr p along the separate contraction and gain steps from s to t is at most E. Therefore

Together with Lemma 4.4, this bounds the sum on the right of (32) by

Since 0\le E\le e_0\le1, we have E\le E^{1/a}. Lemma 4.3 now proves (29), including E=0.□

Proof. The Gaussian density and its reciprocal are bounded on D, so the Gaussian and Lebesgue H_0^1 form domains agree. Integration by parts identifies the displayed form with the killed Ornstein–Uhlenbeck semigroup P_T^D. Its L^2(\gamma_m) operator norm is e^{-T\lambda_Q^{\mathrm{OU}}(D)}. The killed-semigroup representation used in Lemma 2.4 therefore gives

This proves the first inequality. Equivalently, the representation follows from the Dirichlet Feynman–Kac formula after the conjugation below; its potential is bounded on D [14].

Write \rho(x)=(2\pi)^{-m/2}e^{-|x|^2/2} and put g=h\sqrt\rho. For h\in C_c^\infty(D), expansion and integration by parts give

The identity extends by form closure to H_0^1(D). Multiplication by \sqrt\rho maps this space bijectively to itself and preserves the corresponding L^2 norms. Since the potential is at least -\tr Q/2, taking Rayleigh infima proves the second inequality.□

Proof. We may omit indices with F_t=0. By (26), every remaining index has k_t\ge1/4. Divide these indices into the classes

We first bound the expected supremum within one nonempty class, writing k=K_j.

Stationarity, coisometry and (26) give

For two indices in the class, Lemma 4.1, with the indices put in chronological order, implies

Here we dropped the positive right weight in that lemma and used 1+k_t\le6k. For time increments at a fixed index,

so that

This trace identity uses R_tR_t^T=I; it does not require Q and F_t to commute.

We give the elementary chaining argument for the two parameters. Choose H so that h_t\in[H,H+e_0] for every index under consideration, and put \alpha=(h_t-H)/e_0 and \beta=\theta(\tau-u) in [0,1]. Split a mixed increment into an index increment and a time increment. Equations (46) and (47) bound its second moment by

where \alpha is the normalized energy coordinate; the constant absorbs e_0\le1. At depth l, divide both parameter intervals into dyadic cells of width 2^{-l} and choose a representative from each occupied product cell. There are at most C4^l representatives. The increment from each representative to that of its parent cell is a centered Gaussian vector with second moment at most

For use here, if G_1,\ldots,G_M are arbitrarily dependent centered Gaussian vectors and \mathbb E\lVert G_i\rVert^2\le v, then

Indeed, for v>0, diagonalizing the covariance of G_i gives \mathbb E e^{\lVert G_i\rVert^2/(4v)}\le e^{1/2}, because its eigenvalues are nonnegative and sum to at most v. Bound the exponential of the maximum by the sum of the exponentials, then use Jensen’s inequality and Cauchy–Schwarz. The case v=0 is immediate.

Apply (48) to the increments at each depth. Starting with (45) and summing the parent increments gives an absolute C_0 such that

To justify convergence of the representatives, note that there are only finitely many distinct energy values. If h_t=h_s, Lemma 4.1 gives F_t=F_s exactly. At sufficiently fine depth a target index therefore has the same filter as its representative, and the representative times converge to its target time. Continuity of U completes the passage to the supremum. Equivalently, one may first use finite time grids and then increase them to a dense set. Neither argument uses a lower bound on the positive gaps between energy values. In particular, the number of indices does not enter (49).

It remains to control all the k classes at once. On a finite time grid the supremum S_j in (49) is a maximum of Gaussian vector norms. Represent the joint Gaussian vectors as linear images of one standard Gaussian vector. Each corresponding linear map has norm at most one because its output covariance is F_t^2\preceq I, by (26); consequently S_j is a 1-Lipschitz function of that standard Gaussian vector. Equivalently, it is a supremum of scalar Gaussian functionals, each with variance at most one.

Markov’s inequality and (49) give \mathbb P\{S_j\le2C_0\sqrt{K_j}\}\ge1/2. Borell’s Gaussian enlargement inequality [9, Theorem 3.1], applied to this sublevel set, gives

where \Phi is the standard normal distribution function. The same bound holds for the full time supremum by increasing dense grids and path continuity. Choose c_1>2C_0. The probability that any constraint in class j exceeds c_1\sqrt{k_t} is at most

With A=(c_1-2C_0)^2/8, the sum of these bounds is at most

once c_1 is an absolute constant large enough that A\ge\log3. This proves (44). Restricting the time interval can only increase its probability.□

Proof of Proposition 2.2. Fix d,n,Q and the entire recursion. Let \Theta be the finite set of dyadic scales for which some F_t^\theta is nonzero. If q_{\min} and q_{\max} are the smallest and largest diagonal entries of Q, then coisometry gives q_{\min}I\preceq L_t\preceq q_{\max}I, and the support of f_0 gives

At each scale, partition the sequence indices by the half-open intervals

containing E_\theta(0,t). These are the energy intervals to which Lemma 5.2 applies. There are at most C(1+E_\theta(0,n)) nonempty intervals, including any repetitions of an energy value in the same interval.

For each fixed t, the scale constraints control the original state norm. To see this, diagonalize L_t and write y=R_tU(\tau) in this eigenbasis, with eigenvalues \lambda_i>0. Each \lambda_i admits a dyadic scale with \lambda_i/\theta\in[1,2], where f_0=1; that scale belongs to \Theta. Since R_t^T is an isometry,

Thus all the scale constraints at a given time imply, by (25),

with an absolute C_\phi.

We also impose coordinate bounds. A stationary scalar Ornstein–Uhlenbeck process of rate q>0, restricted to an interval of length at most 1/q, stays in [-2,2] with probability at least an absolute p_0>0. By stationarity and time rescaling, it suffices to consider rate one on [0,1]. In distribution that process is

where Z is standard normal and B is an independent standard Brownian motion. The event |Z|\le1 and \sup_{r\le e^2-1}|B(r)|\le1 has a fixed positive probability and implies the asserted bound.

Choose absolute constants

and let \mathcal D be the domain in Proposition 2.2 with these constants. It is bounded, open, centrally symmetric and convex, and contains a neighborhood of zero. The closed constraints (52) and |U_j(\tau)|\le2 lie strictly inside \mathcal D.

For a fixed T>0, cover [0,T] by at most 1+T\theta consecutive closed intervals of length at most 1/\theta at scale \theta. For every such interval and every nonempty energy interval impose the event in Lemma 5.2. Also cover [0,T] by at most 1+TQ_{jj} intervals of length at most 1/Q_{jj} for coordinate j and impose its box event. All these events are closed symmetric convex constraints on linear evaluations of the centered Gaussian path. There are finitely many events for this fixed input and T. Lemma 2.5 therefore multiplies their probability lower bounds. In particular, its finite-grid argument and the continuity of the paths apply even when some constraints are duplicates. The strict slack just chosen ensures that their intersection is an event of survival in the open domain \mathcal D.

It follows that

Here (28) and (50) bound the coefficient of T by an absolute constant times \tr Q, and

This additive constant may depend on the input and on the smallest entry of Q; no uniform bound on it is required.

By Lemma 5.1,

Let T tend to infinity while keeping the input fixed. This removes the additive constant, including the number of spectral scales. The second inequality in (43) now gives

Thus H_0=C'+1/2 is absolute. The constants A_0,B_0,H_0 are independent of d,n,Q and of the recursion, as required.□

Proof. For 1\le p\le2, the norm comparisons

allow direct application of Theorems 1.1 and 1.2, followed by the bound C d^{1/p} on all prefixes. For 2\le p\le\infty, use

Divide the input vectors by d^{1/2-1/p}, apply the corresponding Euclidean theorem, and scale back to obtain C d^{1-1/p}. Scaling preserves the zero sum, and in each case the one signing or permutation controls all prefixes. At p=\infty this gives Cd.

For the lower bounds, let 1\le p\le2. The ordered standard basis e_1,\ldots,e_d has final signed sum of norm d^{1/p} for every signing. For the ordering problem, take e_1,\ldots,e_d and d copies of w=-\tfrac1d(1,\ldots,1). This indexed family sums to zero and lies in the unit ball, since \lVert w\rVert_p=d^{1/p-1}\le1. If d\ge2, consider any permutation and its prefix just after the k=\lfloor d/2\rfloor-th basis vector. If t copies of w have appeared, put a=t/d\in[0,1]. The prefix sum s has k coordinates equal to 1-a and d-k equal to -a. Since both k and d-k are at least d/3, convexity gives

Thus \lVert s\rVert_p\ge\tfrac12(2d/3)^{1/p} \ge\tfrac13d^{1/p}, for every permutation. When d=1, the family is (1,-1) and either permutation has a prefix of norm one.□

Proof. For an arbitrary k\times n array B=(b_i^j) in the Euclidean unit ball B_2^d, with no zero-sum condition, list its entries column by column:

Apply Theorem 1.1 to this sequence of length kn. With \varepsilon_i^j=\varepsilon_{(i-1)k+j}, every complete-column prefix satisfies

This is the column-major reduction in the proof of [7, Lemma 2.1], with the present signed-prefix bound in place of its dimension-linear bound. Thus Bárány’s matrix signed constant satisfies V(B_2^d)\le C\sqrt d, uniformly in k,n. Here V allows an entrywise signing of an arbitrary array, whereas the row-permutation constant U ranges over total-zero arrays and controls the same aggregate prefixes. His transference theorem [7, Theorem 2.2] gives U(B_2^d)\le2V(B_2^d) for every number of rows. Shorter auxiliary arrays may be padded with trailing zero columns when using the bound uniformly in the number of columns. Since B_2^d is a centrally symmetric convex body, this gives the asserted bound.□