Proof. For \(0<r\le1\), a chordal cap about \(u\) has angular radius \(\theta\le\pi/3\), \(\sin\theta\le r\), and \(\cos\theta\ge1/2\). Its normalized area is \[\frac{\int_0^\theta\sin^{n-1}v\,dv} {\int_0^\pi\sin^{n-1}v\,dv}.\] The numerator is at most \(2r^n/n\) after substituting \(w=\sin v\); the denominator is at least \(2/n\), since \(\int_0^{\pi/2}\sin^{n-1}v\,dv \ge\int_0^{\pi/2}\sin^{n-1}v\cos v\,dv=1/n\). For \(r\ge1\) the same bound is trivial. An ambient ball meeting the sphere is contained, on the sphere, in a radius-\(2r\) ball about any point of its intersection, proving the second bound.

The row span of \(X\) has dimension \(T\) almost surely. Its labels specify the row-space projection of \(S\). Conditional on the rows and labels, the remaining component is uniform on its sphere in \(\ker X\), with radius \(R=\|P_{\ker X}S\|\). To see this, write \(S\) as a normalized standard Gaussian and separate its independent row-space and nullspace components; the direction of the latter is independent of both lengths and of the former component.

When \(R>r_0>\epsilon\), the set of residual directions that place the signal within \(\epsilon\) of a fixed estimate cannot contain both members of any antipodal pair. Its conditional mass is at most \(1/2\), including after averaging the estimate’s independent randomness. Finally, \(\mathbb E\|P_{\operatorname{row}X}S\|^2=T/d\) by rotational invariance. Markov’s inequality applied to \(\|P_{\operatorname{row}X}S\|^2=1-R^2\) proves (3). ◻

Proof. We first derive a tube bound from (6), then estimate a smoothed projection by expanding its \(m\)th moment. Finally we pass to the exact measure. The replica expansion and Gaussian orthogonalization have a close predecessor in (Sharan et al. 2019, sec. 7, Lemma 12); the weighted multirow estimate and the exact-measure passage are proved here.

For every affine \(q\)-plane \(V\subset\mathbb R^d\) with \(q\le m-2\), we claim \[ \mu\{z:\mathop{\mathrm{dist}}(a(z),V)\le\delta\} \le BC^d\delta^{\alpha n-q}\qquad(0<\delta\le1). \tag{8}\] Projection onto the first \(n\) coordinates shows that every such \(z\) lies within \(\delta r\) of the projection of \(c_Q+rV\). Only the part of that projected plane within \(2r\) of the center of \(Q\) is needed. A maximal \(\delta r\)-separated subset of that part has at most \((C/\delta)^q\) points, by volume comparison in the plane. Balls of radius \(2\delta r\) about these points cover all relevant \(z\).

Choose \(l\ge0\) so that \(2^{-l}\le\delta<2^{-l+1}\). Each covering ball meets at most \(C^n\) level-\((J+l)\) cells. Indeed those cells are disjoint, have side greater than \(\delta r/(2\sqrt n)\), and lie inside a ball of radius \(3\delta r\). If \(v_n\) is the volume of the unit ball in \(\mathbb R^n\), the estimate \(v_n\le(2\pi e/n)^{n/2}\) gives the claimed count; the powers of \(\sqrt n\) cancel. Each such cell has mass at most \(B2^{-\alpha nl}\le B\delta^{\alpha n}\), proving (8).

By Cauchy–Schwarz, \(\nu\) has mass at most one. For \(\eta>0\) define \[F_\eta(X,u)=\int (2\eta)^{-k} \mathbf 1_{\{\|u-Xa(z)\|_\infty\le\eta\}}\,d\nu(z).\] This is smoothing in the label variable only. Expanding its \(m\)th power introduces points \(z_1,\ldots,z_m\). Put \(a_i=a(z_i)\), define \(D_i\) for \(2\le i\le m\), and set \[D_i=\mathop{\mathrm{dist}}\bigl(a_i,\mathop{\mathrm{aff}}(a_1,\ldots,a_{i-1})\bigr),\qquad \mathsf D=[a_2-a_1,\ldots,a_m-a_1],\qquad V_*^2=\det(\mathsf D^{\mathsf T}\mathsf D).\] The exponent in (8) is positive. Thus each affine span in this display has zero \(\mu\)-mass and zero \(\nu\)-mass. Almost every tuple is affinely independent, and Gram–Schmidt gives \(V_*=\prod_{i=2}^mD_i\).

The intersection of the \(m\) smoothing boxes has volume at most \((2\eta)^k\) and is empty unless \(\|X(a_i-a_1)\|_\infty\le2\eta\) for every \(i\ge2\). For a fixed affinely independent tuple, one row of these differences is Gaussian with covariance \(\mathsf D^{\mathsf T}\mathsf D\) and maximum density \((2\pi)^{-(m-1)/2}V_*^{-1}\). The \(k\) rows are independent. Bounding the probability of the difference box by its volume times this maximum density, and using Tonelli’s theorem, yields \[ \int F_\eta^m\,dP_X\,du \le C^{k(m-1)}\int V_*^{-k}\,d\nu^{\otimes m}. \tag{9}\] All powers of \(\eta\) have canceled. We now bound the right-hand side uniformly over the preceding points in each affine span.

Put \(\gamma=\alpha n-(m-2)\). Cauchy–Schwarz and (8) give, for each fixed preceding tuple, \[\nu\{D_i\le\delta\}\le(BC^d)^{1/2}\delta^{\gamma/2} \qquad(0<\delta\le1).\] The chosen \(k,m\) satisfy \(\gamma/2-k\ge n/8\). Integrating the tail of \(D_i^{-k}\) therefore gives \[\begin{align*} \int D_i^{-k}\,d\nu &\le1+k\int_0^1\nu\{D_i\le\delta\}\delta^{-k-1}\,d\delta\\ &\le1+\frac{k(BC^d)^{1/2}}{\gamma/2-k} \le C^dB^{1/2}. \end{align*}\] Integrate \(z_m,z_{m-1},\ldots,z_2\) in this order in (9); the remaining \(z_1\) integral has mass at most one. Taking the \(m\)th root gives \[\|F_\eta\|_m \le\bigl[C^{k(m-1)}(C^dB^{1/2})^{m-1}\bigr]^{1/m} \le C^dB^{1/2}.\]

To recover exact labels, let \(\psi\) be continuous and compactly supported in the variables \((X,u)\). Averaging \(\psi\) over a shrinking box and applying bounded convergence shows \[\int\psi F_\eta\,dP_X\,du \longrightarrow\int\psi(X,Xa(z))\,dP_X\,d\nu(z).\] Hölder’s inequality bounds this limiting functional by \(C^dB^{1/2}\|\psi\|_{m/(m-1)}\). Continuous compactly supported functions are dense in \(L^{m/(m-1)}(P_Xdu)\). Duality supplies an \(L^m\) density with that bound. Agreement on continuous compactly supported tests identifies the two locally finite Borel measures. This proves (7) for the exact joint law, so it can be tested against arbitrary measurable message rules. ◻

Proof. Keep the normalization \(X\phi(z)=Xc_Q+rXa(z)\) from Section 3.1. Let \(L=\{u\in\mathbb R^k:\|u\|\le4\sqrt k\}\). Since \(\|a(z)\|\le2\), \[ \mathbb P_X\{Xa(z)\notin L\}\le e^{-ck} \tag{11}\] uniformly in \(z\). For example, if \(G\) is standard Gaussian in \(\mathbb R^k\), then \(\mathbb Ee^{\|G\|^2/4}=2^{k/2}\), and Markov’s inequality at \(\|G\|>2\sqrt k\) proves this with \(c=1-\tfrac12\log2\). Also \(|L|=v_k(4\sqrt k)^k\le C^k\).

Define the subprobabilities \[p_w(z)=\mathbb E_X\bigl[\pi_w(X,X\phi(z))\mathbf 1_{\{Xa(z)\in L\}}\bigr]\] For a reference experiment, keep \(X\) Gaussian and replace the normalized exact label \(Xa(z)\) by an independent uniform point in \(L\). Its message probabilities are \[b_w=|L|^{-1}\int_L\mathbb E_X\pi_w(X,Xc_Q+ru)\,du.\] They satisfy \(\sum_wb_w=1\). This uses the probability-kernel identity at every label, including labels outside the support of the observation law. Test Lemma 6 with \(\pi_w(X,Xc_Q+ru)\mathbf 1_L(u)\). Because \(0\le\pi_w\le1\), Hölder’s inequality gives, for every \(\|h\|_2\le1\), \[\int|h|p_w\,d\mu \le C^dB^{1/2}(|L|b_w)^{1-1/m}.\] Duality in \(L^2(\mu)\) consequently gives \[ \|p_w\|_2\le A b_w^{1-1/m},\qquad A=C^dB^{1/2}\ge1. \tag{12}\]

We next turn this into information without assuming that the posterior is uniform. Adjoin the bit \(G=\mathbf 1_{\{Xa(Z)\in L\}}\) to \(W\), which can only increase mutual information. Put \(P_w=\int p_w\,d\mu\) and \(P_g=\sum_wP_w\). For \(P_w>0\), Jensen’s inequality under the probability measure \(p_w\mu/P_w\) gives \[\int p_w\log(p_w/P_w)\,d\mu \le2P_w\log(\|p_w\|_2/P_w).\] Thus the contribution from \(G=1\) to \(I(Z;W,G)\) is at most \[\begin{gathered} 2\log A-(2-2/m)\sum_wP_w\log(P_w/b_w)\\ {}+(2/m)\sum_wP_w\log(1/P_w). \end{gathered}\] If \(b_w=0\), then (12) gives \(P_w=0\), and the corresponding terms vanish. The log-sum inequality and the entropy bound for \(N\) outcomes give \[\sum_wP_w\log(P_w/b_w)\ge P_g\log P_g, \qquad \sum_wP_w\log(1/P_w)\le\log N-P_g\log P_g.\] The good contribution is therefore at most \(2\log A+(2/m)\log N-2P_g\log P_g\).

For \(G=0\), let \(q_w(z)\) be the corresponding conditional subprobability and \(Q_w=\int q_w\,d\mu\). Since \(q_w\le1\), \[\sum_w\int q_w\log(q_w/Q_w)\,d\mu \le\sum_wQ_w\log(1/Q_w) \le P_b\log N-P_b\log P_b,\] where \(P_b=1-P_g\le e^{-ck}\) by (11). The functions \(-P_g\log P_g\) and \(-P_b\log P_b\) are bounded by absolute constants. Finally \(2\log A\le Cd+\log B\), proving (10). ◻

Proof. For every measurable set \(A\), the posterior satisfies \(\lambda(A)\le\mu_0(A)/p\). A heavy cell at relative depth \(j\) therefore satisfies \[2^{-\alpha nj}\le p^{-1}2^{-n(J+j)}.\] Since \(1-\alpha>0\), this bounds \(j\). The parent cell is heavy, so each path has a deepest heavy cell. There are only finitely many cells at the relevant levels, and all selection events are measurable.

