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

Lecture 6

Lecturer: Igor Pak Scribe: C. Goddard

Probabilistic Generation

In this lecture, we will complete the classical proof for Dixon’s theorem on the probabilistic generation of S_{n}, based on the work by Erdős and Turán. Reiterating from the previous lectures, here is Dixon’s theorem: Theorem 1 (Dixon)

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

We will use Lemma 2, proved last lecture, and Jordan’s theorem (Theorem 3) and combine them with Lemma 4, proved here, to prove Dixon’s theorem (Theorem 1) classically. Thus, Lemma 2 and Jordan’s theorem are merely stated here: Lemma 2 (Erdős-Turán) Let 1 ≤ a_{1} < a_{2} < a_{r} ≤ n. Then

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

Theorem 3 (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}. Now continuing from the previous lecture, we will prove the following lemma. Lemma 4 (Erdős-Turán) For a fixed prime p (or prime power),

Pr(σ ∈ S_{n}, p ∤ order(σ)) = ∏_{i=1}^{⌊ \frac{n}{p} ⌋} (1 − \frac{1}{p · i})

Proof: Let

z_{λ} = \frac{n!}{1^{m_{1}} m_{1}! 2^{m_{2}} m_{2}! …} = # elements in conjugacy class (λ)

where λ = (1^{m_{1}}2^{m_{2}} …) and ∑ m_{i} · i = n. Now

1 = ∑_{λ⊢n} \frac{z_{λ}}{n!} = coeff [t^{n}] ∏_{i=1}^{∞} (1 + \frac{t^{i}}{1! · i} + \frac{t^{2i}}{2! · i^{2}} + \frac{t^{3i}}{3! · i^{3}} + …)
Pr(σ ∈ S_{n}, p ∤ order(σ)) = coeff [t^{n}] ∏_{i=1, p∤i}^{∞} (1 + \frac{t^{i}}{1! · i} + \frac{t^{2i}}{2! · i^{2}} + \frac{t^{3i}}{3! · i^{3}} + …)

Now denote Π = 1 + \frac{t^{i}}{1!·i} + \frac{t^{2i}}{2!·i^{2}} + \frac{t^{3i}}{3!·i^{3}} + …

So Π = ∏_{p∤i,i=1}^{∞} exp (\frac{t^{i}}{i} ) (since e^{x} = 1 + \frac{x}{1!} + \frac{x^{2}}{2!} + …)
= \begin{matrix}∏ & {∞ \atop i=1} & exp & (\frac{t^{i}}{i} ) \\ ∏ & {∞ \atop α=1} & exp & (\frac{t^{pα}}{pα} ) \end{matrix}
= exp (∑_{i=1}^{∞} \frac{t^{i}}{i} − ∑_{α=1}^{∞} \frac{t^{αp}}{αp} )
= exp (− log(1 − t) + \frac{1}{p} log(1 − t^{p})) (using − log(1 − x) = x + \frac{x^{2}}{2} + \frac{x^{3}}{3} + …)
= \frac{(1 − t^{p})^{\frac{1}{p}}}{1 − t}
= \frac{1 − t^{p}}{1 − t} · (1 − t^{p})^{\frac{1}{p} −1}
= \frac{1 − t^{p}}{1 − t} · (\frac{1}{1 − t^{p}} )^{1− \frac{1}{p}}
= (1 + t + … + t^{p−1}) · \{1 + ∑_{m=1}^{∞} t^{mp} · (1 − \frac{1}{p}) (1 − \frac{1}{2p}) · . . . · (1 − \frac{1}{mp})\}

(Note: (1 + x)^{α} = 1 + \frac{α}{1!}x + \frac{α(α−1)}{2!}x^{2} + …) So to find coeff[t^{n}], take m = ⌊\frac{n}{p}⌋ above, and we’re done. Now we are ready to prove Dixon’s theorem (Theorem 1). Proof: Pr(σ has p − cycle) ⟶ 1 as n → ∞, p < n − 2 . Let A = {log^{2} n < p < n − 2, p − prime}. Using Lemma 2, ⇒ Pr(σ has no A − cycles)

≤ \frac{1}{∑{n−2 \atop p=log^{2} n} \frac{1}{p}} ∼ \frac{1}{log log(n − 2) − log log(log^{2} n)}
(Using Euler’s theorem: ∑_{p<x} \frac{1}{p} ∼ log log x)
∼ c · (log log n)^{−1} where c is a constant

⇒ with Pr > 1 − \frac{c}{log log n} , ∃ p − cycle with p ∈ A for some prime p .

Lecture 6: 21 September 2001 3 Now from Lemma 4, since p > log^{2} n, we have:

Pr(σ contains exactly one p-cycle | σ contains at least one p-cycle) = ∏_{i=1}^{n−p} (1 − \frac{1}{p · i})

> exp (∑_{i=1}^{n} log (1 − \frac{1}{p · i})) = exp (− ∑_{i=1}^{n} \frac{1}{p · i} + o(1)) = exp (\frac{− log n + log p + o(1)}{p})

> exp (\frac{− log n}{p}) > exp (\frac{−1}{log n}) > 1 − \frac{1}{log n}

Finally, for the Pr as in Theorem 1, we obtain

Pr > (1 − \frac{c}{log log n}) (1 − \frac{1}{log n}) → 1 as n → ∞ ■