Quantitative lower bounds for trace reconstruction

1 Introduction

For a binary word x and a known deletion probability q\in(0,1), let \Dcal_q(x) denote the law obtained by deleting each bit independently with probability q and concatenating the surviving bits in their original order. The retention probability is p=1-q. A sample from this law is a complete trace: its length and all surviving bits are observed, without the positions they occupied in x.

For s\in(0,1], let T_{q,s}(n) be the least nonnegative integer m for which an estimator, given n,q and m independent complete traces, recovers every x\in\{0,1\}^n with probability at least s. The estimator may be randomized and its computation is unrestricted. If no finite m suffices, set T_{q,s}(n)=+\infty. Write T_q(n)=T_{q,2/3}(n). Our lower bounds concern this fixed sample budget.

The varying-channel statement keeps the requested channel fixed throughout the construction for each instance; it is allowed to change only when the instance changes. The result gives a negative answer to the polynomial-sample question for deterministic binary inputs at every fixed deletion probability. A separate consequence concerns one-trace indistinguishability itself. For laws on the countable set of finite binary words, write

The channel is fixed independently of A. The proof of (1.2) uses an explicit score and approximation bound. Since the minimum is attained at every n, a single sequence of minimizing pairs realizes all the limits simultaneously.

1.1 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 [16]. 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 [3, Section 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 [17]. Holden and Lyons used a defect in an alternating background to prove \Omega(n^{5/4}/\sqrt{\log n}) [13, 14], and Chase obtained \Omega(n^{3/2}/\log^7 n) by a direct Hellinger calculation for a related pair [6]. 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)) [15], where \widetilde O suppresses polylogarithmic factors. Independently, De, O’Donnell, and Servedio and Nazarov and Peres improved it to \exp(O(n^{1/3})) [10, 18], and Chase obtained \exp(O(n^{1/5}\log^5 n)) [7]. 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 [5]. 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 [19].

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 [9]. Those deletion probabilities lie outside the regime q^3\log n\to\infty of Theorem 1.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 [1].

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 [10, 18]. Chen, De, Lee, and Servedio study a tolerance oracle for functions of contiguous blocks of trace coordinates [8]. 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)) [20]. Their arguments using translated segments and cancellation are related to the observation constructed in Section 6. Theorems 1.1 and 1.2 concern the entire trace law of one deterministic binary word.

