平成 10 年度卒業論文

多項式環上のイデアルの構成要素に関する問題

指導教官:木村俊一教官

広島大学理学部数学科学生番号:0771061J

森島聖

平成 11 年 2 月 10 日

序文

この卒業論文は、多項式環上のイデアルの構成要素に関する問題について考察することを目的とする。

4 年セミナーで、 1 年を通し、 Ideals, Varieties, and Algorithm (David Cox, John Little, Donal O’Shea 著) を、テキストとして読み進めてきた。この論文の内容は、その中で一番興味を抱いた話題についてまとめたものである。

1 章では、多項式環上のイデアルの構成要素に関する問題を提示するにあたっての必要な語句を定義した。この章の内容は、主に 2 年次の代数学の講義の内容とほとんど重複しており、執筆にあたり私自身にとって基礎理論の復習となった。 2 章、 3 章では、それぞれ 1 変数と多変数の場合にわけて、多項式環上のイデアルの構成要素に関する問題の解法について考察した。本質的には、多変数の場合についてのみ考察すれば、 1 変数の場合については考察する必要はないのだが、多変数の場合について考察するにあたっての基礎理論や、 1 変数の場合のみの特有の性質などがあったため、各々の場合について考察した。定理等の証明は、出来る限り記述しようとしたが、 Gröbner 基底の計算方法の証明については、そこだけで他のかなりの内容を論じなければならず、本題の目的から少しはずれるので、残念ながら割愛した。また、各章の最後に、数学コンピューターソフト Mathematica で作成したプログラムを用いて、具体例についての計算を行った。 1 年間のコンピューターセミナーでプログラミングにかなりの力を注いだので、それなりのものは作成出来たと思う。 (ちなみに、コンピューターセミナーでの研究成果は、広島大学理学部数学科の代数学、整数論講座のホームページ (http://top2.math.sci.hiroshima-u.ac.jp:80/algebra/index-j.html) にリンクしてある。 )

最後に、この論文は、多数の方々の助言、御指導のもとで完成することが出来ました。セミナーの指導教官であった木村俊一先生には、 3 年次の代数学の講義で、当時、代数学に対して抽象的で難しいというイメージを抱いていた私に、代数学のおもしろさや、奥深さを教えて頂き、さらに、 4 年セミナーやコンピューターセミナーで、多大な御指導を頂きました。また、高橋宣能先生には、忙しいながらも、木村先生の出張時にセミナーに参加して頂き、御指導を頂きました。大学院生の田上恵洋さん、百瀬智行さん、奥田俊一朗さん、川上高史さん、 4 年生の中川正史君、安本直史君、研究生の Duncan Tebbs さんには、コンピューターセミナーや、 4 年セミナーに出席して頂き、様々な助言を頂きました。そして最後に、 1 年間私と一緒にセミナーを進めてきた木村省吾さん、森村靖彦君には、助言を頂いたり、様々な面でお世話になり、楽しくセミナーを進めていくことが出来ました。 4 年間で、様々な面においてお世話になった他の諸先生方や、友人達も含めて、この場を借りて感謝の意を表します。

平成 11 年 2 月 10 日広島大学理学部数学科森島聖

目次

3

Chapter 1

準備

この章では、多項式環上のイデアルの構成要素に関する問題を提示するにあたっての、必要な語句を定義し、最後に、多項式環上のイデアルの構成要素に関する問題を提示する。

1.1 可換環と体

Definition 1.1.1 集合 R(≠ ∅) に、二つの演算加法:R × R ∋ (x, y) ⟶ x + y ∈ R 乗法:R × R ∋ (x, y) ⟶ xy ∈ R が、定義されていて

1. (x + y) + z = z + (y + z) (∀x, y, z ∈ R)

2. ∃0 ∈ R s.t. x + 0 = 0 + x = x (∀x ∈ R)

0 を加法単位元、または零元という。

3. ∃ − x ∈ R s.t. x + (−x) = (−x) + x = 0 (∀x ∈ R) −x を加法逆元という。

4. x + y = y + x (∀x, y ∈ R)

5. (xy)z = x(yz) (∀x, y, z ∈ R)

6. ∃1 ∈ R s.t. 1x = x1 = x (∀x ∈ R)

1 を乗法単位元という。

7. x(y + z) = xy + xz (∀x, y, z ∈ R)

(x + y)z = xz + yz (∀x, y, z ∈ R)

を満たすときに、 Rを環という。 Lemma 1.1.1 零元と乗法単位元は、一意である。

(Proof) 0,0′ を零元とすると、 0 = 0 + 0′ = 0′ より、零元は一意である。 1,1′ を乗法単位元とすると、 1 = 1 · 1′ = 1′ より、乗法単位元は一意である。 (証明終わり)

Lemma 1.1.2 ∀x ∈ R に対して、 x の加法逆元 −x は、一意である。

(Proof) y,y′ を x の加法逆元とすると、 y = y + 0 = y + (x + y′) = (y + x) + y′ = 0 + y′ = y′ より、 ∀x ∈ R に対して、 x の加法逆元は一意である。 (証明終わり)

Lemma 1.1.3 ∀x ∈ R に対し

1. 0 · x = x · 0 = 0

2. (−1) · x = x · (−1) = −x

(Proof)

1. 0 · x = (0 + 0) · x = 0 · x + 0 · x よって、 0 · x = 0 である。 x · 0 についても同様に示せる。

2. 0 = 0 · x = {1 + (−1)} · x = x + (−1) · x よって、 (−1) · x = −x である。 x · (−1) = −x についても同様に示せる。 (証明終わり)

Definition 1.1.2 R を環とする。 ∀x, y ∈ R に対し、 xy = yx を満たすとき、 R を可換環という。

Definition 1.1.3 R ≠ {0} を可換環とする。 ∀x ∈ R − {0} に対し、 ∃x^{−1} s.t. x · x^{−1} = x^{−1} · x = 1 を満たすとき、 R を体という。

1.2 イデアルと生成元

Definition 1.2.1 R を可換環とする。 R の部分集合 I が

1. 0 ∈ I

2. x, y ∈ I ⟹ x + y ∈ I

3. x ∈ I, a ∈ R ⟹ ax ∈ I を満たすとき、 I を R のイデアルという。

Proposition 1.2.1 R を可換環とする。 x_{1}, ⋯, x_{n} ∈ R に対し

S =< x_{1}, ⋯, x_{n} >= {∑_{i=1}^{n} a_{i}x_{i} | a_{1}, ⋯, a_{n} ∈ R}

とおくと、 S は、 R の、 x_{1}, ⋯, x_{n} を含む最小のイデアルになる。

(Proof)

1. 0 = 0x_{1} + 0x_{2} + ⋯ + 0x_{n} より、 0 ∈ S である。

2. a = a_{1}x_{1} + ⋯ + a_{n}x_{n} b = b_{1}x_{1} + ⋯ + b_{n}x_{n} (a, b ∈ S) とおくと a + b = (a_{1} + b_{1})x_{1} + ⋯ + (a_{n} + b_{n})x_{n} a_{i} + b_{i} ∈ R より、 a + b ∈ S である。

3. α ∈ R に対し αa = αa_{1}x_{1} + ⋯ + αa_{n}x_{n} αa_{i} ∈ Rより、 αa ∈ S である。

以上により、 S は R のイデアルである。

次に、 I を、 x_{1}, ⋯, x_{n} を含むイデアルとする。 s ∈ S とすると、 S の定義より

s = c_{1}x_{1} + ⋯ + c_{n}x_{n} (c_{1}, ⋯, c_{n} ∈ R)

と表せる。一方、 x_{1}, ⋯, x_{n} ∈ I より、 Definition 1.2.1 の 3 から、 c_{1}x_{1}, ⋯, c_{n}x_{n} ∈ I になる。よって、 Definition 1.2.1 の 2 から、 s = c_{1}x_{1} + ⋯ + c_{n}x_{n} ∈ I になる。以上により、 S は、 R の、 x_{1}, ⋯, x_{n} を含む最小のイデアルになる。 (証明終わり)

< x_{1}, ⋯, x_{n} > を、 x_{1}, ⋯, x_{n} で生成されるイデアル (または、有限生成イデアル)、特に、唯一の元 x で生成されるイデアル < x > を、単項イデアルという。また、 x_{1}, ⋯, x_{n} を、生成元という。

Proposition 1.2.2 R を可換環、 Λ を添え字の集合、 ∀λ ∈ Λ に対して、 x_{λ} ∈ R とする。このとき

T =< x_{λ} : λ ∈ Λ >= {∑_{λ∈Λ} a_{λ}x_{λ} | a_{λ} ∈ Rで、有限個の a_{λ}を除いて a_{λ} = 0}

とおくと、 T は、 R の、 {x_{λ} | λ ∈ Λ} を含む最小のイデアルになる。

(Proof)

1. 0 = ∑_{λ∈Λ} 0x_{λ} より、 0 ∈ T である。

2. a = ∑_{λ∈Λ} a_{λ}x_{λ} b = ∑_{λ∈Λ} b_{λ}x_{λ} (a, b ∈ T) とおくと

a_{λ} ∈ R で、有限個の a_{λ} を除いて a_{λ} = 0 かつ b_{λ} ∈ R で、有限個の b_{λ} を除いて b_{λ} = 0 より、 a + b = ∑_{λ∈Λ}(a_{λ} + b_{λ})x_{λ} となり、 a_{λ} + b_{λ} ∈ R で、有限個の a_{λ} + b_{λ} を除

いて a_{λ} + b_{λ} = 0 より、 a + b ∈ T である。

3. α ∈ R に対し αa = ∑_{λ∈Λ} αa_{λ}x_{λ} αa_{λ} ∈ R で、有限個の αa_{λ} を除いて αa_{λ} = 0 よ

り、 αa ∈ T である。

以上により、 T は R のイデアルである。

次に、 I を、 {x_{λ} | λ ∈ Λ} を含むイデアルとする。 t ∈ T とすると、 T の定義より

t = ∑_{λ∈Λ} c_{λ}x_{λ} (c_{λ} ∈ R で、有限個の c_{λ} を除いて c_{λ} = 0)

と表せる。一方、 ∀λ ∈ Λ に対して、 x_{λ} ∈ I より、 Definition 1.2.1 の 3 から、 ∀λ ∈ Λ に対して、 c_{λ}x_{λ} ∈ I になる。有限個の c_{λ}x_{λ} を除いて c_{λ}x_{λ} = 0 より、 Definition 1.2.1 の 2 か

ら、 t = ∑_{λ∈Λ} c_{λ}x_{λ} ∈ I になる。

以上により、 T は、 R の、 {x_{λ} | λ ∈ Λ} を含む最小のイデアルになる。 (証明終わり)

< x_{λ} : λ ∈ Λ > を、 {x_{λ} | λ ∈ Λ} で生成されるイデアルといい、 {x_{λ} | λ ∈ Λ} の元を、生成元という。また、 Λ が有限集合のとき、 < x_{λ} : λ ∈ Λ > は、明らかに有限生成イデアルになる。

Proposition 1.2.3 R を可換環とする。任意のイデアル I ⊂ R は、いくつか (無限個の場合もありうる) の I の元によって生成される。

(Proof) I そのものを添え字の集合とみて、 {x | x ∈ I} という集合を考える。これにより生成されるイデアルを、 J =< x : x ∈ I > とする。このとき、 I = J を示す。

(⊂) Proposition 1.2.2 より、 J は、 {x | x ∈ I} を含む最小のイデアルである。また、明らかに I = {x | x ∈ I} であるので、 I ⊂ J である。

(⊃) y ∈ J とすると

y = ∑_{x∈I} a_{x}x (a_{x} ∈ R で、有限個の a_{x} を除いて a_{x} = 0)

と表せる。 ∀x ∈ I に対して、 a_{x} ∈ R より、 a_{x}x ∈ I であり、有限個の a_{x}x を除いて a_{x}x = 0 より、 y = ∑_{x∈I} a_{x}x ∈ I になる。よって、 I ⊃ J である。以上により、 I = J である。よって、 I =< x : x ∈ I > と表せるので、 I は、 {x | x ∈ I} によって、生成される。 (証明終わり)

1.3 多項式と多項式環

Definition 1.3.1 文字 x_{1}, ⋯, x_{n} を変数 (不定元)、 α_{1}, ⋯, α_{n} を非負整数とする。このとき、積 x_{1}^{α_{1}} · x_{2}^{α_{2}} ⋯ x_{n}^{α_{n}} を、 x_{1}, ⋯, x_{n} の単項式といい、 α_{1} + ⋯ + α_{n} を単項式の総次数という。 ( 1 変数 (n = 1) の場合は、単に、単項式の次数という。 )

以後、簡略表記のために、 α = (α_{1}, ⋯, α_{n}) に対して、 x_{1}^{α_{1}} · x_{2}^{α_{2}} ⋯ x_{n}^{α_{n}} を x^{α} で表す。また、 x^{α} の総次数を、 |α| で表す。

Definition 1.3.2 kを体、 Z_{≥0}^{n} = {(a_{1}, ⋯, a_{n}) | a_{i} は非負整数 } とする。

f = ∑_{α} a_{α}x^{α} (α ∈ Z_{≥0}^{n}) (a_{α} ∈ k で、有限個の a_{α} を除いて、 a_{α} = 0)

を、 k の元を係数とする n 変数 x_{1}, ⋯, x_{n} 多項式という。さらに、このような任意の多項式全体の集合を k[x_{1}, ⋯, x_{n}] と表す。また、 k の元を定数という。

Definition 1.3.3 f = ∑_{α} a_{α}x^{α} ∈ k[x_{1}, ⋯, x_{n}] とする。

1. a_{α} を、単項式 x^{α} の係数という。

2. a_{α} ≠ 0 のとき、 a_{α}x^{α} を f の項という。

3. a_{α} ≠ 0 なる任意の α に対し、 |α| の最大値を、 f の総次数といい、 deg(f) と表す。 ( 1 変数 (n = 1) の場合は、単に、 f の次数という。 )

Definition 1.3.4 f = ∑_{α} a_{α}x^{α}, g = ∑_{α} b_{α}x^{α} ∈ k[x_{1}, ⋯, x_{n}] に対し

加法: f + g = ∑_{α}(a_{α} + b_{α})x^{α} ∈ k[x_{1}, ⋯, x_{n}]

乗法: fg = ∑_{γ} ( ∑_{α+β=γ} a_{α}b_{β}) x^{γ} ∈ k[x_{1}, ⋯, x_{n}]

(但し, α = (α_{1}, ⋯, α_{n}), β = (β_{1}, ⋯, β_{n}) に対し、 α + β := (α_{1} + β_{1}, ⋯, α_{n} + β_{n}) ) と定義する。

Definition 1.3.5 f, g ∈ k[x_{1}, ⋯, x_{n}] に対し、 g = fh なる h ∈ k[x_{1}, ⋯, x_{n}] が存在するとき、 f は g を割り切るという。 Theorem 1.3.1 k[x_{1}, ⋯, x_{n}] は、 Definition 1.3.4 で定義した、加法、乗法に関して可換環になる。以後、 k[x_{1}, ⋯, x_{n}] を多項式環という。

(Proof)

f = ∑_{α} a_{α}x^{α}, g = ∑_{α} b_{α}x^{α}, h = ∑_{α} c_{α}x^{α} ∈ k[x_{1}, ⋯, x_{n}] とする。

1. (f + g) + h = ∑_{α}(a_{α} + b_{α})x^{α} + ∑_{α} c_{α}x^{α} = ∑_{α}{(a_{α} + b_{α}) + c_{α}}x^{α} = ∑_{α}{a_{α} + b_{α} + c_{α}}x^{α}

= ∑_{α}{a_{α} + (b_{α} + c_{α})}x^{α} = ∑_{α} a_{α}x^{α} + ∑_{α}(b_{α} + c_{α})x^{α} = f + (g + h)

2. 0 ∈ k[x_{1}, ⋯, x_{n}] が、加法単位元になっている。

3. f に対し、 −f ∈ k[x_{1}, ⋯, x_{n}] が、加法逆元になっている。

4. f + g = ∑_{α}(a_{α} + b_{α})x^{α} = ∑_{α}(b_{α} + a_{α})x^{α} = g + f

5. (fg)h = ∑_{γ} ( ∑_{α+β=γ} a_{α}b_{β}) x^{γ} · ∑_{γ} c_{γ}x^{γ} = ∑_{r} { ∑_{p+q=r} ( ∑_{α+β=p} a_{α}b_{β}) c_{q}} x^{r}

= ∑_{r} { ∑_{p+q=r} ( ∑_{α+β=p} a_{α}b_{β}c_{q})} x^{r} = ∑_{r} { ∑_{α+β+q=r} a_{α}b_{β}c_{q}} x^{r}

= ∑_{r} { ∑_{α+p=r} a_{α} ( ∑_{β+q=p} b_{β}c_{q})} x^{r} = ∑_{α} a_{α}x^{α} · ∑_{α} ( ∑_{β+q=α} b_{β}c_{q}) x^{α} = f(gh)

6. 1 ∈ k[x_{1}, ⋯, x_{n}] が、乗法単位元になっている。

7. f(g + h) = ∑_{α} a_{α}x^{α} · ∑_{α}(b_{α} + c_{α})x^{α} = ∑_{γ} { ∑_{α+β=γ} a_{α}(b_{β} + c_{β})} x^{γ}

= ∑_{γ} ( ∑_{α+β=γ} a_{α}b_{β} + ∑_{α+β=γ} a_{α}c_{β}) x^{γ} = ∑_{γ} ( ∑_{α+β=γ} a_{α}b_{β}) x^{γ} + ∑_{γ} ( ∑_{α+β=γ} a_{α}c_{β}) x^{γ}

= fg + fh

(f + g)h = fh + gh も、 8. の乗法に関する可換性より、成り立つ。

8. fg = ∑_{γ} ( ∑_{α+β=γ} a_{α}b_{β}) x^{γ} = ∑_{γ} ( ∑_{β+α=γ} b_{β}a_{α}) x^{γ} = gf

以上により、 k[x_{1}, ⋯, x_{n}] は、可換環である。 (証明終わり)

1.4 多項式環上のイデアルの構成要素に関する問題

多項式環 k[x_{1}, ⋯, x_{n}] 上のイデアル I ⊂ k[x_{1}, ⋯, x_{n}] と、多項式 f ∈ k[x_{1}, ⋯, x_{n}] に対して、 f が I の元になっているかどうかという問題を、多項式環上のイデアルの構成要素に関する問題とする。 3 章で紹介する Hilbert の基底定理によって、任意のイデアル I は、有限生成イデアル (特に、 n = 1 のときは、単項イデアル) であらわされるので、実際は f が f_{1}, ⋯, f_{s} で生成されるイデアル < f_{1}, ⋯, f_{s} > の元になっているかどうかの判定法を、 2 章では、 1 変数多項式環 k[x] について、 3 章では、多変数 (n 変数) 多項式環 k[x_{1}, ⋯, x_{n}] について論じていく。そして、各章の最後には、数学コンピューターソフト Mathematica でプログラムを組み、具体例について、実際に計算をしていく。

1 変数多項式環上のイデアルの構成要素に関する問題

この章では、 1 変数多項式環 k[x] 上のイデアルの構成要素に関する問題について論じる。

2.1 1 変数多項式

Definition 2.1.1 f ∈ k[x] に対し

f = a_{m}x^{m} + a_{m−1}x^{m−1} + ⋯ + a_{0} (a_{m} ≠ 0 i.e. deg(f) = m)

とする。このとき、 a_{m}x^{m} を f の最高次の項といい、 LT (f) と表す。

Lemma 2.1.1 f, g ∈ k[x] を零でない多項式とする。このとき

deg(f) ≤ deg(g) ⟺ LT (f) は LT (g) を割り切る。

(Proof) LT (f) = ax^{m}, LT (g) = bx^{n} (a ≠ 0, b ≠ 0) とする。

(⟹) deg(f) ≤ deg(g) より m ≤ n である。

LT (g) = bx^{n} = ba^{−1}x^{n−m} · ax^{m} = ba^{−1}x^{n−m} · LT (f)

より、 LT (f) は LT (g) を割り切る。

(⟸) LT (f) は LT (g) を割り切るので ∃cx^{l} ∈ k[x] (c ≠ 0, l ≥ 0) s.t. LT (g) = cx^{l} · LT (f) = cx^{l} · ax^{m} = cax^{l+m} よって

deg(g) = deg(LT (g)) = deg(cax^{l+m}) = l + m = l + deg(f)

l ≥ 0 より、 deg(f) ≤ deg(g) である。

(証明終わり)

Lemma 2.1.2 f, g ∈ k[x] を零でない多項式とする。このとき

deg(fg) = deg(f) + deg(g)

(Proof)

f = ∑_{α} a_{α}x^{α}, g = ∑_{α} b_{α}x^{α} deg(f) = m, deg(g) = n とする。

fg = ∑_{γ} c_{γ}x^{γ} (c_{γ} = ∑_{α+β=γ} a_{α}b_{β}) で、 deg(fg) は定義より、 c_{γ} ≠ 0 なる任意の γ の最大値

である。 γ > m + n なる任意の γ に対しては、明らかに c_{γ} = 0 であり、 γ = m + n のときは、 c_{γ} = a_{m}b_{n} ≠ 0 より、 deg(fg) = m + n = deg(f) + deg(g) である。 (証明終わり)

Lemma 2.1.2 は、一般に、多変数多項式環についても成り立つ。

2.2 除法定理

Theorem 2.2.1 (除法定理) f, g ∈ k[x] (g ≠ 0) に対し

1. f = qg + r (r = 0 または deg(r) < deg(g)) を満たす q, r ∈ k[x] が存在する。 ( q を商、 r を余りという。 )

2. q, r は一意である。

(Proof)

1. f = 0 または deg(f) < deg(g) のとき、 q = 0, r = f とすると、 1 は成り立つ。

deg(f) ≥ deg(g) (f ≠ 0) のとき

\{ \begin{matrix}f = a_{m}x^{m} + a_{m−1}x^{m−1} + ⋯ + a_{0} \\ g = b_{n}x^{n} + b_{n−1}x^{n−1} + ⋯ + b_{0} \end{matrix} (a_{m} ≠ 0, b_{n} ≠ 0, m ≥ n)

とする。 m = 0 のとき、 f = a_{0}, g = b_{0} より、 q = a_{0}b_{0}^{−1}, r = 0 とすると、 1 は成り立つ。次数が m(≥ 1) より小さい f に対して、 1 は成り立つと仮定すると、 f_{0} = f − a_{m}b_{n}^{−1}x^{m−n}g は、 deg(f_{0}) < m より

f_{0} = q_{0}g + r_{0} (r_{0} = 0 または deg(r_{0}) < deg(g))

を満たす q_{0}, r_{0} が存在する。

f = f_{0} + a_{m}b_{n}^{−1}x^{m−n}g = q_{0}g + r_{0} + a_{m}b_{n}^{−1}x^{m−n}g = (q_{0} + a_{m}b_{n}^{−1}x^{m−n})g + r_{0}

より、 q = q_{0} + a_{m}b_{n}^{−1}x^{m−n}, r = r_{0} とすると、 1 は成り立つ。 2. f = qg + r = q′g + r′

(r = 0 または deg(r) < deg(g)) (r′ = 0 または deg(r′) < deg(g))

とすると

(q − q′)g = r′ − r となる。

q − q′ ≠ 0 と仮定すると、左辺は零でない多項式で次数は deg(g) 以上になる。一方、右辺は、零多項式か、次数が deg(g) より小さい多項式になるので、矛盾。よって、 q = q′, r = r′ になり、 q, r は一意である。

(証明終わり)

Proposition 2.2.1 k[x] 上のすべてのイデアルは、零でない定数倍を除いて、ある f ∈ k[x] によって一意に < f > と表される。 (つまり、単項イデアルになる。 )

(Proof) I ⊂ k[x] をイデアルとする。 I = {0} のとき、 I =< 0 > とおけば成り立つ。 I ≠ {0} のとき、 f を I の元の中の零でない多項式で、次数が最小のものとする。このとき、 < f >= I を示す。 (⊃) ∀af ∈< f > (a ∈ f[x]) に対し、イデアルの定義より、 af ∈ I である。

(⊂) g ∈ I とする。除法定理より

g = qf + r (r = 0 または deg(r) < deg(f))

と表せる。イデアルの定義より、 g, qf ∈ I に対し、 r = g − qf ∈ I r ≠ 0 ならば、 deg(r) < deg(f) より、 f の次数の最小性に矛盾する。よって、 r = 0 より、 g = qf ∈< f > である。

以上により、 < f >= I が示された。

次に、 f は、零でない定数倍を除いて一意であることを示す。

f = 0 ⟺ < f >= {0} より、 f = 0 のときは、零でない定数倍を除かなくても一意であるので、 f ≠ 0 とする。 < f >=< g > (g ≠ 0) とすると、 f ∈< g > より、 f = hg (h ∈ k[x], h ≠ 0) と表せる。 deg(f) = deg(hg) = deg(h) + deg(g) よって、 deg(f) ≥ deg(g) f と g の立場を入れかえると、同様に deg(f) ≤ deg(g) となる。よって、 deg(f) = deg(g) より、 deg(h) = 0 となるので、 h は零でない定数である。よって、 f は零でない定数倍を除いて一意である。 (証明終わり)

2.3 最大公約多項式

1 章の最後で、 3 章で紹介する Hilbert の基底定理により、多項式環上の任意のイデアルは、いくつかの有限個の生成元 f_{1}, ⋯, f_{s} で生成される (i.e. < f_{1}, ⋯, f_{s} > となる。 ) ということを述べた。しかし、前節で述べたように、 1 変数多項式環上においては、任意のイデアルは、さらに単項イデアル (i.e. ∃f ∈ k[x] s.t. < f >=< f_{1}, ⋯, f_{s} >) になっていることをみた。この節では、最大公約多項式を定義し、 f_{1}, ⋯, f_{s} の最大公約多項式が f になっていることを証明する。

Definition 2.3.1 f, g ∈ k[x] に対し、 h ∈ k[x] が

1. h は、 f, g を割り切る。

2. p ∈ k[x] を、 f, g を割り切るとすると、 p は h を割り切る。

を満たすとき、 h を最大公約多項式といい、 h = GCD(f, g) と表す。

Proposition 2.3.1 f, g ∈ k[x] とする。

1. GCD(f, g) は、零でない定数倍を除いて一意に存在する。

2. GCD(f, g) で生成される単項イデアルは、 < f, g > に等しい。

(Proof)

Proposition 2.2.1 より、 k[x] のイデアル < f, g > は、ある h ∈ k[x] に対し、 < f, g >=< h > と表せる。このとき、 h = GCD(f, g) を示す。 f, g ∈< h > より、 h は f, g を割り切る。よって、 Definition 2.3.1 の 1 を満たす。次に、 p ∈ k[x] を、 f, g を割り切るとすると

f = Cp g = Dp (C, D ∈ k[x])

と表せる。また、 h ∈< f, g > より

h = Af + Bg (A, B ∈ k[x])

と表せる。 h = ACp + BDp = (AC + BD)p となるので、 p は h を割り切る。よって、 Definition 2.3.1 の 2 を満たす。よって、 h = GCD(f, g) となる。これにより、存在性と 2 が示された。次に、 h′ = GCD(f, g) とすると、 Definition 2.3.1 の 2 より、 h, h′ はおのおのを割り切る。よって、 h′ は h の零でない定数倍になる。 (証明終わり)

Lemma 2.3.1 f ∈ k[x] に対し

GCD(f, 0) = GCD(0, f) = f

(Proof)

f は、 f、 0 を割り切る。また、 p ∈ k[x] を、 f、 0 を割り切るとすると、 p は f を割り切る。よって、 f = GCD(f, 0) = GCD(0, f) である。 (証明終わり)

最大公約多項式の概念は、 3 つ以上の多項式の場合に拡張出来る。 Definition 2.3.2 f_{1}, ⋯, f_{s} ∈ k[x] に対し、 h ∈ k[x] が

1. h は、 f_{1}, ⋯, f_{s} を割り切る。

2. p ∈ k[x] が、 f_{1}, ⋯, f_{s} を割り切るとすると、 p は h を割り切る。を満たすとき、 h を最大公約多項式といい、 h = GCD(f_{1}, ⋯, f_{s}) と表す。

Proposition 2.3.2 f_{1}, ⋯, f_{s} ∈ k[x] (s ≥ 2) とする。 1. GCD(f_{1}, ⋯, f_{s}) は、零でない定数倍を除いて一意に存在する。

2. GCD(f_{1}, ⋯, f_{s}) で生成される単項イデアルは、 < f_{1}, ⋯, f_{s} > に等しい。

3. s ≥ 3 のとき GCD(f_{1}, ⋯, f_{s}) = GCD(f_{1}, GCD(f_{2}, ⋯, f_{s}))

(Proof)

1,2 は、 Proposition 2.3.1 と同様の方法で証明出来る。よって、 3 のみを示す。 h = GCD(f_{2}, ⋯, f_{s}) とする。

f_{1} = f_{1} + 0 · f_{2} + ⋯ + 0 · f_{s} ∈< f_{1}, ⋯, f_{s} >

< h >=< f_{2}, ⋯, f_{s} > より、 h ∈< f_{2}, ⋯, f_{s} > なので、 h = a_{2}f_{2} + ⋯ + a_{s}f_{s} (a_{2}, ⋯, a_{s} ∈ k[x]) と表せる。よって、

h = 0 · f_{1} + a_{2}f_{2} + ⋯ + a_{s}f_{s} ∈< f_{1}, ⋯, f_{s} >

以上により、 < f_{1}, ⋯, f_{s} > ⊃ < f_{1}, h > となる。

逆に、

f_{1} = f_{1} + 0 · h ∈< f_{1}, h >

< h >=< f_{2}, ⋯, f_{s} > より、 f_{i} = b_{i}h (b_{i} ∈ k[x] 2 ≤ i ≤ s) と表せる。よって、

f_{i} = 0 · f_{1} + b_{i}h ∈< f_{1}, h >

以上により、 < f_{1}, ⋯, f_{s} > ⊂ < f_{1}, h > となる。

よって、 < f_{1}, ⋯, f_{s} >=< f_{1}, h > となる。

Proposition 2.3.2 の 2 より、 < GCD(f_{1}, ⋯, f_{s}) >=< GCD(f_{1}, h) > となり、最大公約多項式は、零でない定数倍を除いて一意より、 GCD(f_{1}, ⋯, f_{s}) = GCD(f_{1}, h) = GCD(f_{1}, GCD(f_{2}, ⋯, f_{s})) (証明終わり)

2.4 1 変数多項式環上のイデアルの構成要素に関する問題の解法

f, f_{1}, ⋯, f_{s} ∈ k[x] に対し、 fが < f_{1}, ⋯, f_{s} > の元であるか否かを調べたい。 h = GCD(f_{1}, ⋯, f_{s}) とすると、 < f_{1}, ⋯, f_{s} >=< h > となるので、この問題は、 f が < h > の元であるか否かに帰着される。 h = 0 ならば、 (つまり、 f_{1} = ⋯ f_{s} = 0 のとき ) < h > の元は、 0 のみになるので、 h ≠ 0 の場合について考える。除法定理により、 f = qh+r (r = 0 または deg(r) < deg(h)) と、一意に表せる。もし、 r = 0 ならば、 f = qh ∈< h >であり、 r ≠ 0 ならば、 deg(r) < deg(h) から、 r ∉< h > より、 f = qh + r ∉< h > である。

論理的には解決出来たが、実際問題として、 h, q, r の存在のみを証明して、求め方については論じていなかったので、具体例について計算が出来ない。そこで、除法定理における q, r と、最大公約多項式 h を求める計算方法を紹介する。

Proposition 2.4.1 f, g ∈ k[x] (g ≠ 0) に対し、除法定理による

f = qg + r (r = 0 または deg(r) < deg(g))

なる、 q, r ∈ k[x] を求める計算方法がある。

(Proof) m, n ∈ Z_{≥0} (n ≥ m) q_{0} = 0, r_{0} = f とし、 n ≥ m + 1 を満たす m について

\{ \begin{matrix}q_{m+1} = q_{m} + \frac{LT (r_{m})}{LT (g)} \\ r_{m+1} = r_{m} − \frac{LT (r_{m})}{LT (g)}g \end{matrix}

とする。但し、 n は、 ( r_{m} = 0 または deg(r_{m}) < deg(g) ) を初めて満たす m とする。このとき、 q_{n}, r_{n} が、求める q, r であることを示す。

1. まず、任意の m に対し、 f = q_{m}g + r_{m} であることを示す。

m = 0 のとき

q_{0}g + r_{0} = 0 · g + f = f

m ≥ 1 のとき、 m − 1 まで成り立つと仮定すると

q_{m}g + r_{m} = \{q_{m−1} + \frac{LT (r_{m−1})}{LT (g)}\} g + \{r_{m−1} − \frac{LT (r_{m−1})}{LT (g)}g\} = q_{m−1}g + r_{m−1} = f

よって、任意の m に対して、 f = q_{m}g + r_{m} より、 q_{n}, r_{n} は、 f = q_{n}g + r_{n} を満たす。

2. n の条件より、 r_{n} は、 ( r_{n} = 0 または deg(r_{n}) < deg(g) ) を満たすのは当たり前である。 3. 最後に、条件を満たす n が存在することを示す。 ( つまり、ある n で、 r_{n} = 0 また

は、 deg(r_{n}) < deg(g) が成り立ち、有限回の計算で、終わることを示す。 )

( r_{m} ≠ 0 かつ deg(r_{m}) ≥ deg(g) ) を満たす m に対し

r_{m} = a_{i}x^{i} + ⋯ + a_{0} ( a_{i} ≠ 0 )
g = b_{j}x^{j} + ⋯ + b_{0} ( b_{j} ≠ 0 )

とする。

r_{m+1} = r_{m} − \frac{LT (r_{m})}{LT (g)}g = a_{i}x^{i} + ⋯ + a_{0} − \frac{a_{i}x^{i}}{b_{j}x^{j}} (b_{j}x^{j} + ⋯ + b_{0})

= a_{i−1}x^{i−1} + ⋯ + a_{0} − (\frac{a_{i}x^{i}}{b_{j}x^{j}} b_{j−1}x^{j−1} + ⋯ + \frac{a_{i}x^{i}}{b_{j}x^{j}} b_{0})

= a_{i−1}x^{i−1} + ⋯ + a_{0} − \frac{a_{i}}{b_{j}} (b_{j−1}x^{i−1} + ⋯ + b_{0}x^{i−j})

よって、 r_{m+1} は、次数が下がるか、 0 になる。このことをくり返すことにより、 ( r_{n} = 0 または deg(r_{n}) < deg(g) ) を満たす n が存在することが示される。

以上により、 q_{n}, r_{n} が、求める q, r であることが示された。 (証明終わり)

Proposition 2.4.2 f_{1}, ⋯, f_{s} ∈ k[x] に対し

h = GCD(f_{1}, · · · .f_{s})

を満たす h を求める計算方法がある。

(Proof)

まず、 f、 g ∈ k[x] に対する GCD(f, g) を求める計算方法があることを示す。 g = 0 ならば、 GCD(f, g) = GCD(f, 0) = f より、求まるので、 g ≠ 0 とする。除法定理により

f = q_{1}g + r_{1} (r_{1} = 0 または deg(r_{1}) < deg(g))

と表せる。まず、 < f, g >=< f − q_{1}g, g > を示す。

f = 1 · (f − q_{1}g) + q_{1} · g ∈< f − q_{1}g, g >
g = 0 · (f − q_{1}g) + 1 · g ∈< f − q_{1}g, g >

以上により、 < f, g >⊂< f − q_{1}g, g > となる。

f − q_{1}g = 1 · f − q_{1} · g ∈< f, g >
g = 0 · f + 1 · g ∈< f, g >

以上により、 < f, g >⊃< f − q_{1}g, g > となる。よって、 < f, g >=< f − q_{1}g, g > が示された。このことより

GCD(f, g) = GCD(f − q_{1}g, g) = GCD(r_{1}, g) = GCD(g, r_{1})

(r_{1} = 0 または deg(r_{1}) < deg(g))

r_{1} = 0 ならば、 GCD(f, g) = GCD(g, 0) = g より、求まる。 r_{1} ≠ 0 とする。同様に除法定理により

g = q_{2}r_{1} + r_{2} (r_{2} = 0 または deg(r_{2}) < deg(r_{1}))

同様に

GCD(g, r_{1}) = GCD(r_{1}, r_{2}) (r_{2} = 0 または deg(r_{2}) < deg(r_{1}))

同様にくり返していくと、途中で r_{i} = 0 なる i が存在する。もしくは

deg(g) > deg(r_{1}) > deg(r_{2}) > deg(r_{3}) > · · · · · ·

のように次数が下がっていく。もし、 deg(r_{j}) = 0 まで次数が下がったとすると、 r_{j} は定数より、 r_{j} は r_{j−1} を割り切るので r_{j+1} = 0 となる。よって、 r_{n} = 0 なる n が必ず存在する。よって

GCD(f, g) = GCD(g, r_{1}) = GCD(r_{1}, r_{2}) = ⋯ = GCD(r_{n−1}, r_{n}) = GCD(r_{n−1}, 0) = r_{n−1}

となり、 GCD(f, g) が求まる。

以上により、 GCD(f, g) の計算方法がわかった。 Proposition 2.3.2 の 3 より、 h = GCD(f_{1}, ⋯, f_{s}) は、 2 つの多項式の最大公約多項式を求める計算を、有限回 (s − 1 回 ) くり返すことにより、求まる。 (証明終わり)

次に、数学コンピューターソフト Mathematica で、この 2 つの計算方法を利用して組んだプログラムを用いて、具体例を計算してみる。但し、プログラム上では、 1 変数多項式 f = a_{n}x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{0} (a_{n} ≠ 0) を、 {a_{0}, a_{1}, ⋯, a_{n}} のように、係数のリストで表して処理をする。

以下に、プログラムの紹介をする。

In[1]:=ListDiv[f_,g_]:=ListDiv[f,g]=Module[{q,r,deg,coe},
                       q=Table[0,{Max[Length[f]-Length[g]+1,1]}];r=f;
                       While[r=!={0}&&Length[g]<=Length[r],
                       deg=Length[r]-Length[g]; coe=r[[-1]]/g[[-1]];
                       q=ReplacePart[q,coe+q[[deg+1]],deg+1];
                       r=r-Join[Table[0,{deg}],coe*g];
                       While[Length[r]>=1&&r[[-1]]==0,r=Delete[r,-1]]];
                       If[r=={},r={0}];{q,r}]

ListDiv[f, g] ( 但し、 g ≠ 0) と入力すると、

f = qg + r (r = 0 または deg(r) < deg(g))

を満たす {q, r} を出力する。

In[2]:=ListGCD[f_,g_]:=ListGCD[f,g]=Module[{h,s,rem、 h1},
                       h=f;s=g;
                       While[s=!={0},rem=ListDiv[h,s][[2]];h=s;s=rem];
                       h/(h[[-1]])]
In[3]:=ListGCDs[f_]:=ListGCDs[f]=Module[{s,h},s=Length[f];h=f[[1]];
                     Do[h=ListGCD[h,f[[i]]],{i,2,s}];h]

ListGCDs[{f_{1}, ⋯, f_{s}}] と入力すると、 GCD(f_{1}, ⋯, f_{s}) を出力する。

以下に、具体例をあげる。 Example 1 Q を有理数体とし

\{ \begin{matrix}f = x^{3} + 4x^{2} + 3x − 7 \\ f_{1} = x^{3} − 3x + 2 \\ f_{2} = x^{4} − 1 \\ f_{3} = x^{6} − 1 \end{matrix} f, f_{1}, f_{2}, f_{3} ∈ Q[x]

とする。

In[4]:=f={-7,3,4,1};f1={2,-3,0,1};f2={-1,0,0,0,1};f3={-1,0,0,0,0,0,1}

f が < f_{1}, f_{2}, f_{3} > の元であるか否かを調べる。

In[5]:=h=ListGCDs[{f1,f2,f3}]
Out[5]={-1,1}

< f_{1}, f_{2}, f_{3} >=< h > より、 f が < h > の元であるかどうかを調べる。

In[6]:=ListDiv[f,h]
Out[6]={{8,5,1},{1}}

余りが 1 ≠ 0 なので、 f ∉< h > より、 f ∉< f_{1}, f_{2}, f_{3} >である。 Example 2

\{ \begin{matrix}f = x^{2} − 4 \\ f_{1} = x^{3} + x^{2} − 4x − 4 \\ f_{2} = x^{3} − x^{2} − 4x + 4 \\ f_{3} = x^{3} − 2x^{2} − x + 2 \end{matrix} f, f_{1}, f_{2}, f_{3} ∈ Q[x]

In[7]:=f={-4,0,1};f1={-4,-4,1,1};f2={4,-4,-1,1};f3={2,-1,-2,1}

f が < f_{1}, f_{2}, f_{3} > の元であるか否かを調べる。

In[8]:=h=ListGCDs[{f1,f2,f3}]
Out[8]={-2,1}

< f_{1}, f_{2}, f_{3} >=< h > より、 f が < h > の元であるかどうかを調べる。

In[9]:=ListDiv[f,h]
Out[9]={{2,1},{0}}

余りが 0 なので、 f ∈< h > より、 f ∈< f_{1}, f_{2}, f_{3} >である。 Example 3

\{ \begin{matrix}f = x^{5} − 3x^{4} − 1 \\ f_{1} = x^{4} + x^{2} + 1 \\ f_{2} = x^{4} − x^{2} − 2x − 1 \\ f_{3} = x^{3} − 1 \\ f_{4} = x^{3} − 3x^{2} − 3x − 4 \end{matrix} f, f_{1}, f_{2}, f_{3}, f_{4} ∈ Q[x]

とする。

In[10]:=f={-1,0,0,0,-3,1};f1={1,0,1,0,1};f2={-1,-2,-1,0,1};f3={-1,0,0,1};
        f4={-4,-3,-3,1}

f が < f_{1}, f_{2}, f_{3}, f_{4} > の元であるか否かを調べる。

In[11]:=h=ListGCDs[{f1,f2,f3,f4}]
Out[11]={1,1,1}

< f_{1}, f_{2}, f_{3}, f_{4} >=< h > より、 f が < h > の元であるかどうかを調べる。

In[12]:=ListDiv[f,h]
Out[12]={{1,3,-4,1},{-2,-4}}

余りが −4x − 2 ≠ 0 なので、 f ∉< h > より、 f ∉< f_{1}, f_{2}, f_{3}, f_{4} >である。 Example 4

\{ \begin{matrix}f = x^{5} − 1 \\ f_{1} = x^{3} + 2x^{2} − x − 2 \\ f_{2} = x^{3} − 2x^{2} − x + 2 \\ f_{3} = x^{3} − x^{2} − 4x + 4 \\ f_{4} = x^{4} − 1 \end{matrix} f, f_{1}, f_{2}, f_{3}, f_{4} ∈ Q[x]

In[13]:=f={-1,0,0,0,0,1};f1={-2,-1,2,1};f2={2,-1,-2,1};f3={4,-4,-1,1};
        f4={-1,0,0,0,1}

f が < f_{1}, f_{2}, f_{3}, f_{4} > の元であるか否かを調べる。

In[14]:=h=ListGCDs[{f1,f2,f3,f4}]
Out[14]={-1,1}

< f_{1}, f_{2}, f_{3}, f_{4} >=< h > より、 f が < h > の元であるかどうかを調べる。

In[15]:=ListDiv[f,h]
Out[15]={{1,1,1,1,1},{0}}

余りが 0 なので、 f ∈< h > より、 f ∈< f_{1}, f_{2}, f_{3}, f_{4} >である。 Example 5

\{ \begin{matrix}f = 3x^{4} − x^{2} − 4 \\ f_{1} = x^{3} + x^{2} + x + 1 \\ f_{2} = x^{3} − x^{2} + x − 1 \\ f_{3} = 2x^{3} + 3x^{2} + 2x + 3 \\ f_{4} = x^{4} + 2x^{2} + 1 \end{matrix} f, f_{1}, f_{2}, f_{3}, f_{4} ∈ Q[x]

とする。

In[16]:=f={-4,0,-1,0,3};f1={1,1,1,1};f2={-1,1,-1,1};f3={3,2,3,2};
        f4={1,0,2,0,1}

f が < f_{1}, f_{2}, f_{3}, f_{4} > の元であるか否かを調べる。

In[17]:=h=ListGCDs[{f1,f2,f3,f4}]
Out[17]={1,0,1}

< f_{1}, f_{2}, f_{3}, f_{4} >=< h > より、 f が < h > の元であるかどうかを調べる。

In[18]:=ListDiv[f,h]
Out[18]={{-4,0,3},{0}}

余りが 0 なので、 f ∈< h > より、 f ∈< f_{1}, f_{2}, f_{3}, f_{4} >である。

多変数多項式環上のイデアルの構成要素に関する問題

この章では、多変数多項式環 k[x_{1}, ⋯, x_{n}] 上のイデアルの構成要素に関する問題について論じる。

3.1 単項式順序

この節では、単項式に便宜よく順序づけが出来る単項式順序を紹介する。 Definition 3.1.1 集合 X 上の関係 > が、 X の任意の 2 つの元 α, β に対し

α > β α = β β > α

のどれか 1 つだけを必ず満たし、 X の任意の元 α, β, γ に対し

α > β β > γ ⟹ α > γ

を満たすとき、関係 > を、 X 上の全順序 (または線形順序) という。 Definition 3.1.2 集合 X 上の関係 > に対し、 X の空でない任意の部分集合に、 > における最小要素が存在するとき、関係 > を、 X 上の整列順序という。 ( 但し、一般に関係 > に対し、 α > β のとき、 β は α より小さいという。 ) Definition 3.1.3 Z_{≥0}^{n} 上の関係 > が

1. > は、全順序である。

2. > は、整列順序である。

3. ∀α, β, γ ∈ Z_{≥0}^{n} に対し、 α > β ⟹ α + γ > β + γ を満たすとき、 > を、 Z_{≥0}^{n} 上の単項式順序という。

Lemma 3.1.1 Z_{≥0}^{n} 上の関係 > に対し

> は、整列順序である。 ⟺ Z_{≥0}^{n} 上の任意の単調減少要素列は、有限個で終わる。

(Proof) 対遇をとって

> は、整列順序でない。 ⟺ 無限に続く Z_{≥0}^{n} 上の単調減少要素列が存在する。

を証明する。 (⟹) > が整列順序でないので、最小要素を持たない Z_{≥0}^{n} の空でない部分集合 S が存在する。 α(1) ∈ S とする。 α(1) は最小要素でないので

∃α(2) ∈ S s.t. α(1) > α(2)

α(2) は最小要素でないので

∃α(3) ∈ S s.t. α(2) > α(3)

同様にくり返すことによって、無限に続く Z_{≥0}^{n} 上の単調減少要素列

α(1) > α(2) > α(3) > α(4) > · · · · · ·

が出来る。 (⟸)

α(1) > α(2) > α(3) > α(4) > · · · · · ·

を、無限に続く Z_{≥0}^{n} 上の単調減少要素列とする。このとき、集合 {α(1), α(2), α(3), α(4), · · · · · ·} は、最小要素を持たない Z_{≥0}^{n} の空でない部分集合になる。よって、 > は、整列順序でない。 (証明終わり)

次に、単項式順序の例である、辞書式順序を紹介する。

Definition 3.1.4 ∀α, β ∈ Z_{≥0}^{n} に対し、 α − β ∈ Z^{n} の 0 でない一番左にくる要素が正の数のとき、 α >_{lex} β と表し、 >_{lex} を、 Z_{≥0}^{n} 上の辞書式順序という。

Proposition 3.1.1 Z_{≥0}^{n} 上の辞書式順序は、単項式順序である。

(Proof)

1. Z_{≥0} 上の不等号が全順序より、 >_{lex} の定義から明らかに、 Z_{≥0}^{n} の任意の 2 つの元 α, β

は

α >_{lex} β α = β β >_{lex} α

のどれか 1 つだけを必ず満たす。また、 α, β, γ ∈ Z_{≥0}^{n} に対し、 α >_{lex} β β >_{lex} γ と仮定すると、 α >_{lex} β より、 α − β の 0 でない一番左の要素 p は、正の数である。 ( 左から i 番目とする。 ) また、 β >_{lex} γ より、 β − γ の 0 でない一番左の要素 q は、正の数である。 (左から j 番目とする。 )

α − γ = (α − β) + (β − γ)

より、 α − γ の 0 でない一番左の要素は

i = j のとき p + q > 0
i < j のとき p > 0
i > j のとき q > 0

より、正の数になる。よって、 α >_{lex} γ になる。以上により、 >_{lex} は、全順序である。

2. >_{lex} が整列順序でないと仮定する。 Lemma 3.1.1 より、無限に続く Z_{≥0}^{n} 上の単調減

少要素列

α(1) >_{lex} α(2) >_{lex} α(3) >_{lex} α(4) >_{lex} · · · · · ·

が存在する。辞書式順序の定義より

α(1), α(2), α(3), α(4), · · · · · ·

の第 1 要素は、単調非増加非負整数列になる。よって、ある自然数 m_{1} に対して、 α(m_{1}) から先は第 1 要素がすべて同じ値になる。次に、 α(m_{1}) から先の第 2 要素に注目する。先程と同様に

α(m_{1}), α(m_{1} + 1), α(m_{1} + 2), α(m_{1} + 3), · · · · · ·

の第 2 要素は、単調非増加非負整数列になる。よって、ある自然数 m_{2}(≥ m_{1}) に対して、 α(m_{2}) から先は第 2 要素がすべて同じ値になる。このことを第 n 要素までくり返すと、ある自然数 m_{n}(≥ ⋯ ≥ m_{2} ≥ m_{1}) に対して、 α(m_{n}) から先は第 n 要素がすべて同じ値になる。 α(m_{n}) から先の第 1 要素から第 n − 1 要素は、すでに、すべて同じ値になっているので

α(m_{n}) = α(m_{n} + 1) = α(m_{n} + 2) = α(m_{n} + 3) = · · · · · ·

このことは

α(m_{n}) >_{lex} α(m_{n} + 1) >_{lex} α(m_{n} + 2) >_{lex} α(m_{n} + 3) >_{lex} · · · · · ·

に矛盾する。よって、 >_{lex} は、整列順序である。 3. α >_{lex} β を満たす ∀α, β ∈ Z_{≥0}^{n} に対し、 >_{lex} の定義より、 α − β の 0 でない一番左

の要素は正の数である。よって、 ∀γ ∈ Z_{≥0}^{n} に対し

(α + γ) − (β + γ) = α − β

より、 α + γ >_{lex} β + γ になる。以上により、 >_{lex} は、単項式順序である。 (証明終わり) Definition 3.1.5 f = ∑_{α} a_{α}x^{α} ∈ k[x_{1}, ⋯, x_{n}] を零でない多項式とし、 > を単項式順序とする。このとき

1. multideg(f) = max{α ∈ Z_{≥0}^{n} | a_{α} ≠ 0} を、 f の多重次数という。 ( 但し、 max は、 > による最大要素を意味する。 )

2. LC(f) = a_{multideg(f)} を、 f の最高次の係数という。

3. LM(f) = x^{multideg(f)} を、 f の最高次の単項式という。

4. LT (f) = LC(f) · LM(f) を、 f の最高次の項という。 Lemma 3.1.2 f ∈ k[x_{1}, ⋯, x_{n}] を零でない多項式とし、 > を単項式順序とする。

1. m を単項式とすると、 LT (m · f) = m · LT (f)

2. g ∈ k[x_{1}, ⋯, x_{n}] を零でない多項式とすると、 LT (f · g) = LT (f) · LT (g) (Proof)

f = a_{α(p)}x^{α(p)} + a_{α(p−1)}x^{α(p−1)} + ⋯ + a_{α(1)}x^{α(1)} (∀a_{α(i)} ≠ 0)
( α(p) > α(p − 1) > ⋯ > α(1) )

とする。

1. m = x^{α} を単項式とする。

m · f = a_{α(p)}x^{α(p)+α} + a_{α(p−1)}x^{α(p−1)+α} + ⋯ + a_{α(1)}x^{α(1)+α}

単項式順序の定義より

α(p) + α > α(p − 1) + α > ⋯ > α(1) + α

よって、 LT (m · f) = a_{α(p)}x^{α(p)+α} になる。

一方、 m · LT (f) = x^{α} · a_{α(p)}x^{α(p)} より、 LT (m · f) = m · LT (f) である。

g = b_{β(q)}x^{β(q)} + b_{β(q−1)}x^{β(q−1)} + ⋯ + b_{β(1)}x^{β(1)} (∀b_{β(i)} ≠ 0)
( β(q) > β(q − 1) > ⋯ > β(1) )

とする。

f · g = ∑_{i=1}^{q}{(a_{α(p)}x^{α(p)} + a_{α(p−1)}x^{α(p−1)} + ⋯ + a_{α(1)}x^{α(1)}) · b_{β(i)}x^{β(i)}}

= ∑_{i=1}^{q}{x^{β(i)} · (a_{α(p)}b_{β(i)}x^{α(p)} + a_{α(p−1)}b_{β(i)}x^{α(p−1)} + ⋯ + a_{α(1)}b_{β(i)}x^{α(1)})}

1 より、 ∑ の中の最高次の項は、 a_{α(p)}b_{β(i)}x^{α(p)+β(i)} になる。単項式順序の定義より

α(p) + β(q) > α(p) + β(q − 1) > ⋯ > α(p) + β(1)

よって、 LT (f · g) = a_{α(p)}b_{β(q)}x^{α(p)+β(q)} になる。一方、 LT (f) · LT (g) = a_{α(p)}x^{α(p)} · b_{β(q)}x^{β(q)} より、 LT (f · g) = LT (f) · LT (g) である。

(証明終わり) Lemma 3.1.3 f, g ∈ k[x_{1}, ⋯, x_{n}] を零でない多項式とし、 > を単項式順序とする。

1. multideg(fg) = multideg(f) + multideg(g)

2. f + g ≠ 0 のとき、 multideg(f + g) ≤ max{ multideg(f), multideg(g) } (但し、 β < α とは、 α > β のこととし、 ≤ は、 < か = のどちらか一方が成り立つことを意味する。 )

(Proof)

1. Lemma 3.1.2 の 2 より、明らかである。

2. multideg(f + g) > max{ multideg(f), multideg(g) } と仮定する。

f = ∑_{α} a_{α}x^{α}, g = ∑_{α} b_{α}x^{α} とすると

f + g = ∑_{α} c_{α}x^{α} ( c_{α} = a_{α} + b_{α} )

β = max{ multideg(f), multideg(g) }, γ = multideg(f + g) とすると、 ∀α > β に対し、 a_{α} = 0 かつ b_{α} = 0 より c_{α} = 0 となる。仮定より、 γ > β であるから、 c_{γ} = 0 になる。このことは、 c_{γ} ≠ 0 に矛盾する。よって、 multideg(f + g) ≤ max{ multideg(f), multideg(g) } である。

(証明終わり)

以後、単項式順序を固定して論じていく。

3.2 多変数多項式の除法定理

Theorem 3.2.1 (多変数多項式の除法定理)f, f_{1}, ⋯, f_{s} ∈ k[x_{1}, ⋯, x_{n}] ( ∀f_{i} ≠ 0 ) に対し

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r (r = 0 または ∀LT (f_{i}) は r のすべての項を割り切らない )

を満たす a_{1}, ⋯, a_{s}, r ∈ k[x_{1}, ⋯, x_{n}] が存在する。 ( r を余りという。 )

(Proof) 5 節で、この定理における a_{1}, ⋯, a_{s}, r ∈ k[x_{1}, ⋯, x_{n}] を求める計算方法があることを、今まで論じてきたことのみを用いて証明するので、この節では証明を省略する。

以後、この定理を仮定して論じていく。

3.3 単項式イデアルと Dickson の補題

Definition 3.3.1 I ⊂ k[x_{1}, ⋯, x_{n}] をイデアルとする。 Z_{≥0}^{n} の空でない部分集合 A によって

I =< x^{α} : α ∈ A >

と表せるとき、 I を単項式イデアルという。

Lemma 3.3.1 ∀β ∈ Z_{≥0}^{n} とする。単項式イデアル I =< x^{α} : α ∈ A >⊂ k[x_{1}, ⋯, x_{n}] に対し

x^{β} ∈ I ⟺ ∃α ∈ A s.t. x^{α} は x^{β} を割り切る。

(Proof) (⟸) ある α ∈ A に対し、 x^{α} は x^{β} を割り切るので

x^{β} = x^{γ} · x^{α} ( γ ∈ Z_{≥0}^{n} )

と表せる。 x^{α} ∈ I より、イデアルの定義から、 x^{β} ∈ I である。

(⟹) x^{β} ∈ I より

x^{β} = ∑_{i=1}^{s} h_{i}x^{α(i)} ( h_{i} ∈ k[x_{1}, ⋯, x_{n}] α(i) ∈ A )

と表せる。 h_{i} = ∑_{γ} a_{iγ}x^{γ} とおくと

x^{β} = (∑_{γ} a_{1γ}x^{γ}) · x^{α(1)} + ⋯ + (∑_{γ} a_{sγ}x^{γ}) · x^{α(s)} = ∑_{γ} a_{1γ}x^{γ+α(1)} + ⋯ + ∑_{γ} a_{sγ}x^{γ+α(s)}

よって、 x^{β} = x^{γ+α(i)} = x^{γ} · x^{α(i)} を満たす γ, i が存在するので、 x^{β} を割り切るような x^{α} が存在する。 (証明終わり)

Lemma 3.3.2 I, J ⊂ k[x_{1}, ⋯, x_{n}] を単項式イデアルとする。このとき

I = J ⟺ I と J の単項式の元は、すべて同じである。

(Proof) (⟹) 明らかである。

(⟸) I =< x^{α} : α ∈ A >とおく。 f = 0 のとき、明らかに、 f ∈ I ⟹ f ∈ J である。

f ≠ 0 のとき、 f = ∑_{i=1}^{s} a_{i}x^{β(i)} ∈ I (a_{i} ∈ k a_{i} ≠ 0) とおく。

f は、単項式イデアルの元なので

f = ∑_{j=1}^{t} h_{j}x^{α(j)} (h_{i} ∈ k[x_{1}, ⋯, x_{n}], α(j) ∈ A)

と表せる。 Lemma 3.3.1 の証明と同様、右辺を展開すると、任意の i に対し

x^{β(i)} = x^{γ} · x^{α(j)} (γ ∈ Z_{≥0}^{n})

を満たす γ, j が存在する。 x^{α(j)} ∈ I より、任意の i に対し、 x^{β(i)} ∈ I になる。 I と J の単項式の元は、すべて同じなので、 x^{β(i)} ∈ J より、 f ∈ J になる。よって、 I ⊂ J である。同様に I ⊃ J も示せるので、以上により、 I = J である。 (証明終わり)

Theorem 3.3.1 (Dickson の補題) 単項式イデアル I =< x^{α} : α ∈ A >⊂ k[x_{1}, ⋯, x_{n}] は、有限個の α(1), ⋯, α(s) ∈ A によって

I =< x^{α(1)}, ⋯, x^{α(s)} >

と表せる。 (つまり、有限生成で表せる。 )

(Proof) n = 1 のとき

I =< x_{1}^{α} : α ∈ A >⊂ k[x_{1}] (A ⊂ Z_{≥0})

A の不等号における最小要素を β とする。 ∀α ∈ A に対し、 β ≤ α より、 x_{1}^{β} は x_{1}^{α} を割り切る。よって、 I =< x_{1}^{β} > である。

定理が n−1 まで成り立つと仮定する。 x_{1}, ⋯, x_{n−1}, y の n 変数で考えると、 k[x_{1}, ⋯, x_{n−1}, y] 上の任意の単項式は

x^{α}y^{m} ( α ∈ Z_{≥0}^{n−1} m ∈ Z_{≥0} )

と表せる。 I ⊂ k[x_{1}, ⋯, x_{n−1}, y] を単項式イデアルとする。 J ⊂ k[x_{1}, ⋯, x_{n−1}] を、 x^{α}y^{m} ∈ I を満たすような m が存在する任意の x^{α} で生成される単項式イデアルとすると、仮定より、有限個の J の生成元 x^{α(1)}, ⋯, x^{α(s)} によって

J =< x^{α(1)}, ⋯, x^{α(s)} >

と表せる。 J の定義より、 1 ≤ i ≤ s の任意の i に対して、 x^{α(i)}y^{m_{i}} ∈ I を満たす m_{i} が存在する。ここで

m = max{ m_{i} | 1 ≤ i ≤ s }

とする。 0 < l ≤ m − 1 の任意の l に対して、 J_{l} ⊂ k[x_{1}, ⋯, x_{n−1}] を、 x^{β}y^{l} ∈ I を満たす任意の x^{β} で生成される単項式イデアルとすると、仮定より、有限個の J_{l} の生成元 x^{α_{l}(1)}, ⋯, x^{α_{l}(s_{l})} によって

J_{l} =< x^{α_{l}(1)}, ⋯, x^{α_{l}(s_{l})} >

と表せる。ここで

x^{α(1)}y^{m}, ⋯, x^{α(s)}y^{m}
x^{α_{0}(1)}, ⋯, x^{α_{0}(s_{0})}
x^{α_{1}(1)}y, ⋯, x^{α_{1}(s_{1})}y
⋮
x^{α_{m−1}(1)}y^{m−1}, ⋯, x^{α_{m−1}(s_{m−1})}y^{m−1}

で生成される単項式イデアルを I′ とする。 ∀x^{α}y^{p} ∈ I とすると、 p ≥ m のとき、 J の定義より x^{α}y^{p} を割り切るような x^{α(i)}y^{m} が存在する。 p ≤ m − 1 のとき、 J_{p} の定義より x^{α}y^{p} を割り切るような x^{α_{p}(j)}y^{p} が存在する。よって、 Lemma 3.3.1 より、 I の単項式の元はすべて I′ に含まれる。逆に、 I′ の生成元は I の元になっているので、 I′ ⊂ I より、 I′ の単項式の元はすべて I に含まれる。 I と I′ の単項式の元はすべて同じであるので、 Lemma 3.3.2 より、 I = I′ になる。

以上により、単項式イデアル I =< x^{α} : α ∈ A >⊂ k[x_{1}, ⋯, x_{n}] は、有限個の x^{β(1)}, ⋯, x^{β(t)} ∈ I によって

I =< x^{β(1)}, ⋯, x^{β(t)} >

と表せることがわかった。また、 Lemma 3.3.1 より、 1 ≤ i ≤ t の任意の i に対して、 x^{α(i)} が x^{β(i)} を割り切るような α(i) ∈ A が存在する。このとき、

< x^{α} : α ∈ A >=< x^{α(1)}, ⋯, x^{α(t)} >

であることを示す。

(⊃) 明らかである。

(⊂) < x^{α} : α ∈ A >=< x^{β(1)}, ⋯, x^{β(t)} > ⊂ < x^{α(1)}, ⋯, x^{α(t)} > 以上により

< x^{α} : α ∈ A >=< x^{α(1)}, ⋯, x^{α(t)} > (α(i) ∈ A)

である。 (証明終わり)

3.4 Hilbert の基底定理と Gröbner 基底

Definition 3.4.1 I(≠ {0}) ⊂ k[x_{1}, ⋯, x_{n}] をイデアルとする。このとき 1. LT (I) = { LT (f) | f ∈ I − {0} } とする。

2. LT (I) のすべての元で生成されるイデアルを < LT (I) > と表す。 Proposition 3.4.1 I(≠ {0}) ⊂ k[x_{1}, ⋯, x_{n}] をイデアルとする。このとき

1. < LT (I) > は、単項式イデアルである。

2. < LT (I) >=< LT (g_{1}), ⋯, LT (g_{s}) > を満たす g_{1}, ⋯, g_{s} ∈ I が存在する。 (Proof)

1. < LT (I) >=< LM(g) : g ∈ I − {0} > であることを示す。

(⊂) LT (g) ∈< LT (I) > とする。

LT (g) = LC(g) · LM(g) ∈< LM(g) : g ∈ I − {0} >

(⊃) LM(f) ∈< LM(g) : g ∈ I − {0} > とする。

LM(f) = \frac{1}{LC(f)} · LT (f) ∈< LT (I) >

以上により、 < LT (I) >=< LM(g) : g ∈ I − {0} > が成り立つので、 < LT (I) > は、単項式イデアルである。

2. < LT (I) > は、単項式イデアルより、 Dickson の補題から、

< LT (I) >=< LM(g_{1}), ⋯, LM(g_{s}) >

を満たす g_{1}, ⋯, g_{s} ∈ I が存在する。 1 の証明と同様の方法で

< LM(g_{1}), ⋯, LM(g_{s}) >=< LT (g_{1}), ⋯, LT (g_{s}) >

が示せる。よって、 < LT (I) >=< LT (g_{1}), ⋯, LT (g_{s}) > である。 (証明終わり)

Theorem 3.4.1 (Hilbert の基底定理) 任意のイデアル I ⊂ k[x_{1}, ⋯, x_{n}] は、有限個の g_{1}, ⋯, g_{s} ∈ I によって、 I =< g_{1}, ⋯, g_{s} > と表せる。 (つまり、有限生成で表せる。 )

(Proof) I = {0} のとき、 I =< 0 > である。 I ≠ {0} のとき、 Proposition 3.4.1 の 2 より

< LT (I) >=< LT (g_{1}), ⋯, LT (g_{s}) >

と表せる。このとき、 I =< g_{1}, ⋯, g_{s} > であることを示す。

(⊃) 明らかである。

(⊂) f ∈ I とする。多変数多項式の除法定理より

f = a_{1}g_{1} + ⋯ + a_{s}g_{s} + r (a_{i}, r ∈ k[x_{1}, ⋯, x_{n}])
(r = 0 または ∀LT (g_{i}) は r のすべての項を割り切らない )

と表せる。このとき

r = f − a_{1}g_{1} − ⋯ − a_{s}g_{s} ∈ I

となる。 r ≠ 0 と仮定すると

LT (r) ∈< LT (I) >=< LT (g_{1}), ⋯, LT (g_{s}) >

より、 LT (r) を割り切る LT (g_{i}) が存在する。このことは矛盾より、 r = 0 である。よって、 f = a_{1}g_{1} + ⋯ + a_{s}g_{s} ∈< g_{1}, ⋯, g_{s} >である。

以上により、 I =< g_{1}, ⋯, g_{s} > である。 (証明終わり)

Definition 3.4.2 I(≠ {0}) ⊂ k[x_{1}, ⋯, x_{n}] をイデアルとする。 G = {g_{1}, ⋯, g_{s}} ⊂ I が

< LT (g_{1}), ⋯, LT (g_{s}) >=< LT (I) >

を満たすとき、 G を Gröbner 基底 (または標準基底) という。

Hilbert の基底定理の証明過程により、任意のイデアル I(≠ {0}) ⊂ k[x_{1}, ⋯, x_{n}] に対し、 Gröbner 基底 G = {g_{1}, ⋯, g_{s}} が存在し、 I の生成元になっていることがわかる。つまり、 I =< g_{1}, ⋯, g_{s} > と表せる。

Proposition 3.4.2 f ∈ k[x_{1}, ⋯, x_{n}]、 I(≠ {0}) ⊂ k[x_{1}, ⋯, x_{n}] をイデアル、 G = {g_{1}, ⋯, g_{s}} ⊂ I を Gröbner 基底とする。このとき、多変数多項式の除法定理により

f = a_{1}g_{1} + ⋯ + a_{s}g_{s} + r (a_{i}, r ∈ k[x_{1}, ⋯, x_{n}])
(r = 0 または ∀LT (g_{i}) は r のすべての項を割り切らない )

と表したとき、 r は一意である。

(Proof)

f = g + r = g′ + r′
( g = a_{1}g_{1} + ⋯ + a_{s}g_{s} g′ = b_{1}g_{1} + ⋯ + b_{s}g_{s} a_{i}, b_{i} ∈ k[x_{1}, ⋯, x_{n}] )

とする。 g, g′ ∈ I より

r − r′ = g′ − g ∈ I

になる。 r ≠ r′ とすると

LT (r − r′) ∈< LT (I) >=< LT (g_{1}), ⋯, LT (g_{s}) >

より、 LT (r − r′) を割り切る LT (g_{i}) が存在する。このことは、 ∀LT (g_{i}) は、 r, r′ のすべての項を割り切らないことに矛盾する。よって、 r = r′ である。 (証明終わり)

3.5 多変数多項式環上のイデアルの構成要素に関する問題の解法

f, f_{1}, ⋯, f_{s} ∈ k[x_{1}, ⋯, x_{n}] に対し、 fが < f_{1}, ⋯, f_{s} > の元であるか否かを調べたい。 < f_{1}, ⋯, f_{s} >= {0} とすると、 < f_{1}, ⋯, f_{s} > の元は 0 のみになるので、 < f_{1}, ⋯, f_{s} >≠ {0} の場合について考える。 < f_{1}, ⋯, f_{s} > の Gröbner 基底を G = {g_{1}, ⋯, g_{t}} とすると、 < f_{1}, ⋯, f_{s} >=< g_{1}, ⋯, g_{t} > となるので、この問題は、 f が < g_{1}, ⋯, g_{t} > の元であるか否かに帰着される。多変数多項式の除法定理により、 f = a_{1}g_{1} + ⋯ + a_{t}g_{t} + r (r = 0 または ∀LT (g_{i}) は r のすべての項を割り切らない ) と表せる。もし、 r = 0 ならば、 f = a_{1}g_{1} + ⋯ + a_{t}g_{t} ∈< g_{1}, ⋯, g_{t} >である。 r ≠ 0 ならば、 {g_{1}, ⋯, g_{t}} が Gröbner 基底より、 r は一意であるので、 f = b_{1}g_{1} + ⋯ + b_{t}g_{t} を満たす b_{1}, ⋯, b_{t} は存在しない。よって、 f ∉< g_{1}, ⋯, g_{t} > である。

論理的には解決出来たが、実際問題として、 g_{1}, ⋯, g_{t}, a_{1}, ⋯, a_{t}, r の求め方については論じていなかったので、具体例について計算が出来ない。そこで、多変数多項式の除法定理における a_{1}, ⋯, a_{t}, r と、 Gröbner 基底 G = {g_{1}, ⋯, g_{t}} を求める計算方法を紹介する。

Proposition 3.5.1 f, f_{1}, ⋯, f_{s} ∈ k[x_{1}, ⋯, x_{n}] ( ∀f_{i} ≠ 0 ) に対し、多変数多項式の除法定理による

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r (r = 0 または ∀LT (f_{i}) は r のすべての項を割り切らない )

なる a_{1}, ⋯, a_{s}, r ∈ k[x_{1}, ⋯, x_{n}] を求める計算方法がある。

(Proof) コンピューターの言語をまねたスードコードを用いて表示する。 Input: f_{1}, ⋯, f_{s}, f Output: a_{1}, ⋯, a_{s}, r

a_{1} := 0; ⋯; a_{s} := 0; r := 0 p := f WHILE p ≠ 0 DO

i := 1

divisionoccurred := false

WHILE i ≤ s AND divisionoccurred := false Do IF LT (f_{i}) divides LT (p) THEN

a_{i} := a_{i} + LT (p)/LT (f_{i}) p := p − (LT (p)/LT (f_{i}))f_{i} divisionoccurred := true

ELSE

i := i + 1

IF divisionoccurred := false THEN r := r + LT (p)

p := p − LT (p)

これが、計算方法であることを示す。

この計算方法には、各計算段階において、 LT (p) を割り切るような LT (f_{i}) が存在する場合の段階 (除法段階とする) と、 LT (p) を割り切るような LT (f_{i}) が存在しない場合の段階 (余り段階とする) の 2 通りがある。まず、 a_{1}, ⋯, a_{s}, r、 p の初期値を、 a_{1(0)}, ⋯, a_{s(0)}, r_{(0)}, p_{(0)} とおき、 m 回目の計算段階における a_{1}, ⋯, a_{s}, r、 p の値を、 a_{1(m)}, ⋯, a_{s(m)}, r_{(m)}, p_{(m)} とおく。

まず、各計算段階において

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + p + r

を満たすことを示す。 m = 0 のとき

a_{1(0)}f_{1} + ⋯ + a_{s(0)}f_{s} + p_{(0)} + r_{(0)} = 0 · f_{1} + ⋯ + 0 · f_{s} + f + 0 = f

m 回目の計算段階に進む前に

f = a_{1(m−1)}f_{1} + ⋯ + a_{s(m−1)}f_{s} + p_{(m−1)} + r_{(m−1)}

が、成り立っていると仮定する。 m 回目の計算段階が除法段階のとき、値が変わる変数は、 a_{i}, p で

a_{i(m)}f_{i} + p_{(m)} = \{a_{i(m−1)} + \frac{LT (p_{(m−1)})}{LT (f_{i})}\} f_{i} + \{p_{(m−1)} − \frac{LT (p_{(m−1)})}{LT (f_{i})}f_{i}\} = a_{i(m−1)}f_{i} + p_{(m−1)}

より

f = a_{1(m)}f_{1} + ⋯ + a_{s(m)}f_{s} + p_{(m)} + r_{(m)}

m 回目の計算段階が余り段階のとき、値が変わる変数は、 p、 r で

p_{(m)} + r_{(m)} = {p_{(m−1)} − LT (p_{(m−1)})} + {r_{(m−1)} + LT (p_{(m−1)})} = p_{(m−1)} + r_{(m−1)}

より

f = a_{1(m)}f_{1} + ⋯ + a_{s(m)}f_{s} + p_{(m)} + r_{(m)}

以上により、各計算段階において

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + p + r

を満たす。

次に、 p = 0 のときに計算が終わるので、出力結果が

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r

となることは明らかである。

さらに、出力結果が、 r = 0 または ∀LT (f_{i}) は r のすべての項を割り切らないという条件を満たすのは、 r の初期値 (r_{(0)} = 0) と、余り段階に進む条件 (LT (p) を割り切るような LT (f_{i}) は存在しない) と、余り段階における計算 (r_{(m)} = r_{(m−1)} + LT (p_{(m−1)})) より、明らかである。

最後に、有限回の計算で p = 0 になる。つまり、計算が有限回で終わることを示す。 m 回目の計算段階が除法段階のとき

p_{(m)} = p_{(m−1)} − \frac{LT (p_{(m−1)})}{LT (f_{i})}f_{i}

LT (\frac{LT (p_{(m−1)})}{LT (f_{i})}f_{i}) = \frac{LT (p_{(m−1)})}{LT (f_{i})} · LT (f_{i}) = LT (p_{(m−1)})

より、 multideg(p_{(m)}) < multideg(p_{(m−1)}) または p_{(m)} = 0 になる。 m 回目の計算段階が余り段階のとき

p_{(m)} = p_{(m−1)} − LT (p_{(m−1)})

より、明らかに multideg(p_{(m)}) < multideg(p_{(m−1)}) または p_{(m)} = 0 になる。また、単項式順序は整列順序より、以上により、有限回の計算で p = 0 になる。 (証明終わり)

一般に、 f_{1}, ⋯, f_{s} の順番を入れかえて計算すると、計算結果の a_{1}, ⋯, a_{s}、 r の値は、同じであるとは限らない。 Definition 3.5.1 f, f_{1}, ⋯, f_{s} ∈ k[x_{1}, ⋯, x_{n}] ( ∀f_{i} ≠ 0 ) とし、 F = {f_{1}, ⋯, f_{s}} とする。 Proposition 3.5.1 の計算方法を用いて

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r (r = 0 または ∀LT (f_{i}) は r のすべての項を割り切らない )

と表したときの余り r を、\overline{f}^{F} と表す。

Definition 3.5.2 f, g ∈ k[x_{1}, ⋯, x_{n}] を零でない多項式とする。

1. multideg(f) = α, multideg(g) = β ( α = (α_{1}, ⋯, α_{n}), β = (β_{1}, ⋯, β_{n}) ) のとき

γ = (γ_{1}, ⋯, γ_{n}) ( γ_{i} = max{α_{i}, β_{i}} (1 ≤ ∀i ≤ n) )

に対し、 x^{γ} を LM(f) と LM(g) の最小公倍単項式といい

x^{γ} = LCM(LM(f), LM(g))

と表す。

2. x^{γ} = LCM(LM(f), LM(g)) のとき

S(f, g) = \frac{x^{γ}}{LT (f)} · f − \frac{x^{γ}}{LT (g)} · g

を、 f と g の S 多項式という。

Proposition 3.5.2 イデアル I =< f_{1}, ⋯, f_{s} > (≠ {0}) ⊂ k[x_{1}, ⋯, x_{n}] の Gröbner 基底 G を求める計算方法がある。

(Proof) スードコードを用いて表示する。

Input: F = (f_{1}, ⋯, f_{s}) Output: a Gröbner basis G = (g_{1}, ⋯, g_{t}) for I, with F ⊂ G

G := F REPEAT

G′ := G
FOR each pair {p, q}, p ≠ q in G′ DO
S := \overline{S(p, q)}^{G′}
IF S ≠ 0 THEN G := G ⋃ {S}

UNTIL G = G′

これが、計算方法であることの証明は省略する。 (証明終わり)

次に、数学コンピューターソフト Mathematica で、この 2 つの計算方法を利用して組んだプログラムを用いて、具体例を計算してみる。但し、プログラム上では、多変数多項式を、例えば Q[x, y, z] 上の 4xy^{2}z + 4z^{2} − 5x^{3} + 7x^{2}z^{2} という多項式の場合、

{{{0, 0, 4}}, {{0}, {0}, {0, 4}}, {{0, 0, 7}}, {{−5}}}

のように、リストの中の 1 番目のかっこは、 x の次数について、 2 番目のかっこは、 y の次数について・・・、という様にして、 1 変数多項式の場合のように、係数のリストで表して処理をする。

以下に、プログラムの紹介をする。 (但し、単項式順序は、辞書式順序とする。 )

In[19]:=LT[f_]:=LT[f]=Module[{n,ff,deglist,coe},
n=Depth[f]-1;ff[i_]:=ff[i]=ff[i-1][[-1]];
ff[1]:=f;deglist=Table[Length[ff[i]]-1,{i,1,n}];
coe=Flatten[f][[-1]];{deglist,coe}]
In[20]:=Polymono[f_,m_]:=Polymono[f,m]=
Module[{deglist,coe,f1,f2,k,a,zero,f3,co,ze},
deglist=m[[1]];coe=m[[2]];k=deglist[[1]]+1;
If[Length[f]>=k,If[Length[deglist]==1,
If[coe+f[[k]]==0,f1=ReplacePart[f,0,k];
While[Length[f1]>=2&&f1[[-1]]==0,f1=Delete[f1,-1]];f1,
ReplacePart[f,coe+f[[k]],k]],
f2=ReplacePart[f,Polymono[f[[k]],
{Delete[deglist,1],coe}],k];
While[Length[f2]>=2&&Flatten[f2[[-1]]]=={0},
f2=Delete[f2,-1]];f2],a=k-Length[f];zero=0;
Do[zero={zero},{Depth[f]-2}];f3=f;
Do[f3=Append[f3,zero],{a-1}];co={coe};ze=0;
Do[Do[co=Prepend[co,ze],{deglist[[-i]]}];co={co};
ze={ze},{i,1,Length[deglist]-1}];
If[Depth[co]==2,co=coe,co=FlattenAt[co,{1}]];
Append[f3,co]]]
In[21]:=PolyDiv[f_,g_]:=PolyDiv[f,g]=Module[{s,z,a,r,p,i,c,h1,h2,gg},
s=Length[g];z=0;Do[z={z},{Depth[f]-1}];a={};
Do[a=Append[a,z],{s}];r=z;p=f;
While[p=!=z,i=1;c=True;
While[i<=s&&c,h1=LT[p][[1]]-LT[g[[i]]][[1]];

                        If[Select[h1,#1<0&]=={},
                        h2=LT[p][[2]]/(LT[g[[i]]][[2]]);
                        a=ReplacePart[a,Polymono[a[[i]],{h1,h2}],i];gg=g[[i]];
                        While[gg=!=z,
                        p=Polymono[p,{h1+LT[gg][[1]],-h2*LT[gg][[2]]}];
                        gg=Polymono[gg,{LT[gg][[1]],-LT[gg][[2]]}]];
                        c=False,i=i+1]];If[c,r=Polymono[r,LT[p]];
                        p=Polymono[p,{LT[p][[1]],-LT[p][[2]]}]]];{a,r}]

PolyDiv[f, {f_{1}, ⋯, f_{s}}] ( 但し、 ∀f_{i} ≠ 0) と入力すると、

f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r (r = 0 または ∀LT (f_{i}) は r のすべての項を割り切らない )

を、満たす {{a_{1}, ⋯, a_{s}}, r} を出力する。

In[22]:=S[f_,g_]:=S[f,g]=Module[{mf,mg,s,a,b,z,aa,ff,gg},
                  mf=LT[f][[1]];mg=LT[g][[1]];s=Length[mf];c={};
                  Do[c=Append[c,Max[{mf[[i]],mg[[i]]}]],{i,1,s}];
                  a={c-mf,1/(LT[f][[2]])};b={c-mg,1/(LT[g][[2]])};
                  z=0;Do[z={z},{s}];aa=z;ff=f;While[ff=!=z,
                  aa=Polymono[aa,{a[[1]]+LT[ff][[1]],a[[2]]*LT[ff][[2]]}];
                  ff=Polymono[ff,{LT[ff][[1]],-LT[ff][[2]]}]];gg=g;
                  While[gg=!=z,aa=Polymono[aa,{b[[1]]+LT[gg][[1]],
                  -b[[2]]*LT[gg][[2]]}];
                  gg=Polymono[gg,{LT[gg][[1]],-LT[gg][[2]]}]];aa]
In[23]:=Groeb[F_]:=Groeb[F]=Module[{G,GG,z,s,r},
                   G=F;z=0;Do[z={z},{Depth[F[[1]]]-1}];
                   While[G=!=GG,GG=G;s=Length[G];
                   Do[Do[r=PolyDiv[S[G[[i]],G[[j]]],G][[-1]];
                   If[r=!=z,G=Append[G,r]],{j,i+1,s}],{i,1,s-1}]];G]

Groeb[{f_{1}, ⋯, f_{s}}] と入力すると、 < f_{1}, ⋯, f_{s} > の Gröbner 基底 {g_{1}, ⋯, g_{t}} を出力する。

以下に、具体例をあげる。

Example 6

\{ \begin{matrix}f = −4x^{2}y^{2}z^{2} + y^{6} + 3z^{5} \\ f_{1} = xz − y^{2} \\ f_{2} = x^{3} − z^{2} \end{matrix} f, f_{1}, f_{2} ∈ Q[x, y, z]

とする。

In[24]:=f={{{0,0,0,0,0,3},{0},{0},{0},{0},{0},{1}},{{0}},{{0},{0},{0,0,-4}}};
       f1={{{0},{0},{-1}},{{0,1}}};f2={{{0,0,-1}},{{0}},{{0}},{{1}}}

f が < f_{1}, f_{2} > の元であるか否かを調べる。

In[25]:=G=Groeb[{f1,f2}]
Out[25]={{{{0},{0},{-1}},{{0,1}}},{{{0,0,-1}},{{0}},{{0}},{{1}}},
        {{{0,0,0,1}},{{0}},{{0},{0},{-1}}},
        {{{0,0,0,0,1}},{{0},{0},{0},{0},{-1}}},
        {{{0,0,0,0,0,1},{0},{0},{0},{0},{0},{-1}}}}

< f_{1}, f_{2} >=< g : g ∈ G > より、 f が < g : g ∈ G > の元であるかどうかを調べる。

In[26]:=PolyDiv[f,G]
Out[26]={{{{{0},{0},{0},{0},{-4}},{{0},{0},{0,-4}}},{{{0}}},{{{0}}},
        {{{0}}},{{{3}}}},{{{0}}}}

余りが 0 なので、 f ∈< g : g ∈ G > より、 f ∈< f_{1}, f_{2} >である。

Example 7

\{ \begin{matrix}f = xy^{3} − z^{2} + y^{5} − z^{3} \\ f_{1} = −x^{3} + y \\ f_{2} = x^{2}y − z \end{matrix} f, f_{1}, f_{2} ∈ Q[x, y, z]

とする。

In[27]:=f={{{0,0,-1,-1},{0},{0},{0},{0},{1}},{{0},{0},{0},{1}}};
       f1={{{0},{1}},{{0}},{{0}},{{-1}}};f2={{{0,-1}},{{0}},{{0},{1}}}

f が < f_{1}, f_{2} > の元であるか否かを調べる。

In[28]:=G=Groeb[{f1,f2}]
Out[28]={{{{0},{1}},{{0}},{{0}},{{-1}}},{{{0,-1}},{{0}},{{0},{1}}},
        {{{0},{0},{-1}},{{0,1}}},{{{0,0,-1}},{{0},{0},{0},{1}}},
        {{{0,0,0,1},{0},{0},{0},{0},{-1}}}}

< f_{1}, f_{2} >=< g : g ∈ G > より、 f が < g : g ∈ G > の元であるかどうかを調べる。

In[29]:=PolyDiv[f,G]
Out[29]={{{{{0}}},{{{0}}},{{{0}}},{{{1}}},{{{-1}}}},{{{0}}}}

余りが 0 なので、 f ∈< g : g ∈ G > より、 f ∈< f_{1}, f_{2} >である。

Example 8

\{ \begin{matrix}f = x^{3}z − 2y^{2} \\ f_{1} = xz − y \\ f_{2} = xy + 2z^{2} \\ f_{3} = y − z \end{matrix} f, f_{1}, f_{2}, f_{3} ∈ Q[x, y, z]

とする。

In[30]:=f={{{0},{0},{-2}},{{0}},{{0}},{{0,1}}};f1={{{0},{-1}},{{0,1}}};
        f2={{{0,0,2}},{{0},{1}}};f3={{{0,-1},{1}}}

f が < f_{1}, f_{2}, f_{3} > の元であるか否かを調べる。

In[31]:=G=Groeb[{f1,f2,f3}]
Out[31]={{{{0},{-1}},{{0,1}}},{{{0,0,2}},{{0},{1}}},{{{0,-1},{1}}},
        {{{0,0,-1,-2}}},{{{0,1,2}}}}

< f_{1}, f_{2}, f_{3} >=< g : g ∈ G > より、 f が < g : g ∈ G > の元であるかどうかを調べる。

In[32]:=PolyDiv[f,G]
Out[32]={{{{{0,-2}},{{0}},{{1}}},{{{0}},{{1}}},{{{0,-4},{-2}}},{{{0}}},
        {{{-2}}}},{{{0,2}}}}

余りが 2z ≠ 0 なので、 f ∉< g : g ∈ G > より、 f ∉< f_{1}, f_{2}, f_{3} >である。 Example 9

\{ \begin{matrix}f = 3 + x^{2}y + y^{2} \\ f_{1} = x^{2} + y \\ f_{2} = x^{4} + 2x^{2}y + y^{2} + 3 \end{matrix} f, f_{1}, f_{2} ∈ Q[x, y, z]

とする。

In[33]:=f={{{3},{0},{1}},{{0}},{{0},{1}}};f1={{{0},{1}},{{0}},{{1}}};
        f2={{{3},{0},{1}},{{0}},{{0},{2}},{{0}},{{1}}}

f が < f_{1}, f_{2} > の元であるか否かを調べる。

In[34]:=G=Groeb[{f1,f2}]
Out[34]={{{{0},{1}},{{0}},{{1}}},{{{3},{0},{1}},{{0}},{{0},{2}},{{0}},{{1}}},
        {{{-3}}}}

< f_{1}, f_{2} >=< g : g ∈ G > より、 f が < g : g ∈ G > の元であるかどうかを調べる。

In[35]:=PolyDiv[f,G]
Out[35]={{{{{0},{1}}},{{{0}}},{{{-1}}}},{{{0}}}}

余りが 0 なので、 f ∈< g : g ∈ G > より、 f ∈< f_{1}, f_{2} >である。 Example 10

\{ \begin{matrix}f = x^{3}y^{2} + y + 1 \\ f_{1} = x^{2}y − 1 \\ f_{2} = xy^{2} − x \end{matrix} f, f_{1}, f_{2} ∈ Q[x, y, z]

とする。

In[36]:=f={{{1},{1}},{{0}},{{0}},{{0},{0},{1}}};
        f1={{{-1}},{{0}},{{0},{1}}};f2={{{0}},{{-1},{0},{1}}}

f が < f_{1}, f_{2} > の元であるか否かを調べる。

In[37]:=G=Groeb[{f1,f2}]
Out[37]={{{{-1}},{{0}},{{0},{1}}},{{{0}},{{-1},{0},{1}}},
        {{{0},{-1}},{{0}},{{1}}},{{{-1},{0},{1}}}}

< f_{1}, f_{2} >=< g : g ∈ G > より、 f が < g : g ∈ G > の元であるかどうかを調べる。

In[38]:=PolyDiv[f,G]
Out[38]={{{{{0}},{{0},{1}}},{{{0}}},{{{0}}},{{{0}}}},{{{1},{1}},{{0},{1}}}}

余りが xy + y + 1 ≠ 0 なので、 f ∉< g : g ∈ G > より、 f ∉< f_{1}, f_{2} >である。 Example 11

\{ \begin{matrix}f = xz^{2} − yz \\ f_{1} = x − z^{4} \\ f_{2} = y − z^{5} \end{matrix} f, f_{1}, f_{2} ∈ Q[x, y, z]

とする。

In[39]:=f={{{0},{0,-1}},{{0,0,1}}};f1={{{0,0,0,0,-1}},{{1}}};
        f2={{{0,0,0,0,0,-1},{1}}}

f が < f_{1}, f_{2} > の元であるか否かを調べる。

In[40]:=G=Groeb[{f1,f2}]
Out[40]={{{{0,0,0,0,-1}},{{1}}},{{{0,0,0,0,0,-1},{1}}}}

< f_{1}, f_{2} >=< g : g ∈ G > より、 f が < g : g ∈ G > の元であるかどうかを調べる。

In[41]:=PolyDiv[f,G]
Out[41]={{{{{0,0,1}}},{{{0,-1}}}},{{{0}}}}

余りが 0 なので、 f ∈< g : g ∈ G > より、 f ∈< f_{1}, f_{2} >である。 Example 12

\{ \begin{matrix}f = x^{6} − 1 \\ f_{1} = y^{2}zw + 1 \\ f_{2} = x^{3}yzw − yw \\ f_{3} = zw − x^{3}w \\ f_{4} = y^{4} − 1 \end{matrix} f, f_{1}, f_{2}, f_{3}, f_{4} ∈ Q[x, y, z, w]

In[42]:=f={{{{-1}}},{{{0}}},{{{0}}},{{{0}}},{{{0}}},{{{0}}},{{{1}}}};
f1={{{{1}},{{0}},{{0},{0,1}}}};
f2={{{{0}},{{0,-1}}},{{{0}}},{{{0}}},{{{0}},{{0},{0,1}}}};
f3={{{{0},{0,1}}},{{{0}}},{{{0}}},{{{0,-1}}}}
f4={{{{-1}},{{0}},{{0}},{{0}},{{1}}}}

f が < f_{1}, f_{2}, f_{3}, f_{4} > の元であるか否かを調べる。

In[43]:=G=Groeb[{f1,f2,f3,f4}]
Out[43]={{{{{1}},{{0}},{{0},{0,1}}}},
{{{{0}},{{0,-1}}},{{{0}}},{{{0}}},{{{0}},{{0},{0,1}}}},
{{{{0},{0,1}}},{{{0}}},{{{0}}},{{{0,-1}}}},
{{{{-1}},{{0}},{{0}},{{0}},{{1}}}},
{{{{0}},{{0}},{{0,1}}},{{{0}}},{{{0}}},{{{1}}}},
{{{{0},{-1}},{{0}},{{0,-1}}}},{{{{0},{0,1}},{{0}},{{1}}}},
{{{{0}},{{0,-1},{0},{0,1}}}},{{{{0,-1},{0},{0,1}}}},
{{{{1},{0},{-1}}}},{{{{1,0,-1}}}}}

< f_{1}, f_{2}, f_{3}, f_{4} >=< g : g ∈ G > より、 f が < g : g ∈ G > の元であるかどうかを調べる。

In[44]:=PolyDiv[f,G]
Out[44]={{{{{{-1}}}},{{{{0}}}},{{{{0}},{{0}},{{1}}}},{{{{0}}}},
{{{{0}}},{{{0}}},{{{0}}},{{{1}}}},{{{{0}}}},{{{{0}}}},{{{{0}}}},
{{{{0}}}},{{{{0}}}},{{{{0}}}}},{{{{0}}}}}

余りが 0 なので、 f ∈< g : g ∈ G > より、 f ∈< f_{1}, f_{2}, f_{3}, f_{4} >である。

Bibliography

[1] David Cox, John Little, Donal O’Shea : Ideals, Varieties, and Algorithm, Springer-Verag New York, 1996

[2] 上野健爾 : 代数幾何入門, 岩波書店, 1995

[3] 酒井文雄 : 環と体の理論, 共立出版, 1997

[4] 藤崎源二郎 : 体とガロア理論, 岩波書店, 1991

[5] E. アルティン著寺田文行訳 : ガロア理論入門, 東京書籍, 1974

[6] J. ロットマン著関口次郎訳 : ガロア理論, シュプリンガー・フェアラーク東京, 1997 [7] 堀田良之 : 代数入門−群と加群−, 裳華房, 1987

[8] 上野健爾, 志賀浩二, 砂田利一編集 :

数学の楽しみ No.11 「多項式環の視点:グレブナー基底」 , 日本評論社, 1999