A Polynomial Time Nilpotence Test for Galois Groups and Related Results

V. Arvind^{1} and Piyush P Kurur^{2}

1 Institute of Mathematical Sciences C.I.T Campus,Chennai, India 600 113

                            arvind@imsc.res.in

2 Department of Computer Science and Engineering, Indian Institute of Technology, Kanpur, Kanpur, UP 208016, India

                           ppk@cse.iitk.ac.in ^{⋆}

Abstract. We give a deterministic polynomial-time algorithm to check whether the Galois group Gal (f) of an input polynomial f(X) ∈ ℚ[X] is nilpotent: the running time is polynomial in size (f). Also, we generalize the Landau-Miller solvability test to an algorithm that tests if Gal (f) is in Γ_{d}: this algorithm runs in time polynomial in size (f) and n^{d} and, moreover, if Gal (f) ∈ Γ_{d} it computes all the prime factors of #Gal (f).

1 Introduction

Computing the Galois group of a polynomial is a fundamental problem in algorithmic number theory. Asymptotically, the best known algorithm is due to Landau [3]: on input f(X), it takes time polynomial in size (f) and the order of its Galois group Gal (f). If f(X) has degree n then Gal (f) can have n! elements. Thus, Landau’s algorithm takes time exponential in input size. It is a long standing open problem if there is an asymptotically faster algorithm for computing Gal (f). Lenstra’s survey [6] discusses this and related problems.

A different kind of problem is to test for a given f(x) if Gal (f) satisfies a specific property without explicitly computing it. Galois’s seminal work showing f(X) is solvable by radicals if and only if Gal (f) is solvable is a classic example. Landau and Miller [4] gave a remarkable polynomial-time algorithm for testing solvability of the Galois group without computing the Galois group.

1.1 The results of this article

Our main result is a deterministic polynomial-time algorithm for testing if Gal (f) is nilpotent. Although nilpotent groups are a proper subclass of solvable groups, the Landau-Miller solvability test does not give a nilpotence test. Basically, the Landau-Miller test is a method of testing that all composition factors of Gal (f)

⋆ work done when the author was a PhD student at the Institute of Mathematical Sciences, Chennai.

are abelian, which tests solvability. Nilpotence however is a more “global” property, in the sense that it cannot be inferred by properties of the composition factors alone.

We note here that nilpotence testing of Galois groups has been addressed by other researchers with the goal of developing good practical algorithms. For example in [2] an algorithm for nilpotence testing is given which takes time polynomial in size (f) and #Gal (f). However, ours is the first algorithm that is provably polynomial time, i.e. runs in time polynomial in size (f), on all inputs.

Next, we show that the Landau-Miller solvability test can be extended to a polynomial-time algorithm for checking, given f ∈ ℚ[X], if Gal (f) is in Γ_{d} for constant d. A group G is in Γ_{d} if there is a composition series G = G_{0}▷…▷G_{t} = {1} such that each nonabelian composition factor G_{i}/G_{i+1} is isomorphic to a subgroup of S_{d}. The class Γ_{d} often arises in permutation group algorithms (see e.g. [7]). Moreover, if Gal (f) ∈ Γ_{d}, the prime factors of #Gal (f) can be found in polynomial time.

1.2 Galois theory overview

We quickly recall some Galois theory (see, e.g. [5] for details). Let L and K be fields. If L ⊃ K, we say that L is an extension of K and denote it by L/K. If L/K then L is a vector space over K and by the degree of L/K, denoted by [L : K], we mean its dimension. An extension L/K is finite if its degree [L : K] is finite. If L/M and M/K are finite extensions then [L : K] = [L : M].[M : K]. The polynomial ring K[X] is a unique factorisation domain: every polynomial can be uniquely (up to scalars) written as a product of irreducible polynomials. Let L/K be an extension. An α ∈ L is algebraic over K if f(α) = 0 for some f(X) ∈ K[X]. For α algebraic over K, the minimal polynomial of α over K is the unique monic polynomial μ_{α}[K](X) of least degree in K[X] for which α is a root. We write μ_{α}(X) for μ_{α}[K](X) when K is understood. Elements α, β ∈ L are conjugates over K if they have the same minimal polynomial over K. The smallest subfield of L containing K and α is denoted by K(α).

The splitting field K_{f} of f ∈ K[X] is the smallest extension of K containing all the roots of f. A finite extension L/K is normal if for all irreducible polynomials f(X) ∈ K[X], either f(X) splits or has no root in L. Any normal extension over K is the splitting field of some polynomial in K[X]. An extension L/K is separable if for all irreducible polynomials f(X) ∈ K[X] there are no multiple roots in L. A normal and separable finite extension L/K is a Galois extension.

The Galois group Gal (L/K) of L/K is the subgroup of automorphisms σ of L that leaves K fixed, i.e. σ(α) = α for all α ∈ K. The Galois group Gal (f) of f ∈ K[X] is Gal (K_{f}/K). For a subgroup G of automorphisms of L, the fixed field L^{G} is the largest subfield of L fixed by G. We now state the fundamental theorem of Galois.

Theorem 1. [5, Theorem 1.1, Chapter VI] Let L/K be a Galois extension with Galois group G. There is a one-to-one correspondence between subfields E of L containing K and subgroups H of G, given by E ⇌ L^{H}. The Galois group of Gal (L/E) is H and E/K is a Galois extension if and only if H is a normal subgroup of G. If H is a normal subgroup of G and E = L^{H} then Gal (E/K) is isomorphic to the quotient group G/H.

