Invariable generation of the symmetric group

Abstract

We say that permutations ${\pi }_1,\dots ,{\pi }_r\in {\mathcal{S}}_n$ invariably generate ${\mathcal{S}}_n$ if, no matter how one chooses conjugates ${\pi }_1^{\prime },\dots ,{\pi }_r^{\prime }$ of these permutations, ${\pi }_1^{\prime },\dots ,{\pi }_r^{\prime }$ generate ${\mathcal{S}}_n$. We show that if ${\pi }_1,{\pi }_2,{\pi }_3$ are chosen randomly from ${\mathcal{S}}_n$ then, with probability tending to 1 as $n\to \infty$, they do not invariably generate ${\mathcal{S}}_n$. By contrast it was shown recently by Pemantle, Peres and Rivin that four random elements do invariably generate ${\mathcal{S}}_n$ with positive probability. We include a proof of this statement which, while sharing many features with their argument, is short and completely combinatorial.

15 pages. Corrections and clarifications suggested by the referees. Added a reference to a paper of Raouj and Stef which solves related problems about divisors

References in corpus (1)

• Permutations fixing a k-set

Cited by in corpus (7)

• Irreducible polynomials of bounded height
• The characteristic polynomial of a random matrix
• Invariable generation of finite classical groups
• Divisibility of binomial coefficients and generation of alternating groups
• Almost all alternating groups are invariably generated by two elements of prime order
• Multiplicative arithmetic functions and the generalized Ewens measure
• On invariable generation of alternating groups by elements of prime and prime power order