THE EUCLIDEAN ALGORITHM IN GALOIS EXTENSIONS OF ℚ

David A. Clark^{1,} ^{2} and M. Ram Murty^{1}

McGill University^{1} and Institut für Experimentelle Mathematik^{2} Universität GHS Essen

A Euclidean algorithm for an integral domain R is a map

ϕ : R \ {0} → ℕ_{0},

the set of nonnegative integers, such that for all a, b ∈ R, b ≠ 0, there exist q, r ∈ R with a = qb + r and either ϕ(r) < ϕ(b) or r = 0. One important property of integral domains satisfying this condition is that all their ideals are principal. An integral domain equipped with a Euclidean algorithm is called a Euclidean domain. Often we shall say that a field is Euclidean if its ring of integers is a Euclidean domain. For algebraic number fields the Euclidean algorithm that has usually been studied is the absolute value of the norm. We will to refer to such fields as being norm-Euclidean.

Historical Introduction

Dedekind showed in Supplement XI to Dirichlet’s Vorlesungen über Zahlentheorie that ℚ(\sqrt{d}) is norm-Euclidean for d = −1, −2, −3, −7, −11, 2, 3, 5, 13. He also noted that while the ring of integers of ℚ(\sqrt{−19}) is a principal ideal domain it is not Euclidean for the norm (this is also true for d = −43, −67, and −163). Hasse [12] asked if it is possible to define Euclidean algorithms other than the norm when the ring of integers is a principal ideal domain. Motzkin [24] showed that the ring of integers of ℚ(\sqrt{−19}) is not Euclidean for any algorithm, thus giving a negative answer to this question in general (The same proof also works in the other three cases). Previously, no examples of rings of integers of algebraic number fields were known which were Euclidean but not norm-Euclidean.

L.E. Dickson [9], p. 151, claimed that the above list of norm-Euclidean quadratic fields was complete; however, Perron [27] observed that Dickson’s proof was valid only for imaginary quadratic fields. Perron gave the additional examples with d =

Typeset by AMS-TEX

6, 7, 11, 17, 21, 29. Other examples were given by Oppenheim [26] and Remak[29], d = 33, 37, 41; Berg [2], d = 19; Hofreiter [16], d = 57; and Rédei [28], d = 73. Rédei also claimed that ℚ(\sqrt{97}) was norm-Euclidean. This was later shown to be false by Barnes and Swinnerton-Dyer [1].

In 1938, Heilbronn [13] and Erdös and Chao Ko [10] proved that there are only finitely many d for which ℚ(\sqrt{d}) is norm-Euclidean. The proof that the above list of norm-Euclidean quadratic fields is complete was finished by Inkeri [18] and Chatland [5]. In addition, Davenport [7] [8] showed that there are only finitely many cubic and quartic fields with rank one unit group which are norm-Euclidean. Heilbronn [14] [15] showed that there are only finitely many cyclic cubic norm-Euclidean fields and gave many other classes of cyclic extensions for which the number of norm-Euclidean fields is finite. However, except for the quadratic fields, a complete list of the norm-Euclidean fields of these types has not been determined.

Many methods have been used to verify that a field is norm-Euclidean. Suppose that the field K = ℚ(α) has a generating polynomial f of degree n, with r real zeros, α_{1}, α_{2}, …, α_{r}, and s complex conjugate pairs of complex zeros, β_{1}, β̄_{1}, …, β_{s}, β̄_{s}. Now, R, the ring of integers of K, can be embedded as an n-dimensional lattice of V = ℝ^{r}×ℂ^{s} by the map which sends

g(α) = a_{o} + a_{1}α + ⋯ + a_{n−1}α^{n−1} ↦ (g(α_{1}), …, g(α_{r}), g(β_{1}), …, g(β_{s})).

An integral basis z_{0}, ⋯, z_{n−1} of K is also a basis for the embedded lattice. It is easy to see that R is norm-Euclidean if every element of V can be written as a sum of an element of R and an element of norm less than 1. Equivalently, R is norm-Euclidean if the parallelepiped

{a_{0}z_{0} + ⋯ + a_{n−1}z_{n−1} : 0 ≤ a_{i} < 1, i = 0, …, n − 1}

is covered by translates of U = {θ ∈ V : N(θ) < 1} by elements of R. Therefore, one way of determining if a field is norm-Euclidean is to break the parallelepiped into small pieces and check that each piece is translated into U by an element of R.

Let Δ be the discriminant of K. Lenstra [20] showed that if m elements ω_{1}, …, ω_{m},

m > \frac{n!}{n^{n}} (\frac{4}{π} )^{s} |Δ|^{1/2},

can be found with each ω_{i} − ω_{j}, i ≠ j, a unit of R, then R is norm-Euclidean. This idea was used by Lenstra [20], Mestre [23], and Leutbecher and Martinet [22] to give several hundred new examples of norm-Euclidean fields.

Motzkin [24] constructed a special kind of Euclidean algorithm. Given a nonempty collection of Euclidean algorithms ϕ_{α} on R, the map defined by

