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

Lecture 3

Lecturer: Igor Pak Scribe: T. Chiang

Probabilistic Generation

In this lecture, we will prove the following Theorem with contemporary mathematics:

Theorem 1 (Dixon)

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

We first recall that a simple group G is a group with no proper normal subgroups. Let G be simple; then the following proposition is valid:

Proposition 2

φ_{k}(G) ≤ 1 − ∑_{M} \frac{1}{[G : M]^{k}} = 1 − ∑_{M⊂μ} \frac{1}{[G : M]^{k−1}} ,  (2)

where M is a maximal subgroup of G and μ is the conjugacy classes of M.

Proof: It is clear that 1 − φ_{k}(G) ≤ ∑_{M} \frac{1}{[G:M]^{k}}. Now, because M is the maximal subgroup of G, we can define N_{G}(M) as the maximal subgroup of G such that M ◁ G. The only solution must be in the set {M, G}, and since G is simple, this implies that N = M. Now if we define the term M^{G} = gMg^{−}1 as the conjugacy class of M, we can readily verify that |\{M^{G}\}| = \frac{|G|}{|N_{G}(M)|} = [G : M].

Theorem 3 (O’nan -Scott) Let G ⊂ S_{n} be primitive. Then G is

A. Affine B. Product Type C. Diagonal Type D. Almost Simple

Proof: Implicit from the Classification of Finite Simple Groups.

From here we deduce Theorem 1.

Proof: We begin with some Group Theoretic terminology. First we suppose that G ⊂ S_{n} and that G = {σ_{1} … σ_{k}}. We call a group G - transitive if ∀i, j ∈ {i … n} then there exists an element σ ∈ G such that σ(i) = j. Next we call a group G - primitive if the following occur:

(R_{1})(R_{2}) ⋯ (R_{m})

where |R_{i}| = d and n = md so that ∀σ ∈ G; ∀i, j ∈ R_{α}, there exists β : σ(i), σ(j) ∈ R_{β}. Now if we use the O’nan-Scott Theorem with these two facts, we see that the 4 properties of G are exactly the conjugacy classes which gives us the proof to the theorem.

We also give another Theorem concerning the number of conjugacy classes of the maximal subgroups of S_{n}.

Theorem 4 (Liebeck-Shalev) The number of conjugacy classes of maximal subgroups of S_{n} is of the order: \frac{n}{2}(1 + O(1)).

From here we can also deduce Theorem 1 :

Proof: First we preface the proof by noting that the maximal subgroups of S_{n} are of the form S_{k} × S_{n−k} for k ≤ \frac{n}{2}. First we see that

φ_{2}(A_{n}) ≥ 1 − ∑_{M⊂μ} \frac{1}{[G : M]}

= 1 − ∑_{k=1}^{⌊ \frac{n}{2} ⌋} \frac{1}{\binom{n}{k}} + O(\frac{1}{e^{cn}})

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

We end this lecture with an example and a corollary.

Suppose that G = P SL(2, p) - simple. Then

|G| = \frac{1}{2(p − 1)}(p^{2} − 1)(p^{2} − p) = \frac{p(p − 1)(p + 1)}{2}.  (3)

Now if H is a maximal subgroup in P SL(2, p), then H has the form

H = \{(\begin{matrix}a b \\ 0 c \end{matrix}) : ac = 1\}  (4)

Thus |H| = \frac{p(p−1)}{2}. So we see that [G : H] = p + 1 which is roughly p. It was never shown, but is told to be true that the number of conjugacy classes of maximal subgroups is ≤ 7 when the index ≥ p. Hence φ_{2} > 1 − \frac{7}{p}.

Corollary 5 As p → ∞, φ_{2} (P SL(2, p)) → 1.