diff 63c0b20..b34550f uniform_trace_reconstruction_v2.txt
diff --git a/uniform_trace_reconstruction_v2.txt b/uniform_trace_reconstruction_v2.txt
index a9c680c..584cde7 100644
--- a/uniform_trace_reconstruction_v2.txt
+++ b/uniform_trace_reconstruction_v2.txt
@@ -3,36 +3,36 @@
% 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}
-\newtheorem{theorem}{Theorem}
-\newtheorem{proposition}[theorem]{Proposition}
-\newtheorem{lemma}[theorem]{Lemma}
-\newtheorem{corollary}[theorem]{Corollary}
-\theoremstyle{definition}
-\newtheorem{definition}[theorem]{Definition}
-\newtheorem{remark}[theorem]{Remark}
-\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}
-
-\begin{document}
-
-Fix a binary string $x=x_1\cdots x_n\in\{0,1\}^n$. A \emph{deletion trace}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Fix a binary string $x=x_1... x_n\in\{0,1\}^n$. A 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$
+the positions $1,2,...,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
@@ -41,7 +41,7 @@ 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$. The goal is an algorithm that succeeds with probability at least $2/3$
-\emph{for every} $x$ (a worst-case guarantee), while minimizing the
+for every $x$ (a worst-case guarantee), while minimizing the
two resources: how many traces it reads, and how many bit operations it
performs.
@@ -50,7 +50,7 @@ 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 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
+a family of carefully chosen 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.
@@ -58,48 +58,48 @@ 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}
+Define the budget proxy
+
+
\mathsf X(n,p) &=
- \begin{cases}
- 1+\dfrac{\log n}{1+\log(1/q)}, & q>0,\\[6pt]
+
+ 1+(\log n)/(1+\log(1/q)), & q>0,\\[6pt]
1, & q=0,
- \end{cases}\\[4pt]
+ \\[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}
+ (1+\log \mathsf X(n,p))^6 .
-\begin{theorem}[Uniform trace reconstruction]\label{thm:main}
+
+
+[Uniform trace reconstruction]
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*)]
+[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
+
+Moreover, for every internal sequence of random bits and
+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
+ (n+L+M_C(n,p))^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}
-For a fixed $p$, plugging $q>0$ constant into \eqref{eq:budget} gives
+
+For a fixed $p$, plugging $q>0$ constant into (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
+$B(n,p)=O_p((\log n)^3 (1+\log\log n)^6)$. 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
+$\exp(O_p((\log n)^3(1+\log\log n)^6))$, 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
@@ -111,7 +111,7 @@ and everything is polynomial in $n$.
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
+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.
That is an analytic fact, proved by moving a local signal out to large
@@ -150,9 +150,9 @@ doi.org/10.1512/iumj.1997.46.1435
Chase improved the general sample upper bound to
$\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,
+$Ω(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
+$\exp(p^{-7/3}(\log_2 n)^{c_0})$ 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
@@ -205,34 +205,34 @@ 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
+trace statistic: an expected product of a few trace ranks. Because
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}
+semidefinite (positivity) condition, and solves for a completion
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
+Throughout, $[n]=\{1,...,n\}$ and $X_1,...,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.
-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
+Fix a nonempty set of ranks $I=\{\ell_1<...<\ell_k\}⊆[n]$. The
+corresponding 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
+
+ T_I(X)=\sum_{i_1<...<i_k} c_{I;\,i_1,...,i_k}\,X_{i_1}... X_{i_k}.
+
+The coefficient $c_{I;\,i_1,...,i_k}$ is the probability that the
+input positions $i_1,...,i_k$ land at trace ranks
+$\ell_1,...,\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}
+
+ c_{I;\,i_1,...,i_k}\ge 0,\qquad
+ \sum_{i_1<...<i_k} c_{I;\,i_1,...,i_k}\le 1.
+
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
@@ -245,45 +245,45 @@ 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
-$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
+remaining positions $U=\{d+1,...,n\}$ introduce sign variables
+$Y_i=2X_i-1$, so that $Y_i^2=1$ and $X_i=(1+Y_i)/2$. A moment
+array assigns real numbers $m_J$ to subsets $J⊆ U$ with
+$|J|\le 2D$, with $m_∅=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\\
+
+ \mathcal M_D(m)=(m_{I△ J})_{\substack{I,J⊆ U\\
|I|,|J|\le D}}\succeq 0,
-\end{equation}
-where $\triangle$ is symmetric difference. Only subsets that actually
+
+where $△$ 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
+$\EE[\prod_{i\in J}Y_i]=m_J$ and extend complex-linearly. Call
+$u\mapsto\EE$ a positive moment functional of order $2D$ fixing
+$u$. The word ``positive'' asserts (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*)]
+[Elementary moment bounds]
+For every array obeying (eq:moment-matrix):
+[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
+ $< P,R>_{\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}
+
+
+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
+$J=I\sqcup K$ with $|I|,|K|\le D$. In (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
@@ -291,62 +291,62 @@ 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},
+the real symmetric positive semidefinite matrix (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}
+point (b) of Lemma~lem:moment-bounds gives the useful bound
+
\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}
+ Y=1+(\log n)/(Q).
+
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
+[Separation from a wrong prefix]
+There exist absolute constants $C_{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
+using (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
+$x_1,...,x_{d-1},1-x_d$ with $D\ge D_*$. Then some nonempty
+$I⊆[n]$ with $|I|\le D_*$ satisfies
\[
- \bigl|\EE[T_I]-T_I(x)\bigr|
- > \exp\bigl(-C_{\mathrm{sep}}\,B(n,p)\bigr).
+ |\EE[T_I]-T_I(x)|
+ > \exp(-C_{sep}\,B(n,p)).
\]
-\end{theorem}
-The theorem holds for \emph{every} feasible array, including arrays that
+
+The theorem holds for every feasible array, including arrays that
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,
@@ -356,87 +356,87 @@ 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
+Fix $x,d,\EE$ as above. For $1\le k\le 2D$ an 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}
+
+ f_j=\sum_{i_1<...<i_k=j}
+ X_{i_1}... 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}
+
+ H_f=\prod_{h=1}^{k-1}(1+\frac1{a_h}).
+
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
+For $s>0$ and $\omega\in\RR$, the 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 has one goal: to preserve a detectable signal
+(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.
-The signal \eqref{eq:signal} is a damped sum: it heavily discounts
+The signal (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
+of eight. Controlling the angles of the new gap parameters is
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, 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}
+[One multiscale step]
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
+(eq:feature), and let \(\Delta\) come from a moment functional of
order \(2D\) satisfying the prefix conditions stated earlier.
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}
+ E\ge C_0(1+k\log(2k)+\log H_f+\log\frac1{S'}).
+
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}
+
+ H_{f'}\le H_f^4(1+\frac1{\beta S'})^3 .
+
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
+list \((z_1,...,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
@@ -445,47 +445,47 @@ frequency is small. Second, expanding that product and
deforming Gaussian contours produces one feature with the claimed
parameters, built later.
-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}
+Throughout the proof of Proposition~prop:multiscale set
+
+ \sigma=(K\sqrt E)/(S'),\qquad
+ W(l)=\exp(-(l^2)/(2\sigma^2)),\qquad b=\beta S',
+
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.
Repeated use will be made of this consequence of
-\eqref{eq:multiscale-cost}. For any fixed product of powers of
+(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,
+ C(1+k\log(2k)+\log H_f+\log\frac1{S'})+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)].
+ \quadsatisfies\quad P(e^{\ii t})=\Delta[A(t)].
\]
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}.
-\end{equation}
+ \quadfor some\quad \abs{s_1/s-1}\le10^{-4}.
+
Let $V$ be a centred real normal variable with variance $\sigma^{-2}$.
Since $W(l)\,\mathbf E\,e^{Vl}=1$,
@@ -494,38 +494,38 @@ Since $W(l)\,\mathbf E\,e^{Vl}=1$,
\]
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).
+ W(l)\,\mathbf E[e^{Vl}\mathbf 1_{\{\abs V>\delta s\}}]
+ =\Pr\!(\abs{N(l/\sigma^2,\sigma^{-2})}>\delta s).
\]
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}
+
+ 2H_f(1+1/s)(2e^{-c\delta^2s^2\sigma^2}+e^{-\delta s^2\sigma^2/2}).
+
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
+$C_0$ large to make (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}.
+least that large. This proves (eq:window-interior-signal).
Set
\[
- \Lambda(t)=\log\frac{U}{\abs{P(e^{\ii t})}}\ge0,
+ Λ(t)=\log\frac{U}{\abs{P(e^{\ii t})}}\ge0,
\]
-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}
+with value $+∞$ at a boundary zero. The key estimate is
+
+ \int_{\RR}Λ(t)\,(s_1\,dt)/(\pi(s_1^2+(t-\omega)^2))\le1.001E.
+
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
+periodizing the density in (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
@@ -539,7 +539,7 @@ 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)}
+ \int_{\RR}Λ(t)(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).
\]
@@ -548,7 +548,7 @@ claim.
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
+with that difference. The product $A(t)A(t')bar$ 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
@@ -557,18 +557,18 @@ 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}
+[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}
+
+ 2\mu_r(\RR^2)=1-\frac4\piarctan(e^{-\pi/r});
+
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}
+(eq:cauchy-matching-mass) exceeds $0.737$ for $0<r\le2$.
-\begin{proof}
+
+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
@@ -585,15 +585,15 @@ 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
+subtract its translate by $r$. By (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}.
+ R(v)=\frac2r\sum_{m\ge0}\tau^{2m+1}\cos((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,
+ =(\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
@@ -602,143 +602,143 @@ 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,
+ =\frac4\piarctan\tau,
\]
-proving \eqref{eq:cauchy-matching-mass}. The expression decreases with
+proving (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
+$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}
+
+[Frequencies from the logarithmic bound]
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}
+$Λ:\RR\to[0,∞]$ be measurable satisfying
+(eq:poisson-log-bound). There is a real $\lambda$ with
+
+ \abs\lambda\le2s_1,\qquad Λ(\lambda)\le2.40E.
+
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}
+ Λ(t)+Λ(t')\le2.74E.
+
+
-\begin{proof}
+Proof.
The Cauchy mass of $[-2s_1,2s_1]$ is at least
\[
- \frac{\arctan(2-2.003)+\arctan(2+2.003)}\pi>0.418.
+ \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}.
+Because $1.001/0.418<2.40$, averaging proves (eq:single-frequency).
-For \eqref{eq:paired-frequencies}, apply Lemma~\ref{lem:cauchy-matching}
+For (eq:paired-frequencies), apply Lemma~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
+measure in (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
+$C_2\to∞$ 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
+$Λ(t)+Λ(t')$ is at most $1.001E$, so some retained pair has
sum at most
\[
- \frac{2(1.001)}{0.733}E<2.74E,
+ (2(1.001))/(0.733)E<2.74E,
\]
as required. The diagonal construction gives the same when $y=0$.
-\end{proof}
+
The window parameters satisfy $\abs\omega/s_1\le2.002/0.9999<2.003$, so
-Lemma~\ref{lem:good-frequencies} applies to this $\Lambda$. Individual
-frequencies in \eqref{eq:paired-frequencies} need not be small, but their
+Lemma~lem:good-frequencies applies to this $Λ$. Individual
+frequencies in (eq:paired-frequencies) need not be small, but their
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.
-\begin{lemma}[Gram chaining]\label{lem:gram-chain}
-Let $v_0,\ldots,v_J$, $J\ge1$, lie in a complex Hilbert space whose inner
+[Gram chaining]
+Let $v_0,...,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).
+ \abs{< v_i,v_{i-1}>-1}\le\xi\ (1\le i\le J).
\]
-Then $\abs{\langle v_J,v_0\rangle-1}\le2J^2\xi$.
-\end{lemma}
+Then $\abs{< v_J,v_0>-1}\le2J^2\xi$.
+
-\begin{proof}
+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
+ \abs{< h_i,v_{i-1}>}\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}
+$\abs{< h_i,v_0>}\le2\xi+4(i-1)\xi$. Sum over $i$ and use
+$< v_0,v_0>=1$.
+
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
+Lemma~lem:good-frequencies have magnitude at most $C_3S$. A product
+of one to four factors, each of the form $A(t)$ or $A(t)bar$ with
+$\abs t\le C_3S$, is called 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}
+[A balanced product keeps a signal]
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}
+
+
+Proof.
Suppose not: every balanced product has signal below
-$\epsilon=e^{-7.94E}$. The squared modulus $\abs{A(t)}^2$ is one such
+$ε=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,
+ \abs{\EE[A(t)]}^2\le\EE[\abs{A(t)}^2]\le\abs{B_x(t)}^2+ε,
\]
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{\Delta[A(t)]}\le2\abs{B_x(t)}+\sqrtε.
+
+At $\lambda$ from (eq:single-frequency) this implies
+
\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
+$\sqrtε=e^{-3.97E}$; fixed factors are absorbed by the lower bound
+on $E$ in (eq:multiscale-cost). For a pair in
+(eq:paired-frequencies), nonnegativity of $Λ$ gives both
signals at least $e^{-2.74E}$, and
\[
- \abs{\Delta[A(t)]\Delta[A(t')]}=U^2e^{-\Lambda(t)-\Lambda(t')}
+ \abs{\Delta[A(t)]\Delta[A(t')]}=U^2e^{-Λ(t)-Λ(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}
+Applying (eq:evaluation-lower-bound) to each gives
+
+ \abs{B_x(t)B_x(t')bar}\ge e^{-2.75E}.
+
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
+Take a monotone chain $0=y_0,y_1,...,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
+choose a pair from (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)}.
+ V_i=\frac{A(t)A(t')bar}{B_x(t)B_x(t')bar}\ (0<i<J),
+ \qquad V_J=(A(\lambda))/(B_x(\lambda)).
\]
The denominators are nonzero by
-\eqref{eq:endpoint-normalization}--\eqref{eq:pair-normalization}, and
+(eq:endpoint-normalization)--(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$.
@@ -749,80 +749,80 @@ 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}.
+ \abs{< v_i,v_{i-1}>-1}\le\xi,\qquad
+ \xi=ε e^{5.50E}=e^{-2.44E}.
\]
-Since $v_0=1$ has norm one, Lemma~\ref{lem:gram-chain} yields
+Since $v_0=1$ has norm one, Lemma~lem:gram-chain yields
\[
\abs{\Delta[A(\lambda)]}
- =\abs{B_x(\lambda)}\,\abs{\langle v_J,v_0\rangle-1}
+ =\abs{B_x(\lambda)}\,\abs{< v_J,v_0>-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}
+$\log(2UJ^2)<0.04E$ by (eq:multiscale-cost). This contradicts
+(eq:single-frequency) and proves the lemma.
+
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 below does exactly that.
-Lemma~\ref{lem:balanced-product} gives a product of at most four
+Lemma~lem:balanced-product gives a product of at most four
windowed Fourier sums with a substantial discrepancy and small total
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
+Proposition~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
+Fix a product from Lemma~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
+tuples that define $f$. An 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
+relabel its copies so $j_1\le...\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),
+
+ \prod_{r=1}^m W(j_r-d)\exp(\ii t_r(j_r-d)),
\qquad |t_r|\le C_3S,\qquad
- \Bigl|\sum_{r=1}^m t_r\Bigr|\le b.
-\end{equation}
+ |\sum_{r=1}^m t_r|\le b.
+
Conjugation also conjugates the old inner-gap parameters, leaving their
dampings unchanged.
{\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}}
- \int_{-\ii\infty}^{\ii\infty}
- \exp\Bigl(\frac{\sigma^2v^2}{2}+vl\Bigr)\,dv.
-\end{equation}
+
+ W(l)=\frac{\sigma}{\ii√(2\pi)}
+ \int_{-\ii∞}^{\ii∞}
+ \exp((\sigma^2v^2)/(2)+vl)\,dv.
+
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
+Set $\rho=1/2.002$. For $u=(u_1,...,u_m)\in\RR^m$ define
+
+ Ω=\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}
+ v_m=-mb-\rho|Ω|+\ii u_m.
+
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
+$-b-\rho|Ω|$. 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$;
+produce outer decay $b+\rho|Ω|$ 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$,
+of (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
+integrals vanish by Gaussian decay. Next fix $(u_1,...,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
+(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$,
@@ -831,36 +831,36 @@ 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}
+position-dependent factors. Outside the measure-zero set $Ω=0$,
+
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}
+ (\frac{\sigma}{√(2\pi)})^m
+ \exp((\sigma^2)/(2)\sum_{r=1}^m v_r^2)
+ (1+\ii\rhosgnΩ)\,du.
+
The last factor is the differential of the bent contour divided by
$\ii\,du_m$. This quantity is bounded uniformly over the frequencies in
-\eqref{eq:endpoint-window}; the bounds also give absolute convergence.
+(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
+ &=(m-1)b^2+(mb+\rho|Ω|)^2 \notag\\
+ &\le 3b^2+(2\rho√(\textstyle\sum_r u_r^2)+(4+\rho)b)^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
+(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.
+ \exp((C_4\sigma^2b^2)/(2)
+ -(c_1\sigma^2)/(2)\sum_r u_r^2)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
@@ -871,51 +871,51 @@ 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}}
+
+ \|\nu\|_{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$
+ &\le C'\exp\Bigl[((C_4K^2\beta^2)/(2)
+ -(c_1K^2)/(1024))E\Bigr].
+
+Here $\|\nu\|_{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
+
+ \|\nu\|_{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.
{\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)
- =\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}
+ =(\sum_{r=1}^m c_r)(j_m-d)
+ -\sum_{r=1}^{m-1}(\sum_{l=1}^r c_l)(j_{r+1}-j_r).
+
+So the largest endpoint has coefficient $-s'+\iiΩ$ with
+
+ s'=b+\rho|Ω|.
+
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}
+
+ \exp(-rb-\ii\sum_{l=1}^r(u_l+t_l)),\qquad 1\le r<m.
+
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'.
+ |Ω|\le(\beta+1/4)S',\qquad
+ \beta S'\le s'\le[\beta+\rho(\beta+1/4)]S'\le S',
+ \qquad |Ω|\le2.002s'.
\]
-The angle in \eqref{eq:endpoint-link} has absolute value at most
+The angle in (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$
+parameters satisfy (eq:multiscale-output) and the endpoint links
+satisfy (eq:added-parameters). The choice of $C_1$ uses only $C_3$
and $S'\le S$, imposing no new condition on $K$ or $\beta$.
The outer weights are at the right scale. To finish, each interleaving
@@ -925,9 +925,9 @@ 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
+$i_1<...<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
+between consecutive endpoints in (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.
@@ -940,7 +940,7 @@ 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}.
+factor-count assertion of Proposition~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
@@ -948,18 +948,18 @@ 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))$.
+$\exp((-s'+\iiΩ)(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
+[Assigning distinct edges to consecutive gaps]
+
+Let a connected multigraph have ordered vertices $i_1<...<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}
+
+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$
@@ -969,9 +969,9 @@ 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}:
+
+To see why distinctness matters, look at Figure~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
@@ -980,9 +980,9 @@ $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]
+[htbp]
\centering
-\begin{tikzpicture}[x=1.28cm,y=0.9cm,>=stealth,
+[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}]
@@ -999,27 +999,27 @@ supplies the bound for $g_2$.
\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}
+Lemma~lem:edge-gap-assignment gives
+
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\prod_{e\ assigned}(1+1/a_e)
+ \le\prod_{e\ 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
@@ -1029,65 +1029,65 @@ is the empty product one.
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}]
+
+ \Delta[product]
=\sum_{\mathcal I}\int_{\RR^m}
- \mathcal S_{f^{\mathcal I,u}}(s',\Omega)\,d\nu_{\mathcal I}(u).
-\end{equation}
+ \mathcal S_{f^{\mathcal I,u}}(s',Ω)\,d\nu_{\mathcal I}(u).
+
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$
+most the height in (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|
+
+ |\mathcal S_{f^{\mathcal I,u}}(s',Ω)|
\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
+Let $N_{int}$ be the number of interleavings and
+$V=2H_f^4(1+1/b)^4$. Hypothesis~(eq:multiscale-cost) with large
enough absolute $C_0$ gives
\[
- E\ge100,\qquad \log N_{\mathrm{int}}\le0.01E,\qquad \log V\le0.01E.
+ E\ge100,\qquad \log N_{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
+signal in (eq:product-feature-integral) with $u\in\mathcal U$ had
+magnitude below $e^{-7.98E}$, then (eq:contour-mass) and
+(eq:contour-uniform-signal) would give
\[
- |\Delta[\text{product}]|
- \le N_{\mathrm{int}}\bigl(e^{(0.005-7.98)E}+Ve^{-20E}\bigr)
+ |\Delta[product]|
+ \le N_{int}(e^{(0.005-7.98)E}+Ve^{-20E})
\le e^{-7.965E}+e^{-19.98E}<e^{-7.94E}.
\]
-This contradicts Lemma~\ref{lem:balanced-product}. Some interleaving and
+This contradicts Lemma~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}
+$e^{-7.98E}$. Its order is at most $mk\le4k$; (eq:new-outer-decay)
and the bounds on $\mathcal U$ give the outer parameters;
-\eqref{eq:interleaving-height} gives \eqref{eq:multiscale-height}; and
+(eq:interleaving-height) gives (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}.
+(eq:added-parameters). This completes the proof of
+Proposition~prop:multiscale.
-Theorem~\ref{thm:separation} is now proved. Proposition~\ref{prop:multiscale}
+Theorem~thm:separation is now proved. Proposition~prop:multiscale
keeps a detectable input-coordinate signal while lowering its decay rate.
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, $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}
+(eq:aux-parameters). Recall from (eq:aux-comparisons) that
+
1\le\mathsf X(n,p)\le Y\le2\mathsf X(n,p),\qquad
QY=Q+\log n\le C\log n.
-\end{equation}
+
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
@@ -1095,88 +1095,88 @@ 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
-\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
+the decrease, write $θ=\eta q_*Y^{-\alpha}$ and $t_j=D_*S_j$, so
+$t_j=θ\,t_{j-1}\min\{1,t_{j-1}\}$. Then, whenever the quadratic
regime begins,
\[
- t_{J_*}\le\vartheta^{J_*}t_0
+ t_{J_*}\leθ^{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
+Proposition~prop:multiscale. Now $\log(1/θ)\ge Q$ and
+$t_j\le1$ for $j\ge J_*$. Iterating $t_j=θ t_{j-1}^2$ in that
range gives
-\begin{equation}\label{eq:terminal-scale}
- t_h\le\vartheta^{\,2^{h-J_*}-1}
+
+ t_h\leθ^{\,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.
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
- \log(1/\vartheta)\le CA_0,
+ \ell_j\le2\ell_{j-1}+\log(1/θ),\quad\ell_0=0,\quad
+ \log(1/θ)\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
+
+Now iterate Proposition~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}
+ =1-(2)/(e^4-1)>\frac12 .
+
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$
+
+
+The base case follows from (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
+(eq:scale-cost) give
\[
- \log H_{f^{(j)}}\le4\log H_{f^{(j-1)}}+3\log\bigl(1+1/(\beta S_j)\bigr)
+ \log H_{f^{(j)}}\le4\log H_{f^{(j-1)}}+3\log(1+1/(\beta S_j))
\le4\log H_{f^{(j-1)}}+C2^jA_0,
\]
-and summing this proves the height bound in \eqref{eq:scale-induction}.
+and summing this proves the height bound in (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).
+ C(1+j4^{j-1}+4^{j-1}A_0+2^jA_0).
\]
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
+Proposition~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$. There is a signal
@@ -1185,20 +1185,20 @@ step records where its parameters sit inside the unit disk; this controls
the cost of continuing the signal to the trace domain.
Call the parameters introduced between endpoints in any application of
-Proposition~\ref{prop:multiscale} \emph{elementary parameters}, and
+Proposition~prop:multiscale 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
+and $\abs{\theta}\le C_1S_{j-1}$. Using (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}.
+parameter preserves (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;
@@ -1206,7 +1206,7 @@ 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}.
+ N_0=0,\qquad N_j\le4N_{j-1}+1,\qquad N_j\le(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.
@@ -1215,17 +1215,17 @@ 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, and a
quantitative distance from its boundary is needed.
-\begin{lemma}[Products with controlled damping]\label{lem:product-cayley}
+[Products with controlled damping]
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.
+ \re(1+z)/(1-z)\ge c_3\gamma.
\]
-\end{lemma}
-\begin{proof}
+
+Proof.
Write $z=e^{-T+\ii\psi}$ with $T=\sum_j a_j>0$ and
$\psi=\sum_j\theta_j$. Let
\[
@@ -1235,7 +1235,7 @@ $\psi=\sum_j\theta_j$. Let
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)
+ T\ge\gamma(U+N\!\!\sum_{\abs{\theta_j}<1/N}\theta_j^2)
\ge\gamma(U+V^2).
\]
If $U\ge1$ or $V\ge1$ the bracket is at least one; otherwise
@@ -1246,63 +1246,63 @@ $U+V^2\ge U^2+V^2\ge(U+V)^2/2$. Since $\abs\psi\le U+V$, in all cases
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.
+ \abs{1-z}^2\le C(T^2+\min\{1,\psi^2\})\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}
-Let $z_1,\ldots,z_{k-1}$ be the inner gap parameters of the final feature
+
+Let $z_1,...,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}
+
+ F(Z_0,...,Z_{k-1})
+ =\sum_{1\le i_1<...<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}
+at most $D_*$ elementary parameters, so Lemma~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}
+
+ \re(1+Z_r^*)/(1-Z_r^*)\ge c_3\gamma\qquad(0\le r<k).
+
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),
\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}
+using $e^u\ge1+u$. The height bound in (eq:scale-induction) and
+(eq:scale-cost) therefore give
+
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}
+ \le\log H_f+\log(1+1/(\beta S_h))\le C4^hA_0.
+
Now express the same polynomial through observable trace moments on a
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$
+$\ell=(\ell_1,...,\ell_k)$ with $1\le\ell_1<...<\ell_k\le n$ write
+$T_\ell=T_{\{\ell_1,...,\ell_k\}}$. For $u=(u_0,...,u_{k-1})\in\CC^k$
set
\[
- G(u)=\sum_{1\le\ell_1<\cdots<\ell_k\le n}
+ G(u)=\sum_{1\le\ell_1<...<\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
+
+ (\prod_{r=0}^{k-1}Z_r)G(u)=p^kF(Z).
+
+To prove it, fix input positions $i_1<...<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
@@ -1310,33 +1310,33 @@ $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}
+gives $G(u)$ as $p^k$ times the polynomial of (eq:input-polynomial)
with every displayed gap exponent reduced by one; multiplying by
-$\prod_rZ_r$ proves \eqref{eq:trace-generating-identity}, including points
+$\prod_rZ_r$ proves (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}
+
+ \abs{\Delta[T_I]}\leε
+ \quadfor every I⊆\{1,...,n\} with 1\le\abs I\le D_*.
+
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}
+$\abs{G(u)}\le n^kε$ when all $\abs{u_r}\le1$; on that polydisk
+$\abs{Z_r}\le q+p=1$. Thus (eq:trace-generating-identity) gives
+
+ \abs{F(Z)}\le(n/p)^kε
+ \qquadwhenever \abs{Z_r-q}\le p\ (0\le r<k).
+
This uses only ordinary trace ranks and the convention that a rank
product is zero when the trace is too short.
-The lower bound \eqref{eq:input-polynomial-signal} and the upper bound
-\eqref{eq:trace-polydisk-bound} live at different points. In Cayley
+The lower bound (eq:input-polynomial-signal) and the upper bound
+(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}
+ \iff \re(1+Z)/(1-Z)\ge\frac qp\qquad(\abs Z<1).
+
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$. All
coordinates are moved into this half-plane with one complex variable. A single
@@ -1345,14 +1345,14 @@ coordinate.
Write
\[
- w_r=\frac{1+Z_r^*}{1-Z_r^*}=\xi_r+\ii\zeta_r,\qquad \xi_r\ge c_3\gamma,
+ w_r=(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}
+ Z_r(v)=(w_r(v)-1)/(w_r(v)+1),\quad
+ R=1+(q)/(pc_3\gamma).
+
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
@@ -1360,14 +1360,14 @@ $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}).
+$F(Z_0(v),...,Z_{k-1}(v))$ on one complex strip, simultaneously for
+every coordinate (Figure~fig:simultaneous-cayley).
\suppressfloats[t]
-\begin{figure}[htbp]
+[htbp]
\centering
-\begin{tikzpicture}[x=1.2cm,y=1.2cm,>=Stealth,font=\small]
- \begin{scope}
+[x=1.2cm,y=1.2cm,>=Stealth,font=\small]
+
\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$};
@@ -1382,10 +1382,10 @@ every coordinate (Figure~\ref{fig:simultaneous-cayley}).
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]
+ node[midway,above=5pt] {$w=(1+Z)/(1-Z)$};
+ [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$};
@@ -1404,33 +1404,33 @@ every coordinate (Figure~\ref{fig:simultaneous-cayley}).
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
+same parameter: $w_r(v)=(1+v)\re w_r+\iiImw_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
+$F(Z_0(v),...,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$ 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}
+boundary $\re w_r(v)=(1+R)\xi_r\ge q/p$, so (eq:trace-polydisk-bound)
applies. Moreover
-\begin{equation}\label{eq:strip-width}
- 1+R\le C\frac{Y^\alpha}{p},
-\end{equation}
+
+ 1+R\le C(Y^\alpha)/(p),
+
because $\gamma=c_2q_*Y^{-\alpha}$ and $q\le q_*$.
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}.
-\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
@@ -1441,17 +1441,17 @@ 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
+It follows from (eq:left-boundary-distance) that
\[
- g(v):=\frac{F(Z_0(v),\ldots,Z_{k-1}(v))}{(2+v)^{2k}}
+ g(v):=\frac{F(Z_0(v),...,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}
+ \log\abs{g(v)}&\le k\log(n/p)+\logε &&(\re v=R).
+
+
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$.
@@ -1468,64 +1468,64 @@ 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)
+(eq:input-polynomial-signal), $\log\abs{g(0)}\ge-E_h-1-2k\log2$.
+Substituting (eq:strip-side-bounds) gives
+
+ \log(1/ε)
&\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}
+ &\le k\log(n/p)+C(1+R)(E_h+4^hA_0).
+
+
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
+It remains to compare this exponent with the budget (eq:budget). Put
+$t=\log_2\mu$. The choices in (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*}
+Thus (eq:strip-width) yields
+
(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)
+ k\log(n/p)\le CY^2(\log n+\log(1/p))
\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}
+Using (eq:aux-comparisons-2), the right-hand side of
+(eq:separation-exponent) is at most
+
\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
+ (1+\log\mathsf X(n,p))^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}.
+
+Taking $ε=e^{-C_{sep}B(n,p)}$ with
+$C_{sep}>C_6$ contradicts (eq:separation-exponent), so
+(eq:trace-closeness) fails for that $ε$. This proves
+Theorem~thm:separation with the cutoff (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
+Proposition~prop:multiscale; then $J_*,H,\eta$; then $C_5,c_2$; and
+finally $C_{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.
-Theorem~\ref{thm:separation} gives a test for the first wrong bit of a
+Theorem~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, the construction must also
-recognise a \emph{correct} prefix in bounded time. The extra fact that
+recognise a 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. That slack is exhibited first, then a rational procedure is given
@@ -1533,16 +1533,16 @@ that is guaranteed to find a feasible system whenever slack exists.
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
+ 4\zeta<e^{-C_{sep}B(n,p)},\quad
b_\zeta=O(B(n,p)),
-\end{equation}
-with $C_{\mathrm{sep}}$ from Theorem~\ref{thm:separation}. Integer
+
+with $C_{sep}$ from Theorem~thm:separation. Integer
formulas for these choices come later. Let
\[
- \mathcal I_D=\{I\subseteq\{1,\ldots,n\}:1\le|I|\le D\},\quad
+ \mathcal I_D=\{I⊆\{1,...,n\}:1\le|I|\le D\},\quad
N=|\mathcal I_D|,\quad
T=512(1+N)\zeta^{-2},
\]
@@ -1552,46 +1552,46 @@ $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}
+
+ |\widehat t_I-T_I(x)|\le\zeta/8\quadfor every I\in\mathcal I_D.
+
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}
+
+ \mathbb P_x(\mathcal G^c)\le(16N)/(T\zeta^2)\le\frac1{32}.
+
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
+matrix $M(m)=\mathcal M_D(m)$ from (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}.
+absolute sum at most one by (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
+position has no solution to (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
+
+ M(m^*)\succeq(\zeta/8)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}
+
+
+Proof.
If a wrong prefix had a feasible moment vector, then
-\eqref{eq:empirical-good} and \eqref{eq:prefix-feasibility} would give
+(eq:empirical-good) and (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}.
+Theorem~thm:separation and (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
@@ -1599,19 +1599,19 @@ 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
+at most $\zeta/8$; (eq:empirical-good) then bounds the discrepancy
from $\widehat t_I$ by $\zeta/4$, stronger than required.
-\end{proof}
+
The next lemma gives the bounded procedure for
-\eqref{eq:prefix-feasibility}. It only promises to succeed when there is
+(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; the iteration and its rounding analysis are given
explicitly.
-\begin{lemma}[Rational feasibility with slack]\label{lem:rational-feasibility}
+[Rational feasibility with slack]
Let $r\ge0$ and $D\ge1$ be integers, and let $m$ consist of the
\[
l=\sum_{j=1}^{\min(2D,r)}\binom rj
@@ -1625,48 +1625,48 @@ 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,
+ m\in[-1,1]^l,\quad M(m)\succeq0,\quad \ell_t(m)\le b_t\ 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.
+ M(m^*)\succeq(\zeta/8)Id_G,\quad
+ \ell_t(m^*)\le b_t-\zeta/2\ 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}
+
+Proof.
If $l=0$ the matrix is $[1]$ and all inequalities are constant, so direct
rational comparisons suffice. Suppose $l>0$. Exact separating
directions, then an iteration with bounded precision.
{\itshape Directions from violated constraints.}
-At a current point $m^{\mathrm{cur}}\in[-1,1]^l$ first check the affine
+At a current point $m^{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
+current vector. A violated inequality $\ell_t(m^{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$.
+$< m^*-m^{cur},a>\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
+with $v^\top M(m^{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.
+ < m^*-m^{cur},a>
+ =\frac{v^\top(M(m^*)-M(m^{cur}))v}{G\,v^\top v}
+ \ge(\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}
+
+ \norm a_2\le1,\qquad < m^*-m^{cur},a>\ge\lambda
+
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.
@@ -1680,10 +1680,10 @@ 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$; assume $c\ge0$,
else a negative diagonal already exists. Then
\[
- y=e_i-\frac{b}{1+c+|b|}e_j
+ y=e_i-(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
+$(b^2)/((1+c+|b|)^2)[-2(1+c+|b|)+c]<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
@@ -1702,10 +1702,10 @@ the check and the negative vector in polynomially many bit operations,
however small a positive pivot or negative quadratic form may be.
{\itshape Iteration and rounding.}
-Start with $m^{\mathrm{cur}}=0$. Choose the dyadic grid with mesh
+Start with $m^{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.
+ g=\Bigl\lceil\log_2(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
@@ -1714,10 +1714,10 @@ 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
+Under the slack assumption (eq:feasibility-direction) gives
\[
- \norm{m^{\mathrm{cur}}+\lambda a-m^*}_2^2
- \le\norm{m^{\mathrm{cur}}-m^*}_2^2-\lambda^2.
+ \norm{m^{cur}+\lambda a-m^*}_2^2
+ \le\norm{m^{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
@@ -1730,14 +1730,14 @@ 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}
+(eq:prefix-feasibility) as two affine inequalities and apply
+Lemma~lem:rational-feasibility. Lemma~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}.
+(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
@@ -1745,16 +1745,16 @@ 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.
-The choices in \eqref{eq:decoder-parameters} are now realised using only the
+The choices in (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*}
+(eq:aux-parameters). Define the positive integers
+
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
@@ -1767,36 +1767,36 @@ The elementary comparisons
\]
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}
+Theorem~thm:separation and set
+
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
+(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}
+Next form the rational constraints. For $I=\{l_1<...<l_k\}$ and
+$i_1<...<i_k$ the coefficient of $X_{i_1}... X_{i_k}$ in $T_I$ is
+
\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
+are unrestricted. Formula (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
+(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
@@ -1805,10 +1805,10 @@ 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}
+$Y\asymp\mathsf X(n,p)$, and (eq:budget),
+
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
@@ -1816,33 +1816,33 @@ $\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
+By (eq:decoder-parameters), $T$ is $\exp(O(B(n,p)))$. For every
+prefix the iteration cap of Lemma~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}]
+Proof. [Proof of Theorem~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$
+For $p<1$, use (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
+Lemma~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$.
@@ -1850,7 +1850,7 @@ 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
+caps already given. Thus (eq:decoder-total-resource) bounds every
well-formed trace stream, independently of the success event, and the
machine can ignore its internal random bits.
@@ -1865,8 +1865,8 @@ 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}
+
\par
-\end{document}
+