diff 2167f8f..eab029b generalized_star_height_four_v2.txt
diff --git a/generalized_star_height_four_v2.txt b/generalized_star_height_four_v2.txt
index 81e4cb5..920e421 100644
--- a/generalized_star_height_four_v2.txt
+++ b/generalized_star_height_four_v2.txt
@@ -1,1472 +1,1231 @@
-GENERALIZED STAR HEIGHT AT MOST FOUR
+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).
+
+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.
+
+The theorem proved is the following.
+
+ 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.
+
+./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-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.
+
+./pst-1992.pdf
+./straubing2002.pdf
+
+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
+ 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
+
+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.
+
+./krieger1982.pdf
+./meyerovitch-2025.pdf
+
+ 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.
+
+There are Z centers for the boundaries and R_s scales for each cut
+role. The clock-tag set is
+
+ 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.
+
+Its ambiguity constant C depends only on the tag set.
+
+Let kappa_0 be the number of stage-0 buffer kinds. Choose a prime
+P > R_s large enough that
-A COMPLETE WALKTHROUGH
+ floor(P^{k_0} / kappa_0) > C_0,
+ C_0 = C + 2^{R_s} (3 Z + 1)^{R_s} P^{2 Z}.
+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
-HOW TO READ THIS DOCUMENT
+ x_r(p) = p(xi_r).
-This is a plain-language but mathematically complete account of the
-paper "Generalized star height at most four." The technical original
-is a journal-length research paper. This walkthrough states every
-main theorem exactly, defines every term, and explains every major
-step at a level suitable for a motivated high-school student who
-knows sets, functions, and basic algebra. If you follow the whole
-thing you will know precisely what the paper proves and why each
-piece of the proof is needed.
+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.
-If you want only the headline, read Part 1 (the question) and Part
-11 (the answer). If you want the full construction, work through
-Parts 2 through 10 in order. Parts 3-10 are the technical
-construction; if you get lost there, you can read Part 11 and Part
-12 to see what was proved and what is still open. A short glossary
-is at the end.
+./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.
-PART 1. THE QUESTION
+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
+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
+ smooth and divisible by N sigma for every smooth positive integer
+ sigma <= S_r. Then gcd(delta_r, n) = 1.
-1.1 Regular languages and star height
+ (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
+ separated from one another and from zero by more than
+ 10 (J_r + R_r + 1). Write h'_r for their diameter.
-Fix a finite alphabet Sigma, a finite set of "letters" (for example
-Sigma = {a,b}, or Sigma = {a,b,c}, or any other finite set). A word
-is a finite sequence of letters, like "abba" or "aabcb" or the
-empty word epsilon of length zero. A language is any set of words.
-The set of all words of every length, including epsilon, is
-Sigma*.
+ (iii) Choose S'_r > max(S_r, 10 (h'_r + J_r + R_r + 1)).
-A regular expression is a formula that describes a language. Its
-basic constructs are
+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.
- 0 the empty language
- 1 the language {epsilon}
- a the language {a}, for each letter a
- P + Q the union of P and Q
- P Q the concatenation: all pq with p in P, q in Q
- ~P the complement of P in Sigma*
- P* the Kleene star of P: all finite concatenations of
- words of P, including the empty concatenation
+Assign slot p the numerical offset
-Every regular language can be described by some regular expression:
-this is Kleene's theorem from 1951.
+ sum_{r=1}^{R_s} f_r(x_r(p)) + eps_p, 0 <= eps_p < n.
-The star height of an expression is the deepest nesting of stars
-inside it:
+Choose eps_p so that 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.
- ht(0) = ht(1) = ht(a) = 0
- ht(P+Q) = ht(PQ) = max(ht(P), ht(Q))
- ht(~P) = ht(P)
- ht(P*) = 1 + ht(P)
+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,
-The generalized star height of a regular language L is
+ h_0 < n + sum_r h'_r.
- h(L) = min over expressions E with L(E) = L of ht(E).
+Inner controls. The inner boundary rule needs marker parameters far
+exceeding every scale and every monoid period. Choose integers
-It measures how deeply the star operator must be nested if we try
-to describe L exactly, with no limit on how many times we use the
-other operations.
+ 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
-1.2 The ordinary (non-complemented) problem is unbounded
+ H > 10 ((N + m + 1) d_o + (max_r R_r) + 1).
-If you take regular expressions and forbid the complement, you
-get the "ordinary" star height problem. In 1963 Eggan introduced
-this notion and observed that different regular languages need
-different depths. In 1966 Dejean and Schutzenberger proved that
-ordinary star height is unbounded: over the binary alphabet there
-are regular languages of ordinary star height 1, 2, 3, and so on
-without bound.
+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).
-Adding complement changes everything. A famous theorem of
-Schutzenberger (1965) classifies the star-free languages, meaning
-the languages of ordinary star height 0: they are exactly the
-languages whose syntactic monoid is aperiodic (contains no
-nontrivial group). The same criterion controls generalized star
-height 0, because adding complement does not remove the need for
-stars: a language has generalized height 0 if and only if it is
-recognized by an aperiodic finite monoid.
+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).
-1.3 The open question of height one
+The definition does not depend on the representative of x. Moreover,
-What about height one? Several beautiful theorems are known.
+ gcd(d, sigma N) = sigma,
+ lcm(d, sigma N) = d N,
- Henneman (as recalled in Pin-Straubing-Therien 1992, Theorem
- 3.4): every language recognized by a finite commutative group
- has generalized height at most one.
+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].
+
+Center spacing. Choose an even integer
+
+ G > 10 (H + r_o + (max_r R_r) + 1).
+
+For the main segment set
+
+ o_j = (j + 1) G,
+ z_j = t + o_j, B_j = B(z_j), (0 <= j <= l),
+ c_j = (o_{j-1} + o_j) / 2, (1 <= j <= l).
+
+At another proposed origin tau, write z_j(tau) = tau + o_j and
+B_j(tau) = B(z_j(tau)). The notation without an argument refers to
+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.
+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
+
+ 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,
+
+ (i) u(z_j + h) = u(z_j) for every integer h with |h| <= R_r,
+ including agreement on absence;
+
+ (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.
+
+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).
- Pin-Straubing-Therien (1992, Theorem 7.3): the same conclusion
- holds for every finite nilpotent group of class two.
+For a fixed endpoint b >= z_l + H, the last transfer gives
-These results are algebraic. They fall far short of a general
-theorem. The fact is that nobody knows whether every regular
-language has generalized star height at most one. That is a
-different, still-open question. The question addressed here is the
-weaker question: is there any fixed absolute bound?
+ 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.
-1.4 The main theorem
+Proof. Three steps: the two boundaries at each center lie in one
+class modulo d N; the periodic run around each boundary is long
+enough; and monoid-power periodicity turns the shift into an identity
+on the level of ordered products.
-This paper proves:
+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
+|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.
+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
+[z - R_r, z + R_r] contains no point of the lattice x + sigma Z and
+the boundary does not move at all. In either case,
- Theorem. For every finite alphabet Sigma and every regular
- language L contained in Sigma*, one has
+ B(z + h) - B(z) = q d N with |q| d N <= 2 H + R_r.
- h(L) <= 4.
+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.
-The bound 4 is absolute. It does not depend on Sigma, on L, or on
-the number of states of any automaton recognizing L. It does not
-assert that 4 is necessary: some languages may have smaller height,
-possibly height 1. What the theorem says is that 4 is always
-enough.
+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
-The number 4 comes from a chain of three star-producing splits
-plus one star-free compilation step. This paper also has two
-companion papers:
+ 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)}].
- Uniform13 (companion, "Finite monoid computations and a uniform
- generalized star-height bound"): proves height 13.
+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
- Height3 (companion, "Generalized star height at most three"):
- proves height 3.
+Proposition (inner ambiguity). For every stage-0 tag alpha and every
+u in Z/n,
-Each paper proves its own required algebra, timing statements,
-and original-alphabet compilation. The bound 3 is the strongest
-known; the present paper's split and multiscale method is
-independent of that and does not rely on the companion theorem.
+ #{(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.
-PART 2. TOUR OF THE PROOF
+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)),
-2.1 The reduction to a finite monoid
+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.
-The expression we want to construct is over the original alphabet
-Sigma. But every regular language is recognized by a finite
-deterministic automaton, and every such automaton yields a finite
-monoid M together with a morphism
+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
+witnesses across the R_s scales. Summing the Z-center choices over
+the R_s scales gives the finite bound
- T : Sigma* -> M
+ (3 Z + 1)^{R_s} P^{2 Z}
+
+on the number of gamma offsets that survive A_1 at one translate.
+Multiplying,
+
+ |D| <= 2^{R_s} (1 + 4 F^2) (3 Z + 1)^{R_s} P^{2 Z} <= C_0,
+
+which proves the bound. QED
+
+End system. Episodes end at deterministic anchors. The end system
+consists of four pieces.
+
+ (i) A second instance of the local-markers lemma, called the end
+ markers, with integer parameters d_e, K_e, and radius r_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.
+
+ (iv) A fixed positive integer b_tail, chosen large enough that the
+ end windows sit strictly before q + b_tail.
+
+Parameters. Choose integers
+
+ d_e > 2 (h_e + w) + 1,
+ K_e > 3 d_e^2,
+
+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 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.
+
+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.
+
+Episode ends. 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.
+
+ (A) Fix the buffer offsets from s and place buffer 1, including
+ a_1, before buffer 0.
-that assigns to each word the "type" of its action on the
-automaton's states. If q_0 is the start state and F the set of
-accepting states, then L is a finite union of fibers T^{-1}(m),
-one for each m in M with q_0 . m in F.
+ (B) Choose L large enough that the inner envelope, containing the
+ inner windows of the buffer cuts, sits after all buffer data.
-So it suffices to build a generalized expression of height at most
-4 for T^{-1}(m) for each m in M, and then take the finite union.
-The construction below does exactly this.
+ (C) Choose o_e large enough that the end envelope, containing the
+ end markers, the seed block, and the end windows, sits after the
+ inner envelope.
-The finite monoid M has an "affine lift" trick that turns the
-question into a statement about linear maps on a finite-dimensional
-vector space V over F_2. Instead of tracking just the monoid value
-of the whole word, we track a linear map on V whose "basis
-survivor" encodes the monoid value. This makes the math linear and
-allows the affine-line lemma (Part 5) to apply.
+ (D) Choose b_tail large enough that the fixed tail sits after 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.
-2.2 Three essential tricks
+Lemma (placement). The translations of the two buffers and the
+integers L, o_e, b_tail can be chosen so that:
-The proof uses three genuinely different tricks.
+ (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.
- Trick 1. Split a sequence into a prefix and a suffix.
- Given a word that is a sequence of small "episodes," we can cut
- it at a specific place. The prefix announces its own state, the
- suffix announces its output, and the two sides agree on enough
- finite data to determine the total. This builds a graph test on
- a larger class of episodes from a graph test on a smaller
- class. Each split application introduces one new star.
+ (ii) Every bounded window required at main hypotheses or at
+ aligned buffer hypotheses is internal to every complete episode
+ at a true cut.
- Trick 2. Hide one interval product by an affine correction.
- Suppose a word splits into l equal-length intervals, and neither
- side can read the product across the cut. We precompute a
- correction function beta that, for every possible tuple of
- interval products, hides one of them: for every tuple some
- coordinate is "evadable." The prefix goes up to the cut and
- announces everything weak; the suffix reads the rest and checks
- "constancy along a line." The existence of beta is
- probabilistic: the Erdos-Lovasz local lemma guarantees that a
- random beta works.
+ (iii) A prefix or suffix computation has its required data on its
+ own side of a true cut.
- Trick 3. A finite clock and multiple scales.
- When a prefix chooses one of finitely many "tags" and a suffix
- chooses another, we need to decide whether they are compatible
- using only finitely many residue tests. The clock provides such
- tests. The scales let us "slide" a boundary through a periodic
- region without changing any interval product, so we can always
- find a cut position that avoids finitely many bad shifts.
+ (iv) Every possible true first-episode end is after all cuts and
+ bounded control windows.
-2.3 The height ladder
+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
+
+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.
-The central construction is a sequence of five steps that raise
-the height from 0 up to 4:
+Lemma (end ambiguity). On any two-sided word, 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|.
- height 0 -> height 2 stage 1 aligned split
- height 2 -> height 2 recover g_1 from g_2 (Boolean)
- height 2 -> height 3 stage 0 aligned split
- height 3 -> height 3 recover g_0 from g_1 (Boolean)
- height 3 -> height 4 main split
-
-Each split adds exactly one. Each recovery is Boolean and adds
-nothing. The Boolean recoveries are what let us interleave lifts
-of the update without paying extra height for them.
-
-2.4 What is not claimed
-
-The proof gives no runtime bound. The finite choices of
-parameters are made by exhaustive search, but the sizes of the
-objects obtained are not controlled. The expressions produced
-are finite objects with bounded height; their lengths and the
-running times to find them are arbitrary.
-
-The proof does not exhibit any specific regular language that
-needs height more than 1. It is completely compatible with the
-conjecture that height 1 always suffices.
-
-
-PART 3. ALGEBRA: EPISODES, INTERVALS, AND GRAPH LANGUAGES
-
-
-3.1 Episode prefix codes
-
-Let E be a set of nonempty words over Sigma such that no member of
-E is a proper prefix of another member of E. Such a set is called
-a prefix code, and its elements are called episodes.
-
-The defining property of a prefix code is: every word in E* (every
-concatenation of episodes) has a unique factorization into
-episodes. Proof: compare the first factors of two factorizations of
-the same word. Both are prefixes of the word, so one is a prefix
-of the other; the prefix-code property forces them to be equal.
-Cancel and continue by induction.
-
-We build E from "small complete words" that a deterministic
-end-marker rule selects: an episode starts at s and ends exactly at
-its anchor position plus a fixed tail. Because the endpoint is
-uniquely determined by the word's own letters up to and including
-that point, prefix relations are impossible (an episode would have
-to be a proper prefix of another episode, contradicting the
-deterministic rule). Section 8 proves this elementary fact.
-
-
-3.2 Interval products
-
-Fix a finite monoid M and a morphism T : Sigma* -> M (Section
-2.1). For a word w_1 w_2 ... w_k, let T(w) in M be the product of
-letters in reading order. Write T_{a,b} for the product of letters
-at positions a, a+1, ..., b-1, the "interval product" from cut a to
-cut b. Because T is a morphism, T_{a,c} = T_{a,b} * T_{b,c} for
-a <= b <= c. Each letter occupies a unit interval [i, i+1), and the
-endpoint i is the cut before the i-th letter.
-
-
-3.3 A vector space that distinguishes monoid elements
-
-Let V = F_2^M be the vector space with basis indexed by M. Right
-multiplication in M gives a linear right action of M on V:
-
- e_c . d = e_{cd}, extended to V by F_2-linearity.
-
-The key property: e_{1_M} . d = e_d tells us which monoid value
-produced it, so a linear map on V that survives to e_m identifies
-m. In the construction we will track affine maps on V whose linear
-part is x -> x T(w) for the total monoid value of the word. Then
-e_{1_M} is transported to e_{T(w)}; reading the surviving basis
-index gives T(w). Fibers T^{-1}(m) are then distinguished by the
-surviving basis index.
-
-
-3.4 Graph languages
-
-Suppose each episode e carries a deterministic update G_e of a
-fixed finite state set S. For x, y in S, the graph language from x
-to y on D* (where D is a subset of E) is
-
- W_{x,y}(D) = { w in D* : the composite update of w sends x to y }.
-
-The domain condition is part of the language: it accepts no word
-outside D*. The empty word carries the identity update and lies in
-W_{x,x}.
-
-
-3.5 Buffers and kinds (preview)
-
-Each episode will have two "buffer" regions preceding its main
-cut, physically laid out in the order 1 then 0 along the word
-(this reversed order is explained in Section 8.7). Buffer i has
-checkpoints B_{i,0} < ... < B_{i,l_i} < a_i, giving l_i "interval
-products" d_{i,1},...,d_{i,l_i} with d_{i,f} = T_{B_{i,f-1},
-B_{i,f}}. The "kind" of a buffer hypothesis is the tuple
-
- (j, v, d_1, ..., d_{j-1}) with 1 <= j <= l_i, v in U_{i+1},
- d_f in M.
-
-It records the hidden interval index, the input vector at the start
-of the buffer, and the preceding interval products.
-
-
-PART 4. THE SPLIT LEMMA
-
-
-4.1 The split identity
-
-The split lemma converts a graph test on D'* (a smaller class) into
-one on D* (a larger class), via two auxiliary languages P_x and Q_y.
-
- Lemma. Let D' be a subset of D, where D is a subset of the
- prefix code E. Let (G_e) be deterministic updates of a finite
- state set S. Suppose languages P_x, Q_y (x, y in S) satisfy:
-
- (i) If a word in D* has a prefix u v with u in P_x and
- v in Q_y, then its first episode e exists, u v = 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)}.
-
- Then the graph language from x to y on D* equals
-
- D* intersect ( W_{x,y}
- + (union_a W_{x,a} P_a)
- ( union_{b,c} Q_b W_{b,c} P_c )*
- ( union_f Q_f W_{f,y} ) ),
-
- where W_{x,y} is the graph language from x to y on D'*.
-
- If D, all P_x, and all Q_y have height at most one, and every
- W_{x,y} has height at most b, then the graph language from x
- to y on D* has height at most max(2, b+1).
-
-
-4.2 Idea in words
-
-Episodes in D' are "easy": the W-languages handle them directly,
-without any splitting. Episodes in D \ D' are "hard": each is in
-P_x Q_{G_e(x)} for the true current state x (condition ii), so we
-split it into a prefix announcing "we are in x" and a suffix
-announcing "we came out at y". Between splits the word runs through
-D'-episodes, which W absorbs. The central star lets us repeat the
-alternation as many times as needed.
-
-Condition (i) is the soundness condition: it prevents P and Q from
-cheating by producing a fake episode. Condition (ii) is the
-completeness condition: every D \ D'-episode can be split honestly
-at least one way.
-
-
-4.3 Soundness in detail
-
-Suppose a word is accepted by the right side of the split identity.
-It is in D* by the outer intersection, so it really is a
-concatenation of D-episodes. The W-factors, by the prefix-code
-property, respect that factorization: each W-factor consumes whole
-episodes. The explicit P Q pairs, by condition (i), consume the
-next episode and send the current state to the announced target.
-Alternating through the central star's rounds, we induct on the
-rounds and conclude that the composite update sends x to y.
-
-The first term W_{x,y} is handled by induction on D'*: those
-episodes never needed splitting.
-
-
-4.4 Completeness in detail
-
-Take any word in D* with update from x to y. Split each D \ D'-
-episode using condition (ii): the current state is the true one,
-and the episode lands at its honest G_e. Chop the word at every
-D \ D'-episode; each D'-run is handled by its W; each explicit
-split is a P Q pair. This gives a factorization accepted by the
-right side. If there are no D \ D'-episodes, W_{x,y} captures the
-whole word.
-
-
-4.5 Height
-
-The outer D* has height at most 2, because D is contained in the
-prefix code E: a word is in D* if it is a concatenation of
-episodes AND every episode is in D; both are height-1 languages,
-and their intersection has height 2.
-
-The central star has operand of height max(1, b), so it contributes
-height max(2, b+1). All other operations (finite unions,
-concatenations, intersections) don't raise the height. This is the
-one place in the whole construction where height increases.
-
-
-PART 5. AFFINE CORRECTION AND THE AFFINE-LINE LEMMA
-
-
-5.1 Why affine correction is needed
-
-At an interior cut, neither side can read the interval product d_j
-that straddles the cut. We precompute a correction beta such that
-even without d_j the total output can be recovered. The trick is
-to work with affine updates
-
- G_e(v) = v L_e + sigma_e (v in U, L_e linear, sigma_e in U)
-
-on a finite-dimensional F_2-vector space U with a linear right
-action of M. Affine updates compose to affine updates: v |-> v L +
-c, where L = L_1 L_2 ... L_k (product in reading order) and c is a
-constant. If c is readable by the suffix, and v L is what we want,
-we can use a Boolean "recovery" step at the end to extract the
-linear part.
-
-
-5.2 Affine recovery lemma
-
- Lemma. Let U be a finite-dimensional F_2-vector space, D a
- subset of the prefix code E, and the update for e in D affine:
-
- G_e(v) = v L_e + sigma_e.
-
- If R_{v,y} are graph languages for the affine composite on D*
- (from v to y), then the graph language of the product of the
- linear parts (from v to y) is
-
- union over f in U of ( R_{v, y+f} intersect R_{0, f} ).
-
- This recovery uses only finite Boolean operations.
-
- Proof. On any word of D*, the affine composite has form v |-> v
- L + c. Its output at v is v L + c; at 0 it is c. The difference
- is v L. The displayed intersection says "the first output is
- y + f and the second is f," which is exactly "v L = y." QED.
-
-
-5.3 Affine-line lemma
-
- Lemma. Let U be a finite-dimensional F_2-vector space with a
- linear right action rho of M. There exist an integer l >= 1 and
- a function beta : M^l -> U such that for every v in U and every
- tuple d = (d_1, ..., d_l) in M^l, some index j in {1,...,l}
- makes the function
-
- 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.
-
-
-5.4 Intuition
-
-Think of d as a center point in the l-dimensional grid M^l. Through
-it run l coordinate lines (one per coordinate direction). On each
-line, only one coordinate varies; the other l-1 are fixed.
-
-For a given v and d, we want SOME coordinate line to make the
-function of a_j constant. If beta is chosen uniformly at random in
-U^(M^l), then the chance that a specified line is constant is
-q_U^{1-m}, because beta must take one specified value at each of
-the m-1 off-center points on that line (each with probability 1/q_U).
-Different lines through the same center touch disjoint sets of
-off-center points, so their constancy events are independent.
-
-So the probability that a specific (v, d) is BAD (no line constant)
-is p_l = (1 - q_U^{1-m})^l, which decays exponentially in l. For
-large l, most centers are good.
-
-The uniformity is essential: a single beta must work for all v and
-all d simultaneously. So we need to rule out ALL bad centers.
-
-
-5.5 Erdos-Lovasz local lemma
-
-The naive union bound fails: q_U * m^l pairs, each failing with
-probability p_l, gives q_U * m^l * p_l, which is huge.
-
-The Erdos-Lovasz local lemma does better. If the failure events
-have bounded maximum dependency degree Delta (each is independent
-of all but at most Delta others) and each has probability at most
-u (1-u)^Delta for some u in (0,1), then all events can be avoided
-simultaneously. Here, the dependency degree is bounded by
-
- Delta_l = q_U (1 + l m + l^2 m^2),
-
-the number of centers within Hamming distance 2 of a given one.
-Choose u = 1/(2 Delta_l); Bernoulli's inequality gives
-u (1-u)^Delta_l >= 1/(4 Delta_l). Since p_l decays exponentially,
-choose l large enough that p_l <= 1/(4 Delta_l). The local lemma
-then gives a choice of beta with no bad centers. Fix such a beta.
-
-
-5.6 Uniformity
-
-The choices of l and beta depend only on U, M, rho. They are fixed
-before any v or d is given. The successful coordinate j is allowed
-to depend on v and d. So the whole procedure is uniform in the cut
-and in the input.
-
-The proof is effective in principle: enumerate l = 1, 2, ...; for
-each, check p_l <= 1/(4 Delta_l); the first l that works stops the
-search. Enumerate the finitely many candidate beta and test. At
-least one passes. This gives a finite existence proof, but no
-useful running-time bound.
-
-
-5.7 Applying the lemma to a word segment
-
-To apply the affine-line lemma to a word segment, choose l ordered
-checkpoints B_0 < ... < 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 can transmit 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. When that check holds, it obtains the correct vector at B_l
-without knowing d_j. For every actual tuple and input at least one
-interval permits this procedure. Because the added vector depends
-only on the actual tuple, the composite of the whole segment is
-still affine and remains eligible for the recovery lemma.
-
-
-PART 6. THE FINITE TAG CLOCK
-
-
-6.1 The problem the clock solves
-
-At a main split, the prefix chooses a finite "tag" alpha and the
-suffix independently chooses a finite "tag" lambda. We need a
-finite test that says "alpha and lambda are compatible at this cut."
-The clock converts this into a residue test "s in I_alpha +
-J_lambda" modulo a modulus n. It also supplies a "bad set" of
-residues W and gives each roster item p a residue v_p, so that at
-most boundedly many translate-rosters produce collisions in W.
-Everything is finite and enumerable.
-
-
-6.2 Clock lemma
-
- Lemma. For every finite monoid M, there exist a modulus n, a
- prime q dividing n, a finite tag set Lambda with maps X, Y :
- Lambda -> M, and finite sets I_alpha, J_lambda in Z/nZ (alpha,
- lambda in Lambda) satisfying:
-
- (i) For every s in Z/nZ, the relation
-
- E(s) = {(alpha, lambda) in Lambda^2 : s in I_alpha +
- J_lambda}
-
- either is contained in the diagonal { (a,a) : a in Lambda }
- or is a singleton consisting of an off-diagonal pair.
-
- (ii) There is a set W in Z/nZ such that, for every ordered
- list ((p_a, p'_a))_{a=0}^{F-1} of F distinct roster items
- with underlying undirected edges forming a forest, the
- number of ordered pairs (p, p') with p != p' whose
- difference residue v_p - v_{p'} lands in W is at most
-
- C_cl = 2^{|Lambda|} (1 + 4 F^2),
-
- where F = 400.
-
- The construction is explicit and finite. Here are the key ideas.
-
-
-6.3 Coordinate blocks per left/right assignment
-
-For every map chi : Lambda -> {L, R} we build one "first coordinate"
-of prime order q (large) and a "batch" of redundant coordinates. A
-tag alpha is "left" at chi if chi(alpha) = L, else "right."
-
-First coordinate:
- - Left tag alpha: the first coordinate of I_alpha is exactly 0.
- - Right tag alpha: the first coordinate of I_alpha is nonzero.
- - Left tag alpha: the first coordinate of any element of J_alpha
- is nonzero.
- - Right tag alpha: the first coordinate of J_alpha is exactly 0.
-
-Batch coords (all left tags alpha):
- - I_alpha sits within 1/16 of a center from C_I = {0, 1, 3}/6.
- - J_alpha sits within 1/16 of a center from C_J = {2, 4, 5}/6.
-Right tags: both I_alpha and J_alpha are "small" in a strict
-majority of batch coordinates (within 1/100 of 0).
-
-
-6.4 Two key inequalities
-
- Sums cover everything. For a left tag, any target t is a sum:
- C_I + C_J contains all six multiples of 1/6, and 1/16 slack in
- each batch absorbs any rounding error. For a right tag, any
- target with a small coordinate in each batch is a sum. Hence an
- s notin W (which has a small coordinate in every batch) is a
- sum for every tag.
-
- Differences are separated. Across EVERY batch coordinate, any
- left-tag diagonal difference i - j (i, j from I_alpha, J_alpha
- for the same left tag alpha) has |i - j| >= 1/6 - 2/16 = 1/24.
- Across SOME batch coordinate, any right-tag diagonal difference
- i' - j' (same right tag alpha') has |i' - j'| <= 2/100 < 1/24.
- So a left-diagonal difference and a right-diagonal difference
- can never be equal as full vectors.
-
-
-6.5 Why relation (i) holds
-
-Take any fixed chi. In the first coordinate:
-
- - Left tag alpha: I_alpha first = 0, J_alpha first nonzero.
- - Right tag alpha: I_alpha first nonzero, J_alpha first = 0.
-
-Excluding off-diagonal pairs when s notin W. Suppose s notin W, so
-every first coordinate of s is nonzero. If (alpha, alpha') were an
-off-diagonal pair in E(s), choose a chi with alpha left and alpha'
-right. In this block, s[first] = I_alpha[first] + J_alpha'[first]
-= 0 + 0 = 0. Contradiction. So no off-diagonal pair is in E(s).
-
-The full diagonal is present for s notin W by the sum
-constructions (left tags: any target; right tags: any target with
-a small coordinate). So E(s) is exactly the full diagonal.
-
-At most one off-diagonal pair, at any s. Suppose (alpha, alpha')
-is an off-diagonal pair in E(s). Any other pair (lambda, mu) with
-different unordered pair may be excluded: choose a chi with alpha
-left, alpha' right, and lambda, mu on the same side. In this block,
-(alpha, alpha') forces s[first] = 0, while (lambda, mu) forces
-s[first] != 0. Contradiction, so (lambda, mu) is not in E(s).
-
-The remaining competitor is the reverse pair (alpha', alpha). If
-both are in E(s), there would be elements satisfying
-
- i_alpha + j_alpha' = s = i_alpha' + j_alpha,
- so i_alpha - j_alpha = i_alpha' - j_alpha'.
-
-LHS is a left-diagonal difference (for left tag alpha); RHS is a
-right-diagonal difference (for right tag alpha'). By the two key
-inequalities, these can never be equal as full vectors.
-Contradiction. So only one off-diagonal pair survives at s.
-
-
-6.6 Roster residues v_p
-
-In every first coordinate of every chi, place roster items p_0,
-p_1, ... with v_{p_j} = 2^j modulo q. For two distinct a < b,
-
- v_{p_b} - v_{p_a} = 2^b - 2^a = 2^a (2^{b-a} - 1).
-
-The exact power of 2 identifies a, and after removing it, the odd
-factor 2^{b-a} - 1 identifies b - a. So distinct ordered pairs give
-distinct nonzero integers, and choosing q > 2^r preserves this in
-Z/qZ. The v_p are then distinct on every first coordinate.
-
-
-6.7 Dedicated batch coordinates
-
-For every ordered list ((p_a, p'_a))_{a=0}^{F-1} of F distinct
-roster items with underlying undirected edges forming a forest,
-give one dedicated batch coordinate. Set z_a = grid point within
-1/(2q) of a/F, and prescribe v_{p'_a} - v_{p_a} = z_a in this
-coordinate. This is satisfiable (forest has no cycle constraint).
-
-Then for any translate u, some a has |u + z_a| <= 1/(2F) + 1/(2q)
-< 1/400 < 1/100. So every dedicated forest has a NEGATIVE witness:
-some pair with SMALL translated difference in that coordinate.
-
-Counting bad ordered pairs for a batch. Fix u and a batch. Call a
-pair (p, p') "bad" if u + v_{p'} - v_p has no small coordinate.
-Form the undirected graph of bad pairs (drop isolated vertices). If
-a spanning forest had fewer than F edges, its vertices would be at
-most 2F - 2, so the number of unordered pairs would be at most
-(2F-2)(2F-3) < 4F^2. But we could pick F edges of the forest and
-they would form one of the dedicated lists, forcing a violation.
-So a spanning forest has >= F edges; hence the number of bad
-ordered pairs is at most 4F^2. Take the union over all 2^{|Lambda|}
-blocks and add 1 from the first-coordinate obstructions: total
-at most C_cl = 2^{|Lambda|} (1 + 4 F^2).
-
-
-PART 7. LOCAL MARKERS AND MOVING BOUNDARIES
-
-
-7.1 Why markers and scales
-
-The suffix does not know where the first episode that produced its
-argument truly began. It has a bounded candidate list, but the
-interval products it must check depend on the true start position.
-If the true start is far from every candidate, nothing works.
-
-The remedy is a pair of tools. "Markers" are well-spaced integer
-positions; "scales" are scales of sliding the boundary. Boundaries
-are locally determined: near a marker, the boundary IS the marker;
-away from any marker, the boundary follows a periodic extension of
-the local word. This gives a finite set of possible boundary
-positions and a uniform bound on how often ambiguity fails.
-
-
-7.2 Local markers
-
- Lemma. Let d >= 2 and K > 3d^2. There is a translation-
- equivariant rule marking 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 [z-d, z+d], then the block
- [z, z+K) has a positive period less than d.
-
- Proof sketch. List the finitely many length-K words with no
- positive period below d. Process them in a fixed order, marking
- all starts not within distance < d of an earlier marker. Two
- starts added at the same step cannot be at distance a < d:
- their overlap would make a a period of the listed word.
- Contradiction. The finite list gives a finite inspection
- radius; enlarge it to at least K. The absent-marker conclusion
- follows: any "would-be-marked" start either was marked at its
- step, or has a marker within distance < d. QED.
-
-The marker-vs-periodicity principle is due to Krieger (1982).
-We use only the elementary finite-window version above.
-
-
-7.3 Common periodic extensions
-
- Lemma. A block of length K > 3d^2 with 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 no marker is in [z-H, z+H],
- H >= d, then the actual letters on [z-H+d, z+H-d+K) belong to
- one such extension.
-
- Sketch. A block of period a extends by repeating its first a
- letters. Two two-sided periodic words of periods a, b that
- agree on ab consecutive positions agree everywhere (standard
- fact). Here a, b < d, so ab < d^2. QED.
-
-
-7.4 The vector spaces U_0, U_1, U_2
-
-The construction lifts V = F_2^M to two larger spaces. For any M
-and any F_2-vector space U with a linear right action of M, let
-U x M be the space with basis e_{[v,c]} for v in U, c in M. The
-right action is
-
- [v, c] . d = [v . d, cd].
-
-Then choose U_0 = V, U_1 = U_0 x M, U_2 = U_1 x M. The "work
-actions" rho_i : M -> End(U_{i+1}) on U_{i+1} are defined by
-rho_i(d)([v, c]) = [v, cd]. Note that rho_i has nothing to do with
-the episode structure; it is a generic linear action that only
-multiplies the M-coordinate.
-
-The key property: the basis vector [v, 1_M] is "distinguished", and
-after multiplying by a product of M-elements, the M-coordinate
-stays 1_M. So the distinguished basis is closed under the
-computation, letting us transport vectors of V up through the lifts
-without ambiguity.
-
-
-7.5 Buffer kinds and stencils
-
-Each episode has two buffers preceding its main cut, physically in
-the order 1 then 0 along the word. Buffer i has checkpoints B_{i,0}
-< ... < B_{i,l_i} < a_i. The kind of a buffer-i hypothesis is
-
- (j, v, d_1, ..., d_{j-1}) with 1 <= j <= l_i, v in U_{i+1},
- d_f in M.
-
-It says "the hidden interval index is j, the input vector at B_{i,0}
-is v, and the interval products before j are d_1, ..., d_{j-1}."
-
-A stencil P_i is a finite set of integer offsets from s together
-with a kind assigned to each offset. We need more offsets of each
-kind than the total bad-origin count C_0 = C_cl + 2^{l} (something),
-so that a good offset always exists.
-
-
-7.6 Polynomial roster
-
-Roster items are polynomials p of degree < k_0 over a prime field
-F_P. Fix R distinct evaluation points xi_1, ..., xi_R in F_P. The
-"digit" at scale r is x_r(p) = p(xi_r).
-
-Two distinct polynomials of degree < k_0 have at most k_0 - 1 roots,
-so distinct polynomials differ in at least R - k_0 + 1 = k_0 digits.
-This is the Reed-Solomon distance property.
-
-Choose positions f_r(0) < ... < f_r(P-1) at each scale r so that
-all nonzero digit differences are distinct and well-separated.
-Give slot p the numerical offset
-
- sum_{r=1}^{R} f_r(x_r(p)) + epsilon_p,
-
-where 0 <= epsilon_p < n is a small correction to land on residue
-v_p mod n. Then distinct slots get distinct offsets, any two
-offsets are separated by more than 2, and the residues match v_p.
-Choose P large enough that P^{k_0} / kappa_0 > C_0.
-
-
-7.7 Scales and usability
-
-For each scale r in 1..R, choose integers
-
- S_r < S'_r thresholds
- delta_r smooth (coprime to n)
- R_r = n delta_r movement bound
- f_r as above
-
-with S'_r dominating all smaller scales' diameters and movements.
-The inequalities ensure that a nonzero digit at scale r dominates
-all smaller digits plus the epsilon correction.
-
-A scale r is usable at origin t if, at every center z_j = t + o_j,
-
- - the first-marker search is stable under all shifts of size
- <= R_r (same answer), or
- - the search is absent and the periodic-extension lattice is
- too coarse to be affected by any such shift.
-
-If r is usable, then shifted boundaries B_j^{(h)} := B(z_j + h)
-for h = delta_r a (0 <= a < n) give identical interval products:
-
- T_{B_{j-1}^{(h)}, B_j^{(h)}} = T_{B_{j-1}, B_j} for all j.
-
-
-7.8 Transport lemma
-
- Lemma. Suppose scale r is usable at t, and h is a multiple of
- delta_r with |h| <= R_r. Then T_{B_{j-1}, B_j} = T_{B_{j-1}^{(h)},
- B_j^{(h)}} for all j. And for any fixed end b >= z_l + H,
- T_{B_l, b} = T_{B_l^{(h)}, b}.
-
- Sketch. The two boundaries at each center stay in the same
- class modulo d * N (d = period, N = |M|, since the shift is
- delta_r * n * something). Actual word has a full periodic run
- around each boundary (by the marker lemma). Monoid-power
- periodicity c^{h+N} = c^h for h >= m then gives the interval
- product equality, one endpoint at a time. QED.
-
-
-7.9 Inner ambiguity bound
-
-For an origin t and an anchor q, define the "bad" predicate
-
- A_0(t, q): q - t (mod n) in W, OR no scale usable at t.
-
- Proposition. On any two-sided word, for any integers t, q,
-
- #{(p, p') in P_0^2 : p != p', A_0(t + p - p', q)} <= C_0,
-
- where C_0 = C_cl + 2^R (3Z+1)^R P^{2Z}, with Z = l + 1.
-
- Sketch. Two cases.
-
- (a) Clock failure: q - t - (p - p') mod n in W. By the clock
- property, at most C_cl ordered pairs survive.
-
- (b) No usable scale: examine digit differences D_r = f_r(x_r(p))
- - f_r(x_r(p')). Distinct slots differ in at least k_0 = 2Z
- + 1 digits. At each nonexceptional scale r, the marker
- search range under all shifts bounded by R_r contains at
- most one marker (or one lattice point); this pins D_r to at
- most 3Z+1 possible values. Exceptional scales (at most Z in
- number) contribute at most P^{2Z}. Multiplying over scales
- gives the bound.
-
- Sum the two contributions. QED.
-
-
-PART 8. EPISODES AND EXACT END DETECTION
-
-
-8.1 Second stencil and end-marker rule
-
-The main split cuts an episode at one of many buffer positions. To
-enforce exact ends (so P_x Q_y consumes exactly one episode), we
-need a separate end-marker system. Choose integers d_e, K_e with
-d_e > 10(1 + w + h_1) and K_e > 3d_e^2. Apply the marker lemma with
-these parameters to obtain an end-marker rule of radius r_e >= K_e.
-
-Each episode has an "end-search center" z_e(t) = t + o_e. The end
-marker function eta(t) is the first end marker in the inclusive
-interval [z_e(t) - d_e, z_e(t) + d_e], or "absent" if none.
-
-Predicate A_1(t) is "eta changes somewhere within a shift of size w":
-
- A_1(t): exists u, |u| <= w, with eta(t+u) != eta(t).
-
-
-8.2 End ambiguity lemma
-
- Lemma. On any two-sided word, uniformly in t,
-
- #{(p, p') in P_1^2 : p != p', there exists gamma in Delta_0
- with A_1(t + p - p' + gamma)}
- <= C_1,
-
- where Delta_0 is a fixed finite set of integer offsets and
- C_1 = 2 |Delta_0|.
-
- Sketch. If the first marker in a moving search interval changes
- under a shift of size <= w, a marker crosses an endpoint. Fix
- gamma and an endpoint. As p - p' ranges over the roster of
- ordered differences, the possible marker positions lie in a
- bounded interval of diameter at most 2h_1 + 2w < d_e, which
- contains at most one end marker. That marker pins p - p' to an
- interval of length 2w, so at most one nonzero ordered pair. Two
- endpoints, |Delta_0| choices of gamma: 2 |Delta_0| in total. QED.
-
-
-8.3 The anchor rule
-
-For an episode beginning at s and true origin t = s + L:
-
- - If eta(t) is present (a marker exists): set q = eta(t).
- - Otherwise, the seed [z_e(t), z_e(t) + K_e) has a period < d_e
- by the marker lemma, hence determines a unique two-sided
- periodic extension. Set q = the position of the first mismatch
- (first position where the actual word differs from the
- extension), if any such position exists.
-
-The episode ends at q + b_tail, for a fixed positive integer b_tail.
-Episodes for which eta is absent and no mismatch appears are
-incomplete: they are not episodes.
-
-
-8.4 The episode language E
-
-Let E be the set of nonempty words starting at s such that:
- - all required windows are available (they lie inside the word
- with sufficient margins on each side);
- - the anchor rule gives a well-defined q;
- - the word ends exactly at q + b_tail.
-
-E is a prefix code: no member of E is a proper prefix of another
-member. Proof: every marker and bounded-control decision is
-unaffected by appending letters, because each decision window lies
-strictly inside the current word. So any extension of an episode
-has the same anchor and the same endpoint, and can be a complete
-episode only if it ends at that endpoint. QED.
-
-
-8.5 Placement
-
-The main construction slips finite "windows" around each episode
-to ensure every required datum is available on the correct side of
-any cut.
-
- Lemma. 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 all
- relevant inner-system windows and cuts, then all
- relevant end-system windows and seeds.
- (ii) All bounded windows required at main hypotheses or at
- aligned buffer hypotheses are 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.
- (iv) Every possible true first-episode end is after all cuts
- and bounded control windows.
-
- Sketch. Three finite envelopes chosen in acyclic order:
- 1. Fix buffer offsets from s; put buffer 1 before buffer 0.
- 2. Choose L large enough that the inner envelope (inner
- windows, buffer-related data, all usability shifts) sits
- after all buffer data.
- 3. Choose o_e large enough that the end envelope (end windows,
- seeds) sits after the inner envelope.
- 4. Choose b_tail large enough that the fixed tail sits after
- the end envelope.
- Each step only enlarges a translation. QED.
-
-
-8.6 End guard
-
-A suffix with a finite candidate list {k - h : h in H} forms its
-"end guard" by:
-
- - requiring eta to agree across all candidates,
- - requiring the exact-end test (anchor rule plus endpoint
- q + b_tail) at one fixed reference candidate in the list.
-
- 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
- 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. This conclusion holds even if the
- proposed suffix initially ends before e or extends past e.
-
- Sketch. On the true episode all candidate windows are present.
- A premature suffix would miss a mandatory window; an excessive
- suffix would still attempt to end at q + b_tail. Both excluded
- by the availability requirement. QED.
-
-
-8.7 Why buffers are in reverse order
-
-The construction uses buffer 1 then buffer 0 along the word, even
-though the update-order is g_0 then g_1 then g_2. This reversed
-physical order is what lets the suffix compute the "lift" data that
-the main split needs: the buffer-1 suffix is physically positioned
-to observe the later buffer-0 segment data, so it can build the
-total table Phi_1 that encodes g_1 into g_2's lifted linear part.
-Without this reversal, the second lift could not be built from the
-suffix data alone.
-
-
-PART 9. THE THREE SPLIT CONSTRUCTIONS
-
-
-9.1 The main update g_0
-
-Fix an episode e with start s, true origin t = s + L, anchor q,
-end b = q + b_tail. Set:
-
- T_e = T_{s, b} total monoid value of e
- d_j = T_{B_{j-1}, B_j} interval products, 1 <= j <= l
- d = (d_1, ..., d_l) tuple of interval products
- res = q - t (mod n) anchor-cut residue
- E(res) = {(alpha, lambda) in Lambda^2 : res in I_alpha + J_lambda}
-
-Define the main update g_{0,e} : V -> V by
-
- Diagonal case (E(res) subset of diagonal):
- g_{0,e}(x) = x T_e + beta(d) T_{B_l, b}
-
- Off-diagonal case (E(res) = {(alpha, lambda)}, alpha != lambda):
- g_{0,e}(x) = x T_e + Y(lambda) - X(alpha) T_e
-
-In both cases this is affine on V with linear part x -> x T_e. The
-correction term is built from e's own data, so g_{0,e} is determined
-by e alone, independent of any prefix or suffix choices.
-
-
-9.2 Main prefix and suffix tests
-
- Prefix P_x^main (x in V). Choose a buffer kind (j, v, d_1, ...,
- d_{j-1}) and a residue representative a in I_alpha, and check:
- - x = v at the start (which is s for the prefix).
- - the preceding products d_1, ..., d_{j-1} match their true
- values on the episode prefix.
- - the prefix ends at the buffer position corresponding to j.
- P_x^main has height 0 (finite languages of fixed-length words).
-
- Suffix Q_y^main (y in V). The suffix sees the letters from its
- cut position k to the end of the whole word (which extends past
- the first episode). It does:
- 1. Enumerate candidate origins tau_{p'} = k + L - p' for
- roster items p'.
- 2. Apply the end guard: eta must agree across all candidates;
- require the exact-end test at one reference candidate.
- 3. Enumerate surviving (alpha, lambda) pairs via the clock:
- for each, check residue membership.
- 4. For each surviving (alpha, lambda) pair in E(res), compute the
- corrected vector: if diagonal, add beta(d) T_{B_l, b}; if
- off-diagonal, add Y(lambda) - X(alpha) T_e.
- 5. Apply H_0 and compare to y.
-
- Q_y^main has height at most 1 (single exact-end rule).
-
-
-9.3 Main split proposition
-
- Proposition. The languages P_x^main and Q_y^main satisfy the two
- split hypotheses of Part 4 for the episode update g_0, with
- D = E and D' = {e in E : A_0(t, q) or A_1(t)}.
-
- Sketch.
- Soundness: any accepted concatenation has cut inside the first
- episode, and the end guard forces exact consumption. The clock
- gives either alpha = lambda or one specific off-diagonal pair.
- In the diagonal case, at true origin tau = t, clock properties
- give the exact sandwiching, and line constancy (via the Erdos-
- Lovasz lemma) gives the correct lift to B_l. In the off-diagonal
- case, the constant Y - X exactly compensates the tag mismatch.
-
- Completeness: for e in E \ D', some scale is usable, so the
- transport lemma gives equal later products for all candidates;
- affine-line lemma gives an interval j; clock gives a residue;
- since gcd(delta_r, n) = 1, some a gives k - t in I_alpha, so
- prefix and suffix clock tests both succeed. End guard succeeds
- because A_1(t) is false. The split gives exactly g_0(x) = y.
- QED.
-
-
-9.4 The two exceptional classes D_0, D_1
-
-Define:
-
- D_2 = empty.
- D_1 = {e in D_0 : exists gamma in Delta_0 with A_1(t+gamma)}.
- D_0 = {e in E : A_0(t, q) or A_1(t)}.
-
-Since 0 is in Delta_0, "e in D_0 \ D_1" implies A_0(t, q) and no
-A_1 hits for any gamma in Delta_0.
-
-The construction goes from bottom (D_2, easy) to top (E, hard):
-
- 0 -> 2 (on D_1*): stage-1 aligned split, skip D_2 = empty.
- 2 -> 2 (on D_1*): Boolean recover g_1 from g_2.
- 2 -> 3 (on D_0*): stage-0 aligned split, skip D_1.
- 3 -> 3 (on D_0*): Boolean recover g_0 from g_1.
- 3 -> 4 (on E*): main split, skip D_0.
- 4 -> 4 (on E*): final recovery of the monoid value.
-
-
-9.5 Total tables and lifts
-
-To handle the D_0 class (where A_0 or A_1 fails), we encode g_0 in a
-linear map on a larger space and recover it later. This uses a
-"total prefix table" Phi_i : M -> End(U_i) for each buffer i. The
-table is determined by the suffix's data after a_i and is defined
-for all hypothetical monoid values.
-
-The initial table (i = 0). Let A = T_{a_0, b} and C = T_{B_l, b}.
-For every c in M and v in U_0 = V:
-
- Phi_0(c)(v) =
- v(cA) + beta(d) C (diagonal clock)
- v(cA) + Y(lambda) - X(alpha)(cA) (off-diagonal clock)
-
-Substituting the true c = T_{s, a_0} recovers g_0. The formula only
-uses c hypothetically, so it can be used even when c is not the
-true prefix product.
-
-The lift to U_{i+1}. Define the linear map H_i : U_{i+1} -> U_{i+1}
-on basis vectors by
-
- H_i([v, c]) = [Phi_i(c)(v), 1_M].
-
-The next-level update is
-
- g_{i+1, e}(z) =
- ( z rho_i(T_{s, a_i})
- + beta_i(d_i) rho_i(T_{B_{i, l_i}, a_i}) ) H_i,
-
-where d_i is the tuple of interval products in buffer i. Its linear
-part is L_{i+1, e} = rho_i(T_{s, a_i}) H_i. The crucial identity,
-on distinguished basis vectors [v, 1_M]:
-
- [v, 1_M] L_{i+1, e} = [g_{i, e}(v), 1_M].
-
-So the lift linearly encodes the smaller update on distinguished
-basis. This is the first lift (i = 0, giving g_1 from g_0) and the
-second lift (i = 1, giving g_2 from g_1).
-
-
-9.6 Aligned decoders
-
-For i = 0, 1, we define P_x^{(i)}, Q_y^{(i)} for x, y in U_{i+1}.
-These implement g_{i+1} on D_i with skipped class D_{i+1}.
-
- Prefix P_x^{(i)}: choose offset p in P_i (stencil of buffer's
- checkpoints). If the kind attached to p is (j, v, d_1, ..., d_{j-1}),
- check v = x . rho_i(T_{s, B_{i, 0}}) and d_f = T_{B_{i, f-1}, B_{i, f}}
- for f < j. All these checks precede the cut.
-
- Suffix Q_y^{(i)}: candidate origins tau_{p'} = k + L - p' for p'
- in P_i. Two decoding paths:
- - Stage 0 (i = 0): require A_1(tau_{p'}) false for every
- candidate. Apply end guard to the full candidate list,
- obtaining anchor q. Require a unique p' with A_0(tau_{p'},
- q) true. All A_0 evaluations use this same anchor, so no
- additional unbounded end searches.
- - Stage 1 (i = 1): require a unique p' such that exists
- gamma in Delta_0 with A_1(tau_{p'} + gamma). Bounded
- controls, no q involved. After decoding p', apply the
- exact end rule at tau_{p'} to obtain q and the argument end.
-
- After decoding, set s' = k - p' and use the kind at p'. The
- suffix supplies later products d_f for j < f <= l_i, checks
- the line-constancy condition, then applies H_i and compares to
- y.
-
-
-9.7 Aligned split proposition
-
- Proposition. For i = 0, 1, the languages P_x^{(i)}, Q_y^{(i)}
- satisfy the two split hypotheses of Part 4 for the update
- g_{i+1}, with D = D_i and D' = D_{i+1}.
-
-
-9.8 Recovery chain
-
-The input and output of each split are now established:
-
- g_2 on D_1*: height after stage-1 split = 0 -> 2.
- g_1 on D_1*: Boolean recovery, stays at 2.
- g_1 on D_0*: stage-0 split, 2 -> 3.
- g_0 on D_0*: Boolean recovery, stays at 3.
- g_0 on E*: main split, 3 -> 4.
-
-Finally, the composite g_0 update on E* through the affine recovery
-lemma gives a graph test for the linear part x -> x T_w on E*: for
-the whole word w in E*, T_w is exactly T(w). Applying to e_{1_M}
-in V gives e_{T(w)}, so the surviving basis index distinguishes the
-fiber T^{-1}(m). This final recovery is Boolean.
-
-So the graph language on E* from e_{1_M} to e_m has height at most
-4. This is the top of the ladder. In Part 10 we compile everything
-back to the original alphabet Sigma and close the last gap (words
-that are not complete episode sequences).
-
-
-PART 10. COMPILATION OVER THE ORIGINAL ALPHABET
-
-
-10.1 Periodic templates a b^h c
-
-Every component language S (P_x, Q_y, E, D_0, D_1, the leftover
-class F) has a single "unbounded continuation": the end-marker
-search that keeps going as far as the case keeps repeating letters.
-So the word follows one fixed period b until its first mismatch (or
-until it ends). This makes each component a finite union of
-templates.
-
- Lemma (periodic templates). Take a finite collection of
- templates
-
- a b^h c, h >= 0
-
- with fixed words a, b, c (b != eps). Suppose a test on each
- template uses only:
- (i) letters in fixed finite collections of windows at
- offsets from the argument's start or end;
- (ii) order and availability of endpoints from fixed finite
- sets of offsets;
- (iii) M-products between endpoints whenever available, and
- lengths modulo fixed positive integers;
- (iv) fixed finite combinations, choices, and calculations
- from this data.
-
- Then the accepted words have a generalized expression of height
- <= 1. Adding or removing a finite language preserves this bound.
- Furthermore, every exact-end test whose reference or decoded
- origin is chosen from finitely many offsets relative to the test
- start is covered by a finite language and finitely many such
- templates.
-
- Sketch. Fix a template. For large h, availability conditions
- stabilize; the growing middle contains complete copies of b.
- Any partial product has form u T(b)^{h-j} v for fixed u, v, j.
- Because M is finite, powers of T(b) are ultimately periodic (if
- two powers coincide, multiplying further gives a period). So
- every product, every length-mod-n condition, and every finite
- combination is ultimately periodic in h. Accepted exponents
- become a finite set plus progressions { h_0 + f*k : k >= 0 }.
- Each progression gives a b^{h_0} (b^f)^* c of height 1; finite
- exceptions have height 0. Union over the finitely many templates:
- height 1.
-
- For the "Furthermore", fix an end-rule origin. Present-marker
- case has bounded length (finite language). Absent-marker case:
- finite choices of letters through the seed, sample short period
- and phase, and fixed-length tail at the first mismatch give
- a = prefix through seed, b = period word, c = post-mismatch
- tail. Finitely many choices. QED.
-
-
-10.2 Component bounds
-
- Proposition. The episode languages E, D_0, D_1 and every suffix
- component Q_y have height at most one. Every prefix component
- P_x has height zero. All bounds hold over the original alphabet
- Sigma.
-
- Sketch. Prefix P_x comes from fixed finite offset sets, so it is
- finite (height 0).
-
- Episode and suffix languages each have one exact-end rule on
- their entire argument. For E, D_0, D_1 it is the true episode
- rule; for Q_y at the main or stage-0 split it is the reference
- rule inside the end guard; for Q_y at stage 1 it is the decoded
- rule. Finitely many reference or decoded offsets. Apply the
- template lemma.
-
- All remaining operations - marker searches, usability, phase and
- lattice choices, additional candidate translates, boundary
- placement near centers, buffer boundary offsets, line-constancy,
- total table Phi_i computations, terminal map H_i - inspect
- bounded windows at fixed nominal offsets or are finite
- combinations of actual partial products. All partial products
- have endpoints in a finite set of start offsets, except for the
- argument end itself, which the anchor rule pins to end - b_tail.
- So all data are ultimately periodic in the template length. QED.
-
-
-10.3 The remainder
-
-Not every word is a complete sequence of episodes: some words stop
-before finishing an episode. Define
-
- F = ~(E Sigma*), Sigma* = ~0.
-
-So F consists of words that cannot start with a complete episode.
-
- Lemma. For every d in M, F intersect T^{-1}(d) has height at
- most one.
-
- Sketch. Choose a threshold length exceeding all bounded windows
- at a first start and all possible first-episode lengths in the
- present-marker case. A longer word in F cannot have a present
- end marker: that would already make a complete episode prefix.
- Its marker-absent seed has a fixed period; either no mismatch
- has appeared, or its first mismatch is within b_tail of the end
- (if it were farther, the prefix ending at q + b_tail would be a
- complete episode). Finite choices of the bounded initial word,
- the period, the phase, and the final partial period give
- templates a b^h c. On every template T(u) = d is ultimately
- periodic in h, so the template lemma gives a height-one
- language with that value on the template cover. Intersecting
- with F keeps the same bound. Words below the threshold form a
- finite language. QED.
-
- Lemma (unique parsing). Every word admits a unique factorization
- into a sequence of episodes followed by a word in F.
-
- Proof. Repeatedly remove an episode prefix while one exists.
- Every episode is nonempty, so this terminates. The remaining
- word is in F. The prefix-code property makes each removed
- prefix unique. Any alternative E*F factorization must remove the
- same successive episodes; it also cannot stop earlier while an
- episode prefix remains. QED.
-
-
-PART 11. PROOF OF THE MAIN THEOREM
-
-
-11.1 Assembling the expression
-
-Fix m, d, f in M with d f = m. Set:
-
- G_d = graph language on E* from e_{1_M} to e_d (height <= 4)
- F_f = F intersect T^{-1}(f) (height <= 1)
-
-The unique-parsing lemma says every word w in T^{-1}(m) is in
-exactly one such product G_d F_f (with d = T(episodes), f =
-T(remainder)), and conversely every word in such a product lies in
-T^{-1}(m) because T(w) = d f = m. So
-
- T^{-1}(m) =
- union over (d, f) in M^2 with d f = m of G_d F_f.
-
-Each factor has height at most 4 (resp. 1); their concatenation has
-height at most max(4, 1) = 4; the finite union over M^2 also has
-height at most 4. All operations are over the original alphabet
-Sigma.
-
-
-11.2 The main theorem
-
- Theorem. For every finite alphabet Sigma and every regular
- language L contained in Sigma*, one has h(L) <= 4.
-
- Proof. Follow the reduction (Section 2.1) from L to a morphism
- T : Sigma* -> M and a finite union of fibers T^{-1}(m). For
- each fiber our construction gives an expression of height at
- most 4 over Sigma. Finite unions do not increase height. QED.
-
-
-11.3 What is not proved
-
- - The construction gives no bound on the length of expressions
- or on the running time to find them. It is constructive in
- principle but not in complexity.
-
- - The construction does not exhibit any specific regular
- language that requires generalized star height > 1. It is
- compatible with the conjecture that height 1 always suffices.
-
- - The bound 4 is not claimed optimal. The companion paper
- (Height3) improves it to 3; whether 1 suffices is open.
-
-
-PART 12. WHAT WE GAINED AND THE GLOSSARY
-
-
-12.1 The bound 4
-
-Every regular language has generalized star height at most 4.
-Companion papers improve this to 3; whether 1 suffices is a
-still-open problem.
-
-The present paper's proof uses three conceptually distinct tools,
-each contributing something real.
-
- - Splits. A star-producing operation: converts a graph test
- on a smaller episode class into one on a larger class. Each
- split adds one to the height.
-
- - Affine corrections. A probabilistic construction
- (Erdos-Lovasz local lemma) that lets a single correction
- function hide one interval product from any cut, for every
- tuple of inputs simultaneously and every choice of tuple.
-
- - Finite clock and multiple scales. A bounded-disjunction
- system that converts unbounded tag ambiguity into bounded
- tag uncertainty, and a set of scales that keeps interval
- products stable under small origin shifts.
-
-These three tools are independent of the companion "Generalized
-star height at most three" paper's method. They also do not rely on
-that paper's stronger numerical bound. Together they show directly
-that the generalized star height is finite-term bounded for every
-regular language, with no dependence on Sigma's size, the language
-L, or the number of automaton states.
-
-
-12.2 What is still open
-
- - Does every regular language have generalized star height at
- most one? Known partial results: aperiodic monoids
- (Schutzenberger), finite commutative groups (Henneman),
- nilpotent groups of class two (Pin-Straubing-Therien).
-
- - Can the methods here be sharpened to give an explicit lower
- bound, if some language actually requires height > 1? No such
- language is currently known.
-
- - Is there a bound on expression length or on how large the
- finite choices must be? The present paper gives none.
-
-
-12.3 Glossary
-
- Sigma finite alphabet
- Sigma* all finite words over Sigma, including eps
- L a regular language, subset of Sigma*
- P + Q, PQ union, concatenation of languages
- ~P complement of P in Sigma*
- P* Kleene star
- ht(E) star height: maximum nesting depth of * in E
- h(L) generalized star height: min ht(E) over
- expressions E for L
- M finite monoid, image of transition morphism
- T morphism Sigma* -> M
- T^{-1}(m) fiber of T at m
- V = F_2^M vector space over F_2 with basis indexed by M
- T_{a,b} monoid product of letters at positions
- a through b-1
- prefix code E subset of Sigma+ with no element a proper
- prefix of another
- E* concatenations of episodes; unique
- factorization (prefix-code property)
- graph language from x to y on D*: words whose composite
- update sends x to y (domain D* required)
- split lemma converts a graph test on D'* to one on D*,
- using prefix P_x and suffix Q_y. +1 height.
- affine-line lemma existence of correction beta hiding one
- interval product of any tuple of M-values,
- uniformly in the input state and tuple
- affine recovery from graph languages of an affine composite,
- extract graph language of the product of
- linear parts, via finite Boolean operations
- clock modulus n and sets I_alpha, J_alpha, plus
- bad set W. Bounded disjunction of "how tags
- agree at a residue."
- marker well-spaced integer positions deciding
- whether a long block is periodic
- U_0, U_1, U_2 nested vector spaces for the two lifts
- g_0, g_1, g_2 episode updates at three levels
- D_0, D_1, D_2 exceptional classes; at each stage the
- "skip" class is fixed
- a b^h c template with ultimate period b and
- finite a, c
-
-End of glossary.
-
-The bound 4 is what this paper establishes. The proof is a single
-coherent construction that reduces every regular fiber to a finite
-union of episode-sequence components and a remainder, and it
-isolates the three techniques (splits, affine corrections, finite
-clock plus scales) that make the problem tractable.
-
-The height-one problem remains open.
+Proof. Fix a gamma in Delta_0 and an 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
+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
+
+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.
+
+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
+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
+
+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
+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:
+
+ 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,
+
+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].
+
+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.
+
+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
+[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
+
+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