> < ^ From:

> < ^ Subject:

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]