Principal Ideal Domain which is Not Euclidean Domain
Xan
I know that there are domains such that are principal ideal domains
but not euclidean domains, but I don't know any explicit description
of anyone of them. I know that this kind of domains is very strange
(the "99%" of principal ideal domains are euclidean domains).
Can anyone say me a domain (explicit description) A such that:
i) A is a principal ideal domain,
ii) A is not a euclidean domain?.
[Definitions:
A domain A is said "principal ideal domain" iff all of its ideals are
principal.
An ideal I is "principal" iff I = {a搾 | c in A}, for some a in A
A domain A is "euclidean" iff there exist an application n:A-{0}---->N
such that: for all a, b in A, a<>0, there are q, r in A such that and
((r = 0) or (n(r)<n(a))) (The application n is said "norm" and
frequently is denoted by ||會|]
dnahlhytbhy
> i) A is a principal ideal domain,
> ii) A is not a euclidean domain?.
i remember someone told me that the set:
{x+y*(1+i*sqrt(19))/2 | x,y in Z}
is a subring of C with the wanted property...
does it ring some bell?
ma...@mimosa.csv.warwick.ac.uk
xa...@start.com.au (Xan) writes:
>Hello everybody,
>
>I know that there are domains such that are principal ideal domains
>but not euclidean domains, but I don't know any explicit description
>of anyone of them. I know that this kind of domains is very strange
>(the "99%" of principal ideal domains are euclidean domains).
As another poster pointed out, Z[(1 + sqrt(-19))/2] is a PID but not
and ED.
According to Stewart and Tall, Algebraic Number Theory, the ring of
integers of Q[sqrt(d)] is not an ED for squarefree d < -11, but for
squarefree d < 0 it is a PID iff d = -1, -2, -3, -7, -11, -19, -43, -67
or -163.
For squarefree d > 0, it is an ED iff d=2,3,5,6,7,11,13,17,19,21,29,33,37,41,
55, or 73. It is a PID also for d=14,22,23,31,38,43,46,47,53, and more.
It is unknown whetehr there are infinitely many positive d for which
this ring is a PID.
I am sceptical about your claim that 99% of PIDs are EDs. What makes
you think that?
Derek Holt.
Paul Pollack
news:67a09600.02040...@posting.google.com...
> Hello everybody,
[ . .. ]
> Can anyone say me a domain (explicit description) A such that:
> i) A is a principal ideal domain,
> ii) A is not a euclidean domain?.
> [Definitions:
> A domain A is said "principal ideal domain" iff all of its ideals are
> principal.
> An ideal I is "principal" iff I = {a搾 | c in A}, for some a in A
> A domain A is "euclidean" iff there exist an application n:A-{0}---->N
> such that: for all a, b in A, a<>0, there are q, r in A such that
[missing?: b = aq+r]
and
> ((r = 0) or (n(r)<n(a))) (The application n is said "norm" and
> frequently is denoted by ||會|]
Let K = Q(sqrt(-19)), and A = Z[(1+sqrt(-19))/2] be its ring of integers.
We can write A = Z[w], where w=(1+sqrt(-19))/2.
The easier part of this is showing A is not a Euclidean domain. Suppose it
were, with Euclidean function n, and let alpha be a nonunit of A-{0} with
n(alpha) minimal. Let b be in R, and choose q, r in A with
b=alpha*q+r,
r=0 or n(r) < n(alpha). Then r is zero or a unit. So b is congruent to 0 or
+/- 1 (the only units) in A.
Hence |A/(alpha)| <= 3. But the size of |A/(alpha)| is given by N(alpha),
where N is the usual norm. Writing alpha = a+b*w, we have N(alpha) =
(a-b/2)^2 +19*b^2/4 >= 4 > 3 as alpha is nonzero and not a unit. This is a
contradiction.
To see A is a PID, one can use standard methods of algebraic number theory
(see, e.g., Robin Chapman's excellent notes at
http://www.maths.ex.ac.uk/~rjc/rjc.html) to show the class group is trivial.
Alternately, one can check that something called the Dedekind-Hasse
criterion is satisfied in this case; a proof along these lines can be found
in Dummit and Foote's _Abstract Algebra_.
HTH,
Paul
Xan
Xan
Wow. I did not know this great results. Well, I heard something about
what Q[sqrt(d)] are PID and what not, but I don't know that there is a
analog result for ED.
> I am sceptical about your claim that 99% of PIDs are EDs. What makes
> you think that?
I recognize that surely I was wrong about this percentage. I thought
it by two reasons: first is because my teacher of Algebra told me it,
and he told me also that the examples of ED that are not PID are
strange. But, now I don't know if I have to still believing him :-).
And the second is because the examples that I saw are always ED and
PID. I recognize that this is two bad (worse?) reasons. But because I
did not find any better reason for the contrary... .
>
> Derek Holt.
Thank you for your interest.
Regards,
Xan.
Xan
> "Xan" <xa...@start.com.au> wrote in message
> news:67a09600.02040...@posting.google.com...
> > Hello everybody,
> [ . .. ]
> > Can anyone say me a domain (explicit description) A such that:
> > i) A is a principal ideal domain,
> > ii) A is not a euclidean domain?.
> [...]
> > [Definitions:
> > A domain A is said "principal ideal domain" iff all of its ideals are
> > principal.
> > An ideal I is "principal" iff I = {a搾 | c in A}, for some a in A
> > A domain A is "euclidean" iff there exist an application n:A-{0}---->N
> > such that: for all a, b in A, a<>0, there are q, r in A such that
>
> [missing?: b = aq+r]
Yes, I missed b = aq+r.
>
> and
> > ((r = 0) or (n(r)<n(a))) (The application n is said "norm" and
> > frequently is denoted by ||會|]
>
> Let K = Q(sqrt(-19)), and A = Z[(1+sqrt(-19))/2] be its ring of integers.
> We can write A = Z[w], where w=(1+sqrt(-19))/2.
>
> The easier part of this is showing A is not a Euclidean domain. Suppose it
> were, with Euclidean function n, and let alpha be a nonunit of A-{0} with
> n(alpha) minimal. Let b be in R, and choose q, r in A with
>
> b=alpha*q+r,
>
> r=0 or n(r) < n(alpha). Then r is zero or a unit.
> So b is congruent to 0 or +/- 1 (the only units) in A.
[missing?: (mod alpha); i.e., b congruent 0 or +/- 1 mod alpha.
Well, I think that you did not missing it, else you supposed it.]
>
> Hence |A/(alpha)| <= 3.
I'm in agreement with you until now.
> But the size of |A/(alpha)| is given by N(alpha),
> where N is the usual norm. Writing alpha = a+b*w, we have N(alpha) =
> (a-b/2)^2 +19*b^2/4 >= 4 > 3 as alpha is nonzero and not a unit. This is a
> contradiction.
I don't know what the size of |A/(alpha)| is given by N(alpha). Why?.
Can you explain me. I'm sure that it's easy, but I don't see. Well, I
thinking in it meanwhile... .
>
> To see A is a PID, one can use standard methods of algebraic number theory
> (see, e.g., Robin Chapman's excellent notes at
> http://www.maths.ex.ac.uk/~rjc/rjc.html) to show the class group is trivial.
> Alternately, one can check that something called the Dedekind-Hasse
> criterion is satisfied in this case; a proof along these lines can be found
> in Dummit and Foote's _Abstract Algebra_.
Thank you. I'll see it, and I'll see it also for find an answer to the
previous problem of N. Overall, I'll see the Robin Chapman's "Notes in
Algebraic Numbers" and "Algebraic Number Theory".
Apart of all of these, can you know any domain A such that A is an ED
and S^(-1)A [S^(-1)A is a fraction ring of A; and I suppose that 0 is
not in S] is not ED (obviously S^(-1)A has to be PID). I think that
this A exists, but I don't know what is it [you can see the article
news:<67a09600.02012...@posting.google.com> and next
articles of the thread].
It's for this reason that I ask for domains which are PID and not ED.
You provide me a domain that is PID and not ED: Z[w] (and Derek Holt
more). So the natural question is:
Is there S, A such that S^(-1)A = Z[w] (or = any PID which is not ED)
and such that A is an ED?.
I'm thinking it, but I don't find any success.
>
> HTH,
> Paul
Thanks in advance,
Xan.
Daniel R. Grayson
xa...@start.com.au (Xan) writes:
> Hello everybody,
>
> I know that there are domains such that are principal ideal domains
> but not euclidean domains, but I don't know any explicit description
> of anyone of them. I know that this kind of domains is very strange
> (the "99%" of principal ideal domains are euclidean domains).
>
>
>
> Can anyone say me a domain (explicit description) A such that:
> i) A is a principal ideal domain,
> ii) A is not a euclidean domain?.
The ring obtained from the polynomial ring Z[t] by inverting t and all
polynomials of the form 1-t^n is an example. (Here Z is the ring of
integers.)
Steven E. Landsburg
> According to Stewart and Tall, Algebraic Number Theory, the ring of
> integers of Q[sqrt(d)] is not an ED for squarefree d < -11, but for
> squarefree d < 0 it is a PID iff d = -1, -2, -3, -7, -11, -19, -43, -67
> or -163.
>
> For squarefree d > 0, it is an ED iff d=2,3,5,6,7,11,13,17,19,21,29,33,37,41,
> 55, or 73. It is a PID also for d=14,22,23,31,38,43,46,47,53, and more.
> It is unknown whetehr there are infinitely many positive d for which
> this ring is a PID.
>
>
Careful. Q[sqrt[14]] is not a euclidean domain in the obvious norm,
but there might still be some other norm in which it *is* euclidean.
The last I looked into it (at least ten years ago), this was an open
question.
The original poster asked for a PID that is not an ED, and the natural
interpretation of "not an ED" is "not an ED in any norm". So I don't
think these examples clearly settle the question.
Steven E. Landsburg
www.landsburg.com/about2.html
--
Paul Pollack
news:a91msi$1br...@biko.cc.rochester.edu...
A few things that might be helpful to mention in this context:
(1) the ring of integers of an imaginary quadratic field is Euclidean iff it
is norm Euclidean:
The main idea of this proof can be found in the proof I sketched for
Z[(1+sqrt(-19))/2] not being Euclidean with respect to any norm. One shows
by that sort of argument that the only possibilities for imaginary quadratic
fields with Euclidean rings of integers are the ones where we already know
the ring of integers to be Euclidean with respect to the usual norm.
(2) In contrast, we have the following result of DA Clark: Q(sqrt(69)) is
not Euclidean with respect to the (absolute value of the) usual norm but
nevertheless is Euclidean. See
http://groups.google.com/groups?hl=en&th=442e5550cd83a3cb&rnum=2
AFAIK the case of Q(sqrt(14)) is still open.
(3) Henri Cohen has mentioned on this newsgroup the following result of HW L
enstra: If K is a number field whose ring of integers has unique
factorization and infinitely many units, then the ring of integers of K is
Euclidean with respect to some norm. (Note that if [K:Q] > 1, then the ring
of integers of K has finitely many units iff K is imaginary quadratic.)
See
http://groups.google.com/groups?selm=1993Jan12.095311.16393%40greco-prog.fr
HTH,
Paul
ma...@mimosa.csv.warwick.ac.uk
Yes, you are quite right. I misread the result in Stewart & Tall.
Q(srqt(14)) is still open.
Derek Holt.
Dik T. Winter
> (3) Henri Cohen has mentioned on this newsgroup the following result of HW L
> enstra: If K is a number field whose ring of integers has unique
> factorization and infinitely many units, then the ring of integers of K is
> Euclidean with respect to some norm. (Note that if [K:Q] > 1, then the ring
> of integers of K has finitely many units iff K is imaginary quadratic.)
[ Under the generalized Riemann hypothesis.]
Which makes the remark by the original poster that non-Euclidean UFD's
are scarce apparently correct, there are only 4! Q[sqrt(d)] with
d = -19, -43, -67 and -163.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Paul Pollack
news:GuEHE...@cwi.nl...
> In article <a92ll7$lq$1...@cronkite.cc.uga.edu> "Paul Pollack"
<pa...@arches.uga.edu> writes:
> > (3) Henri Cohen has mentioned on this newsgroup the following result of
HW L
> > enstra: If K is a number field whose ring of integers has unique
> > factorization and infinitely many units, then the ring of integers of K
is
> > Euclidean with respect to some norm. (Note that if [K:Q] > 1, then the
ring
> > of integers of K has finitely many units iff K is imaginary quadratic.)
>
> [ Under the generalized Riemann hypothesis.]
Ack! Yes, this certainly should have been pointed out.
Thanks for the correction,
Paul
Bill Daly
> ...
> Yes, you are quite right. I misread the result in Stewart & Tall.
> Q(srqt(14)) is still open.
>
> Derek Holt.
There is a paper by Malcolm Harper published in July 2000 proving that
Q(sqrt(14)) is Euclidean, and indeed strongly suggesting that all real
quadratic PIDs are Euclidean.
Regards, Bill
Xan
> xa...@start.com.au (Xan) writes:
> > Can anyone say me a domain (explicit description) A such that:
> > i) A is a principal ideal domain,
> > ii) A is not a euclidean domain?.
>
> The ring obtained from the polynomial ring Z[t] by inverting t and all
> polynomials of the form 1-t^n is an example. (Here Z is the ring of
> integers.)
Sorry for replying you after too much days, but I have net problems.
But, can you explain this with more precission, overall the last example?
Can you give me a proof?.
Thanks,
Xan.
Gerry Myerson
bill...@tradition-ny.com (Bill Daly) wrote:
=> There is a paper by Malcolm Harper published in July 2000 proving that
=> Q(sqrt(14)) is Euclidean, and indeed strongly suggesting that all real
=> quadratic PIDs are Euclidean.
No sign of this paper in Math Reviews, so far as I can tell.
Bill Dubuque
>
> I know that there are domains such that are principal ideal domains
> but not euclidean domains, but I don't know any explicit description
Below is an outline of a proof that Z[w], w = (1 + sqrt(-19))/2,
is a non-Euclidean PID, from George Bergman's web page [1].
[1] http://math.berkeley.edu/~gbergman/grad.hndts/nonEucPID.ps
Notation: \/a/b = sqrt(a)/b, ~x = x bar = complex conjugate of x
Math 250A, G. Bergman, 1995
A principal ideal domain that is not Euclidean
developed as a series of exercises
Let w denote the complex number (1 + \/-19)/2, and R the ring Z[w].
We shall show that R is a principal ideal domain, but not a Euclidean
ring. This is Exercise III.3.8 of Hungerford's Algebra (2nd edition),
but no hints are given there; the proof outlined here was sketched for
me by H. W. Lenstra, Jr.
(1) Verify that w^2 - w + 5 = 0, that R = {m + n a | m, n in Z} =
{m + n ~a | m, n in Z}, where the bar denotes complex conjugation,
and that the map x -> |x|^2 = x ~x is nonnegative integer valued
and respects multiplication.
(2) Deduce that |x|^2 = 1 for all units of R, and using a lower bound
on the absolute value of the imaginary part of any noneal member of R,
conclude that the only units of R are +-1.
(3) Assuming R has a Euclidean function h, let x be a nonzero nonunit
of R minimizing h(x). Show that R/xR consists of the images in this
ring of 0 and the units of R, hence has cardinality at most 3. What
nonzero rings are there of such cardinalities? Show w^2 - w + 5 = 0
has no solution in any of these rings, and deduce a contradiction,
showing that R is not Euclidean.
We shall now show that R is a principal ideal domain. To do this, let
I be any nonzero ideal of R, and x a nonzero element of I of least
absolute value, i.e., minimizing the integer x ~x. We shall prove I = xR.
(Thus, we are using the function x -> x ~x as a substitute for a
Euclidean function, even though it doesn't enjoy all such properties.)
For convenience, let us "normalize" our problem by taking J = x^-1 I.
Thus, J is an R-submodule of C, containing R and having no nonzero element
of absolute value < 1. We shall show from these properties that J - R = {},
i.e., that J = R.
(4) Show that any element of J that has distance less than 1 from some
element of R must belong to R. Deduce that in any element of J - R, the
imaginary part must differ from any integral multiple of \/19/2 by at
least \/3/2. (Suggestion: draw a picture showing the set of complex numbers
which the preceding observation excludes. However, unless you are told the
contrary, this picture does not replace a proof; it is merely to help you
find a proof.)
(5) Deduce that if J - R is nonempty, it must contain an element y with
imaginary part in the range [\/3/2, \/19/2 - \/3/2], and real part in the
range (-1/2, 1/2].
(6) Show that for such a y, the element 2y will have imaginary part too
close to \/19/2 to lie in J - R. Deduce that y = w/2 or - ~w/2, and
hence that w ~w/2 in J.
(7) Compute w ~w/2, and obtain a contradiction. Conclude that R is a
principal ideal domain.
(8) What goes wrong with these arguments if we replace 19 throughout by 17?
By 23?
Xan
> Below is an outline of a proof that Z[w], w = (1 + sqrt(-19))/2,
> is a non-Euclidean PID, from George Bergman's web page [1].
>
> [1] http://math.berkeley.edu/~gbergman/grad.hndts/nonEucPID.ps
>
Thank you very much, Bill. I will see this paper and I will try to
prove it with your indications. If I have any dubt, I will say you it.
Thank you for your interest,
Xan.