Conjugacy of finite subsets in hyperbolic groups

Martin R. Bridson and James Howie

Preprint, October 2003 --- submitted for publication.

We prove that there exists a quadratic-time algorithm that determines conjugacy between finite subsets in any torsion-free hyperbolic group. Moreover, in any $k$-generator, $\delta$-hyperbolic group $\G$, if two finite subsets $A$ and $B$ are conjugate, then $x^{-1}Ax=B$ for some $x\in\G$ with $\|x\|$ less than a linear function of $\max\{\|\g\| : \g\in A\cup B\}$. (The coefficients of this linear function depend only on $k$ and $\delta$.)

These results have implications for group-based cryptography and the width of homotopies in negatively curved spaces.

In an appendix, we construct examples of finitely presented groups in which the conjugacy problem for individual elements is soluble but the conjugacy problem for finite subsets is not.