View source for Every Euclidean ring has a unique smallest Euclidean norm

==Statement==

Every [[fact about::Euclidean ring]] (and in particular, every [[fact about::Euclidean domain]]) has a ''unique'' smallest Euclidean norm <math>N</math>. More specifically, given a [[commutative unital ring]] <math>R</math> that possesses a [[fact about::Euclidean norm]], there is a Euclidean norm <math>N</math> with the following properties:

* For any Euclidean norm <math>N_1</math> on <math>R</math>, and any <math>a \in R \setminus \{ 0 \}</math>, <math>N(a) \le N_1(a)</math>.
* The elements of norm zero are precisely the [[unit]]s and the elements of norm one are precisely the [[fact about::universal side divisor]]s.
* <math>N</math> is a [[fact about::multiplicatively monotone Euclidean norm]], i.e., it is [[fact about::multiplicatively monotone norm|multiplicatively monotone]]: if <math>ab \ne 0</math>, <math>N(ab) \ge \max \{ N(a), N(b) \}</math>.
* <math>N</math> is an [[fact about::automorphism-invariant Euclidean norm]].

==Related facts==

* [[Element of minimum norm in Euclidean ring is a unit]]
* [[Element of minimum norm among non-units in Euclidean ring is a universal side divisor]]
* [[Minimum over principal ideal of Euclidean norm is a smaller multiplicatively monotone Euclidean norm]]
==Examples==

* Over the [[particular example::ring of rational integers]], the smallest Euclidean norm is the greatest integer of the logarithm to base two of the absolute value. {{further|[[Ring of rational integers is Euclidean with norm equal to binary logarithm of absolute value]]}}.
* Over the [[particular example::polynomial ring over a field]], the smallest Euclidean norm is the usual degree function. {{further|[[Polynomial ring over a field is Euclidean with norm equal to degree]]}}

==Facts used==

# [[uses::Element of minimum norm in Euclidean ring is a unit]]
# [[uses::Minimum over principal ideal of Euclidean norm is a smaller multiplicatively monotone Euclidean norm]]
==Proof==

'''Given''': A commutative unital ring <math>R</math> with a Euclidean norm <math>N_1</math>.

===Construction of the sloewst growing Euclidean norm===

We define the norm inductively as follows.

For <math>n \ge 0</math>, define <math>R_n</math> as follows:

* <math>R_0</math> is the set of units.
* For <math>n \ge 1</math>, <math>R_n</math> is defined as the set of those <math>x</math> such that <math>x \ne 0</math>, <math>x \notin \bigcup_{m=0}^{n-1} R_m</math>, and for every <math>y \in R</math>, there exists <math>r \in \{ 0 \} \cup \bigcup_{m=0}^{n-1} R_m</math> such that <math>x | y - r</math>.

For any <math>x \in R \setminus \{ 0 \}</math>, <math>N(x)</math> is defined as the unique <math>n</math> such that <math>x \in R_n</math>.

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

<math>y = xq + r</math>

with <math>r = 0</math> or <math>N(r) < N(x)</math>.

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

We prove that if <math>N_1(a) = n</math> for the Euclidean norm <math>N_1</math>, then <math>a \in \bigcup_{m=0}^n R_m</math>. This will prove that <math>N</math> is well-defined and <math>N(x) \le N_1(x)</math> for all nonzero <math>x</math>.

'''Given''': <math>a \in R \setminus \{ 0 \}</math> with <math>N_1(x) = n</math>.

'''To prove''': <math>a \in \bigcup_{m=0}^n R_m</math>.

'''Proof''': We prove this claim by induction on <math>n</math>. 

'''Base case''': When <math>n = 0</math>, we have <math>N_1(x) = 0</math>. By fact (1), <math>a</math> is a unit, so <math>a \in R_0</math> by definition.

'''Induction step''': Suppose <math>n > 1</math>, and the statement is true for <math>0 \le m \le n - 1</math>. We have <math>N_1(x) = n</math>. 

* If <math>x \in \bigcup_{m=0}^{n-1} R_m</math>, we are done. 
* Suppose <math>x \notin \bigcup_{m=0}^{n-1} R_m</math>. For any <math>y \in R</math>, the division algorithm yields:

<math>y = xq + r</math>

where <math>r = 0</math> or <math>N_1(r) < N_1(x) = n</math>. By the inductive assumption, <math>r \in \{ 0 \} \cup \bigcup_{m=0}^n-1} R_m</math>. Thus, for any <math>y \in R</math>, <math>x | y - r</math> for some <math>r \in \{ 0 \} \cup \bigcup_{m=0}^{n-1} R_m</math>.

Thus, <math>x \in R_n</math>.

===Proof that the norm is multiplicatively monotone===

'''Given''': <math>a,b \in R</math> such that <math>ab \ne 0</math>.

'''To prove''': <math>N(ab) \ge \max \{ N(a), N(b) \}</math>.

'''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 <math>N</math> 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 <math>ab \in R_n</math>, then either <math>a \in R_m</math> for some <math>m < n</math>, or <math>a</math> satisfies all the conditions for being in <math>R_n</math>. In either case, <math>N(ab) \ge N(a)</math>. Similarly, <math>N(ab) \ge N(b)</math>.

===Proof that the norm is automorphism-invariant===

The way the norm is defined is clearly automorphism-invariant, since it depends on no choices.