Computing the subgroup lattice of a permutation group

John Cannon, Bruce Cox and Derek F. Holt

Abstract

A new method for computing the full lattice of subgroups of a finite group is described.

1 Introduction

In this paper, we describe a new method for computing the complete subgroup lattice of a finite group. It has been implemented within the Magma computational algebra system [1] for finite permutation groups, and its performance is very encouraging

Until recently, the only genuinely feasible approach to this problem was based on the cyclic extension method. This is one of the oldest existing group theoretical algorithms, and was first introduced by Neubüser in 1960 [10]. The idea is to start by finding all cyclic subgroups of prime order, which we regard as forming the first layer in the lattice. The subgroups H in subsequent layers are formed from those K in the previous layer, as H = ⟨K, g⟩, where K ⊲H. Clearly only the soluble subgroups will be found by this method. The insoluble subgroups can be constructed in a corresponding manner, by using the perfect subgroups as the first layer. For this, a complete stored list of the isomorphism classes of finite perfect groups up to a given order n is required, and the subgroup lattice found by this method can only be guaranteed correct for groups of order up to n. See Chapter 6 of [2] for a detailed description of this approach and further references.

The cyclic extension method is generally extremely fast for groups of order up to about 1000, and is tolerable up to order 10 000. Until relatively recently, this was adequate, and it would have been impractical to go much beyond this order anyway. However, the range of most algorithms for finite groups has been increasing dramatically over the past 10 years or so, and so it is reasonable to expect a corresponding increase in the power of a subgroup lattice algorithm. The main barrier with the cyclic extension method is the policy of storing all perfect groups, which starts to becomes impractical with increasing order. There are 66 isomorphism classes of perfect groups of order up to 10 000. These were categorized in [11], and they are stored in the latest implementations that use this approach. There are a further 163 perfect groups up to order 50 000, but then at 61 440, the exact number becomes unknown. (See Chapter 5 of [8] for tables of finite perfect groups.)

Our method is to start by finding a series of normal subgroups

1 = N_{0} ≤ N_{1} ≤ … ≤ N_{r} = L ≤ G

of our given group G, such that each N_{i+1}/N_{i} is elementary abelian and G/L has no nontrivial soluble normal subgroup. We shall call groups with this last property trivial-Fitting groups, since they have trivial Fitting subgroups. Of course, L is uniquely defined as the largest normal soluble subgroup of G, and G/L = 1 if G itself is soluble.

For trivial-Fitting groups, we either store representatives of the conjugacy classes of all subgroups (after computing it once and for all, usually using the cyclic extension method) or, for larger groups, where this would be expensive in storage space, we store this information just for the maximal subgroups. In the latter case, we can find representatives of all classes when required, by applying the algorithm recursively to the maximal subgroups, and then testing for conjugacy of the resulting subgroups in G. This information is all stored in a database of trivial-Fitting groups, where some form of compressed data storage is used to save space.

In fact, for orders up to 60^{6}, which is way beyond the current range of application, all nontrivial trivial-Fitting groups are automorphism groups of simple groups, or of direct products of simple groups. There are just 98 of these of order up to 100 000, and 154 of order less than 216 000. More importantly, they are relatively easy to list from tables of finite simple groups, and it would probably be feasible to store information for all of them (at least for maximal subgroups) up to order a million. To find the maximal subgroups explicitly for the larger trivial-Fitting groups, we generally used information in [5] to determine their number and structure, and then located them by some combination of intelligence and random search.

Having found class representatives of subgroups of G/N_{r}, we lift these successively through the layers, going down the series, finding conjugacy class representatives of subgroups of G/N_{i−1} from those of G/N_{i}. The lifting process requires a finite presentation for each subgroup in the previous layer that is being lifted. These need to be stored along with the subgroups themselves for the trivial-Fitting groups, and we need to be able to compute presentations of the lifted subgroups of G/N_{i−1} from those of G/N_{i}. It is not necessary to do this in the final step, when we lift to G/N_{0} = G itself, but doing this is available as an option in the implementation.

The stored presentations of the subgroups of the trivial-Fitting groups were computed by using a basic method of finding presentations for any finite group of moderate order, which was described in [3]. This requires the use of the regular permutation representation of the group, and so it starts to become slow as the order increases into the 100 000 region, but of course it only needs to be done once.

We generally only aim to compute representatives of conjugacy classes of subgroups, rather than all subgroups, mainly because there would usually be too many subgroups. The other subgroups within a class are easily found by conjugating the representative subgroup S by coset representatives of the normalizer of S in G. In the earlier implementations, using the cyclic extension method, it was customary to store each of these normalizers and their transversals in G, but in fact they can be computed so quickly compared with the algorithm itself, that it is really not worthwhile. The implementation in Magma does have various option to store the normalizers (or centralizers), and information about maximal subgroups and minimal overgroups of each stored subgroup S of G.

In our description of the algorithms, we shall normally be thinking of G as a finite permutation group. However, very similar methods can be used for finite soluble groups, when the groups are represented by means of powerconjugate presentations. For such groups, it is easy, and natural to pass over to power-conjugate representations of the factor groups G/N_{i}.

