Artin groups and Coxeter groups

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

Last update: 29 January 2014

Divisibility Theory

4.1. By a common divisor of a system gj, jJ of elements of a semigroup G+ we mean an element of G+ which divides each gj (or more exactly, divides on the left). Similarly, a common multiple is an element which is (left) divisible by all gj, jJ. 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 GM+ and no element of GM+ other than the identity has an inverse, when greatest common divisors and least common multiples exist, they are uniquely determined. For the system g1,,gkG+, we denote the least common multiple (w.r.t. left divisibility) by [g1,,gk]l or just [g1,,gk] and the greatest common divisor by (g1,,gk)l or (g1,,gk). The corresponding notation for divisibility from the right is [g1,,gk]r and (g1,,gm)r respectively. Corresponding ideas and notations apply for the positive words (in F+) 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 GM+ 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 V and W which have a common multiple a least common multiple exists. We prove this simultaneously for all W by induction on the length of V.

Starting the induction: Let Va and U a common multiple of a and W. Then from (3.3) there is a term Wi in the a-series of W with WiWi+1. This Wi is then a least common multiple of a and W, since by (3.3) both a and W divide Wi, and from the construction of the a-series and (3.1) it follows that Wj divides U for j=1,2,,i.

[Aside: Recall

(3.1) If C is a chain from a to b and D a positive word such that CD is divisible by a, then D is divisible by b.

So if W|U, then either Wk+1Wk so Wk+1|U, or Wk is an a-chain from a to b say, and WkKU for some word K, and a|WkK, so K must be divisible by b, so UWkbK for some word K, but Wk+1Ta(Wb). So UWk+1K, and Wk+1|U.

So we have that Wi is a least common multiple. ]

Completing the induction: Let VaV and U be a common multiple of V and W with UaU. Since U is a common multiple of a and W, by the first induction step there is a least common multiple aW of a and W. By the reduction lemma, U is a common multiple of V and W, so by induction hypothesis there exists a least common multiple [V,W]. Then a[V,w] is the least common multiple of V and W.

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 GM+ has a greatest common divisor.


Let XGM+ and WX. The set of common divisors of the elements of X is a finite set {A1,,Ak}, since each of these elements must divide W, and there are only finitely many divisors of W.

[Aside: A divisor of W cannot be longer than W, and (given a finite indexing set / set of letters) there are only finitely many words of length less than or equal to W in F+. ]

Since W is a common multiple of all A1,,Ak, by (4.1), (Existence of least common multiple), the least common multiple [A1,,Ak] exists, and this is clearly the greatest common divisor of the elements of X.

[Aside: Let N=[A1,,Ak]. For all WX, W is a common multiple of {A1,,Ak}, so since N is the least common multiple, N|W. So N is a common divisor of X. So N{A1,,Ak}, 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 [a,W]: W1Ta(W), and Wi+1Wi if Wi starts with a, or Wi+1Ta(Wib) if Wi is an a-chain from a to b. But if ba, then the only way we can have an a-chain from a to b is if there is an elementary sub-chain somewhere in the a-chain containing b. So Wi+1 only contains letters which are already in Wi. ]

4.3. From application of the operation rev to the result of (4.1), it is easy to get the following Lemma:

(i) [A1,,Ak]l exists precisely when [revA1,,revAk]r exists, and then the following holds: [A1,,Ak]l rev ( [revA1,,revAk]r ) ,
(ii) (A1,,Ak)l rev ((revA1,,revAk)r) .

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