# Hyperbolic Groups For an introduction to the theory of hyperbolic groupss (also known as *word-hyperbolic* or sometimes *Gromov hyperbolic* groups), see for example [[Holt *et al.*, 2017](../../references.md#cite-hrr17)]. The problem of determining whether or not a finitely presented group is *hyperbolic* is undecidable in general, but if the group is hyperbolic, then it is possible in principle to verify this property, In the following two sections, we describe two Magma intrinsics for attempting to verify that a group is hyperbolic. The first of these requires the prior construction of an automatic structure for the group, whereas the second can be applied directly to a finitely presented group. ## Testing an Automatic Group for Hyperbolicity In this section we describe the version of the intrinsic `IsHyperbolic` that can applied to an automatic group. The other version of `IsHyperbolic`, described below in Section [Testing a Finitely Presented Group for Hyperbolicity](#sec-fpg-hyperbolicity), can be applied to any finitely presented group. It succeeds less often than the hyperbolicity test for an automatic group when applied to hyperbolic groups having a small number of generators, but is much faster when it does succeed, and it does not require the prior computation of an automatic structure for $G$. ### `IsHyperbolic(G): GrpAtc -> BoolElt, Rec` ```magma MaxTries : RngIntElt Default: 10 MaxBadWords: RngIntElt Default: 200 ``` This intrinsic attempts to prove that the automatic group $G$ is hyperbolic. If `true` is returned, then the group has been proved to be hyperbolic, and a finite state automaton that accepts all geodesic words over the group generators is also returned. If `false` is returned, then this means that $G$ has not been proved to be hyperbolic. It does *not* mean that $G$ is not hyperbolic, but the program has no possibility of proving it. It works by making successive attempts to construct the automaton that accepts geodesic words, and it gives up and returns `false` if it fails to do this after `MaxTries` attempts. So it may still be possible to verify hyperbolicity by increasing the value of this parameter. When an attempt fails, a set of at most `MaxBadWords` words is found consisting of geodesic words that are not accepted by the current version of the putative geodesic word acceptor. If the verbose flag “KBMAG” is set to $1$ or more, then the number of states of the putative geodesic word acceptor is printed after each attempt, which might help the use to decide whether it might be worthwhile to try with an increased value of `maxtries`. ### `Example: verbose (ex-29ea10)` ```magma > G := Group< x,y | x^3, y^3, (x*y)^6, (x,y)^6 >; > A := AutomaticGroup(G : Large:=true); > SetVerbose("KBMAG",1); > ish, GWA := IsHyperbolic(A); Word acceptor has 459 states There are 219 word differences Geodesic word acceptor has 1028 states Attempt number 1 failed. There are now 245 word differences Geodesic word acceptor has 762 states Attempt number 2 failed. There are now 251 word differences Geodesic word acceptor has 508 states Hyperbolicity proved after 3 attempts > ish; true ``` ### `IsConjugate(G, x, y): GrpAtc, GrpAtcElt, GrpAtcElt -> BoolElt, GrpAtcElt` Test elements $x$ and $y$ of the hyperbolic automatic group $G$ for conjugacy in $G$, and return `true` or `false`, together with an element $g$ with $g^{-1}xg=y$ in the positive case. This will only work if `IsHyperbolic`$(G)$ returns `true`. The algorithm, which is due to Eric Swenson and Joe Marshall, is described in []. and it can only be applied to elements of infinite order. It will exit with an error message if $x$ and $y$ have the same finite order. The first call of this function on an automatic group $G$ will require the computation of some automata, which may take some time. Subsequent calls on the same group $G$ will be fast. ## Testing a Finitely Presented Group for Hyperbolicity This version of the intrinsic `IsHyperbolic` attempts to prove that a finitely-presented group is hyperbolic. It is based on a forthcoming paper by Holt, Linton, Neunhöffer, Parker, Pfeiffer and Roney-Dougal, provisionally entitled *A New Approach to Proving Hyperbolicity*. If `IsHyperbolic` returns `true` then the given group is guaranteed to have a linear Dehn function, and hence be hyperbolic. It may fail and return `false`, in which case the group may still be hyperbolic: if it fails, then it returns extra data on the cause of failure, which may help the user to modify the presentation and try again. If `IsHyperbolic` succeeds, then the value of the parameter $\epsilon$ (written as `epsilon` in the intrinsic) yields information about the group. In particular, let $r$ be the length of the longest relator in `green`, then the Dehn function of the group is bounded above by $$ f(n) = n(4 + r + {3+r\over 2\epsilon}) - {3+r\over\epsilon}. $$ By default, if `IsHyperbolic` succeeds, then it also attempts to compute a Dehn algorithm for the group, which can be used to test whether words in the group generators define the identity element of the group. This attempt is usually successful but may fail. The alternative intrinsic, also called `IsHyperbolic`, for attempting to prove that an automatic group is hyperbolic was described above in Section [Testing an Automatic Group for Hyperbolicity](#sec-atc-hyperbolicity)). To use that version, it is necessary to first convert the finitely presented group $G$ into an automatic group, by using the function `AutomaticGroup(G)`. For groups with a moderately small number of generators, applying `IsHyperbolic` to an automatic group will succeed on more examples than the version of `IsHyperbolic` that we describe in this section. But the version in this section will typically be much faster if it does work, and it does not require prior computation of an automatic structure for the finitely-presented group $G$. Also the version described here can be applied to groups with large numbers (several thousands) of generators, and it can be used for investigating the asymptotic behaviour of such groups. ### `IsHyperbolic(F, red, green): GrpFP, SeqEnum, SeqEnum -> BoolElt, BoolElt, SeqEnum, SeqEnum` ```magma epsilon : FldRatElt Default: 1/10 VerifySolver: BoolElt Default: true Print : RngIntElt Default: 0 noboundary : BoolElt Default: false verifypgp : BoolElt Default: true complete : BoolElt Default: false ``` The group $F$ should be a free group, and `red` and `green` should be (possibly empty) lists $A$ and $B$ of elements of $F$ that define a finitely presented group $G = F/{\rm ncl}_F\langle A \cup B\rangle$. The words in `red` must all have length $3$. The easiest way to use `IsHyperbolic` is to put all relators into `green`, leaving `red` empty. The following example shows that $\langle x, y, z | (xyz)^2 \rangle$ is hyperbolic: ### `Example: rsym1 (ex-d7a495)` ```magma > F:= FreeGroup(3); > red:= []; > green:= [(x*y*z)^2]; > ish, dehn, D1, D2 := IsHyperbolic(F, red, green); > ish, dehn; true true ``` The variables `ish` and `dehn` are both `true`, which means that the group has been proved hyperbolic and a Dehn algorithm has been calculated. The data returned as `D1` can be used to decide whether words in $F$ define the identity element of $G$, using the function `IsIdentity` described in Section [The Dehn Algorithm](#using-dehn) below. The intrinsic `IsHyperbolic` can be applied to a group $G$ that is already constructed in Magma as a group of type `FPGroup`, as follows:- ### `Example: rsym6 (ex-b541e8)` ```magma > F:= FreeGroup(3); > G:= quo; > ish, dehn, L1, L2 := IsHyperbolic(F, [], Relators(G)); > ish, dehn; true true ``` ## Common Error Messages, and How to Avoid Them The function will return an error if `green` contains any relators of the form $ab$ with $a \neq b$. The intrinsic [`Simplify`](../FPGroups/simplification.md#function-grpfp-1-simplify) should be applied before invoking `IsHyperbolic` in this case. ### `Example: rsym2 (ex-cd92b6)` ```magma > F:= FreeGroup(3); > green:= [a*b, (a*b*c)^6]; > flag:= IsHyperbolic(F, [], green); Runtime error: Non-square relators must have length at least 3 > G:= Simplify(quo); > G; Finitely presented group on 2 generators Generators as words G.1 = $.1 G.2 = $.3 Relations G.2^6 = Id($) > flag:= IsHyperbolic(FreeGroup(G), [], Relators(G)); > flag; true ``` The function will also return an error if `green` contains any pairs of relators (or their inverses) that are identical in all but one letter. Again the function `Simplify` may be able to resolve the problem. ### `Example: Rsym 3 (ex-976118)` ```magma > F:= FreeGroup(3); > green:= [(a*b*c)^2, a*b*c*a*b*b]; > IsHyperbolic(F, [], green); Runtime error: A piece of a relator consists of all but one letter > G:= Simplify(quo); > G; Finitely presented group G on 2 generators Generators as words G.1 = $.1 G.2 = $.2 Relations (G.1 * G.2^2)^2 = Id(G) > IsHyperbolic(FreeGroup(G), [], Relators(G)); true ``` ## The Relators red The `IsHyperbolic` function is based on a generalisation of the ideas of small cancellation theory. If a presentation contains very short relators then it is harder for small cancellation conditions to be satisfied. However, it is possible for `IsHyperbolic` to work on such presentations, by using the `red` relators. These relators are required to have length $3$ and (together with any relators of the form $x^2$ in `green`) should define a pregroup structure on the group generators, their inverses, and the identity, as defined by Stallings. A *pregroup* $P$ is a set $X$, with a distinguished element $1$, an involution $\sigma$ and a partial multiplication $(x, y) \to xy$ which is defined for $(x, y) \in D(P)$, satisfying five axioms. The first three of these axioms essentially state that $\sigma$ operates in the same way as group inversion, and that $1$ acts as an identity. The final two axioms are (P4) if $(x, y), (y, z) \in D(P)$ then $(xy, z) \in D(P)$ if and only if $(x, yz) \in D(P)$, in which case $(xy)z = x(yz)$; and (P5) if $(x, y), (y, z), (z, t) \in D(P)$ then at least one of $(xy, z)$ and $(yz, t)$ is in $D(P)$. These axioms are checked unless the parameter `verifypgp` is set to `false`. Any group which is a quotient of a free product of free and finite groups can be defined by a presentation with relators in `red` and `green`, satisfying a pregroup structure. It is also possible to present any group which is a quotient of a virtually free group by including additional relators in this way, but the choice of relators to put in `red` may be more complicated. The following example shows that the quotient $\langle a, b | a^2, b^3, (ab)^7 \rangle$ of the modular group $C_2 \ast C_3$ is hyperbolic. ### `Example: Rsym 4 (ex-5a8018)` ```magma > F:= FreeGroup(2); > ish:= IsHyperbolic(F, [], [a^2, b^3, (a*b)^7]); > ish; false > red:= [b^3]; > green:= [a^2, (a*b)^7]; > ish, dehn := IsHyperbolic(F, red, green); > ish, dehn; true true ``` As a more complicated example, the following example shows how to work with a quotient of $S_3 \ast C_3 \ast Z$, using the function `RedRelatorsForFreeProduct`. ### `RedRelatorsForFreeProduct(groupList, freeFacs): List, RngIntElt -> GrpFP, SeqEnum, SeqEnum, Map, SeqEnum` The list `groupList` should be a nonempty list of finite permutation groups $G_1, \ldots, G_t$, and the integer `freeFacs` should be an integer $k \geq 0$. It produces the free product $G_1 \ast G_2 \ast \cdots \ast G_t \ast F_k$ in a form that can be worked with by `IsHyperbolic`. The function `RedRelatorsForFreeProduct` will return a free group, a list of red relators, a list of involutory generators (to which additional green relators can be added by the user) and a function for turning lists of elements from the groups $G_i$ and $F_k$ into relators over the free product. The final return value is a list of generators for each group, in the order to which they correspond to the generators of the new free group $F$, and may be helpful for checking accuracy. ### `Example: Rsym Red1 (ex-fac47e)` ```magma > groupList:= [*Sym(3), CyclicGroup(3)*]; > F, red, green, GreenRelator, gens:= > RedRelatorsForFreeProduct(groupList, 1); > F; Finitely presented group F on 6 generators (free) > ish, dehn := IsHyperbolic(F, red, green); > ish, dehn; true true ``` This is unsurprising, since only a free product has been constructed at this point! The next step is to define an additional relator, using the returned function `GreenRelator`: ```magma > extra_rel:= GreenRelator([* < 1, Sym(3)!(1, 3, 2)>, > <3, 1>, <2, CyclicGroup(3)!(1, 2, 3)>, <3, -1>, > <2, CyclicGroup(3)!(1, 3, 2)>, <1, Sym(3)!(1, 2)>, <3, 1>*]); > extra_rel; F.1^-1 * F.6 * F.5 * F.6^-1 * F.5^-1 * F.3 * F.6 > Append(~green, extra_rel); > ish, dehn, D1, D2 := IsHyperbolic(F, red, green); > ish, dehn; true false ``` So this is an example where hyperbolicity was proved, but `IsHyperbolic` failed to compute a Dehn algorithm. In this case, the data items `D1` and `D2` provide extra information on the cause of this failure as described in the forthcoming paper mentioned earlier. If it is not known how to represent the input group as a quotient of a free product of groups, and `IsHyperbolic` fails to succeed with the given presentation, some general tips are: 1. It is advisable to include all relators of the form $x^3$ in `red`. 2. If there are relators $x^k$ for small values of $k$ ($k \le 6$), then it may be a good idea to introduce new generators so that the relator $x^k$ can be broken up into relators of length $3$, all of which can be put into `red`. This is illustrated in the following example. ### `Example: rsym5 (ex-2ba258)` ```magma > F := FreeGroup(2); > red := [y^3]; green := [x^4, (x*y)^4 ]; > ish := IsHyperbolic(F, red, green); > ish; false ``` That didn’t work, but let’s try breaking up the relator $x^4$. ```magma > F :=FreeGroup(3); > red := [y^3, x^2*t]; green := [t^2, (x*y)^4]; > ish, dehn := IsHyperbolic(F, red, green); > ish, dehn; true true ``` However, it will not always work simply to put all relators of length $3$ into `red`, as the conditions for being a pregroup may fail. ```magma > F := FreeGroup(5); > red := [a*b*c^-1, b*c*d^-1, c*d*e^-1, d*e*a^-1, e*a*b^-1 ]; > IsHyperbolic(F,red,[]); Runtime error: Pregroup axiom (P5) fails on generators <1, 2, 3, 4> ``` Here is another example, where we use the same technique to prove that the group $\langle x,y \mid x^4, y^5, (xy)^7, [x,y]^3 \rangle$ is hyperbolic. Note that the alternative intrinsic `IsHyperbolic` described in Section [Testing an Automatic Group for Hyperbolicity](#sec-atc-hyperbolicity) for proving hyperbolicity of automatic groups succeeds on the groups $\langle x,y \mid x^4, y^5, (xy)^k, [x,y]^3 \rangle$ for all $k \ge 4$. ### `Example: rsym6 (ex-7ee847)` ```magma > F := FreeGroup(4); > ish, dehn := IsHyperbolic(F, [x^2*t, y^2*u, u^-2*y], [t^2, (x*y)^7, (x,y)^3]); > ish, dehn; true true ``` ## The Parameter epsilon The intrinsic `IsHyperbolic` works by attempting to move positive curvature in van Kampen diagrams for the group presentation to the boundary of these diagrams. The aim is to ensure that, after this curvature shifting, all non-boundary regions of a diagram that are labelled by green relators have negative curvature of at most $-$`epsilon`, where `epsilon` is a small positive number that can be adjusted by the user. Its default value is $1/10$. If `IsHyperbolic` fails, then the third and fourth return values describe how it failed, in the form of a list of lists and a list of places. If the fourth value in the third entry is less than the value of `epsilon` that was used, then running again with a smaller value of `epsilon` *might* enable it to succeed. Conversely, if it succeeds with the default value, then the user may wish to try again with a larger value of $\epsilon$, to deduce lower bounds for the Dehn function. ### `Example: Rsym Eps (ex-9972b6)` ```magma > F:= FreeGroup(2); > ish, dehn, D1, D2:= IsHyperbolic(F, [b^3], [a^2, (a*b)^7]: epsilon:= 1/5); > ish, dehn; false false > D1; [ [ 1, 0, 0, 0, 0, 0 ], [ 1, 2, 1, 1/210, 1, 2 ], [ 1, 4, 2, 1/105, 2, 2 ], [ 1, 6, 3, 1/70, 3, 2 ], [ 1, 8, 4, 2/105, 4, 2 ], [ 1, 10, 5, 1/42, 5, 2 ], [ 1, 12, 6, 1/35, 6, 2 ], [ 1, 14, 7, 1/30, 7, 2 ] ] > ish, dehn, D1, D2:= IsHyperbolic(F, [b^3], [a^2, (a*b)^7]: epsilon:= 1/6); > ish, dehn; true true ``` And it worked this time! ## The Dehn Algorithm ### `IsIdentity(w, D1): GrpFPElt, Rec -> BoolElt, GrpFPElt, SeqEnum, SeqEnum` If `IsHyperbolic` has proved that a group $G$ is hyperbolic and computed a Dehn algorithm for $G$, then the data returned as the third return value can be used to apply the Dehn algorithm to words in the free group, and to test whether they map onto the identity element of $G$. The result of application of the Dehn algorithm to the word is also returned. In general, it is possible for different representatives of the same group element to reduce to different words, so this reduction cannot be used as a normal form for group elements. ### `Example: Rsym Dehn (ex-1c88ea)` ```magma > F:= FreeGroup(2); > ish, dehn, D1, D2:= IsHyperbolic(F, [b^3], [a^2, (a*b)^7]); > ish, dehn; true true > isid, wd := IsIdentity((a*b^2)^6,D1); > isid, wd; false b * a > isid, wd := IsIdentity(b^-1*(a*b^2)^6*a,D1); > isid, wd; true Id(F) ```