# Generating symmetric groups with small cycles

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?

• 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. – Gerhard Paseman Nov 16 '17 at 19:43
• You mentioned the question on MSE, but I can't find it. Could you link to it? – LSpice Nov 20 '17 at 19:44
• @LSpice This one? – bof Nov 20 '17 at 20:44

## 2 Answers

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$.

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.

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