usetikzlibrary{arrows.meta,decorations.pathreplacing}


urlstyle{same}

















allowdisplaybreaks[2]



Fix a binary word x=x_1... x_nin{0,1}^n and a deletion probability qin(0,1). Write p=1-q. A complete trace of x is produced as follows: each position i is retained independently with probability p; the retained bits, in positional order, form a word of length at most n. A trace reports its own length and its bits, but nothing about which starting positions survived. Let Dcal_q(x) denote the resulting law on the countable set of finite binary words.

For sin(0,1], define T_{q,s}(n) as the least nonnegative integer m for which some estimator, equipped with n, q, and m independent samples from Dcal_q(x), recovers every xin{0,1}^n with probability at least s. The estimator may be randomized and computationally unbounded; if no finite m suffices, set T_{q,s}(n)=+∞. Write T_q(n)=T_{q,2/3}(n).

[Quantitative sample lower bound]
Fix sin(0,1] and 0<c<1/(4log 2). Along every sequence of instances (n,q) with nto∞, qin(0,1), and q^3log nto∞,
[
T_{q,s}(n)ge n^{clog(q^3log n)}
]
for all sufficiently large instances. All logarithms are natural. In particular, at every fixed deletion probability qin(0,1) and every fixed positive success probability s, the required sample size is n^{Ω(loglog n)}.


The channel is fixed for each instance; it may change only when the instance changes. The result gives a negative answer to the polynomial-sample question for deterministic binary inputs at every fixed deletion probability. For probability laws P,Q on the set of finite binary words, write
[
TV(P,Q)=frac12sum_w|P(w)-Q(w)|.
]

[Superpolynomial one-trace indistinguishability]
For every fixed deletion probability qin(0,1),
[
lim_{nto∞}n^Amin_{substack{x,yin{0,1}^n xne y}}TV(Dcal_q(x),Dcal_q(y))=0quadfor every A>0.
]
At the same channel, T_{q,s}(n)/n^Ato∞ for every fixed A>0 and sin(0,1].


The channel is fixed independently of A. The minimum is attained at every n, so a single sequence of minimizing pairs realizes all the limits simultaneously.

Reconstructing a sequence from repeated corrupted observations has a long information-theoretic history. Levenshtein studied both combinatorial and memoryless channel formulations. Batu, Kannan, Khanna, and McGregor brought reconstruction from independent random deletion traces into theoretical computer science, motivated partly by multiple sequence alignment, and outlined a linear-sample obstruction at fixed deletion probability.

./pdf/levenshtein-2001-ieee-slides.pdf
./pdf/batu-kannan-khanna-mcgregor-2004.pdf

Later lower bounds for complete traces focused on the difficulty of locating a small discrepancy within a long background. McGregor, Price, and Vorotnikova analysed neighbouring positions of a single one among zeros, using squared Hellinger distance and common mass. Holden and Lyons used a defect in an alternating background to prove Ω(n^{5/4}/√(log n)), and Chase obtained Ω(n^{3/2}/log^7 n) by a direct Hellinger calculation for a related pair. The displayed Holden--Lyons and Chase rates fix the channel and a reconstruction success greater than 1/2. The seed set out later starts from the periodic defect family used by Chase and makes signed choices across many periods; it also supplies the overlap and score estimates required for repeated amplification.

./pdf/mcgregor-price-vorotnikova-2014.pdf
./pdf/holden-lyons-2020.pdf
./pdf/holden-lyons-errata-2022.pdf
./pdf/chase-2021-lower.pdf

For fixed deletion probability, Holenstein, Mitzenmacher, Panigrahy, and Wieder obtained a worst-case upper bound of exp(widetilde O(sqrt n)), where widetilde O suppresses polylogarithmic factors. Independently, De, O'Donnell, and Servedio and Nazarov and Peres improved it to exp(O(n^{1/3})), and Chase obtained exp(O(n^{1/5}log^5 n)). The 2026 preprint of Burudgunte, Valiant, and Wang supplies exp(p^{-7/3}(log_2 n)^{C_0}) samples for a universal constant C_0 and every positive retention probability p=1-q. At fixed p this bound is quasipolynomial in n, and the preprint gives no quasipolynomial-time reconstruction algorithm. The logarithm of this sample bound is a fixed power of log n, whereas the logarithm of the lower bound of Theorem~thm:main at a fixed channel has order (log n)(loglog n); a gap between the rates remains.

./pdf/hmpw-2008.pdf
./pdf/dos-2017.pdf
./pdf/nazarov-peres-2017.pdf
./pdf/chase-2021-upper.pdf
./pdf/burudgunte-valiant-wang-2026.pdf

Polynomial reconstruction remains possible under other channel or input conditions. For every fixed ε>0, Chen, De, Lee, Servedio, and Sinha give reconstruction in polynomial time when qle n^{-1/3-ε}, using O(n^{4/3}) traces. Those deletion probabilities lie outside the regime q^3log nto∞ of Theorem~thm:main. Aamand, Liu, and Narayanan prove polynomial reconstruction when the internal zero gaps between successive ones have length at least a sufficiently large constant times (log n)^8 and the deletion probability is at most a sufficiently small universal constant.

./pdf/chen-de-lee-servedio-sinha-2021.pdf
./pdf/aamand-liu-narayanan-2025.pdf

Some lower bounds restrict the available statistics. De, O'Donnell, and Servedio measure the precision required of an oracle returning an ell^1 approximation to the expected trace vector padded with zeros, while Nazarov and Peres study repeated observations of one fixed output coordinate. Chen, De, Lee, and Servedio study a tolerance oracle for functions of contiguous blocks of trace coordinates. These lower bounds concern those specified statistics. A different input model is studied by Rivkin, Valiant, and Valiant: the input is a fixed probability vector, with fresh Bernoulli bits drawn from it before each trace. For deletion probability at least a constant times n^{-1/2} its generalised trace laws can have total variation exp(-Ω(sqrt n)). Its use of translated segments and cancellation is related to the observation constructed in the proof of Theorem~thm:main. Theorems~thm:main and~thm:tv concern the entire trace law of one deterministic binary word.

./pdf/dos-2017.pdf
./pdf/nazarov-peres-2017.pdf
./pdf/chen-de-lee-servedio-2024.pdf
./pdf/rivkin-valiant-valiant-2025.pdf

The basic source of hidden randomness is exact common mass. If the trace laws of k and k+1 copies of a word share mass omega, such a pair of runs is placed on opposite sides of a central segment and its orientation is fixed by a fair bit. Their joint trace laws share a product component of mass omega^2. On that component the orientation stays fair even after the side outputs are reported. Many independent pairs therefore leave a binomial uncertainty in the position of the central segment. Marginalising the flags restores the product of the two side trace laws for each orientation. Concatenating independent genuine traces of a partition of the fixed word then recovers its trace law exactly. At later scales the preliminary observation uses earlier auxiliary outputs at its leaves and allows rare failed layouts. At every scale, conditioning to obtain likelihood domination adds a small change. The resulting auxiliary laws therefore have an approximate common projection to genuine traces, with all these losses recorded in an invariant.

The two words use complementary signed patterns in their central segments. The generating polynomial of a Prouhet--Thue--Morse pattern vanishes to high order at 1, which makes its convolution with a broad binomial offset small. The same dyadic sign recursion is used by Holenstein, Mitzenmacher, Panigrahy, and Wieder to produce iterated finite differences of a kernel for coordinate means. In the conditional likelihood difference, each selected leaf set indexes a product of old likelihood scores, one per leaf, multiplied by a coefficient. This coefficient is expanded along the tree of nested segments as a sum of expected products of signed motif factors and support indicators, averaging over the hidden bits. Inside one such product, a child is active at a vertex when it supplies one of these local factors, and the term is odd there when an odd number of the local factors are signed. The complementary words give root types +1 and -1, so subtracting the two root evaluations cancels every even root term. At a vertex where an odd term has exactly one active child, the hidden offset smooths its single local signed factor. For an odd root term with no such singleton, selecting two active children recursively forces a complete binary subtree with 2^b selected leaves at depth b, hence at least 2^b old-score factors. A shared displacement for each sibling group, together with independent local displacements for its members, spreads these descendant locations. A joint bound that retains the shared displacement then yields the additional decay beyond the factors inherited from the old score.

./pdf/allouche-shallit-1999.pdf
./pdf/hmpw-2008.pdf

Three quantitative requirements drive the scale choices. The initial pair must work uniformly as q decreases. The number of amplification blocks grows with n, so constants depending on the channel or the cancellation order must stay within the available scale margins. And every oracle conditioning and every failed random layout must be charged to an error that remains negligible after many traces.

For probability laws P,Q, define overlap by ov(P,Q)=1-TV(P,Q), the mass of a largest common subprobability. The squared Hellinger distance is
[
 H^2(P,Q)=int(√(dP)-√(dQ))^2 .
]
Cauchy--Schwarz and Hellinger affinity give TV(P,Q)le H(P,Q)le√(2TV(P,Q)). Both distances decrease under a common stochastic kernel, and squared Hellinger distance of product laws is at most the sum for the factors. If Qll P, then
[
 H^2(P,Q)leint((dQ)/(dP)-1)^2 dP .
]
These elementary ineualities explain why a small likelihood score is an appropriate induction quantity.

For the remainder of the construction put
[
 delta=min(q,1/2), Λ=delta^{-3}, H_{del}=delta^3log n .
]
Write Tr(w)=Dcal_delta(w) throughout. The requested channel q is obtained from a delta-trace by deleting each surviving bit with additional probability (q-delta)/(1-delta), so every upper bound on distinguishability proved at delta also holds at q. Moreover
[
 H_{del}to∞,
 log H_{del}=log(q^3log n)+O(1).
]
The working deletion rate delta stays fixed through every intermediate scale of an instance. In all integer index ranges the endpoints may be real; only integer labels inside the range are used.

The induction carries three estimates for each pair of deterministic words. Two auxiliary laws mu,nu can be postprocessed by one kernel to approximate the genuine trace laws, and the likelihood score dnu/dmu-1 has a small moment. These control distinguishability at the current length. The third estimate is common mass between traces of two consecutive powers of the first word, which supplies the hidden orientation bits used to construct the next pair.

Abstracting the small exponent margins, a block of depth b with target length N starts from atoms of length about N^{2^{-b}} whose squared score is at most N^{-2^{-b}d}. The low-degree analysis either suppresses a term by signed smoothing or forces 2^b old-score factors, which together retain approximately the decay N^{-d}. Joint locations of sibling groups supply the additional decay N^{-(b-1)/4}.

Fix 0<c<c_+<1/(4log 2), then fix a constant integer Bge 2 and 0<zeta<1 with
[
((1-zeta)((B-1)/4-.05))/(Blog 2)>c_+>c .
]
Set
[
D=Big⌊( (1-zeta)frac{log H_{del}}{Blog 2}),
j_0=5· 2^B,
ε=2^{-4B-100}/(D+1),

b_i=2,&1le ile j_0, B,&j_0<ile D.
]
Work in the regime D>j_0 (which fails for finitely many n). For each admissible depth, put
[
a_0(b)=(1+ε)2^{-b}-ε ,
]
which is positive for all sufficiently large instances. Define target scales backwards by
[
N_D=n, N_{i-1}=N_i^{a_0(b_i)}(1le ile D),
]
and score exponents by
[
d_0=2.20, d_i=d_{i-1}+(b_i-1)/4-.05quad(1le ile D).
]
Each preliminary depth-2 block adds .20, so d_{j_0}=2.20+2^B. That preliminary phase raises the seed exponent to the strength required by depth-B blocks. The remaining blocks give the asymptotic gain in Theorem~thm:main.

The remaining parameters control accumulated projection error and rare events. Put
[
Delta=n^{-100(d_D+B+1)},
r_i=2Bigllceil 10^8,2^{10B}(d_D+B+1)(log n)/(log N_i)Bigrrceilquad(0le ile D).
]
The even moment orders r_i are nonincreasing in i, so a moment bound available at one level survives to the next. Their dependence on log n/log N_i makes the exceptional probabilities small relative to the final-length error budget even at the smallest scale.

[Uniform scale margins]
For the parameters above,
[
log N_0gtrsim_B(log n)2^{-BD}gtrsim_B(log n)H_{del}^{-(1-zeta)}=Λ H_{del}^{zeta}.
]
Moreover,
[
εlog N_0gtrsim_B((log n)^zeta)/(1+loglog n)ggloglog n+log(d_D+B+1).
]
For every fixed nonnegative integer h, uniformly over 0le ile D,
[
(D+1)^hΛ=o(εlog N_0),
exp(O_B((D+1)^hΛ))=N_i^{o(ε)}.
]

Proof. 
For every admissible b one has a_0(b)ge2^{-B}(1-(2^B-1)ε). Multiplying over D blocks loses only a factor bounded away from zero by a positive constant depending on B, because Dεle 2^{-4B-100}. The definition of D proves the first display. Since H_{del}lelog n and D+1=O_B(1+loglog n), the same bound proves the second. Finally
[
((D+1)^hΛ)/(εlog N_0)lesssim_Bfrac{(D+1)^{h+1}}{H_{del}^{zeta}}→0,
]
because D=O_B(log H_{del}). Since N_ige N_0, this proves the exponential form as well.


In particular log r_i=O_B(D+1) uniformly in i. Constants in O,asymp,lesssim may depend on B,zeta,c_+ unless further dependence is stated. All estimates used at multiple levels are uniform in i as nto∞. The rate delta always has the value fixed by the input instance, not one recomputed from N_i.

Distinct equal-length words each admit an exclusive full-length trace of positive probability, so neither genuine trace law dominates the other. This motivates placing the likelihood score on auxiliary laws and recording their projection errors separately.

