Dear Forum members,
In a letter of January 27 to this Forum, Dima Pasechnik had asked:
(insertions [...] by me)
I have a homomorphism [to be called f in the sequel] of a (big,
possibly infinite) finitely presented group [to be called G in the
sequel] to a permutation group of degree few hundred. I would like
to know the abelian factors of the kernel [to be called N in the
sequel] of this homomorphism. Is there a way of doing this in GAP
now?
In reply to my request for more details, in a letter of January 28 he
had explained:
The image of the homomorphism [f] is McL (the MacLaughlin group) in
its minimal permutation representation on 275 points. It is
constructed by adding 2 extra relators to the original presentation
of G. It is known that G itself also admits a homomorphism onto a
nonsplit extension 3^23.McL. We conjecture that the abelian
invariants of the kernel [N] of G->McL are just this 3^23.
At this point I have taken the discussion out of the Forum, since it
went into details, but have in fact continued it quite intensively
during the last days. Alexander Hulpke, Werner Nickel, and George
Havas also took part in that discussion.
All the computations that I describe below were done by Volkmar
Felsch, who also wrote the two GAP programs that play a central role
in these, but should also be useful quite generally in similsr
situations.
I first asked Dima to send us his data, and he sent us
1. The presentation of G (on 10 involutary generators, with 41
further fairly short relators)2. Two words w1 and w2 in the generators of G that generate the
kernel N of the homomorphism f of G onto McL as a normal
subgroup.3. With respect to the presentation of M := G/N (isomorphic to
McL), obtained by adding w1 and w2 to the relators of G, 10
words in the generators which generate a subgroup S1/N of index
275 in M. The homomorphism f is then defined by the permutation
representation of M on the cosets of S1/N in M = G/N.
Let me depict the situation in a diagram in which I have introduced
some further subgroups that will be defined later.
G ------> McL | f | | 275 | 275 | | S1 ------> S1f | f | | 162 | 162 | | S2 S2f | | | 20160 | 20160 | | N ------> <1> | f | 3^23 | K | | 1? | N' | | ??? | <1>
Let K be the kernel of the homomorphism of G onto the nonsplit
extension of 3^23 .Mcl that is known to exist, then Dima's question is
whether K = N'.
To decide this, one would like to get N/N'. One classical approach
would be to try to get a presentation of N and apply the command
'AbelianInvariants'. The idea to obtain a presentation of N would be
to use the Reidemeister-Schreier method RS or rather its improved
version Reduced Reidemeister-Schreier RRS, described in the GAP
manual.
To apply RS or RRS in order to obtain a presentation of a subgroup Y
of a finitely presented group X, the coset table of Y in X is needed,
and it is clear that this cannot be used for N in G, which is of index
|McL| = 898.128.000. Rather one would try to apply this idea several
times stepping down a chain of subgroups from G to N and finding
presentations of each of these subgroups in turn.
This idea has indeed been used in the past in similar
situations. However I know of no cases where the index to be 'bridged'
in this way was bigger than 50.000. In fact, as you will see we did
not succeed with this idea, and in fact cannot at present answer
Dima's question, however the methods involved as well as some thoughts
what might be done in the future are perhaps interesting enough to
justify a description.
We start by determining the coset table of S1/N in G/N = M, using an
ordinary Todd-Coxeter method (by the function 'CosetTableFpGroup') for
the finitely presented group G/N with subgroup generators of S1/N
known. This coset table can be considered as a coset table of S1 in G
and we can obtain a presentation of S1 using the function
'PresentationSubgroupRrs'.
This function produces a presentation of S1 on 539 generators with
5142 relators of total length 20764, which reduces under Tietze
transformations to a presentation of S1 on 3 generators with 51
relators of total length 1649. These three generators are in fact
three of the original generators.
We also determine McL as a permutation group on 275 points applying
the function 'OperationCosetsFpGroup'. We need McL to find further
subgroups of G contained in S1 as preimages of subgroups of McL
contained in S1f (cf. picture above). There are several choices for
such subgroups of McL. One is to consider a stabilizer chain of McL,
which has indices 275, 162, 105, 16, 3, 2, 2. The next base point is 2
and so we obtain a subgroup S2f of McL of index 162 in S1f as
stabilizer of the point 2 in S1f.
We next need the coset table of S2 in S1, and we want to obtain it by
calculating the coset table of S2f in S1f and interpreting this as
coset table of S2 in S1. There are two problems here:
- while GAP provides a function to compute the permutation
representation of S2f in S1f, this does not produce the coset table in
the format GAP needs for the RRS function. Volkmar Felsch has written
such a function 'CosetTableBySubgroup'.
- S1 is now known by a presentation on three generators that were
produced by the function RRS as words in the generators of G and we
need the images of these three generators under f in order to be able
to use the function described above correctly. Volkmar Felsch has
written a function 'TzElementsFromTree' for this purpose.
With the help of these two functions then indeed a coset table of S2
in S1 can be obtained and used as input for RRS together with the
presentation of S1. RRS then produces a presentation of S2, however
this is on 186 generators with 7186 relators of total lenghth 136.656.
Of course this can again be reduced by Tietze transformations and
indeed these can be used to show that S2 can be generated by 5
elements, however the presentation obtained for these looks too big to
apply the same kind of trick again to find e.g. a presentation of a
subgroup S3 contained in S2 as the preimage of some S3f contained in
S2f with the hope to step down to N eventually by further such steps.
So we gave up at this stage.
Volkmar Felsch will send his two functions mentioned above as well as
a log of the computation described above that shows how they are used
to St. Andrews for inclusion among the 'deposited contributions'.
Let me close this lengthy discussion with some general remarks.
- The tools used above can of course be used to try to step down other
chains of subgroups or to use different presentations obtained e.g. by
application of Tietze transformations. There is no good reason why
some of these should not be more managable than what we used. So if
somebody is interested in the original or similar questions (s)he
should try.
- However I would not be too optimistic that Dima's question can
indeed be answered this way. As I said in my reply to Dima's first
letter, this kind of method works for not too big indices, and |McL|
likely qualifies as 'too big'.
- On the other hand a rather encouraging information from this
computation is that the subgroups S1 and S2 constructed intermediately
are on so few generators (at most 3 and 5 respectively). One is
inclined to believe that these subgroups should have much better
presentations than those obtained from RRS.
- In fact it is our experience that RRS (as well as RS) usually
produces many redundant relators. We have veryfied this very often
when the group defined by the presentation obtained from RRS was
finite. So a first methodological challenge that one can take from
this experiment is:
*** Device an improved RRS that avoids producing (many) redundant
relators.
However one may also look at Dima's problem forgetting about RRS and
all that. N/N' after all is an abelian group on which McL operates and
Dima has normal subgroup generators for N, which provide generators of
N/N' as a (McL-) operator group. Or consider N/N'.N^3, then we have a
GF(3)McL module for which we have module generators. Hence a second
challenge:
*** It should be possible to use ideas such as in Steve Linton's
module enumerator or the Groebner base techniques in Charles
Sims'/Eddie Lo's 'Polycyclic Quotient' to find subgroup generators for
this module.
If somebody does something along these lines, I would be grateful to
get notified. We may in fact later on try to follow the second
challenge ourselves, and if we get anywhere, you will hear of it in
this Forum.
As a final remark: I have welcomed the opportunity given by Dima's
question to talk about methods even though they do not lead to success
here.
***I would welcome if GAP users would occasionally also report about
attempts, successful or not, of using GAP on particular problems. Only
that way can we improve the mathematical functionality of GAP.
Joachim Neubueser