Proof. Rotation invariance reduces the projection to the first \(k\) coordinates. Let \(G\in\mathbb R^k\) and \(H\in\mathbb R^{D-k}\) be independent standard Gaussian vectors. Then \((G,H)/\sqrt{\left\lVert G\right\rVert^2+\left\lVert H\right\rVert^2}\) is uniform on the sphere. The random variables \(\left\lVert G\right\rVert^2/2\) and \(\left\lVert H\right\rVert^2/2\) are independent unit-scale gamma variables of shapes \(k/2\) and \((D-k)/2\). Changing variables from these two positive numbers to their sum and their first fraction shows that the fraction has density \[\frac{\Gamma(D/2)} {\Gamma(k/2)\Gamma((D-k)/2)} t^{k/2-1}(1-t)^{(D-k)/2-1},\qquad 0<t<1.\] The direction of \(G\) is uniform and independent of these lengths. Polar coordinates in \(\mathbb R^k\), with \(\operatorname{vol}(S^{k-1})=2\pi^{k/2}/\Gamma(k/2)\), now give (1). The surface-area identity itself follows by integrating \(e^{-\left\lVert x\right\rVert^2}\) in polar coordinates. The direction of \(H\) is uniform and independent of both lengths and of \(G\), which proves the conditional assertion. The event \(H=0\) is null. ◻

Proof. On the ball of radius \(\sqrt k\), the function \(e^{-\left\lVert z\right\rVert^2/2}\) is at least \(e^{-k/2}\). Comparing its integral there with the full Gaussian integral gives \[e^{-k/2}k^{k/2}v_k \le\int_{\mathbb R^k}e^{-\left\lVert z\right\rVert^2/2}\,dz=(2\pi)^{k/2},\] which is the claimed bound. ◻

Proof. For \(r\le1\), rotate \(c\) to the north pole. A sphere point in \(B(c,r)\) has last coordinate at least \(1-r^2/2\ge1/2\). Its surface element as a graph over \(c^\perp\) is at most twice Lebesgue measure, and its projection lies in the \(n\)-ball of radius \(r\). The full sphere has area at least twice the volume of the unit \(n\)-ball, by projecting both hemispheres. This proves the upper bound for \(r\le1\); total mass one proves it for \(r>1\).

For the lower bound when \(r\le1\), the angular radius \(2\arcsin(r/2)\) is at least \(r\). In polar angle the cap mass is the integral of \(\sin^{n-1}\theta\) over this interval divided by its integral over \([0,\pi]\). Use \(\sin\theta\ge2\theta/\pi\) for \(0\le\theta\le r\) and bound the denominator by \(\pi\). Since \(n\le2^{n-1}\), the result is at least \((r/\pi)^n\). For \(1\le r\le2\), monotonicity therefore gives the lower bound with \(a=1/(2\pi)\).

If an ambient ball meets the sphere, choose \(c\) in the intersection. Its sphere portion is contained in \(B(c,2r)\), proving (4); an empty intersection is immediate. Finally, angular error at most \(\epsilon\) implies chordal error at most \(\epsilon\), because \(2\sin(\theta/2)\le\theta\). Apply the sphere-centered upper bound to each fixed output and then integrate over any independent output randomization. ◻

Proof. First suppose the rule includes a fresh seed of law \(\kappa\). Each completed-product measurable coordinate has a product-measurable version: approximate it by simple functions and replace the countably many level sets by product-measurable sets modulo null sets. Replace the resulting finite vector by a fixed point mass wherever it fails to be a probability vector. This repair occurs on a product-measurable null set. Integrating against \(\kappa\) now gives a Borel probability vector in the current pair, and Fubini shows agreement with the original integrated rule for \(\lambda\)-almost every pair. It therefore suffices to consider the coordinate probabilities in the first statement.

For each fixed state and index, combine the possible transitions and stops into a finite set of destinations, tagged as continuing or stopping. Choose Borel versions of their coordinate probabilities by the same simple-function construction. On the Borel null set where the versions fail to be nonnegative or to sum to one, replace the vector by a fixed point mass. Finitely many states and indices are involved, so all changes lie in one Borel \(\lambda\)-null set \(Z\).

For every nonzero feature \(x\), Lemma 1 gives a Lebesgue density for \(\langle x,S\rangle\). Since a Gaussian feature is nonzero almost surely, every pre-generated pair \((X_t,\langle X_t,S\rangle)\) has law absolutely continuous with respect to \(\lambda\). Thus each pair avoids \(Z\) almost surely. Even if the current state depends on previous observations, the probability of being in a particular state and seeing a pair in \(Z\) is bounded by the marginal probability of seeing that pair in \(Z\), which is zero.

Almost surely none of the finitely many pre-generated pairs lies in \(Z\). Couple the original and modified finite destination kernels by the same fresh uniform random numbers. Induction gives identical state paths and stopping decisions; couple their unchanged terminal output laws identically as well. This proves equality of the specified joint laws. Finally, finite composition and integration of the Borel kernels against independent future features and coins defines a measurable continuation from every specified state and index, including unreachable states. ◻

Proof. Let \(F\) be the row span of the pre-generated feature matrix and put \(u=P_FS\). Its dimension is \(T\) almost surely, with the evident interpretation for \(T=0\). The labels determine \(u\). For \(T=0\), the residual is the original uniform signal. For \(T>0\), Lemma 1, applied after fixing the feature matrix, shows that conditional on all the data the residual is \(\sqrt{1-\left\lVert u\right\rVert^2}\,\omega\), with \(\omega\) uniform on the unit sphere of \(F^\perp\). Before conditioning on the labels, isotropy gives \(\mathbb E\left\lVert u\right\rVert^2=T/d\). Consequently \(\mathbb P\{\left\lVert u\right\rVert^2\ge1/2\}\le2T/d\).

When \(\left\lVert u\right\rVert^2<1/2\), opposite residual directions give two signals at distance \(2\sqrt{1-\left\lVert u\right\rVert^2}>\sqrt2>2\epsilon\). They have the same conditional law, and at most one can be within chordal distance \(\epsilon\) of a fixed output. Angular success implies this chordal condition, so conditional success is at most \(1/2\), also after averaging independent estimator randomness. Total success is at most \[\frac12+\frac12\mathbb P\{\left\lVert u\right\rVert^2\ge1/2\} \le\frac12+\frac Td\le\frac58.\] Giving the estimator all pre-generated data also covers a learner that stops at a prefix, with its independent shared and fresh randomness. ◻

