How can the following lemma be used to solve the conjugacy problem for hyperbolic groups?

Question

We are given the following lemma:

Let $G = \langle X \ | \ R\rangle $ be a $\delta$-hyperbolic group, then let $u,v \in X^\ast$ be two words such no shorter words in $X^\ast$ define the same elements, and let $w \in X^\ast$ be such that $w^{-1}uw = v$ in $G$, and $w$ is the shortest word which conjugates a cyclic shift of $u$ to a cyclic shift of $v$. Then either

1. $|w| \leq |u| + |v| + 4\delta + 2$, or

2. There exists two words $a,b \in X^\ast$ such that $|b| < 4\delta$, $|a| < |w|$ and $a^{-1}ua = b$ in $G$.

We also know that all hyperbolic groups have a solvable word problem. How can we use the above lemma to construct a solution to the conjugacy problem? That is, given any two words $w,v \in X^\ast$ decide in a finite time whether these words define conjugate elements in $G$.

I am having trouble detaching this lemma from its conditions and applying it to the conjugacy problem itself to produce a generic algorithm. Any help would be appreciated.

The source for the lemma (and exercise) is Lemma 3.14 of these lecture notes.

Thanks!

Answer 1

I don't think the statement of the lemma that you are using is strong enough to prove what you want. The second part only tells you that $|a| < |w|$, which is not very useful because the whole problem is that we are trying to bound the length of the conjugating element. But if you look at the proof of Lemma 3.14 in the lecture notes, you will see that it is actually proved that $|a| = |u| + 2\delta + 1$, which is what you need. With that modification, the following procedure works.

For all cyclic shifts $u'$ of $u$ and all cyclic shifts $v'$ of $v$ do the following.

First try all words $w$ with $|w| < |u|+|v|+4\delta+2$ and test whether any of them satisfies $w^{-1}u'w=_Gv'$. If so, you are done.

If not, then try all words $a$ with $|a| = |u| + 2\delta + 1$ and see if any of them satisfy $|a^{-1}u'a=b$ with $|b| < 4\delta$.

If both of these tests fail for all $u'$ and $v'$ then you know from the lemma that $u$ and $v$ are not conjugate.

If the second test succeeds then for some $u'$ and $v'$, then replace $u$ by its conjugate $a^{-1}u'a=b$. So we now have $|u| < 4 \delta$.

Now interchange $u$ and $v$ and repeat the above tests. Again, either we decide whether $u$ and $v$ are conjugate, or we replace $v$ by a conjugate of length less than $4\delta$.

So now we have reduced to only a finite number of possible $u$ and $v$, and we can assume that we are given a lookup table to check for their conjugacy.

The reasoning here is that there exists such a lookup table, and therefore there exists an algorithm to solve the conjugacy problem in a hyperbolic group, and therefore that problem is theoretically solvable. (That is my understanding of the situation!)

So to say that a problem is solvable means theoretically that there exists an algorithm to solve it. It does not immediately imply that we know how to describe such an algorithm - i.e. how to implement it.

In fact in the case of conjugacy and hyperbolic groups there is another method of solving the problem. Hyperbolic groups are biautomatic groups, which means that certain finite state automata associated with the groups can be constructed, and these can be used to decide conjugacy of pairs of elements in the group. The disadvantage of this method is that it has very bad complexity (probably worse than exponential), whereas the method you asked about is polynomial-time. But the method based on biautomaticity could be used to construct the lookup table that you need to implement it.