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

Lecture 1

Lecturer: Igor Pak Scribe: R. Radoičić

Probability of Generating a Group

Let G be a finite group and let |G| denote the order of G. Let d(G) denote the minimum number of generators of G and l(G) the length of the longest subgroup chain 1 = G_{0} ⊊ G_{1} ⊊ G_{2} ⊊ … ⊊ G_{l} = G. Also, let m(G) denote the maximal size of a non-redundant generating set, where a generating set ⟨g_{1}, g_{2}, …, g_{k}⟩ is called redundant if there exists an i such that ⟨g_{1}, …, g_{i−1}, g_{i+1}, …, g_{k}⟩ = G. Furthermore, let

φ_{k}(G) = P r(⟨g_{1}, g_{2}, …, g_{k}⟩ = G),

where g_{i} are elements of G, chosen independently and uniformly at random from G. The main topic of the lecture today is to give a good estimate on φ_{k}(G). More precisely, for every group G, we would like to find the smallest k for which φ_{k}(G) ≥ \frac{1}{3} or some other positive constant. Trivially, φ_{k}(G) = 0 for k < d(G).

Let’s look at several examples to understand the meaning of the notions above.

For example, let’s take G = ℤ_{2} × ℤ_{3} × ℤ_{5} × ℤ_{7} × … × ℤ_{p}. Then, clearly,

φ_{1}(G) = (1 − \frac{1}{2}) (1 − \frac{1}{3}) (1 − \frac{1}{5}) … (1 − \frac{1}{p}) ,

which tends to 0 as p → ∞. Indeed,

φ_{1}(G) = exp ( ∑_{i<p,i prime} log (1 − \frac{1}{i})) ≈ exp (− ∑_{i<p,i prime} \frac{1}{i}) ,

which converges to 0 since ∑ \frac{1}{i} diverges. On the other hand,

φ_{2}(G) = (1 − \frac{1}{2^{2}} ) (1 − \frac{1}{3^{2}} ) (1 − \frac{1}{5^{2}} ) … (1 − \frac{1}{p^{2}} )

is strictly positive since ∑ \frac{1}{i^{2}} converges.

If G is ℤ_{2}^{r}, i.e an r-dimensional vector space on {0, 1}-vectors, then d(G) = m(G) = l(G) = r. But this is not always the case.

If G is ℤ_{2^{r}}, then d(G) = m(G) = 1, but l(G) = r, since 1 = ℤ_{1} ⊊ ℤ_{2} ⊊ ℤ_{4} ⊊ … ℤ_{2^{r}}.

Now, let G = S_{n}, the permutation group on n letters. Since G = ⟨(1, 2), (1, 2, …, n)⟩ and since S_{n} is not a cyclic group, then d(G) = 2. Because there are n − 1 adjacent transpositions (1, 2), (2, 3), …, (n − 1, n), we have m(G) ≥ n − 1. Actually, Whiston [W00] showed that m(G) = n − 1.

What about l(S_{n})? Well, for any group G we have the following trivial bounds:

Proposition 1

d(G) ≤ m(G) ≤ l(G) ≤ log_{2} |G|

Proof: The first and the last inequality are obvious, while the middle inequality follows from the implication: m(G) = k and ⟨g_{1}, g_{2}, …, g_{k}⟩ is the maximal non-redundant generating set ⇒ ⟨g_{1}⟩ ⊊ ⟨g_{1}, g_{2}⟩ ⊊ … ⊊ ⟨g_{1}, g_{2}, …, g_{k}⟩.

One of the serious theorems in this subject shows that l(S_{n}) ≈ \frac{3}{2}n, but its proof is quite involving and uses the classification theorems [B86], [CST89]. We are going to show a weaker but elegant statement:

Theorem 2

l(S_{n}) = O(n log log n)

Proof: We will use ◯_{p} to denote the highest power of p dividing n!. Then we have

