Approximating rings of integers in number fields version 19941108

Approximating rings of integers in number fields

J. A. Buchmann and H. W. Lenstra, Jr.

Fachbereich Informatik Department of Mathematics Universität des Saarlandes University of California D–6600 Saarbrücken Berkeley, CA 94720 Germany U. S. A. buchmann@cs.uni-sb.de hwl@math.berkeley.edu

Abstract. In this paper we study the algorithmic problem of finding the ring of integers of a given algebraic number field. In practice, this problem is often considered to be wellsolved, but theoretical results indicate that it is intractable for number fields that are defined by equations with very large coefficients. Such fields occur in the number field sieve algorithm for factoring integers. Applying a variant of a standard algorithm for finding rings of integers, one finds a subring of the number field that one may view as the “best guess” one has for the ring of integers. This best guess is probably often correct. Our main concern is what can be proved about this subring. We show that it has a particularly transparent local structure, which is reminiscent of the structure of tamely ramified extensions of local fields. A major portion of the paper is devoted to the study of rings that are “tame” in our more general sense. As a byproduct, we prove complexity results that elaborate upon a result of Chistov. The paper also includes a section that discusses polynomial time algorithms related to finitely generated abelian groups.

Key words: maximal order, tame extensions, algorithm.

1991 Mathematics subject classification: 11Y16, 11S15.

Acknowledgements. The first author was supported by the Deutsche Forschungsgemeinschaft. The second author was supported by the National Science Foundation under grants No. DMS 90-02939 and 92-24205. The second author is grateful to the Institute for Advanced Study (Princeton), where part of the work on which this paper is based was done. The final version of this paper was prepared while the second author was on appointment as a Miller Research Professor in the Miller Institute for Basic Research in Science.

1. Introduction In this paper we are concerned with the following problem from algorithmic algebraic number theory: given an algebraic number field K, determine its ring of integers O. Paradoxically, this problem is in practice considered well-solved (cf. [7, Chapter 6] and 7.2 below), whereas a result of Chistov [6] (Theorem 1.3 below) suggests that from a theoretical perspective the problem is intractable. The apparent contradiction is easy to resolve. Namely, all computational experience so far is limited to “small” number fields K, such as number fields that are given as K = Q[X]/fQ[X], where Q is the field of rational numbers and f is an irreducible polynomial of small degree with small integer coefficients. The algorithms that are used for small fields will not always work when they are applied to “large” number fields. Large number fields are already making their appearance in applications of algebraic number theory (see [14]), and the determination of their rings of integers is generally avoided (see [5; 17, 9.4; 9]). The results of the present paper are mainly theoretically inspired, but they may become practically relevant if one wishes to do computations in large number fields.

In accordance with Chistov’s result, we shall see that there is currently not much hope to find a good algorithm for the problem of constructing rings of integers. This is true if “good” is taken to mean “running in polynomial time”, and it is equally true if, less formally, it is taken to mean “practically usable, also in hard cases”. The same applies to the problem of recognizing rings of integers, i. e., the problem of deciding whether a given subring of a given algebraic number field K is equal to O.

To appreciate the central difficulty it suffices to look at quadratic fields. If m is an integer that is not a square, then determining the ring of integers of Q(\sqrt{m}) is equivalent to finding the largest square divisor of m. The latter problem is currently considered infeasible. Likewise, the problem of recognizing the ring of integers of a quadratic field is equivalent to the problem of recognizing squarefree integers, which is considered infeasible as well.

In the present paper we obtain some positive results. We shall prove that, even though O may be hard to determine, one can at least construct a subring B of K that comes “close” to O, that is perhaps even likely to be equal to O, that in any case has some of the good properties of O, and that in computational applications of algebraic number theory can probably play the role of O. Before we state our main result we give an informal outline of our approach.

Chistov [6] showed that the problem of determining the ring of integers of a given number field is polynomially equivalent to the problem of determining the largest squarefree divisor of a given positive integer (see Theorem 1.3 below). For the latter problem no good algorithm is known (see Section 7). However, there is a naïve approach that often works. It is based on the observation that positive integers with a large repeated prime factor are scarce: for most numbers it is true that all repeated prime factors are small and therefore easy to find. Thus, dividing a given positive integer d by all of its repeated prime factors that are less than a certain upper bound b one finds a number that may have a good chance of being the largest squarefree divisor of d, and that is often the best guess one has. The success probability of this method depends on b and on the way in which d was obtained in the first place. It is, of course, easy to construct numbers d that defeat the algorithm.

One can attempt to determine the ring of integers O of a given number field K in a similarly naïve manner. One starts from an order in K, i. e., a subring A of O for which the index ⟨O : A⟩ of additive groups is finite; for example, one may take A = Z[α], where α ∈ K is an algebraic integer with K = Q(α). As we shall see, one can determine O if the largest squarefree divisor m of the discriminant Δ_{A} of A is known. This result suggests that one can determine a “best guess” for O by working with the best guess q that one has for m instead of m itself. If, in the course of the computations, the hypothesis that q is squarefree is contradicted because an integer a > 1 is found for which a^{2} divides q, then one simply replaces q by q/a and one continues as if nothing has happened.

This vague idea can be made perfectly precise. It gives rise to a polynomial time algorithm that, given an order A ⊂ K, produces an order B ⊂ K containing A as well as a positive integer q. One knows that B = O if q is squarefree. It will often be considered very likely that q is indeed squarefree, so that one is inclined to believe that B = O. Our main concern is what one can prove about B without relying on any unproved assumptions regarding q. In particular, we shall prove that B equals O if and only if q is squarefree, and that finding an order in K that properly contains B is equivalent to finding a square a^{2} > 1 dividing q.

Our results are derived from a local property of B that we refer to as tameness at q. Loosely speaking, B is tame at q if B is trying to resemble a full ring of integers as closely as is possible in view of the fact that q is not known to be squarefree. Tameness is a strong property, which provides us with substantial control over the ring. Before we give the definition we remind the reader of the local structure of full rings of integers.

Let O be the ring of integers of an algebraic number field, let p be a maximal ideal of O, and let O_{p} be the p-adic completion of O (see [1, Chapter 10]). Denote by p the unique prime number that belongs to p. If the ramification index e(p/p) of p over p equals 1, then p is said to be unramified over p, and in that case O_{p} is a local unramified algebra over the ring Z_{p} of p-adic integers (see Section 3). Local unramified Z_{p}-algebras are easy to understand and to classify, and they have a very transparent structure [25, Section 3-2]; for example, they are, just like Z_{p} itself, principal ideal domains that have, up to units, only one prime element, namely p. If, more generally, p does not divide e(p/p), then p is said to be tame over p. In this case there is a local unramified Z_{p}-algebra T and a unit v of T such that O_{p} ≅ T [X]/(X^{e(p/p)} − vp)T [X] = T [(vp)^{1/e(p/p)}] (see [25, Section 3-4]). Conversely, let p be a prime number, let T be a local unramified Z_{p}-algebra, let v be a unit of T, and let e be a positive integer that is not divisible by p. Then there is an algebraic number field whose ring of integers O has a maximal ideal p containing p for which the ring T [(vp)^{1/e}] is isomorphic to O_{p}, and then e(p/p) = e. In summary, the rings T [(vp)^{1/e}], which are relatively simple to understand, provide a full description of the completions of the rings of integers of all algebraic number fields at all tame maximal ideals.

In the wild case, in which p does divide e(p/p), the structure of O_{p} is somewhat more complicated, but there is fortunately no need for us to consider it: it occurs only if p is small, and small primes can be taken care of directly.

Imitating the description above of O_{p} we make the following definition. Let B be an order in a number field, and let q be a positive integer. We call B tame at q if for every prime number p dividing q and every maximal ideal p of B containing p there exist a local unramified Z_{p}-algebra T, an integer e that is not divisible by p, and a unit u of T such that the p-adic completion B_{p} of B is, as a Z_{p}-algebra, isomorphic to T [X]/(X^{e} −uq)T [X] (see Section 4). If q is squarefree then p divides q only once; in that case uq = vp for some unit v of T, and we are back at the ring T [(vp)^{1/e}] considered above. However, if p^{2} divides q then T [X]/(X^{e} − uq)T [X] occurs as a ring O_{p} as above only in the trivial case that e = 1 (cf. 3.5).

One of our main results now reads as follows.

Theorem 1.1. There is a deterministic polynomial time algorithm that, given a number field K and an order A in K, determines an order B in K containing A and a positive integer q, such that B is tame at q and such that the prime numbers dividing ⟨O : B⟩ are the same as the repeated prime divisors of q; here O denotes the ring of integers of K.

This theorem is proved in Section 6, along with the other theorems stated in this introduction. The algorithms referred to in our theorems will be explicitly exhibited.

Clearly, the ring B in Theorem 1.1 equals O if and only if q is squarefree. Generally we shall see that exhibiting a square a^{2} > 1 dividing q is, under polynomial transformations, equivalent to finding an order in K that strictly contains B (see Theorem 6.9).

Finding rings of integers is customarily viewed as a local problem, in the sense that it suffices to do it prime-by-prime. Algorithmically, however, the bottleneck is of a global nature: how to find the prime numbers that one needs to look at? Once these are known, the problem admits a solution. This is expressed in our next result. If m is an integer, then an order A in K is said to be maximal at m if gcd(m, ⟨O : A⟩) = 1.

Theorem 1.2. There is a polynomial time algorithm that, given an algebraic number field K, an order A in K, and a squarefree positive integer m, determines an order B in K containing A that is maximal at m.

From 1.2 we see in particular that if m is prime one can find, in polynomial time, an order in K that is maximal at m. If m is taken to be the product of the primes p for which p^{2} divides the discriminant of A, then the order B in Theorem 1.2 equals O.

We next formulate a few complexity results of purely theoretical interest.

Theorem 1.3. Under polynomial transformations, the following two problems are equivalent:

(a) given an algebraic number field K, find the ring of algebraic integers of K;

(b) given a positive integer d, find the largest squarefree divisor of d.

Theorem 1.3 represents a slight improvement over a theorem of Chistov [6], as explained in 6.11. We shall prove that the corresponding recognition problems are also equivalent (Theorem 6.12).

Suppose that an order A in an algebraic number field is given. In the proof of Theorem 1.3 we shall see that, given the largest squarefree divisor of the discriminant Δ_{A} of A, one can find the ring of integers O of K in polynomial time. In 6.13 we argue that it is hard to go in the opposite direction: if given O one can easily find the largest squarefree divisor of Δ_{A}, then problem 1.3(b) is easy as well. It is possible, however, to compute the largest square divisor of Δ_{A} quickly from O; again it is hard to go in the opposite direction (see 6.14).

If the ring of integers of a number field K is known, then the discriminant of K is easy to compute. One may wonder whether, conversely, it is easy to compute the ring of integers of K from the discriminant of K. In 6.10 we shall see that this is currently not the case. However, we do have the following result.

Theorem 1.4. There are polynomial time algorithms that given an algebraic number field K and one of (a), (b), determine the other:

(a) the ring of algebraic integers of K;

(b) the largest squarefree divisor of the discriminant of K.

In the body of the paper we work with orders in products of number fields rather than orders in number fields. This presents no additional difficulty. One may remark, though, that the case of products of number fields can in polynomial time be reduced to the case of a single number field, by the main result of [15]. Also, several of our results are local in the sense that they are directed not at constructing O, but at constructing an order that is maximal at a given integer m, as in Theorem 1.2.

We have refrained from considering more general base rings than the ring Z of rational integers. Over some base rings, the problem of finding maximal orders is, in substance, equivalent to the problem of resolving singularities of curves (see [24]); but in that context there is a quick algorithm for problem 1.3(b), so that the issues considered in this paper do not arise. It may be interesting to consider base rings that are rings of integers of number fields or, more generally, orders in number fields as produced by our algorithms.

The contents of this paper are as follows. Sections 2, 3 and 4 contain the commutative algebra that we need. No algorithms occur in these sections. In Section 2 we assemble some well-known results concerning orders. Sections 3 and 4 are devoted to the notion of tameness, locally in Section 3 and globally in Section 4. Sections 5 and 6 deal with algorithms. In Section 5 we recall a few basic algorithms for which a convenient reference is lacking; they mostly concern linear algebra over the rings Z and Z/qZ, where q is a positive integer. In Section 6 we present the algorithm that underlies the proof of Theorem 1.1. It is a variant of an algorithm for determining maximal orders that is due to Zassenhaus [26; 27]. Section 6 also contains the proofs of the theorems stated above. In Section 7 we discuss the practical repercussions of our results.

For our conventions and notations on commutative algebra we refer to Section 2. For conventions concerning algorithms we refer to Section 5 and to [18].

2. Orders In this section we establish the notation and terminology concerning rings and orders that we shall use, and we recall a few well-known facts. For background on commutative algebra, see [1].

