Typical examples of relatively hyperbolic groups include Gromov hyperbolic groups, fundamental groups of finite volume real hyperbolic manifolds and groups acting properly and cocompactly on spaces with isolated flats ([HK] ). There are 5 different but equivalent definitions for relatively hyperbolic groups: one due to each of Gromov ([?] ), B. Farb ([F] ) and D. Osin ([O1] ), and two due to B. Bowditch ([B] ). We shall use B. Bowditch's definition of relatively hyperbolic groups as geometrically finite groups.

The main ingredient in our proof is B. Bowditch's theorem on the existence of an invariant collection of disjoint horoballs (see Proposition  2.2 ).

The usual way for proving uniform exponential growth is as follows: for any finite generating set $S$  of $G$  , find two elements $g_1,g_2\in G$  with word length bounded independent of $S$  , such that $<g_1,g_2>$  is free with basis $\{g_1,g_2\}$  . We shall use the same strategy. Let $G$  be a relatively hyperbolic group and $S$  a finite generating set.

For any positive integer $n$  , let $S\left(n\right)=\{g\in G:d_S(g,id)\le n\}$  . Notice that $S\left(n\right)$  is also a finite generating set of $G$  , and $S\left(n\right)\subset S\left(m\right)$  if $n\le m$  . In particular, $S\subset S\left(n\right)$  for all $n\ge 1$  .

We prove uniform exponential growth in two steps:

Step 1: There exists some positive integer $n_0$  with the following property. For any finite generating set $S$  of $G$  , $S\left(n_0\right)$  contains a hyperbolic element. See Proposition  5.1 .

Step 2: There exists some positive integer $k_0$  with the following property. If a finite generating set $S$  of $G$  contains a hyperbolic element, then there are $g_1,g_2\in S\left(k_0\right)$  such that $<g_1,g_2>$  is free with basis $\{g_1,g_2\}$  . See Corollary  3.2 and Proposition  4.1 .

Uniform exponential growth It should be noted that uniform exponential growth for geometrically finite groups acting on pinched Hadamard manifolds has been established by R. Alperin and G. Noskov ([AN] ). Some of our arguments are similar to theirs. Theorem  1.1 was conjectured by C. Drutu in [D] .

Notation: For a metric space $Y$  , any subset $A\subset Y$  and any $r\ge 0$  , we denote by $N_r\left(A\right)=\{y\in Y:d(y,A)\le r\}$  the closed $r$  -neighborhood of $A$  . For any $p,q\in Y$  , $pq$  denotes a geodesic segment between $p$  and $q$  , although it is not unique in general.

Xiangdong Xie

2 Relatively hyperbolic groups as geometrically finite groups

Here we recall the notion of geometrically finite groups and B. Bowditch's result on the existence of an invariant system of disjoint horoballs (see Proposition  2.2 ).

The reader is referred to [B] for more details.

Suppose that $M$  is a compact metrizable topological space and a group $G$  acts by homeomorphisms on $M$  . We say that $G$  is a convergence group if the induced action on the space of distinct triples is properly discontinuous. Let $G$  be a convergence group on $M$  . A point $\xi \in M$  is a conical limit point if there exists a sequence in $G$  , $\{g_n{\}}_{n=1}^{\infty }$  , and two points $\zeta \ne \eta \in M$  , such that $g_n\left(\xi \right)\to \zeta$  and $g_n\left({\xi }^{\prime }\right)\to \eta$  for all ${\xi }^{\prime }\ne \xi$  . An element $g\in G$  is a hyperbolic element if it has infinite order and fixes exactly two points in $M$  . A subgroup $H<G$  is parabolic if it is infinite, fixes a point $\xi \in M$  , and contains no hyperbolic elements. In this case, the fixed point of $H$  is unique and is referred to as a parabolic point. The nontrivial elements in a parabolic subgroup are called parabolic elements. A parabolic point $\xi$  is a bounded parabolic point if its stabilizer $Stab\left(\xi \right):=\{g\in G:g(\xi )=\xi \}$  acts properly and cocompactly on $M\backslash \left\{\xi \right\}$  . A convergence group $G$  on $M$  is a geometrically finite group if each point of $M$  is either a conical limit point or a bounded parabolic point.

Definition 2.1. A group $G$  is hyperbolic relative to a family of finitely generated subgroups $\mathcal{G}$  , if it acts properly discontinuously by isometries, on a proper geodesic hyperbolic space $X$  , such that the induced action on $\partial X$  is of convergence, geometrically finite, and such that the maximal parabolic subgroups are exactly the elements of $\mathcal{G}$  .

By definition a relatively hyperbolic group is a geometrically finite group. A. Yaman ([Y] ) proved that if $G$  is a geometrically finite group on a perfect metrizable compact space $M$  , and the maximal parabolic subgroups are finitely generated, then $G$  is hyperbolic relative to the family of maximal parabolic subgroups.

