グレブナー基底について

平成

25年

度

学位論文

グ レ ブ ナ ー 基 底 に つ い て

兵 庫 教 育 大 学 大 学 院 教育内容 ・方法開発専攻

M12152H

学 校 教 育 研 究 科 認識形成系教育 コース 仲

川

拓

哉

目 次

序 準備 整列集 合 環 ４     ５

0章

■章 1.1 1.2 1.3

2章

2.1 2.2 3章 3.1 3.2 3.3 多項式環 項順 序 とモ ノイデ アル 項‖贋序 モ ノイデアル グレブナー基底 単項簡約 グ レブナー基底 の定義 と存在 簡約 グ レブナー基底

4章

ブッフバー ガー アル ゴ リズム

4.l S多

項式

.…

_{… … … ・ … … ・ ― ・ … ・… … ・・ … …}

'…

・… … … ・ 4.2 ブ ッフバー ガーアル ゴ リズム

.…

_{… … … ・… … ・… ・… ・… ・ ・… … ・} 参考文献 ０     ０ １     １ 13 ８     ８ １     １ ４     ８ ２     ２ ３２     ３２     ４ ． 48

序

土早

0

本論文では,グ レブナー基底 とブ ッフバーガーアル ゴ リズムについて述べ る。 グ レブナー基底 の概念 は,ブ ッフバーガー (B.Buchberger)に よ り,多項式環のイデ ア ル による乗1余類環 を計算す る問題 を研究す る過程 で発 見 され ,そ の計算方法で あるブ ッフ バーガーアル ゴ リズム と共 に,彼 のイ ンスブル ック大学(オース トリア)で の学位論文 (1965 年

)の

中核 をな してぃ る. グ レブナー基底 とは_,多項式環のイデアル の基底 で,“よい条件

"を

みたす ものであ り, 多項式がイデアル に属す るか どうかの判定問題や連立代数方程式 の解法 な ど多方面に応用 されている

.例

えば_{,複素数係数連立代数方程式}

ヽ A("1,・

・

・

メ

n)=0

ル

(″1,…,χ

π

)=0

の解 を求める問題 は,■,… "ん で生成 された

Ch,…

"″』 のイデアル 」

=(A,…

っル)の零 ′点 を求 める問題 と一致 し,イ デアル 」の “よい

"生

成系で あるグ レブナー基底 ク1,¨ "ク

mを

求 め,そ の共通零点 を求 める問題 に帰着す る. 筆者は学部 の卒業研究の過程で,グ レブナー基底 を利用 して対称式 の計算 を行つた。し か し,グ レブナー基底 の諸性質について十分 に理解 していたわけではな く,計 算機 を用いて 計算す るための道具 としていたにす ぎないことに気付いた。この ような理 由か ら,本 大学院 において,グ レブナー基底 の概念 とブ ッフバー ガーアル ゴリズムについてのよ り深い理解 と知識 を得 るための研 究を行 うことに した. なお_,グレブナー基底 とい う名称 はブ ッフバーガーの指導教授

W,Grё

bnerに

ちなん で名付 け られ た よ うである。また,ほ ぼ同時期 に 広 中平祐が代数幾何学 の研究 か らグレブ ナー基底 と同一 の概念 を発見 している. 以下,論文 の構成 について述べ る. ｒ ｌ ｌ く ︱ ｌ ｔ

0, F諄

1章

では_,順序 と整列順序,環,多項式環 な ど,後 章 で用い る基本事項 について述べ る。

2章

では,項 順序 とモ ノイデアル を定義 し,モ ノイデアル が有限生成 である とい うデ イ クソンの補題 を示す。また,ディクソンの補題 を用 いて,項 順序 が整列順序であることを導 く.これ らの結果 は

3章

で有限回の単項簡約 で正規化 で きるこ との証 明や グL/ブナー基底 の存在証明な どで用 い られ る。 §2,1では,項のなす集合

T=T(″

1,… ""れ

)上

の項順序 と,指数のなす集合 Z。れ上の項 順序 を定義 し

,2つ