2.1. Rings and algebras. All rings in this paper are assumed to be commutative with a unit element. Ring homomorphisms are assumed to preserve the unit element, and subrings contain the same unit element. By Z, Q, F_{p} we denote the ring of integers, the field of rational numbers, and the field of p elements, respectively, where p is a prime number. The group of units of a ring R is denoted by R^{∗}. Let R be a ring. An R-module M is called free if it is isomorphic to the direct sum of a collection of copies of R; if R ≠ 0 then the number of copies needed is uniquely determined by M, and it is called the rank of M; if R = 0, then the rank of M is defined to be 0. If an R-module M is free of finite rank n, then there is a basis of M over R, i. e., a collection of n elements ω_{1}, ω_{2}, …, ω_{n} ∈ M such that for each x ∈ M there is a unique sequence of n elements r_{1}, r_{2}, …, r_{n} ∈ R such that x = ∑_{i=1}^{n} r_{i}ω_{i}. By an R-algebra we mean a ring A together with a ring homomorphism R → A. An R-algebra A is said to admit a finite basis if A is free of finite rank when considered as an R-module. If this is the case, then the rank of A as an R-module is called the degree of A over R, notation: [A : R].

2.2. Trace and discriminant. Let R be a ring and let A be an R-algebra admitting a finite basis ω_{1}, …, ω_{n}. For each a ∈ A, the trace Tr a of a is defined to be the trace of the R-linear map A → A sending x to ax; so if aω_{i} = ∑_{j=1}^{n} r_{ij}ω_{j} with r_{ij} ∈ R, then Tr a = ∑_{j=1}^{n} r_{jj}. The trace Tr is an R-linear map A → R. In case of possible ambiguity, we may write Tr_{A} or Tr_{A/R} instead of Tr. The discriminant Δ_{A} or Δ_{A/R} of A over R is the determinant of the matrix (Tr(ω_{i}ω_{j}))_{1≤i,j≤n}. The discriminant is well-defined only up to squares of units of R. The R-ideal generated by Δ_{A} is well-defined, and we shall also denote it by Δ_{A}. If R′ is an R-algebra, then A′ = A ⊗_{R} R′ is an R′-algebra that also admits a finite basis. The trace function A′ → R′ is obtained from the trace function A → R by base extension, and the notation Tr, Tr_{A}, Tr_{A/R} used for the latter will also be used for the former. We have Δ_{A′/R′} = Δ_{A/R}R′ as ideals.

2.3. Orders. Let R be a principal ideal domain, and denote by F the field of fractions of R. An order over R is an R-algebra A that admits a finite basis and that satisfies Δ_{A} ≠ 0. An order over Z is simply called an order; equivalently, an order can be defined as a ring without non-zero nilpotent elements of which the additive group is free of finite rank as an abelian group. Let A be an order over R, and write A_{F} = A ⊗_{R} F. Then A_{F} is, as an F -algebra, the product of finitely many finite separable field extensions of F. By a fractional A-ideal we mean a finitely generated A-submodule of A_{F} that spans A_{F} as a vector space over F. If a and b are fractional A-ideals, then the index ⟨a : b⟩ of b in a is defined to be the determinant of any F -linear map A_{F} → A_{F} that maps a onto b; the index is an element of F^{∗} that is well-defined only up to units of R. If b ⊂ a then the index belongs to R−{0}, and if in addition R = Z then it is, up to sign, equal to the usual index. If a, b are fractional A-ideals, then we write a : b = {x ∈ A_{F} : xb ⊂ a}; this is also a fractional A-ideal. A fractional A-ideal a is called invertible if ab = A for some fractional A-ideal b; if this is true, then b = A : a, and a = A : b = A : (A : a). An example of a fractional ideal is the complementary module A^{†} = {x ∈ A_{F} : Tr(xA) ⊂ R}. If (ω_{i})_{i=1}^{n} is a basis for A over R, then a basis for A^{†} over R is given by the dual basis (ω_{i}^{†})_{i=1}^{n}, which is characterized by Tr(ω_{i}ω_{j}^{†}) = 0 or 1 according as i ≠ j or i = j. One has A ⊂ A^{†} and ⟨A^{†} : A⟩ = Δ_{A}. By an overorder of A we mean a fractional A-ideal that is a subring of A_{F}. If a is a fractional A-ideal, then a : a is an overorder of A. Each overorder B of A is an order, and it satisfies A ⊂ B ⊂ B^{†} ⊂ A^{†} and Δ_{A} = Δ_{B}⟨B : A⟩^{2}. Among all overorders of A there is a unique one that is maximal under inclusion; we shall denote it by O. The ring O is equal to the integral closure of R in A_{F}, and it is the product of finitely many Dedekind domains. The discriminant of O is also called the discriminant of A_{F}. We call A maximal if A = O; this is the case if and only if all fractional A-ideals are invertible. If m ∈ R, then the order A is said to be maximal at m if gcd(m, ⟨O : A⟩) = 1; this happens, for example, if gcd(m, Δ_{A}) = 1, because ⟨O : A⟩^{2} divides Δ_{A}. For the same reason, A itself is maximal if and only if it is maximal at Δ_{A}.

Proposition 2.4. Suppose that R is a principal ideal domain, that m ∈ R is a non-zero element, and that A is an order over R. Then there are only finitely many prime ideals p of A containing m, and they are all maximal. Moreover, if b denotes the intersection of these prime ideals, then we have:

(a) b/mA is the nilradical of the ring A/mA, and there exists a positive integer t such that b ⊃ mA ⊃ b^{t};

(b) for each prime ideal p of A containing m one has A : p ⊄ A;

(c) A is maximal at m if and only if b : b = A.

Proof. Since A admits a finite basis over the principal ideal domain R, the R-module A/mA is of finite length. Therefore the ring A/mA is an Artin ring. From [1, Chapter 8] it follows that each prime ideal of A/mA is maximal, that there are only finitely many of them, and that their intersection is nilpotent. This proves the first two assertions of 2.4, as well as (a). To prove (b), we note that the annihilator of the prime ideal p/mA in the Artin ring A/mA is non-zero, so mA : p properly contains mA. Therefore A : p properly contains A. To prove (c), first assume that A is maximal at m. From ⟨O : A⟩O ⊂ A and gcd(m, ⟨O : A⟩) = 1 it follows that for each maximal ideal pR of R dividing m the localizations A_{pR} and O_{pR} are equal. Hence the order A_{pR} over R_{pR} is a product of finitely many Dedekind domains, and b_{pR} is a product of non-zero ideals in those Dedekind domains. Therefore b_{pR} : b_{pR} = A_{pR}. The same equality also holds for maximal ideals pR of R that do not contain m, since in that case b_{pR} = A_{pR}. It follows that b : b = A, as required. For the converse, assume that b : b = A. The maximal ideals p of A containing m are pairwise coprime, so their intersection b is equal to their product. Hence b : b = A implies that all those p satisfy p : p = A. We claim that (A : p)p = A for each p, so that each p is invertible. If not, then from p ⊂ (A : p)p ⊂ A and the maximality of p one derives that p = (A : p)p, so A : p ⊂ p : p = A, contradicting (b). From the invertibility of all maximal ideals containing m one deduces by induction that all A-ideals that contain a power m^{k} of m, with k ≥ 0, are invertible, and the same is then true for all fractional ideals H with A ⊂ H ⊂ m^{−k}A for some k ≥ 0. Apply this to H = {x ∈ O : m^{i}x ∈ A for some i ≥ 0}. This is a ring, so HH = H, and the invertibility of H implies H = A. Therefore ⟨O : A⟩ is coprime to m. This proves 2.4.

Remark. Every maximal ideal p of an order A over a principal ideal domain R that is not a field contains a non-zero element of R, by [1, Corollary 5.8]. So 2.4(b) shows that A : p ⊄ A for each such p.

Proposition 2.5. Let A be an order over a principal ideal domain, and let a be a fractional A-ideal. Then a is invertible if and only if the overorder (A : a) : (A : a) of A equals A, and if and only if both A : (A : a) = a and a : a = A.

Proof. If a is invertible, then as we saw in 2.3 we have A : (A : a) = a, and a : a = (a : a)A = (a : a)a(A : a) = a(A : a) = A; also, b = A : a is then invertible as well, so for the same reason we have (A : a) : (A : a) = A. Next suppose that a is not invertible. Then the A-ideal (A : a)a is different from A, so there is a maximal ideal p of A containing (A : a)a. We have A : p ⊂ A : ((A : a)a) = (A : a) : (A : a), so from 2.4(b) we see that (A : a) : (A : a) ≠ A. This proves that a is invertible if (A : a) : (A : a) = A. Applying this to b = A : a, we find that b is invertible if A : b = a and a : a = A, and then its inverse a is invertible as well. This proves 2.5.

2.6. Gorenstein rings. Let A be an order over a principal ideal domain. We call A a Gorenstein ring if A : (A : a) = a for every ideal a of A that contains a non-zero-divisor of A or, equivalently, for every fractional A-ideal a. It is an easy consequence of [3, Theorem (6.3)] that this is, for orders over principal ideal domains, equivalent to the traditional notion. Note that A is a Gorenstein ring if it is a maximal order. The converse is not true (cf. 2.8).

Proposition 2.7. Let A be an order over a principal ideal domain R, with complementary module A^{†}. Then the following properties are equivalent:

(a) A is a Gorenstein ring;

(b) for any fractional A-ideal a, we have a : a = A if and only if a is invertible;

(c) A^{†} is invertible.

Proof. From 2.5 and the definition of a Gorenstein ring it is clear that (a) implies (b). To prove that (b) implies (c), it suffices to prove that A^{†} : A^{†} = A. Generally, put a^{†} = {x ∈ A_{F} : Tr(xa) ⊂ R} for any fractional A-ideal a, where A_{F} is as in 2.3. Using dual bases one easily proves that a^{††} = a, and from the definitions one sees that a^{†} = A^{†} : a. Applying this to a = A^{†} one obtains A^{†} : A^{†} = A, as required. Finally, we prove that (c) implies (a). Suppose that A^{†} is invertible, and let a be a fractional ideal. Applying the equality a^{†} = A^{†} : a twice we find that a = a^{††} = A^{†} : (A^{†} : a). We need to prove that this equals A : (A : a). If b = A : A^{†} denotes the inverse of A^{†}, then we have A^{†} : a = (A : b) : a = A : (ab) = (A : a) : b = (A : a)A^{†} and A^{†} : (A^{†} : a) = A^{†} : ((A : a)A^{†}) = (A^{†} : A^{†}) : (A : a) = A : (A : a). This proves 2.7.

2.8. Example. Let R be a principal ideal domain and let f ∈ R[X] be a monic polynomial with non-vanishing discriminant. Then A = R[X]/fR[X] is an order over R, and if we write α = (X mod f) ∈ A then A^{†} = f′(α)^{−1}A (cf. [25, Proposition 3-7-12]). This shows that A^{†} is invertible, so 2.7 implies that A is a Gorenstein ring. It is well-known that A is not necessarily maximal.

Proposition 2.9. Let R be an Artin ring, let L be a free R-module of finite rank, and let N ⊂ L be a submodule. Then N is free over R if and only if L/N is free over R.

Proof. Since each Artin ring is a product of finitely many local Artin rings, the proof immediately reduces to the case that R is local. It is convenient to use a few properties of projective modules, which can be found in [12, Chapter 1, Section 1]. First suppose that L/N is free. Then the exact sequence 0 → N → L → L/N → 0 splits, so N is projective, and therefore free. For the converse, assume that N is free. Let m be the maximal ideal of R, and let a ∈ R a non-zero element annihilated by m. Then mN = {x ∈ N : ax = 0} = N ∩{x ∈ L : ax = 0} = N ∩(mL), so N/mN is a subspace of the R/m-vector space L/mL. Supplementing an R/m-basis of N/mN to one for L/mL and applying Nakayama’s lemma one finds a surjection N ⊕ R^{n} → L, where n = rank L − rank N. Comparing the lengths of the two modules we see that it is an isomorphism. Hence L/N ≅ R^{n}. This proves 2.9.

3. Tame algebras over the p-adic integers This section and the next one are devoted to a study of tameness, which is one of the central notions of this paper.

We let in this section p be a prime number, and we denote by Z_{p} the ring of p-adic integers. We call a Z_{p}-algebra T local if T is local as a ring with a residue class field of characteristic p. A local Z_{p}-algebra T is said to be unramified if T ≅ Z_{p}[Y]/gZ_{p}[Y] for some monic polynomial g ∈ Z_{p}[Y] for which (g mod p) ∈ F_{p}[Y] is irreducible. Equivalently, a local unramified Z_{p}-algebra is the integral closure of Z_{p} in a finite unramified extension of the field Q_{p} of p-adic numbers (see [25, Section 3-2]).

Throughout this section, q denotes a non-zero element of pZ_{p}. Let S be a Z_{p}-algebra. If S is local, then we call S tame at q if there exist a local unramified Z_{p}-algebra T, a positive integer e that is not divisible by p, and a unit u ∈ T^{∗}, such that S ≅ T [X]/(X^{e} − uq)T [X] as Z_{p}-algebras. In general, we call S tame at q if S is the product of finitely many local Z_{p}-algebras that are tame at q.

