有限群生成元的数目(英文文献)

The Number of Generators of a Finite Group

Abstract： In this expository article, which is a slightly expanded in the conception of the gengerators of finite groups, we ?rst recall a technique recently developed by F. Dalla Volta and A. Lucchini to study generation properties of ?nite groups. We then discuss some problems in permutation groups, linear groups and pro?nite groups where this technique has proved useful. Finally, we comment on some results and problems related to probability and computation.

Key words: gengerators ; permutation groups; linear groups; pro?nite groups

1. Introduction

If G is a ?nite group (all groups in this paper will be ?nite, unless explicitly stated otherwise), we denote by d(G) the minimum cardinality of a set of generators of G. (This is not to be confused with the related notion of cardinality of an irredundant set of generators: e.g. in Sym(n), (12),(23),..., (n?1n) is an irredundant set of generators having n?1 elements, but d(Sym(n)) = 2: (12),(12 ...n) suffice. But in the particular case of p-groups the two notions coincide, namely, according to Burnside’s Basis Theorem, if G is a ?nite p-group, then any irredundant set of generators has d(G) elements.) It is well known that the map G→ d(G) is not well behaved with respect to subgroups. As a familiar example, consider the group Sym(n): d(Sym(n)) = 2, but Sym(n) has a subgroup E = {(12),(34),...,((2i ? 1)2i),...} with d(E) = [n/2]. And this time p-groups are no exception: if we denote Cm a cyclic group of order m, the standard wreath product W, d(W) = 2, while its base subgroup B has d(B) = pn. On the other hand, if d(G) = m and X is any epimorphic image of G, then obviously d(X) ≤ d(G), and there is an epimorphic image H of G with the property d(H) = m and d(X) < m for all proper epimorphic images of H. We refer to such groups as being generator-critical. To transform this simple-minded remark into a useful tool, we will need to study generator-critical groups in some detail. We note at this point that the classi?cation of ?nite simple groups enters heavily in most general results on the generation of ?nite groups. In particular, the classi?cation allows to assemble classical results on alternating groups and groups of Lie type with individual checks on the sporadic simple groups into the fundamental uni?ed statement. Theorem. If S is any non abelian simple ?nite group, then d(S) = 2.

And it is also required in the proof of the following more technical results which will be basic in our discussion:

Theorem. [1]. Let N be a proper, minimum normal subgroup of the ?nite group G. Then d(G) ≤ d(G/N) + 1.

Theorem. [3]. Let the ?nite, non cyclic group G have a unique minimum normal subgroup M. Then d(G) = max(2,d(G/M)). 2. Generator-critical Groups

Let L be the set of ?nite groups L with the properties:

L has a unique minimal normal subgroup, M; if M is abelian then it has a complement in L.

The groups in L are rather well understood. With M abelian, easy examples are: if F is the ?eld with p elements, take M = F (the additive group of the ?eld), L = M × H with H ≤ F (the multiplicative group of F; we do not exclude H = 1). In general L is an affine group L = M×H, where M is an F-vector space and H is an irreducible subgroup of GLF(M).

With M non abelian, easiest examples are: if S is a non abelian simple group, S ≤ L ≤ AutS (i.e. L is almost simple; we do not exclude L = S. We record that d(L) ≤ 3 for any almost simple group [4]). Here are more examples: L = S wrSym(n), where M = Sn is the base subgroup. The general case is as follows: L is a subgroup of W = AutS wrSym(n), M = Sn ≤ L ≤ W, such that L projects onto a transitive subgroup of Sym(n).

Given L ∈ L with M = socL and a positive integer t de?ne the group Lt. Moreover let L0= L/M. The following properties of these groups Lt for t > 0 are easily proved: socLt = Mt; if K is a minimal normal subgroup of Lt, then K ≌ M and Lt/K ≌ Lt?1; d(Lt?1) ≤ d(Lt) ≤ d(Lt?1) + 1 for t > 1; lim d(Lt) =∞. Hence if m > d(L) there is a unique t = f(L,m) such that d(Lt) = m, d(Lt?1) < m. This means that d(Lf(L,m)) = m and for every proper epimorphic image X we have d(X) < m: in other words, Lf(L,m) is generator- critical.

The signi?cance of this construction comes from the following theorem.

Theorem. [1]. If H is a generator-critical ?nite group and d(H) = m, then H is isomorphic to Lf(L,m) for some L ∈ L.

Hence, if G is any nontrivial ?nite group, there exist L ∈ L and a positive integer t such that Lt is an epimorphic image of G and d(G) = d(Lt).

