> < ^ From:

< ^ Subject:

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> 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> 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> 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> 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, a^-2*c^-2*a^-1*b^-1*a^-6, b^-2*c^-2*b^-1*a^-2*c^-2*a^-1*b^-1*a^-2 *c^-2*a^-1*b^-1*c^-1*a^-2*b^-1*c^-1, b^-2*c^-2*b^-3*a^-8*c^-1*a^-1*b^-1*a^-1 ] gap> Index( m11, Subgroup( m11, last ) ); 495

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:

a:=AbstractGenerator("a");

b:=AbstractGenerator("b");G:=Group(a,b); G.relators:=[a^2,b^3,(a*b)^5] H:=Subgroup(G,[a,(b*a)^2*b^-1];OperationCosetsFpGroup(G,H);

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

(1,3,5)

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

Martin.

--

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]