History and comparison with earlier results

Reconstructing a sequence from repeated corrupted observations has a long history. Levenshtein studied both combinatorial and memoryless channel formulations (Levenshtein 2001). Batu, Kannan, Khanna, and McGregor studied the independent-deletion trace problem in connection with multiple sequence alignment and outlined a linear sample obstruction at fixed deletion probability (Batu et al. 2004, sec. 4.2). Later lower bounds for complete traces focused on the difficulty of locating a small discrepancy within a long background. McGregor, Price, and Vorotnikova analyzed neighboring positions of a single one among zeros, using Hellinger distance and common mass (McGregor et al. 2014). Holden and Lyons used a defect in an alternating background to prove \(\Omega(n^{5/4}/\sqrt{\log n})\) (Holden and Lyons 2020, 2022), and Chase obtained \(\Omega(n^{3/2}/\log^7 n)\) by a direct Hellinger calculation for a related pair (Chase 2021a). The displayed Holden–Lyons and Chase rates fix the channel and a reconstruction success greater than \(1/2\). Our seed starts from the periodic defect family used by Chase and makes signed choices across many periods; it also supplies the overlap and score estimates needed for repeated amplification.

For fixed deletion probability, Holenstein, Mitzenmacher, Panigrahy, and Wieder obtained a worst-case upper bound of \(\exp(\widetilde O(\sqrt n))\) (Holenstein et al. 2008), where \(\widetilde O\) suppresses polylogarithmic factors. Independently, De, O’Donnell, and Servedio and Nazarov and Peres improved it to \(\exp(O(n^{1/3}))\) (De et al. 2017; Nazarov and Peres 2017), and Chase obtained \(\exp(O(n^{1/5}\log^5 n))\) (Chase 2021b). The 2026 preprint of Burudgunte, Valiant, and Wang gives \(\exp(p^{-7/3}(\log_2 n)^{C_0})\) samples for a universal constant \(C_0\) and every positive retention probability \(p=1-q\) (Burudgunte et al. 2026). At fixed \(p\) this is a quasipolynomial sample upper bound; the cited preprint does not give a quasipolynomial-time reconstruction algorithm. The logarithm of this sample bound is a fixed power of \(\log n\), whereas the logarithm of our lower bound at a fixed channel has order \((\log n)(\log\log n)\), leaving a gap between the rates. The companion paper Uniform quasipolynomial-time trace reconstruction proves such a time bound for every fixed known rational retention probability (OpenAI 2026).

Polynomial reconstruction remains possible under other channel or input conditions. For every fixed \(\varepsilon>0\), Chen, De, Lee, Servedio, and Sinha give reconstruction in polynomial time when \(q\le n^{-1/3-\varepsilon}\), using \(O(n^{4/3})\) traces (Chen et al. 2021). Those deletion probabilities lie outside the regime \(q^3\log n\to\infty\) of Theorem 1. Aamand, Liu, and Narayanan prove polynomial reconstruction when the internal zero gaps between successive ones have length at least a sufficiently large constant times \((\log n)^8\) and the deletion probability is at most a sufficiently small universal constant (Aamand et al. 2025).

Some lower bounds restrict the available statistics. De, O’Donnell, and Servedio measure the precision required of an oracle returning an \(\ell^1\) approximation to the expected trace vector padded with zeros, while Nazarov and Peres study repeated observations of one fixed output coordinate (De et al. 2017; Nazarov and Peres 2017). Chen, De, Lee, and Servedio study a tolerance oracle for functions of contiguous blocks of trace coordinates (Chen et al. 2024). Their lower bounds concern those specified statistics. A different input model is studied by Rivkin, Valiant, and Valiant: the input is a fixed probability vector, with fresh Bernoulli bits drawn from it before each trace. For deletion probability at least a constant times \(n^{-1/2}\), their generalized trace laws can have total variation \(\exp(-\Omega(\sqrt n))\) (Rivkin et al. 2025). Their arguments using translated segments and cancellation are related to the observation constructed in Section 6. Theorems 1 and 2 concern the entire trace law of one deterministic binary word.

Mechanism and proof structure

Our construction hides differences in location at several scales. The basic source of hidden randomness is exact common mass. If trace laws for \(k\) and \(k+1\) copies of a word share mass \(\omega\), place such a pair of runs on opposite sides of a central segment and choose their orientation by a fair bit. Their joint trace laws share a product component of mass \(\omega^2\). On that component the orientation remains fair even after the side outputs are reported. Many independent pairs therefore leave a binomial uncertainty in the position of the central segment. Marginalizing the flags restores the product of the two side trace laws for each orientation. Concatenating independent genuine traces of a partition of the fixed word then recovers its trace law exactly. At later scales the preliminary observation uses earlier auxiliary outputs at its leaves and allows rare failed layouts; at every scale, conditioning to obtain likelihood domination adds a small change. The resulting auxiliary laws therefore have an approximate common projection to genuine traces, with all these losses recorded in the invariant.

The two words use complementary signed patterns in their central segments. The generating polynomial of a Prouhet–Thue–Morse pattern vanishes to high order at \(1\) (Allouche and Shallit 1999, Proposition 2 and Theorem 6), making its convolution with a broad binomial offset small. The same dyadic sign recursion is used by Holenstein et al. (2008, sec. 3.2, equation (3.10)) to produce iterated finite differences of a kernel for coordinate means. In the conditional likelihood difference, each selected leaf set indexes a product of old likelihood scores, one per leaf, multiplied by a coefficient. We expand this coefficient along the tree of nested segments as a sum of expected products of signed motif factors and support indicators, averaging over the hidden bits. Within one product, a child is active at a vertex when it supplies one of these local factors, and the term is odd there when an odd number of the local factors are signed. The complementary words give root types \(+1\) and \(-1\), so subtracting the two root evaluations cancels every even root term. At a vertex where an odd term has only one active child, the hidden offset smooths its single local signed factor. For an odd root term with no such singleton, selecting two active children recursively produces a forced binary subtree with \(2^b\) selected leaves at depth \(b\), and hence at least \(2^b\) factors from the old score. A shared displacement for each sibling group, together with independent local displacements for its members, spreads these descendant locations. A joint bound that retains the shared displacement gives the extra decay beyond the factors from the old score.

The argument has three quantitative requirements. The initial pair must work uniformly as \(q\) decreases. The number of amplification blocks grows with \(n\), so constants depending on the channel or cancellation order must remain below the available scale margins. Finally, every oracle conditioning and failed random layout must be charged to an error that remains negligible after taking many traces.

Section 2 states the oracle invariant and the global schedule with two phases. Section 3 proves the common-mass, moment, and clipping tools, and Section 4 constructs the seed at the working channel. Section 5 chooses the local word and window sizes and proves the overlap estimates. Section 6 defines the random observation, proves its projection to a genuine trace, and identifies the law of the hidden bits after the report. Section 7 then proves the gain from the forced binary subtree and closes the induction. Section 8 restores genuine traces, pads to every exact length, and proves both main theorems. The extension to arbitrary fixed positive success uses several independently chosen gadgets and posterior factorization.

Distances and channel reduction

For probability laws \(P,Q\), define overlap by \(\mathop{\mathrm{ov}}(P,Q)=1-\mathop{\mathrm{TV}}(P,Q)\), the largest mass of a common subprobability. Our squared Hellinger distance is \[H^2(P,Q)=\int(\sqrt{dP}-\sqrt{dQ})^2.\] Cauchy–Schwarz and Hellinger affinity give \(\mathop{\mathrm{TV}}(P,Q)\le H(P,Q)\le\sqrt{2\mathop{\mathrm{TV}}(P,Q)}\). Both distances decrease under a common stochastic kernel, and squared Hellinger distance of product laws is at most the sum for the factors. If \(Q\ll P\), then \[H^2(P,Q)\le\int\left(\frac{dQ}{dP}-1\right)^2dP.\] These elementary inequalities also explain why a small likelihood score is an appropriate induction quantity.

For the rest of the proof put \[\delta=\min(q,1/2),\qquad \Lambda=\delta^{-3},\qquad H_{\rm del}=\delta^3\log n.\] We use \(\mathrm{Tr}(w)=\mathcal D_\delta(w)\) throughout the construction. The requested channel \(q\) is obtained by deleting each surviving bit of a \(\delta\)-trace with additional probability \((q-\delta)/(1-\delta)\). Thus all upper bounds on distinguishability proved at \(\delta\) also hold at \(q\). Moreover \[H_{\rm del}\to\infty,\qquad \log H_{\rm del}=\log(q^3\log n)+O(1).\] The working deletion rate \(\delta\) remains fixed through every intermediate scale of an instance. In all integer index ranges, endpoints may be real and only integer labels in the range are used.

Paired hiding and the reported information

The paired construction below uses a joint common component of mass \(\omega^2\); on this component, the orientation remains fair conditional on the flag and both reported side outputs. Common-part constructions appear in the average-case block argument of McGregor et al. (2014, sec. 3.3) and the partial-trace construction in the proof of Holden and Lyons (2020, Lemma 2.1).

Figure 1 depicts one pair and the resulting uncertainty in the number of copies to the left of the central segment.