Now let $X$  be a $\delta$  -hyperbolic geodesic metric space for some $\delta \ge 0$  . Recall that each geodesic triangle in $X$  is $\delta$  -thin, that is, each edge is contained in the $\delta$  -neighborhood of the union of the other two edges. Below we shall denote by $c=c\left(\delta \right)$  a constant that depends only on $\delta$  . Let $\xi \in \partial X$  . A (not necessarily continuous) function $h:X\to \mathbb{R}$  is a horofunction about $\xi$  if there are constants $c_1=c_1\left(\delta \right)$  , $c_2=c_2\left(\delta \right)$  such that: if $x,a\in X$  and $d(a,x\xi )\le c_1$  for some geodesic ray $x\xi$  from $x$  to $\xi$  , then $\left|h\right(a)-(h\left(x\right)+d(x,a)\left)\right|\le c_2$  . A closed subset $B\subset X$  is a horoball about $\xi$  if there is a horofunction $h$  about $\xi$  and a constant $c=c\left(\delta \right)$  such that $h\left(x\right)\ge -c$  for all $x\in B$  , and $h\left(x\right)\le c$  for all $x\in X\backslash B$  . Note that $\xi$  is uniquely determined by $B$  , and we refer to it as the center of the horoball.

Proposition 2.2. (B. Bowditch, Proposition 6.13 in [B] ) Let $G$  be a relatively hyperbolic group, and $X$  a proper hyperbolic geodesic metric space that $G$  acts upon as in Definition  2.1 . Let $\Pi$  be the set of all bounded parabolic points in $\partial X$  . Then $\Pi /G$  is finite. Moreover, for any $r\ge 0$  , there is a collection of horoballs $\mathcal{ℬ}=\{B_{\xi }:\xi \in \Pi \}$  indexed by $\Pi$  with Uniform exponential growth the following properties:

(1) $\mathcal{ℬ}$  is $r$  -separated, that is, $d(B_{\xi },B_{\eta })\ge r$  for all $\xi \ne \eta \in \Pi$  ; (2) $\mathcal{ℬ}$  is $G$  -invariant, that is, $g\left(B_{\xi }\right)=B_{g\left(\xi \right)}$  for all $g\in G$  and $\xi \in \Pi$  ; (3) $Y(\mathcal{ℬ})/G$  is compact, where $Y(\mathcal{ℬ})=X\backslash {\cup }_{\xi \in \Pi }\text{int}\left(B_{\xi }\right)$  .

Xiangdong Xie

3 Axes of hyperbolic elements

In this section we study how a hyperbolic element “translates” its “axes”.

Let $G$  and $X$  be as in Definition  2.1 . That is, $X$  is a proper $\delta$  -hyperbolic geodesic space for some $\delta \ge 0$  , $G$  acts properly discontinuously by isometries on $X$  , such that the induced action on $\partial X$  is of convergence and geometrically finite.

Recall that, in a $\delta$  -hyperbolic space $X$  , any two complete geodesics that have the same endpoints in $\partial X$  have Hausdorff distance at most $2\delta$  . For a hyperbolic element $\gamma \in G$  , let ${\gamma }_{+}$  and ${\gamma }_{-}$  be the attracting and repelling fixed points of $\gamma$  in $\partial X$  respectively. We shall call any complete geodesic with ${\gamma }_{+},{\gamma }_{-}$  as endpoints an axis of $\gamma$  , and denote by $A_{\gamma }$  the union of all axes of $\gamma$  . Note that $\gamma$  may have many different axes and an axis of $\gamma$  in general is not invariant under $\gamma$  . However, for any axis $c$  of $\gamma$  , $\gamma \left(c\right)$  is also an axis of $\gamma$  and hence the Hausdorff distance between $c$  and $\gamma \left(c\right)$  is at most $2\delta$  .

Proposition  2.2 implies that there is a $200\delta$  -separated $G$  -invariant collection of horoballs $\mathcal{ℬ}$  centered at the parabolic points such that $Y(\mathcal{ℬ})/G$  is compact.

Lemma 3.1. There exists a positive integer $k_1$  with the following property: for any infinite order element $\gamma \in G$  and any $x\in Y(\mathcal{ℬ})$  , there is some $k$  , $1\le k\le k_1$  such that $d\left({\gamma }^k\right(x),x)\ge 200\delta$  .

• Proof. Notice that the action of $G$  on $Y(\mathcal{ℬ})$  is properly discontinuous and cocompact.
  It follows that there is some integer $k_1\ge 1$  such that for any $x\in Y(\mathcal{ℬ})$  , the cardinality of $\{g\in G:d(x,g\left(x\right))\le 200\delta \}$  is less than $k_1$  . In particular, for any $x\in Y(\mathcal{ℬ})$  and any infinite order element $\gamma \in G$  , there is some $k$  , $1\le k\le k_1$  such that $d\left({\gamma }^k\right(x),x)\ge 200\delta$  .

Corollary 3.2. If a finite generating set $S$  of $G$  contains a hyperbolic element, then there is a hyperbolic element $\gamma \in S\left(k_1\right)$  and some $x\in A_{\gamma }$  such that $d\left(\gamma \right(x),x)\ge 200\delta$  , where $k_1$  is the constant in Lemma  3.1 .

• Proof. Let $g\in S$  be a hyperbolic element and $c$  an axis of $g$  . It follows from the definition of a horoball that $c$  is not contained in any horoball. Since $\mathcal{ℬ}$  is a disjoint collection of horoballs and c is connected, we have $c\cap Y(\mathcal{ℬ})\ne \varnothing$  . Let $x\in c\cap Y(\mathcal{ℬ})$  .
  By Lemma  3.1 , there is some $k$  , $1\le k\le k_1$  such that $d\left(g^k\right(x),x)\ge 200\delta$  . Notice that $g^k\in S\left(k_1\right)$  is hyperbolic and $c$  is also an axis of $g^k$  .

