\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{mathpazo}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,decorations.pathreplacing}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\urlstyle{same}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\DeclareMathOperator{\TV}{TV}
\DeclareMathOperator{\ov}{ov}
\DeclareMathOperator{\Bin}{Bin}
\DeclareMathOperator{\supp}{supp}
\newcommand{\Dcal}{\mathcal D}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\newcommand{\Tr}{\mathrm{Tr}}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\allowdisplaybreaks[2]
\setlength{\emergencystretch}{2em}
\begin{document}

Fix a binary word $x=x_1\cdots x_n\in\{0,1\}^n$ and a deletion probability $q\in(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 $s\in(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 $x\in\{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)=+\infty$. Write $T_q(n)=T_{q,2/3}(n)$.

\begin{theorem}[Quantitative sample lower bound]\label{thm:main}
Fix $s\in(0,1]$ and $0<c<1/(4\log 2)$. Along every sequence of instances $(n,q)$ with $n\to\infty$, $q\in(0,1)$, and $q^3\log n\to\infty$,
\[
T_{q,s}(n)\ge n^{c\log(q^3\log n)}
\]
for all sufficiently large instances. All logarithms are natural. In particular, at every fixed deletion probability $q\in(0,1)$ and every fixed positive success probability $s$, the required sample size is $n^{\Omega(\log\log n)}$.
\end{theorem}

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)=\frac12\sum_w|P(w)-Q(w)|.
\]

\begin{theorem}[Superpolynomial one-trace indistinguishability]\label{thm:tv}
For every fixed deletion probability $q\in(0,1)$,
\[
\lim_{n\to\infty}n^A\min_{\substack{x,y\in\{0,1\}^n\\ x\ne y}}\TV\bigl(\Dcal_q(x),\Dcal_q(y)\bigr)=0\quad\text{for every }A>0.
\]
At the same channel, $T_{q,s}(n)/n^A\to\infty$ for every fixed $A>0$ and $s\in(0,1]$.
\end{theorem}

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.

