Submitted exclusively to the London Mathematical Society doi:10.1112/0000/000000

Artin groups of large type are shortlex automatic with regular geodesics

Derek F. Holt and Sarah Rees

Abstract

We prove that any Artin group of large type is shortlex automatic with respect to its standard generating set, and that the set of all geodesic words over the same generating set satisfies the Falsification by Fellow-Traveller Property (FFTP) and hence is regular.

1. Introduction

In this article we consider Artin groups of large type, in their standard presentations. The standard presentation for an Artin group over its standard generating set X = {a_{1}, …, a_{n}} is as

⟨a_{1}, …, a_{n} | _{m_{ij}}(a_{i}, a_{j}) = _{m_{ji}}(a_{j}, a_{i}) for each i ≠ j⟩,

where the integers m_{ij} are the entries in a Coxeter matrix (a symmetric n × n matrix (m_{ij}) with entries in ℕ ∪ {∞}, m_{ii} = 1, m_{ij} ≥ 2, ∀i ≠ j), and where for generators a, a′ and m ∈ ℕ we define _{m}(a, a′) to be the word that is the product of m alternating a’s and a′’s that starts with a. Adding the relations a_{i}^{2} = 1 to those for the Artin group defines the associated Coxeter group, which is more commonly presented as

⟨a_{1}, …, a_{n} | (a_{i}a_{j})^{m_{ij}} = 1 for each i, j⟩.

An Artin group is said to be of spherical or finite type if the associated Coxeter group is finite, of dihedral type if the associated Coxeter group is dihedral (or, equivalently, the standard generator set has two elements), of large type if m_{ij} ≥ 3 for all i ≠ j, and of extra-large type if m_{ij} ≥ 4 for all i ≠ j.

The aim of this paper is to prove that Artin groups of large type are shortlex automatic over the standard generating set X, for any ordering of A := X ∪ X^{−1}. We shall show also that the set of all geodesic words over A satisfies the Falsification by Fellow-Traveller Property (FFTP), and hence is a regular set. These two main results appear as Theorem 3.2 and Theorem 4.6.

We remind the reader that a group G = ⟨X⟩ is defined to be shortlex automatic if the set of minimal representatives in G of words under the shortlex ordering, with respect to some ordering of X ∪ X^{−1}, is a regular language L, and for some constant k, any two words w, v ∈ L with |w^{−1}v|_{G} ≤ 1 ‘k-fellow travel’. Here we use |u|_{G} to denote the word length of the minimal representative of u in G; words w, v are defined to k-fellow travel if, where w(i), v(i) denote the prefixes of w, v of length i, we have |w(i)^{−1}v(i)| ≤ k for each i = 1, …, max{|w|, |v|}. An additional fellow traveller property could make the group biautomatic. We do not attempt to give a complete introduction to this topic, but refer the reader to [4] as a basic reference on automatic groups.

The Falsification by Fellow-Traveller Property (FFTP), which is not known to be related to automaticity, is proved in [7] to be a sufficient condition for the set of all geodesics over A

2000 Mathematics Subject Classification 20F36 (primary), 20F10, 20F65 (secondary).

Page 2 of 26 DEREK F. HOLT AND SARAH REES

to be regular. We say that the set of all geodesics over A satisfies FFTP if, for some k, any non-geodesic word over A asynchronously k-fellow travels with a shorter representative of the same element.

If, for an Artin group, m_{ij} = ∞ for all i ≠ j, then the group is free. Since free groups are well understood and are known to be biautomatic, we shall assume that this is not the case, and define M to be 2 max{m_{ij} | m_{ij} ≠ ∞}. This will be our fellow traveller constant for automaticity proofs.

It is known that Artin groups of spherical type [2], extra-large type [8], large type with at most three generators [1], or right angled type [5, 9] are biautomatic. The first two results were each proved by direct construction of an appropriate regular language, while the third result was proved via the verification of appropriate small cancellation conditions on the groups.

Artin groups of spherical type are also known to be Garside, and the language of geodesics in a Garside group with respect to the Garside (rather than standard) generators was studied by Charney and Meier ([3]). The geodesics for 2-generator Artin groups over the standard generating set were subsequently described by Mairesse and Mathéus in [6].

The remainder of this paper is divided into three sections. Section 2 discusses 2-generator Artin groups, the structure of their geodesics, and the process of reduction to them, and proves Theorems 2.4 and 2.6. These are the 2-generator analogues of Theorems 3.2 and 4.6, but hold for all 2-generator Artin groups, without requiring the groups to be of large type; they are vital components of the higher rank results. In the final two sections we consider Artin groups of large type. Section 3 considers the process that rewrites a word to shortlex normal form, and proves Theorem 3.2, while Section 4 is dedicated to the proof of Theorem 4.6.

Notational Conventions: We use a, b, or a_{1}, a_{2}, …, a_{n} for the fixed generators of an Artin group, X = {a_{1}, …, a_{n}}, A = X ∪ X^{−1}. We use the shortlex ordering <_{slex} on A^{∗} relative to some fixed but arbitrary ordering of A; u <_{slex} v if either u is shorter than v or u and v have the same length but u precedes v lexicographically. We call elements of X generators, and elements of the larger set A letters; a letter is positive if it is a generator, negative otherwise. We define the name of the letters a_{i} and a_{i}^{−1} to be a_{i}. We say that a word w ∈ A^{∗} involves the generator a_{i} if w contains a letter with name a_{i}, and we call w a 2-generator word if it involves exactly two of the generators. We shall generally use x, y, z, t for generators in X and g, h for letters in A. Words in A^{∗} will be denoted by u, v, w (possibly with subscripts) or α, β, γ, η, ξ. (Roughly speaking, the difference is that u, v, w will be used for interesting subwords of a specified word, and the Greek letters for subwords in which we are not interested.) A positive word is one in X^{∗} and a negative word one in (X^{−1})^{∗}; otherwise it is unsigned. For u, v ∈ A^{∗}, u = v denotes equality as words, whereas u =_{G} v denotes equality within the Artin group. The length of the word w is denoted by |w|, while as above |w|_{G} denotes the length of a geodesic representative.

For any distinct letters x and y and a positive integer r, we define alternating products r(x, y) and (y, x)_{r}. The product _{r}(x, y), is defined, as it was earlier, to be the word of length r of alternating x and y starting with x, while (y, x)_{r} is defined to be the word of length r of alternating x and y ending with x. For example, _{6}(x, y) = xyxyxy = (x, y)_{6}, _{5}(x, y) = xyxyx = (y, x)_{5}. We define both _{0}(x, y) and (y, x)_{0} to be the empty word. For any nonempty word w, we define f[w] and l[w] to be respectively the first and last letter of w, and pre[w] and suf[w] to be the maximal proper prefix and suffix of w. So w = pre[w]l[w] = f[w]suf[w].

2. 2-generator Artin groups

The 2-generator subwords of words over the standard generators of an Artin group of large type will play a significant role, so we first study certain aspects of the 2-generator case.

Let

DA(m) = ⟨a, b | _{m}(a, b) = _{m}(b, a)⟩

ARTIN GROUPS OF LARGE TYPE Page 3 of 26

be a 2-generator (dihedral) Artin group with m ≥ 2. The element

Δ := _{m}(a, b) =_{DA(m)} _{m}(b, a)

is called the Garside element. If m is even then Δ is central, while if m is odd then a^{Δ} = b and Δ^{2} is central. Conjugation by Δ induces a permutation δ of order 2 or 1 on the letters in A, and hence an automorphism δ of order 2 or 1 of the free monoid A^{∗}.

Let w be a freely reduced word over A = {a, b, a^{−1}, b^{−1}}. Then we define p(w) to be the minimum of m and the length of the longest subword of w of alternating a’s and b’s (that is the length of the longest subword of w of the form _{r}(a, b) or _{r}(b, a)). Similarly, we define n(w) to be the minimum of m and the length of the longest subword of w of alternating a^{−1}’s and b^{−1}’s. It is proved in [6] that w is geodesic in DA(m) if and only if p(w) + n(w) ≤ m. If p(w) + n(w) < m, then w is the unique geodesic representative of the group element it defines, but if p(w) + n(w) = m then there are other representatives.

For example, consider the case m = 3 in which

DA(m) = ⟨a, b | aba = bab⟩.

In this case aba and bab are two geodesic representatives of the same element with p(aba) = p(bab) = 3, n(aba) = n(bab) = 0. Less trivially, let w = ab^{2}a^{−1}. Then p(w) = 2, n(w) = 1, and so w is geodesic. Since b^{−1}Δ =_{DA(m)} ab =_{DA(m)} Δa^{−1} and Δb =_{DA(m)} aΔ, we see that

w = ab^{2}a^{−1} =_{DA(m)} b^{−1}Δba^{−1} =_{DA(m)} b^{−1}aΔa^{−1} =_{DA(m)} b^{−1}a^{2}b

Based on what we have observed in these two pairs of geodesic words, we shall identify a set of geodesic words which we shall call critical words, and define an involution τ acting on that set. The recognition of critical subwords of a word and their replacement by their images under τ will turn out to be crucial to the recognition of words in shortlex normal form, and to the rewriting of words to that form, both for the dihedral Artin groups that we consider now and for higher rank Artin groups of large type. Critical words w in DA(m) will be non-unique geodesic words (hence freely reduced with p(w) + n(w) = m). From our definition we shall verify the following.

Proposition 2.1. For any critical word w:

(1) τ(w) is also critical, it represents the same element of DA(m) as w, and τ(τ(w)) = w.

(2) p(τ(w)) = p(w) and n(τ(w)) = n(w).

(3) The names of the first letters of w and τ(w) are distinct, as are the names of the last letters of w and τ(w).

(4) The first letters of w and τ(w) have the same sign if w is positive or negative, but different signs if w is unsigned; the same is true of the last letters of w and τ(w).

(5) w and τ(w) 2m-fellow travel. Furthermore, any freely reduced word w satisfying p(w) + n(w) ≥ m must contain at least one critical subword.

A freely reduced, unsigned, geodesic word w with p(w) + n(w) = m is defined to be critical if it is has either of the forms

p(x, y)ξ(z^{−1}, t^{−1})_{n} or _{n}(x^{−1}, y^{−1})ξ(z, t)_{p}.

with p = p(w), n = n(w) and {x, y} = {z, t} = {a, b}. (Obviously these conditions put some restrictions on the subword ξ.)

We define a positive geodesic word w to be critical if it has either of the forms _{m}(x, y)ξ or ξ(x, y)_{m}, and only the one positive alternating subword of length m. Similarly we define a negative geodesic word w to be critical it is has either of the forms _{m}(x^{−1}, y^{−1})ξ or ξ(x^{−1}, y^{−1})_{m}, and only the one negative alternating subword of length m. In either case the uniqueness condition on the maximal alternating subword ensures that a maximal alternating subword is either on the left side or the right side but not both (unless ξ is empty), and so the decomposition of the word is uniquely defined.

The involution τ is defined in terms of the automorphism δ of A^{∗} that we defined earlier. Note that, for any word w, δ(w) is a word representing the element w^{Δ} =_{DA(m)} Δ^{−1}wΔ =_{DA(m)} ΔwΔ^{−1}.

For unsigned critical words, we define τ by

τ(_{p}(x, y) ξ (z^{−1}, t^{−1})_{n}) := _{n}(y^{−1}, x^{−1}) δ(ξ) (t, z)_{p},
τ(_{n}(x^{−1}, y^{−1}) ξ (z, t)_{p}) := _{p}(y, x) δ(ξ) (t^{−1}, z^{−1})_{n}.

For positive and negative geodesic words, we define τ as follows, where ξ is non-empty in the final four equations.

τ(_{m}(x, y)) := _{m}(y, x),
τ(_{m}(x^{−1}, y^{−1})) := _{m}(y^{−1}, x^{−1})
τ(_{m}(x, y) ξ) := δ(ξ) (z, t)_{m}, where z = l[ξ], {x, y} = {z, t},
τ(ξ (x, y)_{m}) := _{m}(t, z) δ(ξ), where z = f[ξ], {x, y} = {z, t},
τ(_{m}(x^{−1}, y^{−1}) ξ) := δ(ξ) (z^{−1}, t^{−1})_{m}, where z = l[ξ]^{−1}, {x, y} = {z, t},
τ(ξ (x^{−1}, y^{−1})_{m}) := _{m}(t^{−1}, z^{−1}) δ(ξ), where z = f[ξ]^{−1}, {x, y} = {z, t}.

Proof of Proposition 2.1. Most of (1) is immediate from the definitions of critical words w, and of their images under τ. To verify that w and τ(w) represent the same group element, we observe (using Δ = _{m}(a, b) =_{DA(m)} _{m}(b, a)) that whenever p + n = m,

p(x, y) =_{DA(m)} _{n}(y^{−1}, x^{−1}) Δ and Δ (z^{−1}, t^{−1})_{n} =_{DA(m)} (t, z)_{p},

