Euclidean domain: Difference between revisions

Many authors use other terms in place of "Euclidean function", such as "degree function", "valuation function", "gauge function" or "norm function".<ref name="DummitAlgebra">{{Cite book|title=Abstract Algebra|last1=Dummit|first1=David S.|last2=Foote|first2=Richard M.|publisher=Wiley|year=2004|isbn=9780471433347 |page=270}}</ref> Some authors also require the [[domain of a function|domain]] of the Euclidean function to be the entire ring {{mvar|R}};<ref name="DummitAlgebra"/> however, this does not essentially affect the definition, since (EF1) does not involve the value of {{math|''f''&thinsp;(0)}}. 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.

* {{math|'''Z'''[''ω'']}} (where {{math|''ω''}} is a [[Root of unity#General definition|primitive]] (non-[[real number|real]]) [[cube root of unity]]), the ring of [[Eisenstein integer]]s. Define {{math|''f''&thinsp;(''a'' + ''bω'') {{=}} ''a''{{sup|2}} − ''ab'' + ''b''{{sup|2}}}}, the norm of the Eisenstein integer {{math|''a'' + ''bω''}}.

* {{math|'''Z'''[''φ'']}}, the ring of [[golden integer]]s, where {{mvar|''φ''}} is the [[golden ratio]]. Define {{math|''f''&thinsp;(''a'' + ''bφ'') {{=}} ''a''{{sup|2}} + ''ab'' − ''b''{{sup|2}}}}, the norm of {{math|''a'' + ''bφ''}}.

*{{math|''K''{{brackets|''X''}}}}, the ring of [[formal power series]] over the field {{mvar|K}}. For each nonzero [[power series]] {{mvar|P}}, define {{math|''f''&thinsp;(''P'')}} as the [[order (power series)|order]] of {{mvar|P}}, that is the degree of the smallest power of {{mvar|X}} occurring in {{mvar|P}}. In particular, for two nonzero power series {{mvar|P}} and {{mvar|Q}}, {{math|''f''&thinsp;(''P'') ≤ ''f''&thinsp;(''Q'')}} if and only if {{mvar|P}} [[Formal power series#Dividing series|divides]] {{mvar|Q}}.

* The [[ring of integers]] of {{math|'''Q'''({{hairsp|{{sqrt|−19}}}})}}, consisting of the numbers {{math|{{sfrac|''a'' + ''b''{{sqrt|&minus;19}}|2}}}} where {{mvar|a}} and {{mvar|b}} 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>{{Cite journal |last=Motzkin |first=Th |date=December 1949 |title=The Euclidean algorithm |url=https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-55/issue-12/The-Euclidean-algorithm/bams/1183514381.full |journal=Bulletin of the American Mathematical Society |volume=55 |issue=12 |pages=1142–1146 |doi=10.1090/S0002-9904-1949-09344-8 |issn=0002-9904|doi-access=free }}</ref>

{{cite book|first=Pierre|last=Samuel|url=http://www.math.tifr.res.in/~publ/ln/tifr30.pdf|title=Lectures on Unique Factorization Domains|date=1964|publisher=Tata Institute of Fundamental Research|isbn= |pages=27–28|author-link=}}

*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 {{em|not}} Euclidean (because it doesn't have this property), but the cases ''d'' = −1, −2, −3, −7, −11 {{em|are}} Euclidean.<ref>{{Citation

| doi-access = free}}</ref>

Assuming the [[extended Riemann hypothesis]], if ''K'' is a finite [[field extension|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>{{Citation

   | journal = Proceedings of Symposia in Pure Mathematics

   | publisher = AMS

   | volume = 24 | pages = 321–332 | year = 1973

| doi = 10.1090/pspum/024/0337902 | isbn = 9780821814246 }}</ref>

[[Algebraic number field]]s ''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 [[Conjugate element (field theory)|conjugates]] of ''α''.  This norm maps the [[ring of integers]] of a number field ''K'', say ''O''_''K'', to the nonnegative [[Integer|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">{{cite book | title=Algebraic Numbers | publisher=Wiley-Interscience | author=Ribenboim, Paulo | year=1972 | isbn=978-0-471-71804-8}}</ref><ref name="HardyWright">{{cite book |first1=G.H. |last1=Hardy |first2=E.M. |last2=Wright |first3=Joseph |last3=Silverman |first4=Andrew |last4=Wiles |title=An Introduction to the Theory of Numbers |url=https://books.google.com/books?id=P6uTBqOa3T4C&pg=PP1 |date=2008 |publisher=Oxford University Press |edition=6th |isbn=978-0-19-921986-5 }}</ref>  Strictly speaking it is the ring of integers that is Euclidean since fields are trivially Euclidean domains, but the terminology is standard.

:−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 {{OEIS|id=A048981}}.<ref>{{cite book | last = LeVeque | first = William J. | author-link = William J. LeVeque | title = Topics in Number Theory|volume=I and II | publisher = Dover | year = 2002 | orig-year = 1956 | isbn = 978-0-486-42539-9 | zbl = 1009.11001 | pages = [https://archive.org/details/topicsinnumberth0000leve/page/ II:57,81] | url = https://archive.org/details/topicsinnumberth0000leve/page/ }}</ref>