For permutation groups, however, it is not always easy to compute in factor groups since, if G is a permutation group of degree d and N ⊲ G, then it is not in general possible to find a permutation representation of G/N of degree comparable to d. We shall therefore carry out our computations within G rather than in the factor groups G/N_{i} wherever possible. (In fact, there is only one place during the lifting process where we are forced to compute an explicit representation of a quotient group, which means using the regular permutation representation.)

We do, however, require a permutation representation of the trivial-Fitting factor group G/L of G in order to find an explicit isomorphism between G/L and the corresponding group stored in the database. For this purpose we can use some results of the third author proved in [7] that G/N has a faithful permutation representation of degree at most d for various particular normal subgroups N of G, including the largest normal soluble subgroup of G. The proof of this result makes it clear how to calculate the epimorphism from G to the permutation representation of G/L, and this calculation has been implemented in Magma. (The existence of this representation can also be deduced immediately from results proved previously by Easdown and Praeger in [6].)

The remainder of the paper is organized as follows. In Section 2, we describe how we find the normal series of subgroups {N_{i}}, and how we find an explicit identification and isomorphism between our group G/L and the isomorphic trivial-Fitting group stored in the database. In Sections 3 and 4 we describe the process of lifting subgroups from one layer G/N_{i} to the next layer G/N_{i−1}. This involves some cohomological calculations, which form the main theme of Section 4. In Section 5, we mention briefly some related calculations that can be carried out once the complete subgroup lattice has been computed, and some possibilities for finding only a particular subset of the complete lattice, such as the normal subgroup lattice. Finally, in Section 6, we discuss some examples and provide some performance statistics of the Magma implementation. These help to provide some idea of the current range of the method.

2 Finding the normal series and identifying the trivial-Fitting factor

In this section, we describe how we find the series of normal subgroups

1 = N_{0} ≤ N_{1} ≤ … ≤ N_{r} = L ≤ G

of G, such that each N_{i+1}/N_{i} is elementary abelian, and G/L is a trivial-Fitting group. We also need to show how to set up the identification between G/L and the isomorphic stored group in the database of trivial-Fitting groups.

Although L is uniquely determined by G, the subgroups N_{i} are, in general, not. The most significant choice we need to make is whether to aim for large or small factor groups N_{i+1}/N_{i}. In practice, this means that when we find such a factor, we need to decide whether to attempt to refine it or not. The chief problem with large factors is that we shall need to work out the conjugation action of G on the complete subgroup lattice of N_{i+1}/N_{i}, which becomes impractical if it is too large. (In fact, the ability to find reasonable sized elementary abelian factors in G appears to be the most important prerequisite for the algorithm to be applicable to G.) For more moderately sized factors, it is usually preferable not to attempt to refine them, since this reduces the number of layers through which we need to lift the subgroups.

Our algorithm for finding the series is quite simple. We start by finding a set {P_{p}} of Sylow p-subgroups of G for all primes p dividing |G|. Suppose, inductively, that at some stage we have found N_{i} for 1 ≤ i ≤ k, for some k ≥ 0, and we are trying to choose N_{k+1}. We then consider each P_{p} for which P_{p} ⊈ N_{k}, and compute the core C_{p} of N_{k}P_{p} in G. Then G/N_{k} has a nontrivial elementary abelian normal p-subgroup if and only if N_{k} is strictly contained in C_{p}.

If we find that N_{k} = C_{p} for all primes p dividing |G|, then G/N_{k} is a trivial-Fitting group, and so N_{k} = L and the series is complete. Otherwise, we find some prime p with N_{k} ⊂ C_{p}. We then refine the factor C_{p}/N_{k} to one with elementary abelian layers.

It is not necessary to compute explicitly in the quotient group to do this. For example, we can first calculate the derived series of C_{p}, and consider its terms modulo N_{k}. This reduces the problem to the abelian case, and we can refine an abelian layer to elementary abelian layers by taking groups generated by p-th powers.

If any of the factors N_{i+1}/N_{i} computed by this method are too large (which, for p = 2, 3, 5 or 7, means larger than about 2^{5}, 3^{4}, 5^{4} or 7^{3}, respectively) then we can attempt to refine it, by regarding it as a G/N_{i}-module with module action induced by conjugation in G, and looking for submodules. Of course, if this module is irreducible, then there is nothing we can do.

Finally, we have the problem of identifying G/L with the isomorphic group in the database. First we need to recognize the isomorphism class of G/L. In most small cases, this is uniquely determined by the order, and there is no problem. However, for larger orders, there are sometimes many distinct trivial-Fitting groups, and so we need a second invariant; for example, there are 10 of order 120 960.

Both for the purpose of identifying G/L and for finding an explicit isomorphism between it and the corresponding group stored in the database, it is useful at this stage to use the methods described in [7] to construct a faithful permutation representation of G/L of degree at most that of G, and to calculate the epimorphism ρ : G → G/L from G to this representation. The recently improved algorithm for finding conjugacy class representatives in permutation groups, which is described by Cannon and Souvignier in [4], is then applied to this representation of G/L. The sum of the orders in G/L of these class representatives seems to be an effective second invariant (after the order of G/L) for identifying G/L, and we are using this currently.