and so

p(x, y) ξ (z^{−1}, t^{−1})_{n} =_{DA(m)} _{n}(y^{−1}, x^{−1}) Δ ξ (z^{−1}, t^{−1})_{n}
=_{DA(m)} _{n}(y^{−1}, x^{−1}) δ(ξ) Δ (z^{−1}, t^{−1})_{n}
=_{DA(m)} _{n}(y^{−1}, x^{−1}) δ(ξ) (t, z)_{p}.

That τ(τ(w)) = w is clear for unsigned words w; for positive and negative words it will follow from (3).

(2) is immediate from the definitions.

It is immediate from the definition that Property (3) holds for an unsigned critical word. A short calculation verifies that it also holds for critical positive and negative words. For example, for a critical positive word w of the form _{m}(x, y), the definition of τ clearly ensures that the names of the last letters of w and τ(w) are different. If ξ is non-empty, the fact that w has a unique positive alternating subword of length m ensures, both when m is odd and even, that f[ξ] = l[_{m}(x, y)], and so that f[δ(ξ)] = y = f[τ(w)] ≠ x = f[w].

(4) is immediate from the descriptions of w and τ(w).

The fellow traveller property (5) follows from the observation that, for any prefix η of ξ, we have δ(η^{−1})_{n}(y^{−1}, x^{−1})^{−1} _{p}(x, y)η =_{DA(m)} δ(η^{−1})Δη =_{DA(m)} Δ, which has length at most m. Note that the words _{p}(x, y)η and _{n}(y^{−1}, x^{−1})δ(η) may not have the same length, but their length differs by |p − m| ≤ m. Hence the words fellow travel at distance at most 2m.

Finally we observe that any word w satisfying p(w) + n(w) ≥ m must have a prefix w′ = with p(w′) + n(w′) = m, which itself has a suffix w′′ that is either positive alternating of length p(w′) or negative alternating of length n(w′). If w′ is signed then w′′ is critical; otherwise, any suffix of w′ is critical that starts with a maximal alternating subword of w′ of the opposite sign to w′′.

We define T to be the set of all critical words. We call w upper critical if τ(w) <_{lex} w and lower critical if w <_{lex} τ(w). Note that Proposition 2.1 (3) and (4) ensure that whether w is upper or lower critical is determined by the first letter of w together with the fact of whether w is positive, negative or unsigned.

We easily deduce the following from Proposition 2.1, which we record here since it is useful later on.

Corollary 2.2. Suppose that w is critical. If w_{1} is a prefix of w that is also critical, then τ(w_{1}) begins with the same letter as τ(w). If w_{2} is a suffix of w that is also critical, then τ(w_{2}) ends with the same letter as τ(w).

We already observed that any non-geodesic or even non-unique geodesic must contain a critical subword. In fact we can use the critical subwords within non-geodesics to reduce to geodesic form.

Lemma 2.3. Suppose that w ∈ A^{∗} is geodesic and g ∈ A.

If wg is non-geodesic, then either l[w] = g^{−1} or w has a critical suffix v such that l[τ(v)] = g^{−1}. Similarly, if gw is non-geodesic, then either f[w] = g^{−1} or w has a critical prefix v such that f[τ(v)] = g^{−1}.

Proof. Let p = p(w), n = n(w). Suppose that wg is non-geodesic and that w does not end with g^{−1}, so wg is freely reduced. Then p(wg) + n(wg) > m, and since w is geodesic, we must have p(w) + n(w) = m and p(wg) + n(wg) = m + 1. If g = z ∈ X, then p(wg) = p + 1, and so wg must end with an alternating positive subword of length p + 1. Then wg (and hence w) also contains a negative alternating subword of length n, and hence w has a critical suffix v = _{n}(x^{−1}, y^{−1})ξ(z, t)_{p} for which l[τ(v)] = z^{−1} = g^{−1}. (This is true even when p = 0.) Similarly, if g = z^{−1} with z ∈ X then n(wg) = n + 1 and w has a critical suffix v = _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with l[τ(v)] = z = g^{−1}.

We can deduce the second result by applying the first result to w^{−1}.

In this article we are specifically interested in shortlex normal form. We shall see that whenever w is a freely reduced word that is not minimal under the shortlex ordering then w has a factorisation as w_{1}w_{2}w_{3}, where w_{2} is critical and either w_{1}τ(w_{2})w_{3} <_{lex} w or w_{1}τ(w_{2})w_{3} is not freely reduced. In that case, we call the substitution of τ(w_{2}) for w_{2} within w together with any subsequent free reduction within w_{1}τ(w_{2})w_{3} a critical reduction of w.

Where a critical reduction as above reduces w lexicographically, the first letter of τ(w_{2}) must precede the first letter of w_{2} lexicographically. Where a critical reduction is length reducing there could be free cancellation at either end of τ(w_{2}); however we shall see that we can always select reductions in such a way that free cancellation is at the right hand end of the critical subword. With this in mind we define W to be the set of freely reduced words that have no factorisation as w_{1}w_{2}w_{3} with w_{2} critical that gives either f[τ(w_{2})] <_{lex} f[w_{2}] or free cancellation between l[τ(w_{2})] and f[w_{3}].

Theorem 2.4. The set W is the set of shortlex minimal representatives for the 2-generator Artin group DA(m).

Proof. Since both free and critical reductions to a word produce a word less than it in the shortlex order, a shortlex minimal word must certainly be in W.

So now suppose that w ∈ W, but that w is not shortlex minimal. We may assume by induction that every subword of w is shortlex minimal.

First suppose that w is not geodesic. Then, since pre[w] is geodesic, Lemma 2.3 implies that pre[w] has a critical suffix w′ such that l[τ(w′)] = l[w]^{−1}. This contradicts w ∈ W.

So suppose that w is geodesic but not shortlex minimal. Then p + n = m, with p = p(w), n = n(w). Let v be the shortlex minimal representative of w. Then, since every subword of w is shortlex minimal, we must have f[v] <_{lex} f[w]. Let g = f[v]. Then g^{−1}w represents the same element as suf[v], and hence is not geodesic. So by Lemma 2.3, w has a critical prefix w′ with f[τ(w′)] = g. But then g <_{lex} f[w] implies τ(w′) <_{lex} w′, again contradicting w ∈ W.

This completes our proof of Theorem 2.4, which is an essential component of Theorem 3.2. We finish this section with some further technical results on geodesics, which will be used in Section 4.

Lemma 2.5. Suppose that w and v are distinct geodesics in DA(m) such that one can be obtained from the other by a single τ-move, and suppose that l[w] has name a. Let p = p(w), n = n(w), and suppose that p and n are both non-zero. Let σ be the longest alternating suffix of w.

(1) If σ = (b, a)_{p}, then v has either σ or (a^{−1}, b^{−1})_{n} as a suffix.

(2) If σ = (b^{−1}, a^{−1})_{n}, then v has either σ or (a, b)_{p} as a suffix.

(3) Otherwise σ is also the longest alternating suffix of v.

Proof. In cases (1) and (2), there are critical suffices containing σ and any critical subword intersecting σ must contain it. The result follows immediately by looking at the effect of τ on such a subword.

In case (3), without loss of generality we may assume that σ = (b, a)_{k}, with k < p, and we may assume that v is obtained from w by applying a single τ move that involves a critical subword w′ of w immediately preceding σ; note that σ itself cannot intersect a critical subword. We suppose that v contains a longer alternating suffix. Then l[τ(w′)] must be whichever element of {a, b} is not the first letter of σ. But in that case l[(w′)] = f[σ]^{−1}, and hence w is not freely reduced, and cannot be geodesic. We have a contradiction, and so deduce that σ is a longest alternating suffix of v.

Corollary 2.6. Suppose that w =_{DA(m)} v with w, v both geodesic, and l[w] ≠ l[v]. Then a single τ-move on a critical suffix of w transforms w to a geodesic word v′ that 2m-fellow travels with w, such that v =_{DA(m)} v′ and l[v′] = l[v].

Proof. It follows immediately from Theorem 2.4 that w and v are linked by a sequence of τ-moves. Then w and v are either both positive, or both negative, or by Lemma 2.5 one ends with a positive alternating word (b, a)_{p} and the other with (a^{−1}, b^{−1})_{n}, where p = p(w), n = n(w).

When both words are positive, we may (without loss of generality) suppose that w has a minimal critical suffix w′ of the form _{m}(a, b)ξ for some possibly empty word ξ. We let v′ be the word derived from w by applying a τ-move to w′. Then v′ 2m-fellow travels with w, by Proposition 2.1. It follows from the definition of τ that τ(w′) has its last letter distinct from w′, and hence this must be the last symbol of v. The argument is analogous when both words are negative.

So now we suppose that p(w) and n(w) are both non-zero. Assuming that the name of l[w] is a (and hence the name of l[v] is b) we see that w has a critical suffix w′ that ends either with (b, a)_{p}, or with (b^{−1}, a^{−1})_{n}. Again we let v′ be the word derived from w by applying a τ-move to w′. Then τ(w′) ends either with b^{−1} or with b, and so l[v′] has name b, the same as v.

We can also deduce the following, as is explained in Section 4 just before Proposition 4.6:

Corollary 2.7. For any m, the dihedral Artin group DA(m) defined over its standard generating set satisfies FFTP, and hence the set of all geodesics over that generating set is regular.

Note that the regularity of this set of geodesics was already known, [6].

Lemma 2.8. Suppose that for some letter g and some j ≥ 1, a τ-move transforms a geodesic word g^{j}u in DA(m) to a word v. Then there is a τ-move that transforms gu to a word v′ with l[v′] = l[v].

Proof. The given τ-move transforms a critical subword w of g^{j}u. The result is immediate except when w = g^{j′}u for some j′ ≥ 1. It is clear from the definition of critical words that in this case gu′ is also critical and that l[τ(w)] = l[τ(gu′)], and the result follows.

3. Shortlex reduction in Artin groups of large type

We assume from now on that G = ⟨X⟩ is an Artin group of large type defined by a matrix (m_{ij}). The large type condition demands that each m_{ij} is at least 3. We shall assume that not all m_{ij} are infinite; otherwise the group is free, and shortlex automaticity is easy to prove.

For any distinct pair of generators a_{i}, a_{j}, where i < j, we let G(a_{i}, a_{j}) be the subgroup of G generated by a_{i} and a_{j}. Then G(a_{i}, a_{j}) is a quotient group of the 2-generator Artin group DA(m_{ij}), and so all equations between words in the DA(m_{ij}) also hold in G(a_{i}, a_{j}).

Remark. For a general Artin group G with standard generating set X, a subgroup of G generated by a subset Y of X is known as a parabolic or special subgroup of G. It follows easily from the main result of this section (Theorem 3.2) that, in an Artin group of large type, the shortlex minimal representatives of elements within a special subgroup G_{Y} := ⟨Y ⟩ of G are the same as the shortlex minimal representatives of the corresponding elements of the Artin A_{Y} group defined by the presentation

⟨Y | _{m_{ij}}(a_{i}, a_{j}) = _{m_{ji}}(a_{j}, a_{i}) for each i ≠ j with a_{i}, a_{j} ∈ Y ⟩,

and that any geodesic representative of an element of G_{Y} involves only the generators in Y. It follows that G_{Y} ≅ A_{Y} and G_{Y} is quasi-convex in G.

It was already proved in [?] that G_{Y} ≅ A_{Y} for all special subgroups of all Artin groups G. In general however it is not known whether or not special subgroups of Artin groups are quasiconvex. Quasi-convexity has been proved where all m_{ij} are even, and also for Artin groups of finite type using the Garside generators (see the discussion preceding Problem 9 in [?]); hence Theorem 3.2 extends what was previously known about quasi-convexity.

Now if w is a 2-generator word in a_{i}, a_{j}, we define p(w) and n(w) just as we did for words of DA(m_{ij}) in Section 2, we call w critical if it satisfies the definition of criticality of that section, and then we define τ(w) just as in that section. From Proposition 2.1 we have w =_{G} τ(w). We also define δ(ξ) for any subword ξ of w, just as in Section 2. We denote by T_{ij} the set of critical words over a_{i}, a_{j}.

Of course we can define critical 2-generator words for any pair of generators; we denote by T the set of all such critical words (that is the union of all T_{ij}). The bijection τ from Section 2 is well defined on that set, and the integer valued maps p, n are well defined on the set of 2-generator words. We can also use the notation δ(ξ) without ambiguity, for subwords ξ of 2-generator words; even when ξ itself involves only one generator, it will always be clear which two generators are involved.

We shall say that a 2-generator word w involving a_{i}, a_{j} is 2-geodesic if it is geodesic as a word in the 2-generator Artin group DA(m_{ij}). We know from the previous section that this is the case if and only if p(w) + n(w) ≤ m_{ij}. We do not know at this stage that such words are geodesics as elements of G, but this will follow from Theorem 3.2.

