45 Finitely Presented Groups

returns true if H is a finitely presented group or a subgroup of a finitely presented group.

is a synonym for IsSubgroupFpGroup(G) and IsGroupOfFamily(G).

Free groups are a special case of finitely presented groups, namely finitely presented groups with no relators.

Another special case are groups given by polycyclic presentations. GAP uses a special representation for these groups which is created in a different way. See chapter Pc Groups for details.

The info class for functions dealing with finitely presented groups is InfoFpGroup.

45.1 Creating Finitely Presented Groups

creates a finitely presented group given by the presentation 〈gens | rels 〉 where gens are the generators of the free group F. Note that relations are entered as relators, i.e., as words in the generators of the free group. To enter an equation use the quotient operator, i.e., for the relation a^b = ab one has to enter a^b/(a*b).

gap> f := FreeGroup( 3 );;
gap> f / [ f.1^4, f.2^3, f.3^5, f.1*f.2*f.3 ];
<fp group on the generators [ f1, f2, f3 ]>

returns the factor group G/N of G by the normal closure N of elts where elts is expected to be a list of elements of G.

45.2 Comparison of Elements of Finitely Presented Groups

Two elements of a finitely presented group are equal if they are equal in this group. Nevertheless they may be represented as different words in the generators. Because of the fundamental problems mentioned in the introduction to this chapter such a test may take very long and cannot be guaranteed to finish.

The method employed by GAP for such an equality test use the underlying finitely presented group. First (unless this group is known to be infinite) GAP tries to find a faithful permutation representation by a bounded Todd-Coxeter. If this fails, a Knuth-Bendix (see Rewriting Systems and the Knuth-Bendix Procedure) is attempted and the words are compared via their normal form.

If only elements in a subgroup are to be tested for equality it thus can be useful to translate the problem in a new finitely presented group by rewriting (see IsomorphismFpGroup);

The equality test of elements underlies many ``basic'' calculations, such as the order of an element, and the same type of problems can arise there. In some cases, working with rewriting systems can still help to solve the problem. The ``kbmag' package provides such functionality, see the package manual for further details.

Problems get even worse when trying to compute a total ordering on the elements of a finitely presented group. As any ordering that is guaranteed to be reproducible in different runs of GAP or even with different groups given by syntactically equal presentations would be prohibitively expensive to implement, the ordering of elements is depending on a method chosen by GAP and not guaranteed to stay the same when repeating the construction of an FpGroup. The only guarantee given for the < ordering for such elements is that it will stay the same for one family during its lifetime. The attribute FpElmComparisonMethod is used to obtain a comparison function for a family of FpGroup elements.

If fam is the elements family of a finitely presented group this attribute returns a function smaller(left, right) that will be used to compare elements in fam.

for an fp group f, an element e of it or the family fam of its elements this function will force immediate reduction when multiplying, keeping words short at extra cost per multiplication.

45.3 Preimages in the Free Group

returns the underlying free group for the finitely presented group G. This is the group generated by the free generators provided by FreeGeneratorsOfFpGroup(G).

FreeGeneratorsOfFpGroup returns the underlying free generators corresponding to the generators of the finitely presented group G which must be a full fp group.

FreeGeneratorsOfWholeGroup also works for subgroups of an fp group and returns the free generators of the full group that defines the family.

returns the relators of the finitely presented group G as words in the free generators provided by FreeGeneratorsOfFpGroup(G).

gap> f := FreeGroup( "a", "b" );;
gap> g := f / [ f.1^5, f.2^2, f.1^f.2*f.1 ];
<fp group on the generators [ a, b ]>
gap> Size( g );
10
gap> FreeGroupOfFpGroup( g ) = f;
true
gap> FreeGeneratorsOfFpGroup( g );
[ a, b ]
gap> RelatorsOfFpGroup( g );
[ a^5, b^2, b^-1*a*b*a ]

Elements of a finitely presented group are not words, but are represented using a word from the free group as representative. The following two commands obtain this representative, respectively create an element in the finitely presented group.

Let elm be an element of a group whose elements are represented as words with further properties. Then UnderlyingElement returns the word from the free group that is used as a representative for elm.

gap> w := g.1*g.2;
a*b
gap> IsWord( w );
false
gap> ue := UnderlyingElement( w );
a*b
gap> IsWord( ue );
true

If fam is the elements family of a finitely presented group and word is a word in the free generators underlying this finitely presented group, this operation creates the element with the representative word in the free group.

gap> ge := ElementOfFpGroup( FamilyObj( g.1 ), f.1*f.2 );
a*b
gap> ge in f;
false
gap> ge in g;
true

45.4 Operations for Finitely Presented Groups

Finitely presented groups are groups and so all operations for groups should be applicable to them (though not necessarily efficient methods are available.) Most methods for finitely presented groups rely on coset enumeration. See Coset Tables and Coset Enumeration for details.

The command IsomorphismPermGroup can be used to obtain a faithful permutation representation, if such a representation of small degree exists. (Otherwise it might run very long or fail.)

