Almost-everywhere Fourier convergence in L log L

Proof. Consider probability laws on S^T\times TS, with coordinates (X^T,Z), having uniform one-letter marginals. Minimize

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

To check the expression inside this dual, set

For a conditional law \pi of X^T given Z=z, its entropy and cost, after subtracting the multipliers, equal

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 Equation (3.8).

The dual objective is concave in the tuple (a_1,\ldots,a_T): the negative logarithm in Equation (3.8) 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

For these multipliers, the full expression in Equation (3.8) is

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 Equation (3.4); 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

then gives Equation (3.7) 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

It follows from the chain rule that

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

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

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 Lemma 3.2 and put

These numbers are nonincreasing. Indeed conditioning decreases entropy, and exchangeability of the unrevealed coordinates gives

The chain rule and Equation (3.7) also give

The nonnegative deficits in this sum are nondecreasing. Therefore, for j<T,

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

For 0\le i<m_*, summing the differences over j cancels all interior terms:

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 Equation (3.13) over j, with m=m_*, now gives

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, Lemma 3.3 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 Equation (3.11); projection contracts total variation and proves it for every smaller m.□

Proof. First consider sums under the correlated law \Psi, before introducing contexts. By Lemma 3.3, for every s\le T_0 the law of (X^s,\Gamma) has \mathcal C_\nu\le CE. Relative entropy to q gives

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

Since \sum_iX_i=Z_s-\Gamma, it follows that

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 Equation (3.11). 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

Interchanging U,V yields the corresponding absolute difference bound. Apply this with the common alphabet sS. The added error is at most

Indeed m_*\sqrt E/T\le d^{-1/2+o(1)} for fixed D_0, while Equation (3.3) 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 Equations (3.20) and (3.21) 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

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 Equation (3.17), 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

using Equations (3.11) and (3.20) and Lemma 3.3. 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

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:

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 Equation (3.23) 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 Equation (3.17) 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 Section 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 Lemma 3.6. 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

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

The rule consequently gives

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,

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

By Lemma 3.3, 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

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

This is a probability law on S^m by Equation (3.26). 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

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

Convexity of \mathcal C_\nu on mixing, followed by the full-vector identity of Lemma 3.6, bounds K_m by the sum of the right-hand sides of Equations (3.27) and (3.28).

It remains to verify the scale of all additional terms. Since w^2=\sqrt{\log d} and r\le Te^{-w^2}/2,

Also \delta\log(1/\delta)\le1/e, so the first term of Equation (3.28) is at most r/e=o(d/h^2). For its second term, Equation (3.25) gives \delta\le d^{-1/2+o(1)}, and mr\le T_0/2<d^2 allows the sumset hypothesis to give

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 Equation (3.24).□

Proof. Independence of the pairs gives

which proves Equation (4.1).

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

where each (Y_a,V_a) has the sum-and-context law of an independent (m-1)-letter block. Set

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

For the subtracted joint entropies, condition both terms on both old outputs:

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

The assertion follows.□

Proof. Normalize by

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.

Available updates. Suppose the desired K inequality fails at index j in a given state. Consider separately from that same state the full observations of Lemma 4.1 for m_{j,0}<m\le m_{j,1}. Let d_m\ge0 be their decreases in a_j, and c_m\ge0 their costs. Telescoping Equations (4.2) and (4.1) gives

For p_j>0, offers with c_m>2p_jd_m have total decrease less than \tau/2. The other offers have total decrease greater than \tau/2. There are at most m_* offers, so one satisfies

If p_j=0, all costs are zero and the same conclusion follows. For any target x\in(0,d_m], use a partial observation with probability x/d_m. Its actual decrease is at least x and its cost at most 2p_jx.

Why two visit orders are needed. The available update decreases a_j at a cost controlled by the current width p_j. Although both endpoints g_{m_{j,0}} and g_{m_{j,1}} decrease under refinement, their difference need not decrease. We will therefore stop working at an index when the difference between the g-value at its upper endpoint on entry and the g-value at its lower endpoint in the current state is too large relative to the cost already spent there.

Two comparisons determine the order of the search. When we visit indices in increasing order, their block-length ranges descend: the g-value at the upper endpoint on entry to the next visited index is bounded by the g-value at the lower endpoint on exit from the earlier index. These endpoint differences telescope in [0,1] and will control the cost of skipped work. Completed decreases of a_j telescope in the opposite index order, because a_j increases with j and decreases under refinement. The nested partition below uses increasing indices within a subblock to control skips, decreasing subblocks within a macroblock to control completed decreases, and increasing macroblocks to control the remaining skips. The numerical thresholds make the total cost O(h^{-2}).

Partitions and visit orders. Put

Take d large enough that N\ge4. Partition the first Nq_*n indices into N successive macroblocks, each containing q_* successive subblocks of n indices. There is room since

Process macroblocks in ascending index order; within a macroblock, process subblocks in descending order; within a subblock, process indices in ascending order. A subblock finishes when a_j at one of its indices has decreased by at least u since entry to that index. Discovery of the desired K inequality stops the whole search. The skip rules below can end an index or a macroblock earlier.

One index and one subblock. At index j, let c_0 be the cost spent there so far and put

This nonnegative quantity dominates the current p_j. Skip this index if

Otherwise check the desired K inequality. If it fails, take an offer from Equation (4.7). Write \Delta_j=a_j(\text{entry to }j)-a_j(\text{current state})<u for the decrease already achieved at this index, and choose the partial observation with target

Repeat until a skip, completed target, or discovery. The sum of the targets x in an index is at most u, since actual decreases are at least their targets and a clipped last target finishes the attempt. Each unclipped target equals d_m\ge\eta, so the loop is finite.

At every update the skip test has failed, whence

Starting at c_0=0, and using 1+t\le e^t, the cost at every stage satisfies

Write H,\ell for the highest and lowest block-length endpoints in the current macroblock and set

For successive skipped indices j<j' within a subblock, the block-length ranges descend, so m_{j',1}<m_{j,0}. Decrease over refinement time then gives

