Last update: 26 January 2014
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 and are positive words and and are letters such that then there exists a positive word such that
The proof is by a double induction, first on the length of the word and then on the length of the positive transformation from to
Let be the statement of the lemma for words of length and let be the statement under the additional condition that can be transformed into by a positive transformation of length The base cases and are trivial. Thus we assume now that for and for hold and prove
Assume that is transformed into by a positive transformation of length Then there is a positive word such that becomes under an elementary transformation and becomes by a positive transformation of length If either or then it follows immediately from for that resp. and through renewed application of the assertion of the lemma follows.
Hence we suppose that and Since arises from an elementary transformation of and the induction assumption is applicable to and then there exist positive words and such that: If then it follows from the two relations for that by using the induction hypothesis for Then it follows from the other two relations that completing the case when
From this point we assume that and are pairwise distinct. Let be the Coxeter matrix on defined by and The proof of the induction step for certain cases is already set out by Garside - namely for the cases in which 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: 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 does not define a finite group, can be dealt with. The remainder of the proof of 2.1 follows from the induction assumption for and the following Lemma 2.2.
2.2. The reason that we can deal with the above mentioned case is that the relation is only possible for finite To see this we must first prove the following somewhat complicated lemma.
Let be a Coxeter matrix for which the statement of the reduction lemma hold for words such that Let be pairwise distinct letters for which the Coxeter matrix does not define a finite Coxeter group. Then there do not exist positive words and with and
We assume that and are positive words for which the given relation holds and derive a contradiction. We will consider the different cases for the graph of We get from the classification of Coxeter systems of rank three that we have the following possibilities. In cases 2 and 3 we will also have to distinguish the different possibilities for the choice of the vertex in these graphs.
Case 1: We will prove in this case the stronger statement: There do not exist positive words with and Assume that there are such words. Let these be chosen such that is minimal. By repeated applications of the reduction rule on the last equality of the given relation we get the existence of words for which Setting and and we get and contradicting the minimality of The remaining cases are similar and we shall be more brief.
Case 2: There are two cases to consider:
(i) Let us suppose that is the other end point. Suppose that we are given a relation between positive words of minimal length From successive applications of the reduction lemma we have the existence of with On account of the last relation contradicting the minimality of
(ii) From a relation between positive words of minimal length and successive applications of the reduction lemma we have the existence of with The last relation combined with gives a contradiction.
Case 3: We distinguish three cases:
(i) Assume that there is a relation 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 and with Substituting the second equation into the first, applying the defining relation and the reduction lemma gives Again, a two fold application of the reduction lemma gives the existence of a word with This relation combined with contradicts the minimality of
(ii) Assume that there is a relation between words of length less than It follows from the reduction lemma that there exists a word with 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 between words of length It follows from the reduction lemma that there exists a word with 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 if the associated Coxeter matrix 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 define the positive word rev by Clearly implies since the passage from to 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 and are positive words with then
The Artin monoid thus satisfies the cancellation condition.
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.