Posts Tagged ‘Euclidean functions’

A simple property of Euclidean domains

Posted: May 19, 2024 in Basic Algebra, Rings
Tags: , , ,
0

As always, given a ring R, we denote by U(R) the multiplicative group of units of R.

Definition. Let R be a commutative domain with identity. An element a \in R \setminus U(R) is called a universal side divisor if for every b \in R, either a \mid b or a \mid b+u for some u \in U(R). Equivalently, a \in R \setminus U(R) is a universal side divisor if R=Ra + U(R) \cup \{0\}.

Remark. If a is a universal side divisor of R, then Ra is a maximal ideal of R. The converse is not true.

Proof. Let I \supset Ra be an ideal of R and b \in I \setminus Ra. Then b=ra+u for some u \in U(R) \cup \{0\}. Since b \notin Ra, we have u \ne 0 and so u \in U(R). Thus u=b-ra \in I \cap U(R) and hence I=R.
To see that the converse is false, consider the example R=\mathbb{Z}, \ a=5. Then Ra is a maximal ideal of R but Ra+U(R) \cup \{0\}=5\mathbb{Z}+\{0,1,-1\} \ne \mathbb{Z}=R and so a=5 is not a universal side divisor of \mathbb{Z}. \ \Box

Proposition. If R is a Euclidean domain, then R has a universal side divisor.

Proof. Suppose first that R is a field. Note that R is a Euclidean domain with the constant Euclidean function \phi(r)=1. Now, since every nonzero element of R is a unit, a=0 is a universal side divisor of R.
Suppose now that R is a Euclidean domain which is not a field and let \phi be a Euclidean function of R. Let

S:=\{\phi(r): \ \ 0 \ne r \in R \setminus U(R)\}.

Since R is not a field, S \ne \emptyset and hence S has a smallest element, say \phi(a). Let b \in R. So there exist elements c, d \in R such that b=ca+d, where either d=0 or \phi(d) < \phi(a). If d=0, then a \mid b. If \phi(d) < \phi(a), then \phi(d) \notin S, by minimality of \phi(a), and so d \in U(R). Thus u:=-d \in U(R) and a \mid b+u because ca=b-d=b+u. \ \Box

Example 1. The ring of integers \mathbb{Z} is a Euclidean domain with the Euclidean function \phi(n)=|n|. For every integer n, we have either 2 \mid n or 2 \mid n+1 amd so 2 is a universal side divisor of \mathbb{Z}. Similarly, -2, 3, -3 are also universal side divisors of \mathbb{Z} and \mathbb{Z} has no other universal side divisors (why?).

Example 2. The ring of Gaussian integers \mathbb{Z}[i]=\mathbb{Z}+\mathbb{Z}i \subset \mathbb{C} is a Euclidean domain with the Euclidean function \phi(a+bi)=a^2+b^2. It is easy to see that U(\mathbb{Z}[i])=\{1,-1,i,-i\}. So the set S in the proof of the above Proposition is S=\{a^2+b^2: \ a,b \in \mathbb{Z}, \ a^2+b^2 > 1\}. So the smallest element of S is 2 and hence \pm 1 \pm i are universal side divisors of \mathbb{Z}[i].

Example 3. Let k be a field. Then the polynomial ring k[x] is a Euclidean domain with the Euclidean function \phi(p(x))=\deg p(x). By this post, U(k[x])=U(k)=k \setminus \{0\}. So the set S in the proof of the above Proposition is S=\{\deg p(x): \ \deg p(x) \ge 1\}=\{1,2, 3, \cdots \}. So 1 is the smallest element of S and hence any polynomial of degree 1 is a universal side divisor of k[x].

Example 4. The polynomial ring R:=\mathbb{Z}[x] is not a Euclidean domain.

Proof. The standard proof is that since every Euclidean domain is a PID and R is not a PID, R is not a Euclidean domain. But here we want to prove that using the above Proposition. First note that, by the post linked in Example 3, U(R)=U(\mathbb{Z})=\{1,-1\}. Suppose now, to the contrary, that R is a Euclidean domain and let p(x) be a universal side divisor of R. So for every q(x) \in R, we have either p(x) \mid q(x) or p(x) \mid q(x) +1 or p(x) \mid q(x)-1. Choosing q(x)=2, we get that p(x)=\pm 2 or \pm 3. But then choosing q(x)=x, we must have p(x) \mid x or p(x) \mid x+1 or p(x) \mid x-1, which are all impossible. So R has no universal side divisor hence is not a Euclidean domain. \ \Box

Note. The Proposition in this post is a slightly modified version of Proposition 3.63 in Joseph Rotman’s book Advanced Modern Algebra. The Remark and Examples in this post are mine. Proposition 3.63 in Rotman’s book says that every Euclidean domain which is not a field has a universal side divisor. I have no idea why Rotman decided to exclude fields!

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