Thus the values of p at skips sum to at most P, including at every intermediate state in this subblock. A skipped index has c_0<\alpha_0(p-\delta_0)\le\alpha_0p and p>\delta_0. There are therefore fewer than 1/\delta_0=\sqrt n skips; all n indices cannot be skipped. Skipped attempts cost at most \alpha_0P, and there is at most one other, active or terminal, index attempt. By Equation (4.10), every prefix or completed run of the subblock costs at most

A completed subblock without discovery must consequently reach a target.

One macroblock. Let c_1 be the cumulative cost in the current macroblock. At boundaries before or after subblock runs, skip the rest of the macroblock if

Target indices decrease strictly between completed subblocks. For successive such indices j>j', monotonicity in index and time gives

Their actual targeted decreases telescope to at most one. At most 1/u subblocks can complete targets, whereas there are q_*>1/u subblocks. Thus this macroblock must be skipped or discover the desired inequality before it can be exhausted.

For a completed subblock after which no macroblock skip is made and processing continues, apply Equation (4.12) with the new P, and then the failure of Equation (4.13):

Put \beta_*=\alpha_0/\alpha_1=1/(1000\log N) and \delta_*=\delta_1+n^{-2/5}. Iteration over at most 1/u such runs yields

Indeed n\ge N^5, so n^{-2/5}\le N^{-2}. Also -\log(1-\beta_*)\le2\beta_*, and hence (1-\beta_*)^{-1/u}\le N^{1/500}. The factor multiplying \alpha_1 is at most N^{-249/500}+N^{-999/500}<1 for N\ge4. One last or partial subblock costs at most 2\alpha_0 by Equation (4.12) and P\le1.

Across macroblocks and termination. Macroblocks advance in index order, so their block-length ranges descend as in Equation (4.11). The values of P at macroblock skips sum to at most one. Their total cost is at most \alpha_1, and fewer than 1/\delta_1=\sqrt N macroblocks can be skipped. Since a macroblock cannot be exhausted without a skip or discovery, the whole search must discover the desired K inequality. Its loops are finite by the positive minimum offer before clipping. Total cost through discovery is bounded by

Both telescopes allow decreases caused by intervening refinements; see Figure 1.

Since h=4\log w and M\asymp w^2, both \log n and \log N are of order h. Thus 4\alpha_1\le C/h^2. Undoing the cost normalization proves Equation (4.6). Each new observation and mark has a finite alphabet, so the finite sequence leaves a finite-valued context.□

Completion of the proof of Lemma 3.1. Use the context W, index j, and high endpoint m=m_{j,1} supplied by Proposition 4.2. Put r=r_j and s=mr\ge L. Combining Equation (4.6) with the low-end bound Equation (3.24), preserved under refinement, gives

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

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