gap> f := FreeGroup( "a", "b" );
<free group on the generators [ a, b ]>
gap> g := f / [ f.1^2, f.2^3, (f.1*f.2)^5 ];
<fp group on the generators [ a, b ]>
gap> h := IsomorphismPermGroup( g );
[ a, b ] -> [ (1,2)(4,5), (2,3,4) ]
gap> u:=Subgroup(g,[g.1*g.2]);;rt:=RightTransversal(g,u);
RightTransversal(<fp group of size 60 on the generators [ a, b ]>,Group(
[ a*b ]))
gap> Image(ActionHomomorphism(g,rt,OnRight));
Group([ (1,2)(3,4)(5,7)(6,8)(9,10)(11,12), (1,3,2)(4,5,6)(7,8,9)(10,11,12) ])

45.5 Coset Tables and Coset Enumeration

Coset enumeration (see Neu82 for an explanation) is one of the fundamental tools for the examination of finitely presented groups. This section describes GAP functions that can be used to invoke a coset enumeration.

Note that in addition to the built-in coset enumerator there is the GAP package ACE. Moreover, GAP provides an interactive Todd-Coxeter in the GAP package ITC which is based on the XGAP package.

returns the coset table of the finitely presented group G on the cosets of the subgroup H.

Basically a coset table is the permutation representation of the finitely presented group on the cosets of a subgroup (which need not be faithful if the subgroup has a nontrivial core). Most of the set theoretic and group functions use the regular representation of G, i.e., the coset table of G over the trivial subgroup.

The coset table is returned as a list of lists. For each generator of G and its inverse the table contains a generator list. A generator list is simply a list of integers. If l is the generator list for the generator g and if l[i] = j then generator g takes the coset i to the coset j by multiplication from the right. Thus the permutation representation of G on the cosets of H is obtained by applying PermList to each generator list (see PermList).

The coset table is standard (see below).

For finitely presented groups, a coset table is computed by a Todd-Coxeter coset enumeration. Note that you may influence the performance of that enumeration by changing the values of the global variables CosetTableDefaultLimit and CosetTableDefaultMaxLimit described below and that the options described under CosetTableFromGensAndRels are recognized.

gap> tab := CosetTable( g, Subgroup( g, [ g.1, g.2*g.1*g.2*g.1*g.2^-1 ] ) );
[ [ 1, 4, 5, 2, 3 ], [ 1, 4, 5, 2, 3 ], [ 2, 3, 1, 4, 5 ], [ 3, 1, 2, 4, 5 ] ]
gap> List( last, PermList );
[ (2,4)(3,5), (2,4)(3,5), (1,2,3), (1,3,2) ]
gap> PrintArray( TransposedMat( tab ) );
[ [  1,  1,  2,  3 ],
  [  4,  4,  3,  1 ],
  [  5,  5,  1,  2 ],
  [  2,  2,  4,  4 ],
  [  3,  3,  5,  5 ] ]

The last printout in the preceding example provides the coset table in the form in which it is usually used in hand calculations: The rows correspond to the cosets, the columns correspond to the generators and their inverses in the ordering g₁, g₁⁻¹, g₂, g₂⁻¹. (See section Standardization of coset tables for a description on the way the numbers are assigned.)

Traces the coset number pt under the word word through the coset table tab. (Note: word must be in the free group, use UnderlyingElement if in doubt.)

gap> TracedCosetFpGroup(tab,UnderlyingElement(g.1),2);
4

returns the action of G on the cosets of the subgroup H of G.

gap> u := Subgroup( g, [ g.1, g.1^g.2 ] );
Group([ a, b^-1*a*b ])
gap> FactorCosetAction( g, u );
[ a, b ] -> [ (2,4)(5,6), (1,2,3)(4,5,6) ]

returns a coset table for the action of G on the cosets of H. The columns of the table correspond to the GeneratorsOfGroup(G).

is an internal function which is called by the functions CosetTable, CosetTableInWholeGroup and others. It is, in fact, the proper working horse that performs a Todd-Coxeter coset enumeration. fgens must be a set of free generators and grels a set of relators in these generators. fsgens are subgroup generators expressed as words in these generators. The function returns a coset table with respect to fgens.

CosetTableFromGensAndRels will call TCENUM.CosetTableFromGensAndRels. This makes it possible to replace the built-in coset enumerator with another one by assigning TCENUM to another record.

The library version which is used by default performs a standard Felsch strategy coset enumeration. You can call this function explicitly as GAPTCENUM.CosetTableFromGensAndRels even if other coset enumerators are installed.

The expected parameters are

fgens

generators of the free group F

grels

relators as words in F

fsgens

subgroup generators as words in F.

CosetTableFromGensAndRels processes two options (see chapter Options Stack):

max

The limit of the number of cosets to be defined. If the enumeration does not finish with this number of cosets, an error is raised and the user is asked whether she wants to continue. The default value is the value given in the variable CosetTableDefaultMaxLimit. (Due to the algorithm the actual limit used can be a bit higher than the number given.)

silent

if set to true the algorithm will not raise the error mentioned under option max but silently return fail. This can be useful if an enumeration is only wanted unless it becomes too big.

is the default limit for the number of cosets allowed in a coset enumeration.

A coset enumeration will not finish if the subgroup does not have finite index, and even if it has it may take many more intermediate cosets than the actual index of the subgroup is. To avoid a coset enumeration ``running away'' therefore GAP has a ``safety stop'' built in. This is controlled by the global variable CosetTableDefaultMaxLimit.

If this number of cosets is reached, GAP will issue an error message and prompt the user to either continue the calculation or to stop it. The default value is 256000.

See also the description of the options to CosetTableFromGensAndRels.

