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