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