ϕ(r) = min_{α} ϕ_{α}(r)

is also a Euclidean algorithm on R. To check this, let a, b ∈ R, b ≠ 0. Choose an α_{1} such that ϕ(b) = ϕ_{α_{1}}(b). Since

ϕ(r) ≤ ϕ_{α_{1}}(r) < ϕ_{α_{1}}(b) = ϕ(b),

ϕ is Euclidean. If the minimum is taken over all the Euclidean algorithms of the ring R, the resulting algorithm E is called the minimal algorithm.

Let E_{n} = {0} ⋃{r ∈ R : E(r) ≤ n}. One can show that E_{0} is the set consisting of 0 and the units of R. If b ∈ E_{n+1} and a + Rb is any residue class mod Rb, then there exist q, r ∈ R with a = qb + r and E(r) < E(b) so that r ∈ E_{n}. Thus, E_{n} → R/Rb is surjective. Conversely, consider b ∈ R such that E_{n} → R/Rb is surjective. If E(b) > n + 1 then a new map E′ could be defined by E′(r) = E(r), for r ≠ b and E′(b) = n + 1. To see that E′ is an algorithm it suffices to consider the cases when b occurs as either a divisor or a remainder. Since E_{n} → R/Rb is surjective, every residue class a + Rb has a representative such that a = qb + r, r ∈ E_{n} which implies E′(r) < n + 1 = E′(b). If a = qc + b with E(b) < E(c), then trivially E′(b) < E(b) < E(c) = E′(c).

The importance of the sets E_{n} is that they can be constructed in any ring. If

R′ = ⋃_{n≥0} E_{n} = R,  (1)

then R is Euclidean with algorithm defined by

ϕ(r) = max{n : r ∈ E_{n}}.

On the other hand, if R is Euclidean then every element of R is in some E_{n}. So the condition (1) is necessary and sufficient for R to be a Euclidean domain. Now it is easy to see why ℚ(\sqrt{−19}) is not Euclidean for any algorithm, the only units are ±1 and every ideal has norm greater than 4 so the construction of the sets E_{n} stops at E_{0}.

Samuel [30] noted a similarity between the success of the construction of the minimal algorithm and Artin’s Primitive Root Conjecture. Namely, if there are infinitely many primes π such that a unit is a primitive root modulo π, then E_{1} contains these primes. In particular, Samuel asked whether ℚ(\sqrt{14}) is Euclidean for some algorithm other than the norm. (ℚ(\sqrt{14}) is not Euclidean for the norm, as noted above.)

Weinberger [31] made the connection with Artin’s conjecture more precise and showed how the conditional proof of Artin’s conjecture by Hooley [17] could be modified to show that under the assumption of the Generalized Riemann Hypothesis for Dedekind zeta functions (GRH), the ring of integers of an algebraic number field with at least one fundamental unit is Euclidean if and only if it is a principal ideal domain. That is, on the GRH, if K is an algebraic number field which is not an imaginary quadratic field and the ring of integers is a principal ideal domain, then it is a Euclidean domain. Thus, conjecturely, Hasse’s question can be answered positively, with only the four exceptions noted above. Lenstra [21] generalized this result to rings of S-integers, |S| ≥ 2, where S is a set of primes containing the infinite primes. R. Gupta, K. Murty, and R. Murty [11] removed the condition of the Generalized Riemann Hypothesis from Lenstra’s result for large enough |S|.

Statement of Theorem

In this paper we prove the following result.

Theorem. Let R be a principal ideal domain with unit group of rank r whose quotient field K is a Galois extension of ℚ of degree n_{K}. Suppose that a collection S of m = max(4 − r, 2n_{K} − r − 4) nonassociate prime elements π_{1}, π_{2}, …, π_{m} of R can be found so that for any non-negative integers a_{i}, i = 1, …, m, the unit group of R maps onto (R/(π_{1}^{a_{1}} ⋯ π_{m}^{a_{m}}))^{∗}. Assume that either

(a) K has a real embedding, or

(b) K contains ζ_{g} where g = gcd(Nπ − 1 : π ∈ S) and ζ_{g} is a primitive g^{th} root of

unity, then R is a Euclidean domain.

Since the unit group is the product of r+1 cyclic groups, one expects to be able to find r + 1 prime elements π_{i}, i = 1, …, r + 1 satisfying the condition stated in the theorem. Hence, this theorem should apply to rings such that min(2r − 3, 5 + 2r − 2n_{K}) ≥ 0. This type of ring would include the ring of integers of totally real Galois extensions with degree greater than or equal to three.

In the special case of totally real quartic Galois fields, to show that the ring of integers is a Euclidean domain requires only the existence of a single prime element π such that the unit group maps onto (R/(π^{m}))^{∗} for all nonnegative integers m. This case was treated in detail by Clark [6]. Call these prime elements Wieferich primes. We conjecture, by analogy to Artin’s Primitive Root Conjecture, that there is a positive density of Wieferich primes. Computations support the validity of this conjecture.

