Shortlex automaticity and geodesic regularity in Artin groups

Derek F. Holt and Sarah Rees

Abstract

We extend results of [8] and prove shortlex automaticity and regularity of geodesics in a family of Artin groups that includes all groups of large type but also allows some commuting pairs of generators.

1 Introduction and notation

The purpose of this article is to extend the results of [8] to cover a larger class of Artin groups. It was proved there that every Artin group of large type is shortlex automatic over its natural generating set, and that its set of geodesic words over those generators is regular. We extend these results beyond large type Artin groups to allow Artin groups in which some pairs of generators commute, as explained below.

The main results in this article are Theorem 2.1, where Artin groups satisfying our new hypothesis are proved to be shortlex automatic over their natural generating sets, and Theorem 3.1, where those same Artin groups are proved to satisfy the ‘falsification by fellow traveller property’ (FFTP), from which regularity of their sets of geodesics can be deduced as an immediate corollary.

Various other types of Artin groups have been proved to be automatic and, in some cases, biautomatic. This was done, for example, for the Artin groups of finite or spherical type in [3], and for right angled Artin groups in [7, 11]. But while it is proved that right-angled and large type Artin groups are shortlex automatic over their natural generating sets, that is not proved for spherical type groups, and indeed computational evidence (produced using [9]) suggests that it is not true for those of rank at least 3. Each extension of the types of Artin groups for which automaticity has been established adds evidence to the conjecture that all Artin groups are (bi)automatic, but we are still a long way from settling that question. It is not even known whether they all have solvable word problem.

For letters x, y we define _{m}(x, y) to be the product of m alternating xs and ys that starts with x, and (x, y)_{m} to be the product of m alternating xs and ys that ends with y.

The standard presentation for an Artin group over its standard generating set X = {a_{1}, …, a_{n}} is

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

where (m_{ij}) is a Coxeter matrix (a symmetric n × n matrix with entries in ℕ ∪ {∞}, m_{ii} = 1, m_{ij} ≥ 2, ∀i ≠ j).

We call a pair of generators x_{i}, x_{j} a braid pair if 3 ≤ m_{ij} < ∞, a free pair if m_{ij} = ∞, or a commuting pair if m_{ij} = 2. By definition, an Artin group has large type if every pair of generators is either a braid pair or a free pair. Our hypothesis allows commuting pairs too under the following restriction:

if a triple of generators contains a commuting pair, then either the other two pairs are both commuting, or at least one of them is free.

We shall call Artin groups with this property sufficiently large. The class of sufficiently large Artin groups has a significant intersection with the class of locally non-spherical Artin groups, which are considered in [4], where they are proved to have soluble word problem, extending the results of Appel and Schupp for large type groups [1, 2]. But note that we allow triples of commuting pairs of generators, which violate the locally non-spherical condition, and we disallow many triples of the form {2, m, n} that do not violate that condition.

Since our proofs are extensions of the corresponding proofs in [8], and use the same notation, but extended to the more general context, realistically, reading this paper in detail can only be undertaken in conjunction with reading our earlier paper.

As in [8] we derive our results from descriptions of the sets of shortlex minimal and geodesic representatives of elements of an Artin group satisfying our hypotheses, together with the processes that reduce input words to elements of those sets. We perform our reductions using sequences of τ-moves, just as we did in [8]; we just need to extend our definition of a τ-move. Hence we will now have two types of τ-moves: braid- or β-moves; and commutingor κ-moves. The τ-moves of [8] were all braid moves; we shall recall the definition of those below, once we have established our notation.

We define X^{−1} = {x^{−1} : x ∈ X}, A = X ∪ X^{−1}, and call the elements of A letters. We extend our definitions of braid, free and commuting pairs of generators to letters in the obvious way. The letters x and x^{−1} are said to have name x. A word is a sequence of letters, and for a word w and letter x, x ∈ w means ‘x is a letter of w’, while for B ⊆ A, w ∩ B consists of those letters of B within w. If we say w involves x, then we mean x ∈ w or x^{−1} ∈ w.

We shall apply braid (β-) moves to 2-generator words over braid pairs of generators x_{i}, x_{j}; just as in [8]. We call 2-generator subwords of the form p(x, y)ξ(z^{−1}, t^{−1})_{n} or _{n}(x^{−1}, y^{−1})ξ(z, t)_{p} with p + n = m_{i,j} (with some extra conditions imposed when one of p, n is zero) critical (or β-critical). A β-move interchanges the β-critical words_{p}(x, y)ξ(z^{−1}, t^{−1})_{n} and_{n}(y^{−1}, x^{−1})δ(ξ)(t, z)_{p}, replacing w by τ(w).

In addition, we shall apply commuting (κ-) moves to words over sets of generators any pair of which is either free or commuting. Specifically, let u be a word over a subset X_{J} of the generating set, and let a be a letter that commutes with all generators in X_{J}; our main hypothesis ensures that in this case any pair of generators in X_{J} is either commuting or free. Assume also that u contains neither the letter a nor the letter a^{−1}. Under these conditions we define ua to be right κ-critical and au to be left κ-critical. We define a rightward κ-move on w := au to be the substitution au → ua, and a leftward κ-move on w := ua to be the substitution ua → au. We call the result of such a substitution τ(w).

Note that if two words au_{1} and au_{2} are both left κ-critical then so is the word au_{1}u_{2}, while if u_{1}a and u_{2}a are both right κ-critical then so is u_{1}u_{2}a.

When sequences of κ-moves and β-moves are applied, subwords that are either maximal as 2-generator subwords or κ-maximal become important, the first kind in relation to β-moves and the second kind in relation to κ-moves. A subword w′ of a word w is called κ-maximal if

(i) all pairs of letters in w′ are either free or commuting, (ii) each letter in w′ forms a free pair with the immediate predecessor

and successor of w′ in w (if they exist), and (iii) no subword w′′ of w that strictly contains w′ satisfies both (i) and

(ii).

We extend our definitions of rightward and leftward reducing sequences in [8] to allow κ-moves as well as β-moves.

We say that a freely reduced word w admits a rightward length reducing sequence of length k:

(u_{i} → τ(u_{i}) : i = 1, …, k)

if w can be written as a concatenation w = αw_{1}w_{2} ⋯ w_{k}γ, such that:

(i) u_{1} := w_{1} is either β-critical or left κ-critical and so is u_{i} for each i = 2, …, k, where u_{i} := l[τ(u_{i−1})]w_{i}.

(ii) u_{i} and u_{i+1} are not both κ-critical for 1 ≤ i < k. (iii) l[τ(u_{k})] is the inverse of f[γ].

Note that condition (ii) is not hard to impose, since the concatenation of two adjacent κ-critical subwords is κ-critical.

As in [8], we define u′_{l} := pre[τ(u_{l})] for 1 ≤ l ≤ k. Then the rightward length reducing sequence followed by the free cancellation of l[τ(u_{k})] with f[γ] transforms w to αu′_{1}u′_{2} ⋯ u′_{k}suf[γ].