If q is a prime element of Z_{p} then tameness at q is equivalent to the traditional notion, as expressed by the following result. Proposition 3.1. Suppose that q ∈ pZ_{p}, q ∉ p^{2}Z_{p}, and let S be a Z_{p}-algebra. Then S is local and tame at q if and only if S is isomorphic to the integral closure of Z_{p} in a finite tamely ramified field extension of Q_{p}. Proof. This follows from the description of tamely ramified extensions given in [25, Sections 3-2, 3-3, 3-4].

We now prove various properties of Z_{p}-algebras that are tame at q.

Proposition 3.2. Let T be a local unramified Z_{p}-algebra, let e be a positive integer that is not divisible by p, and let u ∈ T^{∗} be a unit. Let further S = T [X]/(X^{e} − uq)T [X] = T [π], where π = (X mod X^{e} − uq). Then S is local and tame at q, and its maximal ideal is generated by p and π. Further, the residue class field k of S is the same as that of T, and it satisfies [k : F_{p}] = [T : Z_{p}] = [S : Z_{p}]/e.

Proof. It is easy to see that the S-ideal pS + πS is maximal and that its residue class field k is the same as the residue class field T/pT of T. Conversely, let p ⊂ S be a maximal ideal. Since S is integral over Z_{p}, we have p ∩ Z_{p} = pZ_{p} (see [1, Corollary 5.8]), so p ∈ p. Also, from π^{e} = uq ∈ p it follows that π ∈ p. This implies that p = pS + πS, and that S is local. The fact that S is tame at q follows from the definition of tameness. The relations between the degrees follow from [T/pT : Z_{p}/pZ_{p}] = [T : Z_{p}] and [S : T] = e. This proves 3.2.

Proposition 3.3. Let T, e, u, S and π be as in 3.2, and let Tr be the trace function of S over Z_{p}. Then we have:

(a) the complementary module S^{†} of S over Z_{p} is given by S^{†} = πq^{−1}S, and S^{†}/S is as a Z_{p}-module isomorphic to the direct sum of [k : F_{p}](e − 1) copies of Z_{p}/qZ_{p}.

(b) Δ_{S/Z_{p}} = q^{[k:F_{p}](e−1)}Z_{p};

(c) the S-ideal a = {x ∈ S : Tr(xS) ⊂ qZ_{p}} satisfies a = πS, a^{e} = qS, and S/a is as a Z_{p}/qZ_{p}-module free of rank [k : F_{p}];

(d) for each positive integer i the Z_{p}/qZ_{p}-module (a^{i−1} + qS)(a^{i+1} + qS)/(a^{i} + qS)^{2} is free, and its rank equals 0 for i ≠ e and [k : F_{p}] for i = e.

Proof. Since T is unramified over Z_{p}, we have T^{†} = T. Combining this with Tr = Tr_{T} ∘ Tr_{S/T} one finds that S^{†} is also the complementary module of S over T. A T -basis of S is given by 1, π, π^{2}, …, π^{e−1}. A straightforward computation shows that the dual basis is given by e^{−1}, (euq)^{−1}π^{e−1}, (euq)^{−1}π^{e−2}, …, (euq)^{−1}π, and this is a basis for πq^{−1}S. Hence S^{†} = πq^{−1}S, which is the first assertion of (a). Another T -basis for S^{†} is given by 1, q^{−1}π, q^{−1}π^{2}, …, q^{−1}π^{e−1}, from which it follows that S^{†}/S is, as a T -module, isomorphic to the direct sum of e − 1 copies of T/qT. Since T/qT is free of rank [k : F_{p}] over Z_{p}/qZ_{p} this implies the last assertion of (a).

To prove (b) it suffices, by 2.3, to compute the determinant of a Z_{p}-linear map that maps S^{†} onto S (for example, multiplication by π^{e−1}). This is left to the reader. For (c) we note that a = (qS^{†}) ∩ S = πS ∩ S = πS, so a^{e} = π^{e}S = qS and S/a = S/πS ≅ T/qT; the last isomorphism follows from S = T [X]/(X^{e} − uq)T [X]. Finally, from (c) we obtain that a^{i} + qS = π^{min{e,i}}S for any positive integer i, so (a^{i−1} + qS)(a^{i+1} + qS)/(a^{i} + qS)^{2} = 0 if i ≠ e and (a^{e−1} + qS)(a^{e+1} + qS)/(a^{e} + qS)^{2} = π^{2e−1}S/π^{2e}S ≅ S/πS = S/a, which implies (d). This proves 3.3.

3.4. Remark. Let S be a local Z_{p}-algebra that is tame at q, and let k be its residue class field. We shall call [k : F_{p}] the residue class field degree of S over Z_{p}. From 3.2 it follows that T and e are uniquely determined by S. Namely, T is, as a local unramified Z_{p}-algebra, determined by its residue class field, which is k. Using Hensel’s lemma one can show that T is even uniquely determined as a subring of S (cf. the construction of T in the proof of 3.7). Next, e is determined by e = [S : Z_{p}]/[k : F_{p}]. We shall call e the ramification index of S over Z_{p}. If e > 1, then from 3.3(a) it follows that the ideal qZ_{p} is also uniquely determined by S. Hence a local Z_{p}-algebra that is not unramified cannot be tame at two values of q that are not divisible by the same power of p. From 3.3(c) one can deduce that, for e > 1, not only the ideal qZ_{p} but also the set uqT^{∗e} is uniquely determined by S. Conversely, S is clearly determined by T, e and uqT^{∗e}.

Proposition 3.5. Let the notation be as in 3.2, and let the positive integer g be such that qZ_{p} = p^{g}Z_{p}. Denote by S̃ the integral closure of S in S ⊗_{Z_{p}} Q_{p}. Then we have S̃ = ∑_{i=0}^{e−1} T π^{i}p^{−[gi/e]}, and qp^{−1}S̃ ⊂ S. Further, S̃ is equal to S if and only if e = 1 or q ∉ p^{2}Z_{p}. We have Δ_{S̃/Z_{p}} = p^{[k:F_{p}](e−gcd(g,e))}Z_{p}, and this equals (1) if and only if g is divisible by e.

Proof. We first prove the expression for S̃ under the added assumption that T contains a primitive eth root of unity ζ. In that case, there is a T -algebra automorphism σ of S with σπ = ζπ, and σ generates a group Γ of order e. The action of Γ on S extends to an action of Γ on S ⊗_{Z_{p}} Q_{p} and on S̃. We consider the structure of S̃ as a module over the group ring T [Γ]. From e ≢ 0 mod p it follows that there is an isomorphism of T -algebras T [Γ] → T^{e} = T × T × … × T that sends σ to (ζ^{i})_{i=0}^{e−1}. Therefore S̃ is, as a T [Γ]-module, the direct sum of modules S̃_{i}, 0 ≤ i < e, where S̃_{i} = {x ∈ S̃ : σx = ζ^{i}x}. We have π^{i} ∈ S̃_{i}, so σ acts as the identity on π^{−i}S̃_{i}, and therefore π^{−i}S̃_{i} is contained in the field T ⊗_{Z_{p}} Q_{p}. Because T is unramified over Z_{p}, any T -submodule of that field is determined by the integral powers of p that it contains; so it remains to see which powers of p belong to π^{−i}S̃_{i}. For j ∈ Z, we have p^{j} ∈ π^{−i}S̃_{i} if and only if π^{i}p^{j} is integral over S, if and only if its eth power (uq)^{i}p^{ej} is integral over S, if and only if ej ≥ −gi, if and only if j ≥ −[gi/e]. This shows that π^{−i}S̃_{i} = p^{−[gi/e]}T, as required.

Next we prove the expression for S̃ in the general case. From e ≢ 0 mod p it follows that there exists a local unramified Z_{p}-algebra T′ containing T that contains a primitive eth root of unity. Apply the above to S′ = S ⊗_{T} T′, and use that S̃ equals the intersection of S ⊗_{Z_{p}} Q_{p} with the integral closure of S′ in S′ ⊗_{Z_{p}} Q_{p}. This leads to the desired result.

From [gi/e] < g we see that qp^{−1}S̃ = p^{g−1}S̃ ⊂ S. We have S̃ = S if and only if [gi/e] = 0 for 0 ≤ i ≤ e − 1, if and only if g(e − 1) < e, if and only if g = 1 or e = 0. This proves the second statement of 3.5.

The formula for the discriminant follows by an easy computation from 3.3(b) and the formula Δ_{S̃/Z_{p}} = Δ_{S/Z_{p}}/⟨S̃ : S⟩^{2} from 2.3. The last assertion is obvious. This proves 3.5.

Let now S be a Z_{p}-algebra that is tame at q but that is not necessarily local. Then S is the product of the localizations S_{p} of S at its maximal ideals p, of which there are only finitely many, and each S_{p} is a local Z_{p}-algebra that is tame at q. We shall denote the residue class field degree and the ramification index of S_{p} over Z_{p} by f(p) and e(p), respectively.

Proposition 3.6. Let S be a Z_{p}-algebra that is tame at q, and put a = {x ∈ S : Tr(xS) ⊂ qZ_{p}}, where Tr is the trace of S over Z_{p}. Denote by S̃ the integral closure of S in S ⊗_{Z_{p}} Q_{p}. Then S/a is free as a Z_{p}/qZ_{p}-module, and we have

(a) Δ_{S/Z_{p}} = q^{∑_{p} f(p)(e(p)−1)}Z_{p} = q^{[S:Z_{p}]−[S/a:Z_{p}/qZ_{p}]}Z_{p};

(b) for each positive integer i the Z_{p}/qZ_{p}-module (a^{i−1} + qS)(a^{i+1} + qS)/(a^{i} + qS)^{2} is free of rank ∑_{p, e(p)=i} f(p);

(c) if a = qS, then Δ_{S/Z_{p}} = (1) and S̃ = S; (d) if a ≠ qS, then q divides Δ_{S/Z_{p}}, we have qp^{−1}S̃ ⊂ S, and S̃ equals S if and only if

q ∉ p^{2}Z_{p};

(e) if e denotes the least common multiple of the numbers e(p), with p ranging over the maximal ideals of S, then we have Δ_{S̃/Z_{p}} = (1) if and only if qZ_{p} is the eth power of an ideal of Z_{p}.

Proof. The ideal a is the product of the similarly defined ideals a_{p} of the rings S_{p}. By 3.3(c), each of the Z_{p}/qZ_{p}-modules S_{p}/a_{p} is free, so the same is true for S/a. To prove (a), we may likewise assume that S is local, in which case it suffices to apply 3.3(b), 3.2, and 3.3(c). In the same way (b) follows from 3.3(d). If a = qS, then we have [S : Z_{p}] − [S/a : Z_{p}/qZ_{p}] = 0, which implies the first statement of (c); the second follows by 2.3. Next suppose that a ≠ qS. Then we have [S : Z_{p}] − [S/a : Z_{p}/qZ_{p}] > 0, which implies the first statement of (d). Also, for at least one p we have [S_{p} : Z_{p}] − [S_{p}/a_{p} : Z_{p}/qZ_{p}] > 0, which means that e_{p} > 1. Since S is integrally closed in S ⊗_{Z_{p}} Q_{p} if and only if each S_{p} is integrally closed in S_{p} ⊗_{Z_{p}} Q_{p}, it now follows from 3.5 that this is also equivalent to q ∉ p^{2}Z_{p}. This proves (d). Finally, (e) follows from the last statement of 3.5. This proves 3.6.

The main result of this section enables us to recognize whether a given Z_{p}-algebra is tame at q, provided that it has sufficiently small degree over Z_{p}.

Theorem 3.7. Let p be a prime number, and let q ∈ pZ_{p}, q ≠ 0, where Z_{p} denotes the ring of p-adic integers. Let further S be a Z_{p}-algebra that admits a finite basis, with [S : Z_{p}] < p. Put a = {x ∈ S : Tr(xS) ⊂ qZ_{p}}, where Tr is the trace of S over Z_{p}. Then S is tame at q if and only if a : a = S and both a/qS and (S : a)/S are free as Z_{p}/qZ_{p}-modules.

Proof. We first remark that by 2.9, applied to R = Z_{p}/qZ_{p}, L = S/qS, and N = a/qS, the Z_{p}/qZ_{p}-module a/qS is free if and only if S/a is. Hence we may replace a/qS by S/a in the statement of Theorem 3.7.

For the proof of the “only if” part we may assume that S is not only tame at q but also local, as in the proof of 3.6. Then by 3.3(c) we have a = πS, so a : a = S. Also, S/a is free over Z_{p}/qZ_{p}, by 3.3(c), and the same applies to (S : a)/S = π^{−1}S/S ≅ S/πS = S/a. This proves the “only if” part.

