Random walks on groups and superlinear-divergent geodesics

Abstract

In this paper, we study random walks on groups that contain superlinear-divergent geodesics, in the line of thoughts of Goldsborough and Sisto. The existence of a superlinear-divergent geodesic is a quasi-isometry invariant which allows us to execute Gouëzel’s pivoting technique. We develop the theory of superlinear divergence and establish a central limit theorem for random walks on these groups.

1 Introduction

Classical limit laws in probability theory concern the asymptotic behaviour of the random variable (RV)

$$ \begin{align*}Z_{n} = \xi_{1} + \xi_{2} + \cdots+ \xi_{n}. \end{align*} $$

for independent and identically distributed (i.i.d.) random variables $\xi _{1}, \xi _{2}, \ldots $ on $\mathbb {R}$ . As a non-commuting counterpart, Bellman, Furstenberg and Kesten initiated the study of random walks on a matrix group G [Bel54, Kes59, FK60, Fur63]. Given a probability measure $\mu $ on G, the random walk generated by $\mu $ is a Markov chain on G with transition probabilities $p(x, y) := \mu (x^{-1}y)$ . Our goal is to understand the nth step distribution

$$ \begin{align*} Z_n = g_1 \cdots g_n, \end{align*} $$

where $g_i$ are independent random variables distributed according to $\mu $ .

There are several generalizations of Bellman, Furstenberg and Kesten’s theory of non-commuting random walks: random walks on Lie groups (cf. [BQ16] and the references therein) and random conformal dynamics [DK07] to name a few. In geometric group theory, there is a strong analogy between rank-1 Lie groups and groups with a non-elementary action on a Gromov hyperbolic space X [MT18]. Given a basepoint $o \in X$ , the sample path $(Z_{n} o)_{n \geq 0}$ on X tracks a geodesic and the displacement $d(o, Z_{n} o)$ at step n grows like a sum of i.i.d. random variables with positive expectation. From this, one can derive a number of consequences, such as exponential bounds on the drift [BMSS23, Gou22], limit laws [KM99, Bjö10, GS21, Gou17, Hor18] and identification of the Poisson boundary [MT18, Kai00, CFFT22]. If the G-action on X is compatible with the geometry of G in a suitable sense, one can transfer these results on X to G. One of the most successful results in this direction is due to Mathieu and Sisto [MS20], who proved a central limit theorem (CLT) for random walks on acylindrically hyperbolic groups. We refer the readers to [BHS19, Osi16] for examples of acylindrically hyperbolic groups and hierarchically hyperbolic groups.

Although the notion of acylindrical hyperbolicity captures a wide range of discrete groups, acylindrical hyperbolicity of a group is not known to be quasi-isometry (QI) invariant or even commensurability invariant. This is because there is no known natural way to transfer a group action through a quasi-isometry. To overcome this, the second author proposed a theory for random walks using a group-theoretic property that does not involve hyperbolic actions, namely, possessing a strongly contracting element [Cho22]. Nevertheless, this theory is still not invariant under quasi-isometry.

Meanwhile, certain hyperbolic-like properties are known to be quasi-isometry invariant, such as the existence of a Morse quasi-geodesic. Hence, one can expect that many consequences of hyperbolicity should hold under quasi-isometry invariant assumptions. To address this, Goldsborough and Sisto [GS21] developed a QI-invariant random walk theory for groups. Given a bijective quasi-isometry f from a group H to a group G, the pushforward of the random walk from H to G is not necessarily a random walk, but only an inhomogeneous Markov chain. Nonetheless, if one—equivalently both—groups are non-amenable, the induced Markov chain satisfies some sort of irreducibility, which the authors call tameness. At this moment, Goldsborough and Sisto require that G acts on a hyperbolic space X and contains what they call a ‘superlinear-divergent’ element g, that is, any path must spend a superlinear amount of time to deviate from the axis of g (see §2 for the definition). Goldsborough and Sisto observed that along a random path arising from a tame Markov chain on G, some translates of the superlinear-divergent axis are aligned on X. Such alignment is also realized on the Cayley graph of G, and subsequently on H. As a consequence, they established a central limit theorem for random walks on H, which is only quasi-isometric to G.

In the setting of Goldsborough and Sisto, still, G is required to possess an action on a hyperbolic space. Our purpose is to remove this assumption and establish a central limit theorem for groups satisfying a QI-invariant property, without referring to a hyperbolic space. Our main result describes the growth of the word norm $|Z_{n}|$ of a random element $Z_{n}$ picked by a simple random walk on G.

Theorem A. Let G be a finitely generated group with exponential growth, and suppose that G has a superlinear-divergent quasi-geodesic $\gamma : {\mathbb {Z}} \rightarrow G$ . Let $(Z_n)_{n\geq 1}$ be a simple random walk on G. Then there exist constants $\unicode{x3bb} , \sigma \geq 0$ such that

$$ \begin{align*}\frac{|Z_{n}|-\unicode{x3bb} n}{ \sqrt{n}} \rightarrow \mathcal{N}(0, \sigma^{2}) \quad \textit{in distribution}. \end{align*} $$

Note that we only assume existence of a superlinear-divergent quasi-geodesic, as opposed to a superlinear-divergent element. This makes our setting invariant under quasi-isometry; see Lemma 2.2. In addition, our proof only uses the classical theory of random walks and does not refer to tame Markov chains.

Theorem A does not exclude the possibility that the limiting Gaussian distribution is degenerate. To address this, Mathieu and Sisto give a sufficient criterion [MS20, Theorem 4.12] for positivity of the limiting variance. By using a variant of their criterion, we show that the constants $\unicode{x3bb} $ and $\sigma $ in Theorem A are strictly positive when G is non-amenable, and the random walk under consideration is simple and symmetric (see §4.3).

This theorem applies to groups that are not flat but not of rank 1 either. For example, we can construct a superlinear-divergent element in any right-angled Coxeter group (RACG) that contains a periodic geodesic with geodesic divergence at least $r^3$ .

Proposition 1.1. Let $W_{\Gamma }$ be a right-angled Coxeter group of thickness $k\geq 2$ . Then, any Cayley graph of $W_\Gamma $ contains a periodic geodesic $\sigma $ which is $(f, \theta )$ -divergent for some $\theta>0$ and $f(r) \gtrsim r^k$ . In particular, simple random walks on $W_\Gamma $ satisfy the central limit theorem.

By $f(r) \gtrsim r^k$ , we mean that $f(r)\geq cr^k$ for some sufficiently small $c> 0$ and r sufficiently large. The proof of this proposition is Appendix A. Such RACGs can be produced following the method in [BHS17, Lev22] that shows there is an abundance of such groups. The recent paper of Behrstock, Çiçeksiz and Falgas-Ravry [BCF24, Theorem 1.2] provides a range of parameters for which the RACG on the corresponding Erdős–Renyi random graph $\Gamma $ has thickness exactly 2 asymptotically almost surely.

Lastly, let us mention the relationship between superlinear divergence and the strongly contracting property, which is a core ingredient of the second author’s previous work [Cho22]. In general, a superlinear-divergent axis need not be strongly contracting and vice versa. Hence, the present theory and the theory in [Cho22] are logically independent. We elaborate this independence in Appendix B.

1.1 Outline of the paper

Our main idea is to bring Gouëzel’s recent theory of pivotal time construction for random walks [Gou22]. Here, the key ingredient is a local-to-global principle for alignments between quasigeodesics. Lacking Gromov hyperbolicity of the ambient group, we establish such a principle among sufficiently long superlinear-divergent geodesics (Proposition 3.3). For this purpose, in §2, we continue to develop the theory of superlinear-divergent sets after Goldsborough and Sisto [GS21]. In §3, we discuss alignment of superlinear-divergent geodesics. In §4, we estimate the probability for alignment to happen during a random walk. This yields a deviation inequality (Lemma 4.7) that leads to the desired central limit theorem.

2 Superlinear-divergence

For this section, let X be a geodesic metric space. For points $x,y \in X$ , we will use the notation $[x, y]$ to mean an arbitrary geodesic between x and y (which may not be unique in general). For a quasi-geodesic $\alpha $ with points $x,y \in \alpha $ , we use $[x, y]|_\alpha $ to denote the quasi-geodesic segment from x to y along $\alpha $ . Throughout, all paths are continuous maps from an interval into X.

We adopt the definition in [GS21]. For a set $Z \subseteq X$ and constants $A, B> 0$ , we say a map $\pi = \pi _{Z} : X \rightarrow Z$ is an $(A, B)$ -coarsely Lipschitz projection if

$$ \begin{align*} \text{for all } x, y \in X, \quad d(\pi(x), \pi(y)) \le A d(x, y) + B \end{align*} $$

and

$$ \begin{align*} \text{for all } z \in Z, \quad d(\pi(z),z) \leq B. \end{align*} $$

We say that a map $\pi $ is coarsely Lipschitz if it is $(A,B)$ -coarsely Lipschitz for some $A,B>0$ . Note that a coarsely Lipschitz projection is comparable to the closest point projection: for any $x \in X$ , we have

(2.1) $$ \begin{align} d(x, \pi(x)) &\le \inf_{z \in Z} ( d(x, z) + d(z, \pi(z)) + d(\pi(z), \pi(x))) \nonumber \\ &\le \inf_{z \in Z} ( d(x, z) + B + (Ad(x,z)+B) ) \nonumber \\ &\le (A+1) d(x, Z) + 2B. \end{align} $$

We say that a function $f : \mathbb {R}_{+} \rightarrow \mathbb {R}_{+}$ is superlinear if it is convex, increasing and

$$ \begin{align*} \lim_{x \to \infty}\frac{f(x)}{x} = \infty. \end{align*} $$

Definition 2.1. (Cf. [GS21, Definition 3.1])

Let Z be a closed subset of a geodesic metric space X, let $\theta> 0$ and let $f : \mathbb {R}_{+} \rightarrow \mathbb {R}_{+}$ be superlinear. We say that Z is $(f,\theta )$ -divergent if there exists a coarsely Lipschitz projection $\pi _{Z} : X \rightarrow Z$ such that for any $R>0$ and any path p outside of the R-neighbourhood of Z, if the endpoints $p_{-}$ and $p_{+}$ of the path p satisfy

$$ \begin{align*} d(\pi_{Z}(p_{-}),\pi_{Z}(p_{+}))> \theta, \end{align*} $$

then the length of p is at least $f(R)$ .

We say that Z is superlinear divergent if it is $(f,\theta )$ -divergent for some constant $\theta> 0$ , for some coarsely Lipschitz projection $\pi _{Z}$ and for a superlinear function $f : \mathbb {R}_{+} \rightarrow \mathbb {R}_{+}$ .

The following lemma shows that the existence of a superlinear-divergent quasi-geodesic in a group G is a quasi-isometry invariance.

Lemma 2.2. Let X and Y be geodesic metric spaces where X contains a superlinear- divergent subset Z, and let $\phi :X\to Y$ be a quasi-isometry. Then, $\phi (Z)$ is also superlinear divergent.

Proof. Let $Z \subset X$ be $(f,\theta )$ -divergent with a coarsely Lipschitz projection $\pi _{Z}$ (albeit with potentially different constants). Let $\phi :X\to Y$ be a $(q,Q)$ -quasi-isometry. Then $\pi _Z$ pushes forward to a coarsely Lipschitz projection $\pi _{\phi (Z)} = \phi \circ \pi _Z \circ \phi ^{-1}$ . Here, $\phi ^{-1}$ is a quasi-inverse to $\phi $ , that is to say, a map $\phi ^{-1}: Y \to X$ such that $\sup _{x\in X} d_X (x, \phi ^{-1}(\phi (x))) < \infty $ .

Note that the image under $\phi ^{-1}$ of a continuous path in Y may not be a continuous path in X. However, by the taming quasi-geodesics lemma [BH99, Lemma III.H.1.11], we can find a continuous path within the $(q+Q)$ -neighbourhood of $\phi ^{-1}(p)$ with the same endpoints.

Fix $R>0$ . Suppose p is a path in Y outside of an R-neighbourhood of $\phi (Z)$ , and suppose the endpoints $p_-$ and $p_+$ satisfy

$$ \begin{align*} d(\pi_{\phi(Z)}(p_-),\pi_{\phi(Z)}(p_+))>\theta', \end{align*} $$

where $\theta ' = q \theta + Q$ . Then, let $p'$ be a continuous path in the $(q+Q)$ -neighbourhood of $\phi ^{-1}(p)$ with endpoints $p^{\prime }_{-} \in \phi ^{-1}(p_{-})$ and $p^{\prime }_{+} \in \phi ^{-1}(p_+)$ . It follows that $p'$ is outside of the $({R}/{q}-q-2Q)$ -neighbourhood of Z. Moreover, the endpoints have projections bounded by

$$ \begin{align*} d_{Z}(\pi_{Z}(p^{\prime}_-),\pi_{Z}(p^{\prime}_+))>\theta. \end{align*} $$

Superlinear divergence of Z lets us conclude that

