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

Lecture 2

Lecturer: Igor Pak Scribe: Jason Burns

The probability of generating a group, part 2

Some notation from last time:

Let G be a group. We will write φ_{k}(G) for the probability that k random elements of G generate the entire group. (We assume that all the elements are chosen independently, and each group element is equally likely.) For example, φ_{1}(G) ≠ 0 if and only if G is cyclic.

We also define ℓ(G) as the length of the longest subgroup chain in G; that is, ℓ(G) is the largest ℓ such that

1 = G_{0} ⊊ G_{1} ⊊ ⋯ ⊊ G_{ℓ} = G.

Yesterday^{1} we proved that, if |G| ≤ 2r (or even if we only have ℓ(G) ≤ r), then φ_{k}(G) ≥ φ_{k}(ℤ_{2}^{r}).

Today, we’ll estimate φ_{k}(ℤ_{2}^{r}). We argued last time that this was the worst possible case (that is, φ_{k}(G) ≥ φ_{k}(ℤ_{2}^{r}) whenever |G| ≤ 2^{r}), so this immediately leads to a lower bound for φ_{k}(G) …

Theorem 1 Let G = ℤ_{2}^{r}. Then φ_{r}(G) > \frac{1}{4}, φ_{r+1}(G) > \frac{1}{2}, and in general φ_{r+j}(G) > 1 − \frac{c}{2^{j}} for some constant c.

To make our estimate, we’ll use two famous identities of Euler (1748):

∏_{j=1}^{∞}(1 − z^{j}) = 1 + ∑_{m=1}^{∞}(−1)^{m}(z^{\frac{m(3m−1)}{2}} + z^{\frac{m(3m+1)}{2}} )

and

∏_{j=0}^{∞} \frac{1}{1 − tz^{j}} = 1 + ∑_{m=1}^{∞} \frac{t^{m}}{(1 − z)(1 − z^{2}) ⋯ (1 − z^{m})}.

Proof of Theorem 1

One way of visualizing φ_{k}(ℤ_{2}^{r}) is as follows. Consider ℤ_{2}^{r} as an r-dimensional vector space over the twoelement field ℤ_{2}. Then we’re asking for the probability that a given set of k vectors span the whole space of r dimensions. Or, put in another way,