We say that a freely reduced word w admits a leftward lex reducing sequence of length k:

(u_{i} → τ(u_{i}) : i = 1, …, k)

if w can be written as a concatenation w = αw_{k} ⋯ w_{1}γ, such that:

(i) u_{1} := w_{1} is either β-critical or right κ-critical and so is u_{i} for each i = 2, …, k, where u_{i} := w_{i}f[τ(u_{i−1})].

(ii) u_{i} and u_{i+1} are not both κ-critical for 1 ≤ i < k. (iii) f[τ(u_{k})] is earlier in the lexicographic order of letters than f[u_{k}].

As above, condition (ii) is not hard to impose.

As in [8], we define u′_{l} := suf[τ(u_{l})] for 1 ≤ l < k, and u′_{k} is not defined. Then the leftward lex reducing sequence transforms w to ατ(u_{k})u′_{k−1} ⋯ u′_{1}γ.

We define W to be the set of freely reduced words that admit no rightward length reducing sequence or leftward lex reducing sequence of any length k ≥ 1.

2 Proof of shortlex automaticity

This section is devoted to the proof of the following theorem.

Theorem 2.1 Let G be a sufficiently large Artin group, defined over its standard generating set. Then G is shortlex automatic. Furthermore, the set W defined above is the set of shortlex minimal representatives of the elements of G.

We recall that G is shortlex automatic over X if the set of shortlex minimal representatives of its elements as words over X is a regular set, satisfying a synchronous fellow traveller property [6]. Imitating the proof of [8, Theorem 3.2], we can deduce Theorem 2.1 from the following three propositions, whose statements appear identical to the statements of the corresponding propositions in [8], but in fact apply under the more general hypotheses on G of this paper, and with a more general definition of reducing sequence.

For the remainder of this section we assume that G satisfies the hypotheses of Theorem 2.1, and that W is defined as above.

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

Now we define a map ρ : A^{∗} → W recursively as follows.

(i) For w ∈ W, ρ(w) := w.

(ii) For w ∈ W, g ∈ A and wg ∉ W, if l[w] = g^{−1} then ρ(wg) := pre[w], but otherwise ρ(wg) is the element of W obtained from wg as specified in Proposition 2.2.

(iii) For any w ∈ A^{∗} and g ∈ A, ρ(wg) := ρ(ρ(w)g).

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

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

Before proving these three propositions we establish some technical lemmas.

Lemma 2.5 Suppose that wg is freely reduced and admits a rightward length reducing sequence, with corresponding factorisation αw_{1} … w_{k}g of wg, and notation as above. Then either the suffix w_{k}g of wg is 2-generator over a pair of braid generators satisfying p(w_{k}g) + n(w_{k}g) ≥ m and hence contains a β-critical subword, or it contains a right κ-critical suffix.

Proof: This is exactly as in [8, Lemma 3.6] if the final move of the rightward length reducing sequence is a β-move. If it is a κ-move, we must have u_{k} = w_{k} = g^{−1}suf[w_{k}] (when k = 1) or u_{k} = g^{−1}w_{k} (when k > 1), and so w_{k}g contains the right κ-critical suffix suf[w_{k}]g or w_{k}g. □

As in [8], 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, and 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.

NB: in modifying the statements of two lemmas of [8] to get Lemmas 2.6, 2.7, we have added the condition that w ∈ W, which certainly holds whenever the lemma is applied. The purpose in adding that condition was to make the statement of part (7) of each lemma a little more straightforward.

Lemma 2.6 For w ∈ W, 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) If u_{l} is β-critical then no proper suffix of u_{l} is critical; hence u_{l} has one of the forms: _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with p > 0, or_{n}(x^{−1}, y^{−1})ξ(z, t)_{p} with n > 0, where {x, y} = {z, t} = {a_{i_{l}}, a_{j_{l}}}.

(2) If u_{l} is β-critical, then u′_{l} involves both of the generators a_{i_{l}} and a_{j_{l}}.

(3) If u_{l} is β-critical then p(u′_{l}) + n(u′_{l}) < m.

(4) Suppose that l > 1. If u_{l−1} is β-critical then f[u′_{l}] ∉ {a_{i_{l−1}}^{±1}, a_{j_{l−1}}^{±1}}, and if further u_{l} is κ-critical, then u′_{l} ∩ {a_{i_{l−1}}^{±1}, a_{j_{l−1}}^{±1}} = ∅. If u_{l−1} is κ-critical but u_{l} is β-critical then {f[u′_{l}], x} is free for all x ∈ u′_{l−1}.

(5) Suppose that l < k. If u_{l+1} is β-critical, then l[u′_{l}] ∉ {a_{i_{l+1}}^{±1}, a_{j_{l+1}}^{±1}}, and if further u_{l} is κ-critical, then u′_{l} ∩ {a_{i_{l+1}}^{±1}, a_{j_{l+1}}^{±1}} = ∅. If u_{l+1} is κ-critical, then {l[u′_{l}], x} is free for all x ∈ u′_{l+1}. Further, l[u′_{k}] ≠ g^{±1}, and if u_{k} is κ-critical, then u′_{k} ∩ {g^{±1}} = ∅.

(6) Suppose that k > 1. Then, for those u_{i}’s that are β-critical and κ-critical respectively, the corresponding words amongst w_{2}, …, w_{k}g and u′_{2}, …, u′_{k} are maximal 2-generator subwords and κ-maximal subwords respectively, within wg and α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}.

This lemma is a modification of [8, Lemma 3.7], and the proof of much of that lemma transfers.

Proof: The proofs of (1), (2) and (3) need no adjustment.

For (4) the proof needs adjustment only when one of u_{l} and u_{l−1} is κcritical. Suppose first that u_{l−1} is β-critical and u_{l} is κ-critical. Since h := l[τ(u_{l−1})] = f[u_{l}], h must commute with every letter in w_{l} = u′_{l}. Now, by the definition of a κ-critical word, {h, h^{−1}}∩u′_{l} = ∅. h ∉ u′_{l} and h^{−1} ∉ u′_{l}. If x is the other generator of u_{l−1}, then xh ≠ hx, and so we also have {x, x^{−1}} ∩ u′_{l} = ∅.

Suppose next that u_{l−1} is κ-critical and u_{l} is β-critical. Since h := f[u_{l}] = l[τ(u_{l−1})] commutes with every letter in u′_{l−1} and {h, f[u′_{l}]} is a braid pair, our hypothesis ensures that f[u′_{l}] is in a free pair with every letter of u′_{l−1}.

This completes the adjustment of the proof of (4). The proof of (5) is adjusted in a very similar way.

The proof of (6) needs no adjustment for the β-critical words. For the κmaximality of the words corresponding to κ-critical words, we observe that, since the neighbouring moves in the sequence are β-moves that involve braid pairs of generators, any longer subwords would violate the definition of κmaximality.

