Last update: 29 January 2014
4.1. By a common divisor of a system of elements of a semigroup we mean an element of which divides each (or more exactly, divides on the left). Similarly, a common multiple is an element which is (left) divisible by all A greatest common divisor (g.c.d.) is a divisor into which all other common divisors divide, and a least common multiple (l.c.m.) is a common multiple which divides all other common multiples. The analogous concepts of divisibility on the right are similarly defined.
Because the reduction rule (2.3) holds in the Artin semigroup and no element of other than the identity has an inverse, when greatest common divisors and least common multiples exist, they are uniquely determined. For the system we denote the least common multiple (w.r.t. left divisibility) by or just and the greatest common divisor by or The corresponding notation for divisibility from the right is and respectively. Corresponding ideas and notations apply for the positive words (in which these elements represent.
It is clear that infinite subsets of an Artin semigroup can have no common multiples. But for finite subsets:
A finite set of elements of an Artin semigroup either has a least common multiple or no common multiple at all.
Since one can carry out an induction on the number of elements, it suffices to show that for any two positive words and which have a common multiple a least common multiple exists. We prove this simultaneously for all by induction on the length of
Starting the induction: Let and a common multiple of and Then from (3.3) there is a term in the of with This is then a least common multiple of and since by (3.3) both and divide and from the construction of the and (3.1) it follows that divides for
(3.1) If is a chain from to and a positive word such that is divisible by then is divisible by
So if then either so or is an from to say, and for some word and so must be divisible by so for some word but So and
So we have that is a least common multiple. ]
Completing the induction: Let and be a common multiple of and with Since is a common multiple of and by the first induction step there is a least common multiple of and By the reduction lemma, is a common multiple of and so by induction hypothesis there exists a least common multiple Then is the least common multiple of and
4.2. While in certain Artin semigroups there are pairs of elements without a least common multiple, the greatest common divisor always exists:
Every non-empty set of elements of an Artin semigroup has a greatest common divisor.
Let and The set of common divisors of the elements of is a finite set since each of these elements must divide and there are only finitely many divisors of
[Aside: A divisor of cannot be longer than and (given a finite indexing set / set of letters) there are only finitely many words of length less than or equal to in ]
Since is a common multiple of all by (4.1), (Existence of least common multiple), the least common multiple exists, and this is clearly the greatest common divisor of the elements of
[Aside: Let For all is a common multiple of so since is the least common multiple, So is a common divisor of So and since it is a common multiple of this set, it must be the greatest common divisor. ]
Comment. The only letters arising in the greatest common divisor and least common multiple of a set of words are those occurring in the words themselves.
For the greatest common divisor it is clear, because in any pair of positive equivalent words exactly the same letters occur. For the least common multiple, the proof is an exact analogue of the existence proof in (4.1).
[Aside: Recall how we found and if starts with or if is an from to But if then the only way we can have an from to is if there is an elementary sub-chain somewhere in the containing So only contains letters which are already in ]
4.3. From application of the operation rev to the result of (4.1), it is easy to get the following Lemma:
|(i)||exists precisely when exists, and then the following holds:|
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.