Distortion of finitely presented subgroups of non-positively curved groups II — hydra groups

This post is written by Tim Riley. (Given that I’m writing about my own work here, it would seem awkward to blog this under the partial anonymity of the collective name “Berstein.”) The main sources for this post are my papers Hydra groups with Will Dison and Hyperbolic Hydra with Noel Brady and Will Dison. The latter is currently in preparation here. I am also using some of my talk slides on hydra groups.

Hercules versus the hydra and Ackermann’s function

For Dison and me, a hydra is a finite–length positive word on the alphabet ${a_1}$, ${a_2}$,…. Hercules fights a hydra by striking off its first letter. The hydra then regenerates as follows: each remaining letter ${a_i}$, where ${i > 1}$, becomes ${a_i a_{i-1}}$ and the ${a_1}$ are unchanged. This process — removal of the first letter and then regeneration — repeats, with Hercules victorious when (not if!) the hydra is reduced to the empty word ${\epsilon}$.

Example. Hercules defeats ${a_2 a_3 a_1}$ in five strikes:

$\displaystyle a_2 a_3 a_1 \ \rightarrow \ a_3 a_2 a_1 \ \rightarrow \ a_2 a_1 a_1 \ \rightarrow \ a_1 a_1 \ \rightarrow \ a_1 \ \rightarrow \ \varepsilon.$

(Each arrow represents the removal of the first letter and then regeneration.)

Proving that Hercules always wins is a fun exercise.

Perhaps surprisingly, the battles tend to be of enormous duration. Define ${\mathcal{H}(w)}$ to be the number of strikes it takes Hercules to vanquish the hydra ${w}$, and for integers ${k \geq 1}$, ${n \geq 0}$, define ${\mathcal{H}_k(n) := \mathcal{H}({a_k}^n)}$. For example, ${\mathcal{H}_1(n) = n}$ and ${\mathcal{H}_2(n) = 2^n-1}$ (another fun exercise).

What we have is a variation on Ackermann’s famous fast–growing functions ${A_k : {\mathbb N} \rightarrow {\mathbb N}}$, defined for integers ${k,n \geq 0}$ by: ${A_1(n) = 2n}$ and ${A_{k+1}(n) = A_k^{(n)}(1)}$. So, in particular, ${A_1(n)=2n}$, ${A_2(n)=2^n}$ and ${A_3(n) = \exp_2^{(n)}(1)}$, the ${n}$–fold iterated power of ${2}$.

It turns out that ${\mathcal{H}_k(n)}$ is essentially a version of Ackermann’s function:

Proposition. For all ${k \geq 1}$, ${\mathcal{H}_k \simeq A_k}$.

Recursion is apparent in the battle. Suppose ${ua_k}$ is a hydra (${u}$ denotes some word on ${a_1, \ldots, a_k}$). Then in the time ${\mathcal{H}(u)}$ it takes to kill ${u}$, there appear ${\mathcal{H}(u)}$ letters ${a_{k-1}}$ (and many other letters besides) after the final ${a_k}$. Disposing of those letters then represents an additional challenge for Hercules. So the time it takes to complete that initial task of killing ${u}$ determines the magnitude of the remaining challenge (the hydra that has grown up beyond the ${a_k}$ in that time).

Hydra groups

The reason for our interest in this Hercules–versus–the–hydra battle is that it is suited to group theoretic manifestations, even in settings of non–positive curvature. It leads to the result that even for apparently benign ${G}$ and ${H}$, distortion can be wild.

Define

$\displaystyle G_k \ := \ \langle \ a_1, \ldots, a_k, t \ \mid \ t^{-1} {a_1} t=a_1, \ t^{-1}{a_i} t=a_i a_{i-1} \ (\forall i>1) \ \rangle$

and

$\displaystyle H_k := \langle a_1t, \ldots, a_kt \rangle.$

Theorem (Dison and Riley). Each ${G_k}$

• is free–by–cyclic,
• can be presented with only one defining relator,
• is ${\textup{CAT}(0)}$,
• and is biautomatic,

and yet ${H_k}$ is a rank–${k}$ free subgroup that is distorted ${\simeq A_k}$.

Some parts of this theorem are easy to explain. That the ${G_k}$ are free–by–cyclic is evident from their presentations. As for being one–relator groups, by re–expressing the original relations as ${[a_1,t]=1}$ and ${a_{i-1} = [a_i,t]}$ for ${i>1}$ (convention: ${[a,b]= a^{-1}b^{-1}ab}$) and then eliminating ${a_1, \ldots, a_{k-1}}$ and defining ${a:= a_k}$, one can present ${G_k}$ with one relation, a nested commutator:

$\displaystyle G_k \ \cong \ \langle \ a, t \ \mid \ [a, \underbrace{t, \ldots, t}_k ] =1 \ \rangle.$

That is, the relation is ${v_k=1}$ where ${v_k}$ is the “Engel” word defined recursively by ${v_0 = a}$ and ${v_{i+1} = [v_i,t]}$ for ${i \geq 0}$.

Samuelson was the first (we think) to prove ${G_k}$ is ${\textup{CAT}(0)}$. Our approach is to recursively define a family of words by ${u_0= a}$ and ${u_{i+1} = {u_i}^{-1}s{u_i}}$ for ${i \geq 0}$. By inducting on ${i}$, one can verify that after substituting ${t^{\pm 1}}$ for every ${s^{\mp 1}}$ in ${u_i}$, the words ${t^{-(i-1)} u_i t^i}$ and ${v_i}$ become freely equal for all ${i \geq 1}$. So the relation ${v_k=1}$ can be replaced by ${u_k =s}$ to give an alternative one–relator presentation for ${G_k}$:

Re–expressing this presentation via ${\alpha_i := u_{k-i}}$ for ${1 \leq i \leq k}$ as

$\displaystyle G_k \ \cong \ \left\langle \ \alpha_1, \ldots, \alpha_k, s \ \left| \ {\alpha_1}^{-1}s{\alpha_1} =s, \ {\alpha_i}^{-1} s {\alpha_i} =\alpha_{i-1} \ ( i >1) \ \right. \right\rangle.$

and then checking the link condition, one finds that the presentation 2-complex, metrized so that each 2-cell is a Euclidean square, is locally ${\textup{CAT}(0)}$. All such groups are automatic (Gersten and Short) and, indeed, are biautomatic (Niblo and Reeves).

Open question. Is there a one–relator group with a finite–rank free subgroup (or even a finitely presented subgroup) of distortion greater than these examples?

That ${H_k}$ is free of rank ${k}$ is harder to prove. Our method is somewhat brutal in that we analyse combinatorial manipulations of words head-on. However, it may be of interest as a new way to recognise subgroups as being free. (I think ping–pong could not be used here as that produces non-distorted free subgroups.) We suppose we have a freely reduced word ${w}$ on ${a_1 t, \ldots, a_kt}$ that represents the identity. So when the ${t}$‘s are carried through the word and collected at the end (using the defining relations of ${G_k}$ to change the ${a_i}$ they pass), the result is a word on the ${a_i}$‘s times a power of ${t}$. But as ${w}$ represents ${1}$, this word on the ${a_i}$‘s must freely reduce to the empty word and the power of ${t}$ must be zero. We show that the free reduction that occurs amongst the ${a_i}$‘s, must be echoed in free–reduction amongst some of the ${a_1 t, \ldots, a_kt}$ in ${w}$ — this is awkward; we use a somewhat messy induction on ${k}$. So, in fact, ${w}$ must be the empty word. It follows that there are no non-trivial relations between the ${a_1 t, \ldots, a_kt}$ and so they generate a rank–${k}$ free group. The most fun part of the theorem (I think) is that the distortion of ${H_k}$ in ${G_k}$ is so large. This is where the battle between Hercules and the hydra comes in. Consider —

Question. For what ${r}$ is ${{a_k}^n t^r \in H_k}$?

