2 Preliminaries

2.2 Subgroup distortion

For a finitely generated subgroup S of a finitely generated group $\Gamma $ , the distortion function $\mathrm {Dist}^{\Gamma }_{S} : \mathbb {N} \to \mathbb {N}$ , with respect to fixed finite generating sets, is

$$ \begin{align*}\mathrm{Dist}^{\Gamma}_{S}\left(n\right) \ := \ \max \left\{\left|\gamma\right|{}_S \ \mid \ \gamma \in {S} \text{ with } \left|\gamma\right|{}_{\Gamma} \leq n \right\}\!.\end{align*} $$

3 Quantifications around Bézout’s Lemma

The following elementary estimates pertaining to Bézout’s Lemma play an important role in our proof. Lemma 3.1 follows a similar account in our paper [Reference Bridson and RileyBR26a]. We add Corollary 3.2 because it will lead to a bound on $|\sigma (w)|$ in Lemma 7.3 that is crucial in the final case of our proof that $\mathrm {CL}_{\Lambda }(n) \leq 2^n$ in Section 8; Corollary 3.3 is also called upon multiple times in that proof.

Proof Because $ax+by=c$ has a solution, $d = \gcd (a,b) $ divides c, and if $(x_0, y_0)$ is an integer solution, then the set of all such solutions is

$$ \begin{align*}\left\{ \left. \left(x_0 + \frac{b}{d} k , y_0 - \frac{a}{d} k\right) \, \right| \, k \in \mathbb{Z} \, \right\}\!.\end{align*} $$

Therefore, there exists a solution $(x,y)$ with $0 \leq x < \frac {b}{d}$ and another with $\frac {b}{d} \leq x < 0$ . Now, $y = \frac {c}{b} - \frac {a}{b} x$ , so $\frac {c}{b} - \frac {a}{d} < y \leq \frac {c}{b}$ for the first of these two solutions, and $ \frac {c}{b} < y \leq \frac {a}{d} + \frac {c}{b}$ for the second.

If $\frac {a}{d}$ and $\frac {c}{b}$ have the same sign, then $|\frac {c}{b} - \frac {a}{d}| \leq \max \left \{|\frac {c}{b}|, |\frac {a}{d}|\right \}$ and so the first of our two solutions satisfies the requirements of the lemma. If they have opposite signs, then similarly the second of our two solutions works.

Corollary 3.3 Suppose the linear Diophantine equation

(3.1) $$ \begin{align} a_1 x_1 + \cdots + a_m x_m = c \end{align} $$

has a solution $(x_1, \ldots , x_m)$ . Then it has a solution such that for all i,

(3.2) $$ \begin{align} |x_i| \leq \max \left\{|a_1|, \ldots, |a_m|, |c|\right\}\!. \end{align} $$

4 The structure of G

By way of reminder, $F = F(a_1, \ldots , a_m)$ is a rank-m free group, $H = F\rtimes _{\phi} \mathbb {Z}$ is hyperbolic, and G is the HNN-extension $H \dot \ast _F$ of H:

$$ \begin{align*} H & = \langle a_1, \ldots, a_m, s \mid s^{-1} a_i s = \phi(a_i) \ \ \forall i \rangle, \\G & = \langle H, t \mid [t,a_1]= \cdots = [t,a_m]=1 \rangle. \end{align*} $$

In preparation for the sections that follow, we shall describe some decompositions and retractions of G and establish useful notation.

We will work with the fixed basis $\{ a_1, \ldots , a_m \}$ for F, and to generate H, G, and $\Lambda $ , we add s, then t, and then $\lambda $ , respectively (paying attention to the fact that the role of t in $\Lambda $ is different from its role in G). Our generating set for the rank-2 free group E is $\{ s, t \}$ . For $g \in \Lambda $ , we write $| g |_{\Lambda }$ for the length of a shortest word in our generating set for $\Lambda $ representing g. We define $| g |_E$ , $| g |_F$ , $| g |_G$ , and $| g |_H$ likewise.

We have the semidirect product decomposition $G = F \rtimes E$ . We view E, F, and H as subgroups of G and will use three retractions:

• • $G {\kern 3pt\to \kern -8pt\to \kern 3pt} H$ killing t, denoted by $g \mapsto g_H$ ,

• • $G {\kern 3pt\to \kern -8pt\to \kern 3pt} E$ killing $a_1, \ldots , a_m$ , denoted by $g \mapsto g_E$ , and

• • $G {\kern 3pt\to \kern -8pt\to \kern 3pt} \mathbb {Z} \cong \langle s \rangle $ killing $a_1, \ldots , a_m, t$ denoted by $g \mapsto \sigma (g)$ .

Because these maps $G {\kern 3pt\to \kern -8pt\to \kern 3pt} H$ and $G {\kern 3pt\to \kern -8pt\to \kern 3pt} E$ are defined by killing certain generators,

(4.1) $$ \begin{align} \forall \gamma \in G, \ \max\left\{|\gamma_E |_E, | \gamma_H |_H\right\} \leq | \gamma |_G \end{align} $$

and because they are retracts,

(4.2) $$ \begin{align} \forall \gamma \in H, \ | \gamma |_G = | \gamma |_H \ \text{ and } \ \forall \gamma \in E, \ | \gamma |_G = | \gamma |_E. \end{align} $$

According to the decomposition $G = F \rtimes E$ , every $g \in G$ can be expressed uniquely as $g_F g_E$ for some $g_F \in F$ and the $g_E \in E$ that is defined above. Because t acts trivially on F,

(4.3) $$ \begin{align} \forall f \in F, \ \forall x \in E, \ \ x^{-1} f x = s^{-\sigma(x)} f s^{\sigma(x)} \text{ in } G. \end{align} $$

Define $E_0 := \ker ( \sigma : E \to \mathbb {Z})$ . This is the set of elements of E that commute with every element of F.

We extend the above notation to the level of words: if w is a word in $a_1, \ldots , a_m, s, t$ (the generators of G), then $w_H$ is the word obtained from w by deleting all letters $t^{\pm 1}$ , and $w_F$ and $w_E$ are the reduced words on $a_1, \ldots , a_m$ and on $s, t$ , respectively, such that $w = w_F w_E$ in G.

5 The distortion of $\langle \lambda \rangle $ in $\Lambda $

Here, we prove the following proposition.

We noted in the introduction that one can see that $\langle \lambda \rangle $ is infinite by observing that $\Lambda $ decomposes as $(H\times \langle \lambda \rangle )\rtimes \langle s,t \rangle $ . The upper bound on the distortion of $\langle \lambda \rangle $ that we require is a special case of a well-known general fact: if $1\to Z\to \widetilde {\Gamma }\to \Gamma \to 1$ is a central extension of a finitely presented group $\Gamma $ , and Z is finitely generated, then the distortion of Z in $\widetilde {\Gamma }$ is bounded above by the Dehn function of $\Gamma $ . In our case, a standard diagrammatic argument shows that the Dehn function of G is exponential. But we give a more detailed argument (Lemma 5.2) because features of its proof give a sharper estimate that will be needed in Section 8. It also provides a useful introduction to the use of the notation established in the previous section.

Lemma 5.2 There exists a constant $C>1$ such that if $\overline {W}$ is a word in the generators of $\Lambda $ and W is the word obtained from $\overline {W}$ by deleting all letters $\lambda ^{\pm 1}$ , then $\overline {W} = W_FW_E\lambda ^N$ in $\Lambda $ for some $N \in \mathbb {Z}$ and

(5.1) $$ \begin{align} |W_F| & \leq C^{|W|}, \end{align} $$

(5.2) $$ \begin{align} |W_E| & \leq |W|, \ \text{and} \end{align} $$

(5.3) $$ \begin{align} |N| & \leq |\ell| + \alpha C^{\Sigma\left(W\right)}, \end{align} $$

