Euclidean ring

In mathematics , a Euclidean ring is a ring in which there is a generalized division with remainder , as is known from integers . "Rest" is defined by a suitable evaluation function.

Definitions

There are a number of different but similar definitions of a Euclidean ring in literature and in academic and scientific practice. Often they already contain more specific properties, such as B. can bring relief in the formulation of the theory spanned below. What all these definition variants have in common, however, is that in a Euclidean ring a division by the remainder and thus a Euclidean algorithm for determining the greatest common divisor (GCD) of two ring elements is possible. The name is derived from this property.

version 1

An integrity ring (also known as an integrity domain , i.e. a commutative , zero-divisor-free ring with 1) is called a Euclidean ring if there is an evaluation function with the following properties: ${\displaystyle R}$ ${\displaystyle g\colon R\setminus \{0\}\to \mathbb {N} _{0}}$

• for all with exist elements with (division with remainder) , where is either or , and ${\displaystyle x,y\in R}$ ${\displaystyle y\neq 0}$ ${\displaystyle q,r\in R}$ ${\displaystyle x=qy+r}$ ${\displaystyle r=0}$ ${\displaystyle g(r)<g(y)}$
• for always applies . ${\displaystyle x,y\in R\setminus \{0\}}$ ${\displaystyle g(xy)\geq g(x)}$

The evaluation function is then also called the Euclidean norm function (Euclidean amount) of the ring. ${\displaystyle g}$

Variant 2

The above definition is almost equivalent to the following, also frequently used, in which, however, an evaluation for the zero is also given.

Definition:
An integrity ring is called a Euclidean ring if there is an evaluation function with the following properties: ${\displaystyle R}$ ${\displaystyle g\colon R\to \mathbb {N} _{0}}$

• ${\displaystyle g(0)=0,}$
• for all with exist elements with (division by remainder) , where is, and ${\displaystyle x,y\in R}$ ${\displaystyle y\neq 0}$ ${\displaystyle q,r\in R}$ ${\displaystyle x=qy+r}$ ${\displaystyle g(r)<g(y)}$
• for always applies . ${\displaystyle x,y\in R\setminus \{0\}}$ ${\displaystyle g(xy)\geq g(x)}$

Variation 3

Another variant provides the following

Definition:
An integrity ring (here only: a commutative, zero- divisor -free ring with at least one non-zero element) is called a Euclidean ring if a degree function exists with the following properties: ${\displaystyle R}$ ${\displaystyle g\colon R\setminus \{0\}\to \mathbb {N} _{0}}$

• for all with exist elements with (division with remainder) , where is either or . ${\displaystyle x,y\in R}$ ${\displaystyle y\neq 0}$ ${\displaystyle q,r\in R}$ ${\displaystyle x=qy+r}$ ${\displaystyle r=0}$ ${\displaystyle g(r)<g(y)}$

Variant 3 only appears to be weaker. The following actually applies: If one of the three above-mentioned evaluation functions exists on an integrity ring (with 1), there are also evaluation functions that correspond to the other two definitions. It follows that the three definitions of Euclidean ring are equivalent, although the definition of evaluation function differ.

Another much more general, but seldom used variant, in which the evaluation function is real-valued, is not necessarily equivalent to the above definitions:

Variation 4

Definition:
An integrity ring is called a Euclidean ring if a value function (or evaluation function) exists with the following properties: ${\displaystyle R}$ ${\displaystyle g\colon R\setminus \{0\}\to \mathbb {R} }$

• for all with exist elements with (division with remainder) , where is either or , and ${\displaystyle x,y\in R}$ ${\displaystyle y\neq 0}$ ${\displaystyle q,r\in R}$ ${\displaystyle x=qy+r}$ ${\displaystyle r=0}$ ${\displaystyle g(r)<g(y)}$
• for a given there are at most finitely many real numbers from the range of that are smaller than . More formally : . ${\displaystyle s\in \mathbb {R} }$ ${\displaystyle w_{i}}$ ${\displaystyle W{\stackrel {\mathrm {def} }{=}}\{g(a)\mid a\in R\setminus \{0\}\}}$ ${\displaystyle g}$ ${\displaystyle s}$ ${\displaystyle \exists n\in \mathbb {N} }$ ${\displaystyle \operatorname {card} \{w_{i}\in W\mid w_{i}<s\}=n}$

properties

• The following applies to the evaluation functions of variants 1 and 2: Associated elements are evaluated identically, in particular the units are the minimally evaluated elements of the ring (apart from the zero element).
• It can be shown that every Euclidean ring has a minimal evaluation function ; this is of the above variant 2. There is even an algorithm for its iterative determination. However, finding a closed form for this minimal evaluation function is generally very laborious.
• Every Euclidean ring is a main ideal domain , because if there is a minimally valued element of an ideal , then it is , therefore, a main ideal . In particular, every Euclidean ring is factorial . ${\displaystyle a}$ ${\displaystyle I}$ ${\displaystyle I=(a)}$