Now suppose that w is a freely reduced word over the Artin generators and that w = α_{1}u_{1}β_{1} where u_{1} ∈ T_{i_{1}j_{1}} for some i_{1}, j_{1}. Then α_{1}τ(u_{1})β_{1} may contain a critical subword u_{2} in a set T_{i_{2}j_{2}} for which |{i_{1}, j_{1}} ∩ {i_{2}, j_{2}}| = 1, where u_{2} and τ(u_{1}) overlap in a single generator. If u_{2} overlaps the left hand end of τ(u_{1}) and, in addition, the name of l[α_{1}] is not in {a_{i_{1}}, a_{j_{1}}} then we have a critical left overlap. If u_{2} overlaps the right hand end of τ(u_{1}) and, in addition, the name of f[β_{1}] is not in {a_{i_{1}}, a_{j_{1}}} then we have a critical right overlap.

We shall consider sequences

α_{1}u_{1}β_{1},
α_{1}τ(u_{1})β_{1} = α_{2}u_{2}β_{2},
α_{2}τ(u_{2})β_{2} = α_{3}u_{3}β_{3},
…
α_{k}τ(u_{k})β_{k}.

of words that are all equal in the group, and where either we have a critical left overlap at every step or a critical right overlap at every step.

We call such a sequence a leftward or rightward critical sequence of length k for w.

For example, with m_{12}, m_{13}, m_{23} = 3, 4, 5 and writing a, b, c for a_{1}, a_{2}, a_{3}:

αca^{2}cab^{−1}c^{−1}b^{2}c(a^{−1}b^{−2}a)β,
αca^{2}ca(b^{−1}c^{−1}b^{2}cb)a^{−2}b^{−1}β,
α(ca^{2}cac)bc^{2}b^{−1}c^{−1}a^{−2}b^{−1}β,
αacac^{2}abc^{2}b^{−1}c^{−1}a^{−2}b^{−1}β

is a leftward critical sequence of length 3 in which the words u_{1}, u_{2}, u_{3} (defined above) are bracketed.

The following result, which we shall use in the proof of Theorem 3.2, is an easy consequence of Proposition 2.1 (5). We recall that M = 2 max{m_{ij} | m_{ij} ≠ ∞}.

Lemma 3.1. Suppose that w′ is derived from w by the application of a critical sequence. Then w and w′ M-fellow travel.

We call a critical sequence a reducing sequence if α_{k}τ(u_{k})β_{k} is either not freely reduced or is less than α_{1}u_{1}β_{1} lexicographically, and in the first case call it a length reducing sequence, in the second a lex reducing sequence. In general, a reducing sequence of either type might be either leftward or rightward, and a lex reducing sequence might be either leftward or rightward; but in this article, we shall reduce words to shortlex normal form using a combination of rightward

[figure: a^{−1}; b; a; b; a; b^{−1}; c^{−1}; b; c; b^{−1}; c; b; c^{−1}; a; b; a; b; a^{−1}; a]

[figure: c; a; c^{−1}; c; a; a; b^{−1}; a; b^{−1}; a^{−1}; a^{−1}; a^{−1}; b; b; c; b; c; b^{−1}; b^{−1}; c; b; c]

Figure 1. A rightward length reducing and a leftward lex reducing sequence in ⟨a, b, c | aba = bab, aca = cac, bcbc = cbcb⟩

length reducing sequences that spark off free reductions at the right hand ends of subwords τ(u_{k}), and leftward lex reducing sequences for which τ(u_{k}) <_{lex} u_{k}.

Now we define W to be the set of all freely reduced words w that admit no rightward length reducing sequence or leftward lex reducing of any length k ≥ 1. Note that this agrees with the definition of W in the 2-generator case in Section 2. We call the words in W critically reduced.

As an example we consider the Artin group

⟨a, b, c | aba = bab, aca = cac, bcbc = cbcb⟩,

for which we have m_{12} = m_{13} = 3, m_{23} = 4, with the generators in the order

a < a^{−1} < b < b^{−1} < c < c^{−1}.

The word w_{1} = a^{−1}bac^{−1}bcaba is not in W. It contains a critical subword a^{−1}ba, and application of a τ-move to that subword sparks off a rightward length reducing sequence:

w_{1} = a^{−1}bac^{−1}bcaba → bab^{−1}c^{−1}bcaba → bacbc^{−1}b^{−1}aba
→ bacbc^{−1}ab^{−1}a^{−1}a → bacbc^{−1}ab

The end result bacbc^{−1}ab^{−1} contains no critical subword, and so must be in W.

For the same group, the word w_{2} = cbcab^{−1}ab^{−1}cac^{−1} is not in W. Here cac^{−1} is a critical subword, and application of a τ-move to this sparks off a leftward lex reducing sequence:

w_{2} = cbcab^{−1}ab^{−1}cac^{−1} → cbcab^{−1}ab^{−1}a^{−1}ca → cbcb^{−1}a^{−1}a^{−1}bbca
→ b^{−1}cbca^{−1}a^{−1}bbca

The end result w_{3} = b^{−1}cbca^{−1}a^{−1}bbca contains only one critical subword, b^{−1}cbc. And so the only words that can be reached from w_{3} by sequences of τ-moves are the other words in the sequence above; hence w_{3} must be in W. We display both reductions in Figure ??.

The following is the first of our two main results:

Theorem 3.2. Let G be an Artin group of large type, defined over its standard generating set, and let W be the set of words just defined. Then W is the set of shortlex minimal representatives of the elements of G, and G is shortlex automatic.

The complete proof contains a considerable amount of technical detail, which will be verified later in this section, as the proofs of three subsidiary results, Propositions 3.3, 3.4 and 3.5. But given those three propositions, the proof of the theorem itself is straightforward, and so we give that now.

Proof of Theorem 3.2. The proof divides into two parts. First we show (1) that W is the set of shortlex minimal representatives of the elements of G. Then (2) we verify that W is regular and satisfies the M-fellow traveller property.

We start our proof of (1) by defining a map ρ : A^{∗} → W; we shall verify that application of ρ reduces any word to shortlex minimal form.

First we define ρ(w) = w for all w ∈ W. Note that W is closed under subwords, and contains ϵ, which is therefore fixed by ρ.

Now suppose that w ∈ W, and that g ∈ A, but that wg ∉ W. If wg is not freely reduced, then the free reduction of wg is a prefix of w, and so is in W; we define ρ(wg) to be that prefix. Otherwise we can apply the following result (proof deferred):

Proposition 3.3. Suppose that w ∈ W and g ∈ A is such that wg is freely reduced but wg ∉ W. Then a single rightward length reducing or leftward lex reducing sequence followed by a free reduction in the rightward case can be applied to wg to yield an element of W.

In the first case of the proposition, wg admits a rightward length reducing sequence followed by a free reduction to a representative of wg within W, which we shall call ρ_{1}(wg). In the second case, wg admits a leftward lex reducing sequence to an element of W, which we shall call ρ_{2}(wg). We define ρ(wg) to be ρ_{1}(wg) in the first case, and ρ_{2}(wg) in the second case, assuming that the first case does not also occur.

In each of the three situations just considered it is clear that ρ(wg) is an element of W that represents the same group element as wg, and that ρ(wg) <_{slex} wg.

We can now extend the definition of ρ to the whole of A^{∗} using the recursive rule ρ(wg) = ρ(ρ(w)g) for w ∈ A^{∗}, g ∈ A. Then at most |w| successive reductions reduce w to the element ρ(w) of W, which we call the reduction of w.

We see that ρ(w) =_{G} w, that ρ(w) ≤_{slex} w, for any word w, and hence that the shortlex minimal representative of any element is fixed by application of ρ and so must be in W. To prove (1) we need only to verify that every word in W is shortlex minimal.

Now suppose that w′ is a word over A^{∗} that is not shortlex minimal, and w is the shortlex representative of the group element represented by w′. We can define a chain of words w_{0} = w′, w_{1}, …, w_{k} = w, where, for each i = 0, …, k − 1, w_{i} is transformed to w_{i+1} either by the insertion or deletion of a subword gg^{−1}, for some g ∈ A, or by the replacement of a subword _{m}(a_{i}, a_{j}) by a subword _{m}(a_{j}, a_{i}), for some i ≠ j and m = m_{ij}. That ρ(w_{i}) = ρ(w_{i+1}) is guaranteed by the two results, Proposition 3.4 and Proposition 3.5 (proofs deferred):

Proposition 3.4. ρ(wgg^{−1}) = w, ∀w ∈ W, g ∈ A.

Proposition 3.5. ρ(w_{m_{ij}}(a_{i}, a_{j})) = ρ(w_{m_{ij}}(a_{j}, a_{i})), ∀w ∈ W, 1 ≤ i, j ≤ n.

α  w_{1} u_{1} τ(u_{1}) u′_{1}  w_{2} u_{2} τ(u_{2}) u′_{2}  w_{3} u_{3} τ(u_{3}) u′_{3}  w_{4} u_{4} τ(u_{4}) u′_{4}  w_{k} u_{k} τ(u_{k}) u′_{k}  g^{−1} gβ

Figure 2. Rightward length reducing sequence for w, rewriting w = αw_{1} ⋯ w_{k}β as αu′_{1} ⋯ u′_{k−1}τ(u_{k})β, enabling free reduction of l[τ(u_{k})] = g^{−1} with f[β] = g, and so reduction of w to

αu′_{1} ⋯ u′_{k}suf[β].

It follows that ρ(w′) = ρ(w) = w, and so that w′ ∉ W. This completes the proof of (1). Now it follows from the combination of Proposition 3.3 and Lemma 3.1 that w and ρ(wg)

M-fellow travel for any w ∈ W, g ∈ A. Hence we can describe W as the set of words w for which there is no word w′ with w′ =_{G} w and w′ <_{slex} w that M-fellow travels with w. Using this description of W we can construct a finite state automaton to recognise it; hence W is regular, and we have completed the proof of (2). So G is shortlex automatic.

The verification of the theorem will be complete once the three propositions used in its proof have been verified. Before we embark on these proofs, we shall introduce some more detailed notation for critical sequences and prove some technical results about rightward length reducing and leftward lex reducing sequences.

We start by considering rightward critical sequences. If w admits a rightward critical sequence, then w = αw_{1} ⋯ w_{k}β where:

(i) For 1 ≤ l ≤ k, w_{l} is a word over generators a_{i_{l}}, a_{j_{l}} (ii) For each 1 ≤ l < k, |{i_{l}, j_{l}} ∩ {i_{l+1}, j_{l+1}}| = 1, the name of the final letter of w_{l} is a_{i}

with i ∉ {i_{l+1}, j_{l+1}}, and the name of the first letter of w_{l+1} is a_{j} with j ∉ {i_{l}, j_{l}}. We call αw_{1} ⋯ w_{k}β a rightward critical factorisation of w, with factors w_{1}, w_{2}, …, w_{k}, and first term w_{1}.

The chain of τ-moves transforms w through the sequence of words

w = αw_{1}w_{2} ⋯ w_{k}β = αu_{1}w_{2} ⋯ w_{k}β,
ατ(u_{1})w_{2} ⋯ w_{k}β,
αpre[τ(u_{1})]τ(l[τ(u_{1})]w_{2})w_{3} ⋯ w_{k}β = αu′_{1}τ(u_{2})w_{3} ⋯ w_{k}β,
αpre[τ(u_{1})]pre[τ(u_{2})]τ(l[τ(u_{2})]w_{3}) ⋯ w_{k}β = αu′_{1}u′_{2}τ(u_{3}) ⋯ w_{k}β,
…,
αpre[τ(u_{1})]pre[τ(u_{2})] ⋯ pre[τ(u_{k−1})]τ(u_{k})β = αu′_{1}u′_{2} ⋯ u′_{k−1}τ(u_{k})β,

where we define u_{1} = w_{1}, u_{l} = l[τ(u_{l−1})]w_{l} for 1 < l ≤ k, and u′_{l} = pre[τ(u_{l})] for 1 ≤ l ≤ k. We notice that |w_{1}| = |u_{1}| = |u′_{1}| + 1, and for l > 1 |w_{l}| = |u′_{l}| = |u_{l}| − 1.

This sequence is length reducing when l[τ(u_{k})] = f[β]^{−1}, and in this case we call the letter f[β] the tail of the sequence. Then the free reduction of the final word in the sequence is

αu′_{1}u′_{2}u′_{3} ⋯ u′_{k}suf[β]

Figure 1 illustrates a rightward length reducing sequence.

When a sequence of this type reduces a word of the form wg with w ∈ W, then β must be the single letter g, and then the tail is g too, and the whole of β.

