Properties of an FP-Group#

In this section intrinsics for providing information about the global properties of an fp-group are described.

Cardinality#

A very basic requirement is to determine whether a given fp-group \(G\) is finite or infinite. Unfortunately, this is a problem for which there is no general solution. Instead, an intrinsic Order is provided which attempts to prove that the group is finite and a second intrinsic IsInfiniteFPGroup is provided which attempts to prove that the group is infinite. If both fail to produce a result then no conclusion can be drawn.

We assume that the group is finite and try to prove that this assumption is true using coset enumeration and other techniques.

Order(G: parameters): GrpFP -> RngIntElt#

FactoredOrder(G: parameters): GrpFP -> [ <RngIntElt, RngIntElt> ]#

Given an fp-group \(G\), this function attempts to determine the order of \(G\) or to prove that \(G\) is infinite. If a finite order can be computed, the function Order returns the order as a positive integer, whereas the function FactoredOrder returns a sequence of prime power factors. The function FactoredOrder reports an error in all other cases, whereas the function Order returns the object Infinity, if \(G\) can be shown to be infinite and returns a value of 0 if neither a finite value for the group order nor a proof for the infinity of \(G\) can be obtained. No conclusions can be drawn from a return value 0 of Order.

In addition to the parameters controlling possibly invoked coset enumerations, there exist some other parameters controlling the strategy used by the functions Order and FactoredOrder. These parameters are described below.

Example: Order11 (ex-134948)#

We use the function Order without any parameters to compute the order of the group

\[G =\,\, <a, b\ |\ a^8, b^7, (ab)^2, (a^{-1}b)^3>.\]

> G<x, y> := FPGroup<x,y | x^8, y^7, (x*y)^2, (x^-1*y)^3>;
> G;
Finitely presented group G on 2 generators
Relations
    x^8 = Id(G)
    y^7 = Id(G)
    (x * y)^2 = Id(G)
    (x^-1 * y)^3 = Id(G)
> Order(G);
10752

Run in calculator

The strategy employed by the functions Order and FactoredOrder may involve trying to obtain information on certain subgroups of \(G\). Whether or not an attempt is made to construct a presentation for a subgroup arising in the course of the computation by means of Reidemeister-Schreier rewriting, is controlled by three parameters:

UseRewrite: BoolElt                      Default: true
MinIndex  : RngIntElt                    Default: 10
MaxIndex  : RngIntElt                    Default: 1000

If UseRewrite is set to false, attempts to construct presentations for subgroups are not made. Otherwise, MinIndex and MaxIndex specify for subgroups of which index range Reidemeister-Schreier rewriting is done.

The following strategy is used for trying to determine the order of \(G\).

(1): Check whether \(G\) is free. If so, \(G\) is either trivial or infinite.
(2): Check whether the presentation for \(G\) is deficient (i.e. whether the number of relations is smaller than the number of generators). If it is, \(G\) is infinite.
(3): Check the subgroups of \(G\) with known order. If such a subgroup is known to be infinite or if we can compute its index in G, we’re done.
(4): Try to compute the index of \(G\) in a supergroup of known order. (An infinite supergroup in which \(G\) has finite index proves \(G\) to be infinite.)
(5): Try to enumerate the cosets of the trivial subgroup in \(G\).
(6): Check the subgroups of known or easily computable index in \(G\). If we can compute the order of such a subgroup or prove that it is infinite, we’re done.
(7): Try to enumerate the cosets of some subgroups occurring “naturally” in the presentation of \(G\).
(8): Check the supergroups in which \(G\) has known or easily computable index. If we can compute the order of a supergroup or prove that it is infinite, we’re done.
(9): Try to rewrite \(G\) w.r.t. some supergroup and to enumerate the cosets of the trivial subgroup using the resulting presentation.

Steps requiring coset enumeration in \(G\) or a supergroup of \(G\) are skipped, if no relations are known for this group. Steps involving Reidemeister-Schreier rewriting may be skipped according to the values of the parameters mentioned above.

Experienced users can control the behaviour of coset enumerations which may be invoked by the functions Order and FactoredOrder with a wide range of parameters. Both functions – in addition to the parameters mentioned above – accept the same parameters as the function CosetEnumerationProcess in Subsec. Interactive Coset Enumeration.