◯_{p} = ⌊\frac{n}{p}⌋ + ⌊\frac{n}{p^{2}} ⌋ + … = ∑_{i}⌊\frac{n}{p^{i}} ⌋ ≤ \frac{n}{p (1 − \frac{1}{p})} = \frac{n}{p − 1}.

Then clearly:

l(S_{n}) ≤ ∑_{p≤n,p prime} ◯_{p} ≤ n ∑_{p≤n} \frac{1}{p − 1} ≤ n log log n + O(n),

where the last inequality follows from the Prime Number Theorem:

∑_{p≤n} \frac{1}{p − 1} ∼ ∫_{1}^{n} \frac{dx}{x log x} = ∫ \frac{d log x}{log x} = log log x|_{1}^{n}.

Definition 3 We define the random group process {B_{t}}:

B_{0} = 1 and for t > 0, B_{t+1} = ⟨B_{t}, g_{t+1}⟩, where g_{t+1} ∈ G is a random element chosen at moment t + 1. We obtain the chain of subgroups B_{0} ⊂ B_{1} ⊂ B_{2} ⊂ … ⊂ B_{t} ⊂ … ⊂ G. Let τ(G) denote the stopping time of {B_{t}}, i.e.

τ := min{t : B_{t} = G}

Proposition 4

E[τ] ≤ 2 log_{2} |G|

Proof: Given that t < τ (i.e. B_{t} ≠ G), we have

P r(B_{t+1} ≠ B_{t}) = 1 − \frac{|B_{t}|}{|G|} ≥ \frac{1}{2}.

Thus, the expected time for the random group process to increase the order of the current subgroup is ≤ 2. Hence, E[τ] ≤ 2 log_{2} |G|.

If G = ℤ_{2}^{r}, then the inequality in the previous proof is an equality, so, in a sense, ℤ_{2}^{r} is the worst to generate. Notice that we actually proved the following stronger statement:

Proposition 5

E[τ] ≤ 2l(G)

However, l(G) in the proposition above cannot be replaced by m(G), which is clear, e.g. when G = ℤ_{2}^{r}. Still, the result is not the best possible. Clearly, E[τ] ≥ l(G), but we will show today that the multiplicative constant factor in front of l(G) can be shed.

Theorem 6 Let |G| ≤ 2^{r}. Then for all k, φ_{k}(G) ≥ φ_{k}(ℤ_{2}^{r}).

Proof: Fix k and a subgroup A ⊊ G. Let B_{t} and B′_{t} be the random group processes for G and ℤ_{2}^{r}, respectively. Let τ_{1}, τ_{2}, …, τ_{L} = τ denote times t for which B_{t} ≠ B_{t−1}. Similarly, define τ′_{1}, τ′_{2}, …, τ′_{R} = τ′. We will use the induction on |G|. When |G| = 1, the theorem is trivial. Let s := τ_{L−1}. We need to show that

P r(τ_{L} − τ_{L−1} ≤ k|B_{s} = A) ≥ P r(τ′_{R} − τ′_{R−1} ≤ k)

Indeed, the lefthand side is equal to 1 − (\frac{|A|}{|G|})^{k}, and the righthand side is equal to 1 − P r(τ′_{R} − τ′_{R−1} > k) = 1 − \frac{1}{2^{k}}.

Now \frac{|A|}{|G|} ≤ \frac{1}{2} and the claim above follows.

This claim, combined with the induction assumption P r(τ_{L−1} ≤ k) ≥ P r(τ′_{R−1} ≤ k), gives

P r(τ_{L} ≤ k|B_{s} = A) ≥ P r(τ′_{R} ≤ k) = φ_{k}(ℤ_{2}^{r}).

This holds for any fixed k and A, so the theorem follows.

References

[W00] J. Whiston: Maximal independent generating sets of the symmetric group, Journal of Algebra 232 (2000), 255–268.

[B86] L. Babai: On the length of subgroup chains in the symmetric group, Comm. Algebra 14 (1986), 1729–1736.

[CST89] P. J. Cameron, R. Solomon, A. Turull: Chains of subgroups in symmetric groups, Journal of Algebra 127 (1989), 340–352.