gap> f := FreeGroup( "a", "b" );;
gap> u := Subgroup( f, [ f.2 ] );
Group([ b ])
gap> Index( f, u );
Error, the coset enumeration has defined more than 256000 cosets
 called from
TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
CosetTableFromGensAndRels( fgens, grels, fsgens ) called from
TryCosetTableInWholeGroup( H ) called from
CosetTableInWholeGroup( H ) called from
IndexInWholeGroup( H ) called from
...
Entering break read-eval-print loop ...
type 'return;' if you want to continue with a new limit of 512000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit
brk> quit;

At this point, a break-loop (see Section Break Loops) has been entered. The line beginning Error tells you why this occurred. The next seven lines, occur if OnBreak has its default value of Where (see OnBreak) and explains, in this case, how GAP came to be doing a coset enumeration. Then you are give a number of options of how to escape the break-loop: you can either continue the calculation with a larger number of permitted cosets, stop the calculation if you don't expect the enumeration to finish (like in the example above), or continue without a limit on the number of cosets. (Choosing the first option will, of course, land you back in a break-loop. Try it!)

Setting CosetTableDefaultMaxLimit (or the max option value, for any function that invokes a coset enumeration) to infinity (or to 0) will force all coset enumerations to continue until they either get a result or exhaust the whole available space. For example, each of

gap> CosetTableDefaultMaxLimit := 0;;
gap> Index( f, u );

or

gap> Index( f, u : max := 0 );

have essentially the same effect as choosing the third option (typing: maxlimit := 0; return;) at the brk> prompt above (instead of quit;).

is the default number of cosets with which any coset table is initialized before doing a coset enumeration.

The function performing this coset enumeration will automatically extend the table whenever necessary (as long as the number of cosets does not exceed the value of CosetTableDefaultMaxLimit), but this is an expensive operation. Thus, if you change the value of CosetTableDefaultLimit, you should set it to a number of cosets that you expect to be sufficient for your subsequent coset enumerations. On the other hand, if you make it too large, your job will unnecessarily waste a lot of space.

The default value of CosetTableDefaultLimit is 1000.

is an internal function which is used in some applications of coset table methods. It returns the first of those generators of the given finitely presented group G which occur most frequently in the relators.

returns the indices of those generators of the finitely presented group G which are known to be involutions. This knowledge is used by internal functions to improve the performance of coset enumerations.

45.6 Standardization of coset tables

For any two coset numbers i and j with i < j the first occurrence of i in a coset table precedes the first occurrence of j with respect to the usual row-wise ordering of the table entries. Following the notation of Charles Sims' book on computation with finitely presented groups Sims94 we call such a table a standard coset table.

The table entries which contain the first occurrences of the coset numbers i > 1 recursively provide for each i a representative of the corresponding coset in form of a unique word w_i in the generators and inverse generators of G. The first coset (which is H itself) can be represented by the empty word w₁. A coset table is standard if and only if the words w₁, w₂, ... are length-plus-lexicographic ordered (as defined in Sims94), for short: lenlex.

We would like to warn you that this standardization of coset tables is different from the concept that we have used in earlier GAP versions. That old concept ignored the columns that correspond to inverse generators and hence only considered words in the generators of G. We will call the old standard the semilenlex standard as it would also work in the case of semigroups where no inverses of the generators are known.

We have changed the convention from the semilenlex standard to the lenlex standard because the definiton of a standard coset table in Sims' book tends to become a kind of international standard. However, for reasons of upward compatibility GAP still offers the possibility to switch back to the old convention by just changing the value of the global variable CosetTableStandard from its default value "lenlex" to "semilenlex". Then all implicit standardizations of coset tables will follow the old convention. Setting the value of CosetTableStandard back to "lenlex" again means switching back to the new convention.

specifies the definiton of a standard coset table. It is used whenever coset tables or augmented coset tables are created. Its value may be "lenlex" or "semilenlex". If it is "lenlex" coset tables will be standardized using all their columns as defined in Charles Sims' book (this is the new default standard of GAP). If it is "semilenlex" they will be standardized using only their generator columns (this was the original GAP standard). The default value of CosetTableStandard is "lenlex".

Independent of the current value of CosetTableStandard there is the possibility to standardize (or restandardize) a coset table at any time using the following function.

standardizes the given coset table table. The second argument is optional. It defines the standard to be used, its values may be "lenlex" or "semilenlex" specifying the new or the old convention, respectively. If no value for the parameter standard is provided the function will use the global variable CosetTableStandard instead. Note that the function alters the given table, it does not create a copy.

gap> StandardizeTable( tab, "semilenlex" );
gap> PrintArray( TransposedMat( tab ) );
[ [  1,  1,  2,  4 ],
  [  3,  3,  4,  1 ],
  [  2,  2,  3,  3 ],
  [  5,  5,  1,  2 ],
  [  4,  4,  5,  5 ] ]

45.7 Coset tables for subgroups in the whole group

is equivalent to CosetTable(G,H) where G is the (unique) finitely presented group such that H is a subgroup of G. It overrides a silent option (see CosetTableFromGensAndRels) with false.

The variant TryCosetTableInWholeGroup does not override the silent option with false in case a coset table is only wanted if not too expensive. It will store a result that is not fail in the attribute CosetTableInWholeGroup.

