On the Complexity of Computing Units in a Number Field

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

                {arvind,ppk}@imsc.res.in

April 4, 2011

Abstract

Given an algebraic number field K, such that [K : ℚ] is constant, we show that the problem of computing the units group O_{K}^{∗} is in the complexity class SPP. As a consequence, we show that principal ideal testing for an ideal in O_{K} is in SPP. Furthermore, assuming the GRH, the class number of K, and a presentation for the class group of K can also be computed in SPP. A corollary of our result is that solving PELL′S EQUATION, recently shown by Hallgren [12] to have a quantum polynomial-time algorithm, is also in SPP.

1 Introduction

The computation of units in a number field is a fundamental problem in computational number theory and is considered an important algorithmic task in the area. It has been the subject of considerable research in the last two decades and several algorithmic results as well some complexity-theoretic results have been pioneered. Much of this research (e.g. [17, 7, 6]) is based on ideas developed by Buchmann in [3, 4].

In the present paper we are interested in the following problems in computational number theory, from a structural complexity perspective. Let K be a number field given by its minimal polynomial.

1. Computing a fundamental system of units that generates the units group O_{K}^{∗} in O_{K}.

2. Computing a presentation (i.e. a set of generators and relators) for the class group Cl(K) of K and the class number h(K).

3. Testing if a given ideal A of O_{K} is a principal ideal.

From a purely complexity theory perspective, earlier research on these problems was by McCurley [16], and Buchmann and Williams [7]. This was followed by the Thiel’s work [17] where it is shown that the problem of principal ideal testing is in NP. Furthermore, assuming the Generalized Riemann Hypothesis, it is shown in [17] that principal ideal testing and verifying the class number are in NP ∩ coNP.

Our interest to further investigate the computational complexity of these problems is motivated by the recent exciting work of Hallgren [12] where it is shown that computing a solution to PELL′S EQUATION is in BQP (the class of problems that have polynomial-time quantum algorithms). Hallgren’s main result is that given a quadratic number field K, its regulator R_{K} can be computed by a polynomial-time quantum algorithm. The regulator is the solution to PELL′S EQUATION. For quadratic fields, Hallgren also indicates how principal ideal testing and computing the class group are problems in BQP. Hallgren’s results, however, do not appear to generalize to number fields of larger degree. Thus, it remains an open problem if these problems are in BQP for number fields of degree more than two.

How does the class BQP relate to standard complexity classes defined using classical Turing machines? Fortnow and Rogers [11] show that BQP is contained in the counting complexity class AWPP (definitions in Section 1.1). Thus, in a sense, we can think of BQP as a counting class. Counting classes is an area of research in structural complexity theory motivated by Valiant’s class #P (see e.g. [10]). Intuitively, counting complexity classes are defined by suitable restrictions on the number of accepting and rejecting paths in nondeterministic Turing machines. In the rest of this section we give formal definitions followed by a summary of our results.

1.1 SPP and other Counting Complexity Classes

Let Σ = {0, 1} be the finite alphabet. Let lg denote logarithm to base 2. Let FP denote the class of polynomial-time computable functions and NP denotes all languages accepted by polynomial-time nondeterministic Turing machines. Let ℤ denote integers. A function f : Σ^{∗} → ℤ is said to be gap-definable if there is an NP machine M (i.e. a nondeterministic polynomial time Turing machine M) such that, for each x ∈ Σ^{∗}, f(x) is the difference between the number of accepting paths and the number of rejecting paths of M on input x. Let GapP denote the class of gap-definable functions [10]. For each NP machine M let gap_{M} denote the GapP function defined by it.

A language L is in UP if there is an NP machine M accepting L such that M has at most one accepting path on any input. The class UP was defined by Valiant and it captures the complexity of 1-way functions. The complexity class SPP is defined as follows. A language L is in SPP if there is an NP machine M such that x ∈ L implies gap_{M}(x) = 1 and x ∉ L implies gap_{M}(x) = 0. In this case we say that L is accepted by the machine M. Note that the class SPP is essentially a GapP analogue of the class UP and UP ⊆ SPP.

We say that f is in GapP^{A}, for oracle A ∈ Σ^{∗}, if there is an NP^{A} machine M^{A} such that, for each x ∈ Σ^{∗}, f(x) is the difference between the number of accepting paths and the number of rejecting paths of M^{A} on input x. For an oracle A, we can now define the class SPP^{A}.

The class PP is defined as follows: a language L is in PP if there is an f ∈ GapP such that x ∈ L if and only if f(x) > 0. PP is a hard counting class: by Toda’s theorem we know that PH ⊆ P^{PP}. We say that a language A ∈ Σ^{∗} is low for PP if PP^{A} = PP. Characterizing the class of languages low for PP is an intriguing open question in structural complexity.

In [10] it is shown that every language in SPP is low for PP. Additionally, SPP has nice closure properties [10]: P^{SPP} = SPP^{SPP} = SPP. Another class that is low for PP [14] is BPP (the class of languages with polynomial-time randomized algorithms with error probability bounded by, say, 1/3.) Subsequently, the complexity class AWPP was introduced^{1} in [9]. The class AWPP generalizes both BPP and SPP, and it is shown that every language in AWPP is low for PP. To complete the picture relating these classes, Fortnow and Rogers in [11] show that BQP is contained in AWPP. It is interesting to note that NP ∩ coNP is not known to be low for PP. Here is a diagram that shows the containments between the complexity classes discussed here.

[figure: AWPP; SPP; BQP; UP; BPP; P] .

