Euclidean but not Norm-Euclidean Quadratic rings

Euclidean Algorithm: If given any two elements $a, b$ of a ring $R$ , we have quotients and remainders $q, r \in R$ such that

$a=bq+r$ ,

where $r$ is strictly “smaller'” than $b$ , we say that the ring is Euclidean.

For instance, for integers $\mathbb Z$ the measure of smallness is the size (absolute value as real number) and we have $0 \le |r| < |b|$ . How do we measure the size in other rings?

For Gaussian integers, $\mathbb Z[i]$ , we can measure the size by the absolute value (as a complex number).

More generally for

$d=-1,-2,-3,-7,-11, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 ,$

the rings of integers of $\mathbb Q(\sqrt{d})$ are Euclidean where the measure of the size for an element $X+Y\sqrt d$ is the absolute values of the norm $|X^2-dY^2|.$ Recall that the ring of integers is given by $\mathbb Z \oplus \mathbb Z[\sqrt{d}]$ if $d= 2, 3 \mod 4$ and $\mathbb Z \oplus \mathbb Z[\frac{1+\sqrt{d}}{2}]$ if $d =1 \mod 4$ respectively.

Another way to think of euclidean algorithm: In each of the above rings, given an arbitrary element in the field $x$ , we can find an integral approximation $y$ such that $|\text{Norm}(x-y)| <1$ . Taking $x = a/b, y=q$ , this corresponds to $|\text{Norm}(r/b)| <1$ that is $|\text{Norm}(r)| < |\text{Norm}(b)|$ .

Euclidean rings are nice because of the gcd algorithm and we see that every ideal is a principal (generated by a single element, if there are two elements take their gcd!)

So how many quadratic rings are euclidean and how many of them are euclidean with norm as the measure of smallness? What are the Euclidean rings that are not norm-Euclidean?

Chatland, Davenpport, and independently Inkeri showed that the above list are the only rings of quadratic integers whcih are norm-Euclidean. For imaginary fields, there are not other Euclidean rings. But what about real quadratic fields, are there any $d>0$ for which can we find Euclidean functions that are not norms?

If it’s euclidean , it’s a PID and hence have class number 1. So if we just focus on class number 1 fields, are all these fields Euclidean? In fact GRH implies that all these quadratic fields with class number 1 are Euclidean. Unconditionally Narkiewiscz showed that there at most $2$ exceptions. More generally, we have for any number field $K$ of class number 1 with infinite unit group, the ring of integers is Euclidean (assuming GRH).

We discuss the cases of $d=14$ and $d=69$ .

$\mathbb Z[\sqrt 14]$ is not norm-Euclidean.

To show that something is not norm Euclidean, we have exhibit an element in the field $x$ which doesn’t have good approximation with integral elements. Consider

$x = \frac{1+ \sqrt {14}}{2}$

If $y =m +n \sqrt {14}$ is such that $|\text{Norm}(x-y)| <1$ , we get

$|\text{Norm}(x-y)| =\left|\left(\frac{1}{2}-m\right)^{2}-14\left(\frac{1}{2}-n\right)^{2}\right|<1$

$\left|\left(1-2m\right)^{2}-14\left(1-2n\right)^{2}\right|<4$

$\left(1-2m\right)^{2}-14\left(1-2n\right)^{2} = 3 \mod 8 \implies \left(1-2m\right)^{2}-14\left(1-2n\right)^{2} = 3$

Now looking $\mod 7$ we see that $(1-2m)^2 = 3 \mod 7$ which is not possible $3$ is not a square modulo $7$ . Thus the solution $y =m +n \sqrt {14}$ doesn’t exist and $\mathbb Z[\sqrt 14]$ is not-norm Euclidean.

But it doesn’t mean that $\mathbb Z[\sqrt 14]$ is not Euclidean. We can check that $\mathbb Z[\sqrt 14]$ is a PID by verifying that all the prime ideals below Minkowski bound are principal. But still, it could be a PID but not have the Euclidean algorithm.

It’s actually Euclidean!

$d=69$ , the ring of integers $Z[\frac{1+\sqrt{69}}{2}]$ is not norm-Euclidean.

We follow the same strategy and consider $x =-\frac{4}{23} \sqrt{69}.$

If the domain was norm-Eulcidean, we need to find $y =\frac{m+n \sqrt{69}}{2}$ such that

$|\text{Norm}\left( \frac{m+n \sqrt{69} }{2}-\frac{4}{23} \sqrt{69}\right)| <1$

$\implies \left|23 m^{2}-3(23 n-8)^{2}\right| < 92$

Now checking $\mod 92$ by looking at $\mod 4$ and $\mod 23$ we see that

$23 m^{2}-3(23 n-8)^{2} = -8 \mod 92$ . Hence the only option are $23 m^{2}-3(23 n-8)^2=-8$ and $23 m^{2}-3(23 n-8)^2 =-8+92 =84$

