> < ^ Date: Tue, 08 Feb 1994 17:33:00 +0000
> < ^ From: Derek Holt <dfh@maths.warwick.ac.uk >
> < ^ Subject: Re: on permutation group "transversals".

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).

Unfortunately, it was not very useful for "practical" purposes :-):
For Rubik's Cube it produced words with an average length of about
500,000. It also needed quite some memory to compute those. But it
did produce solutions in finite time ;-).

If you are interested in the code (it will probably work better for
smaller groups), I can dig it out and mail it to you.

hwb
--
Harald Boegeholz | hwb@mathematik.uni-stuttgart.de
| os2a@info2.rus.uni-stuttgart.de

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.

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.

The particular situation in which I needed this was to calculate induced
representations from a subgroup H of G to G. The representation of
H is likely to be given on the generators of H, but to calculate the
induced representation, you need to be able to calculate its value on
lots of arbitrary elements of H. I solved this also by modifying
MakeStabStrong. Now it works very quickly for quite large examples.
I can supply the GAP functions to anyone who is interested.
(I happen also to know that Peter Webb did something similar for the
identical problem.)

Derek Holt.


> < [top]