The expected number of random elements to generate a finite group by Alexander Lubotzky^{∗}

To John Thompson

Let G be a finite group with a minimal number of generators d = d(G). If one chooses random elements from G independently, and with the uniform distribution, how many should one expect to pick until the elements chosen generate G? Call this number E(G).

Carl Pomerance [Po], motivated by some algorithms for primality testing, studied the question for G abelian. He showed that if G is abelian,

E(G) ≤ d(G)+σ when σ = 1+ ∑_{j=2}^{∞}(1− ∏_{t=2}^{∞} ζ(t)^{−1} ∏_{ℓ=2}^{j−1} ζ(ℓ)) = 2.118456563 … and

this σ is best possible (when G runs over all finite abelian groups). He raised the question of studying E(G) and E(G) − d(G) for more general groups.

Igor Pak [P], motivated by potential applications for the Product Replacement Algorithm, studied a closely related invariant: For k ∈ N, let d_{k}(G) = #\{(x_{1}, …, x_{k}) ∈ G^{k} | ⟨x_{1}, …, x_{k}⟩ = G\}, so \frac{d_{k}(G)}{|G|^{k}} is the probability of k random elements from G to generate G. Pak defined

V(G) = min \{k ∈ N | \frac{d_{k}(G)}{|G|^{k}} ≥ \frac{1}{e}\} .

He evaluated V(G) for various classes of groups G, and based on these and estimates in [KL] and [M], he conjectured that V(G) = O(d(G) log log |G|). He also pointed out that up to multiplication by (small) constants V(G) is roughly E(G). In particular, he showed that E(G) ≤ eV(G).

In [DLM], Detoni, Lucchini and Morini proved a weaker form of Pak’s conjecture by showing that V(G) ≤ d(G) + O(log log |G| log log log |G|). (See there for more results in this direction).

∗This work was partially supported by BSF and NSF grants

In this paper, we answer Pomerance’s question and prove Pak’s conjecture, in fact in a stronger form. Theorem.

V(G) ≤ d(G) + 2 log log |G| + 4.02.

Corollary.

E(G) ≤ ed(G) + 2e log log |G| + 11.

For the proof, we introduce a third invariant for G: Let m_{n}(G) denote the number of maximal subgroups of G of index n, and let

M(G) = max_{n≥2} \frac{log m_{n}(G)}{log n}.

M(G) is actually the “polynomial degree” of the rate of growth of m_{n}(G). This rate has been studied in recent years for finite and profinite groups by Mann, Shalev, Borovik, Liebeck and Pyber (see [M], [MS], [BLP] and the references therein). It is roughly equal to V(G) (see Proposition 1.2 below). Our proof follows the footsteps of these works and in particular it also depends on the classification of the finite simple groups.

In §1, we bring some relations between E(G), V(G) and M(G), and in §2, the theorem is proved. When we write log we always take it in base 2.

Acknowledgments. We are grateful to Carl Pomerance and Igor Pak for illuminating discussions which generated our interest in the problem and to Cheryl Praeger, for a crash course she gave me on permutation groups during a walk at the Durham conference 2001, which turned out to contain the main ingredients to solve this problem. We are also grateful to Yale University for its hospitality, and to the NSF and BSF (U.S.-Israel) for their support.

§1. Some comparisons.

Let E(G), V(G) and M(G) be as in the introduction. More generally, if G is a profinite group, denote by P_{k}(G) the probability (with respect to the Haar measure μ of G^{k}) that a k-tuple of elements of G generates G topologically. Namely, P_{k}(G) = μ\{(x_{1}, …, x_{k}) ∈ G^{k} | \overline{⟨x_{1}, …, x_{k}⟩} = G\}. Let P̃_{k}(G) = μ\{(x_{1}, …, x_{k}) ∈ G^{k} | \overline{⟨x_{1}, …, x_{k}⟩} = G; \overline{⟨x_{1}, …, x_{k−1}⟩} ≠ G\},

\begin{matrix}E(G) = ∑_{k=1}^{∞} kP̃_{k}(G) \\ and V(G) = min\{k | P_{k}(G) ≥ \frac{1}{e}\} \end{matrix}

when we agree that V(G) = ∞ if such k does not exist.

Let m_{n}(G) be the number of maximal open subgroups of G of index n and

M(G) = sup_{n≥2} \frac{log m_{n}(G)}{log n}.

Proposition 1.1. (Pak [P])

\frac{1}{e}E(G) ≤ V(G) ≤ \frac{e}{e − 1}E(G).

This is proved by Pak for finite groups but the same proof works for profinite groups. One can also deduce the result from finite to profinite by observing that if G = lim_{⟵} G_{i} then E(G) = lim E(G_{i}) and V(G) = lim V(G_{i}).

