diff 45db8d1..62f1989 trace_reconstruction_anchor_induction_v2.txt
diff --git a/trace_reconstruction_anchor_induction_v2.txt b/trace_reconstruction_anchor_induction_v2.txt
index 6b2f7fa..73a5c0b 100644
--- a/trace_reconstruction_anchor_induction_v2.txt
+++ b/trace_reconstruction_anchor_induction_v2.txt
@@ -1191,3 +1191,403 @@ the negligible log term; the total is below 1.203 B. Hence (11.1).
Interpretation. K is a Gaussian bump in g. For now it decays like
exp(-epsilon t |g|_1), which is the (M1) behaviour, before we make it
compact.
+
+
+========================================================================
+12. RADIAL COMPACTIFICATION
+========================================================================
+
+12.1 Applying the expansion.
+
+Each fixed-omega discrepancy contribution, after the expansion, is a
+merged sum with new outer factor
+
+ exp( -t Y_0 + i (omega + theta_1 + ... + theta_r) Y_0 )
+
+and inner phases exp(-i theta_s g_s), plus K(g, omega). Its modulus is
+at most 2 Z_{j+1}/(1 - exp(-t)) <= exp(10^{-8} B), apart from the outer
+factor exp(1.203 B), because every merged loose edge has coverage and
+(11.1) applies. Latest offsets Y_0 < 0 cancel exactly, leaving Y_0 >= 0
+and hence a geometric sum from the outer damping.
+
+Where |omega + theta_1 + ... + theta_r| > 5t, the Gaussian factor is at
+most
+
+ exp(1.2031 B) * 2 exp( -(4.99)^2 (1 - zeta) 2.4 B / 8 )
+ = o( exp(-6B) ),
+
+uniformly over categories, after multiplying by P = exp(o(B)). So only
+the range |omega + theta_1 + ... + theta_r| <= 5t matters.
+
+12.2 Making the mask compact.
+
+We must replace K(g, omega), for the retained omega, by an admissible
+K^c(g, omega) with
+
+ | K(g) - K^c(g) | <= exp(-20B) exp( -epsilon t sum_s g_s ). (12.1)
+
+Everything is uniform on |omega| <= 5.01 t and measurable in omega.
+
+Fix omega. Put R = R_j; recall R/t = (j+1)^2 M_j/L_j >= 1. Choose a
+large absolute constant H_0 and set
+
+ W = H_0 B / t
+ tau^2 = W / R
+ U(x) = (1/(tau sqrt(2 pi)))
+ * int_{-W}^{W} exp( -(x - v)^2/(2 tau^2) ) dv.
+
+So U is a smoothed indicator of the interval [-W, W].
+
+CLAIM 12.1.
+
+ | K(g) - K(g) prod_{s<r} U(g_s) |
+ <= (1/4) exp(-20B) exp( -epsilon t sum_s g_s ) for g_s >= 0.
+
+Proof. If all g_s <= W/2, use
+
+ 1 - U(g_s) <= 2 exp( -W^2/(8 tau^2) ) = 2 exp(-R W/8)
+ = 2 exp(-H_0 B/8),
+
+and then (11.1). If some g_s > W/2, use Q(g) >= W^2/(4r), by Cauchy
+together with g_r = 0. That makes the Gaussian factor in the derivation
+of (11.1) at most exp(-c W^2/sigma^2) = exp(-c H_0^2 B/2.4); and
+0 <= U <= 1.
+
+Now form the entire function of d' = r-1 variables
+
+ J_cal(g) = exp( R sum_s g_s ) K(g) prod_{s<r} U(g_s),
+
+and its inverse transform
+
+ J_cal_hat(lambda) = (2 pi)^{-d'}
+ int_{R^{d'}} J_cal(g) exp(-i lambda . g) dg.
+
+CLAIM 12.2. There are absolute constants C_2, C_3, allowed to depend on
+H_0, with
+
+ int |J_cal_hat(lambda)| dlambda <= exp( C_2 R W ), (12.2a)
+
+ int_{|lambda|_inf > C_3 R} |J_cal_hat(lambda)| dlambda
+ <= (1/4) exp(-20B). (12.2b)
+
+Sketch of proof. Continue the integral formula for K to complex
+g = x - i y, with x and y real vectors in R^{d'} and the last coordinate
+set to zero. Using Re Q(x - i y) = Q(x) - Q(y), one gets
+
+ |K(x - i y)| <= exp( C_4 B + C_4 t sum_{s<r} (|x_s| + |y_s|)
+ + C_4 |y|_2^2/sigma^2 ).
+
+Also
+
+ |U(x_s - i y_s)| <= (2W/(tau sqrt(2 pi)))
+ * exp( ( y_s^2 - max(|x_s| - W, 0)^2 ) / (2 tau^2) ).
+
+Shifting g = x - i y in J_cal_hat by y, which is legal because of
+Gaussian tail decay in every real direction, and using
+
+ max(|x_s| - W, 0)^2 >= x_s^2/2 - W^2
+
+to complete squares, gives
+
+ |J_cal_hat(lambda)| <= tau^{d'}
+ exp( C_5 R W + C_5 |y|_2^2 / tau^2 - lambda . y ).
+
+Take y = tau^2 lambda/(2 C_5). This leaves a Gaussian envelope in
+lambda. Integrating in lambda proves (12.2a) and (12.2b).
+
+Finally define
+
+ K^c(g) = exp( -R sum_s g_s )
+ int_{|lambda|_inf <= C_3 R} exp( i lambda . g )
+ J_cal_hat(lambda) dlambda.
+
+Fourier inversion, valid because both J_cal and its transform are
+integrable, together with Claim 12.1 and (12.2b), gives (12.1).
+Combining (11.1) and (12.1) shows K^c also obeys the quadrant decay
+|K^c| <= (some absolute constant) exp(-epsilon t sum g_s), and (12.2b)
+gives the complex-measure representation with |xi|_inf <= C R_j and
+total variation at most exp(C (R_j/t_j) B_j), after enlarging C once.
+
+This completes the construction of stage j+1 from stage j.
+
+
+========================================================================
+13. STOPPING: FROM MASKS TO PHASE PARAMETERS
+========================================================================
+
+We now have a_j n <= .001, j <= b, and the pivot point
+z_0 = exp(-a_j + i theta).
+
+13.1 One frequency choice.
+
+Expand all retained masks by their compact representations (M2). The
+total variation of the product measure is at most
+
+ exp( C sum_{h<j} 4^{j-h-1} (R_h/t_h) B_h )
+ <= exp( O( ell_* 8^b (b+1)^6 ) ). (13.1)
+
+Check. We have R_h/t_h = (h+1)^2 2^{b-h} and
+B_h = 10^100 ell_* 8^h (b+1)^3, so
+
+ 4^{j-h-1} (R_h/t_h) B_h
+ <= 4^{j-1} 2^b (h+1)^2 10^100 ell_* (b+1)^3,
+
+and summing over h <= j <= b gives 8^b (b+1)^3 times a polynomial in b.
+
+At every set of frequencies in the product integral, the difference
+contribution is still a finite sum. So by the pivot magnitude and
+(13.1), some frequency choice has an unintegrated discrepancy of
+magnitude at least
+
+ exp( -O( ell_* 8^b (b+1)^6 ) ).
+
+Fix it.
+
+13.2 Reading off a pure product probe.
+
+A mask now contributes, for each of its differences g_s, a number
+
+ exp( -R_h g_s + i (beta_s + xi_s) g_s ),
+
+with |xi_s| <= C R_h and |beta_s| <= 10^4 a_h.
+
+Assign these factors edgewise. Each g_s is a sum of consecutive gap
+distances in the merged tuple, so each factor becomes a product of
+per-edge factors. Drop factors on exact edges; they are scalars of
+modulus at most 1 and nonzero. What remains is a pure product probe:
+bit predicates, exact constraints, and, on each loose edge e, a complex
+number
+
+ z_e^* = exp( -eta_e + i phi_e ).
+
+CLAIM 13.1. There is an absolute c_0 in (0,1] with
+
+ kappa(z_e^*) := Re ( (1 + z_e^*)/(1 - z_e^*) )
+ = (1 - |z_e^*|^2) / |1 - z_e^*|^2
+ >= c_0 q. (13.2)
+
+Proof. Let the sum over covering differences be counted with
+multiplicity. Because every loose edge is covered, eta_e, the sum of the
+relevant R_h, is strictly positive. The frequency perturbations sum to
+at most C eta_e in absolute value, and the beta's satisfy
+
+ (sum beta_s)^2 <= eta_e sum_h (10^4 a_h)^2/R_h
+ <= C_6 (eta_e/q) sum_h 1/(h+1)^2
+ = O( eta_e/q ),
+
+using at most 3 * 4^{j-h-1} <= M_h coverings per level h. When
+eta_e <= 1, we have
+
+ 1 - |z_e|^2 = 1 - exp(-2 eta_e) >= (1 - e^{-2}) eta_e
+
+and |1 - z_e|^2 <= C_7 eta_e/q, because
+
+ |1 - z|^2 = 1 - 2 exp(-eta) cos phi + exp(-2 eta)
+ ~ eta^2 + phi^2 <= C (eta^2 + eta/q).
+
+When eta_e > 1, use |1 - z_e| <= 2 and 1 - |z_e|^2 >= 1 - e^{-2}.
+
+For the root itself, kappa(z_0) >= 4/p. Because |1 - z_0| <= 6 a_j and
+1 - |z_0|^2 >= a_j, and a_j <= .001/n, we get
+
+ 1/(36 a_j) >= 1000 n/36 >= 4 n >= 4/p,
+
+since p >= 1/n.
+
+
+========================================================================
+14. INTERPOLATION AND THE TRACE STATISTIC
+========================================================================
+
+14.1 A one-parameter family of edge arguments.
+
+Put
+
+ S = 4/(p c_0),
+
+and let varsigma be a complex variable in the strip
+1/2 <= Re varsigma <= S.
+
+For each loose edge e, write
+
+ alpha_e + i delta_e = (1 + z_e^*)/(1 - z_e^*).
+
+By (13.2), alpha_e = kappa(z_e^*) >= c_0 q. For each exact edge, set the
+target z_e^* = 0, i.e. alpha_e = 1 and delta_e = 0. Define
+
+ z_e(varsigma) = (alpha_e varsigma + i delta_e - 1)
+ / (alpha_e varsigma + i delta_e + 1).
+
+Then z_e(1) = z_e^* and
+
+ kappa( z_e(varsigma) ) = alpha_e Re varsigma.
+
+At Re varsigma = S this is at least c_0 q S = 4 q/p.
+
+14.2 The interpolating function.
+
+Let K_ex = k - A be the number of exact edges. Define G(varsigma) as the
+difference sum at z_0 with the following substitutions:
+
+ each exact-edge selector on source distance Delta becomes
+ z_e(varsigma)^{Delta - 1}, so Delta = 1 gives 1, as before;
+
+ each loose edge at source distance Delta uses z_e(varsigma)^Delta;
+
+ the whole sum is normalized by n^{-A} (1 + varsigma)^{-2 K_ex};
+
+ all negative latest-offset terms are cancelled.
+
+So at an exact edge the weight relaxes from a strict constraint to a
+geometric sum over possible source distances, and the value 1 of that
+sum at varsigma = 1 recovers the original constraint.
+
+CLAIM 14.1.
+
+ (a) |G(varsigma)| <= 2 on the entire strip.
+
+ (b) At varsigma = 1,
+
+ log |G(1)| >= -A log n - 2 K_ex log 2
+ - O( ell_* 8^b (b+1)^6 )
+ = -O( ell_* 8^b (b+1)^6 ). (14.1)
+
+Proof of (a). For an exact edge, the sum over Delta >= 1 of
+|z_e|^{Delta - 1} equals 1/(1 - |z_e|). Since alpha = 1 and delta = 0,
+
+ 1 - |z_e|^2 = 4 Re varsigma / |1 + varsigma|^2,
+
+so this costs at most 1 against the normalization |1 + varsigma|^{-2},
+per exact edge. For the other edges, use at most n choices per gap and
+modulus at most 1.
+
+Proof of (b). Use k <= 2 P_0 4^b = O(8^b), A <= 4^b, and
+log n <= ell_* 2^b.
+
+14.3 Hadamard three-lines.
+
+Apply the three-lines theorem on the vertical strip
+1/2 <= Re varsigma <= S, with bounds |G| <= 2 on both vertical edges.
+The right-line weight of the point Re varsigma = 1 is
+(1/2)/(S - 1/2). So there is a point varsigma of the strip with
+Re varsigma = S and
+
+ |G(varsigma)| >= exp( -O( p^{-1} ell_* 8^b (b+1)^6 ) ). (14.2)
+
+14.4 The disk of radius p centred at q.
+
+The following algebraic fact is the bridge from analytic parameters to
+actual traces.
+
+ FACT (product ratio). For u and v in the open unit disk with
+ kappa(u), kappa(v) > 0,
+
+ |1 - u v|^2 / (1 - |u v|^2)
+ <= |1 - u|^2/(1 - |u|^2) + |1 - v|^2/(1 - |v|^2). (14.3)
+
+ Proof: 1 - uv = (1 - u) + u(1 - v), then the weighted
+ Cauchy-Schwarz inequality with weights (1 - |u|^2) and
+ |u|^2 (1 - |v|^2), whose sum is exactly 1 - |uv|^2.
+
+Apply (14.3) with u = z_0, which has kappa >= 4/p, and v =
+z_e(varsigma), which has kappa >= 4q/p. The right side is at most
+
+ p/4 + p/(4q) <= p/(2q).
+
+So, for y_e = z_0 z_e(varsigma),
+
+ |1 - y_e|^2 / (1 - |y_e|^2) <= p/(2q).
+
+Use the identity
+
+ p^2 - |y - q|^2 = p(1 - |y|^2) - q |1 - y|^2.
+
+Combining with the previous line gives, for y = y_e,
+
+ p^2 - |y_e - q|^2 >= (p/2)(1 - |y_e|^2)
+ >= (p/2)(1 - |z_e|^2).
+
+The same computation applies to z_0 itself.
+
+So z_0 and y_1,...,y_{k-1} all lie in the closed disk of centre q and
+radius p. Define
+
+ lambda_e = (y_e - q)/p, lambda_0 = (z_0 - q)/p.
+
+All have modulus at most 1. Moreover
+
+ 1 - |lambda_e| >= (1 - |z_e|^2)/(4p). (14.4)
+
+Proof: p - |y_e - q| >= (p^2 - |y_e - q|^2)/(2p) >= (1 - |z_e|^2)/4,
+then divide by p.
+
+14.5 The trace statistic.
+
+Given a trace U of the extended input, define
+
+ T(U) = n^{-A} (1 + varsigma)^{-2 K_ex}
+ * sum over 0 <= s_1 < ... < s_k < |U|
+ of lambda_0^{s_1}
+ * prod_{e=1}^{k-1} lambda_e^{ s_{e+1} - s_e - 1 }
+ * prod_{e=1}^{k} chi_e( U_{s_e} ).
+
+CLAIM 14.2. |T(U)| <= 1 for every trace.
+
+Proof. Expand the sum over the exact-edge gaps. For an exact edge the
+geometric weight over possible source distances Delta is
+sum_{Delta >= 1} |lambda_e|^{Delta - 1} = 1/(1 - |lambda_e|). By (14.4)
+together with 1 - |z_e|^2 = 4 S/|1 + varsigma|^2,
+
+ 1 - |lambda_e| >= (1 - |z_e|^2)/(4p) = S/(p |1 + varsigma|^2).
+
+So the geometric sum is at most p |1 + varsigma|^2/S. After its share
+|1 + varsigma|^{-2} of the normalization, each exact edge contributes at
+most
+
+ p/S = p^2 c_0/4 <= 1.
+
+The loose edges, of which there are A-1, contribute at most n each,
+because there are at most n possible gap lengths. The first index s_1
+ranges over at most n values. Together with the normalization n^{-A},
+the choices of the A block starts cost at most 1.
+
+The bit predicates are bounded by 1.
+
+14.6 The expectation gap.
+
+Condition on the survival of the source symbols at the tuple positions.
+Each survives independently with probability p. If all k chosen positions
+survive, the symbols observed there are exactly x's bits at those
+positions. The counts of survivors before s_1 and between consecutive
+s_e have independent binomial laws.
+
+By linearity of expectation, and the identity
+
+ q + p lambda_0 = z_0,
+ q + p lambda_e = z_0 z_e for each loose edge e,
+
+together with the fact that at an exact edge the exponent is zero (there
+are no survivors strictly between two forced-consecutive positions, so
+both sides contribute 1), we get
+
+ E_x T - E_y T = p^k z_0^{d - k + 1}
+ * ( prod over loose e of z_e(varsigma)^{-1} )
+ * G(varsigma).
+
+The powers of z_0 and z_e reorganize the inner sum into exactly
+G(varsigma) times an overall factor.
+
+Modulus of the prefactor. We have
+
+ |z_0|^{d - k + 1} >= exp(-a_j n) >= exp(-.001),
+ because a_j n <= .001 and d - k + 1 <= n;
+
+ |prod over loose e of z_e^{-1}| >= 1,
+ because each |z_e| < 1 at Re varsigma = S, and |z_e| > 0 by (14.2);
+
+ p^k >= exp(-k log(1/p)) >= exp(-O(8^b/p)),
+ because k = O(8^b) and log(1/p) <= 3/p.
+
+So, by (14.2),
+
+ |E_x T - E_y T| >= exp( -O( p^{-1} ell_* 8^b (b+1)^6 ) ). (14.5)