From now on, whenever a word w has a rightward critical factorisation αw_{1} ⋯ w_{k}β as above, we will use the labels u_{1}, …, u_{k}, u′_{1}, …, u′_{k} for subwords of w and its reductions through the rightward length reducing sequence just as above. (And similarly, we shall define words ū_{1}, … ūk̄

β w_{1} u_{1} τ(u_{1}) u′_{1} w_{2} u_{2} τ(u_{2}) u′_{2} w_{3} u_{3} τ(u_{3}) u′_{3} w_{4} u_{4} τ(u_{4}) u′_{4} w_{k} u_{k} τ(u_{k}) α
Figure 3. Leftward lex reducing sequence, reducing w = αw_{k} ⋯ w_{1}β to ατ(u_{k})u′_{k−1} ⋯ u′_{1}β

and ū′_{1}, … ū′ ; k̄ as labels for subwords associated with a rightward critical factorisation of a word ᾱw̄_{1} ⋯ w̄k̄β̄.)

Now we consider leftward critical sequences. If w admits a leftward critical sequence then we can write w = αw_{k} ⋯ w_{1}β where:

(i) For 1 ≤ l ≤ k, w_{l} is a word over generators a_{i_{l}}, a_{j_{l}} (ii) For each 1 ≤ l < k, |{i_{l}, j_{l}} ∩ {i_{l+1}, j_{l+1}}| = 1, the name of the final letter of w_{l+1} is a_{i}

with i ∉ {i_{l}, j_{l}}, and the name of the first letter of w_{l} is a_{j} with j ∉ {i_{l+1}, j_{l+1}}. We call αw_{k} ⋯ w_{1}β a leftward critical factorisation of w, with factors w_{1}, w_{2}, …, w_{k}, and first term w_{1}.

The chain of τ moves transforms w through the sequence of words

w = αw_{k} ⋯ w_{2}w_{1}β = αw_{k} ⋯ w_{2}u_{1}β,
αw_{k} ⋯ w_{2}τ(u_{1})β,
αw_{k} ⋯ w_{3}τ(w_{2}f[τ(u_{1})])suf[τ(u_{1})]β = αw_{k} ⋯ w_{3}τ(u_{2})u′_{1}β,
αw_{k} ⋯ τ(w_{3}f[τ(u_{2})])suf[τ(u_{2})]suf[τ(u_{1})]β = αw_{k} ⋯ τ(u_{3})u′_{2}u′_{1}β,
…,
ατ(u_{k})suf[τ(u_{k−1})] ⋯ suf[τ(u_{2})]suf[τ(u_{1})]β = ατ(u_{k})u′_{k−1} ⋯ u′_{2}u′_{1}β

where we define u_{1} = w_{1}, u_{l} = w_{l}f[τ(u_{l−1})] for 1 < l ≤ k, and u′_{l} = suf[τ(u_{l})] for 1 ≤ l < k. (We don’t need to define u′_{k} in this case.) We notice that |w_{1}| = |u_{1}| = |u′_{1}| + 1, and for l > 1 |w_{l}| = |u′_{l}| = |u_{l}| − 1.

The sequence is lex reducing when f[τ(u_{k})] is earlier in the lexicographic order of generators than f[w_{k}],

Figure 2 illustrates the leftward critical sequence.

From now on, whenever a word w has a leftward critical factorisation αw_{k} ⋯ w_{1}β as above, we will use the labels u_{1}, …, u_{k}, u′_{1}, …, u′_{k−1} for subwords of w and its reductions through a leftward lex reducing sequence as defined above. (And similarly, we shall define words ū_{1}, … ūk̄ and ū′_{1}, … ū′_{k̄−1} as labels for subwords associated with a leftward critical factorisation of a word w̄ = ᾱw̄k̄ ⋯ w̄_{1}β̄.)

Of course this notation is analogous to that used for rightward critical factorisations, but with some differences; these should not cause problems, since it will always be clear which type of factorisation is being considered.

The following four technical results are used in the proofs of the three propositions, Propositions 3.3, 3.4 and 3.5.

Lemma 3.6. Suppose that wg admits a rightward length reducing sequence, with corresponding factorisation αw_{1} … w_{k}g of wg, and notation as above. Then the 2-generator suffix w_{k}g of wg satisfies p(w_{k}g) + n(w_{k}g) ≥ m, and hence contains a critical subword.

Proof. Since τ(u_{k})g is not freely reduced, it is not 2-geodesic and hence neither is u_{k}g. So p(u_{k}g) + n(u_{k}g) > m, and hence p(suf[u_{k}]g) + n(suf[u_{k}]g) ≥ m. Since suf[u_{k}] = w_{k} when k > 1, while w_{1} = u_{1}, the result now follows immediately.

We call a rightward length reducing sequence for wg optimal if the left hand end of w_{1} is further right in w than in any other such factorisation. We call a leftward lex reducing sequence for wg optimal if the left hand end of w_{k} is further left in w than in any other such factorisation.

Lemma 3.7. Suppose that wg admits an optimal rightward length reducing sequence, with corresponding factorisation αw_{1} ⋯ w_{k}g of wg, and notation as above. Then for each l with 1 ≤ l ≤ k:

(1) No proper suffix of u_{l} is critical; hence u_{l} either has the form _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with p > 0 or the form _{n}(x^{−1}, y^{−1})ξ(z, t)_{p} with n > 0, and {x, y} = {z, t} = {a_{i_{l}}, a_{j_{l}}}.

(2) u′_{l} involves both of the generators a_{i_{l}} and a_{j_{l}}.

(3) p(u′_{l}) + n(u′_{l}) < m.

(4) When l > 1, u′_{l} begins with a letter whose name is not in {a_{i_{l−1}}, a_{j_{l−1}}}.

(5) When l < k, each u′_{l} ends with a letter whose name is not in {a_{i_{l+1}}, a_{j_{l+1}}} and u′_{k} ends with a letter with a different name from g.

(6) When k > 1, w_{2}, …, w_{k}g are maximal 2-generator subwords of wg, and u′_{2}, …, u′_{k} are maximal 2-generator subwords of its reduction αu′_{1} ⋯ u′_{k}.

(7) If αu′_{1} ⋯ u′_{k} admits a further left lex reducing or right length reducing sequence, then all of the factors of that sequence, as well as its tail when length reducing, are contained within αu′_{1}.

Proof. The fact (1) that no proper suffix of any u_{l} is critical follows from the optimality of the chosen sequence. For if u_{0} is a proper suffix of u_{l} that is critical, then τ(u_{0}), like τ(u_{l}), is critical, and Corollary 2.2 tells us that τ(u_{0}) ends in the same letter as τ(u_{l}), and hence also has critical overlap with w_{l+1}. Since u_{0} is also a suffix of w_{l}, α′u_{0}w_{l+1} ⋯ w_{k}g is the factorisation associated with a rightward length reducing sequence for wg, where α′ = αw_{1} ⋯ w_{l−1}w_{0}, for some prefix w_{0} of w_{l}, and the optimality of the chosen sequence is contradicted.

Once it is clear that u_{l} has no critical suffix it is immediate that it has one of the two given forms. From now on we shall assume that it has the first form _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with p > 0.

(2) is clear except possibly when m = 3 and p = 2, n = 1 with u_{l} = xyξy^{−1}. But in that case, ξ is nonempty and cannot start with x or end with x^{−1}, so ξ must involve the generator y and then pre[τ(u_{l})] involves both x and y. So (2) holds. (But note that (2) would not necessarily hold when m = 2, so we are using the largeness assumption here.)

If p(suf[u_{l}]) + n(suf[u_{l}]) ≥ m then either suf[u_{l}] itself or some suffix of it is critical (since u_{l} is already critical), and we have already excluded this possibility. Hence p(suf[u_{l}]) + n(suf[u_{l}]) < m, so p(pre[τ(u_{l})]) + n(pre[τ(u_{l})]) < m and (3) holds.

(4) follows immediately from the fact that the first letters of the critical words u_{l} and τ(u_{l}) have different names.

Since pre[τ(u_{l})] ends with (z, t)_{p−1}, we see that (5) holds except possibly when p = 1 and n = m − 1. In that case, p(suf[u_{l}]) < p (which follows from (3)) implies that ξ is either empty or a negative word. If ξ is empty, then pre[τ(u_{l})] must end with t^{−1} or else τ(u_{l}) would not be freely reduced. Otherwise, the the last letter of ξ must be the same as the first letter of (z^{−1}, t^{−1})_{n} (since otherwise we would have a longer negative alternating word), and hence, for both odd and even m, l[δ(ξ)] = t^{−1}, so (5) holds in all cases.

(6) follows immediately from (4) and (5).

For (7) we may assume that k > 1, or there is nothing to prove. (3) implies that none of u′_{2}, …, u′_{k} can contain critical subwords. Since they are maximal 2-generator subwords within wg their concatenation cannot contain or intersect any critical subword (where we have once again used the largeness condition). Now the first term of any further reducing sequence is critical so must be disjoint from the suffix u′_{2} ⋯ u′_{k} of the reduction of wg. If that sequence is leftward then this implies that the whole sequence is to the left of the suffix u′_{2} ⋯ u′_{k}. If it is rightward length reducing then Lemma 3.6 tells us that its rightmost factor must contain a critical subword, hence cannot intersect the suffix u′_{2} ⋯ u′_{k} and must be to its left. Hence (7) is proved.

Lemma 3.8. Suppose that wg admits a leftward lex reducing sequence, with corresponding factorisation αw_{k} ⋯ w_{1} of wg, and notation as above, and that w admits no leftward lex reducing sequence. Then for each l with 1 ≤ l ≤ k:

(1) No proper prefix of u_{l} is critical; hence u_{l} either has the form _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with n > 0 or the form _{n}(x^{−1}, y^{−1})ξ(z, t)_{p} with p > 0, where {x, y} = {z, t} = {a_{i_{l}}, a_{j_{l}}}.

(2) u′_{l} involves both of the generators a_{i_{l}} and a_{j_{l}} when l < k.

(3) p(u′_{l}) + n(u′_{l}) < m when l < k.

(4) When l < k, u′_{l} begins with a letter whose name is not in {a_{i_{l+1}}, a_{j_{l+1}}}.

(5) When 1 < l < k, u′_{l} ends with a letter whose name is not in {a_{i_{l−1}}, a_{j_{l−1}}}, and u′_{1} ends with a letter with a different name from g.

(6) When k > 1, w_{1}, … w_{k−1} are maximal 2-generator subwords of wg. and u′_{1}, … u′_{k−1} are maximal 2-generator subwords of its reduction ατ(u_{k}) ⋯ u′_{1}.

(7) If ατ(u_{k}) ⋯ u′_{1} admits a further left lex reducing or right length reducing sequence, then all of the factors of that sequence, as well as the tail if it is length reducing, are contained within ατ(u_{k}).

Proof. This is very similar to the previous proof, so we shall omit it.

Note, however, that in (1) the fact that u_{l} has no critical prefix follows from the lack of a left lex reducing sequence for w.

In the proof of (7) we consider of course the suffix

u′_{k−1} ⋯ u′_{2}u′_{1}

of the reduction; otherwise the argument is identical.

Lemma 3.9. Suppose that w admits a rightward critical sequence with corresponding factorisation αw_{1} ⋯ w_{k}, and whose application to w transforms it to a word ending in g. Let ζ be a non 2-geodesic 2-generator word with f[ζ] = g, for which suf[ζ] is 2-geodesic, and suppose that wsuf[ζ] is freely reduced. Then the given sequence for w extends to a rightward length reducing sequence for wsuf[ζ] of length k + 1.

Proof. ζ is not 2-geodesic but some non-empty prefix of it is. Applying Lemma 2.3 to a maximal such prefix, we can deduce that ζ contains a critical subword θ, such that replacement within ζ of θ by τ(θ) gives a word with free cancellation between the last letter of τ(θ) and the next letter of ζ. Since suf[ζ] is geodesic, this substitution cannot happen with suf[ζ], and hence θ must be a prefix of ζ. So θ = gw_{k+1}, where w_{k+1} is a prefix of suf[ζ]. Now αw_{1} ⋯ w_{k}w_{k+1}β is a rightward critical factorisation for wsuf[ζ]. The final application of τ (to θ) in the corresponding critical sequence sparks a free reduction at the right hand end of θ, and hence this sequence is length reducing.

We are now ready to prove our three propositions.

Proof of Proposition 3.3. Since w ∈ W and wg ∉ W, it follows from the definition of W that one of the following two possibilities occurs:

Case 1 wg admits a rightward length reducing sequence enabling the free cancellation of the final g.

Case 2 wg admits a leftward lex reducing sequence but no rightward length reducing sequence.

In each of the two cases we need to eliminate the possibilities that either (a) the reduction of wg admits a rightward length reducing sequence, or (b) the reduction of wg admits a leftward lex reducing sequence. We use the notation for rightward and leftward reducing sequences that was established above.

