ユークリッド環
数学の特に抽象代数学および環論におけるユークリッド整域(ユークリッドせいいき、Euclidean domain)あるいはユークリッド環(ユークリッドかん、Euclidean ring)とは、「ユークリッド写像(次数写像)」とも呼ばれるある種の構造を備えた環で、そこではユークリッドの互除法を適当に一般化したものが行える。この一般化された互除法は整数に対するもともとの互除法アルゴリズムとほとんど同じ形で行うことができ、任意のユークリッド環において二元の最大公約数を求めるのに適用できる。特に、任意の二元に対してそれらの最大公約数は存在し、それら二元の線型結合として書き表される(ベズーの等式)。また、ユークリッド環の任意のイデアルは主イデアル(つまり、単項生成)であり、したがって算術の基本定理の適当な一般化が成立する。すなわち、任意のユークリッド環は一意分解環である。
ユークリッド環のクラスをより大きな主イデアル環 (PID) のクラスと比較することには大いに意味がある。勝手な PID はユークリッド環(あるいは実際には有理整数環を考えるので十分だが)と多くの「構造的性質」を共有しているが、しかしユークリッド環には明示的に与えられるユークリッド写像から得られる具体性があるのでアルゴリズム的な応用に有用である。特に、有理整数環や体上一変数の任意の多項式環が容易に計算可能なユークリッド写像を持つユークリッド環となることは、計算代数において基本的に重要な事実である。
そういったことから、整域 R が与えられたとき、R がユークリッド写像を持つことがわかるとしばしば非常に便利なのである。特に、そのとき R が PID であることが分かるが、しかし一般にはユークリッド写像の存在が「明らか」でないときに R が PID かどうかを決定する問題は、それがユークリッド環であるかどうかの決定よりも容易である。
整数全体の成す集合 Z に自然な演算として加法 + と乗法 × を考える。よく知られた整数に対する長除法は、Z における次の事実に強く依拠したものである:
除法の原理:「整数 a と 0 でない整数 b が与えられたとき、a  q × b + r を満たす整数の対 q, r が存在して、さらにそのようなものの中に r  0 または r < b を満たすものが取れる」
a および b が正である場合のみを考えることにすれば、r と b に関する制約条件は、単に「r  0 または r < b」と表すことができる。
任意の環にも加法と乗法の概念があるから、長除法の概念が任意の環で展開できないかを考えるのはある意味で自然なことだが、しかし剰余や商に関する条件(つまり「r  0 または r < b」)を単なる環の文脈で定義することは(もちろん、環上に何らの順序関係も定義されていないので)容易にはできない。こうして、各元に加法単位元 0 からの「距離」を導く(「次数」や「賦値」などとも呼ばれる)ある種のノルム必ずしも解析学でいうところのノルムの概念とは一致しない(特に解析学的なノルムのように一次の斉次函数になるとは限らない)。d を備えた環としてのユークリッド環の概念が導かれる。そうして、制約条件「r  0 または r < b」は「r  0 または d(r) < d(b)」で置き換わる。
ユークリッド環の裏にある本質的な考え方は、それが環であって「その任意の元 a と任意の非零元 b に対して、b の倍元の中に a に十分近い元が存在する」という性質を持つということである。もちろん、その環が可除環(あるいは体)であったならば、a × b−1 を倍率として左から b に掛ければ a が得られる。つまり、体や可除環については a に「ちょうど」一致するような b の倍元が存在する。もちろんこのことは一般の環では成立するとは限らない(例えば整数環 Z では成り立たない)から、制約条件は「b の倍元の中に a に十分近い元が存在する」というだけに緩めるのである。
自然な問いとして「次数はどのような集合に値を取るのか」という問題が考えられるが、多くの目的で(特にユークリッドの互除法が自由にできるという目的で)、自然数全体の成す集合 N に値をとるものと定めるのが普通である。自然数全体の成す集合 N の持つ、この文脈で重要になる性質は、それが整列集合を成すことである。
R を整域とする。R 上のユークリッド函数 f: R setminus 0 → N は除法の原理
(EF1): a および b は R の元で、b は零でないとすると、R の元 q および r で、a  bq + r, かつ r  0 または f(r) < f(b) のいずれかを満たすようなものが存在する
を満たす。少なくとも一つのユークリッド函数を備えた整域をユークリッド環と呼ぶ。ここで、ユークリッド環の構造が「特定」のユークリッド函数を持つことを要求していないことに注意すべきである。一般に一つのユークリッド環が複数のユークリッド函数を持ちうるが、そのようなものはどれでも一つあればよいのである。
多くの代数学の教科書では、ユークリッド函数がさらに次のような性質
(EF2): ともに零元でない R の任意の二元 a および b に対して f(a) ≤ f(ab) が成立する。
をも満たすことを仮定している。しかし、これは次のような意味で冗長である:
条件 (EF1) を満たす g を備えた任意の整域 R に対して、(EF1) および (EF2) をともに満たす f: R setminus 0 → N が取れる。
実際 a ∈ R setminus 0に対して f(a) を
f(a) = \min_{x \in R \smallsetminus \{0\} g(xa)
のように定めればこの f は条件を満たす。言葉で書けば、f(a) の値として、a が生成する主イデアルの非零元全体の成す集合上での g の最小値を与えるのである。
「ユークリッド函数」と言うかわりに「次数」、「賦値」、「ゲージ函数」、「ノルム」などといったような用語を用いているものも多いMay 2009(特に名称を提示せず、単に条件を満たす写像/函数とだけ言っている場合も少なくないが)。
ユークリッド函数の定義として任意の整列集合に値を取ることを許して一般化する場合もある。このように条件を弱めても、ユークリッド性の最も重要な部分には何も影響しない。またユークリッド函数の定義域から零元 0R を抜かず R 全体で定義されることを仮定する文献もある。この場合、例えば一変数多項式環 KX に対して通常の次数函数 deg は(ユークリッド函数の値域を N とするとそのままでは使えないが)零多項式 0 の次数 deg(0) = −∞ を最小値として付与した N ∪ −∞ に値をとるユークリッド函数にはなる。
条件 (EF1) を次のような形に書きなおすこともできる:
R の任意の非零元 b が生成する主イデアル I  (b) に対して、剰余環 R⁄I の零でない同値類は必ず f(r) < f(b) を満たす代表元 r を含む。
f の取りうる値は整列順序付けられているから、I に属さない元 r のうち、それが属する同値類において f(r) の値が最小となるものだけについて、必ず f(r) < f(b) が成り立っていることを示せば、この条件が満たされることが言える。この条件の下で確定されるユークリッド函数に対して (EF1) における q と r が効果的に決定できる方法が存在することは必要とされていないことに注意。
以下にユークリッド環の例を挙げる。
任意の体 K, f(x)  1 (∀x ≠ 0).
有理整数環 Z, f(n)  n(絶対値).
ガウス整数環 Zi, f(a + bi)  a2 + b2(ガウス整数の標準ノルム).
アイゼンシュタイン整数環 Zω (ω は 1 の虚立方根), f(a + bω)  a2 − ab + b2(アイゼンシュタイン整数の標準ノルム).
体 K 上の多項式環 KX, 零多項式でない任意の多項式 P に対して f(P)  deg(P) (多項式の次数).
体 K 上の形式冪級数環 KX, 非零冪級数 P に対し、f(P)  ord(P) (冪級数の位数: P に現れる(係数が 0 でない)項の最小次数)。特に二つの非零冪級数 P, Q に対して、f(P) ≤ f(Q) ⇔ P ! Q.
任意の離散賦値環, f(x) は x を含む極大イデアルの最高冪。上述の KX はこの特別の場合である。
有限個の非零素イデアル P1, …, Pn を持つデデキント整域, f(x)  i1 vi(x) (vi はイデアル Pi に対応する離散賦値)
整域 R とその上のユークリッド函数 f について:
R は主イデアル整域を成す。実は、I が R の非零イデアルならば、I setminus 0 の各元 a のうち f(a) が最小となるもので I は生成される。ここから R が一意分解環かつネーター環でもあることが帰結される。一般の主イデアル整域に比べ、分解の存在性(つまり R が分解整域であること)は、ユークリッド環の場合には特に容易に示せる。ユークリッド函数 f を (EF2) を満たすように取り、x は f(x) 個よりも多くの非単元因子に分解できないものとして、x から繰り返し既約因子に分解していけば、必ず既約元への分解が得られる。
f がそこで大域的な最小値を取るような R の点は必ず R の可逆元である。f が (EF2) を満たすように選ばれているならば、逆も成り立ち、しかも f は R の可逆元においてのみ最小値を取る。
ユークリッド性はアルゴリズム的である。すなわち、与えられた a, b(≠ 0) から「a  bq + r かつ [r  0 または f(r) < f(b)]」を満たす商 q と剰余 r を得る割り算アルゴリズムが存在するならば、この除法に関する意味での拡張ユークリッド互除法が定義できる。
全ての PID がユークリッドというわけではない。例えば d  −19, −43, −67, −163 のときの二次体 Q(d) の整数環は PID だがユークリッドでない。他方、d  −1, −2, −3, −7, −11 の場合にはユークリッドになる。
しかし、自明なイデアル類群を持つ Q の有限次拡大体の多くにおいて、その整数環はユークリッドになる(ただし、必ずしも体のノルムの絶対値に関してというわけではない。後述)。拡張リーマン予想 (ERH) を仮定すると、K が Q の有限次拡大で、かつ K の整数環が無限個の単元を持つ PID ならば、その整数環はユークリッドであることが従う。
特にこのことを自明な類群を持つ総実二次体の場合に応用できる。さらに(ERH の仮定なしに)体 K が Q のガロワ拡大で自明類群を持ち、かつ階数 (unit rank) が 3 より真に大きいならば、その整数環はユークリッドである。
ここから直ちに得られる系として、数体 K が Q 上ガロワで類群が自明かつ拡大次数が 8 より大きいならば、その整数環はユークリッドでなければならない。
代数体 K には体のノルム N(各代数的な元 α をその共軛元 (体論)全ての積へ写す写像)の絶対値による標準ノルム写像が存在する。このノルムは数体 K の整数環 OK を非負有理整数全体の成す集合のなかへ写すから、この環上のユークリッド函数の候補となり得る。このノルムがユークリッド函数の公理を満足するならば、数体 K はノルムに関してユークリッド的あるいはノルムユークリッド的 (norm-Euclidean) であるという。厳密に言えば、(体は自明なユークリッド環であるし)整数環のほうがユークリッド的だということを言っているのだが、このような語法が標準的である。
「体がノルムユークリッドでない」というのは、整数環がユークリッド環にならないことを必ずしも意味しない。単に体のノルムがユークリッド函数の公理を満足しないというだけである。実際、その整数環がユークリッド環になるが自身はノルムユークリッドでないような数体は存在する。簡単な例として二次体 Q(69) があるが、このような体を(特に二次体の場合に)全て決定する問題は重要な未解決問題である。
ノルムユークリッド二次体の分類は済んでおり、そのような二次体 Q(d) を成す整数 d の値は
−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 (OEIS: A048981).
であたえられる。