On the maximal number of elements pairwise generating the symmetric group of even degree (Q2075524): Difference between revisions

It is well known that the symmetric group \(S_n\) on \(n\) letters can be generated by two elements. Denote by \(\omega(S_n)\) the maximal size of a subset \(S \subseteq S_n\) such that \(\langle x, y \rangle = S_n\) for any distinct elements \(x,y\) of \(S\), and denote by \(\sigma(S_n)\) the minimal size of a set of proper subgroups of \(S_n\) whose set theoretic union is \(S_n\). It is not difficult to prove that \(\omega(S_n) \leqslant \sigma(S_n)\); however, exact values of these two invariants are extremely difficult to calculate in general. (Indeed, exact results for \(\sigma(S_n)\) are known only when \(n\) is odd or divisible by \(6\), and exact results for \(\omega(S_n)\) are known only when \(n\) is odd and at least \(17\).) The purpose of this paper is to study the relationship between these two invariants when \(n\) is even. The authors prove that \(\omega(S_n)\) and \(\sigma(S_n)\) are both asymptotically \(\frac{1}{2}\binom{2n}{n}\) when \(n\) is even, and, in fact, \(\sigma(S_n)/\omega(S_n) \to 1\) as \(n \to \infty\). Furthermore, the authors prove related results about sets of elements of \(S_n\) that pairwise generate at least \(A_n\) and also provide CFSG-free lower bounds for \(\omega(S_n)\). The proofs are probabilistic in nature and rely on the Lovász local lemma.