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

The Division Algorithm

Let $U,V$ and $W$ be positive words. Say $U$ divides $W$ (on the left) if $$\begin{array}{ccc}W& \equiv & UV\text{(if working in}\hspace{0.17em}{F}^{+}\text{),}\\ W& ⩦& UV\text{(if working in}\hspace{0.17em}{G}_M^{+}\text{),}\end{array}$$ and write $U|W$ (interpreted in the context of $F^{+}$ or $G_M^{+}\text{).}$

We present an algorithm which is used later in the theory of divisibility in $G_M^{+}\text{.}$ 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 $a\in I$ 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 ${⟨ba⟩}^q$ with $q<m_{ab}$ and $m_{ab}\ne 2$ are also not divisible by $a\text{.}$ Of course many other quite simple words have this property, for example concatenations of the previous types of words in specific order, called $a\text{-chains,}$ which we will define shortly. At the same time we will define what we mean by the source and target of an $a\text{-chain.}$

Definition.

(i)	A primitive $a\text{-chain}$ is a positive word $W$ such that $m_{ab}=2$ for all letters $b$ in $W$ (so $b\not\equiv a$ and $ab=ba\text{).}$

We call $a$ the source and target of $W\text{.}$ (Note vacuously the empty word is a primitive $a\text{-chain.)}$

(ii)	An elementary $a\text{-chain}$ is a positive word of the form ${⟨ba⟩}^q$ with $m_{ab}>2$ and $0<q<m_{ab}\text{.}$ The source is $a,$ and the target is $b$ if $q$ is even, and $a$ if $q$ is odd.
(iii)	An $a\text{-chain}$ is a product $C\equiv C_1\cdots C_k$ where for each $i=1,\dots ,k,$ $C_i$ is a primitive or elementary $a_i\text{-chain}$ for some $a_i\in I,$ such that $a_1=a$ and the target of $C_i$ is the source of $C_{i+1}\text{.}$

[Ed: This may be expressed as: $$\begin{array}{c}a\equiv a_1\stackrel{C_1}{⟶}{a}_2\stackrel{C_2}{⟶}{a}_3⟶\cdots \stackrel{C_{n-1}}{⟶}{a}_k\stackrel{C_k}{⟶}{a}_{k+1}\equiv b\\ \text{]}\end{array}$$

The source of $C$ is $a$ and the target of $C$ is the target of $C_k\text{.}$ If this target is $b$ we say: $C$ is a chain from $a$ to $b\text{.}$

[Example. $I=\{a,b,c,d\},$ $m_{ab}=m_{bc}=2,$ $m_{cd}=4,$ $m_{ac}=m_{ad}=m_{bd}=2\text{.}$
$c,$ $cd,$ $dcd,$ $c^{2}dc{d}^7$ are primitive $a\text{-chains.}$
$b,$ $ba$ are elementary $a\text{-chains.}$
$a,$ $ab,$ $c,$ $cb$ are elementary $b\text{-chains.}$
$dcd,$ $dc,$ $d$ are elementary $c\text{-chains.}$
$\underset{\underset{C_1}{⏟}}{aba}\underset{\underset{C_2}{⏟}}{cd}\underset{\underset{C_3}{⏟}}{bc}\underset{\underset{C_4}{⏟}}{ab}\underset{\underset{C_5}{⏟}}{d{c}^2{d}^2}\underset{\underset{C_6}{⏟}}{ba}$ is a $d\text{-chain.}$ $$\begin{array}{ccccccccccccc}d& \underset{\text{prim}}{\overset{C_1}{⟶}}& d& \underset{\text{el.}}{\overset{C_2}{⟶}}& c& \underset{\text{el.}}{\overset{C_3}{⟶}}& b& \underset{\text{el.}}{\overset{C_4}{⟶}}& a& \underset{\text{prim}}{\overset{C_5}{⟶}}& a& \underset{\text{el.}}{\overset{C_6}{⟶}}& b\text{.}\text{]}\end{array}$$

