Artin groups and Coxeter groups

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

Last update: 26 January 2014

The Division Algorithm

Let U,V and W be positive words. Say U divides W (on the left) if W UV(if working in F+), W UV(if working inGM+), and write U|W (interpreted in the context of F+ or GM+).

We present an algorithm which is used later in the theory of divisibility in GM+. For example the algorithm can be used to decide whether a given letter divides a positive word, and to determine the smallest common multiple of a letter and a word if it exists.

3.1. Let aI be a letter. The simplest positive words which are not multiples of a are clearly those in which a does not appear. Further, the words of the form baq with q<mab and mab2 are also not divisible by a. Of course many other quite simple words have this property, for example concatenations of the previous types of words in specific order, called a-chains, which we will define shortly. At the same time we will define what we mean by the source and target of an a-chain.


(i) A primitive a-chain is a positive word W such that mab=2 for all letters b in W (so ba and ab=ba).
We call a the source and target of W. (Note vacuously the empty word is a primitive a-chain.)
(ii) An elementary a-chain is a positive word of the form baq with mab>2 and 0<q<mab. The source is a, and the target is b if q is even, and a if q is odd.
(iii) An a-chain is a product CC1Ck where for each i=1,,k, Ci is a primitive or elementary ai-chain for some aiI, such that a1=a and the target of Ci is the source of Ci+1.

[Ed: This may be expressed as: aa1C1 a2C2a3 Cn-1 akCk ak+1b ]

The source of C is a and the target of C is the target of Ck. If this target is b we say: C is a chain from a to b.

[Example. I={a,b,c,d}, mab=mbc=2, mcd=4, mac=mad=mbd=2.
c, cd, dcd, c2dcd7 are primitive a-chains.
b, ba are elementary a-chains.
a, ab, c, cb are elementary b-chains.
dcd, dc, d are elementary c-chains.
abaC1 cdC2 bcC3 abC4 dc2d2C5 baC6 is a d-chain. d primC1 d el.C2 c el.C3 b el.C4 a primC5 a el.C6 b.]

(iv) There is a unique decomposition of a given a-chain into primitive and elementary factors if one demands that the primitive factors are as large as possible. The number of elementary factors is the length of the chain.

Remark. If C is a chain from a to b then revC is a chain from b to a.

Let CC1Ck be a chain from a to b (where Ci is a primitive or elementary chain from ai to ai+1 for i=1,,k) and D a positive word such that a divides CD. Then b divides D, and in particular a does not divide C.


The last claim follows from the first by putting D equal to the empty word. We prove the first claim by induction on k. Suppose k=1.

(a) Suppose Cx1xm is primitive, so maxi=2 for all i. Then x1xmDaV for some positive word V. [Recall the Reduction Lemma (2.1): If X,Y are positive words and a,bI such that aXbY then there exists a positive word W such that X bamab-1 Wand Y abmab-1 W.] By (2.1), x2xmDax1max1-1WaW for some positive word W. Continuing in this fashion yields that a divides D and we are done (since a is the target of C).