where $\ell $ is the exponent sum of the letters $\lambda ^{\pm 1}$ in $\overline {W}$ , $\alpha $ is the number of letters $a_1^{\pm 1}, \ldots , a_m^{\pm 1}$ in $\overline {W}$ , and $\Sigma \left (W\right )$ is the maximum of $\left |\sigma \left (W_0\right )\right |$ among all prefixes $W_0$ of W.

6 Conjugators in H and E

Accounts of the following proposition can be found in [Reference LysënokLys89], [Reference Bridson and HaefligerBH99, pp. 451–454], and [Reference Bridson, Riley and SaleBRS26]. The proof is a careful coarsening of an observation concerning conjugacy in finitely generated free groups: there, working with a free basis, two words represent conjugate elements if and only if they have cyclic permutations that are freely equal, which shows that the constant C of the following proposition can be taken to be $1$ in that setting.

So, given that H is hyperbolic and E is free, and given the length bounds (4.1) and (4.2), we deduce the following corollary.

Corollary 6.2 There is a constant $C>0$ such that if $u \sim v$ in G and $n := |u| + |v|$ , then there exist $x_0 \in E$ and $w_0 \in H$ such that $u_E x_0 = x_0 v_E$ in E and $u_H w_0 =w_0 v_H$ in H (and so in G), and

(6.1) $$ \begin{align} |x_0|_E & \leq n, \text{ and} \end{align} $$

(6.2) $$ \begin{align} |w_0|_H =|w_0|_G & \leq C n. \end{align} $$

We work with a torsion-free hyperbolic group H because the following well-known result – a consequence of Corollary 3.10 of [Reference Bridson and HaefligerBH99, Chapter III. $\varGamma$ ], for example – tells us that centralizers of elements in H have a straightforward structure. It will allow us to understand centralizers of elements in G in Lemma 7.1, which will then help us understand conjugacy.

We will also call on the following fact, which is of surprisingly recent origin [Reference BridsonBri25, Proposition 4.7].

In the context of G, Propositions 6.3 and 6.4 contribute to our next lemma.

Suppose u is a word on the generators of G. When $u_E$ , $u_F$ , and $u_H$ are non-identity elements, Proposition 6.3 applies to each and tells us that their centralizers in E, F, and H (respectively) are generated by maximal roots $u^{\prime }_E$ of $u_E$ , $u^{\prime }_F$ of $u_F$ , and $u^{\prime }_H$ of $u_H$ (respectively). Here, take $u^{\prime }_E$ to be a reduced word in $\left \{s,t\right \}^{\pm 1}$ , $u^{\prime }_F$ to be a reduced word in $\left \{a_1, \ldots , a_m\right \}^{\pm 1}$ , and $u^{\prime }_H$ to be a geodesic word in the generators for H. The following lemma records length bounds and in the cases of $u_F$ and $u^{\prime }_F$ gives contrasting bounds on word length $| \cdot |$ and on the lengths $| \cdot |_G$ of shortest representatives in G.

Lemma 6.5 There exists a constant $C> 1$ such that if u is a word of length at most n on the generators of G, then (when defined as explained above)

(6.3) $$ \begin{align} \max \{ |u_E|, |u_H| \} & \leq n, \end{align} $$

(6.4) $$ \begin{align} \max \{ |u^{\prime}_E|, |u^{\prime}_H| \} & \leq C n, \end{align} $$

(6.5) $$ \begin{align} \max \{ |u_F|, |u^{\prime}_F| \} & \leq C^n, \end{align} $$

(6.6) $$ \begin{align} |u_F|_G & \leq 2 n. \end{align} $$

7 Centralizers and conjugators in G

Our next lemma classifies the centralizers of elements in G. Its statement (ditto Lemma 7.2 that follows) implicitly assumes that the centralizers of $u_E \neq 1$ in E, $u_F \neq 1$ in F, and $u_H \neq 1$ in H are cyclic, which is true by Proposition 6.3 since these three groups are hyperbolic and torsion-free.

Lemma 7.2 Suppose $u, v \in G$ and that $u_E \neq 1$ , $u_H\neq 1$ , and $\sigma (u) \neq 0$ . Let $u_E'$ and $u_H'$ be generators for the centralizers of $u_E$ in E and $u_H$ in H (respectively). Suppose $x_0 \in E$ and $w_0 \in H$ are such that $u_E x_0 = x_0 v_E$ in E and $u_H w_0 = w_0 v_H$ in H.

Then $\sigma (u^{\prime }_H)$ and $\sigma (u^{\prime }_E)$ are nonzero. Further, $g \in G$ satisfies $ug=gv$ in G if and only if g is represented by a word $w = w_H s^{-\sigma (w)} w_E$ such that $w_H = (u^{\prime }_H)^p w_0$ in H and $w_E = (u^{\prime }_E)^q x_0$ in E and p and q are integers satisfying

(7.2) $$ \begin{align} p \, \sigma(u^{\prime}_H) - q \, \sigma(u^{\prime}_E) = \sigma(x_0) - \sigma(w_0). \end{align} $$

Proof The reason that $\sigma (u^{\prime }_H)$ and $\sigma (u^{\prime }_E)$ are nonzero is that $\sigma (u_H) \neq 0$ is a multiple of each.

We claim that a word $w \in G$ satisfies $uw = wv$ in G if and only if

(7.3) $$ \begin{align} u_H w_H & = w_H v_H \text{ in } H \text{ and } \end{align} $$

(7.4) $$ \begin{align} u_E w_E & = w_E v_E \text{ in } E. \end{align} $$

The “only if” direction is apparent from equating the images of $uw$ and $wv$ under the map $G {\kern 3pt\to \kern -8pt\to \kern 3pt} H$ and then under $G {\kern 3pt\to \kern -8pt\to \kern 3pt} E$ . For the “if” direction, we calculate that

(7.5) $$ \begin{align} u w & = u_H s^{- \sigma(u)} u_E w_H s^{- \sigma(w)} w_E \end{align} $$

(7.6) $$ \begin{align} & = u_H w_H s^{- \sigma(w)} s^{- \sigma(u)} u_E w_E \end{align} $$

(7.7) $$ \begin{align} & = w_H v_H s^{- \sigma(v)} s^{- \sigma(w)} w_E v_E \end{align} $$

(7.8) $$ \begin{align} & = w_H s^{- \sigma(w)} w_E v_H s^{- \sigma(v)} v_E \end{align} $$

(7.9) $$ \begin{align} & = w v \end{align} $$

because (7.6) $w_H s^{- \sigma (w)} \in F$ and $s^{- \sigma (u)} u_E \in E_0$ and so they commute, (7.7) by the hypotheses (7.3) and (7.4) hold and also by $\sigma (u) = \sigma (v)$ , which follows from either, and (7.8) $v_H s^{- \sigma (v)} \in F$ and $s^{- \sigma (w)} w_E \in E_0$ and so they commute.

The result then follows because any w satisfying these equivalent conditions must equal $w = w_F w_E = w_H s^{-\sigma (w_H)} w_E$ in G and have $w_H = (u^{\prime }_H)^p w_0$ in H for some $p \in \mathbb {Z}$ and $w_E = (u^{\prime }_E)^q x_0$ in E for some $q \in \mathbb {Z}$ . Further, (7.2) must hold because $\sigma (w_H) = \sigma (w_E)$ .

The following lemma shows that $\mathrm {CL}_G(u,v)$ is at most a constant times $(|u| + |v|)^2$ under the hypotheses of Case (e) of Lemma 7.1. In fact, $\mathrm {CL}_G(u,v)$ is at most a constant times $|u| + |v|$ in Cases (a)–(d), and so $\mathrm {CL}_G\left (n\right ) \preceq n^2$ . Most of the estimates establishing this can be found within our arguments in Section 8, but it is not a result we will need, so we do not include an explicit proof.

