Proof. The local growth hypothesis is of Frostman type, and inverse-distance averaging is a classical projection method; compare (Mattila 1975, Lemmas 3.5 and 5.1, pp. 230–231 and 236). Here we retain the coefficient and radius throughout the calculation.

The orthogonal projection of \(B(z,R)\) onto \(L\) lies in a \(j\)-dimensional ball of radius \(R\). A maximal \(t\)-separated set in that ball is a \(t\)-net and has at most \((1+2R/t)^j\le(3R/t)^j\) points, by comparing disjoint balls of radius \(t/2\) with the ball of radius \(R+t/2\). When \(j=0\), use its single point. Every point of \(B(z,R)\) at distance at most \(t\) from \(L\) is within \(2t\) of a net point. Applying (9) to these ambient balls proves (12). Since \(\beta-j>0\), letting \(t\downarrow0\) also gives \(\mu(L)=0\).

The total mass is at most \(HR^\beta\). Integrating the elementary identity for an inverse power up to radius \(R\), and using Tonelli’s theorem, gives \[\begin{align*} \int\operatorname{dist}(s,L)^{-m}\,d\mu(s) &\le R^{-m}\mu(\mathbb R^d) +m\int_0^R t^{-m-1} \mu\{s:\operatorname{dist}(s,L)\le t\}\,dt\\ &\le \left(1+3^j2^\beta\frac{m}{\beta-j-m}\right) HR^{\beta-m}. \end{align*}\] The denominator is positive by the stated hypothesis on \(\beta\). This proves (13).

If \(p-1>d\), then \(d\le p-2\); applying the tube estimate to \(L=\mathbb R^d\) and letting \(t\downarrow0\) shows that \(\mu=0\). The Gram conclusion is then immediate. Otherwise, the nullity of affine planes of dimensions at most \(p-2\) shows by successive integration that \(s_i\) lies outside \(\operatorname{aff}(s_1,\ldots,s_{i-1})\) for almost every tuple and every \(2\le i\le p\). Hence \(V\) has full column rank almost everywhere. Gram–Schmidt orthogonalization gives, on this set, \[\det(V^{\mathsf T}V)^{-m/2} = \prod_{i=2}^p \operatorname{dist}\bigl(s_i, \operatorname{aff}(s_1,\ldots,s_{i-1})\bigr)^{-m}.\] The product of the corresponding positive heights is \((p-1)!\) times the \((p-1)\)-simplex volume. Related simplex-volume factors occur in Drury’s affine-plane Jacobian (Drury 1984, Lemma 1, pp. 497–498); its normalization and exponent differ from this Gaussian calculation.

Integrate first in \(s_p\), then in \(s_{p-1}\), and continue down to \(s_2\). At the \(s_i\) step the preceding affine span has dimension \(i-2\) almost everywhere, so (13) contributes \(J_{i-2}HR^{\beta-m}\). The final \(s_1\) integral contributes at most \(HR^\beta\). All integrands are nonnegative, and Tonelli’s theorem therefore justifies this order and proves (14). ◻

Proof. Let \(\eta_1,\ldots,\eta_k\) be independent \(N(0,\delta^2I_m)\) vectors. For fixed \(A\), integrating the product over the common location \(y\) gives the density at zero of the \(k-1\) differences \[(At_i+\eta_i)-(At_1+\eta_1),\qquad 2\le i\le k.\] Indeed, the linear change from \(k\) vectors to the first vector and these differences has determinant one. After averaging over \(A\), each of the \(m\) rows is a centered Gaussian difference vector with covariance \[D^{\mathsf T}D+\delta^2(I_{k-1}+\mathbf1\mathbf1^{\mathsf T}).\] The \(m\) row vectors are independent. Evaluating their joint density at zero gives (15). For fixed \(\delta>0\), the conditional difference densities are continuous and bounded uniformly in \(A\), so their averaged value at zero equals the value of the averaged density. The covariance is positive definite even when \(D\) is rank deficient.

If \(G=D^{\mathsf T}D\) is positive definite and \(B\) is positive semidefinite, then \(\det(G+B)=\det G\,\det(I+G^{-1/2}BG^{-1/2})\ge\det G\). Apply this with \(B=\delta^2(I+\mathbf1\mathbf1^{\mathsf T})\). ◻

Proof. The defining integrand is nonnegative and Borel, so its parameter integral is Borel. Expand the \(p\)th power and use Tonelli’s theorem. The general Gaussian difference identity (15), with \(k=p\), \(m\) rows, and the tuple \(s_1,\ldots,s_p\), gives the displayed equality. In particular the common first noise contributes \(\delta^2\mathbf1\mathbf1^{\mathsf T}\), and the prefactor is \((2\pi)^{-m(p-1)/2}\).

On the full-rank tuples of Proposition 7, adding the positive definite noise covariance can only increase the determinant. Indeed, for positive definite \(G\) and positive semidefinite \(Q\), \(\det(G+Q)=\det(G)\det(I+G^{-1/2}QG^{-1/2})\ge\det(G)\). The rank-deficient tuples have product measure zero. The bound now follows from (14) and the definition of \(\mathcal B\). ◻

Proof. The locally finite Borel measures here have Radon extensions (Stanford Mathematics Department, n.d., Corollary 2.11); on Euclidean space these are the completions of the Borel measures. On the completion of \(\lambda\), the space \(C_c(E)\) is dense in \(L^{p/(p-1)}(\lambda)\) (Fremlin, n.d.-b, Proposition 416I). The assumed functional extends by continuity to that space. Real \(L^p\) duality (Fremlin, n.d.-a, Theorem 244K) gives a representing \(f\in L^p(\lambda)\) of norm at most \(U\).

