EUCLIDEAN RINGS OF ALGEBRAIC INTEGERS

Malcolm Harper and M. Ram Murty^{1}

1. Introduction

An integral domain R is said to be Euclidean if there exists a map ϕ : R\{0} → ℕ such that given any a, b ∈ R, there exist q and r such that a = bq + r with either r = 0 or ϕ(r) < ϕ(b). Any such ring is a principal ideal domain (PID).

If R is the ring of integers of an algebraic number field, then clearly a necessary condition for R to be Euclidean is that R be a PID. That this condition is also sufficient whenever the quotient field of R is not an imaginary quadratic field is a remarkable prediction of the generalized Riemann hypothesis (GRH) and is a beautiful theorem of Weinberger [W]. Such a result, together with its connection to a number field version of the Artin primitive root conjecture was first signaled in a paper of Samuel [S]. In that paper, Samuel discusses the situation with quadratic extensions of ℚ. After reviewing a general criterion of Motzkin [M] for a ring to be Euclidean, he applies it to the context of quadratic fields.

This criterion is easily described. Let A_{0} = {0} and define inductively A_{n} to be the set of elements r of R having the property that every residue class modulo r has a representative in A_{j} for some j < n. Thus, A_{1} consists of the unit group of R. Motzkin’s criterion is that R is Euclidean if and only if R = ∪_{n=0}^{∞}A_{n}.

Motzkin used his criterion to prove that of the nine imaginary quadratic fields of class number one, only five of them are Euclidean and for these fields, the norm map serves as the function ϕ. In contrast, Samuel’s work [S] made the exciting prediction that any ring of integers of a real quadratic field of class number one is Euclidean, but not necessarily for the absolute value of the norm map serving as ϕ. In particular, Samuel conjectured that ℤ[\sqrt{14}] is Euclidean this being the quadratic field of smallest discriminant whose nature was unresolved.

We refer the reader to Lenstra’s paper [L] for both the historical developments and applications of these ideas in the more general context of function fields over finite fields where the GRH is known and the analog of Weinberger’s theorem can be proved unconditionally.

1Research partially supported by an NSERC grant.

In an earlier paper, the first author [H] proved that ℤ[\sqrt{14}] is Euclidean without the use of the generalized Riemann hypothesis. More generally, he proved that if K is a real quadratic field and O_{K} its ring of integers whose discriminant is less than 500, then O_{K} is Euclidean if and only if O_{K} has class number one. In the same paper, he also determined all the cyclotomic fields whose ring of integers is a Euclidean domain.

In this paper, we generalize the work of [H] to a larger context that includes the abelian case. Our methods originate in the papers of Gupta, K. Murty and R. Murty [GMM] where the first attempt was made to make Weinberger’s results unconditional using the earlier work of [GM] on Artin’s primitive root conjecture. Their work studied the ring O_{K,S} of S-integers where S was a finite set of places that included the infinite places and required |S| ≥ max(5, 2[K : ℚ]−3) to be applicable in the Euclidean context. A novel idea was injected into the method by Clark and Murty [CM] in 1995. This idea allowed one to discover new Euclidean rings of integers of totally real Galois extensions K over ℚ with [K : ℚ] ≥ 4. Thus, at that time, the case of ℤ[\sqrt{14}] was still elusive.

In [H], a variant of the Motzkin criterion was discovered, which when combined with the lower bound sieve results of previous works on the problem, along with a clever use of the large sieve inequality, finally led to the applicability of the method to the quadratic field context.

The goal of this paper is to prove:

Theorem 1. Let K/ℚ be a finite Galois extension with unit rank r > 3. Then O_{K} is Euclidean if and only if O_{K} is a PID.

As a corollary, we deduce:

Corollary. Let K/ℚ be a finite Galois extension of degree > 8. Then O_{K} is Euclidean if and only if O_{K} is a PID.

Indeed, if r_{1} and r_{2} denotes the number of real and complex embeddings of K respectively, we have r > (r_{1} + 2r_{2} − 2)/2 = (n − 2)/2 so that r > 3 whenever n > 8 and r_{1} > 0. If r_{1} = 0, then r = r_{2} − 1 > 3 whenever n > 8.

