Why do we care whether a PID admits some crazy Euclidean norm?

Question

An integral domain $R$ is said to be Euclidean if it admits some Euclidean norm: i.e., a function $N: R \rightarrow \mathbb{N} = \mathbb{Z}^{\geq 0}$ such that: for all $x, y \in R$ with $N(y) > 0$, either $y$ divides $x$ or there exists $q \in R$ such that $N(x-qy) < N(y)$. A well-known "descent" argument shows that any Euclidean domain is a PID. In fact, the argument that a Euclidean domain is necessarily a UFD is a little more direct and elementary than the argument that shows that a PID is a UFD (because, in the latter case, one needs some kind of ideal-theoretic argument to show the existence of factorizations into irreducible elements). Because of this, Euclidean domains are a familiar staple of undergraduate algebra.

A lot of texts seem to emphasize the fact that a PID need not be a Euclidean domain. In order to show this, one has to show not only that some particular norm (and often there is a preferred norm in sight, see below) is not Euclidean, but that there is no Euclidean norm whatsoever. In general this is a very delicate question: for instance, the proof of the most standard example -- that the ring of integers of $\mathbb{Q}(\sqrt{-19})$ is a PID but does not admit any Euclidean norm -- is already rather intricate.

My question is this:

Given a ring $R$ that we already know is a PID, why do we care whether or not it admits some Euclidean norm?

Note that in contrast, many domains admit natural norms. A class of domains which I have been thinking about recently are the infinite domains satisfying (FN): the quotient by every nonzero ideal is finite. In this case, the map $0 \mapsto 0$, $x \in R \setminus \{0\} \mapsto \# R/(x)$ is a multiplicative norm, which I call canonical. For instance, the usual absolute value on $\mathbb{Z}$ is the canonical norm, as is the norm on any ring of integers in a number field that you meet in an algebraic number theory course.

I have recently realized that I care quite a bit about whether certain specific norms on integral domains are Euclidean. (This has come up in my work on quadratic forms and the Davenport-Cassels theorem.) There is some very natural algebra and discrete geometry here. But why do I care if some crazy Euclidean norm exists?

Here are three reasons that one might care about this:

1. If a domain admits an "effective" Euclidean norm, one can give effective algorithms for linear algebra over that ring, whereas the structure theory of modules over an arbitrary PID is not a priori algorithmic in nature.

2. (in algebraic K-theory): If $R$ is Euclidean, $\operatorname{SK}_1(R) = 0$, but there exists a PID with nonvanishing $\operatorname{SK}_1$. (Thanks to Charles Rezk for giving the precise result based on my vague allusion to it.)

3. In algebraic number theory, there has been a lot of work towards proving the conjecture that if $K$ is a number field which is not $\mathbb{Q}(\sqrt{D})$ for $D = -19, -43, -67, -163$, then the ring $\mathbb{Z}_K$ of integers of $K$ is a PID iff it is Euclidean (for some crazy norm). In particular, disproving this would disprove the generalized Riemann hypothesis.

Comments on 1: There is something to this, but I somehow doubt that it's such a big deal. For instance, the ring of integers of $\mathbb{Q}(\sqrt{-19})$ is not Euclidean, but I'm pretty sure that there are algorithms for modules over it. In particular, it seems to me that for algorithmic purposes, having a Dedekind-Hasse norm is just as good as a Euclidean norm, and every PID has a Dedekind-Hasse norm. In fact, for every PID which satisfies (FN), the canonical norm is a Dedekind-Hasse norm. (See p. 27 of http://alpha.math.uga.edu/~pete/factorization2010.pdf for this.)

Comments on 3: if I knew more about this result, I might appreciate it better. It does seem to involve some interesting geometry of numbers. But this convinces me why I should be interested in the special case of rings of integers in number fields, which, as a number theorist, I am already convinced are more worthy of scrutiny from every possible angle than an arbitrary domain.

If there are other good reasons to care, I'd certainly like to know.

Answer 1

There are a lot of results in elementary number theory that can be proved with the quadratic reciprocity law. In such a proof you usually have to invert some Jacobi symbol $(a/b)$ and then reduce the numerator modulo the denominator. For number fields that are not Euclidean with respect to some simple map you have a problem if you want to follow this route (the same goes for applications of quadratic and higher residues to cryptography, although this is mostly a theoretical business). In principle, Dedekind-Hasse will also do the trick in some cases.

If the ring of integers you're interested in is not Euclidean for the canonical norm, the first idea is to modify it. You could give prime ideals a different weight (weighted norms), or allow division chains in which the norm does not necessarily get smaller in every step (k-stage Euclidean rings), or try some version of Dedekind-Hasse. But if (given a pair $(a,b)$ of elements in a ring) you want to make the norm of $ka-bq$ small, you need more than just the knowledge that a suitable $k$ exists: you need a method for finding $k$ (in addition to finding $q$), perhaps by showing that you can select it from a finite set of elements with bounded norm or something similar.

Edit. The Euclidean algorithm is closely related to continued fractions, and the latter are routinely used for doing calculations of units and ideal class groups of real quadratic number fields. For number fields that admit a Euclidean algorithm, something similar can be done: Hurwitz and Mathews worked out a theory of continued fractions over the Gaussian integers, and people like Arwin, Trinks, Degel, Lakein, Stein etc. generalized this to complex Euclidean number fields and used it for computing units and class numbers. I am not aware of too many recent contributions in this direction, but a short search has at least revealed D. Fried, Reduction theory over quadratic imaginary fields, T. Number Theory 2005.

Answer 2

One needs to be careful with those Samuel-Euclidean rings and Hiblot result. Yes, there exist Samuel-Euclidean rings which are not Euclidean, however: whether there is a domain with these properties, seems to be an open question so far.