[GAP Forum] size of permutation groups

[Allan Adler]

Thanks for telling me about IsNaturalPermutationGroup. To try it out,
I installed Gap4 and tested it on the examples I had already tried with
Gap3. It did them, but no faster. The way I did it with Gap3 was to
define the group g by giving it the explicit permutations of List([1..n])
that generate g and then by telling Gap to evaluate Size(g) to see whether
I got n!. I decided to check the source code for IsNaturalPermutationGroup
to see whether part of the algorithm involves first computing the size of
the group and it appears that it does. Therefore, IsNaturalPermutationGroup
can't improve on what I was already doing.

I realize that there might be some misunderstanding: any subgroup h of the
permutation group on n objects is a permutation group and
IsNaturalPermutationGroup is intended to detect whether h is isomorphic
to a permutation group on possibly fewer than n objects. Therefore, it might
well be, as Stefan said, that Gap was able to decide in 3 seconds that a
group of permutations on millions of objects is a natural permutation group,
but that natural permutation group might have been on a much smaller number
of objects than n. How long would it have taken to realize that a group
on millions of objects is the full symmetric group on all those millions
of objects?

Here is what I think might be more useful for my purposes: let x1,...xr be
permutations on List([1..n]), let g be the group they generate. I want to be
able to decide whether g is the full group of n! permutations on List([1..n]).
First, one needs a routine that decides whether g acts transitively on
List([1..n]) without actually computing the whole group or its order. If it
doesn't act transitively, it isn't the full symmetric group. If it does act
transitively, let h be the subgroup of g that fixes the last number n,
viewed as a group of permutations on List([1..n-1]). Then one needs a routine
that will take x1,...,xr and n and which will return an explicit set of
generators of h, again without computing all of h or its order. Then by
induction one tests whether g is n-point transitive. This procedure also
makes it possible to examine the generators of h at any stage of the
induction, which might also facilitate constructing proofs when
computation fails.

I don't know how efficiently one can compute the generators of h. Maybe it
is harder than computing the order of g. Also, I haven't looked at the
source code for Size(g). For all I know, it uses a variant of the method
I just described. In that case, I just have to modify the code for Size(g)
to make it print out information about h as it proceeds.

Of course, if it turns out not to be the full symmetric group on List([1..n]),
I'll want to know what it really is, but I'll cross that bridge when I come
to it. At the moment, I'm convinced that the class of examples I'm looking at
will always generate the full symmetric group on List([1..n]) and I just
need a way  to verify it in a number of cases.
-- 
Ignorantly,
Allan Adler <ara at zurich.csail.mit.edu>
* Disclaimer: I am a guest and *not* a member of the MIT CSAIL. My actions and
* comments do not reflect in any way on MIT. Also, I am nowhere near Boston.