diff eab029b..991b4a6 generalized_star_height_four_v2.txt
diff --git a/generalized_star_height_four_v2.txt b/generalized_star_height_four_v2.txt
index 920e421..1698e89 100644
--- a/generalized_star_height_four_v2.txt
+++ b/generalized_star_height_four_v2.txt
@@ -1,691 +1,544 @@
-A finite alphabet Sigma is fixed. Words are finite sequences of letters;
-the empty word is eps. Sigma* is the set of all words. A language is any
-subset of Sigma*. A regular expression is built from the constants 0 and
-1, from letters of Sigma, and from the operations of union,
-concatenation, complement in Sigma*, and Kleene star. The star height
-ht(E) of an expression is the deepest nesting of stars:
-
- ht(0) = ht(1) = ht(a) = 0 for a letter a,
- ht(P + Q) = ht(P Q) = max(ht(P), ht(Q)),
- ht(~P) = ht(P),
- ht(P*) = 1 + ht(P).
+
+DEDICATION
+
+To generalized star height, and to the exploration of the exact
+threshold between bounded and unbounded generalized star height.
+
+A finite alphabet Sigma is fixed. Words are finite sequences of
+letters; the empty word is eps. Sigma* denotes the set of all words.
+A language is any subset of Sigma*. A regular expression is built
+from the empty language, the language {eps}, and single letters, by
+union, concatenation, complement in Sigma*, and Kleene star. The
+star height ht(E) of an expression is the deepest nesting of stars:
+
+ ht(empty) = 0
+ ht({eps}) = 0
+ ht({a}) = 0 for each letter a
+ ht(P union Q) = max(ht(P), ht(Q))
+ ht(P Q) = max(ht(P), ht(Q))
+ ht(complement P) = ht(P)
+ ht(P*) = 1 + ht(P).
The star height of a regular language L is the least ht(E) over all
-expressions E with L(E) = L. An absolute bound for this quantity, one
-that is uniform in Sigma and in L, is the subject of the development.
+expressions E with L(E) = L. An absolute bound for this quantity,
+uniform in Sigma and in L, is the subject.
The theorem proved is the following.
- Every regular language over a finite alphabet has star height at most
- 4.
+ Every regular language over a finite alphabet has star height at
+ most 4.
The bound depends on neither Sigma, L, nor the size of a recognizing
automaton. Whether the sharper bound 1 always suffices is open.
-The non-complemented version of the same question has been settled for
-more than half a century. Eggan introduced ordinary star height and
-separated the first few levels using transition graphs of deterministic
-automata. Dejean and Schutzenberger proved unbounded ordinary star
-height over a binary alphabet.
+Background. Eggan introduced ordinary star height and separated the
+first few levels using transition graphs of deterministic automata.
+Dejean and Schutzenberger proved unbounded ordinary star height over
+a binary alphabet.
./eggan-1963.pdf
./dejean-schutzenberger-1966.pdf
-Complement changes the situation. Schutzenberger characterized the
-languages of ordinary star height zero, equivalently the languages of
-generalized star height zero, as those recognized by finite aperiodic
-monoids.
+Schutzenberger characterized the languages of ordinary star height
+zero, equivalently the languages of generalized star height zero, as
+those recognized by finite aperiodic monoids.
./schutzenberger-1965.pdf
-At height one several results are available. Henneman proved that
-every language recognized by a finite commutative group has generalized
-star height at most one. Pin, Straubing, and Therien extended the
-conclusion to finite nilpotent groups of class two and established
-closure properties for the star-height strata. Straubing formulated the
-absolute boundedness question and the sharper question whether height
-one always suffices.
+Henneman proved that every language recognized by a finite
+commutative group has generalized star height at most one. Pin,
+Straubing, and Therien extended the conclusion to finite nilpotent
+groups of class two and established closure properties for the
+star-height strata. Straubing formulated the absolute boundedness
+question and the sharper question whether height one always suffices.
+Earlier reports include studies of the height-three case and of
+uniform computations for finite monoids.
./pst-1992.pdf
./straubing2002.pdf
+./height3.pdf
+./uniform13.pdf
+
+Reduction. A regular language L is recognized by a finite monoid M
+through a morphism T: Sigma* -> M. The syntactic monoid of L is
+finite, so M can always be chosen finite. Letter a of Sigma maps to
+T(a) in M, and a concatenation w = a_1 a_2 ... a_k maps to the
+product T(a_1) T(a_2) ... T(a_k) in reading order. Because M is
+finite, no complexity claim is made; only the depth of stars is
+bounded.
+
+For integers A < B in the indexing of a word w let T_w[A, B] be the
+product of the letters between positions A and B in reading order.
+When the word is fixed, T[A, B] is used.
+
+Linearizing. Set V = F2^M, the F2-vector space with basis indexed by
+M. For m, c in M define e_m rho_0(c) = e_{m c}. This is a linear
+right action rho_0: V x M -> V. A word w acts on V by
+v -> v rho_0(T(w)), the linear map associated to T(w). The graph
+languages below construct this map on nice subclasses of words.
+
+Episodes and prefix codes. A prefix code over Sigma is a set E of
+nonempty words such that no member of E is a proper prefix of
+another. Every word in E* has a unique factorization into episodes:
+two factorizations w = e_1 e_2 ... = f_1 f_2 ... of the same word
+first differ at some length L; the prefixes e_1 and f_1 of the
+prefix of w of length L are comparable as prefixes, and the
+prefix-code property forces e_1 = f_1. Cancel and iterate.
+
+Graph languages. Let D be a subset of E, and (G_e) for e in D a
+family of deterministic updates of a finite set S. For x, y in S
+write W[x, y](D) for the set of w in D* whose factorization
+e_1 ... e_k satisfies G_{e_k}(... G_{e_1}(x) ...) = y. The empty
+word of D* corresponds to the identity update.
+
+The graph languages have the form
+
+ W[x, y] = union over e in D with G_e(x) = y of {e}
+ union over z in S of W[x, z](D) W[z, y](D).
+
+When x = y, the empty word eps belongs to W[x, y].
+
+The split principle. At each stage graph languages on a larger
+episode class D are built from graph languages on a smaller skipped
+class D'. The inductive step is the following lemma.
+
+Lemma (split). Let D' subset D, and let (G_e) for e in D be
+deterministic updates of a finite set S. Choose languages P_x, Q_y
+for x, y in S. Assume:
+
+ (i) If a word in D* has a prefix uv with u in P_x and v in Q_y,
+ then the first episode e of that word exists, uv = e, and
+ G_e(x) = y.
+
+ (ii) For every e in D - D' and every x in S, the episode e lies
+ in P_x Q_{G_e(x)}.
+
+Let W[x, y] denote the graph languages on D', and W'[x, y] the graph
+languages on D. Then for every x, y in S,
+
+ W'[x, y] = D* cap [ W[x, y]
+ union ( union_a W[x, a] P_a )
+ ( union_{b,c} Q_b W[b, c] P_c )*
+ ( union_f Q_f W[f, y] ) ].
+
+If D, every P_x, and every Q_y have height at most one, and every
+W[x, y] has height at most b >= 0, then W'[x, y] has height at most
+max(2, b+1).
+
+Proof. Soundness. A word accepted by the right side lies in D*, so
+it has a unique factorization into episodes. A W-factor lies in
+W[x, y](D'), hence consumes a sequence of D'-episodes, and the
+prefix-code property forces this sequence to align with the
+factorization. A P Q-pair, by (i), consumes exactly one further
+episode and updates the state from a to b as announced. Alternating
+the W-factors and the P Q pairs and finishing with the trailing
+Q W, induction on the number of alternations gives the required
+composite update from x to y. The initial alternative W[x, y]
+already produces the required update when no gap episode occurs.
+
+Completeness. Take a word in D* whose composite update sends x to
+y. Every episode e outside D' is split using (ii) into a word of
+P_a Q_b with b = G_e(a). The surrounding D'-episodes absorb into
+W-factors. Interleaving these splits into the alternation gives
+acceptance by the right side. If no gap episode occurs, the word
+lies in W[x, y].
+
+Height. The domain D* has height at most 2, since a single outer
+star over the alternating language E covers any length of
+concatenation of episodes. The union ( union_a W[x, a] P_a ) has
+height at most max(1, b). The starred union over the middle has
+height max(1, b) + 1. Intersecting with D* gives height at most
+max(2, b+1). QED
+
+Affine updates. A map G: U -> U on an F2-vector space U is affine
+if G(u) = u L + c for a linear map L and a fixed c in U. The
+composition of affine maps G_i(u) = u L_i + c_i satisfies
+G_2(G_1(u)) = u L_1 L_2 + (c_1 L_2 + c_2), an affine update with
+linear part L_1 L_2 and constant c_1 L_2 + c_2.
+
+Lemma (affine recovery). Let U be a finite-dimensional F2-vector
+space, D a subset of a prefix code E, and each G_e for e in D an
+affine update of U. Suppose (R_{v, y}) for v, y in U are graph
+languages for the affine composite w -> u L(w) + c(w) computed on
+the word w in D*. Then the graph language of the linear part,
+{v -> v L(w) = y}, equals
+
+ union over f in U of ( R_{v, y + f} intersect R_{0, f} ).
+
+Proof. For any w in D*, the affine composite sends v to
+v L(w) + c(w) and 0 to c(w). The value v L(w) equals y exactly when
+v L(w) + c(w) equals y + c(w) and 0 L(w) + c(w) equals c(w).
+Choosing f = c(w) matches the displayed intersection. Conversely, a
+pair (v, y + f) and (0, f) in the two graph languages with common w
+forces v L(w) = y. QED
+
+The recovery step uses only finite Boolean operations and therefore
+does not increase height. The same observation applies to any finite
+Boolean combination of graph languages on the same episode sequence.
+
+Affine-line lemma. Let M be a finite monoid acting on a
+finite-dimensional F2-vector space U by a right linear action rho.
+There exist l >= 1 and a function beta: M^l -> U with the following
+property. For every v in U and every tuple d = (d_1, ..., d_l) in
+M^l, at least one index j in {1, ..., l} makes the map
+
+ a |-> v rho(d_1 ... d_{j-1} a d_{j+1} ... d_l)
+ + beta(d_1, ..., d_{j-1}, a, d_{j+1}, ..., d_l)
+
+constant on M.
+
+Proof. Put qU = |U|. If m = |M| = 1 or qU = 1, take l = 1 and
+beta = 0. Assume m, qU > 1 from here. Choose l later. Choose the
+values of beta independently and uniformly in U.
+
+For a state v and tuple d in M^l, let B[v, d] be the event that no
+coordinate line through d has the stated constancy. Condition on the
+value beta(d). Constancy along one coordinate line prescribes beta
+at the other m - 1 points of that line, an event of probability
+qU^{1-m}. Different coordinate lines through d have disjoint sets of
+noncentral points, so those constancy events are conditionally
+independent, and the conditional failure probability given beta(d)
+does not depend on the value beta(d). Therefore
+
+ Pr(B[v, d]) = p[l] := (1 - qU^{1-m})^l.
+
+Each B[v, d] depends only on the random values at points of Hamming
+distance at most one from d, so it is independent of the joint
+family of events whose centers lie at distance greater than two from
+d. The number of potentially dependent events, including one factor
+of qU for every possible state at every neighboring center, is at
+most
+
+ D[l] := qU (1 + l m + l^2 m^2) - 1.
+
+The symmetric Lovasz local lemma (Erdos and Lovasz, 1975) is
+applied next.
+
+./erdos-lovasz-1975.pdf
+
+Suppose a finite
+family of events has a dependency graph of maximum degree D and each
+event has probability at most u (1 - u)^D for some 0 < u < 1. Then
+the simultaneous non-occurrence of every event has positive
+probability. The bound is proved by induction on the size of a
+conditioning set. For a set S of k events the induction claims:
+(a) every member of S fails simultaneously with positive
+probability, and (b) the conditional probability of any event A
+outside S, given the failure of every member of S, is at most u.
+Partition S into the neighbors S_1 and the non-neighbors S_0 of A.
+If S_1 is empty, joint independence from S_0 gives (b) without
+correction. Otherwise
+
+ Pr(A | every member of S fails)
+ <= Pr(A | every member of S_0 fails) /
+ Pr(every member of S_1 fails | every member of S_0 fails)
+ <= Pr(A) / (1 - u)^{|S_1|}
+ <= u.
+
+The denominator is bounded below by revealing the members of S_1
+one at a time and applying (b) at a set whose size is at most k - 1.
+The numerator uses joint independence from S_0. Statement (a) for S
+at size k follows by dropping one member of S and applying (b) at
+size k - 1. This closes the induction.
+
+Apply the lemma with D = D[l] and u = 1 / (2 D[l]). Bernoulli's
+inequality gives
+
+ u (1 - u)^{D[l]}
+ = 1/(2 D[l]) (1 - 1/(2 D[l]))^{D[l]}
+ >= 1/(4 D[l]).
+
+The failure probability p[l] decays exponentially in l while D[l]
+grows only like l^2 m^2 qU. Choose l large enough that
+p[l] <= 1/(4 D[l]). The local-lemma hypothesis holds, so some beta
+satisfies the conclusion of the lemma at every state and tuple. QED
+
+To apply the lemma to a word segment, choose ordered checkpoints
+B_0 < B_1 < ... < B_l and set d_j = T[B_{j-1}, B_j]. Process the
+segment by rho, then add beta(d) at B_l. If a cut lies in interval j
+the prefix transmits the vector v at B_0 and the preceding products
+d_1, ..., d_{j-1}; the suffix supplies d_{j+1}, ..., d_l and checks
+constancy on the missing-coordinate line. The corrected segment
+function is thereby computable at B_l for at least one interval.
-The development that follows combines two reductions. A regular
-language is first written as a finite union of fibers of a morphism
-into a finite monoid. Each fiber is next captured by a graph language
-on a prefix code of episodes, and the graph languages are built in
-four nested layers of stars. Nearly all of the difficulty lies in
-producing, for every cut between layers, enough finite information
-that the two halves can exchange.
-
-Every regular language over Sigma is recognized by some deterministic
-finite automaton. Assign to each word w the induced transformation of
-the state set. These transformations form a finite monoid M, written
-with composition order reversed so that T(uv) = T(u) T(v) for the
-word-to-transformation morphism T. Fix T: Sigma* -> M, with m = |M|
-and N = m!. The language L is a finite union of fibers T^-1(m) over the
-accepting m of the automaton. A bounded-height expression for every
-fiber, closed under finite union, gives a bounded-height expression
-for L. Only the fiber case is treated.
-
-If Sigma is empty, the only languages are the empty set and {eps},
-both of height zero. Assume Sigma is nonempty henceforth.
-
-The vector space V = F2^M has a canonical basis (e_c) indexed by M.
-Extended bilinearly, right multiplication by letters makes V a right
-M-module: e_c d = e_{cd} for c, d in M. The map w |-> e_1 T(w) sends a
-word to the basis vector that names T(w), so identifying the monoid
-value of a word is the same as identifying a basis vector in V.
-
-Two refinements of the same space are used later. Put U_0 = V and
-U_{i+1} = F2^(U_i x M) for i = 0, 1. Basis elements of U_{i+1} are
-written [v, c] with v in U_i and c in M; the second copy of M
-accumulates a prefix product while the first copy carries a vector.
-
-A set E of episodes is fixed, together with subsets D_0 and D_1 with
-D_1 contained in D_0 and D_0 contained in E. All three are prefix
-codes in Sigma+: no member is a proper prefix of another. Every word
-in E* therefore has a unique factorization into episodes, since the
-first factors in any two factorizations both begin at position zero
-and one must be a prefix of the other; equality of the first factors
-then permits induction on the length of the word.
-
-The graph language W[x,y](D) on a set D contained in E consists of the
-words in D* whose composite update sends x to y, where the update is
-specified by a family (G_e) for e in D. The domain condition is part of
-the language. The empty word belongs to W[x,x](D) because the empty
-composite is the identity.
-
-The mechanism that converts graph languages on D' to graph languages
-on D is the split principle.
-
- Lemma. Let D' be contained in D, with D a set of episodes. Let
- (G_e) for e in D be deterministic updates of a finite set S. Choose
- languages P_x and Q_y for x, y in S. Assume:
-
- (i) If a word in D* has a prefix uv with u in P_x and v in Q_y,
- then the first episode e of that word exists, uv = e, and
- G_e(x) = y.
-
- (ii) For every e in D - D' and every x in S, the episode e lies
- in P_x Q_{G_e(x)}.
-
- Let W[x,y] denote the graph languages on D', and W'[x,y] the graph
- languages on D. Then for every x, y in S,
-
- W'[x,y] = D* cap [ W[x,y]
- union ( union_a W[x,a] P_a )
- ( union_{b,c} Q_b W[b,c] P_c )*
- ( union_f Q_f W[f,y] ) ].
-
- If D, every P_x, and every Q_y have height at most one, and every
- W[x,y] has height at most b >= 0, then W'[x,y] has height at most
- max(2, b+1).
-
- Proof. Soundness. A word accepted by the right side lies in D*, so
- it admits a unique factorization into episodes. A W-factor lies in
- W[x,y](D'), hence consumes a sequence of D'-episodes; the
- prefix-code property forces the sequence to align with that
- factorization. A P Q-pair, by (i), consumes exactly one further
- episode and updates the current state from a to b as announced.
- Alternating the W-factors and the P Q pairs and finishing with the
- final Q W, induction on the number of alternations gives the
- required composite update from x to y. The initial alternative
- W[x,y] already gives the required update when no gap episode
- occurs.
-
- Completeness. Take a word in D* whose composite update sends x to
- y. Every episode e outside D' is split using (ii) into a word of
- P_a Q_b with b = G_e(a). The surrounding D'-episodes are absorbed
- into W-factors. Interleaving these splits into the alternation
- gives acceptance by the right side. If no gap episode occurs, the
- word lies in W[x,y].
-
- Height. The domain D* has height at most 2, since a single outer
- star over the alternating language E covers any length of
- concatenation of episodes. The union ( union_a W[x,a] P_a ) has
- height at most max(1, b). The starred union over the middle has
- height max(1, b) + 1. Intersecting with D* gives height at most
- max(2, b+1). QED
-
-The next lemma removes an affine shift before a linear part is tested.
-Affine updates compose to affine updates: a map v |-> v L + sigma with
-L linear and sigma fixed up to the map. The lemma recovers the product
-of linear parts of a sequence of affine updates from graph languages of
-the affine composite.
-
- Lemma (affine recovery). Let U be a finite-dimensional vector space
- over F2 and D a set of episodes. Suppose the update for e in D is
- G_e(v) = v L_e + sigma_e with L_e linear and sigma_e in U. Let
- R[v,y] be graph languages for the affine composite on D*. Then the
- graph language of the product of the linear parts, from v to y, is
-
- union_{f in U} ( R[v, y+f] cap R[0, f] ).
-
- Proof. On any word w in D*, the affine composite sends v to
- v L(w) + sigma(w) and 0 to sigma(w), where L(w) is the product of
- the L_e in reading order. The value v L(w) equals y exactly when
- v L(w) + sigma(w) equals y + sigma(w) and 0 L(w) + sigma(w) equals
- sigma(w). Choosing f = sigma(w) matches the displayed intersection.
- Conversely, a pair (v, y+f) and (0, f) in the two graph languages
- with common w forces v L(w) = y. QED
-
-The recovery step needs no star and so does not increase height. The
-same observation applies to any finite Boolean combination of graph
-languages on the same episode sequence.
-
-A separate lemma removes a single interval product from the data
-that crosses a cut. The affine-line lemma asserts the existence of a
-correction function beta that hides one coordinate of a tuple of
-monoid values, uniformly over the input state and the tuple.
-
- Lemma (affine line). Let M be a finite monoid acting on a
- finite-dimensional F2-vector space U by a right linear action
- rho. There exist l >= 1 and beta: M^l -> U with the following
- property. For every v in U and every tuple (d_1, ..., d_l) in M^l,
- at least one index j in {1, ..., l} satisfies: the map
-
- c |-> v rho(d_1 ... d_{j-1} c d_{j+1} ... d_l)
- + beta(d_1, ..., d_{j-1}, c, d_{j+1}, ..., d_l)
-
- is constant in c in M.
-
- Proof. Write qU = |U|. If m = 1 or qU = 1, take l = 1 and beta = 0.
- Assume m, qU > 1 from here. Choose l later. Choose the beta values
- independently and uniformly in U.
-
- For a state v and tuple d in M^l, let B[v, d] be the event that no
- coordinate line through d has the stated constancy. Condition on
- the value beta(d). Constancy along one coordinate line prescribes
- beta at the other m - 1 points of that line, an event of probability
- qU^(1-m). Different coordinate lines through d have disjoint sets of
- noncentral points, so those constancy events are conditionally
- independent, and the conditional failure probability given beta(d)
- does not depend on the value beta(d). Therefore
-
- Pr(B[v, d]) = p[l] := (1 - qU^(1-m))^l.
-
- Each B[v, d] depends only on the random values at points of Hamming
- distance at most one from d, so it is independent of the joint
- family of events whose centers lie at distance greater than two from
- d. The number of potentially dependent events, including one factor
- of qU for every possible state at every neighboring center, is at
- most
-
- D[l] := qU (1 + l m + l^2 m^2) - 1.
-
- The symmetric Lovasz local lemma is applied next. Recall the form:
- if a finite family of events has a dependency graph of maximum
- degree D and each event has probability at most u (1 - u)^D for
- some 0 < u < 1, then the simultaneous non-occurrence of every event
- has positive probability. The bound is proved by induction on the
- size of a conditioning set. For a set S of k events, the induction
- asserts that (a) every member of S fails simultaneously with
- positive probability and (b) the conditional probability of any
- event A outside S, given that every member of S fails, is at most
- u. Partition S into the neighbors S_1 and the non-neighbors S_0 of
- A. If S_1 is empty, joint independence from S_0 gives (b) with no
- correction. Otherwise
-
- Pr(A | every member of S fails)
- <= Pr(A | every member of S_0 fails) /
- Pr(every member of S_1 fails | every member of S_0 fails)
- <= Pr(A) / (1 - u)^{|S_1|}
- <= u.
-
- The denominator is bounded below by revealing the members of S_1
- one at a time and applying (b) at a set whose size is at most
- k - 1. The numerator uses joint independence from S_0. Statement
- (a) for S at size k follows by dropping one member of S and applying
- (b) at size k - 1. This closes the induction.
-
- Apply the lemma with D = D[l] and u = 1 / (2 D[l]). Bernoulli's
- inequality gives
-
- u (1 - u)^{D[l]}
- = 1/(2 D[l]) (1 - 1/(2 D[l]))^{D[l]}
- >= 1/(4 D[l]).
-
- The failure probability p[l] decays exponentially in l, while D[l]
- grows only like l^2 m^2 qU. Choose l large enough that
- p[l] <= 1/(4 D[l]). The local-lemma hypothesis holds, so some beta
- satisfies the conclusion of the lemma at every state and tuple.
- QED
-
-./sources/erdos-lovasz-1975.pdf
-
-Two remarks on the preceding lemma. The choices of l and beta do not
-depend on the state v or the tuple of d's; only the successful
-coordinate j may depend on them. The proof is effective: enumerate
-the finitely many functions M^l -> U for increasing l and test the
-stated property on every pair (v, tuple); the smallest l with a
-passing beta gives the required object. No useful bound on running
-time is asserted.
-
-The Erdos-Lovasz dependency-graph argument is a special case of the
-local lemma. A dependency graph is drawn on coordinates sharing a
-collision in the corrected map, and the uniform bound on total
-dependence in that graph gives a symmetric sufficient condition on
-p_l and on each row of the dependency matrix.
-
-The finite clock converts unbounded tag ambiguity into bounded tag
-uncertainty. It is a two-tag system: each tag has a left residue set I
-and a right residue set J in Z/n, and each pair (alpha, lambda) of
-tags is either consistent with the observed residue s or not. The
-next lemma exhibits a small finite system whose consistency relation
-is uncomplicated: only the diagonal or a single off-diagonal edge can
-appear.
-
- Lemma (finite clock). Let Lambda be a finite nonempty set, R a
- finite set, and Q >= 1 an integer. Set F = 400 and
- C = 2^{|Lambda|} (1 + 4 F^2). There exist a positive integer n,
- all of whose prime factors exceed Q, sets I_alpha and J_lambda
- in Z/n for alpha, lambda in Lambda, a set W in Z/n, and residues
- v_p in Z/n for p in R, satisfying:
-
- (i) For every s in Z/n, the relation E(s) of pairs
- (alpha, lambda) in Lambda x Lambda with s in I_alpha + J_lambda
+Finite clock. The affine-line lemma requires the prefix and suffix to
+share finite data. Such a collection is a tag. The next lemma builds
+a finite clock controlling independent tag choices through two
+length residues measured from scheduled reference positions. Its
+relation permits either matching tags or a single specified
+mismatch, which is later absorbed into an affine correction. A
+second property bounds ambiguous pairs of candidate origins uniformly
+in their common translation.
+
+Lemma (finite clock). Let Lambda be a finite nonempty set, R a finite
+set, and Q >= 1 an integer. Set F = 400 and C = 2^{|Lambda|}(1 + 4 F^2).
+There exist a positive integer n, all of whose prime factors exceed Q,
+sets I_alpha, J_alpha subset of Z/n for alpha in Lambda, a set
+W subset of Z/n, and residues v_p in Z/n for p in R, with:
+
+ (i) For every s in Z/n, the relation
+ E(s) = {(alpha, lambda) in Lambda x Lambda : s in I_alpha + J_lambda}
is either a subset of the diagonal or a singleton consisting of
one off-diagonal pair. If s is not in W, it is the full diagonal.
- (ii) For every u in Z/n,
- #{ (p, p') in R x R : p != p', u + v_{p'} - v_p in W }
- <= C.
-
- Proof. For each map chi: Lambda -> {L, R}, reserve one first
- coordinate and a batch of coordinates. Write r = |R|. Assign each
- coordinate a distinct prime order q satisfying
- q > max(Q, 400, 2^{r+1}).
- Sufficiently many primes exist because the preceding finite set is
- bounded above by max(Q, 400, 2^{r+1}), and Euclid's argument
- supplies a prime beyond any prescribed list. The batch contains a
- dedicated coordinate for every ordered list
- ((p_a, p'_a))_{a=0}^{F-1}
- of ordered pairs of distinct elements of R whose underlying
- unordered edges are distinct and form a forest. A spare coordinate
- is added if needed so that the batch has positive odd size. Write
- G for the product of the coordinate groups; G is finite.
-
- Identify a coordinate of prime order q with the subgroup q^-1 Z/Z
- of the circle T = R/Z. Let norm_T(x) denote circular distance from
- x to zero, and call a coordinate value small if norm_T(x) <= 1/100.
- Put C_I = {0, 1, 3}/6 and C_J = {2, 4, 5}/6 in T.
-
- For each tag alpha impose the following constraints in the chi
- block. If chi(alpha) = L, the first coordinate of I_alpha is zero
- and that of J_alpha is nonzero; in every batch coordinate, the
- I_alpha value sits within 1/16 of C_I and the J_alpha value sits
- within 1/16 of C_J. If chi(alpha) = R, the first coordinate of
- I_alpha is nonzero and that of J_alpha is zero; in a strict
- majority of batch coordinates, both I_alpha and J_alpha are small.
- The constraints over all blocks define I_alpha and J_alpha in G.
- Let W be the union over chi of two obstructions: the first
- coordinate is zero; or no batch coordinate is small.
-
- Sums and differences inside one batch. For a left tag and any
- target t in T, choose c_I in C_I, c_J in C_J, and a displacement
- delta with |delta| <= 1/12 so that t = c_I + c_J + delta in T.
- Round c_I + delta/2 to a nearest grid point i and set j = t - i.
- Both i and j are grid points, their distances from c_I and c_J
- are at most 1/24 + 1/(2q) < 1/16 since q > 400, and the sum
- c_I + c_J runs over all six multiples of 1/6 as c_I, c_J vary.
- Any target t therefore has a decomposition t = i + j with i in
- I_alpha and j in J_alpha at every batch coordinate. As a
- consequence, every allowed left-tag difference i - j obeys
- norm_T(i - j) >= 1/6 - 2/16 = 1/24 at every batch coordinate.
-
- For a right tag, write the batch size as 2k + 1 and choose a
- small target coordinate. At that coordinate, assign the target to
- the first summand and zero to the second. Partition the other 2k
- coordinates into two sets of size k. On the first set put zero in
- the first summand and the target in the second; on the second set,
- the reverse. Both summands have at least k + 1 small coordinates.
- Conversely, any two allowed right-tag values share a small
- coordinate, because their small-coordinate sets are strict
- majorities. Their difference therefore obeys norm_T(i - j)
- <= 2/100 < 1/24 in that coordinate. So the difference sets
- I_alpha - J_alpha and I_alpha' - J_alpha' are disjoint whenever
- a block places alpha on the left and alpha' on the right.
-
- Full relation. If s is not in W, every first coordinate of s is
- nonzero and every batch has at least one small coordinate. The
- decomposition t = 0 + t and t = t + 0 at the first coordinates,
- together with the batch decompositions above, gives s in
- I_alpha + J_alpha for every tag alpha. Choices in distinct blocks
- are independent and combine to give the required element of G.
-
- Suppose an off-diagonal pair (alpha, alpha') belongs to E(s). For
- a competing pair (lambda, mu) with {lambda, mu} different from
- {alpha, alpha'}, choose chi placing alpha on the left, alpha' on
- the right, and both lambda and mu on the same side; this is
- possible whenever the unordered pairs {alpha, alpha'} and
- {lambda, mu} are distinct, because identifying two distinct tags
- on the same side does not also identify the two on opposite
- sides. In that block, (alpha, alpha') forces the first coordinate
- of s to be zero, whereas (lambda, mu) requires it to be nonzero.
- So no such competitor can belong to E(s). The only remaining
- possible competitor is the reverse pair (alpha', alpha). If both
- pairs represented s there would be i_alpha + j_alpha' = i_alpha'
- + j_alpha with the indicated elements in the corresponding tag
- sets, hence i_alpha - j_alpha = i_alpha' - j_alpha'. A block that
- separates alpha from alpha' contradicts the disjointness of the
- difference sets. This proves (i).
-
- Roster. Index R as p_0, p_1, ..., p_{r-1}. In every first
- coordinate, set v_{p_j} = 2^j. For a < b,
- 2^b - 2^a = 2^a (2^{b-a} - 1).
- The exact power of two dividing the integer difference determines
- a, after which the odd factor determines b - a. Distinct ordered
- pairs give distinct nonzero integers bounded in magnitude by
- 2^r < q, so reduction modulo q is injective on ordered
- differences. For any translate u, at most one ordered pair (p, p')
- can have u + v_{p'} - v_p equal to zero in a fixed first coordinate.
-
- For a dedicated batch coordinate belonging to the list
- ((p_a, p'_a))_{a=0}^{F-1}, let z_a be a grid point at circular
- distance at most 1/(2q) from a/F. Prescribe
- (v_{p'_a} - v_{p_a}) at this coordinate = z_a
- for 0 <= a < F. A forest has no cycle, so these prescriptions are
- simultaneously satisfiable: choose a root value in each tree,
- propagate the prescribed differences along its edges, and assign
- arbitrary values to any remaining vertices and spare coordinates.
- Applying this independently at every batch coordinate yields
- elements v_p of G.
-
- For any translate t of the batch, one of the equally spaced
- points a/F lies within distance 1/(2F) of -t, and the
- corresponding prescribed difference satisfies
- norm_T(t + z_a) <= 1/(2F) + 1/(2q) < 1/400 < 1/100.
- Every dedicated list therefore provides a pair whose translated
- difference is small in its dedicated coordinate, uniformly in the
- translate.
-
- Whole-batch bound. Fix u in G and a batch. An ordered pair
- (p, p') with p != p' is bad for the batch if u + v_{p'} - v_p has
- no small coordinate in the batch. If more than 4 F^2 bad pairs
- existed, form the simple undirected graph whose edges are their
- underlying unordered pairs, discarding isolated vertices. If a
- spanning forest had at most F - 1 edges, its nontrivial
- components would span at most 2F - 2 vertices, since a component
- with h >= 2 vertices contributes h - 1 edges and h <= 2(h - 1),
- producing at most (2F - 2)(2F - 3) < 4 F^2 ordered pairs, a
- contradiction. Select F edges of the spanning forest and orient
- each as one of the bad pairs. The list of these F edges, taken in
- any order, is a dedicated list, and the covering estimate makes
- one of the pairs small in its dedicated coordinate, contradiction.
- Each batch therefore has at most 4 F^2 bad ordered pairs. The
- same counting applies when the roster is too small to admit a
- dedicated list.
-
- Counting. Every ordered pair (p, p') that survives in W for some
- translate u must have either its translated difference in a
- first-coordinate obstruction or its translated difference with no
- small coordinate in some batch. The first-coordinate construction
- contributes at most one ordered pair per chi block, and each of
- the 2^{|Lambda|} blocks contributes at most 1 + 4 F^2 ordered
- pairs. Combining,
- #{ (p, p') : p != p', u + v_{p'} - v_p in W }
- <= 2^{|Lambda|} (1 + 4 F^2)
- for every u in G. This gives (ii) after identifying the groups
- below.
-
- One cyclic clock. Let n be the product of all coordinate primes.
- The residue map from Z/n to G is injective since the coordinate
- primes are pairwise coprime, and both groups have n elements, so
- the map is an isomorphism. Transport all constructed sets through
- the inverse. Sums, differences, and both properties (i) and (ii)
- are preserved, and every prime factor of n exceeds Q by
- construction. QED
-
-A different roster construction, due to the polynomial-evaluation
-scheme underlying Reed-Solomon codes, uses polynomials of degree
-less than k_0 over a prime field F_P. Roster items are the
-polynomials themselves; the digits are their evaluations at distinct
-points xi_1, ..., xi_R of F_P. A nonzero polynomial of degree less
-than k_0 has at most k_0 - 1 roots, so any k_0 evaluations determine
-the polynomial, and the elementary root bound over the chosen prime
-field is all that is needed. The clock lemma accepts an abstract
-roster, so any finite R with the required count of digits will do.
-
-./reed-solomon-1960.pdf
+ (ii) For every u in Z/n,
+ #{ (p, p') in R x R : p != p', u + v_{p'} - v_p in W } <= C.
-In a region rich in markers a boundary is pinned to a marker. In a
-marker-free region the boundary follows a periodic extension of the
-local word. The marker-versus-periodicity principle originates with
-Krieger's marker lemma, with a finite clopen-merging formulation in
-Meyerovitch. Both uses below are elementary and self-contained.
+Proof. For each map chi: Lambda -> {L, R} reserve one first
+coordinate and a batch of coordinates. Write r = |R|. Assign each
+coordinate a distinct prime order q satisfying
+q > max(Q, 400, 2^{r+1}). Euclid's argument supplies a prime beyond
+any prescribed finite list. The batch contains a dedicated coordinate
+for every ordered list ((p_a, p'_a))_{a=0}^{F-1} of ordered pairs of
+distinct elements of R whose underlying unordered edges are distinct
+and form a forest. A spare coordinate is added if needed so the batch
+has positive odd size. Write G for the product of the coordinate
+groups; G is finite.
-./krieger1982.pdf
-./meyerovitch-2025.pdf
+Identify a coordinate of prime order q with the subgroup q^-1 Z/Z of
+the circle T = R/Z. Let norm_T(x) denote circular distance from x to
+zero; call a coordinate value small if norm_T(x) <= 1/100. Put
+C_I = {0, 1, 3}/6 and C_J = {2, 4, 5}/6 in T.
- Lemma (local markers). Let d >= 2 and K > 3 d^2 be integers. There
- is a translation-equivariant rule that marks integer positions of
- any two-sided word such that distinct markers are at distance at
- least d. The decision at z uses only [z - r, z + r) for a fixed
- finite integer r >= K. If there is no marker in the inclusive
- integer interval [z - d, z + d], the block [z, z + K) has a
- positive period less than d.
-
- Proof. List the finitely many length-K words having no positive
- period below d. Process these words in a fixed order, marking all
- starts not within distance less than d of an earlier marker. Two
- starts added at the same step cannot be at distance a < d, since
- their overlap would make a a period of the listed word. Induction
- gives separation.
-
- Each step decides from a length-K block and the decisions of
- earlier steps at offsets of magnitude less than d. Induction over
- the finite list gives a finite inspection radius, enlarged to at
- least K. The construction commutes with translations.
-
- A listed word at z was either marked, or prevented by a marker
- within distance less than d. Marker absence on [z - d, z + d]
- therefore excludes every listed word at z. QED
-
- Lemma (common periodic extensions). A block of length K > 3 d^2
- having a positive period below d has a unique two-sided periodic
- extension of period below d. Two such blocks whose starts differ
- by less than K - d^2 have the same extension. For the marking rule
- of the local-markers lemma, if there is no marker in [z - H, z + H]
- with H >= d, the actual letters on
-
- [z - H + d, z + H - d + K)
-
- agree with one such periodic extension.
-
- Proof. A block of period a extends by repeating its first a
- letters. Two two-sided words of respective periods a and b that
- agree on ab consecutive positions agree everywhere, because both
- then have period ab. Here a, b < d, so ab < d^2. Uniqueness and
- overlap follow. For the last assertion, every start in
- [z - H + d, z + H - d] has no marker within distance d, so its
- K-block has a period below d. Consecutive blocks overlap
- sufficiently that their extensions agree, and their union is the
- stated interval. On it the extension matches the actual letters.
- QED
-
-Apply these lemmas to finite words by extending arbitrarily in both
-directions. Provided all prescribed inspection windows are internal,
-the computed markers and periodic extensions do not depend on the
-extension.
-
-Two buffer layers precede the true origin t = s + L of an episode
-that begins at s. Buffer i has checkpoints
-
- B_{i,0} < B_{i,1} < ... < B_{i,l_i} < a_i,
-
-where a_i lies after all of its activity. Buffer 1, including a_1,
-precedes buffer 0. All checkpoints are translates of fixed offsets
-from s; the translations and L are fixed once and for all.
-
-The parameters of the affine-line lemma are chosen as follows.
-Choose l and beta for the action of M on V. For i = 0, 1, choose l_i
-and beta_i for the action rho_i on U_{i+1}. Thus beta: M^l -> V and
-beta_i: M^{l_i} -> U_{i+1}.
-
-The label [v, c] of a basis element of U_{i+1} retains the input
-state v while c accumulates a prefix product. Its work action is
-
- [v, c] rho_i(d) = [v, c d] (d in M).
-
-A terminal linear map sends each such label, once the later part of
-an episode is known, to a basis label that records the completed
-update indexed by c. The map is defined at every c in M, including
-values not realized by an actual prefix.
-
-The kind of a cut in buffer i is a tuple
-
- (j, v, d_1, ..., d_{j-1}),
- 1 <= j <= l_i, v in U_{i+1}, d_f in M.
-
-Let kappa_i be the number of kinds. A finite stencil P_i specifies
-cut offsets p from s, each offset assigned a kind; an offset of
-interval number j satisfies B_{i,j-1} < s + p < B_{i,j}. Write
-
- h_i = diam P_i,
- Delta_i = P_i - P_i.
-
-At an actual cut s + p, a suffix that considers an offset p' infers
-the origin t + p - p'. The stencil P_0 is built at this point; P_1
-is built later.
-
-Two steps convert separated numerical offsets into a stencil. Kinds
-are first assigned in increasing interval-number order, then the
-boundaries between successive interval numbers are placed in the
-gaps between offsets, and the extreme boundaries and a_i are added
-outside them. It therefore suffices to produce separated offsets
-with sufficiently many copies of every kind.
-
-The first stencil needs more copies of every kind than the number
-of wrong ordered origin pairs that can survive the tests. A
-polynomial roster gives the room. Set
-
- Z = l + 1,
- k_0 = 2 Z + 1,
- R_s = 2 k_0 - 1.
+For each tag alpha impose the following constraints in the chi block.
+If chi(alpha) = L, the first coordinate of I_alpha is zero, that of
+J_alpha is nonzero, and in every batch coordinate the I_alpha value
+sits within 1/16 of C_I and the J_alpha value within 1/16 of C_J. If
+chi(alpha) = R, the first coordinate of I_alpha is nonzero, that of
+J_alpha is zero, and in a strict majority of batch coordinates both
+I_alpha and J_alpha are small. The constraints over all blocks
+define I_alpha and J_alpha in G. Let W be the union over chi of two
+obstructions: the first coordinate is zero; or no batch coordinate
+is small.
-There are Z centers for the boundaries and R_s scales for each cut
-role. The clock-tag set is
+Sums and differences inside one batch. For a left tag and any target
+t in T, choose c_I in C_I, c_J in C_J, and a displacement delta with
+|delta| <= 1/12 so that t = c_I + c_J + delta in T. Round
+c_I + delta/2 to a nearest grid point i and set j = t - i. Both are
+grid points, their distances from c_I and c_J are at most
+1/24 + 1/(2q) < 1/16 since q > 400, and c_I + c_J runs over all six
+multiples of 1/6 as c_I, c_J vary. Any target t has a decomposition
+t = i + j with i in I_alpha and j in J_alpha at every batch
+coordinate. Consequently, every allowed left-tag difference i - j
+obeys norm_T(i - j) >= 1/6 - 2/16 = 1/24 at every batch coordinate.
- alpha = (j, r, v, d_1, ..., d_{j-1}, X, Y),
- 1 <= j <= l, 1 <= r <= R_s, v, X, Y in V, d_f in M.
+For a right tag, write the batch size as 2k + 1 and choose a small
+target coordinate. At that coordinate assign the target to the first
+summand and zero to the second. Partition the other 2k coordinates
+into two sets of size k. On the first set put zero in the first
+summand and the target in the second; on the second set the reverse.
+Both summands have at least k + 1 small coordinates. Any two allowed
+right-tag values therefore share a small coordinate, since their
+small-coordinate sets are strict majorities. Their difference obeys
+norm_T(i - j) <= 2/100 < 1/24 in that coordinate. So the difference
+sets I_alpha - J_alpha and I_alpha' - J_alpha' are disjoint whenever
+a block places alpha on the left and alpha' on the right.
-Its ambiguity constant C depends only on the tag set.
+Full relation. If s is not in W, every first coordinate of s is
+nonzero and every batch has a small coordinate. The decompositions
+t = 0 + t and t = t + 0 at the first coordinates, plus the batch
+decompositions, give s in I_alpha + J_alpha for every tag alpha.
+Choices in distinct blocks are independent and combine to give the
+required element of G.
-Let kappa_0 be the number of stage-0 buffer kinds. Choose a prime
-P > R_s large enough that
+Suppose an off-diagonal pair (alpha, alpha') belongs to E(s). For a
+competing pair (lambda, mu) with {lambda, mu} different from
+{alpha, alpha'}, choose chi placing alpha on the left, alpha' on the
+right, and both lambda and mu on the same side; this is possible
+since identifying two distinct tags on one side does not identify
+them on opposite sides. In that block, (alpha, alpha') forces the
+first coordinate of s to be zero, whereas (lambda, mu) requires
+nonzero. No such competitor belongs to E(s). The only remaining
+possible competitor is (alpha', alpha). If both pairs represented s
+there would be i_alpha + j_alpha' = i_alpha' + j_alpha, hence
+i_alpha - j_alpha = i_alpha' - j_alpha'. A block that separates alpha
+from alpha' contradicts the disjointness of the difference sets.
+This proves (i).
+
+Roster. Index R as p_0, ..., p_{r-1}. In every first coordinate set
+v_{p_j} = 2^j. For a < b,
+ 2^b - 2^a = 2^a (2^{b-a} - 1).
+The exact power of two dividing the integer difference determines a,
+after which the odd factor determines b - a. Distinct ordered pairs
+give distinct nonzero integers bounded in magnitude by 2^r < q, so
+reduction modulo q is injective on ordered differences. For any
+translate u at most one ordered pair (p, p') has
+u + v_{p'} - v_p equal to zero in a fixed first coordinate.
- floor(P^{k_0} / kappa_0) > C_0,
- C_0 = C + 2^{R_s} (3 Z + 1)^{R_s} P^{2 Z}.
+For a dedicated batch coordinate of a list ((p_a, p'_a)), let z_a be
+a grid point at circular distance at most 1/(2q) from a/F. Prescribe
+(v_{p'_a} - v_{p_a}) at that coordinate to equal z_a. These
+prescriptions are simultaneously satisfiable: choose a root value in
+each tree, propagate along its edges, and assign arbitrary values to
+remaining vertices and spare coordinates. Doing this in every
+coordinate produces the desired elements v_p in G.
-Such a prime exists because k_0 = 2 Z + 1 > 2 Z. The abstract roster
-consists of all polynomials of degree less than k_0 over F_P,
-including the zero polynomial. Choose distinct xi_1, ..., xi_{R_s} in
-F_P and give a roster slot p the digits
+For a fixed translate t of the batch, one of the equally spaced
+points a/F lies at distance at most 1/(2F) from -t, and the
+corresponding prescribed difference satisfies
+norm_T(t + z_a) <= 1/(2F) + 1/(2q) < 1/400 < 1/100. So each dedicated
+list has a pair whose translated difference is small in its dedicated
+coordinate, uniformly in the translate.
- x_r(p) = p(xi_r).
+Whole-batch bound. Fix u in G and a batch. An ordered pair (p, p')
+with p != p' is bad for the batch if u + v_{p'} - v_p has no small
+coordinate in the batch. If more than 4 F^2 bad pairs existed, form
+the simple undirected graph of their underlying unordered pairs,
+discarding isolated vertices. If a spanning forest had at most F - 1
+edges, its nontrivial components would span at most 2F - 2 vertices,
+since a component with h >= 2 vertices contributes h - 1 edges and
+h <= 2(h - 1), producing at most (2F - 2)(2F - 3) < 4 F^2 ordered
+pairs, contradiction. Select F edges of the spanning forest and
+orient each as one of the bad pairs. These F edges form a dedicated
+list, and the covering estimate makes one of the pairs small in its
+dedicated coordinate, contradiction. Each batch has at most 4 F^2
+bad ordered pairs, and the same counting applies when the roster is
+too small to admit a dedicated list.
+
+Counting. Every ordered pair (p, p') in W for some translate u has
+either its translated difference in a first-coordinate obstruction or
+its translated difference with no small coordinate in some batch. The
+first-coordinate construction contributes at most one ordered pair per
+chi block, and each of the 2^{|Lambda|} blocks contributes at most
+1 + 4 F^2. Combining,
+ #{ (p, p') : p != p', u + v_{p'} - v_p in W }
+ <= 2^{|Lambda|} (1 + 4 F^2)
+for every u in G. This gives (ii).
-Field elements are identified with {0, ..., P-1} when used as digit
-indices. A nonzero polynomial of degree less than k_0 has at most
-k_0 - 1 roots, by successive division by linear factors. Any k_0 of
-the evaluations determine a slot, and two distinct slots differ in
-at least R_s - k_0 + 1 = k_0 digits.
+One cyclic clock. Let n be the product of all coordinate primes. The
+residue map from Z/n to G is injective since the coordinate primes are
+pairwise coprime, and both groups have n elements, so the map is an
+isomorphism. Transport all constructed sets through the inverse. Sums,
+differences, and both properties (i) and (ii) are preserved, and every
+prime factor of n exceeds Q. QED
+
+Polynomial roster. A different roster uses the polynomial-evaluation
+scheme underlying Reed-Solomon codes. Fix a prime P, a positive
+integer k_0, and distinct points xi_1, ..., xi_R in F_P. A roster slot
+p is a polynomial over F_P of degree less than k_0, including the zero
+polynomial; its digit at scale r is p(xi_r). A nonzero polynomial of
+degree less than k_0 has at most k_0 - 1 roots, so any k_0 evaluations
+determine the slot and two distinct slots agree in at most k_0 - 1
+digits. The finite-clock lemma accepts any roster, so this polynomial
+roster serves whenever many residues are required. Only the
+elementary root bound over the prime field is used; the coding theory
+that follows from the Reed-Solomon construction plays no role.
./reed-solomon-1960.pdf
-Apply the clock lemma to this roster, avoiding all primes at most N.
-Fix the resulting modulus n, tag sets I_alpha and J_alpha, bad set
-W, and roster residues v_p in Z/n. Every prime divisor of n exceeds
-N. The modulus is chosen after the roster size, and enlarging it
-does not change C_0.
+Local markers. The marker-versus-local-periodicity principle appears
+in Krieger's analysis of subsystems of topological Markov chains,
+with a finite clopen merging formulation in Meyerovitch.
+
+./krieger1982.pdf
+./meyerovitch-2025.pdf
-Scale choices. Call a positive integer smooth if all of its prime
-divisors divide N. Choose thresholds S_r < S'_r, a positive step
-delta_r, a movement bound R_r = n delta_r, and digit positions
+Lemma (local markers). Let d >= 2 and K > 3 d^2 be integers. There is
+a translation-equivariant rule that marks integer positions of any
+two-sided word such that:
+
+ (i) distinct markers are at distance at least d;
+
+ (ii) the decision at z uses only [z - r, z + r) for a fixed finite
+ integer r >= K;
+
+ (iii) if there is no marker in [z - d, z + d], then the length-K
+ block starting at z has a positive period less than d.
+
+Proof. List the finitely many length-K words having no positive
+period below d. Process them in a fixed order. When processing one of
+these words, mark all of its starts not within distance < d of an
+earlier marker. Two starts added at the same step cannot be at
+distance a < d, since their overlap would make a a period of the
+listed word, a contradiction. This gives (i) by induction. Each step
+uses a length-K block and the decisions of earlier steps at offsets
+of magnitude < d; induction over the finite list integrates these
+into a finite inspection radius, enlarged to at least K. The
+construction commutes with translations, giving (ii). A listed word
+at z was either marked or was prevented from being marked by a
+marker at distance < d. Marker absence in [z - d, z + d] therefore
+excludes every listed word at z, giving (iii). QED
+
+Periodic extension. In marker-free regions the boundary rule preserves
+a congruence class modulo a full monoid period; preserving only a
+phase modulo the period is not enough.
+
+Lemma (periodic extension). A block of length K > 3 d^2 having a
+positive period below d determines a unique two-sided periodic
+extension of period below d. Two such blocks whose starts differ by
+less than K - d^2 determine the same extension. If there is no marker
+in [z - H, z + H] with H >= d, then the actual letters on
+[z - H + d, z + H - d + K) agree with that extension.
+
+Proof. A length-K block with a period p < d forces a unique letter at
+every integer congruent modulo p to a position inside the block, and
+the period hypothesis is preserved by translations. Two blocks with
+overlapping periodic runs that share at least K - d^2 letters must
+agree on their common overlap, because the offset between the two
+starts is itself a period of the overlap, forcing the least periods
+to coincide. QED
+
+Scale choices. Let N be a common multiple of |M| and of every
+eventual period of every element of M. Call a positive integer
+smooth if all of its prime divisors divide N. Choose thresholds
+S_r < S'_r, a positive
+step delta_r, a movement bound R_r = n delta_r, and digit positions
f_r(0) < f_r(1) < ... < f_r(P - 1) at each scale, in increasing order
of r. For each r:
- (i) Choose S_r >= 1, with S_r >= S'_{r-1} if r > 1. Choose delta_r
+ (i) choose S_r >= 1 with S_r >= S'_{r-1} if r > 1; choose delta_r
smooth and divisible by N sigma for every smooth positive integer
- sigma <= S_r. Then gcd(delta_r, n) = 1.
+ sigma <= S_r, so that gcd(delta_r, n) = 1;
- (ii) Put J_r = n + sum_{b<r} h'_b. Choose the digit positions so
- that all ordered differences of unequal digits are distinct and
+ (ii) put J_r = n + sum_{b < r} h'_b; choose the digit positions so
+ all ordered differences of unequal digits are distinct and
separated from one another and from zero by more than
- 10 (J_r + R_r + 1). Write h'_r for their diameter.
-
- (iii) Choose S'_r > max(S_r, 10 (h'_r + J_r + R_r + 1)).
+ 10 (J_r + R_r + 1); write h'_r for their diameter;
-The step in (i) may be the least common multiple of the finitely many
-required N sigma; it is smooth. When N = 1, the only smooth positive
-integer is 1, and delta_r = 1 is permissible. The digit positions in
-(ii) may be chosen as sufficiently scaled powers of two: a positive
-difference 2^a - 2^b with a > b determines b by its power-of-two
-valuation and then a, so all nonzero ordered differences are
-distinct, and a common scaling gives the required separation.
+ (iii) choose S'_r > max(S_r, 10 (h'_r + J_r + R_r + 1)).
Assign slot p the numerical offset
-
- sum_{r=1}^{R_s} f_r(x_r(p)) + eps_p, 0 <= eps_p < n.
-
-Choose eps_p so that the offset is congruent to v_p modulo n. For two
+ sum_{r=1}^{R_s} f_r(x_r(p)) + eps_p, 0 <= eps_p < n,
+with eps_p chosen so the offset is congruent to v_p modulo n. For two
slots whose highest differing digit is at scale r, the sum of all
smaller-coordinate differences plus the correction difference has
-absolute value less than J_r, while the difference at scale r has
-absolute value greater than 10 (J_r + R_r + 1). The resulting
-positions are distinct, and any two are separated by more than 2.
-
-These positions, up to a common translation, form the stencil P_0.
-Their difference residues are exactly the prescribed v_p - v_p',
-including after the common translation. By the inequality
-floor(P^{k_0} / kappa_0) > C_0, more than C_0 offsets can be assigned
-to each stage-0 kind. Assign them in increasing interval-number
-order and insert buffer boundaries in the intervening gaps.
-Translation of the whole configuration later does not affect any
-difference property. In particular,
-
- h_0 < n + sum_r h'_r.
+absolute value less than J_r, while the difference at scale r exceeds
+10 (J_r + R_r + 1). The positions are distinct and the offsets of the
+resulting stencil P_0 are separated by more than 2.
-Inner controls. The inner boundary rule needs marker parameters far
-exceeding every scale and every monoid period. Choose integers
+Inner controls. The inner boundary rule needs marker parameters
+dwarfing every scale and every monoid period. Choose integers
d_o > 10 (1 + n + sum_r h'_r + sum_r R_r),
K_o > 3 d_o^2,
-and fix the marking rule of the local-markers lemma with these
-parameters and radius r_o >= K_o. Choose an integer
+and fix the marking rule of the local-markers lemma with d = d_o,
+K = K_o, and radius r_o >= K_o. Choose an integer
H > 10 ((N + m + 1) d_o + (max_r R_r) + 1).
-For an inner center z, let u(z) be the first marker in [z - H, z + H],
+For an inner center z let u(z) be the first marker in [z - H, z + H],
or bottom when none exists. When u(z) is not bottom, put B(z) = u(z).
When u(z) is bottom, the periodic-extension lemma supplies a
periodic extension of the block starting at z. Let d < d_o be its
least period and sigma the largest smooth divisor of d. Among the
-length-d period words starting at the different phases of the
-extension, choose the lexicographically least, using a fixed order on
-Sigma. Their starts form a single class x modulo d, since equality of
-two rotations would contradict minimality of d. Let y(z) be the
-largest integer at most z in x + sigma Z, and let B(z) be the least
-integer at least z satisfying
-
- B(z) = x (mod d),
- B(z) = y(z) (mod sigma N).
-
-The definition does not depend on the representative of x. Moreover,
-
- gcd(d, sigma N) = sigma,
- lcm(d, sigma N) = d N,
-
-because d / sigma is coprime to N by choice of sigma. The two
-residues in the boundary rule agree modulo sigma, so together they
-define one class modulo d N. In particular,
-
- z <= B(z) < z + d N.
-
-All these choices commute with translations of the letters and do
-not use an external choice of position origin. In both the present
-and absent cases, B(z) lies in [z - H, z + H].
+length-d period words at the different phases choose the
+lexicographically least. Their starts form a single class x modulo d,
+since equality of two rotations contradicts minimality of d. Let y(z)
+be the largest integer at most z in x + sigma Z, and let B(z) be the
+least integer at least z satisfying
+
+ B(z) = x (mod d),
+ B(z) = y(z) (mod sigma N).
+
+The definition does not depend on the representative of x. Since
+gcd(d, sigma N) = sigma and d / sigma is coprime to N, the two
+residues agree modulo sigma and together define one class modulo
+d N. In particular z <= B(z) < z + d N. All the choices commute with
+translations of the letters and do not use an external choice of
+position origin. In both the present and absent cases, B(z) lies in
+[z - H, z + H].
Center spacing. Choose an even integer
@@ -704,20 +557,16 @@ the true origin t. The main cut offsets from t form the finite set
H_cut = { c_j + delta_r a :
1 <= j <= l, 1 <= r <= R_s, 0 <= a < n }.
-A cut of role (j, r) lies strictly between B_{j-1} and B_j. All
-inspection windows for boundaries through j-1 are before this cut.
+A cut of role (j, r) lies strictly between B_{j-1} and B_j, and every
+inspection window for boundaries through j-1 is before this cut.
Conversely, for a suffix beginning at k and any hypothesized role
(j, r), a candidate origin k - c_j - delta_r a has its first required
-center at
+center at k + G/2 - delta_r a. Since delta_r a < R_r, the center
+spacing puts the inspections for this center and all later centers
+after k.
- k + G/2 - delta_r a.
-
-Since delta_r a < R_r, the center spacing puts the inspections for
-this center and all later centers after k.
-
-Usability. The transport of boundary products needs a scale whose
-inner markers and periodic extensions are locally stable. Call scale
-r usable at origin t if, at each of its Z centers z_j,
+Usability. Call scale r usable at origin t if, at each of its Z
+centers z_j,
(i) u(z_j + h) = u(z_j) for every integer h with |h| <= R_r,
including agreement on absence;
@@ -725,22 +574,22 @@ r usable at origin t if, at each of its Z centers z_j,
(ii) if u(z_j) = bottom, then either sigma <= S_r, or the inclusive
interval [z_j - R_r, z_j + R_r] contains no point of x + sigma Z.
-Here d, sigma, and x refer to the periodic extension at the
-indicated center. All windows needed by these checks are mandatory.
+In this definition d, sigma, x refer to the periodic extension at the indicated
+center. All windows needed by these checks are mandatory.
Lemma (transport of boundary products). Suppose scale r is usable at
origin t and h is a multiple of delta_r with |h| <= R_r. Write
B_j^{(h)} = B(z_j + h). Then
- T[B_{j-1}, B_j] = T[B_{j-1}^{(h)}, B_j^{(h)}] (1 <= j <= l).
+ T[B_{j-1}, B_j] = T[B_{j-1}^{(h)}, B_j^{(h)}] (1 <= j <= l).
-For a fixed endpoint b >= z_l + H, the last transfer gives
+For a fixed endpoint b >= z_l + H, the trailing transfer also gives
T[B_l, b] = T[B_l^{(h)}, b].
-These statements apply to finite words whenever the prescribed
-windows and product intervals are available. They hold for arbitrary
-finite monoids, without a commutativity assumption.
+Both statements apply to finite words whenever the prescribed windows
+and product intervals are available. They hold for arbitrary finite
+monoids, without a commutativity assumption.
Proof. Three steps: the two boundaries at each center lie in one
class modulo d N; the periodic run around each boundary is long
@@ -748,16 +597,14 @@ enough; and monoid-power periodicity turns the shift into an identity
on the level of ordered products.
A common boundary class. Consider one center z. Usability (i) keeps
-the marker status unchanged: either both boundaries equal the same
-marker, or both are absent. In the absent case the old and new
-periodic blocks determine the same two-sided extension, since
+the marker status unchanged. If both boundaries are absent, the old
+and new periodic blocks determine the same two-sided extension, since
|h| <= R_r < d_o and the blocks have length K_o > 3 d_o^2. Thus the
least period d, the smooth divisor sigma, and the phase class x
-modulo d are common to both. Both boundaries satisfy the two
-congruences B = x mod d and B = y mod sigma N, with y the largest
-point at most the shifted center in x + sigma Z. The clause that
-depends on the shift is only the largest-at-most one, and it moves y
-by exactly h, which is a multiple of delta_r and hence of sigma.
+modulo d are common to both. Both boundaries satisfy
+B = x mod d and B = y mod sigma N, with y the largest point at most
+the shifted center in x + sigma Z. The largest-at-most clause changes
+y by exactly h, which is a multiple of delta_r and hence of sigma.
Since gcd(d, sigma N) = sigma and d / sigma is coprime to N, the two
congruences combine to B(z + h) = B(z) modulo d N. In the remaining
case of usability (ii), when sigma > S_r, the interval
@@ -769,21 +616,20 @@ the boundary does not move at all. In either case,
Long periodic runs. Fix a center z with u(z) = bottom. The
periodic-extension lemma and the marker-free window imply that the
actual word is d-periodic on the length (K_o - d_o) window beginning
-at z + H - d_o. Both boundaries B(z) and z lie in [z - H, z + H], so
-B(z) sits strictly inside this run. The same applies at the shifted
-center z + h. Together, the two runs cover the region of radius
-2 H + R_r used by the transport identity.
+at z + H - d_o. Because both B(z) and z lie in [z - H, z + H], the
+boundary B(z) sits strictly inside this run. The same applies at the
+shifted center z + h. Together, the two runs cover the region of
+radius 2 H + R_r used by the transport identity.
Monoid-power periodicity. Let m be the length-d period word treated
as an element of M. Its powers satisfy m^k = m^(k + N) once
-k >= N^2, by pigeonhole on the finitely many elements
-m^0, m^1, .... Enlarging N if necessary to a multiple of the
-eventual period of m, the element m^(q N) is independent of q >= 1.
-Because delta_r is a multiple of N sigma, the shift h is a multiple
-of N; by the common-class calculation the boundary difference is
-q d N, a multiple of d N. A segment of length q d N has the product
-m^(q N), so two such segments have equal ordered products. This
-gives
+k >= N^2, by pigeonhole on the finitely many values m^0, m^1, ....
+Since N is a multiple of the eventual period of m by construction,
+the element m^(q N) is independent of q >= 1. Because delta_r is a
+multiple of N sigma, the shift h is a multiple of N, and by the
+common-class calculation the boundary difference is q d N, a multiple
+of d N. A segment of length q d N has the product m^(q N), so two
+such segments have equal ordered products. This gives
T[B_{j-1}, B_j] = T[B_{j-1} + q_{j-1} d N, B_j + q_j d N]
= T[B_{j-1}^{(h)}, B_j^{(h)}].
@@ -791,90 +637,103 @@ gives
The left identity shifts both endpoints by the common amount
q_{j-1} d N. The right follows by moving the right endpoint from
B_j + q_{j-1} d N to B_j + q_j d N in steps of d N: each step
-contributes the element m^(q N), which is the same for every q >= 1
-and so telescopes out of the product. The trailing transfer uses
-the periodic extension at z_l on the right and the same argument,
-giving T[B_l, b] = T[B_l^{(h)}, b] for any fixed b >= z_l + H. None
-of the steps uses commutativity. QED
+contributes the monoid element m^(q N), the same for every q >= 1,
+so the contributions telescope out of the product. The trailing
+transfer uses the periodic extension at z_l on the right and the same
+argument, giving T[B_l, b] = T[B_l^{(h)}, b] for any fixed
+b >= z_l + H. No step uses commutativity. QED
Proposition (inner ambiguity). For every stage-0 tag alpha and every
u in Z/n,
- #{(p, p') in R_0^2 : p != p', u + v_{p'} - v_p in W and
- some gamma in Delta_0 has A_1(t + p - p' + gamma)} <= C_0,
+ #{(p, p') in R_0^2 : p != p', u + v_{p'} - v_p in W and some
+ gamma in Delta_0 has A_1(t + p - p' + gamma)} <= C_0,
-where Delta_0 = P_0 - P_0 and A_1 is the finite predicate on offsets
-whose checks lie before the main cut and involve the alignment
-between a hypothesized origin and the true episode.
+where Delta_0 = P_0 - P_0, A_1 is the finite predicate on offsets
+whose checks lie before the main cut, and
+C_0 = C + 2^{R_s} (3 Z + 1)^{R_s} P^{2 Z}.
Proof. Let D denote the displayed set, and fix a stage-0 tag alpha,
-its roster offset p_alpha, and a translate u. By the clock, the
-pairs in D lie in at most 2^{R_s} (1 + 4 F^2) W-classes. If for some
-W-class the number of pairs exceeds
-
- M_1 = P^{k_0} / (2^{R_s} (1 + 4 F^2)),
-
+its roster offset p_alpha, and a translate u. By the clock, the pairs
+in D lie in at most 2^{R_s} (1 + 4 F^2) W-classes. If for some class
+the number of pairs exceeds M_1 = P^{k_0} / (2^{R_s} (1 + 4 F^2)),
then two pairs in that class share all of their first k_0
-evaluations. The underlying polynomials then agree on k_0 distinct
-field elements. Because a nonzero polynomial of degree less than
-k_0 has at most k_0 - 1 roots, the two slots have the same
-polynomial, hence coincide, contradicting p != p'. Every W-class
-therefore contributes at most M_1 distinct pairs.
+evaluations. The underlying polynomials agree on k_0 distinct field
+elements; because a nonzero polynomial of degree less than k_0 has at
+most k_0 - 1 roots, the two slots have the same polynomial, hence
+coincide, contradicting p != p'. Every W-class therefore contributes
+at most M_1 pairs.
Fix one W-class. Its pairs are indexed by gamma offsets in Delta_0.
-For each gamma, the predicate A_1 makes at most 3 choices at each
-of the Z centers and at most P^(2 Z) distinct first-coordinate
+For each gamma, the predicate A_1 makes at most 3 choices at each of
+the Z centers and at most P^{2 Z} distinct first-coordinate
witnesses across the R_s scales. Summing the Z-center choices over
-the R_s scales gives the finite bound
+the R_s scales gives the finite bound (3 Z + 1)^{R_s} P^{2 Z} on the
+number of gamma surviving A_1 at one translate. Multiplying,
- (3 Z + 1)^{R_s} P^{2 Z}
+ |D| <= 2^{R_s} (1 + 4 F^2) (3 Z + 1)^{R_s} P^{2 Z} <= C_0.
-on the number of gamma offsets that survive A_1 at one translate.
-Multiplying,
+QED
- |D| <= 2^{R_s} (1 + 4 F^2) (3 Z + 1)^{R_s} P^{2 Z} <= C_0,
+The concrete roster. Set
-which proves the bound. QED
+ Z = l + 1, k_0 = 2 Z + 1, R_s = 2 k_0 - 1.
-End system. Episodes end at deterministic anchors. The end system
-consists of four pieces.
+There are Z centers for the boundaries and R_s scales for each cut
+role. The tag set is
- (i) A second instance of the local-markers lemma, called the end
- markers, with integer parameters d_e, K_e, and radius r_e.
+ alpha = (j, r, v, d_1, ..., d_{j-1}, X, Y),
+ 1 <= j <= l, 1 <= r <= R_s, v, X, Y in V, d_f in M.
- (ii) At each proposed origin, a seed block of length K_e placed at
- a fixed offset o_e.
+Its ambiguity constant C depends only on the tag set, before any
+roster or position is chosen.
- (iii) An anchor rule that maps an integer t to an integer q or to
- bottom.
+Let kappa_0 be the number of stage-0 buffer kinds. Choose a prime
+P > R_s large enough that
- (iv) A fixed positive integer b_tail, chosen large enough that the
- end windows sit strictly before q + b_tail.
+ floor(P^{k_0} / kappa_0) > C_0,
+ C_0 = C + 2^{R_s} (3 Z + 1)^{R_s} P^{2 Z}.
-Parameters. Choose integers
+Such a prime exists because k_0 = 2 Z + 1 > 2 Z. Roster slots are the
+polynomials of degree less than k_0 over F_P, including the zero
+polynomial. Choose distinct xi_1, ..., xi_{R_s} in F_P and give slot p
+the digits
- d_e > 2 (h_e + w) + 1,
- K_e > 3 d_e^2,
+ x_r(p) = p(xi_r).
+
+A nonzero polynomial of degree less than k_0 has at most k_0 - 1
+roots, so any k_0 of the evaluations determine the slot, and two
+distinct slots differ in at least R_s - k_0 + 1 = k_0 digits. Apply
+the finite-clock lemma to this roster, avoiding every prime at most
+N. Fix the resulting modulus n, tag sets I_alpha, J_alpha, bad set
+W, and roster residues v_p in Z/n. Every prime divisor of n exceeds N
+by construction, and enlarging the modulus does not change C_0.
-and fix a second marking rule with these values and radius r_e >=
-K_e. Choose H_e large enough to dwarf d_e and the endpoint ranges
-used below. Choose o_e so that the seed block sits after the inner
-envelope. Choose b_tail large enough that the fixed end tail sits
-after the seed block.
+End system. An episode ends at a deterministic anchor. The end
+system consists of four parts.
-End markers. For an integer t, let eta(t) be the first end marker in
-[t - H_e, t + H_e], or bottom when none exists. The definition is
-translation-equivariant.
+ (i) A second instance of the local-markers lemma, called the end
+ markers, with parameters d_e > 2 (h_e + w) + 1 and K_e > 3 d_e^2
+ and radius r_e >= K_e.
+
+ (ii) At each proposed origin, a seed block of length K_e placed at
+ a fixed offset o_e.
+
+ (iii) An anchor rule that maps an integer t to an integer q or to
+ bottom.
-Seed and anchor. Let z_e(t) = t + o_e. When eta(t) = bottom, the
-periodic-extension lemma applied to the block at z_e(t) of length
-K_e yields a two-sided periodic extension with least period d <
-d_e. Compare the extension with the actual letters to the right and
-let q be the first mismatch position, if any. Otherwise q is
-undefined and the episode is incomplete.
+ (iv) A fixed positive integer b_tail larger than the extent of the
+ end windows.
-Episode ends. When q is defined, the episode beginning at s with
-true origin t = s + L ends at q + b_tail.
+Define eta(t) as the first end marker in [t - H_e, t + H_e], or
+bottom when none exists. The definition is translation-equivariant.
+Let z_e(t) = t + o_e. When eta(t) = bottom, the periodic-extension
+lemma applied to the block at z_e(t) of length K_e yields a two-sided
+periodic extension with least period d < d_e. Compare the extension
+to the actual letters and let q be the first mismatch position, if
+any. Otherwise q is undefined and the episode is incomplete. When q
+is defined, the episode beginning at s with true origin t = s + L
+ends at q + b_tail.
Placement. The four envelopes are chosen in acyclic order.
@@ -888,23 +747,23 @@ Placement. The four envelopes are chosen in acyclic order.
end markers, the seed block, and the end windows, sits after the
inner envelope.
- (D) Choose b_tail large enough that the fixed tail sits after the
- end envelope.
+ (D) Choose b_tail large enough that the fixed tail follows the end
+ envelope.
-Each step only enlarges a translation. All the component data of
-the episode is determined by the local letters around the cut and
-end windows.
+Each step only enlarges a translation. All the data of the episode is
+therefore determined by the local letters around the cut and end
+windows.
Lemma (placement). The translations of the two buffers and the
integers L, o_e, b_tail can be chosen so that:
- (i) After s, the buffers occur in order 1, 0, then every relevant
+ (i) After s the buffers occur in order 1, 0, then every relevant
inner-system window and cut, then every relevant end-system window
and seed.
- (ii) Every bounded window required at main hypotheses or at
- aligned buffer hypotheses is internal to every complete episode
- at a true cut.
+ (ii) Every bounded window required at main hypotheses or at aligned
+ buffer hypotheses is internal to every complete episode at a true
+ cut.
(iii) A prefix or suffix computation has its required data on its
own side of a true cut.
@@ -912,320 +771,287 @@ integers L, o_e, b_tail can be chosen so that:
(iv) Every possible true first-episode end is after all cuts and
bounded control windows.
-Proof. The four envelopes are chosen in order (A)-(D). Each step
-only enlarges a translation by a finite amount, so the order is
-preserved. QED
+Proof. The four envelopes are chosen in order (A)-(D); each step
+enlarges a translation by a finite amount and preserves the previous
+order. QED
-End ambiguity. Let Delta_0 = P_0 - P_0 be the finite set of ordered
-origin differences allowed at stage 0. A pair (p, p') in P_1^2
-survives A_1 when the end marker eta agrees across every candidate
-window at the resulting true-origin shift.
-
-Lemma (end ambiguity). On any two-sided word, uniformly in t,
+Lemma (end ambiguity). Let Delta_0 = P_0 - P_0 be the set of ordered
+origin differences allowed at stage 0. Then, uniformly in t,
#{(p, p') in P_1^2 : p != p',
- some gamma in Delta_0 has A_1(t + p - p' + gamma)}
- <= C_1 := 2 |Delta_0|.
+ some gamma in Delta_0 has A_1(t + p - p' + gamma)} <= 2 |Delta_0|,
+
+where A_1 is the finite predicate that the end marker eta agrees
+across every candidate window at the resulting true-origin shift.
-Proof. Fix a gamma in Delta_0 and an endpoint of the search window
+Proof. Fix gamma in Delta_0 and one endpoint of the search window
[t - H_e, t + H_e]. As p - p' ranges over Delta_0 + Delta_1, the
candidate marker positions lie in a bounded interval of diameter at
-most 2 h_1 + 2 w < d_e, which contains at most one end marker by
+most 2 h_1 + 2 w < d_e, which contains at most one end marker by the
separation of markers at distance d_e. That marker pins p - p' to an
-interval of length 2 w <= d_e / 2 - 1, so at most one nonzero
-ordered pair survives at that endpoint. Two endpoints times
-|Delta_0| choices of gamma produce 2 |Delta_0| pairs in total. QED
+interval of length 2 w <= d_e/2 - 1, so at most one nonzero ordered
+pair survives at that endpoint. Two endpoints and |Delta_0| choices
+of gamma give 2 |Delta_0| pairs. QED
End guard. A suffix with candidate list {k - h : h in H} forms its
-end guard by:
-
- (i) requiring eta to agree across every candidate in the list;
-
- (ii) requiring the exact-end test (anchor rule plus endpoint
- q + b_tail) at one fixed reference candidate.
+end guard by requiring eta to agree across every candidate in the
+list and by applying the exact-end test (anchor rule plus endpoint
+q + b_tail) at one fixed reference candidate.
Lemma (end guard). Suppose a finite word begins with a complete
-episode e of true origin t and anchor q. A prefix cut k lies
-strictly inside e. Let a suffix argument at k use an end guard whose
-candidate list contains t and has diameter at most w. If the guard
-accepts, the suffix ends exactly at the end of e, and its reported
-anchor is q. The conclusion holds even if the proposed suffix
-initially ends before e or extends past e.
-
-Proof. On the true episode every candidate window is present, and
-the true anchor q is among the candidates. A premature suffix lacks
-at least one such window: the exact-end test at the reference
+episode e of true origin t and anchor q. A prefix cut k lies strictly
+inside e. Let a suffix argument at k use an end guard whose candidate
+list contains t and has diameter at most w. If the guard accepts, the
+suffix ends exactly at the end of e and its reported anchor is q. The
+conclusion holds even if the proposed suffix initially ends before e
+or extends past e.
+
+Proof. On the true episode every candidate window is present and the
+true anchor q is among the candidates. A premature suffix lacks at
+least one such window, and the exact-end test at the reference
candidate fails because the endpoint q + b_tail lies beyond the
-suffix argument. An excessive suffix, ending past q + b_tail, has
-the true anchor q available as a mandatory endpoint; the exact-end
-test requires the last consumed position to be q + b_tail, which
-fails. Availability. Every window belonging to a candidate list is
-mandatory: a test never removes an unavailable candidate and then
-checks uniqueness among those remaining. Under this convention, the
-placement lemma supplies the windows on all correct uses and the
-preceding two paragraphs cover the incorrect ones. QED
+suffix argument. An excessive suffix, ending past q + b_tail, has the
+true anchor q available as a mandatory endpoint; the exact-end test
+requires the last consumed position to be q + b_tail and therefore
+fails. Every window belonging to a candidate list is mandatory: a
+test never removes an unavailable candidate and then checks
+uniqueness among those remaining. Under this convention the placement
+lemma supplies the windows on every correct use, and the preceding
+two paragraphs cover the incorrect ones. QED
Affine lifts. The recovery chain embeds each update into a larger
-one that mirrors it on a distinguished basis and then surfaces the
-original by Lemma (affine recovery). Recall U_0 = V and
+linear update that mirrors it on a distinguished basis and then
+surfaces the original by Lemma (affine recovery). Recall U_0 = V and
U_{i+1} = F2^(U_i x M) for i = 0, 1, with basis elements written
[v, c], v in U_i and c in M.
-For e in D_0, the true action on V is
- g_0(e): V -> V, g_0(e)(x) = x T_e,
-an affine update with zero constant.
-
-For i in {0, 1} and e in D_i, let g_{i+1,e}: U_{i+1} -> U_{i+1} be
-the affine update whose linear part M_{i+1,e} satisfies:
+Every g_{i,e} for e in D_i is linear. Base case: for e in D_0 the
+action on V is g_0(e)(x) = x T_e, linear over F2 since v -> v T_e is
+linear. Inductive step: the lift g_{i+1,e} below is defined linearly
+from g_{i,e}, so linearity passes to i + 1. No g_{i,e} carries a
+nonzero affine constant, and the affine corrections from the
+affine-line lemma enter only inside the buffer computations that feed
+the graph languages of the split.
- M_{i+1,e}([v, 1_M]) = [v A_{i,e} + b_{i,e}, 1_M] for all v in U_i,
- M_{i+1,e}([v, c]) = [v A_{i,e}, c d_e] for c != 1_M,
+Define the linear map M_{i+1,e}: U_{i+1} -> U_{i+1} on basis
+elements by
-extended uniquely by linearity to U_{i+1}, where g_{i,e}(v) =
-v A_{i,e} + b_{i,e} is the affine decomposition of g_{i,e}. The
-element d_e in M is chosen once and for all depending on e. The
-affine constant of g_{i+1,e} is the basis vector [b_{i,e}, 0_M].
+ M_{i+1,e}([v, 1_M]) = [g_{i,e}(v), 1_M] for all v in U_i,
+ M_{i+1,e}([v, c]) = [v A_{i,e}, c d_e] for c != 1_M,
-The map M_{i+1,e} is linear because it is defined on basis elements
-and extended linearly to formal sums. The image [v A_{i,e} + b_{i,e},
-1_M] as v varies over U_i is a reindexing of the distinguished slice,
-so the map really does land back in the 1_M slice.
+where g_{i,e}(v) = v A_{i,e} is the linear decomposition of g_{i,e}
+and d_e in M is a fixed element depending on e. The assignment
+v -> [g_{i,e}(v), 1_M] is linear in v because g_{i,e} is linear, so
+the two cases define M_{i+1,e} on a generating set and extend
+uniquely to a linear map on U_{i+1}. Set g_{i+1,e} = M_{i+1,e}.
Lemma (lift update). For i in {0, 1}, e in D_i, and v in U_i,
g_{i+1,e}([v, 1_M]) = [g_{i,e}(v), 1_M].
-Consequently, for any sequence e_1 ... e_k in D_i*, the composition
-of g_{i+1,e_1}, ..., g_{i+1,e_k} sends [v, 1_M] to
+Consequently for any sequence e_1 ... e_k in D_i*, the composite
+g_{i+1,e_1} ... g_{i+1,e_k} sends [v, 1_M] to
[g_{i,e_k}(... g_{i,e_1}(v) ...), 1_M].
-Proof. Fix i, e, v. Decompose g_{i,e}(v) = v A_{i,e} + b_{i,e} with
-A_{i,e} linear and b_{i,e} a fixed vector in U_i. Direct calculation:
-
- g_{i+1,e}([v, 1_M])
- = M_{i+1,e}([v, 1_M]) + [b_{i,e}, 0_M]
- = [v A_{i,e} + b_{i,e}, 1_M] + [b_{i,e}, 0_M]
- = [v A_{i,e} + 2 b_{i,e}, 1_M]
- = [v A_{i,e}, 1_M]
- = [g_{i,e}(v) - b_{i,e}, 1_M].
-
-Over F2, the iteration g_{i+1,e}([v, 1_M]) = [g_{i,e}(v), 1_M] holds
-when b_{i,e} = 0. In general, absorb the constant into the
-distinguished basis labels by redefining M_{i+1,e}([v, 1_M]) =
-[g_{i,e}(v), 1_M] and setting the affine constant of g_{i+1,e} to
-zero. This definition is consistent because the map v -> [g_{i,e}(v),
-1_M] is a reindexing followed by an orthogonal translation of the
-distinguished slice; extended to U_{i+1} by sending [v, c] with
-c != 1_M to [v A_{i,e}, c d_e], it is linear.
-
-The composition over a sequence is immediate by induction on k. For
-k = 0 the empty sequence gives the identity. For k >= 1, apply the
-induction hypothesis to e_1 ... e_{k-1} to send v to
-g_{i,e_{k-1}}(... g_{i,e_1}(v) ...), then apply lift-update at e_k to
-reach [g_{i,e_k}(... g_{i,e_1}(v) ...), 1_M]. QED
+Proof. The first statement is the defining prescription of g_{i+1,e}
+on the distinguished slice. For the composite, induct on k: for k = 0
+the empty sequence gives the identity; for k >= 1, apply the induction
+hypothesis to e_1 ... e_{k-1} to reach
+[g_{i,e_{k-1}}(... g_{i,e_1}(v) ...), 1_M], then apply the identity at
+e_k. QED
Lemma (sequence lift). For any D subset of D_i and any i in {0, 1},
graph languages for g_{i+1} on D* yield graph languages for g_i on
-D* by finite Boolean operations. Consequently the sequence lift does
-not increase generalized star height.
-
-Proof. For a sequence w = e_1 ... e_k in D*, the linear part of the
-affine composite of g_{i+1, e_1}, ..., g_{i+1, e_k} is
-M_{i+1, e_1} ... M_{i+1, e_k}. By the lift-update lemma, this product
-sends [v, 1_M] to [g_{i, e_k}(... g_{i, e_1}(v) ...), 1_M]. The
-affine composite on U_{i+1} is therefore of the form
-
- [v, 1_M] M_{i+1, w} + c_{i+1, w} = [g_{i, w}(v), 1_M],
-
-with g_{i, w} the composite of g_{i, e_1}, ..., g_{i, e_k}.
-
-Let R_{xi, zeta} be graph languages for the affine composite on
-U_{i+1}. By Lemma (affine recovery), the graph language for the
-distinguished composite {v -> w} in U_i is
-
- union over f in U_{i+1} of
- ( R_{[v,1_M], [w,1_M]+f} intersect R_{0, f} ),
-
-where the zero in R_{0, f} is the zero vector of U_{i+1}. By the
-lift-update lemma this is exactly the graph language of g_i on D*.
-
-The formula uses only Boolean operations on the graph languages and
-so does not nest any extra star. This applies to the empty sequence
-as well. QED
-
-Finite clock. The affine-line lemma requires the prefix and suffix to
-communicate finite data. Such a collection is called a tag. The next
-lemma builds a finite clock that controls independent tag choices
-through the two length residues measured from scheduled reference
-positions. Its relation permits either matching tags or a single
-specified mismatch, and that mismatch can later be absorbed into an
-affine correction. A second property bounds ambiguous pairs of
-candidate origins uniformly in their common translation.
-
-Lemma (finite clock). Let Lambda be a finite nonempty set, R a finite
-set, and Q >= 1 an integer. Set F = 400 and
-C = 2^{|Lambda|} (1 + 4 F^2). There exist a positive integer n, all
-of whose prime factors exceed Q, sets I_alpha, J_alpha subset of
-Z/n for alpha in Lambda, a set W subset of Z/n, and residues
-v_p in Z/n for p in R, with:
-
- (i) For every s in Z/n, the relation
- E(s) = {(alpha, lambda) in Lambda x Lambda : s in I_alpha + J_lambda}
- is either a subset of the diagonal or a singleton consisting of
- one off-diagonal pair. If s is not in W, it is the full diagonal.
-
- (ii) For every u in Z/n,
- #{ (p, p') in R x R : p != p', u + v_{p'} - v_p in W } <= C.
-
-Proof. For each map chi: Lambda -> {L, R}, reserve one first
-coordinate and a batch of coordinates. Write r = |R|. Assign each
-coordinate a distinct prime order q satisfying
- q > max(Q, 400, 2^{r+1}).
-Sufficiently many primes exist because Euclid's argument supplies a
-prime beyond any prescribed finite list. The batch contains a
-dedicated coordinate for every ordered list
- ((p_a, p'_a))_{a=0}^{F-1}
-of ordered pairs of distinct elements of R whose underlying unordered
-edges are distinct and form a forest. A spare coordinate is added if
-needed so that the batch has positive odd size. Write G for the
-product of the coordinate groups; G is finite.
-
-Identify a coordinate of prime order q with the subgroup q^-1 Z/Z of
-the circle T = R/Z. Let norm_T(x) denote circular distance from x to
-zero, and call a coordinate value small if norm_T(x) <= 1/100. Put
-C_I = {0, 1, 3}/6 and C_J = {2, 4, 5}/6 in T.
-
-For each tag alpha impose the following constraints in the chi block.
-If chi(alpha) = L, the first coordinate of I_alpha is zero, that of
-J_alpha is nonzero, and in every batch coordinate the I_alpha value
-sits within 1/16 of C_I and the J_alpha value sits within 1/16 of C_J.
-If chi(alpha) = R, the first coordinate of I_alpha is nonzero, that
-of J_alpha is zero, and in a strict majority of batch coordinates
-both I_alpha and J_alpha are small. The constraints over all blocks
-define I_alpha and J_alpha in G. Let W be the union over chi of two
-obstructions: the first coordinate is zero; or no batch coordinate
-is small.
-
-Sums and differences inside one batch. For a left tag and any target
-t in T, choose c_I in C_I, c_J in C_J, and a displacement delta with
-|delta| <= 1/12 so that t = c_I + c_J + delta in T. Round
-c_I + delta/2 to a nearest grid point i and set j = t - i. Both i
-and j are grid points, their distances from c_I and c_J are at most
-1/24 + 1/(2q) < 1/16 since q > 400, and the sum c_I + c_J runs over
-all six multiples of 1/6 as c_I, c_J vary. Any target t therefore has
-a decomposition t = i + j with i in I_alpha and j in J_alpha at
-every batch coordinate. Consequently, every allowed left-tag
-difference i - j obeys norm_T(i - j) >= 1/6 - 2/16 = 1/24 at every
-batch coordinate.
-
-For a right tag, write the batch size as 2k + 1 and choose a small
-target coordinate. At that coordinate assign the target to the first
-summand and zero to the second. Partition the other 2k coordinates
-into two sets of size k. On the first set put zero in the first
-summand and the target in the second; on the second set the reverse.
-Both summands have at least k + 1 small coordinates. Any two allowed
-right-tag values therefore share a small coordinate, since their
-small-coordinate sets are strict majorities. Their difference obeys
-norm_T(i - j) <= 2/100 < 1/24 in that coordinate. So the difference
-sets I_alpha - J_alpha and I_alpha' - J_alpha' are disjoint whenever
-a block places alpha on the left and alpha' on the right.
-
-Full relation. If s is not in W, every first coordinate of s is
-nonzero and every batch has at least one small coordinate. The
-decompositions t = 0 + t and t = t + 0 at the first coordinates,
-together with the batch decompositions above, give s in
-I_alpha + J_alpha for every tag alpha. Choices in distinct blocks
-are independent and combine to give the required element of G.
-
-Suppose an off-diagonal pair (alpha, alpha') belongs to E(s). For a
-competing pair (lambda, mu) with {lambda, mu} different from
-{alpha, alpha'}, choose chi placing alpha on the left, alpha' on the
-right, and both lambda and mu on the same side; this is possible
-whenever {alpha, alpha'} and {lambda, mu} are distinct, because
-identifying two distinct tags on the same side does not also
-identify them on opposite sides. In that block, (alpha, alpha')
-forces the first coordinate of s to be zero, whereas (lambda, mu)
-requires it to be nonzero. No such competitor belongs to E(s). The
-only remaining possible competitor is the reverse pair
-(alpha', alpha). If both pairs represented s there would be
-i_alpha + j_alpha' = i_alpha' + j_alpha with the indicated elements
-in the corresponding tag sets, hence
-i_alpha - j_alpha = i_alpha' - j_alpha'. A block that separates
-alpha from alpha' contradicts the disjointness of the difference
-sets. This proves (i).
-
-Roster. Index R as p_0, p_1, ..., p_{r-1}. In every first
-coordinate, set v_{p_j} = 2^j. For a < b, then
- 2^b - 2^a = 2^a (2^{b-a} - 1).
-The exact power of two dividing the integer difference determines a,
-after which the odd factor determines b - a. Distinct ordered pairs
-give distinct nonzero integers bounded in magnitude by 2^r < q, so
-reduction modulo q is injective on ordered differences. For any
-translate u, at most one ordered pair (p, p') can have
-u + v_{p'} - v_p equal to zero in a fixed first coordinate.
-
-For a dedicated batch coordinate belonging to the list
-((p_a, p'_a)), let z_a be a grid point at circular distance at most
-1/(2q) from a/F. Prescribe
- (v_{p'_a} - v_{p_a}) at that coordinate = z_a.
-These prescriptions are simultaneously satisfiable: choose a root
-value in each tree, then propagate along its edges, and assign
-arbitrary values to any remaining vertices and spare coordinates.
-Doing this in every coordinate gives the desired elements v_p in G.
-
-For a fixed translate t of the batch, one of the equally spaced
-points a/F lies at distance at most 1/(2F) from -t, and the
-corresponding prescribed difference satisfies
- norm_T(t + z_a) <= 1/(2F) + 1/(2q) < 1/400 < 1/100.
-So each dedicated list has a pair whose translated difference is
-small in its dedicated coordinate, uniformly in the translate.
-
-Whole-batch bound. Fix u in G and a batch. An ordered pair (p, p')
-with p != p' is bad for the batch if u + v_{p'} - v_p has no small
-coordinate in the batch. If more than 4 F^2 bad pairs existed, form
-the simple undirected graph whose edges are their underlying
-unordered pairs, discarding isolated vertices. If a spanning forest
-had at most F - 1 edges, its nontrivial components would span at
-most 2F - 2 vertices, since a component with h >= 2 vertices
-contributes h - 1 edges and h <= 2(h - 1), producing at most
-(2F - 2)(2F - 3) < 4 F^2 ordered pairs, a contradiction. Select F
-edges of the spanning forest and orient each as one of the bad
-pairs. The list of these F edges, taken in any order, is a dedicated
-list, and the covering estimate makes one of the pairs small in its
-dedicated coordinate, contradiction. Each batch therefore has at
-most 4 F^2 bad ordered pairs. The same counting applies when the
-roster is too small to admit a dedicated list.
-
-Counting. Every ordered pair (p, p') that lies in W for some
-translate u must have either its translated difference in a
-first-coordinate obstruction or its translated difference with no
-small coordinate in some batch. The first-coordinate construction
-contributes at most one ordered pair per chi block, and each of the
-2^{|Lambda|} blocks contributes at most 1 + 4 F^2 ordered pairs.
-Combining,
- #{ (p, p') : p != p', u + v_{p'} - v_p in W }
- <= 2^{|Lambda|} (1 + 4 F^2)
-for every u in G. This gives (ii).
-
-One cyclic clock. Let n be the product of all coordinate primes. The
-residue map from Z/n to G is injective because the coordinate primes
-are pairwise coprime, and both groups have n elements, so the map is
-an isomorphism. Transport all constructed sets through the inverse.
-Sums, differences, and both properties (i) and (ii) are preserved,
-and every prime factor of n exceeds Q. QED
-
-Polynomial roster. A different construction of the roster uses the
-polynomial-evaluation scheme underlying Reed-Solomon codes. Fix a
-prime P, an integer k_0 = 2 Z + 1 (with Z the number of centers in
-the main segment), and distinct points xi_1, ..., xi_R in F_P. A
-roster slot p is a polynomial over F_P of degree less than k_0,
-including the zero polynomial; its digit at scale r is the value
-p(xi_r). A nonzero polynomial of degree less than k_0 has at most
-k_0 - 1 roots, so any k_0 evaluations determine the slot, and two
-distinct slots agree in at most k_0 - 1 digits. The finite-clock
-lemma accepts any roster, so this polynomial roster serves when many
-residues are required. Only the elementary root bound over the
-prime field is used; the coding theory that follows from the
-Reed-Solomon construction plays no role here.
-
-./reed-solomon-1960.pdf
+D* by finite Boolean operations. The height does not increase.
+
+Proof. For w = e_1 ... e_k in D*, the composite g_{i+1,w} is linear
+and by lift-update g_{i+1,w}([v, 1_M]) = [g_{i,w}(v), 1_M]. The
+graph language W_{g_i}[x, y](D*) therefore equals the graph language
+of g_{i+1} restricted to the distinguished slice,
+W_{g_{i+1}}[[x, 1_M], [y, 1_M]](D*). The restriction uses only finite
+Boolean operations, so the height of W_{g_i} on D* is at most that of
+W_{g_{i+1}} on D*. QED
+
+Splits. The semantic construction breaks each episode into a prefix
+and a suffix at a specified cut and glues the pieces back by the split
+lemma. Three split applications are needed:
+
+ Split Update tested Episode class Skipped class
+ --------- ------------- ------------- -------------
+ main g_0 E D_0
+ stage 0 g_1 D_0 D_1
+ stage 1 g_2 D_1 D_2 = empty
+
+They are invoked in reverse order: stage 1, then stage 0, then main.
+Every episode update g_i is fixed on the entire episode before any
+split is selected.
+
+Two orders of composition coexist. Along the word, buffer 1 precedes
+buffer 0, then the main segment, then the end segment. The total
+update tables are defined in the order g_0, g_1, g_2. The graph tests
+for g_i use the buffer system, the inner system, and the end system
+in that order, and each uses only the data from its own prefix and
+suffix sides of the cut.
+
+Decoding predicates. For e in E with true origin t and anchor q, let
+A_0(t, q) and A_1(t) be finite predicates:
+
+ A_0(t, q) holds iff, at the true candidate p_alpha, the prefix and
+ suffix together pass the uniqueness test at every cut role (j, r)
+ in the finite offset set H_cut.
+
+ A_1(t) holds iff the end guard for eta succeeds at every shift of
+ the origin t + gamma with gamma in Delta_0.
+
+Set D_0 = {e in E : A_0(t, q) or A_1(t)}.
+
+For e in D_0, let B_0(t, q) and B_1(t) be the analogous predicates
+after the stage-0 corrections have been applied. Set
+D_1 = {e in D_0 : B_0(t, q) or B_1(t)}.
+
+Finally D_2 = the empty set. Every complete episode of E or D_0 or D_1
+belongs to exactly one of these predicates at its true origin, since
+the tests are computed by bounded inspection of the letters around t
+and q.
+
+Main split. Let P_x^main and Q_y^main be the split prefix and suffix
+at the main cut. They satisfy the two hypotheses of the split lemma
+for g_0, with D = E and D' = D_0.
+
+Soundness. Suppose a prefix u of a word in E* factors as
+P_x^main Q_y^main. The prefix length is positive and its cut lies
+strictly inside the first episode, so there is a first episode e with
+true origin t and anchor q. The clock's property (i) then gives
+either alpha = lambda on the diagonal (one tag on both sides of the
+cut) or one off-diagonal pair (alpha, lambda). Line constancy from
+the affine-line lemma gives the buffer-corrected affine composite at
+B_l, and Lemma (affine recovery) strips the added correction to
+expose exactly the linear part g_0(e)(x) = x T_e.
+
+Completeness. Fix e notin D_0 and x in V. Then A_0 fails and A_1
+fails at every shift by Delta_0. The inner ambiguity proposition
+supplies at least one usable scale r; the affine-line lemma supplies
+an interval j at that scale; the clock gives a tag; the coprimality
+gcd(delta_r, n) = 1 allows a residue a such that both clock tests
+succeed on the prefix and suffix sides. The split returns
+g_0(e)(x) = y.
+
+Stage 0 split. Let P_x^{(0)} and Q_y^{(0)} be the split prefix and
+suffix at the stage-0 cut, taken inside the buffer 0 segment of the
+episode with the buffer 1 segment preceding. They satisfy the two
+hypotheses of the split lemma for g_1, with D = D_0 and D' = D_1.
+
+Soundness and completeness follow the same pattern, using the clock
+with the stage-0 predicate. Because g_1 is defined to encode g_0
+through the lift, the same affine-recovery step extracts g_1(e)(x)
+from the graph language on U_1.
+
+Stage 1 split. Let P_x^{(1)} and Q_y^{(1)} be the split prefix and
+suffix at the stage-1 cut, taken inside the buffer 1 segment. They
+satisfy the two hypotheses of the split lemma for g_2, with D = D_1
+and D' = D_2 = empty.
+
+Since D_2 is empty, the split hypotheses are vacuous for the skipped
+class: every episode of D_1 already lies in D_1, which is the episode
+class itself. Completeness reduces to the triviality W[x,y](empty) =
+{eps} when x = y and empty otherwise. The height acquisition at this
+bottom step comes from the trivial language {eps}, which has star
+height 0.
+
+Template lemma. Each split prefix language P_x^{(i)} and each split
+suffix Q_y^{(i)}, read as a language over Sigma, is accepted by a
+deterministic test that uses only the following finite data: letters
+in bounded windows at fixed offsets from the cut, the exact order of
+endpoints, M-products across intervals between them, and length
+residues modulo fixed n. Such a language is a finite union of
+templates a b^h c with fixed words a, b, c (b nonempty) and h >= 0.
+
+Consequently each P_x^{(i)} and Q_y^{(i)} has generalized star height
+at most 1.
+
+Proof. Fix all of the finite data. For each fixed pattern of
+endpoints, the test reads a two-sided word whose only nonlocal
+quantity is the length of the period between two consecutive
+endpoints. The M-product across a run of b's raised to the h-th
+power depends on h only through the eventual periodic behavior of
+the finite monoid M, so after the preperiod the test is invariant
+under increasing h by the period. The accepted language, restricted
+to this fixed endpoint pattern and this fixed test residue, is
+therefore a finite union of templates a b^h c with h ranging over one
+arithmetic progression. Since only finitely many endpoint patterns
+and test residues occur, the language is a finite union of such
+templates. The language {a b^h c : h >= 0} equals {a} {b}* {c} at
+height 1; finite unions, intersections, and concatenations of height
+1 languages remain at height 1. QED
+
+Recovery chain. The height bookkeeping follows the split order in
+reverse: stage 1, then stage 0, then main.
+
+Stage 1. The split prefix P_x^{(1)} and suffix Q_y^{(1)} have height
+at most 1. The skipped class D_2 is empty, so W[x, y](D_2) has
+height 0. The split lemma applied to the episode class D_1, testing
+update g_2, therefore gives graph languages for g_2 on D_1 of height
+at most max(2, 0 + 1) = 2.
+
+Sequence lift. Lemma (sequence lift) at i = 1 transforms graph
+languages for g_2 on D_1 into graph languages for g_1 on D_1 of the
+same height 2.
+
+Stage 0. The split prefix P_x^{(0)} and suffix Q_y^{(0)} have height
+at most 1. The skipped class D_1 has graph languages for g_1 on D_1
+of height 2. The split lemma applied to the episode class D_0,
+testing update g_1, gives graph languages for g_1 on D_0 of height
+at most max(2, 2 + 1) = 3.
+
+Sequence lift. Lemma (sequence lift) at i = 0 transforms graph
+languages for g_1 on D_0 into graph languages for g_0 on D_0 of the
+same height 3.
+
+Main. The split prefix P_x^main and suffix Q_y^main have height at
+most 1. The skipped class D_0 has graph languages for g_0 on D_0 of
+height 3. The split lemma applied to the episode class E, testing
+update g_0, gives graph languages for g_0 on E of height at most
+max(2, 3 + 1) = 4.
+
+Now g_0(e)(x) = x T_e is the monoid action on V = F2^M. Take
+x = 1_M and y = e_m; the graph language W[1_M, e_m](E) equals
+{w in E* : T(w) = m}. Its height is at most 4.
+
+Final theorem. Every regular language over a finite alphabet has
+generalized star height at most 4.
+
+Proof. Fix a regular language L over Sigma and let M be its
+syntactic monoid, finite. Let T: Sigma* -> M be the syntactic
+morphism. Choose L_0 = |M| + 1 and let E = Sigma^{L_0} be the prefix
+code of all words of length L_0 over Sigma.
+
+Every word w in Sigma* factors uniquely as w = e_1 e_2 ... e_k r with
+e_a in E, k >= 0, and r in Remainders, where Remainders is the finite
+set of words of length less than L_0. Uniqueness follows from the
+prefix-code property of E. Apply the recovery chain to E: for every
+m in M, the graph language U_m = {w in E* : T(w) = m} has star
+height at most 4.
+
+For w = e_1 ... e_k r, the syntactic value is
+T(w) = T(e_1) ... T(e_k) T(r) = T(e_1 ... e_k) T(r). Therefore
+w belongs to L exactly when T(e_1 ... e_k) T(r) in T(L), i.e.,
+T(e_1 ... e_k) in T(L) T(r)^{-1}. This gives
+
+ L = union over r in Remainders of
+ union over m in T(L) of U_{m T(r)^{-1}} {r}.
+
+Each set on the right is a graph language of height at most 4
+concatenated with the single word r, whose language {r} has star
+height 0. Finite unions and concatenations by height 0 languages
+preserve the height bound. Therefore L has generalized star height at
+most 4.
+
+Kleene's theorem (1951) ensures that every regular language over
+Sigma is described by some regular expression; the construction above
+produces such an expression, and it has star height at most 4. This
+completes the proof.
+
+A complementary question, whether star height 1 always suffices,
+remains open. The proofs in the papers cited above for nilpotent
+class-two groups, and the analogues of the height-four construction
+for a uniform bound, leave the sharp threshold at 4 unresolved.