の補題 を示す` §2.2では,Z。つのモ ノイデアルを定義 し,ディクソンの補題 を示す 。さらに,項 順序 が 整列順序であ ることを導 く.

3章

では_,与え られ た項順序 のもとに_,先頭項,先頭単項式 ,先 頭指数,単 項簡約,正規 形,正 規化 な どの概念 を定義 し,す べての多項式が有限回の単項簡約で正規化で きることを 示す

.次

にグ レブナー基底 を定義 し,モ ノイデアルが有限生成 であるこ とを基 に グレブナー 基底の存在 を示す。また,グ レブナー基底による正規化 が二意に定まることを導 く。最後に, グ レブナー基底 か ら極小 グレブナー基底が得 られ るこ と,極小 グ レブナー基底 か ら簡約 グ レブナー基底 が得 られ ることを示 した後,簡 約 グレブナー基底 の一意性 を証明す る. §3.1で は,項 順序か ら単項式の大小 を定め,多 項式の単項式 の中で最大であるものとし て先頭 単項式 を定義す る。さらに先頭単項式 の倍数 を消去す る操作である単項簡約 を定義 し,項 順序が整列順序であることを用いて,すべての多項式が有限回の単項簡約 で正規化 で きることを示す. §3,2で は,イデアル のグ レブナー基底 を定義 し,イデアル に含 まれ る多項式 の先頭指数 か らなるモ ノイデアル が有限生成であることを基 にグ レブナー基底 の存在 を示す.こ れ よ

り

_,多

項式環

Ch,¨

"″

』の任意のイデアルが有限生成であること

(ヒ

ルベルトの基底定理

) が導かれ る.また_,グレブナー基底に よる正規化が一意 に定ま ることを示す。 §3.3では,極 小 グ レブナー基底,簡 約 グ レブナー基底 を定義 し,グ レブナー基底か ら余 分な多項式 を取 り除いて極小 グ レブナー基底 が得 られ ること,極小 グ レブナー基底か ら正 規化 によ り簡約 グ レブナー基底が得 られ ることを示す

.最

後 に,簡約 グ レブナー基底の一意 性 を証明す る。

4章

では

,0で

ない

2つ

の多項式 に対 して

S多

項式 を定義 し,イデ アルの有限生成系が グレブナー基底 であるか どうか判定す るブッフバーガー の判定条件 を導 く.こ れ より,グレ ブナー基底 を求 めるブ ッフバーガー アル ゴ リズムが得 られ る。 §4.1では

,S多

項式 を定義 し,イデアル

Iの

有限生成系 θ がグレブナー基底であるこ

0.序

とと「θ の任意の

2元

の

S多

項式の正規化が

0と

なる」 こととが同値である とい うブ ッ フバーガーの判定条件 を導 く.

§4.2で は,イ デアルの有限生成系にブ ッフバーガーアル ゴ リズムを適用す ることによ

1章

準

この論文では

,参

考文献

p]に

あるような群・環・体についての基本事項は既

知とするが

,後

章で必要となる順序

,環 ,多

項式環等についての用語や定理をこ

こに挙げておく。なお

,こ

の論文を通して次の記号を用いる。、

Z =

Z。

=

Z3 =

C =

{0,±1,=2,■ 3,…

} (整

数全体

) {0,1,2,3,…

} (非

負整黎全体

)

中

={し

_…

α

励

lα

L"α

れ∈

ZO} れ個 {α十づblα,bは実数

},

ただし

'2=_1 (複

素数全体)

C上

の η変数 κl,… "χπの多項式環 η変数 χl,¨っ “ηの項"争 …・χ静 全体のなす集合 多項式 θl,¨り

gmで

生成 されたCI"1,¨_""』 のイデアル 多項式 ノが多項式 クを割 り切 る 集合

4の

任意の元 αに対して

Aな

らば

Bで

ある ■ と

Bは

同値である

Aを

条件で定義する 多項式 ノ≠

0の

先頭単項式 多項式 ノ≠

0の

先頭項 多項式 ノ≠

0の

先頭係数 多項式 ノ≠

0の

先頭項の指数 ノに θによる単項簡約を行って んを得ること ノに

Gの

元による単項簡約を行つて んを得ること ノに θ の元による単項簡約を有限回行って んを得ること グレブナー基底 θ による ノの正規化 tl,t2∈ T("1,¨ "“為)の最小公倍数であるT("1,¨""れ)の 元 CI"1,¨・,"れ] T(ωl,…・,″れ) 01,¨

_"%)

ノ

lθ ∀α∈ 五 ス →

B

ス ⇔

B

4撃

彗 条件

LM(ノ₎ LT(/1 LC(ノ₎ LE(ノ)

ノー→ ん

_g ノ瓦言 ん

ノ÷ ん

NFさ_(∫) [ιl,ι 2]

1.準

備 1。

1

整列集 合

集合スの任意の

2元

α

,bに

対して

,α

∼

bで

あるか

,そ

うでないか

(α

≠

b),の

いずれ

かが成 り立つ とき,∼ を ス 上 の関係 とい う, 定義 1。

1集

合 ス 上 の関係 ≦ が次 の

3条

件 をみ たす とき順 序 _(関係)であ る とい う.た だ し,α,b,cは ■ の任意 の元 であ る。 (1)α ≦ α

(2)a≦ b,b≦

α → α

=b

(3)α ≦

b,b≦

C→

α≦C

・ α≦bを

b≧

αと表すこともある。

・ α≦わかつ α≠らのとき α<b,ま たは α≦

bと

表す。

定義 1。

2集

合 五 上の順序 ≦ が条件 「∀α,b∈ ■ に対 して α≦ b,ま たは α≧ らのいず れかが成 り立つ」 をみたす とき全順序(関係 )で ある とい う.

・ ≦が集合 ス上の順序であるとき

,に

,≦

)を

順序集合という。単に ス を順序集合 と

いうこともある。特に ≦が集合 五上の全順序であるとき,/1を 全順序集合という

.

・ に

,≦)を

順庁集合

,Sを

_{その部分集合とする。次の2条 件が成り立つとき}

,α

を

Sの

最ノ

￨ヽ

元という

: (1)α

CS

(2)α ≦ ″ (∀グ∈S) 定義 1。

3全

順序集合 ス が条件 「空でない任意 の部分集合 に最小元 が存在す る」をみ たす とき整列順序 _{(関係)で あるとい う。} ・ 整列順序 の定義 された集合 を整列集合 とい う.

1.準

備 6 1。

2

環

集合 ス に加法 十,と乗法 ・が定義 されていて,次の条件 (1)∼(8)を みたす とき,ス を の任意 の元であ り

,0,1は

ス の特別 な元で

0≠

1で

ある。 環 とい う。ただ し,α,b,cは И また_,積 α・らは αbと略記す る. (5)α

b=bα

(1)α

+b=b+α

(2)(α

+b)十 C=α

+(b+C) (6)(α

b)C=α(bC) (7)α

l=lα

=α

(3)α

+0=0+α

=α (4)α 十(―α

)=(―

α)十 α

=0 (8)α

(b+C)=α

b+α

C,(α

+b)C=α

C tt bC をみたす ―αが存在す る. 上の条件 を満 たす

Aは

,一 般 に可換環 と呼ばれ るが,こ の論文 では単 に環 とい うことにす る _{以下,環 についての基本事項 を述べ る。}

=0な

らば α

=0ま

たは

b=0」

が成 り立つ とき,ス を整域 ●環 ス において条件 「αb とい う。 ●環 ス にお いて条件 「α≠

0の

とき αα

1=α

lα

=1を

みたす α1∈

Aが

存在す る」 が成 り立つ とき

,ス

を体 とい う.α

lを

αの逆元 とい つ. ●環 ス の空でない部分集合

Iで

次の条件 をみたす ものを ス のイデ アル とい う. oα

,bcr→

α

+b∈

f oα ∈■_{,b∈ r=→} αb∈ ∬ ●環 ス の部分集合

Sに

対 して

,Sを

含む /1の イデアルすべての共通部分 は ス のイデ (S)と 表す

.Sを

_(S)の生成 アル とな る。これ を

Sで

生成 されたイデ アル といい,

S≠ 0の

ときは 系,ま たは基底 とい う.

(S)={α lSl+…

・

+αrSr l

α

バ ス

,S′

CS}

が成り立つ。また

_,(0)=0で

ある。ここで

0は

_{0}と

記すべきであるが

,以

下

,慣

用

的 に

0と

表 す こ とにす る。

・ 有限集合

S={sl,…

_{"Sm)に 対}

して

と表 す. (S)=(Sl,… ,Sm)

1.準

備 ・ ∬=(Sl,… っ

Sm)と

表 され るイデアル を有限生成イデアル とい う.また 「」は有限生成 である」 ともい う。 ●すべてのイデ アル が有限生成である環 ス をネー ター環 とい う。 ・ 環 ス がネー ター環 であることと,相 異な る.イ デ アルか らな る無限昇鎖列 が存在 しな い こ、ととは同値 である。ただ し,相 異なるイデアル か らな る無限昇鎖列 とは,イ デ ア ルの列 ム ⊆ち ⊆ ム ⊆ ………⊆島 ⊆ ム+1⊆ ……… の ことである.

oス

が体 で ある とき,ス のイデアル は ■ と

0の

み である。従 つて体はネー ター環 で ある, 1。

3

多項式環

ス が環であるとき,次の形の式 ∫(χ)を ″を変数 とする

A係

数多項式 とい う. ∫(″

)=α

π″π+αれ1″れ

1+…

・+αl■+α

O(α

れ:…,α。∈ス) αれ≠

0の

とき ∫(″

)の

次数は ηであるといい,deg∫(π

)=η

と表す

."を

変数 とする ス 係 数多項式の全体を

4″

]と表 し,4[π]を ■ 上の多項式環 とい う。然下,多項式環について の基本事項を述べる.

04回

は通常の多項式の加法 と乗法によ り環をなす

.特

に

_,Aが

整域ならばAレ]も肇 域である.

o変

_{数 ″}1,″

2に

対 して

,■

上の多項式環

4"11上

の多項式環 (■[″ll)レ列が定まる.こ れを A[″_1,″

_2]=(■

_[″11)[π2] とおき,ス 上の

2変

数 πl,"2の多項式環 とい う

.同

様に

,■

上の η変数多項式環￨ 五_[″1,…・,″れ

]=(■

["1,¨。,″π_11)[″ π] が定義 され る.

1.準

備

・ 体

F上

の多項式環

F[″_]は

単項イデアル整域である。すなわち

_,す

べてのイデアルは

1元

で生

.成

される

_.特

に

F回

はネニター環である

. 定理

1.4(Hilbertの

基底定理

,12,定

理

29.11)ネ

ー タ∵環上の多項式環はネーター

環である

.特

に

,体

F上

のη変数多項式環

Fh,…

っ″

』はネすター環である

.

o3章

_,§3.2で

グレブナー基底を定義し

,そ

れより

,Ch,…

_"χ

」がネ

Tタ

ー環であぅこ

とを導 く(系 3.13), 素 元 分 解 整 域 以下,整域 と素元分解整域についての基本事項を述べる. ・ 整域

4の

元 包に対 して,%z′

=1と

なる%′ ∈/1が存在す るとき

,%を

可逆元_(また は正則元)と い う。 ・ 整域 ス の元 α,bに 対 して,α

=zbと

なる可逆元 鶴∈

Aが

存在す るとき αと

bは

同 伴であるとい う。 ・ 整域 ス の元 α,bに 対 して,α ‐bcと なる

ccAが

存在す るとき,b′は αを割 り切 る といい,blα と表す。この とき,α を らの倍数

,bを

αの約数 とい う。 ・ 整域

Aの

可逆元でない元

p≠

0が

条件 「P l αb(α ,b∈ ■

)な

らばPlα またはPlb」 をみたす とき

,pを

素元 とい う。 ・ 整域

Aの

0で

も可逆元でもない元がすべて素元の積 として表 され るとき,■ を素元 分解整域(または一意分解整域)と い う. ・ 素元分解整域 ■ においては

,0で

も可逆元でもない元 αはすべて素元の積に同伴 を 除いて一意的に分解 され る。すなわち, α=pl p2・ …pπ

=910…

・⑫ と素元の積 として

2通

りに表 された ときは

,m=イ

であ り,適 当に番号 を付 け替 える とPこ と 銑 が同伴 にな るよ うにできる。 ・ 素元分解整域 とはI整数環

Zで

素因数分解 が成 り立つの と類似 の性質 を持つ整域 の ことである.

1.準

備

・ 整数環

Zや

体

F上

の多項式環 F回 は素元分解整域である

(P,例

26.q).Fレ

]の

素

元は既約多項式

(因

数分解できない多項式

)で

ある

. 定理

1.5(12,定

理26。

131)体

F上

の η変数多項式環 到″i,¨っ "」 は素元分解整域で ある。

・ 定理■

.5よ

り

_,見

変数多項式は既約多項式の積として

_,定

数倍を除いて一意的に表さ

れる。特に,FL,…

_"″

」の2つ の多項式の最大公約数

,最

小公倍数などが定義される

2章

項順 序 とモ ノイデアル

2章

で は_,項順 序 と

_,ノ

イ デ アル を定 義 し￨モ ノイデ アル が有 限生成 で ある とい うデ ィク ソンの補題 を示 す 。また,ディク ィンの補題 を用いて ,項順序 が整 列順序 で あ るこ とを導 く。これ らの結果 は

3章

で グ レブナ ー基 底 を考察 す る際 に必要 とな る。 2。

1

項 順 序

で

複素数体上の多項式環

Ch,¨

""』

の多項式∫

(χl,…

っχ

れ

)は

氏

L_→

=Σ

Ql_12・

1・

π

2あ

…″

ル

幌

11..∈

Q

と表 され る。ただ し,右辺 の和 は非負整数 の組 を1,¨っjη につ い て の和 で あ る。こ こでい くつ か の用語 と記 号 を定義 してお く。 ●α `L¨"づっ≠