Choose a Borel representative of \(f\) (Fremlin, n.d.-a, sec. 241B(k)). Hölder makes \(f^+\lambda\) and \(f^-\lambda\) finite on compact sets. Their Radon extensions obey \[\int\psi\,d(f^+\lambda) =\int\psi\,d(\eta+f^-\lambda) \qquad(\psi\in C_c(E)).\] Radon measures are determined by these tests (Fremlin, n.d.-b, Proposition 416E(b)). The two measures therefore agree. Evaluating on the Borel set where \(f<0\) gives \(f^-\lambda=0\), and then \(\eta=f\lambda\). ◻

Proof of Theorem 6. For a real \(\psi\in C_c(\mathbb R^{md}\times\mathbb R^m)\), let \(Z\sim N(0,I_m)\) be independent. Then \[\int\psi F_\delta\,d\lambda_m =\int\mathbb E_Z\psi(A,As+\delta Z)\, d\gamma_m(A)d\mu(s) \longrightarrow\int\psi\,d\eta_\mu\] by bounded convergence, since \(\mu\) is finite. Hölder’s inequality and Lemma 9 bound the limiting functional by \(\mathcal B\|\psi\|_{L^{p/(p-1)}(\lambda_m)}\). The measure \(\lambda_m\) is locally finite and \(\sigma\)-finite Borel, and \(\eta_\mu\) is finite nonnegative Borel. Applying Lemma 10 with \(U=\mathcal B\) gives (11). Choose a Borel representative and multiply it by the indicator of \(\mathcal E_{z,R}\). The image measure is supported on the Borel set \(\mathcal E_{z,R}\), so its nonnegative density vanishes almost everywhere outside that set. ◻

Proof. The zero measure is immediate. Any ambient ball of radius \(\rho\) with positive mass contains a support point, and is contained in the ball of radius \(2\rho\) about that point. Hence its mass is at most \((2\rho)^a\). Apply Theorem 6 with \(\beta=a\), \(p=q\), \(H=2^a\), and support radius \(R=1\). For \(0\le j\le q-2\), the parameters in (4) give \[ a-j-m\ge n/2-2q+2\ge n/4+2, \qquad \frac{m}{a-j-m}\le\frac12. \tag{19}\] Thus \(J_j\le\exp(Cd)\), and the stated norm bound follows. ◻

Proof. The image measure is carried by \(\mathcal E_{z,R}\), which proves the support assertion.

Almost surely \(A\) has full row rank. In singular-value coordinates, \(A B(0,R)\) is an ellipsoid whose semiaxes are \(R\) times the \(m\) singular values of \(A\). Its volume is therefore exactly \(v_mR^m\sqrt{\det(AA^{\mathsf T})}\). Hadamard’s inequality bounds the square root by the product of the row norms: Gram–Schmidt replaces each row norm by the length of its component perpendicular to the preceding rows, which can only decrease it. Those rows are independent and each has expected norm at most \(\sqrt{\mathbb E\|a_i\|^2}=\sqrt d\), giving the first inequality. Also \[(2\pi)^{m/2} =\int_{\mathbb R^m}e^{-\|y\|^2/2}\,dy \ge e^{-m/2}v_m m^{m/2},\] which proves \(v_m\le(2\pi e/m)^{m/2}\).

To see uniformity for short blocks, put \(t=m/d\in(0,1]\). Since \(t\log(1/t)\le1/e\), \[\frac1d\log\!\left((2\pi e d/m)^{m/2}\right) =\frac t2\log(2\pi e)+\frac t2\log(1/t) \le\frac12\log(2\pi e)+\frac1{2e}.\] This supplies an absolute \(C_{\mathrm E}\) in (20). For any full-block choice \(m=p\) with \(d/16\le p\le d\), one can instead use \(d/p\le16\) directly to obtain \[ \lambda_p(\mathcal E_{z,R}) \le \bigl(\sqrt{32\pi e}\,R\bigr)^p. \tag{21}\] ◻

Proof. The everywhere-defined kernels and the forced terminal action at \(T\) give a finite scored experiment from every specified state. Its score function is Borel in the signal. Indeed, the map \((s,x)\mapsto(x,\langle x,s\rangle)\) is continuous, and each path probability is a finite product of Borel coordinate probabilities. Summing over the finitely many paths and integrating against the fixed laws of future rows preserves Borel measurability. The same argument applied to \(\ell(s,v)\) and each fixed output law shows that \(h^{\mathrm{out}}_{k,w}\) is Borel. The integration fact follows first for indicators of rectangles and then for nonnegative Borel functions by the monotone class theorem and monotone convergence; see also the composition of kernels in (Gagné and Panangaden 2023, sec. 2.3).

Pre-generate all \(m\) rows of the block, including those after an early stop. At each \(k=t,\ldots,t+m-1\), perform the sample-free stopping check and, if still active, process the next pair through the transition to \(k+1\). A terminal tag from that transition stops at \(k+1\). An active exit from the final transition is passed to the continuation before the stopping check at \(t+m\), so that check is performed exactly once. If \(t+m=T\), the continuation performs the forced terminal action.

A terminal destination records its local stopping offset \(i\in\{0,\ldots,m\}\) and its terminal state in \(Q_{t+i}\). The offset \(i=0\) includes an immediate stop, and \(i=m\) can arise from the last transition. A transition tag and a sample-free stop at the same state and index have the same output law, so their outcomes can be merged. Continuing destinations form one additional copy of \(Q_{t+m}\), distinguished from the terminal destinations at that index. Consequently the number of destinations is at most \[\sum_{i=0}^m|Q_{t+i}|+|Q_{t+m}|\le(m+2)2^M.\] The block’s entrance index is fixed, so local offsets determine all absolute stopping indices; the count has no factor depending on \(T\).

