Generating Subfields

Mark van Hoeij

Florida State University Tallahassee, FL 32306

Jürgen Klüners

Mathematisches Institut der Universität Paderborn Universität Paderborn Warburger Str. 100 33098 Paderborn, Germany

Andrew Novocin

David R. Cheriton School of Computer Science University of Waterloo, Ontario, Canada N2L 3G1

Abstract

Given a field extension K/k of degree n we are interested in finding the subfields of K containing k. There can be more than polynomially many subfields. We introduce the notion of generating subfields, a set of up to n subfields whose intersections give the rest. We provide an efficient algorithm which uses linear algebra in k or lattice reduction along with factorization in any extension of K. Implementations show that previously difficult cases can now be handled.

Key words: Symbolic Computation, Subfields, Lattice Reduction

⋆ This research was partly supported by NSF Grant number 0728853 and 1017880 and by the Deutsche Forschungsgemeinschaft

  Email addresses: hoeij@math.fsu.edu (Mark van Hoeij), klueners@math.uni-paderborn.de (Jürgen

Klüners), andy@novocin.com (Andrew Novocin).

Preprint submitted to Elsevier 3 June 2012

Preliminary version – 3 June 2012

1. Introduction

Let K/k be a finite separable field extension of degree n and α a primitive element of K over k with minimal polynomial f ∈ k[x]. We explore the problem of computing subfields of K which contain k. We prove that all such subfields (there might be more than polynomially many) can be expressed as the intersections of at most n particular subfields which we will call the ‘generating subfields’. We give an efficient algorithm to compute these generating subfields. Subfields are used in finding the Galois group of polynomials and can be used when simplifying expressions involving algebraic numbers (see section 3.4 for an example).

Previous methods progress by solving combinatorial problems on the roots of f, such as [4; 5; 8; 13]. Similar to our algorithm [11] starts by factoring f over K and then tries to find all subfield polynomials (see Definition 5) by a combinatorial approach. Such approaches can be very efficient, but in the worst cases they face a combinatorial explosion. While [14] proceeds by factoring resolvent polynomials of degree bounded by \binom{n}{⌊n/2⌋}. By introducing the concept of generating subfields we restrict our search to a small number of target subfields. This new fundamental object allows for polynomial time algorithms.

We can find the generating subfields whenever we have a factorization algorithm for f over K or any K̃/K and the ability to compute a kernel in k. For k = ℚ this implies a polynomial-time algorithm as factoring over ℚ(α) and linear algebra over k = ℚ are polynomial time. When one desires all subfields we give such an algorithm which is additionally linear in the number of subfields.

For the number field case we are interested in a specialized and practical algorithm. Thus we replace exact factorization over ℚ(α) by a p-adic factorization and the exact kernel computation by approximate linear algebra using the famous LLL algorithm for lattice reduction [15]. We take advantage of some recent practical lattice reduction results [19] and tight theoretical bounds to create an implementation which is practical on previously difficult examples.

ROADMAP: The concept of the principal and generating subfields are introduced in Section 2.1. In Section 2.2 we explain how to compute all subfields in a running time which is linearly dependent on the number of subfields. For the number field case we will use the LLL algorithm and this case is handled in detail in Section 3. Finally we compare our approach with the state of the art in Section 4.

NOTATIONS: For a polynomial g we let ∥ g ∥ be the ℓ_{2} norm on the coefficient vector of g. For a vector v we let v[i] be the i^{th} entry. Unless otherwise noted ∥ · ∥ will represent the ℓ_{2} norm.

2. A general algorithm

2.1. Generating subfields

In this section we introduce the concept of a generating set of subfields and prove some important properties. Let K̃ be a field containing K. We remark that we can choose K̃ = K, but in some case it might be better to choose a larger K̃ from an algorithmic point of view. E.g. in the number field case we choose a p-adic completion (see Section 3). Let f = f_{1} ⋯ f_{r} be the factorization of f over K̃ where the f_{i} ∈ K̃[x] are irreducible and f_{1} = x − α. We define the fields K̃_{i} := K̃[x]/(f_{i}) for 1 ≤ i ≤ r. We denote elements of K as g(α) where g ∈ k[x] is a polynomial of degree < n, and define for 1 ≤ i ≤ r the embedding

ϕ_{i} : K → K̃_{i}, g(α) ↦ g(x) mod f_{i}.

Note that ϕ_{1} is just the identity map id : K → K̃. We define for 1 ≤ i ≤ r:

L_{i} := Ker(ϕ_{i} − id) = {g(α) ∈ K | g(x) ≡ g(α) mod f_{i}}.

The L_{i} are closed under multiplication, and hence fields, since ϕ_{i}(ab) = ϕ_{i}(a)ϕ_{i}(b) = ab for all a, b ∈ L_{i}.

Theorem 1. If L is a subfield of K/k then L is the intersection of L_{i}, i ∈ I for some I ⊆ {1, …, r}.

Proof. Let f_{L} be the minimal polynomial of α over L. Then f_{L} divides f since k ⊆ L, and f_{L} = ∏_{i∈I} f_{i} for some I ⊆ {1, …, r} because L ⊆ K̃. We will prove

L = {g(α) ∈ K | g(x) ≡ g(α) mod f_{L}} = ⋂_{i∈I} L_{i}.

If g(α) ∈ L then h(x) := g(x) − g(α) ∈ L[x] is divisible by x − α in K[x]. The set of polynomials in L[x] divisible by x−α is the principal ideal (f_{L}) by definition of f_{L}. Then h(x) ≡ 0 mod f_{L} and hence g(x) ≡ g(α) mod f_{L}. Conversely, g(x) mod f_{L} is in L[x] (mod f_{L}) because division by f_{L} can only introduce coefficients in L. So if g(x) ≡ g(α) mod f_{L} then g(α) ∈ K ∩ L[x] = L.

By separability and the Chinese remainder theorem, one has g(x) ≡ g(α) mod f_{L} if and only if g(x) ≡ g(α) mod f_{i} (i.e. g(α) ∈ L_{i}) for every i ∈ I. □

Lemma 2. The set S := {L_{1}, …, L_{r}} is independent of the choice of K̃.

Proof. Let f = g_{1} ⋯ g_{s} ∈ K[x] be the factorization of f into irreducible factors over K. Suppose that f_{i} divides g_{l}. Let L resp. L_{i} be the subfield corresponding to g_{l} resp. f_{i}. Assume g(α) ∈ L, in other words g(x) ≡ g(α) mod g_{l}. Then g(x) ≡ g(α) mod f_{i} because f_{i} divides g_{l}. Hence g(α) ∈ L_{i}.

Conversely, assume that g(α) ∈ L_{i}. Now h(x) := g(x) − g(α) is divisible by f_{i}, but since h(x) ∈ L_{i}[x] ⊆ K[x] it must also be divisible by g_{l} since g_{l} is irreducible in K[x] and divisible by f_{i}. So g(x) ≡ g(α) mod g_{l} in other words g(α) ∈ L. It follows that L = L_{i}. □

Definition 3. We call the fields L_{1}, …, L_{r} the principal subfields of K/k. A set S of subfields of K/k is called a generating set of K/k if every subfield of K/k can be written as ⋂ T for some T ⊆ S. Here ⋂ T denotes the intersection of all L ∈ T, and ⋂ ∅ refers to K. A subfield L of K/k is called a generating subfield if it satisfies the following equivalent conditions

(1) The intersection of all fields L′ with L ⊊ L′ ⊆ K is not equal to L.

(2) There is precisely one field L ⊊ L̃ ⊆ K for which there is no field between L and L̃ (and not equal to L or L̃).

The field L̃ in condition 2. is called the field right above L. It is clear that L̃ is the intersection in condition 1., so the two conditions are equivalent.

The field K is a principal subfield but not a generating subfield. A maximal subfield of K/k is a generating subfield as well. Theorem 1 says that the principal subfields form a generating set. By condition 1., a generating subfield can not be obtained by intersecting larger subfields, and must therefore be an element of every generating set. In particular, a generating subfield is also a principal subfield.

If S is a generating set, and we remove every L ∈ S for which ⋂{L′ ∈ S|L ⊊ L′} equals L, then what remains is a generating set that contains only generating subfields. It follows that

Proposition 4. S is a generating set if and only if every generating subfield is in S.

