\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 $00.
\]
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.

./pdf/trefs/levenshtein-2001-ieee-slides.pdf
./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.

./pdf/trefs/mcgregor-price-vorotnikova-2014.pdf
./pdf/trefs/holden-lyons-2020.pdf
./pdf/trefs/holden-lyons-errata-2022.pdf
./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.

./pdf/trefs/hmpw-2008.pdf
./pdf/trefs/dos-2017.pdf
./pdf/trefs/nazarov-peres-2017.pdf
./pdf/trefs/chase-2021-upper.pdf
./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.

./pdf/trefs/chen-de-lee-servedio-sinha-2021.pdf
./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.

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

./pdf/trefs/allouche-shallit-1999.pdf
./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 $0c_+>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_0j_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}

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

./pdf/trefs/mcgregor-price-vorotnikova-2014.pdf
./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.

./pdf/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$.

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

./pdf/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<\cdots0$. 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<\cdots0\\\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.

./pdf/trefs/holden-lyons-2020.pdf
./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