Every Euclidean ring has a unique smallest Euclidean norm

Statement

Every Euclidean ring (and in particular, every Euclidean domain) has a unique smallest Euclidean norm $N$ . More specifically, given a commutative unital ring $R$ that possesses a Euclidean norm, there is a Euclidean norm $N$ with the following properties:

For any Euclidean norm $N_{1}$ on $R$ , and any $a\in R\setminus \{0\}$ , $N(a)\leq N_{1}(a)$ .
The elements of norm zero are precisely the units and the elements of norm one are precisely the universal side divisors.
$N$ is a multiplicatively monotone Euclidean norm, i.e., it is multiplicatively monotone: if $ab\neq 0$ , $N(ab)\geq \max\{N(a),N(b)\}$ .
$N$ is an automorphism-invariant Euclidean norm.

Related facts

Examples

Over the ring of rational integers, the smallest Euclidean norm is the greatest integer of the logarithm to base two of the absolute value. Further information: Ring of rational integers is Euclidean with norm equal to binary logarithm of absolute value.
Over the polynomial ring over a field, the smallest Euclidean norm is the usual degree function. Further information: Polynomial ring over a field is Euclidean with norm equal to degree

Facts used

Proof

Given: A commutative unital ring $R$ with a Euclidean norm $N_{1}$ .

Construction of the sloewst growing Euclidean norm

We define the norm inductively as follows.

For $n\geq 0$ , define $R_{n}$ as follows:

$R_{0}$ is the set of units.
For $n\geq 1$ , $R_{n}$ is defined as the set of those $x$ such that $x\neq 0$ , $x\notin \bigcup _{m=0}^{n-1}R_{m}$ , and for every $y\in R$ , there exists $r\in \{0\}\cup \bigcup _{m=0}^{n-1}R_{m}$ such that $x|y-r$ .

For any $x\in R\setminus \{0\}$ , $N(x)$ is defined as the unique $n$ such that $x\in R_{n}$ .

Note that $N(x)$ is well-defined for all $x$ , $N$ is Euclidean by definition: for every $x,y\in R$ with $x\neq 0$ , there exists $r$ such that $x|y-r$ with $r=0$ or $r\in \bigcup _{m=0}^{N(x)-1}R_{m}$ , which is precisely saying that $r=0$ or $N(r)<N(x)$ . Thus, we can write:

$y=xq+r$

with $r=0$ or $N(r)<N(x)$ .

Proof that this Euclidean norm exists for a Euclidean ring and is smaller than any other Euclidean norm

We prove that if $N_{1}(a)=n$ for the Euclidean norm $N_{1}$ , then $a\in \bigcup _{m=0}^{n}R_{m}$ . This will prove that $N$ is well-defined and $N(x)\leq N_{1}(x)$ for all nonzero $x$ .

Given: $a\in R\setminus \{0\}$ with $N_{1}(x)=n$ .

To prove: $a\in \bigcup _{m=0}^{n}R_{m}$ .

Proof: We prove this claim by induction on $n$ .

Base case: When $n=0$ , we have $N_{1}(x)=0$ . By fact (1), $a$ is a unit, so $a\in R_{0}$ by definition.

Induction step: Suppose $n>1$ , and the statement is true for $0\leq m\leq n-1$ . We have $N_{1}(x)=n$ .

If $x\in \bigcup _{m=0}^{n-1}R_{m}$ , we are done.
Suppose $x\notin \bigcup _{m=0}^{n-1}R_{m}$ . For any $y\in R$ , the division algorithm yields:

$y=xq+r$

where $r=0$ or $N_{1}(r)<N_{1}(x)=n$ . By the inductive assumption, Failed to parse (syntax error): {\displaystyle r \in \{ 0 \} \cup \bigcup_{m=0}^n-1} R_m} . Thus, for any $y\in R$ , $x|y-r$ for some $r\in \{0\}\cup \bigcup _{m=0}^{n-1}R_{m}$ .

Thus, $x\in R_{n}$ .

Proof that the norm is multiplicatively monotone

Given: $a,b\in R$ such that $ab\neq 0$ .

To prove: $N(ab)\geq \max\{N(a),N(b)\}$ .

Proof: One way of proving this is to invoke fact (2), which states that given any Euclidean norm, we can obtain a smaller multiplicatively monotone Euclidean norm. Since the norm $N$ is the smallest Euclidean norm, it must be equal to the multiplicatively monotone Euclidean norm obtained from it using fact (2).

We can also check the condition directly. If $ab\in R_{n}$ , then either $a\in R_{m}$ for some $m<n$ , or $a$ satisfies all the conditions for being in $R_{n}$ . In either case, $N(ab)\geq N(a)$ . Similarly, $N(ab)\geq N(b)$ .