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

Lecture 29

Lecturer: Igor Pak Scribe: Etienne Rassart

Two theorems on the product replacement graph

Let Γ_{k}(G) be the graph with vertex set {(g_{1}, …, g_{k}) ∈ G^{k} : ⟨g_{1}, …, g_{k}⟩ = G} and edges

(g_{1}, …, g_{i}, …, g_{k}) ⟷ (g_{1}, …, g_{i}g_{j}^{±1}, …, g_{k})
⟷ (g_{1}, …, g_{j}^{±1}g_{i}, …, g_{k}) ,

for a finite group G. Conjecture Γ_{k}(G) is connected if k ≥ d(G) + 1. Theorem Γ_{k}(G) is connected if k ≥ d(G) + m(G). Corollary Γ_{k}(G) is connected if k ≥ 2 log_{2} |G|.

Theorem 1 (Babai) If k = 2⌈ log_{2} |G|⌉ then there is a constant c > 0 such that diam Γ_{k}(G) ≤ c · log_{2}^{2}|G|.

Proof: Let r = ⌈ log_{2} |G|⌉, so that k = 2r and m(G) ≤ r. There is a path in Γ_{k}(G) from (g_{1}, …, g_{k}) to (1, …, 1, h_{1}, 1, …, 1, h_{r}, 1, …, 1), where ⟨h_{1}, …, h_{r}⟩ = G. Since we can exchange elements, we can assume that we send (g_{1}, …, g_{k}) to (h_{1}, …, h_{r}, 1, …, 1). We want to go from (h_{1}, …, h_{r}, 1, …, 1) to (h_{1}, …, h_{r}, a_{1}, …, a_{r}) in such a way that

{a_{1}^{ε_{1}} ⋯ a_{r}^{ε_{r}} : ε_{i} ∈ {0, 1}} = G .

Set a_{1} to be some h_{i} ≠ 1. Then (h_{1}, …, h_{r}, 1, …, 1) ⟶ (h_{1}, …, h_{r}, a_{1}, 1, …, 1) and |{a_{1}^{ε_{1}}}| = 2 .

From there we proceed by induction. Suppose we have (g_{1}, …, g_{k}) connected to (h_{1}, …, h_{r}, a_{1}, …, a_{i}, 1, …, 1) with |{a_{1}^{ε_{1}} ⋯ a_{i}^{ε_{i}}}| = 2^{i}. Let C = {a_{1}^{ε_{1}} ⋯ a_{i}^{ε_{i}}} and A = C · C^{−1}. A first observation is that if A ≠ G then we can find x not in A such that x is at distance at most 2i + 1 from the identity (distance with respect to the generating set {h_{1}, …, h_{r}, a_{1}, …, a_{i}}): we take x to be one away from an element on the boundary of A. Then we can use a’s to get to the boundary and one of the h’s for the final step to x. So if we let a_{i+1} = x then we can go from (h_{1}, …, h_{r}, a_{1}, …, a_{i}, 1, …, 1) to (h_{1}, …, h_{r}, a_{1}, …, a_{i}, a_{i+1}, 1, …, 1) in O(log |G|) steps (since i ≤ r). Also, |{a_{1}^{ε_{1}} ⋯ a_{i+1}^{ε_{i+1}}}| = 2^{i+1}.

So

(h_{1}, …, h_{r}, 1, …, 1) ⟶_{steps}^{O(log^{2} |G|)} (h_{1}, …, h_{r}, a_{1}, …, a_{r}) ⟶_{steps}^{O(log^{2} |G|)} (1, …, 1, a_{1}, …, a_{r}) .

Hence

(g′_{1}, …, g′_{k}) ⟶^{O(log^{2} |G|)} (h′_{1}, …, h′_{r}, 1, …, 1) ⟶^{O(log^{2} |G|)} (h′_{1}, …, h′_{r}, a′_{1}, …, a′_{r})
↓^{O(log^{2} |G|)}
(1, …, 1, a′_{1}, …, a′_{r})
↓^{O(log |G|)}
(a′_{1}, …, a′_{r}, 1, …, 1)
↓^{O(log^{2} |G|)}
(a′_{1}, …, a′_{r}, a_{1}, …, a_{r})
↓^{O(log^{2} |G|)}
(1, …, 1, a_{1}, …, a_{r})
↓^{O(log^{2} |G|)}
(g_{1}, …, g_{k}) ⟵_{O(log^{2} |G|)} (h_{1}, …, h_{r}, 1, …, 1) ⟵_{O(log^{2} |G|)} (h_{1}, …, h_{r}, a_{1}, …, a_{r})

