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 , ,…. Hercules fights a hydra by striking off its first letter. The hydra then regenerates as follows: each remaining letter , where , becomes and the 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 .
Example. Hercules defeats in five strikes:
(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 to be the number of strikes it takes Hercules to vanquish the hydra , and for integers , , define . For example, and (another fun exercise).
What we have is a variation on Ackermann’s famous fast–growing functions , defined for integers by: and . So, in particular, , and , the –fold iterated power of .
It turns out that is essentially a version of Ackermann’s function:
Proposition. For all , .
Recursion is apparent in the battle. Suppose is a hydra ( denotes some word on ). Then in the time it takes to kill , there appear letters (and many other letters besides) after the final . Disposing of those letters then represents an additional challenge for Hercules. So the time it takes to complete that initial task of killing determines the magnitude of the remaining challenge (the hydra that has grown up beyond the in that time).
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 and , distortion can be wild.
Theorem (Dison and Riley). Each
- is free–by–cyclic,
- can be presented with only one defining relator,
- is ,
- and is biautomatic,
and yet is a rank– free subgroup that is distorted .
Some parts of this theorem are easy to explain. That the are free–by–cyclic is evident from their presentations. As for being one–relator groups, by re–expressing the original relations as and for (convention: ) and then eliminating and defining , one can present with one relation, a nested commutator:
That is, the relation is where is the “Engel” word defined recursively by and for .
Samuelson was the first (we think) to prove is . Our approach is to recursively define a family of words by and for . By inducting on , one can verify that after substituting for every in , the words and become freely equal for all . So the relation can be replaced by to give an alternative one–relator presentation for :
Re–expressing this presentation via for as
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 . 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 is free of rank 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 on that represents the identity. So when the ‘s are carried through the word and collected at the end (using the defining relations of to change the they pass), the result is a word on the ‘s times a power of . But as represents , this word on the ‘s must freely reduce to the empty word and the power of must be zero. We show that the free reduction that occurs amongst the ‘s, must be echoed in free–reduction amongst some of the in — this is awkward; we use a somewhat messy induction on . So, in fact, must be the empty word. It follows that there are no non-trivial relations between the and so they generate a rank– free group. The most fun part of the theorem (I think) is that the distortion of in is so large. This is where the battle between Hercules and the hydra comes in. Consider —
Question. For what is ?
Let’s look at the instance where and . One can try to convert to a word on and times a power of by introducing a to pair the first letter with , and then carry the accompanying to the end of the word by conjugating through the intervening letters; then pair off the next likewise, and repeat:
Notice that the hydra battle
is playing out within this calculation. Pairing off the first letter with a corresponds to the removal of the first letter of a hydra and conjugating a through to the right–hand end corresponds to a regeneration. There is nothing special about and here. So, as Hercules triumphs, we have:
This calculation, run to its conclusion, is displayed in this van Kampen diagram:
Let denote the reduced word on which represents . 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 of a reduced word on of length (the word along the bottom of the diagram) to a word of length . Thus the distortion is at least .
Establishing the upper bound on the distortion of in 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 lead to easy examples of groups with extravagantly large Dehn functions:
has Dehn function when .
The more recent development is:
Theorem (N. Brady, Dison and Riley). For all , there is a hyperbolic group with a free rank– subgroup whose distortion is .
The are obtained by embellishing the . 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, is
where acts via an automorphism
where , , and the are some words on the which we won’t specify explicitly here. So comparing with , we’ve added and the seventeen , and now acts to interchange and , except it introduces some words on the whilst doing so. The basic point of this is to avoid the that is present in whilst maintaining the pattern of interaction between the and . The action of restricted to is an automorphism.
The subgroup which we claim is free of rank– and distorted is
Our proof of its freeness is similar to that of the corresponding result for . We obtain the distortion result by mimicking the calculations for in — the words involved become interspersed with the but the do not obstruct the calculations. An alternative (and entirely explicit) presentation for is encoded in the picture below, which displays the case . [The number of is . The numbers of and do not depend on .]
The letters shown on the diagram are the generators. Two defining relations are given by 2–cells: and . All the other defining relations are encoded in the graphs: an edge labelled from a vertex labelled to a vertex labelled corresponds to a relation . I won’t explain here why these presentations both give , except to say that the result in the background is that if a 2–complex admits an –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 , the four green edges have length , and all other edges have length .]
The way we prove that 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 , and then checking that no cells have all their corners giving rise to edges in the list.