Assuming we have located the correct group X in the database, we now need to construct an isomorphism ϕ : X → G/L. For a conjugacy class x^{X} of X, let us call the order |x| of x and the length |x^{X}| of the class the parameters of that class. Each trivial-Fitting group X in the database is stored as a finitely presented group, and the parameters of the classes of the generators of X are also recorded. (In fact, X has just two generators in all cases except S_{5} × P Γ L(2, 9), for which three are necessary.) The first generator x_{1} of X has always been selected such that there is a unique class of X having the parameters of x_{1}^{X}. This means that ϕ(x_{1}) can be chosen as the representative of the unique class in G/L having the same parameters as x_{1}^{X}.

For the images of the remaining generators x_{i} (i > 1) of X, we choose random members of those conjugacy classes in G/L that have the same parameters as x_{i}^{X}, and for each such choice we check to see whether the defining relators of X are satisfied by the selected images ϕ(x_{i}) in G/L. If so, then we must also check that the ϕ(x_{i}) generate G/L. If this is the case, then we have found the required isomorphism ϕ : X → G/L. (The generators x_{i} (i > 1) of X have been selected in such a way as to minimize the expected searching time for an isomorphism.)

For small and moderately large examples, the database contains generators and defining relators for a representative of each conjugacy class of subgroups of X. These generators are stored as words in the x_{i} and their inverses, and we apply the map ϕ to each of these words to give us elements that generate the corresponding subgroups of G/L. The inverse images of these subgroups in G, which are needed as the initial input to the lifting part of the subgroup lattice algorithm, can then be found by using the map ρ : G → G/L mentioned above.

For larger examples, space is saved by storing only the representatives of the conjugacy classes of maximal subgroups Y of X. The main algorithm can then be applied recursively to the subgroups ϕ(Y)/L of G/L. (These will often not themselves be trivial-Fitting groups.) After doing this for each such Y, we have a collection subgroups S/L of G/L which contain conjugacy class representatives of all subgroups of G/L. Unfortunately, some of these are conjugate, since they will be produced from more than one maximal subgroup of G/M, so we have to test each such subgroup for conjugacy with the earlier subgroups in the list of the same order. This test can of course be done in G rather than G/L, but it is rather time consuming.

3 Lifting subgroups to the next layer

In this section, we assume that G is a group with normal subgroups N and M, such that N ≤ M and M/N is an elementary abelian p-group of order p^{d} for some prime p and some integer d > 0. We assume that conjugacy class representatives of the subgroups of G/M are known, together with finite presentations for each of these subgroups on suitable generating sets.

More precisely, for each such subgroup S/M of G/M, we have elements g_{i} ∈ G such that S/M = ⟨g_{i}M⟩, together with a set of words in the g_{i} and their inverses which, taken modulo M, form a set of defining relators for S/M. These words evaluate in G to elements of M. We shall describe our algorithm for computing the same information for G/N.

We denote the finite field of order p by F_{p}. Then V := M/N can be regarded as a d-dimensional vector space over F_{p}, and the conjugation action of G on M induces a G-module action (and, in fact, a G/M-module action) on V. It is routine to transfer between the representations of M/N as a subgroup of G/N, and as an F_{p}G-module V.

In fact, it is convenient to start by numbering all subgroups of M/N (or, equivalently, subspaces of V) in some standard fashion, and setting up a permutation action of G acting by conjugation on these subgroups.

Clearly, if two subgroups T_{1}/N and T_{2}/N of G/N are conjugate in G/N, then T_{1}M/M and T_{2}M/M are conjugate in G/M. It therefore suffices to take each class representative S/M of G/M in turn, and to compute class representatives of those subgroups T/N of G/N such that T M/N = S/M. From now on, we shall therefore take S/M to be a fixed subgroup of G/M.

We stress again that, although we are formulating this description in terms of quotient groups S/M, T/N, etc., almost all of our computations are done in the group G using the complete inverse images of S and T, or in the quotient V = M/N regarded as a F_{p}G-module. So we almost never need to construct these quotient groups explicitly.

Let R/M be the normalizer of S/M in G/M (or, equivalently, R = N_{G}(S)). (Currently, we simply compute R at the beginning of the calculations for the subgroup S/M. For groups of the orders currently under consideration, this is not costly. However, for large permutation groups, the computation of normalizers of subgroups is potentially very slow indeed. It would be possible to adopt the alternative policy of storing the normalizers for the trivial-Fitting groups, and computing the normalizers of the subgroups T/N at the next level as part of the lifting computation.)

The idea is to find all possible intersections L = T ∩ M for subgroups T/N with T M = S, and then to take each such L in turn, and to find all T that have that particular intersection. Of course L/N must be normalized by S/N and, since we are only looking for conjugacy class representatives of subgroups, we only want to take one such group L from each orbit of the action of R/M on the S/N-invariant subgroups of M/N.

