MatAnn Manuskript-Nr. (will be inserted by hand later)

Springer-Verlag

Mathematische Annalen Heidelberg, 1.1.1991

\begin{matrix}c \\ ◯ \end{matrix} Springer-Verlag

A finiteness property and an automatic structure for Coxeter groups

Brigitte Brink^{1} and Robert B. Howlett^{1}

1 School of Mathematics and Statistics, University of Sydney, NSW 2006, Australia

[the date of receipt and acceptance should be inserted later]

Summary. If α and β are positive roots in the root system of a Coxeter group W, we say that α dominates β if w · β is negative for every w ∈ W such that w · α is negative. It is shown that if the distinguished generating set of W is finite, then the set of all positive roots α for which there is no β dominated by α is finite. It follows as a consequence that the group W is automatic.

Keywords. Coxeter group – Automatic group

1. Root systems of Coxeter groups

Let (W, R) be a Coxeter system, as defined in [6], and for all r, s ∈ R let m_{rs} be the order of rs in W. Let Π = { α_{r} | r ∈ R } denote the set of simple roots and V the R-vector space with basis Π. Let ⟨ , ⟩: V × V → R be a symmetric bilinear form which satisfies ⟨α_{r}, α_{s}⟩ = − cos(π/m_{rs}) for all r, s ∈ R such that m_{rs} is finite, and ⟨α_{r}, α_{s}⟩ ≤ −1 if m_{rs} is infinite; then r · v = v − 2⟨v, α_{r}⟩α_{r} (for all r ∈ R and v ∈ V) determines a faithful action of W on V which preserves ⟨ , ⟩. We refer to such representations as standard geometric realizations of W.

The set Φ = {w · α_{r} | w ∈ W, r ∈ R} is called the root system of W in V. The subsets Φ^{+} = { ∑_{r∈R} λ_{r}α_{r} ∈ Φ | λ_{r} ≥ 0 for all r ∈ R } and Φ^{−} = { α ∈ V | −α ∈ Φ^{+} } are the sets of positive roots and negative roots respectively. Define the support of α = ∑_{r∈R} λ_{r}α_{r} ∈ Φ to be the set supp_{R}(α) = { r ∈ R | λ_{r} ≠ 0 }. For w ∈ W define the length of w to be l(w) = min{ l ∈ ℕ | w = r_{1} ⋯ r_{l} for some r_{1}, …, r_{l} ∈ R } (where ℕ is the set of nonnegative integers), and let N(w) = { α ∈ Φ^{+} | w · α ∈ Φ^{−} }.

We start with a proposition which lists an assortment of well known facts (see [6], for example).

Proposition 1.1 (i) Φ = Φ^{+} ∪ Φ^{−}. (ii) |N(w)| = l(w) for all w ∈ W. (iii) Let r_{1}, …, r_{n}, s ∈ R with l(r_{1} ⋯ r_{n}s) < l(r_{1} ⋯ r_{n}). Then there exists i ∈ {1, …, n} such that r_{1} ⋯ r_{n}s = r_{1} ⋯ r_{i−1}r_{i+1} ⋯ r_{n}. (iv) For all w ∈ W and r ∈ R,

