Euclidean domains with a special Euclidean function

Posted: December 22, 2023 in Basic Algebra, Rings
Tags: , , , ,
0

In this post we are going to show that if R is a Euclidean domain with a Euclidean function \phi that satisfies the inequality \phi(a+b) \le \max \{\phi(a),\phi(b)\}, whenever a,b,a+b \in R \setminus \{0\}, then R is either a field or a polynomial ring over a field. This result was posted as a problem on the Art of Problem Solving website recently; you can see the problem and my solution here. I’m now going to give a slightly improved version of that solution here.

Let’s begin with the definition of Euclidean domains.

Definition. A Euclidean domain is a commutative domain with identity R such that there exists a function \phi: R \setminus \{0\} \to \mathbb{Z}_{\ge 0} with the following properties.

i) If a,b \in R, \ b \ne 0, then a=sb+r for some r,s \in R with either r=0 or \phi(r) < \phi(b).

ii) if a,b \in R \setminus \{0\}, then \phi(a) \le \phi(ab).

The function \phi is called a Euclidean function for R.

Not all ring theorists are happy with having the condition ii) in the definition of a Euclidean domain since it can be shown that i) implies the existence of a function R \setminus \{0\} \to \mathbb{Z}_{\ge 0} that satisfies both i), ii). But in this post, we are going to stay away from that argument and keep ii).

There are many examples of Euclidean domains but, for a reason you’re going to see in a moment, we are only interested in two of them in this post.

Example 1. Any field F is a Euclidean domain. Just choose any nonnegative integer n and define \phi(a)=n, for all 0 \ne a \in F. Then the condition ii) clearly holds and if 0 \ne b \in R, then a=(ab^{-1})b+0, so the condition i) is also satisfied.

Example 2. The ring of polynomials F[x] over a field F is a Euclidean domain. Here we define the Euclidean function by \phi(p(x))=\deg p(x), for all 0 \ne p(x) \in F[x]. Then the condition ii) clearly holds because

\phi(p(x)q(x))=\deg (p(x)q(x))=\deg p(x)+\deg q(x) \ge \deg p(x)=\phi(p(x)).

The condition i) is just the familiar process of dividing two polynomials.

Remark. Both Euclidean functions in Examples 1,2 satisfy the inequality \phi(a+b) \le \max \{\phi(a),\phi(b)\}, whenever a,b,a+b \in R \setminus \{0\}. Interestingly, there are no other Euclidean domains whose Euclidean functions satisfy the said inequality. The goal in this post, as mentioned in the first paragraph of this post, is to prove that result.

Notation. From now on, R is a Euclidean domain with a Euclidean function \phi, and U(R) is the multiplicative group of units of R.

Next is to find U(R). This is a well-known result about Euclidean domains but since it is important and also for the sake of completeness, I’m going to prove it here.

Lemma. Let a,b \in R \setminus \{0\}. Then

1) \phi(1) \le \phi(a), i.e. \phi(1) is the minimum value of \phi,

2) \phi(a)=\phi(ab) if and only if b is a unit. In particular,

U(R)=\{a \in R \setminus \{0\}: \ \phi(a)=\phi(1)\}.

Proof. 1) \phi(a)=\phi(1 \cdot a) \ge \phi(1).

2) If b is a unit, then \phi(ab) \ge \phi(a)=\phi(abb^{-1}) \ge \phi(ab) and so \phi(a)=\phi(ab). Suppose now that \phi(a)=\phi(ab). If Ra=Rab, then b is a unit. Otherwise, there exists c \in Ra \setminus Rab and so c=sab+r for some r,s \in R with either r=0 or \phi(r) < \phi(ab). If r=0, then c \in Rab, which is not true. Therefore \phi(r) < \phi(ab)=\phi(a), which is not possible because r=c-sab \in Ra and so r=da for some d \in R, which then gives the contradiction \phi(r)=\phi(da) \ge \phi(a). \ \Box

We are now ready to prove the result mentioned in the above Remark.

Theorem. Let F:=U(R) \cup \{0\}, and suppose that

\phi(a+b) \le \max\{\phi(a),\phi(b)\},

whenever a,b,a+b \in R \setminus \{0\}. Then

1) \phi(a+b)=\phi(a), for all a,b \in R with a \ne 0, \ a+b \ne 0, \ b \in F,

2) F is a subfield of R,

3) either R = F or R is a polynomial ring over F.

Proof. 1) That is clear if b=0. Suppose now that b \in U(R). Then by the Lemma

\phi(a+b) \le \max \{\phi(a),\phi(b)\}=\max \{\phi(a), \phi(1)\}=\phi(a).

Similarly,

\phi(a)=\phi(a+b-b) \le \max \{\phi(a+b),\phi(-b)\}=\max \{\phi(a+b),\phi(1)\}=\phi(a+b).

2) The only thing that we need to prove is that if a,b \in F, then a+b \in F. Well, that’s clear if a=0 or a+b=0. If a, a+b are nonzero, then, by 1), \phi(a+b)=\phi(a)=\phi(1), and so a+b \in F.

3) Choose x \in R \setminus F such that \phi(x) is a minimal element of \{\phi(a): \ a \in R \setminus F\}. Notice that x is not algebraic over the field F because then either x=0 or x would be a unit, contradicting x \notin F. So we are done if we show that R=F[x]. Let a \in R. We prove by induction over \phi(a) that a \in F[x]. By the first part of the Lemma, \phi(1) is the minimum value of \phi. If \phi(a)=\phi(1), then a \in F \subset F[x], and we are done. Suppose now that a \notin F. We have a=sx+r for some r,s \in R with either r=0 or \phi(r) < \phi(x). If \phi(r) < \phi(x), then r \in F, by the minimality condition on \phi(x). So either way, r \in F. So if s \in F, then a \in F[x] and we are done. Thus we may assume that s \notin F. Then, by the Lemma and the first part of the Theorem, \phi(s) < \phi(sx)=\phi(a) and so, by induction, s \in F[x]. Therefore a=sx+r \in F[x] and that completes the proof of the Theorem. Merry Christmas! \ \Box

Leave a Reply