簡約グ レブナー基底

補題 ^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が

成 り立つ。

      ￨

31

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な

_{い多項式で ∫}

￨シ ⁰ であるとす る.こ の とき

,次

^{をみたす多項式 ん}1,¨

"んπ が存在する^.

ノ ^=Σ _Eれ ク ・ ^{:  LM(れ 3)≦}

^LM(∫

^) (れ 働≠

^0の

とき

) 二==1

【証明】

 

補題 3.9よ り

,0で

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

)が

^存在 して

∫ =Σ

ι

凡仇 ん

ん=1

と表される .LM(既 _夕

_1)は

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

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

.以

_{下,帰納的に}

LM(Ⅳ

_Iクtr)が

∫Σ凡働ん

ん=1 のある単項式 と一致す ることか ら

が得 られ る。従 って

ι

ノ=Σ

 _ttaん

た=1 を整理 して

∫=Σ ん じ 多

を=1

と表せば

,れ

ク づ≠0で あるすべての れク じに対して

Ｍ∫

≪Ｌ 一

ヽ １

︲

′

／

凡

ｇ

日 ▼

ドキュメント内 グレブナー基底について (ページ 30-35)