So there remains to check that we can go from (g_{1}, …, g_{k}) to (1, …, 1, h_{1}, 1, …, 1, h_{r}, 1, …, 1) in reasonable time. If we had (h_{1}, …, h_{r}, t_{1}, …, t_{r}) instead, we could actually use the t_{i}’s instead of x if some of them lie outside of C · C^{−1} (starting with t_{1} and adding an element at a time as before; if t_{i} is inside, we construct x outside as above). So we can go from (h_{1}, …, h_{r}, t_{1}, …, t_{r}) to (h′_{1}, …, h′_{r}, t′_{1}, …, t′_{r}) in O(log^{2} |G|) steps. All the transpositions throughout this process are done in O(log |G|) steps (overall).

Theorem 2 (Dunwoody) If G is solvable and k ≥ d(G) + 1 then Γ_{k}(G) is connected.

Proof: Consider the chain

{1} = G_{0} ⊆ G_{1} ⊆ … ⊆ G_{l} = G ,

where G_{i−1} is minimal G-invariant in G_{i}. We proceed by induction. If l = 0, there is nothing to prove. If l ≥ 1, let M = G_{1}. Because G is solvable, M is normal in G and abelian. Fix (h_{1}, …, h_{k−1}) such that ⟨h_{1} …, h_{k−1}⟩ = G. We can go from (g_{1}, …, g_{k}) to (m, m_{1}h_{1}, …, m_{k−1}h_{k−1}) for m, m_{i} ∈ M. This is done by working in the quotient group G/M, applying the inductive hypothesis, then lifting back to the whole group by taking a representative in each coset. Next observe that (m_{i}h_{i})^{−1} · m · (m_{i}h_{i}) = h_{i}^{−1} · m · h_{i} = m^{h_{i}} since M is abelian. This implies that word(m_{1}h_{1}, …, m_{k−1}h_{k−1})^{−1}·m·word(m_{1}h_{1}, …, m_{k−1}h_{k−1}) = word(h_{1}, …, h_{k−1})^{−1}·m·word(h_{1}, …, h_{k−1}) .

Now ⟨h_{1}, …, h_{k−1}⟩ = G, so (m, m_{1}h_{1}, …, m_{k−1}h_{k−1}) ⟶ (m^{g}, m_{1}h_{1}, …, m_{k−1}h_{k−1}) for any g ∈ G (write g as word(h_{1}, …, h_{k−1})). Also, ⟨m^{g} : g ∈ G⟩ = M since M is minimal, and thus m_{1} = m^{g_{i_{1}}} m^{g_{i_{2}}} ⋯ m^{g_{in}} for some g_{i_{j}} ∈ G. Therefore

(g_{1}, …, g_{k}) ⟶ (m, m_{1}h_{1}, …, m_{k−1}h_{k−1})

↓

(m^{g_{i_{1}}} , m_{1}h_{1}, …, m_{k−1}h_{k−1})

↓

(m^{g_{i_{1}}} , (m^{g_{i_{1}}} )^{−1}m_{1}h_{1}, …, m_{k−1}h_{k−1})

↓

(m^{g_{i_{2}}} , (m^{g_{i_{1}}} )^{−1}m_{1}h_{1}, …, m_{k−1}h_{k−1})

↓

(m^{g_{i_{2}}} , (m^{g_{i_{2}}} )^{−1}(m^{g_{i_{1}}} )^{−1}m_{1}h_{1}, …, m_{k−1}h_{k−1}) ↓ … ↓

(m^{a}, h_{1}, m_{2}h_{2}, …, m_{k−1}h_{k−1}) (some a ∈ G) ↓ … ↓

(m^{z}, h_{1}, h_{2}, …, h_{k−1}) (some z ∈ G)

↓ ^{since ⟨h_{1}...,h_{k−1}⟩=G}

(1, h_{1}, h_{2}, …, h_{k−1})

Now (h_{1}, …, h_{k−1}) was arbitrary, so any two (g_{1}, …, g_{k}) are connected in Γ_{k}(G).