Next we prove the “if” part. Assume that a : a = S and that both S/a and (S : a)/S are free as Z_{p}/qZ_{p}-modules. We first reduce to the case that S is local. Since S is free of finite rank as a Z_{p}-module, we may identify S with the projective limits of the rings S/p^{n}S, n ≥ 0. From 2.4(a) we know that there is a positive integer t such that ∏_{p} p ⊃ pS ⊃ ∏_{p} p^{t}, where p ranges over the prime ideals of S containing p. It follows that the system of ideals (p^{n}S)_{n=1}^{∞} is cofinal with the system of ideals (∏_{p} p^{n})_{n=1}^{∞}, so that S is also the projective limit of the rings S/(∏_{p} p^{n}). For each n, the ideals p^{n} are pairwise coprime, so S/( ∏_{p} p^{n}) ≅ ∏_{p} S/p^{n}. Hence if we let S_{p} denote the projective limit of the rings S/p^{n}, n ≥ 0, then we have an isomorphism S ≅ ∏_{p} S_{p} of Z_{p}-algebras, the product extending over the prime ideals p of S containing p. In addition, each S_{p} is local, and it is actually the localization of S at p. As a Z_{p}-module, each S_{p} is a direct summand of S, so it is free, with [S_{p} : Z_{p}] ≤ [S : Z_{p}] < p. Also, the assumptions on a carry over to each S_{p}. Since S is tame if each of the S_{p} is, we conclude that we may assume that S is local, which we do for the remainder of the proof.

Denote by p the maximal ideal of S. As above, we have p ⊃ pS ⊃ p^{t} for some positive integer t, and S is p-adically complete.

We first prove that p = pS + a. From [S : Z_{p}] < p it follows that Tr 1 = [S : Z_{p}] · 1 ∉ qZ_{p}, so 1 ∉ a. This implies that a ⊂ p, so pS + a ⊂ p. To prove the other inclusion, we first note that the definition of a gives rise to an exact sequence

0 → a/qS → S/qS → Hom(S/a, Z_{p}/qZ_{p}) → 0

of Z_{p}/qZ_{p}-modules, the third arrow mapping x mod qS to the map sending y mod a to Tr(xy) mod qZ_{p}; this arrow is surjective because S/a and Hom(S/a, Z_{p}/qZ_{p}) are free of the same rank over Z_{p}/qZ_{p} and hence have the same cardinality. Since S/a is Z_{p}/qZ_{p}-free, we have a natural isomorphism Hom(S/a, Z_{p}/qZ_{p}) ⊗_{Z_{p}/qZ_{p}} F_{p} ≅ Hom((S/a) ⊗_{Z_{p}/qZ_{p}} F_{p}, F_{p}) = Hom(S/(pS + a), F_{p}). Hence if we tensor the exact sequence above with F_{p} we obtain an exact sequence

a/(qS + pa) → S/pS → Hom(S/(pS + a), F_{p}) → 0 of F_{p}-vector spaces. From this sequence we deduce that p ⊂ pS + a, as follows. Let x ∈ p. We have p^{t} ⊂ pS, so for any y ∈ S the multiplication-by-xy map S/pS → S/pS is nilpotent and has therefore trace 0 when considered as an F_{p}-linear map. This implies that x mod pS belongs to the kernel of the map S/pS → Hom(S/(pS +a), F_{p}). This kernel equals the image of a/(qS + pa), so that x ∈ pS + a. This completes the proof of the equality p = pS + a.

The next step in the proof is the construction of an unramified subring T of S that has the same residue class field as S. Let k = S/p be the residue class field of S, and let T be the unique unramified local Z_{p}-algebra with residue class field T/pT ≅ k. If T ≅ Z_{p}[Y]/gZ_{p}[Y], then by Hensel’s lemma g has a zero in S (see [1, Exercise 10.9]); at this point we use that S is p-adically complete. This gives a Z_{p}-algebra homomorphism T → S, which makes S into a T -algebra. Let e be the dimension of S/pS as a vector space over T/pT = k. By Nakayama’s lemma there is a surjective T -linear map T^{e} → S. We have e · [T : Z_{p}] = e · [k : F_{p}] = [S/pS : F_{p}] = [S : Z_{p}], so comparing Z_{p}-ranks we see that the map T^{e} → S must be injective. This implies in particular that the map T → S is injective. Hence we may view T as a subring of S, and S is free of rank e as a T -module.

In the definition of a we may now replace Z_{p} by T, i. e., we have a = {x ∈ S : Tr_{S/T} (xS) ⊂ qT }, where Tr_{S/T} is the trace map for the extension T ⊂ S. This is an immediate consequence of the formula Tr = Tr_{T/Z_{p}} ∘ Tr_{S/T} and the fact that qT = {x ∈ T : Tr_{T/Z_{p}}(xT) ⊂ qZ_{p}}; the last equality holds because T is unramified over Z_{p}.

Any T/qT -module N that is finitely generated and free as a Z_{p}/qZ_{p}-module is also free as a T/qT -module, the rank being [T : Z_{p}] times as small; one proves this by lifting a k-basis of N/pN to a T/qT -basis of N, in the same way as we proved above that S is free as a T -module. Hence the hypotheses on a now imply that S/a and (S : a)/S are free as T/qT -modules. The rank of S/a over T/qT can be computed over the residue class field; using that pS + a = p we find that [S/a : T/qT] = [S/(pS + a) : T/pT] = [k : k] = 1, so the natural map T/qT → S/a is an isomorphism.

Next we prove that a is invertible. From a ⊂ p and 2.4(b) we see that S : a ≠ S, so the module (S : a)/S is non-zero. Also, it is free over T/qT = S/a, so the annihilator of (S : a)/S in S/a is zero. This means that S : (S : a) = a. From our hypothesis a : a = S and 2.5 it now follows that a is invertible, so a(S : a) = S.

We deduce that a is principal. Namely, choose ρ ∈ a with ρ(S : a) ⊄ p. Then 1 ∈ ρ(S : a), and multiplying by a we find a ⊂ ρS. Since we also have ρS ⊂ a this proves that a = ρS.

We claim that S = T [ρ]. To see this, we first note that T [ρ] is local with maximal ideal p′ = p ∩ T [ρ]. This follows from the fact that S is integral over T [ρ] and local. Next, from T/qT ≅ S/a = S/ρS we see that S = T + ρS and therefore S = T [ρ] + p′S. Applying Nakayama’s lemma to the T [ρ]-module S we now see that S = T [ρ].

Let f ∈ T [X] be the characteristic polynomial of ρ over T. Then f is a monic polynomial of degree e, and f(ρ) = 0. Hence there is a surjective T -algebra homomorphism T [X]/fT [X] → T [ρ] = S sending X mod f to ρ, and comparing ranks over T we see that this is an isomorphism.

We show that f is an “Eisenstein polynomial at q”, i. e., if we write f = ∑_{i=0}^{e} a_{i}X^{e−i} then a_{j} ∈ qT for 0 < j < e and a_{e} ∈ qT^{∗}. We have

T/qT ≅ S/a = T [ρ]/ρT [ρ] ≅ T [X]/(fT [X] + XT [X]) ≅ T/f(0)T = T/a_{e}T,

and therefore a_{e} ∈ qT^{∗}. For each positive integer i, the element p_{i} = Tr_{S/T} (ρ^{i}) of T belongs to Tr_{S/T} a and therefore to qT. Hence Newton’s formulas, which assert that ja_{j} + ∑_{i=1}^{j} p_{i}a_{j−i} = 0 for 1 ≤ j ≤ e, imply that ja_{j} ∈ qT for 1 ≤ j ≤ e. From p > [S : Z_{p}] ≥ e it now follows that a_{j} ∈ qT.

The next step is to modify ρ so that its eth power becomes a unit times q. From f(ρ) = 0 and the fact that f is Eisenstein at q we see that ρ^{e} = − ∑_{i=1}^{e} a_{i}ρ^{e−i} ∈ −a_{e}(1 + ρS). Hensel’s lemma and the fact the gcd(e, p) = 1 imply that each element of 1 + ρS is an eth power in S^{∗}. Hence there exists v ∈ S^{∗} such that π = ρv satisfies π^{e} = −a_{e}, which equals uq for some u ∈ T^{∗}.

Since π is, just as ρ, a generator of the ideal a, anything that we proved for ρ applies to π as well. In particular, there is a monic polynomial h ∈ T [X] of degree e such that there is an isomorphism T [X]/hT [X] ≅ S of T -algebras that maps X mod h to π. Then X^{e} − uq is divisible by h, and comparing degrees and leading coefficients we see that X^{e} − uq = h. Therefore S ≅ T [X]/(X^{e} − uq)T [X], and S is tame at q. This proves Theorem 3.7.

Remark. With only minor changes, the results of this section and their proofs can be carried over to the case that Z_{p} and q are replaced by a one-dimensional noetherian complete local ring R and an element q of the maximal ideal of R that is not a zero-divisor; in 3.1, 3.5, and 3.6(c, d, e) it should in addition be required that R is regular, so that it is a complete discrete valuation ring.

4. Tame orders Let A be an order and let q be a positive integer. For a prime number p, we write A_{p} = A ⊗_{Z} Z_{p}. We call A tame at q if for each prime number p dividing q the Z_{p}-algebra A_{p} is tame at q in the sense of the previous section. Note that, as in the third paragraph of the proof of Theorem 3.7, one has A_{p} ≅ ∏_{p} A_{p}, where p ranges over the prime ideals of A containing p and A_{p} denotes the completion of A at p; this implies that the present definition of “tame” coincides with that given in the introduction.

We denote by O the maximal overorder of A, as in 2.3, and by Tr the trace of A over Z.

Proposition 4.1. Let A be an order and let q be a positive integer with the property that each prime dividing q exceeds [A : Z]. Put a = {x ∈ A : Tr(xA) ⊂ qZ}. Suppose that both a/qA and (A : a)/A are free when considered as Z/qZ-modules, and that a : a = A. Then A is tame at q. In addition, we have:

(a) if a = qA, then gcd(q, Δ_{A}) = 1 and A is maximal at q;

(b) if a ≠ qA, then q divides Δ_{A}, and the primes dividing gcd(q, ⟨O : A⟩) are those that appear at least twice in q.

Proof. Let p be a prime dividing q. One easily verifies that a_{p} = a ⊗_{Z} Z_{p} may be identified with the ideal {x ∈ A_{p} : Tr(xA_{p}) ⊂ qZ_{p}} of A_{p}, and that O_{p} = O ⊗_{Z} Z_{p} may be identified with the integral closure of A_{p} in A_{p} ⊗_{Z_{p}} Q_{p}. Proposition 4.1 now follows immediately from Theorem 3.7 and Proposition 3.6, applied to S = A_{p}.

Proposition 4.2. Let A be an order, let q > 1 be an integer dividing Δ_{A}, and suppose that A is tame at q. Put a = {x ∈ A : Tr(xA) ⊂ qZ}. Then there exists an integer h with 2 ≤ h ≤ [A : Z] for which the Z/qZ-module (a^{h−1} + qA)(a^{h+1} + qA)/(a^{h} + qA)^{2} is non-zero; if for some such h that module is actually free over Z/qZ, and gcd(q, Δ_{O}) = 1, then q is an hth power.

Proof. Let p be a prime number dividing q, and let a_{p} = a ⊗_{Z} Z_{p} ⊂ A_{p}. Since p divides Δ_{A}, it divides Δ_{A_{p}/Z_{p}}. Applying 3.6(a) we see that there exists a maximal ideal p of A_{p} with e(p) > 1. By 3.6(b), we have (a_{p}^{h−1} +qA_{p})(a_{p}^{h+1} +qA_{p})/(a_{p}^{h} +qA_{p})^{2} ≠ 0 for h = e(p), so also (a^{h−1} + qA)(a^{h+1} + qA)/(a^{h} + qA)^{2} ≠ 0. This implies the first assertion, since 2 ≤ h ≤ [A : Z].

Next let h be a positive integer for which M = (a^{h−1} + qA)(a^{h+1} + qA)/(a^{h} + qA)^{2} is a free non-zero Z/qZ-module, and suppose that gcd(q, Δ_{O}) = 1. Let p again be a prime number dividing q. Tensoring M with Z_{p} we see that the Z_{p}/qZ_{p}-module (a_{p}^{h−1} + qA_{p})(a_{p}^{h+1} + qA_{p})/(a_{p}^{h} + qA_{p})^{2} is free of positive rank. Thus e(p) = h for some maximal ideal p of A_{p}, by 3.6(b). Since p does not divide Δ_{O/Z}, we have Δ_{O_{p}/Z_{p}} = (1), so by 3.6(e) the ideal qZ_{p} is the hth power of an ideal of Z_{p}. This means that the number of factors p in q is divisible by h. Because p is arbitrary, this implies that q is an hth power. This proves 4.2.

The following result describes a natural class of examples of tame orders.

Proposition 4.3. Let f ∈ Z[X] be a monic polynomial of which the discriminant Δ is non-zero, and let q be the largest divisor of Δ that is not divisible by any prime number p ≤ deg f. Put A = Z[X]/fZ[X] = Z[α], where α = (X mod f). Then A is tame at q if and only if A/f′(α)A has an element of additive order q.

Remark. Note that the order of A/f′(α)A equals |Δ|, which is divisible by q. The proposition asserts that A is tame at q if and only if the exponent of A/f′(α)A is divisible by q as well. This condition is satisfied, for example, if A/f′(α)A ≅ Z/ΔZ.

