I've tried a few different pairs of numbers in $\mathbb{Z}[\sqrt{14}]$ and in each case I've been able to find a remainder for which the absolute value of the norm is suitable for the Euclidean algorithm. But the Tooth Fairy tells me that $\mathbb{Z}[\sqrt{14}]$ is not norm-Euclidean. If not the absolute value of the norm, then what is the Euclidean function for $\mathbb{Z}[\sqrt{14}]$? This riddle has me stumped.
-
$\begingroup$ I don't understand why are you convinced that such an Euclidean function exists. $\endgroup$– CrostulFeb 14, 2015 at 22:30
4 Answers
This ring, as well as all the other number rings that were shown to be Euclidean using analytic techniques, are Euclidean with respect to the minimal Euclidean function $f$, which in your case is defined as follows.
We set $f(r) = 0$ iff $r = 0$.
We set $f(r) = 1$ iff $r$ is a unit, i.e, for elements $\pm (15+4\sqrt{14})^n$.
We set $f(r) = 2$ for all other elements whose residue classes are represented by elements with $f(r) \le 1$. This includes elements of norm $2$ but also (probably) infinitely many prime elements that have the fundamental unit as a primitive root.
We set $f(r) = 3$ for all other elements whose residue classes are represented by elements with $f(r) \le 2$.
Continue this process indefinitely. It can be shown (but only with analytic means so far) that $f$ is a Euclidean function on ${\mathbb Z}[\sqrt{14}]$.
It is straightforward to compute $f(r)$ for a given element; the difficult problem is showing that every element $r$ has a finite value $f(r)$.
Edit. Perhaps "straightforward" is too strong a word. Let me compute the value $f(7+2\sqrt{14})$ for the element $\pi = 7+2\sqrt{14}$ generating the prime ideal of norm $7$.
I first claim that $f(\pi) \ge 3$. In fact, $\pi$ is not a unit, so $f(\pi) \ge 2$. Next, $\varepsilon = 15 + 4 \sqrt{14} \equiv 1 \bmod \pi$ shows that all units are $\equiv \pm 1 \bmod \pi$, so only the residue classes $0$ and $\pm 1$ are covered by elements with $f(r) \le 1$. But this shows that $f(\pi) \ge 3$.
Next I claim that $f(4 + \sqrt{14}) = f(5 + \sqrt{14}) = 2$. The first element has norm $2$, so the claim is trivial. For the second we observe that $\varepsilon \equiv -5 \bmod (5 + \sqrt{14})$, and since $-5$ is a primitive root modulo $11$, all the residue classes of $5 + \sqrt{14}$ are represented by units.
For showing that $f(\pi) \le 3$ I have to represent the residue classes $0$, $\pm 1$, $\pm 2$ and $\pm 3$ modulo $\pi$ by elements $r$ with $f(r) \le 2$. This now follows easily as $-2 \equiv 5 + \sqrt{14} \bmod \pi$ and $-3 \equiv 4 + \sqrt{14} \bmod \pi$.
-
1$\begingroup$ How do you compute $f(r)$ for a given element $r$? $\endgroup$– MarkFeb 22, 2017 at 18:16
It's not the norm function, that much I can tell you for sure.
From an answer to this question Have I found an example of norm-Euclidean failure in $\mathbb Z [\sqrt{14}]$? I have gleaned a pair of numbers that prevent a successful run of the Euclidean algorithm with the absolute value of the norm as the Euclidean function. And it helps that in a comment to yet another question on this topic the answerer gives a specific pair of numbers.
$$\gcd(2, 1 + \sqrt{14}) = 1$$
Now I will work out the specifics of why that specific result can't be obtained by the norm-Euclidean algorithm.
Since $N(1 + \sqrt{14}) = -13$ and $N(2) = 4$, we need to solve $1 + \sqrt{14} = 2q + r$ so that $-4 < N(r) < 4$.
We already know that 2 and $1 + \sqrt{14}$ are coprime, so $r = 0$ is hardly worth mentioning.
The fundamental unit is $\eta = 15 + 4\sqrt{14}$ (note that $N(\eta) = 1$, not $-1$). If $\eta^n = a + b\sqrt{14}$, then it is obvious that $a$ must be odd and $b$ even. But if $2q = c + d\sqrt{14}$ then both $c$ and $d$ are even, and $r = \eta^n$ will not work because we need $b + d = 1$ (though, for what it's worth, $a + c = 1$ is possible).
Let's try now for $N(r) = 2$, which means that $r = \pm(4 \pm \sqrt{14})^n$. If $r = a + b\sqrt{14}$, then $a$ is always even ($n = 0$ doesn't count because that gives us one of the units, which we've already gone over). But $2q = c + d\sqrt{14}$ has $c$ even, and in this case $a + c = 1$ is impossible.
Since $$\left(\frac{14}{3}\right) = -1,$$ 3 is prime in this domain and $N(x) = \pm 3$ is impossible.
Hence the Euclidean algorithm is stymied by this pair of numbers.
I read somewhere that someone has compiled a lot of empirical evidence suggesting that these difficulties can be overcome by "cheating" in $\mathbb Z[\sqrt{14}, \frac{1}{2}]$.
It's not proven, but it does suggest a possible Euclidean function: if the norm is even, then double it. Then we'd have $\tilde N(2) = 8$, and we'd be able to proceed thus: $1 + \sqrt{14} = 2 \times 2 + (-3 + \sqrt{14})$, then $2 = (-3 + \sqrt{14})(-4 - \sqrt{14}) + (4 + \sqrt{14})$ (this still works even though we have to double the norm of $4 + \sqrt{14}$ to 4), and then finally $-3 + \sqrt{14} = (4 + \sqrt{14})(-11 + 4\sqrt{14}) - \eta$. Obtaining a unit as a remainder confirms the two initial numbers are coprime.
But this does not rule out the possibility that someone could find a pair of numbers that similarly stymies this Euclidean function I'm proposing.
The purpose of this community wiki post is to show that $\mathbb Z[\sqrt{14}]$ is does not fail the first step in Motzkin's construction of a Euclidean algorithm, thereby providing some useful background for the other answers.
Every number of even norm is divisible by $4 + \sqrt{14}$, which has a norm of 2.
If $a + b \sqrt{14}$ has even norm and $a$ and $b$ are both even, we can set $$c = \frac{a}{2}, d = \frac{b}{2}.$$ It doesn't matter if $c + d \sqrt{14}$ is itself divisible by $4 + \sqrt{14}$, because 2 is.
Of course $a + b \sqrt{14}$ can still have even norm if $b$ is odd, provided that $a$ is still even. It's only a tiny bit more complicated to show that such a number is also divisible by $4 + \sqrt{14}$. Set $$c = -7b + 2a, d = 2b - \frac{a}{2}$$ and verify that $(4 + \sqrt{14})(c + d \sqrt{14}) = a + b \sqrt{14}$.
Now suppose that $a + b \sqrt{14}$ has odd norm. This means that $a$ must be odd. But if you increment or decrement $a$ by 1, you have a number of even norm which is therefore divisible by $4 + \sqrt{14}$. This means that $4 + \sqrt{14}$ is a universal side divisor in this domain (not everyone likes that terminology, but it seems to be almost standard).
The presence of a universal side divisor means the second subset in Motzkin's construction is non-empty so that Motzkin's construction does not fail at this level. When the second subset is empty, as for example in $\mathcal O_{\mathbb Q(\sqrt{-19})}$, we can conclude that the ring is not a Euclidean domain. In this case the second subset is non-empty. We cannot conclude that $\mathbb Z[\sqrt{14}]$ is Euclidean, but we know that the technique used to prove domains non-Euclidean by failure of Motzkin's construction does not apply to $\mathbb Z[\sqrt{14}]$. It also gives no guidance as to what the Euclidean function might be.
It should be noted, however, that for many pairs of numbers in $\mathbb Z[\sqrt{14}]$ the absolute value of the norm does properly work as a Euclidean function. For example, using the foregoing, it should be a breeze to find $r = 0$ or 1 for $\gcd(4 + \sqrt{14}, a + b \sqrt{14})$. Certain multiples of $4 + \sqrt{14}$ could be problematic, however, as the other answers will elaborate.
-
$\begingroup$ Please give a reference where it is proved that the presence of a universal side divisor implies the domain is Euclidean, $\endgroup$– MalcolmDec 9, 2017 at 13:20
-
1$\begingroup$ @Malcolm Presence of a universal side divisor in a ring together with that ring being a principal ideal domain is enough to prove the domain is Euclidean. This is to be gleaned from any paper that proves the ring of $\mathbb{Q}(\sqrt{-19})$ is not Euclidean; this is gleaned more easily from some papers than others, which holds me back from editing this community wiki answer. $\endgroup$ Dec 9, 2017 at 22:39
-
$\begingroup$ @Mr.Brooks Reference please. The proof at maths.qmul.ac.uk/~raw/MTH5100/PIDnotED.pdf that $\mathcal O_{\mathbb Q(\sqrt{-19})}$ is not Euclidean makes no mention that somehow or other the presence of a side divisor implies the ring is Euclidean. Certainly Motzkin's original proof that $\mathcal O_{\mathbb Q(\sqrt{-19})}$ is not Euclidean contains no such claim. Neither does Samuel's seminal paper. $\endgroup$– MalcolmDec 9, 2017 at 23:26
-
2$\begingroup$ @Malcolm Sounds like something you should add to this community wiki post. I got somewhat more complicated math on my mind today: NFL stats. ;-) $\endgroup$ Dec 10, 2017 at 17:15
-
1$\begingroup$ @Malcolm Thank you very much for your edit. Today I've been dealing with a personal issue I won't burden you with, and I would much rather focus on this than that. Thanks for taking care of this. $\endgroup$ Dec 12, 2017 at 19:42
The Tooth Fairy is wrong.
This is a classic question. Until semi-recently, the euclidian character of this ring was proved conditionally to the generalized Riemann hypothesis, by Clark (and maybe another guy), but in 2004, Harper gave an unconditional proof. See here.
-
$\begingroup$ If you click where it says "Read article [PDF: 223KB]" it should load in your browser. It's a 16-page paper and I just barely understand the first page, but in my skimming ahead I don't see where it says what the Euclidean function is for this domain. $\endgroup$ Feb 15, 2015 at 1:42
-
$\begingroup$ First of all, $\mathbf{Z}[\sqrt{14}]$ is not norm euclidian (easy to check), but is euclidian. Now, what is its euclidian fonction (in the sense of Samuel's second definition) ? Look at proposition 4 of the paper (the classic Motzkin's lemma). (The lemma is btw proved in Samuel's book, that you can easily find...) This lemma states that under certain conditions, a ring is euclidian. You should first look at this proof (in Samuel's book for instance) to see how they construct the euclidian function, to get some intuition. Now, Harper proves a variation of Motzkin's lemma to conclude... $\endgroup$– OlórinFeb 15, 2015 at 10:43
-
$\begingroup$ ... so reading carefully the proof of this variation (plus the use of the sieve method) should allow you to construct the euclidian function. I did it a years ago, and it is ok, just follow linearly arguments, and patch. $\endgroup$– OlórinFeb 15, 2015 at 10:44
-
1$\begingroup$ Another exposition of the proof is given at thales.doa.fmph.uniba.sk/macaj/skola/atc/LutzmannDipl.pdf but the author writes "we are not able to explicitely write down an Euclidean algorithm". But the author does give a Euclidean algorithm for ${\bf Q}(\sqrt{69})$, which is also Euclidean but not norm-Euclidean. $\endgroup$ Feb 15, 2015 at 11:50
-
1$\begingroup$ Your opening sentence is wrong. The Tooth Fairy did not say that $\mathbb Z[\sqrt{14}]$ was not a Euclidean domain. $\endgroup$ Feb 18, 2017 at 15:00