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?

Solution 1:

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\}$

Solution 2:

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$?

Solution 3:

$\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} $$