J. Symbolic Computation (2001) 11, 1–000

Computing subgroups by exhibition in finite solvable groups

Bettina Eick^{†} and Charles R. B. Wright^{‡}

†Fachbereich für Mathematik und Informatik, Universität Kassel, 34109 Kassel, Germany ‡ Department of Mathematics, University of Oregon, Eugene, Oregon 97403, U.S.A.

(Received 20 January 2000)

We present practical algorithms to compute subgroups such as Hall systems, system normalizers, 𝔉-normalizers and 𝔉-covering subgroups in finite solvable groups. An application is an algorithm to calculate head complements in finite solvable groups; that is, complements which are closely related to maximal subgroups. Our algorithms use the technique of exhibiting subgroups.

Subgroups such as Hall systems, system normalizers, 𝔉-normalizers and 𝔉-covering subgroups arise naturally in the study of finite solvable groups. Here we present practical algorithms to compute such subgroups. Besides being of interest in the theory of formations, the algorithms also yield fast methods for constructing head complements. These complements are closely related to the maximal subgroups of the underlying group and they also arise in the determination of special polycyclic generating sequences for solvable groups. Such sequences have proved to be of central importance for fast computations with finite solvable groups, and thus a practical method to obtain them has important applications.

Our approach is to start with a special type of generating set for a given solvable group and then to modify the set until it contains an easily identified generating set for the desired subgroup. This process, which is called “exhibition,” was first introduced by C. R. Leedham-Green and is described in (Cannon and Leedham-Green, 1993) and (Eick, 1997). It is a powerful method for computing subgroups that are described by their intrinsic properties. One element of our approach will be a characterization of those sets of subgroups that can be simultaneously exhibited.

The paper is organized as follows. First we describe the fundamental idea of exhibiting subgroups of finite solvable groups in Section 1. Then in Section 2 we introduce the key algorithm of our paper: a method to exhibit certain normalizers in a finite solvable group. In Section 3 we show how to use such normalizers to compute head complements, and in Section 4 we describe their applications for the computation of formation theoretic subgroups. We report on the implementations of these methods in the computer algebra system GAP, see (Schönert et al., 1995), and to show the practicability of our methods we give runtimes in Section 5. Finally, in Section 6 we outline a complexity analysis.

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 2001 Academic Press Limited

1. Polycyclic generating sequences and exhibition

Let G be a finite solvable group with polycyclic series G = C_{1}⊳…⊳C_{n}⊳C_{n+1} = {1}. If we choose elements a_{i} such that ⟨a_{i}, C_{i+1}⟩ = C_{i}, then the sequence A = (a_{1}, …, a_{n}) is a polycyclic generating sequence of G. We assume throughout this paper that the polycyclic series is a composition series, so that each index [C_{i} : C_{i+1}] is a prime, say p_{i}.

The tails (a_{i}, …, a_{n}) of A form polycyclic generating sequences of the subgroups C_{i}, and so A determines the polycyclic series. Moreover, each element of G is uniquely expressible as a normal word in the form a_{1}^{e_{1}} ⋯ a_{n}^{e_{n}} with 0 ≤ e_{i} < p_{i} for 1 ≤ i ≤ n; for short we say that a_{1}^{e_{1}} ⋯ a_{n}^{e_{n}} is a normal word in A.

In our applications we will often choose the polycyclic series of G to refine a given normal series with elementary abelian factors. In this case we say that A is compatible with the normal series.

The polycyclic generating sequence A determines a power-commutator presentation of G, a type of presentation often used to represent finite solvable groups for computations; see for example (Sims, 1994) for further information. A practical algorithm to compute polycyclic generating sequences for solvable permutation groups is given in (Sims, 1990). Further, (Plesken, 1987) and (Niemeyer, 1994) present methods to obtain power-commutator presentations for finite solvable factors of finitely presented groups.

1.1. Exhibited subgroups

Let A = (a_{1}, …, a_{n}) be a polycyclic generating sequence of G and let U be a subgroup of G. Then A exhibits U in case the subsequence of elements a_{i} that belong to U forms a polycyclic generating sequence of U. We denote the subsequence by A ∩ U.

It is easily seen, e.g. as a consequence of Theorem 1.4 below, that for any chain of subgroups there exists a polycyclic generating sequence simultaneously exhibiting all subgroups in the chain.

If A exhibits U, then U = ⟨A ∩ U⟩, but the converse is not true. For example, consider the dihedral group G = ⟨(1234), (12)(34)⟩, with subgroup U = ⟨(1234)⟩ and polycyclic generating sequence A = ((1234), (12)(34), (14)(23)). Then A ∩ U = ((1234)), and thus U = ⟨A ∩ U⟩, but A does not exhibit U.

It will be useful to characterize exhibition in two ways.

Lemma 1.1. Let U be a subgroup of G, and let A = (a_{1}, …, a_{n}) be a polycyclic generating sequence of G that determines the composition series G = C_{1} ⊳ … ⊳ C_{n} ⊳ C_{n+1} = 1 with [C_{i} : C_{i+1}] = p_{i}. Then the following statements are equivalent.

(1) A exhibits U.

(2) U is the set of normal words in A ∩ U.

(3) |U| = ∏_{a_{i}∈A∩U} p_{i}.

Proof. Clearly (1) implies (2). Moreover, (2) implies (3), since the number of normal words in A ∩ U is ∏_{a_{i}∈A∩U} p_{i} and such expressions are unique. On the other hand, (3) implies (2), since U contains the set of normal words in A ∩ U in any case and the condition in (3) implies that U cannot contain more elements.

Now suppose that (2) is true and we want to show (1). Let A_{i} = (a_{i}, …, a_{n}) for i = 1, …, n + 1. First we show that ⟨A_{i} ∩ U⟩ = C_{i} ∩ U. Clearly, A_{i} ∩ U ⊆ C_{i} ∩ U and hence ⟨A_{i} ∩ U⟩ ≤ C_{i} ∩ U. On the other hand, U is the set of normal words in A ∩ U and thus C_{i} ∩ U is the set of normal words in A_{i} ∩ U. Therefore we obtain C_{i} ∩ U ≤ ⟨A_{i} ∩ U⟩.

Clearly, the subgroups C_{i} ∩U form a subnormal chain of subgroups of U whose indices [C_{i} ∩ U : C_{i+1} ∩ U] are either prime or trivial. Hence the set of subgroups ⟨A_{i} ∩ U⟩ contains the members of a composition series of U. Thus A∩U is a polycyclic generating sequence of U. □

1.2. Intersections and Products of exhibited subgroups

