16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand why are you convinced that such an Euclidean function exists. $\endgroup$ – Crostul Feb 14 '15 at 22:30
18
+250
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ How do you compute $f(r)$ for a given element $r$? $\endgroup$ – Mark Feb 22 '17 at 18:16
8
+500
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Please give a reference where it is proved that the presence of a universal side divisor implies the domain is Euclidean, $\endgroup$ – Malcolm Dec 9 '17 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$ – Mr. Brooks Dec 9 '17 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$ – Malcolm Dec 9 '17 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$ – Robert Soupe Dec 10 '17 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$ – Robert Soupe Dec 12 '17 at 19:42
6
$\begingroup$

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.

$\endgroup$
  • $\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$ – Mr. Brooks Feb 15 '15 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órin Feb 15 '15 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órin Feb 15 '15 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$ – Gerry Myerson Feb 15 '15 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$ – Thomas Andrews Feb 18 '17 at 15:00

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.