Computing automorphism groups of finite groups

Derek F. Holt

Abstract. A new method for computing the automorphism group Aut(G) of a reasonably small finite group G will be described in outline. The method is compared with earlier ones, and with current more specialized algorithms that handle the cases when G is a finite p-group, or a finite soluble group.

1991 Mathematics Subject Classification: primary 20D45; secondary 20B25, 20-04, 20B40.

1. Introduction

In this article, we describe in outline a new method for efficiently computing the automorphism group of a finite group G. Full technical details of the algorithm will be described elsewhere [6]. It has been implemented for finite permutation groups within the language of the MAGMA computational algebra system [1], and its performance is encouraging. It is currently practical for most groups of order up to about 50000, but the range of applicability is expected to increase substantially in the near future. It should also be possible to use similar ideas to test pairs of finite groups for isomorphism.

The method used is a generalization of that described for soluble groups by Michael Smith in [12]. The idea is to find a series of characteristic subgroups

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

2 Derek F. Holt

of our given group G, such that each N_{i}/N_{i+1} is elementary abelian and G/L has no non-trivial 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. We compute Aut(G/N_{1}), Aut(G/N_{2}), …, Aut(G/N_{r}) = Aut(G) successively, where Aut(G/N_{i+1}) is computed by testing which elements of Aut(G/N_{i}) can be lifted to automorphisms of G/N_{i+1}. If G/N_{1} is non-trivial, then its automorphism group is looked up in a database of automorphism groups of trivial-Fitting groups. The basic strategy of this approach is very similar to that described in [2] for computing the subgroup lattice of a finite group.

In Section 2 we discuss some earlier general methods that have been used to compute automorphism groups, together with the more specialized methods of O’Brien and Smith that are applicable to finite p-groups and to finite soluble groups, respectively. In Section 3, we give a brief outline of our algorithm, identify bottlenecks, and suggest possible directions for future development. In Section 4, we provide some performance statistics of the current MAGMA implementation.

2. Various methods for computing automorphisms groups

The earliest implementation of a general purpose automorphism group algorithm was probably that described by Felsch and Neubüser in [7]. They started by computing the full subgroup lattice of the group G.

A related approach that required less preprocessing was developed by Cannon and Neubüser in the early 1970’s; it required the initial computation of the conjugacy classes of G but not the full subgroup lattice. An automorphism must map an element to one of the same order and in a conjugacy class of the same size. By finding a suitable generating set for G, and using a variety of other tricks, it is usually possible in groups of moderate order to restrict the number of possible mappings of the generators in potential automorphisms to a reasonably small number. To check whether such a map really is an automorphism of G it is necessary to verify that it preserves a system of defining relators for G on the generators.

This method is described in detail in [9]. It has proved remarkably enduring and is still used in the GAP system [10]. It can be applied equally easily to power-conjugate presentations of soluble groups or to permutation representations of general groups, and is very reliable for most groups of order up to about 10000 and indeed for many larger groups. However there are few types of quite small examples, such as p-groups of class 2, that it is unable to handle easily, and more generally its effectiveness diminishes rapidly with increasing order.

The special case of finite p-groups, which includes the most difficult examples in which the group G has small order, was handled separately in an algorithm due to O’Brien that is described in [8]. As mentioned earlier, a method for finite soluble groups given by a power-conjugate presentation is described by Smith in [12]. O’Brien’s implementation is available from both MAGMA and GAP, and Smith’s is available as the GAP share package autag.

Computing automorphism groups of finite groups 3

In common with the author’s method for general groups, these both work by lifting automorphism groups through the quotients of a series of characteristic subgroups. In all three cases, the most time-consuming part of the algorithm is to solve the following lifting problem. Suppose that M and N are characteristic subgroups of G, with N < M and M/N elementary abelian. If A_{M} = Aut(G/M) is already known, then find the subgroup of A_{M} containing those elements that lift to automorphisms of G/N. The problem arises when A_{M} is large; for example, if G/M is elementary abelian, then A_{M} = GL(r, p) for some r and p; but the subgroup that lifts might be relatively small, and so testing all elements of A_{M} for lifting in a naïve fashion is not practical.

This lifting problem appears to be considerably more tractable in the pgroup case than in the soluble or general cases. For a p-group G, the most suitable series is the lower p-central series. There is a group Ĝ, known as the p-covering group of G/M, which has central elementary abelian subgroups M̂ and N̂ such that Ĝ/M̂ ≅ G/M and Ĝ/N̂ ≅ G/N, and has the useful property that all elements of A_{M} lift to automorphisms of Ĝ. We can regard M̂ as a vector space over the field of order p, and then A_{M} induces a group T of linear transformations of this space. The subgroup of A_{M} that lifts to automorphisms of G/N can then be computed indirectly as the subgroup of T that fixes the subspace N̂. This is still a difficult calculation, but it has been the subject of some research, and it can currently be solved considerably more efficiently than the automorphism lifting problem. There is a specific power-commutator presentation of G known as the standard presentation with the property that isomorphic groups have the same standard presentation. This is computed simultaneously with Aut(G), and it can be used to solve the isomorphism problem between G and other groups of the same order.

An issue involved in calculation of Aut(G) for finite groups G that has (in the author’s opinion) not always been adequately addressed is how the resulting automorphism groups should best be represented. This obviously depends on what use the user would like to make of the information once it has been computed. It would be helpful to have more feedback from users on this question; one such instance arose from the investigation of automorphisms of Burnside groups by Sims (see below).

If the group G is quite small, then representing Aut(G) as a permutation group on the elements of G is the obvious solution, and is likely to be satisfactory for all applications. Cannon and Neubüser tried to find a smaller degree faithful permutation representation on the union of some of the conjugacy classes of G. For larger groups G, this is not always possible. It is particularly problematic in the p-group and soluble group cases, where one would hope to be able to handle much larger groups. In the published descriptions by O’Brien and Smith, only generators of Aut(G) are returned, and no attempt is made to compute the group structure, although certain sections of Aut(G) are explicitly defined as elementary abelian groups or as matrix groups. However, the most recent implementations of O’Brien’s algorithm do include some facilities for computing with automorphism groups as groups, and these are expected to be be developed further in the near future.

As far as the basic lifting problem is concerned, the automorphism group representation problem does not play a rôle in the p-group case, because it reduces to a subspace stabilizer problem. However, in the soluble and general group cases there is no such reduction, and it is often essential to have an efficient concrete representation of A_{M} = Aut(G/M).

We cannot offer a completely satisfactory solution to these problems. The author has chosen, in his implementation, to return Aut(G) as a finitely presented group in which the subgroup Inn(G) of inner automorphisms is generated by an initial subset of the generators. This is at least versatile enough to allow nice permutation representations to be computed when possible, and the permutation action on the elements of G can also be computed if required.

In [11], Sims considered the problem of computing the order of subgroups of Aut(G) defined by generating automorphisms supplied by the user, and of membership testing in such subgroups, and he described a GAP implementation of a proposed solution to these problems. He was particularly interested in the case when G is a large finite p-group (for example, quotients of the Burnside group B(2, 5)), where the automorphisms groups are large. Sims’ method also uses a series of characteristic subgroups of G, and the automorphism groups of the associated factor groups. Although we have not done so yet, it would be straightforward to incorporate this idea into our implementation.

3. A brief description of the method and its implementation

Since we wish to deal with general finite groups, and the implementations of O’Brien and Smith are available for p-groups and soluble groups defined by power-conjugate presentations, we decided to implement our algorithm for finite permutation groups. Finding an appropriate series

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

of characteristic subgroups presents no particular problems; it usually proves best to refine this series as much as possible so as to make the factors as small as possible. Computing in quotients of permutation groups is not straightforward in general. However, it is proved in [4], and again in algorithmic terms by the author in [5], that the soluble radical quotient G/L has a faithful permutation representation of degree at most that of G, and the layer quotients N_{i}/N_{i+1} can be explicitly computed as G/N_{i}-modules. All other computations in the quotients G/N_{i} are actually done by working in their inverse images in G, and so there are no computational bottlenecks involving quotients of permutation groups.

When the soluble radical quotient G/L is non-trivial, the automorphism group A_{L} of the trivial-Fitting group G/L is looked up in a database. All trivial-Fitting groups T of order less that 60^{6} occur as subgroups of automorphism groups Aut(S) of groups S that are either simple or direct products of simple groups, where S ≤ T ≤ Aut(S). Currently this database stores the necessary data on all such subgroups T for all possible S with |S| ≤ 40000. The amount of data involved is not very great, and computing it, which we have done largely by trial and error using the known results from [3], is tedious but not very difficult. We intend eventually to extend this database to cover at least all S up to order one million. In order to extract this data, the abstract isomorphism types of S and T for the given group G/L must first be recognized (which is often possible just from the order of G/L), and then an explicit isomorphism has to be constructed from G/L to the corresponding group in the database, which is stored as a finitely presented group. The stored data on Aut(L) includes its order, and a presentation of the required form having the inner automorphism group (which is isomorphic to G/L) as the subgroup generated by the first two generators. There appear to be no particular computational bottlenecks in this part of the computation.

The remainder of the algorithm involves computing A_{N} = Aut(G/N) from A_{M} = Aut(G/M), where M = G_{i} and N = G_{i+1} for some i. Now A_{N} has subgroups C and B with C ≤ B, where B consists of those automorphisms that induce the identity map on G/M, and C consists of those inducing the identity on both G/M and M/N. Let K be the field of order p, where p is the prime dividing |M/N|.

The subgroup C is an elementary abelian p-group isomorphic to the group of derivations from G/M to M/N, and its computation reduces to solving a reasonably small system of linear equations over K. The quotient B/C is isomorphic to a subgroup of the group of module automorphisms of the vector space M/N regarded as a KG/M-module. Finally G/B is isomorphic to the subgroup of A_{M} of those elements that lift to automorphisms of G/N.

The computations are relatively straightforward when G/N splits as an extension of M/N by G/M. In that case B/C is the full group of module automorphisms, which can be computed quickly by using Meataxe methods. Furthermore, the lifting subgroup of A_{M} consists of those automorphisms which fix M/N a KG/M-module, and again this can be computed quickly.

The non-split case is more difficult, but we can begin by making an extra reduction. We can refine the series of characteristic subgroups of G so as to make M/N a semisimple KG/M-module contained in the Frattini subgroup of G/N. It has been proved by L.G. Kovács under these assumptions that, for an automorphism α ∈ G/N, the restriction α_{M/N} of α to M/N is uniquely determined by the induced action α_{G/M} of α on G/M. In particular, we get B = C in this case. Unfortunately, we do not currently know of any algorithmic method of computing α_{M/N} from α_{G/M}, and so for each α_{G/M} ∈ A_{M} which we are trying to lift to A_{N}, we are reduced to trying all possible module automorphisms as candidates for α_{M/N}. For a given pair (α_{G/M}, α_{M/N}), testing whether there is a corresponding lifting reduces to straightforward linear algebra. Of course, if we do find a pair that lifts, then we need try no further α_{M/N} for that particular α_{G/M}, but the vast bulk of the computation time for difficult examples consists in running through large numbers of α_{G/M} for which there is no lifting.

Judging from our current experimental implementation, it seems that all components of this algorithm can be carried out quickly and efficiently apart from the search through the potentially large group A_{M} for automorphisms that lift. This could be speeded up considerably in some examples if we knew how to compute α_{M/N} from α_{G/M}, and devising a practical method to do this must be an immediate priority. However, the search can still be a large one, even for quite small groups. For example, if G is extraspecial of order 128 defined as a central product of three quaternion groups of order 8, N = 1 and M is the central subgroup of order 2, then A_{M} is the group GL(6, 2) of order 20158709760, whereas the lifting subgroup of A_{M} has order only 51840. This computation took nearly six hours of cpu-time with our implementation; to carry out this search, we represented A_{M} as a permutation group of degree 63 on the non-identity elements of G/M, and used standard backtrack searching methods for permutation groups.

O’Brien’s p-group automorphism took only about 2 seconds to compute the automorphism group of this extraspecial group also in MAGMA on the same machine, which indicates emphatically just how much improvement can be gained by using special properties of p-groups and treating it as a subspace stabilizer problem.

This raises the question whether O’Brien’s methods, or even his code, could profitably be inserted somewhere in a general group automorphism program to handle sections of the group that happen to be p-groups. For example, it should be relatively straightforward to deal with p-quotients of the group for all primes p in this manner. Some situations would be more challenging however; for example, what could we do with the group G defined as a central product of SL(2, 5) and the extraspecial group considered above?

4. Some current performance figures

We conclude with a few timings of the current MAGMA implementation.

The table contains some sample performance figures on a Sun UltraSPARC10. The columns headed |A| and |O| list the orders of the automorphism group

G  |G|  |A|  |O| Deg. TF-Gp. Layer Sizes Time
11_{a}^{1+2}  1331 1597200 13200 121 1  121 11  11
11_{b}^{1+2}  1331 13310  110 121 1  121 11  87
D_{8}×D_{8}  64  2048  128 8  1  16 4  44
2^{1+6}  128  3317760 51840 128 1  64 2  6h
2^{4}SL_{2}(5)  1920 23040  24  40 A_{5}  60 2 16  3
2^{8}A_{5}  15360 88473600 5760 32 A_{5}  60 256  11
C_{3} ≀ S_{5}  29160 38880  4  15 S_{5}  120 81 3  9
AGL_{2}(7)  98784 98784  1  49 P GL_{2}(7) 336 3 2 49  45
AGL_{2}(7)′  16464 98784  6  49 P GL_{2}(7) 336 49  6
SL_{2}(13)×Q_{8} 17472 209664 48  64 L_{2}(13)  1092 4 2 2  49
SL_{2}(13)∨Q_{8} 8736 52416  12  224 L_{2}(13)  1092 4 2  8
3L_{3}(4)  60480 241920 12  63 L_{3}(4)  20160 3  39
3A_{6}×SL_{2}(5) 129600 172800 8  42 A_{6}×L_{2}(5) 2160 3 2  195
T (15, 30)  750  24000  32  15 1  3 2 125  1
T (15, 62)  9720 58320  6  15 A_{5}  60 81  2
T (15, 64)  9720 19440  2  15 1  2 2 5 2 243 4
T (16, 200) 128  12288  192 16 1  16 2 2 2  10
T (16, 1298) 1536 6144  8  16 1  2 3 8 4 4 2  19
T (16, 1753) 11520 23040  2  16 S_{6}  720 16  3
T (16, 1755) 12288 49152  8  16 1  3 4 4 16 4 2 2 163
T (16, 1800) 21504 21504  2  16 1  3 7 64 8 2  40
T (16, 1840) 40320 40320  1  16 A_{7}  5040 16  5

and outer automorphism group of the group G, respectively. The layer sizes are from the top downwards. All times are in seconds, with one exception, which is in hours.

In general, the notation for groups follows that in [3]. Thus 11_{a}^{1+2} and 11_{b}^{1+2} denote the two types of extraspecial groups of order 11^{3}, where the former is the one with exponent 11. The group SL_{2}(13) ∨ Q_{8} is a central product of the two factors. The group T (m, n) is the n-th transitive group of degree m, and is returned by the MAGMA function TransitiveGroup(m,n).

The special purpose method for soluble groups described in [12] is faster on some of the soluble examples, but not hugely so, whereas on others, such as D_{8} × D_{8} it seems to be significantly slower for some reason. In any case, we expect these performances to improve substantially and for the method to become applicable to much larger groups in the near future.

References

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

[2] J.J. Cannon, B. Cox and D.F. Holt, Computing the subgroup lattice of a permutation group, to appear in J. Symbolic Computation.

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

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

[5] D.F. Holt, Representing quotients of permutation groups, Quar. J. Math. (Oxford) 48 (1997), 347–350.

[6] D.F. Holt, Computing the automorphism group of a permutation group, preprint.

[7] V. Felsch & J. Neubüser, Über ein Programm zur Berechnung der Automorphismengruppe einer endlichen Gruppe, Numer. Math. 11 (1968), 277–292.

[8] E.A. O’Brien, Computing automorphisms of p-groups, in “Computational Algebra Number and Number Theory”, Wieb Bosma and A.J, van Poorten (Eds.), Proceedings of CANT ’92, Kluwer, 1995, 83–90.

[9] H. Robertz, Eine Methode zur Berechnung der Automorphismengruppe einer endlichen Gruppe, Diplomarbeit, RWTH Aachen, 1976.

[10] M. Schönert et al., GAP- Group, Algorithms and Programming, Lehrstuhl D für Mathematik, RWTH, Aachen, 1993.

[11] C.C. Sims, Computing with subgroups of automorphism groups of finite groups, “ISSAC 97”.

[12] Michael J. Smith, Computing automorphisms of finite soluble groups, Australian National University Doctoral Thesis, 1995.

Mathematics Institute, University of Warwick, Coventry, CV47AL, UK. dfh@maths.warwick.ac.uk