D is Not EuclideanDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/