Proposition 1.2.

M(G) − 3.5 ≤ V(G) ≤ M(G) + 2.02.

Proof. Let us start with the right-hand side inequality:

V(G) = min \{k | 1 − P_{k}(G) < 1 − \frac{1}{e} = \frac{e − 1}{e}\} .

Now,

\begin{aligned}1 − P_{k}(G) & ≤ ∑_{M maximal}[G : M]^{−k} \\ & = ∑_{n=2}^{∞} m_{n}(G)n^{−k} ≤ ∑_{n=2}^{∞} n^{M(G)−k}. \end{aligned}

Thus, if k ≥ M(G) + 2.02, we deduce that

1 − P_{k}(G) ≤ ∑_{n=2}^{∞} \frac{1}{n^{2.02}} = ζ(2.02) − 1

which is smaller than \frac{e−1}{e}.

The proofs of Proposition 1.1 and half of Proposition 1.2 are elementary. On the other hand, the proof of the left-hand side inequality of Proposition 1.2, which is actually not needed in the rest of the paper, does require the following result of Pyber whose proof uses the classification of the finite simple groups. Theorem 1.3 (Pyber [Py]) There exists a constant b such that for every finite group G and every n ≥ 2, G has at most n^{b} core-free maximal subgroups of index n. In fact, b = 2 will do.

Pyber’s result is needed for the proof of the main theorems of this paper. Its proof uses, beside the classification, also the detailed description of core-free maximal subgroups as given in Aschbacher-Scott [AS]. Mann and Shalev show in [MS] a slightly weaker form of Theorem 1.3. In their result b depends on d = d(G). Their form implies a slightly weaker inequality in Proposition 1.2 and in the main theorems.

Anyway, the following proof of the left hand side of Proposition 1.2 is not more than a quantitative version of the qualitative result of Mann and Shalev which say that for a profinite group G, V(G) < ∞ if and only if M(G) < ∞. In fact, we follow closely Section 4 of [MS]:

Let now N_{i} be an enumeration of all cores of maximal subgroups of G (each core occuring only once). For each N_{i} choose a maximal subgroup M_{i} whose core is N_{i}. Let C_{n}(G) be the number of the maximal subgroups of index n obtained in this way. The events M_{i}^{k} in G^{k} are pairwise independent and from the (quantitative version of the) Borel-Cantelli lemma, one deduces that

∑_{n=2}^{∞} C_{n}(G)n^{−k} ≤ \frac{1}{P_{k}(G)} and in particular, C_{n}(G) ≤ \frac{n^{k}}{P_{k}(G)}. Taking k = V(G) we

get that

C_{n}(G) ≤ e · n^{V(G)}.

Now, Pyber’s Theorem (1.3) implies that

m_{n}(G) ≤ C_{n}(G)n^{b}.

Hence, m_{n}(G) ≤ e · n^{V(G)+b}.

It follows that

M(G) = sup_{n≥2} \frac{log m_{n}(G)}{log n} ≤ V(G) + b + log e ≤ V(G) + 3.5.

This proves Proposition 1.2.

We can now restate Mann-Shalev result:

Corollary 1.4. For a profinite group G, E(G) < ∞ ⇔ V(G) < ∞ ⇔ M(G) < ∞.

§2. Proof of the main theorem.

We will prove the main theorem by proving the following theorem which together with Propositions 1.1 and 1.2 gives the main theorem. Theorem 2.1. Let G be a finite group. Then M(G) ≤ d(G) + 2 log log |G| + 2.

To prove Theorem 2.1 we have to bound the number of maximal subgroups of G, or equivalently to bound the number of primitive permutational respresentations of G.

The following Proposition summarizes Theorem 4.3B and Theorem 4.7A of [DM] and gives us the needed information about the structure of finite primitive groups. Proposition 2.2. Let X be a primitive permutation group on a set Ω of size n. Then X has at most two minimal normal subgroups K_{1} and K_{2}, where K_{i} ≃ T^{k} when T is a simple group. There are three possibilities: (A): Affine case: K = K_{1} = K_{2} is a unique abelian minimal normal subgroup of order n = p^{k} isomorphic to (Z/pZ)^{k}. X is a semi-direct product of K and X_{α} - a stabilizer of α ∈ Ω. X_{α} is an irreducible subgroup of GL_{k}(p). The centralizer of K in X is K, C_{X}(K) = K. (B1): K = K_{1} = K_{2} is a unique non-abelian minimal normal subgroup. In this case C_{X}(K) = {1}. (B2): X has two different non-abelian minimal normal subgroups K_{1} and K_{2}. They are isomorphic to each other, acting regularly on Ω, K_{1} ∩ K_{2} = {1} and C_{X}(K_{i}) = K_{3−i} for i = 1, 2.

