Proof. Consider probability laws on \(S^T\times TS\), with coordinates \((X^T,Z)\), having uniform one-letter marginals. Minimize \[T\mathrm H(U_S)-\mathrm H(X^T\mid Z) +\mathbb E c\!\left(Z-\sum_iX_i\right).\] The feasible set is a nonempty compact polytope. Conditional entropy is continuous on finite probability simplices, including their boundaries, so the minimum is attained. It is a convex minimization problem because conditional entropy is concave in the joint law and the other terms are linear or constant.

We give the dual formula, including the marginal constraint. For a tuple \(\boldsymbol\mu=(\mu_1,\ldots,\mu_T)\) of probability laws on \(S\), let \(f(\boldsymbol\mu)\) be the minimum of \(-\mathrm H(X^T\mid Z)+\mathbb E c(Z-\sum_iX_i)\) with these marginals. It is finite everywhere on the product of simplices: a product law for the letters and any fixed \(z\in TS\) is feasible and has finite cost. It is convex by mixing feasible laws. At the tuple of uniform laws, a relative interior point of this product, the finite convex function \(f\) has a supporting affine function. Equivalently, separating its epigraph from points strictly below its value yields finite multipliers for the marginal constraints. Therefore there is no duality gap, and the desired minimum equals \[ \begin{split} T\mathrm H(U_S)+\sup_{a_1,\ldots,a_T:S\to\mathbb R} \left\{\sum_{i=1}^T\mathbb E_{U_S}a_i -\log\max_{z\in TS} \sum_{\boldsymbol x\in S^T} e^{\sum_i a_i(x_i)} H_q\!\left(z-\sum_i x_i\right)\right\}. \end{split} \tag{9}\] To check the expression inside this dual, set \[B_z=\sum_{\boldsymbol x\in S^T} e^{\sum_i a_i(x_i)}H_q\!\left(z-\sum_i x_i\right)>0.\] For a conditional law \(\pi\) of \(X^T\) given \(Z=z\), its entropy and cost, after subtracting the multipliers, equal \[\sum_{\boldsymbol x}\pi(\boldsymbol x) \log\frac{\pi(\boldsymbol x)}{ e^{\sum_i a_i(x_i)}H_q(z-\sum_i x_i)} =D(\pi\|B_z^{-1}e^{\sum_i a_i}H_q(z-\textstyle\sum_i x_i)) -\log B_z.\] The minimum is \(-\log B_z\), attained at the displayed normalized Gibbs law. The remaining optimization over the distribution of \(Z\) selects a maximizer of \(B_z\), giving \(-\log\max_z B_z\) as in [entropy-foundations:dual].

The dual objective is concave in the tuple \((a_1,\ldots,a_T)\): the negative logarithm in [entropy-foundations:dual] is the negative of a maximum of convex log-sum-exponential functions. The objective is also invariant under coordinate permutations. Averaging over all such permutations can only increase it. Hence it suffices to consider \(a_i=a\) for every \(i\). Write \[A_a=\sum_{x\in S}e^{a(x)},\qquad \lambda(x)=e^{a(x)}/A_a.\] For these multipliers, the full expression in [entropy-foundations:dual] is \[-T D(U_S\|\lambda) -\log\max_{z\in TS} \mathbb E_{\lambda^{\otimes T}} H_q\!\left(z-\sum_iX_i\right).\] The maximum is at least its average when \(z\) is the sum of an independent \(T\)-tuple with law \(\lambda\). That average is at least \(e^{-E}\) by [entropy-foundations:moment-hypothesis]; the two independent tuples can be interchanged to obtain the sign convention there. Since relative entropy is nonnegative, the displayed dual value is at most \(E\). This proves the same upper bound for the primal minimum.

Finally average a minimizing joint law of \((X^T,Z)\) over all permutations of \(X^T\). Convexity preserves the upper bound, and both the constraints and the cost are permutation invariant. Define \(\Gamma=Z-\sum_iX_i\in TS-TS\). The identity \[D(X^T\|U_S^{\otimes T})+\mathrm I(X^T;Z) =T\mathrm H(U_S)-\mathrm H(X^T\mid Z)\] then gives [eq:source-1] and the required exchangeability, including the error variable. ◻

Proof. For (i), write \(B\) and \(O\) for the kept and omitted vectors, and let \(Z_B=Z-\sum O\). The cross entropy with respect to the product comparison separates over \(B,O\). Also \[\mathrm H(B\mid Z_B)\ge\mathrm H(B\mid Z,O).\] It follows from the chain rule that \[\begin{align*} \mathcal C_p(B,O;\Gamma)-\mathcal C_p(B,\Gamma) &=\mathbb E[-\log p^{\otimes |O|}(O)] -\mathrm H(B,O\mid Z)+\mathrm H(B\mid Z_B)\\ &\ge\mathbb E[-\log p^{\otimes |O|}(O)]-\mathrm H(O\mid Z) \ge0. \end{align*}\] The last inequality follows by first removing the conditioning on \(Z\) and then using nonnegativity of \(D(O\|p^{\otimes |O|})\). Reordering does not change either the sum or the product comparison.

For (ii), the cross entropy and error cost are unchanged after averaging conditional laws, whereas the conditional entropy becomes \(\mathrm H(X^s\mid Z,J)\). Thus the exact average increase is \[ \sum_j\mathbb P(J=j)\mathcal C_p(X^s,\Gamma\mid J=j) -\mathcal C_p(X^s,\Gamma) =\mathrm I(X^s;J\mid Z)\le\mathrm H(J). \tag{11}\] This argument does not impose independence on \(J\): it may depend on the letters, the error, and additional randomness. Apply (i) within each conditional law to obtain the final assertion.

For (iii), let \(B\) be the revealed prefix and \(O\) the remaining vector. Conditional on \(B\), replacing \(Z\) by \(Z-\sum B\) is an invertible translation of the output. Consequently \[\begin{align*} &\mathcal C_p(B,O;\Gamma) -\mathbb E_B\mathcal C_p(O,\Gamma\mid B)\\ &\hspace{1cm} =\mathbb E[-\log p^{\otimes |B|}(B)]-\mathrm H(B\mid Z) \ge0. \end{align*}\] In a conditional law where each remaining letter has marginal \(\nu\), changing the product comparison decreases its cross entropy by \(|O|D(\nu\|p)\). The other two terms are unchanged. This proves the claim, including when \(\nu\) vanishes at some letters. ◻

Proof. Start with 3 and put \[s_j=\mathrm H(X_{j+1}\mid X_1,\ldots,X_j),\qquad 0\le j<T.\] These numbers are nonincreasing. Indeed conditioning decreases entropy, and exchangeability of the unrevealed coordinates gives \[s_{j+1}\le\mathrm H(X_{j+2}\mid X_1,\ldots,X_j)=s_j.\] The chain rule and [eq:source-1] also give \[ \sum_{j=0}^{T-1}(\log|S|-s_j) =D(X^T\|U_S^{\otimes T})\le E. \tag{13}\] The nonnegative deficits in this sum are nondecreasing. Therefore, for \(j<T\), \[\log|S|-s_j\le\frac{E}{T-j}.\]

Let \(a=\lfloor T/4\rfloor\), \(b=\lfloor T/2\rfloor\), and choose a prefix length \(j\) uniformly in the integer interval \([a,b]\). Since \(m_*=o(T)\), we may assume \(b+m_*\le3T/4\). For all indices in the enlarged interval \([a,b+m_*]\), the entropy deficit, and hence the total variation of the sequence \(s_j\) on that interval, is at most \(CE/T\).

For a fixed prefix realization \(x^j\) of positive probability, write \(\nu_{j,x^j}\) for the conditional law of \(X_{j+1}\). It is the conditional marginal of every unrevealed coordinate. The expected divergence of the next \(m\) letters from its product is exactly \[ \begin{split} &\mathbb E_{X^j} D\!\left(\mathcal L(X_{j+1},\ldots,X_{j+m}\mid X^j) \,\middle\|\,\nu_{j,X^j}^{\otimes m}\right)\\ &\hspace{2cm}=m s_j-\sum_{i=0}^{m-1}s_{j+i} =\sum_{i=0}^{m-1}(s_j-s_{j+i}). \end{split} \tag{14}\] For \(0\le i<m_*\), summing the differences over \(j\) cancels all interior terms: \[\sum_{j=a}^{b}(s_j-s_{j+i}) =\sum_{j=a}^{a+i-1}s_j-\sum_{j=b+1}^{b+i}s_j \le i(s_a-s_{b+i})\le C iE/T.\] The equality for \(i=0\) means that both sides are zero; for \(i>0\) it is valid because \(i\le b-a+1\) for sufficiently large \(d\). Averaging [entropy-foundations:conditional-block-divergence] over \(j\), with \(m=m_*\), now gives \[ \mathbb E_{j,X^j} D\!\left(\mathcal L(X_{j+1},\ldots,X_{j+m_*}\mid X^j) \,\middle\|\,\nu_{j,X^j}^{\otimes m_*}\right) \le C m_*^2E/T^2. \tag{15}\] The expectation of \(\log|S|-\mathrm H(\nu_{j,X^j})\) is \(\log|S|-s_j\le CE/T\). In addition, for each fixed \(j\), 4 allows us to condition on the prefix, keep \(T_0\) of the remaining coordinates, and change the comparison to \(\nu_{j,X^j}^{\otimes T_0}\) with cost at most \(E\) after averaging over \(X^j\). Averaging these bounds over \(j\) retains the same upper bound.

All three quantities just bounded are nonnegative. Dividing each by its stated positive upper scale and averaging their sum shows that some common \(j\) and positive-probability prefix realization meet all three bounds, with a larger numerical constant. Freeze this choice, set its conditional marginal equal to \(\nu\), and keep the first \(T_0\) remaining letters. Conditional exchangeability of the unrevealed letters, including their joint law with \(\Gamma\), gives the claimed exchangeable law \(\Psi\). For the \(m_*\)-letter marginal, Pinsker’s inequality \(\|P-Q\|_{\mathrm{TV}}\le\sqrt{D(P\|Q)/2}\) gives the last line of [eq:source-2]; projection contracts total variation and proves it for every smaller \(m\). ◻

Proof. First consider sums under the correlated law \(\Psi\), before introducing contexts. By 4, for every \(s\le T_0\) the law of \((X^s,\Gamma)\) has \(\mathcal C_\nu\le CE\). Relative entropy to \(q\) gives \[ \mathrm H(\Gamma)\le\mathbb E[-\log q(\Gamma)] =F_0+\mathbb E c(\Gamma). \tag{20}\] This comparison is legitimate although \(q\) lives on all of \(\mathbb Z\): \(\Gamma\) is finite-valued and \(q\) is positive on its support. Write \(Z_s=\sum_{i=1}^sX_i+\Gamma\). Given \(X^s\), the two variables \(Z_s\) and \(\Gamma\) are translates of one another. Hence \[\mathrm H(Z_s)=\mathrm I(X^s;Z_s)+\mathrm H(\Gamma\mid X^s) \le\mathrm I(X^s;Z_s)+\mathrm H(\Gamma).\] Since \(\sum_iX_i=Z_s-\Gamma\), it follows that \[ \mathrm H_\Psi\!\left(\sum_{i=1}^sX_i\right) \le\mathrm I(X^s;Z_s)+2\mathrm H(\Gamma) \le 2F_0+CE. \tag{21}\]

We transfer this bound to independent letters only for \(s\le m_*\). The sum laws then have total variation distance at most \(\eta=Cm_*\sqrt E/T\) by [eq:source-2]. For completeness, if two laws on a finite alphabet of size \(N\) have distance \(\eta'\), couple them as \(U,V\) with \(\mathbb P(U\ne V)=\eta'\). Such a coupling uses their common submeasure, the pointwise minimum, for the equal values; the two residual submeasures have disjoint supports and total mass \(\eta'\). Let \(J\) be the disagreement indicator. The chain rule gives \[\mathrm H(U)\le\mathrm H(V)+\mathrm H(J)+\mathrm H(U\mid V,J) \le\mathrm H(V)+\log2+\eta'\log N.\] Interchanging \(U,V\) yields the corresponding absolute difference bound. Apply this with the common alphabet \(sS\). The added error is at most \[ \log2+C\frac{m_*\sqrt E}{T}\log|sS|=o(d/h^2). \tag{22}\] Indeed \(m_*\sqrt E/T\le d^{-1/2+o(1)}\) for fixed \(D_0\), while [entropy-foundations:sumset-hypothesis] bounds the logarithm by \(D_0d h^{P_0}\log d\); the product is \(d^{1/2+o(1)}\). This estimate is uniform in \(s\le m_*\), and \(s\le d^2\) for large \(d\). Combining [entropy-foundations:correlated-sum-entropy,entropy-foundations:continuity-error] shows \(G_s(\varnothing)\le C(D_0)d\).

For independent current pairs, conditioning on all the contexts makes the letters independent. For any independent finite-valued \(A,B\) on \(\mathbb Z\), one has \(\mathrm H(A+B)\ge\mathrm H(A+B\mid B)=\mathrm H(A)\). Applying this at each fixed context tuple and averaging proves that \(G_s(W)\) is nondecreasing in \(s\). Adding the last context does not change the law of the first \(s\) pairs, so the averaged right-hand side is exactly \(G_s(W)\). Refinement decreases \(G_s\) by conditioning on more information in an iid extension of all pairs. The established initial bound therefore proves (i).

Nonnegativity of \(I_r\) follows from that of \(\mathcal F\). For its monotonicity in \(r\), take any \((r+1)\)-row trial and put \(S_r=\sum_{a=1}^rX_a\). The chain rule and removal of conditioning give \[\begin{align*} &\mathrm H(X^{r+1}\mid S_{r+1},W^{r+1})\\ &\quad=\mathrm H(X_{r+1}\mid S_{r+1},W^{r+1}) +\mathrm H(X^r\mid X_{r+1},S_r,W^{r+1})\\ &\quad\le\mathrm H(X\mid W)+\mathrm H(X^r\mid S_r,W^r). \end{align*}\] The projected first \(r\) pairs form an admissible trial. Subtracting this inequality from \((r+1)\mathrm H(X\mid W)\) and taking infima proves \(I_{r+1}(W)\ge I_r(W)\). To refine a trial for \(I_r\), use independent channels given each old pair as in [entropy-foundations:refinement-identity], with \(Z=S_r\). They preserve the required new one-row marginal and do not increase the objective. Taking an optimal old trial proves refinement monotonicity.

