> < ^ Date: Thu, 18 Apr 1996 14:16:28 +0200
> < ^ From: Volkmar Felsch <Volkmar.Felsch@Math.RWTH-Aachen.DE >
> ^ Subject: Computing a presentation for a group
Announcement
------------

I would like to announce that a new GAP function,

PresentationViaCosetTable,

is available which computes a presentation for a given concrete
(e. g. permutation or matrix) group. The method being used is
John Cannon's relations finding algorithm which has been described in

John J. Cannon: Construction of defining relators for finte groups.
Discrete Math. 5 (1973), 105-129, and in

Joachim Neubueser: An elementary introduction to coset table methods
in computational group theory. Groups-St. Andrews 1981, edited by
C. M. Campbell and E. F. Robertson, pp. 1-45. London Math. Soc.
Lecture Note Series no. 71, Cambridge Univ. Press, Cambridge, 1982.

The function is available by anonymous ftp to 'ftp.math.rwth-aachen.de'.
There are two files, a file '/pub/incoming/pres.doc' which contains just
a copy of this announcement, and a file '/pub/incoming/pres.g' which
contains the function.

Description
-----------

The function can be called using either of the two forms

PresentationViaCosetTable( G );
or
PresentationViaCosetTable( G, F, words );

In its first form, if only the group G has been specified, it applies
Cannon's single stage algorithm which, by plain element multiplication,
computes a coset table of G with respect to its trivial subgroup and
then uses coset enumeration methods to find a defining set of relators
for G. The resulting presentation is returned as a presentation record.

Example:

gap> Read( "pres.g" );
gap> G := GeneralLinearGroup( 2, 7 );
GL(2,7)
gap> G.generators;
[ [ [ Z(7), 0*Z(7) ], [ 0*Z(7), Z(7)^0 ] ],
  [ [ Z(7)^3, Z(7)^0 ], [ Z(7)^3, 0*Z(7) ] ] ]
gap> Size( G );
2016
gap> P := PresentationViaCosetTable( G );
<< presentation with 2 gens and 5 rels of total length 46 >>
gap> TzPrintRelators( P );
#I  1. f.2^3
#I  2. f.1^6
#I  3. f.1*f.2*f.1*f.2*f.1*f.2*f.1*f.2*f.1*f.2*f.1*f.2
#I  4. f.1*f.2*f.1^-1*f.2*f.1*f.2^-1*f.1^-1*f.2*f.1*f.2*f.1^-1*f.2^-1
#I  5. f.1^2*f.2*f.1*f.2*f.1*f.2^-1*f.1^-1*f.2^-1*f.1^3*f.2^-1

The second form allows to call Cannon's two stage algorithm which
first applies the single stage algorithm to an appropriate subgroup
H of G and then uses the resulting relators of H and a coset table
of G with respect to H to find relators of G. In this case the second
argument, F, is assumed to be a free group with the same number of
generators as G, and words is expected to be a list of words in the
generators of F which, when being evaluated in the corresponding
generators of G, provide subgroup generators for H.

Example:

gap> M12 := MathieuGroup( 12 );;
gap> M12.generators;
[ ( 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> F := FreeGroup( "a", "b", "c" );
Group( a, b, c )
gap> words := [ F.1, F.2 ];
[ a, b ]
gap> P := PresentationViaCosetTable( M12, F, words );
<< presentation with 3 gens and 10 rels of total length 97 >>
gap> G := FpGroupPresentation( P );
Group( a, b, c )
gap> G.relators;
[ c^2, b^4, a*c*a*c*a*c, a*b^-2*a*b^-2*a*b^-2, a^11,
  a^2*b*a^-2*b^-2*a*b^-1*a^2*b^-1,
  a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1,
  a^2*b*a^2*b^-2*a^-1*b*a^-1*b^-1*a^-1*b^-1,
  a^2*b^-1*a^-1*b^-1*a*c*b*c*a*b*a*b, a^3*b*a^2*b*a^-2*c*a*b*a^-1*c*a
 ]

Before it is returned, the resulting presentation is being simplified
by appropriate calls of the function 'SimplifyPresentation', but without
allowing it to eliminate any generators. This restriction guarantees
that we get a bijection between the list of generators of G and the list
of generators in the presentation. Hence, if the generators of G are
redundant and if you don't care for the bijection, it may be convenient
to apply the function 'SimplifyPresentation' again.

Example:

gap> H := Group(
>  [ (2,5,3), (2,7,5), (1,8,4), (1,8,6), (4,8,6), (3,5,7) ], () );;
gap> P := PresentationViaCosetTable( H );
<< presentation with 6 gens and 12 rels of total length 42 >>
gap> SimplifyPresentation( P );
#I  there are 4 generators and 10 relators of total length 36
------------

I hope the function is of some use to someone, Volkmar Felsch

volkmar.felsch@math.rwth-aachen.de


> < [top]