$23 m^{2}-3(23 n-8)^2=-8 \implies m^2 =2 \mod 3$ which has no solutions.
$23 m^{2}-3(23 n-8)^2 =84 \implies 5m^2-3(5n+1)^2 =0 \mod 9$ which also has no solutions.

Thus we see that norm cannot serve as the Euclidean function. Can we construct other functions? To understand the failure of the norm, we need to understand all the elements like $x=-\frac{4}{23} \sqrt{69}$ which don’t have good approximations.

Lemma: The only elements of the field for which there is no approximation $y$ such that $|\text{Norm}(x-y)|<1$ are elements which are

$\pm \frac{26+7 \alpha}{10+3 \alpha}~~ \mod \mathbb{Z}[\alpha]$

where $\alpha = \frac{1+ \sqrt{69}}{2}.$ .

In addition, we can choose the approximation $y$ so that $x-y$ is not divisible by $10+3\alpha .$

In fact, the norm function $\text{Norm}(X+Y\alpha)=X^2+XY-17Y^2$ attains the maximum inhomogenuous norm at $\left(\frac{19}{23}, \frac{8}{23}\right)$ and $\left(\frac{4}{23}, \frac{15}{23}\right)$ with a value of $\frac{25}{23} >1,$ which exactly corresponds to those two residue classes.

The same statement can be repharsed in terms of the integral elements as follows: The only coprime residue classes modulo any element of $\mathbb{Z}[\alpha]$ which do not contain an element of smaller norm are $\pm(16+4 \alpha)$ modulo $(10+3 \alpha)$ .

Thus if we start with any pair of elements in the ring $a, b$ such that $x=a/b \neq \pm \frac{26+7 \cdot \alpha}{10+3 \alpha}~~ \mod \mathbb{Z}[\alpha]$ , we can find $y, r$ such that $a=by+r$ and $|\text{Norm}(r)| <|\text{Norm}{(b)}|$ .

On the other hand if we start with say $a = 26+7\alpha, b = 10+3\alpha$ , the norm of the remainder will never be smaller than $|\text{Norm}(b)|=|-23|=23$ . For instance, if we take $a = 3b+r$ , that is $r =\frac{13}{2}+\frac{\sqrt{69}}{2}$ , we get $\text{Norm}(r)=25.$

We have a slightly stronger lemma:

The only coprime residue classes modulo any element of $\mathbb{Z}[\alpha]$ which do not contain an element of smaller norm not divisible by $10+3 \alpha$ are $\pm(16+4 \alpha)$ modulo $(10+3 \alpha)$ .

That is we can even assume that the remainder $r =a-bq$ is not divisible by the prime $10+3\alpha$ (lying above 23) for most choices with the only except being the $a=\pm(16+4 \alpha) , b= (10+3 \alpha)$ .

Proof sketch of the lemma: Explicitly construct some regions with good approximations, and then use the action by units to cover rest of the region. (“Method of Automorphs”). Then only two points (residues mentioned above) inside the fundamental domain of the integer lattice remain uncovered.

$\mathbb Z[\alpha]~$ is Euclidean:

From the above discussion we see that there is a problem with the prime $10+3\alpha$ . So we modify the norm at this prime to define a completely multiplicative function with

$\phi(\pi)= \begin{cases}|\text{Norm}(\pi)|, & \text { if } \pi \neq 10+3 \alpha \\ 26, & \text { if } \pi=10+3\alpha\end{cases}$

defined on primes $\pi$ .

With this function we given $x$ , we need to find $y \in R$ such that $\phi(x-y)<1$ . From the strengthening of the lemma, if $x$ is not in the exceptional classes we can find $y$ such $x-y$ is not divisible by $10+3\alpha$ with $latex |\text{Norm}(x-y)|<1 and hence

$\phi(x-y) = |\text{Norm}(x-y)| <1$

If $x$ is exceptional, we can $x-y = \pm \frac{26+7 \alpha}{10+3 \alpha}$ and then

$\phi(x-y) =\phi\left(\pm \frac{26+7 \alpha}{10+3 \alpha}\right) =\frac{\phi(\pm(26+7 \alpha))}{\phi(10+3\alpha)}=\frac{|\text{Norm}(\pm(26+7 \alpha))|}{26}=\frac{25}{26}<1$

$\mathbb Z[\sqrt 14]$ is Euclidean: We discuss Motzkin’s construction and the modifications by Harper to prove that the ring is Euclidean.

Motzkin’s lemma: Definition 2.15. Let $R$ be an integral domain (no zero divisors). Define the sets

$A_{0}:=R^{\times}$
$A_{n}:=\left\{ b \in R \ \{0\} \mid A_{n-1} \cup{0} \rightarrow R / R b \text { is surjective }\right\}, n \geq 1$

Then $R$ is Euclidean iff every non-zero element of $R$ is contained in some $A_n.$

For a Euclidean domain, these sets are given by elements of size atmost $n+1$ (size measure according to the Euclidean function). It’s easy to see that remainder $\mod b$ are size strictly smaller, hence come from the map $A_{n-1}\cup{0} \rightarrow R / R b$ , that is $A_{n-1} \cup {0} \rightarrow R/Rb$ is surjective.