One of the chief advantages of the exhibition approach is the ability to immediately exhibit certain subgroups built from ones on hand.

Theorem 1.2. Let A be a polycyclic generating sequence of G that simultaneously exhibits the subgroups U and V of G.

(a) Then A exhibits U ∩ V.

(b) If UV = V U, then A exhibits ⟨U, V ⟩.

Proof. (a) By Lemma 1.1, U ∩ V is the set of elements that are normal words in both A∩U and A∩V. Since representations as normal words are unique, these are the elements that are normal words in A ∩ (U ∩ V). By Lemma 1.1 again, A exhibits U ∩ V.

(b) Using (a) and applying Lemma 1.1 to U, V, U ∩ V and finally to UV we obtain

|UV | = |U||V |/|U ∩ V |
= ∏_{a_{i}∈A∩U} p_{i} ∏_{a_{i}∈A∩V} p_{i} / ∏_{a_{i}∈A∩(U∩V)} p_{i}
= ∏_{a_{i}∈(A∩U)∪(A∩V)} p_{i} ≤ ∏_{a_{i}∈A∩UV} p_{i} ≤ |UV |.

Hence we have equality and the desired result is obtained. □

If we have exhibited a set of subgroups, then by Theorem 1.2 their intersections and permuting products can be obtained without further computational effort. For example, suppose that we want to exhibit a Hall system of G, i.e., a set of permuting Hall subgroups, one for each set of primes dividing the order of G. By Theorem 1.2 it is enough to exhibit either all Sylow subgroups in the Hall system (a Sylow basis) or all Sylow complements in the Hall system (a complement basis), since we can derive all the other Hall subgroups as products from the Sylow basis or as intersections from the complement basis.

The ability to compute intersections and certain products quickly will be important when we compute system normalizers and related subgroups in what follows. Theorem 1.2 also yields the following facts that we will use later.

Proposition 1.3. Let A be a polycyclic generating sequence for G. If A exhibits the π-Hall subgroup H of G and also the subgroup U of G, then H ∩ U is a π-Hall subgroup of U. Hence if A exhibits the Hall system Σ for G, then Σ reduces into every subgroup of G that A exhibits.

Proof. By Theorem 1.2, A exhibits H ∩ U. Thus the result follows with Lemma 1.1.

□

1.3. A characterization of the sets of subgroups that can be exhibited

It is in general not possible to exhibit simultaneously all members of a given set of subgroups. The following theorem characterizes in a natural and useful way those sets of subgroups for which there exists a polycyclic generating sequence simultaneously exhibiting all subgroups in the set.

Theorem 1.4. Let G be a finite solvable group and let X be a set of subgroups of G. Then there exists a polycyclic generating sequence of G exhibiting all subgroups in X if, and only if, there exists a composition series G = C_{1} ⊳ … ⊳ C_{n+1} = {1} such that for each i ∈ {1, …, n} the factor C_{i}/C_{i+1} is covered by the intersection V_{i} of all those members of X that cover C_{i}/C_{i+1}.

In this case we can choose a_{i} ∈ V_{i} ∩C_{i} \C_{i+1} to obtain a polycyclic generating sequence A = (a_{1}, …, a_{n}) that exhibits X and the series G = C_{1} ⊳ … ⊳ C_{n+1} = {1}.

Proof. Suppose first that A = (a_{1}, …, a_{n}) is a polycyclic generating sequence of G that exhibits all subgroups in X. Let G = C_{1} ⊳ … ⊳ C_{n+1} = 1 be the composition series determined by A, and consider i ∈ {1, …, n}. Suppose that U in X covers C_{i}/C_{i+1}. Since U is exhibited by A, we have a_{i} ∈ U. Thus a_{i} is an element of the intersection V_{i}, and hence V_{i} covers C_{i}/C_{i+1} as well.

Suppose now that there exists a composition series G = C_{1} ⊳ … ⊳ C_{n+1} = 1 of G such that for each i ∈ {1, …, n} the intersection V_{i} of the members of X covering C_{i}/C_{i+1} also covers C_{i}/C_{i+1}. (Here V_{i} = G if no member of X covers C_{i}/C_{i+1}.) For each i we choose a_{i} ∈ V_{i} ∩(C_{i} \C_{i+1}) and use inverse induction on i to show that A = (a_{1}, …, a_{n}) exhibits all subgroups in X. Let U ∈ X and suppose for induction that U ∩ C_{i+1} is exhibited by A. If U avoids C_{i}/C_{i+1}, then U ∩ C_{i} = U ∩ C_{i+1} and thus U ∩ C_{i} is exhibited as well. If U covers C_{i}/C_{i+1}, then a_{i} ∈ V_{i} ≤ U and thus a_{i} together with A ∩ (U ∩ C_{i+1}) yields a subsequence of A that is a polycyclic generating sequence of U ∩ C_{i}. Thus A exhibits U ∩ C_{i} in this case too. □

Theorem 1.4 provides a proof that every chain of subgroups can be exhibited, since the intersection of subgroups in such a chain is again a subgroup in the chain. The condition of Theorem 1.4 is also trivially fulfilled if a set X of subgroups has the property that each composition factor is covered by at most one member of X; for example, every set of Sylow subgroups for different primes can be exhibited and thus, by Theorem 1.2, every Hall system can be.

To prove that a certain set of subgroups can be exhibited it is sometimes more natural or more useful to consider a subnormal series that is not necessarily a composition series of G. It is an easy consequence of Theorem 1.4 to obtain the following similar characterization using a subnormal series instead.

Corollary 1.5. Let G be a finite solvable group and X a set of subgroups of G. Then there exists a polycyclic generating sequence of G exhibiting all members of X if, and only if, there exists a subnormal series G = S_{1} ⊳ … ⊳ S_{m} ⊳ S_{m+1} = {1} such that for each j ∈ {1, …, m} (a) each subgroup in X either covers or avoids S_{j}/S_{j+1}, and

(b) the intersection W_{j} of all those members of X that cover S_{j}/S_{j+1} also covers S_{j}/S_{j+1}.

Proof. If there exists a polycyclic generating sequence A of G exhibiting X, then we may choose the composition series determined by A as subnormal series and invoke Theorem 1.4.

Now suppose that we are given a subnormal series and an X that satisfy (a) and (b). Refine the series to a composition series G = C_{1} ⊳ … ⊳ C_{n+1} = 1, and consider the chain S_{j} ≥ C_{i} > C_{i+1} ≥ S_{j+1}. Since each subgroup in X either covers or avoids S_{j}/S_{j+1}, the subgroups in X covering C_{i}/C_{i+1} are exactly the subgroups in X covering S_{j}/S_{j+1}. By assumption, the intersection of these subgroups covers S_{j}/S_{j+1}, and thus it covers C_{i}/C_{i+1}. Hence X is exhibited, by Theorem 1.4. □