k\{\underbrace{[ \begin{matrix}a_{1}, & a_{2}, & ⋯, & a_{r} \\ b_{1}, & b_{2}, & ⋯, & b_{r} \\ & ⋯ \\ z_{1}, & z_{2}, & ⋯, & z_{r} \end{matrix} ]}_{r}

1Last Friday, actually, but it feels like only yesterday.

if we make a matrix out of our k vectors, what is the probability that matrix has rank r? — Just when all r of the columns are independent, of course.

k\{\underbrace{[ \begin{matrix}a_{1} & a_{2} & & a_{r} \\ b_{1} & b_{2} & & b_{r} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ z_{1} & z_{2} & & z_{r} \end{matrix} ]}_{r}

The probability that the first column is nonzero is (1 − \frac{1}{2^{k}}). The probability that the second column is linearly independent of the first row is (1 − \frac{1}{2^{k−1}} ). In general, the probability that the j-th column is linearly independent of the previous j − 1 columns is (1 − \frac{2^{j−1}}{2^{k}}), and hence the probability that all the columns are linearly independent is φ_{k}(ℤ_{2}^{r}) = ∏_{j=1}^{r}(1 − \frac{2^{j−1}}{2^{k}}).

Now, we already know that ℤ_{2}^{r} cannot be generated by fewer than r elements, and indeed φ_{k}(ℤ_{2}^{r}) = 0 for k < r, according to the formula we’ve just derived. How about for k = r? Then we have the estimate

φ_{r}(ℤ_{2}^{r}) = (1 − \frac{1}{2^{r}})(1 − \frac{1}{2^{r−1}} ) ⋯ (1 − \frac{1}{2})

> ∏_{j=1}^{∞}(1 − \frac{1}{2^{j}})

= \underbrace{1 − \frac{1}{2^{1}} − \frac{1}{2^{2}}}_{= \frac{1}{4}} + \underbrace{\frac{1}{2^{5}} + \frac{1}{2^{7}} − \frac{1}{2^{12}} − \frac{1}{2^{15}} + ⋯}_{>0}

> \frac{1}{4}.

Did you notice how we used one of Euler’s famous identities in the third line?

One down, two to go. For φ_{r+1}(ℤ_{2}^{r}), we just mimic the previous argument.

φ_{r+1}(ℤ_{2}^{r}) = (1 − \frac{1}{2^{r+1}} )(1 − \frac{1}{2^{r}}) ⋯ (1 − \frac{1}{2^{2}} )

> ∏_{j=2}^{∞}(1 − \frac{1}{2^{j}})

= (1 − \frac{1}{2})^{−1} ∏_{j=1}^{∞}(1 − \frac{1}{2^{j}})

= 2 ∏_{j=1}^{∞}(1 − \frac{1}{2^{j}})

> 2 · \frac{1}{4}

= \frac{1}{2}.

We’ll use a different estimate for the general case.

φ_{r+k}(ℤ_{2}^{r}) = (1 − \frac{1}{2^{r+k}})(1 − \frac{1}{2^{r+k−1}} ) ⋯ (1 − \frac{1}{2^{k+1}} )

> ∏_{j=1}^{∞}(1 − tz^{j}) (let t = \frac{1}{2^{k}} and z = \frac{1}{2})

= (1 + ∑_{m=1}^{∞} \frac{t^{m}}{(1 − z)(1 − z^{2}) ⋯ (1 − z^{m})})^{−1}

Now, to get a lower bound on this, we need an upper bound on the quantity in parentheses. The denominator of the sum might look familiar — it’s just φ_{m}(ℤ_{2}^{m}) = (1−z)(1−z^{2}) ⋯ (1−z^{m}), which we already determined was at least \frac{1}{4}.

1 + ∑_{m=1}^{∞} \frac{t^{m}}{φ_{m}(ℤ_{2}^{m})} < 1 + 4 ∑_{m=1}^{∞} t^{m}

< 1 + 4\frac{t}{1 − t}

= 1 + 4\frac{\frac{1}{2^{k}}}{1 − \frac{1}{2^{k}}}

< 1 + 4 \frac{\frac{1}{2^{k}}}{\frac{1}{2}}

= 1 + \frac{8}{2^{k}}

Hence

φ_{r+k}(ℤ_{2}^{r}) > \frac{1}{1 + \frac{8}{2^{k}}} > 1 − \frac{8}{2^{k}} .

You can, of course, make a better estimate.

Random Group Processes: Loose Ends

We can turn this around, and ask what the probability is that the elements we pick don’t generate a group. Let δ(t) = 1 − φ_{t}(G), where G is (as usual) a finite group. Obviously δ(t + 1) ≤ δ(t), and in general δ(t + s) ≤ δ(t)δ(s) since we’re picking each element independently. So δ is submultiplicative, it decays exponentially^{2}, and if you’ve been paying attention you should be able to estimate when δ first drops below \frac{1}{2}.

Yet another way of posing this question, as you may recall from last lecture, is to ask how many elements we have to pick to generate G. Recall that we defined the stopping time τ to be the number of elements we have to pick, one at a time, to generate G. Of course, it depends on which elements we pick, but we can estimate it.

Proposition 2 E(τ) = ∑_{τ=0}^{∞} δ(τ).

2The exponent turns out to be the smallest index of a proper subgroup of G.

Proof: ∑_{t=0}^{∞} δ(t) = ∑_{t=0}^{∞} Pr(τ > t) = ∑_{t=0}^{∞} t · Pr(τ = t) = E(t).

We know E(τ) in terms of δ, and we know δ in terms of φ_{k}(G), and we have the estimate φ_{k+r}(G) > 1 − \frac{8}{2^{k}} from above. So we can estimate E(τ):

Corollary 3 For any group G, E(τ) ≤ ℓ(G) + C, where C is a constant.

Proof: The worst possible case for a given r = ℓ(G) is ℤ_{2}^{r}, and in that case, φ_{k+r}(H) > 1 − \frac{8}{2^{k}}, as we proved earlier today. So δ_{m+k}(G) is less than \frac{8}{2^{k}}, and E(τ) < r + ∑_{k+1}^{∞} \frac{8}{2^{k}} = r + 8.

Next time …

Babai proved that two random elements of S_{n} generate either A_{n} or S_{n}, with probability 1 − \frac{1}{n} + O(\frac{1}{n^{2}} )^{3}.

Tomorrow we’ll prove that, using classification of the finite simple groups.

(Where does the \frac{1}{n} come from?, you may ask. Well, let’s suppose that the two permutations never mix some of the n elements — that they permute k elements, and the other n − k separately. Specifically, if they both fix a point, that gives rise to our \frac{1}{n} term. (Only one pair in n^{2} fixes a given point under both permutations — but there are n points to choose from. Hence \frac{1}{n}.))

3Dixon proved the weaker result 1 − O( \frac{1}{(log log n)^{2}} ).