takes a family of an fp group and a coset table tab and returns the subgroup of fam!.wholeGroup defined by this coset table.

See also CosetTableBySubgroup (CosetTableBySubgroup).

45.8 Augmented Coset Tables and Rewriting

For a subgroup H of a finitely presented group, this function returns an augmented coset table. If a generator set gens is given, it is guaranteed that gens will be a subset of the primary and secondary subgroup generators of this coset table.

It is mutable so we are permitted to add further entries. However existing entries may not be changed. Any entries added however should correspond to the subgroup only and not to an homomorphism.

is an internal function used by the subgroup presentation functions described in Subgroup Presentations. It applies a Modified Todd-Coxeter coset representative enumeration to construct an augmented coset table (see Subgroup presentations) for the given subgroup H of G. The subgroup generators will be named string1, string2, ... .

The function accepts the options max and silent as described for the function CosetTableFromGensAndRels (see CosetTableFromGensAndRels).

is an internal function used by the subgroup presentation functions described in Subgroup Presentations. It applies the Reduced Reidemeister-Schreier method to construct an augmented coset table for the subgroup of G which is defined by the given coset table table. The new subgroup generators will be named string1, string2, ... .

RewriteWord rewrites word (which must be a word in the underlying free group with respect to which the augmented coset table aug is given) in the subgroup generators given by the augmented coset table aug. It returns a Tietze-type word (i.e. a list of integers), referring to the primary and secondary generators of aug.

If word is not contained in the subgroup, fail is returned.

45.9 Low Index Subgroups

These functions compute representatives of the conjugacy classes of subgroups of the finitely presented group G that contain the subgroup H of G and that have index less than or equal to index.

LowIndexSubgroupsFpGroupIterator returns an iterator (see Iterators) that can be used to run over these subgroups, and LowIndexSubgroupsFpGroup returns the list of these subgroups. If one is interested only in one or a few subgroups up to a given index then preferably the iterator should be used.

If the optional argument excluded has been specified, then it is expected to be a list of words in the free generators of the underlying free group of G, and LowIndexSubgroupsFpGroup returns only those subgroups of index at most index that contain H, but do not contain any conjugate of any of the group elements defined by these words.

If not given, H defaults to the trivial subgroup.

The algorithm used finds the requested subgroups by systematically running through a tree of all potential coset tables of G of length at most index (where it skips all branches of that tree for which it knows in advance that they cannot provide new classes of such subgroups). The time required to do this depends, of course, on the presentation of G, but in general it will grow exponentially with the value of index. So you should be careful with the choice of index.

gap> li:=LowIndexSubgroupsFpGroup( g, TrivialSubgroup( g ), 10 );
[ Group(<fp, no generators known>), Group(<fp, no generators known>), 
  Group(<fp, no generators known>), Group(<fp, no generators known>) ]

By default, the algorithm computes no generating sets for the subgroups. This can be enforcd with GeneratorsOfGroup:

gap> GeneratorsOfGroup(li[2]);
[ a, b*a*b^-1 ]

If we are interested just in one (proper) subgroup of index at most 10, we can use the function that returns an iterator. The first subgroup found is the group itself, except if a list of excluded elements is entered (see below), so we look at the second subgroup.

gap> iter:= LowIndexSubgroupsFpGroupIterator( g, 10 );;
gap> s1:= NextIterator( iter );;  Index( g, s1 );
1
gap> IsDoneIterator( iter );
false
gap> s2:= NextIterator( iter );;  s2 = li[2];
true

As an example for an application of the optional parameter excluded, we compute all conjugacy classes of torsion free subgroups of index at most 24 in the group G = 〈x,y,z | x², y⁴, z³, (xy)³, (yz)², (xz)³ 〉. It is know from theory that each torsion element of this group is conjugate to a power of x, y, z, xy, xz, or yz. (Note that this includes conjugates of y².)

gap> F := FreeGroup( "x", "y", "z" );;
gap> x := F.1;; y := F.2;; z := F.3;;
gap> G := F / [ x^2, y^4, z^3, (x*y)^3, (y*z)^2, (x*z)^3 ];;
gap> torsion := [ x, y, y^2, z, x*y, x*z, y*z ];;
gap> SetInfoLevel( InfoFpGroup, 2 );
gap> lis := LowIndexSubgroupsFpGroup( G, TrivialSubgroup( G ), 24, torsion );;
#I  LowIndexSubgroupsFpGroup called
#I   class 1 of index 24 and length 8
#I   class 2 of index 24 and length 24
#I   class 3 of index 24 and length 24
#I   class 4 of index 24 and length 24
#I   class 5 of index 24 and length 24
#I  LowIndexSubgroupsFpGroup done. Found 5 classes
gap> SetInfoLevel( InfoFpGroup, 0 );

If a particular image group is desired, the operation GQuotients (see Quotient Methods) can be useful as well.

45.10 Converting Groups to Finitely Presented Groups

returns an isomorphism from the given finite group G to a finitely presented group isomorphic to G. The function first chooses a set of generators of G and then computes a presentation in terms of these generators.

