From: Ken.Pledger@vuw.ac.nz (Ken Pledger) Subject: Re: Euclidean Domains and defining Norm Date: Tue, 07 Mar 2000 13:41:22 +1200 Newsgroups: sci.math Summary: [missing] In article , Neil Zanella wrote: > .... > I have seen different possibly equivalent definitions of Euclidean domain > in different textbooks. Yes, there are different versions floating around. Some years ago I taught a course on elementary ring theory, and spent a lot of time puzzling over this. > Curiosity leads to the following question: given > the following two definitions does the third property follow? Does a > even a weaker version of property 3 follow?.... A weaker version does follow. See below. > 1 Definition [ Norm ] > --------------------- > > Let R be an integral domain. > A norm on R is a function N:R\0-->(positive integers). > > 2 Definition [ Euclidean Domain ] > --------------------------------- > > Let R be an integral domain. > Then R is said to be a Euclidean Domain with norm N if for all a,b in R > there exist q,r in R with a=qb+r and r=0 or N(r) > 3 Problem (does this follow?) > --------- > > Let E be a Euclidean Domain with norm N. Prove or disprove: there exists a > norm N' on E such that for all a,b in E, N'(ab)=N'(a)N'(b). There's a popular strengthening of your #2 which is weaker than #3. I'll call it #2.5. 2.5. A Euclidean domain as defined in #2 above may (or may not) have the extra property that whenever x divides y (and y is not 0), then N(x) <= N(y). In many books you'll find that the author builds in #2.5 as part of the definition of Euclidean domain. But it's not necessary. I've found that #2 is strong enough to prove the following: Each non-zero element x has an associate x' such that whenever x divides y (and y is not 0), then N(x') <= N(y). That's just as useful as #2.5 for proving things, but I'd be surprised if you'd seen it before anywhere. Ken Pledger. ============================================================================== From: Robin Chapman Subject: Re: Euclidean Domains and defining Norm Date: Tue, 07 Mar 2000 08:08:11 GMT Newsgroups: sci.math In article <38C31B1A.8774B856@world.std.com>, David M Einstein wrote: > > No, or at least there is not neccessarily an N' that satisfies > condition 2. An example is the ring of integers of Q(sqrt(69)). > Unfortunately, > I do not recall who proved this, but it was proved sometime in the last > five years. David Clark. I think his paper appeared in 1993 or 1994, but I can no longer recall the details. -- Robin Chapman, http://www.maths.ex.ac.uk/~rjc/rjc.html "`The twenty-first century didn't begin until a minute past midnight January first 2001.'" John Brunner, _Stand on Zanzibar_ (1968) Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: "Malcolm Harper" Subject: Re: Euclidean Domains and defining Norm Date: Tue, 07 Mar 2000 13:51:10 GMT Newsgroups: sci.math Neil Zanella wrote in message news:Pine.OSF.4.21.0003031643330.3089-100000@garfield.cs.mun.ca... > > Hello, > > I have seen different possibly equivalent definitions of Euclidean domain > in different textbooks. Curiosity leads to the following question: given > the following two definitions does the third property follow? Does a > even a weaker version of property 3 follow? > > Any references to papers covering this norm issue would be appreciated. > > Thanks, > > Neil Zanella > nzanella@cs.mun.ca > > > 1 Definition [ Norm ] > --------------------- > > Let R be an integral domain. > A norm on R is a function N:R\0-->(positive integers). > > 2 Definition [ Euclidean Domain ] > --------------------------------- > > Let R be an integral domain. > Then R is said to be a Euclidean Domain with norm N if for all a,b in R > there exist q,r in R with a=qb+r and r=0 or N(r) > 3 Problem (does this follow?) > --------- > > Let E be a Euclidean Domain with norm N. Prove or disprove: there exists a > norm N' on E such that for all a,b in E, N'(ab)=N'(a)N'(b). I don't believe 3 follows although I don't know a counter- example. Any counter-example must come from outside the realm of algebraic number fields. See Samuel [1] for among other things a proof of 3a) Given a Euclidean algorithm N:R\0 --> (non-negative integers) satisfying 2 there exists a Euclidean algorithm N':R\0 --> (non-negative integers) satisfying 2 such that N'(ab) >= N'(a) + N'(b) for all non-zero ab. [1] P. Samuel, About Euclidean rings, Journal of Algebra 19 (1971), 282--301. Malcolm ============================================================================== From: "Malcolm Harper" Subject: Re: Euclidean Domains and defining Norm Date: Tue, 07 Mar 2000 13:51:13 GMT Newsgroups: sci.math David M Einstein wrote in message news:38C31B1A.8774B856@world.std.com... > > Neil Zanella wrote: [snip] > > > > 1 Definition [ Norm ] > > --------------------- > > > > Let R be an integral domain. > > A norm on R is a function N:R\0-->(positive integers). > > > > 2 Definition [ Euclidean Domain ] > > --------------------------------- > > > > Let R be an integral domain. > > Then R is said to be a Euclidean Domain with norm N if for all a,b in R > > there exist q,r in R with a=qb+r and r=0 or N(r) > > > 3 Problem (does this follow?) > > --------- > > > > Let E be a Euclidean Domain with norm N. Prove or disprove: there exists a > > norm N' on E such that for all a,b in E, N'(ab)=N'(a)N'(b). > > No, or at least there is not neccessarily an N' that satisfies > condition 2. An example is the ring of integers of Q(sqrt(69)). > Unfortunately, > I do not recall who proved this, but it was proved sometime in the last > five years. There is probably a simpler example, but I can't think of > one right now. > Deinst. It is a little unclear (to me) what is being asked here. If the question is "Are there algebraic number fields whose ring of integers is a Euclidean domain for which the norm is not a Euclidean algorithm?" then your response is quite correct. As Robin Chapman notes the proof is due to Clark [1]. The Q(sqrt{69}) result is actually the simplest example. By more complicated methods Clark gave other examples in his thesis. If the question is "Given a Euclidean domain with algorithm N does there exist a multiplicative algorithm N'? " the answer is not so clear. I don't believe this could be true in general, however it is true for the rings of integers of algebraic number fields if you accept a generalized Riemann hypothesis. [1] David A. Clark, A quadratic field which is Euclidean but not norm-Euclidean, Manuscripta Mathematica 83 (1994), 327--330. Malcolm ============================================================================== From: Deinst@world.std.com (David M Einstein) Subject: Re: Euclidean Domains and defining Norm Date: Tue, 7 Mar 2000 16:45:59 GMT Newsgroups: sci.math Malcolm Harper (pirround@NOSPAMhotmail.com.invalid) wrote: : David M Einstein wrote in message : news:38C31B1A.8774B856@world.std.com... : > : > Neil Zanella wrote: : [snip] : > > : > > 1 Definition [ Norm ] : > > --------------------- : > > : > > Let R be an integral domain. : > > A norm on R is a function N:R\0-->(positive integers). : > > : > > 2 Definition [ Euclidean Domain ] : > > --------------------------------- : > > : > > Let R be an integral domain. : > > Then R is said to be a Euclidean Domain with norm N if for all a,b in R : > > there exist q,r in R with a=qb+r and r=0 or N(r) > : > > 3 Problem (does this follow?) : > > --------- : > > : > > Let E be a Euclidean Domain with norm N. Prove or disprove: there : exists a : > > norm N' on E such that for all a,b in E, N'(ab)=N'(a)N'(b). : > : > No, or at least there is not neccessarily an N' that satisfies : > condition 2. An example is the ring of integers of Q(sqrt(69)). : > Unfortunately, : > I do not recall who proved this, but it was proved sometime in the last : > five years. There is probably a simpler example, but I can't think of : > one right now. : > Deinst. : It is a little unclear (to me) what is being asked here. : If the question is "Are there algebraic number fields whose ring of : integers is a Euclidean domain for which the norm is not a Euclidean : algorithm?" then your response is quite correct. As Robin Chapman notes : the proof is due to Clark [1]. The Q(sqrt{69}) result is actually the : simplest example. By more complicated methods Clark gave other examples in : his thesis. : If the question is "Given a Euclidean domain with algorithm N does there : exist a multiplicative algorithm N'? " the answer is not so clear. I don't : believe this could be true in general, however it is true for the rings of : integers of algebraic number fields if you accept a generalized Riemann : hypothesis. : [1] David A. Clark, A quadratic field which is Euclidean but not : norm-Euclidean, Manuscripta Mathematica 83 (1994), 327--330. : Malcolm IIRC Clark's norm was not multiplicative. If it was, sorry. Is it possible to have a ring in which r can always be 0 or a unit? This is obviously true of fields, but are there more? ============================================================================== From: "Malcolm Harper" Subject: Re: Euclidean Domains and defining Norm Date: Wed, 08 Mar 2000 00:41:40 GMT Newsgroups: sci.math David M Einstein wrote in message news:Fr298n.8JA@world.std.com... [snip] > IIRC Clark's norm was not multiplicative. If it was, sorry. As I recall what Clark did for Q(sqrt{69}) was modify the norm at one or two primes and extend by complete multiplicativity giving a multiplicative algorithm not the norm. In any event even if Clark's algorithm is not multiplicative does not mean that no multiplicative algorithm exists. > > Is it possible to have a ring in which r can always be 0 or a unit? > This is obviously true of fields, but are there more? Interesting question. My thinking went no .. yes .. no. Let R be a Euclidean domain and suppose for every non-zero b in R every residue class a+bR contains a remainder r with r either 0 or a unit. Suppose b is not 0. If the residue class b+(b^2)R contains 0 then b^2 divides b and b is a unit. If the residue class b+(b^2)R contains a unit r then b|r and again b is a unit. Every non-zero b is a unit so R is a field. Malcolm