18.317 Combinatorics, Probability, and Computations on Groups 28 November 2001

Lecture 30

Lecturer: Igor Pak Scribe: Michael Korn

Bias in the Product Replacement Algorithm

Here is the algorithm: The input to the algorithm is a k-tuple \overline{g} = (g_{1}, g_{2}, …, g_{r}, 1, …, 1), where the elements g_{1}, …, g_{r} generate the group G. We then run a random walk on Γ_{k}(G) starting at \overline{g} for L steps, putting us at the point \overline{g′}. We choose i randomly from 1, …, k, and output the group element g′_{i}. This algorithm is supposed to generate random group elements. Here are some questions which can be asked about this algorithm: Q1: Is Γ_{k}(G) connected? Q2: How do we choose the values for k and L? Q3: Is there bias in the output? (Are all group elements equally represented in generating k-tuples?) In this lecture we will try to answer question 3.

Definition 1 Suppose G is a finite group, and k ≥ d(G). (Recall that d(G) is the minimum number of generators necessary to generate G.) Let Q be the probability distribution of the first component of (g_{1}, …, g_{k}), where (g_{1}, …, g_{k}) is selected uniformly at random from among all k-tuples which generate G. So Q(a) is the probability that g_{1} = a.

Proposition 2 Let ϕ_{k}(G) be the probability that a random k-tuple (g_{1}, …, g_{k}) generates G. If ϕ_{k−1}(G) ≥ 1/2, then sep(Q) ≤ 1/2.

Proof: We need to show that for all a ∈ G, P rob(g_{1} = a) ≥ \frac{1}{2|G|}, where (g_{1}, …, g_{k}) is a random generating ktuple. This probability is equal to the number of generating k-tuples of the form (a, g_{2}, …, g_{k}), divided by the total number of generating k-tuples. The total number of generating k-tuples is at most |G|^{k}. Since ϕ_{k−1}(G) ≥ 1/2, the (k − 1)-tuple (g_{2}, …, g_{k}) generates G at least half the time. So (a, g_{2}, …, g_{k}) is a generating k-tuple at least half the time, for any a. So there are at least \frac{|G|^{k−1}}{2} generating k-tuples which have first element a. So the probability is at least \frac{1}{2|G|}. Question: Are there finite groups G with very small ϕ_{k}(G) for k ≥ d(G)? The answer will turn out to be yes. Let G_{n} be the group (A_{n})^{n!/8}. Then d(G_{n}) = 2 for n large enough. This fact follows from the following theorem.

Theorem 3 (P. Hall, 1938)

Let H be a nonabelian simple group. Let α_{k}(H) = max{m : d(H^{m}) = k}. Then α_{k}(H) is the number of Aut(H) orbits of action on Γ_{k}(H).

Let us see why this implies the earlier fact. We let H = A_{n} and let k = 2. For n > 6, it is a fact that Aut(A_{n}) = S_{n}. (This is not true for n = 6, but this is not for normal people to understand why.) We will assume that ϕ_{2}(A_{n}) ≥ 1/2 (so two random elements of A_{n} generate A_{n} at least half the time). Thus there are at least \frac{1}{2}(\frac{n!}{2})^{2} vertices in Γ_{2}(A_{n}). Since Aut(A_{n}) = S_{n}, the size of an orbit is n!, so the number of orbits is at least \frac{1}{2}(\frac{n!}{2})^{2} \frac{1}{n!} = \frac{n!}{8}. So α_{2}(A_{n}) ≥ \frac{n!}{8}, so d((A_{n})^{n!/8}) = 2, which proves the fact from above.

We will now give a proof of Hall’s Theorem.

Proof:

Let G = H^{m}. Take ⟨g_{1}, …, g_{k}⟩ = G, and let g_{i} = (h_{1}^{(i)}, h_{2}^{(i)}, …, h_{m}^{(i)}) ∈ G, where h_{j}^{(i)} ∈ H. Let us write these elements in a k-by-m array as shown:

g_{1} = h_{1}^{(1)}, h_{2}^{(1)}, …, h_{j}^{(1)}, …, h_{m}^{(1)}

g_{2} = h_{1}^{(2)}, h_{2}^{(2)}, …, h_{j}^{(2)}, …, h_{m}^{(2)}

⋮

g_{k} = h_{1}^{(k)}, h_{2}^{(k)}, …, h_{j}^{(k)}, …, h_{m}^{(k)}

Now look at the columns of this array. For all j, we must have ⟨h_{j}^{(1)}, h_{j}^{(2)}, …, h_{j}^{(k)}⟩ = H.

Claim 4 ⟨g_{1}, …, g_{k}⟩ = G iff (h_{j}^{(1)}, …, h_{j}^{(k)}) are generating k-tuples in different Aut(H) orbits.

Proving this claim is enough to prove the theorem.

The “only if” direction is obvious; if two such k-tuples were in the same orbit, then it would be impossible for (g_{1}, …, g_{k}) to generate all of H^{m}, since the two columns would always be bound by the isomorphism between them.

For the “if” direction, assume the columns of the array are generating k-tuples which are in different orbits. Let B = ⟨g_{1}, …, g_{k}⟩, and suppose B does not equal G. We will use an inductive argument. So assume that for a k-by-(m − 1) array, if the columns are generating k-tuples in different orbits, then the rows generate all of G. In our situation, this means that the projection of B onto the first m − 1 coordinates is onto. (In other words, for any choice of the first m − 1 coordinates, there is an element of B which attains those values, though we can’t say what its last coordinate will be.) Of course, there is nothing special about the first m − 1 coordinates; this statement holds for any collection of m − 1 coordinates.

Now consider the subset C ⊂ B consisting of points whose first m − 1 coordinates are all equal to 1 (the identity element). This is a normal subgroup of H, hence it is either H itself, or 1, since H is simple. Suppose C = H. Then B would have to equal G, since we can find an element of B which sets the first m−1 coordinates to whatever we want, and then multiplying this by an appropriate member of C will yield any element of G at all. So we must assume C = 1. Again, there is nothing special about the last coordinate. So any element of B which has the value 1 for m − 1 of its coordinates must have value 1 in the remaining coordinate as well.

Recall that we assumed H is nonabelian. Hence there are elements x and y with xyx^{−1}y^{−1} ≠ 1. Since we can set any m − 1 coordinates any way we like, it follows that (x, 1, …, 1, z) ∈ B, for some z. Similarly, we have (y, 1, …, 1, w, 1) ∈ B, for some w. Multiplying these gives (xy, 1, …, 1, w, z) ∈ B and (yx, 1, …, 1, w, z) ∈ B. Dividing these last two gives (xyx^{−1}y^{−1}, 1, …, 1, 1) ∈ B. But this contradicts the result of the previous paragraph.

This completes the proof of Hall’s Theorem.

Now back to the situation with A_{n}. As it turns out, for A_{5} we have α_{2}(A_{5}) = 19, which is greater than \frac{5!}{8} = 15, as we claimed that it should be for n large enough.

Claim 5 ϕ_{k}((A_{n})^{n!/8}) → 0 very rapidly as n → ∞.

Proof:

Recall that

P rob(⟨σ_{1}, σ_{2}, …, σ_{k}⟩ ≠ A_{n}) > \frac{1}{n^{k}}

(This is true since each permutation will fix the point 1 with probability 1/n, hence with probability 1/n^{k} all k permutations will fix the point 1.) So

P rob (⟨g_{1}, …, g_{k}⟩ = (A_{n})^{n!/8}) ≤ (1 − \frac{1}{n^{k}} )^{n!/8} ≤ e^{−n!/8n^{k}}

which is very small for n large.