GAP Instructional Material

Return to Index

GAP code is shown like this.

[Press ?? to see GAP output]

You can also choose to see a page showing ALL GAP output.

Finitely presented groups

This document assumes that the reader is familiar with finitely presented groups and the standard algorithms. We do not cover generic algorithms since they are dealt with elsewhere.

A problem

Given the presentation < x,y | x5 = 1, y2 = (xy)3, (x3yx4y)2 = 1 > one of the natural questions to ask is "What is the group defined by this presentation?" As it stands this question is not too meaningful. We may be able to find properties which allow us to identify it uniquely as being isomorphic to a "known" group. This would give a full answer to the question. However, failing such full information we may still be able to find out many properties of the group defined by the presentation and often these are enough for our purposes.

We first need to input the presentation into GAP. This is done in a 'natural' way as follows:

Creating finitely presented groups in GAP

Since a finitely presented group is the quotient of a free group by the normal closure of a set of relators we first need to create the free group on the two generators. GAP will give you a free group withthe command FreeGroup(2) which will then have generators f1 and f2, but in our case it is more convenient to have x and y as generators.

f:= FreeGroup("x","y");      ??

If we want to refer to words in these generators using x and y we need to label the generators and make input easier

x:= f.1; y:= f.2;      ??

Now we input the set of relators as a list

rels:= [ x^5, (x*y)^3*y^(-2), (x^3*y*x^4*y)^2 ];      ??

Finally form the group G that is the quotient of the free group by the
normal closure of the set of relators

G:= f/rels;      ??

Note that x and y are elements of the free group and not of its quotient and so we give more convenient names to the generators of the finitely presented group G .

a:= G.1; b:= G.2;      ??


Finding Properties

We now use well documented procedures to discover certain properties of the group G.

We first ask GAP to calculate the size of the group. GAP uses the Todd-Coxeter procedure.

size:= Size( G );      ??

So |G|=60. Let us look at defining some subgroups

H:= Subgroup(G, [ b, a*b*a^-1 ]);      ??

We can find its index in G

Index( G, H );      ??

We can find the order of elements of G

Order( b );      ??

At this point we can also find a permutation representation for G by looking at its coset table. In GAP a coset table is given as a list of lists. Each list represents the action of a generator or its inverse on the cosets. Hence to view it as a conventional coset table where the columns give the action of the generators and their inverses on the cosets, we look at the transpose of the coset table

Display(TransposedMat(CosetTable(G,TrivialSubgroup( G ))));      ??

We could also look at the coset table for the action of G on its subgroup H

Display(TransposedMat(CosetTable( G, H )));      ??

(For more information on coset table methods in GAP see section 45.5 of the GAP manual.)

The easiest way to produce the permutation representation of a finitely presented group is through its action on the cosets of the trivial subgroup

perm_rep:= Image( IsomorphismPermGroup( G ) );      ??

Let us now compute G/G', the factor by the derived group of G (sometimes called the abelianization of G)

AbelianInvariants( G );      ??

So our group G is a perfect group of order 60. Of course there is only one perfect group of order 60, namely A5, but assume for the moment that we don't know that. We see how many perfect groups there are of order 60 by looking in the group library in GAP

AllSmallGroups(Size, 60, IsPerfect, true);      ??

Since this returns a single group this is a way of describing the group G up to isomorphism (it is in fact A5).

Another way to see that G is isomorphic to A5 is to find an explicit isomorphism via

A_5:= AlternatingGroup( 5 );      ??
iso:= IsomorphismGroups( G, A_5 );      ??

Since the computer did not return fail the groups are indeed isomorphic.


Subgroups

We now obtain some information about the internal structure of the group G. We start by looking for all normal subgroups of G (since the group is so small this is easily computable)

norm_subG:= NormalSubgroups( G );      ??

Since there are only two normal subgroups of G this means that G has no proper normal subgroups and so is simple. We could have asked GAP directly whether G was simple

IsSimple( G );      ??

