[seqfan] Re: Symmetric group S_n as product of at most A225788(n) cyclic subgroups

[W. Edwin Clark]

Two OEIS editors have ask to see my GAP program for computing the smallest
integer k
such that S_n = C_1*C_2*...*C_k  where the C_i are cyclic subgroups of S_n.
At present I only have a clumsy program which doesn't deserve publication
in the OEIS.

In  hopes that someone can improve my program, I present it  below.

It is a GAP program that one can use to determine whether or not S_n is
a product of k = 3 cyclic groups. One can alter it to work for k = 2 or 4,
or whatever, by changing the
number of do loops. Below the program is the output for S_n, n = 3,4,5,6.
If you want to
wait a bit you can also do n = 7.  For example, the output:

5, Group( [ (1,2,3)(4,5) ] ), Group( [ (1,2)(3,4,5) ] ), Group( [
(1,2,4,5,3) ] ) ,3

means that S_5 is the product of the cyclic groups with generators
(1,2,3)(4,5), etc.

Using this program (with the necessary alterations) one can determine the
values
             1,1,2,3,3,4,4
 for n from 1 to 7.

[Note that  we can assume that C_1 is generated by some representative of
the p(n) conjugacy
classes of S_n. p(n) is much smaller than the number of distinct cyclic
subgroups of S_n <https://oeis.org/A051625>--
of which C_i, for  i > 1, can be any one. However I guess one can perhaps
eliminate some, for
example, if  n_i = order(C_i) then the product n_1*n_2*...*n_k must be at
least n!.  But I didn't
try that. (small project: find the number of k-tuples (n_1,...,n_k) where
n_i is the order of a
cyclic subgroup of S_n and n_1*n_2*...*n_k >=n!.) ]



prod:=function(s,t)
local u,i,j;
u:=[];
for i in s do
for j in t do
  Add(u,i*j);
od;
od;
return Set(u);
end;;

prod2:=function(V)
local n,a,i;
n:=Length(V);
if n = 2 then return prod(V[1],V[2]); fi;
a:=prod(V[1],V[2]);
for i in [3..n] do
 a:=prod(a,V[i]);
od;
return a;
end;;

FindGenerator:=function(u)
local x,n;
n:=Length(u);
for x in u do
 if Order(x) = n then return x; fi;
od;
end;;

for n in [3..6] do
 g:=SymmetricGroup(n);;
  v:=Elements(g);;
  ee:=Filtered(Elements(g), t->Order(t)>1);;
  CC:=ConjugacyClasses(g);;
  RC:=List(CC,Representative);;
  RC:=Filtered(RC,t->Order(t)>1);;
  SRC:=List(RC,t->Elements(Subgroup(g,[t])));;
  Sort(SRC,function(y,z) return Length(y) >= Length(z); end );
  CyclicSubgroups:=[];;
  for x in ee do
    S:=Subgroup(g,[x]);
    u:=Elements(S);
    Add(CyclicSubgroups,u);
  od;;
CyclicSubgroups:=Set(CyclicSubgroups);;
Sort(CyclicSubgroups,function(y,z) return Length(y) >= Length(z); end );
flag:=false;;
 for a in SRC do
  for b in CyclicSubgroups do
     for c in CyclicSubgroups do
       U:=[a,b,c];;
       if Length(prod2(U)) = Factorial(n) then
Print(n,",",List(U,t->Group(FindGenerator(t))),",",Length(U),"\n");flag:=true;
break; fi;
     od;
     if flag=true then break; fi;
   od;
   if flag= true then break; fi;
  od;
  if flag = false then Print(n,",",Length(U), " do not suffice \n"); fi;
od;

# output as follows:

3,[ Group( [ (1,2,3) ] ), Group( [ (1,2,3) ] ), Group( [ (1,3) ] ) ],3
4,[ Group( [ (1,2,3,4) ] ), Group( [ (1,3,2,4) ] ), Group( [ (1,2,4,3) ] )
],3
5,[ Group( [ (1,2,3)(4,5) ] ), Group( [ (1,2)(3,4,5) ] ),
  Group( [ (1,2,4,5,3) ] ) ],3
6,3 do not suffice