THE EUCLIDEAN ALGORITHM

IN ALGEBRAIC NUMBER FIELDS

Franz Lemmermeyer

Institut für Mathematik Universität Heidelberg

Abstract. This article intends to survey what is known about Euclidean number fields; we will do this from a number theoretical (and number geometrical) point of view, i.e. we will not deal with questions concerning the number of steps of the Euclidean algorithm, etc. We have also tried to put some emphasis on the open problems in this field.

0. Definitions and general properties

An integral domain R is called Euclidean with respect to a given function f : R → ℕ if f has the following properties: (E–1) f(α) = 0 ⟺ α = 0 (E–2) for all α, β ∈ R \ {0} there is an γ ∈ R such that f(α − βγ) < f(β). We call such an f a Euclidean function on R. There are equivalent definitions of Euclidean rings and functions, most of which are studied in Lenstra (1974). For example, a function f : R → ℝ_{≥0} satisfying (E–1) and (E–2) is called Euclidean if it also satisfies (E–3) For every κ > 0 the set {f(α) : α ∈ R, f(α) < κ} is finite.

It is easily seen that an integral domain which is Euclidean with respect to a realvalued function is also Euclidean with respect to a suitably chosen integer-valued function. Variants of Euclidean functions have been studied by Picaret (1972), Lenstra (1974), and Hiblot (1975).

For every integral domain R we can define the Euclidean minimum M(R, f) of R with respect to a given integer-valued function f satisfying (E–1) by

M(R, f) = inf {κ > 0 : for all α, β ∈R \ {0} there exists γ ∈ R
such that f(α − βγ) < κ · f(β)}.

Obviously R is (resp. is not) Euclidean with respect to f if M(R, f) < 1 (resp. M(R, f) > 1). If M(R, f) = 1, both possibilities actually occur. If β ≠ 0 is no unit in R, then we have M(R, f) ≥ f(β)^{−1}.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 11 R 04; Secondary 11 H 50.

Key words and phrases. Euclidean algorithm, geometry of numbers.

Let S be an integral domain contained in R; then

M(R/S, f) = inf {κ > 0 : for all α, β ∈S \ {0} there exists γ ∈ R
such that f(α − βγ) < κ · f(β)}

is called the relative Euclidean minimum of S in R. It would be interesting to find non-trivial inequalities relating M(R, f), M(S, f) and M(R/S, f), especially if S = 𝔒_{K} and R = 𝔒_{L} are the rings of integers in an extension L/K of number fields and f is the absolute value of the norm (cf. Sect. 1).

If R is Euclidean, the function f_{min} defined by

f_{min}(α) = min {f(α) : f is a Euclidean function on R}

is called the minimal Euclidean function on R. It is easily seen that f_{min} is in fact a Euclidean function on R. For every integral domain R, define the Motzkin sets E_{k}, k ≥ 0, by

E_{0} = {0},
E_{1} \ {0} = R^{∗}, the unit group of R and, generally,
E_{k} \ {0} = {α ∈ R : each residue class mod α contains a β ∈ E_{k−1}},
E_{∞} = ⋃_{k≥0} E_{k}

The Motzkin sets of R = ℤ are easily computed:

E_{0} = {0}, E_{1} = {0, ±1}, E_{2} = {0, ±1, ±2, ±3}, …, E_{k} = {0, ±1 …, ±(2^{k} − 1)}.

The following observation is due to Motzkin (1949):

(0.1) R is Euclidean if and only if E_{∞} = R. If E_{∞} = R, then the function f_{M} defined by f_{M}(α) = min {k ∈ ℕ : α ∈ E_{k}} coincides with the minimal Euclidean function on R.

Our next result provides us with examples of Euclidean functions f such that M(R, f) = 1:

(0.2) Let R be an integral domain; then i) R = E_{1} if and only if R is a field; ii) if R is not a field, then R ≠ E_{k} for all k ∈ ℕ; if, moreover, R is

Euclidean, then M(R, f_{min}) = 1.

In 1976 Cooke introduced the following more general concept: let R be an integral domain. A sequence of equations (with α, β, γ_{i}, ρ_{i} ∈ R)

α = βγ_{1} + ρ_{1},
β = ρ_{1}γ_{2} + ρ_{2},
…
ρ_{k−2} = ρ_{k−1}γ_{k} + ρ_{k}

is called a division chain starting from the pair (α, β); we say that R is quasi-Euclidean, if we can find a function f : R → ℕ with the properties (E_{q}-1) f(α) = 0 ⟺ α = 0, (E_{q}-2) for every pair α, β ∈ R \ {0} there exists a k-stage division chain for some

k ∈ ℕ such that f(ρ_{n}) < f(β). If we can replace (E_{q}-2) by the stronger condition

(E_{k}-2) there is a k ∈ ℕ such that for every pair α, β ∈ R \ {0} there exists an

n-stage division chain for some n ≤ k with f(ρ_{k}) < f(β), then R is called k-stage Euclidean with respect to f. We also can introduce k-Euclidean minima in an obvious way. Several equivalent definitions of quasi-Euclidean rings have been given by Cooke (1976), Bougaut (1976, 1980) and Leutbecher (1977/78).

Lenstra (1979a) introduced Euclidean ideal classes; they generalize Euclidean rings because the trivial ideal class [R] is Euclidean if and only if R is Euclidean. Euclidean ideal classes have been investigated by van der Linden (1984). Nontrivial Euclidean ideal classes seem to occur very rarely: if K is a real quadratic field which contains a non-trivial Euclidean ideal class, then disc K = 40, 60, 85. The known examples in degree ≥ 3 are:

- the cubic field with disc K = −283 and h(K) = 2 (van der Linden),

- the cubic field with disc K = −331 and h(K) = 2 (Lemmermeyer),

- the quartic field ℚ(\sqrt{−3}, \sqrt{13} ) with h(K) = 2 (Lenstra). Schulze (1994) defined Euclidean systems; they generalize Euclidean ideal classes,

and the simplest Euclidean systems correspond to the Dedekind-Hasse-test (cf. Hasse (1928)):

(0.3) R is a principal ideal ring if and only there is a function f : R → ℕ satisfying (E–1) with the following property: for every α, β ∈ R such that β ∤ α there exist λ, μ ∈ R such that f(λα − μβ) < f(β).

1. The norm as a Euclidean function

Let K be an algebraic number field and 𝔒_{K} its ring of integers. If the absolute value of the norm is a Euclidean function, 𝔒_{K} (or, by abuse of language, K) is called norm-Euclidean. The Euclidean minimum of K with respect to the norm is called norm-Euclidean minimum and will be denoted by M(K). The following theorem of Weinberger (1973) suggested strongly the existence of number fields that are Euclidean with respect to functions different from the norm:

(1.1) Assume that GRH holds; then every number field K with unit rank ≥ 1 has class number 1 if and only if K is Euclidean with respect to a suitably chosen function f.

On the other hand, the work of O’Meara (1964) and Vaserstein (1972) (cf. Cooke (1976)) shows unconditionally

(1.2) Every number field K with unit rank ≥ 1 has class number 1 if and only if it is k-stage norm-Euclidean for some k ∈ ℕ.

For every ξ ∈ K, define M(ξ) = inf {|N_{K/ℚ}(ξ−η)| : η ∈ 𝔒_{K}}. M(ξ) is called the Euclidean minimum at ξ, and we have M(K) = sup {M(ξ) : ξ ∈ K}. Obviously, M(ξ) = M(ξ − η) for every η ∈ 𝔒_{K}, i.e. M(ξ) only depends on the class of ξ in K/𝔒_{K}. Now let

C_{1} = {ξ ∈ K/𝔒_{K} : M(ξ) = M(K)}

and define the second Euclidean minimum of K by

M_{2}(K) = sup {M(ξ) : ξ ∈ (K/𝔒_{K}) \ C_{1}}.

Obviously M_{2}(K) ≤ M(K) = M_{1}(K), and if this inequality is strict, we say that M_{1}(K) is isolated. The Euclidean minima M_{k}(K), k ≥ 2, are defined in a similar way. There are number fields with an infinite sequence of strictly decreasing Euclidean minima, and fields whose second minimum is not isolated. Barnes and Swinnerton-Dyer (1952) showed

(1.3) If K is a number field with unit rank ≥ 1 and if C_{1} is finite, then the minimum M_{1}(K) is isolated.

In order to prove that a given number field K is norm-Euclidean, we choose a ℚ-basis {α_{1}, ..., α_{n}} of K and let ϕ : α = ∑ a_{i}α_{i} → (a_{1}, …, a_{n}) ∈ ℝ^{n}; after identifying K and ϕ(K), we find that 𝔒_{K} is a lattice in \overline{K} = ℝ^{n}, and that K is dense in \overline{K}. We extend the norm N_{K/ℚ}α = ∏_{σ} α^{σ} on K (here σ runs through all n = (K : ℚ) embeddings of K into ℂ) to a continuous function

N : ℝ^{n} → ℝ : (ξ_{1}, …, ξ_{n}) → N(x) = ∏_{σ} (∑_{j=1}^{n} ξ_{j}α_{j}^{σ}) .

Obviously K is norm-Euclidean if and only if for all ξ ∈ K we can find η ∈ 𝔒_{K} such that |N(ϕ(ξ) − ϕ(η))| < 1; we see that it suffices to show that for every real ξ ∈ \overline{K} we have |N(ξ − ϕ(η))| < 1 for a suitably chosen η ∈ 𝔒_{K}.

Therefore we define the Euclidean minimum at x ∈ \overline{K} by

M(x) = inf {|N(x − ϕ(η))| : η ∈ 𝔒_{K}},

and call M(\overline{K}) = sup \{M(x)|x ∈ \overline{K}\} the inhomogeneous minimum of K; it is clear by definition that M(K) ≤ M(\overline{K}). Let x ∈ \overline{K} and a real ε > 0 be given; it follows from the definition of M(\overline{K}) that we can find η ∈ 𝔒_{K} with |N(x − ϕ(η))| < M(\overline{K}) + ε. If we can satisfy the stronger inequality |N(x − ϕ(η))| ≤ M(\overline{K}) for every x ∈ \overline{K} we shall say that the minimum M(\overline{K}) is attained.

(1.4) We have M(K) = M(\overline{K}) for every number field K with unit rank 1, and there exist x ∈ \overline{K} with M(x) = M(\overline{K}).

This equality has been observed by Barnes and Swinnerton-Dyer (1952); they proved it for n = 2, and van der Linden (1985) gave a proof for fields with unit rank 1. Computations seem to suggest the following conjectures for number fields K with unit rank ≥ 1:

C-1 M_{1}(K) is isolated even if C_{1} is not finite; C-2 M_{1}(K) is always rational; C-3 M_{1}(K) = M_{1}(\overline{K}) for every number field with unit rank ≥ 1; C-4 in (1.4), x = ∑ a_{j}α_{j} has coordinates a_{i} ∈ K; C-5 in (1.4), x can be chosen from the dense subset K (i.e. x can be chosen to

have rational coordinates a_{i}; such x are called rational points in \overline{K}). Call ESp(K) = {M(x)|x ∈ ℝ^{n}} the Euclidean spectrum of K; ESp(K) is known

to be closed as a subset of the reals (theorem L of Barnes and Swinnerton-Dyer). Let ∂ ESp(K) be the boundary of ESp(K) (with respect to the usual topology on ℝ). Another question is

C-6 Is ∂ ESp(K) ⊂ K, if K is totally real?

For related questions, we refer the reader to Berend and Moran (1992). The background necessary for the computation of Euclidean minima has been provided by Barnes and Swinnerton-Dyer; although the presentation of some of the proofs given in their papers (1952a, b) can be simplified slightly, these articles still are worth reading, and they are recommended to anyone interested in computing minima of number fields of small degree.

The inequality M(K) ≤ 2^{−n}\sqrt{d} for totally real number fields of degree n and absolute value of discriminant d is called the ”Minkowski conjecture”; it is known to hold for n ≤ 5, and Chebotarev could prove that M(K) ≤ 2^{−n/2}\sqrt{d}. Similar results (not even a conjecture) for fields with mixed signature are not known except for a theorem of Swinnerton-Dyer (1954) concerning complex cubic fields (see Sect. 4)