For a complete geodesic $c$  in $X$  , we define a map $P_c:X\to c$  as follows: for any $x\in X$  , let $P_c\left(x\right)\in c$  be a point with $d(x,P_c(x\left)\right)=d(x,c)$  . Note that for any two points $x_1,x_2\in c$  with $d(x,x_1)=d(x,x_2)=d(x,c)$  , we have $d(x_1,x_2)\le 4\delta$  .

Lemma 3.3. Let $c,c^{\prime }:\mathbb{R}\to X$  be two geodesics with $c(+\infty )=c^{\prime }(+\infty )$  and $c(-\infty )=c^{\prime }(-\infty )$  . Let $a,b\in \mathbb{R}$  with $b\ge a+8\delta$  , and $a^{\prime }$  , $b^{\prime }\in \mathbb{R}$  be determined by $c^{\prime }\left(a^{\prime }\right)=P_{c^{\prime }}\left(c\right(a\left)\right)$  and $c^{\prime }\left(b^{\prime }\right)=P_{c^{\prime }}\left(c\right(b\left)\right)$  . Then $(b^{\prime }-a^{\prime })\ge (b-a)-4\delta$  .

Uniform exponential growth

• Proof. Recall that the Hausdorff distance between $c$  and $c^{\prime }$  is at most $2\delta$  . It follows from triangle inequality that $|b^{\prime }-a^{\prime }|\ge (b-a)-4\delta$  . So either $(b^{\prime }-a^{\prime })\ge (b-a)-4\delta$  or $(b^{\prime }-a^{\prime })\le -(b-a)+4\delta$  . Suppose $(b^{\prime }-a^{\prime })\le -(b-a)+4\delta$  . Let $x_i=c(b+i\delta )$  , $i=0,1,\cdots$  , and $y_i=P_{c^{\prime }}\left(x_i\right)$  . Then $y_0=c^{\prime }\left(b^{\prime }\right),y_1,\cdots ,$  is a sequence of points on $c^{\prime }$  with $d(y_i,y_{i+1})\le 5\delta$  . Since $(b^{\prime }-a^{\prime })\le -(b-a)+4\delta \le -4\delta$  and $y_i\to c(+\infty )$  , there is some $i\ge 1$  such that $d(y_i,c^{\prime }(a^{\prime }\left)\right)\le 2.5\delta$  . Triangle inequality implies that $(b+i\delta )-a=d(x_i,c(a\left)\right)\le d(x_i,y_i)+d(y_i,c^{\prime }(a^{\prime }\left)\right)+d\left(c^{\prime }\right(a^{\prime }),c(a\left)\right)\le 6.5\delta$  , contradicting the fact that $b\ge a+8\delta$  .

Lemma 3.4. Let $g\in G$  be a hyperbolic element, and $c$  an axis of $g$  .

Suppose $x\in c$  is a point with $d\left(g\right(x),x)\ge 20\delta$  . Then for any integers $i<j$  , the point $P_c\left(g^j\right(x\left)\right)$  lies between $P_c\left(g^i\right(x\left)\right)$  and $g_{+}$  .

• Proof. Denote $x_i=P_c\left(g^i\right(x\left)\right)$  . Note that $x_i\to g_{+}$  as $i\to +\infty$  . It suffices to show that for any $i$  , $x_i$  lies between $x_{i-1}$  and $x_{i+1}$  . Set $t=d\left(g\right(x),x)$  . Triangle inequality implies that $t-4\delta \le d(x_i,x_{i+1})\le t+4\delta$  . Suppose $x_i$  does not lie between $x_{i-1}$  and $x_{i+1}$  for some $i$  . Then $d(x_{i-1},x_{i+1})\le 8\delta$  and $d\left(g^{i-1}\right(x),g^{i+1}(x\left)\right)\le 12\delta$  . Since $g$  is an isometry, $d(x,g^2(x\left)\right)\le 12\delta$  . We shall show that $d(x,g^2(x\left)\right)\ge 2t-16\delta$  , which is a contradiction.
  Let $\sigma :\mathbb{R}\to X$  be the parameterization of $c$  with $\sigma \left(0\right)=x$  and $\sigma (+\infty )=g_{+}$  , $\sigma (-\infty )=g_{-}$  . Then $g\circ \sigma$  is the parameterization of $g\left(c\right)$  with $g\circ \sigma \left(0\right)=g\left(x\right)$  and $g\circ \sigma (+\infty )=g_{+}$  , $g\circ \sigma (-\infty )=g_{-}$  . Since $t-4\delta \le d(x_1,x)\le t+4\delta$  , we have $x_1=\sigma \left(b\right)$  with either $-(t+4\delta )\le b\le -(t-4\delta )$  or $t-4\delta \le b\le t+4\delta$  . We consider the case $-(t+4\delta )\le b\le -(t-4\delta )$  , the other case can be handled similarly. Let $y_1=P_c\left(g\right(x_1\left)\right)$  . Then $y_1=\sigma \left(a\right)$  for some $a\in \mathbb{R}$  . Now Lemma  3.3 applied to $\sigma$  , $g\circ \sigma$  and the projections of $g\left(x\right)$  , $g\left(x_1\right)$  onto $c$  implies that $b-a\ge 0-b-4\delta \ge t-8\delta$  .

  It follows that $d(y_1,x)=0-a\ge -b+t-8\delta \ge 2t-12\delta$  . By triangle inequality $d(x,g^2(x\left)\right)\ge d(x,y_1)-d(y_1,g(x_1\left)\right)-d\left(g\right(x_1),g^2(x\left)\right)\ge 2t-12\delta -2\delta -2\delta =2t-16\delta$  .