Let’s look at the instance where ${k=2}$ and ${n=4}$. One can try to convert ${{a_2}^4}$ to a word on ${a_1t}$ and ${a_2t}$ times a power of ${t}$ by introducing a ${tt^{-1}}$ to pair the first letter with ${t}$, and then carry the accompanying ${t^{-1}}$ to the end of the word by conjugating through the intervening letters; then pair off the next ${a_i}$ likewise, and repeat:

$\displaystyle \begin{array}{rl} {a_2}^4 & = \ {a_2}t \ t^{-1} {a_2}^3 t \ t^{-1} \\ & = \ {a_2}t \ {a_2}{a_1}{a_2}{a_1}{a_2}{a_1} \ t^{-1} \\ & = \ {a_2}t \, {a_2}t \ t^{-1}a_1 {a_2}a_1 {a_2}a_1 t \ t^{-2} \\ & = \ {a_2}t \, {a_2}t \ a_1 {a_2}a_1a_1 {a_2}a_1 a_1 \ t^{-2} \\ & \vdots \end{array}$

Notice that the hydra battle

$\displaystyle \begin{array}{l} {a_2}^4 \\ {a_2}{a_1}{a_2}{a_1}{a_2}{a_1} \\ a_1 {a_2}a_1a_1 {a_2}a_1 a_1 \\ \vdots \end{array}$

is playing out within this calculation. Pairing off the first letter with a ${t}$ corresponds to the removal of the first letter of a hydra and conjugating a ${t^{-1}}$ through to the right–hand end corresponds to a regeneration. There is nothing special about ${k=2}$ and ${n=4}$ here. So, as Hercules triumphs, we have:

Answer: ${r = \mathcal{H}_k(n)}$.

This calculation, run to its conclusion, is displayed in this van Kampen diagram:

Let ${u_{k,n}}$ denote the reduced word on ${a_1t, \ldots, a_kt}$ which represents ${{a_k}^n t^{\mathcal{H}_k(n)}}$. The diagram pictured above can be paired with its mirror image, separated by three corridors of 2–cells as shown below, to give a diagram that demonstrates the equality in ${G_k}$ of a reduced word on ${a_1t, \ldots, a_kt}$ of length ${\simeq \mathcal{H}_k(n)}$ (the word along the bottom of the diagram) to a word of length ${\simeq n}$. Thus the distortion is at least ${ \mathcal{H}_k(n)}$.

Establishing the upper bound on the distortion of ${H_k}$ in ${G_k}$ is a technical slog (it takes about half the paper!) and I won’t give any details here… anyway, the lower bound is what’s most interesting.

Incidentally, the ${G_k}$ lead to easy examples of groups with extravagantly large Dehn functions:

${\langle G_k, p \mid [p, a_it]=1 \ (\forall i) \rangle}$

has Dehn function ${\simeq A_k}$ when ${k >1}$.

Hyperbolic hydra

The more recent development is:

Theorem (N. Brady, Dison and Riley). For all ${k \geq 1}$, there is a hyperbolic group ${\Gamma_k}$ with a free rank–${(k+18)}$ subgroup ${\Lambda_k}$ whose distortion is ${\succeq A_k}$.

The ${\Gamma_k}$ are obtained by embellishing the ${G_k}$. I’ll present them in two ways. The first is as a free–by–cyclic group and it’s in this guise that we will show that there is a hugely distorted subgroup. The second is via “Labelled Oriented Trees” (LOTs) and is suited for establishing hyperbolicity.

As a free–by–cyclic group, ${\Gamma_k}$ is

$\displaystyle F(a_0, a_1, \ldots, a_k, b_1, \ldots, b_{17}) \rtimes {\mathbb Z}$

where ${t}$ acts via an automorphism

$\displaystyle t^{-1} {a_0} t=u a_1 v, \ t^{-1} {a_1} t=a_0, \ t^{-1}{a_i} t=a_i a_{i-1} \ (\forall i>1), \ t^{-1}{b_j} t=w_j \ (\forall j),$

where ${u}$, ${v}$, and the ${w_j}$ are some words on the ${b_l}$ which we won’t specify explicitly here. So comparing with ${G_k}$, we’ve added ${a_0}$ and the seventeen ${b_l}$, and ${t}$ now acts to interchange ${a_0}$ and ${a_1}$, except it introduces some words on the ${b_l}$ whilst doing so. The basic point of this is to avoid the ${\langle a_0, t \rangle \cong {\mathbb Z}^2}$ that is present in ${G_k}$ whilst maintaining the pattern of interaction between the ${a_i}$ and ${t}$. The action of ${t}$ restricted to ${F(b_1, \ldots, b_{17})}$ is an automorphism.

The subgroup ${\Lambda_k}$ which we claim is free of rank–${(k+18)}$ and distorted ${\succeq A_k}$ is

$\displaystyle \langle a_0t, a_1t, \ldots, a_kt, b_1, \ldots, b_{17} \rangle.$

Our proof of its freeness is similar to that of the corresponding result for ${H_k}$. We obtain the distortion result by mimicking the calculations for ${H_k}$ in ${G_k}$ — the words involved become interspersed with the ${b_j}$ but the ${b_j}$ do not obstruct the calculations. An alternative (and entirely explicit) presentation for ${\Gamma_k}$ is encoded in the picture below, which displays the case ${k=6}$. [The number of ${\alpha_i}$ is ${k}$. The numbers of ${\beta_i}$ and ${\gamma_i}$ do not depend on ${k}$.]

The letters shown on the diagram are the generators. Two defining relations are given by 2–cells: ${\gamma_3 \beta_5 = \beta_3 \gamma_5}$ and ${\alpha_1 \gamma_1 \tau = \tau \gamma_7 \alpha_1}$. All the other defining relations are encoded in the graphs: an edge labelled ${y}$ from a vertex labelled ${x}$ to a vertex labelled ${z}$ corresponds to a relation ${y^{-1}xy=z}$. I won’t explain here why these presentations both give ${\Gamma_k}$, except to say that the result in the background is that if a 2–complex admits an ${S^1}$–valued Morse function all of whose ascending and descending links are trees, then its fundamental group is free–by–cyclic. (See, for example, here.) You can check this holds for the link, shown below, of presentation 2–complex of the LOT presentation if we metrize the cells corresponding to commutator relations as Euclidean squares and the remaining relations as shown in the picture above. [The two grey edges in the link have length ${\pi/3}$, the four green edges have length ${5\pi/6}$, and all other edges have length ${\pi/2}$.]

The way we prove that ${\Gamma_k}$ is hyperbolic is first to check that the link is large, and so the presentation 2–complex is locally CAT(0), and then invoke the The Flat Plane Theorem to conclude that the universal cover is hyperbolic. The Flat Plane Theorem requires that there be no isometrically embedded copy of the Euclidean plane. This can be checked by first identifying which edges in the link occur in simple loops of length ${2\pi}$, and then checking that no cells have all their corners giving rise to edges in the list.

Distortion of finitely presented subgroups of non-positively curved groups I

We have seen that the Rips construction can be used to construct hyperbolic groups with finitely generated subgroups of enormous distortion — that is, not bounded above by any recursive function. However, those examples were not finitely presentable. This post and the next two will look at distortion of subgroups in non–positively curved groups when the subgroup can be finitely presented. [In fact, in almost all the examples we will examine, the heavily distorted subgroup will be a finite-rank free group.]

First a reminder —

What is distortion?

Definition. The distortion ${\textup{Dist}^{\Gamma}_H : {\mathbb N} \rightarrow {\mathbb N}}$ of a finitely generated subgroup ${H}$ in a finitely generated group ${\Gamma}$, is defined by

$\displaystyle \textup{Dist}^{\Gamma}_H(n) \ = \ \max \{ \, d_H(1,h) \, \mid \, h \in H, \ d_{\Gamma}(1,h) \leq n \, \}.$

Here ${d_{\Gamma}}$ and ${d_H}$ denote word metrics associated to some choices of finite generating sets. Those choices are not important: different choices lead to ${\simeq}$–equivalent distortion functions.

In this post we will give a number of examples culminating in some examples of Barnard, N. Brady, and P. Dani of CAT(-1) groups with free subgroups whose distortion outgrows any finite tower of exponentials.