1.3 Presenting algebraic numbers, number fields and Galois groups

The algorithms we describe take objects like algebraic numbers, number fields etc. as input. We define sizes of these objects. Integers are encoded in binary. A rational r is given by coprime integers a, b such that r = a/b. Thus, size (r) is size (a) + size (b). A polynomial T (X) = a_{0} + … + a_{n}X^{n} ∈ ℚ[X] is given by a list of its coefficients. Thus, size (T) is defined as ∑ size (a_{i}).

A number field is a finite extension of ℚ. Let K/ℚ be a number field of degree n. By the primitive element theorem [5, Theorem 4.6, Chapter V], there is an algebraic number η ∈ K such that K = ℚ(η). Such an element is a primitive element of K/ℚ and its minimal polynomial is a primitive polynomial. Let μ_{η}(X) be the minimal polynomial of η over ℚ. Then the field K can be written as the quotient K = ℚ[X]/μ_{η}(X). Thus K can be presented by giving a primitive polynomial for K/ℚ. We can assume that η is an algebraic integer and hence its minimal polynomial μ_{η}(X) has integer coefficients [5, Proposition 1.1, Chapter VII]. When we say that an algorithm takes a number field K as input we mean that it takes a primitive polynomial μ_{η}(X) for K as input. Thus the input size for K, which we denote by size (K), is defined to be size (μ_{η}).

Suppose K = ℚ(η) is presented by μ_{η}(X). Notice that each α ∈ K can be expressed as α = A_{α}(η) for a unique polynomial A_{α}(X) ∈ ℚ[X] of degree less than n. By size (α) we mean size (A_{α}(X)). Note that the size of α ∈ K depends on the primitive element η ∈ K. Now, for a polynomial f(X) = a_{0} +…+a_{m}X^{m} in K[X] we define size (f) to be ∑ size (a_{i}).

Let f(X) ∈ ℚ[X] of degree n. For an algorithm purporting to compute Gal (f), one possibility is that it outputs the complete multiplication table for Gal (f). However, this could be exponential in size (f) as Gal (f) can be as large as n!. A succinct presentation of Gal (f) is as a permutation group acting on the roots of f since elements of Gal (f) permute the roots of f and are completely determined by their action on the roots of f. Thus, by numbering the roots of f, we can consider Gal (f) as a subgroup of the symmetric group S_{n} (note here that Gal (f) is determined only up to conjugacy as the numbering of the roots is arbitrary). Since any subgroup of S_{n} has a generator set of size n − 1 (see e.g. [8]), we can present Gal (f) in size polynomial in n. Thus, by computing Gal (f) we mean finding a small generator set for it as a subgroup of S_{n}. Determining Gal (f) as a subgroup of S_{n} is a reasonable way of describing the output. Algorithmically, we can answer several natural questions about a subgroup G of S_{n} given by generator set in polynomial time. E.g. testing if G is solvable, finding a composition series for G etc. [8].

Previous complexity results As mentioned, the best known algorithm for computing the Galois group of a polynomial is due to Landau [3].

Theorem 2 (Landau). There is a deterministic algorithm that takes as input a number field K, a polynomial f(X) ∈ K[X] and a positive integer b in unary, and in time bounded by size (f), size (K) and b, decides if Gal (K_{f}/K) has at most b elements, and if so computes Gal (K_{f}/K) by finding the entire multiplication table of Gal (K_{f}/K) (and hence also by giving the generating set of Gal (K_{f}/K) as a permutation group on the roots of f(X)).

The algorithm first computes a primitive element θ of K_{f}. Determining Gal (f) amounts to finding the action of the automorphisms on θ. Subsequently, Landau and Miller [4] gave their polynomial-time solvability test.

Theorem 3 (Landau-Miller). Given f(X) ∈ ℚ[X] there is a deterministic polynomial-time algorithm for testing if Gal (f) is solvable.

2 Preliminaries

We recall some permutation group theory from Wielandt’s book [9]. Let Ω be a finite set. The symmetric group Sym (Ω) is the group of all permutations on Ω. By a permutation group on Ω we mean a subgroup of Sym (Ω). For α ∈ Ω and g ∈ Sym (Ω), let α^{g} denote the image of α under the permutation g. For A ⊆ Sym (Ω), α^{A} denotes the set {α^{g} : g ∈ A}. In particular, for G ≤ Sym (Ω) the G-orbit containing α is α^{G}. The G-orbits form a partition of Ω. Given G ≤ Sym (Ω) by a generating set A and α ∈ Ω, there is a polynomial-time algorithm to compute α^{G} [8].

For Δ ⊆ Ω and g ∈ Sym (Ω), Δ^{g} denotes {α^{g} : α ∈ Δ}. The setwise stabilizer of Δ, i.e. {g ∈ G : Δ^{g} = Δ}, is denoted by G_{Δ}. If Δ is the singleton set {α} we write G_{α} instead of G_{{α}}. For any Δ by G|_{Δ} we mean G_{Δ} restricted to Δ. An often used result is the orbit-stabilizer formula stated below [9, Theorem 3.2].

Theorem 4 (Orbit-stabilizer formula). Let G be a permutation group on Sym (Ω) and let α be any element of Ω then the order of the group G is given by #G = #G_{α}.#α^{G}.