In Clark [6], Wieferich primes were found in each of the 165 totally real quartic Galois fields of class number one with discriminant less that one million, which were determined by Buchmann, Ford, Pohst, and von Schmettow [3] [4], and the required primes were also found for the real cubic Galois fields with discriminant less than 500,000 with class number one. Some examples will be given in the last section.

Proof of the Theorem

Let S be a set of primes of K. In analogy to the minimal algorithm, we define the S-minimal algorithm as follows. Let U_{S} be the multiplicative monoid generated by the units and the prime elements in S. Define sets E_{n}^{S} inductively as follows,

E_{0}^{S} = {0} ∪ U_{S}, and E_{n+1}^{S} = E_{n}^{S} ∪ {a : E_{n}^{S} ↦ R/(a) is onto}.

Define the S-minimal algorithm as we did earlier for the minimal algorithm. In general, the S-minimal algorithm is not a Euclidean algorithm. However we have:

Lemma 1. If each prime element of R is contained in E_{2}^{S}, then R is a Euclidean domain.

Proof: We use induction on the number n of prime divisors not in S of an element a. The case n = 0 is an assumption on the set S. We next consider the case n = 1. First suppose that the element has no prime divisors from S. If a = π_{1} is in E_{1}^{S}, then every residue class contains either = or an element of U_{S}. Since the elements of U_{S} are contained in Motzkin’s construction, all the prime elements in E_{1}^{S} are also contained in the construction. Next, suppose that a = π_{1}s, where s is an element from U_{S}. The coprime residue classes modulo a contain prime elements by Dirichlet’s prime ideal theorem. Since we have shown all prime elements are in the construction, we need only consider non-coprime residue classes. These residue classes are two types π_{1}t′(b + (t′′)) or t′(b + (π_{1}t′′)), where b is a representative of a coprime residue class and t′t′′ = s. The coprime residue class for the first type contains a unit, so by induction on the number of prime divisors of s, this residue class contains an element in the construction. The coprime residue class contains a prime element, so except for the case that t′′ is a unit, we can use induction on the number of prime divisors of s to show that the residue class contains elements in the construction. If t′′ is a unit and π_{1} is in E_{1}^{S}, the the coprime residue class contains an element from U_{S}. If π_{1} is in E_{2}^{S}, the the coprime residue class contains either an element from U_{S} or a prime from E_{1}^{S}. This concludes the proof of the case n = 1. Finally, suppose we have proved the claim for all elements with fewer than n prime divisors not in S. Consider the element a = π_{1}π_{2} ⋯ π_{n}s, where all the π_{i} are not in S and s is in U_{S}. The coprime residue classes modulo a all contain prime elements by Dirichlet’s prime ideal theorem. After reordering, any other residue class modulo a has a representative π_{1} ⋯ π_{k}a′t where a′ is in a coprime residue class modulo π_{k+1} ⋯ π_{n}t′ and t, t′ are elements of U_{S}. If n − k ≥ 2, then since there is a prime element in this coprime residue class, we are done. If n − k = 1, there are two cases to consider. If π_{n} is in E_{1}^{S}, then every residue class modulo π_{n} contains an element in E_{0}^{S} and we are done. If π_{n} is in E_{2}^{S}, then every residue class modulo π_{n} contains an element in E_{1}^{S}. These residue classes are contained in the construction by the previous case. This concludes the proof of the claim.

The method for proving the theorem is similar to that used by R. Gupta, K. Murty and R. Murty [11]. We first interpret the problem in terms of class field theory. Let π be a prime not in S, we want to show that π is contained in E_{2}^{S}.

Let F be the S-ray class field of modulus π. That is, F is the largest extension field of K (in some algebraic closure) with the properties

(i) F/K is abelian, (ii) the conductor of F/K is equal to π (since R is a pid), (iii) all τ ∈ S split completely in F, (iv) Gal(F/K) ≅ (R/(π))^{∗} /ψ(U_{S}) .

To show that π is contained in E_{2}^{S} is equivalent to finding a prime element ϖ having Artin symbol (ϖ, F/K) = σ, where σ is the element of Gal(F/K) corresponding to a + Rπ under the isomorphism (iv), such that the map U_{S} → (R/ϖR)^{∗} is onto.

Let F_{2} be a finite Galois extension of some number field F_{1} and D a union of conjugacy classes of Gal(F_{2}/F_{1}). Denote by d(F_{2}/F_{1}, D) the the set of rational primes ℓ such that ℚ(ζ_{ℓ}) ⊆ F_{2} and τ|_{ℚ(ζ_{ℓ})} = 1 for all τ ∈ D. Let K_{ℓ} denote the Kummer extension of K formed by adjoining the ℓ^{th} roots of the elements of ⟨units, S⟩. Consider the compositum L of all the K_{ℓ} for ℓ contained in d(F/K, σ). Let L_{1} be the compositum of L and F and let L_{2} be the Galois closure of L_{1} over ℚ. Then let

