> < ^ Date: Mon, 28 Sep 1992 17:57:09 +0100
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: homorphisms from fp groups

There were two e-mails to the GAP Forum that I wanted to answer for a
very long time. I apologize that it took me so long. I hope that this
is still interesting.

In his e-mail of 8-Jun-92 David Sibley wrote:

Again I am a bit confused and would appreciate some pointers on how best
to do the following.

Note: I have not yet done either of the upgrades and that might be my
problem. We are going to install Gap in a different place and I am
waiting on the upgrade until we move it.

Well neither the first nor the second upgrade would have been any help.
However, the third upgrade, which I sent out together with this answer
will help. I will first discuss how to solve your problem and then
afterwards give some hints why this did not work in GAP 3.1 patchlevel 2.

David continues:

I have a finitely presented group (it's M11) and a subgroup. I use
OperationCosetsFpGroup to get the permutation representation on the
cosets of the subgroup.

1. OperationHomomorphism does not produce the homomorphism I want.
I just get an error message that the permutation group is the wrong
kind of thing. Why doesn't this work? (Even if it's not designed to,
I think it should, just so one can do what I'm trying to do here.)

Well here is an example of what can be done in GAP 3.1 patchlevel 3.

gap> # first define m11 as a finitely presented group
gap> a := AbstractGenerator( "a" );
gap> b := AbstractGenerator( "b" );
gap> c := AbstractGenerator( "c" );
gap> m11 := Group( a, b, c );;
gap> m11.relators := [ a^11, b^5, c^4, (a*c)^3, a^b/a^4, b^c/b^2 ];;
gap> m11.name := "m11";;
gap> # take the subgroup of index 12 and the operation on its cosets
gap> m11_12 := Subgroup( m11, [ a^3, b, c^2 ] );
gap> m11_p := OperationCosetsFpGroup( m11, m11_12 );
Group( ( 2, 3, 4, 7, 5, 9,10,11, 8,12, 6),
       ( 3, 5, 9,12, 7)( 4, 8, 6,11,10),
       ( 1, 2)( 3, 6,12,11)( 4, 7)( 5,10, 9, 8) )
gap>  m11_p.name := "m11_p";;
gap> # make the homomorphism from m11 into the permutation group
gap> h := OperationHomomorphism( m11, m11_p );
GroupHomomorphismByImages( m11, m11_p,
                       [ a, b, c ],
                       [ ( 2, 3, 4, 7, 5, 9,10,11, 8,12, 6),
                         ( 3, 5, 9,12, 7)( 4, 8, 6,11,10),
                         ( 1, 2)( 3, 6,12,11)( 4, 7)( 5,10, 9, 8) ] )
gap> # compute the 2-Sylow subgroup in the permutation group
gap> SylowSubgroup( m11_p, 2 );
Subgroup( m11_p,
      [ ( 2,10)( 4,12)( 5, 9)( 6, 7),
        ( 3, 8)( 4,12)( 5, 7)( 6, 9),
        ( 1,11)( 2, 4)( 6, 7)(10,12),
        ( 1, 3)( 2, 6,10, 7)( 4, 5,12, 9)( 8,11) ] )
gap> # and pull the result back to m11
gap> List( last.generators, gen -> PreImagesRepresentative( h, gen ) );
[ b^-4*a^-2*c^-2*a^-1*b^-2*a^-7,
  b^-2*c^-2*b^-3*a^-8*c^-1*a^-1*b^-1*a^-1 ]
gap> Index( m11, Subgroup( m11, last ) );

You probably noticed that I did not simply computed the 2-Sylowsubgroup
of the finitely presented group with 'PreImage(SylowSubgroup(m11_p,2))'.
There is a reason for that, which I want to formulate as a warning.

You should *not* use 'PreImage', 'PreImages', or 'Kernel' for an
operation homomorphism (build by 'OperationHomomorphism') from a
finitely presented group onto the group given by the operation on the
cosets of a subgroup (as build by 'OperationCosetsFpGroup') in any
but the smallest examples.

The reason is that in those cases it is necessary to compute the kernel
of the homomorphism. And I don't know a way to compute this kernel
without writing down the coset table of this kernel (in fact I don't even
know a way to test whether this kernel is trivial without writing down
the coset table of this kernel). Because the index of the kernel in the
whole group is likely to be rather large this will take a lot of time and
probably a lot of space (if it works at all in any reasonable amount of
time and memory).

David continues:

2. I use GroupHomomorphismByImages to produce the homomorphism I want
anyway. As recommended, I set the field isMapping to true. I then
try to compute an image: Image(f,a). Since a is one of the original
abstract generators, this should be trivial and instantaneous. It's
not. After waiting a bit, I abort this operation and use
ImagesRepresentative instead. This gives an immediate answer. Why
is Image not working here?

This will also now work in GAP 3.1 patchlevel 3. However in GAP 3.1
patchlevel 2 this is what happened. 'GroupHomorphismByImages' was
implemented using the generic functions that should work for all groups.
When asked to compute the image of an element under such an homomorphism,
'Image' (actually 'GroupHomomorphismByImagesOps.Image') makes two
parallel lists. One contains all the elements of the source, and the
other list contains the image of the corresponding element in the source.
This is done by generating all elements of the source using a orbit like
algorithm and performing exactly the same computations with the images of
the generators. Now for finitely presented groups the process of
enumerating all elements of the source will actually never stop, because
instead of really enumerating the elements of the source, the process
will try to enumerate the elements of the coressponding free group. This
will fail of course. But if you interrupt the computation after some
time, quite a bit of elements and there images will already be found.
This partial list will already be stored in the homomorphism record. If
you now call 'ImagesRepresentative' (the same thing would happen if you
simply called 'Image' again), 'ImagesRepresentative' thinks that those
lists are complete, will look up 'a' in the list of elements, find it
there, and return the corresponding element in the images list.

David continues:

Generally, I would think that for efficient computations one wants to
use some small-degree permutation represenation of the group. Yet one
also must keep some connection to the original presentation of the
group in most cases. This is all I'm trying to do here. If there's a
better way, or this is the wrong idea, please let me know.

Of course, what you say is absolutely correct.

In his e-mail message of 19-Jun-92 Allan Adler addresses the same issue:

I'm glad to see the recent articles on going from a finitely presented
group to a permutation group in GAP. I have been having trouble with
just this. I would find it helpful if someone would post a complete
example of how this is done. Specifically:

Let's say I define G as a finitely presented group and H as a subgroup:





So far, I am following the example of 21.5 of the GAP manual. According
to that example, GAP now returns:

Group( (2,3)(4,5), (1,2,4) );

Can someone now post the code that (with this example) lets one take
any word w in a,b and returns the corresponding permutation, along with
a transcript showing that the code works?

This answer is again that this will only work in GAP 3.1 patchlevel 3.
There however it is very easy. Assuming the name of the permutation
group is 'P' then you just enter

hom := OperationHomomorphism( G, P );
Image( hom, a*b*a );

to get


Hope this helps. Again I apologize that this took so long.


Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany

> < [top]