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

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, 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#

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)#

> 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

Run in calculator

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). 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#

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)#

> F<x, y, z>:= FreeGroup(3);
> red:= [];
> green:= [(x*y*z)^2];
> ish, dehn, D1, D2 := IsHyperbolic(F, red, green);
> ish, dehn;
true true

Run in calculator

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 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)#

> F<a, b, c>:= FreeGroup(3);
> G:= quo<F | a^5, (b*c)^7>;
> ish, dehn, L1, L2 := IsHyperbolic(F, [], Relators(G));
> ish, dehn;
true true

Run in calculator

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 should be applied before invoking IsHyperbolic in this case.

Example: rsym2 (ex-cd92b6)#

> F<a, b, c>:= 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<F|green>);
> 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

Run in calculator

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)#

> F<a, b, c>:= 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<F|green>);
> 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

Run in calculator

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)#

> F<a, b>:= 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

Run in calculator

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)#

> 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

Run in calculator

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:

> 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

Run in calculator

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:

It is advisable to include all relators of the form \(x^3\) in red.
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)#

> F<x,y> := FreeGroup(2);
> red := [y^3]; green := [x^4, (x*y)^4 ];
> ish := IsHyperbolic(F, red, green);
> ish;
false

Run in calculator

That didn’t work, but let’s try breaking up the relator \(x^4\).

> F<x,y,t> :=FreeGroup(3);
> red := [y^3, x^2*t]; green := [t^2, (x*y)^4];
> ish, dehn := IsHyperbolic(F, red, green);
> ish, dehn;
true true

Run in calculator

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.

> F<a,b,c,d,e> := 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>

Run in calculator

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 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)#

> F<x,t,y,u> := 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

Run in calculator

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)#

> F<a, b>:= 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

Run in calculator

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)#

> F<a, b>:= 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)

Run in calculator