C_{1} = {τ ∈ Gal(L_{1}/K) : τ|F = σ, τ|_{K_{ℓ}} ≠ 1 for all ℓ ∈ d(F/K, σ)} ,

let C_{2} be the inverse image of C_{1} in Gal(L_{2}/K), and let C_{2}^{∗} be the smallest subset of Gal(L_{2}/ℚ) containing C_{2} closed under conjugation.

Condition (a) or (b) of the Theorem implies that every ℓ^{th} root of unity ζ_{ℓ} in F is actually an element of K. More importantly, this condition implies that L is an abelian extension of K.

Next, we show that K_{ℓ}∩F = K. The primes of K which ramify in K_{ℓ} are the divisors of ℓ and the elements of S. Since K contains all the ℓ^{th} roots of unity for ℓ ∈ d(F/K, σ), [K_{ℓ} : K] is a power of ℓ. Primes in S split completely in F. Only π ramifies in F and [F : K]|(Nπ − 1). K has no proper unramified extensions since its ring of integers is a principal ideal domain. Since π does not belong to S, (Nπ − 1, ℓ) = 1 which implies K_{ℓ} ∩ F = K. In addition, this implies that C_{1} is nonempty.

Suppose that ℓ′ is an element of d(L_{1}/K, C_{1}) not in d(F/K, C), and consider J = Gal(L_{1}/K(ζ_{ℓ′}). For any τ ∈ C_{1},

τH \ ⋃_{ℓ∈d(L_{1}/K,C_{1})} (τH ∩ H_{ℓ}) ⊆ C_{1} ⊆ J ∩ τH,

so that

|H| − ∑_{ℓ∈d(L_{1}/K,C_{1})} |H ∩ H_{ℓ}| ≤ |J ∩ τH| ≤ \frac{1}{2}|H|,

which implies

∑_{ℓ∈d(L_{1}/K,C_{1})} |H ∩ H_{ℓ}| ≥ \frac{1}{2}|H|.

Furthermore,

H ∩ H_{ℓ} = Gal(L/K_{ℓ}F) = H/(Gal(K_{ℓ}/K_{ℓ} ∩ F)) = H/(Gal(K_{ℓ}/K)).

Since

| Gal(K_{ℓ}/K)| ≥ ℓ^{r},

it would follow that

\frac{1}{2} ≤ ∑_{ℓ∈d(F/K,C)} \frac{1}{ℓ^{r}} ≤ ∑_{ℓ prime} \frac{1}{ℓ^{r}} .

Since the sum on the right is strictly less than 1/2, a contradiction results. Hence, d(L_{1}/K, C_{1}) = d(F/K, C).

It is obvious that d(L_{2}/ℚ, C_{2}^{∗}) = d(L_{2}/K, C_{2}) and that d(L_{1}/K, C_{1}) ⊆ d(L_{2}/K, C_{2}). We want to show d(L_{2}/K, C_{2}) = d(L_{1}/K, C_{1}). Suppose that ℓ′ ∈ d(L_{2}/K, C_{2}) \ d(L_{1}/K, C_{1}). Then a prime element ϖ of K can be found which does not split completely in K(ζ_{ℓ′}) such that (ϖ, L_{1}/K) ⊆ C_{1}. But this is equivalent to (ϖ, L_{2}/K) ⊆ C_{2}, which contradicts ℓ′ ∈ d(L_{2}/K, C_{2}). Thus, we have proved that d(L_{2}/ℚ, C_{2}^{∗}) = d(F/K, C).

Now we can apply sieve methods to the problem of finding primes in E_{2}^{S}. Let A be a finite sequence of integers, P a sequence of rational primes, z a real number greater than 2, and

P (z) = ∏_{\begin{matrix}p<z \\ p∈P \end{matrix}} p.

then

S(A, P, z) = |{a ∈ A : (a, P (z)) = 1}|

is the number of elements of A whose prime factors which belong to P are all greater than z. For d a square-free integer define

A_{d} = {a ∈ A : a ≡ 0(mod d)} .

Let X be an approximation to |A|, the number of elements in A. For each prime p ∈ P choose ω(p) such that (ω(p)/p)X is a good approximation to A_{p}, and set ω(1) = 1. For square-free integers composed only of primes in P, define

ω(d) = ∏_{p|d} ω(p),

and for other square-free integers set ω(d) = 0. The numbers

R_{d} = |A_{d}| − \frac{ω(d)}{d}X,

give the error of the approximation. Let

W (z) = ∏_{p<z} (1 − \frac{ω(p)}{p}) .

We will use the linear sieve in the form given by Iwaniec [19].

Lemma 2. Assume that

0 ≤ \frac{ω(p)}{p} ≤ 1 − \frac{1}{A_{1}}

−L ≤ ∑_{w≤p<z} \frac{ω(p) log p}{p} − κ log \frac{z}{w} ≤ A_{2}

then for ξ ≥ z there is the lower bound

S(A, 𝔓, z) ≥ XW (z) \{f (\frac{log ξ^{2}}{log z} ) − B \frac{L}{(log ξ)^{1/3}} \} − ∑_{\begin{matrix}q<ξ^{2} \\ q|P (z) \end{matrix}} 3^{ν(q)}|R_{q}|,

with f defined by

f(u) = \frac{2e^{γ}}{u} log(u − 1),

for 2 ≤ u ≤ 4.

We apply this lemma using the sequence A = {p − 1 ≤ x : (p, F_{1}/ℚ) ⊂ C}. For this case, we have

|R_{q}| ≤ R_{C}(x, d) = max_{y≤x} max_{(a,d)=1} |π_{C}(y, d, a) − \frac{|C|}{|G|ϕ(d)}y|,

where π_{C}(y, d, a) is the number of primes p ≤ y such that p is congruent to a modulo d and (p, F_{1}/ℚ) ⊂ C. As customary, we will actually get estimates using

ψ_{C}(y, d, a) = ∑_{\begin{matrix}p^{n}≤y \\ p≡a(mod d) \\ (p,F_{1}/ℚ)⊂C \end{matrix}} log p.

The remainder terms above can then be estimated by partial summation.

We use a variant of the Bombieri-Vinogradov theorem given by K. Murty and R. Murty [25] and slightly improved in Clark [6].

Lemma 3. Let F_{1} be a Galois extension of ℚ and D a conjugacy class in G = Gal(F_{1}/ℚ). Given A > 0, there is B > 0 such that for

Q = x^{\frac{1}{η}} (log x)^{−B},

then

∑_{q≤Q}′ max_{(a,q)=1} max_{y≤x} |ψ(y, λ(D, q, a), F_{1}(ζ_{q})/ℚ) − δ(D, a, q)y| ≪ \frac{x}{log^{A} x},

where η = max(d − 2, 2), with

d = min_{M} max_{ω}[G : H]ω(1),

and where the ′ indicates summation over q such that F_{1} ∩ ℚ(ζ_{q}) = ℚ, which implies δ(D, a, q) = |D|/(ϕ(q)|G|). The min is taken over subfields M of F_{1} such that L(s, ω ⊗ χ, F_{1}(ζ_{q})/M) are holomorphic for all characters χ and the max is over characters of H = Gal(F_{1}/M).

This yields the following lemma.

Lemma 4. There are more than

δ_{1}x/(log x)^{2+1/4}

rational primes p such that (1) p ≤ x,

(2) (p, L_{2}/ℚ) ⊆ C_{2}^{∗},

(3) If ℓ | (p − 1), then ℓ ∈ d(L_{2}/ℚ, C_{2}^{∗}) or ℓ > x^{1/2η} exp (−(log x)^{1/4}), for some positive constant δ_{1}.

Proof: Consider the sequence A with P = P_{d}. To apply Lemma 1, the two conditions must be checked. The first condition is trivial since 2 ∈ d(L_{2}/ℚ, C_{2}^{∗}) and 0 ≤ 1/(p−1) ≤ 1/2 for p ≥ 3. Since ψ(x) ∼ x, partial summation implies that

∑_{w≤p<z} \frac{log p}{p − 1} = log \frac{z}{w} + O(1),

which implies the second condition for κ = 1 since only finitely many primes are contained in d(L_{2}/ℚ, C_{2}^{∗}). Since

|R_{q}| ≤ max_{(a,q)=1} max_{y≤x} |ψ(y, λ(D, q, a), F_{1}(ζ_{q})/ℚ) − δ(D, a, q)y|,

Lemma 3 implies that

∑_{\begin{matrix}q<x^{1/η}/(log x)^{B} \\ q|P (z) \end{matrix}} 3^{ν(q)}|R_{q}| ≪ x/(log x)^{4},

for some constant B ≥ 1. Choose z = x^{1/2η} exp(−(log x)^{3/4}) and ξ^{2} = x^{1/η}/(log x)^{B}. Apply Lemma 2 to obtain

S(A, P_{d}, z) ≥ XW (z) \{f (\frac{log ξ^{2}}{log z} ) − B_{1} \frac{L}{(log ξ)^{1/3}} \} − O (\frac{x}{(log x)^{4}} ) .

Lemma 5. There are more than

δ_{2}x/(log x)^{2+1/4}

prime elements ϖ of K such that (1) Nϖ = p ≤ x for some rational prime p,

(2) (ϖ, F/K) = σ,

(3) (ϖ, K_{ℓ}) ≠ 1 for all ℓ ∈ d(F/K, σ),

(4) If ℓ′ | (p − 1), then ℓ′ ∈ d(F/K, σ) or ℓ′ > x^{1/2η} exp (−(log x)^{1/4}), for some positive constant δ_{2}.

Proof: Consider the rational primes p found in Lemma 4. Choose a prime element Π of L_{2} lying above p. For some τ ∈ Gal(L_{2}/ℚ), (τ^{−1}Πτ, L_{2}/ℚ) ⊆ C_{2}^{∗}. If ϖ is a prime element of K lying below τ^{−1}Πτ, then ϖ has the desired properties.

The last lemma we require states that there are many prime elements ϖ so that ψ_{ϖ}(U_{S}) is large.

Lemma 6. Let s = |S| + r, where r is the rank of the unit group, then the number of prime elements ϖ of K for which |ψ_{ϖ}(U_{S})| < y is ≪ y^{(s+1)/s}.

Proof: The number of integer s-tuples (a_{1}, a_{2}, …, a_{s}) with

|a_{1}| + |a_{2}| + ⋯ + |a_{s}| ≤ y^{1/s}  (3)

is less than \frac{s+1}{s}y. If |ψ_{ϖ}(U_{S})| ≤ y, then

ω_{1}^{a_{1}}ω_{2}^{a_{2}} ⋯ ω_{s}^{a_{s}} ≡ ω_{1}^{b_{1}}ω_{2}^{b_{2}} ⋯ ω_{s}^{b_{s}}(mod ϖ),

for some pair of s-tuples satisfying (3) with the ω_{i} either units or prime elements in S. Then, ϖ divides the numerator of

ω_{1}^{a_{1}−b_{1}}ω_{2}^{a_{2}−b_{2}} ⋯ ω_{s}^{a_{s}−b_{s}} − 1.

The number of primes dividing this element is O(y^{1/s}). Thus the total number of primes ϖ such that |ψ_{π}(U_{S})| ≤ y is O(y^{(s+1)/s}).

Now, to prove the theorem, consider the primes ϖ found in Lemma 5. For these primes either |ψ_{ϖ}(U_{S})| < x^{1−1/2η} exp((log x)^{1/4})) or the only divisors of