Like in Lemma 5.2, $\Sigma \left (w\right )$ denotes the maximum of $\left |\sigma \left (w_0\right )\right |$ among all prefixes $w_0$ of w.

Lemma 7.3 There exists a constant $C_0>0$ such that for all words u and v as per Lemma 7.2, there exists a word w such that $uw =wv$ in G and

(7.10) $$ \begin{align} |w|_G & \leq C_0 n^2, \end{align} $$

(7.11) $$ \begin{align} \Sigma(w) & \leq C_0 n, \end{align} $$

(7.12) $$ \begin{align} |\sigma(w)| & \leq C_0 n. \end{align} $$

Proof Let C be the maximum of the constants of Corollary 6.2 and Lemma 6.5. Lemma 6.5 applies to u and, given that $|u^{\prime }_E|_E = |u^{\prime }_E|_G$ and $|u^{\prime }_H|_H = |u^{\prime }_H|_G$ , tells us that

(7.13) $$ \begin{align} \max \{ |u^{\prime}_E|_E, |u^{\prime}_H|_H \} \leq C n. \end{align} $$

Per Corollary 6.2, let $x_0 \in E$ and $w_0 \in H$ be such that $u_E x_0 = x_0 v_E$ in E and $u_H w_0 = w_0 v_H$ in H and

(7.14) $$ \begin{align} |x_0| \leq n \ \text{ and } \ |w_0| \leq C n. \end{align} $$

If w is any conjugator as per Lemma 7.2, then

(7.15) $$ \begin{align} w = w_H s^{-\sigma(w)} w_E = (u^{\prime}_H)^p w_0 s^{-\sigma(w)} (u^{\prime}_E)^q x_0 \end{align} $$

so that $w_H = (u^{\prime }_H)^p w_0$ in H and $w_E = (u^{\prime }_E)^q x_0$ in E, and p and q are integers satisfying (7.2). And then, by the triangle inequality and then (7.13) and (7.14),

(7.16) $$ \begin{align} |w|_G & \leq |p| \, |u^{\prime}_H|_H + |w_0| + |\sigma(w)| + |q| \, |u^{\prime}_E|_E + |x_0| \end{align} $$

(7.17) $$ \begin{align} &\leq C_1 n \, \max \left\{|p|, |q|\right\} \end{align} $$

for a suitable constant $C_1> 0$ .

Now, $u \sim v$ and so there exists such a conjugator w and therefore there exist integers p and q satisfying (7.2). But then, because $\sigma (u^{\prime }_H)$ and $\sigma (u^{\prime }_E)$ are nonzero, Corollary 3.2 applies so as to tell us that there exist integers p and q satisfying (7.2) such that

(7.18) $$ \begin{align} |p \sigma(u^{\prime}_H)| & \leq \operatorname{\mathrm{lcm}} \left\{|\sigma(u^{\prime}_H)|, |\sigma(u^{\prime}_E)|\right\} \ \text{ and} \end{align} $$

(7.19) $$ \begin{align} |q \sigma(u^{\prime}_E)| & \leq \max \left\{ \operatorname{\mathrm{lcm}} \left\{|\sigma(u^{\prime}_H)|, |\sigma(u^{\prime}_E)|\right\}, |\sigma(x_0) - \sigma(w_0)|\right\}. \end{align} $$

Both $\sigma (u^{\prime }_H)$ and $\sigma (u^{\prime }_E)$ divide $\sigma (u)$ , and so $ {\operatorname {\mathrm {lcm}} \left \{|\sigma (u^{\prime }_H)|, |\sigma (u^{\prime }_E)|\right \} \leq |\sigma (u)| \leq n}$ . And $|\sigma (x_0) - \sigma (w_0)| \leq |\sigma (x_0)| + |\sigma (w_0)| \leq |x_0|_G + |w_0|_G \leq (1 + C) n$ , the last by (7.14). So

(7.20) $$ \begin{align} \max \left\{|p \sigma(u^{\prime}_H)|, |q \sigma(u^{\prime}_E)|\right\} \leq (1 +C)n. \end{align} $$

Because $\sigma (u^{\prime }_H)$ and $\sigma (u^{\prime }_E)$ are nonzero integers, (7.20) implies that

(7.21) $$ \begin{align} \max \left\{|p|, |q|\right\} \leq (1+ C)n. \end{align} $$

And, for a suitable constant $C_0$ , the conjugator w associated with this p and q per (7.15) witnesses to the bound (7.10) because of (7.17) and (7.21).

Finally, we will explain why this w witnesses to the three bounds claimed in the lemma. The bound (7.10) holds because of (7.17) and (7.21). For (7.11), first observe that any prefix $\pi $ of $(u^{\prime }_H)^p$ has $|\sigma (\pi )|$ at most a constant times n because of (7.20) and because $|u^{\prime }_H|$ is at most a constant times n by Lemma 6.5. The same holds for any prefix of $(u^{\prime }_E)^q$ , likewise.

So (7.11) holds because the remainder of $w = (u^{\prime }_H)^p w_0 s^{-\sigma (w)} (u^{\prime }_E)^q x_0$ – namely, $w_0$ , $s^{-\sigma (w)}$ , and $x_0$ – has total length at most a constant times n.

Finally, the bound (7.12) follows immediately from (7.11).

8 Why $\mathrm {CL}_{\Lambda }(n) \preceq 2^n$

We again recall the context: $\Lambda $ is the central extension of G constructed as

$$ \begin{align*} H & = \langle a_1, \ldots, a_m, s \mid s^{-1} a_i s = \phi(a_i) \ \ \forall i \rangle, \\G & = \langle H, t \mid [t,a_1]= \cdots = [t,a_m]=1 \rangle, \\\Lambda & = \langle H, t, \lambda \mid [t,a_1]= \cdots = [t,a_m]=\lambda, \ \lambda \text{ central} \rangle. \end{align*} $$

A word in $a_1, \ldots , a_m, s, t$ can represent an element $g \in G$ or $\overline {g} \in \Lambda $ , with $\overline {g}$ being a particular lift of g. Both contexts will arise in our proof and we will take care to distinguish them.

A number of constants $C_i$ will arise in the following proof. All will be independent of n, but they may depend on $\Lambda $ , m, and our choices of generating sets.

Suppose $\overline {u}$ and $\overline {v}$ are words on the generators of $\Lambda $ such that $\overline {u} \sim \overline {v}$ in $\Lambda $ . Let ${n = |\overline {u}| + |\overline {v}|}$ .

Let u and v be the words obtained from $\overline {u}$ and $\overline {v}$ , respectively, on deleting all letters $\lambda ^{\pm 1}$ . Then $u \sim v$ in G and $|u| + |v| \leq n$ . If we write $L_u$ and $L_v$ for the exponent-sums of the letters $\lambda ^{\pm 1}$ in $\overline {u}$ and $\overline {v}$ , respectively, then $\overline {u} = u \lambda ^{L_u}$ and $\overline {v} = u \lambda ^{L_v}$ in $\Lambda $ and

(8.1) $$ \begin{align} |L_u| + |L_v| \leq n. \end{align} $$

Lemma 6.5 applies to both u and v (when $u_E$ , $u_F$ , $u_H$ , $v_E$ , $v_F$ , and $v_H$ are non-identity elements). We will call on the estimates it gives in what follows.

Lemma 7.1 sets out the structure of $Z_G(u)$ in five mutually exclusive cases. We will examine those cases in turn and find suitable upper bounds for $\mathrm {CL}_{\Lambda }(\overline {u},\overline {v})$ .

Case (a). $u =1$ in G, and so $Z_G(u) = G$ . In this case, $v=1$ in G also and $\overline {u}$ and $\overline {v}$ are central in $\Lambda $ , and so $\mathrm {CL}_{\Lambda }(\overline {u},\overline {v}) =0$ .

