Euclidean domain

Template:Short description In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination of them (Bézout's identity). In particular, the existence of efficient algorithms for Euclidean division of integers and of polynomials in one variable over a field is of basic importance in computer algebra.

It is important to compare the class of Euclidean domains with the larger class of principal ideal domains (PIDs). An arbitrary PID has much the same "structural properties" of a Euclidean domain (or, indeed, even of the ring of integers), but lacks an analogue of the Euclidean algorithm and extended Euclidean algorithm to compute greatest common divisors. So, given an integral domain Template:Mvar, it is often very useful to know that Template:Mvar has a Euclidean function: in particular, this implies that Template:Mvar is a PID. However, if there is no "obvious" Euclidean function, then determining whether Template:Mvar is a PID is generally a much easier problem than determining whether it is a Euclidean domain.

Every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is also a unique factorization domain. Euclidean domains appear in the following chain of class inclusions: Template:Commutative ring classes Template:Algebraic structures

Definition

Let Template:Mvar be an integral domain. A Euclidean function on Template:Mvar is a function Template:Mvar from Template:Mathto the non-negative integers satisfying the following fundamental division-with-remainder property:

• (EF1) If Template:Mvar and Template:Mvar are in Template:Mvar and Template:Mvar is nonzero, then there exist Template:Mvar and Template:Mvar in Template:Mvar such that Template:Math and either Template:Math or Template:Math.

A Euclidean domain is an integral domain which can be endowed with at least one Euclidean function. A particular Euclidean function Template:Mvar is not part of the definition of a Euclidean domain, as, in general, a Euclidean domain may admit many different Euclidean functions.

In this context, Template:Mvar and Template:Mvar are called respectively a quotient and a remainder of the division (or Euclidean division) of Template:Mvar by Template:Mvar. In contrast with the case of integers and polynomials, the quotient is generally not uniquely defined, but when a quotient has been chosen, the remainder is uniquely defined.

Most algebra texts require a Euclidean function to have the following additional property:

• (EF2) For all nonzero Template:Mvar and Template:Mvar in Template:Mvar, Template:Math.

However, one can show that (EF1) alone suffices to define a Euclidean domain; if an integral domain Template:Mvar is endowed with a function Template:Mvar satisfying (EF1), then Template:Mvar can also be endowed with a function satisfying both (EF1) and (EF2) simultaneously. Indeed, for Template:Mvar in Template:Math, one can define Template:Math as follows:<ref>Template:Citation</ref>

<math>f(a) = \min_{x \in R \setminus \{0\}} g(xa)</math>

In words, one may define Template:Math to be the minimum value attained by Template:Mvar on the set of all non-zero elements of the principal ideal generated by Template:Mvar.

A Euclidean function Template:Mvar is multiplicative if Template:Math and Template:Math is never zero. It follows that Template:Math. More generally, Template:Math if and only if Template:Mvar is a unit.

Notes on the definition

Many authors use other terms in place of "Euclidean function", such as "degree function", "valuation function", "gauge function" or "norm function".<ref name="DummitAlgebra">Template:Cite book</ref> Some authors also require the domain of the Euclidean function to be the entire ring Template:Mvar;<ref name="DummitAlgebra"/> however, this does not essentially affect the definition, since (EF1) does not involve the value of Template:Math. The definition is sometimes generalized by allowing the Euclidean function to take its values in any well-ordered set; this weakening does not affect the most important implications of the Euclidean property.

The property (EF1) can be restated as follows: for any principal ideal Template:Mvar of Template:Mvar with nonzero generator Template:Mvar, all nonzero classes of the quotient ring Template:Math have a representative Template:Mvar with Template:Math. Since the possible values of Template:Mvar are well-ordered, this property can be established by showing that Template:Math for any Template:Math with minimal value of Template:Math in its class. Note that, for a Euclidean function that is so established, there need not exist an effective method to determine Template:Mvar and Template:Mvar in (EF1).

Examples

Examples of Euclidean domains include:

• Any field. Define Template:Math for all nonzero Template:Mvar.
• Template:Math, the ring of integers. Define Template:Math, the absolute value of Template:Mvar.<ref>Template:Harvnb</ref>
• Template:Math, the ring of Gaussian integers. Define Template:Math, the norm of the Gaussian integer Template:Math.
• Template:Math (where Template:Math is a primitive (non-real) cube root of unity), the ring of Eisenstein integers. Define Template:Math, the norm of the Eisenstein integer Template:Math.
• Template:Math, the ring of polynomials over a field Template:Mvar. For each nonzero polynomial Template:Mvar, define Template:Math to be the degree of Template:Mvar.<ref>Template:Harvnb</ref>
• Template:Math, the ring of formal power series over the field Template:Mvar. For each nonzero power series Template:Mvar, define Template:Math as the order of Template:Mvar, that is the degree of the smallest power of Template:Mvar occurring in Template:Mvar. In particular, for two nonzero power series Template:Mvar and Template:Mvar, Template:Math if and only if Template:Mvar divides Template:Mvar.
• Any discrete valuation ring. Define Template:Math to be the highest power of the maximal ideal Template:Mvar containing Template:Mvar. Equivalently, let Template:Mvar be a generator of Template:Mvar, and Template:Mvar be the unique integer such that Template:Mvar is an associate of Template:Mvar, then define Template:Math. The previous example Template:Math is a special case of this.
• A Dedekind domain with finitely many nonzero prime ideals Template:Math. Define <math>f(x) = \sum_{i=1}^n v_i(x)</math>, where Template:Mvar is the discrete valuation corresponding to the ideal Template:Mvar.<ref>Template:Cite journal</ref>

Examples of domains that are not Euclidean domains include:

• Every domain that is not a principal ideal domain, such as the ring of polynomials in at least two indeterminates over a field, or the ring of univariate polynomials with integer coefficients, or the number ring Template:Math.
• The ring of integers of Template:Math, consisting of the numbers Template:Math where Template:Mvar and Template:Mvar are integers and both even or both odd. It is a principal ideal domain that is not Euclidean.This was proved by Theodore Motzkin and was the first case known.<ref>Template:Cite journal</ref>
• The ring Template:Math is also a principal ideal domain<ref>

Template:Cite book </ref> that is not Euclidean. To see that it is not a Euclidean domain, it suffices to show that for every non-zero prime <math>p\in A</math>, the map <math>A^\times\to(A/p)^\times</math> induced by the quotient map <math>A\to A/p</math> is not surjective.<ref> {{#invoke:citation/CS1|citation |CitationClass=web }} </ref>

Properties

Let R be a domain and f a Euclidean function on R. Then:

• R is a principal ideal domain (PID). In fact, if I is a nonzero ideal of R then any element a of I \ {0} with minimal value (on that set) of f(a) is a generator of I.<ref>Template:Harvnb</ref> As a consequence R is also a unique factorization domain and a Noetherian ring. With respect to general principal ideal domains, the existence of factorizations (i.e., that R is an atomic domain) is particularly easy to prove in Euclidean domains: choosing a Euclidean function f satisfying (EF2), x cannot have any decomposition into more than f(x) nonunit factors, so starting with x and repeatedly decomposing reducible factors is bound to produce a factorization into irreducible elements.
• Any element of R at which f takes its globally minimal value is invertible in R. If an f satisfying (EF2) is chosen, then the converse also holds, and f takes its minimal value exactly at the invertible elements of R.
• If Euclidean division is algorithmic, that is, if there is an algorithm for computing the quotient and the remainder, then an extended Euclidean algorithm can be defined exactly as in the case of integers.<ref>Template:Harvnb</ref>
• If a Euclidean domain is not a field then it has a non-unit element a with the following property: any element x not divisible by a can be written as x = ay + u for some unit u and some element y. This follows by taking a to be a non-unit with f(a) as small as possible. This strange property can be used to show that some principal ideal domains are not Euclidean domains, as not all PIDs have this property. For example, for d = −19, −43, −67, −163, the ring of integers of <math>\mathbf{Q}(\sqrt{d}\,)</math> is a PID which is Template:Em Euclidean (because it doesn't have this property), but the cases d = −1, −2, −3, −7, −11 Template:Em Euclidean.<ref>Template:Citation</ref>

However, in many finite extensions of Q with trivial class group, the ring of integers is Euclidean (not necessarily with respect to the absolute value of the field norm; see below). Assuming the extended Riemann hypothesis, if K is a finite extension of Q and the ring of integers of K is a PID with an infinite number of units, then the ring of integers is Euclidean.<ref>Template:Citation</ref> In particular this applies to the case of totally real quadratic number fields with trivial class group. In addition (and without assuming ERH), if the field K is a Galois extension of Q, has trivial class group and unit rank strictly greater than three, then the ring of integers is Euclidean.<ref>Template:Citation</ref> An immediate corollary of this is that if the number field is Galois over Q, its class group is trivial and the extension has degree greater than 8 then the ring of integers is necessarily Euclidean.

Norm-Euclidean fields

Algebraic number fields K come with a canonical norm function on them: the absolute value of the field norm N that takes an algebraic element α to the product of all the conjugates of α. This norm maps the ring of integers of a number field K, say O_K, to the nonnegative rational integers, so it is a candidate to be a Euclidean norm on this ring. If this norm satisfies the axioms of a Euclidean function then the number field K is called norm-Euclidean or simply Euclidean.<ref name="RibAlgNum">Template:Cite book</ref><ref name="HardyWright">Template:Cite book</ref> Strictly speaking it is the ring of integers that is Euclidean since fields are trivially Euclidean domains, but the terminology is standard.

If a field is not norm-Euclidean then that does not mean the ring of integers is not Euclidean, just that the field norm does not satisfy the axioms of a Euclidean function. In fact, the rings of integers of number fields may be divided in several classes:

• Those that are not principal and therefore not Euclidean, such as the integers of <math>\mathbf{Q}(\sqrt{-5}\,)</math>
• Those that are principal and not Euclidean, such as the integers of <math>\mathbf{Q}(\sqrt{-19}\,)</math>
• Those that are Euclidean and not norm-Euclidean, such as the integers of <math>\mathbf{Q}(\sqrt{69}\,)</math><ref>Template:Cite journal</ref>
• Those that are norm-Euclidean, such as Gaussian integers (integers of <math>\mathbf{Q}(\sqrt{-1}\,)</math>)

The norm-Euclidean quadratic fields have been fully classified; they are <math>\mathbf{Q}(\sqrt{d}\,)</math> where <math>d</math> takes the values

−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 (sequence A048981 in the OEIS).<ref>Template:Cite book</ref>

Every Euclidean imaginary quadratic field is norm-Euclidean and is one of the five first fields in the preceding list.

See also

• Valuation (algebra)

Notes

<references/>

References

• Template:Cite book
• Template:Cite journal