18.317 Combinatorics, Probability, and Computations on Groups 30 October 2001

Lecture 31

Lecturer: Igor Pak Scribe: D. Jacob Wildstrom

Bias (continued)

Theorem 1 (P. Hall). For a simple group H and G = H^{m}, it follows that ⟨g_{1}, …, g_{k}⟩ = G if and only if ⟨h_{j}^{(1)}, h_{j}^{(2)}, …, h_{j}^{(k)}⟩ = H for all j from 1 to m.

We shall henceforth work with H = A_{n}, m = \frac{n!}{8}, κ = o(n), G = H^{m}, and Q = Q_{k}, which to refresh our memory, is simply the probability distribution of g_{1} in ḡ = (g_{1}, g_{2}, …, g_{k}) ∈ Γ_{k}(G).

Theorem 2. There is a subset B of G such that, as n → ∞, \frac{|B|}{|G|} → 1 but Q(B) → 0.

That is to say that there is a huge subset (approaching the full set) of G which is hardly ever generated by a k-tuple of generators.

We claim that, roughly, if k ≥ k, then the values of h_{j} = (h_{j}^{(1)}, h_{j}^{(2)}, …, h_{j}^{(k)}) are independent.

Then we have the lemma:

Lemma 3. |Γ_{k}(o)| = |Γ_{k}(H)|^{m}|(1 − O(\frac{1}{n!})).

Proof: The number of automorphisms of Γ_{k}(H) is, as we discussed earlier, α_{k}(G), which must exceed \frac{H^{k}}{2| Aut(H)|} = \frac{1}{2} \frac{( \frac{n}{2} )^{k}}{n!} = N. Now, |Γ_{k}(G)| is equal to the product of |Γ_{k}(H)|^{m} and the probability that each generated k-tuple is in a distinct orbit. This we can easily calculate to be (1 − \frac{1}{N})(1 − \frac{2}{N}) ⋯ (1 − \frac{m}{N}), which exceeds (1 − \frac{m}{N})^{m} and thus (1 − \frac{m^{2}}{N}). Using the equation m = \frac{n!}{8} and N ≥ \frac{(n!)^{3}}{32} , the above factor can be easily shown to exceed 1 − \frac{1}{2n!}

Let A_{n} be generated by (h_{1}^{1}, h_{1}^{2}, …, h_{1}^{k}). We know that with probability ≈ \frac{1}{n} (specifically, \frac{1}{n} ± \frac{1}{n^{3}} ), h_{1}^{1} moves the first element. What would the specific probability tell us about g_{1}?

We start by looking at ϕ_{k}(A_{n}), which would be 1 minus the probability of “bad events”. What sort of “bad events” might we have in mind? They can be characterized by h_{1}, …, h_{k} ∈ M for some maximal subgroup M of H. There are really only 3 types of maximal subgroups in H: those with one fixed point, those with a pair of elements forming an orbit, and those with two fixed points. The probability of generating any of these is easily calculated:

ϕ_{k}(A_{n}) = 1 − \frac{1}{n^{k}} n − \frac{1}{n(n − 1)^{k}} \binom{n}{2} + \frac{1}{2(n(n − 1))^{k}} \binom{n}{2} = 1 − \frac{1}{n^{k−1}} + O(\frac{1}{n^{2(k−1)}} )

Let A be the event (h_{1}, …, h_{k}) ∈ Γ_{k}(H), and B be the event that h_{1} = 1. By the above, Pr(A) = 1 − \frac{1}{n^{k}−1} + O(\frac{1}{n^{2(k−1)}} ) and Pr(B) = \frac{1}{n}.

So what is Pr(B|A)? Well, it is equal to \frac{Pr(A|B)}{Pr(A)} Pr(B), and we may interpret Pr(A|B) as such; either h_{2}, …, h_{k} fix the first element or they fix an element not equal to the first. Calculating the probabilities, it follows that

Pr(A|B) = 1 − \frac{2}{n^{k−1}} + O(\frac{1}{n^{2(k−1)}} )

and thus

Pr(B|A) = \frac{1}{n} (\frac{1 − \frac{2}{n^{k−1}} + O(\frac{1}{n^{2(k−1)}} )}{1 − \frac{1}{n^{k−1}} + O(\frac{1}{n^{2(k−1)}} )}) = \frac{1}{n} (1 − \frac{1}{n^{k−1}} + O(\frac{1}{n^{2(k−1)}} ))

so P = \frac{1}{n} − \frac{1}{nk} + O(\frac{1}{n^{2k−1}} ).

So, if we were to plot the number of generating sets giving us h_{1}(1) = 1 for g uniform and g_{1} ∈ Γ_{k}(G), we wil have peaks at \frac{1}{n} and \frac{1}{n} − \frac{1}{n^{k}} respectively, and we may return to our original result by choosing B ⊂ G such that \{g = (h_{1}, …, h_{m})\} in which the number of generating sets in which h_{i}(1) = 1 exceeds m(\frac{1}{n} − \frac{1}{2n^{2}} ). Using the Chernoff bounds, we find that |B| ≈ |G|(1 − \frac{1}{n!}) → 1, and that Q_{k}(B) ≈ \frac{1}{n!} → 0.