For (7) we may assume that k > 1, or there is nothing to prove. As in [8] we see that none of u′_{2}, …, u′_{k} can contain β-critical subwords. And a β-critical word cannot be contained within u′_{l}u′_{l+1}, either when both u_{l} and u_{l+1} are βcritical (by (6)), or when one is β-critical and the other κ-critical (by (4) and (5)). Suppose that v is a κ-critical subword of αu′_{1}u′_{2} ⋯ u′_{k}. Suppose that v intersects both u′_{l} and u′_{l+1} non-trivially. If both are braid (2-generator) subwords, then the intersections must be powers of single generators which, according to our main hypotheses, cannot commute, and so v ⊆ u′_{l}u′_{l+1} cannot be κ-critical. If one of u′_{l} and u′_{l+1} is a braid subword, then that intersection is a power of a single generator, which (4) and (5) guarantee to be free with the rest of v, and again v cannot be κ-critical. So v cannot intersect a braid subword, and must be a subword of some u′_{l}; if l > 1 the adjacent subwords must be braid subwords, and so the sequence has length 1. Since w ∈ W, this case cannot occur.

So the first term of any further reducing sequence 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 2.5 tells us that its rightmost factor must contain a critical subword. That can only intersect the suffix u′_{2} ⋯ u′_{k} if it is κ-critical, and in that case it is within some u′_{l}. Within u′_{l−1} there is a 2-generator subword on a braid pair of generators neither of which is in u′_{l}, and so neither of which can freely cancel with a letter of u′_{l} after a κ-move has been applied. Hence (7) is proved. □

Lemma 2.7 For w ∈ W, 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) If u_{l} is β-critical then no proper prefix of u_{l} is critical; hence u_{l} has one of the forms: _{p}(x, y)ξ(z^{−1}, t^{−1})_{n} with n > 0, or_{n}(x^{−1}, y^{−1})ξ(z, t)_{p}

with p > 0, where {x, y} = {z, t} = {a_{i_{l}}, a_{j_{l}}}.

(2) If l < k and u_{l} is β-critical then u′_{l} involves both of the generators a_{i_{l}} and a_{j_{l}}.

(3) If l < k and u_{l} is β-critical than p(u′_{l}) + n(u′_{l}) < m.

(4) Suppose that l < k. If u_{l+1} is β-critical, then f[u′_{l}] ∉ {a_{i_{l+1}}^{±1}, a_{j_{l+1}}^{±1}}, and if further u_{l} is κ-critical, then u′_{l} ∩ {a_{i_{l+1}}^{±1}, a_{j_{l+1}}^{±1}} = ∅. If u_{l+1} is κ-critical but u_{l} is β-critical, then {f[u′_{l}], x} is free for all x ∈ u′_{l+1}.

(5) Suppose that 1 < l < k. If u_{l−1} is β-critical, then l[u′_{l}] ∉ {a_{i_{l−1}}^{±1}, a_{j_{l−1}}^{±1}}, and if further u_{l} is κ-critical, then u′_{l} ∩ {a_{i_{l−1}}^{±1}, a_{j_{l−1}}^{±1}} = ∅. If u_{l−1} is κ-critical, then {l[u′_{l}], x} is free for all x ∈ u′_{l−1}. Further l[u′_{1}] ≠ g^{±1}, and if u_{1} is κ-critical, then {g^{±1}} ∩ u′_{1} = ∅.

(6) Suppose that k > 1. Then, for those u_{i}’s that are β-critical and κcritical respectively, the corresponding words amongst w_{1}, …, w_{k−1} and u′_{1}, … u′_{k−1} are maximal 2-generator subwords and κ-maximal subwords respectively, within wg and ατ(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 its tail when length reducing, are contained within ατ(u_{k}).

The proof of this is very similar to the previous proof, so we shall omit it, as we omitted the proof of the corresponding [8, Lemma 3.8].

Lemma 2.8 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 over generators that form a braid pair, where f[ζ] = g and suf[ζ] is 2-geodesic. 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: This is identical to the proof of [8, Lemma 3.9]. □

We are now ready to prove Proposition 2.2. The argument has the same structure as the proof of [8, Proposition 3.3] but using the modified lemmas. We shall outline the whole argument but only give detail where the argument needs modification. Where we comment that the argument follows that of the proof of [8, Proposition 3.3] without adjustment, we intend it to be understood that any applications of [8, Lemmas 3.6 to 3.9] have been replaced by applications of Lemmas 2.5 to 2.8 of this article.

Proof of Proposition 2.2: 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; 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}; we call the word resulting from this reduction ρ_{2}(wg).

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 this argument now follow.

Case 1(a):