Let G now be a finite group and 1 = N_{0} ≤ N_{1} ≤ N_{2} ≤ … ≤ N_{r} = G a chief-series of G, i.e., for every i = 1, …, r, N_{i} ◁ G and N_{i}/N_{i−1} is a minimal normal subgroup of G/N_{i−1}. The series is not uniquely defined but r depends only on G as well as the quotients N_{i}/N_{i−1} as G-groups ([H] Theorem 8.4.5 p. 127).

Define C_{i} = C_{G}(N_{i}/N_{i−1}) = Ker(G →^{π_{i}} Aut(N_{i}/N_{i−1})) where π_{i} is the natural action of G on N_{i}/N_{i−1}. The collection of subgroups C = {C_{i}}_{i=1}^{r} is independent of the choice of the chief series.

Proposition 2.3. Let ρ : G → Sym(Ω) be a primitive permutational representation and X = ρ(G).

(a) If X is of type A (of (2.2)) with an abelian minimal normal subgroup K and ρ̃: G → X/K the composition of ρ and the projection from X to X/K, then there exist i, 1 ≤ i ≤ r, such that Kerρ̃ = C_{i}

(b1) If X is of type B1, then there exist i, 1 ≤ i ≤ r, such that Kerρ = C_{i}. (b2) If X is of type B2, then there exists i and j in {1, …, r}, such that

Kerρ = C_{i} ∩ C_{j}.

Proof. For i, 1 ≤ i ≤ r, ρ(N_{i})/ρ(N_{i−1}) is either trivial or a chief factor of X. Moreover, if it is non-trivial then N_{i}/N_{i−1} is isomorphic as G-group to ρ(N_{i})/ρ(N_{i−1}) (where g ∈ G acts on ρ(N_{i})/ρ(N_{i−1}) via conjugation by ρ(g)).

Now, if K is a minimal normal subgroup of X, then there exists a smallest i, 1 ≤ i ≤ r such that ρ(N_{i}) ∩ K ≠ {1}. For such an i, ρ(N_{i−1}) ∩ K = {1} and ρ(N_{i}) must contain K. As K is a minimal normal subgroup of X and N_{i}/N_{i−1} of G/N_{i−1}, K is isomorphic as a G-group to N_{i}/N_{i−1} (via ρ). This implies that ρ(C_{i}) ≤ C_{X}(K). In fact, it implies that ρ(C_{i}) = C_{X}(K) since if x ∉ C_{i}, it acts non-trivially on N_{i}/N_{i−1} and hence ρ(x) acts non-trivially on K. This observation and Proposition 2.2 prove all parts of Proposition 2.3.

If M is a maximal subgroup of G, we will say that M is of type A (resp. B) if the (primitive) permutation group induced by G on the coset space G/M is of type A (resp. B_{1} or B_{2}) of Proposition 2.2. Let m_{n}^{A}(G) (resp. m_{n}^{B}(G)) be the number of maximal subgroups of G of type A (resp. B) of index n.

Let r_{a}(G) (resp., r_{b}(G)) be the number of abelian (resp. non-abelian) chief factors of G. So r_{a}(G) + r_{b}(G) = r. Claim 2.4. m_{n}^{B}(G) ≤ \frac{1}{2}(r_{b}(G) + 1)r_{b}(G)n^{2}.

Proof: By Proposition 2.3 parts (b1) and (b2), the core of a maximal subgroup M of G of type B is equal to C_{i} ∩C_{j} for some 1 ≤ i, j ≤ n (i may be equal to j). It is clear that in this case, i and j come from non-abelian chief factors, so the number of possibilities for \{i, j\} is at most \frac{1}{2}(r_{b}(G) + 1)r_{b}(G). Given the core, there are at most n^{2} maximal subgroups with this core, by Theorem 1.3.

We need now to bound m_{n}^{A}(G), i.e., the number of affine primitive representations of G of degree n. We saw in (2.3)(a), that a maximal subgroup M of type A determines a primitive representation ρ : G → X where X has a unique abelian minimal normal subgroup K. Now, K is an abelian chief factor of X and hence isomorphic as a G-group to one of the r_{a}(G) abelian chief factors of G, say N_{i}/N_{i−1}. Moreover, by Proposition 2.2(A) and Proposition 2.3(a) we know that if ρ̃ : G → X/K is the induced map, then Kerρ̃ = C_{i} and X is isomorphic to the semi-direct product N_{i}/N_{i−1} ⋊ G/C_{i} ≃ K ⋊ X/K. The kernel of ρ is not unqiuely determined by Kerρ̃, but ρ is a homomorphism from G to K ⋊ X/K whose projection to X/K is the given ρ̃, which is determined by the choice of i. One can easily see that given i (and ρ̃) ρ determines (and it is determined) by a cocycle σ : G → K, a cocycle with respect to the G-action on K. The number of these cocycles is equal to Z^{1}(G, K) which is bounded by |K|^{d(G)}, since every cocycle is determined by its values on the generators.

