Upper Bounds on the Complexity of some Galois Theory Problems

V. Arvind and Piyush P Kurur Institute of Mathematical Sciences, C.I.T Campus, Chennai 600113, India

                {arvind,ppk}@imsc.res.in

April 4, 2011

Abstract Assuming the generalized Riemann hypothesis, we prove the following complexity bounds: The order of the Galois group of an arbitrary polynomial f(x) ∈ ℤ[x] can be computed in P#P. Furthermore, the order can be approximated by a randomized polynomial-time algorithm with access to an NP oracle. For polynomials f with solvable Galois group we show that the order can be computed exactly by a randomized polynomial-time algorithm with access to an NP oracle. For all polynomials f with abelian Galois group we show that a generator set for the Galois group can be computed in randomized polynomial time.

1 Introduction

A fundamental problem in computational algebraic number theory is to determine the Galois group of a polynomial f(x) ∈ ℚ[x]. Formally, in this paper we study the computational complexity of the following problem:

Problem 1.1. Given a nonzero polynomial f(x) over the rationals ℚ,

(a) determine the Galois group of f over ℚ.

(b) determine the order of the Galois group of f over ℚ.

An extension of a field K is a field L that contains K (written L/K). If L/K is a field extension then L is a vector space over K and its dimension, denoted by [L : K] is called its degree. If [L : K] is finite then L/K is a finite extension. If L/M and M/K are finite extensions then [L : K] = [L : M].[M : K].

Let K[x] denotes the ring of polynomials with indeterminate x and coefficients from the field K. A polynomial f(x) ∈ K[x] is irreducible if it has no nontrivial factor over K. The splitting field K_{f} of a polynomial f(x) ∈ K[x] is the smallest extension L of K such that f factorizes into linear factors in L.

An extension L/K is normal if for any irreducible polynomial f(x) ∈ K[x], f either splits in L or has no root in L. 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 called a Galois extension.

An automorphism of a field L is a field isomorphism σ : L → L. The Galois group Gal (L/K) of a field extension L/K is the subgroup of the group of automorphisms of L that leaves K fixed: i.e. for every σ ∈ Gal (L/K), σ(a) = a for all a ∈ K. By the Galois group of a polynomial f ∈ K[x] we mean Gal (K_{f}/K).

Roots of polynomials over ℚ are algebraic numbers. The minimal polynomial T ∈ ℚ[x] of an algebraic number α is the unique monic polynomial of least degree with α as a root. Algebraic integers are roots of monic polynomials in ℤ[x]. A number field is a finite extension of ℚ. For an algebraic number α, ℚ(α) denotes the smallest number field that contains α. If f(x) is the minimal polynomial of α then ℚ(α) can be identified with the quotient ℚ[x]/(f(x)ℚ[x]). Every number field K has an element α such that K = ℚ(α) (see [7, Theorem 4.6 Chap.V]). Such elements are called primitive elements of the field K.

Let f ∈ ℚ[x] with roots α_{1}, α_{2}, …, α_{n} ∈ ℚ_{f}. A well known lemma [14] states that ℚ_{f} has a primitive element of the form ∑_{i=1}^{n} c_{i}α_{i} for integers c_{i}. The proof actually yields a probabilistic version which states that ∑_{i=1}^{n} c_{i}α_{i} is primitive for most c_{i}.

Lemma 1.2. Let f ∈ ℚ[x] be a degree n polynomial with roots α_{1}, α_{2}, …, α_{n}. For a random choice of integers c_{1}, c_{2}, …, c_{n} such that size(c_{i}) ≤ n^{2} the algebraic integer θ = ∑_{i=1}^{n} c_{i}α_{i} is such that L = ℚ(θ) with probability 1 − \frac{1}{2^{O(n^{2})}} .

A polynomial f(x) ∈ ℚ[x] is said to be solvable by radicals if the roots of f can be expressed, starting with the coefficients of f, using only field operations and taking r^{th} roots for integer r. Galois showed that a polynomial is solvable by radicals if and only if its Galois group is solvable.

