The Probability that some Power of a Permutation has Small Degree

Let S n be the symmetric group of degree n. In this paper we prove the following result THEOREM 1. Given £ > 0 and a with 0 < a < 1. Then n~ m <$ P{a e S n : minimal degree of {a) > n a } ^ n*" a as n-> oo. Here and throughout the paper <| denotes inequality with a positive constant independent of n (but perhaps depending on e or a). The concept of minimal degree (or class) is one of the oldest in permutation group theory (see 1.5 of Wielandt [5]). It was introduced by Jordan on account of his theorem [4]: Let b be a primitive permutation group of minimal degree m and of degree n. Then As an application of Theorem 1 we can get an improvement in the estimate (of Bovey and Williamson [1]) of the probability that two elements chosen at random from S n generate either A n or S n. In fact we prove THEOREM 2. Given e > 0, the proportion of ordered pairs {x, y) {x, y e S n) which generate either A n or S n is greater than 1 —n~ 1+e for all sufficiently large n. The result of Theorem 2 is close to being the best possible because Dixon [3] has shown that the proportion of pairs which generate a primitive subgroup of S n is 1 + n~ 1 + O(n~ 2) as n-* • oo. Before we can prove the main theorem we have to prove two lemmas. The first is a generalisation of [1] Lemma 4. LEMMA 1. Let Q be a subset of {1,2,..., n] with sup Q ^ n/logn. Define f{n,Q,k) to be the proportion of permutations a in S n containing exactly k q-cycles {q e Q). Then X k f(n,Q,k) =-e-* + O(n 5-lo * l °& n) where X = £ \/q.