|(R/Rϖ)^{∗}/ψ_{ϖ}(U)|  (4)

are contained in d(L_{2}/K, C_{2}^{∗}) = d(F/K, C). Since L_{2}/K is abelian we can choose η = max(2, n_{K} − 2), which implies

(1 − \frac{1}{2η} ) (\frac{s + 1}{s}) < 1.

The previous lemma implies that the primes satisfying the first condition may be disregarded. A prime ℓ dividing (4) splits completely in K_{ℓ}, but this is not possible since τ|_{K_{ℓ}} ≠ 1 for all ℓ ∈ d(F/K, σ) and all τ ∈ C_{2}^{∗}. Hence, for these primes the index (4) equals one, which proves the theorem.

Examples

The following lemma is helpful for verifying that the unit group maps onto

(R/(π_{1}^{a_{1}} ⋯ π_{m}^{a_{m}}))^{∗},

for all nonnegative integers a_{i}, i = 1, …, m.

Lemma 7. Suppose that π_{1}, …, π_{s} are non-ramified prime elements of inertia degree one in R not lying above 2. If a multiplicative submonoid M of R containing only elements of infinite order maps onto (R/(π_{1}^{2}π_{2}^{2} ⋯ π_{s}^{2}))^{∗}, then M maps onto (R/(π_{1}^{a_{1}}π_{2}^{a_{2}} ⋯ π_{s}^{a_{s}}))^{∗} for any choice of nonnegative integers a_{i}, i = 1, …, s.

Proof: Suppose the claim has been proved for all products π_{1}^{m_{1}} ⋯ π_{s}^{m_{s}}, such that m_{i} ≤ n_{i} for i = 1, …, s with at least one of the inequalities strict. Use the inductive assumption to find an element of M, ϵ_{1} such that ϵ_{1} ≡ 1(mod π_{i}^{n_{i}}) for i = 2, …, s and ϵ_{1} has order p_{1}^{n_{1}−2}(p_{1} − 1) modulo π_{1}^{n_{1}−1}π_{2}^{n_{2}} ⋯ π_{s}^{n_{s}}, where Nπ_{1} = p_{1}. Then,

ϵ_{1}^{p_{1}^{n_{1}−3}(p_{1}−1)} = 1 + kπ_{1}^{n_{1}−2}π_{2}^{n_{2}} ⋯ π_{s}^{n_{s}},
ϵ_{1}^{p_{1}^{n_{1}−2}(p_{1}−1)} ≡ 1 + k′π_{1}^{n_{1}}(mod π_{1}^{n_{1}−1}π_{2}^{n_{2}} ⋯ π_{s}^{n_{s}})

where π_{1} ∤ k, k′ which implies that ϵ_{1} has order p_{1}^{n_{1}−1}(p_{1} − 1) modulo π_{1}^{n_{1}}π_{2}^{n_{2}} ⋯ π_{s}^{n_{s}}. Similarly, elements ϵ_{i} ∈ M can be found such that ϵ_{i} ≡ 1(mod π_{j}^{n_{j}}) for j ≠ i and ϵ_{i} has order p_{i}^{n_{i}−1}(p_{i} − 1) modulo π_{1}^{n_{1}}π_{2}^{n_{2}} ⋯ π_{s}^{n_{s}}. Then the multiplicative group generated by ϵ_{1}, …, ϵ_{s} maps onto the coprime residue classes modulo π_{1}^{n_{1}} ⋯ π_{r}^{n_{s}}.