1.2 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 [2, 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. [15, Section 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.

1.3 Distances and channel reduction

For probability laws P,Q, define overlap by \ov(P,Q)=1-\TV(P,Q), the largest mass of a common subprobability. Our squared Hellinger distance is

Cauchy–Schwarz and Hellinger affinity give \TV(P,Q)\le H(P,Q)\le\sqrt{2\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

These elementary inequalities also explain why a small likelihood score is an appropriate induction quantity.

For the rest of the proof put

We use \Tr(w)=\Dcal_\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

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.

2 The induction and global scales

The induction carries three estimates for each pair of deterministic words. Two auxiliary laws \mu,\nu can be postprocessed by one kernel to approximate the genuine trace laws, and the likelihood score d\nu/d\mu-1 has a small moment. These two estimates control distinguishability at the current length. The third estimate is common mass between traces of two consecutive powers of the first word; it supplies the hidden orientation bits used to construct the next pair.

Here is the quantitative idea behind the scale choices. Ignoring the small exponent margins, a block of depth b with target length N starts from atoms of length about N^{2^{-b}} whose squared score is at most N^{-2^{-b}d}. The low-degree analysis will either suppress a term by signed smoothing or force it to contain 2^b old-score factors. Those factors together retain approximately the decay N^{-d}. The joint locations of their sibling groups supply the additional decay N^{-(b-1)/4}. Sections 5–7 prove this estimate with the margins used below. They also verify the input strength needed to control high degrees and preserve consecutive-power overlap.

Fix 0<c<c_+<1/(4\log2), then choose a constant integer B\ge2 and 0<\zeta<1 such that

Set

We henceforth take D>j_0, as holds eventually. For either allowed block depth b, define the contraction exponent

It is positive for all sufficiently large instances. Define the target scales backwards by

and the score exponents by

Each preliminary depth-two block adds .20, so d_{j_0}=2.20+2^B. This fixed preliminary phase raises the seed exponent to the strength required by depth-B blocks. The remaining blocks produce the asymptotic gain in the theorem. The nested-overlap proof and the high-degree score estimate will show separately where this stronger input is used.

The remaining parameters control the accumulated projection error and rare events. Put

The even moment orders r_i are nonincreasing with i, so a moment bound available at one level is still available at the next. Their dependence on \log n/\log N_i makes the exceptional probabilities small relative to the final-length error budget even at the smallest scale.

In particular, \log r_i=O_B(D+1) uniformly in i. Equation (2.3) will control factors involving the channel, the number of blocks, and the fixed-depth calculations. Constants here and below may depend on B,\zeta,c_+. Unless additional dependence is explicit, constants in O, \asymp, \lesssim, and similar notation are absolute or depend only on fixed numerical parameters, such as a fixed degree cutoff; they do not depend on \delta,n,D,r_i. All estimates used at multiple levels are uniform over those levels as n\to\infty. In particular, the working rate \delta always has the value fixed from the original instance, not a value recomputed from N_i.

Distinct equal-length words each have an exclusive full-length trace of positive probability, so neither genuine trace law dominates the other. This motivates placing the likelihood score on auxiliary laws and recording their projection errors separately.

For every positive integer m, the first two conditions give

by Hellinger tensorization and telescoping the projection errors, as detailed in Section 8. This explains why the squared score carries the sample exponent d_i.

The pairs need not hit the target scales exactly. Padding is reserved for the final transfer and is not inserted into words used by later blocks.

The proof is by induction. Section 4 supplies level zero. Proposition 5.1 constructs the next level, with its observation and likelihood estimates proved in Sections 6–7. Section 8 applies the final common kernel and returns to complete traces.

3 Common mass, smoothing, and score moments

The induction needs three operations: converting overlap into hidden offsets, controlling multilinear score expansions, and conditioning on an event where the reference density is bounded below. We prove them with the uniformity needed later.

3.1 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. [17, Section 3.3] and the partial-trace construction in the proof of Holden and Lyons [13, 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 \ov(\Tr(w^k),\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.

3.2 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 [6, arXiv v2, Section 2]. The following version keeps the full moment and simulation-error budgets.

4 An initial pair at the working deletion rate

This section supplies the induction with a pair whose squared score decays as N_0^{-2.20} and whose repeated traces have enough common mass to hide later offsets. The initial words have one defect in each alternating period. A finite signed pattern moves some of these defects by one slot in opposite directions. We first describe an observation that forgets the original slot labels, then use its conditional rank probabilities for two purposes: obtaining common mass for pure runs and bounding the score of the signed pair.

4.1 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

Lemma 2.1 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

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

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 [6, 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

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 [2, 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

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 [13] 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

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 \Tr(H)=r_e\delta_\varnothing+(1-r_e)\nu_H.

Under \nu_{\mathsf A}, define

The defect law is dominated by the ordinary-block law. Its support is contained in \{\varnothing,1\}, where the likelihood ratios are

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.

4.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

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

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

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 (4.1) now gives

Define the slot gaps and rank gaps by

Their sums are n_b-r and l-r. Put \theta=l/n_b and f_g(z)=\Prob\{\operatorname{Bin}(g,\theta)=z\}. Counting returning untagged slots in each gap gives the exact kernel

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

For a tagged tuple define the coarse gaps

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.

4.3 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

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

Both densities are nondecreasing functions of the same coordinate likelihood values 1+Z\ge0: (4.1) 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 [11, 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

The count laws overlap on

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

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

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

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).

4.4 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

For every schedule the exceptional global period a+i has central index X+i, where

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

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

These densities all integrate to one under Q_l. In particular

with l read from \mathfrak d, and the analogous identity holds for P_{\rm pure}. This is the common conditional reference required by Lemma 3.3.

Call metadata typical when

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:

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 4.2 and 3.1 give

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 (4.3) and (4.11). Geometric summation, followed by Minkowski’s inequality when mixing over X, gives

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.

4.5 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

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.

4.6 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,

Each shift factor is exactly

For disjoint \mathcal D,\mathcal V\subseteq\{1,\ldots,r\}, write

The coefficient differences B_r=A_{r,+}-A_{r,-} and B_r^{\rm pure}=A_{r,+}-A_{r,\rm pure} come from (4.11). Here and below, \sum_{\mathbf j} runs over 1\le j_1<\cdots<j_r\le K. Expanding the shift factors gives

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.

From individual tuples to the full array. Within the increasing rank tuples 1\le v_1<\cdots<v_r\le l, define

These regions are disjoint. The first and internal coarse gaps determine the tuple, and any differing coordinate changes its center by at least \theta m\ge3m/4, more than the combined radii m/4. Bounded shifts of a kernel use the same region.

Fix one pattern and abbreviate its multiplier and operator by c_{\mathbf j} and \partial. Disjointness gives the weighted identity

The part outside these regions is negligible as an analytic coefficient estimate. To estimate it, expand D_h,V_h directly into tag shifts T_h, which preserve the total Km. Each resulting term is a fixed signed coefficient times a nonnegative shifted rank kernel. For each such kernel in \partial W_{\mathbf j}, the conditional binomial formula and Hoeffding’s inequality [12, Theorem 2] give

Indeed a bounded shift changes each relevant mean by O_r(1), while the excluded deviation is order m, and each gap has length at most Km+O_r(1). Dropping the total constraint and taking a union bound over i<r proves the display. There are at most K^r tuples, the multiplier is bounded by 1, and \partial is a fixed linear combination of shifted kernels. Using \|\cdot\|_2\le\|\cdot\|_1 for coefficient arrays, the discarded array has \ell^2 norm at most

It follows from (4.15) that the squared norm of the full array for this pattern is at most

This restriction does not condition a reported law or incur a total-variation error. Since m/K=N^{\eta+o(1)}, even (C_*r_0\delta^{-1})^r\tau_r=o(N^{-A}) for every fixed A, uniformly over the finitely many r<R_0.

Sums with one involved period fixed. The next two sums separate rank differentiation from the random location multiplier. For 1\le h\le r and an integer j, put

For r\ge2, let \Sigma_{r,h}^{\rm bd}(j) be the same sum restricted to tuples with \gamma_i\le|I| for some 1\le i<r.

The location multipliers. For the fixed metadata, (4.9) shows that every j\in\operatorname{supp}(\chi_{\rm seed}*\pi) satisfies j=K/2+O(J+|I|), and hence lies in [K/3,2K/3] for all large instances. Thus Lemma 4.4 applies to every involved period. For a sequence a on the integers, use the Fourier transform \widehat a(t)=\sum_j a(j)e^{ijt}. If M\ge\omega^2J/2 is the hidden count, then

Since

Parseval and the binomial decay give

The constants depending on s_0=300 are fixed.

The dyadic signs turn convolution into a high-order finite difference. The same cancellation algebra appears in Holenstein et al. [15, Section 3.2, equation (3.10)], where iterated input-position differences act on a mean-coordinate binomial kernel. Here the signs are convolved with the conditional location law inside a likelihood coefficient; the terms involving several scores require the separate gap estimate above.

In (4.14), a singleton \mathcal D=\{h\},\mathcal V=\varnothing has v'=1 and multiplier (\beta*\pi)(j_h). Every other surviving pattern has an odd positive number of D’s, so v'\ge3 and at least two indices are involved. At any chosen involved h,

A nonzero multiplier requires all involved periods to lie in a common translate of I. Two of them therefore differ by at most |I|-1, so some intervening internal gap is at most |I|.

For either kind of pattern choose such an involved h, and let \psi(j) be the corresponding envelope |(\beta*\pi)(j)| or (\chi_{\rm seed}*\pi)(j). Apply Lemma 4.3 and first sum over tuples with j_h=j:

Now (4.16) and (4.17) apply. Combining the finitely many patterns in (4.14) and the analytic tail gives

The nonlinear m^{-7/2} is m^{-3} from its minimum difference order and m^{-1/2} from the bounded internal gap. For B_r^{\rm pure}, the singleton D contribution is the same. Every other pattern has v'\ge2, but a singleton V requires no bounded internal gap. The full pure-comparison array therefore satisfies

4.7 Closing the initial invariant

For each fixed r<R_0, Lemma 3.1 converts the coefficient estimate to the required score estimate:

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 (4.18), at r=2, is

The singleton term is N^{-3.394+o(1)} at its worst degree r=1. The worst nonlinear term in (4.19) 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 (4.12). On every typical metadata value this yields

Let \mathcal A be the joint event of typical metadata and G_+^{\mathfrak d}(Y)\ge1/2, and define

Lemma 3.3 applies to the common conditional reference above: (4.12) gives \rho=.0009\ge2^{-4B-10}, and 2.22>2.20+.01 supplies its difference margin. Hence

and conditioning changes each preliminary law by o(\Delta) in total variation. By (4.10) and contraction under the same \mathcal K_0,

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,

On the complement use the bound G_++G_{\rm pure}. The high-moment estimate (4.12) 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 (4.20) gives

Projection by \mathcal K_0 gives the same upper bound for H^2(\Tr(x_0),\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,

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

Lemma 3.2, 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

Together with the length, distinction, score, and simulation estimates already proved, this completes Proposition 4.1.

5 One amplification block: words and overlap

We now construct one longer pair from the preceding oracle pair. This section defines the nested words and proves the consecutive-power overlap needed for their side runs. Section 6 constructs the observation of those words, and Section 7 proves its score estimate.

Fix i for the proof. The value C' meets the hypothesis of Lemma 3.2. Every preceding upper count bound remains true after replacing C by C', since its exponent 2Bh+M_B at a level h\ge0 is nonnegative; the lower count bounds, scores, and projection errors do not involve C. The enlarged constant still depends only on \delta and satisfies \log C'=O(\Lambda). We henceforth write C for C' and use this common enlarged constant in the counts constructed below and in later blocks.

Abbreviate

Within this block write a_0=a_0(b) for the contraction exponent defined in (2.1). Thus \ell\in[N^{a_0}/2,N^{a_0}]. Since r_i\le r_{i-1}, the old score satisfies

5.1 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

Let \mathcal I=\{0,\ldots,L-1\} and define the signs by

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 2.1 gives, uniformly,

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

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.

5.2 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

This recurrence and (2.1) give the identities

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

The \kappa_j are positive for all sufficiently large instances, uniformly in the block. Directly from (5.3),

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

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

For the root, choose

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

The overlap counts remain within the declared uniform bound. Indeed h_j\ge S_j by induction, and

because h_{j-1}/S_{j-1}\ge1 and C>2. Starting from the level-(i-1) bound gives

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

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

Here the count overhead is N^{o(\epsilon)} by (2.3), and 2a_{b-1}=1-\epsilon by (5.3). Thus also S_b\in[N/2,N]. Working backward from \kappa_b>\epsilon in (5.4) gives \kappa_j>\epsilon at every depth. The uniform loss bound (5.2) therefore gives L=o(T_j) and L=o(P_j) uniformly, so all motif labels used above fit. We take

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.

5.3 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.

6 An observation with randomly displaced windows

The nested words now have the overlap needed to hide their motif locations. We construct an auxiliary observation that reports the tree of windows and the side traces while retaining the hidden fair orientation bits. Its projection to a genuine trace is justified before any conditioning. The score proof will then condition only on the reported side data.

A related auxiliary experiment in the probability-vector model of Rivkin et al. [20, Section 3, Lemmas 6–8] exposes a binomially translated middle segment and separately deleted sides. That model draws fresh Bernoulli bits from the probability vector before each trace. Here the input is a fixed deterministic word, and the construction below proves the projection needed for that input.

6.1 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 5.3. 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

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.

6.2 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

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

Then the number of lower atoms before the window of Gu, counted from the start of the group, is

In (6.2), 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 (6.3). 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

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.

6.3 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

For every other level-j vertex I, j\ge1, put

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

6.4 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;

• •

  \Prob(\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 2.1 makes the resulting tail negligible relative to \Delta. For the last condition, apply Markov’s inequality to (6.8).

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.

7 Likelihood cancellation and the forced binary subtree

Fix the block of Proposition 5.1. For every supported exact value \mathfrak d of the report D_0 from Section 6.4, write \E_{\mathfrak d} for expectation over the remaining hidden bits with this report fixed. This expectation includes failed layouts; it is not conditioned on \mathcal F. The report space is countable, so its supported values carry its full law.

Let \mathcal L be the leaf set and use the conditional reference

For v\in\mathcal L, let Z_v be the old likelihood score at that coordinate. Under Q these variables are independent and centered, with \|Z_v\|_{r_i}^2\le N^{-a_0d} by (5.1). Conditional on the bits, the leaf of type -1 has density 1+Z_v and the leaf of type +1 has density one. Thus the two conditional surrogate densities are

For every supported \mathfrak d, these densities integrate to one because they are mixtures of product probability laws. The superscript on \tau records the root type.

We now fix a typical \mathfrak d for the proof of the lemma.

7.1 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

The margin between the old score and this number of possible positions is

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,

For b=B after the preliminary phase, d\ge2^B+2.20 and

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 (7.2) uniformly.

At fixed bits, Lemma 3.1 bounds the squared L^{r_i}(Q) norm of the homogeneous degree-r part of either density by

Convexity permits averaging over the bits at this bound. Geometric summation of the norms, using (7.2), gives

For the second inequality, r_*g_B(d+1)>d'+3 leaves the required margin. Only the fixed degrees 1\le r<r_* remain.

7.2 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

Lemma 3.1 reduces the squared norm of this degree to

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

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

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

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 (7.6)–(7.7) 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 (7.4) 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 (6.1). Hence such a term has conditional multiplier at most \Prob(\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 (5.5), so their contribution to the right side of (7.5) 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

the interval where their offsets share the global sum in (6.4).

7.3 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 (6.2) 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 (5.8) bounds the conditional multiplier by

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

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.

7.4 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

Every extra, nonforced selected leaf still contributes an absolute \chi constraint by (7.6). After discarding the other constraints, the absolute multiplier is at most a fixed scalar times

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 (6.2)–(6.4).

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 (7.8). At fixed bits each extra leaf has at most L labels satisfying its constraint, even if several constraints share bits. Hence

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.

7.5 The fixed-label anchor factorization

It remains to sum (\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

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

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

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,

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, (6.4) 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

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,

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

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 (7.13). No group estimate is invoked at coincident sibling IDs. Iterating this inequality from the leaves upward, and finally using (7.9), gives

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.

7.6 The exponent gain and closure

Combine the extra-label reduction, (7.15), 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 2.1 and (5.2). The squared degree contribution of a branching term is therefore at most

The last factor pays for every extra leaf and is at most one by (7.2). Using the lower bounds for J,t_j, the decay exponent of the remaining factors is at least

For this calculation, (5.3) 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 (7.5). 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 (7.3) yields

which proves Lemma 7.1.

Apply Lemma 3.3 to the preliminary laws \widetilde\mu_i,\widetilde\nu_i, their common report D_0, and the conditional densities (7.1). The typical report has probability 1-o(\Delta), (7.3) supplies \rho=g_B, and Lemma 7.1 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 (6.7), 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

The length and overlap conditions were proved in Section 5, so this completes Proposition 5.1. Starting from Proposition 4.1 and iterating the block proves Proposition 2.3.

8 Genuine traces, exact lengths, and testing

Proposition 2.3 now supplies the final pair and its auxiliary laws. We first retain a one-trace bound before using product observations. This proves the minimum-total-variation theorem independently of the sample-complexity deduction.

8.1 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+\TV(P,Q))/2. If \varphi is the conditional probability of choosing the first hypothesis, its average success is

This is the standard two-point comparison; trace-reconstruction versions appear in Holden and Lyons [13, Appendix A.2].

Fix 0<c<c_+<1/(4\log2) and choose B,\zeta so that

The j_0 preliminary blocks have fixed number depending only on B, and therefore

For an absolute constant a>0 sufficiently small, (8.1) 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

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 (8.3) therefore imply

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.

8.2 Every fixed positive reconstruction success probability