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.)