Conjugacy problem in hyperbolic groups: pigeonhole principle I am trying to understand the proof of the conjugacy problem for hyperbolic groups: see
http://andreghenriques.com/Teaching/GeometricGroupTheory.pdf Lemma 6.2
https://www.math.ucdavis.edu/~kapovich/280-2009/hyplectures_papasoglu.pdf 3.28
I know this has been discussed before but could someone please explain, preferably with some clear pictures, the pigeonhole principle step of the argument. I understand the construction up to there, I just can't see how we can assume there exists $i<j$ where we can make the $x$ shorter.  I'm sure this is meant to be straightforward but I'm just not getting it, no matter how many pictures I draw! Any help would be greatly appreciated :)
 A: I am looking at the proof of Lemma 6.2 in Papasoglu's paper.
From what you write, it sounds as though you understand the first claim, that
$$ |(x_1\cdots x_i)^{-1}g(x_1\cdots x_i)| \le 2\delta + |g_1|$$
for all $i$ with $|g_1| \le i \le n-|g_2|$.
Now a group element $g$ of length $k$ has an expression as $y_1 \cdots y_k$ with each $y_i \in S \cup S^{-1}$, and so the number of such elements is at most $(2|S|)^k$, and the number of elements of length at most $k$ is at most $(2|S|+1)^k$. (I think there might be a minor mistake in the paper, because we need to replace $2|S|$ by $2|S|+1$, or make some similar adjustment.)
So, if $|x| \ge (2|S|+1)^{2\delta + |g_1|} + |g_1|+|g_2|+1$, then there are at least
$(2|S|+1)^{2\delta + |g_1|} +1$ values of $i$ with $|g_1| \le i \le n-|g_2|$, and hence there must be two such values, which the author calls $i$ and $j$ with $i<j$, such that
$$ (x_1\cdots x_i)^{-1}g(x_1\cdots x_i) = (x_1\cdots x_j)^{-1}g(x_1\cdots x_j).$$ Hence
$$g_2 = x^{-1}g_1x = (x_1\cdots x_n)^{-1}g(x_1\cdots x_n) = (x_1\cdots x_ix_{j+1} \cdots x_n)^{-1}g(x_1\cdots x_ix_{j+1} \cdots x_n)$$
as claimed.
