Four random permutations conjugated by an adversary generate S_n with high probability

We prove a conjecture dating back to a 1978 paper of D.R. Musser [11], namely that four random permutations in the symmetric group S_n generate a transitive subgroup with probability p_n > ε for some ε > 0 independent of n, even when an adversary is allowed to conjugate each of the four by a possibly different element of S_n. In other words, the cycle types already guarantee generation of a transitive subgroup; by a well known argument, this implies generation of A_n or S_n except for probability 1 + o(1) as n → ∞. The analysis is closely related to the following random set model. A random set M ⊆ Z + is generated by including each n ≥ 1 independently with probability 1/n. The sumset sumset(M) is formed. Then at most four independent copies of sumset(M) are needed before their mutual intersection is no longer infinite.