Decidability of conjugacy problem for finitely generated subgroups of free groups - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T18:51:38Z http://mathoverflow.net/feeds/question/20539 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20539/decidability-of-conjugacy-problem-for-finitely-generated-subgroups-of-free-groups Decidability of conjugacy problem for finitely generated subgroups of free groups Nick Hildebrand 2010-04-06T19:41:25Z 2010-04-16T16:38:14Z <p>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.</p> <p>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!</p> http://mathoverflow.net/questions/20539/decidability-of-conjugacy-problem-for-finitely-generated-subgroups-of-free-groups/20544#20544 Answer by Daniel Groves for Decidability of conjugacy problem for finitely generated subgroups of free groups Daniel Groves 2010-04-06T20:44:22Z 2010-04-06T20:53:25Z <p>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 <a href="http://www.math.uiuc.edu/~kapovich/PAPERS/gr.pdf" rel="nofollow">here</a>, it is Corollary 7.8 on page 18.</p>