Let L be a number field and O_{L} be the ring of algebraic integers in L. We can write O_{L} as O_{L} = {∑_{i=1}^{N} a_{i}ω_{i} | a_{i} ∈ ℤ} where ω_{1}, ω_{2}, …, ω_{N} is its ℤbasis. The discriminant d_{L} of the field L is defined as the determinant of the matrix (Tr(ω_{i}ω_{j}))_{i,j} where Tr : L → ℚ is the trace map. The discriminant d_{L} is always a nonzero integer. Let T be any polynomial of degree N. Then the discriminant d(T) of the polynomial T is defined as d(T) = ∏_{i≠j}(θ_{i} − θ_{j}), where θ_{1}, θ_{2}, …, θ_{N} are the N distinct roots of T (i.e. all the conjugates of θ). The following is important property that relates d(T) and d_{L} ([2, Proposition 4.4.4]).

Proposition 1.3. Let L be a number field and T be the minimal polynomial of a primitive element θ of L. Then d_{L} | d(T). More precisely, d(T) = d_{L} · t^{2}, for an integer t.

Let size(a) denote the length of the binary encoding of an integer a. For a rational r = p/q such that gcd(p, q) = 1, let size(r) = size(p) + size(q). A polynomial is encoded as a list of its coefficients. For a polynomial f(x) = ∑ a_{i}x^{i} ∈ ℚ[x] we define size(f) = ∑ size(a_{i}). Thus, for an algorithm taking a polynomial f as input, the input size is size(f).

For any polynomial g(x) = a_{0} + a_{1}x + … + a_{n}x^{n} in ℤ[x], let |g|_{2} = \sqrt{∑ a_{i}^{2}}. Applying an inequality [4] which bounds every root η of g by |g|_{2}, we obtain the following.

Theorem 1.4. Let f(x) ∈ ℤ[x] be a monic polynomial of degree n with splitting field L. Let α_{1}, α_{2}, …, α_{n} be the roots of f. Consider an element of the form θ = ∑ c_{i}α_{i}, c_{i} ∈ ℤ, and let T be the minimal polynomial of θ. Then |d(T)| ≤ (2c|f|_{2})^{N^{2}}, where c = max{|c_{i}| : 1 ≤ i ≤ n}. As a consequence, d_{L} ≤ (2^{n^{2}}|f|_{2})^{n!^{2}} and log d_{L} ≤ (n + 1)!^{2}.size(f).

The Galois group of a polynomial f(x) ∈ K[x] is completely determined by its action on the roots of f in K_{f}. We assume w.l.o.g throughout this paper that f is square-free. Otherwise, we can replace f by f/gcd(f.f′) which is square-free with the same Galois group. Thus, if we label the n distinct zeroes of f, we can consider the Galois group as a subgroup of the symmetric group S_{n}. Notice that this subgroup is determined only up to conjugacy (as the labeling of the zeroes of f is arbitrary). Since every subgroup of S_{n} has a generator set of size n − 1 (c.f. [12] and [9]), we can specify the Galois group in size polynomial in n. By computing the Galois group of a polynomial f we mean finding a small generator set (polynomial in n) for it as a subgroup of S_{n}.

We now state Landau’s result on computing the Galois group of a polynomial f. Its worst case running time is exponential in size(f).

Theorem 1.5 ([5]). Given a polynomial f ∈ F [x], where the number field F is given as a vector space over ℚ, the Galois group G of f over F can be computed in time polynomial in |G| and size(f).

The extended abstract is organized as follows: In Sect. 2 we explain the Chebotarev density theorem in a form that is useful to us. In Sect. 3 we give a polynomial time algorithm making a single query to #P to compute the order of the Galois group of a polynomial f(x) ∈ ℚ. In Sect. 4 we show that if the polynomial is solvable by radicals the order of its Galois group can be computed by a randomized algorithm with an NP oracle. Finally in Sect. 5 we show that if the Galois group of f is abelian then it can be computed by a randomized polynomial time algorithm. For the definitions of various complexity classes the reader can consult any complexity theory text like [1].

2 Chebotarev Density theorem

The main tool in the proofs of our complexity results is the Chebotarev density theorem. In this section we explain the theorem statement and also state it in a form that is suitable for our applications.

