# 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.

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.