gap> g := Group( (2,3,4,5), (1,2,5) );;
gap> iso := IsomorphismFpGroup( g );
[ (2,5,4,3), (1,2,3,4,5), (1,3,2,4,5) ] -> [ F1, F2, F3 ]
gap> fp := Image( iso );
<fp group of size 120 on the generators [ F1, F2, F3 ]>
gap> RelatorsOfFpGroup( fp );
[ F1^2*F2^2*F3*F2^-1, F2^-1*F1^-1*F2*F1*F2^-2*F3, F3^-1*F1^-1*F3*F1*F3^-1, 
  F2^5*F3^-5, F2^5*F3^-1*F2^-1*F3^-1*F2^-1, F2^-2*F3^2*F2^-2*F3^2 ]

returns an isomorphism from a finite group G to a finitely presented group F isomorphic to G. The generators of F correspond to the generators of G given in the list gens. If string is given it is used to name the generators of the finitely presented group.

The NC version will avoid testing whether the elements in gens generate G.

gap> SetInfoLevel( InfoFpGroup, 1 );
gap> iso := IsomorphismFpGroupByGenerators( g, [ (1,2), (1,2,3,4,5) ] );
#I  the image group has 2 gens and 5 rels of total length 39
[ (1,2), (1,2,3,4,5) ] -> [ F1, F2 ]
gap> fp := Image( iso );
<fp group of size 120 on the generators [ F1, F2 ]>
gap> RelatorsOfFpGroup( fp );
[ F1^2, F2^5, F2^-1*F1*F2^-1*F1*F2^-1*F1*F2^-1*F1, 
  F2^-1*F1*F2*F1*F2^-1*F1*F2*F1*F2^-1*F1*F2*F1, 
  F2^2*F1*F2^-2*F1*F2^2*F1*F2^-2*F1 ]

The main task of the function IsomorphismFpGroupByGenerators is to find a presentation of G in the provided generators gens. In the case of a permutation group G it does this by first constructing a stabilizer chain of G and then it works through that chain from the bottom to the top, recursively computing a presentation for each of the involved stabilizers. The method used is essentially an implementation of John Cannon's multi-stage relations-finding algorithm as described in Neu82 (see also Can73 for a more graph theoretical description). Moreover, it makes heavy use of Tietze transformations in each stage to avoid an explosion of the total length of the relators.

Note that because of the random methods involved in the construction of the stabilizer chain the resulting presentations of G will in general be different for repeated calls with the same arguments.

gap> M12 := MathieuGroup( 12 );
Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6), 
  (1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ])
gap> gens := GeneratorsOfGroup( M12 );;
gap> iso := IsomorphismFpGroupByGenerators( M12, gens );;
#I  the image group has 3 gens and 21 rels of total length 541
gap> iso := IsomorphismFpGroupByGenerators( M12, gens );;
#I  the image group has 3 gens and 26 rels of total length 766

Also in the case of a permutation group G, the function IsomorphismFpGroupByGenerators supports the option method that can be used to modify the strategy. The option method may take the following values.

method := "regular"

This may be specified for groups of small size, up to 10⁵ say. It implies that the function first constructs a regular representation R of G and then a presentation of R. In general, this presentation will be much more concise than the default one, but the price is the time needed for the construction of R.

method := [ "regular", bound ]

This is a refinement of the previous possibility. In this case, bound should be an integer, and if so the method "regular" as described above is applied to the largest stabilizer in the stabilizer chain of G whose size does not exceed the given bound and then the multi-stage algorithm is used to work through the chain from that subgroup to the top.

method := "fast"

This chooses an alternative method which essentially is a kind of multi-stage algorithm for a stabilizer chain of G but does not make any attempt do reduce the number of relators as it is done in Cannon's algorithm or to reduce their total length. Hence it is often much faster than the default method, but the total length of the resulting presentation may be huge.

method := "default"

This simply means that the default method shall be used, which is the case if the option method is not given a value.

gap> iso := IsomorphismFpGroupByGenerators( M12, gens : method := "regular" );;
#I  the image group has 3 gens and 11 rels of total length 92
gap> iso := IsomorphismFpGroupByGenerators( M12, gens : method := "fast" );;
#I  the image group has 3 gens and 181 rels of total length 4169

Though the option method := "regular" is only checked in the case of a permutation group it also affects the performance and the results of the function IsomorphismFpGroupByGenerators for other groups, e. g. for matrix groups. This happens because, for these groups, the function first calls the function NiceMonomorphism to get a bijective action homomorphism from G to a suitable permutation group, P say, and then, recursively, calls itself for the group P so that now the option becomes relevant.

gap> G := ImfMatrixGroup( 5, 1, 3 );
ImfMatrixGroup(5,1,3)
gap> gens := GeneratorsOfGroup( G );
[ [ [ -1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 0, 1, 0 ], 
      [ -1, -1, -1, -1, 2 ], [ -1, 0, 0, 0, 1 ] ], 
  [ [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], 
      [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ] ] ]