Although no containment is known between BQP and SPP, it is interesting to compare these classes in terms of natural problems they contain. Important problems known to be in SPP are Graph Isomorphism and the hidden subgroup problem for permutation groups [1]. These problems have resisted efficient deterministic or randomized algorithms, but are considered potential candidates for quantum algorithms. On the other hand, FP^{SPP} contains Integer Factoring and Discrete Log that have polynomial-time quantum algorithms.^{2}

1.2 The New Results and the Methods

We now state the main results of the paper.

1For the definition see [9].

2In fact, these problems are even in FP^{UP}. Also, as P^{SPP} = SPP, notice that the class FP^{SPP} is essentially SPP: for f ∈ FP^{SPP} and input x, the bits of f(x) can be computed in SPP. A similar closure property holds for BQP.

(a) Given a number field K (by its minimal polynomial as input), the problem of computing a fundamental system of units is in FP^{SPP}, assuming that K is a constant degree extension of ℚ. As a consequence finding the regulator of K upto polynomially many bits of approximation is also in FP^{SPP}. As a corollary the PELL′S EQUATION problem is in FP^{SPP}.

(b) Given a constant-degree number field K and an ideal A of the ring O_{K}, testing if A is a principal ideal is in SPP.

(c) Given a constant-degree number field K (by its minimal polynomial as input), the problem of computing the class group of K (by finding a generator-relator presentation for it) and finding the class number of K is in FP^{SPP}, assuming GRH.

In particular, PELL′S EQUATION is also in FP^{SPP}. Thus, we add to the list of natural problems that are in both SPP and BQP. A brief outline of the methods used to show the above results is given below.

Let M be an oracle Turing machine. For a language A in NP, we say that M^{A} makes UP-like queries to A if there is an NP machine N accepting A such that on all inputs x, M^{A}(x) makes only such queries y for which N(y) has at most one accepting path. Effectively, it is like M having access to a UP oracle. We state a useful variant of a result from [15].

Theorem 1.1 ([15]). Let M be a nondeterministic polynomial-time oracle machine with oracle A ∈ NP such that M^{A} makes UP-like queries to A then the function h(x) = gap_{M^{A}}(x) is in GapP.

Next, we recall an important property of the class SPP shown in [10].

Theorem 1.2 ([10]). If L is in SPP^{A} for some oracle A ∈ SPP then L ∈ SPP. I.e. SPP^{SPP} = SPP.

The following lemma, which is a straightforward consequence of Theorem 1.1 and of Theorem 1.2, is in a form useful for this paper.

Lemma 1.3.

• Suppose L is in SPP^{A} accepted by the nondeterministic polynomial-time oracle machine M^{A} with oracle A ∈ NP (i.e. x ∈ L implies that gap_{M^{A}}(x) = 1, and x ∉ L implies that gap_{M^{A}}(x) = 0), such that the machine M^{A} makes UP-like queries to A, then L is in SPP.

• Suppose a function f : Σ^{∗} → Σ^{∗} is in FP^{A} (i.e. f is computed by a polynomial-time oracle transducer M^{A}) where A ∈ NP, such that the machine M^{A} makes UP-like queries to A, then f is in FP^{SPP}.

Lemma 1.3 is a crucial tool in obtaining the FP^{SPP} upper bounds. For computing a fundamental system of units in FP^{SPP} we first show that a bound B ∈ ℚ can be computed in FP^{SPP} such that the regulator R_{K} of K lies between B and 2B. Once such a bound is computed, we again apply an algorithm based on Lemma 1.3 to compute a canonical fundamental system of units in FP^{SPP}. This notion of canonical fundamental system of units is developed and explained in Sections 2 and 3, where we show how to transform an arbitrary fundamental system of units to the canonical set.

Once we have the FP^{SPP} upper bound for computing fundamental units, we can design an SPP algorithm for principal ideal testing. If we assume the generalized Riemann hypothesis then, by a result of Bach [2], we can apply our SPP algorithm for principal ideal testing and give an FP^{SPP} algorithm for computing the class group Cl(K).

1.3 Comparison with previous results

As mentioned, Thiel [17] has shown that principal ideal testing is in NP. Thiel also shows, assuming the GRH, that principal ideal testing and verifying class number are in NP ∩ coNP. On the other hand, our results on principal ideal testing and computing a fundamental system of units are unconditional, but applicable to only number fields of constant degree. The FP^{SPP} upper bound for the class group problem depends on the GRH.

No containment relation is known between SPP and NP∩coNP or BQP and NP ∩ coNP. Furthermore, we remark here that NP ∩ coNP is not known to be low for PP. Thus, the results of Thiel [17] are incomparable to our results.

An important computational aspect in all our results is the notion of compact representation as explained by Thiel [17], based on Buchmann’s earlier papers [3, 4]. We need compact representations to succinctly express units as well as the generating element of a principal ideal in O_{K}.

2 Compact representation

Let K be a number field of degree n and let O be the ring of integer of K. Let D be the discriminant of K. For an element α ∈ K by N (α) we mean the norm N_{ℚ}^{K}(α). Without loss of generality we assume that the input to the algorithm is O presented as a ℤ-module with basis ω_{1}, … ω_{n} and constants c_{ijk} such that ω_{i}ω_{j} = ∑_{k} c_{ijk}ω_{k}. For, computing the maximal order from a given order is reducible to the problem of finding the square free part of an integer which can be done in FP^{SPP}, as factoring integers is in FP^{SPP}. By size of O we mean ∑ size(c_{ijk}). The constants c_{ijk} will be the called the explicit data for K.

