% =====================================================================
% Uniform quasipolynomial-time trace reconstruction
% A self-contained, student-friendly write-up of the full proof.
% Compile with pdflatex. Every symbol is defined before it is used.
% =====================================================================
\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype,enumitem,xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,positioning,calc,decorations.pathreplacing}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\setlist{itemsep=3pt,topsep=5pt}
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\RR}{\mathbb R}
\newcommand{\CC}{\mathbb C}
\newcommand{\ii}{\mathrm i}
\newcommand{\EE}{\mathcal E}
\newcommand{\abs}[1]{\lvert #1\rvert}
\newcommand{\norm}[1]{\lVert #1\rVert}
\DeclareMathOperator{\re}{Re}

\title{Uniform quasipolynomial-time trace reconstruction}
\author{}
\date{}

\begin{document}
\maketitle

\begin{abstract}
A deletion trace of a binary string $x$ is obtained by keeping each
position independently with probability $p$ and deleting it otherwise,
then writing the kept bits in order. The kept bits keep no record of
where they came from. \emph{Trace reconstruction} asks: given several
independent traces of an unknown $x$, how many traces are needed, and
how fast can $x$ be recovered? We give one explicit algorithm that
works for every string $x$, for every known rational retention
probability $p$, with success probability at least $2/3$. If $p$ is
held fixed, both the number of traces and the running time are
quasipolynomial in the string length $n$ (i.e.\ of the form
$\exp(\text{polylog}(n))$). The bound is also stated uniformly in $p$:
the running time is a fixed polynomial in the number of traces the
theorem allows. When the deletion probability is at most
$n^{-\varepsilon}$ for a fixed $\varepsilon>0$, everything becomes
polynomial. This document proves that theorem completely.
\end{abstract}

\section{Introduction}\label{sec:intro}

\subsection*{The problem in one paragraph}
Fix a binary string $x=x_1\cdots x_n\in\{0,1\}^n$. A \emph{deletion trace}
is the random string produced by the following experiment: walk through
the positions $1,2,\ldots,n$; keep position $i$ with probability $p$
and drop it with probability $q=1-p$, independently at each $i$; the
kept bits, in their original order, form the trace. For example, if
$x=1011$ and the deletion removes positions $2$ and $4$, the resulting
trace is $11$. The trace reports
its own length and its bits, but nothing about which original positions
survived. An algorithm is handed $n$, the value $p$ (as a rational
number), and a stream of independent traces of $x$, and must output
$x$. We want an algorithm that succeeds with probability at least $2/3$
\emph{for every} $x$ (a worst-case guarantee), and we want to count the
two resources: how many traces it reads, and how many bit operations it
performs.

\subsection*{Why the problem is subtle}
If the trace were the input up to independent bit flips, we could
denoise one coordinate at a time. Here the trouble is different: the
same trace rank can come from many different input positions as the
random deletions shift everything. So the positions we want are
``smeared out'', and local statistics do not suffice. What saves us is
a family of carefully chosen \emph{nonlocal} statistics (products of
bits at ranks that may be far apart) together with a way to test, bit
by bit, whether a partial guess is consistent with the data.

\subsection*{Main result}
Let $n\ge 2$ and let $p=a/b\in(0,1]$ be a rational in lowest terms.
Write $L$ for the total number of bits in $a$ and $b$ when written in
binary, so $L$ is the length of the honest input to an algorithm.
Write $q=1-p$. All logarithms are natural unless a base is shown.
Define the \emph{budget proxy}
\begin{equation}\label{eq:budget}
\begin{split}
  \mathsf X(n,p) &=
  \begin{cases}
    1+\dfrac{\log n}{1+\log(1/q)}, & q>0,\\[6pt]
    1, & q=0,
  \end{cases}\\[4pt]
  B(n,p) &= p^{-1}\,(\log n)\,\mathsf X(n,p)^2\,
            \bigl(1+\log \mathsf X(n,p)\bigr)^6 .
\end{split}
\end{equation}

\begin{theorem}[Uniform trace reconstruction]\label{thm:main}
There are absolute constants $C,c\ge 1$ and one randomized multitape
Turing machine $\mathcal A$ with the following property. Take any
$n\ge 2$, any rational $p\in(0,1]$, and any $x\in\{0,1\}^n$. Given
$n$ and $p$ in binary and access to independent deletion traces of $x$
with retention probability $p$, the machine
\begin{enumerate}[label=(\roman*)]
\item reads at most $M_C(n,p)=\bigl\lceil \exp(C\,B(n,p))\bigr\rceil$
      traces,
\item outputs a string in $\{0,1\}^n$, and
\item returns $x$ with probability at least $2/3$.
\end{enumerate}
Moreover, for \emph{every} internal sequence of random bits and
\emph{every} stream of well-formed traces of strings of length at most
$n$, the machine halts within
\[
  \bigl(n+L+M_C(n,p)\bigr)^c
\]
bit operations. This count already includes reading every trace bit
and every delimiter, all preprocessing, all finite-precision arithmetic,
and writing the output. The only thing not counted is the external
generation of the traces.
\end{theorem}

\subsection*{Reading the bound}
For a fixed $p$, plugging $q>0$ constant into \eqref{eq:budget} gives
$\mathsf X(n,p)=O(\log n)$ and hence
$B(n,p)=O_p\bigl((\log n)^3 (1+\log\log n)^6\bigr)$. Since
$M_C=\exp(CB)$, the number of traces is
$\exp\bigl(O_p((\log n)^3(1+\log\log n)^6)\bigr)$, which is
quasipolynomial in $n$. The running time bound
$(n+L+M_C)^c$ is then also quasipolynomial. So both resources are
quasipolynomial for fixed $p$. When instead $q\le n^{-\kappa}$ for a
fixed $\kappa>0$, one has $1+\log(1/q)\ge \kappa\log n$, so
$\mathsf X(n,p)\le 1+1/\kappa$ is bounded and $p^{-1}$ is bounded by a
constant depending only on $\kappa$; then $B(n,p)=O_\kappa(\log n)$
and everything is polynomial in $n$.

\subsection*{How the proof is organised}
The proof is one long chain. We first build the object the decoder
tests against: a family of ``positive moment functionals'', a convex
relaxation of the set of genuine probability laws on strings. The heart
of the argument (Section~\ref{sec:separation}) is a
\emph{separation theorem}: any positive moment functional that insists
on a wrong bit at some position must disagree, by an exponentially
small but nonzero amount, with one of the observable trace statistics.
This is an analytic fact, proved by moving a local signal out to large
distance scales (Section~\ref{sec:multiscale} and~\ref{subsec:contour-conversion})
and then rotating it into the trace generating function
(Section~\ref{sec:separation}). The decoder (Section~\ref{sec:decoding})
turns separation into an algorithm: it tests one bit at a time using
exact rational feasibility, and we bound the cost. Section~\ref{sec:history}
records the lineage of these ideas.

\section{History and relation to earlier work}\label{sec:history}

Reconstructing a sequence from corrupted copies has a long
information-theoretic history. Levenshtein studied reconstruction under
several combinatorial and probabilistic channel models
\cite{Levenshtein2001}. Batu, Kannan, Khanna, and McGregor introduced
reconstruction from independent random deletion traces into theoretical
computer science, motivated partly by sequence alignment
\cite{BKKM2004}. What makes the deletion channel different from
coordinatewise denoising is that a single trace rank can come from many
input positions.

For a fixed deletion probability, Holenstein, Mitzenmacher, Panigrahy,
and Wieder proved a worst-case sample bound of
$\exp(\widetilde O(\sqrt n))$ \cite{HMPW2008}. In independent STOC 2017
papers, De, O'Donnell, and Servedio and, separately, Nazarov and Peres
proved $\exp(O(n^{1/3}))$ bounds together with matching limitations for
methods that use only trace means \cite{DOS2019,NP2017}. Their
complex-analytic approach ties deletion statistics to
bounded-coefficient polynomials; analytic inequalities of Borwein and
Erd\'elyi are in the background of this method \cite{BE1997}. That
mean-based lower bound restricts a method, not arbitrary trace
algorithms.

Chase improved the general sample upper bound to
$\exp(O(n^{1/5}\log^5 n))$ \cite{Chase2021Upper}. On the lower-bound
side, Holden and Lyons proved an almost-$n^{5/4}$ bound and Chase
strengthened it to $\Omega(n^{3/2}/\log^7 n)$ for fixed deletion
probability \cite{HoldenLyons2020,Chase2021Lower}. Burudgunte, Valiant,
and Wang then proved the sample bound
$\exp\bigl(p^{-7/3}(\log_2 n)^{c_0}\bigr)$ for an absolute $c_0$,
using nonlocal low-order statistics and a multiscale propagation
argument \cite[Theorem~43]{BVW2026}. Their bound is quasipolynomial
when $p^{-1}$ is polylogarithmic in $n$. Theorem~\ref{thm:main} builds
on this strategy and provides an explicit uniform reconstruction
algorithm with the displayed bit-complexity bound.

Sample complexity and reconstruction time need different arguments.
At fixed confidence, maximum likelihood reconstructs worst-case using
at most $O(n)$ times the optimal sample count, but evaluating it over
all candidate strings requires a large search
\cite[Corollary~1.1 of the full version]{CGLSZ2024}. Burudgunte,
Valiant, and Wang explicitly separate testing two known strings from
reconstructing an unknown string, and leave quasipolynomial-time
reconstruction open for their approach \cite[Section~1]{BVW2026}. The
extra separation proved here concerns \emph{every} positive
semidefinite moment completion of a wrong prefix. It enables
constructive feasibility tests in place of a search over complete
strings. Earlier polynomial-time results already cover low-deletion
regimes \cite{CDLSS2021LowDeletion}.

The use of nonlocal statistics is essential to compare with known
barriers. Chen, De, Lee, and Servedio proved strong lower bounds for
statistical queries restricted to short \emph{consecutive} trace blocks
\cite{CDLS2024}. Our statistics involve few ranks but may span the whole
trace, as in \cite{BVW2026}. The generating-function identity used to
transfer them from input coordinates has antecedents in higher-order
trace reconstruction \cite{CDLSS2021Smoothed,Chase2021Upper}.

The positive moment relaxation is a Boolean instance of the semidefinite
moment and sum-of-squares framework \cite{Lasserre2001,Parrilo2000}.
The finite feasibility iteration is related to the classical relaxation
methods of Agmon and Motzkin--Schoenberg \cite{Agmon1954,MotzkinSchoenberg1954}.
We prove the analytic separation and the rational implementation
directly; no external trace-reconstruction or optimization theorem is
used.

\section{Moment relaxations and prefix separation}\label{sec:setup}

We now describe exactly what the decoder measures and exactly what
convex family it tests against. Everything the algorithm ever sees is a
\emph{trace statistic}: an expected product of a few trace ranks. Because
we cannot know which input positions produced those ranks, the algorithm
treats these statistics as a system of linear equations with a
semidefinite (positivity) condition, and solves for a \emph{completion}
of a partial guess. This section sets up that relaxation and states the
separation theorem that makes the relaxation useful.

Throughout, $[n]=\{1,\ldots,n\}$ and $X_1,\ldots,X_n$ are formal Boolean
variables standing for the unknown bits. Products are always reduced by
$X_i^2=X_i$ (a bit times itself is itself), so every polynomial has
degree at most the number of distinct variables it mentions.

\subsection{Observable trace moments}

Fix a nonempty set of ranks $I=\{\ell_1<\cdots<\ell_k\}\subseteq[n]$. The
corresponding \emph{trace observable} is the product of the bits that sit
at those ranks in a single trace; if the trace is shorter than $\ell_k$,
the observable is $0$. Let $T_I(X)$ be its expectation over the
deletion channel, viewed as a polynomial in the input bits:
\begin{equation}\label{eq:trace-moment}
  T_I(X)=\sum_{i_1<\cdots<i_k} c_{I;\,i_1,\ldots,i_k}\,X_{i_1}\cdots X_{i_k}.
\end{equation}
The coefficient $c_{I;\,i_1,\ldots,i_k}$ is the probability that the
input positions $i_1,\ldots,i_k$ land at trace ranks
$\ell_1,\ldots,\ell_k$. As the input tuple varies these events are
disjoint, so
\begin{equation}\label{eq:coeff-bounds}
  c_{I;\,i_1,\ldots,i_k}\ge 0,\qquad
  \sum_{i_1<\cdots<i_k} c_{I;\,i_1,\ldots,i_k}\le 1.
\end{equation}
Thus $T_I$ has degree at most $k$, nonnegative coefficients, and
coefficient sum at most one; its coefficients are rational when $p$ is
rational. The algorithm estimates $T_I(x)$ by averaging the observable
over independent traces. It never learns the coefficients' input
positions from the data, only the numeric value.

\subsection{Positive moment arrays}

The following Boolean moment relaxation is a special case of the
semidefinite moment and sum-of-squares frameworks of
Lasserre \cite[Section~2]{Lasserre2001} and
Parrilo \cite[Sections~4.2--4.3]{Parrilo2000}. We use only the defining
positivity condition and its elementary consequences, all proved below.

Fix a proposed prefix $u\in\{0,1\}^d$ and a degree bound $D\ge 1$. On the
remaining positions $U=\{d+1,\ldots,n\}$ introduce sign variables
$Y_i=2X_i-1$, so that $Y_i^2=1$ and $X_i=(1+Y_i)/2$. A \emph{moment
array} assigns real numbers $m_J$ to subsets $J\subseteq U$ with
$|J|\le 2D$, with $m_\varnothing=1$, subject to the single
positive-semidefiniteness condition
\begin{equation}\label{eq:moment-matrix}
  \mathcal M_D(m)=\bigl(m_{I\triangle J}\bigr)_{\substack{I,J\subseteq U\\
     |I|,|J|\le D}}\succeq 0,
\end{equation}
where $\triangle$ is symmetric difference. Only subsets that actually
exist are indexed, so the definition still makes sense when $D>|U|$ or
$U$ is empty.

The array defines a functional $\EE$ on polynomials of degree at most
$2D$ as follows: substitute $X_i=u_i$ for $i\le d$; expand each remaining
bit as $(1+Y_i)/2$; reduce $Y_i^2=1$; then set
$\EE\bigl[\prod_{i\in J}Y_i\bigr]=m_J$ and extend complex-linearly. Call
$u\mapsto\EE$ a \emph{positive moment functional of order $2D$ fixing
$u$}. The word ``positive'' asserts \eqref{eq:moment-matrix}, not the
existence of an actual probability law realising all these moments; any
feasible array, even a fictitious one, is allowed in the test.

\begin{lemma}[Elementary moment bounds]\label{lem:moment-bounds}
For every array obeying \eqref{eq:moment-matrix}:
\begin{enumerate}[label=(\alph*)]
\item $\abs{m_J}\le 1$ for every $|J|\le 2D$;
\item under $\EE$, the value of any product of at most $2D$ distinct
      input bits has magnitude at most one;
\item on polynomials of degree at most $D$, the form
      $\langle P,R\rangle_{\EE}=\EE[P\,\overline R]$ is a positive
      semidefinite Hermitian form, linear in its first argument; it
      satisfies Cauchy--Schwarz and becomes an inner product after
      quotienting by its zero-norm subspace.
\end{enumerate}
\end{lemma}

\begin{proof}
The empty moment equals one. Any nonempty $J$ with $|J|\le 2D$ splits as
$J=I\sqcup K$ with $|I|,|K|\le D$. In \eqref{eq:moment-matrix} the
$I,K$ principal submatrix has diagonal entries one and off-diagonal
entry $m_J$; positive semidefiniteness of a real symmetric matrix with
unit diagonal forces $|m_J|\le 1$. This is (a). For (b), write each
unfixed bit as $(1+Y_i)/2$; a product of $t$ unfixed bits becomes
$2^{-t}\prod(1+Y_i)$, a convex combination of sign monomials of the
$Y_i$, each of modulus at most one by (a); fixed bits simply remove
factors or send the product to zero. For (c), the Gram-form reading of
the real symmetric positive semidefinite matrix \eqref{eq:moment-matrix},
extended to complex coefficient vectors, gives the stated form;
Cauchy--Schwarz follows by applying positivity to $P+zR$ for $z\in\CC$,
and it shows every zero-norm vector is orthogonal to every vector, so
the quotient is well defined.
\end{proof}

Now fix the true input $x\in\{0,1\}^n$ and a prefix $u$ of length $d$
that is wrong exactly at its last position,
\begin{equation}\label{eq:wrong-prefix}
  u_i=x_i\ \ (i<d),\qquad u_d=1-x_d.
\end{equation}
For any positive moment functional fixing $u$, define the discrepancy
\begin{equation}\label{eq:Delta}
  \Delta[P]=\EE[P]-P(x).
\end{equation}
Because $u$ agrees with $x$ before $d$, one has $\Delta[X_d]=\pm 1$;
because every monomial using only positions strictly before $d$ agrees
with $x$ there, $\Delta[P]=0$ whenever $P$ mentions only positions
$<d$. If $P=\sum_A c_A\prod_{i\in A}X_i$ has degree at most $2D$, then
point (b) of Lemma~\ref{lem:moment-bounds} gives the useful bound
\begin{equation}\label{eq:delta-coefficients}
  \abs{\Delta[P]}\le 2\sum_A \abs{c_A}.
\end{equation}

For $p<1$ introduce the bookkeeping quantities
\begin{equation}\label{eq:aux-parameters}
  q_*=\max(q,\,1/n),\qquad
  Q=1+\log(1/q_*),\qquad
  Y=1+\frac{\log n}{Q}.
\end{equation}
When $q\ge 1/n$ these give $Y=\mathsf X(n,p)$ exactly. When $q<1/n$
they give $1\le \mathsf X(n,p)\le Y<2$. In all cases
\begin{equation}\label{eq:aux-comparisons}
  \mathsf X(n,p)\le Y\le 2\,\mathsf X(n,p),\qquad
  QY=Q+\log n\le C\log n
\end{equation}
for an absolute constant $C$, since $n\ge 2$.

\begin{theorem}[Separation from a wrong prefix]\label{thm:separation}
There exist absolute constants $C_{\mathrm{sep}}\ge 1$ and an integer
$H\ge 1$ with the following property. For $n\ge 2$ and $0<p<1$ define
\[
  D_*=4^{\lceil \log_2 Y\rceil+H}\le 4^{H+1}Y^2
\]
using \eqref{eq:aux-parameters}. Take any $x\in\{0,1\}^n$, any
$d\in[n]$, and any positive moment functional of order $2D$ fixing
$x_1,\ldots,x_{d-1},1-x_d$ with $D\ge D_*$. Then some nonempty
$I\subseteq[n]$ with $|I|\le D_*$ satisfies
\[
  \bigl|\EE[T_I]-T_I(x)\bigr|
  > \exp\bigl(-C_{\mathrm{sep}}\,B(n,p)\bigr).
\]
\end{theorem}

The theorem holds for \emph{every} feasible array, including arrays that
no distribution realises. Its proof occupies
Sections~\ref{sec:multiscale}--\ref{sec:separation}. Once it is
available, accurate empirical trace moments rule out every wrong
extension of any prefix, because a wrong prefix would force a feasible
array that violates such a statistic. Section~\ref{sec:decoding} shows
how to actually find the feasible extension using a bounded rational
computation.

\subsection{Exponentially weighted tuple statistics}

The separation proof is analytic, so we set up the objects it uses.
Fix $x,d,\EE$ as above. For $1\le k\le 2D$ an \emph{order-$k$ feature} is
a family of polynomials indexed by the last position $j$,
\begin{equation}\label{eq:feature}
  f_j=\sum_{i_1<\cdots<i_k=j}
      X_{i_1}\cdots X_{i_k}
      \prod_{h=1}^{k-1} z_h^{\,i_{h+1}-i_h},
  \qquad j\in[n],
\end{equation}
where $z_h=\exp(-a_h+\ii\theta_h)$ with $a_h>0$ and
$\theta_h\in\RR$. For $k=1$ this is just $f_j=X_j$. Each $f_j$ sums over
increasing tuples of input positions with exponential weights on the
gaps. Put
\begin{equation}\label{eq:feature-height}
  H_f=\prod_{h=1}^{k-1}\Bigl(1+\frac1{a_h}\Bigr).
\end{equation}
Summing geometric series over the positive gaps and using
$(1-e^{-a})^{-1}\le 1+1/a$ shows that $H_f\ge 1$ bounds the sum of the
absolute coefficients of every $f_j$.

For $s>0$ and $\omega\in\RR$, the \emph{signal} of the feature is the
exponentially damped Fourier sum
\begin{equation}\label{eq:signal}
  \mathcal S_f(s,\omega)
  =\sum_{j=1}^n \Delta[f_j]\,e^{(-s+\ii\omega)(j-d)}.
\end{equation}
Every monomial in $f_j$ uses positions at most $j$, so
$\Delta[f_j]=0$ for $j<d$; hence, despite the exponent being centred at
$d$, only $j\ge d$ contribute. For the base case $k=1$, where $f_j=X_j$,
this reads $\mathcal S_f(s,0)=\sum_{j\ge d}\Delta[X_j]\,e^{-s(j-d)}$, whose
first term is $\Delta[X_d]=\pm1$; that single term is what makes the
starting signal about $1/2$ at decay $s=4$, as made precise in
\eqref{eq:initial-signal}. The whole multiscale argument (the next
two sections) has one goal: to preserve a detectable signal
$\mathcal S_f(s,\omega)$ while shrinking both $s$ and $|\omega|$ to
$O(1/n)$, at the cost of raising the order $k$ by at most a factor of
four per step.

\section{Moving a signal to a larger scale}\label{sec:multiscale}

The signal \eqref{eq:signal} is a damped sum: it heavily discounts
positions more than about $1/s$ beyond the first disagreement. The next
proposition moves a detectable signal to a much smaller decay parameter
$S'$, at the price of letting the order grow by at most a factor of four.
The overall loss in the logarithm of the signal is kept below a factor
of eight. Controlling the \emph{angles} of the new gap parameters is
equally important: those angle bounds later let us pass from input
coordinates to trace coordinates. Enlarging distance scales while
raising the order follows the strategy of Burudgunte, Valiant, and Wang
\cite{BVW2026}, but here the comparison functional may be a truncated
positive moment functional, and the scale step uses Gram matrices of
polynomial vectors.

\begin{proposition}[One multiscale step]\label{prop:multiscale}
There are absolute constants \(0<\beta,\eta_0<1\) and \(C_0,C_1\ge1\)
with this property. Let \(f\) be an order-\(k\) feature from
\eqref{eq:feature}, and let \(\Delta\) come from a moment functional of
order \(2D\) satisfying the prefix conditions of Section~\ref{sec:setup}.
Suppose
\[
 0<S\le4,\qquad 0<S'\le\min\{1,\eta_0S\},\qquad 4k\le D,
\]
and, for some \(\beta S\le s\le S\) and \(\abs{\omega}\le2.002s\),
\begin{equation}\label{eq:multiscale-cost}
 \abs{\mathcal S_f(s,\omega)}\ge e^{-E},\qquad
 E\ge C_0\Bigl(1+k\log(2k)+\log H_f+\log\frac1{S'}\Bigr).
\end{equation}
Then there is an order-\(k'\) feature \(f'\), with \(1\le k'\le4k\),
satisfying
\begin{equation}\label{eq:multiscale-output}
 \abs{\mathcal S_{f'}(s',\omega')}\ge e^{-7.98E},\qquad
 \beta S'\le s'\le S',\qquad \abs{\omega'}\le2.002s',
\end{equation}
and
\begin{equation}\label{eq:multiscale-height}
 H_{f'}\le H_f^4\Bigl(1+\frac1{\beta S'}\Bigr)^3 .
\end{equation}
Moreover there are \(1\le m\le4\) lists, each equal to the old parameter
list \((z_1,\ldots,z_{k-1})\) or its complex conjugate, and at most
\(m-1\) added parameters, so that: each new inner-gap parameter is a
nonempty product using at most one entry from each list and at most one
added parameter; and every added parameter \(e^{-a+\ii\theta}\) obeys
\begin{equation}\label{eq:added-parameters}
 a\ge\beta S',\qquad \abs{\theta}\le C_1S.
\end{equation}
\end{proposition}

The proof splits in two. First, a wide Gaussian window turns the signal
into Fourier sums, and positivity of the moment functional forces a
product of at most four such sums to keep a signal while its total
frequency is small (this section). Second, expanding that product and
deforming Gaussian contours produces one feature with the claimed
parameters (Section~\ref{subsec:contour-conversion}).

\subsection{A Gaussian window and its logarithmic bound}

Throughout the proof of Proposition~\ref{prop:multiscale} set
\begin{equation}\label{eq:window-parameters}
 \sigma=\frac{K\sqrt E}{S'},\qquad
 W(l)=\exp\Bigl(-\frac{l^2}{2\sigma^2}\Bigr),\qquad b=\beta S',
\end{equation}
with $K$ a sufficiently large absolute constant. Constants are chosen in
the order: $K$ first, then $\beta$ small enough, then $\eta_0$ small
enough, and finally $C_0$ large enough. The choices of $K$ and $\beta$
also force the contour estimates later.

We will repeatedly use this consequence of
\eqref{eq:multiscale-cost}. For any fixed product of powers of
$H_f,1+\sigma,1/S',1/b$, together with a factor $\exp(O(k\log(2k)))$,
the logarithm is at most
\[
 C\Bigl(1+k\log(2k)+\log H_f+\log\frac1{S'}\Bigr)+C\log E,
\]
with $C$ depending only on constants already fixed. Enlarging $C_0$
makes this at most any chosen positive multiple of $E$. Only finitely
many such estimates occur, so one final choice of $C_0$ handles them all.

For real $t$ define the polynomial and its value at $x$,
\begin{equation}\label{eq:window-sums}
 A(t)=\sum_{j=1}^n f_j\,W(j-d)\,e^{\ii t(j-d)},\qquad
 B_x(t)=A(t)(x).
\end{equation}
The coefficient bound on $f_j$ and the Gaussian sum give
\begin{equation}\label{eq:window-uniform-bound}
 \abs{B_x(t)},\quad \abs{\EE[A(t)]},\quad \abs{\Delta[A(t)]}
 \le U:=C H_f(1+\sigma),
\end{equation}
with $C$ absolute and $U\ge1$. By prefix cancellation,
\[
 P(z):=\sum_{j=d}^n \Delta[f_j]\,W(j-d)\,z^{j-d}
 \quad\text{satisfies}\quad P(e^{\ii t})=\Delta[A(t)].
\]
We first show $P$ keeps a signal at almost the original decay:
\begin{equation}\label{eq:window-interior-signal}
 \abs{P(e^{-s_1+\ii\omega})}\ge\tfrac12 e^{-E}
 \quad\text{for some}\quad \abs{s_1/s-1}\le10^{-4}.
\end{equation}

Let $V$ be a centred real normal variable with variance $\sigma^{-2}$.
Since $W(l)\,\mathbf E\,e^{Vl}=1$,
\[
 \mathcal S_f(s,\omega)=\mathbf E\,P(e^{-s+V+\ii\omega}).
\]
Write $\delta=10^{-4}$. Exponential tilting gives
\[
 W(l)\,\mathbf E\bigl[e^{Vl}\mathbf 1_{\{\abs V>\delta s\}}\bigr]
 =\Pr\!\Bigl(\abs{N(l/\sigma^2,\sigma^{-2})}>\delta s\Bigr).
\]
For $0\le l\le\delta s\sigma^2/2$ this probability is at most
$2e^{-c\delta^2s^2\sigma^2}$; for larger $l$ use the bound one and sum
$e^{-sl}$. Because $\abs{\Delta[f_j]}\le2H_f$, the contribution of
$\abs V>\delta s$ is at most
\begin{equation}\label{eq:window-tail}
 2H_f(1+1/s)\Bigl(2e^{-c\delta^2s^2\sigma^2}+e^{-\delta s^2\sigma^2/2}\Bigr).
\end{equation}
Here $1/s\le1/(\beta S')$ and
$s^2\sigma^2\ge\beta^2K^2E/\eta_0^2$. Choose $\eta_0$ small and then
$C_0$ large to make \eqref{eq:window-tail} less than $e^{-2E}$. Then the
integral over $\abs V\le\delta s$ has magnitude at least
$e^{-E}-e^{-2E}\ge e^{-E}/2$, so its integrand attains magnitude at
least that large. This proves \eqref{eq:window-interior-signal}.

Set
\[
 \Lambda(t)=\log\frac{U}{\abs{P(e^{\ii t})}}\ge0,
\]
with value $+\infty$ at a boundary zero. We claim
\begin{equation}\label{eq:poisson-log-bound}
 \int_{\RR}\Lambda(t)\,\frac{s_1\,dt}{\pi(s_1^2+(t-\omega)^2)}\le1.001E.
\end{equation}
For completeness, the Cauchy Fourier transform is
\begin{equation}\label{eq:cauchy-transform}
 \int_{\RR}\frac{e^{\ii\xi v}}{\pi(1+v^2)}\,dv=e^{-\abs\xi}.
\end{equation}
For $\xi>0$ close the contour in the upper half-plane and take the residue
at $\ii$; for $\xi<0$ use the lower half-plane; $\xi=0$ is direct. Thus
periodizing the density in \eqref{eq:poisson-log-bound} gives the circle
Poisson measure at $e^{-s_1+\ii\omega}$.

To apply it, factor the nonzero polynomial $P$ into linear factors. A
factor with a root outside the unit disk has harmonic logarithmic
magnitude inside. For a root $a$ inside the disk, the identity
$\abs{e^{\ii t}-a}=\abs{1-\overline a e^{\ii t}}$ and the inequality
\[
 \abs{1-\overline a z}^2-\abs{z-a}^2=(1-\abs a^2)(1-\abs z^2)\ge0
\]
bound its contribution by its Poisson integral. Roots on the circle
follow by a radial limit; their logarithmic singularities are integrable.
Summing over factors gives
\[
 \int_{\RR}\Lambda(t)\frac{s_1\,dt}{\pi(s_1^2+(t-\omega)^2)}
 \le\log U-\log\abs{P(e^{-s_1+\ii\omega})}
 \le E+\log(2U).
\]
The last term is at most $1.001E$ by the choice of $C_0$, proving the
claim.

\subsection{Frequencies at prescribed differences}

We want a frequency $\lambda\in[-2s_1,2s_1]$ with a large signal, and,
for every prescribed difference in that interval, pairs of frequencies
with that difference. The product $A(t)\overline{A(t')}$ carries signed
frequency $t-t'$. After normalizing by the evaluations at $x$, these
products will be the interior vectors of a chain from $1$ to a
normalized copy of $A(\lambda)$, with consecutive frequency labels
differing by at most $b$. Each neighbouring inner product then has signed
frequency of magnitude at most $b$, even though $\abs\lambda$ may be
much larger. The logarithmic estimate turns the existence of enough
pairs into a question about pairing Cauchy mass.

\begin{lemma}[Cauchy matching]\label{lem:cauchy-matching}
Let $w(v)=1/(\pi(1+v^2))$. For every $r\ge0$ there is a finite positive
measure $\mu_r$ on $\RR^2$, supported on $v-v'=r$, whose two marginals
sum to at most $w(v)\,dv$. For $r>0$ its total mass is
\begin{equation}\label{eq:cauchy-matching-mass}
 2\mu_r(\RR^2)=1-\frac4\pi\arctan(e^{-\pi/r});
\end{equation}
for $r=0$ its total mass is $1/2$. In particular
\eqref{eq:cauchy-matching-mass} exceeds $0.737$ for $0<r\le2$.
\end{lemma}

\begin{proof}
For $r=0$ put half of $w(v)\,dv$ on the diagonal. Suppose $r>0$ and
partition the line into chains $v+jr$, $j\in\mathbb Z$, with
$-r/2\le v<r/2$. Write $w_j=w(v+jr)$. On the edge from $j$ to $j-1$, for
$j\ge1$, put weight
\[
 e_j=\sum_{m\ge0}(-1)^m w_{j+m}.
\]
These weights are nonnegative because the summands decrease along the
tail, and $e_j+e_{j+1}=w_j$, so the edges exhaust the weight at every
positive vertex. Build the negative-side edges the same way, from the
negative tail toward zero. The only possibly unused weight sits at the
central vertex, with value
\[
 R(v)=\sum_{j\in\mathbb Z}(-1)^j w(v+jr).
\]
To check no weight is overused, periodize $w$ at period $2r$ and
subtract its translate by $r$. By \eqref{eq:cauchy-transform}, with
$\tau=e^{-\pi/r}$, this gives the absolutely convergent Fourier series
\[
 R(v)=\frac2r\sum_{m\ge0}\tau^{2m+1}\cos\frac{(2m+1)\pi v}{r}.
\]
Writing $a=\pi v/r$, the sum equals
\[
 \re\frac{\tau e^{\ii a}}{1-\tau^2e^{2\ii a}}
 =\frac{\tau(1-\tau^2)\cos a}{1-2\tau^2\cos(2a)+\tau^4}\ge0,
\]
since $\abs a\le\pi/2$. Orient each edge with its larger endpoint first
and integrate the edge weights against $dv$ over $[-r/2,r/2)$. The
resulting measure has the claimed marginal domination. Its uncovered
mass is
\[
 \int_{-r/2}^{r/2}R(v)\,dv
 =\frac4\pi\sum_{m\ge0}\frac{(-1)^m\tau^{2m+1}}{2m+1}
 =\frac4\pi\arctan\tau,
\]
proving \eqref{eq:cauchy-matching-mass}. The expression decreases with
$r$ and at $r=2$ exceeds $0.737$; for instance
$e^{-\pi/2}<0.209$ together with $\arctan u\le u-u^3/3+u^5/5$ for
$0\le u\le1$ gives this numeric bound.
\end{proof}

\begin{lemma}[Frequencies from the logarithmic bound]\label{lem:good-frequencies}
Let $s_1,E>0$, let $\abs\omega\le2.003s_1$, and let
$\Lambda:\RR\to[0,\infty]$ be measurable satisfying
\eqref{eq:poisson-log-bound}. There is a real $\lambda$ with
\begin{equation}\label{eq:single-frequency}
 \abs\lambda\le2s_1,\qquad \Lambda(\lambda)\le2.40E.
\end{equation}
There is also an absolute $C_2$ such that, for every $\abs y\le2s_1$,
some real $t,t'$ satisfy
\begin{equation}\label{eq:paired-frequencies}
 t-t'=y,\qquad \abs t,\abs{t'}\le C_2s_1,\qquad
 \Lambda(t)+\Lambda(t')\le2.74E.
\end{equation}
\end{lemma}

\begin{proof}
The Cauchy mass of $[-2s_1,2s_1]$ is at least
\[
 \frac{\arctan(2-2.003)+\arctan(2+2.003)}\pi>0.418.
\]
Because $1.001/0.418<2.40$, averaging proves \eqref{eq:single-frequency}.

For \eqref{eq:paired-frequencies}, apply Lemma~\ref{lem:cauchy-matching}
with $r=\abs y/s_1\le2$ and substitute $t=\omega+s_1v$, reversing the
orientation if needed. The two marginals sum to at most the Cauchy
measure in \eqref{eq:poisson-log-bound}, while twice the pair mass
exceeds $0.737$. Discard pairs with an endpoint outside
$[-C_2s_1,C_2s_1]$; twice the discarded mass is at most twice the Cauchy
tail outside that interval, which tends uniformly to zero as
$C_2\to\infty$ since $\abs\omega/s_1\le2.003$. Choose absolute $C_2$ so
the retained mass exceeds $0.733/2$. Its integral of
$\Lambda(t)+\Lambda(t')$ is at most $1.001E$, so some retained pair has
sum at most
\[
 \frac{2(1.001)}{0.733}E<2.74E,
\]
as required. The diagonal construction gives the same when $y=0$.
\end{proof}

\subsection{A product with small total frequency}

The window parameters satisfy $\abs\omega/s_1\le2.002/0.9999<2.003$, so
Lemma~\ref{lem:good-frequencies} applies to our $\Lambda$. Individual
frequencies in \eqref{eq:paired-frequencies} need not be small, but their
differences can be prescribed. We use these pairs to build a chain of
polynomial vectors whose neighbouring inner products have small total
frequency. The following Hilbert-space fact explains why such a chain
keeps the needed exponential accuracy.

\begin{lemma}[Gram chaining]\label{lem:gram-chain}
Let $v_0,\ldots,v_J$, $J\ge1$, lie in a complex Hilbert space whose inner
product is linear in its first argument. Suppose $\norm{v_0}=1$ and, for
some $\xi\ge0$,
\[
 \abs{\norm{v_i}^2-1}\le\xi\ (0\le i\le J),\qquad
 \abs{\langle v_i,v_{i-1}\rangle-1}\le\xi\ (1\le i\le J).
\]
Then $\abs{\langle v_J,v_0\rangle-1}\le2J^2\xi$.
\end{lemma}

\begin{proof}
Put $h_i=v_i-v_{i-1}$. The hypotheses give
\[
 \norm{h_i}\le2\sqrt\xi,\qquad
 \abs{\langle h_i,v_{i-1}\rangle}\le2\xi,\qquad
 \norm{v_{i-1}-v_0}\le2(i-1)\sqrt\xi.
\]
So Cauchy--Schwarz gives
$\abs{\langle h_i,v_0\rangle}\le2\xi+4(i-1)\xi$. Sum over $i$ and use
$\langle v_0,v_0\rangle=1$.
\end{proof}

Choose an absolute $C_3$ large enough that all frequencies supplied by
Lemma~\ref{lem:good-frequencies} have magnitude at most $C_3S$. A product
of one to four factors, each of the form $A(t)$ or $\overline{A(t)}$ with
$\abs t\le C_3S$, is called \emph{balanced} if the sum of its signed
frequencies has magnitude at most $b$; conjugation flips the sign of a
frequency.

\begin{lemma}[A balanced product keeps a signal]\label{lem:balanced-product}
Some balanced product $G$ satisfies
\begin{equation}\label{eq:balanced-product-signal}
 \abs{\Delta[G]}\ge e^{-7.94E}.
\end{equation}
\end{lemma}

\begin{proof}
Suppose not: every balanced product has signal below
$\epsilon=e^{-7.94E}$. The squared modulus $\abs{A(t)}^2$ is one such
product. Positivity of $\EE$ on $A(t)$ and $1$ gives
\[
 \abs{\EE[A(t)]}^2\le\EE[\abs{A(t)}^2]\le\abs{B_x(t)}^2+\epsilon,
\]
hence
\begin{equation}\label{eq:evaluation-lower-bound}
 \abs{\Delta[A(t)]}\le2\abs{B_x(t)}+\sqrt\epsilon.
\end{equation}
At $\lambda$ from \eqref{eq:single-frequency} this implies
\begin{equation}\label{eq:endpoint-normalization}
 \abs{B_x(\lambda)}\ge e^{-2.41E}.
\end{equation}
Indeed $\abs{\Delta[A(\lambda)]}\ge e^{-2.40E}$ whereas
$\sqrt\epsilon=e^{-3.97E}$; fixed factors are absorbed by the lower bound
on $E$ in \eqref{eq:multiscale-cost}. For a pair in
\eqref{eq:paired-frequencies}, nonnegativity of $\Lambda$ gives both
signals at least $e^{-2.74E}$, and
\[
 \abs{\Delta[A(t)]\Delta[A(t')]}=U^2e^{-\Lambda(t)-\Lambda(t')}
 \ge e^{-2.74E}.
\]
Applying \eqref{eq:evaluation-lower-bound} to each gives
\begin{equation}\label{eq:pair-normalization}
 \abs{B_x(t)\overline{B_x(t')}}\ge e^{-2.75E}.
\end{equation}
Each evaluation is at least a third of its signal once $E$ is large; the
factor $1/9$ is absorbed in $e^{-0.01E}$.

Take a monotone chain $0=y_0,y_1,\ldots,y_J=\lambda$ with consecutive
distances at most $b$ and
\[
 1\le J\le C(1+S/b).
\]
If $\lambda=0$, use two endpoints and $J=1$. For each interior $y_i$
choose a pair from \eqref{eq:paired-frequencies} and set
\[
 V_0=1,\qquad
 V_i=\frac{A(t)\overline{A(t')}}{B_x(t)\overline{B_x(t')}}\ (0<i<J),
 \qquad V_J=\frac{A(\lambda)}{B_x(\lambda)}.
\]
The denominators are nonzero by
\eqref{eq:endpoint-normalization}--\eqref{eq:pair-normalization}, and
every $V_i(x)=1$. View these polynomials as vectors $v_i$ in the Hilbert
space of $\EE$; they have degree at most $2k\le D$.

For $1\le i\le J$ the norm square of $v_i$ and its inner product with
$v_{i-1}$ are expectations of normalized balanced products, whose signed
frequencies are respectively zero and $y_i-y_{i-1}$; each product has at
most four factors and its normalizing denominator has magnitude at least
$e^{-5.50E}$. The contradictory assumption therefore gives
\[
 \abs{\norm{v_i}^2-1}\le\xi,\qquad
 \abs{\langle v_i,v_{i-1}\rangle-1}\le\xi,\qquad
 \xi=\epsilon e^{5.50E}=e^{-2.44E}.
\]
Since $v_0=1$ has norm one, Lemma~\ref{lem:gram-chain} yields
\[
 \abs{\Delta[A(\lambda)]}
 =\abs{B_x(\lambda)}\,\abs{\langle v_J,v_0\rangle-1}
 \le2UJ^2e^{-2.44E}<e^{-2.40E}.
\]
The last strict inequality holds after enlarging $C_0$, because
$\log(2UJ^2)<0.04E$ by \eqref{eq:multiscale-cost}. This contradicts
\eqref{eq:single-frequency} and proves the lemma.
\end{proof}

We now have a product of at most four windowed feature sums with signal at
least $e^{-7.94E}$ and total frequency at most $b$. It remains to turn it
into one feature while keeping both decay and frequency of order $S'$;
the Gaussian contour construction in the next section does exactly that.

\subsection{Converting a balanced product to a feature}\label{subsec:contour-conversion}

Lemma~\ref{lem:balanced-product} gives a product of at most four
windowed Fourier sums with a substantial discrepancy and small total
frequency. We now write that product as an integral of features. The
contour puts their outer parameters in the sector that
Proposition~\ref{prop:multiscale} requires; what remains is to bound
the damping on the inner gaps.

Fix a product from Lemma~\ref{lem:balanced-product} and let
$1\le m\le4$ be its number of factors. Expand each factor into the
tuples that define $f$. An \emph{interleaving} is an ordering, ties
included, of the $mk$ labeled positions in these tuples. There are at
most $(mk)^{mk}=\exp(O(k\log(2k)))$ interleavings: assign each labeled
position its rank among the distinct positions. Keep only interleavings
that increase strictly inside each old tuple. Fix one interleaving and
relabel its copies so $j_1\le\cdots\le j_m$. Ties between endpoints may
be ordered arbitrarily. Absorbing conjugation into the signs of the
frequencies, the window weight is
\begin{equation}\label{eq:endpoint-window}
 \prod_{r=1}^m W(j_r-d)\exp\bigl(\ii t_r(j_r-d)\bigr),
 \qquad |t_r|\le C_3S,\qquad
 \Bigl|\sum_{r=1}^m t_r\Bigr|\le b.
\end{equation}
Conjugation also conjugates the old inner-gap parameters, leaving their
dampings unchanged.

\paragraph{A Gaussian contour with controlled total frequency.}
Recall $\sigma=K\sqrt E/S'$ and $b=\beta S'$. For every real $l$,
\begin{equation}\label{eq:gaussian-contour}
 W(l)=\frac{\sigma}{\ii\sqrt{2\pi}}
       \int_{-\ii\infty}^{\ii\infty}
       \exp\Bigl(\frac{\sigma^2v^2}{2}+vl\Bigr)\,dv.
\end{equation}
Indeed, $v=\ii u$ gives the Gaussian Fourier transform; its value at
$l=0$ is one, and integration by parts shows its $l$-derivative is
$-l/\sigma^2$ times itself, fixing the formula.

Set $\rho=1/2.002$. For $u=(u_1,\ldots,u_m)\in\RR^m$ define
\begin{equation}\label{eq:bent-contour}
 \Omega=\sum_{r=1}^m(u_r+t_r),\qquad
 v_r=b+\ii u_r\ (r<m),\qquad
 v_m=-mb-\rho|\Omega|+\ii u_m.
\end{equation}
These real parts have partial sums $rb$ for $r<m$ and total
$-b-\rho|\Omega|$. Centred at $j_m$, the total sum gives the real part
of the outer coefficient and the negatives of the partial sums give the
real parts on consecutive endpoint gaps. So the contour is built to
produce outer decay $b+\rho|\Omega|$ and positive inner dampings $rb$;
the exact rewriting is checked below.

For each fixed tuple of positions, first shift the first $m-1$ contours
of \eqref{eq:gaussian-contour} to the vertical lines $\re v_r=b$,
leaving the last on the imaginary axis. The linking horizontal
integrals vanish by Gaussian decay. Next fix $(u_1,\ldots,u_{m-1})$ and
deform the last contour to the piecewise-linear graph in
\eqref{eq:bent-contour}, whose slopes have absolute value $\rho<1$. Along
horizontal segments that join its truncations to the imaginary axis at
height $\pm T$, the Gaussian exponent has real part at most $-cT^2+O(T)$
for some $c>0$, while $\exp(v_m(j_m-d))$ adds only a linear term in $T$,
so those linking integrals also vanish. The integrands are entire, so no
residues occur. This proves the identities as iterated integrals; joint
absolute convergence follows from the bound below.

Let $\nu$ be the resulting complex measure on $\RR^m$ after removing the
position-dependent factors. Outside the measure-zero set $\Omega=0$,
\begin{equation}\label{eq:contour-measure}
 d\nu(u)=
 \Bigl(\frac{\sigma}{\sqrt{2\pi}}\Bigr)^m
 \exp\Bigl(\frac{\sigma^2}{2}\sum_{r=1}^m v_r^2\Bigr)
 \bigl(1+\ii\rho\operatorname{sgn}\Omega\bigr)\,du.
\end{equation}
The last factor is the differential of the bent contour divided by
$\ii\,du_m$. We now bound this uniformly over the frequencies in
\eqref{eq:endpoint-window}; the bounds also give absolute convergence.

Put $\delta_0=1-4\rho^2>0$ and $c_1=\delta_0/2$. Since $m\le4$ and
$|\sum t_r|\le b$, Young's inequality gives an absolute $C_4$ with
\begin{align}
 \sum_{r=1}^m(\re v_r)^2
 &=(m-1)b^2+(mb+\rho|\Omega|)^2 \notag\\
 &\le 3b^2+\Bigl(2\rho\sqrt{\textstyle\sum_r u_r^2}+(4+\rho)b\Bigr)^2
 \notag\\
 &\le (1-c_1)\sum_r u_r^2+C_4b^2.
 \label{eq:contour-quadratic}
\end{align}
The strict inequality $4\rho^2<1$ is essential: summing at most four
imaginary coordinates can multiply their squared norm by four, and the
sector constant $2.002$ leaves a positive Gaussian margin. For example
$C_4=3+(4+\rho)^2(1+8\rho^2/\delta_0)$ works. With
\eqref{eq:contour-measure} this gives
\[
 |d\nu(u)|\le C\sigma^m
 \exp\Bigl(\frac{C_4\sigma^2b^2}{2}
           -\frac{c_1\sigma^2}{2}\sum_r u_r^2\Bigr)du.
\]
For any fixed tuple the remaining exponential factor has modulus at most
$\exp(C_n(1+\sum_r|u_r|))$ for a finite $C_n$, which is integrable
against the Gaussian bound. So the iterated deformation is a jointly
absolutely convergent integral, and finite tuple sums may be exchanged
with it.

Write $\mathcal U=\{u:\max_r|u_r|\le S'/16\}$. Integrating the last bound
and splitting the negative quadratic term into two equal halves on
$\mathcal U^c$ gives absolute constants $C,C'$ with
\begin{align*}
 \|\nu\|_{\mathrm{abs}}
   &\le C\exp(C_4K^2\beta^2E/2),\\
 \int_{\mathcal U^c}|d\nu|
   &\le C'\exp\Bigl[\Bigl(\frac{C_4K^2\beta^2}{2}
                 -\frac{c_1K^2}{1024}\Bigr)E\Bigr].
\end{align*}
Here $\|\nu\|_{\mathrm{abs}}$ is total variation; the powers $\sigma^m$
cancel under Gaussian rescaling. Choose $K$ with $c_1K^2/1024\ge30$,
then $\beta\le1/4$ with $C_4K^2\beta^2/2\le0.001$. Enlarging $C_0$ to
absorb fixed prefactors gives
\begin{equation}\label{eq:contour-mass}
 \|\nu\|_{\mathrm{abs}}\le e^{0.005E},\qquad
 \int_{\mathcal U^c}|d\nu|\le e^{-20E}.
\end{equation}
This respects the constant order fixed earlier: $K$ first, $\beta$
second, then $\eta_0$ small to meet the window estimate, and only
afterward $C_0$ enlarged.

\paragraph{Outer parameters and endpoint gaps.}
For $c_r=v_r+\ii t_r$, telescoping the endpoint differences gives
\begin{equation}\label{eq:endpoint-telescoping}
 \sum_{r=1}^m c_r(j_r-d)
 =\Bigl(\sum_{r=1}^m c_r\Bigr)(j_m-d)
  -\sum_{r=1}^{m-1}\Bigl(\sum_{l=1}^r c_l\Bigr)(j_{r+1}-j_r).
\end{equation}
So the largest endpoint has coefficient $-s'+\ii\Omega$ with
\begin{equation}\label{eq:new-outer-decay}
 s'=b+\rho|\Omega|.
\end{equation}
The link from $j_r$ to $j_{r+1}$ receives the parameter
\begin{equation}\label{eq:endpoint-link}
 \exp\Bigl(-rb-\ii\sum_{l=1}^r(u_l+t_l)\Bigr),\qquad 1\le r<m.
\end{equation}
Thus every added damping is at least $b$, uniformly in $u$. On
$\mathcal U$,
\[
 |\Omega|\le(\beta+1/4)S',\qquad
 \beta S'\le s'\le\bigl[\beta+\rho(\beta+1/4)\bigr]S'\le S',
 \qquad |\Omega|\le2.002s'.
\]
The angle in \eqref{eq:endpoint-link} has absolute value at most
$3(C_3S+S'/16)\le C_1S$ for a fixed absolute $C_1$. Hence the outer
parameters satisfy \eqref{eq:multiscale-output} and the endpoint links
satisfy \eqref{eq:added-parameters}. The choice of $C_1$ uses only $C_3$
and $S'\le S$, imposing no new condition on $K$ or $\beta$.

\subsection{Interleavings and the cost of the inner gaps}\label{subsec:interleavings}

We have outer weights at the right scale. To finish, each interleaving
must have exactly the form of a feature with controlled coefficient sum.
One old inner edge can cross several gaps of the merged tuple, so
charging its damping at every crossing would overcount. A distinct-edge
assignment prevents that loss.

For the fixed interleaving write its distinct positions as
$i_1<\cdots<i_v$ with $1\le v\le mk$. Form a multigraph on these
vertices: include the inner edges of each old tuple and the links
between consecutive endpoints in \eqref{eq:endpoint-link}, each edge
carrying its exponential parameter. It is connected, since each old
tuple is a path to its endpoint and the endpoint links join those paths.
Delete loops from equal endpoints; their weights are one.

For each merged gap $i_{a+1}-i_a$, multiply the parameters of all edges
crossing it. Each edge length is the sum of the merged gaps it crosses,
so the new parameters reproduce the original weight exactly. Every
merged gap is crossed by some edge, by connectivity, so its damping is
positive. Within one old tuple the inner-edge intervals have disjoint
interiors, and the same holds for the consecutive endpoint links. It
follows that each new parameter uses at most one old parameter from each
copy and at most one added endpoint parameter. This is exactly the
factor-count assertion of Proposition~\ref{prop:multiscale}.

Ties merge repeated bit variables by $X_i^r=X_i$ for $r\ge1$. Once the
interleaving is fixed, choosing arbitrary strictly increasing values for
its $v$ distinct positions specifies exactly one assignment to its
labeled tuples, so no further restriction remains on the new tuple. Its
largest position is $i_v=j_m$. Summing all these assignments gives an
order-$v$ feature $f^{\mathcal I,u}$ with outer weight
$\exp((-s'+\ii\Omega)(i_v-d))$.

The needed combinatorial fact controls its height.

\begin{lemma}[Assigning distinct edges to consecutive gaps]
\label{lem:edge-gap-assignment}
Let a connected multigraph have ordered vertices $i_1<\cdots<i_v$. There
is an assignment of a distinct edge to each gap $(i_a,i_{a+1})$ so that
the assigned edge crosses that gap.
\end{lemma}

\begin{proof}
For $v=1$ there is nothing to prove. Otherwise keep a spanning tree and
orient each edge from its smaller to its larger endpoint. Let $M$ be the
$(v-1)\times(v-1)$ matrix whose $(e,a)$ entry is one if tree edge $e$
crosses gap $a$ and zero otherwise. It is invertible: for $g$ in its
kernel set $y_1=0$ and $y_{a+1}=y_a+g_a$; then $Mg=0$ says $y$ is equal
at the endpoints of every tree edge, and connectivity forces all values
zero, so $g=0$. A nonzero term in the determinant expansion of $M$ pairs
its rows and columns through entries equal to one; that pairing is the
required assignment.
\end{proof}

To see why distinctness matters, look at Figure~\ref{fig:edge-gap-assignment}:
one edge may contribute to several new parameters, but it need pay for
only one of their upper bounds. Concretely, take two old tuples
$(i_1,i_3,i_5)$ and $(i_2,i_4,i_6)$ joined by one dashed endpoint
link-edge, with gaps $g_a=(i_a,i_{a+1})$ for $1\le a\le5$. The assignment
$g_a\mapsto e_a$, $1\le a\le5$, gives every gap a distinct crossing edge:
$e_1$ crosses both $g_1$ and $g_2$ but is charged only to $g_1$, and $e_2$
supplies the bound for $g_2$.

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1.28cm,y=0.9cm,>=stealth,
  olda/.style={draw=blue!70!black,thick},
  oldb/.style={draw=orange!85!black,thick},
  added/.style={draw=black,thick,dashed}]
  \draw[gray] (0,0)--(5,0);
  \foreach \a in {1,...,6} {
    \fill (\a-1,0) circle (1.8pt);
    \node[below=3pt] at (\a-1,0) {$i_{\a}$};
  }
  \draw[olda] (0,0) to[bend left=30] node[above,pos=.5] {$e_1$} (2,0);
  \draw[olda] (2,0) to[bend left=30] node[above,pos=.5] {$e_3$} (4,0);
  \draw[oldb] (1,0) to[bend left=65] node[above,pos=.5] {$e_2$} (3,0);
  \draw[oldb] (3,0) to[bend left=65] node[above,pos=.5] {$e_4$} (5,0);
  \draw[added] (4,0) to[bend right=60] node[below=2pt,pos=.5] {$e_5$} (5,0);
  \foreach \a in {1,...,5} {
    \node at (\a-.5,-1.05) {$g_{\a}$};
  }
\end{tikzpicture}
\caption{A schematic interleaving of the two old tuples $(i_1,i_3,i_5)$
and $(i_2,i_4,i_6)$, joined by the dashed endpoint link $e_5$. Here
$g_a$ is the gap $(i_a,i_{a+1})$. The assignment $g_a\mapsto e_a$ for
$1\le a\le5$ uses a distinct crossing edge for every gap: $e_1$ crosses
both $g_1$ and $g_2$ but is charged only to $g_1$, while $e_2$ supplies
the bound for $g_2$.}
\label{fig:edge-gap-assignment}
\end{figure}

Give each edge occurrence $e$ its damping $a_e>0$. A merged gap's damping
is the sum of $a_e$ over edges crossing it, hence at least that of its
assigned edge. Since $1+1/a$ decreases with $a$,
Lemma~\ref{lem:edge-gap-assignment} gives
\begin{align}
 H_{f^{\mathcal I,u}}
 &\le\prod_{e\ \text{assigned}}(1+1/a_e)
 \le\prod_{e\ \text{present}}(1+1/a_e) \notag\\
 &\le H_f^m(1+1/b)^{m-1}\le H_f^4(1+1/b)^3.
 \label{eq:interleaving-height}
\end{align}
The second inequality uses that all factors are at least one; the
endpoint-link dampings are $rb\ge b$. This covers all overlaps between
old tuples and also the single-distinct-position case, where the height
is the empty product one.

\paragraph{Completing the multiscale estimate.}
Apply $\Delta$ to the expanded product and use the integral
representation for each interleaving. With $\nu_{\mathcal I}$ the
corresponding measure,
\begin{equation}\label{eq:product-feature-integral}
 \Delta[\text{product}]
 =\sum_{\mathcal I}\int_{\RR^m}
   \mathcal S_{f^{\mathcal I,u}}(s',\Omega)\,d\nu_{\mathcal I}(u).
\end{equation}
All estimates are uniform over interleavings, and the integrands are
uniformly bounded even outside $\mathcal U$. Indeed, for each fixed
endpoint $j$ the coefficients of $f_j^{\mathcal I,u}$ have absolute sum at
most the height in \eqref{eq:interleaving-height}, terms with $j<d$
vanish under $\Delta$ by prefix agreement, and $s'\ge b$ gives
\begin{equation}\label{eq:contour-uniform-signal}
 \bigl|\mathcal S_{f^{\mathcal I,u}}(s',\Omega)\bigr|
 \le 2H_f^4(1+1/b)^3\sum_{l\ge0}e^{-bl}
 \le 2H_f^4(1+1/b)^4.
\end{equation}
No exponential factor from negative distances appears.

Let $N_{\mathrm{int}}$ be the number of interleavings and
$V=2H_f^4(1+1/b)^4$. Hypothesis~\eqref{eq:multiscale-cost} with large
enough absolute $C_0$ gives
\[
 E\ge100,\qquad \log N_{\mathrm{int}}\le0.01E,\qquad \log V\le0.01E.
\]
Here $\log(1+1/b)$ is at most an absolute constant plus $\log(1/S')$,
because $b=\beta S'$, $S'\le1$, and $\beta$ is already fixed. If every
signal in \eqref{eq:product-feature-integral} with $u\in\mathcal U$ had
magnitude below $e^{-7.98E}$, then \eqref{eq:contour-mass} and
\eqref{eq:contour-uniform-signal} would give
\[
 |\Delta[\text{product}]|
 \le N_{\mathrm{int}}\bigl(e^{(0.005-7.98)E}+Ve^{-20E}\bigr)
 \le e^{-7.965E}+e^{-19.98E}<e^{-7.94E}.
\]
This contradicts Lemma~\ref{lem:balanced-product}. Some interleaving and
some $u\in\mathcal U$ therefore give a feature with signal at least
$e^{-7.98E}$. Its order is at most $mk\le4k$; \eqref{eq:new-outer-decay}
and the bounds on $\mathcal U$ give the outer parameters;
\eqref{eq:interleaving-height} gives \eqref{eq:multiscale-height}; and
the crossing description gives the parameter factors and
\eqref{eq:added-parameters}. This completes the proof of
Proposition~\ref{prop:multiscale}.

\section{From an input signal to separation of trace moments}\label{sec:separation}

We now prove Theorem~\ref{thm:separation}. Proposition~\ref{prop:multiscale}
keeps a detectable input-coordinate signal while lowering its decay rate.
First we choose enough scales to force the rate down to $1/n$. The
resulting gap parameters need not lie in the disk where trace moments
control the signal, so a single one-variable continuation bridges the gap.
Throughout this section $0<p<1$ and $q_*,Q,Y$ are as in
\eqref{eq:aux-parameters}. Recall from \eqref{eq:aux-comparisons} that
\begin{equation}\label{eq:aux-comparisons-2}
  1\le\mathsf X(n,p)\le Y\le2\mathsf X(n,p),\qquad
  QY=Q+\log n\le C\log n.
\end{equation}

\subsection{A scale schedule and the surviving signal}

Set
\begin{equation}\label{eq:separation-cutoff}
  \mu=7.98,\qquad \alpha=0.001,\qquad
  h=\lceil\log_2Y\rceil+H,\qquad D_*=4^h,
\end{equation}
where the absolute integer $H$ is fixed below; in particular
$D_*\le4^{H+1}Y^2$. Fix any positive moment functional of order $2D$ with
$D\ge D_*$ and first wrong position $d$, and let $\Delta$ be its
difference from the true word, as in Section~\ref{sec:setup}. Every
constant chosen below is independent of this system, of $n$, and of $p$.

For an absolute constant $\eta>0$ define
\begin{equation}\label{eq:scale-schedule}
  S_0=4,\qquad
  S_j=\eta\,q_*\,Y^{-\alpha}\,S_{j-1}\,
        \min\{1,D_*S_{j-1}\}\quad(1\le j\le h).
\end{equation}
The linear regime of this recurrence pushes $D_*S_j$ below one; its
quadratic regime then makes $S_j$ shrink fast. Both regimes also control
the arguments of the final gap parameters.

Choose an integer $J_*$ with $\alpha J_*\ge3$ and set $H=J_*+3$. To check
the decrease, write $\vartheta=\eta q_*Y^{-\alpha}$ and $t_j=D_*S_j$, so
$t_j=\vartheta\,t_{j-1}\min\{1,t_{j-1}\}$. Then, whenever the quadratic
regime begins,
\[
  t_{J_*}\le\vartheta^{J_*}t_0
  \le4^{H+2}\eta^{J_*}Y^{2-\alpha J_*}\le1
\]
once $\eta$ is small enough. Require also
$\eta\le\min\{\eta_0,1/4,e^{-1}\}$, with $\eta_0$ from
Proposition~\ref{prop:multiscale}. Now $\log(1/\vartheta)\ge Q$ and
$t_j\le1$ for $j\ge J_*$. Iterating $t_j=\vartheta t_{j-1}^2$ in that
range gives
\begin{equation}\label{eq:terminal-scale}
  t_h\le\vartheta^{\,2^{h-J_*}-1}
  \le\exp\{-Q(2^{h-J_*}-1)\}\le n^{-1},\qquad S_h\le n^{-1}.
\end{equation}
The last inequality uses $2^{h-J_*}\ge8Y$ and $Q(Y-1)=\log n$. At each
transition $0<S_j\le\min\{1,\eta_0S_{j-1}\}$, as the proposition requires.

We also need the cost of these small scales. Put $A_0=Q+\log Y$. With
$\ell_j=\max\{0,\log(1/S_j)\}$ the recurrence gives
\[
  \ell_j\le2\ell_{j-1}+\log(1/\vartheta),\quad\ell_0=0,\quad
  \log(1/\vartheta)\le CA_0,
\]
hence
\begin{equation}\label{eq:scale-cost}
  \log(1/S_j)\le C2^jA_0\qquad(0\le j\le h).
\end{equation}

Now iterate Proposition~\ref{prop:multiscale}. Start with the order-one
feature $f_i^{(0)}=X_i$ at decay $s_0=4$ and frequency zero. Prefix
agreement gives $\Delta[X_i]=0$ for $i<d$ while $\abs{\Delta[X_d]}=1$;
since $\abs{\Delta[X_i]}\le2$ for all $i$,
\begin{equation}\label{eq:initial-signal}
  \abs{\mathcal S_{f^{(0)}}(4,0)}
  \ge1-2\sum_{r\ge1}e^{-4r}
  =1-\frac{2}{e^4-1}>\frac12 .
\end{equation}
Use error exponents
\begin{equation}\label{eq:scale-errors}
  E_j=C_5A_0\mu^j\qquad(0\le j\le h),
\end{equation}
with absolute $C_5$ chosen after $H$ and $\eta$.

The induction maintains this statement. At stage $j$ there is a feature
$f^{(j)}$ of order $k_j\le4^j$ with
\begin{equation}\label{eq:scale-induction}
  \begin{gathered}
    \beta S_j\le s_j\le S_j,\quad
    \abs{\omega_j}\le2.002s_j,\quad
    \abs{\mathcal S_{f^{(j)}}(s_j,\omega_j)}\ge e^{-E_j},\\
    \log H_{f^{(j)}}\le C4^jA_0.
  \end{gathered}
\end{equation}
The base case follows from \eqref{eq:initial-signal} and $H_{f^{(0)}}=1$
on increasing $C_5$. At the transition $j-1\to j$ the degree requirement
is $4k_{j-1}\le4^j\le D_*\le D$. The proposition's height conclusion and
\eqref{eq:scale-cost} give
\[
  \log H_{f^{(j)}}\le4\log H_{f^{(j-1)}}+3\log\bigl(1+1/(\beta S_j)\bigr)
  \le4\log H_{f^{(j-1)}}+C2^jA_0,
\]
and summing this proves the height bound in \eqref{eq:scale-induction}.
For the exponent hypothesis, the proposition's bracket is at most
\[
  C\bigl(1+j4^{j-1}+4^{j-1}A_0+2^jA_0\bigr).
\]
Because $\mu>4$, the sequences $j(4/\mu)^{j-1}$ and $2^j/\mu^{j-1}$ are
bounded. Thus one choice of $C_5$ makes this bracket times $C_0$ at most
$E_{j-1}$ for every $j$. All hypotheses of
Proposition~\ref{prop:multiscale} hold, and its signal bound is
$e^{-\mu E_{j-1}}=e^{-E_j}$.

Write $f=f^{(h)}$, $k=k_h$, $s=s_h$, $\omega=\omega_h$. We have a signal
of magnitude at least $e^{-E_h}$ with $k\le D_*$ and $s\le1/n$. The next
step records where its parameters sit inside the unit disk; this controls
the cost of continuing the signal to the trace domain.

\subsection{Damping under multiplication}

Call the parameters introduced between endpoints in any application of
Proposition~\ref{prop:multiscale} \emph{elementary parameters}, and
include the final outer parameter $z_0=e^{-s+\ii\omega}$. An elementary
parameter $e^{-a+\ii\theta}$ introduced at stage $j$ has $a\ge\beta S_j$
and $\abs{\theta}\le C_1S_{j-1}$. Using \eqref{eq:scale-schedule}, pick a
small absolute $c_2>0$ so that every elementary parameter obeys
\begin{equation}\label{eq:elementary-damping}
  a\ge\gamma\min\{\abs{\theta},D_*\theta^2\},\qquad
  \gamma=c_2q_*Y^{-\alpha}\le1.
\end{equation}
Indeed, the increasing map $u\mapsto u\min\{1,D_*u\}$ changes by at most
a factor $\max\{C_1,C_1^2\}$ when $u$ becomes $C_1u$, so
$c_2\le\beta\eta/\max\{C_1,C_1^2\}$ suffices; shrinking $c_2$ further
covers $z_0$ since $\abs\omega\le2.002s$. Conjugating an elementary
parameter preserves \eqref{eq:elementary-damping}.

Each new inner gap holds at most one parameter from each of at most four
copies of the preceding feature, and at most one new elementary parameter;
count repeated factors with multiplicity, and conjugation does not change
the count. Starting with no inner parameters, the maximum number $N_j$ of
elementary factors in a stage-$j$ inner gap satisfies
\[
  N_0=0,\qquad N_j\le4N_{j-1}+1,\qquad N_j\le\frac{4^j-1}{3}.
\]
In particular an inner gap of $f$, even after multiplying by $z_0$,
contains at most $(4^h+2)/3\le D_*$ elementary factors.

The next lemma explains why this count matters. The Cayley map
$z\mapsto(1+z)/(1-z)$ sends the unit disk to the right half-plane; we
need a quantitative distance from its boundary.

\begin{lemma}[Products with controlled damping]\label{lem:product-cayley}
Let $N\ge1$ be an integer and $0<\gamma\le1$. Suppose $z$ is a nonempty
product of at most $N$ numbers $e^{-a_j+\ii\theta_j}$ with $a_j>0$,
$\theta_j\in\RR$, and $a_j\ge\gamma\min\{\abs{\theta_j},N\theta_j^2\}$.
Then for some absolute $c_3>0$,
\[
  \re\frac{1+z}{1-z}\ge c_3\gamma.
\]
\end{lemma}

\begin{proof}
Write $z=e^{-T+\ii\psi}$ with $T=\sum_j a_j>0$ and
$\psi=\sum_j\theta_j$. Let
\[
  U=\sum_{\abs{\theta_j}\ge1/N}\abs{\theta_j},\qquad
  V=\sum_{\abs{\theta_j}<1/N}\abs{\theta_j}.
\]
Summing the hypotheses and applying Cauchy--Schwarz to at most $N$ small
angles gives
\[
  T\ge\gamma\Bigl(U+N\!\!\sum_{\abs{\theta_j}<1/N}\theta_j^2\Bigr)
   \ge\gamma(U+V^2).
\]
If $U\ge1$ or $V\ge1$ the bracket is at least one; otherwise
$U+V^2\ge U^2+V^2\ge(U+V)^2/2$. Since $\abs\psi\le U+V$, in all cases
\[
  T\ge\tfrac12\gamma\min\{1,\psi^2\}.
\]
For $0<T\le1$ this gives
\[
  1-\abs z^2\ge cT,\qquad
  \abs{1-z}^2\le C\bigl(T^2+\min\{1,\psi^2\}\bigr)\le C'T/\gamma.
\]
Their ratio is $\re((1+z)/(1-z))$. If $T>1$, that ratio is at least
$(1-e^{-2})/4$, which also suffices because $\gamma\le1$.
\end{proof}

\subsection{The exact trace generating identity}

Let $z_1,\ldots,z_{k-1}$ be the inner gap parameters of the final feature
$f$. Define the polynomial in $k$ complex variables
\begin{equation}\label{eq:input-polynomial}
 F(Z_0,\ldots,Z_{k-1})
 =\sum_{1\le i_1<\cdots<i_k\le n}
  \Delta\Bigl[\prod_{r=1}^kX_{i_r}\Bigr]
  Z_0^{i_1}\prod_{r=1}^{k-1}Z_r^{i_{r+1}-i_r}.
\end{equation}
At the point $Z_0^*=z_0$, $Z_r^*=z_rz_0$ $(1\le r<k)$, the powers of
$z_0$ telescope to $i_k$, so
\begin{equation}\label{eq:input-polynomial-signal}
 F(Z^*)=z_0^d\,\mathcal S_f(s,\omega),\qquad
 \abs{F(Z^*)}\ge e^{-E_h-1},
\end{equation}
where $sd\le nS_h\le1$. Each coordinate of $Z^*$ is a nonempty product of
at most $D_*$ elementary parameters, so Lemma~\ref{lem:product-cayley}
gives
\begin{equation}\label{eq:input-cayley-margin}
 \re\frac{1+Z_r^*}{1-Z_r^*}\ge c_3\gamma\qquad(0\le r<k).
\end{equation}
We also need the coordinates' collective closeness to the unit circle. If
$z_r=e^{-a_r+\ii\theta_r}$, then
\[
 \frac1{1-\abs{Z_r^*}}\le1+\frac1{a_r+s}\le1+\frac1{a_r}\ (r\ge1),
 \qquad \frac1{1-\abs{Z_0^*}}\le1+\frac1s,
\]
using $e^u\ge1+u$. The height bound in \eqref{eq:scale-induction} and
\eqref{eq:scale-cost} therefore give
\begin{equation}\label{eq:input-boundary-cost}
 W_*:=\log\prod_{r=0}^{k-1}\frac1{1-\abs{Z_r^*}}
 \le\log H_f+\log\bigl(1+1/(\beta S_h)\bigr)\le C4^hA_0.
\end{equation}

Now express the same polynomial through observable trace moments on a
different domain. This is the multivariate trace generating identity of
\cite[Section~5.2]{CDLSS2021Smoothed}; see also \cite[Fact~20]{CDLS2024}.
We give the counting argument directly. For a rank tuple
$\ell=(\ell_1,\ldots,\ell_k)$ with $1\le\ell_1<\cdots<\ell_k\le n$ write
$T_\ell=T_{\{\ell_1,\ldots,\ell_k\}}$. For $u=(u_0,\ldots,u_{k-1})\in\CC^k$
set
\[
 G(u)=\sum_{1\le\ell_1<\cdots<\ell_k\le n}
       \Delta[T_\ell]\,
       u_0^{\ell_1-1}\prod_{r=1}^{k-1}u_r^{\ell_{r+1}-\ell_r-1}.
\]
Then, with $Z_r=q+pu_r$, the exact identity is
\begin{equation}\label{eq:trace-generating-identity}
 \Bigl(\prod_{r=0}^{k-1}Z_r\Bigr)G(u)=p^kF(Z).
\end{equation}
To prove it, fix input positions $i_1<\cdots<i_k$ that supply the
specified retained bits. Their own retention contributes $p^k$. Every input
position before $i_1$ contributes $q+pu_0$ according to whether it is
deleted or retained; there are $i_1-1$ such positions. Similarly, the
$i_{r+1}-i_r-1$ positions between $i_r$ and $i_{r+1}$ each contribute
$q+pu_r$, and positions after $i_k$ contribute a factor of one. The
retained counts in these intervals are exactly $\ell_1-1$ and
$\ell_{r+1}-\ell_r-1$. Summing over all input tuples and applying $\Delta$
gives $G(u)$ as $p^k$ times the polynomial of \eqref{eq:input-polynomial}
with every displayed gap exponent reduced by one; multiplying by
$\prod_rZ_r$ proves \eqref{eq:trace-generating-identity}, including points
where some $Z_r=0$.

Suppose for the moment that
\begin{equation}\label{eq:trace-closeness}
 \abs{\Delta[T_I]}\le\varepsilon
 \quad\text{for every }I\subseteq\{1,\ldots,n\}\text{ with }1\le\abs I\le D_*.
\end{equation}
Since $k\le D_*$ the rank sum has at most $n^k$ terms, so
$\abs{G(u)}\le n^k\varepsilon$ when all $\abs{u_r}\le1$; on that polydisk
$\abs{Z_r}\le q+p=1$. Thus \eqref{eq:trace-generating-identity} gives
\begin{equation}\label{eq:trace-polydisk-bound}
 \abs{F(Z)}\le(n/p)^k\varepsilon
 \qquad\text{whenever }\abs{Z_r-q}\le p\ (0\le r<k).
\end{equation}
This uses only ordinary trace ranks and the convention that a rank
product is zero when the trace is too short.

\subsection{Simultaneous continuation and the separation bound}

The lower bound \eqref{eq:input-polynomial-signal} and the upper bound
\eqref{eq:trace-polydisk-bound} live at different points. In Cayley
coordinates the disk $\abs{Z-q}\le p$ becomes a half-plane:
\begin{equation}\label{eq:cayley-trace-disk}
 \abs{Z-q}\le p
 \iff \re\frac{1+Z}{1-Z}\ge\frac qp\qquad(\abs Z<1).
\end{equation}
Indeed, writing $w=(1+Z)/(1-Z)$ and expanding
$\abs{pw-(1+q)}^2\le p^2\abs{w+1}^2$ reduces it to $4q\le4p\re w$. We move
all coordinates into this half-plane with one complex variable. A single
strip interpolation avoids paying a separate continuation loss per
coordinate.

Write
\[
 w_r=\frac{1+Z_r^*}{1-Z_r^*}=\xi_r+\ii\zeta_r,\qquad \xi_r\ge c_3\gamma,
\]
with $\xi_r,\zeta_r\in\RR$. For $v\in\CC$ set
\begin{equation}\label{eq:simultaneous-path}
 w_r(v)=(1+v)\xi_r+\ii\zeta_r,\quad
 Z_r(v)=\frac{w_r(v)-1}{w_r(v)+1},\quad
 R=1+\frac{q}{pc_3\gamma}.
\end{equation}
A common real value of $v$ moves every starting coordinate into the trace
half-plane at once. Concretely, in the $Z$-plane the region
$\abs{Z-q}\le p$ is a disk; after the Cayley map
$w=(1+Z)/(1-Z)$ it becomes the half-plane $\re w\ge q/p$. Each path
$w_r(v)=(1+v)\re w_r+\ii\,{\rm Im}\,w_r$ is a horizontal segment starting
at $w_r$ and ending at $w_r(R)$ with $\re w_r(R)=(1+R)\xi_r\ge q/p$. All
coordinates use the same parameter $0\le v\le R$; the proof interpolates
$F(Z_0(v),\ldots,Z_{k-1}(v))$ on one complex strip, simultaneously for
every coordinate (Figure~\ref{fig:simultaneous-cayley}).

\suppressfloats[t]
\begin{figure}[htbp]
\centering
\begin{tikzpicture}[x=1.2cm,y=1.2cm,>=Stealth,font=\small]
 \begin{scope}
  \fill[blue!4] (0,0) circle (1);
  \fill[teal!17] (0.4,0) circle (0.6);
  \draw[black!35,->] (-1.2,0)--(1.32,0) node[right] {$\re Z$};
  \draw[black!35,->] (0,-1.16)--(0,1.2);
  \draw[black!65] (0,0) circle (1);
  \draw[teal!65!black] (0.4,0) circle (0.6);
  \fill (0.4,0) circle (0.022) node[below right] {$q$};
  \node[below right] at (1,0) {$1$};
  \fill[blue!70!black] (-0.2027,0.5791) circle (0.027)
       node[above left] {$Z_0^*$};
  \fill[orange!80!black] (-0.1753,-0.4310) circle (0.027)
       node[below left] {$Z_1^*$};
  \node at (0,1.5) {The $Z$-plane};
  \node at (0,-1.42) {$\abs{Z-q}\le p$ is shaded};
 \end{scope}
 \draw[->,thick] (1.68,0.22)--(3.78,0.22)
       node[midway,above=5pt] {$w=\dfrac{1+Z}{1-Z}$};
 \begin{scope}[xshift=6cm]
  \fill[blue!4] (0,-1.1) rectangle (2.85,1.1);
  \fill[teal!17] (0.6667,-1.1) rectangle (2.85,1.1);
  \draw[black!35,->] (-0.15,0)--(3,0) node[right] {$\re w$};
  \draw[black!65,->] (0,-1.16)--(0,1.22);
  \draw[dashed,teal!65!black] (0.6667,-1.1)--(0.6667,1.1);
  \node[below right] at (0.6667,0) {$q/p$};
  \draw[->,thick,blue!70!black] (0.35,0.65)--(1.6333,0.65);
  \fill[blue!70!black] (0.35,0.65) circle (0.027)
        node[above left] {$w_0$};
  \fill[blue!70!black] (1.6333,0.65) circle (0.027)
        node[above] {$w_0(R)$};
  \draw[->,thick,orange!80!black] (0.5,-0.55)--(2.3333,-0.55);
  \fill[orange!80!black] (0.5,-0.55) circle (0.027)
        node[below left] {$w_1$};
  \fill[orange!80!black] (2.3333,-0.55) circle (0.027)
        node[below] {$w_1(R)$};
  \node at (1.4,1.5) {The $w$-plane};
  \node at (1.4,-1.42) {Both paths use the same $0\le v\le R$};
 \end{scope}
\end{tikzpicture}
\caption{Geometry of the simultaneous continuation. The Cayley map turns
the deletion disk into $\re w\ge q/p$. Two possible starting coordinates
are shown; the horizontal arrows have different lengths but share the
same parameter: $w_r(v)=(1+v)\re w_r+\ii\operatorname{Im}w_r$ for
$0\le v\le R$. The proof interpolates
$F(Z_0(v),\ldots,Z_{k-1}(v))$ on one complex strip, simultaneously for
every coordinate.}
\label{fig:simultaneous-cayley}
\end{figure}

On the closed strip $-1/2\le\re v\le R$ we have
$\re w_r(v)=(1+\re v)\xi_r>0$, so all $Z_r(v)$ lie in the unit disk and
depend analytically on $v$; at $v=0$ they equal $Z_r^*$. On the right
boundary $\re w_r(v)=(1+R)\xi_r\ge q/p$, so \eqref{eq:trace-polydisk-bound}
applies. Moreover
\begin{equation}\label{eq:strip-width}
 1+R\le C\frac{Y^\alpha}{p},
\end{equation}
because $\gamma=c_2q_*Y^{-\alpha}$ and $q\le q_*$.

We need a left-boundary bound free of $n^k$. The identity
$1-\abs Z^2=4\re w/\abs{w+1}^2$ gives, at $\re v=-1/2$,
\begin{equation}\label{eq:left-boundary-distance}
 1-\abs{Z_r(v)}\ge\frac{1-\abs{Z_r^*}}{4(1+\abs v)^2}.
\end{equation}
To check the constant, first use
$1-\abs{Z_r(v)}\ge\xi_r/\abs{w_r(v)+1}^2$ and
$1-\abs{Z_r^*}\le4\xi_r/\abs{w_r+1}^2$, then
$\abs{w_r(v)+1}\le\abs{w_r+1}+\xi_r\abs v\le(1+\abs v)\abs{w_r+1}$.
The coefficients of $F$ have magnitude at most two, so summing independent
geometric series over the positive prefix and gap lengths gives, in the
open unit polydisk,
\[
 \abs{F(Z)}\le2\prod_{r=0}^{k-1}\frac1{1-\abs{Z_r}}.
\]
It follows from \eqref{eq:left-boundary-distance} that
\[
 g(v):=\frac{F(Z_0(v),\ldots,Z_{k-1}(v))}{(2+v)^{2k}}
\]
has the boundary bounds
\begin{equation}\label{eq:strip-side-bounds}
 \begin{aligned}
  \log\abs{g(v)}&\le W_*+Ck+C &&(\re v=-1/2),\\
  \log\abs{g(v)}&\le k\log(n/p)+\log\varepsilon &&(\re v=R).
 \end{aligned}
\end{equation}
On the left $(1+\abs v)/\abs{2+v}$ is bounded absolutely; on the right
$\abs{2+v}\ge2+R>1$. The function $g$ is analytic and bounded on the strip,
since $F$ is a finite polynomial on the unit polydisk and $\abs{2+v}\ge3/2$.

The strip estimate we use is a consequence of the maximum principle. If a
bounded analytic function on $a\le\re v\le b$ has logarithmic boundary
bounds $L_-,L_+$, then at real $t\in[a,b]$ its logarithm is at most
$((b-t)L_-+(t-a)L_+)/(b-a)$. Multiply by the exponential of the negative
affine interpolant to make both sides one; on rectangles of height tending
to infinity apply the maximum principle after multiplying by
$\exp\{\tau(v^2-\max\{a^2,b^2\})\}$ for $\tau>0$, which has modulus at most
one on the vertical sides and tends to zero on the horizontal sides. Let
the height tend to infinity, then $\tau\to0$; this proves the estimate,
including zeros of the function by continuity.

At $t=0$ the right boundary has weight $1/(2R+1)$. By
\eqref{eq:input-polynomial-signal}, $\log\abs{g(0)}\ge-E_h-1-2k\log2$.
Substituting \eqref{eq:strip-side-bounds} gives
\begin{align}
 \log(1/\varepsilon)
 &\le k\log(n/p)+(2R+1)(E_h+1+2k\log2)+2R(W_*+Ck+C)\notag\\
 &\le k\log(n/p)+C(1+R)\bigl(E_h+4^hA_0\bigr).
 \label{eq:separation-exponent}
\end{align}
This is the quantitative transfer from input coordinates to trace
coordinates.

It remains to compare this exponent with the budget \eqref{eq:budget}. Put
$t=\log_2\mu$. The choices in \eqref{eq:separation-cutoff} give
$t+\alpha<3$, and
\[
 4^h\le CY^2,\qquad E_h\le CA_0Y^t,\qquad
 A_0\le Q(1+\log Y),\qquad QY\le C\log n.
\]
Thus \eqref{eq:strip-width} yields
\begin{align*}
 (1+R)E_h
 &\le\frac Cp(\log n)Y^{t+\alpha-1}(1+\log Y)
 \le\frac Cp(\log n)Y^2(1+\log Y),\\
 (1+R)4^hA_0
 &\le\frac Cp(\log n)Y^{1+\alpha}(1+\log Y)
 \le\frac Cp(\log n)Y^2(1+\log Y).
\end{align*}
Also, since $n\ge2$ and $\log(1/p)\le1/p$,
\[
 k\log(n/p)\le CY^2\bigl(\log n+\log(1/p)\bigr)
 \le\frac Cp(\log n)Y^2.
\]
Using \eqref{eq:aux-comparisons-2}, the right-hand side of
\eqref{eq:separation-exponent} is at most
\begin{equation}\label{eq:final-B-bound}
 \frac Cp(\log n)Y^2(1+\log Y)
 \le C_6\,p^{-1}(\log n)\mathsf X(n,p)^2
      \bigl(1+\log\mathsf X(n,p)\bigr)^6
 =C_6\,B(n,p).
\end{equation}
Taking $\varepsilon=e^{-C_{\mathrm{sep}}B(n,p)}$ with
$C_{\mathrm{sep}}>C_6$ contradicts \eqref{eq:separation-exponent}, so
\eqref{eq:trace-closeness} fails for that $\varepsilon$. This proves
Theorem~\ref{thm:separation} with the cutoff \eqref{eq:separation-cutoff}.

All constants were fixed in this order: those of
Proposition~\ref{prop:multiscale}; then $J_*,H,\eta$; then $C_5,c_2$; and
finally $C_{\mathrm{sep}}$. Nothing depends on the denominator of $p$ or
on how close $p$ is to an endpoint. In particular, when $q<1/n$ the cutoff
$q_*=1/n$ keeps $Y<2$ and $Q=1+\log n$, while $q/q_*\le1$ keeps the strip
estimate uniform; when $p$ is small the strip width is controlled by the
single factor $p^{-1}$ already in the budget. The case $p=1$ is handled
directly in the decoding argument.

\section{A uniform decoder}\label{sec:decoding}

Theorem~\ref{thm:separation} gives a test for the first wrong bit of a
prefix: no moment system that fixes that prefix can match all the
low-order trace statistics. To turn this into an algorithm we must also
recognise a \emph{correct} prefix in bounded time. The extra fact that
makes this possible is that a correct prefix admits a moment system with
strict slack, both in its statistical constraints and in its positivity
condition. We first exhibit that slack, then give a rational procedure
that is guaranteed to find a feasible system whenever slack exists.

\subsection{Statistical constraints for a prefix}

Assume for now $p<1$. Choose an integer $D$ and a positive dyadic number
$\zeta=2^{-b_\zeta}$ so that
\begin{equation}\label{eq:decoder-parameters}
 D_*\le D\le CY^2,\quad
 \zeta\le\tfrac14,\quad
 4\zeta<e^{-C_{\mathrm{sep}}B(n,p)},\quad
 b_\zeta=O(B(n,p)),
\end{equation}
with $C_{\mathrm{sep}}$ from Theorem~\ref{thm:separation}. Integer
formulas for these choices come later. Let
\[
 \mathcal I_D=\{I\subseteq\{1,\ldots,n\}:1\le|I|\le D\},\quad
 N=|\mathcal I_D|,\quad
 T=512(1+N)\zeta^{-2},
\]
which is an integer. From $T$ independent traces form the empirical mean
$\widehat t_I$ of the rank observable defining $T_I$, for every
$I\in\mathcal I_D$. These are ordinary trace observables: a requested
rank that is absent contributes zero.

For each fixed input $x$ let $\mathcal G$ be the event
\begin{equation}\label{eq:empirical-good}
 |\widehat t_I-T_I(x)|\le\zeta/8\quad\text{for every }I\in\mathcal I_D.
\end{equation}
Each observable takes values in $\{0,1\}$, so its empirical mean has
variance at most $1/(4T)$. Chebyshev and a union bound give
\begin{equation}\label{eq:good-probability}
 \mathbb P_x(\mathcal G^c)\le\frac{16N}{T\zeta^2}\le\frac1{32}.
\end{equation}
The same event controls all the prefix tests, even though the prefixes are
chosen using the data.

For a proposed prefix, use the remaining sign variables and their moment
matrix $M(m)=\mathcal M_D(m)$ from \eqref{eq:moment-matrix}; its nonempty
moment coordinates form a real vector $m$. Consider the rational
constraints
\begin{equation}\label{eq:prefix-feasibility}
 m\in[-1,1]^l,\quad M(m)\succeq0,\quad
 |\EE_m[T_I]-\widehat t_I|\le\zeta\quad(I\in\mathcal I_D),
\end{equation}
where $l$ is the number of moment coordinates. Substituting the prefix and
writing each remaining bit as one half of one plus its sign makes
$\EE_m[T_I]$ an affine function of $m$; its nonconstant coefficients have
absolute sum at most one by \eqref{eq:coeff-bounds}.

\begin{lemma}\label{lem:prefix-slack}
On $\mathcal G$, a prefix whose first incorrect bit is at its last
position has no solution to \eqref{eq:prefix-feasibility}. Every correct
prefix has a moment vector $m^*\in[-1,1]^l$ such that, with $G$ the
dimension of its moment matrix,
\begin{equation}\label{eq:prefix-slack}
 M(m^*)\succeq(\zeta/8)\operatorname{Id}_G,\qquad
 |\EE_{m^*}[T_I]-\widehat t_I|\le\zeta/2\quad(I\in\mathcal I_D).
\end{equation}
\end{lemma}

\begin{proof}
If a wrong prefix had a feasible moment vector, then
\eqref{eq:empirical-good} and \eqref{eq:prefix-feasibility} would give
$|\EE_m[T_I]-T_I(x)|\le9\zeta/8$ for all $I\in\mathcal I_D$, contradicting
Theorem~\ref{thm:separation} and \eqref{eq:decoder-parameters}.

For a correct prefix, mix the moments of the true completion with weight
$1-\zeta/8$ and the moments of independent uniform signs on the remaining
positions with weight $\zeta/8$. The latter moment matrix is the identity:
its $(I,J)$ entry is zero unless $I=J$. The mixture has the stated matrix
lower bound and coordinates in $[-1,1]$. Both constituent distributions
give channel expectations in $[0,1]$, so mixing changes each $T_I(x)$ by
at most $\zeta/8$; \eqref{eq:empirical-good} then bounds the discrepancy
from $\widehat t_I$ by $\zeta/4$, stronger than required.
\end{proof}

\subsection{Finding a moment system with slack}

The next lemma gives the bounded procedure for
\eqref{eq:prefix-feasibility}. It only promises to succeed when there is
slack, and every reported solution satisfies the exact inequalities. This
sidesteps deciding arbitrary semidefinite feasibility. The procedure is a
projected relaxation method in the tradition of Agmon and
Motzkin--Schoenberg \cite{Agmon1954,MotzkinSchoenberg1954}; we give the
iteration and its rounding analysis explicitly.

\begin{lemma}[Rational feasibility with slack]\label{lem:rational-feasibility}
Let $r\ge0$ and $D\ge1$ be integers, and let $m$ consist of the
\[
 l=\sum_{j=1}^{\min(2D,r)}\binom rj
\]
nonempty sign moments. Let $M(m)$ be their moment matrix, of dimension
\[
 G=\sum_{j=0}^{\min(D,r)}\binom rj.
\]
Suppose a finite list of rational affine inequalities $\ell_t(m)\le b_t$
is given, each with nonconstant coefficient vector of $\ell^1$-norm at
most one, together with a dyadic $0<\zeta\le1/4$. Then a deterministic
rational procedure either returns a vector with
\[
 m\in[-1,1]^l,\quad M(m)\succeq0,\quad \ell_t(m)\le b_t\ \text{for all }t,
\]
or reports failure. It returns a vector whenever some $m^*\in[-1,1]^l$
satisfies
\[
 M(m^*)\succeq(\zeta/8)\operatorname{Id}_G,\quad
 \ell_t(m^*)\le b_t-\zeta/2\ \text{for all }t.
\]
Put $\lambda=\zeta/(16G)$. The procedure performs at most
$\lceil10(1+l)/\lambda^2\rceil$ feasibility checks, each taking polynomially
many bit operations in the list dimensions, the input bit lengths, and
$\log(1/\zeta)$. These time bounds hold without the slack assumption.
\end{lemma}

\begin{proof}
If $l=0$ the matrix is $[1]$ and all inequalities are constant, so direct
rational comparisons suffice. Suppose $l>0$. We give exact separating
directions, then an iteration with bounded precision.

\paragraph{Directions from violated constraints.}
At a current point $m^{\mathrm{cur}}\in[-1,1]^l$ first check the affine
inequalities and the matrix condition exactly. If all hold, return the
current vector. A violated inequality $\ell_t(m^{\mathrm{cur}})>b_t$ gives
the direction $a$ equal to minus its nonconstant coefficient vector. Then
$\norm a_2\le1$ and, under the slack assumption,
$\langle m^*-m^{\mathrm{cur}},a\rangle\ge\zeta/2\ge\lambda$.

If instead the matrix condition fails, find a nonzero rational vector $v$
with $v^\top M(m^{\mathrm{cur}})v<0$ (constructed just below). Write the
associated affine form as $v^\top M(m)v=c+h\cdot m$ and set
$a=h/(G\,v^\top v)$. Each matrix entry is the constant $1$ or one moment
coordinate, so $\norm h_1\le\norm v_1^2\le G\norm v_2^2$ and
$\norm a_2\le1$. The slack matrix bound gives
\[
 \langle m^*-m^{\mathrm{cur}},a\rangle
 =\frac{v^\top(M(m^*)-M(m^{\mathrm{cur}}))v}{G\,v^\top v}
 \ge\frac{\zeta}{8G}\ge\lambda.
\]
Thus either violated condition yields a rational direction with
\begin{equation}\label{eq:feasibility-direction}
 \norm a_2\le1,\qquad \langle m^*-m^{\mathrm{cur}},a\rangle\ge\lambda
\end{equation}
whenever a slack solution exists. A violated constant inequality has zero
direction; that cannot happen in the slack case, and otherwise the
iteration is still bounded.

\paragraph{An exact matrix check.}
For a rational symmetric matrix, eliminate a positive diagonal pivot via
its Schur complement. Congruence by an invertible triangular matrix shows
the original is positive semidefinite exactly when the positive pivot and
this Schur complement are. A negative diagonal gives a negative unit
vector. If a remaining diagonal at $i$ is zero and its entry $b$ in column
$j$ is nonzero, let $c$ be the diagonal at $j$; we may assume $c\ge0$,
else a negative diagonal already exists. Then
\[
 y=e_i-\frac{b}{1+c+|b|}e_j
\]
has quadratic form
$\frac{b^2}{(1+c+|b|)^2}\bigl[-2(1+c+|b|)+c\bigr]<0$. Otherwise continue
with a positive diagonal pivot; when none remain, all entries are zero and
the remainder is positive semidefinite. A negative vector of a Schur
complement lifts to one of the original matrix using only rational
arithmetic: with $P$ the eliminated block and $B$ its block against the
remaining indices, the lift of $y$ is $v=(-P^{-1}By,\,y)$, whose quadratic
form equals that of $y$ for the Schur complement.

These operations have polynomial bit complexity. Clear denominators in a
rational matrix with $t$-bit entries; the product of all denominators has
at most $G^2t$ bits. If $H$ is the resulting integer matrix with $s$-bit
entries, the determinant expansion bounds every $j$-row minor by
$j!\,2^{js}$, of bit length $O(G(s+\log G))$. Schur-complement entries are
ratios of minors, and the inverse formula for $P$ gives the same bound for
the lift. Fraction-reduced elimination with rational comparisons computes
the check and the negative vector in polynomially many bit operations,
however small a positive pivot or negative quadratic form may be.

\paragraph{Iteration and rounding.}
Start with $m^{\mathrm{cur}}=0$. Choose the dyadic grid with mesh
\[
 \eta=2^{-g},\qquad
 g=\Bigl\lceil\log_2\frac{100(1+l)}{\lambda^2}\Bigr\rceil.
\]
The integer $g$ is computed by rational comparisons with powers of two, so
$\eta\le\lambda^2/(100(1+l))$, with $O(1+\log((1+l)/\lambda))$ fractional
bits. After an unsuccessful check, add $\lambda a$, clip every coordinate
to $[-1,1]$, and round to the nearest grid point in the box (both box
endpoints lie on the grid). Repeat up to the stated number of checks,
reporting failure if none accepts.

Under the slack assumption \eqref{eq:feasibility-direction} gives
\[
 \norm{m^{\mathrm{cur}}+\lambda a-m^*}_2^2
 \le\norm{m^{\mathrm{cur}}-m^*}_2^2-\lambda^2.
\]
Clipping cannot increase distance to $m^*$; since both the clipped vector
and $m^*$ lie in the box, rounding changes the squared distance by at most
$4l\eta+l\eta^2<\lambda^2/2$. Each failed check thus decreases squared
distance by at least $\lambda^2/2$, whose initial value is at most $l$, so
acceptance occurs before the cap. Finally, rounding keeps every iterate on
a single grid of the indicated bit length; the exact matrix check, the
affine comparisons, forming and normalizing $h$, and one update involve
polynomially many rational operations on numbers of polynomial bit length,
and temporary denominators do not accumulate across updates. The fixed cap
and these bounds apply to every rational input list, with or without a
slack solution.
\end{proof}

For a prefix test, write each absolute-value constraint of
\eqref{eq:prefix-feasibility} as two affine inequalities and apply
Lemma~\ref{lem:rational-feasibility}. Lemma~\ref{lem:prefix-slack}
verifies exactly the slack hypotheses for a correct prefix, and every
acceptance, on any data, gives an actual moment system satisfying
\eqref{eq:prefix-feasibility}.

The decoder starts with the empty prefix and tests both one-bit
extensions. If precisely one accepts, it appends that bit; otherwise it
appends $0$. It repeats until the prefix has length $n$. The latter rule
specifies a length-$n$ output even on data where the statistical estimates
fail. There are at most $2n$ tests.

\subsection{Integer parameters and bit complexity}

We now realise the choices in \eqref{eq:decoder-parameters} using only the
binary input. Continue to assume $p<1$ and use $q_*,Q,Y$ from
\eqref{eq:aux-parameters}. Define the positive integers
\begin{align*}
 u&=1+\lceil\log_2 n\rceil, &
 v&=1+\lfloor\log_2(1/q_*)\rfloor,\\
 y&=1+\lceil u/v\rceil, &
 w&=1+\lceil\log_2 y\rceil, &
 a_p&=\lceil1/p\rceil.
\end{align*}
All logarithms here mean integer length comparisons. In particular the
integer part of a logarithm of a rational number is found by comparing its
numerator with power-of-two multiples of its denominator, and the rational
maximum defining $q_*$ is found by an integer comparison.

The elementary comparisons
\[
 u\asymp\log n,\quad v\asymp Q,\quad Y\le y\le C Y,\quad
 w\asymp1+\log Y,\quad p^{-1}\le a_p\le2p^{-1}
\]
have absolute constants. For the bound on $y$ use $u\ge(\log n)/\log2$
and $v\le Q/\log2$. With $Y\asymp\mathsf X(n,p)$ these give
\begin{equation}\label{eq:integer-budget-proxy}
 B(n,p)\le a_p\,u\,y^2\,w^6\le C\,B(n,p).
\end{equation}
Choose fixed positive integers $K_D,K_m$ large enough for the constants in
Theorem~\ref{thm:separation} and set
\begin{equation}\label{eq:integer-decoder-parameters}
 D=K_Dy^2,\qquad b_\zeta=K_m\,a_p\,u\,y^2\,w^6,\qquad
 \zeta=2^{-b_\zeta}.
\end{equation}
Since $D_*\le C Y^2$ and $B(n,p)\ge\log2$, these ensure all of
\eqref{eq:decoder-parameters}. The integers $D,b_\zeta$ in binary are
computable in time polynomial in the input bit lengths; writing the
denominator $2^{b_\zeta}$ then costs $O(b_\zeta)$ bits, included below.

Next form the rational constraints. For $I=\{l_1<\cdots<l_k\}$ and
$i_1<\cdots<i_k$ the coefficient of $X_{i_1}\cdots X_{i_k}$ in $T_I$ is
\begin{equation}\label{eq:explicit-channel-coefficient}
 \binom{i_1-1}{l_1-1}
 \prod_{j=1}^{k-1}
 \binom{i_{j+1}-i_j-1}{l_{j+1}-l_j-1}\,
 p^{l_k}q^{i_k-l_k},
\end{equation}
when all gap counts are possible and zero otherwise. Indeed the selected
positions must be retained, and the prefix and successive open gaps must
contain the indicated numbers of extra retentions; positions after $i_k$
are unrestricted. Formula \eqref{eq:explicit-channel-coefficient} follows
from multiplying these independent binomial probabilities.

If the input representation is $p=a/b$, every denominator in
\eqref{eq:explicit-channel-coefficient} divides $b^n$. Binomial
coefficients have $O(n)$ bits. Sign expansion adds a denominator dividing
$2^D$, and empirical means have denominator $T$. Hence the constraint
coefficients have polynomial bit length in $n+L+D+\log T$. Enumerating the
rank and input tuples, expanding the resulting bit monomials, and
substituting the prefix constructs them directly; no list of complete
trace masks is needed.

These enumerations fit the resource scale. From $D=O(Y^2)$,
$Y\asymp\mathsf X(n,p)$, and \eqref{eq:budget},
\begin{equation}\label{eq:decoder-size-bound}
 D\log n=O(B(n,p)).
\end{equation}
The rank list, every matrix basis, and every moment list have size at most
$(n+1)^{2D}=\exp(O(B(n,p)))$, and so do input tuple lists. A sign expansion
has at most $2^D$ terms; products of these enumerations remain
$\exp(O(B(n,p)))$. Subsets larger than the available positions are simply
absent, so this includes $D>n$ and prefixes with very few remaining
positions.

By \eqref{eq:decoder-parameters}, $T$ is $\exp(O(B(n,p)))$. For every
prefix the iteration cap of Lemma~\ref{lem:rational-feasibility} is at most
\[
 2560(1+l)G^2\zeta^{-2}+1=\exp(O(B(n,p))),
\]
and the bit length of its grid is $O(b_\zeta+\log G+\log(1+l))=O(B(n,p))$.
The coefficient bounds and that lemma bound all computation by a fixed
polynomial in
\begin{equation}\label{eq:decoder-total-resource}
 n+L+\exp(O(B(n,p))),
\end{equation}
including parameter and constraint construction, exact rational
arithmetic, and the at most $2n$ prefix tests.

\begin{proof}[Proof of Theorem~\ref{thm:main}]
If $p=1$, request one trace and output it. For the universal halting
specification, output $0^n$ if the supplied well-formed trace has a
different length; the actual channel always supplies the input itself,
and this branch takes polynomially many bit operations in $n+L$.

For $p<1$, use \eqref{eq:integer-decoder-parameters}, request the $T$
traces, and compute the empirical statistics. Run the prefix rule. This
defines the machine on every stream of well-formed traces.

On $\mathcal G$, induction on prefix length shows precisely the correct
extension accepts: the incorrect extension is infeasible by
Lemma~\ref{lem:prefix-slack}, and the correct one has the slack that
guarantees acceptance. Thus the output is $x$ on $\mathcal G$, whose
probability is at least $31/32>2/3$ for each fixed $x$.

Each trace has at most $n$ bits and one delimiter. Reading the traces and
computing each of the finitely many rank observables costs polynomially
many bit operations in $n+T+N$; the empirical counters have $O(\log T)$
bits. All loops, including all feasibility tests, have the input-dependent
caps already given. Thus \eqref{eq:decoder-total-resource} bounds every
well-formed trace stream, independently of the success event, and the
machine can ignore its internal random bits.

To pin the computational model, the finite lists are stored sequentially
on tapes; replacing an indexed lookup by a scan costs at most a polynomial
factor in their total encoded length. Integer addition, multiplication,
division, and fraction reduction have elementary polynomial-time multitape
implementations. The bit-length and loop bounds thus give absolute
constants $K,d$ with trace count at most $\exp(KB(n,p))$ and total bit cost
at most $(n+L+\exp(KB(n,p)))^d$, after enlarging $K,d$ to absorb fixed
factors. This enlargement is uniform because $B(n,p)\ge\log2$. Choose
absolute $C,c$ with $C\ge K$ and $c\ge d$; both the sample bound $M_C(n,p)$
and the runtime $(n+L+M_C(n,p))^c$ follow. All constants in parameter
selection are fixed integers in one finite program.
\end{proof}

\begin{thebibliography}{99}

\bibitem{Agmon1954}
Shmuel Agmon.
The relaxation method for linear inequalities.
\emph{Canadian Journal of Mathematics} \textbf{6} (1954), 382--392.

\bibitem{BKKM2004}
Tu\u{g}kan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor.
Reconstructing strings from random traces.
In \emph{Proceedings of the Fifteenth Annual ACM--SIAM Symposium on
Discrete Algorithms (SODA)}, 2004, pp.~910--918.

\bibitem{BE1997}
Peter Borwein and Tam\'as Erd\'elyi.
Littlewood-type problems on subarcs of the unit circle.
\emph{Indiana University Mathematics Journal} \textbf{46}(4) (1997),
1323--1346.

\bibitem{BVW2026}
Arnav Burudgunte, Paul Valiant, and Hongao Wang.
Quasipolynomial trace reconstruction.
Preprint, 2026. arXiv:2607.04073v1.

\bibitem{Chase2021Lower}
Zachary Chase.
New lower bounds for trace reconstruction.
\emph{Annales de l'Institut Henri Poincar\'e, Probabilit\'es et
Statistiques} \textbf{57}(2) (2021), 627--643.

\bibitem{Chase2021Upper}
Zachary Chase.
Separating words and trace reconstruction.
In \emph{Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of
Computing (STOC)}, 2021, pp.~21--31.

\bibitem{CDLS2024}
Xi Chen, Anindya De, Chin Ho Lee, and Rocco A.~Servedio.
Trace reconstruction from local statistical queries.
In \emph{Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques (APPROX/RANDOM 2024)}, LIPIcs \textbf{317}
(2024), 52:1--52:24.

\bibitem{CDLSS2021LowDeletion}
Xi Chen, Anindya De, Chin Ho Lee, Rocco A.~Servedio, and Sandip Sinha.
Polynomial-time trace reconstruction in the low deletion rate regime.
In \emph{12th Innovations in Theoretical Computer Science Conference
(ITCS 2021)}, LIPIcs \textbf{185} (2021), 20:1--20:20.

\bibitem{CDLSS2021Smoothed}
Xi Chen, Anindya De, Chin Ho Lee, Rocco A.~Servedio, and Sandip Sinha.
Polynomial-time trace reconstruction in the smoothed complexity model.
In \emph{Proceedings of the 2021 ACM--SIAM Symposium on Discrete
Algorithms (SODA)}, 2021, pp.~54--73. arXiv:2008.12386.

\bibitem{CGLSZ2024}
Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, and Minshen Zhu.
On $k$-mer-based and maximum likelihood estimation algorithms for trace
reconstruction.
In \emph{2024 IEEE International Symposium on Information Theory (ISIT)},
2024, pp.~879--884. arXiv:2308.14993v2.

\bibitem{DOS2019}
Anindya De, Ryan O'Donnell, and Rocco A.~Servedio.
Optimal mean-based algorithms for trace reconstruction.
\emph{Annals of Applied Probability} \textbf{29}(2) (2019), 851--874.

\bibitem{HoldenLyons2020}
Nina Holden and Russell Lyons.
Lower bounds for trace reconstruction.
\emph{Annals of Applied Probability} \textbf{30}(2) (2020), 503--525.

\bibitem{HMPW2008}
Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder.
Trace reconstruction with constant deletion probability and related
results.
In \emph{Proceedings of the Nineteenth Annual ACM--SIAM Symposium on
Discrete Algorithms (SODA)}, 2008, pp.~389--398.

\bibitem{Lasserre2001}
Jean B.~Lasserre.
Global optimization with polynomials and the problem of moments.
\emph{SIAM Journal on Optimization} \textbf{11}(3) (2001), 796--817.

\bibitem{Levenshtein2001}
Vladimir I.~Levenshtein.
Efficient reconstruction of sequences.
\emph{IEEE Transactions on Information Theory} \textbf{47}(1) (2001),
2--22.

\bibitem{MotzkinSchoenberg1954}
Theodore S.~Motzkin and Isaac J.~Schoenberg.
The relaxation method for linear inequalities.
\emph{Canadian Journal of Mathematics} \textbf{6} (1954), 393--404.

\bibitem{NP2017}
Fedor Nazarov and Yuval Peres.
Trace reconstruction with $\exp(O(n^{1/3}))$ samples.
In \emph{Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of
Computing (STOC)}, 2017, pp.~1042--1046.

\bibitem{Parrilo2000}
Pablo A.~Parrilo.
\emph{Structured semidefinite programs and semialgebraic geometry methods
in robustness and optimization}.
Ph.D. thesis, California Institute of Technology, 2000.

\end{thebibliography}

\end{document}