In Case 1, we choose an optimal rightward length reducing sequence of wg, with corresponding factorisation αw_{1} ⋯ w_{k}g; recall that we call the word resulting from this reduction ρ_{1}(wg). In Case 2, we choose an optimal leftward lex reducing sequence of wg, with corresponding factorisation αw_{k} ⋯ w_{1}; recall we call the word resulting from this reduction ρ_{2}(wg). Note that we have defined ρ(wg) to be ρ_{1}(wg) in Case 1, and ρ_{2}(wg) in Case 2.

We shall see that in Case (1), if ρ_{1}(wg) admits either a rightward or leftward reducing sequence, then the same is true of w, while in Case (2), if ρ_{2}(wg) admits a rightward reducing sequence, then so does wg (and so in fact we are in case (1)), and if ρ_{2}(wg) admits a leftward reducing sequence then either the same is true of w or wg admits a leftward reducing sequence whose left hand end is further left than in the previously chosen sequence for wg, contradicting its optimality. The details of thise argument now follow.

Case 1(a):

Suppose that we are in Case 1 and that ρ(wg) = ρ_{1}(wg) admits a rightward length reducing sequence with associated factorisation βw̄_{1} ⋯ w̄k̄hγ, where h is the tail, which cancels after application of the τ-moves to ρ(wg).

Since w is in W and hence cannot admit a rightward length reducing sequence, the subword w̄_{1} ⋯ w̄k̄h of ρ(wg) cannot be a subword of w. Hence it has some intersection with the suffix u′_{1} ⋯ u′_{k} of ρ(wg). However, Lemma 3.7 (7) tells us that it is contained within αu′_{1}. So the 2generator subword w̄k̄h has some intersection with u′_{1}, but by Lemma 3.7(6) any other factors of this sequence are to the left of u′_{1} in ρ(wg). If k̄ > 1, w̄k̄ starts no later than f[u′_{1}], but if k̄ = 1, w̄_{1} may start within u′_{1}.

We eliminate first the case k̄ = 1. We define η to be the 2-generator subword of ρ(wg) that starts at the beginning of w̄_{1} and ends at the right hand end of u′_{1}. Then we define ζ be the 2-generator subword of w that starts at the beginning of w̄_{1} if that is within α, or otherwise at the beginning of w_{1}, and ends at the right hand end of w_{1}. Since the application of a τ-move to w̄_{1} sparks a free reduction with the following letter in u′_{1}, η cannot be 2-geodesic and, since η is a subword of a word obtained by applying a τ-move to ζ, neither is ζ. But ζ is a subword of w, so we contradict w ∈ W.

So now we assume that k̄ > 1. Then βw̄_{1} ⋯ w̄_{k̄−1} is a rightward critical factorisation of length k̄ − 1 of a word that is also a prefix of w. We shall now show how to extend this to yield a rightward length reducing sequence of length k̄ for w, thereby contradicting w ∈ W.

Let v̄ be the word that is derived from ρ(wg) by applying the k̄ − 1 τ-moves of this rightward critical sequence of length k̄ − 1. Then (using the notation we have already established for a rightward critical factorisation of w̄)

v̄ = βū′_{1}ū′_{2} ⋯ ū′_{k̄−1}ūk̄hγ.

[figure: wg, ρ(wg); v, v̄; w̄_{k̄−1}; ū_{k̄−1}; τ(ū_{k̄−1}); ū′_{k̄−1}; w̄k̄; ūk̄; τ(ūk̄); w_{1}; u_{1}; τ(u_{1}); u′_{1}; w_{2}; u_{2}; τ(u_{2}); u′_{2}]

Figure 4. Collision between two rightward sequences.

Let v be the word that is derived from w by applying the same sequence of k̄ − 1 moves. Then v and v̄ share a prefix that includes

βū′_{1}ū′_{2} ⋯ τ(ū_{k̄−1}).

Figure 3 illustrates this situation. In the figure we can trace out the paths of wg, ρ(wg), v̄, v. All four paths pass through the circled vertex; wg and ρ(wg) come into the circled vertex along the upper route along w̄_{k̄−1} and part of w̄k̄, while v and v̄ follow the lower route along τ(ū_{k̄−1}) and part of w̄k̄. The paths of wg and v leave the circled vertex along w_{1}, while those of ρ(wg) and v̄ leave along u′_{1}.

Now let η be the 2-generator subword of v̄ that starts at the beginning of ūk̄ and ends at the right hand end of u′_{1}. Let ζ be the 2-generator subword of v that starts at the beginning of ūk̄ and ends at the right hand end of u_{1}. The subwords ζ and η are marked in bold in the figure.

The first letter of both η and ζ is the last letter of τ(ū_{k̄−1}). Since the final move in the rightward length reducing sequence for ρ(wg) sparks a free reduction, η is not 2-geodesic, and since η is a subword of a word derived from ζ by applying a τ-move to a suffix, neither is ζ. The subword suf[ζ] of w must be 2-geodesic, for otherwise Theorem 2.4 tells us that suf[ζ] is not in W, and hence neither is w, and we have a contradiction. So now we can apply Lemma 3.9 to deduce the existence of a rightward length reducing sequence of length k̄ for the prefix βw̄_{1}w̄_{2} ⋯ w̄_{k̄−1}suf[ζ] of w, contradicting the fact that w ∈ W.

Case 1(b):

Next suppose that we are in Case 1 and that ρ(wg) = ρ_{1}(wg) admits a leftward lex reducing sequence with associated factorisation βw̄k̄ ⋯ w̄_{1}γ. Applying Lemma 3.7(7) we see that w̄_{1} is contained within αu′_{1} in ρ(wg). Since w is in W and so cannot admit a leftward lex reducing sequence, w̄_{1} cannot be contained within α, but must end within u′_{1}.

Now we assume that w_{1} = u_{1} = _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with p(w_{1}) + n(w_{1}) = m for the appropriate m, and τ(u_{1}) = _{n}(x^{−1}, y^{−1})δ(ξ)(t, z)_{p}. (We omit the argument that excludes the other choice for w_{1} of Lemma 3.7 (1), which is very similar.) By Lemma 3.7 (1), we have p > 0.

Now since the chosen factorisation of wg is optimal, no proper suffix of u_{1} is critical, and so p(suf[u_{1}]) < p and hence p(pre[τ(u_{1})]) < p; that is, p(u′_{1}) < p. Hence if π is the positive alternating subword of length p at the beginning or end of w̄_{1}, π cannot be a subword of u′_{1} and so must intersect α.

If n > 0, then u′_{1} begins with a negative alternating subword, and so π is contained within α. In this case we define w̄′_{1} to be the subword of w that starts at the beginning of π and ends at the end of w_{1}. If n = 0, then by Lemma 3.8 (1) we can assume that π lies at the right hand end of w̄_{1}, and so it must intersect u′_{1}, and hence the prefix δ(ξ) of u′_{1} (since it also intersects α). In this case we define w̄′_{1} to be the subword of w that starts at the beginning of π and ends at the end of the prefix _{p}(x, y) of w_{1}. Either way, w̄′_{1} is a critical subword of w, and βw̄k̄ ⋯ w̄_{2}w̄′_{1} is a factorisation of a prefix of w (either αw_{1} or a prefix of that) corresponding to a leftward reducing sequence for that prefix. This contradicts the fact that w ∈ W.

This completes the analysis of Case 1, so now suppose that we are in Case 2.

Case 2(a):

The possibility that we are in Case 2, and that ρ_{2}(wg) admits a rightward length reducing sequence is excluded by the following result, which we state as a separate lemma since we shall also use it in the proof of Proposition 3.4:

Lemma 3.10. Suppose that w ∈ W, and that wg admits an optimal leftward lex reducing sequence with associated factorisation wg = αw_{k} ⋯ w_{1}, leading to

ρ_{2}(wg) = ατ(u_{k})u′_{k−1} ⋯ u′_{3}u′_{2}u′_{1}.

Then ρ_{2}(wg) admits a rightward length reducing sequence if and only if wg admits a rightward length reducing sequence.

We apply the lemma (whose proof we defer until the end of the proof of this proposition) to deduce that in this case wg must also admit a rightward length reducing sequence, a possibility that we have excluded from Case 2.

Case 2(b):

So now suppose that we are in Case 2 and that ρ(wg) = ρ_{2}(wg) admits a leftward lex reducing sequence with associated factorisation βw̄k̄ ⋯ w̄_{1}γ. Lemma 3.8 (7) tells us that the subword w̄_{1} is a subword of ατ(u_{k}) within ρ(wg). Since w ∈ W, w̄_{1} cannot be a subword of α and so w̄_{1} must end within τ(u_{k}).

We suppose that u_{k} = _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with p(u_{k}) + n(u_{k}) = m for the appropriate m, and τ(u_{k}) = _{n}(x^{−1}, y^{−1})δ(ξ)(t, z)_{p} (We omit the other case dealing with the other possibility for u_{k} of Lemma 3.8 (1), which is similar.) By Lemma 3.8 (1), we have n > 0. Let ν be the negative alternating sequence of length n at the beginning or end of w̄_{1}. and let ν′ be the subword _{n}(x^{−1}, y^{−1}) of τ(u_{k}).

We claim that ν′ must be the unique negative alternating subword of length n in τ(u_{k}). If p = 0, then this is true by definition of critical words for negative words. If p > 0 and there there was another such subword, then it would necessarily lie entirely within δ(ξ), in which case ξ would also contain such a subword, and then a prefix of the subword _{p}(x, y)ξ of w would be upper critical. The application of τ to this prefix would give w a leftward lex reducing sequence of length 1, contradicting w ∈ W. Hence in this case too the claim is proved.

Suppose first that p > 0.

If ν ≠ ν′ then, by the preceding paragraph, ν lies to the left of ν′ and hence to the left of τ(u_{k}), at the beginning of w̄_{1}, within α. Now we define w̄′_{1} to be the subword of αu_{k} that runs from the beginning of ν to the end of the prefix _{p}(x, y) of u_{k}, and find a leftward lex reducing sequence for w with associated factorisation βw̄k̄ ⋯ w̄_{2}w̄′_{1}γ′, contradicting w ∈ W.

