18.317 Combinatorics, Probability, and Computations on Groups 14 September 2001

Lecture 4

Lecturer: Igor Pak Scribe: Ben Recht

Even if a paper is famous and written by very famous individuals, that does not necessarily mean that it is correct. In this lecture, we will look at a proof of the probabilistic generation of S_{n} by Dixon, based on results of Erdős and Turan. Then we discuss the lemmas which they proved incorrectly in their paper.

Our goal will be to prove

Theorem 1

P r(⟨σ_{1}, σ_{2}⟩ = A_{n} or S_{n} ) → 1 as n → ∞

The idea of the proof is a follows. First we will prove that the probability that ⟨σ_{1}, σ_{2}⟩ is primitive goes to 1 as n goes to infinity. Next, we can show that the probability that ⟨σ_{1}, σ_{2}⟩ contains a cycle of length p, where p is a prime less than n − 3 also goes to 1 as n goes to infinity. Then the theorem follows immediately by the following result of Jordan

Theorem 2 (Jordan 1873) If G ≤ S_{n} is primitive and contains a cycle of length p where p is a prime less than n − 3 the G is equal to A_{n} or S_{n}.

The proof of Jordan’s theorem can be found in many classic texts on group theory.

We’ll proceed with the following

Lemma 3 P r(⟨σ_{1}, σ_{2}⟩ is transitive) = 1 − \frac{1}{n} + O(\frac{1}{n^{2}} )

Proof: Let p = P r(⟨σ_{1}, σ_{2}⟩ is transitive). Then

1 − p < ∑_{k=1}^{n/2} \binom{n}{k}P r(σ_{1} and σ_{2} fix blocks of size k and n − k)

= ∑_{k=1}^{n/2} \binom{n}{k}\frac{1}{\binom{n}{k}2}

= ∑_{k=1}^{n/2} \frac{1}{\binom{n}{k}}

= \frac{1}{n} + O(\frac{1}{n^{2}} )

We’ll now prove a result about when ⟨σ_{1}, σ_{2}⟩ is primitive.

Theorem 4 P r(⟨σ_{1}, σ_{2}⟩ is imprimitive) = O(\frac{n}{2^{n/4}} )

Proof: The probability that σ has a fixed block structure with block size d (md = n) is equal to \frac{d!^{m}m!}{n!} as we can permute the blocks and the elements within the blocks. The number of block structures with block size d is equal to

\frac{\binom{n}{d...d}}{m!} = \frac{n!}{d!^{m}m!} .

Here is is clear that the multinomial coefficient is over m d’s.

Now

P r(⟨σ_{1}, σ_{2}⟩ is imprimitive) < ∑_{d|n} \frac{n!}{d!^{m}m!} (\frac{d!^{m}m!}{n!})^{2}

< ∑_{m=2}^{n/2} \frac{(\frac{n}{m})!^{m}m!}{n!}

= \frac{(n/2)!2^{n}}{n!} + … + \frac{2!(n/2)!^{2}}{n!}

The last term in this sum is a dominating term, there are n/2 such terms and \binom{n}{n/2} > 2^{n/2}, thus completing the proof.

Corollary 5 P r(⟨σ_{1}, σ_{2}⟩ is primitive ) = 1 − \frac{1}{n} + O(\frac{1}{n^{2}} )

We now will attempt to prove

Theorem 6 Let σ ∈ S_{n} and p be a prime less than n − 2. Then P r(σ = σ_{p} ∏_{i} γ_{i}), where σ_{p} is a p-cycle and γ_{i} are c_{i}-cycles with p ∤ c_{i}, goes to 1 as n goes to infinity.

This result will imply Dixon’s theorem. To prove this result, we will prove the following two lemmas next time.

Lemma 7 (Erdős -Turan) Let 1 ≤ a_{1} ≤ a_{2} ≤ a_{r} ≤ n. Then

P r(σ ∈ S_{n} does not contain any cycles of length a_{i}) ≤ ∑_{i=1}^{r} \frac{1}{a_{i}} .

Lemma 8 Let σ ∈ S_{n} and p < n be a prime. Then P r(p ∤ order(σ)) = ∏_{k=1}^{n/p}(1 − \frac{1}{pk}).

Erdős and Turan published a famous proof of these lemmas. We will construct correct proofs in the next lecture.