Last update: 26 January 2014
Let $U,V$ and $W$ be positive words. Say $U$ divides $W$ (on the left) if $$\begin{array}{ccc}W& \equiv & UV\phantom{\rule{1em}{0ex}}\text{(if working in}\hspace{0.17em}{F}^{+}\text{),}\\ W& \u2a66& UV\phantom{\rule{1em}{0ex}}\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 ${\u27e8ba\u27e9}^{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{).}$ |
(ii) | An elementary $a\text{-chain}$ is a positive word of the form ${\u27e8ba\u27e9}^{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}}{\u27f6}{a}_{2}\stackrel{{C}_{2}}{\u27f6}{a}_{3}\u27f6\cdots \stackrel{{C}_{n-1}}{\u27f6}{a}_{k}\stackrel{{C}_{k}}{\u27f6}{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{.}$
$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}}{\u23df}}{aba}\underset{\underset{{C}_{2}}{\u23df}}{cd}\underset{\underset{{C}_{3}}{\u23df}}{bc}\underset{\underset{{C}_{4}}{\u23df}}{ab}\underset{\underset{{C}_{5}}{\u23df}}{d{c}^{2}{d}^{2}}\underset{\underset{{C}_{6}}{\u23df}}{ba}$
is a $d\text{-chain.}$
$$\begin{array}{ccccccccccccc}d& \underset{\text{prim}}{\overset{{C}_{1}}{\u27f6}}& d& \underset{\text{el.}}{\overset{{C}_{2}}{\u27f6}}& c& \underset{\text{el.}}{\overset{{C}_{3}}{\u27f6}}& b& \underset{\text{el.}}{\overset{{C}_{4}}{\u27f6}}& a& \underset{\text{prim}}{\overset{{C}_{5}}{\u27f6}}& a& \underset{\text{el.}}{\overset{{C}_{6}}{\u27f6}}& b\text{.}\phantom{\rule{4em}{0ex}}\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\u2a66aV$ 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\u2a66bY$ then there exists a positive word $W$ such that $$\begin{array}{ccc}X& \u2a66& {\u27e8ba\u27e9}^{{m}_{ab}-1}W\phantom{\rule{1em}{0ex}}\text{and}\\ Y& \u2a66& {\u27e8ab\u27e9}^{{m}_{ab}-1}W\text{.]}\end{array}$$ By (2.1), ${x}_{2}\cdots {x}_{m}D\u2a66{\u27e8a{x}_{1}\u27e9}^{{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 {\u27e8ba\u27e9}^{q}$ is elementary, where ${m}_{ab}>2$ and $0<q<{m}_{ab}\text{.}$ Then $$D\equiv {\u27e8ba\u27e9}^{q}D\u2a66aV$$ for some positive word $V\text{.}$ By (2.1), ${\u27e8ab\u27e9}^{q-1}D\u2a66{\u27e8ab\u27e9}^{{m}_{ab}-1}W$ for some positive word $W\text{.}$ So by cancellation (special case of (2.1)), $$D\u2a66\{\begin{array}{cc}{\u27e8ab\u27e9}^{{m}_{ab}-q}W& \text{if}\hspace{0.17em}q\hspace{0.17em}\text{is odd, or}\\ {\u27e8ba\u27e9}^{{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\u2a66{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}{\u27e8ba\u27e9}^{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}{\u27e8ba\u27e9}^{q+1}& \text{otherwise.}\end{array}$$ In each case ${C}^{+}\u2a66Cc$ where $c$ is the target of $C\text{.}$
[Ed: Note that, if $q={m}_{ab}-1,$ $${C}^{+}\equiv aC\u2a66{C}_{0}a{\u27e8ba\u27e9}^{q}\equiv {C}_{0}{\u27e8ab\u27e9}^{{m}_{ab}}\u2a66{C}_{0}{\u27e8ba\u27e9}^{{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\u2a66{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)\u2a66{S}_{a}\left(W\right)\u2a66W\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)\u2a66{D}_{a}\left(W\right)\text{.}$ Since ${C}^{+}{D}^{-}\u2a66CD$ it is clear (either way) that $${S}_{a}\left(W\right)\u2a66{C}_{a}\left(W\right){T}_{c}\left({D}_{a}\left(W\right)\right)\u2a66{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)\u2a66{S}_{a}\left(W\right)\u2a66W\text{.}$ $\square \phantom{\rule{1em}{0ex}}\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)\u2a66W\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}^{+}\u2a66Cc\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)\phantom{\rule{1em}{0ex}}\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\u2a66{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)\u2a66{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\u2a66{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\u2a66aY\u2a66{W}_{i}Z$ for some positive words $T$ and $Z,$ so by (3.1) $$V\u2a66{W}_{i}bZ\prime \u2a66{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 \phantom{\rule{1em}{0ex}}\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}\u2a66W$], 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}\u2a66V$ 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}{\u27e8ba\u27e9}^{{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}{\u27e8ba\u27e9}^{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)\u2a66{\u27e8ba\u27e9}^{{m}_{ab}}E\text{.}$$ Then $$\begin{array}{ccc}\stackrel{\sim}{V}& \equiv & a{C}_{0}{\u27e8ba\u27e9}^{{m}_{ab}-1}{\u27e8ba\u27e9}^{q}E\phantom{\rule{1em}{0ex}}\text{if}\hspace{0.17em}{m}_{ab}\hspace{0.17em}\text{is even}\\ \stackrel{\sim}{V}& \equiv & a{C}_{0}{\u27e8ba\u27e9}^{{m}_{ab}-1}{\u27e8ab\u27e9}^{q}E\phantom{\rule{1em}{0ex}}\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\u2a66aU\text{.}$ It follows from the reduction lemma that $U\u2a66W$ 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}\u2a66W\text{.}$ Assume ${W}_{i}$ is square free. Then either ${W}_{i+1}\equiv {W}_{i}$ or ${W}_{i+1}\u2a66{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\u2a66W\xb7(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{.}$$
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.