Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Coxeter classifies all finite Coxeter groups in a paper from 1935 (jlms.oxfordjournals.org/content/s1-10/1/21.extract is a link, but it might not work for you. The paper is entitled "the complete enumeration of finite groups of the form R_i^2=(R_iR_j)^{k_{i, j}}=1", J. Lon. Math. Soc) –  user1729 Sep 23 '11 at 8:45
    
en.wikipedia.org/wiki/Triangle_group –  user641 Sep 23 '11 at 13:31
    
@SteveD: That's a very nice link. Thank you. I think that answere my question fully and directly, for the case of 3 generators and also answers very fast to the contest problem, since $\frac{1}{3}+\frac{1}{3}+\frac{1}{3}=1$ and $\frac{1}{3}+\frac{1}{3}+\frac{1}{2}>1$. –  Beni Bogosel Sep 23 '11 at 14:10
1  
For an algorithmic solution to #2, change your arrows and equals signs to only point to the left (except CB→BC), and you have a shortlex rewriting system. It is either already confluent, or only needs one or two more rules, and then counting words is easier. Ch 12 of Holt's CGT is pretty good. –  Jack Schmidt Sep 23 '11 at 17:10

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.