[seqfan] Re: Symmetric group S_n as product of at most A225788(n) cyclic subgroups.
W. Edwin Clark
wclark at mail.usf.edu
Sat May 25 22:47:51 CEST 2013
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):
at the beginning matches the sequence a, and apparently is not in the OEIS
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
> >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
> >Case Western Reserve University
> 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/
More information about the SeqFan