Last update: 29 January 2014
In this section we solve the word problem first for Artin semigroups of finite type and then for Artin groups of finite type.
6.1. Let $M$ be a Coxeter matrix on $I\text{.}$ For each positive word $W$ we define a subset $I\left(W\right)$ of $I$ by $$I\left(W\right)=\{i\in I\hspace{0.17em}\text{such that}\hspace{0.17em}{a}_{i}|W\}\text{.}$$ For $W\u2a66W\prime $ it follows naturally that $I\left(W\right)=I\left(W\prime \right)\text{.}$
For each subset $J$ of $I$ for which a fundamental element exists, we choose to represent this by the fundamental word ${\Delta}_{J}$ as we did in 5.8. [Ed: Implicitly we have chosen an ordering of the elements of $J,$ and the words $\Pi ,\Pi \prime ,\Pi \u2033$ from (5.8) are products of letters in that order.] Now we can define the normal form for positive words.
Definition. A positive word $W$ is in normal form relative to $M$ when $$W\equiv {\Delta}_{{I}_{1}}{\Delta}_{{I}_{2}}\cdots {\Delta}_{{I}_{k}}$$ where $k\ge 0$ and the ${I}_{j}$ are nonempty subsets of $I$ such that, for $j=1,2,\dots ,k,$ we have $${I}_{j}=I\left({\Delta}_{{I}_{j}}{\Delta}_{{I}_{j+1}}\dots {\Delta}_{{I}_{k}}\right)\text{.}$$
For positive words in normal form we have $${\Delta}_{{I}_{1}}\dots {\Delta}_{{I}_{k}}\u2a66{\Delta}_{{J}_{1}}\cdots {\Delta}_{{J}_{l}}$$ exactly when $k=l$ and ${I}_{j}={J}_{j}$ for $j=1,2,\dots ,k\text{.}$
Proof. | |
The proof is by induction on the length of the words. For length $0$ the statement is trivial. Let $V\equiv {\Delta}_{{I}_{1}}\cdots {\Delta}_{{I}_{k}}$ and $W\equiv {\Delta}_{{J}_{1}}\cdots {\Delta}_{{J}_{l}}$ be of length less than or equal to $\lambda $ and assume the statement of the lemma for words of length less than $\lambda \text{.}$ It follows from $V\u2a66W$ that $I\left(V\right)=I\left(W\right)$ and thus ${I}_{1}={J}_{1}\text{.}$ From 2.3 it follows that ${\Delta}_{{I}_{2}}\cdots {\Delta}_{{I}_{k}}\u2a66{\Delta}_{{J}_{2}}\cdots {\Delta}_{{J}_{l}}$ and hence that $l=k$ and ${I}_{j}={J}_{j}$ by the induction assumption. $\square $ |
6.2. We shall algorithmically rewrite each positive word $W$ into a positive equivalent word ${N}^{+}\left(W\right)$ which is in normal form.
For the empty word $W$ we define ${N}^{+}\left(W\right)\equiv W\text{.}$ For words $W$ of positive length ${N}^{+}\left(W\right)$ is recursively defined by $${N}^{+}\left(W\right)\equiv {\Delta}_{I\left(W\right)}{N}^{+}(W:{\Delta}_{I\left(W\right)})\text{.}$$
(i) | ${N}^{+}\left(W\right)\u2a66W\text{.}$ |
(ii) | ${N}^{+}\left(W\right)$ is in normal form. |
Proof. | |
(i) By induction on word length one proves that $$W\u2a66{\Delta}_{I\left(W\right)}\xb7(W:{\Delta}_{I\left(W\right)})\u2a66{\Delta}_{I\left(W\right)}{N}^{+}(W:{\Delta}_{I\left(W\right)})\text{.}$$ (ii) This statement is also proved by an easy induction. By the induction assumption ${N}^{+}(W:{\Delta}_{I\left(W\right)})$ is in normal form and since, by (i), $I\left(W\right)=I\left({N}^{+}\left(W\right)\right)$ it follows that ${N}^{+}\left(W\right)$ is in normal form. $\square $ |
Definition. ${N}^{+}\left(W\right)$ is the positive normal form of $W\text{.}$
6.3. The following theorem solves the word problem for all Artin semigroups such that the positive normal form is computable.
$V\u2a66W$ if and only if ${N}^{+}\left(V\right)\equiv {N}^{+}\left(W\right)\text{.}$ In other words: positive words represent exactly the same element of the Artin semigroup ${G}_{M}^{+}$ when they have the same normal form with respect to $M\text{.}$
Proof. | |
By 6.2 (i) $V\u2a66W$ if and only if ${N}^{+}\left(V\right)\u2a66{N}^{+}\left(W\right)\text{.}$ By 6.1 and 6.2 (ii) this happens exactly when ${N}^{+}\left(V\right)\equiv {N}^{+}\left(W\right)\text{.}$ $\square $ |
6.4. Let $M$ be a Coxeter matrix on $I$ and suppose the Artin group ${G}_{M}$ is of finite type.
Definition. A word in the free group ${F}_{I}$ is in normal form if it is equal in the free group to a word $${\Delta}_{I}^{m}{\Delta}_{{I}_{1}}\cdots {\Delta}_{{I}_{k}}$$ where $m$ is an integer, $k$ is a natural number, $k\ge 0,$ the ${I}_{j}$ are subsets of $I$ and the positive word ${\Delta}_{{I}_{1}}\cdots {\Delta}_{{I}_{k}}$ is in normal form. [Ed: Here it is assumed that ${I}_{1}\ne I\text{.}$]
For words in normal form we have $${\Delta}_{I}^{m}{\Delta}_{{I}_{1}}\cdots {\Delta}_{{I}_{k}}={\Delta}_{I}^{n}{\Delta}_{{J}_{1}}\cdots {\Delta}_{{J}_{l}}$$ if and only if $m=n$ and $k=l$ and ${I}_{j}={J}_{j}$ for $j=1,\cdots ,k\text{.}$
Proof. | |
Let $m\ge n\text{.}$ Then by 5.5 $${\Delta}_{I}^{m-n}{\Delta}_{{I}_{1}}\cdots {\Delta}_{{I}_{k}}\u2a66{\Delta}_{{J}_{1}}\cdots {\Delta}_{{J}_{l}}$$ and the result now follows from 6.1. $\square $ |
6.5. Now we define a computable normal form $N\left(W\right)$ for each word $W\text{.}$ By 5.5, for each $W$ there exists an integer $m$ and a positive word $W\prime $ such that $W={\Delta}_{I}^{m}W\prime \text{.}$ We define the exponent of $W$ to be the maximum $m\left(W\right)$ of all such $m\text{.}$ The integer $m\left(W\right)$ is computable.
There is a positive word ${W}^{+}$ with $$W={\Delta}_{I}^{m\left(W\right)}{W}^{+}\text{.}$$ Such a ${W}^{+}$ is computable by the division algorithm 3.6 and the method described in 5.5. We note that with this definition ${W}^{+}$ is defined only up to positive equivalence, but by 6.3 ${N}^{+}\left({W}^{+}\right)$ is uniquely defined. Thus we can define $$N\left(W\right)\equiv {\Delta}_{I}^{m\left(W\right)}{N}^{+}\left({W}^{+}\right)\text{.}$$
(i) | $N\left(W\right)=W$ in ${G}_{M}\text{.}$ |
(ii) | $N\left(W\right)$ is in normal form. |
Proof. | |
(i) This statement follows trivially from 6.2 (i). (ii) To prove that (ii) is satisfied one observes that by 5.2 and 6.2 (ii) one need only show that $I\left({N}^{+}\left({W}^{+}\right)\right)\ne I\text{.}$ This is clear from the maximality of $m\left(W\right)\text{.}$ $\square $ |
Definition. $N\left(W\right)$ is the normal form of $W\text{.}$
6.6. The following theorem solves the word problem for Artin groups of finite type.
In an Artin group of finite type two words $V$ and $W$ represent the same element precisely when their normal forms are such that $N\left(V\right)\equiv N\left(W\right)\text{.}$
Proof. | |
The theorem follows trivially from 6.4 and 6.5. $\square $ |
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.