The subgroup H can't be simple. Let us find its normal subgroups

norm_subH:= NormalSubgroups( H );      ??

Now norm_subH[1] is H, while norm_subH[3] is trivial. What about norm_subH[2]?

norm_subH[2];      ??

Now H must be the dihedral group of order 10. Let us confirm this

D_5:= DihedralGroup( 10 );      ??
iso:= IsomorphismGroups( H, D_5 );      ??

Since GAP has constructed an explicit isomorphism then H is isomorphic to the dihedral group of order 10.

Maybe we would like to find all elements of a certain order, 3 say, in G. We will put them in a list

n:= 0;; order3:= [];;
for x in G do
 if Order(x) = 3 then n:= n+1; order3[n]:= x; fi;
od;

How many elements of order 3 does G have?

Size(order3);      ??

We could list all twenty

Print(order3, "\n");      ??

We found one subgroup of order 10, namely H. Suppose we want to find all subgroups of G of order 10. To do this we use the Low Index procedure, this produces all subgroups of index less than or equal to a given number that contains a given subgroup. So we need to run the Low Index procedure for index 6 and the trivial subgroup (which will give one representation of each conjugacy class of subgroups of index less than or equal to 6 containing the trivial subgroup) and then take away all subgroups for index 5 containing the trivial subgroup as follows

lis6:= LowIndexSubgroupsFpGroup( G, TrivialSubgroup( G), 6);      ??
lis5:= LowIndexSubgroupsFpGroup( G, TrivialSubgroup( G), 5);      ??
subgroups:=Difference(lis6, lis5);      ??

From this we see that there is only one conjugacy class of subgroups of order 10. To find how many there are we need to find the number of conjugates of this subgroup (or of H)

cc:= ConjugacyClassSubgroups( G, subgroups[1] );
Size(cc);      ??


Manipulating presentations

Now we use Tietze transformations to try and reduce the complexity of the finitely presented group G. First we need to create the presentation that defines G.

presn:= PresentationFpGroup( G );      ??

Now we may use GAP's Tietze transformation routines to try to reduce the number of relators or the size of the relators. To do this we use the TzGoGo command

TzGoGo(presn);      ??

So our presentation is now reduced. Notice that presn has become the simplified presentation. We would like to see the relations

TzPrintRelators(presn);      ??

We could also investigate the effects of changing some of the internal variables in the TzGoGo program to try and find a minimal presentation. See Tietze Transformations in the manual for more information.

Now let g be the group defined by the presentation presn.

g:= FpGroupPresentation(presn);      ??

Then this group is isomorphic to our original group G

IsomorphismGroups( G, g);      ??

but because GAP has represented the two groups differently, the are not "the same".

G=g;      ??

Epimorphisms and quotient algorithms

We now introduce a new finitely presented group to investigate the applications of a very important family of algorithms, namely quotient algorithms for finitely presented groups.


f:= FreeGroup("x","y");; x:= f.1;; y:= f.2;;
rels:= [ x^6, y^6, (x*y)^6 ];;
H:= f/rels;      ??

We now find an epimorphism from H to its 3-group of class 8

epi:= EpimorphismPGroup( H, 3, 8 );      ??
sp:= Size(Image(epi));      ??

We can also find an epimorphism to the nilpotent quotient of H of class 8

nil:= EpimorphismNilpotentQuotient( H, 8 );      ??
sn:= Size(Image(nil));      ??

What other primes are there in the nilpotent quotient?

sn/sp;      ??

Finally we find ALL epimorphisms from H onto the symmetric group S3 up to automorphisms of H.

GQuotients( H, SymmetricGroup(3) );      ??

For more information on quotient methods for finitely presented groups see 45.13.


A more complicated example

We now give an example of how these algorithms and techniques can be used to find out some useful information about a given finitely presented group.

Let the group G be defined by the following presentation

< a, b,c | a6 = b6 = c6 = 1, ab2 = ba2, ac2 = ca2, bc2 =cb2 >