Here we just want to illustrate the requirements for finding a generating set of subfields in polynomial time. Suppose that K/k is a finite separable field extension and that one has polynomial time algorithms for factoring over K and linear algebra over k (for example when k = ℚ). Then applying Theorem 1 with K̃ = K yields a generating set S with r ≤ n elements in polynomial time. We may want to minimize r by removing all elements of S that are not generating subfields, then r ≤ n − 1.

Note that the computation of the principal subfields L_{i} is trivial when we know a factorization of f over K. In this case we get a k-basis of L_{i} by a simple kernel computation. In the number field case, the factorization of f over K is the bottleneck. Therefore for some fields k we prefer to take a larger field K̃ ⊋ K where the factorization is faster. In Section 3 this is done for k = ℚ, but this can be generalized to an arbitrary global field. Then we let K̃ be some completion of K. This reduces the cost of the factorization, however, one now has to work with approximations for the factors f_{i} of f, which means that we get approximate (if K̃ is the field of p-adic numbers then this means modulo a prime power) linear equations. Solving approximate equations involves LLL in the number field case and [2; 7] in the function field case.

2.2. All subfields

We would like to compute all subfields of K/k by intersecting elements of a generating set S = {L_{1}, …, L_{r}}. Figure 1 is an algorithm with complexity proportional to the number of subfields of K/k. Unfortunately there exist families of examples where this number is more than polynomial in n. Note that we represent our subfields k ≤ L_{i} ≤ K as k-vector subspaces of K. This allows the intersection L_{1} ∩ L_{2} to be found with linear algebra as the intersection of two subspaces of a vector space. To each subfield L of K/k we associate a tuple e = (e_{1}, …, e_{r}) ∈ {0, 1}^{r}, where e_{i} = 1 if and only if L ⊆ L_{i}.

Input: A generating set S = {L_{1}, …, L_{r}} for K/k. Output: All subfields of K/k.

1. Let e := (e_{1}, …, e_{r}) be the associated tuple of K.

2. ListSubfields := [K].

3. Call NextSubfields(S, K, e, 0).

4. Return ListSubfields.

Fig. 1. AllSubfields Algorithm

The algorithm of figure 2 returns no output but appends elements to ListSubfields, which is used as a global variable. The input consists of a generating set, a subfield L, its associated tuple e = (e_{1}, …, e_{r}), and the smallest integer 0 ≤ s ≤ r for which L = ⋂{L_{i} | 1 ≤ i ≤ s, e_{i} = 1}.

Input: S, L, e, s.

For all i with e_{i} = 0 and s < i ≤ r do

1. Let M := L ∩ L_{i}.

2. Let ẽ be the associated tuple of M.

3. If ẽ_{j} ≤ e_{j} for all 1 ≤ j < i then

4. append M to ListSubfields and call NextSubfields(S, M, ẽ, i).

Fig. 2. NextSubfields Algorithm

Definition 5. Let L be a subfield of K/k. Then the minimal polynomial f_{L} of α over L is called the subfield polynomial of L.

Remark 6. Let g ∈ K[x] be a monic polynomial. Then the following are equivalent:

(1) g = f_{L} for some subfield L of K/k.

(2) f_{1} | g | f and [ℚ(α) : ℚ(coefficients(g))] = degree(g).

(3) f_{1} | g | f and the ℚ–vector space {h(x) ∈ ℚ[x] | deg(h) < deg(f), h mod g = h mod f_{1}} has dimension deg(f)/deg(g).

Remark 7. For each subfield L, we can compute the subfield polynomial f_{L} with linear algebra. Testing if L ⊆ M then reduces to testing if f_{L} is divisible by f_{M}. For many fields K this test can be implemented efficiently by choosing a non-archimedian valuation v of K with residue field F such that the f mod v (the image of f in F[x]) is defined and separable. Then f_{L} is divisible by f_{M} in K[x] if and only if the same is true mod v, since both are factors of a polynomial f whose discriminant does not vanish mod v.

Subfields that are isomorphic but not identical are considered to be different in this paper. For instance, let f = x^{6} + 3. Now ℚ[x]/(f) is isomorphic to the splitting field of x^{3} − 3. This polynomial has 3 roots, \sqrt[3]{3}, ω\sqrt[3]{3}, ω^{2} \sqrt[3]{3} where ω is a third root of unity. Each of these roots gives a subfield of degree 3 that is isomorphic to ℚ[x]/(x^{3} − 3). We consider these as 3 distinct subfields.

Let m be the number of subfields of K/k. Since S is a generating set, all subfields occur as intersections of L_{1}, …, L_{r}. The condition in Step (3) in Algorithm NextSubfields holds if and only if M has not already been computed before. So each subfield will be placed in ListSubfields precisely once, and the total number of calls to Algorithm NextSubfields equals m. For each call, the number of i’s with e_{i} = 0 and s < i ≤ r is bounded by r, so the total number of intersections calculated in Step (1) is ≤ rm. Step (2) involves testing which L_{j} contain M. Bounding the number of j’s by r, the number of subset tests is ≤ r^{2}m. One can implement Remark 7 to keep the cost of each test low.

Theorem 8. Given a generating set for K/k with r elements, Algorithm AllSubfields returns all subfields by computing at most rm intersections and at most r^{2}m subset tests, where m is the number of subfields of K/k.

2.3. Quadratic subfields

As a theoretical application, to illustrate the framework of generating subfields, we note that all quadratic subfields can be computed in polynomial time when we already know the generating subfields. Note that during our discussion we encounter a field extension with Galois group C_{2}^{s}, which is the simplest example of a field extension which has more than polynomially many subfields.

Let Q(K/k) denote the subfield generated over k by {a ∈ K|a^{2} ∈ k}, and let C_{2} denote the cyclic group of order 2. If K = Q(K/k), in other words the Galois group of f is C_{2}^{s} for some s, then n = 2^{s} and f splits over K into linear factors f_{1} ⋯ f_{n} where f_{1} = x − α. Furthermore, there are precisely n − 1 generating subfields L_{2}, …, L_{n} and n principal subfields L_{1}, …, L_{n} where L_{1} = K.

Conversely, suppose there are n principal subfields. Every principal subfield corresponds to at least one factor of f over K, and hence to precisely one factor since f has degree n. So f must split into linear factors, and each L_{i} corresponds to precisely one linear factor f_{i}. Then the minimal polynomial of α over L_{i} is f_{1}f_{i} when i ∈ {2, …, n}. The degree of f_{1}f_{i} is 2, so there are n − 1 subfields of degree index 2, which implies that the Galois group is C_{2}^{s} for some s.

Theorem 9. If factoring over K and linear algebra over k can be done in polynomial time then all quadratic subfields of K/k can be computed in polynomial time.

Note that a subfield of degree index 2 of K/k corresponds to an autmorphism of K/k of order 2 which can be easily computed. Therefore the knowledge of all principal subfields of Q(K/k) is equivalent to the knowledge of all automorphisms of the Galois group. Hence, the quadratic subfields of Q(K/k) can be computed easily in polynomial time. So it suffices to prove that the following algorithm computes Q(K/k) in polynomial time.

Input: A separable field extension K/k where K = k(α).

Output: Q(K/k).

1. Let n := [K : k]. If n is odd then return k.

2. Compute the set S of generating subfields.

3. If K/k has n − 1 distinct subfields of degree index 2 then return K.

4. Choose a generating subfield L_{i} ∈ S with degree index > 2, and let L̃_{i} be the field right above L_{i}, so L_{i} ⊊ L̃_{i} := ⋂{L_{j} ∈ S | L_{i} ⊊ L_{j}}.

5. If [L̃_{i} : L_{i}] = 2 then return Q(L̃_{i}/k), otherwise return Q(L_{i}/k).

Fig. 3. Algorithm Q

In the first call to Algorithm Q, we can compute a generating set in Step (2) in polynomial time using Theorem 1 with K̃ := K. For the recursive calls we use:

Remark 10. If S is a generating set for K/k and if L is a subfield of K/k, then {L ⋂ L′|L′ ∈ S} is a generating set of L/k.

For Step (3) see the remarks before Theorem 9. If we reach Step (4) then K ≠ Q(K/k). The field L_{i} in Step (4) exists by Lemma 11 below. Let L̃_{i} be the field right above L_{i}. If [L̃_{i} : L_{i}] = 2 then L̃_{i} ≠ K so the algorithm terminates.

Let a ∈ Q(K/k). We may assume that a^{2} ∈ k. Now L̃_{i} is contained in any subfield L′ of K/k that properly contains L_{i}. So if a ∉ L_{i} then L_{i}(a) contains L̃_{i} and hence equals L̃_{i} since [L_{i} : L_{i}(a)] = 2. Then a ∈ L̃_{i}. We conclude Q(K/k) ⊆ L̃_{i}. If [L̃_{i} : L_{i}] ≠ 2 then the assumption a ∉ L_{i} leads to a contradiction since L_{i}(a) can not contain L̃_{i} in this case. So Q(K/k) ⊆ L_{i} in this case, which proves that Step (5) is correct.

Lemma 11. If K/k does not have n − 1 distinct subfields of degree index 2 then there exists a generating subfield of degree index > 2.

Proof. Assume that every generating (and hence every maximal) subfield has degree index 2. So the subfields of degree index 2 form a generating set. Let G be the automorphism group of K/k. If K/L_{i} and K/L_{j} are Galois extensions, then so is K/(L_{i} ∩ L_{j}) since L_{i} ∩ L_{j} is the fixed field of the group generated by the Galois groups of K/L_{i} and K/L_{j}. If [K : L_{i}] = 2 then K/L_{i} is Galois. Let k′ be the intersection of all subfields L_{i} of degree index 2. Then K/k′ is Galois. However, k′ must equal k, otherwise the set of subfields of degree index 2 can not be a generating set. It follows that K/k is Galois.

If n is not a power of 2, then there exists a maximal subfield of odd degree index. If n = 2^{s} with s > 1 then the Galois group must have an element of order 4 (G can not be C_{2}^{s} since the number of subfields of degree index 2 is not n − 1). This element of order 4 corresponds to a linear factor f_{i} of f in K[x]. Let L_{i} be its corresponding principal subfield. Then L_{i} is contained in m maximal subfields where m is either 1 or 3. Let f̌_{i} be the minimal polynomial of α over L_{i}. If m = 3 then every irreducible factor of f̌_{i}/(x − α) corresponds to a subfield of degree index 2. This is a contradiction since f_{i} divides f̌_{i}/(x − α). □

3. The number field case

3.1. Introduction

In this section we describe an algorithm for producing a generating set when K = ℚ(α). Factoring f over K, though polynomial time, is slow, thus we prefer to use an approximation of a p-adic factorization and LLL. We show that when the algorithm terminates^{1} , it returns the correct output.

For a prime number p, let ℚ_{p} denote the field of p-adic numbers, ℤ_{p} the ring of p-adic integers, and F_{p} = ℤ/(p). We choose a prime number p with these three properties: p does not divide the leading coefficient of f ∈ ℤ[x], the image \overline{f} of f in F_{p}[x] is separable, and has at least one linear factor which we denote \overline{f}_{1} (asymptotically, the probability that a randomly chosen prime p has these properties is ≥ 1/n, where equality holds when K/k is Galois).

By factoring \overline{f} in F_{p}[x] and applying Hensel lifting, we obtain a factorization of f = f_{1} ⋯ f_{r} over ℚ_{p} where f_{1} has degree 1. By mapping α ∈ K to the root α_{1} of f_{1} in ℚ_{p} we obtain an embedding K → ℚ_{p}, and so we can view K as a subfield of K̃ := ℚ_{p}.

1 a bound for the running time can be obtained in a similar way as in [3]

The advantage of taking ℚ_{p} (instead of K) for K̃ is that it saves time on factoring f over K̃. Since p does not divide the denominators of the coefficients of f, the factors f_{1}, …, f_{r} of f over ℚ_{p} lie in ℤ_{p}[x]. We can not compute these factors with infinite accuracy, but only to some finite accuracy a, meaning that f_{1}, …, f_{r} are only known modulo p^{a}.

For each of the factors, f_{i}, we will need to find the principal subfield L_{i} which was defined in Section 2.1 as the kernel of ϕ_{i} − id. To do this we will make use of a knapsackstyle lattice in the style of [19]. To get the best performance we would like to design a lattice such that boundably short vectors correspond to elements in L_{i}.

A natural approach would be to use 1, α, …, α^{n−1} as a basis, and search for linear combinations whose images under ϕ_{i} −id are 0 (mod p^{a}). However, we will use a different basis. Denote ℤ[α]_{<n} := ℤ·α^{0} +⋯+ℤ·α^{n−1} (note: if f is monic then this is simply ℤ[α] but we do not assume that f is monic). Then the basis \frac{1}{f′(α)}, …, \frac{α^{n−1}}{f′(α)} of \frac{1}{f′(α)} · ℤ[α]_{<n} allows us to prove more practical bounds (this phenomena has also been observed in other contexts [6]). Using this basis of K we prove the existence of a ℚ-basis of L_{i} which has a bounded representation. We delay the proof of this theorem until section 3.5.

Theorem 12. Let L_{i}, the target principal subfield, have degree m_{i} over ℚ. For β ∈ \frac{1}{f′(α)} · ℤ[α]_{<n} with β = ∑ b_{i} \frac{α^{i}}{f′(α)} we associate the vector v_{β} := (b_{0}, …, b_{n−1}). Then there exists m_{i} linearly independent algebraic numbers β_{1}, … β_{m_{i}} ∈ L_{i} ∩ \frac{1}{f′(α)} · ℤ[α]_{<n} each with ∥v_{β_{k}}∥ ≤ n^{2}∥f∥_{2}.

3.2. The computation of a principal subfield

Now we can continue the description of the computation of the principal subfield L_{i} corresponding to the factor f_{i} of degree d_{i}. As mentioned before we will represent our elements in the basis \frac{1}{f′(α)}, …, \frac{α^{n−1}}{f′(α)}. Each of these basis elements will be represented as the column of an identity matrix to which we attach entries for the image of that basis element under ϕ_{i} − id. Since these images are only known modulo p^{a} we must also adjoin columns which allow for this modular reduction. Suppose the degree of f_{i} is d_{i}, then our lattice is spanned by the columns of the following (n + d_{i}) × (n + d_{i}) integer matrix:

B_{i} := (\begin{matrix}1 \\ . & . & . \\ & & 1 \\ c_{0,0} & … & c_{0,n−1} & p^{a} \\ ⋮ & ... & ⋮ & & ... \\ c_{d_{i}−1,0} & … & c_{d_{i}−1,n−1} & & & p^{a} \end{matrix})  (1)

where c_{k,j} is the k^{th} coefficient of \frac{x^{j}}{f′(x)}modf_{i} − \frac{x^{j}}{f′(x)}modf_{1} reduced modulo p^{a}. To interpret a vector v in the column space of this matrix we take the first n entries b_{0}, …, b_{n−1} and then compute (∑ b_{j}α^{j})/f′(α). A vector corresponding to an element in L_{i} will have its final d_{i} entries be 0 modulo p^{a}. Thus Theorem 12 shows us that the lattice generated by columns of B_{i} contains a dimension m_{i} sublattice which has a small basis. This allows us to use the new sub-lattice reduction techniques of [19] on B_{i}. Thus, rather than standard LLL, we use LLL with removals which performs lattice reduction but removes any vectors in the final position whose G-S norm is above a given bound. The following lemma is derived from [15] and justifies these removals.

Lemma 13. Given a basis b_{1}, …, b_{d} of a lattice Λ, and let b_{1}^{∗}, …, b_{d}^{∗} be the output of Gram-Schmidt orthogonalization. If ∥ b_{d}^{∗} ∥ > B then any vector in L with norm ≤ B is a ℤ-linear combination of b_{1}, …, b_{d−1}.

This technique is common and is used in [10; 19]. As the removal condition requires Gram-Schmidt norms we can state that LLL reduced bases tend to be numerically stable for Gram-Schmidt computations so a floating point Gram-Schmidt computation could be used for efficiency (see [20]). Also FLINT 1.6 [9] has an LLL with removals routine which takes a bound and returns the dimension of the appropriate sub-lattice.

In this way using LLL with removals with the bound from Theorem 12 will allow us to reduce the dimension. In Figure 4 we give a practical algorithm which will create a basis of a subfield of K which is highly likely to be L_{i}. We will use D := diag{1, …, 1, C, …, C} as a matrix for scaling the last d_{i} rows of B_{i} by a scalar C. Since the vectors guaranteed by Theorem 12 come from L_{i} we know that the final d_{i} entries must be 0. Thus multiplication on the left by D and removals will eventually ensure that vectors with zero entries are found by LLL.

Input: f_{i}

Output: h_{k} which probably generate L_{i}

1. Create lattice B_{i} from equation ((1))

                     2. A := LLL with removals(B_{i}, n^{2} ∥ f ∥)

3. m := dim(A)

4. while ∃l > n, j such that A[l, j] ≠ 0 :

5. A := D · A

                     6. A := LLL with removals(A, n^{2} ∥ f ∥)

7. m := dim(A)

8. if m ∤ n increase precision repeat principal 9. for 1 ≤ k ≤ m:

10. h_{k} := ∑_{j=1}^{n} \frac{A[j,k]x^{j−1}}{f′(x)}

Fig. 4. principal algorithm

Using LLL on the matrix entire B_{i} will suffice for this paper. However, in practice the d_{i} final rows of B_{i} can also be reduced one at a time. In this way one could potentially arrive at a solution without needing all rows of B_{i}. Such an approach is seen in [19] and could be adapted to this situation.

The algorithm in figure 4 will produce m p-adic polynomials h_{k}, which are likely to correspond to algebraic numbers which generate L_{i} as a ℚ-vector space. It is possible that m is not m_{i} but some other divisor of n. In particular, if the p-adic precision is not high enough then there could be entries in the lattice basis which are 0 modulo p^{a} but not exactly 0. In that case one of the h_{k} would not be from L_{i}. Even so the ℚ-vector space generated by the h_{k} must at least contain L_{i}. The reason is that at least m_{i} linearly independent algebraic numbers from L_{i} remain within the lattice after LLL with removals thanks to the bound of Theorem 12 and Lemma 13.

Theorem 12 can also be used to make a guess for a starting precision of p^{a}. Since any reduced basis has Gram-Schmidt norms within a factor 2^{n+d_{i}} of the successive minima and the determinant of B_{i} is p^{a·d_{i}} then we should ensure that p^{a·d_{i}} is at least (2^{n+d_{i}}n^{2}∥f∥)^{n}.

3.3. Confirming a principal subfield

In this section we will assume that we have elements which are likely to generate a principal subfield (in other words, the output of the algorithm in Figure 4). At this point it seems reasonable to discuss the possible paths forward. This must include a discussion of the types of output that a user might want. We recommend outputting the subfield polynomial represented in the α^{i}/f′(α) basis. This has the advantage of certifying that the elements we have indeed generate the target L_{i}. In addition it gives us a representation of L_{i} which can be stored on a relatively small number of bits.

It may also seem reasonable to ask for a primitive element of L_{i} perhaps given as the root of some minimal polynomial with coefficients in ℤ. The coefficients of the subfield polynomial are a good source of potential primitive elements which will have small minimal polynomials. After all, the coefficients of the subfield polynomial must generate L_{i}. It might also be likely that such a minimal polynomial could be much larger than our suggested representation of the subfield polynomial. For these reasons we will deal primarily with finding the subfield polynomial, we do this in section 3.3.2.

Before that we treat the option of resuming the algorithm using the block methods of [12; 13]. This makes some sense as the combinatorial explosion in that method might already have been bypassed. This approach is discussed in section 3.3.1. The output of that algorithm is a primitive element of the L_{i}.

Then in section 3.4 we will give an illustrative example of the algorithm in action so as to clarify the procedure. Finally in section 3.5 we prove the main technical theorem which allowed us to provably bound the output of Figure 4.

3.3.1. Using block systems to confirm the subfield

In this section we show the connection with what we have computed so far and the block systems approach of [12; 13]. We can use any of the non integral algebraic numbers output by figure 4 to generate block systems if we would like to avoid doing more LLL reduction. We try to combine the advantages of both methods. The big problem of the method presented in [12; 13] is that we have to consider exponentially many possibilities of potential block systems in the worst case. On the other hand this method is very efficient as soon as we have found the right block system. After the computation done in Figure 4 we get elements h_{1}, …, h_{m} and we are almost certain that these elements generate our principal subfield. More precisely we expect that they form a vector space basis of our prinicipal subfield L_{i}. In order to be sure we need a proof for this statement. Furthermore we would like to find a nice presentation of our subfield. Knowing the elements h_{1}, …, h_{m} it is easy to write down the corresponding block system. Having the actual block system in our hand we can apply the methods described in [12; 13] without having the combinatorial explosion.

Before we explain this approach let us give a criterion which gives a check if a given subfield L is equal to the principal subfield L_{i}.

Lemma 14. Let L = ℚ(β) be a subfield of K. Let β = g(α), where g(x) ∈ ℚ[x] is a polynomial of degree smaller than n. As before denote by f = f_{1} ⋯ f_{r} ∈ ℚ_{p}[x] the factorization of f into irreducible factors over ℚ_{p}. Define T := {1 ≤ i ≤ r | g(x) ≡ g(α) mod f_{i}}. Then the subfield polynomial f_{L} = ∏_{i∈T} f_{i}.

The proof of this lemma follows easily from the discussion before Theorem 1. Now L is a subfield of L_{i} if and only if i ∈ T. From the computation in Figure 4 we know that L_{i} has at most degree m. This means that our field L = L_{i}, when we know that L ≤ L_{i} and the degree of L is m.

One approach could be to compute the minimal polynomials of the elements h_{i} hoping to quickly find a primitive element (of degree m). Then we test if L ≤ L_{i} by using Lemma 14. We remark that the test in Lemma 14 can be done modulo p^{k} for a small k (in most cases k = 1). We can increase k until we get that the degree of L times the product of the degrees of the f_{i} with i ∈ T equals n. In general the elements h_{i} are non-integral elements and their minimal polynomials are not nice at all. If we look at our computation it is not necessary to compute the minimal polynomials. In order to identify the right set T we can use the identity:

T = {1 ≤ i ≤ r | ∀1 ≤ j ≤ m : g_{j}(x) ≡ g_{j}(α) mod f_{i}},

where h_{j} = g_{j}(α).

Now we explain how to compute the corresponding (potential) block system which can be used by the method described in [13]. For this we use the notation of this paper. Let α_{1}, …, α_{n} be the roots of f in some unramified p-adic extension of ℚ_{p}. Let β = h(α) be a primitive element of the subfield L of degree m, where h ∈ ℚ[x] is a polynomial of degree less than n. Furthermore we denote by β_{1}, …, β_{m} the roots of g in the same p-adic extension. Then the corresponding block system is given by Lemma 3.21 in [13] via

Δ_{i} := {α_{j} | h(α_{j}) = β_{i}, 1 ≤ j ≤ n}.

Now enter the subfield algorithm in [13] using this potential block system. If this algorithm succeeds in computing a subfield L, then test if L = L_{i} using Lemma 14. Note (see equation (12) in [13]) that this algorithm computes the element δ_{1} = ∏_{α∈Δ_{1}} α as a first guess of a primitive element of our subfield. If this element fails to generate our subfield then elements of the form ∏_{α∈Δ_{1}}(α + k) for some k ∈ ℤ are chosen. Note that δ_{1} is, up to the sign, the absolute coefficient of the subfield polynomial f_{L}. It is easy to adapt the algorithm described in [13] to use other coefficients of f_{L}. In the case that ∑_{α∈Δ_{1}} α is a primitive element, this usually gives generators of small size.

3.3.2. Finding a small representation of the subfield polynomial using LLL

We give an algorithm which will construct the subfield polynomial g, of L_{i} or return failure, in which case more p-adic precision is needed. We choose the subfield polynomial as it will provide a proof that we have a principal subfield and can be stored in a relatively compact way thanks to our new basis. Of course other representations and proofs are possible.

From here on our algorithmic objective will be to output the minimal polynomial g ∈ L_{i}[x] of α over L_{i}. This g is the subfield polynomial of L_{i} and its coefficients generate L_{i}. We know m elements h_{k} modulo p^{a}, we know that m|n and that (ϕ_{i} − id)(h_{k}) ≡ 0 modulo p^{a} for each k. Recall that the h_{k} were from columns of a lattice basis A. First we will create a p-adic candidate subfield polynomial which we then subject to 3 certification checks.

Candidate g: Create an index set T := {j|ϕ_{j}(h_{k}) ≡ id(h_{k}) mod p^{a}∀h_{k}}, that is find the p-adic factors of f which also agree with f_{1} on the elements corresponding to the basis from A. T will contain at least 1 and i. Now let g_{cand} := ∏_{j∈T} f_{j} mod p^{a}. This is done in steps 1–5 of Figure 5

Input: h_{1} … h_{m}, f_{1}, … f_{r} ∈ ℚ_{p}[x], precision a Output: g subfield poly, or fail

1. T := {}

2. for each 1 ≤ j ≤ r:

3. if (h_{k} mod f_{j} = h_{k} mod f_{1}) mod p^{a}∀k then:

4. T := T ∪ j

5. g_{cand} := lc(f) · ∏_{j∈T} f_{j} mod p^{a} where lc(f) is the leading coefficient of f

6. Create lattice M using (2)

7. M :=LLL(M)

8. g_{temp} = 0

9. for each coefficient g_{k} of x^{k} in g_{cand}:

10. create M_{g_{k}} lattice using (3)

11. Check 1 find v in LLL(M_{g_{k}})

with v[n + 1] = 0 and v[n + 2] = 1 12. g_{temp} := g_{temp} + ∑_{j=1}^{n} \frac{v[j]α^{j−1}}{f′(α)} x^{k}

13. g_{cand} := g_{temp} ∈ ℚ(α)[x]

14. Check 2 ensure g_{cand}|f exactly

15. Check 3 ensure (h_{k} mod g_{cand} = h_{k} mod f_{1}) ∀k 16. return g := g_{cand}

Fig. 5. final check algorithm

Check 1: Let Λ(A) ⊆ \frac{ℤ[α]_{<n}}{f′(α)} be the lattice generated by the algebraic numbers corresponding with columns of A. We now attempt to find an exact representation of g_{cand} by converting each coefficient into an algebraic number in Λ(A) ∩ \frac{ℤ[α]_{<n}}{f′(α)} . We’ll do this by attempting to find linear combinations of h_{k} which exactly equal each coefficient of g_{cand}.

Note that this g_{cand} is a polynomial with p-adic coefficients, these coefficients can be quickly Hensel lifted using the fact that f = g · (f/g) mod p^{a} if more precision is needed. Now we want to express these coefficients in the basis \frac{ℤ[α]_{<n}}{f′(α)} ∩ Λ(A). To do this we will use a lattice basis similar to A with a slight adjustment. Rather than finding algebraic numbers whose images under ϕ_{i} − id are zero, we’ll find combinations of the h_{k} whose p-adic valuations match a coefficient of g_{cand}.

Lets call v_{h_{k}} the coefficient vector of h_{k}, and the corresponding p-adic valuation c_{j} := h_{k}(α_{1}) (that is, h_{k} modulo f_{1}). Also we pick a large scalar constant C (to ensure that LLL works on reducing the size of the p-adic row). We let the columns of the new matrix be (v_{h_{j}}, C · c_{j})^{T}, and the column (0, …, 0, C · p^{a}).

M := (\begin{matrix}v_{h_{1}}^{T} & … & v_{h_{m}}^{T} & 0 \\ C · c_{1} & … & C · c_{m} & C · p^{a} \end{matrix})  (2)

A vector in the column space of this matrix is a representation of a combination of the elements from h_{k} along with a p-adic valuation of that element. Now for each coefficient we’ll use this matrix to find a combination which matches that coefficient. In practice we LLL-reduce M before adjoining data from the coefficients of g_{cand}, but here we present an augmented M without altering the columns first (for clarity).

For each coefficient g_{k} of g_{cand} augment each column of M with a zero, then adjoin a new column (0, …, 0, C · g_{k}, 1)^{T}. This is what the coefficient matching matrix looks like:

M := (\begin{matrix}v_{h_{1}}^{T} & … & v_{h_{m}}^{T} & 0 & 0 \\ C · c_{1} & … & C · c_{m} & C · p^{a} & C · g_{k} \\ 0 & … & 0 & 0 & 1 \end{matrix})  (3)

Run LLL on this matrix (provided C is large enough) then find the vector which has its final two entries as 0,1, the first n entries are an expression of g_{k} in \frac{ℤ[α]_{<n}}{f′(α)} . If this works for every coefficient of g_{cand} then the check has passed.

Check 2: Ensure that g_{cand}|f in ℚ(α)[x].

Check 3: Ensure that h_{k} mod g_{cand} = h_{k} mod f_{1} for each h_{k}.

Theorem 15. If all checks pass then the ℚ-linear combination of the elements corresponding to the lattice basis A generate L_{i} the target principal subfield, and g_{cand} is the subfield polynomial of L_{i}.

Proof. By construction of g_{cand} and A we know that the span over ℚ of the elements corresponding to A, the h_{k}, contains L_{i}. Let’s call this span V, so L_{i} ⊆ V. Since g_{cand} divides f and f_{i} divides g_{cand} then h mod g_{cand} = h mod f_{1} implies h mod f_{i} = h mod f_{1}. By check 1 this implies that V ⊆ L_{i} thus the span over ℚ of the elements from the lattice is L_{i}.

Now x−α, f_{i}|g_{cand} mod p^{a} and g_{cand}|f exactly then f_{i}|g_{cand} and (x−α)|g_{cand} exactly. Now by Remark 6 we know g_{cand} is the subfield polynomial of L_{i}. □

If any check fails increase the p-adic precision via Hensel lifting and try again.

3.4. An illustrative example

Here we provide an example from a potential application of the algorithm. Suppose that one is searching for solutions to the system of equations

a^{2} − 2ab + b^{2} − 8 = 0
a^{2}b^{2} − (a^{2} + 2a + 5)b + a^{3} − 3a + 3 = 0.

Using MAPLE’s [16] solve command the output is:

α = RootOf(x^{8} − 20x^{6} + 16x^{5} + 98x^{4} + 32x^{3} − 12x^{2} − 208x − 191)
a = α
b = −34α^{7} + 61α^{6} + 742α^{5} − 1757α^{4} − 3378α^{3} + 6013α^{2} + 6368α + 7175.

By writing α in terms of generators of proper subfields of ℚ(α) we can greatly simplify the expression to:

a = \sqrt{3} + \sqrt[4]{2} − \sqrt{2}
b = \sqrt{3} + \sqrt[4]{2} + \sqrt{2}.

This illustrates that computing subfields is an important step toward simplifying algebraic expressions.

Here we will give the various stages of the algorithm’s output using the minpoly of α, f = x^{8} − 20x^{6} + 16x^{5} + 98x^{4} + 32x^{3} − 12x^{2} − 208x − 191, as our input.

The first step is to find a prime such that f is squarefree modulo p and has at least one linear factor. The first acceptable prime is 23 and the factorization of f mod 23 is:

f ≡ (x + 3)(x − 4)(x + 10)(x − 6)(x^{2} + x + 1)(x^{2} − 4x − 1).

Now we must Hensel lift this factorization so that short vectors are not likely to be because of a small modulus. To decide a target p-adic precision we refer to Theorem 12 which asserts that we are looking for vectors of norm ≤ n^{2} ∥ f ∥_{2}= 64 · 302. One could begin the algorithm with p^{a} just above this bound and resume hensel lifting in the case of failure; or one could begin well above the bound to minimize the chances of early failure. In this particular case a modulus of p^{25} is always sufficient for solving the problem.

We will let the first linear local factor of f be labeled f_{1} (in this case the factor whose image is x + 3 modulo 23). Recall that f_{1} is defined to be x − α so that the principal subfield L_{1} := {g(α) ∈ ℚ(α)|g(x) ≡ g(α) mod f_{1}} is simply ℚ(α). Thus L_{2} is potentially the first non-trivial principal subfield, where f_{2} is the next factor (in this case the p-adic factor whose image mod 23 is equivalent to x − 4).

Now we must construct the lattice from equation (1) whose columns correspond with a basis of \frac{1}{f′(α)}ℤ_{≤n}[α]. Specifically column i will be e_{i} (the standard basis vector) augmented with (\frac{x^{i−1}}{f′(x)} mod f_{2}) − (\frac{x^{i−1}}{f′(x)} mod f_{1}), thus any element in L_{2} will have 0 as the final entry. In the implementation we compute \frac{1}{f′(x)} mod f as an integer polynomial with a single denominator at the beginning of the procedure and use its image modulo the local factors in the various stages when it is needed.

For illustration we will show the lattice with low p-adic precision, so that the reader can easily confirm the construction. In this case \frac{1}{f′(α)} mod ⟨x + 3, 23⟩ ≡ 3 and \frac{1}{f′(α)} mod ⟨x − 4, 23⟩ ≡ 22. So (\frac{x^{0}}{f′(x)} mod f_{2}) − (\frac{x^{0}}{f′(x)} mod f_{1}) is 19. Repeat the process for the other powers of x, (\frac{x^{i−1}}{f′(x)} mod f_{2}) − (\frac{x^{i−1}}{f′(x)} mod f_{1}), to get the lattice from equation (1) with 23-adic precision 1 (i.e. mod 23):

B_{2}^{T} := (\begin{matrix}1 & & & & & & & & 19 \\ & 1 & & & & & & & 5 \\ & & 1 & & & & & & 3 \\ & & & 1 & & & & & 17 \\ & & & & 1 & & & & 7 \\ & & & & & 1 & & & 4 \\ & & & & & & 1 & & 19 \\ & & & & & & & 1 & 21 \\ & & & & & & & & 23 \end{matrix}) .

Now this matrix does not have large enough p-adic entries to get valuable information out of an LLL run. However LLL on B_{2} with higher p-adic precision will yield 4 vectors of small norm and 5 vectors of large norm. When the precision is at least 23^{25} then the G-S norms of the 5 final vectors will be large enough (more than 64 · 302) to prove, via Lemma 13, that the span of 4 short vectors must contain the basis of L_{2} guaranteed by Theorem 12. In this case the four short vectors are the transpose of:

(\begin{matrix}7 & 6 & 2 & −20 & −3 & 2 & 0 & 0 & 0 \\ −18 & 12 & 1 & 5 & 8 & 10 & −1 & −1 & 0 \\ 5 & −15 & −18 & 11 & −1 & 9 & 0 & −1 & 0 \\ −15 & −35 & 3 & −23 & 9 & −7 & −1 & 1 & 0 \end{matrix}) .

These four vectors represent a potential basis of L_{2} ∩ \frac{1}{f′(α)}ℤ_{≤n}[α]. The fact that 4 divides 8 is a simple first check that we have a potential subfield. Next the fact that each of the last entries is 0 is a check that we might be looking at vectors inside of L_{2} (the worst case is that two or four of these vectors happen to have last entry with an image of 0 mod 23^{25} but this would not be exactly 0 at infinite precision). From here, there are several paths we could take, namely: compute the subfield polynomial of L_{2}, that is the minimal polynomial of α over L_{2} (proving that we really have L_{2}) or compute a primitive element of L_{2} and prove that what we have is actually L_{2} in some other way. See the discussion in section 3.3. Here we will compute the subfield polynomial.

The subfield polynomial must be the product of some subset of the p-adic factors of f. We wish to find all factors which make up the subfield polynomial for L_{2}. We do this by checking which other p-adic factors of f agree with f_{1} on the four given elements. For example to check the first vector one computes \frac{(7+6x+2x^{2}−20x^{3}−3x^{4}+2x^{5})}{f′(x)} modulo ⟨f_{i}, 23^{25}⟩ for all i. Then any f_{i} which give the same output as f_{1} will be considered to agree on the first element. In this case, none of the other factors agree with f_{1} and f_{2} on all 4 vectors (although f_{5} agrees on two of the four elements).

So we now assume that the subfield polynomial is f_{1} · f_{2} until we can prove otherwise. Since we have approximations of those factors to precision 23^{25} we compute the candidate for the subfield poly g = f_{1} · f_{2} mod 23^{25}, this is g_{cand} in figure 5. Now we have p-adic numbers g_{i} for each coefficient in g_{cand} = g_{0} + g_{1}x + g_{2}x^{2}. The lattice from equation (3) will help us find a representation of the g_{i} in terms of α. This works by attempting to find a linear combination of the short vectors which has the same p-adic image as one of the coefficients of g_{cand}. So if we let v_{i} be the p-adic images of the four short vectors in our example we could use a lattice like the transpose of this one for finding g_{0}:

(\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 23^{25} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & g_{0} & 1 \\ 7 & 6 & 2 & −20 & −3 & 2 & 0 & 0 & v_{1} & 0 \\ −18 & 12 & 1 & 5 & 8 & 10 & −1 & −1 & v_{2} & 0 \\ 5 & −15 & −18 & 11 & −1 & 9 & 0 & −1 & v_{3} & 0 \\ −15 & −35 & 3 & −23 & 9 & −7 & −1 & 1 & v_{4} & 0 \end{matrix}) .

In this case we also suggest scaling the column containing p^{a}, v_{j}, and g_{i} by some large constant (in the implementation we used 2^{40}), so that LLL is more likely to find a vector which ends with 0 and 1. This particular lattice yields such a vector, (0, −24, −368, −136, 32, 424, −16, −40, 0, 1). We interpret this to say that

g_{0} = \frac{(−24α − 368α^{2} − 136α^{3} + 32α^{4} + 424α^{5} − 16α^{6} − 40α^{7})}{f′(α)}.

By constructing the same lattice for g_{1} and g_{2} we can get a representation of g_{cand} in L_{2}[x] which uses the α^{i}/f′(α) basis. That representation could be encoded in the transpose of the following:

(\begin{matrix}0 & −24 & −368 & −136 & 32 & 424 & −16 & −40 \\ 1552 & 1824 & 208 & −192 & −816 & −32 & 80 & 0 \\ 208 & 24 & −96 & −392 & −80 & 120 & 0 & −8 \end{matrix}) .

Note that the final row is actually the coefficients of f′(α) so this is a monic polynomial. In general the coefficients of g, the subfield polynomial, will have much smaller minimal polynomials than the elements from the short vectors. If one needs to compute a primitive element of L_{2} then we suggest taking coefficients of g and testing if they are primitive elements. For instance g_{1} and g_{0} have minimal polynomials of degree 4, so either will generate L_{2} because g has degree 2 and [ℚ(α) : ℚ] = 8. In this case the minimal polynomial of g_{1}, corresponding to the second row above, is x^{4} − 40x^{2} + 16. If this fails then try small combinations of the coefficients.

3.5. Bounds for the coefficients

The only aim of this section is to prove Theorem 12. The techniques described in this section are not used in the algorithm.

In order to get our desired bounds it is useful to introduce the notation of a codifferent, see [17, Chapter 4.2] for more details.

Lemma 16. Let f ∈ ℤ[x] be primitive and irreducible, with degree n. Let α be a root of f. Let O_{K} be the ring of integers in K = ℚ(α) and let O_{K}^{∗} be the co-different which is defined as:

O_{K}^{∗} = {a ∈ K|∀_{b∈O_{K}} Tr(ab) ∈ ℤ}.

Then

O_{K}^{∗} ⊆ \frac{1}{f′(α)}ℤ[α]_{<n}.  (4)

Proof. Let a ∈ O_{K}^{∗}, so Tr(ab) ∈ ℤ for any b ∈ O_{K}. The content of a polynomial g = c_{0}x^{0} + ⋯ + c_{d}x^{d} ∈ K[x] is defined as the fractional ideal c(g) = O_{K}c_{0} + ⋯ + O_{K}c_{d}. Let g_{1} = x−α and g_{2} = f/g_{1}. Gauss’ lemma says c(g_{1})c(g_{2}) = c(g_{1}g_{2}). Then c(g_{1})c(g_{2}) = c(f) = O_{K}, (f is primitive) and since g_{1} has a coefficient equal to 1 it follows that c(g_{2}) ⊆ O_{K}, in other words g_{2} ∈ O_{K}[x]. Now ag_{2} ∈ a · O_{K}[x]_{<n} and by definition of O_{K}^{∗} we see that Tr(ag_{2}) ∈ ℤ[x]_{<n}. So

Tr(a\frac{f(x)}{x − α}) = ∑ a^{(i)} \frac{f(x)}{x − α^{(i)}} ∈ ℤ[x]_{<n}

where a^{(i)} and α^{(i)} denote the conjugates of a and α. Evaluating the right-hand side at x = α = α^{(1)} gives af′(α) ∈ ℤ[α]_{<n} and hence a ∈ 1/f′(α) · ℤ[α]_{<n}. □

Now suppose that we have a β ∈ O_{K}^{∗}, then we can write

f′(α)β = ∑_{i=0}^{n−1} b_{i}α^{i} with b_{i} ∈ ℤ.  (5)

In our applications β is an element of a principal subfield and we would like to bound the size of b_{i}. In the following we need the complex embeddings and some norms of algebraic numbers.

Definition 17. Let K = ℚ(α) be a number field of degree n and f be the minimal polynomial of α. Then we denote by ϕ_{1}, …, ϕ_{n} : K → ℂ, α ↦ α_{i} the n complex embeddings, where α_{1}, …, α_{n} are the complex roots of f. We assume that α_{1}, …, α_{r_{1}} are real and the complex roots are ordered such that α_{r_{1}+i} = ᾱ_{r_{1}+r_{2}+i} for 1 ≤ i ≤ r_{2}.

For β ∈ K we define the norms

∥β∥_{1} := ∑_{i=1}^{n} |ϕ_{i}(β)| and ∥β∥_{2} := \sqrt{∑_{i=1}^{n} |ϕ_{i}(β)|^{2}}.

Note the well known estimates:

∥β∥_{2} ≤ ∥β∥_{1} ≤ \sqrt{n}∥β∥_{2}.

We are able to give the promised bounds.

Lemma 18. Let β be given as in (5) with coefficient vector b := (b_{0}, …, b_{n−1}). Then we have ∥b∥_{2} ≤ n∥β∥_{1}∥f∥_{2} ≤ n^{1.5}∥β∥_{2}∥f∥_{2}.

Proof. Let h(x) := ∑_{i=0}^{n−1} b_{i}x^{i}. Let α_{i} := ϕ_{i}(α) and β_{i} := ϕ_{i}(β), then we get: h(α_{i}) = β_{i}f′(α_{i}) for 1 ≤ i ≤ n. Using Lagrange interpolation we get:

h(x) = ∑_{i=1}^{n} β_{i}f′(α_{i})\frac{f(x)/(x − α_{i})}{f′(α_{i})} = ∑_{i=1}^{n} β_{i} \frac{f(x)}{x − α_{i}} .

Now:

∥b∥_{2} = ∥h∥_{2} = ∑_{i=1}^{n} |β_{i}|∥f/(x − α_{i})∥_{2}

≤ max_{i} ∥f/(x − α_{i})∥_{2} ∑_{i=1}^{n} |β_{i}| ≤ n∥f∥_{2}∥β∥_{1},

∥f/(x−α_{i})∥_{2} ≤ n∥f∥_{2} is proved in [18, cor4.7]. The second estimate follows then trivially from ∥ · ∥_{1} ≤ \sqrt{n} ∥ · ∥_{2}. □

Now our goal is the following. Let L be a principal subfield of degree m which we would like to compute. We want to find a ℚ-basis of L represented in our \frac{1}{f′(α)}ℤ[α]_{<n}–basis. Note that O_{L}^{∗} ⊆ O_{K}^{∗} ⊆ \frac{1}{f′(α)} · ℤ[α]_{<n}. In order to apply Lemma 18 we need to bound ∥β_{i}∥_{2} for m linearly independent elements β_{1}, …, β_{m} ∈ L. We will use the following theorem.

Theorem 19 (Banaszczyk). Let Λ ⊂ ℝ^{m} be a lattice and denote by Λ^{∗} := {y ∈ ℝ^{m} | ∀x ∈ Λ : ⟨x, y⟩ ∈ ℤ} the dual lattice. Furthermore denote by λ_{i}, λ_{i}^{∗} the i-th successive minima of Λ, Λ^{∗}, respectively. Then λ_{i}λ_{m+1−i}^{∗} ≤ m for 1 ≤ i ≤ m.

The proof can be found in [1, Theorem 2.1]. In our application λ_{1} = \sqrt{m}, so we get the upper bound λ_{m}^{∗} ≤ \sqrt{m}. There are canonical ways to map number fields to lattices, but we have the slight problem that the bilinear form L × L → ℚ, (x, y) ↦ Tr(xy) is not positive definite, if L has non-real embeddings. We assume the same order of the complex embeddings of L as in Definition 17, so we have m = r_{1} + 2r_{2}. Defining γ_{i} = ϕ_{i}(γ) and δ_{i} = ϕ_{i}(δ) we get:

Tr(γδ) = ∑_{i=1}^{m} γ_{i}δ_{i}.

The corresponding scalar product looks like:

⟨γ, δ⟩ := ∑_{i=1}^{m} γ_{i}δ̄_{i}.

For totally real number fields L those two notions coincide. The dual lattice equals O_{L}^{∗} and we can apply Theorem 19 directly to get the desired bounds. First we introduce the canonical real lattice Λ := Ψ(O_{L}) ⊆ ℝ^{m} associated to ⟨γ, δ⟩ via

Ψ : L → ℝ^{m},  (6)

β ↦ (β_{1}, …, β_{r_{1}}, \sqrt{2}ℜ(β_{r_{1}+1}), …, \sqrt{2}ℜ(β_{r_{1}+r_{2}}),

\sqrt{2}ℑ(β_{r_{1}+1}), …, \sqrt{2}ℑ(β_{r_{1}+r_{2}})). Note that now the standard scalar product of ℝ^{m} coincides with the (complex) scalar product defined above. This is the reason for the weight \sqrt{2} in the above definition. Denote by ⟨·, ·⟩_{1} the standard scalar product of ℝ^{m}. Furthermore denote by

⟨x, y⟩_{2} := ∑_{i=1}^{r_{1}+r_{2}} x_{i}y_{i} − ∑_{i=r_{1}+r_{2}+1}^{m} x_{i}y_{i}.

Then we have

⟨γ, δ⟩ = ⟨Ψ(γ), Ψ(δ)⟩_{1} and Tr(γδ) = ⟨Ψ(γ), Ψ(δ)⟩_{2}.

Now we are able to compare our two dual objects, the dual lattice Λ^{∗} of Λ corresponding to ⟨·, ·⟩_{1} and the codifferent.

Lemma 20. Using the above notations. Then θ : ℝ^{m} → ℝ^{m},

(x_{1}, …, x_{m}) ↦ (x_{1}, …, x_{r_{1}+r_{2}}, −x_{r_{1}+r_{2}+1}, …, −x_{m})

induces an isomorphism Λ^{∗} → Ψ(O_{L}^{∗}) of ℤ–modules.

Proof. θ is linear and has the property

⟨x, y⟩_{1} = ⟨x, θ(y)⟩_{2} for all x, y ∈ ℝ^{m}.

We need to show that θ(Λ^{∗}) = Ψ(O_{L}). Note that θ^{2} is the identity and therefore this is equivalent to θ(Ψ(O_{L})) = Λ^{∗}. Denote by ω_{1}, …, ω_{m} a ℤ–basis of O_{L}. Then Λ = ℤΨ(ω_{1}) + … + ℤΨ(ω_{m}). Choose γ ∈ O_{L}^{∗} arbitrarily. Then Tr(ω_{i}γ) ∈ ℤ for 1 ≤ i ≤ m and therefore

⟨Ψ(ω_{i}), θ(Ψ(γ))⟩_{1} = ⟨Ψ(ω_{i}), Ψ(γ))⟩_{2} = Tr(ω_{i}γ) ∈ ℤ.

Therefore θ(Ψ(γ)) ∈ Λ^{∗} and we have shown θ(Ψ(O_{L}^{∗})) ⊆ Λ^{∗}. Denote by τ_{1}, …, τ_{m} ∈ O_{L}^{∗} the dual basis of ω_{1}, …, ω_{m}. Because of duality (e.g. see [17, Proof of Prop. 4.14]) we know that disc(τ_{1}, …, τ_{m}) = disc(ω_{1}, …, ω_{m})^{−1} = d_{L}^{−1}. Furthermore θ(Ψ(τ_{i})) (1 ≤ i ≤ m) are linearly independent elements of Λ^{∗} and the discriminant of the ℤ–module generated by those elements is |d_{L}^{−1}| since the corresponding determinants differ by a power of −1 because we have to consider the twists between our two bilinear forms. Therefore we know a subset θ(Ψ(O_{L}^{∗})) ⊆ Λ^{∗} which has the correct lattice discriminant. Therefore we get equality. □

Now we are able to get our bound by applying Lemma 20 and Theorem 19.

