diff 295faa5..a62ba7d two_way_nondeterministic_complement_v2.txt
diff --git a/two_way_nondeterministic_complement_v2.txt b/two_way_nondeterministic_complement_v2.txt
index 91a726e..3b99dec 100644
--- a/two_way_nondeterministic_complement_v2.txt
+++ b/two_way_nondeterministic_complement_v2.txt
@@ -97,10 +97,14 @@ state and scanned symbol.
 --------------------------------------------------------------------------------
 
 A binary relation on a set X is a set of ordered pairs, i.e. a subset of
-X x X.  We write "a R b" as shorthand for "(a,b) is in R".
+X x X.  We write "a R b" as shorthand for "(a,b) is in R".  For example,
+on X = {1,2,3}, the relation R = {(1,2),(2,3)} says 1 R 2 and 2 R 3.
 
 Relations compose in PATH ORDER: a (R S) b holds iff there is some c with
-a R c and c S b.  So we apply R first and then S.
+a R c and c S b.  So we apply R first and then S.  In the example above,
+R R = {(1,3)}: from 1 we reach 2 via R, then 3 via R; no other pairs
+survive.  The EMPTY relation (the empty set of pairs) has no pairs at all,
+and the IDENTITY relation I_X = {(p,p) : p in X} leaves every p fixed.
 
 Fix the set H of h = n-2 points.  Let
 
@@ -150,9 +154,6 @@ the machine accepts w iff r(w) is nonempty.  For the empty word the guessed
 p_0 sits immediately on the right endmarker and stays into q_acc, so the
 empty word is also accepted, matching r(epsilon) = I_H nonempty.  QED
 
-The task is now to show that the COMPLEMENT (Sigma^* minus L_H) needs
-exponentially many states, even for a nondeterministic two-way machine.
-
 --------------------------------------------------------------------------------
 3.  PATH DIAGRAMS
 --------------------------------------------------------------------------------
@@ -558,13 +559,27 @@ P_e (K_e F_e) = K_e F_e let us move from p to any q in C, using q P_e p and
 p P_e q, without changing the set; the two factors of the rectangle are
 unchanged.
 
-Coverage: from F_e K_e F_e = F_e we get F_e P_e^k F_e = F_e for every k >= 1.
-Given a pair (u,v) in F_e, choose a witness of this for a power k with k > m.
-Along the P_e part, some of the m+1-or-more labels repeats; call the repeated
-label p.  The portion of the P_e-path between two occurrences of p is a loop
-p P_e p, so p is recurrent.  The part before p lies in F_e P_e^j <= F_e K_e
-and the part after p in P_e^j F_e <= K_e F_e (for j >= 0, using reflexivity of
-K_e when j = 0).  So (u,v) lies in the rectangle of the recurrent class of p.
+Coverage: we factor an arbitrary pair (u,v) in F_e through a recurrent point.
+Because P_e = K_e F_e K_e and F_e K_e F_e = F_e,
+
+    F_e P_e  =  F_e K_e F_e K_e  =  F_e K_e ,
+    P_e F_e  =  K_e F_e K_e F_e  =  K_e F_e ,
+
+so, since K_e is reflexive, induction on j >= 0 gives
+
+    F_e P_e^j  <=  F_e K_e           and           P_e^j F_e  <=  K_e F_e .
+
+Also P_e is idempotent, so F_e P_e^k F_e = F_e P_e F_e = F_e K_e F_e = F_e
+for every k >= 1.  Fix k > m and expand (u,v) in F_e = F_e P_e^k F_e as
+
+    u  F_e  c_1  P_e  c_2  P_e  ...  P_e  c_k  P_e  c_{k+1}  F_e  v .
+
+The k+1 labels c_1, ..., c_{k+1} all lie in the m-element set D+, so two of
+them coincide: c_i = c_j with i < j.  Idempotence of P_e then gives
+c_i P_e^{j-i} c_j = c_i P_e c_i, so p = c_i is recurrent.  The prefix ending
+at p lies in F_e P_e^{i-1} <= F_e K_e, giving u F_e K_e p; the suffix starting
+at p lies in P_e^{k+1-i} F_e <= K_e F_e, giving p K_e F_e v.  Thus (u,v) lies
+in the rectangle of the recurrent class of p, so the rectangles cover F_e.
 
 Now suppose C is not missing from z.  Then for p in C the loop
 p K_e F_z K_e p holds.  Inserting it between the two halves of the rectangle,
@@ -599,13 +614,14 @@ that, for every z in the corner e T_m e with  M_e(z) <= J  and  u z v in d T_m d
 PROOF.  We fix witnesses once and for all, independent of z.
 
 Fix a positive class C of C_d with representative x.  Its recurrence reads
-x K_d^+ F_d K_d^+ x, and after substituting d = u e v the middle F_d = F_{uev}
-is a concrete finite path through the three diagrams u, e, v.  That path uses
-finishing moves out of cells; whenever it crosses the MIDDLE diagram e it uses
-a through edge of e (a pair of F_e, or of B_e, according to sign).  For each
-such middle through edge pick, using Lemma 7.2, an e-recurrent class whose
-rectangle covers it.  Do the same for every negative class, using
-x K_d^- B_d K_d^- x.  These choices depend only on u, e, v, d, not on z.
+x K_d^+ F_d K_d^+ x.  Substituting d = u e v, the edge F_d = F_{uev} expands
+into a finite path that enters u, crosses e, and exits through v (with
+possible return loops at each boundary).  Every time this path crosses the
+middle factor e it uses a through edge of e (a pair of F_e, or of B_e for
+the negative sign).  For each such middle edge pick, using Lemma 7.2, an
+e-recurrent class whose rectangle covers it.  Do the same for every negative
+class, using x K_d^- B_d K_d^- x.  These choices depend only on u, e, v, d,
+not on z.
 
 Now define J'.  A class C of C_d is MARKED when any e-class chosen along its
 fixed witness lies in J.  Let J' be the set of marked classes.
@@ -1113,9 +1129,10 @@ which rearranges to
 
     s  >=  (1/2) * 2^floor((n-4)/127)  -  1 .
 
-The right-hand side grows exponentially with n and is bounded by no polynomial.
-Hence no single polynomial, independent of the alphabet, bounds the number of
-states needed to complement an n-state 2NFA.  QED
+The right-hand side grows exponentially with n and is bounded by no polynomial
+(for any fixed degree d, the ratio 2^floor((n-4)/127) / n^d tends to infinity
+as n grows).  Hence no single polynomial, independent of the alphabet, bounds
+the number of states needed to complement an n-state 2NFA.  QED
 
 A word of honesty about the alphabet.  The alphabet Sigma_n = R_H has
 |Sigma_n| = 2^{(n-2)^2} letters and grows with n.  The theorem is about bounds