The proof of this theorem involves many important ideas. In addition to the Motzkin criterion described above, the generalization of the Bombieri-Vinogradov theorem to algebraic number fields as developed by K. Murty and R. Murty [MM] plays a vital role. Their generalization has two versions, one which is unconditional and another which assumes the Artin holomorphy conjecture for the Artin L-functions that intervene. Undoubtedly, we feel that there is great scope for further improvements. In particular, it should be possible to sharpen the theorem to allow r = 3. This is possible in the abelian case thanks to a theorem of Bombieri, Friedlander and Iwaniec [BFI] extending the range of applicability of the Bombieri-Vinogradov theorem beyond the usual limit of x^{1/2} in the lower bound sieve method. Such a result is not available in the non-abelian context and so our result stands with the strict inequality at present. Still, by injecting ideas utilised in Theorem 2 (below), especially the notion of admissible primes, one can hope to make further improvements. This we hope to develop in future research.

As is well-known, the Euclidean algorithm plays an important role in the study of bounded generation of arithmetic groups. We state an application of our theorem to this study, but refer the reader to the exposition of K. Murty [KM].

2. Variation of Motzkin’s criterion

In [H], Harper discovered a variation of Motzkin’s criterion applicable to rings of integers of algebraic number fields. This can be described as follows.

First we define the notion of admissible sets of primes as described by Clark and Murty [CM]. Let K be an algebraic number field, O_{K} its ring of integers. We suppose that O_{K} is a PID. Let π_{1}, ..., π_{s} ∈ O_{K} be distinct non-associate primes. We say {π_{1}, ..., π_{s}} is an admissible set of primes if for all β = π_{1}^{a_{1}} ⋯ π_{s}^{a_{s}} with a_{i} non-negative integers, every coprime residue class (mod β) can be represented by a unit of O_{K}. As noted in [CM], to check if {π_{1}, ..., π_{s}} is admissible, it suffices to check that every coprime residue class (mod π_{1}^{2} ⋯ π_{s}^{2}) can be represented by a unit of O_{K}.

Now let B_{0} be the monoid generated by the unit group and an admissible set of primes (which could be empty). For n ≥ 1, inductively define B_{n} as the set of all primes π of O_{K} such that every non-zero residue class modulo (π) has a representative in B_{n−1} ∪ B_{0}. Thus, B_{1} is the set of primes π such that every residue class mod π is represented by an element of B_{0}. The fundamental result in [H] is:

Proposition 1. Suppose O_{K} is a PID. If all the primes of O_{K} lie in ∪_{n=0}^{∞}B_{n}, then O_{K} is Euclidean.

A key innovation in the argument of Harper [H] was the following application of the large sieve inequality.

Proposition 2. Suppose that O_{K} is a PID. Let B_{n}(x) denote the cardinality of the set of elements in B_{n} whose norm is less than or equal to x. If

B_{1}(x) ≫ \frac{x}{log^{2} x},

then O_{K} is Euclidean.

It is this last proposition that simplfies the earlier approaches to the study of Euclidean rings of algebraic integers. Indeed, in the proofs below we apply the lower bound sieve to establish Proposition 2.

3. Preliminaries

We record in this section various theorems from the literature which will be needed in the proofs.

Proposition 3. [MM] Let K/ℚ be a finite Galois extension with group G. Let C be a conjugacy class of G, and a, q be positive integers with 1 ≤ a < q, (a, q) = 1. Denote by π_{C}(x, q, a) the number of primes p ≤ x such that p ≡ a( mod q) with Artin symbol (p, K/ℚ) ∈ C. There exist numbers δ(C, q, a) ≥ 0 such that for any ϵ > 0 and A > 0, we have

∑_{q≤Q} max_{(a,q)=1} max_{y≤x} |π_{C}(y, q, a) − δ(C, q, a)π(y)| ≪ \frac{x}{(log x)^{A}} ,

with Q = x^{α−ϵ} where α ≤ min(2/|G|, 1/2) and the summation is over q such that K ∩ ℚ(ζ_{q}) = ℚ. (Here, π(y) denotes the number of primes p ≤ y. )

This is the basic result of [MM]. However, as remarked in section 7 of that paper, some improvements can be made (see, in particular Theorem 7.3 and section 7.4).

