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 \[ \begin{split} \mathsf X(n,p)&= \begin{cases} 1+\dfrac{\log n}{1+\log(1/q)},&q>0,\\[3pt] 1,&q=0, \end{cases}\\ B(n,p)&=p^{-1}(\log n)\mathsf X(n,p)^2 (1+\log\mathsf X(n,p))^6. \end{split} \tag{1}\]

For fixed \(p\), the budget in (1) is \(O_p((\log n)^3(1+\log\log n)^6)\) as \(n\to\infty\). Thus both resources in Theorem 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)\).

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 \[\exp\bigl(p^{-7/3}(\log_2n)^{c_0}\bigr)\] for an absolute \(c_0\), using nonlocal low-order statistics and a multiscale propagation argument [4]. This bound is quasipolynomial when \(p^{-1}\) is polylogarithmic in \(n\). Theorem 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]. 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]. 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.

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.

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.

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, \[T_I(X)=\sum_{i_1<\cdots<i_k} c_{I;i_1,\ldots,i_k}\,X_{i_1}\cdots X_{i_k},\] 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.

Positive moment arrays

The following Boolean moment relaxation is a specialization of the semidefinite moment and sum-of-squares frameworks of Lasserre [14] and Parrilo [18]. 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 \[ \mathcal M_D(m)= \bigl(m_{I\triangle J}\bigr)_{ I,J\subseteq U,\ |I|,|J|\le D}\succeq0. \tag{2}\] Only existing subsets are indexed; thus the definition also applies when \(D>|U|\) or \(U\) is empty.

The array defines a functional \(\mathcal E\) 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 \(\mathcal E[\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), 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 \[u_i=x_i\quad(i<d),\qquad u_d=1-x_d.\] For a positive moment functional fixing \(u\), write \[\Delta[P]=\mathcal E[P]-P(x).\] 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 gives \[ |\Delta[P]|\le2\sum_A |c_A| \quad\text{when }P=\sum_A c_A\prod_{i\in A}X_i. \tag{3}\]

For \(p<1\), introduce \[ q_* =\max(q,1/n),\qquad Q=1+\log(1/q_*),\qquad Y=1+\frac{\log n}{Q}. \tag{4}\] When \(q\ge1/n\), \(Y=\mathsf X(n,p)\). When \(q<1/n\), \(1\le\mathsf X(n,p)\le Y<2\). Hence \[\mathsf X(n,p)\le Y\le2\mathsf X(n,p),\qquad QY=Q+\log n\le C\log n\] 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.

Exponentially weighted tuple statistics

For the analytic proof, fix \(x,d,\mathcal E\) as above. For \(1\le k\le2D\), an order-\(k\) feature is a sequence of polynomials \[ f_j=\sum_{i_1<\cdots<i_k=j} X_{i_1}\cdots X_{i_k} \prod_{h=1}^{k-1}z_h^{i_{h+1}-i_h}, \qquad j\in[n], \tag{5}\] where \(z_h=\exp(-a_h+\mathrm i\theta_h)\), \(a_h>0\), and \(\theta_h\in\mathbb R\). For \(k=1\) this means \(f_j=X_j\). Put \[H_f=\prod_{h=1}^{k-1}(1+1/a_h).\] 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\mathbb R\), define its signal by \[ \mathcal S_f(s,\omega)= \sum_{j=1}^n\Delta[f_j]e^{(-s+\mathrm i\omega)(j-d)}. \tag{6}\] 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 (6). The purpose of the multiscale argument is to preserve a detectable signal while reducing \(s\) and \(|\omega|\), at the cost of increasing \(k\).

A Gaussian window and its logarithmic bound

