1.20 About Finitely Presented Groups and Presentations

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.

Previous Up Top Next
Index

GAP 3.4.4
April 1997