Artin groups and Coxeter groups

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia

Last update: 26 January 2014

Reduction Rule

In these paragraphs we prove that one can always reduce in the Artin semigroup.

2.1. The main result in this section is the reduction lemma which will be used again and again in this work.

Reduction lemma. For each Coxeter matrix we have the following reduction rule:

If X and Y are positive words and a and b are letters such that aXbY then there exists a positive word W such that Xbamab-1 WandY abmab-1 W.


The proof is by a double induction, first on the length L(X) of the word X and then on the length t of the positive transformation from aX to bY.

Let Aλ be the statement of the lemma for words of length L(X)=λ and let Aλ,τ be the statement under the additional condition that aX can be transformed into bY by a positive transformation of length τ. The base cases A0 and Aλ,0 are trivial. Thus we assume now that Aλ for λ<l and Al,τ for τ<t hold and prove Al,t.

Assume that aX is transformed into bY by a positive transformation of length t. Then there is a positive word cZ such that aX becomes cZ under an elementary transformation and cZ becomes bY by a positive transformation of length t-1. If either ca or cb then it follows immediately from Al,τ for τ<t that XZ, resp. YZ, and through renewed application of Al,τ, the assertion of the lemma follows.

Hence we suppose that ca and cb. Since cZ arises from an elementary transformation of aX, and the induction assumption Al,τ is applicable to cZ and bY, then there exist positive words U and V such that: X camac-1U and Z acmac-1 U, Y cbmac-1V and Z bcmbc-1 V. If ab then it follows from the two relations for Z that UV, by using the induction hypothesis for Aλ, λ<l. Then it follows from the other two relations that XY, completing the case when ab.

From this point we assume that a, b and c are pairwise distinct. Let Ma,b,c be the Coxeter matrix on {a,b,c} defined by mab, mac and mbc. The proof of the induction step for certain cases is already set out by Garside - namely for the cases in which Ma,b,c defines a finite Coxeter group. This is known to be precisely the when the corresponding Graph is one of the following three vertex Coxeter graphs: p 3p 3 p 3p5 The cases are completed by reproducing exactly the line of reasoning in the proof of Garside [Gar1969] p. 237 and 253. Thus the proof will be complete when we can show that the other cases, in which Ma,b,c does not define a finite group, can be dealt with. The remainder of the proof of 2.1 follows from the induction assumption Aλ for λ<l and the following Lemma 2.2.

2.2. The reason that we can deal with the above mentioned case is that the relation aXbYcZ is only possible for finite GMa,b,c. To see this we must first prove the following somewhat complicated lemma.

Let M be a Coxeter matrix for which the statement of the reduction lemma hold for words X such that L(X)<l. Let a,b,c be pairwise distinct letters for which the Coxeter matrix Ma,b,c does not define a finite Coxeter group. Then there do not exist positive words U,V, and Z with L(Z)l and Zacmac-1 Ubcmbc-1 V.


We assume that U,V and Z are positive words for which the given relation holds and derive a contradiction. We will consider the different cases for the graph Γ of Ma,b,c. We get from the classification of Coxeter systems of rank three that we have the following possibilities. Case 1:Γis a cycle pq withp,q,r3. Case 2:Γis a tree qrp withp,q>3. Case 3:Γis a tree 3rp withp>5. In cases 2 and 3 we will also have to distinguish the different possibilities for the choice of the vertex c in these graphs.

Case 1: We will prove in this case the stronger statement: There do not exist positive words Z, W1, W2 with L(Z)< and ZaW1bc W2. Assume that there are such words. Let these be chosen such that L(Z) is minimal. By repeated applications of the reduction rule on the last equality of the given relation we get the existence of words W3, W4, W5 for which aW1 bcW2 cW2 abW3 bW3 caW4 aW4 bcW5. Setting W14 and W2W5 and ZaW4 we get ZaW1 bcW2, and L(Z)<L(Z), contradicting the minimality of L(Z). The remaining cases are similar and we shall be more brief.

Case 2: There are two cases to consider:

(i) c is one of the two end points of Γ,
(uu) c is the middle point of Γ.

(i) Let us suppose that a is the other end point. Suppose that we are given a relation between positive words of minimal length aW1bcW2. From successive applications of the reduction lemma we have the existence of W3, W4, W5, W6 with aW1 bcW2 cW2 abaW3 baW3 cW4 aW3 cbcW5 bcW5 aW6. On account of the last relation L(W6)<L(W1) contradicting the minimality of L(W1).

(ii) From a relation aW1bcbW2 between positive words of minimal length and successive applications of the reduction lemma we have the existence of W3, W4 with bW2 acaW3 aW3 babW4. The last relation combined with L(W3)<L(W1) gives a contradiction.

Case 3: We distinguish three cases:

(i) c is the “middle” point of Γ (thus mac=3, mbc=p),
(ii) c is the “left” point of Γ (thus mac=2, mbc=3),
(iii) c is the “right” point of Γ (thus mac=2, mbc=p).

(i) Assume that there is a relation aW1bcbcW2 between positive words, the relevant words being of minimal length. By a four fold application of the reduction lemma it follows that there exist words W3 and W4 with bcW2 acW3 W3 bcmbc-1 W4. Substituting the second equation into the first, applying the defining relation and the reduction lemma gives cW2 acbmbc-1 W4. Again, a two fold application of the reduction lemma gives the existence of a word W5 with aW5 bcmbc-2 W4. This relation combined with L(W5)<L(W1) contradicts the minimality of L(W1).

(ii) Assume that there is a relation aW1 bcW2 between words of length less than l. It follows from the reduction lemma that there exists a word W3 with cW2 abmab-1 W3. One such relation can from (i) not be valid, and the same analysis as in (i) except for only some changes in the markings of the letters and the words.

(iii) Assume that there is a relation aW1 bcbcbW2 between words of length <. It follows from the reduction lemma that there exists a word W3 with aW3 cbcbW2 Again, by (i), such a relation cannot hold.

Thus all cases are settled and Lemma 2.2 is proved.

2.3. We shall derive a few easy conclusions from the reduction lemma.

First we note the following. From 2.1 and 2.2 it follows that a positive word can only be divisible by 3 different letters a,b,c if the associated Coxeter matrix Ma,b,c defines a finite Coxeter group. Later this statement will be generalized even further.

In addition we remark that in analogy to 2.1 we naturally get a reduction lemma for reduction on the right side. One can reach this conclusion as follows. For each positive word Aai1 aik define the positive word rev A by revAaik ai1. Clearly AB implies revArevB since the passage from A to revA is compatible with elementary transformations. It is clear that the application of rev to the words in Lemma 2.1 gives the right hand analog.

From Lemma 2.1 and the right hand analog we get the following:

If A,B and X,Y are positive words with AXBAYB then XY.

The Artin monoid GM+ thus satisfies the cancellation condition.

Notes and references

This is a translation, with notes, of the paper, Artin-Gruppen und Coxeter-Gruppen, Inventiones math. 17, 245-271, (1972).

Translated by: C. Coleman, R. Corran, J. Crisp, D. Easdown, R. Howlett, D. Jackson and A. Ram at the University of Sydney, 1996.

page history