> < ^ From:

< ^ Subject:

Paul Igodt asks in his e-mail message of 1994/02/07

Is there a procedure in GAP to solve the "word"-problem for permutation

groups? E.g. something like "wordsolve(element,group,group.generators)"?

Steve Linton answers in his e-mail message of 1994/02/08

Not as far as I know [...]

Harald Boegeholz answers in his e-mail message of 1994/02/08

I don't think so. I once wrote such a program (by modifying

MakeStabStrong etc. in such a way that it records how new generators

were constructed out of the old generators).

Derek Holt answers in his e-mail message of 1994/02/08

Yes, I have also done something similar.

It is in fact possible to do this in GAP, but appearantly this is one of

the best kept secrets in GAP :-(.

Here is how to do it.

gap> m12 := Group( (1,12,6,8,9,2)(3,7,4,10,11,5), > (1,4,5,3,11)(2,12,7,6,9) );; gap> Size( m12 ); 95040 gap> f2 := FreeGroup( 2, "f2" ); Group( f2.1, f2.2 ) gap> h := GroupHomomorphismByImages(f2,m12,f2.generators,m12.generators);; gap> r := Random(m12);; w := PreImagesRepresentative(h,r);; time; 3089 gap> r := Random(m12);; w := PreImagesRepresentative(h,r);; time; 4 gap> LengthWord( w ); 510

The first call to 'PreImagesRepresentative' takes about 3 seconds,

because it constructs the extended stabilizer chain.

All subsequent calls then take only a couple of milliseconds.

It is important to use 'PreImagesRepresentative', instead of 'PreImage'.

'PreImage' can only be used if each image has a unique preimage, i.e., is

if the kernel of the homomorphism is trivial, which is clearly not the

case with 'h' (actually GAP 3.3 fails with the message 'index of <H> in

<G> is infinite', which is a bug).

To compute images under 'h', one should either use 'ImagesRepresentative',

or set 'h.isHomomorphism := true;' and 'h.isMapping := true;' and use

'Image' (yes, it is a bug in GAP that declaring 'h' to be a homorphism

is necessary in this case).

It is also possible to do this as follows.

gap> x := GroupHomomorphismByImages(m12,f2,m12.generators,f2.generators);; gap> r := Random(m12);; w := ImagesRepresentative(h,r);; time; 4152 gap> r := Random(m12);; w := ImagesRepresentative(h,r);; time; 4 gap> LengthWord( w ); 415

Note, however that 'x' is not a homorphism, in fact it is not even a

single valued mapping. In GAP 3.3 this is not a problem (but in GAP 4.0

we will probably disallow the construction of such multivalued mappings).

But one must use 'ImagesRepresentative' of course. Telling GAP that it

is a homomorphism, so that one can use 'Image', is indeed a shocking

suggestion.

Anyhow, the problem with this approach is however the length of the words

produced by this method. In the above example the words are of length

510 and 415 respectively. The methods used by Philip Osterlund to

shorten the words seem very interesting.

Martin.

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

> < [top]