For this, we can use the permutation action of G on the subgroups of M/N computed earlier, and then take our subgroups L/N to be orbit representatives of the orbits of R on the fixed points of S. So, from now on, we can fix our attention on a particular subgroup L/N of M/N, normalized by S/N, and we shall look for those subgroups T/N of G/N such that T M = S and T ∩ M = L. We denote the stabilizer of L in R (that is, N_{R}(L)) by Q.

The required subgroups T are precisely the complete inverse images in G of the complements T/L of M/L in S/L (if there are any). These are found using a cohomology calculation, which we shall describe in detail in the next section.

In fact, this calculation gives us conjugacy class representatives of these complements under conjugation by M/L. If the subgroups T_{1}/N and T_{2}/N of G/N resulting from two such representatives T_{1}/L and T_{2}/L are conjugate in G/N by an element gN, then g must normalize S and L, and so g ∈ Q. We therefore need to compute the conjugation action of Q on the set of these complements.

We tried two approaches to this calculation. The first, and simpler, is to test all such pairs T_{1} and T_{2} for conjugacy within the permutation group Q, by using the standard default backtrack search method. The second is to use a cohomological calculation.

The chief disadvantage of this second method is that it appears to necessitate doing calculations within the regular representation of the quotient group S/M, and so we are forced to form this representation explicitly. (Of course, this is only necessary when Q is strictly larger than S. If, as often happens, Q = S, then we omit this part of the calculation.) However, our current experience indicates that this second approach is superior in general, mainly because the direct conjugacy test occasionally takes a very long time indeed.

For the cohomological method of testing for conjugacy, we start by finding a set of elements h_{j} of Q such that the elements h_{j}S generate Q/S. This set should of course be as small as possible. For each such h_{j} and each of the generators g_{i} of S modulo M, we need to calculate a word σ_{ji}(g_{i}) in the elements g_{i} and their inverses, such that h_{j}^{−1}g_{i}h_{j}M = σ_{ji}(g_{i})M. The only way we know of calculating such a word is by working in in the regular permutation representation of S/M (which can be thought of as the Cayley graph of S/M using the generators g_{i}M).

Note that if we conjugate back again by h_{j}^{−1}, then we get equations of the form h_{j}σ_{ji}(g_{i})h_{j}^{−1} = g_{i}y_{ji} for elements y_{ji} of M, which we can calculate. We defer the remainder of the description of this calculation until the next section, since it requires the cohomological machinery used in finding the complements themselves.

As the final part of the lifting process, we need to calculate presentations of the lifted subgroups T/N of S/M. As before, let g_{i} be the generators of S modulo M. Then the generators of T will consist of g_{i}w_{i} and v_{j}, where w_{i} are elements of M that are computed in the cohomology calculation described in the next section, and v_{j} generate L modulo N. (So the v_{j} form a basis of L/N regarded as a subspace of V = M/N.)

The defining relators of T are constructed in the standard manner for group extensions by regarding T as an extension of L/N by S/M. (See, for example, Chapter 10 of [9].) They fall into three classes. The first consist of commutators and p-th powers of the v_{j}, to force them to generate an elementary abelian subgroup. The second specify the conjugation action of the g_{i} on the v_{j}; these are routine to calculate. For the third, we take each defining relator r of S/M and evaluate r in G, using g_{i}w_{i} in place of g_{i}M in r. The resulting element lies in L, and so it can be written (modulo N) as a word v(r) in the generators v_{j}. Then we take rv(r)^{−1} as the corresponding defining relator of T/N.

4 Cohomological calculations

We retain the notations introduced in the preceding section, and we assume that we are considering a fixed subgroup S/M of G/M and a fixed S-invariant subgroup L/N of M/N, and looking for subgroups T/N of G/N with T M = S and T ∩ M = L. That is, we want the conjugacy classes of complements T/L of M/L in S/L, if any. We have elements g_{1}, …, g_{m} ∈ G such that S/M = ⟨g_{i}M⟩, and words ρ_{1}, …, ρ_{n} in the elements g_{i} and their inverses which, taken modulo M, form a set of defining relators for G/M.

For the cohomological calculation, we regard W := M/L as an F_{p}S/Mmodule (and therefore use additive notation within W). We fix a basis b_{1}, …, b_{d′} of W, where d′ = dim(W), and calculate the matrices m(g_{i}) corresponding to the conjugation action of g_{i} on W, for 1 ≤ i ≤ m. We then evaluate the words ρ_{j} modulo L. Since the ρ_{j} are relators modulo M, the results of this evaluation will lie in M/L = W. We can therefore write each ρ_{j} modulo L as a vector u_{j} in W, using the fixed basis b_{1}, …, b_{d′}. (These calculations are routine.)

The matrices m(g_{i}) together with the equations ρ_{j}(g_{i}) = u_{j} now define the extension S/L of W by S/M as an abstract group extension, and the cohomological calculations take place within this context.

