Last update: 26 January 2014
Let and be positive words. Say divides (on the left) if and write (interpreted in the context of or
We present an algorithm which is used later in the theory of divisibility in 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 be a letter. The simplest positive words which are not multiples of are clearly those in which does not appear. Further, the words of the form with and are also not divisible by Of course many other quite simple words have this property, for example concatenations of the previous types of words in specific order, called which we will define shortly. At the same time we will define what we mean by the source and target of an
|(i)||A primitive is a positive word such that for all letters in (so and|
|(ii)||An elementary is a positive word of the form with and The source is and the target is if is even, and if is odd.|
|(iii)||An is a product where for each is a primitive or elementary for some such that and the target of is the source of|
[Ed: This may be expressed as:
The source of is and the target of is the target of If this target is we say: is a chain from to
|(iv)||There is a unique decomposition of a given 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 is a chain from to then is a chain from to
Let be a chain from to (where is a primitive or elementary chain from to for and a positive word such that divides Then divides and in particular does not divide
The last claim follows from the first by putting equal to the empty word. We prove the first claim by induction on Suppose
(a) Suppose is primitive, so for all Then for some positive word [Recall the Reduction Lemma (2.1): If are positive words and such that then there exists a positive word such that By (2.1), for some positive word Continuing in this fashion yields that divides and we are done (since is the target of
(b) Suppose is elementary, where and Then for some positive word By (2.1), for some positive word So by cancellation (special case of (2.1)), So is divisible by if is odd, and if is even, which is in each case the target of and we are done.
This begins the induction. Suppose now By the inductive hypothesis divides and by (a) and (b), divides and we are done.
3.2. For all positive words and letters we will define a recursively calculable positive word such that and either begins with or is an To simplify the description we need other operations on positive words:
(i) Every positive has a unique factorization where or where is a primitive and and elementary such that the word length of is as large as possible.
(ii) If is a primitive put which is positive equivalent to by commutativity.
If where is primitive, put In each case where is the target of
[Ed: Note that, if where is the target of
N.B.: The point of this definition is to construct a word which is positive equivalent to a chain from to and such that either starts with or where is also elementary, but longer than
(iii) If is any nonempty positive word denote by the word obtained by deleting the first letter of [Ed: Thus
Definition. For empty or beginning with put For all other words define recursively: let and suppose the has target Then put and (the result of applying times).
[Observations. Let be positive and Then
|(A)||if is an or begins with|
(A) The result if clear if begins with or is empty. Suppose is a nonempty so where is a nonempty chain from to say and is a By an inductive hypothesis, since so that noting that cannot be the first letter of whence and (i) is proved.
(B) Again the result is clear if begins with or is empty. Otherwise, we may suppose that is nonempty. Thus and by an inductive hypothesis Since it is clear (either way) that Now since we may repeat this step times to show that
Let be positive and Then
|(i)||is an or begins with|
|(ii)||if and only if is an or begins with|
The proof for all three parts follows by induction on the wordlength, where the induction basis is trivial. [ Ed: Namely when More concretely, if then is or an and the algorithm again leaves unchanged. ]
(i) [We may suppose that ]. From the definition of and the induction hypothesis the following is true. If is neither an nor a word beginning with then has length strictly greater than Hence the result of successive applications of must eventually, for at least, be either an or word beginning with
[Note: If is an or begins with then the first statement is clear since, by Observation (A), Otherwise, is non-empty. Then, by the induction hypothesis, if is not its first letter is a and composes with to make an Otherwise and, by the N.B. above, either starts with or is of such a form that is must divide This last implies that Note that, by Observation (A), each further application of either leaves the word unchanged (when it is already either an or a word beginning with or strictly increases the prefix Thus, after successive applications, either is an or starts with or This last case gives an obvious contradiction once since preserves the total word length, so that Hence must either be an or start with (One may like to observe that, once 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 and the induction hypothesis it follows that, for an or word beginning with and thence that The converse follows by (i).
(iii) The proof by induction is trivial, given that
3.3. With the help of the projection operators defined in 3.2 one gets a simple algorithm for producing a common multiple of a letter and a word if one exists. If a positive word begins with put If is a chain from to then put
Definition. Let be a positive word and Then the of is the sequence at positive words for where for all
[Ed: Note that the following lemma anticipates the following section (§4) by effectively demonstrating that if a common multiple exists then the of terminates in a word which is a least common multiple for and That is both and divide and divides any other common multiple of and
The original text is translated below, but we give here an expanded version as follows:
|(i)||If is a common multiple of and then divides for all and for (the sequence terminates).|
|(ii)||Conversely, if for some then is a common multiple of and (and, by (i), a least common multiple).|
(ii) Suppose By definition begins with Certainly (by Lemma 3.2). Suppose divides Now But which is divisible by and hence by By induction divides so is a common multiple of and
(i) Suppose now that is a common multiple of and Since divides Suppose divides Either begins with in which case and certainly divides or is an and where is the target of But for some positive words and so by (3.1) for some positive word By induction this shows divides for all If then Since we must then have Thus for all
Let be a positive word, a letter, and the of Then there exists a common multiple of and precisely when for
When it follows by the definition of the that divides Because each clearly divides [Ed: and because ], then every is a common multiple of and Conversely, if is a common multiple, then it follows by the definition of together with (3.1) and (3.2) that is divisible by every From it follows that From it then follows that Thus implies that
3.4. When a positive word is of the form where and are positive words and is a letter then we say has a quadratic factor. A word is square-free relative to a Coxeter matrix when is not positive equivalent to a word with a quadratic factor. The image of a square free word in is called square-free.
Let be a square-free positive word and a letter such that is not square free. Then divides
First we prove the following lemma.
Lemma. Let be a positive word which is divisible by and contains a square. Then there is a positive word with which contains a square and which begins with
The proof of the Lemma is by induction on the length of Decompose as in 3.2, in the form Without loss of generality we may assume that is a representative of its positive equivalence class which contains a square and is such that is maximal.
When is the empty word it follows naturally that satisfies the conditions for For nonempty we have three cases
|(i)||contains a square. Then satisfies the conditions for|
|(ii)||contains a square. By the induction assumption, one can assume, without loss of generality that begins with the target of the Thus, since the length of is maximal, is of the form where is a primitive From this if follows that when contains a square then satisfies the conditions for and otherwise does.|
|(iii)||Neither or contain a square. Then is of the form where and begins with if is even, and if is odd. Then from the fact that divides the reduction lemma is applicable and the relations imply that there exists such that Then satisfy the conditions.|
This finishes the proof of the lemma.
|Proof of 3.4.|
By the Lemma there exists a positive word such that contains a square and It follows from the reduction lemma that and, since is square free that does not contain a square. So begins with and is divisible by
3.5. By applying 3.4 we get the following lemma which will be needed later.
If is a square free positive word and is a letter then the of are also square free.
is square free since Assume is square free. Then either or where is the target of the chain If is not square free then is not square free and by 3.4, the chain is not divisible by in contradiction to 3.1.
3.6. Using the operators we can give a division algorithm, which, when given positive words and such that divides constructs a positive word such that
Definition. For is the word
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.