18.23 (2014)

The normal covering number of the symmetric group $S_n$ of degree $n$ is the minimum number $\gamma(S_n)$ of proper subgroups $H_1, \dots, H_{\gamma(S_n)}$ of $S_n$ such that every element of $S_n$ is conjugate to an element of $H_i$, for some $i = 1, \dots, \gamma(S_n)$. Write $n = p_1^{\alpha_1} \cdots p_r^{\alpha_r}$ for primes $p_1 < \dots < p_r$ and positive integers $\alpha_1, \dots, \alpha_r$.

Conjecture:
$$\gamma(S_n) = \begin{cases} \frac{n}{2}(1 - \frac{1}{p_1}) & \text{if } r = 1 \text{ and } \alpha_1 = 1 \\ \frac{n}{2}(1 - \frac{1}{p_1}) + 1 & \text{if } r = 1 \text{ and } \alpha_1 \geqslant 2 \\ \frac{n}{2}(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) + 1 & \text{if } r = 2 \text{ and } \alpha_1 + \alpha_2 = 2 \\ \frac{n}{2}(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) + 2 & \text{if } r \geqslant 2 \text{ and } \alpha_1 + \dots + \alpha_r \geqslant 3 \end{cases}$$

This is the strongest form of the conjecture. We would be also interested in a proof that this holds for $n$ sufficiently large. The result for $r \leqslant 2$, which includes the first three cases above, is proved for $n$ odd (D. Bubboloni, C. E. Praeger, J. Combin. Theory (A), 118 (2011), 2000–2024). When $r \geqslant 3$ we know that $cn \leqslant \gamma(S_n) \leqslant \frac{2}{3}n$ for some positive constant $c$ (D. Bubboloni, C. E. Praeger, P. Spiga, J. Algebra, 390 (2013) 199–215). We showed that the conjectured value for $\gamma(S_n)$ is an upper bound, by constructing a normal covering for $S_n$ with this number of conjugacy classes of maximal subgroups, and gave further evidence for the truth of the conjecture in other cases (D. Bubboloni, C. E. Praeger, P. Spiga, Int. J. Group Theory, 3, no. 2 (2014), 57–75).