Extension of conjugacy problem

Question

Let $F = \langle a,b \rangle$ be a non-abelian free group.

Question: Is there an algorithm that takes as input $x,y,z \in F$ and answers the question whether $x$ is a product of conjugates of $y$ and $z$, i.e. whether there exists $g,h \in F$ with $$ x = gyg^{-1} \cdot hzh^{-1} ?$$

It is obvious that there exists an algorithm that enumerates all products of conjugates of $y$ and $z$. What is missing is a certificate that $x$ cannot be written in this form. Sometimes (like in the case of the word problem or the membership problem for finitely generated subgroups), this part is done by looking at the finite quotients and finding one finite quotient so that $x$ is not in the product of the conjugacy classes. Hence, one starting point would be to ask if the product of conjugacy classes is closed in the pro-finite topology. This was conjectured by Stallings to hold even in the pro-p topology and disproved (in the pro-p case) by Howie in

The p-adic Topology on a Free Group: A Counterexample, Math. Z. 187,25-27 (1984)

It might hold in the pro-finite topology, but this seems to be difficult. Anyhow, I am just looking for an algorithm, maybe this can be done without looking at the finite quotients.

Answer 1

Yes, it is an equation in the free group. There exists an algorithm solving any equation due to Makanin, Makanin, G. S. Equations in a free group. Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 6, 1199–1273.

Answer 2

Andreas, I believe so, and for free groups with more than 2 generators too. As well as the analogous question for more than 3 elements: for example, if $w=fxf^{-1}gyg^{-1}hzh^{-1}$.

To see if $x=gyg^{-1}hzh^{-1}$, it is enough to study first the cases $x=1$, $y=1$, $z=1$, and if none of these elements is trivial, to see if it is possible to "glue" a sphere out of 3 discs labelled on the boundary with $x$, $y$, and $z$, respecting the labels, and so that the orientations of the discs labelled with $y$ and $z$ were the same, and the orientation of the disc labelled with $x$ was the inverse.

The length of the $1$-skeleton of such a sphere will be $(|x|+|y|+|z|)/2$, so there are finitely many cases to consider.

More details.

If such a "sphere" (more properly it would be called a "combinatorial sphere") glued of 3 faces exists, it is more or less clear that $x$ is the product of a conjugate of $y$ and a conjugate of $z$.

Suppose now $x=gyg^{-1}hzh^{-1}$. Then it is possible to use 3 faces with contour labels $x$, $y$, and $z$, and additional "degenerate" faces with contour labels "$a1a^{-1}1$", "$b1b^{-1}1$", "$a1a^{-1}$", "$b1b^{-1}$", "$a^{-1}1a$", "$b^{-1}1b$", "$111$" to glue a "big" sphere as above, except with additional "degenerate" faces.

Then it is possible to "collapse" all edges labelled with "1". The sphere will "fall apart" into several spheres. Assuming that none of the words $x$, $y$, $z$ is trivial, none of the 3 "essential" faces can be left on its own, so all 3 will be in the same smaller sphere. Other faces in this smaller sphere will be digons with contour labels "$aa^{-1}$" and "$bb^{-1}$". It is possible to "eliminate" these bigons one by one, leaving a sphere with only 3 faces as desired.

Remark.

Alternatively to combinatorial complexes, you can think in terms of pictures in the sense of Rourke, as in

1. Colin P. Rourke, Presentations and the trivial group, Topology of low-dimensional manifolds (Berlin), Lecture Notes in Math., vol. 722, Springer, 1979, Proc. Second Sussex Conf., Chelwood Gate, 1977, pp. 134–143.

2. Johannes Huebschmann, Aspherical 2-complexes and an unsettled problem of J. H. C. Whitehead, Math. Ann. 258 (1981), 17–37.