(iv)	There is a unique decomposition of a given $a\text{-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 $\text{rev}\hspace{0.17em}C$ is a chain from $b$ to $a\text{.}$

Let $C\equiv C_1\cdots C_k$ be a chain from $a$ to $b$ (where $C_i$ is a primitive or elementary chain from $a_i$ to $a_{i+1}$ for $i=1,\dots ,k\text{)}$ and $D$ a positive word such that $a$ divides $CD\text{.}$ Then $b$ divides $D,$ and in particular $a$ does not divide $C\text{.}$

		Proof.
	The last claim follows from the first by putting $D$ equal to the empty word. We prove the first claim by induction on $k\text{.}$ Suppose $k=1\text{.}$ (a) Suppose $C\equiv x_1\cdots x_m$ is primitive, so $m_{a{x}_i}=2$ for all $i\text{.}$ Then $x_1\cdots x_{m}D⩦aV$ for some positive word $V\text{.}$ [Recall the Reduction Lemma (2.1): If $X,Y$ are positive words and $a,b\in I$ such that $aX⩦bY$ then there exists a positive word $W$ such that $$\begin{array}{ccc}X& ⩦& {⟨ba⟩}^{m_{ab}-1}W\text{and}\\ Y& ⩦& {⟨ab⟩}^{m_{ab}-1}W\text{.]}\end{array}$$ By (2.1), $x_2\cdots x_{m}D⩦{⟨a{x}_1⟩}^{m_{a{x}_1}-1}W\equiv aW$ for some positive word $W\text{.}$ Continuing in this fashion yields that $a$ divides $D$ and we are done (since $a$ is the target of $C\text{).}$ (b) Suppose $C\equiv {⟨ba⟩}^q$ is elementary, where $m_{ab}>2$ and $0<q<m_{ab}\text{.}$ Then $$D\equiv {⟨ba⟩}^{q}D⩦aV$$ for some positive word $V\text{.}$ By (2.1), ${⟨ab⟩}^{q-1}D⩦{⟨ab⟩}^{m_{ab}-1}W$ for some positive word $W\text{.}$ So by cancellation (special case of (2.1)), $$D⩦\{\begin{array}{cc}{⟨ab⟩}^{m_{ab}-q}W& \text{if}\hspace{0.17em}q\hspace{0.17em}\text{is odd, or}\\ {⟨ba⟩}^{m_{ab}-q}W& \text{if}\hspace{0.17em}q\hspace{0.17em}\text{is even.}\end{array}$$ 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\text{.}$ By the inductive hypothesis $a_k$ divides $C_{k}D,$ and by (a) and (b), $b\equiv a_{k+1}$ divides $D$ and we are done. $\square$

3.2. For all positive words $W$ and letters $a\in I$ we will define a recursively calculable positive word $T_a\left(W\right)$ such that $W⩦T_a\left(W\right)$ and either $T_a\left(W\right)$ begins with $a$ or $T_a\left(W\right)$ is an $a\text{-chain.}$ To simplify the description we need other operations on positive words:

(i) Every positive $W$ has a unique factorization $$W\equiv C_a\left(W\right)D_a\left(W\right)$$ where $C_a\left(W\right)\equiv C_0$ or $C_a\left(W\right)\equiv C_0{C}_1$ where $C_0$ is a primitive $a\text{-chain}$ and $C_1$ and elementary $a\text{-chain}$ such that the word length of $C_a\left(W\right)$ is as large as possible.

(ii) If $C$ is a primitive $a\text{-chain}$ put $$C^{+}\equiv aC$$ which is positive equivalent to $Ca$ by commutativity.

If $C\equiv C_0{⟨ba⟩}^q$ where $C_0$ is primitive, put $$C^{+}\equiv \{\begin{array}{cc}aC& \text{if}\hspace{0.17em}q=m_{ab}-1\text{, or}\\ C_0{⟨ba⟩}^{q+1}& \text{otherwise.}\end{array}$$ In each case $C^{+}⩦Cc$ where $c$ is the target of $C\text{.}$

[Ed: Note that, if $q=m_{ab}-1,$ $$C^{+}\equiv aC⩦C_{0}a{⟨ba⟩}^q\equiv C_0{⟨ab⟩}^{m_{ab}}⩦C_0{⟨ba⟩}^{m_{ab}}\equiv Cc,$$ where $c$ is the target of $C\text{.}$

N.B.: The point of this definition is to construct a word $C^{+}$ which is positive equivalent to $Cc$ $\text{(}C\equiv C_0{C}_1$ a chain from $a$ to $c\text{)}$ and such that either $C^{+}$ starts with $a,$ or $C^{+}\equiv C_0{C}_1^{+}$ where $C_1^{+}$ is also elementary, but longer than $C_1\text{.]}$

(iii) If $D$ is any nonempty positive word denote by $D^{-}$ the word obtained by deleting the first letter of $D\text{.}$ [Ed: Thus $CD⩦C^{+}{D}^{-}\text{.]}$

Definition. For $W$ empty or beginning with $a$ put $$T_a\left(W\right)\equiv W\text{.}$$ For all other words define $T_a\left(W\right)$ recursively: let $L\left(W\right)=\ell$ and suppose the $a\text{-chain}$ $C_a\left(W\right)$ has target $c\text{.}$ Then put $$S_a\left(W\right)\equiv \{\begin{array}{cc}{C}_a\left(W\right)T_c\left(D_a\left(W\right)\right)& \text{if}\hspace{0.17em}c\hspace{0.17em}\text{is not the first letter of}\hspace{0.17em}{T}_c\left(D_a\left(W\right)\right)\\ C_a{\left(W\right)}^{+}{T}_c{\left(D_a\left(W\right)\right)}^{-}& \text{otherwise,}\end{array}$$ and $T_a\left(W\right)\equiv S_a^{\ell }\left(W\right)$ (the result of applying $S_a$ $\ell$ times).

[Observations. Let $W$ be positive and $a\in I\text{.}$ Then

(A)	$T_a\left(W\right)\equiv S_a\left(W\right)\equiv W$ if $W$ is an $a\text{-chain}$ or begins with $a,$
(B)	$T_a\left(W\right)⩦S_a\left(W\right)⩦W\text{.}$

		Proof.
	(A) The result if clear if $W$ begins with $a$ or is empty. Suppose $W$ is a nonempty $a\text{-chain,}$ so $W\equiv C_a\left(W\right)D_a\left(W\right)$ where $C_a\left(W\right)$ is a nonempty chain from $a$ to $c,$ say and $D_a\left(W\right)$ is a $c\text{-chain.}$ By an inductive hypothesis, since $L\left(D_a\left(W\right)\right)<L\left(W\right),$ $T_c\left(D_a\left(W\right)\right)\equiv S_c\left(D_a\left(W\right)\right)\equiv D_a\left(W\right)$ so that $S_a\left(W\right)\equiv C_a\left(W\right)D_a\left(W\right)\equiv W$ noting that $c$ cannot be the first letter of $D_a\left(W\right),$ whence $T_a\left(W\right)\equiv S_a^{\ell }\left(W\right)\equiv W,$ and (i) is proved. (B) Again the result is clear if $W$ begins with $a$ or is empty. Otherwise, we may suppose that $C_a\left(W\right)$ is nonempty. Thus $L\left(D_a\left(W\right)\right)<L\left(W\right),$ and by an inductive hypothesis $T_c\left(D_a\left(w\right)\right)⩦D_a\left(W\right)\text{.}$ Since $C^{+}{D}^{-}⩦CD$ it is clear (either way) that $$S_a\left(W\right)⩦C_a\left(W\right)T_c\left(D_a\left(W\right)\right)⩦C_a\left(W\right)D_a\left(W\right)\equiv W\text{.}$$ Now since $L\left(S_a\left(W\right)\right)=L\left(W\right)$ we may repeat this step $\ell$ times to show that $T_a\left(W\right)⩦S_a\left(W\right)⩦W\text{.}$ $\square \text{]}$

Let $W$ be positive and $a\in I\text{.}$ Then

(i)	$T_a\left(W\right)$ is an $a\text{-chain}$ or begins with $a,$
(ii)	$T_a\left(W\right)\equiv W$ if and only if $W$ is an $a\text{-chain}$ or begins with $a,$
(iii)	$T_a\left(W\right)⩦W\text{.}$

		Proof.
	The proof for all three parts follows by induction on the wordlength, where the induction basis is trivial. [ Ed: Namely when $L\left(W\right)=0,$ $T_a\left(W\right)\equiv W\text{.}$ More concretely, if $L\left(W\right)=1,$ then $W$ is $a$ or an $a\text{-chain,}$ and the algorithm again leaves $W$ unchanged. ] (i) [We may suppose that $L\left(W\right)>0$]. From the definition of $S_a\left(W\right)$ and the induction hypothesis the following is true. If $S_a\left(W\right)$ is neither an $a\text{-chain}$ nor a word beginning with $a,$ then $C_a\left(S_a\left(W\right)\right)$ has length strictly greater than $C_a\left(W\right)\text{.}$ Hence the result $S_a^k\left(W\right)$ of $k$ successive applications of $S_a$ must eventually, for $k=\ell$ at least, be either an $a\text{-chain}$ or word beginning with $a\text{.}$ [Note: If $W$ is an $a\text{-chain}$ or begins with $a$ then the first statement is clear since, by Observation (A), $S_a\left(W\right)\equiv W\text{.}$ Otherwise, $C_a\left(W\right)$ is non-empty. Then, by the induction hypothesis, if $c$ is not its first letter $T_c\left(D_a\left(W\right)\right)$ is a $c\text{-chain}$ and composes with $C_a\left(W\right)$ to make $S_a\left(W\right)$ an $a\text{-chain.}$ Otherwise $S_a\left(W\right)=C_a{\left(W\right)}^{+}{T}_c{\left(D_a\left(W\right)\right)}^{-}$ and, by the N.B. above, $C_a{\left(W\right)}^{+}$ either starts with $a$ or is of such a form that is must divide $C_a\left(S_a\left(W\right)\right)\text{.}$ This last implies that $$L\left(C_a\left(S_a\left(W\right)\right)\right)\ge L\left(C_a{\left(W\right)}^{+}\right)=L\left(C_a\left(W\right)\right)+1\text{.}$$ Note that, by Observation (A), each further application of $S_a$ either leaves the word unchanged (when it is already either an $a\text{-chain}$ or a word beginning with $a\text{)}$ or strictly increases the prefix $C_a\text{.}$ Thus, after $k$ successive applications, either $S_a^k\left(W\right)$ is an $a\text{-chain}$ or starts with $a,$ or $L\left(C_a\left(S_a^k\left(W\right)\right)\right)\ge L\left(C_a\left(W\right)\right)+k>k\text{.}$ This last case gives an obvious contradiction once $k=L\left(W\right)=\ell ,$ since $S_a$ preserves the total word length, so that $L\left(C_a\left(S_a^k\left(W\right)\right)\right)\le L\left(W\right)\text{.}$ Hence $T_a\left(W\right)$ must either be an $a\text{-chain}$ or start with $a\text{.}$ (One may like to observe that, once $k>L\left(D_a\left(W\right)\right),$ 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 $S_a\left(W\right)$ and the induction hypothesis it follows that, for an $a\text{-chain}$ or word $W$ beginning with $a,$ $S_a\left(W\right)\equiv W$ and thence that $T_a\left(W\right)\equiv W\text{.}$ The converse follows by (i). (iii) The proof by induction is trivial, given that $C^{+}⩦Cc\text{.}$ $\square$

3.3. With the help of the projection operators $T_a$ 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 $$R_a\left(V\right)\equiv V\text{.}$$ If $V$ is a chain from $a$ to $b$ then put $$R_a\left(V\right)\equiv T_a\left(Vb\right)\text{.}$$

Definition. Let $W$ be a positive word and $a\in I\text{.}$ Then the $a\text{-sequence}$ of $W$ is the sequence at positive words $W_i,$ for $i=1,2,\cdots$ where $$\begin{array}{ccc}{W}_1& \equiv & T_a\left(W\right)\text{and}\\ W_{i+1}& \equiv & R_a\left(W_i\right)\end{array}$$ for all $i>1\text{.}$

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

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 $W_i$ divides $V$ for all $i>0,$ and $W_j\equiv W_{j+1}$ for $j>L\left(V\right)-L\left(W\right)$ (the sequence terminates).
(ii)	Conversely, if $W_j\equiv W_{j+1}$ for some $j,$ then $W_j$ is a common multiple of $a$ and $W$ (and, by (i), a least common multiple).

		Proof.
	(ii) Suppose $W_j\equiv W_{j+1}\text{.}$ By definition $W_j$ begins with $a\text{.}$ Certainly $W⩦T_a\left(W\right)\equiv W_1$ (by Lemma 3.2). Suppose $W$ divides $W_i\text{.}$ Now $$W_{i+1}\equiv \{\begin{array}{cc}{W}_i& \text{if}\hspace{0.17em}{W}_i\hspace{0.17em}\text{begins with}\hspace{0.17em}a\\ T_a\left(W_{i}b\right)& \text{if}\hspace{0.17em}{W}_i\hspace{0.17em}\text{is a chain from}\hspace{0.17em}a\hspace{0.17em}\text{to}\hspace{0.17em}b\end{array}$$ But $T_a\left(W_{i}b\right)⩦W_{i}b$ which is divisible by $W_i$ and hence by $W\text{.}$ By induction $W$ divides $W_j,$ so $W_j$ is a common multiple of $a$ and $W\text{.}$ (i) Suppose now that $V$ is a common multiple of $a$ and $W\text{.}$ Since $W⩦T_a\left(W\right),$ $W_1$ divides $V\text{.}$ Suppose $W_i$ divides $V\text{.}$ Either $W_i$ begins with $a,$ in which case $W_{i+1}\equiv W_i$ and certainly $W_{i+1}$ divides $V,$ or $W_i$ is an $a\text{-chain}$ and $W_{i+1}\equiv R_a\left(W_j\right)\equiv T_a\left(W_{i}b\right)$ where $b$ is the target of $W_i\text{.}$ But $V⩦aY⩦W_{i}Z$ for some positive words $T$ and $Z,$ so by (3.1) $$V⩦W_{i}bZ\prime ⩦T_a\left(W_{i}b\right)Z\equiv W_{i+1}Z\prime$$ for some positive word $Z\text{.}$ By induction this shows $W_i$ divides $V$ for all $i\text{.}$ If $W_i\not\equiv W_{i+1}$ then $L\left(W_{i+1}\right)=L\left(W\right)+i\text{.}$ Since $L\left(W_{i+1}\right)\le L\left(V\right),$ we must then have $i\le L\left(V\right)-L\left(W\right)\text{.}$ Thus $W_j\equiv W_{j+1}$ for all $j>L\left(V\right)-L\left(W\right)\text{.}$ $\square \text{]}$

Let $W$ be a positive word, $a$ a letter, and $W_i,$ $i=1,2,\dots ,$ the $a\text{-sequence}$ of $W\text{.}$ Then there exists a common multiple $V$ of $a$ and $W$ precisely when $W_j\equiv W_{j+1}$ for $j>L\left(V\right)-L\left(W\right)\text{.}$

		Proof.
	When $W_j\equiv W_{j+1},$ it follows by the definition of the $a\text{-sequence}$ that $a$ divides $W_j\text{.}$ Because each $W_i$ clearly divides $W_{i+1}$ [Ed: and because $W_1⩦W$], then every $W_j$ is a common multiple of $a$ and $W\text{.}$ Conversely, if $V$ is a common multiple, then it follows by the definition of $W_i$ together with (3.1) and (3.2) that $V$ is divisible by every $W_i\text{.}$ From $W_j\not\equiv W_{j+1}$ it follows that $L\left(W_{j+1}\right)=L\left(W\right)+j\text{.}$ From $W_{j+1}|V$ it then follows that $L\left(W\right)+j\le L\left(V\right)\text{.}$ Thus $j>L\left(V\right)-L\left(W\right)$ implies that $W_j\equiv W_{j+1}\text{.}$ $\square$

3.4. When a positive word $W$ is of the form $W\equiv UaaV$ 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 $G_M^{+}$ 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\text{.}$

		Proof.
	First we prove the following lemma. $\square$

Lemma. Let $V$ be a positive word which is divisible by $a$ and contains a square. Then there is a positive word $\stackrel{\sim }{V}$ with $\stackrel{\sim }{V}⩦V$ which contains a square and which begins with $a\text{.}$

The proof of the Lemma is by induction on the length of $V\text{.}$ Decompose $V,$ as in 3.2, in the form $$V\equiv C_a\left(V\right)D_a\left(V\right)\text{.}$$ 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\left(C_a\left(V\right)\right)$ is maximal.

When $C_a\left(V\right)$ is the empty word it follows naturally that $\stackrel{\sim }{V}=V$ satisfies the conditions for $\stackrel{\sim }{V}\text{.}$ For nonempty $C_a\left(V\right)$ we have three cases

(i)	$C_a\left(V\right)$ contains a square. Then $\stackrel{\sim }{V}\equiv T_a\left(V\right)$ satisfies the conditions for $\stackrel{\sim }{V}\text{.}$
(ii)	$D_a\left(V\right)$ contains a square. By the induction assumption, one can assume, without loss of generality that $D_a\left(V\right)$ begins with the target of the $a\text{-chain}$ $C_a\left(V\right)\text{.}$ Thus, since the length of $C_a\left(V\right)$ is maximal, $C_a\left(V\right)$ is of the form $C_0{⟨ba⟩}^{m_{ab}-1},$ where $C_0$ is a primitive $a\text{-chain.}$ From this if follows that when ${D_a\left(V\right)}^{-}$ contains a square then $\stackrel{\sim }{V}\equiv a{C}_a\left(V\right)D_a{\left(V\right)}^{-}$ satisfies the conditions for $\stackrel{\sim }{V},$ and otherwise $\stackrel{\sim }{V}\equiv a^2{C}_a\left(V\right)D_a{\left(V\right)}^{--}$ does.
(iii)	Neither $C_a\left(V\right)$ or $D_a\left(V\right)$ contain a square. Then $V$ is of the form $V\equiv C_0{⟨ba⟩}^q{D}_a\left(V\right)$ where $q\ge 1,$ and $D_a\left(V\right)$ 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 $$D_a\left(V\right)⩦{⟨ba⟩}^{m_{ab}}E\text{.}$$ Then $$\begin{array}{ccc}\stackrel{\sim }{V}& \equiv & a{C}_0{⟨ba⟩}^{m_{ab}-1}{⟨ba⟩}^{q}E\text{if}\hspace{0.17em}{m}_{ab}\hspace{0.17em}\text{is even}\\ \stackrel{\sim }{V}& \equiv & a{C}_0{⟨ba⟩}^{m_{ab}-1}{⟨ab⟩}^{q}E\text{if}\hspace{0.17em}{m}_{ab}\hspace{0.17em}\text{is odd,}\end{array}$$ 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 $aW⩦aU\text{.}$ It follows from the reduction lemma that $U⩦W$ and, since $W$ is square free that $U$ does not contain a square. So $U$ begins with $a$ and $W$ is divisible by $a\text{.}$ $\square$

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\text{-sequences}$ $W_i$ of $W$ are also square free.

		Proof.
	$W_1$ is square free since $W_1⩦W\text{.}$ Assume $W_i$ is square free. Then either $W_{i+1}\equiv W_i$ or $W_{i+1}⩦W_i{b}_i$ where $b_i$ is the target of the chain $W_i\text{.}$ If $W_i{b}_i$ is not square free then $b_i\hspace{0.17em}\text{rev}\hspace{0.17em}{W}_i$ is not square free and by 3.4, the $b_i$ chain $W_i$ is not divisible by $b_i,$ in contradiction to 3.1. $\square$

3.6. Using the operators $T_a$ 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 $$V⩦W·(V:W)\text{.}$$

Definition. For $W\equiv a_1\cdots a_k,$ $V:W$ is the word $$V:W\equiv T_{a_k}{\left(T_{a_{k-1}}{\left(\cdots {\left(T_{a_2}{\left(T_{a_1}\left(V\right)\right)}^{-}\right)}^{-}\cdots \right)}^{-}\right)}^{-}\text{.}$$

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