> < ^ From:

> < ^ Subject:

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

> < [top]