Lemma 3.5. Let $g\in G$  be a hyperbolic element. Suppose there is a point $x\in A_g$  with $d(x,g(x\left)\right)\ge 200\delta$  . Then $\left|d\right(y,g\left(y\right))-d(z,g\left(z\right)\left)\right|\le 40\delta$  for all $y,z\in A_g$  .

• Proof. Let $c$  be an axis of $g$  that contains $x$  . We first show $\left|d\right(y,g\left(y\right))-d(x,g\left(x\right)\left)\right|\le 16\delta$  for all $y\in c$  . Fix $y\in c$  . Denote $t=d(x,g(x\left)\right)$  , $x_i=P_c\left(g^i\right(x\left)\right)$  , $x_i^{\prime }=P_c\left(g\right(x_i\left)\right)$  and $y^{\prime }=P_c\left(g\right(y\left)\right)$  . Then $d(x_i,g^i(x\left)\right)\le 2\delta$  and $d(x_i,x_{i-1})\ge t-4\delta$  . By Lemma  3.4 there is some $i$  such that $y$  lies between $x_i$  and $x_{i+1}$  , and $x_{i+1}$  lies between $x_i$  and $g_{+}$  . Triangle inequality implies $\left|d\right(y^{\prime },x_{i-1}^{\prime })-d(y,x_{i-1}\left)\right|=\left|d\right(y^{\prime },x_{i-1}^{\prime })-d(g\left(y\right),g\left(x_{i-1}\right)\left)\right|\le 4\delta$  and $d(x_i,x_{i-1}^{\prime })\le d(x_i,g^i(x\left)\right)+d\left(g^i\right(x),g(x_{i-1}\left)\right)+d\left(g\right(x_{i-1}),x_{i-1}^{\prime }))\le 6\delta$  . It follows that $\left|d\right(y^{\prime },x_i)-d(y,x_{i-1}\left)\right|\le 10\delta$  . In particular, $d(y^{\prime },x_i)\ge d(y,x_{i-1})-10\delta =d(y,x_i)+XiangdongXied(x_i,x_{i-1})-10\delta \ge d(y,x_i)+t-4\delta -10\delta >d(y,x_i)$  . On the other hand, Lemma  3.3 applied to $g\left(c\right)$  , $c$  and the projections of $g\left(y\right)$  , $g\left(x_{i-1}\right)$  onto $c$  implies that $y^{\prime }$  lies between $x_i$  and $g_{+}$  . It now follows from $d(y^{\prime },x_i)>d(y,x_i)$  that $y$  lies between $x_i$  and $y^{\prime }$  . Now $\left|d\right(y,y^{\prime })-d(x_{i-1},x_i\left)\right|=\left|\right[d(x_i,y)+d(y,y^{\prime })]-[d(x_{i-1},x_i)+d(x_i,y)\left]\right|=\left|d\right(x_i,y^{\prime })-d(x_{i-1},y\left)\right|\le 10\delta$  . Finally $\left|d\right(y,g\left(y\right))-d(x,g\left(x\right)\left)\right|=\left|d\right(y,g\left(y\right))-d(g^{i-1}\left(x\right),g^i\left(x\right)\left)\right|\le \left|d\right(y,y^{\prime })-d(x_{i-1},x_i\left)\right|+d\left(g\right(y),y^{\prime })+d\left(g^{i-1}\right(x),x_{i-1})+d\left(g^i\right(x),x_i)\le 16\delta$  .
  Now fix any $y\in A_g$  . Set $y^{\prime }=P_c\left(y\right)\in c$  . Then $\left|d\right(y,g\left(y\right))-d(x,g\left(x\right)\left)\right|\le \left|d\right(y^{\prime },g\left(y^{\prime }\right))-d(x,g\left(x\right)\left)\right|+d(y,y^{\prime })+d\left(g\right(y^{\prime }),g(y\left)\right)\le 20\delta$  . By triangle inequality, we have $\left|d\right(y,g\left(y\right))-d(z,g\left(z\right)\left)\right|\le 40\delta$  for all $y,z\in A_g$  .

Uniform exponential growth

4 Free subgroups

The goal in this section is to find two short hyperbolic elements that generate a free group:

Proposition 4.1. Let $G$  be a relatively hyperbolic group, and $X$  a proper $\delta$  -hyperbolic geodesic metric space that $G$  acts upon as in Definition  2.1 .

Then there exists a positive integer $k_2$  with the following property. If $S$  is a finite generating set of $G$  and $s\in S$  is a hyperbolic element such that $d\left(s\right(x),x)\ge 200\delta$  for some $x\in A_s$  , then there are $g_1,g_2\in S\left(k_2\right)$  such that $<g_1,g_2>$  is free with basis $\{g_1,g_2\}$  .

Xiangdong Xie

4.1 Ping-Pong lemma

The proof of Proposition  4.1 is based on the following Ping-Pong lemma.

Lemma 4.2. Let $G$  be a group acting on a set $X$  , and $g_1$  , $g_2$  two elements of $G$  . If $X_1$  , $X_2$  are disjoint subsets of $X$  and for all $n\ne 0$  , $i\ne j$  , $g_i^n\left(X_j\right)\subset X_i$  , then the subgroup $<g_1,g_2>$  is free with basis $\{g_1,g_2\}$  .