Lemma 21. Let L be a number field of degree m. Then O_{L}^{∗} contains m ℚ–linearly independent elements γ_{1}, …, γ_{m} such that ∥γ_{i}∥_{2} ≤ \sqrt{m} for 1 ≤ i ≤ m.

Proof. As before let Λ := Ψ(O_{L}), where Ψ is defined in (6). Now we claim that the first successive mimimum λ_{1} equals \sqrt{m} by taking the element Ψ(1). Let γ ∈ O_{L}. Then

1 ≤ |Norm(γ)| = (∏_{i=1}^{m} |γ_{i}|^{2})^{1/2} ≤ (\frac{∑_{i=1}^{m} |γ_{i}|^{2}}{m} )^{m/2}

= (\frac{⟨Ψ(γ), Ψ(γ)⟩_{1}}{m} )^{m/2} ,

19 where the inequality is the one between geometric and arithmetic means. Now we get that ⟨Ψ(γ), Ψ(γ)⟩_{1} ≥ m which finishes the proof that λ_{1} = \sqrt{m}.

Preliminary version – 3 June 2012

Applying Theorem 19 we find m linearly independent elements y_{1}, …, y_{m} ∈ Λ^{∗} with euclidean length bounded by m/\sqrt{m} = \sqrt{m}. By using Lemma 20 we find elements θ(y_{i}) ∈ Ψ(O_{L}^{∗}) which have the same euclidean length. By choosing γ_{i} := Ψ^{−1}(θ(y_{i})) for 1 ≤ i ≤ m we finish our proof. □

Now we are able to prove our theorem. Note that the field L takes the role of the principal subfield L_{i} in the statement.

Proof. [of Theorem 12] Using Lemma 21 we find m_{i} linearly independent elements β_{j} in O_{L}^{∗} with 2-norm bounded by \sqrt{m_{i}}. When we interpret those elements in K, we get n/m_{i} copies of the complex embeddings, which gives that the 2-norm as elements of K is bounded by \sqrt{n}. Now apply Lemma 18. □

4. CPU time in Magma

The aim of this section is to compare our algorithm with the state of the art, to be precise, to compare it with [12]. We use the computer algebra system Magma for this comparison, as it has an implementation of both [12] and the algorithm in this paper.

The algorithm from [12] uses a combinatorial approach in order to find block systems corresponding to subfields. Each combination is processed very quickly, however, it is possible that exponentially many combinations need to be tried. The number of combinations depends on the cycle structures of the elements of the Galois group, i.e., it depends on the number of factors of f mod prime numbers, and the degrees of these factors.

To keep the table below simple, we do not list these cycle structures, but list only r, n and l_{f}. Here r is the minimal number of monic irreducible factors of f in F_{p}[x] (taken over all p that do not divide the leading coefficient or the discriminant of f). The degree of f is denoted by n, while l_{f} denotes log_{10}(||f||_{2}).

Note that these polynomials are not chosen at random. Most polynomials have large Galois groups, and consequently, have small r. For small r, [12] is much faster than the algorithm in this paper (however, if r is large, then [12] becomes exponentially slow, and our algorithm will be faster). To get a good comparison, we constructed examples with a variety of values for r and n. To ensure that r is not very small, these examples are chosen to have Galois groups whose orders are not much greater than n. The table lists the CPU time (in seconds) for [12] and for the algorithm in this paper. Those marked “N/F” are computations that did not (yet) finish at the time of writing, and have been running for days, while “N/A” means not attempted.

r n  l_{f}  [12] HKN r  n  l_{f}  [12]  HKN
6 36 5.4  1.3 30.7 13 75 32.4 228796.3 2911.2
7 75 10.6  75.2 453.2 14 81 13.1 16281.8 1849.3
8 48 4.4  15.5 101.2 15 81 14.0 31478.1 1644.1
8 56 11.2 3161.2 192.2 16 32 5.5  N/F  170.8
10 50 9.3 212.6 95.3 16 64 8.3  N/F  609.1
11 60 11.1 262.9 458.0 16 80 16.6  N/A 4195.9
12 60 15.0 5746.7 746.2 16 96 10.0  N/A 5494.3
12 64 10.5 277.4 417.1 18 90 21.5  N/A 4053.2
12 72 4.3 9575.4 785.9 20 100 28.2  N/A 43376.6

Observe that [12] was faster on all examples with r < 8, as well as some with r ≤ 12, while our algorithm (the columns HKN) was faster on all examples with r > 12, as well as some with r ≥ 8. We list two of the examples here: r = 12, n = 72, f = x^{72} + 4x^{68} + 62x^{64} + 346x^{60} + 2077x^{56} + 3367x^{52} + 6647x^{48} + 6536x^{44} + 6634x^{40} + 5773x^{36} + 6634x^{32} + 6536x^{28} + 6647x^{24} + 3367x^{20} + 2077x^{16} + 346x^{12} + 62x^{8} + 4x^{4} + 1. r = 16, n = 32, f = x^{32} − 161x^{28} + 25345x^{24} − 92414x^{20} + 305854x^{16} − 92414x^{12} + 25345x^{8} − 161x^{4} + 1.

The remaining f’s can be copied from http://www.math.fsu.edu/~hoeij/subfields/

where some other details (Magma commands, memory usage, processor) are given as well.

References

[1] W. Banaszczyk. New bounds in some transference theorems in the geometry of number. Math. Ann, 296:625–635, 1993.

[2] Bernhard Beckermann and George Labahn. A uniform approach for the fast computation of matrix-type pade approximants. SIAM J. Matrix Anal. Appl., 15:804–823, July 1994.

[3] Karim Belabas, Mark van Hoeij, Jürgen Klüners, and Allan Steel. Factoring polynomials over global fields. J. Théor. Nombres Bordeaux, 21:15–39, 2009.

[4] D. Casperson and J. McKay. Symmetric functions, m-sets, and Galois groups. Math. Comput., 63:749–757, 1994.

[5] Henri Cohen and Francisco Diaz y Diaz. A polynomial reduction algorithm. Séminaire de Théorie des Nombres de Bordeaux 2, 3:351–360, 1991.

[6] Xavier Dahan and Éric Schost. Sharp estimates for triangular sets. In Proceedings of the 2004 international symposium on Symbolic and algebraic computation, ISSAC ’04, pages 103–110, New York, NY, USA, 2004. ACM.

[7] H. Derksen. An algorithm to compute generalized Padé-Hermite forms. Preprint, Catholic University Nijmegen, 1994.

[8] J Dixon. Computing subfields in algebraic number fields. J. Austral. Math. Soc. Series A, 49:434–448, 1990.

[9] W. Hart. Flint. open-source C-library http://www.flintlib.org.

[10] Mark van Hoeij. Factoring polynomials and the knapsack problem. J. Number Theory, 95:167–189, 2002.

[11] A. Hulpke. Block systems of a Galois group. Exp. Math., 4(1):1–9, 1995.

[12] J. Klüners. Über die Berechnung von Automorphismen und Teilkörpern algebraischer Zahlkörper. Dissertation, Technische Universität Berlin, 1997.

[13] J. Klüners. On computing subfields - a detailed description of the algorithm. Journal de Théorie des Nombres de Bordeaux, 10:243–271, 1998.

[14] D. Lazard and A. Valibouze. Computing subfields: Reverse of the primitive element problem. In A. Galligo F. Eyssete, editor, MEGA-92, Computational algebraic geometry, volume 109, pages 163–176. Birkhäuser, Boston, 1993.

[15] A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515–534, 1982.

[16] Michael B. Monagan, Keith O. Geddes, K. Michael Heal, George Labahn, Stefan M. Vorkoetter, James McCarron, and Paul DeMarco. Maple 10 Programming Guide. Maplesoft, Waterloo ON, Canada, 2005.

[17] Władisław Narkiewicz. Elementary and Analytic Theory of Algebraic Numbers. Springer, 2004.

[18] M. van Hoeij and V. Pal. Isomorphisms of algebraic number fields. arXiv:1012.0096v2, 2010.

[19] Mark van Hoeij and Andrew Novocin. Gradual sub-lattice reduction and a new complexity for factoring polynomials. In LATIN, pages 539–553, 2010.

[20] G. Villard. Certification of the QR factor R, and of lattice basis reducedness. In Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation (ISSAC’07), pages 361–368, 2007.