# Ring of integers is a PID but not a Euclidean domain

I have noticed that to prove fields like $$\mathbb{Q}(i)$$ and $$\mathbb{Q}(e^{\frac{2\pi i}{3}})$$ have class number one, we show they are Euclidean domains by tessellating the complex plane with the points $$a+bv : a, b \in \mathbb{Z}$$, where $$1, v$$ is an integral basis. Then any $$c +dv$$ in the field has distance $$\leq 1$$ from some lattice point. On the other hand a similar geometric argument fails with the field $$\mathbb{Q}(\sqrt{-5})$$, which does not have class number one.

Any ring of integers of a finite extension of $$\mathbb{Q}$$ is a Dedekind domain, hence a PID if and only if a UFD. But can such a ring be a PID but fail to be a Euclidean domain?

• Jul 6 '14 at 14:05

Here's what I think is a nice way to find a few PIDs that aren't Euclidean. It's not quite elementary, but if you know a bit about number fields I think it's a lot easier and nicer than the normal drudge.

Let $K=\mathbb{Q}(\sqrt{-d})$ for $d>3$ squarefree, with ring of integers $\mathcal{O}_K$. Then the only units in $\mathcal{O}_K$ are $\pm1$.

Suppose $\mathcal{O}_K$ is Euclidean with Euclidean function $\varphi$. Then take $x \in \mathcal{O}_K\setminus\{0,\pm1\}$ with $\varphi(x)$ minimal. By definition, any element of $\mathcal{O}_K$ can be written in the form $px+r$ where $\varphi(r) < \varphi(x)$, so it must be that $r \in \{0,\pm1\}$, i.e. $|\mathcal{O}_K/(x)|$ is $2$ or $3$. In other words $\mathcal{O}_K$ has a principal ideal of norm $2$ or $3$.

So now we know that if $K = \mathbb{Q}(\sqrt{-d})$ has class number one, where $d>3$ is squarefree*, $K$ is a non-Euclidean PID if there are no elements in $\mathcal{O}_K$ of norm $\pm2$ or $\pm3$. As $K$ is a PID (and degree $2$ over $\mathbb{Q}$), this is equivalent to saying that $2$ and $3$ are inert. To find some examples then:

If $d = 3\pmod{4}$, $\mathcal{O}_K = \mathbb{Z}[\frac{1+\sqrt{-d}}{2}]$, the minimal polynomial of $\frac{1+\sqrt{-d}}{2}$ over $\mathbb{Q}$ is $f_d(X)=X^2-X+\frac{1+d}{4}$. Applying Dedekind's criterion gives that $d$ works provided that $f_d(X)$ is irreducible $\pmod{2}$ and $\pmod{3}$. This then gives that $d = 19$ works (which is the usual example), but also shows that $d = 43,67$ or $163$ work as well (I think!).

*It can be shown that this implies $d \in \{1,2,3,7,11,19,43,67,163\}$

Yes, below is a sketch a proof that $\rm\: \mathbb Z[w],\ w = (1 + \sqrt{-19})/2\$ is a non-Euclidean PID, based on remarks of Hendrik W. Lenstra.

The standard proof usually employs the Dedekind-Hasse criterion to prove it is a PID, and the universal side divisor criterion to prove it is not Euclidean, e.g. see Dummit and Foote. The latter 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\ w\ :\ m, n \in \mathbb Z\} = \{m + n\ \bar w\ :\ 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$?

• I didn't downvote this myself, but I imagine it was because this answer is word for word copy and paste from your answer here: math.stackexchange.com/questions/23844/… and possibly someone thought it would have been better as a link in a comment. Jul 6 '14 at 17:17
• @Tom I was in the process of revising this before being pulled from my keyboard (holiday here in USA). If you look closer you'll see that both links have changed to newer, better expositions, and ditto for linked, content, etc. Jul 6 '14 at 18:06
• @Tom Believe it or not, I have not too infrequently received (harsh) complaints for posting too many/complex links. That, combined with the fact that many readers seem to not chase links and waste time duplicating the link, means that I have given up my old strategy of heavily linking things, promoting abstract duplicates, etc. That would work well if duplicate questions were merged, but this rarely occurs. So now, I try to continually improve my posts in each new iteration. Jul 6 '14 at 18:07
– D_S
Jul 6 '14 at 20:18

$\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is not a E.D..

Supose that $R=\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a E.D.. Let $N(\cdot)$ be the Euclidean norm. Recall that the set of all unit in $R$ is $\{\pm 1\}$. Take an element $a\notin \{0, \pm 1\}$ such that $N(a)$ is minimal. For any $b\in R$, we have $b=aq+r$, where $r=0$ or $N(r)<N(a)$. By the minimality of $N(a)$, we have $r\in \{0, \pm 1\}$. Thus, $R/\langle a\rangle\cong \Bbb{Z}_2$ or $\Bbb{Z}_3$.

On the other hand, the polynomial $x^2+x+5$ has root in $R$ because $x^2+x+5=[x-(-\frac{1+\sqrt{-19}}{2})][x-(-1+\frac{1+\sqrt{-19}}{2})]$. So $x^2+x+5$ has root in $R/\langle a\rangle$. But $x^2+x+5$ has no root in $\Bbb{Z}_2$ nor in $\Bbb{Z}_3$. Hence, $R/\langle a\rangle$ can't be isomorphic to $\Bbb{Z}_2$ nor $\Bbb{Z}_3$.

$\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a P.I.D. (See Artin's Algebra ch.13)

Since $-19\equiv 1\pmod{4}$, we compute $\mu=\sqrt{\frac{|-19|}{2}}\approx 2.52$ and the prime integers don't exceed $\mu$ is $2$. Note that $x^2-x+\frac{1-(-19)}{4}=x^2-x+5$ is irreducible in $\Bbb{F}_2[x]$. Hence, $\langle 2\rangle$ is a prime ideal in $\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$. Since $\langle 2\rangle$ is principal, the ideal class of $\langle 2\rangle$ in the class group is the identity. Thus, the ideal class group is trivial and $\Bbb{Z}[\frac{1+\sqrt{-19}}{2}]$ is a P.I.D..

Lemma 1. The ideal class group $\mathcal{C}$ is generated by the classes of prime ideal $P$ whose norms are prime integers $p\leq \mu$

Lemma 2. If $d\equiv 1\pmod{4}$, then $\langle p\rangle$ is a prime ideal in $\Bbb{Z}[\frac{1+\sqrt{d}}{2}]$ if and only if the polynomial $x^2-x+\frac{1-d}{4}$ is irreducible in $\Bbb{F}_p[x]$. $$\begin{array}{rcl} \Bbb{Z}[x] & \stackrel{\langle p\rangle}{\longrightarrow} & \Bbb{F}_p[x] \\ /\langle x^2-x+\frac{1-d}{4}\rangle \downarrow& & \downarrow /\langle x^2-x+\frac{1-d}{4}\rangle \\ \Bbb{Z}[\frac{1+\sqrt{d}}{2}] & \stackrel{\langle p\rangle}{\longrightarrow} & R' \end{array}$$