[Level invariant]
Choose C>2, 0<omega<1/8, and a constant M_Bge0 depending only on B, with log C=O(Λ) and log(omega^{-1})=O(Λ), depending only on delta. The same choices are used at every level. For 0le ile D, a level-i pair consists of two different strings x_i,y_i of common length ell_iin[N_i/2,N_i], and probability laws mu_i,nu_i on a common auxiliary space, satisfying three conditions:
[(i)] There are a Markov kernel K_i from the auxiliary space to finite binary words and a number E_ige0 with
[
TV(K_i,Tr(x_i))le E_i, TV(K_i,Tr(y_i))le E_i, (E_i)/(ell_i)le(i+1)Delta.
]
[(ii)] nu_illmu_i and
[
Bigl|(dnu_i)/(dmu_i)-1Bigr|_{L^{r_i}(mu_i)}^2le N_i^{-d_i}.
]
[(iii)] For an integer k_iin[ell_i,C^{2Bi+M_B}ell_i],
[
ov(Tr(x_i^{k_i}),Tr(x_i^{k_i+1}))geomega .
]

Powers concatenate copies of a word.


For every positive integer m, conditions (i) and (ii) give
[
TV(Tr(x_i)^{ ⊗  m},Tr(y_i)^{ ⊗  m})lesqrt{m N_i^{-d_i}}+2mE_i,
]
by Hellinger tensorisation and telescoping the projection errors. That ineuality isolates why the squared score carries the sample exponent d_i. The pairs need not hit the target scales exactly; padding is reserved for the final transfer and is not inserted into words used by later blocks.

[Construction at every scale]
Fix B,zeta,c_+ and the parameters above. Along every sequence with nto∞ and delta^3log nto∞, for all sufficiently large instances there exist level-i pairs satisfying Definition~def:invariant simultaneously for 0le ile D. The constants C,omega depend only on delta and satisfy the stated logarithmic bounds; a single M_B depending only on B works at every level.


[Multilinear moment bound]
Let tge2 be an even integer, let hge0, and let (Z_j)_{jinJ} be a finite family of independent centred real variables with |Z_j|_tle h. For an integer rge1, the degree-r multilinear polynomial with real coefficients A(S) on r-subsets satisfies
[
Bigl|sum_{|S|=r} A(S)prod_{jin S} Z_jBigr|_tle (C_1 t h)^r |A|_{ell^2},
]
where ell^2 uses counting measure and C_1 is absolute.

Proof. 
The tensorisation follows the classical principle behind hypercontractive estimates. An elementary argument works for arbitrary independent centred real coordinates with the stated moment bound; neither symmetry nor a common distribution is required. Normalise h=1 (the zero case is trivial). A scalar satisfies |b+vZ|_t^2le |b|^2+C_2 t |v|^2 for real b,v. If |v|le |b|/t and bne0, expand the moment, whose linear term vanishes, and bound it by |b|^t(1+O(t^2(v/b)^2)) using sum_{kge2}(t|v/b|)^k/k!. Concavity gives (1+O(t^2(v/b)^2))^{2/t}le 1+O(t(v/b)^2). Otherwise use the triangle ineuality and 2|bv|le 2t|v|^2. Iteration by conditioning on one variable's complement and applying the triangle ineuality in L^{t/2} proves the bound. The same ineuality applies to finite families indexed by positions or ranks, identifying ordered increasing tuples with subsets.


./pdf/bonami-1970.pdf

[Lifting adjacent-power overlap]
Let w be a nonempty word, k a positive integer, and 0<omega<1/8 with ov(Tr(w^k),Tr(w^{k+1}))geomega. There is an absolute C_{abs} such that whenever Cge C_{abs}/omega, P exceeds a sufficiently large absolute constant, and the integer F satisfies Fge CkP,
[
ov(Tr(w^{FP}),Tr(w^{FP+P}))ge 2/3 .
]

Proof. 
This is a quantitative common-part smoothing statement related in mechanism to consecutive-power smoothing for positive contractions. Write the two words as a common tail of FP-g(k+1/2) copies and g=2floor( FP/(2k+1)) chunks of k or k+1 copies, where the number m of long chunks is g/2 or g/2+P respectively. Use a uniform random schedule conditional on this total, and let omega U be a common sublaw of the chunk trace distributions. Emit the trace under U on independent flags of probability omega (hiding the label k or k+1); else reveal the label and generate from the normalised residual. The augmented laws postprocess to the asserted ordinary ones by joining the chunks and simulating the known tail.

