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) > epsilon for some epsilon > 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 otherwords, 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 -> infinity. The analysis is closely related to the following random set model. A random set M subset of Z(+) is generated by including each n >= 1 independently with probability 1. 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. (C) 2015 Wiley Periodicals, Inc.