Fix a selected cell \(R\) at relative depth \(j\), and let \(R'\) be a strict descendant at further depth \(l\). If \(R'\) is heavy, the event \(\{U=R\}\cap R'\) is empty: any point of \(R'\) has a deeper heavy ancestor. If \(R'\) is not heavy, then \(\lambda(R')<2^{-\alpha n(j+l)}\). In either case, \[\mathbb P(Z\in R'\mid H=h,U=R) \le\frac{2^{-\alpha nj}}{p_R}2^{-\alpha nl} \le B_R2^{-\alpha nl}.\] At depth zero the bound follows from \(B_R\ge1\). Notice that this uses the probability \(p_R\) of selection; replacing \(p_R\) by \(\lambda(R)\) would condition on a different event.

At depth \(j\), there are at most \(K_j=2^{\alpha nj}\) heavy cells, because their posterior masses sum to at most one. The entropy chain rule and the bound on the number of choices at each depth prove (13). Comparing the depth distribution with the geometric distribution \(2^{-(j+1)}\), nonnegativity of relative entropy gives (14).

For the remaining estimate, write \(\log^+x=\max\{0,\log x\}\) for \(x>0\). Let \(P_j=\mathbb P(j(U)=j)\) and, on a level of positive mass, set \(\rho_R=p_R/P_j\). There are at most \(K_j\) possible cells on that level. Consequently, for \(u\ge0\), \[\mathbb P\!\left\{\log^+\frac1{K_j\rho_U}>u\,\middle|\,j(U)=j\right\} \le e^{-u}.\] Indeed every cell in this event has conditional mass less than \(e^{-u}/K_j\), and there are at most \(K_j\) of them. Integrating the tail shows that this positive logarithm has conditional expectation at most one. Since \[\log B_R =\log^+\frac1{K_jP_j\rho_R} \le\log(1/P_j)+\log^+\frac1{K_j\rho_R},\] averaging over the levels proves (15). ◻

Proof of Theorem 5. Start with \(\Pi_0\) empty, \(Q_0\) as above, \(J_0=0\), and \(B_0=1\). After observing \(W_i\), put \(\Pi_i^-=(\Pi_{i-1},W_i)\). Apply Lemma 8 to this history and the parent \(Q_{i-1}\). Let \(Q_i\) be the selected cell, \(j_i\) its relative depth, and \(J_i=J_{i-1}+j_i\). Set \(\Pi_i=(\Pi_i^-,Q_i)\), and let \(B_i\) be the constant supplied by that lemma.

Only positive-probability histories matter. Each history has a finite range by induction: the message range is finite, and each intermediate history permits finitely many selected cells by Lemma 8. Thus every entropy below is finite. Fresh rows remain independent of \(Z\) conditional on the past, because all past messages and revelations depend only on \(Z\), past data, and independent past randomization. The rule for \(W_i\), conditional on this enlarged history, is an admissible kernel for Lemma 7; the extra cells are analysis variables and do not change the original rule.

Let \(h_i=H(j_i\mid\Pi_i^-)\), including the average over intermediate histories. The alphabet hypothesis and Lemmas 7 and 8 give \[I(Z;W_i\mid\Pi_{i-1})\le Cd+\mathbb E\log B_{i-1}, \qquad \mathbb E\log B_i\le h_i+1.\] The selection is deterministic from \((Z,\Pi_i^-)\), so \[\begin{align*} I(Z;Q_i\mid\Pi_i^-) &=H(Q_i\mid\Pi_i^-)\\ &\le h_i+\alpha n\log2\,\mathbb Ej_i, \qquad h_i\le\log2\,(\mathbb Ej_i+1). \end{align*}\] Summing the information chain rule, using \(B_0=1\) and \(\sum_i j_i=J_t\), yields \[ I(Z;\Pi_t)\le Cdt+(\alpha n+2)\log2\,\mathbb EJ_t. \tag{16}\] The \(2\) in the depth coefficient accounts for the depth entropy at selection and for its use in the next block’s concentration factor.

For a fixed terminal history, its posterior \(\lambda\) is supported in its level-\(J_t\) cell \(Q_t\). Writing \(\mu_0(\,\cdot\mid Q_t)\) for normalized restriction to this cell gives the exact identity \[D(\lambda\|\mu_0) =nJ_t\log2+ D\bigl(\lambda\|\mu_0(\,\cdot\mid Q_t)\bigr).\] Nonnegativity and averaging imply \[ I(Z;\Pi_t)\ge n\log2\,\mathbb EJ_t. \tag{17}\] Combining (16) and (17), and using \((1-\alpha)n-2\ge n/4\) for large \(n\), proves \(\mathbb EJ_t\le Ct\). Substitution into (16) proves (5). ◻

Proof of Corollary 9. First average the success guarantee over \(s=\phi(Z)\), \(Z\sim\mu_0\). Fix the shared rule-selection randomness, if present, with cube-prior average success greater than \(3/5\); such a choice exists because the original average is at least \(2/3\). The chart has full-rank derivative because its first \(n\) coordinates are \(z\), so Lemma 2 applies. Apply Lemma 1 to these fixed rules. Now expose all remaining independent randomness and fix a realization with prior-average success at least \(3/5\). Finite transition and stopping kernels can be sampled using independent uniforms indexed by state and sample index. Output laws can likewise be sampled in advance for each terminal state and stopping index. The resulting deterministic learner has the same state bound, and its output is a function of its terminal state and stopping index.

Divide its horizon into \(t=\lceil T/k\rceil\) blocks. Pregenerate all \(k\) rows in every block, including an unused final suffix. A block message records one of the following: the continuing state; a terminal state together with the local stopping offset; or a dummy value if the learner was already inactive. Allowing offsets at the block endpoints and immediate stopping, it suffices to use \[ N\le(k+3)2^M+1. \tag{18}\] The transcript determines the global stopping index from the block index and local offset. Conditional on its past, the starting state is known, and composing the transitions gives a measurable rule of the whole exact block. Thus Theorem 5 applies. Eventually \(M\le d^2\), so (18) gives \(\log N\le Cd^2\) and hence (4) with an absolute \(C_0\).

We next lower-bound the information needed for accurate estimation. For a fixed unit vector \(v\), angular error at most \(\epsilon\) implies \(\|\phi(Z)-v\|\le\epsilon\), and hence \(\|Z-P_{\mathbb R^n}v\|\le\epsilon\). The normalized cube volume of this event is at most \[ n^{n/2}v_n\epsilon^n\le(5\epsilon)^n. \tag{19}\] Let \(p\ge3/5\) be the success probability for the fixed learner and the cube prior. Under the product of the marginal laws of \((Z,\widehat s)\), the same success event has probability \(p_0\le(5\epsilon)^n\). Relative-entropy data processing to its binary indicator gives \[\begin{align*} I(Z;\widehat s) &\ge p\log(p/p_0)+(1-p)\log((1-p)/(1-p_0))\\ &\ge p\log(1/p_0)-\log2\\ &\ge pn\log(1/(5\epsilon))-\log2. \end{align*}\] For \(\epsilon\le1/10\), \[\log(1/(5\epsilon)) \ge\left(1-\frac{\log5}{\log10}\right)\log(1/\epsilon).\] Since the output is determined by the messages, data processing and Theorem 5 imply \(t\ge c\log(1/\epsilon)\) for large \(d\).

It remains to remove the ceiling in \(t=\lceil T/k\rceil\). Return to the original randomized learner and average its every-signal success over a uniform spherical signal. The \(T>d/8\) instance of Lemma 3 applies to this same learner and prior; it grants the entire stream and therefore includes early stopping. This step does not infer cube-prior success from a sphere-average premise. Thus \(T/k\ge1\), \(\lceil T/k\rceil\le2T/k\), and \(k\ge c'd\) for large \(d\). The block lower bound gives \(T\ge c''d\log(1/\epsilon)\), as required. ◻

Proof. The score at depth zero is one. Every score at depth \(j\) is at most \[P^{-1}2^{-n(i+j)}2^{\beta j} =P^{-1}2^{-ni}2^{-(n-\beta)j},\] which tends to zero uniformly in \(z\). Hence a maximum is attained among finitely many depths. The first such depth is measurable because each score is constant on Borel cells and there are countably many score comparisons. Comparing its score with one proves the stated bound on \(J\).

Let \(E_{j,B}\subseteq B\) be the actual selection event, of \(\pi\)-mass \(p\). Comparison with the depth-zero score gives \(\pi(B)\ge2^{-\beta j}\). If a further subcell \(B'\subseteq B\) of relative depth \(m\) has positive posterior mass after selection, it meets \(E_{j,B}\). The maximizing inequality at such a point implies \(\pi(B')\le2^{-\beta m}\pi(B)\). Its new posterior mass is therefore at most \(p^{-1}\pi(B')\le e^{a'}2^{-\beta m}\); if it has zero selected mass, the same bound holds. Since \(p\le\pi(B)\), the slack is nonnegative.

For fixed \(j\), let \(p_B\) be the probabilities of its cell outcomes and \(p_j=\sum_Bp_B\). These \(B\)’s are disjoint at one grid level, so \(\sum_B\pi(B)\le1\). The log-sum inequality then gives \[\sum_Bp_B\log\frac{\pi(B)}{p_B}\le p_j\log(1/p_j).\] Summing over \(j\) proves \(\mathbb E a'\le H(J)\). Comparison of the law of \(J\) with the probability vector \((2^{-j-1})_{j\ge0}\), by nonnegativity of relative entropy, gives \(H(J)\le(1+\mathbb EJ)\log2\). These quantities are finite because \(J\) has the displayed finite bound. Finally \[\log(1/p)=\log(1/\pi(B))+a'\le\beta j\log2+a'.\] Averaging proves (22). ◻

Proof. Let \(z_c\) be the center of \(C\) and \(s_c=s(z_c)\). The radius of \(C\) is \(r/2\), so its graph image lies in \(B(s_c,r)\). For \(0<h\le r\), choose \(j\ge0\) with \(r2^{-j}\le h<2r2^{-j}\). A depth-\((i+j)\) cell meeting the first-coordinate projection of an ambient ball of radius \(h\) lies in the concentric \(n\)-ball of radius \(3r2^{-j}\). These cells have disjoint interiors and volume \((r2^{-j}/\sqrt n)^n\). The unit-ball volume estimate \(v_n\le(2\pi e/n)^{n/2}\) therefore bounds their number by \(C^n\), for an absolute \(C\), by the Gaussian-integral proof in Lemma 4. By (20), \[ \mu\{z:\|s(z)-x\|\le h\} \le C^ne^a(h/r)^\beta. \tag{25}\] After increasing \(C\), this bound also holds trivially when \(h>r\).

If \(P\) has dimension \(m\le\ell\), the projection of \(B(s_c,r)\) onto \(P\) is contained in an \(m\)-ball of radius \(r\). A maximal \(h\)-separated set in that ball has at most \((1+2r/h)^m\) points: its disjoint radius-\(h/2\) balls fit inside the concentric ball of radius \(r+h/2\). Ambient balls of radius \(2h\) about these centers cover points of \(B(s_c,r)\) at distance at most \(h\) from \(P\). Applying the ball bound and absorbing the covering constants gives, for \(C_2\) absolute, \[ \mu\{z:\operatorname{dist}(s(z),P)\le h\} \le K(h/r)^{\beta-m}\qquad(0<h\le r). \tag{26}\] The estimate also shows that \(P\) has zero \(\mu\)-mass.

Suppose \(f>0\), and put \(\theta=k/(\beta-m)\). Since \(m\le\ell=k\le n/8\), we have \(\theta\le1/3\). For \(t\ge1\), the \(\mu\)-mass within \(F\) where \((r/\operatorname{dist}(s(z),P))^k>t\) is at most \(\min\{f,Kt^{-1/\theta}\}\). Integrating this tail and splitting at \(t=(K/f)^\theta\ge1\) gives \[\int_F\left(\frac r{\operatorname{dist}(s(z),P)}\right)^k\,d\mu \le\frac{K^\theta f^{1-\theta}}{1-\theta} \le2K^{1/3}f^{2/3}.\] Here \(K\ge1\), \(0<f\le1\), and \(\theta\le1/3\) justify the last inequality. This proves (23).

Let \(\nu_A\) be the image of \(\mu|_F\) under \(z\mapsto As(z)\). If \(F\) is measurable only in the completion, replace it by a Borel representative modulo \(\mu\), which leaves the restricted measure unchanged. For \(h>0\), write \(v_k\) for the volume of the unit ball in \(\mathbb R^k\) and define its ball-average density \[v_{F,h}(A,b)=\frac{\nu_A(B(b,h))}{v_kh^k}.\] Expand the \(\ell\)th power using \(z_1,\ldots,z_\ell\) integrated against \((\mu|_F)^{\otimes\ell}\), and put \(s_j=s(z_j)\). The intersection of the balls \(B(As_j,h)\) has volume at most \(v_kh^k\), and is empty unless \(\|A(s_j-s_1)\|\le2h\) for all \(2\le j\le\ell\). For a fixed tuple, condition successively on the preceding difference images. Orthogonal decomposition of each Gaussian row shows that the conditional image at step \(j\) has an independent centered residual with covariance \(\operatorname{dist}(s_j,P_j)^2I_k\), where \[P_j=s_1+\operatorname{span}\{s_t-s_1:2\le t<j\}.\] The subspace bound makes all zero-distance tuples null. On every remaining tuple, the conditional probability of a radius-\(2h\) ball is at most \[v_k(2h)^k(2\pi)^{-k/2} \operatorname{dist}(s_j,P_j)^{-k}.\] Multiplying these bounds, dividing by \((v_kh^k)^\ell\), and including the intersection volume cancels every \(h\) and \(v_k\) factor. Integrating \(z_\ell,\ldots,z_2\) in this order and applying (23) at each step leaves the factor \(\mu(F)=f\) for \(z_1\). Absorbing the numerical Gaussian and radius factors into \(C_3^k\) proves \[\int v_{F,h}^\ell\,d\gamma_{k,d}\,db \le f[C_3^kr^{-k}K^{1/3}f^{2/3}]^{\ell-1}\] uniformly for \(h>0\).

For every continuous compactly supported test function on the matrix and label space, integrals against these ball averages converge as \(h\downarrow0\) to its integral against the exact joint image measure. This follows by averaging translations of the test function over a shrinking ball and then using bounded convergence. Hölder’s inequality bounds the limiting functional on \(L^{\ell/(\ell-1)}(\gamma_{k,d}(dA)\,db)\) by the \(\ell\)th root of the last display. Continuous compactly supported tests are dense for this locally finite reference measure. Extension and \(L^p\) duality therefore give a jointly measurable representing density with (24); equality on these tests identifies it with the exact image measure and makes it nonnegative. Finally, testing the joint identity on a countable algebra of rational label boxes and arbitrary measurable matrix sets identifies the conditional density for almost every \(A\). The averaging operation has only proved a statement about exact labels; it is absent from the observation rule. ◻

Proof. Write \(q_u(A,b)\) for the kernel probabilities, so that \(q_u\ge0\) and \(\sum_uq_u=1\). With the center \(s_c\) used above, define \[E=\{\|As(Z)-As_c\|\le3r\sqrt k\},\qquad V=v_k(3r\sqrt k)^k\le(3\sqrt{2\pi e}\,r)^k.\] For each fixed \(Z\), the vector \(A(s(Z)-s_c)\) is Gaussian with covariance at most \(r^2I_k\). Hence \[\Pr(E^c\mid Z)\le e^{-9k/4}2^{k/2}\le e^{-k},\] by Markov’s inequality and \(\mathbb E\exp(\|G\|^2/4)=2^{k/2}\) for standard Gaussian \(G\in\mathbb R^k\). Define comparison probabilities \[\lambda_u=\mathbb E_A\frac1V \int_{B(As_c,3r\sqrt k)}q_u(A,b)\,db, \qquad \sum_u\lambda_u=1.\] These probabilities use an auxiliary label uniform on the displayed ball, independently conditional on \(A\).

For a measurable \(F\) of mass \(f\), apply Hölder to its exact joint density \(v_F\) and the function \(q_u(A,b)\mathbf1_{\{\|b-As_c\|\le3r\sqrt k\}}\). Since \(0\le q_u\le1\), its conjugate norm is at most \((V\lambda_u)^{1-1/\ell}\). Lemma 11 therefore gives \[\Pr(Z\in F,U=u,E) \le (V\lambda_u)^{1-1/\ell} \{f[C_3^kr^{-k}K^{1/3}f^{2/3}]^{\ell-1}\}^{1/\ell}.\] The \(r\) powers cancel. The exact exponent of \(f\) is \[\frac{1+(2/3)(\ell-1)}{\ell} =\frac23+\frac1{3\ell}.\] Because \(f\le1\), it may be weakened to \(2/3\). The exponent of \(K\) is \((\ell-1)/(3\ell)\le1/3\). Thus, for an absolute \(C_4\ge1\), \[ \Pr(Z\in F,U=u,E) \le L_0\lambda_u^{1-1/\ell}f^{2/3}, \qquad L_0=C_4^ne^{a/3}. \tag{28}\]

Put \(p_u=\Pr(U=u,E)\). For \(p_u>0\), let \(\nu_u=\mathcal L(Z\mid U=u,E)\) and \(f_u=d\nu_u/d\mu\). Applying (28) with \(F=C\) shows that \[D_u^*=\frac{L_0\lambda_u^{1-1/\ell}}{p_u}\ge1;\] in particular \(\lambda_u>0\). Since \(\mu\{f_u>e^t\}\le e^{-t}\), a second application to that set gives \[\nu_u\{\log f_u>t\}\le\min\{1,D_u^*e^{-2t/3}\} \qquad(t\ge0).\] Integrating this upper bound gives \(\tfrac32(\log D_u^*+1)\). Relative entropy is no greater than the expected positive part of the log density, so \[ D(\nu_u\Vert\mu)\le\frac32(\log D_u^*+1). \tag{29}\] This calculation is why the \(a/3\) in \(L_0\) becomes \(a/2\).

Let \(p_E=\sum_up_u\). The log-sum inequality and the entropy bound for at most \(W\) letters give \[\sum_up_u\log\frac{\lambda_u}{p_u}\le p_E\log(1/p_E), \qquad \sum_up_u\log(1/p_u)\le p_E\log(1/p_E)+p_E\log W.\] The identity \[\log\frac{\lambda_u^{1-1/\ell}}{p_u} =\left(1-\frac1\ell\right)\log\frac{\lambda_u}{p_u} +\frac1\ell\log(1/p_u)\] therefore bounds the weighted sum of these log ratios by \(1+(\log W)/\ell\). All zero terms are omitted. For the outcomes \((U,E^c)\), their weighted divergences to \(\mu\) sum to at most \[p_{E^c}\log(1/p_{E^c})+p_{E^c}\log W.\] Indeed, conditioning first on \(E^c\) multiplies the density by at most \(1/p_{E^c}\), and revealing \(U\) afterwards adds at most its conditional entropy. This bound is zero when \(p_{E^c}=0\).

The mutual information of the finite pair \((U,\mathbf1_E)\) is the sum of these good and bad weighted divergences. Combining the last bounds with (29) gives \[I(Z;U)\le I(Z;U,\mathbf1_E) \le Cn+\frac a2+C\frac{\log W}{\ell} +e^{-k}\log W+C.\] Here \((\log W)/\ell=O(d)\) and \(e^{-k}\log W=O(1)\) in the stated width range. Absorbing the absolute terms proves (27). ◻

Proof. First fix a realization of a data-independent shared seed, if present. The graph derivative contains the identity in its first \(n\) rows, so Lemma 2 applies to the cube prior. For this fixed seed, Lemma 1 supplies everywhere-defined Borel rules with the same prior law. We do this separately for each seed value under consideration; no jointly chosen family of Borel versions is needed. Use the initial finite state as \(\mathcal H_0\). By the joint independence of the shared seed and initial state from the signal and all rows in Section 2, conditional on the fixed seed this state has zero information about \(Z\), and the future rows remain independent of both. At an active block end record the continuing state or the terminal state and its stopping position within the block, including immediate stopping. Given the preceding history there are at most \((k+2)2^M\) such destinations. After a stop, later messages may be dummy messages because the earlier history already records the terminal state and index. Padding the last block by ignored Gaussian rows is harmless. This count depends only on the block length, not the total horizon.

Start at depth \(i_0=0\) with slack \(a_0=0\). At step \(t\), apply Lemma 12 to its outgoing message \(U_t\). Then apply Lemma 10 to the posterior given \(\mathcal H_t^-=(\mathcal H_{t-1},U_t)\), and append its selection \((J_t,B_t)\) to form \(\mathcal H_t\). The new depth is \(i_t=i_{t-1}+J_t\), and its slack is \(a_t\). The added labels use only \(Z\) and the history already observed. Future Gaussian rows remain independent of that joint collection. Given the starting state, the message is a kernel of the fresh block data, so the block lemma applies on every positive-probability history.

Every such history of probability \(P\) has posterior at most \(\tau/P\). All entropies used below are finite. Indeed a block message has a finite alphabet, and the depth bound in Lemma 10 is integrable after averaging over the preceding history because it is bounded by a constant times \(\log(1/P)\). The label-charge inequality then preserves finite history entropy by induction.

The information chain rule, followed by (21) and (22), gives \[\begin{split} I(Z;\mathcal H_N) &\le\sum_{t=1}^N \left(C_0d+\tfrac12\mathbb E a_{t-1} +H(J_t,B_t\mid\mathcal H_t^-)\right)\\ &\le C_5dN+ (\beta+\tfrac32)(\log2)\sum_{t=1}^N\mathbb EJ_t \end{split}\] for an absolute \(C_5\). On the other hand the final posterior is supported on a depth-\(i_N\) cell, of prior mass \(2^{-ni_N}\). Relative entropy to \(\tau\) is therefore at least \(ni_N\log2\), since the conditional divergence to the uniform law of that cell is nonnegative. Averaging yields \[I(Z;\mathcal H_N)\ge n(\log2)\mathbb Ei_N =n(\log2)\sum_{t=1}^N\mathbb EJ_t.\] The ratio \((\beta+3/2)/n=1/2+3/(2n)\) is bounded away from one for large \(n\). Substituting the last bound into the preceding upper bound and moving that term to the left proves \(I(Z;\mathcal H_N)\le C_6dN\).

The history records the terminal state and stopping index. Conditional on those data, the output uses only fresh randomness, so data processing gives \(I(Z;\widehat S)\le I(Z;\mathcal H_N)\). For each fixed seed, Lemma 1 preserved the original conditional prior law, so the output-information bound just proved holds for that original law. Integrating the original measurable conditional information values over a shared seed \(R\), whose law is independent of \(Z\), gives \[I(Z;\widehat S)\le I(Z;\widehat S,R) =\mathbb E_R I(Z;\widehat S\mid R)\le C_6dN.\] When \(T=0\), the same argument has no blocks and the output is independent of \(Z\). This proves the stated zero upper bound as well. ◻

Proof. At an attempt, consider the current conditional law in its current cell. A strict descendant \(E\) of relative depth \(h\ge1\) is heavy if its current mass \(m_E\) exceeds \(2^{-\alpha nh}\). Select the heavy descendants with no heavy strict ancestor of positive relative depth. Every heavy cell has such a first heavy ancestor, because its chain of ancestors back to the current cell is finite. The selected cells are a countable disjoint family.

If \(W\) is in one of these cells, reveal which cell, condition on it, replace the current cell by it, and begin another attempt. Otherwise reveal that \(W\) is in the complement, whose current probability is \(q\), condition on that complement, and keep the current cell. Stop if \(q\ge1/2\); if \(0<q<1/2\), begin another attempt. Zero-probability branches are omitted. These operations are Borel and the label records their finite sequence if the procedure stops.

At a stop, a descendant that was heavy immediately before the last complement decision lies in a selected cell, so it has zero posterior mass. Every other descendant of depth \(h\) had mass at most \(2^{-\alpha nh}\), and conditioning on a complement of probability at least \(1/2\) increases this by at most two. The resulting law is therefore regular.

It remains to prove that a stop occurs and that its cost satisfies (34). Let \(f\) be the density of the current law relative to the uniform probability on the current cell. On a heavy transition of depth \(h\), its value at the sampled point changes to \[f(W)\frac{2^{-nh}}{m_E}.\] Its logarithm therefore decreases by at least \((1-\alpha)nh\log2\). On a complement transition it increases by \(\log(1/q)\). These are exact density updates on every positive-probability branch, with all previous complement exclusions retained in the conditional law.

Truncate after \(N\ge1\) attempts, freezing a path once it has stopped. Let \(H_N\) be accumulated heavy depth, \(J_N\) the sum of complement logarithmic increases, and \(A_N\) the number of attempts actually made. If \(f_N\) is the resulting conditional density, the pathwise updates give \[ \log f_N(W)+(1-\alpha)n(\log2)H_N \le\log f_0(W)+J_N. \tag{35}\] For an active attempt the conditional expected complement increase, counted as zero on a heavy branch, is \(q\log(1/q)\le1/e\). Thus \[\mathbb EJ_N\le \mathbb EA_N/e\le N/e.\]

We justify taking expectations of the logarithms before using (35). For any density \(f\) relative to a probability measure \(\lambda\), \[\int_{\{f<1\}} f\log(1/f)\,d\lambda\le1/e,\] because \(x\log(1/x)\le1/e\) for \(0<x<1\). This bounds the expected negative log part at the sampled point, conditionally on each positive-probability history. Finite \(K_0\) then makes the positive part of \(\log f_0(W)\) integrable. The path inequality bounds the positive part of \(\log f_N(W)\) by \((\log f_0(W))^++J_N\). Consequently \(\mathbb E\log f_N(W)\) is well defined and is the expected conditional relative entropy, hence is nonnegative. Taking expectations in (35) first shows \(\mathbb EH_N<\infty\).

An attempt after the first follows a heavy transition or a continuing complement. The number of heavy transitions is at most \(H_N\), because each adds at least one unit of depth. At each active attempt, the conditional probability of a continuing complement is at most \(1/2\). Counting such predecessors and taking expectations gives \[ \mathbb EA_N\le1+\mathbb EH_N+\tfrac12\mathbb EA_N, \qquad \mathbb EA_N\le2(1+\mathbb EH_N). \tag{36}\] Substituting \(\mathbb EJ_N\le\mathbb EA_N/e\) into the expected path inequality now yields \[ \mathbb E\log f_N(W) +\bigl((1-\alpha)n\log2-2/e\bigr)\mathbb EH_N \le K_0+2/e. \tag{37}\] For sufficiently large \(n\), the coefficient is at least \(bn=(1-\alpha)n(\log2)/2\). Hence the expectations of \(H_N\) and, by (36), \(A_N\), are bounded uniformly in \(N\).

Both sequences increase on every path. Monotone convergence gives finite expectations for their limits \(H,A_*\), and preserves \(\mathbb EA_*\le2(1+\mathbb EH)\). A path that never stops has \(A_N\to\infty\), so nontermination has probability zero. The possible terminating histories form a countable set of finite sequences.

The limiting complement sum \(J\) also satisfies, by monotone convergence, \[\mathbb EJ\le\mathbb EA_*/e \le(2/e)(1+\mathbb EH)<\infty.\] At termination the positive log part of the final density is integrable by the path inequality, and its negative log part is integrable by the conditional bound above. We may therefore take expectations directly in the terminating path inequality. This gives \[\mathbb E D(P'\Vert\mu_{C'}) +(1-\alpha)n(\log2)\mathbb EH \le K_0+(2/e)(1+\mathbb EH),\] which implies (34). In particular, no passage of a signed logarithm through a limit is being used. ◻

Proof. The cell diameter is \(2^{-j}\); the \(2\)-Lipschitz property gives the stated support radius. For \(r\le R/2\), choose \(h\ge1\) with \(r\le R2^{-h}<2r\). The depth-\((j+h)\) cells have side between \(r/(2\sqrt n)\) and \(r/\sqrt n\), and diameter at most \(r\). A ball test for the graph image restricts \(w\) to a ball of radius \(r\) in its first \(n\) coordinates. Every cell meeting that ball lies in the concentric ball of radius \(2r\). Comparing disjoint cell volumes and using the unit-ball estimate from Lemma 4 gives at most \[v_n(2r)^n(2\sqrt n/r)^n\le(4\sqrt{2\pi e})^n\] such cells. Each has \(P\)-mass at most \(2\,2^{-\alpha nh}\). Since \(2^{-h}<2r/R\) and \(\alpha n=(d-1)/2\ge d/3=\beta d\), all factors are bounded by \(C_0^d(r/R)^{\beta d}\) for an absolute \(C_0\). For \(R/2<r\le R\), enlarge \(C_0\) and use total mass one. ◻

Proof. Let \(F\) be an affine subspace of dimension \(m\le p-2\). For \(0<r\le R\), a maximal \(r\)-separated set in the projection of \(B(z,R)\) onto \(F\) has at most \((5R/r)^m\) points, by packing disjoint radius-\(r/2\) balls. Ambient balls of radius \(2r\) at these centers cover the part of \(B(z,R)\) at distance at most \(r\) from \(F\). If \(2r>R\), the trivial mass bound can replace the local bound at that radius, whose right side would already be at least one. Since \(\beta d-m\ge\gamma d\), absorbing the covering constants gives \[ \nu\{s:\operatorname{dist}(s,F)\le r\} \le\min\{1,e^{(a+C_1)d}(r/R)^{\gamma d}\}. \tag{40}\] In particular \(F\) has zero \(\nu\)-mass. Set \(r_0=R e^{-(a+C_1)/\gamma}\). Layer-cake integration, using total mass at most one above the cutoff \(r_0\), gives \[ \begin{split} \int\operatorname{dist}(s,F)^{-k}\,d\nu(s) &\le r_0^{-k} +k r_0^{-\gamma d}\int_0^{r_0}r^{\gamma d-k-1}\,dr\\ &=r_0^{-k}\left(1+\frac{k}{\gamma d-k}\right) \le2R^{-k}e^{(a+C_1)k/\gamma}=:B. \end{split} \tag{41}\] The last inequality uses \(k\le\gamma d/2\).

Choose a continuous nonnegative probability density \(\varphi_\eta\) supported in \(B(0,\eta)\subseteq\mathbb R^k\), and define \[g_\eta(A,y)=\int\varphi_\eta(y-As)\,d\nu(s).\] For \(\nu^{\otimes p}\)-almost every tuple \(s_1,\ldots,s_p\), the differences \(s_i-s_1\), \(2\le i\le p\), are linearly independent: at the \(i\)th step, the preceding affine span has dimension at most \(i-2\le p-2\), so it is null by (40). For such a tuple put \(D=[s_2-s_1,\ldots,s_p-s_1]\). The joint Gaussian vector of its images under \(A\) has density at most \[(2\pi)^{-k(p-1)/2}\det(D^{\mathsf T}D)^{-k/2} \le\prod_{i=2}^p \operatorname{dist}(s_i,\operatorname{aff}(s_1,\ldots,s_{i-1}))^{-k}.\] The determinant factorization is Gram–Schmidt.

Expand \(g_\eta^p\), shift the label integration variable by \(As_1\), and integrate over the Gaussian difference images. Bounding their density by the displayed supremum leaves a product of \(p\) probability kernels. Its integral over the \(p-1\) difference variables and then the shifted label variable is one. Tonelli’s theorem and successive integration of \(s_p,\ldots,s_2\), using (41), therefore give \[\int g_\eta^p\,d\rho\,dy\le B^{p-1};\] the last variable contributes \(\nu(\mathbb R^d)\le1\).

For a continuous compactly supported test function \(v(A,y)\), integration against \(g_\eta\) converges to \(\int v(A,As)\,d\rho(A)d\nu(s)\) as \(\eta\downarrow0\). Shrinking support and bounded convergence prove this for the finite measure \(\nu\). Hölder bounds the limiting functional on \(L^{p/(p-1)}(\rho(dA)\,dy)\) by \(B^{(p-1)/p}\). Density of continuous compactly supported tests and \(L^p\) duality give a representing density with that norm. Equality on those tests identifies it with the exact image measure, so a nonnegative version may be used. This proves (39). The auxiliary kernels have been removed before any message is formed. ◻

Proof. For each positive-probability letter let \(p_u=\Pr(U=u)\) and \(\ell_u(w)=\Pr(U=u\mid W=w)\). Its posterior density relative to \(P\) is \(\ell_u/p_u\). Set \[B_u=\{w:\ell_u(w)/p_u>e^d\},\qquad \lambda=e^{-d}.\] Since this density integrates to one, \(P(B_u)\le\lambda\). Outside \(W\in B_U\), the log posterior density is at most \(d\). We will show that \(\Pr(W\in B_U)\) is exponentially small in \(d\), and then bound its contribution using the finite alphabet.

Use \(z,R\) from Lemma 16. The exact joint law of \((A,Y)\) has a density \(D(A,y)\) by Lemma 17 with \(a=0\). The graph image of \(\lambda^{-1}P|_{B_u}\) has mass at most one and satisfies the ball hypothesis with multiplier \(e^d\), namely with \(a=1\). Let \(g_u(A,y)\) be its exact projection density from Lemma 17. Under the original experiment, \[b_u(A,Y):=\Pr(W\in B_u\mid A,Y) =\frac{\lambda g_u(A,Y)}{D(A,Y)}\] almost surely. This is the Radon–Nikodym ratio of the restricted joint measure to the original one; points where \(D=0\) have zero original probability.

To control this ratio, choose an absolute \(C_2>2\sqrt{2\pi e}\) and define \[G=\{D(A,Y)\ge(C_2R)^{-k}\}.\] For every fixed \(s\) in the support, \(A(s-z)\) is centered Gaussian with covariance at most \(R^2I_k\). Markov’s inequality with exponential parameter \(1/4\) gives \[\Pr\{\|Y-Az\|>2\sqrt kR\}\le e^{-k}2^{k/2}.\] The label ball of radius \(2\sqrt kR\) has volume at most \((2\sqrt{2\pi e}R)^k\). The probability of points inside it where \(D<(C_2R)^{-k}\), after integrating over \(A\), is at most \((2\sqrt{2\pi e}/C_2)^k\). Thus \[ \Pr(G^c)\le2e^{-c_2k} \tag{43}\] for some absolute \(c_2>0\).

Let \(p=\lfloor\beta d/2\rfloor\). On \(G\), the density denominator is bounded below, so \[ \begin{split} \mathbb E[\mathbf1_G b_u(A,Y)^p] &\le \lambda^p(C_2R)^{k(p-1)} \int g_u(A,y)^p\,d\rho(A)\,dy\\ &\le \exp\{-dp+C_3k(p-1)\}, \end{split} \tag{44}\] where \[C_3=\log C_2+(1+C_1)/\gamma+\log2\] is valid because \(k\ge1\). Choose the fixed \(c_*>0\) so that \[c_*\le\gamma/2,\qquad C_3c_*\le1/4.\] Then the projection lemma applies and the last moment is at most \(e^{-3dp/4}\) for all sufficiently large \(d\).

Given \((A,Y)\), the conditional independence assumption lets us average the choice of \(U\) separately from the event \(W\in B_u\). Consequently \[\Pr(W\in B_U,G)\le\mathbb E[\mathbf1_G\max_u b_u(A,Y)].\] The \(p\)th power of the maximum is at most the sum of the \(p\)th powers. Since \(\log m_d\le dp/4\) eventually, Hölder and (44) bound this probability by \(e^{-d/2}\). Also \(k\ge c_*d/2\) eventually, so (43) yields \[q_0:=\Pr(W\in B_U)\le e^{-c_3d}\] after decreasing an absolute \(c_3>0\) and increasing the dimension threshold.

For \(q_u=\Pr(U=u,W\in B_u)\le p_u\), the contribution of the event \(W\in B_U\) to \(\mathbb E\log(\ell_U(W)/p_U)\) is at most \[\sum_uq_u\log(1/p_u) \le\sum_uq_u\log(1/q_u) \le q_0\log(m_d/q_0).\] The last bound is the entropy bound for at most \(m_d\) letters after normalization by \(q_0\); its value is zero if \(q_0=0\). The exponential bound on \(q_0\) and \(\log m_d=o(d^2)\) make this \(o(1)\). Outside the event, the log posterior density is at most \(d\). Hence \(I(W;U)\le d+o(1)\le2d\), as claimed. ◻

Proof. At a node cell \(C\), use the original law \(\mu\) conditioned on \(C\). Select all inclusion-maximal strict dyadic descendants \(D\) whose conditional mass exceeds \(2^{-n\ell/2}\), where \(\ell\) is depth relative to \(C\). They are disjoint: two dyadic cells are disjoint or nested, and nesting would contradict maximality. A point in a selected cell moves to that cell. Every other point stops in the remainder of the current cell. Repeat at the selected cells. The label records the terminal node and its remainder.

Let \(K=\|d\mu/d\tau_A\|_\infty<\infty\); necessarily \(K\ge1\). Along a nontrivial path reaching relative depth \(j\), the product of the selected conditional masses exceeds \(2^{-nj/2}\). No complement decision occurs before stopping, so reaching the path cell is exactly membership in it. The same product is its original \(\mu\)-mass, which is at most \(K2^{-nj}\). Hence \[j<\frac{2\log K}{n\log2}.\] This uniformly bounds every nontrivial path depth and leaves finitely many grid cells. At an individual node, its bounded conditional density likewise rules out heavy descendants at unbounded depth, so each selected inclusion-maximal descendant exists. The construction is therefore a finite tree and defines a finite partition.

Let \(q_i\) be the conditional probability of the terminal remainder at its node, omitting zero-probability remainders. A strict descendant that exceeded its threshold before the remainder decision is contained in a selected cell and has zero remainder mass. Every other descendant has its conditional mass increased by at most \(q_i^{-1}\). This proves (50); the case \(\ell=0\) is immediate. The product of masses on the path, multiplied by \(q_i\), is \(p_i\), so its lower bound proves \(-\log p_i\le\tfrac12n(\log2)j_i+Q_i\).

For the expected remainder cost, a node reached with probability \(r\) and having remainder probability \(q\) contributes \(rq\log(1/q)\) to \(\mathbb E_iQ_i\). This is at most \(r\), since \(q\log(1/q)\le1\), with value zero at \(q=0\). Summing over the finite tree bounds \(\mathbb E_iQ_i\) by the expected number of visited nodes. Each move increases depth by at least one, so this number is at most \(1+\mathbb E_i j_i\).

On the part with label \(i\), the density relative to \(\tau_{A_i}\) is the original density relative to \(\tau_A\), multiplied by \(p_i^{-1}2^{-nj_i}\). Taking its logarithm, integrating on that part, and averaging over \(i\) proves (52). All terms are finite because the partition is finite and each conditional density is bounded. ◻

Proof. We first use the dyadic mass bound to control inverse Gram determinants of independent centered signal vectors. These determinants bound the moment of a smoothed projection density. We then remove the smoothing and compare the exact density with the Gaussian reference.

For every \(y\in\mathbb R^d\) and \(0<r\le1\), \[ \Pr_\mu\{\|s(z)-y\|\le rR\}\le C^ne^{Q_*}r^{n/2}. \tag{54}\] Indeed, choose \(\ell\ge0\) with \(2^{-\ell-1}<r\le2^{-\ell}\). A relative-depth-\(\ell\) cell meeting the projection of this ball onto the first \(n\) coordinates lies in the concentric ball of radius \(2\,2^{-\ell}R\). Its side is \(2^{-\ell}R/\sqrt n\). The unit-ball volume estimate in Lemma 4 therefore bounds the number of such disjoint cells by \(C^n\). Multiply by their mass bound \(e^{Q_*}2^{-n\ell/2}\) and use \(2^{-\ell}<2r\).

If \(U\subseteq\mathbb R^d\) is a linear subspace of dimension \(m\le n/8\), a maximal \(rR\)-separated set in its radius-\(R\) ball has at most \((1+2/r)^m\) points. Its radius-\(rR\) balls cover that ball, by maximality. Because \(\|s-s_0\|\le R\), ambient balls of radius \(2rR\) about the translated centers cover the event \(\operatorname{dist}(s-s_0,U)\le rR\). Using (54), and the trivial mass bound for \(r>1/2\), gives \[ \Pr_\mu\{\operatorname{dist}(s-s_0,U)\le rR\} \le C^ne^{Q_*}r^{n/2-m}\qquad(0<r\le1). \tag{55}\]

For \(m\le p-1\), put \(a=n/2-m\ge3n/8\) and \(D_U=R^{-1}\operatorname{dist}(s-s_0,U)\). Then \(0<D_U\le1\) almost surely. Let \(\mathcal A=C^ne^{Q_*}\ge1\). Since \(J\le a/2\), layer-cake integration of \(\Pr(D_U<r)\le\min\{1,\mathcal A r^a\}\), split at \(\mathcal A^{-1/a}\), gives \[ \begin{split} \mathbb E_\mu D_U^{-J} &=1+J\int_0^1r^{-J-1}\Pr(D_U<r)\,dr\\ &\le\frac a{a-J}\mathcal A^{J/a} \le2\mathcal A^{J/a}\le(Ce^{CQ_*/n})^J. \end{split} \tag{56}\] For independent \(z_1,\ldots,z_p\sim\mu\), put \(s_i=s(z_i)\) and let \(G\) be the Gram matrix of \(e_i=s_i-s_0\). Conditional on its predecessors, each \(e_i\) has positive distance from their span almost surely by (55). Gram–Schmidt and successive conditioning in (56) yield \[ \mathbb E(\det G)^{-J/2} \le(Ce^{CQ_*/n}/R)^{Jp}. \tag{57}\]

Add an independent uniform vector in \([-t,t]^J\), \(t>0\), to the exact label \(b\). Its joint density is \[f_t(X',b)=(2t)^{-J}\mathbb E_\mu \mathbf1_{\{\|X'(s-s_0)-b\|_\infty\le t\}}.\] Expand its integer \(p\)th power using independent \(e_1,\ldots,e_p\). For fixed \(b\), Tonelli’s theorem and independence of the \(J\) rows give \[\int f_t(X',b)^p\,dP_{X'} =(2t)^{-Jp}\mathbb E_{e_1,\ldots,e_p} \prod_{j=1}^J \Pr_x\{|\langle x,e_i\rangle-b_j|\le t\text{ for all }i\le p\}.\] For almost every tuple the inner-product vector for one row is Gaussian with nonsingular covariance \(G\). Its density is bounded by \((2\pi)^{-p/2}(\det G)^{-1/2}\). Each box probability is at most \((2t)^p\) times this supremum. The \(2t\) powers cancel, and (57) gives, uniformly in \(t,b\), \[\int f_t(X',b)^p\,dP_{X'} \le(Ce^{CQ_*/n}/R)^{Jp}.\] Integrating on \(\Omega\) therefore bounds the local \(p\)th power integral by \(|\Omega|(Ce^{CQ_*/n}/R)^{Jp}\).

For a continuous compactly supported test function on the product of the matrix space and \(\Omega\), its integral against the jittered law converges to its integral against the exact law as \(t\downarrow0\). Extend the test by zero outside a compact subset of \(\Omega\) and use bounded convergence. Hölder bounds these limiting integrals by the local \(L^p\) bound times the test’s \(L^{p/(p-1)}(dP_{X'}\,db)\) norm. Density of such tests and \(L^p\) duality give a density for the exact law on this open region, with \[ \int_\Omega\int f(X',b)^p\,dP_{X'}\,db \le|\Omega|(Ce^{CQ_*/n}/R)^{Jp}. \tag{58}\] Equality on the tests identifies the represented measure with the restricted exact law. This asserts a density on \(\Omega\), which is the only region used below.

On \(\Omega\), the Gaussian reference satisfies \(h_R(b)\ge(CR)^{-J}\). Also the ball-volume estimate gives \(|\Omega|\le(CR)^J\). In the integral of \(f^ph_R^{1-p}\), the powers of \(R\) from (58) are \[R^{-Jp}R^JR^{J(p-1)}=1.\] Taking the \(p\)th root gives (53). The auxiliary jitter has been removed before the exact observation rule is applied. ◻

Proof. Put \(R=2^{-h}\) and \(s_0=s(\operatorname{center}A)\). Write the kernel probabilities as \(g_u(X,Y)\in[0,1]\), with \(\sum_ug_u(X,Y)=1\) for every matrix-label pair \((X,Y)\). Define \[\mathcal G=\{\|X(s-s_0)\|\le2\sqrt k R\},\qquad K_u(s)=\mathbb E_X[\mathbf1_{\mathcal G}g_u(X,Xs)],\] and define a comparison probability vector by \[\rho_u=\mathbb E_{X,Z}g_u(X,Xs_0+RZ), \qquad Z\sim N(0,I_k)\text{ independently}.\] In \(\mathbb E_\mu K_u(s)^2\), use two independent block matrices at the same signal \(s\). Their stack has \(J=2k\) rows. When both blocks satisfy \(\mathcal G\), the stacked residual norm is at most \(2\sqrt J R<3\sqrt J R\), inside \(\Omega\). Apply Lemma 20 and Hölder’s inequality to this exact joint law. Under the Gaussian reference, the two matrices and the two residual vectors are independent between blocks. The product of the two \(g_u\)’s lies in \([0,1]\) and has reference expectation \(\rho_u^2\). Dropping the good indicators in its conjugate norm gives \[ \mathbb E_\mu K_u(s)^2 \le C^J e^{C(J/n)Q_*}\rho_u^{2(1-1/p)}. \tag{60}\] Thus \(\rho_u=0\) implies \(K_u=0\) almost surely.

For every fixed \(s\), the probability of \(\mathcal G^c\) is at most \[e^{-k}2^{k/2}=e^{-ck}=:\delta<1\] for an absolute \(c>0\), by the Gaussian exponential moment at \(1/4\). Put \(g_0(s)=\sum_uK_u(s)\ge1-\delta\) and \(P_g=\mathbb E_\mu g_0(s)\). Including the good indicator with \(u\) can only increase information. The indicator costs at most \(\log2\), and the weighted bad conditional information costs at most \(\delta\log W\).

The weighted good conditional information is at most \[ \mathbb E_\mu\sum_uK_u(s) \log\frac{K_u(s)}{g_0(s)\rho_u}. \tag{61}\] Indeed, replacing the actual conditional marginal \(\Pr(u\mid\mathcal G)\) by \(\rho\) adds \(P_gD(\Pr(u\mid\mathcal G)\Vert\rho)\ge0\). Zero states cause no issue by (60). The contribution of \(-\log g_0(s)\) is at most \(\log(1/(1-\delta))\). For the remaining term, Jensen’s inequality under the probability measure with weights \(\mu(ds)K_u(s)/P_g\) gives \[\begin{split} \mathbb E_\mu\sum_uK_u(s)\log\frac{K_u(s)}{\rho_u} &\le P_g\log\left(\frac1{P_g} \sum_{u:\rho_u>0}\frac{\mathbb E_\mu K_u(s)^2}{\rho_u}\right)\\ &\le P_g\log\left( \frac{C^J e^{C(J/n)Q_*}W^{2/p}}{P_g}\right). \end{split}\] The last inequality uses (60) and \(\sum_u\rho_u^{1-2/p}\le W^{2/p}\), by concavity for \(p\ge2\). All sums are finite. Combining the terms gives \[I_\mu(z;u)\le Cn+CQ_*+\frac2p\log W+e^{-ck}\log W.\] Since \(k,p\) are proportional to \(n\) and \(\log W\le n^2\), the last two terms are \(O(n)\). This proves the lemma. ◻

Proof. Before each block, apply Lemma 19 to the law conditional on the analysis transcript, and record its label. Also record the outgoing boundary state after the block. Initially the cell is the whole cube and the law is \(\tau\). Every positive-probability posterior has bounded density relative to its current cell’s uniform law: splitting preserves this property, and conditioning on a state multiplies the density by a likelihood in \([0,1]\) and divides by a positive state probability. Every split is finite, so each stage has finitely many histories. Future Gaussian rows remain independent of the signal and these histories, which depend only on the signal and past blocks. The block from a known entering state is a measurable kernel of its exact data. Lemma 21 therefore applies in each selected component.

For a current cell of depth \(h\) and conditional law \(\mu\), define \[ \Phi=\tfrac14n(\log2)h+D(\mu\Vert\tau_A). \tag{62}\] It is nonnegative. By (52), the expected change under a split is \[H(i)-\tfrac34n(\log2)\mathbb E_i j_i \le-\tfrac14n(\log2)\mathbb E_i j_i+\mathbb E_iQ_i.\] Within component \(i\), conditioning on its outgoing state keeps the cell fixed and increases the expected relative entropy by exactly \(I_{\mu_i}(z;u)\). This follows by multiplying the density by \(\Pr(u\mid z,i)/\Pr(u\mid i)\), taking logarithms, and averaging. The block lemma bounds this increase by \(Cn+CQ_i\). Thus the combined conditional drift is at most \[ \begin{split} Cn-\tfrac14n(\log2)\mathbb E_i j_i+(C+1)\mathbb E_iQ_i &\le Cn+(C+1) +(C+1-\tfrac14n\log2)\mathbb E_i j_i\\ &\le C'n \end{split} \tag{63}\] for large \(n\), using \(\mathbb E_iQ_i\le1+\mathbb E_i j_i\). Only this expected bound on \(Q_i\) is used.

The initial potential is zero, so after \(B\) blocks \(\mathbb E\Phi\le C'nB\). For the final transcript \(\mathcal H\), its posterior in a depth-\(h\) cell satisfies \[D(P(z\mid\mathcal H)\Vert\tau) =n(\log2)h+D(P(z\mid\mathcal H)\Vert\tau_A) \le4\Phi.\] Averaging over the finite history gives \[ I(z;\mathcal H)\le4C'nB. \tag{64}\] ◻

Proof. Choose a shared-seed value with conditional cube-prior success greater than \(3/5\). The joint experiment in Section 2 makes this conditioning meaningful, and the conditional initial-state law remains independent of the signal and rows. The derivative of the chart has the identity in its first \(p\) rows, so Lemma 2 proves absolute continuity of its one-pair law. Lemma 1 therefore provides everywhere Borel finite kernels preserving this fixed-seed cube-prior joint law of the signal, path, stopping index, and output.

Use the finite-randomness reduction following that lemma. Sample the conditional initial state, independent uniforms for all finite choices indexed by state and index (including an input-free index-zero stopping choice), and one output from each terminal state/index law. These finitely many choices are independent of the inputs. Fixing a realization by averaging retains cube-prior success at least \(3/5\). The resulting state rules are Borel, and the state and horizon bounds are unchanged. ◻

Proof. For \(0<u<R\), choose an integer \(j\ge1\) with \(R2^{-j}\le u<2R2^{-j}\), and write \(\delta=R2^{-j}\). Project \(B(x,u)\) onto the first \(p\) coordinates. Each relative-depth \(j\) cell meeting the projected ball has diameter \(\delta\), so the union of those cells lies in a ball of radius \(u+\delta<3\delta\). The cells have disjoint interiors and volume \((\delta/\sqrt p)^p\). The unit-ball estimate used in (70) bounds their number by \[\frac{V_p(3\delta)^p}{(\delta/\sqrt p)^p}\le15^p.\] Using (72) for each cell gives \(P\{s(z)\in B(x,u)\}\le15^p2^d2^{-\lambda j}\). Since \(2^{-j}\le u/R\), this proves (73) after choosing \(C_0\) absolutely. For \(u\ge R\) the bound follows from \(P(C)=1\).

Let \(s_0\) be the lift of the center of \(C\). The cell has Euclidean radius \(R/2\) in parameter space, so the Lipschitz bound implies \(\|s(z)-s_0\|\le R\le2R\) for \(z\in C\). Orthogonal projection onto \(H\) is nonexpansive. Thus the projections of all these lifted points lie in the radius-\(2R\) ball in \(H\) about the projection of \(s_0\). Disjoint ball packing covers that ball by at most \((1+4R/u)^k\) balls of radius \(u\). A point at distance at most \(u\) from \(H\) whose projection lies in one of these balls is within \(2u\) of its center. For \(u\le R\), applying (73) to the cover gives \[P\{\operatorname{dist}(s(z),H)\le u\} \le (1+4R/u)^k C_0^d(2u/R)^\lambda \le C^d(u/R)^{\lambda-k}.\] Here and below \(C\) denotes an absolute constant that may increase. The identity \(Q=(d-1)/2-\lfloor d/8\rfloor\ge d/3\) for large \(d\) lets us absorb \(C^d\) into \(C_1^Q\). For \(u>R\), enlarge \(C_1\) so that the right side is at least one. This proves (74). In particular every affine subspace of the stated dimension has \(P\)-mass zero, by letting \(u\) decrease to zero.

To prove (75), apply the layer-cake formula to \((\operatorname{dist}(s(z),H)/R)^{-n}\mathbf 1_E\). At height \(t>0\) its tail has mass at most \(\min\{\rho,C_1^Qt^{-Q/n}\}\). With \(t_0=C_1^n\rho^{-n/Q}\), \[\begin{align*} \int_0^\infty\min\{\rho,C_1^Qt^{-Q/n}\}\,dt &\le \rho t_0+C_1^Q\int_{t_0}^\infty t^{-Q/n}\,dt\\ &=\frac{C_1^n}{1-\alpha}\rho^{1-\alpha}. \end{align*}\] Because \(\alpha\le1/4\) and \(n\le d\), an absolute \(C_2\) bounds the prefactor by \(C_2^d\). Restoring \(R^{-n}\) proves the assertion.

We turn from affine distances to the projection moment. Tonelli’s theorem expands \(\int J_\eta^k\,d\beta\) over \(z_1,\ldots,z_k\in E\). Write \(s_i=s(z_i)\). For fixed \(A\) and this tuple, integration of \(\prod_{i=1}^k\varphi_\eta(y-As_i)\) over the common label \(y\) is the density at zero of the \(k-1\) differences from the first of the independently mollified labels \(As_i+\eta Z_i\). After averaging over \(A\), the differences are centered Gaussian, independently across rows, with per-row covariance \[ G+\eta^2(I+\mathbf1\mathbf1^{\mathsf T}),\qquad G=\bigl(\langle s_i-s_1,s_j-s_1\rangle\bigr)_{i,j=2}^k. \tag{78}\] Their density at zero is \[(2\pi)^{-n(k-1)/2} \det\!\left(G+\eta^2(I+\mathbf1\mathbf1^{\mathsf T})\right)^{-n/2} \le \det(G)^{-n/2},\] where the upper bound is interpreted as infinity when \(G\) is singular. For nonsingular \(G\), the inequality follows by factoring \(G^{1/2}\) and observing that all eigenvalues of \(I+\eta^2G^{-1/2}(I+\mathbf1\mathbf1^{\mathsf T})G^{-1/2}\) are at least one. Gram–Schmidt gives \[\det(G)^{-n/2} =\prod_{i=2}^k \operatorname{dist}\bigl(s_i, \operatorname{aff}(s_1,\ldots,s_{i-1})\bigr)^{-n}.\] The affine spaces here have dimension at most \(k-2\). The null-mass consequence of (74), applied successively, shows that degenerate tuples have product \(P\)-measure zero. Integrate the last display from \(z_k\) down to \(z_2\) using (75), then integrate \(z_1\) with mass \(\rho\). The result is \[\rho\bigl(C_2^dR^{-n}\rho^{1-\alpha}\bigr)^{k-1},\] which is (76).

Hölder’s inequality now bounds the mollified measure of \(B\) by \[\beta(B)^{1-1/k} \bigl(C_2^dR^{-n}\bigr)^{1-1/k} \rho^{\,1-\alpha+\alpha/k}.\] Since \(\rho\le1\), this implies the weaker power of \(\rho\) in (77). For an open \(B\), couple the mollified labels as \(As(z)+\eta Z\) using one independent standard Gaussian \(Z\). As \(\eta\) decreases to zero, membership of \((A,As(z))\) in \(B\) implies eventual membership of the approximants. Fatou’s lemma therefore passes the same bound to the exact observation measure. The Gaussian–Lebesgue measure \(\beta\) is a locally finite regular Borel measure on the Euclidean joint space. Its outer regularity extends the bound from open sets to every Borel \(B\) of finite measure. In particular the exact measure vanishes on \(\beta\)-null sets, so the same bound extends to the completion of \(\beta\) as well. The mollifier was used only in this calculation; the observation in (77) is the exact label. ◻

Proof. The functions \(q_w\) are Borel by integration of the Borel routing indicators. For \(b_w>0\) define \(E_w=\{z:q_w(z)>2^{ad}b_w\}\). Markov’s inequality gives \(P(E_w)\le2^{-ad}\). A state with \(b_w=0\) is reached with probability zero and contributes nothing.

Retain the lift \(s_0\) of the center of \(C\) used in the preceding proof. Conditional on \(z\), the vector \(A(s(z)-s_0)\) is distributed as \(\|s(z)-s_0\|Z\) for a standard Gaussian \(Z\in\mathbb R^n\). Because \(\|s(z)-s_0\|\le2R\), \[ \mathbb P\{\|As(z)-As_0\|>4R\sqrt n\} \le \mathbb P\{\|Z\|^2>4n\} \le 2^{n/2}e^{-n}. \tag{80}\] The last inequality uses \(\mathbb E e^{\|Z\|^2/4}=2^{n/2}\). Since \(n\ge d/64\) for large \(d\), the right side is exponentially small in \(d\).

Define the joint domain \[\mathcal D=\{(A,y):\|y-As_0\|\le4R\sqrt n\}\] and let \(B_w=\mathcal D\cap f^{-1}(\{w\})\). These Borel sets are disjoint, and the volume bound gives \[\sum_w\beta(B_w)\le\beta(\mathcal D) =V_n(4R\sqrt n)^n\le(20R)^n.\] Apply (77) to \(E_w\) and \(B_w\), and sum over \(w\). Hölder’s inequality on the finite state set yields \[\begin{align*} \sum_w\mathbb P\{z\in E_w,(A,As(z))\in B_w\} &\le \bigl(C_2^dR^{-n}\bigr)^{1-1/k} 2^{-ad(1-\alpha)} N^{1/k}\left(\sum_w\beta(B_w)\right)^{1-1/k}\\ &\le C_4^dN^{1/k}2^{-ad(1-\alpha)} \tag{81}\end{align*}\] for an absolute \(C_4\ge1\). The powers of \(R\) cancel exactly. Since \(1-\alpha\ge3/4\) and \(N^{1/k}\le2^d\), choose \(a\) so that \(3a/4\ge\log_2 C_4+3\). The last display is then at most \(2^{-2d}\). Adding (80) and reducing an absolute \(c_1>0\) if necessary proves (79) for large \(d\). ◻

Proof. Run the fresh next block, and let \(\mathcal E=\{q_W(z)>2^{ad}b_W\}\) be the event in (79). Write \(\delta=\mathbb P(\mathcal E)\le2^{-c_1d}\). Discard \(\mathcal E\). For \(b_w>0\), let \(r_w=\mathbb P(\mathcal E^c\mid W=w)\), and also discard every state with \(r_w<1/2\). The mass of these states is at most \(2\delta\): \[\sum_{w:r_w<1/2}b_w \le2\sum_{w:r_w<1/2}\mathbb P(\mathcal E\cap\{W=w\}) \le2\delta.\] The two deletions therefore cost at most \(3\delta\).

For a remaining state \(w\), condition on \(W=w\) and \(\mathcal E^c\). Its parameter law \(P'\) is given by \[P'(B)=\frac1{b_wr_w} \int_B \mathbf1_{\{q_w(z)\le2^{ad}b_w\}}q_w(z)\,dP(z)\] for Borel \(B\). Since \(r_w\ge1/2\), \[ P'\le2^{ad+1}P\le2^{ad+1}K\mu_C. \tag{84}\]

For \(z\in C\), let \(U_j(z)\) be the cell containing \(z\) at relative depth \(j\). Select the least \(j\ge0\) maximizing the score \[ 2^{\lambda j}P'(U_j(z)). \tag{85}\] The score at \(j=0\) is one. Since \(\mu_C(U_j(z))=2^{-pj}\), (84) gives \[2^{\lambda j}P'(U_j(z)) \le2^{ad+1}K2^{-(p-\lambda)j} \le2^{ad+1+Ddt-(p-\lambda)j}.\] This upper bound tends to zero. Thus the maximum is attained, and every selected depth is at most \(J_t\), since a selected score is at least one. The least-maximizer rule is unambiguous. It is Borel: there are finitely many possible depths, the cell at each depth is a Borel function of \(z\), and each score is a fixed number on that cell.

For each possible selected cell \(U\), define the actual selection event \[ F_U=\{z:\text{the rule in \eqref{l:lt:score} selects }U\}\subseteq U. \tag{86}\] These Borel events form a finite partition of \(C\). Discard those for which \(P'(F_U)<2^{-d}P'(U)\). At a fixed depth the cells partition \(C\), so their \(P'\)-masses sum to one. Summing over the at most \(\lfloor J_t\rfloor+1\) depths bounds this deletion by the second term of (83). Events of zero mass need no conditional law.

Fix a remaining event \(F_U\) of positive mass, and let \(j\) be the relative depth of \(U\). Put \(P''=P'(\,\cdot\mid F_U)\). If a descendant \(V\) of \(U\) at further depth \(i\) meets \(F_U\), choose \(z\in V\cap F_U\). Maximality on this parameter’s cell chain gives \[2^{\lambda j}P'(U)\ge2^{\lambda(j+i)}P'(V).\] Consequently \[P''(V)\le\frac{P'(V)}{P'(F_U)} \le2^d2^{-\lambda i},\] using \(P'(F_U)\ge2^{-d}P'(U)\). If \(V\cap F_U\) is empty, its \(P''\)-mass is zero. This proves regularity in \(U\).

The selected score is at least one, so \(P'(U)\ge2^{-\lambda j}\) and \(P'(F_U)\ge2^{-d-\lambda j}\). The cell reference measures satisfy \(\mu_C|_U=2^{-pj}\mu_U\). Therefore \[\begin{align*} P'' &\le2^{ad+1}K \frac{2^{-pj}}{P'(F_U)}\,\mu_U\\ &\le2^{(a+1)d+1}K2^{-(p-\lambda)j}\mu_U \le2^{Dd}K2^{-(p-\lambda)j}\mu_U. \tag{87}\end{align*}\] The last inequality uses \((a+1)d+1\le(a+2)d=Dd\) for \(d\ge1\). Substituting the value of \(K\) yields \[P''\le2^{Dd(t+1)-(p-\lambda)(l+j)}\mu_U,\] which is (82) at the new time and total depth. The normalization throughout is by \(P'(F_U)\), including when \(F_U\) is a proper subset of \(U\). ◻

Proof. Apply Lemma 28 at each surviving history and at each block. There are finitely many histories at every time. The conditional deletion bounds are uniform, so their unconditional sum is at most \(\Delta_m\): at each time, the probabilities of the surviving histories sum to at most one. Also \(p-\lambda=(d-1)/2\), and hence \(J_t=O(t+1)\) with an absolute constant depending only on the already fixed \(a\). Thus \[\Delta_m\le3m2^{-c_1d}+C(m^2+m)2^{-d},\] which tends to zero when \(m=o(d)\).

At a surviving terminal history, integrating (82) forces \(K\ge1\). Hence \((p-\lambda)l\le Ddm\). Since \(\mu(C)=2^{-pl}\), the bound relative to the original cube probability becomes \[ P\le2^{Ddm+\lambda l}\mu\le2^{2Ddm}\mu. \tag{89}\] The last inequality uses \(\lambda=p-\lambda\). The history fixes the final boundary state and therefore its output. Equation (70) bounds conditional success by \(2^{2Ddm}(5\epsilon)^p\). Average over surviving histories and add the deleted mass to obtain (88). For \(m=0\), the same argument is the fixed-output bound at the root. ◻

Proof. Let \(S\) be uniform on \(S^{d-1}\), independently of the \(T\) pregenerated Gaussian rows. The original jointly measurable experiment has prior success equal to the integral of its fixed-signal successes. For each admissible fixed shared seed, Lemmas 2 and 1 give Borel rules with the same uniform-prior law. The bound below is uniform over these rules, so it bounds the original conditional success before averaging over the seed. This returns to the original learner; it does not reuse the cube-selected program.

If \(T\le d/4\), the span \(U\) of the rows has dimension \(T\) almost surely. Given the rows, the labels determine \(P_US\), since the row map is injective on \(U\). Conditional on the rows and \(P_US\), the residual \((I-P_U)S\) is uniform on the sphere in \(U^\perp\) of radius \(r=(1-\|P_US\|^2)^{1/2}\). This follows, for example, by representing \(S\) as a normalized standard Gaussian and using rotational invariance of its component in \(U^\perp\).

Spherical symmetry gives \(\mathbb E\|P_US\|^2=T/d\), so Markov’s inequality yields \[\mathbb P\{r<1/2\} =\mathbb P\{\|P_US\|^2>3/4\} \le\frac{4T}{3d}\le\frac13.\] Suppose \(r\ge1/2\) and condition on the rows and labels. Fix any possible output, and let \(w\) be its projection onto \(U^\perp\). If \(w=0\), its residual error is \(r>1/10\). If \(w\ne0\), write \(\Theta\) for the unit residual direction and \(e=w/\|w\|\). When \(|\langle\Theta,e\rangle|<1/2\), the component of \(r\Theta\) orthogonal to \(e\) has length greater than \(\sqrt3\,r/2>1/10\), so the output cannot succeed. The second moment of \(\langle\Theta,e\rangle\) for the uniform direction in the \((d-T)\)-dimensional space \(U^\perp\) is \(1/(d-T)\). Markov’s inequality therefore bounds success for the fixed output by \(4/(d-T)\). The learner’s conditional output law uses only the revealed data and independent randomness, so averaging over that law preserves the bound. Angular success implies the Euclidean error bound used here.

The uniform-prior success is consequently at most \(1/3+4/(d-T)\), which is below \(2/3\) for large \(d\) when \(T\le d/4\). The every-signal premise gives uniform-prior average at least \(2/3\), a contradiction. ◻

Proof of Theorem 23. Write \(L=\log_2(1/\epsilon)\) and keep the absolute constants \(a,c_1,D\) already fixed. Choose \[ L_0\ge\max\{32D,\,2\log_2 5\},\qquad 0<c\le\min\left\{1,\frac1{4L_0},\frac1{2048D}\right\}. \tag{90}\] Suppose for contradiction that there are infinitely many dimensions with successful learners satisfying \[ T<c\,dL. \tag{91}\] All asymptotic reductions below concern these dimensions only.

We first obtain the precision range forced by the finite set of terminal labels. For fixed shared rules, there are at most \((T+1)2^M\) terminal state/index labels. Let \(\mathcal O_{t,u}\) be the output law at one such label. For each parameter, its success probability is at most the sum, over all terminal labels, of the success probabilities under their output laws: this drops the probability of reaching each label, which is at most one. Integrating over \(z\) and then over each \(\mathcal O_{t,u}\), using (70), bounds cube-prior success by \((T+1)2^M(5\epsilon)^p\). This bound is uniform in the fixed shared rules, so it also bounds the original randomized learner. Its every-signal guarantee gives cube-prior average at least \(2/3\). Thus \[ p(L-\log_2 5) \le M+\log_2(T+1)+\log_2(3/2). \tag{92}\]

Because \(L\ge\log_2 10\), the absolute number \(c_0=1-\log_2 5/\log_2 10\) is positive and \(L-\log_2 5\ge c_0L\). Under (91) and \(c\le1\), \[\log_2(T+1)\le1+\log_2 d+\log_2 L\le1+\log_2 d+L.\] For large \(d\), absorb the last \(L\) into \(c_0pL\) on the left of (92). It follows that \[ L=O\!\left(\frac{M+\log d}{d}\right)=o(d), \qquad T=o(d^2). \tag{93}\] The constants in this bound are absolute. In particular, for a fixed memory sequence it bounds every \(L\) arising in (91) by the same sequence \(o(d)\).

At each such dimension, Lemma 24 supplies a deterministic Borel learner with cube-prior success at least \(3/5\). Pad a halted path by retaining its terminal state and its terminal index. At any later layer, the continuing states together with all terminal tags have total width at most \[ N=(T+2)2^M. \tag{94}\] Pad the last block with ignored rows and put \(m=\lceil T/n\rceil\). By (93), \(\log_2 N=o(d^2)\) and \(m=o(d)\). Since \(k=\Theta(d)\), \(N^{1/k}\le2^d\) for all sufficiently large dimensions under consideration. Proposition 29 applies and gives \[ \frac35\le \Delta_m+2^{2Ddm}(5\epsilon)^p =o(1)+2^{2Ddm}(5\epsilon)^p. \tag{95}\] The \(o(1)\) is uniform over the short-run precisions for a fixed memory sequence, by the uniform bound on \(L\) just obtained.

If \(L\le L_0\), then (91) and \(c\le1/(4L_0)\) give \(T<d/4\). Apply Lemma 30 to the original learner and its uniform-sphere average, obtaining a contradiction for large \(d\). This use of the original learner preserves the prior of that lemma.

It remains to consider \(L>L_0\). For large \(d\), \(n\ge d/64\), so \[m\le64cL+1,\qquad 2Ddm\le128Dc\,dL+2Dd\le dL/8.\] The last inequality follows from \(c\le1/(2048D)\) and \(L\ge32D\). Also \(p=d-1\ge d/2\) and \(L\ge2\log_2 5\), whence \[p(L-\log_2 5)\ge dL/4.\] Therefore the second term in (95) is at most \(2^{-dL/8}\). It tends to zero, as does \(\Delta_m\), contradicting the fixed lower bound \(3/5\). No infinite subsequence (91) exists. This proves the asserted sample bound with the absolute \(c\) in (90). ◻

Proof. Use the reductions following Lemma 2 under the uniform prior. First fix the shared rule randomness with success greater than \(3/5\), and apply Lemma 1. Then fix the independent initial state, the finite transition choices, and the outputs assigned to terminal state/index pairs by averaging. The resulting deterministic Borel learner has uniform-prior success at least \(3/5\) and the same state and horizon bounds.

Put \(L=\log(1/\epsilon)\), with \(0<\epsilon\le1/10\). The case \(T\ge dL\) already has the required order. In the other case the fixed learner has at most \((T+1)2^M\) terminal outputs, counting every possible stopping index. Angular error at most \(\epsilon\) implies Euclidean error at most \(\epsilon\), because \(2\sin(\theta/2)\le\theta\). Applying (97) to each output gives \[ \frac35\le(T+1)2^M\epsilon^{d-1},\qquad (d-2)L\le M\log2+O(\log d). \tag{114}\] For the second inequality, take logarithms in the first and use \(T<dL\) and \(\log(dL+1)\le\log(d+1)+L\). Thus \(M=o(d^2)\) implies \(L=o(d)\) along these putative short runs, and eventually \(T\le d^2\). This is a consequence of the short-run assumption, not an added restriction on the accuracy sequence.

Preserve a stopped state together with its terminal index, and use ignored fresh samples after stopping. At any later index there are at most \(2^M\) active states and \((T+1)2^M\) tagged terminal states. Padding the last block as well therefore uses width at most \[ (T+2)2^M,\qquad m=M\log2+\log(T+2)=o(d^2). \tag{115}\] Take \(B=\lceil T/k\rceil\) blocks, padding with fewer than \(k\) ignored samples if necessary. The final augmented history recovers the output. Under the product of the signal and output marginals, angular success has probability at most \(\epsilon^{d-1}\) by (97). For an event with probabilities \(u\) and \(v\) under two laws, data processing to the event gives relative entropy at least \(u\log(1/v)-\log2\): expand binary relative entropy and use binary entropy at most \(\log2\). Hence \[ I(S;G_B)\ge I(S;\widehat S) \ge\frac35(d-1)L-\log2. \tag{116}\] Since \(m/p=o(d)\), (113) and (116) imply \(L\le C(1+B)\). With \(B\le T/k+1\), this gives \(T\ge cdL\) whenever \(L\) exceeds a fixed absolute constant.

We finish the bounded range of \(L\) with the route’s linear sample bound. Grant the learner all \(T<d\) pre-generated rows and exact labels, including any it did not use. Their row space \(V\) has dimension \(T\) almost surely. The data determine \(P_VS\), and conditional on the data the residual \(S-P_VS\) has uniform direction in \(V^\perp\), with radius \(\sqrt{1-\|P_VS\|^2}\). This follows by splitting a normalized standard Gaussian into its independent row-space and nullspace components. Its conditional mean is zero and its covariance is \((1-\|P_VS\|^2)P_{V^\perp}/(d-T)\). For every unit estimate determined by the data, also after averaging independent output randomness, \[ \mathbb E\langle S,\widehat S\rangle^2 \le\mathbb E\|P_VS\|^2+\frac1{d-T} =\frac Td+\frac1{d-T}. \tag{117}\] On angular success the squared inner product is at least \(\cos^2(1/10)\). Since \((3/5)\cos^2(1/10)>1/2\), average success \(3/5\) excludes \(T\le d/2\) for large \(d\). This linear bound absorbs the bounded range of \(L\) and completes the proof. ◻

Proof of Corollary 34 using side data. Take \(S\sim\mu\) and use the reductions following Lemma 2. First fix the shared rule randomness with uniform-prior success greater than \(3/5\), apply Lemma 1, and then fix the independent initial state with success at least \(3/5\). Fresh transition and terminal output randomness may remain: the two lemmas permit finite message kernels, and the calculation below integrates the terminal output law.

Put \(L=\log(1/\epsilon)\) with \(0<\epsilon\le1/10\). If \(T=0\), the fixed initial state and terminal rule give an output independent of \(S\), whose success is at most \(\epsilon^{d-1}<3/5\) by (119). Thus the successful runs considered below have \(T\ge1\).

It suffices to consider \(T<dL\). There are at most \((T+1)2^M\) terminal pairs consisting of the stopping index and state. For a fixed pair \(h\), the joint subprobability law \(\lambda_h\) of \(S\) and the event of reaching \(h\) satisfies \(\lambda_h\le\mu\). The unit output conditional on \(h\) uses only its terminal law and fresh randomness, so is independent of \(S\). Angular success implies Euclidean error at most \(\epsilon\), and (119) applies since \(\epsilon\le1/10\). Integrating the terminal output law and summing over pairs gives \[ \frac35\le(T+1)2^M\epsilon^{d-1},\qquad (d-1)L\le M\log2+\log(T+1)+O(1). \tag{143}\] Using \(T<dL\) and \(\log(dL+1)\le\log(d+1)+L\) yields \((d-2)L\le M\log2+O(\log d)\). Along a sequence \(M=o(d^2)\) this implies \(L=o(d)\) in the present short-run case and eventually \(T\le d^2\).

After an early stop, preserve its state together with its terminal index and ignore the remaining fresh samples. The active states and all terminal tags together give the global width bound \[ w=(T+2)2^M,\qquad \log w=M\log2+\log(T+2)=o(d^2). \tag{144}\] The output law at a terminal tag is the original terminal law. Split the \(T\) padded samples into \(N=\lceil T/k_*\rceil\) consecutive blocks of length at most \(k_*\). Let \(\Pi_i\) record every state at the first \(i\) block ends, with \(\Pi_0\) empty. This is the full state transcript, not just its final state.

Independently draw one matrix \(W\) with \(\ell\) Gaussian rows and retain the same \(D_*=(W,WS)\) for all blocks. For every positive-mass history \(h\) of \(\Pi_{i-1}\), its conditional signal law satisfies \[ \frac{d\nu_h}{d\mu}(s) =\frac{\mathbb P(\Pi_{i-1}=h\mid S=s)} {\mathbb P(\Pi_{i-1}=h)} \le B_h:=\frac1{\mathbb P(\Pi_{i-1}=h)}. \tag{145}\] Given \(h\), the next block matrix is still fresh Gaussian and independent of \(S\), and \(W\) remains independent of both. The incoming state is known from \(h\). The persistent-memory restriction makes the successor state a kernel of that state and the block’s complete exact data, with alphabet size at most \(w\). It has no access to \(D_*\). Lemma 36 therefore applies conditionally on each history.

The posterior-density cost is small after averaging. Since \(\Pi_{i-1}\) is a tuple of at most \(N\) states from an alphabet of size \(w\), \[\mathbb E_h\log B_h=H(\Pi_{i-1})\le N\log w.\] Jensen’s inequality gives \[\begin{align*} \mathbb E_h\log\left(C\left(2+\frac{\log B_h}{d}\right)\right) &\le\log\left(C\left(2+\frac{N\log w}{d}\right)\right) =O(\log d). \end{align*}\] Here \(N=O(d)\) follows from \(T\le d^2\) and \(k_*\ge d/64\) for large \(d\); also \((\log w)/p=o(d)\) by (144). Summing the conditional information bounds for successive states by the chain rule gives an absolute \(C_1\) such that \[ I(S;\Pi_N\mid D_*)\le C_1dN. \tag{146}\] The local cell \(U\) used in each application is not an uncharged part of \(\Pi_N\): its revelation was paid by (142) inside that block’s conditional bound.

For a lower bound on the same information, condition on \(D_*\). Almost surely \(W\) has rank \(\ell\). Its labels specify \(P_WS\), where \(P_W\) is the orthogonal projector onto its row space. The remaining component has uniform direction in the nullspace, of dimension \(d-\ell\), and radius \[\rho=\sqrt{1-\|P_WS\|^2}.\] This conditional law follows by writing \(S\) as a normalized standard Gaussian: the nullspace direction is independent of its length and of the row-space component. The event \(\mathcal G=\{\rho\ge1/2\}\) is determined by \(D_*\), and Markov’s inequality gives \[ \mathbb P(\mathcal G^c) \le\frac43\mathbb E\|P_WS\|^2 =\frac{4\ell}{3d}\le\frac49. \tag{147}\] On \(\mathcal G\), the mass of the conditional sphere within Euclidean distance \(\epsilon\) of any fixed estimate is at most \((4\epsilon)^{d-\ell-1}\). If the ball meets that sphere, choose a point of intersection. The rest of the intersection lies within \(2\epsilon\) of it. After rescaling the residual sphere by \(\rho\ge1/2\), the radius is at most \(4\epsilon\le2/5<1/2\), so the first bound in (119) applies in ambient dimension \(d-\ell\).

The final output \(\widehat S\) is conditionally independent of \(S\) given \((\Pi_N,D_*)\), because the transcript contains its terminal tag. For each value of \(D_*\), compare the actual joint law of \((S,\Pi_N,\widehat S)\) with the product of its conditional \(S\) marginal and conditional \((\Pi_N,\widehat S)\) marginal. On \(\mathcal G\) the success probability under this product is at most \((4\epsilon)^{d-\ell-1}\). Binary relative entropy is at least the true event probability times the negative logarithm of its product-law probability, minus \(\log2\). Integrating over \(\mathcal G\), and using nonnegativity elsewhere, gives \[\begin{align*} I(S;\Pi_N\mid D_*) &=I(S;\Pi_N,\widehat S\mid D_*)\\ &\ge\left(\frac35-\frac49\right)(d-\ell-1) \log\frac1{4\epsilon}-\log2 \ge c_0dL \tag{148}\end{align*}\] for an absolute \(c_0>0\) and sufficiently large \(d\). The coefficient \(3/5-4/9\) accounts for the success mass outside the failed-radius event. For the last inequality, \(d-\ell-1\) is a positive multiple of \(d\) and \(L-\log4\ge(1-\log4/\log10)L\).

Combining (146) and (148), and using \(N=\lceil T/k_*\rceil\le T/k_*+1\), gives the exact intermediate bound \[ T\ge k_*\left(\frac{c_0}{C_1}L-1\right). \tag{149}\] We retain a separate linear endpoint to absorb its additive constant. If \(T<d/3\), reveal all \(T\) pre-generated rows and exact labels, even after an early stop. The same normalized-Gaussian argument gives a uniform conditional sphere of ambient dimension \(d-T\). Its radius is at least \(1/2\) except on an event of probability at most \(4T/(3d)<4/9\). The preceding conditional cap argument therefore bounds the success of even a full-data estimator by \[\frac49+(4\epsilon)^{d-T-1}<\frac35\] for sufficiently large \(d\), a contradiction. Thus \(T\ge d/3\). When \(L\ge2C_1/c_0\), (149) implies \(T\ge cdL\); for smaller \(L\), the linear bound gives the same conclusion after reducing the absolute constant. The case \(T\ge dL\) needed no reduction. Every learner observation throughout this argument is the exact inner product; the auxiliary noise appeared only in the proved passage to the exact-message inequality. ◻

Proof. The subset averaging below is the entropy-cover mechanism used in the Product Theorem of Chung, Graham, Frankl, and Shearer (Chung et al. 1986, sec. V, Equation (22), pp. 33–34). We give the conditional differential-entropy form required here. Let \(Q\) be an independent Haar orthogonal frame and set \(Z_i=\langle Q_i,S\rangle\). Put \(N=d-1\). For a \(k\)-subset \(E\subset\{1,\ldots,N\}\), the entropy chain rule and conditioning give \[h(Z_E\mid Q,K) \ge\sum_{i\in E}h(Z_i\mid Q,K,Z_1,\ldots,Z_{i-1}).\] Every index occurs in the same number of \(k\)-subsets. Averaging over the subsets and over \(Q\), whose law is unchanged by column permutations, yields \[ h(Z_1,\ldots,Z_k\mid Q,K) \ge\frac{k}{N}h(Z_1,\ldots,Z_N\mid Q,K). \tag{156}\] This uses no rotation invariance of the conditional law given \(K\). All projected entropies are finite: the uniform projection density has an integrable logarithm for every number of coordinates at most \(d-1\), and finite-entropy conditioning preserves this as above.

Let \(h_j^0\) be the entropy of \(j\) fixed orthogonal coordinates of a uniform sphere point. The Gaussian maximum-entropy bound and the covariance \(I_j/d\) give \[h_k^0\le\frac{k}{2}\log(2\pi e/d).\] For \(j=N\), the two hemispherical graphs give \[h_N^0=\log(|S^{d-1}|/2)+\mathbb E\log|S_d| \ge-\frac{N}{2}\log d-Cd.\] For the last inequality, use the sphere-area formula and Stirling’s bound, and write \(S=g/\|g\|\); Jensen bounds \(\mathbb E\log\|g\|\) above by \(\tfrac12\log d\), whereas \(\mathbb E\log|g_d|\) is a finite absolute constant. Data processing gives \[h(Z_1,\ldots,Z_N\mid Q,K)\ge h_N^0-I(S;K).\] Thus (156) bounds the information in \(k\) frame coordinates by \(\tfrac{k}{N}I(S;K)+Cd\).

Given \(X_B\), its label is an invertible linear transform of the orthogonal coordinates in its row space. That row space is uniform, independent of \((S,K)\); extending an orthonormal row frame gives the \(Q\) experiment above. Hence the same information bound holds for \(I(Y_B;K\mid X_B)\). Without \(K\), (156) gives \(h_k^0\ge(k/N)h_N^0\). Passing from orthogonal coordinates to \(Y_B\) adds \(\tfrac12\mathbb E\log\det(X_BX_B^{\mathsf T})\), which cancels the leading \(-\tfrac{k}{2}\log d\) term. This proves both inequalities in (154).

By the definition of \(P\), \[I(S;K\mid B)=P-P_0+n\Lambda.\] Freshness and \(Y_B=X_BS\) give the chain-rule identity \[I(S;K)=I(S;K\mid B)+I(Y_B;K\mid X_B).\] Since \(k/(d-1)\le1/4\), the first inequality of (154) can be absorbed on the left. This proves the information estimate in (155). Finally \(h(Y_B\mid X_B,K)=h(Y_B\mid X_B)-I(Y_B;K\mid X_B)\); the two bounds just proved give the negative-entropy estimate. ◻

Proof. We describe a decision tree conditional on \(K,A\). At a node let \(\nu\) be the signal law after the recorded prefix, supported in the current ball \(B(z_0,r_0)\). Enumerate once and for all a countable dense family of affine subspaces of dimensions at most \(\ell-2\), for example those generated by rational points. If the first subspace \(E\) with \[\nu\{s:\operatorname{dist}(s,E)<2\eta r_0\}>p_0\] exists, record whether the signal belongs to this tube. On a negative answer, continue with the conditional law and the same ball. On a positive answer, cover the current ball by a fixed ordered maximal \(\eta r_0\)-separated net, choose the first center within \(\eta r_0\) of \(S\), record its index, and replace the ball by the radius-\(\eta r_0\) ball about that center. Then continue.

The full ambient net has at most \((1+2/\eta)^d\) points. Given the selected subspace, only \(\exp(b_0d+\ell a)\) indices can occur, where \(b_0\) is independent of \(a\ge1\). To see this, an eligible center lies within \(3\eta r_0\) of \(E\). Its projection to \(E\) lies in a radius-\(r_0\) ball, coverable by \((1+2/\eta)^v\) radius-\(\eta r_0\) balls when \(v=\dim E\). Over each covering ball, the eligible centers lie in an ambient radius-\(4\eta r_0\) ball. Their disjoint radius-\(\eta r_0/2\) balls fit in its radius-\(9\eta r_0/2\) enlargement, giving at most \(9^d\) centers. Since \(v\le\ell-2\), the claimed exponential bound follows after enlarging \(b_0\).

If no selected subspace exists, every affine subspace of dimension at most \(\ell-2\) has mass at most \(p_0\) in its open \(\eta r_0\)-tube. Indeed its distance function on the bounded current ball can be approximated uniformly within \(\eta r_0\) by that of a subspace from the countable family. Mass greater than \(p_0\) in the smaller open tube would therefore trigger the larger tube test for a member of the family.

In this case, draw \(\ell-1\) additional independent points from \(\nu\), using \(S\) as the first point, and record whether \[\mathsf V(s_1,\ldots,s_\ell)\ge(\eta r_0)^q.\] On failure continue at the same scale with the updated signal law; on success stop. Before the outcome, the tuple is i.i.d. from \(\nu\). If the volume is smaller than \((\eta r_0)^q\), one of the \(q\) successive distances is smaller than \(\eta r_0\). Conditionally on its predecessors, each such event has probability at most \(p_0\). The pass probability is therefore at least \(1-qp_0\ge1/2\).

Record the decision type, its outcome, and any ambient net index, but not the extra test points. Given \((K,A)\) and the prefix, the type and selected subspace are already determined. The first successful subspace is a measurable choice because the family is countable and its tube probabilities are kernel integrals of Borel indicators. Fixed scaled nets and ordered ties give measurable centers. Regular conditional laws at nodes, with arbitrary defaults at null nodes, complete a recursion by probability kernels on standard Borel spaces. Independent auxiliary draws make \(W\) independent of \((S,C_*)\) given \((K,A)\).

First truncate the tree after \(u\) decisions, and write \(C_u,N_u\) for its string and number of refinements. At every active node the progress outcome, meaning refinement or a successful test, has conditional probability \(p\ge p_0\). Its binary entropy is at most \[p\{\log(1/p_0)+1\}=p u_d,\] because \(-p\log p\le p\log(1/p_0)\) and \(-(1-p)\log(1-p)\le p\). The expected number of progress outcomes is at most \(\mathbb E N_u+1\). Summing the node entropies and the eligible index costs gives \[ H(C_u\mid K,A) \le(b_0d+\ell a+u_d)\mathbb E N_u+u_d. \tag{161}\] The expected number of active decisions is at most \(p_0^{-1}(\mathbb E N_u+1)\). For an encoding that is decoded given \(K\) alone, use two bits for the type and outcome at each active node and a fixed-length full ambient net index at a refinement. The decoder knows the truncation depth \(u\); the recorded type and outcome determine any earlier stop. The ambient index recovers the next center without knowing the selected subspace. This prefix encoding has expected length at most \(C_a d(1+\mathbb E N_u)\) nats, so \[ H(C_u\mid K)\le C_a d(1+\mathbb E N_u). \tag{162}\]

At finite depth all strings have finite entropy. The area bound and the conditional mutual-information identity give \[\begin{align*} 0\le P_{\mathrm{mid},u} &=P-na\mathbb E N_u+I(S;C_u\mid K,A)\\ &\le P-\{(n-\ell)a-b_0d-u_d\}\mathbb E N_u+u_d. \end{align*}\] For large \(d\), \(n-\ell>d/2\) and \(u_d=O(\log d)\). Choose \(a\) once and for all large enough that the coefficient in braces is at least \(\delta da\) with an absolute \(\delta>0\). It follows that \(\sup_u\mathbb E N_u<\infty\), and then that the expected number of active decisions is bounded uniformly in \(u\). By monotone convergence the full number of decisions is integrable, so the tree terminates almost surely. Denote its string and refinement count by \(C_*,N\).

The same prefix encoding at termination has finite expected length, so \(H(C_*\mid K)<\infty\). The truncated prefixes increase to the full string and \(N_u\uparrow N\). Conditional information in the prefixes increases to the information in the full countable string; this also follows from the chain rule and \(H(C_*\mid C_u,K,A)\to0\), using its finite entropy. Passing to the limit in the preceding bounds proves (157)–(159). Thus the stopping argument did not presume entropy finiteness for an infinite procedure.

Finally condition on a terminal prefix just before its successful test, with signal law \(\nu\). Let \(E_{\mathrm{pass}}\) be its symmetric volume event and set \(Q=\nu^{\otimes\ell}(\,\cdot\mid E_{\mathrm{pass}})\). The symmetry makes all marginals equal, and the first marginal is exactly the signal law after recording the pass. Call it \(\mu_*\). If \(p=\nu^{\otimes\ell}(E_{\mathrm{pass}})\ge1/2\), then the product-reference decomposition gives \[D(Q\|\mu_*^{\otimes\ell}) =D(Q\|\nu^{\otimes\ell})-\ell D(\mu_*\|\nu) \le\log(1/p)\le\log2.\] All terms are finite because \(dQ/d\nu^{\otimes\ell} =\mathbf1_{E_{\mathrm{pass}}}/p\). The volume bound holds throughout the conditioned law. This proves (160). ◻

Proof. We first identify a common measure for the two singular laws. Let \(\mathcal R\) be the open region in the ambient tuple–matrix space where \(D_{\mathbf s}\) has rank \(q\), \(X\) has rank \(k\), and \(j_X(s_i)>0\) for every \(i\). On the incidence constraint \(XD_{\mathbf s}=0\), let \(\gamma_{\mathbf s}\) be the Gaussian matrix law conditioned on that constraint. The ambient Gaussian density of \(XD_{\mathbf s}\) at zero is \[\phi_{\mathbf s}=(2\pi)^{-kq/2}\mathsf V(\mathbf s)^{-k}.\] Indeed each row has covariance \(D_{\mathbf s}^{\mathsf T}D_{\mathbf s}\). Write \(p_X\) for ambient Gaussian matrix density. On the regular incidence set the locally finite measure \[ \sigma^{\otimes\ell}(d\mathbf s)\, \phi_{\mathbf s}\,\gamma_{\mathbf s}(dX) \tag{165}\] also has the integration description \[ p_X(X)\,dX\,\sigma(ds_1) \prod_{i=2}^{\ell} \frac{\sigma_{X,Xs_1}(ds_i)}{j_X(s_i)}. \tag{166}\]

To verify this equality, take a continuous test \(G(\mathbf s,X)\) compactly supported in \(\mathcal R\). In its integral under \(\sigma^{\otimes\ell}(d\mathbf s)p_X(X)dX\), insert the normalized indicator of a radius-\(\varepsilon\) ball in \(\mathbb R^{kq}\), evaluated at \(XD_{\mathbf s}\). Fixing the tuple first, the conditional law given \(XD_{\mathbf s}=Z\) is \(\gamma_{\mathbf s}\) translated by \(Z(D_{\mathbf s}^{\mathsf T}D_{\mathbf s})^{-1}D_{\mathbf s}^{\mathsf T}\). This translation and the Gaussian image density vary continuously at \(Z=0\). On the tuple projection of the compact support, the smallest singular value of \(D_{\mathbf s}\) is bounded away from zero, so the image densities are uniformly bounded. Dominated convergence gives (165).

In the other order, fix \(X,s_1\) and apply the area identity (150) separately to \(s_2,\ldots,s_\ell\), using labels \(X(s_i-s_1)\). The affine fibers near the zero label are continuous translations and scalings of unit spheres. On the compact regular support their radii and \(j_X(s_i)\) are bounded away from zero, so the fiber integrals of \(G\) are continuous at zero and uniformly bounded. Dominated convergence in the label vector gives (166). Equality on all continuous compactly supported tests identifies the locally finite Borel measures on the regular set. Thus it also holds for nonnegative measurable integration there. This is a regular-region identity; no global finite mass for the unweighted incidence measure has been assumed.

Both probability laws in the comparison give this region full mass. For the reference, the one-point law has a density relative to sphere area, so its independent tuple is affinely independent almost surely. Its constrained rows live in dimension \(d-q>k\) and have full row rank almost surely. On the constraint, all points have the same row-space projection. That projection has norm strictly less than one: if \(s_1\) were in the row space, then \(\langle s_1,s_i-s_1\rangle=0\) would give \(\langle s_1,s_i\rangle=1\), forcing \(s_i=s_1\) and contradicting full affine rank. For the actual law, the volume lower bound gives full affine rank, and the true \((S_1,X_A)\) marginal gives full row rank and positive residual radius almost surely. The quantities \(j_X(s_i)\) agree on the constraint because their row-space projections agree.

Condition now on \((K,C_*)\). Jointly measurable density versions can be obtained by taking Radon–Nikodym derivatives of the joint laws with their conditioning variables and then disintegrating; absolute continuity follows from the finite-entropy conditioning above and from the coupling bound. Let \(p_c\) be the full-sphere marginal density, \(p_{1,X}\) the density of the true \((S_1,X_A)\) law relative to \(\sigma\otimes dX\), and \(p_{\mathrm{sl}}(\,\cdot\mid A)\) the conditional slice density. Let \(t(\mathbf s\mid A)\) be the coupling density relative to the product of these slice marginals. The reference density relative to (165) is \[\frac{\prod_{i=1}^{\ell}p_c(s_i)}{\phi_{\mathbf s}}.\] The actual density relative to the same measure, using (166), is \[\frac{p_{1,X}(s_1,X)}{p_X(X)} \prod_{i=2}^{\ell} \{p_{\mathrm{sl}}(s_i\mid A)j_X(s_i)\}\, t(\mathbf s\mid A).\] Here \(A=(X,Xs_1)\) is determined by \(X,s_1\). Each \(p_c(S_i)\) is finite and positive almost surely under the actual law, since each coordinate has that marginal after averaging \(A\). These densities therefore establish absolute continuity of the actual law with respect to the reference, rather than transferring arbitrary null sets between the singular laws.

The first-coordinate contribution to the expected log ratio is \[\begin{align*} \mathbb E\log\frac{p_{1,X}(S_1,X_A)} {p_X(X_A)p_c(S_1)} &=I(S;X_A\mid K,C_*)+I(X_A;C_*\mid K)\\ &=I(X_A;C_*\mid S,K). \end{align*}\] The last equality uses independence of \(X_A\) from \((S,K)\) at block entry. Each of the other \(q\) coordinates contributes \(h_f-h_{\mathrm{mid}}+\mathbb E\log j_{X_A}(S)\). The term \(\log\phi_{\mathbf S}\) contributes \(-\tfrac{kq}{2}\log(2\pi)-k\mathbb E\log\mathsf V\), and \(\log t\) contributes \(D_{\mathrm{coup}}\). These are finite log integrals. The signal and slice log densities are integrable because \(H(K,C_*)<\infty\); the first-coordinate divergence is at most \(H(C_*\mid K)\); the Jacobian has its original true marginal; and \[q(\log\eta+\log r_*)\le\log\mathsf V(\mathbf S)\le q\log2\] with \(\mathbb E[-\log r_*]<\infty\). The coupling log likelihood is integrable by its finite divergence and the usual \(1/e\) negative-part bound. Taking the log ratio now proves (163).

Discard \(X_A\) by data processing. The divergence of the tuple from the product of its \((K,C_*)\)-conditional marginals is at most \(\mathcal E\). Adding \(W\) and using an independent \((K,C_*)\)-conditional copy of \(W\) in that reference adds at most \(H(W\mid K,C_*)\le b\). Decomposing the same finite divergence after conditioning on \(W\) gives \[\ell I(S;W\mid K,C_*)+ \mathbb E D\!\left( \mathcal L(\mathbf S\mid K,C_*,W) \middle\| \mathcal L(S\mid K,C_*,W)^{\otimes\ell}\right).\] The equality of every signal–message marginal, established before the lemma, is what makes the first term \(\ell\) times the same information. The second term is nonnegative. This proves (164). ◻

Proof. By definition, \(P_+=P_{\mathrm{mid}}+h_{\mathrm{mid}}-h_+\). Combine (159) and (168), and take \(\gamma=\delta/2\). For sufficiently large \(d\), the coefficient \(-\delta da+C_a+\gamma da\) of \(\mathbb E N\) is nonpositive. The term \(u_d=O(\log d)\) is absorbed in \(C_2d\). Since \(P,\Lambda\ge0\), the remaining \(C'(P+d\Lambda)/d\) is bounded by \((C_1/d)(P+\gamma d\Lambda)\). This proves (169).

Every new transcript is countable with finite entropy, specifies the new containing ball, and has \(\Lambda_+<\infty\). Fresh future matrices can therefore be generated and the construction repeated. Starting from \(P_0=O(d)\) and \(\Lambda_0=0\), iteration through \(m\le d\) steps has multiplier \((1+C_1/d)^m\le e^{C_1}\), which proves the potential bound in (170). Lemma 37 then gives the information bound. No linear-growth claim for unrestricted numbers of blocks is made. ◻

Proof. Set \(L=\log(1/\epsilon)\). For almost every realization of shared rule randomness, Lemmas 1 and 2 give Borel rules with the same uniform-prior experiment. All bounds below are numerical bounds on that conditional success probability, with constants independent of the realization, so they may be averaged. No jointly selected family of Borel versions is needed. The joint independence of the shared randomness and initial state from the signal and rows ensures the required signal-independent initial transcript for almost every value of the shared randomness.

We first explain why the restriction \(m\le d\) suffices. An angular cap of radius \(\epsilon\) has uniform mass at most \((2\epsilon)^{d-1}\). For example, its polar-area numerator is at most \(\epsilon^{d-1}/(d-1)\), while its denominator is at least \((\pi/3)(\sqrt3/2)^{d-2}\); the displayed bound follows for large \(d\). There are at most \((T+1)2^M\) terminal time–state pairs. For each pair, integration over its fixed fresh output law contributes at most one cap mass, even before multiplying by its reach probability. Summing and averaging over shared randomness gives \[ (d-1)L\le M\log2+\log(T+1)+(d-1)\log2+\log(3/2). \tag{171}\] At indices with \(T<dL\), \(\log(T+1)\le\log(d+1)+L\). Since \(M=o(d^2)\), (171) implies \(L=o(d)\) along those indices. Also \[b=\log((T+2)2^M)\le d^2\] eventually, and after padding to a multiple of \(k\), \[m=\lceil T/k\rceil\le 32L+1=o(d)\le d\] eventually. Thus every potentially short run lies within the proved horizon.

At indices with \(T\ge dL\), the claimed conclusion holds with constant one. At all remaining indices, the horizon and width bounds just established apply eventually. Pad an early-stopping program by retaining its terminal state and stopping index, then ignore later observations and any suffix added to complete the last block. At boundaries its state is a message with at most \(e^b\) values. The augmented transcript retains all earlier auxiliary strings, but the learner uses only its state. Future matrices remain fresh, so Proposition 40 applies with \(m=\lceil T/k\rceil\le d\). For each shared seed, \(I(S;K_m)\le C_0d(m+1)\), with an absolute \(C_0\).

Let \(\pi\) be the success probability for that seed. The output uses information contained in \(K_m\) and fresh randomness. Under the product of its marginal and the uniform signal law, success has probability at most \((2\epsilon)^{d-1}\). By data processing and (1), \[I(S;K_m)\ge \pi(d-1)\log\frac1{2\epsilon}-\log2.\] Combining the two bounds gives a numerical inequality in \(\pi\); averaging it over the shared seed replaces \(\pi\) by the original success probability, at least \(2/3\). Thus, for absolute \(L_0,c_0>0\), whenever \(L\ge L_0\), \[c_0dL\le C_0d(m+1)\le C_0d(T/k+2),\] so \(T\ge k(c_0L/C_0-2)\). Choose \(L_1=\max\{L_0,4C_0/c_0\}\). Since \(k\ge d/32\), this gives \[T\ge \frac{c_0}{64C_0}\,dL\qquad(L\ge L_1).\] For \(L<L_1\), the local full-data endpoint in Lemma 3 gives \(T>d/4\), hence \(T\ge dL/(4L_1)\). The minimum of these absolute constants and one works for every allowed accuracy sequence, including nonmonotone ones. ◻

Proof. Apply (OpenAI 2026a, Theorem 3.3) with row count \(r\), difference count \(p-1\), tuple size \(p\), and base and reweighted measure both equal to \(\mu\). Its dimension condition is exactly \(r+p-1\le d-2\), and its determinant and constrained Gaussian law are \(J\) and \(\gamma_{r,B_{\mathbf s}}\) above. ◻

Proof. A new sphere point avoids the proper affine span of its predecessors almost surely, so \(J>0\) for \(\mu^{\otimes p}\)-almost every tuple. Apply (173) separately with \(r=k+1\). Its dimension condition is \[r+(p-1)=k+p\le d-2,\] which follows from the integer inequality \(k+p+1<d\). We check directly that the total mass on the label side is finite. The exponent in (172) is \((d-k-3)/2\ge0\), and hence \[\int \rho_{0,k+1}(X,y)^p\,dy \le c_{d,k+1}^{\,p-1} \det(XX^{\mathsf T})^{-(p-1)/2}.\] Here \(c_{d,k+1}\) is the positive normalizing constant in (172). Gram–Schmidt on the Gaussian rows expresses \(\sqrt{\det(XX^{\mathsf T})}\) as the product of their successive perpendicular lengths. Conditional on the preceding rows, these lengths have chi laws in dimensions \(d,d-1,\ldots,d-k\). A chi variable in dimension \(v\) has a finite inverse moment of order \(p-1\) whenever \(v>p-1\), as is seen by integrating its density \(c_v t^{v-1}e^{-t^2/2}\) at zero and infinity. The smallest dimension here is \(d-k>p-1\), so iterated conditioning makes the displayed determinant bound integrable.

Set \(H=1\) in the \(r=k+1\) instance. Its right side is the positive constant \((2\pi)^{-(k+1)(p-1)/2}\) times \(\int J^{-(k+1)}d\mu^{\otimes p}\), because the constrained matrix law is a probability. The finite label-side mass proves the claim. This argument is separate from the later logarithmic estimates. ◻

Proof. For each such value of \(A\), on the label side of (173) with \(r=k\), insert the everywhere-defined nonnegative Borel multiplier \[\begin{cases} \displaystyle\frac{\prod_i f_A(s_i)}{\rho_A(X,y)^{p-1}}, &0<\rho_A(X,y)<\infty,\\ 0,&\text{otherwise}. \end{cases}\] The identity applies first to bounded truncations and then to this multiplier by monotone convergence. The label-side measure becomes the actual label law \(\rho_A(X,y)\,dy\) followed by \(p\) normalized posterior draws. The other side is the right side of (175) relative to \(\lambda\). This proves the likelihood formula. In particular, no bounded posterior theorem has been applied to \(f_A\); the only geometric input was the identity for \(\mu\). Values on invalid label fibers are handled by the multiplier itself, so no unproved transfer of a Lebesgue-null set to the singular reference is being used.

We justify logarithmic integrability before taking any entropy difference. Since \(s_i\mid A\) has density \(f_A\), \[\int f_A(\log f_A)_-\,d\mu\le 1/e.\] Together with \(\mathcal D(A)<\infty\), this gives averaged absolute integrability of \(\log f_A(s_i)\). Let \(g\) be standard Gaussian density on \(\mathbb R^k\). For almost every \((A,X)\), \[\int\rho_A(X,y) \left(\log\frac{g(y)}{\rho_A(X,y)}\right)_+dy \le \frac1e\int g(y)\,dy=\frac1e.\] Moreover \(\mathbb E\|Y\|^2=k\), because \(X\) is fresh and \(\|S\|=1\). Since \(-\log g(Y)=\tfrac{k}{2}\log(2\pi)+\tfrac12\|Y\|^2\), the negative part of \(\log\rho_A(X,Y)\) is integrable.

Put \(c=(2\pi)^{-k(p-1)/2}\) and \[Z=c\int J^{-k}\,d\mu^{\otimes p}.\] The \(r=k\) input shows \(0<Z<\infty\). Let \(Q\) be the probability with density \(cJ^{-k}/Z\) relative to \(\lambda\). The likelihood formula gives \(\pi_A\ll\lambda\). Since \(0<J<\infty\) \(\lambda\)-almost surely, the density of \(Q\) is finite and strictly positive there; thus \(Q\) and \(\lambda\) have the same null sets, and \(\pi_A\ll Q\). We may therefore write \[ \log\frac{d\pi_A}{dQ} =\log Z+\sum_{i=1}^p\log f_A(s_i) -(p-1)\log\rho_A(X,Y). \tag{176}\] Its positive part satisfies \[\left(\log\frac{d\pi_A}{dQ}\right)_+ \le |\log Z|+\sum_i(\log f_A(s_i))_+ +(p-1)(\log\rho_A(X,Y))_-,\] so it is integrable by the two bounds just proved, without using \(\log J\). Its negative part has integral at most \(1/e\): if \(v=d\pi_A/dQ\), then \(\int v(\log v)_-\,dQ\le1/e\). Hence \(\mathbb E D(\pi_A\|Q)<\infty\), and the log likelihood in (176) is absolutely integrable on average. Rearranging that identity now proves full integrability of \(\log\rho_A(X,Y)\). This step has not used \(\log J\).

By Lemma 44, \[\int e^{(\log J)_-}\,dQ \le \frac cZ\left( \int J^{-k}\,d\mu^{\otimes p} +\int J^{-(k+1)}\,d\mu^{\otimes p}\right)<\infty.\] For probabilities \(P,Q\) and nonnegative \(F\), exponential tilting gives \[\mathbb E_P F\le D(P\|Q)+\log\mathbb E_Q e^F\] first for bounded \(F\), and then for nonnegative \(F\) by truncation. This is the bounded variational inequality of (Dupuis and Mao 2022, Equations (1.1)–(1.2)), with the limiting step given here. Apply it to \(F=(\log J)_-\) conditionally on \(A\) and average. Its right side is finite. The positive part of \(\log J\) is at most \((p-1)\log2\) by Hadamard’s inequality, since every chord has length at most two. This completes the integrability proof. ◻

Proof. Taking logarithms in (175) is legitimate by Lemma 45. Discard \(X\) by data processing, then condition on \(w\). The latter step adds the conditional mutual information of the tuple and \(w\), at most \(\log W\). The product-reference chain rule, in the finite form discussed in (Austin 2020, sec. 3.3, Equations (13)–(18)), therefore yields \[\begin{align*} \mathbb E D(\mathcal L(\mathbf s\mid A,w)\|\mu^{\otimes p}) &\le \log W+p\mathcal D(A) +(p-1)\mathbb E[-\log\rho_A(X,Y)] \\ &\quad-\frac{k(p-1)}2\log(2\pi)-k\mathbb E\log J. \tag{178}\end{align*}\] The label entropy is bounded by its cross entropy with \(N(Xc_A,r_A^2I_k)\). Freshness and the containing ball give \(\mathbb E(\|Y-Xc_A\|^2/r_A^2\mid A)\le k\), whence \[\mathbb E[-\log\rho_A(X,Y)] \le \frac{k}{2}\log(2\pi)+k\mathbb E\log r_A+\frac{k}{2}.\] All terms are finite by (174) and the preceding lemma. Substitute this estimate and \(\log J=\sum_{i=2}^p\log\delta_i\) into (178). Since \(\log(r_A/\delta_i)\le\Delta_i\), the result is \[\mathbb E D(\mathcal L(\mathbf s\mid A,w)\|\mu^{\otimes p}) \le \log W+p\mathcal D(A)+\frac{k(p-1)}2 +k\mathbb E\sum_{i=1}^p\Delta_i.\] This finite relative entropy also implies that, almost surely, each conditional coordinate law given its predecessors is absolutely continuous with respect to \(\mu\). The product-reference chain rule and the uniform choice of \(I\) give the exact identity \[\mathcal D(A_*) =\frac1p\,\mathbb E D\!\left( \mathcal L(\mathbf s\mid A,w)\middle\|\mu^{\otimes p}\right).\] Dividing the preceding bound by \(p\) and using \((p-1)/p\le1\) gives (177). ◻

Proof. If \(I=1\), set \(j=0\). For \(I\ge2\), set \[j=\max\{0,\lfloor\log_2(r_A/\delta_I)\rfloor\}.\] When \(j=0\), keep the old ball. When \(j\ge1\), the predecessor span has dimension \(v=I-2\) almost surely. Use orthonormal coordinates in that affine span based at \(s_1\). The projection of \(s_I-s_1\) has norm at most \(2r_A\), because both points lie in the old ball.

For every integer pair \((j,v)\), fix an ordered \(2^{-j}\)-net of the radius-two ball in \(\mathbb R^v\) with at most \((1+4\cdot2^j)^v\) points. A maximal \(2^{-j}\)-separated set has this size by comparing the volumes of its disjoint radius-\(2^{-j-1}\) balls with the containing ball. In dimension zero use one point. Record the first net point within \(2^{-j}\) of the projection coordinates divided by \(r_A\). After scaling and translating back, let \(c'\) be that point of the predecessor span. The in-span error and perpendicular error are both at most \(r_A2^{-j}\). Hence \(B(c',2r_A2^{-j})\) contains \(s_I\); set \(r'=2r_A2^{-j}\). It is at most \(r_A\) for \(j\ge1\).

Figure 1 depicts this step, writing \(\eta=r_A2^{-j}\) and \(F=\operatorname{aff}(s_1,\ldots,s_{I-1})\) within the illustration. Only the \(v\)-dimensional projection must be encoded; the perpendicular error is absorbed by the decoded radius. The radius does not increase, but the balls need not be nested.

For \(j\ge1\), \(j\log2\le\Delta_I<(j+1)\log2\). Thus \[\log r_A-\Delta_I\le \log r' \le\log r_A-\Delta_I+2\log2.\] For \(j=0\), either \(\Delta_I=0\) or \(\Delta_I<\log2\), and the same upper bound holds with \(r'=r_A\). These inequalities give (179) and, using the finite expectations already proved, \(\mathbb E|\log r'|<\infty\).

Encode \(j\) by the unary prefix code of length \(j+1\) bits. For \(j\ge1\), append a fixed-length net index of \(\lceil v\log_2(1+4\cdot2^j)\rceil\) bits. Given \(A_*\), the dimension \(v\) is known, so the combined code is prefix-free. Since \(1+4\cdot2^j\le5\cdot2^j\), its length is at most \((1+v)j+C v+2\). Now \(1+v\le p\) and \(j\log2\le\Delta_I\), so its expected length in nats is at most \(p\mathbb E\Delta_I+C_1p\). We give the countable conditional entropy step explicitly. For a conditioning value \(a_*\) with finite conditional expected length, let \(\ell_{a_*}(c)\) be the bit length and let \(p_{a_*}(c)\) be the conditional code distribution. Kraft’s inequality (Kraft 1949), in the finite or countable form stated in (Duchi 2023, sec. 2.4.2, Theorem 2.4.2), gives \[0<K_{a_*}:=\sum_c2^{-\ell_{a_*}(c)}\le1.\] Normalize \(q_{a_*}(c)=2^{-\ell_{a_*}(c)}/K_{a_*}\). Its cross entropy is \[\sum_c p_{a_*}(c)\log\frac1{q_{a_*}(c)} =(\log2)\mathbb E[\ell_{a_*}(C)\mid a_*]+\log K_{a_*} \le(\log2)\mathbb E[\ell_{a_*}(C)\mid a_*]<\infty.\] For a finite partition of the code alphabet with one remaining tail atom, nonnegative relative entropy bounds the partition entropy by its \(q_{a_*}\) cross entropy, and that cross entropy is at most the displayed full cross entropy. Refining such partitions gives the countable entropy by monotone convergence. Hence \(H(C\mid a_*)\le(\log2)\mathbb E[\ell_{a_*}(C)\mid a_*]\). Finite conditional expected length holds for almost every \(a_*\) because its average is finite. Averaging proves the first inequality in (180).

Gram–Schmidt with fixed conventions supplies measurable orthonormal coordinates from the predecessor differences, and the fixed ordering resolves net ties. Define the code arbitrarily on the null degeneracy set. The decoded ball is therefore measurable. The pointwise construction puts \(s_I\) in that decoded ball outside the null degeneracy set. The event \(\{\|s_I-c'(A')\|\le r'(A')\}\) is Borel and has probability one. Disintegrating it over \(A'\) shows that its conditional probability is one for almost every \(A'\). Thus the decoded ball supports the conditional signal law. Conditioning an absolutely continuous law on a discrete code keeps absolute continuity almost surely. The conditional entropy chain rule gives the second inequality in (180), and its finite right side proves the remaining finiteness claim. ◻

Proof. Condition on the shared rule randomness. For almost every value, the joint initialization independence in Section 2 leaves the initial state independent of the signal and all sample rows. By Lemmas 1 and 2, the conditional uniform-prior experiment has Borel rule versions. We prove the displayed numerical bound for each such value, with its conditional success probability. Averaging that bound at the end handles shared randomness without requiring jointly selected Borel versions.

Pad an early-stopping program to \(T\) observations by retaining its terminal state and stopping index, and then ignoring the remaining pairs. At each index the padded state has at most \(W\) values, and the final output law uses only that state. Divide the observations into blocks of length \(K\), allowing a shorter final block. Set \[a=K+p,\qquad \Phi(A,r_A)=\mathcal D(A)+a\mathbb E\log r_A.\] For every nonempty block length \(1\le k\le K\), the inequalities \(k+p+1<d\) and \(a\le(d-1)/2\) hold once \(d\) is sufficiently large. Initially \(A\) is the signal-independent initial state and the containing ball is \(B(0,1)\), so \(\Phi=0\).

At a block, select a replica and encode its new ball as above. Combining (177)–(180) gives \[\begin{align*} \Phi(A',r') &\le\Phi(A,r_A)+\frac{\log W}{p}+\frac{k}{2}+C_1p+2a\log2 +(k+p-a)\mathbb E\Delta_I \\ &\le\Phi(A,r_A)+C_2d. \tag{182}\end{align*}\] Indeed \(k+p-a\le0\), while \(p\ge d/16\) and \(\log W\le2d^2\) make the width charge \(O(d)\). The cancellation has a direct explanation: the likelihood charges \(k\Delta_I\), the code charges at most \(p\Delta_I\), and the radius credit is \(a\Delta_I=(K+p)\Delta_I\).

Every posterior draw has the correct joint marginal with the block destination. Uniformly selecting one draw therefore preserves the learner’s state–signal marginal, and recording its code changes no marginal law. Generate the next Gaussian block independently of the pair consisting of the current signal and augmented analysis variables. Since the learner’s transition uses the past only through its state, induction preserves the actual state–signal marginal at every boundary. The predecessor points and codes are never given to the learner. All required finiteness properties propagate by Lemma 47. Thus after \(b=\lceil T/K\rceil\) blocks, \[\Phi\le C_2db.\] For \(T=0\) this holds directly with \(b=0\).

Write \(n=d-1\). Lemma 3 gives \(\mu(B(c_A,r_A))\le(2r_A)^n\). A density supported in a set \(E\) has relative entropy at least \(-\log\mu(E)\), by comparison with \(\mu(\,\cdot\mid E)\). Therefore \[D(f_A\mu\|\mu)\ge-n\log(2r_A)\] almost surely, and \[ \Phi\ge\left(1-\frac an\right)\mathcal D(A)-a\log2 \ge\frac12\mathcal D(A)-a\log2. \tag{183}\] The unconditional signal law remains \(\mu\), so \(\mathcal D(A)=I(S;A)\). The final \(A\) includes the padded state \(w\), and hence \(\mathcal D(A)\ge I(S;w)\).

Under the product of \(\mu\) and the output marginal, angular success has probability at most \(\epsilon^n\), by Lemma 3. Data processing through the terminal output and then through the success event gives \[I(S;w)\ge I(S;\widehat S) \ge \pi n\log(1/\epsilon)-\log2\] by (1). This holds with the success probability for the fixed shared seed. Combining it with the potential upper bound and (183) proves (181) with constants independent of that seed. Averaging proves the asserted bound for the original shared randomness as well. ◻

Proof. Put \(L=\log(1/\epsilon)\ge\log10\). The last statement follows by averaging over the uniform signal, so it suffices to prove the average statement. There are at most \((T+1)2^M\) terminal time–state pairs. For each fixed pair its fresh output law succeeds on uniform mass at most \(\epsilon^{d-1}\), by the cap bound and integration over that output law. More explicitly, for a terminal pair \(h\) let \(a_h(s)\) be that fixed output law’s success probability at signal \(s\), and let \(t_h(s)=\Pr(h\text{ is reached}\mid S=s)\). The pair’s contribution is \[\int t_h(s)a_h(s)\,\mu(ds) \le\int a_h(s)\,\mu(ds)\le\epsilon^{d-1},\] because \(0\le t_h(s)\le1\). Summing over all pairs, for almost every shared seed and hence after averaging, yields \[\frac23\le (T+1)2^M\epsilon^{d-1}.\] Equivalently, \[ (d-1)L\le M\log2+\log(T+1)+\log(3/2). \tag{184}\]

At indices where \(T\ge dL\) the conclusion is immediate. At the other indices, (184) gives \[(d-1)L\le M\log2+\log(dL+1)+\log(3/2).\] For all sufficiently large \(d\), uniformly for \(L\ge\log10\), \(\log(dL+1)\le dL/6\), while \((d-1)L\ge dL/2\). Consequently \(dL\le3M\log2+3\log(3/2)=o(d^2)\) along such short indices. In particular \(\log((T+2)2^M)\le2d^2\) eventually, so Proposition 48 applies. It gives \[T\ge K\{c_0L-C_0-1\}\] with absolute \(c_0>0,C_0\). Above a sufficiently large absolute threshold for \(L\), use \(K\ge d/16\) and absorb the constants to obtain \(T\ge c_1dL\).

For completeness, the local full-data argument supplies the remaining constant-accuracy range with explicit constants. If \(T\le d/8\), reveal every row and label. The conditional unknown component is uniform on a residual sphere of radius \(R\). By isotropy and Markov’s inequality, \[\Pr\{R<1/2\}\le \frac{4T}{3d}\le\frac16.\] On \(R\ge1/2\), antipodal residual points correspond to signals separated by at least one, so a radius-\(\epsilon\) error ball with \(\epsilon\le1/10\) contains at most one point of each pair. Conditional success is at most \(1/2\), also for a randomized estimate. Total success is at most \[\frac16+\frac56\cdot\frac12=\frac7{12}<\frac23.\] Thus \(T>d/8\). This proves \(T\ge c_2dL\) throughout the bounded range of \(L\) left above. Taking the minimum of the absolute constants completes the proof, including nonmonotone accuracy sequences and early stopping. ◻

Proof. Writing \(H_g=(gg^{\mathsf T})^{1/2}\), an orthogonal change of coordinates and a nonsingular change of label coordinates give \[p_\sigma(g,y)= \frac{c_{d,\ell}}{\det(gg^{\mathsf T})^{1/2}} \left(1-\|H_g^{-1}y\|^2\right)^{(d-\ell-2)/2} \mathbf 1_{\{\|H_g^{-1}y\|<1\}}.\] The spherical coordinate formula follows by splitting a normalized standard Gaussian into its \(\ell\) row-space coordinates and the remaining coordinates: the squared projected length is \(\operatorname{Beta}(\ell/2,(d-\ell)/2)\). Domination proves absolute continuity for \(\nu\). Lebesgue differentiation proves the claim about cube limits, and their defining integrals are jointly Borel.

Under \(G\otimes\sigma\), the logarithm in the displayed formula is integrable. The beta density has integrable logarithms at its two endpoints. Gram–Schmidt expresses \(\det(GG^{\mathsf T})\) as a product of chi-square variables of positive degrees, each with integrable logarithm. Domination by \(H\) preserves this baseline integrability for \(S\sim\nu\). The projected likelihood ratio \(p_\nu/p_\sigma\) has relative entropy at most \(D(\nu\|\sigma)\le\log H\) by data processing. Its negative logarithmic part has expectation at most \(1/e\), since \(t\log^-(t)\le1/e\) under the probability reference. Its positive part is then finite as well. This proves the first integrability assertion.

For a positive-probability \(w\), the actual law of \((G,S)\) given \(w\) is dominated by \(P(W=w)^{-1}\) times \(G\otimes\sigma\). Its image therefore has a density, and the baseline logarithm is integrable; averaging over \(w\) restores its original finite expectation. The log ratio of the actual image density to \(p_\sigma\) has relative entropy \(I(W;GS\mid G)\le H(W)\) and negative part at most \(1/e\). Thus the actual log density is integrable. Moreover, \[\mathbb ED(P_{S\mid G,W}\|\nu_W)=I(S;G\mid W)\le H(W),\] where the last inequality uses \(I(S;G)=0\) and the chain rule. Data processing under \(s\mapsto Gs\) gives integrability of the log ratio between the actual image density and \(p_{\nu_W}\); subtracting it proves the remaining claim. If a finite entering variable is first fixed, its signal law is bounded relative to \(\sigma\), and the same argument applies to each positive-probability case and then to their finite average. ◻

Proof. For \(r_i=2^{1-i}\), let \(m_i(s)=\nu(B(s,r_i))\). Dyadic shells give \[J_\nu(s)\le 2^p\sum_{i\ge0}r_i^{-p}m_i(s).\] Since \(m_i(s)\le H(2r_i)^n\) and \(n-p\ge1\), choosing \(C_0\) large makes the sum over \(i>b_H\) at most \(2^{-p}\). The term \(i=0\) is itself \(2^{-p}\). Choose the first maximizer \(j=j(s)\le b_H\). This is measurable and satisfies \[\log(r_j^{-p}m_j(s)) \ge\log J_\nu(s)-Cd-\log(b_H+2).\]

For fixed \(X\), compare the actual projected density to \[Q_X(y)=\frac1{b_H+1}\sum_{i=0}^{b_H} \int \gamma_{r_i}(y-Xu)\,d\nu(u),\] where \(\gamma_r\) is the \(N(0,r^2I_p)\) density. At \(y=Xs\), retain the \(j\)-summand and restrict it to \(B(s,r_j)\). Jensen’s inequality for the logarithm on that normalized restriction and \(\mathbb E_X\|X(s-u)\|^2=p\|s-u\|^2\le pr_j^2\) give \[\mathbb E_X\log Q_X(Xs) \ge\log(r_j^{-p}m_j(s))-\log(b_H+1) -\tfrac p2\log(2\pi)-\tfrac p2.\] Integrate over \(s\). The comparison density has finite cross entropy by this bound and its finite Gaussian-mixture upper bound. The actual differential entropy is finite by Lemma 51. Nonnegativity of relative entropy to \(Q_X(y)\,dy\) proves the result. ◻

Proof. For \(s\in B(z,r)\), \(J_\nu(s)\ge(2r)^{-p}\nu(B(z,r))\). Integrating its reciprocal over the ball proves the first inequality; if the ball has zero \(\nu\)-mass there is nothing to prove. The second uses \(J_\nu\ge2^{-p}\).

Apply Theorem 53 with \(m=r=q=k\), \(\ell=p=2k\), \(B=2^p\), and \(D=2^{p+n}H\), using the ambient-center cap bound of Lemma 3. The angular margin is exactly \(p-k-(k-1)=1\), and the radial margin is \(n-p>0\). Moreover \(1+\log^+(D/B)\le C(d+1+\log H)\le C(b_H+2)\); the factor \(2^p\) is absorbed in \(e^{Cd}\). This proves (186). The local inverse factor behind this substitution is \(\|u-s\|^{-k}\mathop{\mathrm{dist}}(u-s,E)^{-k}\), where \(E\) is a linear subspace with \(\dim E\le k-1\). ◻

Proof. Condition first on \(V=v\) with positive probability. Put \(\nu=P_{S\mid v}\) and \(H_v=P(V=v)^{-1}\). In this conditional experiment \(w\) always ranges over values with \(P(V=v,W=w)>0\); for these values put \(\nu_w=P_{S\mid v,w}\) and \(H_{vw}=P(V=v,W=w)^{-1}\). The two posteriors are bounded by \(H_v\sigma\) and \(H_{vw}\sigma\). Introduce a \(k\)-row Gaussian matrix \(A'\) independent of \((S,V,A,W)\), and put \(X=(A;A')\), \(Y=XS\). Within the conditional experiment \(X\) is independent of \(S\), and \(W\) depends on \(S\) only through \((X,Y)\). The chain rule gives \[ I(S;W)=h(Y\mid X)-h(Y\mid X,W)-I(X;S\mid W). \tag{187}\] For example, \(I(S;W)=I(X,Y;W)-I(X;W\mid S)\), and \(I(X;S)=0\) converts the difference of the two row-information terms into \(-I(X;S\mid W)\). All displayed differential entropies are finite by Lemma 51, and \(I(X;S\mid W)\le H(W)\).

For fixed \(w\), use the finite nonzero measure \(\rho_w=\nu_w/J_{\nu_w}\) as a reference, and write \(a_w=\rho_w(S^{d-1})\). First normalize this reference. The relative entropy of the actual conditional law of \((X,S)\) with respect to \(P_{X\mid w}\otimes(\rho_w/a_w)\) is \[I(X;S\mid w)+B(\nu_w)+\log a_w<\infty.\] Indeed, \(\log J_{\nu_w}\) is bounded for this \(v,w\), and \(I(X;S\mid w)<\infty\). Probability data processing under \((X,s)\mapsto(X,Xs)\) makes the corresponding post-map relative entropy finite. For probability laws \(P\ll Q\), the elementary bound \[\int_{\{dP/dQ<1\}}-\log(dP/dQ)\,dP\le 1/e\] shows that a finite relative entropy has an integrable log density ratio. The post-map ratio is the actual conditional label density divided by \(p_{\rho_w}(X,Y)/a_w\). Its logarithm is therefore integrable. Lemma 51 makes the logarithm of the actual conditional label density integrable as well, so \(\log p_{\rho_w}(X,Y)\) is integrable under the actual conditional law. Here \(p_{\rho_w}\) is the cube-limit density version; the same construction applies to a finite measure.

We may now expand both finite-reference divergences and subtract \(\log a_w\) from probability data processing. Before the map the divergence is \(I(X;S\mid w)+B(\nu_w)\), while after the map it is \(-h(Y\mid X,w)-\mathbb E[\log p_{\rho_w}(X,Y)\mid w]\). Consequently, \[ -h(Y\mid X,w)-I(X;S\mid w) \le B(\nu_w)+\mathbb E[\log p_{\rho_w}(X,Y)\mid w]. \tag{188}\] This is precisely the finite-reference data-processing statement proved in Section 2, including when \(\rho_w\) has mass greater than one.

We now bound the last logarithm under the selected actual rows. Let \(Q\) be the original Gaussian law of \(A\), still conditional on \(v\), and write \(\kappa_w(a,as)\) for the Borel block probability of message \(w\). For \(r_w(s)=\int\kappa_w(a,as)\,Q(da)>0\), choose the conditional row law \[Q_{s,w}(da)=\frac{\kappa_w(a,as)}{r_w(s)}\,Q(da);\] when \(r_w(s)=0\), assign \(Q_{s,w}=Q\). The normalizer is positive for almost every \((s,w)\) under the actual law, and this is a conditional version of the row law there. In particular \(Q_{s,w}\ll Q\). Also \[\mathbb E_{s,w}D(Q_{s,w}\|Q)=I(A;W\mid S)\le H(W)\le\log N,\] so the divergence is finite for almost every \((s,w)\) under that law. The fresh \(A'\) retains its independent Gaussian law after conditioning on \((A,s,w)\). For almost every such pair and for \(\delta>0\), Jensen in \(A'\), followed by (2) with exponent \(k\), gives \[\begin{align*} &\mathbb E[\log(1+p_{\rho_w,\delta}(X,Xs))\mid s,w]\\ &\quad\le\frac{D(Q_{s,w}\|Q)}k+ \frac1k\log\mathbb E_{A\sim Q} \left(1+\mathbb E_{A'}p_{\rho_w,\delta}(X,Xs)\right)^k\\ &\quad\le\frac{D(Q_{s,w}\|Q)}k+Cd+\log(b_{H_{vw}}+2). \tag{189}\end{align*}\] The last step uses the \(L^k\) triangle inequality and (186), whose fresh moment holds for every fixed \(s\in S^{d-1}\). The displayed row-charge inequality is used only for almost every \((s,w)\) under the actual law, while \(\delta\) is positive.

Here is the exact null-set transfer in that passage. For each full-rank \(X\), Lebesgue differentiation makes \(p_{\rho_w,1/a}(X,y)\) converge to \(p_{\rho_w}(X,y)\) for Lebesgue-almost every \(y\). The failure set is jointly Borel by the cube definitions. Under the actual conditional law given \((v,w)\), \((X,S)\) is dominated by a finite multiple of \(\gamma_p\otimes\sigma\); pushing forward shows that \((X,Y)\) is absolutely continuous with respect to \(\gamma_p(dX)\,dy\). Consequently it avoids this failure set, including after the actual rows have been tilted by \(w\). Fatou applied to the nonnegative \(\log(1+p_{\rho_w,1/a}(X,Y))\), after integrating (189) over \(s,w\), proves the same integrated upper bound for \(\log(1+p_{\rho_w}(X,Y))\), and hence for \(\log p_{\rho_w}\). This argument does not invoke an unsmoothed moment at \(\rho_w\)-almost every fixed signal.

The preceding estimate supplies the quantitative positive-log bound; integrability of both signs was established before (188). Substituting Lemma 52 and (188)–(189) into (187), and using \(I(S;W)=\mathbb E_wD(\nu_w\|\sigma)-D(\nu\|\sigma)\), yields \[\mathbb E_w\Phi(\nu_w)\le\Phi(\nu)+Cd+2\log(b_{H_v}+2) +\mathbb E_w\log(b_{H_{vw}}+2)+\frac{\log N}{k}.\] Restore the average over \(v\). \(\mathbb E\log H_V=H(V)\le\log N\) and \(\mathbb E\log H_{VW}=H(V,W)\le2\log N\). Jensen bounds the averaged cutoff terms by \(C\log(d+1+2\log N)\), while \(\log N/k\le Cd\). For fixed \(w\), \(P_{S\mid W=w}\) is the finite mixture of \(\nu_w=P_{S\mid v,w}\) over \(v\). Lemma 50 permits forgetting \(v\), proving the drift. ◻

Proof. Fix the shared rule randomness with uniform-prior success at least \(2/3\), and apply Lemmas 2 and 1. Keep the internal transition and output randomness. Put \(L=\log(1/\epsilon)\). Under the product of the marginal laws of \((S,\widehat S)\), angular success has probability at most \(\epsilon^{d-1}\), by Lemma 3. Equation (1) therefore gives \[ I(S;\widehat S)\ge\tfrac23(d-1)L-\log2. \tag{190}\]

Assume \(T<dL\). The other case is already sufficient. The terminal state and stopping index have at most \((T+1)2^M\) values, so the left side of (190) is at most \(M\log2+\log(T+1)\). Since \(\log(T+2)\le C+\log d+\log(L+1)\le C+\log d+L\), absorption gives \[L\le C\frac{M+1+\log d}{d},\qquad T=O(d+M).\] For \(M=o(d^2)\), pad stopped states with their original terminal labels and indices and add unused rows to complete the last block. Every padded layer has at most \(N=(T+2)2^M\) states and \(\log N=o(d^2)\).

The initial conditional signal law is \(\sigma\), because the model makes initialization independent of the signal conditional on the fixed shared rule randomness. Iterate Proposition 55 for \(\lceil T/k\rceil\) blocks and apply Lemma 50. For the final padded state \(F\), \[I(S;F)=\mathbb ED(P_{S\mid F}\|\sigma) \le Cd\bigl(1+\lceil T/k\rceil\bigr).\] The output is generated from \(F\) and fresh randomness. Data processing with (190) gives \(L\le C(1+T/d)\). The \(2/3\) instance of Lemma 3 gives \(T>d/4\) for this same prior and exact observation model. Thus \(1+T/d\le5T/d\), proving the claimed sample bound. The global-clock calculation controls only the padded width; the precision-dependent conclusion comes from the block drift. ◻

Proof. For the selected cell \(C\), \[\log m_{\mu_v}(U) \le \frac{\alpha}{d-1}\log\frac{p_C}{\sigma(C)}+\alpha\log 2,\] using \(\sigma(C)\le (2r_j)^{d-1}\) and \(\log p_C\le 0\). The log ratio here is at most \(\log(p_D/\sigma(D))+\log(p_C/p_D)\). The expected first term is at most \(I_V\) by relative entropy under the partition for each \(v\); (191) bounds the other term. Since \(\alpha/(d-1)=1/2\), the correction removes at most half the information, up to an additive \(O(d)\). ◻

Proof. The volume is positive almost surely, since \(\nu\) gives zero mass to affine spaces of dimension \(i<\alpha\). This last fact follows by covering any bounded portion by \(O(r^{-i})\) balls of radius \(r\) as \(r\downarrow 0\), and suffices by conditioning successively on the previous draws.

We order the vectors \(z_i-u\) greedily, taking at each step one of largest distance to the span of those preceding. Every tuple admits such an ordering. By exchangeability, it suffices to bound the expectation restricted to the original order being greedy and multiply by \(k!\); this also allows ties. In this order let \(\delta_i\) be the distance to the preceding span, with the norm used for the first vector. Then \(S=\prod_i\delta_i\), and the distances are nonincreasing. Fix their length bins \[2^{-\ell_i-1}<\delta_i\le 2^{-\ell_i},\qquad \ell_1\le\cdots\le\ell_k,\quad \ell_i\in\mathbb Z.\] We will first bound the probability of these bins and the greedy conditions, then sum their contributions to the inverse volume.

Given the first \(i-1\) draws, let \(e_j\), \(j<i\), be their translated vectors’ successive Gram–Schmidt axes. Group these axes according to \(h=\ell_j\). Greediness forces the projection of \(z_i-u\) onto each group to have norm at most \(2^{-h}\): before the first axis in that group was chosen, the residual norm of \(z_i-u\) was no greater than the distance chosen at that step. Its residual norm after all preceding axes is at most \(2^{-\ell_i}\).

In a group of dimension \(a_h\), cover the ball of radius \(2^{-h}\) by a net of radius \(2^{-\ell_i}2^{-(\ell_i-h)}\). Euclidean ball packing bounds its cardinality by \((3\cdot 2^{2(\ell_i-h)})^{a_h}\). The distinct group indices are integers \(h\le\ell_i\), so their squared net errors sum to at most \[2^{-2\ell_i}\sum_{h\le\ell_i}2^{-2(\ell_i-h)} =\tfrac43\,2^{-2\ell_i}.\] Including the orthogonal residual, all allowed points \(z_i\) therefore lie in at most \(3^{i-1}2^{2\sum_{j<i}(\ell_i-\ell_j)}\) ambient balls of radius \(2\cdot2^{-\ell_i}\). These necessary constraints involve only the preceding draws and the fixed bins. The local ball bound gives their conditional probability at most \[3^{i-1}2^\alpha\, 2^{2\sum_{j<i}(\ell_i-\ell_j)-\alpha\ell_i}.\]

We may multiply these bounds sequentially, imposing only the necessary constraints just described and never conditioning preceding draws on future greedy choices. Use the local estimate when \(\ell_i\ge0\) and probability one otherwise. Put \[P=\sum_i\max(\ell_i,0),\qquad N=\sum_i\max(-\ell_i,0).\] The double sum in the product exponent satisfies \[\sum_{i:\ell_i\ge0}\sum_{j<i}(\ell_i-\ell_j) \le \sum_{i:\ell_i\ge0}\left(k\ell_i+ \sum_{j:\ell_j<0}(-\ell_j)\right) \le k(P+N).\] Indeed, each inner sum is \((i-1)\ell_i-\sum_{j<i}\ell_j\). Its first term is at most \(k\ell_i\), subtracting nonnegative \(\ell_j\) can only decrease it, and each negative index contributes at most \(k\) times. The probability of the greedy and length conditions is consequently at most \[\exp(Cdk)\,2^{-(\alpha-2k)P+2kN}.\]

On these bins, \(S^{-n}\le2^{nk}2^{n(P-N)}\). When negative bins dominate, the large distances already make this inverse volume small; otherwise the local probability bound supplies the needed decay. For \(N\le2P\), combining the two bounds gives the exponent \[-(\alpha-2k-n)P+(2k-n)N \le -(\alpha-6k-n)P-nN\le -(P+N),\] since \(\alpha-6k-n\ge3\) and \(n\ge3\) for large \(d\). For \(N>2P\), use probability at most one: then \(n(P-N)\le -(P+N)\), because \((n+1)P\le(n-1)N\) for \(n\ge3\). Thus either region contributes at most \(\exp(Cdk)2^{-(P+N)}\). The sum of \(2^{-(P+N)}\), even over all integer tuples, is \(3^k\). This factor and \(k!\) are absorbed by \(\exp(Cdk)\), proving (194) at arbitrary length scales. ◻

Proof. Take \(k\) independent draws from \(\eta/q\). By (193), scaling the space (also scaling \(u\)) by \((C^d m_0/q)^{1/\alpha}\) makes (194) applicable. In the original space the bound for \(\mathbb E S^{-n}\) is multiplied by \((C^d m_0/q)^{kn/\alpha}\). For fixed draws, the probability that all \(\|A(z_i-u)\|_\infty\le a\) is bounded by \((2a)^{nk}(2\pi)^{-nk/2} S^{-n}\), by the maximum Gaussian density in \(k\) coordinates for each row. The \(A\)-expectation of the cube mass to the power \(k\) is \(q^k\) times the draws’ average of this event probability. Thus we get (195) for the mass divided by \((2a)^n\) in place of the density. Fatou’s lemma proves it for the liminf. Constants use that \(n/\alpha\) is bounded. ◻

Proof. Conditional on \(V,D,A,b,W\), the density of \(U\) relative to \(\lambda_{A,b}\) is \[f_v{\bf 1}_D\, g_{0,A}(b)/g_{v,D,A}(b),\] since the message given \(V,A,b\) no longer depends on \(U\). Compare on this fiber with the subprobability density \[\sum_{t'} \frac{q_{Dt'}}{q_D}\, f_w{\bf 1}_{D,\ t'}\, g_{0,A}(b)/g_{w,D,t',A}(b)\] where zero-denominator terms are omitted, and the indicator restricts to the specified bin of \(m_{\mu_w}\) as well as to \(D\). Each included fiber density before its mixing weight has integral one. Omitting bins can only reduce the total mass, so the displayed mixture is a subprobability.

On the actual draw, the term of its bin has positive denominator almost surely. Indeed, a zero denominator with \(g_{0,A}(b)>0\) makes \(f_w{\bf 1}_{D,\ t'}\) zero \(\lambda_{A,b}\)-almost everywhere. The actual conditional law is absolutely continuous on the fiber, and \(f_w(U)>0\) almost surely. The log ratio of the true density to the comparison density is therefore \[\log\frac{f_v(U)}{f_w(U)} +\log\frac{g_{w,D,t,A}(b)}{g_{v,D,A}(b)} -\log\frac{q_{Dt}}{q_D}.\] The last term averages to \(H(t\mid W,D)\). Once integrability is verified, the nonnegative expectation of this log ratio gives (198), by Jensen on each fiber against the subprobability.

We verify the logarithmic integrability needed here and in (197). The log densities \(\log f_V(U)\) and \(\log f_W(U)\) are integrable by the state probability bounds and \(x\log^-x\le1/e\) for densities relative to a probability. Both projection densities have integrable positive log parts: they are bounded above by \(g_{0,A}/p_v\) or \(g_{0,A}/p_w\), and \[g_{0,A}\le c_{d,n}\det(AA^\top)^{-1/2}\] has integrable positive log part. For this last assertion, Gram–Schmidt on Gaussian rows gives squared successive distances with conditional chi-square laws and integrable logarithms.

For the incoming density \(g_{v,D,A}\), the Gaussian comparison also bounds the negative log part. A log density ratio under its numerator law has expected negative part at most \(1/e\) when compared to a probability. The Gaussian comparison density has integrable negative log part by \(r\le2\) and the squared norm estimate, while \(-\log p_D\) has finite expectation. Thus \(\log g_{v,D,A}(b)\) is integrable.

The displayed fiber log ratio now has integrable positive part, using the outgoing positive log bound, the incoming integrability, and the finite expected surprisal for \(t\mid W,D\). Its expected negative part is at most \(1/e\), which remains true for comparison with a subprobability. The log ratio is therefore integrable, and its displayed decomposition also gives integrability of \(\log g_{w,D,t,A}(b)\). This justifies (198). ◻