Artin groups and Coxeter groups

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 29 January 2014

The Word Problem

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⩦W\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 ″$ 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}⩦{\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⩦W$ 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}⩦{\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)⩦W\text{.}$
(ii)	$N^{+}\left(W\right)$ is in normal form.

		Proof.
	(i) By induction on word length one proves that $$W⩦{\Delta }_{I\left(W\right)}·(W:{\Delta }_{I\left(W\right)})⩦{\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⩦W$ 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⩦W$ if and only if $N^{+}\left(V\right)⩦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}⩦{\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$

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