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.

  • $\begingroup$ You mean $w = w'$, not $ww' = 1$, right? $\endgroup$ – hunter Nov 20 '13 at 18:09
  • $\begingroup$ @hunter the conditions are equivalent because a shortest word will have the same length as its shortest inverse. $\endgroup$ – Dan Rust Nov 20 '13 at 18:20

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 $$ <x,y| [x,y]^k> $$ 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.

  • $\begingroup$ Thank you very much. I think I solved my problem in an easier way (just because my case was even more specific than what I explained) but still I got to learn something more thanks to your answer! $\endgroup$ – fatoddsun Nov 21 '13 at 11:39

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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