Throughout, unless window boundaries or additional payloads are specified explicitly, report only one unseparated output per segment/chunk/residual, plus flags and revealed orientation bits as indicated (not original word boundaries internal to that output). Given a word \(w\) and a count \(k\) with \(\mathop{\mathrm{ov}}(\mathrm{Tr}(w^k),\mathrm{Tr}(w^{k+1}))\ge\omega\), choose a common sublaw \(\omega U\). Two chunks use a paired random bit orientation giving lengths \((k,k+1)\) or \((k+1,k)\) even when far separated in the concatenation. Use one joint flag of probability \(\omega^2\) and output from \(U\otimes U\) on it, otherwise reveal the bit and generate the two traces jointly from the normalized residual after subtracting \(\omega^2 U\otimes U\) from the product law for that orientation. Marginalizing flags yields the requisite conditionally independent pair traces given orientations. Conditional on the augmented pair data, the bit remains fair on the hidden event. Independent pairs thus carry independent hidden fair bits conditional on this part of the report. All auxiliary schedules/flags are redrawn independently for each trace.

Conditioning to obtain a small likelihood score

Separating a typical region from a small exceptional mass is also used in Hellinger estimates for trace reconstruction (Chase 2021a, arXiv v2, Section 2). The following version keeps the full moment and simulation-error budgets.

Words and the reported mark lists

In this section \(C_*,c_*>0\) denote absolute constants whose values may change between estimates; constants indexed by \(r\) or \(s_0\) may depend on those fixed indices.

Put \(N=N_0\), \(\eta=.004\), and \[m=\lfloor N^{1/2-\eta}\rfloor,\qquad K=\lfloor N^{1/2-2\eta}\rfloor,\qquad k=\lfloor\delta m\rfloor,\] \[J=\left\lfloor \frac{\lfloor N/(2m-1)\rfloor-K}{2k+1} \right\rfloor,\qquad P=J(2k+1)+K.\] Lemma 3 gives \(\Lambda=o(\log N)\), hence \(\delta^{-1}=N^{o(1)}\). In particular \(\delta^3m\to\infty\), \(m\delta^2\to\infty\), and \(K,k+1\le m\) for all sufficiently large instances. The definitions then give \[J\asymp\delta^{-1}N^{2\eta},\qquad J=o(K),\qquad P(2m-1)\in[N/2,N].\] For the last assertion, \(P\) differs from \(\lfloor N/(2m-1)\rfloor\) by fewer than \(2k+1\), so the omitted length is \(O(km+m)=o(N)\).

For this construction only, let the ordinary block be \(\mathsf A=01\) and the defect block be \(\mathsf D=1\). For \(b\in\{-1,0,1\}\), define the period \[W_b=\mathsf A^{\lfloor m/2\rfloor+b-1}\, \mathsf D\, \mathsf A^{m-\lfloor m/2\rfloor-b}.\] It has \(m\) blocks, with the defect at block position \(\lfloor m/2\rfloor+b\), and length \(2m-1\). Period, slot, and rank indices in this section start at \(1\). For even \(m\), the adjacent types \(W_0,W_1\) are exactly the shifted-defect pair displayed by Chase (2021a, arXiv v2, Introduction and Theorem 1); for odd \(m\), they are the corresponding smaller pair with one common final \(\mathsf A\) appended. Below we compare \(W_{-1}\) with \(W_1\) in exceptional periods and make signed choices across many periods.

Set \[\begin{gathered} a=\lfloor P/2\rfloor,\qquad s_0=300,\qquad I=\{0,\ldots,2^{s_0}-1\},\\ \sum_{i\in I}\beta_i z^i=\prod_{v=0}^{s_0-1}(1-z^{2^v}). \end{gathered}\] The two words \(x_0,y_0\) have \(P\) periods. Every period is \(W_0\) except those at \(a+i\), \(i\in I\), where \(x_0\) uses \(W_{\beta_i}\) and \(y_0\) uses \(W_{-\beta_i}\). For all sufficiently large instances these indices lie in \(\{1,\ldots,P\}\). Both words have length \(\ell_0=P(2m-1)\in[N/2,N]\), and they differ: the parse into \(01\) and \(1\) from the left is unique. The signs are the classical Prouhet–Thue–Morse signs; their polynomial has a zero of order \(s_0\) at \(1\) (Allouche and Shallit 1999, Proposition 2 and Theorem 6).

We now define the more informative observation used only at this level. For \(H\in\{\mathsf A,\mathsf D\}\), put \[r_e=\delta^2/2,\qquad \nu_H=\frac{\mathrm{Tr}(H)-r_e\delta_\varnothing}{1-r_e},\] where \(\varnothing\) denotes the empty string. This reserves the same empty output mass in both block laws. In the proof of Lemma 2.1, steps (I) and (III), Holden and Lyons (2020) first erase a mass \(q^2/2\) from \(01\) blocks at their deletion rate \(q\); here the same decomposition is applied at rate \(\delta\) to both \(01\) and \(1\), followed by an explicit likelihood score.

For each block independently, silently erase it with probability \(r_e\); otherwise report a mark with law \(\nu_H\). The mark alphabet is \[\mathcal M_{\rm mark}=\{\varnothing,0,1,01\}.\] An observation on a sequence of blocks is the ordered list of its returning marks, an element of \(\bigsqcup_{l\ge0}\mathcal M_{\rm mark}^l\). The list reports its individual entries, including empty-valued entries, but no original slot labels or period boundaries. Thus the empty list and the one-entry list \((\varnothing)\) are distinct. Its count \(l\) is the number of entries, not the number of bits in their concatenation. Concatenating the mark strings gives the ordinary trace law, since \(\mathrm{Tr}(H)=r_e\delta_\varnothing+(1-r_e)\nu_H\).

Under \(\nu_{\mathsf A}\), define \[Z(Y)=\frac{\nu_{\mathsf D}(Y)}{\nu_{\mathsf A}(Y)}-1.\] The defect law is dominated by the ordinary-block law. Its support is contained in \(\{\varnothing,1\}\), where the likelihood ratios are \[\frac{\delta-\delta^2/2}{\delta^2/2} \quad\text{and}\quad \frac1\delta,\] respectively. Hence \(Z\) is centered, \(\|Z\|_\infty=O(\delta^{-1})\), and \(\|Z\|_{L^2(\nu_{\mathsf A})}^2\lesssim\delta^{-1}\), uniformly for \(\delta\le1/2\).

Conditional densities and the rank kernel

Consider \(1\le u\le m\) periods with fixed types \(\mathbf b=(b_1,\ldots,b_u)\in\{-1,0,1\}^u\). There are \(n_b=um\) slots, and the defect in period \(j\) is at \[p_{\mathbf b}(j)=(j-1)m+\lfloor m/2\rfloor+b_j.\] The return count has law \(\operatorname{Bin}(n_b,1-r_e)\), independent of \(\mathbf b\). Conditional on any count \(0\le l\le n_b\), the returning subset \(S_l\) is uniform among the size-\(l\) subsets of \(\{1,\ldots,n_b\}\). This subset is not reported. If \(p\in S_l\), let \(\operatorname{rk}_{S_l}(p)\) be its rank in the increasing order on \(S_l\). Put \(Q_l=\nu_{\mathsf A}^{\otimes l}\), with \(Q_0\) the point mass on the empty list.

Relative to \(Q_l\), the density of the reported list \(Y=(Y_1,\ldots,Y_l)\) is \[ G_{\mathbf b}^{(u,l)}(Y) =\mathbb E_{S_l} \prod_{\{j:p_{\mathbf b}(j)\in S_l\}} \bigl(1+Z(Y_{\operatorname{rk}_{S_l}(p_{\mathbf b}(j))})\bigr). \tag{9}\] Empty products are \(1\), so this also defines the density at \(l=0\). It integrates to one because each \(1+Z\) has mean one under \(\nu_{\mathsf A}\). To expand it, for \(1\le r\le u\) take an increasing tagged tuple \(\mathbf j=(j_1,\ldots,j_r)\) of periods and an increasing rank tuple \(1\le v_1<\cdots<v_r\le l\). Write \(p_h=p_{\mathbf b}(j_h)\), and put \[ \begin{split} W_{\mathbf j,\mathbf b}(v) &=\mathbb P\bigl\{ p_h\in S_l,\ \operatorname{rk}_{S_l}(p_h)=v_h \text{ for every }h \bigr\},\\ A_{r,\mathbf b}(v)&=\sum_{1\le j_1<\cdots<j_r\le u} W_{\mathbf j,\mathbf b}(v). \end{split} \tag{10}\] The event in \(W_{\mathbf j,\mathbf b}\) imposes no restriction on untagged slots, including other defects. It is the joint probability of the tagged returns and ranks within the count conditioning, rather than a rank law conditioned again on all tags returning. Expanding the product in (9) now gives \[ G_{\mathbf b}^{(u,l)}(Y) =1+\sum_{r=1}^{u}\ \sum_{1\le v_1<\cdots<v_r\le l} A_{r,\mathbf b}(v)\prod_{h=1}^r Z(Y_{v_h}). \tag{11}\]

Define the slot gaps and rank gaps by \[\begin{aligned} (g_0,\ldots,g_r) &=(p_1-1,p_2-p_1-1,\ldots,p_r-p_{r-1}-1,n_b-p_r),\\ (z_0,\ldots,z_r) &=(v_1-1,v_2-v_1-1,\ldots,v_r-v_{r-1}-1,l-v_r). \end{aligned}\] Their sums are \(n_b-r\) and \(l-r\). Put \(\theta=l/n_b\) and \(f_g(z)=\mathbb P\{\operatorname{Bin}(g,\theta)=z\}\). Counting returning untagged slots in each gap gives the exact kernel \[ \begin{aligned} W_{\mathbf j,\mathbf b}(v) &=\frac{\prod_{i=0}^{r}\binom{g_i}{z_i}}{\binom{n_b}{l}}\\ &=\frac{\theta^r}{f_{n_b}(l)} \prod_{i=0}^{r}f_{g_i}(z_i). \end{aligned} \tag{12}\] We set \(f_g(z)=0\) outside \(z\in\{0,\ldots,g\}\). The last expression represents the same uniform subset by independent Bernoulli-\(\theta\) sampling conditioned on its total, including the degenerate laws at \(\theta=0,1\); it does not change the actual erasure rate \(r_e\).

