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

[W. Edwin Clark]

Concerning the sequence a(n) = smallest k such that the symmetric group S_n
is a product of  k cyclic subgroups:

I calculate that for n from 1 to 7 we have a = 1,1,2,3,3,4,4. I used GAP
and a more or less brute force approach. Perhaps someone can do better?
The computation depends on the number of distinct cyclic subgroups of S_n
--given by http://oeis.org/A051625  Note that for n = 8 there are 14170
cyclic subgroups. Using the fact that we can fix one of the cyclic
subgroups to be generated by an element in one of the p(8) = 15 conjugacy
classes of S_8, this still means that to prove that a(8) is not 4 (see
lower bound below) requires checking possibly 15*14170^3  = 42677680695000
products  of  4 cyclic subgroups of S_8.  Or am I missing something?

Using the idea in the paper by Miklos Abert  mentioned in A225788 it is
easy to see that if m is the maximal order of an element of of S_n (
http://oeis.org/A000793 ) then m^a(n) >= n! and hence a(n) >= log[m](n!).

The sequence log[m](n!), m = A000783(n):
      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,
at the beginning matches the sequence a, and apparently is not in the OEIS

--Edwin

On Thu, May 23, 2013 at 8:22 PM, L. Edson Jeffery <lejeffery2 at gmail.com>wrote:

> >On Thu, May 23, 2013 at 3:58 PM, Charles Greathouse <
> charles.greathouse at case.edu> wrote:
> >
> >I think the sequence can be defined unambiguously: Smallest k such that
> the
> >symmetric group S_n is a product of at most k cyclic subgroups. I would
> >love to see this sequence in the OEIS. Do we have any GAP experts who can
> >code this up?
> >
> >Charles Greathouse
> >Analyst/Programmer
> >Case Western Reserve University
>
> Charles,
>
> In retrospect, the definition "a(n) = least k such that the symmetric group
> S_n is a product of k cyclic subgroups" might be a better one (if the
> sequence can be determined) because of the following. For this idea, Abért
> gave the lower bound of (1 + o(1))*(n*log(n))^(1/2) cyclic subgroups.  But
> for the upper bound (A225788) he pointed out the "obvious decomposition"
>
> S_n = [(1,2,...,n)][(1,2,...,n-1)]...[(1,2)]
>
> of S_n as a product of n-1 cyclic subgroups (replace the brackets [] with
> angled ones). Although I don't claim to understand all of this to any great
> depth, it appears that your idea for the sequence would reduce to just a(n)
> = n-1 which unfortunately does not seem terribly interesting. Can you use
> the above lower bound to produce another sequence like A255788?
>
> Ed Jeffery
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>