It is not always possible to exhibit a complete set of representatives of the conjugacy classes of maximal subgroups of a group; such a goal is unattainable even for elementary abelian groups. The head complements introduced by Leedham-Green and described in (Cannon and Leedham-Green, 1993) and (Eick, 1997) provide a useful substitute, however, and in Section 3 below we give an algorithm to exhibit head complements. In Section 4 we describe algorithms that exhibit system normalizers and subgroups associated with the theory of formations, together with their corresponding Hall systems.

1.4. Hall generating sequences

An important application of Theorem 1.4 for our purposes is included in the following obvious consequence of Corollary 1.5.

Corollary 1.6. Let G be a finite solvable group and let G = K_{1} ⊳ … ⊳ K_{m+1} = {1} be a normal series of G with elementary abelian factors. Furthermore let Σ be a Hall system of G. Then there exists a polycyclic generating sequence A of G compatible with the normal series and exhibiting the Hall system Σ.

We call such a polycyclic generating sequence A as described in Corollary 1.6 a Hall generating sequence. These sequences will be the starting points for all of our computations. In Appendix A we give an algorithm that starts with a normal series with elementary abelian factors and computes a polycyclic generating sequence that is compatible with the normal series and that exhibits a Hall system. Another algorithm for computing a Hall generating sequence is described in (Cannon and Leedham-Green, 1993).

2. Computing certain normalizers

In this section we introduce an algorithm to exhibit subgroups of the form N_{G}(S_{p′} ∩M), where S_{p′} is a p-complement and M a normal subgroup of G. Such subgroups will play key roles in the algorithms in later sections.

Methods are known to compute the normalizer of an arbitrary subgroup of a finite solvable group; for example, a practical algorithm is described in (Celler et al., 1990). While our method is restricted to subgroups of a specific type, in that setting it is more efficient than the other known methods for this purpose. Moreover, our algorithm yields not just a generating set for the normalizer, but even a polycyclic generating sequence of G that exhibits the normalizer.

We emphasize that our approach allows us to avoid the computation of chief factors, which is a standard approach in theoretical work with finite solvable groups. From an algorithmic point of view, our indifference to whether factors are chief yields a significant speedup in performance, since a chief series would generally take longer to obtain than our series, and furthermore would typically entail more steps down an elementary abelian series in any algorithm based on the homomorphism principle.

2.1. Exhibiting N_{G}(S_{p′} ∩ M)

Let p be a prime and M a normal subgroup of G. As setup for our algorithm we use a normal series K = (G = K_{1} ⊳ K_{2} ⊳ … ⊳ K_{m} ⊳ K_{m+1} = {1}) with elementary abelian factors such that each p-factor is either M-central or M-hypereccentric, i.e. contains no M-central G-chief factor. In Section 2.2 we describe a method to obtain such a series K.

Let A be a Hall generating sequence associated to K; that is, the composition series determined by A refines the series K, and A exhibits a Hall system Σ = {S_{π} | π a set of primes} of G. We want to modify A to a polycyclic generating sequence which additionally exhibits N_{G}(S_{p′} ∩ M), where S_{p′} is the p-complement in Σ.

Theorem V.1(1.5) of (Doerk and Hawkes, 1992), with π = {p} and ν(p) = M, says that N_{G}(S_{p′} ∩ M) either covers or avoids each chief factor of G, and covers a p-chief factor precisely if S_{p′} ∩ M centralizes it. Since S_{p′} ∩ M centralizes a chief factor if, and only if, M acts on it as a p-group, since M ⊴ G, and since N_{G}(S_{p′} ∩ M) covers all p′-chief factors, it follows that N_{G}(S_{p′} ∩M) avoids the M-hypereccentric p-chief factors of G and covers all other chief factors. Thus N_{G}(S_{p′} ∩ M) either covers or avoids each factor in K. By Corollary 1.5, G has a polycyclic generating sequence that simultaneously exhibits Σ, the subgroups in K and the subgroup N_{G}(S_{p′} ∩ M).

We wish to modify A by working down the factors of the series K, using the following fact.

Lemma 2.1. Let H be a π-Hall subgroup and M a normal subgroup of the finite solvable group G. Then N_{G}(H ∩ M)K/K = N_{G/K}(HK/K ∩ MK/K) for every normal subgroup K of G.

Proof. Since HK/K is a π-Hall subgroup in G/K, it follows that HK/K ∩ MK/K is a π-Hall subgroup in MK/K, as is (H ∩ M)K/K. Thus HK ∩ MK = (H ∩ M)K.

We may assume that K is minimal normal in G. If K is a π′-group, then H ∩M is a π-Hall subgroup in (H∩M)K, so by the Frattini argument N_{G}((H∩M)K) = N_{G}(H∩M)K. If K is a π-group, then K ≤ H, so N_{G}((H∩M)K) = N_{G}(H∩MK) ≤ N_{G}(H∩MK∩M) = N_{G}(H ∩ M) ≤ N_{G}((H ∩ M)K). □

Clearly, our setup is inherited by the factor groups G/K_{i}; in fact, the induced sequences A/K_{i} = (a_{1}K_{i}, …, a_{j_{i}}K_{i}) form Hall generating sequences of G/K_{i} associated with the normal series K_{1}/K_{i}⊳…⊳K_{i}/K_{i} and with the Hall systems {S_{π}K_{i}/K_{i}}, where the index j_{i} is chosen such that (a_{j_{i}+1}, …, a_{n}) forms a polycyclic generating sequence of K_{i}. Hence we may assume by induction that A/K_{m} exhibits N_{G/K_{m}}(S_{p′}K_{m}/K_{m} ∩ MK_{m}/K_{m}), which is equal to N_{G}(S_{p′} ∩ M)K_{m}/K_{m}, according to Lemma 2.1. Therefore it will be enough to show that if A exhibits N_{G}(S_{p′} ∩ M)K_{m}, then A can be modified to exhibit N_{G}(S_{p′} ∩ M) in addition to K and Σ.

Let K = K_{m}, and suppose that K is a q-group for the prime q. If q ≠ p or if q = p and K is M-central, then K ≤ N_{G}(S_{p′} ∩ M), and thus A exhibits N_{G}(S_{p′} ∩ M) by induction.