For the rank estimates, call a count admissible when \[\theta=\frac{l}{n_b}\in[1-\delta^2,1-\delta^2/4].\]

For a tagged tuple define the coarse gaps \[\gamma_0=j_1-\tfrac12,\qquad \gamma_i=j_{i+1}-j_i\ (1\le i<r),\qquad \gamma_r=u-j_r+\tfrac12.\] They sum to \(u\), and \(g_i=m\gamma_i+\alpha_i\) with \(|\alpha_i|\le3\). The end coarse gaps are positive half-integers and the internal coarse gaps are positive integers. In particular \(g_i\gtrsim m\); at an admissible count, their expected binomial success and failure counts tend to infinity uniformly by \(m\delta^2\to\infty\).

Common mass for consecutive pure runs

The rank estimate first gives common mass at the working deletion rate. This mass will later conceal the side orientations that move the exceptional periods as a group.

For \(u=k,k+1\), write \(G^{(u,l)}=G_{\mathbf0}^{(u,l)}\) for the conditional density of the list from \(W_0^u\). At a count \(l\) admissible for both totals, the two densities use the same \(Q_l\), although their respective parameters are \(\theta=l/(um)\). Orthogonality of distinct multilinear monomials in the independent centered scores gives \[\mathbb E_{Q_l}\bigl[(G^{(u,l)})^2\bigr] =1+\sum_{r=1}^{u}\|A_{r,\mathbf0}\|_2^2\|Z\|_2^{2r} \le1+\sum_{r\ge1} (C_6\delta^{-2}\sqrt{u/m})^r r^{-r/2} \le\exp(C_6'\Lambda).\] Indeed, for \(a\ge0\), \(\sum_{r\ge1}(a/\sqrt r)^r\le\exp(C_*(1+a^2))\): for \(r>4a^2\) the terms are at most \(2^{-r}\); for \(1\le r\le4a^2\), the maximum of \(r\log(a/\sqrt r)\) over positive reals is at most \(a^2/(2e)\). Here \(\delta^{-4}u/m\lesssim\delta^{-3}\) at both side counts.

Nonnegativity, mean one, and Cauchy–Schwarz imply \[Q_l\{G^{(u,l)}\ge1/2\}\ge\tfrac14\exp(-C_6'\Lambda).\] Both densities are nondecreasing functions of the same coordinate likelihood values \(1+Z\ge0\): (9) is an average of nonnegative products in those variables. The coordinates are independent under \(Q_l\). Increasing events for independent real coordinates are nonnegatively correlated, the independent-coordinate case of association (Esary et al. 1967, Theorem 2.1). For completeness, in one dimension the covariance of increasing bounded functions \(f,g\) equals \(\mathbb E[(f(X)-f(X'))(g(X)-g(X'))]/2\ge0\) for independent copies \(X,X'\). Induction conditions on the last coordinate and applies the same fact to the conditional means. Applying this to the two threshold events gives \[\int\min(G^{(k,l)},G^{(k+1,l)})\,dQ_l \ge\tfrac1{32}\exp(-2C_6'\Lambda).\]

The count laws overlap on \[|l-(1-r_e)km|\le m.\] For either \(n_b=km\) or \(n_b=(k+1)m\), every such count is admissible for all large instances: its distance from the corresponding mean is at most \(2m\), and \(m/n_b\asymp1/(\delta m)=o(\delta^2)\). Stirling’s formula gives mass per count at least \[c_7(\delta\sqrt{n_b})^{-1} \exp\!\left(-C_7\frac{m^2}{\delta^2n_b}\right) \ge m^{-1}\exp(-C_8\Lambda)\] for absolute positive constants. One way to see the exponent is that the relative entropy between \(\operatorname{Ber}(l/n_b)\) and \(\operatorname{Ber}(1-r_e)\) is at most a constant times \((l/n_b-(1-r_e))^2/\delta^2\), while \[(l/n_b)(1-l/n_b)n_b\asymp\delta^2n_b \asymp\delta^3m^2\longrightarrow\infty.\] There are at least \(m\) integer counts in this interval. Sum the conditional overlap bounds with the lesser of the two count probabilities. For a sufficiently large absolute \(C_9\), the mark-list laws of \(W_0^k,W_0^{k+1}\) have overlap at least \[\omega=\exp(-C_9\Lambda)<1/8.\] Their ordinary trace laws have at least the same overlap by concatenation. Choose \(C=\max\{C_{\rm abs}/\omega,9/\delta\}\). Then \(C\delta>8\) and \(\log C=O(\Lambda)\).

The preliminary observation and its high-degree terms

We use the common mass just obtained for the mark-list laws. Draw \(J\) independent fair bits \(E_1,\ldots,E_J\). Pair a run of \(k+E_i\) periods before a central run of \(K\) periods with a run of \(k+1-E_i\) periods after it; use a fixed order for the runs on each side. The number of periods before the central run is \[L_{\rm left}=Jk+\sum_{i=1}^J E_i.\] For every schedule the exceptional global period \(a+i\) has central index \(X+i\), where \[ X=a-L_{\rm left} =\left\lfloor\frac{J+K}{2}\right\rfloor-\sum_{i=1}^J E_i =K/2+O(J+1). \tag{17}\] Since \(J=o(K)\) and \(|I|\) is fixed, all exceptional periods lie in the central run for every schedule. Thus each schedule cuts the same prescribed word into pure side runs and a central run with the indicated translated types.

Use the paired flag construction of Section 3 on each pair of side mark-list laws, with a common sublaw \(\omega U\) on the list space. Report the flag and both lists; report the orientation bit only on the visible flag. Report one ordered list of individual marks from the central run, without period boundaries or original slot labels. The list values, including empty-valued entries, are retained. The full report also records the fixed left/right order of its side lists.

Let \(P_+,P_-\) be these preliminary report laws for \(x_0,y_0\), and let \(P_{\rm pure}\) be the corresponding law for \(W_0^P\). There is one deterministic projection \(\mathcal K_0\): discard the flags and bits and concatenate all mark values in chronological order. Conditional on any orientation schedule, averaging the pair flags gives independent correct side-list laws; the central list is generated independently from the actual central types. The schedule partitions the same word as just observed. Consequently \[ \mathcal K_0P_+=\mathrm{Tr}(x_0),\qquad \mathcal K_0P_-=\mathrm{Tr}(y_0),\qquad \mathcal K_0P_{\rm pure}=\mathrm{Tr}(W_0^P). \tag{18}\]

For the score analysis, the metadata consist of the side flags and lists, the visible bits, and the central list count \(l\); they exclude the central mark values. Their law \(Q_{\rm meta}\) is common to all three words. The count is independent of the side data and of \(X\), because the \(Km\) central erasures have the same probabilities for every type. Given a metadata value \(\mathfrak d\), let \(M\) be the number of hidden pairs. The remaining hidden bits are independent and fair, so the conditional law \(\pi_{\mathfrak d}\) of \(X\) is a constant minus \(\operatorname{Bin}(M,1/2)\).

Extend \(\beta_i\) by zero outside \(I\), and define the central type vectors by \((\mathbf b_\pm(X))_j=\pm\beta_{j-X}\). Conditional on \(\mathfrak d\), the central densities and their coefficient arrays are \[ \begin{aligned} G_\pm^{\mathfrak d} &=\mathbb E_{X\sim\pi_{\mathfrak d}}G_{\mathbf b_\pm(X)}^{(K,l)}, &A_{r,\pm}^{\mathfrak d} &=\mathbb E_{X\sim\pi_{\mathfrak d}}A_{r,\mathbf b_\pm(X)},\\ G_{\rm pure}^{\mathfrak d}&=G_{\mathbf0}^{(K,l)}, &A_{r,\rm pure}^{\mathfrak d}&=A_{r,\mathbf0}. \end{aligned} \tag{19}\] These densities all integrate to one under \(Q_l\). In particular \[P_\pm(d\mathfrak d,dY) =Q_{\rm meta}(d\mathfrak d)\, G_\pm^{\mathfrak d}(Y)Q_l(dY),\] with \(l\) read from \(\mathfrak d\), and the analogous identity holds for \(P_{\rm pure}\). This is the common conditional reference required by Lemma 8.

Call metadata typical when \[\frac l{Km}\in[1-\delta^2,1-\delta^2/4], \qquad M\ge\omega^2J/2.\] The first failure is a multiplicative binomial tail for the central erasures, and the second is one for the independent hidden flags. The scale margins make both negligible at the required final-length budget: \[(d_D+B+1)\log n=N^{o(\epsilon)},\qquad \delta^2Km=N^{1-3\eta-o(1)},\qquad \omega^2J=N^{2\eta-o(1)}.\] Thus both Chernoff exponents dominate \(\log\Delta^{-1}=100(d_D+B+1)\log n\), and atypical metadata have mass \(o(\Delta)\).

Fix typical metadata for the remainder of the coefficient analysis and suppress the superscript \(\mathfrak d\). Put \(\lambda=\sqrt{K/m}=N^{-\eta/2+o(1)}\). For a fixed central type vector, Lemmas 10 and 6 give \[\left\|\sum_{1\le v_1<\cdots<v_r\le l} A_{r,\mathbf b}(v)\prod_{h=1}^r Z(Y_{v_h})\right\|_{r_0} \le \left(C_*r_0\delta^{-3/2}\sqrt\lambda\right)^r r^{-r/4}.\] Here \(\|Z\|_{r_0}\lesssim\delta^{-1}\), and \(r_0,\delta^{-1}=N^{o(1)}\). The factor in parentheses is \(N^{-\eta/4+o(1)}=N^{-.001+o(1)}\). Put \(R_0=3000\), and for each of the three densities write \(G_{\ge R_0}\) for the sum of its homogeneous terms of degrees at least \(R_0\) in (11) and (19). Geometric summation, followed by Minkowski’s inequality when mixing over \(X\), gives \[ \begin{aligned} \|G-1\|_{r_0}&\le N^{-.0009},\\ \|G_{\ge R_0}\|_{r_0}&\le N^{-2.3}. \end{aligned} \tag{20}\] The growing \(r_0\) is a moment order; \(R_0\) is a fixed degree cutoff. It remains to estimate the differences of their finitely many lower-degree arrays.

Differences of one rank kernel

For a tagged tuple in the central \(K\) periods, let \(W_{\mathbf j}\) be its type-\(W_0\) kernel. Let \(T_h\) move the \(h\)-th tagged slot one position to the right, while the rank tuple stays fixed, and put \[D_h=(T_h-T_h^{-1})/2,\qquad V_h=(T_h+T_h^{-1}-2)/2.\] These operators change only the adjacent slot-gap lengths. In particular the total \(Km\), the count \(l\), the parameter \(\theta=l/(Km)\), and the denominator \(f_{Km}(l)\) remain fixed.

Signed coefficient arrays and their sums

Define the seed motif indicator on the integers by \(\chi_{\rm seed}(i)={\bf1}_{\{i\in I\}}\). The rank event depends on the type vector only through its tagged positions, so for a fixed \(X\), \[W_{\mathbf j,\mathbf b_\pm(X)} =\prod_{h=1}^r T_h^{(\mathbf b_\pm(X))_{j_h}}W_{\mathbf j}.\] Each shift factor is exactly \[T_h^{(\mathbf b_\pm(X))_{j_h}} =1+\chi_{\rm seed}(j_h-X)V_h \ \pm\ \beta_{j_h-X}D_h.\] For disjoint \(\mathcal D,\mathcal V\subseteq\{1,\ldots,r\}\), write \[c_{\mathbf j}^{\mathcal D,\mathcal V} =\mathbb E_X\left[ \prod_{h\in\mathcal D}\beta_{j_h-X} \prod_{h\in\mathcal V}\chi_{\rm seed}(j_h-X)\right], \qquad \partial_{\mathcal D,\mathcal V} =\prod_{h\in\mathcal D}D_h\prod_{h\in\mathcal V}V_h.\] The coefficient differences \(B_r=A_{r,+}-A_{r,-}\) and \(B_r^{\rm pure}=A_{r,+}-A_{r,\rm pure}\) come from (19). Here and below, \(\sum_{\mathbf j}\) runs over \(1\le j_1<\cdots<j_r\le K\). Expanding the shift factors gives \[ B_r =2\sum_{\substack{\mathcal D\cap\mathcal V=\varnothing\\ |\mathcal D|\ {\rm odd}}} \ \sum_{\mathbf j} c_{\mathbf j}^{\mathcal D,\mathcal V} \partial_{\mathcal D,\mathcal V}W_{\mathbf j}. \tag{22}\] For \(B_r^{\rm pure}\), the same expansion runs over all nonempty patterns, without the oddness restriction or the factor \(2\). These are finite sums of \(C_r\) patterns because \(r<R_0\) is fixed.

Closing the initial invariant

For each fixed \(r<R_0\), Lemma 6 converts the coefficient estimate to the required score estimate: \[\left\|\sum_{1\le v_1<\cdots<v_r\le l} B_r(v)\prod_{h=1}^r Z(Y_{v_h})\right\|_{r_0}^2 \le (C_1r_0\|Z\|_{r_0})^{2r}\|B_r\|_2^2.\] The analogous inequality applies to the pure comparison. The fixed pattern constants, the displayed powers of \(\delta^{-1}\) and \(\omega^{-1}\), and the moment factors are \(N^{o(1)}\): use \(\log r_0=O_B(D+1)\), \(\log\omega^{-1}=O(\Lambda)\), and \(\Lambda=o(\log N)\). The analytic tails remain below every fixed power after these factors.

The worst nonlinear term of (26), at \(r=2\), is \[J^{-1/2}(Km)^{-1/2}m^{-7/2} =N^{-\eta}\,N^{-1/2+3\eta/2}\, N^{-7/4+7\eta/2+o(1)} =N^{-9/4+4\eta+o(1)}=N^{-2.234+o(1)}.\] The singleton term is \(N^{-3.394+o(1)}\) at its worst degree \(r=1\). The worst nonlinear term in (27) is \(N^{-3/2+5\eta/2+o(1)}=N^{-1.49+o(1)}\). Sum over the finitely many lower degrees and add the degree tails in (20). On every typical metadata value this yields \[ \|G_+-G_-\|_{r_0}^2\le N^{-2.22},\qquad \|G_+-G_{\rm pure}\|_{r_0}^2\le N^{-1.4}. \tag{28}\]

Let \(\mathcal A\) be the joint event of typical metadata and \(G_+^{\mathfrak d}(Y)\ge1/2\), and define \[\mu_0=P_+(\,\cdot\mid\mathcal A),\qquad \nu_0=P_-(\,\cdot\mid\mathcal A).\] Lemma 8 applies to the common conditional reference above: (20) gives \(\rho=.0009\ge2^{-4B-10}\), and \(2.22>2.20+.01\) supplies its difference margin. Hence \[\nu_0\ll\mu_0,\qquad \|d\nu_0/d\mu_0-1\|_{L^{r_0}(\mu_0)}^2\le N^{-2.20},\] and conditioning changes each preliminary law by \(o(\Delta)\) in total variation. By (18) and contraction under the same \(\mathcal K_0\), \[\mathop{\mathrm{TV}}(\mathcal K_0\mu_0,\mathrm{Tr}(x_0))\le o(\Delta)\le\Delta,\qquad \mathop{\mathrm{TV}}(\mathcal K_0\nu_0,\mathrm{Tr}(y_0))\le o(\Delta)\le\Delta\] for all large instances. This gives \(E_0\le\Delta\) and the score part of the invariant. The hidden-bit law was used for the preliminary densities only.

It remains to transfer pure-run overlap to \(x_0\). This comparison uses the preliminary laws, rather than the full clipping conclusion for their weaker \(N^{-1.4}\) difference. On typical metadata and \(G_+\ge1/2\), \[(\sqrt{G_+}-\sqrt{G_{\rm pure}})^2 \le 2|G_+-G_{\rm pure}|^2.\] On the complement use the bound \(G_++G_{\rm pure}\). The high-moment estimate (20) and the clipping proof bound the mass of the bad-density region under both preliminary laws by \(o(\Delta)\); atypical metadata have the same bound. Thus (28) gives \[H^2(P_+,P_{\rm pure})\le2N^{-1.4}+o(\Delta)\le3N^{-1.4}.\] Projection by \(\mathcal K_0\) gives the same upper bound for \(H^2(\mathrm{Tr}(x_0),\mathrm{Tr}(W_0^P))\).

Set \(k_0=\lceil CkP\rceil\). Since \(k\sim\delta m\) and \(C\delta>8\), we have \(k_0\ge\ell_0\) for all large instances. Also, \[\frac{k_0}{\ell_0} \le\frac{C\delta m}{2m-1}+\frac1{\ell_0}<C,\] using \(\delta\le1/2\), \(C\ge18\), and \(\ell_0\to\infty\). Thus the common choice \(M_B=1\) meets the level-zero count predicate. Moreover \(C=\exp(O(\Lambda))=N^{o(1)}\). For \(F=k_0,k_0+1\), tensorization followed by concatenation therefore gives \[\mathop{\mathrm{TV}}(\mathrm{Tr}(x_0^F),\mathrm{Tr}(W_0^{PF})) \le\sqrt{F\,H^2(\mathrm{Tr}(x_0),\mathrm{Tr}(W_0^P))} \le\sqrt{3F N^{-1.4}} =N^{-0.2+o(1)}=o(1).\] Lemma 7, with base word \(W_0\), overlap count \(k\), replication \(P\), and \(F=k_0\), gives overlap at least \(2/3\) for the two pure repeated comparison words. Paying the two replacement costs leaves \[\mathop{\mathrm{ov}}(\mathrm{Tr}(x_0^{k_0}),\mathrm{Tr}(x_0^{k_0+1})) \ge2/3-o(1)\ge\omega.\] Together with the length, distinction, score, and simulation estimates already proved, this completes Proposition 9.

Nested signed words

The two new words will use the same nested motif at \(b\) depths. Choose the fixed degree cutoff and the cancellation order \[r_*=2^{10B+40},\qquad s_*=\left\lceil100(d_D+r_*+B+10)/\epsilon\right\rceil, \qquad L=2^{s_*}.\] Let \(\mathcal I=\{0,\ldots,L-1\}\) and define the signs by \[\sum_{a\in\mathcal I}\sigma_a z^a =\prod_{v=0}^{s_*-1}(1-z^{2^v}).\] Extend \(\sigma_a\) by zero outside \(\mathcal I\), and put \(\chi={\bf1}_{\mathcal I}\). The order \(s_*=O_B((D+1)^2)\) is large enough for the signed smoothing below at every block. Lemma 3 gives, uniformly, \[ \begin{gathered} L^{O_B(r_*B)}=N^{o(\epsilon)},\\ \exp\bigl(O_B((s_*+1)^2+(s_*+1)(D+1)\Lambda)\bigr) =N^{o(\epsilon)}. \end{gathered} \tag{30}\] Here and below fixed-depth constants may depend on \(B\).

Start with \(U_0^+=x\), \(U_0^-=y\), both of length \(S_0=\ell\), and with overlap count \(h_0=k\). Once a positive integer \(P_j\) has been chosen, form \(U_j^\tau\), for \(\tau\in\{+1,-1\}\), from \(P_j\) consecutive level-\((j-1)\) atoms. Use type \(+\) except at the labels \(\lfloor P_j/2\rfloor+a\), \(a\in\mathcal I\), where the type is \(\tau\sigma_a\). We choose the counts below so that these labels lie in \([1,P_j]\). The common length is \[S_j=P_jS_{j-1}.\] The two words are distinct: at a motif label their atom types differ, and equal-length atoms give a fixed parse back to the distinct old words.

Word sizes, windows, and paired counts

Write \(N^{a_j}\) for the target length of a level-\(j\) word. It then contains about \(N^{a_j-a_{j-1}}\) lower atoms. An overlap chunk will contain \(h_{j-1}\) such atoms, with \(h_{j-1}\) within the controlled channel factor of their word length \(N^{a_{j-1}}\). To leave about \(N^\epsilon\) paired chunks, choose the remaining exponents by \[a_j(b)=2a_{j-1}(b)+\epsilon\quad(1\le j\le b).\] This recurrence and (3) give the identities \[ a_j(b)=(1+\epsilon)2^{j-b}-\epsilon\quad(0\le j\le b), \qquad a_b(b)=1. \tag{31}\] In the rest of this block, \(a_j\) abbreviates \(a_j(b)\).

A level-\(j\) child window will contain \(T_j\) level-\((j-1)\) atoms. Define \[\kappa_j=a_{j-1}-3(2^j-1)\epsilon, \qquad T_j=4\left\lfloor N^{\kappa_j}/4\right\rfloor \quad(1\le j\le b).\] The \(\kappa_j\) are positive for all sufficiently large instances, uniformly in the block. Directly from (31), \[ \begin{aligned} 2\kappa_j-\kappa_{j+1}-\epsilon&=\epsilon\quad(1\le j<b),\\ \kappa_b&>\epsilon,\qquad \kappa_j<a_{j-1}<a_j-a_{j-1}\quad(1\le j\le b). \end{aligned} \tag{32}\] The first identity makes \(T_j\) larger than the typical displacement from \(T_{j+1}\) collections of about \(N^\epsilon\) fair bits: the squared window width divided by that bit count has order \(N^\epsilon\). The remaining inequalities leave room for the windows inside their words. We also have \[ \sum_{j=1}^b\kappa_j<1, \tag{33}\] since \(\kappa_j<a_{j-1}<2^{j-1-b}\); this will bound the number of vertices in the observation tree.

For \(1\le j<b\), choose \[\begin{aligned} P_j&=\left\lfloor N^{a_j}/S_{j-1}\right\rfloor, &h_j&=\lceil C h_{j-1}P_j\rceil,\\ t_j&=2\left\lfloor P_j/[100(2h_{j-1}+1)]\right\rfloor. \end{aligned}\] For the root, choose \[\begin{aligned} J&=\left\lfloor\frac{\lfloor N/S_{b-1}\rfloor-T_b} {2h_{b-1}+1}\right\rfloor, &P_b&=J(2h_{b-1}+1)+T_b,\\ h_b&=\lceil C h_{b-1}P_b\rceil. \end{aligned}\] The counts \(t_j\) and \(J\) are the numbers of paired chunks used for local and outer displacements, respectively. The factors \(2\) and \(4\) in their definitions and in \(T_j\) ensure the parity and divisibility needed by the partition.

We record the size consequences before using the words. For \(j<b\), flooring loses at most \(S_{j-1}=o(N^{a_j})\), so \[S_j\in[N^{a_j}/2,N^{a_j}],\qquad P_j\asymp N^{a_j-a_{j-1}},\qquad T_j=o(P_j).\] The overlap counts remain within the declared uniform bound. Indeed \(h_j\ge S_j\) by induction, and \[\frac{h_j}{S_j}\le C\frac{h_{j-1}}{S_{j-1}}+1 \le C^2\frac{h_{j-1}}{S_{j-1}}\] because \(h_{j-1}/S_{j-1}\ge1\) and \(C>2\). Starting from the level-\((i-1)\) bound gives \[ S_j\le h_j\le C^{2B(i-1)+M_B+2j}S_j \le C^{2Bi+M_B}S_j\quad(0\le j\le b), \tag{34}\] In particular the extra count factor is at most \(\exp(O_B((D+1)\Lambda))\).

Using these bounds in the definitions of \(t_j\) and \(J\) yields \[ e^{-O_B((D+1)\Lambda)}N^\epsilon\le t_j\le O(N^\epsilon) \quad(1\le j<b), \tag{35}\] and the same lower and upper bounds for \(J\). All these counts tend to infinity uniformly. At the root, \(J=o(T_b)\) by \(\kappa_b>\epsilon\), and \[N-S_b=O((h_{b-1}+1)S_{b-1}) \le N^{2a_{b-1}+o(\epsilon)} =N^{1-\epsilon+o(\epsilon)}=o(N).\] Here the count overhead is \(N^{o(\epsilon)}\) by (5), and \(2a_{b-1}=1-\epsilon\) by (31). Thus also \(S_b\in[N/2,N]\). Working backward from \(\kappa_b>\epsilon\) in (32) gives \(\kappa_j>\epsilon\) at every depth. The uniform loss bound (30) therefore gives \(L=o(T_j)\) and \(L=o(P_j)\) uniformly, so all motif labels used above fit. We take \[x_i=U_b^+,\qquad y_i=U_b^-,\qquad \ell_i=S_b,\qquad k_i=h_b.\]

The following estimate quantifies the smoothing supplied by a hidden binomial offset. It will be used in the early overlap comparison and in the main score proof. In those applications, its local parameter \(m\) is one of the paired counts \(J\) or \(t_j\), while \(g\) is the actual number of hidden orientation trials.

Overlap for each nested atom

The words, counts, and overlaps required for the observation are now available at every nested depth. The next section uses their paired side runs to hide the relative locations of the motifs.

The index tree and the outer window

Use a deterministic tree common to both hypotheses. Its root \(\varnothing\) is the sole level-\(b\) vertex. A level-\(j\) vertex has \(T_j\) children at level \(j-1\), indexed by appending \(h\in\{1,\ldots,T_j\}\) to its own index. Thus an index records positions relative to successive sibling groups. Level-zero vertices are leaves. The entire experiment described below is redrawn independently for each observation.

At the root, place a central run of \(T_b\) level-\((b-1)\) atoms between \(J\) pairs of pure \(U_{b-1}^+\) runs. For each pair use an independent fair bit \(E\), giving counts \(h_{b-1}+E\) on the left and \(h_{b-1}+1-E\) on the right. Use the paired flag mechanism from Section 3, with hidden probability \(\omega^2\), at the overlap proved in Lemma 15. Report one unseparated ordinary trace per side run, its flag, and its orientation bit when revealed. The left runs have fixed pair-number order before the center, and the right runs have the corresponding fixed order afterward.

The root motif at the word label \(\lfloor P_b/2\rfloor+a\) has relative label \(X+a\) in this central run, where \[ X=\lfloor P_b/2\rfloor-Jh_{b-1}-\sum E =T_b/2+O(J+1). \tag{42}\] This is the coordinate of a fixed motif relative to the moving central window. Since \(J=o(T_b)\) and \(L=o(T_b)\), every \(X+a\), \(a\in\mathcal I\), lies in \([T_b/3,2T_b/3]\) for all orientations and all sufficiently large instances.

One group of child windows

Fix \(1\le j<b\) and a level-\((j+1)\) vertex \(G\). Its \(T=T_{j+1}\) children \(Gu\), \(1\le u\le T\), represent a planned consecutive sequence of \(T\) level-\(j\) units. We partition that sequence into successive parts, measured in level-\((j-1)\) atoms. Part \(u\) contains a window of \(T_j\) atoms for the children of \(Gu\), with nominal pre and post counts \[A_j=\lfloor(P_j-T_j)/2\rfloor, \qquad P_j-T_j-A_j.\] The parts may have different actual lengths, but their total length will remain \(TP_j\).

Reserve \(t_j\) local pairs in each part. For \(1\le v\le t_j\), a fair bit \(E^{\rm loc}_{u,v}\) gives a pre chunk of \(h_{j-1}+E^{\rm loc}_{u,v}\) pure \(U_{j-1}^+\) atoms and a post chunk of \(h_{j-1}+1-E^{\rm loc}_{u,v}\) such atoms. Also reserve global pairs between distant parts. For every \(1\le a\le T/4\) and \(1\le v\le t_j\), a fair bit \(E^{\rm glob}_{a,v}\) gives a pre chunk of \(h_{j-1}+E^{\rm glob}_{a,v}\) atoms in part \(a\) and a post chunk of \(h_{j-1}+1-E^{\rm glob}_{a,v}\) atoms in part \(T+1-a\). All these bits are independent.

Treat each reserved chunk as having nominal count \(h_{j-1}+1/2\). Complete every pre and post region to its nominal count by one pure-\(U_{j-1}^+\) filler of deterministic count, and order its chunks and filler by fixed relative IDs. The filler counts are nonnegative: each region reserves at most \(2t_j\) chunks, while the choice of \(t_j\) reserves at most \(P_j/50\) atoms and \(T_j=o(P_j)\). They are integers because each reserved collection has the even number \(t_j\) of chunks; a region contains zero, one, or two such collections. Generate each reserved pair of chunks with the joint flag mechanism at the overlap of \(U_{j-1}^+\); generate each filler as an independent ordinary trace. Each chunk or filler reports one unseparated trace, with the flags and revealed bits for paired chunks. The surrogate uses these pure-run laws for every orientation, even when the corresponding locations would not be pure in the true word.

The exact prefix count explains the two displacement scales. Define \[\begin{align*} H_{Gu}&=\sum_{v=1}^{t_j}(E^{\rm loc}_{u,v}-1/2),\\ V_{Gu}&=\sum_{a=1}^{T/4}\sum_{v=1}^{t_j} \bigl({\bf1}_{a\le u}-{\bf1}_{T+1-a<u}\bigr) (E^{\rm glob}_{a,v}-1/2),\qquad Y_{Gu}=V_{Gu}+H_{Gu}. \tag{43}\end{align*}\] Then the number of lower atoms before the window of \(Gu\), counted from the start of the group, is \[ (u-1)P_j+A_j+Y_{Gu}. \tag{44}\] In (43), a global pre chunk is included when its part \(a\) is at or before \(u\), whereas its post chunk is included only when part \(T+1-a\) is strictly before \(u\). Completed global pairs cancel. Every earlier local pair has also been completed; only the current local pre chunks contribute \(H_{Gu}\). This proves (44). Each included collection contributes the even number \(t_j\) of half-integer deviations, so the displacements are integers. After the last post region all pairs have cancelled, proving the total count \(TP_j\).

For the middle half of the group, every global pre chunk has appeared and no global post chunk has appeared. Thus \[ V_{Gu}=V_G:=\sum_{a=1}^{T/4}\sum_{v=1}^{t_j} (E^{\rm glob}_{a,v}-1/2) \quad\text{when }T/4<u\le3T/4. \tag{45}\] The local sums \(H_{Gu}\) are independent across \(u\) and independent of the global bits. The global sums outside this interval are partial sums of the same group’s bits. Distinct groups and depths use independent mechanisms.

The surrogate law and its projection

We now apply this group partition recursively. The root center is the first group of \(T_b\) planned level-\((b-1)\) units. A window at any later vertex is partitioned into the group for its children by the construction above.

Define type labels for every orientation, starting from \(\tau_\varnothing=+1\) or \(-1\) under the two hypotheses. At the root put \[\tau_h=1-\chi(h-X)+\sigma_{h-X}\tau_\varnothing.\] For every other level-\(j\) vertex \(I\), \(j\ge1\), put \[ \tau_{Ih}=1-\chi(h-w_j+Y_I)+\sigma_{h-w_j+Y_I}\tau_I, \qquad w_j=\lfloor P_j/2\rfloor-A_j=T_j/2. \tag{46}\] The last equality uses the evenness of \(T_j\). These rules place the motif labels that fit in each window and use type \(+\) at its other labels. They define a surrogate even on a failed layout, when an intended motif label falls outside its window; all non-leaf pieces still use the pure laws already specified.

Conditional on all bits, sample the leaf outputs independently of one another and of the entire collection of non-leaf flags and emissions, using law \(\mu_{i-1}\) for type \(+1\) and \(\nu_{i-1}\) for type \(-1\). The complete report consists of these separate leaf outputs, all side outputs, flags, and visible bits, with their relative tree and segment IDs. It contains no hidden type labels, absolute word labels, or hidden boundary positions. Let \(D_0\) denote all of this report except the complete old oracle payload at each leaf; in particular, any metadata inside an old payload are excluded from \(D_0\).

Let \(\widetilde\mu_i,\widetilde\nu_i\) be the two unconditioned surrogate laws. A common kernel \(\mathcal K_{\rm tree}\) applies \(\mathcal K_{i-1}\) independently to every leaf output and concatenates the resulting binary words and side traces in the chronological order specified by the IDs: pre pieces, the recursively ordered window contents, and post pieces in each part, with the outer side runs in their stated order.

Define the fit event, which depends on the orientation bits, by \[ \mathcal F=\bigl\{|Y_I|\le T_j/8 \text{ for every level-$j$ vertex }I,\ 1\le j<b\bigr\}. \tag{47}\]

The information retained after the report

The law of \(D_0\) is common to the two surrogate hypotheses, because every non-leaf emission is generated from a pure run and all IDs are fixed. Conditional on its full value, every unrevealed orientation is still a fair bit. These hidden bits are independent across pairs, groups, and depths: the report of a hidden pair has the common product law, while a non-hidden pair reveals its bit, and the pair mechanisms were generated independently. Visible contributions are fixed by the report. Consequently \(X\), each local sum, and each global sum have exactly the affine hidden-bit forms given above. Global offsets within a group retain their prescribed dependence.

Call a metadata value typical when all of the following hold:

• the root has at least \(\omega^2J/2\) hidden orientations;

• for every \(1\le j<b\), every local collection at a level-\(j\) vertex has at least \(\omega^2t_j/2\) hidden orientations, and every global collection in a group of \(T_{j+1}\) children has at least \(\omega^2(T_{j+1}/4)t_j/2\);

• \(\mathbb P(\mathcal F^c\mid D_0)\le\exp(-N^{\epsilon/4})\).

These conditions fail with probability \(o(\Delta)\). For the hidden counts, apply multiplicative binomial concentration to the independent flags and then a union bound. Every required expectation is at least \(e^{-O_B((D+1)\Lambda)}N^\epsilon\), and Lemma 3 makes the resulting tail negligible relative to \(\Delta\). For the last condition, apply Markov’s inequality to (49).

The score analysis in the next section fixes one exact typical value of \(D_0\) and averages over all its remaining hidden bits. It does not condition those bits on \(\mathcal F\).

High degrees from the input score

For fixed bits, every level-one window has at most \(L\) negative leaves, because its negative types can occur only on the support of its motif. There are \(\prod_{j=2}^bT_j\) such windows. This remains true on failed layouts, so the number of factors \(1+Z_v\) in either fixed-bit density is at most \[L\prod_{j=2}^bT_j.\] The margin between the old score and this number of possible positions is \[ \lambda_d:=a_0d-\sum_{j=2}^b\kappa_j>8g_B(d+1), \qquad g_B:=2^{-4B-10}. \tag{51}\] Here is the promised use of the two depth phases. Since \(\sum_{j=2}^b\kappa_j<1-2^{1-b}\) and \(a_0\ge2^{-b}-\epsilon\), for \(b=2\) and \(d\ge2.20\), \[\lambda_d>d/4-1/2-\epsilon d.\] For \(b=B\) after the preliminary phase, \(d\ge2^B+2.20\) and \[\lambda_d>2^{-B}(d-2^B+2)-\epsilon d.\] In each case the positive part is a fixed positive fraction, depending only on \(B\), of \(d+1\). The choices of \(g_B\) and \(\epsilon\) leave the bound in (51) uniformly.

At fixed bits, Lemma 6 bounds the squared \(L^{r_i}(Q)\) norm of the homogeneous degree-\(r\) part of either density by \[(C_1r_i)^{2r}N^{-a_0dr} \binom{L\prod_{j=2}^bT_j}{r} \le \bigl(N^{-\lambda_d+o(\epsilon)}\bigr)^r.\] Convexity permits averaging over the bits at this bound. Geometric summation of the norms, using (51), gives \[ \|G_\pm-1\|_{r_i}\le N^{-g_B},\qquad \|\text{degree }\ge r_*\text{ part of }G_\pm\|_{r_i}^2 \le N^{-d'-1}. \tag{52}\] For the second inequality, \(r_*g_B(d+1)>d'+3\) leaves the required margin. Only the fixed degrees \(1\le r<r_*\) remain.

A fixed coefficient and its parity terms

Fix such a degree \(r\) and a leaf subset \(\mathcal S\) of size \(r\). Its coefficient in \(G_+-G_-\) is \[ c(\mathcal S)=\mathbb E_{\mathfrak d}\left[ \prod_{v\in\mathcal S}\frac{1-\tau_v^+}{2} -\prod_{v\in\mathcal S}\frac{1-\tau_v^-}{2}\right]. \tag{53}\] Lemma 6 reduces the squared norm of this degree to \[ \left\|\sum_{|\mathcal S|=r}c(\mathcal S) \prod_{v\in\mathcal S}Z_v\right\|_{r_i}^2 \le (C_1r_i)^{2r}N^{-a_0dr} \sum_{|\mathcal S|=r}|c(\mathcal S)|^2. \tag{54}\] To estimate the right side, expand the integrand for fixed bits and fixed relative leaf labels, and only then average each chosen term. Call a vertex occupied if it is an ancestor of a leaf in \(\mathcal S\), including that leaf itself.

For a vertex \(I\) and one of its child labels \(h\), write \[\xi_{I,h}=\begin{cases}h-X,&I=\varnothing,\\ h-w_j+Y_I,&I\text{ at level }j<b, \end{cases} \qquad \chi_{Ih}=\chi(\xi_{I,h}),\quad \sigma_{Ih}=\sigma_{\xi_{I,h}}.\] For an occupied vertex \(I\), let \(F_I(t)\) be the contribution of the selected leaves below it when its incoming type is \(t\in\{-1,1\}\). At a level-one vertex with \(m_I\) selected children, the type rule gives the already-cancelled expression \[ F_I(t)=2^{-m_I}\prod_{h:\,Ih\in\mathcal S} (\chi_{Ih}-\sigma_{Ih}t). \tag{55}\] In particular every selected leaf contributes a motif factor. At a higher occupied vertex, the selected-leaf product splits across child subtrees, giving the algebraic recursion \[ F_I(t)=\prod_{h:\,Ih\text{ occupied}} F_{Ih}(1-\chi_{Ih}+\sigma_{Ih}t),\qquad t\in\{-1,1\}. \tag{56}\] The substituted type is again \(+1\) or \(-1\). No probabilistic independence of the child functions is asserted here; this is the factorization of one product of leaf indicators at fixed bits.

Every function on \(\{-1,1\}\) has an even and an odd part. To retain the individual motif choices, expand (55)–(56) into terms \(M_I t^{p_I}\), reducing powers by \(t^2=1\), where \(p_I\in\{0,1\}\). The following rules describe each chosen term.

• At level one choose \(\chi_{Ih}\) or \(-\sigma_{Ih}t\) from every selected leaf factor. Every such leaf is called active, and \(p_I\) is the parity of the number of signed factors.

• At a higher vertex choose one term \(M_{Ih}\tau_{Ih}^{p_{Ih}}\) from each occupied child. If \(p_{Ih}=0\), its contribution is \(M_{Ih}\). If \(p_{Ih}=1\), substitute the type rule and choose one of \(1\), \(-\chi_{Ih}\), or \(\sigma_{Ih}t\) in \(M_{Ih}(1-\chi_{Ih}+\sigma_{Ih}t)\). The child is active at \(I\) when the second or third summand is chosen. Set \(p_I\) to the parity of the signed summands chosen at \(I\).

Odd and even are roles of these chosen terms, not intrinsic properties of the vertex or of its full coefficient function. At the root, the difference \(F_\varnothing(+1)-F_\varnothing(-1)\) keeps exactly the odd terms and gives each a factor two. Apart from bounded scalar factors, a chosen term in (53) is therefore the expectation of the product of its active \(\sigma\) and \(\chi\) factors.

For fixed \(r\) and \(b\), the number of ordered occupied-tree shapes and expansion choices is bounded solely in terms of \(r,b\). A shape specifies adjacency and sibling order, not the numerical child labels. We may fix a shape and its choices, bound the squared coefficient sum over the labels, and combine these finitely many bounds by Cauchy–Schwarz.

We first split that label sum into central and noncentral assignments. If an active child of a level-\(j\) vertex has label outside \([T_j/3,2T_j/3]\), a nonzero factor requires \(|Y_I|>T_j/8\) for all large instances, since \(w_j=T_j/2\) and \(L=o(T_j)\); at the root it is impossible by (42). Hence such a term has conditional multiplier at most \(\mathbb P(\mathcal F^c\mid D_0=\mathfrak d)\le\exp(-N^{\epsilon/4})\) in absolute value. There are at most \(O_B(N^r)\) label assignments by (33), so their contribution to the right side of (54) is at most \(N^{-d'-1}\) eventually. From now on all active child labels in the sum lie in their central intervals. This is a restriction of deterministic label assignments, not conditioning of the bit law. In particular, two forced children of a level-\((j+1)\) parent will lie in \[[T_{j+1}/3,2T_{j+1}/3]\subset(T_{j+1}/4,3T_{j+1}/4],\] the interval where their offsets share the global sum in (45).

Terms with a singleton odd role

Suppose a chosen odd term at a vertex \(I\) has exactly one active child. The active factor must be signed, since the number of signed factors is odd. All other local choices at that vertex contribute one or no factor.

We need the precise locality of its relative argument. After the relative IDs and expansion choices are fixed, the local sum \(H_I\) occurs among the surrogate arguments \(\xi_{J,h}\) only when \(J=I\). Equation (43) shows that the local pre/post deviations cancel before a later sibling part. Lower relative arguments use the fresh mechanisms of their own groups. The physical absolute positions of the descendant subtree can move with \(H_I\), but those positions are unreported and do not occur in its lower relative arguments. Likewise \(X\) occurs only in root arguments. This statement does not require independence of child terms, which may share lower global bits.

Condition on every orientation bit except the hidden local bits at \(I\); for the root, keep only its hidden outer bits unconditioned. Every other active factor is then fixed, while the singleton signed factor is convolved with a translated or reflected fair binomial. Its number of trials is at least \(\omega^2t_j/2\) for a level-\(j\) vertex with \(j<b\), and at least \(\omega^2J/2\) at the root. Equation (36) bounds the conditional multiplier by \[\exp(O((s_*+1)^2+(s_*+1)\Lambda)) \begin{cases} t_j^{-(s_*+1)/2},&1\le j<b,\\ J^{-(s_*+1)/2},&j=b. \end{cases}\] The estimate remains valid after averaging the other bits. Typicality is already a property of the fixed report, and no fit conditioning has been used.

The lower bounds for \(J,t_j\) give \[J^{-(s_*+1)},\ t_j^{-(s_*+1)} \le e^{O_B((s_*+1)(D+1)\Lambda)} N^{-\epsilon(s_*+1)}.\] Since \(\epsilon s_*\ge100(d_D+r_*+B+10)\), this absorbs the \(O_B(N^r)\) label assignments and the squared moment factor \((C_1r_i)^{2r}N^{-a_0dr}\). The resulting contribution to the squared degree-\(r\) norm is at most \(N^{-d'-1}\) eventually.

The forced subtree and extra labels

In a remaining odd root term, every odd nonleaf has at least two active children. At a higher vertex those children carry odd chosen terms; at level one they are selected leaves. Starting at the root, choose the first two active children in sibling order and repeat this choice at each selected odd child. This forces a complete binary subtree with \(2^b\) leaves. The choice depends on the shape and expansion roles, not on the numerical labels. Thus \(r\ge2^b\); put \(e=r-2^b\).

For each forced nonleaf \(I\), let \(h_I<h'_I\) be its two forced child labels, calling the first the anchor. A nonzero term requires \(0<h'_I-h_I<L\), because both active arguments belong to the same translate of \(\mathcal I\). Define the nonnegative anchor kernel \[f=\prod_{I\text{ forced nonleaf}}\chi(\xi_{I,h_I}).\] Every extra, nonforced selected leaf still contributes an absolute \(\chi\) constraint by (55). After discarding the other constraints, the absolute multiplier is at most a fixed scalar times \[ \mathbb E_{\mathfrak d}\left[f\prod_{\text{extra leaves }Ih} \chi(\xi_{I,h})\right]. \tag{57}\] The expectation has no additional fit indicator. The central and close-label restrictions concern the fixed labels being summed.

Figure 2 illustrates the forced selection and the shared global offset produced by (43)–(45).

First sum the extra labels so that only the forced anchor expectation remains. Fix the forced labels and all nonleaf labels. For an assignment \(\mathbf h\) of the \(e\) extra leaf labels, let \(a_{\mathbf h}\) be the nonnegative expectation in (57). At fixed bits each extra leaf has at most \(L\) labels satisfying its constraint, even if several constraints share bits. Hence \[\sum_{\mathbf h}a_{\mathbf h}\le L^e\mathbb E_{\mathfrak d}f, \qquad \sum_{\mathbf h}a_{\mathbf h}^2 \le\left(\sum_{\mathbf h}a_{\mathbf h}\right)^2 \le L^{2e}(\mathbb E_{\mathfrak d}f)^2.\] This avoids a free factor \(T_1\) per extra leaf. At each positive nonroot level, there are at most \(e\) occupied nonforced vertices: their descendant sets are disjoint at that level, and each contains an extra leaf and no forced leaf. Summing their child labels costs at most \((\prod_{j=2}^bT_j)^e\). With the forced labels fixed, \(f\) does not depend on which nonforced labels were selected, because the complete tree and every group mechanism were fixed before choosing \(\mathcal S\).

The fixed-label anchor factorization

It remains to sum \((\mathbb E_{\mathfrak d}f)^2\) over the forced labels. Call a forced sibling pair valid when its two labels are central and their positive difference is less than \(L\). Dropping any further order restrictions involving nonforced children can only increase this nonnegative sum. Define the outer anchor convolution \[K_{\rm out}^{\mathfrak d}(z)=\mathbb E_{\mathfrak d}\chi(z-X).\] Its \(\ell^1\) mass is \(L\), and its supremum is at most \(O(L\omega^{-1}J^{-1/2})\) by the hidden root count. Including at most \(2L\) choices for the close root child, its squared sum costs \[ \sum_{\substack{u_1,u_2\text{ valid root}\\\text{forced labels}}} K_{\rm out}^{\mathfrak d}(u_1)^2 \le \Gamma_{\rm out},\qquad \Gamma_{\rm out}=O(L^3\omega^{-1}J^{-1/2}). \tag{58}\]

For a fixed forced labeling, let \(\mathcal G_j\) be its forced level-\((j+1)\) parents. Each \(G\in\mathcal G_j\) has two forced level-\(j\) children \(Gu_1(G),Gu_2(G)\) with fixed distinct labels \(u_1(G)<u_2(G)\) in the middle-half interval. For any such fixed \(G\) and sibling labels \(u_1<u_2\), define their joint anchor kernel by \[ \mathcal H_{j,G;u_1,u_2}^{\mathfrak d}(z_1,z_2) =\mathbb E_{\mathfrak d}\left[ \chi(z_1-w_j+Y_{Gu_1})\chi(z_2-w_j+Y_{Gu_2})\right]. \tag{59}\] The expectation here uses that group’s global bits and the two local collections under the fixed report. The actual \(G,u_1,u_2\) select those collections; only \(z_1,z_2\) are variables in the norm below. The factor can vary with all of these fixed data.

Independence of the distinct group mechanisms conditional on \(D_0=\mathfrak d\) now gives, for this fixed forced labeling, \[ \mathbb E_{\mathfrak d}f =K_{\rm out}^{\mathfrak d}(h_\varnothing) \prod_{j=1}^{b-1}\prod_{G\in\mathcal G_j} \mathcal H_{j,G;u_1(G),u_2(G)}^{\mathfrak d} (h_{Gu_1(G)},h_{Gu_2(G)}). \tag{60}\] The group sets and sibling IDs in this identity are determined by the fixed upper labels. In particular \(\mathcal G_{b-1}\) contains the root; its interior global/local mechanism is independent of the outer mechanism defining \(X\).

For fixed distinct plateau siblings, (45) gives \(Y_{Gu_1}=V_G+H_{Gu_1}\) and \(Y_{Gu_2}=V_G+H_{Gu_2}\). Conditional on \(\mathfrak d\), the two local hidden sums are independent of each other and of the shared global hidden sum, though their visible shifts and hidden counts can differ. We have uniformly in the fixed data \[ \begin{aligned} \|\mathcal H_{j,G;u_1,u_2}^{\mathfrak d}\|_{\ell^1(\mathbb Z^2)}&\le L^2,\\ \|\mathcal H_{j,G;u_1,u_2}^{\mathfrak d}\|_{\ell^\infty(\mathbb Z^2)} &\le C_{10}L^2\omega^{-2}(T_{j+1}t_j)^{-1/2}t_j^{-1/2}. \end{aligned} \tag{61}\] Here \(C_{10}\) is absolute. The first bound follows by summing the two indicators before averaging. For the supremum, first fix all global bits and bound the local average at \(Gu_2\) by \(O(L\omega^{-1}t_j^{-1/2})\). This bound is uniform in the global offset, so discard that factor’s constraint. Average the other factor over its local bits and the global bits. The latter contain at least a constant times \(\omega^2T_{j+1}t_j\) hidden fair trials, giving \(O(L\omega^{-1}(T_{j+1}t_j)^{-1/2})\). Multiplication proves the displayed joint bound without treating the two offsets as independent.

Multiplying the \(\ell^1\) and supremum bounds controls the squared \(\ell^2\) sum. Allowing a close child for each anchor costs at most \((2L)^2\). Thus for fixed valid \(G,u_1,u_2\), \[ \begin{aligned} \sum_{\substack{z_1,z'_1,z_2,z'_2\in\mathbb Z\\ 0<z'_1-z_1<L,\ 0<z'_2-z_2<L}} \mathcal H_{j,G;u_1,u_2}^{\mathfrak d}(z_1,z_2)^2 &\le\Gamma_j,\\ \Gamma_j&=C_{11}L^6\omega^{-2}T_{j+1}^{-1/2}t_j^{-1}, \end{aligned} \tag{62}\] with an absolute \(C_{11}\) large enough for every group.

We make the order of the nested sums explicit. For two fixed valid level-\(j\) siblings \(Gu_1,Gu_2\), let \(\mathcal R_j(G;u_1,u_2)\) be the sum of the squares of the products of all their interior \(\mathcal H\) factors, including the factor of \(G\), over all valid forced descendant labelings. Set \(\mathcal R_0=1\). Splitting the descendant labels at their first two pairs gives the exact recurrence \[ \begin{aligned} \mathcal R_j(G;u_1,u_2) &=\sum_{\substack{(z_1,z'_1),(z_2,z'_2)\\ \text{valid at level }j}} \mathcal H_{j,G;u_1,u_2}^{\mathfrak d}(z_1,z_2)^2 \prod_{v=1}^2\mathcal R_{j-1}(Gu_v;z_v,z'_v)\\ &\le \Gamma_j\left(\sup_{G',v_1,v_2\text{ valid}}\mathcal R_{j-1}(G';v_1,v_2)\right)^2. \end{aligned} \tag{63}\] For the inequality, first use the uniform descendant bound on the valid distinct child pairs. Only afterward enlarge the remaining close-label sums to at most \(2L\) choices and apply (62). No group estimate is invoked at coincident sibling IDs. Iterating this inequality from the leaves upward, and finally using (58), gives \[ \sum_{\text{valid forced labels}}(\mathbb E_{\mathfrak d}f)^2 \le \Gamma_{\rm out}\prod_{j=1}^{b-1}\Gamma_j^{2^{b-j-1}}. \tag{64}\] This procedure applies a uniform bound to each actual group after its upper IDs are fixed; it does not replace the varying kernels by one stationary kernel.

The exponent gain and closure

Combine the extra-label reduction, (64), and the squared moment factor \((C_1r_i)^{2r}N^{-a_0dr}\). The fixed shape and expansion counts, the powers of \(L\) and \(\omega^{-1}\), and the positive factor \((C_1r_i)^{2r}\) contribute \(N^{o(\epsilon)}\) by Lemma 3 and (30). The squared degree contribution of a branching term is therefore at most \[N^{o(\epsilon)}J^{-1/2} \prod_{j=1}^{b-1}\bigl[T_{j+1}^{-1/2}t_j^{-1}\bigr]^{2^{b-j-1}} N^{-2^ba_0d}N^{-\lambda_de}.\] The last factor pays for every extra leaf and is at most one by (51). Using the lower bounds for \(J,t_j\), the decay exponent of the remaining factors is at least \[\begin{align*} &\epsilon/2+\sum_{j=1}^{b-1}2^{b-j-1}(\kappa_{j+1}/2+\epsilon) +2^ba_0d-o(\epsilon)\\ &\qquad\ge d+(b-1)/4 -\bigl[(2^b-1)d+3b\,2^{b-1}\bigr]\epsilon-o(\epsilon) >d'+.03. \end{align*}\] For this calculation, (31) gives \(\kappa_{j+1}=2^{j-b}-(6\cdot2^j-2-2^{j-b})\epsilon\). Its leading contribution at depth \(j\) is \(2^{b-j-1}2^{j-b}/2=1/4\), which is the gain from the shared location of each forced sibling group. The bound \(d\le2.20+(B/4)D\) and the chosen \(\epsilon\) absorb the displayed corrections and leave the strict margin over \(d'=d+(b-1)/4-.05\).

For each \(r<r_*\), combine the fixed-shape estimates by Cauchy–Schwarz in (54). The noncentral and singleton terms are at most \(N^{-d'-1}\) in squared norm, and the branching terms have the margin just proved. Summing the finitely many degree norms and the tail in (52) yields \[\|G_+-G_-\|_{r_i}^2\le N^{-d'-.01},\] which proves Lemma 17.

Apply Lemma 8 to the preliminary laws \(\widetilde\mu_i,\widetilde\nu_i\), their common report \(D_0\), and the conditional densities (50). The typical report has probability \(1-o(\Delta)\), (52) supplies \(\rho=g_B\), and Lemma 17 supplies the density difference. Conditioning on the common event consisting of typical metadata and \(G_+\ge1/2\) gives laws \(\mu_i,\nu_i\) with the required domination and score. Each preliminary law changes by \(o(\Delta)\). The hidden-bit law was used only before this conditioning.

Together with (48), the new conditioning and failed-layout loss is at most \(\Delta\) for all large instances. The inherited loss is at most \((\prod_jT_j)E_{i-1}\le(\prod_jP_j)E_{i-1}=(\ell_i/\ell)E_{i-1}\). Thus one may take \[E_i\le\Delta+(\ell_i/\ell)E_{i-1},\qquad \frac{E_i}{\ell_i}\le\frac{\Delta}{\ell_i} +\frac{E_{i-1}}{\ell_{i-1}}\le(i+1)\Delta.\] The length and overlap conditions were proved in Section 5, so this completes Proposition 13. Starting from Proposition 9 and iterating the block proves Proposition 5.

Two-point testing with a strict exponent margin

For two equally likely hypotheses with observation laws \(P,Q\), every randomized decision rule has average success at most \((1+\mathop{\mathrm{TV}}(P,Q))/2\). If \(\varphi\) is the conditional probability of choosing the first hypothesis, its average success is \[\frac12\bigl(1+\mathbb E_P\varphi-\mathbb E_Q\varphi\bigr) \le\frac12(1+\mathop{\mathrm{TV}}(P,Q)),\qquad 0\le\varphi\le1.\] This is the standard two-point comparison; trace-reconstruction versions appear in Holden and Lyons (2020, Appendix A.2).

Fix \(0<c<c_+<1/(4\log2)\) and choose \(B,\zeta\) so that \[\alpha:=\frac{(1-\zeta)((B-1)/4-.05)}{B\log2}>c_+.\] The \(j_0\) preliminary blocks have fixed number depending only on \(B\), and therefore \[ d_D=\alpha\log H_{\rm del}+O_B(1). \tag{67}\] For an absolute constant \(a>0\) sufficiently small, (65) with \(m\le a n^{d_D}\) is strictly less than \(1/3\) eventually: its first term is at most \(\sqrt a\), and its second is at most \[2a(D+1)n^{d_D+1-100(d_D+B+1)}=o(1).\] Thus the maximal average success for the pair is at most \(2/3\) (in fact strictly less for all sufficiently large instances). Recall from the channel reduction in Section 1 that \(\log H_{\rm del}=\log(q^3\log n)+O(1)\) uniformly in \(q\). The strict inequality \(\alpha>c_+\) and (67) therefore imply \[ a n^{d_D}\ge n^{c_+\log(q^3\log n)} \tag{68}\] eventually. Exact worst-case reconstruction with success \(2/3\) would distinguish this pair with that success, so this proves the usual \(2/3\) lower bound, with the additional margin needed next.

Every fixed positive reconstruction success probability