[seqfan] Re: Symmetric group S_n as product of at most A225788(n) cyclic subgroups
W. Edwin Clark
wclark at mail.usf.edu
Sun May 26 17:39:58 CEST 2013
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
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
Here are the first few terms.
..And neither is the sequence A000783(n) = maximal order of an element of
So it is conceivable that a(n) <= a(n+1) does not always hold.
More information about the SeqFan