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

Lecture 15

Lecturer: Igor Pak Scribe: Fumei Lam

Hall Bases

Definition 1 Let H be an abelian p-group. A set B = {b_{1}.b_{2}, … b_{r}} ⊆ H is a Hall basis if ∀h ∈ H, ∃ α_{1}, α_{2}, … α_{r} ∈ {0, 1, … p − 1} such that h = b_{1}^{α_{1}}b_{2}^{α_{2}} … b_{r}^{α_{r}}. The following lemma shows that for a Hall basis B, the distribution of B\overline{α} over \overline{α} is uniform in H. Lemma 2 If B = {b_{1}, b_{2}, … b_{r}} is a Hall basis in H, then

P r\overline{α}(b_{1}^{α_{1}}b_{2}^{α_{2}} … b_{r}^{α_{r}} = h) = \frac{1}{|H|} ∀ h ∈ H

Proof: Consider H as a vector space. Since B is a Hall basis, it is a spanning set and contains a basis, say b_{1}, b_{2}, … b_{k}. Then for uniform α_{i} ∈ {0, 1, … p − 1} , we have

\underbrace{b_{1}^{α_{1}}b_{2}^{α_{2}} … b_{k}^{α_{k}}}_{uniform in H} b_{k+1}^{α_{k+1}}b_{k+2}^{α_{k+2}} … b_{r}^{α_{r}},

which is uniform in H.

Recall that G is nilpotent if some G_{l} in the lower central series

G = G_{0} ⊃ G_{1} ⊃ G_{2} ⊃ G_{3} ⊃ ⋯ ⊃ G_{l} = {1}

is the identity element (where G_{i} = [G_{i−1}, G] for i = 1, 2, 3 …). Let H_{i} = G_{i−1}/G_{i} and let γ_{i} : G_{i−1} → H_{i} denote the standard map of G_{i−1} onto the cosets of G_{i}. From last time, if ψ_{i} : H_{i} → G_{i−1} is a map such that γ_{i}(ψ_{i}(h)) = h for all h ∈ H, then we have the following lemma. Lemma 3 For h_{i} uniform in H_{i} and g_{i} uniform in G_{i}, ψ(h_{i})g_{i} is uniform in G_{i−1}. In what follows, we will assume G is nilpotent with G = G_{0} ⊃ G_{1} ⊃ G_{2} ⊃ … ⊃ G_{l} = {1}.

Definition 4 Let \overline{B} = (B_{1}, B_{2}, … B_{l}), B_{i} ⊂ G_{i−1}. \overline{B} is a Hall basis if γ_{i}(B_{i+1}) is a Hall basis of H_{i+1} for all i = 0, 1, … l − 1.

Lemma 5 Let \overline{B} = (B_{1}, B_{2}, … B_{l}), B_{i} = \{b_{i_{1}}, b_{i_{2}}, … b_{i_{r_{i}}} \}, and suppose α_{ij} is uniform in \{0, 1, … p − 1\}. Then

g = ∏_{i=1,2,...l}^{→} ∏_{j=1,2,...r_{i}}^{→} b_{ij}^{α_{ij}}

is uniform in G, where ∏_{i=1,2,...l}^{→} denotes the product in the order 1, 2 … l.

Proof: Note that since \overline{B} is a Hall basis, g can be written as g = g_{1}g_{2} … g_{l} with g_{i} ∈ G_{i−1} and h_{i} = γ_{i}(g_{i}) uniform in H_{i}.

Since H_{l} = G_{l−1}, h_{l} = γ_{l}(g_{l}) = g_{l} is uniform in G_{l−1}. Furthermore, h_{l−1} = γ_{l−1}(g_{l−1}) is uniform in H_{l−1} and by the previous lemma, this implies g_{l−1}g_{l} is uniform in G_{l−2}. Continuing by induction, we obtain g = g_{1}g_{2} … g_{l} is uniform in G_{0} = G.

In fact, the lemma remains true even if we remove the restriction on the product order of the b_{ij}, as we will show in the following theorem.

Definition 6 Let Λ = {(i, j) : i = 1, 2, … l, j = 1, 2, … r_{i}}. A word w in b_{ij}, (i, j) ∈ Λ is complete if b_{ij} occurs in w for all (i, j) ∈ Λ.

Theorem 7 If \overline{B} is a Hall basis and w is a complete word, then w\overline{α} is uniform in G.

Proof: First, consider all the elements b_{l∗} ∈ B_{l} in w. Since B_{l} ⊆ G_{l−1}, and G_{l−1} is contained in the center of G, each element b_{l∗} commutes with all other elements in the word w and we can express w as

w = ∗ ∗ ⋯ ∗ _{B_{l}} .

Now, observe that if a ∈ B_{i}, b ∈ B_{j}, then ab ∈ ba[a^{−1}, b^{−1}] with [a^{−1}, b^{−1}] ∈ G_{c} for some c > i, j. So we can move all the elements b_{l−1∗} ∈ B_{l−1} in w to the right and write w in the form

w = ∗ ∗ ⋯ ∗ _{B_{l−1}} _{B_{l}},

where the shaded box represents a product of terms in G_{l−1} accumulated by commuting the elements b_{l−1∗}.

Lecture 15: 15 October 2001 3 Continuing in this way, we obtain

w = _{B_{1}} _{B_{2}} … _{B_{l−1}} _{B_{l}} .

Since each of the products in B_{i} corresponds to a uniform element in H_{i} under γ_{i}, we have

w = \underbrace{. . . . . . \underbrace{_{uniform in G_{l−1}}}_{uniform in G_{l−2}}}_{uniform in G_{0} = G},

proving the theorem.