Dear Forum,

In his letter, Derek Holt wrote:
>
> >
> > > Is there a procedure in GAP to solve the "word"-problem for permutation groups?
> > > E.g. something like "wordsolve(element, group, group.generators)" ?
> >
> > 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).
>
> Yes, I have also done something similar.
> I have often found myself in the situation of having some sort of
> homomorphism phi:G -> H, where G is a permutation group, and
> phi is defined by its images on the generators.
> But then you want to be able to calculate phi on an arbitrary element
> of G. The last time I tried this naively in GAP, it took ages, even
> on what I consider to be moderately small groups like M12. I suspect it
> was calculating the whole Cayley graph of the group to do the calculation.

If you define the Homomorphism by GroupHomomorphismByImages (which is
probably the procedure most useful for this task), you should also set
h.isMapping:=true; and h.isHomomorphism:=true;
The reason is, that GAP will otherwise try to check, whether the mapping
really is an homomorphism, a task which might lead to partial computation of
the Cayley graph and takes abominably long.

To do this efficiently, you do not need to express an element g as a
word in the original generators (which, as was observed by Harald Boegeholz
above, would result in extremely long words). The obvious way is to
calculate phi on the strong generators, and then express your g as a
word in the strong generators, which can be done very quickly.
It is easy to calculate phi on the strong generators, provided you do it
as you calculate them, since the new strong generators appear as words
in the existing ones. The problem is that these words are not remembered
by GAP, and so you need to recalculate the strong generators for every
homomorphism that you want to define. It would be more satisfactory if there
were a built-in method for remembering and reconstructing these words.

If GAP knows, that the object you defined is indeed an homomorphism, it
basically does the suggested procedure: It will construct a new stabilizer
chain for this homomorphism and represent the strong generators as words in
the given preimages. Applying the homomorphism should be fast afterwards,
I would suppose applying it to an element of M12 (unless the range involves
very hard computations) should take not more than a few seconds (at least
these are my experiences with groups that are even significantely larger
than M12).
If you set .isMapping and .isHomomorphism to true, GAP will just do this
evaluation process. Thus the easiest way to decompose a group element is
generator words via the stabilizer chain, probably is (in an abuse of
Homomorphisms:

f:=FreeGroup(n);
h:=GroupHomomorphismByGenerators(g,f,g.generators,f.generators);
h.idMapping:=true;h.isHomomorphism:=true; # this is not really true
Image(h,el); #yields word in generators

Strangely enough, the other --- proper --- way (i.e. mapping from the free
group to the group) seems to take longer (most likely, because it starts
computing the kernel first). Also GAP has quite difficulties
in that case to prove, that the mapping is an homomorphism if you don't tell
it so (though it is one by definition of a free group).

I should add one further observation to ease working with homomorphisms:
If your homomorphism corresponds to an operation, which is not obvious (i.e.
operation on an orbit), it may be helpful to use GroupHomomorphismByImages
instead of OperationHomomorphism, especially when computing preimages,
because running through a stabilizer chain is in general much faster, than
operation or even finding an element, that will yield the desired
operation.

Alexander Hulpke