./trefs/levenshtein-2001-ieee-slides.pdf
./trefs/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 $\Omega(n^{5/4}/\sqrt{\log n})$, and Chase obtained $\Omega(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.

./trefs/mcgregor-price-vorotnikova-2014.pdf
./trefs/holden-lyons-2020.pdf
./trefs/holden-lyons-errata-2022.pdf
./trefs/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~\ref{thm:main} at a fixed channel has order $(\log n)(\log\log n)$; a gap between the rates remains.

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

Polynomial reconstruction remains possible under other channel or input conditions. For every fixed $\varepsilon>0$, Chen, De, Lee, Servedio, and Sinha give reconstruction in polynomial time when $q\le n^{-1/3-\varepsilon}$, using $O(n^{4/3})$ traces. Those deletion probabilities lie outside the regime $q^3\log n\to\infty$ of Theorem~\ref{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.

./trefs/chen-de-lee-servedio-sinha-2021.pdf
./trefs/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(-\Omega(\sqrt n))$. Its use of translated segments and cancellation is related to the observation constructed in the proof of Theorem~\ref{thm:main}. Theorems~\ref{thm:main} and~\ref{thm:tv} concern the entire trace law of one deterministic binary word.

./trefs/dos-2017.pdf
./trefs/nazarov-peres-2017.pdf
./trefs/chen-de-lee-servedio-2024.pdf
./trefs/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.

./trefs/allouche-shallit-1999.pdf
./trefs/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\bigl(\sqrt{dP}-\sqrt{dQ}\bigr)^2 .
\]
Cauchy--Schwarz and Hellinger affinity give $\TV(P,Q)\le H(P,Q)\le\sqrt{2\TV(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 $Q\ll P$, then
\[
 H^2(P,Q)\le\int\Bigl(\frac{dQ}{dP}-1\Bigr)^2 dP .
\]
These elementary inequalities explain why a small likelihood score is an appropriate induction quantity.

For the remainder of the construction put
\[
 \delta=\min(q,1/2),\qquad \Lambda=\delta^{-3},\qquad H_{\rm del}=\delta^3\log 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_{\rm del}\to\infty,\qquad
 \log H_{\rm del}=\log(q^3\log 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 $d\nu/d\mu-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/(4\log 2)$, then fix a constant integer $B\ge 2$ and $0<\zeta<1$ with
\[
\frac{(1-\zeta)\bigl((B-1)/4-.05\bigr)}{B\log 2}>c_+>c .
\]
Set
\[
D=\Bigl\lfloor (1-\zeta)\frac{\log H_{\rm del}}{B\log 2}\Bigr\rfloor,\quad
j_0=5\cdot 2^B,\quad
\epsilon=2^{-4B-100}/(D+1),
\quad
b_i=\begin{cases}2,&1\le i\le j_0,\\ B,&j_0<i\le D.\end{cases}
\]
Work in the regime $D>j_0$ (which fails for finitely many $n$). For each admissible depth, put
\[
a_0(b)=(1+\epsilon)2^{-b}-\epsilon ,
\]
which is positive for all sufficiently large instances. Define target scales backwards by
\[
N_D=n,\qquad N_{i-1}=N_i^{a_0(b_i)}\quad(1\le i\le D),
\]
and score exponents by
\[
d_0=2.20,\qquad d_i=d_{i-1}+(b_i-1)/4-.05\quad(1\le i\le 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~\ref{thm:main}.

The remaining parameters control accumulated projection error and rare events. Put
\[
\Delta=n^{-100(d_D+B+1)},\qquad
r_i=2\Bigl\lceil 10^8\,2^{10B}(d_D+B+1)\frac{\log n}{\log N_i}\Bigr\rceil\quad(0\le i\le 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.

\begin{lemma}[Uniform scale margins]\label{lem:scale-margins}
For the parameters above,
\[
\log N_0\gtrsim_B(\log n)2^{-BD}\gtrsim_B(\log n)H_{\rm del}^{-(1-\zeta)}=\Lambda H_{\rm del}^{\zeta}.
\]
Moreover,
\[
\epsilon\log N_0\gtrsim_B\frac{(\log n)^\zeta}{1+\log\log n}\gg\log\log n+\log(d_D+B+1).
\]
For every fixed nonnegative integer $h$, uniformly over $0\le i\le D$,
\[
(D+1)^h\Lambda=o\bigl(\epsilon\log N_0\bigr),\qquad
\exp\bigl(O_B((D+1)^h\Lambda)\bigr)=N_i^{o(\epsilon)}.
\]
\end{lemma}
\begin{proof}
For every admissible $b$ one has $a_0(b)\ge2^{-B}(1-(2^B-1)\epsilon)$. Multiplying over $D$ blocks loses only a factor bounded away from zero by a positive constant depending on $B$, because $D\epsilon\le 2^{-4B-100}$. The definition of $D$ proves the first display. Since $H_{\rm del}\le\log n$ and $D+1=O_B(1+\log\log n)$, the same bound proves the second. Finally
\[
\frac{(D+1)^h\Lambda}{\epsilon\log N_0}\lesssim_B\frac{(D+1)^{h+1}}{H_{\rm del}^{\zeta}}\longrightarrow0,
\]
because $D=O_B(\log H_{\rm del})$. Since $N_i\ge N_0$, this proves the exponential form as well.
\end{proof}

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 $n\to\infty$. 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.

\begin{definition}[Level invariant]\label{def:invariant}
Choose $C>2$, $0<\omega<1/8$, and a constant $M_B\ge0$ depending only on $B$, with $\log C=O(\Lambda)$ and $\log(\omega^{-1})=O(\Lambda)$, depending only on $\delta$. The same choices are used at every level. For $0\le i\le D$, a level-$i$ pair consists of two different strings $x_i,y_i$ of common length $\ell_i\in[N_i/2,N_i]$, and probability laws $\mu_i,\nu_i$ on a common auxiliary space, satisfying three conditions:
\begin{itemize}
\item[(i)] There are a Markov kernel $\mathcal K_i$ from the auxiliary space to finite binary words and a number $E_i\ge0$ with
\[
\TV(\mathcal K_i\mu_i,\Tr(x_i))\le E_i,\qquad \TV(\mathcal K_i\nu_i,\Tr(y_i))\le E_i,\qquad \frac{E_i}{\ell_i}\le(i+1)\Delta.
\]
\item[(ii)] $\nu_i\ll\mu_i$ and
\[
\Bigl\|\frac{d\nu_i}{d\mu_i}-1\Bigr\|_{L^{r_i}(\mu_i)}^2\le N_i^{-d_i}.
\]
\item[(iii)] For an integer $k_i\in[\ell_i,C^{2Bi+M_B}\ell_i]$,
\[
\ov\bigl(\Tr(x_i^{k_i}),\Tr(x_i^{k_i+1})\bigr)\ge\omega .
\]
\end{itemize}
Powers concatenate copies of a word.
\end{definition}

For every positive integer $m$, conditions (i) and (ii) give
\[
\TV\bigl(\Tr(x_i)^{\otimes m},\Tr(y_i)^{\otimes m}\bigr)\le\sqrt{m N_i^{-d_i}}+2mE_i,
\]
by Hellinger tensorisation and telescoping the projection errors. That inequality 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.

\begin{proposition}[Construction at every scale]\label{prop:construction}
Fix $B,\zeta,c_+$ and the parameters above. Along every sequence with $n\to\infty$ and $\delta^3\log n\to\infty$, for all sufficiently large instances there exist level-$i$ pairs satisfying Definition~\ref{def:invariant} simultaneously for $0\le i\le 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.
\end{proposition}

\begin{lemma}[Multilinear moment bound]\label{lem:moment}
Let $t\ge2$ be an even integer, let $h\ge0$, and let $(Z_j)_{j\in\mathcal J}$ be a finite family of independent centred real variables with $\|Z_j\|_t\le h$. For an integer $r\ge1$, the degree-$r$ multilinear polynomial with real coefficients $A(S)$ on $r$-subsets satisfies
\[
\Bigl\|\sum_{|S|=r} A(S)\prod_{j\in S} Z_j\Bigr\|_t\le (C_1 t h)^r \|A\|_{\ell^2},
\]
where $\ell^2$ uses counting measure and $C_1$ is absolute.
\end{lemma}
\begin{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^2\le |b|^2+C_2 t |v|^2$ for real $b,v$. If $|v|\le |b|/t$ and $b\ne0$, expand the moment, whose linear term vanishes, and bound it by $|b|^t(1+O(t^2(v/b)^2))$ using $\sum_{k\ge2}(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 inequality and $2|bv|\le 2t|v|^2$. Iteration by conditioning on one variable's complement and applying the triangle inequality in $L^{t/2}$ proves the bound. The same inequality applies to finite families indexed by positions or ranks, identifying ordered increasing tuples with subsets.
\end{proof}

./trefs/bonami-1970.pdf

\begin{lemma}[Lifting adjacent-power overlap]\label{lem:lift}
Let $w$ be a nonempty word, $k$ a positive integer, and $0<\omega<1/8$ with $\ov(\Tr(w^k),\Tr(w^{k+1}))\ge\omega$. There is an absolute $C_{\rm abs}$ such that whenever $C\ge C_{\rm abs}/\omega$, $P$ exceeds a sufficiently large absolute constant, and the integer $F$ satisfies $F\ge CkP$,
\[
\ov(\Tr(w^{FP}),\Tr(w^{FP+P}))\ge 2/3 .
\]
\end{lemma}
\begin{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=2\lfloor FP/(2k+1)\rfloor$ 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,2\omega g]$ except with probability at most $2\exp(-c'\omega g)$ for an absolute $c'>0$ by the multiplicative binomial Chernoff bound, where $\omega g\ge 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/2\le m\le 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 $\lfloor(g-M+1)(m+1)/(g+2)\rfloor$. 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 $g\gtrsim CP^2$, $M\ge\omega g/2\gtrsim P^2$, and $g-M\ge(1-2\omega)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/\sqrt{\omega g})$ plus the rare flag probability, which is at most $1/3$ at large $P$ by choosing $C\omega$ greater than a sufficiently large absolute constant. Taking smaller common sublaws if needed uses exactly mass $\omega$ in the flag construction.
\end{proof}

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~\ref{fig:paired-hiding} depicts one pair and the resulting uncertainty in the number of copies to the left of the central segment.

./trefs/mcgregor-price-vorotnikova-2014.pdf
./trefs/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}))\ge\omega$, 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\otimes U$ on it; otherwise reveal the bit and generate the two traces jointly from the normalised residual after subtracting $\omega^2 U\otimes 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.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[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=\small\bfseries] at (0,0.58)
    {A fair bit swaps the side lengths};
  \node[anchor=east] at (13.7,0.58)
    {$E\sim\mathrm{Bernoulli}(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\otimes U)+(1-\omega^2)R_E$};
  \node[card,fill=blue!9] (hidden) at (3.45,-2.52)
    {\textbf{Hidden:} $E$ is not reported. Emit $U\otimes U$; $E$ remains fair.};
  \node[card,draw=black!50,fill=black!3] (visible) at (10.55,-2.52)
    {\textbf{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_{\rm left}:=Jk+\sum_{i=1}^{J}E_i$ copies of $w$ on the left.\\
     After the side report, $c_{\rm vis}:=Jk+\sum_{\rm visible}E_i$ and hidden count $M$ fixed, and\\
     $L_{\rm left}=c_{\rm vis}+\sum_{\rm hidden}E_i
     \overset{\rm law}{=}c_{\rm vis}+\mathrm{Bin}(M,1/2)$.};
\end{tikzpicture}
\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, $M\sim\Bin(J,\omega^2)$ before reporting. The lower panel conditions on flags, side outputs, and visible bits; $L_{\rm left}$ counts only copies contributed by the left pair members. Other fixed material adds a deterministic location offset. Block widths are schematic.}
\label{fig:paired-hiding}
\end{figure}

\begin{lemma}[Clipping with a common event]\label{lem:clipping}
Fix a level $0\le i\le D$ and its parameters. Suppose preliminary oracle laws have common side metadata with law $Q_{\rm 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_{\rm side}$-almost every metadata value, and use $Q_{\rm 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}
\quad\text{and}\quad
\|G_y-G_x\|_{r_i}^2\le N_i^{-d_i-.01}
\]
hold in $L^{r_i}(Q)$, where $\rho\ge2^{-4B-10}$. Then conditioning each law on the event consisting of typical metadata and $G_x\ge1/2$ changes it in total variation by $o(\Delta)$. The conditioned laws $\mu,\nu$ satisfy $\nu\ll\mu$ and $\|d\nu/d\mu-1\|_{L^{r_i}(\mu)}^2\le N_i^{-d_i}$. All conclusions are uniform over $0\le i\le D$.
\end{lemma}
\begin{proof}
Condition each preliminary law separately on the common event $A_{\rm keep}$ consisting of typical metadata and $G_x\ge1/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_x\ge1/2$ on $A_{\rm 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_x\ge1/2,\ {\rm typical}\}}\bigl|G_y/G_x-1\bigr|^{r_i}G_x\,d(Q_{\rm 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 $\Delta\le N_i^{-100d_D}$. Any $o(\Delta)$ masses claimed from the assumed estimates follow uniformly from the definition of $r_i$ and $\log N_i\to\infty$; 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_x\ge1/2$ and $G_x+G_y$ on its complement.
\end{proof}

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.

\begin{proposition}[Seed pair]\label{prop:initial}
For the parameters set out above, there is a choice of the common constants in Definition~\ref{def:invariant} with $M_B=1$ for which a level-$0$ pair exists with simulation error $E_0\le\Delta$. One may choose $\omega=\exp(-C_9\Lambda)$ for an absolute $C_9$ and $C>2$ with $\log C=O(\Lambda)$.
\end{proposition}

Throughout the proof of Proposition~\ref{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=\lfloor N^{1/2-\eta}\rfloor,\quad
 K=\lfloor N^{1/2-2\eta}\rfloor,\quad
 k=\lfloor\delta m\rfloor,
\]
\[
 J=\Bigl\lfloor\frac{\lfloor N/(2m-1)\rfloor-K}{2k+1}\Bigr\rfloor,\quad
 P=J(2k+1)+K .
\]
Lemma~\ref{lem:scale-margins} gives $\Lambda=o(\log N)$, hence $\delta^{-1}=N^{o(1)}$. In particular $\delta^3 m\to\infty$, $m\delta^2\to\infty$, and $K,k+1\le m$ for all sufficiently large instances. The definitions then give
\[
 J\asymp\delta^{-1}N^{2\eta},\qquad J=o(K),\qquad P(2m-1)\in[N/2,N].
\]
For the last assertion, $P$ differs from $\lfloor N/(2m-1)\rfloor$ by fewer than $2k+1$, so the omitted length is $O(km+m)=o(N)$.

For this construction, take the ordinary block $\mathsf A=01$ and the defect block $\mathsf D=1$. For $b\in\{-1,0,1\}$ define the period
\[
 W_b=\mathsf A^{\lfloor m/2\rfloor+b-1}\,\mathsf D\,\mathsf A^{m-\lfloor m/2\rfloor-b} .
\]
It contains $m$ blocks, with the defect at block position $\lfloor m/2\rfloor+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 $\mathsf A$ appended. Later, $W_{-1}$ is compared with $W_1$ on exceptional periods and signed choices are made across many periods.

./trefs/chase-2021-lower.pdf

Set
\[
 a=\lfloor P/2\rfloor,\quad s_0=300,\quad I=\{0,\ldots,2^{s_0}-1\},\quad
 \sum_{i\in 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$, $i\in 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,\ldots,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$.

./trefs/allouche-shallit-1999.pdf

A more informative observation is used at this level only. For $H\in\{\mathsf A,\mathsf D\}$ put
\[
 r_e=\delta^2/2,\qquad
 \nu_H=\frac{\Tr(H)-r_e\delta_\varnothing}{1-r_e},
\]
where $\varnothing$ 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.

./trefs/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
\[
 \mathcal M_{\rm mark}=\{\varnothing,0,1,01\}.
\]
An observation on a sequence of blocks is the ordered list of its returning marks, an element of $\bigsqcup_{l\ge0}\mathcal M_{\rm 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 $(\varnothing)$ 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_e\delta_\varnothing+(1-r_e)\nu_H .
\]

Under $\nu_{\mathsf A}$ define
\[
 Z(Y)=\frac{\nu_{\mathsf D}(Y)}{\nu_{\mathsf A}(Y)}-1 .
\]
The defect law is dominated by the ordinary-block law. Its support lies in $\{\varnothing,1\}$, where the likelihood ratios are
\[
 \frac{\delta-\delta^2/2}{\delta^2/2}\quad\text{and}\quad\frac1\delta,
\]
respectively. Hence $Z$ is centred, $\|Z\|_\infty=O(\delta^{-1})$, and $\|Z\|_{L^2(\nu_{\mathsf A})}^2\lesssim\delta^{-1}$, uniformly for $\delta\le1/2$.

Take $1\le u\le m$ periods with fixed types $\mathbf b=(b_1,\ldots,b_u)\in\{-1,0,1\}^u$. There are $n_b=um$ slots, and the defect in period $j$ sits at
\[
 p_{\mathbf b}(j)=(j-1)m+\lfloor m/2\rfloor+b_j .
\]
The return count has law $\Bin(n_b,1-r_e)$, independent of $\mathbf b$. Conditional on any $0\le l\le n_b$, the returning subset $S_l$ is uniform among the size-$l$ subsets of $\{1,\ldots,n_b\}$. This subset is not reported. If $p\in S_l$, write $\mathrm{rk}_{S_l}(p)$ for its rank in the increasing order on $S_l$. Put $Q_l=\nu_{\mathsf A}^{\otimes l}$, with $Q_0$ the point mass on the empty list. Relative to $Q_l$, the density of the reported list $Y=(Y_1,\ldots,Y_l)$ is
\[
 G_{\mathbf b}^{(u,l)}(Y)
 =\mathbb E_{S_l}\prod_{\{j:\,p_{\mathbf b}(j)\in S_l\}}
 \bigl(1+Z(Y_{\mathrm{rk}_{S_l}(p_{\mathbf b}(j))})\bigr).
\]
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_{\mathsf A}$. To expand it, fix $1\le r\le u$ and take an increasing tagged tuple $\mathbf j=(j_1,\ldots,j_r)$ of periods and an increasing rank tuple $1\le v_1<\cdots<v_r\le l$. Write $p_h=p_{\mathbf b}(j_h)$ and put
\[
\begin{aligned}
 W_{\mathbf j,\mathbf b}(v)
 &=\Prob\bigl\{p_h\in S_l,\ \mathrm{rk}_{S_l}(p_h)=v_h\text{ for every }h\bigr\},\\
 A_{r,\mathbf b}(v)&=\sum_{1\le j_1<\cdots<j_r\le u}W_{\mathbf j,\mathbf b}(v).
\end{aligned}
\]
The event defining $W_{\mathbf j,\mathbf 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_{\mathbf b}^{(u,l)}(Y)=1+\sum_{r=1}^{u}\sum_{1\le v_1<\cdots<v_r\le l}
 A_{r,\mathbf b}(v)\prod_{h=1}^r Z(Y_{v_h}) .
\]

Define the slot gaps and rank gaps by
\[
\begin{aligned}
 (g_0,\ldots,g_r)&=(p_1-1,\,p_2-p_1-1,\ldots,p_r-p_{r-1}-1,\,n_b-p_r),\\
 (z_0,\ldots,z_r)&=(v_1-1,\,v_2-v_1-1,\ldots,v_r-v_{r-1}-1,\,l-v_r).
\end{aligned}
\]
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_{\mathbf j,\mathbf b}(v)=\frac{\prod_{i=0}^r\binom{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 $z\in\{0,\ldots,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=\frac{l}{n_b}\in[1-\delta^2,1-\delta^2/4].
\]
For a tagged tuple define the coarse gaps
\[
 \gamma_0=j_1-\tfrac12,\quad
 \gamma_i=j_{i+1}-j_i\ (1\le i<r),\quad
 \gamma_r=u-j_r+\tfrac12 .
\]
These sum to $u$, and $g_i=m\gamma_i+\alpha_i$ with $|\alpha_i|\le3$. End coarse gaps are positive half-integers and internal coarse gaps are positive integers. In particular $g_i\gtrsim m$. At an admissible count, the expected binomial success and failure counts tend to infinity uniformly by $m\delta^2\to\infty$.

\begin{lemma}[Rank-kernel square sum]\label{lem:base-kernel}
For the $u$-period construction and admissible count above, and for every $1\le r\le u$,
\[
 \|A_{r,\mathbf 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.
\end{lemma}
\begin{proof}
Fix $u,l,\mathbf 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
\[
 \langle W_{\mathbf j,\mathbf b},W_{\mathbf j',\mathbf b}\rangle
 =\frac{\theta^{2r}}{f_{n_b}(l)^2}
  \sum_{\substack{z_i\ge0\\\sum_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_e\gtrsim mu/(r+1)$. Solve the total constraint for $z_e$, bound that factor by its supremum, and drop the constraints on the remaining coordinates:
\[
 \langle W_{\mathbf j,\mathbf b},W_{\mathbf j',\mathbf b}\rangle
 \le\frac{\theta^{2r}}{f_{n_b}(l)^2}
  \sup_z f_{g_e}(z)f_{g_e'}(z)
  \prod_{i\ne 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_{\rm rk}/\delta)g^{-1/2}
  \exp\!\Bigl(-c_{\rm rk}\frac{(g-g')^2}{g+g'}\Bigr).
\]
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\,\mathrm{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_{\rm rk}(g-g')^2/(g+g')$, since $\theta\ge1/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((\delta\sqrt g)^{-1})$.

Corresponding coarse-gap coordinates have integer differences. Since $g_i=m\gamma_i+O(1)$ with an absolute error, for a nonzero mismatch and all large $m$,
\[
 |g_i-g_i'|\ge\tfrac12m|\gamma_i-\gamma_i'|,\quad
 g_i+g_i'\lesssim mu,\quad
 g_i\gtrsim m\gamma_i.
\]
For a matching coordinate the exponential equals $1$. Substituting these comparisons and using $\theta^{2r}\le1$ yields
\[
 \langle W_{\mathbf j,\mathbf b},W_{\mathbf j',\mathbf b}\rangle
 \le C_{\rm rk}(r+1)\prod_{i\ne e}\Bigl[
  \frac{C_{\rm rk}}{\delta\sqrt{m\gamma_i}}
  \exp\!\Bigl(-c_{\rm rk}\frac{m(\gamma_i-\gamma_i')^2}{u}\Bigr)\Bigr].
\]
It remains to sum over both tagged tuples. Once the other coarse gaps are fixed, the constraint $\sum_i\gamma_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_{i\ne e}e^{-c_{\rm rk}m(\gamma_i-\gamma_i')^2/u}
 \le\prod_{i\ne e}\sum_{z\in\mathbb Z}e^{-c_{\rm rk}(m/u)z^2}
 \le C_{\rm rk}^r
\]
because $m\ge u$. Thus the remaining $r$ first-tuple coordinates contribute $m^{-r/2}$ times a sum of $\prod_{i\ne e}\gamma_i^{-1/2}$ with their total at most $u$. With $\tau=r/u\in(0,1]$,
\[
 \sum_{\sum_{i\ne e}\gamma_i\le u}\prod_{i\ne e}\gamma_i^{-1/2}
 \le e^{\tau u}\prod_{i\ne e}\sum_{\gamma_i>0}\gamma_i^{-1/2}e^{-\tau\gamma_i}
 \le C_{\rm 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,\mathbf b}\|_2^2$ is the sum of these inner products, the lemma follows.
\end{proof}

Two gap-sum inequalities are used repeatedly. For $1\le h\le r$ and an integer $j$ put
\[
 \Sigma_{r,h}(j)=\sqrt{Km}\sum_{\substack{1\le j_1<\cdots<j_r\le K\\j_h=j}}\prod_{i=0}^r(m\gamma_i)^{-1/2}.
\]
For $r\ge2$, let $\Sigma_{r,h}^{\rm bd}(j)$ be the same sum restricted to tuples with $\gamma_i\le|I|$ for some $1\le i<r$.

\begin{lemma}[Gap sums at a fixed period]\label{lem:base-fixed-sums}
For fixed $1\le r<R_0$, uniformly in $h$ and $j\in[K/3,2K/3]$,
\[
 \Sigma_{r,h}(j)\le C_r(Km)^{-1/2}\lambda^{r-1},\qquad
 \Sigma_{r,h}^{\rm bd}(j)
 \le C_{r,s_0}(Km)^{-1/2}m^{-1/2}\lambda^{r-2}\quad(r\ge2).
\]
\end{lemma}
\begin{proof}
The left gaps $0,\ldots,h-1$ sum to $j-\tfrac12$ and the right gaps $h,\ldots,r$ sum to $K-j+\tfrac12$. 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>0\\\gamma\le K}}(m\gamma)^{-1/2}
 \le C_*\sqrt{K/m}=C_*\lambda
\]
on either lattice. Grouping by the at most $C_r$ choices of selected gaps and multiplying by $\sqrt{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|}(m\gamma)^{-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.
\end{proof}

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}^{(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
\[
 \mathbb E_{Q_l}\bigl[(G^{(u,l)})^2\bigr]
 =1+\sum_{r=1}^{u}\|A_{r,\mathbf0}\|_2^2\|Z\|_2^{2r}
 \le1+\sum_{r\ge1}
 (C_6\delta^{-2}\sqrt{u/m})^r r^{-r/2}
 \le\exp(C_6'\Lambda).
\]
Indeed, for $a\ge0$, $\sum_{r\ge1}(a/\sqrt r)^r\le\exp(C_*(1+a^2))$: for $r>4a^2$ the terms are at most $2^{-r}$; for $1\le r\le4a^2$, the maximum of $r\log(a/\sqrt r)$ over positive reals is at most $a^2/(2e)$. Since $\delta^{-4}u/m\lesssim\delta^{-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_b\asymp1/(\delta m)=o(\delta^2)$. Stirling's formula gives mass per count at least
\[
 c_7(\delta\sqrt{n_b})^{-1}
 \exp\!\Bigl(-C_7\frac{m^2}{\delta^2n_b}\Bigr)
 \ge m^{-1}\exp(-C_8\Lambda)
\]
for absolute positive constants. One way to see the exponent: the relative entropy between $\mathrm{Ber}(l/n_b)$ and $\mathrm{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_b\asymp\delta^2n_b\asymp\delta^3m^2\longrightarrow\infty .
\]
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\Lambda)<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_{\rm abs}/\omega,9/\delta\}$, so $C\delta>8$ and $\log C=O(\Lambda)$.

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\otimes 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.

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

Use the common mass for the mark-list laws. Draw $J$ independent fair bits $E_1,\ldots,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_{\rm 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_{\rm left}
 =\Bigl\lfloor\frac{J+K}{2}\Bigr\rfloor-\sum_{i=1}^J E_i
 =K/2+O(J+1).
\]
\label{eq:base-anchor}
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 $(\mathbf b_\pm(X))_j=\pm\beta_{j-X}$. Conditional on the report $\mathfrak d$, the central densities and coefficient arrays are
\[
\begin{aligned}
 G_\pm^{\mathfrak d}&=\mathbb E_{X\sim\pi_{\mathfrak d}}G_{\mathbf b_\pm(X)}^{(K,l)},
 &A_{r,\pm}^{\mathfrak d}&=\mathbb E_{X\sim\pi_{\mathfrak d}}A_{r,\mathbf b_\pm(X)},\\
 G_{\rm pure}^{\mathfrak d}&=G_{\mathbf0}^{(K,l)},
 &A_{r,\rm pure}^{\mathfrak d}&=A_{r,\mathbf0}.
\end{aligned}
\]
These densities all integrate to one under $Q_l$. In particular
\[
 P_\pm(d\mathfrak d,dY)=Q_{\rm meta}(d\mathfrak d)\,G_\pm^{\mathfrak d}(Y)Q_l(dY)
\]
with $l$ read from $\mathfrak d$, and the analogous identity holds for $P_{\rm pure}$. This is the common conditional reference required by Lemma~\ref{lem:clipping}.

Call metadata typical when
\[
 \frac l{Km}\in[1-\delta^2,1-\delta^2/4],\qquad M\ge\omega^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(\epsilon)},\quad
 \delta^2Km=N^{1-3\eta-o(1)},\quad
 \omega^2J=N^{2\eta-o(1)} .
\]
Both Chernoff exponents therefore dominate $\log\Delta^{-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 $\mathfrak d$. Put $\lambda=\sqrt{K/m}=N^{-\eta/2+o(1)}$. For a fixed central type vector, Lemmas~\ref{lem:base-kernel} and~\ref{lem:moment} give
\[
 \Bigl\|\sum_{1\le v_1<\cdots<v_r\le l}A_{r,\mathbf b}(v)\prod_{h=1}^r Z(Y_{v_h})\Bigr\|_{r_0}
 \le\bigl(C_*r_0\delta^{-3/2}\sqrt\lambda\bigr)^r r^{-r/4} .
\]
One has $\|Z\|_{r_0}\lesssim\delta^{-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 inequality when mixing over $X$, gives
\[
 \|G-1\|_{r_0}\le N^{-.0009},\qquad
 \|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 $\mathcal B_r=A_{r,+}-A_{r,-}$ and $\mathcal B_r^{\rm 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_{\rm seed}(i)=\mathbf 1_{\{i\in I\}}$. The rank event depends on the type vector only through its tagged positions, so for a fixed $X$,
\[
 W_{\mathbf j,\mathbf b_\pm(X)}=\prod_{h=1}^r T_h^{(\mathbf b_\pm(X))_{j_h}}W_{\mathbf j}.
\]
Each shift factor is exactly
\[
 T_h^{(\mathbf b_\pm(X))_{j_h}}
 =1+\chi_{\rm seed}(j_h-X)V_h\pm\beta_{j_h-X}D_h .
\]
For disjoint $\mathcal D,\mathcal V\subseteq\{1,\ldots,r\}$ write
\[
 c_{\mathbf j}^{\mathcal D,\mathcal V}
 =\mathbb E_X\Bigl[\prod_{h\in\mathcal D}\beta_{j_h-X}\prod_{h\in\mathcal V}\chi_{\rm seed}(j_h-X)\Bigr],
 \qquad
 \partial_{\mathcal D,\mathcal V}=\prod_{h\in\mathcal D}D_h\prod_{h\in\mathcal V}V_h .
\]
Throughout, $\sum_{\mathbf j}$ runs over $1\le j_1<\cdots<j_r\le K$. Expanding the shift factors gives
\[
 \mathcal B_r=2\sum_{\substack{\mathcal D\cap\mathcal V=\varnothing\\ |\mathcal D|\text{ odd}}}
 \ \sum_{\mathbf j}c_{\mathbf j}^{\mathcal D,\mathcal V}\partial_{\mathcal D,\mathcal V}W_{\mathbf j}.
\]
The factor 2 records root types $\tau_\varnothing=\pm1$; the oddness restriction records cancellation of all even-valued root patterns under subtraction. For $\mathcal B_r^{\rm 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 $1\le v_1<\cdots<v_r\le l$ define
\[
 R_{\mathbf j}=\{v:|z_i(v)-\theta m\gamma_i|<m/8\text{ for }0\le 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 m\ge3m/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_{\mathbf j}$ and $\partial$. Disjointness gives the weighted identity
\[
 \Bigl\|\sum_{\mathbf j}\mathbf 1_{R_{\mathbf j}}c_{\mathbf j}\partial W_{\mathbf j}\Bigr\|_2^2
 =\sum_{\mathbf j}|c_{\mathbf j}|^2\|\mathbf 1_{R_{\mathbf j}}\partial W_{\mathbf j}\|_2^2
 \le\sum_{\mathbf j}|c_{\mathbf j}|^2\|\partial W_{\mathbf 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 $\partial W_{\mathbf j}$, the conditional binomial formula and Hoeffding's inequality give
\[
 \sum_{v\notin R_{\mathbf j}}W_{\mathbf j,{\rm shift}}(v)
 \le C_r f_{Km}(l)^{-1}e^{-c_* m/K}
 \le C_r\sqrt{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 $\partial$ is a fixed linear combination of shifted kernels. Using $\|\cdot\|_2\le\|\cdot\|_1$ for coefficient arrays, the discarded array has $\ell^2$ norm at most
\[
 \tau_r=C_rK^r\sqrt{Km}\,e^{-c_* m/K}.
\]
Thus the squared norm of the full array for this pattern is at most
\[
 2\sum_{\mathbf j}|c_{\mathbf j}|^2\|\partial W_{\mathbf j}\|_2^2+2\tau_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_0\delta^{-1})^r\tau_r=o(N^{-A})$ for every fixed $A$, uniformly over the finitely many $r<R_0$.

./trefs/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.

\begin{lemma}[Finite differences of a rank kernel]\label{lem:base-differences}
Fix $1\le r<R_0$, an admissible central count, and a tagged tuple in $K$ periods with coarse gaps $\gamma_i$. For disjoint $\mathcal D,\mathcal V\subseteq\{1,\ldots,r\}$ put $v'=|\mathcal D|+2|\mathcal V|$. Then
\[
 \Bigl\|\prod_{h\in\mathcal D}D_h\prod_{h\in\mathcal V}V_h\,W_{\mathbf j}\Bigr\|_{\ell^2}^2
 \le\delta^{-O_r(1)}\sqrt{Km}\,m^{-v'}\prod_{i=0}^r(m\gamma_i)^{-1/2}.
\]
The implicit constants depend only on $r$.
\end{lemma}
\begin{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=\tfrac12(T_h-1)(1+T_h^{-1}),\quad
 V_h=\tfrac12(T_h-1)^2T_h^{-1},\quad
 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 $g\ge1$, 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)\gtrsim\delta^2$. Parseval and Fourier inversion give
\[
 \|(\nabla^b f)_g\|_2^2\le C_b\delta^{-(2b+1)}g^{-b-1/2},\qquad
 \|(\nabla^b f)_g\|_\infty^2\le C_b\delta^{-(2b+2)}g^{-b-1}.
\]
All shifted lengths are comparable to $g_i$ for large $m$, since $r$ is fixed and $g_i\gtrsim m$.

Choose a largest coarse gap $e$, so its shifted length $\widetilde g_e\gtrsim_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 $\mathcal F$, the displayed bounds and $f_{Km}(l)^{-2}\lesssim\delta^2Km$ give
\[
 \|\mathcal F\|_2^2
 \le C_r\delta^{-(2v'+r)}Km\,\widetilde g_e^{-1-b_e}\prod_{i\ne e}\widetilde g_i^{-1/2-b_i}
 \le C_r\delta^{-(2v'+r)}\sqrt{Km}\,m^{-v'}\prod_{i=0}^r(m\gamma_i)^{-1/2}.
\]
The second line uses $\widetilde g_i\gtrsim m\gamma_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.
\end{proof}

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

./trefs/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.

./trefs/hmpw-2008.pdf

In the pattern expansion a singleton $\mathcal D=\{h\},\mathcal V=\varnothing$ 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_{\mathbf j}^{\mathcal D,\mathcal V}|\le(\chi_{\rm 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_{\rm seed}*\pi)(j)$. Lemma~\ref{lem:base-differences} and a first sum over tuples with $j_h=j$ give
\[
 \sum_{\mathbf j}|c_{\mathbf j}|^2\|\partial W_{\mathbf j}\|_2^2
 \le\delta^{-O_r(1)}m^{-v'}\sum_j\psi(j)^2
 \begin{cases}
  \Sigma_{r,h}(j),&\text{for a singleton},\\
  \Sigma_{r,h}^{\rm bd}(j),&\text{otherwise}.
 \end{cases}
\]

Lemma~\ref{lem:base-fixed-sums} and the two multiplier norms apply. Combining the finitely many patterns in the expansion and the analytic tail gives
\[
\begin{aligned}
 \|\mathcal B_r\|_2^2\le 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}\\
 &+\mathbf 1_{r\ge2}\,\omega^{-1}J^{-1/2}(Km)^{-1/2}m^{-7/2}\lambda^{r-2}\Bigr]
 +C_r\tau_r^2 .
\end{aligned}
\]
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 $\mathcal B_r^{\rm 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
\[
\begin{aligned}
 \|\mathcal B_r^{\rm pure}\|_2^2\le 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_r\tau_r^2 .
\end{aligned}
\]
For each fixed $r<R_0$, Lemma~\ref{lem:moment} converts the coefficient estimate to a score estimate:
\[
 \Bigl\|\sum_{1\le v_1<\cdots<v_r\le l}\mathcal B_r(v)\prod_{h=1}^r Z(Y_{v_h})\Bigr\|_{r_0}^2
 \le(C_1r_0\|Z\|_{r_0})^{2r}\|\mathcal B_r\|_2^2 .
\]
The analogous inequality 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)$, $\log\omega^{-1}=O(\Lambda)$, and $\Lambda=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+3\eta/2}\,N^{-7/4+7\eta/2+o(1)}
 =N^{-9/4+4\eta+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+5\eta/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}^2\le N^{-2.22},\qquad
 \|G_+-G_{\rm pure}\|_{r_0}^2\le N^{-1.4} .
\]

Let $\mathcal A$ be the joint event of typical metadata and $G_+^{\mathfrak d}(Y)\ge1/2$, and define
\[
 \mu_0=P_+(\,\cdot\mid\mathcal A),\qquad \nu_0=P_-(\,\cdot\mid\mathcal A).
\]
Lemma~\ref{lem:clipping} applies to the common conditional reference. The high-degree estimates supply $\rho=.0009\ge2^{-4B-10}$, and $2.22>2.20+.01$ supplies its difference margin. Hence
\[
 \nu_0\ll\mu_0,\qquad
 \|d\nu_0/d\mu_0-1\|_{L^{r_0}(\mu_0)}^2\le N^{-2.20},
\]
and conditioning changes each preliminary law by $o(\Delta)$ in total variation. By contraction under the same $\mathcal K_0$,
\[
 \TV(\mathcal K_0\mu_0,\Tr(x_0))\le o(\Delta)\le\Delta,\qquad
 \TV(\mathcal K_0\nu_0,\Tr(y_0))\le o(\Delta)\le\Delta
\]
for all large instances. This gives $E_0\le\Delta$ 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$,
\[
 (\sqrt{G_+}-\sqrt{G_{\rm pure}})^2\le2|G_+-G_{\rm pure}|^2.
\]
On the complement use $G_++G_{\rm 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_{\rm pure})\le2N^{-1.4}+o(\Delta)\le3N^{-1.4}.
\]
Projection by $\mathcal K_0$ gives the same bound for $H^2(\Tr(x_0),\Tr(W_0^P))$.

Set $k_0=\lceil CkP\rceil$, where $k=\lfloor\delta m\rfloor$ is the seed count. Since $k\sim\delta m$ and $C\delta>8$, one has $k_0\ge\ell_0$ for all large instances. Also,
\[
 \frac{k_0}{\ell_0}\le\frac{C\delta m}{2m-1}+\frac1{\ell_0}<C,
\]
using $\delta\le1/2$, $C\ge18$, and $\ell_0\to\infty$. Thus the common choice $M_B=1$ meets the level-zero count predicate, and $C=\exp(O(\Lambda))=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\sqrt{F\,H^2(\Tr(x_0),\Tr(W_0^P))}
 \le\sqrt{3F N^{-1.4}}=N^{-0.2+o(1)}=o(1).
\]
Lemma~\ref{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\bigl(\Tr(x_0^{k_0}),\Tr(x_0^{k_0+1})\bigr)\ge2/3-o(1)\ge\omega.
\]
Together with the length, distinction, score, and simulation estimates, this completes Proposition~\ref{prop:initial}.

\begin{proposition}[One amplification block]\label{prop:block}
For the scale parameters, let $1\le i\le D$ and suppose a level-$(i-1)$ pair satisfies Definition~\ref{def:invariant} with constants $C,\omega,M_B$. Set
\[
 C'=\max\{C,C_{\rm 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,\qquad E_i\le\Delta+(\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.
\end{proposition}
\begin{proof}
Fix $i$. The value $C'$ meets the hypothesis of Lemma~\ref{lem:lift}. Every preceding upper count bound remains true after replacing $C$ by $C'$, since its exponent $2Bh+M_B$ at a level $h\ge0$ 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(\Lambda)$. Write $C$ for $C'$ and use this common enlarged constant in the counts constructed and in later blocks.

Abbreviate
\[
 b=b_i,\quad N=N_i,\quad d=d_{i-1},\quad d'=d_i,\quad
 x=x_{i-1},\quad y=y_{i-1},\quad \ell=\ell_{i-1},\quad k=k_{i-1}.
\]
Within this block write $a_0=a_0(b)$ for the contraction exponent defined by $a_0(b)=(1+\epsilon)2^{-b}-\epsilon$. Thus $\ell\in[N^{a_0}/2,N^{a_0}]$. Since $r_i\le r_{i-1}$, the old score satisfies
\[
 \Bigl\|\frac{d\nu_{i-1}}{d\mu_{i-1}}-1\Bigr\|_{L^{r_i}(\mu_{i-1})}^2\le 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},\qquad
 s_*=\Bigl\lceil100(d_D+r_*+B+10)/\epsilon\Bigr\rceil,
 \qquad L=2^{s_*}.
\]
Let $\mathcal I=\{0,\ldots,L-1\}$ and define the signs by
\[
 \sum_{a\in\mathcal I}\sigma_a z^a=\prod_{v=0}^{s_*-1}(1-z^{2^v}).
\]
Extend $\sigma_a$ by zero outside $\mathcal I$ and put $\chi=\mathbf 1_{\mathcal I}$. The order $s_*=O_B((D+1)^2)$ is large enough for the signed smoothing at every block. Lemma~\ref{lem:scale-margins} gives, uniformly,
\[
 L^{O_B(r_*B)}=N^{o(\epsilon)},\qquad
 \exp\bigl(O_B((s_*+1)^2+(s_*+1)(D+1)\Lambda)\bigr)=N^{o(\epsilon)}.
\]
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$, $\tau\in\{+1,-1\}$, from $P_j$ consecutive level-$(j-1)$ atoms. Use type $+$ except at the labels $\lfloor P_j/2\rfloor+a$, $a\in\mathcal I$, where the type is $\tau\sigma_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^\epsilon$ paired chunks, choose the remaining exponents by
\[
 a_j(b)=2a_{j-1}(b)+\epsilon\qquad(1\le j\le b).
\]
This recurrence and the definition of $a_0(b)$ give
\[
 a_j(b)=(1+\epsilon)2^{j-b}-\epsilon\quad(0\le j\le b),\qquad 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)\epsilon,\qquad
 T_j=4\Bigl\lfloor N^{\kappa_j}/4\Bigr\rfloor\quad(1\le j\le b).
\]
The $\kappa_j$ are positive for all sufficiently large instances, uniformly in the block. Directly from the exponents,
\[
\begin{aligned}
 2\kappa_j-\kappa_{j+1}-\epsilon&=\epsilon\quad(1\le j<b),\\
 \kappa_b&>\epsilon,\qquad
 \kappa_j<a_{j-1}<a_j-a_{j-1}\quad(1\le j\le b).
\end{aligned}
\]
The first identity makes $T_j$ larger than the typical displacement from $T_{j+1}$ collections of about $N^\epsilon$ fair bits: the squared window width divided by that bit count has order $N^\epsilon$. The remaining inequalities leave room for the windows inside their words. Also
\[
 \sum_{j=1}^b\kappa_j<1,
\]
since $\kappa_j<a_{j-1}<2^{j-1-b}$; this bounds the number of vertices in the observation tree.

For $1\le j<b$ choose
\[
 P_j=\Bigl\lfloor N^{a_j}/S_{j-1}\Bigr\rfloor,\quad
 h_j=\lceil Ch_{j-1}P_j\rceil,\quad
 t_j=2\Bigl\lfloor P_j/[100(2h_{j-1}+1)]\Bigr\rfloor .
\]
For the root choose
\[
 J=\Bigl\lfloor\frac{\lfloor N/S_{b-1}\rfloor-T_b}{2h_{b-1}+1}\Bigr\rfloor,\quad
 P_b=J(2h_{b-1}+1)+T_b,\quad
 h_b=\lceil Ch_{b-1}P_b\rceil.
\]
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_j\in[N^{a_j}/2,N^{a_j}],\qquad
 P_j\asymp N^{a_j-a_{j-1}},\qquad T_j=o(P_j).
\]
The overlap counts remain within the declared uniform bound. Indeed $h_j\ge S_j$ by induction, and
\[
 \frac{h_j}{S_j}\le C\frac{h_{j-1}}{S_{j-1}}+1\le C^2\frac{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_j\le h_j\le C^{2B(i-1)+M_B+2j}S_j\le C^{2Bi+M_B}S_j\quad(0\le j\le b).
\]
In particular the extra count factor is at most $\exp(O_B((D+1)\Lambda))$.

Substitution in the definitions of $t_j$ and $J$ yields
\[
 e^{-O_B((D+1)\Lambda)}N^\epsilon\le t_j\le O(N^\epsilon)\quad(1\le 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>\epsilon$, and
\[
 N-S_b=O((h_{b-1}+1)S_{b-1})\le N^{2a_{b-1}+o(\epsilon)}=N^{1-\epsilon+o(\epsilon)}=o(N).
\]

The count overhead is $N^{o(\epsilon)}$ by the block losses, and $2a_{b-1}=1-\epsilon$. Thus also $S_b\in[N/2,N]$. Working backward from $\kappa_b>\epsilon$ gives $\kappa_j>\epsilon$ 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^+,\qquad y_i=U_b^-,\qquad \ell_i=S_b,\qquad 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.

\begin{lemma}[Signed binomial smoothing]\label{lem: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 $g\ge c_0\omega^2m$ trials, where $c_0>0$ is absolute and $m\to\infty$ as in the construction. Then
\[
\begin{aligned}
 \|\sigma*\pi\|_\infty&\le\exp(O((s_*+1)^2+(s_*+1)\Lambda))\,m^{-(s_*+1)/2},\\
 \|\sigma*\pi\|_2^2&\le\exp(O((s_*+1)^2+(s_*+1)\Lambda))\,m^{-s_*-1/2},\\
 \|\pi\|_\infty&\le O(\omega^{-1}m^{-1/2}).
\end{aligned}
\]
The norms use counting measure on the integers, and the implicit constants may depend on $c_0$.
\end{lemma}
\begin{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.
\end{proof}

\begin{lemma}[Overlap of the nested atoms]\label{lem:nested-overlap}
Under the input hypotheses of Proposition~\ref{prop:block}, the words and counts constructed above satisfy, for every $1\le j\le b$,
\[
 \ov\bigl(\Tr((U_j^+)^{h_j}),\Tr((U_j^+)^{h_j+1})\bigr)\ge\omega.
\]
\end{lemma}
\begin{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 inequality 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~\ref{lem:lift}, with base word $U_{j-1}^+$, overlap count $h_{j-1}$, replication $P_j$, and $F=h_j\ge 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 $\epsilon$, for $b=2$ and $d\ge2.20$,
\[
 a_0d-a_1>.03,\qquad 2a_0d>1.06.
\]
For $i>j_0$, one has $b=B$ and $d\ge2^B+2.20$, giving
\[
 a_0d>1+2^{-B}.
\]
Before the $\epsilon d$ correction the first two left sides are at least $.05$ and $1.10$, and the last is at least $1+2.20\cdot2^{-B}$. The bound $d\le2.20+(B/4)D$ and $\epsilon=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_j\le e^{O_B((D+1)\Lambda)}N$, $L^b=N^{o(\epsilon)}$, and $E_{i-1}\le n(D+1)\Delta$. In a preliminary block, $b=2$. At $j=1$ the same argument uses $h_1\le e^{O_B((D+1)\Lambda)}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(\epsilon)}+O(P_1E_{i-1}+\Delta),\qquad b=2,
\]
is required. The inequality $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=\lfloor(P_1-T_1)/2\rfloor$ 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),\qquad 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 $\mathcal 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}^{\otimes 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~\ref{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(\epsilon)},
\]
and the squared norm of the terms of degree at least two is at most $N^{-2a_0d+o(\epsilon)}$. 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}^2\le N^{-2a_0d+o(\epsilon)};
\]
indeed $t_1^{-s_*}\le N^{-\epsilon s_*}\exp(O_B((D+1)s_*\Lambda))$.

On typical metadata, the region $G_+<1/2$ has mass $o(\Delta)$ under both laws by the same moment argument as in Lemma~\ref{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(\epsilon)$. 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.
\end{proof}

./trefs/hoeffding-1963.pdf
./trefs/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.

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

Use a deterministic tree common to both hypotheses. Its root $\varnothing$ is the sole level-$b$ vertex. A level-$j$ vertex has $T_j$ children at level $j-1$, indexed by appending $h\in\{1,\ldots,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 $\lfloor P_b/2\rfloor+a$ has relative label $X+a$ in this central run, where
\[
 X=\lfloor P_b/2\rfloor-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$, $a\in\mathcal I$, lies in $[T_b/3,2T_b/3]$ for all orientations and all sufficiently large instances.

Fix $1\le j<b$ and a level-$(j+1)$ vertex $G$. Its $T=T_{j+1}$ children $Gu$, $1\le u\le 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=\lfloor(P_j-T_j)/2\rfloor,\qquad 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 $1\le v\le t_j$, a fair bit $E^{\rm loc}_{u,v}$ gives a pre chunk of $h_{j-1}+E^{\rm loc}_{u,v}$ pure $U_{j-1}^+$ atoms and a post chunk of $h_{j-1}+1-E^{\rm loc}_{u,v}$ such atoms. Also reserve global pairs between distant parts. For $1\le a\le T/4$ and $1\le v\le t_j$, a fair bit $E^{\rm glob}_{a,v}$ gives a pre chunk of $h_{j-1}+E^{\rm glob}_{a,v}$ atoms in part $a$ and a post chunk of $h_{j-1}+1-E^{\rm 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
\[
\begin{aligned}
 H_{Gu}&=\sum_{v=1}^{t_j}(E^{\rm loc}_{u,v}-1/2),\\
 V_{Gu}&=\sum_{a=1}^{T/4}\sum_{v=1}^{t_j}\bigl(\mathbf 1_{a\le u}-\mathbf 1_{T+1-a<u}\bigr)(E^{\rm glob}_{a,v}-1/2),\\
 Y_{Gu}&=V_{Gu}+H_{Gu}.
\end{aligned}
\]
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^{\rm glob}_{a,v}-1/2)
 \qquad\text{when }T/4<u\le3T/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_\varnothing=+1$ or $-1$ under the two hypotheses. At the root put
\[
 \tau_h=1-\chi(h-X)+\sigma_{h-X}\tau_\varnothing .
\]
For every other level-$j$ vertex $I$, $j\ge1$, put
\[
 \tau_{Ih}=1-\chi(h-w_j+Y_I)+\sigma_{h-w_j+Y_I}\tau_I,
 \qquad w_j=\lfloor P_j/2\rfloor-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 $\widetilde\mu_i,\widetilde\nu_i$ be the two unconditioned surrogate laws. A common kernel $\mathcal K_{\rm tree}$ applies $\mathcal 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
\[
 \mathcal F=\bigl\{|Y_I|\le T_j/8\text{ for every level-$j$ vertex }I,\ 1\le j<b\bigr\}.
\]

\begin{lemma}[Simulation of a genuine trace]\label{lem:tree-simulation}
For the unconditioned surrogate laws and the common projection above,
\[
 \TV(\mathcal K_{\rm tree}\widetilde\mu_i,\Tr(U_b^+))\le o(\Delta)+\Bigl(\prod_{j=1}^bT_j\Bigr)E_{i-1},
 \qquad
 \TV(\mathcal K_{\rm tree}\widetilde\nu_i,\Tr(U_b^-))\le o(\Delta)+\Bigl(\prod_{j=1}^bT_j\Bigr)E_{i-1}.
\]
All error terms are uniform in $i$.
\end{lemma}
\begin{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 inequality and the scale estimates give
\[
 \Prob(|Y_I|>T_j/8)\le2\exp\bigl(-c\,T_j^2/(T_{j+1}t_j)\bigr)\le2\exp(-c'N^\epsilon)
\]
for absolute positive constants at all sufficiently large instances. The bound $\sum\kappa_j<1$ controls the number of vertices by $O_B(N)$. A union bound therefore gives
\[
 \Prob(\mathcal F^c)\le\exp(-N^{\epsilon/2})=o(\Delta).
\]
The last comparison follows uniformly from Lemma~\ref{lem:scale-margins}: $\epsilon\log N\ge\epsilon\log N_0$ dominates $\log\log n+\log(d_D+B+1)$, so $N^{\epsilon/2}$ dominates $\log\Delta^{-1}$.

./trefs/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 $\mathcal 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.
\end{proof}

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

Let $\mathcal L$ be the leaf set and use the conditional reference
\[
 Q=\mu_{i-1}^{\otimes\mathcal L}.
\]
For $v\in\mathcal L$, let $Z_v$ be the old likelihood score at that coordinate. Under $Q$ these variables are independent and centred, with $\|Z_v\|_{r_i}^2\le 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_{\mathfrak d}\prod_{v\in\mathcal L}\Bigl(1+\frac{1-\tau_v^\pm}{2}Z_v\Bigr).
\]
For every supported $\mathfrak d$, these densities integrate to one because these are mixtures of product probability laws. The superscript on $\tau$ records the root type.

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

Fix a typical $\mathfrak 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 $L\prod_{j=2}^bT_j$. The margin between the old score and this number of possible positions is
\[
 \lambda_d:=a_0d-\sum_{j=2}^b\kappa_j>8g_B(d+1),\qquad g_B:=2^{-4B-10}.
\]
The two depth phases supply this bound. Since $\sum_{j=2}^b\kappa_j<1-2^{1-b}$ and $a_0\ge2^{-b}-\epsilon$, for $b=2$ and $d\ge2.20$ one has $\lambda_d>d/4-1/2-\epsilon d$; for $b=B$ after the preliminary phase, $d\ge2^B+2.20$ and $\lambda_d>2^{-B}(d-2^B+2)-\epsilon 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 $\epsilon$ leave the bound uniform.

At fixed bits, Lemma~\ref{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{L\prod_{j=2}^bT_j}{r}
 \le\bigl(N^{-\lambda_d+o(\epsilon)}\bigr)^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},\qquad
 \|\text{degree }\ge r_*\text{ part of }G_\pm\|_{r_i}^2\le N^{-d'-1}.
\]
For the second inequality, $r_*g_B(d+1)>d'+3$ leaves the required margin. Only the fixed degrees $1\le r<r_*$ remain.

Fix such a degree $r$ and a leaf subset $\mathcal S$ of size $r$. Its coefficient in $G_+-G_-$ is
\[
 c(\mathcal S)=\E_{\mathfrak d}\Bigl[\prod_{v\in\mathcal S}\frac{1-\tau_v^+}{2}-\prod_{v\in\mathcal S}\frac{1-\tau_v^-}{2}\Bigr].
\]
Lemma~\ref{lem:moment} reduces the squared norm of this degree to
\[
 \Bigl\|\sum_{|\mathcal S|=r}c(\mathcal S)\prod_{v\in\mathcal S}Z_v\Bigr\|_{r_i}^2
 \le(C_1r_i)^{2r}N^{-a_0dr}\sum_{|\mathcal S|=r}|c(\mathcal S)|^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 $\mathcal S$, including that leaf itself.

For a vertex $I$ and one of its child labels $h$, write
\[
 \xi_{I,h}=\begin{cases}h-X,&I=\varnothing,\\ h-w_j+Y_I,&I\text{ at level }j<b,\end{cases}
 \qquad \chi_{Ih}=\chi(\xi_{I,h}),\quad \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 $t\in\{-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:\,Ih\in\mathcal S}(\chi_{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\text{ occupied}}F_{Ih}(1-\chi_{Ih}+\sigma_{Ih}t),\qquad t\in\{-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_I\in\{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_\varnothing(+1)-F_\varnothing(-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(\mathcal F^c\mid D_0=\mathfrak d)\le\exp(-N^{\epsilon/4})$ in absolute value. There are at most $O_B(N^r)$ label assignments by $\sum\kappa_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\bigl(O((s_*+1)^2+(s_*+1)\Lambda)\bigr)
 \begin{cases}t_j^{-(s_*+1)/2},&1\le j<b,\\ J^{-(s_*+1)/2},&j=b.\end{cases}
\]
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)\Lambda)}N^{-\epsilon(s_*+1)}.
\]
Since $\epsilon 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 $r\ge2^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 $\mathcal I$. Define the nonnegative anchor kernel
\[
 f=\prod_{I\text{ 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_{\mathfrak d}\Bigl[f\prod_{\text{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 $\mathbf h$ of the $e$ extra leaf labels, let $a_{\mathbf 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_{\mathbf h}a_{\mathbf h}\le L^e\E_{\mathfrak d}f,
 \qquad
 \sum_{\mathbf h}a_{\mathbf h}^2\le\Bigl(\sum_{\mathbf h}a_{\mathbf h}\Bigr)^2\le L^{2e}(\E_{\mathfrak d}f)^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 $\mathcal S$.

It remains to sum $(\E_{\mathfrak d}f)^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_{\rm out}^{\mathfrak d}(z)=\E_{\mathfrak d}\chi(z-X).
\]
Its $\ell^1$ mass is $L$, and its supremum is at most $O(L\omega^{-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\text{ valid root}\\\text{forced labels}}}K_{\rm out}^{\mathfrak d}(u_1)^2\le\Gamma_{\rm out},
 \qquad \Gamma_{\rm out}=O(L^3\omega^{-1}J^{-1/2}).
\]

For a fixed forced labeling, let $\mathcal G_j$ be its forced level-$(j+1)$ parents. Each $G\in\mathcal G_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
\[
 \mathcal H_{j,G;u_1,u_2}^{\mathfrak d}(z_1,z_2)
 =\E_{\mathfrak d}\bigl[\chi(z_1-w_j+Y_{Gu_1})\chi(z_2-w_j+Y_{Gu_2})\bigr].
\]
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=\mathfrak d$ gives, for this fixed forced labeling,
\[
 \E_{\mathfrak d}f=K_{\rm out}^{\mathfrak d}(h_\varnothing)\prod_{j=1}^{b-1}\prod_{G\in\mathcal G_j}
 \mathcal H_{j,G;u_1(G),u_2(G)}^{\mathfrak 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 $\mathcal 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 $\mathfrak 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,
\[
 \|\mathcal H_{j,G;u_1,u_2}^{\mathfrak d}\|_{\ell^1(\mathbb Z^2)}\le L^2,\qquad
 \|\mathcal H_{j,G;u_1,u_2}^{\mathfrak d}\|_{\ell^\infty(\mathbb Z^2)}
 \le C_{10}L^2\omega^{-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(L\omega^{-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(L\omega^{-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'\in\mathbb Z\\ 0<z_1'-z_1<L,\ 0<z_2'-z_2<L}}
 \mathcal H_{j,G;u_1,u_2}^{\mathfrak d}(z_1,z_2)^2\le\Gamma_j,
 \qquad \Gamma_j=C_{11}L^6\omega^{-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 $\mathcal R_j(G;u_1,u_2)$ be the sum of the squares of the products of all their interior $\mathcal H$ factors, including the factor of $G$, over all valid forced descendant labelings. Set $\mathcal R_0=1$. Splitting the descendant labels at their first two pairs gives the exact recurrence
\[
 \mathcal R_j(G;u_1,u_2)
 =\sum_{\substack{(z_1,z_1'),(z_2,z_2')\\\text{valid at level }j}}
 \mathcal H_{j,G;u_1,u_2}^{\mathfrak d}(z_1,z_2)^2\prod_{v=1}^2\mathcal R_{j-1}(Gu_v;z_v,z_v')
 \le\Gamma_j\Bigl(\sup_{G',v_1,v_2\text{ valid}}\mathcal R_{j-1}(G';v_1,v_2)\Bigr)^2 .
\]
For the inequality, 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_{\text{valid forced labels}}(\E_{\mathfrak d}f)^2
 \le\Gamma_{\rm 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(\epsilon)}$ by Lemma~\ref{lem:scale-margins} and the block losses. The squared degree contribution of a branching term is therefore at most
\[
 N^{o(\epsilon)}J^{-1/2}\prod_{j=1}^{b-1}\bigl[T_{j+1}^{-1/2}t_j^{-1}\bigr]^{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
\[
 \epsilon/2+\sum_{j=1}^{b-1}2^{b-j-1}(\kappa_{j+1}/2+\epsilon)+2^ba_0d-o(\epsilon)
 \ge d+(b-1)/4-\bigl[(2^b-1)d+3b\,2^{b-1}\bigr]\epsilon-o(\epsilon)>d'+.03.
\]
For this calculation the local exponents give $\kappa_{j+1}=2^{j-b}-(6\cdot2^j-2-2^{j-b})\epsilon$. 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 $d\le2.20+(B/4)D$ and the choice of $\epsilon$ 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}^2\le N^{-d'-.01}$, which proves Lemma~\ref{lem:tree-score}.

Lemma~\ref{lem:clipping} now applies to the preliminary laws $\widetilde\mu_i,\widetilde\nu_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~\ref{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_i\le\Delta+(\ell_i/\ell)E_{i-1},\qquad
 \frac{E_i}{\ell_i}\le\frac{\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~\ref{prop:block}. Starting from Proposition~\ref{prop:initial} and iterating the block proves Proposition~\ref{prop:construction}.
\end{proof}

Proposition~\ref{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.

\begin{lemma}[Restoration and padding]\label{lem:restoration}
For the scale parameters, there are distinct words $x,y\in\{0,1\}^n$ such that, for every positive integer $m$,
\[
 \TV\bigl(\Dcal_q(x)^{\otimes m},\Dcal_q(y)^{\otimes m}\bigr)\le\sqrt{m n^{-d_D}}+2mn(D+1)\Delta .
\]
In particular,
\[
 \TV\bigl(\Dcal_q(x),\Dcal_q(y)\bigr)\le n^{-d_D/2}+2n(D+1)\Delta .
\]
\end{lemma}
\begin{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_D\le 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.

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

The final moment estimate, monotonicity of norms on a probability space, and $r_D\ge2$ give
\[
 H^2(\mu_D,\nu_D)\le\Bigl\|\frac{d\nu_D}{d\mu_D}-1\Bigr\|_{L^2(\mu_D)}^2\le n^{-d_D}.
\]
Tensorisation and $\TV\le 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.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:tv}]
Fix $q\in(0,1)$. Choose $B=2$, $\zeta=1/2$, and auxiliary coefficients $c=1/(80\log2)<c_+=1/(40\log2)$ once, independently of $A$. The setup inequality holds because its left side is $1/(20\log2)$. The construction remains valid with these fixed parameters; its proof requires only their positivity and the eventual inequalities. In this case $\delta>0$ is fixed, $D\to\infty$, and $d_D=2.20+0.20D\to\infty$. 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)}\longrightarrow0.
\]
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~\ref{thm:main}, whose proof does not use Theorem~\ref{thm:tv}; indeed $c\log(q^3\log n)\to\infty$ for any fixed admissible $c>0$.
\end{proof}

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 $\varphi$ is the conditional probability of choosing the first hypothesis, its average success is
\[
 \tfrac12\bigl(1+\E_P\varphi-\E_Q\varphi\bigr)\le\tfrac12(1+\TV(P,Q)),\qquad 0\le\varphi\le1 .
\]
Trace-reconstruction versions of this two-point comparison appear in Appendix~A.2 of Holden and Lyons.

./trefs/holden-lyons-2020.pdf

Fix $0<c<c_+<1/(4\log2)$ and choose $B,\zeta$ so that
\[
 \alpha:=\frac{(1-\zeta)((B-1)/4-.05)}{B\log2}>c_+ .
\]
The $j_0$ preliminary blocks have a fixed number depending only on $B$, so
\[
 d_D=\alpha\log H_{\rm del}+O_B(1).
\]
For an absolute constant $a>0$ sufficiently small, the product bound with $m\le 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_{\rm del}=\log(q^3\log n)+O(1)$ uniformly in $q$. The strict inequality $\alpha>c_+$ therefore implies
\[
 a n^{d_D}\ge n^{c_+\log(q^3\log 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.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Fix $s\in(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=\lfloor n/g\rfloor$ 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^3\log N\sim q^3\log n\to\infty$ and $\log N=\log n+O_g(1)$, the construction and testing bounds apply to each gadget. Moreover
\[
 \frac{(\log N)\log(q^3\log N)}{(\log n)\log(q^3\log n)}\longrightarrow1,
\]
so $c_+>c$ gives
\[
 N^{c_+\log(q^3\log N)}\ge n^{c\log(q^3\log 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.

./trefs/mcgregor-price-vorotnikova-2014.pdf
./trefs/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,\ldots,\theta_g)$ and separated data $z=(z_1,\ldots,z_g)$,
\[
 \Prob(\theta\mid z)=\prod_{j=1}^g\Prob(\theta_j\mid 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 $m\le n^{c\log(q^3\log n)}$, the two threshold inequalities 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.
\end{proof}

\end{document}