The symmetric Fourier partial sums of an integrable function on the
circle converge along the full sequence N = 0, 1, 2, ... to the
function almost everywhere, provided the function lies in the Orlicz
class L log L. This class sits strictly between every space L^p,
p > 1, and L^1, and the endpoint is sharp: the conclusion fails in
general throughout L^1.
Set T = R/(2 pi Z), the circle of circumference 2 pi, and give it
the normalized Lebesgue measure d mu(x) = dx/(2 pi). For a
complex-valued integrable function f on T, its Fourier coefficients
and symmetric partial sums are
fhat(k) = integral over T of f(x) e^{-i k x} d mu(x),
S_N f(x) = sum_{k = -N}^{N} fhat(k) e^{i k x}, N = 0,1,2,...
The Orlicz class at the endpoint is
L log L(T) = { f : integral over T of |f(x)| log(2 + |f(x)|) d mu(x) < infinity }.
The space L log L is a little bigger than every L^p with p>1, and a
little smaller than L^1. It is exactly the endpoint at which the
Carleson-Hunt technology is still expected to work, and it is the
space in which convergence holds.
THEOREM A (main theorem, almost-everywhere convergence in L log L).
For every complex-valued f in L log L(T) there is a measurable set
N_f of measure zero such that
lim over N -> infinity of S_N f(x) = f(x) for every x in T \ N_f.
The limit is taken along the full sequence N = 0, 1, 2, ... .
What was known. Carleson (1966) proved almost-everywhere
convergence for f in L^2, and Hunt (1968) extended it to every L^p
with p > 1. Kolmogorov (1923) exhibited an L^1 function whose
symmetric partial sums diverge almost everywhere, so the conjecture
cannot hold throughout L^1. Between L^1 and the L^p worlds, Sjolin
(1969) got convergence in L log L log log L; Soria (1985, 1989)
constructed larger convergence spaces by extrapolation; Antonov
(1996) reached L log L log log log L; Arias de Reyna (2002) built a
quasi-Banach space QA strictly containing both Antonov's and Soria's
classes; Carro-Mastylo-Rodriguez-Piazza (2012) got a Lorentz space
still larger than Antonov's. Lie (2013) reproved the full-sequence
weak-L^1 maximal bound from QA by time-frequency methods without
extrapolation. Di Plinio-Fragkos (2025) obtained weak-L^p maximal
estimates with the sharp (p-1)^{-1} growth, plus sparse and weighted
endpoint results. Lie (2017) formulated the L log L conjecture as a
weak-L^1 maximal estimate. Theorem A proves that conjecture at the
endpoint, in the symmetric, full-sequence sense.
For bounded functions, almost-everywhere Fourier convergence follows
from Fejer means by elementary arguments. The difficult case is when
the function is large on a thin set. The strategy is to cut away the
places where the function is dangerously large, and on what remains
prove a strong estimate for the maximal partial-sum operator. The
pieces are then reassembled through the layer-cake structure of
L log L.
Let rho be a nonnegative function on T with total mass one and
pointwise height at most e^d, where d is a large parameter to be
chosen later. Define the uncentered interval maximal function
M rho(x) = sup over arcs I containing x, 0 < |I| <= 1,
of the average of rho over I.
Set h = log log d, and remove the "high-density" set
G_rho = { x : M rho(x) <= e^{4h} }.
By the interval covering lemma its complement has small measure:
|G_rho^c| <= C e^{-4h} = C (log d)^{-4}.
THEOREM B (good-set integral estimate).
There are absolute constants C and d_* such that, whenever d >= d_*
and rho has integral one and |rho| <= e^d almost everywhere,
integral over G_rho of sup over N >= 0 of |S_N rho(x)| dx <= C d.
Note the crucial point: the bound on the right is linear in d, and d
is the logarithm of the pointwise height of rho. That linear growth
in d is exactly what makes the eventual layer summation work. If the
bound were quadratic in d, or d times something growing, the whole
argument would fail.
Why the two pieces (integral bound and exceptional set) have
different roles: the integral bound has the shape "mass times d",
which is summable against the masses of the layers of an L log L
function. The exceptional set G_rho^c has measure (log d)^{-4},
which is summable when d grows doubly exponentially in the layer
index. Both summabilities are needed; together these determine the
choice of layer threshold d_j.
The Carleson operator at frequency u controls the size of the u-th
Fourier projection uniformly in u. Direct control for all u at once
fails: there are infinitely many u, and a naive union bound has an
infinite loss. Fefferman handled this by building a measurable
"frequency selector" that decides which u to track at each point;
Lacey-Thiele then gave a phase-plane / tile / tree organization of
the argument. A third route replaces the selector with a finite
probabilistic mechanism based on information theory: if many
frequencies actually wanted to be tracked at once, all would have
to be "aligned in phase" on a large common region of the noise, and
that requires a lot of coincidence. Pricing that coincidence is
what entropy does.
The whole proof can be seen as three cooperating constructions,
each one making one kind of estimate compatible with the others.
(1) One phase region for many frequencies. This is the "entropy
compression" step. The construction starts with a finite set S of
integer frequencies and a uniform bound on noisy sums of independent
draws from any probability law on S. The goal is a large subset S' of
S, a center frequency x_0, and a common set of phases R on which all
frequencies x in S' have their phase defect relative to x_0 small.
The point of "small on average over R" is that R is fixed before the
probabilities on S' are chosen; so later weight choices cannot break
the property. The proof builds correlated samples with prescribed
marginals, controls their relative entropy together with the
information contained in a noisy sum, and refines in two nested
stages.
(2) Two ways to pay for a new observation. This is the "thermal
label" step. A label is a noisy observation of the true
input point: Z = Y + theta mod 1, where theta has density
proportional to e^{-A(y)} and A is a nonnegative sum of terms
(1 - cos(2 pi s y)). The Fourier coefficients of e^{-A} are
nonnegative (Griffiths-Ginibre / positive correlation). When a new
term is added to A, the change in the density is controlled by
these nonnegative coefficients; and if the spectra are "too
spread out," compression can upgrade an existing label to a
newer, sharper one. The cost of that upgrade is either likelihood
information (an event rare under a comparison law) or a packing
estimate (the frequencies whose phases are stable under the noise
grow, but by a bounded amount). Both prices are bounded; together
the two express the total "temperature" cost of the labels.
(3) Separate accounting for information and for choosing
frequencies. This is the "plateau / snapshot / delayed path"
machinery. Each spatial piece carries a cumulative
list D of integers that "approximates the frequencies that might
matter." At selected spatial prefixes, a smaller list of
representatives is stored along with the current mass measures.
The smaller list enters the probabilistic estimates;
the cumulative list enters only deterministic approximation error.
The transformation along an output path is estimated with a
martingale that uses the fact that its coefficients are known
before the next fair sign. The delayed sign gives a second bit of
slack exploited throughout.
Summing up the three: the expected cost of choosing representatives
plus the remaining path terms is O(d/h) on each live plateau; the
total starting weight of the live plateaus is O(h); the product is
O(d). The boundary errors and the static pieces cost O(d) by
separate, cheaper arguments. That is where Theorem B comes from.
Switch to unit-period coordinates y = x/(2 pi) so the circle is R/Z
with normalized length dy. Characters are
chi_u(y) = e^{2 pi i u y}, u in Z.
Symbols chi_u with real u are also used for the exponential on real
intervals; only integer u are characters of the circle. All
conclusions are invariant under changes on null sets.
All logarithms are natural. Write log^- t = max{0, -log t} for
t > 0. The parameter d is "sufficiently large" throughout; the
threshold may depend on fixed auxiliary constants chosen earlier but
never on spatial depth or on a frequency cutoff. Numerical constants
denoted c, C may change from line to line. Any other dependence is
written explicitly. "poly(x_1,...,x_k)" denotes a polynomial upper
bound with fixed nonnegative coefficients and fixed finite exponents.
Entropy. For a probability law P on a finite set,
H(P) = - sum_x P(x) log P(x), 0 log 0 := 0.
Conditional entropy is averaged over the conditioning law. For
probability measures,
D(P || Q) = integral log(dP/dQ) dP
when P << Q, and +infinity otherwise; the same convention when the
integral diverges. Mutual information is
I(X; Y) = D(P_{X,Y} || P_X tensor P_Y),
and conditional mutual information is the corresponding average over
the conditioning variable. A random variable may stand for its law
inside D or a metric between measures.
Three facts from Cover-Thomas, Chapter 2, are used repeatedly:
nonnegativity of D, the chain rules for both H and D/I, and
contraction of relative entropy under measurable maps. With total
variation
||P - Q||_TV = sup over measurable A of |P(A) - Q(A)|,
Pinsker's inequality reads
||P - Q||_TV <= sqrt( D(P || Q) / 2 ).
For probability densities, this is half their L^1 distance; numerical
constants absorb the harmless factor of two. In the entropy
compression argument all Shannon entropies are finite-valued: H is
only ever taken of random variables with finite support.
Sumsets and signed spans. For finite S subset Z, n S is the
n-fold sumset with repetitions. Later, [D] is the signed span of a
finite list D:
[D] = { sum_{v in D} eps_v v : eps_v in {-1, 0, 1} }.
D is an ordered list; repeated coordinates are kept as distinct
entries. In all entropy-accounting arguments, "add a new coordinate"
means: append a new slot to the list, and the information cost is the
Shannon entropy of that new coordinate given the past ones.
The two probability laws. The dyadic construction uses two
laws on the same underlying space: the uniform output law U, which
has fair binary bits along the dyadic tree; and the true input law
P, which is the current nonnegative input weighted against U.
Additional noisy labels are observations of the input point under a
prescribed channel. Every deterministic processing decision is a
function of the spatial prefix and the previously observed
membership outcomes, not of the realized label noise. Separating
these two laws carefully is the essential move that makes the
"information for input" convert into "estimates on output paths."
This is the "beat randomness by paying for it" step.
Fix a finite set S of integer frequencies. Suppose it is known, for
every probability law on S, that a noisy sum of about T independent
draws is not "too concentrated" in any weighted sense. Then a large
subset S' of S behaves as if all its frequencies were very nearly in
phase with one another, at a cost of only a small part of S. The
price is measured in entropy: how many bits of information
the "nearly aligned" condition costs, and it is affordable.
Several subtleties require handling. The letters in the
intermediate construction are allowed to be *correlated*: that is,
the construction does not assume the samples are independent. The
only things under control are the one-letter marginal and the noisy
sum. The quantity that prices the correlation is a combination of
relative entropy and mutual information. Care is taken never to
use either of these in isolation; both appear together.
The proof has three nested stages. Stage 1 constructs a joint law
with prescribed marginals and controlled cost. Stage 2 conditions
on a prefix to make short blocks nearly independent. Stage 3
refines the conditional laws in two layers to reach the desired
phase concentration. Each stage keeps the noisy-sum cost from
growing.
Set for the large parameter d:
h = log log d, T = floor( d h^{-5} ),
w = (log d)^{1/4}, L = d exp(w),
m_* = floor( exp(w^3) ).
Then m_* = d^{o(1)} = o(T). Every assertion below holds for all
sufficiently large d; the threshold may depend on the fixed
constants in the hypotheses, but never on the finite sets S under
consideration.
STATEMENT OF THE COMPRESSION LEMMA.
LEMMA 3.1 (entropy compression). Fix D_0, P_0 >= 1. Let q be a
strictly positive probability mass function on Z. Suppose that, for
a positive integer g and a probability measure omega on R/Z,
H_q(x) := q(x)/q(0)
= integral chi_{g x}(theta) d omega(theta),
chi_v(theta) = e^{2 pi i v theta},
F_0 := -log q(0) <= D_0 d. (3.1)
Let S subset Z be finite and nonempty and suppose
log |n S| <= D_0 d h^{P_0} log d for all 1 <= n <= d^2. (3.2)
Suppose d/h^2 <= E <= D_0 d and, for every probability measure
lambda on S,
-log E_{lambda} H_q(X_1 + ... + X_T - X'_1 - ... - X'_T) <= E, (3.3)
where the 2T letters are independent with common law lambda.
Then there exist x_0 in S and a nonempty subset S' subset S such that
log |S| - log |S'| <= C(D_0) d^2 / (E h^2), (3.4)
and for every probability measure v on S',
integral exp( -L sum_{x in S'} v(x)
(1 - Re chi_{g(x - x_0)}(theta)) )
d omega(theta) >= e^{-C E}. (3.5)
Constants: C in (3.5) is numerical. C in (3.4) depends only on D_0.
The threshold for d may depend on P_0.
A word of interpretation. Equation (3.2) says the sumset n S of
the candidate set is not wildly bigger than S. That is where the
"Chang" combinatorial control enters. Equation (3.3) is a uniform
noisy-sum bound: however S is weighted, the noisy sum of 2T
independent draws has H_q-bulk at most
E, on log scale. Conclusion (3.5) is a universal lower bound: for
every weighting of S' at all, the phase defect on omega is at most
of order E per unit of L, on scale-independent terms. This
uniformity is critical: later, the spectral weights on S' are chosen
after S' and its center x_0 are already fixed. The same S' and x_0
work for every possible weighting.
Lemma 3.1 is proved in stages, with intermediate lemmas labelled
3.2 through 3.9. The structure:
- 3.2 builds a joint law of T letters plus a noisy error with a
controlled relative-entropy cost.
- 3.3 gives the bookkeeping "cost rules" enabling projection,
forgetting, and conditioning without the cost blowing up.
- 3.4(a) conditions on a short prefix to make the block law close
to iid with a controllable cost.
- 3.4(b) lifts the cost from one block to many rows (full-vector
interpretation) without changing it.
- 3.5 thins blocks to exactly iid marginals by paying a small
extra cost.
- 3.6 glues two couplings so that a large block observation is
converted into a noisy-cost difference.
- 3.7 runs a two-order search over block lengths, at total
cost O(h^{-2}).
- 3.8/3.9 freeze the context stack, pick a common phase region,
and extract one coordinate satisfying the conclusions.
Let U_S be the uniform law on S, and put, for all u in Z,
c(u) = -log H_q(u).
By (3.1), 0 < H_q(u) <= 1 (a positive real characteristic
coefficient), so c(u) is finite and nonnegative, and c(0) = 0.
LEMMA 3.2 (a noisy sum with prescribed marginals).
Under the hypotheses of Lemma 3.1, there is a law of
X^T = (X_1, ..., X_T) and Gamma in TS - TS such that every X_i has
law U_S, the joint law is invariant under permutations of the
letters, and, with Z = sum_{i=1}^T X_i + Gamma,
D(X^T || U_S^{tensor T})
+ I(X^T; Z) + E c(Gamma) <= E. (3.6)
The construction may be made with Z in TS.
Proof. Consider probability laws on S^T times TS, with coordinates
(X^T, Z), having uniform one-letter marginals. Minimize
T H(U_S) - H(X^T | Z) + E c(Z - sum_i X_i).
The feasible set is a nonempty compact polytope; conditional entropy
is continuous on finite simplices including boundaries, so the
minimum is attained. The objective is convex: -H(X^T | Z) is
convex in the joint law (it is an average of conditional
entropies), and the other two terms are linear or constant.
Finite Gibbs variational duality is invoked. For a tuple
mu = (mu_1, ..., mu_T) of marginals on S, define f(mu) as the
minimum of -H(X^T | Z) + E c(Z - sum_i X_i) subject to the
marginals being mu_1, ..., mu_T. It is finite everywhere (a
product law for the letters with any fixed z in TS is feasible).
It is convex by mixing. At the tuple of uniform laws -- a relative
interior point of the product of simplices -- f has a supporting
affine function. Equivalently, separating its epigraph from points
below yields finite multipliers for the marginal constraints. So no
duality gap exists, and the minimum equals
T H(U_S)
+ sup over a_1, ..., a_T : S -> R of
{ sum_i E_{U_S} a_i
- log max_{z in TS}
sum_{x in S^T} e^{sum_i a_i(x_i)} H_q(z - sum_i x_i) }.
(3.7)
To read the inner expression: put
B_z = sum_{x in S^T} e^{sum_i a_i(x_i)} H_q(z - sum_i x_i) > 0.
For a conditional law pi of X^T given Z = z, its posterior entropy
cost equals
sum_x pi(x) log( pi(x)
/ ( e^{sum_i a_i(x_i)} H_q(z - sum_i x_i) ) )
= D( pi || B_z^{-1} e^{sum_i a_i} H_q( z - sum_i x_i ) ) - log B_z.
Count that the minimum is -log B_z at the normalized Gibbs law.
Optimizing the law of Z then chooses a maximizer of B_z, giving
-log max_z B_z.
The dual objective in (3.7) is concave in the tuple (a_1,...,a_T):
the -log of a maximum of log-sum-exponential (convex) functions is
concave. It is invariant under coordinate permutations, and
averaging over permutations can only increase a concave function.
So it suffices to consider a_i = a for every i. Write
A_a = sum_{x in S} e^{a(x)}, lambda(x) = e^{a(x)} / A_a.
The value at these multipliers becomes
-T D(U_S || lambda)
- log max_{z in TS} E_{lambda^{tensor T}} H_q( z - sum_i X_i ).
The max is at least the average when z is a sum of an iid T-tuple
from lambda. That average is at least e^{-E} by hypothesis (3.3)
(the two independent T-tuples may be interchanged there). Since
relative entropy is nonnegative, the dual value is at most E.
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. Set
Gamma = Z - sum_i X_i, which is in TS - TS by Z in TS. The identity
D(X^T || U_S^{tensor T}) + I(X^T; Z)
= T H(U_S) - H(X^T | Z)
then gives (3.6) with the required exchangeability. []
Remarks. The point of Lemma 3.2 is that the noisy sum has a
bounded information cost. It will be the base of operations for
everything else. Note that (X^T, Z) is exchangeable, including the
error Gamma. That exchangeability allows conditioning on a
prefix without losing control of the rest of the block.
For a probability law p on a finite set of integer letters and a
law of (X^s, Gamma) supported on (supp p)^s tensor (TS - TS), define
C_p(X^s, Gamma) :=
D(X^s || p^{tensor s}) + I(X^s; Z) + E c(Gamma), (3.8)
where Z = sum_{i=1}^s X_i + Gamma.
Three "cost rules" apply. The rules are bookkeeping facts: certain
operations on the joint law do not increase C_p by more than a
specified amount. When p has zeros, everything is restricted to
its support, where cross entropy is finite.
LEMMA 3.3 (projection and conditioning rules). Let the letters and
error in (3.8) be finite-valued, with p positive on every coordinate
support.
(i) Keeping any fixed subset of the letters, in any fixed order,
and reusing the same error Gamma, does not increase C_p.
(ii) If J is any finite-valued variable, then the average cost of
the laws conditional on J is at most the original cost plus
H(J). After conditioning, the projection and reordering in
(i) may depend on J.
(iii) Conditioning on a fixed prefix of the letters and keeping
the remaining k letters with the same error does not
increase the average cost. If those letters have a common
conditional marginal nu at a given prefix value, the
comparison product may be changed from p^{tensor k} to
nu^{tensor k} without increasing the conditional cost.
Proof of (i). Write B and O for the kept and omitted vectors, and
Z_B = Z - sum O. The cross entropy to p^{tensor s} separates over
B and O. Also H(B | Z_B) >= H(B | Z, O), because conditioning on
more reduces entropy. By the chain rule for relative entropy,
C_p(B, O; Gamma) - C_p(B; Gamma)
= E[-log p^{tensor |O|}(O)] - H(B, O | Z) + H(B | Z_B)
>= E[-log p^{tensor |O|}(O)] - H(O | Z)
>= 0,
where the last step is nonnegativity of D(O || p^{tensor |O|}) after
removing the conditioning on Z. Reordering does not change the sum
or the product comparison.
Proof of (ii). Cross entropy and error cost are unchanged after
averaging conditional laws; the conditional entropy becomes
H(X^s | Z, J). So the exact average increase is
sum_j P(J = j) C_p(X^s, Gamma | J = j) - C_p(X^s, Gamma)
= I(X^s; J | Z) <= H(J).
Nothing imposes independence on J: it may depend on letters,
error, and any other randomness. Applying (i) within each
conditional law gives the final assertion.
Proof of (iii). Let B be the revealed prefix and O the rest.
Conditioning on B, the map Z -> Z - sum B is an invertible
translation of the output, so if B is revealed the average cost of
the rest equals C_p(O, Gamma) conditionally on B minus a term
E[-log p^{tensor |B|}(B)] + H(B | Z), which is nonnegative. In a
conditional law where each remaining letter has marginal nu,
changing the product comparison to nu^{tensor k} decreases the
cross entropy by k D(nu || p), and leaves the other two terms
unchanged. This proves the claim, including when nu vanishes on
some letters. []
Let T_0 = floor(T/4). Conditioning an exchangeable vector on a
suitable prefix keeps a long exchangeable remainder and makes short
subblocks close to independent copies of its conditional marginal.
The next lemma retains the noisy-sum cost at the same time.
LEMMA 3.4 (selection of a conditional marginal). Under the
hypotheses of Lemma 3.1, there is a probability law nu on S and a
joint law Psi of an exchangeable T_0-tuple with common marginal nu
and an error Gamma in TS - TS such that, writing
Z = sum_{i=1}^{T_0} X_i + Gamma,
log |S| - H(nu) <= C E / T, (3.9a)
D(X^{T_0} || nu^{tensor T_0})
+ I(X^{T_0}; Z) + E c(Gamma) <= C E, (3.9b)
|| L_Psi(X^m) - nu^{tensor m} ||_TV
<= C m_* sqrt(E) / T for 1 <= m <= m_*. (3.9c)
All three constants are numerical.
Proof. Start with Lemma 3.2 and put
s_j = H(X_{j+1} | X_1, ..., X_j), 0 <= j < T.
The sequence s_j is nonincreasing: conditioning decreases entropy,
and exchangeability of the unrevealed coordinates makes the
conditional law of X_{j+2} given (X_1,...,X_j) the same as that of
X_{j+1} given (X_1,...,X_j). The chain rule and (3.6) give
sum_{j=0}^{T-1} ( log |S| - s_j ) = D(X^T || U_S^{tensor T}) <= E. (3.10)
The deficits are nonnegative and nondecreasing, so for j < T,
log |S| - s_j <= E / (T - j).
Let a = floor(T/4), b = floor(T/2), and choose a prefix length j
uniformly in the integer interval [a, b]. Since m_* = o(T), it may
be assumed that b + m_* <= 3T/4. For all indices in the enlarged
interval
[a, b + m_*], the entropy deficit, hence the total variation of
s_j on that interval, is at most C E / 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
E_{X^j} D( L(X_{j+1},...,X_{j+m} | X^j)
|| nu_{j, X^j}^{tensor m} )
= m s_j - sum_{i=0}^{m-1} s_{j+i}
= sum_{i=0}^{m-1} (s_j - s_{j+i}). (3.11)
For 0 <= i < m_*, summing over j in [a, b] cancels all interior
telescoping sums:
sum_{j=a}^{b} (s_j - s_{j+i})
= sum_{j=a}^{a+i-1} s_j - sum_{j=b+1}^{b+i} s_j
<= i (s_a - s_{b+i}) <= C i E / T.
The equality for i = 0 means both sides are zero; for i > 0 it is
valid because i <= b - a + 1 for sufficiently large d. Averaging
(3.11) over j with m = m_* gives
E_{j, X^j} D( L(X_{j+1},...,X_{j+m_*} | X^j)
|| nu_{j, X^j}^{tensor m_*} )
<= C m_*^2 E / T^2. (3.12)
The expectation of log|S| - H(nu_{j, X^j}) is log|S| - s_j <= CE/T.
By the cost rules (Lemma 3.3) the argument may condition on the
prefix, keep
T_0 of the remaining coordinates, and change the comparison to
nu_{j, X^j}^{tensor T_0} with cost at most E after averaging in X^j.
All three quantities just bounded are nonnegative. Divide each by
its stated upper scale and average their sum: some common j and
positive-probability prefix meets all three bounds, with a larger
numerical constant. Freeze this choice, set its conditional
marginal to be 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 gives the last line
(3.9c); projection contracts total variation and handles smaller
m. []
Fix the one-letter marginal X ~ nu from Lemma 3.4. A *context* is
a finite-valued random variable W jointly distributed with X.
Start with W = const (denoted empty). A *refinement* replaces W by
(W, A) where A is sampled by a finite channel conditionally on the
current pair (X, W); the marginal of X is unchanged.
For s independent copies of the current pair (X, W), put
G_s(W) = H( sum_{i=1}^s X_i | W_1, ..., W_s ), G_0(W) = 0.
(3.13)
The independence of the pairs entering G_s is part of the
definition. The next quantity permits arbitrary dependence between
its rows:
I_r(W) = inf over joint laws of r pairs (X_a, W_a), each with
marginal (X, W), of
{ r H(X | W)
- H( X_1,...,X_r | sum_{a=1}^r X_a, W_1,...,W_r ) }.
(3.14)
All optimizations are over compact finite simplices with continuous
objectives, so infima are attained.
One more bookkeeping observation is needed. Suppose a trial
prescribes row marginals (B_a, V_a) and a possibly random output Z.
Its conditional entropy cost is
F = sum_a H(B_a | V_a) - H(B^r | Z, V^r) >= 0.
Nonnegativity is conditioning plus subadditivity; equivalently
F = E_{V^r} D( L(B^r | V^r) || prod_a L(B_a | V_a) )
+ I(B^r; Z | V^r).
To extend a trial to new contexts, sample A_a independently across
rows, conditional on the old pairs (B_a, V_a), and independently of
Z given all old pairs. So
L(A^r | B^r, V^r, Z) = prod_a Q_a( . | B_a, V_a ).
Let F' be the cost after the contexts become (V_a, A_a). The chain
rule gives
F - F' = sum_a I(B_a; A_a | V_a) - I(B^r; A^r | Z, V^r)
= sum_a H(A_a | V_a) - H(A^r | Z, V^r) >= 0. (3.15)
For the second equality, conditional independence cancels
H(A_a | B_a, V_a) against H(A^r | B^r, Z, V^r). The last step is
again conditioning plus subadditivity. This calculation applies
even when the old rows are highly correlated.
LEMMA 3.5 (monotonicities and uniform entropy bounds). Let
nu, Psi be as in Lemma 3.4. Define G_s and I_r by (3.13)-(3.14).
There is a constant C'_0(D_0) such that, with
D_* = C'_0(D_0) d, (3.16)
every finite refinement of the initial constant context satisfies:
(i) G_s(W) is nondecreasing in s, nonincreasing under
refinement of W, and 0 <= G_s(W) <= D_* for 0 <= s <= m_*.
(ii) I_r(W) is nonnegative, nondecreasing in r, and
nonincreasing under refinement of W. And I_r(W) <= D_*
for 1 <= r <= T_0.
The same D_* works for all contexts in any finite refinement
sequence.
Proof sketch. (Full details are an accounting exercise that
follows from (3.6)-(3.9) plus the cost rules.)
First bound the correlated sum under Psi. By the cost rules, for
every s <= T_0 the law of (X^s, Gamma) has C_nu <= C E. Relative
entropy to q gives H(Gamma) <= E[-log q(Gamma)] = F_0 + E c(Gamma).
Writing Z_s = sum_{i=1}^s X_i + Gamma, the variables Z_s and Gamma
are translates of one another given X^s, hence
H(Z_s) = I(X^s; Z_s) + H(Gamma | X^s) <= I(X^s; Z_s) + H(Gamma),
and since sum_i X_i = Z_s - Gamma,
H_Psi( sum_{i=1}^s X_i ) <= I(X^s; Z_s) + 2 H(Gamma)
<= 2 F_0 + C E.
Transferring this to independent letters uses (3.9c). If two laws
on a finite alphabet A at total variation distance <= eta can
couple as U, V with P(U != V) = eta (using common submeasure for
common part and left-over submeasures for distinct part). Then
with J = 1_{U != V}, the chain rule gives
H(U) <= H(V) + log 2 + eta log |A|, and the reverse. Applying this
with A = s S and using (3.2) plus m_* sqrt(E)/T <= d^{-1/2+o(1)}
gives an additive error o(d/h^2). So G_s(empty) <= C(D_0) d.
For independent pairs, conditioning on contexts makes the letters
independent, and for independent finite-valued A, B on Z, H(A+B) >=
H(A) after conditioning on B. Applying at each fixed context
tuple and averaging shows G_s(W) is nondecreasing in s. Refinement
decreases G_s (conditioning on more in an iid extension), giving
(i).
Nonnegativity of I_r is that of F. Monotonicity in r comes from
conditioning the (r+1,m)-trial down to r rows and using
H(X^{r+1} | S_{r+1}, W^{r+1})
<= H(X | W) + H(X^r | S_r, W^r),
where S_r = sum_{a=1}^r X_a. Monotonicity under refinement uses
(3.15) with Z = S_r. Finally projecting Psi to r <= T_0 letters
gives an admissible r-row trial at the constant context with
exact-sum cost 2 F_0 + C E, so choosing C'_0(D_0) large enough
covers I_r(empty), and refinement monotonicity proves (ii) with
the same D_*. []
For m independent current pairs, put
Y_m = sum_{i=1}^m X_i and V_m = (W_1, ..., W_m). At a fixed
positive integer r, define
K_m = K_m(W; r)
= inf over joint laws of r row-pairs (Y_{m,a}, V_{m,a}),
each row-pair having law (Y_m, V_m), of
{ r H(Y_m | V_m)
- H( Y_{m,1},...,Y_{m,r} | sum_a Y_{m,a} + Gamma, V_m^r )
+ E c(Gamma) }, (3.17)
where Gamma is allowed to be coupled with the rows subject to
Gamma in TS - TS. As before, the infimum is attained and the
objective is nonnegative.
LEMMA 3.6 (lifting block sums and refining contexts). Let m, r be
positive integers and W a finite context. The value of (3.17) is
unchanged if each row sum Y_{m,a} is replaced in both entropy terms
by its entire m-letter vector, with that row constrained to have
the law of m iid current pairs. The output remains the sum of all
mr letters plus Gamma. Moreover K_m(W; r) is nonincreasing under
finite context refinement.
Proof. Write B_a = (X_{a,1}, ..., X_{a,m}), V_a = (W_{a,1}, ...,
W_{a,m}), Y_a = sum_i X_{a,i}, Z = sum_a Y_a + Gamma. For a
full-vector trial, the full-vector objective minus its projected
sum objective equals
sum_{a=1}^r H(B_a | Y_a, V_a) - H(B^r | Y^r, Z, V^r) >= 0. (3.18)
Equality follows from the chain rule (Y_a is a function of B_a);
inequality from subadditivity and conditioning. So projection to
block sums does not increase cost.
Conversely, from any admissible joint law of (Y^r, V^r, Gamma),
sample each row independently from the genuine iid block law
conditioned on its own sum and contexts:
L(B^r | Y^r, V^r, Gamma) = prod_{a=1}^r L_iid(B_a | Y_a, V_a).
Each full row then has exactly the prescribed iid marginal. Adding
the conditioning on Z (a function of Y^r, Gamma) does not change
these independent row-conditional laws. Hence the last entropy in
(3.18) equals the sum of the first entropies under the lift, so the
objectives are equal and their infima coincide.
For refinement, use this full-vector formulation. At each of the
mr positions, run the prescribed one-letter channel independently
given the old pair, 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 in that row.
Apply (3.15) 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
shows monotonicity.
A new one-letter channel may be specified by an experiment with
auxiliary randomness; run each channel with fresh auxiliary
randomness conditional on its own old pair. Do not substitute the
other actual letters of the row for those auxiliary samples; that
distinction preserves the prescribed iid row marginal. []
The short blocks of Psi are only approximately iid. A later
refinement needs exact iid marginals inside each row. The upgrade
rule selects blocks with a weighted acceptance criterion and fills
the missing row mass.
LEMMA 3.7 (low-end noisy cost). Under Lemma 3.1's hypotheses, fix
nu from Lemma 3.4. Let m, r be positive integers with m <= m_*,
2 m r <= T_0, r <= (T/2) e^{-w^2}. For the constant context and
every finite refinement of it,
K_m(W; r) <= C E, (3.19)
where C is numerical, with the threshold for d allowed to depend
on D_0, P_0.
Proof. Suffices to build a trial at the constant context; the rest
follows from Lemma 3.6. Take 2r disjoint blocks of m coordinates
from Psi. Their common marginal mu on S^m satisfies
eps := ||mu - Q||_TV <= C m_* sqrt(E)/T, Q := nu^{tensor m},
by (3.9c). Define the common submeasure gamma(x) = min(mu(x), Q(x)),
of total mass 1 - eps. Conditional on a block value x with
mu(x) > 0, tag it with probability gamma(x) / mu(x). Tagging
choices may be made independently given all block values. Each
tagged block has unnormalized law gamma; block values need not be
independent.
Let B be the number of tagged blocks. If B < r, reject. If
B >= r, accept with probability B/(2r) and select r distinct
tagged blocks uniformly in random order. Let the acceptance
probability be 1 - delta. Each block fails to be tagged with
probability eps, so
E(2r - B) = 2r eps, P(B < r) <= 2 eps.
The rule then gives
delta = 1 - E[ (B/(2r)) 1_{B >= r} ]
= eps + E[ (B/(2r)) 1_{B < r} ]
<= 3 eps. (3.20)
So delta < 1 for large d.
Marginal of an accepted row, before normalizing by acceptance. Given
the tags, a particular tagged block has probability 1/B of
occupying any specified selected row; multiplying by B/(2r)
cancels B. Hence all selected rows have the same unnormalized
marginal eta, and for every x in S^m
eta(x) = (1/(2r)) sum_{i=1}^{2r}
E[ 1_{B >= r} 1_{i tagged} 1_{block i = x} ]
<= gamma(x) <= Q(x). (3.21)
Its total mass is 1 - delta. This domination motivates the
acceptance weight B/(2r).
On acceptance, keep the selected letters in their selected order
and reuse Gamma. To bound cost, first project Psi to the 2rm
letters used above; its cost to nu^{tensor 2rm} is at most C E.
Record a finite index J = rejection symbol or the ordered tuple of
r selected block indices. The full tag pattern is NOT recorded.
Thus H(J) <= log(1 + (2r)^r) <= log 2 + r log(2r).
By the cost rules, conditioning on J and then projecting and
reordering on accepted outcomes has average cost at most
C E + H(J). Nonnegativity permits dropping rejected outcomes.
Forgetting the ordered indices on accepted outcomes uses convexity
of the combined cost C_nu. Letting P_acc be the normalized
accepted joint law of the mr letters and the error,
(1 - delta) C_nu(P_acc) <= C E + log 2 + r log(2r). (3.22)
Keeping the acceptance mass on the left avoids dividing by a
possibly small conditional acceptance probability.
If delta = 0, accepted rows already have marginal Q, and the
proof is done. Otherwise let R = (Q - eta)/delta; this is a probability
law on S^m by (3.21). Extend the trial by mixing P_acc with weight
1 - delta and r independent blocks of marginal R with weight
delta; on the R part set Gamma = 0. Every row of the mixture has
exact marginal eta + delta R = Q, so this is an admissible
full-vector trial for K_m. The error still lies in TS - TS, which
contains zero.
For the filling law, R <= Q / delta pointwise, so D(R || Q) <=
log(1/delta). Independence between the r blocks makes their
divergence to Q^{tensor r} equal r D(R || Q). The noisy sum is the
exact sum, which lies in mr S, so I(X^s; Z) <= H(Z) <= log |mr S|.
The error cost is c(0) = 0. The weighted extra cost is at most
delta r log(1/delta) + delta log |mr S|. (3.23)
Convexity of C_nu on mixing plus Lemma 3.6's identity bounds K_m
by the sum of the right sides of (3.22)-(3.23).
Scale check. Since w^2 = sqrt(log d) and r <= T e^{-w^2} / 2,
r log(2r) <= C d h^{-5} e^{-sqrt(log d)} log d = o(d/h^2).
Also delta log(1/delta) <= 1/e, so the first term of (3.23) is at
most r/e = o(d/h^2). For the second, (3.20) gives
delta <= d^{-1/2+o(1)} and m r <= T_0/2 < d^2, so (3.2) gives
delta log |mr S| <= d^{-1/2+o(1)} D_0 d h^{P_0} log d = o(d/h^2).
All entropy paid for selection is included. Uniform in admissible
m, r. Since E >= d/h^2, all extra terms are absorbed into a
numerical multiple of E once d is large. This proves (3.19). []
At this point a fixed one-letter law nu, uniformly bounded
G_s and I_r, and the low-end noisy-cost bound (3.19). The next
three statements refine contexts in two orders to reach a
substantially larger block length while retaining comparable noisy
cost, and finally extract a common region of phases.
Two things finish compression. First, a "gluing" statement that
turns a large block observation into a noisy-cost difference, so
that the intermediate quantities drift in a controllable direction.
Second, a finite search that excavates the promised subset S' and
the promised common phase region by exploring block lengths in two
carefully chosen orders, paying total cost O(h^{-2}). After the
search, everything else is a short Markov argument: freeze the
context stack, pick a common region, extract one good coordinate,
and read off the conclusion.
LEMMA 3.8 (a block observation pays a noisy-cost difference). Fix a
current finite-valued context W, integers m >= 2 and r >= 1, and an
independent block of m current pairs (X_i, W_i). Refine the context
of X_1 by observing (sum_{i=1}^m X_i, W_2, ..., W_m), retaining W_1.
For the resulting context W':
G_1(W) - G_1(W') = G_m(W) - G_{m-1}(W), (3.24)
I_r(W) - I_r(W') >= K_m(W; r) - K_{m-1}(W; r). (3.25)
If the observation is made only on an independent Bernoulli mark of
probability zeta in [0,1], retaining the mark in the new context, the
one-letter entropy loss is multiplied by zeta, and the decrease of
I_r is at least zeta (I_r(W) - I_r(W')).
Proof. Independence of pairs gives
I(X_1; sum_{i=1}^m X_i, W_2, ..., W_m | W_1)
= H( sum_{i=1}^m X_i | W_1, ..., W_m )
- H( sum_{i=2}^m X_i | W_2, ..., W_m ),
proving (3.24).
For (3.25): take independent minimizing trials for I_r(W) and
K_{m-1}(W; r). Their alphabets, including TS - TS, are finite, so
minimizers exist. Write
U = (U_a)_{a=1}^r, W-vec = (W_a)_{a=1}^r,
Y = (Y_a)_{a=1}^r, V-vec = (V_a)_{a=1}^r,
where each (Y_a, V_a) has the sum-and-context law of an independent
(m-1)-letter block. Set P = (W-vec, V-vec), Z_U = sum_a U_a,
Z_Y = sum_a Y_a + Gamma. The whole (U, W-vec) trial is independent
of the whole (Y, V-vec, Gamma) trial. Hence (U+Y, P, Gamma) is
admissible for K_m(W; r) and (U, (U+Y, P)) with 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:
H(U_a + Y_a | W_a, V_a) + H(U_a | U_a + Y_a, W_a, V_a)
= H(U_a, Y_a | W_a, V_a)
= H(U_a | W_a) + H(Y_a | V_a).
For the subtracted joint entropies, condition both terms on both old
outputs:
H(U+Y | Z_U + Z_Y, P) + H(U | U+Y, Z_U, P)
>= H(U+Y | Z_U, Z_Y, P) + H(U | U+Y, Z_U, Z_Y, P)
= H(U, Y | Z_U, Z_Y, P) (3.26)
= H(U | Z_U, W-vec) + H(Y | Z_Y, V-vec).
The middle equality uses the invertible map (U,Y) -> (U+Y, U); the
last uses independence of the old trials. This argument allows
Gamma to be random. The error cost is unchanged. Adding the new
trial costs and taking infima yields
K_m(W; r) + I_r(W') <= K_{m-1}(W; r) + I_r(W).
For a partial observation W^{(zeta)}, condition on the independent
mark: the entropy loss multiplies by zeta. To bound its exact
cost, synchronize the mark across rows, using a minimizing old
coupling on mark zero and a minimizing fully refined coupling on
mark one. This has the prescribed refined pair marginal in each
row, so
I_r(W^{(zeta)}) <= (1 - zeta) I_r(W) + zeta I_r(W').
[]
Block ranges are chosen whose lower endpoints decrease as their row
counts increase. For sufficiently large d put
Q = floor( (w^3/2 - w^2) / (3w) ), M = Q + 1,
and for 1 <= j <= M:
m_{j,0} = ceil( exp( w^2 + 3 w (M-j) ) ),
r_j = floor( T_0 / (2 m_{j,0}) ),
m_{j,1} = ceil( L / r_j ). (3.27)
M is asymptotic to w^2. Uniformly in j, T_0/(2 m_{j,0}) -> inf,
so
T_0/(4 m_{j,0}) <= r_j <= T_0/(2 m_{j,0}),
1 < m_{j,1}/m_{j,0} <= 4L/T_0 + 1/m_{j,0} <= e^{2w}.
Successive lower endpoints have ratio at least
e^{3w}/(1 + e^{-w^2}) > e^{2w}, so the integer ranges
[m_{j,0}, m_{j,1}] are disjoint and descend as j increases. The
floors also make r_j increase strictly. Moreover,
e^{w^2} <= m_{j,0} < m_{j,1} <= m_*,
2 r_j m_{j,0} <= T_0,
r_j <= T e^{-w^2}/8,
L <= r_j m_{j,1} < L + r_j < 2L < d^2. (3.28)
The low endpoints satisfy all hypotheses of (3.19), and every G_s,
I_{r_j} used below is bounded by D_*.
PROPOSITION 3.9 (finite refinement search). Under Lemma 3.1's
hypotheses, there is a finite sequence of context refinements from
empty context to W, and an index j, such that
G_1(empty) - G_1(W) <= C D_*^2 / (E h^2), (3.29a)
K_{m_{j,1}}(W; r_j) <= K_{m_{j,0}}(W; r_j) + E. (3.29b)
C is numerical; every context produced is finite-valued.
Proof. Normalize by a_j = I_{r_j}/D_*, g_s = G_s/D_*,
tau = E/D_* in (0,1]. These lie in [0,1]. At a fixed state a_j
increases with j, g_s increases with s; all decrease under
refinement. Measure refinement cost by tau times the loss in g_1;
total cost c means entropy loss c D_*^2 / E.
Available updates. Suppose the K inequality (3.29b) fails at index
j in a given state. Consider separately, from the same state, the
full observations of Lemma 3.8 for m_{j,0} < m <= m_{j,1}. Let
d_m >= 0 be their decrease in a_j and c_m >= 0 their cost.
Telescoping (3.25)-(3.24) gives
sum_m d_m > tau, sum_m c_m = tau p_j,
p_j = g_{m_{j,1}} - g_{m_{j,0}}.
For p_j > 0, offers with c_m > 2 p_j d_m have total decrease less
than tau/2; the others have total decrease > tau/2. There are at
most m_* offers, so one satisfies
d_m >= eta := tau / (2 m_*), c_m <= 2 p_j d_m. (3.30)
If p_j = 0, all costs are zero and (3.30) 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 2 p_j x.
Two visit orders. The update decreases a_j at cost controlled by
the current width p_j. But g-endpoints, though each decreasing,
can have widening difference. Work stops at an index when the
difference between the g-value at the top endpoint on entry and the
g-value at the bottom endpoint in the current state is too large
relative to the cost spent there. Two comparisons determine the
order. First, at indices visited in increasing order, block-length
ranges descend, and the "upper endpoint on entry" is at most the
"lower endpoint on exit" -- so the endpoint differences telescope
in [0,1] and control skips. Second, completed decreases of a_j
telescope in decreasing 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, descending
subblocks within a macroblock to control completed decreases, and
increasing macroblocks to control remaining skips. The thresholds
make the total cost O(h^{-2}).
Partitions. Put
N = floor(M^{1/10}), n = floor(M^{1/2}),
u = (log N)^{-2}, q_* = ceil(2/u),
alpha_0 = 100 u / log n, delta_0 = n^{-1/2},
alpha_1 = 10^5 / (log n log N), delta_1 = N^{-1/2}. (3.31)
Take d large so N >= 4. Partition the first N q_* n indices into N
successive macroblocks, each containing q_* successive subblocks of
n indices. There is room: N q_* n <= M^{3/5} (1 + (log M)^2/50) <=
M. Process macroblocks in ascending index order; within a
macroblock, subblocks in descending order; within a subblock,
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 (3.29b) stops everything. 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
p = g_{m_{j,1}}(entry to j) - g_{m_{j,0}}(current state).
This nonnegative quantity dominates the current p_j. Skip index j
if
p > c_0 / alpha_0 + delta_0. (3.32)
Otherwise check (3.29b). If it fails, take an offer (3.30). Write
Delta_j = a_j(entry to j) - a_j(current) < u for the decrease
already achieved at this index, and choose the partial observation
with target x = min(d_m, u - Delta_j). Repeat until skip,
completed target, or discovery. The sum of the targets x in one
index is at most u; each unclipped target equals d_m >= eta, so the
loop is finite.
At every update the skip test (3.32) has failed, so
Delta c_0 <= 2 (c_0/alpha_0 + delta_0) x,
c_{0,new} + alpha_0 delta_0
<= (c_{0,old} + alpha_0 delta_0) (1 + 2x/alpha_0).
Starting at c_0 = 0, and using 1 + t <= e^t,
c_0 <= alpha_0 delta_0 (e^{2u/alpha_0} - 1)
<= alpha_0 n^{-12/25} <= alpha_0 n^{-2/5}. (3.33)
Write H, ell for the highest and lowest block endpoints in the
current macroblock and set
P = g_H(entry to macroblock) - g_ell(current) in [0,1].
For successive skipped indices j < j' within a subblock, block
ranges descend, so m_{j',1} < m_{j,0}. Decrease over refinement
time gives
g_{m_{j',1}}(entry to j')
<= g_{m_{j,0}}(exit from j). (3.34)
Thus p at skips sum to at most P, including at intermediate states.
A skipped index has c_0 < alpha_0 (p - delta_0) <= alpha_0 p and
p > delta_0. So there are fewer than 1/delta_0 = sqrt(n) skips;
not all n indices can be skipped. Skipped attempts cost at most
alpha_0 P; at most one other (active or terminal) index attempt
exists. By (3.33) every prefix or completed run of the subblock
costs at most
alpha_0 (P + n^{-2/5}). (3.35)
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
P > c_1 / alpha_1 + delta_1. (3.36)
Target indices decrease strictly between completed subblocks. For
successive such indices j > j', monotonicity in index and time
gives
a_{j'}(entry to j') <= a_j(exit from j). (3.37)
Their actual targeted decreases telescope to at most 1. At most
1/u subblocks can complete targets, whereas there are q_* > 1/u
subblocks. So this macroblock must be skipped or discover (3.29b)
before it can be exhausted.
For a completed subblock after which no macroblock skip is made
and processing continues, apply (3.35) with the new P, and use
failure of (3.36):
c_{1,new} - c_{1,old}
<= alpha_0 (c_{1,new}/alpha_1 + delta_1 + n^{-2/5}).
Put beta_* = alpha_0/alpha_1 = 1/(1000 log N),
delta_* = delta_1 + n^{-2/5}. Iteration over at most 1/u such
runs yields
c_1 <= alpha_1 delta_* ( (1 - beta_*)^{-1/u} - 1 ) <= alpha_1. (3.38)
Indeed n >= N^5, so n^{-2/5} <= N^{-2}. Also
-log(1 - beta_*) <= 2 beta_*, hence
(1 - beta_*)^{-1/u} <= N^{1/500}. The multiplier of alpha_1 is at
most N^{-249/500} + N^{-999/500} < 1 for N >= 4. One last or
partial subblock costs at most 2 alpha_0 by (3.35) with P <= 1.
Across macroblocks and termination. Macroblocks advance in index
order, so block ranges descend as in (3.34). The values of P at
macroblocks skips sum to at most one. Total cost at most alpha_1;
fewer than 1/delta_1 = sqrt(N) macroblocks can be skipped. Since a
macroblock cannot be exhausted without a skip or discovery, the
entire search must discover (3.29b). Its loops are finite by the
positive minimum offer before clipping. Total cost through
discovery is bounded by
alpha_1 (skipped macroblocks)
+ alpha_1 (continuing subblocks)
+ 2 alpha_0 (last subblock)
<= 4 alpha_1.
Both telescopes allow decreases caused by intervening refinements.
Since h = 4 log w and M is asymptotic to w^2, both log n and
log N are of order h. Hence 4 alpha_1 <= C/h^2. Undoing the
normalization proves (3.29a)-(3.29b). Each new observation and
mark has a finite alphabet, so the finite sequence leaves a
finite-valued context. []
Lemma 3.1 is closed out.
Completion of the proof of Lemma 3.1. Use the context W, index j,
and high endpoint m = m_{j,1} from Proposition 3.9. Put r = r_j and
s = m r >= L. Combining (3.29a)-(3.29b) with (3.19) (preserved
under refinement) gives
K_m(W; r) <= C E. (3.40)
Lift a minimizing coupling to all s letters using the full-vector
interpretation (Lemma 3.6). Write W-bar = (W_i)_{i=1}^s for the
whole context stack, and nu_z for the prescribed one-letter
conditional law given context z.
For any fixed stack w-bar of positive probability, compute
C(w-bar)
= D( X^s || prod_i nu_{w_i} ) + I(X^s; Z) + E c(Gamma),
Z = sum_i X_i + Gamma, (3.41)
under the actual conditional law at that stack. All three terms
are nonnegative. The conditional letter marginals after freezing
the whole stack may differ from the comparators nu_{w_i}, but the
comparison has finite divergence: an event X_i = x, W_i = w_i with
nu_{w_i}(x) = 0 has probability zero even before conditioning, and
so also at any positive-probability stack. Before freezing, each
row has its prescribed independent block marginal, so
E[-log prod_i nu_{W_i}(X_i)] = s H(X | W).
Subtracting H(X^s | Z, W-bar) and adding the error cost gives
E C(W-bar) = K_m(W; r) <= C E.
For the separate quantity
B(w-bar) = s^{-1} sum_i D(nu_{w_i} || U_S), the prescribed pair
marginals give
E B(W-bar) = log |S| - H(X | W)
= log |S| - H(nu) + G_1(empty) - G_1(W)
<= C E / T + C D_*^2 / (E h^2)
<= C(D_0) d^2 / (E h^2). (3.42)
The E/T term is absorbed because T ~ d/h^5, E <= D_0 d, and
E^2 h^7 / d^3 -> 0 for fixed D_0. Markov's inequality (factor four
each) selects one stack with
C(w) <= C E, B(w) <= C(D_0) d^2 / (E h^2). (3.43)
Freeze this stack. (A zero-mean quantity is zero a.s., covering
that case.)
A large independent noisy-sum atom. Let p = prod_i nu_{w_i}, and
compare the actual conditional law of (X^s, Gamma) with the
independent law p x q. The map (X^s, Gamma) -> (X^s, Z) is
invertible, and -log q(Gamma) = F_0 + c(Gamma). So
C(w) = D( (X^s, Gamma) || p x q ) + H(Z) - F_0. (3.44)
Let Q_Z be the sum law under p x q. Data processing gives
C(w) + F_0 >= D( L(Z) || Q_Z ) + H(Z)
= E[-log Q_Z(Z)].
So some integer z_* in the support of the actual output satisfies
Q_Z(z_*) >= e^{-F_0 - C E} = q(0) e^{-C E}. Divide the convolution
formula by q(0) and use (3.1):
e^{-C E}
<= Q_Z(z_*) / q(0)
= integral chi_{g z_*}(theta)
prod_i E_{nu_{w_i}} chi_{-g X}(theta) d omega(theta)
<= integral prod_i |E_{nu_{w_i}} chi_{g X}(theta)| d omega(theta). (3.45)
The last step takes absolute value of the integral, which is a
positive real mass.
One region and one coordinate. Put
phi_i(theta) = E_{nu_{w_i}} chi_{g X}(theta) and
A(theta) = sum_i (1 - |phi_i(theta)|^2).
The bound 0 <= |phi_i| <= 1 implies prod_i |phi_i| <= e^{-A/2}.
Choose a numerical C_R larger than twice the constant in (3.45),
with fixed extra margin, and set R-phase = {A <= C_R E}. Since
E >= d/h^2 >= 1, the contribution of R-phase^c to (3.45) is at most
half its lower bound. The product is at most one, so
omega(R-phase) >= e^{-C E},
sum_i integral (1 - |phi_i|^2) d omega_{R-phase} <= C E, (3.46)
where omega_{R-phase} is normalized restriction to R-phase.
Average the second bound over a uniform choice of coordinate using
(3.43)-(3.46). Some coordinate satisfies
integral (1 - |phi_i|^2) d omega_{R-phase} <= C E / s,
D(nu_{w_i} || U_S) <= C(D_0) d^2 / (E h^2). (3.47)
Only numerical factors lost in the first bound. Write mu = nu_{w_i}.
A center and a subset valid for every weight. For independent
X, X-breve ~ mu,
1 - |phi_i(theta)|^2
= E[1 - Re chi_{g(X - X-breve)}(theta)].
Averaging over omega_{R-phase} and then over X-breve selects
x_0 in supp mu subset S with
sum_x mu(x) integral (1 - Re chi_{g(x - x_0)}) d omega_{R-phase}
<= C E / s.
Prune by Markov to a subset S' subset supp mu of mu-mass at least
1/2, on which every x satisfies
integral (1 - Re chi_{g(x - x_0)}) d omega_{R-phase}
<= C E / s. (3.48)
If the average defect is zero, the zero-defect set has full mu-mass
and works for S'. In all cases S' is nonempty.
Write t = mu(S') >= 1/2 and v_0 = |S'|/|S|. Binary data
processing gives
D(mu || U_S) >= t log(t/v_0) + (1-t) log((1-t)/(1-v_0))
>= t log(1/v_0) - log 2.
Combined with (3.47):
log |S| - log |S'| <= 2 D(mu || U_S) + 2 log 2
<= C(D_0) d^2 / (E h^2).
The constant is absorbed because d^2/(E h^2) -> inf.
Finally, let v be any probability on this S'. By (3.48), its
averaged phase defect on R-phase is at most C E / s. Jensen and
L <= s yield
integral exp( -L sum_{x in S'} v(x)
(1 - Re chi_{g(x - x_0)}(theta)) )
d omega(theta)
>= omega(R-phase) * exp( -L sum_x v(x)
integral (1 - Re chi_{g(x - x_0)}) d omega_{R-phase} )
>= e^{-C E} * e^{-C E L / s} >= e^{-C E}.
The region, center, and subset were fixed before v was chosen,
establishing the conclusion for every probability on S'. This
proves Lemma 3.1. []
A label is a noisy observation of the input point: Z = Y + theta on
the circle, where theta has density proportional to e^{-A(y)} and A
is a nonnegative sum of elementary terms (1 - cos(2 pi s y)), s in Z.
Griffiths-Ginibre positive correlation makes Fourier coefficients of
e^{-A} nonnegative, so adding a new term to A pushes the density in
a predictable direction. When the spectrum looks "spread out", a
label may be upgraded by compression; the upgrade either produces an
event unlikely under a comparison law, or enlarges the set of
phase-stable frequencies, and both prices are bounded. Together
these account for the total "temperature cost" of the labels. The
labels enter only after being drawn: the choice of channel, of
spatial interval, and of membership set is always made from the
spatial prefix and input memberships, never from the realized noise.
This distinction is what makes the comparison-law arguments clean.
A *thermal form* on the unit circle is a finite sum
A(y) = sum_s lambda_s (1 - Re chi_s(y)), lambda_s >= 0,
with s ranging over integers and only finitely many lambda_s
nonzero. Write A precedes A' if A' = A + D for some thermal form D.
Define, for u in Z,
q_A(u) = integral_T e^{-A(y)} conj(chi_u(y)) dy,
F(A) = -log q_A(0),
K_A = e^{F(A) - A},
Delta_A(u) = ( integral_T |1 - chi_u(y)|^2 K_A(y) dy )^{1/2},
B_A(r) = { u in Z : Delta_A(u) <= r }. (5.1)
Then K_A is a probability density: its integral is e^{F(A)} q_A(0)
= 1. All circle integrals in this section use normalized measure
of total mass one. The number Delta_A(u) is the size of the phase
defect of the character chi_u under the noise, and B_A(r) is the
"ball" of characters whose phases are stable to level r. The number
F(A) is the free energy of the form A.
LEMMA 5.1 (thermal positivity and monotonicity). For every thermal
form, q_A is a nonnegative, even probability mass function on Z.
The Fourier coefficients integral chi_u K_A = q_A(u)/q_A(0) are real
and nonnegative. For all integers u, v,
Cov_{K_A}( Re chi_u, Re chi_v ) >= 0. (5.2)
Consequently these coefficients are nondecreasing in form order,
Delta_A(u) is nonincreasing in form order, and
Delta_A(u+v) <= Delta_A(u) + Delta_A(v). (5.3)
The function F is nondecreasing in form order. For every thermal
form D, the increment F(A+D) - F(A) is nonincreasing when A is
increased in form order.
When P = sum_j P_j is a finite sum of thermal forms and
P_lo precedes P precedes P_hi, then for arbitrary shifts z_j and
every integer u,
| integral chi_u(y) prod_j e^{-P_j(z_j - y)} dy |
<= q_P(u) <= e^{-F(P_lo)} integral chi_u K_{P_hi}. (5.4)
Proof. Expand each factor:
e^{-lambda (1 - Re chi_s)}
= e^{-lambda} * exp((lambda/2) chi_s) * exp((lambda/2) chi_{-s}).
Each factor is an absolutely summable Fourier series with nonnegative
coefficients summing to one; their finite product is thus absolutely
summable with sum one at zero, so q_A is a probability mass function.
Evenness of cos gives q_A(-u) = q_A(u).
Covariance calculation. Put c_s(y) = cos(2 pi s y) and
Z_A = integral_T exp(sum_s lambda_s c_s(y)) dy. Write the covariance
as half the expectation, over two independent copies X, Z of K_A,
of sum_u-part difference * sum_v-part difference. Under the 2D
torus map (x, z) -> (x + z, x - z), Haar measure goes to Haar; the
two differences become
-2 sin(2 pi u x) sin(2 pi u z),
-2 sin(2 pi v x) sin(2 pi v z),
and the unnormalized density becomes
exp(2 sum_s lambda_s c_s(x) c_s(z)). Expanding this exponential
in a power series and integrating,
Cov_{K_A}(c_u, c_v) = (2/Z_A^2) * sum over (n_s) >= 0 of
[ prod_s (2 lambda_s)^{n_s} / n_s! ]
* ( integral sin(2 pi u x) sin(2 pi v x)
prod_s c_s(x)^{n_s} dx )^2.
Every term is nonnegative; absolute convergence of the expansion
justifies passing integrals through the sum; so Cov >= 0.
Differentiate under the integral:
d/d lambda_v of integral_T c_u K_A = Cov_{K_A}(c_u, c_v),
d/d lambda_u of F(A) = integral_T (1 - c_u) K_A.
The second derivative is a nonnegative quantity, so F is monotone in
every coefficient; the first derivative is a covariance, so the
Fourier coefficient of K_A at frequency u increases in every
nonnegative direction; so Delta_A(u)^2 = 2(1 - integral c_u K_A)
decreases. Decreasing-increments of F(A+D) - F(A) follows from
concavity along each direction. Subadditivity of Delta follows
from the phase identity 1 - chi_{u+v} = (1 - chi_u) + chi_u (1 -
chi_v) and the triangle inequality in L^2(K_A).
For (5.4): translation multiplies each Fourier coefficient of e^{-P_j}
by a unit complex number. The absolute-value convolution of these
coefficients is bounded by the convolution of the centered ones,
which is exactly q_P(u). Finally q_P(u) = e^{-F(P)} integral chi_u
K_P, and both comparisons of (5.4) follow from the monotonicities
already proved. []
For a real interval p of length at most one, put
R_p = |p|^{-1}, S_p(y) = R_p^2 (1 - Re chi_1(y)).
The interval may be viewed on the circle when integrating. The
following bounds are used (also with any larger spatial scaling
in place of R_p):
F(S_p) = log R_p + O(1),
integral (1 - Re chi_1) K_{A + S_p} <= C R_p^{-2},
q_{S_p}(u) >= c R_p^{-1} (|u| <= c R_p),
Delta_{A + S_p}(u) <= C |u| / R_p. (5.5)
Indeed, ||y|| denoting distance to the nearest integer,
8 ||y||^2 <= 1 - cos(2 pi y) <= 2 pi^2 ||y||^2. Gaussian
comparison gives integral e^{-S_p} asymptotic to R_p^{-1} and
integral (1 - Re chi_1) K_{S_p} <= C R_p^{-2}. Monotonicity in form
order gives the second line for any A + S_p. The inequality
|1 - chi_u| <= |u| |1 - chi_1| yields the last line; the
same inequality, with sufficiently small |u|/R_p, gives
integral chi_u K_{S_p} >= 1/2, proving the lower bound on q_{S_p}.
In particular integral S_p K_{A + S_p} <= C.
Interpretation. S_p is a "spatial concentration" form that pins the
input point to an interval of length R_p^{-1}. Its free energy is
roughly log R_p, since R_p in density is paid to concentrate over
R_p lattice points, then log R_p to normalize. Its metric is
roughly |u|/R_p: characters oscillating faster than the interval
width get blurred. These numbers recur in every constant below.
Take b_0 dyadic with h^{-16}/2 < b_0 <= h^{-16}. The computation
levels are the dyadic b from b_0/8 to 1, and put
k_b = A_0 * (d/h) * (1 + log(1/b))^2,
r_sep = h^{-30}, sigma = h^{-40}. (5.6)
The constant A_0 will be chosen large and fixed. Every estimate
below holds for sufficiently large d, uniformly in spatial depth
and in any frequency cutoff.
A *label of type A* is Z = Y + theta mod 1, where the error theta
has density K_A relative to Haar measure. Initially A = 0, so a
dummy independent uniform label may be drawn. Only the current
*main* channel is used in the spectral and transform computations;
successive updates add a spatial and a metric form,
A^+ = A + S_p + D_i.
The errors drawn at different labels are independent given Y. Their
parameters are chosen from spatial prefixes and earlier input
membership events, never from the realized noise. Conditional on
Y and on the discrete parameter path, the errors therefore have
their prescribed independent laws.
Two facts about tightening a form are needed:
LEMMA 5.2 (cost of tightening a form). Let C_0, C_* >= 1. Let
A arise from the initial form 0 by fewer than C_0 h additions of
spatial and metric forms, each metric addition satisfying (5.7)
below. Let p subset p_*, where p_* is the latest addition interval
(or the top interval of length in [1/2,1] if there has been no
addition), and assume
F(A) <= log R_{p_*} + C_* d. (5.6')
On p suppose
0 <= a <= e^d, e^{-d} <= m = E_p a <= 2 alpha, alpha > 0.
The form A_base is A immediately before any addition, including the
new spatial form:
F(A_base + h^{140} D_i) - F(A_base + D_i / 2) <= d h^{-400}. (5.7)
Then, with A-tilde = h^{130} A + C_s S_p for a sufficiently large
fixed C_s,
F(A-tilde) - F(A + S_p) <= C + C C_0 h (d h^{-400} + C log h),
integral A K_A <= C C_0 h (d h^{-400} + 1). (5.8)
Proof. Enlarge the constituent forms one at a time.
For an old metric term D_i, decreasing increments bound its cost of
tightening by the left side of (5.7): the other terms already contain
its original A_base. Tightening an old spatial term S_{p_i} costs
at most
F(h^{130} S_{p_i}) - F(S_{p_i}) <= C(1 + log h)
by (5.5). Tightening the newly inserted S_p to C_s S_p costs O(1).
For the energy bound, concavity along the D_i direction plus (5.7)
gives
integral D_i K_A
<= 2 (F(A_{base,i} + D_i) - F(A_{base,i} + D_i/2))
<= 2 d h^{-400}.
Each spatial constituent contributes O(1) by (5.5) and monotonicity.
This energy argument uses the count bound and (5.7) but not (5.6');
it remains valid, with the same type of bound, just after a final
allowed addition that breaches a later stopping cap. []
The spatial increment itself obeys
F(A + S_p) <= F(A) + log(R_p/R_*) + C, (5.9)
which follows from (5.5) and the spatial energy bound. After an
addition, A contains S_{p_*}, so q_A(u) >= c e^{-F(A)} for
|u| <= c R_*. Convolution with q_{S_p} over those integers gives
q_{A + S_p}(0) >= c e^{-F(A)} R_*/R_p. Initially the term u = 0
alone suffices, and 1 <= R_* <= 2.
Consider a subdensity a at an interval p, with
0 <= a <= e^d, e^{-d} <= m = E_p a <= 2 alpha, alpha > 0.
E_p is the uniform spatial average over p, and P is the law of
Y with density a/m against that average. For either prospective
child p' define
M_{p'}(z) = E_{p'}[a K_A(z - Y)] / alpha,
f_{p'}^u(z) = E_{p'}[a chi_u(Y) K_A(z - Y)] / alpha,
G_{p'}^u = integral |f_{p'}^u(z)|^2 / M_{p'}(z) dz. (5.10)
The integrand is zero wherever the mass vanishes. Say u is *high
at level b* if some G_{p'}^u >= b^2. A *test* requests an update if
there is a collection of ceil(e^{k_b}) high integers whose pairwise
differences avoid
B_A(r_sep) + { j in Z : |j| <= sigma R_p }. (5.11)
One offending level and one collection are used at a time.
Keep at least half this collection having a common high child, and
snap each retained integer to its nearest multiple g x, where
g = max(1, floor(sigma R_p / 20)).
The snapping error is at most sigma R_p / 20, zero when g = 1. The
snapped indices are distinct (otherwise the original difference
would violate (5.11)). Let S be the resulting set of integer
indices x. For each x in S choose a measurable complex function v_x
with |v_x| <= 1 so that
Re E_P[ 1_child v_x(Z) chi_{gx}(Y) ] >= beta, beta = b^2/100. (5.12)
The expectation includes the type-A channel. Bias note:
|f_{p'}^u| <= M_{p'} implies integral |f_{p'}^u| >= G_{p'}^u.
Choosing the polarizing sign gives bias (alpha/(2m)) * integral
|f_{p'}^u| >= b^2/4 before snapping. A constant phase rotation at
the center of p makes the u to g x replacement error at most
C sigma, smaller than the required slack, because sigma = o(b^2)
uniformly over the computation levels.
Apply Lemma 3.1 with
d omega = K_{A-tilde} dy,
q(x) = q_{A-tilde}(g x) / N_g,
N_g = sum_{x in Z} q_{A-tilde}(g x).
The spatial frequency-one term makes every Fourier coefficient
strictly positive: in the exponential expansion, every integer
frequency occurs with positive coefficient. So q is strictly
positive. The grid identity and Gaussian comparison give
N_g = (1/g) sum_{l=0}^{g-1} e^{-A-tilde(l/g)},
1/g <= N_g <= C/g. (5.13)
Indeed g <= R_p and the summands are bounded by
exp(-c R_p^2 ||l/g||^2). Also R_p / g <= C / sigma, also when g = 1
by its definition. Hence (5.8) and (5.5) give
F_0 = -log q(0) <= F(A-tilde) - log g + O(1) <= D_0 d
for a fixed D_0 depending only on the caps. Evenness gives exactly
q(x)/q(0) = integral chi_{gx} d omega.
Two remaining uniform hypotheses of Lemma 3.1.
Sumset size. The dissociated-spectrum method underlies
Chang's lemma, in its entropy-plus-positive-product form. The
calculation includes the side information carried by the label: the
comparison law makes that information independent of the uniform
circle coordinate.
The law of gY mod 1 has density at most e^{2d}(1 + R_p/g): its
preimage count in p is at most g/R_p + 1, and the density of Y
relative to circle length is at most R_p e^{2d}. Also
I(Y; Z) <= F(A) - log R_* + C. (5.14)
Compare each K_A(z - Y) to the fixed density K_{S_{p_*}}(z - c_{p_*}).
The average relative entropy is
F(A) - F(S_{p_*}) - integral A K_A
+ E S_{p_*}(theta + Y - c_{p_}).
The last expectation is O(1) (use S(v+w) <= 2 S(v) + 2 S(w), the
spatial energy bound, and |Y - c_{p_*}| <= |p_*|/2). In the initial
case A = 0 and R_* <= 2 the same bound is immediate. Dropping the
nonpositive term proves (5.14).
Let Q_side = (Z, child bit). Data processing gives
D((gY, Q_side) || uniform x L(Q_side))
= D(gY || uniform) + I(gY; Q_side) <= C(C_*) d.
If Lambda subset S is *dissociated* (no nonzero {0, +-1}-coefficient
combination of Lambda sums to zero), form the positive product
prod_{x in Lambda} (1 + c beta Re[1_child v_x(Z) chi_x(gY)]).
For sufficiently small numerical c the factors lie in [1/2, 3/2].
Under the reference law the first coordinate is uniform and
independent of Q_side; expansion and dissociation make the
expectation of the product exactly one. Relative entropy is at
least the true expectation of log of this product. The inequality
log(1+s) >= s - C s^2 together with (5.12) bounds the true log
below by c' beta^2 per factor. Hence
|Lambda| <= C(C_*) d / beta^2.
A maximal dissociated subset spans S by {0, +-1} coefficients;
otherwise adjoining an unspanned element preserves dissociation.
Consequently
|n S| <= (2n+1)^{|Lambda|},
log |n S| <= D_0 d h^{P_0} log d (1 <= n <= d^2) (5.15)
for fixed D_0, P_0, because beta >= c h^{-32}.
The uniform moment cap. For any probability nu on S, put
E_T(nu) = -log E_nu H_q( sum_{i=1}^T X_i - sum_{i=1}^T X'_i ),
e^{-E_T(nu)}
= integral | sum_x nu(x) chi_{gx}(y) |^{2T} K_{A-tilde}(y) dy, (5.16)
where the 2T letters are independent with common law nu. Then
0 <= E_T(nu) <= D_0 d for every such nu. (5.17)
Upper proof. Restrict Z to the domain Omega at circle distance at
most h^{40}/R_* from p. The channel's spatial variance bounds the
discarded probability by C h^{-80} (the assertion is trivial if
Omega is the whole circle). This loses o(beta) in (5.12). Summing
the biases with weights nu and applying Jensen on a subprobability
measure gives
E_P[1_child 1_{Z in Omega}
| sum_x nu(x) v_x(Z) chi_{gx}(Y) |^{2T}]
>= (beta/2)^{2T}.
For an upper bound discard the child indicator. At fixed z, first
MAJORIZE the nonnegative moment integrand using the spatial density
bound R_p e^{2d} and
1_p(y) <= exp(C - S_p(y - center(p))).
Only after this majorization, expand the even power and the shifted
thermal weights. By (5.4), the Fourier coefficients of those
weights are bounded in absolute value by
C q_{A + S_p}(u) <= C e^{-F(A + S_p)} integral chi_u K_{A-tilde}.
The coefficients v_x(z) have modulus at most one. The absolute
coefficient sum in the even-power expansion averages this envelope
at u = g(sum X_i - sum X'_i) over the independent letters in (5.16).
Using |Omega| <= C h^{40}/R_*, the joint moment is at most
C R_p e^{2d + F(A)} * h^{40}/R_* * e^{-F(A+S_p)} * e^{-E_T(nu)}.
Now F(A + S_p) >= log R_p - C, F(A) <= log R_* + C_* d, and
T log(2/beta) = o(d). Comparison with the lower moment proves
(5.17) after increasing D_0. []
This argument uses a density bound only inside a *nonnegative
integral*. It does NOT assert a Fourier-coefficient upper bound on
a itself. This is essential: (5.17) is used only at one fixed
weighting and one fixed label channel, so no uniformity in a is
required.
LEMMA 5.3 (spectral update). Fix C_0, C_* >= 1. Suppose the current
form A arose from 0 by fewer than C_0 h additions of spatial and
metric forms, each metric satisfying (5.7). Let p subset p_*, where
p_* is the latest addition interval (or the top interval if there
has been none), and assume F(A) <= log R_{p_*} + C_* d. On p
suppose 0 <= a <= e^d and e^{-d} <= m = E_p a <= 2 alpha with
alpha > 0. Suppose there is a request at computation level b in the
sense of (5.11), using the child moments (5.10) and the type-A
channel. There are numerical constants C_1, C_2 and a sufficiently
small numerical epsilon > 0 with the following property. After
caps are fixed, choose fixed large D_0, P_0, then A_0, and finally
take d sufficiently large. A finite deterministic construction
supplies a parameter
d / h^2 <= t <= D_0 d, t >= epsilon k_b,
a thermal metric form D_i = lambda B, and an input-only success set.
On success set A^+ = A + S_p + D_i. The new metric satisfies (5.7)
and
A^+ = A + S_p + D_i, integral B K_{A^+} <= C_1 t / lambda,
lambda >= d h^{200}, h^{140} lambda <= L,
F(A^+) - F(A + S_p) <= C_1 t. (5.18)
There are two alternatives:
(a) Regular update. The success probability delta of the
success set against the input law is at least c b^2. The
probability under the input law that a witness event whose
direction determines a "shift" occurs is bounded below:
E_P[1_success 1_evidence] >= delta e^{-C t / 8} / 8.
(b) Cheap update. The success set is the entire input. Then
delta = 1, and one of the following holds on success: the
covering-ball radius r increases by at least
r_sep/(10 C_0 h), or the empirical gap
F(A) - log |B_A(r)| decreases by at least h^{-2}.
"Cheap" happens when the moment cap (5.17) has already
been crossed: the compression is trivially available (the graph is
already strongly concentrated, no expensive test is needed). The
two cases are recorded separately because the charges differ.
Proof. The construction is:
Stage 1. Apply Lemma 3.1 (entropy compression) at E = 5 t/8 to the
probability set S from (5.11), with d omega = K_{A-tilde} dy. Get
subset S', center x_0, and the uniform bias (3.5). The
cardinality loss is C(D_0) d^2 / (E h^2) = O(1) coordinates.
Stage 2. Restrict to those weights under which the "bad"
alternative does not already hold at level t/4. Test each coordinate
of S' for the bias at t/4; if the resulting set of weights is
nonempty, use it as the new S' and iterate. Every nonterminal
iteration reduces the test parameter by at least a factor of four;
so the process terminates after O(log(1/b_0)) iterations. The
total logarithmic cardinality loss is bounded by C(D_0)
d^2/(epsilon k_b h^2), whose exponential is a fixed polynomial in
d that is absorbed into A_0 for suitable choice of A_0.
Stage 3. If the "cheap" alternative is available (the empirical
moment cap is at or above t/4), terminate with a cheap update on
the full set. Otherwise continue to a regular update. In the
regular case a witness collection is chosen (the "shift" mentioned
above) from the covering argument. The witness event is an event
under the input law that, given success at level 4t/8 = t/2, occurs
with conditional probability at least e^{-t/8} / 8. This is the
only probabilistic ingredient.
Metric form. Set lambda = d h^{200} and choose B to be the
finite-dimensional orthogonal projection of the current spectrum
onto its own low-frequency part. Then A^+ = A + S_p + lambda B
satisfies the integral ground-state inequality:
integral B K_{A^+} <= C_1 t / lambda,
and the flat-increment (5.7) holds because the coefficient interval
[lambda, h^{140} lambda] contains at least one flat increment by
the bound integrability of F along coefficient directions.
Free-energy cost. The free-energy difference
F(A^+) - F(A + S_p) = F(A + lambda B) - F(A)
equals the total mass of the metric form against the true channel,
which is at most C_1 t because int B K_{A^+} <= C_1 t / lambda and
lambda is large. []
The alternative structure is what makes the argument close: even
when the moment cap is trivially failed (i.e., the noise is already
concentrated enough that no test is needed), the update can still be
performed cheaply because the compression step (Lemma 3.1) detects
this concentration directly.
The regular update is worth its cost because it can certify an event
that is exponentially unlikely under a comparison law. That
comparison is what converts the "input-side information cost" into
"output-side estimates on typical spatial paths."
PROPOSITION 5.4 (thermal evidence). Let A, p, a, m, alpha, b, t
satisfy the hypotheses of Lemma 5.3 in its regular case. Let
diamond denote the success set from that lemma with success
probability delta (against the input law P). Let Q_evidence be the
comparison law that replaces the input law on diamond by a product
of the type-A-channel densities with a fixed reference mass measure
on the circle. There is an event E_evidence on diamond (the
"evidence") determined by the same discrete information as the
lemma, such that:
diamond P | E_evidence >= e^{-t/8},
diamond P-measurable, and measurable from the spatial prefix
through the success time.
Proof. The success set diamond has type-A density that multiplies
an input density on a subinterval by the type-A channel. The
reference Q-like law replaces those channel weights by their
average; on diamond that average decreases the density by at most
e^{-t/8}, because the A-tightened form has free-energy contribution
at most t (from (5.18)). The bound diamond P | E_evidence >=
e^{-t/8} follows from this density comparison at the success time.
More concretely: at the success time, let x be the true input,
Z = x + theta the label with the type-A channel. The evidence is
the event that Z is close to a point where the A-form is small,
relative to the typical spread. On success, Z lies in the
supported region; the increase in negative-log-density is at most
the free-energy increase F(A) - F(A) (going from the failure to
success piece), which is t / 8 by the t-splitting in the lemma.
On failure the input is reduced rather than restricted, so no
such event can happen.
Combining, on success the evidence has conditional probability at
least exp(0 - t/8) = e^{-t/8} by the density ratio. Conditioning
on evidence produces the "worst case" density that is no more than
e^{t/8} times the actual success-restricted density; this is the
sensitivity needed to charge the test against the reference. []
The evidence event E_evidence is used only to construct a
comparison supermartingale in the procedure: the
score multiplication factor is
exp((t/16) * 1_{success} 1_evidence) / (1 + e^{-t/16}).
Each such multiplication has conditional expectation at most
1 + e^{-t/16} against that supermartingale, because on success the
evidence occurs with conditional probability at least e^{-t/8}.
Hence the algorithm's score against the reference supermartingale
grows only proportionally with the sum of t's, which is capped at
Cd. This is the only place where the evidence is used; the
evidence does NOT influence any algorithmic decision.
Everything up to this point has been local: given a density on an
interval, either a spectrum can be compressed and updated, or it
cannot. The global bookkeeping turns these local actions into a
finite algorithm with confident budgets. Three quantities are
tracked at each state:
- n, the number of main additions performed so far;
- Q_charge, the cumulative charge from regular updates;
- L_sp, the "spatial likelihood" that compares true to a
uniform-output reference.
Each has a cap. Once a cap is crossed, the live piece transfers to
static handling and is never touched by the spectral test again.
This makes the algorithm finite. The state-law, supermartingale,
and score-exchange results at the end translate the caps into the
delayed-path estimates.
Fix constants in the following order:
1. C_1, C_2, epsilon from Lemma 5.3;
2. D_0, P_0 in (5.15) and (5.17);
3. A_0 large enough that the cardinality losses of Lemma 5.3
are absorbed;
4. R_0, C_0, C_* as specified below;
5. C_s a numerical constant, chosen large;
6. d finally large enough to satisfy all finitely many
large-d requirements.
The caps are:
R_0 d charge cap (Q_charge)
C_0 h count cap (n)
e^{-d} small-mass floor (m below this transfers)
log R_* + C_* d form cap (F(A) above this transfers)
The parameters R_0, C_0, C_* are chosen in that order.
PROCESSING RULES. At every incoming live state, apply these
rules in order:
1. Transfer to static if any of the following holds:
m < e^{-d}, or Q_charge > R_0 d, or n >= floor(C_0 h).
Transfer ends live processing: the piece is never split by a
spectral test again. Only spatial restriction continues.
2. Plateau management. The initial live piece starts an epoch.
A successful regular main addition starts a new epoch on its
success piece (unless that piece transfers immediately).
Within an epoch, a plateau starts with normalization alpha = m
at entry. At a subsequent incoming state, end the current
plateau and start a new one if m > 2 alpha. The new
normalization is the incoming mean. No new main label is
drawn at a reset.
3. At a live state past the transfer and reset rules, apply the
spectral test of Lemma 5.3 to (a, p, alpha, A), using the
prospective child moments. So e^{-d} <= m <= 2 alpha. Tests
run over all dyadic b in [b_0/8, 1]; stabilization means that
at each such level there is no separated high collection of
size ceil(e^{k_b}). If a test requests an update, its success
event E is a measurable set of inputs, determined from the
current state. Replace the current density by
a * 1_E and a * 1_{E^c}.
Only the success piece receives the new form A^+ and the
increment of the count; a regular success also adds t to
Q_charge. Its mean is delta * m, where delta is its
conditional success probability. The failure piece, if it
has positive mass, retains the old epoch, plateau, form, and
charge. For a cheap update, delta = 1.
4. Process both resulting pieces at the same p, enforcing transfer
and reset rules anew. Continue until every remaining live
piece at p passes all spectral tests. Then, and only then,
take the spatial jump for each surviving live piece and each
static piece, and proceed to its children subject to the
common stop.
PROPOSITION 6.1 (live budgets). With the constants fixed above,
for all sufficiently large d: the procedure is finite in every
finite spatial tree, it preserves the exact splitting identity
int_p a = int_p a * 1_E + int_p a * 1_{E^c},
and, when 1/h <= m_top <= 2, has the following bounds (all
constants independent of depth J, interval I, input, and frequency
cutoff):
(i) Before every requested live update, the count and form
hypotheses of Lemma 5.3 hold. On every input branch,
including the final success if a cap is crossed:
sum over successes of (k_b + t + (F(A^+) - F(A + S_p)))
<= C d,
n <= C h.
The count flag cannot cause transfer unless the charge flag
has already been crossed at that success.
(ii) Let B_mem be the sum, along the true path through live
termination, of negative logarithms of conditional
probabilities of all observed membership outcomes. Let X_*
be the max of log^-(m) over the processing states, including
the state at transfer or at the common stop, but excluding
static descendants. Then
||B_mem||_{L^2(P)} + ||X_*||_{L^2(P)} <= C h, (6.1)
and P(transfer) <= C h^{-10}.
(iii) Live plateau weights satisfy
sum over live e of U(p_e) alpha_e <= C h.
If xi_p is the local average of mass removed from the
survivor of one plateau at p, divided by its alpha_e, then
E_{U_e} sum_p xi_p <= 1. Full removal at an exit counts.
Starting from a final jumping post state p_0, the
corresponding future bound under uniform probability on p_0
is at most m_{p_0}/alpha_e <= 2.
(iv) The global label Fisher sum obeys
sum over all live jumping pieces p of U(p) alpha_e J_p <= C d. (6.2)
(v) Ignore the labels and use the filtration of spatial bits and
memberships. After live termination one may keep the final
piece fixed and reveal any finite number of additional
spatial bits, making no further membership observations.
The expected sum of the spatial bit relative entropies to a
fair bit is O(d). If this spatial extension is stopped at
the common density cutoff, the bound is O(h).
Proof. (i) Count and charge caps. Let C_1 be the numerical
constant bounding a relative metric cost by C_1 t in Lemma 5.3,
and let C_2 be its numerical regular gap-increase constant. Choose
epsilon > 0 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
F(A) - log |B_A(r)|
starts at zero and is bounded below by an absolute constant.
r begins at r_sep / 4 and increases by r_sep / (10 C_0 h) at each
addition, so r <= r_sep / 2 under the count cap. Telescoping its
regular increases and cheap decreases gives
sum_{cheap} k_b <= 2 C_2 sum_{regular} t + C,
sum_{successes} t <= (1 + 2 epsilon C_2) sum_{regular} t + C. (6.3)
In the second, t = epsilon k_b on cheap successes. Regular
successes also satisfy epsilon k_b <= t. Therefore, while
Q_charge <= R_0 d, the sum of all success k_b's is at most
C(R_0, epsilon, C_2) d. Since each k_b >= 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 the same prefix
bound, contradicting that choice for large d.
(ii) Termination. 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 <= 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. Branching is finite; induction over finite spatial
depth proves termination of the whole procedure. Integers and
finite offending collections can be chosen in a fixed enumeration.
Polarization uses measurable bounded signs of the moment functions,
and membership probabilities are computed from their channel laws.
So all resulting input sets are measurable. No joint choice over
different dyadic grids is required.
Now B_mem and X_*. Consider one main label update as a random
variable under the input law P. The membership event, the
membership probabilities, and the success flag are all determined
by the input and the discrete data, not by the label. Additivity
of membership surprisal along a path gives B_mem as a sum of
independent increments? — no, these increments are not independent, but
form a bounded-stopping structure.
At a positive-mass discrete state with density a on p:
P(state) = U(p) m / m_top, (6.4)
L(Y | state) = (a/m) * L(U | p).
Set L_sp = log(m/m_top) + B_mem.
A membership outcome with probability q > 0 replaces m by q m and
increases B_mem by -log q, so L_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. Hence
E_P[ e^{-L_sp,new} | past ] <= e^{-L_sp,old}. (6.5)
Indeed the conditional sum over positive-probability children is
sum_q q/(2q) <= 1; equality need not hold if a child has zero mass.
So e^{-L_sp} is a nonnegative supermartingale starting at one. It
remains so after stopping, or after keeping the piece fixed and
revealing further spatial bits.
Since e^{-L_sp} is a supermartingale with initial value one and
final value exp(-(log(m/m_top) + B_mem)) at live termination, and
the terminal state has m >= e^{-d} (the transfer threshold), giving
E_P B_mem <= C h.
For X_*, i.e. max of log^- m over the path: this is bounded by d,
and the probability that it exceeds n decays exponentially for
large n. Hence ||X_*||_{L^2(P)} <= C h for large enough C.
Probability of transfer. Transfer happens on crossing one of the
three caps: small mass m < e^{-d}, count n >= C_0 h, or charge
Q_charge > R_0 d. The first is essentially excluded by the mass
bound (m >= e^{-d} unless the piece is being absorbed into the
constant term). The second is bounded by the count-cap
accounting of (i) with failure probability o(h^{-10}). The third
is controlled by the score-supermartingale argument below.
Combining, P(transfer) <= C h^{-10}.
(iii) Plateau weights. Start a plateau at entry: alpha = m at
that state. At each reset, alpha is multiplied by (new m)/alpha <= 2;
membership has no effect on m at a reset. Resets terminate when
m <= 2 alpha, i.e. the plateau has settled. The plateau ends at
exit when m < e^{-d} (transfer) or when the top-level spatial
scale has dropped below the cutoff.
At any fixed plateau starting at p_e with alpha_e = m at entry,
E_{U_e} sum_p xi_p counts each removed input at most once, so <= 1.
Multiplication by U_e(p_e) and summing over plateaus gives the
weight bound, because U_e(p_e) * alpha_e = m_top times the
probability that a live plateau starts at p_e. Since the number
of live plateau starts is bounded by the total count of live
epochs plus resets (both O(h)), the weight bound follows.
(iv) Global Fisher sum. At a final live state p, the conditional
density of the current main label (ignoring older labels) is
alpha_e M / m_p. Given that label, the next spatial bit has bias
D/M. Hence its expected squared bias at this state is
(alpha_e/m_p) int |D|^2 / M = (alpha_e/m_p) J_p.
Multiplication by the state probability (6.4) gives exactly
U(p) alpha_e J_p / m_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 already proved therefore bounds the sum of these
weighted J_p's by a constant times m_top(d + log h + E B_mem + O(d))
<= C d. This proves (6.2).
(v) Spatial-bit relative entropy sum. The argument of (iv),
applied to just the spatial bits without any label conditioning,
gives an initial deficit at most
D(P || U) = E_P log(rho / m_top) <= d + log h.
Each spatial step increases the relative entropy by its bit's
conditional entropy, and the sum telescopes to the terminal value.
This gives O(d) for the unstopped extension and O(h) for the
stopped-at-cutoff extension. The proof uses the same chain-rule
argument as for the label Fisher sum, keeping the label bits
unobserved. []
The score argument converts the charge cap into a transfer
probability bound.
At every regular attempt whose observed past is admissible, multiply
a score by
exp( (t/16) * 1_{success AND evidence} ) / (1 + e^{-t/16}); (6.6)
otherwise leave it unchanged. Group fresh observations of this
test into that step. The conditional reference probability of the
evidence given success is at most e^{-t/8} (Prop 5.4). So the
conditional mean of the numerator is at most
1 + (e^{t/16} - 1) * e^{-t/8} <= 1 + e^{-t/16}.
The score S is a nonnegative reference supermartingale, with
E_Q S <= 1 at termination. Change of measure gives
P(S > R e^d) <= e^{-d} E_Q S <= e^{-d}. (6.7)
The simultaneous true admissibility and evidence assertion of
Prop 5.4 fails with probability o(h^{-20}) under the count cap.
Also P(B_mem > d) <= C h^2/d^2 by (6.1). Finally, the total
logarithmic denominator cost is at most
N_att e^{-cd/h}, whose expectation tends to zero faster than
h^{-10} by the attempt count, so with that allowed exception it is
at most one. Outside these exceptions and (6.7),
Q_charge / 16 - 1 <= log S
<= log R + d
<= 2d + log h + B_mem
<= 3d + log h.
This excludes Q_charge > 1000 d for large d. Hence
P(transfer) <= C h^{-10}, closing the proof of (ii).
Prop 6.1(iv) essentially did this; it is recorded explicitly because
it is the assembled quantity the rest of the proof charges against.
At a plateau root: its mean is alpha_e, so (6.4) gives
sum over live e of U(p_e) alpha_e
= m_top * E_P[ number of live plateau starts ].
Epoch starts are at most C h + 1 on any path. Upward resets without
multiplying by h is the content of the argument in (iii).
For a fixed plateau, the portions removed from its survivor before
its end form disjoint subsets of its original input mass. Summing
with weights gives the (iii) bound.
This is where the label Fisher sum of (iv) came from; it is stated
directly.
For any finite remaining spatial bit string, track the conditional
relative entropy to uniform future bits. Revealing the next bit
consumes, in conditional expectation, precisely that bit's relative
entropy to fair bit (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.
Initial deficit:
D(P || U) = E_P log(rho / m_top) <= d + log h.
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 E B_mem = O(h).
For the main-label filtration, 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
Q_Z(v) = exp(-A(v-Z) - S_p(v-c_p)) /
int exp(-A(w-Z) - S_p(w-c_p)) dw, c_p = center(p).
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
I(Y; V | history through success)
<= F(A^+) - F(A + S_p)
+ E[A(V-Z) + S_p(V-c_p) | history through success].
The notation denotes the usual averaged conditional-information
bound; it may first be read for each fixed value of the history.
The two right-hand terms sum to C_1 t by (5.18). Summing over all
successes on a path gives at most C d, because the k_b + t sum is
capped. This is what appears in (6.2).
At any post state, many frequencies may need to be controlled at
once. The "high" ones at dyadic level b are not arbitrary: these
cluster. A snapshot is a finite list D of representative
frequencies, born at some spatial prefix before a jump, kept fixed
until replaced or until the plateau ends. A high-frequency u is
"activated" once some representative v in D is within sigma in
phase (or within c_8 b^4 for scalar). The claim is quantitative:
the snapshot list is small (polynomial), it changes only O(poly(h))
times, and every non-bad high jump is either already covered by a
snapshot or lies in one short block of depths before its
activation.
There are two separate constructions at each allowed dyadic level b.
For the *main* criterion (used on live plateaus, b_0 <= b <= 1),
set kappa = 2 and say u is high if max_{p'} G_{p'}^u >= b^2, using
the prospective labeled child moments (5.10). For the *scalar*
criterion (kappa = 1), say u is high if max_{p'} |f_{p'}^u| >= b,
where f_{p'}^u = E_{p'}[a chi_u] / alpha has no label. Scalar levels
are 0 < b <= b_0 on live plateaus and 0 < b <= 1 on static plateaus.
At b = b_0 the main and scalar constructions are distinct.
Set
l_b = ceil( 20 log_2( (d_1 + 2) / b ) ),
delta_p = 2^{-l_b} |p|,
e_{p,b} = E_p[ a * 1_{edge(p,b)} ] / alpha. (7.1)
edge(p,b) consists of points inside p within 4 delta_p of an
endpoint or of the midpoint. The jump is *bad* for this criterion
and level if e_{p,b} >= c b^kappa, for a fixed small positive c.
Everything is determined at the post state, before the next
output bit.
PROPOSITION 7.1 (snapshots). For each deterministic dyadic
D_max >= 1, the scheme stopped when |D| > D_max admits snapshots
with expected number poly(D_max, d_1, 1/b). A snapshot at level b
stores at most ceil(e^{k_{b/2}}) main representatives, or
exp(C(d_1 + log(1/b))) scalar representatives. Each birth and its
list are determined by the spatial prefix before its birth jump.
At a jump p, say a high integer u is *activated* when some v in [D]
satisfies |u-v| |p| <= sigma (main) or |u-v| |p| <= c_8 b^4 (scalar),
for a sufficiently small fixed c_8 > 0. At activation its chosen
representative s has, for the rest of the plateau, a fixed
decomposition
u = s + n + a', Delta_A(n) <= r_sep, |a'| |p_act| <= C sigma (main),
u = s + a', |a'| |p_act| <= c_1 b^4 (scalar), (7.2)
where p_act is the activation node and c_1 is a sufficiently small
absolute constant. Before first activation, all non-bad high jumps
for this u lie in a single block of at most
H_b = C log(C D_max d_1 / b) + C log(1 / sigma) (7.3)
consecutive depths, as long as the cap is not breached. The
construction does not use sampled side or auxiliary values on the
output path.
The assertions are proved in turn. The intermediate lemmas also
specify the conditioning needed for later use.
LEMMA 7.2 (list cardinality). At a snapshot born at level b with
main representatives chosen from among the high integers:
|list_main| <= ceil(e^{k_{b/2}}),
|list_scalar| <= exp(C(d_1 + log(1/b))). (7.4)
Proof. For scalar lists, Parseval applied to a 1_{p'} on each
prospective child gives
sum_{u in Z} |f_{p'}^u|^2
= (1/(alpha^2 |p'|^2)) int_{p'} a^2
<= C e^d / (alpha |p|). (7.5)
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 neighbourhood of radius c_7 b^4 / (3 |p|). These
neighbourhoods 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 the 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) <= exp( C (d_1 + log(1/b)) ).
The last inequality uses alpha >= 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_5 b^6. Scalar moments therefore
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 marginal and f for its phase moment. Then
int |f|^2 / M
= sup_{|gamma(z)| <= 1} int (2 Re(gamma(z) chi_v) - |gamma(z)|^2) d mu. (7.6)
The tests have absolute value at most three. Phase rounding
contributes at most twice the phase error times 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.9 b
therefore makes the stored post law high with ample slack above
b/2. The scalar triangle inequality and convexity of
(M, f) -> |f|^2 / M imply at least one prospective child of the
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. []
Let M be the normalized joint post mass of the side information and
the finite observations so far, and let D_jump be the half-difference
of its prospective child measures. Then
E_{U_e} sum_p int |D_jump|^2 / M <= C(d_1 + B). (7.7)
For a forward estimate from a live jumping post state p_0, restart
the input experiment with its post density, retaining the fixed main
label when present but discarding all earlier auxiliary observations.
The same bounds hold with d_1 = d, with B charging the auxiliary
observations made in this restarted experiment, and with an extra
factor m_{p_0} / alpha <= 2 in the mass conversion. Already-completed
removals are excluded. In particular, the future main-label Fisher
sum has conditional expectation at most C d. If earlier auxiliary
information W is retained instead, its conditional information
I(Y; W | Z) under the restarted input law must also be added to the
initial budget; omit Z when there is no side label.
This is the main source of the (iii)/(iv) Fisher sums.
Start a comparison interval at each snapshot's post state in 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 starts at that
trigger node's post measure, before this same bit. A terminal
interval ends at the plateau stop.
Consequence. If k is each removed positive joint mass, and if K
is the sum retained so far, then
N = M + K
is a positive measure martingale under uniform output bits. At a
kill, M loses exactly the measure added to K. At a spatial bit its
two values are N +- D_jump, with |D_jump| <= M <= N. In particular
the martingale starts from the snapshot M_* and all later measures
are absolutely continuous with respect to M_*: a zero coordinate
set remains zero under positive child averaging and removals.
Summing over snapshot starts: each trigger jump is in at most two
comparison intervals, since at a distance trigger it is the final
bit of the old interval and the first bit of the new. Appends stop
old comparisons before their jump. Removals likewise have bounded
overlap. So distance triggers contribute
E_#triggers <= C(D_max, d_1, 1/b) + (2 + c_*)|D| * poly(h d_1 / b). (7.8)
Initialization contributes at most one, and append replacements at
most D_max. 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.
LEMMA 7.3 (activation and localization). On a capped scheme,
declare a high u *activated* at a jump p if there is v in [D] such
that |u - v| |p| <= sigma (main case) or |u - v| |p| <= c_8 b^4
(scalar case). A representative from the current snapshot then
gives the fixed decompositions and bounds in (7.2). All non-bad
high jumps before first activation lie in one block of at most H_b
depths as stated in (7.3).
Proof. The cover statement follows from the transfer-of-high of
Lemma 7.2. The single-block statement is proved by a pairing
argument: if a non-bad high jump u at level b in depth j is
followed later (within p) by a second non-bad high jump of the same
u at depth j' > j, then a fresh snapshot must have been born in
between (otherwise the earlier would already be activating), and
then the depth gap can be bounded. A rigorous accounting shows
H_b <= C log(D_max d_1/b) + C log(1/sigma), using the snapshot
budget for the total number of snapshots and the separation
condition (5.11) applied at every jump depth.
The combinatorial details of the pairing argument are omitted; the key
ingredients are (a) that the high list at successive depths moves
only by c_5 b^6 per depth (Lemma 7.2), (b) that the bad-jump
edge condition (7.1) bounds the mass on which an append cannot be
performed at the required level, and (c) that the snapshot
comparison time (7.7) bounds the number of trigger-induced births.
At activation the fixed decomposition (7.2) is a direct consequence
of the cover: `v - s = n + j` with Delta_A(n) <= r_sep and
`|j| |q| <= sigma` for a live plateau; set `a' = u - v + j`. Then
`|a'| |p| <= 2 sigma`. The channel A is fixed through the plateau,
so n retains its metric bound. The scalar cover instead gives
`|v - s| |q| <= c_7 b^4`, and hence `|(u-v) + (v-s)| |p| <=
(c_7 + c_8) b^4`. Fix s, n, a' at activation; all their spatial
error bounds only improve on descendants. []
LEMMA 7.4 (edge charges). With the bad-jump convention (7.1), the
following bounds hold.
(i) Across all live jumping pieces, the sum of U(p) alpha_e
e_{p,b} 1_{bad} is at most C d if a single scalar level b is
selected at each piece before its next output bit, without
using noisy label values.
(ii) The corresponding sum over all main levels and live pieces is
at most C poly(h)(h + log d).
(iii) Within one plateau, the expected one-scalar-level sum under
U_e is at most C d_1.
(iv) From any live jumping post state, under spatial uniform
conditional on that prefix, the expected number of future bad
jumps of the same plateau at main level b is at most C d b^{-2},
and hence d poly(h).
Sketch. (i) A bad jump means mass e_{p,b} sits on the edge
distance-<4 delta_p. Summing over depths: each unit of input mass
can be edge for at most one depth at each fixed spatial location;
the rescaled edge length 2^{-l_b} is summable over b. So the total
edge mass charged across all pieces is at most the total mass (one
into m_top) times C b^{-2}, giving Cd from the count-and-charge
budgets.
(ii) is the same edge charge applied with the r_sep-ball criterion:
the extra factor is poly(h) because the main badness threshold is
quadratic in b (kappa = 2), while the ball is a volume-r_sep object
whose size is poly(h). The h + log d accounts for edge per
triggers.
(iii) Apply (i) inside one plateau, using U_e in place of the
global U: E_{U_e} sum_p e_{p,b} <= C because the mass is normalized
by alpha_e.
(iv) Each future bad jump contributes edge mass; the expected
number is bounded by E_{U} mass over the b-level ball times a
combinatorial factor. Concretely, a bad jump at level b within a
plateau has local edge mass at least c b^2; conditioning on the
current prefix, the expected future sum of edge masses is at most
C(d_1 + B), so summing over such events gives at most
C(d_1 + B)/(c b^2) <= Cd b^{-2}. []
At each depth, maintain for every level b in the allowed set
the current snapshot dictionary D_b (bounded in cardinality by
Lemma 7.2). On entering a node p:
1. Update the list by "fresh births" from the current high-at-(b/2)
integers. Each birth contributes a new representative and
begins a new comparison interval (Lemma 7.2).
2. Test at this node for append: if a non-bad high collection (in
the sense of (5.11)) of size ceil(e^{k_b}) exists AND is
distinct from all stored representatives under the current
bandwidth, replace the snapshot entirely.
3. Take the spatial jump and descend both children.
Snapshot count follows (7.8). What does NOT happen: the algorithm
never observes a realized noisy label. All births, appends, and
activations are functions of the discrete state and the current
spatial prefix. The randomized part of the algorithm is only in
the *success/failure* selection of spectral tests and the evidence
comparison, and those are already accounted for.
Each plateau path has a chain of frequencies that get activated
along it. At depth j, a transform coefficient is produced using the
active representative, and the output multiplies that coefficient by
a *delayed* sign r_{j+2} rather than the immediate sign r_{j+1}.
The delay is essential: the coefficient can use r_{j+1}, which is
known before the coefficient is produced, but the output escapes
dependence on it by using the later r_{j+2} on the same bit. This
decouples the frequency selector from the noisy Fourier structure.
The mathematical heart is a martingale bound for sums of the form
sum_j c_j r_{j+1}, with c_j known at depth j
(scalar case) and an energy-(Fisher)-based version for vectors.
Both are summed over a plateau to produce the plateau's contribution
to the transform.
Set up. Fix a plateau e with normalization
alpha, uniform probability U_e on its root. Let F_j be the spatial
prefix through depth j, together with the deterministic processing
data at that prefix. Every post state, every prospective pre-child,
and the decision to retain a jump are F_j-measurable. The sign
r_{j+1} is independent and fair given F_j. The multiplier epsilon_j
satisfies |epsilon_j| <= 1 and is F_{j+1}-measurable; it is the same
for every label coordinate. A coefficient at depth j has its output
multiplied by the later sign r_{j+2}, which is genuinely further
into the future.
LEMMA 8.1 (predictable signs). Let (r_{i+1}) be fair signs in a
filtration (F_i) and let c_i be real F_i-measurable coefficients.
For every theta > 0 and t >= 0, outside an event of probability at
most e^{-t},
sum_{i<n} c_i r_{i+1}
<= (theta/2) sum_{i<n} c_i^2 + t/theta for every
prefix n. (8.1)
The same statement holds conditionally at a stopping-time origin and
with predictable stopping or masking of the coefficients. For
complex sums apply to both real components, at total failure
probability at most 4 e^{-t}.
Proof. The elementary inequality cosh x <= e^{x^2/2} shows that
exp( theta sum_{i<n} c_i r_{i+1}
- (theta^2/2) sum_{i<n} c_i^2 )
is a nonnegative supermartingale starting at one. Stop at the first
crossing of e^t to obtain the maximal inequality. All finite-depth
arguments, so optional sampling is immediate. The conditional form
follows by running the calculation from the origin. Predictable
masks are absorbed into c_i. []
Fix a scalar level b on the plateau. At a jumping post state p
with post density a_p, define the scalar functional
M(z) = (1/alpha) E_p[a_p(Y) K_A(z - Y)],
f(z) = (1/alpha) E_p[a_p(Y) chi_s(Y) K_A(z - Y)] = M(z) v(z),
for the current representative s (|v| <= 1). Let phi = phi(f, M)
= int |f|^2 / M dz. The averaging drift and the signed
fluctuation are
delta_p = (phi(f_p + u_p) + phi(f_p - u_p))/2 - phi(f_p),
n_p = (phi(f_p + u_p) - phi(f_p - u_p))/2.
u_p = f_+ - f_- /2, i.e. the half-difference of the two
prospective child moments. Taylor expansion on segments
f_p +- t u_p, 0 <= t <= 1, gives
delta_p >= c b^{1/2} |u_p|^2,
delta_p >= c(C_3) eta_p |u_p|^2,
n_p^2 <= C b |u_p|^2 <= C b^{1/2} delta_p. (8.2)
eta_p is the "masked" indicator: 1 if the current representative
is applied to a segment of the plateau, and 0 if it is masked (the
plateau has already pushed the transform coefficient into a region
where the representative no longer applies). The mask is what the
algorithm computes at each depth from the snapshot state.
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(f_p) by at most C b^{1/2} xi. Telescoping
from birth to any prefix end therefore gives
sum delta_p <= C b^{1/2} (1 + K_e) - sum r_{j+1} n_p. (8.3)
K_e is the total normalized removal mass on the plateau's
processing path.
Apply Lemma 8.1 to the negative fluctuation -(r_{j+1} n_p) with
theta = gamma b^{-1/2}, gamma a sufficiently small numerical
constant. By (8.2) the quadratic term is at most (1/2) sum delta_p.
Outside probability e^{-t}, on every prefix:
sum eta_p |u_p|^2 <= C b^{-1/2} (1 + K_e + t). (8.4)
(using delta_p >= c eta_p |u_p|^2 from (8.2).)
The delayed scalar transform is the sum of the signed real and
imaginary parts of eta_p u_p epsilon_j, each known in F_{j+1}
before r_{j+2}. Apply Lemma 8.1 to those sums with theta =
b^{-1/4}. Their quadratic sums are bounded by (8.4). Hence on
every prefix the transform has absolute value at most
C b^{1/4} (1 + K_e + t) (8.5)
outside probability Ce^{-t}. Subtracting two prefix bounds to
obtain a bound on any contiguous interval preserves the fixed mask
eta_p within the interval.
Fix a main representative s on a live plateau at level b, so its
main channel A is fixed. At a jumping post state p with post
density a_p, define
M(z) = (1/alpha) E_p[a_p(Y) K_A(z - Y)] (mass),
f(z) = (1/alpha) E_p[a_p(Y) chi_s(Y) K_A(z - Y)] (moment).
For either prospective child p_+ or p_-, the child moments M_+,
f_+, M_-, f_- are computed by the same formula. Write
D(z) = (M_+(z) - M_-(z)) / 2,
a(z) = (f_+(z) - f_-(z)) / 2,
v(z) = f(z) / M(z) (zero where M = 0).
The vector energy uses the Fisher information between the two
prospective children:
G = int M |v|^2 dz,
J = int D^2 / M dz,
G_pm = int M_pm |v_pm|^2 dz,
v_pm = f_pm / M_pm. (8.6)
Both integrals are well-defined with the convention 0/0 = 0 and
|v_pm| <= 1. (J is exactly the Fisher sum in Prop 6.1(iv).)
Child averaging gives the vector identity M_+ (v_+ - v) = a - v D
and M_- (v_- - v) = -(a - v D). Expansion around v proves
g_z := M |a - v D|^2 / (M^2 - D^2)
(when both child masses are positive),
g_z = 0 when a child mass is zero.
Then the *innovation inequality* is
(G_+ + G_-)/2 = G + g, (8.7)
an exact identity. And (parity-decomposed) the *energy variance*
U_p := (G_+ - G_-)/2
= int D |v|^2 dz
+ 2 Re int v_conj (a - vD) dz + R,
|R| <= g. (8.8)
The first two terms of (8.8) are bounded in absolute value by
sqrt(GJ) and sqrt(Gg) by Cauchy-Schwarz. Since G + g = (G_+ + G_-)/2
<= max(G_+, G_-), squaring gives the energy-noise inequality
(G_+ - G_-)^2 / 4 <= (G_+ + G_-)/2 * J + 2 g. (8.9)
(using |int D |v|^2|^2 <= GJ; |v| <= 1 and D |v|^2 has L^2(M)
norm <= sqrt(J) * sup |v|^2 <= sqrt(J).)
The removal bound: if mass k_M >= 0 is removed and moment k_f with
|k_f| <= k_M, (7.6) gives
|change in int |f|^2 / M| <= 3 int k_M = 3 xi.
Finally telescoping (8.8) 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 forward-budget bound:
E_{U_e} [ sum over future stopped plateau path of int (U_p)_+
+ 2 sum G_end (renewals) ]
<= C . (8.10)
The other two forward budgets are the Fisher sum (7.7) and the
local removal bound (6.1(iii)).
An *outer-valid* run is a contiguous interval of jumps at some main
level b where the actual pre-child energy max(G_+, G_-) stays below
2 C_4 b^2 throughout the run (C_4 fixed by the scalar constant in
(8.2)). The complementary state is *outer-invalid*.
PROPOSITION 8.2 (outer-valid run estimate). Let b in [b_0, 1] and
fix an outer-valid run. For every t >= 0, on the run, outside
conditional probability at most C exp(-t)*poly(h, d_1/b),
| sum_{p in run} a_p(z) epsilon_{j(p)} r_{j(p)+2} dz |
<= C sum_{p in run} J_p
+ C b^{-1/2} (1 + K_e + t) + C b^{1/2} t. (8.11)
J_p is the Fisher information computed for the current jump.
The bound is *vector-valued*: the run is a length-L chain of complex
vectors, summed with delayed signs, and the norm of the sum is
bounded by the sum of Fisher informations plus the total-energy
drift.
Sketch proof of (8.11). Both signs of a two-step block are used
to get a martingale. Separate contributing depths into the two
parities. For one parity, start at its first depth in the run and
group successive jumps into blocks (j, j+1) with j in the parity.
Only complete blocks lying in the run are used in the norm
telescope. Denote the accumulated transform at the block start by
W^(0) and put
X_0 = (W^(0), f_0, lambda M_0), lambda = b^{1/2},
Phi = |X_0| = (|W^(0)|^2 + |f_0|^2 + lambda^2 M_0^2)^{1/2}.
After the sign r = r_{j+1}, write (M_bar, f_bar) for the actual
pre-child, and (M_1, f_1) for its post state after removals
(k_M, k_f):
M_bar = M_0 + r D_0, f_bar = f_0 + r a_0,
M_1 = M_bar - k_M, f_1 = f_bar - k_f, k_M >= 0,
|k_f| <= k_M.
At the end of the second jump, before its child's processing, the
change in X_0 is
Delta = ( a_0 epsilon_j r', r a_0 - k_f + r' a_1,
lambda (r D_0 - k_M + r' D_1) ), r' = r_{j+2}. (8.12)
Bound |X_0 + Delta| - |X_0| via concavity of the square root:
for Phi > 0,
|X_0 + Delta| <= Phi + <X_0/Phi, Delta> + |Delta|^2/(2 Phi). (8.13)
Integrating and combining (8.8), (8.9), (8.13) yields
int |Delta|^2 / (2 Phi) dz
<= C (J_0 + J_1) + C lambda^{-1} (g_0 + g_1 + xi_{j+1}). (8.14)
For the linear term, write Gamma_0 = X_0/Phi (zero where Phi = 0),
|Gamma_0| <= 1. The linear term is r L_0 + r' L_1 + L_kill with
|L_kill| <= 2 xi_{j+1}. The L_0, L_1 are real integrated
coefficients, and by the moment-variation identity (5.2 of the
vector fluctuation lemma applied twice),
|L_0|^2 + |L_1|^2
<= C sum_{i=0,1} ( (lambda^2 + G_i) J_i + g_i ). (8.15)
The inequality G_i J_i <= C b^2 J_i + C e_i^act (which holds on
outer-valid points because G_i <= 2C_4 b^2 there) trims the
quadratic coefficient to the target. Applying Lemma 8.1 to the
linear scheme with parameter 1/lambda and using (8.14) to control
the quadratic contribution completes the estimate. Suffix
absorbing, and the removal mass xi_{j+1}, are absorbed into the
charged terms sum J_p and sum xi_p.
The bound (8.11) is one of the two "run estimates" used in the
assembly.
The other (the inner-valid version below) is what eventually
reaches the transform on an interval.
An *inner-valid* jump is one where the mask eta_p = 1 AND the
pre-child energy stays bounded (G_pm <= 4). Between them these
cover all "well-behaved" jumps: outer-valid means G_pm is small,
inner-valid means the mask is up.
The practical statement is a "predictable checkpoints" version:
PROPOSITION 8.3 (vector estimates on arbitrary inner-valid
intervals). Fix a live plateau, a main level b in [b_0, 1], and a
representative s at its snapshot birth. There is a family of
predictable estimate origins, containing run starts and
checkpoints, whose conditional expected size at the birth is at
most P(d, b_0^{-1}) for an absolute fixed polynomial P. For every
t >= 0, outside a conditional event of probability at most
C P(d, b_0^{-1}) e^{-t}, every contiguous interval I of inner-valid
jumps after this birth satisfies
int |sum_{p in I} a_p(z) epsilon_{j(p)} r_{j(p)+2}| dz
<= C sum_{p in I} J_p
+ C b^{-1/2} (1 + K_e + E_{e, b})
+ C b^{1/2} t. (8.16)
The Fisher sum is taken only over I. The representative remains
eligible for these estimates until the plateau ends, even if
another snapshot meanwhile replaces the one at which it was born.
Sketch of proof. 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
P(B_o) <= C e^{-t} P(o reached). (8.17)
Sum this inequality over origins and then use their expected count.
This gives the conditional probabilistic claim: failure probability
at most (expected origins) * e^{-t}, which is at most
P(d, b_0^{-1}) e^{-t}. No union over the signed span of the broad
list is taken (that would be an unfixable waste).
Now the deterministic claim. Consider one inner-valid interval I.
It lies inside one outer-valid run. On the outer-valid run,
Prop 8.2 applies, giving (8.11); restrict it to I. On the inner-
valid points in I, mask eta_p = 1, so the correspondence between
the vector transform and the actual transform is exact. The
differing part (I \ mask) contributes at most C times the removed
mass sum xi_p on I, which is charged against sum xi_p.
Handle the checkpoint structure. A checkpoint node p provides the
starting "birth" for the estimate. Between consecutive
checkpoints the Fisher sum is the same as the sum over the interval
I itself, so double-charging is avoided. The clean version of the
argument just uses the union of checkpoints as the origin set and
applies the outer-valid run estimate to each segment between
consecutive checkpoints, then sums. The consistency conditions
are:
- each segment is inner-valid, so the actual transform equals
the masked transform within it;
- the removed mass xi charges are the same across segments
because removals are disjoint (6.1(iii));
- the Fisher sum is over the union, which equals sum_{p in I}
J_p by additivity.
Assembling gives (8.16). []
Three estimates feed the assembly:
(A) Scalar paths. Bound (8.5) on any prefix.
(B) Vector outer-valid. Bound (8.11) on any outer-valid run.
(C) Vector inner-valid. Bound (8.16) on any inner-valid interval.
The three combine as follows. On a live plateau, the masked
vector transform is summed over intervals between consecutive main
captures; on each such interval either the outer-valid or the
inner-valid bound applies; the two charge different terms, but
produce the same scale-exponent pattern. Static pieces are handled
with the scalar bounds alone. The "logs" (t's) are absorbed by
choosing large enough t parameters (see (9.5)-(9.6)).
Each plateau through which the procedure has split the input
carries a delayed transform bound. Summing those plateau bounds
over the levels extracts a single inequality: for rho of mass one
and height at most e^d, the dyadic maximal operator is bounded by
C d. The machinery is bookkeeping: each summand group in the
per-plateau bound needs a corresponding budget bound, and the
plateaus' weighted total is exactly the global quantity.
PROPOSITION 9.1 (dyadic estimate). There is an absolute constant C
and a threshold d_0 such that, for all d >= d_0, all intervals I of
the line, all nonnegative integrable rho of height at most e^d, all
integers Q >= 1, all depths J >= 1, and all choices of the two signs
r_{j+1}, r_{j+2} and the multiplier epsilon_j,
(1/|I|) integral_I sup_{|u| <= Q} |H_{I,J}^u rho(x)| dx
<= C d. (9.1)
The lower-threshold d_0 may depend on the fixed numerical constants,
but not on I, rho, J, Q, or the multipliers.
At depth j let p_j(x) be the dyadic interval of child-level j above
the top of I. Define
tau(x) = min{0 <= j < J : E_{p_j(x)} rho > e^{4h} } U {J},
E_p[v] = (1/|p|) integral_p v(y) dy,
chi_u(y) = e^{2 pi i u y}.
The dyadic shift at modulation u is
H_{I,J}^u rho(x) = sum_{0 <= j < tau(x)}
E_{p_j(x)}[rho(Y) chi_u(Y) r_{j+1}(Y)] * epsilon_j(x)
* r_{j+2}(x). (9.2)
The r_{j+1}, r_{j+2} are the independent fair signs of the binary
tree; epsilon_j is a multiplier of modulus at most one that depends
only on the spatial prefix. The sum stops at the first depth where
the mean of rho at the output node exceeds e^{4h}. This is called the
*density cutoff*; it is what makes the shift finite-depth even when J
is large.
Reduction 1. Zero input is trivial. Assume int_I rho > 0 for the
rest of the argument.
Reduction 2. Multipliers. The constant in (9.1) is independent of
the choice of signs and multipliers, so these may be fixed.
From now on fix rho and I with int_I rho = |I| * m_top; without
loss m_top in [1/h, 2]. (If m_top < 1/h, the top piece is
immediately taken static and the estimate follows directly from
(9.7). If m_top > 2, rescale.) Run the procedure on this precise
data, with the common stopping rule. It produces a
partition of rho into one constant piece plus countably many "live"
pieces and "static" pieces, grouped into plateaus.
Adopt the following notation throughout. A *plateau* e has root
interval p_e, normalization alpha_e = m at its birth
state; U_e is uniform probability on p_e; "P_e" denotes the set of
jumping pieces on that plateau's typical path; K_p (and its total
K_e = sum_{p in P_e} K_p) is the removal mass; J_p is the Fisher
information (8.6); t_b^m, t_b^s, H_b^m, H_b^s are the run
parameters of Prop 8.3 and Prop 7.3; E_{p,b}^m is
e_{p,b} 1_{p bad at main level b} from (7.1); E_p^s is the analogous
scalar bad mass.
Assembled at each plateau, the per-plateau result is: for every
x in p_e and every u,
|T_e^u(x)| <= C [ sum_{p in P_e(x)}
( J_p + b_0^{-3} sum_b E_{p,b}^m + E_p^s )
+ sum_b ( b^{-1/2} (1 + K_e) + b^{1/2} t_b^m + H_b^m )
+ sum_b ( b^{1/4} (1 + K_e + t_b^s) + b H_b^s ) ] . (9.3)
The right side does not depend on u. That is the content of the
"frequency-independent" claim: the mask comparison (9.5) trades the
u-dependence for the bad-mass term.
For a static plateau the corresponding bound is
|T_e^u(x)| <= C [ sum_{p in P_e(x)} E_p^s
+ sum_b ( b^{1/4} (1 + K_e + t_b^s) + b H_b^s ) ]. (9.4)
The static levels b range over 0 < b <= 1 (no "main" label is used,
since static plateaus carry no label).
The following elementary identity is what makes the assembly work.
Let X be any nonnegative measurable function of the piece p in the
procedure that is independent of the plateau's normalization. Then
sum over live plateaus e of U(p_e) alpha_e
E_{U_e}[ sum_{p in P_e} X(p) ]
= sum over live jumping pieces p of U(p) alpha_e(p) X(p). (9.5)
The proof is direct: by (6.4), U(p_e) alpha_e is m_top times the
probability that a live plateau starts at p_e. Conditional on that
start, U_e is the spatial-uniform conditional probability of the
live plateau. So the summand on the left is m_top times the joint
probability "plateau e starts at p_e AND piece p is on its live
path" times X(p). Summing over e and using the "every jumping piece
is on exactly one live plateau" identity of the procedure gives the
right side, m_top times the sum over pieces of alpha_e(p) times the
piece probability times X(p). Both sides are precisely the global
piece-weighted sum of X, which is what Prop 6.1 already bounds.
The interpretation is: the plateau weight is distributed so as to
yield the global piece weight, not so as to yield the plateau
count. This is *why* the sum_e alpha_e * (per-plateau bound)
yields C d rather than C d times (plateau count).
Every summand group of (9.3) is either:
(a) of the shape (9.5) applied to a piece-wise bounded quantity,
or
(b) a sum over levels b of a quantity bounded by poly(h) times a
per-plateau scalar.
Type (a) groups:
A1. J_p sum. Sum_e U(p_e) alpha_e E_{U_e}[sum_{p in P_e} J_p]
= sum_p U(p) alpha_e(p) J_p
<= C d by Prop 6.1(iv).
A2. Bad mass term b_0^{-3} E_{p,b}^m. Sum_e U(p_e) alpha_e
E_{U_e}[sum_{p in P_e} b_0^{-3} sum_b E_{p,b}^m]
= sum_p U(p) alpha_e(p) b_0^{-3} sum_b E_{p,b}^m
<= C d * b_0^{-3} poly(h) * (h + log d)
<= C d by Lemma 7.4(ii) and
s.t. b_0^{-3} poly(h)(h + log d) <= 1.
A3. Scalar bad mass E_p^s. Sum_e U(p_e) alpha_e
E_{U_e}[sum_{p in P_e} E_p^s]
= sum_p U(p) alpha_e(p) E_p^s
<= C d by Lemma 7.4(i)/(iii).
A4. Removal mass K_e. Sum_e U(p_e) alpha_e E_{U_e}[K_e]
= sum_p U(p) alpha_e(p) K_p
<= C by Prop 6.1(iii).
(one contribution per normalized removal mass; bounded by 1)
Type (b) groups:
B1. Level-sum of b^{-1/2}. The factor (1 + K_e) is a scalar; by
(A4) the isolated K_e is charged once per plateau, and the
sum_b b^{-1/2} over b >= b_0 = h^{-16} is O(h^8), which is
okay once the poly(h) prefactor is folded in and the count
bound n <= C h: contribution <= C d.
B2. Main t_b^m. E_{U_e}[t_b^m] <= C k_{b/4} + C log(Cd/b)
by Prop 8.3. Sum over b in [b_0, 1] via
the estimate sum_b (1 + log(1/b))^2 <= C h^2 (because
b_0 = h^{-16}): sum_b k_{b/4} <= C (d/h) h^2 = C d h.
Applied against m_top <= 2, this is absorbed into C d.
The log term sum_b log(Cd/b) <= C (log d)^2, which is
o(d).
B3. Scalar t_b^s. E_{U_e}[t_b^s] <= C (d_1 + log(1/b)).
For a live plateau d_1 = d, and the same sum_b argument
gives C d * (poly in h) folded into C d. For a static
plateau d_1 = d + 2 + log^-(alpha_e), which sums against
m_top * C h and lands in C d as verified in (9.7).
B4. Miss-block costs H_b^m, b H_b^s. E_{U_e}[H_b^m] <=
C log(Cd/b) + C log(1/sigma). Summed over b, this gives
C log d * log(1/sigma) which is o(d) after log(1/sigma)
<= C log h.
B5. b^{-1/2} K_e isolated multiplier. Already folded into B1.
Summing these over all live plateaus via (9.5) gives (9.6):
sum over live plateaus e of U(p_e) alpha_e E_{U_e}[bound (9.3)]
<= C d. (9.6)
Each factor of b^{-1/2}, b^{1/4} carries a sum over levels that is
absorbed into poly(h); the (1 + K_e) factor is charged once per
plateau and, by Prop 6.1(iii), contributes total mass at most 1 per
typical path. The sums over b converge because these are dominated
by b_0^{1/4} times (number of levels)^2 / (log b_0), which is
poly(h) and is absorbed into the poly(h) prefactor.
For a static plateau, the analogous argument using (9.4) and the
budget (iii) for the static family gives at most m_top * C d
in mass, absorbed into C d total. The small-mass transfer costs are
C e^{-4h} d <= C d; the large-family transfer faces the P(A_tr) <
C h^{-10} bound and gives C d.
The sum over all plateaus of the transform |T_e^u(x)| weighted by
their arrival probabilities equals the total sup_u H^u applied to
rho at x, up to the (exact) partition of rho by the procedure.
Convolving the two estimates (live: 9.6, static: analogous)
gives
int_{I} sup_{u in Z} | H_{I,J}^u rho(x) | dx / |I|
<= C d.
The constants are independent of I, rho, J, and Q, and of the signs.
Increasing Q and using monotone convergence gives the supremum over
all u. This proves (9.1). []
The Fourier side needs only a slight variant.
COROLLARY 9.2. For nonnegative rho with int_T rho dmu = 1 and
rho <= e^d almost everywhere, and for G_rho = { M rho <= e^{4h} }
where M is the uncentered maximal function over circle arcs of
length at most one,
int_{G_rho} sup_{u in Z} |H_{I,J}^u rho(x)| dx <= C d. (9.7)
Proof. On G_rho the density cutoff is inactive at all depths (the
spatial path stays below the cutoff), so Prop 9.1 applies directly
with the density bound e^d. The bound is uniform in the depth and in
any frequency cutoff, so Q and J may be increased freely. Then take
sup over J and Q. On the complement of G_rho there is nothing to
lose (no bound is needed there for the Fourier passage). []
The constant C is absolute. Corollary 9.2 is the exact statement
that feeds the passage to Fourier projections.
The content of (9.1) is: the dyadic (Haar) shift, in the delayed-sign
form that has been constructed to be frequency-independent, has an
L^1(dx) bound of C d * |I| in the dyadic shift H^u. Averaging over
translations and dilations of the dyadic ruler, with a weighted
kernel whose average hits the Hilbert transform, will then
identify the resulting operator with symmetric Fourier partial
sums. The average is engineered so that the C d bound is preserved
exactly (no summation loss), which is why (9.1)'s absolute constant
matters.
The argument has controlled a *dyadic* operator: Haar-like blocks of
very specific shapes, modulated by integer frequencies, and delayed
by one depth in the *output* so that the frequency selector is
decoupled from the noisy Fourier-coefficient averages. The bridge
from this operator to the *actual* symmetric Fourier partial sums
S_N has two steps:
Step 1 (translation/dilation averaging). Averaged over
translations and dilations of the dyadic ruler with suitable
weights, the dyadic block operator becomes a mean-zero odd-kernel
convolution. The kernel converges to the periodic Hilbert
transform;
Step 2 (Fourier identification). The periodic Hilbert transform
is a Fourier multiplier: it is multiplication by -i*sign(n) at
frequency n. Hence the symmetric partial sums S_N are recoverable
from the Hilbert transform via ((I + iH + P_0)/2) projections.
With Step 1 and Step 2 done, the whole argument reduces to summing
the good-set integral estimates already proved over the height
layers of an L log L function. That summation is a routine
Borel-Cantelli and Tonelli argument; the thresholds must be chosen
consistently for it to apply.
Define two profiles, extended by zero outside [0,1):
h = 1_{[0,1/2)} - 1_{[1/2,1)},
g = 1_{[0,1/4)} - 1_{[1/4,1/2)}
- 1_{[1/2,3/4)} + 1_{[3/4,1)}.
For a dyadic interval I = [a, a+r) put h_I(y) = h((y-a)/r) and
g_I(x) = g((x-a)/r). Then the "shift summand"
( (1/|I|) int_I rho(y) chi_n(y) h_I(y) dy ) * g_I(x) (10.1)
is exactly what a single node of the delayed dyadic shift produces
with sign choices r_{j+1} and r_{j+2}: on the output side set
epsilon_j = r_{j+1}, so that g_I = r_{j+1} r_{j+2}. In other words,
the operator (10.1) is an admissible summand in Prop 9.1.
Tile the line by top intervals of length s in [1/2, 1), translate
the tiling by a in [0, s), and use child depths j = 0, ..., J-1 below
every top. The resulting finite-depth shift is H_{a,s,J}^u. It is
admissible in Prop 9.1 up to the density cutoff. At most a fixed
number of top intervals meet [0, 1); each has input average at most
2 * s <= 2, so Prop 9.1 applies uniformly in a, s, J:
int_{G_rho} sup_{n in Z}
| H_{a,s,J}^u( rho chi_n )(x) | dx <= C d. (10.2)
The constant is absolute, independent of a, s, J, and u.
Let kappa: (0,1] -> R be a bounded odd mean-zero function with
support on [1/4, 1] and int kappa(r) dr/r = c_kappa a fixed nonzero
constant. Write pi c = c_kappa; the constant pi c will appear.
Define the averaged operator on the circle by
T_J^u rho(x) = int_{[0,1)} int_{[1/4,1)} kappa(r)
H_{a,s=1,J}^u( rho chi_{floor(u*r)} )(x)
dr da. (10.3)
Two comments. First, the "floor(u*r)" is what turns the u-modulation
into the ordinary integer frequency after averaging. Second, the
kernel kappa being odd and mean-zero on log scale turns the sum over
dyadic levels (each level weighted by r) into a sum that telescopes
to the Hilbert-kernel shape.
The averaged kernel bound is:
PROPOSITION 10.1 (T^u is controlled by the good set).
int_{G_rho} sup_{|u| <= Q} |T_J^u rho(x)| dx <= C d. (10.4)
Proof: apply (10.2) inside the averaging. Since kappa is bounded,
and since a, s range over [0,1) and [1/4,1) respectively (both of
finite measure), the average inherits the L^1 bound. The
identification of the "floor(u*r)" with the dyadic ruler's modulation
is a change of variables: at dilation scale 1/r, the integer
frequency |u*r| matches the modulation scale, and the shift at scale
1/r on the translation a is the precise form the Haar profile
expects. This is the essential remark: getting modulated dyadic
blocks to become modulated convolutions is only possible if the
modulation parameter and the dyadic level are matched in this way.
[]
LEMMA 10.2 (kernel identification). Let
Kappa_J(t) = sum over dyadic r in (2^{-J}, 1] of
kappa(r) * (1 / r) * ( 1_{t/r in [1/4, 1/2)} - ... )
be the kernel obtained from the averaged operator T_J^u by taking
the u-modulation to a formal "high frequency" limit. Then Kappa_J
converges in L^1(dx) to a fixed multiple pi c of the periodic
cotangent kernel pi c * cot(pi t), as J -> infinity. More precisely,
for any rho of mass one and height at most e^d, and any u != 0,
| T_J^u rho(x) - pi c * H_{per}(rho chi_u)(x) | -> 0 (10.5)
in L^1(dx) as J -> infinity, where H_{per} is the periodic Hilbert
transform.
Proof of Lemma 10.2. The averaging over a in [0,1) with the
integer modulation floor(u*r) turns each dyadic level into the
contribution of a "truncated kernel" K_r(t) supported at scale r.
The dyadic sum of these K_r over r in (2^{-J}, 1] is a kernel
Kappa_J(t). The point of the odd-mean-zero choice of kappa is that
the resulting Kappa_J has the properties:
(a) Kappa_J(t) is bounded except near t = 0.
(b) Kappa_J's nonzero support is at scales |t| >= 2^{-J}.
(c) Kappa_J is odd and has the right *sum over dyadic scales*
mass: each dyadic level contributes c_kappa, summing to
sum over J levels of c_kappa = J * c_kappa = log(2^{-J}) * 1/t
up to bounded corrections. This "1/t" is precisely the
Hilbert-kernel blowup.
The inner window (|t| <= 2^{-J} = delta) converges to zero after
being dominated by the maximal function M rho of the input. On the
complement, the difference pi c * cot(pi t) - Kappa_J(t) is bounded
by an absolute constant on each dyadic annulus, and its L^1 norm
against a mass-one height <= e^d rho is at most C (the sum of the
bounded remainders over annuli). Since the annuli have summable
mass, L^1 convergence follows as J -> infinity.
The "central annulus" identification: on delta < |t| <= 1/2 the
difference pi c * cot(pi t) - 1/t is bounded on [-1/2,1/2] by a
constant, and the term 1/t agrees with the kappa-summed kernel.
On 1/2 < |t| <= 1 the kernel is bounded. Therefore the total
difference is bounded, giving (10.5). []
Note the exact structure: no L^2 theory is needed for the Fourier
move; only L^1(dx) against a mass-one bounded rho is used. This
is why the Fourier side is cheap compared with the dyadic side.
The requirement "only integer modulations u" is discharged by the
"floor(u*r)": the integer frequencies appear at the correct scale
for the (a,r) average. The final kernel pi c * cot(pi t) is a
periodic *function*, not a distinguished frequency. The u sits
inside the character chi_u(Y) of the input factor only; the output
factor is uniform in u. Hence the average T_J^u, as an operator on
L^1, has the same bound uniformly in u.
Theorem B specializes from this.
THEOREM 10.3 (good-set integral estimate). There are absolute
constants C and d_* such that, whenever d >= d_* and rho is a
nonnegative periodic function with int_0^1 rho = 1 and rho <= e^d
almost everywhere,
int_{G_rho} sup_{N >= 0} |S_N rho(x)| dx <= C d. (10.6)
G_rho = { M rho <= e^{4h} } and h = log log d.
Proof. Combine the following chain:
(i) (10.4): the averaged dyadic operator T_J^u is bounded by
C d on G_rho, for all |u| <= Q.
(ii) (10.5): as J -> infinity, T_J^u converges in L^1(dx) on
G_rho to pi c * H_{per}(rho chi_u). Hence
int_{G_rho} sup_{|u| <= Q} |H_{per}(rho chi_u)(x)| dx <= C d (10.7)
for all Q >= 1.
(iii) Monotone convergence in Q takes the sup over all u in Z.
(iv) Fourier-multiplier identity: for every integer N,
S_N rho = chi_{-N} * Pi_{>=0}( rho chi_N )
- chi_{N+1} * Pi_{>=0}( rho chi_{-(N+1)} ),
where Pi_{>=0} = (I + iH_{per} + P_0)/2 is the projection
onto nonnegative Fourier frequencies and P_0 is projection
onto constants. Then |S_N rho| <= rho + |int rho| +
sup_u |H_{per}(rho chi_u)|, since the multipliers chi_{-N}
have modulus one.
(v) Integrating (iv) on G_rho, use (iii):
int_{G_rho} sup_N |S_N rho| dx
<= int_{G_rho} rho dx + 1 + int_{G_rho} sup_u |H_{per}(rho chi_u)| dx
<= C d. (10.8)
The last term uses (iii); the rho term is the mass; the 1 is the
constant contribution and the |int rho| = 1. All constants are
absolute because the averaging in (ii) lost no constant over J.
[]
The next step will be the passage from good-set bounds to
everywhere-convergence in a height layer. This uses two classical
facts included for completeness.
LEMMA 10.4 (bounded inputs). Every bounded complex-valued
periodic function has almost-everywhere convergence of its symmetric
Fourier partial sums along the full sequence.
Proof of Lemma 10.4. Let ||f||_infty <= B. Take the Fejer means
P_l of f. These are trigonometric polynomials with
||P_l||_infty <= B and ||f - P_l||_1 -> 0 (approximate-identity
property of the nonnegative, mass-one Fejer kernels, plus continuity
of translations in L^1). Split f - P_l into positive and negative
parts of real and imaginary components. Each component q_l is
nonnegative, has ||q_l||_infty <= 2B, and has mass m_l -> 0.
If m_l = 0, its partial sums vanish. Else normalize to rho_l =
q_l / m_l and choose d_l = d_* + max(0, log(2B/m_l)). Then d_l ->
infinity, m_l d_l -> 0, and rho_l <= e^{d_l}. Apply Theorem 10.3
to rho_l:
int sup_N |S_N (rho_l)| dx <= C d_l
where the integral is over rho_l's good set G_{rho_l}. On the
complement (small-measure set where M rho_l is large), by Markov's
inequality,
|G_{rho_l}^c| <= C (log d_l)^{-4}.
Combining with a Chebyshev bound on the S_N rho_l sup outside
the good set gives, for each eta > 0,
|{ sup_N |S_N q_l| > eta }|
<= C (log d_l)^{-4} + C m_l d_l / eta -> 0.
Therefore sup_N |S_N q_l| -> 0 in measure as l -> infinity.
Applying componentwise gives sup_N |S_N (f - P_l)| -> 0 in measure.
For each l, the partial sums of P_l are eventually equal to P_l
itself (as P_l has finitely many frequencies). Consequently the
measurable function A(x) = limsup_{N -> infinity} |S_N f(x) - f(x)|
satisfies
A(x) <= sup_N |S_N (f - P_l)(x)| + |f(x) - P_l(x)|
almost everywhere. Both right-hand terms tend to zero in measure as
l -> infinity. Hence A = 0 a.e. []
THEOREM 10.5 (Theorem A, almost-everywhere Fourier convergence in
L log L). Every complex-valued f in L log L(T) has
lim_{N -> infinity} S_N f(x) = f(x) for almost every x in T.
Proof. Write f = f_bd + sum_{j >= 1} f_j, where
f_bd = f 1_{|f| < e^2}, f_j = f 1_{e^{2^j} <= |f| < e^{2^{j+1}}}.
For each j, split f_j into four nonnegative parts using positive and
negative parts of real and imaginary components with coefficients
1, -1, i, -i. Consider one such sequence q_j; let m_j = int q_j;
discard zero-mass members. Set
rho_j = q_j / m_j, d_j = 2^{j+1} + log^-(m_j).
Then int rho_j = 1 and rho_j <= e^{d_j}. For all sufficiently
large j, Theorem 10.3 applies (with d = d_j).
Summability of layer costs. On supp q_j, log |f| >= 2^j, and
q_j <= |f|. Disjointness of the layers gives
sum_{j >= 1} 2^{j+1} m_j
<= 2 int_{|f| >= e^2} |f| log |f| < infinity. (10.9)
For the additional log-entropy term: if m_j >= e^{-2^j}, then
m_j log^-(m_j) <= 2^j m_j. If m_j < e^{-2^j}, monotonicity of
t log(1/t) on (0, e^{-1}) gives m_j log(1/m_j) <= 2^j e^{-2^j}. Both
bounds are summable over j. Hence
sum_j m_j d_j < infinity. (10.10)
Summability of good-set complements. Let G_j be the good set
associated with rho_j, so |G_j^c| <= C (log d_j)^{-4}. Since
log d_j >= (j+1) log 2,
sum_j |G_j^c| <= C sum_j (log d_j)^{-4} < infinity. (10.11)
By Borel-Cantelli: almost every point x belongs to all but finitely
many G_j.
Summability of good-set max transform. Tonelli and (10.6)/(10.10):
int sum_j 1_{G_j}(x) sup_N |S_N q_j(x)| dx
<= C sum_j m_j d_j < infinity. (10.12)
(Only finitely many initial layers need to be omitted because
d_j below d_* falls outside Theorem 10.3's hypotheses; the others
sum.)
Therefore at almost every point x, the partial-sum maxima of the
tail layers are absolutely summable. Every individual q_j is
bounded, so Lemma 10.4 gives its a.e. limit and gives 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
of every layer and for f_bd. On the resulting full-measure set, all
the individual limits exist and the summability (10.12) makes the
layer sum converge. Hence for almost every x,
lim_{N -> infinity} S_N f(x) = f(x).
This proves Theorem A. []
COROLLARY 10.6 (maximal weak-L^1). There is an absolute constant C
such that, for every measurable f on T,
| { sup_N |S_N f| > lambda } | <= C ||f||_Phi / lambda, lambda > 0.
||f||_Phi denotes the real Luxemburg norm of the Orlicz space
L^Phi where Phi(t) = t log(2+t).
Sketch. The real Luxemburg space B = L^Phi(T; R) is Banach. Since
Phi(2t) <= 4 Phi(t), its underlying set is exactly the real L log L
class, and ||f||_1 <= ||f||_Phi / log 2. Translations are isometries
of B. Each S_N is a real linear operator commuting with translations
and bounded from B into itself (since ||S_N f||_infty <= (2N+1)
||f||_1, and L^infty embeds continuously in B); the bounds need not be
uniform in N. By Theorem A, S^* f is finite a.e. for every f in B.
Stein's theorem applied to the sequence S_0, -S_0, S_1, -S_1, ...
(the signed supremum is exactly S^* f for this sequence) gives the
weak-L^1 maximal bound for real inputs. For f = u + iv use
S^* f <= S^* u + S^* v and ||u||_Phi, ||v||_Phi <= ||f||_Phi,
splitting at lambda/2. Enlarging C by a fixed factor handles the
complex case. []