A permutation group G on Ω is transitive if there is a single G-orbit. Suppose G ≤ Sym (Ω) is transitive. Then a non-empty subset Δ of Ω is a G-block if for all g ∈ G either Δ^{g} = Δ or Δ^{g} ∩ Δ = ∅. For every G, Ω is a block and each singleton {α} is a block. These are the trivial blocks of G. A transitive group G is primitive if it has only trivial blocks and it is imprimitive if it has nontrivial blocks. A G-block Δ is a maximal subblock of a G-block Σ if Δ ⊂ Σ and there is no G-block Υ such that Δ ⊂ Υ ⊂ Ω. Let Δ and Σ be two G-blocks. A chain Δ = Δ_{0} ⊂ … ⊂ Δ_{t} = Σ is a maximal chain of G-blocks between Δ and Σ if for all i, Δ_{i} is a maximal subblock of Δ_{i+1}.

For a G-block Δ and g ∈ G, Δ^{g} is also a G-block such that #Δ = #Δ^{g}. Let Δ and Σ be two G-blocks such that Δ ⊆ Σ. The Δ-block system of Σ, is the collection

B (Σ/Δ) = {Δ^{g} : g ∈ G and Δ^{g} ⊆ Σ}.

The set B (Σ/Δ) is a partition of Σ. It follows that #Δ divides #Σ and by index of Δ in Σ, which we denote by [Σ : Δ], we mean #B (Σ/Δ) = \frac{#Σ}{#Δ}. We will use B (Δ) to denote B (Ω/Δ). We state the connection between blocks and subgroups [9, Theorem 7.5].

Theorem 5 (Galois correspondence of blocks). Let G ≤ Sym (Ω) be transitive and α ∈ Ω. For G ≥ H ≥ G_{α} the orbit Δ = α^{H} is a G-block and G_{Δ} = H. The correspondence α^{H} = Δ ⇌ G_{Δ} = H is a one-to-one correspondence between G-blocks Δ containing α and subgroups H of G containing G_{α}. Furthermore for G-blocks Δ ⊆ Σ we have [G_{Σ} : G_{Δ}] = [Σ : Δ].

Let G ≤ Sym (Ω) be transitive and Δ and Σ be two G-blocks such that Δ ⊆ Σ. Let G(Σ/Δ) denote the group {g ∈ G : Υ^{g} = Υ for all Υ ∈ B (Σ/Δ)}. We write G^{Δ} for the group G (Ω/Δ). For any g ∈ G_{Σ}, since g setwise stabilises Σ, g permutes the elements of B (Σ/Δ). Hence for any Υ ∈ B (Σ/Δ) we have Υ^{g^{−1}G(Σ/Δ)g} = Υ. Thus, G (Σ/Δ) is a normal subgroup of G_{Σ}. In particular, G^{Δ} is a normal subgroup of G. Remark. The following two lemmata are quite standard in permutation group theory. For the reader’s convenience we have included short proofs. The following lemma lists important properties of G^{Δ}.

Lemma 1.

1. For a G-block Δ ⊆ Σ, G (Σ/Δ) is the largest normal subgroup of G_{Σ} contained in G_{Δ}.

2. Let Σ be G-block then G^{Σ} ↪ ∏_{Υ ∈B(Σ)} G|_{Υ}.

3. Let Δ be a G-subblock of Σ then \frac{G_{Σ}}{G(Σ/Δ)} is a faithful permutation group on B (Σ/Δ) and is primitive when Δ is a maximal subblock.

4. The quotient group G^{Σ}/G^{Δ} can be embedded as a subgroup of (\frac{G_{Σ}}{G(Σ/Δ)})^{l} for some l.

Proof. Let N ⊆ G_{Δ} be a normal subgroup of G_{Σ}. Since Δ^{N} = Δ, and since G_{Σ} acts transitively on B (Σ/Δ), for any Υ ∈ B (Σ/Δ) there is a g ∈ G_{Σ} such that Υ = Δ^{g}. Therefore, Υ^{N} = Δ^{gN} = Δ^{Ng} = Υ for each Υ ∈ B (Σ/Δ). Thus N ⊆ G (Σ/Δ). Since G (Σ/Δ) ⊴ G_{Σ} we have proved part 1.

Part 2 directly follows from the definition of G^{Σ}. Part 3 follows from the fact that g, h ∈ G_{Σ} have the same action on B (Σ/Δ) precisely when gG (Σ/Δ) = hG (Σ/Δ). The nontrivial \frac{G_{Σ}}{G(Σ/Δ)}-blocks of B (Σ/Δ) are in 1-1 correspondence with the G-blocks properly between Δ and Σ. Thus, \frac{G_{Σ}}{G(Σ/Δ)} is primitive if and only if Δ is a maximal subblock of Σ.

For Part 4 notice that we have the group isomorphism

\begin{matrix}G| & Υ \\ G (Υ/Δ_{Υ})| & Υ \end{matrix} ≅ \frac{G_{Υ}}{G (Υ/Δ_{Υ})},

for each Υ ∈ B (Σ). As G^{Δ} = G^{Σ} ∩ ∏ G (Υ/Δ_{Υ})|_{Υ} we have

G^{Σ}/G^{Δ} ↪ ∏_{Υ ∈B(Σ)} \begin{matrix}G| & Υ \\ G (Υ/Δ_{Υ})| & Υ \end{matrix} = ∏_{Υ ∈B(Σ)} \frac{G_{Υ}}{G (Υ/Δ_{Υ})}.

