Uniform quasipolynomial-time trace reconstruction

1 Introduction

A deletion trace of a binary string is obtained by retaining each position independently with probability p and concatenating the retained bits in order. The trace contains its length and its bits, but does not identify their original positions. Trace reconstruction asks for the original string from independent repetitions of this experiment. We consider the worst case: the unknown string is arbitrary, and the recovery probability must hold separately for each string.

Knowing that a collection of statistics distinguishes every pair of strings gives a sample bound, but an efficient decoder needs a way to find the unknown string. We obtain such a decoder by extending separation to a convex family of moment arrays. The resulting tests determine one bit at a time and can be implemented using rational arithmetic.

1.1 The uniform guarantee

Let n\ge2 be the known original length and let p=a/b\in(0,1] be known, where a,b are positive integers in lowest terms. Write L for the total binary length of a and b, and put q=1-p. All logarithms are natural unless a base is displayed. Define

For fixed p, the budget in (1.1) is O_p((\log n)^3(1+\log\log n)^6) as n\to\infty. Thus both resources in Theorem 1.1 are quasipolynomial. The theorem also controls channels whose retention probability varies with n, including probabilities arbitrarily close to zero or one. Its running-time guarantee is polynomial in the permitted sample budget. For every fixed \kappa>0, the regime q\le n^{-\kappa} has polynomial sample complexity in n and polynomial bit complexity in n+L: indeed, \mathsf X(n,p)\le1+1/\kappa and p^{-1} is bounded by a constant depending only on \kappa, so B(n,p)=O_\kappa(\log n).

1.2 History and relation to earlier work

Reconstructing a sequence from corrupted copies has a broad information-theoretic history; Levenshtein studied reconstruction under several combinatorial and probabilistic channel models [15]. Batu, Kannan, Khanna, and McGregor formulated reconstruction from independent random deletion traces in theoretical computer science, motivated in part by sequence alignment [2]. The missing positions make the problem different from coordinatewise denoising: the same trace rank can originate at many input positions.

For a fixed deletion probability, Holenstein, Mitzenmacher, Panigrahy, and Wieder obtained a worst-case sample bound \exp(\widetilde O(\sqrt n)) [13]. In independent papers published at STOC 2017, De, O’Donnell, and Servedio, and Nazarov and Peres, obtained \exp(O(n^{1/3})) bounds and matching limitations for methods using only trace means [11, 17]. Their complex-analytic approach connects deletion statistics to bounded-coefficient polynomials; analytic inequalities of Borwein and Erdélyi are part of the background to this method [3]. The mean-based lower bound is a restriction on that method, not on arbitrary trace algorithms.

Chase improved the general sample upper bound to \exp(O(n^{1/5}\log^5n)) [6]. On the lower-bound side, Holden and Lyons proved an almost-n^{5/4} bound, and Chase strengthened it to \Omega(n^{3/2}/\log^7n) for fixed deletion probability [12, 5]. Burudgunte, Valiant, and Wang subsequently proved the sample bound

for an absolute c_0, using nonlocal low-order statistics and a multiscale propagation argument [4, Theorem 43]. This bound is quasipolynomial when p^{-1} is polylogarithmic in n. Theorem 1.1 builds on this strategy and provides an explicit uniform reconstruction algorithm with the displayed bit-complexity bound.

Sample complexity and reconstruction time require different arguments. At fixed confidence, maximum likelihood achieves worst-case reconstruction using at most O(n) times the optimal sample count, but evaluating it over all candidate strings entails a large search [10, Corollary 1.1 of the full version]. Burudgunte, Valiant, and Wang explicitly distinguish testing two known strings from reconstructing an unknown string, and leave quasipolynomial-time reconstruction open for their approach [4, Section 1]. The additional separation proved here 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 [8].

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 [7]. Our statistics involve few ranks but may span the whole trace, as in [4]. The generating-function identity used to transfer them from input coordinates has antecedents in higher-order trace reconstruction [9, 6].

The positive moment relaxation is a Boolean instance of the semidefinite moment and sum-of-squares framework [14, 18]. The finite feasibility iteration is related to the classical relaxation methods of Agmon and Motzkin–Schoenberg [1, 16]. We prove the analytic separation and the rational implementation directly; no external trace-reconstruction or optimization theorem is needed.

1.3 Proof strategy and additional ingredients

The decoder estimates products of bits at specified trace ranks; those ranks may be far apart. It then tests a proposed prefix by asking for moments of the remaining input bits that agree with these estimates within a prescribed tolerance. The moment array is constrained so that the expected squared magnitude of every polynomial up to a prescribed degree is nonnegative. Actual distributions give such arrays, but an arbitrary feasible array need not come from a distribution.

