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

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://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.

-
The $K$-theory result is that $SK_1(A)=0$ when $A$ is euclidean, where $K_1(A) = SK_1(A)\oplus K^*$. The counterexample is due to Grayson ($SK_1$ of an interesting PID, JPAA 1981); the PID with $SK_1(A)\neq 0$ is $A=S^{-1}\mathbb{Z}[T]$, where $S=\{T^m-1\,,\,m\geq 1\}\cup \{T\}$. Nifty. – Charles Rezk Sep 15 '10 at 5:22
"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 Euclidean, ..." Hopefully this should say "is not Euclidean". – Ricky Demer Sep 15 '10 at 5:31
A similar question - why do we care that the norm is \mathbb{N}? I think I once saw Euclidean domain defined with the target space of the norm being any well-ordered set rather than \mathbb{N}; it does seem to be just well-ordering that matters. Is this definition equivalent? Or is there some reason to care that it's \mathbb{N}? Or is the general ordinal definition really the "right" definition? – Harry Altman Sep 15 '10 at 16:09
@Harry: the concept of a Euclidean norm taking values in an arbitrary well-ordered set has indeed been considered, especially by Pierre Samuel. Of course any such "Samuel-Euclidean ring" is a PID. Much less obviously: (i) there exist Samuel-Euclidean rings which are not Euclidean with an $\mathbb{N}$-valued Euclidean function and (ii) the ring of integers of $\mathbb{Q}(\sqrt{-19})$ is a PID which is not Samuel-Euclidean. See e.g. Section 12.2 of math.uga.edu/~pete/integral.pdf for a little more on this and some references. – Pete L. Clark Sep 15 '10 at 17:24
Ah, thank you! I was wondering because everything I'd seen about Euclidean rings, including the proof of $\mathbb{Q}(\sqrt{-19})$ not being Euclidean, and the decomposition into elementary matrices / vanishing SK_1 thing worked just as well for Samuel-Euclidean. – Harry Altman Sep 15 '10 at 18:30

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.

-
@Franz: first, I was hoping that you would respond, since (in my book at least) you are the reigning king of Euclidean rings. Second, I understand what you're saying about the D-H norm: knowing that it exists is not enough to be effective; you need to know how to choose the auxiliary element "$k$". In the (few) examples I have looked at, the choice of $k$ is quite simple: e.g. I do the case of the ring of integers in $\mathbb{Q}(\sqrt{-19})$ in my article cited above. Do you know of any specific class number one number field where one can't work out a good method for finding $k$? – Pete L. Clark Sep 15 '10 at 7:55
Finding elements with small norm is a pain in the neck for number fields of high degree and one of the reasons why pari can't compute class groups up there. So take the ring of integers in the field of 19th roots of unity, if you want. But of course you have the same problem for the usual norm even if you knew that this ring is norm-Euclidean. – Franz Lemmermeyer Sep 15 '10 at 17:40
N.B.: I'm accepting this answer for now (I may not get another one). But my suspicions about crazy Euclidean norms have not yet been entirely quelled... – Pete L. Clark Sep 21 '10 at 15:08

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.

-
I think this is not the case: both Hiblot's example and Nagata's example are indeed of Euclidean domains. See for instance the MathSciNet review of a 1985 paper of Kazuo Amano: "the author produces another example of a Euclidean ring (defined via a well-ordered set) which is not a Euclidean ring (defined via the positive integers). This differs from the examples of J.-J. Hiblot and M. Nagata in its not being an integral domain." – Pete L. Clark Nov 10 '12 at 11:03
Also the MathSciNet review of Hiblot's papers describes the ring he constructs, and it is a domain. Are you suggesting that this work of Hiblot and Nagata is incorrect? – Pete L. Clark Nov 10 '12 at 11:09

Oh, really?! You are right, Pete! My fault--I should have checked Hiblot's result better... My confusion stems from the fact, that the examples by Hiblot and Nagata seem not to be generally known: I stumbled across at least two recent independent sources claiming that it is a long-standing open problem (e.g. www.math.uchicago.edu/~drh/mcs/Jointseminar7.html).

-
Welcome to MO! It is not a big deal, but for future reference: to do this discussion via an answer is a bit against the intent of how to use the site. (While due to some lacking points you cannot yet comment on others peoples answers and questions, you could have commented on you own answer if you had logged in/registered your first account (or preserved the cookie, I think)). Thus, in case you should intent to use the site more regularly, which I hope, I receommend to register an account. (You can then also ask on the sticky thread on 'meta' for your accounts to be merged.) – quid Nov 13 '12 at 11:33