From: dean@ucdmath.ucdavis.edu (Dean Hickerson) Newsgroups: sci.math.research Subject: Euclidean rings (Re: Quadratic Fields) Date: Sat, 17 Jun 1995 13:18:45 -0700 In article <1995Jun16.190331.22984@njitgw.njit.edu> katz@galois.njit.edu (Robert Katz) asked: >Consider the quadratic number fields, a + b * sqrt (d), where >a, b are rational and d is a square free integer, positive or >negative. For which d is the field a >i) Euclidean domain >ii) Principal ideal domain >iii) unique factorization domain ? And Noam Elkies (elkies@ramanujan.harvard.edu) replied: > [The *field* is, of course, a UFD, but presumably you mean the ring > of integers... Anyway, (ii) <-> (iii). For d<0 it's known that there > are only 9 fields and 13 rings (four of which are proper subrings of > the rings of integers) which have unique factorization. The Euclidean > domains with both d<0 and d>0 are known, but I don't remember the list > or a good reference. It's conjectured that there are infinitely many > UFD's with d>0 but there's probably no proof coming soon. --NDE] In a followup article, Bob Silverman (bobs@mathworks.com) said: > You can find it in Hardy & Wright. > > The five Euclidean fields with d < 0 are -1, -2, -3, -7, -11. > With d > 0 we have 2,3,5,6,7,11,13,17,19,21,29,33,37,41,57,73. This is only partially correct. The general definition of a Euclidean ring is that there is some function n from the nonzero elements of the ring to the nonnegative integers for which the division algorithm works. (Specifically, for any a and b in the ring with b nonzero, there exist q and r in the ring with a=qb+r and either r=0 or n(r) katz@galois.njit.edu (Robert Katz) asked: |> Consider the quadratic number fields, a + b * sqrt (d), where |> a, b are rational and d is a square free integer, positive or |> negative. For which d is the field a |> i) Euclidean domain |> ii) Principal ideal domain |> iii) unique factorization domain ? To which Guest Moderator Noam Elkies (elkies@ramanujan.harvard.edu) added: |> [The *field* is, of course, a UFD, but presumably you mean the ring |> of integers... Anyway, (ii) <-> (iii). For d<0 it's known that there |> are only 9 fields and 13 rings (four of which are proper subrings of |> the rings of integers) which have unique factorization. I wonder what you were thinking of here? `UFD' implies `integrally closed'; a proper subring of the ring of integers cannot have unique factorization. In Z[sqrt(-3)] , e.g., the _invertible_ ideals are all principal, but there are non-principal non-invertible ideals like (2, 1+sqrt(-3)). Z[sqrt(-4)] is a similar example, Z[sqrt(-27)] is another, and I'm too lazy to discover the fourth ;-). Is this what you had in mind? [Since Noam took the ring of integers of a number field, that is then integrally closed by the usual definition. - Greg] |> The Euclidean |> domains with both d<0 and d>0 are known, but I don't remember the list |> or a good reference. It's conjectured that there are infinitely many |> UFD's with d>0 but there's probably no proof coming soon. --NDE] In a followup article (which I haven't seen here yet), Bob Silverman (bobs@mathworks.com) provided the reference to Hardy & Wright and the list of norm-euclidean quadratic fields, and in article <199506172018.NAA20568@ucdmath.ucdavis.edu>, dean@ucdmath.ucdavis.edu (Dean Hickerson) commented on this as follows: |> This is only partially correct. The general definition of a Euclidean |> ring is that there is some function n from the nonzero elements of the |> ring to the nonnegative integers for which the division algorithm works. |> [...] It |> happens to be true that for every algebraic number field that's been |> proved to be Euclidean we can take n to be the absolute value of the |> norm; i.e. n(a) is the absolute value of the products of the conjugates |> of a. This is no longer true; David A Clark recently showed that the ring of integers of Q(sqrt(69)) , which fails to be norm-euclidean, is euclidean with respect to a multiplicative function which agrees with the absolute norm on all primes except that of norm 23 where it needs to take a larger value (anything > 25 will do), and Clark and Franz Lemmer- meyer proceeded to find some more examples like this in higher degrees. See "A quadratic field which is euclidean but not norm-euclidean" by D A Clark, Manuscripta Math. 83 (1994), 327--330. See also the note by Yours Truly, same volume, 443--446. The proofs use (slight variants of) time-honored number-geometric methods. [...] |> In particular, the ring Z[sqrt(14)] is |> probably Euclidean; in "L'anneau Z[sqrt(14)] et l'algorithme Euclidien", |> by Edmondo Bedocchi, Manuscripta Math. 53 (1985), 199-216, a function n |> is given with respect to which the ring is conjectured to be Euclidean. This ring, however, has so far resisted a determined attack along the same lines... Gerhard Niklasch -- +------------------------------------+----------------------------------------+ | Gerhard Niklasch | All opinions are mine --- I even doubt | | | whether this Institute HAS opinions:-] | +------------------------------------+----------------------------------------+ ============================================================================== From: elkies@ramanujan.math.harvard.edu (Noam Elkies) Newsgroups: sci.math.research Subject: Re: Euclidean rings (Re: Quadratic Fields) Date: 20 Jun 1995 00:23:54 GMT In article <1995Jun19.103103@mathematik.tu-muenchen.de> nikl@mathematik.tu-muenchen.de writes: >[...] >In Z[sqrt(-3)] , e.g., the _invertible_ ideals are all principal, but >there are non-principal non-invertible ideals like (2, 1+sqrt(-3)). >Z[sqrt(-4)] is a similar example, Z[sqrt(-27)] is another, and I'm >too lazy to discover the fourth ;-). Is this what you had in mind? Yes it is, except that for Z[sqrt(-27)] substitute Z[(1+sqrt(-27))/2]. The fourth example is Z[sqrt(-7)], which is of index 2 in its integral closure Z[(1+sqrt(-7))/2]. --Noam D. Elkies (elkies@math.harvard.edu) Dept. of Mathematics, Harvard University ============================================================================== Date: Mon, 19 Jun 95 13:45:23 CDT From: rusin (Dave Rusin) To: katz@galois.njit.edu Subject: Re: Quadratic Fields Status: RO In article <1995Jun16.190331.22984@njitgw.njit.edu> you write: >Consider the quadratic number fields, a + b * sqrt (d), where >a, b are rational and d is a square free integer, positive or >negative. For which d is the field a >i) Euclidean domain >ii) Principal ideal domain >iii) unique factorization domain ? > >[The *field* is, of course, a UFD, but presumably you mean the ring >of integers... Anyway, (ii) <-> (iii). For d<0 it's known that there >are only 9 fields and 13 rings (four of which are proper subrings of >the rings of integers) which have unique factorization. The Euclidean >domains with both d<0 and d>0 are known, but I don't remember the list >or a good reference. It's conjectured that there are infinitely many >UFD's with d>0 but there's probably no proof coming soon. --NDE] I suppose it's possible that you did _not_ mean the ring of integers. The distinction occurs precisely when d = 1 mod 4. In that case, the ring of integers of the field Q[sqrt(d)] is the ring of all integral linear combinations of 1 and (-1 + sqrt(d) ) / 2. You do need to be careful when reading the literature if for example you really want to know about Z[sqrt(-3)], since this is only a subring of what most people are studying (in this case, Z[1^(1/3)].) The reason the larger ring is preferred is that it is integrally closed (in its quotient field) -- in this example, for instance, the roots of x^2+x+1=0 are integral over Z[sqrt(-3)], but lie in the quotient field of this ring. Usually it's true that unique factorization (and thus also being a PID) requires that the ring be integrally closed. In the example above, for example, 2.2=(1+sqrt(-3))(1-sqrt(-3)) defies unique factorization. Likewise it is clear that d must be square-free. Here are two of the lists Elkies implied. The data come from Borevich and Shafarevich (see p. 167, 422, and 425). When d < 0, any Euclidean algorithm would give a UFD, and there are only nine such fields, those with -d = 1 2 3 7 11 19 43 67 163 I don't know what the other four rings he mentioned are. I also don't know just which of these UFDs really are Euclidean -- when d= -1 , -2, or -3, the rings are Euclidean, but not when d=-19 (see Motzkin, "The Euclidean Algorithm", Bull AMS 55 (1949) 1142-6.) Among positive integers d, the ring of integers of Z[sqrt(d)] is a Euclidean domain relative to the usual norm (size of a+b sqrt(d) is |a^2-d b^2|) iff d is one of the following 2 3 5 6 7 11 13 17 19 21 29 33 37 41 57 73 I guess it's true that there could be other norms which suffice to make other rings Euclidean domains, but that seems unlikely. There are other rings with d>0 which are UFDs but not Euclidean (relative to the standard norm anyway), probably infinitely many, I suppose, starting with d= 14 22 23 31 38 43 46 47 53 59 61 62 67 69 71 and all the UFDs with d>73. I don't know in this case what happens for non integrally-closed rings. If you get more detailed information I'd appreciate a copy for my files. dave ============================================================================== Date: Wed, 5 Jul 1995 17:10:47 -0400 (EDT) From: robert katz To: rusin@math.niu.edu Subject: Re: Quadratic Integers Gentlemen: A while back I posed a question concerning quadratic number fields. Specifically, for which `d' is the domain of integers --I originally forgot to specify integers-- in the quadratic field a + b * sqrt (d) i) euclidean ii) principal iii) unique factorization Thank you all for your help. This seems to be the summary: If you define a size function to be abs (a^2 - d * b^2) then the euclidean fields are precisely those with d = -1 -2 -3 -7 -11 2 3 5 6 7 11 13 17 19 21 29 33 37 41 57 73. For a different size function, there may be other euclidean domains. The ufd also include the values of d = -19 -43 -67 -163, and it is unknown whether there are an infinite number of d > 0 for which the domain is ufd. Finally, in a quadratic number field, every ufd is a principal ideal domain. Thanks again, Robert Katz ============================================================================== From: Paul Pollack Subject: re http://www.math.niu.edu/~rusin/known-math/95/euclidean.dom Date: Sun, 07 Mar 1999 13:30:45 -0500 Newsgroups: [missing] To: rusin@math.niu.edu I was glancing through your wonderful archives, particularly the page discussing rings of integers of quadratic fields and when they are Euclidean domains and noticed the following: > When d < 0, any Euclidean algorithm would give a UFD, and there > are only nine such fields, those with -d = > 1 2 3 7 11 19 43 67 163 > I don't know what the other four rings he mentioned are. > I also don't know just which of these UFDs really are Euclidean -- > when d= -1 , -2, or -3, the rings are Euclidean, but not when d=-19 > (see Motzkin, "The Euclidean Algorithm", Bull AMS 55 (1949) 1142-6.) As mentioned on your page, when d<0 the ring in question is norm Euclidean for d=-1,-2,-3,-7,-11 and no others. It seems relevant to note that Dubois & Steger (1958) proved that in the imaginary quadratic field case, the ring is Euclidean w.r.t. some function <==> it is norm-Euclidean. Thus for d<0, we have a complete list. Their proof goes like this: Let R(d) be the ring of integers of Q(sqrt(-d)), and suppose R(d) is Euclidean with respect to some "norm" f. Let alpha be a nonzero nonunit which minimizes f, and look at R(d)/ which has N(alpha) elements. But since R(d) is Euclidean with respect to f, by D.A. and our choice of alpha, R(d)/ can have as elements only the cosets of 0 and units. Since we can assume d != 1,2,3,7 or 11, the only units are 1 and -1 ==> R(d)/ has at most 3 elements ==> N(alpha) <= 3. But it is easy to see that for d != 1,2,3,7,11, there are no elements of norm 2 or 3 in R(d) ==> N(alpha)=1 ==> alpha is a unit, contradicting our choice of alpha. Sincerely, Paul Pollack ============================================================================== From: Paul Pollack Subject: Re: re http://www.math.niu.edu/~rusin/known-math/95/euclidean.dom Date: Mon, 08 Mar 1999 19:16:46 -0500 Newsgroups: [missing] To: Dave Rusin Dave Rusin wrote: > Thanks for your kind remarks, and your suggestions for improvement. > Unless you have some specific objection, I'd like to append your remarks > to the file. I would be honored. I didn't see the result in question mentioned already, and it seemed somewhat interesting, so I just decided to chime in. I hope it's not already somewhere else in your extensive archives! [deletia --djr] Sincerely, Paul Pollack ============================================================================== From: Franz Lemmermeyer Subject: Re: Unique Factorization Domains Date: Sun, 24 Oct 1999 18:11:01 +0200 Newsgroups: sci.math.research Keywords: Which quadratic extensions of Z are UFDs? Daz wrote: > > I am fascinated by the theorem stating that among the rings Z[sqrt(-m)] > for m a positive integer, the only ones with unique factorization are > those for m = 1,2,3,7,11,19,43,67, or 163. > > QUESTION 1: Is there some deep reason that the successive differences of these > numbers divide each other (with all successive quotients being 1, 2, 3, or 4)? > > That is, 1 | 1 | 4 | 4 | 8 | 24 | 24 | 96. 1. It is not the rings Z[sqrt(-m)] that are UFD's but the rings of integers in Q(sqrt(-m)): these are different from Z[sqrt(-m)] for m = 3 mod 4. 2. Yes there is a "deep" reason for this kind of behaviour: the integers 19,43,67, 163 are quadratic nonresidues modulo small primes (and must be if Q(sqrt(-m) is to have class number 1). This forces these integers to lie in certain residue classes modulo the product of small primes. > QUESTION 2: What is known about which of the rings Z[sqrt(m)], for m > a positive integer, have unique factorization? Gauss conjectured that there are infinitely many. See Hardy & Wright, Ireland & Rosen, or one of H. Cohn's books on (algebraic) number theory. franz ============================================================================== From: "Daniel Grace" Subject: Conditions on d for {a+b*sqrt(d)} a UFD? Date: Wed, 17 Nov 1999 09:14:30 -0000 Newsgroups: sci.math What are conditions must d satisfy for F={a+b*sqrt(d):a,b are integers} to be unique factorization domain? Obviously F contains complex numbers iff d is negative. I have seen a complete list of negative values for d in books and on the following web page http://www.ams.org/new-in-math/cover/factorization.html The theorem that proves this list is complete is "deep". Presumably that means there are lots of cases and a long proof? For what positive d's if any is F a UDF? What are the neccessary conditions for positive d? Thanks, ---------------------------------------------------------- Daniel e-mail: dan.@landemann.freeserve.co.uk ============================================================================== From: Robin Chapman Subject: Re: Conditions on d for {a+b*sqrt(d)} a UFD? Date: Wed, 17 Nov 1999 21:45:33 GMT Newsgroups: sci.math In article <80tsre$bdr$1@news6.svr.pol.co.uk>, "Daniel Grace" wrote: > What are conditions must d satisfy for > F={a+b*sqrt(d):a,b are integers} to be unique factorization > domain? > For what positive d's if any is F a UDF? > What are the neccessary conditions for positive d? A lot of examples are known, but it's not known whether there are finitely or infinitely many instances. -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "`Well, I'd already done a PhD in X-Files Theory at UCLA, ...'" Greg Egan, _Teranesia_ Sent via Deja.com http://www.deja.com/ Before you buy.