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 Conjugation Problem

In this section we solve the conjugation problem for all Artin groups $G_M$ of finite type.

Two words $V$ and $W$ are called conjugate when there exists a word $A$ such that $V=A^{-1}WA$ and we denote this by $V\sim W\text{.}$ The conjugation problem consists of giving an algorithm for deciding whether any two given words are conjugate. In our case this problem can easily be reduced to the simpler problem of checking whether any two positive words are conjugate. Here we give a method with which one can calculate, for every positive word $W,$ the finite set of all positive words which are conjugate to $W\text{.}$ With this the conjugation problem is clearly solved.

8.1. When two positive words $V$ and $W$ are conjugate, there exists a word $A$ such that $AV=WA\text{.}$ Since by 5.5 there exist a positive word $B$ and a central word $C$ such that $A=B{C}^{-1},$ then also $BV⩦WB\text{.}$ This proves the following lemma.

Positive words $V$ and $W$ are conjugate precisely when there is a positive word $A$ such that $$AV⩦WA$$

8.2. Every positive word is positive equivalent to the product of square free words. This approaches the goal of creating the positive word $A^{-1}WA$ conjugate to the positive word $W,$ in which one conjugates successively by the square-free factors of $A,$ and in such a manner that one always obtains positive words. By considering 8.1 one arrives at the following construction.

For every finite set $X$ of positive words define the set $X\prime$ of positive words by $$X\prime =\left\{V\hspace{0.17em}\right|\hspace{0.17em}AV⩦WA\hspace{0.17em}\text{with}\hspace{0.17em}W\in X\hspace{0.17em}\text{and}\hspace{0.17em}A\hspace{0.17em}\text{square free}\}\text{.}$$ Because this set is finite, one can iterate the construction and obtain the sets $$X^{\left(k\right)}=\left(X^{(k-1)}\right)\prime \text{.}$$ The sets $X^{\left(k\right)}$ of positive words are calculable. Since by 5.4, for $G_M$ of finite type there are only finitely many square free words $A,$ namely divisors of the fundamental word $\Delta ,$ and these are calculable using the division algorithm. Furthermore the division algorithm decides for which square free words $A$ the word $WA$ is left divisible, and the division algorithm 3.6 gives us the quotient $(W·A):A\text{.}$ Finally, by the solution to the word problem in 6.3, all positive words $V$ such that $V⩦\left(WA\right):A$ are calculable, that is, all $V$ such that $AV⩦WA\text{.}$ Hence $X\prime$ is calculable, and so too are $X^{\left(k\right)}\text{.}$

Let $l\left(X\right)$ be the maximum of the lengths of words in $X\text{.}$ Then it is clear that $l\left(X^{\left(k\right)}\right)=l\left(X\right)\text{.}$ [Ed: Clearly $X^{\left(i\right)}\subseteq X^{(i+1)},$ by putting $A\equiv 1,$ and for $V\in X^{(i+1)},$ $l\left(V\right)=l\left(W\right)$ for some $W\in X^{\left(i\right)}\text{.}$ ] If we let $k\left(l\right)$ be the number of positive words of length $\le l$ then $X^{\left(k\right)}$ has at most $k\left(l\left(X\right)\right)$ elements. Because $X^{\left(k\right)}\subseteq X^{(k+1)},$ then eventually, for $k=k\left(l\left(X\right)\right),$ $X^{\left(k\right)}=X^{(k+1)}\text{.}$ [Ed: Note that once $X^{\left(i\right)}=X^{(i+1)}$ then $X^{\left(i\right)}=X^{\left(j\right)}$ for all $j>i\text{.}$ ] Hence $$X^{\left(k\left(l\left(X\right)\right)\right)}={\cup }_k{X}^{\left(k\right)}\text{.}$$

Definition. $X^{\sim }=X^{\left(k\left(l\left(X\right)\right)\right)}\text{.}$