When trying to prove that a ?nite group which has a given property P can by generated by a certain number m of elements, a minimum counterexample is often a generator-critical group with m+1 generators. Hence results on the generation of groups Lt allow us to prove general results on the generation of ?nite groups. In particular, we are interested in getting information about f(L,m).

Here is an informal and very crude summary: if M is abelian, then f(L,m) is

linear in m, while if M is not abelian, then f(L,m) is approximately exponential in m. For a precise statement, we distinguish several cases.

Case 1: L = M is cyclic of order p. In this case of course Lt = Lt and f(L,m) = m. Case 2: L > M, M abelian.

Let F be the ?eld CEndM(L0), and de?ne rL, sL by rL = dimF M, sL = dimF H1(L0,M). If m > d(L0), then f(L,m) = rL(m ? 2) +1?sL. Since sL < rL [1], we get the inequalities m?1 ≤ f(L,m) ≤ rL(m ? 2) + 1. Case 3: M non abelian.

For any ?nite group X, let φX(s) denote the number of s-bases, that is, ordered s-tuples (x1,...,xs) of elements of X that generate X. We may identify L with a subgroup of AutM, and there is a simple group S such that M ≌ Sn. Let γL = |CAutM(L/M)|. It can be proved that if m > d(L0) then f(L,m) = ψL(m ? 1) + 1. Moreover, there is a constant γ, 0 < γ < 1, such that for any s ≥ max(2,d(L0)). And then, known information on the automorphism groups of simple groups allows to conclude that there is a constant c such that c|M|m?2 log|M| ≤ f(L,m) ≤ |M|m?2.

As a matter of fact, it turns out that in many instances the following simpli?ed statement is enough to get the desired conclusion: If m elements are really needed to generate a group G, then G has a normal section H/K that is either elementary abelian of rank ≥ m?1 or the direct product of at least a constant times 2m isomorphic simple groups.

3. Generating Permutation Groups

Every subgroup of Sym(n) can be generated by at most n elements [10]; this bound has been lowered, using the classi?cation, to [n/2] if n > 3 (P. Neumann, in [3]). But for special classes of permutation groups, such as transitive and primitive ones, it has long been suspected that substantially smaller bounds would hold. Theorem. [11] There is a constant C such that, if G ≤ Sym(n) is transitive, then d(G) ≤Cn / logn.

To prove this result, which was ?rst obtained for nilpotent groups in [12] and extended to soluble groups in [2], we used the approach via generator-critical groups introduced above, but also a bound on the number of abelian composition factors [10] and the following lemma, also proved in the soluble case in [2]:

Lemma. There is a constant b such that, if H is a subgroup of index n ≥ 2 of a ?nite group G, F is any ?eld, V is an FH-module of dimension a over F, then every submodule of the induced module W = V can be generated by [（abn）/logn] elements. The same ideas, plus information on linear groups which will be described in the next section, yield

Theorem. [6] There is a constant C such that, if G is a primi- tive permutation group of degree n ≥ 3, then d(G) ≤C logn/log(logn).

Note that the bounds given by the above theorems are asymptotically best possible [12], [15].

4. Generating Linear Groups

In this section K is a ?eld, V a K-vector space, dimK V = n is ?nite, and G is a ?nite subgroup of GLK(V ). The goal is to give bounds for d(G) (under suitable restrictions for G and K) in terms of n (and possibly of K). The starting point is the following

Theorem. [13] If G is completely reducible, then d(G) ≤ (3/2)n.

Note that this statement is valid for arbitrary ?elds, and contains no unspeci?ed constant!

If we restrict to irreducible groups, one might suspect that a better bound could be found; but the examples in [9] show that any bound for the number of generators of an irreducible linear group of degree n over an arbitrary ?eld K must be linear in n. So we assume that the ?eld K has ?nite degree d over its prime sub?eld.

Theorem. [7] Let V be a vector space of ?nite dimension n ≥ 2 over the ?nite ?eld K of order pd. There exists a constant C such that G is an irreducible subgroup of GLK(V ).

The study of the particular case of primitive linear groups is crucial in the proof of both theorems. But the result in this case is more satisfactory: it holds for arbitrary ?elds and the bound for the number of generators is much stronger.

Theorem. [14] Let K be a ?eld, V a K-vector space of dimension n ≥ 2, G a ?nite primitive subgroup of GLK(V ). Then d(G) ≤ C logn for some constant C. Also for linear groups, there are examples showing that these bounds have the correct order (up to the choice of the constants).