1. Introduction
All groups considered in this paper will be finite.
Given a group G, one can ask how many elements one should choose uniformly and at random to generate G with a certain given probability. The fact that an ordered r-tuple generates G is equivalent to the fact that is not contained in any maximal subgroup M of G. The probability that is contained in the maximal subgroup M of G is . This makes it relevant, in this context, to analyse the number of maximal subgroups of a group G with a given index n. Let us call this number .
Pak [
1], motivated by potential applications for the product replacement algorithm, widely used to generate random elements in a finitely generated group, introduced the following invariant.
Definition 1. Given a group G, we denote by the least positive integer k, such that the probability that G is generated by k random elements is at least .
Pak conjectured that for a group
G with minimum size of a generating system
,
. Here and throughout this paper, the symbol log will be used to denote the logarithm to the base 2, and we follow the convention that
, while we reserve ln to denote the natural logarithm, that is, the logarithm to the base
. Lubotzky [
2], with the help of the number of chief factors in a given chief series, and Detomi and Lucchini [
3], with the help of the number
of non-Frattini chief factors in a given chief series of
G and by considering their associate crowns, proved independently the validity of Pak’s conjecture.
We have obtained upper bounds for
and
in [
4] that improve some results of Lubotzky [
2] and Detomi and Lucchini [
3]. The bounds of [
4] depend on the next invariants, associated to the different types of primitive quotient groups according to the theorem of Baer [
5] (see also Theorem 1.1.7 in [
6]) and to the crowns associated to abelian and non-abelian chief factors (see Chapter 1 in [
6]). The first invariant is related to primitive quotient groups of type 1.
Definition 2. Let G be a group and let be a natural number. We denote by the number of crowns associated to complemented abelian chief factors of order n of G, that is, the number of G-isomorphism classes of complemented abelian chief factors of G.
Clearly, unless n is a power of a prime. The second invariant concerns non-abelian chief factors and is related to the primitive quotients of type 2.
Definition 3. Let n be a natural number. The symbol denotes the number of non-abelian chief factors A in a given chief series of G, such that the associated primitive group has a core-free maximal subgroup of index n.
Our third and fourth invariants concern also non-abelian chief factors and contain information about the primitive quotients of type 3 of the group.
Definition 4. Let n be a natural number. The symbol denotes the number of non-abelian chief factors A in a given chief series of G, such that A has order n.
Definition 5. Let n be a natural number. The symbol denotes the maximum of the lengths of the G-crowns associated to non-abelian chief factors of order n of G.
Denote by
the set of all prime powers greater than 1 and by
the set of all powers greater than 1 of the orders of non-abelian simple groups. The main results of [
4] are the following ones.
Theorem 1 (Theorem B in [
4])
. The number of maximal subgroups of index n of a d-generated group G satisfies the following bounds: Theorem 2. Let G be a d-generated non-trivial group. Then, for Other bounds for
can be found in [
7]. They depend on an invariant, defined there only for non-abelian characteristically simple groups, but that can be also defined for elementary abelian groups.
Definition 6. Let G be a group. For a characteristically simple group A, that is, a direct product of copies of a simple group S, denotes the largest number r such that G has a normal section that is the direct product of r non-Frattini chief factors of G that are isomorphic (not necessarily G-isomorphic) to A.
The main theorem of [
8] gives a simpler reinterpretation of the invariant
as the number of non-Frattini chief factors isomorphic to
A in a given chief series of
G.
The following result was proved in [
7]. We present here a corrected version available in [
9] due to a misprint in the originally published version.
Theorem 3 (Theorem 9.5 in [
9])
. Let G be a d-generated group. Then, where c and are two absolute constants. Here, the symbol denotes the maximum of the numbers , where A runs over the non-abelian characteristically simple groups A with , where denotes the least degree of a faithful transitive permutation representation of a group X, that is, the smallest index of a core-free subgroup of X.
The lower bound in Theorem 3 depends on the following result.
Lemma 1 (Corollary 9.3 in [
9])
. Let G be a group. Then, for some . Our aim in this paper is twofold. In the first place, we establish significant improvements of the lower bound of Theorem 3. We prove:
Theorem 4. Let G be a d-generated non-trivial group. Then, We obtain our lower bound by means of an improved version of Lemma 1. This is done in two ways. On the one hand, we show that the constant can be taken to be 2 and, on the other hand, we obtain a larger lower bound for the number of maximal subgroups of index x. Moreover, if we impose some restrictions to the composition factors of the group, the bounds are further improved (see Theorem 13).
Theorem 5. Let G be a group. Then, for some .
Here, the symbol denotes the excess integer part of x, that is, the smallest integer number n, such that . The symbol will denote the defect integer part of x, that is, the largest integer number n, such that .
The proof of Theorem 5 will be presented in
Section 2. It depends on some results proved in [
10] about maximal subgroups of small index in almost finite groups.
In the second place, we compare the bounds of Theorem 1 with the ones of Theorem 3. This is only possible if we precise the values of the constants appearing in Theorem 3. As far as we know, the values of the constants
c and
in Theorem 3 have not been estimated in the literature. We obtain, in
Section 3, the value of the constant
c of Theorem 3 and we prove the following result.
Theorem 6. Let G be a d-generated group. Then,where . A slight variation of the proof of Theorem 6 gives smaller values for some of the constants (see Theorem 20). We do it in
Section 3.
The following example, that appears in Example 3.4 in [
4], depends on a couple of constructions of subdirect products also introduced in that paper. In this example, we see that our bound for
improves dramatically the one of [
7].
Example 1. There are three isomorphism classes of 2-generated primitive groups of type 1 with socle of order 8, namely , and . We can construct 2-generated groups , , and with all possible crowns whose associated primitive quotients are isomorphic to , , and , respectively, by using Construction 3.3 in [4]. By using Construction 3.2 in [4], we can construct a subdirect product S of , , and in such a way the generating pairs of all these three groups are identified. Note thatthe other values of the ranks and the numbers of abelian crowns are zero. Therefore, , , , ; the other values are zero (in fact, S coincides with the direct product ). Since the indices of the maximal subgroups of are 7 and 8 (see for instance [11]), we conclude that and . The crowns of chief factors of order 8 in are minimal normal subgroups, in they are products of three minimal normal subgroups, while in they are products of two minimal normal subgroups. The crowns of chief factors of order 7 in and coincide with the corresponding chief factors. There is a unique crown composed of two central chief factors of order 3. Hence, S has chief factors of order 8, 8 chief factors of order 7, 2 chief factors of order 3, and 57 chief factors isomorphic to . Bearing in mind that , the bound of [7] is and . However, by Theorem 2 we obtain the boundthat is, As an example of application of Theorem 2, let us analyse the bounds a group with no abelian chief factor. We only have to compare
and
with
. Let us start with
. Let us denote by
the number of possible isomorphism types of socles of primitive groups of type 2 that possess a core-free maximal subgroup of index
n. Given a chief series of
G, let
denote the set of the non-abelian chief factors
A of
G in this series, such that the primitive group
has a core-free maximal subgroup of index
n. We have that
. If
, since
can be embedded in
, we find that
. Let
be the different isomorphism classes of chief factors in
. Then,
. Suppose that
A is isomorphic to
with
. Then, the number of chief factors
F isomorphic to
such that
has a core-free maximal subgroup of index
n is bounded by
, which coincides with the number of chief factors of
G isomorphic to
by the main result of [
8]. Hence,
This proves the next result.
Proposition 1. Let G be a group and . Then, Therefore, to compare
with
, our first interest is to obtain a bound for
. This will be done in
Section 3, where we obtain the following result.
Theorem 7. for all n.
To compare
with
, it is enough to take into account the following result formulated as a question by Cameron [
12], who attributed its proof to Teague in Note (ii) at the end of his paper and generalises the well-known fact, derived from the classification of finite simple groups, that for each natural number there are at most two simple groups of that order.
Theorem 8 (see Theorem 6.1 in [
13])
. Let S and T be non-isomorphic finite simple groups. If for some natural numbers a and b, then and S and T are either or , or are and for some and some odd q. From this, we conclude that
, and
unless
n is one of the order of the exceptional groups of Theorem 8. Since
, we find that
This proves:
Theorem 9. Let G be a d-generated group with no abelian chief factors. Then, .
Example 2. If G is a group such as in Theorem 9, with no abelian chief factors, the upper bound of Theorem 3 gives that . Since , our upper bound improves dramatically the one of [7]. For soluble groups, the contribution of the abelian chief factors to
in Theorem 3 is contained in the term
. We have the following improvement of Theorem 19 for soluble groups, that will be proved in
Section 3.
Theorem 10. Let G be a soluble d-generated group. The number of inequivalent irreducible G-modules of size n is at most , where and . In particular, .
Now, let us compare
with
. First of all, note that
is bounded by the number of irreducible
G-modules of size
n. As a result of combining Propositions 6.1 and 7.1 and Lemma 7.2 of [
7], we obtain the following stronger form of Corollary 7.3 in [
7] that appears as an intermediate step in the proof of Theorem 3.
Corollary 1. Let G be a d-generated group. There exists a constant , such that the number of irreducible G-modules of size n is at most The value of the constant
is not specified in [
7]. Again, we precise this bound in
Section 3.
At a first glance, we can use Corollary 1 to obtain that Theorem 3 follows from Theorem 2 and the results of Sections 5 and 6 in [
7]. By Corollary 1,
On the other hand, we know by Proposition 1 that
. By Theorem 7,
. Finally, by Theorem 8,
. We conclude that
Hence, Theorem 3 can be obtained as a consequence of Theorem 2.
Unless otherwise stated, we will follow the notation of the books [
6,
14]. Detailed information about primitive groups and chief factors, crowns, and precrowns of a group can be found in Chapter 1 in [
6].
2. Lower Bounds for the Number of Maximal Subgroups of a Given
Index in a Group
In this section we will obtain the inequality of Theorem 4. For this, we will need the results of [
10] on the existence of conjugacy classes of subgroups of small indices in almost simple groups and some arithmetical properties about the smallest index of a core-free maximal subgroup of an almost simple group. These results are needed to obtain lower bounds for the number of maximal subgroups of a given index in a group
G and for
. The results depend on some classes of simple groups that we define now.
Notation 1. Let be the class of simple groups composed of the following groups:
The linear groups , where is a power of a prime p with f odd;
The linear groups , with q a prime power and or ;
The symplectic groups , .
Notation 2. Let be the class of simple groups composed of the following groups:
The Mathieu group ;
The O’Nan group ;
The Tits group ;
The linear groups , , , ;
The linear groups , with a prime power;
The linear groups , q a prime power;
The linear groups , q a prime power;
The unitary group ;
The orthogonal groups , q a prime power;
The orthogonal groups , ;
The exceptional groups of Lie type , ;
The exceptional groups of Lie type , ;
The exceptional groups of Lie type , q a prime power.
If R is a primitive group, we denote by the smallest index of a core-free maximal subgroup of R.
We say that a maximal subgroup of a simple group S is ordinary if its conjugacy class in S coincides with its conjugacy class in .
Theorem 11 (Theorem A in [
10])
. Let S be a simple group and let R be an almost simple group, such that . We can assume that .If S belongs to , then S has at least two conjugacy classes of maximal subgroups of the smallest index and there exists a number , depending only on S, such that R has at least two conjugacy classes of core-free maximal subgroups with index or one conjugacy class of core-free maximal subgroups with index ;
If S belongs to , then S has at least two conjugacy classes of maximal subgroups of the smallest index and there exists a number , depending only on S, such that R has a conjugacy class of core-free maximal subgroups with index ;
If S does not belong to , then S has a conjugacy class of ordinary maximal subgroups. In particular, the smallest index of a core-free maximal subgroup of R is also ;
In all cases, and ;
If, in addition, , S is not of the form with , , and , or and , S is not of the form with and , and with and , then .
Lemma 2. Suppose that G is a primitive group of type 2 with socle isomorphic to , where S is a non-abelian simple group.
If , then G has at least maximal subgroups of index or at least maximal subgroups of index , where is defined in Theorem 11;
If , then G has at least maximal subgroups of index , where is defined in Theorem 11;
If , then G has at least maximal subgroups of index .
Proof. Suppose that
G is not an almost simple group and that
, where
is the set of all conjugate subgroups of a simple normal subgroup
of
, write
and
. By a result of Gross and Kovács ([
15], see also Theorem 1.1.35 in [
6]), there exists a bijection between, on the one hand, the conjugacy classes in
G of supplements
U of
in
G, such that
and, on the other hand, the conjugacy classes in
of supplements
of
in
. This correspondence sends conjugacy classes of maximal subgroups of
G to conjugacy classes of maximal subgroups of
and conjugacy classes of complements of
M in
G to conjugacy classes of complements of
in
. From this, it follows that every primitive group of type 2 has maximal subgroups
U, such that the projection
of
onto
is a non-trivial proper subgroup of
. In this case, by Proposition 1.1.44 and Remarks 1.1.46 in [
6],
G can be regarded as a subgroup of
, where
Z is an almost simple group,
is a transitive group of degree
, and
for a maximal subgroup
H of
Z.
By Remarks 1.1.46 in [
6], if
H is a maximal subgroup of
Z and
, then
and, by Proposition 1.1.44 in [
6],
U is a core-free maximal subgroup of
G. Moreover, all elements in its conjugacy class, consisting of
elements, are also core-free maximal subgroups of the same index.
Suppose that . Then, we can consider a core-free maximal subgroup H of Z of index and construct . Then, the conjugacy class of U in G contains at least elements.
Suppose that
. Then,
Z contains two non-conjugate core-free maximal subgroups
and
of index
, and so if
,
, then
, or
Z contains a core-free maximal subgroup
of index
, and so if
, then
. By the mentioned result of Gross and Kovács ([
15], see also Theorem 1.1.35 in [
6]),
and
are in different conjugacy classes in
G. It follows that there are at least
maximal subgroups of
G of index
or at least
maximal subgroups of
G of index
.
Finally, suppose that . Then, Z contain a core-free maximal subgroup H of index , and so if , then . In this case, the conjugacy class of U in G contains elements. □
Remark 1. Consider the O’Nan simple group , and let . According to [11], all the core-free maximal subgroups of A have index greater than its order. Let . Let D be the diagonal subgroup of the base group of W, let , and let . In the primitive pair with simple diagonal action (see Definition 1.1.42 in [6]), we have that is smaller than the index of any maximal subgroup of the form (see Remarks 1.1.46 in [6]). Hence, the smallest index of a core-free maximal subgroup of G is smaller than the index corresponding to the product action with the core-free subgroup of smallest index of A. What we prove in Lemma 2 is that there are maximal subgroups of indices and . Notation 3. For a group G and a prime p we denote by the number of central p-chief factors of G in a given chief series.
Notation 4. Given a natural number and a chief factor A of a group G, we denote by the number of maximal subgroups of G of index n for which the socle of the associated primitive group is isomorphic to A.
Now, we are in a position to establish our lower bound.
Theorem 12. Let G be a group and let A be a non-Frattini chief factor of G isomorphic to , with k a natural number and S a simple group.
If , then for some and ;
If , then for ;
If S is non-abelian and , then for ;
If , with , then for ;
If , then . Moreover, if , then .
Proof of Theorem 12 . Suppose, first, that
A is non-abelian. As in the proof of Corollary 9.3 in [
7], there exists a normal section
of
G that is the direct product of
chief factors isomorphic to a direct product
of
r copies of a simple group
,
, with
. Consider the groups
,
. Then, the
are different normal subgroups of
G and the quotients
are groups with a unique minimal normal subgroup isomorphic to
A.
Suppose that . According to Lemma 2, there exists an integer , such that has at least maximal subgroups of index or has at least maximal subgroups of index . Let be the number of , such that has at least maximal subgroups of index and let be the number of , such that has at least maximal subgroups of index . It follows that G has at least maximal subgroups of index and at least maximal subgroups of index . Suppose that . Then, . Hence, G has at least maximal subgroups M of index with . Suppose, now, that . Then . It follows that G has at least maximal subgroups M of index with .
Suppose, now, that . By Lemma 2, there exists an integer such that has at least maximal subgroups of index for . For , we have that .
Finally, suppose that S is non-abelian and . By Lemma 2, has at least maximal subgroups of index for . Then, for , we obtain that .
Assume that is a power of the prime p and that there exist normal subgroups of G such that is a direct product of r non-Frattini chief factors of G isomorphic to an elementary abelian group A of order n. Let and let be a maximal subgroup supplementing . Consider the primitive group . Then, has a minimal normal subgroup , namely the precrown associated with and M, and a maximal subgroup of trivial core.
Assume that . Then, and so . By the maximality of , . It follows that the conjugacy class of in G has exactly elements.
Assume that . Then, and is a central chief factor, in particular, is a prime number.
Suppose that
has
a central
G-chief factors and
b non-central
G chief factors in a given chief series. Note that, in the case that
,
and
. For each of the
b non-central chief factors, we can obtain with the previous construction
n maximal subgroups, they have different core since the core contains the product of all other chief factors. Hence, we obtain at least
maximal subgroups. Now, suppose that
and consider the
a central chief factors, in this case,
is prime. By the main result of [
8],
G has a normal subgroup with elementary abelian quotient of order
. This group has
subgroups of index
p, and all of them have in their core the non-central chief factors. It follows that
. If
, then
. If
, then
. If
, then
because
, and so
. The result follows. □
Remark 2. The bounds of Theorem 12 for abelian chief factors are attained in groups which are direct products of copies of a primitive group of type 1 with non-cyclic socle or in and .
In order to simplify the statement of the main theorem of this section, we propose the following definition.
Definition 7. For a group G and a chief factor of G with S a simple group and k natural, As a consequence of Theorem 12, we obtain a lower bound for , the inequality of Theorem 4.
Theorem 13. Let G be a d-generated group. Then,where A runs over the non-Frattini chief factors of G. Proof. By Proposition 1.2 in [
2],
. Let
B be a non-Frattini chief factor of
G, such that
. Let
with
T a simple group.
Suppose that
. Then,
for
and
. In this case,
Suppose that
. Then,
for some
. Hence,
Suppose that
for a prime
p and that
G has exactly one or two central chief factors isomorphic to
B in a given chief series. Then,
and so
Suppose that
B does not satisfy any of the previous properties. Then, for
,
and so
The inequality holds trivially. □
Remark 3. Since the smallest index of a maximal subgroup of a non-abelian simple group is at least 5, if with , Consequently,where A runs over the set of all non-abelian chief factors in a given chief series of G. Moreover, since , we have that, if N is such that and B is a chief factor of G satisfying that , then Therefore, this bound improves the boundgiven in Theorem 9.5 in [7]. Example 3. Let be the alternating group of degree 5. According to a result of Wiegold (Theorem in [16]), since S is 2-generated and has order , we have that for all . Let G be a direct product of copies of S. We have that . Moreover, . Hence, the lower bound we obtain is , that is, . The bound obtained by [7] for this group was just , because and . This example also highlights the fact that the formula for the lower bound only gives interesting values different from in groups with a large number of chief factors isomorphic to a non-abelian characteristically simple group in a given chief series. In fact, in order to obtain a non-trivial value for the lower bound for with the formula of Theorem 3 in a direct product of copies of , and assuming that by our analysis, we need . In this case, has 28 generators (Theorem in [16]) and , that is, . Our bound in this case is improved to , that is, . Even the most general bound of Theorem 4 would give , that is, . Remark 4. The effort to show that for every simple group S there exists an integer such that every almost simple group with socle S has a maximal subgroup of index or is necessary in order to make the lower bounds for useful. By Theorem 11, for all simple groups. In particular, for all simple groups S. Suppose that in the quotient the coefficient is greater than . Then, we see that the lower bound is trivial for the Janko sporadic group of order and with : for the groups of the form , with generators by Theorem in [16], and so , so in this case we only obtain the trivial bound . 3. Upper Bounds for the Number of Maximal Subgroups of a Given Index in a Group
3.1. Bounds for the Number of Socles of Primitive Groups of Type 2
In Lemma 2.3 in [
17], it is shown that the symmetric group
has at most
isomorphism classes of non-abelian simple subgroups. We will adapt the proof in this paper in order to give precise values to the constants associated with this bound.
Lemma 3. The number of isomorphism classes of non-abelian simple subgroups of the symmetric group for satisfies the inequalities , whereand Proof. The number of subgroups of alternating type or sporadic type is at most
. By all results mentioned in the proof of Theorem 11, the minimum degree of a permutation representation of a simple group
of Lie type of rank
k over
is
, with the only exception of
, already considered. Since
, we obtain that
. For each
k, the number of possibilities for odd
q is at most
(namely
,
,
,
) and for even
q it is at most
(namely
,
,
,
). Once
q and
k are given, there are at most 7 possibilities for the simple group
T (up to isomorphism). Recall that the harmonic sum
satisfies the inequality
, as we can check by using the integral test. Hence, the number
of non-abelian simple subgroups
is bounded by
Since the second derivative of the function
is negative, the function
is concave. Therefore, the graph of
lies below its tangent on any point, for example, the tangent on
, that is,
as we can compute with Maxima [
18]. □
It is also shown in Lemma 2.3 in [
17] that the number of almost simple subgroups of
up to isomorphism is at most
. We specify the bound in that lemma by adapting its arguments and show that the exponent 6 can be reduced to 3 by using Theorem 11. We need the following bound for the number of subgroups of the outer automorphism group of a non-abelian simple group.
Lemma 4 (Theorem B in [
10]).
The number of subgroups of the outer automorphism group of a non-abelian simple group S is bounded by . Lemma 5. The number of isomorphism classes of almost simple subgroups of is at most , where and are the functions defined in Lemma 3.
Proof. Let be an almost simple subgroup and let . There are possibilities for T. By Lemma 4, we know that the number of subgroups of is bounded by . Therefore, contains at most almost simple subgroups. The results follow. □
Let us denote by the largest natural number r, such that there exists a natural c, such that . It is clear that , and the equality holds if, and only if, n is a power of 2. Moreover, is the greatest common divisor of the exponents of the different primes appearing in the decomposition of n as a product of prime powers. Note that if , then s divides the exponents of the different primes appearing in the prime power decomposition of n, in particular, .
The following result follows from Theorem 1.1.52 and Proposition 1.1.53 in [
6] and a result of Gross and Kovács [
15] whose proof can be found in Theorem 1.1.35 in [
6].
Proposition 2. Let P be a primitive group with a minimal normal subgroup , where for , is isomorphic to a given non-abelian simple group S. Let and let U be a maximal subgroup of P of a given index .
Exactly one of the following three conditions holds:
Condition 1. . In this case, there exists a maximal subgroup of X, such that , , and for some m;
Condition 2. , where is such that there exists an integer b with . In this case, ;
Condition 3. and, in this case, .
There exists a natural bijection between the conjugacy classes of maximal subgroups of X of trivial core and the conjugacy classes in P of core-free maximal subgroups satisfying the above Condition 1.
Proposition 3. The number of isomorphism types of minimal normal subgroups of primitive groups of type 2 with a core-free maximal subgroup of index n satisfies the inequalities Proof. Let P be a primitive group with a unique minimal normal subgroup isomorphic to , where S is a non-abelian simple group, and with a core-free maximal subgroup U of index n.
Let and consider (the values are valid in this context).
We first look for the possibilities of A corresponding to primitive groups P of type 2 with a core-free maximal subgroup satisfying the Condition 1 of Proposition 2. We must consider simple groups S having an almost simple group with a core-free maximal subgroup of index . By Lemma 3, the number of the possibilities for A is at most . The Condition 1 can only hold if P is almost simple or . In the former case, by Lemma 3, the number of possibilities for A is at most . In the latter case, we obtain for each a number of possibilities for A bounded by . Hence, the total number of possibilities for A of this type is at most .
Now, we look for the possible socles of P satisfying the Condition 2 of Proposition 2. We must look for simple groups S with order and, for each divisor a of s, we can have a socle where . Since for each value of there are at most two simple groups of this order, we find that the number of possibilities for A is less than or equal to .
Finally, let us study the possible socles of P satisfying the Condition 3 of Proposition 2. Then, S is a simple group of order and we have at most two non-abelian simple groups of order . This implies that the number of possibilities for A is less than or equal to .
It follows that the total number
of possible isomorphism types of the minimal normal subgroups of a primitive group of type 2 with a core-free maximal subgroup of index
n satisfies the inequality
□
We isolate in a few technical lemmas some results that will be used to obtain bounds for .
Lemma 6. Let be the function of Lemma 3. Then, for , Proof. Since the functions defined by
,
and
are decreasing, for
we find that
We conclude that, for
,
It follows that
v is a decreasing function in
. Therefore, for
,
. Consequently, for
,
□
Lemma 7. The functionsatisfies the inequality for all . Proof. Consider the function , that is a decreasing function because its derivative is negative. Therefore, for , . Consequently, . □
We are now in a position to prove Theorem 7.
Proof of Theorem 7 . The claim for
follows as a consequence of Proposition 3 and Lemmas 3, 6 and 7. The library of primitive permutation groups of small degree of
Magma (see [
19]) contains all primitive permutation groups of degree at most 4095, that were determined in [
20]. From the information in this database, we conclude that the number of primitive groups of degree
n, and so the number of isomorphism types of socles of primitive groups of degree
n, is bounded by
for
. □
3.2. Bounds on the Number of Inequivalent Irreducible G-Modules
We can go further if we specify the values of the constants of this linear combination giving rise to the values of the constant c. The existence of these constants follows from counting arguments in which some terms are known to be , but we have not found any explicit value for them. We begin by estimating the constant of the following result.
Proposition 4 (Proposition 2.4 in [
7])
. There exists an absolute constant such that, for each n, the group has at most conjugacy classes of primitive subgroups. We will prove the following result.
Proposition 5. The value of the constant of Proposition 4 can be taken to be .
The proof of Proposition 4 depends on the following result.
Theorem 14 (Theorem I in [
21])
. The number of conjugacy classes of primitive subgroups of the symmetric group is at most , where c is some absolute constant and denotes the maximal exponent of a prime in the prime factorisation of the natural number n. Consequently, has at most conjugacy classes of primitive subgroups. We will obtain a value for this constant c.
Theorem 15. The constant c of Theorem 14 can be taken to be .
In our arguments, we will replace the term by , the largest number r, such that for a natural number m, that is, the greatest common divisor of the exponents in the decomposition of n as a product of prime powers. If is a power of a prime, then , while, in general, .
We use the following result of Pálfy.
Lemma 8 (see Lemma 3.4 (ii) in [
22])
. The number of conjugacy classes of maximal, irreducible, soluble subgroups of (p prime) is at most The following two results, of Kovács and Robinson, and Wolf, respectively, concern completely reducible subgroups of .
Lemma 9 (Theorem in [
23])
. If G is a completely reducible subgroup of , with p a prime, then G can be generated by at most elements. Lemma 10 (Theorem 3.1 in [
24])
. A soluble completely reducible subgroup of has order at most , where In Lemma 1.5 in [
21], it is shown that the number of completely reducible soluble subgroups of
is at most
. We specify the term
. In the following results, we will follow the notation and the proofs of [
21] and we will indicate only the differences. Hence, these are best followed with [
21] at hand.
Lemma 11. The number of completely reducible soluble subgroups of the linear group is at most , where Proof. We follow the proof of Lemma 1.5 in [
21]. It is shown at the end of the first paragraph there that
M can be chosen in at most
ways. By Lemma 10, once fixed a maximal soluble completely reducible subgroup
M of
, by Lemma 10 we find that
. By Lemma 9, every completely reducible subgroup
G of
M can be generated by at most
elements. Therefore, the number of completely reducible subgroups
G of
M is at most
. Hence, the number of completely reducible soluble subgroups of
is bounded by
. □
In Lemma 2.3, in [
21], it is shown that the number of subgroups
X of
such that
for some irreducible subgroup
G of
is at most
, where
denotes the generalised Fitting subgroup of
G. We specify the term
in this expression.
Lemma 12. The number of subgroups X of , such that or some irreducible subgroup G of is at most , where is defined in Lemma 11.
Proof. We can argue as in the proof of Lemma 2.3 in [
21], where it is shown that
can be generated by three soluble completely reducible subgroups of
. □
If we replace the term
by
in the proof of Lemma 2.7 in [
21], we obtain the following result, where the 8 is replaced by
.
Lemma 13. With the same notation of Lemma 2.7 in [21], if P is a p-subgroup of , then . The following result specifies the bound
that appears in Theorem 2.8 in [
21].
Theorem 16. The number of irreducible subgroups G of is at most , where is defined in Lemma 11.
Proof. We can follow the proof of Theorem 2.8 in [
21] by replacing the terms
by
,
by
, and 8 by
according to Lemmas 11–13, respectively. We obtain that the number of choices for
G is at most
□
The following result specifies the bound
of Lemma 3.2 in [
21].
Lemma 14. The number of conjugacy classes of subgroups F of , such that for some primitive subgroup G of is at mostwhere is defined in Lemma 3. Proof. We follow the proof of Lemma 3.2 in [
21]. If
F acts regularly on
, we have at most
choices for
F up to conjugacy. If
F is not regular and has diagonal action, then there are at most
choices for
F up to conjugacy. Suppose that
F is not regular on
and has a wreath product action. Then there are at most
choices for
. By Lemma 5,
has at most
almost simple subgroups up to isomorphism and so
can be chosen in at most
as an abstract group. Once
is fixed up to isomorphism,
has at most
core-free maximal subgroups of index
by Theorem 1.3 in [
2]. Hence there are
possibilities for the conjugacy class of
in
. We can distinguish the case
and the rest of the cases, corresponding to
. Consequently, the number is bounded by
□
The following result specifies the bound
on the number of subgroups of
given in Corollary 3.3 in [
22]. It is based on the proof of this last result.
Theorem 17. The number of subgroups of is at most Now we can prove Theorem 15.
Proof of Theorem 15 . We follow the proof in Proof of Theorem I in [
21].
Assume that
G has abelian socle and
, we obtain at most
choices for
G up to conjugacy.
Suppose now that
G has a non-abelian socle
, where
L is a simple group. By Lemma 14,
F can be chosen in at most
ways in
up to conjugacy. The element
can be chosen in at most
ways. The total number of subgroups of
is at most
. Given
, there are at most
choices for
. It follows that the number of choices for
is at most
. Let
and
. Since
, we obtain that
G can be chosen in at most
ways.
In order to obtain a bound for the number of conjugacy classes of primitive groups of degree n, it will be enough to find a bound on .
Since we must obtain a bound for
of the form
, it will be enough to maximise
. We can check, with the help of a computer algebra system, such as Maxima [
18], that
is bounded by
(the bound is attained if
and
), while the bound for
is bounded by
(the bound is attained for
,
). Therefore, since
for
and
, we obtain that
Consequently Theorem 14 holds with
. □
Finally, we can prove Proposition 5.
Proof of Proposition 5 . To obtain the constant
of Proposition 4, in which we need a bound of the type
, we must find a bound for
, that will correspond to
. With the help of Maxima [
18], we show that
, where
, with the maximum attained in
, and
, where
, with the maximum attained in
. Since
, we have that
where
.
However, we see that for
, the value of
, corresponding to
, satisfies that
, and
, also corresponding to
, satisfies that
. As above, for
, we have that
where
. This bound also holds for all values of
as we can check with
Magma (see [
19]). □
Our next step will be to estimate the constant associated to the number of conjugacy classes of transitive subgroups of the symmetric group
of degree
n. In the next results we will follow the notation and the arguments of [
7]. Hence, it will be convenient for the reader to have that paper at hand.
In order to avoid confusion between the constants in [
7] and our constants, we will use capital letters to refer to the constants of [
7] and reserve the lowercase letters for our constants when they are different. In Theorem 3.1 in [
7], it was shown that the number of conjugacy classes of transitive
d-generated subgroups of the symmetric group
of degree
n is at most
, where
and
was the constant of Proposition 5 whose value can be taken to be equal to
and so
takes the value
. In this subsection, we will show that the value of the constant
can be reduced to
.
Theorem 18. The number of conjugacy classes of transitive d-generated subgroups of the symmetric group of degree n is at most , where .
Proof. It is enough to follow the proof of [
7, Theorem 3.1]. We use the notation of this result. We will argue by induction on
n and assume that
. Given a
d-generated transitive subgroup of
and a system
of blocks for
T, such that
and
the stabiliser of
, such that
acts primitively on
, then
T can be regarded as a subgroup of
. Let
P be the image of
in the symmetric group on
, isomorphic to
, and let
be the kernel of the action of
T on the blocks. Then,
can be naturally embedded into
and
T into
. We can divide the
d-generated transitive subgroups of
into three families:
The first family corresponds to the case in which
P does not contain the alternating group
or
. We have that the number of conjugacy classes of
d-generated groups in this family is bounded by
The second family corresponds to the case in which
,
P contains
, and
. The number of
d-generated groups in this family is bounded by
The third family corresponds to the case in which
,
P contains
, and
. The number of
d-generated groups in this family is bounded by
Note that
. In order to obtain a value of
, such that
, it will be enough to obtain a value of
, such that
and
. The condition
is equivalent to
. By taking logarithms, it is equivalent to
We maximise the left hand side with the help of
Maxima [
18] and using that
and
. We obtain that the maximum of this expression is less than
and so the value of
satisfies this inequality. We have to show that
. Since
, the condition
is equivalent to
By taking logarithms, it is equivalent to
We also use
Maxima [
18] to check that the maximum of the first expression is
. □
We recall the constant associated to the number of epimorphisms from a d-generated group onto a transitive group of degree n.
Proposition 6 (Proposition 4.1 and Remark 4.2 in [
7])
. Let G be a d-generated group and T a transitive group of degree n. Then, there are at most epimorphisms from G onto T, where . The following result is Proposition 5.6 in [
7], with the precise value of the constant
.
Proposition 7. There exists a constant , such that if H is a quasisimple group and U is an absolutely irreducible -module (where F is a finite field), such that , then one of the following holds:
and W is the natural -module;
, a classical group over , and , where is the natural module for .
In fact, the constant satisfies these conditions.
Proof. This follows as a consequence of [
25,
26,
27]. □
This gives a value of
to the constant defined before Proposition 5.7 in [
7].
In Proposition 5.9 in [
7], it is shown that the number of conjugacy classes of primitive
d-generated groups
P of
is at most
, where
. A slight variation of the same arguments can be used to give a lower bound for this number.
Proposition 8. The number of conjugacy classes of primitive d-generated subgroups P of is at most , where , .
Proof. We follow the same arguments of Proposition 5.9 in [
7] and we will show how to modify that argument to obtain our bound. We divide the primitive groups
P into several families.
The family 1 corresponds to
. There are, at most,
conjugacy classes of primitive
d-generated groups in this family.
The family 2 corresponds to
and
P almost fixing a non-trivial tensor product decomposition
of
W. The induction argument shows that there are at most
choices for
Y up to conjugacy in
, and so the number of conjugacy classes of primitive
d-generated groups in this family is bounded by
The family 3 consists of the groups in which
and
P does not almost fix any non-trivial tensor product decomposition
of
W. The subfamily 3.1 corresponds to the case in which
is the product of a
q-group
T of symplectic type and a cyclic group
C of order coprime to
p and
q. We obtain that the number of conjugacy classes of primitive
d-generated groups in this subfamily is bounded by
The subfamily 3.2 corresponds to the case in which
is a central product of
k copies of a quasisimple group
S and a cyclic group
C. The number of conjugacy classes of primitive
d-generated groups in this family is bounded by
Now, since we can assume that
, we obtain that
The inequality
is equivalent to
which is, in turn, equivalent to
and is satisfied for
,
. Since all other terms involved the maximum are less than or equal to the second one, the equality holds. □
In Proposition 6.1 in [
7], it is shown that the number of conjugacy classes of
d-generated irreducible subgroups of
is at most
, where
. In Proposition 7.1 in [
7], it is proved that if
G is a
d-generated group and
T is an irreducible linear subgroup of
, then there are at most
epimorphisms from
G onto
T, where
Given an irreducible subgroup of
, we have that the number of
T-conjugacy classes of epimorphisms from a group
G onto
T is at most
by Lemma 7.2 in [
7]. As a consequence, we can obtain the following result (compare with Corollary 7.3 in [
7]).
Corollary 2. Let G be a d-generated group. There exists a constant , such that the number of irreducible G-modules of size n is at most The value of the constant
is not presented in [
7], but it seems clear that the arguments in this paper that the constant
satisfies the condition.
3.3. Determination of the Constants
We are now in a position to complete the proof of Theorem 6.
Proof of Theorem 6 . The arguments of the proof of Corollary 9.1 in [
7] show that the constant
appearing there is essentially the same as the constant
of Corollary 2. The constant
c such that the number of maximal subgroups of index
n of
G is bounded by
can be taken as
. This is the constant that appears in Theorem 3. □
We can present the arguments of Sections 6 and 7 of [
7] in a different way to improve the bound for the number of irreducible
G-modules of order
n.
Theorem 19. Let G be a d-generated group. The number of irreducible non-equivalent G-modules of size n is at most , where and .
Proof. As in Propositions 6.1 and 7.1 in [
7], let
T be an irreducible
d-generated subgroup of
and let
H be a subgroup of
T, such that the representation of
T is induced from a primitive representation of
H. Let
W be a primitive
H-module such that
. Let
P be the image of
H in
and
. Set
. Then,
is a transitive group of degree
, where
, and
T is a subgroup of
.
We divide the
d-generated irreducible subgroups of
into two families, as in Proposition 6.1 in [
7].
In the first family,
. Note that
and so
, that is, we are in Case 1 in the proof of Proposition 7.1. The argument in the proof of Proposition 6.1 in [
7], with the replacement of
by
and
by
shows that the number of conjugacy classes of
d-generated irreducible subgroups in the first family is bounded by
Now, we obtain a bound for
. The argument in Case 1 of Proposition 7.1 in [
7] shows that
By Lemma 7.2 in [
7], we conclude that the number of irreducible
-modules of size
n obtained starting from a primitive linear group
P with
is bounded by
In the second family,
. This corresponds to Case 2 in Proposition 7.1 in [
7]. The number of choices of conjugacy classes of primitive
d-generated groups in this family, according to the proof of Proposition 8, family 1, is bounded by
. As in the proof of Proposition 6.1 in [
7], we can consider two subfamilies. In the subfamily 2.1, there are at most
conjugacy classes of
d-generated irreducible subgroups, while in the subfamily 2.2, there are at most
conjugacy classes of
d-generated irreducible subgroups. In Case 2 of Proposition 7.1 in [
7], we see that
By Lemma 7.2 in [
7], we conclude that the number of irreducible
-modules of size
n obtained starting from a primitive linear group
P with
is bounded by
because
.
Putting everything together, we obtain that the number of irreducible
G-modules of size
n is bounded by
□
Proof of Theorem 10 . To determine the values of the constants, we can follow the results needed to prove Theorem 19 avoiding all arguments with insoluble groups. We will only state the differences.
First of all, we can use the bound of Lemma 11 as a bound for the number of irreducible soluble subgroups of . We can replace the bound of Theorem 16 by this value. We use the arguments of the proof of Proposition 4, but taking into account that now only the term appears, to obtain a bound of the form for the number of conjugacy classes of primitive subgroups of . We obtain that the corresponding value of is .
The result corresponding to Theorem 18 says that the number of conjugacy classes of soluble transitive d-generated subgroups of the symmetric group is at most . We can use the same arguments than in the proof of Theorem 18, but here only the first family should be taken into account. By induction, we obtain that is obtained for .
The corresponding version of Theorem 19, that is, the number of irreducible G-modules of size n for a d-generated soluble group G is at most , holds then for and . □
Note that for soluble groups, the exponent of n in the bound can be reduced by with respect to Theorem 19.
The fact that the number of crowns associated to chief factors of order n is obviously bounded by the number of representations gives an immediate bound for the number of irreducible G-modules of dimension r over a field of p elements that is useful for modules of small dimension.
Proposition 9. Let G be a d-generated group. The number of G-modules of size , where p is a prime and , is at most .
Proof. Let , let V be a G-module over G and let be a basis of V as a vector space over . Then, the action of G on V is completely determined by the action of each of the on the , say . Each of these images can take at most values. This gives the result. □
Proposition 9 makes clear that the bound of Theorem 19 is only useful for prime-power values
with
r big, say
otherwise Proposition 9 gives better bounds for the number of irreducible
G-modules of size
. For example, if
G is a
d-generated group, then Proposition 9 gives better bounds for the number of irreducible
G-modules of size
with
p a prime.
Putting together Theorem 19 and Proposition 9, we obtain the following result.
Theorem 20. The number of non-equivalent irreducible G-modules of size , where p is a prime and , is at mostwhere and are the constants of Theorem 19.