Patrick Dehornoy
email: patrick.dehornoy@unicaen.fr

Eddy A Godelle
email: eddy.godelle@unicaen.fr

A CONJECTURE ABOUT ARTIN-TITS GROUPS

Keywords: 1991 Mathematics Subject Classification. 20B30, 20F55, 20F36 Artin-Tits groups, positive presentation, van Kampen diagram, Dehn algorithm, amalgamated product, word problem, subword reversing

come

Artin-Tits groups, also known as Artin groups, are those groups that are defined by relations of the form (1) sts... = tst...

where both terms consist of two alternating letters and have the same length. These groups were first investigated by J. Tits in the late 1960's [START_REF] Brieskorn | Sur les groupe de tresses[END_REF]. Two seminal references are [START_REF] Brieskorn | Artin-Gruppen und Coxeter-Gruppen[END_REF] and [START_REF] Deligne | Les immeubles des groupes de tresses généralisés[END_REF]. At the moment many questions involving these groups remain open, including the decidability of the word problem in the general case [START_REF] Charney | Problems related to Artin Groups[END_REF]. The aim of this paper is to discuss a conjecture about the word problem of Artin-Tits groups, namely that, when a word w represents 1, hence is equivalent to the empty word modulo the relations, then w can be transformed to the empty word without introducing trivial factors ss -1 or s -1 s at any intermediate step of the derivation. Here we shall elaborate this intuitive idea into a precise statement, called Property H, and interpret the latter as a weak form of hyperbolicity (whence the notation). So, our conjecture is that all Artin-Tits groups-or, rather, all Artin-Tits presentations since Property H involves a specific presentation-satisfy Property H. It is known that Artin-Tits groups are not hyperbolic in general and, therefore, our conjecture is about how much of hyperbolicity could nevertheless be true in these groups. The main positive result we prove here is that all Artin-Tits presentation of type FC satisfy Property H. In terms of applications, Property H does not imply the decidability of the word problem, at least directly, but it implies that the monoid defined by a family of relations embeds in the corresponding group. Such a result is known to be true for Artin-Tits groups [START_REF] Paris | Artin monoids inject in their groups[END_REF], but, so far, the only available proof is quite indirect and relies on the existence of linear representations. If our conjecture is true, it would in particular lead to a more direct proof of that result.

The article is organized as follows. In Section 1, we introduce Property H, connect it with hyperbolicity, and show as a warm-up exercise that all Artin-Tits presentations of spherical type satisfy Property H. We also mention the application to monoid embeddability. Next, in Section 2, we establish that all Artin-Tits presentations of type FC satisfy Property H. Finally, in Section 3, we give an alternative proof of the result that all right-angled Artin-Tits presentations (a subfamily of type FC) satisfy Property H. The current range of the argument is more limited than that of Section 2, but it might be more promising in terms of subsequent developments as it involves no normal form.

Property H

We introduce special transformations and Property H in Subsection 1.1. We discuss its connection with the Dehn algorithm in Subsection 1.2. Then, in Subsection 1.3, we establish that all Artin-Tits presentations of spherical type satisfy Property H. Finally, we mention in Subsection 1.4 an application of Property H to the embeddability of a monoid S|R + in the corresponding group S|R .

1.1. Special transformations. For S a nonempty set, we denote by W + (S) the free monoid consisting of all words in the alphabet S, and by W(S) the free monoid of all words in S∪S -1 , where S -1 denotes a disjoint copy of S containing one letter s -1 for each letter s of S. By definition, a group G admits the presentation S|R if G is isomorphic to W(S)/≡ R , where ≡ R is the least congruence on W(S) containing the relations of R plus the free group relations s -1 s = ss -1 = 1. For w in W(S), we denote by w the element of S|R represented by w. We use ε for the empty word, and, for w in W(S), we denote by w -1 the word obtained from w by exchanging the letters s and s -1 everywhere and reversing their order. Finally, we say that a word v is a factor of another word w if there exist w 1 , w 2 satisfying w = w 1 vw 2 .

Hereafter, we shall consider presentations of a special type.

Definition 1.1. We say that a group presentation (S, R) is positive if all relations of R are of the form v = v ′ -or, equivalently, v -1 v ′ = 1-where v, v ′ are nonempty words of W + (S).

So the point is that the relations can be written with no letter s -1 and no empty word. As shows (1), Artin-Tits presentations are positive. If (S, R) is a positive presentation, it makes sense to consider the monoid presented by (S, R), which will be denoted by S|R + . In the context of positive presentations, the definition of the group S|R implies that two words w, w ′ of W(S) represent the same element of S|R if and only if one can go from w to w ′ by a finite sequence of transformations of the following types:

(i) Remove some pair s -1 s or ss -1 , where s is a letter of S;

(ii) Replace some factor v by v ′ , where v = v ′ is a relation of R;

(iii) Insert some pair s -1 s or ss -1 , where s is a letter of S. The question we will investigate is the extent to which transformations of the third type (inserting trivial factors s -1 s or ss -1 ) can be avoided. If we consider arbitrary words w, w ′ , we cannot expect a positive answer, as removing type (iii) transformations yields a relation that is not symmetric. However, the question makes sense when w ′ is the empty word ε: Question 1.2. Assume that (S, R) is a positive presentation and w is a word of W(S) that represents 1 in S|R . Can one transform w into the empty word by using transformations of type (i) and (ii) only?

The answer to Question 1.2 is positive when R is empty, that is, in the case of a free group, but the question is not well posed in general. For instance, if ab = ba belongs to R, the word ab -1 a -1 b represents 1, but it is eligible for no transformation of type (i) and (ii). This is due to a lack of symmetry in type (ii) transformations, and it can be fixed by extending the definition so as to also allow replacing v -1 by v ′-1 when v = v ′ is a relation of R. However, even so, the answer to Question 1.2 remains negative in simple cases. For instance, assume S = {a, b, c} and R = {ab = ba, bc = cb, ac = ca}. Let w = aBcAbC, where we adopt the convention that, in concrete examples, A, B, ... stand for a -1 , b -1 , ... [START_REF] Epstein | Word Processing in Groups[END_REF]. Then w represents 1 in S|R , but it is eligible for no transformation of type (i) or (ii). type 1:

v v ′ type 2 r : v v ′ u ′ u type 2 ℓ : u u ′ v ′ v Figure 1
. Special transformations viewed in the Cayley graph: relations correspond to oriented cells; special transformations of types 1 and 2 correspond to changing way around a cell: in type 1, the old path (plain) follows one side of the cell whereas the new path (dotted) follows the other side; in type 2r, the old path crosses the source of the cell, with at least one letter on both sides, and the new path crosses the target instead; type 2 ℓ is symmetric; note that a transformation of type 2r is not just the inverse of a transformation of type 2 ℓ as the definition requires that the initial words v, v ′ are not empty whereas it requires nothing for the final words u, u

′ : for instance, if v = v ′ is a relation of R, then v -1 v ′ 2r R ε holds, but ε 2 ℓ R v -1 v ′ does not.
Here comes the point. In addition to the above transformations, we consider a new type of syntactic transformations, namely the subword reversing transformations of [START_REF] Dehornoy | Complete positive group presentations[END_REF][START_REF] Dehornoy | The subword reversing method[END_REF]. Definition 1.3. For (S, R) a positive presentation, we define special transformations on words of W(S) 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 v ′ , or v -1 by v ′-1 , where v = v ′ is a relation of R, -type 2 r ("type 2-right"): Replace some factor v -1 v ′ with uu ′-1 , where v, v ′ are nonempty and vu = v ′ u ′ is a relation of R, -type 2 ℓ ("type 2-left"): Replace some factor vv ′-1 by u -1 u ′ , where v, v ′ are nonempty and uv = u ′ v ′ is a relation of R.
For X ⊆ {0, 1, 2, ∞}, we write w X R w ′ if w can be transformed to w ′ using special transformations of type belonging to X.

Special transformations are easily illustrated when words are viewed as paths in the Cayley diagram [START_REF] Epstein | Word Processing in Groups[END_REF], see Figure 1. With the above notation, the standard result is that, for every positive presentation (S, R) and every word w of W(S), we have

(1.1) w = 1 ⇔ w 0,1,∞ R ε.
Moreover, as is clear from Figure 1, every transformation of type 2 replaces a word with a new word that represents the same element of the involved group, so w 0,1,2,∞ R w ′ implies and, therefore, is equivalent to, w = w ′ . In particular, w

0,1,2,∞ R ε is equivalent to w = 1.
The question we will address is whether type ∞ transformations can be avoided: Question 1.4. Assume that (S, R) is a positive presentation and w is a word of W(S) that represents 1 in S|R . Does w 0,1,2 R ε necessarily hold? Introducing type 2 transformations really changes the situation. For instance, if S is {a, b, c} and R consists of ab = ba, bc = cb, and ac = ca, we observed above that, for w = aBcAbC, although w represents 1, the relation w

0,1 R ε fails. Now, w 0,1,2 R ε holds, since we can write aBcAbC 2 R aBAcbC 1 R aABcbC 0 BcbC 1 R BbcC 0 cC 0 ε.
We are ready to introduce our main definition and state our conjecture. Definition 1.5. We say that a positive presentation (S, R) satisfies Property H if the relation w 0,1,2 R ε holds for every word w of W(S) that represents 1 in S|R .

Conjecture 1.6. Every Artin-Tits presentation satisfies Property H. Before going on, let us immediately note that some positive presentations do not satisfy Property H. For instance, let S be {a, b, c, d, e, f} and let R consist of the four relations ca = ace, cb = bce, da = adf, and db = bdf. Let w = ACdaBDcb. Then, as shown in Figure 2, the word w represents 1 in the group S|R , but w 0,1,2 R ε cannot be true, as w is eligible for no transformation of type 0, 1, or 2. Hence the positive presentation (S, R) does not satisfy Property H. 1.2. Connection with the Dehn algorithm and hyperbolicity. Property H is reminiscent of the property that underlies the Dehn algorithm, and, in this way, it is connected with hyperbolicity. Here, we make this connection precise. The result is stated in Proposition 1.8 below, and it shows that Property H can be viewed as a weak hyperbolicity condition. In this way, Conjecture 1.6 asserts that Artin-Tits groups, which cannot to be hyperbolic in general as they include a free Abelian group of rank two, nevertheless satisfy some weak variant of hyperbolicity. Hereafter, we denote by |w| the length (number of letters) of a word w. Let us first recall the standard definition of the Dehn algorithm, here in the context of a positive presentation. Definition 1.7. Assume that (S, R) a positive group presentation. For w, w ′ in W(S), we say that w ′ is obtained from w by a Dehn transformation with respect to R if w ′ is obtained by replacing some factor u of w with a new factor u ′ such that |u| > |u ′ | holds and there exists a relation

