diff f62dbea..b1f9bc4 trace_reconstruction_anchor_induction_v2.txt
diff --git a/trace_reconstruction_anchor_induction_v2.txt b/trace_reconstruction_anchor_induction_v2.txt
index 96dc7b6..02f3af4 100644
--- a/trace_reconstruction_anchor_induction_v2.txt
+++ b/trace_reconstruction_anchor_induction_v2.txt
@@ -7,32 +7,6 @@ A complete and readable account of the quasipolynomial sample bound
-========================================================================
-0. WHAT THIS DOCUMENT IS
-========================================================================
-
-This is a readable companion to a research paper about trace
-reconstruction. The paper proves an upper bound on how many independent
-deletion traces are needed to determine an unknown string of length n.
-
-The original is written for specialists. This version keeps every step
-and every constant, but explains each one in plain words. A reader who
-knows what a sequence is, what a probability is, and what a polynomial
-is should be able to follow the whole argument.
-
-Two warnings.
-
-First, this is a proof of an information-theoretic statement. It says:
-this many traces contain enough information to identify the string. It
-does not give a fast algorithm for extracting the string from the
-traces. The paper is explicit about this and so is this document.
-
-Second, the constants are enormous (10^100 appears). They are
-bookkeeping, chosen so that many inequalities are obviously true, not
-because anybody believes they are tight. Read them as "some fixed
-number large enough". The interesting content is in the exponents.
-
-
========================================================================
1. THE PROBLEM
========================================================================
@@ -142,56 +116,6 @@ Three things the theorem does not say.
become polynomial in n. Getting polynomial for any fixed p is open.
-========================================================================
-3. HOW THIS COMPARES WITH EARLIER WORK
-========================================================================
-
-The previous quantitative quasipolynomial estimate is due to
-Burudgunte, Valiant, and Wang, cited as BVW. Their Theorem 43 states a
-quasipolynomial bound with an unspecified log-power c and a p^{-7/3} in
-the exponent.
-
-If you unwind their proof (their Section 8) you find concrete
-prescriptions:
-
- b_old = ceil( log_{1.1} log_2 n )
- p_base = 3^{-b_old} min(p, 1/4)
- pair-test bound = 4 tau_base^{-2 C^{b_old}} for some C >= 1
- log(1/tau_base) = constant * d_base^{1/3} p_base^{-1/3}
- d_base = max( p_base^{-6}, O(1) )
-
-Even if you ignore the C^{b_old} multiplier entirely, the inverse
-retention term alone forces a log-power of at least
-
- (7/3) log_{1.1}(3) > 26
-
-for fixed p. The present result improves on that proved estimate. It is
-not a claim that no other optimization of BVW's approach could do
-better, and it does not go below quasipolynomial order for fixed
-0 < p < 1.
-
-What is genuinely new.
-
- The core idea is kept from BVW: test relations between phases using
- products of Fourier coefficients.
-
- The induction is different. It runs directly on generating functions
- of the source string, instead of on the pair-test structure.
-
- The phase argument is weighted and uses up to four factors at once.
-
- Masks are made spectrally compact: extra low-dimensional factors are
- propagated with a bounded frequency footprint. That lets the proof
- relax the angle budget during the induction and spend it at the very
- last step.
-
- The base case keeps the period-avoiding-word idea of Chase and
- Rubinstein.
-
-For polynomial-time bounds in the low deletion regime, see Chen, De,
-Lee, Servedio, and Sinha. See also the references at the end.
-
-
========================================================================
4. NOTATION AND THE TOOLS WE BORROW
========================================================================
@@ -282,54 +206,6 @@ finite partitions.
of n in any application.
-========================================================================
-5. THE SHAPE OF THE PROOF IN EIGHT STEPS
-========================================================================
-
-Here is the whole argument at a glance. Each step is expanded in a
-later section.
-
- STEP 1. Double the input. Prepend a long block of zeros that
- everybody knows. This makes room to work and puts the first mismatch
- far from the left end. Section 6.
-
- STEP 2. Look at several positions at once. A probe picks indices
- i_1 < ... < i_k, tests a predicate at each, and may force some
- adjacent pairs to be consecutive. Weighting by z to the power of the
- last index minus the mismatch position gives a polynomial H(z).
- Section 6.
-
- STEP 3. Set up an induction. At stage j the polynomial is large at a
- point near z = 1, at radius exp(-a_j). Each stage moves a much closer
- to 0, i.e. closer to the unit circle. Section 7.
-
- STEP 4. Base case. Build a probe out of a period-avoiding word whose
- occurrences are far apart, so H has the shape 1 - eta z^u plus a
- small tail; the Poisson inequality then supplies a pivot. Section 8.
-
- STEP 5. Step. Multiply by a Gaussian window, then run a phase test on
- the arc of radius exp(-a_j): either a product of two, three, or four
- Fourier coefficients is already large, or the deficit budget would be
- exceeded. The budget is a Cauchy-kernel vertex-cover statement.
- Section 9.
-
- STEP 6. Shuffle. Expand the products. Each copy contributes its own
- tuple; merge all copies into one big tuple with ties allowed. The
- phases collapse into one outer phase and r-1 inner phases in the
- differences between latest offsets. Section 10.
-
- STEP 7. Make the mask admissible. A Fourier expansion in the outer
- offset converts the Gaussian window into a compactly supported
- frequency measure, giving a legitimate mask of the new level.
- Sections 11 and 12.
-
- STEP 8. Stop and count. Expand all masks, pick one frequency
- combination, interpolate the loose-edge parameters with Hadamard
- three-lines, build a bounded trace statistic whose expectation
- differs between the two candidates, and apply Hoeffding plus a union
- bound over all 2^n rivals. Sections 13, 14, 15.
-
-
========================================================================
6. DOUBLING, ANCHORS, PROBES, AND THE DIFFERENCE POLYNOMIAL
========================================================================
@@ -1742,124 +1618,6 @@ 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
========================================================================