$$ \begin{align*} l_{X}(p')> f \bigg(\frac{R}{q}-q-2Q\bigg), \end{align*} $$

so $l_{Y}(p)> g(d)$ , where

$$ \begin{align*} g(x) = \frac{1}{q}f \bigg(\frac{x}{q}-q-2Q \bigg)-Q \end{align*} $$

is a superlinear function.

Corollary 2.3. Suppose a finitely generated group G contains a superlinear-divergent bi-infinite quasi-geodesic $\gamma : {\mathbb {R}} \rightarrow G$ . Let H be a finitely generated group quasi-isometric to G. Then, H also contains a superlinear-divergent bi-infinite quasi-geodesic.

We now establish basic consequences of superlinear divergence of a geodesic. In part, superlinear-divergent geodesics are ‘constricting’ (in the sense of [ACT15, Sis18]) up to a logarithmic error. This will be formulated more precisely in Lemma 2.6.

Lemma 2.4. For each superlinear function f and positive constants $A, B, K, \theta , q, Q$ , there exists a constant $K_{0}>1$ such that the following holds.

Let Z be an $(f, \theta )$ -divergent subset of X with respect to an $(A, B)$ -coarsely Lipschitz projection $\pi _{Z}$ . Let $ M>0 $ be a positive constant and let $\alpha : [0, M] \rightarrow X$ be a geodesic in X such that

$$ \begin{align*} d(\pi_{Z}\alpha(0), \pi_{Z}\alpha(M)) \ge \theta \quad\text{and}\quad d(\alpha(0), Z)> K_{0}. \end{align*} $$

Then there exists $t \in [0,M]$ such that

$$ \begin{align*} d(\pi_{Z}\alpha(0), \pi_{Z}\alpha(t)) \le \theta+B, \end{align*} $$

and either

$$ \begin{align*} d(\alpha(t), Z) \ge K \cdot d(\alpha(0), Z) \quad\text{or}\quad d(\alpha(t), Z) \le \frac 1K \cdot d(\alpha(0), Z). \end{align*} $$

Proof. Let $A,B$ be the coarsely Lipschitz constants of $\pi _Z$ . Choose $K'>1$ large enough such that for all $t> K'$ ,

$$ \begin{align*} \frac{f(t)}{t} \ge K(K+5B+\theta+1)(A+1). \end{align*} $$

Let

$$ \begin{align*} \tau := \inf \{t \in [0,M]: d(\pi_{Z}\alpha(0), \pi_{Z}\alpha(t)) \ge \theta\}. \end{align*} $$

By the $(A, B)$ -coarse Lipschitzness of $\pi _{Z}$ , we have

$$ \begin{align*} d(\pi_{Z}\alpha(0), \pi_{Z}\alpha(t)) \le \theta+B \end{align*} $$

for all $t \in [0, \tau ]$ . We now take $K_{0} = K'K$ . For convenience, let $d_{t} := d(\alpha (t), Z)$ for each t. The desired conclusion holds if $d_{t} \le d_{0}/K = K'$ for some $t \in [0, \tau ]$ ; suppose not. Under this assumption, we show that $d_\tau> Kd_0$ . By superlinear divergence of Z,

$$ \begin{align*} l(\alpha([0, \tau])){\kern-1pt} \ge{\kern-1pt} f\bigg({\kern-1pt} \frac{d_{0}}{K}{\kern-1pt}\bigg) {\kern-1pt}\ge{\kern-1pt} K(K{\kern-1pt}+{\kern-1pt}5B{\kern-1pt}+{\kern-1pt}\theta{\kern-1pt}+{\kern-1pt}1)(A{\kern-1pt}+{\kern-1pt}1) \cdot \bigg({\kern-1pt}\frac{d_{0}}{K}{\kern-1pt}\bigg) {\kern-1pt}\ge{\kern-1pt} (K{\kern-1pt}+{\kern-1pt}5B{\kern-1pt}+{\kern-1pt}\theta{\kern-1pt}+{\kern-1pt}1)(A{\kern-1pt}+{\kern-1pt}1) d_{0}. \end{align*} $$

Using inequality (2.1) and the fact that $\alpha $ is a geodesic, we observe that

$$ \begin{align*}\begin{aligned} l(\alpha([0,\tau])) &\le d(\alpha(0), \pi_{Z}(\alpha(0))) + d(\pi_{Z}(\alpha(0)), \pi_{Z}(\alpha(\tau))) + d(\pi_{Z}(\alpha(\tau)), \alpha(\tau))\\ &\le ((A+1) d_{0} + 2B) + (\theta+B) + [(A+1) d_{\tau} + 2B]. \end{aligned} \end{align*} $$

Combining these, we have

$$ \begin{align*} d_{\tau} &\ge \frac{1}{A+1}[(K+5B+\theta+1)(A+1) d_{0} -5B-(A+1)d_0 - \theta]\\ &\ge K d_{0} + (5B+ \theta) \bigg(d_0-\frac{1}{A+1} \bigg)\\ &\ge K d_{0}, \end{align*} $$

where the final inequality is due to $d_{0} \ge K_{0} = KK'> 1 > 1/(A+1)$ .

The following lemma is a technical calculation that will be used in the proof of Lemma 2.6 to examine the behaviour of a sequence of points along a geodesic whose projections are making steady progress.

Lemma 2.5. Let $\pi _Z : X \rightarrow Z$ be an $(A, B)$ -coarsely Lipschitz projection onto a subset Z of X and let $K>0$ . Suppose that points $x, z \in X$ and a point $y \in [x, z]$ satisfy

$$ \begin{align*} \begin{aligned} d(\pi_{Z}(x), \pi_{Z}(y)) &<K, \\ d(\pi_{Z}(y), \pi_{Z}(z)) &< K \text{ and} \\ d(x, Z),\, d(z, Z) &\le \frac{1}{8(A+1)} d(y, Z). \end{aligned} \end{align*} $$

Then, we have $d(y, Z) \le 2K + 16B$ .

Proof. Suppose in contrast that $d(y, Z)> 2K + 16B$ . First, the assumption together with inequality (2.1) tells us that

$$ \begin{align*} (A+1) d(x, Z) + 2B \le \tfrac{1}{8} d(y, Z) + 2B \le \tfrac{1}{4} d(y, Z). \end{align*} $$

This forces

$$ \begin{align*} d(x, y) \ge d(y, \pi_{Z}(x)) - d(x, \pi_{Z}(x)) \ge d(y, Z) - (A+1)d(x, Z) - 2B \ge \frac{3}{4} d(y, Z) \end{align*} $$

and similarly $d(y, z) \ge \tfrac 34 d(y, Z)$ , which leads to

(2.2) $$ \begin{align} d(x, z) = d(x, y) + d(y, z) \ge \tfrac{3}{2}d(y, Z). \end{align} $$

Meanwhile, note that

(2.3) $$ \begin{align} &d(x, z)\nonumber\\&\quad\le d(x, \pi_{Z}(x)) + d(\pi_{Z}(x), \pi_{Z}(z)) + d(\pi_{Z}(z), z) & \!(\because \mathrm{triangle inequality})\nonumber\\&\quad\le (A+1) d(x, Z) + d(\pi_{Z}(x), \pi_{Z}(z)) +(A+1) d(z, Z) + 4B & \!(\because \mathrm{inequality~(2.1)}) \nonumber\\&\quad\le \tfrac{1}{4}d(y, Z) + 4B + 2K & \!(\because \mathrm{the assumption}) \nonumber\\&\quad\le \tfrac{1}{2}d(y, Z) + 2K. & \!(\because \mathrm{the assumption}) \end{align} $$

Combining equations (2.2) and (2.3), we have

$$ \begin{align*}\tfrac{3}{2}d(y, Z) \le \tfrac{1}{2}d(y, Z) + 2K,\end{align*} $$

which contradicts the assumption.

The following is the main lemma.

Lemma 2.6. Let Z be an $(f, \theta )$ -divergent subset of X. Then, for any $\delta>0$ , there exists $K_1 = K_1(\delta , f,\theta )> 0$ such that the following holds. For any $x, y \in X$ , if

$$ \begin{align*} d(\pi_{Z}(x), \pi_{Z}(y))> \delta (\log d(x, Z) + \log d(y, Z)) + K_{1}, \end{align*} $$

then there exist a subsegment $[p_{x}, p_{y}]$ of $[x, y]$ and points $q_{x}, q_{y} \in Z$ such that:

1. (1) $d(p_x, q_x), d(p_y, q_y) < K_1$ ;

2. (2) $d(q_{x}, \pi _{Z}(x)) \le \delta \log d(x, Z) + K_{1}$ ;

3. (3) $d(q_{y}, \pi _{Z}(y)) \le \delta \log d(y, Z) + K_{1}$ ;

4. (4) the segment $[p_x, p_y]$ is in the $K_{1}$ -neighbourhood of Z.

Roughly speaking, parts (1), (2) and (3) state that the geodesic $[x,y]$ will approach the $K_1$ -neighbourhood of Z exponentially (with respect to the progress made by its projection along Z) from both sides, and part (4) states that it stays near Z in the middle (see Figure 1).

Proof. Let $(A, B)$ be the coarsely Lipschitz constants for $\pi _{Z}$ . Let $K' = 8(A+1) + \operatorname {exp}(({\theta + B})/{\delta })$ , let $K" = K_{0}(K') + 2K + 16B$ where $K_{0}(K')$ is as in Lemma 2.4 and let

$$ \begin{align*} K_{1} = (2A+3)(K" + 2\theta + 4B) + 5B + \theta + \log K'. \end{align*} $$

If $[x, y]$ entirely lies in the $(K" + 2\theta + 4B)$ -neighbourhood of Z, we can take $p_{x} = x$ , $p_{y} = y$ , $q_{x} = \pi _{Z}(x)$ and $q_{y} = \pi _{Z}(y)$ .

Figure 1 A geodesics whose endpoints project sufficiently far apart onto a superlinear-divergent set Z must enter and exit a small neighbourhood of Z near the projections.

If not, we analyse the subsegments of $[x,y]$ outside of the $(K" + 2\theta + 4B)$ - neighbourhood of Z. Fix an arbitrary connected component $[x', y']$ of

$$ \begin{align*}[x, y] \setminus N_{K" + 2\theta + 4B} (Z) := \{ p \in [x, y]: d(p, Z) \ge K" + 2\theta + 4B\}. \end{align*} $$

We will take a sequence of points $\{x_{i}\}_{i=0, 1, 2, \ldots }$ on $[x', y']$ , associated with a sequence of real numbers $\{r_{i} := d(x_i,Z)\}_{i=0,\ldots ,M}$ for some $M \in \mathbb {N}$ (Figure 1). We construct the sequence recursively. Start by choosing $x_{0} := x'$ , then recursively choose $x_{i+1} \in [x_{i}, y']$ such that

$$ \begin{align*} d(\pi_{Z}(x_{i}), \,\pi_{Z}(x_{i+1})) \le \theta + B \end{align*} $$

and either

(2.4) $$ \begin{align} r_{i+1} \ge K'r_{i} \quad\text{or}\quad r_{i+1} \le r_{i}/K'. \end{align} $$

Such $x_{i+1}$ must exist when $d(\pi _{Z}(x_{i}), \pi _{Z}(y')) \geq \theta + B$ , due to Lemma 2.4. We stop the process at step M when $d(\pi _{Z}(x_M), \pi _{Z}(y')) <\theta + B$ . By inequality (2.4), for each i, we have

$$ \begin{align*} d(x_{i}, x_{i+1}) {\kern-1pt}\ge{\kern-1pt} |d(x_{i}, Z) - d(x_{i+1}, Z)| {\kern-1pt}\ge{\kern-1pt} (K'{\kern-1pt}-{\kern-1pt}1) \min(r_{i}, r_{i+1}) {\kern-1pt}\ge{\kern-1pt} (K'{\kern-1pt}-{\kern-1pt}1) (K" {\kern-1pt}+{\kern-1pt} 2\theta {\kern-1pt}+{\kern-1pt} 4B). \end{align*} $$

This implies that M is finite and, in particular, $M \le d(x, y)/(K'-1)(K"+2\theta +4B)$ .

We first observe that, by Lemma 2.5, for any i, we cannot simultaneously have

$$ \begin{align*} r_{i} \ge K'r_{i-1} \quad \text{and}\quad r_i \geq K'r_{i+1}. \end{align*} $$

Hence, the only possibilities for the sequence are either:

1. (i) $r_{i}$ keeps decreasing;

2. (ii) $r_{i}$ keeps increasing; or

3. (iii) $r_{i}$ decreases at first and then keeps increasing.

We will apply this observation in two cases depending on the endpoints of $[x',y']$ .

Case 1. One (or both) of the endpoints is x or y. We will first discuss the case $x' = x$ . Note that the sequence $(r_{i})_{i}$ terminates at step M that satisfies

(2.5) $$ \begin{align} d(\pi_{Z}(x_{M}), \pi_{Z}(y')) \le \theta + B. \end{align} $$

Let $r_{j} := \min _{i=0, \ldots , M} r_{i}$ . Then considering scenarios (i)–(iii) discussed above, we have

(2.6) $$ \begin{align} \frac{r_{M}}{r_{j}} \cdot \frac{r_{0}}{r_{j}} \ge (K')^{M}. \end{align} $$

Now, inequality (2.5) and our choices of $x_{i}$ values imply that

(2.7) $$ \begin{align} M \ge \frac{1}{\theta + B}d(\pi_{Z}(x), \pi_{Z}(y')) - 1. \end{align} $$

Combining inequalities (2.6) and (2.7), we have

$$ \begin{align*} \log d(y', Z) + \log d(x, Z) - 2 \log r_{j} \ge d(\pi_{Z} (x), \pi_{Z}(y')) \cdot \frac{\log K' }{\theta+B} - \log K'. \end{align*} $$

This implies that

$$ \begin{align*} d(\pi_{Z}(x), \pi_{Z}(y')) \le \delta(\log d(x, Z) + \log d(y', Z))) + \log K'. \end{align*} $$

Considering the assumption of the lemma, we conclude that $y'$ cannot equal y. Hence, $[x, y']$ is not the entire $[x, y]$ and $d(y', Z) =K"+2\theta + 4B$ holds.

Now, at step M, we have either $r_{M} \ge K' r_{M-1}$ or $r_{M} \le r_{M-1}/K'$ . In the former case, note that

$$ \begin{align*} r_{M} \ge K' r_{M-1} \ge K' \cdot (K" + 2\theta + 4B). \end{align*} $$

This implies that $r_{M} \ge K' d(y', Z)$ as well. Now, Lemma 2.5 asserts that $d(x_{M}, Z) \le 2 K + 16B \le K" + 2\theta + 4B$ , which is a contradiction to the fact that $x_{M} \in [x', y']$ is $(K" + 2\theta +4B)$ away from Z. Hence, we are bound to the case that $r_{M} \le r_{M-1}/K'$ , which means scenario (i) out of the three scenarios mentioned before.

In particular, $(r_{i})_{i}$ is decreasing for $i=0, \ldots , M$ , and we have

$$ \begin{align*} (K')^{M} \le r_{0}/r_{M}, \end{align*} $$

which implies

$$ \begin{align*}M \le \frac{\log r_{0} - \log r_{M}}{\log K'}. \end{align*} $$

This means

$$ \begin{align*} d(\pi_{Z}(x_{M}), \pi_{Z}(x)) \le (\theta + B) M \le \delta \log d(x, Z). \end{align*} $$

Now, recall that $y' \in N_{K" + 2\theta + 4B}(Z)$ . Let $p_{x} = y'$ and take $q_{x} \in Z$ such that

$$ \begin{align*} d(p_{x}, q_{x}) \le K" + 2\theta + 4B. \end{align*} $$

This choice of $p_x$ and $q_x$ guarantees that

$$ \begin{align*} d(\pi_{Z}(p_{x}), q_{x}) &\le d(\pi_{Z}(p_{x}), \pi_{Z}(q_{x})) + d(\pi_{Z}(q_{x}), q_{x}) \\ &\le (A d(p_{x}, q_{x}) + B ) + B \\ &\le K_{1} \end{align*} $$

and consequently

$$ \begin{align*} d(q_{x}, \pi_{Z}(x)) \le \delta \log d(x, Z) + K_{1}. \end{align*} $$

An analogous argument applies to the connected component $[x', y]$ of $[x, y] \setminus N_{K" + 2\theta + 4B}(Z)$ that contains y. In this case, we conclude that $x' \neq x$ and $d(x', Z) = K" + 2\theta + 4B$ . Moreover, if we set $p_{y} = x'$ and let $q_{y} \in Z$ be such that $d(p_{y}, q_{y}) = K" + 2\theta + 4B$ , then we conclude

$$ \begin{align*} d(p_{y}, q_{y}) \le K_{1} \quad \text{and} \quad d(q_{y}, \pi_{Z}(y)) \le \delta \log d(y, Z) + K_{1}.\end{align*} $$

Case 2. The endpoints $x'$ and $y'$ both belong to the closure of $N_{K" + 2\theta + 4B}(Z)$ . These are segments between our choice of $p_x$ and $p_y$ . We show that they are within the $K_1$ -neighbourhood of Z.

In this case,

$$ \begin{align*} d(x', Z) = d(y', Z) = K" + 2\theta + 4B \le d(p, Z) \quad (\text{for all } p \in [x', y']). \end{align*} $$

Observe that $r_{i}$ cannot decrease at first since $[x',y']$ lies outside the $(K"+2\theta +4B)$ -neighbourhood of Z. However, $r_{i}$ also cannot keep increasing, because $d(x', Z) = d(y', Z)$ . So the process must stop at the very beginning, that is,

$$ \begin{align*} M=0 \quad \text{and} \quad d(\pi_{Z}(x'), \pi_{Z}(y')) \le \theta + B. \end{align*} $$

Then, we have

$$ \begin{align*} d(x', y') &\le d(x', \pi_{Z}(x')) + (\theta + B) + d(\pi_{Z}(y'), y') \\ &\leq ((A+1)d(x',Z)+2B ) + (\theta + B) + ((A+1)d(y',Z)+2B ) \\ & = 2(A+1)(K" + 2\theta + 4B) + 4B + (\theta + B). \end{align*} $$

The second inequality is due to inequality (2.1). From this, we deduce that $[x', y']$ lies in the $K_{1}$ -neighborhood of Z.

The next lemma helps us strengthen Lemma 2.6 to a statement about Hausdorff distance.

Lemma 2.7. Let $K{\kern-1pt},{\kern-1pt} M,{\kern-1pt} M'$ be positive constants, and $\alpha {\kern-1pt}:{\kern-1pt} [0, M] {\kern-1pt}\rightarrow{\kern-1.2pt} X$ and $\beta {\kern-1pt}:{\kern-1pt} [0, M'] {\kern-1pt}\rightarrow{\kern-1.2pt} X$ be $(q, Q)$ -quasi-geodesics. Suppose that $\alpha $ is contained in a K-neighbourhood of $\beta $ and

$$ \begin{align*} d(\alpha(0), \beta(m))< K, \quad d(\alpha(M), \beta(n)) < K \end{align*} $$

hold for some $0 \le m < n \le M'$ . Then, we have

$$ \begin{align*} d_{\mathrm{Haus}}(\alpha, \beta|_{[m, n]}) \leq 2(q^{6} + q^{4} + q^{2} + 1)(Q+K). \end{align*} $$

Proof. Let us define a map h from $[0, M]$ to $[0, M']$ . For each $t \in [0, M]$ , let $h(t) \in [0, M']$ be such that $d(\alpha (t), \beta (h(t))) \le K$ . This map is well defined, and is a $(q^{2}, 2qK + 2qQ)$ -quasi-isometric embedding of $[0, M]$ into $\mathbb {R}$ . Indeed, note that

$$ \begin{align*} |h(t) - h(t')| &\le q d(\beta(h(t)), \beta(h(t'))) + qQ \\ &\le qd(\alpha(t), \alpha(t')) + 2qK + qQ \\ &\le q^{2} |t-t'| + 2qK + 2qQ \end{align*} $$

and

$$ \begin{align*} |t - t'| &\le q d(\alpha(t), \alpha(t')) + qQ \\ &\le qd(\beta(h(t)), \beta(h(t'))) + 2qK + qQ \\ &\le q^{2} |h(t)-h(t')| + 2qK + 2qQ. \end{align*} $$

From the very definition, it is clear that $\alpha $ and $\beta (h([0, M]))$ are within Hausdorff distance K. Next, as h is a $(q^{2}, 2qK+2qQ)$ -QI-embedding of $[0, M]$ , its image $h([0, M])$ is a $(2qK+2qQ)$ -connected subset of $\mathbb {R}$ . Now, let $\tau \in [0, M]$ be such that $h(\tau ) = \inf _{0 \le t \le M} h(t)$ . Then, $h(\tau ) \le m < n = h(M)$ holds. Since $h([0, M])$ is $(2qK+2qQ)$ -connected, there exists $\tau _{0} \in [\tau , M]$ such that $|h(\tau _{0}) - m| \le 2qK+2qQ$ . Now, we have

$$ \begin{align*}\begin{aligned} |m-h(\tau)| &= |h(0) - h(\tau)|\le q^{2} |\tau - 0| + 2qK + 2qQ \\ &\le q^{2} |\tau_{0} - 0| + 2qK + 2qQ \\ &\le q^{2} ( q^{2} |h(\tau_{0}) - h(0)| + 2qK+ 2qQ) + 2qK+2qQ \\ &\le (q^{4} + q^{2} + 1)(2qK+2qQ). \end{aligned} \end{align*} $$

Similarly, we have $\sup _{0 \le t \le M} h(t) < n + (q^{4} + q^{2} + 1)(2qK+2qQ)$ . In other words, $h([0, M])$ is contained in

$$ \begin{align*} [m - 2(q^{5} + q^{3} + q)(Q+K),\,\, n + 2(q^{5} + q^{3} + q)(Q+K)]. \end{align*} $$

In particular, $h([0, M])$ and $[m, n]$ are within Hausdorff distance $2(q^{5} + q^{3} + q)(Q+K)$ . By applying $\beta $ , we deduce that $\beta (h([0, M]))$ and $\beta |_{[m, n]}$ are within Hausdorff distance $2(q^{6}+q^{4}+q^{2})(Q+K)+ Q$ . Combining all these, we conclude that

$$ \begin{align*} d_{\mathrm{Haus}}(\alpha, \beta|_{[m, n]}) \leq 2(q^{6}+q^{4}+q^{2})(Q+K)+ Q+K. \\[-37pt] \end{align*} $$

Corollary 2.8. In the setting of Lemma 2.6, assume that Z is a $(q,Q)$ -quasi-geodesic. Then for some constant $K_2$ depending on $f,\theta ,q,Q,\delta $ ,

$$ \begin{align*} d_{\mathrm{Haus}}([p_x,p_y],[q_x,q_y]|_{Z}) \leq K_2. \end{align*} $$

As another corollary of Lemma 2.6, we can replace a superlinear-divergent quasigeodesic on X with a superlinear-divergent geodesic.

Corollary 2.9. Let $\gamma $ be a bi-infinite $(f, \theta )$ -divergent quasigeodesic on a proper space X. Then there exists a bi-infinite $(f',\theta ')$ -divergent geodesic $\gamma '$ such that $d_\mathrm{Haus}(\gamma , \gamma ')$ is finite. Specifically, $f'(x) = f(x-C)$ , $\theta ' = \theta + 2C$ , where C is the Hausdorff distance between $\gamma $ and $\gamma '$ .

Proof. Let $\gamma : {\mathbb {Z}} \rightarrow X$ be an $(f, \theta )$ -divergent $(q, Q)$ -quasigeodesic on X. Let $K_{1}$ be the constant given by Lemma 2.6 for $Z = \gamma $ and $\delta = 0$ . For each sufficiently large n, we note that

$$ \begin{align*} d(\pi_{\gamma}(\gamma(n)), \pi_{\gamma}(\gamma(-n))) \ge d(\gamma(n), \gamma(-n)) - 2B> \frac{2n}{q} - Q - 2B > K_{1}. \end{align*} $$

Lemma 2.6 tells us that there exists a subsegment $[p_{-n}, p_{n}]$ of $[\gamma (-n), \gamma (n)]$ and $j_{-n}, j_{n} \in {\mathbb {Z}}$ such that

$$ \begin{align*} d(p_{-n}, \gamma(j_{-n})) \le K_{1}, \quad d(p_{n}, \gamma(j_{n})) \le K_{1}, \end{align*} $$

$$ \begin{align*} d(\gamma(j_{-n}), \gamma(-n)) \le d(\gamma(j_{-n}), \pi_{\gamma}(\gamma(-n))) + d(\pi_{\gamma}(\gamma(-n)), \gamma(-n)) \le K_{1}+B, \end{align*} $$

$$ \begin{align*} d(\gamma(j_{n}), \gamma(n)) \le d(\gamma(j_{n}), \pi_{\gamma}(\gamma(n))) + d(\pi_{\gamma}(\gamma(n)), \gamma(n)) \le K_{1}+B, \end{align*} $$

and such that $[p_{-n}, p_{n}] \subseteq N_{K_{1}} (\gamma )$ . By Lemma 2.7, $[p_{-n}, p_{n}]$ and $\gamma ([j_{-n}, j_{n}])$ are within Hausdorff distance $(q^{5} + q^{3} + q)(2K_{1}+2qQ) + Q +K_{1}$ . For simplicity, let $C = (q^{5} + q^{3} + q)(2K_{1}+2qQ) + Q +K_{1}$ . Note also that

$$ \begin{align*} j_{-n} < -n + q(K_{1} + B) + Q < 0 < n - q(K_{1} + B) - Q < j_{n} \end{align*} $$

for large enough n. In conclusion, $[p_{-n}, p_{n}]$ contains a point p that is C-close to $\gamma (0)$ . Moreover, the distance

$$ \begin{align*}d(\gamma(0), p_{n})> d(\gamma(0), \gamma(j_{n})) - 2K_{1} - B\end{align*} $$

grows linearly, and likewise so does $d(\gamma (0), p_{-n})$ . Using the properness of X and Arzelà–Ascoli theorem, we conclude that the sequence $\{[p_{-n}, p_{n}]\}_{n>1}$ converges to a bi-infinite geodesic $\gamma '$ , within a $K_{1}$ -neighbourhood of $\gamma $ . By Lemma 2.7 again, we have $d_{\mathrm{Haus}}(\gamma , \gamma ') \le ~C$ .

It remains to declare a coarsely Lipschitz projection $\pi _{\gamma '}$ onto $\gamma '$ and show that $\gamma '$ is $(f', \theta ')$ -divergent with respect to $\pi _{\gamma '}$ . Since $d_{\mathrm{Haus}}(\gamma ,\gamma ') \le C$ , we can define $\pi _{\gamma '}(z)$ to be a point on $\gamma '$ such that

$$ \begin{align*}d(\pi_{\gamma'}(z), \pi_{\gamma}(z)) < C. \end{align*} $$

Any path p outside of the R-neighbourhood of $\gamma '$ is outside of the $(R-C)$ -neighbourhood of $\gamma $ . Moreover, if the endpoints $p_-$ and $ p_+$ of p satisfy that

$$ \begin{align*} d(\pi_{\gamma'}(p_-),\pi_{\gamma'}(p_+))> \theta + 2C, \end{align*} $$

then by the construction of $\pi _{\gamma '}$ ,

$$ \begin{align*} d(\pi_{\gamma}(p_-),\pi_{\gamma}(p_+))> \theta. \end{align*} $$

Superlinear divergence of $\gamma $ implies that the length of p is at least $f(R-2C)$ . This concludes the proof.

2.1 Convention

From now on, we fix a finitely generated group G with exponential growth which contains a superlinear-divergent bi-infinite geodesic $\gamma : \mathbb {R} \rightarrow G$ : this is a QI-invariant property thanks to Corollaries 2.3 and 2.9.

3 Alignment

In this section, we define the alignment of sequences of (subsegments of) superlinear- divergent geodesics. The key lemma is Proposition 3.3, which promotes alignment between consecutive pairs to global alignment of a sequence.

Definition 3.1. Given paths $\gamma _{1}, \ldots , \gamma _{N} : {\mathbb {Z}} \rightarrow G$ equipped with $(A,B)$ -coarse Lipschitz projections $\pi _{\gamma _1}, \ldots , \pi _{\gamma _N}$ , integers $m_{i} \leq n_{i}$ and subpaths $\gamma _{i}' := \gamma _{i}([m_{i}, n_{i}])$ , we say that $(\gamma _{1}', \ldots , \gamma _{N}')$ is K-aligned if:

1. (1) $\pi _{\gamma _{i}}(\gamma _{i-1}')$ lies in $\gamma _{i}((-\infty , m_{i} + K])$ ; and

2. (2) $\pi _{\gamma _{i}}(\gamma _{i+1}')$ lies in $\gamma _{i}([n_{i} - K, +\infty ))$ .

Note that $\gamma _i$ can be a single point. We will construct linkage words using K-aligned paths, starting with the following lemma.

Lemma 3.2. Given a superlinear function f, positive constants $\theta , A, B$ and $0<\epsilon , \eta < 0.1$ , there exists a constant $K_{3} = K_{3}(f, \theta , A, B, \epsilon , \eta )$ such that the following holds.

For $i = 1,2$ , let $\gamma _i$ be an $(f,\theta )$ -divergent geodesic with respect to an $(A,B)$ -coarsely Lipschitz projection $\pi _{\gamma _i} : X \to \gamma _i$ and let $\gamma _{i}' = \gamma _{i}([m_{i}, n_{i}])$ be a subpath of $\gamma _{i}$ . Let $z \in X$ and let $D> K_3$ be a constant such that:

1. (1) $\operatorname {\mathrm {\operatorname {diam}}}(\gamma _{1}' \cup \gamma _{2}' \cup z) \leq D$ ;

2. (2) $ |n_{2} - m_{2}| \ge \epsilon \log D$ ;

3. (3) $(\gamma _1', \gamma _2')$ is $(\eta \epsilon \log D)$ -aligned and $(\gamma _2', z)$ is $(2\eta \epsilon \log D)$ -aligned.

Then $(\gamma _{1}', z)$ is $(2\eta \epsilon \log D)$ -aligned (see Figure 2).

Figure 2 The segments satisfy $(\gamma _1', \gamma _2')$ is $(\eta \epsilon \log n)$ -aligned and $(\gamma _2', \gamma _3')$ is $(2\eta \epsilon \log n)$ -aligned.

Proof. We will assume that D is much larger than the constants $K_{1}$ and $K_{2}$ that appear in the argument. For $i=1,2$ , denote $x_i = \gamma (m_i)$ and $y_i = \gamma (n_i)$ . Suppose for contradiction that $\pi _{\gamma _1}(z)$ lies in $ \gamma _1((-\infty , n_1 - 2 \eta \epsilon \log D))$ as in Figure 3. This implies that

$$ \begin{align*} \begin{aligned} d(\pi_{\gamma_{1}}(y_{2}), \pi_{\gamma_{1}}(z)) &\ge \eta \epsilon \log D> \frac{\eta \epsilon}{3}( \log d(y_{2}, \gamma_{1}) + \log d(z, \gamma_{1})) + K_1, \end{aligned} \end{align*} $$

where $K_{1}$ is the constant given in Lemma 2.6 taking $\delta = \eta \epsilon / 3$ . By Lemma 2.6, there exist a subsegment $[p_{1}, p_{2}]$ of $[z, y_{2}]$ and time parameters s, t of $\gamma _1$ such that $d(p_{1}, \gamma _{1}(s)) < K_1$ , $d(p_{2}, \gamma _{1}(t)) < K_1$ and

$$ \begin{align*}\begin{aligned} d(\gamma_{1}(s), \pi_{\gamma_{1}}(z)) &< \frac{\eta \epsilon}{3} \log d(z, \gamma_{1}) + K_{1} ,\\ d(\gamma_{1}(t), \pi_{\gamma_{1}}(y_{2})) &< \frac{\eta \epsilon}{3} \log d(y_{2}, \gamma_{1}) + K_{1}. \end{aligned} \end{align*} $$

Figure 3 If $\pi _{\gamma _1}(z)$ lies in $ \gamma _1((-\infty , n_1 - 2 \eta \epsilon \log (n)))$ , then the geodesic $[y_2,z]$ would fellow travel $\gamma _1'$ then $\gamma _2'$ , causing a contradiction.

In particular, we have

$$ \begin{align*}\begin{aligned} s &< \gamma_{1}^{-1} (\pi_{\gamma_{1}}(z)) + \bigg( \frac{\eta \epsilon}{3} \log d(y_{2}, \gamma_{1}) + K_{1}\bigg) \\ &\le n_{1} - \frac{5}{3}\eta \epsilon \log D. \end{aligned} \end{align*} $$

A similar calculation shows that $t> n_{1} - \tfrac 43\eta \epsilon \log D$ . Now let $K_2$ be the constant in Corollary 2.8 so that $\gamma _{1}([s, t])$ and $[p_{1}, p_{2}]$ are within Hausdorff distance $K_{2}$ of each other. In particular, for $p' := \gamma _{1}(n_{1} - 1.5 \eta \epsilon \log D) \in \gamma _{1}([s, t])$ , we have a point $p \in [p_{1}, p_{2}] \subseteq [z, y_{2}]$ such that $d(p, p') \le K_{2}$ .

Let us now investigate the relationship between $[p, y_{2}]$ and $\gamma _{2}'$ . First, the coarse Lipschitzness of $\pi _{\gamma _{2}}$ tells us that

$$ \begin{align*}\begin{aligned} d(\pi_{\gamma_{2}}(p), \pi_{\gamma_{2}}(y_{2})) &\ge d(\pi_{\gamma_{2}}(p'), y_{2}) - d(\pi_{\gamma_{2}}(p'), \pi_{\gamma_{2}}(p)) - d(y_{2}, \pi_{\gamma_{2}}(y_{2})) \\ &\ge d(\pi_{\gamma_{2}}(p'), y_{2}) - AK_{2}- 2B. \end{aligned} \end{align*} $$

Since $\pi _{\gamma _{2}}(p') \in \pi _{\gamma _{2}}(\gamma _{1}')$ is contained in $\gamma _{2}( (-\infty , m_{2} + \eta \epsilon \log D) )$ , we deduce that

$$ \begin{align*}\begin{aligned} d(\pi_{\gamma_{2}}(p), \pi_{\gamma_{2}}(y_{2}))> (n_{2} - m_{2}) - \eta \epsilon \log D - AK_{2} - 2B > \frac{\eta \epsilon}{3}(\log d(p, \gamma_{2})) + K_{1}. \end{aligned} \end{align*} $$

Again, by Lemma 2.6, there exist a subsegment $[p_{1}', p_{2}'] \subseteq [p,z]$ and time parameters $s', t'$ of $\gamma _2$ with $d(p_{1}', \gamma _{2}(s')) < K_{1} $ , $d(p_{2}', \gamma _{2}(t')) < K_{1}$ and

$$ \begin{align*}\begin{aligned} d(\gamma_{2}(s'), \pi_{\gamma_{2}}(p)) &< \frac{\eta \epsilon}{3q} \log d(p, \gamma_{2}) + K_{1},\\ d(\gamma_{2}(t'), \pi_{\gamma_{2}}(y_{2})) &< K_{1}. \end{aligned} \end{align*} $$

This means that

$$ \begin{align*}\begin{aligned} d(p_{1}', p_{2}') &\ge d(\pi_{\gamma_{2}}(p),\pi_{\gamma_{2}}(y_{2})) - d(\gamma_{2}(t'), \pi_{\gamma_{2}}(y_{2})) -d(\gamma_{2}(s'), \pi_{\gamma_{2}}(p))\\ &\quad -d(p_{1}', \gamma_{2}(s')) -d(p_{2}', \gamma_{2}(t')) \\ &\ge \frac{(n_{2} - m_{2}) - \eta \epsilon \log D}{q} - Q - \frac{1}{3}\eta \epsilon \log D - 4K_{1} \\ &\ge \frac{2}{3}\eta \epsilon \log D. \end{aligned} \end{align*} $$

Hence, $[y_{2}, p_{2}']$ is longer than $\tfrac 23 \eta \epsilon \log D$ . However,

$$ \begin{align*}d(p_{2}', y_{2}) \le d(p_{2}', \gamma_{2}(t')) + d(\gamma_{2}(t'), \pi_{\gamma_{2}}(y_{2})) + d(y_{2}, \pi_{\gamma_{2}}(y_{2})) \le 2K_{1}+ B.\end{align*} $$

This is a contradiction for sufficiently large D.

Proposition 3.3. Let f be a superlinear function, $\theta , A, B> 0$ , $0< \epsilon , \eta < 0.1$ and let $K_{3}$ be the constant given in Lemma 3.2. Let $x, y \in X$ , and for $i=1, \ldots , N$ , $\gamma _{i}$ be an $(f, \theta )$ -divergent geodesic with respect to an $(A, B)$ -coarse-Lipschitz projection and let $\gamma _{i}' = \gamma _{i}([m_{i}, n_{i}])$ be a subpath of $\gamma _{i}$ . Let $D> K_3$ be a constant such that:

1. (1) $\operatorname {\mathrm {\operatorname {diam}}}(\gamma _{1}' \cup \cdots \cup \gamma _{N}') \leq D$ ;

2. (2) $ |n_{i} - m_{i}| \ge \epsilon \log D$ for each i; and

3. (3) $(x, \gamma _{1}', \ldots , \gamma _{N}', y)$ is $(\eta \epsilon \log D)$ -aligned.

Then for each i, $(x, \gamma _{i}', y)$ is $(2\eta \epsilon \log D)$ -aligned.

Proof. This follows inductively from Lemma 3.2. Fixing $i<j$ , we show that

$$ \begin{align*} \pi_{\gamma_i}(\gamma_j') \in \gamma_i((-\infty, m_i+2\eta\epsilon\log D]). \end{align*} $$

If $i = j-1$ , immediately by assumption, we have

$$ \begin{align*} \pi_{\gamma_i}(\gamma_j') \in \gamma_i((-\infty, m_i+\eta\epsilon\log D]) \subset \gamma_i((-\infty, m_i+2\eta\epsilon\log D]). \end{align*} $$

Now assuming

$$ \begin{align*} \pi_{\gamma_{i+1}}(\gamma_j) \in \gamma_{i+1}((-\infty, m_{i+1}+2\eta\epsilon\log D]), \end{align*} $$

since $(\gamma _i,\gamma _{i+1})$ are $(\eta \epsilon \log D)$ -aligned, the triple $(\gamma _i,\gamma _{i+1}, \gamma _j)$ satisfies the assumptions in Lemma 3.2. We conclude that

$$ \begin{align*} \pi_{\gamma_{i}}(\gamma_j) \in \gamma_i((-\infty, m_i+2\eta\epsilon\log D]). \end{align*} $$

Applying the same argument to $\pi _{\gamma _{j}}(\gamma _i)$ , $\pi _{\gamma _{j}}(\gamma _k)$ and $\pi _{\gamma _{k}}(\gamma _j)$ shows that

$$ \begin{align*} \pi_{\gamma_{j}}(\gamma_i) &\in \gamma_j([n_j-2\eta\epsilon\log D, +\infty)),\\ \pi_{\gamma_{j}}(\gamma_k) &\in \gamma_j((-\infty, m_j+2\eta\epsilon\log D])\quad \text{and}\\ \pi_{\gamma_{k}}(\gamma_j) &\in \gamma_k([n_k-2\eta\epsilon\log D,+\infty)).\\[-3pc] \end{align*} $$

Lemma 3.4. Given a superlinear function f, positive constants $\theta , A, B$ and $0<\epsilon , \eta < 0.1$ , there exist constants $K_{4} = K_{4}(f, \theta , A, B, \epsilon , \eta )$ and $C = C(A)$ such that the following holds.

Let $\alpha $ and $\beta $ be $ (f, \theta )$ -divergent geodesics with respect to $(A, B)$ -coarsely Lipschitz projections. Let $\alpha '$ and $\beta '$ be their subsegments with beginning points $x_1$ and $x_2$ , respectively, such that:

1. (1) $D := \operatorname {\mathrm {\operatorname {diam}}}(\alpha '\cup \beta ') \ge K_{4}$ ;

2. (2) $\operatorname {\mathrm {\operatorname {diam}}}(\alpha ') \geq \epsilon \log D$ ; and

3. (3) $(\alpha ', x_2)$ and $(x_1, \beta ')$ are $\eta \epsilon \log D$ -aligned.

Then, $(\alpha ', \beta ')$ is $(C \eta \epsilon \log D)$ -aligned.

Proof. Let $\alpha '= \alpha ([m_{1}, n_{1}])$ and $\beta '= \beta ([m_{2}, n_{2}])$ . Denote $x_1 = \alpha (m_1)$ , $y_1 = \alpha (n_1)$ , $x_2 = \beta (m_2)$ , $y_2 = \beta (n_2)$ . Let $C' = 16(A+1)+1$ and $C = (C')^2 + 2$ . We first show that

$$ \begin{align*} \pi_{\beta}(\alpha') \subset \beta((-\infty, m_2 + C'\epsilon \log D]) \subset \beta((-\infty, m_2 + C\epsilon \log D]). \end{align*} $$

Suppose in contrast that for some point $a \in \alpha '$ , the projection

$$ \begin{align*} \pi_\beta(a) \in \beta([m_2 + C'\epsilon \log D , +\infty)). \end{align*} $$

Then, we have

$$ \begin{align*} d(\pi_\beta (x_1), \pi_\beta (a)) & \geq (C'-1) \eta \epsilon \log D\\ & \geq \frac{1}{16A}(C'-1) \eta \epsilon (\log d(x_1, \beta) + \log d(a,\beta)) + K_1, \end{align*} $$

where $K_1>0$ is the constant as in Lemma 2.6 taking $\delta = {1}/{16A}(C'-1)\eta \epsilon $ . Then, there exists a subsegment $[p_{x_1},p_a]|_\alpha \subset [x_1,a]|_\alpha \subset [x_{1}, y_{1}]|_\alpha $ and points $q_{x_1}, q_a$ on $\beta $ such that

$$ \begin{align*} d(p_{x_1}, q_{x_1}), d(p_a, q_a) &< K_1,\\ d(q_{x_1}, \pi_{\beta}(x_1)) &\le \bigg(\frac{1}{16A}(C'-1)\eta \epsilon\bigg) \log d(x_1, \beta) + K_{1},\\ d(q_{a}, \pi_{\beta}(a)) &\le \bigg(\frac{1}{16A}(C'-1)\eta \epsilon\bigg) \log d(a, \beta) + K_{1}. \end{align*} $$

Then, by Corollary 2.8, there is a point $p^{\prime }_{x_1} \in [p_{x_1},p_{a}]|_{\alpha }$ close to $x_2$ . The point $p^{\prime }_{x_1}$ is chosen to be $p_{x_1}$ if $q_{x_1} \in \beta ((m_2,\infty ))$ , or the point where the Hausdorff distance $K_2$ is attained if $q_{x_1} \in \beta ((-\infty , m_2])$ . The distance is bounded by

$$ \begin{align*} d(x_2,p^{\prime}_{x_1}) &\leq \max \bigg(\bigg(\frac{1}{16A}(C'-1)\eta \epsilon\bigg) \log d(x_1, \beta) + 2K_{1},K_2 \bigg)\\ &\leq \bigg(\frac{1}{16A}(C'-1) \bigg)\eta\epsilon \log D + O(1)\\ &= \bigg(\frac{A+1}{A} \bigg)\eta\epsilon \log D + O(1), \end{align*} $$

where $K_2$ is the constant in Corollary 2.8 and $O(1)$ is the implied constant. Projecting to $\alpha $ gives that

$$ \begin{align*} d(\pi_\alpha(x_2),p^{\prime}_{x_1}) \leq d(\pi_\alpha(x_2),\pi_\alpha(p^{\prime}_{x_1})) + B \leq (A+1)q\eta\epsilon \log D + O(1). \end{align*} $$

However, since $(\alpha ', x_{2})$ is $(\eta \epsilon \log D)$ -aligned,

$$ \begin{align*} d(\pi_\alpha(x_2),p^{\prime}_{x_1}) &\geq d(y_1,p^{\prime}_{x_1}) - \eta\epsilon\log D \\ &\geq d(p_{a},p^{\prime}_{x_1}) - \eta\epsilon\log D\\ &\geq d(x_2,\pi_\beta(a)) - d(x_2,p^{\prime}_{x_1}) - d(\pi_\beta(a), p_{a})- \eta\epsilon\log D\\ & \geq \bigg( \frac{1}{q} C'\eta \epsilon \log D \bigg) - 2 \bigg( \frac{C'-1}{16A} \eta \epsilon \log D \bigg)- \eta\epsilon\log D - O(1)\\ & \geq (14(A+1)-1 ) \eta \epsilon \log D - O(1) \end{align*} $$

contradicting the previous inequality when D is sufficiently large.

We now show that

$$ \begin{align*} \pi_{\alpha}(\beta') \subset \alpha((n_1 - C\epsilon \log D,\infty)). \end{align*} $$

Suppose in contrast that for some point $b \in \beta '$ , the projection

$$ \begin{align*} \pi_{\alpha}(b) \in \alpha((-\infty, n_1 - C\epsilon \log D)). \end{align*} $$

We will discuss in two cases. If

$$ \begin{align*} \pi_{\alpha}(b) \in \alpha((m_1, n_1 - C\epsilon \log D)) \subset \alpha', \end{align*} $$

then the previous calculation shows that

$$ \begin{align*} \pi_\beta(\pi_{\alpha}(b)) \in \beta ((-\infty, m_2+C'\eta \epsilon \log D]). \end{align*} $$

This shows that $(\pi _\alpha (b),[x_2,b]|_\beta , )$ and $(b,[\pi _\alpha (b), y_1]|\alpha )$ are $(C'\eta \epsilon \log D)$ -aligned. Moreover, $\operatorname {\mathrm {\operatorname {diam}}} ([x_2,b]|_\beta \cup [\pi _\alpha (b), y_1]|_\alpha ) < D$ . So the exact same calculation as before shows that

$$ \begin{align*} \pi_\alpha ([x_2,b]|_\beta) \subset \alpha ((- \infty, \pi_\alpha(b)+C^{\prime2} \epsilon \log D )) \subset \alpha ((- \infty, n_1-2 \epsilon \log D) ). \end{align*} $$

This contradicts that

$$ \begin{align*} \pi_\alpha (x_2) \in \alpha ((n_1 - \eta\epsilon\log D , \infty)). \end{align*} $$

The remainder case is when $\pi _{\alpha }(b) \in \alpha ((-\infty , m_1))$ . We will show that this is impossible assuming $\eta < \min ({1}/({q+2q^2}) , ({A+2})/({A+q+2}))$ and $\alpha '$ is long. In this case,

$$ \begin{align*} d(\pi_{\alpha}(b),\pi_{\alpha}(x_2)) & \geq \frac{1}{q}(1-\eta)\epsilon \log D\\ & \geq \frac{1}{(2+A)} \eta \epsilon \log d(b,\alpha) + \log d(x_2,\alpha) - K_1, \end{align*} $$

where $K_1$ is the constant in Lemma 2.6 choosing $\delta = {1}/{(2+A)} \eta \epsilon $ . Then, by Lemma 2.6, there are points $p_{x_2},p_b \in [x_2,b]$ such that

$$ \begin{align*} d(p_{x_2}, y_1) & \leq \frac{1}{2+A} \eta \epsilon \log D +K_1\quad \text{and}\\ d(p_b, x_1) &\leq \frac{1}{2+A} \eta \epsilon \log D +K_1. \end{align*} $$

Then,

$$ \begin{align*} d(\pi_\beta (x_1), p_b) \leq \frac{A}{2+A} \eta \epsilon \log D +O(1). \end{align*} $$

However, $\pi _\beta (x_1) \in \beta ((-\infty ,m_2 + \eta \epsilon \log D])$ implies that

$$ \begin{align*} d(\pi_\beta (x_1), p_b) & \geq d(x_2,p_b) - \eta \epsilon \log D \\ & \geq d(p_{x_2},p_b) - \eta \epsilon \log D \\ & \geq d(x_1,y_1) - d(x_1,p_b) - d(y_1,p_{x_2}) \eta \epsilon \log D \\ & \geq \epsilon\log D - \frac{2}{2+A}\eta \epsilon \log D - \eta \epsilon \log D - O(1)\\ &> \frac{A}{2+A} \eta \epsilon \log n +O(1). \end{align*} $$

The last step is due to $\eta < 1/3$ . This is a contradiction.

We now construct linkage words. These play the role of Schottky sets in [BMSS23, Gou22]. We use the notation $\mathcal {B}(g, R) := \{h \in G : d(g, h) \le R\}$ to mean the ball of radius R around g, and $\mathcal {S}(g, R) := \{h \in G : d(g, h) = R\}$ to mean the sphere of radius R around g.

Lemma 3.5. Let $\gamma : {\mathbb {R}} \rightarrow G$ be an $(f, \theta )$ -divergent quasi-geodesic and let $\epsilon>0$ . For K sufficiently large, the following holds. For each $m\in {\mathbb {Z}}$ , there exists a subset $S \subseteq G$ with 100 elements such that for each pair of distinct elements $a, b \in S$ , we have:

1. (1) $ |a|, |b| = K$ and $|b a^{-1}|, |a^{-1} b|\ge 0.5K$ ;

2. (2) $\pi _{\gamma }(\gamma (0) a^{-1})$ and $\pi _{\gamma }(\gamma (0)a^{-1} b) \in \mathcal {B}(\gamma (0), \epsilon K)$ ; and

3. (3) $\pi _{\gamma }(\gamma (m) a)$ and $\pi _{\gamma }(\gamma (m) ab^{-1}) \in \mathcal {B}(\gamma (m), \epsilon K)$ .

Proof. Let $K_{1} = K_{1}(0.1\epsilon , f,\theta )$ be as in Lemma 2.6.

Let $\unicode{x3bb}> 1$ be the growth rate of G. For n large enough, we have

$$ \begin{align*} \unicode{x3bb}^{n}\le \# \mathcal{S}(\mathrm{id}, n) \le \unicode{x3bb}^{(1+0.1\epsilon)n}. \end{align*} $$

We consider the sets

$$ \begin{align*}\begin{aligned} O_1 &:= \{g \in \mathcal{S}(\mathrm{id},K): d(\gamma(0), \pi_{\gamma}(\gamma(0)g)) \geq 0.5 \epsilon K\}, \\ O_{2} &:= \{g \in \mathcal{S}(\mathrm{id},K): d(\gamma(m), \pi_{\gamma}(\gamma(m)g)) \ge 0.5\epsilon K \}.\\ \end{aligned}\end{align*} $$

We will argue that both of these sets are much smaller than $\mathcal {S}(\mathrm {id},K)$ and use a certain subset of $\mathcal {S}(\mathrm {id},K) \setminus (O_1\cup O_2)$ to construct our set S.

To show that $O_1,O_2$ are relatively small, let us now consider a word a with $|a| = K$ and $d(\pi _{\gamma }(\gamma (0)a^{-1}), \gamma (0)) \ge 0.5\epsilon K$ . Then, since (assuming K is sufficiently large)

$$ \begin{align*} d(\pi_{\gamma}(\gamma(0) a^{-1}), \pi_{\gamma}(\gamma(0))) \ge 0.5 \epsilon K - B \ge K_{1} + 0.1\epsilon \log B + 0.1\epsilon \log K, \end{align*} $$

Lemma 2.6 asserts that there exist $p \in [\gamma (0), \gamma (0)a^{-1}]$ and $q \in \gamma $ such that $d(p, q) \le K_{1}$ and $d(p, \pi _{\gamma }(\gamma (0)a^{-1})) \le \log |a| + K_{1}$ . In this case, we have

$$ \begin{align*}\begin{aligned} d(p, \gamma(0) a^{-1}) &= d(\gamma(0), \gamma(0) a^{-1}) - d(\gamma(0), p) \\ &\le |a| - d(\gamma(0), \pi_{\gamma}(\gamma(0) a^{-1})) + d(p, \pi_{\gamma}(\gamma(0) a^{-1})) \\ &\le K - 0.5\epsilon K + \log K + K_{1}. \end{aligned} \end{align*} $$

In summary,

$$ \begin{align*}a^{-1} = (\gamma(0)^{-1}q)\cdot(q^{-1} p) \cdot (p^{-1}\gamma(0)a^{-1})\end{align*} $$

where, as in Figure 4:

• • $\gamma (0)^{-1}q = \gamma (0)^{-1} \gamma (k)$ for some k between $-2qK - Q$ and $2qK+Q$ ;

• • $|q^{-1}p| \le K_{1}$ ; and

• • $|p^{-1}\gamma (0)a^{-1}| \le (1 - 0.5\epsilon ) K+ \log (1.5K) + K_{1}$ .

Figure 4 Decomposing $ a ^{-1} $ as a concatenation of well-controlled paths.

For large enough K, the number of such elements is at most

$$ \begin{align*}5QK \cdot \unicode{x3bb}^{(1+0.1\epsilon) (1-0.4\epsilon)K} \le 5QK \unicode{x3bb}^{(1-0.3 \epsilon)K}.\end{align*} $$

Hence, the cardinality of

$$ \begin{align*} \mathcal{A} := \{ (g_{1}, \ldots, g_{100}) \in \mathcal{S}(\mathrm{id},K)^{100} : g_i \in O_1 \text{ for some } i \in [1,100]\} \end{align*} $$

is at most $100 \cdot (\# S_{0})^{99} \cdot 3QK \unicode{x3bb} ^{ (1+0.3) \epsilon K}$ —we pick some index i which satisfies the given condition and draw the rest of the elements from $\mathcal {S}(\mathrm {id},K)$ . This is exponentially small compared with $(\# \mathcal {S}(\mathrm {id},K))^{100}$ .

By a similar logic,

$$ \begin{align*} \mathcal{B} := \{ (g_{1}, \ldots, g_{100}) \in \mathcal{S}(\mathrm{id},K)^{100} : g_i \in O_2\text{ for some } i \in [1,100]\} \end{align*} $$

is exponentially small compared with $\mathcal {S}(\mathrm {id},K)^{100}$ .

Finally, we observe that for each $h \in \mathcal {S}(\mathrm {id},K)$ , there are at most

$$ \begin{align*}\#\mathcal{B}(h,0.5K)\leq \unicode{x3bb}^{(1+\epsilon)0.5K}\end{align*} $$

elements g such that $|g^{-1}h| \leq 0.5K$ .

Hence, we deduce that the cardinality of

$$ \begin{align*}\mathcal{C} := \{ (g_{1}, \ldots, g_{100}) \in S_{0}^{100} : d(g_i,g_j) \leq 0.5K \text{ for some } i \neq j\} \end{align*} $$

is at most $100 \cdot 99 \cdot 2 \cdot \unicode{x3bb} ^{0.6K} \cdot (\#\mathcal {S}(\mathrm {id},K)^{99}$ , which is exponentially small compared with $(\#\mathcal {S}(\mathrm {id},K))^{100}$ . Given these estimates, we conclude that for sufficiently large K,

$$ \begin{align*} \mathcal{S}(\mathrm{id},K)^{100} \setminus( \mathcal{A} \cup \mathcal{B} \cup \mathcal{C} ) \end{align*} $$

is non-empty.

Letting $(g_{1}, \ldots , g_{100})$ be one of its elements, we claim that the choice $S = \{g_i, i = 1, \ldots ,100\}$ satisfies the conditions of the lemma.

Note in particular that $g_i^{-1}g_j\neq \mathrm {id}$ since its norm is at least $0.5K$ . We observe that:

1. (1) $g_{i}$ are all distinct;

2. (2) $|g_{i}| = K$ for all $1 \le i\le 100$ ;

3. (3) $|g_{i} g_{j}^{-1}|$ , $|g_{i}^{-1} g_{j}| \ge 0.5K$ for each $i\neq j$ ;

4. (4) $\pi _{\gamma }(\gamma (0) g_{i}^{-1}) \in \mathcal {B}(\gamma (0), 0.5\epsilon K)$ and $\pi _{\gamma }(\gamma (m) g_{i}) \in \mathcal {B}(\gamma (m), 0.5\epsilon K)$ for each $1 \le i \le 100$ .

It remains to show that $d(\gamma (0), \pi _{\gamma }(\gamma (0) g_{i}^{-1} g_{j})) < \epsilon K$ for each $i \neq j$ . Suppose not; then for large enough K, we have

$$ \begin{align*} \begin{aligned} d(\pi_{\gamma}(\gamma(0) g_{i}^{-1}), \pi_{\gamma}(\gamma(0) g_{i}^{-1}g_{j})) &\ge \epsilon K - 0.5 \epsilon K \\ &> 2 \epsilon \log K \\ &> \epsilon \log |g_{i}| + \epsilon \log (|g_{i}|+|g_{j}|) + K_{1}' \\ &\ge \epsilon \log d( \gamma, \gamma(0) g_{i}^{-1}) + \epsilon \log d( \gamma, \gamma(0) g_{i}^{-1} g_{j}) + K_{1}', \\ \end{aligned} \end{align*} $$

where $K_1' = K_{1}(\epsilon , f,\theta )$ defined as in Lemma 2.6. Then by Lemma 2.6, there exists $p \in [\gamma (0) g_{i}^{-1}, \gamma (0) g_{i}^{-1} g_{j}]$ such that

$$ \begin{align*} d( p, \pi_{\gamma}(\gamma(0) g_{i}^{-1})) < \epsilon \log d(\gamma, \gamma(0) g_{i}^{-1}) + 2K_{1}' \le \epsilon \log K + 2K_{1}' \end{align*} $$

and $d(\gamma (0), p) < 0.6 \epsilon K$ . Here, we have

$$ \begin{align*} d(p, \gamma(0) g_{i}^{-1}) \ge d(\gamma(0), \gamma(0) g_{i}^{-1}) - d(\gamma(0), p) \ge K - 0.6 \epsilon K \end{align*} $$

and

$$ \begin{align*} \begin{aligned} d(\gamma(0), \gamma(0) g_{i}^{-1} g_{j}) &\le d(\gamma(0), p) + d(p, \gamma(0) g_{i}^{-1}(g_{j}) \\ &\le 0.6 \epsilon K + [d(\gamma(0) g_{i}^{-1}, \gamma(0) g_{i}^{-1} g_{j}) - d(\gamma(0) g_{i}^{-1}, p)] \\ &\le 0.6 \epsilon K + 0.6 \epsilon K. \end{aligned} \end{align*} $$

However, this contradicts $|g_{i}^{-1} g_{j}| \ge 0.5 K$ .

Given a translate of $\gamma $ , we can naturally define the projection

$$ \begin{align*}\pi_{g\gamma}(x) := g\pi_{\gamma}(g^{-1}x).\end{align*} $$

Since G acts by isometries, this is an $(A,B)$ -coarse Lipschitz projection so long as $\pi _{\gamma }$ is as well. The following lemma describes projections between translates of superlinear-divergent quasi-geodesics.

Lemma 3.6. Let $\alpha $ and $\beta $ be $(f, \theta )$ -divergent quasi-geodesics equipped with $ (A,B)$ -coarse Lipschitz projections and let $0< \epsilon < {1}/{10(A+1)}$ . Then, there exists $K_{6}> 0$ such that the following holds. Suppose $a \in G$ and $i \in {\mathbb {Z}}$ satisfy that:

1. (i) $|a|> K_{6}$ ;

2. (ii) $\pi _{\beta }(\beta (0) a^{-1}) \in \mathcal {B}(\beta (0), \epsilon |a|)$ ; and

3. (iii) $\pi _{\alpha }(\alpha (i) a) \in \mathcal {B}(\alpha (i), \epsilon |a|)$ .

Then, for each $j \in {\mathbb {Z}}$ , $\pi _{\alpha }(\alpha (i)a \beta (0)^{-1}\beta (j))$ is within distance $\epsilon \log |j| + 2|a|$ from $\alpha (i)$ .

Proof. For simplicity, we denote and parametrize the translate of $\beta $

$$ \begin{align*} \beta' (j) = \alpha(i) a \beta(0)^{-1} \beta (j). \end{align*} $$

Let $\gamma : [0, M] \rightarrow G$ be a geodesic connecting $\alpha (i)$ and $\beta '(j)$ , see Figure 5. The projection of $\alpha (i)$ onto $\beta '$ is near $\alpha (i) a$ :

$$ \begin{align*} d(\alpha(i) a, \pi_{\beta'} (\alpha(i)) ) = d (\beta(0), \pi_{\beta}(\beta(0)a^{-1}) ) \le \epsilon |a|. \end{align*} $$

Figure 5 The geodesic $[\alpha (i), \beta '(j)]$ comes near $\beta '(0)$ .

Then, there exists $t \in [0,M]$ such that $\gamma (t) \in \mathcal {B}(\alpha (i) a, 2 \epsilon |a|)$ . If $d(\beta '(j),\alpha (i)a) < 2 \epsilon |a|$ , simply take $t=M$ so that $\gamma (t) = \beta '(j)$ . Additionally, if $d(\beta '(j),\alpha (i)a) \geq 2 \epsilon |a|$ , we obtain such t by applying Lemma 2.6. Notice

$$ \begin{align*} & d(\pi_{\beta'}(\alpha(i)a),\pi_{\beta'}(\beta'(j)))\\ &\quad\geq d(\alpha(i)a,\beta'(j)) - d(\alpha(i)a,\pi_{\beta'}(\alpha(i)a)) - d(\pi_{\beta'}(\beta'(j)),\beta'(j)))\\ &\quad\geq 2 \epsilon |a| - \epsilon |a| - B\\ &\quad\geq \epsilon (\log d(\beta'(j),\beta') + \log d(\alpha(i),\beta')) + K_1, \end{align*} $$

where $K_1$ is the constant from Lemma 2.6 taking $\delta = \epsilon $ . The last inequality holds when $|a|$ is sufficiently large. Then Lemma 2.6 implies that for some t,

$$ \begin{align*} d(\gamma(t), \alpha(i)a) & \leq d(\gamma (t), \pi_{\beta'}(\alpha(i))) + d(\pi_{\beta'}(\alpha(i)),\alpha(i)a) \\ & \leq (\epsilon \log |a| + K_1) + \epsilon |a| \\ & \leq 2 \epsilon |a| \end{align*} $$

for sufficiently large $|a|$ . Note that

$$ \begin{align*} t = d(\gamma(0),\gamma(t)) \le d(\alpha(i), \alpha(i) a) + 2\epsilon |a| \le \tfrac{3}{2} |a|. \end{align*} $$

Now, if

$$ \begin{align*} d(\pi_{\alpha}(\gamma(0)), \pi_{\alpha}(\gamma(M))) &> \epsilon \log (|j|+|a|)\\ & \geq \epsilon (\log d(\gamma(0),\alpha)+\log d(\gamma(M), \alpha)) - K_1, \end{align*} $$

where $K_1$ is the constant from Lemma 2.6 taking $\delta = \epsilon $ , then there exists $\tau \in [0, M]$ such that

$$ \begin{align*} d(\gamma(\tau), \pi_{\alpha}(\gamma(M))) \le \epsilon \log (|j| + |a|) + K_{1} \end{align*} $$

and $\gamma |_{[0, \tau ]}$ is contained in the $K_{1}$ -neighbourhood of $\alpha $ . Notice that $\tau $ cannot be larger than t, otherwise $\gamma (t)$ is $K_{1}$ -close to $\alpha $ ; let $p \in \alpha $ be the point such that $d(\gamma (t), p) \le K_{1}$ . Then, when $|a|$ is sufficiently large,

$$ \begin{align*} \begin{aligned} d(\alpha(i), \pi_{\alpha}(\alpha(i) a)) &\ge d(\alpha(i),p) - d(\pi_{\alpha}(\alpha(i) a), p) \\ &\ge d(\alpha(i) a, \alpha(i))) - d(\alpha(i)a,q) - (A d(p, \alpha(i) a) + 2B) \\ &\ge |a| - (A+1) (2 \epsilon |a|+ K_{1}) - 2B> \epsilon |a|. \end{aligned} \end{align*} $$

This is a contradiction, so we must have $\tau \le t$ . We then have

$$ \begin{align*} d(\pi_{\alpha} (\alpha(i) a \beta(0)^{-1} \beta(j)), \alpha(i)) &\le d(\pi_{\alpha}(\gamma(M)), \gamma(\tau)) + d(\gamma(\tau), \gamma(0)) \\ &\le \epsilon \log (|j| + |a|) + K_{1} + \tfrac{3}{2} |a| \\ &\le \epsilon \log |j| + 2|a|.\\[-35pt] \end{align*} $$

4 Probabilistic part

In this section, fixing a small enough $\epsilon>0$ , we study the situation where a random path $(\mathrm {id} =: Z_{0}, Z_{1}, \ldots , Z_{n})$ is seen by a superlinear-divergent direction, or to be precise, where $(Z_{i}, \ldots , Z_{i+\epsilon \log n})$ is (a part of) an $(f, \theta )$ -divergent quasigeodesic and

$$ \begin{align*} (\mathrm{id}, (Z_{i}, Z_{i+1}, \ldots, Z_{i+\epsilon \log n}), Z_{n}) \end{align*} $$

is $\epsilon ^{2}$ -aligned for some $i \ll n$ . We will prove in Corollary 4.6 and Lemma 4.7 that this happens with overwhelming probability.

To make an analogy, consider a random path $(\mathrm {id} =: Z_{0}, Z_{1}, \ldots , Z_{n})$ arising from a simple random walk on the Cayley graph of a free group $F_{2} \simeq \langle a, b \rangle $ . Here, we similarly expect that $Z_{n} = \mathrm {id}$ is not desirable and $(\mathrm {id}, (Z_{i}, Z_{i+1}), Z_{n})$ is aligned for some $i \ll n$ . In fact, the alignment fails with exponentially decaying probability. A classical argument using martingales can be described as follows:

1. (1) construct a ‘score’ that marks the progress made till step i;

2. (2) prove that at each step i, it is more probable to earn a score rather than lose one;

3. (3) sum up the difference at each step and use concentration inequalities to deduce an exponential bound.

Here, the score at step i should be determined by information up to time i. Moreover, when the score grows, the recorded local progresses should also pile up. To realize these features on a general Cayley graph other than tree-like ones, we employ the concatenation lemma proven in §3.

4.1 Combinatorial model

In the following, let $\gamma $ be an $(f, \theta )$ -divergent geodesic on G with $\gamma (0) = \mathrm {id}$ and $\epsilon>0$ be a small enough constant. Let us fix some constants:

• • $K_{3} = K_{3}(f, \theta , q, Q, A, B, \epsilon ^{3}, \epsilon )$ be as in Lemma 3.2;

• • K is larger than $K_{5} = K_{5}(({1}/{10q})\epsilon ^{4} )$ and the twice of $K_{6} = K_{6}(0.1\epsilon ^{4})$ given by Lemmas 3.5 and 3.6, respectively;

• • $N_{0}$ is a threshold such that

  $$ \begin{align*} \epsilon^{4} n> 10( K + K_{3}+ \log n) \end{align*} $$
  for all $n> N_{0}$ .

After multiple applications of our alignment lemmas, the exponent on $\epsilon $ will decrease, which is why we start with $\epsilon ^4$ .

Throughout this section, we will consider the following combinatorial model. Fix $w_{0}, w_{1}, \ldots \in G$ . Now, given a sequence of 3-tuples $s_{i} = (a_{i}, b_{i}, c_{i}) \in S^{3}$ , we consider a word of the form

$$ \begin{align*} W_{k} = w_{0} \cdot a_{1} \gamma(\epsilon \log n ) b_{1} \gamma(\epsilon \log n) c_{1} \cdot w_{1} \cdots a_{k} \gamma(\epsilon \log n ) b_{k} \gamma(\epsilon \log n) c_{k}\cdot w_{k}. \end{align*} $$

To ease the notation, let us also define

$$ \begin{align*} V_{k} = W_{k-1} a_{k}, \quad U_{k} = W_{k-1} a_{k} \gamma(\epsilon \log n) b_{k}. \end{align*} $$

We also denote

$$ \begin{align*}s = (a_1, b_1, c_1, \ldots, a_k, b_k, c_k).\end{align*} $$

We will argue that for most choices of $s \in S^{3k}$ , a certain subsequence of

$$ \begin{align*} (\mathrm{id},\, V_{1} \gamma|_{[0, \epsilon \log n]}, U_{1} \gamma|_{[0, \epsilon \log n]}\ldots, U_{k-1} \gamma|_{[0, \epsilon \log n]}, W_{k}) \end{align*} $$

is well aligned. In §4.2, we will derive from this a deviation inequality (Lemma 4.7) and deduce a central limit theorem.

To show well alignment, we argue analogously to [BMSS23, Gou22, Cho22], by keeping track of times in which the random walk may travel along different translates of $\gamma |_{[0, \epsilon \log n]}$ and arguing that, at most of these times, most directions of the random walk do not backtrack. To implement, we need the following Proposition 4.1. We remark that for the rest of the paper, whenever we discuss alignment of a sequence of points and geodesic segments, the only segments used are translates of $\gamma |_{[0, \epsilon \log n]}$ .

Proposition 4.1. Let $g \in G$ and let n be an integer greater than $N_{0}$ and $|g|$ . Let S be the subset of $\mathcal {S}(\mathrm {id}, K)$ described in Lemma 3.5 for $m=\epsilon \log n$ . Then for any distinct $a,b \in S$ , at least one of

$$ \begin{align*} (\gamma|_{[0, \epsilon \log n]}, \gamma(\epsilon \log n) ag) \quad\text{and}\quad (\gamma|_{[0, \epsilon \log n]}, \gamma(\epsilon \log n) bg ) \end{align*} $$

is $\epsilon ^{4} \log n$ -aligned. Likewise, at least one of

$$ \begin{align*} (a^{-1}g, \gamma|_{[0, \epsilon \log n]}) \quad \text{and} \quad (b^{-1}g, \gamma|_{[0, \epsilon \log n]}) \end{align*} $$

is $\epsilon ^{4} \log n$ -aligned.

Proof. We prove the first claim only. Let $t \in {\mathbb {Z}}$ be such that $\gamma (t) = \pi _{\gamma }(\gamma (\epsilon \log n) a g)$ . If t is greater than $ \epsilon (1- \epsilon ^{3} ) \log n$ , we deduce that $(\gamma |_{[0, \epsilon \log n]},\, \gamma (\epsilon \log n) a g)$ is $\epsilon ^{4} \log n$ -aligned as desired. Let us deal with the remaining case: we assume

(4.1) $$ \begin{align} t \in (-\infty, \epsilon \log n - \epsilon^{4} \log n ]. \end{align} $$

Consider two translates of $\gamma $ :

$$ \begin{align*} \gamma_{1} = a^{-1} \gamma(\epsilon \log n)^{-1} \gamma \quad\text{and}\quad \gamma_{2} = b^{-1} \gamma(\epsilon \log n)^{-1} \gamma, \end{align*} $$

and their subpaths

$$ \begin{align*} \gamma_{1}' := \gamma_{1}|_{[t, \epsilon \log n]} \quad \text{and} \quad \gamma_{2}' := \gamma_{2}|_{[0, \epsilon \log n]}. \end{align*} $$

Let $\bar {\gamma }_{2}'$ be the reversal of $\gamma _{2}'$ .

By the definition of t, $(\gamma (\epsilon \log n) a g, \gamma |_{[t, \epsilon \log n]})$ is automatically $0$ -aligned or, equivalently, $(g, \gamma _{1}')$ is $0$ -aligned. Next, since a and b are chosen from S, the subset of $\mathcal {S}(\mathrm {id}, K)$ as described in Lemma 3.5, we have that

$$ \begin{align*} \pi_{\gamma}(\gamma(\epsilon \log n) a b^{-1}) \quad\text{is within}\quad \mathcal{B}(\gamma(\epsilon \log n ), 0.1\epsilon^{4} |ab^{-1}|) \end{align*} $$

and

$$ \begin{align*} \pi_{\gamma}(\gamma(\epsilon \log n) b a^{-1}) \quad\text{is within}\quad \mathcal{B}(\gamma(\epsilon \log n), 0.1\epsilon^{4} |ab^{-1}|). \end{align*} $$

Moreover, we have

$$ \begin{align*} |ba^{-1}| \ge 0.5K \ge K_{6}. \end{align*} $$

By plugging in $\alpha = \gamma $ and $\beta = \bar {\gamma }$ (that is, $\beta (t) = \gamma (\epsilon \log n - t)$ for each $t \in {\mathbb {Z}}$ ), we can apply Lemma 3.6. The required assumptions are

$$ \begin{align*} \pi_{\beta}(\beta(0) (ba^{-1})^{-1}) &= \pi_{\gamma}(\gamma(\epsilon \log n) a b^{-1}) \\ &\in \mathcal{B}(\gamma(\epsilon \log n), 0.1\epsilon^{4} |ab^{-1}|) = \mathcal{B}(\beta(0), 0.1\epsilon^{4} |ab^{-1}|) \end{align*} $$

and

$$ \begin{align*} \pi_{\alpha}(\alpha(\epsilon \log n), ba^{-1}) = \pi_{\gamma}(\gamma(\epsilon \log n), ba^{-1}) \in \mathcal{B}(\gamma(\epsilon \log n), 0.1 \epsilon^{4}|ab^{-1}|). \end{align*} $$

As a result, for each $j \in {\mathbb {Z}}$ , we have

$$ \begin{align*} d (\pi_{\gamma}(\gamma(\epsilon \log n) ab^{-1} \gamma(\epsilon \log n)^{-1} \gamma(j)), \gamma(\epsilon \log n) ){\kern-1pt} \le{\kern-1pt} 0.1\epsilon^{4} \log |j-\epsilon \log n| {\kern-1pt}+{\kern-1pt} 2|ab^{-1}|. \end{align*} $$

In other words, we have

$$ \begin{align*} \pi_{\gamma_{1}}(\gamma_{2}') \in \gamma_{1}( (\epsilon \log n - 0.1\epsilon^{4} \log (\epsilon \log n) - 2K, +\infty)). \end{align*} $$

Similarly, we deduce that

$$ \begin{align*} \pi_{\gamma_{2}}(\gamma_{1}')\in \gamma_{2}( (\epsilon \log n -0.1\epsilon^{4} \log (\epsilon \log n) -2K, +\infty)). \end{align*} $$

We conclude that $(\gamma _{1}', \bar {\gamma }_{2}')$ is $(0.1\epsilon ^{4} \log (\epsilon \log n) + 2K)$ -aligned.

We now let $D = |g| + 2\epsilon \log n + 2K +K_{3}$ ; note that

$$ \begin{align*} D> \operatorname{\mathrm{\operatorname{diam}}}(g^{-1} \cup \gamma_{1}' \cup \gamma_{2}'). \end{align*} $$

Moreover, the lengths of $\gamma _{1}'$ and $\gamma _{2}'$ are at least $\epsilon ^{4} \log n$ and we have

$$ \begin{align*} \epsilon^{4} \log n \ge \epsilon^{3} \log D. \end{align*} $$

Finally, $(g, \gamma _{1}', \bar {\gamma }_{2}')$ is $(0.1\epsilon ^{4} \log m + 2K)$ -aligned, and hence $0.2 \epsilon ^{4} \log D$ -aligned. Lemma 3.2 now tells us that $(g^{-1}, \bar {\gamma }_{2}')$ is $\epsilon ^{4} \log D$ -aligned. This implies that $(\gamma |_{[0, m]}, \gamma (m) b g)$ is $\epsilon ^{4} \log n$ -aligned, as desired.

Following Boulanger et al [BMSS23] and Gouëzel [Gou22], we define the set of pivotal times $P_{k}(s)$ inductively. We will suppress the notation $P_k := P_k(s)$ when it is unambiguous, and the remaining notation follows from the beginning of this section. First, set $P_{0} = \emptyset $ and $z_{0} = \mathrm {id}$ . Given $P_{k-1} \subseteq \{1, \ldots , k-1\}$ and $z_{k-1} \in G$ , $P_{k}$ and $z_{k}$ are determined by the following criteria.

1. (a) When $(z_{k-1}, \,V_{k} \gamma |_{[0, \epsilon \log n]},\,U_{k} \gamma |_{[0, \epsilon \log n]}, W_{k} )$ is $\epsilon ^{3} \log n$ -aligned, we set $P_{k} = P_{k-1} \cup \{k\}$ and $z_{k} = U_{k}$ .

2. (b) Otherwise, we find the maximal index $m \in P_{k-1}$ such that $(V_{m} \gamma |_{[0. \epsilon \log n]}, W_{k})$ is $\epsilon ^{3} \log n$ -aligned and let $P_{k} = P_{k-1} \cap \{1, \ldots , m-1\}$ (that is, we gather all pivotal times in $P_{k-1}$ smaller than m) and $z_{k} = V_{m}$ . If such an m does not exist, then we set $P_{k} = \emptyset $ and $z_{k} = \mathrm {id}$ .

Given input $w_{0}, w_{1}, \ldots , w_{k} \in G$ and $s \in S^{3k}$ , this algorithm outputs a subset $P_{k}(s)$ of $\{1, \ldots , k\}$ . Our first lemma tells us that $P_{k}(s)$ effectively records the alignment.

Lemma 4.2. The following holds for all $n> N_{0}$ .

Let $P_{k} = \{i(1) < \cdots < i(M)\}$ and suppose that $\epsilon \log ( |w_{0}| + \cdots + |w_{k}| + k\epsilon \log n ) \le \log n$ . Then, there exists $ N \in \mathbb {N} $ and $g_{1}, \ldots , g_{N}= z_{k}$ such that $(V_{i(1)}, U_{i(1)}, \ldots , V_{i(M)}, U_{i(M)})$ is a subsequence of $(g_{1}, \ldots , g_{N})$ and

$$ \begin{align*} (\mathrm{id},\, g_{1} \gamma|_{[0, \epsilon \log n]}, \ldots, g_{N} \gamma|_{[0, \epsilon \log n]}, W_{k}) \end{align*} $$

is $\epsilon ^{2} \log n$ -aligned.

Proof. We induce on k. If we added a pivot, $P_{k} = P_{k-1} \cup \{k\}$ , there are the following two cases.

(1) $P_{k-1}= \emptyset $ . Then, $(\mathrm {id}, V_{k} \gamma |_{[0, \epsilon \log n]}, U_{k} \gamma |_{[0, \epsilon \log n]}, W_{k})$ is $(\epsilon ^{3} \log n)$ -aligned, with $z_{k} = U_{k}$ , as desired.

(2) $P_{k-1}= \{i(1) < \cdots < i(M-1)\}$ is non-empty. Then, there exist $g_{1}, \ldots , g_{N}$ such that $(V_{i(1)}, \ldots , V_{i(M-1)})$ is a subsequence of $(g_{1}, \ldots , g_{N})$ , $g_{N} = z_{k-1}$ and

$$ \begin{align*} (\mathrm{id},\, g_{1} \gamma|_{[0, \epsilon \log n]}, \ldots, g_{N} \gamma|_{[0, \epsilon \log n]}, W_{k-1}) \end{align*} $$

is $\epsilon ^{2} \log n$ -aligned. Moreover,

$$ \begin{align*}(z_{k-1}, V_{k}\gamma|_{[0, \epsilon \log n]}, U_{k} \gamma|_{[0, \epsilon \log n]}, W_{k})\end{align*} $$

is $(\epsilon ^{3} \log n)$ -aligned. Here, since $(z_{k-1} \gamma |_{[0, \epsilon \log n]}, W_{k-1})$ is $\epsilon ^{3} \log n$ -aligned,

$$ \begin{align*} (z_{k-1} \gamma|_{[0, \epsilon \log n]}, W_{k-1} a_{k}) = (z_{k-1} \gamma|_{[0, \epsilon \log n]}, V_{k}) \end{align*} $$

is also $(\epsilon ^{3} \log n + AK+B)$ -aligned. Now, Lemma 3.4 asserts that for large enough n, $(z_{k-1} \gamma |_{[0, \epsilon \log n]}, V_{k} \gamma |_{[0, \epsilon \log n]})$ is $\epsilon ^{2}\log n$ -aligned. As a result,

$$ \begin{align*} (\mathrm{id},\, g_{1} \gamma|_{[0, \epsilon \log n]}, \ldots, g_{N} \gamma|_{[0, \epsilon \log n]},\, V_{k}\gamma|_{[0, \epsilon \log n]}, \,U_{k}\gamma|_{[0, \epsilon \log n]}, W_{k}) \end{align*} $$

is $\epsilon ^{2}\log n$ -aligned, with $z_{k} = U_{k}$ .

Now, suppose we backtracked: $P_{k} = P_{k-1} \cap \{1, \ldots , m-1\}$ for some $m \in P_{k-1}$ . Letting $M = \#P_{k-1}$ , so that $\#P_k = M+1$ , our induction hypothesis tells us that there exist $g_{1}, \ldots , g_{N}$ such that $(V_{i(1)},U_{i(1)}, \ldots , V_{i(M+1)}, U_{i(M+1)})$ is a subsequence of $(g_{1}, \ldots , g_{N})$ and

$$ \begin{align*} (\mathrm{id},\, g_{1} \gamma|_{[0, \epsilon \log n]}, \ldots, g_{N} \gamma|_{[0, \epsilon \log n]}, W_{k-1}) \end{align*} $$

is $\epsilon ^{2} \log n$ -aligned. Moreover, we have that $(V_{i(M+1)} \gamma |_{[0, \epsilon \log n]}, W_{k})$ is $\epsilon ^{3} \log n$ -aligned by the criterion. It follows that

$$ \begin{align*} (\mathrm{id}, \, g_{1} \gamma|_{[0, \epsilon \log n]}, \ldots, V_{i(M+1)} \gamma|_{[0, \epsilon \log n]}, W_{k}) \end{align*} $$

is $\epsilon ^{2} \log n$ -aligned, with $z_{k} = V_{m} = V_{i(M+1)}$ , as desired.

Next, we have the following lemma.

Lemma 4.3. Let us fix $a_{1}, b_{1}, c_{1}, \ldots , a_{k}, b_{k}, c_{k}$ and draw $a_{k+1}$ , $b_{k+1}, c_{k+1}$ in $S^{3}$ according to the uniform measure. For $n \in \mathbb {N}$ sufficiently large, the probability that $\# P_{k+1} = \# P_{k} + 1$ is at least $9/10$ .

Proof. We need to choose $a_{k+1}$ , $b_{k+1}, c_{k+1}$ in $S^{3}$ such that

$$ \begin{align*} (z_{k}, \,V_{k+1} \gamma|_{[0, \epsilon \log n]},\,U_{k+1} \gamma|_{[0, \epsilon \log n]}, W_{k+1}) \end{align*} $$

is $\epsilon ^{3} \log n$ -aligned. By Proposition 4.1, there are at least 99 choices of $a_{k+1}$ such that

$$ \begin{align*} (z_{k}, \,V_{k+1} \gamma|_{[0, \epsilon \log n]}) \end{align*} $$

is $\epsilon ^{3} \log n$ -aligned.

Likewise, there are at least $98$ choices of $b_{k+1}$ such that both

$$ \begin{align*} (V_k, \,U_{k+1} \gamma|_{[0, \epsilon \log n]}) \quad\text{and}\quad (V_{k+1} \gamma|_{[0, \epsilon \log n]},\,U_{k+1}) \end{align*} $$

are $\epsilon ^4 \log n$ -aligned. From Lemma 3.4, for sufficiently large n, this tells us there are at least $98$ choices of $b_{k+1}$ such that $(V_{k+1} \gamma |_{[0, \epsilon \log n]},\,U_{k+1} \gamma |_{[0, \epsilon \log n]})$ is $\epsilon ^4 \log n$ -aligned.

Finally, there are at least $99$ choices of $c_{k+1}$ such that $(U_{k+1} \gamma |_{[0, \epsilon \log n]}, W_{k+1})$ is $\epsilon ^3 \log n$ -aligned.

We are done as ${99}/{100}\cdot {98}/{100} \cdot {99}/{100}> {9}/{10}$ .

Given a sequence $s =( a_{i}, b_{i}, c_{i})_{i=1}^{k}$ , we say that another sequence $s' = (a_{i}', b_{i}', c_{i}')_{i=1}^{k}$ is pivoted from s if they have the same pivotal times, $(a_{l}, c_{l}) = (a_{l}', c_{l}')$ for all $l=1, \ldots , k$ , and $b_{l} = b_{l}'$ for all l except for $l \in P_{k}(s)$ . We observe that being pivoted is an equivalence relation. The following lemma shows that these equivalence classes are large.

Lemma 4.4. Given $s =( a_{i}, b_{i}, c_{i})_{i=1}^{k}$ and a pivotal time $\ell \in P_k(s)$ , construct a new sequence $s'$ by replacing $b_\ell $ with another $b^{\prime }_{\ell }\in S$ such that

$$ \begin{align*}(z_{\ell-1}, \,V_{\ell} \gamma|_{[0, \epsilon \log n]},\,U_{\ell} \gamma|_{[0, \epsilon \log n]}, W_{\ell} )\end{align*} $$

is $\epsilon ^{3} \log n$ -aligned. Then, $s'$ is pivoted from s.

Proof. We need to show that both sequences s and $s'$ have the same set of pivotal times. Before time $\ell $ , the sequences are identical, so that $P_{j}(s) = P_{j}(s')$ for $j < \ell $ . By our choice of $b^{\prime }_\ell $ , we know that the time $\ell $ is added as a pivot, and so $z^{\prime }_\ell = U^{\prime }_{\ell }$ . Now we induce on $j> \ell $ : suppose that all pivotal times in $P_{j-1}(s)$ are still in $P_{j-1}(s')$ .

To determine $P_j(s)$ , either we added a new pivotal time j or we backtracked. In the former case, we have that $(z_{j-1}, \,V_{j} \gamma |_{[0, \epsilon \log n]},\,U_{j} \gamma |_{[0, \epsilon \log n]}, W_{j} )$ is $\epsilon ^3 \log n$ -aligned. Since G acts on itself by isometries, this happens if and only if the sequence

$$ \begin{align*} (z^{\prime}_{\ell}(z_{\ell}^{-1})z_{j-1}, z^{\prime}_{\ell}(z_{\ell}^{-1})V_{j} \gamma|_{[0, \epsilon \log n]}, z^{\prime}_{\ell}(z_{\ell}^{-1})U_{j} \gamma|_{[0, \epsilon \log n]}, z^{\prime}_{\ell}(z_{\ell}^{-1})W_{j} ) \end{align*} $$

is $\epsilon ^3 \log n$ -aligned. However, this is the same as requiring that

$$ \begin{align*}(z^{\prime}_{j-1}, \,V^{\prime}_{j} \gamma|_{[0, \epsilon \log n]},\,U^{\prime}_{j} \gamma|_{[0, \epsilon \log n]}, W^{\prime}_{j} )\end{align*} $$

is $\epsilon ^3 \log n$ -aligned, so that $j \in P_j(s')$ .

In the latter case, we found the maximum M such that $(V_{M} \gamma |_{[0. \epsilon \log n]}, W_{k})$ is $\epsilon ^{3} \log n$ -aligned. Since $\ell \in P_{k}(s) $ , we know that $M> \ell $ . Hence, this is the same as requiring that

$$ \begin{align*} (z^{\prime}_{\ell}(z_{\ell}^{-1})V_{M} \gamma|_{[0. \epsilon \log n]}, z^{\prime}_{\ell}(z_{\ell}^{-1})W_{k}) = (V^{\prime}_{M} \gamma|_{[0. \epsilon \log n]}, W^{\prime}_{k}) \end{align*} $$

is $\epsilon ^3 \log n$ -aligned. Therefore, $j \in P_{k}(s')$ .

Now fixing $w_{i}$ terms, we regard $W_{k}$ as a random variable depending on the choice of

$$ \begin{align*} (a_{1}, b_{1}, c_{1}, \ldots, a_{k}, b_{k}, c_{k}), \end{align*} $$

which are distributed according to the uniform measure on $S^{3k}$ .

Fixing a choice $s = (a_{1}, \ldots , c_k)$ , let $\mathcal {E}_{k}(s)$ be the set of choices $s'$ that are pivoted from s. Since being pivoted is an equivalence relation, the collection of $\mathcal {E}_k(s)$ terms partitions the space of sequences $S^{3k}$ . We claim that most of these equivalence classes are large: at pivotal times $\ell \in P_k$ , one can replace $b_\ell $ with one of many other $b^{\prime }_{\ell }$ terms while remaining pivoted.

Lemma 4.5. Let $s = (a_{1}, b_{1}, c_{1}, \ldots , a_{k}, b_{k}, c_{k})$ . Draw $(a_{k+1}, b_{k+1}, c_{k+1})$ according to the uniform measure on $S^{3}$ . Then, for all $j \ge 0$ ,

$$ \begin{align*} {\mathbb{P}}(\#P_{k+1}(s', s_{k+1}) < \#P_{k}(s') - j \, | \, (s', s_{k+1})\in \mathcal{E}_{k}(s) \times S^{3} ) \le (\tfrac{1}{10})^{j+1}. \end{align*} $$

We remark that the conditional measure ${\mathbb {P}}(\cdot | \mathcal {E}_k(s)\times S^3)$ on $S^{3(k+1)}$ is the same as the uniform measure on $\mathcal {E}_k(s) \times S^{3}\subset S^{3(k+1)}$ , because ${\mathbb {P}}(\cdot )$ is the uniform measure on a finite set.

Proof. We induce on $j\geq 0$ . The $j=0$ case is Lemma 4.3. We prove it for $j=1$ . Suppose that we made some choice of $s_{k+1} := (a_{k+1}, b_{k+1}, c_{k+1})$ that led to backtracking. We must show that for such an $s_{k+1}$ ,

$$ \begin{align*} {\mathbb{P}}(\#P_{n+1}(s', s_{k+1}) < \#P_{n}(s') - 1 \, | \, s' \in \mathcal{E}_{k}(s)) \le \tfrac{1}{10}. \end{align*} $$

To this end, we examine the final pivot $s_{\ell }$ . By Lemma 4.4, we can replace $b_{\ell }$ with any distinct $b^{\prime }_{\ell } \in S$ such that

$$ \begin{align*}(z_{\ell-1}, \,V_{\ell} \gamma|_{[0, \epsilon \log n]},\,U_{\ell} \gamma|_{[0, \epsilon \log n]}, W_{\ell})\end{align*} $$

is $\epsilon ^{4} \log n$ -aligned. There are at least $98$ choices of such a $b^{\prime }_{\ell }$ , by Proposition 4.1.

Likewise, there are at least $98$ choices of $b^{\prime }_{\ell } \neq b_{\ell }$ such that $(U_{\ell }\gamma _{[0, \epsilon \log n]}, W_k)$ is $\epsilon ^4 \log n$ -aligned. From Lemma 3.2, we know that

$$ \begin{align*}(V_{\ell} \gamma|_{[0, \epsilon \log n] }, \,W_k)\end{align*} $$

is $\epsilon ^3 \log n$ -aligned. For this choice of $s'$ , we have $P_{k+1}(s') = P_{k}(s') \cap \{0, \ldots , \ell - 1\}$ . In particular, $\#P_{k+1} = \#P_{k} - 1$ . Hence,

$$ \begin{align*} {\mathbb{P}}(\#P_{k+1} < \#P_{k} - 1 \, | \, \mathcal{E}_{k}(s), s_{k+1}) \le (\tfrac{4}{100}) < (\tfrac{1}{10}). \end{align*} $$

To handle the induction step for $j \geq 2$ , the same argument works, except we condition not only on $s_{k+1}$ but also on the final j pivotal increments which resulted in backtracking.

Corollary 4.6. Let $P_k$ be the set of pivotal times. Then we have

$$ \begin{align*} {\mathbb{P}} ( \#P_{k} \le k/2 ) < (1/10)^{k}. \end{align*} $$

4.2 Random walks

Recall that G contains an $(f, \theta )$ -superdivergent $(q,Q)$ -quasigeodesic $\gamma : {\mathbb {Z}}\rightarrow G$ with $\gamma (0) = \mathrm {id}$ .

Let $\mu $ be a probability measure on G whose support generates G as a semigroup. Passing to a convolution power if necessary, assume that $\mu (a)> 0$ for all a in our finite generating set $A \subset G$ . Let $(Z_n)_{n\geq 1}$ be the simple random walk generated by $\mu $ and let $\alpha \in (0,1)$ . We can define

$$ \begin{align*}\begin{aligned} p &= \min \{\mu(a), a \in A\},\\ \epsilon &=\frac{\alpha/100}{\log(1/p)}, \end{aligned} \end{align*} $$

so that $p^{\epsilon \log n} = n^{-\alpha /100}$ . Then for any path $\eta $ of length $100 \epsilon \log n$ and any $k \in {\mathbb {Z}}$ , we have

$$ \begin{align*} {\mathbb{P}}( (g_{k+1}, \ldots, g_{k+100 \epsilon \log n}) = \eta ) \ge n^{-\alpha}. \end{align*} $$

Also recall that for any three points $o,x,y \in G$ , we can define the Gromov product, given by

$$ \begin{align*}(x, y)_{o} = \tfrac{1}{2}(d(o,x) + d(o,y) - d(x,y) ).\end{align*} $$

We now have the following lemma.

Lemma 4.7. For any $0<\alpha < 1$ , there exists $K> 0$ such that for each $n \in \mathbb {N}$ and $x \in \mathcal {B}(\mathrm {id}, 2n)$ , we have

$$ \begin{align*} {\mathbb{P}}[(x, Z_{n})_{\mathrm{id}} \ge n^{3\alpha})] \le K e^{-n^{\alpha}/K}. \end{align*} $$

Proof. First, we would like to find a nice decomposition of our random walk, which will allow us to analyse the sample paths using our combinatorial model in §4.1.

Let $\overline {\unicode{x3bb} }_{i}$ be i.i.d. distributed according to the uniform measure on the subset $S' \subset G^5$ defined by

$$ \begin{align*} S' := \{(a, \gamma', b, \gamma', c) : a, b, c \in S, \gamma' = \gamma(\epsilon \log n)\}. \end{align*} $$

Then, the evaluation $\unicode{x3bb} _i = a\cdot \gamma '\cdot b \cdot \gamma ' \cdot c$ is distributed according to the measure $\mu _S * \gamma ' * \mu _S * \gamma ' * \mu _S$ , where $\mu _S$ is uniform over S.

Let $N = 3K + 2\epsilon \log n$ . By our choice of p, for each $a,b,c \in S$ , we have $\mu ^{*N} (a\gamma ' b \gamma ' c) \geq p^{N}$ . Then, we can decompose

$$ \begin{align*}\mu^{*N} = 10^6p^{N} (\mu_S * \gamma' * \mu_S * \gamma' * \mu_S) + (1-10^6 p^{N}) \nu\end{align*} $$

for some probability measure $\nu $ .

Now, we consider the following coin-toss model. Let $\rho _{i}$ be independent 0-1 valued random variables, each with probability $10^{6} \cdot p^{N}$ of being equal to 1. Also, let $\xi _{i}$ be i.i.d. distributed according to $\nu $ . We set

$$ \begin{align*}g_i = \begin{cases} \unicode{x3bb}_{i} & \mathrm{if}\ \rho_{i} = 1, \\ \xi_{i} & \mathrm{otherwise}. \end{cases}\end{align*} $$

Then, $(g_1 \cdots g_n)_n$ has the same distribution as $(Z_{Nn})$ , because each $g_i$ is distributed according to $\mu ^{*N}$ .

Hoeffding’s inequality tells us that

$$ \begin{align*} {\mathbb{P}}\bigg( \sum_{i=1}^{n^{3\alpha}} \rho_{i} \ge 0.5 n^{3\alpha} \cdot n^{-\alpha}\bigg) \ge 1 - 2 \exp \bigg( - \frac{2 (0.5 n^{2\alpha})^{2}}{n^{3\alpha}}\bigg) \ge 1 - 2 \exp (-0.5 n^{\alpha}). \end{align*} $$

After tossing away an event of probability at most $2\exp (-0.5n^{\alpha })$ , we assume $\sum _{i=1}^{n^{3\alpha }} \rho _{i} \ge 0.5 n^{2\alpha }$ .

To apply the analysis of our combinatorial model, we condition on the values of $\rho _i, \xi _{i}$ and only keep the randomness coming from the $\eta _{i}$ terms. Let

$$ \begin{align*}i(1) < i(2) < \cdots < i(M) \end{align*} $$

be the indices in $[1, n^{3\alpha }]$ , where $\rho _i = 1$ . Then, we can write

$$ \begin{align*} &x^{-1} \cdot Z_{n}\\ &\quad= w_{0} \cdot a_{1} \gamma(\epsilon \log n ) b_{1} \gamma(\epsilon \log n) c_{1} \cdot w_{1} \cdots a_{M} \gamma(\epsilon \log n ) b_{M} \gamma(\epsilon \log n) c_{M}\cdot w_{M}, \end{align*} $$

where

$$ \begin{align*} \begin{aligned} w_{0} &= x^{-1} g_{1} \cdots g_{N(i(1)-1) - 1},\\ w_{1} &= g_{Ni(1) + 1} \cdots g_{N(i(2)-1) - 1}, \\ &\vdots \\ w_{M} &= g_{Ni(M) + 1} \cdots g_{n} \end{aligned} \end{align*} $$

and $a_{i}, b_{i}, c_{i}$ are i.i.d.s distributed according to the uniform measure on S. As in the previous section, we set $s = (a_1,b_1,c_1, \ldots , a_M,b_M, c_M)$ . By Lemma 4.6, the set of pivots $P_{M}(s)$ is non-empty with probability at least $1-(1/10)^{M} \ge 1- (1/10)^{0.5 n^{2\alpha }}$ . By Proposition 3.3, for any pivotal time $i \in P_M(s)$ , we have

$$ \begin{align*} (\mathrm{id}, x^{-1} Z_{N(i-1)} \gamma|_{\epsilon \log n}, x^{-1} Z_{n}) = (\mathrm{id}, (x^{-1}Z_{N(i-1)}, \ldots, x^{-1}Z_{N(i-1)+\epsilon \log n}), x^{-1} Z_{n})\end{align*} $$

is $\epsilon \log n$ -aligned. Lemma 2.6 implies that $[\mathrm {id}, x^{-1} Z_{n}]$ passes through the $K_{1}$ - neighbourhood of $(x^{-1}Z_{N(i-1)}, \ldots , x^{-1}Z_{N})$ . In other words, $[x, Z_{n}]$ passes through the $(Ni + K_{0})$ -neighbourhood of $\mathrm {id}$ , which is within the $n^{3\alpha }$ -neighbourhood of $\mathrm {id}$ when n is large.

Corollary 4.8. For any $\alpha>0$ , there exists $K'$ such that for each $0 \le m \le n$ , we have

$$ \begin{align*} {\mathbb{E}}[(\mathrm{id}, Z_{n})_{Z_{m}}^{2}] \le n^{6\alpha} + K e^{-n^{\alpha}/K} \cdot n \le n^{6\alpha}+K'. \end{align*} $$

The following lemma states that our deviation inequality (Corollary 4.8) implies a rate of convergence in Fekete’s subadditivity lemma.

Lemma 4.9. Let

$$ \begin{align*}\unicode{x3bb} := \lim_{n\to \infty}\frac{1}{n} {\mathbb{E}}[d(\mathrm{id}, Z_{n})].\end{align*} $$

Then,

$$ \begin{align*}\unicode{x3bb} - \frac{1}{n}{\mathbb{E}}[d(\mathrm{id}, Z_{n})]= o\bigg(\frac{1}{\sqrt{n}}\bigg).\end{align*} $$

Proof. Note that by the definition of the Gromov product, we have

$$ \begin{align*} {\mathbb{E}}[d(\mathrm{id}, Z_{n2^{k}})] = \sum_{i=1}^{2^{k}} {\mathbb{E}}[d(Z_{n(i-1)}, Z_{ni})] - 2\sum_{i=1}^{k} \sum_{t = 1}^{2^{k-i}} {\mathbb{E}}[(Z_{n 2^{i}(t-1))}, Z_{n2^{i}t})_{Z_{n(2^{i}t - 1)}}]. \end{align*} $$

Also, by Corollary 4.8,

$$ \begin{align*} {\mathbb{E}}[(Z_{n 2^{i}(t-1))}, Z_{n2^{i}t})_{Z_{n(2^{i}t - 1)}}] \le 2(n2^{i-1})^{6\alpha} + K' \end{align*} $$

and we also know that ${\mathbb {E}}[d(Z_{n(i-1)}, Z_{ni})] = {\mathbb {E}}[d(\mathrm {id}, Z_{n})]$ for any $i \in \mathbb {N}$ . Hence, for any sufficiently small $\alpha>0$ , we have

$$ \begin{align*}\begin{aligned} \bigg|\frac{1}{2^{k}} {\mathbb{E}}[d(\mathrm{id}, Z_{n2^{k}})] - {\mathbb{E}}[d(\mathrm{id}, Z_{n})]\bigg| &\le \frac{2}{2^{k}} \sum_{i=1}^{k} 2^{k-i} \cdot (2(n2^{i-1})^{6\alpha} + K') \\ &\lesssim n^{6\alpha} \sum_{i=1}^{k} 2^{-i/2}. \end{aligned} \end{align*} $$

As $k \rightarrow \infty $ , the quantity $2^{-k} {\mathbb {E}}[d(\mathrm {id}, Z_{n2^{k}})]$ converges to L. Picking $\alpha < 1/12$ , we can send $k \rightarrow \infty $ and divide by n to conclude.

We now prove the CLT (Theorem A). It is essentially the same argument as [MS20], but with a different deviation inequality as input.

Proof. We claim that for any $\epsilon>0$ , there exists N sufficiently large, such that the sequence

$$ \begin{align*} \frac{1}{\sqrt{Nk}} (d(\mathrm{id}, Z_{Nk}) - {\mathbb{E}}[d(\mathrm{id}, Z_{Nk})]) \end{align*} $$

converges to a Gaussian distribution up to an error at most $\epsilon $ in the Lévy distance.

Indeed, the sequence

$$ \begin{align*} \bigg\{\frac{1}{\sqrt{k}} (d(\mathrm{id}, Z_{k}) - {\mathbb{E}}[d(\mathrm{id}, Z_{k})])\bigg\}_{k> 0} \end{align*} $$

is eventually $2\epsilon $ -close to a distribution X (in the Lévy distance) as long as its N-jump subsequence $\{{1}/{\sqrt {Nk}} (d(\mathrm {id}, Z_{Nk}) - {\mathbb {E}}[d(\mathrm {id}, Z_{Nk})] )\}_{k> 0}$ is eventually $\epsilon $ close to X for some $N \in \mathbb {N}$ . To see this, we note that the difference

$$ \begin{align*} \frac{1}{\sqrt{k}} (d(\mathrm{id}, Z_{k}) - {\mathbb{E}}[d(\mathrm{id}, Z_{k})]) - \frac{1}{\sqrt{k+1}} (d(\mathrm{id}, Z_{k+1}) - {\mathbb{E}}[d(\mathrm{id}, Z_{k+1})]) \end{align*} $$

is $O(k^{-1/2})$ with probability $1-o_k(1)$ (in fact, since the step sizes are bounded, this holds with probability $1$ , but when we consider unbounded step distributions, only $1-o_k(1)$ is necessary). Moreover, from Lemma 4.9, we know that

$$ \begin{align*}{\mathbb{E}}[d(\mathrm{id}, Z_{Nk})] = L Nk + o(\sqrt{Nk}).\end{align*} $$

To show the claim, we first take a sequence

$$ \begin{align*} 0 = j(0) < j(1) < \cdots < j(2^{\lfloor \log_{2} k \rfloor }) =k \end{align*} $$

such that $j(t+1) - j(t) = 1$ or $2$ for each t. The easiest way is to keep halving the numbers, that is,

$$ \begin{align*} j(2^{t}k) := \bigg\lfloor \frac{j(2^{t}(k-1)) + j(2^{t}(k+1))}{2} \bigg\rfloor \end{align*} $$

for each t and odd k. Let T be the collection of $j(t)$ terms such that $j(t+1) - j(t) = 2$ .

Then,

$$ \begin{align*} \frac{1}{\sqrt{Nk}} (d(\mathrm{id}, Z_{Nk}) - {\mathbb{E}}[d(\mathrm{id}, Z_{nk})] ) = I_1 - I_2 - I_3m, \end{align*} $$

where

$$ \begin{align*}I_1 = \sum_{i=1}^{k} \frac{1}{\sqrt{k}} \bigg[ \frac{d(Z_{N(i-1)}, Z_{Ni}) - {\mathbb{E}}[d(Z_{N(i-1)}, Z_{Ni})]}{\sqrt{N}}\bigg],\end{align*} $$

$$ \begin{align*}I_2 = \frac{2}{\sqrt{Nk}}\sum_{t \in T} ( (Z_{Nj(t)}, Z_{N(j(t)+2})_{Z_{N(j(t)+1})} - {\mathbb{E}}[(Z_{Nj(t)}, Z_{N(j(t)+2})_{Z_{N(j(t)+1})}]) \end{align*} $$

and

$$ \begin{align*}I_3 = \frac{2}{\sqrt{Nk}}\sum_{t=1}^{\lfloor \log_{2} k - 1 \rfloor}\! \sum_{l = 1}^{2^{\lfloor \log_{2} k \rfloor - t - 1}} \!\! ((Z_{N2^{t}l}, Z_{N2^{t} (l+2)})_{Z_{N2^{t}(l+1)}}\! - {\mathbb{E}}[(Z_{N2^{t}l}, Z_{N2^{t} (l+2)})_{Z_{N2^{t}(l+1)}}]).\end{align*} $$

We claim that for sufficiently large $N \in \mathbb {N}$ , $I_2$ and $I_3$ are small (in terms of the Lévy distance). Then the only non-negligible term $I_1$ is a sum of i.i.d random variables, normalized to converge to a Gaussian as $k \to \infty $ .

The second summation $I_{2}$ is the sum of at most k independent RVs whose variance is bounded by

$$ \begin{align*}\frac{4}{Nk} \cdot 3N^{6\alpha}. \end{align*} $$

Hence, the second summation has variance at most $12 N^{6\alpha -1}$ and

$$ \begin{align*}{\mathbb{P}}(|I_{2}| \ge N^{-\alpha}) \le 12 N^{8\alpha - 1}\end{align*} $$

by Chebyshev.

Now, for each t,

$$ \begin{align*} I_{3;t} := \frac{2}{\sqrt{Nk}}\sum_{l = 1}^{2^{\lfloor \log_{2} k \rfloor - t - 1}} ((Z_{N2^{t}l}, Z_{N2^{t} (l+2)})_{Z_{N2^{t}(l+1)}} - {\mathbb{E}}[(Z_{N2^{t}l}, Z_{N2^{t} (l+2)})_{Z_{N2^{t}(l+1)}}] ) \end{align*} $$

is the sum of at most $k/2^{t}$ independent RVs whose variance is bounded by ${4}/{Nk} \cdot 3 (N2^{t})^{6\alpha }$ . This means that $I_{3;t}$ has variance at most $12 N^{6\alpha - 1} \cdot 2^{(6\alpha - 1) t}$ and

$$ \begin{align*}{\mathbb{P}}(|I_{3; t}| \ge N^{-\alpha} 2^{-\alpha t}) \le 12 N^{8 \alpha - 1} 2^{(8\alpha - 1) t}\end{align*} $$

by Chebyshev.

Summing them up, we have

$$ \begin{align*}\bigg|I_{2} + \sum_{t} I_{3;t}\bigg| \le N^{-\alpha} \sum_{t} 2^{-\alpha t}\end{align*} $$

outside a set of probability $N^{8\alpha - 1} \sum _{t} 2^{(8 \alpha - 1) t}$ . These are small, regardless of the range of t. More precisely, by setting $\alpha = 1/10$ , we deduce that

$$ \begin{align*}|I_{2} + I_{3}| = O(N^{-1/10})\end{align*} $$

outside a set of probability $O(N^{-1/10})$ , ending the proof.

4.3 Some comments on Theorem A

We can also establish the CLT for random walks with finite pth moment for some $p>2$ . It suffices to show that Corollary 4.8 holds for such random walks.

For some $q> 0$ , let E be the event that $\sum _{i=1}^{n} |g_{i}|$ is at least $n^{q}$ . We note the following inequality:

$$ \begin{align*}\begin{aligned} {\mathbb{E}}[ n^{q (p-2)} \bigg( \sum_{i=1}^{n} |g_{i}| \bigg)^{2} 1_{\sum_{i=1}^{n} |g_{i}| \ge n^{q}} \bigg] &\le {\mathbb{E}} \bigg[ \bigg( \sum_{i=1}^{n} |g_{i}| \bigg)^{p} \bigg] \\ &\le {\mathbb{E}} \bigg[ ( n \max_{i=1}^{n} |g_{i}|)^{p}\bigg]\\ &\le n^{p} {\mathbb{E}} \bigg[ \sum_{i=1}^{n} |g_{i}|^{p}\bigg]\\ &\le n^{p+1} {\mathbb{E}} |g|^{p}. \end{aligned} \end{align*} $$

This implies that ${\mathbb {E}}[ (\sum _{i=1}^{n} |g_{i}| )^{2} 1_{E}] \le Cn^{(p+1) - q(p-2)}$ . By taking $q> ({p+1})/({p-2})$ , we can keep this bounded.

Now, on the event $E^c$ , we argue as in Lemma 4.7. We remark that the only place we used the finite support assumption was to invoke Lemma 4.2. In particular, we needed

$$ \begin{align*}\epsilon \log ( |w_{0}| + \cdots + |w_{k}| + k\epsilon \log n ) \le \log n,\end{align*} $$

where $w_i$ . However, on the event $E^c$ , this assumption is still met, replacing $\epsilon $ with $\epsilon /q$ if necessary. Then, we may still apply Lemma 4.2. Hence, we get

$$ \begin{align*} {\mathbb{E}}[(\mathrm{id}, Z_{n})_{Z_{m}}^{2}] \le n^{6\alpha} + K e^{-n\alpha/K} \le 2n^{6\alpha} + K'. \end{align*} $$

Given this estimate, we get the following theorem.

Theorem 4.10. Let G be a finitely generated group with exponential growth and suppose that G has a superlinear-divergent quasi-geodesic. Let $\mu $ be an admissible measure on G with finite p-moment for some $p> 2$ , and $(Z_{n})_{n}$ be the random walk on G generated by $\mu $ . Then, there exist constants $\unicode{x3bb} , \sigma \geq 0$ such that

$$ \begin{align*} \frac{|Z_{n}|-\unicode{x3bb} n}{ \sqrt{n}} \rightarrow \mathcal{N}(0, \sigma^2). \end{align*} $$

We now discuss the positivity of the escape rate $\unicode{x3bb} $ and the asymptotic variance $\sigma $ in Theorem A. We first recall a classical result about non-amenable groups [Gui80, Kes59].

Theorem 4.11. For any simple symmetric random walk $(Z_{n})_{n>0}$ on a non-amenable group, we have

$$ \begin{align*} \lim_{n \rightarrow \infty} \frac{{\mathbb{E}}[|Z_{n}|]}{n}> 0. \end{align*} $$

Using this theorem and [MS20, Theorem 4.12], we observe the following.

Theorem 4.12. Let G be a finitely generated non-amenable group and suppose that G has a superlinear-divergent quasi-geodesic $\gamma : {\mathbb {Z}} \rightarrow G$ . Let $(Z_{n})_{n\ge 1}$ be a simple symmetric random walk on G. Then, there exist $\unicode{x3bb} , \sigma> 0$ such that

$$ \begin{align*} \frac{|Z_{n}| - \unicode{x3bb} n}{\sqrt{n}} \rightarrow \mathcal{N}(0, \sigma^{2}). \end{align*} $$

Proof. First note that the escape rate $\unicode{x3bb} := \lim _{n} {\mathbb {E}}|Z_{n}|/n$ is positive by Theorem 4.11.

Let

$$ \begin{align*} \sigma_{n}^{2} := Var \bigg( \frac{1}{\sqrt{n}} d(\mathrm{id}, Z_{n}) \bigg). \end{align*} $$

In the proof of Theorem A, we showed that for each $\epsilon>0$ , for sufficiently large N,

$$ \begin{align*} \bigg\{\frac{1}{\sqrt{k}} (d(\mathrm{id}, Z_{k}) - {\mathbb{E}}[d(\mathrm{id}, Z_{k})] ) \bigg\}_{k\geq 1 } \end{align*} $$

converges to a Gaussian RV $\mathcal {N}(0, \sigma _{N}^{2})$ in distribution (by the classical CLT) up to an error of $O(N^{-1/10})$ in Lévy distance. From this, we deduce that $\sigma _{N}$ converges to a constant $\sigma \ge 0$ as N tends to infinity. If we show that $\sigma>0$ , then the sequence of random variables $\{{|Z_{n}| - {\mathbb {E}}|Z_{n}| }/{\sqrt {n}}\}_{n\geq 1}$ converges in distribution to a non-degenerate Gaussian $\mathcal {N}(0, \sigma ^{2})$ , as desired.

First, the proof of [MS20, Theorem 4.12] guarantees an $\epsilon>0$ such that

$$ \begin{align*} {\mathbb{E}} ((| Z_{2n}| - 2\unicode{x3bb} n)^{2} ) + {\mathbb{E}} ((| Z_{2n+ 2\lceil\sqrt{n}\rceil}| - 2\unicode{x3bb} n - 2\unicode{x3bb} \lceil\sqrt{n}\rceil)^{2} )> \epsilon n \end{align*} $$

holds for all large enough n. This follows from the fact that $\mu ^{\ast 2}$ puts non-zero weight on the identity element (since $\mu $ is symmetric), which implies that the even-step distributions $(Z_{2n})_{n>0}$ are $\{\mathrm {id}\}$ -consistent. Note that, even though [MS20, Theorem 4.12] is stated with the second moment deviation inequality assumption, the above claim only requires $\{\mathrm {id}\}$ -consistency. As a result, we conclude that

$$ \begin{align*} \limsup_{n} \frac{1}{n} {\mathbb{E}} ((| Z_{2n}| - 2\unicode{x3bb} n)^{2} )> \epsilon. \end{align*} $$

Now, observe that

$$ \begin{align*}\begin{aligned} \frac{1}{n} {\mathbb{E}} ((| Z_{2n}| - 2\unicode{x3bb} n)^{2} ) &= \frac{1}{n} {\mathbb{E}} ((| Z_{2n}| - {\mathbb{E}}|Z_{2n}| + {\mathbb{E}}|Z_{2n}| - 2\unicode{x3bb} n)^{2} )\\ &= \frac{1}{n} ({\mathbb{E}} ((| Z_{2n}| - {\mathbb{E}}|Z_{2n}|)^{2} ) + ( {\mathbb{E}}|Z_{2n}| - 2\unicode{x3bb} n)^{2} ), \end{aligned} \end{align*} $$

and $({\mathbb {E}}|Z_{2n}|-2\unicode{x3bb} n)^{2}$ is $o(n)$ by Lemma 4.9. Combining these, we also deduce that

$$ \begin{align*} \limsup_{n} \sigma_{n}^{2} = \limsup_{n} \frac{1}{n} {\mathbb{E}} ((| Z_{2n}| - {\mathbb{E}}|Z_{2n}|)^{2} )> \epsilon \end{align*} $$

and $\sigma = \lim _{n} \sigma _{n}> 0$ , as desired.