A complement T/L of W = M/L in S/L will be generated by elements g_{i}w_{i} (1 ≤ i ≤ m) for suitable w_{i} ∈ W. Suppose that, for 1 ≤ j ≤ n, the word ρ_{j} has length l_{j} and is equal to g_{j(1)}^{ε(1)}g_{j(2)}^{ε(2)} … g_{j(l_{j})}^{ε(l_{j})}, where each ε(j) is equal to ±1. Then it is easily seen that the elements g_{i}w_{i} generate a complement if and only if, working modulo L, the elements

y_{j} := (g_{j(1)}w_{j(1)})^{ε(1)}(g_{j(2)}w_{j(2)})^{ε(2)} … (g_{j(l_{j})}w_{j(l_{j})})^{ε(l_{j})}

of W evaluate to 0_{W} for all 1 ≤ j ≤ n.

By collecting the generators g_{i} to the left, we find that y_{j} = u_{j}x_{j}, where

x_{j} = w_{j(1)}^{f_{j(1)}}w_{j(2)}^{f_{j(2)}} … w_{j(l_{j})}^{f_{j(l_{j})}}

and, for 1 ≤ k ≤ l_{j}, the conjugating element f_{j(k)} is equal to g_{j(k+1)}^{ε(k+1)}g_{j(k+2)}^{ε(k+2)} … g_{j(l_{j})}^{ε(l_{j})}

if ε(k) = 1 and −g_{j(k)}^{ε(k)}g_{j(k+1)}^{ε(k+1)} … g_{j(l_{j})}^{ε(l_{j})} if ε(k) = −1. (Here we are using g^{h} to denote h^{−1}gh and g^{−h} to denote its inverse h^{−1}g^{−1}h.) See also page 103 of [8] for an alternative notation using Fox derivatives.

For a complement, we therefore need x_{j} = −u_{j} in W for 1 ≤ j ≤ n (note the change to additive notation in W). Since we know the elements u_{j} as vectors in W and the matrices m(g_{i}) for the conjugation action of the g_{i} on W, this reduces to an explicit system of d′n equations in d′m unknowns in W, where the unknowns are the d′ components of the vectors w_{i} (1 ≤ i ≤ m). The equations can be solved by echelonizing their matrix in the standard way.

If they have no solution, then the extension is non-split, and there are no complements and hence no corresponding subgroups T/N of G/N. Assume therefore that solutions exist, and that w_{i} = c_{i} (1 ≤ i ≤ m) is one such solution. Then, a general solution has the form c_{i} + z_{i}, where z_{i} (1 ≤ i ≤ m) is a solution of the corresponding homogeneous system of equations x_{j} = 0. These solutions z_{i} form a vector space that can be identified with the space of 1-cocycles Z^{1}(S/M, W).

We are only interested in finding the complements up to conjugacy, so we need to find the subspace of coboundaries B^{1}(S/M, W) and select complements c_{i} + z_{i}, where we take one solution z_{i} for each coset of B^{1}(S/M, W) in Z^{1}(S/M, W). Since B^{1}(S/M, W) is generated by the d′ solutions y(k)_{i} (1 ≤ k ≤ d′), where y(k)_{i} = b_{k}m(g_{i}) − b_{k}, this calculation is straightforward. The selected solutions then correspond to classes of complements T/L of W in S/L under the conjugation action of W = M/L.

As we saw in the previous section, to get the G-conjugacy classes, we need to calculate the conjugation action of Q/M on our chosen set of complements, where Q = N_{R}(L) and R = N_{G}(S). For this calculation, we will need to be able to recognize in which coset of B^{1}(S/M, W) a given element of Z^{1}(S/M, W) belongs. We therefore need to choose our coset representatives in some canonical way. The easiest way of doing this is to treat the solutions z_{i} (1 ≤ i ≤ m) in Z^{1}(S/M, W) as row vectors of length d′m, and to compute echelonized bases b(Z) and b(B) of Z^{1}(S/M, W) and of B^{1}(S/M, W). Let b(Z \ B) be those elements of b(Z) of which the leading term does not occur as a leading term of a vector in b(B). Then we can choose all linear combinations of b(Z \ B) as our canonical coset representatives of B^{1}(S/M, W) in Z^{1}(S/M, W), and an arbitrary vector in Z^{1}(S/M, W) can be reduced to its canonical representative by reducing it using the vectors in b(B).

We now turn to the calculation of the conjugation action mentioned above. Recall that, for generators h_{j} of Q modulo S, we have computed words σ_{ji}(g_{i}) such that h_{j}^{−1}g_{i}h_{j} = σ_{ji}(g_{i}) modulo M.

We now take each of of our complements T/L in turn, and compute h_{j}T h_{j}^{−1}/L for each h_{j}. If T/L is generated (modulo L) by g_{i}w_{i}, for w_{i} ∈ W, then by substituting g_{i}w_{i} for g_{i} in the words h_{j}^{−1}g_{i}h_{j}, for 1 ≤ i ≤ m, we obtain another set of generators for T/L, which have the form σ_{ji}(g_{i})w_{ji}, for certain vectors w_{ji} ∈ W, which we can calculate.

