Shortest words in a group with finite presentation

Question

Suppose we're given a group with presentation G=, where both the generating set and the relations are finite. Given a word $w$ in the elements of $X$, I would like to know whether this word is shortest, that is whether there are no other words $w'$ with $ww'=1$ and $||w||>||w'||$. I guess this has to do with the word problem for groups. If it can help, in my specific case the group is a subgroup of the hyperbolic isometries $\mathbb{P}SL(2,\mathbb{C})$, has only two generators $x$ and $y$, and the relation is only one, i.e. the commutator is elliptic of finite order, that is $[x,y]^k=1$. Can you help me with that? Thank you.

Answer 1

It is well-known that even the problem: where $w$ has the length 1, is unsolvable.

Answer 2

It is well known that the word problem in this context is solvable.

There are several reasons for this:

1. The "bad" reason is that your group is linear and hence is residually finite. The WP is solvable for all finitely presented residually finite groups. However the algorithm is terribly inefficient.

2. A better solution is that your group $$ \langle x,y\mid [x,y]^k\rangle $$ is either abelian ($k=1$) or hyperbolic ($k\ge 2$) and the WP is solvable in polynomial time for such groups. I will now ignore the easy abelian case.

3. Even better reason is that the presentation you have satisfies a "small cancellation condition" and hence there is a very efficient and concrete algorithm due to Max Dehn to solve the WP. This is a greedy algirithm which shortens a word $w$ if possible by finding in it a subword $u$ whose length is more than half of the relator and replacing $u$ with the rest of the relator. If no such $u$ can be found then $w$ is nontrivial. (I am simplifying a bit: Instead of writing your word as a string, you have to write it on the circle so that the first and the last letters stand next to each other; you also have to keep checking for cyclic reductions and performing them if possible.) Google "Dehn algorithm" to find more details.