Artin groups and Coxeter groups

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

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 $a X ⩦ b Y$ then there exists a positive word $W$ such that $X ⩦ {⟨ b a ⟩}^{m_{a b} - 1} W and Y ⩦ {⟨ a b ⟩}^{m_{a b} - 1} W .$

Proof.

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 $a X$ to $b Y .$

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 $a X$ can be transformed into $b Y$ by a positive transformation of length $τ .$ The base cases $A_{0}$ and $A_{λ, 0}$ are trivial. Thus we assume now that $A_{λ}$ for $λ < l$ and $A_{l, τ}$ for $τ < t$ hold and prove $A_{l, t} .$

Assume that $a X$ is transformed into $b Y$ by a positive transformation of length $t .$ Then there is a positive word $c Z$ such that $a X$ becomes $c Z$ under an elementary transformation and $c Z$ becomes $b Y$ by a positive transformation of length $t - 1 .$ If either $c \equiv a$ or $c \equiv b$ then it follows immediately from $A_{l, τ}$ for $τ < t$ that $X ⩦ Z,$ resp. $Y ⩦ Z,$ and through renewed application of $A_{l, τ},$ the assertion of the lemma follows.

Hence we suppose that $c ≢ a$ and $c ≢ b .$ Since $c Z$ arises from an elementary transformation of $a X,$ and the induction assumption $A_{l, τ}$ is applicable to $c Z$ and $b Y,$ then there exist positive words $U$ and $V$ such that: $\begin{matrix} X ⩦ {⟨ c a ⟩}^{m_{a c} - 1} U and Z ⩦ {⟨ a c ⟩}^{m_{a c} - 1} U, \\ Y ⩦ {⟨ c b ⟩}^{m_{a c} - 1} V and Z ⩦ {⟨ b c ⟩}^{m_{b c} - 1} V . \end{matrix}$ If $a \equiv b$ then it follows from the two relations for $Z$ that $U ⩦ V,$ by using the induction hypothesis for $A_{λ},$ $λ < l .$ Then it follows from the other two relations that $X ⩦ Y,$ completing the case when $a \equiv b .$

