Euclidean Domain
Alfred Steele
In article <HAMMOND.93...@annemarie.albany.edu>, ham...@csc.albany.edu (
William F. Hammond) writes:
|> In article <Jan.3.02.05....@spade.rutgers.edu>
|> ca...@spade.rutgers.edu (Uniquely TiJean) writes:
[....]
|>If someone can answer the question:
|>Why there are not other candidates for the Euclidean function?
I have asked the very same question and do not know the answer. The previous
posters have made reference to Hungerford's Algebra Text
Hungerford's definition does not use the norm - this is true of most
texts. His problem #8 Chapter III section 3 (in my edition) asks to show
a + b(1 + sqrt(19)) a,b \in Q is a principal ideal domain but not a
Euclidean domain. My guess is that any function that satisfies Hungerford's
definition of Euclidean domain:
f : R - {0} \arrow N
a) a,b \in R and ab \notequal 0 then f(a) \le f(ab)
b) usual definition with division and f(r) \lt f(b) or r = 0 in
a = qb + r
will be equivalent to a norm. Something like this is Ostrowski's theorem
which states that non-trivial norms (or valuations) are either absolute
values or p-adic norms.
Any information netters know about this, I would be interested in hearing
about. What is the "folklore" on the subject?
Alfred T. Steele
ste...@isis.cgd.ucar.edu
Richard Bumby
>In article <HAMMOND.93...@annemarie.albany.edu>, ham...@csc.albany.edu (
>William F. Hammond) writes:
>|> In article <Jan.3.02.05....@spade.rutgers.edu>
>|> ca...@spade.rutgers.edu (Uniquely TiJean) writes:
>[....]
>|>If someone can answer the question:
>|>Why there are not other candidates for the Euclidean function?
>I have asked the very same question and do not know the answer....
>Any information netters know about this, I would be interested in hearing
>about. What is the "folklore" on the subject?
This should be a FAQ. T. S. Motzkin, "The Euclidean Algorithm", Bull.
Amer. Math. Soc. 55(1949), 1142-1146, gave a simple analysis of the
properties of any Euclidean Algorithm in an integral domain. The idea
is to work backwards, starting with the set consisting only of zero,
and applying the following construction. The derived set of a set, S,
consists of all elements of the domain which have a complete set of
residues in S. This construction may be extended transfinitely if
necessary by taking unions at limit ordinals. In order to have a
Euclidean Algorithm, you must be able to exhaust the domain in this
way. For quadratic number rings, there are only finitely many units.
The derived set of {0} consists only of units. If all proper ideals
have index greater than the number of units (only 2 except for some
rings that are already Euclidean for the norm), the process stops
there.
Another major article on Euclidean Algorithms is P. Samuel, "About
Euclidean Rings", J. Algebra 19 (1971), 282-301. It would appear that
the next major exposition is due this year.
--
R. T. Bumby ** Rutgers Math || Amer. Math. Monthly Problems Editor
bu...@math.rutgers.edu || P.O. Box 10971 New Brunswick, NJ08906-0971
bu...@dimacs.rutgers.edu || Phone: [USA] 908 932 0277 * FAX 908 932 5530
David Bradley
>William F. Hammond) writes:
>
>a + b(1 + sqrt(19)) a,b \in Q is a principal ideal domain but not a
>Euclidean domain.
For the record, that should read {a + b(1 + sqrt(19))/2 : a,b \in Z} or
equivalently, R := { a + b sqrt(19) : a,b \in (Z + 1/2) }. See the
November 1988 issue of the Monthly for a short, elementary proof that
the above ring is a PID but not an ED (not just not Euclidean in the
norm, but that no Euclidean function works).
>Any information netters know about this, I would be interested in hearing
>about. What is the "folklore" on the subject?
I've been told that making the above an exercise, with no hints or
similar disproofs in the text was "irresponsible".
-d
Henri Cohen
bu...@dimacs.rutgers.edu (Richard Bumby) writes:
|> ste...@isis.cgd.ucar.edu (Alfred Steele) writes:
|>
|>
|> >In article <HAMMOND.93...@annemarie.albany.edu>,
ham...@csc.albany.edu (
|> >William F. Hammond) writes:
|> >|> In article <Jan.3.02.05....@spade.rutgers.edu>
|> >|> ca...@spade.rutgers.edu (Uniquely TiJean) writes:
|> >[....]
|>
|> >|>If someone can answer the question:
|> >|>Why there are not other candidates for the Euclidean function?
|>
|> >I have asked the very same question and do not know the answer....
|> >Any information netters know about this, I would be interested in hearing
|> >about. What is the "folklore" on the subject?
|>
|> This should be a FAQ. T. S. Motzkin, "The Euclidean Algorithm", Bull.
|> Amer. Math. Soc. 55(1949), 1142-1146, gave a simple analysis of the
|> properties of any Euclidean Algorithm in an integral domain. The idea
|> is to work backwards, starting with the set consisting only of zero,
|> and applying the following construction. The derived set of a set, S,
|> consists of all elements of the domain which have a complete set of
|> residues in S. This construction may be extended transfinitely if
|> necessary by taking unions at limit ordinals. In order to have a
|> Euclidean Algorithm, you must be able to exhaust the domain in this
|> way. For quadratic number rings, there are only finitely many units.
Of course this is only for IMAGINARY quadratic number rings.
|> Another major article on Euclidean Algorithms is P. Samuel, "About
|> Euclidean Rings", J. Algebra 19 (1971), 282-301. It would appear that
|> the next major exposition is due this year.
|> --
|> R. T. Bumby ** Rutgers Math || Amer. Math. Monthly Problems Editor
|> bu...@math.rutgers.edu || P.O. Box 10971 New Brunswick, NJ08906-0971
|> bu...@dimacs.rutgers.edu || Phone: [USA] 908 932 0277 * FAX 908 932 5530
A result which I believe is due to H. W. Lenstra is that under the Generalized
Riemann Hypothesis, ALL number fields with class number 1 (i.e. with unique
factorization) are Euclidean for SOME Euclidean algorithm (of course usually
not the one given by the norm), EXCEPT those which have finitely many units,
in other words imaginary quadratic fields.
Henri Cohen
Bradley W. Brock
> In article <HAMMOND.93...@annemarie.albany.edu>,
ham...@csc.albany.edu (
> >William F. Hammond) writes:
> >
> >Hungerford's problem #8 Chapter III section 3 (in my edition) asks to show
> >a + b(1 + sqrt(19)) a,b \in Q is a principal ideal domain but not a
> >Euclidean domain.
>
> For the record, that should read {a + b(1 + sqrt(19))/2 : a,b \in Z} or
> equivalently, R := { a + b sqrt(19) : a,b \in (Z + 1/2) }. See the
> November 1988 issue of the Monthly for a short, elementary proof that
> the above ring is a PID but not an ED (not just not Euclidean in the
> norm, but that no Euclidean function works).
Further corrections: 1) it should be sqrt(-19) not sqrt(19).
2) {a + b(1 + sqrt(19))/2 : a,b \in Z} and {a+b sqrt(19):a,b \in (Z + 1/2) }
are not the same thing. If I understand the notation correctly 1/2 is in the
latter but not in the former.
--
Bradley W. Brock, Department of Mathematics
Rose-Hulman Institute of Technology | "Resist not evil.... Love your
br...@nextwork.rose-hulman.edu | enemies."--Jesus of Nazareth
David Bradley
>In article <C0r0J...@news.cso.uiuc.edu> dbra...@symcom.math.uiuc.edu
>(David Bradley) writes:
>> For the record, that should read {a + b(1 + sqrt(19))/2 : a,b \in Z} or
>> equivalently, R := { a + b sqrt(19) : a,b \in (Z + 1/2) }. See the
>> November 1988 issue of the Monthly for a short, elementary proof that
>> the above ring is a PID but not an ED (not just not Euclidean in the
>> norm, but that no Euclidean function works).
>
>Further corrections: 1) it should be sqrt(-19) not sqrt(19).
>2) {a + b(1 + sqrt(19))/2 : a,b \in Z} and {a+b sqrt(19):a,b \in (Z + 1/2) }
>are not the same thing. If I understand the notation correctly 1/2 is in the
>latter but not in the former.
Yes, the minus should be there, but 1/2 is in neither set, as far as I
can tell. By Z+1/2, I mean the {x+1/2 | x \in Z}. Let a,b in Z.
Then a+b/2 and b/2 are both in Z+1/2, hence the first set is a subset of
the second. Conversely, if x+1/2, y+1/2 are given with x,y \in Z, let
a=x-y, b=2y+1. Then (x+1/2) + (y+1/2)sqrt = x-y + (1/2)*(2y+1)(1+sqrt)
= a + b(1 + sqrt)/2.
So the second set is a subset of the first.
-D.M. Bradley