diff 0e0ec4d..8fb88fe exact_quantum_factoring_v2.txt
diff --git a/exact_quantum_factoring_v2.txt b/exact_quantum_factoring_v2.txt
index fd1da38..39d59d1 100644
--- a/exact_quantum_factoring_v2.txt
+++ b/exact_quantum_factoring_v2.txt
@@ -16,10 +16,12 @@ computing; each unfamiliar object is defined first. A qubit is a unit
vector in C^2; a gate is a unitary matrix of fixed size. Nothing is
hidden.
-How to read. First pass: Sections 1-2 for the map, then every lemma
-and theorem STATEMENT, skipping proofs. Second pass: the proofs. Each
-uses only earlier material plus the cited reference. Every proof is
-complete; nothing is waved away.
+How to read. Read the Notation table below the Contents first; it
+decodes every symbol at a glance. First pass: Sections 1-2 for the map,
+then every lemma and theorem STATEMENT, skipping proofs (Section 1.2,
+prior work, may be skimmed). Second pass: the proofs. Each uses only
+earlier material plus the cited reference. Every proof is complete;
+nothing is waved away.
Why "probability one" matters. No "with high probability" or "large
enough constant" arguments. Every probability is exact; every
@@ -46,6 +48,37 @@ Contents
A. An elementary polynomial-time primality test
Bibliography
+Notation and symbols
+--------------------
+
+Every symbol below is defined again where it is first used; this table
+is a map, not a substitute for the definitions.
+
+ N input integer, N >= 2; the number to factor.
+ n, B n = max(128, floor(log_2 N) + 1); B = 2^n; so N < B.
+ log logarithm base two everywhere (in bit counts).
+ G the fixed gate set: NOT, CNOT, Toffoli, H, S = diag(1,i),
+ their inverses, and their singly controlled versions.
+ dyadic a number of the form A / 2^T, with A an integer and T >= 0.
+ ord_m(a) order of a unit a modulo m: least r > 0 with a^r = 1 mod m.
+ phi(d) Euler totient (count of units mod d); phi(1) = 1.
+ lambda(d) 2^(-ceil(log_2 d) - 10); the exact target mass at d.
+ Q, b Q = B^16 = 2^b, with b = 16n: size of the phase register.
+ g the 1-periodic function, linear on quarter intervals and
+ equal to exp(-2 pi i z) at the quarter-integers.
+ k(d,j), eta k(d,j) = floor(jQ/d + 1/2) is the bin of fraction j/d;
+ eta = k(d,j) - jQ/d lies in [-1/2, 1/2].
+ P(d,j,t) squared modulus of (1/Q) times the sum of g(k x / Q)
+ over x = t mod d. A genuine probability when d = r.
+ U, S U(d,j,u): dyadic majorant of P; S(d,j): half its total.
+ c(d,j), rho a rounded factor of lambda/S and the leftover lambda - c S.
+ D(M), D auxiliary tree of factorizations; D = D(N) is all the data.
+ K, L, W K = n^5 draws per transition; L = n^10 slots; W = n(K+1) bits.
+ v_2(e) exponent of 2 in a positive integer e (2-adic level).
+ s exact probability that one transition outputs a good value.
+ z, delta per-slot mass z=1-2^-n; guess weight delta=2^-2n.
+ p_*, J prep success p_*=(1-2^-n)^(n^10); J=n^2 bits of a list.
+
SECTION 1. INTRODUCTION
-----------------------
@@ -1621,9 +1654,9 @@ Polynomial bounds. Each of the L conditional pass probabilities is a
dyadic with denominators dividing 2^E where E = W + 2n + 2 =
O(n^6), or from the transition's own s with denominators dividing
2^{(n+10)K} = 2^{n^6 + 10 n^5}. Both denominators have polynomial
-bit length. Evaluating the deferred tests over L slots, using the retained histories, costs
-polynomial time and workspace. The output string is polynomially
-long. This completes the proof. []
+bit length. Evaluating the deferred tests over L slots, using the
+retained histories, costs polynomial time and workspace. The output
+string is polynomially long. This completes the proof. []
Final bound. p_* = (1 - 2^{-n})^{n^{10}}. Bernoulli gives
(1 - 2^{-n})^{n^{10}} >= 1 - n^{10} 2^{-n}. At n = 128 the subtracted