diff 58a5071..63c0b20 uniform_trace_reconstruction_v2.txt
diff --git a/uniform_trace_reconstruction_v2.txt b/uniform_trace_reconstruction_v2.txt
index d7a3aed..a9c680c 100644
--- a/uniform_trace_reconstruction_v2.txt
+++ b/uniform_trace_reconstruction_v2.txt
@@ -13,8 +13,7 @@
\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{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
@@ -29,34 +28,8 @@
\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$
@@ -67,22 +40,20 @@ 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
+$x$. The goal is an algorithm that succeeds with probability at least $2/3$
+\emph{for every} $x$ (a worst-case guarantee), while minimizing 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
+If the trace were the input up to independent bit flips, one 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
+random deletions shift everything. So the desired positions are
+``smeared out'', and local statistics do not suffice. What rescues the problem 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.
@@ -124,7 +95,6 @@ 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
@@ -138,107 +108,115 @@ $\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
+The proof is one long chain. The decoder is tested against a family of
+positive moment functionals, a convex relaxation of the set of genuine
+probability laws on strings. The heart of the argument 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}
+That is an analytic fact, proved by moving a local signal out to large
+distance scales and then rotating it into the trace generating
+function. Turning separation into an algorithm then tests one bit at a
+time using exact rational feasibility, with a bound on the cost. The
+lineage of these ideas comes next.
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.
+several combinatorial and probabilistic channel models. Batu, Kannan,
+Khanna, and McGregor brought reconstruction from independent random
+deletion traces into theoretical computer science, motivated partly by
+sequence alignment. What separates the deletion channel from
+coordinatewise denoising is that a single trace rank can originate at
+many input positions.
+
+doi.org/10.1109/18.904499
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
+and Wieder proved a worst-case sample bound of $\exp(\widetilde
+O(\sqrt n))$. 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. Their complex-analytic approach ties
+deletion statistics to bounded-coefficient polynomials, with analytic
+inequalities of Borwein and Erd\'elyi in the background. That
mean-based lower bound restricts a method, not arbitrary trace
algorithms.
+doi.org/10.1145/1347082.1347125
+doi.org/10.1214/18-AAP1394
+doi.org/10.1145/3055399.3055494
+doi.org/10.1512/iumj.1997.46.1435
+
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
+$\exp(O(n^{1/5}\log^5 n))$. 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. 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;
+their bound is quasipolynomial when $p^{-1}$ is polylogarithmic in $n$.
+The uniform reconstruction algorithm developed later builds on this
+strategy and adds an explicit bit-complexity bound.
+
+arxiv.org/pdf/2009.03296
+doi.org/10.1214/20-AIHP1089
+doi.org/10.1214/19-AAP1506
+arXiv:2607.04073
+
+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. Burudgunte, Valiant, and
+Wang explicitly separate testing two known strings from reconstructing
+an unknown string, and leave quasipolynomial-time reconstruction open
+for their approach. The extra separation proved later concerns 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}.
+regimes.
-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}.
+arxiv.org/pdf/2308.14993
+arXiv:2607.04073
+doi.org/10.4230/LIPIcs.ITCS.2021.20
-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.
+The use of nonlocal statistics is essential to the comparison with
+known barriers. Chen, De, Lee, and Servedio proved strong lower bounds
+for statistical queries restricted to short consecutive trace blocks.
+The statistics used later involve few ranks but may span the whole
+trace. The generating-function identity that transfers them from input
+coordinates has antecedents in higher-order trace reconstruction.
-\section{Moment relaxations and prefix separation}\label{sec:setup}
+doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.52
+arXiv:2607.04073
+arxiv.org/pdf/2008.12386
+arxiv.org/pdf/2009.03296
-We now describe exactly what the decoder measures and exactly what
-convex family it tests against. Everything the algorithm ever sees is a
+The positive moment relaxation is a Boolean instance of the semidefinite
+moment and sum-of-squares framework. The finite feasibility iteration is
+related to the classical relaxation methods of Agmon and
+Motzkin--Schoenberg. The analytic separation and the rational
+implementation are proved directly; no external trace-reconstruction or
+optimization theorem is imported.
+
+doi.org/10.1137/S1052623400366802
+doi.org/10.7907/2K6Y-CH43
+doi.org/10.4153/CJM-1954-037-2
+doi.org/10.4153/CJM-1954-038-x
+
+The decoder measures expected products of a few trace ranks and tests them
+against a convex family. 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
+the input positions behind those ranks are unknown, 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.
+of a partial guess. That relaxation is set up first, along with the
+separation theorem that makes it 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$,
@@ -261,13 +239,10 @@ 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.
+Lasserre and Parrilo. Only the defining positivity condition and its
+elementary consequences are used, 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
@@ -372,17 +347,15 @@ $I\subseteq[n]$ with $|I|\le D_*$ satisfies
\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.
+no distribution realises. Its proof runs through the construction of a slowly decaying signal, the
+transfer of that signal to trace statistics, and the decoder that turns
+the resulting separation into an algorithm. Once separation holds,
+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. A bounded rational computation then finds the feasible
+extension.
+
+The separation proof is analytic, so the objects it uses come first.
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}
@@ -414,24 +387,20 @@ $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
+\eqref{eq:initial-signal}. The whole multiscale argument 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
+equally important: those angle bounds later allow passage 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
+raising the order follows the strategy of Burudgunte, Valiant, and Wang, but here the comparison functional may be a truncated
positive moment functional, and the scale step uses Gram matrices of
polynomial vectors.
@@ -439,7 +408,7 @@ polynomial vectors.
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}.
+order \(2D\) satisfying the prefix conditions stated earlier.
Suppose
\[
0<S\le4,\qquad 0<S'\le\min\{1,\eta_0S\},\qquad 4k\le D,
@@ -472,11 +441,9 @@ added parameter; and every added parameter \(e^{-a+\ii\theta}\) obeys
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
+frequency is small. 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}
+parameters, built later.
Throughout the proof of Proposition~\ref{prop:multiscale} set
\begin{equation}\label{eq:window-parameters}
@@ -488,7 +455,7 @@ 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
+Repeated use will be made of 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
@@ -514,7 +481,7 @@ 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:
+First, $P$ is shown to keep 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}.
@@ -548,7 +515,7 @@ Set
\[
\Lambda(t)=\log\frac{U}{\abs{P(e^{\ii t})}}\ge0,
\]
-with value $+\infty$ at a boundary zero. We claim
+with value $+\infty$ at a boundary zero. The key estimate is
\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}
@@ -579,9 +546,7 @@ Summing over factors gives
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,
+The goal is 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
@@ -684,12 +649,10 @@ sum at most
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
+Lemma~\ref{lem:good-frequencies} applies to this $\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
+differences can be prescribed. These pairs 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.
@@ -800,16 +763,14 @@ $\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
+There is now 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}
+the Gaussian contour construction below does exactly that.
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
+frequency. That product is now written 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.
@@ -832,7 +793,7 @@ frequencies, the window weight is
Conjugation also conjugates the old inner-gap parameters, leaving their
dampings unchanged.
-\paragraph{A Gaussian contour with controlled total frequency.}
+{\itshape 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}}
@@ -878,7 +839,7 @@ position-dependent factors. Outside the measure-zero set $\Omega=0$,
\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
+$\ii\,du_m$. This quantity is bounded 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
@@ -929,7 +890,7 @@ 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.}
+{\itshape 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)
@@ -957,9 +918,7 @@ 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
+The outer weights are 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
@@ -1066,7 +1025,7 @@ 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.}
+{\itshape 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,
@@ -1112,22 +1071,18 @@ 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}
+Theorem~\ref{thm:separation} is now proved. 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
+First, enough scales are chosen 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
+Throughout, $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
@@ -1136,7 +1091,7 @@ Set
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
+difference from the true word, as set out earlier. Every
constant chosen below is independent of this system, of $n$, and of $p$.
For an absolute constant $\eta>0$ define
@@ -1169,7 +1124,7 @@ range gives
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
+The cost of these small scales is also needed. 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
@@ -1224,13 +1179,11 @@ $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
+Write $f=f^{(h)}$, $k=k_h$, $s=s_h$, $\omega=\omega_h$. There is 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
@@ -1259,8 +1212,8 @@ 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.
+$z\mapsto(1+z)/(1-z)$ sends the unit disk to the right half-plane, and a
+quantitative distance from its boundary is needed.
\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
@@ -1299,8 +1252,6 @@ 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}
@@ -1321,7 +1272,7 @@ 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
+A bound on the coordinates' collective closeness to the unit circle is also needed. 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),
@@ -1335,9 +1286,10 @@ using $e^u\ge1+u$. The height bound in \eqref{eq:scale-induction} and
\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
+different domain. This is a multivariate trace generating identity from the smoothed-analysis
+literature on higher-order trace reconstruction, and the same counting fact
+underlies the consecutive-block statistical-query work. The counting
+argument is given 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
@@ -1378,8 +1330,6 @@ $\abs{Z_r}\le q+p=1$. Thus \eqref{eq:trace-generating-identity} gives
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:
@@ -1388,8 +1338,8 @@ coordinates the disk $\abs{Z-q}\le p$ becomes a half-plane:
\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
+$\abs{pw-(1+q)}^2\le p^2\abs{w+1}^2$ reduces it to $4q\le4p\re w$. All
+coordinates are moved into this half-plane with one complex variable. A single
strip interpolation avoids paying a separate continuation loss per
coordinate.
@@ -1466,7 +1416,7 @@ every coordinate.}
\label{fig:simultaneous-cayley}
\end{figure}
-On the closed strip $-1/2\le\re v\le R$ we have
+On the closed strip $-1/2\le\re v\le R$ there holds
$\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}
@@ -1476,7 +1426,7 @@ applies. Moreover
\end{equation}
because $\gamma=c_2q_*Y^{-\alpha}$ and $q\le q_*$.
-We need a left-boundary bound free of $n^k$. The identity
+A left-boundary bound free of $n^k$ is needed. 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}.
@@ -1506,7 +1456,7 @@ 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
+The strip estimate used here 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
@@ -1572,19 +1522,15 @@ 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
+low-order trace statistics. To turn this into an algorithm, the construction 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
+condition. That slack is exhibited first, then a rational procedure is given
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}
@@ -1657,15 +1603,13 @@ 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.
+Motzkin--Schoenberg; the iteration and its rounding analysis are given
+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
@@ -1697,10 +1641,10 @@ $\log(1/\zeta)$. These time bounds hold without the slack assumption.
\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
+rational comparisons suffice. Suppose $l>0$. Exact separating
directions, then an iteration with bounded precision.
-\paragraph{Directions from violated constraints.}
+{\itshape 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
@@ -1727,13 +1671,13 @@ 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.}
+{\itshape 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$,
+$j$ is nonzero, let $c$ be the diagonal at $j$; assume $c\ge0$,
else a negative diagonal already exists. Then
\[
y=e_i-\frac{b}{1+c+|b|}e_j
@@ -1757,7 +1701,7 @@ 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.}
+{\itshape Iteration and rounding.}
Start with $m^{\mathrm{cur}}=0$. Choose the dyadic grid with mesh
\[
\eta=2^{-g},\qquad
@@ -1801,9 +1745,7 @@ 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
+The choices in \eqref{eq:decoder-parameters} are now realised 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*}
@@ -1925,113 +1867,6 @@ 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}
+\par
\end{document}