Representing quotients of permutation groups

Derek F. Holt

1 Introduction and statement of results

In this note, we consider the following problem. Let G be a finite permutation group of degree d, and let N be a normal subgroup of G. Under what circumstances does G/N have a faithful permutation representation of degree at most d?

Positive answers to this question are likely to have applications to computational group theory, since there are currently no really satisfactory practical methods known for computing in quotients of permutation groups. Although Kantor and Luks demonstrate in [1] that essentially all of the algorithms that are known to have polynomial complexity for permutation groups G also have polynomial complexity for quotient groups G/N of G, they do not attempt to answer the above question, and it is not clear to what extent, if any, their proposed algorithms are practical. In view of this, it is somewhat surprising that the only answer to the question in the literature appears to be the negative result of P.M. Neumann in [2]. He observes that if we take G to be a direct product of n copies of the dihedral group D_{8} of order 8, with its natural permutation action of degree 4n having n orbits of size 4, and then take N to be a central subgroup of G of order 2^{n−1} such that G/N is extraspecial, then the smallest faithful permutation representation of G/N has degree 2^{n+1}, which can clearly be very much larger than 4n. More generally, we are likely to get negative answers of this type whenever G/N is some sort of central product, but one feature of these examples is that N is not a maximal normal subgroup of its class; specifically, it is not a maximal elementary abelian normal subgroup in Neumann’s example.

We shall prove two closely related positive results.

Theorem 1 Let G be a finite permutation group of degree d. Let A be a class of finite abelian groups closed under subgroup, quotient and direct product, and let N be a normal A-subgroup of G. Then there exists a normal A-subgroup M of G with N ≤ M such that G/M has a faithful permutation representation of degree at most d. In particular, if N is a maximal normal A-subgroup of G, then G/N has such a representation.

Theorem 2 Let G be a finite permutation group of degree d. Let X be a class of finite groups closed under subgroup, quotient and group extension, and let N = O_{X} (G) be the largest normal X -subgroup of G. Then G/N has a faithful permutation representation of degree at most d.

So, for example, if π is any set of primes, then Theorem 2 tells us that G/O_{π}(G) has a faithful permutation representation of degree d. Note, however, that the class of nilpotent groups is not closed under group extension, and so we cannot conclude that G/Fit(G) has such a representation. It would be interesting to know whether the result is true or not in this case. It would also be interesting to know whether it is true for G/Φ(G), where Φ(G) is the Frattini subgroup of G. Since Fit(G/Φ(G)) = Fit(G)/Φ(G) is an abelian group, the truth of this would imply the result for Fit(G) by Theorem 1.

We shall prove these theorems in the next section, and explain how to find the representations of the quotients explicitly, which is important for the applications to computational group theory. Although we do not want to go into details about specific applications here, it is worth pointing out in what setting they are likely to arise

There are many algorithms for computing with finite soluble groups G, which make use of a series 1 = G_{0} < G_{1} < … G_{n} = G of normal subgroups of G with elementary abelian factors G_{i}/G_{i−1}. They work by solving the appropriate problem (for example, finding representatives of the conjugacy classes of G, or calculating the centraliser of an element of G) successively in the quotients G/G_{n−1}, G/G_{n−2}, …, G/G_{0} = G, where, at each stage, the solution in G/G_{i} is lifted through the elementary abelian layer G_{i}/G_{i−1} to find the solution in G/G_{i−1}. Soluble groups are best represented in a computer by using a special type of presentation known as an AG-presentation or PCpresentation. With this representation, computing in quotients is natural and straightforward.

On the other hand, any finite group has a series of normal subgroups 1 = G_{0} < G_{1} < … G_{n} ≤ G, where again G_{i}/G_{i−1} is elementary abelian for 1 ≤ i ≤ n, and G/G_{n} has no soluble normal subgroups. In fact, G_{n} is the soluble radical (that is, the largest normal soluble subgroup) of G. In many important examples, such as extensions of modules by finite simple groups, G/G_{n} is a relatively small group compared with G, and we can solve the problem concerned directly (perhaps by brute force searching methods) in G/G_{n}, but not so easily in G. If G is given as a permutation group of reasonable degree, then the only serious barrier to using the same lifting techniques as in soluble groups is the problem of finding explicit representations of the quotients G/G_{i}; in fact, group theory packages use the regular permutation representation for quotients by default, which often renders the whole approach impractical. By choosing the class A in Theorem 1 to be the class of elementary abelian p-groups for an appropriate prime p, and applying Theorem 1 repeatedly, we can always choose such a series of normal subgroups with the property that each of the quotients G/G_{i} has a faithful permutation representation of degree d. In fact, since the conjugation action of the quotients G/G_{i} on the layers G_{i}/G_{i+1} can be represented concisely as a group of matrices over a finite prime field, in many applications it is only necessary to have a convenient representation of the top factor group G/G_{n}. Theorem 2 can be used for this purpose, by taking X to be the class of all finite soluble groups.