Let g ∈ G such that Δ^{g} = Δ_{Υ}. Then, G_{Υ} = g^{−1}G_{Σ}g and G (Υ/Δ_{Υ}) = g^{−1}G (Σ/Δ)g. Thus, \frac{G_{Σ}}{G(Σ/Δ)} and \frac{G_{Υ}}{G(Υ/Δ_{Υ})} are isomorphic, which implies that

G^{Σ}/G^{Δ} is isomorphic to a subgroup of (\frac{G_{Σ}}{G(Σ/Δ)})^{l} for some l.

Lemma 2. Let G ≤ Sym (Ω) be transitive and N ⊴ G. Let α ∈ Ω. Then the N-orbit α^{N} is a G-block and the collection of N-orbits is an α^{N}-block system of Ω under G action. If N ≠ {1} then ∥α^{N}∥ > 1. Furthermore, if G_{α} ≤ N ≠ G then the α^{N}-block system is nontrivial implying that G is not primitive.

Proof. Let α ∈ Ω and g ∈ G. Then (α^{N})^{g} = α^{Ng} = α^{gN} = (α^{g})^{N}. Thus (α^{N})^{g} and α^{N} are N-orbits, and hence are identical or disjoint. Thus, α^{N} is a G-block and the N-orbits form a block system. Clearly, if α^{N} = {α} then N = {1}. Finally, by the Orbit-Stabilizer formula #G = #Ω·#G_{α} and #N = #α^{N} ·#G_{α}. Thus, if {1} ≠ N ≠ G then α^{N} is a proper G-block.

3 Nilpotence testing for Galois groups

First we recall crucial properties of nilpotent transitive permutation groups. These are standard group theoretic facts that we assemble together and, for the sake of completeness, provide proof sketches where necessary. We start with a characterization of finite nilpotent groups. Let G be a finite group and p_{1}, …, p_{k} be the prime factors of #G. For each i, let G_{p_{i}} be a p_{i}-Sylow subgroup of G. Then G is nilpotent if and only if G is the (internal) direct product G_{p_{1}} × … × G_{p_{k}}. Consequently, G_{p_{i}} is the unique p_{i}-Sylow subgroup of G for each i and hence G_{p_{i}} ◁ G.

Lemma 3. Let G ≤ Sym (Ω) be transitive and nilpotent, and p be any prime. Then

(1) The prime p divides #G if and only if p divides #Ω.

(2) If p | #G and α ∈ Ω then there is a block Σ_{p}^{α} containing α such that #Σ_{p}^{α} is the highest power of p that divides #Ω.

(3) Let Δ be any G-block containing α such that #Δ = p^{l} and suppose p divides #G. Then Δ ⊆ Σ_{p}^{α}. Also, for q ≠ p, the q-Sylow subgroup of G_{Δ} is given by G_{q} ∩ G_{Δ} = G_{q} ∩ G_{α}.

Proof. Part (1): As G is transitive, #Ω divides #G. Hence, each prime factor of #Ω divides #G. Let p be a prime factor of #G. For α ∈ Ω, let Σ_{p}^{α} = α^{G_{p}}. Since G_{p} is transitive on Σ_{p}^{α}, it follows from the Orbit-Stabilizer formula that #Σ_{p}^{α} divides #G_{p}. Hence #Σ_{p}^{α} is p^{l} for some l. Since G_{p} ◁ G, by Lemma 2 it follows that its orbit Σ_{p}^{α} is G-block which contains more than one element of Ω. Hence #Σ_{p}^{α} = p^{l} for some l > 0. Since p divides the cardinality of a G-block Σ_{p}^{α}, p divides #Ω.

Part (2): From the Galois correspondence of G-blocks (Theorem 5) we have [Ω : Σ_{p}^{α}] = [G : G_{Σ_{p}^{α}}]. Notice that p is not a factor of [G : G_{p}] as G_{p} is the p-Sylow subgroup of G. Since G_{p} ◁ G_{Σ_{p}^{α}} it follows that p is not a factor of [G : G_{Σ_{p}^{α}}]. Hence p is not a factor of [Ω : Σ_{p}^{α}].

Part (3): notice that G_{Δ} is a nilpotent group with the unique normal q-Sylow subgroup G_{q} ∩ G_{Δ}. Thus, G_{Δ} = ∏_{q}(G_{q} ∩ G_{Δ}). By Theorem 5 we have

#Δ = [G_{Δ} : G_{α}] = ∏_{q}[G_{q} ∩ G_{Δ} : G_{q} ∩ G_{α}].  (1)

Since G_{q} ∩ G_{Δ} is a q-group, p divides [G_{q} ∩ G_{Δ} : G_{q} ∩ G_{α}] if and only if q = p. However, in Equation 1, #Δ is a power of p. This forces [G_{q} ∩G_{Δ} : G_{q} ∩G_{α}] = 1 for all q ≠ p. Thus G_{q} ∩ G_{Δ} = G_{q} ∩ G_{α} for q ≠ p. Therefore, G_{Δ} is the product group G_{p} ∩ G_{Δ} × ∏_{q≠p} G_{q} ∩ G_{α}. Since G_{Σ_{p}^{α}} contains both G_{p} and G_{α} we have G_{Σ_{p}^{α}} ≥ G_{Δ}. Thus, Δ is a G-subblock of Σ_{p}^{α}.

We recall a result about permutation p-groups (see e.g. Luks [7, Lemma 1.1]).