We will apply the Ping-Pong Lemma in the following setting.

Lemma 4.3. Let $X$  be a metric space and $g_1,g_2$  isometries of $X$  . Let $B_i\subset A_i\subset X$  ( $i=1,2$  ) be subsets of $X$  , and $p_i:X\to A_i$  a map. Denote $X_i=p_i^{-1}(A_i-B_i)$  . Then the assumptions in the Ping-Pong lemma are satisfied if the following conditions hold:

(1) $X_1\cap X_2=\varnothing$  ; (2) $g_i^n\left(p_i^{-1}\right(B_i\left)\right)\subset X_i$  for all $n\ne 0$  , $i=1,2$  .

In our case, $g_i$  is a hyperbolic element, $A_i$  is an axis of $g_i$  , $B_i\subset A_i$  is a segment, and $p_i=P_{A_i}$  .

Uniform exponential growth

4.2 Two hyperbolic elements

In this section we prove Proposition  4.1 . For this, we shall find two short hyperbolic elements and segments in their axes such that the two conditions in Lemma  4.3 are satisfied.

Let $\mathcal{ℬ}$  be a fixed $200\delta$  -separated $G$  -invariant collection of horoballs centered at the parabolic points. Recall (see the proof of Lemma  3.1 ) that there is an integer $k_1\ge 1$  such that for any $x\in Y(\mathcal{ℬ})$  , the cardinality of $\{g\in G:d(x,g\left(x\right))\le 200\delta \}$  is less than $k_1$  .

Lemma 4.4. Let $g\in G$  be a hyperbolic element such that there is some $x\in A_g$  with $d(x,g(x\left)\right)\ge 200\delta$  , and $\gamma \in G$  an element such that $\left\{\gamma \right(g_{+}),\gamma (g_{-}\left)\right\}\cap \{g_{+},g_{-}\}=\varnothing$  . Let $c_1$  and $c_2$  be axes of $g$  and $h:=\gamma g{\gamma }^{-1}$  respectively. Let $a=min\{t\in \mathbb{R}:d(c_1\left(t\right),c_2)\le 2\delta \}$  and $b=max\{t\in \mathbb{R}:d(c_1\left(t\right),c_2)\le 2\delta \}$  , and denote $y=c_1\left(a\right)$  , $z=c_1\left(b\right)$  . Then $d(y,z)\le 3k_{1}d(x,g(x\left)\right)$  .

• Proof. Denote $t=d(x,g(x\left)\right)$  . Suppose $d(y,z)>3k_{1}t$  . Let $y^{\prime }=c_2\left(a^{\prime }\right)\in c_2$  , $z^{\prime }=c_2\left(b^{\prime }\right)\in c_2$  with $d(y,y^{\prime }),d(z,z^{\prime })\le 2\delta$  . It is easy to see from the $\delta$  -thin condition that the Hausdorff distance between $yz$  and $y^{\prime }{z}^{\prime }$  is at most $4\delta$  . After replacing $h$  by its inverse if necessary, we may assume $g$  and $h$  translate in the “same direction”, that is, if both $c_1$  and $c_2$  are parameterized from the repelling fixed point toward the attracting fixed point, then $b^{\prime }>a^{\prime }$  (we have $b>a$  by definition).
  Since $h$  is a conjugate of $g$  or its inverse, Lemma  3.5 implies that the inequality $\left|d\right(p,g^i\left(p\right))-d(q,h^i\left(q\right)\left)\right|\le 40\delta$  holds for all $i\ge 1$  , and all $p\in A_g$  , $q\in A_h$  . In particular, $\left|d\right(y,g^i\left(y\right))-d(y^{\prime },h^i\left(y^{\prime }\right)\left)\right|\le 40\delta$  for all $i\ge 1$  .

  For $i\ge 0$  , let $y_i=P_{c_1}\left(g^i\right(y\left)\right)$  and $y_i^{\prime }=P_{c_2}\left(h^i\right(y^{\prime }\left)\right)$  . Lemma  3.4 implies that $y_{i+1}$  lies between $y_i$  and $c_1(+\infty )$  . Since $d(y_i,y_{i+1})\le d(y,g(y\left)\right)+4\delta \le d(x,g(x\left)\right)+40\delta +4\delta \le 2t$  , we have $y_i\in yz$  for all $1\le i\le k_1$  . Similarly $y_i^{\prime }\in y^{\prime }{z}^{\prime }$  for all $1\le i\le k_1$  . Hence for $1\le i\le k_1$  there exists $z_i\in yz$  with $d(z_i,y_i^{\prime })\le 4\delta$  .

  We first assume $y\in Y(\mathcal{ℬ})$  . Triangle inequality implies $\left|d\right(y,y_i)-d(y^{\prime },y_i^{\prime }\left)\right|\le \left|d\right(y,g^i\left(y\right))-d(y^{\prime },h^i\left(y^{\prime }\right)\left)\right|+d(y_i^{\prime },h^i(y^{\prime }\left)\right)+d(y_i,g^i(y\left)\right)\le 40\delta +2\delta +2\delta =44\delta$  and $\left|d\right(y^{\prime },y_i^{\prime })-d(y,z_i\left)\right|\le d(y,y^{\prime })+d(z_i,y_i^{\prime })\le 6\delta$  . It follows that $d(y_i,z_i)=\left|d\right(y,y_i)-d(y,z_i\left)\right|\le 50\delta$  and $d\left(g^i\right(y),h^i(y^{\prime }\left)\right)\le d\left(g^i\right(y),y_i)+d(y_i,z_i)+d(z_i,y_i^{\prime })+d(y_i^{\prime },h^i(y^{\prime }\left)\right)\le 2\delta +50\delta +4\delta +2\delta =58\delta$  . Now for any $i$  , $1\le i\le k_1$  , we have $d(y,h^{-i}\circ g^i(y\left)\right)=d\left(h^i\right(y),g^i(y\left)\right)\le d\left(h^i\right(y),h^i(y^{\prime }\left)\right)+d\left(h^i\right(y^{\prime }),g^i(y\left)\right)=d(y,y^{\prime })+d\left(h^i\right(y^{\prime }),g^i(y\left)\right)\le 60\delta$  .

  Since $y\in Y(\mathcal{ℬ})$  , it follows from the definition of $k_1$  that there are $i\ne j$  , $1\le i,j\le k_1$  with $h^{-i}\circ g^i=h^{-j}\circ g^j$  . Consequently $h^{j-i}=g^{j-i}$  , contradicting the fact that $g$  and $h$  do not share any fixed points in $\partial X$  .

  Now suppose $y/\in Y(\mathcal{ℬ})$  . Since $Y(\mathcal{ℬ})$  is $G$  -invariant, $g\left(y\right)/\in Y(\mathcal{ℬ})$  . There are horoballs $B_1,B_2\in \mathcal{ℬ}$  with $y\in B_1$  and $g\left(y\right)\in B_2$  . Note $B_1\ne B_2$  , otherwise $g\left(B_1\right)=B_1$  and so $g$  fixes the center of $B_1$  , contradicting the fact that $g$  is a hyperbolic element. Since $\mathcal{ℬ}$  is $200\delta$  -separated and $d(y_1,g(y\left)\right)\le 2\delta$  , there is some $p\in c_1$  between Xiangdong Xie $y$  and $y_1$  such that $p\in Y(\mathcal{ℬ})$  . Now we run the argument from the pervious paragraph using $p$  instead of $y$  .