If we now conjugate this new set of generators by h_{j}^{−1}, we obtain generators for h_{j}T h_{j}^{−1} modulo L, of the form g_{i}y′_{ji}w′_{ji}, where y′_{ji}, w′_{ji} ∈ W and, modulo L, h_{j}σ_{ji}(g_{i})h_{j}^{−1} = g_{i}y′_{ji} and h_{j}w_{ji}h_{j}^{−1} = w′_{ji}. Note that the vectors y′_{ji}, which are obtained simply by taking the elements y_{ji} defined in last section modulo L, do not depend on the particular complement T/L, whereas the vectors w′_{ji} are obtained by applying the matrix for the action of h_{j}^{−1} on W to the vectors w_{ji}.

We now have generators for conjugated complement T′/L := h_{j}T h_{j}^{−1}/L in the required standard form g_{i}w′_{i}, for vectors w′_{i} ∈ W, and so we can locate the representative cocycle for T′, as described above, and thereby identify T′.

These calculations enable us to set up the permutation action, induced by conjugation, of the group Q/S on the set of conjugacy class representatives under M of complements of M/L in S/L. Orbit representatives of this permutation action provide us with the required conjugacy class representatives in G of those subgroups T/N of G/N with T M = S and T ∩ M = L. This completes the description of lifting subgroups to the next layer begun in Section 3.

5 Variations and related calculations

In many situations, the user will only be interested in finding subgroups with specific properties, and will expect to be able to find them much more quickly, and for much larger groups than is possible with the basic algorithm that looks for all subgroups. This can be done quite efficiently for many instances of subgroup properties.

It is straightforward to look only for abelian, elementary abelian, nilpotent, soluble, or perfect subgroups, or subgroups of which the order divides a fixed integer n, since these properties are all inherited by quotients, and we can impose them effectively at every stage of the lifting process. In fact insoluble subgroups are also easily found since, with our method, a subgroup S is insoluble if and only if SL/L is insoluble, where as usual L is the largest normal soluble subgroup of G. Subgroups of order exactly n are a little less efficient in that we may need to look for those of order dividing n throughout the lifting process, and then restrict to those of order exactly n during the last stage. Similar considerations apply if we want, for example, all regular subgroups (which is an important requirement for some applications), where we have to look for subgroups of order dividing the degree of the group, and then restrict to regular subgroups at the last stage.

Normal subgroups of G are easily found; in fact several parts of the process become much simpler. For example, in the cohomological part of the lifting process, we must have B^{1}(S/M, W) = 0 for normal subgroups. Maximal subgroups of G can also be found quite easily. At any stage in the lifting process, the subgroup S/M must either equal G/M or be maximal in G/M. In the latter case, when we lift to G/N, only the complete inverse image S/N needs to be kept. When S/M = G/M, we take either the lift to S/N, or to those subgroups T containing N such that T M = S and T ∩ N is a maximal G-invariant subgroup of M/N.

We now turn to the different question of what we can do with the collection of class representatives of subgroups once we have found them. We routinely store the order of each subgroup and the size of its class, and it is optional to store the normalizer and centralizer of each subgroup. (There is some sense in storing normalizers, since they are computed during the lifting process anyway.)

The most obvious question is to identify the class of a user-given subgroup S of G, and possibly to find a conjugating element to the stored class representative. For this, we first look at the order of S, and if there are several classes of subgroups of this order, then we try to eliminate as many as possible by using easily computed class-invariant properties, such as number of orbits and derived length. Finally, we have to find a transversal T_{i} for the normalizer of each remaining stored subgroup S_{i} in G, and seek an element g ∈ T_{i} with S^{g} = S_{i}.

Subgroup-lattice information is sometimes required. The basic question here is whether one stored class representative S_{i} is contained in a conjugate of another S_{j}. Again, we first attempt to use simple calculations to find a negative answer. If this fails, we calculate a transversal N_{G}(S_{i}) or N_{G}(S_{j}) in G, whichever is the smaller (and we know which is smaller, since the sizes of the classes are stored), and search among this set for a conjugating element g with S_{i}^{g} ⊂ S_{j} or S_{i} ⊂ S_{j}^{g}, respectively. With some extra work of the same nature, we can determine whether S_{i} is a maximal subgroup of a conjugate of S_{j}. The current Magma implementation has the option of calculating and storing this lattice information for all pairs of subgroups at the same time as the original calculation.

6 Examples and performance statistics

In the table below, we provide some timings for a range of examples, using the current Magma implementation. The first column specifies the group G, using the standard ATLAS notation ([5]). In one or two cases, there are two nonisomorphic groups which are not distinguished by this notation, and then we have named the groups, for example, 2^{6}A_{5}a and 2^{6}A_{5}b. When the same group name occurs more than once (for example 5^{5}SL_{2}(5)), the permutation group is the same, but the layer sizes are different. The single P that occurs in two of the group names is an abbreviation for P Γ L_{2}(9). The next two columns give the order and permutation degree of the group.

