2
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Incredibly helpful, thank you. $\endgroup$ – jmacmanus Apr 12 '20 at 21:27
  • 1
    $\begingroup$ Apologies, I've just come back to this and I'm having trouble with the very last step - once we replaced $u$ and $v$ with conjugates of length less than $4\delta$, why are we able to assume we have a look-up table for their conjugacy? $\endgroup$ – jmacmanus Apr 13 '20 at 0:19
  • 1
    $\begingroup$ That's an interesting question! I have added some more discussion to my answer. $\endgroup$ – Derek Holt Apr 13 '20 at 7:53
  • 1
    $\begingroup$ Thank you. Hopefully I haven't misunderstood but I suppose the obvious follow-up question is whether you think we are able to construct such a table without making use of existing solutions? I.e. using the above lemma. $\endgroup$ – jmacmanus Apr 13 '20 at 11:44
  • 2
    $\begingroup$ No, I cannot see how to use the lemma to make a lookup table for testing the conjugacy of elements of length less than $4\delta$. I don't believe that the lemma is intended to solve that problem. $\endgroup$ – Derek Holt Apr 13 '20 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.