> < ^ From:

> ^ Subject:

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 inJoachim 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]