Case (b). $u_H =1$ in H and $u \neq 1$ in G, and so $Z_G(u) = F \times \langle u_E' \rangle $ . In this case, $u=u_E$ and $v=v_E$ in G and $\sigma (u) = \sigma (v)=0$ . And $|u_E| \leq |u|$ and $|v_E| \leq |v|$ , and so ${|u_E| + |v_E| \leq n}$ . So, given that $\mathrm {Dist}_{\langle \lambda \rangle }^{\Lambda } \left (n\right ) \simeq 2^n$ (by Proposition 5.1), for a suitable constant $C_1>0$ , we have that in $\Lambda $ ,

(8.2) $$ \begin{align} u = u_E \lambda^{L^{\prime}_u} \text{ and } v = v_E \lambda^{L^{\prime}_v} \text{ for some } L^{\prime}_u, L^{\prime}_v \in \mathbb{Z} \text{ with } |L^{\prime}_u|, |L^{\prime}_v| \leq C_1^n. \end{align} $$

Now, $u_E \sim v_E$ in E, and so by Corollary 6.2, there exists $x_0 \in E$ such that ${u_E x_0 = x_0 v_E}$ in E and $|x_0|_E \leq n$ . Because $Z_G(u) = \left \{ f \, (u^{\prime }_E)^q \mid f \in F, q \in \mathbb {Z} \right \}$ , the words w such that $uw = wv$ in G are those expressible as $w = f \, (u^{\prime }_E)^q x_0$ for some $f \in F$ and $q \in \mathbb {Z}$ . For such a w, we have $u w = wv$ in G and so $u w = wv \lambda ^N$ in $\Lambda $ for some $N \in \mathbb {Z}$ . Indeed, in $\Lambda $ ,

(8.3) $$ \begin{align} u w & = u_E f \left(u^{\prime}_E\right)^q x_0 \ \lambda^{L^{\prime}_u} \end{align} $$

(8.4) $$ \begin{align} & = f \left(u^{\prime}_E\right)^q u_E x_0 \ \lambda^{L^{\prime}_u+L} \end{align} $$

(8.5) $$ \begin{align} & = f \left(u^{\prime}_E\right)^q x_0 v_E \ \lambda^{L^{\prime}_u+L} \end{align} $$

(8.6) $$ \begin{align} & = w v \lambda^{L^{\prime}_u-L^{\prime}_v+L}, \end{align} $$

where for (8.3) and (8.6), we use (8.2), for (8.4), we use that in $\Lambda $

(8.7) $$ \begin{align} u_E f = f u_E \lambda^L \end{align} $$

for some $L \in \mathbb {Z}$ and $u_E$ commutes with $u^{\prime }_E$ , and for (8.5), we use that $u_e x_0 =x_0 v_E$ in E and so in $\Lambda $ .

So, because $\overline {u} = u \lambda ^{L_u}$ and $\overline {v} = v \lambda ^{L_v}$ in $\Lambda $ , we have $ \overline {u} w = w \overline {v}$ in $\Lambda $ if and only if ${L = L_v - L_u + L^{\prime }_v - L^{\prime }_u}$ . Because $\overline {u} \sim \overline {v}$ in $\Lambda $ , there exists $f \in F$ such that (8.7) holds for this value of L.

For $i =1, \ldots , m$ , we have $u_E a_i = a_i u_E$ in G because $\sigma (u_E) = \sigma (u)=0$ . So ${u_E a_i = a_i u_E \lambda ^{n_i}}$ in $\Lambda $ for a unique integer $n_i$ . Let $\alpha _i$ be the exponent-sum of the letters $a_i$ in f. Then from (8.7), we get that

(8.8) $$ \begin{align} L = \alpha_1 n_1 + \cdots + \alpha_m n_m. \end{align} $$

Because $|u_E| \leq C n$ by (6.4), Proposition 5.1 gives that for a suitable constant $C_2>1$ , for all i,

(8.9) $$ \begin{align} |n_i| \leq C_2^n. \end{align} $$

Now, $|L| \leq C_3^n$ for a suitable constant $C_3>1$ by (8.1) and (8.2). Given our quantification of Bézout of Corollary 3.3, these estimates tell us that there exist $\alpha _1, \ldots , \alpha _m$ satisfying (8.8) with $|\alpha _i| \leq \max \{C_2^n, C_3^n\}$ for all i. But then $f = a_1^{\alpha _1} \ldots a_m^{\alpha _m}$ satisfies (8.7) and, calling on (6.1), we get that $w = f x_0$ is a word of length at most $C_4^n$ for a suitable constant $C_4>1$ such that $\overline {u} w = w \overline {v}$ in $\Lambda $ , as required. (In the above analysis, the value of q in w played no role, so we can choose it to be zero.)

Case (c). $u_E =1$ and $u_H \neq 1$ , and so $Z_G(u) = \langle u^{\prime }_F \rangle \times E_0$ . In this case, $u=u_F$ and ${v=v_F}$ in G and $\sigma (u) = \sigma (v)=0$ . By (6.5), $\max \left \{ |u_F|, |u^{\prime }_F|, |v_F|\right \} \leq C_1^{n}$ . Further, because $|u|_G + |v|_G \leq n$ and, by (6.6), $\max \left \{|u_F|_G, |v_F|_G\right \} \leq C_0 n$ , and so there exists a constant $C_5>1$ such that $u = u_F \lambda ^{L^{\prime }_u}$ and $v = v_F \lambda ^{L^{\prime }_v}$ in $\Lambda $ for some integers,

(8.10) $$ \begin{align} |L^{\prime}_u| + |L^{\prime}_v| \leq C_5^{n}. \end{align} $$

Now, $u \sim v$ in H and so by Corollary 6.2, there exists a $w_0 \in H$ such that $u w_0 =w_0 v$ in H (and so in G) and, for a suitable constant $C_6>1$ ,

(8.11) $$ \begin{align} |w_0|_G = |w_0|_H \leq C_6\left(|u|_H + |v|_H\right) \leq C_6 n. \end{align} $$

Because $Z_G\left (u\right ) = \langle u^{\prime }_F \rangle \times E_0$ , the elements of G that conjugate u to v in G are those represented by the words $w =\left (u^{\prime }_F\right )^p x w_0$ for $p \in \mathbb {Z}$ and $x \in E_0$ . We calculate in $\Lambda $ that for such w,

(8.12) $$ \begin{align} u w & = u_F \left(u^{\prime}_F\right)^p x w_0 \ \lambda^{L^{\prime}_u } \end{align} $$

(8.13) $$ \begin{align} & = \left(u^{\prime}_F\right)^p x u_F w_0 \lambda^{L+L^{\prime}_u} \end{align} $$

(8.14) $$ \begin{align} & = \left(u^{\prime}_F\right)^p x w_0 v_F \lambda^{L+M+L^{\prime}_u} \end{align} $$

(8.15) $$ \begin{align} & = w v \lambda^{L+M+ L^{\prime}_u- L^{\prime}_v } \end{align} $$

because (8.12) $u = u_F \lambda ^{L^{\prime }_u}$ , (8.13) $u_F$ and $u^{\prime }_F$ commute and

(8.16) $$ \begin{align} u_F x = x u_F \lambda^{L} \end{align} $$

for some $L \in \mathbb {Z}$ , (8.14) $u_F w_0= w_0 v_F \lambda ^{M}$ for some $M \in \mathbb {Z}$ , and (8.15) $v = v_F \lambda ^{L^{\prime }_v}$ . Then, because $\overline {u} = u \lambda ^{L_u}$ and $\overline {v} = v \lambda ^{L_v}$ in $\Lambda $ , for $\overline {u} w = w \overline {v}$ in $\Lambda $ , we must have

(8.17) $$ \begin{align} L = L_v - L_u - M - L^{\prime}_u + L^{\prime}_v. \end{align} $$