Abelian subgroups of semi–hyperbolic groups

As we have seen, finitely generated abelian subgroups of semi–hyperbolic (for example, hyperbolic or CAT(0)) groups are quasi–isometrically embedded and so are undistorted — that is, their distortion functions grow like ${n \mapsto n}$ (in the sense of ${\simeq}$). This is the Algebraic Flat Torus Theorem.

Iterated Baumslag–Solitar groups

These examples are not non–positively curved, but they pave the way for non–positively curved examples to come. In each case, the subgroup we identify as having large distortion is ${{\mathbb Z}}$ and this leads to the Dehn functions being at least as fast growing as the distortion functions: if a short word ${w}$ represents a large power ${a^k}$ in this ${{\mathbb Z} = \langle a \rangle}$, then ${[a,w]}$ represents the identity and has area at least ${k}$. [It is not always the case that heavily distorted ${{\mathbb Z}}$ subgroups lead to large Dehn functions, but it is so for the examples that follow.] And, as we’ve previously discussed, in a group that has any right to be called non–positively curved, the Dehn function can grow no faster than quadratically.

The starting point for this family of examples is often referred to (inappropriately, as Gilbert Baumslag is known to point out!) as the Baumslag–Solitar group:

$\displaystyle \langle a, s \mid s^{-1} a s \ = \ a^2 \rangle.$

The subgroup ${{\mathbb Z} = \langle a \rangle}$ is exponentially distorted: the lower bound is apparent from the relation

$\displaystyle s^{-n} a s^n = a^{2^n}$

that stems from the doubling effect of ${s}$ when it conjugates ${a}$.
The figure below, which is a Van Kampan diagram for ${a^{2^n}s^{-n}a^{-1}s^n}$, graphically displays this calculation.

Suppose we now distort ${s}$ by introducing a new letter ${u}$ acting by ${u^{-1} s u = s^2}$. Then the distortion of ${{\mathbb Z} = \langle a \rangle}$ inside

$\displaystyle \langle a, s, u \mid s^{-1} a s =a^2, \ u^{-1} s u =s^2 \rangle$

grows like ${n \mapsto \exp^{(2)}(n)}$. [We will write ${\exp^{(l)}}$ for the ${l}$-fold iterate of the exponential function.] This time the lower bound comes from

$\displaystyle (u^{-n} s u^n)^{-1} a (u^{-n} s u^n) \ = \ s^{-2^n} a s^{2^n} \ = \ a^{2^{2^n}}.$

Iterating, we find the distortion of ${{\mathbb Z} = \langle a \rangle}$ inside

$\displaystyle \langle a, s_1, \cdots, s_l \mid {s_1}^{-1} a {s_1} =a^2, \ {s_{i+1}}^{-1} s_i s_{i+1} ={s_i}^2 \ (i >1) \rangle$

is ${\simeq \exp^{(l)}}$. [We will not go into details of the upper bounds, it suffices to say they do not harbour any great subtleties.] Here is an illustration of the calculation that leads to the 3–fold iterated exponential distortion:

This family has a limit (loosely speaking) — a one–relator group first described by Baumslag, and since analyzed by Gersten, Bernasconi (University of Utah thesis, 1994) and Platonov (Vestnik Moskov. Univ. Ser. I Mat. Mekh. 2004, , no. 3, pp. 12–17; trans. in Moscow University Mathematics Bulletin, vol. 59 (2004), no. 3, pp. 12–17 (2005)) —

$\displaystyle \langle a, t \mid (t^{-1} a t)^{-1} a (t^{-1} a t) \ = \ a^2 \rangle.$

Introducing ${s}$ as shorthand for ${t^{-1} a t}$, we can re–express this presentation as:

$\displaystyle \langle a, s, t \mid s^{-1} a s = a^2, \ s = t^{-1} a t \rangle,$

and we see that conjugation by ${s}$ again has a doubling effect on ${a}$, and that ${t}$ conjugates ${a}$ to ${s}$ leads to a feedback effect whereby we get huge distortion of ${{\mathbb Z} = \langle a \rangle}$ on account of diagrams of the form shown below. To be precise, if the portion of the perimeter of this diagram that excludes the huge power of ${a}$ is to have length ${n}$, then the tree dual to the picture must have depth ${\simeq \lfloor \log_2 n \rfloor}$ and so the distortion grows like ${n \mapsto \exp^{(\lfloor \log_2 n \rfloor)}(1)}$.

Hyperbolic free–by-cyclic and free–by–free groups

Perhaps, on account of the connection with 3–manifolds that are mapping tori of surface diffeomorphisms, the natural first examples of non–positively curved groups with heavily distorted subgroups are free–by–cyclic and free–by–free groups where, in each case, the automorphism giving the action on the fibre distorts it exponentially.

A CAT(0) example of such a free–by–cyclic group is relatively easy to come by:

$\displaystyle F(a,b) \rtimes {\mathbb Z}$

where the generator ${t}$ for the ${{\mathbb Z}}$ factor acts by ${t^{-1} a t = ab}$ and ${t^{-1} b t = a}$. This is an exponentially growing automorphism — that is, ${t^{-n} a t^n}$ has length ${\simeq \exp(n)}$ when re–expressed as a minimal length word in ${a}$ and ${b}$. (In fact, the length grows exactly like the Fibonacci numbers.) This group can be presented as

$\displaystyle \langle a, b, t \mid t^{-1} a t = ab, \ t^{-1} b t = a \rangle,$

or equivalently as

$\displaystyle \langle a, b, c, t \mid at=cb, \ c=bt, \ c=ta \rangle.$

If we metrize the presentation 2–complex so that the cell corresponding to ${at=cb}$ is a Euclidean square and those corresponding to ${c=bt}$ and ${ c=ta}$ are Euclidean equilateral triangles, all of side–length ${1}$, then the link condition can be verified: one checks that the links “are large” — that is, all simple loops in the graph shown below have length at least ${2\pi}$. So the universal cover is a CAT(0)–space and the group is CAT(0).

Hyperbolic free–by–cyclic examples are a little harder to pin down. [For one thing the free group has to have rank at least three: Nielsen showed that any automorphism ${F(a,b) \rightarrow F(a,b)}$ takes ${a^{-1}b^{-1}ab}$ to a conjugate of itself or its inverse. It follows that ${F(a,b) \rtimes_{\phi} {\mathbb Z}}$ has a ${{\mathbb Z}^2}$–subgroup and so is not hyperbolic.] The existence of hyperbolic free–by–cyclic and, more generally, free–by–free examples can be derived from Bestvina–Feighn and Bestvina–Feighn–Handel. There are explicit CAT(-1) free–by–cylic examples in McCammond–Wise and CAT(-1) free–by–free examples (where the free group acting on the free fibre can have any finite rank) in N. Brady–A. Miller. All necessarily have exponentially distorted free fibres.

We will describe groups with free subgroups that are distorted like the iterated–exponential ${n \mapsto \exp^{(l)}(n)}$ or, faster, like ${n \mapsto \exp^{(\lfloor \log_4 n \rfloor)}(1)}$. These examples combine the techniques we’ve seen above for free–by–cyclic and the iterated Baumslag–Solitar groups. The idea of uniting these ideas to give hyperbolic examples is due to Mitra. We will describe subsequent examples of Barnard, Brady and Dani that are more explicit and are also CAT(-1).

Barnard, Brady and Dani use some of the combinatorial and geometric techniques created by Wise in his work on the Rips construction. As building blocks for their groups they use

$\displaystyle G_n \ = \ \langle \, a_1, \ldots, a_m, t_1, \ldots, t_n \mid {t_i}^{-1} a_j t_i = W_{ij} \ (1 \leq i \leq n, \ 1 \leq j \leq m) \ \rangle$

where ${m =14n}$ and the ${W_{ij}}$ are positive words on ${a_1, \ldots a_m}$ of length ${14}$ with the property that each two letter–word ${a_k a_l}$ appears at most once as a subword of the ${W_{ij}}$. They get such ${W_{ij}}$ explicitly by chopping up Wise’s word

