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

[W. Edwin Clark]

On Sun, May 26, 2013 at 9:15 AM, Richard J. Mathar <mathar at mpia-hd.mpg.de>wrote:

> On a mximum bound of the shortest cyclic subgroup factorization in
> http://list.seqfan.eu/pipermail/seqfan/2013-May/011212.html :
>
> The order of the symmetric group is n!. If we whish to write
> this as a product of cyclic subgroups, with subgroups of order
> m1, m2, m3 etc, the product m1*m2*.. should be n! .
>

Well, m1*m2*...  should be at least n!  --but, I see no reason that if
S_n = C_1*C_2*..*.C_k  where C_i is cyclic of order m_i,
that if g in S_n has the form g = a_1*a_2*...*a_k , a_i in C_i, then
the a_i's should  be unique.  In fact, as an example, one smallest
factorization of S_7 is given by C_1*C_2*C_3*C_4 where

C_1 = <(1,2,3,4)(5,6,7)>  which has order 12
C_2 = <(1,4,6)(2,3,5,7)>  which has order 12
C_3 = <(1,2,5,7)(3,4,6)>  which has order 12
C_4 = <(1,3,5,6,7)(2,4)>  which has order 10

and 12*12*12*10 =17280  is not equal to 7! = 5040.

Further, to the point by Ed Jeffry, it is not too hard to prove that
for a(n) = least k such that S_n is a product of k cyclic groups
that we have a(n+1) <= a(n) + 1.

But is it true that a(n) <= a(n+1)?  Can anyone see how to prove that?
If so then a(n+1) = a(n) or a(n)+1. So one "only" has to find where the
jumps are.

By the way the lower bound I mentioned of b(n) = log[m](n!), m = A000783(n).
I should have written b(n) = ceil(log[m](n!)) and this sequence is not
non-decreasing.
Here are the first few terms.

      1,1,2,3,3,4,4,4,5,5,6,5,6,6,6,7,7,7,7,8,8,9,8,9,9,9,9,9,10,

..And neither is the sequence A000783(n) = maximal order of an element of
S_n.
So it  is conceivable that a(n) <= a(n+1) does not always hold.

--Edwin