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. For each positive word W we define a subset I(W) of I by I(W)= {iIsuch thatai|W}. For WW it follows naturally that I(W)=I(W).

For each subset J of I for which a fundamental element exists, we choose to represent this by the fundamental word ΔJ as we did in 5.8. [Ed: Implicitly we have chosen an ordering of the elements of J, and the words Π,Π,Π 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ΔI1 ΔI2 ΔIk where k0 and the Ij are nonempty subsets of I such that, for j=1,2,,k, we have Ij=I ( ΔIj ΔIj+1 ΔIk ) .

For positive words in normal form we have ΔI1 ΔIk ΔJ1 ΔJl exactly when k=l and Ij=Jj for j=1,2,,k.

Proof.

The proof is by induction on the length of the words. For length 0 the statement is trivial.

Let VΔI1ΔIk and WΔJ1ΔJl be of length less than or equal to λ and assume the statement of the lemma for words of length less than λ. It follows from VW that I(V)=I(W) and thus I1=J1. From 2.3 it follows that ΔI2ΔIkΔJ2ΔJl and hence that l=k and Ij=Jj by the induction assumption.

6.2. We shall algorithmically rewrite each positive word W into a positive equivalent word N+(W) which is in normal form.

For the empty word W we define N+(W)W. For words W of positive length N+(W) is recursively defined by N+(W)ΔI(W) N+(W:ΔI(W)).

(i) N+(W)W.
(ii) N+(W) is in normal form.

Proof.

(i) By induction on word length one proves that WΔI(W) ·(W:ΔI(W)) ΔI(W) N+(W:ΔI(W)).

(ii) This statement is also proved by an easy induction. By the induction assumption N+(W:ΔI(W)) is in normal form and since, by (i), I(W)=I(N+(W)) it follows that N+(W) is in normal form.

Definition. N+(W) is the positive normal form of W.

6.3. The following theorem solves the word problem for all Artin semigroups such that the positive normal form is computable.

VW if and only if N+(V)N+(W). In other words: positive words represent exactly the same element of the Artin semigroup GM+ when they have the same normal form with respect to M.

Proof.

By 6.2 (i) VW if and only if N+(V)N+(W). By 6.1 and 6.2 (ii) this happens exactly when N+(V)N+(W).

6.4. Let M be a Coxeter matrix on I and suppose the Artin group GM is of finite type.

Definition. A word in the free group FI is in normal form if it is equal in the free group to a word ΔImΔI1 ΔIk where m is an integer, k is a natural number, k0, the Ij are subsets of I and the positive word ΔI1ΔIk is in normal form. [Ed: Here it is assumed that I1I.]

For words in normal form we have ΔImΔI1 ΔIk= ΔInΔJ1 ΔJl if and only if m=n and k=l and Ij=Jj for j=1,,k.

Proof.

Let mn. Then by 5.5 ΔIm-n ΔI1 ΔIk ΔJ1 ΔJl and the result now follows from 6.1.

6.5. Now we define a computable normal form N(W) for each word W. By 5.5, for each W there exists an integer m and a positive word W such that W=ΔImW. We define the exponent of W to be the maximum m(W) of all such m. The integer m(W) is computable.

There is a positive word W+ with W=ΔIm(W) W+. 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+(W+) is uniquely defined. Thus we can define N(W)ΔIm(W) N+(W+).

(i) N(W)=W in GM.
(ii) N(W) 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(N+(W+))I. This is clear from the maximality of m(W).

Definition. N(W) is the normal form of W.

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(V)N(W).

Proof.

The theorem follows trivially from 6.4 and 6.5.

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