GAP (walrus) - Chapter 1: Overview

‣ TriangleGroup( p, q, r ) ( function )

Returns a pregroup presentation for the (p,q,r)-triangle group, the pregroup is the pregroup of the free product of a cyclic group of order p generated by x and a cyclic group of order q generated by y together with the relation (xy)^r.

gap> T := TriangleGroup(2,3,7);
<pregroup presentation with 3 generators and 1 relators>
gap> Pregroup(T);
<pregroup with 4 elements in table rep>
gap> Relators(T);
[ <pregroup relator ([ "2", "3" ])^7> ]
gap> T := TriangleGroup(17,22,100);
<pregroup presentation with 37 generators and 1 relators>
gap> Pregroup(T);
<pregroup with 38 elements in table rep>
gap> Relators(T);
[ <pregroup relator ([ "2", "18" ])^100> ]
gap> IsHyperbolic(T, 1/6);
true

1.1-2 TriangleCommutatorQuotient

‣ TriangleCommutatorQuotient( m, n ) ( function )

‣ TriSH( arg ) ( function )

Returns a pregroup presentation of the quotient of the (2,3,m)-triangle group by the normal subgroup generated by nth power of the commutator of x and y. The name TriSH is a synonym for TriangleCommutatorQuotient provided for backwards compatibility and might be removed in the future.

1.1-3 RandomTriangleQuotient

‣ RandomTriangleQuotient( p, q, r, len ) ( function )

Returns the quotient of the (p,q,r)-triangle group by a random relator of length len.

1.1-4 JackButtonGroup

‣ JackButtonGroup( ) ( function )

The Jack-Button group, as suggested to me by Alan Logan. It is known to be hyperbolic, but the tester fails for it. The pregroup is the pregroup of the free group of rank 3 with generators a,b, and t and two relators t^-1atb^-1a^-1 and t^-1ata^-1b^-1.

gap> J := JackButtonGroup();
<pregroup presentation with 6 generators and 2 relators>
gap> Pregroup(J);
<pregroup of free group of rank 3>
gap> Relators(J);
[ <pregroup relator TatBA>, <pregroup relator TatAB> ]

1.1-5 RandomPregroupPresentation

‣ RandomPregroupPresentation( pg, nrel, lrel ) ( function )

Returns a pregroup presentation over the given pregroup pg with nrel randomly chosen relators of length lrel.

1.1-6 RandomPregroupWord

‣ RandomPregroupWord( pg, len ) ( function )

A random list of pregroup element numbers of the pregroup pregroup of length len. When interpreted as a pregroup word this is cyclically reduced.

This package provides the operations IsHyperbolic, ways of testing a finitely presented group for hyperbolicity in the sense of Gromov.

The algorithm is based on ideas by Richard Parker, and the theory is described in the paper "Polynomial time proofs that groups are hyperbolic".

1.2 Testing Hyperbolicity

The main function of this package is the so-called RSym-tester. Given a (pregroup) presentation of a group, this function will try to prove whether the group defined by the presentation is hyperbolic, and will give an answer in polynomial time. Since hyperbolicity is undecidable, the answer can be positive, negative, or inconclusive.

As a simple example consider the following. Triangle groups are known to be hyperbolic when the sum frac1p + frac1q + frac1r is less than 1. The parameter for IsHyperbolic (3.5-3) gives the algorithm a hint how hard it should try.

gap> triangle := TriangleGroup(2,3,7);
<pregroup presentation with 3 generators and 1 relators>
gap> IsHyperbolic(triangle, 1/6);
true
gap> triangle := TriangleGroup(3,3,3);
<pregroup presentation with 3 generators and 1 relators>
gap> IsHyperbolic(triangle, 1/6);
[ fail, [ [ 1, 0, 0, 0 ], [ 2, 1, 1, 1/36 ], [ 1, 2, 2, 1/18 ],
         [ 2, 3, 3, 1/12 ], [ 1, 4, 4, 1/9 ], [ 2, 5, 5, 5/36 ],
         [ 1, 6, 6, 1/6 ] ], [ 2, 5, 5, 5/36 ] ]

One can also create pregroup presentations by giving a pregroup and relators, that is, words over the pregroup.

gap> G1 := CyclicGroup(3);;
gap> pg := PregroupOfFreeProduct(G1,G1);
<pregroup with 5 elements in table rep>
gap> rel := [2,5,3,4,3,4,3,4,3,5,2,4,3,5,2,4,3,5,3,4,2,4,3,5];
[ 2, 5, 3, 4, 3, 4, 3, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 3, 4, 2, 4, 3, 5 ]
gap> pgp := NewPregroupPresentation(pg,[pg_word(pg,rel)]);
<pregroup presentation with 4 generators and 1 relators>
gap> res := RSymTest(pgp, 0);;
gap> res[1];
fail

1.3 The MAGMA-compatible interface

An implementation of the hyperbolicity testing algorithm and word-problem solver exist in MAGMA as well. For ease of comparison between the results these two systems give, walrus contains an interface that aims to be compatible with MAGMA's. Please refer to MAGMA's documentation for further details.

gap> F := FreeGroup("x", "y");;
gap> AssignGeneratorVariables(F);;
gap> rred := [ y^3 ];;
gap> rgreen := [ x^4, (x*y)^4 ];;
gap> IsHyperbolic(F, rred, rgreen, 1/10);
[ fail, [ [ 1, 0, 0, 0 ], [ 2, 1, 1, 13/120 ], [ 1, 2, 2, 13/60 ],
          [ 2, 3, 3, 13/40 ], [ 1, 4, 4, 13/30 ] ], [ 2, 3, 3, 13/40 ] ]

1 Overview

1.1 Examples