Proof. Right rotational invariance allows us to replace the fixed columns of \(E\) by an independent uniform orthonormal frame. Conditional on \(P\), its projection has the same law as the first \(k\) coordinates of that frame. Sample the full columns successively and let \(Z_j\) be the matrix of the first \(k\) coordinates of its first \(j\) columns. Set \[S_j=I_k-Z_jZ_j^{\mathsf T},\qquad S_0=I_k.\] Given the preceding full columns, the next column is uniform on the unit sphere in their \(d-j\)-dimensional orthogonal complement. The coordinate map from that complement to the first \(k\) coordinates has row Gram matrix \(S_j\). When \(S_j>0\), multiplication by \(S_j^{-1/2}\) makes its rows orthonormal. Lemma 1 and a linear change of variables therefore give the next projected column \(z\) conditional density \[c(d-j,k)(\det S_j)^{-1/2} (1-z^{\mathsf T}S_j^{-1}z)^{(d-j-k-2)/2}\] on \(z^{\mathsf T}S_j^{-1}z<1\). This expression depends only on \(Z_j\), so it is also the conditional density given those projected columns. The strict inequality implies \(S_{j+1}=S_j-zz^{\mathsf T}>0\) almost surely. The determinant identity \[\det S_{j+1}=\det S_j(1-z^{\mathsf T}S_j^{-1}z)\] shows that multiplication of the \(m\) conditional densities cancels every intermediate determinant. The remaining factor is \(\det S_m^{(d-k-m-1)/2}\), proving (5). Its exponent is nonnegative and \(0<\det S_m\le1\).

The normalizing constants have the stated scale. For a unit-scale gamma variable \(G\) of shape \(a=(d-j-k)/2>0\), Cauchy–Schwarz and the gamma recurrence give \[\frac{\Gamma((d-j)/2)}{\Gamma((d-j-k)/2)} =\mathbb EG^{k/2} \le(\mathbb EG^k)^{1/2} =\left(\prod_{i=0}^{k-1}(a+i)\right)^{1/2} \le d^{k/2}.\] Together with the factor \(\pi^{-k/2}\), this bounds each \(c(d-j,k)\) by \((C\sqrt d)^k\).

For the last assertion, Gram–Schmidt writes \([x_2-x_1,\ldots,x_{m+1}-x_1]=ER\), where \(E\) has orthonormal columns and \(R\) is triangular with \(\left\lvert \det R\right\rvert=\prod_{i=2}^{m+1}\delta_i\). Right multiplication by \(R\) on \(k\)-by-\(m\) matrices has Jacobian \(\left\lvert \det R\right\rvert^k\), one factor for each row. Applying this change of variables to the preceding density proves (6). ◻

Proof. For \(0<t\le R\), the projection of \(B(z,R)\) onto \(F\) is contained in a \(j\)-ball of radius \(R\). A maximal \(t\)-separated subset is a \(t\)-net with at most \((3R/t)^j\) points, by packing disjoint \(j\)-balls of radius \(t/2\). For \(j=0\), one point suffices. The corresponding ambient balls of radius \(2t\) cover the points of \(B(z,R)\) within distance \(t\) of \(F\). Thus \[ \nu\{\operatorname{dist}(x,F)\le t\}\le 3^j2^\beta K R^j t^{\beta-j}. \tag{9}\] Because \(\beta-j>0\), continuity from above as \(t\downarrow0\) gives \(\nu(F)=0\). Distances greater than \(R\) contribute at most \(R^{-k}\nu(B(z,R))\le KR^{\beta-k}\). On the shell \(2^{-h-1}R<\operatorname{dist}(x,F)\le2^{-h}R\), (9) gives a contribution at most \[3^j2^{\beta+k}KR^{\beta-k}\,2^{-h(\beta-j-k)}.\] The sum over \(h\ge0\) is at most twice its first term. Since \(\beta,j,k\le d\), the resulting factor is bounded by \(C^d\). ◻

Proof. When \(K=0\), the measure is zero and the assertion is immediate. For \(K>0\), let \(v_k\) be the unit-ball volume and define \[g_\delta(P,u)=\frac{\nu\{x:\left\lVert Px-u\right\rVert\le\delta\}}{v_k\delta^k}.\] These are jointly measurable nonnegative functions. Expanding their \(q\)th powers and using Tonelli’s theorem expresses the integrated moment through \(q\) points \(x_1,\ldots,x_q\) drawn from \(\nu\). The intersection of the \(q\) label balls of radius \(\delta\) has volume at most \(v_k\delta^k\); it is empty unless \(\left\lVert P(x_i-x_1)\right\rVert\le2\delta\) for \(i\ge2\).

Put \(\delta_i=\operatorname{dist}(x_i,\operatorname{aff}(x_1,\ldots,x_{i-1}))\). Lemma 9 shows that every affine plane encountered here has zero \(\nu\)-mass: its dimension is at most \(q-2\), so the last condition in (10) applies. Consequently the tuple is affinely independent for \(\nu^{\otimes q}\)-almost every choice. For such a tuple, Lemma 8 applies with \(m=q-1\); the condition \(k+q\le d\) is exactly its determinant condition. The probability of all \(q-1\) inequalities is bounded by \[(C\sqrt d)^{k(q-1)} \prod_{i=2}^q\delta_i^{-k} \bigl[v_k(2\delta)^k\bigr]^{q-1}.\] The label-ball volumes cancel those in the definition of \(g_\delta\). Absorbing \(2^{k(q-1)}\) in \(C\), we obtain \[ \int\!\!\int g_\delta^q\,du\,d\vartheta_{d,k} \le (C\sqrt d)^{k(q-1)} \int\prod_{i=2}^q\delta_i^{-k}\,d\nu^{\otimes q}. \tag{12}\] The degenerate tuples form a null set and can be assigned an infinite upper bound in this nonnegative integral.

Integrate first in \(x_q\), then in \(x_{q-1},\ldots,x_2\). At each step Lemma 9 bounds the current factor by \(C^d K R^{\beta-k}\). The remaining first-point mass is at most \(KR^\beta\). Hence the last integral in (12) is at most \[C^{d(q-1)}K^qR^{q\beta-k(q-1)}.\] This proves the \(q\)th power of (11) uniformly in \(\delta\).