In the light of Weinberger’s result we are interested in functions f that might serve as Euclidean functions on number fields K with unit rank ≥ 1 and class number 1. Of course, if R is Euclidean we can always take f = f_{min}; but this function is not very useful if we want to prove that R is Euclidean because f_{min} is rather hard to compute. Lenstra (1974) proposed to look at ”weighted norms” instead: first we define a multiplicative function ϕ : I_{K} → ℝ, where I_{K} denotes the group of fractional ideals of 𝔒_{K}, by giving its values on the prime ideals; to this end choose a prime ideal 𝔭, a real number c > 0, and define ϕ(𝔭) = c, ϕ(𝔮) = N(𝔮) for every prime ideal 𝔮 ≠ 𝔭. Then extend ϕ multiplicatively to all ideals of 𝔒_{K} and put ϕ(α) = ϕ(α𝔒_{K}) for elements α ∈ K. Then ϕ = ϕ_{𝔭,c} is a well defined multiplicative function with the property (E–3), and

w(𝔭) = {c ∈ ℝ : ϕ_{𝔭,c} is a Euclidean function on 𝔒_{K}}

is called the Euclidean window of the weighted norm ϕ.

(1.5) The Euclidean window w(𝔭) of a weighted norm f is a (possibly empty) interval contained in ]1, ∞[.

Using an incredibly simple idea, Clark (1993) succeeded in proving that f = f_{𝔭,c} is a Euclidean function in the quadratic number field ℚ(\sqrt{69} ) for 𝔭 = (23, \sqrt{69}) and every c > 25. This was done as follows: first one observes that M_{1} is isolated and that M_{2} < 1. For every ξ ∈ \overline{K} \ C_{1} we can find η ∈ 𝔒_{K} such that the usual norm of (ξ − η) is < 1; if the nominator of ξ − η is not divisible by 𝔭, we will also have f(ξ − η) < 1. In order to get rid of the points ξ − η with nominator divisible by 𝔭, we show that for every ξ ∈ \overline{K} \C_{1} we can find η_{1}, η_{2} ∈ 𝔒_{K} such that |N(ξ −η_{j})| < 1 for j = 1, 2 and η_{1} − η_{2} ≢ 0 mod 𝔭. Unfortunately, this method does not seem to work for other quadratic number fields.

In 1994, Clark and Murty devised a method for proving number fields to be Euclidean with respect to functions different from the norm; this method applies to totally real Galois extensions of degree ≥ 3. In his thesis (1992), Clark showed that the 165 totally real quartic number fields with class number 1 and discriminant less than 10^{6} as well as the cyclic cubic number fields with discriminant less than 5 · 10^{5} are Euclidean if and only if they have class number 1.

Cooke and Weinberger have made some very interesting observations concerning the k-stage Euclidean algorithm in number fields: define continued fractions [γ_{1}, γ_{2}, …, γ_{k}] of length k (with coefficients γ_{j} ∈ 𝔒_{K}) by

[γ_{1}, γ_{2}, …, γ_{k}] = γ_{1} + \frac{1}{γ_{2} + \frac{1}{γ_{3} + ⋯ + \frac{1}{γ_{k}}}}

Let CF_{k}(K) be the set of all continued fractions of length ≤ k with coefficients in 𝔒_{K}. Then for all α, β ∈ 𝔒_{K} there exists a k-stage division chain of length k ≤ n such that f(ρ_{k}) < f(β) if and only if we can find γ ∈ CF_{k}(K) with |N(α/β−γ)| < 1.

The k-stage Euclidean minimum of K is the real number

M^{k}(K) = inf {κ : for all ξ ∈ K there is a γ ∈ CF_{k}(K) : |N(ξ − γ)| < κ}

and the inhomogeneous minimum of K is defined by replacing K by \overline{K}.

Let us define sets B_{k} = {ξ ∈ K : |N(ξ − γ)| ≥ 1 for all γ ∈ CF_{k}(K)} for k ≥ 1; obviously we have B_{1} ⊇ B_{2} ⊇ … ⊇ B_{∞} = ⋂ B_{k}; if B_{∞} = B_{k} for some k ∈ ℕ we say that K has Euclidean depth k and write Ed(K) = k.

(1.6) Assume that the generalized Riemann hypothesis holds. Then Ed(K) ≤ 4 for every number field K with unit rank ≥ 1, and Ed(K) ≤ 2 if K has at least one real embedding.

The inequalities Ed(K) ≤ 5 (resp. Ed(K) ≤ 3) are due to Cooke and Weinberger (1976); Lemmermeyer (1989) noticed that these inequalities are strict.

Using results of Vaserstein, Cooke was able to show that B_{∞} is discrete. By defining a suitable equivalence relation on the points in B_{∞}, Cooke could show that the number of equivalence classes equals h − 1, where h = h(K) is the class number of K.

2. Imaginary quadratic number fields

If K is an imaginary quadratic number field, i.e. K = ℚ(\sqrt{−m}), m a square free integer, the situation is completely clear (we write D(−m) for the ring of integers in ℚ(\sqrt{−m})):

(2.1) The rings D(−m) are Euclidean if and only if m = 1, 2, 3, 7, 11, and in these cases the norm is a Euclidean function.

In order to prove (2.1) we have to show:

a) D(−m) is norm-Euclidean for m = 1, 2, 3, 7, 11;

b) if f is a Euclidean function on D(−m), then m = 1, 2, 3, 7, 11.

The first proofs of a) are due to Gauss (m = 1, 3 (1801)), Dirichlet (1847), Cauchy (m = 1, 3 (1847)), Wantzel (1847), Traub (m = 1, 2 (1867)), and Dedekind (1893), who also noticed that these values of m are the only ones for which K is norm-Euclidean. Proofs for this fact have later been given by Birkhoff (1906) and Schatunowsky (1911). In 1948 Motzkin gave the first proof of b); this result has been rediscovered several times, for example by Dubois and Steger (1958) or Chadid (1984).

Wantzel (1847) and Traub (1867) were the first to show that M(f) = 1 for R = D(−3), where f is the norm, although the following proposition can easily be deduced from a result of Dirichlet (1842):

(2.2) The Euclidean minimum M(R, N) of R = D(−m) with respect to the norm is given by

\frac{(|m| + 1)}{4}, if R = ℤ [\sqrt{−m}], and
\frac{(|m| + 1)^{2}}{16m} , if R = ℤ [\frac{1 + \sqrt{−m}}{2}]

This implies the inequalities \frac{|d|}{16} < M(K) ≤ \frac{|d|+4}{16} for imaginary quadratic fields K with discriminant d.

Concerning k-stage Euclidean rings, we have the result of P. Cohn (1966)

(2.3) D(−m) is k-stage Euclidean if and only if it is Euclidean.

The Dedekind-Hasse-test (0.3) with f = N has often been applied to show that D(−19) is a principal ideal domain; cf. Wilson (1973), Feyzioglu (1992).

3. Real quadratic number fields

As in Sect. 2, let D(m) denote the ring of integers of ℚ(\sqrt{m}), where m is assumed to be squarefree. The real quadratic number fields which are norm-Euclidean are known:

(3.1) The rings D(m) are norm-Euclidean if and only if

m = 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73.

The if-part of (3.1) can be proved easily; it is the ”only if” that causes the difficulties. The following table shows the evolution of the proof: 1848 Wantzel shows that ℚ(\sqrt{m}) is norm-Euclidean for m = 2, 3, 5, and claims

that this holds also for m = 6, 7, 13, 17. 1927 Dickson shows that ℚ(\sqrt{m}) is norm-Euclidean if m = 2, 3, 5, 13 and asserts

that these are the only such values.

1933 Perron detects Dickson’s error by showing that ℚ(\sqrt{m}) is norm-Euclidean for m = 6, 7, 11, 17, 21, 29; moreover he asks if every real quadratic number field with class number 1 is norm-Euclidean. In a letter to Perron, Schur shows that ℚ(\sqrt{47} ) is not norm-Euclidean.

1934 Oppenheim finds a clever method to prove that ℚ(\sqrt{m}) is norm-Euclidean for m = 2, 3, 5, 6, 7, 11, 17, 21, 29, 33, 37, 41, and shows that ℚ(\sqrt{m}) is not norm-Euclidean for m = 23, 31, 53.

1935 Fox and Berg show that if ℚ(\sqrt{m}) is norm-Euclidean and m ≡ 2, 3 mod 4, then m = 2, 3, 6, 7, 11, 19, and Berg is able to prove that ℚ(\sqrt{47} ) is indeed norm-Euclidean. Hofreiter shows that ℚ(\sqrt{57} ) is norm-Euclidean; moreover he proves that ℚ(\sqrt{21} ) is the only norm-Euclidean field among the ℚ(\sqrt{m}) with m ≡ 21 mod 24.

1936 Behrbohm and Redei find all norm-Euclidean ℚ(\sqrt{m}) with m ≡ 5 mod 24. 1938 Schuster treats the case m ≡ 9 mod 24.

Erdös and Ko show that there are only finitely many norm- Euclidean D(m) with m ≡ 1 mod 8 prime, and Heilbronn extends this to composite values of m.

1940 Brauer shows m ≤ 109 for all norm-Euclidean ℚ(\sqrt{m}) with m ≡ 13 mod 24. 1942 Rédei finds all norm-Euclidean ℚ(\sqrt{m}), m ≡ 17 mod 24, and shows that

D(73) is norm-Euclidean. Moreover he shows that D(m) is not norm-Euclidean for m = 61, 89, 109, 113, 137. This leaves only the m ≡ 1 mod 24 undecided. Redei also claims that D(97) is norm-Euclidean.

1944 Hua shows m < e^{250}, if ℚ(\sqrt{m}) is norm-Euclidean and m ≡ 1 mod 4 is

prime. 1947 Inkeri shows that the only norm-Euclidean fields with disc K < 5000 are

the known ones. 1948 Davenport proves disc K < 2^{14} = 16384 for every norm-Euclidean real

quadratic number field. 1949 Chatland shows that there are no norm-Euclidean fields whose discriminants

lie between 601 and 16 384. 1950 Chatland and Davenport, unaware of the results of Inkeri, show that there

are no norm-Euclidean fields with 193 ≤ disc K ≤ 601. 1952 Barnes and Swinnerton-Dyer discover that D(97) is not norm-Euclidean. We know the following bounds for Euclidean minima of quadratic fields:

(3.2) For real quadratic fields K with d = disc K, we have

\frac{\sqrt{d}}{16 + 6\sqrt{6}} ≤ M(K) ≤ \frac{1}{4}\sqrt{d}

The upper bound, due to Minkowski, is easily seen to be best possible:

(3.3) Let n be an odd integer, put m = n^{2}+1 and R = ℤ[\sqrt{m}]; then the Euclidean minimum of R is M = \frac{n}{2}, and this minimum is attained exactly at the points ξ ≡ \frac{1}{2} \sqrt{m} mod R.

Since m is squarefree for an infinite number of n, and R = D(m) in this case, the upper bound in (3.2) is in fact best possible. Heinhold (1939), Barnes and Swinnerton-Dyer (1952), and Varnavides have given results of this kind for a lot of other orders in real quadratic fields.

The lower bound D ≥ \frac{1}{128} for the ”Davenport constant” D = sup M(K)/\sqrt{d} is due to Davenport (1950). It was improved to D ≥ \frac{1}{51} by Cassels (1952), and to the result given in (3.2) by Ennola (1958).

The minima M_{i}(\overline{K}), i ≥ 1, have been investigated thoroughly for many quadratic number fields; we cite a few examples that show some of the phenomena that can occur:

(3.4) (Davenport (1948)) Let K = ℚ(\sqrt{5} ); then ω = \frac{1}{2}(1+\sqrt{5} ) is the fundamental unit of K, and we have M(K) = \frac{1}{4}. There is an infinite sequence of isolated minima M_{i}(K) given by

M_{i+1}(\overline{K}) = \frac{F_{6i−2} + F_{6i−4}}{4(F_{6i−1} + F_{6i−3} − 2)}

