# On Euclidean ideal classes

Table of Contents Dedication ii Acknowledgments iii List of Figures viii Chapter (1) Introduction 1 Motzkin's Lemma for Elements 4 A Motzkin-type Lemma for C 63 The Large Sieve for Elements and Ideals 9 (2) The Euclidean algorithm and Motzkin's Lemma 14 Harper's Lemma 21 The Large Sieve 31 The Gupta-Murty Bound 33 The Large Sieve Applied to a Variation of Harper's Lemma .... 42 (3) Euclidean Ideal Classes Euclidean ideal classes 45 A Motzkin-type Lemma for C 63 A Harper-type Lemma for C 68 Admissible Sets of Primes with Respect to C 72 A Variation of Harper's Lemma for C 84 vi

The Large Sieve for Euclidean Ideal Classes 87 Growth results 97 Index 101 Bibliography 103 vii

List of Figures (1) The Lattice (2,1 + /^ 5 ) 52 (2) Boxes and the Lattice's Fundamental Domains 52 (3) A Set within y/2 of the Lattice 53 (4) A Larger Set within y/2 of the Lattice 54 (5) An Even Larger Set within y/2 of the Lattice 54 vi n

CHAPTER 1 INTRODUCTION In abstract algebra courses, the first way a student learns to prove a ring is principal is by using the Euclidean algorithm. Usually, this is taught by using the norm function to prove that Z and Z[i], both rings of integers of number fields, are principal ideal domains. What is not usually covered is that the norm is not the only function that can be used as a Euclidean algorithm. In fact, there are some rings that are Euclidean but not norm-Euclidean, like the ring of integers of Q(A/69) ([I])- Definition 1.0.1. — Given a ring R and a well ordered set W, a map (f> : R \ 0 —> W is a Euclidean algorithm as long as, for any elements a and b in R with b ^ 0, there exist some elements q and r in R such that a = qb + r, with either 4>{r) < 4>{b) or r = 0. Just like the norm function, any function satisfying the conditions above can be used to find the greatest common divisor of two elements, l

implying principality of all ideals. An integral domain with a Euclidean algorithm is called a Euclidean domain. Number fields with norm-Euclidean rings of integers have an interest ing property. By definition, if OK is norm-Euclidean, then for any a and b in OK with 6 ^ 0, there exists some q and r in OK such that Nm(o — qb) = Nm(r) < Nm(6). If we divide through by the norm of 6, we can then see that Nm( | — q) < 1. There is therefore an equiva lent statement that given a number field K, the ring of integers of K is norm-Euclidean if and only if for every x in K, there exists some y in OK such that Nm(a; — y) < 1. Note that y is an element of OK and that 1 is the norm of OK- i n [8], Lenstra asked what would happen if OK were replaced by some non-zero ideal C. He then defined the ideal C to be Euclidean for the norm if, for all x E K, there exists some y E C such that Nm( x - y) < Nm(C). If C is Euclidean for the norm, then so is every other ideal in its ideal class, and in this case we will call the class [C] is a norm-Euclidean ideal class (see Proposition 3.1.4). Interestingly enough, the ring OK can have at most one norm-Euclidean ideal class ([8]). As before, the norm is not the only function that can be a Euclidean algorithm for an ideal. This inspired Lenstra to come up with Definition 1.0.3 below. In order to state it, though, we first need the following terminology. 2

Definition 1.0.2. — Let R be a Dedekind domain. A fractional ideal is an element in the set {\l \ b € R \ 0, / is an ideal of R}. Henceforth, unless otherwise stated, all ideals in this paper are fractional. Ideals that are properly contained in R are called integral ideals. For the rest of the paper, given a Dedekind domain R, let E be the set of fractional ideals of R that contain R itself. For example, if ^7" is in E, then b is an element of/. Definition 1.0.3. — Let R be a Dedekind domain, let C be a non-zero ideal, let W be a well-ordered set, and let 0 be a function from E to W. We say that

Going back to our original motivation, given a number field K with trivial class group, it makes sense to ask whether &% is Euclidean or not. In 1973, Weinberger ([11]) proved, modulo the generalized Riemann hypothesis, that if if is a number field with trivial class group and if 6K has infinitely many units, then the ring 6K is a Euclidean domain. This then suggests the question: when do number fields with cyclic class group have a Euclidean ideal class? Lenstra proved that if one assumes the generalized Riemann hypothesis, then for every number field with infinitely many units and cyclic class group, each generator of the class group is a Euclidean ideal class. Other than this one theorem, the author knows of no result in the literature implying that if K has a Euclidean ideal class, then it has any other Euclidean ideal classes. Both Weinberger's and Lenstra's results assume the generalized Rie mann hypothesis, so the next question to ask is whether they can be proved without assuming the Riemann hypothesis. Malcolm Harper was able to partially prove Weinberger's theorem without assuming the Rie mann hypothesis by using analytic techniques and a reformulation of the Euclidean algorithm called Motzkin's construction. 1.1. Motzkin's Lemma for Elements For the rest of this section, assume that all Euclidean algorithms are N-valued, i.e. that the well-ordered set W in the definitions above is N. Motzkin's construction for elements is useful because one can start 4

with any ring and the construction will determine whether or not it has a Euclidean algorithm without one having to find such an algorithm. Definition 1.1.1. — (Motzin's Construction for Elements) Given a do main R, let AQ := {0} U Rx, so it contains zero and all the units. Let Ai = Ai-i U < a e R Vi e R, 3y e A{_x such that x — y G (a) for i > 0, and let A := U^0 ^j. If A = R, then let us define : A —> N, where

, defined above. The only such algorithm explicitly computed in the literature is for the ring Z. No others have been computed since the publication of Motzkin's paper in 1929. This paper includes nontrivial upper bounds for the least algorithm from Z[i] to N. Harper ([5]) modified Motzkin's construction for elements so that the only elements in the construction are zero, units, and primes. Harper was then able to use analytic methods to study the growth of these sets. 5

Definition 1.1.3. — (Harper's Construction for Elements) Given a do main R, let BQ = {0} U Rx, so that B0 is the set containing zero and all the units. For i greater than zero, let Bi = i?,_i U < primes p € R \/x e R, By € A-i such that x — y € (p) and let B = U°°=QBt. He also had to use Dirichlet's theorem on primes in arithmetic pro gressions in order to prove Lemma 1.1.4 below. Lemma 1.1.4- — (Harper's Lemma for Elements) Given a number field K with trivial class group, if B contains every prime element of OK, then OK is a Euclidean domain. Note that every set Bi in the construction, for % ^ 0, is a set of primes, which lends itself to estimating its size via analytic methods and sieving techniques. Moreover, there is an intelligent way to augment B0 so that these sets grow more quickly and the lemma still holds. The aim is to say that if one of the Bi grows quickly enough, then every prime element is contained in B and therefore the ring R is Euclidean. Harper used the large sieve for number fields to construct general ma chinery that shows that if any of the B% grows quickly enough then every prime element is contained in B and therefore R is a Euclidean domain. In particular, if we define Bi(x) to be \{p : Nm(p) < x,p € Bi} | and Bi(x) » Y^T^. for some positive integer i, Harper ([5]) shows that the 6

ring R is Euclidean. This machinery is general enough that it can even be applied to the situation where B0 is augmented in the manner alluded to above. Harper then found a way to use the Gupta-Murty bound ([5]) to show that, in specific instances, he could force B\ to grow quickly. He then applied the large sieve for elements to show the associated ring was a Euclidean domain. Using the Gupta-Murty bound followed by his large sieve machinery, he was able to show that Z[\/l4] is Euclidean, even though it is not norm-Euclidean. Analogously, it makes sense to ask if Lenstra's result on Euclidean ideal classes can be proved without assuming the generalized Riemann hypothesis. A natural way to do this would be to try to adapt Harper's techniques to Euclidean ideal classes. Unfortunately, the constructions and tools he used do not apply to Euclidean ideal classes. In order to use them, they need to be reformulated for ideal classes. 1.2. A Motzkin-type Lemma for C Motzkin's construction for ideal classes yields immediate results sup porting Lenstra's theorem modulo the Riemann hypothesis. Everything in this section is new work. Definition 1.2.1. — [Motzkin's Construction for Ideals, Relative to C) If R is a Dedekind domain and C is a non-zero ideal, let A0c '•= {R}> so that it is a one element set, where the one element is the ideal R. For 7

i greater than zero, let Ac,i = A C,i -1 U< J- 1 / is an ideal contained in R and yxel^CXC, Bye C such that (x - y) _ 1/_ 1 C G -Ac,*-i and let 4 C := U£0j4iiCr. Lemma 1.2.2. — (Motzkin's Lemma for Ideal Classes) Given a Dedekind domain R and a non-zero ideal C, if every ideal in E is contained in Ac, then [C] is a Euclidean ideal class. Another variation of the construction is needed in order to apply a general machinery inspired by Harper. The new sets will consist of R and inverses of prime ideals, which lend themselves more easily to sieving techniques than generic sets of ideals that contain the entire ring. Definition 1.2.3. — (Harper's Construction for Ideals, Relative to C) If R is a Dedekind domain and C is a non-zero ideal, let B$c be {R}. For i > 0, let Bc,i = B, c, U< p C R is prime, and Vx € p - 1 C\C, 3ye C such that (x - 2/)_1p_1C G Bc,i-i and let Bc = U°l0Bc,i-

Lemma 1.2.4- — (Harper's Lemma for Ideals, Relative to C) If K is a number field and p~l is an element of Be for all prime ideals p in @K, then [C] is a Euclidean ideal class. The proof uses the Chebotarev density theorem applied to a well- chosen ray class field in an analogous fashion to the use of Dirichlet's theorem on primes in arithmetic progressions to prove Lemma 1.2.4. The set Bc,i are more amenable to growth analysis than the sets A^c are. In order to create general machinery like Harper's, however, his tools will have to be adapted to the Euclidean ideal class framework. 1.3. The Large Sieve for Elements and Ideals The large sieve is the heart of Harper's general machinery. The usual large sieve measures how a set of finitely many elements is distributed among the congruence classes of various primes. Note below how the elements in the finite set must be non-associate. In other words, no element in the set is the product of a unit and another element in the set. Definition 1.3.1. — Given a prime ideal p , a G &K, and a finite set of non-associated integers A, let Z(a,p) := \{x E A | x = a (mod p)}| . 9

Now that we have Definition 1.3.1, we can state the version of the Large Sieve in [12]. It is sometimes called the "Statistical Version" of the Large Sieve. Theorem 1.3.2. — (The Large Sieve) Let K be a number field, let A a finite set of non-associate algebraic integers and let P a finite set of prime ideals. If X = m.axx€A |Nm(x)| and if Q — maxpGpNm(p)7 then peP aeR/p v y r j/ where the implied constant depends only on K. The issue of associate elements comes up again with the adaptation of the large sieve to ideal classes. In order to reformulate the large sieve appropriately, we need the following definitions. Definition 1.3.3. — For a number field K and a prime ideal p, we define /(p) to be the number of equivalence classes of elements modulo p that are represented by a unit, i.e. /(p) := \{a G @K/p I (a - u) e p for some u G ff^}\ . The following definition and theorem are new. Definition 1.3.4- — Let K be a number field and let C be a non-zero ideal. Suppose A is a finite set of fractional ideals in E such that if / 10

and J are in A, then [/] = [J]. Then for any prime ideal p such that [P_1] — [-fC-1] for an ideal I in A and for any a in p_ 1 C, we define Z(a,p,C):={ I(P) I e A\3y e C such that (a + y)-1p-iC = I I € A\3y E C such that (a + y)-1p-lC = I a(£C ae C Using these definitions, we can now state the large sieve for ideal classes. Theorem 1.3.5. — (Large Sieve with Respect to C) Let K be a number field, C a non-zero ideal in (?%, and n an integer. Suppose A is a finite set of ideals containing &K such that given two ideals I and J in A , [I] = [J]. Suppose P is a finite set of prime ideals p such that [p_1] = [/C_1] for any ideal I in A. If X = m&xIeA Nm(/_1) and Q = maxpepNm(p), then *>•»*> £ ( £<^) - l AL) 2 «^ + x)|,|. pep aep-^c/c v J Krj yv,/ The implied constant depends only on K and the ideal class of C. Now that we have a reformulation of the large sieve for ideal classes, we can then develop general machinery to apply to the variation of Motzkin's construction for ideal classes. Using this, we show that if |{J e B^c I Nm(7_1) < x} | >> J^4-J, then [C] is a Euclidean ideal class. As in 11

the previous case, we can intelligently augment the set B^c and the machinery is still robust enough for the result to hold. The way Harper augmented his sets B^ in a number field K was by finding a set of 'admissible' primes, and then adding the monoid gen erated by 0^ and these primes to his set. He could then still use his machinery to show that if the appropriate set grows 'quickly enough,' then the ring &K is Euclidean. He did this because by augmenting his set by this monoid, the sets grew more quickly and he could then use the growth of early sets to show that B itself is sufficiently large. Our goal is to find a way to apply our ideal class machinery to specific number fields. Due to technical obstructions, we could not augment our sets by the monoids Harper used. Instead, we concentrated on the concept of an 'admissible' set of primes. After tweaking that concept, we found and proved Theorem 1.3.7. Definition 1.3.6. — Given a number field K, we denote the size of its classgroup by hx- Theorem 1.3.7. — (The Gupta-Murty Bound with Respect to C) Let K be a number field; let C be a non-zero ideal; let m be an integer; let pi,... ,pk be a set of distinct prime ideals, such that each [pi] = [Cm]; and let Wl be the set {Pr a i - - - Pr t I (ai,. ••,<**) GN*, ai + --- + ak = m {mod hK)} . 12

If p is a prime ideal such that [p] = [Cm+l], then we define I\OT'-= \{aep-lC/C,a^0\3y e C such that (a + yYlp~1C G 9Jt}| . The set of primes p such that [p] = [Cm+1] and Tp

CHAPTER 2 THE EUCLIDEAN ALGORITHM AND MOTZKIN'S LEMMA Before studying Euclidean algorithms on ideals, we shall first review traditional N-valued Euclidean algorithms on elements. Recall that the most common use of the Euclidean algorithm is showing that a ring is a principal ideal domain. Definition 2.0.8. — Let R be a domain and let W be a well-ordered set. If ip is a function, ip : R \ 0 —> W, and if for all elements a, b in R, b 7^ 0, there exist some elements q, r in R such that a = bq + r, with either r = 0 or tp(r) < ip(b), then ip is a Euclidean algorithm on R. If R is a domain with a Euclidean algorithm, then R is a Euclidean domain. Theorem 2.0.9. — If R is Euclidean, then it is a principal ideal do main. Proof. — Let (/ \ 0), then given any a € I, there exist q,r 6 R 14

such that a = bq + r,(j)(r) < 4>(b), implying r = 0 and b \ a. We therefore conclude I = (b). O The classic example of a Euclidean domain is Z, where the absolute value is a Euclidean algorithm. The second most commonly taught ex ample is 1i[i], where both the norm and the square root of the norm, i.e. ijj(a + bi) = \/a2 + b2, are Euclidean algorithms. In fact, Euclidean originally meant norm-Euclidean. Definition 2.0.10. — If K is a number field and S is the set of field embeddings into C, then we define the norm of an element x in K to be Nm(i) = JJcr(:c). aes Definition 2.0.11. — Let K be a number field. If for all elements x of K, there exists some y in ffK such that Nm(:r — y) < 1, then &K is called norm-Euclidean. We can see that this is equivalent to having the norm be a Euclidean algorithm for 6K. If a; is a non-zero element of K, then it can be written as a quotient |, where a and b are elements of &K, with b ^ 0. If the norm is a Euclidean algorithm for GK, then there exist some y and r in OK such that a = yb + r and Nra(r) < Nm(6). This implies that Nm( l -s).Nm(£-y)-Nnl (i^)=Nm(I)-^<. 15

and we see that two definitions are indeed equivalent. It was unknown until the work of David A. Clark whether there are any Euclidean integer rings that are not norm-Euclidean. In 1994 , Clark proved ([1]) Z[±±f^] is Euclidean but not norm-Euclidean. This means that, given a number field K, we cannot always use the norm to check whether or not &K is Euclidean. Fortunately, in 1948, Theodore Motzkin ([9]) came up with a new way to look at Euclidean rings. Definition 2.0.12. — (Motzin's Construction for Elements) Given a domain R, let A0 := {0} U Rx, so it contains zero and all the units. Let Ai = Ai_i U < a G R Vx £ R, 3y e 4j_i such that x — y G (a) for i > 0 and let A := U^0^4i. We call the sequence of nested sets Ai Motzkin's Construction. If A = R, we define 4>R to be the function from R \ 0 to N such that 4>R(X) is i if x is an element of Ai \ Ai-\. Lemma 2.0.13. — Let R be a domain. Given an unit u G Rx and an element (3 E Ai, the element u/3 is also in Ai. In other words, uAi = Ai for all i. Proof. — By definition, (5 is in Ai if every equivalence class modulo (/?) is represented by an element of Ai_\. The ideals (/3) and (u@) are equal for any unit u, so the result holds. • 16

Theorem 2.0.14- — (Motzkin's Lemma) If the domain R is equal to A, then R is a Euclidean domain. Proof. — Assume A equals R and let 4>R be the function in Definition 2.0.12. Given two elements a, b of R, b ^ 0, we know that either b divides a or there exists some r E A^^-i such that a — r is an element of the ideal (b). This means that there exist some r, q £ R such that a = qb + r, where either r = 0 or (j)R(r) <

Definition 2.0.15. — Given a Euclidean ring R and a well-ordered set W, we define 4>w '• R —• W, by 4>w{®) := inf^0(a), where the infimum is taken over the set of all Euclidean algorithms from R to W. Proposition 2.0.16. — The map w(P)- We conclude that (fiw is a Euclidean algorithm from R to W. O Definition 2.0.17. — Henceforth, we shall call 4>w the least algorithm from R to W. Note that it is unique. 18