Proof. Let p be a prime number dividing q, and put A_{p} = A ⊗_{Z} Z_{p}. As we saw in 2.8, the complementary module A_{p}^{†} of A_{p} over Z_{p} is given by A_{p}^{†} = f′(α)^{−1}A_{p}, and the order of A_{p}^{†}/A_{p} equals that of Z_{p}/qZ_{p}. Assume now first that A is tame at q. Then by 3.3(a) the Z_{p}/qZ_{p}-module A_{p}^{†}/A_{p} is free, and the rank must be 1. It follows that we have A_{p}/f′(α)A_{p} ≅ Z_{p}/qZ_{p}. Since this is true for each prime number p dividing q one concludes that A/f′(α)A contains an element of order q. This proves the “only if” part.

For the “if” part, assume that A/f′(α)A contains an element of order q. Then we have A_{p}^{†}/A_{p} ≅ A_{p}/f′(α)A_{p} ≅ Z_{p}/qZ_{p}. Hence the ideal a_{p} = {x ∈ A_{p} : Tr(xA_{p}) ⊂ qZ_{p}} is given by a_{p} = (qA_{p}^{†}) ∩ A_{p} = qA_{p}^{†} = qf′(α)^{−1}A_{p}. Then we have a_{p}/qA_{p} = qA_{p}^{†}/qA_{p} ≅ A_{p}^{†}/A_{p} ≅ Z_{p}/qZ_{p}, which is free over Z_{p}/qZ_{p}. Also, because a_{p} is principal we have a_{p} : a_{p} = A_{p} and (A_{p} : a_{p})/A_{p} ≅ A_{p}/a_{p}, which is free over Z_{p}/qZ_{p} because of 2.9. From Theorem 3.7 it now follows that the Z_{p}-algebra A_{p} is tame at q. Therefore A is tame at q. This proves 4.3.

Proposition 4.4. Let A be an order, and let q and q′ be positive integers dividing Δ_{A} such that A is tame both at q and at q′. Let p be a prime number dividing gcd(q, q′). Then the number of factors p in q equals the number of factors p in q′. Also, the number of factors p dividing the exponent of the finite abelian group O/A is smaller than the number of factors p in q.

Proof. The order A_{p} over Z_{p} is tame at q, and because q divides Δ_{A} not all ramification indices of A_{p} are equal to 1. Thus by 3.4 the ideal qZ_{p} is uniquely determined by A_{p}. Therefore we have qZ_{p} = q′Z_{p}. The last assertion follows from 3.6(d). This proves 4.4.

Suppose that the order A is tame at q. If q is not squarefree, then A is not necessarily maximal at q, by 4.1(b), but it does have many agreeable properties that distinguish it from arbitrary orders. These can be deduced from the results of Section 3. For example, each maximal ideal p of A containing q satisfies dim_{A/p} p/p^{2} ≤ 2, which means that locally (and even globally) it can be generated by two elements (see 3.2). In geometric terms, this means that all singularities of A are plane singularities. The following two propositions mention a few additional properties of orders that are tame at q. Roughly speaking, they express that even though not all fractional A-ideals need be invertible, at least many of them are (cf. 2.7). Since these results do not play a logical role in the rest of the paper we only sketch their proofs.

Proposition 4.5. Let A be an order and let q be a positive integer, and suppose that A is tame at q. Put a = {x ∈ A : Tr(xA) ⊂ qZ}, where Tr denotes the trace of A over Z. Then all fractional A-ideals that one can obtain from A, a and qA by applying the operations +, ∩, ·, :, (− ∩ Q) · A a finite number of times are invertible, and these ideals form, under multiplication, a finitely generated free abelian group.

Proof. In the situation of Proposition 3.3—with Z and A replaced by Z_{p} and a local Z_{p}- algebra S that is tame at q—the corresponding set of ideals is equal to the set {π^{n}S : n ∈ Z}, and the assertions are clear. The reduction of 4.5 to the situation of 3.3 is straightforward. This proves 4.5.

Proposition 4.6. Let A be an order and let q be a positive integer, and suppose that A is tame at q. Then for each prime number p dividing q the order A_{p} over Z_{p} is a Gorenstein ring. If in addition A is maximal at all prime numbers not dividing q, then A is a Gorenstein ring.

Proof. In the local situation of 3.3 this follows from 2.7 and the fact that S^{†} is invertible (3.3(a)). The first assertion follows immediately. If A is maximal at all primes p not dividing q, then A_{p} is a Gorenstein ring for all p. From this it follows in a straightforward way that A itself is a Gorenstein ring. This proves 4.6.

5. Basic algorithms All algorithms in this section and the next one are deterministic. For a general discussion of basic notions related to algorithms in algebraic number theory we refer to [18, Section 2]. In particular, one finds in [18, 2.9] the definition of the phrase “given an algebraic number field K” that occurs in the theorems formulated in the introduction. In the present section we elaborate upon several points that were only briefly mentioned in [18], and we provide some of the proofs that were left out in [18].

5.1. Linear algebra (cf. [18, 2.4]). Let q ∈ Z, q > 1. If q is a prime number, then Z/qZ is a field, and the traditional algorithms from linear algebra can be used to do computations with vector spaces over Z/qZ. We shall see that if q is not necessarily prime, then the same algorithms lead either to a non-trivial divisor q′ of q or to a result that can be interpreted in terms of free modules over Z/qZ. Here we call a divisor q′ of q non-trivial if 1 < q′ < q.

As in [18, 2.4], giving a free Z/qZ-module of finite rank means giving its rank n (in unary). The elements of such a module are encoded as sequences of n elements of Z/qZ. Homomorphisms between two such modules are encoded as matrices in the usual way. A free submodule of a free module is encoded as a sequence of elements of the free module that is a basis for the submodule. When we write, in this paper, that an algorithm determines a submodule of a free module, we will always mean that it determines a basis for that submodule. In particular, if an algorithm determines a submodule, then that submodule is free.

Proposition 5.2. There is a polynomial time algorithm that, given an integer q > 1 and a homomorphism f from one free Z/qZ-module of finite rank to another one, either determines a non-trivial divisor q′ of q or determines the kernel of f and the image of f. There is a polynomial time algorithm that, given an integer q > 1 and two free submodules of a free Z/qZ-module of finite rank, either determines a non-trivial divisor q′ of q or determines the sum and the intersection of these submodules.

Proof. An m×n matrix H = (h_{ij}) with entries h_{ij} ∈ Z/qZ is said to be row reduced if the following conditions are satisfied: (i) there exists k ≤ m such that the ith row of H is zero if and only if i > k; (ii) for each i ≤ k, there exists j_{i} ∈ {1, 2, …, n} such that h_{ij_{i}} = 1, h_{ij} = 0 for j < j_{i}, and h_{i′j_{i}} = 0 for all i′ ≠ i; (iii) j_{i} < j_{i′} whenever 1 ≤ i < i′ ≤ k.

Let H = (h_{ij}) be a row-reduced m × n matrix over Z/qZ, and let j_{1}, j_{2}, …, j_{k} ∈ {1, 2, …, n} be as above. Then one verifies easily that several modules associated to H are free. First of all, the row space of H, which is the submodule of (Z/qZ)^{n} generated by the rows of H, is free of rank k, a basis being formed by the non-zero rows of H. Secondly, the column space of H, which is the submodule of (Z/qZ)^{m} generated by the columns of H, is likewise free of rank k, a basis being formed by the columns with indices j_{1}, j_{2}, …, j_{k}. Thirdly, the nullspace of H, which equals {x ∈ (Z/qZ)^{n} : Hx = 0}, is free of rank n − k, and one obtains a basis by taking, for each j ∈ {1, 2, …, n} − {j_{1}, j_{2}, …, j_{k}}, the vector whose j_{i}th coordinate equals −h_{ij}, for 1 ≤ i ≤ k, whose jth coordinate equals 1, and that is 0 at the remaining n − k − 1 positions.

It is well-known from elementary textbooks in linear algebra that, if q is prime, so that Z/qZ is a field, there exists for every m × n matrix H over Z/qZ an invertible m × m matrix U over Z/qZ such that UH is row reduced. In addition, given H one can find the row reduced matrix UH by performing the following operations O(m^{2}) times: (i) interchange two rows; (ii) divide a non-zero row by its first non-zero entry; (iii) add a multiple of one row to another one.

If q is not necessarily prime, the same operations can still be performed, except that (ii) is impossible if the first non-zero entry a mod q that one wishes to divide by does not have an inverse. In that case the divisor q′ = gcd(a, q) of q is non-trivial. It follows that there is a polynomial time algorithm that, given q and an m × n matrix H over Z/qZ, either determines a non-trivial divisor q′ of q or a row reduced matrix that is obtained from H by finitely many applications of the three operations above. Clearly, the matrix that is obtained in the latter case is of the form UH, where U is an invertible m × m matrix over Z/qZ.

We can now prove 5.2. Let f: (Z/qZ)^{n} → (Z/qZ)^{m} be a homomorphism, and let it be given by the m × n matrix H. Then the image of f is the column space of H, and the kernel of f is the nullspace of H. We can in polynomial time either determine a non-trivial divisor q′ of q or a row-reduced matrix of the form UH, with U invertible. Assume that we are in the latter case. As we saw above, we can write down a basis for the nullspace of UH, and this is the same as the nullspace of H. Further, if the columns with indices j_{1}, j_{2}, …, j_{k} form a basis for the column space of UH, then the columns of H with the same indices form a basis for the column space of H.

Determining the sum and intersection of two free submodules V_{1}, V_{2} of (Z/qZ)^{n} can be reduced to determining images and kernels, as follows. Let f: V_{1} ⊕V_{2} → (Z/qZ)^{n} be the map that sends (x_{1}, x_{2}) to x_{1} + x_{2}. Then V_{1} + V_{2} is equal to the image of f, and V_{1} ∩ V_{2} is the isomorphic image of the kernel of f under the natural projection V_{1} ⊕ V_{2} → V_{1}. This proves 5.2. 5.3. Hermite normal form. We shall say that an m × n matrix H = (h_{ij}) with entries h_{ij} ∈ Z is in Hermite normal form if the following conditions are satisfied: (i) there exists k ≤ m such that the ith row of H is zero if and only if i > k; (ii) for each i ≤ k, there exists j_{i} ∈ {1, 2, …, n} such that h_{ij_{i}} > 0, h_{ij} = 0 for j < j_{i}, and 0 ≤ h_{i′j_{i}} < h_{ij_{i}} for all i′ < i; (iii) j_{i} < j_{i′} whenever 1 ≤ i < i′ ≤ k. This definition is a little more general than the one commonly found in the literature (see [10]), so as to accommodate matrices of rank less than n. For each m × n matrix H over Z there is a unique matrix of the form UH that is in Hermite normal form, and for which U is an invertible m × m-matrix over Z (however, U is not necessarily unique); the matrix UH is called the Hermite normal form of H. Proposition 5.4. There is a polynomial time algorithm that given an m × n matrix H = (h_{ij}) over Z finds an invertible m × m matrix U over Z for which UH is in Hermite normal form. Proof. First suppose that H has rank n. In this case the Hermite normal form UH can be found in polynomial time by [10, Theorem 2.1] (applied to the transpose of H), and U can be found in polynomial time as well (see [10, Section 5, end]). To reduce the general case to the case of rank n, we let J be the set of those j, 1 ≤ j ≤ n, for which the jth column of H is not a Q-linear combination of the earlier columns. If J = {j_{1}, j_{2}, …, j_{k}} with j_{1} < j_{2} < … < j_{k}, then k = rank H, and j_{l} is, for each l ∈ {1, 2, …, k}, equal to the smallest value of j for which the matrix formed by columns j_{1}, …, j_{l−1}, j of H has rank l. Since ranks of matrices over Z can be computed in polynomial time (see [10, Proposition 2.3]), this shows that J can be determined in polynomial time. The m × k matrix H_{J} that is formed by columns j_{1}, …, j_{k} of H now has rank k, so by the above we can find, in polynomial time, the Hermite normal form UH_{J} of H_{J}, as well as the matrix U. It is easy to verify that UH is then also in Hermite normal form. This proves 5.4. 5.5. Free abelian groups of finite rank (cf. [18, 2.5]). Giving a free abelian group of finite rank means giving its rank n (in unary). The elements of such a group are encoded as sequences of n integers, and homomorphisms between two such groups are encoded as matrices, in the usual way. A subgroup of a free abelian group of finite rank is itself free, and it is encoded by means of a sequence of elements that is a basis for the subgroup. Proposition 5.6. There is a polynomial time algorithm for each of the following problems: given a homomorphism f from one free abelian group of finite rank to another one, find the kernel of f and the image of f; given two subgroups of a free abelian group of finite rank, find the sum and the intersection of these subgroups; given a homomorphism f from one free abelian group of finite rank to another one, and a subgroup L of the latter, find f^{−1}L. Proof. Let f: Z^{m} → Z^{n} be a homomorphism, and let it be given by the transpose of the m × n matrix H. By 5.4, we can find an invertible m × m matrix U such that UH is in Hermite normal form. Then the non-zero rows of UH form a basis for the image of f, and if k is equal to the number of non-zero rows of UH, so that k = rank H, then the last m−k rows of U^{−1} form a basis for the kernel of f. This implies the assertion on finding the kernel and image of f. Finding sums and intersections of subgroups can be reduced to finding kernels and images, as in the proof of 5.2. Finally, let f: F_{1} → F_{2} be a homomorphism, and let L ⊂ F_{2} be a subgroup. Denote by g: F_{1} ⊕ L → F_{2} the map sending (x, y) to f(x) − y. Then f^{−1}L is the isomorphic image of the kernel of g under the projection F_{1} ⊕ L → F_{1}. This implies the assertion concerning f^{−1}L. This proves 5.6.