Lemma 4. Let G ≤ Sym (Ω) be a transitive p-group and Δ be a maximal Gblock. Then [Ω : Δ] = p and G_{Δ} = G (Ω/Δ) = G^{Δ} is a normal group of index p in G.

The next lemma is an easy consequence of Lemma 4 and it states a useful property of permutation p-groups.

Lemma 5. Let H ≤ Sym (Ω) be a transitive p-group and α ∈ Ω. Let {α} = Δ_{0} ⊂ … ⊂ Δ_{t} = Ω be any maximal chain of H-blocks. Then

1. [Δ_{i+1} : Δ_{i}] = p for all 0 ≤ i < t.

2. H(Δ_{i+1}/Δ_{i}) = H_{Δ_{i}}. Hence, H_{Δ_{i}} ◁ H_{Δ_{i+1}} and the quotient H_{Δ_{i+1}}/H_{Δ_{i}} is cyclic of order p.

We continue with the notation of Lemma 3. In the next lemma we show that the block structure of transitive nilpotent permutation group G is similar to the block structure p-groups.

Lemma 6. Let G be a nilpotent transitive permutation group on Ω and let p be a prime factor of #G. Let Δ be any subset of Σ_{p}^{α}. Then Δ is a G-block if and only if Δ is a G_{p} block (in its transitive action on Σ_{p}^{α}).

Proof. Let H denote the p-Sylow subgroup G_{p}. Let Ĥ denote the product ∏_{q≠p} G_{q} of all other Sylow subgroups of G. Then G = H × Ĥ. Recall that Σ_{p}^{α} is the H-orbit of α.

Firstly any G-block Δ ⊆ Σ_{p}^{α} is an H-block. To prove the converse consider any H-block Σ ⊆ Σ_{p}^{α}. Consider the group G′ = H_{Σ} × (Ĥ ∩ G_{α}). Firstly notice that the group G′ is a subgroup of G_{Σ_{p}^{α}}. Also since G_{α} is nilpotent, we have G_{α} = H_{α} × (Ĥ ∩ G_{α}). Furthermore since Σ is a H-block, we have H_{Σ} ≥ H_{α}. Therefore G′ ≥ G_{α} and by the Galois correspondence of blocks (Theorem 5), Σ = α^{G′} is a G-block and G_{Σ} = G′.

We give a characterisation of nilpotent transitive permutation groups by properties of maximal chains of G-blocks between {α} and Σ_{p}^{α} which is crucial for our polynomial-time nilpotence test. This characterization is probably wellknown to group theorists. However, as we haven’t seen it anywhere, we include a proof.

Theorem 6. Let G ≤ Sym (Ω) be a transitive permutation group satisfying properties (1) and (2) of Lemma 3 (which are necessary conditions for nilpotence of G). Fix an α ∈ Ω. The following statements are equivalent.

(1) G is nilpotent.

(2) For each prime factor p of #G, every maximal chain of G-blocks {α} = Δ_{0} ⊂ … ⊂ Δ_{m} = Σ_{p}^{α} has the property that [Δ_{i+1} : Δ_{i}] = p, G_{Δ_{i}} is a normal subgroup of G_{Δ_{i+1}}, and p does not divide the order of G/G^{Δ_{m}}.

(3) For each prime p dividing #G, there is a maximal chain of G-blocks {α} = Δ_{0} ⊂ … ⊂ Δ_{m} = Σ_{p}^{α} with the property that [Δ_{i+1} : Δ_{i}] = p, G_{Δ_{i}} is a normal subgroup of G_{Δ_{i+1}}, and p does not divide the order of G/G^{Δ_{m}}.

Proof. Clearly (2) implies (3). It suffices to show that (3) implies (1) and (1) implies (2).

To see that (3) implies (1) it is enough to show that each Sylow subgroup of G is normal. To this end, let p be a prime factor of #G and let {α} = Δ_{0} ⊂ … ⊂ Δ_{m} = Σ_{p}^{α} be a maximal chain of G-blocks having the properties mentioned in (3).

Firstly, since G (Δ_{i+1}/Δ_{i}) is the largest normal subgroup of G_{Δ_{i+1}} that is contained in G_{Δ_{i}} (part 1 of Lemma 1), (3) implies that G_{Δ_{i}} = G (Δ_{i+1}/Δ_{i}). Furthermore it follows from Lemma 1 that there is a positive integer l_{i} for each i such that the quotient group G^{Δ_{i+1}}/G^{Δ_{i}} is embeddable in an l_{i}-fold product of copies of \frac{G_{Δ_{i+1}}}{G(Δ_{i+1}/Δ_{i})} = G_{Δ_{i+1}}/G_{Δ_{i}}. Since [G_{Δ_{i+1}} : G_{Δ_{i}}] = p it follows that

G^{Δ_{i+1}}/G^{Δ_{i}} is a p-group for each i. As #G^{Δ_{m}} = ∏_{i=0}^{m−1}[G^{Δ_{i+1}} : G^{Δ_{i}}], G^{Δ_{m}} is also a p-group. Since G^{Δ_{m}} ◁ G and p does not divide [G : G^{Δ_{m}}] it follows that G^{Δ_{m}} is a normal p-Sylow subgroup of G. The nilpotence of G follows as this holds for all prime factors of #G.