Thus we assume now that K is an M-hypereccentric p-subgroup of G, so N_{G}(S_{p′} ∩ M) avoids K, and thus N_{G}(S_{p′} ∩M) is a complement to K in N_{G}(S_{p′} ∩M)K. By assumption, A exhibits N_{G}(S_{p′} ∩ M)K; say the subsequence (a_{i_{1}}, …, a_{i_{r}}, a_{l+1}, …, a_{n}) is a polycyclic generating sequence of this subgroup, where (a_{l+1}, …, a_{n}) is a polycyclic generating sequence of K. Then each complement to K has a polycyclic generating sequence of the form (a_{i_{1}}k_{i_{1}}, …, a_{i_{r}}k_{i_{r}}) for certain elements k_{i_{j}} ∈ K. Our aim is to compute elements k_{i_{1}}, …, k_{i_{r}} corresponding to the complement N_{G}(S_{p′} ∩ M).

Since A exhibits Σ, each element in A is either contained in S_{p′} or in the exhibited Sylow subgroup S_{p}. If a_{i_{j}} is an element of S_{p′}, then a_{i_{j}} ∈ N_{G}(S_{p′} ∩ M), and we may choose k_{i_{j}} = 1.

Now consider the case a_{i_{j}} ∈ S_{p}. To simplify notation we will write a = a_{i_{j}}. Since a ∈ N_{G}(S_{p′} ∩ M)K, we have [m, a] ∈ (S_{p′} ∩ M)K for each m in S_{p′} ∩ M. Thus we can factor the commutator into

[m, a] = l_{m} · h_{m} with l_{m} ∈ S_{p′} ∩ M and h_{m} ∈ K

and since K ∩ S_{p′} ∩ M = {1} this factorization is unique. Hence for k in K with ak in N_{G}(S_{p′} ∩ M) we get

[m, ak] = [m, a] · [m^{a}, k]
= l_{m} · h_{m} · [m^{a}, k]
= l_{m} · x_{m} with x_{m} = h_{m} · [m^{a}, k] ∈ K.

Again, this factorization of [m, ak] into elements l_{m} in S_{p′} ∩ M and x_{m} in K is unique. Now ak ∈ N_{G}(S_{p′} ∩ M) if, and only if, [m, ak] ∈ S_{p′} ∩ M for every m in S_{p′} ∩ M, i.e., if, and only if, x_{m} = 1 and

h_{m} = [m^{a}, k]^{−1} = [k, m^{a}]

for each m in S_{p′} ∩ M.

The set of elements m in S_{p′} ∩ M for which [m, ak] ∈ S_{p′} ∩ M is a group, so if {m_{1}, …, m_{s}} is a generating set of S_{p′} ∩ M then

ak ∈ N_{G}(S_{p′} ∩ M) ⇔ [m_{i}, ak] = l_{m_{i}} for 1 ≤ i ≤ s
⇔ h_{m_{i}} = [k, m_{i}^{a}] for 1 ≤ i ≤ s.

Thus if the element a = a_{i_{j}} and a generating set of S_{p′} ∩ M are given, then we can compute k_{i_{j}} as a solution of the system of s inhomogeneous equations h_{m_{i}} = [k, m_{i}^{a}]. Note that h_{m_{i}} is straightforward to obtain; since K is exhibited by A, it is just the K-part of the exponent vector of [m_{i}, a] with respect to A. Furthermore, since K is an elementary abelian p-group, the equations for k can be translated into a system of inhomogeneous linear equations over the field IF_{p}.

Now we modify the given Hall generating sequence A by substituting a_{i_{j}}k_{i_{j}} for a_{i_{j}}. The resulting polycyclic generating sequence B is obviously still compatible with the series K. Furthermore, since the only elements of A that we modify are in the Sylow subgroup S_{p}, and since K ≤ S_{p}, the resulting polycyclic generating sequence B exhibits Σ. Thus B is a Hall generating sequence associated to K and Σ that in addition exhibits N_{G}(S_{p′} ∩ M).

2.2. Separating M-central and M-hypereccentric factors

It remains to show how to construct a normal series K as required in the setup of Section 2.1. Suppose that L_{1}, …, L_{t} is an arbitrary normal series with elementary abelian factors of G. We refine this series such that each p-factor is either M-central or M-hypereccentric.

Let L = L_{i}/L_{i+1} be a p-factor in the given series. Clearly, [L, M] is normal in G/L_{i+1} and L/[L, M] is M-central. We calculate iterated commutators until the series L, [L, M], [[L, M], M], … becomes stable at a normal subgroup U of L with [U, M] = U.

If U = 1, then we have constructed a G-normal series for L with M-central factors. Suppose that U is non-trivial. Consider a G-normal series M = M_{1} ⊳ M_{2} ⊳ … ⊳ M_{d} ⊳ M_{d+1} = {1} with nilpotent factor groups. Such a series may be obtained by computing commutators or by using the given elementary abelian G-normal series compatible with the Hall generating sequence A. Since [U, M] = U and [U, 1] = 1, there exists a smallest index i such that [U, M_{i}] < U. Clearly, [U, M_{i}] is normal in G/L_{i+1}. We use the following observation to show that U/[U, M_{i}] is M-hypereccentric.

Lemma 2.2. If the nilpotent group N acts on the abelian group A with [A, N] = A, then A is hypereccentric under the action of N.

Proof. Consider the split extension H of A by N. The nilpotent residual subgroup H^{𝔑} of H is contained in A, since H/A is nilpotent. On the other hand [A, N] = A; thus A = H^{𝔑}. Since A is abelian, by Theorem 5.15 in (Carter and Hawkes, 1967) each complement to A in H is a system normalizer of H. Thus N is a system normalizer of H. By Theorem I(5.6) of (Doerk and Hawkes, 1992) a system normalizer avoids exactly the non-central chief factors, so each chief factor in A must be non-central. Therefore A is H-hypereccentric and thus N-hypereccentric. □

By definition and Lemma 2.2, the factor U/[U, M_{i}] is hypereccentric under the action of the nilpotent group M_{i−1}/M_{i}. Therefore U/[U, M_{i}] is also M-hypereccentric.

The first factor L/U in the chain L ⊵ U ⊵ [U, M_{i}] is M-hypercentral, and the second is M-hypereccentric. If [U, M_{i}] ≠ 1, then we may iterate the whole procedure, starting with [U, M_{i}] in place of L, until we arrive at the trivial subgroup of L. Thus we obtain a refinement of the factor L_{i}/L_{i+1} in the desired form.

3. Computing head complements

In the following lemma we observe that the algorithm to exhibit normalizers of the form N_{G}(S_{p′} ∩M) can be applied to compute conjugacy classes of complements in certain situations.