for all i ≥ 1, where F_{i} is the i-th number in the Fibonacci sequence defined by F_{0} = F_{1} = 1, F_{n+1} = F_{n} + F_{n−1}. The sequence of minima begins with M_{1} = \frac{1}{4}, M_{2} = \frac{1}{5}, M_{3} = \frac{19}{121}, …, and we have M_{∞}(\overline{K}) = lim M_{i}(\overline{K}) = \frac{1}{4ω} . The sets C_{i}(\overline{K}) = \{x ∈ \overline{K} : M(x) = M_{i}(\overline{K}), where the minima are attained, are C_{1} = \{(0, \frac{1}{2}), (\frac{1}{2}, 0)\}, C_{2} = \{(0, ±\frac{1}{5}), (0, ±\frac{2}{5})\}, and, generally

C_{k} = \{ξ ∈ K : ξ ≡ \frac{ω^{6i−3} + 1}{2(ω^{6i−2} − 1)}ε mod 𝔒_{K}, ε a unit\}.

As Varnavides (1948b) has shown, ℚ(\sqrt{2}) has similar properties; in general, however, the results are much more complicated:

(3.5) (Inkeri (1949)) Let K = ℚ(\sqrt{13} ); then M_{1}(\overline{K}) = \frac{1}{3}, M_{2}(\overline{K}) = \frac{4}{13}, and

C_{1} = \{ (±\frac{1}{6}, \frac{1}{6}) , (±\frac{1}{6} − \frac{1}{6}η^{k}, ±\frac{1}{6} + \frac{1}{6\sqrt{13}}η^{k}) \},

where k ∈ ℕ and η = \frac{1}{2} (−3 + \sqrt{13}), and

C_{2} = \{ (0, ±\frac{2}{13}) , (0, ±\frac{3}{13}) \}.

The minimum M_{1}(\overline{K}) is not attained.

Barnes and Swinnerton-Dyer (1952a) have generalized (3.5) to all fields ℚ(\sqrt{m}) with m = (2n + 1)^{2} + 4, n ≥ 1. They also computed an infinite sequence of minima for m = 13 and noticed that this sequence continues even beyond the limit M_{∞} = lim_{k→∞} M_{k}. On the other hand we know

(3.6) (Godwin (1963)) Let K = ℚ(\sqrt{23} ); then the first minimum M_{1}(\overline{K}) = \frac{77}{46} is attained and isolated, whereas M_{2}(\overline{K}) = \frac{1}{46} (20\sqrt{23} − 31) is not isolated.

It is easy to see that the points

x_{k} = \frac{1}{2} + (\frac{1}{2} − \frac{2}{23} + \frac{2}{23}ε^{−k}) \sqrt{23}, k ∈ ℕ_{0},

have an attained minimum μ = \frac{1}{46} (20\sqrt{23} − 31). Moreover, it is obvious that the x_{k} converge to x = \frac{1}{2} + (\frac{1}{2} − \frac{2}{23}) \sqrt{23}, and that M(x) = M_{1}(\overline{K}) = \frac{77}{46}. Godwin has shown that x is (up to conjugation and translation mod 𝔒_{K}) the only point such that M(x) > μ, and that each x_{k} is the limit of a series x_{k,i} of (rational) points in K such that μ = lim M(x_{k,i}); since the M(x_{k,i}) are rational and M is not, M_{2}(K) is not isolated. It seems likely that the x_{k} generate C_{2}, which would imply that M_{2} is attained.

The first example of a quadratic number field with an infinite set C_{2} such that C_{1} is the set of accumulation points of C_{2} is also due to Godwin (1955): in ℚ(\sqrt{73} ), M_{2} is isolated, and C_{2} consists of irrational points converging to rational points of C_{1}; in particular, M_{2}(K) < M_{2}(\overline{K})!

A numerically simpler example is the following:

(3.7) In K = ℚ(\sqrt{69} ), we have

\begin{matrix}M_{1} = \frac{25}{23}, & C_{1} = \{ ± \frac{4}{23} \sqrt{69}\}, \\ M_{2} = \frac{1}{1058} (3795 − 345\sqrt{69}) , & C_{2} = \{(±P_{k}, ±P′_{k})\}, \end{matrix}

where

P_{k} = \frac{1}{2}ε^{−k} + (\frac{4}{23} + \frac{1}{2\sqrt{69}}ε^{−k}) \sqrt{69},
P′_{k} = \frac{1}{2}ε^{−k} − (\frac{4}{23} + \frac{1}{2\sqrt{69}}ε^{−k}) \sqrt{69}.

Here ε = \frac{1}{2} (25 + 3\sqrt{69} ) is the fundamental unit in ℚ(\sqrt{69} ), and the points P_{k}, Pk^{′} have the limits ±\frac{4}{23} \sqrt{69} in C_{1}. Both M_{1}(K) = M_{1}(\overline{K}) and M_{2}(\overline{K}) are isolated, and M_{2}(K) < 0.875 < M_{2}(\overline{K}).

The Euclidean and inhomogeneous minima M_{i}(K) of real quadratic fields K may or may not have the following properties:

A_{i}: M_{i}(\overline{K}) is attained;
F_{i}: C_{i}(\overline{K}) is finite;
E_{i}: M_{i}(\overline{K}) = M_{i}(K);
I_{i}: M_{i}(\overline{K}) is isolated;
AP_{i}: I_{i} holds, and C_{i}(\overline{K}) is the set of accumulation points of C_{i+1}(\overline{K});

we know that F_{i} ⇒ A_{i}, and that F_{2} ⇒ ¬AP_{i}. Moreover, E_{1} is true, and we conjecture that I_{1} always holds.

The following combinations are known to occur:

\begin{matrix}m & A_{1} & F_{1} & AP_{1} & A_{2} & F_{2} & I_{2} & AP_{2} & E_{2} \\ 5 & x & x & no & x & x & x & no & x \\ 7 & x & x & no & x & x & x & x? & x \\ 13 & no & no & no & x & x & x & no & x \\ 23 & x & x & x & x? & no & no & − & x \\ 69 & x & x & x & x & no & x & ? & no \end{matrix}

Here ”x” means, that D(m) has the corresponding property, while ”x?” denotes a conjecture. This leaves, of course, a lot of questions unanswered:

- is there a D(m) such that F_{2} and AP_{1} are simultaneously false?

- is there a D(m) such that F_{2} holds, but I_{2} does not?

etc. The known examples of 2-stage norm-Euclidean rings D(m) are

m = 14, 22, 23, 31, 38, 43, 46, 47, 53, 59, 61, 62,
67, 69, 71, 77, 89, 93, 97, 101, 109, 113, 129, 133,
137, 149, 157, 161, 173, 177, 181, 193, 197, 201, 213, 253.

The following observation concerning Euclidean windows is due to Lemmermeyer (1989):

(3.8) Let K = ℚ(\sqrt{14} ) and define a weighted norm f in K by f(𝔭) = c, where 𝔭 = (2, \sqrt{14}) is the unique prime ideal above (2). If f is a Euclidean function on D(14), then necessarily 5 < c^{2} < 7, i.e., w(𝔭) ⊆ ]\sqrt{5}, \sqrt{7}[.

This shows again that D(14) is not norm-Euclidean, because the absolute value of the norm coincides with f_{𝔭,2}, and c = 2 lies outside the Euclidean window of 𝔭. It is tempting to try the value c = \sqrt{6}; actually Bedocchi (1985) has studied a function that – although not even being multiplicative – does not differ much from this f. I have not been able to prove that the Euclidean window of 𝔭 is non-empty using the method of Clark that succeeds for D(69); even a modification of this idea due to R. Schroeppel and G. Niklasch does not seem to work.

Euclidean minima of real quadratic number fields have been computed by Heinhold (1939), Davenport (1947), Varnavides (1948, 1949, 1970a-b), Bambah (1950, 1951), Inkeri (1950), Barnes and Swinnerton-Dyer (1952a-b, 1954), Godwin (1963, 1965), Bedocchi (1989), and Lemmermeyer (1989); the table at the end of our survey gives the minima for all m ≤ 102.

4. Cubic number fields

I. Complex cubic number fields.

It was Davenport (1951) who first could prove that there are only finitely many norm-Euclidean complex cubic number fields; the best lower bound for M(\overline{K}) so far has been obtained by Cassels (1952) (also, cf. van der Linden (1984), who notes that this bound does not seem to be best possible):

(4.1) If K is a complex cubic number field with d = |disc K|, then

\frac{\sqrt{d}}{420} ≤ M(\overline{K}) ≤ \frac{d^{2/3}}{16\sqrt[3]{2}}.

In particular, d < 170 520 if K is norm-Euclidean.

The upper bound is due to Swinnerton-Dyer (for fields with |d| ≤ 1236, (4.1) has been proved by direct computation), who also showed that the exponent 2/3 and the constant 16\sqrt[3]{2} cannot be improved. Note that we cannot define a Davenport constant since we do not know if the exponent 1/2 in the lower bound is best possible or not; it seems that no one has yet dared to conjecture that this exponent can be improved to 2/3.

Already in 1848 Wantzel claimed that the cubic field with discriminant −23 is norm-Euclidean. The next result concerning the Euclidean algorithm in complex cubic fields was obtained more than a hundred years later by Prasad (1950), who showed M(K) = \frac{1}{5} for the cubic field with disc K = −23. In 1967, Godwin showed that the fields with −23 ≥ disc K ≥ −152 are norm-Euclidean, and Taylor (1976) found all norm-Euclidean fields with 0 > disc K > −680. The pure cubic number fields wich are norm-Euclidean were determined by Cioffari (1979): there are only three, namely ℚ(\sqrt[3]{m}) with m = 2, 3, 10. Finally, Lemmermeyer (1989) computed the Euclidean minima for many complex cubic fields and confirmed the computations of Taylor and Cioffari.

In the tables below, let E denote the number of fields in a given interval which are norm-Euclidean; the number of those which are not resp. whose Euclidean nature is unknown, will be denoted by N and U, respectively.

disc k  E  N  U  Σ
0 < −d ≤ 200  18  1  0  19
200 < −d ≤ 400  15  9  0  24
400 < −d ≤ 600  16  10  0  26
600 < −d ≤ 800  7  20  0  27
800 < −d ≤1000  1  24  6  31
1000 < −d ≤1200  0  26  3  29
1200 < −d ≤1400  0  30  5  35
Σ  57  120  14  191

It is surprising that all cubic fields with 0 > disc K > −419 have an attained Euclidean minimum M_{1}(\overline{K}) with finite C_{1}(K); this has to be seen in contrast to the situation for quadratic fields, where already ℚ(\sqrt{13} ) and ℚ(\sqrt{29} ) have infinite C_{1}(K) and minima M_{1}(\overline{K}) which are not attained. The fields with |disc K| < 1000 whose Euclidean nature remains unknown have discriminants disc K = −856, −876, −888, −971, −996, −999.

As in the quadratic case it is possible to compute the Euclidean minima of an infinite sequence of fields:

(4.2) Let K be the number field defined by the real root α of f(x) = x^{3} + 2ax − 1 (where a ≥ 1) and let R = ℤ[α]. Then M(K) = M(\overline{K}) = \frac{1}{2}(a^{2} − a + 1), and this minimum is attained exactly at ξ ≡ \frac{1}{2}(1 + α + α^{2}) mod R.

This theorem is due to Swinnerton-Dyer (1954) for sufficiently large a ≥ 1; Lemmermeyer (1989) observed that (4.2) is valid for all a ≥ 1. This sequence incidentally shows that the upper bound in (4.1) is best possible. Similar results for sufficiently large a are known for other families of cubic number fields (cf. Swinnerton-Dyer (1954)).

The idea of Clark (1993) has been used to show that the complex cubic fields with discriminants −199, −327 and −351 are Euclidean with respect to a weighted norm:

K  disc K M_{1}(K) M_{2}(K)  𝔭  w(𝔭)
α^{3} + 4α^{2} + α + 1 = 0 −199  1  < 0.75 (7, α − 1) ]7, ∞[
α^{3} − 2α^{2} + α + 3 = 0 −327  \frac{101}{99}  < 0.9 (11, α − 5) ]\frac{101}{99}, ∞[
α^{3} + 3α^{2} + 6α + 1 = 0 −351  1  \frac{9}{11}  (11, α − 1) ]11, ∞[

Let K be the field generated by a root α of the polynomial x^{3} + 3x^{2} + 6x + 1, and let f = f_{𝔭,c} be the weighted norm for the prime ideal 𝔭 = (11, α − 1). I cannot determine the Euclidean minimum M_{1}(K) of 𝔒_{K} with respect to f for all values c ∈ w(𝔭), but I know that M_{f}(K) = \frac{187}{189} for all c ≥ \frac{189}{8}. This minimum is attained mod 𝔒_{K} at the points

P = ±\frac{1}{21}(10 + 6α + 6α^{2}), ±\frac{1}{21}(12 + 3α + 10α^{2}), ±\frac{1}{21}(15 + 16α + 9α^{2}).

On the other hand, M_{f}(K) = \frac{11}{c} for all real c in the interval [11, \frac{189}{17}[, and this minimum is attained at the points P = ±(5 + 2α + 6α^{2})/11 mod 𝔒_{K}.

II. Totally real cubic number fields.

Remak (1923) proved Minkowski’s conjecture for the cubic case, i.e.

(4.3) M(\overline{K}) ≤ \frac{1}{8} \sqrt{disc K} for totally real cubic fields.

This implies in particular that the cubic number field with disc K = 49 is norm-Euclidean. Some minima M(K) have been computed by Davenport (1947) (disc K = 49, 81), Clarke (1951) (disc K = 148), Samet (1954) (for an infinite class of fields whose discriminants are ”big enough”), Smith (1971), and Lemmermeyer (1989). Clark (1993) independently has shown some fields to be norm-Euclidean.

A. Cyclic fields.

Heilbronn (1950) proved that the number of norm-Euclidean cyclic cubic fields is finite, but could give no bound for the discriminants of such fields. Smith (1969) examined the cyclic cubic fields with discriminant < 10^{8} and found that

- the fields with conductors 𝔣 = 7, 9, 13, 19, 31, 37, 43, 61, 67 are Euclidean with respect to the norm;

- the fields with conductors 𝔣 = 73, 79, 97, 139, 151, and 163 < 𝔣 < 10^{4} are not norm-Euclidean.

Since fields with class number 1 have conductors which are prime powers, this left only the fields with conductors 𝔣 = 103, 109, 127, 157 undecided; these were shown to be Euclidean by Godwin and Smith (1993). In the meantime, Lemmermeyer (1989) had found that there are no norm-Euclidean fields with conductors 10^{4} < 𝔣 < 5·10^{5}.

B. Non-cyclic totally real fields.

Heilbronn (1950) has conjectured that there are infinitely many norm-Euclidean fields of this type. The numerical results obtained so far are in favour of Heilbronn’s conjecture, and in fact most of the fields with discriminants disc K < 4600 are norm-Euclidean.

The following table gives the number E of totally real cubic fields (cyclic and non-cyclic) that are known to be norm-Euclidean:

disc k  E  N  U  Σ
0 < d ≤ 1000  26  1  0  27
1000 < d ≤ 2000  29  5  0  34
2000 < d ≤ 3000  31  4  0  35
3000 < d ≤ 4000  36  6  0  42
4000 < d ≤ 5000  15  7  13  35
Σ  137  23  13  173

Explicit information on the real cubic fields with disc K < 2600 is given at the end of this article.

Euclidean real cubic fields with disc K > 2600:

\begin{matrix}2636, & 2673, & 2677, & 2700, & 2708, & 2713, & 2804, & 2808, & 2917, & 2920, \\ 2941, & 2981, & 2993, & 3021, & 3028, & 3124, & 3132, & 3137, & 3144, & 3173, \\ 3221, & 3229, & 3252, & 3261, & 3281, & 3316, & 3325, & 3356, & 3368, & 3496, \\ 3508, & 3540, & 3569, & 3576, & 3580, & 3592, & 3596, & 3604, & 3624, & 3721, \\ 3732, & 3736, & 3753, & 3873, & 3877, & 3892, & 3941, & 3957, & 3973, & 4001, \\ 4065, & 4104, & 4281, & 4344, & 4364, & 4409, & 4481, & 4489, & 4493, & 4596, \\ 4597, & 4628, & 4641, & 4649, & 5081, & 5685, & 10609, & 11881, & 16129, & 24649; \end{matrix}

Non-Euclidean real cubic fields with disc K > 2600 :

\begin{matrix}2777, & 2836, & 2857, & 3305, & 3889, & 3969, & 3969, & 3981, & 3988, & 4193, \\ 4212, & 4312, & 4345, & 4360, & 4684, & 4729, & 5684, & 7537, & 11417; \end{matrix}

(there are two fields with disc K = 3969, both have class number 3)

Discriminants of real cubic fields whose Euclidean nature is unknown:

4692, 4749, 4764, 4765, 4825, …

5. Quartic number fields

I. Totally complex quartic fields.

Cassels (1952) proved that the number of norm-Euclidean totally complex quartic fields is finite and gave a bound for the discriminants of such fields; his computation of the bound, however, was shown to contain a mistake by van der Linden (1984).

(5.1) If K is a totally complex quartic field and d = disc K, then M(K) > C · \sqrt{d} for some constant C > 0. The best known C gives disc K < 230 202 117 for Euclidean fields.

There exist slightly better bounds for quadratic extensions of imaginary quadratic fields given by van der Linden ((1984), 10.2), who used them to find all totally complex cyclic quartic fields that are norm-Euclidean:

(5.2) The only norm-Euclidean totally complex cyclic quartic fields are ℚ(ζ_{5}) and the quartic subfield of ℚ(ζ_{13}), where ζ_{m} denotes a primitive m-th root of unity.

Let D(m, n) denote the ring of integers in ℚ(\sqrt{m}, \sqrt{n}); the norm-Euclidean rings D(−m, n), m > 0, have been determined by Lemmermeyer (1989):

(5.3) The following list of norm-Euclidean rings D(−m, n) with m > 0 is complete:

\begin{matrix}m = 1, & n = & 2, 3, 5, 7; & m = 3, & n = & 2, 5, −7, −11, 17, −19; \\ m = 2, & n = & −3, 5; & m = 7, & n = & 5. \end{matrix}

Eisenstein (1850) established the Euclidean algorithm in D(−1, 2) and D(−1, 3) (these are the rings of integers in ℚ(ζ_{8}) and ℚ(ζ_{12}), respectively); other proofs were given later by Masley (1972, 1975), and Lakein (1972) showed that D(−m, n) is norm-Euclidean for all the values (m, n) above except (2, 5), (3, 17), (3, −19), and (7, 5). Sauvageot (1973) showed that certain rings D(m, n) are not norm-Euclidean, for example D(−1, n) with n ≥ 15. The proof of (5.3) is an extension (and correction) of her arguments; surprisingly, it is far less difficult than the proof of the corresponding result for real quadratic fields.

(5.4) Suppose that m > 0 is no square and 4th-power free; then ℚ(\sqrt[4]{−m}) is norm-Euclidean if and only if m = 2, 3, 7, 12.

This is largely due to Cioffari (1979), who showed that if K is Euclidean then m = 2, 3, 7, 12, 44, 67, or 2p^{2} for prime p; moreover he showed that ℚ(\sqrt[4]{−m}) is norm-Euclidean for m = 2, 3, 7. The proof of (5.4) was completed by Lemmermeyer (1989).

Apart from (5.1) - (5.4), there are only partial results on the Euclidean nature of complex quartic fields:

(5.5) (Lemmermeyer (1989,1994)) Assume that K is a norm-Euclidean complex

quartic field;

i) if K contains k = ℚ(\sqrt{2}), then K is one of the fields k(\sqrt{−1}), k(\sqrt{−3}), k(\sqrt{−5 − 2\sqrt{2}} );

ii) if K contains a real quadratic number field and 2 is totally ramified

in K, then K = ℚ(ζ_{8}) = ℚ(\sqrt{2}, \sqrt{−1}); iii) if K contains a real quadratic number field and 2 is the square of a prime ideal in K, then K is one of the fields ℚ(ζ_{12}), ℚ(\sqrt{−3}, \sqrt{2}), ℚ(\sqrt{−3}, \sqrt{−2}), ℚ(\sqrt{5}, \sqrt{−2});