Throughout the proof of Proposition 4, set \[ \sigma=\frac{K\sqrt E}{S'},\qquad W(l)=\exp\left(-\frac{l^2}{2\sigma^2}\right),\qquad b=\beta S', \tag{11}\] 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 (7) 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 \[C\left(1+k\log(2k)+\log H_f+\log\frac1{S'}\right)+C\log E,\] 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 \[ A(t)=\sum_{j=1}^n f_jW(j-d)e^{\mathrm it(j-d)},\qquad B_x(t)=A(t)(x). \tag{12}\] The coefficient bound for \(f_j\) and the Gaussian sum imply that \[ \lvert B_x(t)\rvert,\quad \lvert \mathcal E[A(t)]\rvert,\quad \lvert \Delta[A(t)]\rvert \le U:=C H_f(1+\sigma), \tag{13}\] with \(C\) absolute and chosen so that \(U\ge1\). By prefix cancellation, \[P(z):=\sum_{j=d}^n\Delta[f_j]W(j-d)z^{j-d} \quad\hbox{satisfies}\quad P(e^{\mathrm it})=\Delta[A(t)].\] We first show that \(P\) retains a signal at almost the original decay: \[ \lvert P(e^{-s_1+\mathrm i\omega})\rvert\ge\tfrac12e^{-E} \quad\hbox{for some}\quad \lvert s_1/s-1\rvert\le10^{-4}. \tag{14}\]

Let \(V\) be a centered real normal variable with variance \(\sigma^{-2}\). Since \(W(l)\mathbf E e^{Vl}=1\), \[\mathcal S_f(s,\omega)=\mathbf E\,P(e^{-s+V+\mathrm i\omega}).\] Write \(\delta=10^{-4}\). Exponential tilting gives \[W(l)\mathbf E\big[e^{Vl}\mathbf1_{\{\lvert V\rvert>\delta s\}}\big] =\Pr\!\left(\lvert N(l/\sigma^2,\sigma^{-2})\rvert>\delta s\right).\] 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 \(\lvert \Delta[f_j]\rvert\le2H_f\), the contribution from \(\lvert V\rvert>\delta s\) is at most \[ 2H_f(1+1/s)\left(2e^{-c\delta^2s^2\sigma^2} +e^{-\delta s^2\sigma^2/2}\right). \tag{15}\] 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 (15) less than \(e^{-2E}\). The integral over \(\lvert V\rvert\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 (14).

Set \[\Lambda(t)=\log\frac{U}{\lvert P(e^{\mathrm it})\rvert}\ge0,\] with value \(+\infty\) at a boundary zero. We claim \[ \int_{\mathbb R}\Lambda(t)\frac{s_1\,dt} {\pi(s_1^2+(t-\omega)^2)}\le1.001E. \tag{16}\] For completeness, the Cauchy Fourier transform is \[ \int_{\mathbb R}\frac{e^{\mathrm i\xi v}}{\pi(1+v^2)}\,dv=e^{-\lvert \xi\rvert}. \tag{17}\] For \(\xi>0\), close the contour in the upper half-plane and take the residue at \(\mathrm i\); for \(\xi<0\) use the lower half-plane, and for \(\xi=0\) integrate directly. Thus periodizing the density in (16) gives the circle Poisson measure at \(e^{-s_1+\mathrm i\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 \(\lvert e^{\mathrm it}-a\rvert=\lvert 1-\overline a e^{\mathrm it}\rvert\) and the inequality \[\lvert 1-\overline a z\rvert^2-\lvert z-a\rvert^2 =(1-\lvert a\rvert^2)(1-\lvert z\rvert^2)\ge0\] 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 \[\int_{\mathbb R}\Lambda(t)\frac{s_1\,dt}{\pi(s_1^2+(t-\omega)^2)} \le\log U-\log\lvert P(e^{-s_1+\mathrm i\omega})\rvert \le E+\log(2U).\] The last term is at most \(1.001E\) by the choice of \(C_0\), proving the claim.

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 \(\lvert \lambda\rvert\) may be much larger. The logarithmic estimate makes the required existence of pairs a question about pairing Cauchy mass.

A product with small total frequency

The window parameters satisfy \(\lvert \omega\rvert/s_1\le2.002/0.9999<2.003\), so Lemma 6 applies to our \(\Lambda\). Individual frequencies in (20) 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 6 have magnitude at most \(C_3S\). A product of one to four factors, each of the form \(A(t)\) or \(\overline{A(t)}\) with \(\lvert t\rvert\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 4.

Converting a balanced product to a feature

Lemma 8 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 4; the remaining issue will be to control the damping factors on their inner gaps.

Fix a product supplied by Lemma 8, 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 \[ \prod_{r=1}^m W(j_r-d)\exp\bigl(\mathrm it_r(j_r-d)\bigr), \qquad |t_r|\le C_3S,\qquad \left|\sum_{r=1}^m t_r\right|\le b. \tag{25}\] Conjugation also conjugates the old inner-gap parameters, leaving their dampings unchanged.

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 (33). 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 4.

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'+\mathrm i\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 9 implies \[\begin{align*} H_{f^{\mathcal I,u}} &\le\prod_{e\text{ assigned}}(1+1/a_e) \le\prod_{e\text{ present}}(1+1/a_e) \\ &\le H_f^m(1+1/b)^{m-1} \le H_f^4(1+1/b)^3. \tag{34}\end{align*}\] 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.

A scale schedule and the surviving signal

Set \[ \mu=7.98,\qquad \alpha=0.001,\qquad h=\lceil\log_2Y\rceil+H,\qquad D_*=4^h, \tag{38}\] 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 \[ S_0=4,\qquad S_j=\eta q_*Y^{-\alpha}S_{j-1} \min\{1,D_*S_{j-1}\}\quad(1\le j\le h). \tag{39}\] 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 \[\vartheta=\eta q_*Y^{-\alpha},\qquad t_j=D_*S_j.\] Then \(t_j=\vartheta t_{j-1}\min\{1,t_{j-1}\}\), so, regardless of when the quadratic regime begins, \[t_{J_*}\le \vartheta^{J_*}t_0 \le4^{H+2}\eta^{J_*}Y^{2-\alpha J_*}\le1\] once \(\eta\) is small enough. Require also \[\eta\le\min\{\eta_0,1/4,e^{-1}\},\] where \(\eta_0\) is from Proposition 4. 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 \[ t_h\le\vartheta^{\,2^{h-J_*}-1} \le \exp\{-Q(2^{h-J_*}-1)\}\le n^{-1}, \qquad S_h\le n^{-1}. \tag{40}\] 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)\}\), \[\ell_j\le2\ell_{j-1}+\log(1/\vartheta),\qquad \ell_0=0,\qquad \log(1/\vartheta)\le C A_0.\] Consequently \[ \log(1/S_j)\le C2^jA_0\quad(0\le j\le h). \tag{41}\]

We can now iterate Proposition 4. 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 \(\lvert \Delta[X_d]\rvert=1\). Since \(\lvert \Delta[X_i]\rvert\le2\) for every \(i\), \[ \lvert \mathcal S_{f^{(0)}}(4,0)\rvert \ge1-2\sum_{r\ge1}e^{-4r} =1-\frac{2}{e^4-1}>\frac12. \tag{42}\] Use error exponents \[ E_j=C_5A_0\mu^j\quad(0\le j\le h), \tag{43}\] 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 \[ \begin{gathered} \beta S_j\le s_j\le S_j, \qquad \lvert \omega_j\rvert\le2.002s_j, \qquad \lvert \mathcal S_{f^{(j)}}(s_j,\omega_j)\rvert\ge e^{-E_j},\\ \log H_{f^{(j)}}\le C4^jA_0. \end{gathered} \tag{44}\] The initial case follows from (42) and \(H_{f^{(0)}}=1\), on increasing \(C_5\). At the transition from \(j-1\) to \(j\), the degree requirement is \[4k_{j-1}\le4^j\le D_*\le D.\] The feature-height conclusion of the proposition and (41) give \[\log H_{f^{(j)}} \le4\log H_{f^{(j-1)}} +3\log\bigl(1+1/(\beta S_j)\bigr) \le4\log H_{f^{(j-1)}}+C2^jA_0.\] Summing this recurrence proves the last bound in (44). To check the exponent hypothesis of the proposition, its bracket at this transition is at most \[C\bigl(1+j4^{j-1}+4^{j-1}A_0+2^jA_0\bigr).\] 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 4 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.

Damping under multiplication

Call the parameters introduced between endpoints in each application of Proposition 4 elementary parameters. Include also the final outer parameter \[z_0=e^{-s+\mathrm i\omega}.\] An elementary parameter \(e^{-a+\mathrm i\theta}\) introduced at stage \(j\) satisfies \(a\ge\beta S_j\) and \(\lvert \theta\rvert\le C_1S_{j-1}\). Using (39), choose a sufficiently small absolute \(c_2>0\) so that all these parameters obey \[ a\ge\gamma\min\{\lvert \theta\rvert,D_*\theta^2\}, \qquad \gamma=c_2q_*Y^{-\alpha}\le1. \tag{45}\] 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 \(\lvert \omega\rvert\le2.002s\). Conjugating any elementary parameter preserves (45).

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 \[N_0=0,\qquad N_j\le4N_{j-1}+1, \qquad N_j\le\frac{4^j-1}{3}.\] 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.

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 \[ F(Z_0,\ldots,Z_{k-1}) =\sum_{1\le i_1<\cdots<i_k\le n} \Delta\left[\prod_{r=1}^kX_{i_r}\right] Z_0^{i_1}\prod_{r=1}^{k-1}Z_r^{i_{r+1}-i_r}. \tag{46}\] At the point \[Z_0^*=z_0,\qquad Z_r^*=z_rz_0\quad(1\le r<k),\] the exponents of \(z_0\) telescope to \(i_k\), so \[ F(Z^*)=z_0^d\mathcal S_f(s,\omega), \qquad \lvert F(Z^*)\rvert\ge e^{-E_h-1}. \tag{47}\] Here \(sd\le nS_h\le1\). Each coordinate of \(Z^*\) is a nonempty product of at most \(D_*\) elementary parameters, and hence Lemma 10 gives \[ \mathop{\mathrm{Re}}\frac{1+Z_r^*}{1-Z_r^*}\ge c_3\gamma\quad(0\le r<k). \tag{48}\] We shall also need a bound on the coordinates’ collective proximity to the unit circle. If \(z_r=e^{-a_r+\mathrm i\theta_r}\), then \[\frac1{1-\lvert Z_r^*\rvert} \le1+\frac1{a_r+s}\le1+\frac1{a_r}\quad(r\ge1), \qquad \frac1{1-\lvert Z_0^*\rvert}\le1+\frac1s.\] These inequalities follow from \(e^u\ge1+u\) for \(u>0\). The height bound in (44) and (41) therefore imply \[ W_*:=\log\prod_{r=0}^{k-1}\frac1{1-\lvert Z_r^*\rvert} \le\log H_f+\log\bigl(1+1/(\beta S_h)\bigr) \le C4^h A_0. \tag{49}\]

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]; see also [7]. 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\mathbb C^k\), set \[G(u)=\sum_{1\le\ell_1<\cdots<\ell_k\le n} \Delta[T_\ell]\, u_0^{\ell_1-1} \prod_{r=1}^{k-1}u_r^{\ell_{r+1}-\ell_r-1}.\] Then, with \(Z_r=q+pu_r\), the exact polynomial identity is \[ \left(\prod_{r=0}^{k-1}Z_r\right)G(u)=p^kF(Z). \tag{50}\] 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 \(r\)th 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 (46) with every displayed gap exponent reduced by one. Multiplication by \(\prod_rZ_r\) proves (50), including points where some \(Z_r=0\).

Suppose, for the moment, that \[ \lvert \Delta[T_I]\rvert\le\varepsilon \quad\text{for every }I\subseteq\{1,\ldots,n\} \text{ with }1\le\lvert I\rvert\le D_*, \tag{51}\] where \(\varepsilon>0\). Since \(k\le D_*\), the rank sum has at most \(n^k\) terms, so \(\lvert G(u)\rvert\le n^k\varepsilon\) when all \(\lvert u_r\rvert\le1\). On this polydisk \(\lvert Z_r\rvert\le q+p=1\). Thus (50) gives \[ \lvert F(Z)\rvert\le (n/p)^k\varepsilon \qquad\text{if }\lvert Z_r-q\rvert\le p\quad(0\le r<k). \tag{52}\] This calculation uses only ordinary trace ranks and the convention that a rank product is zero when the trace is too short.

Simultaneous continuation and the separation bound

The lower bound (47) and the upper bound (52) concern different points. In Cayley coordinates the disk \(\lvert Z-q\rvert\le p\) becomes a half-plane: \[ \lvert Z-q\rvert\le p \quad\Longleftrightarrow\quad \mathop{\mathrm{Re}}\frac{1+Z}{1-Z}\ge\frac qp \qquad(\lvert Z\rvert<1). \tag{53}\] Indeed, writing \(w=(1+Z)/(1-Z)\) and expanding \(\lvert pw-(1+q)\rvert^2\le p^2\lvert w+1\rvert^2\) reduces it to \(4q\le4p\mathop{\mathrm{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 \[w_r=\frac{1+Z_r^*}{1-Z_r^*}=\xi_r+\mathrm i\zeta_r, \qquad \xi_r\ge c_3\gamma,\] where \(\xi_r,\zeta_r\in\mathbb R\). For \(v\in\mathbb C\) set \[ w_r(v)=(1+v)\xi_r+\mathrm i\zeta_r, \qquad Z_r(v)=\frac{w_r(v)-1}{w_r(v)+1}, \qquad R=1+\frac{q}{pc_3\gamma}. \tag{54}\] 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 (54) for complex \(v\) throughout a strip.

On the closed strip \(-1/2\le\mathop{\mathrm{Re}}v\le R\) we have \(\mathop{\mathrm{Re}}w_r(v)=(1+\mathop{\mathrm{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, \[\mathop{\mathrm{Re}}w_r(v)=(1+R)\xi_r\ge q/p,\] and therefore (52) applies. Moreover \[ 1+R\le C\frac{Y^\alpha}{p}, \tag{55}\] 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-\lvert Z\rvert^2=4\mathop{\mathrm{Re}}w/\lvert w+1\rvert^2\) gives, when \(\mathop{\mathrm{Re}}v=-1/2\), \[ 1-\lvert Z_r(v)\rvert \ge\frac{1-\lvert Z_r^*\rvert}{4(1+\lvert v\rvert)^2}. \tag{56}\] To check the constant, first use \(1-\lvert Z_r(v)\rvert\ge \xi_r/\lvert w_r(v)+1\rvert^2\) and \(1-\lvert Z_r^*\rvert\le4\xi_r/\lvert w_r+1\rvert^2\). Then use \[\lvert w_r(v)+1\rvert\le\lvert w_r+1\rvert+\xi_r\lvert v\rvert \le(1+\lvert v\rvert)\lvert w_r+1\rvert.\] 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, \[\lvert F(Z)\rvert\le2\prod_{r=0}^{k-1}\frac1{1-\lvert Z_r\rvert}.\] It follows from (56) that \[g(v):=\frac{F(Z_0(v),\ldots,Z_{k-1}(v))}{(2+v)^{2k}}\] has the boundary bounds \[ \begin{aligned} \log\lvert g(v)\rvert&\le W_*+Ck+C &&(\mathop{\mathrm{Re}}v=-1/2),\\ \log\lvert g(v)\rvert&\le k\log(n/p)+\log\varepsilon &&(\mathop{\mathrm{Re}}v=R). \end{aligned} \tag{57}\] On the left, \((1+\lvert v\rvert)/\lvert 2+v\rvert\) is bounded by an absolute constant. On the right, \(\lvert 2+v\rvert\ge2+R>1\). The function \(g\) is analytic and bounded on the strip: \(F\) is a finite polynomial evaluated in the unit polydisk, and \(\lvert 2+v\rvert\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\mathop{\mathrm{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 (47), \(\log\lvert g(0)\rvert\ge-E_h-1-2k\log2\). Substituting (57) consequently gives \[\begin{align*} \log(1/\varepsilon) &\le k\log(n/p)+(2R+1)(E_h+1+2k\log2) +2R(W_*+Ck+C)\\ &\le k\log(n/p) +C(1+R)\bigl(E_h+4^hA_0\bigr). \tag{58}\end{align*}\] This is the desired quantitative transfer from input coordinates to trace coordinates.

It remains to compare the exponent with the budget in (1). Put \(t=\log_2\mu\). The choices in (38) satisfy \(t+\alpha<3\), and \[4^h\le CY^2,\qquad E_h\le CA_0Y^t, \qquad A_0\le Q(1+\log Y),\qquad QY\le C\log n.\] Thus (55) yields \[\begin{align*} (1+R)E_h &\le \frac Cp(\log n)Y^{t+\alpha-1}(1+\log Y) \le \frac Cp(\log n)Y^2(1+\log Y),\\ (1+R)4^hA_0 &\le \frac Cp(\log n)Y^{1+\alpha}(1+\log Y) \le \frac Cp(\log n)Y^2(1+\log Y). \end{align*}\] Also, since \(n\ge2\) and \(\log(1/p)\le1/p\), \[k\log(n/p)\le CY^2\bigl(\log n+\log(1/p)\bigr) \le \frac Cp(\log n)Y^2.\] Using (37), we conclude that the right-hand side of (58) is at most \[ \frac Cp(\log n)Y^2(1+\log Y) \le C_6 p^{-1}(\log n)\mathsf X(n,p)^2 (1+\log\mathsf X(n,p))^6 =C_6B(n,p). \tag{59}\] Taking \(\varepsilon=e^{-C_{\mathrm{sep}}B(n,p)}\) with \(C_{\mathrm{sep}}>C_6\) contradicts (58). Hence (51) fails for that \(\varepsilon\), proving Theorem 3 with the cutoff (38).

All constants were fixed in the following order: those of Proposition 4; 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.

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 \[ D_*\le D\le C Y^2,\qquad \zeta\le \tfrac14,\qquad 4\zeta<e^{-C_{\mathrm{sep}}B(n,p)},\qquad b_\zeta=O(B(n,p)), \tag{60}\] where \(C_{\mathrm{sep}}\) is the constant in Theorem 3. Integer formulas for these choices will be given below. Let \[\mathcal I_D=\{I\subseteq\{1,\ldots,n\}:1\le |I|\le D\}, \qquad N=|\mathcal I_D|, \qquad T=512(1+N)\zeta^{-2}.\] 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 \[ |\widehat t_I-T_I(x)|\le \zeta/8 \quad\text{for every }I\in\mathcal I_D. \tag{61}\] 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 \[ \mathbb P_x(\mathcal G^c) \le \frac{16N}{T\zeta^2}\le\frac1{32}. \tag{62}\] 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). Its nonempty moment coordinates form a real vector \(m\). Consider the rational constraints \[ m\in[-1,1]^l,\qquad M(m)\succeq0,\qquad |\mathcal E_m[T_I]-\widehat t_I|\le\zeta \quad(I\in\mathcal I_D), \tag{63}\] 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 \(\mathcal E_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.

Finding a moment system with slack

The next lemma gives the bounded procedure needed for (63). 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 (63) as two affine inequalities and apply Lemma 12. Lemma 11 verifies exactly the slack hypotheses for a correct prefix. Every acceptance, on any data, gives an actual moment system satisfying (63).

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.

Integer parameters and bit complexity

We now make the choices in (60) 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 (4). Define the positive integers \[\begin{align*} u&=1+\lceil\log_2 n\rceil, &v&=1+\lfloor\log_2(1/q_*)\rfloor,\\ y&=1+\lceil u/v\rceil, &w&=1+\lceil\log_2 y\rceil, &a_p&=\lceil1/p\rceil. \end{align*}\] All logarithms 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 \[u\asymp\log n,\qquad v\asymp Q,\qquad Y\le y\le C Y,\qquad w\asymp1+\log Y,\qquad p^{-1}\le a_p\le2p^{-1}\] 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 \[ B(n,p)\le a_pu y^2w^6\le C B(n,p). \tag{66}\] Choose fixed positive integers \(K_D,K_m\), sufficiently large for the constants in Theorem 3, and set \[ D=K_Dy^2,\qquad b_\zeta=K_m a_pu y^2w^6,\qquad \zeta=2^{-b_\zeta}. \tag{67}\] Since \(D_*\le C Y^2\) and \(B(n,p)\ge\log2\), these choices ensure all of (60). 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 \[ \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}, \tag{68}\] 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 (68) follows by multiplying these independent binomial probabilities.

If the input representation is \(p=a/b\), every denominator in (68) 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), \[ D\log n=O(B(n,p)). \tag{69}\] 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 (60), the trace count \(T\) is \(\exp(O(B(n,p)))\). For every prefix, the iteration cap in Lemma 12 is bounded by \[2560(1+l)G^2\zeta^{-2}+1=\exp(O(B(n,p))).\] 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 \[ n+L+\exp(O(B(n,p))). \tag{70}\] In particular, this includes the construction of parameters and constraints, exact rational arithmetic, and the at most \(2n\) prefix tests.