Lemma 3.1. Let A be an abelian normal p-subgroup of the finite group G, and let M be a normal subgroup of G such that M/A is nilpotent and [A, M] = A. Then there is exactly one conjugacy class of complements to A in G, namely the set of subgroups of form N_{G}(S_{p′} ∩ M), for S_{p′} a p-complement of G.

Proof. Let Q = S_{p′} ∩ M. Then Q is a p-complement of M and, since M/A is nilpotent, QA is a normal subgroup of G. By the Frattini argument, G = AN_{G}(Q). Since A is abelian, N_{A}(Q) = C_{A}(Q) = C_{A}(M), so N_{A}(Q) = 1 by Lemma 2.2, since [A, M] = A. Hence the conjugates of N_{G}(Q) complement A in G. On the other hand, if X complements A in G, then M ∩X complements A in M, so M ∩X must be a p-complement of M. Since X ≤ N_{G}(M ∩ X), and since N_{G}(M ∩ X) complements A, we have X = N_{G}(M ∩ X). □

Head complements are associated with the so-called special polycyclic generating sequences. We include a brief introduction to these sequences here.

Let G = G_{1} ⊳ … ⊳ G_{l} ⊳ {1} be the lower nilpotent series of G, and let G_{i}^{∗}/G_{i+1} be the Frattini subgroup of G_{i}/G_{i+1}. Then the so-called LG-series is an elementary abelian normal series which refines the series G = G_{1} ⊳ G_{1}^{∗} ⊵ G_{2} ⊳ … ⊳ G_{l} ⊵ G_{l}^{∗} ⊵ {1}. The factors G_{i}/G_{i}^{∗} are called the heads of G. A special polycyclic generating sequence is a Hall generating sequence compatible with the LG-series and exhibiting a complement to each head of G.

An effective algorithm to compute a Hall generating sequence compatible with the LG-series in a finite solvable group is introduced in (Cannon and Leedham-Green, 1993). Hence we may assume that we are given such a generating sequence A for G. We want to exhibit a complement to the head H = G_{i}/G_{i}^{∗} with i > 1. Since H is a direct product of elementary abelian groups, we can write H = H_{p} × H_{p′} for a prime p. Let A = H/H_{p′} ≅ H_{p}, an elementary abelian p-factor group of H. Let M = G_{i−1}/G_{i}^{∗}. Since G_{i−1}/G_{i} is a maximal nilpotent factor of G_{i−1}, we have that [A, M] = A. Thus the hypotheses of Lemma 3.1 are fulfilled and we can use this lemma and the method of Section 2 to exhibit a complement to A in G.

Now we iterate this procedure with the other primes p dividing the order of the head H to exhibit a complement to the head. For each step up the normal series we have to multiply elements of A \ G_{i} by preimages of elements of H/H_{p′}. Clearly, we can choose these preimages as preimages of elements of H_{p}, so the steps for the various primes p dividing the order of H do not interfere with each other. Thus we can modify A such that it exhibits a complement to each factor H/H_{p′}, and thus exhibits also the intersection of these complements, which is a complement to H.

This modification of the polycyclic generating sequence will not affect its compatibility with the LG-series or with the Hall system. Moreover, if we change A by multiplying its entries by elements of G_{i+1}, then it will still exhibit the complement to G_{i}/G_{i}^{∗}. Thus by working down the lower nilpotent series we can construct a Hall generating sequence that exhibits a complement to every head, i.e., a special polycyclic generating sequence.

For an alternative proof that it is possible to exhibit a Hall system and complements to all heads simultaneously, see (Eick, 1997).

4. Computing formation theoretic subgroups

This section contains algorithms to compute formation theoretic subgroups of finite solvable groups. For definitions and background on this subject we refer to (Gaschütz, 1963), (Carter and Hawkes, 1967) and (Doerk and Hawkes, 1992).

Let 𝔉 be a formation locally defined by the set {𝔉_{p} | p prime} of formations. To avoid technical problems, we assume that the local definition is integrated, i.e., that 𝔉_{p} ⊆ 𝔉 for each p. We allow 𝔉_{p} to be the empty set, and we call the set of primes p such that 𝔉_{p} is nonempty the support of 𝔉. Associated to each formation 𝔉 and each group G is the 𝔉-residual subgroup G^{𝔉} of G, the smallest normal subgroup of G whose factor group is in 𝔉.

Two types of subgroups of interest in connection with locally defined formations 𝔉 are the 𝔉-normalizers and 𝔉-covering subgroups of finite solvable groups. Both of these types of subgroups form characteristic conjugacy classes that are invariant under taking homomorphic images. Furthermore, these subgroups are themselves in the formation 𝔉. Well known examples of such subgroups are system normalizers and Carter subgroups, which arise as 𝔉-normalizers and 𝔉-covering subgroups for the formation 𝔉 of nilpotent groups.

In this section we will describe efficient algorithms to compute 𝔉-normalizers, 𝔉covering subgroups and 𝔉-residuals for locally defined formations 𝔉 and finite solvable groups G. For this purpose we represent the locally defined formation 𝔉 by a function that computes for each prime p in the support of 𝔉 the 𝔉_{p}-residual G^{𝔉_{p}} of G and, when necessary, residual subgroups U^{𝔉_{p}} for subgroups U of G. Each of our algorithms takes as input a Hall generating sequence and a means of computing the needed residuals.

4.1. Computing 𝔉-normalizers

To describe the 𝔉-normalizer algorithm we consider a slightly more general context. Let G be a finite solvable group, and let σ be a set of primes. For each prime p in σ let M_{p} be a normal subgroup of G, and define the function ν from σ into the set of normal subgroups of G by ν: p ↦ M_{p}. A ν-normalizer of G is a subgroup

D_{ν}(G, Σ) = S_{σ} ∩ ⋂_{p∈σ} N_{G}(S_{p′} ∩ M_{p})

where Σ is a Hall system with σ-Hall subgroup S_{σ} and p-complements S_{p′}. If the normal subgroup M_{p} is chosen to be the residual G^{𝔉_{p}} for each prime p in σ, then the resulting ν-normalizer

D_{𝔉}(G, Σ) = S_{σ} ∩ ⋂_{p∈σ} N_{G}(S_{p′} ∩ G^{𝔉_{p}})

is called an 𝔉-normalizer of G. Thus 𝔉-normalizers are a special case of ν-normalizers.