The first example is K, the splitting field of x^{4} − 18x^{2} + 4. K has an integral basis {1, α, α^{2}/2, α^{3}/2}, where α is a root of the polynomial. The unit group of K is generated by

−9 + α^{2}/2, 1 − 2α − α^{2}/2, 30 + 63α − 3/2α^{2} − 7/2α^{3}.

We consider the prime ideals of K with norm less than or equal to 7. Compute the factorizations of x^{4} − 18x^{2} + 4 modulo p for p ≤ 7.

x^{4} − 18x^{2} + 4 ≡ x^{4}(mod 2)
≡ (x^{2} + x + 2)(x^{2} + 2x + 2)(mod 3)
≡ (x^{2} + 3x + 3)(x^{2} + 2x + 3)(mod 5)
≡ (x + 3)^{2}(x + 4)^{2}(mod 7)

Using these factorizations, we can determine the image of the unit group modulo the prime ideal (7, α + 3).

−9 + α^{2}/2 ≡ −2 + α^{2}/2 + 7/2α^{2} ≡ −2 + 4α^{2} ≡ −2 + 2α ≡ −1 (7, α + 3)
1 − 2α − α^{2}/2 ≡ 1 − 2α + 3α^{2} ≡ 1 − 11α ≡ 1 − 4α ≡ −1 (7, α + 3)
30 + 63α − 3/2α^{2} − 7/2α^{3} ≡ 2 − 3/2α^{2} ≡ 2 + 2α^{2} ≡ 2 + α ≡ −1 (7, α + 3)

Therefore, the image of the unit group modulo (7, α + 3) is {±1}. There is only one nontrivial ideal of norm less than 7, namely (2, α) = (α) of norm 4. Only the classes ±1, ±3 modulo (7, α + 3) contain elements of norm less than 7. Hence, the norm is not a Euclidean algorithm for the ring of integers of K. But, since −9 + α^{2}/2 ≡ 102(mod (13, α + 12)^{2}), and 102 is a primitive root modulo 13^{2}, the theorem implies that the ring of integers of K is Euclidean.

Next, consider the field with generating polynomial x^{3} −x^{2} −24∗x+27. The integral basis is 1, α, γ = (−15 − α + α^{2})/3. The unit group is generated by 41 − 10α + 6γ and 31 + 16α + 10γ. As above, one can show that the ring of integers is not Euclidean for the norm by considering the residue classes modulo the ideal (2). Let π_{1} = 8 − α − 3γ of norm 7 and π_{2} = 1 + 3α + γ of norm 83. The unit group maps onto (R/(π_{1}^{2}π_{2}^{2}))^{∗}. Hence, the theorem implies that R is Euclidean.

We cannot apply the theorem to ℤ[\sqrt{14}]; however, for p a rational prime which does not split in K = ℚ(\sqrt{14}), consider the ring R = ℤ[\sqrt{14}][\frac{1}{p}]. We will choose p later on. The positive fundamental unit of K is ϵ = 15 + 4\sqrt{14}. Let π_{1} = 5 − \sqrt{14} of norm 11, π_{2} = 27 + 7\sqrt{14} of norm 43, and π_{3} = 3 − 2\sqrt{14} of norm 47. ϵ has order 110 modulo π_{1}^{2}, order 1806 modulo π_{2}^{2}, and order 1081 modulo π_{3}^{2}. −ϵ has order 55 modulo π_{1}^{2}, order 903 modulo π_{2}^{2}, and order 2162 modulo π_{3}^{2}. Thus, one can verify that the image of the multiplicative group generated by ±ϵ in (R/(π_{1}^{2}π_{2}^{2}π_{3}^{2}))^{∗} has index 2. The residue class 310417515 of order 2 modulo π_{1}^{2}π_{2}^{2}π_{3}^{2} is not contained in the image of the units. Now choose p = 1298852237 which is contained in this residue class and does not split in ℚ(\sqrt{14}), then the units of ℤ[\sqrt{14}][\frac{1}{p}] map onto (R/(π_{1}^{2}π_{2}^{2}π_{3}^{2}))^{∗}. To see that R is not Euclidean for the norm, note that up to multiplication by units, there is only one element of norm less than 4, 4 + \sqrt{14}. The units all map to 1 modulo (2). The residue class 1 + \sqrt{14} modulo (2) contains no elements of norm less than 4; hence, R is not Euclidean for the norm.

Acknowledgement

We would like to thank Rajiv Gupta and Michael Zieve for their careful comments on a preliminary version of this work.

References

1. E.S. Barnes and H.P.F. Swinnerton-Dyer, The Inhomogeneous Minima of Binary Quadratic Forms, Acta Math. 87 (1952), 259–323.