Let L be a Galois number field and O_{L} be the ring of algebraic integers in L. Let n = [L : ℚ] be the degree of L. For any prime p ∈ ℚ consider the principal ideal pO_{L} generated by p (which we denote by p). The ideal p factorizes in O_{L} as p = 𝔭_{1}^{e}𝔭_{2}^{e} … 𝔭_{g}^{e} for some positive integer e. For each i, O_{L}/𝔭_{i} is a finite field extension of 𝔽_{p} with p^{f} elements for some positive integer f. Furthermore efg = n.

The prime p is said to be ramified in L if e > 1 and unramified otherwise. It is a basic fact about number fields that a prime p is ramified in L if and only if p divides the discriminant of L (see [11, Theorem 1, pg. 238]).

Let p be an unramified prime with factorization p = 𝔭_{1}𝔭_{2} … 𝔭_{g} in O_{L}. Corresponding to the Frobenius automorphism of the finite field O_{L}/𝔭_{i}, there is an

element denoted ( \frac{L/ℚ}{𝔭_{i}} ) in the Galois group G = Gal (L/ℚ) known as the

Frobenius element of 𝔭_{i}, for i = 1, 2, …, g. Furthermore, it is known that the set

[ \frac{L/ℚ}{p} ] = \{( \frac{L/ℚ}{𝔭} ) : 𝔭|p\}

is a conjugacy class in the Galois group G. For any conjugacy class C of G let

π_{C}(x) be the number of unramified primes less that x such that [ \frac{L/ℚ}{p} ] = C.

We have the following theorem:

Theorem 2.1 (Chebotarev’s density theorem). Let L/ℚ be a Galois extension and G = Gal (L/ℚ) be its Galois group. Then for every conjugacy class C of G, π_{C}(x) converges to \frac{|C|}{|G|}.\frac{x}{ln x} as x → ∞.

In order to apply the above theorem in a complexity-theoretic context, we need the following effective version due to Lagarias and Odlyzko [3] proved assuming the GRH.

Theorem 2.2. Let L/ℚ be a Galois extension and G = Gal (L/ℚ) be its Galois group. If the GRH is true then there is an absolute constant x_{0} such that for all x > x_{0}:

|π_{C}(x) − \frac{|C|}{|G|} \frac{x}{ln x}| ≤ \frac{|C|}{|G|}x^{1/2} ln d_{L} + x^{1/2} ln x.|G|.

An unramified prime p such that [ \frac{L/ℚ}{p} ] = \{1\} is called a split prime. By

definition, π_{1}(x) denotes the number of split primes p ≤ x.

Corollary 2.3. Let G = Gal (L/ℚ) for a Galois extension L/ℚ. If the GRH is true then there is an absolute constant x_{0} such that for all x > x_{0}:

|π_{1}(x) − \frac{1}{|G|} \frac{x}{ln x}| ≤ \frac{1}{|G|}x^{1/2} ln d_{L} + x^{1/2} ln x.|G|.

3 Computing the order of Galois Groups

Let f(x) ∈ ℤ[x] be a monic polynomial of degree n without multiple roots and let L denote the splitting field of f. Suppose {α_{1}, α_{2}, …, α_{n}} is the set of roots of f.

As mentioned before, the Galois group G = Gal (L/ℚ) can be seen as a subgroup of S_{n}. Each σ ∈ G, when considered as a permutation in S_{n}, can be expressed as a product of disjoint cycles. Looking at the lengths of these cycles we get the cycle pattern ⟨m_{1}, m_{2}, …, m_{n}⟩ of σ, where m_{i} is the number of cycles of length i, 1 ≤ i ≤ n. We have n = ∑_{i=1}^{n} m_{i}.

If p is a prime such that p ∤ d(f), we can factorize f = g_{1}g_{2} … g_{s} into its distinct irreducible factors g_{i} over 𝔽_{p}. Looking at the degrees of these irreducible factors we get the decomposition pattern ⟨m_{1}, m_{2}, …, m_{n}⟩ of f(mod p), where m_{i} is the number of irreducible factors of degree i.