We can compute ν-normalizers of G by exhibition. Suppose that we are given a Hall generating sequence A of G that is compatible with an elementary abelian normal series G = K_{1}⊳K_{2}⊳…⊳K_{m}⊳K_{m+1} = {1} and that exhibits the Hall system Σ. By the results of Section 2.2, we may suppose that each factor K_{i}/K_{i+1} of p-power order is either M_{p}- central or M_{p}-hypereccentric for each p in σ. To obtain a polycyclic generating sequence that exhibits D_{ν}(G, Σ) as well, we modify A so that for each p in σ it exhibits the subgroup N_{G}(S_{p′} ∩ M_{p}), using the algorithm described in Section 2. Since this algorithm only modifies p-elements by p-elements, we can use it to exhibit all of the normalizers N_{G}(S_{p′} ∩ M_{p}) simultaneously. Moreover Σ remains exhibited throughout this process. Once all subgroups N_{G}(S_{p′} ∩ M_{p}) are exhibited, the intersection D_{ν}(G, Σ) is exhibited as well, by Theorem 1.2.

4.2. Computing 𝔉-covering subgroups

As above, let G be a finite solvable group and let 𝔉 be a locally defined formation. An 𝔉-covering subgroup of G is a subgroup U such that U ∈ 𝔉 and UV^{𝔉} = V for all subgroups V with U ≤ V ≤ G. Our method for computing such subgroups is based on the following facts ((Gaschütz, 1963) Hilfssatz 2.3 and (Carter and Hawkes, 1967) Theorem 5.6, or (Doerk and Hawkes, 1992) Proposition III(3.7) and Theorem V(4.2)).

Proposition 4.1. Let 𝔉 be a locally defined formation and G a finite solvable group.

(a) Let K ⊴ G and U ≤ G such that U/K is an 𝔉-covering subgroup of G/K. If V is an 𝔉-covering subgroup of U, then V is also an 𝔉-covering subgroup of G.

(b) If K is a nilpotent normal subgroup of U with U/K ∈ 𝔉, then the 𝔉-normalizers of U coincide with the F -covering subgroups of U.

Let A be a Hall generating sequence that exhibits a Hall system Σ and that is compatible with a series G = K_{1} ⊳ … ⊳ K_{m} ⊳ K_{m+1} = {1} of normal subgroups whose factors are p-groups. For example, we can use an elementary abelian normal series, or, in case A is a special polycyclic generating sequence, we may refine the lower nilpotent series by taking its maximal p-factors. Suppose inductively that A exhibits a subgroup U such that U/K_{j} is an 𝔉-covering subgroup of G/K_{j}. We wish to exhibit an 𝔉-normalizer of U/K_{j+1}, which by Proposition 4.1 will be 𝔉-covering in G/K_{j+1}. To do this it will be enough to consider the case that K_{j+1} = 1. Let K = K_{j}, and suppose that K is a p-group.

If p is not in the support σ of 𝔉, then S_{p′} ∩ U is an 𝔉-covering subgroup of U. Since A already exhibits this subgroup, by Theorem 1.2, no change in A is required.

Now suppose that p ∈ σ. By Proposition 1.3, Σ ∩ U is a Hall system of U. We wish to modify A to exhibit the corresponding 𝔉-normalizer

D_{𝔉}(U, Σ ∩ U) = S_{σ} ∩ N_{U}(S_{p′} ∩ U^{𝔉_{p}}) ∩ ⋂_{p≠q∈σ} N_{U}(S_{q′} ∩ U^{𝔉_{q}}).

Now U/K ∈ 𝔉 and D_{𝔉}(U, Σ∩U) is an 𝔉-covering subgroup of U, so U = KD_{𝔉}(U, Σ∩U). For p ≠ q ∈ σ we have K ≤ S_{q′}, and hence K ≤ N_{U}(S_{q′} ∩ U^{𝔉_{q}}). Since we have D_{𝔉}(U, Σ ∩ U) ⊆ N_{U}(S_{q′} ∩ U^{𝔉_{q}}) as well, and since U = KD_{𝔉}(U, Σ ∩ U), it follows that U = S_{σ} ∩ ⋂_{p≠q∈σ} N_{U}(S_{q′} ∩ U^{𝔉_{q}}), and thus D_{𝔉}(U, Σ ∩ U) = N_{U}(S_{p′} ∩ U^{𝔉_{p}}), a single normalizer of the type discussed in Section 2. Since D_{𝔉}(U, Σ ∩ U) covers U/K, we only need to employ the homomorphism principle to loop downward over an elementary abelian U-normal series through K in which all factors are either U^{𝔉_{p}}-central or U^{𝔉_{p}}- hypereccentric.

4.3. Computing 𝔉-residuals

Practical methods are known that compute residual subgroups for a number of important locally induced formations, based on their special properties. A generic approach is possible that proceeds from the group G downwards until no more 𝔉-central factors can be found, but for practical computation in the general case we prefer a method based on the following fact (cf. Theorem IV(3.2) of (Doerk and Hawkes, 1992)).

Proposition 4.2. Let G be a finite solvable group and 𝔉 a locally defined formation with support σ. Then

G^{𝔉} = O^{σ}(G) ∏_{p∈σ} O^{pp′}(G^{𝔉_{p}}).

Given the groups G^{𝔉_{p}} for all primes p in σ, this method only requires computing normal closures. It also obviously generalizes to deal with “internal formations” of the sort considered in (Wright, 1973a) and (Wright, 1973b).

5. Implementation and practicality

We have implemented our algorithms in the computer algebra system GAP 3.4 (see (Schönert et al., 1995)). This section contains some timings of our implementations, using the following groups as examples.

• MF i22 is a maximal subgroup of order 2^{8} · 3^{9} of the finite simple group F i_{22}.

• U ≀C_{3} is a wreath product of the subgroup U of upper triangular matrices in GL(4, 7) with the cyclic group of order 3. This group has order 2^{12} · 3^{13} · 7^{18}.

• Lux is a group of order 2^{55} · 3^{7} · 7^{3}. It was constructed so that a chief series would be hard to compute.

• Dark is a group of order 2^{3} · 3^{9} · 5^{24} · 7 · 31^{8}. See (Doerk and Hawkes, 1992), pp. 630ff, for an outline of its construction.

All of our algorithms depend on having a Hall generating sequence as starting point. The GAP 3 command SpecialAgGroup(G, "noHead") provides such sequences. The sample timings below do not include this preprocessing step. To give the reader an idea of the practicality of our methods, we present the times to exhibit a set of head complements, an 𝔉-normalizer and an 𝔉-covering subgroup for the formation 𝔉 of supersolvable groups. We chose to describe experiments with this formation because its local definition is moderately hard to compute with.

The timings in the following table were obtained using GAP 3.4.4 started with 8 megabytes of workspace on a 486 PC. They include garbage collections, and thus reflect on the space requirements of the algorithms as well. Times are given in seconds.

