D is Not Euclidean

Date: 02/20/2003 at 07:34:41
From: Adi
Subject: Euclidean domain

Let a be a negative integer. Show that Z[a^0.5] is a Euclidean 
domain if and only if a = -1 or a = -2.

Date: 02/22/2003 at 09:36:24
From: Doctor Jacques
Subject: Re: Euclidean domain

Hi Adi,

Let D = Z[sqrt(d)] be the domain under consideration.

For convenience, we will write w = sqrt(d); as we are interested in 
d < 0, w is a purely imaginary complex number.  We will write a|b to 
mean that a divides b.

D consists of the complex numbers x + yw, for all integer x, y.

Remember that an integral domain A is Euclidean if there exists a 
function f : A - {0} -> N, such that, for any non-zero a, b in A:

(1) if a | b, then f(a) <= f(b)
(2) there exists q and r in A such that a = bq + r and either r = 0 or
    f(r) < f(b).

We will first prove that D is a Euclidean domain for d = -1 or -2, 
when we take as function f the norm:

  f(x + yw) = N(x + yw) = x^2 - dy^2.

This function is defined for any complex number; in fact:

  f(x + iy) = x^2 + y^2.

It is rather obvious that f(z) is an integer >= 1 for all non-zero z 
in D.

Note also that f(z) = |z|^2, where |z| is the complex modulus 
(absolute value) of z.  This implies the multiplicative property:

  f(z_1*z_2) = f(z_1)*f(z_2)

This should allow you to prove property (1) easily (this is true for 
all negative integers d).

To prove property (2), we rewrite the equation as:

  r/b = (a/b) - q

Because of the particular choice of the function f, f(r) < f(b) is 
equivalent to:

  f(r/b) < 1

    or

  f((a/b) - q) < 1

The ratio a/b can be written as s + tw, where s and t are rational 
numbers (you can check this by rationalizing the denominator).

If s and t are integers, a/b belongs to D, and we set q = a/b and
r = 0.  In this case, property (2) is satisfied.

Assume now that this is not the case.

We must find an element q of D, q = x + yw, such that:

  f((r + sw) - (x + yw)) < 1

which means:

  (r - x)^2 - d*(s - y)^2 < 1

We take x and y as the integers closest to r and s, respectively. 
This implies:

  |r - x| <= 1/2
  |s - y| <= 1/2

This gives

  (r - x)^2 - d*(s - y)^2 <= 1/4 - d/4 <= 3/4 < 1

because -d <= 2, by hypothesis.

There is a geometric interpretation of this.  D can be represented as 
a 2-dimensional lattice in the complex plane, where a fundamental 
region is the rectangle (0, 1, w, 1 + w).

The relation

  f((a/b) - q) < 1

is equivalent to

  |(a/b) - q| < 1

and property (2) will always be satisfied if every element a/b is 
within distance less than 1 of a lattice point, or, equivalently, if 
we can cover the complex plane with open discs of radius 1 centered 
at the lattice points.

If is easy to see that this will be the case if the half-diagonal of 
the fundamental rectangle is < 1, and this corresponds to |d| < 3.

This also proves that, if d <= -3, we cannot use the function f above 
as a Euclidean function.  However, it could still be the case that D 
would be a Euclidean domain, but with a different Euclidean function.

We will now prove that this is not the case.  This is a little more 
complicated, and I'm not sure you are really required to prove it.

We will first assume that d < -3; the case d = -3 will be handled 
separately.

Assume, by contradiction, that d < -3 and there is a Euclidean 
function g (we do NOT assume that g is the norm we used above). We 
keep the notation N(z) to mean |z|^2 :

  N(x + yw) = x^2 - dy^2.

Let us select an element a from D such that N(a) > 1, and g(a) is 
minimal subject to that condition.  We can find such an element 
because g takes only positive integer values.

Consider any element b of D. We have:

  b = aq + r

with r = 0 or g(r) < g(a).

Because of the choice of a, this implies that r = 0 or N(r) = 1.

It is easy to see that the only elements of D with norm 1 are +1 and
-1.  We can therefore conclude that r = 0, 1, or -1.

This means that there are at most three equivalence classes modulo a, 
or that the index in D of the ideal <a> is at most 3.

The ideal <a> (the set of multiples of a) is a sub-lattice generated 
by the vectors a and aw.  The index of that ideal is the ratio of the 
areas of the fundamental regions.

Let a = r + sw.  The basis vectors for <a> are r + sw and rw + sw^2 = 
rw + ds.

If we let v = |w| = sqrt(-d), these vectors can be written as:

  r + isv
  ds + irv

where i is the imaginary unit, and everything else is real.

The area of the fundamental region of <a> is given, by the absolute 
value of the determinant:

  |r  sv| = v(r^2 - ds^2)
  |ds rv|

The area of the fundamental region of D is given by:

  |1  0| = v
  |0  v|

and the index of <a> is therefore (r^2 - ds^2).

Another way to see this is to notice that, if we multiply every 
element of D by a (as complex numbers), the area of the fundamental 
region is multiplied by |a|^2.

Our condition becomes:

  (r^2 - ds^2) <= 3

As d <= -4, it is easily seen that the only solutions are s = 0,
r = (+/-)1, which means that a = +1 or -1, and N(a) = 1.  But this 
contradicts the choice of a, and shows therefore that D is not 
Euclidean.

So far, we have shown:

* D is a Euclidean domain, with the norm as Euclidean function, for
  d = -1 or -2

* These are the only negative d for which D is a Euclidean domain
  with the norm as Euclidean function.

* If d <= -4, D is not Euclidean.

We still have to settle the case D = -3, with a Euclidean function 
other than the norm.