We now state an interesting fact from Galois theory (see [14, page 198] and [7, Theorem 2.9, Chap. VII]).

Theorem 3.1. Let f(x) ∈ ℤ[x] be a monic polynomial of degree n such that d(f) ≠ 0, and let L denote its splitting field. Let G = Gal (L/ℚ). Let p be a prime such that p ∤ d(f). Then there is a conjugacy class C of G such that for each σ ∈ C the cycle pattern of σ is the same as the decomposition pattern of f factorized over 𝔽_{p}. Furthermore, if {α_{1}, α_{2}, …, α_{n}} are the n roots of f in its splitting field and if 𝔽_{p^{m}} is the extension of 𝔽_{p} where f (mod p) splits then there is an ordering of the roots {α′_{1}, α′_{2}, …, α′_{n}} of f in 𝔽_{p^{m}} such that for all indices k and l, σ(α_{k}) = α_{l} if and only if the Frobenius automorphism x ↦ x^{p} of 𝔽_{p^{m}} maps α′_{k} to α′_{l}.

For any prime p that divides the order of the Galois group there is an element whose order is divisible by p. This can happen only if there is a prime q such that the decomposition pattern of f (mod q) contains only the integers p and 1 (using Theorem 3.1). Furthermore using the effective Chebotarev density theorem (Theorem 2.2) we can show that there is a q with size size(f)^{O(1)} satisfying the above property. So to check whether p divides the order of the Galois group we guess such a q. This leads to the following theorem.

Theorem 3.2. Assuming GRH, the following problem is in NP: Given a prime p ≤ n, and a monic polynomial f ∈ ℤ[x] with d(f) ≠ 0 as input, test if p divides the order of the Galois group of f. As a consequence, the set of prime factors of |Gal (ℚ_{f}/ℚ) | can be computed in PNP.

Now for the main result of this section.

Theorem 3.3. Assuming GRH, the order of the Galois group of a monic polynomial f ∈ ℤ[x] can be computed in P#P.

The algorithm first count the number of split primes (with a certain exponentially small error) less than a suitably large x (size(x) = size(f)^{O(1)}) using a single #P query. The order of the Galois group is the nearest integer to \frac{1}{π_{1}(x)} \frac{x}{ln x} which can be computed in polynomial time.

To the best of our knowledge, this is the first polynomial-space bounded algorithm for the problem. Next we consider the approximate counting problem.

Definition 3.4. A randomized algorithm A is an r-approximation algorithm for a #P function f with error probability δ < \frac{1}{2} if for all x ∈ \{0, 1\}^{∗}:

P rob_{y} [|1 − \frac{A(x, y)}{f(x)}| ≤ r(|x|)] ≥ 1 − δ,

where y is a uniformly chosen random string used by the algorithm A on input x.

Stockmeyer [13] showed that for any #P function there is a n^{−O(1)}-approximation BPPNP algorithm. We can use Stockmeyer’s result to approximate π_{1}(x) within an inverse polynomial error and use this approximation instead. This yields the algorithm in the following theorem.

Theorem 3.5. Let f(x) ∈ ℤ[x] be a degree n polynomial, G be its Galois group, and s denote size(f). For any constant c > 0 there is a BPPNP algorithm that computes an approximation A of |G| such that

(1 − \frac{1}{s^{c}} ) A ≤ |G| ≤ (1 + \frac{1}{s^{c}} ) A.

with probability greater than \frac{2}{3}.

We now derive a useful lemma as an immediate consequence of the above result.

Lemma 3.6. Let f and g be monic polynomials in ℤ[x] with nonzero discriminant. Suppose the splitting field ℚ_{g} of g is contained in ℚ_{f} of f and [ℚ_{f} : ℚ_{g}] is a prime power p^{l}. There is a BPPNP algorithm that computes [ℚ_{f} : ℚ_{g}] exactly, assuming that |Gal (ℚ_{g}/ℚ) | is already computed.

4 Computing the order of solvable Galois Groups

In this section we show that if the Galois group G of f ∈ ℤ[x] is solvable then |G| can be computed exactly in BPPNP, assuming GRH. In fact, we show that for solvable Galois groups, finding |G| is polynomial-time reducible to approximating |G|.

To begin with we need a test for solvability by radicals. A naive application of Galois’ theorem gives an exponential time algorithm (using Theorem. 1.5). An important breakthrough was achieved by Landau and Miller when they gave a deterministic polynomial time algorithm to check whether a polynomial is solvable by radicals without actually computing the Galois group (see. [6]). We make use of results from [6]. We begin by recalling some definitions.

A group G is said to be solvable if there is a composition series of G, G = G_{0} ▷ G_{1} ▷ … ▷ G_{t} = 1 such that G_{i}/G_{i+1} is a cyclic group of prime order. Throughout this section by composition series we mean such a composition series.

A Galois extension K/F is said to be solvable if Gal (K/F) is a solvable group. Let G = G_{0} ▷ G_{1} ▷ … ▷ G_{t} = 1 be a composition series of G. There is a corresponding tower of fields F = E_{0} ⊆ E_{1} ⊆ … ⊆ E_{t} = K such that Gal (K/E_{i}) = G_{i}. Moreover if K/F is Galois then by the fundamental theorem of Galois, since G_{i} ▷ G_{i+1}, the extension E_{i+1}/E_{i} is Galois.

At this point we recall some permutation group theory (c.f. [15]): Let G be a subgroup of S_{n} acting on a set Ω = {1, 2, …, n} of n elements. G is said to be transitive if for every pair of distinct elements i, j ∈ Ω, there is a σ ∈ G such that σ maps i to j, written as i^{σ} = j. A block is a subset B ⊆ Ω such that for every σ ∈ G either B^{σ} = B or B^{σ} ∩ B = ∅. If G is transitive then under G-action blocks are mapped to blocks, so that starting with a block B_{1} ⊆ Ω we get a complete block system {B_{1}, B_{2}, …, B_{s}} which is a partition of Ω. Notice that singleton sets and Ω are blocks for any permutation group. These are the trivial blocks. A transitive group G is primitive if it has only trivial blocks. Otherwise it is called imprimitive. A minimal block of an imprimitive group is a nontrivial block of least cardinality. The corresponding block system is a minimal block system.

The following result about solvable primitive permutation groups [10] has been used to show polynomial time bounds for several permutation group algorithms [9].

Theorem 4.1 (Pálfy’s bound). [10] If G < S_{n} is a solvable primitive group then |G| ≤ n^{3.25}.

Let f(x) ∈ ℤ[x] be a monic irreducible polynomial and let G be the Galois group Gal (ℚ_{f}/ℚ) which acts transitively on the set of roots Ω = {α_{1}, α_{2}, …, α_{n}} of f. Let {B_{1}, B_{2}, …, B_{s}} be the minimal block system of Ω under the action of G and H be the subgroup of G that setwise stabilizes all the blocks: i.e. elements of H map B_{i} to B_{i} for each i. Let B_{1} = {α_{1}, α_{2}, …, α_{k}}, where k = n/s. Consider the polynomial p(x) = ∏_{i=1}^{k}(x − α_{i}) = ∑_{i=0}^{k} δ_{i}x^{i}.

In [6] it is shown that p(x) ∈ ℚ(α_{1})[x] and there is a polynomial time deterministic algorithm to find p(x): the algorithm computes each coefficient δ_{i} as a polynomial p_{i}(α_{1}) with rational coefficients. In polynomial time we can compute a primitive element β_{1} of ℚ(δ_{0}, δ_{1}, …, δ_{k}) [6] so that ℚ(β_{1}) = ℚ(δ_{0}, δ_{1}, …, δ_{k}). Let g(x) ∈ ℤ[x] be the minimal polynomial of β_{1}. In the following theorem we recall some results from [6], suitably rephrased.

Theorem 4.2.

1. The degree of g(x) is s.

2. H = Gal (ℚ_{f}/ℚ_{g}) and Gal (ℚ_{g}/ℚ) = G/H.

3. The Galois group Gal (ℚ(B_{1})/ℚ(β_{1})) acts primitively on B_{1}.

