1
$\begingroup$

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.

$\endgroup$
10
  • 3
    $\begingroup$ You can easily find subgroups that require any amount up to $\lfloor \frac{n}{2}\rfloor$: just take any $k$ from $(1,2), (3,4), \ldots, (n-1,n)$ if $n$ is even, up to $(n-2,n-1)$ if $n$ is odd. $\endgroup$ Sep 29, 2023 at 19:22
  • $\begingroup$ @ArturoMagidin Thanks! Do you have some ideas for the rest of cases? Esp. for large $k$ $\endgroup$ Sep 29, 2023 at 19:26
  • 2
    $\begingroup$ On the other hand, all subgroups of $S_4$ are either cyclic or $2$-generated; $S_5$ has subgroups generated by $3$ elements (isomorphic to $S_3\times C_2$), but no subgroup that requires $4$ generators. If $S_m$ has a subgroup requiring $k$ generators, then $S_{m+2}$ has a subgroup requiring $k+1$ generators. So $S_7$ has one requiring $4$, etc; that ups it to $\lfloor \frac{n}{2}\rfloor+1$ for odd $n$. $\endgroup$ Sep 29, 2023 at 19:26
  • 1
    $\begingroup$ A (necessarily abelian) group of exponent $2$ is a vector space over the field of order $2$, and a finite one has order $2^k$, which means it has dimension $k$; you cannot generate a vector space of dimension $k$ with fewer than $k$ elements. $\endgroup$ Sep 29, 2023 at 19:32
  • 1
    $\begingroup$ Note that every finite group is (isomorphic to) a subgroup of $S_n$ for some $n$, so if there are groups that need $1000$ generators, then, for some $n$, there's a subgroup of $S_n$ that needs $1000$ generators. $\endgroup$ Oct 7, 2023 at 9:31

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Derek Would you mind quickly outlining the proof of the $(n-1)$ statement? $\endgroup$ Oct 7, 2023 at 1:39
  • 1
    $\begingroup$ @VincentJ.Ruan I have appended the proof to my answer. $\endgroup$
    – Derek Holt
    Oct 7, 2023 at 9:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .