REWRITING SYSTEMS IN SUFFICIENTLY LARGE ARTIN–TITS GROUPS

EDDY GODELLE AND SARAH REES

Abstract. A conjecture of Dehornoy claims that, given a presentation of an Artin-Tits group, every word that represents the identity can be transformed into the trivial word using the braid relations, together with certain rules (between pairs of words that are not both positive) that can be derived directly from the braid relations, as well as free reduction, but without introducing trivial factors ss^{−1} or s^{−1}s. This conjecture is known to be true for Artin-Tits groups of spherical type or of FC type. We prove the conjecture for Artin–Tits groups of sufficiently large type.

1. Introduction

Let Γ_{0} be a labelled finite complete simplicial graph with vertex set S, edge set E and label map m : E → ℕ_{≥2} ∪ {∞}. The associated Coxeter graph Γ is then obtained from Γ_{0} by removing edges labelled by 2, and unlabelling edges whose label is 3. One associates with Γ_{0} an Artin–Tits group (also known as Artin group), denoted by A(Γ_{0}) (or by A(Γ)), defined by the following Artin group presentation:

⟨ S |\underbrace{sts ⋯}_{m} = \underbrace{tst ⋯}_{m} ; s, t ∈ S and m(\{s, t\}) = m ≠ ∞⟩ .

For instance, if Γ_{0} is a complete graph with all edges labelled with ∞, then Γ is equal to Γ_{0} and the group A(Γ) is the free group on S. Alternatively, if all the labels in Γ_{0} are equal to 2, then Γ is completely disconnected and the group A(Γ) is the free abelian group on S. More generally, considering graphs Γ_{0} whose labels are 2 or ∞ only, one obtains the so-called right-angled Artin groups (RAAG for short), which are the object of numerous articles. Finally, starting from any (undirected) Dynkin diagram and replacing doubled and tripled edges by edges labelled by 4 and 6, respectively, one obtains a Coxeter graph and therefore an Artin group, which is helpful in the study of the associated Coxeter group and the associated Hecke algebra. For instance, if Γ is an unlabelled line and S has cardinality n, then A(Γ) is the braid group on n + 1 strings.

So, the family of Artin groups contains various groups that are of interest. In the present article, we mainly focus on Artin groups where all the labels in Γ_{0} are either equal to ∞ or greater or equal to 3. These groups are called large type Artin groups and have been considered by various authors [1, 2, 3, 11].

1991 Mathematics Subject Classification. 20B30, 20F55, 20F36.

Key words and phrases. Artin–Tits groups, large type, word problem.

Work partially supported by GDRI 571: French-British-German network in Representation theory.

Artin groups are badly understood in general and few results are known. For instance, the word problem is an open problem for Artin groups, although it has been solved for particular subfamilies, including all those introduced above. In general, starting from a finite presentation of a group, there is no general strategy to solve its word problem. From the finite presentation, we can always derive a finite number of elementary transformations on words (that replace some factors of words by other words – see the Preliminary Section 2.1 for the definition of a factor), each of which transforms any word to which it applies into another word with strictly shorter length. And, whenever a sequence of such transformations is applied to an input word w, because the sequence of word lengths is strictly decreasing, this process must stop after at most |w| such elementary transformations. Where the group presentation is hyperbolic, the resulting word is the empty word if and only if the initial word represents the identity element of the group. So, using the bound on the number of possible successive elementary transformations, one gets a solution to the word problem. But, when the group presentation is not hyperbolic, there must be representatives of the identity element that are not reduced by the finite set of transformations to the empty word, and hence the process does not solve the word problem.

Unfortunately, except in the case of free groups, Artin groups are not hyperbolic as they contains copies of ℤ^{2}, so the approach above does not work to solve the word problem in Artin groups. However, one might expect that an alternative family of elementary transformations could lead to a solution to the word problem for any Artin group. It is natural to look for a solution with a set of elementary transformations on words that do not increase length. For instance, the solution to the word problem obtained in [15] for right-angled Artin groups can be seen as a special example of this strategy.

Definition 1.1. For a finite presentation ⟨S, R⟩, we define special transformations on finite words on S ∪ S^{−1} as follows:

- type 0 (resp. ∞): Remove (resp. insert) some pair s^{−1}s or ss^{−1}, where s is a letter of S,

- type 1: Replace some factor v by u, or v^{−1} by u^{−1}, where u = v is a relation of R.

Since the presentation is finite, the set of special transformations is finite. But note that, throughout the paper, we shall abuse notation and consider relations u = v and v = u to be the same relation, and hence, in particular, we shall also consider that there are four (rather than two) type 1 transformations associated with each relation u = v.

From now on, for a set X of types of transformations on words, we write w ⇝^{X}_{R} w′ if w can be transformed to w′ using transformations of type X. Thus, for a group G with finite presentation ⟨S, R⟩ and for every word w on S ∪ S^{−1}, we have

(1.1)  w ⇝^{0,1,∞}_{R} ε ⟺ \overline{w} = 1,

where ε is the empty word and \overline{w} is the image of w in the group G. Of course here we do not get a solution to the word problem as long as we do not have a bound on the length of the path from w to ε using relations of types 0, 1, ∞ — such a bound does not exist in general. If one wants to obtain a set of elementary transformations that do not increase the length then it is legitimate to include transformations of type 0 or 1, whereas transformations of type ∞ have to be avoided. Clearly if w ⇝^{0,1}_{R} ε then \overline{w} = 1 but the converse is not true in general, nor in the special case of Artin group presentations (see [8] for an example). It is therefore natural to address the question of whether one may add some other special transformations to obtain an equivalence for all Artin groups. Two partial results on that direction appear recently in the literature [8, 11].

In [11] a family of elementary operations, called of type β, is introduced. A special case of the main result proved in [11] is that for any Artin group presentation ⟨S, R⟩ of large type and for every word w on S ∪ S^{−1}, we have

(1.2)  w ⇝^{0,1,β}_{R} ε ⟺ \overline{w} = 1.

The type β operations do not increase the length, and so this leads to a solution of the word problem. However type β operations are not finite in number (even if for a given length only a finite number of them can be applied) and given a word, it is not easy to detect where a type β transformation can be applied. Moreover, as shown in [11], one cannot expect that the above equivalence holds for every Artin group.

Now comes the crucial point. In [8], some special transformations of type 2 are introduced, falling into two types called type 2r (“type 2-right”) and type 2l (“type 2-left ), which allow some limited substitution using unsigned words. These are defined as follows:

Definition 1.2. Let G = ⟨S, R⟩ be a group, and suppose that u = v is a relation in R, between two positive words u, v. Suppose that u can be written as a concatenation u_{1}u_{2} and v as a concatenation v_{1}v_{2}. Suppose that w is a word over S ∪ S^{−1}. We define a transformation that replaces a factor v_{1}^{−1}u_{1} of w by v_{2}u_{2}^{−1} to be of type 2r (“type-2-right”), provided that both v_{1} and u_{1} are non-empty. We define a transformation that replaces a factor v_{2}u_{2}^{−1} of w by v_{1}^{−1}u_{1} to be of type 2l (“type-2-left”), provided that both v_{2} and u_{2} are non-empty.

Basically, the rules of type 2 are those directly derived from braid relations for which the left hand side of the rule is unsigned. Note that in the special case where all four of u_{1}, u_{2}, v_{1}, v_{2} are non-empty, the associated transformations of types 2l and 2r are inverse to each other.

Example 1.3. Consider a dihedral Artin group with S = {s, t} and m_{s,t} = 3. Then the transformations

s^{−1}t^{−1}s → ts^{−1}t^{−1} and t^{−1}s^{−1}t^{−1}s → s^{−1}t^{−1}

are both of type 2r, the first one with u_{1} = s, u_{2} = ts, v_{1} = ts and v_{2} = t, and the second one with u_{1} = s, u_{2} = ts,v_{1} = tst and v_{2} empty. Then, the reverse of the first,

ts^{−1}t^{−1} → s^{−1}t^{−1}s

is type 2l, but the reverse of the second,

s^{−1}t^{−1} → t^{−1}s^{−1}t^{−1}s

is not of type 2l.

It is immediate that the set of transformations of type 2 is finite, and therefore so is the set of transformations of types 0, 1 or 2. Moreover, it is clear that w ⇝^{0,1,2}_{R} ε implies \overline{w} = 1. The reader may wonder why operations of type 2 should be considered of special interest. The explanation comes from the case of spherical type Artin presentations (that is, those based on finite type Dynkin diagrams, and so in particular all braid groups).

In this case, w ⇝^{0,1}_{R} ε ⟺ \overline{w} = 1 does not hold,but w ⇝^{0,2}_{R} ε ⟺ \overline{w} = 1 does [8]. Further, in such a group, a sequence of operations of types 2r (resp. 2l) and 0 allows one to transform any (unsigned) word w into a word of the form w_{1}w_{2}^{−1} (resp. w_{1}^{−1}w_{2}) for which w_{1}, w_{2} are positive words with no common right (resp. left) divisor in the associated Artin-Tits monoid. (See [8] and Propositions 2.6 and 2.8 below.)

