# A ring that is not an Euclidean domain

Let $\alpha = \frac{1+\sqrt{-19}}{2}$. Let $A = \mathbb Z[\alpha]$. Let's assume that we know that its invertibles are $\{1,-1\}$. During an exercise we proved that:

Lemma: If $(D,g)$ is an Euclidean Domain such that its invertibles are $\{1,-1\}$, and $x$ is an element of minimal degree among the elements that are not invertible, then $D/(x)$ is isomorphic to $\mathbb Z/2\mathbb Z$ or $\mathbb Z/3\mathbb Z$.

Now the exercise asks:

Prove that $A$ is not an Euclidean Domain.

Everything hints to an argument by contradiction: were $(A, d)$ be an ED and $x$ an element of minimal degree among the non invertibles we'd like to show that $A/(x)$ is not isomorphic to $\mathbb Z/2\mathbb Z$ or $\mathbb Z/3\mathbb Z$.

How do we do that? My problem is that, since I don't know what this degree function looks like, I don't know how to choose this $x$!

I know that the elements of $A/(x)$ are of the form $a+(x)$, with $a$ of degree less than $x$ or zero. By minimality of $x$ this means that $a\in \{0, 1, -1\}$. Now I'm lost: how do we derive a contradiction from this?

-

What a coincidence, this was a recent homework problem for me as well. Here's an additional hint: Show that $X^2 + X + 5$ does not split over $\mathbb{F}_2$ or $\mathbb{F}_3$. Deduce a contradiction to the minimality of the degree of $x$.

-
$X^2-X+5$ doesn't split in $\mathbb F_{2}[X]$ or $\mathbb F_{3}[X]$ because it has no roots in those fields. But it does split in $A[X]$, thus in $A/(x)[X]$. Contradiction! I hope :) –  Jacopo Notarstefano Feb 26 '11 at 15:56
@Jacopo: Yes, something like that. Essentially what happens is that you are forced to conclude that $A/(x)$ is the trivial ring, so $x$ must be a unit, but we already excluded all the units. –  Zhen Lin Feb 26 '11 at 16:19

Perhaps you will find enlightening the following sketched proof that $\rm\: \mathbb Z[w],\ w = (1 + \sqrt{-19})/2\$ is a non-Euclidean PID -- based on a sketch by the eminent number-theorist Hendrik W. Lenstra.

Note that the the proof in Dummit & Foote, uses the Dedekind-Hasse criterion to prove it is a PID, and the universal side divisor criterion to prove it is not Euclidean, is probably the simplest known. The so-called universal side divisor criterion is essentially a special case of research of Lenstra, Motzkin, Samuel, Williams et al. that applies in much wider generality to Euclidean domains. You can obtain a deeper understanding of Euclidean domains from the excellent surveys by Lenstra in Mathematical Intelligencer 1979/1980 (Euclidean Number Fields 1,2,3) and Lemmermeyer's superb survey The Euclidean algorithm in algebraic number fields. Below is said sketched proof of Lenstra, excerpted from George Bergman's web page.

Let $\rm\:w\:$ denote the complex number $\rm\ (1 + \sqrt{-19}/2\:,\:$ and $\rm\:R\:$ the ring $\rm\: Z[w]\:.$ We shall show that $\rm\: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 (Bergman) by H. W. Lenstra, Jr.

$(1)\$ Verify that $\rm\ w^2\! - w + 5 = 0,\:$ that $\rm\ R = \{m + n\ a\ :\ m, n \in \mathbb Z\} = \{m + n\ \bar a\ :\ m, n \in \mathbb Z\},\:$ where the bar denotes complex conjugation, and that the map $\rm\ x \to |x|^2 = x \bar x\$ is nonnegative integer-valued and respects multiplication.

$(2)\$ Deduce that $\rm\ |x|^2 = 1\$ for all units of $\rm\:R\:,\:$ and using a lower bound on the absolute value of the imaginary part of any noneal member of $\rm\:R\:,\:$ conclude that the only units of $\rm\:R\:$ are $\pm 1\:.$

$(3)\$ Assuming $\rm\:R\:$ has a Euclidean function $\rm\:h,\:$ let $\rm\:x\ne 0\:$ be a nonunit of $\rm\,R\,$ minimizing $\rm\: h(x).\:$ Show that $\rm\:R/xR\:$ consists of the images in this ring of $\:0\:$ and the units of $\rm\:R\:,\:$ hence has cardinality at most $3$. What nonzero rings are there of such cardinalities? Show $\rm\ 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 $\rm\:R\:$ is a principal ideal domain. To do this, let $\rm\:I\:$ be any nonzero ideal of $\rm\:R\:,\:$ and $\rm\:x\:$ a nonzero element of $\rm\:I\:$ of least absolute value, i.e., minimizing the integer $\rm\ x \bar x\:.\:$ We shall prove $\rm\ I = x\:R\:.\:$ (Thus, we are using the function $\rm\ x \to x \bar 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 $\rm\ J = x^{-1}\ I\:.\:$ Thus, $\rm\:J\:$ is an $\rm\:R$-submodule of $\:\mathbb C\:,\:$ containing $\rm\:R\:$ and having no nonzero element of absolute value $< 1\:.\:$ We shall show from these properties that $\rm\: J - R = \emptyset\:,\:$ i.e., that $\rm\ J = R\:.$

$(4)\$ Show that any element of $\rm\:J\:$ that has distance less than $1$ from some element of $\rm\:R\:$ must belong to $\rm\:R\:.\:$ Deduce that in any element of $\rm\ J - R\:,\:$ the imaginary part must differ from any integral multiple of $\:\sqrt{19}/2\:$ by at least $\:\sqrt{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 $\rm\: J - R\:$ is nonempty, it must contain an element $\rm\:y\:$ with imaginary part in the range $\rm\ [\sqrt{3}/2,\ \sqrt{19}/2 - \sqrt{3}/2]\:,\:$ and real part in the range $\rm\: (-1/2,\ 1/2]\:.$

$(6)\$ Show that for such a $\rm\: y\:,\:$ the element $\rm\: 2\:y\:$ will have imaginary part too close to $\:\sqrt{19}/2\:$ to lie in $\rm\: J - R\:.\:$ Deduce that $\rm\ y = w/2\$ or $\rm- \bar w/2\:,\:$ and hence that $\rm\ w\ \bar w/2\ \in J\:.$

$(7)\$ Compute $\rm\: w\ \bar w/2\:,\:$ and obtain a contradiction. Conclude that $\rm\:R\:$ is a principal ideal domain.

$(8)\$ What goes wrong with these arguments if we replace $19$ throughout by $17$? By $23$?

-

You don't need to know what the degree function looks like to choose $x$: you already chose it when you said "$x$ an element of minimal degree." (By the well-ordering principle, the set of degrees of nonzero, non-unital elements has a least element.)

-
I guess I should have phrased my question better. I do understand that this $x$, given a degree function, exists. I'll try to edit my question to better reflect what I was trying to say. –  Jacopo Notarstefano Feb 26 '11 at 14:22
@Jacopo: oh. That's a completely different question. Then in fact Zhen Lin gave you the correct hint. –  Qiaochu Yuan Feb 26 '11 at 15:46