[GAP Forum] size of permutation groups

[Stefan Kohl]

Dear Forum,

Allan Adler wrote:

> I'm using Gap 3 on a PC running RH 7.1 Linux. Using it, I took a couple
> of permutations on a little over 100 objects and had no trouble, after
> waiting long enough, getting Gap 3 to confirm that they generated the
> entire symmetric group. I tried the same thing with some permutations
> on several hundred objects and, after 5 hours of waiting for Gap 3 to
> compute the order of the group, I gave up and stopped the program.
> 
> What I'd like to know is the following:
> (1) How large can n be for me to do stuff like this with the symmetric
>     group on n objects and expect the program to run to completion?

In GAP 4, there is an operation `IsNaturalSymmetricGroup', which does
this for degrees until up into the millions. For degree 100000 and two
random generators, it takes just about 3 seconds for me.

There is also a similar operation `IsNaturalAlternatingGroup' which
checks whether the argument is a natural alternating group.

Both checks are algorithmically `easy'.

The GAP implementation follows the description given in Section 10.2 of

Akos Seress, Permutation group algorithms. Cambridge Tracts in
Mathematics, 152. Cambridge University Press, 2003.

Easy-to-check criteria for deciding whether given permutations generate
the full symmetric group can also be found in

John D. Dixon and Brian Mortimer, Permutation Groups, Graduate Texts
in Mathematics, 163. Springer-Verlag, 1996.

After having used `IsNaturalSymmetricGroup' or `IsNaturalAlternatingGroup',
GAP can often choose better methods for subsequent computations with the
same group.

Hope this helps,

     Stefan Kohl

---------------------------------------------------------------------------
http://www.cip.mathematik.uni-stuttgart.de/~kohlsn/
---------------------------------------------------------------------------