Proof. The first \(\ell\) coordinates of a uniform spherical point have density \[\frac{\Gamma(d/2)} {\pi^{\ell/2}\Gamma((d-\ell)/2)} (1-\left\lVert y\right\rVert^2)^{(d-\ell-2)/2} \mathbf 1_{\{\left\lVert y\right\rVert<1\}}.\] To see the normalization, write the point as a standard Gaussian vector divided by its length. Its projected squared length has the \(\operatorname{Beta}(\ell/2,(d-\ell)/2)\) law and its projected direction is uniform. Polar coordinates give the displayed density. An orthogonal change of coordinates followed by the invertible map \((gg^{\mathsf T})^{1/2}\) gives the density for \(g_\#\sigma\), with Jacobian \(\det(gg^{\mathsf T})^{-1/2}\). Absolute continuity gives a density for \(g_\#\rho\). Each cube average is Borel in \((g,y)\) by integration of a Borel indicator. Lebesgue differentiation shows that (3) is a density version for each full-rank \(g\); the specified limit is jointly Borel.

We first verify logarithmic integrability from this explicit spherical density. Under the product law \(\gamma_\ell\otimes\sigma\), the logarithm of the residual squared radius is integrable by the beta law. Gram–Schmidt expresses \(\det(GG^{\mathsf T})\) as a product of chi-square variables with positive degrees of freedom, whose logarithms have finite absolute means. Hence \(\log p_\sigma(G,GS)\) is integrable. Domination by \(H\) preserves this integrability under \(\gamma_\ell\otimes\nu\). For every full-rank \(g\), data processing gives \[D(g_\#\nu\Vert g_\#\sigma)\le D(\nu\Vert\sigma)\le\log H.\] The negative logarithmic part of any probability density ratio \(a/b\), integrated under \(a\), is at most \(1/e\), because \(t\log^-(t)\le1/e\). Its positive part is therefore finite when the relative entropy is finite. Apply this to \(p_\nu/p_\sigma\) and add the integrable baseline logarithm.

Here is a direct proof that retains the first density moment in (4). For distinct \(u,s\), the \(\ell\) coordinates of \(G(u-s)\) are independent centered normals with variance \(\left\lVert u-s\right\rVert^2\). Their joint density is at most \((2\pi)^{-\ell/2}\left\lVert u-s\right\rVert^{-\ell}\). The cube volume is \((2\delta)^\ell\). Multiplying these quantities and applying Tonelli proves the first inequality in (4); the diagonal is null since \(\nu\le H\sigma\) is nonatomic. For each \(s\in S^{d-1}\), Lemma 3 and dyadic shells give \[\int\left\lVert u-s\right\rVert^{-\ell}\,d\nu(u) \le 1+H2^\ell\sum_{j\ge0}2^{-j(n-\ell)}<\infty.\] The term \(1\) covers distances greater than one, and \(n-\ell>0\) makes the series converge. This is uniform in \(s\).

For each full-rank \(G\), Lebesgue differentiation holds at \(GS\) for \(\nu\)-almost every \(S\), since \(G_\#\nu\) has a density. Fubini and Fatou pass the first-moment bound to \(p_\nu(G,GS)\). It follows that \(\mathbb E\log^+p_\nu(G,GS)<\infty\). To control the other part, let \(\phi_\ell\) be the standard Gaussian density on \(\mathbb R^\ell\). For each \(G\), \[\int p_\nu(G,y) \left(\log\frac{p_\nu(G,y)}{\phi_\ell(y)}\right)_-dy \le\frac1e.\] Also \(\mathbb E\left\lVert GS\right\rVert^2=\ell\), so \(\mathbb E[-\log\phi_\ell(GS)]=\frac{\ell}{2}\log(2\pi)+\frac{\ell}{2}\). The inequality \[(-\log p_\nu)_+ \le\left(\log(p_\nu/\phi_\ell)\right)_- +(-\log\phi_\ell)_+\] proves the negative logarithmic bound directly. The densities in these conclusions describe the exact labels; the cube averages only prove their estimates.

For the last assertion, conditioning on \(W=w\) dominates the joint law of \((G,S)\) by \(P(W=w)^{-1}\) times \(\gamma_\ell\otimes\nu\). This gives an actual conditional image density for every full-rank \(G\), up to the usual null set in \(G\). The product marginal is unchanged after averaging over \(w\), so the actual expectation of \(\lvert\log p_\nu(G,GS)\rvert\) is finite. The relative entropy of the actual conditional image density from \(p_\nu(G,\cdot)\), averaged over \((G,W)\), equals \(I(W;GS\mid G)\le H(W)\). The density-ratio negative part is at most \(1/e\), hence its logarithm is integrable and so is the actual log density.

Similarly, conditional data processing gives \[\mathbb ED\bigl(P_{GS\mid G,W}\Vert G_\#\nu_W\bigr) \le \mathbb ED\bigl(P_{S\mid G,W}\Vert\nu_W\bigr) =I(S;G\mid W)\le H(W).\] The last inequality follows from \(I(S;G)=0\) and the chain rule. The log ratio in this display is integrable by the same negative-part bound. Subtracting it from the actual log density proves integrability of \(\log p_{\nu_W}(G,GS)\). The argument also applies to a deterministic refinement \(W'=(W,E(S,W))\) whenever \(H(W')<\infty\). ◻

Proof. Because \(Y\) is determined by \((S,G)\), the conditional chain rule gives \[J_i(W)=I_i(S;W\mid G)-I_i(W;Y\mid G).\] Since \(S\) and \(G\) are independent in both laws, \[I_i(S;W\mid G)=I(S;W)+I_i(S;G\mid W),\] and \(I_0(S;G\mid W)=0\). The \((S,W)\) and \((S,G)\) marginals agree, so subtraction gives \[J_0(W)-J_1(W) =I_1(W;Y\mid G)-I_0(W;Y\mid G)-I_1(S;G\mid W).\] All mutual information terms are finite: those involving the countable message are at most \(H(W)\), and the last is at most \(H(W)\) by this same chain rule. Lemma 5 makes the conditional differential entropies finite. Expressing the two \(I(W;Y\mid G)\) terms as entropy differences, whose \(h(Y\mid G)\) terms agree, proves (5). In particular the conditional row-information term has a negative sign.

Apply conditional data processing to \(s\mapsto Gs\): \[\begin{align*} -h_1(Y\mid G,W)-\mathbb E_1\log p_{\nu_W}(G,Y) &=\mathbb E_1 D(P_1(Y\in\cdot\mid G,W)\Vert G_\#\nu_W)\\ &\le\mathbb E_1 D(P_1(S\in\cdot\mid G,W)\Vert\nu_W)\\ &=I_1(S;G\mid W). \end{align*}\] The integrability assertion of the same lemma justifies these subtractions. Substituting this inequality into (5) proves (6).

Finally \[J_i(W')=J_i(W)+I_i(S;E\mid W,G,Y).\] The difference for \(W\) therefore equals the difference for \(W'\) minus the \(i=0\) term and plus the \(i=1\) term. The former is nonnegative and the latter is at most \(H(E\mid W)\). This proves (7). ◻

Proof. For almost every \((s,w)\), let \(K_{s,w}\) be the conditional law of \(X\). Since \(X\) and \(S\) are initially independent, the conditional chain rule gives \[ \mathbb E_{S,W}D(K_{S,W}\Vert\gamma_m) =I(X;W\mid S)\le H(W)<\infty. \tag{17}\] Thus \(K_{s,w}\ll\gamma_m\) for almost every \((s,w)\). For fixed \(s,w,\delta\), define \[F_{w,\delta}(s,x)= \mathbb E_Zp_{\rho_w,\delta}((x;Z),(x;Z)s).\] The every-signal estimate (10) says that \(\|F_{w,\delta}(s,\cdot)\|_{L^q(\gamma_m)}\le C_w\), uniformly in \(\delta\). Conditional on \((S,X,W)\), \(Z\) still has its independent Gaussian law. Jensen in \(Z\), followed by (2) with the nonnegative test \(q\log(1+F_{w,\delta})\), gives \[\begin{align*} \mathbb E\!\left[\log(1+p_{\rho_w,\delta}(G,Y)) \,\middle|\,S=s,W=w\right] &\le \mathbb E_{K_{s,w}}\log(1+F_{w,\delta}(s,X))\\ &\le \frac{D(K_{s,w}\Vert\gamma_m)}q +\frac1q\log\mathbb E_{\gamma_m}(1+F_{w,\delta}(s,X))^q\\ &\le \frac{D(K_{s,w}\Vert\gamma_m)}q+\log(1+C_w). \end{align*}\] The last step is the \(L^q\) triangle inequality, valid since \(q\ge1\). Average over \((S,W)\) and use (17) to obtain (15).

It remains to specify the null set for the limit in the actual experiment. The marginal law of \((G,S)\) is \(\gamma_\ell\otimes\nu\). Lemma 5 therefore gives a Lebesgue density for the actual conditional law of \(Y\) given \((G,W)\). For each \(w\) and every full-rank \(g\), Lebesgue differentiation for \(g_\#\rho_w\) says that \(p_{\rho_w,1/j}(g,y)\to p_{\rho_w}(g,y)\) outside a Lebesgue-null set of \(y\). The actual conditional density gives that set zero probability. Gaussian \(G\) has full rank almost surely, and there are only countably many \(w\), proving the asserted almost-sure convergence under the actual law.

The functions \(\log(1+p_{\rho_W,1/j}(G,Y))\) are nonnegative. Fatou applied now, after the row-law change, passes (15) to (16). Since \(\log^+x\le\log(1+x)\), the positive logarithmic part is integrable; the negative part may have infinite mean, in which case the extended expectation of \(\log p_{\rho_W}\) is \(-\infty\) and the upper bound remains valid. Applications that subtract this logarithm verify its full integrability separately. Finally, \(E\) is determined by \((S,W)\), so \(I(X;E\mid S,W)=0\); the chain rule proves the refinement identity. ◻

Proof. At each relevant scale \(i\), take a maximal \(r_i\)-separated set of centers on the sphere, and assign each point to a nearest center, breaking ties in a fixed order. Denote the cells and centers by \(C_{ih}\) and \(c_{ih}\). Each cell is contained in \(B(c_{ih},r_i)\). At most \(7^d\) centers lie within \(3r_i\) of a fixed center: the ambient balls of radius \(r_i/2\) about those centers have disjoint interiors and lie in a ball of radius \(7r_i/2\).

Let \(b_{ih}\) be the sum of the \(\nu\)-masses of cells with centers within \(3r_i\) of \(c_{ih}\). For \(s\in C_{ih}\), \(\nu(B(s,r_i))\le b_{ih}\), and \(\sum_h b_{ih}\le7^d\). Partition the sphere by its first maximizing scale \(i(s)\) and its cell at that scale. Write \(w_{ih}\) for the masses of these classes, omitting zero-mass classes. If \(N_0\le C(1+d+\log K)\) is the number of relevant scales, Jensen gives \[ \mathbb E\log\frac{\nu(B(S,r_{i(S)}))} {w_{i(S),h(S)}} \le \log\sum_{i,h:w_{ih}>0}b_{ih} \le d\log7+\log N_0. \tag{35}\]

In a class \((i,h)\), let \(\nu_{ih}\) be the conditional law of \(S\). Its points are within \(r_i\) of \(c_{ih}\). Comparing the density of \(GS\) with the Gaussian density of mean \(Gc_{ih}\) and covariance \(r_i^2I_m\), nonnegative relative entropy yields \[\mathbb E_{G,S\sim\nu_{ih}}\log p_{\nu_{ih}}(G,GS) \ge m\log(1/r_i)-Cm,\] because independence gives \(\mathbb E\|G(S-c_{ih})\|^2\le mr_i^2\). Also \(p_\nu\ge w_{ih}p_{\nu_{ih}}\) almost everywhere. Average its logarithm under each class. The identity \(L_\nu(S)=r_{i(S)}^{-m}\nu(B(S,r_{i(S)}))\) then gives \[\mathbb E\log p_\nu(G,GS) \ge \mathbb E\log L_\nu(S) -\mathbb E\log\frac{\nu(B(S,r_{i(S)}))} {w_{i(S),h(S)}}-Cm.\] Apply (35). The refinement is finite, and every class is dominated by a finite multiple of \(\sigma\); Lemma 5 justifies all logarithmic expectations. ◻

Proof. For every ambient ball and \(t>0\), \[ \mu(B(z,t))\le C_0^d\frac{a}{w_a}t^m, \qquad \mu(B(z,t))\le C_0^d\frac{K}{w_a}t^N \tag{37}\] with one absolute \(C_0\). For the first estimate, if the ball has positive \(\mu\)-mass, choose \(s_0\in F_a\cap B(z,t)\). For \(t\le1\), a dyadic radius between \(2t\) and \(4t\) contains \(B(z,t)\cap F_a\), and its \(\nu\)-mass is at most \(2a(4t)^m\). For \(t>1\), use total mass one and \(a\ge2^{-m}\). The second estimate follows from \(\mu\le(K/w_a)\sigma\) and (30).

Apply the shared/fresh moment theorem, Theorem 7, with \(k\) shared rows, \(j\) fresh rows, total row count \(m\), moment order \(q\), and \[B_0=C_0^d a/w_a,\qquad D_0=C_0^d K/w_a.\] Its angular gap is \(m-k-(q-1)\ge1\), and its radial gap is \(N-m>0\). The inverse factor in its one-point integration is exactly \[\|u-s\|^{-j}\operatorname{dist}(u-s,V)^{-k}, \qquad \dim V\le q-1.\] The ratio \(D_0/B_0=K/a\) does not contain \(w_a\), and \(\log^+(K/a)\le\log K+m\log2\). The theorem therefore gives the right side of (36) uniformly in the cube-average scale, for every fixed \(s\).

For completeness, the passage to the exact density has the almost-everywhere scope asserted here. At \(Gs\) the cube averages converge for almost every \((G,s)\) under \(\gamma_m\otimes\mu\): condition on \(G\), use absolute continuity of its image law and Lebesgue differentiation, and then apply Fubini. For \(\mu\)-almost every fixed \(s\), Fatou first in \(B\) and then in \(X\) after taking the \(q\)-th power gives (36). This passage estimates the exact label; it does not change the learner’s observation. The expansion into independent points underlying the moment theorem is related to the projection-moment method of Sharan, Sidford, and Valiant [9]; the multirow estimate used here is the local theorem with the displayed parameters. ◻

Proof. First take \(V=U\), or a finite refinement of \(U\) determined by \((S,U)\). Let \(P\) be the actual law and \(Q\) the law with the same \((S,V)\) marginal and an independent \(G\sim\gamma_m\). Their \((G,S)\) marginals also agree. Write \(\nu_v=P_{S\mid V=v}=Q_{S\mid V=v}\). Proposition 6 gives the exact identity \[ \mathcal D(V)-\widetilde{\mathcal D}(V) =I_P(V;GS\mid G)-I_Q(V;GS\mid G)-I_P(S;G\mid V). \tag{39}\] Its density bound specializes to \[ \mathcal D(V)-\widetilde{\mathcal D}(V) \le \mathbb E_P\log p_{\nu_V}(G,GS) -\mathbb E_Q\log p_{\nu_V}(G,GS). \tag{40}\] The negative term in (39) is what pays for the changed conditional image density. All quantities are finite by Lemma 5 and \(I_P(S;G\mid V)\le H(V)\).

For \(u\) of positive probability let \(K_u=P(U=u)^{-1}\), so \(\nu_u\le K_u\sigma\). Let \(J\) be the integer with \(S\in F_{2^J}\) for the levels of \(L_{\nu_U}\), and put \(V=(U,J)\). The level count and Jensen give \[ H(J\mid U) \le \mathbb E\log\!\bigl(C(1+d+\log K_U)\bigr) \le \log\!\bigl(C(1+d+H(U))\bigr). \tag{41}\] Under \(Q\), refinement increases the mean log projection density by \(I_Q(J;GS\mid G,U)\ge0\). Applying Lemma 11 to each \(\nu_u\) therefore yields \[ \mathbb E_Q\log p_{\nu_V}(G,GS) \ge \mathbb E\log L_{\nu_U}(S)-Cd -\log\!\bigl(C(1+d+H(U))\bigr). \tag{42}\]

For the actual upper bound, condition on \(S=s,V=v=(u,b)\) and write \(a=2^b\). Conditional on \((s,v,X)\), \(B\) is still independent with law \(\gamma_j\). Jensen in \(B\) bounds the conditional mean of \(\log p_{\nu_v}(G,Gs)\) by the mean, under \(P_{X\mid s,v}\), of \(\log\mathbb E_Bp_{\nu_v}((X;B),(X;B)s)\). Apply (31) with reference \(\gamma_k\), order \(q\), and Lemma 12. The conditional divergences average to \[ \mathbb E D(P_{X\mid S,V}\Vert\gamma_k) =I_P(X;V\mid S)=I_P(X;U\mid S)\le H(U). \tag{43}\] The first equality uses marginal independence of \(X,S\); the second uses that \(J\) is determined by \((S,U)\). Thus the refinement creates no additional conditional row information. Finite average divergence also gives \(P_{X\mid S,V}\ll\gamma_k\) almost everywhere. The exact moment is needed only for \(\nu_v\)-almost every \(s\), which is precisely the conditional signal law at \(V=v\).

If \(w_a=\nu_u(F_a)\), the logarithm of the moment bound is \[Cd+\log a+\log(1/w_a)+\log(1+d+\log K_u).\] Averaging, using \(\mathbb E\log(1/w_a)=H(J\mid U)\), and applying Jensen once more, we obtain \[ \mathbb E_P\log p_{\nu_V}(G,GS) \le Cd+\mathbb E\log a+H(J\mid U) +\log(1+d+H(U))+\frac{H(U)}q. \tag{44}\] The log expectations and the truncated use of (31) are justified by the integrability already established.

Finally, \(\log a\le\log L_{\nu_U}(S)\), so the local-density terms in (42) and (44) cancel. Refinement gives \[\mathcal D(U)\le\mathcal D(V),\qquad \widetilde{\mathcal D}(V) \le\widetilde{\mathcal D}(U)+H(J\mid U).\] Combine these inequalities with (40) and (41). Since \(q\) is a fixed positive fraction of \(d\) for large \(d\), the result is (38). ◻

Proof. Let \(P\) denote the actual law. We first construct the refinement and obtain the two geometric estimates it supplies. For \(\pi_v=P(V=v)>0\), write \(\nu_v=P_{S\mid V=v}\le\pi_v^{-1}\sigma\), and define \[\lambda_v(s)=\max_{i\ge0} r_i^{-k}\nu_v(B(s,r_i)), \qquad r_i=2^{1-i}.\] Let \(j\) be the first maximizing index and let \(b=\lfloor\log_2\lambda_v(s)\rfloor\). The maximum is attained: its \(i=0\) term is \(2^{-k}\), while \(\pi_v^{-1}2^N r_i^{N-k}\) bounds the \(i\)-th term and tends to zero. The ball-mass functions are Borel, so both labels are measurable. The same bounds give \[b\ge-k,\qquad 2^b\le\pi_v^{-1}C^d,\qquad 2^{-k}\le\pi_v^{-1}C^d r_j^{N-k}.\] Because \(N-k\ge d/3\), the last inequality implies \(j\le C(1+\log(1/\pi_v)/d)\). At fixed \(v\), the number of pairs \((j,b)\) is at most \(C(d+1+\log(1/\pi_v))^2\). For \(W=(V,j,b)\) evaluated at \(s=S\), this proves finiteness and \[ H(W\mid V)\le C+2\log(d+1+H(V)). \tag{47}\]

For \(w=(v,j,b)\) with \(\pi_w=P(W=w)>0\), set \(R=r_j\). Let \(E_w\) be the corresponding subset of the sphere, and write \[\nu_w=P_{S\mid W=w} =\alpha_w\,\nu_v|_{E_w},\qquad \alpha_w=\frac{\pi_v}{\pi_w}.\] Every \(s_0\in E_w\) satisfies \[\nu_v(B(s_0,R))\ge2^bR^k,\qquad \nu_v(B(s_0,r_i))\le2^{b+1}r_i^k\quad(i\ge0).\] Choose centers in \(E_w\) successively at distances greater than \(2R\) from those already chosen, until their \(2R\)-balls cover \(E_w\). Their \(R\)-balls are disjoint and each has \(\nu_v\)-mass at least \(2^bR^k\); hence the process stops with at most \((2^bR^k)^{-1}\) centers. Assign each point to one of its covering balls. Under the independent matrix \(G\), conditioning also on this finite index adds at most \(-b\log2-k\log R\) to the entropy. Within a ball, comparison with a Gaussian of covariance \((2R)^2I_k\) adds at most \(k\log R+Ck\), since \(\mathbb E\|G(S-z)\|^2\le4kR^2\) for its center \(z\). Consequently \[ h_{\mathrm{ind}}(GS\mid G,W=w)\le-b\log2+Ck. \tag{48}\] The entropies are finite by Lemma 5.

The same labels give, for all \(z\in\mathbb R^d\) and \(\rho>0\), \[ \nu_w(B(z,\rho)) \le C_0^d\min\{U_w\rho^k,\ \Gamma_w\rho^N\}, \qquad U_w=\alpha_w2^b,\quad \Gamma_w=\pi_w^{-1}. \tag{49}\] For the first bound, choose a point of \(E_w\) in the ball when there is one, double the radius, and use a dyadic radius in \([2\rho,4\rho]\) if \(\rho\le1\). The upper ball bound at that point and restriction by \(\alpha_w\) prove the assertion. For larger \(\rho\), use total mass one and \(U_w\ge2^{-k}\). The second bound follows from \(\nu_w\le\Gamma_w\sigma\) and (30). Notice that \(\alpha_w\ge1\), \(\Gamma_w\ge1\), and \(U_w\ge2^{-k}\).

We next express the information difference in terms of exact projection densities. Let \(Q\) denote the independent law preserving \((S,W)\). Their \((D,S)\) and \((G,S)\) marginals agree after identifying the matrices. Hence \(h_Q(GS\mid G)=h_P(DS\mid D)\). Proposition 6 gives \[ \mathcal J(W)-I_P(S;W\mid D,DS) =h_Q(GS\mid G,W)-h_P(DS\mid D,W)-I_P(S;A\mid W). \tag{50}\] Here independence of \(B\) from \((S,A,W)\) reduces \(I_P(S;D\mid W)\) to \(I_P(S;A\mid W)\). Lemma 5 makes the baseline and conditional entropies finite; it also gives the actual conditional image density. Thus (50) is an identity of finite quantities, with the displayed negative sign.

For a matrix \(D\), let \(p_{w,D}\) be a density of the image of \(\nu_w\) under \(s\mapsto Ds\). This denominator uses \(\nu_w=P_{S\mid W=w}\) before conditioning on the actual rows. Contraction of \[\mathbb E D(P_{S\mid A,W}\Vert\nu_W)=I_P(S;A\mid W)\] under \(s\mapsto Ds\), with \(B\) still independent, gives \[ -h_P(DS\mid D,W)-I_P(S;A\mid W) \le \mathbb E_P\log p_{W,D}(DS). \tag{51}\] The numerator after contraction is the true conditional image density given \((D,W)\). Its log ratio to \(p_{W,D}\) is integrable: the relative entropy is finite, and the negative part of a log likelihood ratio has expectation at most \(1/e\). Subtracting this ratio from the integrable actual log density also proves integrability of the right side.

Here we choose a density version that retains a bound at every fixed target \(s\). For each positive integer \(a\), let \(\varphi_\delta^a\) be the centered Gaussian density of covariance \(\delta^2I_a\), and fix a sequence \(\delta_t\downarrow0\). For any probability measure \(\nu\le K\sigma\), define \[F_\delta^\nu(g,s) =\int\varphi_\delta^k(g(u-s))\,\nu(du),\qquad p^\flat_\nu(g,y) =\liminf_{t\to\infty} \int\varphi_{\delta_t}^k(gu-y)\,\nu(du).\] These functions are measurable. For each full-rank \(g\), the Gaussian approximate identity converges to the image density at its Lebesgue points, so \(p^\flat_\nu(g,\cdot)\) is a density version. It may be defined by a liminf on the exceptional set; this choice is useful at a fixed target. It is valid in (51), since the actual conditional image law is absolutely continuous.

There is a quantitative first-density passage under the independent law, before taking logarithms. For independent \(G\sim\gamma_k\) and \(S\sim\nu\), Gaussian integration and Tonelli give \[\begin{align*} \mathbb E_{G,S}F_\delta^\nu(G,S) &= (2\pi)^{-k/2}\iint (\|u-s\|^2+\delta^2)^{-k/2}\,\nu(du)\nu(ds) \\ &\le (2\pi)^{-k/2}\iint \|u-s\|^{-k}\,\nu(du)\nu(ds)<\infty. \tag{52}\end{align*}\] The last integral is finite uniformly in \(s\): the diagonal has zero mass, and the centered cap bound on dyadic shells gives \[\sup_{s\in S^{d-1}}\int\|u-s\|^{-k}\,\nu(du) \le 1+K2^k\sum_{i\ge0}2^{-i(N-k)}<\infty.\] At \(GS\) the approximate identity converges almost surely under the independent law, by absolute continuity of the image, Lebesgue differentiation, and Fubini. Fatou in (52) therefore gives \[\mathbb E_{G,S}p^\flat_\nu(G,GS) \le (2\pi)^{-k/2}\iint\|u-s\|^{-k}\,\nu(du)\nu(ds)<\infty.\] This proves the positive logarithmic part directly. For the negative part compare with the standard Gaussian density \(\phi\) on \(\mathbb R^k\): \(t(\log t)_-\le1/e\) bounds the negative part of \(\log(p^\flat_\nu/\phi)\), and \(\mathbb E\|GS\|^2=k\) bounds the cross entropy with \(\phi\). This recovers independent log integrability for this density version. Actual log integrability is supplied by the contraction preceding (51). In what follows take \(p_{w,D}=p^\flat_{\nu_w}(D,\cdot)\). The mollifiers here only specify and estimate densities at exact labels.

It remains to bound those densities under independent rows before changing the law of \(A\). We claim that for every fixed \(w\) of positive probability and every \(s\in S^{d-1}\), \[ \left[\mathbb E_A \bigl(\mathbb E_B p^\flat_{\nu_w}((A;B),(A;B)s)\bigr)^q \right]^{1/q} \le e^{Cd}U_w(1+\log\Gamma_w), \tag{53}\] where \(A\sim\gamma_n\) and \(B\sim\gamma_l\) are independent in this displayed expectation. We prove the uniform-in-\(\delta\) version first, with \[F_\delta(A,B,s) =\int\varphi_\delta^k((A;B)(u-s))\,\nu_w(du).\] For \(h=u-s\), \[\mathbb E_B\varphi_\delta^l(Bh) =(2\pi)^{-l/2}(\|h\|^2+\delta^2)^{-l/2}.\] Expanding the \(q\)-th power introduces \(u_1,\ldots,u_q\) and \(h_i=u_i-s\). For their Gram matrix \(K=(\langle h_i,h_j\rangle)_{i,j}\), Gaussian integration in the \(n\) shared rows gives exactly \[\mathbb E_A\prod_{i=1}^q\varphi_\delta^n(Ah_i) =(2\pi)^{-nq/2}\det(K+\delta^2I_q)^{-n/2}.\] Using \(\det(K+\delta^2I_q)\ge\det K\) and Gram–Schmidt, we conclude \[ \mathbb E_A\bigl(\mathbb E_B F_\delta(A,B,s)\bigr)^q \le (2\pi)^{-kq/2} \int\prod_{i=1}^q \|u_i-s\|^{-l}\operatorname{dist}(u_i-s,L_{i-1})^{-n} \,\nu_w^{\otimes q}(d\mathbf u), \tag{54}\] where \(L_{i-1}\) is the span of \(u_1-s,\ldots,u_{i-1}-s\), starting with \(\{0\}\). An infinite upper bound is allowed at singular Gram matrices. All integrations so far are nonnegative.

We bound the corresponding one-point integral uniformly over \(s\) and every linear subspace \(L\) of dimension at most \(q\). On a radial shell \(R/2<\|u-s\|\le R\), \(R=2^{1-i}\), the part at distance at most \(2^{-a}R\) from \(L\) is covered by at most \((3\cdot2^a)^q\) balls of radius \(2^{1-a}R\). This follows by covering the radius-\(R\) projection ball in \(L\) with a \(2^{-a}R\)-net. By (49) its \(\nu_w\)-mass is at most \[C^d\min\{ U_w2^{-a(k-q)}R^k,\, \Gamma_w2^{-a(N-q)}R^N\}.\] In particular the set at distance zero has zero mass. On the band \(2^{-a-1}R<\operatorname{dist}(u-s,L)\le2^{-a}R\), the integrand \(\|u-s\|^{-l}\operatorname{dist}(u-s,L)^{-n}\) is at most \(2^k2^{an}R^{-k}\). Sum the transverse bands first. The positive gaps \(k-q-n\) and \(N-q-n\) make both sums geometric, so the integral on the radial shell is at most \[C^d\min\{U_w,\Gamma_wR^{N-k}\}.\] For the radial sum put \(a_0=N-k\ge d/3\). The sum of \(\min\{1,(\Gamma_w/U_w)2^{a_0(1-i)}\}\) has at most \(2+(\log_2(\Gamma_w/U_w))_+/a_0\) saturated terms followed by a geometric tail. Since \(U_w\ge2^{-k}\) and \(\Gamma_w\ge1\), this proves \[ \int\|u-s\|^{-l}\operatorname{dist}(u-s,L)^{-n}\,\nu_w(du) \le e^{Cd}U_w(1+\log\Gamma_w). \tag{55}\] Integrate (54) from its last point to its first, applying (55) each time. This proves the claimed bound uniformly in \(\delta\).

The liminf version now gives the exact fixed-target conclusion: for every fixed \(s\), \[\mathbb E_Bp^\flat_{\nu_w}((A;B),(A;B)s) \le\liminf_{t\to\infty}\mathbb E_BF_{\delta_t}(A,B,s)\] by Fatou in \(B\). Raise to the \(q\)-th power and apply Fatou in \(A\). The uniform moment bound proves (53), including at targets where a density version specified only almost everywhere would not have sufficed. This is the distinct fixed-target passage used in this comparison.

We finally pay for dependence of the actual rows. Their conditional relative entropies satisfy \[ \mathbb E D(P_{A\mid S,W}\Vert\gamma_n) =I_P(A;W\mid S)=I_P(A;V\mid S)\le H(V). \tag{56}\] Here \(A,S\) are marginally independent, and \(W\) adds only a function of \((S,V)\). Given \((S,W,A)\), \(B\) is still independent. Jensen in \(B\), followed by (31) for the true \(P_{A\mid S,W}\) relative to \(\gamma_n\), uses (53) to give \[ \mathbb E_P\log p^\flat_{\nu_W}(D,DS) \le \frac{H(V)}q+Cd+ \mathbb E\bigl[\log\alpha_W+b\log2+ \log(1+\log\Gamma_W)\bigr]. \tag{57}\] Finite average divergence ensures the required absolute continuity. Truncation permits the conditional inequality wherever a log expectation is negative infinite; the integrated cross entropy is finite by (51).

The \(b\log2\) term cancels (48) when substituted with (57) into (50)–(51). Moreover \[\mathbb E\log\alpha_W=H(W\mid V),\qquad \mathbb E\log(1+\log\Gamma_W)\le\log(1+H(W)).\] Removing the refinement costs another \(H(W\mid V)\), since \[\mathcal J(V)\le\mathcal J(W),\qquad I_P(S;W\mid D,DS)\le I_P(S;V\mid D,DS)+H(W\mid V).\] Thus the full quantitative budget is \[ \mathcal J(V)-I_P(S;V\mid D,DS) \le Cd+\frac{H(V)}q+2H(W\mid V)+\log(1+H(W)). \tag{58}\] Only now use \(H(V)\le d^2\), \(q=\lfloor d/8\rfloor\), and (47). They bound the right side by \(Cd\), proving (46). ◻

Proof. The rows have full rank almost surely. Their labels determine the row-space component of \(S\). Rotational invariance makes the remaining direction uniform in the kernel, conditionally on its length and the data. Representing a uniform sphere point as a standard Gaussian vector divided by its norm proves the ratio law in (62). For \(n>2\), independence and the chi-squared density give \(\mathbb E G_n^{-1}=1/(n-2)\) and \(\mathbb E G_j=j\), proving the inverse moment.

Let \(P\) be projection onto the kernel and let \(x\) be a new row. Conditional on \(D_j,x\), the new label is a fixed shift plus \[R\|Px\|U_1,\] where \(U\) is uniform on \(S^{n-1}\). The density of \(U_1\) is proportional to \((1-u^2)^{(n-3)/2}\) on \((-1,1)\). Its normalizing integral is at least \(c/\sqrt n\), by integrating over \(|u|\le1/\sqrt n\). For the dimensions in use this density is at most \(C\sqrt n\), and hence \[h(U_1)\ge-\log(C\sqrt n).\] Its log density is integrable: near an endpoint this is the integrability of \(t^\alpha|\log t|\) for \(\alpha>-1\).

Also \(\|Px\|^2\) is chi-squared with \(n\) degrees of freedom. For \(j\le3d/4\), the inverse moments of \(R\) and \(\|Px\|/\sqrt n\) are bounded by absolute constants. Jensen’s inequality gives, for example, \[\mathbb E\log R\ge-\tfrac12\log\mathbb E R^{-2}\ge-C, \qquad \mathbb E\log(\|Px\|/\sqrt n)\ge-C.\] Ordinary positive moments control the positive logarithmic parts. The entropy formula under scaling now gives an absolute lower bound for the conditional entropy of the next label. The upper bound is \(\tfrac12\log(2\pi e)\), the entropy of its marginal standard normal law. These calculations also give absolute integrability of the conditional log density. Applying the chain rule in any order gives the same conclusion for all ordered subsets of labels with the stated row budget. Extra independent rows may be conditioned on before \(V\) is added, since they do not change these baseline distributions.

Adding the finite state reduces a joint label entropy by a conditional mutual information at most \(H(V)\). To check absolute integrability as well, let \(r=dQ/dP\) be the density ratio of the conditional joint law to its product-of-conditionals reference law. The negative part of \(\int\log r\,dQ\) is at most \(1/e\), because \(-r\log r\le1/e\) for \(0<r\le1\). Finite relative entropy therefore also makes the positive part integrable. The log density after conditioning on \(V\) is the baseline log density plus this integrable log ratio. All label-entropy chain rules just used are consequently between finite quantities.

For \(n=1\) the cap bound is the trivial bound one. For \(n\ge2\), first scale to \(R=1\) and center the ball at a sphere point. If its radius is \(a\le1/2\), its projection onto the tangent coordinate plane lies in an \((n-1)\)-ball of radius \(a\). The graph area factor there is at most \(2\), while the whole sphere has area at least twice the volume of the unit \((n-1)\)-ball. The cap has mass at most \(a^{n-1}\). For an arbitrary center, choose a sphere point in the intersection, if one exists, and double the radius. This proves the displayed arbitrary-center bound.

Finally, for a sphere point \(s\), integrate the centered cap estimate against \(t^{-2}\,dt\) for \(0<t\le R/2\); the integral is bounded by \[R^{-(n-1)}\int_0^{R/2}t^{n-3}\,dt\le C/R\] when \(n\ge3\). The part with \(t>R/2\) is at most \(C/R\) using total mass one. The layer-cake formula for \(\|t-s\|^{-1}\) proves (63). ◻

Proof. We first relate \(G_i(k)\) to conditional information without subtracting differential entropies of the singular signal. Suppose \(D=(A,AS)\) has the marginal law of \(k\) independent Gaussian measurements, although its rows may have helped produce \(V\). The conditional relative-entropy chain rule gives \[I(S;V\mid D)-I(S;V)=I(D;V\mid S)-I(D;V).\] Every term here is finite, being bounded by \(H(V)\). The labels are determined by \(A,S\), and \(A\) is marginally independent of \(S\). Expanding the finite terms involving \(V\) therefore yields \[ I(S;V\mid D)=I(S;V)-h(AS\mid A)+h(AS\mid A,V)+I(S;A\mid V). \tag{69}\] The label entropies are finite by Lemma 16. In a hybrid, the fresh rows contribute zero to the last mutual information. All hybrids have the same baseline entropy \(h(AS\mid A)\). Thus \[J_k(V)-I(S;V\mid D_m,D'_{k-m})=G_0(k)-G_m(k).\] Given \(D_m,D'_{k-m}\), the block transition is a Markov kernel from \(U\) to \(V\), conditionally independently of \(S\). Conditional data processing gives \[I(S;V\mid D_m,D'_{k-m}) \le I(S;U\mid D_m,D'_{k-m})=J_k(U).\] The equality holds because these \(k\) rows are fresh relative to \((S,U)\). This proves (68).

For the one-row identity, realize the two adjacent hybrids using the same \(r\) fresh rows \(Z\), one further fresh row for \(G_i(k)\), and the actual row \(x\) for \(G_{i+1}(k)\). Expand the labels in the order \(Y_{\le i},ZS,\text{last label}\). Before the last row is added the common part is \[h(Y_{\le i}\mid X_{\le i},V) +I(S;X_{\le i}\mid V)+h(ZS\mid Z,L).\] The remaining term for \(G_i(k)\) is \(a_{r+1}^{(i)}\). For \(G_{i+1}(k)\), conditioning the first two label groups on the actual row subtracts, respectively, \[I(Y_{\le i};x\mid X_{\le i},V) \quad\hbox{and}\quad I(ZS;x\mid Z,L).\] Its new row-information term is initially \(I(S;x\mid X_{\le i},V)\). The first subtraction leaves \(I(S;x\mid L)\), because the old labels are determined by \(S,X_{\le i}\). The second leaves \(I(S;x\mid F_r,L)\): the fresh matrix \(Z\) is independent, and \(ZS\) is determined by \(S,Z\). The last label then contributes \(h(Y\mid x,F_r,L)\). This proves (65) and retains both earlier-label subtractions.

Conditional on \(S,X_{\le i}\), the unconditioned law of \(X_{i+1}\) is \(\gamma\), and the labels in \(L_i\) are redundant. The definition of conditional mutual information proves (66). Summing it is the conditional chain rule for \(X_1,\ldots,X_m\). The resulting information is at most \(H(V)\), proving (67). In particular the conditional actual-row laws have finite divergence from \(\gamma\) almost surely. ◻

Proof. Fix a previous span \(P\) of dimension \(p<q\), and let \(E\) be the row space of the next matrix. When \(p>0\), set \[\xi(P,E)=\inf_{\substack{v\in P\\\|v\|=1}}\|P_Ev\|,\] and set \(\xi=1\) for \(p=0\). An operator and its adjoint have the same norm, so \(\|P_P|_{E^\perp}\|=\|P_{E^\perp}|_P\|\). For \(p>0\), taking complements of their squared norms shows, for every unit \(u\in E^\perp\), that \[ \operatorname{dist}(u,P)^2 \ge1-\|P_P|_{E^\perp}\|^2 =\inf_{\substack{v\in P\\\|v\|=1}}\|P_Ev\|^2 =\xi(P,E)^2. \tag{71}\] For \(p=0\), both the distance and \(\xi\) equal one, so all the bounds below are immediate. We may therefore assume \(p>0\) in the small-ball calculation.

The new \(E\) is a uniform \(r\)-dimensional subspace independent of the preceding selections. For a fixed unit \(v\) and \(0<t\le1/4\), \[ \mathbb P\{\|P_Ev\|\le2t\}\le(Ct)^r. \tag{72}\] Indeed \(\|P_Ev\|\) has the distribution of \(\|g\|/(\|g\|^2+\|g'\|^2)^{1/2}\), with independent standard Gaussian vectors of dimensions \(r\) and \(d-r\). The event forces \(\|g\|\le Ct\|g'\|\). The Gaussian integral, restricted to the ball of radius \(\sqrt r\), gives \((2\pi)^{r/2}\ge e^{-r/2}v_r r^{r/2}\), hence \(v_r\le(C/\sqrt r)^r\). Conditional on \(g'\), this volume estimate and the Gaussian density bound make its probability at most \((Ct\|g'\|/\sqrt r)^r\). For \(z\ge0\), \[z^{r/2}\le(2r/e)^{r/2}e^{z/4}, \qquad \mathbb E e^{\|g'\|^2/4}=2^{(d-r)/2}.\] Since \(r\ge d/8\), these estimates give \(\mathbb E\|g'\|^r\le(C\sqrt d)^r\). Averaging proves (72).

A maximal \(t\)-separated subset of the unit sphere in \(P\) is a \(t\)-net with at most \((1+2/t)^p\le(3/t)^p\) points, by packing disjoint balls of radius \(t/2\) in the ball of radius \(1+t/2\). Projection is a contraction, so \(\xi\le t\) puts some net point at projection distance at most \(2t\). By (72), \[ \mathbb P\{\xi\le t\}\le(3/t)^p(Ct)^r \le(C_0t)^{r-p},\qquad 0<t\le1/4. \tag{73}\] Here \(C_0\) is absolute because \(p<q\le r/2\). Choose a fixed \(t_0\le1/4\) such that \(C_0t_0\le1/2\). Since \(r-p>1\), integration of (73) gives \[\mathbb E\xi^{-1} =1+\int_0^1\mathbb P\{\xi<t\}\,\frac{dt}{t^2} \le C.\] For \(t\ge t_0\), the trivial probability bound suffices. The estimate is uniform in the preceding span \(P\).

Gram–Schmidt expresses the volume as the product of distances from successive preceding spans. Conditional on all previous selections, the \(p=0\) observation and (71) bound the reciprocal of the next distance by \(\xi^{-1}\), whatever vector the new kernel selects. The new row space is still independent of that history. Iterated conditional expectation therefore bounds the inverse-volume product by \(C^q\), and also shows that none of the distances vanishes with positive probability. ◻

Proof. Conditional on \(D_i,F_r\), before \(V\) is imposed, the signal is uniform on a residual sphere of affine dimension \[n=d-i-r=d-k+1>2.\] For a state \(v\) with \(\pi_v=\mathbb P\{V=v\mid D_i,F_r\}>0\), its posterior density relative to the uniform residual law is at most \(1/\pi_v\). This follows directly from Bayes’ formula, since the conditional probability of \(V=v\) given the signal and these data is at most one. Lemma 16 therefore gives \[A(s,L,F_r)\le\frac{C}{R\pi_v}\] for every point \(s\) on the residual sphere. Average first over \(s\) and \(v\). The factor \(\pi_v\) cancels, and the sum has at most \(W\) terms if \(V\) has at most \(W\) values. Consequently \[ \mathbb E A(S,L,F_r)\le CW\,\mathbb E R^{-1}<\infty. \tag{77}\] The inverse moment in (62) proves the last inequality. Every pairwise distance on the unit sphere is at most two, giving \(A\ge1/2\). In particular \(\log A\) is absolutely integrable.

The posterior is nonatomic and is absolutely continuous relative to the uniform residual law. For every row whose projection into the residual kernel is nonzero, the projection of that uniform law has a Lebesgue density, by the one-coordinate formula in Lemma 16. The exceptional rows have Gaussian measure zero. Absolute continuity passes to the projected posterior, proving the assertion about \(p_{\mu,x}\).

The information cost of conditioning this posterior on \(x\) is finite. Indeed \(x\) and \(F_r\) are conditionally independent given \(S,L\), so the conditional chain rule yields \[I(S;x\mid L)-I(S;x\mid L,F_r)=I(x;F_r\mid L)\ge0.\] Also the chain rule for the relative entropy in \(K_i\) gives \[K_i=I(S;x\mid L)+ \mathbb E D_{\rm KL}\bigl(\mathcal L(x\mid L)\,\|\,\gamma\bigr).\] Thus \[ I(S;x\mid L,F_r)\le I(S;x\mid L)\le K_i. \tag{78}\] The conditional actual law of \(S\) given \(x,L,F_r\) is therefore dominated by \(\mu\) almost surely. Projecting by \(s\mapsto xs\) contracts its relative entropy, so the actual projected law is dominated by the reference projected law with expected divergence at most \(I(S;x\mid L,F_r)\). Lemma 16 supplies an integrable log density for the actual conditional label. Applying the log-density-ratio argument from that lemma to the finite projected divergence shows that \(\log p_{\mu,x}(xS)\) is absolutely integrable as well. We may now expand the projected divergence: \[-\mathbb E\log p_{\mu,x}(xS)-h(xS\mid x,L,F_r) \le I(S;x\mid L,F_r).\] This is (75).

It remains to prove (76). Fix a typical pair \((s,L)\) under the joint law of \((S,L)\). Generate \(q\) independent copies \(Z_1,\ldots,Z_q\) of the \(r\) fresh rows, and put \(F^{(j)}=(Z_j,Z_js)\). Let \(\mu_j,A_j\) be the corresponding posterior and scale from (74). Initially let \(x\sim\gamma\) be independent of all these matrices. We claim \[ \mathbb E_{Z_1,\ldots,Z_q,x} \prod_{j=1}^q\frac{p_{\mu_j,x}(xs)}{A_j}\le C^q. \tag{79}\]

For \(\delta>0\), replace the density in the \(j\)-th factor by its symmetric slab average \[p^\delta_{\mu_j,x}(xs) =\frac{1}{2\delta} \mu_j\{s':|x(s'-s)|\le\delta\}.\] Draw \(s'_j\) separately from \(\mu_j\), and write \(\Delta_j=s'_j-s\), \(u_j=\Delta_j/\|\Delta_j\|\). The posteriors are nonatomic, so the differences are nonzero almost surely. Conditional on these differences, the vector \((x\Delta_1,\ldots,x\Delta_q)\) is Gaussian. Its density is bounded by \[ (2\pi)^{-q/2} \prod_{j=1}^q\|\Delta_j\|^{-1} \operatorname{vol}(u_1,\ldots,u_q)^{-1}; \tag{80}\] we may use \(+\infty\) for a singular tuple. This is the usual Gaussian density bound with covariance matrix \((\langle\Delta_j,\Delta_\ell\rangle)_{j,\ell}\). Its probability in \([-\delta,\delta]^q\) is at most (80) times \((2\delta)^q\).

After division by \(\prod_j A_j\), nonnegative integration converts the resulting bound into \((2\pi)^{-q/2}\) times an inverse-volume expectation. Conditional on each \(Z_j\), the selected point in that expectation has the probability law \[ \nu_j(ds')=\frac{\mu_j(ds')}{\|s'-s\|A_j}. \tag{81}\] Each law is normalized by its own \(A_j\). Its total mass is one for every typical \(Z_j\), so the marginal law of the matrices remains the product of their original Gaussian laws. In particular the matrices have not been tilted. Both \(s\) and \(s'_j\) satisfy the labels \(Z_js\); therefore \(u_j\in\ker Z_j\). These selections, made separately conditional on their matrices and \((s,L)\), satisfy the hypotheses of Lemma 18. Indeed \[r=k-i-1\ge k_0-h_0\ge d/8,\qquad q\le r/2,\qquad r-q\ge2\] for sufficiently large \(d\). The lemma bounds the smoothed product expectation by \(C^q\), uniformly in \(\delta\).

Here is a density version that makes passage to exact evaluations legitimate. In the unbiased one-copy experiment, \(x\) is independent of \((S,L,F_r)\), so conditional on \(L,F_r,x\), the signal has law \(\mu\). The one-dimensional Lebesgue differentiation theorem applied to the integrable density \(p_{\mu,x}\) shows that \(xS\) is almost surely a Lebesgue point and that the symmetric slab averages converge to \(p_{\mu,x}(xS)\). Each slab average is jointly measurable in its kernel parameters and evaluation point. Taking its limit along \(\delta=2^{-n}\), and assigning zero when no finite limit exists, therefore gives a jointly measurable density version that agrees at these evaluations. Fubini’s theorem gives the same assertion for almost every fixed \((s,L)\). For such a pair it holds simultaneously for all \(q\) copies, since \(q\) is finite. Fatou’s lemma now proves (79).

Change only \(x\) from its unbiased law to its actual conditional law given \(S=s,L\). The \(Z_j\) remain independent of it and of one another. The divergence from the unbiased product experiment is exactly \(D_{\rm KL}(\mathcal L(x\mid s,L)\,\|\,\gamma)\). For probability laws \(Q\ll P\) and a nonnegative function \(g\), the entropy variational inequality gives \[ \mathbb E_Q\log g \le D_{\rm KL}(Q\|P)+\log\mathbb E_P g. \tag{82}\] For positive bounded \(g\) this follows from Jensen’s inequality applied to \(g/(dQ/dP)\); truncation gives the extended form. This is the standard variational identity recorded in [3]. Apply it to the product in (79). Finite row divergence transfers the unbiased almost-sure density statements to the actual law. The logarithms are integrable by (75) and (77). The expectation of the log product is \(q\) times the one-copy expectation, since the \(q\) fresh copies have the same marginal law. Divide by \(q\) and average over \((S,L)\). Equation (66) then gives (76). ◻

Proof. Write \(C_*=(L,F_r)\). Conditional on \(C_*\), the signal has law \(\mu\). For an integer \(N\ge1\), define \[w_N(s,t)=\min\{N,\|t-s\|^{-1}\},\qquad A_N(s,C_*)=\int w_N(s,t)\,\mu(dt),\] where \(w_N(s,s)=N\). Given \(S=s,C_*\), draw an auxiliary point \(S^*\) from the probability kernel \[\nu_s^N(dt)=\frac{w_N(s,t)}{A_N(s,C_*)}\,\mu(dt).\] Distances on the unit sphere are at most two, so \(1/2\le A_N\le N\) and \(d\nu_s^N/d\mu\le2N\). The marginal law of \(S^*\) need not equal \(\mu\).

Compare the joint conditional law of \((S,S^*)\) with \(\mu\otimes\mu\). Its divergence is \[\mathbb E\log\frac{w_N(S,S^*)}{A_N(S,C_*)}.\] The relative-entropy chain rule splits this into \(I(S;S^*\mid C_*)\) plus the divergence of the actual \(S^*\) marginal from the comparator \(\mu\). Hence \[\begin{align*} I(S;S^*\mid C_*) &\le\mathbb E\log\frac{w_N(S,S^*)}{A_N(S,C_*)}\\ &\le-\mathbb E\log\|S-S^*\| -\mathbb E\log A_N(S,C_*). \tag{84}\end{align*}\] The comparator divergence is finite, at most \(\log(2N)\). The points differ almost surely because \(\mu\) is nonatomic. Their log distance is absolutely integrable: its positive part is at most \(\log2\); under \(\mu\otimes\mu\) its negative part is bounded by an integrable multiple of \(\|S-S^*\|^{-1}\) by (77), and the tilted density is at most \(2N\). Thus both inequalities in (84) are between well-defined finite quantities.

After drawing \(S^*\), generate independent fresh Gaussian rows \(x_1,x_2\) and labels \(b_1=x_1S\), \(b_2=x_2S\). Before \(S^*\) is added to the conditioning, Lemma 16 gives a joint conditional density with an integrable logarithm for these labels, since \(i+r+2=k+1\le3d/4\). Fresh-row independence and data processing give \[\begin{align*} I(b_2;S^*\mid b_1,x_1,x_2,C_*) &\le I((b_1,b_2);S^*\mid x_1,x_2,C_*)\\ &\le I(S;S^*\mid C_*). \tag{85}\end{align*}\] This is finite. The log-density-ratio argument from Lemma 16 consequently gives integrable conditional log densities after \(S^*\) is added, both for the joint labels and for the first label. Their entropy chain rule justifies the conditional entropy of the second label used next.

Given \(b_1,x_1,x_2,C_*,S^*\), compare the density of \(b_2\) with the Cauchy density centered at \(x_2S^*\) and with scale \(|b_1-x_1S^*|\). The scale is positive almost surely. With \(\Delta=S-S^*\), the expected negative log of this reference density at \(b_2\) is \[\begin{align*} &\log\pi+\mathbb E\log|x_1\Delta| +\mathbb E\log\left(1+\frac{(x_2\Delta)^2}{(x_1\Delta)^2}\right) \\ &\hspace{35mm}=\mathbb E\log\|\Delta\|+C_1, \tag{86}\end{align*}\] where \(C_1\) is absolute. Conditional on nonzero \(\Delta\), the two projections divided by \(\|\Delta\|\) are independent standard normals \(G_1,G_2\). The first logarithm is integrable because \(\mathbb E|\log|G_1||<\infty\). For the ratio term, \[\log\bigl(1+(G_2/G_1)^2\bigr) =\log(G_1^2+G_2^2)-\log G_1^2,\] and both logarithms on the right are integrable by the one- and two-dimensional chi-squared densities. The cross-entropy inequality therefore gives \[h(b_2\mid b_1,x_1,x_2,C_*,S^*) \le\mathbb E\log\|\Delta\|+C_1.\]

Removing \(S^*\) from the conditioning in this entropy bound and using (84)–(85) cancels \(\mathbb E\log\|\Delta\|\). We obtain \[h(b_2\mid b_1,x_1,x_2,C_*)\le-\mathbb E\log A_N(S,C_*)+C_1.\] The left side is exactly \(a_{r+2}^{(i)}\) and is independent of \(N\). Finally \(A_N\uparrow A\) and \(\log A_N\ge-\log2\). Monotone convergence, with the integrability of \(\log A\) already proved, yields (83). ◻

Proof of Proposition 15. Equations (75) and (76) lower-bound the bracket in (65) by \(-\mathbb E\log A-C-K_i/q\). Equation (83) then gives \[h(xS\mid x,L,F_r)+I(S;x\mid L,F_r) \ge a_{r+2}^{(i)}-C-K_i/q.\] Since \(r=k-i-1\), the hybrid identity becomes \[ G_i(k)-G_{i+1}(k) \le a_{k-i}^{(i)}-a_{k-i+1}^{(i)}+C+K_i/q. \tag{87}\]

For fixed \(i\), the fresh observations are exchangeable conditional on \(L_i\). Relabel two consecutive fresh observations and then condition on the additional earlier one. Conditional entropy can only decrease, so the successive slopes \(a_j^{(i)}\) are nonincreasing in their finite range. Also \[a_j^{(i)}\le\tfrac12\log(2\pi e)\] by comparison with the marginal standard normal label.

For \(i+j\le k_1+1\), a useful lower bound is \[ a_j^{(i)}\ge-C-B/h_0. \tag{88}\] To prove it, use monotonicity to bound \(a_j^{(i)}\) below by the average of the next \(h_0\) slopes. Their sum is the joint entropy of the next \(h_0\) fresh labels given their rows, \(D'_j\), and \(L_i\). Removing \(V\) from that conditioning increases the entropy by at most \(H(V)\le B\). Without \(V\), the actual prefix and all fresh rows have the ordinary independent-row law. Each successive baseline label entropy is at least \(-C\) by Lemma 16, since the total number of rows is at most \[i+j+h_0\le k_1+1+h_0\le3d/4\] for sufficiently large \(d\). The sum is therefore at least \(-Ch_0-B\), proving (88).

Average (87) over \(k_0\le k\le k_1\). For each \(i\), its slope term is exactly \[\frac1{N_k}\sum_{k=k_0}^{k_1} \bigl(a_{k-i}^{(i)}-a_{k-i+1}^{(i)}\bigr) =\frac{a_{k_0-i}^{(i)}-a_{k_1-i+1}^{(i)}}{N_k} \le\frac{C+B/h_0}{N_k}.\] Now sum over \(i=0,\ldots,m-1\), use \(\sum_iK_i\le B\) from (67), and apply (68). This gives (61). Finally \(N_k,h_0,q\ge cd\) and \(m\le d/8\), so \(B\le d^2\) makes the displayed block cost at most \(C'd\). ◻

Proof. For \(\delta>0\), let \(\kappa_\delta(z)=(2\pi\delta^2)^{-k/2} e^{-\|z\|^2/(2\delta^2)}\). First let \(H\) be bounded and continuous, and integrate \[H(C,s,t)\kappa_\delta(C(t-s)) \quad\text{against}\quad \gamma_k(dC)\sigma(ds)\sigma(dt).\] Fix full-rank \(C\) and \(s\) with \(\|P_Cs\|<1\). Disintegration in \(z=Ct\) makes the integral in \(t\) \[\int\kappa_\delta(z-Cs)\,p_C(z) \left(\int H(C,s,t)\,d\sigma_{C,z}(t)\right)dz.\] The function multiplied by \(\kappa_\delta\) is continuous at \(Cs\). Indeed the displayed fiber parametrization is continuous at interior observations, and the test is bounded and continuous. It is bounded in absolute value by \(\|H\|_\infty\sup_zp_C(z)\). The Gaussian approximate identity therefore converges to the left integrand in (101); the preceding inverse determinant estimate makes this bound integrable in \(C\).

Alternatively fix \(s\ne t\), and integrate first in \(C\). Writing \(v=t-s\), each row integral has total weight \[(2\pi)^{-1/2}(\|v\|^2+\delta^2)^{-1/2}.\] After division by that weight, the row is a centered Gaussian with covariance \(I-vv^{\mathsf T}/(\|v\|^2+\delta^2)\). As \(\delta\downarrow0\) this law converges to the Gaussian law on \(v^\perp\). The \(k\) rows remain independent, so the limit is the right integrand in (101). Its absolute value is dominated by \((2\pi)^{-k/2}\|H\|_\infty\|s-t\|^{-k}\). This is integrable under \(\sigma\otimes\sigma\): dyadic annuli about \(s\), with (90) for the small radii, give a convergent geometric series because \(k<d-1\).

The two orders compute the same limit. They prove equality on bounded continuous tests of two finite Borel measures on the indicated Polish space. Uniqueness of finite Borel measures then proves the equality for bounded Borel tests as well. This last step is what permits measurable routing functions in the application. ◻

Proof. Fix a full-rank \(C'\) and a radius \(r\le2\). Choose a finite maximal \(r\)-separated set \(\{z_i\}\) on the sphere, and partition the sphere into Borel cells \(E_i\subseteq B(z_i,r)\), breaking ties by their indices. The enlarged balls \(B(z_i,2r)\) overlap at most \(5^d\) times: balls of radius \(r/2\) about their separated centers have disjoint interiors, and all those meeting a given point in an enlarged ball lie inside the ambient ball of radius \(5r/2\) about that point.

On \(E_i\), \[L_{w,r}(s)\le r^{-k}\int_{B(z_i,2r)}f_w\,d\sigma.\] Write \(R\) for the row space of \(C'\), \(p_R\) for the density in (91), and \(\sigma_x\) for the corresponding uniform fiber law. Conditioning on \(P_{C'}S=x\) gives \[\begin{align*} \int_{E_i}\frac{f_w(s)}{\bar f_w(C',C's)}\,d\sigma(s) &=\int_R p_R(x) \frac{\int_{E_i}f_w(s)\,d\sigma_x(s)} {\bar f_w(C',C'x)}\,dx\\ &\le\Pr\{P_{C'}S\in B(P_{C'}z_i,r)\} \le e^{Kd}r^k . \end{align*}\] The quotient is defined to be zero on zero-denominator fibers; on all other fibers its numerator is at most its denominator. The numerator vanishes on fibers outside the displayed projected ball. The last probability is under the unweighted prior and is bounded by (93). Multiplying the last two estimates and summing the cells, with their \(5^d\) overlap, yields \[ \int\frac{f_w(s)L_{w,r}(s)} {\bar f_w(C',C's)}\,d\sigma(s) \le e^{Kd}a_w . \tag{107}\]

For \(r\ge r_*\), one of the grid radii \(2,1,1/2,\ldots,r_*\) gives \(L_{w,r}\le2^k L_{w,\mathrm{grid}}\); radii greater than two are already bounded by the radius-two expression. For \(r<r_*\), (90) gives \(L_{w,r}\le r^{d-1-k}\le r_*^{d-1-k}\). A second conditioning on the projection gives \(\int f_w/\bar f_w(C',C'\cdot)\,d\sigma\le1\). We may therefore sum (107) over the grid and over states, obtaining \[\sum_w\int\frac{f_wL_w}{\bar f_w(C',C'\cdot)}\,d\sigma \le 2^k(J+2)e^{Kd}\sum_w a_w+Nr_*^{d-1-k} \le e^{Kd}.\] The bound is uniform in full-rank \(C'\), and averaging proves the claim. ◻

Proof. For \(E\) of dimension \(j\le\ell-1\), layer-cake integration of (111) gives the inverse moment \[ \int\operatorname{dist}(u,E)^{-n}\,d\mu(u) \le2^k+\frac{n\,3^j4^k}{k-j-n}\le e^{Kd}. \tag{113}\] Here \(\operatorname{dist}(u,E)\le1\); its layer-cake integral below one is \(n\int_0^1\eta^{-n-1} \mu\{\operatorname{dist}(u,E)\le\eta\}\,d\eta\). The denominator is positive because \(k-j-n\ge k-\ell+1-n\ge d/10\).

For \(u_1,\ldots,u_\ell\), let \(G=(\langle u_i,u_j\rangle)_{i,j\le\ell}\). The tube estimate, sent to \(\eta\downarrow0\), shows that each proper span of at most \(\ell-1\) preceding directions has \(\mu\)-mass zero. Thus \(G\) is invertible for \(\mu^{\otimes\ell}\)-almost every tuple. Gram–Schmidt gives \[\det G=\prod_{i=1}^{\ell} \operatorname{dist}\bigl(u_i,\operatorname{span}(u_1,\ldots,u_{i-1}) \bigr)^2 .\] Integrate \(u_\ell,u_{\ell-1},\ldots,u_1\) in that order and apply (113) at each step. This proves \[ \int(\det G)^{-n/2}\prod_{i=1}^{\ell}d\mu(u_i) \le e^{Kd\ell}. \tag{114}\]

It remains to pass from this determinant moment to singular row laws. For \(0<\delta\le1\), set \[\begin{aligned} \alpha_\delta&=\Pr\{|Z|\le\delta\},\qquad Z\sim N(0,1),\\ D_\delta(A)&=\int \frac{\mathbf 1_{\{\|Au\|_\infty\le\delta\}}}{\alpha_\delta^n} \,d\mu(u). \end{aligned}\] There is an absolute \(c>0\) such that \(\alpha_\delta\ge c\delta\). Expanding the integer \(\ell\)-th moment under \(\gamma_n\) produces one tuple \(u_1,\ldots,u_\ell\). For an invertible Gram matrix \(G\), the projections of each unrestricted Gaussian row onto those directions have density at most \((2\pi)^{-\ell/2}(\det G)^{-1/2}\). The box of allowed projections has volume \((2\delta)^\ell\). Row independence and (114) therefore give \[\mathbb E_{\gamma_n}D_\delta^\ell \le \left(\frac{(2\delta)^\ell(2\pi)^{-\ell/2}} {\alpha_\delta^\ell}\right)^n e^{Kd\ell} \le e^{Kd\ell}.\] The null set of dependent tuples was removed above. Thus \(\|D_\delta\|_{L^\ell(\gamma_n)}\le e^{Kd}\) uniformly in \(\delta\).

The measure \(D_\delta\,d\gamma_n\) is the mixture, with mixing measure \(\mu\), of the laws conditioned on \(\|Au\|_\infty\le\delta\). For each \(u\), this conditioning preserves the independent perpendicular components and makes all components along \(u\) tend to zero. For every bounded continuous test \(H\), bounded convergence in \(u\) consequently gives \(\int H D_\delta\,d\gamma_n\longrightarrow\int H\,d\lambda\). Hölder’s inequality proves (112) for those tests. Both \(\gamma_n\) and \(\lambda\) are finite Euclidean Borel measures. Bounded continuous functions are dense in \(L^{\ell/(\ell-1)}(\gamma_n+\lambda)\); approximation in this space passes the inequality to every bounded Borel \(H\). In particular no absolute continuity of the singular mixture \(\lambda\) was assumed before the dual estimate. ◻

Proof. For each state and positive index, combine the next-state and stopping choices into one finite destination set, tagging a destination as continuing or terminal. The kernel is a finite vector of completed-measurable nonnegative functions of \((x,y)\) whose sum is one. Every completed-measurable real function has a Borel version: approximate it by simple functions and replace their level sets by Borel sets modulo null sets. Choose such a version for every coordinate. The union of the exceptional sets is contained in a Borel \(\lambda\)-null set. On the Borel set where the chosen vector is not a probability vector, replace it by a fixed point mass. That set is also null. Since the horizon and all state sets are finite, a single Borel \(\lambda\)-null set \(Z\) contains every sample-pair modification. A stopping choice at index zero depends only on the initial state and the fixed seed, with fresh randomness, and has no sample argument to replace.

In the fixed-seed law, (1) leaves \(S\sim\sigma\) independent of the pre-generated Gaussian rows. For a nonzero row \(x\), the image of \(\sigma\) under \(s\mapsto\langle x,s\rangle\) has a Lebesgue density when \(d\ge2\). This follows from the one-coordinate sphere formula after rotation and multiplication by \(\|x\|\). The zero row has Gaussian probability zero. Hence every marginal sample pair \((X_t,\langle X_t,S\rangle)\) is absolutely continuous with respect to \(\lambda\). In particular, \[\mathbb P\{(X_t,\langle X_t,S\rangle)\in Z\}=0.\] For any state \(u\), even one selected using previous observations, the probability that the state before time \(t\) is \(u\) and the current pair lies in \(Z\) is bounded by this same zero probability. A finite union over the pre-generated indices therefore shows that no modified input is visited almost surely.

Couple the original and Borel finite kernels with the same fresh uniform random variable at each step. Induction makes their state paths and stopping choices identical almost surely. At identical terminal state-index pairs their output kernels agree, so the outputs may also be coupled identically. This proves the claimed joint-law equality. For any specified entering state, finite composition of the everywhere Borel kernels gives Borel block routing probabilities on every block-data vector. Such a routing function is a continuation from the specified state; it need not be a conditional law given that the state was reached. ◻

Proof. After stopping, retain the terminal state together with its stopping index in an absorbing state. Defer the output until the end of the extension and apply its original state-index kernel. Active states and all stopped pairs number at most \((T+2)2^M\). At index zero the stopping status is generated from the data-independent initialization and fresh randomness. The independence statements then follow from the pre-generated product row law. Finite composition of the Borel rules gives the asserted block kernel, including on inputs never visited in the original run.

There are at most \((T+1)2^M\) terminal state-index labels. For each label, its output kernel has no further dependence on the signal. In the success integral for that label, bound the conditional probability of reaching it by one. Lemma 3, averaged over the output kernel, bounds the remaining integral by \(\epsilon^{d-1}\). Summing proves (115), including for randomized output. When \(p\ge3/5\), taking logarithms gives \[(d-1)L\le M\log2+\log(T+1)+\log(5/3).\] For sufficiently large \(d\), uniformly for \(L\ge\log10\), \((d-1)L\ge3dL/4\) and \(\log(dL+1)\le dL/4\). On \(T\le dL\), subtraction gives \(dL=O(M+1)\). Consequently \(L=o(d)\), \(T=o(d^2)\), and \(\log N=o(d^2)\). This is a conclusion only on the stated branch; no restriction on the accuracy sequence has been imposed.

For the unrestricted-data bound, suppose \(T\le d/4\) and grant the output all \(T\) pre-generated rows and labels, including unused pairs after a stop. Given those data, the remaining signal is uniform on a sphere of radius \(R\) in a \((d-T)\)-dimensional affine space. Indeed the row-space component is determined, while rotational invariance leaves a uniform direction in the kernel. More generally, if \(U\) is the span of \(t<d\) independent Gaussian rows, isotropy and independence give \[ \mathbb E\|P_US\|^2=t/d. \tag{117}\] Taking \(t=T\) gives \(\mathbb E(1-R^2)=T/d\), so \[\Pr\{R<1/2\}\le\frac{4T}{3d}\le\frac13.\] On the complementary event, an output ball of radius \(\epsilon\) intersecting that residual sphere is contained in a ball of radius \(2\epsilon\) centered at a residual-sphere point. Rescaling by \(R\ge1/2\) and applying Lemma 3 bounds conditional success by \((4\epsilon)^{d-T-1}\). The learner’s remaining randomness has no further signal information after all data are given, so the same estimate holds after averaging its output. Thus success is at most \[\frac13+(2/5)^{3d/4-1}<\frac35\] for large \(d\), a contradiction. This argument includes \(T=0\), when the residual sphere is the original unit sphere. ◻

Proof. Let \(Q\) preserve the side-data marginal \((G,GS)\) and the conditional marginals of \(S,V\) given those data, while making \(S\) and \(V\) conditionally independent. Apply the same state-output kernel under both laws. Their relative entropy, including the output, is \(I(S;V\mid G,GS)\).

The event of angular success and \(R\ge\rho\) has actual probability at least \(p-\eta\). Under \(Q\), condition also on the output. The residual signal remains uniform on its sphere in the kernel of \(G\), independently of the output. Angular success implies Euclidean error at most \(\epsilon\). If the corresponding output ball intersects the residual sphere, centering it at one point of the intersection enlarges its radius to at most \(2\epsilon\). Rescaling the residual sphere to unit radius and applying Lemma 3 bounds the conditional success probability by \((2\epsilon/\rho)^{d-k-1}\).

For any event with actual probability \(a\) and reference probability at most \(b\), where \(0<b\le1\), binary relative entropy and data processing give \[ D(P\Vert Q)\ge a\log(1/b)-\log2. \tag{120}\] Indeed the binary entropy of \(a\) is at most \(\log2\). Applying this inequality to the preceding event proves (118). Finally (117) gives \(\mathbb E(1-R^2)=k/d\); Markov’s inequality proves (119). ◻

Proof. Use Lemma 2 with \(p_0=3/5\), and then Lemma 25. The resulting fixed-seed uniform-prior experiment retains success at least \(3/5\), the conditional initial-state law, the same state bound, and the same horizon. Transition and terminal output randomness remain fresh.

Put \(L=\log(1/\epsilon)\ge\log10\). The branch \(T\ge dL\) already has the desired order. On \(T<dL\), Lemma 26 gives padded states of entropy at most \(H_*=M\log2+\log(T+2)\le d^2\) eventually. In particular its output-capacity estimate specializes to \[ \frac35\le(T+1)2^M\epsilon^{d-1}. \tag{121}\] Use \(B=\lceil T/m\rceil\) full padded blocks, where \(m=\lfloor d/10\rfloor\) as in (18).

For a boundary state \(U\), define \[J(U)=I(S;U\mid G,GS)\] with an independent \(\ell\)-row matrix \(G\), \(\ell=\lfloor d/2\rfloor\), sampled independently of the pair \((S,U)\). In a block, write \(U,W\) for the entering and exiting states and \(A\) for its \(m\) rows. The matrix \(A\) is independent of \((S,U)\). Append an independent \(r=\ell-m\) row matrix \(C\) and set \(G=(A;C)\). In the aligned experiment \((G,GS)\) reveals the entire exact block data \((A,AS)\). Conditional on these data and \(U\), the block transition has no further dependence on \(S\). Conditional data processing therefore gives \[I_1(S;W\mid G,GS) \le I_1(S;U\mid G,GS)=J(U).\] The equality uses independence of \(G\) from the pair \((S,U)\). Theorem 10, applied to the outgoing state with \(H(W)\le H_*\le d^2\), yields \[J(W)\le J(U)+Kd.\] The initial padded state \(\overline U_0\) is independent of \(S\), and its auxiliary matrix is independent of \((S,\overline U_0)\), so \(J(\overline U_0)=0\). Iteration gives for the final padded state \(W_f\) \[ J(W_f)\le Kd\left\lceil\frac{T}{m}\right\rceil . \tag{122}\]

We next lower-bound that final information. Conditional on \((G,GS)\), the row-space projection of \(S\) is determined and the residual direction is uniform in \(\ker G\). If \(a=d-\ell\), its radius \(R\) has the marginal representation \[R^2\stackrel{\mathrm{law}}=\frac{X}{X+Y}, \qquad X\sim\chi_a^2,\quad Y\sim\chi_\ell^2\] with independent \(X,Y\). This follows by normalizing a standard Gaussian vector. Since \(a\ge d/2\), the events \(X\ge0.75a\) and \(X+Y\le1.4d\) imply \(R\ge1/2\). Chebyshev’s inequality, using variances \(2a\) and \(2d\), gives \[ \mathbb P\{R<1/2\} \le\frac{32}{a}+\frac{25}{2d}=O(1/d). \tag{123}\]

For sufficiently large \(d\), the radius tail in (123) leaves success probability at least \(1/2\) on \(R\ge1/2\). Apply Lemma 27 with \(\rho=1/2\) and that tail bound. It gives \[ J(W_f)\ge\frac{a-1}{2}\bigl(L-\log4\bigr)-\log2 \ge c_0dL \tag{124}\] for an absolute \(c_0>0\) and all sufficiently large \(d\). This is uniform over \(L\ge\log10\), because \[L-\log4\ge \left(1-\frac{\log4}{\log10}\right)L>0 .\]

The common stopping reduction gives \(T>d/4\ge m\), so \(\lceil T/m\rceil\le2T/m\). Equation (122) is therefore an \(O(T)\) upper bound. Comparing it with (124) proves \(T\ge cdL\) uniformly over the stated accuracies. ◻

Proof. For every \(k_0\le k\le k_1\), the auxiliary matrix has \(k\le d/2\) rows. At \(\rho=2/5\), (119) therefore gives \[\Pr\{R<2/5\}\le\frac{k/d}{1-4/25}\le\frac{25}{42}.\] The success probability is at least \(2/3\), and \(2/3-25/42=1/14\). Lemma 27 now gives (132), because \(\rho/(2\epsilon)=1/(5\epsilon)\). Its radius condition holds for \(\epsilon\le1/10\). ◻

Proof. Apply Lemma 2 with \(p_0=2/3\) to the original jointly measurable experiment. Fix a seed satisfying (1) with conditional uniform-prior success at least \(2/3\), retain its conditional initial-state law, and then apply Lemma 25. The fixed-seed joint experiment, state bound, and horizon are preserved.

Put \(b=\log(1/\epsilon)\). In dimensions with \(T>db\), the conclusion already holds. In the remaining dimensions, Lemma 26 permits padding with \(W=(T+2)2^M\) states and \(B=\log W=o(d^2)\), so eventually \(B\le d^2\). Break the padded computation into blocks of \(h_0\) observations, with a shorter final block if necessary. The initial padded state \(\overline U_0\) is independent of \(S\), and the side matrix is independent of the pair \((S,\overline U_0)\). Thus \(J_k(\overline U_0)=0\) for every \(k\), and its averaged potential is zero. Proposition 15 gives \[\overline J(V_{\rm final}) \le Cd\left\lceil\frac{T}{h_0}\right\rceil \le C'(T+d)\le C''T.\] The last inequality uses the independent bound \(T>d/4\) from Lemma 26; thus it also covers a shorter last block.

Lemma 29 gives the opposite bound for every \(k\) in the average. Since \(k\le d/2\) and \(b\ge\log10\), \[\log\frac1{5\epsilon}=b-\log5 \ge\frac{\log2}{\log10}\,b.\] The right side of (132) is consequently at least \(c'db\) for all sufficiently large \(d\), uniformly over the allowed accuracies. Comparing the two bounds proves \(T\ge cdb\). The dimensions with \(T>db\) were already covered. ◻

Proof. Apply Lemma 2 with \(p_0=2/3\) to the original jointly measurable uniform-prior experiment. Fix a seed \(\xi\) satisfying (1) whose conditional success is at least \(2/3\), and retain the conditional initial-state law. Then apply Lemma 25 in that fixed-seed experiment. In particular all global Borel routing extensions are fixed before (96) and the finite measure \(Q\) are formed. The two-point identity applies to those Borel functions without transferring a null set from the real observation law to a perpendicular row law.

On a product extension of this fixed-seed experiment, choose an array \(\mathcal R\) of independent uniform random variables consisting of \(R_t\), \(0\le t\le T\), and \(R^{\mathrm{out}}_{t,j}\), \(0\le t\le T\), \(1\le j\le2^M\). Choose the whole array independently of \((U_0,S,(X_t)_{t\ge1})\). The factorization (1) then implies that the complete conditional choice vector \((U_0,\mathcal R)\) is independent of \((S,(X_t)_{t\ge1})\).

Enumerate each finite state alphabet by slots \(j\le2^M\). Use \(R_0\) for a stopping choice before the first sample and, at time \(t\ge1\), use \(R_t\) to realize the joint next-state and stopping outcome by the inverse distribution function of its finite probability row. Use \(R^{\mathrm{out}}_{t,j}\) to realize the unit-vector output kernel at terminal pair \((t,j)\). Such a realization can be chosen Borel for a probability kernel on the standard Borel sphere, by mapping the sphere into a Borel subset of \([0,1]\) and using an inverse distribution function. The resulting fixed-seed experiment is jointly measurable and has the same conditional law as the Borel learner.

Its success probability averaged over \((U_0,\mathcal R)\) is at least \(2/3\). Fubini and averaging give a complete realization with uniform-prior success at least \(3/5\). Fix it. The initial state, all transition and stopping rules, and all terminal outputs are now deterministic. Independence of the complete choice vector leaves the joint law of the signal and all rows unchanged. Thus the complete vector \((\xi,U_0,\mathcal R)\), including the seed and initialization, is fixed before any state comparison. Its unused entries add no persistent learner state.

Put \(X_*=d\log(1/\epsilon)\), and restrict to \(T<X_*\). Apply Lemma 26 to the fixed decoder with success at least \(3/5\). Its output count gives \[ (d-1)\log(1/\epsilon) \le M\log2+\log(T+1)+\log(5/3). \tag{133}\] The common short-run estimate yields \(X_*=O(M+1)\), and the absorbing padded state has width at most \[ \begin{aligned} N&=(T+2)2^M,\\ \log N&\le M\log2+\log(X_*+2)=O(M+1)\le d^2 \end{aligned} \tag{134}\] for all sufficiently large \(d\). The padded decoder is a function of this state, and rows generated after stopping remain fresh.

Pad also to \(\lceil T/n\rceil\) full \(n\)-row blocks. Each block’s row matrix is independent of the pair consisting of the signal and old state, while its labels remain exact. After the complete fixation, the initial padded state is deterministic, so its potential is zero. Iterating Proposition 21 for the padded final state \(F\) gives \[ \Phi(F)\le Kd\lceil T/n\rceil. \tag{135}\] For a lower bound use the independent \(k\)-row matrix in \(\Phi(F)\). Equation (119) gives \[\Pr\{R<1/2\}\le\frac{4k}{3d}\le\frac49.\] The fixed decoder has success at least \(3/5\). Apply Lemma 27 with \(p=3/5\), \(\rho=1/2\), and \(\eta=4/9\), and write \(p_0=3/5-4/9>0\). It gives \[\begin{align*} \Phi(F) &\ge p_0(d-k-1)\log(1/(4\epsilon))-\log2 \\ &\ge c\,d\log(1/\epsilon) \tag{136}\end{align*}\] for sufficiently large \(d\). The constant is absolute because \(d-k-1\ge d/2\) and \(\log(1/(4\epsilon))\ge (1-\log4/\log10)\log(1/\epsilon)\) on the stated accuracy range.

Finally, Lemma 26 gives \(T>d/4\ge n\), including the exclusion of \(T=0\). Hence \(\lceil T/n\rceil\le2T/n\), and \(d/n\) is absolutely bounded for large \(d\). The upper bound (135) is therefore \(O(T)\). Combining it with (136) proves the corollary. ◻