iv) if K = ℚ(i, \sqrt{a + bi} with i^{2} = −1 and a + bi ≡ ±1 + 2i mod 4, then

a + bi = ±1 + 2i, ±3 + 2i, ±5 + 2i, ±1 + 6i, ±7 + 2i. All the fields given above are norm-Euclidean.

Best upper bounds on M(\overline{K}) seem to depend on the existence of a quadratic subfield of K; Davenport and Swinnerton-Dyer (1955) found

(5.6) Suppose that K is a totally complex quartic field which does not contain a real quadratic subfield. Then M(\overline{K}) < C · d^{3/4}.

They also claimed that the exponent 3/4 is best possible. For fields K that have real quadratic subfields, the best possible bound on M(\overline{K}) is \frac{1}{32} \sqrt{d}, as can be deduced from

(5.7) Let n ≥ 1 be odd, and put m = n^{2} + 1; then R = ℤ[i, \sqrt{m}, \frac{1}{2}(\sqrt{m} + \sqrt{−m})] has Euclidean minimum M = \frac{m}{4}, and M is attained exactly at the points congruent to \frac{1}{2}(1 + i + \sqrt{m}) mod 𝔒_{K}. If m is squarefree, we find R = 𝔒_{K}, disc K = (8m)^{2}, and M(\overline{K}) = M(K) = \frac{1}{32} \sqrt{d}.

I do not know a family of totally complex quartic fields such that M(K) is asymptotically equal to C · d^{3/4}.

There are 52 fields known to be norm-Euclidean; their discriminants are

117, 125, 144, 189, 225, 229, 256, 272, 320, 333,
392, 400, 432, 441, 512, 513, 549, 576_{1}, 576_{2}, 656,
657, 784, 832, 837, 873, 981, 1008_{1}, 1008_{2}, 1040_{1}, 1040_{2},
1088_{1}, 1089, 1161, 1168, 1197_{1}, 1197_{2}, 1225, 1372, 1424, 1552,
1600, 1728, 1808, 1856, 2048_{1}, 2192, 2197, 2304_{1}, 2368, 2601,
3249, 3392,

where the discriminants with an index correspond to the following fields:

disc K = 576_{1} :  ℚ(\sqrt{−3}, \sqrt{−2});
disc K = 576_{2} :  ℚ(\sqrt{−3}, \sqrt{2});
disc K = 1008_{1} : ℚ(\sqrt{−3}, \sqrt{2 − \sqrt{−3}});
disc K = 1008_{2} : ℚ(\sqrt{−3}, \sqrt{−2 + \sqrt{−3}});
disc K = 1040_{1} :  ℚ(i, \sqrt{−7 + 4i});
disc K = 1040_{2} :  ℚ(i, \sqrt{1 + 8i});
disc K = 1088_{1} : ℚ(\sqrt{2}, \sqrt{−5 − 2\sqrt{2}});
disc K = 1197_{1} : ℚ(\sqrt{−3}, \sqrt{−5 − 6\sqrt{−3}});
disc K = 1197_{2} : ℚ(\sqrt{−3}, \sqrt{11 + 2\sqrt{−3}});
disc K = 2048_{1} :  ℚ(\sqrt[4]{−2} );
disc K = 2304_{1} :  ℚ(\sqrt{−2}, \sqrt{3}).

II. Quartic fields with unit rank 2.

Our ignorance here is almost complete; we know some examples of fields which are norm-Euclidean, and some fields which are not:

(5.8) There are only finitely many norm-Euclidean fields ℚ(\sqrt[4]{m}).

Egami (1979) proved (5.8) for all m ≠ 2p^{2} using estimates from analytic number theory; Lemmermeyer (1989) gave an elementary proof using the technique of Behrbohm and Redei (1936) and showed that in fact

m = 2, 3, 5, 7, 12, 13, 20, 28, 52, 61, 116, 436, if ℚ(\sqrt[4]{m}) is norm-Euclidean. It should not be too hard to complete the classification of norm-Euclidean pure quartic fields. The fields ℚ(\sqrt[4]{2}) and ℚ(\sqrt[4]{5}) with discriminant −2048 and −2000, respectively, have been shown to be norm-Euclidean with the help of a computer.

The following theorem is due to Davenport and Swinnerton-Dyer, who also claim that the exponent 2/3 is best possible:

(5.9) M(K) < C · |d|^{2/3} for quartic fields with unit rank 2.

Most quartic fields with mixed signature that are known to be Euclidean have been found by Lenstra (1974, 1977) using the method described in Sect. 7 below; in his dissertation, G. Kacerovsky (1977) contributed the five quadratic extensions of ℚ(\sqrt{2}) with smallest discriminants, and together with the two pure quartic fields discussed above, this gives the list

\begin{aligned}−disc K = & 275, & 283, & 331, & 400, & 448, & 475, & 491, & 507, & 563, \\ & 643, & 775, & 1024, & 1472, & 1792, & 1984, & 2000, & 2048 \end{aligned}

of discriminants of Euclidean quartic fields with mixed signature. A computer search would certainly increase the number of Euclidean fields in this class. The minimal discriminants missing from this list are

\begin{aligned}−disc K = & 688, & 731, & 751, & 848, & 976, & 1099, \\ & 1197, & 1156, & 1192, & 1255, & 1323, & ... \end{aligned}

III. Totally real quartic fields.

Almost no negative results are known; using the method of Heilbronn (1950), Egami (1984) has shown that there are some classes of cyclic fields which are not norm-Euclidean. A few more examples can be found in Clark’s thesis, e.g. the bicyclic field ℚ(\sqrt{14}, \sqrt{22} ).

Known examples of Euclidean fields are the 17 fields with discriminants

\begin{matrix}725, & 1125, & 1600, & 1957, & 2000, & 2048, & 2225, & 2304, & 2525, \\ 2624, & 2777, & 3600, & 4205, & 4225, & 7056, & 7168, & 7225. \end{matrix}

These fields were found by Godwin (1965b), Kacerovsky (1977), Cohn and Deutsch (1986), Lemmermeyer (1989), and Niklasch and Quème (1991).

6. Cyclotomic fields

It is known that the rings ℤ[ζ_{m}] (m ≢ 2 mod 4) have class number 1 if and only if

\begin{matrix}m = 1, & 3, & 4, & 5, & 7, & 8, & 9, & 11, & 12, & 13, & 15, & 16, & 17, & 19, & 20, \\ 21, & 24, & 25, & 27, & 28, & 32, & 33, & 35, & 36, & 40, & 44, & 45, & 48, & 60, & 84; \end{matrix}

among these rings, the following are known to be norm-Euclidean:

m = 1, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 20, 21, 24,

and Lenstra (1974) has shown that K = ℚ(ζ_{32}) is not norm-Euclidean; his proof actually shows that M(K) ≥ \frac{97}{64}. There are only a few Euclidean minima known so far:

\begin{matrix}m & 1 & 3 & 4 & 8 & 12 \\ M(K) & \frac{1}{2} & \frac{1}{3} & \frac{1}{2} & \frac{1}{2} & \frac{1}{4} \end{matrix}

If we define Λ(K) = min{N𝔞 : 𝔞 is an integral ideal ≠ (0), 𝔒_{K}}, then we have M(K) = Λ(K)^{−1} in all these cases (of course we always have M(K) ≥ Λ(K)^{−1}).

A masterful exposition of the interesting history of the Euclidean algorithm in cyclotomic fields can be found in Lenstra (1979b); the names of the many mathematicians involved are displayed in the following table:

(K : ℚ) m
1  1  Euclid (ca. 300 B.C.)
2  3  Gauss, Wantzel (1847, 1848)
4  Gauss (1801), Dirichlet (1844)
4 5 Kummer (1844), Cauchy (1847), Ouspensky (1909),

Branchini (1923), Chella (1924), Landau (1927), Lenstra (1975)

8  Eisenstein (1850), Cauchy (1847), Chella (1924),

Lakein (1972), Masley (1975), Lenstra (1975)

12  Eisenstein (1850), Cauchy (1847), Chella (1924),

Lakein (1972), Masley (1975), Lenstra (1975)

6 7 Kummer (1844), Cauchy (1847), Chella (1924), Lenstra (1975)
9  Cauchy (1847), Chella (1924), Lenstra (1975)
8 15 Cauchy (1847), Lenstra (1975)
16  Ojala (1977)
20  Lenstra (1975)
24  Lenstra (1978)
10  11  Lenstra (1975)
12  13  McKenzie (1988)

It was known for a long time that only a finite number of complex subfields of cyclotomic fields have class number 1, and recently they have been determined (K. Yamamura, The determination of the imaginary abelian number fields with class number one; Math. Comp. 62 (1994), 899–921; there are exactly 172 such fields. The Euclidean fields among them are known for (K : ℚ) = 2, 4.

7. Lenstra’s method

In 1974, Lenstra discovered that a modification of an idea originally due to Hurwitz (1895a,b, 1919) yields a new method to find Euclidean number fields K of high degree (5 ≤ (K : ℚ) ≤ 10): he called a sequence ω_{1}, ω_{2}, …, ω_{m} an exceptional sequence of length m in K if the differences ω_{i} − ω_{j}, i ≠ j, are units in 𝔒_{K}.

Let r (resp. 2s) denote the number of real (resp. non-real) embeddings of K in ℂ, and let d = |disc K|. Then Lenstra was able to prove

(7.1) There exist constants α_{r,s} > 0 with the following property: if K contains an exceptional sequence of length m > α_{r,s}\sqrt{d}, then K is norm-Euclidean.

Lenstra showed that the ”Minkowski bounds”

α_{r,s} = \frac{n!}{n^{n}} (\frac{4}{π} )^{s} , π = 3.14159 …, n = (k : ℚ) = r + 2s,

were good enough to find many new Euclidean fields, and that, for most of the values r, s, the bounds of Rogers are even better. For totally real fields, the α_{r,s} given by Lenstra have been sharpened by Niklasch and Quème (1991).

For a given number field K, the length of exceptional sequences is bounded: if ω_{1}, ω_{2}, …, ω_{m} is an exceptional sequence of maximal length in K, then λ(K) = m is called Lenstra’s constant. If Λ(K) denotes the minimal norm of an integral ideal ≠ (0), (1) in 𝔒_{K}, then it is easily seen that λ(K) ≤ Λ(K). Note the analogy M(K) ≥ Λ(K)^{−1}; computations have confirmed that both inequalities tend to be equalities for fields with very small discriminants. Moreover, we know the values of λ(K) and Λ(K) for cyclotomic fields K = ℚ(ζ_{p}) of prime conductor: the decomposition law for abelian extensions of ℚ shows that Λ(K) = p. Lenstra (1974, 1977) found that in fact λ(K) = Λ(K):

(7.2) Let p be prime, ζ = ζ_{p} a primitive p-th root of unity, and K = ℚ(ζ). Then the sequence

ω_{j} = \frac{ζ^{j} − 1}{ζ − 1}, 1 ≤ j ≤ p,

shows that λ(K) = Λ(K) = p.

The analogous question for the maximal real subfields k = ℚ(ζ + ζ^{−1}) of ℚ(ζ) is not yet completely settled: here Λ(k) = p unless p ≥ 5 is a Fermat prime (p = 2^{2^{n}} + 1), where Λ(k) = p − 1. Lenstra (1977) could show that λ(k) ≥ \frac{p+1}{2}, and Leutbecher and Niklasch (1989) improved this to λ(k) ≥ p − 1. For all p ≤ 17 it is known that λ(k) = Λ(k), but the general case is still open.

Exceptional sequences have been studied in Lenstra (1974, 1977a), Mestre (1981), Leutbecher and Martinet (1981, 1981/82) (these two articles contain particularly many open problems), Leutbecher (1985, 1986), Niklasch (1986), Leutbecher and Niklasch (1989), and Niklasch and Quème (1991).

Lenstra’s theorem was generalized by Lemmermeyer (1989): call ω_{1}, ω_{2}, …, ω_{m} a k-exceptional sequence of length m if ω_{i} − ω_{j} is a nonzero element of the Motzkin set E_{k} for all 1 ≤ i < j ≤ m. Then the following theorem gives a device to discover k-stage norm-Euclidean number fields:

(7.3) If K contains a k-exceptional sequence of length m ≥ α_{r,s}\sqrt{d}, for the same constants α_{r,s} as in (7.1), then K is k-stage norm-Euclidean.

As a corollary of (7.3), we conclude that every Euclidean number field is also k-stage norm-Euclidean for a suitable k ≥ 1: choose any sequence ω_{1}, ω_{2}, …, ω_{m} in 𝔒_{K} such that m ≥ α_{r,s}\sqrt{d}; since R = 𝔒_{K} is Euclidean, we have R = E_{∞}(R) by Motzkin. Therefore, the ω_{i} − ω_{j}, 1 ≤ i < j ≤ m, are non-zero elements of E_{k} for some k ≥ 1, and R is k-stage Euclidean with respect to the norm.

It is not known if the length of exceptional k-sequences is finite for k ≥ 3.

Another generalization of (7.1) is due to Blöhmer (1989); he considered sequences ω_{1}, ω_{2}, …, ω_{m} in 𝔒_{K} such that the N(ω_{i} − ω_{j}) are ±1 or prime and showed that 𝔒_{K} is principal if m ≥ α_{r,s}\sqrt{d}.

8. Number fields of degree ≥ 5

Most of the norm-Euclidean number fields of degree ≥ 5 have been found with Lenstra’s method; exceptions are the quintic fields discovered by Godwin (1965b) and Schroeppel (1993), and some cyclotomic fields (cf. Sect. 6). Their discriminants and generating polynomials can be found in the papers of Lenstra, Leutbecher, Martinet, Mestre, Niklasch, and Quème cited in Sect. 7.

We conclude our survey with the now traditional

Table of all known norm-Euclidean number fields (March 1994).

r+s ^{n}  1 2  3 4 5 6 7  8 9 10 11 12 Σ
1  1 5  6
2  16 57 52  125
3  143 17 14 28  202
4  17 10 37 39 45  148
5  3 12 26 65 92 50  248
6  7 3  3 0 0 0 1 14
Σ  1 21 200 86 27 84 68 113 92 50 0 1 743

Similar tables can be found in Lenstra (1977), Leutbecher (1985), Leutbecher and Niklasch (1989).

Moreover, the following fields are known to be Euclidean with respect to a weighted norm:

(K : ℚ)  K  disc K  𝔭  w(𝔭)
2  α^{2} − 69 = 0  69 (23, α)  ]25, ∞[
3  α^{3} + 4α^{2} + α + 1 = 0 −199 (7, α − 1) ]7, ∞[
3  α^{3} − 2α^{2} + α + 3 = 0 −327 (11, α − 5) ]\frac{101}{99}, ∞[
3  α^{3} + 3α^{2} + 6α + 1 = 0 −351 (11, α − 1) ]11, ∞[
3  α^{3} − α^{2} − 10α + 13 = 0 1929 (7, α + 3) ]7, ∞[

As we have mentioned in Sect. 1, Clark has found a lot of totally real cubic and quartic number fields which are Euclidean with respect to functions different from the norm, for example the quartic field ℚ(\sqrt{14}, \sqrt{22} ) (see Clark and Murty, 1994).

Acknowledgement.

I would like to thank Prof. Sigrid Böge for her support and Prof. Michel Olivier for providing a table of complex cubic fields; I am also deeply indebted to Gerhard Niklasch and David Clark for having read preliminary drafts of this survey and for having corrected several mistakes.

The following table gives the minima M_{1}(K) for all real quadratic number fields ℚ(\sqrt{m}), m ≤ 102:

m  M_{1}  m  M_{1}  m  M_{1}
5  1/4  2  1/2  47  253/94
13  1/3  3  1/2  51  287/102
17  1/2  6  3/4  55  9/4
21  5/7  7  9/14  58  3/2
29  4/5  10  3/2  59  125/59
33  29/44  11  19/22  62  13/4
37  3/4  14  5/4  66  15/4
41  23/32  15  3/2  67  341/162
53  9/7  19  170/171  70  891/500
57  14/19  22  27/22  71  7393/3479
61  1611/1525  23  77/46  74  5/2
65  1  26  5/2  78  7/2
69  25/23  30  3/2  79  585/158
73  1541/2136  31  45/31  82  9/2
77  19/11  34  9/4  83  631/166
85  16/9  35  5/2  86  10030/5203
89 1004287/1000004  38  11/4  87  169/58
93  44/31  39  5/2  91  5/2
97 33679354/31404817  42  7/4  94 4708623/2143294
101  5/4  43 11829/6962  95  7/2
46 79877/48668  102  19/4

To the best of my knowledge, there are no minima known for fields beyond this limit, except for some sequences of fields like ℚ(\sqrt{m}), m = n^{2}±r, r|4 etc. (compare 3.3).

This is what we know about minima for the 2-stage algorithm:

m  M^{2}(K)  B_{1}  B_{2} = B_{∞}  Eucl. depth
6  1/4  ∅  ∅  1
10  1  \{(0, \frac{1}{2})\}  \{(0, \frac{1}{2})\}  1
14  1/4  \{(\frac{1}{2}, \frac{1}{2})\}  ∅  2
15  1  ?  \{(\frac{1}{2}, \frac{1}{2})\}  2
26  1  ?  \{(0, \frac{1}{2})\}  2
30  3/2  ?  \{(0, \frac{1}{2})\}  2
34  1  ?  \{(±\frac{1}{3}, ±\frac{1}{3})\}  2
35  7/5  ?  \{(0, ±\frac{2}{5}), (\frac{1}{2}, \frac{1}{2})\}  2
39  5/2  ?  \{(\frac{1}{2}, \frac{1}{2})\}  2
65  1  \{(\frac{1}{4}, ±\frac{1}{4})\}  \{(\frac{1}{4}, ±\frac{1}{4})\}  1
85  1  ?  \{(±\frac{1}{6}, ±\frac{1}{6})\}  2

Only the classes mod 𝔒_{K} of the sets B_{1} and B_{2} = B_{∞} are given.

22 FRANZ LEMMERMEYER

The table below gives the known Euclidean minima for complex cubic number fields with |disc K| ≤ 1000:

d_{K}  M(K)  d_{K}  M(K)  d_{K}  M(K)
−23 E 1/5  −364 N  9/8  −687 E  937/945
−31 E 1/3  −367 N  1  −695 N  25/13
−44 E 1/2  −379 E  397/648  −696 E  ≥ 186/199
−59 E 1/2  −411 E  17/22  −707 N  271/270
−76 E 1/2  −419 E  ≥ 4/5  −716 N  121/109
−83 E 1/2  −424 E  19/27  −728 E  < 0.99
−87 E 1/3  −431 E  43/64  −731 H  2
−104 E 1/2  −436 N  79/78  −743 N  1
−107 E 1/2  −439 N  17/15  −744 E  992/999
−108 E 1/2  −440 E 737/1090  −748 N  62/51
−116 E 1/2  −451 E  41/48  −751 H  25/9
−135 E 3/5  −459 N  9/8  −755 N  1
−139 E 1/2  −460 E  43/50  −755 N  1
−139 E 1/2  −460 E  43/50  −756 N  306/293
−140 E 1/2  −472 E  46/61  −759 N  11/8
−152 E 1/2  −484 E  59/76  −771 E  ≥ 223/252
−172 E 3/4  −491 H  2  −780 N  499/498
−175 E 3/5  −492 E  25/32  −804 N  ≥ 114/113
−199 N  1  −499 E  23/27  −808 N ≥ 2031/1964
−200 E 1/2  −503 E ≥ 307/544  −812 N  44/31
−204 E 61/116  −515 E  4/5  −815 E 24543/25325
−211 E 59/106  −516 E  ≥ 36/53  −823 N  37/25
−212 E 5/8  −519 E 44712/45747  −835 N 110353/106265
−216 E 1/2  −524 N  5/4  −839 N  ≥ 8/7
−231 E 7/9  −527 N  13/7  −843 N  134/131
−239 E 8/9  −543 E ≥ 7593/8343  −856
−243 E 11/18  −547 N  9/8  −863 N  29/11
−244 E 1/2  −563 H  2  −867 N  1115/1028
−247 E 5/7  −567 N  25/17  −876  < 1.06
−255 E 13/15  −588 H  5/2  −883 N  49/47
−268 E 13/22  −620 N  13/8  −888
−283 H 3/2  −628 E  625/664  −891 H  7/2
−300 E 23/30  −643 H  25/16  −907 N  ≥ 113/108
−307 N 9/8  −648 H  5/4  −908 N
−324 E 23/36  −652 E  21/23  −931 H  7/2
−327 N 101/99  −655 N  −932 N  ≥ 136/125
−331 H 3/2  −671 N  25/19  −940 N
−335 N  1  −675 N  9/8  −948 N
−339 N  1  −676 H  7/4  −959 N  19/7
−351 N  1  −679 N  9/8  −964
−356 E 7/8  −680 N  (∗)  −971

(*) The Euclidean minimum M(K) for the field with disc K = −680 is

M(K) = \frac{81956632}{81182612}.

In this table as well as in the one below, E means that the corresponding field is Euclidean (more exactly: that M(K) < 0.999), N indicates that it is not norm-Euclidean although it has class number 1, and H that the field has class number > 1. Instead of upper bounds on M(K) we have sometimes given lower bounds, especially in those cases where we conjecture them to be exact without being able to prove this.

Euclidean Minima of totally real cubic number fields with d_{K} = disc K < 2600

d_{K}  M(K)  d_{K}  M(K)  d_{K}  M(K)
49 E 1/7  1129 E < 0.49  1957 H  2
81 E 1/3  1229 E 16/29  2021 E < 0.7
148 E 1/2  1257 E < 0.42  2024 E < 0.79
169 E 5/13  1300 E 7/10  2057 E 9/11
229 E 1/2  1304 E 1/2  2089 E 1/2
257 E 1/3  1345 N 7/5  2101 E < 0.79
316 E 1/2  1369 E 31/37  2177 E
321 E 1/3  1373 E 1/2  2213 E < 0.79
361 E 8/19  1384 E 11/16  2228 E < 0.79
404 E 1/2  1396 E 1/2  2233 E
469 E 1/2  1425 E 13/15  2241 E
473 E 1/3  1436 E 1/2  2292 E
564 E 1/2  1489 E 29/43  2296 E
568 E 1/2  1492 E 1/2  2300 E
621 E 1/2  1509 E 1/2  2349 E
697 E 13/31  1524 E 1/2  2429 E
733 E 1/2  1556 E 3/4  2505 E
756 E 1/2  1573 E 19/22  2557 E
761 E 1/3  1593 E < 0.5  2589 E
785 E 3/5  1620 E 1/2  2597 H 5/2
788 E 1/2  1708 E 1/2
837 E 1/2  1765 E 13/20
892 E 1/2  1772 E
940 E 1/2  1825 N 7/5
961 E 16/31  1849 E 22/43
985 N  1  1901 E < 0.6
993 E 31/63  1929 N  1
1016 E 1/2  1937 N  1
1076 E 1/2  1940 E 1/2
1101 E 1/2  1944 E < 0.7

References

[1] R. P. Bambah, Cambridge University Thesis, 1950.

[2] , Nonhomogeneous binary quadratic forms I, Acta Math. 86 (1951), 1–29.

[3] , Nonhomogeneous binary quadratic forms II, Acta Math. 86 (1951), 31–56.

[4] E.S. Barnes, Note on non-homogeneous linear forms, Proc. Cambridge Phil. Soc. 49 (1953), 360–362.

[5] , The inhomogeneous minima of binary quadratic forms IV, Acta Math. 92 (1954), 235–264.

[6] , H.P.F. Swinnerton-Dyer, The inhomogeneous minima of binary quadratic forms I, Acta Math. 87 (1952), 259–323.

[7] , _{——}, The inhomogeneous minima of binary quadratic forms II, Acta Math. 88 (1952), 279–316.

[8] , _{——}, The inhomogeneous minima of binary quadratic forms III, Acta Math. 92 (1954), 199-234.

[9] E. Bedocchi, L’anneau ℤ(\sqrt{14} ) et l’algorithme Euclidien, Manuscripta math. 53 (1985), 199–216.

[10] , On the second minimum of a quadratic form and its applications, Riv. Mat. Univ. Parma (4) 15 (1989), 175–190. (Ital.)

[11] H. Behrbohm, L. Redei, Der Euklidische Algorithmus in quadratischen Zahlkörpern, J. Reine Angew. Math. 174 (1936), 192–205.

[12] E. Berg, Über die Existenz eines Euklidischen Algorithmus in quadratischen Zahlkörpern, Kungl. Fysiogr. Saellsk. i Lund Förh. 5 (1935), 53–58.

[13] D. Berend, W. Moran, The inhomogeneous minimum of binary quadratic forms, Math. Proc. Camb. Phil. Soc. 112 (1992), 7–19.

[14] G. B. Birkhoff, Note on certain quadratic number systems for which factorization is unique, Amer. Math. Monthly 13 (1906), 156–159.

[14] J. Blöhmer, Euklidische Ringe, Diplomarbeit TU Berlin, 1989.

[15] B. Bougaut, Anneaux quasi-euclidiens, Thèse, Université de Poitiers, 1976.

[16] , Algorithme explicite pour la recherche du P.G.C.D. dans certains anneaux principaux d’entiers de corps de nombres, Theoret. Comput. Sci. 11 (1980,), 207–220.

[17] G. Branchini, Algoritmo del massimo comun divisore nel corpo delle radici quinte dell’unita, Atti della Reale Accademia dei Lincei, Roma (5) 32-1 (1923), 68–72.

[18] A. Brauer, On the non-existence of the Euclidean algorithm in certain quadratic number fields, Amer. J. Math. 62 (1940), 697–716.

[19] H. H. Brungs, Left Euclidean rings, Pacific J. Math. 45 (1973), 27–33.

[20] E. Cahen, Sur une note de M. Fontene relative aux entiers algebriques de la forme x+y\sqrt{−5}, Nouv. ann. math. (4) 3 (1903), 444–447.

[21] O. A. Campoli, A principal ideal domain that is not a Euclidean domain, American Math. Monthly 95 (1988), 868–871.

[22] J. W. S. Cassels, The lattice properties of asymmetric hyperbolic regions I, Proc. Cambridge Phil. Soc. 44 (1948), 1–7.

[23] , The lattice properties of asymmetric hyperbolic regions II, Proc. Cambridge Phil. Soc. 44 (1948), 145–154.

[24] , The lattice properties of asymmetric hyperbolic regions III, Proc. Cambridge Phil. Soc. 44 (1948), 457–462.

[25] , The inhomogeneous minima of binary quadratic, ternary cubic, and quaternary quartic forms, Proc. Cambridge Phil. Soc. 48, (1952), 519–520 (Corr.: F.J. van der Linden 1983).

[26] , Yet another proof of Minkowski’s theorem on the product of two inhomogeneous linear forms, Proc. Cambridge Phil. Soc. 49 (1953), 365–366.

[27] M. A. Cauchy, Memoire sur de nouvelles formules relatives a la théorie des polynomes radicaux, et sur le dernier théorème de Fermat I, Comptes rendus Paris 24 (1847), 469 ff, see also Oeuvres X, extr. no. 358, 240–254;.

[28] , Memoire sur de nouvelles formules relatives a la théorie des polynomes radicaux, et sur le dernier théorème de Fermat II, Comptes rendus Paris 24 (1847), 516 ff, see also Oeuvres X, extr. no. 359, 254–268;.

[29] I. Castro Chadid, Euclidean quadratic fields, Bol. Mat. 18 (1984), 1–3, 7–21. (Span.)

[30] H. Chatland, On the Euclidean algorithm in quadratic number fields, Bull. Amer. Math. Soc. 55 (1949), 948–953.

[31] , H. Davenport, Euclids algorithm in real quadratic fields, Canad. J. Math. 2 (1950), 289–296.

[32] T. Chella, Dimostrazione dell’essisenza di un algoritmo delle divisioni successive per alcuni corpi circolari, Annali di Matematica pura ed applicata (4) 1 (1924), 199–218.

[33] V. Cioffari, The Euclidean condition in pure cubic and complex quartic fields, Math. Comp. 33 (1979), 389–398.

[34] D. A. Clark, Ph. D. thesis, McGill University, Montreal, 1992.

[35] , A quadratic field which is Euclidean but not norm-Euclidean, Manuscripta math. 83 (1994), 327–330.

[36] , Non-Galois cubic fields which are Euclidean but not norm-Euclidean (1994) (preprint).

[37] , M. R. Murty, The Euclidean algorithm for Galois extensions (1994) (preprint).

[38] L. E. Clarke, On the product of three non-homogeneous linear forms, Proc. Cambridge Phil. Soc. 47 (1951), 260–265.

[39] , Non-homogeneous linear forms associated with algebraic fields, Quart. J. Math. (2) 2 (1951), 308–315.

[40] H. J. Claus, Über die Partialbruchzerlegung in nicht notwendig kommutativen euklidischen Ringen, J. Reine Angew. Math. 194 (1955), 88–100.

[41] H. Cohn, J. Deutsch, Use of a computer scan to prove that ℚ(\sqrt{2 + \sqrt{2}}) and ℚ(\sqrt{3 + \sqrt{2}}) are Euclidean, Math. Comp. 46 (1986), 295–299.

[42] P. M. Cohn, On a generalization of the Euclidean algorithm, Proc. Cambridge Phil. Soc. 57 (1961), 18–30.

[43] , On the structure of the GL(2) of a ring, I.H.E.S. Publ. Math. 30 (1966), 365–413.

[44] , A presentation of SL(2) for Euclidean imaginary quadratic fields, Mathematika 15 (1968), 156–163.

[45] M. J. Collison, The unique factorization theorem: from Euclid to Gauss, Math. Mag. 53 (1980), 96–100.

[46] G. Cooke, The weakening of the Euclidean property for integral domains and application to algebraic number theory I, J. Reine Angew. Math. 282 (1976), 133–156.

[47] , The weakening of the Euclidean property for integral domains and application to algebraic number theory II, J. Reine Angew. Math. 283 (1977), 71–85.

[48] , P. J. Weinberger, On the construction of division chains in algebraic number fields with application to SL(2), Comm. Algebra 2 (1975), 481–524.

[49] M. Cugiani, Osservazioni relative alla questioni dell’esistenza di un algoritmo euclidei nei campi quadratici, Boll. della Unione Math. Italiana 3 (1948), 136–141.

[50] , I campi quadratici e l’algoritmo Euclideo, Periodico di Math. 28 (1950), 52–62, 114–129.

[51] H. Davenport, On the product of three homogeneous linear forms I, J. London Math. Soc. 13 (1938), 139–145, see also Coll. Works I, 7–13.

[52] , On the product of three homogeneous linear forms II, Proc. London Math. Soc. (2) 44 (1938), 412–431, see also Coll. Works I, 14–33.

[53] , On the product of three homogeneous linear forms III, Proc. London Math. Soc. (2) 45 (1939), 98–125, see also Coll. Works I, 34–61.

[54] , Note on the product of three homogeneous linear forms, J. London Math. Soc. 16 (1941), 98–101, see also Coll. Works I, 62–65.

[55] , On the product of three homogeneous linear forms IV, Proc. Cambridge Phil. Soc. 39 (1943), 1–21, see also Coll. Works I, 66-68.

[56] , Non-homogeneous binary quadratic forms I, Proc. Ned. Akad. Wet. 49 (1946), 815–821, see also Coll. Works I, 167–173.

[57] , Non-homogeneous binary quadratic forms II, Proc. Ned. Akad. Wet. 50 (1947), 378–389, see also Coll. Works I, 174–185.

[57] , Non-homogeneous binary quadratic forms III, Proc. Ned. Akad. Wet. 50 (1947), 484–491, see also Coll. Works I, 186–193.

[58] , Non-homogeneous binary quadratic forms IV, Proc. Ned. Akad. Wet. 50 (1947), 741-749, see also Coll. Works I, 194–211.

[59] , On the product of three non-homogeneous linear forms, Proc. Cambridge Phil. Soc. 43 (1947), 137–152, see also Coll. Works I, 212–227.

[60] , Indefinite binary quadratic forms, Quart. J. Math. Oxford (2) 1 (1950), 54–62, see also Coll. Works I, 395–403.

[61] , Euclid’s algorithm in cubic fields of negative discriminant, Acta Math. 84 (1950), 159–179, see also Coll. Works I, 374–394.

[62] , Euclid’s algorithm in certain quartic fields, Trans. Amer. Math. Soc. 68 (1950), 508–532, see also Coll. Works I, 404–428.

[63] , L’algorithme d’Euclide dans certains corps algebriques, Coll. intern. du Centre de la recherche sci. XXIV 41–43 (1950) (Algebrè et theorie des nombres).

[64] , Indefinite binary quadratic forms and Euclid’s algorithm in real quadratic fields, Proc. London Math. Soc. (2) 53 (1951), 65–82, see also Coll. Works I, 344-361.

[65] , Linear forms associated with an algebraic number field, Quart. J. Math. (2) 3 (1952), 32–41, see also Coll. Works II, 552–561.

[66] , H. P. F. Swinnerton-Dyer, Products of n inhomogeneous linear forms, Proc. London Math. Soc. (3) 5 (1955), 474–499, see also Coll. Works of H. Davenport II, 566–591.

[67] H. Decoste, Des anneaux principaux non euclidiens, Ann. Sci. Math. Quebec 5 (1981), 103–114.

[68] R. Dedekind, Suppl. to L. Dirichlet, ”Vorlesungen über Zahlentheorie”.

[69] L. E. Dickson, Algebren und ihre Zahlentheorie, Zürich-Leipzig, 1927.

[70] L. Dirichlet, Vorlesungen über Zahlentheorie, Braunschweig, 1893.

[71] , Recherches sur les forms quadratiques à coèfficients et à indeterminées complexes, J. Reine Angew. Math. 24 (1842), 291–371, see also Werke I, 533–618.

[72] , Ueber die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen, J. Reine Angew. Math. 40 (1850), 209–277, see also Werke II, 27-48.

[73] D. W. Dubois, A. Steger, A note on the division algorithms in imaginary quadratic number fields, Canad. J. Math. 19 (1958), 285-286.

[74] F. J. Dyson, On the product of four non-homogeneous linear forms, Ann. Math. 49 (1948), 82–109.

[75] S. Egami, Euclid’s algorithm in pure quartic fields, Tokyo J. Math. 2 (1979), 379–385.

[76] , On finiteness of numbers of Euclidean fields in some classes of number fields, Tokyo J. Math. 7 (1984), 183–198.

[77] R. B. Eggleton, C. B. Lacampagne, J. L. Selfridge, Euclidean quadratic fields, Amer. Math. Monthly 99 (1992), 829–837.

[78] G. F. Eisenstein, Über einige allgemeine Eigenschaften der Gleichung, von welcher die Teilung der ganzen Lemniskate abhängt, nebst Anwendungen derselben auf die Zahlentheorie, J. Reine Angew. Math. 39 (1850), 224–287, see also Math. Werke II, 556–619.

[79] V. Ennola, On the first inhomogeneous minimum of indefinite binary quadratic forms and Euclid’s algorithm in real quadratic fields, Ann. Univ. Turku. Ser. A I 28 (1958 58pp).

[80] P. Erdös, Ch. Ko, Note on the Euclidean algorithm, J. London Math. Soc. 13 (1938), 3–8.

[81] A. K. Feyziglu, A very simple proof that ℤ[ \frac{1}{2} (1 + \sqrt{−19})] is a principal ideal domain, Doga Mat. 16 (1992), 62–68.

[82] C. R. Fletcher, Euclidean Rings, J. London Math. Soc. 4 (1971), 79–82.

[83] G. Fontené, Sur les entiers algébriques de la forme x + y\sqrt{−5}, Nouv. ann. math. (4) 3 (1903), 209–214.

[84] J. Fox, Ph.D. Thesis, Yale University, 1935, see also Bull. Amer. Math. Soc. 41 (1935), p. 186.

[85] C. F. Gauss, Theoria residuorum biquadraticorum II, Werke II, 1876, pp. 93–148.

[86] , Zur Theorie der komplexen Zahlen, Werke II, 1876, pp. 387–398.

[87] H. J. Godwin, On the inhomogeneous minima of certain norm-forms, J. London Math. Soc. 30 (1955), 114–119.

[88] , On a conjecture of Barnes and Swinnerton-Dyer, Proc. Cambridge Phil. Soc. 59 (1963), 519–522.

[89] , On the inhomogeneous minima of totally real cubic norm-forms, J. London Math. Soc. 40 (1965), 623–627.

[90] , On Euclid’s algorithm in some quartic and quintic fields, J. London Math. Soc. 40 (1965), 699–704.

[91] , On Euclid’s algorithm in some cubic fields with signature one, Quart. J. Math. Oxford 18 (1967), 333–338.

[92] , Computations relating to cubic fields, Computers in number theory, London, 1971, pp. 225–229.

[93] , J. R. Smith, On the Euclidean nature of four cyclic cubic fields, Math. Comp. 60 (1993), 421–423.

[94] D. S. Gorskov, On the Euclidean algorithm in real quadratic fields, Ucenye Zapisky Kazan. Univ. 101 (1941), 31–37. (Russ.)

[95] , Real quadratic fields without an Euclidean algorithm, Ucenye Zapisky Kazan. Univ. 101 (1941), 37–42. (Russ.)

[96] R.Gupta, M. Murty, V. Murty, The Euclidean algorithm for S-integers, Canad. Math. Soc. Conference Proc., vol. 7, 1987, pp. 189–201.

[97] H. Hasse, Über eindeutige Zerlegung in Primelemente oder in Primhauptideale in Integritätsbereichen, J. Reine Angew. Math. 159 (1928), 3–12.

[98] H. Heilbronn, On Euclid’s algorithm in real quadratic fields, Proc. Cambridge Phil. Soc. 34 (1938), 521–526.

[99] , On Euclid’s algorithm in cubic self-conjugate fields, Proc. Cambridge Phil. Soc. 46 (1950), 377–382.

[100] , On Euclid’s algorithm in cyclic fields, Canad. J. Math. 3 (1950), 257–286, see also The collected papers of H. Heilbronn (1988).

[101] M. D. Hendy, Euclid and the fundamental theorem of arithmetic, Hist. Math. 2 (1975), 189–191.

[102] J. J. Hiblot, Des anneaux euclidiens dont le plus petit algorithme n’est pas à valeurs finies, C.R. Acad. Sci. Paris, Sér A 281 (1975), 411–414.

[103] N. Hofreiter, Quadratische Zahlkörper ohne Euklidischen Algorithmus, Math. Ann. 110 (1935), 194-196.

[104] , Quadratische Zahlkörper mit und ohne Euklidischen Algorithmus, Monatsh. Math. Phys. 42 (1935), 397–400.

[105] L. K. Hua, On the distribution of quadratic non-residues and the Euclidean algorithm in real quadratic fields I, Trans. Amer. Math. Soc. 56 (1944), 537–546.

[106] , S.H. Min, On the distribution of quadratic non-residues and the Euclidean algorithm in real quadratic fields II, Trans. Amer. Math. Soc. 56 (1944), 547–569.

[107] L. K. Hua, W. T. Shih, On the lack of the Euclidean algorithm in R(\sqrt{61}), Amer. J. Math. 67 (1945), 209–211.

[108] A. Hurwitz, Über die Entwicklung komplexer Grössen in Kettenbrüche, Acta Math. 11 (1887), 187–200.

[109] , Letter to L. Bianchi, 24.06.1895, Opere di L. Bianchi, vol. XI, pp. 103–105.

[110] , Zur Theorie der algebraischen Zahlen, Nachrichten von der k. Gesellschaft der Wissenschaften zu Göttingen, Math. -phys. Klasse, (1895), 324–331, se also Math. Werke 2 (1932), 236–243.

[111] , Die unimodularen Substitutionen in einem algebraischen Zahlenkörper, Nachrichten von der k. Gesellschaft der Wissenschaften zu Göttingen, Math. -phys. Klasse, (1895), 332-356, se also Math. Werke 2 (1932), 244–268.

[112] , Der Euklidische Divisionssatz in einem endlichen algebraischen Zahlkörper, Math. Zeitschrift 3 (1919), 123–126;, se also Math. Werke 2 (1932), 471–474.

[113] K. Inkeri, Über den Euklidischen Algorithmus in quadratischen Zahlkörpern, Ann. Acad. Sci. Fenn. Ser. A 41 (1947), 1–35.

[114] , Neue Beweise für einige Sätze zum Euklidischen Algorithmus in quadratischen Zahlkörpern, Ann. Univ. Turku. A IX (1948), 1–15.

[115] Non-homogeneous binary quadratic forms, Den 11te Skandinaviske Matematiker Kongress Trondheim, 1949, pp. 216–224.

[116] , V. Ennola, The Minkowski constant for certain binary quadratic forms, Ann. Univ. Turku. Ser A I 25 (1957), 3–18.

[117] D. H. Johnson, C. S. Queens, A. N. Sevilla, Euclidean real quadratic number fields, Arch. Math. 44 (1985), 344–368.

[118] R. G. McKenzie, Ph.D. thesis, Michigan State University, 1988.

[119] G. Kacerovsky, Diss., Wien, 1977.

[120] W. Knorr, Problems in the interpretation of Greek number theory; Euclid and the fundamental theorem of arithmetic, Studies in Hist. and Phil. Sci. 7 (1976), 353–368.

[121] Ch. Kolb, Kap. 3 der Zulassungsarbeit, Univ. Heidelberg, 1976.

[122] G. Kumar, Quadratic Euclidean domains, Math. Ed. 26 (1992), 180–185.

[123] E. E. Kummer, Letters to L. Kronecker, 2.10.1844 and 16.10.1844, Coll. Papers I, 1975, pp. 87–92.

[124] R. B. Lakein, Euclid’s algorithm in complex quartic fields, Acta Arithm. 20 (1972), 393–400.

[125] F. Lemmermeyer, Diplomarbeit, Heidelberg, 1989.

[126] , Euklidische Fenster (manuscript).

[127] , Euclid’s algorithm in quartic CM-fields (in preparation).

[128] V. Lemmlein, On Euclidean rings and rings of principal ideals, Doklady kad. Nauk SSSR (NS) 97 (1954), 585–587.

[129] H. W. Lenstra, Lectures on Euclidean rings, Bielefeld, 1974.

[130] , Euclid’s algorithm in cyclotomic fields, Report 74-01, Dept. Math. Univ. Amsterdam (1974), 13pp.

[131] , Euclid’s algorithm in cyclotomic fields, J. London Math. Soc. 10 (1975), 457–465.

[132] , Euclid’s algorithm in cyclotomic fields, Tagungsbericht 33/75, Math. Forschungsinstitut Oberwolfach (1975).

[133] , Euclidean number fields of large degree, Invent. Math. 38 (1977), 237–254.

[134] , On Artin’s conjecture and Euclid’s algorithm in global fields, Invent. Math. 42 (1977), 201–224.

[135] , Quelques examples d’anneaux euclidiens, C.R. Acad. Sci. Paris Ser. A 289 (1978), 683–685.

[136] , Euclidean ideal classes, Asterisque 61 (1979), 121–131 (Journées Arithmetiques de Luminy).

[137] , Euclidean number fields 1, Math. Intell. 2 (1979), 6–15.

[138] , Euclidean number fields 2, Math. Intell. 2 (1980), 73-77.

[139] , Euclidean number fields 3, Math. Intell. 2 (1980), 99–103.

[140] A. Leutbecher, Euklidischer Algorithmus und die Gruppe GL(2), Math. Ann. 231 (1977/78), 269–285.

[141] , Euclidean number fields having a large Lenstra constant, Ann. Inst. Fourier 35 (1985), 83–106.

[142] , Ausnahmeeinheiten und euklidische Zahlkörper, Tagungsbericht 35/86, Math. Forschungsinstitut Oberwolfach (1986).

[143] , J. Martinet, Constante de Lenstra et corps de nombres Euclidiens, Sémin. Théorie des nombres Univ. Bordeaux exp. no 4 (1981/82).

[144] , J. Martinet, Lenstra’s constant and Euclidean number fields, Astérisque 94 (1982) (Journées Arithmetiques Metz).

[145] , G. Niklasch, On cliques of exceptional units and Lenstra’s construction of Euclidean number fields, Lecture Notes Math. 1380 (1989), 150–178 (Number Theory Ulm 1987).

[146] F. J. van der Linden, Euclidean number rings with two infinite primes, Tagungsbericht Math. Forschungsinstitut Oberwolfach 35/81 (1981).

[147] , Euclidean rings of integers of fourth degree fields, Lecture notes in Math. 1068 (1983), 139–148 (Number theory Noordwijkerhout).

[148] , Euclidean rings with two infinite primes, Ph.D. thesis, Univ. Amsterdam, 1984.

[149] , Euclidean rings with two infinite primes, CWI Tract 15, Centrum voor Wiskunde en Informatica, 1985.

[150] S. Lubelsky, Algorytm Euklidesa, Wiadom Mat. 42 (1937), 5–67.

[151] J. M. Masley, On cyclotomic fields Euclidean for the norm map, Notices Amer. Math. Soc. 19, A-813, Abstr. # 700 A-3.

[152] , On Euclidean rings of integers in cyclotomic fields, J. Reine Angew. Math. 272 (1975), 45–48.

[153] J. F. Mestre, Corps Euclidiens, unites exceptionelles et courbes elliptiques, J. Number Theory 13 (1981), 123–137.

[154] S. H. Min, On the Euclidean algorithm in real quadratic fields, J. London Math. Soc. 22 (1947), 88–90.

[155] , Euclidean algorithm in real quadratic fields, Sci. Rep. Nat. Tsing Hua Univ. Ser. A 5 (1948), 190–223.

[156] T. Motzkin, The Euclidean algorithm, Bull. Am. Math. Soc. 55 (1949), 1142–1146.

[157] M. Nagata, On Euclid algorithm, Stud. Math. 8 (1978), 175–186 (C. P. Ramanujan, A tribute).

[158] , A pairwise algorithm and its application to ℤ[\sqrt{14}], Algebraic geometry Seminar, Singapore, 1987, pp. 69–74.

[159] W. Narkiewicz, Book review ”Collected Papers of H. Heilbronn”, DMV Jahresbericht 93 (1991), 4–5.

[160] G. Niklasch, Diplomarbeit TU München, 1986.

[161] , On Clarks example of a Euclidean field which is not norm-euclidean, manuscripta math. 83 (1994), 443–446.

[162] , R. Quème, An improvement of Lenstra’s criterion for euclidean number fields: The totally real case, Acta Arith. 58 (1991), 157–168.

[163] P. Noordzij, Über das Produkt von vier reellen homogenen linearen Formen, Monatsh. Math. 71 (1967), 436–445.

[164] T. Ojala, Euclid’s algorithm in the cyclotomic fields ℚ(ζ_{16}), Math. Comp. 31 (1977), 268– 273.

[165] A. Oppenheim, Quadratic fields with and without Euclid’s algorithm, Math. Ann. 109 (1934), 349–352.

[166] H. Ostmann, Euklidische Ringe mit eindeutiger Partialbruchzerlegung, J. Reine Angew. Math. 188 (1950), 150–161.

[167] J. Ouspensky, Note sur les nombres entiers dependant d’une racine cinquième de l’unité, Math. Ann. 66 (1909), 109-112, see also Moskau Math. Samml. 26, 1–17.

[168] P. S. Papkov, Der Euklidische Algorithmus im quadratischen Zahlkörper mit beliebiger Klassenzahl (Russ., German summary), Oeuvres sci. Univ. Etat, Rostoff sur Don 1 (1934), 15–60.

[169] , Über eine Anwendung des Euklidischen Algorithmus im quadratischen Zahlkörper mit beliebiger Klassenzahl, Oeuvres sci. Univ. Etat, Rost. s, Don 1 (1934), 61–78. (Russ., German summary)

[170] O. Perron, Quadratische Zahlkörper mit Euklidischem Algorithmus, Math. Ann. 107 (1932), 489–495.

[171] G. Picavet, Caracterisation de certains types d’anneaux euclidiens, Enseignement Math. 18 (1972), 245–254.

[172] G. Pollak, On types of Euclidean norms, Acta Sci. Math. Szeged 20 (1959), 252–268. (Russ.)

[173] C. S. Queen, Arithmetic Euclidean rings, Acta Arith. 26 (1972), 105–113.

[174] L. Rédei, Über den Euklidischen Algorithmus in reellquadratischen Zahlkörpern, J. Reine Angew. Math. 183 (1941), 183–192.

[175] , Zur Frage des Euklidischen Algorithmus in quadratischen Zahlkörpern, Math. Ann. 118 (1942), 588–608.

[176] R. Remak, Über den Euklidischen Algorithmus in reell-quadratischen Zahlkörpern, Jahresber. DMV 44 (1934), 238–250.

[177] G. Renault, Gaz. Sci. Math. Quebec 1 (1977), 16–22.

[178] K. A. Rodosskij, On Euclidean rings, Sov. Math. Dokl. 22 (1980), 186–189.

[179] , The Euclidean algorithm, Moskow, 1988. (Russ.)

[180] H. Rolletschek, The Euclidean algorithm for Gaussian integers, Lecture Notes Comp. Sci. 162 (1983), 12–23 (EUROCAL’83).

[181] , Shortest division chains in imaginary quadratic number fields, J. Symbolic Comp. 9 (1990), 321–354.

[182] P. A. Samet, The product of non-homogeneous linear forms I, Proc. Cambridge Phil. Soc. 50 (1954), 372–379.

[183] , The product of non-homogeneous linear forms II, Proc. Cambridge Phil. Soc. 50 (1954), 380–390.

[184] P. Samuel, About Euclidean rings, J. Algebra 19 (1971), 282–301.

[185] J. Sauvageot, Algorithmes d’Euclide dans certains corps biquadratiques, Sém. Delange-Pisot-Poitou, exp. no 15, 3pp (1972/73).

[186] J. Schatunowsky, Der grösste gemeinschaftliche Teiler von algebraischen Zahlen zweiter Ordnung mit negativer Diskriminante und die Zerlegung dieser Zahlen in Primfaktoren, Diss. Strassburg, Leipzig 1912, 1911.

[187] R. Schroeppel, ℚ( \sqrt[5]{2}) is norm-Euclidean (unpublished).

[188] V. Schulze, Verallgemeinerte euklidische Algorithmen (1994) (preprint).

[189] L. Schuster, Reellquadratische Zahlkoerper ohne Euklidischen Algorithmus, Monatsh. Math. Phys. 47 (1938), 117–127.

[190] D. B. Shapiro, R. K. Markanda, E. Brown, Some Euclidean properties for real quadratic fields, Acta Arith. 47 (1986), 143–152.

[191] J. R. Smith, On Euclid’s algorithm in some cyclic cubic fields, J. London Math. Soc. 44 (1969), 577–582.

[192] , The inhomogeneous minima of some totally real cubic fields, Computers in number theory, London, 1971, pp. 223–224.

[193] H. M. Stark, The papers on Euclid’s algorithm, The Collected papers of H. Heilbronn, 1990, pp. 586–587.

[194] H. P. F. Swinnerton-Dyer, The inhomogeneous minima of complex cubic norm forms, Proc. Cambridge Phil. Soc. 50 (1954), 209–219.

[195] Y. Tanimura, Euclidean algorithm in quadratic fields II, Sci. Rep. Lib. Arts Ed. Gifu Univ. Natur. Sci. 3 (1964/65), 339-345.

[196] , Euclidean algorithm in quadratic fields III, Sci. Rep. Lib. Arts Ed. Gifu Univ. Natur. Sci. 4 (1967), 13–18.

[197] , Euclidean algorithm in cubic fields I, Sci. Rep. Lib. Arts Ed. Gifu Univ. Natur. Sci. 4, (1969), 135–137.

[198] , Non Euclidean point in field ℚ(\sqrt{97}), Bull. Tokai Women’s College 2 (1982), 39–44.

[199] H. Tapia-Recillos, J. Valle Can, Non-Euclidean principal ideal domains of algebraic integers, Proceedings of the XIX-th National Congress of the Mexican Math. Soc., vol. 1, 1986, pp. 231–252. (Span.)

[200] E. M. Taylor, Euclid’s algorithm in cubic fields with complex conjugates, Ph.D. thesis London, 1975.

[201] , Euclid’s algorithm in cubic fields with complex conjugates, J. London Math. Soc. 14 (1976), 49–54.

[202] J. G. Tena Ayuso, Subannillos Euclideos de cuerpos quadraticos reales, Rev. Math. Hisp.- Amer. 37 (1977), 43–50.

[203] C. Traub, Theorie der sechs einfachsten Systeme complexer Zahlen, I, II, Beilage zum Programm des Grossh. Lyceums, Mannheim, 1867/1868.

[204] P. Varnavides, Note on non-homogeneous quadratic forms, Quart. J. Math. Oxford 19 (1948), 54–58.

[205] , Non-homogeneous quadratic forms, Proc. Ned. Acad. Wet. 51 (1948), 396–404.

[206] , Euclid’s algorithm in real quadratic fields, Prakt. Math. Athenon 24 (1949), 117– 123.

[207] , On the quadratic form x^{2} − 7y^{2}, Quart. J. Math. Oxford 20 (1949), 124–128.

[208] , The Euclidean real quadratic number fields, Indag. Math. 14 (1952), 111–122.

[209] , The nonhomogeneous minima of a class of binary quadratic forms, J. Number Theory 2 (1970), 333–341.

[210] L. N. Vaserstein, On the group SL(2) for Dedekind domains of arithmetic type, Mat. Sb. 89 (131) (1972), 313–322.

[211] P. L. Wantzel, Notes sur la théorie des nombres complexes, Compt. Rendus de l’Academie des Sciences 24 (1847).

[212] , Extraits des Proces-Verbaux des Seances, Soc. Philomatique de Paris (1848), 19–22.

[213] P. J. Weinberger, On Euclidean rings of algebraic integers, Proc. Symp. Pure Math. 24 (1973), 321–332 (Analytic number theory, AMS,).

[214] J. C. Wilson, A principal ideal ring that is not a Euclidean ring, Math. Mag. 46 (1973), 34–38.

[215] K. C. Yang, Quadratic fields without Euclid’s algorithm, Sci. Rep. Nat. Tsing-Hua Univ. A 3 (1935), 261–264.

[216] T. Zaupper, A quasi-Euclidean algorithm, Bull. Appl. Math. 31, no. 210 (1983), 127–145. (Hungar.)

Erwin-Rohde-Str. 19, D–69120 Heidelberg

   E-mail address: hb3@ix.uni-heidelberg.de