Integral Domains, A PID that is not a Euclidean Domain

A PID that is not a Euclidean Domain

A factorization domain need not be a ufd, and a ufd need not be a pid. We demonstrated this in the last section. But is there a pid that is not a euclidean domain? There is, and we'll prove it below. But the proof is quite technical, and assumes some familiarity with lattices in the complex plane. You may want to review those results first.

This theorem isnot used very often, so you can skip it if you wish.

Adjoin the square root of -m to the integers, for m > 3. Does this produce a euclidean domain? The answer seems to be no, as illustrated by m=5. The rectangles grow tall, the central points are too far away from the corners, and the gcd algorithm falls into an infinite loop. But that algorithm was based on a particular metric, the square of the distance from the origin. Perhaps there is a better d(z) function.

Assume the ring is a euclidean domain, hence there is a valid metric d(z), with d(1) = 1. Let w have the smallest metric that is greater than 1. Remember that the elements with metric 1 are the units, and in the complex plane, those units lie on the unit circle. when m = 1 we have the gaussian integers, with four lattice points on the unit circle: ±1 and ±i. But for m > 1, the lattice points on the unit circle, the points satisfying a2+mb2 = 1, are ±1, and that's it. There are only two units, 1 and -1.

Divide any point z by w, and the remainder has metric smaller than d(w). That's how the euclidean function d() is defined. Therefore w goes evenly into z, or the remainder has d() < d(w), and is a unit. Each nonzero remainder mod w defines a different unit. We know there are two units, and zero; but how many remainders are there? If there are more than three, we're in trouble.

Let q = sqrt(-m), and let w = c+dq. Let z be an arbitrary lattice point a+bq. Subtract multiples of w or multiples of wq from z without affecting the remainder. This moves z into the base rectangle spanned by the perpendicular vectors w and wq. Remember that this rectangle may be tilted relative to the coordinate axes. How many lattice points are in this base rectangle? Since the sides of the rectangle have irrational slopes, and the lattice points have irrational y coordinates, it's difficult to keep track of who is inside and who is outside. Let's turn to the concept of area for help.

Assume there are k lattice points in the base rectangle defined by w and wq. Hence there are k lattice points in every copy of this rectangle in the complex plane.

Let s be the square root of m, not to be confused with q, which is the square root of -m. Now each lattice point in the complex plane represents a small rectangle 1 unit wide and s units high, giving an area of s. The rectangle spanned by w has base v, where v = sqrt(c2+md2), and height vs. This gives an area of sv2. Perhaps we can divide these areas to compute k, the number of small rectangles inside the larger rectangle.

Unfortunately the small rectangles do not completely tile the larger rectangle. Some of them poke out the sides, and there are notches in the large rectangle that aren't covered. Still, the books must balance across the entire plane. Step back and look at a large section of the plane. A million times the area of the large rectangle, seeded by w, has to be just about a million times k times the area of the small rectangle associated with each lattice point. Since k is an integer, the equation is precise. Declare the areas equal and write ks = sv2. Hence k = v2 = c2+md2.

Remember that w is not 1 or -1, and m is greater than 3, hence k exceeds 3. There are more than three remainders when z is reduced mod w. Yet these remainders are ±1 and 0, hence we have a contradiction. The ring is not a euclidean domain.

sometimes we adjoin ½+½q to the integers, where q is again the square root of -m. This was described for m = 3, and it generalizes from there. The lattice consists of parallelograms, rather than rectangles, but the proof presented above is still valid.

When m = 3 there are six units in the lattice, 6 points on the unit circle, 6 points with a2+mb2 = 1 (where a and b are either integers or half integers). But for m > 3 we are back to two units, 1 and -1.

Suppose m is at least 15. Set w = ½+½q, and there are 4 remainders mod w. And that's the best we can do. There are more remainders than units, and the ring is not a euclidean domain for any m ≥ 15.

Now for the prize. Set m = 19 and adjoin ½+½q, as described above. This is not a euclidean domain, since m ≥ 15, yet we will show it is a pid.

Given any proper ideal, let x be the element of the ideal, other than 0, that is closest to the origin. Remember that x spans a lattice of parallelograms in the plane. This is the principal ideal generated by x.

Consider any point y, and reduce it mod x, so that y lies in the base parallelogram spanned by x. Remember that the base of this tilted parallelogram runs from the origin to x, and the side, which is not perpendicular to the base, runs from the origin to x×(½+½q). After an appropriate translation, y lies somewhere in this parallelogram.

We know that y might be somewhere in the middle, far from the four corners. That's why the gcd algorithm doesn't work. But if y isn't close to one of the corners, 2y is. Let's show this for all points in the complex plane, so we don't have to worry about lattices.

Pivot the parallelogram about the origin and scale its dimensions, so that its base runs along the x axis from 0 to 1. The slanted side now runs from the origin up to ½+½q, giving a height of approximately 2.179. The y coordinate of the point we call y (ouch, that was painful) is at least 0.866, sqrt(3)/2, else y is less than 1 unit away from one of the two lower corners. At the same time, y is no higher than 2.179-0.866 = 1.313, else y is within one unit of one of the upper corners. Now double y, and its height is trapped between 1.732 and 2.616. It is now close to one of the upper corners of the parallelogram.

Return to our lattice in the complex plane. If y is in the ideal that contains x, either y or 2y lands on one of the corners of the parallelogram whose base is x. Wihtin our ideal, x is closest to the origin, so if y is close to a corner of our parallelogram, but does not land on one of these corners, the difference gives a vector in our ideal that is closer to the origin than x. Therefore either y or 2y lands smack on a corner, and is a multiple of x.

Suppose 2y is a multiple of x, but y is not. Move y to our base parallelogram, and y is the midpoint of a segment that joins the origin to one of the corners. We know that y is not ½x, x being minimal. Suppose y = ½xs, where s is ½+½q. In other words, y is the midpoint of the left side of the parallelogram. multiply y by s-1 and add 3x. The key observation is that s2-s = -5. So y×(s-1) becomes -5/2 times x, and when we add 3x, we get ½x, which contradicts the minimality of x.

Finally, y could be ½x×(s+1), the "center" of the parallelogram. Subtract x, multiply by s, and add 3x. Once again we obtain ½x, which is a contradiction.

The point y, an arbitrary point in our ideal, is generated by x, and the ideal is principal. This ring is a pid, but not a euclidean domain.