The central statement separates the true input from every such array fixing a wrong prefix. Let d be the first wrong position, and write \Delta[P] for the difference between the array’s value on a polynomial P and its value at the true input. Then \Delta[X_d]=\pm1, whereas all differences strictly before d vanish. We propagate this local signal through progressively larger distance scales. At each stage, the statistics are weighted sums over increasing tuples of input positions, with exponential weights on their gaps. We track an exponentially damped Fourier sum of the discrepancies of these tuple statistics, indexed by the last input position. The aim is to reduce its damping and frequency while retaining a detectable discrepancy.

Two features make this propagation compatible with the convex relaxation. First, positivity turns polynomial moments into inner products. If squared norms and neighboring inner products along a chain of J vectors differ from one by at most \xi, then a telescoping argument bounds the endpoint error by O(J^2\xi). Applied to normalized Fourier sums and their products, this forces a detectable product whose total frequency is small. Pairing frequencies at prescribed differences under a Cauchy density supplies enough pairs for this chain.

Second, a Gaussian contour deformation converts each such product back into a tuple statistic with smaller decay and frequency. The paths joining consecutive positions in each old tuple, together with links between their endpoints, form a connected graph. A spanning tree assigns distinct edges to the new gaps, controlling the coefficient mass under interleaving. This retains the signal while the tuple order increases by a factor of at most four.

After the last scale, a generating-function identity transfers input statistics to ordinary trace statistics. In this identity, the channel substitution z=q+pw maps the unit disk in a trace gap parameter w to the disk |z-q|\le p in the corresponding input parameter z. A single complex strip moves all input gap parameters into these disks simultaneously. This supplies the quantitative separation theorem without requiring the algorithm to search for any of the analytic witnesses.

Finally, when the empirical estimates are sufficiently accurate, a true prefix has a moment completion with strict slack: give independent uniform signs a sufficiently small weight in a mixture with its true completion. This preserves the statistical tolerance while making the moment matrix positive definite. We exploit that slack with an explicit sequence of rational updates, exact positivity tests, and rounding to a fixed dyadic grid. A fixed iteration cap gives the worst-stream bound in Theorem 1.1.

Section 2 introduces the relaxation. Section 3 proves the multiscale step, and Section 4 transfers its signal to traces. Section 5 constructs the decoder and proves Theorem 1.1.

2 Moment relaxations and prefix separation

We first describe the finite collection of statistics used by the decoder and the convex set against which they will separate the true input. Throughout, [n]=\{1,\ldots,n\} and X_1,\ldots,X_n are formal Boolean variables. Products and degrees are understood after the reductions X_i^2=X_i.

2.1 Observable trace moments

For a nonempty rank set I=\{\ell_1<\cdots<\ell_k\}\subseteq[n], the corresponding trace observable is the product of the bits at those ranks, with value zero if the trace has length less than \ell_k. Let T_I(X) be its channel expectation, regarded as a polynomial in the input bits. More explicitly,

where c_{I;i_1,\ldots,i_k} is the probability that the selected input positions appear at ranks \ell_1,\ldots,\ell_k in a deletion trace. These events are disjoint as the input tuple varies. Consequently the coefficients are nonnegative, their sum is at most one, and the degree is at most k. They are rational when p is rational. The algorithm will estimate T_I(x) by averaging the observable over independent traces; it never observes the input positions that determine the coefficients.

2.2 Positive moment arrays

The following Boolean moment relaxation is a specialization of the semidefinite moment and sum-of-squares frameworks of Lasserre [14, Section 2] and Parrilo [18, Sections 4.2–4.3]. We use only its defining positivity condition and elementary consequences, proved below. Fix a proposed prefix u\in\{0,1\}^d and an integer D\ge1. On the remaining positions U=\{d+1,\ldots,n\}, use sign variables Y_i=2X_i-1, so Y_i^2=1. A moment array consists of real numbers m_J for J\subseteq U with |J|\le2D, including m_\varnothing=1, subject to

Only existing subsets are indexed; thus the definition also applies when D>|U| or U is empty.

The array defines a functional \EE on polynomials of degree at most 2D by substituting X_i=u_i for i\le d, expanding the other bits as (1+Y_i)/2, reducing Y_i^2=1, and setting \EE[\prod_{i\in J}Y_i]=m_J. We extend this functional complex linearly. We call it a positive moment functional of order 2D fixing u. This terminology asserts (2.1), not the existence of a probability distribution realizing all its moments.

Fix a true input x\in\{0,1\}^n and a prefix u of length d with

For a positive moment functional fixing u, write