Assume d = -3.

If D is Euclidean, it admits unique factorization.  However, we have 
the two factorizations:

  4 = 2*2 = (1 + w)(1 - w)

These factorizations are irreconcilable, because:

* the factors are not associate: (1+w)/2 and (1-w)/2 do not belong
  to D.

* the factors are irreducible.  As N(2) = 4, any proper factor q of 2
  would have N(q) = 2, and it is easy to see that the equation
      x^2 + 3y^2 = 2
  has no integer solution.

This shows that D does not admit unique factorization, and is 
therefore not Euclidean.

Does this help?   Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/24/2003 at 04:51:14
From: Adi
Subject: Thank you (Euclidean domain)

Thank you very very much.

- Adi

Date: 12/20/2004 at 04:26:22
From: Ahcool
Subject: Re: Quadratic Fields and the Division Algorithm

The reply says that one needs to prove the division algorithm does 
not exist for the norm map. However this is not sufficient since we 
need to prove that such algorithm does not exist for ANY "degree" 
map.

So my question is whether there is any quick way of showing that, 
something like Z [(1+sqrt(-19))/2] is NOT a Euclidean domain? 

This is a typical hard question since this ring is known to be a 
principle ideal domain and hence a unique factorization domain BUT 
NOT a Euclidean domain.

It is relatively easy to show that such a division algorithm does not 
exist for the norm map. But it's hard to prove, however, for ANY map.

Date: 12/20/2004 at 07:33:37
From: Doctor Jacques
Subject: Re: Quadratic Fields and the Division Algorithm

Hi Ahcool,

A partial answer to your question was given in the article:

    http://mathforum.org/library/drmath/view/62284.html

which is referred to in the article you mention. The proof starts at 
the paragraph:

-----
Assume, by contradiction, that d < -3 and there is a Euclidean 
function g (we do NOT assume that g is the norm we used above)....
-----

As explained in that article, we assume that there is a Euclidean 
function g (what you call a "degree" map), but we *do not* assume 
that g is the usual norm. We keep the notation N(x) for the usual 
norm.

The idea of the proof is to pick a non-zero element a such that a is 
not a unit and for which g(a) is minimal (as g takes only positive 
integer values, as any Euclidean function, such an element exists).

We then proceed to show that any element of D is congruent to -1, 0, 
or 1 (mod ) - this is explained in the article. This means that 
there are at most three congruence classes modulo , and therefore 
the index of the ideal  in D is at most 3.

The index of the ideal  is N(a) - the usual norm (NOT g(a)). This 
means that, if a = r + s*sqrt(d), we have:

  N(a) = r^2 - d*b^2 <= 3

As d <= -4, or, equivalently, (-d) >= 4 this implies:

  r^2 + 4*b^2 = 3

and the only integer solution is a = (+/-) 1, which means that a is a 
unit, and this contradicts our choice of a.

The above proof only applies to rings of the form Z(sqrt(d)). If
d = 1 (mod 4) the ring D of integers of Q(sqrt(d)) also contains 
other elements; the general element of D is of the form:

  R/2 + (S/2)*sqrt(d)

where R and S are integers, both odd or both even. In that case, the 
discriminant of D is -d (instead of -4d), and the proof must be 
modified. The condition in this case is d < -11 (for d >= -11, the 
usual norm can be used as a Euclidean function).

Assume now that d < -11, and d = -1 (mod 4). Note that this implies
d <= -15. We have:

  N(a) = (R^2)/4 -d*(S^2)/4 <= 3

As -d >= 15, this gives:

  (R^2)/4 + 15*(S^2)/4 <= 3

As 15/4 > 3, we must have S = 0, and R must be even. We have
R^2 <= 12, and therefore R = 2 or -2, and a = 1 or -1. Once again, 
this contradicts the fact that a is not a unit.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 09/13/2004 at 18:48:36
From: Vanyo
Subject: is Z[w], w = (1+sqrt(-7)) / 2 a Euclidean domain

I am trying to prove that Z[w], w = (1+sqrt(-7)) / 2, is a Euclidean
domain.  I get to the point where I want to have that 
|| beta/alpha - q || must be < 1.  But I find that it could also be 1.
Am I wrong or is it just that Z[w] is not Euclidean?

Date: 09/14/2004 at 03:38:44
From: Doctor Jacques
Subject: Re: is Z[w], w = (1+sqrt(-7)) / 2 a Euclidean domain

Hi Vanyo,

The article above refers to the case where w = sqrt(d), for d 
a negative integer.  In this case, we have w = (1+sqrt(-7))/2, 
and the argument must be slightly modified.

It is still true that we must check that every complex number is 
within distance 1 of a lattice point; however, in this case, the 
fundamental domain is a parallelogram, not a rectangle.  This means 
that we must select the lattice point with more care.

We pick an arbitrary complex number x + iy, and we must find a 
suitable lattice point:

  z = r + sw = (r+s/2) + i(s*sqrt(7))/2

It is natural to try to have the real and imaginary parts of
(x + yi - z) as small as possible.

Let us start with the imaginary part, y - s*sqrt(7)/2.  We take s as 
the integer closest to 2y/sqrt(7).  This will give us:

  | 2y/sqrt(7) - s | <= 1/2
  | y - s*sqrt(7)/2 | <= sqrt(7)/4

Now, we turn to the real part, x - r - s/2.  If we select r as the 
integer closest to (x - s/2), we will have:

  | x - r - s/2 | <= 1/2

Putting both relations together, we get:

  N(x + yi - z) = (x - r - s/2)^2 + (y - s*sqrt(7)/2)^2
                <= 1/4 + 7/16
                < 1

as desired.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/