gap> iso := IsomorphismFpGroupByGenerators( G, gens );;
#I  the image group has 2 gens and 7 rels of total length 68
gap> iso := IsomorphismFpGroupByGenerators( G, gens : method := "regular" );;
#I  the image group has 2 gens and 6 rels of total length 56
gap> SetInfoLevel( InfoFpGroup, 0 );
gap> iso;
<composed isomorphism:[ [ [ -1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 0, 1,\
 0 ], [ -1, -1, -1, -1, 2 ], [ -1, 0, 0, 0, 1 ] ], [ [ 0, 1, 0, 0, 0 ], [ 0, 0\
, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ] ] ]->[ F1\
, F2 ]>
gap> ConstituentsCompositionMapping(iso);
[ <action isomorphism>, 
  [ (1,55,43,29,19,71)(2,72,18,30,44,54)(3,32,20,31,4,56)(5,75,46,33,47,74)(6,
        35,48,34,7,76)(8,36)(9,63,51,37,27,79)(10,80,26,38,52,62)(11,40,28,39,
        12,64)(13,59,58)(14,15,60)(17,70,41,53,42,69)(21,67,66)(22,23,68)(25,
        78,49,61,50,77)(45,73), (1,13,5,2)(3,29,21,7)(4,14,33,10)(6,30,9,
        15)(8,31,37,23)(11,32,22,35)(12,16,34,38)(18,53,25,19)(20,54,61,
        27)(24,36,39,40)(26,55)(28,56,62,63)(41,57,45,42)(43,69,65,47)(44,58,
        73,50)(46,70,49,59)(48,71,77,67)(51,72,66,75)(52,60,74,78)(68,76,79,
        80) ] -> [ F1, F2 ] ]

Since GAP cannot decompose elements of a matrix group into generators, the resulting isomorphism is stored as a composition of a (faithful) permutation action on vectors and a homomorphism from the permutation image to the finitely presented group. In such a situation the constituent mappings can be obtained via ConstituentsCompositionMapping as separate GAP objects.

45.11 New Presentations and Presentations for Subgroups

IsomorphismFpGroup is also used to compute a new finitely presented group that is isomorphic to the subgroup of a given finitely presented group. (This is typically the only method to compute with subgroups of a finitely presented group.)

gap> f:=FreeGroup(2);;
gap> g:=f/[f.1^2,f.2^3,(f.1*f.2)^5];
<fp group on the generators [ f1, f2 ]>
gap> u:=Subgroup(g,[g.1*g.2]);
Group([ f1*f2 ])
gap> hom:=IsomorphismFpGroup(u);
[ <[ [ 1, 1 ] ]|f2^-1*f1^-1> ] -> [ F1 ]
gap> new:=Range(hom);
<fp group on the generators [ F1 ]>
gap> List(GeneratorsOfGroup(new),i->PreImagesRepresentative(hom,i));
[ <[ [ 1, 1 ] ]|f2^-1*f1^-1> ]

When working with such homomorphisms, some subgroup elements are expressed as extremely long words in the group generators. Therefore the underlying words of subgroup generators stored in the isomorphism (as obtained by MappingGeneratorImages and displayed when Viewing the homomorphism) as well as preimages under the homomorphism are stored in the form of straight line program elements (see Straight Line Program Elements). These will behave like ordinary words and no extra treatment should be necessary.

gap> r:=Range(hom).1^10;
F1^10
gap> p:=PreImagesRepresentative(hom,r);
<[ [ 1, 10 ] ]|f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^
-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1>

gap> r:=EvalStraightLineProgElm(UnderlyingElement(p));
f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^
-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1
gap> p:=ElementOfFpGroup(FamilyObj(p),r);
f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^
-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1

(If you are only interested in a finitely presented group isomorphic to U, but not in the isomorphism, you may also use the functions PresentationViaCosetTable and FpGroupPresentation (see Creating Presentations).)

Homomorphisms can also be used to obtain an isomorphic finitely presented group with a (hopefully) simpler presentation.

applies Tietze transformations to a copy of the presentation of the given finitely presented group G in order to reduce it with respect to the number of generators, the number of relators, and the relator lengths.

The operation returns an isomorphism with source G, range a group H isomorphic to G, so that the presentation of H has been simplified using Tietze transformations.

gap> f:=FreeGroup(3);;
gap> g:=f/[f.1^2,f.2^3,(f.1*f.2)^5,f.1/f.3];
<fp group on the generators [ f1, f2, f3 ]>
gap> hom:=IsomorphismSimplifiedFpGroup(g);
[ f1, f2, f3 ] -> [ f1, f2, f1 ]
gap> Range(hom);
<fp group on the generators [ f1, f2 ]>
gap> RelatorsOfFpGroup(Range(hom));
[ f1^2, f2^3, f1*f2*f1*f2*f1*f2*f1*f2*f1*f2 ]
gap> RelatorsOfFpGroup(g);
[ f1^2, f2^3, f1*f2*f1*f2*f1*f2*f1*f2*f1*f2, f1*f3^-1 ]

(IsomorphismSimplifiedFpGroup uses Tietze transformations to simplify the presentation, see SimplifiedFpGroup.)

45.12 Preimages under Homomorphisms from an FpGroup

For some subgroups of a finitely presented group the number of subgroup generators increases with the index of the subgroup. However often these generators are not needed at all for further calculations, but what is needed is the action of the cosets of the subgroup. This gives the image of the subgroup in a finite quotient and this finite quotient can be used to calculate normalizers, closures, intersections and so forth HulpkeQuot.

The same applies for subgroups that are obtained as preimages under homomorphisms.

takes a fp group family fpfam, a finitely generated group Q such that the fp generators of fam can be mapped by an epimorphism phi onto GeneratorsOfGroup(Q) and a subgroup U of Q. It returns the subgroup of fam!.wholeGroup which is the full preimage of U under phi.

is the representation for subgroups of an fp group, given by a quotient subgroup. The components G!.quot and G!.sub hold quotient, respectively subgroup.