Let Gal (ℚ(B_{1})/ℚ(β)) = G^{B_{1}} = G_{0} ▷ G_{1} ▷ … ▷ G_{t} = 1 be a composition series of the solvable group G^{B_{1}} and let ℚ(β_{1}) = K_{0} ⊆ K_{1} ⊆ … ⊆ K_{t} = ℚ(B_{1}) be the corresponding tower of subfields of the extension ℚ(B_{1})/ℚ(β_{1}). Since K_{i+1}/K_{i} is an extension of prime degree for each i we have the following proposition.

Proposition 4.3. For all 0 ≤ i < t if K′ be any field such that K_{i} ⊆ K′ ⊆ K_{i+1} then either K′ = K_{i} or K′ = K_{i+1}.

For each field K_{j} in the above tower, let θ_{j} be a primitive element, 0 ≤ j ≤ t. I.e. ℚ(θ_{j}) = K_{j} for each j. Let h_{j}(x) ∈ K_{j−1}[x] be the minimal polynomial of θ_{j} over K_{j−1}. We can consider h_{j}(x) as h_{j}(x, θ_{j−1}), a polynomial over ℚ in the indeterminate x and the algebraic number θ_{j−1} as parameter. As before let G = ∪_{i=1}^{s}Hσ_{i}. For each field K_{j} let K_{ij} be the conjugate field under the action of σ_{i}. More precisely, let K_{ij} = K_{j}^{σ_{i}} and θ_{ij} = θ_{j}^{σ_{i}}. We have the following proposition which follows from the fact that σ_{i} is a field isomorphism which maps the extension ℚ(B_{1})/ℚ(β_{1}) to ℚ(B_{i})/ℚ(β_{i}), for each i.

Proposition 4.4.

1. K_{i0} ⊆ K_{i1} ⊆ … ⊆ K_{it} forms a tower of fields of the extension ℚ(B_{i})/ℚ(β_{i}) corresponding to the composition series of Gal (ℚ(B_{i})/ℚ(β_{i})).

2. Gal (K_{it}/K_{ij}) = σ_{i}^{−1}G_{j}σ_{i}.

3. K_{ij} = ℚ(θ_{ij}), where θ_{ij} = θ_{j}^{σ_{i}}.

4. The minimal polynomial of θ_{ij} over the field K_{ij−1} is h_{ij}(x) = h_{j}(x, θ_{ij−1}).

For each i, let \overline{h}_{i}(x) denote the minimal polynomial of θ_{i} over ℚ and let n_{i} be its degree. We have the following lemma:

Lemma 4.5. Let n_{i} = deg(\overline{h}_{i}) then n_{0} = [ℚ(β_{1}) : ℚ] and n_{i} = p_{i}n_{i−1}, where [K_{i} : K_{i−1}] = p_{i} for each i.

Let E_{i} = ℚ_{\overline{h}_{i}}, 0 ≤ i ≤ t. Notice that ℚ_{f} = E_{t} and ℚ_{g} = E_{0}. We have the following theorem:

Theorem 4.6. Let p_{i} be the order of G_{i}/G_{i−1}. For every i there is a l_{i} such that Gal (E_{i}/E_{i−1}) is an abelian group of order p_{i}^{l_{i}}. Furthermore Gal (E_{i}/E_{i−1}) is an elementary abelian p_{i}-group.

Suppose we know [ℚ_{g} : ℚ]. Using Lemma 3.6 we can compute [ℚ_{f} : ℚ] by finding [E_{i} : ℚ] for each 1 ≤ i ≤ t starting from i = 1. We will find [ℚ_{g} : ℚ] recursively. It is also easy to generalize this algorithm for reducible polynomials f(x) ∈ ℚ[x]. This gives the following theorem:

Theorem 4.7. Assuming the GRH, there is a BPPNP procedure that takes as input a monic polynomial f ∈ ℤ[x] such that d(f) ≠ 0, and computes |Gal (ℚ_{f}/ℚ) | exactly when Gal (ℚ_{f}/ℚ) is solvable.

5 Finding the Galois group of an abelian extension

Let f be a polynomial over ℤ[x] such that Gal (ℚ_{f}/ℚ) is abelian. In this section we give a polynomial-time randomized algorithm that computes the Galois group (as a set of generators) with constant success probability.

