Shortlisted Problems for the Romanian NMO

Let $n\ge 3$ and let $m$ be the exponent of $2$ in the prime factorization of $n!$. Recall that the order of $S_n$ is $n!$, so $2^m$ divides $|S_n|$.

We will exhibit at least three subgroups of $S_n$ of order $2^m$.

First, consider the Sylow $2$-subgroups of $S_n$. By Sylow's theorems, the number of Sylow $2$-subgroups is congruent to $1$ modulo $2$ and divides $n!/2^m$. In particular, there is at least one Sylow $2$-subgroup of order $2^m$.

We will construct three explicit subgroups of order $2^m$:

1. The subgroup $H_1$ consisting of all permutations of $S_n$ that permute the first $k$ elements, where $k$ is the largest power of $2$ less than or equal to $n$. That is, $H_1$ is isomorphic to $S_k$, and the $2$-part of $k!$ is maximized. However, to ensure order $2^m$, we need to consider the actual Sylow $2$-subgroups.

2. The subgroup $H_2$ consisting of all permutations that permute a different set of $k$ elements (for example, the last $k$ elements), again forming a subgroup isomorphic to $S_k$.

3. The subgroup $H_3$ can be constructed as follows: Consider the direct product of $S_2\times S_2\times \cdots \times S_2$ ($\lfloor n/2\rfloor$ times), embedded in $S_n$ as the group generated by disjoint transpositions. This subgroup is an elementary abelian $2$-group of order $2^{\lfloor n/2\rfloor }$, but for $n\ge 3$, the Sylow $2$-subgroups are not all conjugate to this one, and the actual Sylow $2$-subgroups are more complicated, but there are at least three such subgroups by the following argument.

Alternatively, note that the number of Sylow $2$-subgroups is greater than $1$ for $n\ge 3$ (since $n!/2^m$ is even for $n\ge 3$), and by Sylow's theorem, the number is congruent to $1$ modulo $2$ and divides $n!/2^m$. Therefore, there are at least three Sylow $2$-subgroups of $S_n$ of order $2^m$.

Thus, $S_n$ has at least three subgroups of order $2^m$.