The conjugacy problem in free solvable groups and wreath product of abelian groups is in TC${}^0$

Abstract

We show that the conjugacy problem in a wreath product $A\wr B$ is uniform-${\mathsf{TC}}^0$-Turing-reducible to the conjugacy problem in the factors $A$ and $B$ and the power problem in $B$. If $B$ is torsion free, the power problem for $B$ can be replaced by the slightly weaker cyclic submonoid membership problem for $B$. Moreover, if $A$ is abelian, the cyclic subgroup membership problem suffices, which itself is uniform-${\mathsf{AC}}^0$-many-one-reducible to the conjugacy problem in $A\wr B$. Furthermore, under certain natural conditions, we give a uniform ${\mathsf{TC}}^0$ Turing reduction from the power problem in $A\wr B$ to the power problems of $A$ and $B$. Together with our first result, this yields a uniform ${\mathsf{TC}}^0$ solution to the conjugacy problem in iterated wreath products of abelian groups - and, by the Magnus embedding, also in free solvable groups.