A finitely presented group (in short: FpGroup) is a group generated by a finite set of abstract generators subject to a finite set of relations that these generators satisfy. Every finite group can be represented as a finitely presented group.
Finitely presented groups are obtained by factoring a free group by a set of relators. Their elements know about this presentation and compare accordingly.
So to create a finitely presented group you first have to generate a free group (see FreeGroup for details). Then a list of relators is constructed as words in the generators of the free group and is factored out to obtain the finitely presented group. Its generators are the images of the free generators. So for example to create the group
< a,b | a^2 b^3 (a*b)^5 >you can use the following commands:
gap> f := FreeGroup( "a", "b" );; gap> g := f / [ f.1^2, f.2^3, (f.1*f.2)^5 ]; <fp group on the generators [ a, b ]>
Note that you cannot call the generators by their names. These names are not variables, but just display figures. So, if you want to access the generators by their names, you first have to introduce the respective variables and to assign the generators to them.
gap> GeneratorsOfGroup( g ); [ a, b ] gap> a; Variable: 'a' must have a value gap> a := g.1;; b := g.2;; # assign variables gap> GeneratorsOfGroup( g ); [ a, b ] gap> a in f; false gap> a in g; true
Note that the generators of the free group are different from the generators of the FpGroup (even though they are displayed by the same names). That means that words in the generators of the free group are not elements of the finitely presented group. Vice versa elements of the FpGroup are not words.
gap> a*b = b*a; false gap> (b^2*a*b)^2 = a^0; true
Such calculations comparing elements of an FpGroup may run into problems: There exist finitely presented groups for which no algorithm exists (it is known that no such algorithm can exist) that will tell for two arbitrary words in the generators whether the corresponding elements in the FpGroup are equal. Therefore the methods used by GAP to compute in finitely presented groups may run into warning errors, run out of memory or run forever. If the FpGroup is (by theory) known to be finite the algorithms are guaranteed to terminate (if there is sufficient memory available), but the time needed for the calculation cannot be bounded a priori. See Coset Tables and Coset Enumeration.
gap> (b^2*a*b)^2; b^2*a*b^3*a*b gap> a^0; <identity ...>
A consequence of our convention is that elements of finitely presented groups are not printed in a unique way.
IsSubgroupFpGroup(
H ) C
returns true
if H is a finitely presented group or a subgroup of a
finitely presented group.
IsFpGroup(
G ) F
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.
InfoFpGroup V
The info class for functions dealing with finitely presented groups is
InfoFpGroup
.
F/
rels
creates a finitely presented group given by the presentation
ágens \midrels ñ 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 ab = 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 ]>
FactorGroupFpGroupByRels(
G,
elts ) F
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.
a =
b
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.
a <
b
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.
FpElmComparisonMethod(
fam ) A
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.
FreeGroupOfFpGroup(
G ) A
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(
G ) A
FreeGeneratorsOfWholeGroup(
U ) O
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.
RelatorsOfFpGroup(
G ) A
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.
UnderlyingElement(
elm )
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
ElementOfFpGroup(
fam,
word ) O
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
44.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.
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) ]
44.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.
CosetTable(
G,
H ) O
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 standardized, i.e., the cosets are sorted with respect to the
smallest word that lies in each coset.
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 CosetTableFpGroupDefaultLimit
and
CosetTableFpGroupDefaultMaxLimit
described below and that the options
described under CosetTableFromGensAndRels
are recognized.
gap> CosetTable( g, Subgroup( g, [ g.1, g.2*g.1*g.2*g.1*g.2^-1 ] ) ); [ [ 1, 3, 2, 5, 4 ], [ 1, 3, 2, 5, 4 ], [ 2, 4, 3, 1, 5 ], [ 4, 1, 3, 2, 5 ] ] gap> List( last, PermList ); [ (2,3)(4,5), (2,3)(4,5), (1,2,4), (1,4,2) ]
CosetTableInWholeGroup(
H ) A
TryCosetTableInWholeGroup(
H ) O
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
.
FactorCosetAction(
G,
H )
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,3)(5,6), (1,2,4)(3,5,6) ]
CosetTableBySubgroup(
G,
H ) O
returns a coset table for the action of G on the cosets of H. The
columns of the table correspond to the GeneratorsOfGroup(
G)
.
CosetTableFromGensAndRels(
fgens,
grels,
fsgens ) F
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
CosetTableFromGensAndRels
processes two options (see
chapter Options Stack):
max
CosetTableDefaultMaxLimit
. (Due to the algorithm the actual
limit used can be a bit higher than the number given.)
silent
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.
CosetTableDefaultMaxLimit V
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: 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,
At this point you can either continue the calculation with a larger number of permitted cosets or stop the calculation if you don't expect the enumeration to finish (like in the example above).
Setting CosetTableDefaultMaxLimit
(or the max
option value) to
infinity
(or to 0) will enforce all coset enumerations to continue until
they either get a result or exhaust the whole available space.
CosetTableDefaultLimit V
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.
AugmentedCosetTableMtc(
G,
H,
type,
string ) F
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).
AugmentedCosetTableRrs(
G,
table,
type,
string ) F
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, ... .
MostFrequentGeneratorFpGroup(
G ) F
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.
IndicesInvolutaryGenerators(
G ) A
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.
LowIndexSubgroupsFpGroup(
G,
H,
index[,
excluded] ) O
returns a list of 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.
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.
The function LowIndexSubgroupsFpGroup
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> LowIndexSubgroupsFpGroup( g, TrivialSubgroup( g ), 10 ); [ Group([ a, b ]), Group([ a, b*a*b^-1 ]), Group([ a, b*a*b*a^-1*b^-1 ]), Group([ a, b*a*b*a*b^-1*a^-1*b^-1 ]) ]
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 \mid x2, y4, z3, (xy)3, (yz)2, (xz)3 ñ. 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.
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 returns 5 classes gap> SetInfoLevel( InfoFpGroup, 0 ); gap> lis; [ Group([ x*y*z^-1, z*x*z^-1*y^-1, x*z*x*y^-1*z^-1, y*x*z*y^-1*z^-1 ]), Group([ x*y*z^-1, z^2*x^-1*y^-1, x*z*y*x^-1*z^-1 ]), Group([ x*y*z^-1, x*z^2*x^-1*y^-1, y^2*x*y^-1*z^-1*x^-1 ]), Group([ x*y*z^-1, y^3*x^-1*z^-1*x^-1, y^2*z*x^-1*y^-1 ]), Group([ y*x*z^-1, x*y*z*y^-1*z^-1, y^2*z*x^-1*z^-1*x^-1 ]) ]
44.7 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.
AbelianInvariantsSubgroupFpGroup(
G,
H ) F
is a synonym for AbelianInvariantsSubgroupFpGroupRrs(
G,
H)
.
AbelianInvariantsSubgroupFpGroupMtc(
G,
H ) F
uses the Modified Todd-Coxeter method to compute the abelian invariants of a subgroup H of a finitely presented group G.
AbelianInvariantsSubgroupFpGroupRrs(
G,
H ) F
AbelianInvariantsSubgroupFpGroupRrs(
G,
table ) F
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.
AbelianInvariantsNormalClosureFpGroup(
G,
H ) F
is a synonym for AbelianInvariantsNormalClosureFpGroupRrs(
G,
H)
.
AbelianInvariantsNormalClosureFpGroupRrs(
G,
H ) F
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.
IsomorphismFpGroup(
G ) A
returns an isomorphism from the given finite group G to a finitely presented group isomorphic to G. The presentation (and thus the generators in which it is presented) is chosen by a method to obtain a short presentation.
gap> g := Group( (1,2,3,4), (1,2) );; gap> iso := IsomorphismFpGroup( g ); [ (3,4), (2,4,3), (1,4)(2,3), (1,3)(2,4) ] -> [ F1, F2, F3, F4 ] gap> fp := Image( iso ); <fp group on the generators [ F1, F2, F3, F4 ]> gap> RelatorsOfFpGroup( fp ); [ F1^2, F2^-1*F1^-1*F2*F1*F2^-1, F3^-1*F1^-1*F3*F1*F4^-1*F3^-1, F4^-1*F1^-1*F4*F1*F4^-1*F3^-1, F2^3, F3^-1*F2^-1*F3*F2*F4^-1*F3^-1, F4^-1*F2^-1*F4*F2*F3^-1, F3^2, F4^-1*F3^-1*F4*F3, F4^2 ]
IsomorphismFpGroupByGenerators(
G,
gens[,
string] ) A
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.
gap> iso := IsomorphismFpGroupByGenerators( g, [ (1,2,3,4), (1,2) ] ); [ (1,2,3,4), (1,2) ] -> [ F1, F2 ] gap> fp := Image( iso ); <fp group on the generators [ F1, F2 ]> gap> RelatorsOfFpGroup( fp ); [ F1*F2*F1*F2*F1*F2, F2^2, F1^-1*F2*F1^2*F2*F1*F2*F1^2*F2*F1^2, F2^-1*F1^4*F2, F1^-2*F2*F1^4*F2*F1^2, F1^2*F2*F1^4*F2*F1^2, F2^-1*F1*F2*F1^3*F2*F1*F2*F1^2*F2*F1^2, F2^-1*F1^-1*F2^-1*F1*F2*F1^3*F2*F1^ 2*F2*F1^2 ]
If you are only interested in a finitely presented group isomorphic to G,
but not in the isomorphism, you may also use the functions
PresentationViaCosetTable
and FpGroupPresentation
(see Creating Presentations).
44.9 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. The same applies for subgroups that are obtained as preimages under homomorphisms.
SubgroupOfWholeGroupByCosetTable(
fpfam,
tab ) F
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.
SubgroupOfWholeGroupByQuotientSubgroup(
fpfam,
Q,
U ) F
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.
IsSubgroupOfWholeGroupByQuotientRep(
G ) R
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.
AsSubgroupOfWholeGroupByQuotient(
U ) A
returns the same subgroup in the representation
AsSubgroupOfWholeGroupByQuotient
.
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
An important class of algorithms for finitely presented groups are the quotient algorithms which compute quotient groups of a given finitely presented group.
MaximalAbelianQuotient(
fpgrp ) O
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
EpimorphismPGroup(
fpgrp,
p ) O
EpimorphismPGroup(
fpgrp,
p,
cl ) O
computes an epimorphism from the finitely presented group fpgrp to the largest p-group of class cl which is a quotient of fpgrp. If cl is omitted, the largest finite p-group quotient 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
EpimorphismNilpotentQuotient(
fpgrp[,
n] ) F
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 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 ] -> [ (1,2,3), (2,3) ],[ f1, f2 ] -> [ (2,3), (1,2,3) ], [ f1, f2 ] -> [ (1,3), (2,3) ] ]
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual