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!


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.

  • $\begingroup$ I fixed your link. $\endgroup$ – Andy Putman Apr 6 '10 at 20:53

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.