Remark 4.5. The proof of Lemma  4.4 actually shows that for any $\gamma \in G$  , either $\left\{\gamma \right(g_{+}),\gamma (g_{-}\left)\right\}=\{g_{+},g_{-}\}$  or $\left\{\gamma \right(g_{+}),\gamma (g_{-}\left)\right\}\cap \{g_{+},g_{-}\}=\varnothing$  holds.

Now let $S$  be a finite generating set of $G$  and suppose $s\in S$  is a hyperbolic element such that $d\left(s\right(x),x)\ge 200\delta$  for some $x\in A_s$  . If $\left\{s^{\prime }\right(s_{+}),s^{\prime }(s_{-}\left)\right\}=\{s_{+},s_{-}\}$  for all $s^{\prime }\in S$  , then $A_s$  is invariant under $G$  . In this case, $G$  is $2$  -ended and hence is virtually infinite cyclic.

We now assume there is some $\gamma \in S$  with $\left\{\gamma \right(s_{+}),\gamma (s_{-}\left)\right\}\cap \{s_{+},s_{-}\}=\varnothing$  . Let $c$  be an axis of $s$  . Set $g_1=s^{10k_1}$  and $g_2=\gamma g_1{\gamma }^{-1}$  , $A_1=c$  , $A_2=\gamma \left(c\right)$  , $p_1=P_c$  and $p_2=P_{\gamma \left(c\right)}$  . If $d(A_1,A_2)>2\delta$  , let $p\in A_1$  , $q\in A_2$  with $d(p,q)=d(A_1,A_2)$  ; in this case, let $B_1\subset A_1$  be the closed segment with midpoint $p$  and length $20\delta$  and similarly for $B_2\subset A_2$  . If $d(A_1,A_2)\le 2\delta$  , let $a=min\{t\in \mathbb{R}:d(c\left(t\right),A_2)\le 2\delta \}$  and $b=max\{t\in \mathbb{R}:d(c\left(t\right),A_2)\le 2\delta \}$  , and denote $y=c\left(a\right)$  , $z=c\left(b\right)$  ; also let $y^{\prime },z^{\prime }\in A_2$  with $d(y,y^{\prime })\le 2\delta$  and $d(z,z^{\prime })\le 2\delta$  ; in this case, let $B_1\subset A_1$  be the closed $20\delta$  -neighborhood of $yz$  in $A_1$  and $B_2\subset A_2$  be the closed $20\delta$  -neighborhood of $y^{\prime }{z}^{\prime }$  in $A_2$  . We shall show that the two conditions in Lemma  4.3 are satisfied, and hence Proposition  4.1 holds.

Lemma 4.6. Condition (2) of Lemma  4.3 is satisfied.