The computation is carried out by lifting through a normal series

1 = N_{0} ≤ N_{1} ≤ … ≤ N_{r} = L ≤ G

of G, where G/L is a trivial-Fitting group. The fourth column, headed “TF-Gp.”, identifies this trivial-Fitting group, and the fifth column, headed “Layer Sizes” lists the orders of the factors N_{1}, N_{2}/N_{1}, …, N_{r}/N_{r−1}, G/L in that order. In the cases, such as 5^{5}SL_{2}(5), where there are two rows for the same group, the object was to compare the performances using different layer sizes.

The final two columns, headed “#Subs.” and “Time”, give the number of conjugacy classes of subgroups in G and the cpu-time in seconds. All computations were done on a Sun SPARCstation20 at Warwick University.

As remarked at the end of the preceding section, there is an option to compute all subgroup lattice information at the same time. However, this proved to be prohibitively slow on all but the smallest examples, and so it seems preferable at the moment to calculate this information for individual classes of subgroups, as and when required. For example, the times for AGL_{2}(3) and 2^{6}A_{5}a were only 5.4 and 101 seconds, respectively, but those for 2^{4+4}A_{5} and 41^{2}SL_{2}(5) were respectively 3229 and 1266 seconds. These slow times were presumably a result of the relatively large number of subgroups (446) in the first case, and the relatively large degree (492) in the second.

Currently, the database of trivial-Fitting groups in Magma contains data on the conjugacy classes of subgroups of all such groups of order less than 216 000; that is, 154 groups. For most of these examples, representatives of all classes of subgroups are stored, but for a few of the larger direct products, only the maximal subgroups are stored. The last four examples in the table are cases in which only maximals have been stored, so the algorithm needs to be applied recursively to these maximals, and then the separate lists of subgroups obtained from the different maximals need to be tested for conjugacy with each other. The database requires about 4 Megabytes of disk space to store. Since the algorithm is feasible for many types of groups of order up to at least a million, it will certainly be worthwhile extending it in future.

We found that the process of identification of G/L and calculating an isomorphism between G/L and the group stored in the database never took more than a few seconds, and so this part of the algorithm is negligible in terms of cpu-time. Thus, except in those cases where only the maximal subgroups of the trivial-Fitting group are stored (as is the case in the last four examples), the vast majority of the cpu-time is taken up with the lifting process. This is the reason why most of the selected examples have a comparatively small trivial-Fitting factor, such as A_{5}. Several of the examples were taken from the Magma library of perfect groups, which is based on the tables in Chapter 5 of [8].

A few of the examples are soluble, in which case there is no group to look up in the database. For such examples, it is possible that it would be more efficient to transfer to a power-conjugate representation of the group, and to do the computation in that setting, but we have not yet experimented with this.

The performance statistics indicate that, provided the order of the elementary abelian sections in the layers N_{r}/N_{r−1} are not too large, the algorithm behaves very predictably. The other most important factors governing the performance appear to be the permutation degree of G, and the total number of subgroups of G, but these dependencies are not excessive, and probably not much worse than linear.

The most important decision that needs to be made in the implementation is when to try and refine an elementary abelian section. Some of the examples, such as 2^{6}L_{2}(7) and 2^{7}L_{2}(7) are given twice, once with a section refined and once without. From this, it is clear that we should always attempt to split a 2^{7} and probably also a 2^{6}, but we found that it is not generally worthwhile splitting a 2^{5}. A similar situation holds for other primes. Generally, there are one or two exponents for which the choice is not critical. The current default is to try to refine for 2^{n} (n ≥ 6), 3^{n}, 5^{n} (n ≥ 5), 7^{n} (n ≥ 4), 11^{n}, 13^{n} (n ≥ 3) and p^{n} (p > 19, n ≥ 2).

By far the major (and only really significant) limiting factor in the application of this algorithm is the layer size. If G/N_{r} acts irreducibly on N_{r}/N_{r−1} then it cannot be refined. A layer of size 2^{8} has 417 199 subgroups. This is on the border of impracticality. (In fact, we did eventually get the example 2^{8}17, with an element of order 17 acting irreducibly on the 2^{8} section to complete, but it took several days of cpu, and over 200 MBytes of memory.) The layer sizes 2^{9}, 3^{7} (2 052 656 subgroups), 5^{6} (3 583 232 subgroups), for example are currently completely impractical.

References

[1] W. Bosma and J. Cannon, Magma Handbook, Sydney, 1993.

[2] G. Butler, “Fundamental algorithms for permutation groups”, Lecture Notes in Computer Science 559, Springer, 1991.

[3] J. Cannon, “Construction of Defining Relators for Finite Groups”, Discrete Mathematics 5 (1960), 105–129.

[4] J. Cannon and B. Souvignier, “On the computation of conjugacy classes in permutation groups”, to be presented at ISSAC 1997.

[5] J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker and R.A. Wilson, ATLAS of Finite Groups, Oxford, 1985.