5.7. Orders and fractional ideals. As in [18, 2.7 and 2.10], an order A will be given by its degree n over Z and the multiplication map A ⊗ A → A. This comes down to specifying a system of n^{3} integers a_{ijk} such that ω_{i}ω_{j} = ∑_{k=1}^{n} a_{ijk}ω_{k} for some basis ω_{1}, ω_{2}, …, ω_{n} of A over Z. Note that one can verify in polynomial time whether or not a given system of n^{3} integers a_{ijk} encodes an order, by checking the ring axioms and the non-vanishing of the discriminant Δ_{A} in a straightforward way; here Δ_{A} is computed directly from its definition (see 2.2). An ideal of an order A will be specified by means of a basis of the ideal over Z, expressed in terms of the given basis of A over Z, as was done for subgroups in 5.5; this may for practical purposes not always be the most efficient representation, but for theoretical purposes it will suffice. To make the representation of an ideal a unique, we may require that the given basis consists of the rows of a matrix in Hermite normal form. In that case all entries of the matrix are bounded by the index of a in A. This is often useful if an algorithm deals with many ideals and one wishes to control the growth of the numbers occurring in the algorithm. A fractional ideal a is given by means of a pair d, b, where d is a positive integer and b is an ideal of A of finite index; then a = d^{−1}b. This is unique if we require that d is coprime to the largest integer e for which b ⊂ eA.

Proposition 5.8. There are polynomial time algorithms that given an order A and fractional A-ideals a_{1}, a_{2}, determine a_{1} + a_{2}, a_{1} · a_{2}, a_{1} ∩ a_{2}, and a_{1} : a_{2}.

Proof. For sum and intersection this follows directly from Proposition 5.6. The computation of a_{1} · a_{2} is easily reduced to the case that a_{1}, a_{2} are contained in A. In that case, a_{1} · a_{2} is the image of the multiplication map a_{1} ⊗ a_{2} → A, which can be calculated by Proposition 5.6. The computation of a_{1} : a_{2} can be reduced to the case that a_{2} ⊃ A ⊃ a_{1}. In that case, we have a_{1} : a_{2} ⊂ A : A = A, which implies that a_{1} : a_{2} is equal to the inverse image of Hom(a_{2}, a_{1}) under the map A → Hom(a_{2}, a_{2}) that sends x ∈ A to the multiplication-by-x map. This inverse image can, again, be calculated by Proposition 5.6. This proves 5.8.

5.9. Overorders. Let A be an order, given by integers a_{ijk} as above. Overorders of A and their fractional ideals will be represented as fractional ideals of A itself. Several algorithms in Section 6 compute many overorders of A, and for the complexity analysis of these algorithms it is important to note that the length of the data encoding any overorder B of A is uniformly bounded by a polynomial function of ∑_{i,j,k} log(|a_{ijk}|+2), i. e., of the length of the data encoding A itself. This follows from what was said above about fractional ideals and the fact that the index of A in B divides Δ_{A}.

6. Approximating maximal orders In this section we prove the results stated in the introduction. We begin with an auxiliary algorithm that corresponds to the case that the number m in Theorem 1.2 is a prime number.

Algorithm 6.1. We describe an algorithm that, given an order A and a prime number p, determines an overorder B of A that is maximal at p. The algorithm begins by putting B = A. Let t be the least positive integer for which p^{t} ≥ [A : Z].

Calculate the kernel b of the F_{p}-linear map B/pB → B/pB that sends every x ∈ B/pB to x^{p^{t}}, as well as the inverse image a of b under the natural map B → B/pB; this can be done by the algorithms of Section 5. Calculate the overorder B′ = a : a of B (see 5.8). If B′ = B, then the algorithm stops. If B′ ≠ B, then replace B by B′ and iterate. This completes the description of the algorithm.

Proposition 6.2. Given an order A and a prime number p, Algorithm 6.1 determines in polynomial time the unique overorder B of A that is maximal at p and for which ⟨B : A⟩ is a power of p.

Proof. Let B be any overorder of A that is encountered in the algorithm. Then B/pB is a finite ring containing F_{p}, and we have [B/pB : F_{p}] = [B : Z] = [A : Z]. Let y ∈ B/pB. Then two of the subspaces

B/pB ⊃ y(B/pB) ⊃ y^{2}(B/pB) ⊃ … ⊃ y^{[A:Z]}(B/pB) ⊃ y^{[A:Z]+1}(B/pB)

of B/pB must have the same dimension over F_{p} and are therefore equal. Hence there exists i, 0 ≤ i ≤ [A : Z], such that y^{i}(B/pB) = y^{i+1}(B/pB), and this space is then equal to y^{j}(B/pB) for all j ≥ i. In particular, y is nilpotent if and only if y^{[A:Z]} = 0, and if and only if y^{p^{t}} = 0. This proves that an element x of B belongs to a if and only if (x mod pB) belongs to the nilradical of B/pB. Therefore a is an ideal of B containing pB. This implies that B ⊂ B′ ⊂ p^{−1}B, so that ⟨B′ : B⟩ is a power of p. It follows that either B′ = B or Δ_{B′} = Δ_{B}/p^{2s} for some positive integer s. Hence the algorithm goes through at most (log |Δ_{A}|)/ log(p^{2}) iterations before it stops. From Section 5 one sees that each iteration can be done in polynomial time. Hence the entire algorithm runs in polynomial time. We also find that ⟨B : A⟩ is a power of p for each B that occurs in the algorithm.

Let now B be the final overorder that is obtained. Then we have B = B′ = a : a, so by 2.4(c) the order B is maximal at p. From gcd(p, ⟨O : B⟩) = 1 and the fact that ⟨B : A⟩ is a power of p it follows that B/A is the p-primary subgroup of the quotient O/A of additive groups. This determines B uniquely. This completes the proof of 6.2.

The second auxiliary algorithm corresponds to the case that the number m in Theorem 1.2 is built up from prime numbers that exceed the degree of A over Z, but without the squarefree-ness assumption.

Algorithm 6.3. In this algorithm, an order A and an integer q > 1 are given with the property that each prime divisor p of q satisfies p > [A : Z]. The algorithm determines an overorder B of A and a divisor q′ of q, such that either q′ is non-trivial or B is well-behaved, as expressed in 6.4. The algorithm begins by putting B = A.

Let a be the B-ideal {x ∈ B : Tr(xB) ⊂ qZ}, and b = a/qB. Note that b is the kernel of the map B/qB → Hom(B/qB, Z/qZ) that sends each (x mod q) ∈ B/qB to the map sending (y mod q) to Tr(xy) mod q. Use the algorithm of Proposition 5.2 to find a basis of b over Z/qZ; this fails only if a non-trivial divisor q′ of q is found, in which case the algorithm stops. If it is found that b = 0, then a = qB, and the algorithm stops, with q′ = 1. Now suppose that b ≠ 0, so that a ≠ qB. Determine the overorder B′ = a : a of B (Proposition 5.8). If B′ ≠ B, replace B by B′ and iterate. Next suppose that B′ = B. Determine B : a, and attempt to find a basis of (B : a)/B as a Z/qZ-module, using the algorithm of Proposition 5.2. If this attempt is not successful, then one has found a nontrivial divisor q′ of q, and the algorithm stops. If the attempt is successful, one searches for the smallest integer h > 1 for which (a^{h−1} + qB)(a^{h+1} + qB)/(a^{h} + qB)^{2} is non-zero (we shall see below that h exists and is at most [A : Z]). Using the algorithm of Proposition 5.2, one attempts to find a basis for (a^{h−1} +qB)(a^{h+1} +qB)/(a^{h} +qB)^{2} as a Z/qZ-module. If this attempt is not successful, then one has found a non-trivial divisor q′ of q, and the algorithm stops. If the attempt is successful, one tests whether q is the hth power of an integer; this can be done with Newton’s method, or simply by means of a bisection. If this is not the case, then one stops at this point, with q′ = q. If q is an hth power, then one puts q′ = q^{1/h}, and again the algorithm stops.

Proposition 6.4. Given A and q as in Algorithm 6.3, the method above determines in polynomial time a pair B, q′ such that ⟨B : A⟩ divides a power of q and such that exactly one of (a), (b), (c) is true:

(a) q′ divides q, and 1 < q′ < q;

(b) q′ = 1, the order B is maximal at q, and gcd(q, Δ_{B}) = 1;

(c) q′ = q; the order B is tame at q and has discriminant divisible by q; if O denotes the maximal overorder of A then gcd(q, Δ_{O}) > 1, and the prime numbers dividing gcd(q, ⟨O : B⟩) are exactly those that appear at least twice in q; and the order B is maximal at q if and only if q is squarefree.

Proof. In each iteration of the algorithm, the order B is replaced by a strictly larger one. This implies, as in the proof of 6.2, that the algorithm runs in polynomial time. At each step, a is a B-ideal containing q, so B ⊂ B′ ⊂ q^{−1}B. Hence each index ⟨B′ : B⟩ divides a power of q, and the same is then true for the final index ⟨B : A⟩.

It is clear that the number q′ obtained from the algorithm divides q and satisfies 1 ≤ q′ ≤ q. Hence if (a) is not satisfied then we have q′ = 1 or q′ = q.

First suppose that q′ = 1. This means that, when the algorithm terminates, we have a = qB. Then B : a = q^{−1}B, so a/qB and (B : a)/B are both free as modules over Z/qZ. Also, we have a : a = qB : qB = B. Hence by 4.1(a) the order B is maximal at q and satisfies gcd(q, Δ_{B}) = 1, so we are in case (b).

Next suppose that q′ = q. Then we have a ≠ qB and a : a = B, and the Z/qZ-modules a/qB = b and (B : a)/B are free. Hence by 4.1 the order B is tame at q, and by 4.1(b) all assertions of (c) except the one about gcd(q, Δ_{O}) are true. By 4.2 the integer h that the algorithm is looking for exists, and it satisfies h ≤ [A : Z]. Also, from q′ = q it follows that (a^{h−1} + qB)(a^{h+1} + qB)/(a^{h} + qB)^{2} is free as a Z/qZ-module, and that q is not an hth power. By 4.2 this implies that gcd(q, Δ_{O}) > 1. This proves Proposition 6.4.

An application of Algorithm 6.3 is considered successful if one is in case (b) or (c). If the algorithm is unsuccessful (case (a)), one is inclined to repeat the algorithm first with q′ and next with q/q′ in the role of q. However, in order to keep the logical structure of the resulting algorithm as clear as possible, it is desirable that once an order B has been made maximal or tame at q, one does not change it “at q” any more. This leads to the problem of refining the factorization q = q′ · q/q′ to a factorization into pairwise coprime factors. For an extensive discussion of this problem we refer to [2]. In our case the following simple result suffices. We say that an integer a can be built up from integers c_{1}, …, c_{t} if there exist non-negative integers n_{1}, …, n_{t} such that a = ∏_{i=1}^{t} c_{i}^{n_{i}}.

Proposition 6.5. There is a polynomial time algorithm that, given two integers a and b with a > 1, b > 1, computes a collection of pairwise coprime divisors c_{1}, …, c_{t} of ab, such that c_{i} > 1 for each i and such that each of a and b can be built up from c_{1}, …, c_{t}.

Proof. We first describe the algorithm. It works with finite sequences c_{1}, …, c_{r} of positive integers from which a and b can be built up, with the property that gcd(c_{i}, c_{j}) = 1 whenever |i − j| > 1, and such that there does not exist an index i < r with c_{i} = c_{i+1} = 1. At the beginning of the algorithm the sequence has only the two members a and b. The algorithm proceeds with a given sequence as follows. First it searches for two successive members d, e of the sequence that are both greater than 1. If these cannot be found, then the members of the sequence are pairwise coprime, and the algorithm terminates after deletion of the 1’s in the sequence. Next suppose that d, e can be found. Then one uses the Euclidean algorithm to calculate f = gcd(d, e), and one replaces the terms d, e of the sequence by d/f, f, e/f (in that order). If this creates two successive 1’s in the sequence, delete one of them, and do this until no two successive 1’s remain. Next one iterates the algorithm on the new sequence; it is easy to see that it satisfies the same conditions as the original one. This completes the description of the algorithm.

The correctness proof of this algorithm is straightforward. To estimate the running time we remark that gcd(d, e) can be computed in O((log d)(log e)) steps, for integers d > 1, e > 1 (cf. [11, Exercise 4.5.2.30]). From this it follows by induction that the running time of the algorithm, when starting with a sequence c_{1}, …, c_{r}, is O(∑_{i=1}^{r−1}(log(c_{i}c_{i+1}))^{2}). For the sequence a, b this is O((log(ab))^{2}). This proves 6.5.

We now combine the algorithms above into a single algorithm, which will prove Theorem 1.1. Algorithm 6.6. In this algorithm, an order A and a positive integer m are given. The algorithm determines an overorder B of A and a collection Q of pairwise coprime divisors > 1 of m such that B and Q have the properties listed in Theorem 6.7. At each stage of the algorithm, one has an overorder B of A. The algorithm begins by putting B = A. Also, we put m_{0} = m.

Step 1. For each prime number p ≤ [A : Z] do the following. Test whether p divides m_{0}; if it does, apply Algorithm 6.1 to B and p, replace B by the order that one obtains from 6.1, and divide m_{0} by the largest power of p that divides it. When all primes p ≤ [A : Z] have been processed, m_{0} is equal to the largest divisor of m that is not divisible by any prime number p with p ≤ [A : Z]. If now m_{0} = 1 then the algorithm stops at this point, with Q = ∅.

In each stage of the remaining part of the algorithm one keeps track of two collections M, Q of pairwise coprime divisors > 1 of m_{0}; the elements of M are the numbers that need to be processed, and Q consists of the numbers that have been processed. One begins with M = {m_{0}}, Q = ∅.

Step 2. If the set M is empty, the algorithm stops. Next suppose that M is non-empty. Choose an element q ∈ M, and apply Algorithm 6.3 to B and q. Replace B by the order that one obtains from 6.3. Next there are three cases, depending on the value of the number q′ that is obtained from 6.3. First suppose that q′ = 1. In this case, remove q from the set M and iterate Step 2. Next, suppose that q′ = q. Then transfer q from M to Q, and iterate Step 2. Finally, let it be supposed that 1 < q′ < q. In this case, apply the algorithm of Proposition 6.5 to q′ and q/q′. This gives rise to a collection of pairwise coprime divisors c_{1}, …, c_{t} of q. Now remove q from M, add each of c_{1}, …, c_{t} to M, and iterate Step 2.

This completes the description of the algorithm.

Theorem 6.7. Given an order A and a positive integer m, Algorithm 6.6 determines in polynomial time an overorder B of A and a set Q of pairwise coprime divisors q > 1 of m that have the following properties: all primes dividing ⟨B : A⟩ divide m; each q ∈ Q divides Δ_{B}; the order B is tame at each q ∈ Q and maximal at all prime numbers that divide m but not ∏_{q∈Q} q; if O denotes the maximal overorder of A then the prime numbers dividing gcd(m, ⟨O : B⟩) are exactly those that appear at least twice in some q ∈ Q, and one has gcd(q, Δ_{O}) > 1 for each q ∈ Q; and B is maximal at m if and only if ∏_{q∈Q} q is squarefree.

Proof. We first show that Algorithm 6.6 runs in polynomial time. By 5.9, all orders B that occur in the algorithm are specified by data of length polynomial in the length of the data specifying A itself, and all numbers p, q, q′ are bounded by m. From this and 6.2, 6.4, 6.5 it follows that each time that Algorithm 6.1 or 6.3 or the algorithm of 6.5 is invoked, it runs in time polynomial in the length of the original data. This implies, first of all, that Step 1 runs in polynomial time, since there are at most [A : Z] values of p to consider. To show that Step 2 runs in polynomial time it suffices to show that the number of iterations is polynomially bounded. Each iteration calls Algorithm 6.3 once, and this call is either successful (q′ ∈ {1, q}) or not (1 < q′ < q). If the call is successful, then M is replaced by M − {q}, which implies that q is coprime to any later value of q for which Algorithm 6.3 is called. This implies that the number of successful calls of Algorithm 6.3 is bounded by the number of distinct prime divisors of m_{0}. To bound the number of unsuccessful calls of Algorithm 6.3, we consider the quantity n(M) = ∏_{q∈M} \frac{q}{P (q)}, where P (q) denotes the largest prime divisor of q. Each time that M is changed in the algorithm, n(M) is replaced by a divisor, and this is a proper divisor when the change is made after an unsuccessful call of Algorithm 6.3. Therefore the number of unsuccessful calls of 6.3 is bounded by the total number of prime divisors of m_{0}, counting multiplicities. Since this is O(log m), this concludes the proof that the algorithm runs in polynomial time.

Next we prove that the final B and Q have the properties listed in the theorem. The assertion about ⟨B : A⟩ is clear from 6.2 and 6.4. Note that Q consists of those numbers q for which Algorithm 6.3 has been called successfully in Step 2 with q′ = q. As we have just seen, these numbers q are pairwise coprime, and they divide m. Fix q ∈ Q, and let B_{(q)} be the order that was obtained from the corresponding successful call of Algorithm 6.3. Since later calls of 6.3 concern only numbers that are coprime to q, the first assertion of 6.4 implies that ⟨B : B_{(q)}⟩ is coprime to q. Also, B_{(q)} has the properties listed in Proposition 6.4(c), and from gcd(⟨B : B_{(q)}⟩, q) = 1 it then follows easily that B itself has these properties as well. This implies the assertions made in the theorem, except those relating to prime numbers dividing m that do not divide ∏_{q∈Q} q. Let p be such a prime number. If p ≤ [A : Z], then in the course of Step 1 an order is obtained that is maximal at p, by 6.2, and the overorder B of this order is then also maximal at p. Next let p > [A : Z]. Then p divides m_{0}, so at the beginning of Step 2 the number p divides a member of M, but at the end it doesn’t, since then M = ∅. Since the set of primes dividing the elements of M does not change after an unsuccessful call of 6.3, it must have happened that p divides a number q for which 6.3 was called successfully; and since p does not divide ∏_{q∈Q} q, this successful call must have led to q′ = 1. Thus Proposition 6.4(b) implies that it also led to an order that is maximal at p, and the final B, which is an overorder of this order, is then likewise maximal at p. This completes the proof of Theorem 6.7.

Corollary 6.8. There is a polynomial time algorithm that, given an order A and a positive integer m, decides whether or not gcd(m, Δ_{O}) = 1, where O denotes the maximal overorder of A; in addition, if gcd(m, Δ_{O}) = 1, then the algorithm determines an overorder of A that is maximal at m.

Proof. Run Algorithm 6.6 on A and m to obtain B and Q. If Q ≠ ∅, then gcd(m, Δ_{O}) > 1, by 6.7. If Q = ∅, then B is maximal at m, by 6.7, so gcd(m, Δ_{O}) = 1 if and only if gcd(m, Δ_{B}) = 1. This proves 6.8.

Theorem 6.9. There are polynomial time algorithms that, given an order A, a positive integer m dividing Δ_{A} such that A is tame at m, and one of the following, construct the other:

(a) an integer a > 1 for which a^{2} divides m;

(b) an overorder B ≠ A of A for which ⟨B : A⟩ divides a power of m.

Proof. First suppose that we know an integer a as in (a). Applying Algorithm 6.6 to A and a we find an overorder B of A and a set Q of divisors of gcd(a, Δ_{B}) with the properties listed in Theorem 6.7 (with a in the role of m). Then B is an overorder of A for which ⟨B : A⟩ divides a power of m. We need to prove that B ≠ A. To this end, let p be a prime number dividing a. We distinguish two cases. First suppose that p does not divide any q ∈ Q. In that case, B is maximal at p, by 6.7, but A is not, by 4.1(b), so B ≠ A. Next, suppose that p does divide some q ∈ Q. Then p divides q and m to different positive powers, so 4.4 shows that A is not tame at q; but B is tame at q, by 6.7, so B ≠ A. This shows that (a) can be used to construct (b). For the converse, suppose that a ring B as in (b) is given. Denote by d the exponent of the finite abelian group B/A. From dZ = Z ∩ (A : B) and Section 5 it follows that d can be computed in polynomial time. From B ≠ A we see that d > 1. Proposition 4.4 implies that d divides m, and that every prime factor of m divides m/d. Therefore a = gcd(d, m/d) has the properties in (a). This proves 6.9.

Proof of Theorem 1.1. Consider the following algorithm: given an order A in a number field K, calculate the discriminant m of A, and apply Algorithm 6.6 to A and m to find an order B in K and a finite set Q of integers; let q be the product of the elements of Q.

It is obvious that this algorithm runs in polynomial time. From Theorem 6.7 it follows that B, q have the properties stated in 1.1. This proves Theorem 1.1.

Proof of Theorem 1.2. This is a consequence of Theorem 6.7, since if m is squarefree then so are all its divisors q ∈ Q.

Proof of Theorem 1.4. Let it first be supposed that the ring of integers O of K is given, and let d be the exponent of the abelian group O^{†}/O; note that dZ = Z ∩ (O : O^{†}), so d can be computed in polynomial time. Since the order of O^{†}/O equals the discriminant Δ of K, the prime divisors of d are the same as those of Δ. Also, if p is a prime dividing Δ, and p > [K : Q], then 3.1 and 3.3(a) (applied to q = p) imply that p occurs only once in d. Hence if one removes the repeated prime factors ≤ [K : Q] from d one obtains the largest squarefree divisor of Δ.

Next suppose that the largest squarefree divisor m of the discriminant Δ of K is given. As in [18, 2.10], one can construct an order A in K. Using Euclid’s algorithm one readily calculates the largest divisor m_{1} of Δ_{A} that is coprime to m. Then gcd(m_{1}, Δ) = 1, so by Corollary 6.8 one can calculate, in polynomial time, an overorder B of A that is maximal at m_{1}. By Theorem 1.2 one can determine, in polynomial time, an overorder of B that is maximal at m. The latter order is maximal at Δ_{A}, so it is equal to the ring of integers of K. This proves 1.4.

6.10. Remark. One may wonder whether there is a polynomial time algorithm that, given K and the discriminant Δ of K, determines the ring of integers O of K. We argue that such an algorithm is currently beyond reach by showing that it would enable us to factor integers n that are known to be of the form p^{2}q^{3}, where p, q are distinct prime numbers; no good algorithm, practically or otherwise, is known for the latter problem.

To prove this, let n be such an integer. To factor n, we may clearly assume that p and q are odd. Let K = Q(n^{1/4}). This is a fourth degree number field, and it is a straightforward exercise to show that its discriminant Δ is of the form Δ = −4^{h}n (cf. 3.5), where h is a positive integer that by Theorem 1.2 (with m = 2) can be computed in polynomial time. Thus, we can compute Δ. By hypothesis, we can compute O from Δ in polynomial time, so by Theorem 1.4 we can now determine the largest squarefree divisor 2pq of Δ as well. This obviously enables us to factor n completely, which finishes the proof.

Proof of Theorem 1.3. We first reduce (a) to (b). Given an algebraic number field K, one can in polynomial time construct an order A in K (see [18, 2.10]). If the algorithm of Theorem 1.2 is applied with m equal to the largest squarefree divisor of Δ_{A}, then the overorder B of A determined by the algorithm is maximal at Δ_{A} and therefore equal to O. Hence O can be determined in polynomial time if m is known. This shows that (a) can be reduced to (b).

For the opposite reduction, let d be the positive integer of which the largest squarefree divisor is to be found. Determine the least positive integer n for which (n + 1)^{n} > d, and the least prime number l not dividing d. Note that both n and l are O(1 + log d), and that they can be found by a direct search. Let d_{0} be the largest divisor of d that is free of prime factors ≤ n. Since we can deal with the small prime factors directly, it will suffice to determine the largest squarefree divisor of d_{0}. By Eisenstein’s criterion, X^{n} − d_{0}l is irreducible, so K = Q((d_{0}l)^{1/n}) is an algebraic number field of degree n. We claim that from the ring of algebraic integers O of K one can compute, in polynomial time, the largest squarefree divisor of d_{0}. Namely, there is no prime number p dividing d_{0} with the property that the number of factors p in d_{0} is divisible by n; this follows from (n + 1)^{n} > d_{0} and the fact that all primes dividing d_{0} are at least n + 1. By 3.5, this implies that each prime factor p of d_{0} divides Δ_{O}. Hence if we use 1.4 to compute the largest squarefree divisor d_{1} of Δ_{O}, then the largest squarefree divisor of d_{0} is given by gcd(d_{1}, d_{0}). This proves 1.3.

6.11. Remark. Chistov’s reduction of 1.3(b) to 1.3(a) makes use of a sequence of number fields of the form K = Q(\sqrt{b}), where b divides d (see [6]). His reduction is, in the language of [8], a “Turing reduction”. Our proof shows that, for a given d, a single algebraic number field K suffices. For this reason we used the term “polynomial transformation” in 1.3 (cf. [8]).

Theorem 6.12. Under polynomial transformations, the following two problems are equivalent:

(a) given an algebraic number field K and a subring A of the ring of integers O of K, decide whether A is equal to O;

(b) given a positive integer d, decide whether d is squarefree.

