# The ring $\Bbb Z\left [\frac{-1+\sqrt{-19}}{2}\right ]$ is not a 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 a 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 a Euclidean Domain.

Everything hints to an argument by contradiction: let $(A, d)$ be a 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?

## 5 Answers

You might find enlightening the following sketched proof that $$\, \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 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 $$\,w\,$$ denote the complex number $$\,(1 + \sqrt{-19})/2,\,$$ and $$\,R\,$$ the ring $$\, \Bbb 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 (Bergman) by H. W. Lenstra, Jr.

$$(1)\$$ Verify that $$\, w^2\! - w + 5 = 0,\,$$ that $$\,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 $$\,x \to |x|^2 = x \bar 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 nonreal member of $$\,R,\,$$ conclude that the only units of $$\,R\,$$ are $$\pm 1.$$

$$(3)\$$ Assuming $$\,R\,$$ has a Euclidean function $$\,h,\,$$ let $$\,x\ne 0\,$$ be a 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 \bar x.\,$$ We shall prove $$\,I = xR.\,$$ (Thus, we are using the function $$\,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 $$\,J = x^{-1}I.\,$$ Thus, $$\,J\,$$ is an $$\,R$$-submodule of $$\,\mathbb C,\,$$ containing $$\,R\,$$ and having no nonzero element of absolute value $$< 1.\,$$ We shall show from these properties that $$\, J - R = \emptyset,\,$$ 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 $$\,\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 $$\, J - R\,$$ is nonempty, it must contain an element $$\,y\,$$ with imaginary part in the range $$\,[\sqrt{3}/2,\,\sqrt{19}/2 - \sqrt{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 $$\,\sqrt{19}/2\,$$ to lie in $$\, J - R.\,$$ Deduce that $$\,y = w/2\,$$ or $$\,-\bar w/2,\,$$ and hence that $$\,w\,\bar w/2\,\in J.$$

$$(7)\$$ Compute $$\, w\,\bar 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$$?

• The link to Dedekind-Hasse criterion points to this answer and should be corrected. +1 for an otherwise great answer. Jul 5 '16 at 16:02
• @BillDubuque "Thus, we are using the function $x\rightarrow x\bar x$ as a substitute for a Euclidean function, even though it doesn't enjoy all such properties." What other properties does Euclidean function enjoy? Also how to do step $4$?
– Mr.
Jan 6 '17 at 2:29
• A simlar but slightly different approach can be found in the first section of these notes, for the most part in the exercises. Apr 6 '19 at 14:34
• @nolemon The argument in $(3)$ chooses a nonunit $\,x\neq 0\,$ that is minimal wrt to the purported Euclidean norm $\,h,\,$ i.e. $x$ has the next smallest E-norm value besides units (value $=1$). So the only possible remainders mod $x$ are $0$ or units $= \pm1$ so $\,R/x\,$ has cardinalty $2$ or $3$, contra $\,\Bbb Z/2\,$ and $\Bbb Z/3\,$ are not images of $R$ since $\,x^2-x+5\,$ has no roots in either. Apr 26 at 1:10
• D&F use the field norm to show that the only possible side divisors are $\,x = \pm2,\,\pm 3.\,$ Yes, hom images preserve roots, applying a hom $h$ to \,$w^2-w+5 = 0\,$ yields $\,(h(w))^2-h(w)+h(5) = 0\,$ so $h(w)$ remains a root in $h(R)\ \$ Apr 26 at 1:39

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 :) 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. Feb 26 '11 at 16:19

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. Feb 26 '11 at 14:22
• @Jacopo: oh. That's a completely different question. Then in fact Zhen Lin gave you the correct hint. Feb 26 '11 at 15:46

I have a solution that seems different from the ones as above, I'm no too sure about whether is correct or not.

We shall show that for any $$a \neq \pm 1 \in A$$, we have $$|A/(a)| > 3$$.

Lemma: Let $$R = \mathbb{Z}[\beta]$$, where $$\beta \in \mathbb{C}-\mathbb{R}$$ and $$|\beta| > 1$$. Then fix $$a \in R$$, and consider the parallelipid $$P$$ spanned by $$0, a, \beta a, a + \beta \alpha$$, and let $$b = |\partial P \cap R|$$ (the boundary of $$P$$ interesected with $$R$$) and $$i = |P^0 \cap R|$$ (the interior of $$P$$ intersected with $$R$$. Then $$|R/(a)| = \frac{b}{2} - 1 + i$$

Proof: Let $$r_1$$ be the closed line segment joining $$0$$ and $$a$$, and $$r_2$$ be the half-open line segment joining $$0$$ and $$\beta a$$. Then a simple double counting shows $$\frac{b}{2} - 1 = |(r_1 \cup r_2) \cap R|$$. It's not hard to see for any $$c \in R$$, we can find one and only one $$b \in r_1 \cup r_2 \cup P^0$$ such that $$b-c \in (a)$$ (the proof is geometrically obvious but annoying to write), and thus $$|R/(a)| = \frac{b}{2} - 1 + i$$. $$\square$$

Now, returning to the main problem, let $$a = m + n \alpha$$. Then $$\alpha a = -10n + \alpha(m+2)$$. Consider the $$\mathbb{R}$$-linear (not $$\mathbb{C}$$-linear) transformation $$T$$ from $$\mathbb{C}$$ to $$\mathbb{R}^2$$ sending $$\alpha$$ to $$(0,1)$$ and $$1$$ to $$(1,0)$$. Then $$T(a) = (m,n)$$ and $$T(\alpha a) = (-10n, m+2)$$. Also, note that $$T(A) = \{ T(r) | r \in A \} = \mathbb{Z}^2$$.

By lemma (note that $$|\partial (TP) \cap TR| = |\partial P \cap R|$$ and $$|(TP)^0 \cap TR| = |P^0 \cap R|$$), let $$b$$ be the lattice points on the boundary of the parallelipid $$P'$$ spanned by $$(0,0), (m,n), (-10n, m+2), (-10n+m, m+n+2)$$, and $$i$$ be the number of interior lattice points of $$P'$$.

Then $$|A/(a)| = \frac{b}{2}-1 + i = Area(P') = \det \begin{pmatrix} m & n \\ -10n & m+2 \end{pmatrix} = m^2 + 2m + 10n^2$$ (where we have used Pick's theorerm for the second equality). Now, $$|A/(a)| > 3 \Rightarrow (m+1)^2 + 10n^2 > 4$$, which is true whenever $$n = 0, m \not \in \{0, 1, -1, -2 \}$$ or $$n \neq 0$$.

Thus the only case that's remaining to be checked is $$(m,n) = (2,0)$$, or $$a = 2$$. But then $$A/(2)$$ contains $$5$$ elements - viz $$0, \alpha, 2 \alpha, 1, 1 + \alpha$$, which is greater than $$3$$, so done !

Here is a solution that may turn out to be helpful: http://www.maths.qmul.ac.uk/~raw/MTH5100/PIDnotED.pdf