Saturday, 2 February 2008

gr.group theory - Decidability of conjugacy problem for finitely generated subgroups of free groups

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!

No comments:

Post a Comment