So we suppose that ν = ν′. If ν is at the beginning of w̄_{1}, then τ(w̄_{1}) has the same prefix p(x, y) as u_{k} and then τ(u_{k}) <_{lex} u_{k} implies w̄_{1} <_{lex} τ(w̄_{1}), so we must have k̄ > 1. But then then also f[τ(w̄_{1}] = f[u_{k}] = f[w_{k}] and so βw̄k̄ ⋯ w̄_{2}f[τ(w̄_{1})] = βw̄k̄ ⋯ w̄_{2}f[w_{k}] is a prefix of αw_{k} and hence of w. Then, where w̄′_{2} = w̄_{2}f[w_{k}], the factorisation βw̄k̄ ⋯ w̄′_{2} of that prefix is associated with a leftward lex reducing sequence that also reduces w, contradicting w ∈ W.

On the other hand if ν is at the right hand end of w̄_{1}, then w̄_{1} = w′_{1}ν. Then there is a leftward lex reducing sequence of wg with factorisation βw̄k̄ ⋯ w̄_{2}w̄′_{1}w_{k−1} ⋯ w_{1} in which w̄′_{1} = w′_{1}w_{k}. This extends further left that the chosen factorisation, contrary to assumption.

If p = 0 then by Lemma 3.8 (1) applied to the shortest prefix of ρ(wg) that is not in W, ν must be at the right hand end of w̄_{1}, and again wg has a leftward reducing sequence that extends further left than the chosen one, giving a contradiction as before.

[figure: wg, ρ_{2}(wg); v, v̄; w̄_{k̄−1}; ū_{k̄−1}; τ(ū_{k̄−1}); ū′_{k̄−1}; w̄k̄; ūk̄; τ(ūk̄); w_{1}; u_{1}; τ(u_{1}); h; ζ; η]

Figure 5. Part (a). Induction, case k = 1.

To complete the proof of Proposition 3.3. we need the proof of Lemma 3.10.

Proof of Lemma 3.10. We prove first (a) that if ρ_{2}(wg) admits a rightward length reducing sequence then wg admits one too, and then (b) that if wg admits a rightward length reducing sequence, then so does ρ_{2}(wg).

Proof of (a):

Suppose that ρ_{2}(wg) has a rightward length reducing sequence with associated factorisation βw̄_{1} ⋯ w̄k̄hγ, where the generator h cancels after application of the τ-moves to w̄ := w̄_{1} ⋯ w̄k̄. Then by Lemma 3.8 (7) w̄k̄h is a subword of ατ(u_{k}). If it were also a subword of α, we would have a rightward length reducing sequence for w, contradicting the fact that w ∈ W. Hence w̄k̄h must end within τ(u_{k}). But by Lemma 3.8(6) any other factors of this sequence must be within α.

The proof is now by induction on k.

Base case. Suppose that k = 1.

In the case where k̄ = 1, we define η to be the maximal 2-generator subword of ρ(wg) that contains w̄_{1}h. Since the application of a τ-move to w̄_{1} enables a free reduction, η cannot be 2-geodesic. Hence neither is ζ, the 2-generator subword of w which is mapped to η by applying a τ-move to a subword. So ζ admits a right length reducing sequence of length 1, and hence so does wg.

So now we shall assume that k̄ is not 1. Let v̄ be the word obtained from ρ_{2}(wg) by applying the first k̄ − 1 terms of its rightward length reducing sequence, and let v be the word obtained by applying the same sequence of moves to wg.

Figure 4 illustrates this situation. The circled vertex marks the end of the common prefix of v, v̄. The subwords ζ and η (defined below) are marked in bold in the figure.

Let η be the 2-generator suffix of v̄ that starts at the left hand end of ūk̄h. The final τ-move of the rightward sequence, which is applied to the prefix ūk̄ of η, enables a free reduction, so η is not 2-geodesic. So the word ζ obtained by replacing the subword τ(u_{1}) in η by u_{1} is also not 2-geodesic. Now we can apply Lemma 3.9 to get a rightward length reducing sequence for wg = βw̄_{1}w̄_{2} ⋯ w̄_{k̄−1}suf[ζ].

Inductive step. Suppose that k > 1. Fig 5 illustrates this part of the proof.

Let w′ be the prefix αw_{k} ⋯ w_{2} of w; as a prefix of w it must be in W. Let g′ := f[τ(w_{1})] = f[τ(u_{1})]. The word αw_{k} ⋯ w_{2}τ(w_{1}) is the result of the first of the k steps of the leftward reduction of wg, and so admits a leftward lex reducing sequence of length k − 1; the same leftward lex reducing sequence of length k − 1 reduces w′g′ (as a prefix of the above) to a prefix ρ_{2}(w′g′) of ρ_{2}(wg).

w_{1} u_{1} g′ τ(u_{1}) u′_{1} w_{2} u_{2} τ(u_{2}) u′_{2} w_{3} u_{3} τ(u_{3}) u′_{3} w_{4} u_{4} τ(u_{4}) w_{k} u_{k} τ(u_{k}) α  w′

Figure 6. Part (a), Inductive step.

Now the rightward length reducing sequence that we have for ρ_{2}(wg) stops within the τ(u_{k}) subword, and so certainly to the left of the final suffix suf[τ(w_{1})] of ρ_{2}(wg); hence ρ_{2}(w′g′) admits a rightward length reducing sequence.

Now we can apply the induction hypothesis to w′g′ to deduce that w′g′ admits a rightward length reducing sequence. Since w′ ∈ W, the last factor of the associated factorisation is a suffix of w′g′. The sequence transforms w′g′ to a word w′′g′, where l[w′′] is the inverse of g′. The same rightward critical sequence can be applied to w = w′w_{1}, which it transforms to w′′w_{1}. Finally, we consider the suffix ζ = g′^{−1}w_{1} of w′′w_{1}. Since g′^{−1}τ(w_{1}) is not freely reduced, it is not 2-geodesic, and hence neither is ζ. Now, just as in the k = 1 case we can apply Lemma 3.9 to find a rightward length reducing sequence for wg.

Proof of (b):

Now suppose that wg admits a rightward length reducing sequence. Again we use induction on k.

Base case. When k = 1 the proof is very similar to the k = 1 case above. We just interchange the roles of u_{1} = w_{1} and τ(u_{1}). But we observe that in this case the tail of the factorisation of wg must be the final g, since w ∈ W.

Inductive step. Now suppose that k > 1. In this case by Lemma 3.8 w_{1},… w_{k−1} are maximal 2-generator words and geodesic.

Suppose that wg admits a rightward length reducing sequence of length k̄. This cannot apply to w, since w ∈ W. It cannot have length 1. For if it did, it would apply to the suffix w_{1}, which is geodesic. So k̄ > 1 and the (k̄ − 1)-th τ-move must change l[w_{2}] to a letter h, say, where hw_{1} is not 2-geodesic. But then, by Lemma 2.3, w_{1} must have a critical prefix v_{1} such that τ(v_{1}) begins with h^{−1}; the possibility that f[w_{1}] = h^{−1} is excluded by the fact that w ∈ W. But in fact for any critical prefix v_{1} of w_{1}, f[τ(v_{1})] = f[τ(w_{1})], and so we have g′ := f[τ(w_{1})] = h^{−1}. So the first k̄ − 1 moves of the rightward length reducing sequence of wg also induce a rightward length reducing sequence of w′ := αw_{k} ⋯ w_{2}g′. But w′ admits a leftward lex reducing sequence of length k − 1, and so we can now apply our inductive hypothesis to conclude that ρ_{2}(w′) admits a rightward length reducing sequence. The result immediately follows since

ρ_{2}(w′) = ρ_{2}(αw_{k} ⋯ w_{2}g′) = ατ(u_{k})u′_{k−1} ⋯ u′_{3}u′_{2}

is a prefix of ρ_{2}(wg).

Proof of Proposition 3.4. This is immediate except in the case when wg is freely reduced but wg ∉ W, in which case ρ(wg) is defined as in the proof of Proposition 3.3, and we use the same notation as in that proof.

First we suppose that ρ(wg) = ρ_{1}(wg). In this case wg admits a factorisation αw_{1} … w_{k}g, corresponding to a rightward length reducing sequence. The sequence of τ moves transforms w to w′ := αu′_{1}u′_{2} ⋯ u′_{k−1}τ(u_{k}) using our standard notation associated with a rightward factorisation of wg, with τ(u_{k}) ending in g^{−1}. Then the final g^{−1} is cancelled to produce ρ(wg) = αu′_{1}u′_{2}u′_{3} ⋯ u′_{k}. So ρ(wg)g^{−1} = w′. Hence to complete consideration of this case, we need to show that ρ(w′) = w.

It follows from Lemma 3.7 (4) and (5), that reversing the τ-moves in the rightward length reducing sequence for wg results in a leftward lex reducing sequence S that transforms w′ back to w. Our next step is to show that S is optimal.

So let S′ be the optimal lefward lex reducing sequence for w′, that is the leftward lex reducing sequence for w′ that extends furthest to the left in w′. Then S′ involves at least k τ-moves, and the first k − 1 of those must match the first k − 1 τ-moves of S, since those must correspond to τ(u_{k}), u′_{k−1}, …, u′_{2}, defined as maximal 2-generator subwords of w′ (as in Lemma 3.8 (6)). These first k − 1 moves transform w′ back to ατ(u_{1})w_{2} ⋯ w_{k}. Suppose that u_{1} = _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with p + n = m for the appropriate m, and τ(u_{1}) = n(x^{−1}, y^{−1})δ(ξ)(t, z)_{p} (the other case is similar) where, by Lemma 3.7 (1), p ≠ 0. If the next τ-move in S′ transforms τ(u_{1}) back to u_{1}, then we are back to w, and any further τ-moves in S′ could have been applied to w, contradicting w ∈ W. Now if S′ extends further left than S, the next τ-move in S′ must apply to a word βτ(u_{1}) having τ(u_{1}) as a proper suffix. Since βτ(u_{1}) is critical, β (like τ(u_{1})) must have a negative alternating word of length n as a prefix. But in that case β_{p}(x, y) must also be critical, and is a subword of w. So this τ-move followed by any remaining moves in the sequence S′ is a leftward lex reducing sequence for w, contradicting w ∈ W. Hence S is indeed the optimal leftward lex reducing sequence that reduces w′ to w, that is ρ_{2}(w′) = w.

Now we can apply Lemma 3.10 to see that if w′ can also be reduced using a rightward length reducing sequence, then w = ρ_{2}(w′) must also admit such a sequence. But this would contradict w ∈ W. Hence w′ admits no such reduction, and so we must have ρ(w′) = ρ_{2}(w′) = w as required.

Now we suppose that ρ(wg) = ρ_{2}(wg). In that case we have a factorisation wg = αw_{k} ⋯ w_{1} of wg corresponding to a leftward lex reducing sequence for of wg to

ρ(wg) = ατ(u_{k})u′_{k−1} ⋯ u′_{2}u′_{1}.

Reversing these τ-moves results in a rightward length reducing sequence S for ρ(wg)g^{−1}, and we need to verify that there is no alternative rightward length reducing sequence S′ for ρ(wg)g^{−1} that starts further to the right than S. By Lemma 3.8 (7), such a sequence would have to start to the left of u′_{k−1}, and so the factorisation would have the form

αβu′′_{k}u′_{k−1} ⋯ u′_{2}u′_{1}

with βu′′_{k} = τ(u_{k}) and β nonempty. Let u_{k} = _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with p + n = m for the appropriate m, and τ(u_{k}) = _{n}(x^{−1}, y^{−1})δ(ξ)(t, z)_{p} (the other case being similar) where, by Lemma 3.8 (1), n ≠ 0. If p > 0, then n(δ(ξ)) = n(ξ) = n, in which case the subword _{p}(x, y)ξ of w contains an upper critical subword, contradicting w ∈ W. The case p = 0 is ruled out by the definition of critical words in this case, which requires that τ(u_{k}) contains a unique negative alternating subword of length n.

Proof of Proposition 3.5. To ease the notation, let a = a_{i}, b = a_{j}, where we may assume that a <_{lex} b, and m = m_{ij}. We consider the 2-generator Artin group DA(m) = ⟨a, b | _{m}(a, b) = m(b, a)⟩. Our general strategy is to show that in every situtation, in the course of the computation of ρ(w_{m}(a, b)) by appending each letter of _{m}(a, b) in turn to w, at most one such appended letter will precipitate a leftward lex reduction or a rightward length reduction of the resulting word. All other appended letters result either in no reduction, or in the cancellation of the appended letter by free reduction. In general, a similar leftward or rightward reduction (if any) is involved in the computation of ρ(w_{m}(b, a)), and we then apply Theorem 2.4 to DA(m) to infer the result.

The result is clear if w is empty or if w is a power of a letter whose name is not a or b, for in these cases we have ρ(w_{m}(a, b)) = ρ(w_{m}(b, a)) = w_{m}(a, b).

Suppose that the name of l[w] is c, with c ∉ {a, b}.

If w does not have the form w′v with v a 2-generator word involving a, c or b, c, then again ρ(w_{m}(a, b)) = ρ(w_{m}(b, a)) = w_{m}(a, b). So from now on we assume that w = w′v where v involves a and c (the other case is similar). In this case, if ρ(wa) = wa then ρ(w_{m}(a, b)) = ρ(w_{m}(b, a)) = w_{m}(a, b). So we suppose that ρ(wa) ≠ wa.

Now we have the usual two cases for ρ(wa). In either case, by Lemmas 3.7 (5) and 3.8 (5), the name of the final letter of ρ(wa) is c, so

ρ(w_{m}(a, b)) = ρ(wa)_{m−1}(b, a).

Note also that ρ(w_{m−1}(b, a)) = w_{m−1}(b, a).

If we are in Case 1 for ρ(wa), and wa has a rightward length reducing sequence with factorisation wa = αw_{1} ⋯ w_{k}a, then w_{m}(b, a) has a rightward length reducing sequence with factorisation αw_{1} ⋯ w_{k}w_{k+1}x, with w_{k+1} = _{m−1}(b, a) and x the final letter of _{m}(b, a), resulting in u_{k+1} = a^{−1} _{m−1}(b, a), τ(u_{k+1}) = _{m−1}(b, a)x^{−1}, so

ρ(w_{m}(b, a)) = u′_{1} ⋯ u′_{k} _{m−1}(b, a) = ρ(wa)_{m−1}(b, a),

and hence ρ(w_{m}(b, a)) = ρ(w_{m}(a, b)), as required.

Similarly, in Case 2 for ρ(wa), where wa has a leftward lex reducing sequence with factorisation wa = αw_{k} ⋯ w_{1}, w_{m}(b, a) has a leftward lex reducing sequence with factorisation αw_{k} ⋯ pre[w_{1}]_{m}(b, a), resulting in

ρ(w_{m}(b, a)) = αu′_{k} ⋯ u′_{1} _{m−1}(b, a) = ρ(wa)_{m−1}(b, a) = ρ(w_{m}(a, b)).

Now we suppose that the name of l[w] is a or b. Without loss of generality, we can assume that it is a; although the other case appears to be inequivalent, since a <_{lex} b, essentially the same arguments work in both cases. So l[w] = a or a^{−1}. We have w = w′v, where v is a word involving only a and (possibly) b, and w′ is either empty or else the name of l[w′] is not a or b. Let p = p(v), n = n(v); so p + n ≤ m. When l[w] = a or a^{−1}, respectively, let v = v′(b, a)_{k} or v = v′(b^{−1}, a^{−1})_{k} with k maximal.

Case 1. Suppose first that n < m and that w′ admits a rightward critical sequence that transforms w′ to w′′ where l[w′′] ∈ {a^{−1}, b^{−1}} and n(l[w′′]v) = n + 1. Then we must have p + n < m, or else w would admit a rightward length reducing sequence.

If l[w] = a, then we find that w _{m−n−1}(a, b) is critically reduced, but w_{m−n}(a, b) admits a rightward reducing sequence starting with the sequence for w′. The remaining n letters of m(a, b) then cancel with a suffix of the reduction of w _{m−n}(a, b), and we get ρ(w _{m}(a, b)) = pre[w′′]v_{1} for some critically reduced 2-generator word v_{1} that is equal in G(a, b) to l[w′′]v _{m}(a, b). There is also a rightward length reducing sequence starting with the same sequence for w′ for w _{m−n−k}(b, a), following which the next n letters of _{m}(b, a) cancel and, since k ≤ p and p + n < m, the final k letters provoke no further reductions. So we have ρ(w _{m}(b, a)) = pre[w′′]v_{2} with v_{2} equal in G(a, b) to l[w′′]v _{m}(b, a). Since v_{1} and v_{2} are reduced 2-generator words representing the same element of G(a, b), Theorem 2.4 implies that they are equal, so ρ(w_{m}(a, b)) = ρ(w_{m}(b, a)).

If l[w] = a^{−1}, then w_{m−n−1}(b, a) is critically reduced, w_{m−n}(b, a) admits a rightward length reducing sequence starting with the sequence for w′, and the remaining n letters of _{m}(b, a) cancel. There is also a rightward length reducing sequence starting with the same sequence for w′ for w_{m−n+k}(a, b), following which the remaining n − k letters of _{m}(a, b) cancel, and the result follows as in the previous case.

Case 2. Suppose then n = m or that w′ admits no such rightward critical sequence. If l[w] = a, then again w_{m−n−1}(a, b) is critically reduced, and w_{m−n}(a, b) admits no rightward length reducing sequence, but it may admit a leftward lex reducing sequence. If so, then the remaining n letters of _{m}(a, b) cancel. In that case, w_{m−n−k}(b, a) admits a corresponding leftward lex reducing sequence, following which the next n letters of _{m}(b, a) cancel. Now, since w ∈ W, we must have k < m − n in this situation, so the final k letters of _{m}(b, a) provoke no further reductions. So, as in Case 1, we can apply Theorem 2.4 to conclude that ρ(w_{m}(a, b)) = ρ(w_{m}(b, a)).

Suppose, on the other hand, that w_{m−n}(a, b) is critically reduced. If n = 0, then w_{m−1}(b, a) must be critically reduced (because, if not, then a corresponding reduction could be applied to w_{m−n}(a, b)), and we have ρ(w_{m}(b, a)) = w_{m}(a, b). If n > 0, then w_{m−n+1}(a, b) admits a rightward length reducing sequence of length 1, and the remaining n − 1 letters of _{m}(a, b) cancel. Similarly, w_{m−n−k+1}(b, a) admits a corresponding rightward length reducing sequence, and the following n − 1 letters of _{m}(b, a) cancel. The final k letters of _{m}(b, a) can provoke no further reductions, since such a reduction could only result from the final letter in the case k = m − n, but if there were such a reduction then the original word w would admit a corresponding reduction, contradicting w ∈ W. So the result follows as before in this case.

If l[w] = a^{−1}, then w_{m−n−1}(b, a) is critically reduced, and w_{m−n}(b, a) admits no rightward length reducing sequence. If w_{m−n}(b, a) admits a leftward lex reducing sequence, then the remaining n letters of_{m}(b, a) cancel. In that case w_{m−n+k}(a, b) admits a corresponding leftward lex reducing sequence, and the remaining n − k letters of _{m}(b, a) cancel, and the result follows as before.

If, on the other hand, w_{m−n}(b, a) is critically reduced (note that this occurs, in particular, when m = n), then w_{m−n+1}(b, a) admits a rightward length reducing sequence of length 1, as does w_{m−n+k+1}(a, b), and again the result follows.

Now that the proof of Theorem 3.2 is complete, it is natural to ask where the fact that G is of large type was used, and whether that condition was really necessary. In fact the braid group

⟨a, b, c | aba = bab, ac = ca, bcb = cbc⟩

demonstrates the necessity of the large type condition. For w = cbbacba^{−1} contains no rightward length reducing or leftward lex reducing sequence, and hence must be in W. But wb^{−1} admits the rightward length reducing sequence

cbbacba^{−1}b^{−1} → cbbcaba^{−1}b^{−1} → cbbcb^{−1}abb^{−1} → w′ := cbbcb^{−1}a,

which then reduces lexicographically to w′′ := b^{−1}cbbca. So w =_{G} w′′b with w′′b <_{slex} w, and both Theorem 3.2 and Proposition 3.3 fail.

An inspection of the proof of Proposition 3.3 reveals that it is Case 1(b) of that proof that has failed, because the unique rightward length reducing sequence of wb^{−1} was followed by a leftward lex reducing sequence. In the notation of the proof in that case, we have αu′_{1} = cbbc but w̄_{1} = cbbcb^{−1}, and so the claim that w̄_{1} is contained within αu′_{1}, which we deduced from Lemma 3.7(7), is false. Hence it is the use of largeness in Lemma 3.7(7) that has caused this example to fail.

Of course we used largeness in other places too, such as in the proof of Lemma 3.7(2), and in corresponding steps in Lemma 3.8, which could conceivably lead to other non-large-type examples in which our main results fail.

4. Geodesics in Artin groups of large type

Theorem 4.1. Artin groups of large type on their standard generating sets satisfy FFTP, and hence the set of geodesic words is regular.

The rest of this section is devoted to the proof of this theorem. Throughout this section, G will be an Artin group of large type over X, and W the set of shortlex minimal representatives of its elements. We start with a useful technical result.

Lemma 4.2. If w ∈ W, x ∈ X and wx and wx^{−1} are both freely reduced, then wx and wx^{−1} cannot both be non-geodesic.

Proof. We use induction on |w|. The result is clear if w involves at most two generators because it is easily seen that p(wx) + n(wx) > m and p(wx^{−1}) + n(wx^{−1}) > m cannot both hold, given that w is geodesic. Otherwise, if wx and wx^{−1} are both non-geodesic, then Proposition 3.3 implies that wx and wx^{−1} both admit rightward length reducing sequences. It follows from the 2-generator case that these sequences cannot both have length 1.

Suppose that one of these sequences, the one for wx say, has length 1, and the other has length greater than 1. Let w_{1} be the result of applying all τ-moves except for the last in the reduction sequence for wx^{−1}, and let u_{1} be the maximal 2-generator suffix of w_{1}. Then u_{1}x and u_{1}x^{−1} are both non-geodesic, so the result again follows from the 2-generator case.

Finally, suppose that both sequences have length greater than 1, and let w = αu, where u is the maximal 2-generator suffix of w. Then applying all terms except the last in the reduction sequences for wx and wx^{−1} transforms α to words with last letters g and h, where gux and hux^{−1} are 2-generator words with p(gux) + n(gux) > m and p(hux^{−1}) + n(hux^{−1}) > m, but all proper subwords of gux and hux^{−1} are geodesic. Suppose without loss of generality that l[u] ∈ X. Then since p(hux^{−1}) = p(hu), we must have n(hux^{−1}) > n(hu), which is only possible if n(hux^{−1}) = 1, p(u) = m − 1 and p(hu) = m. So we must have h ∈ X and h ≠ f[u]. Similarly, we find that p(ux) = m and n(gux) = 1, so g ∈ X^{−1}. But we cannot have g = f[u]^{−1}, and so we must have g = h^{−1}. But then αg and αg^{−1} are both non-geodesic, and freely reduced, by our definition of α, and the result follows by the inductive hypothesis applied to α.

In order to prove the theorem we need to examine in detail the process of reduction of a geodesic word v to its shortlex minimal representative ρ(v), and prove a number of technical results. We shall use all the notation we established in the previous sections, and introduce some more.

The reduction is done in at most n := |v| steps, through a sequence of words v^{(0)} = v, v^{(1)}, ⋯, v^{(n)} = ρ(v); for each i from 1 to n, v^{(i)} is either equal to v^{(i−1)} or is derived from it by replacing its prefix of length i by its lex reduction. When v^{(i)} ≠ v^{(i−1)}, Proposition 3.3 says that the reduction is through a single leftward lex reducing sequence of which the first τ-move is applied to a word ending at the i-th letter of v^{(i−1)}.

In general we assume that v involves at least three generators (the 2-generator case being dealt with in Section 2). In that case, we define u to be the maximal 2-generator suffix of v, and let a, b be the names of the two generators involved in u. Similarly for each i we define u^{(i)} to be the maximal suffix of v^{(i)} involving a and b (conceivably u^{(i)} might be empty or involve just one of those two generators). Then v = αgu with g ∈ A, where the name of g is neither a nor b. Let k := |αg|; so v^{(k)} = ρ(αg)u. We have u^{(1)} = u^{(2)} = ⋯ = u^{(k−1)} = u.

Let h := l[ρ(αg)], and suppose that h has name c. Our arguments will divide into two cases: (A) c is neither a nor b; (B) c is equal to one of a or b.

The following two lemmas summarise the properties that we shall need in these two cases.

Lemma 4.3. Assume that we are in Case (A). Then:

(1) u^{(k)} = u,

(2) If v^{(n−1)} ≠ v^{(n)} then u^{(n)} involves both a and b.

(3) For each m with k ≤ m ≤ n, u^{(k)} is equal in G to a geodesic word having u^{(m)} as a suffix.

Proof. (1) is clear from the definition of Case (A). We examine the reduction of ρ(αg)u to ρ(ρ(αg)u) = ρ(v). For each m > k, if v^{(m−1)} and v^{(m)} are distinct, the names of the m-th letters of v^{(m−1)} and v^{(m)} are the two generators of the maximal 2-generator subword that ends at the m-th letter of v^{(m−1)}. Let l be maximal such that l ≥ k and the l-th letter of v^{(l)} has name c.

We see that l < n. This is obvious if l = k. If l > k then for each k < m ≤ l, the prefix of length m in v^{(m−1)} has a critical suffix involving c and one of a, b; the fact that l < n follows immediately from the fact that it must involve the same one each time (for each critical suffix must end with an alternating subword of length at least 3).

Now by definition of l, any reduction of v^{(m−1)} to v^{(m)} with m > l must start with a τ-move involving a and b. So if v^{(n−1)} ≠ v^{(n)} the maximal 2-generator suffices of both v^{(n−1)} and v^{(n)} must contain both a and b, and we have (2).

Now for each m with k ≤ m ≤ l, u^{(m)} is a suffix of u^{(k)} = u, so (3) holds for all such m. For any m > l, if v^{(m)} ≠ v^{(m−1)}, then the first τ-move in that reduction is to a subword of u^{(m−1)}, and u^{(m)} is a suffix of the word derived from u^{(m−1)} by applying the first τ-move of that reduction. Hence we see that we could take the sequence of τ-moves that form the first steps of each of the non-trivial leftward lex reducing sequences that reduce v^{(l)} through v^{(l+1)}, v^{(l+2)}, … to v^{(n)} = ρ(v), This sequence of τ-moves transforms u through a sequence of geodesics û^{(k+1)}, …, û^{(n)}, with u^{(m)} a suffix of û^{(m)} and û^{(m)} =_{G} u and for each m with k < m ≤ n. This completes the proof of (3).

Lemma 4.4. Assume that we are in Case (B). Then:

(1) u^{(k)} = h^{j}u for some j ≥ 1.

(2) u^{(n)} involves both a and b.

(3) For each m with k ≤ m ≤ n, u^{(k)} is equal in G to a geodesic word having u^{(m)} as a suffix.

Proof. It follows from Lemma 3.8 (2) that ρ(αg) = ηg′h^{j}, for some word η and j ≥ 1, where g′ = g^{±1}, and so u^{(k)} = h^{j}u, and (1) holds.

To prove (2) and (3), we consider the further reduction of v^{(k)} = ρ(αg)u. Again we consider the sequence v^{(k+1)}, ⋯, v^{(n)} of successive reductions of v^{(k)} to v^{(n)}.

We claim that, for any j′ > j, ηg′h^{j′} is already reduced. To see that, note that a critical suffix v′ of ηg′h^{j′} must have the form v′′h^{j′−j} where v′′ is a critical suffix of ηg′h^{j}. And then by Corollary 2.2 τ(v′) and τ(v′′) have the same first letter. So if v′ were part of a critical factorisation leading to a leftward lex reducing sequence of ηg′h^{j′} then ηg′h^{j} would also have such a reduction, which it does not, since hg′h^{j} = ρ(αg) ∈ W.

So the first τ-move in any non-trivial reduction of v^{(m−1)} to v^{(m)} for k < m ≤ n is to a subword of u^{(m−1)}. Since u^{(k)} involves both a and b, the same applies to u^{(m)} for all k < m ≤ n, which proves (2).

Much as in Case (A), we see that this sequence of first τ-moves can be applied to u^{(k)} = h^{j}u to transform it through a sequence of geodesics û^{(k+1)}, …, û^{(n)}, with u^{(m)} a suffix of û^{(m)} and û^{(m)} =_{G} u^{(k)} and for each m with k < m ≤ n, so (3) is true.

Proposition 4.5. Suppose that v, w are any two geodesics in G representing the same group element, and that l[v] ≠ l[w]. Then:

(1) l[v] and l[w] have different names;

(2) The maximal 2-generator suffices of v and w involve generators with names equal to those of l[v] and l[w];

(3) Any geodesic word equal in G to v must end in l[v] or in l[w].

Proof. Since ρ(v) = ρ(w), either l[ρ(v)] ≠ l[v] or l[ρ(w)] ≠ l[w]. We assume without loss of generality that l[ρv] ≠ l[v]. This implies in particular that v^{(n−1)} ≠ v^{(n)}.

Then l[v] = l[v^{(n−1)}] and l[ρ(v)] = l[v^{(n)}], and v^{(n−1)} and v^{(n)} are related by a leftward lex reducing sequence. Hence we can deduce from Proposition 2.1 (3) that l[v] and l[ρ(v)] have distinct names. If l[ρ(v)] = l[w], then it follows immediately that l[v] and l[w] have distinct names, and so (1) holds. Otherwise we can repeat the argument above, replacing v by w, to deduce that l[w] and l[ρ(w)] = l[ρ(v)] have distinct names. In that case, if (1) is false, then we must have l[v] = g and l[w] = g^{−1} for some g ∈ A, and so vg^{−1} and wg cannot be geodesic, and neither can ρ(v)g^{−1} or ρ(v)g = ρ(w)g. Since both ρ(v)g^{−1} and ρ(v)g are freely reduced, this contradicts Lemma 4.2. So (1) is true.

Now we prove (2) by induction on |v|. The application of a τ-move to a word does not change the generators it involves. So if v involves at most two generators, then w involves the same ones, and the result is immediate.

So suppose that v involves at least three generators. Since v^{(n−1)} ≠ v^{(n)}, it follows from Lemmas 4.3 (2) and 4.4 (2) that the two generators involved in the maximal 2-generator suffix of ρ(v) are the same as those in the maximal 2-generator suffix of v.

If l[w] ≠ l[ρ(v)] then we can apply the argument of the last paragraph to w in place of v, and then (2) is proved. So suppose that l[w] = l[ρ(v)]. We need to prove that the maximal 2-generator suffix of w involves the same two generators as that of ρ(v). Let v′ be the result of applying the first τ-move in the reduction of v^{(n−1)} to v^{(n)} = ρ(v). Then also l[w] = l[v′]. Consider the maximal suffix common to v′ and w. If this involves two generators then the result is proved, so assume not. Then v′ = v′_{0}g^{j} and w = w_{0}g^{j} for some j ≥ 1, and v′_{0} =_{G} w_{0}. Since v′ has a critical word as a suffix, v′_{0} must involve both of the final two generators involved in the maximal 2-generator suffix of ρ(v), so (2) follows by applying induction to the words v′_{0} and w_{0}.

(3) now follows from (1) and (2).

To prove Theorem 4.1, it is enough to show that any minimal non-geodesic word in the generators of G M-fellow travels with a geodesic word representing the same group element. So suppose vg is minimal non-geodesic with g ∈ A. The result is clear if l[v] = g^{−1} so suppose not. We have vg =_{G} v′ with |v′| = |v| − 1 and hence w := v′g^{−1} and v are geodesic words representing the same group element. So it is enough to prove the following proposition.

Proposition 4.6. Suppose that v =_{G} w with v, w both geodesic, and l[v] ≠ l[w]. Then v M-fellow travels with a geodesic word w′ with v =_{G} w′ and l[w′] = l[w].

Proof. Since v, w are geodesics, any non-trvial reduction of v to ρ(v), or of w to ρ(w) = ρ(v) must be through a leftward lex reducing sequence. It follows from Lemma 3.8 that a leftward lex reducing sequence does not change the set of generators involved in a word, so v and w involve the same generators.

The proof is by induction on n = |v|. The base of the induction is provided by the 2-generator result Corollary 2.6, which also allows us to assume from now on that v and w involve at least three generators.

Now Proposition 4.5 (2) tells us that the maximal 2-generator suffices of v, w involve the same two generators. As above we call those two generators a, b, and let a be the name of l[v]. Then the name of l[w] is b; it is distinct from the name of l[v] by Proposition 4.5 (1).

We need to verify the inductive step. So we assume the result holds for pairs of geodesics of length less than n, and verify that it holds for the given pair of geodesics v, w.

We use the following lemma.

Lemma 4.7. Suppose that v, w satisfy the hypothesis of Proposition 4.6, and that the conclusion of Proposition 4.6 holds for geodesic words shorter than v and w. Then if u^{(k)} is equal in G to a geodesic word w_{1} that ends in l[w], the conclusion of Proposition 4.6 holds for v and w.

Proof. In both Cases (A) and (B), we have l[u^{(k)}] = l[u] = l[v] ≠ l[w] = l[w_{1}], and Corollary 2.6 tells us that a single τ-move can be applied to a suffix of u^{(k)} to transform it to a word ending in l[w].

In Case (A), it also follows from Corollary 2.6 that u = u^{(k)} M-fellow travels with a geodesic word w′_{1}, with w′_{1} =_{G} u and l[w′_{1}] = l[w_{1}] = l[w]. So αgw′_{1} M-fellow travels with αgu = v, and represents the same element of G as v.

In Case (B), Lemma 2.8 implies that a single τ-move can be applied to hu to transform it to a geodesic word w′_{2} with l[w′_{2}] = l[w_{1}] = l[w]. Then hu M-fellow travels with w′_{2} and w′_{2} =_{G} hu. Since αg is equal in G to a geodesic word ending in h ≠ g and |αg| < |v|, it follows from the hypothesis that αg M-fellow travels with a geodesic word w′_{0}, with αg =_{G} w′_{0} and l[w′_{0}] = h. Now let w′ := pre[w′_{0}]w′_{2}. Then l[w′] = l[w′_{2}] = l[w],

w′ = pre[w′_{0}]w′_{2} =_{G} pre[w′_{0}]hu = w′_{0}u =_{G} αgu = v,

and the fact that w′ M-fellow travels with v is an immediate consequence of that fact that the pairs w′_{0}, αg and w′_{2}, hu M-fellow travel.

If l[w] = l[ρ(v)], then we may assume that w = ρ(v) = v^{(n)}. By Lemmas 4.3 (3) and 4.4 (3), u^{(k)} is equal in G to a geodesic word ending in u^{(n)} and the conclusion of Proposition 4.6 follows immediately from Lemma 4.7.

So we assume from now on that l[w] ≠ l[ρ(v)]. We can assume (by replacing w by ρ(pre[w])l[w]) that a single leftward lex reducing sequence transforms w to ρ(v) = ρ(w).

By Proposition 4.5 (3), we must have l[ρ(v)] = l[v]. We have ρ(v) = v^{(n)} = βg′′u^{(n)} for some word β and g′′ ∈ A, where the name of g′′ is not equal to a or to b.

If the single leftward lex reducing sequence that reduces w to ρ(v) has length 1, then w = βg′′u′ with u′ =_{G} u^{(n)}. In that case, by Lemmas 4.3 (3) and 4.4 (3), u^{(k)} is equal in G to a geodesic word ending in l[w], and the result follows by Lemma 4.7.

So we suppose that this sequence has length greater than 1. Then we have w = γu′, where u′ is the maximal 2-generator suffix of w and u^{(n)} = suf[τ(u′)]. So γf[τ(u′)] =_{G} βg′′.

If |u^{(n)}| < |u^{(k)}|, then the g′′ in ρ(v) appeared as a result of the application of a τ-move during one of the reductions from v^{(m−1)} to v^{(m)} for some m > k. This application was of the form v^{(m−1)} = δv′u′′ → δτ(v′)u′′ = v^{(m)}a, where l[v′] has name a or b, l[τ(v′)] = g′′, and u′′ is a 2-generator suffix of v^{(m−1)}. Since all reductions from v^{(m′−1)} to v^{(m′)} for m′ > m must consist of a single τ-move applied to u^{(m′−1)}, we have u′′ =_{G} u^{(n)}.

Then δτ(v′) =_{G} δv′. But also

δv′u^{(n)} =_{G} δv′u′′ = v^{(m−1)} =_{G} w = γu′
=_{G} γτ(u′) = γf[τ(u′)]suf[τ(u′)] =_{G} γf[τ(u′)]u^{(n)}

so in fact all three of the geodesics δτ(v′), δv′ and γf[τ(u′)] represent the same element of G. The first of these has last letter g′′ (whose name is neither a nor b), but the second and third end in letters with name a or b. So Proposition 4.5 (3) tells us that l[v′] = f[τ(u′)], and hence

l[v′]u′′ =_{G} l[v′]u^{(n)} =_{G} f[τ(u′)]suf[τ(u′)] = τ(u′) =_{G} u′.

So a 2-generator suffix of δv′u′′ is equal in G to the 2-generator suffix u′ of w, which ends in l[w]. But the maximal 2-generator suffix of δv′u′′ is u^{(m−1)}, and then by Lemmas 4.3 (3) and 4.4 (3), u^{(k)} is equal in G to a word ending in l[u^{(n)}] = l[w] and the result follows once again from Lemma 4.7.

Otherwise |u^{(n)}| = |u^{(k)}|, so u^{(n)} =_{G} u^{(k)} and any non-trivial reduction of v^{(m−1)} to v^{(m)} for m > k consists of a single τ-move applied to u^{(m−1)}.

In Case (i), we have

αgu^{(n)} =_{G} v =_{G} w = γu′ =_{G} γf[τ(u′)]u^{(n)},

so αg =_{G} γf[τ(u′)]. Then, by the inductive hypothesis, αg M-fellow travels with a word ending in f[τ(u′)] and f[τ(u′)]u^{(n)} = τ(u′) M-fellow travels with the word u′ ending in l[w], so the result follows.

Recall that in Case (ii) ρ(αg) = ηg′h^{j}. Since ρ(v) = βg′′u^{(n)} =_{G} βg′′u^{(k)}, we have g′ = g′′ and β = η in this situation. We saw earlier that γf[τ(u′)] =_{G} βg′′, so αg and γf[τ(u′)]h^{j} are two geodesics representing the same group element. Since the names of f[τ(u′)] and h are both a or b and the name of g is neither a nor b, Proposition 4.5 (2) implies that f[τ(u′)] has the same name as h and hence f[τ(u′)] = h. But now, since

h^{j+1}u = f[τ(u′)]h^{j}u = f[τ(u′)]u^{(n)} =_{G} f[τ(u′)]suf[τ(u′)] =_{G} u′,

with l[u′] = l[w], we can apply Corollary 2.6 and Lemma 2.8 to deduce that h^{j}u M-fellow travels with a word ending in l[w], and then the result follows from Lemma 4.7.

References

1. T Brady and J P McCammond, Three-generator Artin groups of large type are biautomatic, J. Pure Appl. Alg. 151 (2000) 1–9.

2. R Charney, Artin groups of finite type are biautomatic, Math. Ann. 292 (1992) 671–683.

3. R. Charney, Problems related to Artin Groups, American Institute of Mathematics, Problems in Geometric

    Group Theory wiki, http://aimath.org/pggt/Artin_Group.

4. R. Charney and J. Meier, The language of geodesics for Garside groups, Math. Z. 248 (2004) 495–509.

5. D.B.A. Epstein et al., Word processing in groups, Jones and Bartlett, 1992.

6. S. Hermiller and J. Meier, Algorithms and geometry for graph products of groups, J. Alg. 171 (1995).

7. H. van der Lek, The homotopy type of complex hyperplane complements, PhD Thesis, University of Nijmegen, 1983.

8. J. Mairesse and F. Mathéus, Growth series for Artin groups of dihedral type, Int. J. Alg. Comp. 16 (2006) 1087–1107.

9. W.D. Neumann and M. Shapiro, Automatic structures, rational growth, and geometrically finite hyperbolic groups, Invent. Math. 120 (1995) 259–287.

10. D Peifer, Artin groups of extra-large type are biautomatic, J. Pure Appl. Alg. 110 (1996) 15–56.

11. L. VanWyk, Graph groups are biautomatic, J. Pure App. Alg. 94 (1994).

Derek F. Holt Mathematics Institute, University of

Warwick, Coventry CV4 7AL, UK.

dfh@maths.warwick.ac.uk Sarah Rees, School of Mathematics and Statistics,

University of Newcastle, Newcastle NE1 7RU, UK.

Sarah.Rees@ncl.ac.uk