We may wish to know if G is finite, is it soluble, etc?

We first create the finitely presented group in the GAP environment as follows:

f:= FreeGroup("a","b","c");      ??
a:= f.1;; b:= f.2;; c:= f.3;;
g:= f/[ a^6, b^6, c^6, a*b^2*a^(-2)*b^(-1), a*c^2*a^(-2)*c^(-1), b*c^2*b^(-2)*c^(-1) ];;

We attempt to find the order of g

Size( g );      ??

This however fails.

Let us examine the group by looking at quotients. First we need to see
what G/G' is. This is done by the AbelianInvariants      ?? command as follows:

AbelianInvariants( g );      ??

So G/G' is isomorphic to the cyclic group of order 6.
Now we find a presentation for G'. First we create the derived subgroup G' of G:

ds:= DerivedSubgroup( g );      ??

We create a presentation for G' which will use the Reidemeister-Schreier method

ds_pres:= PresentationSubgroupRrs( g, ds );      ??

We seek to simplify ds_pres via the use of Tietze transformations as follows

TzGoGo( ds_pres );      ??

Let us look at the 10 relations in the simplified presentation ds_pres

TzPrintRelators( ds_pres );      ??

This is as simple as GAP can make it without altering any parameters of the Tietze transformation program so we find a finitely presented group from this presentation

ds:= FpGroupPresentation( ds_pres );      ??

Now we see what the abelianization of this group is, i.e. what is g'/g'' [Note g'' = (g')' ]

AbelianInvariants( ds );      ??

So g'/g'' is isomorphic to four copies of the cyclic group of order four.

We now repeat the method just used to calculate a presentation for g''

dsds:= DerivedSubgroup( ds );      ??

Now simplify this by the use of Tietze transformations:

dsds_pres:= PresentationSubgroupRrs( ds, dsds );      ??
TzGoGo( dsds_pres );      ??

Now convert this into a finitely presented group

dsds:= FpGroupPresentation( dsds_pres );      ??

And find the abelian invariants for g''

AbelianInvariants( dsds );      ??

Thus g''/g''' is isomorphic to the direct product of nine copies of the infinite cyclic group. This is, of course, enough to show that g is infinite. In fact we do better by testing that g'' is abelian so g''' is trivial

IsAbelian( dsds );      ??

This last command takes some time to complete. In fact we can do better by inspecting the presentation for g''

TzPrintRelators( dsds_pres );      ??

By inspection we see that the first 36 relators show that the nine generators of g'' commute pairwise. Hence g'' is abelian.

We have now shown that g'' must be the direct product of nine copies of the infinite cyclic group. So we have shown that g has derived length 3 with derived factors C6 , (C4)4, (C infinity)9. Thus G is an infinite soluble group of derived length 3.

Let us remark that different approaches to finding presentations for subgroups can lead to very different presentations. For example if we go down to g'' in a single step instead of the two as above we get a shorter presentation

f:= FreeGroup("a","b","c");      ??
a:= f.1;; b:= f.2;; c:= f.3;;
g:= f/[ a^6, b^6, c^6, a*b^2*a^(-2)*b^(-1), a*c^2*a^(-2)*c^(-1),
b*c^2*b^(-2)*c^(-1) ];;

ds:= DerivedSubgroup( g );      ??
dsds:= DerivedSubgroup( ds );      ??

dsds_pres:= PresentationSubgroupRrs( g, dsds );      ??
TzGoGo( dsds_pres );      ??

This leads to a presentation with 39 relators of total length 190 while the two step method above gives 50 relators of total length 354. If we complete the problem with

dsds:= FpGroupPresentation( dsds_pres );      ??
IsAbelian( dsds );      ??

We find that the final command takes around half the time that it does on the longer presentation found with the two step method.

JOC/EFR January 2003



Home   |   Members   |   Pre-prints   |   Library   |   Reports   |   Seminars   |   Conferences   |   Research   |   Publicity   |  Pictures   |   GAP   |   Webmail