l(wr) = \{ \begin{matrix}l(w) + 1 & if w · α_{r} ∈ Φ^{+}, \\ l(w) − 1 & if w · α_{r} ∈ Φ^{−}. \end{matrix}

(v) For all α ∈ Φ there is a uniquely defined element r_{α} ∈ W such that r_{α} = wrw^{−1} for all w ∈ W, r ∈ R with α = w·α_{r}. Moreover, r_{α}·v = v−2⟨α, v⟩α for all v ∈ V. (vi) Let α, β ∈ Φ^{+} with ⟨α, β⟩ ≤ −1, and let (r_{α}r_{β})^{n} · α = λ_{n}α + μ_{n}β for each n ∈ ℕ. Then λ_{n} ≥ μ_{n} + 1 and μ_{n+1} ≥ λ_{n} + 1 (for all n ∈ ℕ).

The following lemma is a straightforward consequence of Proposition 1.1 (ii).

Lemma 1.2 Let v, w ∈ W. Then l(vw^{−1}) = l(v) + l(w) if and only if N(v) ∩ N(w) = ∅.

The elements r_{α} defined in Proposition 1.1 (v) are called the reflections in W, and the elements of R = { r_{α} | α ∈ Π } are called simple reflections.

For each set J of simple reflections, the subgroup W_{J} generated by J is called a parabolic subgroup of W. Each W_{J} is itself a Coxeter group, as can be seen from its action on the subspace of V spanned by { α_{r} | r ∈ J }. The following result appears as an exercise in [1], but we include a proof for completeness’ sake.

Proposition 1.3 If H is a finite subgroup of W then there exists w ∈ W and J ⊆ R such that W_{J} is finite and wHw^{−1} ⊆ W_{J}.

Proof Let V^{∗} be the dual space of V and { δ_{α} | α ∈ Π } the basis of V^{∗} dual to the basis Π of V, so that for all α, β ∈ Π,

δ_{α}(β) = \{ \begin{matrix}1 & if α = β \\ 0 & if α ≠ β. \end{matrix}

For each f ∈ V^{∗} define

s(f) = { v ∈ Φ^{+} | f(v) < 0 },

and let C be the set of all f ∈ V^{∗} for which s(f) = ∅; equivalently,

C = { f ∈ V^{∗} | f(α) ≥ 0 for all α ∈ Π }.

For each w ∈ W and f ∈ V^{∗}, define fw: V → ℝ by v ↦ f(w · v); this gives a right action of W on V^{∗}.

Claim Let f ∈ V^{∗} with |s(f)| < ∞. Then fw ∈ C for some w ∈ W.

Proof Choose w ∈ W with |s(fw)| minimal, and let f′ = fw. Assume, for a contradiction, that s(f′) ≠ ∅, and let α ∈ s(f′); that is, α ∈ Π and f′(α) < 0. Now

(f′r_{α})(α) = f′(r_{α} · α) = f′(−α) = −f′(α) > 0,

and so α ∉ s(f′r_{α}). It follows that r_{α}·γ ∈ Φ^{+} for all γ ∈ s(f′r_{α}), and furthermore r_{α} · γ ∈ s(f′) since f′(r_{α} · γ) = (f′r_{α})(γ) < 0. Therefore v ↦ r_{α} · v is a one to one map from s(f′r_{α}) to s(f′), and as α is not in the image of this map we deduce that |s(f′r_{α})| < |s(f′)|, contradicting the minimality of |s(fw)|.

Claim Let f ∈ C and define J = { α ∈ Π | f(α) = 0 }. Then W_{J} is the stabilizer of f in W.

Proof Let S = { w ∈ W | fw = f }, the stabilizer of f. If α ∈ J then, for all v ∈ V,

(fr_{α})(v) = f(r_{α} · v) = f(v − 2⟨vα⟩α) = f(v) − 2⟨v, α⟩f(α) = f(v),

and so fr_{α} = f. Thus W_{J} ⊆ S. To prove the reverse inclusion, we use induction on l(w) to show that if w ∈ W with fw = f then w ∈ W_{J}.

The case l(w) = 0 is trivial. If w ≠ 1, let w′ ∈ W and α ∈ Π such that w = w′r_{α} and l(w′) = l(w) − 1. Then

0 ≤ f(α) = (fw)(α) = f(w · α) = f(w′r_{α} · α) = f(w′ · (−α)) = −f(w′ · α) ≤ 0

as w′ · α ∈ Φ^{+} and f ∈ C. Thus f(α) = 0; that is, α ∈ J. Now by the first part of the proof we have r_{α} ∈ S, and so

fw′ = (fw)r_{α} = fr_{α} = f.

Hence w′ ∈ W_{J} by induction, and it follows that w = w′r_{α} ∈ W_{J}.

We now use induction on |Π| to establish Proposition (2.3). If |W | < ∞ then there is nothing to prove; so suppose, without loss of generality, that W is infinite. Let f = Σ_{α∈Π}δ_{α}, so that f(α) = 1 for all α ∈ Π and thus f(v) > 0 for all v ∈ Φ^{+}, and define f′ = Σ_{h∈H}fh. Define also A = ⋃_{h∈H} N(h), observing that A is finite, since H is finite and N(h) is finite for all h ∈ H.

Let v ∈ Φ^{+} − A. Then h · v ∈ Φ^{+} for all h ∈ H and so

f′(v) = Σ_{h∈H}(fh)(v) = Σ_{h∈H}f(h · v) > 0.

Hence s(f′) ∩ (Φ^{+} − A) = ∅; that is s(f′) ⊆ A. In particular, s(f′) is finite. By the first lemma there exists w ∈ W such that f′ = f′′w for some f′′ ∈ C. Then for all h ∈ H,

f′′whw^{−1} = (f′′w)hw^{−1} = fhw^{−1} = (fh)w^{−1} = fw^{−1} = f′′,

since clearly fh = f for all h ∈ H. Thus, by the second lemma, wHw^{−1} ⊆ W_{J}, where J = {α ∈ Π | f′′(α) = 0}. Now Φ^{+} is infinite as W is infinite; so Φ^{+} − A ≠ ∅, and it follows in particular that f′ ≠ 0, since f(v) > 0 whenever v ∈ Φ^{+} − A. Hence f′′ ≠ 0 also, and thus J ≠ Π. Now by induction there exists I ⊆ J and u ∈ W such that W_{I} is finite and u(wHw^{−1})u^{−1} ⊆ W_{I}.

The authors are indebted to Prof. M. J. Dyer for drawing their attention to the above result and its application to Proposition 2.9 below, which replaces their original much longer argument.

Proposition 1.4 (Dyer [4]) If α, β ∈ Φ and |⟨α, β⟩| < 1, then ⟨α, β⟩ = cos(pπ/q) for some integers p and q, and the subgroup of W generated by r_{α} and r_{β} is a finite dihedral group.

Proof Since ⟨α, α⟩ = ⟨β, β⟩ = 1 the condition |⟨α, β⟩| < 1 implies, by an easy calculation, that the restriction of the form ⟨ , ⟩ to the subspace V_{0} spanned by α and β is positive definite.

Replacing α and β by w · α and w · β for a suitable w ∈ W we may assume that β = α_{s} for some s ∈ R, and replacing α by −α if need be, we may assume that α ∈ Φ^{+}. Let ν be the coefficient of α_{s} in α, and let v = α − να_{s}. Then certainly v ≠ 0, since α_{s} is the only positive root with support {s}, and α ≠ α_{s}. If λv + μα_{s} ∈ Φ, then by Proposition 1.1 (i) it follows that λ and μ are either both nonnegative or both nonpositive. But if cos^{−1}(⟨α, α_{s}⟩) is not a rational multiple of π then there exist powers of r_{α}s which act on the Euclidean plane V_{0} as rotations through arbitrarily small angles. Thus some power of r_{α}s will rotate α into the (skew) quadrant { λv + μα_{s} | λ > 0 and μ < 0 }, contradicting the fact that this set contains no roots. So cos^{−1}(⟨α, α_{s}⟩) is a rational multiple of π, as required. Furthermore, the subgroup D generated by r_{α} and s acts on V_{0} as a finite dihedral group. But since V_{0} is Euclidean we see that V is the orthogonal direct sum of V_{0} and V_{0}^{⊥}, and since D acts trivially on V_{0}^{⊥} it follows that the representation of D on V_{0} is faithful, so that D is finite dihedral.

Definition 1.5 (i) For each α ∈ Φ^{+} define the depth of α (relative to R) to be dp(α) = min{ l ∈ ℕ | w · α ∈ Φ^{−} for some w ∈ W with l(w) = l }.

(ii) For α, β ∈ Φ^{+} define α ⪯ β if and only if the following condition holds: there exists w ∈ W such that β = w · α and dp(β) − dp(α) = l(w). We write α ≺ β if α ⪯ β and α ≠ β.

Lemma 1.6 ⪯ is a partial order on Φ^{+}.

Proof Suppose that α, β ∈ Φ^{+} with α ⪯ β and α ≠ β. Then there exists w ∈ W with w ≠ 1 such that β = w · α and dp(β) − dp(α) = l(w) ≥ 1. Thus dp(β) > dp(α), and so ⪯ must be antisymmetric. It remains to show that ⪯ is transitive.

Let α, β, γ ∈ Φ^{+} with α ⪯ β and β ⪯ γ. Then there exist v, w ∈ W such that β = w · α and γ = v · β, where dp(β) − dp(α) = l(w) and dp(γ) − dp(β) = l(v). Then γ = vw · α and

dp(γ) − dp(α) = dp(γ) − dp(β) + dp(β) − dp(α) = l(v) + l(w),

and so it suffices to prove l(vw) = l(v)+l(w). Let u ∈ W such that l(u) = dp(α) and u·α ∈ Φ^{−}. Then (uw^{−1}v^{−1})·γ = u·α ∈ Φ^{−}, and hence l(uw^{−1}v^{−1}) ≥ dp(γ). Furthermore,

l(uw^{−1}v^{−1}) ≤ l(u) + l(w) + l(v)
= dp(α) + dp(β) − dp(α) + dp(γ) − dp(β)
= dp(γ).

Hence l(uw^{−1}v^{−1}) = l(u) + l(w) + l(v), and so l(vw) = l(v) + l(w).

Lemma 1.7 Let r ∈ R and α ∈ Φ^{+} − {α_{r}}. Then

dp(r · α) = \{ \begin{matrix}dp(α) − 1 & if ⟨α, α_{r}⟩ > 0, \\ dp(α) & if ⟨α, α_{r}⟩ = 0, \\ dp(α) + 1 & if ⟨α, α_{r}⟩ < 0. \end{matrix}

Proof If ⟨α, α_{r}⟩ = 0 then r · α = α − 2⟨α, α_{r}⟩α_{r} = α; hence trivially dp(r · α) = dp(α).

Suppose next that ⟨α, α_{r}⟩ > 0. It suffices to show dp(r · α) < dp(α) since it is trivial that dp(α) ≤ dp(r · α) + 1. To do so we construct a w ∈ W with w · (r · α) ∈ Φ^{−} and l(w) < dp(α). Choose v ∈ V such that v · α ∈ Φ^{−} and l(v) = dp(α). If v · α_{r} ∈ Φ^{−} we choose w = vr; then l(w) = l(v) − 1 by Proposition 1.1 (iv), and w · (r · α) = v · α ∈ Φ^{−}, as required. Hence we may assume that v · α_{r} ∈ Φ^{+}. Now

v · (r · α) = v · (α − 2⟨α, α_{r}⟩α_{r}) = v · α − 2⟨α, α_{r}⟩v · α_{r}

is negative and has at least two simple roots in its support, since v · α and −2⟨α, α_{r}⟩v · α_{r} are both negative linear combinations of simple roots (and not scalar multiples of each other). Now there exist s ∈ R, w ∈ W with v = sw and l(v) = l(w) + 1, and it follows that w · (r · α) = s · (v · (r · α)) ∈ Φ^{−} by the above, as s is a simple reflection and the negative root v · (r · α) cannot equal −α_{s}.

Finally, suppose that ⟨α, α_{r}⟩ < 0. Then ⟨r · α, α_{r}⟩ = −⟨α, α_{r}⟩ > 0; so the preceding paragraph shows that dp(α) = dp(r · (r · α)) = dp(r · α) − 1.

Corollary 1.8 Let α, β ∈ Φ^{+} with α ⪯ β. Let α = ∑_{r∈R} λ_{r}α_{r} and β = ∑_{r∈R} μ_{r}α_{r}. Then λ_{r} ≤ μ_{r} for all r ∈ R.

Proof If β = s · α ≻ α then μ_{r} = λ_{r} for all r ≠ s, and μ_{s} > λ_{s} by Lemma 1.7. A straightforward induction on depth completes the proof.

2. A partial order on the positive roots

Definition 2.1 For α, β ∈ Φ^{+} we say that α dominates β with respect to W (we write α dom_{W} β) if and only if for all w ∈ W, if α ∈ N(w) then β ∈ N(w). Define also Δ_{W} = { α ∈ Φ^{+} | ∃β ∈ Φ^{+} − {α}, α dom_{W} β }.

Our principal result is that if |R| < ∞ then |Φ^{+} −Δ_{W} | < ∞. It can be shown that this is equivalent to the Parallel Wall Theorem of the preprint [3], in which the proof given is incomplete.

The next lemma gives some basic properties of dominance.

Lemma 2.2 Let α, β ∈ Φ^{+} with α dom_{W} β. Then

(i) ⟨α, β⟩ > 0; (ii) (w · α) dom_{W} (w · β) for all w ∈ W with w · β ∈ Φ^{+}; (iii) if α′ ∈ Φ^{+} with α′ ≻ α, then α′ ∈ Δ_{W}; (iv) dp(α) ≥ dp(β), with equality if and only if α = β.

Proof Since r_{α} · α = −α ∈ Φ^{−} it follows that r_{α} · β ∈ Φ^{−}; that is, β − 2⟨α, β⟩α ∈ Φ^{−}. Hence ⟨α, β⟩ > 0, and (i) is proved. Part (ii) is trivial.

For (iii) it is clearly sufficient to consider the case dp(α′) = dp(α) + 1. Then α′ = r · α for some r ∈ ℝ, and ⟨α, α_{r}⟩ < 0, by Lemma 1.7. Hence β ≠ α_{r} (by (i)); thus r · β ∈ Φ^{+}, and (ii) finishes the proof.

It is clear that dp(α) ≥ dp(β). Let w ∈ W, r ∈ R such that w · α = −α_{r} and l(w) = dp(α). Then l(rw) = l(w)−1 by Proposition 1.1 (iv), and also w ·β ∈ Φ^{−} as α dom_{W} β. If (rw) · β ∈ Φ^{+}, then (rw) · β = α_{r} (since r · (rw · β) ∈ Φ^{−}), and this gives β = α. If (rw) · β ∈ Φ^{−} then dp(β) ≤ l(rw) < dp(α).

It is clear that dom_{W} is transitive, and Lemma 2.2 (iv) shows that dom_{W} is antisymmetric; hence dom_{W} is partial order on Φ^{+}. The set Φ^{+} − Δ_{W} consists of the minimal elements in this partial order. Note furthermore that if W is finite and w_{0} is the element of maximal length in W, then α ↦ −w_{0}(α) is a depth preserving and dominance reversing permutation of the positive roots. Thus Lemma 2.2 (iv) shows that there is no nontrivial dominance in a finite Coxeter group.

The following lemma provides us with an alternative characterization of dominance.

Lemma 2.3 Let α, β ∈ Φ^{+} be arbitrary. Then α dom_{W} β if and only if ⟨α, β⟩ ≥ 1 and dp(α) ≥ dp(β).

Proof We may assume that α ≠ β, since both implications are trivial otherwise.

Suppose first that α dom_{W} β. By Lemma 2.2 (iv) we need only show that ⟨α, β⟩ ≥ 1. If ⟨α, β⟩ < 1 then by Lemma 2.2 (i) and Proposition 1.4 it follows that ⟨α, β⟩ = cos(pπ/q) for some integers p and q, and the subgroup D generated by r_{α} and r_{β} is a finite dihedral group. Since there is no dominance in D there exists w ∈ D with w · α ∈ Φ^{−} and w · β ∈ Φ^{+}. Since D ⊆ W, this contradicts our hypothesis that α dom_{W} β. So ⟨α, α_{r}⟩ ≥ 1, as required.

For the converse, assume that ⟨α, β⟩ ≥ 1 and dp(α) ≥ dp(β), and consider first the case β ∈ Π; say β = α_{r}. Then r · α ∈ Φ^{+}, since α ≠ β. Furthermore,

⟨α, r · α⟩ = ⟨α, α⟩ − 2⟨α, α_{r}⟩^{2} = 1 − 2⟨α, α_{r}⟩^{2} ≤ −1,

and by Proposition 1.1 (vi) there are infinitely many roots of the form λα+μr·α with λ, μ > 0. Suppose that α does not dominate β, and choose w ∈ W such that w · α ∈ Φ^{−} and w · α_{r} ∈ Φ^{+}. Then

w · (r · α) = w · α + 2⟨α, α_{r}⟩(−w · α_{r})

is a positive linear combination of negative roots, and must therefore be negative. So N(w) contains α and r · α, and hence also contains all roots of the form λα + μr · α with λ, μ > 0. This contradicts the finiteness of N(w) (see Proposition 1.1 (ii)).

Proceeding by induction on dp(β), suppose now that dp(β) > 1, and choose r ∈ R such that β ≻ r · β ∈ Φ^{+}. Since dp(α) ≥ dp(β) > 1, clearly r · α ∈ Φ^{+}. Now ⟨r · α, r · β⟩ ≥ 1 and

dp(r · α) ≥ dp(α) − 1 ≥ dp(β) − 1 = dp(r · β).

Hence by induction (r · α) dom_{W} (r · β), and by Lemma 2.2 (ii) this implies that α dom_{W} β.

Corollary 2.4 Let α, β ∈ Φ^{+} with β ⪯ α and α ∉ Δ_{W}; let furthermore r ∈ R such that ⟨β, α_{r}⟩ ≤ −1. Then the coefficient of α_{r} in α equals the coefficient of α_{r} in β.

Proof Let γ ∈ Φ^{+} such that β ⪯ γ ⪯ α and γ is maximal (with respect to ⪯) subject to having the same coefficient of α_{r} as β has. If γ ≠ α then γ ≺ s · γ ⪯ α for some s ∈ R, and by maximality of γ we must have s = r. But γ − β = ∑_{t∈R−{r}} λ_{t}α_{t} for some λ_{t} ≥ 0, and hence

⟨r · γ, α_{r}⟩ = −⟨γ, α_{r}⟩ = −⟨β, α_{r}⟩ − ∑_{t∈R−{r}} λ_{t}⟨α_{t}, α_{r}⟩ ≥ 1.

Hence r · γ dom_{W} α_{r}, and by Lemma 2.2 (iii) it follows that α ∈ Δ_{W}, which is the desired contradiction.

Our proof that Φ^{+} − Δ_{W} is finite (if R is finite) depends on the fact that the set of real numbers { ⟨α, α_{r}⟩ | α ∈ Φ^{+} − Δ_{W} and r ∈ R } is finite. The next definition facilitates the statement of the relevant facts.

Definition 2.5 For J ⊆ R define C(J) to be the set of all real numbers of the form cos(aπ/m) with a ∈ ℕ and m = m_{rs} for some r, s ∈ J.

Proposition 2.6 Let α, β ∈ Φ, and suppose that ⟨α, β⟩ ∈ [−1, 1]. Then ⟨α, β⟩ ∈ C(R).

Proof If ⟨α, β⟩ = ±1 then the result is trivial since m_{rr} = 1 for all r. If ⟨α, β⟩ ∈ (−1, 1) then by Proposition 1.4 it follows that the subgroup of W generated by r_{α} and r_{β} is finite, whence, by Proposition 1.3, there exists w ∈ W such that w · α and w · β are in the root system of some finite parabolic subgroup W_{J} of W. It follows by well known properties of finite Coxeter groups that ⟨w ·α, w ·β⟩ ∈ C(J); indeed, by a similar argument to that used in the proof of Proposition 1.3, there exist t ∈ W_{J} and r, s ∈ J such that (tw) · α and (tw) · β are in the root system of the parabolic subgroup generated by r and s, whence the angle between them is an integral multiple of π/m_{rs}.

The following technical lemma, though trivial, provides the key for our proof of the main theorem.

Lemma 2.7 Let α = ∑_{r∈R} λ_{r}α_{r} and β = ∑_{r∈R} μ_{r}α_{r} be positive roots. Let further R = R_{1} ∪ R_{2} such that

(i) ⟨α, α_{r}⟩ = ⟨β, α_{r}⟩ for all r ∈ R_{1}, (ii) λ_{r} = μ_{r} for all r ∈ R_{2}.

Then ⟨α, β⟩ = 1.

Proof We have that α − β = ∑_{r∈R_{1}}(λ_{r} − μ_{r})α_{r}. Thus

⟨α, α − β⟩ = ∑_{r∈R_{1}}(λ_{r} − μ_{r})⟨α, α_{r}⟩ = ∑_{r∈R_{1}}(λ_{r} − μ_{r})⟨β, α_{r}⟩ = ⟨β, α − β⟩.

Since ⟨α, α⟩ = ⟨β, β⟩ = 1, this becomes 1 − ⟨α, β⟩ = ⟨α, β⟩ − 1, and the result follows.

Theorem 2.8 If R is finite, then so is Φ^{+} − Δ_{W}.

Proof Let c = |C(R)|; then c ≤ Σ_{r,s∈R}m_{r,s} < ∞, as R is finite. Since every root of depth d can be expressed as (r_{d}r_{d−1} ⋯ r_{2}) · α_{r_{1}} with each r_{i} ∈ R, there are no more than |R|^{d} roots of depth d. If we can show that no root in Φ^{+} − Δ_{W} can have depth exceeding c^{|R|}(|R| + 1) then the proof will be complete. So let β ∈ Φ^{+} − Δ_{W} have depth d, and let β_{1} ≺ ⋯ ≺ β_{d} = β be a sequence of roots. Note that β_{i} ∈ Φ^{+} − Δ_{W} for each i ∈ {1, …, d}. For i ∈ {1, …, d} define J_{i} = { r ∈ R | ⟨β_{i}, α_{r}⟩ ≥ −1 }. If r ∉ J_{i} then by Corollary 2.4 the coefficient of α_{r} in β_{j} is constant for all j ≥ i. Since ⟨α_{s}, α_{r}⟩ ≤ 0 for all s ∈ R − {r} it follows from Corollary 1.8 that ⟨β_{j}, α_{r}⟩ ≤ ⟨β_{i}, α_{r}⟩ for j ≥ i, and hence α_{r} ∉ J_{j}, for all j ≥ i. Thus the sets J_{i} form a decreasing chain.

Suppose J_{i} = ⋯ = J_{j} = J for i ≤ j. If k ∈ {i, …, j} and r ∈ J then −1 ≤ ⟨β_{k}, α_{r}⟩ ≤ 1, since r ∈ J_{k} and β_{k} does not dominate α_{r} (unless β_{k} = α_{r} in which case ⟨β_{k}, α_{r}⟩ = 1). Hence ⟨β_{k}, α_{r}⟩ ∈ C(R), by Proposition 2.6. So if j − i > c^{|R|}, then there will exist m, n ∈ {i, i + 1, …, j} with n > m and ⟨β_{n}, α_{r}⟩ = ⟨β_{m}, α_{r}⟩ for all r ∈ J. But if r ∉ J, then α_{r} has the same coefficient in β_{m} as in β_{n}, and it follows by Lemma 2.7 that ⟨β_{n}, β_{m}⟩ = 1. This contradicts Lemma 2.3, since β_{n} ∉ Δ_{W}. We conclude that if j − i ≥ c^{|R|} then J_{j} is strictly smaller than J_{i}. Since J_{1} ⊆ R it follows that the chain J_{1} ⊇ J_{2} ⊇ ⋯ ⊇ J_{d} can have length at most c^{|R|}(|R| + 1) and this finishes the proof.

3. Finitely generated Coxeter groups are automatic

The aim of this section is to show that Coxeter groups on finite generating sets are automatic groups (as defined in [2] or [5], for example). This is proved in [3] under the assumption that the Parallel Wall Theorem is valid. In our proof, the concept of root dominance introduced above replaces the parallel wall property.

Let (W, R) be a Coxeter system with R finite. Let R^{∗} be the free monoid on R, and let π: R^{∗} → W be the natural homomorphism. To avoid confusion with multiplication in W, we shall write x ∗ y for the product of elements x, y ∈ R^{∗}. Let ℓ be the length function on R^{∗}, defined by ℓ(r_{1} ∗ ⋯ ∗ r_{l}) = l whenever r_{1}, …, r_{l} ∈ R. Furthermore, let ⪯ be the lexicographical order on R^{∗} for some (arbitrary) ordering of R. We shall write x ≺ y if x ⪯ y and x ≠ y.

In the present context, any subset L of R^{∗} will be called a language, R being the alphabet and the elements of L the words of the language. Later in this section we will consider languages on other alphabets; however, our first objective is to describe a regular language L on R such that the restriction of π is a bijection from L to W.

A language is regular if and only if there exists a finite state automaton which accepts the words of the language and rejects words which are not in the language. The automaton has a finite number of states, one of which is prescribed as the starting state; it reads the letters of a word one at a time, starting from the left, and its state after reading a letter is completely determined by the letter and the state it was in before reading the letter. Finally, certain states are designated as “accept” states, the others as “reject” states; the automaton accepts the word if it is in an accept state after reading the final letter, and rejects it otherwise.

Recall that if w ∈ W, then l(w) = min{ ℓ(x) | x ∈ π^{−1}(w) }. An element x ∈ R^{∗} is called a reduced word if ℓ(x) = l(π(x)). Let L′ be the set of all reduced words. Clearly for each w ∈ W there exists a unique ν(w) ∈ π^{−1}(w) such that ν(w) ∈ L′ and ν(w) ⪯ x for all x ∈ π^{−1}(w) ∩ L′. We define the language L to consist of all these lexicographically minimal reduced words for the various elements of W:

L = { ν(w) | w ∈ W } = { y ∈ L′ | y ⪯ x for all x ∈ L′ with π(x) = π(y) }.

We shall describe a finite state automaton W of which L is the regular language.

Let Δ̃_{W} = Φ^{+} − Δ_{W} denote the (finite) complement of Δ_{W} in Φ^{+}. The accept states of the automaton W will be the subsets of Δ̃_{W}, and there will be one reject state. The starting state is the empty subset of Δ̃_{W}. The transition function μ: S × R → S (where S is the set of all states) is given by (S, r) ↦ S′, where

(i) if S is the reject state then so is S′, (ii) if S ⊆ Δ̃_{W} and α_{r} ∈ S then S′ is the reject state, (iii) if S ⊆ Δ̃_{W} and α_{r} ∉ S then S′ = S′′ ∩ Δ̃_{W}, where

S′′ = { r · α | α ∈ S } ∪ {α_{r}} ∪ { r · α_{s} | s ∈ R and s ≺ r }.

The proof that L is the regular language of W depends on the following lemma:

Lemma 3.1 Let w ∈ W and r_{1}, r_{2}, …, r_{l} ∈ R with ν(w) = r_{1} ∗ r_{2} ∗ ⋯ ∗ r_{l}. Then for arbitrary r ∈ R,

(i) ν(w) ∗ r is not reduced if and only if there exists i ∈ {1, 2, …, l} such that α_{r} = (r_{l}r_{l−1} ⋯ r_{i+1}) · α_{r_{i}},

(ii) if ν(w) ∗ r is reduced, then ν(w) ∗ r ∉ L if and only if there exists i ∈ {1, 2, …, l} and s ∈ R with s ≺ r_{i} such that (r_{l}r_{l−1} ⋯ r_{i}) · α_{s} = α_{r}; if this holds then ν(wr) = r_{1} ∗ ⋯ ∗ r_{i−1} ∗ s ∗ r_{i} ∗ ⋯ ∗ r_{l}.

Proof If α_{r} = r_{l}r_{l−1} ⋯ r_{i+1} · α_{r_{i}}, then r = v^{−1}r_{i}v, where v = r_{i+1} ⋯ r_{l}, and so wr = r_{1}r_{2} ⋯ r_{i−1}r_{i}vr = r_{1}r_{2} ⋯ r_{i−1}v = r_{1} ⋯ r_{i−1}r_{i+1} ⋯ r_{l} has length less than l. If there is no i such that α_{r} = (r_{l}r_{l−1} ⋯ r_{i+1}) · α_{r_{i}}, then clearly α_{r} ∉ N(w), and l(wr) = l(w) + 1 by Proposition 1.1. Thus (i) is proved.

Suppose now that l(wr) = l + 1, and let ν(wr) = s_{1} ∗ ⋯ ∗ s_{l+1}. Then

(1)  ν(wr) = s_{1} ∗ ⋯ ∗ s_{l+1} ⪯ r_{1} ∗ ⋯ ∗ r_{l} ∗ r

since the right hand side also has length l + 1 and is in π^{−1}(wr). Since l(w) = l and w = (wr)r = s_{1}s_{2} ⋯ s_{l+1}r, it follows by the exchange condition (see Proposition 1.1) that w = s_{1} ⋯ s_{i−1}s_{i+1} ⋯ s_{l+1} for some i ≤ l + 1, and so

(2)  ν(w) = r_{1} ∗ ⋯ ∗ r_{l} ⪯ s_{1} ∗ ⋯ ∗ s_{i−1} ∗ s_{i+1} ∗ ⋯ ∗ s_{l+1}.

It is immediate from Eqs. (1) and (2) that r_{j} = s_{j} for all j ∈ {1, 2, … i − 1}. So w = r_{1} ⋯ r_{i−1}s_{i+1} ⋯ s_{l+1}, and we deduce that s_{i+1} ⋯ s_{l+1} = r_{i} ⋯ r_{l}. Now if r_{i} ∗⋯∗r_{l} ≺ s_{i+1} ∗⋯∗s_{l+1}, then s_{1} ∗⋯∗s_{i} ∗r_{i} ∗⋯∗r_{l} ≺ s_{1} ∗⋯∗s_{l+1} = ν(wr), which is impossible, and, similarly, s_{i+1} ∗ ⋯ ∗ s_{l+1} ≺ r_{i} ∗ ⋯ ∗ r_{l} would give r_{1} ∗ ⋯ ∗ r_{i−1} ∗ s_{i+1} ∗ ⋯ ∗ s_{l+1} ≺ r_{1} ∗ ⋯ ∗ r_{l} = ν(w), which is also impossible. Hence r_{j} = s_{j+1} for all j ∈ {i, i + 1, …, l}. Thus we have shown that ν(wr) = r_{1} ∗ ⋯ ∗ r_{i−1} ∗ s ∗ r_{i} ∗ ⋯ ∗ r_{l}, where s = s_{i}.

By Eq. (1) we have either that i ≤ l and s ≺ r_{i}, or else i = l + 1 and s = r. If ν(w)∗r ∉ L the former case obtains, and since sr_{i} ⋯ r_{l} = r_{i} ⋯ r_{l}r it follows readily that (r_{l}r_{l−1} ⋯ r_{i})·α_{s} = α_{r}. Conversely, whenever there exists i ∈ {1, 2, …, l} and s ≺ r_{i} such that (r_{l}r_{l−1} ⋯ r_{i}) · α_{s} = α_{r}, then r_{1} ⋯ r_{i−1}sr_{i} ⋯ r_{l} = r_{1} ⋯ r_{l}r and r_{1} ∗ ⋯ ∗ r_{i−1} ∗ s ∗ r_{i} ∗ ⋯ ∗ r_{l} ≺ r_{1} ∗ ⋯ ∗ r_{l} ∗ r. Hence ν(wr) ≠ r_{1} ∗ ⋯ ∗ r_{l} ∗ r; that is, ν(w) ∗ r ∉ L.

Lemma 3.2 Suppose that β ∈ Δ_{W} and u, v ∈ W satisfy u · β, v^{−1} · β ∈ Π. Then l(uv) ≠ l(u) + l(v).

Proof Let u · β = α_{r} and v^{−1} · β = α_{s}, where r, s ∈ R. Since r · α_{r} and s · α_{s} are negative, β ∈ N(ru) ∩ N(sv^{−1}). Since β ∈ Δ_{W} there exists γ ∈ Φ^{+}, with γ ≠ β, such that β dom_{W} γ. By the definition of dominance we see that ru·γ and sv^{−1}·γ are both negative. Since u · γ ≠ u · β = α_{r}, it follows that u · γ ∉ N(r); hence u · γ ∈ Φ^{−}. Similarly, v^{−1} · γ ∈ Φ^{−}, since v^{−1} · γ ≠ α_{s}. Hence N(u) ∩ N(v^{−1}) ≠ ∅, and so l(uv) ≠ l(u) + l(v) (by Lemma 1.2).

Proposition 3.3 The language L is the language recognized by the automaton W described above.

Proof Suppose first of all that the automaton rejects the word r_{1} ∗ ⋯ ∗ r_{n}, and that rejection occurs when reading r_{l+1}. For convenience of notation, let α_{i} = α_{r_{i}} for all i ∈ {1, 2, …, n}; for i ≤ l let R_{i} = { s ∈ R | s ≺ r_{i} }, and let S_{i} ⊆ Δ̃_{W} be the state of the automaton after reading r_{i}. Then for all i < l,

S_{i+1} ⊆ r_{i+1} · S_{i} ∪ {α_{i+1}} ∪ r_{i+1} · R_{i+1}.

Thus S_{l} is contained in

{ (r_{l} … r_{i+1}) · α_{i} | 1 ≤ i ≤ l } ∪ r_{l} · R_{l} ∪ (r_{l}r_{l−1}) · R_{l−1} ∪ ⋯ ∪ (r_{l}r_{l−1} ⋯ r_{1}) · R_{1}.

Since rejection occurs when r_{l+1} is read, α_{l+1} is in this set. Now by Lemma 3.1 (i), if α_{l+1} ∈ T = { (r_{l} … r_{i+1}) · α_{i} | 1 ≤ i ≤ l } then r_{1} ∗ ⋯ ∗ r_{l+1} is not reduced, hence not in L. If α_{l+1} ∉ T then r_{1} ∗ ⋯ ∗ r_{l+1} is reduced, but since α_{l+1} is in some (r_{l}r_{l−1} ⋯ r_{i}) · R_{i} it now follows by Lemma 3.1 (ii) that r_{1} ∗ ⋯ ∗ r_{l+1} ∉ L. Hence r_{1} ∗ ⋯ ∗ r_{n} ∉ L, as required.

For the converse, suppose that r_{1} ∗ ⋯ ∗ r_{n} ∉ L, and choose l < n maximal such that r_{1} ∗ ⋯ ∗ r_{l} ∈ L. Using the same notation as above, our aim is to show that α_{l+1} ∈ S_{l}, so that the automaton rejects r_{1} ∗ ⋯ ∗ r_{l+1}. Assume, for a contradiction, that α_{l+1} ∉ S_{l}.

Suppose first of all that r_{1} ∗ ⋯ ∗ r_{l+1} is not reduced. By Lemma 3.1 (i) we have that α_{l+1} = (r_{l} ⋯ r_{i+1}) · α_{i} for some i ∈ {1, 2, …, l}. Thus l is in the set { k ∈ {i, i + 1, …, l} | (r_{k}r_{k−1} ⋯ r_{i+1}) · α_{i} ∉ S_{k} }; let j be the least element of this set, and let β = (r_{j}r_{j−1} ⋯ r_{i+1}) · α_{i}. Since α_{i} ∈ S_{i}, certainly j > i. Thus (r_{j−1} ⋯ r_{i+1}) · α_{i} ∈ S_{j−1}, by minimality of j. So β ∈ r_{j} · S_{j−1}. Since r_{j} · S_{j−1} ∩ Δ̃_{W} ⊆ S_{j} it follows that β ∉ Δ̃_{W}. Observe that r_{i+1}r_{i+2} ⋯ r_{j} · β = α_{i} and (r_{j+1}r_{j+2} ⋯ r_{l})^{−1} · β = α_{l+1} are both in Π. By Lemma 3.2 it follows that l(r_{i+1} ⋯ r_{l}) ≠ l − i; but this contradicts the fact that r_{1} ⋯ r_{l} ∈ L. Hence r_{1} ∗ ⋯ ∗ r_{l+1} is reduced.

Since r_{1} ∗⋯∗r_{l+1} ∉ L it follows by Lemma 3.1 (ii) that α_{l+1} = (r_{l} ⋯ r_{i})·α_{s} for some i ∈ {1, 2, … l} and some s ∈ R_{i}. Let j ∈ {i, i+1, …, l} be minimal such that β = (r_{j}r_{j−1} ⋯ r_{i}) · α_{s} ∉ S_{j}. If j = i, then since r_{i} · R_{i} ∩ Δ̃_{W} ⊆ S_{i} it follows that β ∉ Δ̃_{W}. If j > i then minimality of j forces (r_{j−1} ⋯ r_{i}) · α_{s} ∈ S_{j−1}, and since r_{j} ·S_{j−1} ∩Δ̃_{W} ⊆ S_{j} it again follows that β ∉ Δ̃_{W}. But r_{i}r_{i+1} ⋯ r_{j} ·β = α_{s} and (r_{j+1}r_{j+2} ⋯ r_{l})^{−1} · β = α_{l+1} are both in Π, and the same argument as used in the previous paragraph again yields a contradiction.

For each r ∈ R define

L_{r} = { (x_{1}, x_{2}) ∈ R^{∗} × R^{∗} | x_{1}, x_{2} ∈ L and π(x_{1})r = π(x_{2}) }.

We shall describe a finite state automaton M_{r} which recognizes whether or not a pair (x_{1}, x_{2}) ∈ R^{∗} × R^{∗} is in L_{r}. These “multiplier automata” M_{r} together with the “word acceptor” W form an automatic structure for W. (Strictly speaking, a multiplier automaton is also required for the identity element of W, recognizing (x_{1}, x_{2}) if and only if x_{1}, x_{2} ∈ L and π(x_{1}) = π(x_{2}). However, since the words of our language L correspond bijectively with the elements of W, the required automaton is a trivial modification of W.) We refer the reader to [2] or [5] for further discussion of automatic groups.

The automaton M_{r} is required to read x_{1} and x_{2} simultaneously, one letter from each at a time, from left to right. If x_{1} and x_{2} are of unequal lengths then, of course, the end of the shorter will be encountered with part of the longer still unread. To cope with this, a padding symbol, which we will denote by $, is used; the automaton appends as many of these to the shorter of x_{1} and x_{2} as is necessary to make the lengths equal. This turns L_{r} into a language over the alphabet R = (R ∪ {$}) × (R ∪ {$}) − {($, $)}.

Lemma 3.1 enables us to give an explicit description of the language L_{r}. Note first that, trivially, (y, z) ∈ L_{r} if and only if (z, y) ∈ L_{r}.

Proposition 3.4 Suppose that y, z ∈ R^{∗} with ℓ(z) ≤ ℓ(y), and let y = s_{1}∗⋯∗s_{l}, where s_{1}, s_{2}, …, s_{l} ∈ R. Then (y, z), (z, y) ∈ L_{r} if and only if y ∈ L and the following conditions are satisfied for some j ∈ {1, 2, …, l}:

(a) z = s_{1} ∗ ⋯ ∗ s_{j−1} ∗ s_{j+1} ∗ ⋯ ∗ s_{l}, and

(b) α_{r} = (s_{l}s_{l−1} ⋯ s_{j+1}) · α_{s_{j}}.

Furthermore, if these conditions hold, then either j = l or s_{j} ≺ s_{j+1}.

Proof If (y, z) ∈ L_{r} then y = ν(π(z)r), and it follows from Lemma 3.1 that (a) and (b) are satisfied for some j ∈ {1, 2, …, l}, and that s_{j} ≺ s_{j+1} if j ≠ l.

Conversely, suppose that y ∈ L and that conditions (a) and (b) are satisfied; we must show that z = ν(π(y)r). Clearly π(z) = π(y)r, and by Lemma 3.1 it follows that ν(π(z)) is obtained from y by deleting some s_{k}. If k ≠ j then we have that s_{1} ⋯ s_{j−1}s_{j+1} ⋯ s_{l} = s_{1} ⋯ s_{k−1}s_{k+1} ⋯ s_{l}, and it follows easily that s_{j} and s_{k} can be cancelled from s_{1} ⋯ s_{l}, contradicting the fact that y is reduced.

We now describe a suitable automaton M_{r}. It has one accept state, Y, all other states being reject states. There is a “failure” state, F (from which there are no transitions to other states). All subsets of Δ̃_{W} are states, and the remaining states are the elements of the Cartesian product P(Δ̃_{W}) × Δ̃_{W} × R × {±1}, where P(Δ̃_{W}) is the power set of Δ̃_{W}. Let S_{r} be the set of all these states, and let ∅ ⊂ Δ̃_{W} be the initial state.

Note that the subset P(Δ̃_{W})∪{F} of S_{r} can be identified with the set of states of W. Let μ be the transition function, described above, for W. The transition function μ_{r}: S_{r} × R → S_{r} for the automaton M_{r}, is defined by the rules listed below. Let S ∈ S_{r} and s, t ∈ R^{+}, and for brevity let S′ = μ_{r}(S, (s, t)).

Case 1: X ⊆ Δ̃_{W}.

(i) If s = t ∈ R then X′ = μ(X , s).

(ii) If either s or t is $, then X′ = \{ \begin{matrix}Y & if \{s, t\} = \{r, $\} and μ(X , r) ≠ F, \\ F & otherwise. \end{matrix}

(iii) If s ≺ t ∈ R, then X′ = \{ \begin{matrix}(μ(X , s), α_{s}, t, +1) & if μ(X, s) ≠ F, \\ F & if μ(X, s) = F. \end{matrix}

(iv) If t ≺ s ∈ R, then X′ = \{ \begin{matrix}(μ(X , t), α_{t}, s, −1) & if μ(X, t) ≠ F, \\ F & if μ(X, t) = F. \end{matrix}

Case 2: X = (X, β, u, +1) ∈ P(Δ̃_{W}) × Δ̃_{W} × R^{+} × {±1}.

Let X′ = μ(X, s) and γ = s · β.

(i) If s ≠ u, then X′ = F.

(ii) If s = u and t ∈ R, then X′ = \{ \begin{matrix}(X′, γ, t, +1) & if X′ ≠ F and γ ∈ Δ̃_{W}, \\ F & if X′ = F or γ ∉ Δ̃_{W}. \end{matrix}

(iii) If (s, t) = (u, $) and X′ ≠ F, then X′ = \{ \begin{matrix}Y & if γ = α_{r}, \\ F & if γ ≠ α_{r}. \end{matrix}

Case 3: X = (X, β, u, −1) ∈ P(Δ̃_{W}) × Δ̃_{W} × R^{+} × {±1}.

Let X′ = μ(X, t) and γ = t · β.

(i) If t ≠ u then X′ = F.

(ii) If t = u and s ∈ R, then X′ = \{ \begin{matrix}(X′, γ, s, −1) & if X′ ≠ F and γ ∈ Δ̃_{W}, \\ F & if X′ = F or γ ∉ Δ̃_{W}. \end{matrix}

(iii) If (s, t) = ($, u) and X′ ≠ F, then X′ = \{ \begin{matrix}Y & if γ = α_{r}, \\ F & if γ ≠ α_{r}. \end{matrix}

Case 4: X = Y or F.

X′ = F in all cases.

Proposition 3.5 The automaton M_{r} defined above recognizes the language L_{r}.

Proof For each x ∈ R^{∗} and i ≤ ℓ(x), let x(i) be the initial segment of x length i. That is, ℓ(x(i)) = i and x = x(i)∗y for some y. If y, z ∈ R^{∗} with ℓ(y) = ℓ(z) = i, we will say that (y, z) is viable if there exists (x_{1}, x_{2}) ∈ L_{r} with x_{1}(i) = y and x_{2}(i) = z. Note in particular that (y, z) is not viable if either y or z is not in L.

Let x_{1} = s_{1} ∗ s_{2} ∗ ⋯ ∗ s_{l} and x_{2} = t_{1} ∗ t_{2} ∗ ⋯ ∗ t_{m} be elements of R^{∗}; we must show that M_{r} accepts (x_{1}, x_{2}) if and only if (x_{1}, x_{2}) ∈ L_{r}. For each i ≤ max(l, m), let X_{i} be the state of M_{r} after reading (x_{1}(i), x_{2}(i)) (padded if necessary).

Let j ∈ ℕ be maximal such that s_{i} = t_{i} for all i < j. In view of rule (i) of Case 1, and the fact that X_{0} ⊆ Δ̃_{W}, we see that X_{i} ⊆ Δ̃_{W} for all i < j, and, furthermore, X_{i} is the state that W would be in after reading s_{1} ∗ ⋯ ∗ s_{i}. So if X_{i} = F, then s_{1} ∗ ⋯ ∗ s_{i} ∉ L, in which case (x_{1}, x_{2}) is clearly not viable.

Suppose instead that X_{j−1} ≠ F, so that x_{1}(j − 1) = x_{2}(j − 1) = x ∈ L. If l = m = j − 1 (so that the process terminates here) then rejection occurs, since X_{j−1} is a subset of Δ̃_{W}, and hence not equal to Y, which is the only accept state. Clearly, in this case, (x_{1}, x_{2}) = (x, x) ∉ L_{r} since π(x)r ≠ π(x). Suppose now that one of l, m equals j − 1, and the other is greater than j − 1. Then (x_{1}, x_{2}) will be in L_{r} if and only if {x_{1}, x_{2}} = {x, x ∗ r} and x ∗ r ∈ L. By rule (ii) of Case 1 we see that X_{j} is indeed the failure state if the element of R that is read at this stage is not r, or if W would reject x ∗ r. Otherwise, X_{j} = Y, and acceptance will occur, as it should, provided that the end of (x_{1}, x_{2}) has been reached; the Case 4 rule shows that X_{j+1} = F if there is another letter after x ∗ r in the longer x_{i}.

Suppose that x(j − 1) ∈ L and l, m ≥ j, and suppose first of all that s_{j} ≺ t_{j}. By Proposition 3.4 we see that (x_{1}, x_{2}) ∈ L_{r} if and only if x_{1} ∈ L and t_{i} = s_{i+1} for j ≤ i ≤ m = l − 1, and α_{r} = (s_{l}s_{l−1} ⋯ s_{j+1}) · α_{s_{j}}. Rule (iii) of Case 1 applies when (s_{j}, t_{j}) is read. If X_{j} = F then x_{1}(j) ∉ L, and so (x_{1}(j), x_{2}(j)) is not viable. Otherwise, the following conditions hold at k = j:

(a) s_{1} ∗ s_{2} ∗ ⋯ ∗ s_{k} ∈ L,

(b) s_{i} = t_{i−1} for all i such that j < i ≤ k,

(c) X_{k} = (X_{k}, β_{k}, t_{k}, +1), where X_{k} is the state W would be in after reading s_{1} ∗ s_{2} ∗ ⋯ ∗ s_{k}, and β_{k} = (s_{k} ⋯ s_{j+1}) · α_{s_{j}} ∈ Δ̃_{W}.

Choose k maximal such that these conditions hold. By Case 2 we see that either s_{k+1} ≠ t_{k}, or t_{k+1} ∉ R, or μ(X_{k}, s_{k+1}) = F, or s_{k+1} · β ∉ Δ̃_{W}.

Suppose first that t_{k+1} ∈ R, so that either the first, the third or the fourth of the above alternatives obtains. If s_{k+1} ≠ t_{k} then Proposition 3.4 shows that (x_{1}, x_{2}) ∉ L_{r}; rule (i) of Case 2 shows that failure occurs. If μ(X_{k}, s_{k+1}) = F then x_{1}(k + 1) ∉ L, and so (x_{1}, x_{2}) ∉ L_{r}; rule (ii) of Case 2 shows that failure occurs. If s_{k+1}·β ∈ Δ_{W} then Lemma 3.2 shows that l(uv) = l(u)+l(v) is not compatible with us_{k+1} · β and v^{−1}s_{k+1} · β being both in Π. Taking u = s_{j+1} ⋯ s_{k+1} and v = s_{k+2} ⋯ s_{l}, it follows that either s_{j+1} ∗ ⋯ ∗ s_{l} is not reduced, or else (s_{l} ⋯ s_{j+1}) · α_{s_{j}} ≠ α_{r}, whence (x_{1}, x_{2}) ∉ L_{r}. Furthermore, rule (ii) of Case 2 shows that failure occurs.

Consider now the case t_{k+1} = $; that is, m = k. If s_{k+1} ≠ t_{k} or if x_{1}(k) ∗ s_{k+1} ∉ L then (x_{1}, x_{2}) ∉ L_{r}; rules (i) and (iii) of Case 2 show that failure occurs. If s_{k+1} = t_{k} and x_{1}(k) ∗ s_{k+1} ∈ L then (x_{1}, x_{2}) ∈ L_{r} if and only if l = k + 1 and s_{l} · β = α_{r}. Rule (iii) of Case 2 shows that X_{l} = Y if and only if s_{k+1} · β = α_{r}; by the Case 4 rule, acceptance occurs if and only if the process stops at this point, that is, if and only if l = k + 1.

We have now shown that in all cases when s_{j} ≺ t_{j}, the automaton M_{r} accepts (x_{1}, x_{2}) if and only if (x_{1}, x_{2}) ∈ L_{r}. Totally analogous arguments apply if t_{j} ≺ s_{j}, using the rules of Case 3 in place of Case 2.

References

1. Bourbaki, N.: Groupes et Algèbres de Lie, Chap. 4, 5, 6. Hermann, Paris, 1968

2. Cannon, J.W., Epstein, D.B., Holt, D.F., Paterson, M.S., Thurston, W.P.: Word Processing and Group Theory. University of Minnesota Supercomputer Institute (1991) (preprint)

3. Davis, M.W., Shapiro, M.D.: Coxeter groups are automatic. Ohio State University (1991) (preprint)

4. Dyer, M.J.: Hecke algebras and reflections in Coxeter groups. PhD thesis, University of Sydney, 1987

5. Gersten, S.M., Short, H.B.: Small cancellation theory and automatic groups. Invent. Math. 102 (1990) 305–334 14 Brigitte Brink and Robert B. Howlett 6. Hiller, H.: Geometry of Coxeter Groups. Pitman Advanced Publishing Program, 1981 This article was processed by the author using the Springer-Verlag TEX MatAnn macro package 1991.