Suppose f ∈ ℤ[x] is irreducible of degree n with Galois group G. Since G is a transitive subgroup of S_{n}, if G is abelian then |G| = n. Thus, given an irreducible f ∈ ℤ[x], the algorithm of Theorem 1.5 gives a (size(f))^{O(1)} algorithm for testing if its Galois group is abelian, and if so, finding the group explicitly. On the other hand, when f is reducible with abelian Galois group, no polynomial time algorithm is known for computing the Galois group (c.f. Lenstra [8]). However, for any polynomial f testing if its Galois group is abelian can be done in polynomial time: we only need to test if the Galois group of each irreducible factors of f is abelian.

Let f be a polynomial over ℤ[x] such that Gal (ℚ_{f}/ℚ) is abelian. Let f = f_{1}f_{2} … f_{t} be its factorization into irreducible factors f_{i}. Notice that if Gal (ℚ_{f}/ℚ) is abelian then Gal (ℚ_{f_{i}}/ℚ) is abelian for each i. Consequently, each f_{i} is a primitive polynomial. Let G = Gal (ℚ_{f}/ℚ) and let G_{i} = Gal (ℚ_{f_{i}}/ℚ) for each i. Notice that G ≤ G_{1} × G_{2} × … G_{t}.

Let n_{i} be the degree of f_{i}. Since each f_{i} is a primitive polynomial, |G_{i}| = n_{i}. Let θ_{i} be any root of f_{i}, 1 ≤ i ≤ t. Then, ℚ_{f_{i}} = ℚ(θ_{i}) for each i. Factorizing f_{i} in ℚ(θ_{i}), we can express the other roots of f_{i} as A_{ij}(θ_{i}), where A_{ij}(x) are all polynomials of degree at most n_{i}, 1 ≤ j ≤ n_{i}. We can efficiently find these polynomials A_{ij}(x) for 1 ≤ i ≤ t, 1 ≤ j ≤ n_{i}. Thus we can write f_{i}(x) = ∏_{j=1}^{n_{i}} (x − A_{ij}(θ_{i})), where θ_{i} is one of the roots of f_{i}. We have the following lemma:

Lemma 5.1. Let θ be any root of f_{i} and let A_{ij} be polynomials of degree less than deg(f_{i}) such that f_{i}(x) = ∏_{j=1}^{n_{i}}(x − A_{ij}(θ)). Then for 1 ≤ j < deg(f_{i}), we have A_{ij}(A_{ik}(θ)) = A_{ik}(A_{ij}(θ)). Furthermore, for every σ ∈ G_{i} there is an index k, 1 ≤ k ≤ n_{i} such that for any root η of f_{i}(x) we have σ(η) = A_{ik}(η).

From the above lemma it also follows that for each i, 1 ≤ i ≤ t, the polynomials A_{ij}, 1 ≤ j ≤ n_{i} are independent of the choice of the root θ of f_{i} because the Galois group is abelian.

Now, let σ_{ij} denote the unique automorphism of ℚ_{f_{i}} that maps θ to A_{ij}(θ) for every root θ of f_{i}. Since G ≤ G_{1} × G_{2} × … × G_{t}, any element σ ∈ G is a t-tuple σ = ⟨σ_{1j_{1}}, σ_{2j_{2}}, …, σ_{tj_{t}}⟩, for indices j_{1}, j_{2}, …, j_{t}. We will apply the Chebotarev density theorem to determine a generator set for G.

Let q be a prime such that q ∤ d(f) and 𝔽_{q^{m}} be the extension of 𝔽_{q} where f splits. Observe that since G is abelian every conjugacy class of G is a singleton set. Let π_{g}(x) denote the number of primes p ≤ x whose Frobenius corresponds to g. By Theorem 2.1 π_{g}(x) converges to \frac{x}{(ln x)|G|}. Furthermore using Theorem 2.2 we can show that for a random prime p ≤ x, the probability that the Frobenius corresponding to p is g lies in the range (\frac{1}{|G|} − ϵ, \frac{1}{|G|} + ϵ), ϵ = \frac{1}{x^{O(1)}} .