0で

ある項 αJ… .2"1.・ "2わ °・_・″ηづ

2を

_{∫の単項式 とい う。ただ し,同}類項 は ま とめてあるもの とす る。単項式の係数 を除いた式 χlう1″2.2… .″η`,を項 と呼ぶ こと にす る。ただ し

,1=″

1°∬2°・…″π

Oも

項 とみなす ことにす る。また,(づ 1,…Ⅲη

)を

項 ■1づlπ212… .″η a2の_{指数 とい う} .

注意

:単

項式と項の定義は書物により異なる

.上

の定義は参考文献

p]と

_{同じであるが}

_,例

え

ば

,参

考文献降

]で

は

,単

項式と項の定義が上の定義と逆になっている。しかし

,高

等

学校教科書の数学I(啓_{林館,平成}

24年

度用_)などでは 「単項式の和 として表 され る式 を多項式 といい "¨」 と係数 を含 めたものを単項式 と呼んでいることもあ り,この論 文 では上の よ うに定義す ることに した.

・ 非負整数全体を

Z。

とおき

_,そ

の η個の直積集合をZ3と する

. Z。

={QL2ず 乱…

},Z3= ={し

L…

,α

紛

lαb…,α

η∈

ZO} η個 10

2.項

順 序 とモ ノイ デ アル また,Z番 の

2元

の和 を成分 ごとの和 として定める。 ・ 変数 ″1,¨ "″れの項全体 をT(″1,…""π)と お く・ "1,… "πれが明 白な ときは単に

Tと

表す。

T=T("1,・

・

,,"1)={″

_争″

_夕・

…″

_絆

_￨(を1,.・

・

,づ

π

)∈ ZOπ } ●

TD″

1を1"2j2_.″ れを

'に

対 して,そ の指数 か らなる非負整数 の組 (り1,"■ れ)∈ Zoれ を対 応 させ る写像は,明 らかに

Tか

らZ。れへの全単射である。 ・ 以下において

,X=(″

1,… ""π),づ =(づ1,…Ⅲη)と して

χ。

="Tπ

_{′… χ}

_締

と略記す るこ とが あ る. 定義

2,17上

の全順序 ≦ で,次 の条件 をみたす もの を項順序 (term Order)と い う. (1)ιl,ι 2,ι こT,ιl≦ ι

2な

らばt ιl≦ ιι2

(2)任

意 の ι∈

Tに

対 して 1≦ ι 注意

:上

の定義の条件(1)において

,tl≪

t2な らば ιl≠ ι

2で

あるから,ιιl≠ ιι2と なるの で,ιιl≪ ιι

2が

成 り立つ.

o次

_{の条件で定まる}

T上

の順序 ≦ は項順序である(辞書式順序)。 ただし,メ は「≦ か つ ≠」を表す. 補題 2。

2

ιl,ι2,t3,t4∈

rが

ιl≦ ι2,ι3≦ ι

4を

みたせ ば ιl ι3≦ t2ι

4が

成 り立つ

.特

に

_,tlく

ι2,ま たはt3≪ j4のときは ιl ι3く ι2ι

4が

成 り立つ 。 ■1 ． り ″ ・                                     ， ＜                 カ

れ

 

 

協

わ

コ

わ

い

 

 

﹁

も

勧

励 

_鋭

 

 

購´



一

 

＋。．

出

書

枷

 

翔

 ．

_卸

﹁

輸

丸

 

也

 

欄

紛   と     る     ¨     ・   ・_，

．

メ

 

・

_九

 

 

あ

 

 

＋・

一

 

．

司

ｒ   ≠ ′     で       ・   ・_η   ・

情

断

項

釘

⇔



 

 

 

_報

・ 



 

 釘

_⇔

砕

 

 

 

断

 

 

 

呻

¨         の

〓り

  

 趾

  

 一鍔

ノ ュ       る ≪ メ           ま 笏 れ ら れ     定         ″ イ         で ¨       件       タ

一Ｗ

 

 

嫉

 

 

 

ウ

″       次 ●

2.項

順 序 とモ ノイデ アル 12 【証明】 定義2.1の条件(1)よ り ιl≦ ι2,ι3≦ ι

4 =→

ιl ι3≦ ι2ι3,t2ι3≦ ι2ι

4 =→

ιl ι3≦ ι2ι4 が得 られ る。特 に,ιlメ ι2,または ι3メ ι

4の

ときは ιl ι3≠ ι2ι4と なるので, ιl ι3く ι2ι

4が

成 り立つ

. ￨

定義 2,3 ZOれ の全順 序 ≦ で次 の条件 をみたす もの をZoπ ′上 の項順 序 とい う。 (1)α ,b,C∈ ZOれ ,α ≦

bな

らば α

+c≦

b tt c

(2)0豊

(0,… 。,0)≦ α (∀α∈Zoれ) 順序 ≦ が

T=T(″

1,¨ "ππ

)上

の項順序であるとき,づ =(づ1,…,づπ),ブ =(プ1,…っプれ)∈ Zoれ に 対 して

づ

_{≦ブ 基}

aた

…

.″

がπ≦■■―

・

″

ル

と定 める と,ZOη 上 の項順序 とな る

.逆

に,Z。れ上の項順序か ら

T=T(″

1,"ギ

η)上の項 順 序 が定 ま る。 ・ 項 順 序 が整 列順 序 で あ る こ とを定理 2.11,系 2.12で 示 す 。 補題

2.4≦

が るπ上の項順序′α,b∈ Z。れのとき_{,α ≦α}

+bが

成 り立つ. 【証明】 定義 2.3の 条件 _(2)よ り

,0≦

bが

_{成 り立つ。これに条件 (1)を 用い}

ると

0+α

_≦

b+α

となるのでα≦α+bを 得る

.

ヽ

ロ

●α_{,b∈ ‰}れが項順序 ≦ について α≦

bを

みた していて も

,b=α

+cと

な るc∈ Zoη が存在す るとは限 らない。例 えば

Z02上

の辞書式順序 について α

=(2,4),b=(3,1)

｀ とすると,α ≦

bで

あるが

_,b=α

+cを

みたす

ccZ。

りは存在 しない. 補題 2.5 ZOれ の項順序 ≦ について次が成 り立つ. 【証明】 仮定 より,πlll…・″πtη が πl'1…・″πブ・ を割 り切るのでjん ≦」んが成 り立つ.rん =ノλ―をたとおけば(γl,¨っrれ)∈ Zoれ であるか ら,補題2.4よ り

2.項

順序 とモ ノイデ アル 13 が得 られ る. 2。

2

モノイデアル

定義

2,6Z。

つの部分集合

L(≠

0)で

次の条件をみたすものをモノイデアルという

. α∈

Z,b∈

ZOπ

=)α

+b∈

L

モ ノイ デ アル は項1贋序 とは独 立 に定 ま る概 念 で あ る. p.11で述 べ た

, Tか

ら

ZOnへ

の全 単射 に よ り

,モ

ノイ デ アル ら に対 応 す る

T=

a″

1,…_"″

れ

)の

部分集合を■ とすると

,定

義

2.6の

条件は次のようになる。

ι_{L∈ ■}

_{,t∈ T}

→ ιL ι∈

TL

■ ■ ●         ● 補題

2,7モ

ノイデ アル の和集合はモ ノイデアルである.

【

証明】

五バ

jCI)を

ZOれ

のモノイデアルとして

,

アルであることを示す。α∈

Z,b∈ Zoπ

とする。ある

あるか ら,α tt b∈ Lじ が成 り立つ。従 つて

9+ろ

∈五 モ ノイデ アル である。

L=∪

_た

_.Lづ

がモノイデ

j∈

_{」に対してα∈ム で}

も成り立つ

,ゆ

えに 五は

￨

命題

2・

8Z。

れの部分集合

S(≠

0)に

対して

MO叩 (S)={S+α lSCS,α ∈_{Zoη }} はモノイデアルである.こ れを

Sの

生成す るモノイデアル とい う.

【証 明】 b∈

MOno(S),C∈

Zoれ とす る。仮 定 よ り

b=s+α

(s∈ S,α ∈Zol)

と表 され る。これ よ り

b+C=S十

(α tt C) (α

+C∈

Zoれ)

とな るの で

,bttc c Mono(S)が

成 り立つ 。

2.項

順 序 とモ ノイ デ アル 14

●

Mono(S)=∪

_{scs MOno(s)で}

ある。

定理

2,9(デ

イクソンの補題

_)Zoη

_{のモノイデアィレは有限生成である。すなわち}

,任

意

のモノイデアルは適当な有限集合

_{{al,… "α}

′

}に より

MonO(αl,¨ "α_`)と