returns the same subgroup in the representation AsSubgroupOfWholeGroupByQuotient.

See also SubgroupOfWholeGroupByCosetTable (SubgroupOfWholeGroupByCosetTable) and CosetTableBySubgroup (CosetTableBySubgroup).

This technique is used by GAP for example to represent the derived subgroup, which is obtained from the quotient G/G′.

gap> f:=FreeGroup(2);;g:=f/[f.1^6,f.2^6,(f.1*f.2)^6];;
gap> d:=DerivedSubgroup(g);
Group(<fp, no generators known>)
gap> Index(g,d);
36

if U is a subgroup in quotient representation (IsSubgroupOfWholeGroupByQuotientRep), this function returns the defining homomorphism from the whole group to U!.quot.

45.13 Quotient Methods

An important class of algorithms for finitely presented groups are the quotient algorithms which compute quotient groups of a given finitely presented group.

 MaximalAbelianQuotient(fpgroup)

as defined for general groups, this attribute returns the largest abelian quotient of fpgroup.

gap> f:=FreeGroup(2);;fp:=f/[f.1^6,f.2^6,(f.1*f.2)^12];
<fp group on the generators [ f1, f2 ]>
gap> hom:=MaximalAbelianQuotient(fp);
[ f1, f2 ] -> [ f1, f3 ]
gap> Size(Image(hom));
36

computes a factor p-group of a finitely presented group F in form of a quotient system. The quotient system can be converted into an epimorphism from F onto the p-group computed by the function EpimorphismQuotientSystem.

For a group G define the exponent-p central series of G inductively by P₁(G) = G and P_i+1(G) = [P_i(G),G]P_i+1(G)^p· The factor groups modulo the terms of the lower exponent-p central series are p-groups. The group G has p-class c if P_c(G) ≠ P_c+1(G)=1·

The algorithm computes successive quotients modulo the terms of the exponent-p central series of F. If the parameter c is present, then the factor group modulo the (c+1)-th term of the exponent-p central series of F is returned. If c is not present, then the algorithm attempts to compute the largest factor p-group of F. In case F does not have a largest factor p-group, the algorithm will not terminate.

By default the algorithm computes only with factor groups of order at most p²⁵⁶· If the parameter logord is present, it will compute with factor groups of order atmost p^logord · If this parameter is specified, then the parameter c must also be given. The present implementation produces an error message if the order of a p-quotient exceeds p²⁵⁶ or p^logord , respectively. Note that the order of intermediate p-groups may be larger than the final order of a p-quotient.

The parameter ctype determines the type of collector that is used for computations within the factor p-group. ctype must either be single in which case a simple collector from the left is used or combinatorial in which case a combinatorial collector from the left is used.

For a quotient system quotsys obtained from the function PQuotient, this operation returns an epimorphism F →P where F is the finitely presented group of which quotsys is a quotient system and P is a PcGroup isomorphic to the quotient of F determined by quotsys.

Different calls to this operation will create different groups P, each with its own family.

gap> PQuotient( FreeGroup(2), 5, 10, 1024, "combinatorial" );
<5-quotient system of 5-class 10 with 520 generators>
gap> phi := EpimorphismQuotientSystem( last );
[ f1, f2 ] -> [ a1, a2 ]
gap> Collected( Factors( Size( Image( phi ) ) ) );
[ [ 5, 520 ] ]

computes an epimorphism from the finitely presented group fpgrp to the largest p-group of p-class cl which is a quotient of fpgrp. If cl is omitted, the largest finite p-group quotient (of p-class up to 1000) is determined.

gap> hom:=EpimorphismPGroup(fp,2);
[ f1, f2 ] -> [ a1, a2 ]
gap> Size(Image(hom));
8
gap> hom:=EpimorphismPGroup(fp,3,7);
[ f1, f2 ] -> [ a1, a2 ]
gap> Size(Image(hom));
6561

returns an epimorphism on the class n finite nilpotent quotient of the finitely presented group fpgrp. If n is omitted, the largest finite nilpotent quotient (of p-class up to 1000) is taken.

gap> hom:=EpimorphismNilpotentQuotient(fp,7);
[ f1, f2 ] -> [ f1*f4, f2*f5 ]
gap> Size(Image(hom));
52488

A related operation which is also applicable to finitely presented groups is GQuotients, which computes all epimorphisms from a (finitely presented) group F onto a given (finite) group G, see GQuotients.

gap> GQuotients(fp,Group((1,2,3),(1,2)));
[ [ f1, f2 ] -> [ (2,3), (1,2) ], [ f1, f2 ] -> [ (2,3), (1,2,3) ], 
  [ f1, f2 ] -> [ (1,2,3), (1,2) ] ]

45.14 Abelian Invariants for Subgroups

Using variations of coset enumeration it is possible to compute the abelian invariants of a subgroup of a finitely presented group without computing a complete presentation for the subgroup in the first place. Typically, the operation AbelianInvariants when called for subgroups should automatically take care of this, but in case you what to have further control about the methods used, the following operations might be of use.

is a synonym for AbelianInvariantsSubgroupFpGroupRrs(G,H).

uses the Modified Todd-Coxeter method to compute the abelian invariants of a subgroup H of a finitely presented group G.

uses the Reduced Reidemeister-Schreier method to compute the abelian invariants of a subgroup H of a finitely presented group G.