head complements  𝔉-normalizer  𝔉-covering subgroup
group number  time  order  time  order  time
MF i22  4  0.1  2^{2} · 3^{3}  0.3  2^{2} · 3^{9}  2.1
U ≀ C_{3}  3  0.6  2^{4} · 3^{13}  1.1  2^{4} · 3^{13}  0.8
Lux  4  1.8  2 · 3^{7} · 7 6.0  2 · 3^{7} · 7  6.3
Dark  6  1.0  3^{2} · 7  0.9 3^{3} · 7 · 31^{2}  10.0

The comparatively large time for the 𝔉-covering subgroup of the group Dark comes from the computation of the local residuals, which is rather complicated in this case. Altogether the timings are at most 10 seconds, although some of the groups considered are already quite large.

6. Complexity analysis

We measure the algorithms’ computational effort by the total number of group multiplications, field multiplications and field additions they entail. The input parameters are the length n of the input polycyclic generating sequence for the group G, the size p of the largest prime divisor of |G|, and a parameter t describing the complexity of an algorithm to compute the residual subgroups U^{𝔉_{q}} for U ≤ G and q a prime.

Field operations are used in the normalizer calculation, where the modification of a single generator takes O(n^{4}) field operations in addition to O(n^{3} log p) group operations. The remaining algorithms use group multiplications only.

We need a few well-known algorithms to compute with groups given by polycyclic generating sequences; see (Laue et al., 1984) for more information on such methods. The basic steps of computing the exponent vector for an element relative to a polycyclic generating sequence and of finding an induced polycyclic generating sequence for a subgroup require O(n log p) and O((r + n^{2})n log p) operations, respectively, where r is the number of generators of the subgroup in question.

The most time-consuming step in computing 𝔉-residual subgroups is finding normal closures, which can be done in O(n^{4} log p) operations. Thus finding a locally defined residual subgroup has complexity O(nt + n^{5} log p), with t typically negligible.

The first step in the 𝔉-normalizer calculation is the refinement of the elementary abelian series exhibited by a given Hall generating sequence as described in Section 2.2. This takes O(n^{4} log p log n) operations. To modify a single element of a polycyclic generating sequence as required by the 𝔉-normalizer algorithm takes O(n^{3}(log p + n)) operations, so the complete 𝔉-normalizer algorithm runs in time O(n(t + n^{4} log p)). Hence finding an 𝔉-covering subgroup takes O(n^{2}(t + n^{4} log p)) operations.

Appendix A. Computing a Sylow complement system

This appendix contains an algorithm to construct a polycyclic generating sequence that exhibits a system of Sylow complements of a finite solvable group, and hence exhibits a Sylow system of the group. The algorithm is similar in pattern to those in Section 2. We present the algorithm as pseudocode in Figure 1 and include a proof of its correctness below.

We use the same notation as in the Sylow Complement System algorithm for the proof of the correctness. First note that if z ∈ K_{j}, then since K_{j} ≤ C_{i+1} we have a_{i}z in C_{i}\C_{i+1}. Thus replacing a_{i} by a_{i}z gives a polycyclic generating sequence that determines the same composition series G = C_{1} ⊳ … ⊳ C_{n+1} = 1.

For i = n, A exhibits a complement system of C_{n+1} = 1. We assert that if A exhibits a complement system of C_{i+1} before entering the inner for loop then A exhibits a complement system of C_{i} on exit from that loop. It will follow that A exhibits a complement system of C_{1} = G on exit from the outer loop.

Suppose that A exhibits a complement system of C_{i+1}. For convenience we introduce the terminology “H is an r-complement in L mod K” to mean that K ≤ H ≤ L and that H/K is an r-complement of L/K. A complement system of L mod K is a complete set of such subgroups of L. Since C_{i}/K_{t} is a p-group, A exhibits a complement system of C_{i} mod K_{t}. We will show that if A exhibits a complement system of C_{i} mod K_{j} at the start of the inner loop, then A exhibits a complement system of C_{i} mod K_{j+1} at the end

input: A polycyclic generating sequence A = (a_{1}, …, a_{n}) determining the composition series G = C_{1} ⊳ … ⊳ C_{n+1} = 1 and refining the elementary abelian normal series G = K_{1} ⊳ … ⊳ K_{m+1} = 1.

output: A polycyclic generating sequence exhibiting a Sylow complement system.

for i = n down to 1 do Find t with K_{t−1} ≥ C_{i} > C_{i+1} ≥ K_{t}. for j = t to m do

Let p = |C_{i}/C_{i+1}| and let q be the prime dividing [K_{j} : K_{j+1}].

if p ≠ q then Let B be a set of generators for the q-complement R of C_{i+1} that A exhibits. Let a = a_{i}, and factor a^{p} = x · y and [b, a] = x_{b} · y_{b} for each b in B, with

x and x_{b} in R and y and y_{b} in K_{j}. Let z in K_{j} be a solution mod K_{j+1} of the system of congruences z^{−1} · z^{−a} ⋯ z^{−a^{p−1}} ≡ y and z^{−1} · z^{b[b,a]} ≡ y_{b} for all b in B.

Replace a_{i} by az. fi od

od

return A

Figure 1. Sylow Complement System

of the loop. It will follow that on exit from the loop A exhibits a complement system for C_{i} mod K_{m+1}, i.e., a complement system of C_{i}.

Thus suppose that A exhibits a complement system of C_{i+1} and also exhibits a complement system of C_{i} mod K_{j} for some j with t ≥ j ≥ m. Let p = [C_{i} : C_{i+1}] and let q be the prime dividing [K_{j} : K_{j+1}].

We will modify A by replacing a_{i} by a_{i}z for some z in K_{j}. Since z ∈ K_{j} ≤ C_{i+1}, such a replacement does not change the subgroups of C_{i+1} that are exhibited. Hence the new polycyclic generating sequence will exhibit the same complement system of C_{i+1} that A does.

If R_{p′} is the p-complement of C_{i+1} that A exhibits, then R_{p′}K_{j+1} is a p-complement of C_{i} mod K_{j+1} that A exhibits. Moreover, for primes r ≠ q the r-complement S_{r′} of C_{i} mod K_{j} that A exhibits is an r-complement of C_{i} mod K_{j+1}. Thus if p = q, then A already exhibits a complement system of C_{i} mod K_{j+1} and no modification of A is required.

