[GAP Forum] size of permutation groups

[Jack Schmidt]

You should have no trouble with n=5,6,7,8,9.  Here is some code which 
constructs the permutations K and * on n! and checks if they generate 
the symmetric group of size (n!)!.  The code below runs in about one minute.

K:=function(perm,dom)
   return PermList(Concatenation(Reversed(Cycles(perm,dom))));
end;;

for n in [3..9] do
   Sn:=AsSet(SymmetricGroup(n));
   Kn:=PermListList(Sn,List(Sn,p->K(p,[1..n])));
   In:=PermListList(Sn,List(Sn,INV));
   Hn:=Group(Kn,In);
   Print(n,": ",IsNaturalSymmetricGroup(Hn),"\n");
od;

Outputs:
3: false
4: true
5: true
6: false
7: false
8: false
9: false

n=10 is also false, but took more in the 5 minute range. 3-8 is a few 
seconds, and 3-9 is about a minute.  These are on an 1.5ghz pc.

Allan Adler wrote:
> Maybe I should say what my examples are. In section 1.3.3 of Knuth's
> Art of Computer programming, Knuth mentions an unusual correspondence.
> One takes a permutation p on n letters, as a list of n values, the i-th
> value being p(i). E.g., consider 1435276. This has the cycle decomposition
> (1)(245)(3)(67). We rearrange the cycle decomposition so that each cycle
> begins with its smallest element and so that the cycles are listed in
> decreasing order of their first elements: (67)(3)(245)(1). Knuth then
> observes that one can safely remove the parentheses, since one can figure
> out where they were: 6732451. Furthermore, without the parentheses, it
> describes another permutation. So, basically, Knuth has defined a
> bijection from the symmetric group on n objects to itself. Denote
> that bijection K. I computed its orbits for a few values of n. On the
> other hand, let * denote the bijection of the symmetric group to itself
> which sends each permutation to its inverse. There are other nice
> bijections to play with, but I'm just starting with K and *. For n=3,
> K and * generate a group of order 72 on 6 = 3! objects. For n=4 and n=5
> they generate the full symmetric group of order n!! on n! objects. It is
> natural to speculate that this holds for all n > 3. I was computing
> examples and couldn't compute past n=5.
> 
> I wrote K and * as permutations on List([1..Factorial(n)]) using a
> C program I had written. Then I fed them to Gap3. Maybe it is convenient
> to work directly in Gap. Anyway, if someone would like to compute more
> examples, I'd be interested in their results.
> 
> I've written to Knuth to see if he has a reference for K. I've never seen
> it before. Maybe my speculation above is already someone's theorem?
> 
> Steve Linton wrote:
>> On my laptop this took 12 seconds for two random permutations of a million
>> points.
> 
> If your laptop can handle Group(K,*) for n up to 9 or 10, maybe I should
> offer to buy your laptop. :)