Next, we show that (1) implies (2). Suppose G is nilpotent. Let p be a prime factor of #G and α ∈ Ω. Let H be the p-Sylow subgroup G_{p} of G and let Ĥ = ∏_{q≠p} G_{q} be the product of all its other Sylow subgroups. Let {α} = Δ_{0} ⊂ Δ_{1} ⊂ … ⊂ Δ_{m} = Σ_{p}^{α} be any maximal chain of G-blocks between α and Σ_{p}^{α}. It follows from Lemma 6 that the chain {Δ}_{0≤i≤m} is a maximal chain of G_{p}-blocks. By Lemma 5 we have [Δ_{i+1} : Δ_{i}] = p, H_{Δ_{i}} ◁ H_{Δ_{i+1}}, and H_{Δ_{i+1}}/H_{Δ_{i}} is cyclic of order p. The group G_{Δ_{i}} = H_{Δ_{i}} × Ĥ_{Δ_{i}} and G_{Δ_{i+1}} = H_{Δ_{i+1}} × Ĥ_{Δ_{i+1}}. Also since Ĥ_{Δ_{i}} is the product of q-Sylow subgroups of H_{Δ_{i}} where q varies over all prime factors of #G different from p, it follows from Lemma 3 that Ĥ_{Δ_{i}} = Ĥ_{α}. Therefore G_{Δ_{i}} ◁ G_{Δ_{i+1}} and quotient group G_{Δ_{i+1}}/G_{Δ_{i}} ≅ H_{Δ_{i+1}}/H_{Δ_{i}}. The group G/G^{Δ_{m}} acts faithfully on B (Ω/Δ_{m}) and is transitive under this action. Since p ∤ [Ω : Δ_{m}], p cannot divide the order of G/G^{Δ_{m}} (Lemma 3).

The following lemma is crucial for the nilpotence testing algorithm. If G is nilpotent then, for each prime factor p of #G, the lemma implies that no matter how the maximal chain of blocks Δ_{i} of Theorem 6 is constructed, it must terminate in Σ_{p}^{α}.

Lemma 7. Let G be a transitive nilpotent permutation group on Ω. Let p be any prime dividing #G. Let Δ be any G-block such that #Δ = p^{l} for some integer l ≥ 0. Let m be the highest power of p that divides #Ω. If l < m then we have

1. There exists a G-block Σ such that Δ is a maximal G-subblock of Σ and [Σ : Δ] = p.

2. For all G-blocks Σ such that Δ is a maximal G-subblock of Σ and [Σ : Δ] = p, G_{Δ} is a normal subgroup of G_{Σ}.

Proof. Since #Δ is p^{l} it follows that Δ is a G-subblock of Σ_{p}^{α} (Lemma 3). It follows from Lemma 6 that Δ is a G_{p}-block on the transitive action of G_{p} on Σ_{p}^{α}. Furthermore if l < m there is a G_{p}-block Σ (and hence by Lemma 6 a G-block) such that Σ_{p}^{α} ⊇ Σ ⊃ Δ and [Σ : Δ] = p. This proves part 1.

Let α ∈ Δ. It follows from Lemma 3 that for q ≠ p the q-Sylow subgroup of G_{Σ} and G_{Δ} are both G_{q} ∩ G_{α}. Let Ĝ_{p} be ∏_{q≠p} G_{q}. The groups G_{Σ} and G_{Δ} are (G_{p} ∩ G_{Σ}) × (Ĝ_{p} ∩ G_{α}) and (G_{p} ∩ G_{Δ}) × (Ĝ_{p} ∩ G_{α}) respectively. Moreover, G_{p} ∩ G_{Σ} and G_{p} ∩ G_{Δ} are p-groups with index [G_{p} ∩ G_{Σ} : G_{p} ∩ G_{Δ}] = [G_{Σ} : G_{Δ}] = [Σ : Δ] = p. Therefore, G_{p} ∩ G_{Δ} is normal in G_{p} ∩ G_{Σ}. Thus, G_{Δ} = (G_{p}∩G_{Δ})×(Ĝ_{p}∩G_{α}) is normal in G_{Σ} = (G_{p}∩G_{Σ})×(Ĝ_{p}∩G_{α}) and \frac{G_{Σ}}{G_{Δ}} = \frac{G_{p}∩G_{Σ}}{G_{p}∩G_{Δ}} is isomorphic to ℤ_{p}.

3.1 The nilpotence test

Given f(X) ∈ ℚ[X] our goal is to test if Gal (f) is nilpotent. We can assume that f(X) is irreducible. For, otherwise we can compute the irreducible factors of f(X) over ℚ using the LLL algorithm, and perform the nilpotence test on each distinct irreducible factor. This suffices because nilpotent groups are closed under products and subgroups. Let G be Gal (f). We consider G as a subgroup of Sym (Ω), where Ω is the set of roots of f(X). Since f is irreducible, G is transitive on Ω.

For any G-block Δ, let ℚ_{Δ} be the fixed field of the splitting field ℚ_{f} under the automorphisms of G_{Δ}. Let Δ be a G-block containing α. Since G_{Δ} ≥ G_{α}, ℚ_{Δ} is a subfield of ℚ_{{α}} = ℚ(α).

We describe the main idea. By Theorem 6, G is nilpotent if and only if for all primes p that divide the order of G, there is a maximal chain of G-blocks {α} = Δ_{0} ⊂ … ⊂ Δ_{m} satisfying conditions of part (3) of Theorem 6. We show these conditions can be verified in polynomial time once the tower of fields ℚ(α) = ℚ_{Δ_{0}} ⊃ … ⊃ ℚ_{Δ_{m}} are known. Thus, for testing nilpotence of G we will first need a polynomial-time algorithm that computes ℚ_{Δ_{i}}. The following theorem is essentially due to Landau and Miller [4] restated in a form suitable for our application.

