|
For an introduction to the theory of hyperbolic groupss
(also known as word-hyperbolic or sometimes Gromov hyperbolic
groups), see for example [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.
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.
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.
> 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
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
ε (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/2ε)) - (3 + r/ε).
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.
The intrinsic IsHyperbolic can be applied to a group G that is already
constructed in Magma as a group of type FPGroup, as follows:-
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/(ncl)F< A ∪B >. 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 < x, y, z | (xyz)2 > is
hyperbolic:
> F<x, y, z>:= 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
below.
> 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
The function will return an error if green contains any relators of
the form ab with a != b. The intrinsic Simplify should
be applied before invoking IsHyperbolic in this case.
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.
> 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
> 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
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 x2 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 σ and a partial multiplication (x, y) to xy
which is defined for (x, y) ∈D(P), satisfying
five axioms. The first three of these axioms essentially state that σ
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) ∈D(P) then
(xy, z) ∈D(P) if and only if (x, yz) ∈D(P), in which
case (xy)z = x(yz); and
(P5) if (x, y), (y, z), (z, t) ∈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
< a, b | a2, b3, (ab)7 > of the modular group
C2 ast C3 is hyperbolic.
As a more complicated example, the following example shows
how to work with a quotient of
S3 ast C3 ast Z, using the function RedRelatorsForFreeProduct.
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 x3 in
red.
- 2.
- If there are relators xk for small values of k (k ≤6),
then it may be a good idea to introduce new generators so that the relator
xk can be broken up into relators of length 3, all of which can be put
into red.
This is illustrated in the following example.
Here is another example, where we use the same technique to prove that the group
< x, y | x4, y5, (xy)7, [x, y]3 > 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
< x, y | x4, y5, (xy)k, [x, y]3 > for all k ≥4.
> 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
The list groupList should be a nonempty list of finite permutation
groups G1, ..., Gt, and the
integer freeFacs should be an integer k ≥0. It produces
the free product G1 ast G2 ast ... ast Gt ast Fk 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 Gi and Fk 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.
> 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:
> 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
> F<x,y> := 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.
> 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
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>
> 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
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 ε, to deduce lower bounds
for the Dehn function.
> 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
And it worked this time!
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.
> 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)
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|