For arbitrary data \((A,b)\), each destination probability \(g_j(A,b)\) is a finite sum over paths of products of Borel coordinate probabilities. It is therefore Borel. The probabilities are nonnegative and sum to one when all destinations are included. A path that stops early is simply independent of the unused rows. After a continuing destination is fixed, independent future rows and fresh choices give its prescribed continuation score. After a terminal destination is fixed, the prescribed output law gives its terminal score. Conditioning first on the block data and then on its destination proves (25). Because the kernels are defined everywhere, this equality holds for every signal and every starting state, rather than only at states reached by the original run. ◻

Proof. We first construct versions for a fixed set of rules. If \(f:\mathbb R^d\times\mathbb R\to[0,1]\) is measurable in the \(\lambda\)-completion, each dyadic superlevel set \(\{f\ge k2^{-n}\}\), \(1\le k\le2^n\), agrees with a Borel set outside a Borel \(\lambda\)-null set, by the description of completion in Tao (Tao 2011, Exercise 1.4.26). Replace these superlevel sets by their Borel representatives in \[f_n=2^{-n}\sum_{k=1}^{2^n}\mathbf 1_{\{f\ge k2^{-n}\}}.\] The resulting Borel functions have a Borel \(\limsup\) equal to \(f\) outside the union of the countably many null sets, since \(f_n\to f\). Thus each coordinate of each finite kernel has a Borel version. For one state and index, choose all of its coordinate versions simultaneously. The Borel set on which the resulting vector is not nonnegative with sum one is null; on this set replace the vector by a fixed point mass. The result is a Borel probability vector at every sample pair. There are finitely many coordinates, states and indices, so one Borel \(\lambda\)-null set \(Z\) contains every pair where any coordinate was changed. Sample-free decisions and terminal output laws require no such modification.

Pre-generate all \(T\) input rows, including rows after an early stop. Every pair \((X_t,\langle X_t,S\rangle)\) has the marginal law in (26), so \[\mathbb P\{(X_t,\langle X_t,S\rangle)\in Z\}=0.\] For a state \(u\) chosen from earlier observations, the event that the learner is in \(u\) before sample \(t\) and this pair lies in \(Z\) is a subset of the displayed null event. We do not need a density for a sample conditioned on a particular state. A finite union over \(t\) shows that no changed pair is visited almost surely. Couple the original and modified finite choices by the same uniform random numbers. Starting from the same initial state, induction makes their states and stopping decisions equal almost surely. At an equal terminal state and index the output laws are identical, so use their diagonal coupling. This proves the asserted joint-law equality. When \(T=0\) there is no sample pair to modify and the same conclusion is immediate.

It remains to check the spherical prior. Conditional on a nonzero \(X=x\), rotate coordinates so that \(x/\|x\|\) is the first coordinate vector. Write a uniform sphere point as \(G/\|G\|\) for a standard Gaussian vector \(G=(G_1,G_\perp)\). When \(d\ge2\), \(R=\|G_\perp\|>0\) almost surely and is independent of \(G_1\). For each fixed \(R>0\), the map \[g\longmapsto \frac{g}{\sqrt{g^2+R^2}}\] is a smooth strictly increasing bijection from \(\mathbb R\) to \((-1,1)\) with nonzero derivative. The image of the Gaussian law of \(G_1\) therefore has a Lebesgue density. Mixing over \(R\) and then multiplying by \(\|x\|\) shows that \(\langle x,S\rangle\) is absolutely continuous for every \(x\ne0\). The point \(x=0\) has \(\gamma_1\)-measure zero. Fubini’s theorem applied to the sections of a \(\lambda\)-null Borel set now proves (26). ◻

Proof. Use the angular score in Lemma 14. Fix a seed and a prior-preserving Borel replacement as in Section 5.2, with prior \(\sigma\). If \(T=0\), its output is a signal-independent mixture of terminal laws. Lemma 5 gives local mass at scale \(\epsilon\). The radius-two ball about a sphere point covers \(S^{d-1}\), so total success is at most \((2\epsilon)^a\), as required when \(\lceil T/q\rceil=0\). We may now suppose \(T\ge1\).

Increase the absolute threshold \(d_0\) so that \(q\ge2\), \(q\ge d/16\), and \(a\ge d/3\). Partition the \(T\) sample indices into \(B=\lceil T/q\rceil\) consecutive nonempty blocks, each of length at most \(q\). At the final boundary every continuation is a terminal output function and obeys (5) at scale \(\epsilon\). Suppose that at the end of one block, all continuing functions obey that bound at a common scale \(R\ge\epsilon\). Its terminal destinations also obey the bound at scale \(R\), by Lemma 5 and monotonicity in the scale.

For a block of length \(m\le q\), Lemma 14 places every preceding continuation in the form required by Lemma 13, with \(N\le(m+2)2^M\le(q+2)2^M\). That block lemma multiplies the scale by at most \[\exp(C_0d/a)N^{1/(aq)}\] for an absolute \(C_0\). Its logarithm is at most \[ \frac{C_0d}{a}+ \frac{M\log2+\log(q+2)}{aq} \le C\left(1+\frac{M}{d^2}\right)=:\Lambda, \tag{28}\] where \(d/a\le3\), \(1/(aq)\le48/d^2\), and \(\log(q+2)/(aq)\le48\log(d+2)/d^2\) allow an absolute \(C\). Backward induction gives (5) at scale \(R=\epsilon e^{\Lambda B}\) for every initial state. Averaging over the conditional initial-state law preserves this bound, because that law is independent of the signal and rows. Taking the radius-two ball gives total success at most \((2\epsilon e^{\Lambda B})^a\), and a probability is also at most one.