Theorem 7. Let f(X) ∈ ℚ[X] be irreducible, G = Gal (f) be its Galois group and Ω be the set of roots of f. Let Δ ⊆ Ω be any G-block and α ∈ Δ. There is an algorithm that given a primitive polynomial μ_{Δ}(X) ∈ ℚ[X] of ℚ_{Δ}, runs in time polynomial in size (f) and size (μ_{Δ}) and computes a primitive polynomial μ_{Σ}(X) ∈ ℚ[X] of ℚ_{Σ} for all G-blocks Σ such that Δ is a maximal block of Σ. Moreover size (μ_{Σ}) is at most a polynomial in size (f) and is independent of size (μ_{Δ}).

We now give the algorithm for testing nilpotence.

Input: A polynomial f(X) ∈ ℚ[X] of degree n

Output: “Accept” if Gal (f) is nilpotent;“Reject” otherwise

Verify that f(X) is solvable; 1 Compute the set P of all the prime factors of #Gal (f);

Let G ≤ Sym (Ω) denote the Galois group of f, where Ω is the set of roots of f. 2 for every p ∈ P do

if p does not divide n then

print Reject end Let m be the highest power of p dividing n.

3 Attempt to compute the tower ℚ_{Δ_{m}} ⊂ … ⊂ ℚ_{Δ_{0}} for a maximal chain of

G-blocks {α} = Δ_{0} ⊂ … ⊂ Δ_{m} such that [ℚ_{Δ_{i+1}} : ℚ_{Δ_{i}}] = p. 4 if Step 3 fails or ℚ_{Δ_{i+1}} is not normal over ℚ_{Δ_{i}} then

print Reject end Let μ_{Δ_{m}}(X) be the primitive polynomial for ℚ_{Δ_{m}}

5 if p divides #Gal (μ_{Δ_{m}}) then

print Reject end

end

print Accept

Algorithm 1: Nilpotence test

We prove that Algorithm 1 runs in polynomial time. For the steps 1 and 5 note that for polynomials f with solvable Galois groups, as a byproduct of the Landau-Miller test [4], the prime factors of #Gal (f) can be found in polynomial time (see also Theorem 11). We explain how step 3 can be done in polynomial time using Theorem 7. We construct ℚ_{Δ_{i}} inductively starting with ℚ_{Δ_{0}} = ℚ(α). Assume we have computed ℚ_{Δ_{i}}. Using Theorem 7 we compute ℚ_{Σ} for each Gblock Σ containing Δ_{i} as a maximal G-subblock. Among them choose a ℚ_{Σ} for which [Σ : Δ_{i}] = p and let ℚ_{Δ_{i+1}} be ℚ_{Σ}. The inductive construction of ℚ_{Δ_{i+1}} from ℚ_{Δ_{i}} can be done in time bounded by a polynomial in size (f). Putting it together we have the following proposition.

Proposition 1. Algorithm 1 runs in time polynomial in size (f).

We now argue its correctness. Part (1) of Theorem 6 implies that if G is nilpotent then Algorithm 1 accepts. Conversely, suppose the algorithm accepts. Then for each prime p dividing #G we have a maximal chain of G-blocks {α} = Δ_{0} ⊂ … ⊂ Δ_{m} such that ℚ_{Δ_{i}}/ℚ_{Δ_{i+1}} are normal extensions for each 0 ≤ i < m (this we verify in step 4 of Algorithm 1). Recall that ℚ_{Δ_{i}} is the fixed field of ℚ_{f} w.r.t. G_{Δ_{i}}. Hence by checking ℚ_{Δ_{i}}/ℚ_{Δ_{i+1}} is a normal extension we have verified that G_{Δ_{i}} ◁ G_{Δ_{i+1}}. Also, the splitting field of the primitive polynomial μ_{Δ_{m}}(X) is the normal closure of ℚ_{Δ_{m}} over ℚ. It follows from Lemma 1 and Theorem 1 that Gal (μ_{Δ_{m}}) is G^{Δ_{m}}. Hence, by checking p does not divide #Gal (μ_{Δ}) we have verified that p does not divide #G/G^{Δ_{m}}. Thus, we have verified that the maximal chain of G-blocks {α} = Δ_{0} ⊂ … ⊂ Δ_{m} satisfies the conditions of Part(3) of Theorem 6 implying that G is nilpotent. Putting it all together we have the following theorem.

Theorem 8. There is a polynomial-time algorithm that takes f ∈ ℚ[X] as input and tests if Gal (f) is nilpotent.

4 Generalizing the Landau-Miller solvability test

In this section we show that the Landau-Miller solvability test can be adapted to test if the Galois group of f(X) ∈ ℚ[X] is in Γ_{d} for constant d. Note that for d < 5, Γ_{d} is the class of solvable groups and hence our result is a generalization of the result of Landau-Miller [4]. We first recall a well-known bound on the size of primitive permutation groups in Γ_{d}.

Theorem 9 ([1]). Let G ≤ S_{n} be a primitive permutation group in Γ_{d} for a constant d. Then #G ≤ n^{O(d)}.

Theorem 10. For constant d > 0, there is an algorithm that takes as input f(X) ∈ ℚ[X] and in time polynomial in size (f) and n^{O(d)} decides whether Gal (f) is in Γ_{d}.

