# Subgroup rank of symmetric group is about half the degree

## Contents

## Statement

Let be a natural number. Let be the symmetric group of degree , i.e., the symmetric group on a set of size . Then, the subgroup rank of is one of the numbers , , .

In particular:

- If is even, the subgroup rank of is .
- If , the subgroup rank of is .
- If is any odd positive integer other than 3, the subgroup rank of is .

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 has a generating set of size at most the subgroup rank, *and* there is at least one subgroup of for which the minimum size of generating set equals the subgroup rank.

## Particular cases

(order of symmetric group) | symmetric group of degree | 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 .
- 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 .

## Proof

### The easy part: finding subgroups where the maximum is attained

For simplicity, we take the symmetric group on the set .

**Case of even **: In this case, consider the subgroup:

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

**Case of **: In this case, the whole group has minimum size of generating set equal to 2.

**Case of odd ** (): In this case, consider the subgroup:

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