By the reduction in Section 5.2, this is a uniform bound on the original conditional success probabilities for almost every seed. Averaging them proves (27); no joint choice of the Borel replacements is used. ◻

Proof. An empty \(\mathcal B(z,r)\) gives the zero measure. Otherwise fix \(u_*\in\mathcal B(z,r)\), and let \[\mu=\iota_\#\bigl(\mathbf1_{\mathcal B(z,r)}f(u)\,du\bigr).\] For any \(x\in\mathbb R^d\) and \(t>0\), projection onto the first coordinates gives \[ \begin{split} \mu(B_d(x,t)) &\le\int_{\mathcal B(\sqrt n\,\operatorname{pr}x,t)}f(u)\,du\\ &\le Lt^\beta. \end{split} \tag{46}\] For \(u\in\mathcal B(z,r)\), the distance from \(u\) to \(u_*\) is at most \(2\sqrt n\,r\). Thus (38) puts \(\mu\) inside \(B_d(\iota(u_*),4r)\).

If \(L=0\), (40) applied to a ball containing \(Q\) gives \(f=0\) almost everywhere, and the zero density suffices. Suppose now that \(L>0\). Apply the general finite-measure result Theorem 6 with \[H=L,\qquad R=4r,\qquad m=k, \qquad \beta=3n/4,\qquad p=\lfloor n/4\rfloor.\] For its factors \(J_j\), the required margin and their uniform bounds are \[ \beta-j-k\ge\frac{3n}{4}-2p+2\ge\frac n4+2, \qquad J_j=1+3^j2^\beta\frac{k}{\beta-j-k} \le1+3^{n/4}2^{3n/4} \qquad(0\le j\le p-2). \tag{47}\] In particular \(\beta>k+p-2\). We use the general parameter range of that theorem, not the specialization to exponents near half the ambient dimension. Its exact norm bound is \[(2\pi)^{-k(p-1)/(2p)} L(4r)^{\beta-k(1-1/p)} \left(\prod_{j=0}^{p-2}J_j\right)^{1/p}.\] The first factor is at most one, each \(J_j\le C^n\), and \(0<\beta-k(1-1/p)\le\beta\). Absorbing \(4^{\beta-k(1-1/p)}\le4^\beta\) into \(C_2^n\) proves (43). This is the density of the exact joint measure (42); no density relative to spherical area is assumed.

The set \(\mathcal E_{u_*,r}\) is the exact projected image of the enclosing ball \(B_d(\iota(u_*),4r)\). Lemma 12 makes this set Borel and gives the asserted common support. The same lemma gives \[\lambda_k(\mathcal E_{u_*,r}) \le C_{\mathrm E}^d(4r)^k\le C_2^n r^k,\] after one universal increase of \(C_2\), since \(d\le2n+1\) and \(k\le n/4\). This calculation also covers the zero-density case. ◻

Proof. Fix \(z,r\). An empty \(\mathcal B(z,r)\) is immediate. Otherwise choose the same \(u_*\in\mathcal B(z,r)\) for all \(v\). The exact joint densities from Lemma 19 share its region \(\mathcal E_{u_*,r}\). Apply Lemma 18 with density norm at most \(C_2^nLr^{\beta-k(1-1/p)}\) and domain measure at most \(C_2^nr^k\). The image-measure identity and that lemma give \[ \int_{\mathcal B(z,r)}F(u)\,du \le N^{1/p}C_2^n(C_2^n)^{1-1/p}Lr^\beta \le C_3^nN^{1/p}Lr^\beta. \tag{48}\] The radius powers cancel, and the same \(C_3\) works for every \(1\le k\le p\). ◻

Proof. Use the seedwise convention just established, and first start from any prescribed initial state. For \(T>0\), partition the stream into \(m=\lceil T/p\rceil\) consecutive blocks, each of length at most \(p=k_0\). Lemma 14, with angular terminal score and signal \(\iota(u)\), represents the preceding success function by the exact block formula in Corollary 20. For a block of length \(k\), its Borel routes have at most \[ N\le(k+2)2^M \tag{51}\] destinations. The stopping offsets are local to this block, including an immediate stop; its continuing functions use fresh future samples. These are the same phase and terminal-state conventions as in that lemma.

For \(n\ge8\), \(p\ge n/8\), \(d\le2n+1\), and \(M\le d^2\), \[\frac{\log N}{p} \le\frac{d^2\log2+\log(p+2)}p\le C_4n\] with a universal \(C_4\). Choose a universal \(D\ge e\) so that \(D\ge C_0\) and \(C_3^nN^{1/p}\le D^n\). The terminal coefficient is \(C_0^n\epsilon^{n/4}\) by (41). Backward induction, applying the block bound and retaining the terminal estimate at earlier stops, gives coefficient \[L=D^{n(m+1)}\epsilon^{n/4}\] for every initial state. The ball \(\mathcal B(0,1)\) contains \(Q\), so this coefficient bounds total cube-average success. For \(T=0\), the terminal bound gives the same statement with \(m=0\). All constants are uniform over the seedwise Borel rules and prescribed states. The independent conditional initialization and the averaging of original conditional success probabilities from Section 5.2 therefore prove (49) for the original learner, including every short last block.

Suppose now only that the cube-average success is at least \(2/3\). Taking natural logarithms in (49) and using \(m\le T/k_0+1\) gives \[ \frac{T}{k_0} \ge\frac{\log(1/\epsilon)}{4\log D} -2-\frac{\log(3/2)}{n\log D}. \tag{52}\] If \(\log(1/\epsilon)\ge24\log D\), its right side is at least \(\log(1/\epsilon)/(8\log D)\). Since \(k_0\ge n/8\) and \(n\ge d/3\), this already gives \(T\ge d\log(1/\epsilon)/(192\log D)\) in that accuracy range.

For the all-accuracy conclusion (50), assume the stated every-signal guarantee. It gives the cube-average premise just used. It also gives uniform-sphere average success at least \(2/3\) for the same original learner. The reflection consequence (32) therefore forces \(T>d/4\). For \(\log(1/\epsilon)<24\log D\), this implies \[T>\frac d4>\frac{d\log(1/\epsilon)}{96\log D}.\] Combining the two ranges proves (50), for example with \(c=1/(192\log D)\), after increasing the universal dimension threshold as needed. The memory condition \(M\le d^2\) in particular holds eventually for every sequence \(M(d)=o(d^2)\). ◻

Proof. The cases \(L=0\) and an empty parameter ball are immediate as above. Apply Proposition 7 in parameter dimension \(n\) to \(\mathbf1_{\mathcal B(z,r)}f(u)\,du\), with \[H=Ln^{-\beta/2},\qquad R=\sqrt n\,r,\qquad m=k.\] The growth hypothesis follows because a parameter ball of radius \(a>0\) is \(\mathcal B(x,a/\sqrt n)\) after intersection with \(Q\). Its tube bound, evaluated at \(\sqrt n\,tr\), is \[3^j2^\beta (Ln^{-\beta/2})(\sqrt n\,r)^j (\sqrt n\,tr)^{\beta-j} =3^j2^\beta Lr^\beta t^{\beta-j}.\] Its inverse-distance bound is \(J_jLn^{-k/2}r^{\beta-k}\). Multiplication by \(n^{k/2}\) gives the normalization in (55). The bounds (47) absorb both constants into a universal \(C_1^n\). ◻

Proof. Let \(\rho_\delta=(v_m\delta^m)^{-1} \mathbf1_{B(0,\delta)}\) be the uniform probability density of the radius-\(\delta\) ball in \(\mathbb R^m\), and set \(U_\delta(A,y)=\int\rho_\delta(y-As)\,d\mu(s)\). After translating the common label variable by \(As_1\), the tuple kernel in its \(p\)th moment becomes \[K_\delta(v_2,\ldots,v_p) =\int_{\mathbb R^m}\rho_\delta(b) \prod_{i=2}^p\rho_\delta(b-v_i)\,db, \qquad v_i=A(s_i-s_1).\] It is nonnegative, and Tonelli’s theorem gives the exact normalization \[ \int_{\mathbb R^{m(p-1)}}K_\delta(v_2,\ldots,v_p) \,dv_2\cdots dv_p=1. \tag{61}\] In particular the kernel depends on \(A\) only through the differences; no independence of \(As_1\) from those differences is used.

For a full-rank \(V\), the rows of \(AV\) are independent centered Gaussian vectors with covariance \(V^{\mathsf T}V\). Their joint density has supremum \((2\pi)^{-m(p-1)/2}\det(V^{\mathsf T}V)^{-m/2}\). Multiplying this density by the unit-mass kernel (61) bounds the expected tuple kernel by that supremum. Expand \(\int U_\delta^p\,d\lambda_m\), discard only the product-null rank exceptions, and apply (14). This gives \[ \|U_\delta\|_{L^p(\lambda_m)}\le\mathcal B \qquad(\delta>0). \tag{62}\]

The measure \(\lambda_m\) is Borel and finite on compact sets in a Euclidean space. The Radon extension theorem (Stanford Mathematics Department, n.d., Corollary 2.11) applies and gives outer regularity on Borel sets. If \(O\) is open, then for each \((A,As)\in O\), all sufficiently small label perturbations remain in \(O\). Fatou’s lemma followed by Hölder’s inequality gives \[\eta_\mu(O) \le\liminf_{\delta\downarrow0}\int_O U_\delta\,d\lambda_m \le\mathcal B\,\lambda_m(O)^{1-1/p}.\] For a Borel \(E\) with finite \(\lambda_m(E)\), take open supersets whose \(\lambda_m\)-measures decrease to \(\lambda_m(E)\). The last inequality proves (59). Applied to null sets, it gives \(\eta_\mu\ll\lambda_m\). Extending \(\eta_\mu\) by zero on \(\lambda_m\)-null sets gives the asserted version on the \(\lambda_m\)-completion.

The measure \(\eta_\mu\) is supported on the Borel set \(\mathcal E_{z,R}\). If \(\int_{\mathcal E_{z,R}}\varphi\,d\lambda_m<\infty\), apply (59) to \(\{\varphi>t\}\cap\mathcal E_{z,R}\) for \(t>0\). Layer cake and concavity of \(x^{1-1/p}\) yield \[\begin{align*} \int\varphi\,d\eta_\mu &\le\mathcal B\int_0^1 \lambda_m(\{\varphi>t\}\cap\mathcal E_{z,R})^{1-1/p}\,dt\\ &\le\mathcal B \left(\int_0^1 \lambda_m(\{\varphi>t\}\cap\mathcal E_{z,R})\,dt\right)^{1-1/p}, \end{align*}\] which is (60). The case of an infinite right side is immediate. This proof supplies the measurable-test estimate directly; it does not infer a strong \(L^p\) bound from the set inequality alone. ◻

Proof. Rotate the row space of \(A\) to the first \(m\) coordinates. The restriction of \(A\) to that row space is an invertible map onto \(\mathbb R^m\), so it suffices to consider the orthogonal projection onto those coordinates. Write a uniform sphere point as \[\frac{(Z,W)}{\sqrt{\|Z\|^2+\|W\|^2}},\] where \(Z\) and \(W\) are independent standard Gaussian vectors in \(\mathbb R^m\) and \(\mathbb R^{d-m}\). Almost surely \(c=\|W\|>0\). Conditional on \(c\), the projection is the image of \(Z\) under \[z\longmapsto\frac{z}{\sqrt{\|z\|^2+c^2}}.\] This is a smooth diffeomorphism from \(\mathbb R^m\) onto the open unit ball; its inverse is \(u\mapsto cu/\sqrt{1-\|u\|^2}\). Thus the conditional projection law has a Lebesgue density, and integrating in \(c\) preserves absolute continuity. Applying the invertible row-space map proves the assertion for \(A_\#\sigma_d\). Absolute continuity of \(A_\#\mu\) follows from \(\mu\ll\sigma_d\). ◻

A second proof by hemisphere graphs. The two open hemispheres of \(S^{d-1}\) are the graphs \[x\longmapsto\bigl(x,\pm\sqrt{1-\|x\|^2}\bigr), \qquad \|x\|<1,\quad x\in\mathbb R^{d-1}.\] Their surface-area element is \((1-\|x\|^2)^{-1/2}dx\), and the omitted equator has surface measure zero. Projection of \(\sigma_d\) onto the first \(d-1\) coordinates therefore has a Lebesgue density. Integrating that density in the last \(d-1-m\) coordinates proves the same for projection onto the first \(m\) coordinates. Rotation, the invertible row-space map, and \(\mu\ll\sigma_d\) finish the argument as in the first proof. ◻

Proof. For a Borel set \(E\) in the matrix–label space, put \(E_A=\{y:(A,y)\in E\}\). If \(\lambda_m(E)=0\), Fubini’s theorem gives \(|E_A|=0\) for \(\gamma_m\)-almost every \(A\). Such a matrix has full row rank almost surely, and Lemma 24 therefore gives \((A_\#\mu)(E_A)=0\). A second application of Fubini shows that \(\eta_\mu(E)=0\). Thus the finite measure \(\eta_\mu\) is absolutely continuous with respect to the \(\sigma\)-finite measure \(\lambda_m\). The ordinary Radon–Nikodym theorem (Hunter 2011, Theorem 6.27), applied on the product Borel \(\sigma\)-algebra, gives a nonnegative jointly Borel density \(F\).

We verify that one common full-measure set of matrices has the asserted fiber property. Let \(\mathcal C\) be the countable \(\pi\)-system of half-open boxes with rational endpoints, the empty set, and \(\mathbb R^m\) itself. It generates the Borel sets of \(\mathbb R^m\). For \(C\in\mathcal C\) and every Borel matrix set \(D\), the density identity applied to \(D\times C\) gives \[\int_D(A_\#\mu)(C)\,d\gamma_m(A) = \int_D\int_C F(A,y)\,dy\,d\gamma_m(A).\] Both integrands are measurable functions of \(A\). Since this equality holds for every \(D\), they agree almost everywhere. Remove the union of these exceptional sets over the countable class \(\mathcal C\). For every remaining \(A\), the two finite measures agree on \(\mathcal C\), and hence on every Borel set by the uniqueness theorem for measures. This proves the fiber assertion.

When \(\mu\) is supported on \(B(z,R)\), its image is carried by the Borel set \(\mathcal E_{z,R}\). Multiplying \(F\) by the indicator of that set preserves the density identity. ◻

Proof. For almost every \(A\), the function \(F_A=F(A,\cdot)\) is a nonnegative \(L^1\) density of \(A_\#\mu\), of mass \(\mu(\mathbb R^d)\), and \(F_\delta(A,\cdot)=F_A*\phi_\delta\). Tao’s continuity theorem for translations in \(L^1(\mathbb R^m)\) (Tao 2011, Proposition 1.6.13) gives \[\|F_A*\phi_\delta-F_A\|_1 \le\int\phi_\delta(z)\, \|F_A(\,\cdot-z)-F_A\|_1\,dz \longrightarrow0.\] For completeness, fix a small translation radius on which the translation norm is small. The integral inside that radius is then small, and the remaining part is at most \(2\|F_A\|_1\) times the Gaussian mass outside that radius, which tends to zero. This proves the displayed limit.

The fiber difference norm is at most \(2\mu(\mathbb R^d)\). Because \(F\) and \(F_\delta\) are jointly measurable, these norms are measurable functions of \(A\). Dominated convergence in \(\gamma_m\) therefore proves the joint \(L^1\) limit. Choose a sequence \(\delta_i\downarrow0\) for which \(\sum_i\|F_{\delta_i}-F\|_{L^1(\lambda_m)}<\infty\). Tonelli’s theorem implies \(F_{\delta_i}\to F\) almost everywhere. Fatou’s lemma and (16) then give \(\int F^p\,d\lambda_m\le\mathcal B^p\). The density identity from Lemma 25 now applies to arbitrary bounded \(\lambda_m\)-completed-measurable functions of the exact matrix–label pair. ◻

Proof. The negative radial derivative of the Gaussian is \(-\frac{d}{dr}\phi_\delta(re_1) =(r/\delta^2)\phi_\delta(re_1)\). Hence \[\int_{\|y\|}^{\infty}\frac{w_\delta(r)}{v_mr^m}\,dr =\phi_\delta(y).\] This is precisely the claimed ball mixture. Integrating it in \(y\) and using Tonelli proves \(\int_0^\infty w_\delta(r)\,dr=1\). Also \(w_\delta(r)=\delta^{-1}w_1(r/\delta)\); its probability mass therefore concentrates at radius zero as \(\delta\downarrow0\).

Fix a full-row-rank \(A\). Lemma 24 gives a nonnegative \(L^1\) density \(f_A\) of \(A_\#\mu\). At a Lebesgue point \(y\) of \(f_A\), its ball averages \[a_r(y)=\frac{1}{v_mr^m}\int_{B(y,r)}f_A(x)\,dx\] tend to \(f_A(y)\) as \(r\downarrow0\), by the Lebesgue differentiation theorem (Tao 2011, Theorem 1.6.19). The mixture formula gives \[F_\delta(A,y) =(f_A*\phi_\delta)(y) =\int_0^\infty w_\delta(r)a_r(y)\,dr.\] Given an error tolerance, choose \(r_0>0\) such that \(a_r(y)\) is within that tolerance of \(f_A(y)\) for \(0<r<r_0\). For \(r\ge r_0\), the averages are bounded by \(\mu(\mathbb R^d)/(v_mr_0^m)\). The part of the mixture on \([r_0,\infty)\) thus tends to zero after subtracting \(f_A(y)\), while the part on \((0,r_0)\) has the chosen error bound. It follows that \(F_\delta(A,y)\to f_A(y)\) at every Lebesgue point.

Each \(F_{1/i}\) is jointly Borel. The set where its sequence has a finite limit is Borel, so (65) is jointly Borel as well. The preceding fixed-\(A\) argument shows that its fiber is a density for every full-row-rank \(A\), outside a null set of labels. Full row rank holds \(\gamma_m\)-almost surely, and Fubini therefore identifies \(F^\sharp\) with a joint density of \(\eta_\mu\). Finally \((F^\sharp)^p\le\liminf_i F_{1/i}^p\) everywhere by its definition. Fatou’s lemma and (16) prove (66). ◻

Proof. The restriction \(\mu\) is supported on \(B(z,R)\) and inherits the all-radius bound. Theorem 6, together with (68), gives its strong joint \(L^p\) density and (69). The fiber identification in Lemma 25 gives the asserted common almost-everywhere choice of projection densities. ◻

Proof. Choose \(1/4\)-nets of the unit spheres in \(\mathbb R^d\) and \(\mathbb R^m\) with at most \(9^d\) and \(9^m\) points. Approximating both arguments in the bilinear supremum loses at most \(\|A\|_{\mathrm{op}}/2\), so \[\|A\|_{\mathrm{op}}\le2\max_{u,v}|v^{\mathsf T}Au|\] over the net pairs. Each scalar is standard Gaussian. For such a scalar \(Z\), \(\mathbb E|Z|^m\le(C\sqrt m)^m\): use \(|z|^m e^{-z^2/4}\le(2m/e)^{m/2}\) and \(\mathbb Ee^{Z^2/4}=\sqrt2\). Bounding the maximum’s \(m\)-th power by the sum gives \[\mathbb E\|A\|_{\mathrm{op}}^m\le2^m9^{m+d}(C\sqrt m)^m.\] The unit \(m\)-ball volume \(v_m\) obeys \(v_m\le(2\pi e/m)^{m/2}\): integrate \(e^{-\|y\|^2/2}\) over the ball of radius \(\sqrt m\) and compare with its full Gaussian integral. Multiplication cancels \(m^{m/2}\), proving (74) uniformly even for a short block. ◻

Proof. Suppose first that \(0<r\le1/4\) and that \(B(z,r)\) meets the sphere. Choose a point \(a\) of the intersection and rotate it to a coordinate axis. Every other point of the intersection is within chordal distance \(2r\) of \(a\), lies in the corresponding open hemisphere, and projects into the radius-\(2r\) ball in \(\mathbb R^n\). On that projected ball the graph area element is at most \(2\), because \(2r\le1/2\). Thus the area of the patch is at most \(2v_n(2r)^n\), where \(v_n\) is the volume of the unit \(n\)-ball. The two hemisphere graphs together have area at least \(2v_n\). The resulting probability is at most \((2r)^n\), and hence at most \((4r)^n\). An empty intersection is harmless. For \(r>1/4\), the bound \(\sigma_d(B(z,r))\le1<(4r)^n\) proves (77).

For fixed \(u\), the successful part of \(B(z,r)\) is contained both in \(B(z,r)\) and in \(B(u,\epsilon)\). Apply (77) to each ball, take the smaller bound, and integrate in \(\kappa\). Finally \(\min\{r^n,\epsilon^n\}\le\epsilon^{n-\beta}r^\beta\), by considering \(r\le\epsilon\) and \(r\ge\epsilon\) separately. ◻

Proof. In spherical polar coordinates, the area element at polar angle \(t\) is \(\sin^{d-2}t\,dt\) times the area element on \(S^{d-2}\). Dividing the cap area by the total area therefore shows that a cap of angular radius \(0\le\theta\le\pi\) has mass \[\frac{\int_0^\theta\sin^{d-2}t\,dt} {\int_0^\pi\sin^{d-2}t\,dt}.\] The numerator is at most \(\theta^n/n\), since \(\sin t\le t\). Restricting the denominator to two different intervals gives \[\begin{align*} \int_0^\pi\sin^{d-2}t\,dt &\ge \frac\pi3\left(\frac{\sqrt3}{2}\right)^{d-2} &&\text{from }[\pi/3,2\pi/3], \\ \int_0^\pi\sin^{d-2}t\,dt &\ge \frac{2\pi}{3}\,2^{-(d-2)} &&\text{from }[\pi/6,5\pi/6]. \tag{80}\end{align*}\] Either estimate gives an upper bound \(C^d\theta^n\) for the cap.

If \(B(z,R)\) meets the sphere, choose \(s_0\) in the intersection. Every other point in it has chordal distance at most \(2R\) from \(s_0\). The angle between two unit vectors is at most \(\pi/2\) times their chordal distance. Thus their angle is at most \(\pi R\) when \(R\le1\); for \(R\le1/4\) the bound \(2\arcsin R\le4R\) is also available. The cap estimate and the trivial mass bound one for \(R\ge1\) give the asserted ambient-ball bound after enlarging \(C_0\).

For a fixed unit output, angular error at most \(\epsilon\) implies chordal error at most \(\epsilon\), because \(2\sin(\theta/2)\le\theta\). The global success mass is therefore at most \(C_0^d\epsilon^n\), while its mass in \(B(z,R)\) is at most the ambient-ball bound \(C_0^dR^n\). Averaging these bounds over the output law proves the minimum in (79). If \(R\le\epsilon\), then \(R^n\le\epsilon^{n-\beta}R^\beta\); if \(R\ge\epsilon\), then \(\epsilon^n\le\epsilon^{n-\beta}R^\beta\). ◻

Proof. For the fixed ball \(B(z,R)\), take \(\mu_w=\mathbf1_{B(z,R)}h_w\sigma\) in Lemma 29. Its exact density \(F_w\) is supported on the common domain \(\mathcal E_{z,R}\) of Lemma 12. The image identity gives \[\int_{B(z,R)}h\,d\sigma =\int_{\mathcal E_{z,R}}\sum_w g_w(A,y)F_w(A,y) \,d\lambda_m(A,y).\] The density condition of Lemma 18 applies on this domain with its norm parameter equal to \[\mathcal U=C_{\mathrm D}^{d(1-1/p)} H R^{\beta-m(1-1/p)}.\] Its conclusion and Lemma 12 give \[\begin{align*} \int_{B(z,R)}h\,d\sigma &\le N^{1/p}\mathcal U \lambda_m(\mathcal E_{z,R})^{1-1/p}\\ &\le N^{1/p}C_{\mathrm D}^{d(1-1/p)} H R^{\beta-m(1-1/p)}(C_{\mathrm E}^dR^m)^{1-1/p}\\ &\le C_{\mathrm{step}}^dN^{1/p}H R^\beta. \end{align*}\] The maximum-density proof of the same estimate observes pointwise that \(\sum_wg_wF_w\le\max_wF_w\) and \((\max_wF_w)^p\le\sum_wF_w^p\), then applies Hölder on \(\mathcal E_{z,R}\). It gives \(\lambda_m(\mathcal E_{z,R})^{1-1/p} (\sum_w\int F_w^p\,d\lambda_m)^{1/p}\), bounded by the same expression. The radius exponents are \(m(1-1/p)+\beta-m(1-1/p)=\beta\). The densities in this calculation represent exact observations, so the measurable routing functions are evaluated at the exact labels. ◻

Proof. Use the seedwise conditional experiment and Borel replacement from Section 5.2. Conditional on almost every shared seed, the initial state remains independent of the signal and rows. Lemma 14 supplies, from every specified boundary state, including an unreachable one, Borel routes to fresh continuations. In a block of \(m\) rows their number is at most \((m+2)2^M\): continuing states and terminal states tagged with one of the \(m+1\) local stopping indices. The lemma applies to either Borel terminal score.

The terminal bound (78) starts the all-radius coefficient at \(H_0=4^n\epsilon^{n-\beta}\). With \(N=(p+2)2^M\), Proposition 33 gives one recurrence for all actual block lengths \(1\le m\le p\): \[ H_j=H_0\bigl(C_{\mathrm{step}}^dN^{1/p}\bigr)^j. \tag{85}\] Each multiplier is at least one, so terminal options, whose coefficient is \(H_0\), satisfy every later bound. The ball \(B(0,1)\) contains the whole sphere; hence the initial coefficient bounds total success. Average first over the independent conditional initialization and then over the original seed experiment. As in Section 5.2, this averages original conditional probabilities and requires no jointly measurable choice of the seedwise replacements. The trivial probability bound gives the minimum with one. For \(T=0\) this is the terminal estimate. Starting instead from (79) proves the polar version.

One may instead pad the last block of actual length \(m<p\) with independent Gaussian rows and extend each route by ignoring them. Its matrix–label marginal on the first \(m\) rows is unchanged. Thus full padded blocks give exactly the same estimate and count. ◻

Proof. In Proposition 34, set \(\beta=n/2\) and use \(4^n\le4^d\) for the first formula. For the second, set \(\beta=d/2\), use the polar terminal coefficient, and enlarge the category bound to \(N=(2p+4)2^M\). The same recurrence then reads \[ H_j=C_0^d\epsilon^{d/2-1} \bigl(C_{\mathrm{step}}^dN^{1/p}\bigr)^j. \tag{88}\] The final ball \(B(0,1)\) gives the second formula. Angular success implies chordal success. ◻