But the lemma says, these conditions are enough to construct the euclidean function! In fact

define $F (0) =0$ , $F(b) =n+1$ for $b \in A_{n} \ A_{n-1}$ .

We start with units and define $F(u)=1$ for all the units. For elements $b$ whose non-zero residues $\mod b$ can generated by units we define $F(b)=2$ , and so on.

Variant of Motzkin’s lemma: Consider a set of distinct non associate primes $\pi_{1}, \ldots, \pi_{s}$ such that all invertible residues classes modulo $b =\pi_1^2\pi_2^2\cdot \pi_s^2$ contain units. Let $B_{0}$ be the all possible products of units and these primes. For $n \geq 1$ define

$B_{n}:=\left\{ \text {primes } \pi \in R \mid B_{n-1} \cup B_{0} \rightarrow \left(R / \pi\right)^{\times} \text {is surjective }\right\}$

If every prime of the domain is contained in some $B_n$ , then we have a Euclidean domain.

Thus if we start with some admissible set of primes, and verify that all primes are in some $B_n$ , we are done. In fact, some analytic techniques (large sieve, primes in arithmetic progressions etc) reduces the problem to verifying that $B_1$ has a lot of primes. To establish $B_1$ has lot of primes, one needs to start with a big $B_0$ (in fact they start with the admissible primes $\pi_{1}:=5-\sqrt{14}, ~~\pi_{2}:=3-2 \sqrt{14}$ . Then the fact that $B_1$ is large can seen from a sieve lower bound : There are lots of prime $\mathfrak p$ such that $\text{Norm}(\mathfrak p)-1$ don’t have any small prime factors. (The prime factor condition helps to make sure that the residue classes are filled by elements generated by $B_0$ so that $\mathfrak p$ is in $B_0$ — if all the prime factors are all large, the subgroups filled by the group generated by $B_0$ is either the whole residue or a very small set and the chance of it being a small set is small –this is where Large Sieve is helpful! The sieve lower bound use beautiful analytic ingredients like bilinear form for error terms in linear sieve and Bombieri-Friedlander-Iwaniec theorem on well-factorable moduli and primes in arithmetic progressions.

Theorem 1:

$S\left(\mathcal{A}, \mathcal{P}, x^{\theta}\right)\geq X \displaystyle \prod_{\substack{\ell \in \mathcal{P} \\ \ell<x^{\theta}}} \left(1-\frac{\omega(\ell)}{\ell}\right) \left\{f\left(\frac{2 \theta+\varepsilon}{\theta}\right)-\varepsilon^{\prime}\right\}-R_{0}-\sum_{n=1}^{N} R_{n}$

$\displaystyle R_{0}=\sum_{q<x^{\frac{1}{4}}}\left|r_{q}\right| \quad \text { and } \quad R_{n}=\sum_{q} \lambda_{n}(q) r_{q}$
for some well-factorable functions $\lambda_{n}$ of level $x^{2 \theta+\varepsilon}$ .

Theorem 2: Suppose $a \neq 0, \varepsilon>0$ and $Q=x^{4 / 7-\varepsilon}$ . For any well-factorable function $\lambda(q)$ of level $\mathrm{Q}$ and any $A>0$ ,

$\displaystyle \sum_{(q, a)=1} \lambda(q)\left(\psi(x ; q, a)-\frac{x}{\phi(q)}\right)$

Theorem 3: Suppose $a$ and $k$ are coprime integers. If $d=\text{gcd}(a-1, k)$ and suppose $\text{gcd}((a-1) / d, d)=1.$ The number of primes $p \leq x$ such that $p \equiv a(\bmod k)$ and $\frac{p-1}{d}$ is divisible only by primes $\ell$ exceeding $x^{\frac{2}{7}-\varepsilon}$ is $\gg x / \log ^{2} x$

References:

Clark, D.A. A quadratic field which is Euclidean but not norm-Euclidean. Manuscripta Math 83, 327–330 (1994). https://doi.org/10.1007/BF02567617

D. A. Clark and M. R. Murty, The Euclidean algorithm for Galois extensions of Q, J. Reine Angew. Math.459(1995), 151–162

M. Harper, $\mathbb Z[\sqrt{14}]$ is Euclidean, https://doi.org/10.4153/CJM-2004-003-9

H. Chatland and H. Davenport,Euclid’s algorithm in real quadratic fields, Canad. J. Math. Vol.2(1950), 289–296

W. Narkiewicz, Euclidean algorithm in small Abelian fields, Funct. Approx. Comment. Math.37(2007), 337–340

P. J. Weinberger, On Euclidean rings of algebraic integers, Analytic number theory (Proc. Sympos. Pure Math., Vol.XXIV, St. Louis Univ.,St. Louis, Mo., 1972), Amer. Math. Soc., Providence, R. I., 1973, pp.321–332.

Franz Lemmermeyer, The Euclidean Algorithm in Algebraic Number Fields

Share this:

Related

Leave a comment Cancel reply