• Proof. We only write down the proof in the case $d(A_1,A_2)\le 2\delta$  , $i=1$  and $n>0$  , the other cases are similar or simpler.
  Let $y\in p_1^{-1}\left(B_1\right)$  . We need to show $p_1\left(g_1^n\right(y\left)\right)/\in B_1$  . Denote $z=p_1\left(y\right)$  , $y^{\prime }=g_1^n\left(y\right)$  , $z^{\prime }=g_1^n\left(z\right)$  and $y^{\prime \prime }=p_1\left(y^{\prime }\right)$  . Lemma  3.5 implies $d(z,s(z\left)\right)\ge 160\delta$  . Set $t=d(z,s(z\left)\right)$  . By Lemma  3.4 and the fact that $d\left(p_1\right(s^i\left(z\right)),p_1(s^{i+1}\left(z\right)\left)\right)\ge t-4\delta$  we obtain $d\left(p_1\right(z^{\prime }),z)\ge 10k_{1}n(t-4\delta )$  .

  Let $z^{\prime \prime }=p_1\left(z^{\prime }\right)$  . We claim $d(y^{\prime \prime },z^{\prime \prime })\le 13\delta$  . We first finish the proof assuming the claim. The claim implies $d(z,y^{\prime \prime })\ge 10k_1(t-4\delta )n-13\delta$  . Note Lemma  3.5 implies $t-4\delta \ge 2d(x,s(x\left)\right)/5$  . It follows that $d(z,y^{\prime \prime })\ge 4n{k}_{1}d(x,s(x\left)\right)-13\delta \ge 4k_{1}d(x,s(x\left)\right)-13\delta >3k_{1}d(x,s(x\left)\right)+40\delta \ge \text{length}\left(B_1\right)$  . The last inequality follows from the definition of $B_1$  and Lemma  4.4 . Since $z=p_1\left(y\right)\in B_1$  , we have $p_1\left(g_1^n\right(y\left)\right)=y^{\prime \prime }/\in B_1$  .

  We now prove the claim. We may assume $d(y^{\prime \prime },z^{\prime \prime })>3\delta$  . Fix geodesic segments $z^{\prime }{z}^{\prime \prime }$  , $y^{\prime }{z}^{\prime \prime }$  and $y^{\prime }{y}^{\prime \prime }$  . Let $p\in y^{\prime \prime }{z}^{\prime \prime }$  with $d(p,y^{\prime \prime })=3\delta$  . We use the $\delta$  -thin condition.

  Consider the geodesic triangle $\left(y^{\prime }{y}^{\prime \prime }{z}^{\prime \prime }\right)$  . There is some $q\in y^{\prime }{y}^{\prime \prime }\cup y^{\prime }{z}^{\prime \prime }$  with $d(p,q)\le \delta$  .

  If $q\in y^{\prime }{y}^{\prime \prime }$  , then $d(q,y^{\prime \prime })\ge d(p,y^{\prime \prime })-d(p,q)\ge 2\delta$  and hence $d(q,p)<d(q,y^{\prime \prime })$  , contradicting the fact that $y^{\prime \prime }=p_1\left(y^{\prime }\right)$  . So $q\in y^{\prime }{z}^{\prime \prime }$  . Now consider the geodesic triangle $\left(y^{\prime }{z}^{\prime \prime }{z}^{\prime }\right)$  . There is some $r\in z^{\prime }{z}^{\prime \prime }\cup z^{\prime }{y}^{\prime }$  with $d(q,r)\le \delta$  . If $r\in z^{\prime }{z}^{\prime \prime }$  , then $d(r,z^{\prime \prime })\le d(z^{\prime },z^{\prime \prime })\le 2\delta$  and hence $d(y^{\prime \prime },z^{\prime \prime })=d(y^{\prime \prime },p)+d(p,z^{\prime \prime })\le 3\delta +d(p,q)+d(q,r)+d(r,z^{\prime \prime })\le 7\delta$  . Suppose $r\in y^{\prime }{z}^{\prime }$  . Then $d(r,z^{\prime })=d(r,g_1^n(A_1\left)\right)\le d(r,p)+Uniformexponentialgrowthd(p,g_1^n(A_1\left)\right)\le d(r,q)+d(q,p)+2\delta \le 4\delta$  . Therefore $d(z^{\prime \prime },p)\le d(z^{\prime \prime },z^{\prime })+d(z^{\prime },r)+d(r,p)\le 8\delta$  and $d(z^{\prime \prime },y^{\prime \prime })\le 11\delta$  .

The following lemma can be proved by using approximating trees ([GhD] ). One can also prove it directly from the $\delta$  -thin condition. Since it is more or less clear, we omit its proof here.

Lemma 4.7. Condition (1) of Lemma  4.3 is satisfied.

Xiangdong Xie

5 Existence of hyperbolic elements

In this section we establish the following result, which guarantees the existence of hyperbolic elements with short word length.

Proposition 5.1. Let $G$  be an infinite relatively hyperbolic group and $X$  a $\delta$  -hyperbolic geodesic metric space that $G$  acts upon as in Definition  2.1 . Then there exists a positive integer $n_0$  with the following property:

for any finite generating set $S$  of $G$  , $S\left(n_0\right)$  contains a hyperbolic element.

For a finite set of isometries $F$  of a metric space $X$  , and $x\in X$  , we let $\lambda (x,F)=max\left\{d\right(f\left(x\right),x):f\in F\}$  . We use the following result of M. Koubi ([K] ).

Proposition 5.2. Let $X$  be a $\delta$  -hyperbolic geodesic metric space, and $G$  a group of isometries of $X$  with finite generating set $S$  . If $\lambda (x,S)>100\delta$  for all $x\in X$  , then $G$  contains a hyperbolic element $g$  such that $d_S(id,g)=1$  or $2$  .

