Last update: 29 January 2014
4.1. By a common divisor of a system ${g}_{j},$ $j\in J$ of elements of a semigroup ${G}^{+}$ we mean an element of ${G}^{+}$ which divides each ${g}_{j}$ (or more exactly, divides on the left). Similarly, a common multiple is an element which is (left) divisible by all ${g}_{j},$ $j\in J\text{.}$ 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 ${G}_{M}^{+}$ and no element of ${G}_{M}^{+}$ other than the identity has an inverse, when greatest common divisors and least common multiples exist, they are uniquely determined. For the system ${g}_{1},\cdots ,{g}_{k}\in {G}^{+},$ we denote the least common multiple (w.r.t. left divisibility) by ${[{g}_{1},\cdots ,{g}_{k}]}_{l}$ or just $[{g}_{1},\cdots ,{g}_{k}]$ and the greatest common divisor by ${({g}_{1},\cdots ,{g}_{k})}_{l}$ or $({g}_{1},\cdots ,{g}_{k})\text{.}$ The corresponding notation for divisibility from the right is ${[{g}_{1},\cdots ,{g}_{k}]}_{r}$ and ${({g}_{1},\cdots ,{g}_{m})}_{r}$ respectively. Corresponding ideas and notations apply for the positive words (in ${F}^{+}\text{)}$ 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 ${G}_{M}^{+}$ either has a least common multiple or no common multiple at all.
Proof. | |
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\text{.}$ Starting the induction: Let $V\equiv a$ and $U$ a common multiple of $a$ and $W\text{.}$ Then from (3.3) there is a term ${W}_{i}$ in the $a\text{-series}$ of $W$ with ${W}_{i}\equiv {W}_{i+1}\text{.}$ This ${W}_{i}$ is then a least common multiple of $a$ and $W,$ since by (3.3) both $a$ and $W$ divide ${W}_{i},$ and from the construction of the $a\text{-series}$ and (3.1) it follows that ${W}_{j}$ divides $U$ for $j=1,2,\dots ,i\text{.}$ [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\text{.}$ So if $W|U,$ then either ${W}_{k+1}\equiv {W}_{k}$ so ${W}_{k+1}|U,$ or ${W}_{k}$ is an $a\text{-chain}$ from $a$ to $b$ say, and ${W}_{k}K\u2a66U$ for some word $K,$ and $a|{W}_{k}K,$ so $K$ must be divisible by $b,$ so $U\u2a66{W}_{k}bK\prime $ for some word $K\prime ,$ but ${W}_{k+1}\equiv {T}_{a}\left(Wb\right)\text{.}$ So $U\u2a66{W}_{k+1}K\prime ,$ and ${W}_{k+1}|U\text{.}$ So we have that ${W}_{i}$ is a least common multiple. ] Completing the induction: Let $V\equiv aV\prime $ and $U$ be a common multiple of $V$ and $W$ with $U\equiv aU\prime \text{.}$ Since $U$ is a common multiple of $a$ and $W,$ by the first induction step there is a least common multiple $aW\prime $ of $a$ and $W\text{.}$ By the reduction lemma, $U\prime $ is a common multiple of $V\prime $ and $W\prime ,$ so by induction hypothesis there exists a least common multiple $[V\prime ,W\prime ]\text{.}$ Then $a[V\prime ,w\prime ]$ is the least common multiple of $V$ and $W\text{.}$ $\square $ |
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 ${G}_{M}^{+}$ has a greatest common divisor.
Proof. | |
Let $X\subseteq {G}_{M}^{+}$ and $W\in X\text{.}$ The set of common divisors of the elements of $X$ is a finite set $\{{A}_{1},\dots ,{A}_{k}\},$ since each of these elements must divide $W,$ and there are only finitely many divisors of $W\text{.}$ [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}^{+}\text{.}$ ] Since $W$ is a common multiple of all ${A}_{1},\cdots ,{A}_{k},$ by (4.1), (Existence of least common multiple), the least common multiple $[{A}_{1},\cdots ,{A}_{k}]$ exists, and this is clearly the greatest common divisor of the elements of $X\text{.}$ [Aside: Let $N=[{A}_{1},\cdots ,{A}_{k}]\text{.}$ For all $W\in X,$ $W$ is a common multiple of $\{{A}_{1},\cdots ,{A}_{k}\},$ so since $N$ is the least common multiple, $N|W\text{.}$ So $N$ is a common divisor of $X\text{.}$ So $N\in \{{A}_{1},\cdots ,{A}_{k}\},$ and since it is a common multiple of this set, it must be the greatest common divisor. ] $\square $ |
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.
Proof. | |
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]\text{:}$ ${W}_{1}\equiv {T}_{a}\left(W\right),$ and ${W}_{i+1}\equiv {W}_{i}$ if ${W}_{i}$ starts with $a,$ or ${W}_{i+1}\equiv {T}_{a}\left({W}_{i}b\right)$ if ${W}_{i}$ is an $a\text{-chain}$ from $a$ to $b\text{.}$ But if $b\ne a,$ then the only way we can have an $a\text{-chain}$ from $a$ to $b$ is if there is an elementary sub-chain somewhere in the $a\text{-chain}$ containing $b\text{.}$ So ${W}_{i+1}$ only contains letters which are already in ${W}_{i}\text{.}$ ] $\square $ |
4.3. From application of the operation rev to the result of (4.1), it is easy to get the following Lemma:
(i) | ${[{A}_{1},\cdots ,{A}_{k}]}_{l}$ exists precisely when ${[\text{rev}\hspace{0.17em}{A}_{1},\cdots ,\text{rev}\hspace{0.17em}{A}_{k}]}_{r}$ exists, and then the following holds: $${[{A}_{1},\cdots ,{A}_{k}]}_{l}\u2a66\text{rev}\hspace{0.17em}\left({[\text{rev}\hspace{0.17em}{A}_{1},\cdots ,\text{rev}\hspace{0.17em}{A}_{k}]}_{r}\right),$$ |
(ii) | ${({A}_{1},\cdots ,{A}_{k})}_{l}\u2a66\text{rev}\hspace{0.17em}\left({(\text{rev}\hspace{0.17em}{A}_{1},\cdots ,\text{rev}\hspace{0.17em}{A}_{k})}_{r}\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.