Suppose now that p ≠ q. Since R_{p′} ≤ C_{i+1}, the new A will still exhibit R_{p′}K_{j+1}. IF r is a prime such that p ≠ r ≠ q, then A exhibits an r-complement S_{r′} of C_{i} mod K_{j}, which is also an r-complement of C_{i} mod K_{j+1} since r ≠ q. Since A exhibits a complement system of C_{i} mod K_{j}, it exhibits a p-Sylow subgroup of C_{i} mod K_{j}, which must contain a_{i} and, because r ≠ p, must be contained in S_{r′}. Hence a_{i}K_{j} ⊆ S_{r′}. Since A exhibits S_{r′} ∩ C_{i+1}, and since both a_{i} and a_{i}z are in S_{r′} \ C_{i+1}, the new A will still exhibit the r-complement S_{r′} of C_{i} mod K_{j+1}.

As we shall see below, the solutions of the system of congruences in the algorithm are precisely the elements z for which the polycyclic generating sequence obtained by replacing a_{i} by a_{i}z exhibits a q-complement of C_{i} mod K_{j+1}. The issue here is whether K_{j} contains any such solutions. We now show that it does.

Let S be the q-complement of C_{i} mod K_{j} and R the q-complement of C_{i+1} that A exhibits. Let T be a q-complement of C_{i} that contains R. Then T ∩ C_{i+1} = R and T K_{j} is a q-complement of C_{i} mod K_{j}, so S = (T K_{j})^{c} = T^{c}K_{j} for some c in C_{i}. Moreover, R^{c}K_{j} = (T ∩C_{i+1})^{c}K_{j} = (T^{c} ∩C_{i+1})K_{j} = (T^{c}K_{j})∩C_{i+1} = S ∩C_{i+1}, a q-complement of C_{i+1} mod K_{j} exhibited by A. Thus R^{c}K_{j} must be RK_{j}. Since both RK_{j+1} and R^{c}K_{j+1} are q-complements of C_{i+1} mod K_{j+1}, Corollary I(4.14)(c) of (Doerk and Hawkes, 1992) implies that RK_{j+1} = R^{cu}K_{j+1} for some u in K_{j}.

We have T^{cu}K_{j} = T^{c}K_{j} = S. Also a_{i} ∈ S, since p ≠ q and A exhibits S. Hence there is a z in K_{j} with a_{i}z ∈ T^{cu} ≤ S. Now R^{cu} is maximal normal in T^{cu} and R^{cu} ≤ C_{i+1}^{cu} = C_{i+1}, so a_{i}z ∉ R^{cu}K_{j+1} = RK_{j+1}. It follows that ⟨a_{i}z, RK_{j+1}⟩ = T^{cu}K_{j+1}, that (a_{i}z)^{p} ∈ RK_{j+1} and that a_{i}z normalizes RK_{j+1}, i.e., that the polycyclic generating sequence obtained from A by replacing a_{i} by a_{i}z exhibits the q-complement T^{cu}K_{j+1} of C_{i} mod K_{j+1}.

For notational convenience, let a = a_{i}. Factor a^{p} into x · y with x ∈ R and y ∈ K_{j}, and factor [b, a] similarly into x_{b} · y_{b} for each b ∈ B, where ⟨B⟩ = R. Since (az)^{p} = a^{p}z^{a^{p−1}} ⋯ z^{a}z, we have

(az)^{p} ∈ RK_{j+1} ⟺ yz^{a^{p−1}} ⋯ z^{a}z ∈ K_{j} ∩ RK_{j+1} = K_{j+1}
⟺ y ≡ z^{−1}z^{−a} ⋯ z^{−a^{p−1}} mod K_{j+1}.

As we noted in Section 2.1, for each g in G the set of elements v of RK_{j+1} for which [v, g] ∈ RK_{j+1} is a group. Hence az normalizes RK_{j+1} if and only if [b, az] ∈ RK_{j+1} for every b in B. Since [b, az] = x_{b} · y_{b} · [z, b^{a}]^{−1},

[b, az] ∈ RK_{j+1} ⟺ x_{b} · y_{b} · [z, b^{a}]^{−1} ∈ RK_{j+1}
⟺ y_{b} ≡ [z, b^{a}] mod K_{j+1}.

These arguments show not only that K_{j} contains an element z satisfying the system of congruences but also that every solution of the system of congruences can be used to replace a_{i} by a_{i}z and exhibit a complement system of C_{i} mod K_{j+1}.

This completes the proof that the algorithm returns a complement system of G.

Acknowledgements. The first author’s work on this paper was supported by the Graduiertenkolleg “Analyse und Konstruktion in der Mathematik” at RWTH Aachen. The second author especially wishes to thank the Deutsche Akademische Austauschdienst and the RWTH Aachen for their support during the preparation of this article. We are in debt to Joachim Neubüser for his help and his support on this project and to Klaus Lux for supplying us with a test group.

References

Cannon, J., Leedham-Green, C. R. (1993). Special presentations of finite soluble groups. Unpublished. Carter, R. W., Hawkes, T. O. (1967). The 𝔉-normalizers of a finite soluble group. J. Alg, 5:175 – 201. Celler, F., Neubüser, J., Wright, C. R. B. (1990). Some remarks on the computation of complements

and normalizers in finite soluble groups. Acta Applic. Math, 21:57 – 76. Doerk, K., Hawkes, T. O. (1992). Finite soluble groups. Walter de Gruyter. Eick, B. (1997). Special presentations of finite soluble groups and computing (pre-) frattini subgroups.

In Finkelstein, L., Kantor, W., editors, DIMACS series ‘Groups and Computation’ 1996. Amer. Math. Soc.

Gaschütz, W. (1963). Zur Theorie der endlichen auflösbaren Gruppen. Math. Z., 80:300 – 305. Laue, R., Neubüser, J., Schoenwaelder, U. (1984). Algorithms for finite soluble groups and the sogos

system. In Atkinson, M. D., editor, Proceedings of the LMS symposium on computational group theory, Durham 1982, pages 105 – 135. Academic Press.

Niemeyer, A. C. (1994). A finite soluble quotient algorithm. J. Symb. Comput., 18:541 – 561.

Plesken, W. (1987). Towards a soluble quotient algorithm. J. Symb. Comput., 4:111 – 122. Schönert, M. et al. (1995). GAP - Groups, Algorithms and Programming, Lehrstuhl D für Mathematik,

Rheinisch Westfälische Technische Hochschule, Aachen, Germany, fifth edition. Sims, C. C. (1990). Computing the order of a solvable permutation group. J. Symb. Comput., 9:699 –

705. Sims, C. C. (1994). Computation with finitely presented groups. Cambridge University Press. Wright, C. R. B. (1973a). An internal approach to covering groups. J. Alg., 25:128 – 145. Wright, C. R. B. (1973b). On internal formation theory. Math. Z., 134:1 – 9.