7
$\begingroup$

This was asked but never answered at MSE.

Let $S_n$ denote the symmetric group and let $H$ be a subgroup which contains an $n$-cycle. If $n$ is prime, and if $H$ also contains a 2-cycle, then necessarily $H = S_n$. However, this property does not hold in general which raises the question of how many additional cycles are required to restore the conclusion.

Define $f(n)$ to be the smallest integer such that whenever (in addition to the $n$-cycle) $H$ contains cycles of length $2,3,4,\dotsc,f(n)$, then $H$ must be equal to the full symmetric group $S_n$. Note that only the cycle lengths are specified and not the entries. It is known that all cycle lengths do suffice to generate $S_n$. Therefore, $f(n)$ is well defined and takes values in the range $2 \le f(n)\le n-1$. For example, $f(3)=2$ either directly or by noting that 3 is prime. However, $f(4) \neq 2$ because the proper dihedral subgroup has cycles both of length $2$ and $4$. So we get $f(4)=3$ instead (max possible value).

Next consider the even case $n = 2m$. $S_{2m}$ has a wreath product subgroup $S_m\wr S_2$ of order $2(m!)^2$. This not only contains all cycle lengths from 2 up through $m$ but also a full length $2m$-cycle. All of which implies that $f(2m) \ge m+1$ and shows not only that $f(n)$ is unbounded but also that it can exhibit arbitrarily large jumps [e.g., $f(101)=2$ vs. $f(102)\ge52$].

Questions: (1) For which $n$ besides $n=3$ and $n=4$ do we get the maximum value $f(n) = n-1$?

(2) What is the set of values taken on by $f(n)$ as $n$ ranges over the natural numbers? For large $n$, does $f(n)$ vary with number theoretic irregularity or does it settle into predictable patterns?

$\endgroup$
  • $\begingroup$ Actually, if there is an n cycle and another cycle of different length k , those generate roughly n more k cycles, and now two of the k cycles usually generate an element of order different from n or k. Note that n does not have to be prime. In most cases you will get the alternating group or the whole group. I believe this probability has been calculated, but I have no references. Gerhard "Start With Krohn Rhodes Perhaps?" Paseman, 2017.11.16. $\endgroup$ – Gerhard Paseman Nov 16 '17 at 19:43
  • $\begingroup$ You mentioned the question on MSE, but I can't find it. Could you link to it? $\endgroup$ – LSpice Nov 20 '17 at 19:44
  • 1
    $\begingroup$ @LSpice This one? $\endgroup$ – bof Nov 20 '17 at 20:44
3
$\begingroup$

Let $p$ be the smallest prime divisor of $n$. I believe that $f(n)=n/p+1$. The key points are as follows.

1) If $H \leq S_n$ is primitive and contains a $2$-cycle, then $H=S_n$.

2) If $1<k \leq m<n$ and $m$ divides $n$, then every $k$-cycle in $S_n$ preserves a partition of $[n]$ into $n/m$ subsets of size $m$.

3) If $1<m<n$ and $m$ divides $n$, then an $(m+1)$-cycle in $S_n$ does not preserve any partition of $[n]$ into $n/m$ parts of size $m$.

So, a collection of cycles whose lengths are $2,n$ and $d+1$ for each nontrivial proper divisor $d$ of $n$ always generates $S_n$. On the other hand, there exists a collection of cycles whose lengths are $n,2,3,\ldots,n/p$, all preserving a partition of $[n]$ into $p$ parts of size $n/p$.

$\endgroup$
2
$\begingroup$

It is a theorem of Jordan (I believe), that a primitive subgroup of the symmetric group $S_n$ which contains a $p$-cycle for $p< n-2$ contains the alternating group. Now, your group contains an $n$-cycle, so it is transitive, so if it contains a $p$-cycle for any $n/2< p < n-1$ as well as a cycle of even length, then you are golden. This shows that $f(n) < n-1$ for $n$ big enough.

$\endgroup$
  • $\begingroup$ That $<=$ should be $<$. $\endgroup$ – Nick Gill Nov 20 '17 at 17:16

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.