Now, $|M| \leq C_7^n$ for a suitable constant $C_7>1$ by Proposition 5.1 given (6.2) and that $\max \left \{|u_F|_G, |v_F|_G\right \} \leq C_0 n$ . In light of this, (8.1), and (8.10), equation (8.17) then tells us that for a suitable constant $C_8>1$ ,

(8.18) $$ \begin{align} |L| \leq C_8^n. \end{align} $$

Because $E_0$ is generated by $\left \{s^{-i} t s^i \mid i \in \mathbb {Z} \right \}$ , we get the following observation.

Observation The set $\mathcal {L}$ of integers L such that $x^{-1} u_F x = u_F \lambda ^{L}$ in $\Lambda $ for some $x \in E_0$ is the ideal $(\mathcal {L}) \leq \mathbb {Z}$ generated by the integers $\left \{ L_i | i \in \mathbb {Z}\right \}$ defined by

$$ \begin{align*}(s^{-i} t s^i)^{-1} u_F (s^{-i} t s^i) = u_F \lambda^{L_i}.\end{align*} $$

Claim $\mathcal {L}$ equals the ideal $\mathcal {L}' = ( L_0, \ldots , L_{m-1} )$ . For $i=1, \ldots , m$ , let $\alpha _i$ be the exponent-sum of the letters $a_i$ in $u_F$ . Let $\Phi \in \text {GL}_m(\mathbb {Z})$ be the $m \times m$ matrix of the map (with respect to the basis $a_1$ , …, $a_m$ ) induced by $\phi : F \to F$ on abelianizing F. Then

(8.19) $$ \begin{align} L_i = \begin{bmatrix} 1 & \!\!\cdots\!\! & 1 \end{bmatrix} \ \Phi^i \begin{bmatrix} \alpha_{1} \\ \vdots \\ \alpha_{m} \end{bmatrix}. \end{align} $$

By the Cayley–Hamilton theorem, $\Phi ^m$ is a $\mathbb {Z}$ -linear combination of $\Phi ^{m-1}, \ldots , \Phi , I$ and so $L_i \in \mathcal {L}'$ for all $i \geq m$ . Indeed, the constant term of the characteristic polynomial of $\Phi $ is $\text {det}(\Phi ) = \pm 1$ . So $\Phi $ can be expressed as a $\mathbb {Z}$ -linear combination of $\Phi ^2, \ldots , \Phi ^{m+1}$ . So $L_i \in \mathcal {L}'$ for all $i <0$ . Therefore, $\mathcal {L} = \mathcal {L}'$ as claimed.

Because $\overline {u} \sim \overline {v}$ in $\Lambda $ , the L of (8.17) is in $\mathcal {L}$ and there exists $x \in F$ such that (8.16) holds.

In the light of the above claim, we learn from Corollary 3.3 that there exist $n_0, \ldots , n_{m-1} \in \mathbb {Z}$ such that

(8.20) $$ \begin{align} L = n_0 L_0 + \cdots + n_{m-1} L_{m-1} \end{align} $$

and for all i,

(8.21) $$ \begin{align} |n_i| \leq \max \{ |L_0|, \ldots, |L_{m-1}|, |L | \}. \end{align} $$

But for a suitable constant $C_9>1$ , $|L_{j}| \leq C_9^{|j|} |u_F|$ for all $j \in \mathbb {Z}$ . So, for the constant $C_{10} = C_9^{|m-1|}$ ,

$$ \begin{align*}\max \{ |L_0|, \ldots, |L_{m-1}| \} \leq C_{10} |u_F|\end{align*} $$

and therefore, in light also of the bounds on $|u_F|$ from (6.5) and on $|L|$ from (8.18), for a suitable constant $C_{11}>1$ , we have $|n_i| \leq C_{11}^n$ for $i = 0, \ldots , m-1$ . So

$$ \begin{align*}x = (s^{-0} t^{n_0} s^0) \ (s^{-1} t^{n_1} s^1) \ \ldots \ (s^{-(m-1)} t^{n_{m-1}} s^{m-1})\end{align*} $$

is an element of $E_0$ for which $x^{-1} u_F x = u_F \lambda ^{L}$ and $|x| \leq C_{12}^n$ for a suitable constant ${C_{12}>0}$ . And then $w = x w_0$ satisfies $ \overline {u} w = w \overline {v}$ and, given (6.2), we learn that w is sufficiently short.

Case (d). $\sigma (u) =0$ , $u_E \neq 1$ , and $u_H \neq 1$ , and so $Z_G(u) = \langle u^{\prime }_F \rangle \times \langle u_E' \rangle $ .

We have $u_H \sim v_H$ in H, and so like in Case (c), there exists $w_0 \in H$ such that

(8.22) $$ \begin{align} u_H w_0 =w_0 v_H \text{ in } H \text{ and } |w_0|_G \leq C_6 n. \end{align} $$

Also, $u_E \sim v_E$ in E, and so like in Case (b), there exists $x_0 \in E$ such that

(8.23) $$ \begin{align} u_E x_0 = x_0 v_E \text{ in } E \text{ and } |x_0| \leq n. \end{align} $$

There exists $w \in G$ such that $u w =w v$ in G, and therefore such that $u_E w_E = w_E v_E$ in E and $u_H w_H =w_H v_H$ in H. Now, $u_E$ is a power of $u^{\prime }_E$ and $\sigma (u_E) = \sigma (u) =0$ , and so $\sigma (u^{\prime }_E)=0$ . So $\sigma (x_0) = \sigma (w_E)$ because $w_E^{-1} x_0 \in Z_E(u_E) = \langle u^{\prime }_E \rangle $ . For a similar reason, $\sigma (w_0) = \sigma (w_H)$ . But then $\sigma (x_0) = \sigma (w_0)$ because $\sigma (w) = \sigma (w_E) = \sigma (w_H)$ .

Next, observe that $u_H = u_F$ and $v_H = v_F$ because $\sigma (u) =0$ . So $u_F w_H = u_H w_H =w_H v_H = w_H v_F$ . Then $u_F w_H = w_H v_F$ because $w_H = w_F s^{\sigma (w)}$ and $\sigma (x_0) = \sigma (w_0)$ .

That $\sigma (x_0) = \sigma (w_0)$ implies that for $f \in F$ , we have $s^{-\sigma (w_0)} f s^{\sigma (w_0)} = x_0^{-1} f x_0$ in G. So, given that $w_0 = (w_0)_F s^{\sigma (w_0)}$ and $u_H w_0 =w_0 v_H$ ,

(8.24) $$ \begin{align} u_F (w_0)_F x_0 = (w_0)_F x_0 u_F \end{align} $$

in G. Let $w_1$ be a minimal-length word that equals $(w_0)_F x_0$ in G. Then, in G,

(8.25) $$ \begin{align} u w_1 & = u_F u_E (w_0)_F x_0 \end{align} $$

(8.26) $$ \begin{align} & = u_F (w_0)_F u_E x_0 \end{align} $$

(8.27) $$ \begin{align} & = u_F (w_0)_F x_0 v_E \end{align} $$

(8.28) $$ \begin{align} & = (w_0)_F x_0 v_F v_E \end{align} $$

(8.29) $$ \begin{align} & = w_1 v \end{align} $$

because (8.25) and (8.29) hold by definition, (8.26) is a consequence of $\sigma (u_E) =0$ , which implies that $u_E$ and $(w_0)_F$ commute, (8.27) is by (8.23), and (8.28) is by (8.24).

By definition, $(w_1)_F = (w_0)_F$ , $(w_1)_E = x_0$ , and $(w_0)_F = w_0 (w_0)^{-1}_E$ . So $(w_1)_F = w_0 (w_0)^{-1}_E$ and by the triangle inequality, $|(w_0)_F|_G \leq |w_0|_G + |(w_0)_E|_G$ , which is at most $2|w_0|_G$ . So