The result we are going to prove here is

Theorem 1.4. For every sufficiently large Artin-Tits presentation ⟨S, R⟩, and any word w ∈ S ∪ S^{−1},

(1.3)  w ⇝^{0,1,2}_{R} ε ⟺ \overline{w} = 1

Our definition of sufficiently large type for an Artin-Tits presentation is taken from [12], but we repeat it as Definition 3.1; note that this definition includes all presentations of large type.

It is conjectured in [9, Conj. 3.28] that the equivalence of Theorem 1.4 holds for all Artin-Tits presentations. The conjecture is repeated in [8, Conj. 1.6], where it is proved for Artin-Tits presentations of spherical and FC types.

Definition 1.5. A finite presentation ⟨S, R⟩ of a group G satisfies Property H if the equivalence w ⇝^{0,1,2}_{R} ε ⟺ \overline{w} = 1 holds for every word w on S ∪ S^{−1}.

So, we can rephrase [8, Conj. 1.6] as a claim that Property H is satisfied by every Artin presentation, and Theorem 1.4 as a verification of that claim for any Artin presentation of sufficiently large type. The conjecture was already proved in [8] for spherical type Artin groups, and then more generally for all Artin groups of FC type, and so all right-angled Artin groups. But most Artin groups of sufficiently large type (and in particular those of large type) are not of FC type, and so are not covered by the results of [8]; so certainly our result provides a new family of Artin groups for which the conjecture is valid. We prove the result for groups of sufficiently large type as an extension of the result for groups of large type, recognising that the first of those two classes of groups can be built out of the second in the same way that the groups of FC type can be built out of the groups of spherical type; so this part of our proof follows the proof of [8]. In order to obtain their result for Artin groups of FC type, the authors of [8] proved that a stronger but more technical property, namely Property H^{#} (defined in [8]), is satisfied by Artin groups of spherical type. We will prove that this property holds for Artin groups of large type. Then, combining this result with [8, Prop. 2.14] we will derive the following.

Theorem 1.6. Let T be the family of those Artin-Tits presentations (S, R) for which every connected full subgraph of the Coxeter graph Γ without an ∞-labelled edge is either of spherical type or of large type. Then every presentation (S, R) in T satisfies Property H^{#} and (therefore) Property H. Hence, for every word w on S ∪ S^{−1},

w ⇝^{0,1,2}_{R} ε ⟺ \overline{w} = 1.

The reader should note that transformations of type 2 can increase the length of words and therefore our result does not lead directly to a solution to the word problem. However, whenever we can prove a bound on the maximal number of iterations of special transformations we can derive a solution to the word problem. We might expect that such a bound could be found in all cases, even if a general argument for that remains to be found. The main argument of our proof will consist of a proof that that any transformation of type β can be decomposed as a sequence of type 2 and type 1 transformations. The remainder of this article is organised as follows. Section 2 is devoted to the proof of Property H for Artin-Tits groups of large type, stated at the end of the section as Corollary 2.21. Section 3 considers Artin-Tits groups of sufficiently large type. Those groups are introduced at the beginning of Section 3, and characterized in Section 3.1 as a particular class of Artin groups closed under amalgamation over standard parabolic subgroups. Property H^{#} is defined in Section 3.3, and Proposition 3.5 [8, Proposition 2.14] is stated, which will be used to extend the proof of Property H^{#} for large type groups to a larger class of Artin-Tits groups, which (according to the given characterization) must include all those of sufficiently large type. Section 3.4 introduces the machinery of critical factorizations and critical sequences of transformations for large type groups from [11]. Section 3.5 is devoted to the proof that Artin groups of large type satisfy Property H^{#}, and the final section, Section 3.6, to the proofs of Theorems 1.6 and 1.4.

We would like to acknowledge some helpful comments from the referee, which led us to introduce property H^{+}, strengthen Corollary 2.21 as Corollary 2.24, and prove Proposition 3.3.

2. Property H For Artin-Tits groups of large type

In this section we prove that Property H holds for Artin-Tits group of large type. Throughout this section, we fix a Coxeter graph Γ. We denote by Γ_{0} the associated labelled full simplicial graph, as defined in the introduction. We assume that the associated Artin-Tits group is of large type; recall that this means that any edge label is either infinite or at least 3. In order to prove the result, we start with the crucial notion of a critical word introduced in [11]. As before, by S we denote the set of vertices of Γ

2.1. Preliminaries. We start with some terminology. Let S be a finite set. We denote by (S ∪ S^{−1})^{∗} the set of words on S ∪ S^{−1}. A word w on S ∪ S^{−1} will be called positive if it is written over S. It will be called negative if it is written over S^{−1}. A signed word is a word that is either positive or negative. Some words are neither positive nor negative; when this is the case, we say that the word w is unsigned. We denote by w^{−1} the word that is the formal inverse of w. If G is a group generated by S, a element g of G will be called positive (relative to S) when it possesses a positive representative word over S.

A word v on S ∪ S^{−1} will be called a factor of a word w if the word w can be decomposed with w = w_{1}vw_{2} for some words w_{1}, w_{2}.

A word w is called freely reduced if it does not contain a factor of the form either ss^{−1} or s^{−1}s for some s in S. Equivalently, w is freely reduced if no operation of type 0 can be applied.

When x and y are two words and m is a positive integer, we denote by [x, y, j⟩ the word xyxy ⋯ obtained as the alternating concatenation of the words x and y that concatenates j words, the first being x. Hence [x, y, 5⟩ = x[y, x, 4⟩ = xyxyx. Similarly we denote by ⟨y, x, j] the word ⋯ yxyx obtained as the alternating concatenation of the words x and y, that concatenates j words, the last being x. So ⟨y, x, 6] = yxyxyx. In particular [x, y, j⟩ = ⟨y, x, j] or [x, y, j⟩ = ⟨x, y, j] depending on whether j is odd or even. For instance, [x, y, 5⟩ = xyxyx = ⟨y, x, 5] but [x, y, 4⟩ = xyxy = ⟨x, y, 4].

Finally, we say that a positive word is square-free if it does not contain a factor of the form ss for any s in S. Now, for a word w, we denote by p̃(w) the length of the longest square-free positive factor of w. Similarly we denote by ñ(w) the length of the longest negative factor of w whose formal inverse is square-free.

2.2. Dihedral Artin-Tits groups. In the case where Γ has only 2 vertices s, t, the associated Artin group A(Γ_{0}) is called a dihedral Artin group. Indeed, in the case where m = m({s, t}) ≠ ∞, if one adds the relations s^{2} = 1 and t^{2} = 1 to the presentation of A(Γ_{0}), then one obtains the associated Coxeter group. On the other hand the obtained presentation is the one of a dihedral group of order 2m. In particular the latter group is finite. Following [13], for a word w we set p(w) = min(p̃(w), m) and n(w) = min(ñ(w), m).

In order to state the next result, let us introduce a restricted version of the operation of type 2.

Definition 2.1. For a finite presentation of a group ⟨S, R⟩, we define special transformations of type 2^{⋆} on words on S ∪ S^{−1} to be special transformations of type 2 for which, following the notation of Definition 1.2,

- in type 2r with w = w_{1}v^{−1}v′w_{2}, the word v is the greatest left common factor of the words vu and vw_{1}^{−1} and the word v′ is the greatest left common factor of the words v′u′ and v′w_{2};

- in type 2ℓ with w = w_{1}vv′^{−1}w_{2}, the word v is the greatest right common factor of the words uv and w_{1}v and the word v′ is the greatest right common factor of the words u′v′ and w_{2}^{−1}v′.

Example 2.2. Consider a dihedral Artin group with S = {s, t} and m_{s,t} = 4. Consider the word t^{2}sts^{−1}t. Then, we have t^{2}sts^{−1}t ⇝^{2}_{R} t^{2}t^{−1}s^{−1}tstt, but this transformation is not of type 2^{⋆} because v = st; uv = stst and w_{1}v = t^{−1}tst. So the word tst is a greater common right divisor of uv and w_{1}v than v. However, ttsts^{−1}t ⇝^{2^{⋆}}_{R} ts^{−1}tstt. The reader should note that in both cases the last letter of w_{1} is t, but in the first case tv is square-free, whereas in the second case tv is not.

For the remainder of this section, we assume that Γ_{0} has only 2 vertices s, t (so S = {s, t}), and set m = m_{s,t}. So the group A(Γ_{0}) is a dihedral Artin group. We set

Ω(Γ_{0}) = {w ∈ (S ∪ S^{−1})^{∗} | w is freely reduced with max(p(w), n(w)) < m}

The reader should note that the definition of Ω(Γ_{0}) ensures that operations of types 0 or 1 cannot be applied to words in Ω(Γ_{0}); only operations of type 2 can apply. Moreover, if w belongs to Ω(Γ_{0}), then p̃(w) = p(w) and ñ(w) = n(w).

For a non-empty word w in Ω(Γ_{0}), we define the ⋆-decomposition of w to be the unique sequence (v_{1}, …, v_{k}) of non-trivial words such that w = v_{1} ⋯ v_{k} and each factor v_{i} is the maximal square-free signed left factor of the word v_{i} ⋯ v_{k}.

Proposition 2.3. Let w be a non-empty word that belongs to Ω(Γ_{0}), and denote by (v_{1}, ⋯, v_{k}) the ⋆-decomposition of w. Assume that the word w′ is obtained from w by an operation of type 2^{⋆}. Then, w′ belongs to Ω(Γ_{0}) too. Moreover, there exists a subscript i such that the ⋆-decomposition of w′ is (v_{1}, ⋯, v_{i−1}, u_{i}, u_{i+1}, v_{i+2}, ⋯, v_{k}) and the 2^{⋆}-operation transforms w into w′ by replacing the factor v_{i}v_{i+1} of w by the word u_{i}u_{i+1}.

Proof. Since the Artin group is assumed dihedral, the set R consists of a single relation [s, t, m⟩ = [t, s, m⟩. Write w = w_{1}w_{2}w_{3} and w′ = w_{1}w′_{2}w_{3}, where w′_{2} is the factor of w′ obtained from the factor w_{2} of w by applying an operation of type 2^{⋆}. We have either w_{2} = v^{−1}v′ or w_{2} = vv^{′−1}. In the first case, w′_{2} = uu′^{−1} where vu = v′u′ is the unique relation in R. In the second case, w′_{2} = u^{−1}u′ where uv = u′v′ is the unique relation in R.

Assume the first case. The arguments for the second case are similar and left to the reader. We can assume without restriction that v = [s, t, j⟩ and v′ = [t, s, ℓ⟩ for some j, ℓ < m. Then vu = [s, t, m⟩ and v′u′ = [t, s, m⟩. Since the words v_{1}, ⋯, v_{k} are signed words and any word v_{i}v_{i+1} is either unsigned or not square-free, there has to exist a subscript i so that v^{−1} is a right factor of v_{i} and v′ is a left factor of v_{i+1}. Now the operation that transforms w into w′ is not just of type 2 but actually of type 2^{⋆}. This imposes v^{−1} = v_{i} and v′ = v_{i+1}. For a in S = {s, t}, denote by â the other letter of S. Denote by a and a′ the last letter of v and v′, respectively. Then, the first letter of u is â and the last letter of u′^{−1} is (â′)^{−1}. Denote by c the last letter c of w_{1}, that is, the last letter of v_{i−1}, and by d the first letter of w_{3}, that is, the first letter of v_{i+2}.

The only cases where w′ could not be freely reduced would be if either c = â^{−1} or d = â′. If c were equal to â^{−1} then we would have vc^{−1} = [s, t, j + 1⟩ with j + 1 ≤ n(w) < m. so, vc^{−1}, that is, vâ, would be a common left factor of vw_{1}^{−1} and vu, contradicting the fact that the transformation is of type 2^{⋆}. So c ≠ â^{−1}. Similarly, d ≠ â′. Hence, w′ is a freely reduced word.

We prove now that max(p(w′), n(w′)) < n. This will imply that w′ belongs to Ω(Γ_{0}). Assume that one of the words [s, t, m⟩ and [s, t, m⟩ or their inverses is a factor of w′. Since w belongs to Ω(Γ_{0}), this word cannot be a factor of w_{1} or of w_{3}. On the other hand, it can not be a factor of w′_{2}. Then that word has to either overlap w_{1} and w′_{2}, or to overlap w′_{2} and w_{3}. In the first case, it has to contain the word câ as a factor, which implies that c = a. In the second case it has to contain the word d^{−1}â′ which implies that d = a^{′−1}. Either of these would contradict that fact that w is freely reduced. We deduce that max(p(w′), n(w′)) < m, and hence w′ belongs to Ω(Γ_{0}).

From c ≠ a and d ≠ a^{′−1}, we further deduce that neither v_{i−1}â nor u′^{−1}d can be a square-free signed word. Hence (v_{1}, ⋯, v_{i−1}, u, u′^{−1}, v_{i+2}, ⋯, v_{k}) is the ⋆-decomposition of w′. □

From Proposition 2.3 we deduce that

Corollary 2.4. Assume that A(Γ_{0}) is a dihedral Artin group. Then, Ω(Γ_{0}) is closed under the operations of type 2^{⋆}. Moreover, if w, w′ belong to Ω(Γ_{0}) then

w ⇝^{2^{⋆}}_{R} w′ ⟺ w′ ⇝^{2^{⋆}}_{R} w.

2.3. Normal decomposition. In the previous section we have seen that, in the case of a dihedral Artin-Tits group, the set Ω(Γ_{0}) is closed under operations of type 2^{⋆}. Here we study the connected components of Ω(Γ_{0}) under the 2^{⋆} operation.

Proposition 2.5. Assume that A(Γ_{0}) is a dihedral Artin-Tits group. Assume that w and w′ belong to Ω(Γ_{0}), then,

w ⇝^{2^{⋆}}_{R} w′ ⟺ w and w′ represent the same element in A(Γ_{0}).

To prove this result we use the fact that dihedral Artin-Tits groups are contained in the more general family of spherical type Artin-Tits groups. We recall that an Artin-Tits group is of spherical type when its associated Coxeter group is finite, which is the case for dihedral Artin-Tits groups with m < ∞ as explained in the previous section. The crucial argument is the following.

Proposition 2.6. [5] Let A(Γ_{0}) be a spherical type Artin group, and let g ∈ A(Γ_{0}). Then there exists a unique pair of positive elements (g_{1}, g_{2}) such that (1) g = g_{1}g_{2}^{−1} and (2) whenever h_{1}, h_{2} are positive elements with g = h_{1}h_{2}^{−1}, then there exists a positive element h with h_{1} = g_{1}h and h_{2} = g_{2}h.

The above decomposition g_{1}g_{2}^{−1} is called the left normal decomposition of g. The following is an immediate consequence of the above proposition.

Proposition 2.7. Assume that A(Γ_{0}) is a spherical type Artin group. Let g belong to A(Γ_{0}). Assume that (w_{1}, w_{2}) is a pair of positive words so that w_{1}w_{2}^{−1} is a word representative of g. Denote by g_{1} and g_{2} the (positive) elements of A(Γ_{0}) represented by w_{1} and w_{2} respectively. Then, the following are equivalent:

(1) g_{1}g_{2}^{−1} is not the left normal decomposition of g,

(2) there exist two distinct words w and w′ so that w_{1}w_{2}^{−1} ⇝^{1}_{R} w ⇝^{0}_{R} w′.

Using this property, we can deduce the following.

Proposition 2.8. Let A(Γ_{0}) be a dihedral Artin-Tits group, and suppose that w ∈ Ω(Γ_{0}). Denote by g the element of A(Γ_{0}) represented by g and by (g_{1}, g_{2}) the pair of positive elements of A(Γ_{0}) corresponding to the left normal decomposition of g.

Then, there exists a pair of positive words (w_{1}, w_{2}) so that the words w_{1} and w_{2} represent g_{1} and g_{2}, respectively, and

w ⇝^{2^{⋆}}_{R} w_{1}w_{2}^{−1}.

Proof. Let (v_{1}, …, , v_{k}) be the ⋆-decomposition of w. Say that the pair (i, j), with i < j, is an inversion of the word w if v_{i} is a negative word whereas v_{j} is a positive word. Denote by Inv(w) the number of inversions of the word w.

Assume first Inv(w) = 0. Then there exists an index i such that v_{1} ⋯ v_{i} is a positive (or empty) word and v_{i+1} ⋯ v_{k} is negative (or empty). Since w ∈ Ω(Γ_{0}), it follows (immediately from the definition of Ω(Γ_{0})) that no operation of type 1 or 0 can be applied to w. Hence, we deduce from Proposition 2.7 that the words v_{1} ⋯ v_{i} and (v_{i+1} ⋯ v_{k})^{−1} represent g_{1} and g_{2}, respectively.

So now suppose that Inv(w) ≠ 0. Then there exists an index i such that v_{i} is a negative word whereas v_{i+1} is positive. By definition of the decomposition v_{1} ⋯ v_{k}, an operation of type 2^{⋆} can be applied to w to replace the word v_{i}v_{i+1} by the word u_{i}u_{i+1} for which v_{i+1}u_{i+1}^{−1} = v_{i}^{−1}u_{i} is the unique relation in the presentation of the group A(Γ_{0}). We obtain the word w′ = v_{1} ⋯ v_{i−1}u_{i}u_{i+1}v_{i+2} ⋯ v_{k} . By Proposition 2.3, the word w′ remains in Ω(Γ_{0}) and (v_{1}, …, v_{i−1}, u_{i}, u_{i+1}, v_{i+2}, …, v_{k}) is the ⋆-decomposition of w′. It is immediate that Inv(w′) = Inv(w) − 1. Repeating the argument, we deduce there exists a word w′′ in Ω(Γ_{0}) such that w ⇝^{2^{⋆}}_{R} w′′ and Inv(w′′) = 0. Denote by (u_{1}, …, u_{k}) the ⋆-decomposition of the obtained word w′′. By the first case, there exists an index i such that the words u_{1} ⋯ u_{i} and (u_{i+1} ⋯ u_{k})^{−1} represent g_{1} and g_{2}, respectively. This proves the proposition. □

We can now prove Proposition 2.5.

Proof of Proposition 2.5. Assume that w and w′ belong to Ω(Γ_{0}).

Certainly if w ⇝^{2^{⋆}}_{R} w′, then w and w′ represent the same element in A(Γ_{0}).

Conversely, assume w and w′ represent the same element g, and denote its left normal decomposition by g_{1}g_{2}^{−1}. By Proposition 2.8, there exist positive words w_{1}, w′_{1}, w_{2}, w′_{2} so that (a) w_{1} and w′_{1} represent g_{1}; (b) w_{2} and w′_{2} represent g_{2}; (c)

w ⇝^{2^{⋆}}_{R} w_{1}w_{2}^{−1} and w′ ⇝^{2^{⋆}}_{R} w′_{1}w′_{2}^{−1}.

From (c) and Corollary 2.4 we have w′_{1}w′_{2}^{−1} ⇝^{2^{⋆}}_{R} w′. By (a), (b) and [14], we have w_{1} ⇝^{1}_{R} w′_{1} and w_{2} ⇝^{1}_{R} w′_{2}. Since w and w′ belong to Ω(Γ_{0}), the words w_{1}w_{2}^{−1} and w_{1}w_{2}^{−1} must too, by Corollary 2.4, and hence no non-trivial operations of type 1 can be applied to them or to their factors. Hence, w_{1} = w′_{1} and w_{2} = w′_{2}. It follows

that w ⇝^{2^{⋆}}_{R} w_{1}w_{2}^{−1} ⇝^{2^{⋆}}_{R} w′. □

2.4. Critical words. For all of this section, we assume that A(Γ_{0}) is a dihedral Artin group with S = \{s, t\} and m = m_{s,t} ≠ ∞. Set Δ = \overline{[s, t, m⟩} = \overline{[t, s, m⟩}. Then, Δ\overline{s}^{±1} = \overline{δ(s)}^{±1}Δ and Δ\overline{t}^{±1} = \overline{δ(t)}^{±1}Δ, where δ is the permutation of S defined by δ(s) = \overline{s^{Δ}},δ(t) = \overline{t^{Δ}}, acting as the identity when m is even, and swapping s and t when m is odd. The map δ naturally extends to a involution δ on (S ∪ S^{−1})^{∗} such that for every word v on (S ∪ S^{−1})^{∗} one has Δ\overline{v} = \overline{δ(v)}Δ.

We recall that for a group G generated by a set S, a geodesic word representative of an element g is a representative word of g over S ∪ S^{−1} that is of minimal length amongst the representative words of g. Given an arbitrary Artin-Tits group, it is an open question to obtain an algorithm that for each word returns a geodesic word representing the same element. However, in the case of dihedral Artin-Tits groups, and in the more general case of Artin-Tits groups of large type, a positive answer has been obtained in [13] and in [11], respectively.

More precisely, it is proved in [13], in a dihedral group A_{S}, a freely reduced word w over s, t is geodesic if and only if p(w) + n(w) ≤ m. In addition in [11, Section 2], the authors introduced the notion of critical word. A critical word may be signed or unsigned; for now we restrict to unsigned critical words.

Definition 2.9. Assume A(Γ_{0}) is a dihedral Artin group. A freely reduced unsigned geodesic word w with p(w) + q(w) = m is called an unsigned critical word if either

w = [x, y, p⟩ w′ [z, t, q⟩^{−1}

or

w = [x, y, q⟩^{−1} w′ [z, t, p⟩

with {x, y} = {z, t} = S, p = p(w) and q = q(w).

Obviously the conditions p(w) = p, n(w) = n impose some restrictions on the word w′.

Recall that [x, y, p⟩ = ⟨x′, y′, p] where {x, y} = {x′, y′}, and that [z, t, q⟩ = ⟨z′, t′, q] where {z, t} = {z′, t′}. Now, let w = [x, y, p⟩ w′ [z, t, q⟩^{−1} be a word over (S ∪ S^{−1}) such that p + q = m. One has

\overline{w} = \overline{[x, y, p⟩ w′ [z, t, q⟩^{−1}} = \overline{⟨x, y, q]^{−1} Δ w′ [z, t, q⟩^{−1}} = \overline{⟨x, y, q]^{−1} δ(w′)Δ [z, t, q⟩^{−1}}

= \overline{⟨x, y, q]^{−1} δ(w′) ⟨z, t, p]}

Set

τ ([x, y, p⟩ w′ [z, t, q⟩^{−1}) = ⟨x, y, q]^{−1} δ(w′) ⟨z, t, p];

then one has \overline{τ(w)} = \overline{w}. So, w is unsigned and geodesic if and only if τ(w) is. Moreover, w is an unsigned critical word with p = p(w) and q = q(w) if and only if τ(w) is an unsigned critical word with p = p(τ(w)) and q = q(τ(w)). In this case, we also set

τ (⟨x, y, q]^{−1} δ(w′) ⟨z, t, p]) = [x, y, p⟩ w′ [z, t, q⟩^{−1}.

Then τ is an involution over the set of unsigned critical words.

The above is proved, together with other properties of critical words in [11, Proposition 2.1]. From those properties we shall also need the following, in Section 3.5:

Lemma 2.10. Assume that A(Γ_{0}) is a dihedral Artin group with generating set S = {s, t}. Let w be an unsigned critical word. The rightmost letter of w is s^{±1} if and only if the rightmost letter of τ(w) is t^{∓1}.

Lemma 2.11. Assume A(Γ_{0}) is a dihedral Artin group with generating set S = {s, t}. Let w be an unsigned critical word. Then w ⇝^{2^{⋆}}_{R} τ(w).

Proof. The words w and τ(w) are unsigned critical words. In particular p(w) + q(w) = m with p(w) ≠ 0 and q(w) ≠ 0. So w is a freely reduced word so that p(w) < m and q(w) < m, and hence w belongs to Ω(Γ_{0}). But τ(w) is also a reduced word with p(τ(w)) = p(w) < m and q(τ(w)) = q(w) < m, and hence also τ(w) belongs to Ω(Γ_{0}), too. Since \overline{τ(w)} = \overline{w}, Proposition 2.5 proves that

w ⇝^{2^{⋆}}_{R} τ(w). □

In [11], the authors also introduced a notion of a positive (resp. negative) critical word. If A(Γ_{0}) is a dihedral Artin group with generating set S = {s, t}, a positive word w with p̃(w) = p(w) = m is called critical if it has the form [x, y, m⟩w′ or w′⟨m, x, y] with {x, y} = {s, t} and p(w′) < m. Similarly a negative word w with ñ(w) = n(w) = m is called critical if it has the form form [x^{−1}, y^{−1}, m⟩w′ or w′⟨m, x^{−1}, y^{−1}], with {x, y} = {s, t} and n(w′) < m. Further, the definition of τ can be extended to that of an involution on critical words that maps each positive, resp. negative critical word to another positive resp. negative critical word representing the same group element. More precisely, if w = [x, y, m⟩w′ is a positive critical word, then \overline{[x, y, m⟩w′} = \overline{δ(w′)⟨x, y, m]} = \overline{δ(w′)⟨y, x, m]}. Only one of the two words δ(w′)⟨x, y, m] and δ(w′)⟨y, x, m] has different last letter from w. If w′ is not empty it is also the only one of these two words that is critical. We define τ(w) to be this word. We define τ(w) for a negative critical word w = w′⟨x, y, m] in a similar way. It is easy to see that τ remains an involution.

It is straightforward to prove the following, and so we omit the details:

Lemma 2.12. Assume that A(Γ_{0}) is a dihedral Artin group with generating set S = {s, t}. For any positive or negative critical word w, w ⇝^{1}_{R} τ(w).

We now define the special transformation β in the case of dihedral Artin-Tits groups:

Definition 2.13. Assume that A(Γ_{0}) is a dihedral Artin group with generating set S = {s, t}. Let τ be the above involution on the set of critical words. We define special transformations of type β on words on S ∪ S^{−1} as follows: type β : Replace some factor w with τ(w), where w is a critical word.

From this definition and Lemmas 2.11 and 2.12, it follows:

Lemma 2.14. Assume that A(Γ_{0}) is a dihedral Artin group with generating set S = {s, t}. For any two words w, w′, one has

w ⇝^{β}_{R} w′ ⟹ w ⇝^{1,2^{⋆}}_{R} w′.

Proposition 2.15. [11, Sec. 2] Assume that A(Γ_{0}) is a dihedral Artin group. Let w be a word over S ∪ S^{−1}. Then there exists a geodesic word w′ such that \overline{w} = \overline{w′} and

w ⇝^{0,β}_{R} w′.

Proof. The result follows immediately from [11, Lemma 2.3], from which we deduce that if w is freely reduced but non-geodesic then it must possess a critical word w_{1} as a factor, and then the word w′ obtained from w by replacing the factor w_{1} with τ(w_{1}) is not freely reduced. So a combination of free reduction and at most one type β transformation reduces w to w′. □

Combining Lemma 2.14 and Proposition 2.15 we get the following corollary.

Corollary 2.16. Assume that A(Γ_{0}) is a dihedral Artin group with S as generating set. Let w be a word over S∪S^{−1}. There exists a geodesic word w′ such that \overline{w} = \overline{w′} and

w ⇝^{0,1,2^{⋆}}_{R} w′.

Transformations of type 2^{⋆} are special cases of transformations of type 2 and the unique geodesic representative word of 1 is the empty word ε. Therefore as a consequence of the above corollary, we recover :

Corollary 2.17. [8] Assume A(Γ_{0}) is a dihedral Artin group with S as generating set. Let w be a word over S ∪ S^{−1}. Then,

w ⇝^{0,1,2}_{R} ε ⟺ \overline{w} = 1

2.5. The case of large type Artin-Tits groups. Our objective here is to prove the following result, which is a special case of Theorem 1.4.

Proposition 2.18. Assume A(Γ_{0}) is an Artin group of large type with S as generating set. Let w be a word over S ∪ S^{−1}. There exists a geodesic word w′ such that \overline{w} = \overline{w′} and

w ⇝^{0,1,2^{⋆}}_{R} w′.

The proof is similar to the proof of Corollary 2.16; it follows from a combination of Lemma 2.19 below (a straightforward extension of Lemma 2.14) and results from [11], as we now describe.

Assume that A(Γ_{0}) is a Artin group with S as generating set. By [16, 14], the subgroup generated by any subset T of S is canonically isomorphic to the Artin-Tits group associated with the full subgraph of Γ_{0}. These subgroups are called the parabolic subgroups of A(Γ_{0}). So, if T = {s, t} with m_{s,t} ≠ ∞ then the parabolic subgroup generated by T is a dihedral Artin group . We can define the family of (signed or unsigned) critical words of A(Γ_{0}) as the (disjoint) union of the sets of (signed or unsigned) critical words of all dihedral parabolic subgroups of A(Γ_{0}). The involution τ is still well defined on this set, as are the associated operations of type β on words over S ∪ S^{−1}. So, the statement of Lemma 2.14 extends to the framework of Artin groups of large type.

Lemma 2.19. Assume that A(Γ_{0}) is an Artin group of large type. For any two words w, w′, one has

w ⇝^{β}_{R} w′ ⟹ w ⇝^{1,2^{⋆}}_{R} w′.

In the next section, we shall need the notion of rightward critical sequences from [11]. But we postpone the explicit definition of these to Section 3.4. For now, all we need is the following associated result, derived from [11, Proposition 3.3]

Lemma 2.20. Assume that A(Γ_{0}) is a Artin group of large type with S as generating set. Let w be a word over S ∪ S^{−1}. If the word w is not geodesic then it can be transformed into a word that is not freely reduced by a sequence of special transformations of type β.

With Lemma 2.19 at hand, Corollary 2.21 follows immediately.

Corollary 2.21. Assume that A(Γ_{0}) is a Artin group of large type with S as generating set. Let w be a word over S ∪ S^{−1}. Then,

w ⇝^{0,1,2^{⋆}}_{R} ε ⟺ \overline{w} = 1

Thus Property H is verified by Artin-Tits groups of large type. In fact we can prove a stronger property than H, property H^{+} below, using the convexity of parabolic subgroups of Artin groups (proved for large type Artin-Tits groups in [11], but for all Artin groups in [6]):

Proposition 2.22. [6] Assume that A(Γ_{0}) is an Artin-Tits group with S as generating set. Let S_{0} be included in S. If g belongs to the standard parabolic subgroup A_{S_{0}} then all its geodesic representative words over S ∪ S^{−1} are actually over S_{0} ∪ S_{0}^{−1}.

Definition 2.23. Assume that (S, R) is an Artin-Tits presentation. We say that (S, R) satisfies Property H^{+} if for all S_{0} ⊆ S and any word w over S ∪ S^{−1} that represents an element of the standard parabolic subgroup A_{S_{0}}, there exists a word w_{0} over S_{0} ∪ S_{0}^{−1} so that

w ⇝^{0,1,2^{⋆}}_{R} w_{0}

Corollary 2.24. Every Artin-Tits presentation of large type satisfies Property H^{+}.

Proof. By Proposition 2.18 there exists a geodesic word w_{0} so that w ⇝^{0,1,2^{⋆}}_{R} w_{0}. But w_{0} is a geodesic word and \overline{w_{0}} belongs to the standard A_{S_{0}}. So w_{0} is over S_{0} ∪ S_{0}^{−1}. □

We note that we derive Property H^{+} not simply from Property H plus convexity but rather from convexity together with the technical results from which Property H is derived. Hence it does not follow simply from convexity that Artin-Tits presentations of spherical type or of FC type satisfy Property H^{+} as well as H. But nonetheless the property must hold for both (and also for sufficiently large Artin-Tits groups), since it is implied by the Property H^{#} that is introduced in Section 3; see the comment following Proposition 3.5.

3. Sufficiently large Artin-Tits groups

Our objective is now to prove Property H for the family of sufficiently large Artin-Tits groups, which we define in this section. Our strategy is similar to the one used in [8] to prove property H for Artin-Tits groups of FC type. Namely we prove that a stronger property H^{#} holds for large type Artin groups and then extend it to sufficiently large Artin-Tits groups using amalgamation.

3.1. A characterization of Sufficiently large Artin-Tits groups. Sufficiently large Artin-Tits groups were introduced in [12], with the definition expressed in terms of the Coxeter graph. Here we obtain a characterization that proves that these groups are built out of large type Artin-Tits groups and finite rank free abelian groups. We first recall the original definition of sufficiently large Artin-Tits groups.

Definition 3.1. [12] Assume that A(Γ_{0}) is an Artin group with Coxeter graph Γ. We say that A(Γ_{0}) is sufficiently large if the full subgraph on any triple of distinct vertices of Γ is either completely disconnected, or of large type, or contains an edge with a label ∞. In other words, if s, t, u are three distinct vertices with m_{s,t} = 2 and m_{s,u} ≠ 2, ∞, then m_{t,u} = ∞.

From this definition we deduce that

Proposition 3.2. The family of sufficiently large Artin-Tits groups is the smallest family of Artin-Tits groups closed under amalgamation over a standard parabolic subgroup, and which contains finitely generated free Abelian Artin-Tits groups and large type Artin groups.

Proof. First, it is immediate from the definition that every standard parabolic subgroup of a sufficiently large Artin-Tits group is also sufficiently large.

Now, assume that A_{S} is a sufficiently large Artin-Tits group, and denote by S its generating set. If there is no ∞-labelled edge, then either m_{s,t} = 2 for all pairs s, t in S, or there is no pair s, t in S so that m_{s,t} = 2. So A_{S} is either free abelian or of large type. Assume there exist s_{1}, s_{2} in S so that m_{s_{1},s_{2}} = ∞. Then, it is wellknown that A_{S} is canonically isomorphic to the amalgamated product A_{1} ∗_{A_{1,2}} A_{2} where A_{1}, A_{2} and A_{1,2} are the standard parabolic subgroups of A_{S} generated by S \ {s_{1}}, S \ {s_{2}} and S \ {s_{1}, s_{2}}. This proves by induction on the number of ∞-labelled edges that sufficiently large Artin-Tits groups belong to the smallest family of Artin-Tits groups closed under amalgamation over a standard parabolic subgroup and which contains finitely generated free Abelian groups and Artin-Tits groups of large type. Conversely, assume that A_{1}, A_{2} are two Artin-Tits groups , generated by S_{1} and S_{2} respectively ,with a common standard parabolic subgroup A_{1,2} generated by S_{1,2} = S_{1} ∩ S_{2}. Denote by Γ_{1} and Γ_{2} the Coxeter graphs of A_{1}, A_{2}, respectively. Then the group A_{1} ∗_{A_{1,2}} A_{2} is the Artin-Tits group whose graph is obtained by glueing Γ_{1} and Γ_{2} along the common subgraph generated by S_{1,2}, and adding an ∞-labelled edge between each pair s, t of vertices so that s lies in S_{1} \ S_{1,2} and t lies in S_{2} \ S_{1,2}. Therefore, if A_{1}, A_{2} are sufficiently large Artin-Tits groups, so is A_{1} ∗_{A_{1,2}} A_{2}. □

3.2. The property H^{+}. From the previous section, sufficiently large Artin-Tits groups are built out of large type Artin-Tits groups and free abelian groups through iterated sequences of amalgamations. So it would be natural to try and prove that sufficiently large Artin-Tits groups satisfy Property H via a proof that when two group presentations satisfy Property H and can be amalgamated in a proper way then the obtained group presentation also satisfies Property H; unfortunately, there is no clear reason why this should be true. However, since Property H is implied by Property H^{+} (by considering S′ = ∅), a straightforward argument proves that the amalgamated product over a standard parabolic subgroup of two Artin groups satisfying Property H^{+} satisfies property H, as follows:

Proposition 3.3. Let (S, R) be an Artin-Tits presentation. Assume S = S_{1} ∪ S_{2}. Set S_{1,2} = S_{1} ∩ S_{2}. Denote by A_{1}, A_{2} and A_{1,2} the parabolic subgroups of A_{S} generated by S_{1}, S_{2} and S_{1,2}, respectively and by (S_{1}, R_{1}), (S_{2}, R_{2}) and (S_{1,2}, R_{1,2}) their Artin-Tits presentations. Assume that A_{S} = A_{S_{1}} ∗_{A_{S_{1,2}}} A_{S_{2}} and (S_{1}, R_{1}), (S_{2}, R_{2}) and (S_{1,2}, R_{1,2}) satisfy Property H^{+}. Then the presentation (S, R) satisfies Property H.

Proof. Let w be a non-empty word on S ∪ S^{−1}. Assume \overline{w} = 1. We need to prove

that w ⇝^{0,1,2}_{R} ε.

We decompose w as w = w_{1} ⋯ w_{k} for some minimal k ≥ 1, such that each subword w_{i} is written either over S_{1} ∪ S_{1}^{−1} or S_{2} ∪ S_{2}^{−1} (we call the w_{i} the factors of w). We prove by induction on k that w ⇝^{0,1,2}_{R} ε. Clearly the result is true when k = 1.

If k ≥ 2, it follows from consideration of amalgam normal forms (see, for example [10, Corollary 1.8]) that some \overline{w_{i}} belongs to A_{S_{1,2}}. Then, where w_{i} is written over S_{ℓ} ∪ S_{ℓ}^{−1}, since (S_{ℓ}, R_{ℓ}) satisfies Property H^{+}, there exists w′_{i} in S_{1,2} ∪ S_{1,2}^{−1} so that w_{i} ⇝^{0,1,2}_{R} w′_{i}. We let w′ be the word derived from w by replacing w_{i} by w′_{i}. Then w ⇝^{0,1,2}_{R} w′. If 1 < i then w′ contains w_{i−1}w′_{i} as a subword, and otherwise i < k and w′ contains w′_{i}w_{i+1} as a subword; either subword is written over S_{j}. So now, since we have decomposed w′ as a product of at most k − 1 factors, induction implies that w′ ⇝^{0,1,2}_{R} ε. It follows that w ⇝^{0,1,2}_{R} w′ ⇝^{0,1,2}_{R} ε, and our proof is complete. □

Unfortunately this approach does not appear to lead to a proof that all Artin-Tits groups of sufficiently large type satisfy property H, since it is not clear that the presentation of the amlgamated product would satisfy Property H^{+}, as we would need in order to prove that iterating the construction gives a group satisfying H. Instead we need a stronger property than H that is preserved under amalgamation.

3.3. The property H^{#}. The article [8] introduces a stronger property than Property H, namely Property H^{#}. And in that article it is proved that the strategy proposed in Section 3.2 can be applied to Property H^{#}. This is the way that Property H is proved to be satisfied by FC type Artin-Tits groups. We follow the same approach here to prove that Property H is satisfied by sufficiently large Artin-Tits groups.

If H is a subgroup of a group G, we call an H-transversal of G any subset of G that contains exactly one element from each left-H-coset, and in particular contains 1. If A_{S} is an Artin-Tits group generated by S, then we call an S-sequence of transversals any sequence (T (S′))_{S′⊆S} for which the set T (S′) is a A_{S′}-transversal of A_{S}, for each S′ ⊆ S.

Definition 3.4. Assume that (S, R) is an Artin-Tits presentation and T is an associated S-sequence of transversals. We say that (S, R) satisfies Property H^{#} (with respect to T) if, for all S′, S_{0} ⊆ S and any word w over S ∪ S^{−1}, setting S′_{0} = S′ ∩ S_{0}, the following relation is satisfied:

\overline{w} ∈ A_{S′} ⇒

∃v ∈ (S′ ∪ S′^{−1})^{∗}, ∃u ∈ (S′_{0} ∪ S′_{0}^{−1})^{∗} (w ⇝^{0,1,2}_{R} vu and \overline{v} ∈ T (S_{0})).

Roughly speaking, this property says that for every parabolic subgroup A_{S_{0}} of A_{S}, there is an A_{S_{0}}-transversal T (S_{0}) of A_{S}, so that one is able to find the decomposition of any element g as the product of its transversal representative and an element of A_{S_{0}}. Moreover, this can be done at the level of the word representatives, using operations of type 0, 1, 2, only. Finally when the element g, itself, belongs to another parabolic subgroup A_{S′} then the two obtained representative words of the decomposition can be written over S′ ∪ S^{′−1}. This imposes in particular the condition that the restriction of T (S_{0}) to the elements that belong to A_{S′} provide an A_{S_{0}∩S′}-transversal of A_{S′}. Considering the case where S′ is the empty set, we get the first part of the following proposition

Proposition 3.5. [8, Proposition 2.14] Let (S, R) be an Artin-Tits presentation. (1) If (S, R) satisfies Property H^{#}, then (S, R) satisfies Property H.

(2) Assume S = S_{1} ∪ S_{2}. Set S_{1,2} = S_{1} ∩ S_{2}. Denote by A_{1}, A_{2} and A_{1,2} the parabolic subgroups of A_{S} generated by S_{1}, S_{2} and S_{1,2}, respectively and by (S_{1}, R_{1}), (S_{2}, R_{2}) and (S_{1,2}, R_{1,2}) their Artin-Tits presentations. Assume that A_{S} = A_{S_{1}} ∗_{A_{S_{1,2}}} A_{S_{2}} and (S_{1}, R_{1}), (S_{2}, R_{2}) and (S_{1,2}, R_{1,2}) satisfy Property H^{#}. Then (S, R) satisfies Property H^{#}.

Note also that Property H^{#} immediately implies Property H^{+}. We shall use Propositions 3.2 and 3.5 in the final section to deduce Theorems 1.4 and 1.6 from Proposition 3.13, which proves Property H^{#} for Artin-Tits groups of large type, together with the same result for finite rank free Abelian groups. Since finite rank Abelian groups are all of spherical type, and hence covered by the results of [8], we focus now on the case of large type Artin-Tits groups.

3.4. Critical sequence. In order to prove Property H^{#} for large type Artin-Tits groups, we have first to find a S-sequence of transversals. The key argument turns out to involve critical factorizations and associated critical sequences of transformations, which we have already mentioned, and for which we now need a definition. We recall the notion of a critical word from Section 2.4. Our definition of a critical factorization is taken from [11]. Roughly speaking a critical factorization of a word is more-or-less its expression as a concatenation of critical words with one letter overlaps.

Definition 3.6. Assume A_{S} is an Artin-Tits group. Let n be a positive number, and suppose that w is freely reduced.

(1) We define a critical factorization of w of length 1 to be an expression of w as a concatenation αv_{1}β of (possibly empty) words α, β and a critical word v_{1}, and call v_{1} the critical factor of that factorization. A critical factorization of length 1 is considered to be both rightward and leftward.

(2) For n ≥ 2, we define a rightward critical factorization of w of length n with critical factors v_{1}, …, v_{n} to be an expression of w as a concatenation αv_{1} ⋯ v_{n}β, where v_{1} is critical, and, where s is the last letter of τ(v_{1}) (as defined in Section 2.4), the words sv_{2}, v_{3}, …, v_{n} are the critical factors of a critical factorization of length n − 1 of the word sv_{2}v_{3} ⋯ v_{n}.

(3) For n ≥ 2, we define a leftward critical factorization of w of length n with critical factors v_{1}, …, v_{n} to be an expression of w as a concatenation αv_{n} ⋯ v_{1}β, where v_{1} is critical, and, where s is the first letter of τ(v_{1}) , the words v_{2}s, v_{3}, …, v_{n} are the critical factors of a critical factorization of length n − 1 of the word v_{n}v_{n−1} ⋯ v_{2}s.

Note that a word w might admit many critical factorizations, both rightward and leftward, and that we do not require the subwords α, β of w to be non-empty.

It is convenient to extend our definition of τ so that it can be applied to the sequence of critical factors in a critical factorization.

(1) We define the image τ(v_{1}, …, v_{n}) of the sequence of critical factors of a rightward critical factorization to be the n-tuple (v′_{1}, v′_{2}, …, v′_{n}). where v′_{1} is the maximal proper prefix of τ(v_{1}), and (v′_{2}, …, v′_{n}) is the image under τ of the sequence of critical factors (sv_{2}, …, v_{n}) of sv_{2} ⋯ v_{n}.

(2) We define the image τ(v_{1}, …, v_{n}) of the sequence of critical factors of a leftward critical factorization to be the n-tuple (v‘_{1}, v′_{2}, …, v′_{n}). where v′_{1} is the maximal proper suffix of τ(v_{1}), and (v′_{2}, …, v′_{n}) is the image under τ of the sequence of critical factors (v_{2}s, …, v_{n}) of v_{n} ⋯ v_{2}s.

We shall need the following later.

Lemma 3.7. Assume that A_{S} is an Artin-Tits group. If (v_{1}, ⋯, v_{n}) is the sequence of factors of a rightward critical factorization, then so are both (v_{1}, …, v_{k}) and (sv_{k+1}, …, v_{n}), for any 1 ≤ k < n, where s is the final letter of the last term of τ(v_{1}, …, v_{k}).

Proof. This follows from the definition. We leave the details to the reader. □

Definition 3.8. Where a freely reduced word w admits a (rightward or leftward) critical factorization of length n, with critical factors v_{1}, …, v_{n}, the sequence of n critical transformations that leads to the replacement of the (rightward or leftward) concatenation of the critical factors by the (rightward or leftward) concatenation of the terms in the sequence τ(v_{1}, …, v_{n}) is called a critical sequence of transformations. That sequence is called rightward critical or leftward critical depending on whether the factorization is rightward critical or leftward critical.

We shall need the following result, derived from [11, Proposition 3.3] and [12, Proposition 3.2 (2)].

Proposition 3.9. Let A_{S} be an Artin-Tits group of large type. Suppose that w is freely reduced over S ∪ S^{−1}, representing the group element g ∈ A_{S}.

(1) If w is not geodesic then w admits a rightward critical factorization of the form αv_{1} ⋯ v_{n}β, with β non-empty, and application of a single rightward critical sequence of transformations transforms w to a word w′ = αv′_{1} ⋯ v′_{n}β that is not freely reduced. Specifically, the last letter of v′_{n} is the inverse of the first letter of β.

(2) Suppose that some lexicographic ordering has been chosen for S ∪ S^{−1}, and that w_{g} is the minimal representative of g, with respect to the shortlex order on words

If w is not equal to w_{g}, then some finite combination of rightward and leftward critical sequences of transformations together with free cancellation (after each rightward sequence) transforms w to w_{g}.

We shall also need the following corollary later.

Corollary 3.10. Assume that A_{S} is an Artin-Tits group of Large type, and that w, w′ are two geodesic representative words of the same element. Then w′ ⇝^{1,2}_{R} w.

Proof. Set g = \overline{w} = \overline{w′}, fix an ordering of S ∪ S^{−1}, and let w_{g} be the unique minimal representative of g with respect to the associated shortlex ordering on words. Proposition 3.9 ensures that a combination of leftward critical sequences of transformations transforms each of w, w′ into w_{g}; hence a sequence of transformations of type β (according to Definition 2.13) transforms w and w′ into w_{g}, and therefore w into w′. The result now follows by Lemma 2.19. □

3.5. The S-transversal for large Type Artin-Tits groups. With the notion of critical sequence at hand, we can now introduce an S-transversal for a large type Artin-Tits group and prove that Property H^{#} holds for Artin-Tits group of large type.

To verify that the set we define does give an S-transversal, we shall need the following.

Proposition 3.11. Assume that A_{S} is an Artin-Tits group of large type. Suppose that S_{0} ⊆ S and g ∈ A_{S}. Then

(1) Choose h ∈ A_{S_{0}} to satisfy the equation g = g_{0}h, where g_{0} is a minimal length element of gA_{S_{0}}. Let w_{0} and z be geodesic representative words of g_{0} and h, respectively. Then w_{0}z is a geodesic representative word of g.

(2) The left coset gA_{S_{0}} contains a unique element of minimal length.

Proof. Let g_{0}, h, w_{0}, z be as specified in (1). It follows from the convexity (see Proposition 2.22) of parabolic subgroups of Artin groups that z is a word written over S_{0} ∪ S_{0}^{−1}. Since w_{0} and z are freely reduced words, w_{0}z must also be freely reduced; for otherwise w_{0} has a proper suffix over S_{0} ∪ S_{0}^{−1} that freely cancels with a proper prefix of z, and hence a proper prefix of w_{0} represents a shorter element of gA_{S_{0}} than g_{0}.

So now suppose that w_{0}z is not geodesic. Then by Proposition 3.9 w_{0}z admits a rightward critical factorization αv_{1} ⋯ v_{n}β = αvβ such that the last letter of the concatenation of the terms of τ(v_{1}, …, v_{n}) freely cancels with the first letter s of the non-empty word β. Since w_{0} and z are geodesic, clearly vs cannot be a factor of either. If v were a suffix of w_{0}, then we could replace that suffix by the concatenation of the terms of τ(v_{1}, …, v_{n}) to get a new choice of w_{0}; but then we would have free reduction between w_{0} and z. We deduce that v must overlap w_{0} and z.

Now, if for some k < n the first k terms of the critical factorization were within w_{0}, then by Lemma 3.7 those terms would give a critical factorization of a factor of w_{0}, and replacing them by the terms of τ(v_{1}, …, v_{k}) would give us a different minimal choice for w_{0}. With this choice, Lemma 3.7 now implies that w_{0}z would admit a rightward critical factorization with critical factors tv_{k+1}, …, v_{n}, where t is the last letter of the concatenation of the terms of τ(v_{1}, ⋯, v_{k}). Hence we can assume that the first term v_{1} of the sequence overlaps both w_{0} and z.

Suppose now that v_{1} involves generators s_{1} and t_{1}. Let s_{1} be the rightmost letter of v_{1}. Then we know that s_{1} is within z, so s_{1} ∈ S_{0} ∪ S_{0}^{−1}. But since v_{1} is not a subword of z, we see that t_{1} ∉ S_{0} ∪ S_{0}^{−1}.

Let t be the generator immediately to the right of v_{1} in z (we know there must be such a generator even when n = 1, since β is non-empty). Then, by Lemma 2.10, t_{1} is the name of the generator at the end of τ(v_{1}); so either t_{1} = t^{±1} (when we have a free reduction), or t_{1} is the name of a generator in v_{2}, which is a subword of z. Either way t_{1} ∈ S_{0}, and so we have a contradiction.

So all cases lead to a contradiction. We conclude that w_{0}z must be a geodesic representative word of g.

So (1) holds. Now, (2) follows immediately. For if g_{1} is another element of gA_{S_{0}}, then g_{1} = g_{0}h_{1} for some non-trivial h_{1} ∈ A_{s_{0}}, and so g_{0} has a geodesic representative of which w_{0} is a proper prefix. □

Corollary 3.12. Assume that A_{S} is an Artin-Tits group of Large type. For S_{0} ⊆ S, Denote by T (S_{0}) the set of elements of A_{S} that are of minimal length in their left A_{S_{0}}-coset. Then, the sequence (T (S_{0}))_{S_{0}⊆S}, is a S-sequence of transversals.

Proof. That each T (S_{0}) is a left transversal follows immediately from part (2) of Proposition 3.11. And 1 ∈ T (S_{0}) is immediate since the element 1 is minimal in its left coset A_{S_{0}}. □

Proposition 3.13. Let A_{S} be an Artin-Tits group of Large type. Then A_{S} satisfies the Property H^{#}.

Proof. Let (T (S_{0}))_{S_{0}⊆S} be the S-sequence of transversals defined in Corollary 3.12. Choose subsets S_{0}, S′ of S, and let w be a word with \overline{w} ∈ A_{S′}. Choose g_{0} in T (S_{0}) and h in A_{S_{0}} with \overline{w} = g_{0}h, and let w_{0} and z be geodesic representative words of g_{0} and h, respectively.

Since h ∈ A_{S_{0}}, the convexity of parabolic subgroups ensures that z is written over S_{0} ∪ S_{0}^{−1}. By Proposition 3.11, the word w_{0}z is a geodesic representative word of \overline{w}, and so is written over S′ ∪ S′^{−1}. Hence, w_{0} is written over S′ ∪ S′^{−1}, and z is written over S′_{0} ∪ S′_{0}^{−1}, where S′_{0} = S′ ∩ S_{0}. So, in order to prove that Property H^{#} holds for A_{S}, it remains to prove that w ⇝^{0,1,2}_{R} w_{0}z.

By proposition 2.18, there exists a geodesic representative word w′ so that w ⇝^{0,1,2}_{R} w′. It remains to show that w′ ⇝^{1,2}_{R} w_{0}z. Since w′ and w_{0}z are two geodesic representative words of the same element, this follows immediately from Corollary 3.10. □

3.6. Proof of Theorems 1.6 and 1.4. We are now almost ready to prove Theorem 1.6. Using Proposition 3.5, we deduce the result from Proposition 3.13 by induction on the number of edges labelled with ∞ in the Coxeter graph. We need a preliminary result

Lemma 3.14. Let (S_{1}, R_{1}) and (S_{2}, R_{2}) be two Artin-Tits presentations that satisfy property H^{#} with S_{1} ∩ S_{2} = ∅. Set

R_{1,2} = {s_{1}s_{2} = s_{2}s_{1} | s_{1} ∈ S_{1}; s_{2} ∈ S_{2}}

Then, the Artin-Tits presentation (S_{1} ∪ S_{2}, R_{1} ∪ R_{2} ∪ R_{1,2}) satisfies property H^{#}.

Note that in the above lemma, the Artin-Tits group A_{S_{1}∪S_{2}} associated with the presentation (S_{1} ∪S_{2}, R_{1} ∪R_{2} ∪R_{1,2}) is isomorphic to the direct product A_{S_{1}} ×A_{S_{2}}.

Proof. Let (T (S_{1,0}))_{S_{1,0}⊆S_{1}}, be a S_{1}-sequence of transversals and (U(S_{2,0}))_{S_{2,0}⊆S_{2}}, be a S_{2}-sequence of transversals. For S_{0} ⊆ S_{1} ∪ S_{2}, set

V (S_{0}) = {g_{1}g_{2} | g_{1} ∈ T (S_{0} ∩ S_{1}); g_{2} ∈ U(S_{0} ∩ S_{2})}.

Since A_{S_{1}∪S_{2}} is the direct product of A_{S_{1}} and A_{S_{2}}, it immediately follows that (V (S_{0}))_{S_{0}⊆S}, is a S-sequence of transversals.

Let S′ be a subset of S. Set S′_{1} = S_{1} ∩ S′, S′_{2} = S_{2} ∩ S′, S′_{1,0} = S_{1} ∩ S′ ∩ S_{0} and S′_{2,0} = S_{2} ∩ S′ ∩ S_{0}. Let w be a word in S ∪ S^{−1} so that \overline{w} belongs to A_{S′}.

Since the latter group is the direct product of A_{S′_{1}} and A_{S′_{2}}, there exists a unique pair (g_{1}g_{2}) so that \overline{w} = g_{1}g_{2} with g_{1} ∈ A_{S′_{1}} and g_{2} ∈ A_{S′_{2}}. Note that for any two words w′, w′′, any s_{1} in S_{1} and s_{2} in S_{2}, and ε, τ ∈ {±1}, any transformation from w′s_{i}^{ε}s_{j}^{τ} w” to w′s_{j}^{τ} s_{i}^{ε}w” is an elementary transformation of type 1 or of type 2, since s_{1}s_{2} = s_{2}s_{1} belong to R_{1,2} Therefore, there exist w_{1} in S_{1} ∪S_{1}^{−1} and w_{2} in S_{2} ∪S_{2}^{−1} so that w ⇝^{1,2}_{R} w_{1}w_{2}. This imposes \overline{w_{1}} = g_{1} and \overline{w_{2}} = g_{2}.

Since (S_{1}, R_{1}) satisfies property H^{#}, there exist v_{1} ∈ (S′_{1} ∪ S′_{1}^{−1})^{∗} and u_{1} ∈

(S′_{1,0} ∪ S′_{1,0}^{−1})^{∗} so that w_{1} ⇝^{0,1,2}_{R} v_{1}u_{1} and \overline{v_{1}} ∈ T (S_{1,0}). Similarly, there exist v_{2} ∈

(S′_{2} ∪S′_{2}^{−1})^{∗} and u_{2} ∈ (S′_{2,0} ∪S′_{2,0}^{−1})^{∗} so that w_{2} ⇝^{0,1,2}_{R} v_{2}u_{2} and \overline{v_{2}} ∈ T (S_{2,0}). Thus,

we get w ⇝^{0,1,2}_{R} v_{1}u_{1}v_{2}u_{2}. By the same argument as before we have u_{1}v_{2} ⇝^{1,2}_{R} v_{2}u_{1} and w ⇝^{0,1,2}_{R} v_{1}v_{2}u_{1}u_{2}. The word v_{1}v_{2} lies in (S′ ∪ S′^{−1})^{∗} and by definition of V (S_{0}), the element \overline{v_{1}v_{2}} belongs to this transversal. Finally, the word u_{1}u_{2} lies in (S′_{0} ∪S′_{0}^{−1})^{∗}. Hence, Property H^{#} holds for the presentation (S_{1} ∪ S_{2}, R_{1} ∪ R_{2} ∪ R_{1,2}). □

Proof of Theorem 1.6. Recall that T is the family of those Artin-Tits presentation (S, R) whose Coxeter graph Γ satisfies the property that every connected full subgraph without an ∞-labelled edge is either of spherical type or of large type. For (S, R) in T , we denote the number of edges labelled with ∞ in the associated graph by d_{∞}(S, R). Let (S, R) belong to T and denote by Γ its Coxeter graph. As announced in the introduction of this section, we prove the result by induction on d_{∞}(S, R).

If d_{∞}(S, R) = 0, then T is a union of connected Coxeter graphs of spherical type or of large type. Since Property H^{#} holds for both types (see [8] for the spherical case), by Lemma 3.14, (S, R) satisfies Property H^{#}.

Now assume d_{∞}(S, R) ≥ 1. Let s_{1}, s_{2} belong to S so that m_{s_{1},s_{2}} = ∞. Set S_{1} = S \ {s_{2}}, S_{2} = S \ {s_{1}} and S_{1,2} = S \ {s_{1}, s_{2}}. Consider (S_{1}, R_{1}), (S_{2}, R_{2}) and (S_{1,2}, R_{1,2}), the Artin-Tits presentations associated with the full subgraphs of Γ generated by S_{1}, S_{2} and S_{1,2}, respectively. They are the presentations of the subgroups A_{1}, A_{2} and A_{1,2} of A_{S} generated by S_{1}, S_{2} and S_{1,2}, respectively, and A_{S} is equal to the amalgamated product A_{1} ∗_{1,2} A_{2}. Since (S, R) belongs to T , the presentations (S_{1}, R_{1}), (S_{2}, R_{2}) and (S_{1,2}, R_{1,2}) belong to T , too. Moreover, we have d_{∞}(S_{1}, R_{1}) < d_{∞}(S, R), d_{∞}(S_{2}, R_{2}) < d_{∞}(S, R) and d_{∞}(S_{1,2}, R_{1,2}) < d_{∞}(S, R). So by the induction hypothesis, Property H^{#} hold for (S_{1}, R_{1}), (S_{2}, R_{2}) and (S_{1,2}, R_{1,2}). So, (S, R) verifies Property H^{#} by Proposition 3.5. It also satisfies Property H by 3.5. □

Theorem 1.4 can be deduced as an immediate corollary, using Proposition 3.2 and the fact that every Artin-Tits presentation of large type belongs to the family T .

References

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

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

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

[4] E. Brieskorn, K. Saito. Artin-Gruppen und Coxeter-Gruppen. Invent. Math. 17 (1972), 245–271.

[5] R. Charney Injectivity of the positive monoid for some infinite type Artin groups. Geometric group theory down under (Canberra, 1996), 103–118, de Gruyter, Berlin, 1999.

[6] R. Charney, L Paris. Convexity of parabolic subgroups in Artin groups Bull. Lond. Math. Soc. 46 (2014), 1248–1255.

[7] J. Crisp, E. Godelle, B. Wiest The conjugacy problem in right-angled Artin groups and their subgroups J.P.A.A. 2 (2009), 442–460.

[8] P. Dehornoy, E. Godelle A conjecture about Artin-Tits groups J.P.A.A. 217 (2013), 241– 256.

[9] P. Dehornoy The subword reversing method Intern. J. Alg. and Comput. 21 (2011), 71–118.

[10] E. Godelle Parabolic subgroups of Artin groups of type FC Pacific J. Math. 208 (2003), 243–254.

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

[12] D.F. Holt, S. Rees Shortlex automaticity and geodesic regularity in Artin groups, Groups, Complex. Cryptol. 5 (2013), 1–23.

[13] J. Mairesse, F. Mathéus. Growth series for Artin groups of dihedral type. Int. J. Algebra Comput. 16 (2006), 1087–1107.

[14] L. Paris. Parabolic subgroups of Artin groups. J. Algebra. 196 (1997), 369–399.

[15] H Servatius, Automorphisms of Graph Groups, J. Algebra 126 (1987), 34-60.

[16] H. van der Lek. The homotopy type of complex hyperplane complements. Ph. D. Thesis, Nijmegen, 1983.

Eddy Godelle, Normandie Univ, France; UNICAEN, LMNO, F-14032 Caen, France; CNRS UMR 6139, F-14032 Caen, France

E-mail address: eddy.godelle@unicaen.fr
URL: //www.math.unicaen.fr/∼godelle

Sarah Rees, School of Mathematics and Statistics, University of Newcastle, Newcastle NE1 7RU, UK

E-mail address: sarah.rees@ncl.ac.uk
URL: //www.mas.ncl.ac.uk/∼nser