What is the Euclidean function for $\mathbb{Z}[\sqrt{14}]$?

Solution 1:

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

Solution 2:

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.

Solution 3:

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.

Solution 4:

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.