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

Lecture 18

Lecturer: Igor Pak Scribe: Christopher Malon

Testing Solvability and Nilpotence

How to Reduce Generating Sets

Let G = ⟨g_{1}, …, g_{k}⟩, and consider a random subproduct h = g_{1}^{ϵ_{1}} ⋯ g_{k}^{ϵ_{k}}, where the ϵ_{i} ∈ {0, 1} are chosen independently, uniformly. Last time, we showed:

Lemma 1 If H < G is a proper subgroup, then Pr(h ∉ H) ≥ \frac{1}{2}.

From the first lecture of the semester, we know that a nonredundant generating set cannot have more than log_{2} |G| elements. Let L be an upper bound on log_{2} |G|, and c be a constant to be determined.

Theorem 2 A set of cL independently chosen random subproducts {h_{1}, …, h_{cL}} generates G with high probability.

(The cost of forming this generating set is O(kL).)

Proof: Let H_{i} = ⟨h_{1}, …, h_{i}⟩. Either H_{i} = G, or Pr(h_{i+1} ∉ H_{i}) ≥ \frac{1}{2}, by the lemma above. Let τ be the first time i when H_{i} = G. Then E(τ) ≤ 2L. If we take L to be the length of the maximal subgroup chain, and c = 4, then this algorithm succeeds with probability at least \frac{1}{2}, by the Markov inequality.

The Chernoff bound (stated in lecture 10, October 1) provides another estimate of the value of c sufficient to ensure a certain probability of success. We omit the details.

Commutator Subgroups

Fix k = O(log |G|).

In order to test a black box group for solvability or nilpotence, we want to construct generators for a commutator group [G, G] from generators for G.

Suppose G = ⟨g_{1}, …, g_{k}⟩. [G, G] is not necessarily generated by the set of [g_{i}, g_{j}]. For example, a simple alternating group can be generated by two elements g_{1}, g_{2}. Since [G, G] is normal in G and G is simple, [G, G] = G. The single element [g_{1}, g_{2}] can generate only a cyclic subgroup.

The following is true:

Theorem 3 If A = ⟨a_{1}, …, a_{k}⟩ and B = ⟨b_{1}, …, b_{m}⟩ are normal subgroups of G, then [A, B] is the normal closure of the group generated by [a_{i}, b_{j}], 1 ≤ i ≤ k, 1 ≤ j ≤ m.

The normal closure of a subgroup H of G, denoted ⟨H⟩^{G}, is the smallest normal subgroup of G containing H. Since [A, B] is normal, it must contain the normal closure of the group generated by the [a_{i}, b_{j}]. The equality given by the theorem wasn’t proven in class, but I’ve sketched the easy proof at the end of the notes.

Lemma 4 Let H = ⟨h_{1}, …, h_{m}⟩ be a subgroup of G = ⟨g_{1}, …, g_{k}⟩. Suppose H ≠ ⟨H⟩^{G}. Then Pr(h^{g} ∉ H) ≥ \frac{1}{4}, where h and g are random subproducts of the given generators for H and G, respectively.

Proof: Let

N_{G}(H) = {g ∈ G : gHg^{−1} = H}

denote the normalizer of H in G. Since H ≠ ⟨H⟩^{G}, we know H is not normal in G, and N_{G}(H) ≠ G. Let g be a random subproduct of the generators for G. By Lemma 1, Pr(g ∉ N_{G}(H)) ≥ \frac{1}{2}.

Assume g ∉ N_{G}(H). Then H^{g} ∩ H is a proper subgroup of H. Let h be a random subproduct in H. Then

h^{g} = (h_{1}^{ϵ_{1}} ⋯ h_{m}^{ϵ_{m}})^{g} = (h_{1}^{g})^{ϵ_{1}} ⋯ (h_{m}^{g})^{ϵ_{m}}

is a random subproduct on H^{g} = ⟨h_{1}^{g}, …, h_{m}^{g}⟩. Over h, Pr(h^{g} ∉ H) = Pr(h^{g} ∉ H^{g} ∩ H) ≥ \frac{1}{2}, again by Lemma 1. Over h and g, Pr(h^{g} ∉ H) ≥ \frac{1}{2} · \frac{1}{2} = \frac{1}{4}.

Our algorithm to construct a generating set for [A, B] proceeds as follows. Let V_{0} be the group generated by all [a_{i}, b_{j}]. For each r > 0, form V_{r} by adding the element v^{g} to the set of generators for V_{r−1}, where v is a random subproduct of the generators for V_{r−1} and g is a random subproduct of the generators for G. Then V_{cL} = [G, G] with high probability, by Theorem 3, Lemma 4, and the Markov Inequality.

To test whether a black box group is solvable, we just take its commutator repeatedly, using the algorithm above:

G → [G, G] → [[G, G] , [G, G]] → ⋯

We keep doing this for as many iterations as the longest possible subgroup chain in G (logarithmic in the size of G, which is given). We answer that it is solvable (with high probability) if all the generators are equal to the identity at the end of the algorithm. Otherwise, we say that it is not solvable (with certainty).

If we follow the algorithm literally, the number of generators we are considering will blow up as we take more commutators. To avoid this, we apply the generating set reduction algorithm from the beginning of the lecture. Thus, we can test for solvability in polynomial time in k and log_{2} |G|.

Similarly, we can test whether a group is nilpotent, by considering commutators of the form

G → [G, G] → [G, [G, G]] → · · · .

Appendix

To prove Theorem 3, we show that if N < G is a normal subgroup containing all [a_{i}, b_{j}], then it contains [A, B]. The proof can be broken into two lemmas:

Lemma 5 N contains all [a_{i}^{±1}, b_{j}^{±1}].

Proof: Observing that [x, y] = [y, x]^{−1}, we obtain

[a_{i}^{−1}, b_{j}] = a_{i}^{−1}[a_{i}, b_{j}]^{−1}a_{i}
[a_{i}, b_{j}^{−1}] = b_{j}^{−1}[a_{i}, b_{j}]^{−1}b_{j}
[a_{i}^{−1}, b_{j}^{−1}] = b_{j}^{−1}a_{i}^{−1} [a_{i}, b_{j}] a_{i}b_{j}

Lecture 18: 22 October 2001 3 Lemma 6 Let N < G be normal. If x, y, z ∈ G and [x, z] , [y, z] ∈ N, then [xy, z] ∈ N. Proof:

[xy, z] = xyzy^{−1}x^{−1}z^{−1}
= x(yzy^{−1}z^{−1})zx^{−1}z^{−1}
= x(yzy^{−1}z^{−1})x^{−1}xzx^{−1}z^{−1}
= (x [y, z] x^{−1})([x, z])

The theorem follows by considering expansions of arbitrary elements of A and B in terms of the a_{i} and b_{j}, and applying the two lemmas.