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?


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

  • $\begingroup$ $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 :) $\endgroup$ – Jacopo Notarstefano Feb 26 '11 at 15:56
  • $\begingroup$ @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. $\endgroup$ – Zhen Lin Feb 26 '11 at 16:19

You might 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 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 nonreal 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 $\rm\,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$?

  • $\begingroup$ The link to Dedekind-Hasse criterion points to this answer and should be corrected. +1 for an otherwise great answer. $\endgroup$ – Paramanand Singh Jul 5 '16 at 16:02
  • $\begingroup$ @ParamanandSingh The link has been updated, thanks. $\endgroup$ – Bill Dubuque Jul 5 '16 at 16:05
  • $\begingroup$ @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$? $\endgroup$ – 1.. Jan 6 '17 at 2:29
  • $\begingroup$ A simlar but slightly different approach can be found in the first section of these notes, for the most part in the exercises. $\endgroup$ – Servaes Apr 6 '19 at 14:34
  • $\begingroup$ @Servaes Stevenhagen was a student of Lenstra - which likely explains the similarity. $\endgroup$ – Bill Dubuque Apr 6 '19 at 15:15

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.)

  • $\begingroup$ 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. $\endgroup$ – Jacopo Notarstefano Feb 26 '11 at 14:22
  • $\begingroup$ @Jacopo: oh. That's a completely different question. Then in fact Zhen Lin gave you the correct hint. $\endgroup$ – Qiaochu Yuan 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.