Alternatively to the subgroup H, its coset table table in G may be given as second argument.

is a synonym for AbelianInvariantsNormalClosureFpGroupRrs(G,H).

uses the Reduced Reidemeister-Schreier method to compute the abelian invariants of the normal closure of a subgroup H of a finitely presented group G.

See Subgroup Presentations for details on the different strategies.

The following example shows a calculation for the Coxeter group B₁. This calculation and a similar one for B₀ have been used to prove that B₁′/ B₁^′′ ≅ Z₂⁹ ×Z³ and B₀′/ B₀^′′ ≅ Z₂⁹¹ ×Z²⁷ as stated in Proposition 5 in FJNT95.

gap> # Define the Coxeter group E1.
gap> F := FreeGroup( "x1", "x2", "x3", "x4", "x5" );
<free group on the generators [ x1, x2, x3, x4, x5 ]>
gap> x1 := F.1;; x2 := F.2;; x3 := F.3;; x4 := F.4;; x5 := F.5;;
gap> rels := [ x1^2, x2^2, x3^2, x4^2, x5^2,
>  ( x1 * x3 )^2, ( x2 * x4 )^2, ( x1 * x2 )^3, ( x2 * x3 )^3, ( x3 * x4 )^3,
>  ( x4 * x1 )^3, ( x1 * x5 )^3, ( x2 * x5 )^2, ( x3 * x5 )^3, ( x4 * x5 )^2,
>  ( x1 * x2 * x3 * x4 * x3 * x2 )^2 ];;
gap> E1 := F / rels;
<fp group on the generators [ x1, x2, x3, x4, x5 ]>
gap> x1 := E1.1;; x2 := E1.2;; x3 := E1.3;; x4 := E1.4;; x5 := E1.5;;
gap> # Get normal subgroup generators for B1.
gap> H := Subgroup( E1, [ x5 * x2^-1, x5 * x4^-1 ] );;
gap> # Compute the abelian invariants of B1/B1'.
gap> A := AbelianInvariantsNormalClosureFpGroup( E1, H );
[ 2, 2, 2, 2, 2, 2, 2, 2 ]
gap> # Compute a presentation for B1.
gap> P := PresentationNormalClosure( E1, H );
<presentation with 18 gens and 46 rels of total length 132>
gap> SimplifyPresentation( P );
#I  there are 8 generators and 30 relators of total length 148
gap> B1 := FpGroupPresentation( P );
<fp group on the generators [ _x1, _x2, _x3, _x4, _x6, _x7, _x8, _x11 ]>
gap> # Compute normal subgroup generators for B1'.
gap> gens := GeneratorsOfGroup( B1 );;
gap> numgens := Length( gens );;
gap> comms := [ ];;
gap> for i in [ 1 .. numgens - 1 ] do
>     for j in [i+1 .. numgens ] do
>         Add( comms, Comm( gens[i], gens[j] ) );
>     od;
> od;
gap> # Compute the abelian invariants of B1'/B1".
gap> K := Subgroup( B1, comms );;
gap> A := AbelianInvariantsNormalClosureFpGroup( B1, K );
[ 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]

45.15 Testing Finiteness of Finitely Presented Groups

As a consequence of the algorithmic insolvabilities mentioned in the introduction to this chapter, there cannot be a general method that will test whether a given finitely presented group is actually finite.

Therefore testing a finitely presented group for IsFinite can be problematic. What GAP actually does upon a call of IsFinite (or if it is -- probably implicitly -- asked for a faithful permutation representation) is to test whether it can find (via coset enumeration) a cyclic subgroup of finite index. If it can, it rewrites the presentation to this subgroup. Since the subgroup is cyclic, its size can be checked easily from the resulting presentation, the size of the whole group is the product of the index and the subgroup size. Since however no bound for the index of such a subgroup (if any exist) is known, such a test might continue unsuccesfully until memory is exhausted.

On the other hand, a couple of methods exist, that might prove that a group is infinite. Again, none is guaranteed to work in every case:

The first method is to find (for example via the low index algorithm, see LowIndexSubgroupsFpGroup) a subgroup U such that [U:U′] is infinite. If U has finite index, this can be checked by the operation AbelianInvariants (see section Abelian Invariants for Subgroups for an example).

Another method is based on p-group quotients:

Let G be a finitely presented group and p a prime that divides the order of G /G ′. This function applies an infinity criterion due to M.F. Newman New90 to G. (See chapter 16 of Joh97 for a more explicit description.) It returns true if the criterion succeeds in proving that G is infinite and fail otherwise.

Note that the criterion uses the number of generators and relations in the presentation of G. Reduction of the persentation via Tietze transformations (IsomorphismSimplifiedFpGroup) therefore might produce an isomorphic group, for which the criterion will work better.

gap> g:=FibonacciGroup(2,9);
<fp group on the generators [ f1, f2, f3, f4, f5, f6, f7, f8, f9 ]>
gap> hom:=EpimorphismNilpotentQuotient(g,2);;
gap> k:=Kernel(hom);;
gap> Index(g,k);
152
gap> AbelianInvariants(k);
[ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ]
gap> NewmanInfinityCriterion(Kernel(hom),5);
true

This proves that the subgroup k (and thus the whole group g) is infinite. (This is the original example from New90.)

[Top] [Up] [Previous] [Next] [Index]

GAP 4 manual
March 2006