IntroductionSetupAbelian caseNonabelian caseExamplesComputing normal subgroupsAlexander Hulpke∗School of Mathematical and Computational SciencesUniversity of St. AndrewsThe North Haugh, St. Andrews, Fife KY16 9SS,United [email protected]://www-gap.dcs.st-and.ac.uk/~ahulpkeAbstractThis note presents a new algorithm for the computation ofthe set of normal subgroups of a finite group. It is based onlifting via homomorphic images.1 IntroductionNext to a composition series, the structure of a finite group isreflected by the lattice of its normal subgroups. It indicates,for example, possible epimorphic images or decompositionsas (sub)direct products. Furthermore it contains all charac-teristic subgroups. Contrasting this structural prominence,however, the problem never seems to have been consideredseriously in the literature and the best algorithm known tothe author is the na¨ıve approach to take normal closuresof conjugacy classes. This requires a priori knowledge ofthe conjugacy classes. The alternative approach presentedhere avoids this requirement and performs much quicker forlarger groups (even if the classes are known for free). Thiswill permit to compute the normal subgroups in reasonabletime even for fairly large groups, for which for example theconjugacy classes could not be computed. Evidence for thisis given in the last section.The algorithm described below does not explicitly re-fer to a groups representation, but requires several auxil-iary routines which in turn may make use of the represen-tation. It can be applied whenever all these routines can beapplied for a given group. For all those required routines(element test, composition series/chief series, normal inter-section, computation of presentations) efficient algorithmsare known and implemented for permutation groups [19] orgroups given by a polycyclic presentation.2 SetupAssume that G is a finite group for which we want to deter-mine the normal subgroups. We start with a chief series forG. Such a series can be computed [13, 11] by forming the∗Supported by EPSRC Grant GL/L21013intersection of conjugates in a composition series of G (thisyields a series of normal subgroups) and refining elementaryabelian subfactors using the MeatAxe [18]. For permutationgroups alternatively the composition series algorithm can bemodified to compute normal subgroups in the first place [3].Using the homomorphism principle we compute the nor-mal subgroups of G inductively along this series, in a stepfrom Nito Ni+1< Nicomputing the normal subgroupsof G/Ni+1from those of G/Ni. After the last step forNi+1= h1i this yields the normal subgroups of G.Remark 1. Computing representations for factor groups isnot only very hard in the general case; there are situa-tions where all faithful representation of a factor are much“larger” than the representation of G we started with [7, 17].To overcome this problem we always compute with represen-tatives in G instead of elements of a factor group and replacesubgroups of a factor by their full preimages in G. The el-ement order of Nig in the factor can be obtained as thesmallest k such that gk∈ Ni. The readers should convincethemselves that all calculations performed in the next twosections are possible with representatives and preimages aswell and yield representatives respectively preimages of theresults in the factor group. (Note, however, that in manycases it is still possible to compute in reasonable time afaithful permutation representation of reasonable degree fora factor group if it was required. We don’t require it in thispaper.)It is sufficient to describe a single lifting step. In thisfactor H = G/Ni+1the image M = Ni/Ni+1is a minimalnormal subgroup, that is there is no proper subgroup h1i <K < M such that K is normal in H. To simplify notationwe assume without loss of generality that Ni+1= h1i andG = H.If B is a normal subgroup of G which does not contain M ,then B ∩ M = h1i (as the intersection is a normal subgroupcontained in M ) and A = hM, Bi is a normal subgroupcontaining M. B is a normal complement to M in A.Assuming by induction that all normal subgroups A con-taining M are known a priori, it is therefore sufficient toshow how for a given A > M all possible B can be deter-mined. This will give rise to all normal subgroups of G viaa loop over all these subgroups.It is well known [6, Thm. 4.3.A(iii)] that as a minimalnormal subgroup M must be the direct product of copies ofa simple group T . Let n denote the number of direct factors:M =n×i=1Ti, Ti∼=T . Here we have to distinguish two cases,1depending on whether T is abelian or not.3 Abelian caseIf T is abelian, M is an elementary abelian group – in otherwords a vector space over a finite field. A basis m1, . . . , mnof M corresponds to a series of subgroups Ui= hmj| j ≤ iiwithh1i = U0< U1< · · · < Un−1< Un= M.Element tests in these subgroups permit to decompose anelement of M with respect to the chosen basis.If a normal complement B to M in A exists, A is the di-rect product of M with B and M therefore must be central inA. In this case all complements to M in A are parametrized(if they exist) by the group of 1-Cocycles:Z1(A/M, M) := {γ : A/M → M | (fg)γ = (fγ)g(gγ)for all f, g ∈ A/M}If C is a fixed complement, the complement correspondingto γ ∈ Z1is of the form{c · ((cM )γ) | c ∈ C}.If a presentation for A/M is known, it is possible to com-pute C as the solution of an inhomogeneous system of linearequations [5]. If no complements exist, this system has nosolutions. Z1arises from the corresponding homogeneoussystem. A presentation for A/M can either be computeddirectly from a representation for A/M or by first comput-ing a presentation for A and adding words for generatorsof M. For permutation groups a presentation can be com-puted either via a stabilizer chain [4] or from a compositionseries [1, 14]. The latter usually yields a better presentationand can also be modified to yield a presentation for A/Mwithout the need to compute a permutation representationof this group first.The complements parametrized by Z1are all normal inA but not necessarily normal in G. We therefore have todiscard those complements that are not normal in G.Problems may occur if Z1is large, that is there are manysubgroups of A that complement M. If this happens A isusually close to abelian. The worst case certainly is if A iselementary abelian:Lemma 2. If A is elementary abelian, |A| = pdand |M| =pnthere