Find some subgroups of the symmetric group $S_n$ having more than $k$ generators

Question

As I know the fact that the symmetric group $S_n$ ($n > 2$ to be safe) can be generated by 2 permutations (e.g. $\{(1 2), (1 ... n)\}$), I wonder whether there are any subgroups of $S_n$ that must be generated by larger-than-$k$ permutations ($k \ge 2$).

We can start with $k = 2$: can every subgroup of $S_n$ be generated by 2 permutations? By using a counting argument {$(n!)^2$ vs. the number of subgroups of $S_n$ which is $2^{\Theta(n^2)}$}, I roughly figure that probably there are some at-least-3-generated subgroups for large-enough $n$. Then the question becomes how to acquire such subgroup for each large-enough $n$ and how to prove that there is no such subgroup for the exceptions.

Answer 1

Let us say that a group is $k$-generated if it has a generating set with $k$ elements, whether or not it can be generated by fewer elements; and that the group is minimally $k$-generated if it is $k$-generated by cannot be generated by fewer than $k$ elements.

An easy observation is that for any $k$, $0\leq k\leq \lfloor\frac{n}{2}\rfloor$, $S_n$ has a subgroup $H_k$ that is minimally $k$-generated. Indeed, for such $k$, consider $$H_k = \langle (1,2),\ (3,4),\ (2k-1,2k)\rangle.$$ Since the transpositions are disjoint, this is an abelian subgroup of exponent $2$ and order $2^k$. So it is a vector space over $\mathbb{F}_2$ of dimension $k$, and in particular cannot be generated by fewer than $k$ elements. So $H_k$ is minimally $k$-generated.

One can check by inspection that $S_n$, $1\leq n\leq 5$, does not have any minimally $3$-generator subgroups (nor any subgroup that requires $4$-generators).

I would guess that this is best possible; that is, that any subgroup of $S_n$ can be generated by at most $\lfloor\frac{n}{2}\rfloor$ elements, but I do not have a proof.

Answer 2

The fact that there are no minimally $k$-generated subgroups of $S_n$ for $n>3$ and $k > \lfloor\frac{n}{2}\rfloor$ is proved in this paper by Cameron, Solomon, and Turull, but the proof there is attributed to Peter Neumann.

Perhaps surprisingly this proof makes essential use of the classification of finite simple groups. There is an elementary proof that all subgroups of $S_n$ are $(n-1)$-generated, but as far as I know that is the best that has been achieved without CFSG.

As requested, here is a quick proof of the $(n-1)$-generated claim. We prove the stronger statement that if $G$ has $k$ orbits on $\{1,2,\ldots,n\}$, then $G$ can be generated by at most $n-k$ elements. We prove this by induction on $n-k$. If $n-k=0$ then $G$ is trivial and requires no generators.

For $n-k>0$, let $\Omega$ be a nontrivial orbit of $G$ and $\alpha \in \Omega$. Suppose the stabilizer $G_\alpha$ has $t$ orbits, $s$ of which are subsets of $\Omega$. Then $s>1$ and $k \le t-s+1$. By inductive hypothesis $G_\alpha$ can be generated by $n-t$ elements.

For each of the $s-1$ orbits $\Omega_i$ of $G_\alpha$ in $\Omega$ other than $\{\alpha\}$, let $g_i$ be an element of $G$ mapping $\alpha$ to a point in $\Omega_i$. Let $H = \langle G_\alpha,g_1,\ldots,g_{s-1} \rangle$. So $H$ is generated by at most $n-t+s-1 \le n-k$ elements.

Also, since $\Omega$ is an orbit of $H$ and $G_\alpha \le H$, it follows from the Orbit-Stabilizer Theorem that $G=H$, which completes the induction.