Then \Delta[X_d]=\pm1, and \Delta[P]=0 whenever P uses only positions strictly before d. If P is a linear combination of bit monomials of degree at most 2D, Lemma 2.1 gives

For p<1, introduce

When q\ge1/n, Y=\mathsf X(n,p). When q<1/n, 1\le\mathsf X(n,p)\le Y<2. Hence

for an absolute constant C, since n\ge2.

The theorem concerns every feasible array, including arrays not represented by distributions. Its proof occupies the next two sections. Once it is available, empirical trace moments rule out every wrong extension of a correct prefix. Section 5 shows how to find the feasible extension with an explicit bounded computation.

2.3 Exponentially weighted tuple statistics

For the analytic proof, fix x,d,\EE as above. For 1\le k\le2D, an order-k feature is a sequence of polynomials

where z_h=\exp(-a_h+\ii\theta_h), a_h>0, and \theta_h\in\RR. For k=1 this means f_j=X_j. Put

Summing geometric series in the positive gaps shows that H_f\ge1 bounds the sum of the absolute coefficients of each f_j, since (1-e^{-a})^{-1}\le1+1/a for a>0. For s>0 and \omega\in\RR, define its signal by

Every monomial in f_j uses positions at most j, so \Delta[f_j]=0 for j<d. Thus, despite the centered exponent, only nonnegative distances contribute to (2.5). The purpose of the multiscale argument is to preserve a detectable signal while reducing s and |\omega|, at the cost of increasing k.

3 Moving a signal to a larger scale

The signal in (2.5) discounts positions beyond distance about 1/s from the first disagreement. The next proposition moves such a signal to a much smaller decay parameter. It permits an increase in feature order, but keeps the loss in the logarithm of the signal below a factor of eight. Controlling the angles of the new parameters is equally important: those bounds will later permit passage from input coordinates to trace coordinates. Enlarging spatial scales while increasing statistic order follows the strategy of Burudgunte, Valiant, and Wang [4]. Here the comparison functional may be a positive truncated moment functional, and the scale step uses Gram matrices of polynomial vectors.

The proof has two parts. First, a broad Gaussian window turns the original signal into Fourier sums. Positivity of the moment functional then forces a product of at most four such sums to retain a signal while its total frequency is small. Second, expanding that product and deforming Gaussian contours produces a single feature with the asserted parameters. The first part occupies the present subsections; the conversion is carried out in Section 3.4.

3.1 A Gaussian window and its logarithmic bound

Throughout the proof of Proposition 3.1, set

where K is a sufficiently large absolute constant. The constants will be chosen in the order K, then \beta sufficiently small, then \eta_0 sufficiently small, and finally C_0 sufficiently large. The choices of K and \beta will also enforce the contour estimates below.

We use the following consequence of (3.1) repeatedly. The logarithm of any fixed product of powers of H_f,1+\sigma,1/S',1/b, together with a factor \exp(O(k\log(2k))), is bounded by

where C depends only on constants already chosen. Increasing C_0 makes this at most any prescribed positive multiple of E. Only finitely many such estimates will be required, so a single final choice of C_0 suffices.

For real t, define the polynomial and its evaluation

The coefficient bound for f_j and the Gaussian sum imply that

with C absolute and chosen so that U\ge1. By prefix cancellation,

We first show that P retains a signal at almost the original decay:

Let V be a centered real normal variable with variance \sigma^{-2}. Since W(l)\mathbf E e^{Vl}=1,

Write \delta=10^{-4}. Exponential tilting gives

For 0\le l\le\delta s\sigma^2/2, this probability is at most 2e^{-c\delta^2s^2\sigma^2}. For larger l, use the bound one and sum e^{-sl}. Because \abs{\Delta[f_j]}\le2H_f, the contribution from \abs V>\delta s is at most

