Subgroup rank of symmetric group is about half the degree

Statement

Let $n$ be a natural number. Let $G$ be the symmetric group of degree $n$, i.e., the symmetric group on a set of size $n$. Then, the subgroup rank of $G$ is one of the numbers $n/2$, $(n-1)/2$, $(n+1)/2$.

In particular:

• If $n$ is even, the subgroup rank of $G$ is $n/2$.
• If $n=3$, the subgroup rank of $G$ is $2$.
• If $n$ is any odd positive integer other than 3, the subgroup rank of $G$ is $(n-1)/2$.

The subgroup rank is defined as the maximum, over all subgroups, of the minimum size of generating set of that subgroup. In particular, this means that every subgroup of $G$ has a generating set of size at most the subgroup rank, and there is at least one subgroup of $G$ for which the minimum size of generating set equals the subgroup rank.

Particular cases

$n$	$n!$ (order of symmetric group)	symmetric group of degree $n$	subgroup rank
1	1	trivial group	0
2	2	cyclic group:Z2	1
3	6	symmetric group:S3	2
4	24	symmetric group:S4	2
5	120	symmetric group:S5	2
6	720	symmetric group:S6	3
7	5040	symmetric group:S7	3

Related facts

• Jerrum's filter gives an algorithmic method for finding a Jerrum-reduced generating set for any subgroup, and such a generating set must have size at most $n-1$.
• Sims filter gives an algorithmic method for finding a Sims-reduced generating set for any subgroup, and such a generating set must have size at most $n(n-1)/2$.

Proof

The easy part: finding subgroups where the maximum is attained

For simplicity, we take the symmetric group on the set $\{1,2,3,\dots ,n\}$.

Case of even $n$: In this case, consider the subgroup:

$\langle (1,2),(3,4),\dots ,(n-1,n)\rangle$

This is an elementary abelian group of rank $n/2$, so its minimum size of generating set is also $n/2$.

Case of $n=3$: In this case, the whole group has minimum size of generating set equal to 2.

Case of odd $n$ ($n\neq 3$): In this case, consider the subgroup:

$\langle (1,2),(3,4),\dots ,(n-2,n-1)\rangle$

This is an elementary abelian group of rank $(n-1)/2$, so its minimum size of generating set is also $n/2$.