2 Proofs of the theorems

Proof of Theorem 1. We may clearly assume that N ≠ 1. Let X be the set that G is permuting, and let S be the symmetric group on X. Let Σ be the set of orbits of N on X, and let Y be a subset of X containing one representative from each orbit W ∈ Σ. Let L be the subgroup of S consisting of all g ∈ S such that g fixes each W ∈ Σ and, for all W ∈ Σ, there exists h ∈ N with g^{W} = h^{W}. Then L is isomorphic to the direct product of the induced action groups N^{W} for W ∈ Σ, and so, by the assumptions on the class A, we have L ∈ A. It is easy to check that L is normalised by G. Let E be the group GL, and let M = G ∩ L. Then clearly N ≤ M, M ∈ A (since A is subgroup closed), and E/L = GL/L ≅ G/M.

Let D = E_{Y} be the setwise stabiliser of Y in E. We claim that E = DL. Let e ∈ E. To establish the claim, we shall define an element g ∈ L such that eg ∈ D. To do this, we need to define g^{W} for each W ∈ Σ. Since G permutes the set Σ, we have W^{e^{−1}} ∈ Σ and there is a unique point y ∈ Y ∩ W^{e^{−1}}. Then y^{e} ∈ W, and so there exists h ∈ N with y^{eh} equal to the unique point in Y ∩ W. We define g^{W} to be equal to h^{W}. Then, by definition of L, we have g ∈ L, and by choice of h, we have y^{eg} ∈ Y for all y ∈ Y. Thus eg ∈ D, and E = DL as required. Since L is abelian, any element in L that fixes a point of one of its orbits fixes the whole orbit pointwise. But L ∩ D must fix every point in Y (since it fixes the set Y and also fixes each orbit W ∈ Σ), and hence it fixes all points in X. Thus L ∩ D = 1 and D is a complement of L in E.

Now we have G/M ≅ E/L ≅ DL/L ≅ D, and since D is a permutation group of degree d, this completes the proof of Theorem 1.

Notice that D will not normally be a subgroup of G; indeed, the extension G of M by G/M may well be nonsplit. What we have done is to embed G into a larger group to force the extension to split.

Proof of Theorem 2. This is similar to that of Theorem 1, but we do not get the condition L ∩ D = 1, and so we have to use an inductive argument. We define X, Σ, Y and the group L exactly as in Theorem 1. Once again we have L ∈ X, L is normalised by G, and we let E = GL. Since N = O_{X} (G) and G∩L is a normal X -subgroup of G, we have G∩L = N, and so E/L ≅ G/N.

The proof of the theorem is by induction on d − |Σ|. When d − |Σ| = 0 we have N = 1 and the result is trivial, so suppose not. We define D = E_{Y} and we can show that E = DL exactly as in the proof of Theorem 1. Then G/N ≅ E/L ≅ D/(D ∩ L). Since the class X is closed under extension, we have O_{X} (G/N) = 1, and so D ∩ L = O_{X} (D). But, since N ≠ 1, some orbit of L has length greater than 1, and D ∩ L fixes a point of that orbit. Thus D ∩ L has more orbits on X than L does, and we can apply our inductive hypothesis to the group D, and the result follows.

For the applications to computational group theory, we need to know how to calculate the permutation representations guaranteed by the above theorems explicitly. This presents no difficulty in the case of Theorem 1, since each element e in E = GL decomposes uniquely as dl with d ∈ D and l ∈ L, and it is clear from the above proof how to find d.

In the case of Theorem 2, let {g_{i}|1 ≤ i ≤ r} be a generating set for G. Then, for each i with 1 ≤ i ≤ r, we calculate a particular g′_{i} ∈ D ∩ g_{i}L as in the proof of Theorem 2. The g′_{i} are not uniquely determined by g_{i}, but that does not matter. They generate a subgroup C of D with C/O_{X} (C) ≅ D/O_{X} (D) ≅ G/N. If O_{X} (C) ≠ 1, then we repeat the process with C in place of G, using the generators g′_{i} of C, and we carry on until we find a group B with generators g′′_{i} such that O_{X} (B) = 1 and B ≅ G/N. Then the required permutation representation of G/N is defined by the map that sends g_{i} to g′′_{i} for 1 ≤ i ≤ r. Note added in proof: It has been brought to my attention that a result very similar to Theorem 1 as well as several other examples are contained in [3].

References

[1] W.M. Kantor and E.M. Luks, “Computing in quotient groups”, Proc. 22^{nd} ACM STOC, 1990, 524–563.

[2] P.M. Neumann, “Some algorithms for computing with finite permutation groups”, in E.F. Robertson and C.M. Campbell (eds.), Proceedings of Groups-St Andrews 1985, London Math. Soc. Lecture Notes 121, CUP, 59–92,1987.

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

Address:

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