Suppose that we are in Case 1 and that ρ_{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 ρ_{1}(wg).

Since w is in W and hence cannot admit a rightward length reducing sequence, the subword w̄_{1} ⋯ w̄k̄h of ρ_{1}(wg) cannot be a subword of w. Hence it has some intersection with the suffix u′_{1} ⋯ u′_{k} of ρ_{1}(wg). However, Lemma 2.6 (7) tells us that it is contained within αu′_{1}. So the subword w̄k̄h has some intersection with u′_{1}, but by Lemma 2.6 (6) any other factors of this sequence are to the left of u′_{1} in ρ_{1}(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. First suppose that w_{1} → τ(w_{1}) is a β-move. If the intersection of w̄_{1}h and τ(u_{1}) is a 2-generator word, then the argument is as in [8]. If the intersection is h^{r}, with r ≥ 1 (this is a case that was accidentally omitted from the proof of [8, Lemma 3.8]), then we can write w̄_{1} = w̄′_{1}h^{r−1} and apply (essentially) [8, Lemma 2.8] to see that w̄′_{1}h admits a rightward length reducing move, and hence so does the subword w̄′_{1}w_{1} of w, contradicting w ∈ W.

So now suppose that u_{1} → τ(u_{1}) is a κ-move, au′_{1} → u′_{1}a. Since w̄_{1}h and u′_{1} intersect, certainly h ∈ u′_{1}, and hence ha = ah. First suppose that h = f[u′_{1}]. Then w̄_{1}au′_{1} is a subword of w, and can be reduced through the application of a τ-move to the maximal prefix of w̄_{1} not ending with an h (again we can use essentially [8, Lemma 2.8] to see that such a move exists), followed by h^{−1}a → ah^{−1}, and then by free-cancellation; this contradicts w ∈ W.

Otherwise h ≠ f[u′_{1}] and, since the intersection of w̄_{1} with u′_{1} involves at least 2 generators of u′_{1}, w̄_{1} cannot be β-critical. So w̄_{1} → τ(w̄_{1}) is a κmove, which involves commuting h^{−1} past the letters of u′_{1} that precede the first occurrence of h. Since (as we observed earlier) ha = ah, we can apply essentially the same move to commute an h^{−1} (that must be in α) to the right within αau′_{1} = αw_{1}, and then freely cancel that h^{−1} with the first h in u′_{1}; again this contradicts w ∈ W.

This completes the case k̄ = 1. The case k̄ > 1 proceeds as in the proof of [8, Proposition 3.3], with a modification just as above in the case where u′_{1} → τ(u′_{1}) is a κ-move.

Case 1(b):

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

First suppose that u_{1} → τ(u_{1}) is a β-move. If the intersection of w̄_{1} and u′_{1} is a 2-generator word, then the argument is as in [8, Proposition 3.3]. If the intersection is a power of a single generator h (again, this is a case that was accidentally omitted from the proof in [8]), then w̄′_{1}w_{1} is a subword of w admitting a leftward lex reducing reduction, where w̄′_{1} is the maximal prefix of w̄_{1} that ends with a single h.

So suppose that u_{1} → τ(u_{1}) is a κ-move, au′_{1} → u′_{1}a. If the intersection of w̄_{1} with u′_{1} is a power of a single generator h, then, where w̄′_{1} is the maximal prefix of w̄_{1} that does not end with h, w̄′_{1}au′_{1} is a subword of w, and application of the move ah → ha followed by the leftward lex reducing sequence of ρ_{1}(wg) reduces w lexicographically, contradicting w ∈ W.

Otherwise, just as in Case 1(a) we see that w̄_{1} → τ(w̄_{1}) is a κ-move, which involves commuting a letter h ∈ u′_{1} past the letters of u′_{1} that precede the first occurrence of h. Hence ha = ah. We could have applied the same move to commute h to the left within αau′_{1} = αw_{1} causing a lexicographic reduction within w; again this contradicts w ∈ W.

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 corresponds to [8, Lemma 3.10], and which we state as a separate lemma since we shall also use it in the proof of Proposition 2.3.

Lemma 2.9 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 ρ_{2}(wg) admits a leftward lex reducing sequence with associated factorisation βw̄k̄ ⋯ w̄_{1}γ. Lemma 2.7 (7) tells us that the subword w̄_{1} is a subword of ατ(u_{k}) within ρ_{2}(wg). Since w ∈ W, w̄_{1} cannot be a subword of α and so w̄_{1} must end within τ(u_{k}).

First suppose that u_{k} → τ(u_{k}) is a β-move. If the intersection of w̄_{1} and u′_{k} is a 2-generator word, then the argument is as in [8, Proposition 3.3]. If the intersection is a power of a single generator h (this is the accidentally omitted case again), then, where w̄′_{1} is again the maximal prefix of w̄_{1} ending in a single h, w̄′_{1}u′_{k} admits a leftward lex reducing reduction, and so the original reduction sequence can be extended further left, contradicting its optimality.

So now suppose that u_{k} → τ(u_{k}) is a κ-move, w_{k}a → aw_{k}. If the intersection of aw_{k} with w̄_{1} is just a, then we can extend the original reduction sequence by the move ū_{1} → τ(ū_{1}), contradicting its minimality. Otherwise, ū_{1} → τ(ū_{1}) must be a κ-move, commuting l[w̄_{1}] one or more places to the left past a word containing a. If we delete that letter a from the prefix of ρ_{2}(w) that ends at the right hand end of w̄_{1} then we derive a prefix of w to which (essentially) the same κ-move can be applied. If the original κ-move was on a word of length 2, then the new κ-move has no effect. But whether or not this is the case, the application of this move followed by the subsequent moves in the reduction sequence for ρ_{2}(w) (all of which occur to the left of u′_{k}) yields a leftward lex reducing sequence for w, contradicting w ∈ W. □

To complete the proof of Proposition 2.2. we need the proof of Lemma 2.9, which corresponds to [8, Lemma 3.10]. Here too, whenever we comment that the argument follows that of the proof of [8, Lemma 3.10] without adjustment, we intend it to be understood that any applications of [8, Lemmas 3.6 to 3.9] have been replaced by applications of Lemmas 2.5, 2.6, 2.7 and 2.8.

Proof of Lemma 2.9: 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 2.7 (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 w ∈ W. Hence w̄k̄h must end within τ(u_{k}). But by Lemma 2.7 (6) any other factors of this sequence must be within α.

The proof is now by induction on k. We deal first with the base case k = 1.

We eliminate first the case k̄ = 1. First suppose that w_{1} → τ(w_{1}) is a β-move. If the intersection of w̄_{1}h and τ(w_{1}) is a 2-generator word, then the argument is as in [8]. If the intersection is h^{r}, with r ≥ 1 (this is a case that was accidentally omitted from the proof of [8, Lemma 3.8]), then we can write w̄_{1} = w̄′_{1}h^{r−1} and apply (essentially) [8, Lemma 2.8] to see that w̄′_{1}h admits a rightward length reducing move, and hence so does w̄′_{1}τ(w_{1}). So l[τ(w̄′_{1})] = h^{−1}, and h^{−1}τ(w_{1}) is not freely reduced. So h^{−1}τ(w_{1}) is not geodesic, and hence neither is h^{−1}w_{1}, and that word admits a rightward length reducing move. Then the subword w̄′_{1}w_{1} of wg, and hence also wg itself, admits a rightward length reducing sequence of length 2.

So now suppose that w_{1} → τ(w_{1}) is a κ-move, w_{1} = pre[w_{1}]g → gpre[w_{1}]. The letter h that freely cancels with l[τ(w̄_{1})] must be a letter of τ(w_{1}) = gpre[w_{1}].

If h = g then w̄_{1}w_{1} admits the rightward length reducing sequence:

w̄_{1}w_{1} → τ(w̄_{1})w_{1} = pre[τ(w̄_{1})]h^{−1}pre[w_{1}]g →
pre[τ(w̄_{1})]pre[w_{1}]h^{−1}g → pre[τ(w̄_{1})]pre[w_{1}]

(which has length 2 if w̄_{1} → τ(w̄_{1}) is a β-move, but collapses to a sequence of length 1 if it is a κ-move), and hence wg also admits such a sequence.

Otherwise, h ∈ τ(w_{1}). Then, since w ∈ W, w̄_{1}h cannot be a subword of pre[w_{1}], so it must contain g, and hence g ∈ w̄_{1}. Then, since g and h form a commuting pair of generators, both involved in w̄_{1}, the move w̄_{1} → τ(w̄_{1}) must be a (rightward) κ-move; specifically it commutes h^{−1} = f[w̄_{1}] to the right past suf[w̄_{1}]. But the word obtained by removing the letter g from w̄_{1} is a subword of wg, and also admits a rightward length reducing κ-move. Hence so does wg.

This completes the case k̄ = 1. The case k̄ > 1 proceeds as in the proof of [8, Lemma 3.10], with a modification as above in the case where u′_{1} → τ(u′_{1}) is a κ-move.

We now proceed to the inductive step, k > 1. We can use the corresponding part of the proof of [8, Lemma 3.10] almost without modification. The induction hypothesis ensures that we can apply a rightward sequence of τmoves to αw_{k} ⋯ w_{2} and derive a word ending in g^{′−1}, where g′ := f[τ(w_{1})] = f[τ(u_{1})]. Then it is shown that the word g^{′−1}w_{1} is non-geodesic.

When w_{1} → τ(w_{1}) is a β-move, the argument of [8] shows without modification (except that we use Lemma 2.8 (a) rather than [8, Lemma 3.9]) that a β-move on a prefix of g^{′−1}w_{1} can be applied after the rightward sequence of τ-moves applied to αw_{k} ⋯ w_{2} (which results in a word ending in g^{′−1}); the extended sequence is now a rightward length reducing sequence for wg.

Otherwise w_{1} → τ(w_{1}) is the (leftward) κ-move pre[w_{1}]g → gpre[w_{1}], and so g′ = g. So we can combine a rightward sequence of τ-moves applied to αw_{k} ⋯ w_{2} with the rightward κ-move g^{−1}pre[w_{1}] → pre[w_{1}]g^{−1} followed by the cancellation of the final g to construct a rightward length reducing sequence for wg.

Proof of (b):

Now suppose that wg admits a rightward length reducing sequence. Since w ∈ W, the tail of the associated factorisation of wg must be the final g, Again we use induction on k.

Suppose first that k = 1. As in [8], if w_{1} → τ(w_{1}) is a β-move, then the argument is very similar to the k = 1 case in the proof of (a): we just interchange the roles of u_{1} = w_{1} and τ(u_{1}).

When w_{1} → τ(w_{1}) is a leftward κ-move pre[w_{1}]g → gpre[w_{1}], the final move in the rightward length reducing sequence of wg must be a rightward κ-move that commutes g^{−1} past a word having pre[w_{1}] as a suffix. It is then clear that the prefix αw_{k} ⋯ w_{2}g of ρ_{2}(wg) admits a rightward length reducing sequence of length either equal to or one less than that of wg, and hence so does ρ_{2}(wg).

Now suppose that k > 1. Then, by Lemma 2.7 (6), those subwords w_{1},… w_{k−1} for which the corresponding u_{i} are β-critical are maximal 2-generator words and 2-geodesic, whereas those that are κ-critical are κ-maximal.

Suppose that wg admits a rightward length reducing sequence βw̄_{1}w̄_{2} ⋯ w̄_{k}hγ of length k̄. This cannot apply to w, since w ∈ W, so γ is the empty word and h = g. We observe that the k̄-th move in the rightward sequence for wg and the first move in the leftward sequence for wg are either both κ-moves or both β-moves, depending on whether or not l[w] commutes with g.

Suppose that k̄ = 1. Then w̄_{1} is a suffix of w. Now the fact that w_{1} must be either a maximal 2-generator subword of wg or κ-maximal ensures that w̄_{1}g is a suffix of w_{1}. But in that case w_{1} admits a length reduction. That cannot happen if w_{1} → τ(w_{1}) is a β-move, when we observed above that w_{1} must be 2-geodesic, nor can it happen if w_{1} → τ(w_{1}) is a κ-move since that would contradicts the condition in the definition of a (leftward) κ-move ua → au that stipulates that neither a nor a^{−1} occurs in u.

So k̄ > 1. Using the fact that w_{1} is either maximal as a 2-generator subword or κ-maximal, we deduce that the (k̄ − 1)-th τ-move must change l[w_{2}] to a letter h, say, which then becomes the first letter of ūk̄. When the k̄-th move is a β-move, the argument of [8, Lemma 3.10] shows that g′ := f[τ(w_{1})] = h^{−1}. If the k̄-th move is a κ-move, then since f[τ(w_{1})] = l[w_{1}] = g and f[ūk̄] = l[τ(ūk̄] = g^{−1} we have g′ = h^{−1} in this case too.

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 2.3: This is immediate except when wg is freely reduced but wg ∉ W, in which case ρ(wg) is defined as in the proof of Proposition 2.2, and we use the same notation as in that proof.

First suppose that ρ(wg) = ρ_{1}(wg). Then 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 l[τ(u_{k})] = 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 2.6 (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. We need to show that S is optimal.

So let S′ be the optimal leftward 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 subwords of w′ that are either maximal 2generator or κ-maximal (as in Lemma 2.7 (6)). These first k − 1 moves transform w′ back to ατ(u_{1})w_{2} ⋯ w_{k}.

The k-th move of S′ must be of the same type as the move u_{1} → τ(u_{1}) since each of these two moves is a β-move precisely when τ(u_{1}) contains a braid pair of generators.

Suppose first that u_{1} → τ(u_{1}) is a β-move. Now if S′ extends further left than S, then either the k-th move of S′ extends further left than that of S, or else τ(u_{1}) → u_{1} is the k-th move of both S and S′, but it is followed by other moves in S′. In the first case, the argument in the proof of [8, Proposition 3.4] shows that ατ(u_{1}) contains a critical subword γτ(u_{1}), that starts within α and ends at the end of τ(u_{1}); some prefix γγ′ of γu_{1} is also critical, and is a subword of w, and then the β-move γγ′ → τ(γγ′) followed by any remaining moves in S′ gives a leftward reducing sequence for w, contradicting the fact that w ∈ W. In the second case the sequence of remaining moves in S′ also gives a leftward reducing sequence for w, contradicting the fact that w ∈ W.

So suppose that u_{1} → τ(u_{1}) is a κ-move, au′_{1} → u′_{1}a, where a = f[u_{1}]. Then, as we observed above, the k-th move of S′ must also be a κ-move. As before, either this κ-move must extends further left than f[u′_{1}] (in which case it moves the a further left than its original position in w, immediately to the left of f[u′_{1}]), or it must be followed by further moves in S′. In the first case we could have applied a leftward κ-move to move a = f[w_{1}] to the left within w, and in the second case we could applied the additional moves in S′ within w; in either case this contradicts w ∈ W.

Now we can apply Lemma 2.9 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 contradicts w ∈ W. Hence w′ admits no such reduction, and so we must have ρ(w′) = ρ_{2}(w′) = w as required.

Now suppose that ρ(wg) = ρ_{2}(wg). Then we have a factorisation wg = αw_{k} ⋯ w_{1} corresponding to a leftward lex reducing sequence for 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 rightward length reducing sequence S′ for ρ(wg)g^{−1} that starts further to the right than S. By Lemma 2.7 (7), such a sequence would 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, the first move being a τ-move on u′′_{k}. As in [8] we can exclude the possibility that u_{k} is β-critical. Hence we now assume that u_{k} = ua and τ(u_{k}) = au, for some u not containing a or a^{−1}, all of whose letters commute with a, and so u′′_{k} is a suffix of u, and the τ-move on u′′_{k} is a commuting move. Since the result of the τ-move on u′′_{k} must be a word ending in a, we have a ∈ u′′_{k}, and hence also a ∈ u; this gives a contradiction. □

Proof of Proposition 2.4: To ease the notation, let a = a_{i}, b = a_{j}, and m = m_{ij}. We divide our argument into the two cases m > 2 and m = 2.

Suppose first that m > 2; in other words {a, b} is a braid pair. We suppose, as we did in the proof of [8, Proposition 3.5], that a <_{lex} b. The proof is straightforward if w is empty or if w is a power of a letter whose name is not a or b.

Suppose that the name of l[w] is c, with c ∉ {a, b}. It is transparent that ρ(w_{m}(a, b)) = ρ(w_{m}(b, a)) = w_{m}(a, b), except when w has a suffix v that is either a 2-generator word involving a braid pair {a, c} or {b, c}, or such that either va or vb is right κ-critical. Note that va and vb cannot both be κ-critical, since {a, b} is a braid pair. We shall assume that in the braid pair case, that pair is {a, c} rather than {b, c}, a rather than b, and that in κ-critical case it is va that is κ-critical, in which case {b, c} is a free pair; the argument in which the roles of a and b are reversed is essentially identical (we need to exercise care, since we have assumed that a < b).

In the case of a braid pair, we can use the argument in the proof of [8, Proposition 3.5] to conclude that ρ(w_{m}(a, b)) = ρ(wa)_{m−1}(b, a), and also that ρ(w_{m−1}(b, a)) = w_{m−1}(b, a). In the κ-critical case, the same conclusions follow from the observation that the name of the final letter of ρ(wa) is l[w] = c, together with the fact that {b, c} is free. In either case, the argument of [8] goes through without modification to deduce from the equation ρ(w_{m−1}(b, a)) = w_{m−1}(b, a) that ρ(w_{m}(b, a)) = ρ(wa)_{m−1}(b, a). Combining the two expressions for ρ(wa)_{m−1}(b, a), we conclude that ρ(w_{m}(a, b)) = ρ(w_{m}(b, a)).

Now we suppose that the name of l[w] is a or b. In that case, since {a, b} is a braid pair (by assumption), the argument of [8] goes through without modification to prove that ρ(w_{m}(a, b)) = ρ(w_{m}(b, a)).

It remains to consider the case m = 2; that is, when {a, b} is a commuting pair. We need to prove that ρ(wab) = ρ(wba). We use the following result.

Lemma 2.10 Suppose that {a, b} is a commuting pair.

(1) If wa ∈ W, wb ∈ W, then ρ(wab) = ρ(wba) and wab ∈ W or wba ∈ W, depending on whether a <_{lex} b or b <_{lex} a.

(2) If wa ∈ W and wb ∉ W, then ρ(wab) = ρ(wb)a = ρ(wba).

Proof of Lemma 2.10: Suppose that wa, wb ∈ W, and a <_{lex} b. Then wab cannot have a rightward length reducing factorisation, αw_{1} ⋯ w_{k}b, since αw_{1} ⋯ pre[w_{k}]b would then be a rightward length reducing sequence for wb (even if pre[w_{k}] were the empty word). And wab cannot have a leftward lex reducing factorisation, αw_{k} ⋯ w_{1}, since in that case, where w_{1} = v_{1}ab, αw_{k} ⋯ v_{1}b would be a leftward lex reducing sequence for wb (even if v_{1} were the empty word). So wab ∈ W, and (i) is proved.

Now suppose that wa ∈ W, wb ∉ W. Then it is not hard to see that wab ∉ W. We know from Proposition 2.2 that a single reduction is sufficient to reduce wab to ρ(wab). If this is rightward, and αw_{1} ⋯ w_{k}b is the associated factorisation, then αw_{1} ⋯ pre[w_{k}]b is a rightward length reducing factorisation for wb. If the single reduction is leftward, and αw_{k} ⋯ w_{1} is the associated factorisation, then w_{1} = v_{1}ab for some v_{1}, and αw_{k} ⋯ v_{1}b is a leftward lex reducing factorisation for wb. In either case, if the factorisation for wb were not optimal, neither would be the associated factorisation for wab, and hence in both cases we can deduce that ρ(wb)a = ρ(wab). Finally, by definition ρ(wba) = ρ(ρ(wb)a), so ρ(wba) = ρ(ρ(wab)) = ρ(wab). □

The lemma yields the result we need except when w ∈ W but wa, wb ∉ W. So suppose that this is the case. We consider the various possibilities for l[w]. It follows from [8, Lemma 2.8] that we cannot have l[w] = a when w ∈ W but wa ∉ W, and similarly we cannot have l[w] = b. Hence l[w] is equal to a^{−1}, b^{−1}, or c, with c ∉ {a^{±1}, b^{±1}}.

When l[w] = a^{−1}, we have ρ(wa) = pre[w], and ρ(wab) = ρ(pre[w]b). Now ρ(wb) = ρ(pre[w]a^{−1}b). If pre[w]b ∈ W, then Lemma 2.10 (i), together with the fact that wb ∉ W, applies to give ρ(wb) = ρ(pre[w]ba^{−1}) = pre[w]ba^{−1}. On the other hand, if pre[w]b ∉ W, then Lemma 2.10 (ii) gives ρ(wb) = ρ(pre[w]a^{−1}b) = ρ(pre[w]b)a^{−1}, so ρ(wba) = ρ(pre[w]b) = ρ(wab). The case l[w] = b^{−1} is similar.

Finally, suppose that l[w] = c, where c ∉ {a^{±1}, b^{±1}}. Now {c, a} cannot be a free pair, since wa ∉ W. Similarly for {c, b}. And neither {c, a} nor {c, b} can be a braid pair (or the other pair would be free), hence both are commuting pairs. Both wa and wb reduce, but if both reduced with reducing sequences of length greater than 1, then some letter d of w, which is in the second to rightmost subword in the associated factorisations of both wa and wb, would be in a braid pair with both a and b, contrary to our hypothesis. Hence we may assume that a single τ-move reduces wb in shortlex. If wa is also reduced by a single τ-move, then the two such moves are κ-moves, with a, b commuting past suffices u_{a}, u_{b} of w; in that case we assume that u_{b} is no longer than u_{a}.

If wb is non-geodesic, then w = αb^{−1}u_{b}, where u_{b} does not involve b, and ρ(wb) = αu_{b}, while if wb can be reduced lexicographically, then w = αu_{b} and ρ(wb) = αbu_{b}, with bu_{b} < u_{b}b. The rightmost τ-move in the reducing sequence for wa is a κ-move that commutes a or a^{−1} past a suffix of w which must contain u_{b} (by assumption when the sequence has length 1, and otherwise using part (6b) of either Lemma 2.6 or Lemma 2.7). So ρ(wa) has u_{b} as a suffix, and ρ(wa)b can be reduced using the same κ-move that reduces wb. Similarly, ρ(wb)a can be reduced using essentially the same sequence of moves that can be applied to wa. The result of both these two sequences of reductions is the same word v, and is a reduction of both wab and wba. A single reducing sequence of τ-moves derives v from ρ(wb)a. It must be optimal as a reducing sequence for ρ(wb)a, since it corresponds to an optimal reducing sequence for wa. Hence v = ρ(ρ(wb)a) = ρ(wba) ∈ W, and ρ(wab) = v = ρ(wba). □

3 Proving FFTP

This section is devoted to the proof of the following theorem.

Theorem 3.1 Let G be a sufficiently large Artin group, defined over its standard generating set. Then G satisfies FFTP, and hence its set of geodesic words is regular.

It is proved in [10] that regularity of the set of geodesics follows from FFTP. We recall 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. Hence the property is easily deduced from the following result, which is an analogue of [5, Proposition 7.5] under our extended hypotheses; its proof appears at the end of this section.

Proposition 3.2 Suppose that G is an Artin group, defined over its standard generating set, and satisfying the hypotheses of Theorem 3.1.

(1) Let v, w be two geodesic words representing the same group element f, with l[v] ≠ l[w]. Then a single rightward critical sequence can be applied to v to yield a word ending in l[w].

(2) Let v be a freely reduced non-geodesic word with v = wa, a ∈ A and w geodesic. Then v admits a rightward length reducing sequence.

The proof of FFTP for large type groups in [8] followed a slightly different route. We are able to produce a more direct proof here, by using (with some adaptation) a combination of results from [5] as well as [8]. For the remainder of this section we assume that G satisfies the hypotheses of Theorem 3.1. First we prove the analogue of [8, Lemma 4.2]:

Lemma 3.3 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|. If wx and wx^{−1} are both non-geodesic then they admit rightward length reducing sequences. If l[w] and x form a braid pair, then the last move in both sequences is a β-move and the proof is as for [8, Lemma 4.2]. Otherwise l[w] and x must be a commuting pair, and the last move in both sequences is a κ-move.

Suppose that wx is reduced by a single κ-move x^{−1}ux → u. Then the suffix x^{−1}u of w contains one x^{−1} and no x, and every one of its generators commutes with x. On the other hand, the last move in the sequence that reduces wx^{−1} must be a κ-nove xvx^{−1} → v, for a suffix v of w that contains no x or x^{−1}, and which is preceded in w either by x or by a generator that forms a braid-pair with x. But it is not possible for w to have both x^{−1}u and v as suffices.

So both reducing sequences have length greater than 1, and have final moves x^{−1}ux → u and xux^{−1} → u, where u is the maximal suffix of w all of whose letters commute with x. Let w = vu. Then vx and vx^{−1} are both nongeodesic and the inductive hypothesis gives a contradiction. □

We recall from [8, Lemma 4.2] the notation for the process of reduction of a geodesic word v to its shortlex minimal representative ρ(v). This 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 2.2 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)}, which is the same as the i-th letter of v.

We shall also need the following new lemma.

Lemma 3.4 Let x, y ∈ X be a free pair of generators, and let f ∈ G.

(1) If some geodesic word representing f contains x^{±1} but neither y nor y^{−1} after the final x^{±1}, then the same is true of every geodesic word representing f.

(2) f cannot have distinct geodesic representatives, one of which ends in x^{±1} and the other in y^{±1}.

Proof: Any two geodesic representatives of f are connected by a sequence of τ-moves, all of which preserve the property described in (1). Part (2) follows immediately from part (1). □

We need an analogue of [8, Proposition 4.5]:

Proposition 3.5 Suppose that v, w are any two geodesic words representing the same element f ∈ G, and that l[v] ≠ l[w]. Then:

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

(2) If {l[v], l[w]} is a braid pair then the maximal 2-generator suffices of v and w involve generators with the same names as l[v] and l[w];

(3) If {l[v], l[w]} is a braid pair then any geodesic word representing f must end in l[v] or in l[w].

(4) If {l[v], l[w]} is not a braid pair, then it is a commuting pair, and some geodesic representative of f ends in l[v]l[w].

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

The proof of (1) is essentially the same as in [8, Proposition 4.5], but using Lemma 3.3. We prove the remaining parts by induction on |v|. Let l[ρ(v)] = c. Assume first that {l[v], l[w]} is a braid pair. Since the two generator case is straightforward, we assume that v involves at least three generators.

Suppose that the first τ-move of the final reduction v^{(n−1)} → v^{(n)} is a κ-move. Then {l[v], c} is a commuting pair, and so l[w] ≠ c. Then, by hypothesis, {l[w], c} is a free pair, and Lemma 3.4 (2) applied to ρ(v) and w, with {x, y} = {l[w], c}, gives a contradiction. So the first τ-move is a β-move, and {l[v], c} is a braid pair.

We cannot have l[pre[v^{(n−1)}]] = l[v] since otherwise we could use [8, Lemma 2.8] as before to deduce v^{(n−1)} ∈ W, which is false. So l[pre[v^{(n−1)}]] = c^{±1}, while l[v^{(n−1)}] = l[v].

Note that the maximal 2-generator suffix of ρ(v) involves generators with names those of c and l[v]. We claim that the same is true for v. It is true for v^{(n−1)} and, since v^{(n−1)} has a critical suffix, it is also true for pre[v^{(n−1)}]. And pre[v^{(n−1)}] is a geodesic representative of pre[v] that ends in c^{±1}. Let d := l[pre[v]]. If c = d^{±1} then our claim above is confirmed, so assume otherwise. Now Lemma 3.4 (2) applied to pre[v] and pre[v^{(n−1)}] implies that {c, d} is not a free pair. If {c, d} is a commuting pair then, by hypothesis, {l[v], d} is a free pair and now Lemma 3.4 (1) gives a contradiction when applied to pre[v] and pre[v^{(n−1)}]. So {c, d} is a braid pair, and the claim follows by applying (2) inductively to the representatives pre[v] and pre[v^{(n−1)}] of fl[v]^{−1}.

To complete the proof of (2), it remains to show that the maximal 2generator suffix of w also involves the generators with the same names as l[v] and c. If l[w] and c = l[ρ(w)] have different names, then the argument of the previous paragraph applies to w and ρ(w) to show that the maximal 2-generator suffix of ρ(w) (= ρ(v)) involves generators with the names of c and l[w], contrary to the first sentence of the previous paragraph. So l[w] = c. Let v′ be the result of applying the first τ-move in the reduction of v^{(n−1)} to v^{(n)} = ρ(v). Then l[v′] = l[ρ(v)] = c = l[w]. Let v′ = v′_{0}c^{j} and w = w_{0}c^{j} with j ≥ 1 as large as possible. Observe that the generators in the maximal 2-generator suffix of v′_{0} have names equal to those of c and l[v]. Let l[w_{0}] = d. If d = l[v]^{±1} then we are done. If d = c, then l[v′_{0}] = l[v]^{±1} and the required result follows by applying (2) inductively to v′_{0} and w_{0}.

We complete the proof of (2) by showing that d cannot have a name different from that of c and l[v], so suppose that it does. Now l[v′_{0}] is equal to c or to l[v′_{0}] = l[v]. Suppose first that l[v′_{0}] = c. Then Lemma 3.4 (2) applied to v′_{0} and w_{0} shows that {c, d} cannot be a free pair. If {c, d} is a commuting pair then, by hypothesis, {d, l[v]} is a free pair but, since the generators in the maximal 2-generator suffix of v′_{0} have names equal to those of c and l[v], Lemma 3.4 (1) applied to v′_{0} and w_{0} again gives a contradiction. Hence {c, d} is a braid pair, and applying (2) inductively to v′_{0} and w_{0} yields a contradiction.

Exactly the same argument (but with c replaced throughout by l[v])) excludes the possibility that l[v′_{0}] = l[v]. This completes the proof of (2), and (3) follows from (1) and (2).

It remains to prove (4), so assume that {l[v], l[w]} is not a braid pair. Then by Lemma 3.4 (2), {l[v], l[w]} is a commuting pair, and furthermore {l[v], c} cannot be a free pair. If {l[v], c} is a braid pair then we contradict (3) applied to v and ρ(v), so {l[v], c} must be a commuting pair. Hence c = l[pre[v^{(n−1)}]], and the first τ-move of the final reduction v^{(n−1)} → v^{(n)} is a κ-move. If c = l[w] then v^{(n−1)} ends in l[w]l[v], so (4) is true. Otherwise, we have c = l[pre[w^{(n−1)}]] and c, l[v] and l[w] all commute. Then (4) follows by applying (4) inductively to the geodesic representatives pre[pre[v^{(n−1)}]]l[v] and pre[pre[w^{(n−1)}]]l[w] of fc^{−1}. □

Finally we need to adapt [5, Proposition 7.3] to our new hypotheses as follows.

Proposition 3.6 Let f ∈ G and suppose that x_{i}, x_{j} ∈ X with i ≠ j form a braid pair. Then f has a unique left divisor LD_{ij}(f) ∈ G(i, j) of maximal length. Furthermore, if w is any geodesic word representing f, and u is the maximal {x_{i}, x_{j}}-prefix of w, then LD_{ij}(f) =_{G} ua^{r} for some r ≠ 0 with a ∈ {x_{i}^{±1}, x_{j}^{±1}} and |LD_{ij}(f)| = |u| + r.

Similarly, f has a unique right divisor RD_{ij}(f) ∈ G(i, j) of maximal length, to which the corresponding results apply.

Proof: Order the monoid generators of G such that x_{i}^{±1}, x_{j}^{±1} (in some order) come first, and let w′ be the shortlex least representative of f using this ordering with maximal {x_{i}, x_{j}}-prefix u′.

Let w be an arbitrary geodesic representative of f and let u be the maximal {x_{i}, x_{j}}-prefix of w. We consider the process of reducing w to its shortlex form w′ by considering each letter of w in turn, and reducing the prefix ending in that letter to shortlex form. Suppose that w_{0} = w, that w reduces through the sequence of words w^{(1)}, w^{(2)}, … to w^{(n)} = w′ and that u_{0} = u, u_{1}, …, u_{n} = u′ is the corresponding sequence of maximal {x_{i}, x_{j}}-prefixes.

By [8, Proposition 3.3], the prefix of length k in w_{k} is either already shortlex reduced, or can be reduced to shortlex form with a single leftward lex reducing sequence. Such a reduction cannot change a letter of u_{k} to a letter with name not in {x_{i}^{±1}, x_{j}^{±1}}, since that would be shortlex increasing. So either u_{k+1} = u_{k} or u_{k+1} is the shortlex reduction of u_{k}a for some a ∈ {x_{i}^{±1}, x_{j}^{±1}}.

Suppose that u_{k+1} ≠ u_{k}. Without loss of generality we suppose that a has name x_{i} (rather than x_{j}). Let b be the letter in w^{(k+1)} immediately after u_{k+1}.

We first consider the case where {a, b} is a braid pair, and so the move that appends the letter a to u_{k} is a β-move. Then by [8, Lemma 3.7(2)] the next letter other than b in w^{(k+1)} is a^{±1}. So if subsequent reductions occur that increase the length of the maximal {x_{i}, x_{j}}-prefix, then they all involve a penultimate β-move involving a and b, and so they all adjoin the same letter a to the maximal i, j-generator prefix. (We can’t adjoin a and then a^{−1} or the word would not be geodesic!)

Suppose, on the other hand, that {a, b} is a commuting pair, and so the move that appends the letter a to u_{k} is a κ-move. Then by hypothesis, {b, x_{j}} is a free pair. So, applying Lemma 3.4 (1), we see that, in this case too, all subsequent reductions that increase the length of the maximal {x_{i}, x_{j}}-prefix must adjoin the same letter a.

So we have u′ =_{G} ua^{r} with |u′| = |u| + r, as claimed. Since this equation holds for any choice of w, we have proved that (u′)_{G} is the unique longest left divisor of f in G(i, j). The proof for the maximal right divisor is similar. □

We are now ready to prove Proposition 3.2, from which FFTP follows.

Proof of Proposition 3.2: The proof of (1) is by induction on |v|. If {l[v], l[w]} is a braid pair, then the proof is similar to that of [5, Proposition 7.5], but using Propositions 3.6 and 3.5 in place of [5, Proposition 7.3] and [8, Proposition 4.5]. Lemma 3.4 (2) implies that {l[v], l[w]} cannot be a free pair, so it remains to deal with the case where {l[v], l[w]} is a commuting pair.

If l[w] = l[pre[v]] then the single κ-move l[w]l[v] → l[v]l[w] has the required effect on v. Otherwise, by Proposition 3.5 (4), there is a geodesic representative of f ending in l[w]l[v]. By induction, a rightward critical sequence S can be applied to pre[v] to yield a word ending in l[w], and this can be followed by the κ-move l[w]l[v] → l[v]l[w] (which must be combined with the final move of S should that be also a κ-move) to yield the required sequence for v.

This completes the proof of (1) and, if v is as in (2), then w_{G} has a geodesic representative ending in a^{−1}, and so (2) follows from (1). □

References

[1] K.I. Appel, On Artin groups and Coxeter groups of large type, Contemporary Mathematics 33 (1984) 50–78.

[2] K.I. Appel and P.E. Schupp, Artin groups and infinite Coxeter groups, Invent. Math. 72 (1983) 201–220.

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

[4] A. Chermak, Locally non-spherical Artin groups, J. Algebra 200 (1998) 56–98.

[5] L. Ciobanu, D.F. Holt and S. Rees, Rapid decay and Baum-Connes

for large type Artin groups, http://arxiv.org/abs/1203.1198v2,

preprint 2012.

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

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

[8] D.F. Holt and S. Rees, Artin groups of large type are shortlex automatic with regular geodesics, Proc. London Math. Soc 104 (2012) 486–512.

[9] D.F. Holt, KBMAG—Knuth-Bendix in Monoids and Automatic Groups, software package (1995), available from

(http://www.maths.warwick.ac.uk/~dfh/download/kbmag2/).

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

[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. D.F.Holt@warwick.ac.uk

Sarah Rees, School of Mathematics and Statistics, University of Newcastle, Newcastle NE1 7RU, UK. Sarah.Rees@ncl.ac.uk