Examples of Euclidean and non-Euclidean rings

• The ring of whole numbers is a Euclidean ring. The most natural choice for a Euclidean amount is The minimum Euclidean amount of an integer is given by the length of the binary representation of its absolute amount. ${\displaystyle \mathbb {Z} }$ ${\displaystyle g\colon \mathbb {Z} \to \mathbb {N} ,}$ ${\displaystyle x\mapsto |x|.}$
  
• Each body is a Euclidean ring with evaluation function and for ${\displaystyle K}$ ${\displaystyle g(0)=0}$ ${\displaystyle g(a)=1}$ ${\displaystyle a\in K\setminus \{0\}}$
• The polynomial ring over a body in a variable is a Euclidean ring, where the Euclidean norm is given by the degree of a polynomial ; this is already the minimal Euclidean norm. ${\displaystyle K[X]}$ ${\displaystyle K}$ ${\displaystyle X}$
• In contrast, z. B. the polynomial ring is not a Euclidean ring, since the ideal is not a main ideal . ${\displaystyle \mathbb {Z} [X]}$ ${\displaystyle (X,2)}$
• The ring of Gaussian numbers with the square norm (absolute value) is a Euclidean ring. ${\displaystyle \mathbb {Z} [\mathrm {i} ]}$ ${\displaystyle g:\mathbb {Z} [\mathrm {i} ]\to \mathbb {N} ,}$ ${\displaystyle (a+b\mathrm {i} )\mapsto a^{2}+b^{2}}$
• The ring is not Euclidean, because 4 and 4 have no GCF (two are “maximum common factors” and 2, but which are relatively prime ). ${\displaystyle \mathbb {Z} [{\sqrt {-3}}]}$ ${\displaystyle 2+2{\sqrt {-3}}}$ ${\displaystyle 1+{\sqrt {-3}}}$
• The totality ring of the square body with square-free is Euclidean with the square norm if and only if one of the following 21 numbers is: ${\displaystyle \mathbb {Q} ({\sqrt {d}})}$ ${\displaystyle d\in \mathbb {Z} }$ ${\displaystyle d}$
  -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73
  ${\displaystyle d=-1}$corresponds to the Gaussian numbers , the Eisenstein numbers and the ring . However, there are others, e.g. B. for which the ring is Euclidean with a different norm . ${\displaystyle d=-3}$ ${\displaystyle \mathbb {Z} [{\tfrac {-1+{\sqrt {-3}}}{2}}]}$ ${\displaystyle d=5}$ ${\displaystyle \mathbb {Z} [{\tfrac {1+{\sqrt {5}}}{2}}].}$
  ${\displaystyle d=69}$

Generalization to rings with zero divisors

The definitions can be transferred to rings that are not free of zero divisors . The above statements about the different variants of definitions remain, whereby the inequality for may have to be demanded. As in the zero divisor case, such rings have the property that every ideal is a main ideal . They are therefore a main ideal ring in the broader sense (“principal ideal ring” or PIR), but not a main ideal area (“principal ideal domain” or PID). ${\displaystyle g(xy)\geq g(x)}$ ${\displaystyle xy\neq 0}$

Generalization to non-commutative rings

The definitions can even be generalized to non-commutative rings, one then speaks of left or right euclidean. The Hurwitzquaternionen are an example of a non-commutative ring with its standard as is as the Euclidean norm both left and rechtseuklidisch.

literature

• Siegfried Bosch : Algebra . 7th edition. Springer-Verlag, 2009, ISBN 3-540-40388-4 , doi: 10.1007 / 978-3-540-92812-6 .
• Jantzen and Schwermer: Algebra . Springer, 2005, ISBN 3-540-21380-5 . doi: 10.1007 / 3-540-29287-X .
• Bernhard Hornfeck: Algebra . 3. Edition. deGruyter 1976, ISBN 3-11-006784-6

Individual evidence

1. ^ Kurt Meyberg: Algebra - Part 1 , Carl Hanser Verlag Munich, Vienna.
2. ^ ^{A b} Pierre Samuel : About Euclidean rings . In: Journal of Algebra . tape 19 , no. 2 , October 1971, ISSN  0021-8693 , p. 282-301 , doi : 10.1016 / 0021-8693 (71) 90110-4 .
3. ^ Bernhard Hornfeck: Algebra . 3rd edition, deGruyter 1976. ISBN 3-11-006784-6 , p. 142
4. ↑ László Rédei: On the question of the Euclidean algorithm in quadratic number fields . In: Mathematical Annals . 118, 1942, pp. 588-608.
5. ↑ Eric W. Weisstein : Quadratic Field . In: MathWorld (English).
6. ↑ Follow A048981 in OEIS
7. ↑ David A. Clark: A quadratic field which is euclidean but not norm-euclidean Archived from the original on January 29, 2015. Info: The archive link has been inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. In: Manuscripta Math. . 83, 1994, pp. 327-330. Retrieved January 8, 2013.