MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The conjugacy problem for a free group $F_n$ on $n$ letters has an easy solution. Each element of $F_n$ is conjugate to a unique and easily computable "cyclically reduced element" (this means that if you arrange the word around a circle, then there are no cancellations), so two elements of $F_n$ are conjugate if and only if they have the same cyclically reduced conjugates.

I've been trying unsuccessfully to generalize this to solve the following problem. Let $\{x_1,\ldots,x_k\}$ and $\{y_1,\ldots,y_{k'}\}$ be two finite sets of elements of $F_n$. Let $G_x$ and $G_y$ be the subgroups of $F_n$ generated by the $x_i$ and the $y_i$, respectively. Is there an algorithm to decide if $G_x$ and $G_y$ are conjugate? Does anyone know how to do this? Thank you very much!

share|cite|improve this question
up vote 7 down vote accepted

There is an algorithm to do this. I would have thought that it was classical, but in any case an algorithm is given in: I. Kapovich and A. Myasnikov "Stallings foldings and the subgroup structure of free groups", J. Algebra 248 (2002), no 2, pp. 608-668. In the online version I found here, it is Corollary 7.8 on page 18.

share|cite|improve this answer
I fixed your link. – Andy Putman Apr 6 '10 at 20:53
Thanks very much, Andy! – Daniel Groves Apr 6 '10 at 23:05

Your Answer


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.