(b) Suppose Cbaq is elementary, where mab>2 and 0<q<mab. Then Dbaq DaV for some positive word V. By (2.1), abq-1Dabmab-1W for some positive word W. So by cancellation (special case of (2.1)), D { abmab-q W ifqis odd, or bamab-q W ifqis even. So D is divisible by a if q is odd, and b if q is even, which is in each case the target of C and we are done.

This begins the induction. Suppose now k>1. By the inductive hypothesis ak divides CkD, and by (a) and (b), bak+1 divides D and we are done.

3.2. For all positive words W and letters aI we will define a recursively calculable positive word Ta(W) such that WTa(W) and either Ta(W) begins with a or Ta(W) is an a-chain. To simplify the description we need other operations on positive words:

(i) Every positive W has a unique factorization WCa(W) Da(W) where Ca(W)C0 or Ca(W)C0C1 where C0 is a primitive a-chain and C1 and elementary a-chain such that the word length of Ca(W) is as large as possible.

(ii) If C is a primitive a-chain put C+aC which is positive equivalent to Ca by commutativity.

If CC0baq where C0 is primitive, put C+ { aC ifq=mab -1, or C0baq+1 otherwise. In each case C+Cc where c is the target of C.

[Ed: Note that, if q=mab-1, C+aC C0abaq C0abmab C0bamab Cc, where c is the target of C.

N.B.: The point of this definition is to construct a word C+ which is positive equivalent to Cc (CC0C1 a chain from a to c) and such that either C+ starts with a, or C+C0C1+ where C1+ is also elementary, but longer than C1.]

(iii) If D is any nonempty positive word denote by D- the word obtained by deleting the first letter of D. [Ed: Thus CDC+D-.]

Definition. For W empty or beginning with a put Ta(W)W. For all other words define Ta(W) recursively: let L(W)= and suppose the a-chain Ca(W) has target c. Then put Sa(W) { Ca(W)Tc (Da(W)) ifcis not the first letter of Tc(Da(W)) Ca(W)+ Tc(Da(W))- otherwise, and Ta(W)Sa(W) (the result of applying Sa times).

[Observations. Let W be positive and aI. Then

(A) Ta(W)Sa(W)W if W is an a-chain or begins with a,
(B) Ta(W)Sa(W)W.


(A) The result if clear if W begins with a or is empty. Suppose W is a nonempty a-chain, so WCa(W)Da(W) where Ca(W) is a nonempty chain from a to c, say and Da(W) is a c-chain. By an inductive hypothesis, since L(Da(W))<L(W), Tc(Da(W))Sc(Da(W))Da(W) so that Sa(W)Ca(W)Da(W)W noting that c cannot be the first letter of Da(W), whence Ta(W)Sa(W)W, and (i) is proved.

(B) Again the result is clear if W begins with a or is empty. Otherwise, we may suppose that Ca(W) is nonempty. Thus L(Da(W))<L(W), and by an inductive hypothesis Tc(Da(w))Da(W). Since C+D-CD it is clear (either way) that Sa(W)Ca (W)Tc(Da(W)) Ca(W)Da (W)W. Now since L(Sa(W))=L(W) we may repeat this step times to show that Ta(W)Sa(W)W.


Let W be positive and aI. Then

(i) Ta(W) is an a-chain or begins with a,
(ii) Ta(W)W if and only if W is an a-chain or begins with a,
(iii) Ta(W)W.


The proof for all three parts follows by induction on the wordlength, where the induction basis is trivial. [ Ed: Namely when L(W)=0, Ta(W)W. More concretely, if L(W)=1, then W is a or an a-chain, and the algorithm again leaves W unchanged. ]

(i) [We may suppose that L(W)>0]. From the definition of Sa(W) and the induction hypothesis the following is true. If Sa(W) is neither an a-chain nor a word beginning with a, then Ca(Sa(W)) has length strictly greater than Ca(W). Hence the result Sak(W) of k successive applications of Sa must eventually, for k= at least, be either an a-chain or word beginning with a.

[Note: If W is an a-chain or begins with a then the first statement is clear since, by Observation (A), Sa(W)W. Otherwise, Ca(W) is non-empty. Then, by the induction hypothesis, if c is not its first letter Tc(Da(W)) is a c-chain and composes with Ca(W) to make Sa(W) an a-chain. Otherwise Sa(W)=Ca(W)+Tc(Da(W))- and, by the N.B. above, Ca(W)+ either starts with a or is of such a form that is must divide Ca(Sa(W)). This last implies that L(Ca(Sa(W))) L(Ca(W)+)= L(Ca(W))+1. Note that, by Observation (A), each further application of Sa either leaves the word unchanged (when it is already either an a-chain or a word beginning with a) or strictly increases the prefix Ca. Thus, after k successive applications, either Sak(W) is an a-chain or starts with a, or L(Ca(Sak(W)))L(Ca(W))+k>k. This last case gives an obvious contradiction once k=L(W)=, since Sa preserves the total word length, so that L(Ca(Sak(W)))L(W). Hence Ta(W) must either be an a-chain or start with a. (One may like to observe that, once k>L(Da(W)), the contradiction is already reached).

Claims (ii) and (iii) are immediate from Observations (A) and (B) respectively. The original text reads as follows. ]

(ii) From the definition of Sa(W) and the induction hypothesis it follows that, for an a-chain or word W beginning with a, Sa(W)W and thence that Ta(W)W. The converse follows by (i).

(iii) The proof by induction is trivial, given that C+Cc.

3.3. With the help of the projection operators Ta defined in 3.2 one gets a simple algorithm for producing a common multiple of a letter a and a word W, if one exists. If a positive word V begins with a, put Ra(V)V. If V is a chain from a to b then put Ra(V)Ta (Vb).

Definition. Let W be a positive word and aI. Then the a-sequence of W is the sequence at positive words Wi, for i=1,2, where W1 Ta(W)and Wi+1 Ra(Wi) for all i>1.

[Ed: Note that the following lemma anticipates the following section (§4) by effectively demonstrating that if a common multiple exists then the a-sequence of W terminates in a word W which is a least common multiple for a and W. That is both a and W divide W, and W divides any other common multiple of a and W.

The original text is translated below, but we give here an expanded version as follows:

(i) If V is a common multiple of a and W then Wi divides V for all i>0, and WjWj+1 for j>L(V)-L(W) (the sequence terminates).
(ii) Conversely, if WjWj+1 for some j, then Wj is a common multiple of a and W (and, by (i), a least common multiple).


(ii) Suppose WjWj+1. By definition Wj begins with a. Certainly WTa(W)W1 (by Lemma 3.2). Suppose W divides Wi. Now Wi+1 { Wi ifWibegins witha Ta(Wib) ifWiis a chain from atob But Ta(Wib)Wib which is divisible by Wi and hence by W. By induction W divides Wj, so Wj is a common multiple of a and W.

(i) Suppose now that V is a common multiple of a and W. Since WTa(W), W1 divides V. Suppose Wi divides V. Either Wi begins with a, in which case Wi+1Wi and certainly Wi+1 divides V, or Wi is an a-chain and Wi+1Ra(Wj)Ta(Wib) where b is the target of Wi. But VaYWiZ for some positive words T and Z, so by (3.1) VWibZ Ta(Wib)Z Wi+1Z for some positive word Z. By induction this shows Wi divides V for all i. If WiWi+1 then L(Wi+1)=L(W)+i. Since L(Wi+1)L(V), we must then have iL(V)-L(W). Thus WjWj+1 for all j>L(V)-L(W).


Let W be a positive word, a a letter, and Wi, i=1,2,, the a-sequence of W. Then there exists a common multiple V of a and W precisely when WjWj+1 for j>L(V)-L(W).


When WjWj+1, it follows by the definition of the a-sequence that a divides Wj. Because each Wi clearly divides Wi+1 [Ed: and because W1W], then every Wj is a common multiple of a and W. Conversely, if V is a common multiple, then it follows by the definition of Wi together with (3.1) and (3.2) that V is divisible by every Wi. From WjWj+1 it follows that L(Wj+1)=L(W)+j. From Wj+1|V it then follows that L(W)+jL(V). Thus j>L(V)-L(W) implies that WjWj+1.

3.4. When a positive word W is of the form WUaaV where U and V are positive words and a is a letter then we say W has a quadratic factor. A word is square-free relative to a Coxeter matrix M when W is not positive equivalent to a word with a quadratic factor. The image of a square free word in GM+ is called square-free.

Let W be a square-free positive word and a a letter such that aW is not square free. Then a divides W.


First we prove the following lemma.

Lemma. Let V be a positive word which is divisible by a and contains a square. Then there is a positive word V with VV which contains a square and which begins with a.

The proof of the Lemma is by induction on the length of V. Decompose V, as in 3.2, in the form VCa(V)Da (V). Without loss of generality we may assume that V is a representative of its positive equivalence class which contains a square and is such that L(Ca(V)) is maximal.

When Ca(V) is the empty word it follows naturally that V=V satisfies the conditions for V. For nonempty Ca(V) we have three cases

(i) Ca(V) contains a square. Then VTa(V) satisfies the conditions for V.
(ii) Da(V) contains a square. By the induction assumption, one can assume, without loss of generality that Da(V) begins with the target of the a-chain Ca(V). Thus, since the length of Ca(V) is maximal, Ca(V) is of the form C0bamab-1, where C0 is a primitive a-chain. From this if follows that when Da(V)- contains a square then VaCa(V)Da(V)- satisfies the conditions for V, and otherwise Va2Ca(V)Da(V)-- does.
(iii) Neither Ca(V) or Da(V) contain a square. Then V is of the form VC0baqDa(V) where q1, and Da(V) begins with a if q is even, and b if q is odd. Then from the fact that a divides V the reduction lemma is applicable and the relations imply that there exists E such that Da(V) bamab E. Then V aC0 bamab-1 baqE ifmabis even V aC0 bamab-1 abqE ifmabis odd, satisfy the conditions.

This finishes the proof of the lemma.

Proof of 3.4.

By the Lemma there exists a positive word U, such that U contains a square and aWaU. It follows from the reduction lemma that UW and, since W is square free that U does not contain a square. So U begins with a and W is divisible by a.

3.5. By applying 3.4 we get the following lemma which will be needed later.

If W is a square free positive word and a is a letter then the a-sequences Wi of W are also square free.


W1 is square free since W1W. Assume Wi is square free. Then either Wi+1Wi or Wi+1Wibi where bi is the target of the chain Wi. If Wibi is not square free then birevWi is not square free and by 3.4, the bi chain Wi is not divisible by bi, in contradiction to 3.1.

3.6. Using the operators Ta we can give a division algorithm, which, when given positive words V and W such that W divides V, constructs a positive word V:W such that VW·(V:W).

Definition. For Wa1ak, V:W is the word V:WTak ( Tak-1 ( ( Ta2 ( Ta1 (V) ) - ) - ) - ) - .

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