(8.30) $$ \begin{align} |w_1|_G \leq |(w_0)_F|_G + |x_0| \leq 2|w_0|_G + |x_0| \leq (2C_6+1)n, \end{align} $$

where the last inequality is by (8.22) and (8.23).

Because $Z_G(u) = \langle u^{\prime }_F \rangle \times \langle u_E' \rangle $ , the words w such that $uw = wv$ in G are those expressible as $w =(u^{\prime }_F)^p \, (u^{\prime }_E)^q w_1$ for some $p,q \in \mathbb {Z}$ . Now,

(8.31) $$ \begin{align} u_E u^{\prime}_F = u^{\prime}_F u_E \ \text{ and } \ u_F u^{\prime}_E = u^{\prime}_E u_F \text{ in } G \end{align} $$

because $\sigma (u_E) = \sigma (u^{\prime }_E)=0$ . So $ u_E u^{\prime }_F = u^{\prime }_F u_E \lambda ^{P}$ and $u_F u^{\prime }_E = u^{\prime }_E u_F \lambda ^{Q}$ for some integers P and Q, which we use in (8.33) and (8.36) of the following calculation. In $\Lambda $ , for such w,

(8.32) $$ \begin{align} u w & = u_F u_E \left(u^{\prime}_F\right)^p \left(u^{\prime}_E\right)^q w_1 \lambda^{L^{\prime}_u} \end{align} $$

(8.33) $$ \begin{align} & = u_F \left(u^{\prime}_F\right)^p u_E \left(u^{\prime}_E\right)^q w_1 \lambda^{L^{\prime}_u + pP} \end{align} $$

(8.34) $$ \begin{align} & = \left(u^{\prime}_F\right)^p u_F u_E \left(u^{\prime}_E\right)^q w_1 \lambda^{L^{\prime}_u+ pP} \end{align} $$

(8.35) $$ \begin{align} & = \left(u^{\prime}_F\right)^p u_F \left(u^{\prime}_E\right)^q u_E w_1 \lambda^{L^{\prime}_u+ pP} \end{align} $$

(8.36) $$ \begin{align} & = \left(u^{\prime}_F\right)^p \left(u^{\prime}_E\right)^q u_F u_E w_1 \lambda^{L^{\prime}_u+ pP +qQ} \end{align} $$

(8.37) $$ \begin{align} & = w v \lambda^{pP+qQ +N}, \end{align} $$

where the remaining steps are explained by (8.32) $u = u_F u_E \lambda ^{L^{\prime }_u}$ in $\Lambda $ for some integer $L^{\prime }_u$ , (8.34) $u_F \left (u^{\prime }_F\right )^p$ freely equals $\left (u^{\prime }_F\right )^{p} u_F$ , (8.35) $u_E (u^{\prime }_E)^q$ freely equals $(u^{\prime }_E)^qu_E$ , and $u = u_F u_E \lambda ^{L^{\prime }_u}$ , and (8.37) $u = u_F u_E$ and $u w_1 = w_1 v \lambda ^N$ for some integer N.

Similarly to the earlier cases, because $\overline {u} = u \lambda ^{L_u}$ and $\overline {v} = v \lambda ^{L_v}$ in $\Lambda $ , we have $\overline {u} w = w \overline {v}$ in $\Lambda $ if and only if

(8.38) $$ \begin{align} L_v - L_u + pP +qQ+N =0, \end{align} $$

and because $\overline {u} \sim \overline {v}$ in $\Lambda $ , there exist $p, q \in \mathbb {Z}$ satisfying this equation. Now, we claim that $|P|, |Q|, |N + L_v - L_u| \leq C_{13}^n$ for a suitable constant $C_{13}>1$ . Indeed, Lemma 5.2 applied to $u_E u^{\prime }_F$ , which equals $u^{\prime }_F u_E \lambda ^{P}$ in $\Lambda $ , gives that $|P| \leq |u^{\prime }_F| C^{\Sigma \left ( u_E u^{\prime }_F \right )}$ . And so $|P| \leq C_{14}^n$ for a suitable constant $C_{13}>1$ , because of Lemma 6.5 and because $\Sigma \left ( u_E u^{\prime }_F \right ) \leq |u_E|$ . Likewise, applied to $u_F u^{\prime }_E$ , which equals $u^{\prime }_E u_F \lambda ^{Q}$ in $\Lambda $ , it gives $|Q| \leq |u_F| C^{\Sigma \left ( u_F u^{\prime }_E \right )}$ . So $|Q| \leq C_{13}^n$ because of Lemma 6.5 and because $\Sigma \left ( u_F u^{\prime }_E \right ) = \Sigma \left (u^{\prime }_E \right ) \leq |u^{\prime }_E|$ . And Proposition 5.1 applied to $v^{-1} w_1^{-1} u w_1 = \lambda ^N$ gives that $|N| \leq C_{13}^n$ because of $|u| + |v| \leq n$ and (8.30). But then by adjusting the constant suitably, we can get $|N + L_v - L_u| \leq C_{13}^n$ because $|L_u| + |L_v| \leq n$ .

So by the quantification of Bézout in Corollary 3.3, there exist p and q satisfying (8.38) such that $|p|, |q| \leq C_{13}^n$ . And then $\overline {u} w =w \overline {v}$ in $\Lambda $ and the length of $w =(u^{\prime }_F)^p \, (u^{\prime }_E)^q w_1$ is $|p| |u^{\prime }_F| + |q| |u^{\prime }_E| + | w_1|$ is at most $C_{14}^n$ for a suitable constant $C_{14}>1$ , calling on Lemma 6.5 for bounds on the remaining terms.

Case (e). $\sigma (u) \neq 0$ , $u_E \neq 1$ , and $u_H \neq 1$ .

Let p and q be the integers such that $p \sigma (u^{\prime }_H) = q \sigma (u^{\prime }_E) = \mathrm {lcm}\left ( \sigma (u^{\prime }_H), \sigma (u^{\prime }_E) \, \right )$ . Lemma 7.1 tells us that $z = f (u^{\prime }_E)^q$ generates $Z_G(u)$ , where f is the element of F such that $(u^{\prime }_H)^p = f s^{p\sigma (u^{\prime }_H)}$ in H. In particular, $|p|$ and $|q|$ are both at most n because $|\sigma (u^{\prime }_H)|$ and $|\sigma (u^{\prime }_E)|$ both divide n.

Applying the triangle inequality to $(u^{\prime }_H)^p = f s^{p\sigma (u^{\prime }_H)}$ and $z = f (u^{\prime }_E)^q$ gives that for a suitable constant $C_{15}>0$ ,

(8.39) $$ \begin{align} |f|_G & \leq 2 |p| |u^{\prime}_H|_G \leq C_{15} n^2, \ \text{ and} \end{align} $$

(8.40) $$ \begin{align} |z|_G & \leq |f|_G + |q| |u^{\prime}_E|_G \leq C_{15} n^2. \end{align} $$

By Lemma 7.3, there exists a word w such that $uw =wv$ in G and $|w|_G \leq C_0 n^2$ and $\Sigma (w) \leq C_0 n$ . Then $uw =wv \lambda ^N$ in $\Lambda $ for some $N \in \mathbb {Z}$ and, in similar situations, in previous cases, we have called on Proposition 5.1, which would give that $|N| \leq C_{16}^{n^2}$ for some constant $C_{16}>1$ . However, we need a tighter bound and for that we look to Lemma 5.2. Let $W = v^{-1} w^{-1} u w$ . Observe that for any words $\tau $ and $\pi $ , we have $\Sigma (\tau \pi ) \leq \Sigma (\tau ) + \Sigma (\pi )$ and $\Sigma (\tau ) = \Sigma (\tau ^{-1})$ . So $\Sigma (W) \leq 2\Sigma (w) + |u| + |v| \leq (2C_0 +1) n$ and with Lemma 5.2, we get

