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

  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

  x_r(p) = p(xi_r).

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.

./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.

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.

  (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.

  (iii) Choose S'_r > max(S_r, 10 (h'_r + J_r + R_r + 1)).

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.

Assign slot p the numerical offset

  sum_{r=1}^{R_s} f_r(x_r(p)) + eps_p,   0 <= eps_p < n.

Choose eps_p so that the offset is congruent to v_p modulo n. For two
slots whose highest differing digit is at scale r, the sum of all
smaller-coordinate differences plus the correction difference has
absolute value less than J_r, while the difference at scale r has
absolute value greater than 10 (J_r + R_r + 1). The resulting
positions are distinct, and any two are separated by more than 2.

These positions, up to a common translation, form the stencil P_0.
Their difference residues are exactly the prescribed v_p - v_p',
including after the common translation. By the inequality
floor(P^{k_0} / kappa_0) > C_0, more than C_0 offsets can be assigned
to each stage-0 kind. Assign them in increasing interval-number
order and insert buffer boundaries in the intervening gaps.
Translation of the whole configuration later does not affect any
difference property. In particular,

  h_0 < n + sum_r h'_r.

Inner controls. The inner boundary rule needs marker parameters far
exceeding every scale and every monoid period. Choose integers

  d_o > 10 (1 + n + sum_r h'_r + sum_r R_r),
  K_o > 3 d_o^2,

and fix the marking rule of the local-markers lemma with these
parameters and radius r_o >= K_o. Choose an integer

  H > 10 ((N + m + 1) d_o + (max_r R_r) + 1).

For an inner center z, let u(z) be the first marker in [z - H, z + H],
or bottom when none exists. When u(z) is not bottom, put B(z) = u(z).

When u(z) is bottom, the periodic-extension lemma supplies a
periodic extension of the block starting at z. Let d < d_o be its
least period and sigma the largest smooth divisor of d. Among the
length-d period words starting at the different phases of the
extension, choose the lexicographically least, using a fixed order on
Sigma. Their starts form a single class x modulo d, since equality of
two rotations would contradict minimality of d. Let y(z) be the
largest integer at most z in x + sigma Z, and let B(z) be the least
integer at least z satisfying

  B(z) = x       (mod d),
  B(z) = y(z)    (mod sigma N).

The definition does not depend on the representative of x. Moreover,

  gcd(d, sigma N) = sigma,
  lcm(d, sigma N) = d N,

because d / sigma is coprime to N by choice of sigma. The two
residues in the boundary rule agree modulo sigma, so together they
define one class modulo d N. In particular,

  z <= B(z) < z + d N.

All these choices commute with translations of the letters and do
not use an external choice of position origin. In both the present
and absent cases, B(z) lies in [z - H, z + H].

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).

For a fixed endpoint b >= z_l + H, the last transfer gives

  T[B_l, b] = T[B_l^{(h)}, b].

These statements apply to finite words whenever the prescribed
windows and product intervals are available. They hold for arbitrary
finite monoids, without a commutativity assumption.

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.

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,

  B(z + h) - B(z) = q d N  with |q| d N <= 2 H + R_r.

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.

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

  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)}].

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

Proposition (inner ambiguity). For every stage-0 tag alpha and every
u in Z/n,

  #{(p, p') in R_0^2 : p != p', u + v_{p'} - v_p in W and
     some gamma in Delta_0 has A_1(t + p - p' + gamma)} <= C_0,

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.

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)),

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.

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

  (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.

  (B) Choose L large enough that the inner envelope, containing the
  inner windows of the buffer cuts, sits after all buffer data.

  (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.

  (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.

Lemma (placement). The translations of the two buffers and the
integers L, o_e, b_tail can be chosen so that:

  (i) After s, the buffers occur in order 1, 0, then every relevant
  inner-system window and cut, then every relevant end-system window
  and seed.

  (ii) Every bounded window required at main hypotheses or at
  aligned buffer hypotheses is internal to every complete episode
  at a true cut.

  (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.

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.

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|.

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