[6] , D. Easdown and C. E. Praeger, On minimal faithful permutation representations of finite groups, Bull. Aust. Math. Soc. 38 (1988), 207–220.

[7] D.F. Holt, “ Representing quotients of permutation groups”, to appear in Quar. J. Math. (Oxford).

[8] D.F. Holt and W. Plesken, Perfect groups, Oxford University Press, 1989.

Group  Order Deg. TF-Gp. Layer Sizes #Subs Time
AGL_{2}(3)  432  9  1  9 2 4 3 2 1  46  2.6
AGL_{2}(3)^{2}  186624 18  1  81 4 16 9 4 1 6748  951
2^{4}A_{5}  960  16  A_{5}  16 60  77  2.0
2^{6}A_{5}a  3840  48  A_{5}  2 32 60  99  40
2^{6}A_{5}b  3840  56  A_{5}  2 32 60  162  105
2^{8}A_{5}  15360 32  A_{5}  16 16 60  12769 11412
2^{4+4}A_{5}  15360 40  A_{5}  16 16 60  446  130
3^{5}SL_{2}(5)a  29160 42  A_{5}  2 243 60  573  357
3^{5}SL_{2}(5)b  29160 243 A_{5}  3 81 2 60  187  180
3^{6}A_{5}  43740 18  A_{5}  729 60  2412  2438
5^{4}A_{5}  37500 25  A_{5}  625 60  167  26
5^{5}SL_{2}(5)  375000 55  A_{5}  3125 2 60  828  1214
5^{5}SL_{2}(5)  375000 55  A_{5}  25 125 2 60  828  995
19^{2}SL_{2}(5)  43320 361 A_{5}  361 2 60  28  37
19^{3}SL_{2}(5)  823080 138 A_{5}  2 6859 60  118  804
41^{2}SL_{2}(5)  201720 492 A_{5}  1681 2 60  31  57
3^{4}2^{1+4}A_{5}  155520 81  A_{5}  81 2 16 60  289  731
3^{5}2^{4}A_{5}  233280 15  A_{5}  243 16 60  913  292
A_{5}×SL_{2}(5)  7200  29  A_{5}×A_{5} 2 3600  156  45
2^{6}L_{2}(7)  10752 16  L_{2}(7)  64 168  1730  133
2^{6}L_{2}(7)  10752 16  L_{2}(7)  8 8 168  1730  98
2^{7}L_{2}(7)  21504 32  L_{2}(7)  128 168  2458  9430
2^{7}L_{2}(7)  21504 32  L_{2}(7)  16 8 168  2458  358
3^{6}L_{2}(7)  122472 63  L_{2}(7)  729 168  1484  2649
3^{1+6}L_{2}(7)  367416 2187 L_{2}(7)  3 729 168  2086  36439
7^{4}SL_{2}(7)  806736 98  L_{2}(7)  2401 2 168  1218  803
7^{4}SL_{2}(7)  806736 98  L_{2}(7)  49 49 2 168  1218  516
3^{5}A_{6}  87480 48  A_{6}  243 60  854  346
3^{5}A_{6}  87480 48  A_{6}  81 3 60  854  186
3^{1+5}A_{6}  262440 324 A_{6}  3 243 60  541  2453
AGL_{2}(3) × P 622080 19  P Γ L_{2}(9) 9 2 4 3 2 1440 11432 10110
AGL_{2}(11)  1597200 121 GL_{2}(11) 121 2 5 1320 316  407
3^{6}A_{7}  1837080 729 A_{7}  729 2520  1955  5547
2^{5}A_{8}  645120 256 A_{8}  32 20160  3057  1098
2^{6}A_{8}  1290240 64  A_{8}  64 20160  15124 6618
12L_{3}(4)  967680 511 L_{3}(4)  4 3 20160  2873  16527
4Sz(8)  116480 2240 Sz(8)  4 29120  113  605
2M_{12}  190080 24  M_{12}  2 95040  293  40
3U_{3}(5)  378000 378 U_{3}(5)  3 126000  146  110
S_{5} × P GL_{2}(7) 40320 13  G  20160  1001  1299
S_{5} × P GL_{2}(9) 86400 13  G  86400  1094  1695
S_{5} × S_{6}  86400 13  G  86400  3182  15874
S_{5} × P  172800 13  G  172800  4147  65711 15

[9] D.L. Johnson, Presentation of Groups, London Math. Soc. Student Texts 15, Cambridge University Press, 1990.

[10] J. Neubüser, “Untersuchungen des Untergruppenverbandes endlicher Gruppen auf einer programmgesteuerten elektronischen Dualmaschine”, Numerische Mathematik 2 (1960), 280–292.

[11] G. Sandlöbes, “Perfect groups of order less than 10^{4}”, Comm. Alg. 9 (1981), 477–490.

Addresses:

School of Mathematics University of Sydney NSW 2006 Australia e-mail: bruce@maths.su.oz.au, john@maths.su.oz.au

Mathematics Institute University of Warwick Coventry CV4 7AL Great Britain e-mail: dfh@@maths.warwick.ac.uk