> < ^ From:

> ^ Subject:

Dear GAP-FORUM,

This is a description of a calculation of a subgroup presentation using GAP,

which I carried out initially, and then communicated to Volkmar Felsch,

who was able to find a much quicker method of completing the final step.

The index of the subgroup in question in the original problem was

244823040 (= order of the Mathieu group M24), which is really quite large

for this sort of calculation, but in fact part of the argument is

theoretical (since the subgroup turns out to be a free group).

Derek Holt.

The problem initially came from Peter Rowley. He had an epimorphism of a

certain finitely presented group onto M24, and wanted to know whether the

kernel was free, and what its rank was.

The presentation is:

F := FreeGroup(4); F.relators := [ F.1^2, F.2^2, F.3^2, F.4^2, (F.2*F.3)^4, (F.1*F.3)^3, (F.2*F.4)^3, (F.3*F.1)*F.2*F.3*F.2*F.3*(F.1*F.3)*F.2, (F.2*F.4)*F.2*F.3*F.2*F.3*(F.4*F.2)*F.3 ];

and the images of the generators in the map onto M24, are a,b,c,d,

defined as follows.

a:=(1,2)(3,5)(4,9)(6,10)(7,13)(8,15)(11,14)(12,21)(16,24)(17,19)(18,20)(22,23); b:=(1,3)(2,5)(4,10)(6,9)(7,14)(8,16)(11,13)(12,18)(15,24)(17,23)(19,22)(20,21); c:=(1,2)(3,7)(4,6)(5,11)(8,15)(9,17)(10,19)(12,20)(13,14)(16,21)(18,24)(22,23); d:=(1,4)(2,6)(3,8)(5,12)(7,15)(9,18)(10,16)(11,20)(13,22)(14,23)(17,24)(19,21);

The first step was to find the inverse image G of the point-stabiliser M23

under this mapping, and to get a presentation of G. Since the index is only

24, that was straightforward, and I will omit details.

G turned out to be a free product of 3 cyclic groups of order 3.

(I think that Peter Rowley knew that already.)

Here is the presentation of G, and the images px,py,pz of the epimorphism of

G onto P = M23.

G:=FreeGroup("x","y","z"); x:=G.1;; y:=G.2;; z:=G.3; G.relators:=[x^3,y^3,z^3]; px:=( 1,20,21)( 3,13,11)( 4,10,17)( 5,14, 7)( 6, 9,19)(12,18,16); py:=( 1,16,14)( 3,10, 9)( 4, 8,20)( 6,12,15)( 7,17,19)(13,21,18); pz:=( 1,17,18)( 2, 4, 6)( 3,15, 8)( 5,20,12)(13,23,22)(16,21,19); P:=Group(px,py,pz);

Now the Kurosh Subgroup Theorem for free products states that any subgroup

of a free product is isomorphic to a free product of conjugates of the

free factors of the original group and a free group. Since the free factors

of G do not lie in the kernel of the map onto M23, none of their conjugates

can lie in the kernel, and so it follows immediately from the Kurosh Theorem

that this kernel must be free.

However, I know of no theoretical results which will tell us what the rank of

this kernel is. Does anyone know any more about results in this area?

It turned out eventually that the rank of the kernel was |M23| + 1,

so there must surely be some theoretical reason for this.

Now, assuming that the kernel really is free, it follows easily that the

inverse image in G of any subgroup of P with order not divisible by 3 must

also be free. The largest such subgroup is a normaliser of a Sylow

23-subgroup, and has order 253. The GAP calculation continues as follows.

S23:=SylowSubgroup(P,23); N23:=Normalizer(P,S23); # N23 has order 253 and index 40320 in P. #It was chosen because it appears to be the largest 3'-subgroup of P. RC:=RightCosets(P,N23); Q:=Operation(P,RC,OnRight); QG:=Q.generators; # QG is the permutation representation of P on the # right cosets of N23. We want a presentation of # the inverse image of N23 in G. To do this, we # need to calculate the coset table of this inverse # image. This consists of the permutations and their # inverses converted into lists. CT:=[]; CT[1]:=ListPerm(QG[1]); CT[2]:=ListPerm(QG[1]^-1); CT[3]:=ListPerm(QG[2]); CT[4]:=ListPerm(QG[2]^-1); CT[5]:=ListPerm(QG[3]); CT[6]:=ListPerm(QG[3]^-1);

HP:=PresentationSubgroup(G,CT,"h");

#Answer was (after a few hours runtime): # presentation with 53696 gens and 13375 rels of total length 40125

In fact, it turned out that each relator had length 3 and expressed one

generator as a product of two others, so the group itself is free of rank

53696 - 13375 = 40321.

In GAP, I first tried

SimplifyPresentation(HP);; # Interrupted (after 58 hours total running time) - output so far: #I there are 53596 generators and 13275 relators of total length 39825 #I there are 53496 generators and 13175 relators of total length 39525 #I there are 53396 generators and 13075 relators of total length 39225 #I there are 53296 generators and 12975 relators of total length 38925 #I there are 53196 generators and 12875 relators of total length 38625

#After interruption, there were 53128 generators remaining.

#At this rate, we will have a very long wait!

I then decided it would be wiser to try and verify directly that no generator

occurred more than once in the complete set of relators. I did this as

follows - this took about one hour of cpu-time.

for i in [1..53128] do occ:=TzOccurrences(HP.tietze,i); if occ[1][1]>1 then Print(i,occ,"\n"); fi; od;

Since nothing was printed, we conclude that no generator occurs more than once

in the total relator list, and so the group must be free of rank

53196 - 12875 = 40321 (which is the 1 + index of subgroup).

(In fact each relator has length 3.)

Since the kernel of the map from G to P has index 253 in the group HP, we

conclude that it is free of rank 253(40321 - 1) + 1 = |M23| + 1.

I wrote to Volkmar Felsch giving the details of this calculation, and he

found a much quicker method of checking that there were no repeated

generators in the final presentation. Here is his reply:

Dear Dr. Holt,

Thank you for sending me your interesting example. I think your

piece of code for proving that each generator occurs at most once

in the relators was a very clever approach. Of course, there are

a lot of different possibilities to do this, and some of these are

essentially faster. After reproducing your presentation HP, I have

tested a few of these approaches. The most efficient I found took

not even three seconds (on an HP 9000/725). Here it is:

gap> # Get a copy of the presentation record gap> P := Copy( HP ); << presentation with 53696 gens and 13375 rels of total length 40125 >> gap> oldtime := Runtime( );; gap> gap> # Check whether each generator occurs at most once in the relators gap> rels := P.tietze[TZ_RELATORS];; gap> flat := Flat( rels );; gap> for i in [ 1 .. Length( flat ) ] do > if flat[i] < 0 then flat[i] := -flat[i]; fi; > od; gap> if Length( Set( flat ) ) = Length( flat ) then > gens := P.tietze[TZ_GENERATORS]; > rank := Length( gens ) - Length( rels ); > Print( " The group is free of rank ", rank, "\n" ); > fi; The group is free of rank 40321 gap> gap> # Print the time used gap> Print( "time = ", Runtime( ) - oldtime, "\n" ); time = 2660 gap>

I wonder if we should insert such a kind of test into the default

strategy of the SimplifyPresentation function. On the one hand,

there is only a very small probability that a presentation under

investigation will have this property, on the other hand this test

is very cheap compared, for instance, with the expense of the

substring search procedure involved in that command. (When I designed

the Tietze functions, I did not at all think of presentations of this

magnitude.)

> < [top]