Proof. We sketch the proof. Assume without loss of generality that f(X) is irreducible. Let G = Gal (f) as a subgroup of Sym (Ω), where Ω is the set of roots of f. Let {α} = Δ_{0} ⊂ … ⊂ Δ_{t} = Ω be any maximal chain of G-blocks. The series {1} = G^{Δ_{0}} ◁ … ◁ G^{Δ_{t}} = G gives a normal series for G. By closure properties of Γ_{d}, G ∈ Γ_{d} iff \frac{G^{Δ_{i+1}}}{G^{Δ_{i}}} ∈ Γ_{d} for each i. If G is in Γ_{d} so are G_{Δ_{i+1}}

and G (Δ_{i+1}/Δ_{i}) and hence their quotient \frac{G_{Δ_{i+1}}}{G(Δ_{i+1}/Δ_{i})}. On the other hand since

\frac{G^{Δ_{i+1}}}{G^{Δ_{i}}} is isomorphic to a subgroup of (\frac{G_{Δ_{i+1}}}{G(Δ_{i+1}/Δ_{i})})^{l} for some l (Lemma 1), \frac{G^{Δ_{i+1}}}{G^{Δ_{i}}} ∈ Γ_{d} if \frac{G_{Δ_{i+1}}}{G(Δ_{i+1}/Δ_{i})} ∈ Γ_{d}. Hence G ∈ Γ_{d} iff \frac{G_{Δ_{i+1}}}{G(Δ_{i+1}/Δ_{i})} is in Γ_{d} for each i . We give a polynomial-time algorithm to verify the above fact for some maximal chain of G-blocks {α} = Δ_{0} ⊂ … ⊂ Δ_{t} = Ω.

First, by Theorem 7we compute K_{i} = ℚ_{Δ_{i}} for a maximal chain of G-blocks {α} = Δ_{0} ⊂ … ⊂ Δ_{t} = Ω. Let L_{i} be the fixed field of ℚ_{f} with respect to the automorphisms of G (Δ_{i+1}/Δ_{i}) then L_{i+1} is the normal closure of K_{i} over K_{i+1}. This follows because G (Δ_{i+1}/Δ_{i}) is the largest proper normal subgroup of G_{Δ_{i+1}} = Gal (ℚ_{f}/ℚ_{Δ_{i+1}}). Hence Gal (L_{i+1}/K_{i+1}) is \frac{G_{Δ_{i+1}}}{G(Δ_{i+1}/Δ_{i})}, and it suffices to check that each Gal (L_{i}/K_{i}) is in Γ_{d}.

The group \frac{G_{Δ_{i+1}}}{G(Δ_{i+1}/Δ_{i})} acts faithfully and primitively on Ω′ = B (Δ_{i+1}/Δ_{i}), by Lemma 1 and since Δ_{i} is a maximal subblock of Δ_{i+1}. If G ∈ Γ_{d} then [L_{i+1} : K_{i+1}] = #Gal (L_{i+1}/K_{i+1}) ≤ n^{O(d)} and degrees [L_{i} : ℚ] are all less than n^{O(d)}. We can use Theorem 2 to compute Gal (L_{i}/K_{i}) as a multiplication table in time polynomial in size (f) and n^{d} for each i. We then verify that Gal (L_{i}/K_{i}) ∈ Γ_{d} by computing a composition series for it and checking that each composition factor is in Γ_{d}. At any stage in the computation of Gal (L_{i}/K_{i}) if the sizes of the fields becomes too large, i.e. larger than the bound of Theorem 9 we abort the computation and decide that Gal (f) is not in Γ_{d}. Clearly, these steps can be done in polynomial time.

It follows from the proof of Theorem 10 that a prime p divides #Gal (f) if and only if it divides [L_{i} : K_{i}] for some 1 ≤ i ≤ t.

Theorem 11. Given f(X) ∈ ℚ[X] with Galois group in Γ_{d} there is an algorithm running in time polynomial in size (f) and n^{d} that computes all the prime factors of #Gal (f).

References

1. Lázló Babai, Peter J. Cameron, and P. P. Pálfy. On the order of primitive groups with restricted nonabelian composition factors. Journal of Algebra, 79:161–168, 1982.

2. Pilar Fernandez-Ferreiros and M. Angeles Gomez-Molleda. Deciding the nilpotency of the Galois group by computing elements in the centre. Mathematics of Computation, 73(248), 2003.

3. Susan Landau. Polynomial time algorithms for Galois groups. In John Fitch, editor, EUROSAM 84 Proceedings of International Symposium on Symbolic and Algebraic Computation, volume 174 of Lecture Notes in Computer Sciences, pages 225–236. Springer, July 1984.

4. Susan Landau and Gary. L. Miller. Solvability by radicals is in polynomial time. Journal of Computer and System Sciences, 30:179–208, 1985.

5. Serge Lang. Algebra. Addison-Wesley Publishing Company, Inc, third edition, 1999.

6. Hendrik W. Lenstra Jr. Algorithms in algebraic number theory. Bulletin of the American Mathematical Society, 26(2):211–244, April 1992.

7. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25(1):42–65, 1982.

8. Eugene M. Luks. Permutation groups and polynomial time computations. DI-MACS Series in Discrete Mathematics and Theoretical Computer Science, 11:139– 175, 1993.

9. Helmut Wielandt. Finite Permutation Groups. Academic Press, New York, 1964.