editors: nobody
% =====================================================================
% Uniform quasipolynomial-time trace reconstruction
% A self-contained, student-friendly write-up of the full proof.
% Compile with pdflatex. Every symbol is defined before it is used.
% =====================================================================
usetikzlibrary{arrows.meta,positioning,calc,decorations.pathreplacing}
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
kept bits, in their original order, form the trace. For example, if
x=1011 and the deletion removes positions 2 and 4, the resulting
trace is 11. The trace reports
its own length and its bits, but nothing about which original positions
survived. An algorithm is handed n, the value p (as a rational
number), and a stream of independent traces of x, and must output
x. 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.
If the trace were the input up to independent bit flips, one could
denoise one coordinate at a time. Here the trouble is different: the
same trace rank can come from many different input positions as the
random deletions shift everything. So the desired positions are
``smeared out'', and local statistics do not suffice. What rescues the problem is
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.
Define the budget proxy
mathsf X(n,p)sfX(n,p) &=
1+(log n)/(1+log(1/q)), & q>0,[6pt]
1, & q=0,
[4pt]
B(n,p) &= p^{-1},(log n),mathsf X(n,p)^2sfX(n,p)^2,
(1+log mathsf X(n,p))^6sfX(n,p))^6 .
[Uniform trace reconstruction]
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*)]
reads at most M_C(n,p)=bigllceil exp(C,B(n,p))bigrrceil
traces,
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+L+M_C(n,p))^c
]
bit operations. This count already includes reading every trace bit
and every delimiter, all preprocessing, all finite-precision arithmetic,
and writing the output. The only thing not counted is the external
generation of the traces.
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
probability laws on strings. The heart of the argument is a
separation theorem: any positive moment functional that insists
on a wrong bit at some position must disagree, by an exponentially
small but nonzero amount, with one of the observable trace statistics.
That is an analytic fact, proved by moving a local signal out to large
distance scales and then rotating it into the trace generating
function. Turning separation into an algorithm then tests one bit at a
time using exact rational feasibility, with a bound on the cost. The
lineage of these ideas comes next.
Reconstructing a sequence from corrupted copies has a long
information-theoretic history. Levenshtein studied reconstruction under
several combinatorial and probabilistic channel models. Batu, Kannan,
Khanna, and McGregor brought reconstruction from independent random
deletion traces into theoretical computer science, motivated partly by
sequence alignment. What separates the deletion channel from
coordinatewise denoising is that a single trace rank can originate at
many input positions.
doi.org/10.1109/18.904499
For a fixed deletion probability, Holenstein, Mitzenmacher, Panigrahy,
and Wieder proved a worst-case sample bound of exp(widetilde
O(sqrt n)). In independent STOC 2017 papers, De, O'Donnell, and
Servedio, and separately Nazarov and Peres, proved
exp(O(n^{1/3})) bounds together with matching limitations for
methods that use only trace means. Their complex-analytic approach ties
deletion statistics to bounded-coefficient polynomials, with analytic
inequalities of Borwein and Erd'elyi in the background. That
mean-based lower bound restricts a method, not arbitrary trace
algorithms.
doi.org/10.1145/1347082.1347125
doi.org/10.1214/18-AAP1394
doi.org/10.1145/3055399.3055494
doi.org/10.1512/iumj.1997.46.1435
Chase improved the general sample upper bound to
exp(O(n^{1/5}log^5 n)). 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
nonlocal low-order statistics and a multiscale propagation argument;
their bound is quasipolynomial when p^{-1} is polylogarithmic in n.
The uniform reconstruction algorithm developed later builds on this
strategy and adds an explicit bit-complexity bound.
arxiv.org/pdf/2009.03296
doi.org/10.1214/20-AIHP1089
doi.org/10.1214/19-AAP1506
arXiv:2607.04073
Sample complexity and reconstruction time need different arguments. At
fixed confidence, maximum likelihood reconstructs worst-case using at
most O(n) times the optimal sample count, but evaluating it over all
candidate strings requires a large search. Burudgunte, Valiant, and
Wang explicitly separate testing two known strings from reconstructing
an unknown string, and leave quasipolynomial-time reconstruction open
for their approach. The extra separation proved later concerns every
positive semidefinite moment completion of a wrong prefix. It enables
constructive feasibility tests in place of a search over complete
strings. Earlier polynomial-time results already cover low-deletion
regimes.
arxiv.org/pdf/2308.14993
arXiv:2607.04073
doi.org/10.4230/LIPIcs.ITCS.2021.20
The use of nonlocal statistics is essential to the comparison with
known barriers. Chen, De, Lee, and Servedio proved strong lower bounds
for statistical queries restricted to short consecutive trace blocks.
The statistics used later involve few ranks but may span the whole
trace. The generating-function identity that transfers them from input
coordinates has antecedents in higher-order trace reconstruction.
doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.52
arXiv:2607.04073
arxiv.org/pdf/2008.12386
arxiv.org/pdf/2009.03296
The positive moment relaxation is a Boolean instance of the semidefinite
moment and sum-of-squares framework. The finite feasibility iteration is
related to the classical relaxation methods of Agmon and
Motzkin--Schoenberg. The analytic separation and the rational
implementation are proved directly; no external trace-reconstruction or
optimization theorem is imported.
doi.org/10.1137/S1052623400366802
doi.org/10.7907/2K6Y-CH43
doi.org/10.4153/CJM-1954-037-2
doi.org/10.4153/CJM-1954-038-x
The decoder measures expected products of a few trace ranks and tests them
against a convex family. Everything the algorithm ever sees is a
trace statistic: an expected product of a few trace ranks. Because
the input positions behind those ranks are unknown, the algorithm
treats these statistics as a system of linear equations with a
semidefinite (positivity) condition, and solves for a 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
variables standing for the unknown bits. Products are always reduced by
X_i^2=X_i (a bit times itself is itself), so every polynomial has
degree at most the number of distinct variables it mentions.
Fix a nonempty set of ranks I={ell_1<...<ell_k}⊆[n]. The
corresponding trace observable is the product of the bits that sit
at those ranks in a single trace; if the trace is shorter than ell_k,
the observable is 0. Let T_I(X) be its expectation over the
deletion channel, viewed as a polynomial in the input bits:
T_I(X)=sum_{i_1<...<i_k} c_{I;,i_1,...,i_k},X_{i_1}... X_{i_k}.
The coefficient c_{I;,i_1,...,i_k} is the probability that the
input positions i_1,...,i_k land at trace ranks
ell_1,...,ell_k. As the input tuple varies these events are
disjoint, so
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
over independent traces. It never learns the coefficients' input
positions from the data, only the numeric value.
The following Boolean moment relaxation is a special case of the
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
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.
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*)]
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;
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.
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
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,
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
that is wrong exactly at its last position,
u_i=x_i (i<d), u_d=1-x_d.
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
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
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
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.
[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
[
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
[
|EE[T_I]-T_I(x)|
> exp(-C_{sep},B(n,p)).
]
The theorem holds for every feasible array, including arrays that
no distribution realises. Its proof runs through the construction of a slowly decaying signal, the
transfer of that signal to trace statistics, and the decoder that turns
the resulting separation into an algorithm. Once separation holds,
accurate empirical trace moments rule out every wrong extension of any
prefix, because a wrong prefix would force a feasible array that violates
such a statistic. A bounded rational computation then finds the feasible
extension.
The separation proof is analytic, so the objects it uses come first.
Fix x,d,EE as above. For 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},
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
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.
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
(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
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
proposition moves a detectable signal to a much smaller decay parameter
S', at the price of letting the order grow by at most a factor of four.
The overall loss in the logarithm of the signal is kept below a factor
of eight. Controlling the angles of the new gap parameters is
equally important: those angle bounds later allow passage from input
coordinates to trace coordinates. Enlarging distance scales while
raising the order follows the strategy of Burudgunte, Valiant, and Wang, but here the comparison functional may be a truncated
positive moment functional, and the scale step uses Gram matrices of
polynomial vectors.
[One multiscale step]
There are absolute constants (0<beta,eta_0<1) and (C_0,C_1ge1)
with this property. Let (f) be an order-(k) feature from
(eq:feature), and let (Delta) come from a moment functional of
order (2D) satisfying the prefix conditions stated earlier.
Suppose
[
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},
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},
beta S'le s'le S', abs{omega'}le2.002s',
and
H_{f'}le H_f^4(1+frac1{beta S'})^3 .
Moreover there are (1le mle4) lists, each equal to the old parameter
list ((z_1,...,z_{k-1})) or its complex conjugate, and at most
(m-1) added parameters, so that: each new inner-gap parameter is a
nonempty product using at most one entry from each list and at most one
added parameter; and every added parameter (e^{-a+iitheta}) obeys
agebeta S', abs{theta}le C_1S.
The proof splits in two. First, a wide Gaussian window turns the signal
into Fourier sums, and positivity of the moment functional forces a
product of at most four such sums to keep a signal while its total
frequency is small. Second, expanding that product and
deforming Gaussian contours produces one feature with the claimed
parameters, built later.
Throughout the proof of Proposition~prop:multiscale set
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
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))),
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.
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)},
B_x(t)=A(t)(x).
The coefficient bound on f_j and the Gaussian sum give
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,
[
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:
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,
[
mathcal S_f(s,calS_f(s,omega)=mathbf EbfE,P(e^{-s+V+iiomega}).
]
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
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
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
int_{RR}Λ(t),(s_1,dt)/(pi(s_1^2+(t-omega)^2))le1.001E.
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
periodizing the density in (eq:poisson-log-bound) gives the circle
Poisson measure at e^{-s_1+iiomega}.
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
[
abs{1-overlineoverline aa z}^2-abs{z-a}^2=(1-abs a^2)(1-abs z^2)ge0
]
bound its contribution by its Poisson integral. Roots on the circle
follow by a radial limit; their logarithmic singularities are integrable.
Summing over factors gives
[
int_{RR}Λ(t)(s_1,dt)/(pi(s_1^2+(t-omega)^2))
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
claim.
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
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
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.
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
[
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
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
[
R(v)=frac2rsum_{mge0}tau^{2m+1}cos((2m+1)pi v)/(r).
]
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
resulting measure has the claimed marginal domination. Its uncovered
mass is
[
int_{-r/2}^{r/2}R(v),dv
=frac4pisum_{mge0}frac{(-1)^mtau^{2m+1}}{2m+1}
=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.
[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
abslambdale2s_1, Λ(lambda)le2.40E.
There is also an absolute C_2 such that, for every abs yle2s_1,
some real t,t' satisfy
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
[
frac{arctan(2-2.003)+arctan(2+2.003)}pi>0.418.
]
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
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
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
sum at most
[
(2(1.001))/(0.733)E<2.74E,
]
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
frequencies in (eq:paired-frequencies) need not be small, but their
differences can be prescribed. These pairs build a chain of
polynomial vectors whose neighbouring inner products have small total
frequency. The following Hilbert-space fact explains why such a chain
keeps the needed exponential accuracy.
[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,
[
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.
Proof.
Put h_i=v_i-v_{i-1}. The hypotheses give
[
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.
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
abs{Delta[G]}ge e^{-7.94E}.
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
[
abs{EE[A(t)]}^2leEE[abs{A(t)}^2]leabs{B_x(t)}^2+ε,
]
hence
abs{Delta[A(t)]}le2abs{B_x(t)}+sqrtε.
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
[
abs{Delta[A(t)]Delta[A(t')]}=U^2e^{-Λ(t)-Λ(t')}
ge e^{-2.74E}.
]
Applying (eq:evaluation-lower-bound) to each gives
abs{B_x(t)B_x(t')bar}ge e^{-2.75E}.
Each evaluation is at least a third of its signal once E is large; the
factor 1/9 is absorbed in e^{-0.01E}.
Take a monotone chain 0=y_0,y_1,...,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
choose a pair from (eq:paired-frequencies) and set
[
V_0=1,
V_i=frac{A(t)A(t')bar}{B_x(t)B_x(t')bar} (0<i<J),
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.
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
[
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
[
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
(eq:single-frequency) and proves the lemma.
There is now a product of at most four windowed feature sums with signal at
least e^{-7.94E} and total frequency at most b. It remains to turn it
into one feature while keeping both decay and frequency of order S';
the Gaussian contour construction below does exactly that.
Lemma~lem:balanced-product gives a product of at most four
windowed Fourier sums with a substantial discrepancy and small total
frequency. That product is now written as an integral of features. The
contour puts their outer parameters in the sector that
Proposition~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
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
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)),
|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,
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.
Set rho=1/2.002. For u=(u_1,...,u_m)inRR^m define
Ω=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
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;
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,
leaving the last on the imaginary axis. The linking horizontal
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
horizontal segments that join its truncations to the imaginary axis at
height pm T, the Gaussian exponent has real part at most -cT^2+O(T)
for some c>0, while exp(v_m(j_m-d)) adds only a linear term in T,
so those linking integrals also vanish. The integrands are entire, so no
residues occur. This proves the identities as iterated integrals; joint
absolute convergence follows from the bound below.
Let nu be the resulting complex measure on RR^m after removing the
position-dependent factors. Outside the measure-zero set Ω=0,
dnu(u)=
(frac{sigma}{√(2pi)})^m
exp((sigma^2)/(2)sum_{r=1}^m v_r^2)
(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
(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
sum_{r=1}^m(re v_r)^2
&=(m-1)b^2+(mb+rho|Ω|)^2 notag
&le 3b^2+(2rho√(textstylesum_r u_r^2)+(4+rho)b)^2
notag
&le (1-c_1)sum_r u_r^2+C_4b^2.
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
(eq:contour-measure) this gives
[
|dnu(u)|le Csigma^m
exp((C_4sigma^2b^2)/(2)
-(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
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
and splitting the negative quadratic term into two equal halves on
mathcal U^ccalU^c gives absolute constants C,C' with
|nu|_{abs}
&le Cexp(C_4K^2beta^2E/2),
int_{mathcal U^c}calU^c|dnu|
&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
absorb fixed prefactors gives
|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.
{itshape Outer parameters and endpoint gaps.}
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
s'=b+rho|Ω|.
The link from j_r to j_{r+1} receives the parameter
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,
[
|Ω|le(beta+1/4)S',
beta S'le s'le[beta+rho(beta+1/4)]S'le S',
|Ω|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
parameters satisfy (eq:multiscale-output) and the endpoint links
satisfy (eq:added-parameters). The choice of C_1 uses only C_3
and S'le S, imposing no new condition on K or beta.
The outer weights are at the right scale. To finish, each interleaving
must have exactly the form of a feature with controlled coefficient sum.
One old inner edge can cross several gaps of the merged tuple, so
charging its damping at every crossing would overcount. A distinct-edge
assignment prevents that loss.
For the fixed interleaving write its distinct positions as
i_1<...<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
crossing it. Each edge length is the sum of the merged gaps it crosses,
so the new parameters reproduce the original weight exactly. Every
merged gap is crossed by some edge, by connectivity, so its damping is
positive. Within one old tuple the inner-edge intervals have disjoint
interiors, and the same holds for the consecutive endpoint links. It
follows that each new parameter uses at most one old parameter from each
copy and at most one added endpoint parameter. This is exactly the
factor-count assertion of Proposition~prop:multiscale.
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
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)).
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
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
at the endpoints of every tree edge, and connectivity forces all values
zero, so g=0. A nonzero term in the determinant expansion of M pairs
its rows and columns through entries equal to one; that pairing is the
required assignment.
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.
[htbp]
centering
[x=1.28cm,y=0.9cm,>=stealth,
olda/.style={draw=blue!70!black,thick},
oldb/.style={draw=orange!85!black,thick},
added/.style={draw=black,thick,dashed}]
draw[gray] (0,0)--(5,0);
foreach a in {1,...,6} {
fill (a-1,0) circle (1.8pt);
node[below=3pt] at (a-1,0) {i_{a}};
}
draw[olda] (0,0) to[bend left=30] node[above,pos=.5] {e_1} (2,0);
draw[olda] (2,0) to[bend left=30] node[above,pos=.5] {e_3} (4,0);
draw[oldb] (1,0) to[bend left=65] node[above,pos=.5] {e_2} (3,0);
draw[oldb] (3,0) to[bend left=65] node[above,pos=.5] {e_4} (5,0);
draw[added] (4,0) to[bend right=60] node[below=2pt,pos=.5] {e_5} (5,0);
foreach a in {1,...,5} {
node at (a-.5,-1.05) {g_{a}};
}
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,
Lemma~lem:edge-gap-assignment gives
H_{f^{mathcal I,u}calI,u}
&leprod_{e assigned}(1+1/a_e)
leprod_{e present}(1+1/a_e) notag
&le H_f^m(1+1/b)^{m-1}le H_f^4(1+1/b)^3.
The second inequality uses that all factors are at least one; the
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
corresponding measure,
Delta[product]
=sum_{mathcal I}calIint_{RR^m}
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
|mathcal S_calS_{f^{mathcal I,u}calI,u}(s',Ω)|
le 2H_f^4(1+1/b)^3sum_{lge0}e^{-bl}
le 2H_f^4(1+1/b)^4.
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
[
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 UcalU had
magnitude below e^{-7.98E}, then (eq:contour-mass) and
(eq:contour-uniform-signal) would give
[
|Delta[product]|
le N_{int}(e^{(0.005-7.98)E}+Ve^{-20E})
le e^{-7.965E}+e^{-19.98E}<e^{-7.94E}.
]
This contradicts Lemma~lem:balanced-product. Some interleaving and
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
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
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
(eq:aux-parameters). Recall from (eq:aux-comparisons) that
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, 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
difference from the true word, as set out earlier. Every
constant chosen below is independent of this system, of n, and of p.
For an absolute constant eta>0 define
S_0=4,
S_j=eta,q_*,Y^{-alpha},S_{j-1},
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 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
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
range gives
t_hleθ^{,2^{h-J_*}-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 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,
log(1/θ)le CA_0,
]
hence
log(1/S_j)le C2^jA_0qquad(0le jle h).
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,
abs{mathcal S_calS_{f^{(0)}}(4,0)}
ge1-2sum_{rge1}e^{-4r}
=1-(2)/(e^4-1)>frac12 .
Use error exponents
E_j=C_5A_0mu^jqquad(0le jle h),
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
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
(eq:scale-cost) give
[
log H_{f^{(j)}}le4log H_{f^{(j-1)}}+3log(1+1/(beta S_j))
le4log H_{f^{(j-1)}}+C2^jA_0,
]
and summing this proves the height bound in (eq:scale-induction).
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
Proposition~prop:multiscale hold, and its signal bound is
e^{-mu E_{j-1}}=e^{-E_j}.
Write f=f^{(h)}, k=k_h, s=s_h, omega=omega_h. There is a signal
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
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
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
[
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.
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
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,
[
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
[
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
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
[
Tgetfrac12gammamin{1,psi^2}.
]
For 0<Tle1 this gives
[
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.
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
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
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
[
frac1{1-abs{Z_r^*}}le1+frac1{a_r+s}le1+frac1{a_r} (rge1),
frac1{1-abs{Z_0^*}}le1+frac1s,
]
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^*}}
lelog H_f+log(1+1/(beta S_h))le C4^hA_0.
Now express the same polynomial through observable trace moments on a
different domain. This is a multivariate trace generating identity from the smoothed-analysis
literature on higher-order trace reconstruction, and the same counting fact
underlies the consecutive-block statistical-query work. The counting
argument is given directly. For a rank tuple
ell=(ell_1,...,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
(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)
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.
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
abs{F(Z)}le(n/p)^kε
qquadwhenever abs{Z_r-q}le p (0le r<k).
This uses only ordinary trace ranks and the convention that a rank
product is zero when the trace is too short.
The lower bound (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:
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
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, xi_rge c_3gamma,
]
with xi_r,zeta_rinRR. For vinCC set
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
every coordinate (Figure~fig:simultaneous-cayley).
suppressfloats[t]
[htbp]
centering
[x=1.2cm,y=1.2cm,>=Stealth,font=small]
fill[blue!4] (0,0) circle (1);
fill[teal!17] (0.4,0) circle (0.6);
draw[black!35,->] (-1.2,0)--(1.32,0) node[right] {re Z};
draw[black!35,->] (0,-1.16)--(0,1.2);
draw[black!65] (0,0) circle (1);
draw[teal!65!black] (0.4,0) circle (0.6);
fill (0.4,0) circle (0.022) node[below right] {q};
node[below right] at (1,0) {1};
fill[blue!70!black] (-0.2027,0.5791) circle (0.027)
node[above left] {Z_0^*};
fill[orange!80!black] (-0.1753,-0.4310) circle (0.027)
node[below left] {Z_1^*};
node at (0,1.5) {The Z-plane};
node at (0,-1.42) {abs{Z-q}le p is shaded};
draw[->,thick] (1.68,0.22)--(3.78,0.22)
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!65,->] (0,-1.16)--(0,1.22);
draw[dashed,teal!65!black] (0.6667,-1.1)--(0.6667,1.1);
node[below right] at (0.6667,0) {q/p};
draw[->,thick,blue!70!black] (0.35,0.65)--(1.6333,0.65);
fill[blue!70!black] (0.35,0.65) circle (0.027)
node[above left] {w_0};
fill[blue!70!black] (1.6333,0.65) circle (0.027)
node[above] {w_0(R)};
draw[->,thick,orange!80!black] (0.5,-0.55)--(2.3333,-0.55);
fill[orange!80!black] (0.5,-0.55) circle (0.027)
node[below left] {w_1};
fill[orange!80!black] (2.3333,-0.55) circle (0.027)
node[below] {w_1(R)};
node at (1.4,1.5) {The w-plane};
node at (1.4,-1.42) {Both paths use the same 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
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
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)
applies. Moreover
1+Rle C(Y^alpha)/(p),
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,
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
geometric series over the positive prefix and gap lengths gives, in the
open unit polydisk,
[
abs{F(Z)}le2prod_{r=0}^{k-1}frac1{1-abs{Z_r}}.
]
It follows from (eq:left-boundary-distance) that
[
g(v):=frac{F(Z_0(v),...,Z_{k-1}(v))}{(2+v)^{2k}}
]
has the boundary bounds
logabs{g(v)}&le W_*+Ck+C &&(re v=-1/2),
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.
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
affine interpolant to make both sides one; on rectangles of height tending
to infinity apply the maximum principle after multiplying by
exp{tau(v^2-max{a^2,b^2})} for tau>0, which has modulus at most
one on the vertical sides and tends to zero on the horizontal sides. Let
the height tend to infinity, then 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.
Substituting (eq:strip-side-bounds) gives
log(1/ε)
&le klog(n/p)+(2R+1)(E_h+1+2klog2)+2R(W_*+Ck+C)notag
&le klog(n/p)+C(1+R)(E_h+4^hA_0).
This is the quantitative transfer from input coordinates to trace
coordinates.
It remains to compare this exponent with the budget (eq:budget). Put
t=log_2mu. The choices in (eq:separation-cutoff) give
t+alpha<3, and
[
4^hle CY^2, E_hle CA_0Y^t,
A_0le Q(1+log Y), QYle Clog n.
]
Thus (eq:strip-width) yields
(1+R)E_h
&lefrac Cp(log n)Y^{t+alpha-1}(1+log Y)
lefrac Cp(log n)Y^2(1+log Y),
(1+R)4^hA_0
&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,
[
klog(n/p)le CY^2(log n+log(1/p))
lefrac Cp(log n)Y^2.
]
Using (eq:aux-comparisons-2), the right-hand side of
(eq:separation-exponent) is at most
frac Cp(log n)Y^2(1+log Y)
le C_6,p^{-1}(log n)mathsf X(n,p)^2sfX(n,p)^2
(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
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
directly in the decoding argument.
Theorem~thm:separation gives a test for the first wrong bit of a
prefix: no moment system that fixes that prefix can match all the
low-order trace statistics. To turn this into an algorithm, the construction must also
recognise a correct prefix in bounded time. The extra fact that
makes this possible is that a correct prefix admits a moment system with
strict slack, both in its statistical constraints and in its positivity
condition. That slack is exhibited first, then a rational procedure is given
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
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
formulas for these choices come later. Let
[
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_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 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
mathbb P_x(bbP_x(mathcal G^c)calG^c)le(16N)/(Tzeta^2)lefrac1{32}.
The same event controls all the prefix tests, even though the prefixes are
chosen using the data.
For a proposed prefix, use the remaining sign variables and their moment
matrix M(m)=mathcal M_D(m)calM_D(m) from (eq:moment-matrix); its nonempty
moment coordinates form a real vector m. Consider the rational
constraints
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
writing each remaining bit as one half of one plus its sign makes
EE_m[T_I] an affine function of m; its nonconstant coefficients have
absolute sum at most one by (eq:coeff-bounds).
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
dimension of its moment matrix,
M(m^*)succeq(zeta/8)Id_G,
|EE_{m^*}[T_I]-widehatwidehat t_I|t_I|lezeta/2quad(Iinmathcal I_D).calI_D).
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
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_It_I by zeta/4, stronger than required.
The next lemma gives the bounded procedure for
(eq:prefix-feasibility). It only promises to succeed when there is
slack, and every reported solution satisfies the exact inequalities. This
sidesteps deciding arbitrary semidefinite feasibility. The procedure is a
projected relaxation method in the tradition of Agmon and
Motzkin--Schoenberg; the iteration and its rounding analysis are given
explicitly.
[Rational feasibility with slack]
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
[
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
rational procedure either returns a vector with
[
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
satisfies
[
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
many bit operations in the list dimensions, the input bit lengths, and
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
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
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
[
< m^*-m^{cur},a>
=frac{v^top(M(m^*)-M(m^{cur}))v}{G,v^top v}
ge(zeta)/(8G)gelambda.
]
Thus either violated condition yields a rational direction with
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
iteration is still bounded.
{itshape An exact matrix check.}
For a rational symmetric matrix, eliminate a positive diagonal pivot via
its Schur complement. Congruence by an invertible triangular matrix shows
the original is positive semidefinite exactly when the positive pivot and
this Schur complement are. A negative diagonal gives a negative unit
vector. If a remaining diagonal at i is zero and its entry b in column
j is nonzero, let c be the diagonal at j; 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
with a positive diagonal pivot; when none remain, all entries are zero and
the remainder is positive semidefinite. A negative vector of a Schur
complement lifts to one of the original matrix using only rational
arithmetic: with P the eliminated block and B its block against the
remaining indices, the lift of y is v=(-P^{-1}By,,y), whose quadratic
form equals that of y for the Schur complement.
These operations have polynomial bit complexity. Clear denominators in a
rational matrix with t-bit entries; the product of all denominators has
at most G^2t bits. If H is the resulting integer matrix with s-bit
entries, the determinant expansion bounds every j-row minor by
j!,2^{js}, of bit length O(G(s+log G)). Schur-complement entries are
ratios of minors, and the inverse formula for P gives the same bound for
the lift. Fraction-reduced elimination with rational comparisons computes
the check and the negative vector in polynomially many bit operations,
however small a positive pivot or negative quadratic form may be.
{itshape Iteration and rounding.}
Start with m^{cur}=0. Choose the dyadic grid with mesh
[
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
endpoints lie on the grid). Repeat up to the stated number of checks,
reporting failure if none accepts.
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
acceptance occurs before the cap. Finally, rounding keeps every iterate on
a single grid of the indicated bit length; the exact matrix check, the
affine comparisons, forming and normalizing h, and one update involve
polynomially many rational operations on numbers of polynomial bit length,
and temporary denominators do not accumulate across updates. The fixed cap
and these bounds apply to every rational input list, with or without a
slack solution.
For a prefix test, write each absolute-value constraint of
(eq:prefix-feasibility) as two affine inequalities and apply
Lemma~lem:rational-feasibility. Lemma~lem:prefix-slack
verifies exactly the slack hypotheses for a correct prefix, and every
acceptance, on any data, gives an actual moment system satisfying
(eq:prefix-feasibility).
The decoder starts with the empty prefix and tests both one-bit
extensions. If precisely one accepts, it appends that bit; otherwise it
appends 0. It repeats until the prefix has length n. The latter rule
specifies a length-n output even on data where the statistical estimates
fail. There are at most 2n tests.
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
(eq:aux-parameters). Define the positive integers
u&=1+lceillog_2 nrceil, &
v&=1+lfloorlog_2(1/q_*)rfloor,
y&=1+lceil u/vrceil, &
w&=1+lceillog_2 yrceil, &
a_p&=lceil1/prceil.
All logarithms here mean integer length comparisons. In particular the
integer part of a logarithm of a rational number is found by comparing its
numerator with power-of-two multiples of its denominator, and the rational
maximum defining q_* is found by an integer comparison.
The elementary comparisons
[
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
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
Theorem~thm:separation and set
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
computable in time polynomial in the input bit lengths; writing the
denominator 2^{b_zeta} then costs O(b_zeta) bits, included below.
Next form the rational constraints. For I={l_1<...<l_k} and
i_1<...<i_k the coefficient of X_{i_1}... X_{i_k} in T_I is
binom{i_1-1}{l_1-1}
prod_{j=1}^{k-1}
binom{i_{j+1}-i_j-1}{l_{j+1}-l_j-1},
p^{l_k}q^{i_k-l_k},
when all gap counts are possible and zero otherwise. Indeed the selected
positions must be retained, and the prefix and successive open gaps must
contain the indicated numbers of extra retentions; positions after i_k
are unrestricted. Formula (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
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),
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
positions.
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)).
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.
Proof. [Proof of Theorem~thm:main]
If p=1, request one trace and output it. For the universal halting
specification, output 0^n if the supplied well-formed trace has a
different length; the actual channel always supplies the input itself,
and this branch takes polynomially many bit operations in n+L.
For p<1, use (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
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.
Each trace has at most n bits and one delimiter. Reading the traces and
computing each of the finitely many rank observables costs polynomially
many bit operations in n+T+N; the empirical counters have O(log T)
bits. All loops, including all feasibility tests, have the input-dependent
caps already given. Thus (eq:decoder-total-resource) bounds every
well-formed trace stream, independently of the success event, and the
machine can ignore its internal random bits.
To pin the computational model, the finite lists are stored sequentially
on tapes; replacing an indexed lookup by a scan costs at most a polynomial
factor in their total encoded length. Integer addition, multiplication,
division, and fraction reduction have elementary polynomial-time multitape
implementations. The bit-length and loop bounds thus give absolute
constants K,d with trace count at most exp(KB(n,p)) and total bit cost
at most (n+L+exp(KB(n,p)))^d, after enlarging K,d to absorb fixed
factors. This enlargement is uniform because B(n,p)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.