(8.41) $$ \begin{align} |N| \leq |W| C^{\Sigma\left(\widehat{W}\right)} \leq C_{17}^{n} \end{align} $$

for a suitable constant $C_{17}>1$ .

The set of all W such that $u W = W v$ in G is $\left \{ z^r w \mid r \in \mathbb {Z}\right \}$ .

Now, u commutes with z in G, so $u z = z u \lambda ^M$ in $\Lambda $ for some $M \in \mathbb {Z}$ .

By hypothesis, $\overline {u} \overline {W} = \overline {W} \overline {v}$ in $\Lambda $ for some word $ \overline {W} \in \Lambda $ . Let W be this $\overline {W}$ with all letters $\lambda $ deleted. Then $\overline {u} W = W \overline {v}$ in $\Lambda $ also and $u W = W v$ in G, and so this W must equal $z^r w$ in G for some $r \in \mathbb {Z}$ . We calculate that in $\Lambda $ ,

(8.42) $$ \begin{align} \overline{u} W & = uW \lambda^{L_u} \end{align} $$

(8.43) $$ \begin{align} & = u z^rw \lambda^{L_u+K} \end{align} $$

(8.44) $$ \begin{align} & = z^r u w \lambda^{L_u+K+rM} \end{align} $$

(8.45) $$ \begin{align} & = z^r w v \lambda^{L_u+K+rM +N} \end{align} $$

(8.46) $$ \begin{align} & = W v \lambda^{L_u+rM +N} \end{align} $$

(8.47) $$ \begin{align} & = W \overline{v} \lambda^{L_u - L_v+rM +N} \end{align} $$

because (8.42) $\overline {u} = u \lambda ^{L_u}$ , (8.43) and (8.46) $W = z^rw \lambda ^K$ for some $K\in \mathbb {Z}$ , (8.44) ${uz=zu \lambda ^M}$ , (8.45) $uw=wv \lambda ^N$ , and (8.47) $\overline {v} = v \lambda ^{L_v}$ . So $L_v = L_u + rM + N$ .

If $M=0$ , then the above calculation gives that $\overline {u} W = W \overline {v}$ in $\Lambda $ for $W = z^rw$ , irrespective of the value of r. So we can take $r=0$ and we get that $\overline {u} w = w \overline {v}$ in $\Lambda $ .

If $M \neq 0$ , then $r = (L_v - L_u -N)/M$ and because of $|L_u| + |L_v| \leq n$ and (8.41), we get that $|r| \leq C_{18}^n$ for a suitable constant $C_{18}>0$ .

In either case, $|W|_G \leq |r| \cdot |z|_G + |w|_G$ and because of $|w|_G \leq C_0 n^2$ and (8.40), $|W|_G \leq C_{19}^n$ for a suitable constant $C_{19}>0$ .

This completes our proof that $\mathrm {CL}_{\Lambda }(n) \preceq 2^n$ .

9 Why $\mathrm {CL}_{\Lambda }(n) \succeq 2^n$

As we saw in Section 5, if we define $f(n)$ to be the exponent sum of the letters in $\phi ^n\left (a_i\right )$ , for a suitable choice of i, then $f(n) \simeq 2^n$ and $[t, s^{-n} a_i s^n]$ is a word of length $4n+4$ that equals $\lambda ^{f(n)}$ in $\Lambda $ . Without loss of generality, we may assume $i=1$ . So, if for $n \geq 1$ , we define $\overline {u_n} =a_1 t \lambda ^{f(n)}$ and $\overline {v_n} = a_1 t $ , then $|\overline {u_n}|_{\Lambda } + |\overline {v_n}|_{\Lambda } \leq 4n + 8$ and $\overline {u_n} \sim \overline {v_n}$ in $\Lambda $ because

$$ \begin{align*}\overline{u_n} t^{f(n)} = a_1 t^{f(n)+1} \lambda^{f(n)} = t^{f(n)} a_1 t = t^{f(n)} \overline{v_n}.\end{align*} $$

The images $u_n$ and $v_n$ in G of $\overline {u_n}$ and $\overline {v_n}$ , respectively, are $u_n = v_n = a_1 t$ . A shortest word w such that $\overline {u_n} w = w \overline {v_n}$ in $\Lambda $ will contain no letters $\lambda $ , because $\lambda $ is central and will satisfy $u_n w = w v_n$ in G.

Case (d) of Lemma 7.1 tells us that $Z_G \left ( a_1 t \right ) = \langle a_1 \rangle \times \langle t \rangle $ . So, if $u_n w = w v_n$ in G, then $w = a_1^p t^q$ for some $p, q \in \mathbb {Z}$ .

However, not all such w will satisfy $\overline {u_n} w = w \overline {v_n}$ in $\Lambda $ . Indeed, $\overline {u_n} w = a_1 t \lambda ^{f(n)} a_1^p t^q = a_1^{p+1} t^{q+1} \lambda ^{f(n)+p}$ and $w \overline {v_n} = a_1^p t^q a_1 t = a_1^{p+1} t^{q+1} \lambda ^{q}$ . So the $w= a_1^{p} t^{q}$ such that $\overline {u_n} w = w \overline {v_n}$ in $\Lambda $ and those of the form $w = a_1^{p} t^{p + f(n)}$ for some $p \in \mathbb {Z}$ .

For such w,

(9.1) $$ \begin{align} |w|_{\Lambda} \geq |p + f(n)| \end{align} $$

because killing all generators other than t maps $\Lambda {\kern 3pt\to \kern -8pt\to \kern 3pt} \langle t \rangle \cong \mathbb {Z}$ and $w \mapsto t^{p + f(n)}$ . Now, $\langle a_1 \rangle $ is an infinite cyclic subgroup of a hyperbolic group H and as such is an undistorted subgroup of H. On account of this and that killing t and $\lambda $ maps $\Lambda {\kern 3pt\to \kern -8pt\to \kern 3pt} H$ , there exists a constant $C>0$ such that

(9.2) $$ \begin{align} |w|_{\Lambda} \geq | a_1^p |_H \geq C|p|. \end{align} $$

So, if $|p| < f(n)/2$ , then $|w|_{\Lambda } \geq f(n)/2$ by virtue of (9.1), and otherwise $|w|_{\Lambda } \geq C f(n)/2$ by virtue of (9.2). That $\mathrm {CL}_{\Lambda }\left (n\right ) \succeq 2^n$ follows.

This completes our proof of Theorem 1^′ .

10 Fiber products: Examples further up the Grzegorczyk hierarchy

We now turn our attention to a fiber product construction that yields finitely presented groups displaying a wide range of conjugator length functions. Our purpose here is two-fold: first, we want to construct specific finitely presented groups with large but computable conjugator length functions including representatives comparable to every level of the Grzegorczyk hierarchy of primitive recursive functions (Theorem 1.2); secondly, we want to describe a framework (Remark 10.5) that holds the potential to provide calculations of $\mathrm {CL}\left (n\right )$ for finitely presented groups in great generality.

The groups that we shall construct to prove Theorem 1.2 are obtained by following the general template for constructing “designer groups” described in [Reference BridsonBri06], which is based on refinements of the Rips Construction [Reference RipsRip82] and the 1-2-3 Theorem of Baumslag et al. [Reference Baumslag, Bridson, Miller and ShortBBMS00]. As is usual with this template, we will have to craft input groups carefully to achieve the desired output group.

We remind the reader that a group G is said to be of type $\mathrm {{F}}_3$ if it has a classifying space $K(G,1)$ whose 3-skeleton is finite.

The Rips Construction [Reference RipsRip82] associates to any finite group-presentation $\mathcal {Q}$ , a short exact sequence

$$ \begin{align*}1\to N\to \Gamma \overset{p}\to Q\to 1, \end{align*} $$