Proof. We first reduce (a) to (b). Applying the algorithm of Theorem 1.1 to the order A, we find in polynomial time an overorder B of A and a positive integer q. If B ≠ A, then clearly A is not maximal. If B = A, then A is maximal if and only if q is squarefree, by Theorem 1.1. This shows that (a) can be reduced to (b). For the opposite reduction, let d be a positive integer. If d ≡ 0 mod 4, then d is not squarefree. If d ≡ 1 or 2 mod 4, then d is squarefree if and only if the order A = Z[\sqrt{−d}] equals the ring of algebraic integers of the algebraic number field K = Q(\sqrt{−d}). If d ≡ 3 mod 4, then d is squarefree if and only if the order A = Z[(1 + \sqrt{−d})/2] equals the ring of algebraic integers of K = Q(\sqrt{−d}). This shows that (b) can be reduced to (a) and concludes the proof of Theorem 6.12. 6.13. Remark. Suppose that an order A in an algebraic number field K is given. As we saw in the proof of 1.3, we can compute the ring of integers O of K in polynomial time if the largest squarefree divisor m of Δ_{A} is known. However, computing m from O is currently intractable. Namely, suppose we had a good algorithm to do this; applying it to A = Z[d\sqrt{−1}], which has Δ_{A} = −4d^{2} and O = Z[\sqrt{−1}], we would then easily find the largest squarefree divisor of an arbitrary positive integer d, for which no good algorithm is known. 6.14. Remark. Suppose, again, that an order A in an algebraic number field K is given. Then from O one can compute, in polynomial time, the largest square dividing Δ_{A}. This is a fairly straightforward consequence of 1.4 and the fact that Δ_{A}/Δ_{O} is a square. However, computing O from the largest square dividing Δ_{A} is currently intractable. Namely, suppose we had a good algorithm to do this. Let d be an integer that is not divisible by 3 and that is not a cube. The order A = Z[d^{1/3}] has Δ_{A} = −27d^{2}, and the largest square dividing Δ_{A} is (3d)^{2}. Thus the algorithm could be used to find O. Since A is tame at d we have gcd(d, ⟨O : A⟩) = 1 if and only if d is squarefree. This would provide an easy squarefreeness test for d, which is not known to exist.

7. Practical considerations 7.1. Finding largest squarefree divisors. Theorem 1.3 expresses that finding the ring of integers of a given algebraic number field is essentially equally hard as finding the largest squarefree divisor of a given positive integer. In [13] one finds a discussion of complexity results concerning the latter question. We make here a few remarks that are mostly of a practical nature.

The problem of determining the largest squarefree divisor a of a given positive integer m is a very hard one, and the best methods that are known for its solution are derived from methods for factoring m. When applying factoring methods to this problem, one has to keep in mind that in order to determine a it suffices to know all prime divisors of m up to the cube root of m, rather than up to its square root. Namely, let m = n · ∏_{p} p^{t(p)}, where p ranges over the primes ≤ m^{1/3} dividing m, and n has no prime factor ≤ m^{1/3}; then a = n′ · ∏_{p} p, where n′ = \sqrt{n} if n is a square and n′ = n otherwise. This leads to the following complexity bounds for the problem of finding the largest squarefree divisor of a given positive integer m, for m → ∞. The best completely proved deterministic algorithm is derived from the “fast factorials” factoring method of Pollard and Strassen (see [22, Section 4]), and it runs in time at most m^{1/6+o(1)}. The fastest completely proved probabilistic algorithm is the class group relations method (see [21]), which runs in expected time L_{m}[1/2, 1 + o(1)], where L_{x}[a, b] = exp(b(log x)^{a}(log log x)^{1−a}). The elliptic curve method (see [19]) is conjectured to solve the problem in expected time at most L_{m}[1/2, \sqrt{2/3} + o(1)], and the number field sieve (see [5]) in time L_{m}[1/3, O(1)].

In practice, one would apply a variety of factoring methods to m, with a preference for methods that are apt at finding small prime factors, such as the elliptic curve method. For the unfactored part of m one then hopes that it is squarefree, this hope being based on the fact that a random integer that has no small prime factors is very likely to be squarefree. It depends, of course, on the way in which the integer m has been obtained in the first place whether the latter fact is relevant at all; for example, in our context one may wonder to which extent discriminants of random polynomials can be viewed as random integers for this purpose. See also the remarks made in [16, Section 2].

Any algorithm for finding the largest squarefree divisor of a given positive integer can clearly also be used for recognizing squarefree integers. There is not much else that we know about the latter problem. One can prove that an integer m > 4 is squarefree if there exists a positive integer n with gcd(n, m) = 1 such that a^{n} ≡ 1 mod m for all positive integers a with a < (log m)^{2} (cf. [20, Theorem 2]). However, such a value for n does not exist for each squarefree m; if it does exist it may be hard to find; and once it has been found it is very likely—though unproved—that it can be used to factor m completely. For numbers that are not squarefree the situation is even worse: any numerical evidence that we can think of that would imply that a specific number m is not squarefree can be used to readily find a non-trivial square factor of m. As an example, we mention the following. If A is a Z/mZ-algebra that admits a finite basis and for which Δ_{A} is a unit (for example, A may be equal to Z/mZ itself), and A contains a nilpotent element x with x ≠ 0, then one can prove that m is not squarefree; and indeed there exists a deterministic polynomial time algorithm that, given such A and x, finds a non-trivial square factor of m. 7.2. Finding the ring of integers. Suppose that one is given an algebraic number field K, and that one wishes to approximate its ring of integers O. Elaborating upon a procedure sketched in the introduction, we describe how one might, in principle, proceed in practice. Let A be the largest order in K that one knows; this is often an order of the form Z[α], with α ∈ K, but depending on additional information that is available about K one may know a larger order that is possibly not of this form. Next, one determines a sequence q_{1}, q_{2}, …, q_{t} of positive integers with the property that ∏_{i=1}^{t} q_{i} is divisible by each prime number p for which p^{2} divides Δ_{A}; in addition, one tries to make ∑_{i=1}^{t} q_{i} as small as possible. If one knows the complete prime factorization of |Δ_{A}| one can simply let the q_{i} be the prime numbers that appear at least twice in Δ_{A}, but in general one isn’t so lucky. Of course, it is always possible to take t = 1, q_{1} = |Δ_{A}|, but in many cases one can do better. For example, one can determine the complementary module A^{†} (see 2.3), write the finite abelian group A^{†}/A of order |Δ_{A}| as ⨁_{i=1}^{t} Z/d_{i}Z where d_{i+1} divides d_{i} for 1 ≤ i < t, and put q_{i} = d_{i}/d_{i+1}, where d_{t+1} = 1. Also, one may profit from non-trivial factors of Δ_{A} that one happens to know, either from known properties of K or from attempts to factor |Δ_{A}|. In order to try and improve a sequence q_{1}, q_{2}, …, q_{t}, one can apply a factoring algorithm to the q_{i}. Using the algorithm of 6.5 one can achieve that the q_{i} are pairwise coprime. It is easy to see that one may also assume that none of the q_{i} is a square or a higher power of an integer. Let it now be supposed that q_{1}, q_{2}, …, q_{t} are as above, and that any attempt to improve the sequence—i. e., to decrease ∑_{i=1}^{t} q_{i}—has failed. Then one applies Algorithm 6.6 successively to all q_{i}, and one ultimately obtains an overorder B of A as well as a set Q of pairwise coprime integers q > 1, with each q ∈ Q dividing gcd(q_{i}, Δ_{B}) for some i, such that B is tame at ∏_{q∈Q} q and maximal at all prime numbers not dividing that product. This is as close to O as one gets: one can only hope that B = O or, equivalently, that all q ∈ Q are squarefree; this hope is fulfilled if all q_{i} are squarefree. In any case, B is a Gorenstein ring, and many ideals of B are invertible, by 4.5 and 4.6. If it is later discovered that some q ∈ Q has a non-trivial square factor, then by Theorem 6.9 one can enlarge B.

There are cases in which the original order A is never enlarged during the entire procedure. Suppose, for example, that A = Z[α] ≠ Z and that A^{†}/A is cyclic of order |Δ_{A}|. Then one can show that Δ_{A} is odd and that it is not a square. If in fact Δ_{A} has no small prime factors and is not a higher power of an integer either, then none of the methods mentioned above is likely to improve the sequence given by t = 1, q_{1} = |Δ_{A}|. The order A is tame at q_{1} (cf. 4.3), and it can be argued that in these circumstances Algorithm 6.6 is unlikely to enlarge A.

The procedure described above may lead to an order that is not guaranteed to be the maximal order. Whether it can nevertheless be used for the purpose one has in mind clearly depends on what that purpose is. Two things may happen. The first is, that during any subsequent calculations that one performs with the order, the hypothesis that it is the maximal order is never contradicted. In this case, one may be able to show that the same conclusions can be drawn from these calculations that one could draw if the order were known to be maximal. For this to be feasible, it is obviously desirable that much of our theoretical and algorithmic knowledge of maximal orders be extended to more general orders. This has been done for orders in quadratic fields (cf. [4; 21]). Orders in general number fields have been less thoroughly studied (cf. [23; 5, Section 7]).

The second thing that may happen is that during later computations one does obtain evidence that the order is not maximal. In all situations known to us in which this can occur such evidence readily yields a strictly larger order. In this case one can start all over again with the procedure described above, the role of A now being played by the larger order that has been found. To give an example, one is certain that the order A is not maximal if one finds a fractional ideal a that is not invertible. The one can compute the order B = (A : a) : (A : a), which by Proposition 2.5 is strictly larger than A.

References

1. M. F. Atiyah, I. G. Macdonald, Introduction to commutative algebra, Addison-Wesley, Reading, Mass., 1969.

2. E. Bach, J. Driscoll, J. O. Shallit, Factor refinement, J. Algorithms 15 (1993), 199–222.

3. H. Bass, On the ubiquity of Gorenstein rings, Math. Z. 82 (1963), 8–28.

4. Z. I. Borevič, I. R. Šafarevič, Teorija čisel, Izdat. “Nauka”, Moscow, 1964; English translation: Number theory, Academic Press, New York, 1966.

5. J. P. Buhler, H. W. Lenstra, Jr., C. Pomerance, Factoring integers with the number field sieve, [14], 50–94.

6. A. L. Chistov, The complexity of constructing the ring of integers of a global field, Dokl. Akad. Nauk SSSR 306 (1989), 1063–1067; English translation: Soviet Math. Dokl. 39 (1989), 597–600.

7. H. Cohen, A course in computational algebraic number theory, Springer-Verlag, Berlin, 1993.

8. M. R. Garey, D. S. Johnson, Computers and intractability, a guide to the theory of NP-completeness, Freeman, New York, 1979.

9. G. Ge, Algorithms related to multiplicative representations of algebraic numbers, Ph. D. thesis, Department of Mathematics, University of California, Berkeley, May 1993.

10. J. L. Hafner, K. S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 1068–1083.

11. D. E. Knuth, The art of computer programming, volume 2, second edition, Addison-Wesley, Reading, Mass., 1981.

12. T. Y. Lam, Serre’s conjecture, Lecture Notes in Math. 635, Springer-Verlag, Berlin, 1978.

13. S. Landau, Some remarks on computing the square parts of integers, Inform. and Comput. 78 (1988), 246–253.

14. A. K. Lenstra, H. W. Lenstra, Jr. (eds), The development of the number field sieve, Lecture Notes in Math. 1554, Springer-Verlag, Berlin, 1993.

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

16. A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, The factorization of the ninth Fermat number, Math. Comp. 61 (1993), 319–349.

17. A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, J. M. Pollard, The number field sieve, [14], 11–42.

18. H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. 26 (1992), 211–244.

19. H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), 649–673.

20. H. W. Lenstra, Jr., Miller’s primality test, Inform. Process. Lett. 8 (1979), 86–88.

21. H. W. Lenstra, Jr., C. Pomerance, A rigorous time bound for factoring integers, J. Amer. Math. Soc. 5 (1992), 483–516.

22. C. Pomerance, Analysis and comparison of some integer factoring algorithms, in: H. W. Lenstra, Jr., R. Tijdeman (eds), Computational methods in number theory, Mathematical Centre Tracts 154/155, Mathematisch Centrum, Amsterdam, 1982, 89–139.

23. J. W. Sands, Generalization of a theorem of Siegel, Acta Arith. 58 (1991), 47–57.

24. J. Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp. 54 (1990), 797–837.

25. E. Weiss, Algebraic number theory, McGraw-Hill, New York, 1963; reprinted, Chelsea, New York, 1976.

26. H. Zassenhaus, Ein Algorithmus zur Berechnung einer Minimalbasis über gegebener Ordnung, in: L. Collatz, G. Meinardus, H. Unger (eds), Funktionalanalysis, Approximationstheorie, numerische Mathematik, Oberwolfach 1965, Birkhäuser, Basel, 1967, 90–103.

27. H. G. Zimmer, Computational problems, methods and results in algebraic number theory, Lecture Notes in Math. 262, Springer-Verlag, Berlin, 1972.