10
$\begingroup$

Based on the proof that $\mathcal O_{\mathbb Q (\sqrt{-19})}$ is not Euclidean because it lacks universal side divisors, I have convinced myself that $\mathbb Z [\sqrt{14}]$ is Euclidean because it has as universal side divisors numbers with a norm of $2$, e.g., $4 + \sqrt{14}$ (though I have not proved this rigorously). Clearly an example of norm-Euclidean failure must involve numbers with odd norms.

I've been looking at $\gcd(3, 7 + 2 \sqrt{14})$. There is a question that's coming up as "similar" that gives $\gcd(3, 3 + \sqrt{14})$ as a possible example of norm-Euclidean failure (for all I know this question might wind up being closed as a duplicate of that one). I have done calculations with both pairs, and I have found (unless I've made errors), that in $3 = q(7 + 2 \sqrt{14}) + r$ results in larger $|N(r)|$ than $3 = q(3 + \sqrt{14}) + r$.

But even if I have made no mistakes of arithmetic, this still does not prove either of these examples leads to norm-Euclidean failure.


July 27, 2016: Just so that hopefully no one can say I have undefined terms: by "an example of norm-Euclidean failure" in this domain I mean a pair of numbers $a, b$ in this domain such that it is impossible to find suitable numbers $q, r$ in this domain to satisfy $a = qb + r$ with $|N(a)| > |N(b)|$ and $|N(b)| > |N(r)|$.

$\endgroup$
  • $\begingroup$ alpha.math.uga.edu/~pete/Clark_Jagy_11_13_2013.pdf $\endgroup$ – Will Jagy Jul 11 '16 at 23:05
  • $\begingroup$ mostly Theorem 5.9 $\endgroup$ – Will Jagy Jul 11 '16 at 23:09
  • $\begingroup$ I've read Theorem 5.9 but it doesn't make any sense to me. Looks like I need to read everything that precedes it. $\endgroup$ – Mr. Brooks Jul 13 '16 at 21:21
  • $\begingroup$ What exactly do you mean by "norm-Euclidean failure"? $\endgroup$ – Alex M. Jul 26 '16 at 21:54
  • 2
    $\begingroup$ @AlexM. I'm pretty sure he means a pair of numbers such that the Euclidean algorithm using the norm function fails to deliver the GCD of those two numbers. For example, $$\frac{3}{2} + \frac{\sqrt{-19}}{2}$$ and 10 in $\mathcal{O}_{\mathbb{Q}(\sqrt{-19})}$. Of course complex rings are much easier than real rings in so many different regards. $\endgroup$ – Robert Soupe Jul 27 '16 at 3:26
11
+500
$\begingroup$

Although $\mathbb{Z}[\sqrt{14}]$ is not norm-Euclidean, you haven't proved it yet. At least, you can successfully get through one step of the Euclidean algorithm:

$$3 = (7+2\sqrt{14})(-2+\sqrt{14}) + (-11 - 3\sqrt{14}),$$

and the absolute value of the norm of $-11 - 3\sqrt{14}$ is $5$, which is less than the absolute value of the norm of $7+2\sqrt{14}$, which is 7.

ADDED: Mr. Brooks: $(3,3+\sqrt{14})$ certainly does not work. In fact, you can write $$3 = (3 + \sqrt{14})(-4) + (15 + 4\sqrt{14})$$ and note that $15 + 4\sqrt{14}$ is a unit so we've proven $3$ and $3+\sqrt{14}$ are relatively prime.

By the way, here is the trick to use the norm to carry out a Euclidean algorithm:

Goal: Given $a$ and $b$ in the ring of integers, find $q$ in the ring of integers such that $$a = bq + r$$ and $N(r) < N(b)$.

Strategy: Take the quotient $a/b$, which is in the number field, and try to find some integral $q$ such that $N(a/b -q) < 1$. Then set $r = a - bq$ and observe that $$N(r) = N(a - bq) = N(a/b - q)N(b) < N(b).$$

In fact, this leads to a general computational method for trying to prove a number ring is a norm-Euclidean domain: Given a field $K$ and ring of integers $\mathcal{O}$, try to prove that:

For all $x \in K$, there exists $y \in \mathcal{O}$ such that $N(x-y) < 1$.

This gives a geometric approach to the problem.

There are several nice papers by J.P. Cerri which discuss norm-Euclidean domains. I really recommend them if you are interested in this subject (in addition of course to the survey papers by Lenstra and by Lemmermeyer).

PROOF that $\mathbb{Z}[\sqrt{14}]$ is not a norm-Euclidean domain: I'm not sure what the standard proof is, but here is one that works:

Consider $x = (1+\sqrt{14})/2$. We want to show that for any $y \in \mathbb{Z}[\sqrt{14}]$ that $N(x+y) > 1$. Write $y = a + b\sqrt{14}$, with $a$ and $b$ integers. Then suppose $$N(x+y) = \left|\left(a+\frac12\right)^2 - 14\left(b+\frac12\right)^2\right| = \left|a^2 + a - 14b^2 - 14b -\frac{13}{4}\right| < 1.$$ Since $a$ and $b$ are integers, the only possibilities are $$a^2 + a - 14b^2 - 14b = 3 \text{ or } 4.$$ We can rule out $3$ because the left hand side is always even. To rule out 4, we observe that $a^2 + a$ can only equal 0, 2, 6 or 12 modulo 14, and in particular never equals 4 modulo 14. So we have a contradiction, proving that $\mathbb{Z}[\sqrt{14}]$ is not norm-Euclidean.

There is another proof at PlanetMath.

$\endgroup$
  • $\begingroup$ Thank you very much. This was right in front of me but I made a silly arithmetic mistake with $N(-11 - 3 \sqrt{14})$ (I multiplied by $3$ instead of by $9$). $\endgroup$ – Mr. Brooks Jul 26 '16 at 21:46

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.