Define \(g(P,u)=\liminf_{j\to\infty}g_{1/j}(P,u)\). The assumed absolute continuity and Lebesgue differentiation (Tao 2011, Theorem 1.6.19, pp. 146–147) imply that, for almost every \(P\), this is a density of \(P_\#\nu\) for almost every \(u\). Fatou’s lemma on the product space (Tao 2011, Corollary 1.4.47, p. 110) gives (11). If \(\left\lVert u-Pz\right\rVert>R\), sufficiently small label balls miss \(P(B(z,R))\), since \(P\) is a contraction; the displayed version is then zero. This limiting calculation concerns the exact projected measure. It introduces no noise into an observation. ◻

Proof. Restriction preserves the stated all-ball bound. For every \(P\), the projection of \(\sigma\) is absolutely continuous by Lemma 1, so the same holds for the restricted weighted measure. The exact margins are \[k+q=2\lfloor d/4\rfloor\le d,\qquad \beta-k-(q-2)=d+1-3\lfloor d/4\rfloor\ge d/4+1.\] Thus Theorem 10 applies. This also records the nonnegative frame-determinant exponent \((d-k-q)/2=(d-2\lfloor d/4\rfloor)/2\). ◻

Proof. Right rotational invariance of \(X\) makes \(P\) have law \(\vartheta_{d,k}\); the independence assertion about \(P,H\) used later is proved below. The exact determinant and inverse-distance margins are \[k+p=2\lfloor d/16\rfloor\le d,\qquad \lambda-k-(p-2) =\frac{d-1}{2}-2\lfloor d/16\rfloor+2 \ge\frac{3d}{8}+\frac32.\] Apply Theorem 10 with \(q=p\), \(\beta=\lambda\), \(K=D^d\), and \(R=1\). If \(\ell(P,z)\) is its Lebesgue density, then \(g_X(z)=v_k\ell(P,z)\) is the required normalized density. Moreover \[\left(\mathbb E_X\int g_X^p\,dm_k\right)^{1/p} =v_k^{1-1/p}\left\lVert \ell\right\rVert_{L^p(\vartheta_{d,k}\,dz)}.\] Use the unit-ball volume estimate (2). Since \(k\ge d/32\) for sufficiently large \(d\), \[v_k^{1-1/p}(C\sqrt d)^{k(1-1/p)}\le C^d.\] Theorem 10 now bounds the normalized \(L^p\) norm by \(\exp(C_Dd)\), proving (14). The density version and its support are inherited from that theorem. The mass-at-most-one and absolute-continuity hypotheses have been retained explicitly. ◻

Proof. Full row rank holds almost surely because the rank-deficient matrices are the zero set of nonzero minors and the Gaussian law has a density. Right multiplication of \(X\) by a fixed orthogonal matrix leaves its law unchanged, fixes \(H\), and right-rotates \(P\). Let \(O\) be an independent uniform orthogonal matrix. For bounded measurable \(\phi,\psi\), invariance and averaging give \[\mathbb E[\phi(H)\psi(P)] =\mathbb E\!\left[\phi(H)\int\psi(PO)\,d\mu(O)\right],\] where \(\mu\) is uniform orthogonal probability. The inner integral is independent of \(P\): the right action on \(\mathcal V_{d,k}\) is transitive, and \(\mu\) is invariant. Its value is \(\int\psi\,d\vartheta_{d,k}\). This factorizes the expectation for all bounded measurable tests, which proves the stated law and independence. ◻

Proof. Write \(X=HP\) as in Lemma 13 and average the full radial dependence of the routing rule: \[\tau_w(P,u)=\mathbb E_H Q_w(HP,Hu).\] These are measurable nonnegative weights with \(\sum_w\tau_w\le1\). Independence gives the exact identity \[ f_{\mathrm{in}}(s)= \int\sum_w\tau_w(P,Ps)f_w(s)\,d\vartheta_{d,k}(P). \tag{16}\] Fix \(E=B(z,R)\), and let \(g_w(P,u)\) be the exact density in Corollary 11 for \(\mathbf 1_Ef_w\sigma\). After integrating (16) over \(E\), pushforward integration yields \(\int\!\int\sum_w\tau_w g_w\,du\,d\vartheta_{d,k}\). Each \(g_w\) is supported in \(\left\lVert u-Pz\right\rVert\le R\). On this domain the measure with density \(\tau_w\), relative to frame probability, label Lebesgue measure, and counting measure in \(w\), has total mass at most \(v_kR^k\). Hölder’s inequality therefore gives \[\int_E f_{\mathrm{in}}\,d\sigma \le (v_kR^k)^{1-1/q} \left(\sum_w\int\!\!\int\tau_w g_w^q\,du\,d\vartheta_{d,k}\right)^{1/q} \le (v_kR^k)^{1-1/q}N^{1/q}\max_w\left\lVert g_w\right\rVert_{L^q}.\] Substitute (13). The radius powers add exactly to \(\beta\). Also \(k\ge d/8\), so (2) gives \[v_k^{1-1/q}(C\sqrt d)^{k(1-1/q)}\le C_0^d.\] This proves (15). The original \(Q_w\) could use all entries of \(H\); only after that dependence was retained did we average it into \(\tau_w\). ◻

Proof. Use the fixed-seed and Borel-kernel convention of Section 2, and set \(n=d-1\) and \(\beta=n-q\). For each terminal state and stopping index, let \(h(s)\) be the success probability of its signal-independent output law. The cap estimates of Lemma 3 give \[\int_{B(z,R)}h\,d\sigma \le C^d\min\{R^n,\epsilon^n\} \le C^d\epsilon^q R^\beta \qquad(z\in\mathbb R^d,\ R>0).\] The last inequality follows from \(R\le\epsilon\) or \(R\ge\epsilon\), respectively. Thus the all-radii coefficient for every terminal function is at most \(K_0=C^d\epsilon^q\).

Divide the horizon into \(b\) blocks of \(k\) rows, padding the last block with independent rows ignored by its rules. Starting at a specified state and boundary index, define its continuation by a fresh future execution. This definition does not condition on that state being reached. The continuation functions are Borel and take values in \([0,1]\) by Lemma 6.

Within a block, a destination is either a continuing state at the next boundary or a terminal state tagged by its local stopping index. The possible local stopping indices are \(0,1,\ldots,k\), including an immediate stop. There are at most \((k+1)2^M\) terminal destinations and \(2^M\) continuing destinations, hence at most \(N_*\) in total. The global stopping index is determined by the fixed block start and this local index, so the terminal output retains its full allowed dependence on time.

Finite composition of the transition kernels produces Borel routing probabilities \(Q_w(X,y)\) for these destinations, with \(\sum_wQ_w\le1\). Their continuation functions \(f_w\) use only future independent rows and coins; terminal destinations use the functions \(h\) above. The incoming continuation therefore has precisely the form \[f_{\mathrm{in}}(s)=\mathbb E_X\sum_wQ_w(X,Xs)f_w(s)\] from Proposition 14. The Gaussian block is fresh: conditional on the fixed shared seed, its rows are jointly independent of the signal and entering state, which depends only on initialization, past pairs, and past coins.

Backward induction through the blocks multiplies the all-radii coefficient by at most \(C^dN_*^{1/q}\) per block. This factor is at least one, so the coefficient also bounds any earlier terminal option. Integrate the initial continuation over \(B(0,1)\) and average over the conditional initial-state law, which is independent of the signal and rows. Conditional success is at most the right side of (17). The bound is uniform in the fixed rules, so the shared-seed convention gives the same bound for the original learner. When \(T=0\), the terminal bound supplies the conclusion directly. ◻

Proof of Corollary 5 and first proof of Theorem 4. Put \(L=\log(1/\epsilon)\). Choose an absolute dimension threshold so that Proposition 15 applies and \(k=q\ge d/8\). If success is at least \(2/3\), (17) implies \[qL\le (b+1)d\log C +\frac bq\bigl(M\log2+\log(k+2)\bigr) +\log(3/2).\] Since \(b\le8T/d+1\) and \(\log(k+2)/q\) is bounded by an absolute constant, this gives an absolute \(C_1\) such that \[ dL\le C_1(T+d)\left(1+\frac M{d^2}\right). \tag{18}\] No bound on \(M\) was used. Lemma 7 forces \(T>d/8\), and hence \(T+d<9T\). Substitution into (18) proves Corollary 5 with an absolute constant.

Finally, if \(M(d)=o(d^2)\), then \(1+M(d)/d^2\le2\) for all sufficiently large \(d\). The corollary proves Theorem 4, with an absolute lower-bound constant and a dimension threshold that may depend on the memory sequence. This proof is uniform over the accuracy sequence and uses only within-block stopping indices. ◻

Proof. We prove a bound for nonnegative tests and then convert it into a countable positive domination.

Cap tests and their local mass. Put \(\rho_j=r2^{-j}\) and choose a finite \(\rho_j/2\)-net \(N_j\) of the sphere for every \(j\ge0\). Take as a dictionary the parent cap, indexed by \(*\), together with all \(B(c',\rho_j)\), \(c'\in N_j\). Repetitions may have separate indices. For this countable index set \(I\), write \(B_i=B(c_i,\rho_i)\) and \[\phi_i=\frac{\mathbf 1_{B(c_i,\rho_i)}}{\sigma(B(c_i,\rho_i))}, \qquad b_i=(r/\rho_i)^\alpha.\] Thus \(\phi_*\,d\sigma=\mu_{c,r}\), every \(\phi_i\) is a probability density, \(b_*=1\), and the weights at level \(j\) are \(2^{\alpha j}\). If \(h\in L^\infty(\sigma)\) is nonnegative and satisfies \[ \int h\phi_i\,d\sigma\le b_i\qquad(i\in I), \tag{23}\] then its integral against any positive dictionary sum is at most that sum’s weighted cost. We will bound \(\int h f_w\,d\mu_{c,r}\) for every such test.

Let \(\nu\) be the image of \(h\mu_{c,r}\) under \(s\mapsto(s-c)/r\). It has unit-ball support and mass at most one by the parent constraint. We claim that, for an absolute \(D\ge1\), \[ \nu(D(b,t))\le D^d t^\lambda \qquad(b\in\mathbb R^d,\ t>0). \tag{24}\] For \(0<t\le1/4\), suppose the ball meets the rescaled cap, and choose a point \(s_0\in B\) whose image lies in it. The corresponding sphere points are all within \(2rt\) of \(s_0\). Set \[j=\left\lfloor\log_2\frac1{4t}\right\rfloor,\qquad \rho=\rho_j; \qquad 4rt\le\rho<8rt,\quad \rho\le r.\] A center in \(N_j\) within \(\rho/2\) of \(s_0\) gives a dictionary cap containing those points, since \(2rt+\rho/2\le\rho\). Its constraint and the two-sided cap estimate imply \[\begin{align*} \nu(D(b,t)) &\le\frac{\sigma(B_i)}{\sigma(B)}\int h\,d\mu_{c_i,\rho_i}\\ &\le(A_0/a)^n(\rho/r)^{n-\alpha} \le(A_0/a)^n(8t)^\lambda. \end{align*}\] An empty intersection has zero mass. For \(t>1/4\), use the mass bound and \(1\le4^\lambda t^\lambda\). These estimates prove (24).

The quantitative test estimate. All hypotheses of Theorem 12 now hold for \(\nu\). Indeed, the test, parent cap, and measure are fixed before the fresh matrix \(X\) is drawn. For every orthonormal \(k\)-frame \(P\), the coordinate density in Lemma 1 gives \(P_\#\sigma\ll dz\). Because \(h\mu_{c,r}\ll\sigma\), its projection is also absolutely continuous, and the affine rescaling \[P((s-c)/r)=(Ps-Pc)/r\] gives the same conclusion for \(P_\#\nu\). The theorem therefore supplies a jointly measurable density satisfying, for almost every \(X\), \[P_\#\nu=g_Xm_k,\qquad g_X(z)=0\text{ for }\left\lVert z\right\rVert>1, \qquad \mathbb E_X\int g_X^p\,dm_k\le\exp(C_Ddp).\] The density is relative to \(dm_k=dz/v_k\) on the unit ball; \(D\), and hence the new constant, is absolute. Since \(s=c+ru\) gives \(Xs=Xc+rHPu\), Tonelli’s theorem and Hölder’s inequality on the product law of \(X\) and \(z\) yield \[ \begin{split} \int h f_w\,d\mu_{c,r} &=\mathbb E_X\int K_w(X,Xc+rHz)g_X(z)\,dm_k(z)\\ &\le\left(\mathbb E_X\int g_X^p\,dm_k\right)^{1/p} \left(\mathbb E_X\int K_w(X,Xc+rHz)^{p'}\,dm_k\right)^{1/p'}\\ &\le\exp(Cd)q_w^\theta,\qquad p'=p/(p-1). \end{split} \tag{25}\] The last line uses \(0\le K_w\le1\). Thus every test satisfying (23) obeys (25).

Representation by positive cap sums. The geometric estimate is complete; the remaining step uses only the dictionary and its test bound. If \(q_w=0\), the feasible test \(h=1\) shows that \(f_w\mu_{c,r}=0\), and the empty sum suffices. Otherwise set \(K=\exp(Cd)q_w^\theta>0\), with the constant from (25), and define in real \(L^1(\sigma)\) \[\mathcal C_K=\left\{\sum_{i\in I}a_i\phi_i: a_i\ge0,\ \sum_i a_ib_i\le K\right\}.\] Each series converges in \(L^1\), since \(b_i\ge1\) and \(\left\lVert \phi_i\right\rVert_{L^1}=1\). This convex set is norm compact. To see this, take a sequence and choose a coefficient array for each term. A diagonal subsequence converges coefficientwise, since \(0\le a_i\le K/b_i\). The limiting array has cost at most \(K\) by Fatou’s lemma. There are finitely many indices through every level \(J\), and uniformly over all admissible arrays, \[ \left\|\sum_{j>J}\sum_{i\text{ at level }j}a_i\phi_i\right\|_{L^1} =\sum_{j>J}\sum_{i\text{ at level }j}a_i \le K2^{-\alpha(J+1)}. \tag{26}\] The same estimate holds for the limiting array. Finite-level convergence followed by (26) gives convergence in \(L^1\). This proves sequential compactness, and hence compactness in the metric space \(L^1(\sigma)\) (Schnaubelt 2025, sec. 1.3, Theorem 1.37, p. 29).

Its signed downward closure \[\mathcal D_K=\{u\in L^1(\sigma):u\le v\text{ a.e. for some }v\in\mathcal C_K\}\] is convex, contains every nonpositive \(L^1\) function, and is norm closed. In fact, if \(u_m\to u\) and \(u_m\le v_m\in\mathcal C_K\), compactness provides a subsequence \(v_m\to v\in\mathcal C_K\); then \[\left\lVert (u-v)_+\right\rVert_{L^1} \le\left\lVert u-u_m\right\rVert_{L^1}+\left\lVert v_m-v\right\rVert_{L^1}\longrightarrow0.\] Put \(F=f_w\phi_*\). If \(F\notin\mathcal D_K\), strict separation of the closed convex set \(\mathcal D_K\) and the compact singleton \(\{F\}\) (Schnaubelt 2025, sec. 5.2, Theorem 5.20(b), pp. 98–99) gives a continuous real functional \(\ell\) with \[\ell(F)>\sup_{u\in\mathcal D_K}\ell(u).\] A probability measure is localizable (Fremlin, n.d.-a, Theorem 211L), so real \(L^1\)–\(L^\infty\) duality (Fremlin, n.d.-b, Theorem 243G(b)) represents \(\ell(u)=\int hu\,d\sigma\) for a real \(h\in L^\infty(\sigma)\). The finite supremum forces \(h\ge0\): if \(h\le-\delta\) on a set \(E\) of positive measure, the functions \(-t\mathbf 1_E\in\mathcal D_K\) would make it infinite. Define \[S_h=\sup_i\frac{\int h\phi_i\,d\sigma}{b_i},\qquad 0\le S_h\le\left\lVert h\right\rVert_{L^\infty}.\] Then \[ \sup_{u\in\mathcal D_K}\int hu\,d\sigma=KS_h. \tag{27}\] The cost bound gives the upper inequality, and the single terms \((K/b_i)\phi_i\) give the reverse inequality by taking the supremum over \(i\). This does not require the supremum to be attained. If \(S_h=0\), the parent term gives \(\int h\phi_*\,d\sigma=0\), and \(0\le f_w\le1\) implies \(\ell(F)=0\), contrary to strict separation. If \(S_h>0\), the function \(h/S_h\) satisfies (23), so (25) again contradicts separation. Therefore \(F\in\mathcal D_K\). An admissible series dominates its density almost everywhere; integrating gives the asserted measure inequality and cost bound. Its total mass is at most \(K\). ◻

Proof. Multiplication by a nonnegative measurable function preserves a measure inequality, as follows first for simple functions and then by monotone convergence. Summing over incoming states and cap terms therefore gives \[\eta'_w\le\sum_{v,i}a_{v,i}f_{v,w}\mu_{c_{v,i},r_{v,i}}.\] Apply Proposition 16 separately to every term. For a fixed incoming cap, write \(q_{v,i,w}\) for its reference probabilities. They depend on that cap as well as on the starting state, and satisfy \(\sum_wq_{v,i,w}\le1\). Hölder’s inequality for the finite sum gives \[\sum_wq_{v,i,w}^{\theta} \le\left\lvert \mathcal W\right\rvert^{1/p}\left(\sum_wq_{v,i,w}\right)^\theta \le2^{M/p}.\] If the outgoing terms for this parent have coefficients \(\beta_j\) and radii \(\rho_j\), their contribution to the global cost is bounded by \[\begin{align*} \sum_j a_{v,i}\beta_j(2/\rho_j)^\alpha &=a_{v,i}(2/r_{v,i})^\alpha \sum_j \beta_j(r_{v,i}/\rho_j)^\alpha\\ &\le a_{v,i}(2/r_{v,i})^\alpha\exp(Cd)q_{v,i,w}^\theta. \end{align*}\] Sum first over \(w\) and then over the countably many incoming terms to obtain (28). Tonelli’s theorem applies throughout because every summand is nonnegative.

At each of finitely many block boundaries there are only countably many state–cap terms. Choosing a dominating sum for each produces a deterministic proof representation, with another countable sum at the next boundary. There is no choice indexed by the random signal or by the fresh matrix. The state measures here remain unnormalized joint measures; the argument never divides them by their total masses. ◻

Proof. For a fixed unit output \(z\), write \(\vartheta=\arccos\langle z,s\rangle\). Angular success implies \(\left\lVert s-z\right\rVert=2\sin(\vartheta/2)\le\epsilon\). If \(\epsilon<r\), Lemma 3 bounds its probability under \(\mu_{c,r}\) by \[\frac{\sigma(B(z,\epsilon))}{\sigma(B(c,r))} \le(A_0/a)^n(\epsilon/r)^n \le\exp(Cd)(\epsilon/r)^\alpha.\] If \(\epsilon\ge r\), use probability at most one and \((\epsilon/r)^\alpha\ge1\). Integration over \(Q\) proves the result. ◻

Proof. Fix \(t>0\) throughout the argument and split its first \(t\) indices into \(b=\lceil t/k\rceil\) consecutive blocks of length at most \(k\). At a prefinal boundary retain only paths that have not stopped and are eligible to continue. In the final block retain exactly the paths stopping at \(t\), with their terminal state. For a fixed starting state and a supplied block of pairs, integrating the internal randomness gives the probability of each retained ending state. These are Borel kernels with sum at most one, since all omitted paths are discarded. A shorter block is padded by independent unused Gaussian rows, which the kernels ignore. Its likelihood for a signal \(s\) is therefore \(f_{v,w}(s)\) of (21). Conditional on the fixed seed, the fresh Gaussian feature rows in the block are jointly independent of the signal and entering state, indeed of the signal, initialization, past rows, and past coins. Given the signal, the past affects this likelihood only through the starting state and the fixed index.

At any counted boundary, let \(\eta_v(E)\) be the probability that \(S\in E\) and the path is counted in state \(v\). These are unnormalized joint measures and their outgoing laws have exactly the formula in Lemma 17. Initially, \(B(c,2)=S^{d-1}\) and \(\mu_{c,2}=\sigma\). Write \(V_0\) for the initial finite state. For the fixed shared seed \(\xi\), joint initialization independence gives \[\eta_v^\xi(E)=\pi_\xi(v)\sigma(E), \qquad \pi_\xi(v)=\mathbb P\{V_0=v\mid\xi\},\qquad \sum_v\pi_\xi(v)=1.\] Thus the initial total cost is one before any discarded paths are removed, and at most one afterward. After \(b\) applications of that lemma, the counted terminal measures admit positive cap dominations of total cost at most \([\exp(Cd)2^{M/p}]^b\).

At each fixed terminal state and index \(t\), the output is drawn from a fixed law using fresh randomness. Apply Lemma 18 to each term of its dominating cap sum. A term of coefficient \(a\) and radius \(r\) contributes at most \(\exp(Cd)(\epsilon/2)^\alpha a(2/r)^\alpha\). Summing proves the conditional version of (30). At \(t=0\), use the initial domination and the same terminal estimate directly. The index has been fixed throughout, so only the at most \(2^M\) states at each ending boundary were counted. No additional state is charged for the value of \(t\).

The countable dominating sums are chosen only after fixing the shared seed. The bound is uniform in that seed, so the common convention of Section 2 allows us to average the original conditional success probabilities. No measurable choice of cap decompositions across shared seeds is required. Finally, for \(M(d)=o(d^2)\) we eventually have \(M(d)\le d^2\). Since \(p\ge d/32\), the logarithm of the extra factor \(2^{M/p}\) is then at most \(32(\log2)d\). Absorbing it into the absolute exponential constant proves (31). ◻

Proof of Theorem 4 by positive cap domination. Put \(L=\log(1/\epsilon)\).

For the given sequence \(M(d)=o(d^2)\), use (31) in all sufficiently large dimensions. The stopping events are disjoint. Since \(k\ge d/32\), \(\alpha\ge d/3\), and \(\lceil t/k\rceil\le t/k+1\), summing over \(0\le t\le T\) yields \[ \mathbb P\{\text{success}\} \le(T+1)\exp(C_1d+C_2T-dL/3). \tag{32}\] Here \((\epsilon/2)^\alpha\le\exp(-dL/3)\), and \(C_1,C_2\) are absolute. If success is at least \(2/3\), taking logarithms gives \[\frac{dL}{3} \le C_1d+C_2T+\log(T+1)+\log(3/2) \le C_1d+(C_2+1)T+\log(3/2),\] since \(\log(T+1)\le T\) for every \(T\ge0\). Lemma 7 also gives \(T>d/8\), and therefore \(T\ge1\). Consequently \[dL\le3(8C_1+C_2+2)T.\] This proves the claimed bound with an absolute constant, uniformly over the full accuracy range. Only the dimension at which the memory factor is absorbed may depend on the sequence \(M(d)\). ◻

Proof. The ambient estimate (35) follows from Lemma 3, with \(2^{d-1}\) absorbed into \(C^d\). For dyadic outer radii \(r_m=\epsilon2^{-m}\), the shell \(r_m/2<\left\lVert s-z\right\rVert\le r_m\) contributes at most \((2/r_m)^\alpha C^d r_m^{d-1}\). The point \(s=z\) has zero \(\sigma\)-measure, and \(\sum_{m\ge0}2^{-m(d-1-\alpha)}\le2\). Summing proves (36). The same argument at radius \(1/10\), together with the kernel bound \(10^\alpha\) outside that ball, proves \(V(h)<\infty\) uniformly over \(0\le h\le1\). ◻

Proof. For every ambient center \(c\) and radius \(r>0\), definition (34) gives \[ \int_{B_r(c)}h\,d\sigma\le V(h)r^\alpha . \tag{38}\] Fix \(0<r\le\rho\). A maximal \(r\)-separated subset of \(F\cap B_\rho(z)\) has at most \((1+2\rho/r)^\ell \le(3\rho/r)^\ell\) points, by comparing disjoint radius-\(r/2\) balls in \(F\) with the radius-\((\rho+r/2)\) ball. It is an \(r\)-net. The orthogonal projection onto \(F\) of any point in \(B_\rho(z)\) lies in \(F\cap B_\rho(z)\), since \(z\in F\). Consequently the part of \(B_\rho(z)\) within distance \(r\) of \(F\) is covered by the corresponding ambient radius-\(2r\) balls. Equation (38) yields \[ \int_{B_\rho(z)\cap\{\operatorname{dist}(s,F)\le r\}} h(s)\,d\sigma(s) \le 3^\ell2^\alpha V(h)\rho^\ell r^{\alpha-\ell}. \tag{39}\] This includes \(\ell=0\), with a one-point net. Since \(\alpha-\ell>0\), letting \(r\) decrease to zero shows that \(F\cap B_\rho(z)\) has zero mass.

Every point of \(B_\rho(z)\) is within distance \(\rho\) of \(F\). Apply (39) on the shells with outer distance \(r_m=\rho2^{-m}\) and bound the inverse power there by \((2/r_m)^k\). Their sum is at most \[3^\ell2^{\alpha+k}V(h)\rho^{\alpha-k} \sum_{m\ge0}2^{-m(\alpha-\ell-k)}.\] Here \(\alpha-\ell-k\ge\alpha-(q-1)-k\ge2\), so the series is at most \(2\). Since \(\ell\le d/8\), \(\alpha=d/2\), and \(k\le d/8\), the remaining constant is at most \(C^d\). This proves (37). ◻

Proof. Let \(\mu\) be the finite Borel measure given by \(\mu(E)=\int_E h\mathbf1_H\,d\sigma\) on Borel subsets of the sphere. For \(\eta>0\), let \(B_\eta^k=\{u\in\mathbb R^k:\left\lVert u\right\rVert\le\eta\}\) and let \(\operatorname{vol}_k\) denote \(k\)-dimensional Lebesgue measure. Define \[ R_\eta(X,y)= \frac{1}{\operatorname{vol}_k(B_\eta^k)} \int \mathbf1_{\{\left\lVert Xt-y\right\rVert\le\eta\}}\,d\mu(t). \tag{42}\] The integrand is Borel in \((X,y,t)\), so the parameter integral is Borel in \((X,y)\). We first prove (40) with \(R_\eta\) in place of \(R\), uniformly in \(\eta\).

Expand its \(q\)th moment at \(Xz+b\) by Tonelli’s theorem, using \(t_1,\ldots,t_q\) from the \(q\) copies of \(\mu\). For a fixed tuple, the columns \(X(t_j-z)\) form an array whose \(k\) rows are independent centered Gaussian vectors with covariance \[G=\bigl(\langle t_i-z,t_j-z\rangle\bigr)_{1\le i,j\le q}.\] If \(G\) is nonsingular, their joint density is bounded everywhere by \((2\pi)^{-kq/2}(\det G)^{-k/2}\). Therefore the probability that all columns belong to the radius-\(\eta\) ball about \(b\) is at most this bound times \(\operatorname{vol}_k(B_\eta^k)^q\).

The singular tuples have zero \(\mu^q\) mass. Indeed, at the first linearly dependent vector \(t_j-z\), the point \(t_j\) lies in \(z+\operatorname{span}(t_1-z,\ldots,t_{j-1}-z)\), an affine space through \(z\) of dimension at most \(q-1\). Lemma 21 assigns zero \(\mu\) mass to it. The degeneracy set is measurable, and Fubini’s theorem applied at each \(j\) proves the claim. For a nonsingular tuple, Gram–Schmidt triangularizes the matrix with columns \(t_j-z\) with diagonal entries equal to the successive orthogonal distances. Taking the determinant of its Gram matrix gives \[ (\det G)^{-k/2} =\prod_{j=1}^q \operatorname{dist}\!\left( t_j,z+\operatorname{span}(t_1-z,\ldots,t_{j-1}-z) \right)^{-k}. \tag{43}\] Integrate this product first in \(t_q\), then in \(t_{q-1}\), and so on. For every nonsingular prefix, Lemma 21 bounds the next integral by \(C^dV(h)\rho^{\alpha-k}\). The exceptional prefixes have zero product measure by the same degeneracy argument. It follows that the integral of (43) is at most \((C^dV(h)\rho^{\alpha-k})^q\). The ball volumes cancel in the moment expansion, and the Gaussian prefactor is at most one. Thus \[\mathbb E_X R_\eta(X,Xz+b)^q \le \bigl(C^dV(h)\rho^{\alpha-k}\bigr)^q\] for every \(\eta>0\) and every fixed \(b\).

Now choose the function once and for all: \[ R(X,y)=\liminf_{m\to\infty}R_{1/m}(X,y). \tag{44}\] It is jointly Borel. To see that it is a density, fix a full-row-rank \(X\). Set \(D=(XX^{\mathsf T})^{1/2}\) and \(P=D^{-1}X\), so \(D\) is invertible, \(P\) has orthonormal rows, and \(X=DP\). Lemma 1 makes \(P_\#\sigma\) absolutely continuous, and the invertible map \(D\) preserves absolute continuity. Since \(\mu\le\sigma\), the pushforward \(X_\#\mu\) is also absolutely continuous. The Lebesgue differentiation theorem (Tao 2011, Theorem 1.6.19), applied to its \(L^1\) density, shows that (44) equals that density almost everywhere in \(y\). A Gaussian \(X\) has full row rank almost surely, since each successive Gaussian row avoids the span of the preceding rows.

For each fixed \(b\), the identity \(R(X,Xz+b)=\liminf_m R_{1/m}(X,Xz+b)\) holds by the definition of the single function \(R\). Fatou’s lemma (Tao 2011, Corollary 1.4.47) over \(X\) now gives (40). These are separate moment statements for each deterministic \(b\); no simultaneous almost-sure bound in \(X\) over all offsets is asserted. Finally, if \(\left\lVert y-Xz\right\rVert>\left\lVert X\right\rVert_{\mathrm{op}}\rho\), then every \(Xt\) with \(t\in H\) is at distance at least \(\left\lVert y-Xz\right\rVert-\left\lVert X\right\rVert_{\mathrm{op}}\rho>0\) from \(y\). The averages in (42) are eventually zero, proving (41). ◻

Proof. Lemma 3 gives \(\int h\,d\sigma\le\epsilon^{d-1}\), also for a randomized output law. For any ambient center \(z\), use \(h\le1\) and (36) inside \(B_\epsilon(z)\). Outside that ball, bound the kernel by \(\epsilon^{-\alpha}\) and use the total mass bound. The sum is at most \(C^d\epsilon^{d-1-\alpha}\) uniformly in \(z\), proving (47). ◻

Proof. For each successor \(w\), use the particular density \(R_w(X,y)\) of Lemma 22 for the measure \(h_i(w,\cdot)\mathbf1_{H_\rho(z)}\,d\sigma\). Tonelli’s theorem, (46), and pushforward integration give \[ \begin{split} \int_{H_\rho(z)} \frac{h_{i-1}(v,s)}{\left\lVert s-z\right\rVert^{\alpha}}\,d\sigma(s) &\le (2/\rho)^\alpha \mathbb E_X\int_{\mathbb R^k} \sum_wK^{(i)}_{v,w}(X,y)R_w(X,y)\,dy\\ &\le (2/\rho)^\alpha \mathbb E_X\int_{\left\lVert y-Xz\right\rVert\le\left\lVert X\right\rVert_{\mathrm{op}}\rho} \max_wR_w(X,y)\,dy . \end{split} \tag{49}\] The pushforward identity used in the first inequality holds for every full-row-rank \(X\), hence almost surely. The second inequality uses the probability-vector property of \(K^{(i)}\) and (41).

We need a deterministic integration region after averaging over \(X\). Choose a sufficiently large absolute \(D_0\) and partition the matrices into \[E_1=\{\left\lVert X\right\rVert_{\mathrm{op}}\le D_0\sqrt d\},\qquad E_j=\{D_0(j-1)\sqrt d<\left\lVert X\right\rVert_{\mathrm{op}}\le D_0j\sqrt d\} \quad(j\ge2).\] These bins obey \[ \mathbb P(E_j)\le \exp\bigl(-4(j-1)^2d\bigr)\qquad(j\ge2). \tag{50}\] For completeness, take \(1/4\)-nets on the unit spheres of \(\mathbb R^d\) and \(\mathbb R^k\). A maximal separated set has at most \(9^d\) and \(9^k\) points, respectively, by the disjoint-ball volume argument. Approximating each unit vector by its net point incurs an error at most \(\left\lVert X\right\rVert_{\mathrm{op}}/2\) in a bilinear form. Hence \(\left\lVert X\right\rVert_{\mathrm{op}}\) is at most twice the largest absolute bilinear form on the two nets. Each such form is standard Gaussian, so its elementary tail bound and a union bound give \[ \mathbb P\{\left\lVert X\right\rVert_{\mathrm{op}}>t\} \le 2\cdot9^{d+k}\exp(-t^2/8). \tag{51}\] Putting \(t=D_0(j-1)\sqrt d\) proves (50) after increasing \(D_0\), since \(k\le d/8\).

For every deterministic \(b\in\mathbb R^k\), Hölder’s inequality and (40) give \[ \begin{split} \mathbb E_X\!\left[\mathbf1_{E_j}\max_wR_w(X,Xz+b)\right] &\le \mathbb P(E_j)^{1-1/q} \left(\sum_w\mathbb E_X R_w(X,Xz+b)^q\right)^{1/q}\\ &\le \mathbb P(E_j)^{1-1/q}W^{1/q} C^dV_i\rho^{\alpha-k}. \end{split} \tag{52}\] No conditional version of the density lemma is being used: Hölder’s inequality pays for the bin event. For a fixed matrix in \(E_j\), translate \(y=Xz+b\) in (49); the remaining region is \(\left\lVert b\right\rVert\le D_0j\sqrt d\,\rho\). Joint measurability permits Tonelli’s theorem to integrate (52) over this deterministic ball.

The volume of that ball is at most \(C^d j^k\rho^k\). Indeed, the unit-ball bound (2) gives \(v_k\le(2\pi e/k)^{k/2}\). Since \(d/k\le16\), \(v_k(D_0j\sqrt d\,\rho)^k\le C^d j^k\rho^k\). Also, by \(q\ge2\) and (50), \[\sum_{j\ge1}j^k\mathbb P(E_j)^{1-1/q} \le 1+\sum_{j\ge2} \exp\bigl(k\log j-2(j-1)^2d\bigr) \le 2 .\] For the last bound use \(k\log j\le(d/8)(j-1)^2\) for \(j\ge2\) and sum the resulting geometric upper bound. Combining the volume and bin estimates with (49) proves (48). The powers of the shell radius cancel exactly: \[\rho^{-\alpha}\rho^{\alpha-k}\rho^k=1.\] ◻

Proof of Proposition 23. Outside \(B_\epsilon(z)\) use the shells \[2^m\epsilon<\left\lVert s-z\right\rVert\le2^{m+1}\epsilon, \qquad m=0,1,\ldots .\] For every ambient \(z\), at most \(C(1+L)\) of these meet the sphere. If \(\left\lVert z\right\rVert\le3\), all distances are at most \(4\), giving at most \(\lceil\log_2(4/\epsilon)\rceil\) nonempty shells. If \(\left\lVert z\right\rVert>3\), the distances lie between \(\left\lVert z\right\rVert-1\) and \(\left\lVert z\right\rVert+1\), whose ratio is less than \(2\); only a bounded number of dyadic shells can then meet that interval.

Inside \(B_\epsilon(z)\) use \(h_{i-1}\le1\) and (36). On each remaining shell use Lemma 25. Taking the supremum over \(z\) and the maximum over \(v\) gives \[ V_{i-1}\le C^d\epsilon^{d-1-\alpha} +C^d(1+L)W^{1/q}V_i . \tag{53}\] Choose \(C_0\) large enough that the first term here and the terminal value \(V_N\) are at most \(B\) in (45), and that the second coefficient is at most \(J-1\). With \(U_i=\max\{V_i,B\}\), equation (53) gives \(U_{i-1}\le J U_i\), while \(U_N=B\). Hence \(V_0\le BJ^N\), also when \(N=0\).

At \(z=0\) the kernel in (34) equals one on the unit sphere, so \(\int h_0(v,s)\,d\sigma(s)\le V_0\) for each initial state. For almost every fixed shared seed, averaging over its conditional initial-state law preserves the bound, because that law is independent of the signal and rows. Averaging the original conditional success probabilities over the seed then preserves it again. This proves (45). ◻

Proof of Theorem 4 by the Riesz method. There is a useful bound that counts possible terminal tags. For fixed rules as above, write \(p_{\mathrm{succ},\mathrm{rule}}\) for the conditional success probability. For a tag \(a\), let \(f_a(s)\) be the probability of reaching it given \(s\), and let \(g_a(s)\) be its output law’s success probability. This output law depends only on the tag, and \(0\le f_a\le1\). Lemma 3 gives \(\int g_a\,d\sigma\le C^d\epsilon^{d-1}\), including a randomized output law. Sum over at most \(W\) tags to obtain \[ p_{\mathrm{succ},\mathrm{rule}}=\sum_a\int f_a(s)g_a(s)\,d\sigma(s) \le W C^d\epsilon^{d-1}. \tag{54}\] The right side is independent of the chosen rules, so averaging also gives \(p_{\mathrm{succ}}\le W C^d\epsilon^{d-1}\).

Write \(L=\log(1/\epsilon)\). If \(T\ge dL\), the conclusion already holds. In the remaining case \(T<dL\), assume \(p_{\mathrm{succ}}\ge2/3\). Taking logarithms in the averaged form of (54) gives \[(d-1)L \le M\log2+\log(T+2)+d\log C+\log(3/2).\] For the given memory sequence, eventually \(M\le d^2\). Since \(L\ge\log10\) and \(T<dL\), we also have \[\log(T+2)\le\log(2d)+\log L\le\log(2d)+L\] for large \(d\). It follows that \((d-2)L\le d^2\log2+d\log C+\log(2d)+\log(3/2)\). Consequently, only in this remaining case, \[ L\le Cd,\qquad \log W=M\log2+\log(T+2)\le Cd^2 . \tag{55}\] Thus the multiplier from Proposition 23 obeys \[\log J \le \log2+d\log C_0+\log(1+L)+\frac{\log W}{q} \le Cd ,\] using \(q\ge d/16\). In particular the shell-count term has been bounded rather than removed.

Now (45) and \(p_{\mathrm{succ}}\ge2/3\) imply \[ (d/2-1)L \le d\log C_0+N\log J+\log(3/2) \le Cd(1+N)+\log(3/2) \le C'(d+T), \tag{56}\] because \(N=\lceil T/k\rceil\le16T/d+1\). The common full-data bound, Lemma 7, gives \(T>d/8\); hence the additive \(d\) on the right of (56) is at most \(8T\). For \(d\ge4\) the left coefficient is at least \(d/4\), so \(T\ge c\,dL\) for an absolute \(c>0\). This combines with the case \(T\ge dL\) already separated. ◻