In this section we will show you the investigation of a Coxeter group that is given by its presentation. You will see that finitely presented groups and presentations are different kinds of objects in GAP. While finitely presented groups can never be changed after they have been created as factor groups of free groups, presentations allow manipulations of the generators and relators by Tietze transformations. The investigation of the example will involve methods and algorithms like Todd-Coxeter, Reidemeister-Schreier, Nilpotent Quotient, and Tietze transformations.
We start by defining a Coxeter group c on five generators as a factor
group of the free group of rank 5, whose generators we already call
c.1, ..., c.5.
gap> c := FreeGroup( 5, "c" );;
gap> r := List( c.generators, x -> x^2 );;
gap> Append( r, [ (c.1*c.2)^3, (c.1*c.3)^2, (c.1*c.4)^3,
> (c.1*c.5)^3, (c.2*c.3)^3, (c.2*c.4)^2, (c.2*c.5)^3,
> (c.3*c.4)^3, (c.3*c.5)^3, (c.4*c.5)^3,
> (c.1*c.2*c.5*c.2)^2, (c.3*c.4*c.5*c.4)^2 ] );
gap> c := c / r;
Group( c.1, c.2, c.3, c.4, c.5 )
If we call the function Size for this group GAP will invoke the
Todd-Coxeter method, which however will fail to get a result going up to
the default limit of defining 64000 cosets:
gap> Size(c);
Error, the coset enumeration has defined more than 64000 cosets:
type 'return;' if you want to continue with a new limit of
128000 cosets,
type 'quit;' if you want to quit the coset enumeration,
type 'maxlimit := 0; return;' in order to continue without a limit,
in
AugmentedCosetTableMtc( G, H, -1, "_x" ) called from
D.operations.Size( D ) called from
Size( c ) called from
main loop
brk> quit;
In fact, as we shall see later, our finitely presented group is infinite and hence we would get the same answer also with larger limits. So we next look for subgroups of small index, in our case limiting the index to four.
gap> lis := LowIndexSubgroupsFpGroup( c, TrivialSubgroup(c), 4 );;
gap> Length(lis);
10
The LowIndexSubgroupsFpGroup function in fact determines generators for
the subgroups, written in terms of the generators of the given group. We
can find the index of these subgroups by the function Index, and the
permutation representation on the cosets of these subgroups by the
function OperationCosetsFpGroup, which use a Todd-Coxeter method. The
size of the image of this permutation representation is found using
Size which in this case uses a Schreier-Sims method for permutation
groups.
gap> List(lis, x -> [Index(c,x),Size(OperationCosetsFpGroup(c,x))]);
[ [ 1, 1 ], [ 4, 24 ], [ 4, 24 ], [ 4, 24 ], [ 4, 24 ], [ 4, 24 ],
[ 4, 24 ], [ 4, 24 ], [ 3, 6 ], [ 2, 2 ] ]
We next determine the commutator factor groups of the kernels of these
permutation representations. Note that here the difference of finitely
presented groups and presentations has to be observed: We first
determine the kernel of the permutation representation by the function
Core as a subgroup of c, then a presentation of this subgroup using
PresentationSubgroup, which has to be converted into a finitely
presented group of its own right using FpGroupPresentation, before its
commutator factor group and the abelian invariants can be found using
integer matrix diagonalisation of the relators matrix by an elementary
divisor algorithm. The conversion is necessary because Core computes a
subgroup given by words in the generators of c but
CommutatorFactorGroup needs a parent group given by generators and
relators.
gap> List( lis, x -> AbelianInvariants( CommutatorFactorGroup(
> FpGroupPresentation( PresentationSubgroup( c, Core(c,x) ) ) ) ) );
[ [ 2 ], [ 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 0, 0, 0, 0, 0, 0 ], [ 2, 2, 2, 2, 2, 2 ], [ 3 ] ]
More clearly arranged, this is
[ [ 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 2, 2, 2, 2, 2, 2, 2, 2 ],
[ 0, 0, 0, 0, 0, 0 ],
[ 2, 2, 2, 2, 2, 2 ],
[ 3 ] ]
Note that there is another function AbelianInvariantsSubgroupFpGroup
which we could have used to obtain this list which will do an abelianized
Reduced Reidemeister-Schreier. This function is much faster because it
does not compute a complete presentation for the core.
The output obtained shows that the third last of the kernels has a free
abelian commutator factor group of rank 6. We turn our attention to this
kernel which we call n, while we call the associated presentation pr.
gap> lis[8];
Subgroup( Group( c.1, c.2, c.3, c.4, c.5 ),
[ c.1, c.2, c.3*c.2*c.5^-1, c.3*c.4*c.3^-1, c.4*c.1*c.5^-1 ] )
gap> pr := PresentationSubgroup( c, Core( c, lis[8] ) );
<< presentation with 22 gens and 41 rels of total length 156 >>
gap> n := FpGroupPresentation(pr);;
We first determine p-factor groups for primes 2, 3, 5, and 7.
gap> InfoPQ1:= Ignore;;
gap> List( [2,3,5,7], p -> PrimeQuotient(n,p,5).dimensions );
[ [ 6, 10, 18, 30, 54 ], [ 6, 10, 18, 30, 54 ], [ 6, 10, 18, 30, 54 ],
[ 6, 10, 18, 30, 54 ] ]
Observing that the ranks of the lower exponent-p central series are the same for these primes we suspect that the lower central series may have free abelian factors. To investigate this we have to call the package "nq".
gap> RequirePackage("nq");
gap> NilpotentQuotient( n, 5 );
[ [ 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0 ] ]
gap> List( last, Length );
[ 6, 4, 8, 12, 24 ]
The ranks of the factors except the first are divisible by four, and we compare them with the corresponding ranks of a free group on two generators.
gap> f2 := FreeGroup(2);
Group( f.1, f.2 )
gap> PrimeQuotient( f2, 2, 5 ).dimensions;
[ 2, 3, 5, 8, 14 ]
gap> NilpotentQuotient( f2, 5 );
[ [ 0, 0 ], [ 0 ], [ 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0 ] ]
gap> List( last, Length );
[ 2, 1, 2, 3, 6 ]
The result suggests a close relation of our group to the direct product
of four free groups of rank two. In order to study this we want a simple
presentation for our kernel n and obtain this by repeated use of Tietze
transformations, using first the default simplification function TzGoGo
and later specific introduction of new generators that are obtained as
product of two of the existing ones using the function TzSubstitute.
(Of course, this latter sequence of Tietze transformations that we
display here has only been found after some trial and error.)
gap> pr := PresentationSubgroup( c, Core( c, lis[8] ) );
<< presentation with 22 gens and 41 rels of total length 156 >>
gap> TzGoGo(pr);
#I there are 6 generators and 14 relators of total length 74
gap> TzGoGo(pr);
#I there are 6 generators and 13 relators of total length 66
gap> TzGoGo(pr);
gap> TzPrintPairs(pr);
#I 1. 3 occurrences of _x6 * _x11^-1
#I 2. 3 occurrences of _x3 * _x15
#I 3. 2 occurrences of _x11^-1 * _x15^-1
#I 4. 2 occurrences of _x6 * _x15
#I 5. 2 occurrences of _x6^-1 * _x15^-1
#I 6. 2 occurrences of _x4 * _x15
#I 7. 2 occurrences of _x4^-1 * _x15^-1
#I 8. 2 occurrences of _x4^-1 * _x11
#I 9. 2 occurrences of _x4 * _x6
#I 10. 2 occurrences of _x3^-1 * _x11
gap> TzSubstitute(pr,10,2);
#I substituting new generator _x26 defined by _x3^-1*_x11
#I eliminating _x11 = _x3*_x26
#I there are 6 generators and 13 relators of total length 70
gap> TzGoGo(pr);
#I there are 6 generators and 12 relators of total length 62
#I there are 6 generators and 12 relators of total length 60
gap> TzGoGo(pr);
gap> TzSubstitute(pr,9,2);
#I substituting new generator _x27 defined by _x1^-1*_x15
#I eliminating _x15 = _x27*_x1
#I there are 6 generators and 12 relators of total length 64
gap> TzGoGo(pr);
#I there are 6 generators and 11 relators of total length 56
gap> TzGoGo(pr);
gap> p2 := Copy(pr);
<< presentation with 6 gens and 11 rels of total length 56 >>
gap> TzPrint(p2);
#I generators: [ _x1, _x3, _x4, _x6, _x26, _x27 ]
#I relators:
#I 1. 4 [ -6, -1, 6, 1 ]
#I 2. 4 [ 4, 6, -4, -6 ]
#I 3. 4 [ 5, 4, -5, -4 ]
#I 4. 4 [ 4, -2, -4, 2 ]
#I 5. 4 [ -3, 2, 3, -2 ]
#I 6. 4 [ -3, -1, 3, 1 ]
#I 7. 6 [ -4, 3, 4, 6, -3, -6 ]
#I 8. 6 [ -1, -6, -2, 6, 1, 2 ]
#I 9. 6 [ -6, -2, -5, 6, 2, 5 ]
#I 10. 6 [ 2, 5, 1, -5, -2, -1 ]
#I 11. 8 [ -1, -6, -5, 3, 6, 1, 5, -3 ]
gap> TzPrintPairs(p2);
#I 1. 5 occurrences of _x1^-1 * _x27^-1
#I 2. 3 occurrences of _x6 * _x27
#I 3. 3 occurrences of _x3 * _x26
#I 4. 2 occurrences of _x3 * _x27
#I 5. 2 occurrences of _x1 * _x4
#I 6. 2 occurrences of _x1 * _x3
#I 7. 1 occurrence of _x26 * _x27
#I 8. 1 occurrence of _x26 * _x27^-1
#I 9. 1 occurrence of _x26^-1 * _x27
#I 10. 1 occurrence of _x6 * _x27^-1
gap> TzSubstitute(p2,1,2);
#I substituting new generator _x28 defined by _x1^-1*_x27^-1
#I eliminating _x27 = _x1^-1*_x28^-1
#I there are 6 generators and 11 relators of total length 58
gap> TzGoGo(p2);
#I there are 6 generators and 11 relators of total length 54
gap> TzGoGo(p2);
gap> p3 := Copy(p2);
<< presentation with 6 gens and 11 rels of total length 54 >>
gap> TzSubstitute(p3,3,2);
#I substituting new generator _x29 defined by _x3*_x26
#I eliminating _x26 = _x3^-1*_x29
gap> TzGoGo(p3);
#I there are 6 generators and 11 relators of total length 52
gap> TzGoGo(p3);
gap> TzPrint(p3);
#I generators: [ _x1, _x3, _x4, _x6, _x28, _x29 ]
#I relators:
#I 1. 4 [ 6, 4, -6, -4 ]
#I 2. 4 [ 1, -6, -1, 6 ]
#I 3. 4 [ -5, -1, 5, 1 ]
#I 4. 4 [ -2, -5, 2, 5 ]
#I 5. 4 [ 4, -2, -4, 2 ]
#I 6. 4 [ -3, 2, 3, -2 ]
#I 7. 4 [ -3, -1, 3, 1 ]
#I 8. 6 [ -2, 5, -6, 2, -5, 6 ]
#I 9. 6 [ 4, -1, -5, -4, 5, 1 ]
#I 10. 6 [ -6, 3, -5, 6, -3, 5 ]
#I 11. 6 [ 3, -5, 4, -3, -4, 5 ]
The resulting presentation could further be simplified by Tietze
transformations using TzSubstitute and TzGoGo until one reaches
finally a presentation on 6 generators with 11 relators, 9 of which are
commutators of the generators. Working by hand from these, the kernel
can be identified as a particular subgroup of the direct product of four
copies of the free group on two generators.
GAP 3.4.4