Fractional ideals 𝔞 of O will be presented by giving a ℤ-basis for 𝔞. Let α_{i} = ∑_{j} a_{ij}ω_{j}, 1 ≤ i ≤ n, be a basis of 𝔞 then by HNF(𝔞) we mean the Hermite normal form of the matrix (a_{ij}). Once ω_{i}’s are fixed, for every ideal 𝔞, HNF(𝔞) is unique. Since the Hermite normal form of a matrix can be computed in polynomial time this gives a polynomial time algorithm for testing whether two ideals are equal.

Let σ_{1}, …, σ_{r} be all the r real embeddings and σ_{r+1}, \overline{σ}_{r+1}, …, σ_{r+s}, \overline{σ}_{r+s} be all the 2s complex embeddings of K. Define the r + s absolute values on K as follows.

|α|_{i} = \{ \begin{matrix}|σ_{i}(α)| & if 1 ≤ i ≤ r \\ |σ_{i}(α)|^{2} & if r + 1 ≤ i ≤ r + s \end{matrix}

For α ∈ K, by height of α, denoted by H(α), we mean max{|α|_{i} : 1 ≤ i ≤ r + s}.

Lemma 2.1. Given O, we have H(ω_{i}) ≤ n2^{size(O)}, and lg D ≤ n(2 lg n + size(O)).

Proof. Let l be such that for 1 ≤ i ≤ n H(ω_{l}) ≥ H(ω_{i}). Then we have

H(ω_{l}ω_{l}) ≤ ∑_{k} |c_{llk}| H(ω_{k}) ≤ n2^{size(O)}H(ω_{l}).

Hence H(ω_{l}) ≤ n2^{size(O)}. Also since D = ∑_{g∈S_{n}} ∏_{i=1}^{n} σ_{g(i)}(ω_{i}) we have D ≤ n!.H(ω_{l})^{n}.

Fix a basis for O. For any α ∈ O there is a unique set of integers a_{1}, …, a_{n} such that α = ∑ a_{i}ω_{i}. By giving the vector of integers a_{i}’s the algebraic integer α is completely specified. Following [17] this is the standard representation of α which is unique for a fixed ℤ-basis for O. The size of α in standard representation is size_{s}(α) = ∑ size(a_{i}).

The following result from [17] describes a compact representation of algebraic integers.

Theorem 2.2. For α ∈ O there exists k ≤ lg(lg(D) + (n − 1) lg H (α)) + 2 and γ, α_{i} ∈ O and d_{i} ∈ ℤ, 1 ≤ i ≤ k, with H (γ) ≤ N (α)^{2/n}, H (α_{i}) ≤ D^{\frac{3}{4} (m+2)} and 0 < d_{i} ≤ \sqrt{D} such that

α = γ ∏_{i=1}^{k} (\frac{α_{i}}{d_{i}} )^{2^{k−i}} .

Moreover, for 1 ≤ j ≤ k the ideal ∏_{i=1}^{j} (\frac{α_{i}}{d_{i}} )^{2^{k−i}} O is a reduced ideal.

A product of this form can be presented as a tuple ⟨k, γ, ⟨α_{i}, d_{i}⟩_{i=1}^{k}⟩. For a given compact representation of α the size of the representation is the sum of the sizes of the integers d_{i} and the sizes of algebraic integers γ and α_{i}’s in their standard representation. Compact representations are not unique for a given α even for a given ℤ-basis. Let size_{c}(α) denotes the maximum of sizes of all compact representation of α. Using Lemma 2.1 and [17, Corollary 15] we have the following theorem on compact representations.

Theorem 2.3. [17] For nonzero α ∈ O

size_{s}(α) ≤ (n lg H (α) · size(O))^{O(1)} .
size_{c}(α) ≤ (n^{2} lg^{2}(n) · size(O). lg (size(O)) · N (α) · lg lg H(α))^{O(1)}

Furthermore, given the compact representation ⟨k, γ, ⟨α_{i}, d_{i}⟩_{i=1}^{k}⟩ of α, there is a polynomial time algorithm that computes the Hermite Normal Form for the ideal αO.

Conversely the following proposition from [17] gives a bound on the height of the algebraic number based on the size of their representation.

Proposition 2.4. Let α be any algebraic integer of K, a number field of discriminant D. Then we have:

1. For all j, H (α) ≤ n^{2}2^{size_{s}(α)+size(O)}.

2. For all j, ln H (α) ≤ ln N (α) + n^{3} lg n · size_{c}(α) · size(O) · 2^{size_{c}α}.

3 Minimal bases for lattices

For a set of linearly independent vectors a_{1}, a_{2}, … a_{n} let a_{1}^{∗}, a_{2}^{∗}, …, a_{n}^{∗} denote the corresponding GSO (Gram-Schmidt) basis. Given a lattice Λ = ∑_{i=1}^{n} ℤb_{i} in ℝ^{n} with basis b_{i} = ∑_{j=1}^{n} b_{ij}e_{i}. Let M = (μ_{ij}) be the matrix that transforms the GSO basis given by b_{i}^{∗}’s to the basis given by the b_{i}’s. We say that the basis is proper if for every i < j ≤ n we have −\frac{1}{2} ≤ μ_{ij} < \frac{1}{2}. The following holds for any lattice.

Lemma 3.1. Given a lattice Λ with basis a_{1}, a_{2}, …, a_{n}, a new basis b_{1}, b_{2}, … b_{n} can be computed in polynomial time such that b_{i}’s form a proper basis and b_{i}^{∗} = a_{i}^{∗} (i.e. the GSO basis of both vectors are the same).

Proof. Here is the algorithm.

b_{1} := a_{1}; 1 for i = 2 to n do

Let a_{i} = a_{i}^{∗} + ∑_{j=1}^{i−1} μ_{ij}a_{j}^{∗};

b_{i} := a_{i};

2 for j = i − 1 downto 1 do

if μ_{ij} ≥ \frac{1}{2} ∨ μ_{ij} < −\frac{1}{2} then

Let n be the nearest integer to μ_{ij};

3 b_{i} := b_{i} − nb_{j};

end end

end

The invariant for the loop in step 1 is −\frac{1}{2} ≤ μ_{kj} < \frac{1}{2} for all 1 ≤ j < k ≤ i−1. If the invariant is violated at i for some j then the loop in step 2 fixes it. For a given k note that step 3 does not affect any of the μ_{ij} for j > k. It is also clear that step 3 does not affect the GSO of the basis.

Given the vector space W = U ⊕ V such that U and V are orthogonal, for w ∈ W, if w = u + v, u ∈ U and v ∈ V, then w/U denotes the vector v (i.e. the component of w orthogonal to the space U). For a lattice Λ, Λ/V is the lattice {v/V : v ∈ Λ}. If b_{1}, b_{2} … b_{n} forms a basis for Λ then any vector of Λ/V can be expressed as an integer linear combination of b_{i}/V ’s.

Given a lattice Λ, a basis b_{1}, b_{2}, …, b_{n} is called a minimal basis if it is proper and it satisfies the following conditions:

1. b_{1} is a ℓ_{1}-shortest vector in Λ.

2. For all i, if V_{i−1} is the span of the vectors b_{1}, b_{2}, …, b_{i−1} then b_{i}/V_{i−1} is the vector of least ℓ_{1} norm in the lattice Λ/V_{i−1}.

To find a canonical basis for the lattice Λ one can define a total order on the set of all minimal basis of Λ and choose the least basis under that order. For two vectors u = ∑ u_{i}e_{i} and v = ∑ v_{i}e_{i}, u ≺ v if ∥ u ∥_{1} < ∥ v ∥_{1} or if ∥ u ∥_{1} = ∥ v ∥_{1} then there is an 1 ≤ i ≤ n such that u_{j} = v_{j} for all 1 ≤ j < i and u_{i} < v_{i}.

Consider two minimal basis A = {a_{i}}_{i=1}^{n} and B = {b_{i}}_{i=1}^{n} for the lattice Λ. Let A^{∗} = {a_{i}^{∗}}_{i=1}^{n} and B^{∗} = {b_{i}^{∗}}_{i=1}^{n} be their GSO basis respectively. For two such minimal basis A ≺ B if there is an i such that for all j < i, a_{j} = b_{j} and a_{i}^{∗} ≺ b_{i}^{∗}.

Theorem 3.2. On the set of minimal bases, the relation ≺ forms a total order.

Proof. Suppose ≺ does not form a total order then we have two minimal basis A and B and an index i such that a_{j} = b_{j} for all j < i and a_{i}^{∗} = b_{i}^{∗} yet a_{i} ≠ b_{i}. Expressing a_{i} and b_{i} in the respective GSO basis we have

a_{i} = ∑_{j=1}^{i} α_{j}a_{j}^{∗} b_{i} = ∑_{j=1}^{i} β_{j}b_{j}^{∗}.

Let k be the index such that for all j > k, α_{j} = β_{j} and α_{k} ≠ β_{k} . Clearly k < i. Since the basis A and B are proper we have α_{j} and β_{j} lie in the interval [−\frac{1}{2}, \frac{1}{2}). Consider the vector u = a_{i} − b_{i}. Since a_{j}^{∗} = b_{j}^{∗} for all 1 ≤ j ≤ i we have u = (α_{k} −β_{k})a_{k}^{∗} +u′ where u′ lies in the vector space V_{k−1} that is spanned by {a_{j}}_{j=1}^{k−1}. But then ∥ u/V_{k−1} ∥_{1} = |α_{k} − β_{k}| ∥ a_{k}^{∗} ∥_{1} < ∥ a_{k}/V_{k−1} ∥_{1} which contradicts the fact that A and B are minimal.

Given an algorithm for finding the ≺-least vector of a lattice, Theorem 3.2 suggests the following algorithm for finding ≺-minimum basis for a lattice Λ.

To complete this section we give an algorithm for finding the ≺-minimum element of a lattice Λ. We apply Lenstra’s algorithm for integer linear programming [13] that runs in polynomial time if the number of variables is constant.

Lemma 3.3. If Λ ⊂ ℝ^{n} is a lattice of rank r then assuming n is a constant there is a polynomial time algorithm for finding the ≺-minimum element of Λ.

Proof. Let Λ = ℤ[b_{1}, b_{2}, …, b_{r}] where the basis b_{i}’s are given by b_{i} = ∑ b_{ij}e_{j}. The algorithm goes in two steps. The first step is to find a vector with least ℓ_{1} norm. In the subsequent steps this solution is refined further till we get the ≺-minimum vector.

Input: A set of linearly independent vectors b_{1}, b_{2}, …, b_{n}. Output: The ≺-minimum basis for Λ. Let Λ be the lattice ℤ[b_{1}, b_{2}, …, b_{n}]; Find the ≺-least element u of the lattice Λ; Let {u_{k}}_{k=1}^{n} be a basis for Λ such that u_{1} = u; Let u_{k}^{∗} = u_{k} − \frac{⟨u,u_{k}⟩}{⟨u,u⟩}u 1 < k ≤ n; Find the ≺-minimum basis for the lattice Λ^{∗} generated by {u_{k}^{∗}}_{k=2}^{n} recursively; Let this basis be {b′_{i} = ∑_{j=2}^{n} x_{ij}u_{j}^{∗}}_{i=2}^{n}; Consider the basis {a_{i}}_{i=1}^{n} defined by a_{1} = u and a_{i} = ∑_{j=2}^{n} x_{ij}u_{j}, 2 ≤ i ≤ n; Converting this basis to a proper basis using Lemma 3.1 completes that algorithm;

Algorithm 1: Computing ≺-minimal basis

To find a vector with least ℓ_{1} norm we have the following integer programming problem in r variables x_{1}, x_{2}, …, x_{r}: Minimize the expression f(x) = ∑_{i=1}^{n} | ∑_{j=1}^{r} b_{ji}x_{j}| given f(x) > 0. Although this is not an integer linear programming problem one can use the algorithm of Lenstra here as follows: For the 2^{n} different vector c ∈ {−1, 1}^{n}, solve the following integer linear programming problem and pick the best among those 2^{n} different solutions.

Minimize ∑_{i=1}^{r}(∑_{j=1}^{n} b_{ij}c_{j})x_{i},

under the constraints

∑_{i=1}^{r}(∑_{j=1}^{n} b_{ij}c_{j})x_{i} > 0  (1)

0 ≤ c_{j} ∑_{i=1}^{r} b_{ij}x_{i} ≤ B, 1 ≤ j ≤ n.  (2)

The first constraints expresses the fact that the solution should be nonzero. The second set of constraints express the fact that we are choosing the right c_{i}’s.

The B in the equation is an upper bound on the ℓ_{∞} of the shortest vector. The ℓ_{1} norm of any particular vector in the basis will be a suitable value for B.

Having obtained a solution for the ℓ_{1}-shortest vector say u one has to refine the solution to get a ≺-minimum solution. Let u_{j} denote a ℓ_{1}-shortest vector which agrees with the ≺-minimum vector on all coordinates less than or equal to j, then u_{n} is the desired solution. Let u_{0} = u. Having got the vector u_{j} to compute u_{j+1} we minimize ∑_{i=1}^{r} x_{i}b_{ij+1} under the constraints ∥ ∑_{i=1}^{r} x_{i}b_{i} ∥_{1} = ∥ u_{j} ∥_{1} and ∑_{i=1}^{r} x_{i}b_{ik} = u_{jk} for 1 ≤ k ≤ j. Here u_{jk} denotes the component of u_{j} in the direction e_{k}. One can use the same trick as before to convert this to an integer linear programming problem and use Lenstra’s algorithm. Since the dimension n is bounded, the running time is polynomial.

Combining Lemma 3.3 and algorithm 1 we have the following result.

Theorem 3.4. Given a lattice a basis {b_{i}}_{i=1}^{r} of a rank r lattice Λ ⊆ ℝ^{n} there is a polynomial time algorithm to compute the ≺-minimal basis of Λ assuming n to be a constant

4 Units of a number field

Let K be a number field of degree n and let O be the set of algebraic integers of K. If K has r real embeddings and 2s complex embeddings then by Dirichlet’s theorem (see, e.g. [8]) there exists a set of m = r + s − 1 units {ε_{i}}_{i=1}^{m}, called a fundamental system of units, such that every unit of O can be expressed as ζε_{1}^{x_{1}} … ε_{m}^{x_{m}}, x_{i} ∈ ℤ, where ζ is a root of unity in K. Consider the map Log : K ↦ ℝ^{m} defines as follows:

Log (α) = ⟨ln |α|_{1}, ln |α|_{2}, …, ln |α|_{m}⟩

From Dirichlet’s theorem it follows that the set Log (O^{∗}) is a lattice in ℝ^{m} with basis Log (ε_{i})_{i=1}^{m}. Often it is necessary to work with vectors in this lattice whose coordinates are in general irrationals. We will use rational approximations of these vectors instead.

An important algorithmic task that will be useful in the FP^{SPP} algorithm is to compute a canonical fundamental system of units from a given fundamental system of units U = {ε_{i}}_{i=1}^{m}. In this section we give a polynomial time algorithm for the above task assuming that the degree [K : ℚ] is constant. The next theorem is a re-statement of [17, Lemma 16] using the bound in Lemma 2.1.

Theorem 4.1. [17] There exists a fundamental system of units {ε_{i}}_{i=1}^{m} for O such that size_{c}(ε_{i}) = (n.size(O))^{O(1)} for all 1 ≤ i ≤ m.

Consider the fundamental system of units {η_{i}}_{i=1}^{m} that corresponds to ≺- minimal basis of the lattice Log (O^{∗}). We have the following observation.

Lemma 4.2. For all 1 ≤ i ≤ m, size_{c}(η_{i}) = (n.size(O))^{O(1)}.

Proof. The basis b_{i} = Log (η_{i}) is the ≺-minimal basis of Λ = Log (O^{∗}). Let b_{i}^{∗} denote the corresponding GSO basis and let V_{i} = Span{b_{i}}_{i=1}^{m}. Let {ε_{i}}_{i=1}^{m} be any fundamental system of units satisfying the condition in Theorem 4.1 then a_{i} = Log (ε_{i}) spans the lattice Λ. Without loss of generality we may assume that a_{i} ∉ V_{i}. Since b_{i}’s form the ≺-minimal basis of Λ we have ∥ b_{i}^{∗} ∥_{∞} ≤ ∥ b_{i}^{∗} ∥_{1} ≤ ∥ a_{i}/V_{i−1} ∥_{1} ≤ m ∥ a_{i} ∥_{∞}. Hence we have ∥ b_{i} ∥_{∞} ≤ ∥ b_{i}^{∗} ∥_{∞} + \frac{1}{2} ∑_{j=1}^{i−1} ∥ b_{j}^{∗} ∥ ≤ m.A.(i − 1)/2, where A is an upper bound on ∥ a_{i} ∥_{∞}. From Theorem 4.1 and Proposition 2.4 we have A ≤ (n · size(O) + 2^{size_{c}(ε_{i})})^{O(1)} where i is such that Log (ε_{i}) has the largest ℓ_{∞} norm. Hence for every i we have ln H (η_{i}) ≤ (n · size(O) + 2^{size_{c}(ε_{i})})^{O(1)}. Together with Theorem 2.3 we have the result.

We now describe how a canonical fundamental system of units can be computed given an arbitrary fundamental system of units. The following theorem, based on a remark in [17], will be useful.

Theorem 4.3. [17] Assuming that [K : ℚ] is constant, there is a polynomial time algorithm that takes as input a principal ideal 𝔞 = αO by its Hermite Normal Form and a good rational approximation for Log (α), and outputs a compact representation for ζα where ζ is a root of unity in K.

Remark 4.4. The point to note in the above theorem is that only Log (α) is given (as a rational approximation) and not the compact representation of α. Also notice that Log (α) is unique only upto multiplication by roots of unity in K. The theorem promises that one such element ζα, which depends only on HNF(𝔞) and Log (α), is computable in polynomial time.

Theorem 4.5. Assuming [K : ℚ] is a constant, there is a polynomial time deterministic algorithm that takes as input a fundamental system of units (as compact representations) and outputs another fundamental system of units {η_{i}}_{i=1}^{m} (as compact representations) corresponding to the ≺-minimal basis for Log (O^{∗}). Furthermore, {η_{i}}_{i=1}^{m} is canonical in the sense that it does not depend on the input fundamental system of units.

Proof. Given a fundamental system of units {ε_{i}}_{i=1}^{m} compute {Log (ε_{i})}_{i=1}^{m} to the desired approximation. Compute the ≺-minimal basis for the lattice generated by {Log (ε_{i})}_{i=1}^{m} using algorithm in Theorem 3.4. Let it be {b_{i}}_{i=1}^{m}. Use algorithm in Theorem 4.3 to compute compact representations of units {η_{i}}_{i=1}^{m} corresponding to the vectors {b_{i}}_{i=1}^{m}. Since the basis {b_{i}}_{i=1}^{m} is unique (upto approximation) and since all the algorithms involved are polynomial time deterministic algorithm the output generated is independent of the fundamental system of units that was given as input.

Given any set of units {ε_{i}}, we now analyze the approximation of Log (ε_{i}) required in order to accurately compute the canonical fundamental system of units.

Let {η_{i}} the canonical fundamental system of units and let a_{i} = Log (η_{i}). Let b_{i} = Log (ε_{i}). Consider the matrices A = (a_{ij}) and B = (b_{ij}) (recall that for a vector v, v_{i} denotes its i^{th} component). Since a_{i}’s and b_{i}’s span the same lattice Λ = Log (O^{∗}), there is a unimodular transformation U ∈ SL_{m}(ℤ) such that A = UB. Note that the determinant of B is the regulator which is at least 0.2 and hence it can be shown that each entries of U is of size bounded by a polynomial in the sized of entries in A and B. Let B_{q} denote the q bit approximations of B and let A_{q} = UB_{q}. We have

∥ A_{q} − A ∥_{∞} = ∥ U(B_{q} − B) ∥_{∞} ≤ m ∥ U ∥_{∞} 2^{−q}.

If we take q large enough so that ∥ A_{q} − A ∥_{∞} is small enough for us to recover back the compact representation of η_{i}’s we are through. It is easy to see that a q that is bounded by a polynomial in the sizes of entries of A and B is sufficient for this purpose.

Lemma 4.6. In the algorithm of Theorem 4.5, it suffices to approximate Log (ε_{i}) to an error of 2^{−q} where q ≤ (lg(∥ A ∥_{∞}) lg(∥ B ∥_{∞}))^{O(1)}.

5 Computing Units is in FP^{SPP}

In this section we give an FP^{SPP} algorithm for computing a fundamental system of units for a number field K. The algorithm is in two stages. In the first stage it computes a number B such that the regulator R_{K} lies in the range [B, 2B). Notice that, having computed such a bound B, we can test in deterministic polynomial time if an arbitrary set of m algebraic numbers is a fundamental system of units. Given this value of B, in the second stage the FP^{SPP} algorithm computes a fundamental system of units of K. The first stage is described in the following lemma.

Lemma 5.1. Given a number field K, there is an FP^{SPP} algorithm to compute a constant B such that the regulator R_{K} of K, lies in the interval [B, 2B).

Proof. We give a polynomial time algorithm that makes UP-like queries to an NP oracle. Consider the following NP language:

A = {⟨x, O_{K}⟩ | there is a subgroup of index y in O_{K}^{∗} : x ≤ yR_{K} < 2x}.

We consider the following nondeterministic procedure that accepts A.

Input: A rational x and basis for the ring of integers, O of a number

field K Output: “Yes” if there is a subgroup of O^{∗} of index y such that

x ≤ yR_{K} < 2x; “No” otherwise.

1 Guess the polynomial sized compact representations of m units of O say {ε}_{i=1}^{m}; Compute rational approximations of {Log (ε_{i})}_{i=1}^{m} and check if they form a linearly independent set. If not reject; Compute the volume of the parallelepiped formed by the {Log (ε_{i})}_{i=1}^{m} and check if it lies in the interval [x, 2x). If not reject;

2 Use the algorithm in Theorem 4.5 to compute a canonical fundamental system of units say η_{i}’s; Check the whether the compact representations obtained in step 2 is same as the guessed compact representations. If yes accept else reject; We now explain Step 1. First guess m (polynomial sized) compact represen-

tations of m algebraic integers {α_{i}}_{i=1}^{m}. Applying Theorem 2.3 it is possible to compute α_{i}O and check whether α_{i}O = O in polynomial time.

In the above NP machine if x is such that x ≤ R_{K} < 2x then there will be only one accepting path. This is because any set of m units that was guessed in step 1 will indeed be a fundamental system of units. For each of these accepting paths, step 2 will give a unique compact representation of a fundamental system of units— those units that in the Log map gives the ≺-minimum basis of Log (O^{∗}). Hence the only path that will accept is that which guessed that unique compact representation of units corresponding to the ≺-minimal basis of Log (O^{∗}).

Input: A ℤ-basis for the ring of integers, O, of a number field K Output: A rational B such that B ≤ R_{K} < 2B B := 0.2; while true do

if ⟨B, O_{K}⟩ ∈ A then return B; B := 2B;

end

It is known that the regulator of any number field is at least 0.2 [8]. We now describe the procedure that computes the required bound B:

Since this procedure makes UP-like queries to the NP language A we can convert it into a FP^{SPP} algorithm by Lemma 1.3.

Lemma 5.2. Given a constant B such that B ≤ R_{K} < 2B, a fundamental system of units can be computed in FP^{SPP}.

Proof. First, consider the following nondeterministic polynomial time machine M. The machine M first guesses a set of m algebraic integers in their compact representation and then verifies in polynomial time that the guessed algebraic integers indeed form a fundamental system of units by first checking whether they are indeed units (check if αO = O) and then calculating the volume of the parallelepiped (in the Log map) formed by the vectors corresponding to the guessed units, by a determinant computation. If this volume does not lie between B and 2B, the machine M rejects on this computation path. Otherwise, applying Theorem 4.5 along with the guessed fundamental system of units as input, the machine M now computes a canonical fundamental system of units and checks if it coincides with the guessed fundamental system of units. If they do coincide the machine M accepts along this computation path. It is clear from the above description that the nondeterministic machine M has a unique accepting path. Applying Lemma 1.3, we can now design from M an FP^{SPP} algorithm that will compute a fundamental system of units, if it is additionally given B such that B ≤ R_{K} < 2B.

Now, combining Lemmas 5.1 and 5.2 we immediately obtain the following.

Theorem 5.3. There is a FP^{SPP} algorithm to compute a fundamental system of units of the ring of integers of a number field K assuming that the degree [K : ℚ] is a constant.

6 Principle Ideal Testing is in SPP

Given a number field K and a ℤ-basis for its ring of integer O, the principal ideal testing problem (denoted by PrI) problem is to check if an 𝔞 of O is a principal ideal. We show that this problem is in SPP.

Theorem 6.1. Given a number field K with ring of integers O and the ℤ basis of a ideal 𝔞, checking whether 𝔞 is principal is in SPP, assuming [K : ℚ] is a constant.

Proof. Without loss of generality we can assume that 𝔞 is an integral ideal. First compute a fundamental system of units {ε_{i}}_{i=1}^{m} of O using the algorithm in Theorem 5.3. Guess the compact representation of an algebraic integer α. Check if αO = 𝔞 if not reject. Check if Log (α) lies in the fundamental parallelepiped {x ∈ ℝ^{m} : x = ∑ α_{i}Log (ε_{i}) , α_{i} ∈ [0, 1]}. If not reject. Next, apply Theorem 4.3 to obtain a compact representation of α′ from Log (α) and 𝔞, such that Log (α) = Log (α′). If the compact representations of α and α′ coincide we accept on that computation path and reject otherwise. The correctness of the easily follows from Theorem 4.3 and the fact that for every α ∈ O there is a unique associate in the fundamental parallelepiped.

6.1 Computing the Class Number

Finally, we show that if we assume the generalized Riemann hypothesis (GRH) then finding the class number and a presentation for the class group are in FP^{SPP}. It is shown by Bach [2] that if the GRH is true then the class group of any number field K is generated by the ideal classes of all non-inert prime ideals of norm less L = 12 ln^{2} |D|. Let 𝔭_{1}, …, 𝔭_{N} be the (polynomially many) ideal classes of all non-inert prime ideals of norm less L = 12 ln^{2} |D|. We can compute these ideals 𝔭_{i} in polynomial time as explained, for example in [8, Section 6.2.5] or [5].

Our goal is to compute the class number and a generator-relator presentation of the class group of K. Let G_{i} denote the subgroup of Cl(K) generated by {𝔭_{1}, …, 𝔭_{i}} and let G_{0} = {id}. For each i let t_{i} be the least positive integer such that 𝔭_{i}^{t_{i}} ∈ G_{i−1}. Let s_{ij}, 1 ≤ i ≤ N and 1 ≤ j < i be integers such that 0 ≤ s_{ij} < t_{j} and such that 𝔭_{i}^{t_{i}} ∼ ∏_{j}^{i−1} 𝔭_{j}^{s_{ij}}. The set of relators defined by

R = {𝔭_{i}^{t_{i}} = ∏_{j=1}^{i−1} 𝔭_{j}^{s_{ij}} : 1 ≤ i ≤ N}

together with the generator set {𝔭_{1}, …, 𝔭_{N}} gives a generator-relator presentation of Cl(K). Furthermore, notice that the s_{ij}’s are unique in the range 0 ≤ s_{ij} < t_{j}. Also, t_{1} is the order of the ideal class of 𝔭_{1} in Cl(K). We will describe an FP^{SPP} procedure for computing the set R inductively as follows.

Assume that the set of relators

R_{i} = {𝔭_{j}^{t_{j}} = ∏_{k=1}^{j−1} 𝔭_{k}^{s_{jk}} : 1 ≤ j ≤ i}

is already computed (where R_{0} = ∅). It suffices to give an FP^{SPP} procedure for computing R_{i+1}. To this end, we define an NP^{SPP} language A as follows: A consists of the set of tuples ⟨x, y, {𝔞_{j}}_{j=1}^{i}, {(m_{j}, n_{j})}_{j=1}^{i−1}⟩ such that there is a x ≤ t < y and m_{j} ≤ s_{j} < n_{j} such that 𝔞_{i}^{t} ∼ ∏_{j=1}^{i−1} 𝔞_{j}^{s_{j}}, where 𝔞_{j}’s are ideals in O_{K} given by their HNFs. It is easy to see that the language A is in NP^{SPP}: guess t and the s_{j}’s and verify the class group identity by applying the SPP algorithm for principal ideal testing in Theorem 6.1.

The following code is a polynomial-time oracle computation (with oracle A) that computes R_{i+1} from R_{i}.

Let T := 1;

while true do

if ⟨T, 2T, {𝔭_{j}}_{j=1}^{i+1}, {(1, t_{j})}_{j=1}^{i}⟩ ∈ A then break else T := 2T end Do a binary search for t_{i+1} in the range [T, 2T) using A as oracle.; Next, do a binary search to compute the s_{j}’s. (* These s_{j}’s are actually the s_{i+1j} in the definition of R. *) It is easy to see that in the above algorithm only UP-like queries are made to

A. More precisely, the queries will be of the form ⟨x, y, {𝔭_{j}}_{j=1}^{i}, {(m_{j}, n_{j})}_{j=1}^{i−1}⟩, with parameters such that the NP^{SPP} machine for A will have at most one accepting path. The queries are UP-like as R_{i} is a set of relators for G_{i}. Now, using closure properties of SPP and Lemma 1.3 we can transform the above algorithm to an FP^{SPP} procedure that inductively computes the generator-relator presentation of the class group Cl(K). Observe that the class number is given by ∏_{i=1}^{N} t_{i}. Hence we have the following theorem.

Theorem 6.2. Assuming the GRH, the class number and a generator-relator presentation for the class group of a constant-degree number field can be computed in FP^{SPP}.

Acknowledgment. We thank the referees for their useful comments.

References

[1] V. Arvind and P. P. Kurur. Graph Isomorphism is in SPP. In 43^{rd} Annual Symposium of Foundations of Computer Science, pages 743–750. IEEE, November 2002.

[2] E. Bach. Explicit bounds for primality testing and related problems. Mathematics of Computation, 55:355–380, 1990.

[3] J. Buchmann. On computation of units and class number by a generalization of Lagrange’s algorithm. Journal of Number Theory, 26:8–30, 1987.

[4] J. Buchmann. On the period length of the generalized Lagrange algorithm. Journal of Number Theory, 26:31–37, 1987.

[5] J. Buchmann and H. W. Lenstra Jr. Computing maximal orders and decomposing primes in number fields. preprint.

[6] J. Buchmann and H. C. Williams. On the infrastructure of the principal ideal class of an algebraic number field of unit rank one. Mathematics of Computation, 50:569–579, 1988.

[7] J. Buchmann and H. C. Williams. On the existence of a short proof for the value of the class number and regulator of a real quadratic field. Number Theory and Applications, 265:327–345, 1989.

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

[9] S. Fenner, L. Fortnow, S. A. Kurtz, and L. Li. An oracle builder’s toolkit. In SCT: Annual Conference on Structure in Complexity Theory, pages 120– 131, 1993.

[10] S. A. Fenner, L. Fortnow, and S. A. Kurtz. Gap-definable counting classes. In Structure in Complexity Theory Conference, pages 30–42, 1991.

[11] L. Fortnow and J. D. Rogers. Complexity limitations on quantum computation. In IEEE Conference on Computational Complexity, pages 202–209, 1998.

[12] S. Hallgren. Polynomial-time quantum algorithms for pell’s equation and the principal ideal problem. In Proceedings of the 34^{th} ACM Symposium on Theory of Computing, pages 653–658. IEEE, 2002.

[13] H. W. Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538–548, 1983.

[14] J. Kobler, U. Schoning, S. Toda, and J. Toran. Turing machines with few accepting computations and low sets for PP. Journal of Computer and System Sciences, 44(2):272–286, 1992.

[15] J. Köbler, U. Schöning, and J. Torán. The Graph Isomorphism Problem: Its Structural Complexity. Birkhauser, 1993.

[16] K. S. McCurley. Cryptographic key distribution and computation in class groups. In NATO Advanced Science Institute Series C, volume 256, pages 459–479. Kluwer, Dordrecht, 1989.

[17] C. Thiel. Under the assumption of the Generalized Riemann Hyothesis verifying the class number belongs to NP ∩ co-NP. In Algorithmic Number Theory, First International Symposium, ANTS-I, volume 877 of Lecture Notes in Computer Science, pages 234–247. Springer, 1994.