Now, if M is a maximal subgroup of type A and index n, then by Proposition 2.2(A), the action of the minimal normal subgroup K of X = ρ(G) on G/M is regular, in particular |K| = n. We therefore deduce:

Claim 2.5. m_{n}^{A}(G) ≤ r_{a}(G) · n^{d(G)+2}.

Proof: By the discussion above, the number of possible cores of maximal subgroups of type A is at most r_{a}(G)n^{d(G)}. Given the core there are at most n^{2} maximal subgroups of index n with that core, by Theorem 1.3.

Corollary 2.6. m_{n}(G) = m_{n}^{A}(G) + m_{n}^{B}(G) ≤

\begin{matrix}(\frac{1}{2}((r_{b}(G) + 1)(r_{b}(G)) + r_{a}(G)n^{d(G)})n^{2} \\ ≤ r^{2}n^{d(G)+2}. \end{matrix}

Finally as M(G) = max_{n} \frac{log m_{n}(G)}{log n}, we deduce:

M(G) ≤ d(G) + 2 log r + 2.

As r < log G, Theorem 2.1 is proved.

Remark. There is some “significant waste” in the proof. The contribution of the non-affine permutation representations is at most r^{2}n^{2} and hence to M(G) it contributes at most \frac{2 log r}{log n} + 2. We estimated this from above by 2 log r + 2 which is of course ridiculous if n is large. We also allow a “waste” in the second inequality of Corollary 2.6. Let’s now estimate it in a slightly more careful way, keeping the notations as above and denoting i(G) to be the smallest index of a proper subgroup of G.

Now, by Corollary 2.6,

m_{n}(G) ≤ (\frac{1}{2}(r + 1)r + rn^{d(G)})n^{2} ≤ r(r + n^{d(G)})n^{2}

and so:

M(G) = max_{n≥2} \frac{log m_{n}(G)}{log n} ≤ 2 + \frac{1 + log r}{log n} + max(d(G), \frac{log r}{log n}).

Hence, we get: Corollary 2.7 M(G) ≤ \frac{1+log log |G|}{log i(G)} + max(d(G), \frac{log log |G|}{log i(G)}) + 2.

So, for the sequence of groups G_{k} = (A_{k})^{k!/8} (discussed in [KL] and [P]). The main theorem as stated gives V(G_{k}) = O(k log k). But, in fact, i(G_{k}) = k, so Corollary 2.7 shows that V(G_{k}) = O(k) - which is the correct estimate - see [P]).

The referee also showed us how the 2 can be dropped in Corollary 2.7, but as the proof needs some further analysis into the structure of primitive groups, we will not bring the details.

These improvements give a slightly sharper form of the main Theorem as: Corollary 2.8 V(G) ≤ \frac{1+log log |G|}{log i(G)} + max(d(G), \frac{log log |G|}{log i(G)}) + 2.02.

References

[AS] M. Aschbacher and L. Scott, Maximal subgroups of finite groups, J. Algebra 92 (1985) 44-80.

[BPS] A.V. Borovik, L. Pyber, A. Shalev, Maximal subgroups in finite and profinite groups, Trans. AMS 348 (1996), 3745-3761.

[DLM] E. Detoni, A. Lucchini and F. Morini, How many elements are needed to generate a finite group with good probability?, preprint.

[DM] J.D Dixon and B. Mortimer, Permutations Groups, Springer 1996.

[H] M. Hall, The Theory of Groups, The Macmillan Company, NY 1959.

[KL] W.M. Kantor and A. Lubotzky, The probability of generating a finite classical group, Geom. Ded. 36 (1990), 67-87.

[M] A. Mann, Positively finitely generated groups, Forum Math. 8 (1996) 429-459.

[MS] A. Mann, A. Shalev, Simple groups, maximal subgroups and probabilstic aspects of profinite groups, Israel J. Math. 96 (1996) 449-468.

[P] I. Pak, On probability of generating a finite group, preprint 1999.

[Po] C. Pomerance, The expected number of random elements to generate a finite abelian group. Period. Math. Hungar. 43 (2001), no. 1-2, 191-198.

[Py] L. Pyber, in preparation.

Institute of Mathematics Hebrew University Jerusalem 91904 ISRAEL