The intrinsic IsInfiniteFPGroup attempts to prove that an fp-group is infinite by finding a subgroup that has an infinite abelian section.

IsInfiniteFPGroup(G : parameters): GrpFP -> BoolElt#

Given a finitely-presented group \(G\), the function attempts to establish that \(G\) is infinite. If it succeeds it returns true. Otherwise it returns false meaning that the tests it has made don’t prove the group to be infinite. This does not imply that the group is likely to be finite. The code searches for epimorphisms \(\phi\) of \(G\) and uses the Holt-Plesken cohomological criterion, as implemented in the intrinsic HasPositiveH1Dimension, to test for non-finiteness of the kernel of \(\phi\). The version in this release works best on groups \(G\) which are perfect or which have small abelian quotients. It will be extended to handle groups which have larger soluble quotients in a subsequent release.

At present epimorphisms are sought using four techniques that are described elsewhere in this chapter: L2-quotient, Simple Quotient, Low Index Subgroups and Low Index Normal Subgroups. The intrinsic has corresponding parameters L2Quot, SimQuot, LISub and LINSub that allow the user to control the types of epimorphisms to be used. The default is for all four methods to be employed – however, the user can turn any of them off by setting the appropriate parameter to false. A verbose flag InfGrp will provide some information about progress.

The application of the Holt-Plesken theorem to an epimorphism \(\phi\) requires a knowledge of the \(QH\) modules, where \(H\) is the image of \(\phi\). A database containing such modules for ATLAS groups of degree up to 1000 is available as an optional download. The serious user of IsInfiniteFPGroup is strongly advised to have this database available as it can save a great deal of runtime.

Example: Prove Inf1 (ex-fea44f)#

Consider the following one-relator quotient group of the triangle group \(\langle 2, 3, 7 \rangle\):

\[\langle x,y | x^2, y^3, (xy)^7, (x,y)^{12} \rangle\]

> SetVerbose("InfGrp", 2);
> G<x,y> := FPGroup<x,y|x^2, y^3, (x*y)^7, (x,y)^12>;
> inf := IsInfiniteFPGroup(G);
>
 L2Q SEARCH commencing:
   L2Q SEARCH Considering L2Qs with degrees in the interval [1, 1000]
 SIMPLE QUOTIENT Commence searching interval [60, 10000]:
   Found epi onto PSL(2, 7) of order 168 and degree 8: 0.000 secs.
   Found epi onto PSL(2, 13) of order 1092 and degree 14: 0.060 secs.
 SIMPLE QUOTIENT Search of interval [60, 10000] unsuccessful: 2 epis, 0.610
secs.

 NORMAL SUBGROUPS Search of indices [1, 1000] commencing:
 NORMAL SUBGROUPS Search of [1, 1000] unsuccessful: 1 + 0 subgroups, 0.200
secs.

 SUBGRP SEARCH of indices [1, 25] commencing:
 SUBGRP SEARCH of [1, 25] was unsuccessful: 8 + 8 subgroups, 0.990 secs.

 SIMPLE QUOTIENT Commence searching interval [20001, 100000]:
 SIMPLE QUOTIENT Search of interval [20001, 100000] unsuccessful: 0 epis,
0.620 secs.

 NORMAL SUBGROUPS Search of indices [1001, 10000] commencing:
 NORMAL SUBGROUPS Search of [1001, 10000] unsuccessful: 0 + 0 subgroups,
0.960 secs.

 SUBGRP SEARCH of indices [26, 50] commencing:
 SUBGRP SEARCH of [26, 50] was unsuccessful: 8 + 8 subgroups, 1.460 secs.

 SIMPLE QUOTIENT Commence searching interval [100001, 1000000]:
   Found epi onto J_2 of order 604800 and degree 100: 1.300 secs.
     For 4950-dim ex_sq of perm module, dim of H^1/Z is 1: 1.050 secs.
 SIMPLE QUOTIENT Search of interval [100001, 1000000] successful: 1 epis,
2.430 secs.

> inf;
true

Run in calculator

