> < ^ From:

> < ^ Subject:

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

> < [top]