diff 62f1989..142170b trace_reconstruction_anchor_induction_v2.txt
diff --git a/trace_reconstruction_anchor_induction_v2.txt b/trace_reconstruction_anchor_induction_v2.txt
index 73a5c0b..1769544 100644
--- a/trace_reconstruction_anchor_induction_v2.txt
+++ b/trace_reconstruction_anchor_induction_v2.txt
@@ -1591,3 +1591,307 @@ Modulus of the prefactor. We have
So, by (14.2),
|E_x T - E_y T| >= exp( -O( p^{-1} ell_* 8^b (b+1)^6 ) ). (14.5)
+
+
+========================================================================
+15. COUNTING TRACES
+========================================================================
+
+We now have a bounded statistic T with an expectation gap (14.5). That
+is an information statement. To turn it into a reconstruction rule, use
+Hoeffding and a union bound.
+
+15.1 One pair.
+
+Fix x and y. Let delta = |E_x T - E_y T|. By Claim 14.2, T takes
+values in [0,1] after the harmless shift T -> (T + 1)/2, which does not
+change the gap.
+
+Hoeffding's inequality: with N independent traces, the empirical
+average of T deviates from its mean by delta/2 with probability at most
+2 exp(-N delta^2/2). So
+
+ N = O( delta^{-2} log(1/eps) ).
+
+With eps = e^{-2n} this is
+
+ exp( O( p^{-1} ell_* 8^b (b+1)^6 ) + log(2n) ),
+
+and since the first term grows like a fixed power of log n while
+log(2n) does not, the whole exponent is O( p^{-1} ell_* 8^b (b+1)^6 ).
+So this many traces distinguish x from y with error at most e^{-2n} per
+pair, uniformly over pairs.
+
+15.2 All pairs at once.
+
+There are 2^n binary strings of the doubled length. By the union bound
+over all 2^n challengers y for the true x,
+
+ total error <= 2^n * e^{-2n} = (2/e^2)^n < 1/3 for n >= 1.
+
+So that many traces suffice to recover x from its traces with
+probability at least 2/3, simultaneously for every x.
+
+15.3 The final bound.
+
+Substitute the constants:
+
+ N = exp( O( p^{-1} ell_* 8^b (b+1)^6 ) ).
+
+Since 2^b <= 2X and ell_* X <= 1 + 2 log n, this is
+
+ exp( O( p^{-1} (log n) X^2 (1 + log X)^6 ) ),
+
+which is Theorem 2, and in turn
+
+ exp( O( p^{-1} (log n)^3 (1 + log log(2n))^6 ) ),
+
+which is Theorem 1.
+
+For completeness, the steps in detail. We used the doubled length n
+throughout. Switching back to the original length changes the exponent
+by at most an absolute factor, since doubling n only changes log n by
+an additive constant.
+
+The exponent is p^{-1} ell_* 8^b (b+1)^6 times an absolute constant.
+We have
+
+ 2^b <= 2 X (by the definition of X),
+ ell_* X <= 1 + 2 log n (since ell_* = 1 + log(1/q) and q >= 1/n).
+
+So
+
+ p^{-1} ell_* 8^b (b+1)^6
+ <= p^{-1} ell_* (2X)^3 (1 + log_2(1 + log n/ell_*) + 1)^6
+ <= O( p^{-1} ell_* X^3 (1 + log X)^6 )
+ <= O( p^{-1} (log n) X^2 (1 + log X)^6 ),
+
+because ell_* X <= 3 log n for n >= 3. This is Theorem 2.
+
+The cruder form, Theorem 1, follows because X <= 1 + log n, as
+ell_* >= 1. Then X^2 (1 + log X)^6 <= (log n)^2 (1 + log log(2n))^6
+times an absolute constant, and multiplying by log n gives
+(log n)^3 (1 + log log(2n))^6.
+
+The polynomial case, Theorem 3. Suppose q <= n^{-epsilon} for fixed
+epsilon > 0. If q = 0, one trace suffices. Otherwise
+ell_* >= 1 + epsilon log n, so X <= 1 + 1/epsilon while p >= 1/2 for
+large n. Hence the exponent is at most O(log n), and polynomially many
+traces suffice.
+
+Two honest remarks about this counting.
+
+ The bound counts how many traces suffice in principle. The rule that
+ uses them is allowed to be infeasible to compute: it may need to
+ search over all candidates, evaluate the test on each pair, and so
+ on. That is consistent with the statement of the theorem, which only
+ speaks about information.
+
+ An equivalent, more elementary way to say the same thing: the
+ expectation gap of a bounded real test implies, by total variation, a
+ gap at least half as large for an optimal indicator test. The
+ optimal indicator test for a binary pair is simply the one that
+ counts how many times each trace appears as a subsequence of each
+ candidate. Each trace word's probability under x is its embedding
+ count as a subsequence of x, times a length-dependent factor that is
+ the same for x and y. So the sample complexity already contains the
+ subsequence-count test, and the bounded statistic is only an
+ analytical device for proving the gap.
+
+
+========================================================================
+16. GENERAL ALPHABETS
+========================================================================
+
+Let Sigma be the alphabet, with |Sigma| <= n after the small-case
+reduction.
+
+16.1 A preliminary pass to see all symbols.
+
+Collect ceil(p^{-1} log(12n)) preliminary traces. By a union bound over
+the n source positions, with probability at least 11/12 every source
+symbol appears somewhere in these traces. Indeed a given position
+survives none of them with probability
+
+ (1-p)^{ceil(p^{-1} log(12n))} <= exp(-log(12n)) = 1/(12n),
+
+and there are n positions.
+
+Let S be the set of observed symbols. Always |S| <= n.
+
+16.2 Reducing to binary.
+
+Condition on success.
+
+On independent fresh traces, run the binary test for every ordered pair
+of candidate strings in S^n. For a pair (a,b) whose first disagreement
+is at position i, map symbols to bits by the indicator of the symbol
+a_i, that is, send a_i to 0 and every other symbol to 1 (or do the
+symmetric thing). Then a and b project to two distinct binary strings,
+and the binary pair test distinguishes those projections, hence a from
+b.
+
+The Hoeffding sample size is multiplied by O(log n) so that the
+per-pair error is at most e^{-3n log n}. Since there are at most
+n^{2n} = e^{2n log n} ordered pairs, the union bound over all pairs gives
+total error at most e^{-n log n} < 1/3. So a log n factor on top of the
+same sample budget works.
+
+Output a candidate that wins all its comparisons, or declare failure if
+there is none.
+
+The remaining cases are the bounded-size ones and the cases
+min(p, 1-p) < 1/n; those are handled directly by the full-length-trace
+strategy of section 6.1, and the increase does not affect the stated
+asymptotic budget.
+
+This extension concerns sample complexity only.
+
+
+========================================================================
+17. WHAT IS AND IS NOT PROVED
+========================================================================
+
+A short list, so that nothing here is oversold.
+
+ Sample complexity, not computation. The theorem says: this many traces
+ contain enough information. It does not give a fast algorithm. The
+ union-bound recovery step explicitly has no assertion of efficiency
+ and does not rely on computational checking or search as a proof.
+
+ Not optimality. The true number of traces needed might be much
+ smaller. No matching lower bound is claimed.
+
+ Quasipolynomial, not polynomial, for fixed p in (0,1). The bound here
+ does not reach polynomial order except when q is polynomially small
+ in n. Getting polynomial for fixed p is open.
+
+ Improvement relative to BVW's proved quantitative estimate, not to
+ every possible optimization of their approach. The comparison of
+ section 3 is against their Theorem 43 as stated, unwound through
+ their Section 8.
+
+ Absolute constants are enormous. 10^100 and 10^16 appear in the
+ bookkeeping. They are chosen so that many inequalities are obviously
+ true, not because anybody believes they are tight. A careful audit
+ would shrink them. The interesting content is the shape of the
+ exponent, not the size of the constants.
+
+ Binary first, general alphabet second. The main proof is for binary
+ strings with a known prefix; the general-alphabet extension reduces
+ to the binary case after a preliminary sampling step. The surviving
+ symbols are assumed to be observed exactly, with no substitution
+ errors.
+
+
+========================================================================
+18. GLOSSARY
+========================================================================
+
+ trace the survivors of a deletion channel, in order,
+ with their original positions unknown
+
+ retention p the probability that any given symbol survives
+
+ trace reconstruction
+ the problem of recovering a string from traces
+
+ sample complexity the number of traces needed
+
+ worst case the bound must hold for every possible string
+
+ quasipolynomial of the form exp((log n)^C) for a fixed C
+
+ Poisson kernel the harmonic-measure weight on a circle
+
+ Hadamard three-lines
+ log-convexity of the sup norm on vertical lines
+
+ probe a tuple of indices plus predicates and exact-gap
+ constraints plus masks
+
+ mask a factor with a bounded-modulus K and a compact
+ measure representation, attached to differences
+
+ anchor the last index of the tuple, taken relative to
+ the first mismatch of the two candidates
+
+ Fine and Wilf a word with periods p and q and length at least
+ p + q - gcd(p,q) has period gcd(p,q)
+
+ Hoeffding an average of N independent bounded variables
+ deviates from its mean with probability at most
+ 2 exp(-2 N t^2)
+
+ total variation of a complex measure: the largest value of the sum
+ of absolute values over a partition
+
+ vertex cover a set of vertices hitting every edge
+
+ fractional cover the same with vertex numbers in [0,1] and
+ endpoint sums at least 1
+
+
+========================================================================
+19. A READING GUIDE
+========================================================================
+
+If you want the headline result only. Read sections 1, 2, and 17. Skip
+everything else.
+
+If you want the shape of the argument. Read sections 5, 6.4, 6.5, 6.6,
+7, and 8. That gives the induction, the base case, and the meaning of
+the probe.
+
+If you want to understand the phase test. Read section 9 to the end of
+9.3, including the table of numerical constants. The table is the only
+place where concrete numbers are checked; everything else is
+bookkeeping.
+
+If you want to understand the shuffle and the spectral compactness.
+Read sections 10, 11, and 12. The key sentence is (M2): a mask is an
+average of pure phases with bounded frequencies. Once you believe that,
+the induction is just bookkeeping.
+
+If you want to understand the final counting. Read section 14.4, which
+says z_0 and all the y_e lie in the disk of centre q and radius p, and
+then 14.5 and 15. The disk is what makes the trace statistic bounded;
+the expectation gap and Hoeffding do the rest.
+
+If you want to check the arithmetic. Read the table in 9.4 and the
+size bound in 8.5. Those are the two places where an actual number
+needs to come out right.
+
+What to skip on a first reading. Everything in 12.2 and 12.3. Those
+sections make the mask admissible; they do not add intuition.
+
+
+========================================================================
+20. REFERENCES
+========================================================================
+
+ Burudgunte, Valiant, Wang. "A polynomial-time algorithm for the
+ deletion channel." These are the BVW references in the text.
+
+ Chase. "Separating words and trace reconstruction." The
+ period-avoiding word base.
+
+ Chen, De, Lee, Servedio, Sinha. The low-deletion setting, cited as
+ CDLS.
+
+ Fine and Wilf. "Uniqueness theorems for periodic functions." The
+ period lemma.
+
+ Hoeffding. "Probability inequalities for sums of bounded random
+ variables." The concentration used in section 15.
+
+ Rubinstein. "Explicit separating words." The period and separation
+ ideas used in section 8.
+
+ For later developments, see the recent work on trace reconstruction
+ problem. arXiv:2207.11489.
+
+
+========================================================================
+END
+========================================================================