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.


\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


\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.


About berstein

berstein is the name under which participants in the Berstein Seminar - a mathematics seminar at Cornell - are blogging.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s