Next, fix i and let {α_{1}, α_{2}, …, α_{n_{i}}} be the roots of f_{i}. By Theorem 3.1, there is an ordering \{\overline{α}_{1}, \overline{α}_{2}, …, \overline{α}_{n_{i}}\} of the roots of f_{i} in 𝔽_{q^{m}} such that the Frobenius automorphism x ↦ x^{q} maps \overline{α}_{k} to \overline{α}_{l} if and only if the element g (the unique Frobenius element corresponding to q) maps α_{k} to α_{l}. If the element g = ⟨σ_{1j_{1}}, σ_{2j_{2}}, …, σ_{tj_{t}}⟩ we can determine σ_{ij_{i}} as follows: find the splitting field 𝔽_{q^{k}} of f_{i}. Since f_{i} is a primitive polynomial, k ≤ n_{i}, thus 𝔽_{q^{k}} can be found efficiently.^{1} Now, factorize f_{i} in 𝔽_{q^{k}}. Pick any root \overline{θ} ∈ 𝔽_{q^{k}} of f_{i}. Then \overline{θ}^{q} = A_{ij}(\overline{θ}) for exactly one polynomial A_{ij_{i}}, which can be found by trying all of them. This gives us σ_{ij_{i}}. Thus, we can determine g as a t-tuple in polynomial time, in a manner independent of the choice of the root \overline{θ} of f_{i} in 𝔽_{q^{k}}.

We have the following almost uniform polynomial-time sampling algorithm from the Galois group G: Pick primes p ∤ d(f) less that a suitably large x and recover corresponding Frobenius. It can be shown that if we choose x ≥ (n!)^{10}.size(f)^{2}, the algorithm samples g ∈ G with probability in the range (\frac{1}{|G|} − \frac{1}{x^{1/4}} , \frac{1}{|G|} + \frac{1}{x^{1/4}} ). We require the following lemma to complete the proof

Lemma 5.2. Suppose we have a (almost) uniform sampling procedure A from a subgroup G of S_{n}. Then for every constant c > 0, there is a polynomial-time randomized algorithm with A as subroutine that outputs a generator set for G with error probability bounded by 2^{−n^{c}}.

The above lemma implies the the following theorem.

Theorem 5.3. There is a randomized polynomial time algorithm for computing a generator set for the Galois group of a polynomial f ∈ ℤ[x] if it is abelian.

References

[1] J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I & II. ETACS monographs on theoretical computer science. Springer-Verlag, Berlin, 1988 and 1990.

[2] H. Cohen. A Course in Computational Algebraic Number Theory. Springer-Verlag, Berlin, 1993.

[3] J. C. Lagarias and A. M. Odlyzko. Effective versions of the Chebotarev density theorem. In A. Fröhlich, editor, Algebraic Number Fields, pages 409–464. Academic Press, London, 1977.

[4] E. Landau. Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques. Bulletin de la Société de France, 33:251–261, 1905.

[5] S. Landau. Polynomial time algorithms for galois groups. In J. 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.

1In fact k|n_{i} because k is the order of the corresponding Frobenius element which is in the Galois group of f_{i}, and the order of the Galois group is n_{i}.

[6] S. Landau and G. L. Miller. Solvability by radicals is in polynomial time. Journal of Computer and System Sciences, 30:179–208, 1985.

[7] S. Lang. Algebra. Addison-Wesley Publishing Company, Inc, third edition, 1999.

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

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

[10] P. Pálfy. A polynomial bound for the orders of primitive solvable groups. Journal of Algebra, pages 127–137, July 1982.

[11] P. Ribenboim. Classical theory of algebraic numbers. Universitext. Springer, 1999.

[12] C. C. Sims. Computational methods in the study of permutation groups. Computational problems in Abstract Algebra, pages 169–183, 1970.

[13] L. Stockmeyer. On approximating algorithms for #P. SIAM Journal of Computing, 14:849–861, 1985.

[14] B. L. van der Waerden. Algebra, volume I. Springer-Verlag, seventh edition, 1991.

[15] H. Wielandt. Finite Permutation Groups. Academic Press, New York, 1964.