# Understanding the proof of solvable conjugacy problem for hyperbolic groups.

In the first link the theorem I am talking about is on page $$29$$, Theorem $$3.18$$. In the second link the theorem is on page $$63$$, Lemma $$6.2$$.

We want to prove that that the conjugacy problem is solvable for $$\delta$$- Hyperbolic groups. To do that we obtain a bound on $$|x|$$ where $$g_1 = xg_2 x^{-1}$$ for $$g_1,g_2 \in G$$. The argument starts in both cases by claiming that if $$x$$ is a minimal $$x$$ such that $$g_1 = xg_2 x^{-1}$$ with $$x= y_1...y_n$$, and all $$y_i$$ are generators, and we let $$x_i = y_1...y_i$$, then $$|x_ig_1x_i^{-1}| \leq 2\delta +|g_1|$$ for $$|g_1| < i \leq n-|g_2|$$. I do not understand where this comes from. It probably comes from using $$\delta$$ thinness on suitably chosen triangles as hinted in the first link, but I do not understand how we can bound $$|x_i|$$ at all. The range for $$i$$ also remains a mystery to me. Further clarifications on this proof would be appreciated as maybe then I would be able to complete the proof.

My understanding of $$\delta$$ thinness here, is that given any triangle and given any point on one side, there is a point on the other edges that's at least '$$\delta$$ close the first point. I'm not sure how that translates in terms of words and generators on the Cayleh graph.

## 1 Answer

Consider the geodesic quadrangle in the Cayley graph with two "vertical sides" and two horizontal sides labelled $$x, g_1, x^{-1}, g_2^{-1}$$, the ("horizontal") sides $$g_1,g_2$$ are much shorter than the "vertical" sides labelled by $$x$$ because we assume, by contradiction, that there is no algorithm to find $$x$$ given $$g_1,g_2$$. We can also, as you noted, assume that $$x$$ is the shortest possible. Then each side is in a union of $$2\delta$$-neighborhoods of the other three sides (divide the quadrangle by a diagonal). The intersections of $$2\delta$$ neighborhoods of the short sides with the left vertical side are small. Therefore a large portion of the left side is in a $$2\delta$$-neighborhood of the right vertical side. That means for most $$i$$ $$x_ig_1x_i^{-1}$$ has length at most $$d=2\delta(1+|g_1|+|g_2|)$$. Here $$x_i$$ is the suffix of $$x$$ of length $$i$$. The length of $$x$$ can be assumed to be $$\ge \exp(d)$$, so for some $$i we have $$x_ig_1x_i=x_jg_1x_j$$. But that implies, we can cut the subword between $$x_i$$ and $$x_j$$ from $$x$$ and still get a (shorter) conjugator $$x'$$, a contradiction.