表される

. 【証明】

Lを

Z。れのモノイデアルとして_,η に関す る帰納法で証明す る.

(1)2=1の

とき,五 は下に有界

,か

つ空でない

Zの

部分集合 であるか ら, 通常の大小関係 での最小元

sを

含む。この とき

,モ

ノイデアルの定義よ り

Z⊇

MonO(S)と

なる。また,"∈

Zに

対 して

,s≦

″より ″

=S+("―

S),

・ ―

SC Zo

とな り,″ ∈

Mono(s)を

得 る。従つて 五 ⊆MOn。(S)も 成 り立 ち

,L=M91o(s)

が 得 られ る。ゆ え に

,Eは

有 限生 成 で あ る. (2)η

=た

のとき成立すると仮定し

,

五を

Z。

ん

+1の

モノイデアルとする

. Zoλ

+1=Z。

ん×

Z古

であるから

Zoλ

+1の

元は

(α,り

,

α∈

Zoた

,t∈

Z。 と表 す こ とがで きる。ここで '∈

%に

対 して

五じ

={α

∈

Zoん _￨(α,t)∈

ル

_} とお く。この とき

Lが

モ ノイデアルであることか ら,任意の α

cL,b∈

ZOた に対 して,α ∈五t力｀成 り立つ ことか ら, α∈五づ→ (α,り ∈五 ⇒ (α,づ)+(b,0)∈

L⇒

α

+b∈

Lづ より,α tt b∈ ム が成 り立つことになる。ゆえに,五をはZ。たのモノイデア ル とな り,帰納法の仮定か ら有限生成である

.補

題2.7よ り

∪

Lj づ∈Z0 もZOん のモ ノイデ アル とな るが_,帰納 法 の仮 定 か ら有 限生 成 とな り

∪

Lづ

=MOn。

_(αl,¨ "α_`) づ∈Z0

2.項

順 序 とモ ノイデ アル 15 と表 され る

.一

方,づ,ノ ∈

Zoが

づ≦ プをみたす とき,任意 の α∈L乞 に対 し て

α∈

Zづ

⇒

_(α,り)∈

L→

_{(α,')+(0,ノ}

ーの∈

Z→

_(α,プ)∈

L→

α∈

L′ が成 り立つ ので,Lづ ⊆L′ とな り LO⊆ 五1⊆ L2⊆ ……… は昇鎖列である.αl,¨ "αιをすべて含む よ うな 五れ を一つ選ぶ と ∪たzo Zを

=Mono(α

l,¨っの

)

｀ であるか ら 五0⊆ Ll⊆

L2⊆

・….… _{⊆ 五}

m=五

_れ+1 が成 り立つ。ここで,0≦ j≦

m-1の

各 りに対 して,L。 も有限生成だか ら

五

_づ

圭

MonO(bf),¨

っ

b総₎ と表す ことができる

.た

だ し,島

=0の

ときは 鶴

j=0と

してお く.こ の とき 五は次の元を含む。 (br),t)…

っ

(b総,の (0≦

を≦m-1),(α

l,η

⇒…

.,(α `,m) これ らの元 で生成 され るモ ノイデ アル を 五′とお く。

Z=五

′を示せ ば証 明 が完 了す る

.L⊇

ι′は明 らかだか ら_,五 ⊆Z′ を示 せ ば よい。そ の た め に,任 意 の (α,ノ)∈ 五 を選 ぶ

.0≦

ノ≦ 鶴

-1の

ときは

α∈島

=MOn。

(by),っb総) であ るか ら と表 され るので,

α=bF+♂

o′

∈

Zoた

,1≦

ん≦れ

₎ (α ,ノ)=(bF),プ)十 (α

′

,0)∈

五

′

2.項

順序 とモ ノイデ アル 16 が成 り立つ

.J≧

鶴 の ときは 五ブ

=Lm=Mono(α

l,… "αι) よ り α=αん+α′ (α ′_∈Zoた

,1≦

ん≦イ) と表 され るので, (α ,ノ)=(α ん

,m)+(α

′ ,ブ ー鶴)∈ 五′ が成 り立つ

:以

上で 五

=五

ノが得 られたので,定理2.9が_{証明 された。}

￨

系 2.10Z。れのモ ノイデアルが

Sで

生成 され るとき

,有

限部 分集合 乱 ⊆

Sが

存在 し て

_{,Mono(品 )=MOn。}

_(5)を

みたす.

【

証明】

前述の定理

2.9よ

り

_,MonO(S)は

有限生成であるから

MOnO(S)=MOnO(α

l,¨ "αι

)

αl,…"αι∈

Mono(S)

― をみ た す αl,¨ "α

_`が

存 在 す る

.こ

の と き,各 α′は

Mono(S)=∪

b∈s MOn。(b) の元 で あ るか ら

α

_ブ

=%+% %∈

S,%∈

Zoπ と 表 さ れ る 。 こ れ よ り

M6nO(%)⊆

MOnO(り

)が

成 り立 つ の で, MOnO(S)=MOnO(α l,…

"αι)=∪ MOnO(Q)⊆ ∪ MOnO(bづ)⊆ MOn。(S)

づ=l C=1

が得られる。ゆえに跳

={bl,¨

"bι}と

おけば

MOnO(品 _)=∪ MOn。 _(bり =MOnO(S)

`=1

が成 り立つ.

定理 2.1■ Zoπ 上 の項順序 は整列順 序 であ る.

【証明】 Zoη 上の項順序を ≦ とする

.≦

が整列順序であることを示すには,

2.項

順 序 とモ ノイデ アル 17 たモノイデアル

Mono(S)に

ついて,系 2.10よ り

,Sの

有限部分集合 品 が存在 して

Mono(品

_)=MOn。

_{(S)を みたす}

.馬

の最小元をs。 とお く。任意のb∈

S

に対 して

,S⊆

MOnO(品

_)に

注意すれば,ある

.sc跳

が存在 して,

b=s+c (c∈

Zoη₎ と表 され る.s。 ≦

sで

あ るか ら,補題 2.4よ り

SO≦

S≦

S+C=b

が成 り立つ

.ゆ

えに

sOは

Sの

最小元である

.以

上で ≦ が整列順序であること が示 され た

. ￨

｀

_T=T("1,“

りをっ

)上

の項順序はZoπ 上の項順序 と同一視 できる.こ とか ら次の系が成 り立つ.

系

2.12T=Щ

χ

l,… "χ

お

)上

の項順序は整列順序である

.

3章

グ レブナニ基底

3章

で証明す る定理 のほ とん どすべてが一般の体上の多項式環 において成 り 立つが,こ の論 文では簡単のため,複 素数係数の多項式環 CI"1,"""』 において 考察す る。以下,こ の章 を通 じて,項のなす集合

T=T(■

1,¨っ "η

)上

に一つの 項順序 ≦ が与 え られているもの とす る。この項順序 の も とに,先頭項,先頭単 項式,先 頭指数 ,単 項簡約,正 規形,正 規化 な どの概念 を定義 し,すべての多項式 が有限回の単項簡約で正規化できることを示す

.次

にグ レブナー基底 を定義 し, モ ノイデアルが有限生成であることを基 にグレブナー基底 の存在 を示す.また, グ レブナー基底 に よる正規化 が一意 に定 まることを導 く。最後 に_,グレブナー 基底 か ら極小 グ レブナー基底が得 られ ること,極小 グレブナー基底か ら簡約 グ レブナー基底が得 られ ることを示 した後,簡 約 グ レブナー基底の一意性 を証明 す る。 3。

1

単項簡約

まずい くつかの用語 と記号 を導入す る。簡単のため,Q."¨,こπ "争・…″″ を αJ χイと略記 す る。

(1)係

数が

0で

ない

2つ

の単項式 αづχづ

,%Xれ

こ対 して ● χづくχ′の とき,α `χづ≪

%χ

′と表 し

,%X′

は αtt χづよ り大きい とい う .

oX」 =χ

′の とき,α:χJ些

%χ

′と表 し,αじX。 と α′χ′は同等であるとい う. α ・χこと α′χ′が同等の とき,係 数 を除いた項の部分 χづと χ′は一致す るが,係数 が一致す る とは限 らない.

(2)多

項式 ∫

c CI"1,… "″

Jの

,係

数が0で ない単項式の中で

,項

順序 ≦ゅヾ

最大である項

からなる単項式を

,∫

の先頭単項式

(leading monomial)と

いい,LM(∫

)と

表す。先

18

3.グ

レブ ナ ー 基 底 ■9 頭単項式は項順序に依存するので,正確 には LMく(∫

)な

どと評すべきであるが,こ の 章では項順序 ≦ をすつ固定 してあるので,単にLM(ノ )と表す ことにす る。

(3)LM(∫

)=α

じXう の とき_,χづを先頭項_{(leading term)と} いい_{,LT(∫ )と}表す。また,αこを 先 頭 係 数 (leading COettcie飢 )と い い,LC(∫)と表 す 。こ の と きLM(ノ

_)=LC(ノ

)・LT(∫) である.

(4)差

∫―LM(∫

)を

余項 といい,Rem(∫ )と 表す.

(5)LM(ハ

=Ql"¨12″争….″静 であるとき,(ti,… "づπ

)を

∫の先頭指数(leading exponent)

といい

,LE(∫

)と

表す

.ま

た

,部

分集合

S⊆

C[χl,¨_"∬

」に対して

,

LE(S)={LE(∫

_)￨∫

∈

S}

とおく

,LE(S)は

Zoπ

の部分集合である。

補 題

3.10で

_{ない ∫},g∈ CIπl,¨ "″』 に対 して

,LM(ヵ

)=LM(∫

)LM(g)が

成 り立う.

【

証明】

LM(∫

_)=α

`Xを

,LM(g)=ち χ′とする。このとき

∫

=αJ

χこ十

Rem(∫

), g=場

X′

十

Rem(g)

よ り,

∫

g=α

を

_しχ

じ

+′

_+Rem(∫

)(場

χ

J)十 (α `χ

う

)Rem(ク

)+Rem(ハ

Rem(g)

と表される。

Rem(∫_)(し

χ′

_)の

単項式は

_,Rem(ノ

_)の

単項式α

グ

Xノ

により

α

_ゲちχ

ダ

+′

として表 される。χじ

>χ

づ

′

であるから

,項

順序の定義

2.1の

後の注意より

, X'+′ ト リ(づ ′_十′

が成り立つ。同様に

(α

α

XC)Rem(g)の

単項式α

づ

り

X2+′

′

についても

χこ+′ 卜 Xt+′′

3.グ

レブナー基底 20

が成り立つ。また

,Rem(∫

)Rem(g)の 単項式は

Rem(∫ )の

単項式α

グχダと

Rem(θ₎

の単項式 し′χブ

′

の積

α

_づ

′

_け

Xゲ+ブ

′

として得られるものの中から同類項をまとめた和であるが

,補

題

2,2よ

り

Xじ+′ >」χづ′十ノ が成 り立つ。以上か ら LM(ノ

_ク

_)=αぅ

_ちχ

ttJ=LM(∫

_)LM(g)

′

が得 られ る。 ■ ■

命題

3,2 CIπl,…

っ″

』のイデアル

fに

対して,LE(I)け

Zoれ

のモノイデアルである

.

【証明】 ∬≠

0で

あるから,LE(∬)≠

0で

ある。次に,J∈ LE(」),ブ ∈Zoη と

す る.この とき_,ある ∫∈」に対 して

,LM(∫ )=α

をχじとなる(α_・≠0)・ 従 って ∫=αtt XO+Rem(∫) と表 され るが

,Iは

イデアルだか ら X′ _∫=αtt χう +′

+χ

J Rem(∫ )∈ 」 が成 り立つ

.補

題3.1よ り LM(X′ ∫

)=α

:χづ+′ となるので づ+ブ

=LE(χ

θ_∫)∈ LE(I) が得 られ る

.ゆ

えに

LE(I)は

モ ノイデアルである.

3.グ

レブナー基底

定義

3,3∫,ク c CIπl,¨:,″

』

,ク

≠

0と

して

,∫

の単項式の中に

,ク

の先頭単項式

LM(g)

の倍数 χ ≠

0が

あるとする。このとき

ν

ん

=∫

LM(ク

)ク

とおき

,∫

からんを得る操作をgに ょる単項簡約といい

,

∫→

_g

ん

と表す 。

Gを

0で

ない多項式の有限集合 とす る

.多

_{項式 ∫に θ の元によう単項簡約を行つて多項} 式 んが得 られ ることを

Gに

よる単項簡約 といい ノプ ん と表す.また,∫ に σ による単項簡約 を

0回

以上,有限回行 つて んが得 られることを

∫だ豪 ん

と表す ことにす る.

定義

3,4G⊆

Ch,¨

"χ

』 を 0で ない多項式の有限集合とする

.多

項式 ∫に対して θ

のどの元による単項簡約も行えないとき

,∫

は

Gに

関して正規形であるとい う

.ま

た

,

単項簡約を有限回行つて正規形に変形することを正規化という

. ●正規化により得 られた多項式を「正規化」 とい うことがある。 ・ ノが θ に関 して正規形であるとは,∫ の どの単項式も

,Cの

元の先頭単項式の倍数 ではない ことである. ●

0は

どのよ うな

Gに

対 しても正規形である.

注意

:正

_{規形は必ずしも一意的ではない。例えば,Ch,"列 上の辞書式順序で}

, 21

θ

={″

1,ど +″2}

3.グ

レブナー基底 22

により″

_{子を正規化する方法は}

2通

りあり

と異 な る正規形 が得 られ る.

χ

_:プ

0

″

_【

薦

″

2 項順序の拡張

p.18で

,項順序か ら誘導 され る単項式の間の関係、く と 璧 を定義 したが,そ れ を多項式の間の関係 に拡張 してお く。

(1)任

意の多項式 ∫≠

0に

対 して 0メ ∫ と定める.

(2)0で

ない

2つ

の多項式 ∫

,gに

ついては,そ れ らを係数が

0で

ない単項式 の和 として 大 きい方 か ら順 に表す.

ノ

=ν

l+A42+… ・

AZr(ン

1卜

■

6浄

…

'ト

ル年

₎

g=Ⅳ

_l+Ar2+…

_・十馬

_(Nl卜

Ar2卜

…・■Ⅳつ

,こ こで簡単のため r≦ sと して,次 のよ うに定める.

(1)A4笙

既 (j=1,… っι

-1),か

つ

A4く

馬 となる t(≦

r)が

存在す る とき ∫メ g と定 める。 (11)A4堅 場 (づ =1,… ♯

-1),か

つ ハイι卜 凡 となる ι(≦

r)が

存在す る とき ∫浄 g と定 める。 (iil)A4堅 既 (づ =1,¨"r),かつ

r=sの

とき,∫ と クは同等であるといい ∫堅ク と 表す。

(iV)A4竪 義

(J=1,…_"r),か

つ

r<Sの

とき∫くクと定める

.

補題

3.5単

_{項簡約∫ブ ん}

において

,∫

卜んが成り立つ

.

【

証明】

_{単項簡約 ∫ブ んが}

g∈

Gに

よるものとする

.こ

のとき

,∫

の単項

式で クの先頭単項式 LM(g)の 倍数であるもの χ ≠0が あり

,

ん

=∫

LM(g)ク

3.グ

レブナー基底 23

と表される。ここで ∫を単項式の和として

∫

=Σ

_{E Aグ}

十ν

tt

Σ

E γ

″

M′ 丼■/」 A/f″ く■イ と表す と

ん

=Σ

χ′

―

滋「 ′澪 ■イ

となる

.∫

とんの単項式は ν よ

∫―Σ

M′ 卜M

蒟 路

Цの

す

_{几 ザ}

リ大 きい部分 が一致す るので A√

′

=/1/f+Σ

_{E M″}

M″《■/f と

、

ん

―

.乃

/=―

詔揚

Re弧

の

十

A,IIM″

を比べれ ば よい。 ∫―ΣM′

>Mχ

′の先頭単項式 は

Mで

あ り,ん ―ΣM′>iィ A′ の先頭 単項式 は存在 した として もAイ よ り小 さい 。ゆえに ∫卜 んが成 り立 つ

,￨

定理 3,6θ ⊆

CI″1,¨ "″

れ

lを

0で

ない多項式の有限集合とする

.こ

のとき

,任

意の多

項式 ノは,θ による単項簡約を有限回行 うことにより正規化できる

, 【証明】 θ による単項簡約を有限回行 つても正規化できない多項式が存在 し た と仮定 し,それ ら全体のなす集合を

Sと

する。ここで

LT(S)={LT(∫

_)￨∫

∈S}

とおく

.系 2.12よ

りLT(S)に 最小元 ι

。が存在する。

LT(∫_)=ιoと

なる ∫∈S

を選ぶ・ ι

。を項とする ∫の単項式を ■

4と

する。

Sの

定め方から

_,Gに

よる

単項簡約の無限列

∫子 メ⇒プ ∫②

が存在す る

.仮

にある単項簡約

∫

(ん)

∫

(た+1) で1る が消去 されたとすれば,t。

>LT(∫

鮨+1))と な り,∫(λ

+1)/sと

なるので , ∫(た+1)は θ による有限回の単項簡約で正規化 され ることになる。このとき_,ノ も σ による有限回の単項簡約で正規化 され ることになるので仮定に反する。従つ て_,どの単項簡約の無限列においても ユ

_4は

消去 されない

.す

なわち,単項簡約 → … … G

↓で

3.グ

レブナー基底 24

はすべ て ∫―

Moに

対 して行われていることになる。しか し,ιO卜 LT(∫ ―A4o)

となるので,∫

-14は

有限回の単項簡約で正規化できるはずであるから,∫ も 有限回の単項簡約で正規化できることにな り,矛盾が生 じる。

￨

3。

2

グレブナー基底の定義と存在

定義

3,7(グ

_{レブナー基底)f≠}

0を

Cレ1,…;″

」のイデアルとする

.0で

ない多項式

からなる有限集合 θ

={ク1,―

_"%}⊆

」が次の条件

(*)を

みたす

￨き

,Iの

グレブナー

基底という。

(*)任

意の ノ∈

J―

{0}に

対して

,あ

る

gJ∈

σが存在して

,LTb)I LT(∫

)と

なる

.

・ {1}は

CI″1,…

っπ

』のグレブナー基底である。

・ 以下

,￨「

イデアル Iの グレブナー基底」というときは

,J≠

0が 仮定され

‐

Cい

るもの

とする

.

注意

:イ

デアル Iの グレブナー基底は一意に定まるわけではない。θ

={θl,¨

っ

gπ

}が

Iの

グレブナー基底であるとき

,任

意の∫∈∬―

{0}を

付け加えた

C={gl,"%,∫

}も

Iの

グ レブナ ー基底 で あ る.

定理

3.8(グ

・

レブナー基底の存在)Ch,¨

"″

」のイデアル

JI≠

0に

はグレブナー基底

が存在す る。 【証明】 ∬≠

0を

イデアル とする

.命

題3.2よ り

_,LE(I)は

ZOπ のモ ノイデ アルである。デ ィクソンの補題_(定理2.9)よ _り,LE(∬

_)は

_{有限生成であるか ら} LE(」

_)=MOn。

_{(α l,… .,αm)} と表 され る。ここで α

`=LE(gj)(づ

=1,2,¨

"m)

をみ たす

0で

な い多項式 g。 ∈

I選

び

θ

={ク1,・

・

・

,gm}

3.グ

レブナー基底 25

が」のグレブナー基底であることを示す

.任

_{意の ∫∈}

I―

_{0}に

対して

, LE(∫_)∈

LE(f)=MOn。

_{(α l,…} "α

m)=∪

MOn。 (%) を₌₁ であるか ら, LE(ノ_)∈ MOn。_(αじ) となる αづが存在す る。この とき,あ る プ∈Z。れにより LE(∫

_)=α

_じ十ブ と表 され るので

,X=("1,¨

メ れ)なる略記 で LT(∫

_)=χ

LEc)=χ

%χJ=LT(gj)χ

′ が成 り立つ

.LTし

)I LT(∫

)を

みたす gj∈

Gの

存在 が示 されたので

,Gは

」 のグ レブナー基底 である

: ￨

次 に,グ レブナー基底 の諸性質にういて述べ る.

補題

3,9σ

={gl,…

っ

%}が

0で

ない多項式からなる有限集合

,∫

が

0で

ない多項式

, ∫一_か んであ っとき,単項本 凡 と 多ん∈

G(1≦

た≦ イ

)が

存在 して

ん

=∫

Σ凡働

た

た=1 : と表 され る。

【

証明】

仮定より

,適

当な 動た∈

G(1≦

た≦イ

)が

存在 して

∫―→∫

(1)一

→∫

(2)__〉 .… .:..…

_→

_ノ

(イ

)=ん

θ '1 9'2 g,3 θi`

3.グ

レブ ナ ー 基 底 26 と表 され る.また,単項簡約 の定義_(定義3.3)よ り,単項式 凡

(1≦

た≦ イ)が 存在 して

∫

9=∫ ―凡働

1

∫

(2)=∫(1)一

_馬

_92=∫

(」_Vlヵ

_l+馬

₉₂₎

∫

(ι

)=∫ ―

(Ⅳ

191+Ⅳ

b

θ

12+…

・

+恥

gt′ ) が成 り立つ.

補題

3.10ク1,…

っ

gmを

0で ない多項式

,I=(θ

l,…

_"gm),∫

∈」―

(0},∫

_÷

んであ

るとき

,ん

∈」である。

【

証明】

補題

3.9よ

り

_,単

項式 凡 とク

_九∈θ

_(1≦

ん≦イ

_)が

存在して

ん

=∫

―ΣE Щた多ん

た=1

と表される

.∫

∈

I,gこ

_ん∈」

_(1≦

た≦イ)で あるから

_,ん

∈Iで ある。

補題

3.1l G={gl,…

_"%}を

イデアル

Iの

グレブナー基底とする。このとき

,任

意の

∫∈

J―

_{0}に

対して

,∫

_÷

0が

成り立つ。

【

証明】

∫∈」―

{0}と

して

,∫

_÷

んとおく・補題

3.10よ

り

_,ん

∈Iで あ

る

,こ

こで

,ん

≠

0と

仮定すると

,グ

レブナー基底の定義

(定

義

3,7)よ

り

,あ

る

の∈

Gが

存在して

LT(ヵ

_)ILTo)

とな るが,これ は,ん が正 規形 で あるこ とに反す る.ゆえに ん

=0が

成 り立 つ 。￨ ■ ■ 定理 3。

12イ

デ アル 」の グ レブナー 基底 は

Iの

基底 _(生成 系)で あ る.

【

証明】

G={gl,っ

%}を

イデァル 」のグレブナー基底とする

.I⊇

(gl,…

っ

gm)は

明らかであるから

,I⊆

、

(gl,っ

%)を

示せばよい。任意に ∫∈

∬―

_{0)を

選ぶと

,補

題

3.11よ

り

,∫

_÷

0が

成り立つ。また

,補

題

3.9よ

り

_,単

3.グ

レブナー基底 27 項式 Arkと gjん ∈θ (1≦ た≦イ

)が

存在 して'

0=∫

―Σ 肛た

ヵ

_ん

た=1 が成 り立つ.こ れ よ り,

∫=Σ 凡みん∈

0…

,L)

た=1 が得 られ るので,」 ⊆(ク1,… "θ‰)が示 された, 任意のイデアル f≠

0は

グレブナー基底をもち,グレブナー基底は 」を生成す る.グ レブ ナー基底は有限集合であることより,次の定理が得 られる.

系

3。

13(ヒ

ルベル トの基底定理

)ch,…

""」

の任意のイデアルは有限生成である

. 定理

3014(グ

レブナー基底による正規化の一意性

)Gが

イデアル 」のグレブナー基 底であるとき

,任

意の

0で

ない多項式 ∫の

Gに

よる正規化 は一意的である. 【証明】 ∫の θ による正規化 として,多 項式 ん1,ん

2が

得 られた と仮定する. この とき_,補題3.9よ り,単項式 凡

,A4と

Gの

元 働1,ヵんが存在 して

ん

1=∫

―Σ凡‰

ん

2=ノ

Σ

4動

ん

が成 り立つ。これ よ り

ん

1 ん

2=Σ

鴫

%ん

―Σ凡働た∈」

ん た

が得られる。ん1-ん

2≠

0な

らば

,,θ

がグレブナー基底であることから

LT(θ j)I LT(ん

1-ん

2) をみ たす クづ∈θ が存在 す る こ とにな り,ん1,ん

2が

正規 形 で あ る こ とに矛 盾す る

.ゆ

えに ん

1-ん

2=0,す

なわ ち,ん

1=ん

2が

成 り立つ 。

￨

●以下

,∫

のグレブナー基底 θによる正規化を

NFG(∫ )と

表すことにする

. ■ ■

3.グ

レブナー基底

●θがイデアル 」のグレブナー基底であるとき

,乗1余

環

CI"1,¨

っ″

』

/1の

∫の属する

剰余類の代表として

NFG(∫

_)を

選ぶことができる

. 定理

3.15θ

をイデ アル ∬のグ レブナー基底 とす る。この とき,次の同値が成 り立つ.

∫∈

I

⇔ NFG(∫

)=0

【

証明】

ノ∈」とすると

,補

題

3.10よ

_り,NFG(∫

_)∈

Jと なるが

,fに

含まれ

る正規形は 0の みであるから,NFG(∫

_)=0が

成 り立つ。逆に

,NFc(∫

)=0と

仮定すると

,補

題

3.9よ

り

_,単

_{項式 凡 と多ん∈θ が存在 して}

NFGげ

)=∫

―Σ凡免ん

=0

ん

∫

=Σ

凡働

た

げ

ん を得 る.

3.3

簡約グ レブナー基底

補題 3。

16θ

をイデ アル

Iの

グ レブナー基底 とす る

.σ

の多項式 θ_,ん (g≠ ん

)が

LT(g)I LT(ん

_)を

みたす な らば

,G―

{ん

}も

」のグ レブナー基底である.

【

証明】 任意のノ∈∬―

{0}に

対して

,ク1∈

σ―

{ん

}で

LT●

_1)￨「

_(∫) となるものが存在す ることを示せ ばよい

.θ

は

Iの

グ レブナー基底であるか ら,あ るg2∈

Gが

_{存在 して} LT●

2)￨「

(ノ)

をみたす

.ク2≠

んならばθ

2∈

G {ん

}よ

り

,ク

1=g2と

すればよい。ク

2=ん

な

らば_{,LT(θ)ILT(ん )よ} り_{,LT(ク )ILT(∫ )と} な るの で

,91=gと

す れ ば よ い 。￨ となることか ら,

3.グ

レブ ナ ー 基 底 29

定義 3,17(極 小グレブナニ基底

)G=

する。任意の

1≦ J≠

_{ブ≦鶴 に対して}

,

レブナー基底という。

{ク1,¨

っg"}を イデアル ゴのグレブナー基底と

ET(a)ILT(ヵ

_)が

成 り立つ とき

,Gを

極小 グ ・ 補題 3.16に 従つて,グ レブナー基底か ら,順 次,余 分 な多項式 を取 り除 くこ とによ り 極小 グ レブナー基底 が得 られ る。

補題

3・

18θ

={gl,… "`‰

}を

イデアル Iの 極小グレブナー基底とする。このとき

,G

の各元 の先 頭 項 はす べ て相異 な る. 【証 明 】

1≦

J≠ ブ ≦

m,か

つ

LT幌

)=LT(ヵ

)で

あ る とす れ ば,ET(gj)￨

LT(%)と

な り,θ が極 小 グ レブナー基底 で あ る こ とに反 す る

.ゆ

えに

,Gの

各 元 の先頭 項 はす べ て異 な る。

￨

定理

3.19イ

デアル ∬の極小 グ レブナー基底 の先頭項 か らなる集合 は極小 グ レブナー 基底の選び方 によらず一定である.

【

証明】

_{G={gl,… "%},F={A,¨}

っ九

}を

イデアル

Iの

極小グレブナー基

底とする

.Fが

グレブナー基底

,ク1∈

∬であるから

,あ

るん∈

Fが

存在して

, LT(ん_{)I LT(gl)と} な る。一 方

,Gが

グ レブ ナ ー 基 底,ん ∈ ∬で あ るか ら,ある gん ∈

Fが

存 在 して,LT(θ_{ん)I LT(ん)と}な る。この とき,LT(ク た

)ILT(gl)が

成 り 立 ち

,Gは

極 小 グ レブ ナ ー 基 底 で あ るか らgた =ク1と な る.従っ て LT(ん )I LT●

1), LT●

1)I LT(ん) となるので 「

ol)=LT(ん

) を得 る

.Fの

番号を付け替えて

LT●

_1)=LT(■

₎

とする

.m≧

2の

ときは

_,Fが

グレブナー基底

,θ2∈

fで

あるから

,あ

るん∈

F

が存在して

,LT(ん

)I LT(g2)と

なる。上と同様にして

LT(g2)=LT(ヵ

₎

3.グ

レブナー基底 30

が得られる。ここで

,ET(■

)=LT(gl),Gが

極小グレブナー基底であるから

ブ≧2で ある

.Fの

番号を付け替えて

LT(θ

_2)=LT(ん

₎ として よい。以下,同 様 にすれ ば

,m=ι

であ り LT(θ

_l)=LT(■

_),LT(ク

2)豊 LT(ん_),…… … …

,LT(%)=LT(九

) が得 られ る. ・ 定理 3.19よ り,極小 グ レブナー基底の元 の個数 は一定である. 定義

3.20(簡

約グ レブナー基底

)イ

デアル

Iの

グレブナー基底 σ が次の

2条

件をみ たす とき

,Iの

簡約 グレブナー基底であるとい う.

(1)任

意の

gcCが

,σ

―

_{g}に

関して正規形である.

(2)任

意の θ∈θ に対 して

LC(g)=1で

ある。す なわち,θ の どの元の先頭係数 も

1で

ある. 命題

3.21簡

約 グ レブナー 基底 は極 小 グ レブナー基底 で あ る.

【

証明】

θ

={gl,… "θ

m)を

イデアル Iの 簡約グレブナー基底とする。今

,

づ≠ブ

,か

つ

LT(g`)I LT(ヵ

_)で

あると仮定すると

_,方

はσ―

_{%}に

_{関する正規}

形でないことになり

,矛

盾が生じる

.よ

って

,づ

≠ブならば

LT(gづ)I LT(島 )と

な

るの で,θ は極 小 グ レブナー基底 であ る

. ￨

グ レブナー基底 か ら次 の手順 で簡約 グ レブナー基底 が得 られ る。特 に,簡 約 グ レブナー基底 の存在 がわか る。

(1)グ

レブナー基底 か ら,補題 3.16の よ うに,余 分 な元 を取 り除 いて,極 小 グ レブナー基 底 θ を求 め る.

(2)極

小 グ レブナ ー基 底 θ={ク1,¨っ

bm}の

元 を次 の よ うに正 規化 す る. (i)ク

1を

G―

{gl)に

よ り正 規 化 して ク1とす る。 この とき

LM(gl)=LM(ク

1)で

あ る.

3.グ

レブナー基底 (ii)以

下

,j=2,3,¨

,mの

順に 動を

{gi,¨_"gれ1,3+1,…

_"gm}に

より正規化して ク

J

とする

.こ

のとき

LM(a)=LM(gr)で

ある。

(ili)θ

*={gI,¨

_"晩

}と

おくと

,ご

は σ

*― {鋪

}に 関して正規形である。なぜなら

ば

,上

の手順からわかるように

,gJの

単項式はLM(鋪

)で

割りきれないからであ

る

(プ

≠り

,

0{詰

_{齢…論 →齢仲クブ}

ナ

ー

基

底

で

あ

. 定理

3.22(簡

約 グ レブナー基底の一意性

)σ

,Fが

イデアル

Iの

簡約 グレブナー基底 であるな らば,集合 として θ tt Fが 成 り立つ.

【

証明】

G,Fを

イデアル 」の簡約グレブナニ基底とする

.定

理

3.19よ

り

,

θ

={gl,¨

・

,gm}, F={A,…

,∫

鳥

},「

(仇)〒 LT(九

)(j=1,2;…

,m)

とお くことがで きる。この とき,θj一 九 ∈」であ り

,多

一九 は θ ―{gじ

}に

関

して正規形 である。また

,LC(g`)=LCu)〒

1よ

り

_,a―

_{ん の各 単項式} Aイ が

M≪

LM(gじ

_)を

みたす ことに注意すれ ば_{,gj― ん は σ に関 して正規形 である}.

ゆえに,補題 3.11よ り,θづ一九

=0と

なるので,動

=ん

を得 る.づ は任意 であっ

たか ら,θ

=Fが

成 り立つ。

￨

4章

ブ ッフバニ ガー アル ゴ リズム

4章

では

_,S多

項式 を定義 し,イ デアルの生成系が グレブナー基底 か どうか を判 定す るブ ジフバーガーの判定条件 を導 く。これ よ り,グレブナー基底 を求 める ブ ッフバーガーアル ゴ リズムが得 られ る。この章 で も多項式はすべて複素数係 数 とし

,T=Щ

″1,…っ″η

)上

に一つの項1贋序が与 え られ ているもの とす る. 4。

l S多

項 式

で あ る.

以下

,2つ

の項 ι

l,オ

2の

最小公倍数である項をレ

1,ι

月と表すことにする

.例

えば

ι

_l=″

14χ2″32,

ι

2=χ

12″23″

3

→

[ιl,ι21=″14″23を32

定義

4・

1(S多

項式

)0で

ない ∫

,g∈ CIπl,…

っ″

れ

]に

対して

■ ムの

=

∫

g

とおき

,∫

,gの

S多

項式という

.

注意 :任意の複素数

′

_{α≠0に 対して}

S(ノ,ク

)=S(∫

,α

g)が

成 り立つ。

・

T=T(″

1,χ2,π3)の

項順序を辞書式順序とする

:

ノ

(πl,″2メ

3)=2■

14″2"32+″1, g(πl,″2,π

3)=″

12″23″

3+″

1″3 の とき, LT(∫_)〒 ″14"2"32, LT(θ

)=″

12″ 23″

3

→ [LT(∫),ET(θ)]=″14"23χ32 32

4.ブ

ッフバーガーアル ゴ リズム 33

である。従つて ∫

,ク

の

S多

項式は

■ ム の

=:留 2AL賜

り

.勧

←

Lt,0=:均

の

2_れ

′ 砲 である。 補題 4。

2θ

={ク_1,…っ

%}は

0で

ない多項本の有限集合_,ノ は

OFな

い多項式で ∫ ￨シ 0 であるとす る.こ の とき

,次

をみたす多項式 ん1,¨ "んπ が存在する.

ノ

=Σ

_Eれ

ク

_・

: LM(れ

3)≦

LM(∫

_{) (れ}

働≠

0の

とき

) 二==1 【証明】 補題 3.9よ り

,0で

ない単項式 塊 と,gづん∈θ (1≦ ん≦イ

)が

存在 して ι

∫

=Σ

凡仇

ん

ん₌₁

と表される

.LM(既

夕

1)は

∫のある単項式と一致するので

LM(lVl仇_1)≦ LM(∫) が成 り立つ

.以

_{下,帰納的に}

LM(Ⅳ

Iクtr)が

∫Σ凡働ん

ん=1 のある単項式 と一致す ることか ら が得 られ る。従 って ι

ノ=Σ

ttaん た=1 を整理 して

∫=Σ ん

じ

多

を=1

と表せば

,れ

ク

づ≠0で あるすべての れク

じに対して

∫ Ｍ Ｌ ≪ 一 ヽ １ ︲ ′ ／ ｇ

凡

日

▼

ん

Ｈ

一 ∫ ／ １ １ ヽ Ｍ Ｌ ≪ 一 ヽ_︱ ′ ″ 多 馬 Ｍ Ｌ LλI(れ

_a)≦

LM(∫₎

4.ブ

ッフバーガーアル ゴ リズム 34 が成 り立つ 。

定理

4。

3イ

デアル 」≠0と

,0で

ない多項式の有限集合 σ

={gl,… "θ

η

l}⊆

Jに つい

て

_,次

の条件は同値である

.

(1)Gは

Iの

グレブナー基底である

.

(2)任

意の ノ∈∬―{0}に 対して

,次

式をみたす多項式 れ

(1≦ j≦

m)が 存在する

.

∫

=Σ

_Eれ

9, LM(ん

じ

仇

)≦ LM(∫

)(れ

仇≠

0の

とさ

) づ=1 ・ 【証明】 まず,(1)を 仮定す る。σ が

Iの

グレブナー基底であ るか ら,任意の ∫∈I―

{0}に

対 して,補題 3.11よ り_,∫ ÷

9が

成 り立つ

.従

つて,補題4.2 よ り,

∫

=Σ

_Eん

じ

ク

を

, LM(ん

`gこ )≦ LM(∫) (んj多

≠

0の

とき

) (★

₎ j==1 をみたす多項式 れ(1≦ づ≦

m)が

存在す る.ゆ えに(2)が成 り立つ. 次に,(2)を仮定す ると,任意の ∫∈f―

{0}に

対 して,上 式(★)をみたす多 項式 れ(1≦ j≦

m)が

存在する.このとき lⅣ I(∫

)=LNI(喜

んjgづ

)

より,ある をに対 して LM(∫ )竪

LM(れ

多) が成 り立つ.これ より

LTし

_{)I LTげ})

をみたす

g二

∈θ が存在するので

,θ

は定義

3.7の

条件をみたす

.ゆ

えに

,Gは

Iの

グ レブ ナ ー 基 底 で あ る。

￨

系

4。

4G={ク

_1,¨

"%}を

0で ない多項式の集合とする

.z,υ

∈σが

S(鶴,υ)≠

0,か

つ

S(Z,υ

_{)=ゴ 0を みたすならば}

_,多

項式 ん

1,…_"ん

れが存在して

,次

が成り立つ

.

SC,0=Σ

L動

,LTの

ぅの ヽ

[LTc),LTω

】 oこ多 ≠

0の

とき) を=1 ■ ■

4.ブ

ッフバーガーアル ゴ リズム 35 【証明】 仮定 よ り,補題 4.2を 適用すれ ば, S(鶴 ,り

=Σ

_{ELgt, LM(れ}

仇)≦ LM(S(し,υ

))(れ

gづ ≠

0の

とき) づ==1 をみたす多項式 ん1,…っれ

mが

存在す る。一方

,S多

項式の定 め方か ら LⅣI(S(包,υ))竪 LT(S(色,υ))メ [LT(%),LT(υ)] が成 り立つので

LT@3)≪

_{[LT(鶴),LT(υ}

_)l

_{れ 仇 ≠}

0の

と き₎ を得 る.

ここで

_,い

くつかの記号を導入する

.た

だし

,G={ク

1,…

っ

%}は

0で

ない多項式の有限集

合 とす る, ●クう,力 ∈

Gの

先 頭 項

LT(a),LTc)の

最 小 公倍 数 で あ る項 を 写′

=[LT(a),LT(ヵ

)] と表す こ とにす る. ・ Cレ1,… "π』 の元 を成 分 とす る

m次

元横 ベ ク トル の なす 空 間 を9レ1,…""』

mと

お く・ OC[″_1,¨ "″

』

れの

2つ

のベクトル α

=(αl,…,α

m)と b=(bl,っ

bれ

)の

内積 α

obを

α

Ob=Σ

_Qbづ づ=1 . と定 め る。

・

Ch,…

_"″

』

m∋

Ct=(0,…,1,…

_"0)を

第 を成分のみが

1,他

の成分が

0の

ベクトルと

して

島

=品

Q鵡

%

=品

_{し■―の一}

_{ん じ■}

_-0.

とお く。、

4.ブ

ッフバーガーアル ゴ リズム 36

補題

4.5G={gl,っ

gれ

_{}は 0で ない多項式の有限集合とする。}

Cレ1,¨ ""』

れのベク

トル

g=(gl,…

_{っgm)に 対して}

_,次

_{が成り立つ}

. Sガ

og〒

S(0,ヵ₎

【

証明】

_{島プの定め方から}

島吋

=(品

Q品

_→く

_{… わ}

=鵡

仇

―

_品

%

=S(動

,ヵ) が成 り立つ 。

補題 4,6G={gl,… っgm)は

0で

ない多項式の有限集合

,″

1,… "′

‰

)は

0で

ない単項

式で_,次の

2条

件 をみたす とす る. ●項 t∈ T(″1,¨っ "れ

)が

存在 して

,t=LT(1の

。LT(仇

_)が

成 り立つ(1≦ づ≦m)″

oΣ

_鷹lz・

LM(g」

)=0

このとき

,単

項式

Arl,¨

プ‰ が存在して

,次

が成り立つ

. (1)(A/fl,…

っ■

ど

鳥

)=Σ

吉

1既

・島

,づ

+1 '

(2)LTCt)・

■

,こ

+1=t Ct≠

0の

とき

) 【証明】 仮定 より

,tは

ET(ク_を)(づ =1,…

_"m)の

公倍数であるか ら

,z計

1は

ι を割 り切 る。ここで

,札

を次のように定める. 札

=

的 卸 刊 A4・

LM(ヵ )は 単項式で

_,そ

の項は ιであるから

_,上

の 馬 の定義式の分子は

単項式で

,そ

の項は ιである。従つて,既 は単項式であり

,既

≠0の ときは