Finite/Infinite Coxeter Groups

In the same contest as this we got the following problem:

We are given a language with only three letters letters $A,B,C$. Two words are equivalent if they can be transformed from one another using transformations of consecutive letters in a word like this: $ABA \leftrightarrow BAB$, $ACA \leftrightarrow CAC$ and $AA=BB=CC=\emptyset$

Decide if there are finite or infinite number of non equivalent words in this language if the following condition is added:

1) $BC=CB$;

2) $BCB=CBC$.

If there are a finite number of words, how many inequivalent words are there?

The problem can be quickly translated into group theory (which I didn't see...) like this:

A group has three generators $a,b,c$ with the following relations between them. Decide in each case if the group is finite/infinite. If finite, find the number of elements of the group.

1) $a^2=b^2=c^2=e, \ (ab)^3=e, \ (ac)^3=3,\ (bc)^2=e$;

2) $a^2=b^2=c^2=e, \ (ab)^3=e, \ (ac)^3=3,\ (bc)^3=e$.

These are easily seen to be particular cases of Coxeter groups. The official proofs were based on finding actual geometrical models of the given Coxeter groups (this is always possible, although not very simple...). Of course, no one of the participants thought of it like this, and in case $1)$ it is possible to prove that there are finitely many words by proving that a large enough word, which is equivalent to a word of the form $ABCABC..., BABCABC...,BCABCABC...$ can be made shorter, but even if we prove that there are finitely many words, there is still the part when we need to count the different words, which can be very tricky. For the second problem no solution without Coxeter groups geometrical representation was presented.

My questions are:

1) Are there any results from which we can see directly from the relations given for the Coxeter group if the group is finite or not? I am interested especially in the 3 generators case, but maybe there are some results in the general case also.

2) Can we find the number of inequivalent words in the first part without using Coxeter groups?

3) Can you solve second part without using Coxeter groups?

Solution 1:

To expand on Jack Schmidt's comment, a confluent rewriting system for the first example has the eight reduction rules:

$a^2 \to 1$, $b^2 \to 1$, $c^2 \to 1$, $bab \to aba$, $cac \to aca$, $cb \to bc$, $caba \to bcab$, $cabc \to acab$,

form which you can see that there are exactly 24 irreducible words (i.e. those not containing the left-hand-side of a reduction rule):

$1$, $a$, $b$, $c$, $ab$, $ac$, $ba$, $bc$, $ca$, $aba$, $abc$, $aca$, $bac$, $bca$, $cab$, $abac$, $abca$, $acab$, $baca$, $bcab$, $abaca$, $abcab$, $bacab$, $abacab,$

although it makes life easier to check such calculations by computer.

The second example also has a confluent rewriting system, this time with the nine rules:

$a^2 \to 1$, $b^2 \to 1$, $c^2 \to 1$, $bab \to aba$, $cac \to aca$, $cbc \to bcb$, $cabcb \to acabc$, $cbaca \to bcbac$, $cabcaba \to acabcab.$

Note that the words $(abc)^n$ are irreducible for all $n$, so the group is infinite.

Solution 2:

The first group is a presentation of $S_4$ with $b= (12)$, $c=(34)$, and $a=(23)$.

The second group is the symmetries of a tiling of the plane by equilateral triangles, with $a$, $b$ and $c$ reflections in the sides of one equilateral triangle. The group with the given relations maps onto the symmetry group of the tiling (isomorphically, but you don't need to prove that to see that the abstract group is at least as large as the symmetry group of the tiling). The word $(abc)^2$ maps to a translation and generates an infinite subgroup of motions of the tiling.