So the group \(G\) has the simple group \(J_2\) as quotient and the rational representation corresponding to the exterior square of \(J_2\)’s degree 100 permutation module lifted to \(G\) has first cohomology group of dimension 1. So \(G\) is infinite by an application of the Holt-Plesken theorem.

HasPositiveH1Dimension(G, phi : parameters): GrpFP, HomGrp -> BoolElt#

Given a finitely-presented group \(G\) and an epimorphism \(\phi\) of \(G\) onto a permutation group \(H\), this intrinsic returns true if some \({{\mathbb{Q}}}H\)-module, where \({{\mathbb{Q}}}\) is the field of the rationals, lifts to a \({{\mathbb{Q}}}G\)-module whose first cohomology group is non-trivial. By a result of Holt and Plesken this shows that \(G\) is infinite. The \({{\mathbb{Q}}}H\)-modules are obtained in three ways. The first consists of \({{\mathbb{Q}}}H\)-modules that are easily obtainable from the permutation representation of \(H\). The second method is to systematically construct the \({{\mathbb{Q}}}H\)-modules of \(H\) while the third source is the Magma database of rational representations of small simple groups. Parameters allow the user to specify which of these methods are used (see below).

The parameter ESLimit allows the user to place a limit on the dimension of exterior squares for which the Holt-Plesken test will be applied. If the parameter CmpIrrs is set to true then Magma will construct rational irreducible representations for \(H\) if they are not present in the database. If the parameter DBIrrs is set to true then Magma will use those irreducible modules for \(H\) that are available in the Rational Representations Database. Setting both CmpIrrs and DBIrrs to false specifies that the test should be applied only to the permutation module and its exterior square.

There are two signatures for this intrinsic where the second has a third argument needed by the intrinsic IsInfiniteFPGroup. Note that this version is only intended to be called internally. For all other uses the two-argument version should be used.

Small Cancellation Conditions#

SmallCancellationConditions(G): GrpFP -> RngIntElt, RnIntElt, FldRatElt)#

Print    : RngIntElt                    Default: 0
involgens: BoolElt                      Default: false

This functions calculates the values for which the small cancellation conditions \(T(i)\), \(C(j)\) and \(C'(k)\) are satisfied by the presentation \(G\). It returns \(i,j,k'\), where \(T(i)\), \(C(j)\), and \(C'(k)\) are satisfied for all \(k > k'\).

If the parameter involgens is set true then edges labelled by involutory generators \(x\) in a van Kampen diagram for \(G\) are regarded as undirected, and are not regarded as pieces of the relator \(x^2\).

Example: Small Cancel (ex-2f799a)#

> G := FPGroup< x,y | x^6, y^6, (x*y)^5, (x,y)^3 >;
> SmallCancellationConditions(G);
This presentation satisfies T( 3 ).
This presentation satisfies C( 5 ).
This presentation satisfies C'(k) for all k > 1/5 .
3 5 1/5

Run in calculator

Largeness#

IsLarge(G, L, U:parameters): GrpFP, RngIntElt, RngIntElt -> BoolElt, GrpFP#

Simplify   : BoolElt                      Default: true
MaxExponent: RngIntElt                    Default: 100000
TimeLimit  : RngIntElt                    Default: 10

Attempt to show that \(G\) has a subgroup with homomorphic image the free group of rank 2. If successful return true, plus a subgroup witness to this property. If not successful, return false. Note that false does not imply that \(G\) doesn’t have the stated property, just that no such subgroup has been found. The witness group returned has a finite index subgroup with the free group of rank 2 as a homomorphic image. The algorithm will consider subgroups of \(G\) with index \(h\) having \(L\le h\le U\).

We attempt to decide if G is large by calculating the (multivariable) Alexander polynomial of those subgroups \(H\) of \(G\) having index \(h\) in the given range, and also subgroups of H having index up to \(2h\) in \(G\).

Controls simplification of subgroup presentations.

If the abelian torsion of subgroup \(H\) is greater than MaxExponent we do not rewrite to obtain a presentation of \(H\).

If, in computing low index subgroups of a finite index subgroup \(H\) of \(G\), the low-index subgroup calculation takes more than TimeLimit in seconds, then abort without trying to find more subgroups of \(H\).