Given the flags and the sequence of visible labels, the remaining data have the same conditional law under the two hypotheses. The number M of hidden flags lies in [omega g/2,2omega g] except with probability at most 2exp(-c'omega g) for an absolute c'>0 by the multiplicative binomial Chernoff bound, where omega gge c''omega CP^2 for an absolute c''>0 at all large P. Conditional on such flags, the total variation between visible-label sequences equals the total variation of the visible long-count variable v, because the sequences are exchangeable on visible indices. For total m, the variable v has hypergeometric law
[
p_m(v)=binom{g-M}{v}binom{M}{m-v}Big/binom{g}{m}.
]
Uniformly for g/2le mle g/2+P, one has sup_v p_m(v)=O((omega g)^{-1/2}). Consecutive probability ratios locate a mode within O(1) of (g-M)m/g, for instance at floor((g-M+1)(m+1)/(g+2)). At large P the counts and complements in the numerator at the mode are all fixed positive fractions (say between 1/4 and 3/4) of their trial totals, because ggtrsim CP^2, Mgeomega g/2gtrsim P^2, and g-Mge(1-2omega)g. Stirling then gives the bound, the exponential entropy factor being at most one by concavity.

Couple adjacent m,m+1 by flipping one short label uniformly. This increases v by one with probability t(v)=(g-M-v)/(g-m) conditional on v, so p_{m+1}(v)-p_m(v)=t(v-1)p_m(v-1)-t(v)p_m(v). The sequence t(v)p_m(v) on the support, extended by zero, is unimodal by log-concavity. Thus the adjacent total variation is max_v t(v)p_m(v), bounded by max_v p_m(v). The full variation cost of all P steps is O(P/√(omega g)) plus the rare flag probability, which is at most 1/3 at large P by choosing Comega greater than a sufficiently large absolute constant. Taking smaller common sublaws if needed uses exactly mass omega in the flag construction.


doi.org/10.1017/S0013091500004624
A paired construction of two chunks uses a joint common component of mass omega^2; on this component the orientation stays fair conditional on the flag and on both reported side outputs. Common-part constructions appear in the average-case block argument of McGregor, Price, and Vorotnikova and in the partial-trace construction of the proof of Holden and Lyons. Figure~fig:paired-hiding depicts one pair and the resulting uncertainty in the number of copies to the left of the central segment.

./pdf/mcgregor-price-vorotnikova-2014.pdf
./pdf/holden-lyons-2020.pdf

Unless window boundaries or additional payloads are specified, report only one unseparated output per segment, chunk, or residual, together with flags and revealed orientation bits as indicated, and not the word boundaries internal to that output. Given a word w and a count k with ov(Tr(w^k),Tr(w^{k+1}))geomega, choose a common sublaw omega U. Two chunks use a paired random-bit orientation giving lengths (k,k+1) or (k+1,k), even when far separated in the concatenation. Use one joint flag of probability omega^2 and output from U ⊗  U on it; otherwise reveal the bit and generate the two traces jointly from the normalised residual after subtracting omega^2 U ⊗  U from the product law for that orientation. Marginalising flags yields the requisite conditionally independent pair traces given orientations. Conditional on the augmented pair data, the bit remains fair on the hidden event. Independent pairs thus carry independent hidden fair bits conditional on this part of the report. All auxiliary schedules and flags are redrawn independently for each trace.

[htbp]
centering
[x=1cm,y=1cm,font=small,>=Latex,
  side/.style={draw=blue!45!black,fill=blue!6,minimum width=2.8cm,
               minimum height=0.48cm,inner sep=2pt},
  center/.style={draw=blue!45!black,fill=blue!18,minimum width=3.5cm,
                 minimum height=0.48cm,inner sep=2pt},
  card/.style={draw=blue!45!black,rounded corners=2pt,align=center,
               text width=5.8cm,minimum height=0.94cm,inner sep=5pt}]
  node[anchor=west,font=smallbfseries] at (0,0.58)
    {A fair bit swaps the side lengths};
  node[anchor=east] at (13.7,0.58)
    {EsimBernoulli(1/2)};
  node[anchor=east] at (0.75,0) {E=0};
  node[side] at (2.4,0) {w^k};
  node[center] at (7.0,0) {central segment};
  node[side] at (11.6,0) {w^{k+1}};
  draw[blue!45!black] (3.8,0)--(5.25,0);
  draw[blue!45!black] (8.75,0)--(10.2,0);
  node[anchor=east] at (0.75,-0.65) {E=1};
  node[side] at (2.4,-0.65) {w^{k+1}};
  node[center] at (7.0,-0.65) {central segment};
  node[side] at (11.6,-0.65) {w^k};
  draw[blue!45!black] (3.8,-0.65)--(5.25,-0.65);
  draw[blue!45!black] (8.75,-0.65)--(10.2,-0.65);
  node[draw=blue!45!black,fill=white,rounded corners=2pt,
        minimum width=12.6cm,minimum height=0.54cm] (law) at (7.0,-1.48)
    {P_E=omega^2(U ⊗  U)+(1-omega^2)R_E};
  node[card,fill=blue!9] (hidden) at (3.45,-2.52)
    {Hidden: E is not reported. Emit U ⊗  U; E remains fair.};
  node[card,draw=black!50,fill=black!3] (visible) at (10.55,-2.52)
    {Visible: report E. Emit the joint residual R_E.};
  draw[->,blue!45!black] (4.8,-1.75)--(3.45,-1.99);
  draw[->,black!65] (9.2,-1.75)--(10.55,-1.99);
  node[draw=blue!45!black,fill=blue!5,rounded corners=2pt,
        text width=13.0cm,align=center,inner sep=6pt,anchor=north] at (7.0,-3.50)
    {J pairs contribute L_{left}:=Jk+sum_{i=1}^{J}E_i copies of w on the left.
     After the side report, c_{vis}:=Jk+sum_{visible}E_i and hidden count M fixed, and
     L_{left}=c_{vis}+sum_{hidden}E_i
     overset{law}{=}c_{vis}+Bin(M,1/2).};

caption{Let omega U be a common sublaw of the trace laws of w^k and w^{k+1}. For orientation E, P_E is the product of its two side laws and R_E is the normalised joint residual. Across J independent pairs straddling the segment, MsimBin(J,omega^2) before reporting. The lower panel conditions on flags, side outputs, and visible bits; L_{left} counts only copies contributed by the left pair members. Other fixed material adds a deterministic location offset. Block widths are schematic.}



[Clipping with a common event]
Fix a level 0le ile D and its parameters. Suppose preliminary oracle laws have common side metadata with law Q_{side}, and conditional densities G_x,G_y over a conditional reference Q, possibly depending on metadata. Require int G_x,dQ=int G_y,dQ=1 for Q_{side}-almost every metadata value, and use Q_{side}Q as the joint reference. Suppose on a typical metadata event of probability at least 1-o(Delta) the uniform estimates
[
|G_x-1|_{r_i}, |G_y-1|_{r_i}le N_i^{-rho}
quadandquad
|G_y-G_x|_{r_i}^2le N_i^{-d_i-.01}
]
hold in L^{r_i}(Q), where rhoge2^{-4B-10}. Then conditioning each law on the event consisting of typical metadata and G_xge1/2 changes it in total variation by o(Delta). The conditioned laws mu,nu satisfy nullmu and |dnu/dmu-1|_{L^{r_i}(mu)}^2le N_i^{-d_i}. All conclusions are uniform over 0le ile D.

Proof. 
Condition each preliminary law separately on the common event A_{keep} consisting of typical metadata and G_xge1/2. Its complement carries joint reference measure at most (2N_i^{-rho})^{r_i} on the typical part, hence bad mass o(Delta) under each preliminary law by Cauchy--Schwarz, the moment bound, and the common atypical mass. The conditioned laws therefore change postprocessing by o(Delta) in total variation. Since G_xge1/2 on A_{keep}, the new y-law is dominated by the new x-law, and the likelihood ratio on the latter's support is c'G_y/G_x with a scalar c'=1+o(Delta). Also
[
int_{{G_xge1/2, {typical}}}|G_y/G_x-1|^{r_i}G_x,d(Q_{side}Q)
le2^{r_i-1}N_i^{-(d_i+.01)r_i/2}.
]
Under the conditioned x-law this yields |G_y/G_x-1|_{r_i}le3N_i^{-(d_i+.01)/2} for all large n by taking the r_i-th root, since the conditioning probability is 1-o(Delta). Thus |c'G_y/G_x-1|_{r_i}le c'|G_y/G_x-1|_{r_i}+|c'-1|le N_i^{-d_i/2} for large n, because Deltale N_i^{-100d_D}. Any o(Delta) masses claimed from the assumed estimates follow uniformly from the definition of r_i and log N_ito∞; no uniform lower bound on the unconditioned ratio or density is required. For Hellinger comparisons of the preliminary laws, use the squared density difference times 2 on G_xge1/2 and G_x+G_y on its complement.


A seed pair is now constructed at the working rate delta. It supplies the induction with a pair whose squared score decays as N_0^{-2.20} and whose repeated traces share enough common mass to hide later offsets. The words have one defect in each alternating period, and a finite signed pattern moves some of these defects by one slot in opposite directions. The observation is first defined in a form that forgets starting slot labels, and its conditional rank probabilities serve twice: to obtain common mass for pure runs and to bound the score of the signed pair.

[Seed pair]
For the parameters set out above, there is a choice of the common constants in Definition~def:invariant with M_B=1 for which a level-0 pair exists with simulation error E_0leDelta. One may choose omega=exp(-C_9Λ) for an absolute C_9 and C>2 with log C=O(Λ).


Throughout the proof of Proposition~prop:initial, absolute constants are written C_*,c_*>0 and may change between estimates; constants indexed by r or s_0 may depend on those fixed indices. Put N=N_0, eta=.004,
[
 m=floor( N^{1/2-eta}),
 K=floor( N^{1/2-2eta}),
 k=floor(delta m),
]
[
 J=Big⌊((floor( N/(2m-1))-K)/(2k+1)),
 P=J(2k+1)+K .
]
Lemma~lem:scale-margins gives Λ=o(log N), hence delta^{-1}=N^{o(1)}. In particular delta^3 mto∞, mdelta^2to∞, and K,k+1le m for all sufficiently large instances. The definitions then give
[
 Jasympdelta^{-1}N^{2eta}, J=o(K), P(2m-1)in[N/2,N].
]
For the last assertion, P differs from floor( N/(2m-1)) by fewer than 2k+1, so the omitted length is O(km+m)=o(N).

For this construction, take the ordinary block A=01 and the defect block D=1. For bin{-1,0,1} define the period
[
 W_b=A^{floor( m/2)+b-1},D,A^{m-floor( m/2)-b} .
]
It contains m blocks, with the defect at block position floor( m/2)+b, and has length 2m-1. Period, slot and rank indices start at 1. For even m, the adjacent types W_0,W_1 coincide with the shifted-defect pair displayed by Chase in his lower-bound preprint; for odd m, these are the corresponding smaller pair with one common final A appended. Later, W_{-1} is compared with W_1 on exceptional periods and signed choices are made across many periods.

./pdf/chase-2021-lower.pdf

Set
[
 a=floor( P/2), s_0=300, I={0,...,2^{s_0}-1},
 sum_{iin I}beta_i z^i=prod_{v=0}^{s_0-1}(1-z^{2^v}) .
]
The two words x_0,y_0 have P periods. Every period is W_0 except at the labels a+i, iin I, where x_0 uses W_{beta_i} and y_0 uses W_{-beta_i}. For all sufficiently large instances these indices lie in {1,...,P}. Both words have length ell_0=P(2m-1)in[N/2,N] and the two differ: the parse into 01 and 1 from the left is unique. The signs beta_i are the classical Prouhet--Thue--Morse signs, whose polynomial has a zero of order s_0 at 1.

./pdf/allouche-shallit-1999.pdf

A more informative observation is used at this level only. For Hin{A,D} put
[
 r_e=delta^2/2,
 nu_H=(Tr(H)-r_edelta_∅)/(1-r_e),
]
where ∅ denotes the empty word. This reserves the same empty-output mass in both block laws. In the proof of Lemma~2.1, steps (I) and (III), Holden and Lyons first erase a mass q^2/2 from 01 blocks at their deletion rate q; the same decomposition is now applied at rate delta to both 01 and 1, followed by an explicit likelihood score.

./pdf/holden-lyons-2020.pdf

For each block independently, the block is silently erased with probability r_e; otherwise a mark is reported with law nu_H. The mark alphabet is
[
 M_{mark}={∅,0,1,01}.
]
An observation on a sequence of blocks is the ordered list of its returning marks, an element of ⊔_{lge0}M_{mark}^l. The list reports its individual entries, including empty-valued entries, but not starting slot labels or period boundaries. Thus the empty list and the one-entry list (∅) are distinct; the count l is the number of entries, not the number of bits in their concatenation. Concatenating the mark strings gives the ordinary trace law, since
[
 Tr(H)=r_edelta_∅+(1-r_e)nu_H .
]

Under nu_{A} define
[
 Z(Y)=frac{nu_{D}}{nu_{A}}-1 .
]
The defect law is dominated by the ordinary-block law. Its support lies in {∅,1}, where the likelihood ratios are
[
 (delta-delta^2/2)/(delta^2/2)quadandqua1/delta,
]
respectively. Hence Z is centred, |Z|_∞=O(delta^{-1}), and |Z|_{L^2(nu_{A}}^2lesssimdelta^{-1}, uniformly for deltale1/2.

Take 1le ule m periods with fixed types b=(b_1,...,b_u)b=(b_1,...,b_u)in{-1,0,1}^u. There are n_b=um slots, and the defect in period j sits at
[
 p_{b}b(j)=(j-1)m+floor( m/2)+b_j .
]
The return count has law Bin(n_b,1-r_e), independent of b.b. Conditional on any 0le lle n_b, the returning subset S_l is uniform among the size-l subsets of {1,...,n_b}. This subset is not reported. If pin S_l, write rk_{S_l}(p) for its rank in the increasing order on S_l. Put Q_l=nu_{A}{ ⊗  l}, with Q_0 the point mass on the empty list. Relative to Q_l, the density of the reported list Y=(Y_1,...,Y_l) is
[
 G_{b}b^{(u,l)}(Y)
 =E_{S_l}prod_{{j:,p_{b}b(j)in S_l}}
 (1+Z(Y_{rk_{S_l}(p_{b}b(j))})).
]
Empty products are 1, so this also defines the density at l=0. It integrates to one because each 1+Z has mean one under nu_{A} To expand it, fix 1le rle u and take an increasing tagged tuple j=(j_1,...,j_r)j=(j_1,...,j_r) of periods and an increasing rank tuple 1le v_1<...<v_rle l. Write p_h=p_{b}b(j_h) and put
[

 W_{j,j,b}b(v)
 &=Probbigl{p_hin S_l, rk_{S_l}(p_h)=v_h for every hbigr},
 A_{r,b}b(v)&=sum_{1le j_1<...<j_rle u}W_{j,j,b}b(v).

]
The event defining W_{j,j,b}b imposes no restriction on untagged slots, including other defects. It is the joint probability of the tagged returns and ranks within the count conditioning, not a rank law conditioned on all tags returning. Expanding the product gives
[
 G_{b}b^{(u,l)}(Y)=1+sum_{r=1}^{u}sum_{1le v_1<...<v_rle l}
 A_{r,b}b(v)prod_{h=1}^r Z(Y_{v_h}) .
]

Define the slot gaps and rank gaps by
[

 (g_0,...,g_r)&=(p_1-1,,p_2-p_1-1,...,p_r-p_{r-1}-1,,n_b-p_r),
 (z_0,...,z_r)&=(v_1-1,,v_2-v_1-1,...,v_r-v_{r-1}-1,,l-v_r).

]
Their sums are n_b-r and l-r. Put theta=l/n_b and f_g(z)=Prob{Bin(g,theta)=z}. Counting returning untagged slots in each gap gives the exact kernel
[
 W_{j,j,b}b(v)=frac{prod_{i=0}^rbinom{g_i}{z_i}}{binom{n_b}{l}}
 =frac{theta^r}{f_{n_b}(l)}prod_{i=0}^r f_{g_i}(z_i).
]
Set f_g(z)=0 outside zin{0,...,g}. The last expression represents the same uniform subset by independent Bernoulli-theta sampling conditioned on its total, including the degenerate laws at theta=0,1. The actual erasure rate stays r_e. Call a count admissible when
[
 theta=(l)/(n_b)in[1-delta^2,1-delta^2/4].
]
For a tagged tuple define the coarse gaps
[
 gamma_0=j_1-1/2,
 gamma_i=j_{i+1}-j_i (1le i<r),
 gamma_r=u-j_r+1/2 .
]
These sum to u, and g_i=mgamma_i+alpha_i with |alpha_i|le3. End coarse gaps are positive half-integers and internal coarse gaps are positive integers. In particular g_igtrsim m. At an admissible count, the expected binomial success and failure counts tend to infinity uniformly by mdelta^2to∞.

[Rank-kernel square sum]
For the u-period construction and admissible count above, and for every 1le rle u,
[
 |A_{r,b}b|_{ell^2}^2
 le(C_3/delta)^r(u/m)^{r/2}r^{-r/2},
]
where ell^2 uses counting measure on increasing rank tuples and C_3 is absolute, uniformly in the deterministic period types and the admissible count.

Proof. 
Fix u,l,b;b; all kernels share theta and f_{n_b}(l). In an inner product both kernels use the same rank tuple v, hence the same rank-gap vector z(v). The correspondence between increasing v and nonnegative z with sum l-r gives
[
 < W_{j,j,b}b,W_{j',j',b}b>
 =frac{theta^{2r}}{f_{n_b}(l)^2}
  sum_{substack{z_ige0sum_i z_i=l-r}}
  prod_{i=0}^{r}f_{g_i}(z_i)f_{g_i'}(z_i).
]
Choose a largest gamma_e in the first tuple, breaking ties by the least index. Then g_egtrsim mu/(r+1). Solve the total constraint for z_e, bound that factor by its supremum, and drop the constraints on the remaining coordinates:
[
 < W_{j,j,b}b,W_{j',j',b}b>
 lefrac{theta^{2r}}{f_{n_b}(l)^2}
  sup_z f_{g_e}(z)f_{g_e'}(z)
  prod_{ine e}sum_z f_{g_i}(z)f_{g_i'}(z).
]
No multiplicity is introduced when z_e is solved.

For each free coordinate the following holds with absolute positive constants:
[
 sum_z f_g(z)f_{g'}(z)
 le (C_{rk}/delta)g^{-1/2}
  exp!(-c_{rk}((g-g')^2)/(g+g')).
]
To see this, regard the sum as the probability that the difference of two independent binomials is zero. Tilt their product law by e^{t,difference} with t=-e_0(g-g')/(g+g') and a sufficiently small absolute e_0>0. The log moment is theta t(g-g')+O(t^2(g+g'))le-c_{rk}(g-g')^2/(g+g'), since thetage1/2. Under the tilt independence is preserved, the Bernoulli odds are multiplied by e^{pm t}, and the failure probabilities remain comparable to delta^2. The probability of zero under this tilted law is at most the first binomial's maximum mass O((deltasqrt g)^{-1}).

Corresponding coarse-gap coordinates have integer differences. Since g_i=mgamma_i+O(1) with an absolute error, for a nonzero mismatch and all large m,
[
 |g_i-g_i'|ge1/2m|gamma_i-gamma_i'|,
 g_i+g_i'lesssim mu,
 g_igtrsim mgamma_i.
]
For a matching coordinate the exponential equals 1. Substituting these comparisons and using theta^{2r}le1 yields
[
 < W_{j,j,b}b,W_{j',j',b}b>
 le C_{rk}(r+1)prod_{ine e}Bigl[
  frac{C_{rk}}{delta√(mgamma_i)}
  exp!(-c_{rk}(m(gamma_i-gamma_i')^2)/(u))Bigr].
]
It remains to sum over both tagged tuples. Once the other coarse gaps are fixed, the constraint sum_igamma_i=u determines the eliminated gap; the same holds for gamma'. For fixed gamma, dropping validity of the determined gamma_e' can only enlarge the sum, and
[
 sum_{gamma'}prod_{ine e}e^{-c_{rk}m(gamma_i-gamma_i')^2/u}
 leprod_{ine e}sum_{zinZ}{-c_{rk}(m/u)z^2}
 le C_{rk}^r
]
because mge u. Thus the remaining r first-tuple coordinates contribute m^{-r/2} times a sum of prod_{ine e}gamma_i^{-1/2} with their total at most u. With tau=r/uin(0,1],
[
 sum_{sum_{ine e}gamma_ile u}prod_{ine e}gamma_i^{-1/2}
 le e^{tau u}prod_{ine e}sum_{gamma_i>0}gamma_i^{-1/2}e^{-taugamma_i}
 le C_{rk}^r(u/r)^{r/2}.
]
The last lattice sum is O(tau^{-1/2}) on both the positive-integer and positive-half-integer lattices, by comparison with the integral of x^{-1/2}e^{-tau x/2}. Finally sum over the r+1 possible selected coordinates e. The resulting O((r+1)^2) factor is absorbed into a constant to the power r. Since |A_{r,b}b|_2^2 is the sum of these inner products, the lemma follows.


Two gap-sum ineualities are used repeatedly. For 1le hle r and an integer j put
[
 Σ_{r,h}(j)=√(Km)sum_{substack{1le j_1<...<j_rle Kj_h=j}}prod_{i=0}^r(mgamma_i)^{-1/2}.
]
For rge2, let Σ_{r,h}^{bd}(j) be the same sum restricted to tuples with gamma_ile|I| for some 1le i<r.

[Gap sums at a fixed period]
For fixed 1le r<R_0, uniformly in h and jin[K/3,2K/3],
[
 Σ_{r,h}(j)le C_r(Km)^{-1/2}lambda^{r-1},
 Σ_{r,h}^{bd}(j)
 le C_{r,s_0}(Km)^{-1/2}m^{-1/2}lambda^{r-2}(rge2).
]

Proof. 
The left gaps 0,...,h-1 sum to j-1/2 and the right gaps h,...,r sum to K-j+1/2. Each total is order K. Select a largest gap on each side; both are at least c_rK, so their two factors cost C_r(Km)^{-1}. Given j and the other r-1 gaps, the two total constraints determine the selected gaps. Each remaining free sum costs
[
 sum_{substack{gamma>0gammale K}}(mgamma)^{-1/2}
 le C_*√(K/m)=C_*lambda
]
on either lattice. Grouping by the at most C_r choices of selected gaps and multiplying by √(Km) proves the first bound.

For the restricted sum, an internal gap at most |I| is neither selected largest gap for all sufficiently large K. Union over its at most r-1 possible indices. Its sum is at most sum_{gamma=1}^{|I|}(mgamma)^{-1/2}le C_{s_0}m^{-1/2} instead of C_*lambda. The other r-2 free sums are unchanged, proving the second bound.


The rank estimate first gives common mass at the working deletion rate. This mass later conceals the side orientations that move the exceptional periods as a group. For u=k,k+1, write G^{(u,l)}=G_{mathbf0}0^{(u,l)} for the conditional density of the list from W_0^u. At a count l admissible for both totals, the two densities share the same Q_l, though their respective parameters are theta=l/(um). Orthogonality of distinct multilinear monomials in the independent centred scores gives
[
 E_{Q_l}[(G^{(u,l)})^2]
 =1+sum_{r=1}^{u}|A_{r,mathbf0}0|_2^2|Z|_2^{2r}
 le1+sum_{rge1}
 (C_6delta^{-2}√(u/m))^r r^{-r/2}
 leexp(C_6'Λ).
]
Indeed, for age0, sum_{rge1}(a/sqrt r)^rleexp(C_*(1+a^2)): for r>4a^2 the terms are at most 2^{-r}; for 1le rle4a^2, the maximum of rlog(a/sqrt r) over positive reals is at most a^2/(2e). Since delta^{-4}u/mlesssimdelta^{-3} at both side counts.

The count laws overlap on
[
 |l-(1-r_e)km|le m .
]
For either n_b=km or n_b=(k+1)m, every such count is admissible for all large instances: its distance from the corresponding mean is at most 2m, and m/n_basymp1/(delta m)=o(delta^2). Stirling's formula gives mass per count at least
[
 c_7(delta√(n_b))^{-1}
 exp!(-C_7(m^2)/(delta^2n_b))
 ge m^{-1}exp(-C_8Λ)
]
for absolute positive constants. One way to see the exponent: the relative entropy between Ber(l/n_b) and Ber(1-r_e) is at most a constant times (l/n_b-(1-r_e))^2/delta^2, while
[
 (l/n_b)(1-l/n_b)n_basympdelta^2n_basympdelta^3m^2→∞ .
]
There are at least m integer counts in this interval. Summing the conditional overlap bounds with the lesser of the two count probabilities gives, for a sufficiently large absolute C_9, overlap at least
[
 omega=exp(-C_9Λ)<1/8
]
between the mark-list laws of W_0^k and W_0^{k+1}. Their ordinary trace laws have at least the same overlap by concatenation. Choose C=max{C_{abs}/omega,9/delta}, so Cdelta>8 and log C=O(Λ).

The common-mass construction of the tools section involves one joint flag of probability omega^2 per pair of chunks: on it, the two chunk outputs are drawn from a common sublaw omega U (so the orientation is hidden), and on its complement the fair bit is revealed and the pair is drawn from the normalised residual after subtracting omega^2 U ⊗  U from the product law for that orientation. Marginalising the flags reproduces the conditionally independent pair traces given the orientation, and conditional on the augmented data the bit remains fair on the hidden event.

./pdf/holden-lyons-2020.pdf
./pdf/mcgregor-price-vorotnikova-2014.pdf

Use the common mass for the mark-list laws. Draw J independent fair bits E_1,...,E_J. Pair a run of k+E_i periods before a central run of K periods with a run of k+1-E_i periods after it; use a fixed order for the runs on each side. The number of periods before the central run is
[
 L_{left}=Jk+sum_{i=1}^J E_i .
]
For every schedule the exceptional global period a+i has central index X+i, where
[
 X=a-L_{left}
 =Big⌊((J+K)/(2))-sum_{i=1}^J E_i
 =K/2+O(J+1).
]

Since J=o(K) and |I| is fixed, all exceptional periods lie in the central run for every schedule. Thus each schedule cuts the same prescribed word into pure side runs and a central run with the indicated translated types.

Apply the paired flag construction on each pair of side mark-list laws, with a common sublaw omega U on the list space. Report the flag and both lists; report the orientation bit only on the visible flag. Report one ordered list of individual marks from the central run, without period boundaries or starting slot labels.

Extend beta_i by zero outside I and define the central type vectors by (b_pm(X))_j=pmbeta_{j-X}. Conditional on the report d,d, the central densities and coefficient arrays are
[

 G_pm^{d}d&=E_{Xsimpi_{d}d}G_{b_pm(X)}^{(K,l)},
 &A_{r,pm}^{d}d&=E_{Xsimpi_{d}d}A_{r,b_pm(X)},
 G_{pure}^{d}d&=G_{mathbf0}0^{(K,l)},
 &A_{r,rm pure}^{d}d&=A_{r,mathbf0}0.

]
These densities all integrate to one under Q_l. In particular
[
 P_pm(dd,dY)=Q_frakd,dY)=Q_{meta}(dd)d),G_pm^{d}d(Y)Q_l(dY)
]
with l read from d,d, and the analogous identity holds for P_{pure}. This is the common conditional reference required by Lemma~lem:clipping.

Call metadata typical when
[
 frac l{Km}in[1-delta^2,1-delta^2/4], Mgeomega^2J/2 .
]
The first failure is a multiplicative binomial tail for the central erasures; the second is one for the independent hidden flags. The scale margins make both negligible at the required final-length budget:
[
 (d_D+B+1)log n=N^{o(ε)},
 delta^2Km=N^{1-3eta-o(1)},
 omega^2J=N^{2eta-o(1)} .
]
Both Chernoff exponents therefore dominate logDelta^{-1}=100(d_D+B+1)log n, and atypical metadata have mass o(Delta).

Fix typical metadata for the remainder of the coefficient analysis and suppress the superscript d.d. Put lambda=√(K/m)=N^{-eta/2+o(1)}. For a fixed central type vector, Lemmas~lem:base-kernel and~lem:moment give
[
 Bigl|sum_{1le v_1<...<v_rle l}A_{r,b}b(v)prod_{h=1}^r Z(Y_{v_h})Bigr|_{r_0}
 le(C_*r_0delta^{-3/2}sqrtlambda)^r r^{-r/4} .
]
One has |Z|_{r_0}lesssimdelta^{-1} and r_0,delta^{-1}=N^{o(1)}. The factor in parentheses is N^{-eta/4+o(1)}=N^{-.001+o(1)}. Put R_0=3000 and, for each of the three densities, write G_{ge R_0} for the sum of its homogeneous terms of degrees at least R_0. Geometric summation, followed by Minkowski's ineuality when mixing over X, gives
[
 |G-1|_{r_0}le N^{-.0009},
 |G_{ge R_0}|_{r_0}le N^{-2.3} .
]
The growing r_0 is a moment order; R_0 is a fixed degree cutoff. It remains to estimate the differences of their finitely many lower-degree arrays.

The coefficient differences B_r=A_{r,+}-A_{r,-} and B_r^{pure}=A_{r,+}-A_{r,rm pure} are evaluated. The next lemma completes the algebra and the higher-degree bootstrapping.

Define the seed-motif indicator on the integers by chi_{seed}(i)=1_bf1_{{iin I}}. The rank event depends on the type vector only through its tagged positions, so for a fixed X,
[
 W_{j,j,b_pm(X)}=prod_{h=1}^r T_h^{(b_pm(X))_{j_h}}W_{j}j.
]
Each shift factor is exactly
[
 T_h^{(b_pm(X))_{j_h}}
 =1+chi_{seed}(j_h-X)V_hpmbeta_{j_h-X}D_h .
]
For disjoint D,V⊆V⊆{1,...,r} write
[
 c_{j}j^{D,V}
 =E_X[prod_{hinD}{j_h-X}prod_{hinV}{seed}(j_h-X)Bigr],
 
 ∂_{D,V}{hinD}{hinV} .
]
Throughout, sum_{j}j runs over 1le j_1<...<j_rle K. Expanding the shift factors gives
[
 B_r=2{substack{D V=∅V=∅ |D|D| odd}}
  sum_{j}jc_{j}j^{D,V}∂_{D,V}{j}j.
]
The factor 2 records root types tau_∅=pm1; the oddness restriction records cancellation of all even-valued root patterns under subtraction. For B_r^{pure} the same expansion runs over all nonempty patterns, without the oddness restriction or the factor 2. These are finite sums of C_r patterns because r<R_0 is fixed.

Within the increasing rank tuples 1le v_1<...<v_rle l define
[
 R_{j}j={v:|z_i(v)-theta mgamma_i|<m/8 for 0le i<r}.
]
These regions are disjoint: the first and internal coarse gaps determine the tuple, and any differing coordinate changes its center by at least theta mge3m/4, more than the combined radii m/4. Bounded shifts of a kernel use the same region.

Fix one pattern and abbreviate its multiplier and operator by c_{j}j and ∂. Disjointness gives the weighted identity
[
 Bigl|sum_{j}j1_bf1_{R_{j}j}c_{j}j∂ W_{j}jBigr|_2^2
 =sum_{j}j|c_{j}j|^2|1_bf1_{R_{j}j}∂ W_{j}j|_2^2
 lesum_{j}j|c_{j}j|^2|∂ W_{j}j|_2^2.
]
The part outside these regions is negligible as an analytic coefficient estimate. To see this, expand D_h,V_h directly into tag shifts T_h, which preserve the total Km. Each resulting term is a fixed signed coefficient times a nonnegative shifted rank kernel. For each such kernel in ∂ W_{j}j, the conditional binomial formula and Hoeffding's ineuality give
[
 sum_{vnotin R_{j}j}W_{j,j,{shift}}(v)
 le C_r f_{Km}(l)^{-1}e^{-c_* m/K}
 le C_r√(Km),e^{-c_* m/K} .
]
A bounded shift changes each relevant mean by O_r(1), while the excluded deviation is order m, and each gap has length at most Km+O_r(1). Dropping the total constraint and taking a union bound over i<r proves the display. There are at most K^r tuples, the multiplier is bounded by 1, and ∂ is a fixed linear combination of shifted kernels. Using |·|_2le|·|_1 for coefficient arrays, the discarded array has ell^2 norm at most
[
 tau_r=C_rK^r√(Km),e^{-c_* m/K}.
]
Thus the squared norm of the full array for this pattern is at most
[
 2sum_{j}j|c_{j}j|^2|∂ W_{j}j|_2^2+2tau_r^2 .
]
This restriction does not condition a reported law or incur a total-variation error. Since m/K=N^{eta+o(1)}, even (C_*r_0delta^{-1})^rtau_r=o(N^{-A}) for every fixed A, uniformly over the finitely many r<R_0.

./pdf/hoeffding-1963.pdf

Two arithmetic bounds remain. One bounds the effect of the length-difference operators D_h,V_h on a rank kernel; the other bounds the two location multipliers that carry the signed pattern and the seed support.

[Finite differences of a rank kernel]
Fix 1le r<R_0, an admissible central count, and a tagged tuple in K periods with coarse gaps gamma_i. For disjoint D,V⊆V⊆{1,...,r} put v'=|D|+2|D|+2|V|.V|. Then
[
 Bigl|prod_{hinD}{hinV},W_{j}jBigr|_{ell^2}^2
 ledelta^{-O_r(1)}√(Km),m^{-v'}prod_{i=0}^r(mgamma_i)^{-1/2}.
]
The implicit constants depend only on r.

Proof. 
Let S_i increase the length of gap i in the numerator of the rank-kernel formula. Since T_h=S_{h-1}S_h^{-1},
[
 D_h=1/2(T_h-1)(1+T_h^{-1}),
 V_h=1/2(T_h-1)^2T_h^{-1},
 T_h-1=(S_{h-1}-1)S_h^{-1}+(S_h^{-1}-1).
]
Also S_i^{-1}-1=-(S_i-1)S_i^{-1}. Expanding assigns exactly v' first length differences to gaps, with C_r terms and shifts of their lengths by O_r(1). For an assigned term write b_i for the order on gap i; then sum_i b_i=v'.

Write (nabla f)_g=f_{g+1}-f_g. At an integer length gge1, the order-b difference (nabla^b f)_g has Fourier transform theta^b(e^{it}-1)^b(1-theta+theta e^{it})^g. On [-pi,pi] the last factor has modulus at most exp(-c_*delta^2gt^2), since theta(1-theta)gtrsimdelta^2. Parseval and Fourier inversion give
[
 |(nabla^b f)_g|_2^2le C_bdelta^{-(2b+1)}g^{-b-1/2},
 |(nabla^b f)_g|_∞^2le C_bdelta^{-(2b+2)}g^{-b-1}.
]
All shifted lengths are comparable to g_i for large m, since r is fixed and g_igtrsim m.

Choose a largest coarse gap e, so its shifted length widetilde g_egtrsim_rKm. In the squared rank sum, solve for z_e and use the squared supremum there, with squared ell^2 sums on the other r gaps. For one assigned term F, the displayed bounds and f_{Km}(l)^{-2}lesssimdelta^2Km give
[
 |F|_2^2
 le C_rdelta^{-(2v'+r)}Km,widetilde g_e^{-1-b_e}prod_{ine e}widetilde g_i^{-1/2-b_i}
 le C_rdelta^{-(2v'+r)}√(Km),m^{-v'}prod_{i=0}^r(mgamma_i)^{-1/2}.
]
The second line uses widetilde g_igtrsim mgamma_i and sum b_i=v'. Shifts preserve the power up to delta^{-O_r(1)}. Summing the C_r assigned terms proves the display.


For the location multipliers, (eq:base-anchor) shows that every jinsupp(chi_{seed}*pi) satisfies j=K/2+O(J+|I|), hence lies in [K/3,2K/3] for all large instances. Lemma~lem:base-fixed-sums therefore applies to every involved period. For a sequence a on the integers use the Fourier transform ahat(t)=a(t)=sum_j a(j)e^{ijt}. If Mgeomega^2J/2 is the hidden count, then
[
 |pihat(t)|=|cos(t/2)|^Mle e^{-c_*Mt^2}(-pile tlepi).
]
Since
[
 |sum_{iin I}beta_ie^{iti}|=|prod_{v=0}^{s_0-1}(1-e^{i2^vt})|le C_{s_0}|t|^{s_0},
]
Parseval and the binomial decay give
[
 |beta*pi|_2^2le C_{s_0}M^{-s_0-1/2}le C_{s_0}omega^{-2s_0-1}J^{-s_0-1/2},
 
 |chi_{seed}*pi|_2^2le|chi_{seed}|_1^2|pi|_2^2le C_{s_0}M^{-1/2}le C_{s_0}omega^{-1}J^{-1/2}.
]

./pdf/hmpw-2008.pdf

The dyadic signs turn convolution into a high-order finite difference. The same cancellation algebra appears in Section~3.2 of Holenstein, Mitzenmacher, Panigrahy, and Wieder, where iterated input-position differences act on a mean-coordinate binomial kernel.

./pdf/hmpw-2008.pdf

In the pattern expansion a singleton D={h},V=∅V=∅ has v'=1 and multiplier (beta*pi)(j_h). Every other surviving pattern has an odd positive number of D's, so v'ge3 and at least two indices are involved. At any chosen involved h,
[
 |c_{j}j^{D,V}|le(chi_{seed}*pi)(j_h).
]
A nonzero multiplier requires all involved periods to lie in a common translate of I. Two of them therefore differ by at most |I|-1, so some intervening internal gap is at most |I|.

For either kind of pattern choose such an involved h, and let psi(j) be the corresponding envelope, either |(beta*pi)(j)| or (chi_{seed}*pi)(j). Lemma~lem:base-differences and a first sum over tuples with j_h=j give
[
 sum_{j}j|c_{j}j|^2|∂ W_{j}j|_2^2
 ledelta^{-O_r(1)}m^{-v'}sum_jpsi(j)^2
 
  Σ_{r,h}(j),&for a singleton,
  Σ_{r,h}^{bd}(j),&otherwise.
 
]

Lemma~lem:base-fixed-sums and the two multiplier norms apply. Combining the finitely many patterns in the expansion and the analytic tail gives
[

 |B_r|_2^2le C_{r,s_0}delta^{-O_r(1)}Bigl[
 &omega^{-2s_0-1}J^{-s_0-1/2}m^{-1}(Km)^{-1/2}lambda^{r-1}
 &+1_bf1_{rge2},omega^{-1}J^{-1/2}(Km)^{-1/2}m^{-7/2}lambda^{r-2}Bigr]
 +C_rtau_r^2 .

]
The nonlinear m^{-7/2} comes from m^{-3} at the minimum difference order together with m^{-1/2} from the bounded internal gap. For B_r^{pure}, the singleton D contribution is the same. Every other pattern has v'ge2, but a singleton V requires no bounded internal gap. The full pure-comparison array therefore satisfies
[

 |B_r^{pure}|_2^2le C_{r,s_0}delta^{-O_r(1)}Bigl[
 &omega^{-2s_0-1}J^{-s_0-1/2}m^{-1}(Km)^{-1/2}lambda^{r-1}
 &+omega^{-1}J^{-1/2}(Km)^{-1/2}m^{-2}lambda^{r-1}Bigr]
 +C_rtau_r^2 .

]
For each fixed r<R_0, Lemma~lem:moment converts the coefficient estimate to a score estimate:
[
 Bigl|sum_{1le v_1<...<v_rle l}B_r(v){h=1}^r Z(Y_{v_h})Bigr|_{r_0}^2
 le(C_1r_0|Z|_{r_0})^{2r}|B_r|_2^2 .
]
The analogous ineuality applies to the pure comparison. The fixed pattern constants, the displayed powers of delta^{-1} and omega^{-1}, and the moment factors are N^{o(1)}: use log r_0=O_B(D+1), logomega^{-1}=O(Λ), and Λ=o(log N). The analytic tails remain smaller than every fixed power after these factors.

The worst nonlinear term of the first display, at r=2, is
[
 J^{-1/2}(Km)^{-1/2}m^{-7/2}
 =N^{-eta},N^{-1/2+3eta/2},N^{-7/4+7eta/2+o(1)}
 =N^{-9/4+4eta+o(1)}=N^{-2.234+o(1)} .
]
The singleton term is N^{-3.394+o(1)} at its worst degree r=1. The worst nonlinear term in the second display is N^{-3/2+5eta/2+o(1)}=N^{-1.49+o(1)}. Summing over the finitely many lower degrees and adding the degree tails gives, on every typical metadata value,
[
 |G_+-G_-|_{r_0}^2le N^{-2.22},
 |G_+-G_{pure}|_{r_0}^2le N^{-1.4} .
]

Let A be the joint event of typical metadata and G_+^{d}d(Y)ge1/2, and define
[
 mu_0=P_+(,·midA), nu_0=P_-(,·midA).
]
Lemma~lem:clipping applies to the common conditional reference. The high-degree estimates supply rho=.0009ge2^{-4B-10}, and 2.22>2.20+.01 supplies its difference margin. Hence
[
 nu_0llmu_0,
 |dnu_0/dmu_0-1|_{L^{r_0}(mu_0)}^2le N^{-2.20},
]
and conditioning changes each preliminary law by o(Delta) in total variation. By contraction under the same K_0,
[
 TV(K_0,Tr(x_0))le o(Delta)leDelta,
 TV(K_0,Tr(y_0))le o(Delta)leDelta
]
for all large instances. This gives E_0leDelta and the score part of the invariant. The hidden-bit law was used for the preliminary densities only.

It remains to transfer pure-run overlap to x_0. This comparison uses the preliminary laws rather than the full clipping conclusion, because the pure comparison only loses N^{-1.4}. On typical metadata and G_+ge1/2,
[
 (√(G_+)-sqrt{G_{pure}})^2le2|G_+-G_{pure}|^2.
]
On the complement use G_++G_{pure}. The high-moment estimate and the clipping proof bound the mass of the bad-density region under both preliminary laws by o(Delta); atypical metadata have the same bound. Hence
[
 H^2(P_+,P_{pure})le2N^{-1.4}+o(Delta)le3N^{-1.4}.
]
Projection by K_0 gives the same bound for H^2(Tr(x_0),Tr(W_0^P)).

Set k_0=lceil CkPrceil, where k=floor(delta m) is the seed count. Since ksimdelta m and Cdelta>8, one has k_0geell_0 for all large instances. Also,
[
 (k_0)/(ell_0)le(Cdelta m)/(2m-1)+frac1{ell_0}<C,
]
using deltale1/2, Cge18, and ell_0to∞. Thus the common choice M_B=1 meets the level-zero count predicate, and C=exp(O(Λ))=N^{o(1)}. For F=k_0,k_0+1, tensorization followed by concatenation gives
[
 TV(Tr(x_0^F),Tr(W_0^{PF}))
 le√(F,H^2(Tr(x_0),Tr(W_0^P)))
 lesqrt{3F N^{-1.4}}=N^{-0.2+o(1)}=o(1).
]
Lemma~lem:lift, applied to the base word W_0 with overlap count k, replication P, and F=k_0, gives pure overlap at least 2/3 for the two repeated comparison words. Paying the two replacement costs leaves
[
 ov(Tr(x_0^{k_0}),Tr(x_0^{k_0+1}))ge2/3-o(1)geomega.
]
Together with the length, distinction, score, and simulation estimates, this completes Proposition~prop:initial.

[One amplification block]
For the scale parameters, let 1le ile D and suppose a level-(i-1) pair satisfies Definition~def:invariant with constants C,omega,M_B. Set
[
 C'=max{C,C_{abs}/omega}.
]
The input pair remains valid with C replaced by C', and there exists a level-i pair satisfying the definition with the same constants C',omega,M_B, with
[
 d_i=d_{i-1}+(b_i-1)/4-.05, E_ileDelta+(ell_i/ell_{i-1})E_{i-1}.
]
Every preceding level constructed with C also remains valid with C', and this enlarged value is retained in later blocks. All conclusions are uniform over levels along the stated joint asymptotic regime.

Proof. 
Fix i. The value C' meets the hypothesis of Lemma~lem:lift. Every preceding upper count bound remains true after replacing C by C', since its exponent 2Bh+M_B at a level hge0 is nonnegative; the lower count bounds, scores, and projection errors do not involve C. The enlarged constant depends only on delta and satisfies log C'=O(Λ). Write C for C' and use this common enlarged constant in the counts constructed and in later blocks.

Abbreviate
[
 b=b_i, N=N_i, d=d_{i-1}, d'=d_i,
 x=x_{i-1}, y=y_{i-1}, ell=ell_{i-1}, k=k_{i-1}.
]
Within this block write a_0=a_0(b) for the contraction exponent defined by a_0(b)=(1+ε)2^{-b}-ε. Thus ellin[N^{a_0}/2,N^{a_0}]. Since r_ile r_{i-1}, the old score satisfies
[
 Bigl|frac{dnu_{i-1}}{dmu_{i-1}}-1Bigr|_{L^{r_i}(mu_{i-1})}^2le N^{-a_0d}.
]

The two new words use the same nested motif at b depths. Choose the fixed degree cutoff and the cancellation order
[
 r_*=2^{10B+40},
 s_*=Bigllceil100(d_D+r_*+B+10)/εBigrrceil,
  L=2^{s_*}.
]
Let I={0,...,L-1} and define the signs by
[
 sum_{ainI} z^a=prod_{v=0}^{s_*-1}(1-z^{2^v}).
]
Extend sigma_a by zero outside I and put chi=1_bf1_{I} The order s_*=O_B((D+1)^2) is large enough for the signed smoothing at every block. Lemma~lem:scale-margins gives, uniformly,
[
 L^{O_B(r_*B)}=N^{o(ε)},
 exp(O_B((s_*+1)^2+(s_*+1)(D+1)Λ))=N^{o(ε)}.
]
Start with U_0^+=x, U_0^-=y, both of length S_0=ell, and with overlap count h_0=k. Once a positive integer P_j has been chosen, form U_j^tau, tauin{+1,-1}, from P_j consecutive level-(j-1) atoms. Use type + except at the labels floor( P_j/2)+a, ainI, where the type is tausigma_a. The counts ensure these labels lie in [1,P_j]. The common length is S_j=P_jS_{j-1}. The two words are distinct: at a motif label their atom types differ, and equal-length atoms give a fixed parse back to the distinct old words.

Write N^{a_j} for the target length of a level-j word. It then contains about N^{a_j-a_{j-1}} lower atoms. An overlap chunk contains h_{j-1} such atoms, with h_{j-1} within the controlled channel factor of their word length N^{a_{j-1}}. To leave about N^ε paired chunks, choose the remaining exponents by
[
 a_j(b)=2a_{j-1}(b)+ε (1le jle b).
]
This recurrence and the definition of a_0(b) give
[
 a_j(b)=(1+ε)2^{j-b}-εquad(0le jle b), a_b(b)=1.
]
In the rest of this block a_j abbreviates a_j(b).

A level-j child window contains T_j level-(j-1) atoms. Define
[
 kappa_j=a_{j-1}-3(2^j-1)ε,
 T_j=4Big⌊( N^{kappa_j}/4) (1le jle b).
]
The kappa_j are positive for all sufficiently large instances, uniformly in the block. Directly from the exponents,
[

 2kappa_j-kappa_{j+1}-ε&=εquad(1le j<b),
 kappa_b&>ε,
 kappa_j<a_{j-1}<a_j-a_{j-1}(1le jle b).

]
The first identity makes T_j larger than the typical displacement from T_{j+1} collections of about N^ε fair bits: the squared window width divided by that bit count has order N^ε. The remaining ineualities leave room for the windows inside their words. Also
[
 sum_{j=1}^bkappa_j<1,
]
since kappa_j<a_{j-1}<2^{j-1-b}; this bounds the number of vertices in the observation tree.

For 1le j<b choose
[
 P_j=Big⌊( N^{a_j}/S_{j-1}),
 h_j=lceil Ch_{j-1}P_jrceil,
 t_j=2Big⌊( P_j/[100(2h_{j-1}+1)]) .
]
For the root choose
[
 J=Big⌊(frac{floor( N/S_{b-1})-T_b}{2h_{b-1}+1}),
 P_b=J(2h_{b-1}+1)+T_b,
 h_b=lceil Ch_{b-1}P_brceil.
]
The counts t_j and J are the numbers of paired chunks used for local and outer displacements. The factors 2 and 4 in their definitions and in T_j ensure the parity and divisibility required by the partition.

For j<b, flooring loses at most S_{j-1}=o(N^{a_j}), so
[
 S_jin[N^{a_j}/2,N^{a_j}],
 P_jasymp N^{a_j-a_{j-1}}, T_j=o(P_j).
]
The overlap counts remain within the declared uniform bound. Indeed h_jge S_j by induction, and
[
 (h_j)/(S_j)le Cfrac{h_{j-1}}{S_{j-1}}+1le C^2frac{h_{j-1}}{S_{j-1}}
]
because h_{j-1}/S_{j-1}ge1 and C>2. Starting from the level-(i-1) bound gives
[
 S_jle h_jle C^{2B(i-1)+M_B+2j}S_jle C^{2Bi+M_B}S_jquad(0le jle b).
]
In particular the extra count factor is at most exp(O_B((D+1)Λ)).

Substitution in the definitions of t_j and J yields
[
 e^{-O_B((D+1)Λ)}N^εle t_jle O(N^ε)(1le j<b),
]
and the same lower and upper bounds for J. All these counts tend to infinity uniformly. At the root, J=o(T_b) by kappa_b>ε, and
[
 N-S_b=O((h_{b-1}+1)S_{b-1})le N^{2a_{b-1}+o(ε)}=N^{1-ε+o(ε)}=o(N).
]

The count overhead is N^{o(ε)} by the block losses, and 2a_{b-1}=1-ε. Thus also S_bin[N/2,N]. Working backward from kappa_b>ε gives kappa_j>ε at every depth. The uniform loss bound therefore gives L=o(T_j) and L=o(P_j) uniformly, so all motif labels used above fit. Set
[
 x_i=U_b^+, y_i=U_b^-, ell_i=S_b, k_i=h_b.
]

The following estimate quantifies the smoothing supplied by a hidden binomial offset. It is used in the early overlap comparison and in the main score proof. In those applications, the local parameter m is one of the paired counts J or t_j, while g is the actual number of hidden orientation trials.

[Signed binomial smoothing]
Let sigma be the Prouhet--Thue--Morse sequence of order s_*. Suppose pi is an integer translation or reflection of a fair binomial probability mass function with gge c_0omega^2m trials, where c_0>0 is absolute and mto∞ as in the construction. Then
[

 |sigma*pi|_∞&leexp(O((s_*+1)^2+(s_*+1)Λ)),m^{-(s_*+1)/2},
 |sigma*pi|_2^2&leexp(O((s_*+1)^2+(s_*+1)Λ)),m^{-s_*-1/2},
 |pi|_∞&le O(omega^{-1}m^{-1/2}).

]
The norms use counting measure on the integers, and the implicit constants may depend on c_0.

Proof. 
Translations and reflections do not affect the estimates. For the first two, use Fourier inversion and Parseval. On [-pi,pi] the sign transform has modulus at most 2^{s_*(s_*-1)/2}|z|^{s_*}, and the binomial transform has modulus at most e^{-cgz^2}. Gaussian integration contributes, besides the power of g, a factor exp(O((s_*+1)log(s_*+1))). The last estimate is the binomial maximum bound from Stirling's formula.


[Overlap of the nested atoms]
Under the input hypotheses of Proposition~prop:block, the words and counts constructed above satisfy, for every 1le jle b,
[
 ov(Tr((U_j^+)^{h_j}),Tr((U_j^+)^{h_j+1}))geomega.
]

Proof. 
The old score and the two projection errors give
[
 H^2(Tr(x),Tr(y))le O(N^{-a_0d}+E_{i-1}).
]
Indeed the score bounds the squared Hellinger distance of the old oracle laws, and contraction followed by the Hellinger triangle ineuality handles the two projection errors.

The induction on j proceeds from the overlap statement at level j-1; at j=1 it is the input invariant. Lemma~lem:lift, with base word U_{j-1}^+, overlap count h_{j-1}, replication P_j, and F=h_jge Ch_{j-1}P_j, gives overlap at least 2/3 for the two pure comparison words formed by repeating P_j copies of U_{j-1}^+. Replacing one such length-S_j unit by U_j^+ changes at most L lower atoms. For h_j or h_j+1 repeated units, the squared Hellinger replacement cost is therefore at most
[
 (h_j+1)L,H^2(Tr(U_{j-1}^+),Tr(U_{j-1}^-)).
]

The two phases of the depth schedule give the margins needed. From the local exponents and the choice of ε, for b=2 and dge2.20,
[
 a_0d-a_1>.03, 2a_0d>1.06.
]
For i>j_0, one has b=B and dge2^B+2.20, giving
[
 a_0d>1+2^{-B}.
]
Before the ε d correction the first two left sides are at least .05 and 1.10, and the last is at least 1+2.20·2^{-B}. The bound dle2.20+(B/4)D and ε=2^{-4B-100}/(D+1) leave the displayed margins uniformly.

In a block with i>j_0, the two level-(j-1) atoms differ on at most L^{j-1} old atoms. Tensorisation, concatenation, and the old Hellinger bound therefore bound the nested replacement cost by o(1): use a_0d>1+2^{-B}, h_jle e^{O_B((D+1)Λ)}N, L^b=N^{o(ε)}, and E_{i-1}le n(D+1)Delta. In a preliminary block, b=2. At j=1 the same argument uses h_1le e^{O_B((D+1)Λ)}N^{a_1} and a_0d-a_1>.03. At j=2 the sharper comparison
[
 H^2(Tr(U_1^+),Tr(U_1^-))
 le N^{-2a_0d+o(ε)}+O(P_1E_{i-1}+Delta), b=2,
]
is required. The ineuality 2a_0d>1.06 then makes the nested replacement o(1) at the root as well.

For the sharper comparison, report a single window of T_1 separate old oracle outputs. Its nominal start is after A=floor((P_1-T_1)/2) old atoms. Put t_1 paired pure-x chunks before and after the window, with counts h_0+E,h_0+1-E for independent fair bits E. Use the paired flag construction at the input overlap. Complete the two sides by pure-x residuals of counts
[
 A-t_1(h_0+1/2), P_1-T_1-A-t_1(h_0+1/2).
]
These are nonnegative integers. Chunks and residuals have fixed relative IDs and each reports one unseparated ordinary trace, together with its flag and any revealed bit. The window start displacement V is the sum of the t_1 bits minus t_1/2, so |V|le t_1/2=o(T_1). Every motif label therefore lies in the window.

Conditional on the orientation bits, sample the T_1 window outputs independently of one another and of the entire collection of side flags and emissions, using mu_{i-1} for an x atom and nu_{i-1} for a y atom at the corresponding rank. Inside the window, report the old oracle outputs with their relative ranks but not their absolute start or type labels. Apply K_{i-1} independently to these outputs and concatenate in the scheduled order. Given the orientation bits, averaging the flags produces the exact independent trace laws of the other pieces. The common projection therefore approximates the genuine trace with error at most T_1E_{i-1} under either hypothesis.

Except on side metadata of probability o(Delta), at least omega^2t_1/2 orientations are hidden, by binomial concentration and the counting bound on t_1. Conditional on such metadata, V is a translated fair binomial with that many trials. Relative to Q=mu_{i-1}^{ ⊗  T_1}, let G_+,G_- be the conditional densities of the window outputs. For fixed V each is a product of at most L factors 1+Z at distinct positions, averaged over V, where Z is the old score. Lemma~lem:moment gives for its homogeneous degree-r part the squared L^{r_i}(Q) bound
[
 (C_1r_i)^{2r}N^{-a_0dr}binom Lr .
]
Convexity permits averaging over V at the same bound. Geometric summation gives
[
 |G_pm-1|_{r_i}le N^{-a_0d/2+o(ε)},
]
and the squared norm of the terms of degree at least two is at most N^{-2a_0d+o(ε)}. In G_+-G_- the singleton coefficient array is, up to signs, the convolution of sigma with the law of V. The signed smoothing estimate and the counting bound on t_1 make its square sum small enough that
[
 |G_+-G_-|_{r_i}^2le N^{-2a_0d+o(ε)};
]
indeed t_1^{-s_*}le N^{-ε s_*}exp(O_B((D+1)s_*Λ)).

On typical metadata, the region G_+<1/2 has mass o(Delta) under both laws by the same moment argument as in Lemma~lem:clipping. On its complement, the squared density difference bounds Hellinger distance. Adding the atypical metadata and projection errors proves the sharper comparison, with fixed numerical factors absorbed in o(ε). Thus all replacement costs in the nested replacement bound are o(1). The pure overlap 2/3 loses at most the two replacement total variations, and remains above omega<1/8. This completes the overlap induction.


./pdf/hoeffding-1963.pdf
./pdf/holden-lyons-2020.pdf

The surrogate observation is now assembled at each block. It retains the motif information the score proof needs while reporting side data in a form that supports the projection back to a genuine trace. A related auxiliary experiment of Rivkin, Valiant, and Valiant in the probability-vector model exposes a binomially translated middle segment and separately deleted sides; the input is a fixed deterministic word, and the projection is established before any conditioning.

./pdf/rivkin-valiant-valiant-2025.pdf

Use a deterministic tree common to both hypotheses. Its root ∅ is the sole level-b vertex. A level-j vertex has T_j children at level j-1, indexed by appending hin{1,...,T_j} to its own index. Thus an index records positions relative to successive sibling groups. Level-zero vertices are leaves. The entire experiment described is redrawn independently for each observation.

At the root, place a central run of T_b level-(b-1) atoms between J pairs of pure U_{b-1}^+ runs. For each pair use an independent fair bit E, giving counts h_{b-1}+E on the left and h_{b-1}+1-E on the right. Use the paired flag mechanism with hidden probability omega^2 at the overlap proved for the nested atoms. Report one unseparated ordinary trace per side run, its flag, and its orientation bit when revealed. The left runs have a fixed pair-number order before the centre, and the right runs have the corresponding fixed order after it.

The root motif at the word label floor( P_b/2)+a has relative label X+a in this central run, where
[
 X=floor( P_b/2)-Jh_{b-1}-sum E=T_b/2+O(J+1).
]
This is the coordinate of a fixed motif relative to the moving central window. Since J=o(T_b) and L=o(T_b), every X+a, ainI, lies in [T_b/3,2T_b/3] for all orientations and all sufficiently large instances.

Fix 1le j<b and a level-(j+1) vertex G. Its T=T_{j+1} children Gu, 1le ule T, represent a planned consecutive sequence of T level-j units. Partition that sequence into successive parts measured in level-(j-1) atoms. Part u contains a window of T_j atoms for the children of Gu, with nominal pre and post counts
[
 A_j=floor((P_j-T_j)/2), P_j-T_j-A_j .
]
The parts may have different actual lengths, but their total length remains TP_j.

Reserve t_j local pairs in each part. For 1le vle t_j, a fair bit E^{loc}_{u,v} gives a pre chunk of h_{j-1}+E^{loc}_{u,v} pure U_{j-1}^+ atoms and a post chunk of h_{j-1}+1-E^{loc}_{u,v} such atoms. Also reserve global pairs between distant parts. For 1le ale T/4 and 1le vle t_j, a fair bit E^{glob}_{a,v} gives a pre chunk of h_{j-1}+E^{glob}_{a,v} atoms in part a and a post chunk of h_{j-1}+1-E^{glob}_{a,v} atoms in part T+1-a. All these bits are independent.

Treat each reserved chunk as having nominal count h_{j-1}+1/2. Complete every pre and post region to its nominal count by one pure-U_{j-1}^+ filler of deterministic count, and order its chunks and filler by fixed relative IDs. The filler counts are nonnegative, since each region reserves at most 2t_j chunks and the choice of t_j reserves at most P_j/50 atoms, while T_j=o(P_j). These are integers because each reserved collection has the even number t_j of chunks, and a region contains zero, one, or two such collections. Generate each reserved pair of chunks with the joint flag mechanism at the overlap of U_{j-1}^+, and generate each filler as an independent ordinary trace. Each chunk or filler reports one unseparated trace, with flags and revealed bits for paired chunks. The surrogate uses these pure-run laws for every orientation, even when the corresponding locations would not be pure in the true word.

The exact prefix count gives the displacement scales. Define
[

 H_{Gu}&=sum_{v=1}^{t_j}(E^{loc}_{u,v}-1/2),
 V_{Gu}&=sum_{a=1}^{T/4}sum_{v=1}^{t_j}(1_bf1_{ale u}-1_bf1_{T+1-a<u})(E^{glob}_{a,v}-1/2),
 Y_{Gu}&=V_{Gu}+H_{Gu}.

]
Then the number of lower atoms before the window of Gu, counted from the start of the group, is
[
 (u-1)P_j+A_j+Y_{Gu}.
]
A global pre chunk is included when its part a is at or before u, whereas its post chunk is included only when part T+1-a is strictly before u. Completed global pairs cancel. Every earlier local pair has also been completed; only the current local pre chunks contribute H_{Gu}. Each included collection contributes the even number t_j of half-integer deviations, so the displacements are integers. After the last post region all pairs have cancelled, proving the total count TP_j.

For the middle half of the group every global pre chunk has appeared and no global post chunk has appeared. Thus
[
 V_{Gu}=V_G:=sum_{a=1}^{T/4}sum_{v=1}^{t_j}(E^{glob}_{a,v}-1/2)
  when T/4<ule3T/4 .
]
The local sums H_{Gu} are independent across u and independent of the global bits. The global sums outside this interval are partial sums of the same group's bits. Distinct groups and depths use independent mechanisms.

Apply this group partition recursively. The root centre is the first group of T_b planned level-(b-1) units. A window at any later vertex is partitioned into the group for its children by the construction above.

Define type labels for every orientation, starting from tau_∅=+1 or -1 under the two hypotheses. At the root put
[
 tau_h=1-chi(h-X)+sigma_{h-X}tau_∅ .
]
For every other level-j vertex I, jge1, put
[
 tau_{Ih}=1-chi(h-w_j+Y_I)+sigma_{h-w_j+Y_I}tau_I,
  w_j=floor( P_j/2)-A_j=T_j/2.
]
The last equality uses the evenness of T_j. These rules place the motif labels that fit in each window and use type + at its other labels. These define a surrogate even on a failed layout, when an intended motif label falls outside its window; all non-leaf pieces still use the pure laws already specified.

Conditional on all bits, sample the leaf outputs independently of one another and of the entire collection of non-leaf flags and emissions, using law mu_{i-1} for type +1 and nu_{i-1} for type -1. The complete report consists of these separate leaf outputs, all side outputs, flags, and visible bits, with their relative tree and segment IDs. It contains no hidden type labels, absolute word labels, or hidden boundary positions. Let D_0 denote all of this report except the complete old oracle payload at each leaf; any metadata inside an old payload are excluded from D_0.

Let widetildemu_i,widetildenu_i be the two unconditioned surrogate laws. A common kernel K_{tree} applies K_{i-1} independently to every leaf output and concatenates the resulting binary words and side traces in the chronological order specified by the IDs: pre pieces, the recursively ordered window contents, and post pieces in each part, with the outer side runs in their stated order.

Define the fit event, which depends on the orientation bits, by
[
 F={|Y_I|le T_j/8 for every level-j vertex I, 1le j<bbigr}.
]

[Simulation of a genuine trace]
For the unconditioned surrogate laws and the common projection above,
[
 TV(K_{tree}widetildemu_i,Tr(U_b^+))le o(Delta)+(prod_{j=1}^bT_j)E_{i-1},
 
 TV(K_{tree}widetildenu_i,Tr(U_b^-))le o(Delta)+(prod_{j=1}^bT_j)E_{i-1}.
]
All error terms are uniform in i.

Proof. 
By the prefix-offset formula, each Y_I is a centred sum of at most (T_{j+1}+1)t_j independent fair bits with coefficients of magnitude at most one. Hoeffding's ineuality and the scale estimates give
[
 Prob(|Y_I|>T_j/8)le2exp(-c,T_j^2/(T_{j+1}t_j))le2exp(-c'N^ε)
]
for absolute positive constants at all sufficiently large instances. The bound sumkappa_j<1 controls the number of vertices by O_B(N). A union bound therefore gives
[
 Prob(F^c)-N^{ε/2})=o(Delta).
]
The last comparison follows uniformly from Lemma~lem:scale-margins: εlog Ngeεlog N_0 dominates loglog n+log(d_D+B+1), so N^{ε/2} dominates logDelta^{-1}.

./pdf/hoeffding-1963.pdf

A fitting orientation arranges the motif labels of the surrogate inside their intended windows. For each non-leaf vertex the type labels place the motif support exactly as in the true nested word, and for each leaf the type +1 or -1 records the old atom type. Concatenation along the tree, followed by applying K_{i-1} independently at the leaves, produces a product of the old oracle trace laws exactly. The number of leaves is prod_{j=1}^bT_j, and each factor contributes E_{i-1} by tensorised projection error. Adding the failed-layout probability completes the bound.


Fix the block of Proposition~prop:block. For every supported exact value d of the report D_0, write E_{d}d for expectation over the remaining hidden bits with this report fixed. This expectation includes failed layouts; it is not conditioned on F. The report space is countable, so its supported values carry its full law.

Let L be the leaf set and use the conditional reference
[
 Q=mu_{i-1}^{ ⊗ L}
]
For vinL, let Z_v be the old likelihood score at that coordinate. Under Q these variables are independent and centred, with |Z_v|_{r_i}^2le N^{-a_0d} by the old score bound. Conditional on the bits, the leaf of type -1 has density 1+Z_v and the leaf of type +1 has density one. Thus the two conditional surrogate densities are
[
 G_pm=E_{d}dprod_{vinL}+(1-tau_v^pm)/(2)Z_v).
]
For every supported d,d, these densities integrate to one because these are mixtures of product probability laws. The superscript on tau records the root type.

[Conditional score gain]
For every exact typical metadata value d,d, the densities satisfy
[
 |G_+-G_-|_{L^{r_i}(Q)}^2le N^{-d'-.01}.
]
The bound is uniform in d and the block level i.


Fix a typical d for the proof of the lemma.

For fixed bits, every level-one window has at most L negative leaves, because its negative types can occur only on the support of its motif. There are prod_{j=2}^bT_j such windows. This remains true on failed layouts, so the number of factors 1+Z_v in either fixed-bit density is at most Lprod_{j=2}^bT_j. The margin between the old score and this number of possible positions is
[
 lambda_d:=a_0d-sum_{j=2}^bkappa_j>8g_B(d+1), g_B:=2^{-4B-10}.
]
The two depth phases supply this bound. Since sum_{j=2}^bkappa_j<1-2^{1-b} and a_0ge2^{-b}-ε, for b=2 and dge2.20 one has lambda_d>d/4-1/2-ε d; for b=B after the preliminary phase, dge2^B+2.20 and lambda_d>2^{-B}(d-2^B+2)-ε d. In each case the positive part is a fixed positive fraction, depending only on B, of d+1. The choices of g_B and ε leave the bound uniform.

At fixed bits, Lemma~lem:moment bounds the squared L^{r_i}(Q) norm of the homogeneous degree-r part of either density by
[
 (C_1r_i)^{2r}N^{-a_0dr}binom{Lprod_{j=2}^bT_j}{r}
 le(N^{-lambda_d+o(ε)})^r .
]
Convexity permits averaging over the bits at this bound. Geometric summation, using the lower bound on lambda_d, gives
[
 |G_pm-1|_{r_i}le N^{-g_B},
 |degree ge r_* part of G_pm|_{r_i}^2le N^{-d'-1}.
]
For the second ineuality, r_*g_B(d+1)>d'+3 leaves the required margin. Only the fixed degrees 1le r<r_* remain.

Fix such a degree r and a leaf subset S of size r. Its coefficient in G_+-G_- is
[
 c(S)={d}dBigl[prod_{vinS}-tau_v^+)/(2)-prod_{vinS}-tau_v^-)/(2)Bigr].
]
Lemma~lem:moment reduces the squared norm of this degree to
[
 Bigl|sum_{|S|=r}S|=rc(S){vinS}|_{r_i}^2
 le(C_1r_i)^{2r}N^{-a_0dr}sum_{|S|=r}S|=r|c(S)|^2calS)|^2 .
]
To estimate the right side, expand the integrand for fixed bits and fixed relative leaf labels, and only then average each chosen term. Call a vertex occupied if it is an ancestor of a leaf in S, including that leaf itself.

For a vertex I and one of its child labels h, write
[
 xi_{I,h}=h-X,&I=∅, h-w_j+Y_I,&I at level j<b,
  chi_{Ih}=chi(xi_{I,h}), sigma_{Ih}=sigma_{xi_{I,h}} .
]
For an occupied vertex I, let F_I(t) be the contribution of the selected leaves beneath it when its incoming type is tin{-1,1}. At a level-one vertex with m_I selected children, the type rule gives the already-cancelled expression
[
 F_I(t)=2^{-m_I}prod_{h:,IhinS}{Ih}-sigma_{Ih}t).
]
In particular every selected leaf contributes a motif factor. At a higher occupied vertex the selected-leaf product splits across child subtrees, giving
[
 F_I(t)=prod_{h:,Ih occupied}F_{Ih}(1-chi_{Ih}+sigma_{Ih}t), tin{-1,1} .
]
The substituted type is again +1 or -1. No probabilistic independence of the child functions is asserted; this is the factorisation of one product of leaf indicators at fixed bits.

Every function on {-1,1} has an even and an odd part. To retain the individual motif choices, expand the two formulas into terms M_It^{p_I}, reducing powers by t^2=1, where p_Iin{0,1}. At level one choose chi_{Ih} or -sigma_{Ih}t from every selected leaf factor; that leaf is active, and p_I is the parity of the number of signed factors. At a higher vertex choose one term M_{Ih}tau_{Ih}^{p_{Ih}} from each occupied child. If p_{Ih}=0, its contribution is M_{Ih}. If p_{Ih}=1, substitute the type rule and choose one of 1, -chi_{Ih}, or sigma_{Ih}t in M_{Ih}(1-chi_{Ih}+sigma_{Ih}t). The child is active at I when the second or third summand is chosen, and p_I is the parity of the signed summands chosen at I.

Odd and even are roles of these chosen terms, not intrinsic properties of the vertex or of its full coefficient function. At the root, the difference F_∅(+1)-F_∅(-1) keeps exactly the odd terms and gives each a factor two. Apart from bounded scalar factors, a chosen term in the fixed coefficient is therefore the expectation of the product of its active sigma and chi factors.

For fixed r and b, the number of ordered occupied-tree shapes and expansion choices is bounded solely in terms of r,b. A shape specifies adjacency and sibling order, not the numerical child labels. A single shape and its choices can be fixed, the squared coefficient sum over the labels bounded, and the finitely many bounds combined by Cauchy--Schwarz.

That label sum splits into central and noncentral assignments. If an active child of a level-j vertex has label outside [T_j/3,2T_j/3], a nonzero factor requires |Y_I|>T_j/8 for all large instances, since w_j=T_j/2 and L=o(T_j); at the root this is impossible by the outer anchor. Hence such a term has conditional multiplier at most Prob(F^c D_0=d)d)leexp(-N^{ε/4}) in absolute value. There are at most O_B(N^r) label assignments by sumkappa_j<1, so their contribution to the squared coefficient sum is at most N^{-d'-1} eventually. All active child labels in the surviving sum lie in their central intervals. This is a restriction of deterministic label assignments, not conditioning of the bit law. In particular, two forced children of a level-(j+1) parent lie in
[
 [T_{j+1}/3,2T_{j+1}/3]subset(T_{j+1}/4,3T_{j+1}/4),
]
the interval in which their offsets share the global sum.

Suppose a chosen odd term at a vertex I has exactly one active child. The active factor must be signed, since the number of signed factors is odd. All other local choices at that vertex contribute one factor or none.

The relative argument of that factor is local. After the relative IDs and expansion choices are fixed, the local sum H_I occurs among the surrogate arguments xi_{J,h} only when J=I. The local pre/post deviations cancel before any later sibling part. Lower relative arguments use the fresh mechanisms of their own groups. The physical absolute positions of the descendant subtree can move with H_I, but those positions are unreported and do not occur in its lower relative arguments. Likewise X occurs only in root arguments. This does not require independence of child terms, which may share lower global bits.

Condition on every orientation bit except the hidden local bits at I; at the root, keep only its hidden outer bits unconditioned. Every other active factor is then fixed, while the singleton signed factor is convolved with a translated or reflected fair binomial. Its number of trials is at least omega^2t_j/2 for a level-j vertex with j<b, and at least omega^2J/2 at the root. The signed smoothing estimate bounds the conditional multiplier by
[
 exp(O((s_*+1)^2+(s_*+1)Λ))
 t_j^{-(s_*+1)/2},&1le j<b, J^{-(s_*+1)/2},&j=b.
]
The estimate remains valid after averaging the other bits. Typicality is already a property of the fixed report, and no fit conditioning has been used.

The lower bounds for J,t_j give
[
 J^{-(s_*+1)}, t_j^{-(s_*+1)}
 le e^{O_B((s_*+1)(D+1)Λ)}N^{-ε(s_*+1)}.
]
Since ε s_*ge100(d_D+r_*+B+10), this absorbs the O_B(N^r) label assignments and the squared moment factor (C_1r_i)^{2r}N^{-a_0dr}. The resulting contribution to the squared degree-r norm is at most N^{-d'-1} eventually.

In a remaining odd root term, every odd nonleaf has at least two active children. At a higher vertex those children carry odd chosen terms; at level one these are selected leaves. Starting at the root, choose the first two active children in sibling order and repeat this choice at each selected odd child. This forces a complete binary subtree with 2^b leaves. The choice depends on the shape and expansion roles, not on the numerical labels. Thus rge2^b; put e=r-2^b.

For each forced nonleaf I, let h_I<h_I' be its two forced child labels, calling the first the anchor. A nonzero term requires 0<h_I'-h_I<L, because both active arguments belong to the same translate of I. Define the nonnegative anchor kernel
[
 f=prod_{I forced nonleaf}chi(xi_{I,h_I}).
]
Every extra, nonforced selected leaf still contributes an absolute chi constraint. After discarding the other constraints, the absolute multiplier is at most a fixed scalar times
[
 E_{d}dBigl[fprod_{extra leaves Ih}chi(xi_{I,h})Bigr].
]
The expectation has no additional fit indicator. The central and close-label restrictions concern the fixed labels being summed.

First sum the extra labels so that only the forced anchor expectation remains. Fix the forced labels and all nonleaf labels. For an assignment h of the e extra leaf labels, let a_{h}h be the nonnegative expectation in the previous display. At fixed bits each extra leaf has at most L labels satisfying its constraint, even if several constraints share bits. Hence
[
 sum_{h}ha_{h}hle L^eE_{d}df,
 
 sum_{h}ha_{h}h^2le(sum_{h}ha_{h}h)^2le L^{2e}(E_{d}df)^2 .
]
This avoids a free factor T_1 per extra leaf. At each positive nonroot level, there are at most e occupied nonforced vertices: their descendant sets are disjoint at that level, and each contains an extra leaf and no forced leaf. Summing their child labels costs at most (prod_{j=2}^bT_j)^e. With the forced labels fixed, f does not depend on which nonforced labels were selected, because the complete tree and every group mechanism were fixed before choosing S.

It remains to sum (E_{d}df)^2 over the forced labels. Call a forced sibling pair valid when its two labels are central and their positive difference is less than L. Dropping any further order restrictions on nonforced children can only increase this nonnegative sum. Define the outer anchor convolution
[
 K_{out}^{d}d(z)=E_{d}dchi(z-X).
]
Its ell^1 mass is L, and its supremum is at most O(Lomega^{-1}J^{-1/2}) by the hidden root count. Including at most 2L choices for the close root child, its squared sum costs
[
 sum_{substack{u_1,u_2 valid rootforced labels}}K_{out}^{d}d(u_1)^2leGamma_{out},
  Gamma_{out}=O(L^3omega^{-1}J^{-1/2}).
]

For a fixed forced labeling, let G_j be its forced level-(j+1) parents. Each GinG_j has two forced level-j children Gu_1(G),Gu_2(G) with fixed distinct labels u_1(G)<u_2(G) in the middle-half interval. For any such fixed G and sibling labels u_1<u_2, define their joint anchor kernel by
[
 H_{j,G;u_1,u_2}^{d}d(z_1,z_2)
 =E_{d}d[chi(z_1-w_j+Y_{Gu_1})chi(z_2-w_j+Y_{Gu_2})].
]
The expectation uses that group's global bits and the two local collections under the fixed report. The actual G,u_1,u_2 select those collections; only z_1,z_2 are variables in the norm. The factor can vary with all of these fixed data.

Independence of the distinct group mechanisms conditional on D_0=d gives, for this fixed forced labeling,
[
 E_{d}df=K_{out}^{d}d(h_∅)prod_{j=1}^{b-1}prod_{GinG_j}
 H_{j,G;u_1(G),u_2(G)}^{d}d(h_{Gu_1(G)},h_{Gu_2(G)}).
]
The group sets and sibling IDs in this identity are determined by the fixed upper labels. In particular G_{b-1} contains the root, and its interior global and local mechanism is independent of the outer mechanism defining X.

For fixed distinct plateau siblings, Y_{Gu_1}=V_G+H_{Gu_1} and Y_{Gu_2}=V_G+H_{Gu_2}. Conditional on d,d, the two local hidden sums are independent of each other and of the shared global hidden sum, though their visible shifts and hidden counts can differ. Uniformly in the fixed data,
[
 |H_{j,G;u_1,u_2}^{d}d|_{ell^1(Z^2)} L^2,
 |H_{j,G;u_1,u_2}^{d}d|_{ell^∞(Z^2)}
 le C_{10}L^2omega^{-2}(T_{j+1}t_j)^{-1/2}t_j^{-1/2}.
]

C_{10} is absolute. The first bound follows by summing the two indicators before averaging. For the supremum, first fix all global bits and bound the local average at Gu_2 by O(Lomega^{-1}t_j^{-1/2}). This bound is uniform in the global offset, so discard that factor's constraint. Average the other factor over its local bits and the global bits. The latter contain at least a constant times omega^2T_{j+1}t_j hidden fair trials, giving O(Lomega^{-1}(T_{j+1}t_j)^{-1/2}). Multiplication proves the displayed joint bound without treating the two offsets as independent.

Multiplying the ell^1 and supremum bounds controls the squared ell^2 sum. Allowing a close child for each anchor costs at most (2L)^2. Thus for fixed valid G,u_1,u_2,
[
 sum_{substack{z_1,z_1',z_2,z_2'inZ 0<z_1'-z_1<L, 0<z_2'-z_2<L}}
 H_{j,G;u_1,u_2}^{d}d(z_1,z_2)^2leGamma_j,
  Gamma_j=C_{11}L^6omega^{-2}T_{j+1}^{-1/2}t_j^{-1},
]
with an absolute C_{11} large enough for every group.

For two fixed valid level-j siblings Gu_1,Gu_2, let R_j(G;u_1,u_2)R_j(G;u_1,u_2) be the sum of the squares of the products of all their interior H factors, including the factor of G, over all valid forced descendant labelings. Set R_0=1. Splitting the descendant labels at their first two pairs gives the exact recurrence
[
 R_j(G;u_1,u_2)R_j(G;u_1,u_2)
 =sum_{substack{(z_1,z_1'),(z_2,z_2')valid at level j}}
 H_{j,G;u_1,u_2}^{d}d(z_1,z_2)^2prod_{v=1}^2R_{j-1}(Gu_v;z_v,z_v')
 leGamma_j(sup_{G',v_1,v_2 valid}R_{j-1}(G';v_1,v_2))^2 .
]
For the ineuality, first use the uniform descendant bound on the valid distinct child pairs. Only afterward enlarge the remaining close-label sums to at most 2L choices and apply the group-anchor cost. No group estimate is invoked at coincident sibling IDs. Iterating from the leaves upward and finally using the outer-anchor cost gives
[
 sum_{valid forced labels}(E_{d}df)^2
 leGamma_{out}prod_{j=1}^{b-1}Gamma_j^{2^{b-j-1}}.
]
This applies a uniform bound to each actual group after its upper IDs are fixed; the varying kernels are not replaced by a single stationary kernel.

Combine the extra-label reduction, the forced-anchor sum, and the squared moment factor (C_1r_i)^{2r}N^{-a_0dr}. The fixed shape and expansion counts, the powers of L and omega^{-1}, and the positive factor (C_1r_i)^{2r} contribute N^{o(ε)} by Lemma~lem:scale-margins and the block losses. The squared degree contribution of a branching term is therefore at most
[
 N^{o(ε)}J^{-1/2}prod_{j=1}^{b-1}[T_{j+1}^{-1/2}t_j^{-1}]^{2^{b-j-1}}N^{-2^ba_0d}N^{-lambda_de}.
]
The last factor pays for every extra leaf and is at most one by the score gap. Using the lower bounds for J,t_j, the decay exponent of the remaining factors is at least
[
 ε/2+sum_{j=1}^{b-1}2^{b-j-1}(kappa_{j+1}/2+ε)+2^ba_0d-o(ε)
 ge d+(b-1)/4-[(2^b-1)d+3b,2^{b-1}]ε-o(ε)>d'+.03.
]
For this calculation the local exponents give kappa_{j+1}=2^{j-b}-(6·2^j-2-2^{j-b})ε. Its leading contribution at depth j is 2^{b-j-1}2^{j-b}/2=1/4, the gain from the shared location of each forced sibling group. The bound dle2.20+(B/4)D and the choice of ε absorb the corrections and leave the strict margin over d'=d+(b-1)/4-.05.

For each r<r_*, Cauchy--Schwarz in the degree reduction combines the fixed-shape estimates. The noncentral and singleton terms are at most N^{-d'-1} in squared norm, and the branching terms have the margin just proved. Summing the finitely many degree norms and the high-degree tail gives |G_+-G_-|_{r_i}^2le N^{-d'-.01}, which proves Lemma~lem:tree-score.

Lemma~lem:clipping now applies to the preliminary laws widetildemu_i,widetildenu_i, their common report D_0, and the conditional densities. The typical report has probability 1-o(Delta), the high-degree estimate supplies rho=g_B, and Lemma~lem:tree-score supplies the density difference. Conditioning on the common event consisting of typical metadata and G_+ge1/2 gives laws mu_i,nu_i with the required domination and score. Each preliminary law changes by o(Delta). The hidden-bit law was used only before this conditioning.

Together with the tree simulation estimate, the new conditioning and failed-layout loss is at most Delta for all large instances. The inherited loss is at most (prod_jT_j)E_{i-1}le(prod_jP_j)E_{i-1}=(ell_i/ell)E_{i-1}. Thus one may take
[
 E_ileDelta+(ell_i/ell)E_{i-1},
 (E_i)/(ell_i)le(Delta)/(ell_i)+frac{E_{i-1}}{ell_{i-1}}le(i+1)Delta .
]
The length and overlap conditions come from the block construction, so this completes Proposition~prop:block. Starting from Proposition~prop:initial and iterating the block proves Proposition~prop:construction.


Proposition~prop:construction now supplies the final pair and its auxiliary laws. A one-trace bound is retained before any use of product observations, and it proves the minimum-total-variation theorem independently of the sample-complexity deduction.

[Restoration and padding]
For the scale parameters, there are distinct words x,yin{0,1}^n such that, for every positive integer m,
[
 TV(Dcal_q(x)^{ ⊗  m},Dcal_q(y)^{ ⊗  m})lesqrt{m n^{-d_D}}+2mn(D+1)Delta .
]
In particular,
[
 TV(Dcal_q(x),Dcal_q(y))le n^{-d_D/2}+2n(D+1)Delta .
]

Proof. 
Append the same arbitrary binary tail to x_D,y_D to reach length n. The two remain distinct. Applying the final common oracle kernel, then generating an independent trace of the known tail and concatenating it, approximates each padded delta-trace law within E_Dle n(D+1)Delta in total variation. Common padding by this kernel is the monotonicity principle also used in the proof of Lemma~10 of McGregor, Price, and Vorotnikova.

./pdf/mcgregor-price-vorotnikova-2014.pdf

The final moment estimate, monotonicity of norms on a probability space, and r_Dge2 give
[
 H^2(mu_D,nu_D)leBigl|(dnu_D)/(dmu_D)-1Bigr|_{L^2(mu_D)}^2le n^{-d_D}.
]
Tensorisation and TVle H bound the oracle product distance by sqrt{m n^{-d_D}}. Replacing each of the m projected factors by its genuine law costs at most mE_D for each hypothesis, by tensor telescoping. This proves the first bound for delta. Applying the additional deletion kernel independently to each sample proves the same bound for the requested q. Taking m=1 proves the second bound.


Proof. [Proof of Theorem~thm:tv]
Fix qin(0,1). Choose B=2, zeta=1/2, and auxiliary coefficients c=1/(80log2)<c_+=1/(40log2) once, independently of A. The setup ineuality holds because its left side is 1/(20log2). The construction remains valid with these fixed parameters; its proof requires only their positivity and the eventual ineualities. In this case delta>0 is fixed, Dto∞, and d_D=2.20+0.20Dto∞. For every fixed A>0, multiplying the one-trace bound by n^A gives
[
 n^{A-d_D/2}+2(D+1)n^{A+1-100(d_D+B+1)}→0.
]
The construction is available for every sufficiently large integer n, not only a subsequence; its pair has length at most n and common padding reaches n exactly. This proves the total-variation limit. The sample-complexity conclusion follows from Theorem~thm:main, whose proof does not use Theorem~thm:tv; indeed clog(q^3log n)to∞ for any fixed admissible c>0.


For two equally likely hypotheses with observation laws P,Q, every randomised decision rule has average success at most (1+TV(P,Q))/2. If phi is the conditional probability of choosing the first hypothesis, its average success is
[
 1/2(1+E_Pphi-E_Qphi)le1/2(1+TV(P,Q)), 0lephile1 .
]
Trace-reconstruction versions of this two-point comparison appear in Appendix~A.2 of Holden and Lyons.

./pdf/holden-lyons-2020.pdf

Fix 0<c<c_+<1/(4log2) and choose B,zeta so that
[
 alpha:=((1-zeta)((B-1)/4-.05))/(Blog2)>c_+ .
]
The j_0 preliminary blocks have a fixed number depending only on B, so
[
 d_D=alphalog H_{del}+O_B(1).
]
For an absolute constant a>0 sufficiently small, the product bound with mle an^{d_D} is strictly less than 1/3 eventually: its first term is at most sqrt a, and its second is at most
[
 2a(D+1)n^{d_D+1-100(d_D+B+1)}=o(1).
]
Thus the maximal average success for the pair is at most 2/3. The channel reduction gives log H_{del}=log(q^3log n)+O(1) uniformly in q. The strict ineuality alpha>c_+ therefore implies
[
 a n^{d_D}ge n^{c_+log(q^3log n)}
]
eventually. Exact worst-case reconstruction with success 2/3 would distinguish this pair with that success, so this proves the usual 2/3 lower bound with a strict margin.

Proof. [Proof of Theorem~thm:main]
Fix sin(0,1] and c as in the theorem, and retain c_+>c. Choose a fixed positive integer g with (2/3)^g<s. Put N=floor( n/g) and construct the hard pair at length N using the same requested deletion rate q as the input instance. Its working rate is still delta=min(q,1/2). Since q^3log Nsim q^3log nto∞ and log N=log n+O_g(1), the construction and testing bounds apply to each gadget. Moreover
[
 ((log N)log(q^3log N))/((log n)log(q^3log n))→1,
]
so c_+>c gives
[
 N^{c_+log(q^3log N)}ge n^{clog(q^3log n)}
]
eventually.

Take g independent fair choices between the two length-N words, concatenate the chosen words, and append a common known tail of length n-gN. This gives 2^g distinct length-n hypotheses. Give the estimator the stronger observation in which every trace is separated at the gadget boundaries, together with an independent trace of the tail. Concatenation simulates the usual observation exactly. Amplification by independent hard blocks appears in Section 3.3 of McGregor, Price, and Vorotnikova and in Section 4 of Holden and Lyons.

./pdf/mcgregor-price-vorotnikova-2014.pdf
./pdf/holden-lyons-2020.pdf

Under the product prior the separated data from different gadgets are independent. Their posteriors factor as well: for a hypothesis vector theta=(theta_1,...,theta_g) and separated data z=(z_1,...,z_g),
[
 Prob(thetamid z)=prod_{j=1}^gProb(theta_jmid z_j).
]
The largest conditional probability of a correct joint guess is the product of the largest single-gadget posterior probabilities. Averaging, independence of the z_j shows that the optimal joint success is the product of the optimal single-gadget average successes. The tail has the same law under every hypothesis and changes none of these posteriors.

For any positive integer sample budget mle n^{clog(q^3log n)}, the two threshold ineualities bound every single-gadget success by 2/3. The joint average success is therefore at most (2/3)^g<s. When m=0 the posterior remains the uniform prior, so the optimal joint success is 2^{-g}le(2/3)^g<s. A reconstruction procedure with worst-case success at least s would have average success at least s under this finite prior, a contradiction even in the stronger experiment. No nonnegative integer budget at most the claimed threshold suffices, which gives the sample lower bound.