Proposition  5.1 follows from Proposition  5.2 and the following result.

Lemma 5.3. There exists a positive integer $n_0$  with the following property. For any finite generating set $S$  of $G$  , the inequality $\lambda (x,S(n_0\left)\right)>100\delta$  holds for all $x\in X$  .

• Proof. Let $\mathcal{ℬ}$  be a $200\delta$  -separated invariant system of horoballs centered at the parabolic points. Recall that the action of $G$  on $Y(\mathcal{ℬ})$  is proper and cocompact. Let $K\subset Y(\mathcal{ℬ})$  be a compact set such that ${\cup }_{g\in G}g\left(K\right)=Y(\mathcal{ℬ})$  . Set $a=\text{diam}\left(K\right)$  and fix a point $p\in K$  . Let $A=\{g\in G:d(g\left(p\right),p)\le 2a+100\delta \}$  . Notice that $A$  is a finite set.
  Since $G$  is infinite, there is some $g_0\in G$  with $d\left(g_0\right(p),p)>100\delta +2a$  . Notice that if $A$  generates $G$  , then $$n_0:=max\left\{d_S\right(id,g_0):S\subset A\text{and}S\text{generates}G\}$$  is finite.

  Now let $S$  be a finite generating set of $G$  . Suppose there is some $x\in X$  with $\lambda (x,S)\le 100\delta$  . By the definition of $\lambda (x,S)$  , we have $d\left(s\right(x),x)\le 100\delta$  for all $s\in S$  . Recall that $\mathcal{ℬ}$  is $200\delta$  -separated. If $x\in B$  for some $B\in \mathcal{ℬ}$  , then $s\left(B\right)=B$  for all $s\in S$  and consequently the center of $B$  is fixed by the entire group $G$  , a contradiction. Hence $x\in Y(\mathcal{ℬ})$  . There is some $\gamma \in G$  with $\gamma \left(x\right)\in K$  . For $s\in S$  , we have $d(p,\gamma s{\gamma }^{-1}(p\left)\right)\le d(p,\gamma (x\left)\right)+d\left(\gamma \right(x),\gamma s(x\left)\right)+d\left(\gamma s\right(x),\gamma s{\gamma }^{-1}(p\left)\right)=d(p,\gamma (x\left)\right)+d(x,s(x\left)\right)+d\left(\gamma \right(x),p)\le 2a+100\delta$  . It follows that $\gamma S{\gamma }^{-1}:=\{\gamma s{\gamma }^{-1}:s\in S\}\subset A$  . Clearly $\gamma S{\gamma }^{-1}$  generates $G$  . There is some integer $k$  , $1\le k\le n_0$  and $s_i\in S\cup S^{-1}$  ( $1\le i\le k$  ) such that $g_0=\left(\gamma s_1{\gamma }^{-1}\right)\cdots \left(\gamma s_k{\gamma }^{-1}\right)=\gamma (s_1\cdots s_k){\gamma }^{-1}$  .

  Now $d\left({\gamma }^{-1}{g}_0\gamma \right(x),x)=d\left(g_0\gamma \right(x),\gamma (x\left)\right)\ge d\left(g_0\right(p),p)-d\left(g_0\right(p),g_0\gamma (x\left)\right)-d\left(\gamma \right(x),p)=Uniformexponentialgrowthd\left(g_0\right(p),p)-d(p,\gamma (x\left)\right)-d\left(\gamma \right(x),p)>100\delta +2a-a-a=100\delta$  . Notice ${\gamma }^{-1}{g}_0\gamma =s_1\cdots s_k\in S\left(n_0\right)$  . It follows that $\lambda (x,S(n_0\left)\right)>100\delta$  .

References

1. R. Alperin, G. Noskov, Nonvanishing of algebraic entropy for geometrically finite groups of isometries of Hadamard manifolds, preprint(2004).
2. B. Bowditch, Relatively hyperbolic groups, preprint(1999).
3. C. Drutu, Quasi-isometric rigidity of groups, preprint(2004).
4. A. Eskin, S. Mozes, H. Oh, Uniform exponential growth for linear groups, Int. Math. Res. Not. 2002, no. 31, 1675–1683.
5. B. Farb, Relatively hyperbolic groups, Geom. Funct. Anal. 8 (1998), no. 5, 810–840.
6. R. Grigorchuk, P. de la harpe, One-relator groups of exponential growth have uniformly exponential growth, translation in Math. Notes 69 (2001), no. 3-4, 575–577.
7. E. Ghys and P. de la Harpe Sur les groupes hyperboliques d'après Mikhael Gromov, Progress in Mathematics 83.
8. G. Hruska, B. Kleiner, Hadamard spaces with isolated flats, preprint(2004).
9. M. Koubi, Croissance uniforme dans les groupes hyperboliques, Ann. Inst. Fourier (Grenoble) 48 (1998), no. 5, 1441–1453.
10. D. Osin, Relatively hyperbolic groups: Intrinsic geometry, algebraic properties, and algorithmic problems, preprint(2004).
11. D. Osin The entropy of solvable groups, Ergodic Theory Dynam. Systems 23 (2003), no. 3, 907–918.
12. J. Wilson, On exponential growth and uniformly exponential growth for groups, Invent. Math. 155 (2004), no. 2, 287–303.
13. A. Yaman, A topological characterisation of relatively hyperbolic groups, J. Reine Angew. Math. 566 (2004), 41–89.