> < ^ From:

^ Subject:

Dear Forum members,

David Joyner wrote:

I've been trying to obtain relations for two particular generators

of M23 using PresentationViaCosetTable, similar to the M12 example

given in the gap manual. The problem is gap says I run out of

memory. I tried this on a Pentuim 200 with 32M of RAM with the -m

28M option and on an SGI machine using the -m 150M option. The -a

<memory> option is mentioned as it kicks me out but I couldn't find

it in the manual. Can anyone explain -a or suggest a better command

to use? - David Joyner

First of all note that M23 has order 10,200,960, a coset table of that

group with respect to the identity subgroup for two generators has

four columns of that length each holding 4 byte integers as entries.

That is, just for the coset table of M23 with respect to the identity

you would need 16x10200960 bytes, so more than 160 MB.

However, the command 'PresentationViaCosetTable' also allows a two

stage procedure using words generating a subgroup, which then tries to

work with a coset table with respect to that subgroup and with a coset

table of that subgroup with respect to the identity subgroup. The

method goes back to John Cannon, it is described in an easy fashion in

my survey of coset table methods in the first St Andrews proceedings.

This is used in the M12 example in the manual. Optimally the subgroup

should be roughly of order square root of the order of the whole

group.

In the current example one may just apply the following primitive

search loop to find a suitable subgroup.

gap> G := MathieuGroup( 23 );; gap> a := G.1;; b := G.2;; gap> r4 := [ 0 .. 4 ];; r23 := [ 0 .. 23 ];; gap> sizes := [ ];; gap> for i in r23 do for j in r4 do for k in r23 do for l in r4 do > size := Size( Subgroup( G, [ a^i * b^j, a^k * b^l ] ) ); > if not size in sizes then > AddSet( sizes, size ); > Print( i, " ", j, " ", k, " ", l, " ", size, "\n" ); > fi; > od; od; od; od; 0 0 0 0 1 0 0 0 1 5 0 0 1 0 23 0 0 1 2 8 0 0 1 4 7 0 0 2 2 14 0 0 2 3 15 0 0 3 1 6 0 0 3 3 11 0 0 6 2 4 0 1 1 0 10200960 1 1 5 4 443520 1 1 6 2 5760 1 1 8 3 40320 1 4 17 3 20160 6 2 14 1 2688

This job takes quite some time to finish, but the results show up

relatively soon in the beginning. So one should interrupt the job as

soon as one has found an appropriate subroup.

Using the subgroup of order 5760 and index 1771, the function

'PresentationViaCosetTable' proceeds successfully.

gap> G := MathieuGroup( 23 ); Group( ( 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23 ), ( 3,17,10, 7, 9)( 4,13,14,19, 5)( 8,18,11,12,23)(15,20,22,21,16) ) gap> Size( G ); 10200960 gap> x := G.1;; y := G.2;; gap> H := Subgroup( G, [ x*y, x^6*y^2 ] );; gap> Size( H ); 5760 gap> Index( G, H ); 1771 gap> F := FreeGroup( "a", "b" );; gap> a := F.1;; b := F.2;; gap> P := PresentationViaCosetTable( G, F, [ a*b, a^6*b^2 ] ); << presentation with 2 gens and 130 rels of total length 4545 >>

An alternative approach is to use the function 'FpGroup' which

basically calls a procedure similar to 'PresentationViaCosetTable' in

an iterative loop over all subgroups in a stabilizer chain of G. The

resulting fp group F, say, contains a list of defining relators in its

component 'F.relators'.

This approach is much faster than the first one, but the number of the

resulting relators as well as their total length may be much larger.

The following example runs in 12MB workspace in a few seconds:

gap> G := OnePrimitiveGroup( DegreeOperation, 23, Size, 10200960 ); M(23) gap> H := Group( Random( G ), Random( G ) );; # to get arbitrary generators gap> Size( H ); # it is M23 10200960 gap> F := FpGroup( H ); Group( F1, F2 ) gap> rels := F.relators;; gap> length := Length( rels ); 375 gap> totallength := Sum( List( rels, rel -> LengthWord( rel ) ) ); 663218

You can of course also use your own pair of generators.

Finally, as to your question about the '-a' error message, I append a

comment given to me by Frank Celler:

-----

GASMAN, the storage manager of GAP uses `sbrk' to get blocks of memory

from (certain) operating systems and it is required that subsequent

calls to `sbrk' produce adjacent blocks of memory in this case because

GAP only wants to deal with one large block of memory. If the C

function `malloc' is called for whatever reason it is likely that

`sbrk' no longer produces adjacent blocks, therefore GAP does not use

`malloc' itself.

However some operation systems insist on calling `malloc' when a file

is open to fill a buffer. In order to catch these cases GAP

preallocates a block of memory with `malloc' which is immediately

freed. The amount of prealloc can be controlled with the '-a' option.

Why you got the '-a' error message instead of the usual "cannot

extend workspace" I cannot say. You could start GAP with the '-g'

option to see how much memory is actually allocated.

-----

Hope this explains some of what you ask about.

With kind regards Joachim Neubueser

> < [top]