where Q is the group presented by $\mathcal {Q}$ , while N is a 2-generator group and G is a torsion-free hyperbolic group that satisfies a prescribed small-cancellation condition. The 1-2-3 Theorem [Reference Baumslag, Bridson, Miller and ShortBBMS00] implies that if Q is of type $\mathrm {{F}}_3$ , then the fiber product

$$ \begin{align*}P:= \left\{(x,y)\in \Gamma \times \Gamma \mid p(x)=p(y) \right\} \end{align*} $$

is finitely presented. Moreover, it was proved in [Reference Bridson, Howie, Miller and ShortBHMS13] that there is an algorithm that, given the presentation $\mathcal {Q}$ and a set of $\mathbb {Z} Q$ -module generators for the second homotopy module $\pi _2\mathcal {Q}$ (or, equivalently, a combinatorial model for the 3-skeleton of $K(Q,1)$ ), will output a finite presentation for P; if the presentation is aspherical, then the algorithm simplifies considerably.

A primary goal of [Reference Baumslag, Bridson, Miller and ShortBBMS00] was to construct a finitely presented subgroup of a product of hyperbolic groups such that the membership and conjugacy problems for the subgroup were unsolvable. This was done by combining the Rips Construction and the 1-2-3 Theorem as described above: if Q has an unsolvable word problem, then the fiber product $P<\Gamma \times \Gamma $ has the desired properties. This construction builds on an idea that originates in the work of Mihailova [Reference MihailovaMih58], who considered the case where $\Gamma $ is a free group. The following basic lemma from her work contains the key facts and the reader who is new to these ideas will find the exercise of proving it to be instructive.

Lemma 10.1 (Mihailova)

Let $Q = \langle a_1, \ldots , a_n \mid r_1, \ldots , r_m \rangle $ , let F be the free group $F(a_1,\dots ,a_n)$ , and let

$$ \begin{align*}P = \{ (u,v) \mid u=v \text{ in } Q\} < F\times F. \end{align*} $$

Then, P is generated by $ \{(a_1, a_1), \ldots , (a_n,a_n), (r_1,1), \ldots , (r_m,1)\}$ . And for all $w\in F$ ,

1. (1) $w = 1$ in Q if and only if $(w,1) \in P$ , and

2. (2) provided $r \in F$ is not a proper power, $(wrw^{-1},r) \sim (r,r)$ in P if and only if $w=1$ in Q.

By refining the proofs of such basic results, one can establish quantified relationships between membership and conjugacy problems, on the one hand, and word problems, on the other hand, loosely speaking, the Dehn function for Q is reflected in the distortion function of $P<\Gamma \times \Gamma $ , and these functions together with the geometry of cyclic subgroups in Q account for the difficulty of the conjugacy problem in P. These relationships are explored in detail in [Reference BridsonBri25, Reference BridsonBri26]. In particular, the following close relationship between the Dehn function of Q and the conjugator length function of P is established in [Reference BridsonBri25], under the hypothesis that Q has uniformly quasigeodesic cyclics (UQC), meaning that there is a constant $\lambda>0$ such that $|q^n|_Q\ge \lambda |n|$ for all $n\in \mathbb {Z}$ and $q\in Q\setminus \{1\}$ .

Theorem 10.2 [Reference BridsonBri25, Corollary C]

Let $P<\Gamma \times \Gamma $ be the fiber product associated with an epimorphism $\Gamma \to Q$ , where $\Gamma $ is a torsion-free hyperbolic group and Q is a finitely presented group that has UQC. Then

$$ \begin{align*}\mathrm{Dehn}_Q\left(n\right)\preceq \mathrm{CL}_P\left(n\right)\preceq \mathrm{Dehn}_Q\left(n^2\right).\end{align*} $$

To identify groups Q meeting the hypothesis of this theorem, we look to the following lemma.

(Here, $Q\dot \ast _M$ denotes the trivial HNN-extension $\langle Q, t \mid [t,m] =1 \ \forall m \in M \rangle $ of Q along a subgroup $M \leq Q$ .)

Our main interest here lies with large Dehn functions associated with groups that have useful additional properties. We would like to have concise presentations for them, as well as geometry to aid our understanding.

We first consider the function $\Delta \left (n\right )$ defined recursively by $\Delta (1)=2$ and ${\Delta (k+1)=2^{\Delta (k)}}$ . This function arises in several settings: $\Delta (\lfloor \log n\rfloor )$ is the Dehn function of Higman’s group with no finite quotients [Reference HigmanHig51]

$$ \begin{align*}\langle a,b,c,d \mid a^{-1}ba=b^2,\, b^{-1}cb=b^2,\, c^{-1}dc=d^2,\, d^{-1}ad=a^2 \rangle \end{align*} $$

and of the Baumslag–Gersten one-relator group [Reference BaumslagBau69]

(10.1) $$ \begin{align} \langle x, t \mid (t^{-1}x^{-1}t)x(t^{-1}xt)=x^2 \rangle \end{align} $$

(see [Reference BridsonBri15, Reference PlatonovPla04]). Further, $\Delta \left (n\right ) = A_3\left (n\right )$ the third Ackermann function – see Section 1. In fact, all of the Ackermann functions $n \mapsto A_k\left (n\right )$ arise as Dehn functions of groups with small aspherical presentations. These Ackermann functions play a central role in the work of Dison and Riley on hydra groups [Reference Dison and RileyDR13]. They prove that $A_k$ is the Dehn function of the HNN extension $Q_k = H_k\dot \ast _{L_k}$ , where $H_k$ is the free-by-cyclic group $\langle a_1,\dots ,a_k,t \mid t^{-1} a_1 t =a_1, \, t^{-1}a_i t = a_i a_{i-1} \ (i>1) \rangle $ and $L_k$ is the free subgroup generated $\{a_1t,\dots ,a_kt\}$ :

(10.2) $$ \begin{align} Q_k = \langle a_1,\dots,a_k,t, s \mid t^{-1} a_1 t =a_1, \, t^{-1}a_i t = a_i a_{i-1} \ (i>1); [s,a_it]=1 \ (i>0) \rangle. \end{align} $$

Remark 10.5 Theorem 10.2 has an antecedent in [Reference BridsonBri25] which says that for Q a finitely presented group, and $\Gamma {\kern 3pt\to \kern -8pt\to \kern 3pt} Q$ an epimorphism from a torsion-free hyperbolic group, and $P < \Gamma \times \Gamma $ the associated fiber product,

$$ \begin{align*}\mathrm{Dehn}_Q\left(n\right) \preceq \mathrm{CL}_P \left(n\right) \preceq \mathrm{CL}_P^{\Gamma\times \Gamma}\left(n\right) \preceq \mathrm{Dehn}^c_Q\left(n\right),\end{align*} $$

where $\mathrm {CL}^{G\times G}_P \left (n\right )$ is quantified over $u,v$ with $|u|_{G\times G}+|v|_{G\times G}\le n$ rather than $|u|_P+|v|_P\le n$ and $\mathrm {Dehn}_Q^c\left (n\right ):\mathbb {N}\to \mathbb {N}$ is the rel-cyclics Dehn function,

(10.3) $$ \begin{align} \mathrm{Dehn}^c\left(n\right) : = \max_{w,u} \left\{ \mathrm{{Area}}(w\,u^p) \, \colon \, |w|+|u|\le n,\ w=_Qu^{-p},\ |p|< o(u)/2\right\}. \end{align} $$

This relationship motivates us to consider which functions arise as rel-cyclic Dehn functions $\mathrm {Dehn}^c\left (n\right )$ of groups of type $\mathrm {{F}}_3$ . This question seems amenable to attack using the many techniques developed to study Dehn functions and subgroup distortion, and this expectation lends weight to the conviction that the set of $\simeq $ classes of conjugator length functions of finitely presented groups is likely to be as diverse as the set of Dehn functions.Footnote ³