Finally use the projection of \(\Psi\) to \(r\le T_0\) letters as a trial at the constant context. Its exact-sum objective is \[r\mathrm H(\nu)-\mathrm H(X^r\mid S_r) =D(X^r\|\nu^{\otimes r})+\mathrm H(S_r) \le 2F_0+CE,\] using [eq:source-2,entropy-foundations:cost-rules,entropy-foundations:correlated-sum-entropy]. Choose \(C'_0(D_0)\) large enough for this and the \(G_s\) bound. Refinement monotonicity then proves (ii) with the same fixed \(D_*\). ◻

Proof. Write \(B_a=(X_{a,1},\ldots,X_{a,m})\), \(V_a=(W_{a,1},\ldots,W_{a,m})\), \(Y_a=\sum_iX_{a,i}\), and \(Z=\sum_aY_a+\Gamma\). For any full-vector trial, the full-vector objective minus its projected sum objective equals \[ \sum_{a=1}^r\mathrm H(B_a\mid Y_a,V_a) -\mathrm H(B^r\mid Y^r,Z,V^r)\ge0. \tag{24}\] The equality follows from the chain rule, since \(Y_a\) is a function of \(B_a\); the inequality follows by subadditivity and conditioning. Thus projection to block sums does not increase the cost.

Conversely, start with any admissible joint law of \((Y^r,V^r,\Gamma)\). In each row, independently of all the other new rows and of \(\Gamma\) conditional on \((Y^r,V^r)\), sample the block from the genuine iid block law conditioned on its own sum and contexts: \[\mathcal L(B^r\mid Y^r,V^r,\Gamma) =\prod_{a=1}^r \mathcal L_{\mathrm{iid}}(B_a\mid Y_a,V_a).\] Each full row then has precisely the prescribed iid marginal. Conditioning further on \(Z\), a function of \((Y^r,\Gamma)\), does not change these independent conditional row laws. Consequently the last entropy in [entropy-foundations:lift-difference] equals the sum of the first entropies after averaging. The two objectives are equal for this lift, which proves equality of their infima.

For refinement, use this full-vector formulation. At every one of its \(mr\) positions, run the prescribed one-letter channel independently given the old pairs, also independently of the old error given those pairs. The iid old-pair marginal within a row and the independent channels give exactly the iid refined-pair marginal required in that row. Apply [entropy-foundations:refinement-identity] with the whole row as \(B_a\) and its vector of new observations as \(A_a\). The error law and its cost are unchanged, and the entropy objective cannot increase. Taking an optimal old trial proves the stated monotonicity.

A new one-letter channel may itself be specified by an experiment using auxiliary letters, as will occur in 4. In the construction just used, each channel is run with fresh auxiliary randomness conditional on its own old pair. One does not substitute the other actual letters of its row for those auxiliary samples. This distinction is what preserves the prescribed iid row marginal. ◻

Proof. It suffices to construct a trial for the constant context; the rest follows from 7. Take \(2r\) disjoint blocks of \(m\) coordinates from \(\Psi\). Their common marginal is a law \(\mu\) on \(S^m\). Put \(Q=\nu^{\otimes m}\) and \[\varepsilon=\|\mu-Q\|_{\mathrm{TV}} \le C m_*\sqrt E/T.\] Define the common submeasure \(\gamma(\boldsymbol x) =\min(\mu(\boldsymbol x),Q(\boldsymbol x))\), which has total mass \(1-\varepsilon\). Conditional on a block value \(\boldsymbol x\) with \(\mu(\boldsymbol x)>0\), tag it with probability \(\gamma(\boldsymbol x)/\mu(\boldsymbol x)\). The choices of tags may be made independently given all block values. Each tagged block has unnormalized law \(\gamma\); independence between the block values is not assumed.

Let \(B\) be the number of tagged blocks. If \(B<r\), reject. If \(B\ge r\), accept with probability \(B/(2r)\), using a fresh coin, and upon acceptance select \(r\) distinct tagged blocks uniformly in random order. Let the acceptance probability be \(1-\delta\). Each block fails to be tagged with probability \(\varepsilon\), so \[\mathbb E(2r-B)=2r\varepsilon, \qquad\mathbb P(B<r)\le2\varepsilon.\] The rule consequently gives \[ \begin{split} \delta &=1-\mathbb E\left[\frac B{2r}\mathbf1_{\{B\ge r\}}\right]\\ &=\varepsilon+\mathbb E\left[\frac B{2r}\mathbf1_{\{B<r\}}\right] \le3\varepsilon. \end{split} \tag{26}\] In particular \(\delta<1\) for sufficiently large \(d\).

We check the marginal of an accepted row before normalizing by the acceptance probability. Given the tags, a particular tagged block has probability \(1/B\) of occupying any specified selected row. Multiplying this by the acceptance probability \(B/(2r)\) cancels \(B\). Therefore all selected rows have the same unnormalized marginal \(\eta\), and, for each \(\boldsymbol x\in S^m\), \[ \begin{split} \eta(\boldsymbol x) &=\frac1{2r}\sum_{i=1}^{2r} \mathbb E\!\left[ \mathbf1_{\{B\ge r\}} \mathbf1_{\{i\text{ tagged}\}} \mathbf1_{\{\text{block }i=\boldsymbol x\}} \right]\\ &\le\gamma(\boldsymbol x)\le Q(\boldsymbol x). \end{split} \tag{27}\] Its total mass is \(1-\delta\). This domination is the reason for the acceptance weight \(B/(2r)\).

On acceptance, retain the selected letters in their selected order and keep the same error \(\Gamma\). To bound their cost, first project \(\Psi\) to the \(2rm\) letters used above. Its cost with respect to \(\nu^{\otimes 2rm}\) is at most \(CE\). Record a finite index \(J\) that is either a rejection symbol or the ordered tuple of the \(r\) selected block indices. The full tag pattern is not recorded. Thus \[\mathrm H(J)\le\log\bigl(1+(2r)^r\bigr) \le\log2+r\log(2r).\] By 4, conditioning on \(J\) and then projecting and reordering on accepted outcomes has average cost at most \(CE+\mathrm H(J)\). Nonnegativity permits us to drop the rejected outcomes from this upper bound. Finally, forgetting the ordered indices on the accepted outcomes uses convexity of the combined cost \(\mathcal C_\nu\). If \(P_{\mathrm{acc}}\) is the normalized accepted joint law of the \(mr\) letters and the error, we obtain \[ (1-\delta)\mathcal C_\nu(P_{\mathrm{acc}}) \le CE+\log2+r\log(2r). \tag{28}\] Keeping the acceptance mass on the left avoids any division by a small conditional acceptance probability for a particular ordered selection.

If \(\delta=0\), the accepted rows already have marginal \(Q\) and the construction is complete. Otherwise let \[R=\frac{Q-\eta}{\delta}.\] This is a probability law on \(S^m\) by [entropy-foundations:accepted-submeasure]. Complete the trial by mixing \(P_{\mathrm{acc}}\), with weight \(1-\delta\), and the law of \(r\) independent blocks with marginal \(R\), with weight \(\delta\); in the latter law set \(\Gamma=0\). Every row of the mixture now has exact marginal \(\eta+\delta R=Q\). Thus it is an admissible full-vector trial for \(K_m\). The error still lies in \(TS-TS\), which contains zero.

For the filling law, \(R\le Q/\delta\) pointwise, and hence \[D(R\|Q)\le\log(1/\delta).\] Independence between its \(r\) blocks makes its divergence to \(\nu^{\otimes mr}=Q^{\otimes r}\) equal to \(rD(R\|Q)\). Its noisy sum is the exact sum, which lies in \(mrS\), so the mutual information in the output is its entropy, at most \(\log|mrS|\). The error cost is \(c(0)=0\). Its weighted additional cost is therefore at most \[ \delta r\log(1/\delta)+\delta\log|mrS|. \tag{29}\] Convexity of \(\mathcal C_\nu\) on mixing, followed by the full-vector identity of 7, bounds \(K_m\) by the sum of the right-hand sides of [entropy-foundations:accepted-cost,entropy-foundations:residual-cost].

It remains to verify the scale of all additional terms. Since \(w^2=\sqrt{\log d}\) and \(r\le Te^{-w^2}/2\), \[r\log(2r) \le Cdh^{-5}e^{-\sqrt{\log d}}\log d=o(d/h^2).\] Also \(\delta\log(1/\delta)\le1/e\), so the first term of [entropy-foundations:residual-cost] is at most \(r/e=o(d/h^2)\). For its second term, [entropy-foundations:acceptance-error] gives \(\delta\le d^{-1/2+o(1)}\), and \(mr\le T_0/2<d^2\) allows the sumset hypothesis to give \[\delta\log|mrS| \le d^{-1/2+o(1)}D_0d h^{P_0}\log d=o(d/h^2).\] These estimates include all entropy paid for the selection index. They are uniform in admissible \(m,r\). Since \(E\ge d/h^2\), the additional terms can be absorbed into a numerical multiple of \(E\) once \(d\) is sufficiently large depending on \(D_0,P_0\). This proves [eq:source-3]. ◻

Proof. Independence of the pairs gives \[\begin{split} &\mathrm I\left(X_1;\sum_{i=1}^mX_i,W_2,\ldots,W_m\mid W_1\right)\\ &\quad=\mathrm H\left(\sum_{i=1}^mX_i\mid W_1,\ldots,W_m\right) -\mathrm H\left(\sum_{i=2}^mX_i\mid W_2,\ldots,W_m\right), \end{split}\] which proves [entropy-refinement:one-letter-loss].

Take independent minimizing trials for \(I_r(W)\) and \(K_{m-1}(W;r)\). Their alphabets, including the error alphabet \(TS-TS\), are finite, so minimizers exist. Write their row vectors and contexts as \[U=(U_a)_{a=1}^r,\quad\mathcal W=(W_a)_{a=1}^r, \qquad Y=(Y_a)_{a=1}^r,\quad\mathcal V=(V_a)_{a=1}^r,\] where each \((Y_a,V_a)\) has the sum-and-context law of an independent \((m-1)\)-letter block. Set \[P=(\mathcal W,\mathcal V),\qquad Z_U=\sum_aU_a,\qquad Z_Y=\sum_aY_a+\Gamma.\] The whole \((U,\mathcal W)\) trial is independent of the whole \((Y,\mathcal V,\Gamma)\) trial. Consequently \((U+Y,P,\Gamma)\) is admissible for \(K_m(W;r)\), and \((U,(U+Y,P))\), with exact output \(Z_U\), is admissible for \(I_r(W')\). Each row has the prescribed marginal in both trials; independence across rows is not required.

The two positive one-row entropy terms add to \[\begin{split} &\mathrm H(U_a+Y_a\mid W_a,V_a) +\mathrm H(U_a\mid U_a+Y_a,W_a,V_a)\\ &\quad=\mathrm H(U_a,Y_a\mid W_a,V_a) =\mathrm H(U_a\mid W_a)+\mathrm H(Y_a\mid V_a). \end{split}\] For the subtracted joint entropies, condition both terms on both old outputs: \[ \begin{split} &\mathrm H(U+Y\mid Z_U+Z_Y,P)+\mathrm H(U\mid U+Y,Z_U,P)\\ &\quad\ge\mathrm H(U+Y\mid Z_U,Z_Y,P) +\mathrm H(U\mid U+Y,Z_U,Z_Y,P)\\ &\quad=\mathrm H(U,Y\mid Z_U,Z_Y,P)\\ &\quad=\mathrm H(U\mid Z_U,\mathcal W) +\mathrm H(Y\mid Z_Y,\mathcal V). \end{split} \tag{32}\] The middle equality uses the invertible map \((U,Y)\mapsto(U+Y,U)\); the last uses independence of the old trials. This argument permits random \(\Gamma\). The error cost stays unchanged. Adding the new trial costs and taking infima proves \(K_m(W;r)+I_r(W')\le K_{m-1}(W;r)+I_r(W)\).

For a partial observation \(W^{(\zeta)}\), conditioning on the independent mark gives its entropy loss. To bound its exact cost, synchronize the mark across rows, using a minimizing old coupling on mark zero and a minimizing fully refined coupling on mark one. This has the prescribed refined pair marginal in each row, so \[I_r(W^{(\zeta)})\le(1-\zeta)I_r(W)+\zeta I_r(W').\] The assertion follows. ◻

Proof. Normalize by \[a_j=I_{r_j}/D_*,\qquad g_s=G_s/D_*,\qquad\tau=E/D_*\in(0,1].\] These functions take values in \([0,1]\). At a fixed state \(a_j\) increases with \(j\) and \(g_s\) increases with \(s\); all decrease under refinement. Measure refinement cost by \(\tau\) times the loss in \(g_1\). Costs add, and total cost \(c\) means entropy loss \(cD_*^2/E\).

Completion of the proof of 2. Use the context \(W\), index \(j\), and high endpoint \(m=m_{j,1}\) supplied by 10. Put \(r=r_j\) and \(s=mr\ge L\). Combining [entropy-refinement:search-conclusion] with the low-end bound [eq:source-3], preserved under refinement, gives \[ K_m(W;r)\le CE \tag{45}\] with numerical \(C\). Lift a minimizing coupling to all \(s\) letters using the full-vector interpretation of the cost. Write \(\boldsymbol W=(W_i)_{i=1}^s\) for their whole context stack, and \(\nu_z\) for the prescribed one-letter conditional law given context \(z\).

At any fixed stack \(\boldsymbol w\) of positive probability, compute \[ \begin{split} C(\boldsymbol w)&= D\left(X^s\,\middle\|\,\prod_i\nu_{w_i}\right) +\mathrm I(X^s;Z)+\mathbb Ec(\Gamma),\\ &\hspace{35mm}Z=\sum_iX_i+\Gamma, \end{split} \tag{46}\] under the actual conditional law at that stack. All three terms are nonnegative. The actual conditional letter marginals after freezing the whole stack may differ from the comparator laws \(\nu_{w_i}\). Nevertheless the comparison has finite divergence: an event \(X_i=x,W_i=w_i\) with \(\nu_{w_i}(x)=0\) has zero probability even before conditioning, so it also has zero probability at any positive-probability stack. Before freezing, however, each row has its prescribed independent block marginal, and consequently \[\mathbb E\left[-\log\prod_i\nu_{W_i}(X_i)\right]=s\mathrm H(X\mid W).\] Subtracting \(\mathrm H(X^s\mid Z,\boldsymbol W)\) and adding the error cost therefore shows that \(\mathbb EC(\boldsymbol W)=K_m(W;r)\le CE\).

For the separate quantity \(B(\boldsymbol w)=s^{-1}\sum_iD(\nu_{w_i}\|U_S)\), the prescribed pair marginals give \[ \begin{split} \mathbb EB(\boldsymbol W) &=\log|S|-\mathrm H(X\mid W)\\ &=\log|S|-\mathrm H(\nu)+G_1(\varnothing)-G_1(W)\\ &\le CE/T+\frac{CD_*^2}{Eh^2} \le\frac{C(D_0)d^2}{Eh^2}. \end{split} \tag{47}\] This uses [eq:source-2,entropy-refinement:search-conclusion]. The \(E/T\) term is absorbed because \(T\asymp d/h^5\), \(E\le D_0d\), and \(E^2h^7/d^3\to0\) for fixed \(D_0\). Markov’s inequality, with factor four for each quantity, selects one stack such that \[ C(\boldsymbol w)\le CE,\qquad B(\boldsymbol w)\le\frac{C(D_0)d^2}{Eh^2}. \tag{48}\] A zero-mean quantity is zero almost surely, which covers that case as well. Freeze this stack.

Proof. Expand each factor as \[e^{-\lambda(1-\operatorname{Re}\chi_s)} =e^{-\lambda} \exp\bigl((\lambda/2)\chi_s\bigr) \exp\bigl((\lambda/2)\chi_{-s}\bigr).\] Its Fourier coefficients are nonnegative, with sum one. The expansions are absolutely summable, as is their finite product. Evaluation at zero therefore gives \(\sum_uq_A(u)=1\); evenness gives \(q_A(-u)=q_A(u)\).

For completeness, write \(c_s(y)=\cos(2\pi sy)\) and \(Z_A=\int\exp(\sum_s\lambda_sc_s)\). Express the covariance using two independent copies as half the expectation of the product of their differences. The map \((x,z)\mapsto(x+z,x-z)\) pushes Haar probability on the two-dimensional torus to Haar probability. The two differences are \(-2\sin(2\pi ux)\sin(2\pi uz)\) and the analogous expression for \(v\), whereas the unnormalized product density is \(\exp(2\sum_s\lambda_sc_s(x)c_s(z))\). Expanding this last exponential gives the identity \[\operatorname{Cov}_{K_A}(c_u,c_v) =\frac{2}{Z_A^2} \sum_{(n_s)\ge0}\left(\prod_s\frac{(2\lambda_s)^{n_s}}{n_s!}\right) \left(\int\sin(2\pi ux)\sin(2\pi vx) \prod_sc_s(x)^{n_s}\,dx\right)^2.\] Absolute convergence justifies the expansion and proves nonnegativity. Differentiation under the integral yields \[\frac{\partial}{\partial\lambda_v}\int c_uK_A =\operatorname{Cov}_{K_A}(c_u,c_v),\qquad \frac{\partial F}{\partial\lambda_u}=\int(1-c_u)K_A.\] The latter derivatives are nonnegative and decrease in every nonnegative coefficient direction. Integrating these derivative statements proves the assertions about \(F\) and its increments. Since \(\Delta_A(u)^2=2(1-\int c_uK_A)\), the metric monotonicity follows as well. Subadditivity follows from \(1-\chi_{u+v}=(1-\chi_u)+\chi_u(1-\chi_v)\) and the triangle inequality in \(L^2(K_A)\).

Translation multiplies each Fourier coefficient of \(e^{-P_j}\) by a unit complex number. Absolute values in the convolution of these coefficients are therefore bounded by the corresponding convolution of the centered coefficients, which is \(q_P(u)\). Finally \(q_P(u)=e^{-F(P)}\int\chi_uK_P\), and both required comparisons follow from the monotonicities already proved. ◻

Proof. Selecting the subset and its weight. On \(S\) and then on its successive restrictions set \[t=\max\left(\varepsilon k_b, \max_{\nu\text{ supported on the current set}}E_T(\nu) \right).\] The maximum exists: the simplex is compact, its moment integral is continuous and strictly positive, and therefore its negative logarithm is continuous. For large \(d\), the floor is between \(d/h^2\) and \(D_0d\); the upper bound follows also for the maximum from [eq:thermal-moment-cap]. Apply 2 with \(E=t\) to obtain a subset \(S'\) and center \(x_0\). Its conclusion holds for every probability on this fixed \(S'\), so the weight may now be chosen by the following test. If the maximum of \(E_T\) on \(S'\) is at least \(t/4\), keep a maximizing witness and terminate with a regular test. If that maximum is smaller than \(t/4\) and \(t=\varepsilon k_b\), take uniform \(\nu\) on \(S'\) and terminate with a cheap update. Otherwise replace the current set by \(S'\) and repeat. Every nonterminal iteration reduces \(t\) by a factor of at least four, except possibly for the last transition to the fixed floor. Thus the process terminates in finitely many iterations, and the sum of the logarithmic cardinality losses is at most \[C(D_0)\frac{d^2}{\varepsilon k_bh^2}.\] The initial child restriction lost at most \(\log2\) in logarithmic cardinality. Since \(k_b\ge A_0d/h\), choosing \(A_0\) sufficiently large in terms of \(D_0,P_0,\varepsilon\) makes the final loss less than \(0.2k_b\), proving \(\log|S'|\ge0.8k_b\).

Choosing a flat coefficient range. For the last center and chosen probability, the compression conclusion is \[F(\widetilde A+LB)-F(\widetilde A)\le Ct.\] Put \(A_{\rm base}=A+S_p\). Monotonicity of \(F\) and \(A_{\rm base}\preceq\widetilde A\) give \[F(A_{\rm base}+LB)-F(A_{\rm base}) \le \bigl[F(\widetilde A+LB)-F(\widetilde A)\bigr] +\bigl[F(\widetilde A)-F(A_{\rm base})\bigr].\] The first bracket is controlled by compression and the second by the tightening bound in [eq:source-7]. Hence \[ F(A_{\rm base}+LB)-F(A_{\rm base})\le C_1t. \tag{70}\] The constant \(C_1\) is numerical: the volume constant of compression is numerical, and the cap-dependent error in [eq:source-7] is \(o(t)\) after the fixed caps and \(A_0\) have been selected.

To find a flat range, set \[\lambda_j=dh^{200}(2h^{140})^j, \qquad N=\left\lfloor \frac{\log(2L/(dh^{200}))}{\log(2h^{140})}\right\rfloor.\] For \(0\le j<N\), the intervals \([\lambda_j/2,h^{140}\lambda_j]\) are adjacent and lie in \([dh^{200}/2,L]\). Since \(\log(L/d)=w=e^{h/4}\), \(N\asymp e^{h/4}/\log h>C_1D_0h^{400}\) for sufficiently large \(d\). The sum of the free-energy increments on these intervals is bounded by [eq:thermal-volume-cost], hence by \(C_1D_0d\). At least one increment is at most \(dh^{-400}\). Take its \(\lambda\) and \(D_i=\lambda B\); this is [eq:source-5]. Concavity along the \(B\) direction gives \[\int BK_{A_{\rm base}+\lambda B} \le\frac{F(A_{\rm base}+\lambda B)-F(A_{\rm base})}{\lambda} \le C_1t/\lambda,\] which proves [eq:source-9] and the metric increment bound.

The input-only success set. For a regular test define the success set by \[ \left|\sum_x\nu(x)\chi_{gx}(Y) \mathbb E[v_x(Z)\mid Y]\right|\ge\beta/2. \tag{71}\] The expectation uses the specified type-\(A\) channel, rather than the sampled old observation. The expression has modulus at most one, and [eq:source-8], averaged with \(\nu\), gives its expected modulus at least \(\beta\). Thus its probability of exceeding \(\beta/2\) is at least \(\beta/2\). In the cheap alternative take the entire input as success. The data \(a,p,\alpha,A\) determine all these sets and choices.

The change in the gap potential. It remains to prove the gap assertions. Since \(r\le r_{\rm sep}/2\) through the count cap, summability of \(q_A\) gives \[|B_A(r)|e^{-F(A)}(1-r^2/2)\le1, \qquad F(A)-\log|B_A(r)|\ge\log(1-r^2/2)\ge-C.\] The balls are finite by the same inequality. Initially \(A=0\) and \(B_0(r)=\{0\}\), so the gap is zero. The spatial addition raises \(F\), but also allows short integer translates of the old ball inside a slightly larger new ball. We compare these changes using the same overlap multiplicity. Write \[U=B_A(r),\qquad D_p=\mathbb Z\cap[-\sigma R_p/10,\sigma R_p/10],\qquad l=|(U-U)\cap(D_p-D_p)|.\] Here \(l\ge1\). On this intersection \(\Delta_A\le2r\) and \(|u|\le\sigma R_p/5\), so convolution and [eq:thermal-spatial] imply \[ F(A+S_p)-F(A)\le\log R_p-\log l+C, \qquad |U+D_p|\ge |U||D_p|/l. \tag{72}\] For the second inequality, each representation of a fixed element of \(U+D_p\) differs from one fixed representation by an element of the intersection defining \(l\), so its multiplicity is at most \(l\).

After either addition, \(U+D_p\) lies in \(B_{A^+}(r+\eta/2)\), since monotonicity preserves the old radius and \(\Delta_{A^+}(j)\le C|j|/R_p\le C\sigma=o(\eta)\) for \(j\in D_p\). On a cheap success, uniformity of \(\nu\) and [eq:source-9] give \[\frac1{|S'|}\sum_{x\in S'}\Delta_{A^+}(g(x-x_0))^2 \le 2C_1t/\lambda.\] At least half the \(x\) therefore have \(\Delta_{A^+}(g(x-x_0))\le\sqrt{4C_1t/\lambda} \le C(D_0)h^{-100}=o(\eta)\). Their translates \(g(x-x_0)+U+D_p\) lie in the new tracked ball \(B_{A^+}(r+\eta)\). They are disjoint. A collision would put \(g(x-x')\) in \(U-U+D_p-D_p\); after restoring the two snapping errors, the difference of the original frequencies would lie in \[B_A(2r)+\{j\in\mathbb Z:|j|\le3\sigma R_p/10\},\] contrary to [eq:thermal-separation].

Since \(R_p/|D_p|\le C/\sigma\), including the case \(D_p=\{0\}\), [eq:thermal-packing-pair] cancels the same \(\log l\) in the free-energy and cardinality costs. On a regular success the gap increase is at most \(C_1t+O(\log h)\le C_2t\) for a numerical \(C_2\). On a cheap success it is at most \[C_1\varepsilon k_b-\log(|S'|/2)+O(\log h) \le C_1\varepsilon k_b-0.8k_b+O(\log h)\le-k_b/2,\] on choosing \(\varepsilon\) sufficiently small numerically and then taking \(d\) sufficiently large. These choices precede the cap choices; only the size-loss bound and the small-error thresholds require the subsequent choices of \(A_0\) and \(d\). ◻

Proof. First bound the posterior normalizing integral from below at an admissible past. The phase triangle inequality gives \(A_j(v+u)\le2A_j(v)+2A_j(u)\), and the observation count gives \(2\sum_jA_j\preceq h^{130}A\) for sufficiently large \(d\). Thus \[ \int_p\exp\left(-\sum_jA_j(z_j-y)\right)dy \ge c\exp(-2s_d-F(\widetilde A)). \tag{75}\] Indeed in one direction from \(y_0\) a segment of length \(|p|/2\) remains inside \(\overline p\). By symmetry and the spatial variance estimate, the density \(K_{\widetilde A}(y-y_0)\) assigns this segment at least a numerical positive mass if \(C_s\) is large enough: the circular second-moment bound puts a fixed positive mass within distance \(|p|/2\) of zero, and symmetry gives half of that mass in either direction. On this segment the integrand is at least \(e^{-2s_d}\exp(-h^{130}A(y-y_0))\), which is at least \(e^{-2s_d}\exp(-\widetilde A(y-y_0))\).

Fix one fresh clone and integrate over its value \(z'\) in the consistency set \(\{z':A(z'-Z)\le4s_d\}\). Also use the variable \(\theta^+=V-Y\), whose independent conditional density is \(K_{A^+}\). At fixed \(z',\theta^+\) expand the \(2T\)-moment of \[\left|\sum_x\nu(x)v_x(z')\chi_{gx}(Y+\theta^+)\right|\] in the posterior integral. Its weights include the extra clone factor \(e^{-A(z'-y)}\) and the spatial majorant used above. The centered summed form is \[P=\sum_jA_j+A+S_p, \qquad A+S_p\preceq P\preceq\widetilde A.\] The upper comparison follows from the observation count and large \(d\). By [eq:thermal-envelope], the \(y\) integral before the clone normalization and the posterior division is at most \[Ce^{-F(A+S_p)}e^{-E_T(\nu)} \le Ce^{-F(A+S_p)}e^{-t/4}.\] Here the phase factors involving \(\theta^+\) have modulus one, and \(|v_x(z')|\le1\), so the same coefficientwise moment bound applies. The consistency set has length at most \(e^{4s_d-F(A)}\), since \(e^{-A}\ge e^{-4s_d}\) there. This cancels the clone normalization \(e^{F(A)}\) up to \(e^{4s_d}\). The density in \(\theta^+\) integrates to one. Dividing by [eq:thermal-posterior-denominator], applying the moment tail bound at \(\beta/4\), and summing over the clones gives \[C N_h\exp\left( 6s_d+F(\widetilde A)-F(A+S_p) +2T\log(4/\beta)-t/4\right)\le e^{-t/8}.\] Indeed [eq:source-7], \(t\ge\varepsilon k_b\), and \(2T\log(4/\beta)=o(t)\) absorb every positive term. The reference success coin is independent of \(Y\) given the past and so has not altered its posterior.

For the true-law assertion, condition on \(Y\) and its entire discrete parameter path. At a regular success the conditional mean in [eq:thermal-success-set] has modulus at least \(\beta/2\). The empirical mean of the \(N_h\) clone polynomials evaluated at \(Y\) approximates it to error \(\beta/16\) except with probability \(C/(\beta^2N_h)\), by the second-moment bound for independent bounded complex variables. Replacing \(Y\) by \(V\), and removing the common phase \(\chi_{gx_0}(V-Y)\), changes each of these polynomials by at most \[\sum_x\nu(x)|1-\chi_{g(x-x_0)}(V-Y)|.\] Its conditional expectation is at most \(\sqrt{2\int BK_{A^+}}\le C\sqrt{t/\lambda}=O(h^{-100})\) by [eq:source-9]. Markov’s inequality makes this error at most \(\beta/16\) except with probability \(C\sqrt{t/\lambda}/\beta=o(h^{-30})\), since \(\beta\ge ch^{-32}\). Outside these errors the clone average after replacement has modulus at least \(3\beta/8\), so at least one clone satisfies the large-polynomial condition in [eq:source-10]. The empirical-mean error probability is \(O(h^{-56})\), also \(o(h^{-30})\).

Finally sum the own-error energies of every observation on the capped true path, each measured in its own form. Conditional independence and the input-only selection rule let us apply the energy estimate in [eq:source-7] at each draw, including final draws. There are at most \(O(h^{121})\) observations, each of conditional expected energy \(O(h(dh^{-400}+1))\). Their total expected energy is therefore \[O(dh^{-278}+h^{122})=o(s_dh^{-30}).\] With exception probability \(o(h^{-30})\), their total energy is at most \(s_d\). This single event makes every past admissible by taking \(y_0=Y\). It also gives every consistency condition, since the old main and its clone both have type \(A\) and \[A(Z'-Z)\le2A(Z'-Y)+2A(Z-Y)\le4s_d.\] There are only \(O(h)\) regular successes. Unioning their conditional large-polynomial failure bounds and adding the total-energy exception proves the simultaneous \(o(h^{-20})\) assertion. The bound is over successes rather than over all attempts; past admissibility at all attempts followed from the single total-energy event. ◻

Proof.

Proof. The initial density deficit relative to spatial uniform is at most \(d-\log\alpha\le C d_1\). On a live plateau with jumps, \(\alpha\ge e^{-d}\). To pay for its fixed label, let \(p_*\) be the interval of the last main addition and \(c_*\) its center. Compare its channel with the fixed density \(K_{S_{p_*}}(z-c_*)\). Writing \(Z=Y+\theta\) gives \[\begin{split} \mathrm I(Y;Z)&\le\mathbb E_Y D\bigl(K_A(z-Y)\,dz\,\|\,K_{S_{p_*}}(z-c_*)\,dz\bigr)\\ &=F(A)-F(S_{p_*})-\mathbb E A(\theta) +\mathbb E S_{p_*}(Y+\theta-c_*)\\ &\le F(A)-\log R_{p_*}+C\le Cd. \end{split}\] Indeed \(p_e\subseteq p_*\), the channel includes \(S_{p_*}\), and the spatial variance and form monotonicity in 5 bound the last energy by a constant: use the phase triangle inequality and \(|Y-c_*|\le |p_*|/2\). The negative energy can be dropped. The initial dummy channel has zero information. This estimate holds for every input law supported on \(p_e\), so also for the post law at a later live jumping state.

Within one live plateau a true path has at most one success, which is terminal for that plateau. Its success probability at a test is at least \(c b_0^2\), so its success surprisal is \(O(1+\log h)\). The accumulated failure surprisal has an exponential tail by the failure-stretch supermartingale used in 6. Thus the expected total membership entropy cost is \(O(1+\log h)\). Static plateaus have no such cost. Forward from a live post state, \(m_p\ge e^{-d}\), so the initial density deficit is again at most \(2d\), and the same membership argument applies. This forward argument begins without earlier auxiliary observations. Retaining such information \(W\) instead increases the initial information term from \(\mathrm I(Y;Z)\) to \(\mathrm I(Y;Z,W)=\mathrm I(Y;Z)+\mathrm I(Y;W\mid Z)\).

For completeness, apply the entropy chain rule to any finite remaining spatial bit string. Its expected deficit relative to the uniform string starts below the density deficit, plus the information of any label already observed. Revealing a bit consumes its conditional deficit relative to a fair bit. An additional observation increases the expected remaining deficit by its conditional information about the remaining string, at most its conditional Shannon entropy if finite-valued. The remaining deficit is nonnegative at stopping. Membership entropy can be bounded before conditioning on side and auxiliary observations, using the discrete state history that prescribes the tests. This proves the first assertion, including finite extensions.

At a post state \(p\), the joint observations have conditional density \((\alpha/m_p)M\) under truth and the next bit bias is \(D_{\rm jump}/M\). Their averaged squared bias is therefore \[\frac{\alpha}{m_p}\int\frac{|D_{\rm jump}|^2}{M}.\] Observing further past information only increases the mean squared conditional bias, by conditional Jensen. For a bit with bias \(\theta\), its relative entropy to fair is at least \(\theta^2/2\). Multiply by [eq:07-state-conversion] and sum: the factors \(m_p/\alpha\) and \(\alpha/m_p\) cancel. This proves [eq:07-local-fisher] without any lower bound on surviving mass. Starting at \(p_0\) instead leaves the factor \(m_{p_0}/\alpha\le2\), as asserted. ◻

Proof. For (i) and (ii), fix the global unlabelled input experiment of 16, following memberships through all live epochs and freezing the terminal piece only at live termination. For (iii) and (iv), first fix one plateau and use the corresponding local input experiment of 17, freezing the terminal piece at that plateau’s exit. In each application, all windows below belong to one common finite spatial extension of this fixed experiment and use the same predictable spatial entropy sequence.

At a final post state the conditional input edge probability is \[q=\frac{\alpha e_{p,b}}{m_p}\ge c b^\kappa/2 \quad\text{if the jump is bad}.\] From this state compare the next \(l=l_b\) spatial bits, starting with its jump bit, to a reference experiment with fair spatial bits. At intervening membership tests use the very same state-conditional outcome probabilities as in the true unlabelled experiment. Thus membership likelihood factors cancel. This reference can be generated by sampling each bit fairly, regardless of earlier memberships, and by tossing the stated membership coins on their recorded branches. In particular its spatial path remains uniform. Continue bits after exits or stops as needed, keeping the piece fixed and taking no new observations. Histories of zero true mass can be extended arbitrarily under the reference while leaving its bits fair.

The edge is determined by the next \(l\) bits, up to null endpoints, and its reference probability is at most \(16\,2^{-l}\). If \(L\) is the true-to-reference likelihood ratio of this segment, then \[\mathbb P_{\rm true}(\mathrm{edge}\cap\{L<2^{l/2}\}\mid\text{post state}) \le16\,2^{-l/2}\le q/2.\] The last inequality follows uniformly from the choice of \(l_b\), the badness lower bound on \(q\), and sufficiently large \(d\). Call the starting depth marked if the edge occurs and \(\log L\ge(l/2)\log2\). Conditional on a bad post state, its probability is at least \(q/2\).

Let \(s_j\) be the predictable relative entropy to fair of the spatial bit at depth \(j\), in this unlabelled true history. If its bias is \(\theta_j\), then \(s_j\ge\theta_j^2/2\), whereas the positive part of its realized log likelihood increment satisfies \[\bigl[\log(1\pm\theta_j)\bigr]_+ \le |\theta_j|\le\sqrt{2s_j}.\] Memberships contribute no log increment to \(L\). On a mark, Cauchy–Schwarz on the length-\(l\) window consequently yields \[ \sum_{j\text{ in its window}}s_j\ge c_4 l. \tag{96}\] There is at most one final jumping piece at each spatial depth along an actual input path, although membership splitting may have preceded it. For any finite family of marked starting indices, select disjoint windows whose triples cover the union, for example by successively taking a longest remaining window. The number of starting indices is no larger than a constant times the sum of the selected window lengths. By [eq:07-marked-window], this is at most \(C\sum_j s_j\), since the selected windows are disjoint. This proves the interval charging bound for variable window lengths as well as for fixed \(l\).

Globally, the unlabelled full spatial entropy budget of 16 is \(O(d)\) when live pieces occur. Apply the interval bound with the one selected scalar level per index. The marking probability and the state law imply \[\sum_{\rm live\ pieces}\mathbf U(p)\alpha_e e_{p,b}\mathbf1_{\rm bad} =m_{\rm top}\mathbb E_{\mathbf P} \sum_{\rm live\ post\ states}q\mathbf1_{\rm bad} \le2m_{\rm top}\mathbb E_{\mathbf P}(\text{number of marks}) \le Cd.\] Only a finite spatial extension is needed for any finite selection of windows; the bound for the full sum follows by nonnegativity. This also handles arbitrarily small selected scalar levels.

For a fixed main level, \(l_b\) is constant along the live path. Windows wholly before the common cutoff use only its \(O(h)\) truncated unlabelled bit budget. At most \(l_b\) starting indices straddle that cutoff. The truncated budget remains valid on paths that transferred earlier: keep their membership state fixed and continue their spatial sampling. Therefore the main-level weighted edge sum is \(O(h+l_b)\). There are \(O(\log h)\) main levels and \(l_b=O(\log d+\log(1/b_0))\) on them, proving (ii).

For (iii), use \(\mathbf P_e\) and 17, with no side label, in the same proof. The state conversion now has root mass normalization one, giving \(Cd_1\). Starting instead at a live post state \(p_0\), the conversion leaves a factor \(m_{p_0}/\alpha\le2\), and the forward entropy budget is \(Cd\). Thus the expected forward sum of \(e_{p,b}\mathbf1_{\rm bad}\) under \(\mathbf U_{p_0}\) is at most \(Cd\). At a bad main jump \(e_{p,b}\ge cb^2\); dividing gives (iv). ◻

Proof of the cover assertions. At a stabilized live node, a separated high collection of size \(\lceil e^{k_{b/2}}\rceil\) would request another update. The computation levels include \(b/2\). Thus a maximal collection has at most this size and covers all high elements of \([D]\) by the indicated symmetric neighborhoods.

For scalar lists, Parseval applied to \(a\mathbf1_{p'}\) on each prospective child gives \[\sum_{u\in\mathbb Z}|f_{p'}^u|^2 =\frac{1}{\alpha^2|p'|^2}\int_{p'}a^2 \le\frac{C e^d}{\alpha|p|}.\] After rotating by the phase at a point of \(p'\), its moments vary by at most \(C|u-u'||p|\). Around each separated representative take an integer neighborhood of radius \(c_7b^4/(3|p|)\). These neighborhoods are disjoint; each contains at least \(c b^4/|p|\) integers, with the bound also true when that number is less than one. On one of the two children their moments are still at least \(c b\). Summing their squared moments over the two children bounds the list length by \(C e^d/(\alpha b^6)\le\exp(C(d_1+\log(1/b)))\). For the final inequality use \(\alpha\ge e^{-d}\) on a live plateau and the definition of \(d_1\) on a static plateau.

For the transfer from one node to another, the phase of any signed sum \(v\in[D]\) is approximated by the corresponding product of rounded phases with uniform error at most \(c_5b^6\). Scalar moments consequently change by \(O((c_5+c_6)b^6)\) between a prospective child measure and the stored post measure if no refresh occurs. For the main functional, if \(\mu\) is a joint mass measure of input phase and side value, write \(M\) for its side marginal and \(f\) for its phase moment. Then \[ \int\frac{|f|^2}{M} =\sup_{|\gamma(z)|\le1} \int\bigl(2\operatorname{Re}(\gamma(z)\chi_v)-|\gamma(z)|^2\bigr) \,d\mu. \tag{98}\] The tests have absolute value at most three. Phase rounding contributes at most twice the phase error times the total mass, which is at most four; total variation contributes at most three times the distance. Hence the same \(O((c_5+c_6)b^6)\) transfer applies to the main functional. A prospective child high at \(0.9b\) therefore makes the stored post law high with ample slack above \(b/2\). The scalar triangle inequality and the convexity of \((M,f)\mapsto |f|^2/M\) imply that at least one prospective child of that stored post law is high at \(b/2\). Its signed sum belongs to the stored cover. If a fresh snapshot is born at the current node, use its prospective cover directly. This proves the transfer assertion in every case. ◻

Proof of the birth count. Each rounded coordinate is observed only once, when appended, and costs at most \(C\log(CD_{\max}/b)\) in conditional entropy. The successive coordinate spaces increase by retaining all previous coordinates. Before cap breach there are at most \(D_{\max}\) new coordinates on a path. Thus 17 gives \[ \mathbb E_{\mathbf U_e}\sum_p \int\frac{|D_{\rm jump}|^2}{M} \le C d_1+C D_{\max}\log(CD_{\max}/b). \tag{99}\] Here \(M\) has the full coordinate list available at that jump. A Fisher term computed after forgetting some coordinates is smaller, by conditional Jensen. This permits comparisons in old coordinate spaces while charging all of them to [eq:07-rounded-fisher].

Start a comparison interval at each snapshot’s post state in its fixed coordinates. If its next replacement is caused by an append, or if the cap is breached, end the old comparison before that node’s jump, in the old coordinates. Intervening removals at that node can be included. If the next replacement is caused by distance with no append, include its node’s jump in the old comparison and end at the selected child pre measure. The new snapshot nevertheless starts at that trigger node’s post measure, before this same bit. A terminal interval ends at the plateau stop. 2 records this order. Inclusion of a trigger bit is predictable, because the trigger is a test of both prospective children before either is selected.

On one comparison interval let \(k\) be each removed positive joint mass measure, expressed in its fixed coordinate space. Retain \(k\) unchanged after its removal and let \(K\) be the sum retained so far. Then \[N=M+K\] is a positive measure martingale under the uniform output bits. At a kill, \(M\) loses precisely the measure added to \(K\). At a spatial bit its two values are \(N\pm D_{\rm jump}\), with \(|D_{\rm jump}|\le M\le N\). In particular the martingale starts from the snapshot measure \(M_*\), and all later measures are absolutely continuous with respect to \(M_*\): a zero coordinate set remains zero under positive child averaging and removals.

Use generalized relative entropy for finite measures, \[\mathcal E(N\mid M_*)= \int(n\log n-n+1)\,dM_*,\qquad n=dN/dM_*.\] At a spatial bit, writing \(t=D_{\rm jump}/N\), its average increment is \[\int \frac N2\bigl((1+t)\log(1+t)+(1-t)\log(1-t)\bigr) \le C\int\frac{|D_{\rm jump}|^2}{N} \le C\int\frac{|D_{\rm jump}|^2}{M}.\] The scalar ratio in this inequality is bounded on \(-1\le t\le1\), with its limit at zero understood. Kills leave \(N\) unchanged. Bounded stopping in the finite-depth tree therefore bounds the expected terminal entropy by the expected Fisher sum on the comparison interval.

At a distance trigger, one of the two prospective children differs from \(M_*\) by more than \(c_6b^6\), so the selected child has this property with conditional probability at least one half. On that event either \(\|K\|\ge c_6b^6/2\), or \(\|N-M_*\|_{\rm var}>c_6b^6/2\). On the complementary event \(\|K\|<c_6b^6/2\), the latter alternative holds, \(N\) has mass at most \(4+c_6b^6/2\), and \(M_*\) has mass at most two. The scalar inequality \[\frac{(x-1)^2}{1+x}\le C(x\log x-x+1),\qquad x\ge0,\] followed by Cauchy–Schwarz gives \[\|N-M_*\|_{\rm var}^2 \le C\bigl(N(\Omega)+M_*(\Omega)\bigr)\mathcal E(N\mid M_*),\] where \(\Omega\) is the fixed observation space of the comparison interval. Thus the latter event forces \(\mathcal E(N\mid M_*)\ge c b^{12}\). Conditional on the comparison start, the probability that its next replacement is a distance trigger is at most \[ C\mathbb E\left[ b^{-6}\sum_{\rm interval}\xi_p +b^{-12}\sum_{\rm interval} \int\frac{|D_{\rm jump}|^2}{M} \,\middle|\,\text{comparison start}\right]. \tag{100}\] Indeed the far-child event has at least half the trigger probability, and the preceding deterministic alternatives charge it to removals or to terminal entropy, whose expectation was just bounded.

Sum [eq:07-trigger-charge] with the probabilities of the starts. Every jump is in at most two comparison intervals: at a distance trigger it is the final bit of the old interval and the first bit of the new one. Appends stop old comparisons before their jump. Removals likewise have bounded overlap. By [eq:07-kill-bounds,eq:07-rounded-fisher], distance triggers contribute the last two terms in [eq:07-snapshot-count]. Initialization contributes at most one, and append replacements at most \(D_{\max}\). This proves the count. No coordinate is re-observed merely because a snapshot is replaced, and the conditional argument did not condition on a realized side or rounded value. ◻

Proof. Freeze the spatial phase \(\chi_{u-v}\) at any point of \(p\). The normalized scalar error on a prospective child is at most \(C|u-v||p|\), by its mass bound. In the main case conditional Cauchy–Schwarz gives \[\left|\sqrt{G_{p'}^u}-\sqrt{G_{p'}^v}\right| \le\left(\frac1\alpha\mathbb E_{p'} [a|\chi_{u-v}(Y)-\chi_{u-v}(y_p)|^2]\right)^{1/2} \le C|u-v||p|.\] Thus \(v\) is high at \(0.9b\), since \(\sigma\ll b_0\) and the scalar prefactor is small. By 20, it is covered by a stored \(s\). If that snapshot was born at \(q\supseteq p\), its main cover gives \(v-s=n+j\), with \(\Delta_A(n)\le r_{\rm sep}\) and \(|j||q|\le\sigma\). Set \(a'=u-v+j\). Then \(|a'||p|\le2\sigma\). The channel \(A\) is fixed throughout the plateau, so \(n\) retains its metric bound. The scalar cover instead gives \(|v-s||q|\le c_7b^4\), and hence \(|(u-v)+(v-s)||p|\le(c_7+c_8)b^4\). Fix this \(s,n,a'\) at activation; all their spatial error bounds only improve on descendants.

Now let \(p_0\) be the first non-bad high jump before any activation, if one exists. By [eq:source-14] there is a signed combination \(v\in[D]\) at that node with \[|u-v||p_0|\le P(D_{\max},d_1,1/b)\] for a fixed polynomial \(P\). The same signed combination remains available as the list grows. After \(r\) further depths the left side with the new interval is at most \(2^{-r}P(D_{\max},d_1,1/b)\). For \[r\ge C\log(CD_{\max}d_1/b)+C\log(1/\sigma)\] this is at most the relevant activation tolerance, \(\sigma\) or \(c_8b^4\). Any subsequent high jump then activates, whether or not it is bad. Hence every non-bad high jump strictly before first activation lies in the one depth block beginning at \(p_0\) of the claimed length. If no such \(p_0\) exists there is no missed non-bad high jump. This proves the assertion and completes 18. ◻

Proof. The elementary inequality \(\cosh x\le e^{x^2/2}\) shows that \[\exp\left(\theta\sum_{i<n}c_i r_{i+1} -\frac{\theta^2}{2}\sum_{i<n}c_i^2\right)\] is a nonnegative supermartingale starting at one. Stop at the first crossing of \(e^t\) to obtain the asserted maximal inequality. Everything is in finite depth, so optional sampling needs no limiting argument. Starting the same calculation with conditional expectation given the origin proves the conditional assertion. Predictable masks are absorbed in \(c_i\). ◻

Proof. Identify a complex moment with a point in \(\mathbb R^2\) and set \[\psi(x)=b^{1/2}\big((|x|^2+b^2)^{3/4}-b^{3/2}\big).\] On \(|x|\le4\) one has \(0\le\psi(x)\le Cb^{1/2}\) and \(|\nabla\psi(x)|\le Cb^{1/2}\). More precisely, \[\nabla^2\psi(x) =\frac32 b^{1/2}(|x|^2+b^2)^{-5/4} \left((|x|^2+b^2)\operatorname{Id}-\frac12 x x^{\mathsf T}\right).\] Its least eigenvalue is at least \(\frac34 b^{1/2}(|x|^2+b^2)^{-1/4}\). Consequently it is at least \(c b^{1/2}\) throughout that ball, and at least \(c(C_3)>0\) on \(|x|\le C_3b\).

Define the nonnegative averaging drift and the signed fluctuation by \[\delta_p=\frac{\psi(f_p+u_p)+\psi(f_p-u_p)}2-\psi(f_p),\qquad n_p=\frac{\psi(f_p+u_p)-\psi(f_p-u_p)}2.\] Taylor’s formula on the two segments \(f_p\pm t u_p\), \(0\le t\le1\), gives \[ \delta_p\ge c b^{1/2}|u_p|^2, \qquad \delta_p\ge c(C_3)\eta_p|u_p|^2, \qquad n_p^2\le Cb|u_p|^2\le Cb^{1/2}\delta_p. \tag{102}\] For the second inequality the masked segment lies in the ball of radius \(C_3b\), since its endpoints do. The last inequality follows from the gradient bound and the first inequality.

At the actual pre-child the potential is exactly \(\psi(f_p)+\delta_p+r_{j+1}n_p\). A removal of normalized mass \(\xi\) changes the complex moment by at most \(\xi\), and hence changes \(\psi\) by at most \(Cb^{1/2}\xi\). Telescoping from birth to any prefix end therefore gives \[\sum\delta_p\le Cb^{1/2}(1+K_e)-\sum r_{j+1}n_p.\] Apply 22 to the negative fluctuation with \(\theta=\gamma b^{-1/2}\), where \(\gamma>0\) is a sufficiently small numerical constant. By [eq:paths-scalar-drift] its quadratic term is at most \(\frac12\sum\delta_p\). Outside probability \(e^{-t}\) this proves, on every prefix, \[\sum\eta_p|u_p|^2\le Cb^{1/2}(1+K_e+t).\] Now \(\eta_pu_p\epsilon_j\) is known in \(\mathcal F_{j+1}\) before \(r_{j+2}\). Apply 22 to the real and imaginary components of this delayed transform with \(\theta=b^{-1/4}\). Their quadratic sums are bounded by the preceding display. Thus every prefix transform has absolute value at most \(Cb^{1/4}(1+K_e+t)\) except on probability \(Ce^{-t}\). Subtracting the two prefixes bounding any contiguous interval proves [eq:source-15]. This subtraction retains precisely the fixed mask \(\eta_p\) within the interval. ◻

Proof. Child averaging gives \(M_+(v_+-v)=\mathfrak a-vD\) and \(M_-(v_--v)=-(\mathfrak a-vD)\). Expansion around \(v\) proves the first identity. If both child masses are positive, it also gives \[g_z=\frac{M|\mathfrak a-vD|^2}{M^2-D^2}.\] This implies the innovation inequality. If a child mass is zero, the corresponding moment is zero and \(\mathfrak a-vD=0\), giving the same inequality. Write \(e=\mathfrak a-vD\). Expanding the difference of the two child energies yields \[U_p=\int D|v|^2\,dz+2\operatorname{Re}\int\overline v e\,dz+R, \qquad |R|\le g.\] Cauchy–Schwarz bounds the first two integrals in absolute value by \(\sqrt{GJ}\) and \(\sqrt{Gg}\), respectively. Since \(G+g=(G_++G_-)/2\le\max(G_+,G_-)\), squaring proves [eq:paths-energy-noise]. The decomposition \(\mathfrak a=vD+e\) gives \[\int|\mathfrak a|\,dz\le\sqrt{GJ}+\sqrt{\left(\int M\,dz\right)g} \le\sqrt{GJ}+\sqrt{2g},\] which proves [eq:paths-moment-variation].

For the removal assertion, the energy has the variational expression \[\int\frac{|f|^2}{M}\,dz =\sup_{|\gamma(z)|\le1} \int\big(2\operatorname{Re}(\overline\gamma f)-|\gamma|^2M\big)\,dz.\] Removing \(k_M\ge0\) and \(k_f\) with \(|k_f|\le k_M\) changes every test in this supremum by at most \(3\int k_M=3\xi\). Both the old and new moment-to-mass ratios have modulus at most one, so the same test class represents both energies. Finally telescope [eq:paths-energy-noise] over the entire future stopped plateau path. Its martingale terms have zero conditional expectation, its terminal pre energy is at most \(4\), and the removals have expected total at most \(2\). This gives the first bound in [eq:paths-forward-budgets]. The other two are 17. ◻

Proof. Telescope the exact energy identity of [eq:paths-energy-noise]. Initial and terminal energies are bounded by \(4\) and removals cost at most \(3\xi\). On an exceptional jump, \(|U_p|\le4\le4e'_p\), so pay its noise directly. On the remaining jumps, [eq:paths-energy-noise] gives \(|U_p|^2\le Cb^2(J_p+g_p)\). Apply 22 to minus this remaining noise with parameter \(\theta=\gamma/b\). Its quadratic bound is \(C\gamma b\sum(J_p+g_p)\). Choose \(\gamma\) small enough to absorb the \(g\) term, using \(b\le1\). Its other term is \(Cb t\), which proves the simultaneous prefix assertion. ◻

Proof. We prove the norm estimate using both signs of a two-step block. Separate contributing depths into their two parities. For one parity start at its first depth in the run and group successive spatial jumps into blocks \(j,j+1\), with \(j\) contributing to this parity. Only complete blocks lying in the prefix will be used in the norm telescope. Denote the accumulated transform for this parity at the block start by \(W^{(0)}\), and put \[X_0=(W^{(0)},f_0,\lambda M_0),\qquad \Phi=|X_0|=\big(|W^{(0)}|^2+|f_0|^2+\lambda^2M_0^2\big)^{1/2}.\] The complex coordinates are viewed as pairs of real coordinates. Subscript \(0\) denotes the first post state. After its sign \(r=r_{j+1}\), write \((\bar M,\bar f)\) for the actual pre-child, and \((M_1,f_1)\) for its post state after removals \((k_M,k_f)\), where \[\bar M=M_0+rD_0,\quad \bar f=f_0+r\mathfrak a_0,\quad M_1=\bar M-k_M,\quad f_1=\bar f-k_f, \quad k_M\ge0,\quad |k_f|\le k_M.\] Here and in this proof these are pointwise identities in \(z\); in particular \(\int k_M=\xi_{j+1}\). At the end of the second jump, before its child’s processing, the change in \(X_0\) is exactly \[ \Delta=\big(\mathfrak a_0\epsilon_jr',\;r\mathfrak a_0-k_f+r'\mathfrak a_1, \lambda(rD_0-k_M+r'D_1)\big),\qquad r'=r_{j+2}. \tag{109}\]

We first prove the required pointwise quadratic estimate. Put \[q=(|v_0|^2+\lambda^2)^{1/2},\qquad H=M_0q\le\Phi, \qquad j_i=\frac{D_i^2}{M_i},\qquad e_i=\mathfrak a_i-v_iD_i.\] For \(M_0>0\), \(q\ge\lambda\) and \(|v_0|^2/q\le1\). Positivity of the child masses and of the removed density gives \[ 0\le M_1\le\bar M\le2M_0, \quad 0\le k_M\le\bar M\le2M_0, \quad |D_i|\le M_i, \quad |e_i|^2\le M_i g_{i,z}. \tag{110}\] There is also a comparison of the child’s post mean with the starting mean: \[ M_1|v_1-v_0|^2\le4g_{0,z}+8k_M. \tag{111}\] To verify it, let \(\bar v=\bar f/\bar M\) when \(\bar M>0\), and zero otherwise. The actual child’s term in the definition of \(g_{0,z}\) gives \(\bar M|\bar v-v_0|^2\le2g_{0,z}\). If \(M_1=0\), the left side of [eq:paths-child-mean] is zero. If \(0<M_1\le\bar M/2\), then \(M_1\le k_M\) and the bound \(|v_1-\bar v|\le2\) gives \(M_1|v_1-\bar v|^2\le4k_M\). If \(M_1>\bar M/2\), the identity \[M_1(v_1-\bar v)=k_M\bar v-k_f\] instead gives \(M_1|v_1-\bar v|^2\le4k_M^2/M_1\le4k_M\), since \(k_M<M_1\). Thus the same bound covers every intermediate or arbitrarily small remaining mass. The squared triangle inequality, and \(M_1\le\bar M\), now prove [eq:paths-child-mean].

Splitting \(\mathfrak a_0=v_0D_0+e_0\) and retaining the factor \(q\) yields \[ \frac{|\mathfrak a_0|^2}{H}\le2j_0+\frac{2g_{0,z}}\lambda. \tag{112}\] For the child jump use the three terms \(\mathfrak a_1=v_0D_1+(v_1-v_0)D_1+e_1\). Their separate squared ratios obey \[\begin{align*} \frac{|v_0D_1|^2}{H}&\le2j_1,\\ \frac{|v_1-v_0|^2D_1^2}{H} &\le\frac{2}{\lambda}M_1|v_1-v_0|^2 \le\frac{8g_{0,z}+16k_M}{\lambda},\\ \frac{|e_1|^2}{H}&\le\frac{2g_{1,z}}\lambda. \end{align*}\] The factor \(M_1/M_0\le2\) supplies the first and third bounds; the second uses \(|D_1|\le M_1\) and [eq:paths-child-mean]. In particular no lower bound on \(M_1/M_0\) is used. Hence \[ \frac{|\mathfrak a_1|^2}{H} \le6j_1+\frac{24g_{0,z}+6g_{1,z}+48k_M}{\lambda}. \tag{113}\] The mass-coordinate and removal terms satisfy \[\frac{\lambda^2D_0^2}{H}\le j_0, \qquad \frac{\lambda^2D_1^2}{H}\le2j_1, \qquad \frac{k_M^2+|k_f|^2}{H}\le\frac{4k_M}{\lambda}.\] These follow again from [eq:paths-positive-domination] and \(0<\lambda\le1\). If \(M_0=0\), all the masses, half-differences, and removals in [eq:paths-two-step-increment] are zero by positivity, so \(\Delta=0\) whether or not \(W^{(0)}\) is zero. This deals with every zero denominator without an approximation argument.

For \(\Phi>0\), concavity of the square root gives the global norm bound \[|X_0+\Delta|\le\Phi+\left\langle\frac{X_0}{\Phi},\Delta\right\rangle +\frac{|\Delta|^2}{2\Phi}.\] Combining the preceding pointwise inequalities and integrating proves \[ \int\frac{|\Delta|^2}{2\Phi}\,dz \le C(J_0+J_1)+C\lambda^{-1}(g_0+g_1+\xi_{j+1}). \tag{114}\] The absolute Fisher coefficient results from the estimates of \(v_0D_i\) with \(q\), rather than replacing \(q\) by \(\lambda\) in those terms.

It remains to control the integrated linear term and its timing. Write \(\Gamma_0=X_0/\Phi\), with value zero where \(\Phi=0\). Its norm is at most one. The linear term is \[r L_0+r'L_1+L_{\rm kill},\] where \(L_{\rm kill}\) has absolute value at most \(2\xi_{j+1}\), and \(L_0,L_1\) are real integrated coefficients. Specifically \(L_0\) pairs \(\Gamma_0\) with \((0,\mathfrak a_0,\lambda D_0)\), whereas \(L_1\) pairs it with \((\mathfrak a_0\epsilon_j,\mathfrak a_1,\lambda D_1)\). By [eq:paths-moment-variation] and \((\int|D_i|)^2\le(\int M_i)J_i\le2J_i\), their squares satisfy \[ |L_0|^2+|L_1|^2 \le C\sum_{i=0,1}\big((\lambda^2+G_i)J_i+g_i\big). \tag{115}\]

At a block start \(W^{(0)}\) is \(\mathcal F_j\)-measurable: the previous output of the same parity, if present, used \(r_j\). Thus \(L_0\) is known before \(r_{j+1}\). After that bit the removals, second post state, and \(\epsilon_j\) are all known, so \(L_1\) is known before \(r_{j+2}\). Form one scalar sign scheme by including \(rL_0\) whenever the first jump is in the run, and including \(r'L_1\) only if the second jump is also in the run. Both inclusion decisions are known before their respective signs. The linear sum through the last complete block of any prefix is itself a prefix of this scheme. If the run stops after a first step, no first coefficient is retrospectively conditioned on the next validity decision.

On a nonexceptional included state \(G_i\le2C_4b^2\). At an exceptional state both \(G_i\) and \(J_i\) are at most \(2\), and \(e'_i\ge1\). Therefore \[G_iJ_i\le Cb^2J_i+Ce'_i.\] Apply 22 to the linear scheme with parameter \(1/\lambda\). Its quadratic term, by [eq:paths-linear-variance], is at most \[C\sum J_p+C\lambda^{-1}\sum(g_p+e'_p),\] because \(\lambda=b^{1/2}\) and \(b\le1\). The tail term is \(\lambda t\). All sums here can be restricted to the complete blocks of the prefix. At the first block \(W^{(0)}=0\) and \(\int\Phi\le C\). Between complete blocks, passing from a pre state to the next post state changes the integrated norm by at most \(2\xi\), by the norm’s Lipschitz property. Telescoping, using [eq:paths-norm-remainder], proves for the completed blocks the bound \[C\sum J_p+C\lambda^{-1}\left(1+\sum\xi_p+\sum e'_p+\sum g_p\right) +C\lambda t.\] At most one contributing output of this parity is unmatched at a prefix end. It costs at most \(\int|\mathfrak a_p|\le\int M_p\le2\), even if its delayed sign occurs after the run has stopped. Add this output directly. The other parity is started conditionally on reaching its first jump, one step later if necessary, and obeys the same bound with the same conditional failure estimate. Each prefix jump is used in at most two of the completed-block estimates. Finally apply [eq:source-16] on this prefix. Its \(g\) contribution becomes \(C\lambda^{-1}(1+\sum\xi+\sum e')+C(b/\lambda)\sum J+C(b/\lambda)t\). Since \(b/\lambda=\lambda\le1\), adding the two parity bounds gives [eq:source-17]. ◻

Proof. Start a run at the first inner-valid opportunity after birth, possibly at the birth jump itself. Follow consecutive outer-valid jumps, stopping before the first outer-invalid jump or at plateau end. After a break, start the next run at the first later inner-valid opportunity. These are predictable rules: both prospective child energies and the exceptional indicator are known before the jump sign. Every contiguous inner-valid interval lies in one of these outer-valid runs.

We first bound the number of run starts conditionally on the birth prefix. A start on an exceptional jump can be charged to that jump. 19 bounds the expected number of these by \(d\mathop{\mathrm{poly}}(h)\); there are none when \(b=1\). At a nonexceptional start, \(G_{\rm start}\le C_4b^2\). If its run breaks, include the first invalid jump in a comparison interval, although the transform estimate stops before it. At that jump \(\max(G_+,G_-)>2C_4b^2\). Conditional on the prefix there, with probability at least \(1/2\) its actual pre-child energy exceeds \(2C_4b^2\). Mark such a break. The comparison intervals for different runs are disjoint, including their invalid jumps.

Let \(Q\) denote one such start-to-break comparison interval, and put \(\mathcal M_Q=\sum_{p\in Q}r_{j(p)+1}U_p\). By the exact energy identity and the removal bound, a marked break implies \[C_4b^2\le\sum_{p\in Q}g_p+3\sum_{p\in Q}\xi_p+|\mathcal M_Q|.\] Consequently, with a numerical constant depending only on \(C_4\), \[ \mathbf1_{\{Q\text{ marked}\}} \le Cb^{-2}\sum_{p\in Q}(g_p+\xi_p)+Cb^{-4}|\mathcal M_Q|^2. \tag{117}\] To use orthogonality, first include every start-to-break interval of this type and the possible unfinished terminal interval, without conditioning on a mark. Its starting rule and inclusion through the invalid bit are predictable. Thus stopped martingale orthogonality gives \[\mathbb E\sum_Q|\mathcal M_Q|^2 =\mathbb E\sum_{p\in\bigcup Q}U_p^2 \le C\mathbb E\sum_p(J_p+g_p),\] using [eq:paths-energy-noise] and \(\max(G_+,G_-)\le4\). All expectations here are conditional at birth. Each nonexceptional break is marked with conditional probability at least \(1/2\), so [eq:paths-marked-break,eq:paths-forward-budgets] imply \[\mathbb E\#\{\text{nonexceptional-start runs that break}\} \le Cb^{-2}+Cdb^{-4}.\] At most one final run fails to break. Including exceptional starts proves a bound \(P(d,b_0^{-1})\) for all starts, uniformly in \(s\). The factor \(\mathop{\mathrm{poly}}(h)\) is absorbed in a fixed power of \(b_0^{-1}\).

Within each outer-valid run, also start an estimate whenever the accumulated \(J\) since the preceding origin reaches one. More precisely, after including the jump that reaches this threshold, reset the counter and use the next jump as a new origin if it remains in the run. Each such origin’s estimate continues to that run’s same break or end. The counter decision is known at this next origin; no future bit is used. The number of additional origins is at most the total \(J\) of the path, and \(J_p\le\int M_p\le2\) bounds a threshold overshoot. Therefore their conditional expected number is at most \(Cd\) by [eq:paths-forward-budgets].

Apply 26 conditionally at every origin, with the same parameter \(t\). Summing its conditional failure probabilities weights each origin by its probability of being reached. The expected origin count just proved bounds the resulting probability by \(C P(d,b_0^{-1})e^{-t}\). On the event of simultaneous success, fix any desired interval \(I\) and choose the latest origin \(q\) in its outer-valid run at or before its first jump. The total \(J\) between \(q\) and that first jump is at most \(3\); indeed the counter is below one before a threshold crossing, and one jump adds at most two. The interval transform is the difference of two prefixes from \(q\). Their Fisher sums add to \[\sum_{p\in I}J_p+2\sum_{q\le p<\min I}J_p \le\sum_{p\in I}J_p+6.\] Their removal and exceptional sums are bounded by twice \(K_e\) and \(E_{e,b}\), respectively. The extra constant is absorbed by \(b^{-1/2}(1+K_e+E_{e,b})\). The triangle inequality in \(L^1(dz)\) then proves [eq:paths-inner-interval]. This argument also permits the interval to begin long after the snapshot’s replacement. ◻

Proof. Begin with a deterministic dyadic cap \(D_{\max}=2^m\), \(m\ge0\). The broad list is constructed independently of this cap. The capped snapshot scheme creates snapshots only while its list length is at most \(D_{\max}\); estimates for representatives already born continue to the plateau end. By 20, the expected number of births is bounded by a fixed polynomial in \((D_{\max},d_1,1/b)\). The number of representatives in each snapshot is at most \[R_b^{\rm main}=\lceil e^{k_{b/2}}\rceil, \qquad R_b^{\rm sc}=\exp\big(C(d_1+\log(1/b))\big),\] as established in that lemma. Scalar estimates originate at these births. For each main representative, 27 bounds the conditional expected number of run and checkpoint origins by a fixed polynomial in \((d,b_0^{-1})\). For sufficiently large \(d\) this factor is also bounded by a fixed power of \(d\), because \(b_0^{-1}\le2h^{16}\le d\).

Here is the conditional union argument, which also applies when the number of origins is random. Enumerate predictable origins by their finite tree addresses and, within an address, by their representative indices. If \(B_o\) is the event that origin \(o\) is reached and an estimate starting there fails with deterministic parameter \(t\), then \[\mathbb P(B_o) \le Ce^{-t}\mathbb P(o\text{ is reached}).\] Sum this inequality over origins and then use their expected count. Thus the failure probability for a capped scheme is at most \(Ce^{-t}\) times its stated representative cardinality and polynomial count. No union over the signed span of the broad list is taken.

Choose sufficiently large fixed constants and define baseline parameters \[T_b^{\rm main}=Ck_{b/4}+C\log(Cd/b),\qquad T_b^{\rm sc}=C(d_1+\log(1/b)).\] They absorb the logarithms of the representative cardinalities and all polynomial factors except the cap. For a sufficiently large further fixed \(C_{\rm cap}\), use \[t=T_b+C_{\rm cap}\log(CD_{\max})+z\] in each deterministic capped scheme. Its failure probability is at most \(C2^{-2m}e^{-z}\), after increasing \(C_{\rm cap}\) if necessary. Summing over all dyadic caps gives \(Ce^{-z}\). These events are nested as \(z\) increases, since every right-hand side in the path estimates increases. Let \(Z_b\) be the least nonnegative integer \(z\) for which all these capped schemes succeed. Integer tail summation gives \[\mathbb P(Z_b>n)\le Ce^{-n},\qquad \mathbb E Z_b\le C,\] and \(Z_b\) is finite almost surely.

Only now choose a cap from the realized output path: let \(\widehat D\) be the least dyadic integer at least \(1+|D|_{\rm final}\) for the broad list at this level. Thus \(1+|D|_{\rm final}\le\widehat D<2(1+|D|_{\rm final})\), and its capped scheme never breaches the cap on this path. The simultaneous assertion over deterministic caps permits this selection without a stopping-time claim about \(\widehat D\). Set \[t_b=T_b+C_{\rm cap}\log(C\widehat D)+Z_b.\] Broad capture gives \(\mathbb E|D|_{\rm final}\le Cd_1b^{-C}\), so Jensen’s inequality yields \[\mathbb E\log(C\widehat D) \le C+\log\big(C(1+\mathbb E|D|_{\rm final})\big) \le C\log(Cd_1/b).\] This proves [eq:paths-main-parameter,eq:paths-scalar-parameter], using \(d_1=d\) for main levels and \(\log d_1\le d_1\) for scalar levels. Use 21 with this same cap and put \[H_b=C\log(C\widehat Dd_1/b)+C\log(1/\sigma).\] Its expectation satisfies [eq:paths-miss-parameter]. In the static case the optional term \(\log(1/\sigma)=40\log h\) is at most \(Cd\le Cd_1\); thus it causes no loss in the scalar plateau bound used below.

For each level the construction has a probability-one success event. Their countable intersection still has probability one. The resulting parameters depend on the plateau path and the level, but not on the integer frequency whose transform will be compared to these representatives. ◻

Proof. We first pass from 15 to modulated convolutions, then identify the periodic Hilbert transform.

Proof. Let \(\|f\|_\infty\le B\). The case \(B=0\) is immediate. Take the Fejér means \(P_\ell\) of \(f\). They are trigonometric polynomials satisfying \(\|P_\ell\|_\infty\le B\) and \(\|f-P_\ell\|_1\to0\). The latter fact follows from the approximate-identity property of the nonnegative, mass-one Fejér kernels and continuity of translations in \(L^1\).

Split \(f-P_\ell\) into the positive and negative parts of its real and imaginary components. Each nonnegative part \(q_\ell\) is at most \(2B\) and has mass \(m_\ell\to0\). If \(m_\ell=0\) its partial sums vanish. Otherwise normalize to \(\rho_\ell=q_\ell/m_\ell\) and choose \[d_\ell=d_*+\max\{0,\log(2B/m_\ell)\}.\] As \(m_\ell\to0\) through positive values, \(d_\ell\to\infty\), \(m_\ell d_\ell\to0\), and \(\rho_\ell\le e^{d_\ell}\). 29 and Markov’s inequality show, for each \(\eta>0\), \[\left|\left\{\sup_N|S_Nq_\ell|>\eta\right\}\right| \le C(\log d_\ell)^{-4} +\frac{Cm_\ell d_\ell}{\eta}\longrightarrow0.\] Applying this to the four component parts proves \(\sup_N|S_N(f-P_\ell)|\to0\) in measure.

For each \(\ell\), the partial sums of \(P_\ell\) are eventually equal to \(P_\ell\) itself. Consequently the measurable function \[A(x)=\limsup_{N\to\infty}|S_Nf(x)-f(x)|\] satisfies \[A(x)\le \sup_N|S_N(f-P_\ell)(x)|+|f(x)-P_\ell(x)|\] almost everywhere. Both terms on the right tend to zero in measure. For each \(\eta>0\) this bounds \(|\{A>\eta\}|\) by a quantity tending to zero. Thus \(A=0\) almost everywhere, as required. ◻

Proof of 1. It suffices to work in unit-period coordinates. Write \[f=f_{\mathrm{bd}}+\sum_{j\ge1}f_j,\qquad f_{\mathrm{bd}}=f\,\mathbf1_{\{|f|<e^2\}},\qquad f_j=f\,\mathbf1_{\{e^{2^j}\le|f|<e^{2^{j+1}}\}}.\] For each \(j\), split \(f_j\) into four nonnegative parts with coefficients \(1,-1,i,-i\), using the positive and negative parts of its real and imaginary components. Consider one such sequence \(q_j\), and write \(m_j=\int q_j\). Discard its zero-mass members. Put \[\rho_j=q_j/m_j,\qquad d_j=2^{j+1}+\log^-m_j.\] Then \(\int\rho_j=1\) and \(\rho_j\le e^{d_j}\). For all sufficiently large \(j\), 29 applies.

We claim \[ \sum_j m_jd_j<\infty. \tag{152}\] On the support of \(q_j\), \(\log|f|\ge2^j\), and \(q_j\le|f|\). Disjointness of the layers therefore gives \[\sum_j2^{j+1}m_j \le2\int_{\{|f|\ge e^2\}}|f|\log|f|<\infty.\] For the additional entropy term, if \(m_j\ge e^{-2^j}\), then \(m_j\log^-m_j\le2^jm_j\). If \(m_j<e^{-2^j}\), the monotonicity of \(t\log(1/t)\) on \((0,e^{-1})\) gives \(m_j\log(1/m_j)\le2^je^{-2^j}\). Both bounds are summable. This proves [eq:fourier-layer-cost].

Let \(G_j\) be the good set associated to \(\rho_j\). Since \(\log d_j\ge(j+1)\log2\), \[\sum_j|G_j^c|\le C\sum_j(\log d_j)^{-4}<\infty.\] Borel–Cantelli implies that almost every point belongs to all but finitely many \(G_j\). On the other hand, Tonelli’s theorem and [eq:source-18,eq:fourier-layer-cost] give \[\int\sum_j\mathbf1_{G_j}(x)\sup_N|S_Nq_j(x)|\,dx \le C\sum_jm_jd_j<\infty,\] where a finite number of initial layers may be omitted. Therefore, at almost every point, the partial-sum maxima of the tail layers are absolutely summable. Every individual \(q_j\) is bounded, so 30 also gives its full-sequence limit and the finiteness of its partial-sum maximum outside a null set. Restoring finitely many omitted layers causes no difficulty. Intersect these full-measure sets for the four component sequences and for \(f_{\mathrm{bd}}\).

The layers are summable in \(L^1\). For each fixed \(N\), Fourier coefficients can consequently be summed term by term; equivalently, the finite-rank operator \(S_N\) is bounded from \(L^1\) to \(L^\infty\). Thus \[S_Nf=S_Nf_{\mathrm{bd}}+ \sum_{j\ge1}S_Nf_j\] with the four component parts understood in the last sum. At every point of the full-measure set just constructed, the absolute sum of their partial-sum maxima is finite. Its tail tends to zero uniformly in \(N\). Take the limit first on a finite collection of layers, using 30, and then let the collection increase. The result is \(S_Nf(x)\to f_{\mathrm{bd}}(x)+\sum_jf_j(x)=f(x)\). All excluded sets are measurable, and only countably many are used. Changing back to \(x=2\pi y\) proves the stated theorem with normalized measure \(dx/(2\pi)\). ◻

Proof. The real Luxemburg space \(B=L^\Phi(\mathbb T;\mathbb R)\) is Banach. Since \(\Phi(2t)\le4\Phi(t)\), its underlying set is exactly the real \(L\log L\) class used in 1; moreover \(\|f\|_1\le\|f\|_\Phi/\log2\). Translations are isometries of \(B\) by invariance of \(\mu\). Each \(S_N\) is a real linear operator commuting with translations and is bounded from \(B\) into itself: indeed, \(\|S_Nf\|_\infty\le(2N+1)\|f\|_1\), and \(L^\infty\) embeds continuously in \(B\). These bounds need not be uniform in \(N\). By 1, \(S^*f\) is finite almost everywhere for every \(f\in B\). Stein’s theorem (Stein 1961, Appendix, Theorem 10), applied to the sequence \(S_0,-S_0,S_1,-S_1,\ldots\), therefore gives [eq:fourier-weak-l1] for real inputs; the signed supremum in that theorem is precisely \(S^*f\) for this sequence. For \(f=u+iv\), use \(S^*f\le S^*u+S^*v\) and \(\|u\|_\Phi,\|v\|_\Phi\le\|f\|_\Phi\), splitting the level at \(\lambda/2\). This proves the complex-valued assertion after enlarging \(C\) by a fixed factor. ◻