$\displaystyle (a_1 a_1a_2 a_1 a_3 \cdots a_1 a_m) (a_2 a_2a_3 a_2 a_4 \cdots a_2 a_m) \cdots (a_{m-1} a_{m-1} a_m) a_m$

which has length ${m^2}$, and in which no ${a_ka_l}$ appears twice as a subword. In the same manner as the free–by–cyclic example described earlier they get:

Lemma. The subgroup ${\langle a_1, \ldots, a_m \rangle}$ is free of rank–${m}$ and is exponentially distorted in ${G_n}$.

Consider metrizing the presentation ${2}$–complex so that each cell is built from five right–angled hyperbolic pentagons:

One can check that the large–link condition is satisfied and so the complex is locally CAT(-1). So ${G_n}$ is CAT(-1). In fact, in the link the distance between distinct ${t_i^{\pm}}$ and ${t_j^{\pm}}$ is always at least ${2 \pi}$. Accordingly, Barnard–Brady–Dani describe the free subgroup generated by the ${t_i}$ as highly convex — this will be important momentarily.

Next, pursuing an analogy with the ${l}$-fold iterated Baumslag–Solitar examples, let

$\displaystyle H_l \ := \ G_1 \ast_{F_1} G_{14} \ast_{F_2} \ast G_{14^2} \ast \cdots \ast_{F_{l-1}} G_{14^{l-1}},$

where ${F_k}$ is a free group of rank ${14^k}$ which is identified with the exponentially distorted subgroup in ${G_{14^{k-1}}}$ and the highly convex subgroup in ${G_{14^{k}}}$. So we have exponential–upon–exponential–upon–exponential… distortion leading to ${G_{14^{l-1}}}$ being distorted ${\simeq \exp^{(l)}}$ in ${H_l}$. One can build a presentation 2–complex for a presentation of ${H_l}$ by gluing together copies of the presentation ${2}$–complexes we defined above for ${G_1}$, ${G_{14}}$, …, ${G_{14^{l-1}}}$. The key point is that the ${t_i}$‘s subgroups being highly convex prevents the link condition from failing. In summary:

Theorem. ${H_l}$ is a CAT(-1) group and the free group generated by the ${a_i}$‘s in the factor ${G_{14^{l-1}}}$ is distorted ${\simeq \exp^{(l)}}$ in ${H_l}$.

And, pursing an analogy with ${\langle a, s, t \mid s^{-1} a s = a^2, \ s = t^{-1} a t \rangle}$, define

$\displaystyle G \ := \ \langle \, a_1, \ldots, a_m, t_1, \ldots, t_n, s \mid {t_i}^{-1} a_j t_i = W_{ij}, \ s^{-1} a_k s = W_k \ \rangle$

where the ${W_{ij}}$ are ${mn}$ positive words of length ${14}$, the ${W_k}$ are ${m}$ positive words of length ${1}$, and there is no ${a_pa_q}$ subword occurring twice among any of them. Again, find these ${W_{ij}}$ and ${W_k}$ by carving up Wise’s word (${n=14^2}$ and ${m=14^3}$ will work).

Similarly to before, a locally CAT(-1) presentation 2–complex can be constructed out of 2–cells each of which is built out of five hyperbolic pentagons and the result is —

Theorem. ${G}$ is a CAT(-1) group and the free subgroup generated by the ${a_i}$ is distorted at least like ${n \mapsto \exp^{( \lfloor \log_4 n \rfloor )}(1)}$.

Non–positively curved examples of yet more extreme (Ackermannian) distortion will be described in the next post.

The Tits alternative and non-positive curvature

The following is largely based on the paper The Tits Alternative for CAT(0) Cubical Complexes by Sageev and Wise.

1.1. The Tits alternative

A group ${G}$ satisfies the Tits alternative if for all subgroups ${H < G}$, either ${H}$ is virtually solvable or it contains a non-abelian free group. One way to think of this is that a group satisfying the Tits alternative has either “small” subgroups (subgroups and quotients of solvable groups are solvable), or “large” subgroups (extensions by groups containing a free group contain a free group). The term originates from the work of Jacques Tits in which he showed that finitely generated linear groups have this property (later named the Tits alternative).

1.2. Known results

The following groups are known to satisfy the Tits alternative:

1. Finitely generated linear groups (Tits)
2. hyperbolic groups (Gromov, Ghys and de la Harpe)
3. ${\mathrm{Out}(F_n)}$ (Bestvina-Feighn-Handel)
4. mapping class groups of compact surfaces (Ivanov, McCarthy)
5. some large subclasses of CAT(0) groups (Ballmann-Swiatkowski, Sageev-Wise, Xie)

Thompson’s group F is an example of a group not satisfying the Tits alternative as it contains no free subgroup of rank greater than one and isn’t virtually solvable (Bleak, for instance, constructs non-virtually solvable subgroups). Another is the Grigorchuk group. In fact any group of intermediate growth can’t satisfy the Tits alternative: it can’t have a non-abelian free subgroup (otherwise its growth would in fact be exponential), and by the MilnorWolf theorem, if it were virtually solvable, it would have to have a finite index nilpotent subgroup (implying polynomial growth by Gromov’s theorem) or an exponentially growing solvable subgroup (again contradicting intermediate growth).

It’s still an open question whether the Tits alternative holds for all ${\mathrm{CAT}(0)}$ groups, i.e. for groups which act properly and cocompactly by isometries on some ${\mathrm{CAT}(0)}$ space.

1.3. Hyperbolic groups

In case of hyperbolic groups, a stronger version of the Tits alternative holds:

Theorem 1. A subgroup of a hyperbolic group either

1. is finite,
2. is virtually infinite cyclic, or
3. contains a nonabelian free group.

An elementary proof of the above in the case where the subgroup is torsion free is presented on Henry Wilton’s geometric group theory blog (a precursor and inspiration for the blog you’re now reading). The general case requires additional results about hyperbolic elements and is presented (in French) in Sur les groupes hyperboliques d’après Mikhael Gromov (Theorem 37, page 157).

1.4. Groups acting on ${\mathrm{CAT}(0)}$ cube complexes

Theorem 2 (Sageev-Wise). Suppose ${G}$ acts properly on a finite dimensional ${\mathrm{CAT}(0)}$ cube complex ${X}$ and has a bound on the order of finite subgroups. Then any subgroup of ${G}$ either contains ${F_2}$ or is virtually abelian.

In particular, if the group acts on such an ${X}$ freely (and thus has no non-trivial finite subgroups), its subgroups contain ${F_2}$ or are virtually abelian.

I’ll sketch the proof of this theorem following the exposition in the original paper and add a few explanatory details.

We first prove the theorem assuming that ${G}$ is finitely generated.

Since ${X}$ is assumed to be finite dimensional, we proceed, as you may have already guessed, by induction on the dimension. If the dimension is 0, then the group ${G}$ must be finite (since the action is proper), so we’re done. Now we assume the theorem holds for ${G}$ acting on all such cube complexes of dimension less than ${n}$. Assume ${\mathrm{dim}(X) = n}$. To apply the induction step, we will identify a proper action of a subgroup of ${G}$ on a lower dimensional subcomplex of ${X}$. This subcomplex will be a “hyperplane” (defined next) and the subgroup acting will be its stabilizer.

A ${\mathrm{CAT}(0)}$ cube complex ${X}$ is a cubical cell complex which is simply connected and in which every link is flag. Two edges of ${X}$ are square equivalent if they are opposite edges of a square of ${X}$. Let ${\sigma}$ be an ${n}$-cube (identified with the standard unit cube in ${\mathbb{R}^n}$). A midcube of ${\sigma}$ is an intersection of ${\sigma}$ with an ${\mathbb{R}^n}$ hyperplane parallel to a face of ${\sigma}$ and containing its center. For instance, there is only one midcube in an edge, two midcubes in a square, etc.

A hyperplane in ${X}$ is the union of all midcubes meeting the equivalence class of an edge (under the equivalence relation generated by square equivalence). A few facts about hyperplanes:

1. A hyperplane meets each cube in at most one midcube.
2. A hyperplane separates ${X}$ into two components.
3. The ${\mathrm{CAT}(0)}$ cube structure on ${X}$ induces a ${\mathrm{CAT}(0)}$ cube structure on any hyperplane in ${X}$.

1.5. Tangent: ends of groups

Let ${G}$ be any finitely generated group, with ${S}$ being the set of generators. Then the number of ends of ${G}$, denoted ${e(G)}$, is the number of components of the boundary $\partial G$. It’s a classic fact that the number of ends can only equal 0 (when ${G}$ is finite), 1 (e.g. ${\mathbb{Z}^2}$), 2 (e.g. ${\mathbb{Z}}$), or infinity (e.g. ${F_2}$).

The number of ends of a finitely generated group ${G}$ relative to a subgroup ${H}$, denoted ${e(G,H)}$, is the number of ends of the graph ${\mathrm{Cay}_S(G) / H}$, i.e. the quotient of the Cayley graph of ${G}$ by the action of ${H}$. Equivalently, it is the number of ends of the graph in which vertices are cosets of ${H}$ and vertices ${Hx}$ and ${Hxg}$ are connected if and only if ${g \in S}$.

It is a famous result of Stallings that ${e(G) > 1}$ if and only if ${G}$ splits as an amalgamated product or an HNN-extension over a finite group. In the language of Bass-Serre theory, we have:

For relative ends, the picture is more complicated:

The one of the key theorems which embody the (${\Leftarrow}$) implication above is the Algebraic Torus Theorem (Dunwoody-Swenson), given below. First, however, we must establish the subgroup with respect to which ${G}$ has multiple ends.

Theorem 3 (Sageev). Suppose ${G \curvearrowright X}$, a finite dimensional ${\mathrm{CAT}(0)}$ cube complex, without a global fixed point. Then there is a hyperplane ${J \subset X}$ such that ${e(G, \mathrm{stab}(J)) > 1}$.

Theorem 4 (Algebraic Torus). Suppose ${G}$ is finitely generated, and ${H}$, a subgroup of ${G}$, is virtually polycyclic with ${e(G,H) > 1}$. Then one of the following holds.

1. ${G}$ is virtually polycyclic.
2. There exists a short exact sequence

$\displaystyle 1 \rightarrow P \rightarrow G \rightarrow G/P \rightarrow 1$

in which ${P}$ is virtually polycyclic and ${G/P}$ is non-elementary fuchsian (see below).

3. ${G}$ splits over a virtually polycyclic group.

1.6. Tangent: fuchsian groups

A fuchsian group is a subgroup of ${\mathrm{PSL}_2(\mathbb{R})}$. Thus, a fuchsian group ${G}$ acts discretely on the hyperbolic plane ${\mathbb{H}}$. Consider the set ${Gz}$, for some ${z \in \mathbb{H}}$. With respect to the hyperbolic metric on ${\mathbb{H}}$, the set ${Gz}$ has no limit points: either in ${\mathbb{H}}$, since the action is discrete, or in ${\partial\mathbb{H}}$, since every point in ${\mathbb{H}}$ is infinitely far from the boundary. However, considering the Euclidean distance ${\mathbb{H}}$ inherits by being embedded as the Poincaré disk in ${\mathbb{R}^2}$, ${Gz}$ may have limit points in ${\partial\mathbb{H}}$. Basic hyperbolic geometry implies that:

1. the limit points occur only in ${\partial\mathbb{H}}$,
2. for any other ${z' \in \mathbb{H}}$, the sets of limit points of ${Gz'}$ and ${Gz}$ are identical, and
3. the cardinality of the set of limit points is 0, 1, 2 or uncountable.

A fuchsian group is non-elementary when the set of limit points is uncountable. Such a group contains ${F_2}$.

The non-elementary fuchsian groups are really the only interesting ones: the elementary ones are either finite or virtually cyclic.

Let’s recap the proof so far. We proceed by induction, and assume the theorem true for ${\mathrm{dim}(X) = n-1}$. For ${X}$ of dimension ${n}$, since ${G}$ is infinite and acts properly on ${X}$, it has no global fixed points. Hence we apply Sageev’s theorem and conclude that there is a hyperplane ${J \subset X}$ s.t. ${e(G, \mathrm{stab}(J)) > 1}$. Let ${H = \mathrm{stab}(J)}$. Then ${H}$ acts on ${J}$ properly. By induction, either ${H}$ has an ${F_2}$ subgroup, and then so does ${G}$ so we’re done, or ${H}$ is virtually f.g. abelian. In this case, we apply the Algebraic Torus Theorem to ${G}$ and ${H}$, and conclude that (1) ${G}$ is virtually polycyclic, or (2) it has a non-elementary fuchsian quotient, or (3) it splits over a virtually polycyclic group. We deal with these possibilities one by one.

If ${G}$ is virtually polycyclic, then we can apply the following two results of Bridson to conclude that it’s in fact virtually abelian.

Lemma 5.

1. If ${G \curvearrowright X}$, a ${\mathrm{CAT}(0)}$ complex with finitely many shapes, then ${G}$ acts semi-simply with a discrete set of translation lengths.
2. If ${G}$ acts semi-simply and properly on a ${\mathrm{CAT}(0)}$ space, then any virtually solvable subgroup ${H < G}$ is virtually abelian.

(The number of shapes of a metric cell complex is the number distinct isometry classes of cells. In our case, ${X}$ has finitely many shapes since every cube of a given dimension is isometric and ${X}$ is has finite dimension. An action is semi-simple if there are points in the space realizing the translation lengths of each element. I.e., if for every $g \in G$ there’s a point realizing $\mathrm{inf}_{x \in X}d(x, gx)$).

If ${G}$ has a non-elementary fuchsian quotient, which must contain an ${F_2}$, then ${G}$ itself must contain an ${F_2}$.

Finally, suppose ${G}$ splits over a virtually polycyclic group ${P}$. Then by the first part of Bridson’s lemma above, ${G}$ acts semi-simply, and by the second part, ${P}$ must be virtually abelian. We analyze amalgamated products and HNN-extensions separately.