So $X^{\sim }$ is the smallest set of positive words containing both $X$ and, for every element $W\in X^{\sim },$ all other positive words $V$ of the form $V=A^{-1}WA$ for some square free word $A\text{.}$ The set $X^{\sim }$ is calculable.

Let $X$ be a finite set of positive words. Then the finite set $X^{\sim }$ is calculable and $$X^{\sim }=\left\{V\hspace{0.17em}\right|\hspace{0.17em}V\sim W\text{with}W\in X\}$$

		Proof.
	By 8.1 it suffices to show, by induction on the length of $A,$ that for positive words $V$ and $A$ with $AV⩦WA$ for some $W\in X,$ that $V$ is also an element of $X^{\sim }\text{.}$ [Ed: It is clear that $X^{\sim }\subseteq \left\{V\hspace{0.17em}\right|\hspace{0.17em}V\sim W\text{with}W\in X\}\text{.}$ One must establish the reverse inclusion. ] Let $A⩦BC$ where $B$ is a square free divisor of $A$ of maximal length. We claim that $B$ is a left divisor of $WB\text{.}$ When we have proved this we are finished because then $WB⩦BU$ with $U\in X^{\sim }$ and $BCV⩦WBC⩦BUC,$ so $CV⩦UC$ and by induction hypothesis $V\in {\left(X^{\sim }\right)}^{\sim }=X^{\sim }\text{.}$ To prove the left divisibility of $WB$ by $B\text{:}$ For $B$ square free, by 5.1 and 5.4 there exists a positive word $D$ with $DB⩦\Delta \text{.}$ Then $DWBC⩦DBCV⩦\Delta CV,$ so that $DWBC$ is divisible by $\Delta \text{.}$ We claim that indeed $DWB$ is divisible on the right by every letter $a$ and thus by $\Delta \text{.}$ Otherwise by 5.3 we have that $C$ is left divisible by $a$ and by 3.4 $Ba$ is square free. Both together contradict the maximality of the length of $B\text{.}$ So there exists a positive word $U$ with $DWB⩦\Delta U,$ that is with $WB⩦BU,$ which is what was to be shown. $\square$

8.3. The result of the previous section contains the solution to the conjugation problem.

Let $G_M$ be an Artin group of finite type. Let $\Delta$ be the fundamental word for $G_M\text{.}$ Then the following solves the conjugation problem.

(i)

Let $V$ and $W$ be arbitrary words. For their exponents take $m\left(V\right)\ge m\left(W\right)\text{.}$ Let $V={\Delta }^{m\left(V\right)}{V}^{+}$ and $W={\Delta }^{m\left(W\right)}{W}^{+}$ with $V^{+}$ and $W^{+}$ positive words. Then $V$ and $W$ are conjugate when $$\begin{array}{cccc}{W}^{+}& \sim & {\Delta }^{m\left(V\right)-m\left(W\right)}{V}^{+},& \text{if}\hspace{0.17em}\Delta \hspace{0.17em}\text{is central or}\hspace{0.17em}m\left(W\right)\hspace{0.17em}\text{even,}\\ \Delta W^{+}& \sim & {\Delta }^{m\left(V\right)-m\left(W\right)+1}{V}^{+},& \text{if}\hspace{0.17em}\Delta \hspace{0.17em}\text{is not central and}\hspace{0.17em}m\left(W\right)\hspace{0.17em}\text{odd.}\end{array}$$

(ii)

If $V$ and $W$ are positive words, then $V$ is conjugate to $W$ when $V$ is an element of the calculable set of positive words $W^{\sim }\text{.}$

		Proof.
	The statement (i) follows in a trivial way from the centrality of ${\Delta }^2,$ and (ii) follows trivially from 8.2. $\square$

Note added in proof. In the work which was cited in the introduction, Deligne also determined the centre and solved the word and the conjugation problems for the Artin groups of finite type. As we have, he utilises the ideas of Garside but in a geometric formulation which goes back to Tits. We therefore after some consideration deem the publication of our simple purely combinatorial solution defensible.

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