2. E. Berg, Über die Existenz eines Euklidischen Algorithmus in quadratischen Zahlkörpern, Kgl. Fysiogr. Sällsk. Lund Förh. 5 (1935), no. 5.

3. J. Buchmann and D. Ford, On the Computation of Totally Real Quartic Fields of Small Discriminant, Math. Comp. 52 (1989), 161–174.

4. J. Buchmann, M. Pohst, and J. v. Schmettow, On the Computation of Unit Groups and Class Groups of Totally Real Quartic Fields, Math. Comp. 53 (1989), 387–397.

5. H. Chatland, On the Euclidean Algorithm in Quadratic Number Fields, Bull. Amer. Math. Soc. 55 (1949), 948–952.

6. D. Clark, The Euclidean Algorithm for Galois Extensions of the Rational Numbers, Ph.D. Thesis, McGill University, Montréal, 1992.

7. H. Davenport, Euclid’s Algorithm in Cubic Fields of Negative Discriminant, Acta Math. 84 (1950), 159–179.

8. H. Davenport, Euclid’s Algorithm in Certain Quartic Fields, Trans. Amer. Math. Soc. 68 (1950), 508–532.

9. L.E. Dickson, Algebren und ihre Zahlentheorie, Orell Füssli Verlag, Zürich und Leipzig, 1927.

10. P. Erdös and Chao Ko, Note on the Euclidean Algorithm, Lond. Math. Soc. 13 (1938), 3–8.

11. R. Gupta, M.R. Murty, and V.K. Murty, The Euclidean Algorithm for S-integers in Conference Proceedings of the CMS Vol. 7, 1987, pp. 189–201.

12. H. Hasse, Zerlegung in Primelemente oder in Primhauptideale in Integritätsbereichen, J. Reine Angew. Math. 159 (1928), 3–12.

13. H. Heilbronn, On Euclid’s Algorithm in Real Quadratic Fields, Proc. Camb. Phil. Soc. 34 (1938), 521–526.

14. H. Heilbronn, On Euclid’s Algorithm in Cubic Self-Conjugate Fields, Proc. Camb. Phil. Soc. 46 (1950), 377–382.

15. H. Heilbronn, On Euclid’s Algorithm in Cyclic Fields, Can. J. Math. 3 (1951), 257–268.

16. N. Hofreiter, Quadratische Körper mit und ohne Euklidischen Algorithmus, Monatsh. Math. Phys. 42 (1935), 397–400.

17. C. Hooley, On Artin’s Conjecture, J. Reine Angew. Math. 225 (1967), 209–220.

18. K. Inkeri, Über den Euklidischen Algorithmus in quadratischen Zahlkörpern, Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. (1947), no. 41.

19. H. Iwaniec, Rosser’s Sieve, Acta Arithmetica 36 (1980), 171–202.

20. H.W. Lenstra, Jr., Euclidean Number Fields of Large Degree, Invent. Math. 38 (1977), 237–254.

21. H.W. Lenstra, Jr., On Artin’s Conjecture and Euclid’s Algorithm in Global Fields, Invent. Math. 42 (1977), 201–224.

22. A. Leutbecher and J. Martinet, Lenstra’s constant and Euclidean Number Fields, Astérisque 94 (1982), 87–131.

23. J.-F. Mestre, Corps eudlidiens, unités exceptionnelles et courbes elliptiques, J. Number Theory 13 (1981), 123–137.

24. T. Motzkin, On the Euclidean Algorithm, Bull. Amer. Math. Soc. 55 (1949), 1142–1146.

25. M.R. Murty and V.K. Murty, A Variant of the Bombieri-Vinogradov Theorem in Conference Proceedings of the CMS Vol. 7, 1987, pp. 243–271.

26. A. Oppenheim, Quadratic Fields with and without Euclidean Algorithm, Math. Ann. 109 (1935), 349–352.

27. O. Perron, Quadratische Zahlkörpern mit Euklidischem Algorithmus, Math. Ann. 107 (1932), 489– 495.

28. L. Rédei, Zur Frage des Euklidischen Algorithmus in quadratischen Zahlkörpern, Math. Ann. 118 (1942), 588–608.

29. R. Remak, Über den Euklidischen Algorithmus in reell-quadratischen Zahlkörpern, Jahres Ber. Deutsch. Math. Verein. 44 (1934), 238–250.

30. P. Samuel, About Euclidean Rings, J. Algebra 19 (1971), 282–301.

31. P. Weinberger, On Euclidean Rings of Algebraic Integers, Proc. Symp. Pure Math. 24 (1973), 321–332.

32. A.E. Western and J.C.P. Miller, Tables of Indices and Primitive Roots, University Press, Cambridge, 1968.

Department of Mathematics, McGill University, Montréal, Québec, H3A 2K6 Canada

Institut für Experimentelle Mathematik, Universität GHS Essen, Ellernstrasse 29, W-4300 Essen 12, Germany