Suppose ${G = A \ast_P B}$. If ${[A:P] > 2}$ or ${[B:P]>2}$, then ${G}$ contains an ${F_2}$, by the normal form theorem for amalgamated products. If ${[A:P] = [B:P] = 2}$, then the Bass-Serre tree, on which ${G}$ acts, is homeomorphic to a line in which every edge is stabilized by a conjugate of ${P}$. Thus there’s an index 2 subgroup ${G' < G}$ acting by translations and ${\mathrm{ker}(G' \rightarrow \mathbb{Z}) = P}$. Hence ${G' \cong P \rtimes \mathbb{Z}}$, and so ${G}$ is virtually polycyclic and hence virtually abelian by Bridson’s lemma. This takes care of the amalgamated product case. To analyze an HNN-extension by ${P}$, as well as to prove this theorem for non-finitely generated ${G}$, another theorem is required.

Theorem 6 (Bridson-Haefliger). Suppose ${G \curvearrowright X}$ by semi-simple isometries and ${X}$ is ${\mathrm{CAT}(0)}$. Suppose also that

1. there’s a bound on the dimension of isometrically embedded flats,
2. the set of translation lengths of ${G}$ is discrete at 0, and
3. there is a bound on the order of finite subgroups.

Then any ascending sequence of virtually abelian subgroups stabilizes.

Suppose ${G = C \ast_P}$, with ${i_1}$ and ${i_2}$ being the two injections of ${P}$ into ${C}$. If ${[C:i_1(P)] > 1}$ and ${[C:i_2(P)] > 1}$, then by the normal form theorem for HNN-extensions, ${G}$ has an ${F_2}$ subgroup. If ${[C:i_1(P)] = 1}$, then ${[C:i_2(P)] = 1}$. [Otherwise, if ${i_2(P) = ti_1(P)t^{-1} < i_1(P)}$, consider the following subgroups of ${G}$:

$\displaystyle i_1(P) < t^{-1}i_1(P)t < t^{-2}i_1(P)t^2 < \cdots$

By the Bridson-Haefliger theorem above, this sequence must stabilize, hence ${i_1(P) = ti_1(P)t^{-1} = i_2(P)}$.] Then ${G \cong P \rtimes \mathbb{Z}}$, and by Bridson’s lemma, ${G}$ is virtually abelian.

This finishes the proof for finitely generated ${G}$. If ${G}$ is not finitely generated, it contains an ascending, non-stabilizing sequence of finitely generated subgroups

$\displaystyle G_1 < G_2 < G_3 < \cdots$

If any ${G_i}$ contains an ${F_2}$, we’re done. If not, then by the theorem applied to finitely generated groups, each is virtually abelian. Then conditions of the Bridson-Haefliger theorem above are satisfied, however, so a non-stabilizing ascending sequence is impossible. Hence if ${G}$ is not finitely generated, it contains an ${F_2}$.

Subgroups of products of surface and limit groups

This post is about strong generalizations of Baumslag and Roseblade’s theorem about subgroups of direct products of free groups. These generalizations were obtained by Bridson, Howie, Miller and Short. First they consider subgroups of direct products of surface groups. In this context, surface groups will be fundamental groups of orientable surfaces, which may have boundary, and may or may not be compact. Free groups are examples of surface groups. So the next theorem generalizes Baumslag and Roseblade’s.

Theorem 1 (Theorem A, here). Let ${G\leq \Gamma_1\times\cdots\times\Gamma_n}$, where ${\Gamma_i}$ are surface groups. If ${G}$ is of class ${\mbox{FP}_n}$, then it is virtually a direct product of at most ${n}$ surface groups.

Let ${G\leq \Gamma_1\times\cdots\times\Gamma_n}$ be a subgroup of any direct product. Let ${L_i = G\cap \Gamma_i}$. We say that ${G}$ is a subdirect product if all the ${L_i}$ are non-trivial. If ${\pi_i}$ is the projection from ${\Gamma_1\times\cdots\times\Gamma_n}$ that discards the ${i}$-th factor, then ${L_i=\ker(\pi_i|_G)}$. So if, say, ${L_n}$ is trivial, then ${\pi_n|_G}$ embeds ${G}$ into ${\Gamma_1\times\cdots\times\Gamma_{n-1}}$. This allows us to reduce the above theorem to subdirect products. This also allows for a more specific result.

Theorem 2 (Theorem B, here). Let ${G\leq \Gamma_1\times\cdots\times\Gamma_n}$, where ${\Gamma_i}$ are surface groups. Assume ${L_i=G\cap\Gamma_i}$ are non-trivial, and arrange them so that ${L_1,\ldots,L_r}$ are not finitely generated and ${L_{r+1},\ldots,L_n}$ are finitely generated. Then there exists ${G_0 \leq G}$ of finite index such that

1. ${G_0=B\times L'_{r+1} \times \cdots \times L'_n}$ with ${L'_i\leq\Gamma_i}$ (thus a surface group), ${L'_i}$ finitely generated, and ${B\leq \Gamma_1\times\cdots\times\Gamma_r}$.
2. If ${r\geq 1}$, then ${H_r(B;{\mathbb Z})}$ is not finitely generated.

So ${G_0}$, which is of finite index in ${G}$, decomposes into a “nice” part ${L'_{r+1} \times \cdots \times L'_n}$ which verifies Theorem 1, and another factor ${B}$ which contains the obstructions to the conditions of Theorem 1.

If ${r=0}$, then ${G_0}$ is a product of at most ${n}$ surface groups. Moreover, these factors (${L'_j}$) are finitely generated and embedded in corresponding factors of the overgroup ${\Gamma_1\times\cdots\times\Gamma_n}$.

And if ${r\geq 1}$, then ${G}$ is not ${\mbox{FP}_r}$. To see this, let’s recall the definition of the homology groups ${H_*(G;{\mathbb Z})}$. They are obtained from a projective resolution of ${{\mathbb Z}}$ over ${{\mathbb Z} G}$

$\displaystyle \cdots \rightarrow P_r \rightarrow \cdots \rightarrow P_1 \rightarrow {\mathbb Z} G \rightarrow {\mathbb Z} \rightarrow 0$

by applying the tensor product ${-\otimes_{{\mathbb Z} G}{\mathbb Z}}$, and then taking the homology of the resulting chain complex. By this construction, if ${H_r(G;{\mathbb Z})}$ is not finitely generated then ${P_r}$ cannot be finitely generated either. Also, the homology groups satisfy Künneth formula for the direct product

$\displaystyle H_m(A\times B) = \bigoplus_{i=0}^m H_i(A)\otimes H_{n-i}(B)$

Hence, if ${H_r(B;{\mathbb Z})}$ is not finitely generated, then ${G_0}$ (and ${G}$) is not ${\mbox{FP}_r}$.

Next we consider analogous results on subgroups of products of limit groups. In the last post we saw that finitely generated residually free groups are exactly the groups that embed into direct products of limit groups. Thus, such theorems will allow us to study the class of residually free groups.

Theorem 3 (Theorem A, here). Let ${G\leq \Gamma_1\times\cdots\times\Gamma_n}$, where ${\Gamma_i}$ are limit groups. If ${G}$ is of class ${\mbox{FP}_n({\mathbb Q})}$, then it is virtually a direct product of at most ${n}$ limit groups.

This may be considered as a generalization of Theorem 1 in the case when the ${\Gamma_i}$ are finitely generated. A group ${G}$ is of class ${\mbox{FP}_n({\mathbb Q})}$ if ${{\mathbb Q}}$ admits a projective resolution over ${{\mathbb Q} G}$

$\displaystyle \cdots \rightarrow P_n \rightarrow \cdots \rightarrow P_1 \rightarrow {\mathbb Q} G \rightarrow {\mathbb Q} \rightarrow 0$

with ${P_j}$ finitely generated for ${j\leq n}$.

Theorem 4 (Theorem B, here). Let ${G\leq \Gamma_1\times\cdots\times\Gamma_n}$, where ${\Gamma_i}$ are limit groups. Assume ${L_i=G\cap\Gamma_i}$ are non-abelian, and arrange them so that ${L_1,\ldots,L_r}$ are not finitely generated and ${L_{r+1},\ldots,L_n}$ are finitely generated. Then there exists ${G_0 \leq G}$ of finite index such that

1. ${G_0=B\times L'_{r+1} \times \cdots \times L'_n}$ with ${L'_i\leq\Gamma_i}$, ${L'_i}$ finitely generated (so they are limit groups), and ${B\leq \Gamma_1\times\cdots\times\Gamma_r}$.
2. If ${r\geq 1}$, then ${\dim_{{\mathbb Q}} H_j(B;{\mathbb Q})=\infty}$ for some ${j\leq r}$.

Again, if ${r\geq 1}$ then ${G}$ is not of class ${\mbox{FP}_n({\mathbb Q})}$. So Theorem 3 reduces to 4. As an example of an application to residually free groups, we prove the following.

Corollary 5 (Corollary 1.1, here). If a finitely generated residually free group is of type ${\mbox{FP}_{\infty}({\mathbb Q})}$, then it is virtually a direct product of finitely many limit groups.

Proof: Let ${G}$ be a residually free group. As in the last post, ${G}$ embeds into a product ${\Gamma_1\times\cdots\times\Gamma_n}$ of limit groups. Now, since ${G}$ is ${\mbox{FP}_{\infty}({\mathbb Q})}$ (and in particular ${\mbox{FP}_n({\mathbb Q})}$), we can apply Theorem 3. This gives us the conclussion. $\Box$

In their third paper, Bridson, Howie, Miller and Short were able to use the above theorems in order to prove many results about residually free groups. Here is a sample.

1. A residually free group is of type ${\mbox{F}_n}$ if and only if it is of type ${\mbox{FP}_n({\mathbb Q})}$.
2. A residually free group ${G}$ is finitely presented if and only if ${\dim H_2(G_0;{\mathbb Q})<\infty}$ for every ${G_0\leq G}$ of finite index.
3. The class of finitely presented residually free groups is recursively enumerable.
4. (${n}$-fold conjugacy problem) Let ${G}$ be a finitely presentable residually free group. There exists an algorithm that given two ${n}$-tuples ${(u_1,\ldots,u_n)}$ and ${(v_1,\ldots,v_n)}$ of words in the generators of ${G}$, determines whether or not there exists ${g\in G}$ such that ${u_i = gv_i g^{-1}}$ in ${G}$, for ${i=1,\ldots,n}$.
5. (Membership problem) Let ${G}$ be a finitely presentable residually free group and ${H\leq G}$ a finitely presentable subgroup. There exists an algorithm that given a word ${w}$ in the generators of ${G}$, determines whether or not ${w}$ represents an element in ${H}$.

Limit groups and residually free groups

The purpose of this post is to prepare for a discussion in our next post of three papers by Bridson, Howie, Miller and Short — the first about subgroups of direct products of surface groups, the second about subgroups of direct products of limit groups, and the third developing applications to residually free groups.

Here we provide some background on limit groups and residually free groups. Our sources are the surveys of Bestvina and Feighn and Wilton.

Definition 1. A group ${G}$ is residually free if for any ${g\in G}$, ${g\neq 1}$, there is a morphism ${f:G\rightarrow F_n}$ such that ${f(g)\neq 1}$.

Definition 2. A group ${G}$ is fully residually free (or ${\omega}$-residually free) if for any finite set ${X\subset G}$ such that ${1\notin X}$, there is a morphism ${f:G\rightarrow F_n}$ such that ${1\notin f(X)}$.

Definition 3. A limit group is a finitely generated fully residually free group.

First examples of limit groups include free groups ${F_n}$ (of course), free abelian groups ${{\mathbb Z}^n}$ (not too hard to prove), and fundamental groups of closed hyperbolic surfaces with ${\chi<-1}$ (see Wilton’s survey).

Equivalent definitions of limit groups

An alternative definition of a limit group, based on sequences of morphisms to free groups and their stable kernels, can be found in the surveys of Bestvina and Feighn and Wilton. A further definition, involving limits of finitely generated free groups in spaces of marked Cayley graphs, is described by Champetier and Guirardel.

As we will explain, starting with the examples of free groups, free abelian groups and surface groups, we can inductively obtain a large family of limit groups: the ${\omega}$-residually free towers. They play a major role, on account of the following theorem, obtained independently by Kharlampovich and Myasnikov, and by Sela, which provides a more explicit way to look at limit groups.

Theorem 3. Limit groups are exactly the finitely generated subgroups of ${\omega}$-residually free towers.

An ${\omega}$-residually free tower is obtained as the fundamental group of a complex ${X_n}$, for some ${n\geq 0}$. Such a complex is built in levels ${X_0, X_1, \ldots}$ as follows:

• ${X_0}$ is a wedge of graphs, ${m}$-dimensional tori ${T^m=(S^1)^m}$, and closed hyperbolic surfaces (with ${\chi<-1}$ ).
• ${X_{k+1}}$ is constructed by attaching to ${X_k}$ either of the following:
1. A compact surface with boundary ${\Sigma}$ (hyperbolic, ${\chi<-1}$), attached by the boundary, and with the condition that there must exist a retraction ${\rho:X_{k+1}\rightarrow X_k}$ with ${\rho_*(\pi_1(\Sigma))}$ non-abelian.
2. A torus of any dimension ${T^m=(S^1)^m}$, attached by a coordinate curve (i.e. ${S^1\times \{1\} \times \cdots \times \{ 1\}}$). It must also satisfy that the image of this coordinate curve in ${X_k}$ generates a maximal abelian subgroup of ${\pi_1(X_k)}$. (This amounts to saying that it is primitive and does not lie in a previous torus block.)

Key properties of limit groups

1. Limit groups are torsion–free. (After all, residually free group are torsion free.)
2. Limit groups are of type ${F_{\infty}}$. (A consequence of the results in the paper by Bestvina and Feighn about constructible limit groups).
3. A finitely generated subgroup of a limit group is a limit group itself. (It is again fully residually free.) So there are no dragons to be found amongst the subgroups of limit groups!
4. Abelian subgroups of limit groups are finitely generated. (See Bestvina-Feighn.)
5. Limit groups are commutative transitive: for all ${a,b,c}$, if ${[a,b]=[b,c]=1}$ then ${[a,c]=1.}$ (This is a particularly useful case of the next property).
6. Limit groups are exactly the finitely generated groups that have the same one-quantifier first-order theory as a free group — specifically, ${F_2}$ for a non–abelian limit group, and ${{\mathbb Z}}$ for ${{\mathbb Z}^n}$. (See Champetier-Guirardel.)
7. A freely indecomposable limit group splits non–trivially as a graph of groups with cyclic edge stabilizers

Factoring homomorphisms and Makanin–Razborov diagrams

Limit groups come up in the study of ${\mbox{Hom}(G,F_n)}$ for a finitely generated group ${G}$, through the following theorem.

Theorem 4. Let ${G}$ be a finitely generated group. There exist a finite family of epimorphisms ${\{q_i:G\rightarrow \Gamma_i \}_{i=1}^r}$ such that:

1. Each ${\Gamma_i}$ is a limit group.
2. Every morphism ${f:G\rightarrow F_n}$ factors through some map in this family, i.e. ${f=g\circ q_i}$ for some ${i}$, and some morphism ${g:\Gamma_i \rightarrow F_n}$.

The family of quotient maps in the theorem is called the (first layer of the) Makanin-Razborov diagram of ${G}$. Let ${K=\cap_i\ker q_i}$. It is easy to prove from the theorem that ${G}$ is residually free if and only if ${K=1}$. Moreover, ${G/K}$ is the maximal residually free quotient of ${G}$.

Consider the map ${q_1\times \cdots \times q_r : G \rightarrow \Gamma_1 \times \cdots \times \Gamma_r}$. It is clear that ${K}$ is its kernel. So every residually free group embeds into a direct product of limit groups. This will allow us to apply theorems about subgroups of direct products of limit groups to study residually free groups. We will see examples of this in the next post.

Surface subgroups of non-positively curved groups III: Right-angled Artin groups

This is the third of three posts based on a guest lecture by Sam Kim.

In the last post, we considered the question of which Artin groups have hyperbolic surface subgroups. There we focused on Artin groups of finite and Euclidean type. Here, we turn to some non–positively curved (NPC) Artin groups, namely right–angled Artin groups (RAAGs).

A RAAG is an Artin group ${A(\Gamma,m)}$ in which all the edges of ${\Gamma}$ are labeled by ${2}$, and so has the presentation

$\displaystyle A(\Gamma) \ = \ \langle \, v\in V(\Gamma) \, | \, vw=wv \mbox{\ if } \{v,w\} \in E(\Gamma) \ \rangle.$

Charney and Davis found that RAAGs admit ${K(G,1)}$s that are NPC cube complexes. (A metric space is NPC if it’s universal cover is CAT(0)). This allows us to use the following theorems. [A flag complex is a simplicial complex ${\Delta}$ in which every complete subgraph of the 1-skeleton spans a simplex. Notice that if ${X}$ is a cube complex, then ${\mbox{Lk}(X,v)}$ is naturally a simplicial complex. An induced subcomplex is a maximal subcomplex with vertices in a given subset.]

Theorem 1 (Bridson–Haefliger, page 201). Let ${X}$ and ${Y}$ be complete, connected, geodesic metric spaces. If ${X}$ is NPC and ${f:Y\rightarrow X}$ is locally an isometric embedding, then ${f}$ induces an injective morphism ${f_*:\pi_1(Y) \rightarrow \pi_1(X)}$.

Theorem 2 (Bridson–Haefliger, page 212). Let ${X}$ be a finite dimensional cubical complex. Then ${X}$ is NPC if and only if ${\mbox{Lk}(X,v)}$ is a flag complex for every vertex ${v}$ of ${X}$.

Theorem 3 (Charney 2000). A cubical map ${f:Y \rightarrow X}$ between finite dimensional cubical complexes is a local isometric embedding iff the following conditions hold for every vertex ${v}$ of ${Y}$.

1. The induced map ${\mbox{Lk}(f,v):\mbox{Lk}(Y,v) \rightarrow \mbox{Lk}(X,f(v))}$ is injective.
2. The image of ${\mbox{Lk}(f,v)}$ is an induced subcomplex of ${\mbox{Lk}(X,f(v))}$.

Here are some partial results on the question of which RAAGs contain hyperbolic surface groups. [Notation: ${C_n}$ is a cycle on ${n}$ vertices. If ${\Gamma}$ is a graph, then ${\Gamma^*}$ is the graph with the same vertices as ${\Gamma}$ and exactly the edges that are not in ${\Gamma}$ — i.e. ${\{v,w \}}$ is an edge of ${\Gamma^*}$ if and only if it is not an edge of ${\Gamma}$.]

1. Droms–Servatius–Servatius${A(C_n)}$ contains a hyperbolic surface group for ${n\geq 5}$.
2. Crisp–Wiest — Every hyperbolic surface group with ${\chi < -1}$ embeds into some RAAG.
3. Kim${A(C_n^*)}$ contains hyperbolic surface subgroups for ${n \geq 5}$.
4. Crisp–Sageev–Sapir — Determined which ${A(\Gamma)}$ with ${|V(\Gamma)|\leq 8}$ contain hyperbolic surface subgroups.

The proofs of these results more–or–less follow the process of constructing a map from a surface into a ${K(G,1)}$ of a RAAG, and show that this map induces an injective map between the fundamental groups. The key difficulty lies in this latter step; however, thanks to the nonpositive curvature of the associated spaces, the three theorems quoted above apply.

Surface subgroups of non-positively curved groups II: Artin groups

This is the second of three posts based on a guest lecture by Sam Kim.

We now consider Gromov’s question about the existence of hyperbolic surface subgroups in the context of Artin groups — a family closely related to Coxeter groups.

Define ${\theta(x,y,n)}$ to be the word ${xyxy\cdots}$ that alternates between the letters ${x}$ and ${y}$ and has length ${n}$. Suppose ${\Gamma}$ is a simplicial graph with a labeling of its edges ${m:E(\Gamma)\rightarrow {\mathbb Z}_{>1}}$. The associated Artin group is

$\displaystyle A(\Gamma,m) = \langle v\in V(\Gamma) | \theta(v,w,m_e)=\theta(w,v,m_e) \mbox{\ if } e=\{v,w\} \in E(\Gamma) \rangle.$

For example, the braid group on ${3}$ strands ${\mbox{BRAID}_3}$ has presentation ${\langle a,b | aba=bab \rangle}$ and so is $A(\Gamma,m)$ when $\Gamma$ is a two vertices connected by a singe edge and $m$ assigns the label ${3}$ to that edge.

The Coxeter group ${W(\Gamma,m)}$ is the quotient of ${A(\Gamma,m)}$ arising on adding the relations ${v^2=1}$ for all ${v\in V(\Gamma)}$.

Gordon, Long and Reid were the first to consider the question of which Artin groups contain hyperbolic surface subgroups. Let ${\Delta_{l,m,n}}$ be the triangle with edges labeled by ${(l,m,n)}$. They found that most Artin groups of finite and Euclidean type admit hyperbolic surface subgroups. To be precise, they left the question unresolved for Artin groups associated to ${\Delta_{2,3,5}}$, ${\Delta_{2,3,6}}$, and ${\Delta_{2,4,4}}$, and amongst all others of finite and Euclidean type only the groups in the families ${I_2(m)}$, ${A_1}$ and ${\tilde A_1}$ fail to contain hyperbolic surface groups.

${A(\Delta_{2,3,5})}$ is type ${H_3}$ and is of finite type, ${A(\Delta_{2,3,6})}$ is of type ${\tilde B_2}$, and ${A(\Delta_{2,4,4})}$ is of type ${\tilde G_2}$ and so of Euclidean type. For the first two, the problem remains open. We will discuss S. Kim’s (unpublished) account of why the last one admits a hyperbolic surface subgroup.

The standard presentation of a braid group (which you can find here) gives us that

$\displaystyle \mbox{BRAID}_4 \ = \ A(\Delta_{3,3,2}) \ = \ \langle \, a,b,c \, | \, aba=bab, bcb=cbc, ac=ca \, \rangle.$

First we show that this group contains a hyperbolic surface group. Let ${G=\pi_1(S^3-K)}$ where ${K}$ is the figure-eight knot. ${G}$ is known to contain a hyperbolic surface group (see [Cooper-Long-Reid 1997]), and to admit the presentation

$\displaystyle G \ = \ \langle \, x,y,t \, | \, x^t=xy, \, y^t = yxy \, \rangle.$

Using a similar argument to Mangum and Shanahan’s, one can embed ${G}$ into ${\mbox{BRAID}_4}$ via ${x\mapsto ac^{-1}}$, ${y\mapsto bac^{-1}b^{-1}}$ and ${t\mapsto abc^{-1}b^{-1}}$. So ${\mbox{BRAID}_4}$ also contains a surface group.

Now consider the subgroup ${\mbox{BRAID}_4^{(4)}}$ that fixes the ${4}$th string. It is generated by ${a,b,c^2}$, and it admits the presentation of ${A(\Delta_{3,4,2})}$ in these generators. It is an index ${4}$ subgroup of ${\mbox{BRAID}_4}$, so it also contains a surface group.

On the other hand, we can get an isomorphism ${\mbox{BRAID}_4^{(4)} \cong \mbox{BRAID}_3(S^1\times [0,1])}$, by fattening the ${4}$th string (see Kent-Peifer2002]). We can visualize the ${4}$th (fattened) puncture as the inner hole of the annulus, and the punctures ${1}$, ${2}$ and ${3}$ arranged in cyclic order around the annulus, and invariant under a rotation of ${2\pi/3}$. Then the element ${t=c^2ba}$ corresponds, as a braid in ${\mbox{BRAID}_3(S^1\times [0,1])}$, to a rotation of angle ${2\pi/3}$ on the target annulus. This gives a decomposition of ${\mbox{BRAID}_4^{(4)}}$ as a semi-direct product

$\displaystyle \mbox{BRAID}_4^{(4)} = A(\Delta_{3,3,3}) \rtimes \langle t \rangle$

where the first factor is generated by ${a,a^t,a^{t^2}}$. Consider the index ${3}$ subgroup

$\displaystyle A(\Delta_{3,3,3}) \times \langle t^3 \rangle.$

It contains a surface subgroup, since it has finite index in ${\mbox{BRAID}_4^{(4)}}$. But since it is a direct product, the surface subgroup must project isomorphically into the first factor (since a hyperbolic surface group cannot contain ${{\mathbb Z}^2}$).

Next we will consider a different index–3 subgroup of ${\mbox{BRAID}_4^{(4)}}$; namely, we take the subgroup ${\mbox{BRAID}_4^{(1)(4)}}$ of braids that fix the ${1}$st and ${4}$th punctures.
Let ${\phi:\mbox{BRAID}_4^{(1)(4)} \rightarrow {\mathbb Z}}$ be the morphism given by the winding number of the ${1}$st string around the ${4}$th string. Then ${\ker\phi \cong \mbox{BRAID}_2(\Sigma)}$, where ${\Sigma}$ is a pair of pants (a sphere minus three disks). This can be seen by fattening the ${1}$st and ${4}$th strings, and observing that in a braid in ${\ker\phi}$, they do not wind around each other.

In his thesis, Davide Moroni proved that this exact sequence splits, giving ${\mbox{BRAID}_4^{(1)(4)} \cong \ker\phi\times{\mathbb Z}}$. Thus, by the previous argument, ${\ker\phi \cong \mbox{BRAID}_2(\Sigma)}$ contains a surface group.

Moroni also proved that ${\mbox{BRAID}_2(\Sigma) = A(\Delta_{2,4,4})}$, and this finishes the proof.