Proposition 4. [MM, p. 269] With the same setting as in Proposition 3, let A be any abelian subgroup of G with A ∩ C ≠ ϕ. Let d = [G : A]. Then, we may take Q = x^{1/η−ϵ} in Proposition 3 with

η = \{ \begin{matrix}d − 2 & if d ≥ 4 \\ 2 & if d ≤ 4 \end{matrix}

Moreover, we may replace d above by d^{∗} where

d^{∗} = min_{H} max_{ω}[G : H]ω(1)

where the minimum is taken over all subgroups H satisfying the two conditions

• H ∩ C ≠ ϕ and

• for every irreducible character ω of H and any non-trivial Dirichlet character χ, the Artin L-series L(s, ω ⊗ χ) is entire.

The maximum above is over all irreducible characters of H. In particular, if Artin’s holomorphy conjecture is true for K/ℚ, then we may take d^{∗} = max_{χ} χ(1) where the maximum is over all irreducible characters of G.

Proposition 5. (Application of the lower bound sieve) Let K/ℚ be a finite Galois extension and set

t = max_{m}{m : K ⊇ ℚ(ζ_{m})}.

Let η be as in Proposition 4 with C = 1. Then, the number of primes p ≤ x such that p splits completely in K and for every prime ℓ with ℓ|(p − 1)/t, we have ℓ > x^{1/2η−ϵ}, is

≫ \frac{x}{log^{2} x}.

Proposition 6. (Gupta-Murty [GM]) Let K be an algebraic number field. Let M be a monoid in O_{K} and for 𝔭 coprime to the elements of M, denote by f_{M}(𝔭) the order of M mod 𝔭. If M contains r multiplicatively independent elements, then

#{𝔭 : f_{M}(𝔭) ≤ Y } ≪ Y^{(r+1)/r}.

4. The Abelian case

We begin with Lemma 4 of [H].

Proposition 7. Suppose O_{K} is a PID and contains a set of s admissible primes. Let r be the rank of O_{K}^{×} modulo torsion and define t = max{d′ : ζ_{d′} ∈ K}. If r + s ≥ 3 and if there are a and k ∈ ℤ satisfying

1. gcd(a, k) = 1;

2. gcd(a − 1, k) = t; and

3. p ≡ a( mod k) implies there is a prime 𝔭 of K with norm p,

then O_{K} is Euclidean.

We will use this proposition to establish the following:

Theorem 2. Let K/ℚ be abelian of degree n with O_{K} a PID that contains s admissible primes. Let r be the rank of the unit group. If r + s ≥ 3, then O_{K} is Euclidean.

Proof. Let t be as in Proposition 7. We count the number of primes p ≤ x such that p splits completely in K and p does not split completely in ℚ(ζ_{ℓt}) for ℓ|t. Let k be the conductor of K. Since K/ℚ is abelian, this means that there is a set S of residue classes mod k such that p splits completely in K if and only if p ≡ a( mod k) with a ∈ S. Since ℚ(ζ_{t}) is contained in K, we have a ≡ 1( mod t) We want to show that there is an a in S satisfying the conditions of Proposition 7, namely gcd(a − 1, k) = t. To do this, it suffices to show that there is a positive density of primes p which split competely in K but not in ℚ(ζ_{ℓt}) for ℓ|t for these primes will satisfy gcd(p − 1, k) = t. If we let K_{ℓt} = Kℚ(ζ_{ℓt}), then the number of primes in our count is

∑_{δ|t} μ(δ)π(K_{tδ}, x)

where π(L, x) is the number of primes p ≤ x splitting completely in L. Since the degree of K_{tδ} over ℚ is nδ as is easily checked, we have by the Chebotarev density theorem, that the quantity in question is

∼ ∑_{δ|t} μ(δ)\frac{π(x)}{nδ} = \frac{π(x)}{n} \frac{ϕ(t)}{t},

which is a positive proportion. This completes the proof.

5. Proof of the main theorem.

We want to use Proposition 2 to show that O_{K} is Euclidean. Let B_{1}(x) count the number of primes π with norm less than x for which we have O_{K}^{×}( mod π) = (O_{K}/π)^{×}. It suffices to show that

B_{1}(x) ≫ \frac{x}{log^{2} x}.

By Proposition 5, the number of primes π which split completely in K with p = N_{K/ℚ}(π) ≤ x having the property that any prime ℓ dividing p−1 is either greater than x^{1/2η−ϵ} or a divisor of t, (where t, η are defined in Proposition 5) is

≫ \frac{x}{log^{2} x}.

For p sufficiently large, we already know that t divides the order of the image of O_{K}^{×} mod π since the group of roots of unity injects into (O_{K}/π)^{×}. By virtue of the constraint on p guaranteed by Proposition 5, no prime dividing t can divide the index of the image. Thus, the only possible prime divisors of the index are greater than x^{1/2η−ϵ} which means that if the index is not 1, then the size of the image is less than x^{1−1/2η+ϵ}. By Proposition 6, the number of such primes is

O (x^{(1−1/2η+ϵ)(1+1/r)}) = o(x/ log^{2} x)

whenever η < (r + 1)/2. We apply Proposition 5. We determine η of Proposition 4 as follows. Let G = Gal(K/ℚ) and let A be an abelian subgroup of G. Set d = [G : A]. If d ≤ 4, we can take η = 2 so we need r > 3. If d ≥ 4, we can take η = d − 2, and we need d − 2 < (r + 1)/2 which means we need to ensure r > 2d − 5. This is the case if G has an abelian subgroup of order e ≥ 4, since

r = r_{1} + r_{2} − 1 ≥ \frac{r_{1} + 2r_{2} − 2}{2} = \frac{n − 2}{2} > \frac{2n}{e} − 5 = 2d − 5.

Thus, we may assume every prime divisor of |G| = n is ≤ 3. Hence, n = 2^{a}3^{b}. If b ≥ 2, G has a subgroup of order 9 and again by the above argument we are done. If a ≥ 2, we are also done. The only case left is if n divides 6. As the abelian case was dealt with in the previous section, the only case to treat is the non-abelian case of n = 6. But in this case, we have Artin’s conjecture on the holomorphy of non-abelian L-series, so that we may take η = 2 in Proposition 4. Thus, r > 3 is allowed and the proof is complete.

Acknowledgments. The authors would like to thank the referee for helpful comments and suggestions.

References

[BFI] E. Bombieri, J. Friedlander, H. Iwaniec, Primes in arithmetic progressions to large moduli, Acta Math, 156 (1986), no. 3-4, pp. 203-251.

[CM] D. Clark and M. Ram Murty, The Euclidean algorithm for Galois extensions of ℚ, J. Reine Angew. Math., 459 (1995), pp. 151-162.

[GM] R. Gupta and M. Ram Murty, A remark on Artin’s conjecture, Invent. Math., 78 (1984), pp. 127-130.

[GMM] R. Gupta, M. Ram Murty and V. Kumar Murty, The Euclidean algorithm for S-integers, in Number Theory, edited by H. Kisilevsky and J. Labute, CMS Conf. Proceedings, 7 (1987), pp. 189-201.

[H] M. Harper, ℤ[\sqrt{14}] is Euclidean, to appear in Canadian Journal of Math.

[L] H. Lenstra, Euclidean number fields, I, Math. Intelligencer, 2 (1979), no. 1, pp. 6-15.

[M] Th. Motzkin, The Euclidean algorithm, Bulletin of the Amer. Math. Soc., 55 (1949), pp. 1142-1146.

[KM] V. Kumar Murty, Bounded and Finite Generation of Arithmetic Groups, in Number Theory, edited by K. Dilcher, CMS Conf. Proceedings, 15 (1995), pp. 249-261.

[MM] M. Ram Murty and V. Kumar Murty, A variant of the Bombieri-Vinogradov theorem, in Number Theory, edited by H. Kisilevsky and J. Labute, CMS Conference Proceedings, 7 (1987), pp. 243-272.

[S] P. Samuel, About Euclidean Rings, J. Algebra, 19 (1971), pp. 282-301.

[W] P. Weinberger, On Euclidean rings of algebraic integers, in Analytic Number Theory, (St. Louis, 1972), Proceedings of Symposia in Pure Math., 24 (1973), pp. 321-332, American Math. Society.

M. Harper, Champlain College, Montreal, Canada malcolmharper@sympatico.ca

M. Ram Murty, Department of Mathematics, Queen’s University, Kingston, Ontario, K7L 3N6, Canada murty@mast.queensu.ca