v = v ′ of R such that u -1 u ′ is a cyclic permutation of v -1 v ′ or of v ′-1 v. We say that w 0,D R w ′ holds if w ′ is
obtained from w by a finite sequence of type 0 transformations and Dehn transformations with respect to R.

Clearly, w 0,D R w ′ implies w ≡ R w ′ and, in particular, w 0,D R ε always implies w ≡ R ε. Saying that the latter implication is an equivalence means that the Dehn algorithm is valid for the presentation (S, R). It is well known [1,[START_REF] Cannon | The theory of negative curved spaces and groups in Ergodic Theory, Symbolic Dynamics and Hyperbolic spaces[END_REF][START_REF] Lysionok | On some algorithmic properties of hyperbolic groups[END_REF] that, in this case, and provided the presentation (S, R) is finite, the group S|R is hyperbolic in the sense of Gromov.

It turns out that, at least in the case of positive presentations that satisfy simple length constraints, the relations 0,1,2 R and 0,D R are closely connected. Proposition 1.8. Assume that (S, R) is a positive presentation such that, for every rela-

tion v = v ′ of R, we have |v| -|v ′ | 2.
Then, for all w, w ′ in W(S), the relation w

0,D R w ′ implies w 0,1,2 R w ′ . Proof. It is enough to prove that w 0,1,2
R w ′ holds when w ′ is obtained from w by one Dehn transformation. As w

0,1,2 R w ′ implies w 1 ww 2 0,1,2 R w 1 w ′ w 2 for all w 1 , w 2 , it is even sufficient to prove u 0,1,2 R u ′ when there exists a relation v = v ′ of R such that |u| > |u ′ | holds and u -1 u ′ is a cyclic permutation of v ′-1 v. The case when u -1 u ′ is a cyclic permutation of v -1 v ′ would of course be symmetric.
We consider the possible repartitions of the positive and negative letters in u and u ′ . If u contains at most one positive and one negative letter, it must contain a factor s -1 t or a factor st -1 , in which cases it is eligible for a type 2 special transformation, and we directly obtain u 2 R u ′ . Otherwise, assume that u contains only positive letters, that is, it is a factor of v. If u is all of v, then u ′ is v ′ , and we obtain u 2|v| -3, whence |v ′ | |v| -3, which is incompatible with the hypothesis on (S, R). Finally, the case when u contains only negative letters, hence is a factor of v ′-1 , is symmetric. Thus, at least for presentations satisfying the length constraint of Proposition 1.8, the relation 0,1,2 is a weak version of 0,D and, therefore, Property H is a weak version of hyperbolicity. Artin-Tits presentations are eligible for Proposition 1.8 since all Artin-Tits relations are of the form v = v ′ with |v| = |v ′ |. As, except in the degenerate case of free groups, Artin-Tits groups are not hyperbolic, Conjecture 1.6 is a weaker statement in the same direction.

Remark 1.9. As it involves the equivalence relation ≡ R , Property H is connected with the word problem of the considered presentation. However, Property H need not imply the decidability of the word problem. Indeed, starting from a word w, there exist in general infinitely many words w ′ satisfying w 0,1,2 R w ′ . For instance, in the case of 4-strand braids, that is, of the Artin-Tits presentation of type A 3 -which satisfies Property H as will be established in Proposition 1.11 below-there exist infinitely many words

w ′ satisfying σ -1 2 σ -1 1 σ 3 σ 2 0,1,2 R w ′ [14]
. In such a case, there is a priori no method for establishing the failure of w 0,1,2 R ε, and therefore, when Property H is satisfied, for establishing the failure of w ≡ R ε.

To complete the discussion of the connection between Property H and the Dehn algorithm, we now briefly mention the approach of Appel and Schupp [START_REF] Appel | Artin groups and infinite Coxeter groups[END_REF] in extra-large type, and explain why it does not seem to naturally lead to a proof of Property H.

An Artin-Tits presentation (S, R) is said to be of extra-large type if all relations of R have the form v = v ′ with |v| = |v ′ | 4. Appel and Schupp [START_REF] Appel | Artin groups and infinite Coxeter groups[END_REF] prove that, if (S, R) is an Artin-Tits presentation of extra-large type and, if R is the set of all relations u = u ′ where u, u ′ are R-equivalent words of W(S) involving only two letters of S and such that u -1 u ′ is cyclically reduced, then a word w of W(S) represents 1 in S|R if and only if w 0,D R ε holds (here we do not assume that the words u, u ′ are positive, so the presentation (S, R) is not positive in general). In other words, the Dehn algorithm with respect to the family R solves the word problem, a result that does not contradict the non-hyperbolicity of the group S|R as R is always infinite. Owing to Proposition 1.8, it is natural to wonder whether the implication

(1.2) w 0,D R w ′ ⇒ w 0,1,2
R w ′ is always true. A direct proof of this implication would provide a proof of Conjecture 1.6, at least in the extra-large type: if w represents 1, then w 0,D R ε holds, and we would deduce w 0,1,2 R ε. However, (1.2) need not be true, even in very simple cases, as the following counter-example shows. R w ′ fails. The argument is as follows. We consider the finite fragment Γ of the Cayley graph of S|R represented in plain lines in Figure 3: the vertices are the nine left-divisors of the element abab 2 in the monoid S|R + . Then the word w is, in the sense of [START_REF] Dehornoy | A fast method for comparing braids[END_REF] or [13, Chapter IV], traced from a in Γ, that is, there exists inside Γ a path starting from the vertex labeled a whose edges wear as labels the successive letters of w. As explained in the cited references, the family of all words traced from a given vertex in the fragment of the Cayley graph made of all left-divisors of a given element is closed under special transformations of types 0, 1, and 2. Now the picture shows that w ′ is not traced from a in Γ and, therefore, w the vertex a in the fragment of the Cayley graph written in plain lines, and so is every word obtained from w using special transformations, whereas w ′ is not traced from the vertex a in that fragment.

0,1,2 R w ′ cannot hold.
1.3. The case of spherical type. Artin-Tits presentations of spherical type (also known as of finite type), that is, those such that the associated Coxeter group is finite [START_REF] Humphreys | Reflection Groups and Coxeter Groups[END_REF], provide natural test-cases: the corresponding groups are well understood and any conjecture involving general Artin-Tits groups can be expected to be provable for spherical type. This is the case for Property H.

Proposition 1.11. Every Artin-Tits presentation of spherical type satisfies Property H.

In order to establish Proposition 1.11 and to prepare the arguments of Subsection 2.2, we recall some terminology about divisibility relations. If M is a monoid and f, g belong to M , one says that f is a left-divisor of g, and that g is a right-multiple of f , if f g ′ = g holds for some element g ′ of M . If M has no nontrivial (that is, distinct of 1) invertible element-as is the case of every monoid S|R + defined by a positive presentation-the leftdivisibility relation is a partial ordering on M . Right-divisors are defined symmetrically: f is a right-divisor of g, and g is a left-multiple of f , if g = g ′ f holds for some g ′ . Finally, two elements of M are called left-coprime (resp. right-coprime) if they admit no nontrivial common left-divisor (resp. right-divisor).

The specificity of the spherical type is the following classical result describing S|R as a group of (right)-fractions. Proposition 1.12. [START_REF] Brieskorn | Artin-Gruppen und Coxeter-Gruppen[END_REF][START_REF] Epstein | Word Processing in Groups[END_REF][START_REF] Tatsuoka | An isoperimetric inequality for Artin groups of finite type[END_REF][START_REF] Charney | Geodesic automation and growth functions for Artin groups of finite type[END_REF] Assume that (S, R) is an Artin-Tits presentation of spherical type. Then the monoid S|R + embeds in the group S|R and, for every element g of S|R , there exists a unique pair (g 1 , g 2 ) of right-coprime elements of

S|R + satisfying g = g 1 g -1 2 . Moreover, if we have g = f 1 f -1 2
with f 1 , f 2 in S|R + , there exists h in S|R + such that f e = g e h holds for e = 1, 2.

In the above context, the elements g 1 and g 2 above are called the right-numerator and the right-denominator of g, here denoted by N r (g) and D r (g). In terms of words, there exists a simple connection with special transformations. Lemma 1.13. [START_REF] Dehornoy | Groups with a complemented presentation[END_REF] Assume that (S, R) is a Artin-Tits presentation of spherical type and w is a word of W(S). Let g 1 , g 2 be the right numerator and denominator of w.

(i) There exist

w 1 , w 2 in W + (S) satisfying w 0,2 R w 1 w -1 2
and w e = g e for e = 1, 2. (ii) For all w ′ 1 , w ′ 2 in W + (S) satisfying w ′ e = g e for e = 1, 2, we have w

0,1,2 R w ′ 1 w ′ 2 -1 .
Proof (sketch). (i) It follows from the fact that any two elements in the monoid S|R + admit a common left-multiple that, starting from w and performing type 0 and 2 ℓ special transformations, one arrives in finitely many steps to a word of the form v -1

1 v 2 with v 1 , v 2 in W + (S)
. By a symmetric argument, starting from v -1 1 v 2 and performing type 0 and 2 r special transformations, one arrives in finitely many steps to a word of the form w 1 w -1

2 with w 1 , w 2 in W + (S). So w 0,2 R w 1 w -1
2 holds. Moreover, the element of S|R + represented by v 1 w 1 and v 2 w 2 is the least common right-multiple of v 1 and v 2 , which implies that w 1 and w 2 are right-coprime. The uniqueness result in Proposition 1.12 then implies that w e represents g e for e = 1, 2.

(ii) Let w ′ e be any word of W + (S) representing g e . The uniqueness result of Proposition 1.12 implies that w ′ e ≡ + R w e , where w 1 , w 2 are the words obtained in (i). Then we have

w 1 w -1 2 1 R w ′ 1 w ′ 2 -1
. By composing, we deduce w

0,1,2 R w ′ 1 w ′ 2 -1 .
Due to the symmetry of Artin-Tits relations, Proposition 1.12 and Lemma 1.13 have left counterparts involving left-fractions of the form g -1 1 g 2 and negative-positive words w -1 1 w 2 . We shall then speak of the left-numerator and the left-denominator of g, denoted by D ℓ (g) and N ℓ (g). The latter are left-coprime elements of S|R + .

We can now easily complete the argument.

Proof of Proposition 1.11. Assume that w is a word of W(S) that represents 1 in S|R .

Then the left numerator and denominator of w are 1. By Lemma 1.13, there exist w 1 , w 2 in W + (S), both representing 1 in S|R + , and satisfying w

0,2 R w 1 w -1 2 .
The only possibility for a word of W + (S) to represent 1 is to be empty. So we must have w 0,2 R ε and, a fortiori, w

0,1,2 R ε. So Property H is satisfied. Remark 1.14. The result that w ≡ R ε implies w 0,2
R ε is false for general Artin-Tits presentations. For instance, consider the (right-angled) presentation (S, R) with S = {a, b, c, d} and R = {ac = ca, bc = cb, ad = da, bd = db}. The associated group is a direct product of two free groups of rank 2, respectively generated by a, b and c, d. Let w = ACdaBDcb. Then w 0,1,2 R ε is true, as we can for instance write

ACdaBDcb 1 R CAdaBDcb 1 R CAadBDcb 0 CdBDcb 1 R CdDBcb 0 CBcb 1 R CBbc 0 Cc 0 ε, hence w represents 1 in S|R . On the other hand, w 0,2
R ε is false, as w is eligible for no transformation of type 0 or 2.

1.4. An application. We conclude the section with an application of Property H to the embeddability of the monoid S|R + in the group S|R . This application provides an additional motivation for investigating Property H, especially in the case of Artin-Tits presentations. As the proof appears in [START_REF] Dehornoy | The subword reversing method[END_REF] (in a slightly different setting), we shall only state the result here.

To this end, we first need to introduce a condition called completeness. We recall that W + (S) denotes the family of all words in W(S) that contain no letter s -1 . Then, by definition, the monoid S|R + (isomorphic to) W + (S)/≡ + R , where ≡ + R is the least congruence on W + (S) that includes R. For w, w ′ in W + (S), by definition, w ≡ + R w ′ is equivalent to w 1 R w ′ and, from there, to w -1 w ′ 0,1 R ε. Completeness is a formally similar condition that involves special transformations of type 2 r instead of type 1.

Definition 1.15. [START_REF] Dehornoy | Complete positive group presentations[END_REF][START_REF] Dehornoy | The subword reversing method[END_REF] Assume that (S, R) is a positive presentation. We say that (S, R) is complete with respect to right-reversing if, for all w, w ′ in W + (S), the relation w

≡ + R w ′ is equivalent to w -1 w ′ 0,2r R ε. That w -1 w ′ 0,2r
R ε implies w ≡ + R w ′ is always true, so the non-trivial part is the converse implication, namely the condition that types 0 and 2 r transformations are sufficient to detect all pairs of ≡ + R -equivalent words. The embeddability result we wish to mention is as follows. Proposition 1.16. [12, Proposition 3.29] Assume that (S, R) is a positive presentation that is complete with respect to right-reversing, contains no relation of the form sv = sv ′ with v = v ′ , and satisfies Property H. Then the monoid S|R + embeds in the group S|R .

The (non-trivial) proof consists in showing that, if two words w, w ′ of W + (S) satisfy w ≡ R w ′ , then one can go from w to w ′ using a certain "fan" of words of W + (S) that are connected under ≡ + R . One then deduces that w ≡ R w ′ implies w ≡ + R w ′ , which means that S|R + embeds in S|R .

Note that, if (S, R) is eligible for Proposition 1.16, then the monoid S|R + must be leftand right-cancellative, that is, f g = f g ′ and gh = g ′ h both imply g = g ′ . It is easy to see that completeness plus the hypothesis on relations sv = sv ′ implies left-cancellativity. But these conditions alone say nothing about right-cancellativity. This shows that, in such a context, Property H includes a hidden right-cancellativity condition.

For our current purpose, the point is that every Artin-Tits presentation is complete with respect to right-reversing [START_REF] Dehornoy | Complete positive group presentations[END_REF], a result that in essence goes back to Garside [START_REF] Garside | The braid group and other groups[END_REF] in the case of classical braids, that is, for Artin-Tits presentations of type A, and to Brieskorn and Saito [START_REF] Brieskorn | Artin-Gruppen und Coxeter-Gruppen[END_REF] in the general case. It follows that, if Artin-Tits presentations satisfy Property H, they are eligible for Proposition 1.16. L. Paris [START_REF] Paris | Artin monoids inject in their groups[END_REF] proved that, if (S, R) is an Artin-Tits presentation, then S|R + always embeds in S|R . The beautiful but indirect argument of [START_REF] Paris | Artin monoids inject in their groups[END_REF] uses certain linear representations extending the Lawrence-Krammer representation of braids [START_REF] Krammer | Braid groups are linear[END_REF], and a more direct proof remains to be discovered. Together with Proposition 1.16, a proof of Conjecture 1.6 would arguably provide such a natural proof.

Artin-Tits groups of type FC

The family of Artin-Tits groups of type FC is the smallest class of groups that contains all Artin-Tits groups of spherical type and is closed under forming an amalgamated product over a standard parabolic subgroup. The aim of this section is to prove Proposition 2.1. Every Artin-Tits presentation of type FC satisfies Property H. This result shows that Property H is satisfied for a large number of Artin-Tits presentations.

The section is organized as follows. In Subsection 2.1, we introduce a strengthening H ♯ of Property H that is more suitable for amalgamated products. Then we show that all Artin-Tits presentations of spherical type satisfy Property H ♯ in Subsection 2.2. Finally, we develop in Subsection 2.3 the inductive argument needed to establish Proposition 2.1.

The general scheme and the techniques used in this section follow those of Altobelli [START_REF] Altobelli | The word problem for Artin groups of FC type[END_REF]. However, the argument has to be revisited completely because we are considering special transformations and the relation 0,1,2 R instead of ≡ R . Also, in Subsection 2.3, we do not restrict to Artin-Tits groups and propose a new, hopefully optimized construction.

2.1. Property H ♯ . The definition of the family of Artin-Tits presentations of type FC as the closure of the family of Artin-Tits presentations of spherical type under a certain type of amalgamated product naturally suggests an inductive proof for Proposition 2.1. However, we first need to modify Property H to make the induction possible.

By definition of standard parabolic subgroups [START_REF] Van Der Lek | The homotopy type of complex hyperplane complements[END_REF], the amalgamated products involved in the construction of type FC groups correspond, in terms of presentations, to a union. Lemma 2.2. Say that two presentations (S 1 , R 1 ) and (S 2 , R 2 ) are in amalgam position if, denoting by G ′ e the subgroup of S e |R e generated by S 1 ∩ S 2 , the identity map of

S 1 ∩ S 2 induces an isomorphism of G ′ 1 onto G ′ 2 . Then (S 1 ∪ S 2 , R 1 ∪ R 2 ) is a presentation of the amalgamated product S 1 |R 1 * G ′ 1 =G ′ 2 S 2 |R 2 .
It directly follows from the results of van der Lek [START_REF] Van Der Lek | The homotopy type of complex hyperplane complements[END_REF] that two Artin-Tits presentations (S 1 , R 1 ), (S 2 , R 2 ) are in amalgam position if and only if the relations of R 1 and of R 2 that involve generators in S 1 ∩ S 2 coincide. Thus, owing to Proposition 1.11, which says that all Artin-Tits presentations of spherical type satisfy Property H, the natural approach for proving Proposition 2.1 should be to establish that the union of two Artin-Tits presentations that are in amalgam position and satisfy Property H again satisfies Property H. This however seems difficult, even probably false in general. What we shall do below is to introduce some strengthening H ♯ of H and apply the expected induction scheme to Property H ♯ rather than to Property H.

Hereafter, if (S, R) is a positive presentation and S ′ is a subset of S, we denote by S ′ the subgroup of S|R generated by S ′ . Similarly, we denote by S ′ + the submonoid of S|R + generated by S ′ . If G ′ is a subgroup of S|R , a (left)-G ′ -transversal is a subset of S|R that contains one element exactly in each left-G ′ -coset, and that contains 1-the latter condition is not always required, but here we explicitly include it in our definition. Below, we shall consider families of transversals with respect to various subgroups: we define an S-sequence of transversals in S|R to be a sequence T = (T (S ′ )) S ′ ⊆S such that T (S ′ ) is S ′ -transversal in S|R for every S ′ included in S.

Definition 2.3. Assume that (S, R) is a positive presentation and T is an S-sequence of transversals in S|R . We say that (S, R) satisfies Property H ♯ with respect to T if, for all S ′ , S 0 included in S and w in W(S), the following relation P T (S ′ , S 0 , w) is satisfied:

(2.1) w ∈ S ′ implies ∃v ∈ W(S ′ ) ∃u ∈ W(S ′ ∩ S 0 ) (w 0,1,2
R vu and v ∈ T (S 0 )). Roughly speaking, P T (S ′ , S 0 , w) says that, starting with a word w and using special transformations, we can isolate a representative of the (unique) element of the distinguished transversal T (S 0 ) that lies in the left-S 0 -coset of w, and, if w lies in S ′ , we can moreover require that the final words lie in W(S ′ ).

Lemma 2.4. Property H ♯ implies Property H.

Proof. Assume that (S, R) satisfies Property H ♯ with respect to T , and that w represents 1 in S|R . Then w belongs to ∅ . Hence P T (∅, S, w) says that there exists v and u in W(∅) such that w 0,1,2 R vu holds. Now the only element of W(∅) is the empty word ε, so the only possibility is v = u = ε, whence w 0,1,2 R ε. So (S, R) satisfies Property H. The result we shall establish is then Proposition 2.5. Every Artin-Tits presentation of type FC satisfies Property H ♯ . By Lemma 2.4, Proposition 2.5 directly implies Proposition 2.1. The proof of Proposition 2.5 will occupy the rest of this section, and consists in proving that every Artin-Tits presentation of spherical type satisfies Property H ♯ (Proposition 2.7) and that the union of two presentations that are in amalgam position and satisfy Property H ♯ satisfies Property H ♯ (Proposition 2.14). We begin with two direct consequences of the definition: Lemma 2.6. Assume that (S, R) is a positive presentation that satisfies Property H ♯ .

(i) For all S ′ , S ′′ included in S, we have S ′ ∩ S ′′ = S ′ ∩ S ′′ .

(ii) For all S ′ included in S and w in W(S),

(2.2) w ∈ S ′ implies ∃v ∈ W(S ′ ) (w 0,1,2 R v). Proof.
Assume that (S, R) satisfies Property H ♯ with respect to T .

(i) The inclusion S ′ ∩ S ′′ ⊆ S ′ ∩ S ′′ is always true. For the other inclusion, assume that g belongs to S ′ ∩ S ′′ . Let w be a word of W(S) representing g. By P T (S ′ , S ′′ , w), there exist v in W(S ′ ) and u in W(S ′ ∩ S ′′ ) satisfying w 0,1,2 R vu and v ∈ T (S ′′ ). Then we have g = w = v u. By hypothesis v belongs to S ′′ , so v is the element of the S ′′transversal T (S ′′ ) that belongs to the left-S ′′ -coset of w. Now, by hypothesis, w belongs to S ′′ , hence v must be 1, and, therefore, we have w = u, whence g = u ∈ S ′ ∩ S ′′ .

(ii) Assume w ∈ S ′ . Then, by P T (S ′ , ∅, w), there exist v in W(S ′ ) and u in W(∅) satisfying w 0,1,2 R vu and v ∈ T (∅). The only possibility is u = ε, and, therefore, we have w

0,1,2 R v. So (2.2) is satisfied. 2.2.
The spherical case. According to the scheme described above, the first step toward Proposition 2.5 is to consider Artin-Tits presentations of spherical type. We shall establish Proposition 2.7. Every Artin-Tits presentation of spherical type satisfies Property H ♯ .

A first observation is that, for Artin-Tits presentations, Condition P T (S ′ , S 0 , w), which simultaneously involves two subsets S 0 , S ′ of S, can be split into two simpler conditions involving only one subset of S at a time.

Lemma 2.8. Assume that (S, R) is an Artin-Tits presentation. Then (S, R) satisfies Property H ♯ with respect to T if and only if, for all S 0 included in S and w in W(S), we have (2.2) and

(2.3) ∃v ∈ W(S) ∃u ∈ W(S 0 ) (w 0,1,2
R vu and v ∈ T (S 0 )). Proof. We already observed in Lemma 2.6 that Property H ♯ implies (2.2) for all S ′ and w. On the other hand, (2.3) is (equivalent to) P T (S, S 0 , w), so Property H ♯ implies (2.2) and (2.3).

Conversely, assume that (S, R) is an Artin-Tits presentation that satisfies (2.2) and (2.3) for all S ′ , S 0 , and w. Let S 0 , S ′ be subsets of S and let w be a word of W(S) that represents an element of S ′ . By (2.2), there exists a word w ′ of W(S ′ ) satisfying w 0,1,2 R w ′ holds. Next, by (2.3), we find v in W(S) and u in W(S 0 ) satisfying w ′ 0,1,2 R vu and v ∈ T (S 0 ). Now, due to the specific syntactic form of Artin-Tits relations, the hypothesis that w ′ lies in W(S ′ ) implies that w ′′ lies in W(S ′ ) for every word w ′′ satisfying w ′ 0,1,2 R w ′′ . Indeed, a special transformation of type 0, 1, or 2 can never let a new letter of S or S -1 appear. Hence v must lie in W(S ′ ), and u must lie in W(S 0 ∩ S ′ ). So P T (S ′ , S 0 , w) is satisfied.

Next, we observe that (2.2) is almost trivial. Lemma 2.9. Assume that (S, R) is an Artin-Tits presentation of spherical type. Then (2.2) is satisfied for all S 0 included in S and w in W(S).

Proof. Assume that S 0 is included in S and w is an element of W(S) that represents an element of S 0 . Then w has at least one representative that lies in W(S 0 ) and, therefore, N r (w) and D r (w) admit representatives, say v 1 , v 2 that lie in W + (S 0 ). Then the word v 1 v -1 2 is a word of W(S 0 ) and, by Lemma 1.13(ii), we have w

0,1,2 R v 1 v -1
2 . So we are left with proving that, if (S, R) is an Artin-Tits presentation of spherical type, then all instances of (2.3) are satisfied. We begin with a general auxiliary result that will be used several times in the sequel. Lemma 2.10. Assume that (S, R) is an Artin-Tits presentation, S 0 is included in S, and we have gh = g ′ h ′ with g, g ′ in S|R + and h, h ′ in S 0 + . If g is right-divisible by no nontrivial element of S 0 + , then necessarily h right-divides h ′ .

Proof. (See Figure 4.) In the monoid S|R + , the elements h and h ′ admit a least common left-multiple, say h ′′ , that lies in S 0 + . Since gh, which is also g ′ h ′ , is a left-multiple of h and h ′ , it is a left-multiple of h ′′ , say gh = g ′′ h ′′ with g ′′ ∈ S|R + . Write h ′′ = f h. We find gh = g ′′ f h, whence g = g ′′ f . By construction, f belongs to S 0 + and right-divides g, so the hypothesis that g is right-divisible by no nontrivial element of S 0 + implies f = 1, whence h ′′ = h. The latter equality means that h ′ right-divides h.

g ′′ h ′′ g g ′ h ′ h f ′ f Figure 4. Proof of Lemma 2.10.
Until the end of this subsection, we assume that (S, R) is an Artin-Tits presentation of spherical type. We denote by G the group S|R , and by G + the monoid S|R + . We shall now construct an S-sequence of transversals T with the aim of proving that (2.3) is always satisfied.

Definition 2.11. Assume that S 0 is included in S. An element g of G is called S 0minimal if, for every h in S 0 , we have

|D ℓ (gh)| |D ℓ (g)| and |D ℓ (gh)| = |D ℓ (g)| implies |N ℓ (gh)| |N ℓ (g)|. Then we put T (S 0 ) = {g ∈ G | g is S 0 -minimal}.
We shall show that T is an S-sequence of transversals witnessing for Property H ♯ . We begin with several technical results about S 0 -minimal elements. Lemma 2.12. (i) An element of G + is S 0 -minimal if and only it is right-divisible by no nontrivial element of S 0 + . (ii) If g is S 0 -minimal, then, for every h in S 0 + , the elements D ℓ (g) and N ℓ (g)h are left-coprime.

(iii) If g is S 0 -minimal and lies in G + , then, for every h in S 0 , the elements N r (gh) and D r (h) are right-coprime.

(iv) If g is S 0 -minimal, then so is N ℓ (g).

Proof. (i) Assume that g is an element of G + and h is an element of S 0 + that rightdivides g, say g = g ′ h with g ′ in G + . Then we have |D ℓ (gh

-1 )| = |D ℓ (g)| = 0 and |N ℓ (gh -1 )| = |g ′ | = |g| -|h|. If g is S 0 -minimal, the only possibility is |h| = 0, that is, h = 1.
Conversely, assume that g is an element of G + that is right-divisible by no nontrivial element of S 0 + . Let h belong to S 0 . We have D ℓ (ii) Assume that g is S 0 -minimal and h lies in S 0 + . Put g 1 = D ℓ (g), g 2 = N ℓ (g). By definition of an S 0 -minimal element, we have

(g) = 1, so |D ℓ (gh)| |D ℓ (g)| is always satisfied. Assume |D ℓ (gh)| = |D ℓ (g)|, hence |D ℓ (gh)| = 0, that is, gh ∈ G + . Let g ′ =
|D ℓ (gh)| |D ℓ (g)| = |g 1 |. Assume that f is a common left-divisor of g 1 and g 2 h, say g 1 = f g ′ 1 and g 2 h = f g ′ 2 with g ′ 1 , g ′ 2 in G + . As we have gh = g ′ 1 -1 g ′ 2 , we deduce |D ℓ (gh)| |g ′ 1 | = |g 1 | -|f |.
The only possibility is |f | = 0, that is, f = 1. Hence g 1 and g 2 h are left-coprime.

(iii) Let h 1 = N r (h) and h 2 = D r (h). Assume that f right-divides gh 1 and h 2 , say gh 1 = g ′ f . As f right-divides h 2 , it lies in S 0 + . As g is S 0 -minimal, (i) implies that it is right-divisible by no nontrivial element of S 0 + . Then Lemma 2.10 implies that f rightdivides h 1 and, therefore, the hypothesis that h 1 and h 2 are right-coprime implies f = 1. So gh 1 and h 2 are right-coprime, as expected.

(iv) Assume that g is S 0 -minimal. Let g 1 = D ℓ (g) and

g 2 = N ℓ (g). Assume g 2 = g ′ h with h in S 0 + . Let g ′ = g -1 1 g ′ = gh -1 .
The hypothesis that g 1 and g 2 are left-coprime implies that g 1 and g ′ are left-coprime. Hence we have D ℓ (g ′ ) = g 1 = D ℓ (g) and N ℓ (g ′ ) = g ′ . As we have g

′ = gh -1 with h -1 ∈ S 0 and |D ℓ (g ′ )| = |D ℓ (g)|, the hypothesis that g is S 0 minimal implies |N ℓ (g ′ )| |N ℓ (g)|, that is, |g ′ | |g 2 |. As we have |g 2 | = |g ′ | + |h|, the only possibility is |h| = 1, that is, h = 1. Thus g has no nontrivial right-divisor in S 0 . By (i), g is S 0 -minimal.
Lemma 2.13. For every S 0 included in S, the family T (S 0 ) is a S 0 -transversal in G.

Proof. Let C be a left-S 0 -coset. Let C ′ be the set {g ∈ C | |D ℓ (g)| is minimal}, and C ′′ be {g ∈ C ′ | |N ℓ (g)| is minimal}. By definition, C ′′
is nonempty, and every element of C ′′ is an element of C that is S 0 -minimal. So every left-S 0 -coset contains at least one S 0 -minimal element.

Assume now that g and g ′ belong to T (S 0 ) and lie in the same left-S 0 -coset, say g = g ′ h with h ∈ S 0 . Let g 1 , g 2 be the left denominator and numerator of g, and g ′ 1 , g ′ 2 be those of g ′ . Write h = h 1 h -1 2 with h 1 , h 2 in S 0 + . As g ′ is S 0 -minimal, Lemma 2.12(ii) implies that g ′ 1 and g ′ 2 h 2 are left-coprime. Now we have g -1

1 (g 2 h 1 ) = g ′ 1 -1 (g ′ 2 h
2 ). As g ′ 1 and g ′ 2 h 2 are left-coprime, g ′ 1 must right-divide g 1 . By a symmetric argument exchanging the roles of g and g ′ and those of h 1 and h 2 , we see that g 1 must right-divide g ′ 1 . We deduce g 1 = g ′ 1 , whence g 2 h 1 = g ′ 2 h 2 . By Lemma 2.12(iv), g 2 is S 0 -minimal, so, by Lemma 2.12(i), g 2 is right-divisible by no nontrivial element of S 0 + . Hence, by Lemma 2.10, h 2 rightdivides h 1 . A symmetric argument shows that h 1 right-divides h 2 . We deduce h 1 = h 2 , whence g = g ′ . So every left-S 0 -coset contains at most one S 0 -minimal element.

Finally, it is clear that 1 is S 0 -minimal, hence T (S 0 ) contains 1.

With these results at hand, we can complete the argument.

Proof of Proposition 2.7. We have seen that the only point that remains to be proved is the satisfaction of (2.3) for all S 0 and w. So, assume that S 0 are included in S and w is a word of W(S). Put g = w. As T (S 0 ) is S 0 -transversal, we have g = g ′ h for some (unique) g ′ in T (S 0 ) and h in S 0 . In G, we have

(2.4) D ℓ (g) -1 N ℓ (g)D r (h) = gD r (h) = g ′ hD r (h) = D ℓ (g ′ ) -1 N ℓ (g ′ )N r (h)
. By hypothesis, g ′ is S 0 -minimal. Hence, by Lemma 2.12(ii), D ℓ (g ′ ) and N ℓ (g ′ )N r (h) are leftcoprime. So, by (the left counterpart of) Proposition 1.12, (2.4) implies the existence of 5. By Lemma 2.12(iv), the hypothesis that g ′ is S 0 -minimal implies that N ℓ (g ′ ) is S 0 -minimal and, then, Lemma 2.12(iii) implies that N ℓ (g ′ )N r (h) and D r (h) are right-coprime. Now, let w 1 , w 2 be words of W + (S) representing the left denominator and numerator of g, let v 1 , v 2 be words of W + (S) representing the left denominator and numerator of g ′ , and let u 1 , u 2 be words of W + (S 0 ) representing the right numerator and denominator of h. Finally, let u represent f . First, by (the left counterpart of) Lemma 1.13, we have w

f in G + satisfying D ℓ (g) = f D ℓ (g ′ ) and N ℓ (g)D r (h) = f N ℓ (g ′ )N r (h), see Figure
0,1,2 R w -1 1 w 2 . Next, N ℓ (g) = f N ℓ (g ′ ) implies w 1 ≡ + R uv 1 , whence w -1 1 1 R v -1 1 u -1 and w 0,1,2 R v -1 1 u -1 w 2 . Finally, we have f -1 N ℓ (g) = N ℓ (g ′ )N r (h)D r (h) -1
, and we saw above that N ℓ (g ′ )N r (h) and D r (h) are right-coprime, which implies that N ℓ (g

′ )N r (h) is the right- numerator of f -1 N ℓ (g) and D r (h) is its right-denominator. By definition, u -1 w 2 repre- sents f -1 N ℓ (g), whereas v 2 u 1 represents N ℓ (g ′ )N r (h) and u 2 represents D r (h). Lemma 1.13(ii) then implies u -1 w 2 0,1,2 R v 2 u 1 u -1 2 , whence w 0,1,2 R v -1 1 v 2 u 1 u -1 2 , that is, w 0,1,2 R vu if we put v = v -1
1 v 2 and u = u 1 u -1 2 . Now, by construction, v represents g ′ , an element of T (S 0 ), whereas u is a word of W(S 0 ). So (2.3) is satisfied.

D ℓ (g ′ ) N ℓ (g ′ ) N r (h) D r (h) N ℓ (g) D ℓ (g) f g ′ h Figure 5
. Proof of Proposition 2.7: the point is that D ℓ (g ′ ) and N ℓ (g ′ )Nr(h) are left-coprime, and that N ℓ (g ′ )Nr(h) and Dr (h) are right-coprime.

Preservation under union.

We shall now prove that Property H ♯ is preserved under suitable unions. Proposition 2.14. Assume that (S 1 , R 1 ) and (S 2 , R 2 ) are positive group presentations that are in amalgam position and satisfy Property H ♯ . Then

(S 1 ∪ S 2 , R 1 ∪ R 2 ) satisfies Prop- erty H ♯ .
As explained in Subsection 2.1, this result together with Proposition 2.7 implies that every Artin-Tits presentation of FC type satisfies Property H ♯ , hence a fortiori Property H, thus completing the proof of Proposition 2.1.

We split the proof of Proposition 2.14 into several steps. Until the end of the section, we assume that (S 1 , R 1 ) and (S 2 , R 2 ) are fixed positive presentations that are in amalgam position and satisfy Property H ♯ . For e = 1, 2, we denote by G e the group S e |R e , we write G 1,2 for G 1 ∩ G 2 , and G for the amalgamated product G 1 * G1,2 G 2 . Thus, if we put

S = S 1 ∪ S 2 , R = R 1 ∪ R 2 ,
and S 1,2 = S 1 ∩ S 2 , then, by hypothesis, we have G = S|R and G 1,2 = S 1,2 (both in the sense of G 1 and of G 2 ). Next, we fix an S e -sequence of transversals T e witnessing that (S e , R e ) satisfies Property H ♯ , and write P e (S ′ , S ′′ , w) for P T e (S ′ , S ′′ , w).

For g in G 1 △ G 2 (that is, in G 1 \ G 2 or in G 2 \ G 1 )
, we denote by o(g) the index e such that g lies in G e . It follows from Lemma 2.2 that, for every element g of G, there exists a unique sequence (g 1 , ..., g r , g * ) such that g = g 1 ••• g r g * holds, for every i the element g i is a nontrivial element of T 1 (S 1,2 ) ∪ T 2 (S 1,2 ) with o(g i ) = o(g i+1 ), and g * is an element of G 1,2 . Definition 2.15. In the above context, the sequence (g 1 , ..., g r , g * ) is called the amalgam decomposition of g and denoted by AD(g). The number r is called the amalgam length of g and denoted by ℓ(g). Finally, the tail τ (g) of g is defined to be g r g * for r 1, and to be g * (that is, g) for r = 0.

(Note that τ (g) is always g r g * if AD(g) is extended with g i = 1 for i 0.) We begin with a natural result saying that, if a word w represents an element g of G, then, by using special transformations, we can go from w to a concatenation of words that represent the successive entries of the amalgam decomposition of g. So, roughly speaking, the amalgam decomposition can be computed using special transformations. Lemma 2.16. Assume that w is a word of W(S) and (g 1 , ..., g r , g * ) is the amalgam decomposition of w. Then there exist words w 1 , ..., w r , w * such that w

0,1,2 R w 1 ••• w r w * holds, w i lies in W(S o(gi)
) and represents g i for i = 1, ..., r, and w * lies in W(S 1,2 ) and represents g * .

Proof. As S is the union of S 1 and S 2 , every word of W(S) can be expressed as a concatenation of words in W(S 1 ) and in W(S 2 ), say w 1 ••• w p with w i ∈ W(S ei ) and e i = e i+1 . For w in W(S), we denote by a(w) the minimal value of p for which such a decomposition of w exists. Then we prove the result using induction on a(w).

Assume first a(w) = 1. Then w belongs to W(S e ) for e = 1 or 2. Two subcases are possible. Assume first w ∈ G 1,2 . Then we have r = 0, with AD(w) = (g). By Lemma 2.6(ii), there exists w * in W(S 1,2 ) satisfying w 0,1,2 R1 w * . A fortiori, we have w 0,1,2 R w * , whence w * = w, and w * = g = g * , as expected. Assume now w / ∈ G 1,2 . Then, we have r = 1. By P e (S e , S 1,2 , w), there exists w 1 in W(S e ) and w * in W(S 1,2 ) satisfying w 0,1,2 R e w 1 w * and w 1 ∈ T e (S 1,2 ). A fortiori, we have w 0,1,2 R w 1 w * , whence w 1 w * = w. As, by construction, w * belongs to G 1,2 , the uniqueness of the amalgam decomposition implies w 1 = g 1 and w * = g * , as expected again.

Assume now a(w) 2. Write w = vu with a(v) = a(w) -1 and a(u) = 1. Then u belongs to W(S e ) for e = 1 or 2. Let (f 1 , ..., f q , f * ) be the amalgam decomposition of v. By induction hypothesis, there exist words v 1 , ..., v q , v * such that v

0,1,2 R v 1 ••• v q v * holds, v i lies in W(S o(fi)
) and represents f i for i = 1, ..., q, and v * lies in W(S 1,2 ) and represents f * . We consider the various ways AD(w) can be obtained from AD(v) and from u, hereafter denoted by h, an element of G e .

We consider f * h, which, by hypothesis, lies in G e , and its word representative v * u, which lies in W(S e ) and satisfies a(v * u) = 1. Assume first h ∈ G 1,2 . In this case, f * h lies in G 1,2 as well, and we have r = q with AD(w) = (f 1 , ..., f q , f * h). By induction hypothesis (or by Lemma 2.6(ii) applied in S e |R e ), there exist a word u * in W(S 1,2 ) such that v * u 0,1,2 R u * holds and, therefore, u * represents f * u. Then we have w

0,1,2 R v 1 ••• v q u *
, and the words v 1 , ..., v q , u * have the expected properties.

Assume now h ∈ G e \ G 1,2 with q = 0 or o(f q ) = e. In this case, f * h lies in G e \ G 1,2 , and we have r = q + 1 with AD(w) = (f 1 , ..., f q , h 1 , h * ) where (h 1 , h * ) is the amalgam decomposition of f * h. Now, as above, we have a(v * u) = 1, so, by induction hypothesis, there exist words u 1 , u * such that v * u 0,1,2 R e u 1 u * holds, u 1 lies in W(S e ) and represents h 1 , and u * lies in W(S 1,2 ) and represents h * . Then we have w

0,1,2 R v 1 ••• v q v * u 0,1,2 R v 1 ••• v q u 1 u * ,
and the words v 1 , ..., v q , u 1 , u * have the expected properties.

Assume now h ∈ G e \ G 1,2 with q 1 and o(f q ) = e. Then we consider f q f * h, which, by hypothesis, lies in G e , and its word representative v q v * u: by hypothesis, v q lies in W(S o(fq) ), which is W(S e ), so v q v * u lies in W(S e ) and we have a(v q v * u) = 1. As above in the case of v * u, two cases arise. Assume first f q f * h ∈ G 1,2 . In this case, we have r = q -1 and AD(g) = (f 1 , ..., f q-1 , f q f * h). By induction hypothesis (or by Lemma 2.6), there exists u * of W(S 1,2 ) satisfying v q v * u 0,1,2 R u * and, therefore, u * represents f q f * u. Then we have w

0,1,2 R v 1 ••• v q v * u 0,1,2 R v 1 ••• v q-1
u * , and v 1 , ..., v q-1 , u * have the expected properties. Assume finally f q f * h ∈ G e \ G 1,2 . Then we have r = q with AD(g) = (f 1 , ..., f q-1 , h 1 , h * ) where (h 1 , h * ) is the amalgam decomposition of f q f * h. As above, we have a(v q v * u) = 1 so, by induction hypothesis, there exist u 1 and u * such that v * u 0,1,2 R u 1 u * holds, u 1 lies in W(S e ) and represents h 1 , and u * lies in W(S 1,2 ) and represents h * . Then we have w

0,1,2 R v 1 ••• v q v * u 0,1,2 R v 1 ••• v q-1 u 1 u * ,
and v 1 , ..., v q-1 , u 1 , u * have the expected properties. Lemma 2.17. Assume that S ′ is included in S and g lies in S ′ . Then all entries of the amalgam decomposition of g lie in S ′ . More precisely, if AD(g) is (g 1 , ..., g r , g * ), g i lies in S ′ ∩ S o(gi) for i = 1, ..., r, and g * lies in S ′ ∩ S 1,2 .

Proof. As S ′ is the union of S ′ ∩ S 1 and S ′ ∩ S 2 , every element of G ′ can be expressed as a product of elements of S ′ ∩ S 1 and S ′ ∩ S 2 , say g 1 ••• g p with g i ∈ S ′ ∩ S ei and e i = e i+1 . For g in S ′ , we define ℓ S ′ (g) to be the minimal value of p for which such a decomposition of g exists. Then we prove the result using induction on ℓ S ′ (g).

Assume first ℓ S ′ (g) = 1. Then g belongs to G e for e = 1 or 2, and ℓ(g) 1 holds. If g lies in G 1,2 , the amalgam decomposition of g is (g), and g lies in S ′ . Assume now g / ∈ G 1,2 . Let w be a word of W(S) that represents g. By P e (S ′ ∩ S e , S 1,2 , w), we find w 1 in W(S ′ ∩ S e ) and w * in W(S ′ ∩ S 1,2 ) satisfying w 0,1,2 R e w 1 w * and w 1 ∈ T e (S 1,2 ). By uniqueness, the amalgam decomposition of g must be (w 1 , w * ) and, by construction, w 1 lies in S ′ ∩ S e and w * lies in S ′ ∩ S 1,2 .

Assume now ℓ S ′ (g) 2. Write g = f h with f, h in S ′ satisfying ℓ S ′ (f ) < ℓ S ′ (g) and ℓ S ′ (h) = 1. Let (f 1 , ..., f q , f * ) be the amalgam decomposition of f . By induction hypothesis, f 1 , ..., f q and f * lie in S ′ . Then, according to the scheme used in the proof of Lemma 2.16, the amalgam decomposition of g is of one of the types

(i) (f 1 , ..., f q , f * h), (ii) (f 1 , ..., f q , h 1 , h * ) with ℓ S ′ (f * h) = 1 and (h 1 , h * ) = AD(f * h), (iii) (f 1 , ..., f q-1 , f q f * h), (iv) (f 1 , ..., f q-1 , h 1 , h * ) with ℓ S ′ (f q f * h) = 1 and (h 1 , h * ) = AD(f q f * h).
By hypothesis, all involved elements, in particular h 1 and h * in cases (ii) and (iv) owing to the induction hypothesis, lie in S ′ ∩ S 1 , S ′ ∩ S 2 , or S ′ ∩ S 1,2 as expected.

Using Lemmas 2.17 and 2.6(ii), we can obtain a more precise version of Lemma 2.16.

Lemma 2.18. Assume that S ′ is included in S and w is a word of W(S) that represents an element of S ′ . Let (g 1 , ..., g r , g * ) be the amalgam decomposition of w. Then there exist words w ′ 1 , ..., w ′ r , w ′ * such that w

0,1,2 R w ′ 1 ••• w ′ r w ′ * holds, w ′ i lies in W(S ′ ∩ S o(gi)
) and represents g i for i = 1, ..., r, and w ′ * lies in W(S ′ ∩ S 1,2 ) and represents g * . The difference with Lemma 2.16 is that, here, we assume that the words w ′ i and w ′ * lie in W(S ′ ), that is, involve letters from S ′ only.

Proof. By Lemma 2.16, we first find w 1 , ..., w r , w * that represent g 1 , ..., g r , g * . Now, by Lemma 2.17, the elements g 1 , ..., g r , g * lie in S ′ . Then Lemma 2.6(ii) implies the existence of w ′ 1 , ..., w ′ r , w ′ * that satisfy w i 0,1,2 R w ′ i for i = 1, ..., r and w * 0,1,2 R w ′ * , and all lie in W(S ′ ) in addition to the other properties. Then we have w

0,1,2 R w 1 ••• w r w * 0,1,2 R w ′ 1 ••• w ′ r w ′ * .
Assume first ℓ(g) = 0. Then, by definition, g and g ′ belong to T 1 (S 0 ∩ S 1 ) (and to G 1,2 ), hence h belongs to S 0 ∩ G 1 , which, by Lemma 2.6, is S 0 ∩ S 1 . So g and g ′ belong to the same left-S 0 ∩ S 1 -coset in G 1 . Then, the hypothesis that T 1 (S 0 ∩ S 1 ) is a S 0 ∩ S 1transversal in G 1 implies g = g ′ .

Assume now ℓ(g) = 1. By definition, there exist e and e ′ such that g belongs to T e (S 0 ∩S e ) and g ′ belongs to T e ′ (S 0 ∩ S e ′ ). By Lemma 2.20(ii), we must have e = e ′ . It follows that h belongs to S 0 ∩ G e , which is S 0 ∩ S e . So g and g ′ belong to the same left-S 0 ∩ S ecoset in G e and, as T e (S 0 ∩ S e ) is a S 0 ∩ S e -transversal in G e , we must have g = g ′ .

Assume finally r 2. By Lemma 2.20(iii), the amalgam decompositions of g and g ′ have the form AD(g) = (g 1 , ..., g r , g * ) and AD(g ′ ) = (g 1 , ..., g r-1 , g ′ r , g ′ * ). By definition of T , the elements τ (g) and τ (g ′ ) belong to T (S 0 ) since g and g ′ do, and g ′ = gh implies

τ (g ′ ) = g ′ r g ′ * = g -1 1 ••• g -1 r-1 g ′ = g -1 1 ••• g -1
r-1 gh = g r g * h = τ (g)h, so τ (g ′ ) and τ (g) lie in the same S 0 -coset. As, by construction, we have ℓ(τ (g)) = ℓ(τ (g ′ )) = 1, the induction hypothesis implies τ (g) = τ (g ′ ), whence g = g ′ .

We are now ready to complete the argument.

Proof of Proposition 2.14. Let S ′ , S 0 be included in S. Two points have to be established, namely that T (S 0 ) is a S 0 -transversal in G and that P T (S ′ , S 0 , w) holds for every word w of W(S) that represents an element of S ′ . We begin with the second point, which we establish using induction on ℓ(w).

(i) Assume first ℓ(w) 1 with w ∈ G 1 . Applying Lemma 2.18 to S ′ and w, we first find w ′ in W(S ′ ∩ S 1 ) satisfying w 0,1,2 R w ′ . Then, applying P 1 (S ′ ∩ S 1 , S ′ ∩ S 0 ∩ S 1 , w ′ ), we find v in W(S ′ ∩ S 1 ) and u in W(S ′ ∩ S 0 ∩ S 1 ) satisfying w ′ 0,1,2 R1 vu and v ∈ T 1 (S 0 ∩ S 1 ). By composing, we deduce w 0,1,2 R vu and, by definition, T 1 (S 0 ∩ S 1 ) is included in T (S 0 ), so v and u witness for P T (S ′ , S 0 , w).

(ii) Assume now ℓ(w) 1 with w ∈ G 2 \ G 1 . Arguing as above, but now in G 2 , we find v in W(S ′ ∩ S 2 ) and u in W(S ′ ∩ S 0 ∩ S 2 ) satisfying w 0,1,2 R 2 vu and v ∈ T 2 (S 0 ∩ S 2 ). By definition, T 2 (S 0 ∩ S 2 ) \ G 1 is included in T (S 0 ), so, if v does not lie in G 1 , the words v and u witness for P T (S ′ , S 0 , w). If v lies in G 1 , hence in G 1,2 , one more step is needed to go from T 2 (S 0 ∩ S 2 ) to T 1 (S 0 ∩ S 1 ). Now, we have ℓ(u) = 0 with u ∈ G 1 , so by (i) we can find v ′ in W(S ′ ∩ S 1 ) and u ′ in W(S ′ ∩ S 0 ∩ S 1 ) satisfying v 0,1,2 R 1 v ′ u ′ and v ′ ∈ T 1 (S 0 ∩ S 1 ), hence v ′ ∈ T (S 0 ). Then we deduce w 0,1,2 R v ′ (u ′ u), and the words v ′ and u ′ u witness for P T (S ′ , S 0 , w).

(iii) Assume now ℓ(w) 2. Let AD(w) = (g 1 , ..., g r , g * ). Applying Lemma 2.18 to S ′ and w, we find words w 1 , ..., w r , w * such that w 0,1,2 R w 1 ••• w r w * holds, w i lies in W(S ′ ∩S o(gi) ) and represents g i for i = 1, ..., r, and w * lies in W(S ′ ∩S 1,2 ) and represents g * . Let e = o(g r ).

By construction, we have ℓ(g r g * ) = 1 with g r g * ∈ G e . By (i) or (ii) applied to w r w * , we find words v r in W(S ′ ∩ S e ) and u in W(S ′ ∩ S 0 ∩ S e ) satisfying w r w * 0,1,2 Re v r u and v r ∈ T e (S 0 ∩ S e ). So, if we put v = w 1 ••• w r-1 v r , then w 0,1,2 vu is true. Two cases are possible. If v r does not belong to G 1,2 , then (g 1 , ..., g r-1 , v r ) is the amalgam decomposition of v, and v lies in T (S 0 ). Then the words v and u witness for P T (S ′ , S 0 , w). On the other hand, if v r belongs to G 1,2 , we have ℓ(v) < ℓ(w). Then, by induction hypothesis, we can find v ′ in W(S ′ ) and u ′ in W(S ′ ∩ S 0 ) satisfying v 0,1,2 R v ′ u ′ and v ′ ∈ T (S 0 ). Then we deduce w 0,1,2 R v ′ (u ′ u), and the words v ′ and u ′ u witness for P T (S ′ , S 0 , w). So, the proof of P T (S ′ , S 0 , w) is complete, and the only thing still to be proven is that T (S 0 ) is an S 0 -transversal. This amonts to proving two facts, namely that two distinct elements of T (S 0 ) never lie in the same S 0 -coset, which has been done in Lemma 2.21, and that, for every g in G, there exists an element of T (S 0 ) is the left-S 0 -coset of g. Now the latter point follows from P T (S, S 0 , w). Indeed, let w be any word representing g. By P T (S, S 0 , w), we find v in W(S) and u in W(S 0 ) satisfying w 0,1,2 R vu and v ∈ T (S 0 ). Then u lies in S 0 , and v is an element of T (S 0 ) lying in the left-S 0 -coset of g.

Thus the proof that all Artin-Tits presentations of type FC satisfy Properties H ♯ and H (Proposition 2.1) is complete.

A syntactic approach

Our proof of Property H for type FC is essentially based on the existence of a distinguished normal form for the elements of the considered Artin-Tits group. Although the approach is simple, it seems unlikely that it could lead to a proof of Conjecture 1.6 as the construction of a similar normal form in the case of general Artin-Tits presentations seems out of reach. Also, the possible interest of Property H is to provide some control of a group even in the case when no solution to the word problem is known, and using a preexisting solution to that word problem to establish Property H is not natural. In this section, we develop another approach, which leads to Property H directly and does not appeal to any normal form or, more generally, to any solution of the word problem. The principle is to start from a derivation that involves transformations of type 0, 1, and ∞ and eliminate type ∞ transformations by introducing type 2 transformations instead.

We show in Subsection 3.1 how to realize this strategy in the case of right-angled Artin-Tits presentations. A few additional comments are included in Subsection 3.2.

3.1. Right-angled Artin-Tits presentations. An Artin-Tits presentation is said to be right-angled if it only involves commutation relations st = ts. Right-angled Artin-Tits presentations all are of FC type, so Proposition 2.5 implies Proposition 3.1. Every right-angled Artin-Tits presentation satisfies Property H.

We shall now give a new proof of this result relying on a purely syntactic approach. The argument requires several auxiliary developments and will be completed at the end of the subsection. Until there, we assume that (S, R) is a fixed right-angled Artin-Tits presentation, and denote by G the group S|R .

Assume that w is a word of W(S) that represents 1 in G. Then we have w 0,1,∞ R ε, so there exists a sequence of words w 0 , ..., w m with w 0 = w, w m = w ′ and, for every k, the word w k is obtained from w k-1 by applying a special transformation of type 0, 1, or ∞. The idea will be to mark the additional letters created in type ∞ steps and to follow their subsequent destiny in the derivation. The point is that, when we erase these additional letters in a convenient way, the remaining words will make a derivation in terms of type 0, 1, and 2 transformations.

Implementing the above simple principle requires taking into account the step at which each additional letter is created. This leads us to introducing an augmented alphabet S where all letters include a number that corresponds to their age, that is, the date of their creation and, accordingly, an augmented version -R of the relation R for words of W(S). Definition 3.2. We denote by S the alphabet consisting of one letter s [i] for each letter s of S and each nonnegative integer i; we identify s with s [0] . We denote by φ the alphabetical homomorphism of W(S) to W(S) that maps every letter s [i] to s. For h 0, we denote by π h the alphabetical homomorphism of W(S) to itself that maps s [i] to itself for i < h and to ε for i h.

The argument for Proposition 3.1 will be inductive. Here is the basic step for the induction.

Lemma 3.7. Assume that w is a regular augmented word and w ′ is obtained from w using one special transformation. Then (i) The word w ′ is regular;

(ii) If w or w ′ contains at least one letter of positive index and if h is the highest index of a letter occurring in w and w ′ , the relation π h (w)

0,1,2,∞ -R π h (w ′ ) holds; (iii) The relation π 1 (w) 0,1,2 R π 1 (w ′ ) holds.
Proof. We first establish (i) and (ii) by considering the possible types of special transformations connecting w to w ′ . We begin with type 0, that is, we assume that w ′ is obtained from w by removing some factor s e

[i] s -e [j] , e = ±1, and replacing the remaining occurrences of s ±1

[i] and s ±1

[j] with s ±1 [min(i,j)] . (i) If h is neither i nor j, the possible letters of index h in w ′ are those of w, and the commutativity condition is unchanged (if the deleted factor is not nested in the possible h-pair), or weakened. In any case, the hypothesis that w satisfies the properties implies that w ′ does too. Assume now h = i < j. Then we must be in the case when w contains a commutative h-pair, say s e

[h] vs -e [h] , and w ′ is obtained by removing one of the letters s -e

[h] together with some adjacent s ±1

[j] , which occurs in some j-pair s d ... , and the point is that the hypotheses that r commutes with φ(π h (v)) and, on the other hand, with s, implies that it commutes with φ(π h (s e

[j] v ′ s -d [j] .
[i] v)) in every case. So the possible h-pair of w ′ is commutative, and w ′ is regular (ii) Again, if h is larger than i and j, removing the letters of index h changes nothing essential and we obtain π h (w) 1 -R π h (w ′ ). On the other hand, if h = i > j holds, removing the letters of index h cancels the effect of the transformation, and we simply have

π h (w) = π h (w ′ ), hence (trivially) π h (w) 0,1,2,∞ -R π h (w ′ ).
We now consider type 2 and assume that w ′ is obtained from w by replacing s e

[i] t -e [j] with t -e [j] s e [i]
, where st = ts is a relation of R and e is ±1. Both for (i) and (ii), the argument is similar to that of type 1, the only difference being that the commuted letters have now opposite signs (a specificity of the right-angled case).

Finally we consider type ∞, that is, assume that w ′ is obtained from w by inserting some pair s e

[i] s -e [i] , e = ±1, where i is strictly larger than every index of letter occurring in w. (i) If h is not i, in which case h < i holds by definition, the possible h-pair of w provides an h-pair in w ′ . We have no commutation hypothesis involving the letter s, but, even if the inserted pair is nested in the h-pair as in we are sure that r commutes with every letter of φ(π h (vs e [i] s -e [i] v ′ )) as the latter word coincides with φ(π h (vv ′ )). So w ′ is regular.

(ii) By definition, we have π h (w) = π h (w ′ ), whence again π h (w) 0,1,2,∞ -R π h (w ′ ). So the proof of (i) and (ii) is complete, and it remains to deduce (iii). First, we claim that π h (w) 0,1,2,∞ -R π h (w ′ ) holds for every h 1. Indeed, the result is obvious if h is larger than every index of letter occurring in w and w ′ since, in this case, we have π h (w) = w and π h (w ′ ) = w ′ . Then the result follows from (ii), using a decreasing induction on h since applying π h to a word where the largest index is h yields a word where the largest index is at most h -1. So we obtain π 1 (w) 0,1,2,∞ -R π 1 (w ′ ). Now, the word π 1 (w ′ ) contains no letter of positive index. As no type ∞ transformation can lead to a word containing no letter with positive index, the only possibility is that π 1 (w) 0,1,2 -R π 1 (w ′ ) holds, as expected.

We can now combine the results to obtain the expected new proof of Proposition 3.1.

Proof of Proposition 3.1. Let w be a word of W(S) that represents 1 in S|R . Then, by (1.1), we have w 0,1,∞ R ε. Fix a special sequence w 0 , w 1 , ..., w m going from w to the empty word.

By Lemma 3.4, we can find a special sequence of augmented words w 0 , w 1 , ... such that w 0 coincides with w 0 and, for every k, the word w k is the image of w k under φ.

By definition, the (augmented) word w 0 contains no letter of positive index, hence it is regular. Hence, by Lemma 3.7(i), every augmented word w k is regular. Then Lemma 3.7(iii) implies π 1 ( w k-1 ) 0,1,2 -R π 1 ( w k ) for each k. We deduce π 1 ( w 0 ) 0,1,2 R π 1 ( w m ), which is the expected relation w

aBcAbC ∞ aBAacAbC 1 R aABacAbC 0 BacAbC 1 R BcaAbC 0 BcbC 1 R BbcC 0 cC 0 ε aBcAbC ∞ -aBA 1 a 1 cAbC 1 -R aA 1 Ba 1 cAbC 0 -BacAbC 1 -R BcaAbC 0 -BcbC 1 -R BbcC 0 -cC 0 -ε aBcAbC = aBcAbC = aBcAbC 2 R BacAbC 1 R BcaAbC 0 BcbC 1 R BbcC 0 cC 0 ε. ↑ φ ↓ π 1 ↑ φ ↓ π 1 ↑ φ ↓ π 1 ↑ φ ↓ π 1 ↑ φ ↓ π 1 ↑ φ ↓ π 1 ↑ φ ↓ π 1 ↑ φ ↓ π 1 ↑ ↓
(Of course, this example is nearly trivial as one type ∞ transformation only occurs in the initial sequence.)

3.2. Further remarks. Extending the method of Subsection 3.1 to more general Artin-Tits presentations is a challenge we leave open. The technical problem is to find augmented versions of type 2 transformations: in the right-angled case, the latter just are commutations, and the definition is clear; in more complicated cases, things are not so clear. Let us just mention that, in the case of a length 3 relation sts = tst, geometric interpretations suggest that the proper way of defining an augmented version of the type 2 transformation s -1 t 2 R tst -1 s -1 could be to put s -1

[i] t [j] 2 -R t [k] s [j] t -1 [i] s -1 [k] ,
where k is larger than every index of letter occurring in the current word.

Let us still mention two more approaches. First, a natural way for proving Conjecture 1.6 could be to establish the confluence of the relation 0,1,2 R , namely to prove that, if we have both w 0,1,2 R w ′ and w 0,1,2 R w ′′ , then there exists a word w ′′′ satisfying w ′ 0,1,2 R w ′′′ and w ′′ 0,1,2 R w ′′′ . However, as the relation 0,1,2 R need not be Noetherian in general (that is, there may exist infinite special sequences), establishing confluence is not easy.

On the other hand, working with

0,1,2
R is in general difficult because this relation is highly non-deterministic: for every word w, there exist in general many words w ′ such that w 0,1,2 R w ′ is satisfied. In [START_REF] Dehornoy | A fast method for comparing braids[END_REF], an algorithm called handle reduction is constructed in the case of classical braids, that is, of Artin-Tits groups of type A. This algorithm, called handle reduction, extends free group reduction, and it returns for every word w an equivalent word HR(w) with the property that, if w represents 1, then HR(w) is the empty word. However, this algorithm is not a normal form, as w ≡ R w ′ need not imply HR(w) = HR(w ′ ). A precise analysis of the algorithm shows that w 0,1,2 R HR(w) always holds and, therefore, we obtain another proof of Property H in this case. In this approach, handle reduction is used as a strategy for choosing, for every word w, a distinguished word among the many words w ′ that satisfy w 0,1,2 R w ′ . It is natural to wonder whether such an approach, which a priori is less ambitious than constructing a normal form, might apply to more general situations.

Figure 2 .

 2 Figure 2. Whenever ca = ace, cb = bce, da = adf, and db = bdf are valid relations, the word w = ACdaBDcb represents 1. However it is eligible for no special transformation, hence cannot satisfy w 0,1,2 R ε.

1 R

 1 u ′ . Otherwise, we must have |u| < |v|, whence |u| |v|-1, and |u ′ | |v|-2. By hypothesis, we have |u|+ |u ′ | = |v|+ |v ′ |, and we deduce |v| + |v ′ |

Example 1 . 10 .

 110 Consider S = {a, b} and let R consist of the unique relation abab = baba. Then (S, R) is an Artin-Tits presentation of extra-large type, and the associated Coxeter group is the eight element dihedral group. Let w = Ab 2 abaB and w ′ = ababA. Then w and w ′ are R-equivalent, we have |w| = 7 > |w ′ | = 5. So w 0,D R w ′ holds. We claim that w 0,1,2

Figure 3 .

 3 Figure 3. Proving that w w ′ fails in Example 1.10: the word w is traced from

  ... r e [h] vv ′ r -e [h] ... ∞ -... r e [h] vs e [i] s -e [i] v ′ r -e [h] ... ,

Example 3 . 8 .

 38 Applying the above argument to the case of Example 3.5 amounts to collapsing all letters with positive index and forgetting indices. Starting from the initial sequence that contains a type ∞ step (top), we lift it into an augmented sequence (middle, we drop the zero indices), and project it into a new sequence that contains no type ∞ steps (down):

  gh, and write h = h 1 h -1 2 with h 1 , h 2 in S 0 + . Then we have gh 1 = g ′ h 2 . By Lemma 2.10, h 2 right-divides h 1 , that is, h belongs to S 0 + . Then we obtain |N ℓ (gh)| = |gh| |g| = |N ℓ (g)|, and g is S 0 -minimal.

  So, up to symmetries, we may assume that we are in the situation

	the letters nested in the h-pair are not changed; otherwise, up to symmetries, the typical
	case is
	...s e [i] r e [h] vr -e [h] ...	1 -R	...r e [h] s e [i] vr -e [h]
	... s e [h] vs -e [h] s e [j] v ′ s -e [j] ...

Work partially supported by the ANR grant TheoGar ANR-08-BLAN-0269-02.

Our aim is to prove that (S, R) satisfies Property H ♯ and, therefore, we must construct, for every subset S 0 of S, a distinguished S 0 -transversal T (S 0 ) in the group G. To this end, we use the transversals T 1 (S 0 ∩S 1 ) and T 2 (S 0 ∩S 2 ). The natural idea is that T (S 0 ) consists of those elements of G whose tail belongs to T e (S 0 ∩ S e ) for e = 1 or 2-we recall from Definition 2.15 that the tail τ (g) of g is the maximal final chunk of g that lies in G 1 or G 2 . To avoid the ambiguities resulting from the fact that, on G 1 ∩ G 2 , the transversals T 1 (S 0 ∩ S 1 ) and T 2 (S 0 ∩ S 2 ) need not coincide, we systematically choose T 1 (S 0 ∩ S 1 ) whenever possible. Definition 2.19. For S 0 included in S, we put

We shall show that T is an S-sequence of transversals witnessing for Property H ♯ . Note that, the hypothesis that T 1 (S 0 ∩ S 1 ) contains 1 implies that T (S 0 ) contains 1 as well. We begin with two preparatory results.

Lemma 2.20. Assume that S 0 is included in S, that g lies in T (S 0 ) and that g ′ lies in the left-S 0 -coset of g. Let (g 1 , ..., g r , g * ) and (g ′ 1 , ..., g ′ r ′ , g ′ * ) be the amalgam decompositions of g and g ′ . Then we have

Proof. By hypothesis, there exists h in S 0 such that g ′ = gh holds. Let (h 1 , ..., h q , h * ) be the amalgam decomposition of h. By Lemma 2.17 applied to S 0 , the elements h 1 , ..., h q , h * all lie in S 0 . The results are obvious or vacuously true for r = 0, and we assume r 1, with o(g r ) = e. We determine AD(g ′ ) starting from AD(g) and AD(h) using arguments similar to those of Lemma 2.16. The point is that the case when the length of the amalgam decomposition decreases turns out to be impossible. Write e for 3e.

For q = 0, we find AD(g ′ ) = (g 1 , ..., g r , hh * ), and ℓ(g ′ ) = r, so everything is clear.

Next assume q

. By hypothesis, g * h 1 lies in G e \ G 1,2 , which, by uniqueness of the amalgam decomposition, implies f 1 ∈ T e (S 1,2 ) (and p = q, but this is not needed here). In this case, we have AD(gg 0 ) = (g 1 , ..., g r , f 1 , ..., f p , f * ). We deduce ℓ(g ′ ) = r + p r and the other expected results.

Assume now q 1 with h 1 ∈ T e (S 1,2 ) and g r g * h 1 / ∈ G 1,2 . Let AD(g r g * h) = (f 1 , ..., f p , f * ). By hypothesis, g r g * h 1 lies in G e \ G 1,2 , which implies p 1 and f 1 ∈ T e (S 1,2 ). In this case, we find AD(g ′ ) = (g 1 , ..., g r-1 , f 1 , ..., f p , f * ). We deduce ℓ(g ′ ) = r -1 + p r and the other expected results.

Assume finally q 1 with h 1 ∈ T e (S 1,2 ) and g r g * h 1 ∈ G 1,2 . By definition, the hypothesis that g belongs to T (S 0 ) implies that g r g * lies in T e (S 0 ∩ S e ). On the other hand, by Lemma 2.17 applied with S ′ = S 0 , the hypothesis that h lies in S 0 implies that h 1 lies in S 0 ∩ S e . Here comes the point. Let w be any word of W(S e ) that represents g r g * h 1 .

Then P e (S 1,2 , S 0 ∩S e , w) implies the existence of v in W(S 1,2 ) and u in W(S 1,2 ∩S 0 ) satisfying w 0,1,2 R e vu and v ∈ T e (S 0 ∩ S e ). Now, as h 1 lies in S 0 ∩ S e and T (S 0 ∩ S e ) is a S 0 ∩ S etransversal, we must have v = g r g * and u = h 1 . But this implies g r g * ∈ G 1,2 , whence g r ∈ G 1,2 , which contradicts the definition of AD(g). This case, which is the one that could possibly lead to ℓ(g ′ ) < ℓ(g) is therefore impossible. So the proof is complete. Lemma 2.21. For every S 0 included in S, the set T (S 0 ) does not contain two distinct elements lying in the same left-S 0 -coset.

Proof. Assume that g, g ′ belong to T (S 0 ) and lie in the same left-S 0 -coset of G. By Lemma 2.20, we have ℓ(g) ′ ℓ(g), and ℓ(g) ℓ(g ′ ), whence ℓ(g) = ℓ(g ′ ). Put h = g -1 g ′ , an element of S 0 . We now prove g = g ′ by considering the various possible values of ℓ(g).

Words of W(S) will be called augmented. Thus, assuming that a, b, c are letters of S, a typical augmented word is a 1 B 0 c 2 A 1 c 0 . Its image under φ is the (standard) word aBcAc (all indices are forgotten), whereas its image under π 2 is a 1 B 0 A 1 c 0 (all letters with index 2 and larger are erased), and its image under π 1 is B 0 c 0 . Definition 3.3. Special transformations on augmented words are defined as follows:

-type 0: Remove some pair s , e = ±1, where i is strictly larger than every index of letter occurring in the current word. We write w X -R w ′ if w ′ can be obtained from w by a finite sequence of special transformations of type belonging to X. Special transformations on augmented words are liftings of the corresponding special transformations on words: a straightforward inspection shows that, if an augmented word w ′ is the image of another augmented word w under a transformation of type i, then the (nonaugmented) word φ(w ′ ) is the image of φ(w) under a transformation of type i.

The first observation is that every sequence of special transformations on standard words can be lifted into a sequence of special transformations on augmented words. Hereafter, we say that (w 0 , w 1 , ...) is a special sequence of (possibly augmented) words if every word w k is obtained from w k-1 using a special transformation. Lemma 3.4. For every special sequence (w 0 , w 1 , ...) in W(S), there exists a special sequence of augmented words ( w 0 , w 1 , ...) such that w 0 equals w 0 and, for every k, the word w k is the image of w k under φ and, moreover, the type of the transformation connecting w k-1 to w k is the same as the type of the transformation connecting w k-1 to w k .

Proof. We start from w 0 = w 0 and use an induction. For steps of type 0, 1, or 2, we just mimick the transformation. For steps of type ∞, that is, when w k is obtained from w k-1 by inserting a pair s e s -e , we define w k from w k-1 by inserting s e

, where i is the maximum of all indices of letters occurring in w k augmented by 1.

Example 3.5. Assume S = {a, b, c} and let R = {ab = ba, bc = cb, ac = ca}. Then (S, R) is a right-angled Artin-Tits presentation. As in Section 1, consider w = aBcAbC. Then, starting from the special sequence aBcAbC ∞ aBAacAbC 1 R aABacAbC 0 BacAbC 1 R BcaAbC 0 BcbC 1 R BbcC 0 cC 0 ε and using the method of Lemma 3.4 gives

where we write a i for a [i] .

The main point now is to control the properties of the augmented words that appear when special sequences are lifted. Definition 3.6. (i) An augmented word of the form r e

[h] wr -e [h] is called an h-pair ; it is said to be commutative if rs = sr is a relation of R for every letter s such that s ±1 occurs in φ(π h (w)) (that is, such that some letter s ±1

[i] with i h occurs in w). (ii) An augmented word w is said to be regular if, for every h 1, either w contains no letter of index h, or it contains exactly two such letters forming a commutative h-pair.