diff b1f9bc4..56bc728 uniform_trace_reconstruction_v2.txt
diff --git a/uniform_trace_reconstruction_v2.txt b/uniform_trace_reconstruction_v2.txt
index 5744693..2a2318d 100644
--- a/uniform_trace_reconstruction_v2.txt
+++ b/uniform_trace_reconstruction_v2.txt
@@ -30,18 +30,18 @@ usetikzlibrary{arrows.meta,positioning,calc,decorations.pathreplacing}
-Fix a binary string $x=x_1... x_nin{0,1}^n$. A deletion trace
+Fix a binary string x=x_1... x_nin{0,1}^n. A deletion trace
is the random string produced by the following experiment: walk through
-the positions $1,2,...,n$; keep position $i$ with probability $p$
-and drop it with probability $q=1-p$, independently at each $i$; the
+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
-trace is $11$. The trace reports
+x=1011 and the deletion removes positions 2 and 4, the resulting
+trace is 11. The trace reports
its own length and its bits, but nothing about which original positions
-survived. An algorithm is handed $n$, the value $p$ (as a rational
-number), and a stream of independent traces of $x$, and must output
-$x$. The goal is an algorithm that succeeds with probability at least $2/3$
-for every $x$ (a worst-case guarantee), while minimizing the
+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
+for every x (a worst-case guarantee), while minimizing the
two resources: how many traces it reads, and how many bit operations it
performs.
@@ -54,10 +54,10 @@ 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.
-Let $nge 2$ and let $p=a/bin(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.
+Let nge 2 and let p=a/bin(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 budget proxy
@@ -72,20 +72,20 @@ Define the budget proxy
[Uniform trace reconstruction]
-There are absolute constants $C,cge 1$ and one randomized multitape
-Turing machine $mathcal A$calA$ with the following property. Take any
-$nge 2$, any rational $pin(0,1]$, and any $xin{0,1}^n$. Given
-$n$ and $p$ in binary and access to independent deletion traces of $x$
-with retention probability $p$, the machine
+There are absolute constants C,cge 1 and one randomized multitape
+Turing machine mathcal AcalA with the following property. Take any
+nge 2, any rational pin(0,1], and any xin{0,1}^n. Given
+n and p in binary and access to independent deletion traces of x
+with retention probability p, the machine
[label=(roman*)]
-item reads at most $M_C(n,p)=bigllceil exp(C,B(n,p))bigrrceil$
+ reads at most M_C(n,p)=bigllceil exp(C,B(n,p))bigrrceil
traces,
-item outputs a string in ${0,1}^n$, and
-item returns $x$ with probability at least $2/3$.
+ outputs a string in {0,1}^n, and
+ returns x with probability at least 2/3.
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
+n, the machine halts within
[
(n+L+M_C(n,p))^c
]
@@ -95,18 +95,18 @@ and writing the output. The only thing not counted is the external
generation of the traces.
-For a fixed $p$, plugging $q>0$ constant into (eq:budget) gives
-$mathsf X(n,p)=O(sfX(n,p)=O(log n)$ and hence
-$B(n,p)=O_p((log n)^3 (1+loglog n)^6)$. Since
-$M_C=exp(CB)$, the number of traces is
-$exp(O_p((log n)^3(1+loglog 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 $qle n^{-kappa}$ for a
-fixed $kappa>0$, one has $1+log(1/q)ge kappalog n$, so
-$mathsf X(n,p)sfX(n,p)le 1+1/kappa$ is bounded and $p^{-1}$ is bounded by a
-constant depending only on $kappa$; then $B(n,p)=O_kappa(log n)$
-and everything is polynomial in $n$.
+For a fixed p, plugging q>0 constant into (eq:budget) gives
+mathsf X(n,p)=O(sfX(n,p)=O(log n) and hence
+B(n,p)=O_p((log n)^3 (1+loglog n)^6). Since
+M_C=exp(CB), the number of traces is
+exp(O_p((log n)^3(1+loglog 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 qle n^{-kappa} for a
+fixed kappa>0, one has 1+log(1/q)ge kappalog n, so
+mathsf X(n,p)sfX(n,p)le 1+1/kappa is bounded and p^{-1} is bounded by a
+constant depending only on kappa; then B(n,p)=O_kappa(log n)
+and everything is polynomial in n.
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
@@ -132,10 +132,10 @@ many input positions.
doi.org/10.1109/18.904499
For a fixed deletion probability, Holenstein, Mitzenmacher, Panigrahy,
-and Wieder proved a worst-case sample bound of $exp(widetilde
-O(sqrt n))$. In independent STOC 2017 papers, De, O'Donnell, and
+and Wieder proved a worst-case sample bound of exp(widetilde
+O(sqrt n)). In independent STOC 2017 papers, De, O'Donnell, and
Servedio, and separately Nazarov and Peres, proved
-$exp(O(n^{1/3}))$ bounds together with matching limitations for
+exp(O(n^{1/3})) bounds together with matching limitations for
methods that use only trace means. Their complex-analytic approach ties
deletion statistics to bounded-coefficient polynomials, with analytic
inequalities of Borwein and Erd'elyi in the background. That
@@ -148,13 +148,13 @@ doi.org/10.1145/3055399.3055494
doi.org/10.1512/iumj.1997.46.1435
Chase improved the general sample upper bound to
-$exp(O(n^{1/5}log^5 n))$. On the lower-bound side, Holden and Lyons
-proved an almost-$n^{5/4}$ bound and Chase strengthened it to
-$Ω(n^{3/2}/log^7 n)$ for fixed deletion probability. Burudgunte,
+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
+Ω(n^{3/2}/log^7 n) for fixed deletion probability. Burudgunte,
Valiant, and Wang then proved the sample bound
-$exp(p^{-7/3}(log_2 n)^{c_0})$ 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$.
+their bound is quasipolynomial when p^{-1} is polylogarithmic in n.
The uniform reconstruction algorithm developed later builds on this
strategy and adds an explicit bit-complexity bound.
@@ -165,7 +165,7 @@ arXiv:2607.04073
Sample complexity and reconstruction time need different arguments. At
fixed confidence, maximum likelihood reconstructs worst-case using at
-most $O(n)$ times the optimal sample count, but evaluating it over all
+most O(n) times the optimal sample count, but evaluating it over all
candidate strings requires a large search. Burudgunte, Valiant, and
Wang explicitly separate testing two known strings from reconstructing
an unknown string, and leave quasipolynomial-time reconstruction open
@@ -212,30 +212,30 @@ 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,...,n}$ and $X_1,...,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
+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<...<ell_k}⊆[n]$. The
+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
+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:
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
+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
- c_{I;,i_1,...,i_k}ge 0,qquad
+ c_{I;,i_1,...,i_k}ge 0,
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
+Thus T_I has degree at most k, nonnegative coefficients, and
+coefficient sum at most one; its coefficients are rational when p is
+rational. The algorithm estimates T_I(x) by averaging the observable
over independent traces. It never learns the coefficients' input
positions from the data, only the numeric value.
@@ -244,37 +244,37 @@ semidefinite moment and sum-of-squares frameworks of
Lasserre and Parrilo. Only the defining positivity condition and its
elementary consequences are used, all proved below.
-Fix a proposed prefix $uin{0,1}^d$ and a degree bound $Dge 1$. On the
-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
+Fix a proposed prefix uin{0,1}^d and a degree bound Dge 1. On the
+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
mathcal M_D(m)=(m_calM_D(m)=(m_{I△ J})_{substack{I,J⊆ U
|I|,|J|le D}}succeq 0,
-where $△$ is symmetric difference. Only subsets that actually
-exist are indexed, so the definition still makes sense when $D>|U|$ or
-$U$ is empty.
+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 $ile d$; expand each remaining
-bit as $(1+Y_i)/2$; reduce $Y_i^2=1$; then set
-$EE[prod_{iin J}Y_i]=m_J$ and extend complex-linearly. Call
-$umapstoEE$ a positive moment functional of order $2D$ fixing
-$u$. The word ``positive'' asserts (eq:moment-matrix), not the
+The array defines a functional EE on polynomials of degree at most
+2D as follows: substitute X_i=u_i for ile d; expand each remaining
+bit as (1+Y_i)/2; reduce Y_i^2=1; then set
+EE[prod_{iin J}Y_i]=m_J and extend complex-linearly. Call
+umapstoEE 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.
[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
+ abs{m_J}le 1 for every |J|le 2D;
+ 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
- $< P,R>_{EE}=EE[P,overlineoverline R]$R]$ is a positive
+ on polynomials of degree at most D, the form
+ < P,R>_{EE}=EE[P,overlineoverline R]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.
@@ -282,64 +282,64 @@ item on polynomials of degree at most $D$, the form
Proof.
-The empty moment equals one. Any nonempty $J$ with $|J|le 2D$ splits as
-$J=Isqcup 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
-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
+The empty moment equals one. Any nonempty J with |J|le 2D splits as
+J=Isqcup 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
+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 (eq:moment-matrix),
extended to complex coefficient vectors, gives the stated form;
-Cauchy--Schwarz follows by applying positivity to $P+zR$ for $zinCC$,
+Cauchy--Schwarz follows by applying positivity to P+zR for zinCC,
and it shows every zero-norm vector is orthogonal to every vector, so
the quotient is well defined.
-Now fix the true input $xin{0,1}^n$ and a prefix $u$ of length $d$
+Now fix the true input xin{0,1}^n and a prefix u of length d
that is wrong exactly at its last position,
- u_i=x_i (i<d),qquad u_d=1-x_d.
+ u_i=x_i (i<d), u_d=1-x_d.
-For any positive moment functional fixing $u$, define the discrepancy
+For any positive moment functional fixing u, define the discrepancy
Delta[P]=EE[P]-P(x).
-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_Aprod_{iin A}X_i$ has degree at most $2D$, then
+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_Aprod_{iin A}X_i has degree at most 2D, then
point (b) of Lemma~lem:moment-bounds gives the useful bound
abs{Delta[P]}le 2sum_A abs{c_A}.
-For $p<1$ introduce the bookkeeping quantities
+For p<1 introduce the bookkeeping quantities
- q_*=max(q,,1/n),qquad
- Q=1+log(1/q_*),qquad
+ q_*=max(q,,1/n),
+ Q=1+log(1/q_*),
Y=1+(log n)/(Q).
-When $qge 1/n$ these give $Y=mathsf X(n,p)$sfX(n,p)$ exactly. When $q<1/n$
-they give $1le mathsf X(n,p)sfX(n,p)le Y<2$. In all cases
+When qge 1/n these give Y=mathsf X(n,p)sfX(n,p) exactly. When q<1/n
+they give 1le mathsf X(n,p)sfX(n,p)le Y<2. In all cases
- mathsf X(n,p)sfX(n,p)le Yle 2,mathsf X(n,p),sfX(n,p),qquad
+ mathsf X(n,p)sfX(n,p)le Yle 2,mathsf X(n,p),sfX(n,p),
QY=Q+log nle Clog n
-for an absolute constant $C$, since $nge 2$.
+for an absolute constant C, since nge 2.
[Separation from a wrong prefix]
-There exist absolute constants $C_{sep}ge 1$ and an integer
-$Hge 1$ with the following property. For $nge 2$ and $0<p<1$ define
+There exist absolute constants C_{sep}ge 1 and an integer
+Hge 1 with the following property. For nge 2 and 0<p<1 define
[
D_*=4^{lceil log_2 Yrceil+H}le 4^{H+1}Y^2
]
-using (eq:aux-parameters). Take any $xin{0,1}^n$, any
-$din[n]$, and any positive moment functional of order $2D$ fixing
-$x_1,...,x_{d-1},1-x_d$ with $Dge D_*$. Then some nonempty
-$I⊆[n]$ with $|I|le D_*$ satisfies
+using (eq:aux-parameters). Take any xin{0,1}^n, any
+din[n], and any positive moment functional of order 2D fixing
+x_1,...,x_{d-1},1-x_d with Dge D_*. Then some nonempty
+I⊆[n] with |I|le D_* satisfies
[
|EE[T_I]-T_I(x)|
> exp(-C_{sep},B(n,p)).
@@ -356,46 +356,46 @@ 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 $1le kle 2D$ an order-$k$ feature is
-a family of polynomials indexed by the last position $j$,
+Fix x,d,EE as above. For 1le kle 2D an order-k feature is
+a family of polynomials indexed by the last position j,
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 jin[n],
+ jin[n],
-where $z_h=exp(-a_h+iitheta_h)$ with $a_h>0$ and
-$theta_hinRR$. For $k=1$ this is just $f_j=X_j$. Each $f_j$ sums over
+where z_h=exp(-a_h+iitheta_h) with a_h>0 and
+theta_hinRR. 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
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_fge 1$ bounds the sum of the
-absolute coefficients of every $f_j$.
+(1-e^{-a})^{-1}le 1+1/a shows that H_fge 1 bounds the sum of the
+absolute coefficients of every f_j.
-For $s>0$ and $omegainRR$, the signal of the feature is the
+For s>0 and omegainRR, the signal of the feature is the
exponentially damped Fourier sum
mathcal S_f(s,calS_f(s,omega)
=sum_{j=1}^n Delta[f_j],e^{(-s+iiomega)(j-d)}.
-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 $jge d$ contribute. For the base case $k=1$, where $f_j=X_j$,
-this reads $mathcal S_f(s,0)=calS_f(s,0)=sum_{jge 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
+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 jge d contribute. For the base case k=1, where f_j=X_j,
+this reads mathcal S_f(s,0)=calS_f(s,0)=sum_{jge 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
(eq:initial-signal). The whole multiscale argument has one goal: to preserve a detectable signal
-$mathcal S_f(s,calS_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
+mathcal S_f(s,calS_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 (eq:signal) is a damped sum: it heavily discounts
-positions more than about $1/s$ beyond the first disagreement. The next
+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.
+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 angles of the new gap parameters is
equally important: those angle bounds later allow passage from input
@@ -411,18 +411,18 @@ with this property. Let (f) be an order-(k) feature from
order (2D) satisfying the prefix conditions stated earlier.
Suppose
[
- 0<Sle4,qquad 0<S'lemin{1,eta_0S},qquad 4kle D,
+ 0<Sle4, 0<S'lemin{1,eta_0S}, 4kle D,
]
and, for some (beta Sle sle S) and (abs{omega}le2.002s),
- abs{mathcal S_f(s,calS_f(s,omega)}ge e^{-E},qquad
+ abs{mathcal S_f(s,calS_f(s,omega)}ge e^{-E},
Ege C_0(1+klog(2k)+log H_f+logfrac1{S'}).
Then there is an order-(k') feature (f'), with (1le k'le4k),
satisfying
- abs{mathcal S_calS_{f'}(s',omega')}ge e^{-7.98E},qquad
- beta S'le s'le S',qquad abs{omega'}le2.002s',
+ abs{mathcal S_calS_{f'}(s',omega')}ge e^{-7.98E},
+ beta S'le s'le S', abs{omega'}le2.002s',
and
@@ -434,7 +434,7 @@ list ((z_1,...,z_{k-1})) or its complex conjugate, and at most
nonempty product using at most one entry from each list and at most one
added parameter; and every added parameter (e^{-a+iitheta}) obeys
- agebeta S',qquad abs{theta}le C_1S.
+ agebeta S', abs{theta}le C_1S.
@@ -447,75 +447,75 @@ parameters, built later.
Throughout the proof of Proposition~prop:multiscale set
- sigma=(Ksqrt E)/(S'),qquad
- W(l)=exp(-(l^2)/(2sigma^2)),qquad b=beta S',
+ sigma=(Ksqrt E)/(S'),
+ W(l)=exp(-(l^2)/(2sigma^2)), 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$
+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
(eq:multiscale-cost). For any fixed product of powers of
-$H_f,1+sigma,1/S',1/b$, together with a factor $exp(O(klog(2k)))$,
+H_f,1+sigma,1/S',1/b, together with a factor exp(O(klog(2k))),
the logarithm is at most
[
C(1+klog(2k)+log H_f+logfrac1{S'})+Clog 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.
+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$,
+For real t define the polynomial and its value at x,
- A(t)=sum_{j=1}^n f_j,W(j-d),e^{ii t(j-d)},qquad
+ A(t)=sum_{j=1}^n f_j,W(j-d),e^{ii t(j-d)},
B_x(t)=A(t)(x).
-The coefficient bound on $f_j$ and the Gaussian sum give
+The coefficient bound on f_j and the Gaussian sum give
- abs{B_x(t)},quad abs{EE[A(t)]},quad abs{Delta[A(t)]}
+ abs{B_x(t)}, abs{EE[A(t)]}, abs{Delta[A(t)]}
le U:=C H_f(1+sigma),
-with $C$ absolute and $Uge1$. By prefix cancellation,
+with C absolute and Uge1. By prefix cancellation,
[
P(z):=sum_{j=d}^n Delta[f_j],W(j-d),z^{j-d}
quadsatisfiesquad P(e^{ii t})=Delta[A(t)].
]
-First, $P$ is shown to keep a signal at almost the original decay:
+First, P is shown to keep a signal at almost the original decay:
abs{P(e^{-s_1+iiomega})}getfrac12 e^{-E}
quadfor somequad abs{s_1/s-1}le10^{-4}.
-Let $V$ be a centred real normal variable with variance $sigma^{-2}$.
-Since $W(l),mathbf EbfE,e^{Vl}=1$,
+Let V be a centred real normal variable with variance sigma^{-2}.
+Since W(l),mathbf EbfE,e^{Vl}=1,
[
mathcal S_f(s,calS_f(s,omega)=mathbf EbfE,P(e^{-s+V+iiomega}).
]
-Write $delta=10^{-4}$. Exponential tilting gives
+Write delta=10^{-4}. Exponential tilting gives
[
W(l),mathbf E[e^bfE[e^{Vl}mathbf 1_bf1_{{abs V>delta s}}]
=Pr!(abs{N(l/sigma^2,sigma^{-2})}>delta s).
]
-For $0le lledelta ssigma^2/2$ this probability is at most
-$2e^{-cdelta^2s^2sigma^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
+For 0le lledelta ssigma^2/2 this probability is at most
+2e^{-cdelta^2s^2sigma^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
2H_f(1+1/s)(2e^{-cdelta^2s^2sigma^2}+e^{-delta s^2sigma^2/2}).
-Here $1/sle1/(beta S')$ and
-$s^2sigma^2gebeta^2K^2E/eta_0^2$. Choose $eta_0$ small and then
-$C_0$ large to make (eq:window-tail) less than $e^{-2E}$. Then the
-integral over $abs Vledelta s$ has magnitude at least
-$e^{-E}-e^{-2E}ge e^{-E}/2$, so its integrand attains magnitude at
+Here 1/sle1/(beta S') and
+s^2sigma^2gebeta^2K^2E/eta_0^2. Choose eta_0 small and then
+C_0 large to make (eq:window-tail) less than e^{-2E}. Then the
+integral over abs Vledelta s has magnitude at least
+e^{-E}-e^{-2E}ge e^{-E}/2, so its integrand attains magnitude at
least that large. This proves (eq:window-interior-signal).
Set
[
Λ(t)=logfrac{U}{abs{P(e^{ii t})}}ge0,
]
-with value $+∞$ at a boundary zero. The key estimate is
+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.
@@ -523,15 +523,15 @@ For completeness, the Cauchy Fourier transform is
int_{RR}frac{e^{iixi v}}{pi(1+v^2)},dv=e^{-absxi}.
-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
+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 (eq:poisson-log-bound) gives the circle
-Poisson measure at $e^{-s_1+iiomega}$.
+Poisson measure at e^{-s_1+iiomega}.
-To apply it, factor the nonzero polynomial $P$ into linear factors. A
+To apply it, factor the nonzero polynomial P into linear factors. A
factor with a root outside the unit disk has harmonic logarithmic
-magnitude inside. For a root $a$ inside the disk, the identity
-$abs{e^{ii t}-a}=abs{1-overlineoverline aa e^{ii t}}$ and the inequality
+magnitude inside. For a root a inside the disk, the identity
+abs{e^{ii t}-a}=abs{1-overlineoverline aa e^{ii t}} and the inequality
[
abs{1-overlineoverline aa z}^2-abs{z-a}^2=(1-abs a^2)(1-abs z^2)ge0
]
@@ -543,60 +543,60 @@ Summing over factors gives
lelog U-logabs{P(e^{-s_1+iiomega})}
le E+log(2U).
]
-The last term is at most $1.001E$ by the choice of $C_0$, proving the
+The last term is at most 1.001E by the choice of C_0, proving the
claim.
-The goal is a frequency $lambdain[-2s_1,2s_1]$ with a large signal, and,
+The goal is a frequency lambdain[-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)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
-differing by at most $b$. Each neighbouring inner product then has signed
-frequency of magnitude at most $b$, even though $abslambda$ may be
+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
+differing by at most b. Each neighbouring inner product then has signed
+frequency of magnitude at most b, even though abslambda may be
much larger. The logarithmic estimate turns the existence of enough
pairs into a question about pairing Cauchy mass.
[Cauchy matching]
-Let $w(v)=1/(pi(1+v^2))$. For every $rge0$ 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
+Let w(v)=1/(pi(1+v^2)). For every rge0 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
2mu_r(RR^2)=1-frac4piarctan(e^{-pi/r});
-for $r=0$ its total mass is $1/2$. In particular
-(eq:cauchy-matching-mass) exceeds $0.737$ for $0<rle2$.
+for r=0 its total mass is 1/2. In particular
+(eq:cauchy-matching-mass) exceeds 0.737 for 0<rle2.
Proof.
-For $r=0$ put half of $w(v),dv$ on the diagonal. Suppose $r>0$ and
-partition the line into chains $v+jr$, $jinmathbb Z$,bbZ$, with
-$-r/2le v<r/2$. Write $w_j=w(v+jr)$. On the edge from $j$ to $j-1$, for
-$jge1$, put weight
+For r=0 put half of w(v),dv on the diagonal. Suppose r>0 and
+partition the line into chains v+jr, jinmathbb Z,bbZ, with
+-r/2le v<r/2. Write w_j=w(v+jr). On the edge from j to j-1, for
+jge1, put weight
[
e_j=sum_{mge0}(-1)^m w_{j+m}.
]
These weights are nonnegative because the summands decrease along the
-tail, and $e_j+e_{j+1}=w_j$, so the edges exhaust the weight at every
+tail, and e_j+e_{j+1}=w_j, so the edges exhaust the weight at every
positive vertex. Build the negative-side edges the same way, from the
negative tail toward zero. The only possibly unused weight sits at the
central vertex, with value
[
R(v)=sum_{jinmathbb Z}bbZ(-1)^j w(v+jr).
]
-To check no weight is overused, periodize $w$ at period $2r$ and
-subtract its translate by $r$. By (eq:cauchy-transform), with
-$tau=e^{-pi/r}$, this gives the absolutely convergent Fourier series
+To check no weight is overused, periodize w at period 2r and
+subtract its translate by r. By (eq:cauchy-transform), with
+tau=e^{-pi/r}, this gives the absolutely convergent Fourier series
[
R(v)=frac2rsum_{mge0}tau^{2m+1}cos((2m+1)pi v)/(r).
]
-Writing $a=pi v/r$, the sum equals
+Writing a=pi v/r, the sum equals
[
refrac{tau e^{ii a}}{1-tau^2e^{2ii a}}
=(tau(1-tau^2)cos a)/(1-2tau^2cos(2a)+tau^4)ge0,
]
-since $abs alepi/2$. Orient each edge with its larger endpoint first
-and integrate the edge weights against $dv$ over $[-r/2,r/2)$. The
+since abs alepi/2. Orient each edge with its larger endpoint first
+and integrate the edge weights against dv over [-r/2,r/2). The
resulting measure has the claimed marginal domination. Its uncovered
mass is
[
@@ -605,52 +605,52 @@ mass is
=frac4piarctantau,
]
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 ule u-u^3/3+u^5/5$ for
-$0le ule1$ gives this numeric bound.
+r and at r=2 exceeds 0.737; for instance
+e^{-pi/2}<0.209 together with arctan ule u-u^3/3+u^5/5 for
+0le ule1 gives this numeric bound.
[Frequencies from the logarithmic bound]
-Let $s_1,E>0$, let $absomegale2.003s_1$, and let
-$Λ:RRto[0,∞]$ be measurable satisfying
-(eq:poisson-log-bound). There is a real $lambda$ with
+Let s_1,E>0, let absomegale2.003s_1, and let
+Λ:RRto[0,∞] be measurable satisfying
+(eq:poisson-log-bound). There is a real lambda with
- abslambdale2s_1,qquad Λ(lambda)le2.40E.
+ abslambdale2s_1, Λ(lambda)le2.40E.
-There is also an absolute $C_2$ such that, for every $abs yle2s_1$,
-some real $t,t'$ satisfy
+There is also an absolute C_2 such that, for every abs yle2s_1,
+some real t,t' satisfy
- t-t'=y,qquad abs t,abs{t'}le C_2s_1,qquad
+ t-t'=y, abs t,abs{t'}le C_2s_1,
Λ(t)+Λ(t')le2.74E.
Proof.
-The Cauchy mass of $[-2s_1,2s_1]$ is at least
+The Cauchy mass of [-2s_1,2s_1] is at least
[
frac{arctan(2-2.003)+arctan(2+2.003)}pi>0.418.
]
-Because $1.001/0.418<2.40$, averaging proves (eq:single-frequency).
+Because 1.001/0.418<2.40, averaging proves (eq:single-frequency).
For (eq:paired-frequencies), apply Lemma~lem:cauchy-matching
-with $r=abs y/s_1le2$ and substitute $t=omega+s_1v$, reversing the
+with r=abs y/s_1le2 and substitute t=omega+s_1v, reversing the
orientation if needed. The two marginals sum to at most the Cauchy
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
+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_2to∞$ since $absomega/s_1le2.003$. Choose absolute $C_2$ so
-the retained mass exceeds $0.733/2$. Its integral of
-$Λ(t)+Λ(t')$ is at most $1.001E$, so some retained pair has
+C_2to∞ since absomega/s_1le2.003. Choose absolute C_2 so
+the retained mass exceeds 0.733/2. Its integral of
+Λ(t)+Λ(t') is at most 1.001E, so some retained pair has
sum at most
[
(2(1.001))/(0.733)E<2.74E,
]
-as required. The diagonal construction gives the same when $y=0$.
+as required. The diagonal construction gives the same when y=0.
-The window parameters satisfy $absomega/s_1le2.002/0.9999<2.003$, so
-Lemma~lem:good-frequencies applies to this $Λ$. Individual
+The window parameters satisfy absomega/s_1le2.002/0.9999<2.003, so
+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
@@ -658,37 +658,37 @@ frequency. The following Hilbert-space fact explains why such a chain
keeps the needed exponential accuracy.
[Gram chaining]
-Let $v_0,...,v_J$, $Jge1$, lie in a complex Hilbert space whose inner
-product is linear in its first argument. Suppose $norm{v_0}=1$ and, for
-some $xige0$,
+Let v_0,...,v_J, Jge1, lie in a complex Hilbert space whose inner
+product is linear in its first argument. Suppose norm{v_0}=1 and, for
+some xige0,
[
- abs{norm{v_i}^2-1}lexi (0le ile J),qquad
+ abs{norm{v_i}^2-1}lexi (0le ile J),
abs{< v_i,v_{i-1}>-1}lexi (1le ile J).
]
-Then $abs{< v_J,v_0>-1}le2J^2xi$.
+Then abs{< v_J,v_0>-1}le2J^2xi.
Proof.
-Put $h_i=v_i-v_{i-1}$. The hypotheses give
+Put h_i=v_i-v_{i-1}. The hypotheses give
[
- norm{h_i}le2sqrtxi,qquad
- abs{< h_i,v_{i-1}>}le2xi,qquad
+ norm{h_i}le2sqrtxi,
+ abs{< h_i,v_{i-1}>}le2xi,
norm{v_{i-1}-v_0}le2(i-1)sqrtxi.
]
So Cauchy--Schwarz gives
-$abs{< h_i,v_0>}le2xi+4(i-1)xi$. Sum over $i$ and use
-$< v_0,v_0>=1$.
+abs{< h_i,v_0>}le2xi+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~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 tle C_3S$, is called balanced if the sum of its signed
-frequencies has magnitude at most $b$; conjugation flips the sign of a
+Choose an absolute C_3 large enough that all frequencies supplied by
+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 tle C_3S, is called balanced if the sum of its signed
+frequencies has magnitude at most b; conjugation flips the sign of a
frequency.
[A balanced product keeps a signal]
-Some balanced product $G$ satisfies
+Some balanced product G satisfies
abs{Delta[G]}ge e^{-7.94E}.
@@ -696,8 +696,8 @@ Some balanced product $G$ satisfies
Proof.
Suppose not: every balanced product has signal below
-$ε=e^{-7.94E}$. The squared modulus $abs{A(t)}^2$ is one such
-product. Positivity of $EE$ on $A(t)$ and $1$ gives
+ε=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)]}^2leEE[abs{A(t)}^2]leabs{B_x(t)}^2+ε,
]
@@ -705,15 +705,15 @@ hence
abs{Delta[A(t)]}le2abs{B_x(t)}+sqrtε.
-At $lambda$ from (eq:single-frequency) this implies
+At lambda from (eq:single-frequency) this implies
abs{B_x(lambda)}ge e^{-2.41E}.
-Indeed $abs{Delta[A(lambda)]}ge e^{-2.40E}$ whereas
-$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
+Indeed abs{Delta[A(lambda)]}ge e^{-2.40E} whereas
+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^{-Λ(t)-Λ(t')}
ge e^{-2.74E}.
@@ -722,50 +722,50 @@ 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}$.
+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,...,y_J=lambda$ with consecutive
-distances at most $b$ and
+Take a monotone chain 0=y_0,y_1,...,y_J=lambda with consecutive
+distances at most b and
[
1le Jle C(1+S/b).
]
-If $lambda=0$, use two endpoints and $J=1$. For each interior $y_i$
+If lambda=0, use two endpoints and J=1. For each interior y_i
choose a pair from (eq:paired-frequencies) and set
[
- V_0=1,qquad
+ V_0=1,
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)).
+ V_J=(A(lambda))/(B_x(lambda)).
]
The denominators are nonzero by
(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 $2kle D$.
+every V_i(x)=1. View these polynomials as vectors v_i in the Hilbert
+space of EE; they have degree at most 2kle D.
-For $1le ile J$ the norm square of $v_i$ and its inner product with
-$v_{i-1}$ are expectations of normalized balanced products, whose signed
-frequencies are respectively zero and $y_i-y_{i-1}$; each product has at
+For 1le ile J the norm square of v_i and its inner product with
+v_{i-1} are expectations of normalized balanced products, whose signed
+frequencies are respectively zero and y_i-y_{i-1}; each product has at
most four factors and its normalizing denominator has magnitude at least
-$e^{-5.50E}$. The contradictory assumption therefore gives
+e^{-5.50E}. The contradictory assumption therefore gives
[
- abs{norm{v_i}^2-1}lexi,qquad
- abs{< v_i,v_{i-1}>-1}lexi,qquad
+ abs{norm{v_i}^2-1}lexi,
+ abs{< v_i,v_{i-1}>-1}lexi,
xi=ε e^{5.50E}=e^{-2.44E}.
]
-Since $v_0=1$ has norm one, Lemma~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{< 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 (eq:multiscale-cost). This contradicts
+The last strict inequality holds after enlarging C_0, because
+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'$;
+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~lem:balanced-product gives a product of at most four
@@ -776,62 +776,62 @@ Proposition~prop:multiscale requires; what remains is to bound
the damping on the inner gaps.
Fix a product from Lemma~lem:balanced-product and let
-$1le mle4$ be its number of factors. Expand each factor into the
-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(klog(2k)))$ interleavings: assign each labeled
+1le mle4 be its number of factors. Expand each factor into the
+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(klog(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_1le...le j_m$. Ties between endpoints may
+relabel its copies so j_1le...le j_m. Ties between endpoints may
be ordered arbitrarily. Absorbing conjugation into the signs of the
frequencies, the window weight is
prod_{r=1}^m W(j_r-d)exp(ii t_r(j_r-d)),
- qquad |t_r|le C_3S,qquad
+ |t_r|le C_3S,
|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=Ksqrt E/S'$ and $b=beta S'$. For every real $l$,
+Recall sigma=Ksqrt E/S' and b=beta S'. For every real l,
W(l)=frac{sigma}{ii√(2pi)}
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.
+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,...,u_m)inRR^m$ define
+Set rho=1/2.002. For u=(u_1,...,u_m)inRR^m define
- Ω=sum_{r=1}^m(u_r+t_r),qquad
- v_r=b+ii u_r (r<m),qquad
+ Ω=sum_{r=1}^m(u_r+t_r),
+ v_r=b+ii u_r (r<m),
v_m=-mb-rho|Ω|+ii u_m.
-These real parts have partial sums $rb$ for $r<m$ and total
-$-b-rho|Ω|$. Centred at $j_m$, the total sum gives the real part
+These real parts have partial sums rb for r<m and total
+-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|Ω|$ 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 (eq:gaussian-contour) to the vertical lines $re v_r=b$,
+For each fixed tuple of positions, first shift the first m-1 contours
+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,...,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
-(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$,
+height pm T, the Gaussian exponent has real part at most -cT^2+O(T)
+for some c>0, while exp(v_m(j_m-d)) adds only a linear term in T,
so those linking integrals also vanish. The integrands are entire, so no
residues occur. This proves the identities as iterated integrals; joint
absolute convergence follows from the bound below.
-Let $nu$ be the resulting complex measure on $RR^m$ after removing the
-position-dependent factors. Outside the measure-zero set $Ω=0$,
+Let nu be the resulting complex measure on RR^m after removing the
+position-dependent factors. Outside the measure-zero set Ω=0,
dnu(u)=
(frac{sigma}{√(2pi)})^m
@@ -839,11 +839,11 @@ position-dependent factors. Outside the measure-zero set $Ω=0$,
(1+iirhosgnΩ),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
+ii,du_m. This quantity is bounded uniformly over the frequencies in
(eq:endpoint-window); the bounds also give absolute convergence.
-Put $delta_0=1-4rho^2>0$ and $c_1=delta_0/2$. Since $mle4$ and
-$|sum t_r|le b$, Young's inequality gives an absolute $C_4$ with
+Put delta_0=1-4rho^2>0 and c_1=delta_0/2. Since mle4 and
+|sum t_r|le b, Young's inequality gives an absolute C_4 with
sum_{r=1}^m(re v_r)^2
&=(m-1)b^2+(mb+rho|Ω|)^2 notag
@@ -852,10 +852,10 @@ $|sum t_r|le b$, Young's inequality gives an absolute $C_4$ with
&le (1-c_1)sum_r u_r^2+C_4b^2.
-The strict inequality $4rho^2<1$ is essential: summing at most four
+The strict inequality 4rho^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+8rho^2/delta_0)$ works. With
+sector constant 2.002 leaves a positive Gaussian margin. For example
+C_4=3+(4+rho)^2(1+8rho^2/delta_0) works. With
(eq:contour-measure) this gives
[
|dnu(u)|le Csigma^m
@@ -863,14 +863,14 @@ $C_4=3+(4+rho)^2(1+8rho^2/delta_0)$ works. With
-(c_1sigma^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
+exp(C_n(1+sum_r|u_r|)) for a finite C_n, which is integrable
against the Gaussian bound. So the iterated deformation is a jointly
absolutely convergent integral, and finite tuple sums may be exchanged
with it.
-Write $mathcal U=calU={u:max_r|u_r|le S'/16}$. Integrating the last bound
+Write mathcal U=calU={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$calU^c$ gives absolute constants $C,C'$ with
+mathcal U^ccalU^c gives absolute constants C,C' with
|nu|_{abs}
&le Cexp(C_4K^2beta^2E/2),
@@ -878,45 +878,45 @@ $mathcal U^c$calU^c$ gives absolute constants $C,C'$ with
&le C'expBigl[((C_4K^2beta^2)/(2)
-(c_1K^2)/(1024))EBigr].
-Here $|nu|_{abs}$ is total variation; the powers $sigma^m$
-cancel under Gaussian rescaling. Choose $K$ with $c_1K^2/1024ge30$,
-then $betale1/4$ with $C_4K^2beta^2/2le0.001$. Enlarging $C_0$ to
+Here |nu|_{abs} is total variation; the powers sigma^m
+cancel under Gaussian rescaling. Choose K with c_1K^2/1024ge30,
+then betale1/4 with C_4K^2beta^2/2le0.001. Enlarging C_0 to
absorb fixed prefactors gives
- |nu|_{abs}le e^{0.005E},qquad
+ |nu|_{abs}le e^{0.005E},
int_{mathcal U^c}calU^c|dnu|le e^{-20E}.
-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.
+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
+For c_r=v_r+ii t_r, telescoping the endpoint differences gives
sum_{r=1}^m c_r(j_r-d)
=(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
+So the largest endpoint has coefficient -s'+iiΩ with
s'=b+rho|Ω|.
-The link from $j_r$ to $j_{r+1}$ receives the parameter
+The link from j_r to j_{r+1} receives the parameter
- exp(-rb-iisum_{l=1}^r(u_l+t_l)),qquad 1le r<m.
+ exp(-rb-iisum_{l=1}^r(u_l+t_l)), 1le r<m.
-Thus every added damping is at least $b$, uniformly in $u$. On
-$mathcal U$,calU$,
+Thus every added damping is at least b, uniformly in u. On
+mathcal U,calU,
[
- |Ω|le(beta+1/4)S',qquad
+ |Ω|le(beta+1/4)S',
beta S'le s'le[beta+rho(beta+1/4)]S'le S',
- qquad |Ω|le2.002s'.
+ |Ω|le2.002s'.
]
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
+3(C_3S+S'/16)le C_1S for a fixed absolute C_1. Hence the outer
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$.
+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
must have exactly the form of a feature with controlled coefficient sum.
@@ -925,14 +925,14 @@ 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<...<i_v$ with $1le vle mk$. Form a multigraph on these
+i_1<...<i_v with 1le vle mk. Form a multigraph on these
vertices: include the inner edges of each old tuple and the links
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.
-For each merged gap $i_{a+1}-i_a$, multiply the parameters of all edges
+For each merged gap i_{a+1}-i_a, multiply the parameters of all edges
crossing it. Each edge length is the sum of the merged gaps it crosses,
so the new parameters reproduce the original weight exactly. Every
merged gap is crossed by some edge, by connectivity, so its damping is
@@ -942,31 +942,31 @@ 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~prop:multiscale.
-Ties merge repeated bit variables by $X_i^r=X_i$ for $rge1$. Once the
+Ties merge repeated bit variables by X_i^r=X_i for rge1. Once the
interleaving is fixed, choosing arbitrary strictly increasing values for
-its $v$ distinct positions specifies exactly one assignment to its
+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}calI,u$ with outer weight
-$exp((-s'+iiΩ)(i_v-d))$.
+largest position is i_v=j_m. Summing all these assignments gives an
+order-v feature f^{mathcal I,u}calI,u with outer weight
+exp((-s'+iiΩ)(i_v-d)).
The needed combinatorial fact controls its height.
[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
+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.
Proof.
-For $v=1$ there is nothing to prove. Otherwise keep a spanning tree and
-orient each edge from its smaller to its larger endpoint. Let $M$ be the
-$(v-1)times(v-1)$ matrix whose $(e,a)$ entry is one if tree edge $e$
-crosses gap $a$ and zero otherwise. It is invertible: for $g$ in its
-kernel set $y_1=0$ and $y_{a+1}=y_a+g_a$; then $Mg=0$ says $y$ is equal
+For v=1 there is nothing to prove. Otherwise keep a spanning tree and
+orient each edge from its smaller to its larger endpoint. Let M be the
+(v-1)times(v-1) matrix whose (e,a) entry is one if tree edge e
+crosses gap a and zero otherwise. It is invertible: for g in its
+kernel set y_1=0 and y_{a+1}=y_a+g_a; then Mg=0 says y is equal
at the endpoints of every tree edge, and connectivity forces all values
-zero, so $g=0$. A nonzero term in the determinant expansion of $M$ pairs
+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.
@@ -974,11 +974,11 @@ required 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
-link-edge, with gaps $g_a=(i_a,i_{a+1})$ for $1le ale5$. The assignment
-$g_amapsto e_a$, $1le ale5$, 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$.
+(i_1,i_3,i_5) and (i_2,i_4,i_6) joined by one dashed endpoint
+link-edge, with gaps g_a=(i_a,i_{a+1}) for 1le ale5. The assignment
+g_amapsto e_a, 1le ale5, 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.
[htbp]
centering
@@ -989,29 +989,29 @@ centering
draw[gray] (0,0)--(5,0);
foreach a in {1,...,6} {
fill (a-1,0) circle (1.8pt);
- node[below=3pt] at (a-1,0) {$i_{a}$};
+ node[below=3pt] at (a-1,0) {i_{a}};
}
- draw[olda] (0,0) to[bend left=30] node[above,pos=.5] {$e_1$} (2,0);
- draw[olda] (2,0) to[bend left=30] node[above,pos=.5] {$e_3$} (4,0);
- draw[oldb] (1,0) to[bend left=65] node[above,pos=.5] {$e_2$} (3,0);
- draw[oldb] (3,0) to[bend left=65] node[above,pos=.5] {$e_4$} (5,0);
- draw[added] (4,0) to[bend right=60] node[below=2pt,pos=.5] {$e_5$} (5,0);
+ draw[olda] (0,0) to[bend left=30] node[above,pos=.5] {e_1} (2,0);
+ draw[olda] (2,0) to[bend left=30] node[above,pos=.5] {e_3} (4,0);
+ draw[oldb] (1,0) to[bend left=65] node[above,pos=.5] {e_2} (3,0);
+ draw[oldb] (3,0) to[bend left=65] node[above,pos=.5] {e_4} (5,0);
+ draw[added] (4,0) to[bend right=60] node[below=2pt,pos=.5] {e_5} (5,0);
foreach a in {1,...,5} {
- node at (a-.5,-1.05) {$g_{a}$};
+ node at (a-.5,-1.05) {g_{a}};
}
-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_amapsto e_a$ for
-$1le ale5$ 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$.}
+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_amapsto e_a for
+1le ale5 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.}
-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$,
+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~lem:edge-gap-assignment gives
H_{f^{mathcal I,u}calI,u}
@@ -1021,13 +1021,13 @@ Lemma~lem:edge-gap-assignment gives
The second inequality uses that all factors are at least one; the
-endpoint-link dampings are $rbge b$. This covers all overlaps between
+endpoint-link dampings are rbge b. This covers all overlaps between
old tuples and also the single-distinct-position case, where the height
is the empty product one.
{itshape Completing the multiscale estimate.}
-Apply $Delta$ to the expanded product and use the integral
-representation for each interleaving. With $nu_{mathcal I}calI$ the
+Apply Delta to the expanded product and use the integral
+representation for each interleaving. With nu_{mathcal I}calI the
corresponding measure,
Delta[product]
@@ -1035,10 +1035,10 @@ corresponding measure,
mathcal S_calS_{f^{mathcal I,u}calI,u}(s',Ω),dnu_{mathcal I}calI(u).
All estimates are uniform over interleavings, and the integrands are
-uniformly bounded even outside $mathcal U$.calU$. Indeed, for each fixed
-endpoint $j$ the coefficients of $f_j^{mathcal I,u}calI,u$ have absolute sum at
-most the height in (eq:interleaving-height), terms with $j<d$
-vanish under $Delta$ by prefix agreement, and $s'ge b$ gives
+uniformly bounded even outside mathcal U.calU. Indeed, for each fixed
+endpoint j the coefficients of f_j^{mathcal I,u}calI,u have absolute sum at
+most the height in (eq:interleaving-height), terms with j<d
+vanish under Delta by prefix agreement, and s'ge b gives
|mathcal S_calS_{f^{mathcal I,u}calI,u}(s',Ω)|
le 2H_f^4(1+1/b)^3sum_{lge0}e^{-bl}
@@ -1046,16 +1046,16 @@ vanish under $Delta$ by prefix agreement, and $s'ge b$ gives
No exponential factor from negative distances appears.
-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
+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
[
- Ege100,qquad log N_{int}le0.01E,qquad log Vle0.01E.
+ Ege100, log N_{int}le0.01E, log Vle0.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 (eq:product-feature-integral) with $uinmathcal U$calU$ had
-magnitude below $e^{-7.98E}$, then (eq:contour-mass) and
+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 (eq:product-feature-integral) with uinmathcal UcalU had
+magnitude below e^{-7.98E}, then (eq:contour-mass) and
(eq:contour-uniform-signal) would give
[
|Delta[product]|
@@ -1063,9 +1063,9 @@ magnitude below $e^{-7.98E}$, then (eq:contour-mass) and
le e^{-7.965E}+e^{-19.98E}<e^{-7.94E}.
]
This contradicts Lemma~lem:balanced-product. Some interleaving and
-some $uinmathcal U$calU$ therefore give a feature with signal at least
-$e^{-7.98E}$. Its order is at most $mkle4k$; (eq:new-outer-decay)
-and the bounds on $mathcal U$calU$ give the outer parameters;
+some uinmathcal UcalU therefore give a feature with signal at least
+e^{-7.98E}. Its order is at most mkle4k; (eq:new-outer-decay)
+and the bounds on mathcal UcalU give the outer parameters;
(eq:interleaving-height) gives (eq:multiscale-height); and
the crossing description gives the parameter factors and
(eq:added-parameters). This completes the proof of
@@ -1073,61 +1073,61 @@ Proposition~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
+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
+Throughout, 0<p<1 and q_*,Q,Y are as in
(eq:aux-parameters). Recall from (eq:aux-comparisons) that
- 1lemathsf X(n,p)sfX(n,p)le Yle2mathsf X(n,p),sfX(n,p),qquad
+ 1lemathsf X(n,p)sfX(n,p)le Yle2mathsf X(n,p),sfX(n,p),
QY=Q+log nle Clog n.
Set
- mu=7.98,qquad alpha=0.001,qquad
- h=lceillog_2Yrceil+H,qquad D_*=4^h,
+ mu=7.98, alpha=0.001,
+ h=lceillog_2Yrceil+H, D_*=4^h,
-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
-$Dge D_*$ and first wrong position $d$, and let $Delta$ be its
+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
+Dge D_* and first wrong position d, and let Delta be its
difference from the true word, as set out earlier. Every
-constant chosen below is independent of this system, of $n$, and of $p$.
+constant chosen below is independent of this system, of n, and of p.
-For an absolute constant $eta>0$ define
+For an absolute constant eta>0 define
- S_0=4,qquad
+ S_0=4,
S_j=eta,q_*,Y^{-alpha},S_{j-1},
- min{1,D_*S_{j-1}}quad(1le jle h).
+ min{1,D_*S_{j-1}}(1le jle h).
-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 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 $θ=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
+Choose an integer J_* with alpha J_*ge3 and set H=J_*+3. To check
+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θ^{J_*}t_0
le4^{H+2}eta^{J_*}Y^{2-alpha J_*}le1
]
-once $eta$ is small enough. Require also
-$etalemin{eta_0,1/4,e^{-1}}$, with $eta_0$ from
-Proposition~prop:multiscale. Now $log(1/θ)ge Q$ and
-$t_jle1$ for $jge J_*$. Iterating $t_j=θ t_{j-1}^2$ in that
+once eta is small enough. Require also
+etalemin{eta_0,1/4,e^{-1}}, with eta_0 from
+Proposition~prop:multiscale. Now log(1/θ)ge Q and
+t_jle1 for jge J_*. Iterating t_j=θ t_{j-1}^2 in that
range gives
t_hleθ^{,2^{h-J_*}-1}
- leexp{-Q(2^{h-J_*}-1)}le n^{-1},qquad S_hle n^{-1}.
+ leexp{-Q(2^{h-J_*}-1)}le n^{-1}, S_hle n^{-1}.
-The last inequality uses $2^{h-J_*}ge8Y$ and $Q(Y-1)=log n$. At each
-transition $0<S_jlemin{1,eta_0S_{j-1}}$, as the proposition requires.
+The last inequality uses 2^{h-J_*}ge8Y and Q(Y-1)=log n. At each
+transition 0<S_jlemin{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
+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_jle2ell_{j-1}+log(1/θ),quadell_0=0,quad
+ ell_jle2ell_{j-1}+log(1/θ),quadell_0=0,
log(1/θ)le CA_0,
]
hence
@@ -1136,9 +1136,9 @@ hence
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$,
+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,
abs{mathcal S_calS_{f^{(0)}}(4,0)}
ge1-2sum_{rge1}e^{-4r}
@@ -1148,21 +1148,21 @@ Use error exponents
E_j=C_5A_0mu^jqquad(0le jle h),
-with absolute $C_5$ chosen after $H$ and $eta$.
+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_jle4^j$ with
+The induction maintains this statement. At stage j there is a feature
+f^{(j)} of order k_jle4^j with
- beta S_jle s_jle S_j,quad
- abs{omega_j}le2.002s_j,quad
+ beta S_jle s_jle S_j,
+ abs{omega_j}le2.002s_j,
abs{mathcal S_calS_{f^{(j)}}(s_j,omega_j)}ge e^{-E_j},
log H_{f^{(j)}}le C4^jA_0.
-The base case follows from (eq:initial-signal) and $H_{f^{(0)}}=1$
-on increasing $C_5$. At the transition $j-1to j$ the degree requirement
-is $4k_{j-1}le4^jle D_*le D$. The proposition's height conclusion and
+The base case follows from (eq:initial-signal) and H_{f^{(0)}}=1
+on increasing C_5. At the transition j-1to j the degree requirement
+is 4k_{j-1}le4^jle D_*le D. The proposition's height conclusion and
(eq:scale-cost) give
[
log H_{f^{(j)}}le4log H_{f^{(j-1)}}+3log(1+1/(beta S_j))
@@ -1173,112 +1173,112 @@ For the exponent hypothesis, the proposition's bracket is at most
[
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
+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~prop:multiscale hold, and its signal bound is
-$e^{-mu E_{j-1}}=e^{-E_j}$.
+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
-of magnitude at least $e^{-E_h}$ with $kle D_*$ and $sle1/n$. The next
+Write f=f^{(h)}, k=k_h, s=s_h, omega=omega_h. There is a signal
+of magnitude at least e^{-E_h} with kle D_* and sle1/n. The next
step records where its parameters sit inside the unit disk; this controls
the cost of continuing the signal to the trace domain.
Call the parameters introduced between endpoints in any application of
Proposition~prop:multiscale elementary parameters, and
-include the final outer parameter $z_0=e^{-s+iiomega}$. An elementary
-parameter $e^{-a+iitheta}$ introduced at stage $j$ has $agebeta S_j$
-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
+include the final outer parameter z_0=e^{-s+iiomega}. An elementary
+parameter e^{-a+iitheta} introduced at stage j has agebeta S_j
+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
- agegammamin{abs{theta},D_*theta^2},qquad
+ agegammamin{abs{theta},D_*theta^2},
gamma=c_2q_*Y^{-alpha}le1.
-Indeed, the increasing map $umapsto umin{1,D_*u}$ changes by at most
-a factor $max{C_1,C_1^2}$ when $u$ becomes $C_1u$, so
-$c_2lebetaeta/max{C_1,C_1^2}$ suffices; shrinking $c_2$ further
-covers $z_0$ since $absomegale2.002s$. Conjugating an elementary
+Indeed, the increasing map umapsto umin{1,D_*u} changes by at most
+a factor max{C_1,C_1^2} when u becomes C_1u, so
+c_2lebetaeta/max{C_1,C_1^2} suffices; shrinking c_2 further
+covers z_0 since absomegale2.002s. Conjugating an elementary
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;
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
+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_jle4N_{j-1}+1,qquad N_jle(4^j-1)/(3).
+ N_0=0, N_jle4N_{j-1}+1, N_jle(4^j-1)/(3).
]
-In particular an inner gap of $f$, even after multiplying by $z_0$,
-contains at most $(4^h+2)/3le D_*$ elementary factors.
+In particular an inner gap of f, even after multiplying by z_0,
+contains at most (4^h+2)/3le D_* elementary factors.
The next lemma explains why this count matters. The Cayley map
-$zmapsto(1+z)/(1-z)$ sends the unit disk to the right half-plane, and a
+zmapsto(1+z)/(1-z) sends the unit disk to the right half-plane, and a
quantitative distance from its boundary is needed.
[Products with controlled damping]
-Let $Nge1$ be an integer and $0<gammale1$. Suppose $z$ is a nonempty
-product of at most $N$ numbers $e^{-a_j+iitheta_j}$ with $a_j>0$,
-$theta_jinRR$, and $a_jgegammamin{abs{theta_j},Ntheta_j^2}$.
-Then for some absolute $c_3>0$,
+Let Nge1 be an integer and 0<gammale1. Suppose z is a nonempty
+product of at most N numbers e^{-a_j+iitheta_j} with a_j>0,
+theta_jinRR, and a_jgegammamin{abs{theta_j},Ntheta_j^2}.
+Then for some absolute c_3>0,
[
re(1+z)/(1-z)ge c_3gamma.
]
Proof.
-Write $z=e^{-T+iipsi}$ with $T=sum_j a_j>0$ and
-$psi=sum_jtheta_j$. Let
+Write z=e^{-T+iipsi} with T=sum_j a_j>0 and
+psi=sum_jtheta_j. Let
[
- U=sum_{abs{theta_j}ge1/N}abs{theta_j},qquad
+ U=sum_{abs{theta_j}ge1/N}abs{theta_j},
V=sum_{abs{theta_j}<1/N}abs{theta_j}.
]
-Summing the hypotheses and applying Cauchy--Schwarz to at most $N$ small
+Summing the hypotheses and applying Cauchy--Schwarz to at most N small
angles gives
[
Tgegamma(U+N!!sum_{abs{theta_j}<1/N}theta_j^2)
gegamma(U+V^2).
]
-If $Uge1$ or $Vge1$ the bracket is at least one; otherwise
-$U+V^2ge U^2+V^2ge(U+V)^2/2$. Since $abspsile U+V$, in all cases
+If Uge1 or Vge1 the bracket is at least one; otherwise
+U+V^2ge U^2+V^2ge(U+V)^2/2. Since abspsile U+V, in all cases
[
Tgetfrac12gammamin{1,psi^2}.
]
-For $0<Tle1$ this gives
+For 0<Tle1 this gives
[
- 1-abs z^2ge cT,qquad
+ 1-abs z^2ge cT,
abs{1-z}^2le 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 $gammale1$.
+Their ratio is re((1+z)/(1-z)). If T>1, that ratio is at least
+(1-e^{-2})/4, which also suffices because gammale1.
-Let $z_1,...,z_{k-1}$ be the inner gap parameters of the final feature
-$f$. Define the polynomial in $k$ complex variables
+Let z_1,...,z_{k-1} be the inner gap parameters of the final feature
+f. Define the polynomial in k complex variables
F(Z_0,...,Z_{k-1})
=sum_{1le i_1<...<i_kle n}
DeltaBigl[prod_{r=1}^kX_{i_r}Bigr]
Z_0^{i_1}prod_{r=1}^{k-1}Z_r^{i_{r+1}-i_r}.
-At the point $Z_0^*=z_0$, $Z_r^*=z_rz_0$ $(1le r<k)$, the powers of
-$z_0$ telescope to $i_k$, so
+At the point Z_0^*=z_0, Z_r^*=z_rz_0 (1le r<k), the powers of
+z_0 telescope to i_k, so
- F(Z^*)=z_0^d,mathcal S_f(s,calS_f(s,omega),qquad
+ F(Z^*)=z_0^d,mathcal S_f(s,calS_f(s,omega),
abs{F(Z^*)}ge e^{-E_h-1},
-where $sdle nS_hle1$. Each coordinate of $Z^*$ is a nonempty product of
-at most $D_*$ elementary parameters, so Lemma~lem:product-cayley
+where sdle nS_hle1. Each coordinate of Z^* is a nonempty product of
+at most D_* elementary parameters, so Lemma~lem:product-cayley
gives
re(1+Z_r^*)/(1-Z_r^*)ge c_3gammaqquad(0le r<k).
A bound on the coordinates' collective closeness to the unit circle is also needed. If
-$z_r=e^{-a_r+iitheta_r}$, then
+z_r=e^{-a_r+iitheta_r}, then
[
frac1{1-abs{Z_r^*}}le1+frac1{a_r+s}le1+frac1{a_r} (rge1),
- qquad frac1{1-abs{Z_0^*}}le1+frac1s,
+ frac1{1-abs{Z_0^*}}le1+frac1s,
]
-using $e^uge1+u$. The height bound in (eq:scale-induction) and
+using e^uge1+u. The height bound in (eq:scale-induction) and
(eq:scale-cost) therefore give
W_*:=logprod_{r=0}^{k-1}frac1{1-abs{Z_r^*}}
@@ -1290,39 +1290,39 @@ different domain. This is a multivariate trace generating identity from the smoo
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,...,ell_k)$ with $1leell_1<...<ell_kle n$ write
-$T_ell=T_{{ell_1,...,ell_k}}$. For $u=(u_0,...,u_{k-1})inCC^k$
+ell=(ell_1,...,ell_k) with 1leell_1<...<ell_kle n write
+T_ell=T_{{ell_1,...,ell_k}}. For u=(u_0,...,u_{k-1})inCC^k
set
[
G(u)=sum_{1leell_1<...<ell_kle 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
+Then, with Z_r=q+pu_r, the exact identity is
(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
-$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 (eq:input-polynomial)
+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
+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 (eq:input-polynomial)
with every displayed gap exponent reduced by one; multiplying by
-$prod_rZ_r$ proves (eq:trace-generating-identity), including points
-where some $Z_r=0$.
+prod_rZ_r proves (eq:trace-generating-identity), including points
+where some Z_r=0.
Suppose for the moment that
abs{Delta[T_I]}leε
quadfor every I⊆{1,...,n} with 1leabs Ile D_*.
-Since $kle D_*$ the rank sum has at most $n^k$ terms, so
-$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
+Since kle D_* the rank sum has at most n^k terms, so
+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 (0le r<k).
@@ -1332,35 +1332,35 @@ product is zero when the trace is too short.
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:
+coordinates the disk abs{Z-q}le p becomes a half-plane:
abs{Z-q}le p
iff re(1+Z)/(1-Z)gefrac qpqquad(abs Z<1).
-Indeed, writing $w=(1+Z)/(1-Z)$ and expanding
-$abs{pw-(1+q)}^2le p^2abs{w+1}^2$ reduces it to $4qle4pre w$. All
+Indeed, writing w=(1+Z)/(1-Z) and expanding
+abs{pw-(1+q)}^2le p^2abs{w+1}^2 reduces it to 4qle4pre w. All
coordinates are moved into this half-plane with one complex variable. A single
strip interpolation avoids paying a separate continuation loss per
coordinate.
Write
[
- w_r=(1+Z_r^*)/(1-Z_r^*)=xi_r+iizeta_r,qquad xi_rge c_3gamma,
+ w_r=(1+Z_r^*)/(1-Z_r^*)=xi_r+iizeta_r, xi_rge c_3gamma,
]
-with $xi_r,zeta_rinRR$. For $vinCC$ set
+with xi_r,zeta_rinRR. For vinCC set
- w_r(v)=(1+v)xi_r+iizeta_r,quad
- Z_r(v)=(w_r(v)-1)/(w_r(v)+1),quad
+ w_r(v)=(1+v)xi_r+iizeta_r,
+ Z_r(v)=(w_r(v)-1)/(w_r(v)+1),
R=1+(q)/(pc_3gamma).
-A common real value of $v$ moves every starting coordinate into the trace
-half-plane at once. Concretely, in the $Z$-plane the region
-$abs{Z-q}le p$ is a disk; after the Cayley map
-$w=(1+Z)/(1-Z)$ it becomes the half-plane $re wge 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_rge q/p$. All
-coordinates use the same parameter $0le vle R$; the proof interpolates
-$F(Z_0(v),...,Z_{k-1}(v))$ on one complex strip, simultaneously for
+A common real value of v moves every starting coordinate into the trace
+half-plane at once. Concretely, in the Z-plane the region
+abs{Z-q}le p is a disk; after the Cayley map
+w=(1+Z)/(1-Z) it becomes the half-plane re wge 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_rge q/p. All
+coordinates use the same parameter 0le vle R; the proof interpolates
+F(Z_0(v),...,Z_{k-1}(v)) on one complex strip, simultaneously for
every coordinate (Figure~fig:simultaneous-cayley).
suppressfloats[t]
@@ -1370,72 +1370,72 @@ centering
fill[blue!4] (0,0) circle (1);
fill[teal!17] (0.4,0) circle (0.6);
- draw[black!35,->] (-1.2,0)--(1.32,0) node[right] {$re Z$};
+ draw[black!35,->] (-1.2,0)--(1.32,0) node[right] {re Z};
draw[black!35,->] (0,-1.16)--(0,1.2);
draw[black!65] (0,0) circle (1);
draw[teal!65!black] (0.4,0) circle (0.6);
- fill (0.4,0) circle (0.022) node[below right] {$q$};
- node[below right] at (1,0) {$1$};
+ fill (0.4,0) circle (0.022) node[below right] {q};
+ node[below right] at (1,0) {1};
fill[blue!70!black] (-0.2027,0.5791) circle (0.027)
- node[above left] {$Z_0^*$};
+ node[above left] {Z_0^*};
fill[orange!80!black] (-0.1753,-0.4310) circle (0.027)
- node[below left] {$Z_1^*$};
- node at (0,1.5) {The $Z$-plane};
- node at (0,-1.42) {$abs{Z-q}le p$ is shaded};
+ 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};
draw[->,thick] (1.68,0.22)--(3.78,0.22)
- node[midway,above=5pt] {$w=(1+Z)/(1-Z)$};
+ 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$};
+ draw[black!35,->] (-0.15,0)--(3,0) node[right] {re w};
draw[black!65,->] (0,-1.16)--(0,1.22);
draw[dashed,teal!65!black] (0.6667,-1.1)--(0.6667,1.1);
- node[below right] at (0.6667,0) {$q/p$};
+ node[below right] at (0.6667,0) {q/p};
draw[->,thick,blue!70!black] (0.35,0.65)--(1.6333,0.65);
fill[blue!70!black] (0.35,0.65) circle (0.027)
- node[above left] {$w_0$};
+ node[above left] {w_0};
fill[blue!70!black] (1.6333,0.65) circle (0.027)
- node[above] {$w_0(R)$};
+ node[above] {w_0(R)};
draw[->,thick,orange!80!black] (0.5,-0.55)--(2.3333,-0.55);
fill[orange!80!black] (0.5,-0.55) circle (0.027)
- node[below left] {$w_1$};
+ node[below left] {w_1};
fill[orange!80!black] (2.3333,-0.55) circle (0.027)
- node[below] {$w_1(R)$};
- node at (1.4,1.5) {The $w$-plane};
- node at (1.4,-1.42) {Both paths use the same $0le vle R$};
+ 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 0le vle R};
caption{Geometry of the simultaneous continuation. The Cayley map turns
-the deletion disk into $re wge q/p$. Two possible starting coordinates
+the deletion disk into re wge 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+iiImw_r$ for
-$0le vle R$. The proof interpolates
-$F(Z_0(v),...,Z_{k-1}(v))$ on one complex strip, simultaneously for
+same parameter: w_r(v)=(1+v)re w_r+iiImw_r for
+0le vle R. The proof interpolates
+F(Z_0(v),...,Z_{k-1}(v)) on one complex strip, simultaneously for
every coordinate.}
-On the closed strip $-1/2lere vle 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_rge q/p$, so (eq:trace-polydisk-bound)
+On the closed strip -1/2lere vle 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_rge q/p, so (eq:trace-polydisk-bound)
applies. Moreover
1+Rle C(Y^alpha)/(p),
-because $gamma=c_2q_*Y^{-alpha}$ and $qle q_*$.
+because gamma=c_2q_*Y^{-alpha} and qle q_*.
-A left-boundary bound free of $n^k$ is needed. The identity
-$1-abs Z^2=4re w/abs{w+1}^2$ gives, at $re v=-1/2$,
+A left-boundary bound free of n^k is needed. The identity
+1-abs Z^2=4re w/abs{w+1}^2 gives, at re v=-1/2,
1-abs{Z_r(v)}gefrac{1-abs{Z_r^*}}{4(1+abs v)^2}.
To check the constant, first use
-$1-abs{Z_r(v)}gexi_r/abs{w_r(v)+1}^2$ and
-$1-abs{Z_r^*}le4xi_r/abs{w_r+1}^2$, then
-$abs{w_r(v)+1}leabs{w_r+1}+xi_rabs vle(1+abs v)abs{w_r+1}$.
-The coefficients of $F$ have magnitude at most two, so summing independent
+1-abs{Z_r(v)}gexi_r/abs{w_r(v)+1}^2 and
+1-abs{Z_r^*}le4xi_r/abs{w_r+1}^2, then
+abs{w_r(v)+1}leabs{w_r+1}+xi_rabs vle(1+abs v)abs{w_r+1}.
+The coefficients of F have magnitude at most two, so summing independent
geometric series over the positive prefix and gap lengths gives, in the
open unit polydisk,
[
@@ -1452,23 +1452,23 @@ has the boundary bounds
logabs{g(v)}&le klog(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$.
+On the left (1+abs v)/abs{2+v} is bounded absolutely; on the right
+abs{2+v}ge2+R>1. The function g is analytic and bounded on the strip,
+since F is a finite polynomial on the unit polydisk and abs{2+v}ge3/2.
The strip estimate used here is a consequence of the maximum principle. If a
-bounded analytic function on $alere vle b$ has logarithmic boundary
-bounds $L_-,L_+$, then at real $tin[a,b]$ its logarithm is at most
-$((b-t)L_-+(t-a)L_+)/(b-a)$. Multiply by the exponential of the negative
+bounded analytic function on alere vle b has logarithmic boundary
+bounds L_-,L_+, then at real tin[a,b] its logarithm is at most
+((b-t)L_-+(t-a)L_+)/(b-a). Multiply by the exponential of the negative
affine interpolant to make both sides one; on rectangles of height tending
to infinity apply the maximum principle after multiplying by
-$exp{tau(v^2-max{a^2,b^2})}$ for $tau>0$, which has modulus at most
+exp{tau(v^2-max{a^2,b^2})} for tau>0, which has modulus at most
one on the vertical sides and tends to zero on the horizontal sides. Let
-the height tend to infinity, then $tauto0$; this proves the estimate,
+the height tend to infinity, then tauto0; this proves the estimate,
including zeros of the function by continuity.
-At $t=0$ the right boundary has weight $1/(2R+1)$. By
-(eq:input-polynomial-signal), $logabs{g(0)}ge-E_h-1-2klog2$.
+At t=0 the right boundary has weight 1/(2R+1). By
+(eq:input-polynomial-signal), logabs{g(0)}ge-E_h-1-2klog2.
Substituting (eq:strip-side-bounds) gives
log(1/ε)
@@ -1480,11 +1480,11 @@ This is the quantitative transfer from input coordinates to trace
coordinates.
It remains to compare this exponent with the budget (eq:budget). Put
-$t=log_2mu$. The choices in (eq:separation-cutoff) give
-$t+alpha<3$, and
+t=log_2mu. The choices in (eq:separation-cutoff) give
+t+alpha<3, and
[
- 4^hle CY^2,qquad E_hle CA_0Y^t,qquad
- A_0le Q(1+log Y),qquad QYle Clog n.
+ 4^hle CY^2, E_hle CA_0Y^t,
+ A_0le Q(1+log Y), QYle Clog n.
]
Thus (eq:strip-width) yields
@@ -1495,7 +1495,7 @@ Thus (eq:strip-width) yields
&lefrac Cp(log n)Y^{1+alpha}(1+log Y)
lefrac Cp(log n)Y^2(1+log Y).
-Also, since $nge2$ and $log(1/p)le1/p$,
+Also, since nge2 and log(1/p)le1/p,
[
klog(n/p)le CY^2(log n+log(1/p))
lefrac Cp(log n)Y^2.
@@ -1508,18 +1508,18 @@ Using (eq:aux-comparisons-2), the right-hand side of
(1+logmathsf X(n,p))^6sfX(n,p))^6
=C_6,B(n,p).
-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
+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~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
+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~thm:separation gives a test for the first wrong bit of a
@@ -1531,32 +1531,32 @@ strict slack, both in its statistical constraints and in its positivity
condition. That slack is exhibited first, then a rational procedure is given
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
+Assume for now p<1. Choose an integer D and a positive dyadic number
+zeta=2^{-b_zeta} so that
- D_*le Dle CY^2,quad
- zetaletfrac14,quad
- 4zeta<e^{-C_{sep}B(n,p)},quad
+ D_*le Dle CY^2,
+ zetaletfrac14,
+ 4zeta<e^{-C_{sep}B(n,p)},
b_zeta=O(B(n,p)),
-with $C_{sep}$ from Theorem~thm:separation. Integer
+with C_{sep} from Theorem~thm:separation. Integer
formulas for these choices come later. Let
[
- mathcal I_D=calI_D={I⊆{1,...,n}:1le|I|le D},quad
- N=|mathcal I_D|,calI_D|,quad
+ mathcal I_D=calI_D={I⊆{1,...,n}:1le|I|le D},
+ N=|mathcal I_D|,calI_D|,
T=512(1+N)zeta^{-2},
]
-which is an integer. From $T$ independent traces form the empirical mean
-$widehatwidehat t_I$t_I$ of the rank observable defining $T_I$, for every
-$Iinmathcal I_D$.calI_D$. These are ordinary trace observables: a requested
+which is an integer. From T independent traces form the empirical mean
+widehatwidehat t_It_I of the rank observable defining T_I, for every
+Iinmathcal I_D.calI_D. These are ordinary trace observables: a requested
rank that is absent contributes zero.
-For each fixed input $x$ let $mathcal G$calG$ be the event
+For each fixed input x let mathcal GcalG be the event
|widehatwidehat t_I-T_I(x)|t_I-T_I(x)|lezeta/8quadfor every Iinmathcal I_D.calI_D.
-Each observable takes values in ${0,1}$, so its empirical mean has
-variance at most $1/(4T)$. Chebyshev and a union bound give
+Each observable takes values in {0,1}, so its empirical mean has
+variance at most 1/(4T). Chebyshev and a union bound give
mathbb P_x(bbP_x(mathcal G^c)calG^c)le(16N)/(Tzeta^2)lefrac1{32}.
@@ -1564,25 +1564,25 @@ 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)$calM_D(m)$ from (eq:moment-matrix); its nonempty
-moment coordinates form a real vector $m$. Consider the rational
+matrix M(m)=mathcal M_D(m)calM_D(m) from (eq:moment-matrix); its nonempty
+moment coordinates form a real vector m. Consider the rational
constraints
- min[-1,1]^l,quad M(m)succeq0,quad
+ min[-1,1]^l, M(m)succeq0,
|EE_m[T_I]-widehatwidehat t_I|t_I|lezetaquad(Iinmathcal I_D),calI_D),
-where $l$ is the number of moment coordinates. Substituting the prefix and
+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
+EE_m[T_I] an affine function of m; its nonconstant coefficients have
absolute sum at most one by (eq:coeff-bounds).
-On $mathcal G$,calG$, a prefix whose first incorrect bit is at its last
+On mathcal G,calG, a prefix whose first incorrect bit is at its last
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
+prefix has a moment vector m^*in[-1,1]^l such that, with G the
dimension of its moment matrix,
- M(m^*)succeq(zeta/8)Id_G,qquad
+ M(m^*)succeq(zeta/8)Id_G,
|EE_{m^*}[T_I]-widehatwidehat t_I|t_I|lezeta/2quad(Iinmathcal I_D).calI_D).
@@ -1590,17 +1590,17 @@ dimension of its moment matrix,
Proof.
If a wrong prefix had a feasible moment vector, then
(eq:empirical-good) and (eq:prefix-feasibility) would give
-$|EE_m[T_I]-T_I(x)|le9zeta/8$ for all $Iinmathcal I_D$,calI_D$, contradicting
+|EE_m[T_I]-T_I(x)|le9zeta/8 for all Iinmathcal I_D,calI_D, contradicting
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
-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$; (eq:empirical-good) then bounds the discrepancy
-from $widehatwidehat t_I$t_I$ by $zeta/4$, stronger than required.
+1-zeta/8 and the moments of independent uniform signs on the remaining
+positions with weight zeta/8. The latter moment matrix is the identity:
+its (I,J) entry is zero unless I=J. The mixture has the stated matrix
+lower bound and coordinates in [-1,1]. Both constituent distributions
+give channel expectations in [0,1], so mixing changes each T_I(x) by
+at most zeta/8; (eq:empirical-good) then bounds the discrepancy
+from widehatwidehat t_It_I by zeta/4, stronger than required.
The next lemma gives the bounded procedure for
@@ -1612,52 +1612,52 @@ Motzkin--Schoenberg; the iteration and its rounding analysis are given
explicitly.
[Rational feasibility with slack]
-Let $rge0$ and $Dge1$ be integers, and let $m$ consist of the
+Let rge0 and Dge1 be integers, and let m consist of the
[
l=sum_{j=1}^{min(2D,r)}binom rj
]
-nonempty sign moments. Let $M(m)$ be their moment matrix, of dimension
+nonempty sign moments. Let M(m) be their moment matrix, of dimension
[
G=sum_{j=0}^{min(D,r)}binom rj.
]
-Suppose a finite list of rational affine inequalities $ell_t(m)le b_t$
-is given, each with nonconstant coefficient vector of $ell^1$-norm at
-most one, together with a dyadic $0<zetale1/4$. Then a deterministic
+Suppose a finite list of rational affine inequalities ell_t(m)le b_t
+is given, each with nonconstant coefficient vector of ell^1-norm at
+most one, together with a dyadic 0<zetale1/4. Then a deterministic
rational procedure either returns a vector with
[
- min[-1,1]^l,quad M(m)succeq0,quad ell_t(m)le b_t for all t,
+ min[-1,1]^l, M(m)succeq0, ell_t(m)le b_t for all t,
]
-or reports failure. It returns a vector whenever some $m^*in[-1,1]^l$
+or reports failure. It returns a vector whenever some m^*in[-1,1]^l
satisfies
[
- M(m^*)succeq(zeta/8)Id_G,quad
+ M(m^*)succeq(zeta/8)Id_G,
ell_t(m^*)le b_t-zeta/2 for all t.
]
-Put $lambda=zeta/(16G)$. The procedure performs at most
-$lceil10(1+l)/lambda^2rceil$ feasibility checks, each taking polynomially
+Put lambda=zeta/(16G). The procedure performs at most
+lceil10(1+l)/lambda^2rceil 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.
+log(1/zeta). These time bounds hold without the slack assumption.
Proof.
-If $l=0$ the matrix is $[1]$ and all inequalities are constant, so direct
-rational comparisons suffice. Suppose $l>0$. Exact separating
+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^{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^{cur})>b_t$ gives
-the direction $a$ equal to minus its nonconstant coefficient vector. Then
-$norm a_2le1$ and, under the slack assumption,
-$< m^*-m^{cur},a>gezeta/2gelambda$.
-
-If instead the matrix condition fails, find a nonzero rational vector $v$
-with $v^top M(m^{cur})v<0$ (constructed just below). Write the
-associated affine form as $v^top M(m)v=c+hcdot m$ and set
-$a=h/(G,v^top v)$. Each matrix entry is the constant $1$ or one moment
-coordinate, so $norm h_1lenorm v_1^2le Gnorm v_2^2$ and
-$norm a_2le1$. The slack matrix bound 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_2le1 and, under the slack assumption,
+< m^*-m^{cur},a>gezeta/2gelambda.
+
+If instead the matrix condition fails, find a nonzero rational vector v
+with v^top M(m^{cur})v<0 (constructed just below). Write the
+associated affine form as v^top M(m)v=c+hcdot m and set
+a=h/(G,v^top v). Each matrix entry is the constant 1 or one moment
+coordinate, so norm h_1lenorm v_1^2le Gnorm v_2^2 and
+norm a_2le1. The slack matrix bound gives
[
< m^*-m^{cur},a>
=frac{v^top(M(m^*)-M(m^{cur}))v}{G,v^top v}
@@ -1665,7 +1665,7 @@ $norm a_2le1$. The slack matrix bound gives
]
Thus either violated condition yields a rational direction with
- norm a_2le1,qquad < m^*-m^{cur},a>gelambda
+ norm a_2le1, < m^*-m^{cur},a>gelambda
whenever a slack solution exists. A violated constant inequality has zero
direction; that cannot happen in the slack case, and otherwise the
@@ -1676,41 +1676,41 @@ For a rational symmetric matrix, eliminate a positive diagonal pivot via
its Schur complement. Congruence by an invertible triangular matrix shows
the original is positive semidefinite exactly when the positive pivot and
this Schur complement are. A negative diagonal gives a negative unit
-vector. If a remaining diagonal at $i$ is zero and its entry $b$ in column
-$j$ is nonzero, let $c$ be the diagonal at $j$; assume $cge0$,
+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 cge0,
else a negative diagonal already exists. Then
[
y=e_i-(b)/(1+c+|b|)e_j
]
has quadratic form
-$(b^2)/((1+c+|b|)^2)[-2(1+c+|b|)+c]<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
-arithmetic: with $P$ the eliminated block and $B$ its block against the
-remaining indices, the lift of $y$ is $v=(-P^{-1}By,,y)$, whose quadratic
-form equals that of $y$ for the Schur complement.
+arithmetic: with P the eliminated block and B its block against the
+remaining indices, the lift of y is v=(-P^{-1}By,,y), whose quadratic
+form equals that of y for the Schur complement.
These operations have polynomial bit complexity. Clear denominators in a
-rational matrix with $t$-bit entries; the product of all denominators has
-at most $G^2t$ bits. If $H$ is the resulting integer matrix with $s$-bit
-entries, the determinant expansion bounds every $j$-row minor by
-$j!,2^{js}$, of bit length $O(G(s+log G))$. Schur-complement entries are
-ratios of minors, and the inverse formula for $P$ gives the same bound for
+rational matrix with t-bit entries; the product of all denominators has
+at most G^2t bits. If H is the resulting integer matrix with s-bit
+entries, the determinant expansion bounds every j-row minor by
+j!,2^{js}, of bit length O(G(s+log G)). Schur-complement entries are
+ratios of minors, and the inverse formula for P gives the same bound for
the lift. Fraction-reduced elimination with rational comparisons computes
the check and the negative vector in polynomially many bit operations,
however small a positive pivot or negative quadratic form may be.
{itshape Iteration and rounding.}
-Start with $m^{cur}=0$. Choose the dyadic grid with mesh
+Start with m^{cur}=0. Choose the dyadic grid with mesh
[
- eta=2^{-g},qquad
+ eta=2^{-g},
g=Bigllceillog_2(100(1+l))/(lambda^2)Bigrrceil.
]
-The integer $g$ is computed by rational comparisons with powers of two, so
-$etalelambda^2/(100(1+l))$, with $O(1+log((1+l)/lambda))$ fractional
-bits. After an unsuccessful check, add $lambda a$, clip every coordinate
-to $[-1,1]$, and round to the nearest grid point in the box (both box
+The integer g is computed by rational comparisons with powers of two, so
+etalelambda^2/(100(1+l)), with O(1+log((1+l)/lambda)) fractional
+bits. After an unsuccessful check, add lambda a, clip every coordinate
+to [-1,1], and round to the nearest grid point in the box (both box
endpoints lie on the grid). Repeat up to the stated number of checks,
reporting failure if none accepts.
@@ -1719,13 +1719,13 @@ Under the slack assumption (eq:feasibility-direction) gives
norm{m^{cur}+lambda a-m^*}_2^2
lenorm{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
-$4leta+leta^2<lambda^2/2$. Each failed check thus decreases squared
-distance by at least $lambda^2/2$, whose initial value is at most $l$, so
+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
+4leta+leta^2<lambda^2/2. Each failed check thus decreases squared
+distance by at least lambda^2/2, whose initial value is at most l, so
acceptance occurs before the cap. Finally, rounding keeps every iterate on
a single grid of the indicated bit length; the exact matrix check, the
-affine comparisons, forming and normalizing $h$, and one update involve
+affine comparisons, forming and normalizing h, and one update involve
polynomially many rational operations on numbers of polynomial bit length,
and temporary denominators do not accumulate across updates. The fixed cap
and these bounds apply to every rational input list, with or without a
@@ -1741,12 +1741,12 @@ acceptance, on any data, gives an actual moment system satisfying
The decoder starts with the empty prefix and tests both one-bit
extensions. If precisely one accepts, it appends that bit; otherwise it
-appends $0$. It repeats until the prefix has length $n$. The latter rule
-specifies a length-$n$ output even on data where the statistical estimates
-fail. There are at most $2n$ tests.
+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 (eq:decoder-parameters) are now realised using only the
-binary input. Continue to assume $p<1$ and use $q_*,Q,Y$ from
+binary input. Continue to assume p<1 and use q_*,Q,Y from
(eq:aux-parameters). Define the positive integers
u&=1+lceillog_2 nrceil, &
@@ -1758,31 +1758,31 @@ binary input. Continue to assume $p<1$ and use $q_*,Q,Y$ from
All logarithms here mean integer length comparisons. In particular the
integer part of a logarithm of a rational number is found by comparing its
numerator with power-of-two multiples of its denominator, and the rational
-maximum defining $q_*$ is found by an integer comparison.
+maximum defining q_* is found by an integer comparison.
The elementary comparisons
[
- uasymplog n,quad vasymp Q,quad Yle yle C Y,quad
- wasymp1+log Y,quad p^{-1}le a_ple2p^{-1}
+ uasymplog n, vasymp Q, Yle yle C Y,
+ wasymp1+log Y, p^{-1}le a_ple2p^{-1}
]
-have absolute constants. For the bound on $y$ use $uge(log n)/log2$
-and $vle Q/log2$. With $Yasympmathsf X(n,p)$sfX(n,p)$ these give
+have absolute constants. For the bound on y use uge(log n)/log2
+and vle Q/log2. With Yasympmathsf X(n,p)sfX(n,p) these give
B(n,p)le a_p,u,y^2,w^6le C,B(n,p).
-Choose fixed positive integers $K_D,K_m$ large enough for the constants in
+Choose fixed positive integers K_D,K_m large enough for the constants in
Theorem~thm:separation and set
- D=K_Dy^2,qquad b_zeta=K_m,a_p,u,y^2,w^6,qquad
+ D=K_Dy^2, b_zeta=K_m,a_p,u,y^2,w^6,
zeta=2^{-b_zeta}.
-Since $D_*le C Y^2$ and $B(n,p)gelog2$, these ensure all of
-(eq:decoder-parameters). The integers $D,b_zeta$ in binary are
+Since D_*le C Y^2 and B(n,p)gelog2, these ensure all of
+(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.
+denominator 2^{b_zeta} then costs O(b_zeta) bits, included below.
-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
+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}
@@ -1791,64 +1791,64 @@ $i_1<...<i_k$ the coefficient of $X_{i_1}... X_{i_k}$ in $T_I$ is
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$
+contain the indicated numbers of extra retentions; positions after i_k
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
-(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
+If the input representation is p=a/b, every denominator in
+(eq:explicit-channel-coefficient) divides b^n. Binomial
+coefficients have O(n) bits. Sign expansion adds a denominator dividing
+2^D, and empirical means have denominator T. Hence the constraint
+coefficients have polynomial bit length in n+L+D+log T. Enumerating the
rank and input tuples, expanding the resulting bit monomials, and
substituting the prefix constructs them directly; no list of complete
trace masks is needed.
-These enumerations fit the resource scale. From $D=O(Y^2)$,
-$Yasympmathsf X(n,p)$,sfX(n,p)$, and (eq:budget),
+These enumerations fit the resource scale. From D=O(Y^2),
+Yasympmathsf X(n,p),sfX(n,p), and (eq:budget),
Dlog n=O(B(n,p)).
The rank list, every matrix basis, and every moment list have size at most
-$(n+1)^{2D}=exp(O(B(n,p)))$, and so do input tuple lists. A sign expansion
-has at most $2^D$ terms; products of these enumerations remain
-$exp(O(B(n,p)))$. Subsets larger than the available positions are simply
-absent, so this includes $D>n$ and prefixes with very few remaining
+(n+1)^{2D}=exp(O(B(n,p))), and so do input tuple lists. A sign expansion
+has at most 2^D terms; products of these enumerations remain
+exp(O(B(n,p))). Subsets larger than the available positions are simply
+absent, so this includes D>n and prefixes with very few remaining
positions.
-By (eq:decoder-parameters), $T$ is $exp(O(B(n,p)))$. For every
+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^2zeta^{-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))$.
+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
n+L+exp(O(B(n,p))),
including parameter and constraint construction, exact rational
-arithmetic, and the at most $2n$ prefix tests.
+arithmetic, and the at most 2n prefix tests.
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
+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$.
+and this branch takes polynomially many bit operations in n+L.
-For $p<1$, use (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$,calG$, induction on prefix length shows precisely the correct
+On mathcal G,calG, induction on prefix length shows precisely the correct
extension accepts: the incorrect extension is infeasible by
Lemma~lem:prefix-slack, and the correct one has the slack that
-guarantees acceptance. Thus the output is $x$ on $mathcal G$,calG$, whose
-probability is at least $31/32>2/3$ for each fixed $x$.
+guarantees acceptance. Thus the output is x on mathcal G,calG, whose
+probability is at least 31/32>2/3 for each fixed x.
-Each trace has at most $n$ bits and one delimiter. Reading the traces and
+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)$
+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 (eq:decoder-total-resource) bounds every
well-formed trace stream, independently of the success event, and the
@@ -1859,14 +1859,14 @@ on tapes; replacing an indexed lookup by a scan costs at most a polynomial
factor in their total encoded length. Integer addition, multiplication,
division, and fraction reduction have elementary polynomial-time multitape
implementations. The bit-length and loop bounds thus give absolute
-constants $K,d$ with trace count at most $exp(KB(n,p))$ and total bit cost
-at most $(n+L+exp(KB(n,p)))^d$, after enlarging $K,d$ to absorb fixed
-factors. This enlargement is uniform because $B(n,p)gelog2$. Choose
-absolute $C,c$ with $Cge K$ and $cge d$; both the sample bound $M_C(n,p)$
-and the runtime $(n+L+M_C(n,p))^c$ follow. All constants in parameter
+constants K,d with trace count at most exp(KB(n,p)) and total bit cost
+at most (n+L+exp(KB(n,p)))^d, after enlarging K,d to absorb fixed
+factors. This enlargement is uniform because B(n,p)gelog2. Choose
+absolute C,c with Cge K and cge 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.
-par
+