Subtracting \mathrm H(X^s\mid Z,\boldsymbol W) and adding the error cost therefore shows that \E C(\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

This uses Equations (3.11) and (4.6). 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

A zero-mean quantity is zero almost surely, which covers that case as well. Freeze this stack.

A large independent noisy-sum atom. Let p=\prod_i\nu_{w_i}, and compare the actual conditional law of (X^s,\Gamma) to the independent law p\times q. The map (X^s,\Gamma)\mapsto(X^s,Z) is invertible, and -\log q(\Gamma)=F_0+c(\Gamma). Thus

Let Q_Z be the sum law under p\times q. Data processing gives

Some integer z_* in the support of the actual output therefore has Q_Z(z_*)\ge e^{-F_0-CE}=q(0)e^{-CE}. All Q_Z masses are positive since q is strictly positive. Divide the convolution formula by q(0) and use the characteristic formula:

The last step takes the absolute value of the preceding integral, whose value is a positive real mass.

One region and one coordinate. Put \phi_i(\theta)=\E_{\nu_{w_i}}\chi_{gX}(\theta) and A(\theta)=\sum_i(1-|\phi_i(\theta)|^2). The bound 0\le|\phi_i|\le1 implies \prod_i|\phi_i|\le e^{-A/2}. Choose a numerical C_R larger than twice the constant in Equation (4.21), with a fixed additional margin, and set \mathcal R=\{A\le C_RE\}. Since E\ge d/h^2\ge1, the contribution of \mathcal R^c to the product integral is at most half its lower bound. The product is at most one, so

where \omega_{\mathcal R} is normalized restriction to \mathcal R. Apply Markov’s inequality to a uniform choice of coordinate, using Equations (4.19) and (4.22). One coordinate satisfies both

Only numerical factors are lost in the first bound. Write \mu=\nu_{w_i}.

A center and a subset valid for every weight. For independent X,\breve X\sim\mu,

Averaging over \omega_{\mathcal R} and then over \breve X selects x_0\in\operatorname{supp}\mu\subset S with

Prune by Markov’s inequality to a subset S'\subset\operatorname{supp}\mu of \mu-mass at least 1/2, on which every x satisfies

If the average defect is zero, its zero-defect set has full \mu-mass and can be used for S'. In all cases S' is nonempty.

Write t=\mu(S')\ge1/2 and v_0=|S'|/|S|. Binary data processing gives

Together with Equation (4.23), this implies

The constant is absorbed because d^2/(Eh^2)\to\infty.

Finally, let v be any probability measure on this same S'. By Equation (4.24), its averaged phase defect on \mathcal R is at most CE/s. Jensen’s inequality and L\le s yield

The region, center, and subset were fixed before v was chosen, establishing the conclusion for every probability on S'. The exponential constant is numerical: dependence on D_0 occurs in the entropy loss and in the sufficiently large threshold for d, whereas Equation (4.16) and all subsequent constant-factor selections have numerical bounds. This completes the proof.□

Proof. Expand each factor as

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

Absolute convergence justifies the expansion and proves nonnegativity. Differentiation under the integral yields

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

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 Equation (5.15). Apply Lemma 3.1 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

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

Put A_{\rm base}=A+S_p. Monotonicity of F and A_{\rm base}\preceq\widetilde A give

The first bracket is controlled by compression and the second by the tightening bound in Equation (5.7). Hence

The constant C_1 is numerical: the volume constant of compression is numerical, and the cap-dependent error in Equation (5.7) is o(t) after the fixed caps and A_0 have been selected.

To find a flat range, set

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 Equation (5.17), hence by C_1D_0d. At least one increment is at most dh^{-400}. Take its \lambda and D_i=\lambda B; this is Equation (5.5). Concavity along the B direction gives

which proves Equation (5.16) and the metric increment bound.

The input-only success set. For a regular test define the success set by

The expectation uses the specified type-A channel, rather than the sampled old observation. The expression has modulus at most one, and Equation (5.11), 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

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

Here l\ge1. On this intersection \Delta_A\le2r and |u|\le\sigma R_p/5, so convolution and Equation (5.3) imply

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 Equation (5.16) give

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

contrary to Equation (5.10).

Since R_p/|D_p|\le C/\sigma, including the case D_p=\{0\}, Equation (5.19) 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

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

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

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

The upper comparison follows from the observation count and large d. By Equation (5.2), the y integral before the clone normalization and the posterior division is at most

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 Equation (5.22), applying the moment tail bound at \beta/4, and summing over the clones gives

Indeed Equation (5.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 Equation (5.18) 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

Its conditional expectation is at most \sqrt{2\int BK_{A^+}}\le C\sqrt{t/\lambda}=O(h^{-100}) by Equation (5.16). 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 Equation (5.21). 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 Equation (5.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

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

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.

Caps, constant order, and finite termination

Let C_1 be the numerical constant bounding a relative metric cost by C_1t in Lemma 5.3, and let C_2 be its numerical regular gap-increase constant. Choose the numerical \varepsilon>0 there small enough for the cheap gap decrease, and take R_0=1000. Consider a prefix of successes for which the update hypotheses have been justified. The gap potential

starts at zero and is bounded below by an absolute constant. Here r begins at r_{\rm sep}/4 and increases by r_{\rm sep}/(10C_0h) at each addition, so r\le r_{\rm sep}/2 under the count cap. Telescoping its regular increases and cheap decreases gives

In the second inequality we used t=\varepsilon k_b on cheap successes. Regular successes also satisfy \varepsilon k_b\le t. Consequently, while \mathcal Q\le R_0d, the sum of all success k_b’s is at most C(R_0,\varepsilon,C_2)d. Since every k_b\ge d/h, the number of those successes is at most C'h. Choose C_0>C'+2. A first count breach without a charge breach would obey this same prefix bound, contradicting that choice for large d.

The form cap is also inductive. If the preceding main addition occurred at p_*, the spatial and metric estimates give

The spatial scale ratios telescope along a branch. Before a charge breach, Equation (6.5) and the count estimate therefore give F(A)\le\log R_*+C_*d for a sufficiently large fixed C_*. The initial case is A=0 with p_*=I. At the next update, the flat-increment condition Equation (5.5) is supplied by the update itself. Thus the assumptions needed to construct each successive update have been established from its predecessors.

Fix D_0,P_0 in the compression application using these caps, then fix A_0 sufficiently large for the cardinality loss, and finally take d sufficiently large for all required asymptotic inequalities. The constants C_1,C_2 and the choice of \varepsilon precede the caps; their numerical nature is what permits this order. A regular success that first crosses the charge cap adds at most D_0d and is followed immediately by transfer. Hence that final overshoot only changes the absolute constants in the claimed path budgets. No subsequent update uses a form cap for this terminal form. The energy estimate in Equation (5.7) remains valid for the labels drawn at that success, as it uses the flat-increment and count bounds. This proves all the deterministic budget assertions.

At a fixed spatial node, the number of successes along any recurrence path is bounded by the count cap. Between successes, every failure multiplies m by at most 1-c(b_0/8)^2. Since m\le e^d, only finitely many consecutive failures are possible before m<e^{-d}. There is a uniform finite bound, depending on d but not the node, on the length of this local binary recursion. Its branching is finite; induction over the finite spatial depth proves termination of the entire procedure. Integer frequencies and finite offending collections can be chosen in a fixed enumeration. Polarization uses measurable bounded signs of the moment functions, and all membership probabilities are computed from their channel laws. Thus all resulting input sets are measurable. No joint choice over different dyadic grids is required.

The spatial likelihood and membership costs

At a positive-mass discrete state with density a on p,

This follows directly by restricting the initial density to the recorded spatial interval and membership sets. Define, at each such state,

A membership outcome with probability q>0 replaces m by qm and increases B_{\rm mem} by -\log q, so L_{\rm sp} is unchanged. At a spatial step its increment is \log(2q), where q is the conditional probability of the actual child under the unlabelled true law. It follows that

Indeed the conditional sum over positive-probability children is \sum_q q/(2q)\le1; equality need not hold if a child has zero mass. Thus e^{-L_{\rm sp}} is a nonnegative supermartingale starting at one. It remains so after stopping or after keeping the piece fixed and revealing further spatial bits.

A success has surprisal at most C(1+\log(1/b)) because \delta\ge cb^2; a cheap success has zero surprisal. The deterministic k_b budget and

bound the total success surprisal by Ch on every path. Between one success and the next, let F accumulate only failure surprisal. Until that stretch ends, e^F is unchanged at spatial steps; at a membership test keep it multiplied by (1-\delta)^{-1} on failure and send it to zero on success. The resulting process is a nonnegative supermartingale starting at one. Therefore its maximal inequality implies, conditionally on the stretch’s start,

Here F_{\rm final} includes the failures preceding a terminal success, even though the auxiliary process is then sent to zero. There are at most Ch+1 stretches. Their conditional second moments are at most 2; pad with zero stretches and use the triangle inequality in L^2. This proves \|B_{\rm mem}\|_2\le Ch. The same maximal inequality applied to e^{-L_{\rm sp}} bounds the L^2 norm of \max(-L_{\rm sp})_+ by an absolute constant. Since m_{\rm top}\ge1/h,

which proves Equation (6.3), including the mean at transfer.

We shall also need the expected number N_{\rm att} of regular attempts. Each has conditional success probability at least c(b_0/8)^2\ge c'h^{-32}, whereas there are at most Ch successes. Summing conditional success probabilities over the finite processing tree gives

Likelihood evidence and the transfer probability

The small-mass flag implies X_*>d, so its probability is at most Ch^2/d^2=o(h^{-10}). The count flag is already accounted for by the charge flag. To control the latter, attach all the main and evidence observations specified above. Compare the true experiment with a reference law \mathbf Q in which the prior for Y is \mathbf U, the spatial bits and all channel draws still observe Y, but each membership outcome is an independent toss with the state’s prescribed probabilities \delta,1-\delta. On a recorded branch those probabilities are constants in Y. All subsequent states and channel parameters are the same predetermined functions of its spatial and membership history as in the true experiment. One may stop any zero-true-mass branch in the reference as well.

Let \mathcal O denote the terminal observations through live termination, including draws at its final success, and let R=d\mathbf P_{\mathcal O}/d\mathbf Q_{\mathcal O}. On true histories,

To verify this even for histories of different lengths, fix one complete discrete history and all its label values, using densities for the latter. The true likelihood integrates the same channel weights over inputs compatible with both the spatial bits and the actual membership sets, with prior density at most e^d/m_{\rm top}. The reference integrates over all inputs compatible with the spatial bits, and its additional coin factors have product e^{-B_{\rm mem}}. The domain of the true integral is a subset of that reference domain. This proves Equation (6.8) on each terminal branch separately.

At every regular attempt whose observed past is admissible, multiply a score by the following factor, writing E_{\rm ev} for the evidence event in Equation (5.21):

otherwise leave the score unchanged. Group the fresh observations of this test into that step. The conditional reference probability of the evidence given success is at most e^{-t/8} by Proposition 5.4. Consequently the conditional mean of the numerator is at most 1+(e^{t/16}-1)e^{-t/8}\le1+e^{-t/16}. The score \mathcal S is therefore a nonnegative reference supermartingale, with \mathbb E_{\mathbf Q}\mathcal S\le1 at termination. Change of measure gives the particularly useful bound

The simultaneous true admissibility and evidence assertion of Proposition 5.4 fails with probability o(h^{-20}) under the count cap; it includes evidence at a success that immediately transfers. Also \mathbf P(B_{\rm mem}>d)\le Ch^2/d^2 by Equation (6.3). Finally, the total logarithmic denominator cost in the score is at most N_{\rm att}e^{-c d/h}. Its expectation tends to zero faster than h^{-10} by Equation (6.7), so with that allowed exception it is at most one. Outside these exceptions and Equation (6.9),

This excludes \mathcal Q>1000d for large d. It proves the stated transfer probability. The score and evidence draws have only served to estimate this probability; they never select a piece or an update.

The sum of live plateau weights

At a plateau’s root its mean is \alpha_e, so Equation (6.6) gives

Epoch starts number at most Ch+1 on each path. It remains to bound upward resets without multiplying that bound by another h.

Consider one epoch, with start and end stopping times \sigma,\tau in the unlabelled filtration. Include its ending membership success in \tau if there is one. Write \Delta=L_{\rm sp}(\tau)-L_{\rm sp}(\sigma), and let N be its number of upward resets. At its jth reset time \rho_j,

the normalizations have more than doubled at each reset and the membership surprisal is nondecreasing. For any fixed r>0, optional sampling of the inverse likelihood gives

Here \mathcal F^{\rm disc} denotes the spatial and membership history, not the uniform-output filtration used earlier. The second bound follows by integrating the corresponding exponential tail. Every reset not in the exceptional event in the first bound has j\log2\le\Delta+r. Summing reset indicators and then conditioning at the epoch start yields

Sum this inequality over epochs, weighting by the probability that each epoch starts, and set r=2. From one epoch’s end to the next epoch’s start L_{\rm sp} does not change, because only a membership step separates them. Thus all \Delta terms telescope to the terminal L_{\rm sp}. At termination,

The factor two allows the last spatial step that first crosses the common cutoff; membership restrictions cannot increase the mean. The expected total number of resets is therefore O(h) by Equation (6.3). Since m_{\rm top}\le2, this proves the plateau weight bound.

For a fixed plateau, the portions removed from its survivor before its end are disjoint subsets of its original input mass. Multiplying each local removed mean by \mathbf U_e(p) and summing counts each removed input at most once. Division by the entry mean \alpha_e gives \mathbb E_{\mathbf U_e}\sum\xi_p\le1. The identical argument from a final post state p_0, excluding its past removals, starts with mass m_{p_0}/\alpha_e. This proves the remaining assertions in part (iii).

The information cost of main labels

We first recall the finite entropy accounting used here. For any finite remaining spatial bit string, track its conditional relative entropy to uniform future bits. Revealing the next bit consumes, in conditional expectation, precisely that bit’s relative entropy to fair, by the chain rule. An intervening observation increases the expected deficit by its conditional information about the remaining string, at most its conditional information about Y. The remaining deficit is nonnegative, so the same inequality holds when the process is stopped. The initial deficit is at most

For a membership bit its information cost is at most its conditional entropy. Averaging and removing all observed-label conditioning only increases this entropy, so the total membership cost is at most \mathbb E B_{\rm mem}=O(h).

For the main-label filtration we retain all main observations, but not the evidence clones. The initial type-0 observation has zero information. At a success at p, let Z be the old main observation and V the new observation of type A^+. Given the full main-observation history through that success, compare the conditional channel of V with the probability density

For every conditional prior on Y, its information about V is bounded above by the expected relative entropy of the channel to any fixed comparison density. The centered envelope bounds the logarithm of the denominator above by -F(A+S_p). Expanding that relative entropy and dropping the nonpositive new-form energy gives

The notation denotes the usual averaged conditional-information bound; it may first be read for each fixed value of the history.

Now average this inequality over the main-observation histories at the fixed discrete success state. Conditional on Y and that discrete state, the old and new errors still have their prescribed independent laws, because every membership decision is input-only. The phase triangle inequality and form monotonicity imply

This averaging step is essential: conditioning on an observed old label alone would not give its unconditional error law. Also Y\in p and A^+ contains S_p, so

Multiply each such estimate by the true probability of its success state and sum. Those probabilities sum to the expected number of successes, at most Ch. Their total old-error energy is therefore

and their spatial energy is O(h). The relative metric terms in Equation (6.10) sum to O(d) on every path by part (i). Thus all incremental main-channel informations together cost O(d), including a terminal cap-crossing success.

The Fisher sum and the unlabelled deficits

At a final live state p, the conditional density of the current main label, ignoring the older labels, is \alpha_e M/m_p. Given this label, the next spatial bit has bias D/M. Hence its expected squared bias at this state is

Multiplication by the state’s probability in Equation (6.6) gives exactly \mathbf U(p)\alpha_e J_p/m_{\rm top}. Conditioning also on all older main labels can only increase the average squared conditional bias, by conditional Jensen. For a binary law of bias b, its relative entropy to a fair bit is at least b^2/2. The finite entropy accounting just proved therefore bounds the sum of these weighted J_p’s by a constant times m_{\rm top}(d+\log h+\mathbb E B_{\rm mem}+O(d))\le Cd. This proves Equation (6.4) with no lower bound on the surviving mass needed in this conversion.

Finally ignore all labels. The conditional expected increment of L_{\rm sp} at a spatial bit is exactly its relative entropy to fair, while memberships leave L_{\rm sp} unchanged. Starting from L_{\rm sp}=0, the expected sum of bit deficits equals its expected terminal value. On any finite spatial extension with the last piece fixed, m\le e^d, so

If that extension stops at the common density cutoff, instead m\le2e^{4h} and L_{\rm sp,final}\le4h+\log2+\log h+B_{\rm mem}. Taking expectations and using Equation (6.3) gives respectively O(d) and O(h). This completes the 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

Indeed p_e\subseteq p_*, the channel includes S_{p_*}, and the spatial variance and form monotonicity in Section 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 Section 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

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 Equation (7.3) and sum: the factors m_p/\alpha and \alpha/m_p cancel. This proves Equation (7.4) 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 Proposition 6.2, 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 Lemma 7.1, 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

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

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

Memberships contribute no log increment to L. On a mark, Cauchy–Schwarz on the length-l window consequently yields

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 Equation (7.11), 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 Proposition 6.2 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

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 Lemma 7.1, 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

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

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 Lemma 7.1 gives

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 Equation (7.14).

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. Figure 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

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,

At a spatial bit, writing t=D_{\rm jump}/N, its average increment is

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

followed by Cauchy–Schwarz gives

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

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 Equation (7.15) 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 Equations (7.2) and (7.14), distance triggers contribute the last two terms in Equation (7.12). 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

Thus v is high at 0.9b, since \sigma\ll b_0 and the scalar prefactor is small. By Lemma 7.4, 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 Equation (7.6) there is a signed combination v\in[D] at that node with

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

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 Proposition 7.2.□

Proof. The elementary inequality \cosh x\le e^{x^2/2} shows that

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

On |x|\le4 one has 0\le\psi(x)\le Cb^{1/2} and |\nabla\psi(x)|\le Cb^{1/2}. More precisely,

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

Taylor’s formula on the two segments f_p\pm t u_p, 0\le t\le1, gives

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

Apply Lemma 8.1 to the negative fluctuation with \theta=\gamma b^{-1/2}, where \gamma>0 is a sufficiently small numerical constant. By Equation (8.2) its quadratic term is at most \frac12\sum\delta_p. Outside probability e^{-t} this proves, on every prefix,

Now \eta_pu_p\epsilon_j is known in \mathcal F_{j+1} before r_{j+2}. Apply Lemma 8.1 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 Equation (8.1). 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

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

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 Equation (8.4). The decomposition \mathfrak a=vD+e gives

which proves Equation (8.5).

For the removal assertion, the energy has the variational expression

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 Equation (8.4) 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 Equation (8.6). The other two are Lemma 7.1.□

Proof. Telescope the exact energy identity of Equation (8.4). 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, Equation (8.4) gives |U_p|^2\le Cb^2(J_p+g_p). Apply Lemma 8.1 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

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

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

We first prove the required pointwise quadratic estimate. Put

For M_0>0, q\ge\lambda and |v_0|^2/q\le1. Positivity of the child masses and of the removed density gives

There is also a comparison of the child’s post mean with the starting mean:

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 Equation (8.11) 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

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 Equation (8.11).

Splitting \mathfrak a_0=v_0D_0+e_0 and retaining the factor q yields

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

The factor M_1/M_0\le2 supplies the first and third bounds; the second uses |D_1|\le M_1 and Equation (8.11). In particular no lower bound on M_1/M_0 is used. Hence

The mass-coordinate and removal terms satisfy

These follow again from Equation (8.10) and 0<\lambda\le1. If M_0=0, all the masses, half-differences, and removals in Equation (8.9) 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

Combining the preceding pointwise inequalities and integrating proves

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

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 Equation (8.5) and (\int|D_i|)^2\le(\int M_i)J_i\le2J_i, their squares satisfy

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

Apply Lemma 8.1 to the linear scheme with parameter 1/\lambda. Its quadratic term, by Equation (8.15), is at most

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 Equation (8.14), proves for the completed blocks the bound

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 Equation (8.7) 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 Equation (8.8).□

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. Lemma 7.3 bounds the expected number of these by d\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

Consequently, with a numerical constant depending only on C_4,

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

using Equation (8.4) 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 Equations (8.17) and (8.6) imply

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 \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 Equation (8.6).

Apply Lemma 8.5 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

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 Equation (8.16). 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 Lemma 7.4, 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

as established in that lemma. Scalar estimates originate at these births. For each main representative, Proposition 8.6 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

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

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

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

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

Broad capture gives \mathbb E|D|_{\rm final}\le Cd_1b^{-C}, so Jensen’s inequality yields

This proves Equations (8.18) and (8.19), using d_1=d for main levels and \log d_1\le d_1 for scalar levels. Use Lemma 7.5 with this same cap and put

Its expectation satisfies Equation (8.20). 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 of Proposition 6.1. The zero input is immediate. For positive input, apply the finite procedure of Section 6, with the common stopping rule in the statement. In particular, the cutoff always refers to the original \rho, including when a subpiece is being processed. The parameter constants are fixed in the order specified there, and d_0 is increased to satisfy their finitely many large-d requirements.

The contribution of one plateau

For a plateau e, write p_e for its root, \alpha_e for its normalization, and \mathbf U_e for uniform probability on p_e. On an output path x\in p_e, let \mathcal P_e(x) be its consecutive jumping nodes belonging to this plateau. The post density at a node p\in\mathcal P_e(x) is denoted by a_p. Thus all removals at p have already occurred, and a_p is the density whose two prospective child moments are used in that jump. In sums over nodes p, write j=\operatorname{depth}(p). Define

At each jumping node the post pieces partition the original density. Consequently their transforms satisfy the exact identity

Put w_e=\mathbf U(p_e)\alpha_e. The triangle inequality and integration with respect to \mathbf U give

We will bound this weighted sum by Cd, charging the live Fisher and edge terms across all pieces and the remaining terms one plateau at a time.

The local mass bound gives |c_p^u|\le2 and prospective child masses at most 4, in this normalization. Let K_e(x) denote the sum of all normalized removal masses \xi_p on the plateau’s processing path, including the intervening and terminal removals allowed in Proposition 7.2; then

For live plateaus set d_1=d, and for static plateaus set d_1=d+2+\log^-\alpha_e.

Use the main levels \mathcal B_{\rm m}=\{2^{-j}:b_0\le2^{-j}\le1\} on live plateaus. Use scalar levels \mathcal B_{\rm s}(B)=\{B2^{-j}:j\ge0\}, where B=b_0 on a live plateau and B=1 on a static plateau. At the shared level b_0 the main and scalar constructions are distinct. By Lemma 8.7, they have nonnegative, frequency-independent path parameters t_b^{\rm m},t_b^{\rm s} and miss-block lengths H_b^{\rm m},H_b^{\rm s}, satisfying

These statements already include all snapshot births, representative choices, starts, checkpoints, and dyadic list caps. In particular we may use the same parameters for every actual integer u.

At a live jumping piece write

For the scalar construction let \bar b(p) be its largest bad level, if there is one, and put

A nonempty subset of the dyadic levels bounded above by B has a largest member. This choice is determined by the jumping piece before its bit and is independent of u. The scalar edge regions are nested as b increases: their defining l_b decreases. Hence

Main amplitudes and exact decoding

Fix an integer u and a live plateau path. Starting with its first main activation, including that jump, retain the largest main level activated so far. This level is nondecreasing. Its positive intervals therefore use each level b at most once. On the interval assigned to b, keep the representative s and decomposition supplied at its first activation:

The form A is fixed on this plateau. All subsequent nodes in the interval lie below p_{\rm act}.

For clarity, the comparison of criteria uses no loss depending on the number of representatives. For a prospective child q of p, write f_q^v(z)=\alpha_e^{-1}\E_q[a_p(Y)\chi_v(Y)K_A(z-Y)] and M_q(z)=\alpha_e^{-1}\E_q[a_p(Y)K_A(z-Y)]. For the fixed output point x\in p, conditional Cauchy–Schwarz gives

Indeed the square of the channel part is at most

and the spatial part uses |\chi_{a'}(Y)-\chi_{a'}(x)|\le2\pi|a'|\,|p| and \E_q a_p/\alpha_e\le4. The triangle inequality in this weighted Hilbert space proves

If b<1, level 2b has not activated at any jump of this interval. Its non-bad high jumps before activation lie in one block of at most H_{2b}^{\rm m} depths, by Proposition 7.2. Remove the intersection of that entire block with the current interval and pay C H_{2b}^{\rm m} directly, using |c_p^u|\le2. The remaining jumps form at most two contiguous intervals. On each, a nonexceptional jump is not high for u at 2b; thus Equation (9.8) makes it inner-valid for s,b in Proposition 8.6. Here the exceptional jumps are precisely the bad main jumps at 2b. When b=1, every jump is inner-valid after the fixed constant in that definition is chosen large enough, since all G_q^s\le4; no block is removed and no exception is needed.

We next verify the decoding of the vector estimate back to the actual scalar modulation. Put

Evenness and positivity of the thermal Fourier coefficients imply

This is an exact identity, obtained by putting z=Y+\theta in the inner integral. On any subset of the nodes below p_{\rm act},

The sum of lengths is geometric because the nodes lie on one descending path. The bound applies in particular to each retained subinterval. Since the multipliers are common to all label coordinates, Equation (9.9) now gives

for every retained subinterval L.

Apply Proposition 8.6 to L. Its Fisher sum is charged only on L. The intervals at distinct retained levels are disjoint, and there are at most two retained subintervals at each level. Thus these Fisher charges have an absolute bounded multiplicity at every jumping piece. All kill and exceptional sums may use the whole plateau path. Writing the exceptional proxy as e'_p=C b_0^{-2}E_{p,2b}^{\rm m}, and using b^{-1/2}b_0^{-2}\le b_0^{-3} for b\ge b_0, we have bounded the whole main part by a constant times

The constants in the vector estimates and the geometric decoding errors are absorbed by the displayed b^{-1/2} terms.

The scalar prefix and all static paths

On a live plateau consider the prefix strictly before the first main activation, or the whole path if no main activation occurs. On a static plateau consider the entire path. Use the scalar levels through B specified above, again retaining the largest activated level so far, including activations at the current jump, and using zero if none has activated. There are finitely many changes on this finite path even though the available scalar levels extend arbitrarily close to zero. Each positive level b is retained on at most one contiguous interval.

For its fixed representative s, scalar activation supplies u=s+a' with |a'|\,|p_{\rm act}|\le Cb^4, with the sufficiently small constant in Proposition 7.2. On this level interval sum first over the fixed scalar mask

This is precisely the masked transform in Proposition 8.2; that proposition applies to the masked sum over the whole contiguous level interval. Freezing \chi_{a'} at x changes this masked sum by at most Cb^4, by the same geometric sum of interval lengths as above. Hence all such masked sums cost at most

Treat every remaining jump directly. This includes all jumps while the retained level is zero. Put A'_p=\max\{|f_{p,+}^u|,|f_{p,-}^u|\}\le4 in the unlabelled scalar notation. The direct jump costs at most A'_p, and a zero value needs no charge. If a positive level b is currently retained, the jump is outside its mask; the spatial phase comparison gives A'_p\ge C_3b-Cb^4>4b, on taking C_3 large enough.

For a live prefix, any direct jump with A'_p>4b_0 is high at main level b_0. In fact f_{p,\pm}^u=\int f_{p,\pm}^u(z)\,dz and Cauchy–Schwarz gives |f_{p,\pm}^u|^2\le(\int M_{p,\pm})G_{p,\pm}^u\le4G_{p,\pm}^u. No main level has yet activated in this prefix. All its non-bad main high jumps at b_0 are therefore paid by its one miss block, and its bad jumps are paid by C b_0^{-2}E_{p,b_0}^{\rm m}, since each direct coefficient is at most 4. These costs are already included, up to constants, in Equation (9.11).

At every other nonzero direct jump we have A'_p\le4B; this holds automatically on a static path with B=1. Choose the largest available scalar level \widetilde b\le A'_p. Then

and the jump is high at \widetilde b. This level has not activated: if the current level is positive, A'_p>4b implies \widetilde b>b, and otherwise none has activated. All non-bad jumps assigned to a fixed \widetilde b consequently lie in its single preactivation miss block and cost at most C\widetilde b H_{\widetilde b}^{\rm s} together. If the assigned level is bad, then e_{p,\widetilde b}\ge c\widetilde b and Equation (9.6) gives

Thus only one predictably selected scalar edge level per jump is charged. This establishes the scalar accounting for every positive amplitude, including arbitrarily small amplitudes.

Combining these conclusions, the same frequency-independent quantity bounds \sup_u|\mathcal T_e^u| on a live plateau:

For a static plateau the corresponding bound is

The path constructions and bounds used here hold simultaneously outside one \mathbf U_e-null set. The countable scalar-level sums have finite expectation by the estimates below. In particular no exceptional set depending on the actual modulation is introduced in these majorants.

Summing levels and live weights

Write b_0=2^{-M}, so M=O(1+\log h). Since k_b=A_0(d/h)(1+\log(1/b))^2, the main cardinality tails satisfy

The additional logarithms in Equation (9.3) sum to O(\log(Cd)) with the same b^{1/2} weights. Also,

Every fixed polynomial in h, multiplied by 1+\log d, is o(d/h) because h=\log\log d. Thus the second line of Equation (9.13) has expectation O(d/h).

For the scalar series write b=B2^{-j}. The convergent sums \sum_{j\ge0}2^{-j/4} and \sum_{j\ge0}j2^{-j/4}, together with Equations (9.2), (9.4) and (9.5), give

For example the miss-block part alone is bounded by CB(\log(Cd_1/B)+\log(1/\sigma)+1), which is no larger than the displayed right side. On live plateaus B=b_0\le h^{-16} and d_1=d, so this is O(d/h^4) and hence O(d/h). On static plateaus B=1 and d_1\ge d, so \log(1/\sigma)=40\log h\le Cd_1 makes it O(d_1). The local scalar edge bound in Proposition 7.2 therefore proves

For every nonnegative jump quantity V_p of a plateau, change of the uniform root measure gives exactly

The Fisher bound in Proposition 6.2 bounds the right side by Cd when V_p=J_p and e is live. The global scalar edge assertion of Proposition 7.2 does the same for V_p=E_p^{\rm s}. Its global main edge assertion yields

Finally \sum_{e\text{ live}}w_e\le Ch by Proposition 6.2. Multiplying the O(d/h) per-plateau costs in Equation (9.13) by these weights therefore proves

Static roots, small mass, and rare transfers

Consider static handling starting with a positive piece of mean m at an interval q. Its later plateaus restart only when their incoming mean exceeds twice the previous normalization. Along any input path each new normalization is therefore more than twice its predecessor, and every normalization is at least m. A plateau with a jump has normalization at most e^{4h}; allowing a final non-jumping overshoot changes this bound only by a factor of two. Consequently the number N_{\rm st} of static starts on the path obeys

Starts with no subsequent jump may also simply be omitted.

Let \mathbf P_q be the probability with density equal to this entry piece divided by m relative to uniform probability on q. Since the piece is never split again, the probability of reaching a later static plateau root p_e is \mathbf U_q(p_e)\alpha_e/m. Thus the sum of its starting weights is the original weight \mathbf U(q)m multiplied by \E_{\mathbf P_q}N_{\rm st}. Applying Equations (9.17) and (9.20), the entire static descendant family costs at most

This uses the input path only to sum weights; each individual transform estimate remains an integral over its uniform output path.

If 0<m_{\rm top}<1/h, the procedure takes the top static immediately. Writing \ell=\log(1/m_{\rm top}), its total cost is bounded by

For an explicit verification, m_{\rm top}h\le1, \sup_{0<t\le1}t\log(1/t)=1/e, and \sup_{0<t\le1}t\log^2(1/t)=4/e^2. Expanding the product and using h\le d proves the inequality.

It remains to sum static families transferred out of an initially live top, so m_{\rm top}\ge1/h. Every true input path undergoes at most one such transfer. Let A_{\rm tr} be the transfer event under its input probability \mathbf P, and let X_* be the maximum negative logarithm of the mean through transfer or stopping, including the transfer state. Proposition 6.2 gives

This includes both charge/count transfers and the small-mass flag. In particular the small-mass event has X_*>d, hence probability at most Ch^2/d^2\le Ch^{-10}. The cap accounting and the evidence argument in that proposition bound the probability of the other transfers; there is no further sequence of live restarts after transfer.

For a transfer piece of mean m, its true reaching probability is \mathbf U(q)m/m_{\rm top} and \log^-m\le X_* on that event. Summing Equation (9.21) over all transfer roots therefore bounds their entire cost by

Only the second moment in Equation (9.22) is needed. Indeed, with \delta=\mathbf P(A_{\rm tr}),

Here Cauchy–Schwarz gives \E[\mathbf1_{A_{\rm tr}}X_*]\le\sqrt\delta\,\|X_*\|_2\le Ch^{-4}, whereas the quadratic term uses its full bound \E X_*^2\le Ch^2. Multiplying by m_{\rm top}\le2 preserves Cd.

Completion

The live estimate Equation (9.19) and the static-family estimates bound the right side of Equation (9.1) by Cd. This proves Equation (6.1). Every construction was in fixed finite depth and every estimate was independent of Q. Increasing Q and applying monotone convergence proves the assertion for all integer modulations as well.□

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

The two Haar profiles. Extend the following functions by zero outside [0,1):

For a dyadic interval I=[a,a+r) put \mathfrak h_I(y)=\mathfrak h((y-a)/r) and \mathfrak g_I(x)=\mathfrak g((x-a)/r). The shift summand

is an admissible summand in Proposition 6.1: on the output side choose \epsilon_j=r_{j+1}, so that \mathfrak g_I=r_{j+1}r_{j+2}.

Tile the line by top intervals of length s\in[1/2,1], translate the tiling by a\in[0,s), and use depths j=0,\ldots,J-1 below every top, where J\ge1. Denote the resulting finite-depth shift by \mathcal S_{a,s,J}. This shift need not be periodic, so in the next estimate G_\rho denotes its representative in [0,1). At most a fixed number of top intervals meet [0,1). Each has input average at most 2, since \rho has mass one in a period and s\ge1/2. At every x\in G_\rho, the density cutoff in Proposition 6.1 is inactive on all intervals of its spatial path. Thus the stopped and unstopped shifts agree there, and

uniformly in a,s,J. Here a uniform-probability integral on a top interval is multiplied by its length to obtain the ordinary spatial integral. Only a bounded number of top intervals is involved.

Translation and scale averaging. Define

For a fixed length r=s2^{-j}, uniform translation modulo s is also uniform translation modulo r. Changing variables from an interval’s left endpoint to the output’s position v in that interval shows that the translation average of its full tiling is convolution with r^{-1}\kappa(t/r). This identity is just Fubini’s theorem applied to the bounded, compactly supported profiles. For F=\rho\chi_n, integrating the translation average in ds/s gives

where, because the intervals [2^{-j-1},2^{-j}] partition [2^{-J},1],

The triangle inequality, followed by Equation (10.3), therefore yields

The measure ds/s on [1/2,1] has mass \log2; it has not been normalized to a probability measure. This fixed factor is absorbed in C. The functions being averaged are finite shift outputs, measurable in the translation and scale parameters. No measurability of the auxiliary processing choices used to prove their uniform bound is required.

The nonzero singular kernel. Reflection about 1/2 fixes \mathfrak g and reverses the sign of \mathfrak h, so \kappa is odd. It is supported in [-1,1] and is Lipschitz, since it is a finite linear combination of overlaps of intervals. Moreover

The inner primitive is the tent function \min(v,1-v). Thus the average in Equation (10.4) has a nonzero Hilbert-transform component. This calculation agrees with the Haar-shift kernel evaluation in [12, Section 3, pp. 1135–1136].

Put \delta=2^{-J}. When \delta<t\le1, the substitution u=t/r and the support of \kappa give

The second term is bounded by an absolute constant; oddness gives the same conclusion for negative t. On |t|\le\delta,

Compare K_J to

On the central annulus the difference is bounded, because \pi\cot(\pi t)-1/t is bounded on [-1/2,1/2]. On 1/2<|t|\le1 the original kernel is bounded as well. Those bounded errors have convolution at most C in absolute value against any \rho\chi_n, using periodicity and mass one. The inner window contributes at most

It follows from Equation (10.5) and e^{4h}=o(d) that

Division by the fixed nonzero number \pi c is harmless.

The Hilbert multiplier and Fourier projections. For completeness, H_\delta converges in L^2 to the periodic Hilbert transform H whose multiplier is -i\,\operatorname{sgn}(k) for k\ne0 and zero at k=0. To see this directly, oddness reduces its multiplier to a sine integral. These multipliers are uniformly bounded: write \cot(\pi t)=1/(\pi t)+O(1), split the sine integral at inverse frequency, and integrate by parts on the remaining interval. For a fixed positive integer k,

Indeed, setting x=\pi t and using

reduces the integral to the constant term in 2\cos x\sum_{a=1}^k\cos((2a-1)x); all its nonconstant even-frequency cosines have integral zero on [-\pi/2,\pi/2]. The constant term occurs only for a=1 and gives one after division by \pi. Negative frequencies have the opposite sign. Pointwise multiplier convergence and the uniform bound now imply L^2 convergence by Parseval’s identity.

Every \rho\chi_n is bounded and hence belongs to L^2. For a fixed finite set of integers, the maximum of the differences |H_\delta(\rho\chi_n)-H(\rho\chi_n)| tends to zero in L^1, by the finite sum of their L^2 norms. Pass to the limit in Equation (10.7) for that finite set and then increase the set to \mathbb Z. Monotone convergence gives

Let P_0 be projection onto constants and let \Pi_{\ge0} be projection onto the nonnegative Fourier frequencies. As L^2 multiplier identities,

They hold almost everywhere simultaneously for all the indicated integer indices, after removing one null set. Since |\widehat\rho(k)|\le1, their identity and constant terms give the pointwise upper bound

Integrating and applying Equation (10.9) proves Equation (10.2).□

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

As m_\ell\to0 through positive values, d_\ell\to\infty, m_\ell d_\ell\to0, and \rho_\ell\le e^{d_\ell}. Theorem 10.1 and Markov’s inequality show, for each \eta>0,

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

satisfies

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 Theorem 1.1. It suffices to work in unit-period coordinates. Write

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

Then \int\rho_j=1 and \rho_j\le e^{d_j}. For all sufficiently large j, Theorem 10.1 applies.

We claim

On the support of q_j, \log|f|\ge2^j, and q_j\le|f|. Disjointness of the layers therefore gives

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 Equation (10.10).

Let G_j be the good set associated to \rho_j. Since \log d_j\ge(j+1)\log2,

Borel–Cantelli implies that almost every point belongs to all but finitely many G_j. On the other hand, Tonelli’s theorem and Equations (10.2) and (10.10) give

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 Proposition 10.2 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

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 Proposition 10.2, 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 Theorem 1.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 Theorem 1.1, S^*f is finite almost everywhere for every f\in B. Stein’s theorem [22, Appendix, Theorem 10], applied to the sequence S_0,-S_0,S_1,-S_1,\ldots, therefore gives Equation (10.11) 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.□