Here 1/s\le1/(\beta S'), and s^2\sigma^2\ge\beta^2K^2E/\eta_0^2. Choose \eta_0 sufficiently small and then C_0 sufficiently large to make (3.9) less than e^{-2E}. The integral over \abs V\le\delta s consequently has magnitude at least e^{-E}-e^{-2E}\ge e^{-E}/2. Its maximum integrand magnitude is at least that large, proving (3.8).

Set

with value +\infty at a boundary zero. We claim

For completeness, the Cauchy Fourier transform is

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, and for \xi=0 integrate directly. Thus periodizing the density in (3.10) gives the circle Poisson measure at e^{-s_1+\ii\omega}.

To apply it, factor the nonzero polynomial P into linear factors. A factor with a root outside the disk has harmonic logarithmic magnitude inside. For a root a inside, the boundary identity \abs{e^{\ii t}-a}=\abs{1-\overline a e^{\ii t}} and the inequality

give the corresponding upper bound by its Poisson integral. Roots on the circle follow by a radial limit; their logarithmic singularities are integrable. Summing over factors yields

The last term is at most 1.001E by the choice of C_0, proving the claim.

3.2 Frequencies at prescribed differences

We seek a frequency \lambda\in[-2s_1,2s_1] with a large signal and pairs of frequencies with every prescribed difference in that interval. The product A(t)\overline{A(t')} has signed frequency t-t'. After normalization by their evaluations at x, these products will supply 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 neighboring inner product will then have signed frequency of magnitude at most b, even though \abs\lambda may be much larger. The logarithmic estimate makes the required existence of pairs a question about pairing Cauchy mass.

3.3 A product with small total frequency

The window parameters satisfy \abs\omega/s_1\le2.002/0.9999<2.003, so Lemma 3.3 applies to our \Lambda. Individual frequencies in (3.14) need not be small. Their differences, however, can be prescribed. We use these pairs to build a chain of polynomial vectors whose neighboring inner products have small total frequency. The following Hilbert-space fact explains why such a chain preserves the needed exponential accuracy.

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

We have obtained 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 its decay and frequency of order S'. The Gaussian contour construction below supplies that final step of Proposition 3.1.

3.4 Converting a balanced product to a feature

Lemma 3.5 supplies a product of at most four windowed Fourier sums with a substantial discrepancy and small total frequency. We now express that product as an integral of features. The contour will place their outer parameters in the sector required by Proposition 3.1; the remaining issue will be to control the damping factors on their inner gaps.

Fix a product supplied by Lemma 3.5, and let 1\le m\le4 be its number of factors. Expand each factor in the tuples defining f. An interleaving specifies the ordering, including all ties, of the mk labeled positions in these tuples. There are at most (mk)^{mk}=\exp(O(k\log(2k))) interleavings: assigning to each labeled position its rank among the distinct positions gives such a bound. Only interleavings consistent with strict increase inside each old tuple are retained. Fix one interleaving, and relabel its copies so that their endpoints satisfy j_1\le\cdots\le j_m. Equal endpoints may be ordered arbitrarily. After absorbing conjugation into the signs of the frequencies, their window weight is

Conjugation also conjugates the old inner-gap parameters, leaving their dampings unchanged.

A Gaussian contour with controlled total frequency. Recall that \sigma=K\sqrt E/S' and b=\beta S'. For every real l,

Indeed, writing v=\ii u gives the Gaussian Fourier transform. Its value at l=0 is one, and integration by parts shows that its derivative in l is -l/\sigma^2 times itself, proving the formula.

Set \rho=1/2.002. For u=(u_1,\ldots,u_m)\in\RR^m, define

These real parts have partial sums rb for r<m and total sum -b-\rho|\Omega|. When the endpoint exponent is centered at j_m, the total sum gives the real part of its outer coefficient, while the negatives of the partial sums give the real parts of the coefficients on consecutive endpoint gaps. The contour is therefore designed to give outer decay b+\rho|\Omega| and positive inner dampings rb; we verify the exact rewriting below.

For each fixed tuple of positions, first shift the first m-1 contours in (3.20) to their fixed vertical lines \re v_r=b, leaving the last contour on the imaginary axis. The connecting horizontal integrals vanish by Gaussian decay. Next fix (u_1,\ldots,u_{m-1}) and deform the last contour to the piecewise linear graph in (3.21). Its slopes have absolute value \rho<1. Along horizontal segments joining 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. The factor \exp(v_m(j_m-d)) contributes only a linear term in T, so these connecting integrals also vanish. The integrands are entire, and hence no residues occur. This proves the identities as iterated integrals; absolute joint convergence will follow from the next bound.

Let \nu be the resulting complex measure on \RR^m after the factors depending on positions have been removed. More explicitly, outside the measure-zero set \Omega=0,

The last factor is the differential of the bent contour divided by \ii\,du_m. We next obtain estimates uniform over the frequencies in (3.19). These estimates also establish absolute convergence of the joint integrals.

Put \delta_0=1-4\rho^2>0 and c_1=\delta_0/2. Since m\le4 and |\sum t_r|\le b, Young’s inequality gives an absolute C_4 such that

The strict inequality 4\rho^2<1 is essential here: summing at most four imaginary coordinates can multiply their squared norm by four, and the sector constant 2.002 leaves a positive Gaussian decay margin. For example, C_4=3+(4+\rho)^2(1+8\rho^2/\delta_0) suffices. Together with (3.22), this proves

For any fixed tuple of positions, the absolute value of its remaining exponential factor is at most \exp(C_n(1+\sum_r|u_r|)) for a finite constant C_n. This factor is integrable against the Gaussian bound. Thus the iterated deformation also gives a jointly absolutely convergent integral, and finite tuple sums can be interchanged with it.

Write \mathcal U=\{u:\max_r|u_r|\le S'/16\}. Integrating the last bound, and splitting its negative quadratic term into two equal parts on \mathcal U^c, gives absolute constants C,C' with

Here \|\nu\|_{\mathrm{abs}} denotes total variation; the powers \sigma^m cancel under Gaussian rescaling. Choose K large enough that c_1K^2/1024\ge30, then choose \beta\le1/4 small enough that C_4K^2\beta^2/2\le0.001. Increasing C_0 to absorb the fixed prefactors yields

This choice is consistent with the order of constants specified earlier: K is fixed first, \beta second, and \eta_0 may then be reduced to meet the window estimate. Only afterward is C_0 enlarged.

Outer parameters and endpoint gaps. For c_r=v_r+\ii t_r, telescoping the endpoint differences gives

Consequently, the largest endpoint has coefficient -s'+\ii\Omega, where

The link from j_r to j_{r+1} receives the parameter

Thus every added damping is at least b, for every u. On \mathcal U,

The angle in (3.27) has absolute value at most 3(C_3S+S'/16)\le C_1S for a fixed absolute C_1. The outer parameters therefore satisfy the parameter inequalities in (3.2), and the endpoint links satisfy (3.4). The choice of C_1 uses only C_3 and S'\le S and imposes no further condition on K or \beta.

3.5 Interleavings and the cost of the inner gaps

We have obtained outer weights at the required scale. To finish, we must show that each interleaving has 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 cost at every crossing would overcount it. A distinct-edge assignment will prevent this loss.

For our fixed interleaving, write its distinct positions as i_1<\cdots<i_v, where 1\le v\le mk. Form a multigraph on these vertices: include the inner edges of each old tuple and the links between consecutive endpoints in (3.27). Its edges carry their corresponding exponential parameters. It is connected, because each old tuple is a path to its endpoint, and the endpoint links join those paths. Delete loops coming 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 these new parameters reproduce the original weight exactly. Every merged gap is crossed by some edge, by connectivity, and hence its damping is positive. Within a single old tuple, the inner-edge intervals have disjoint interiors. 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 precisely the factor-count assertion in Proposition 3.1.

Ties merge repeated bit variables by the Boolean identity X_i^r=X_i for r\ge1. Once the interleaving is fixed, choosing arbitrary strictly increasing values for its v distinct positions specifies exactly one assignment to its labeled tuples. Thus 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, denoted f^{\mathcal I,u}, with outer weight \exp((-s'+\ii\Omega)(i_v-d)).

The following elementary fact controls its height.

Figure 1 shows why distinctness matters. Although one edge may contribute to several new parameters, it need pay for only one of their upper bounds.

Give each edge occurrence e its damping a_e>0. The damping of a merged gap is the sum of the a_e over all edges crossing it, and is therefore at least that of its assigned edge. Since 1+1/a decreases with a, Lemma 3.6 implies

The second inequality uses that all factors are at least one; the endpoint-link dampings are rb\ge b. This argument includes all overlaps between old tuples and also the case of a single distinct position. In that case the height is the empty product one.

Completing the multiscale estimate. Apply \Delta to the expanded product and use the integral representation for each interleaving. With \nu_{\mathcal I} denoting the corresponding measure, we have the exact identity

All estimates above are uniform over the interleavings. The integrands have a uniform bound even outside \mathcal U. Indeed, for each fixed endpoint j, the coefficients of f_j^{\mathcal I,u} have absolute sum at most the height in (3.28). The terms with endpoint j<d vanish under \Delta by prefix agreement. Using s'\ge b gives

In particular no exponential factor from negative distances occurs in the tail estimate.

Let N_{\mathrm{int}} be the number of interleavings and put V=2H_f^4(1+1/b)^4. Hypothesis (3.1), with a sufficiently large absolute C_0, ensures

Here \log(1+1/b) is bounded by an absolute constant plus \log(1/S'), because b=\beta S', S'\le1, and \beta has already been fixed. If every signal in (3.29) with u\in\mathcal U had magnitude below e^{-7.98E}, then (3.24) and (3.30) would give

This contradicts Lemma 3.5. Some interleaving and some u\in\mathcal U therefore give a feature with signal at least e^{-7.98E}. Its order is at most mk\le4k; (3.26) and the bounds on \mathcal U give the required outer parameters; (3.28) gives (3.3); and the crossing description gives the claimed parameter factors and (3.4). This completes the proof of Proposition 3.1.

4 From an input signal to separation of trace moments

We prove Theorem 2.2. Proposition 3.1 preserves a detectable input-coordinate signal while reducing its decay rate. We first choose enough scales to make that rate at most 1/n. The resulting gap parameters need not belong to the disk on which trace moments directly control the signal. A simultaneous one-variable continuation will bridge this difference.

Throughout this section 0<p<1, and q_*,Q,Y are as in (2.3). Recall from Section 2 that

4.1 A scale schedule and the surviving signal

Set

where the absolute integer H will be fixed below. In particular, D_*\le4^{H+1}Y^2. Fix an arbitrary positive moment functional of order 2D, where D\ge D_*, with first wrong position d, and let \Delta be its difference from evaluation at the true word, as in Section 2. All constants chosen below are independent of this system, n, and p.

For an absolute constant \eta>0, define

The linear regime of this recurrence brings D_*S_j below one; its quadratic regime then makes S_j small rapidly. Both regimes will also be used to control the arguments of the final gap parameters.

Choose an integer J_* with \alpha J_*\ge3, and set H=J_*+3. To verify the decrease precisely, write

Then t_j=\vartheta t_{j-1}\min\{1,t_{j-1}\}, so, regardless of when the quadratic regime begins,

once \eta is small enough. Require also

where \eta_0 is from Proposition 3.1. Now \log(1/\vartheta)\ge Q, and t_j\le1 for j\ge J_*. Iterating t_j=\vartheta t_{j-1}^2 in this range gives

The last inequality follows from 2^{h-J_*}\ge8Y and Q(Y-1)=\log n. At every transition we also have 0<S_j\le\min\{1,\eta_0S_{j-1}\}, as required by the proposition.

We need an upper bound on the cost of these small scales as well. Put A_0=Q+\log Y. The recurrence implies, with \ell_j=\max\{0,\log(1/S_j)\},

Consequently

We can now iterate Proposition 3.1. Begin with the order-one feature f_i^{(0)}=X_i, at decay s_0=4 and frequency zero. The prefix agreement gives \Delta[X_i]=0 for i<d, whereas \abs{\Delta[X_d]}=1. Since \abs{\Delta[X_i]}\le2 for every i,

Use error exponents

where C_5 is an absolute constant chosen after H and \eta.

Here are all the induction bounds. At stage j there is a feature f^{(j)} of order k_j\le4^j, with

The initial case follows from (4.6) and H_{f^{(0)}}=1, on increasing C_5. At the transition from j-1 to j, the degree requirement is

The feature-height conclusion of the proposition and (4.5) give

Summing this recurrence proves the last bound in (4.8). To check the exponent hypothesis of the proposition, its bracket at this transition is at most

Because \mu>4, the sequences j(4/\mu)^{j-1} and 2^j/\mu^{j-1} are bounded. Thus one fixed choice of C_5 makes this bracket times C_0 at most E_{j-1} for every j. All hypotheses of Proposition 3.1 hold, and its signal bound is e^{-\mu E_{j-1}}=e^{-E_j}.

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

4.2 Damping under multiplication

Call the parameters introduced between endpoints in each application of Proposition 3.1 elementary parameters. Include also the final outer parameter

An elementary parameter e^{-a+\ii\theta} introduced at stage j satisfies a\ge\beta S_j and \abs{\theta}\le C_1S_{j-1}. Using (4.3), choose a sufficiently small absolute c_2>0 so that all these parameters obey

For an explicit verification, the increasing function u\mapsto u\min\{1,D_*u\} changes by at most a factor \max\{C_1,C_1^2\} when u is replaced by C_1u. It therefore suffices to take c_2\le\beta\eta/\max\{C_1,C_1^2\}. Shrinking c_2 further covers z_0, since \abs{\omega}\le2.002s. Conjugating any elementary parameter preserves (4.9).

Each new inner gap contains 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; 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

In particular, an inner gap of f, even after multiplication by z_0, contains at most (4^h+2)/3\le D_* elementary factors.

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

4.3 The exact trace generating identity

Let z_1,\ldots,z_{k-1} denote the inner gap parameters of the final feature f. Define the polynomial in k complex variables

At the point

the exponents of z_0 telescope to i_k, so

Here sd\le nS_h\le1. Each coordinate of Z^* is a nonempty product of at most D_* elementary parameters, and hence Lemma 4.1 gives

We shall also need a bound on the coordinates’ collective proximity to the unit circle. If z_r=e^{-a_r+\ii\theta_r}, then

These inequalities follow from e^u\ge1+u for u>0. The height bound in (4.8) and (4.5) therefore imply

We next express the same polynomial in terms of observable trace moments on a different domain. This uses the multivariate trace generating identity of [9, Section 5.2]; see also [7, Fact 20]. We give the required counting argument directly. For a rank tuple \ell=(\ell_1,\ldots,\ell_k) with 1\le\ell_1<\cdots<\ell_k\le n, abbreviate T_\ell=T_{\{\ell_1,\ldots,\ell_k\}}. For u=(u_0,\ldots,u_{k-1})\in\CC^k, set

Then, with Z_r=q+pu_r, the exact polynomial identity is

To prove it, fix input positions i_1<\cdots<i_k that supply the specified retained bits. Their own retention contributes p^k. Every input position before i_1 contributes q+pu_0, according to whether it is deleted or retained; there are i_1-1 such positions. Similarly, the i_{r+1}-i_r-1 positions in the rth intervening gap each contribute q+pu_r. Positions after i_k contribute a total 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 in (4.10) with every displayed gap exponent reduced by one. Multiplication by \prod_rZ_r proves (4.14), including points where some Z_r=0.

Suppose, for the moment, that

where \varepsilon>0. Since k\le D_*, the rank sum has at most n^k terms, so \abs{G(u)}\le n^k\varepsilon when all \abs{u_r}\le1. On this polydisk \abs{Z_r}\le q+p=1. Thus (4.14) gives

This calculation uses only ordinary trace ranks and the convention that a rank product is zero when the trace is too short.

4.4 Simultaneous continuation and the separation bound

The lower bound (4.11) and the upper bound (4.16) concern different points. In Cayley coordinates the disk \abs{Z-q}\le p becomes a half-plane:

Indeed, writing w=(1+Z)/(1-Z) and expanding \abs{pw-(1+q)}^2\le p^2\abs{w+1}^2 reduces it to 4q\le4p\re w. We will move all coordinates to this half-plane using one complex variable. A single strip interpolation avoids incurring a separate continuation loss for every coordinate.

Write

where \xi_r,\zeta_r\in\RR. For v\in\CC set

Figure 2 shows how a common real value of v moves two possible starting coordinates into the trace half-plane. The proof uses the analytic maps (4.18) for complex v throughout a strip.

[t]

On the closed strip -1/2\le\re v\le R we have \re w_r(v)=(1+\re v)\xi_r>0, so all Z_r(v) lie in the unit disk and depend analytically on v. At v=0 they equal Z_r^*. On the right boundary,

and therefore (4.16) applies. Moreover

because \gamma=c_2q_*Y^{-\alpha} and q\le q_*.

We need a bound on the left boundary that does not involve n^k. The identity 1-\abs{Z}^2=4\re w/\abs{w+1}^2 gives, when \re v=-1/2,

To check the constant, first use 1-\abs{Z_r(v)}\ge \xi_r/\abs{w_r(v)+1}^2 and 1-\abs{Z_r^*}\le4\xi_r/\abs{w_r+1}^2. Then use

The coefficients of F have magnitude at most two. Summing independent geometric series over the positive prefix and gap lengths therefore gives, for every point in the open unit polydisk,

It follows from (4.20) that

has the boundary bounds

On the left, (1+\abs v)/\abs{2+v} is bounded by an absolute constant. On the right, \abs{2+v}\ge2+R>1. The function g is analytic and bounded on the strip: F is a finite polynomial evaluated in the unit polydisk, and \abs{2+v}\ge3/2.

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

At t=0 in our strip, the right boundary has weight 1/(2R+1). By (4.11), \log\abs{g(0)}\ge-E_h-1-2k\log2. Substituting (4.21) consequently gives

This is the desired quantitative transfer from input coordinates to trace coordinates.

It remains to compare the exponent with the budget in (1.1). Put t=\log_2\mu. The choices in (4.2) satisfy t+\alpha<3, and

Thus (4.19) yields

Also, since n\ge2 and \log(1/p)\le1/p,

Using (4.1), we conclude that the right-hand side of (4.22) is at most

Taking \varepsilon=e^{-C_{\mathrm{sep}}B(n,p)} with C_{\mathrm{sep}}>C_6 contradicts (4.22). Hence (4.15) fails for that \varepsilon, proving Theorem 2.2 with the cutoff (4.2).

All constants were fixed in the following order: those of Proposition 3.1; then J_*,H and \eta; then C_5,c_2; and finally C_{\mathrm{sep}}. There is no dependence on the denominator of p or on how close it 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 present in the budget. The case p=1 will be handled directly in the decoding argument.

5 A uniform decoder

Theorem 2.2 supplies a test for the first incorrect bit of a prefix: no moment system fixing that prefix can reproduce all the low-order trace statistics. To turn this statement into an algorithm, we must also recognize a correct prefix in bounded time. The useful additional fact is that a correct prefix admits a moment system with strict slack, both in its statistical constraints and in its positivity constraint. We first exhibit that slack, then give a rational procedure which is guaranteed to find a feasible system whenever such slack exists.

5.1 Statistical constraints for a prefix

Assume for now that p<1. Choose an integer D and a positive dyadic number \zeta=2^{-b_\zeta} such that

where C_{\mathrm{sep}} is the constant in Theorem 2.2. Integer formulas for these choices will be given below. Let

The number T is an integer. From T independent traces, form the empirical mean \widehat t_I of the rank observable defining T_I, for every I\in\mathcal I_D. These are observables of the ordinary trace: if a requested rank is absent, its observable is zero.

For each fixed input x, let \mathcal G be the event

Each observable takes values in \{0,1\}, so its empirical mean has variance at most 1/(4T). Chebyshev’s inequality and a union bound give

The same event will control all the prefix tests, even though the prefixes are chosen using the data.

For a proposed prefix, use the remaining sign variables and their moment matrix M(m)=\mathcal M_D(m) from (2.1). Its nonempty moment coordinates form a real vector m. Consider the rational constraints

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 1, by the coefficient bound for T_I in Section 2.

5.2 Finding a moment system with slack

The next lemma gives the bounded procedure needed for (5.4). It only promises to succeed when there is slack; every reported solution satisfies the exact inequalities. This distinction avoids any need to decide arbitrary instances of semidefinite feasibility. The procedure is a projected relaxation method for inequalities, in the tradition of Agmon and Motzkin–Schoenberg [1, 16]. We give the iteration and its rounding analysis explicitly.

For a prefix test, write each absolute-value constraint in (5.4) as two affine inequalities and apply Lemma 5.2. Lemma 5.1 verifies exactly the slack hypotheses for a correct prefix. Every acceptance, on any data, gives an actual moment system satisfying (5.4).

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 for data on which the statistical estimates fail. There are at most 2n tests.

5.3 Integer parameters and bit complexity

We now make the choices in (5.1) using only the binary input. This also accounts for the size of every list and every rational calculation in the decoder. Continue to assume p<1, and use q_*,Q,Y from (2.3). Define the positive integers

All logarithms appearing in these integer formulas 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. The rational maximum defining q_* is also found by an integer comparison.

The elementary comparisons

have absolute constants. For the asserted lower bound on y, use u\ge(\log n)/\log2 and v\le Q/\log2. Together with Y\asymp\mathsf X(n,p), these comparisons give

Choose fixed positive integers K_D,K_m, sufficiently large for the constants in Theorem 2.2, and set

Since D_*\le C Y^2 and B(n,p)\ge\log2, these choices ensure all of (5.1). The integers D,b_\zeta, in binary, are computable in time polynomial in the input bit lengths. Writing the denominator 2^{b_\zeta} subsequently costs O(b_\zeta) bits, which will be included in the bounds below.

We next describe how to form the rational constraints. For I=\{l_1<\cdots<l_k\} and i_1<\cdots<i_k, the coefficient of X_{i_1}\cdots X_{i_k} in T_I is

when all the gap counts are possible, and is zero otherwise. Indeed, the selected positions must be retained, and the prefix and successive open gaps must contain the indicated numbers of additional retentions. Positions after i_k are unrestricted. Formula (5.9) follows by multiplying these independent binomial probabilities.

If the input representation is p=a/b, every denominator in (5.9) divides b^n. Binomial coefficients have O(n) bits. Sign expansion adds a denominator dividing 2^D, and empirical means have denominator T. Consequently the constraint coefficients have polynomial bit length in n+L+D+\log T. Enumerating the rank and input tuples, then expanding the resulting bit monomials and substituting the prefix, constructs them directly. No list of complete trace masks is required.

All these enumerations fit the permitted resource scale. From D=O(Y^2), Y\asymp\mathsf X(n,p), and (1.1),

The rank list, every matrix basis, and every moment list have size at most (n+1)^{2D}=\exp(O(B(n,p))). Input tuple lists satisfy the same bound. A sign expansion has at most 2^D terms; products of these enumeration bounds remain \exp(O(B(n,p))). Subsets larger than the available number of positions are simply absent, so this statement includes D>n and prefixes with very few remaining positions.

By (5.1), the trace count T is \exp(O(B(n,p))). For every prefix, the iteration cap in Lemma 5.2 is bounded by

The bit length of its grid is O(b_\zeta+\log G+\log(1+l))=O(B(n,p)). The preceding coefficient bounds and that lemma therefore bound all computation by a fixed polynomial in

In particular, this includes the construction of parameters and constraints, exact rational arithmetic, and the at most 2n prefix tests.