From this point we assume that $a,$ $b$ and $c$ are pairwise distinct. Let $M_{a, b, c}$ be the Coxeter matrix on ${a, b, c}$ defined by $m_{a b},$ $m_{a c}$ and $m_{b c} .$ The proof of the induction step for certain cases is already set out by Garside - namely for the cases in which $M_{a, 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: $\begin{matrix} p & 3 \leq p \\ 3 & p & 3 \leq p \leq 5 \end{matrix}$ 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 $M_{a, 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 $a X ⩦ b Y ⩦ c Z$ is only possible for finite ${\overline{G}}_{M_{a, 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 $M_{a, b, c}$ does not define a finite Coxeter group. Then there do not exist positive words $U, V,$ and $Z$ with $L (Z) \leq l$ and $Z ⩦ {⟨ a c ⟩}^{m_{a c} - 1} U ⩦ {⟨ b c ⟩}^{m_{b c} - 1} V .$

Proof.

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 $M_{a, b, c} .$ We get from the classification of Coxeter systems of rank three that we have the following possibilities. $\begin{matrix} Case 1: Γ is a cycle^{p}^{q} with p, q, r \geq 3 . \\ Case 2: Γ is a tree q^{r} p with p, q > 3 . \\ Case 3: Γ is a tree 3^{} p with p > 5 . \end{matrix}$ 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,$ $W_{1},$ $W_{2}$ with $L (Z) < ℓ$ and $Z ⩦ a W_{1} ⩦ b c W_{2} .$ 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 $W_{3},$ $W_{4},$ $W_{5}$ for which $\begin{matrix} a W_{1} & ⩦ & b c W_{2} \\ c W_{2} & ⩦ & a b W_{3} \\ b W_{3} & ⩦ & c a W_{4} \\ a W_{4} & ⩦ & b c W_{5} . \end{matrix}$ Setting $W_{1}^{'} \equiv 4$ and $W_{2}^{'} \equiv W_{5}$ and $Z' \equiv a W_{4}$ we get $Z' ⩦ a W_{1}^{'} ⩦ b c W_{2}^{'},$ 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 $a W_{1} ⩦ b c W_{2} .$ From successive applications of the reduction lemma we have the existence of $W_{3},$ $W_{4},$ $W_{5},$ $W_{6}$ with $\begin{matrix} a W_{1} & ⩦ & b c W_{2} \\ c W_{2} & ⩦ & a b a W_{3} \\ b a W_{3} & ⩦ & c W_{4} \\ a W_{3} & ⩦ & c b c W_{5} \\ b c W_{5} & ⩦ & a W_{6} . \end{matrix}$ On account of the last relation $L (W_{6}) < L (W_{1})$ contradicting the minimality of $L (W_{1}) .$

(ii) From a relation $a W_{1} ⩦ b c b W_{2}$ between positive words of minimal length and successive applications of the reduction lemma we have the existence of $W_{3},$ $W_{4}$ with $\begin{matrix} b W_{2} & ⩦ & a c a W_{3} \\ a W_{3} & ⩦ & b a b W_{4} . \end{matrix}$ The last relation combined with $L (W_{3}) < L (W_{1})$ gives a contradiction.

Case 3: We distinguish three cases:

(i)	$c$ is the “middle” point of $Γ$ (thus $m_{a c} = 3,$ $m_{b c} = p),$
(ii)	$c$ is the “left” point of $Γ$ (thus $m_{a c} = 2,$ $m_{b c} = 3),$
(iii)	$c$ is the “right” point of $Γ$ (thus $m_{a c} = 2,$ $m_{b c} = p).$

(i) Assume that there is a relation $a W_{1} ⩦ b c b c W_{2}$ 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 $W_{3}$ and $W_{4}$ with $\begin{matrix} b c W_{2} & ⩦ & a c W_{3} \\ W_{3} & ⩦ & {⟨ b c ⟩}^{m_{b c} - 1} W_{4} . \end{matrix}$ Substituting the second equation into the first, applying the defining relation and the reduction lemma gives $\begin{matrix} c W_{2} & ⩦ & a {⟨ c b ⟩}^{m_{b c} - 1} W_{4} . \end{matrix}$ Again, a two fold application of the reduction lemma gives the existence of a word $W_{5}$ with $\begin{matrix} a W_{5} & ⩦ & {⟨ b c ⟩}^{m_{b c} - 2} W_{4} . \end{matrix}$ This relation combined with $L (W_{5}) < L (W_{1})$ contradicts the minimality of $L (W_{1}) .$

(ii) Assume that there is a relation $\begin{matrix} a W_{1} & ⩦ & b c W_{2} \end{matrix}$ between words of length less than $l .$ It follows from the reduction lemma that there exists a word $W_{3}$ with $\begin{matrix} c W_{2} & ⩦ & {⟨ a b ⟩}^{m_{a b} - 1} W_{3} . \end{matrix}$ 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 $\begin{matrix} a W_{1} & ⩦ & b c b c b W_{2} \end{matrix}$ between words of length $< ℓ .$ It follows from the reduction lemma that there exists a word $W_{3}$ with $\begin{matrix} a W_{3} & ⩦ & c b c b W_{2} \end{matrix}$ 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 $M_{a, 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 $A \equiv a_{i_{1}} \dots a_{i_{k}}$ define the positive word rev $A$ by $rev A \equiv a_{i_{k}} \dots a_{i_{1}} .$ Clearly $A ⩦ B$ implies $rev A ⩦ rev B$ since the passage from $A$ to $rev A$ 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 $A X B ⩦ A Y B$ then $X ⩦ Y .$

The Artin monoid $G_{M}^{+}$ 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