代数幾何ゼミ
石井大海
早稲田大学基幹理工学部
数学科四年2013 年 11 月 27 日

2.3 Gröbner 基底の変換• 零次元イデアル I のある単項式順序に関する Gröbner 基底

G を，他の単項式順序に関する基底 G ′ に変換したい．

⇝ 剰余環 A = k[X]/I の線型代数を使おう！
• Faugère, Gianni, Lazard and Mora による FGLM algorithm• 実用上は lex に関する基底に変換出来れば十分なので，その場合を扱う．
• 最初に grevlex など効率的なので計算しておいて，必要になったら消去などに使う• 入力：零次元イデアル I を生成する Gröbner 基底 G
• lex に関して増加順に k[X ] の単項式を処理していく．
• ステップが進むごとに，最終的な Gröbner 基底の部分集合

Glex ，A の基底 Blex を増やしていく．
• アルゴリズムは三つの段階から成る．

FGLM アルゴリズム I前処理 Glex = Blex = ∅, Xα = 1Main Loop

入力：単項式 XαG2 Xα を計算する．
G3 Xα が Blex の各元の剰余と一次従属か？
1

Case (a) 一次従属の時：
GXα +∑G

cj Xα(j) = 0jとなる線形結合を見付けだし，∑g = Xα +cj Xα(j) ∈ Ijを Glex の末尾に付け加える．単項式は増加順に見ているので，LT(g ) = Xα , LC(g ) = 1．
Case (b) 一次独立の時：Xα を Blex に付け加える．

FGLM アルゴリズム IITermination Check Main Loop で g が Glex に追加されており，LM(g ) が最大の変数の冪なら Glex , Blex を出力し終了する．
Next Monomial lex 順序に関して Xα よりも大きく，どんなgi ∈ Glex に対しても LT(gi ) で割れないような最小の単項式を取り，それを次の入力として Main Loopを実行する．
• このアルゴリズムの正当性は定理 3.4 で示す．
• その前に実際の計算例を見てみよう．

FGLM アルゴリズムの計算例 I
Exercise 3-1
I = ⟨xy + z − xz, x 2 − z, 2x 3 − x 2 yz − 1⟩ ⊆ Q[x, y , z] を考える．
x > y > z なる grevlex についての I の Gröbner 基底を G として，G を z > y > x なる lex Gröbner 基底 Glex に変換したい．
(a) Main Loop を 1, x, . . . , x 6 まで実行せよ．
(b) x 6 の次に y が選ばれることを示し，計算を実行せよ．
(c) y の次に z が選ばれることを示し，計算を実行せよ．
(d) z を処理した後，アルゴリズムは停止する事を示せ．
(e) Glex が求める lex Gröbner 基底であることを示せ．
grevlex に関する基底 G は，432
 f1 = z − 3z − 4yz + 2z − y + 2z − 2 
G = f2 = yz 2 + 2yz − 2z 2 + 1
f3 = y 2 − 2yz + z 2 − z, f4 = x + y − z

FGLM アルゴリズムの計算例 IIで与えられる．よって ⟨LT(I )⟩ = ⟨z 3 , yz 2 , y 2 , x⟩ である．この時，剰余環の基底は B = { 1, y , z, z 2 , z 3 , yz } であり，剰余環の元は全てこの Q-線型結合で書ける．この事を踏まえて，問題を解く．

(a) 計算のため，まず各剰余の係数を求めておく．
1 xx2 x3 x4 x5 x61 11y−1z112z11 −2z311yz−12
これをよく見ると，1, . . . , x 5 は全て一次独立である．よって，Main Loop は Xα = 1, x, . . . , x 5 の間は Blex を増やすのみであり，Termination Check は行われない．x 5 を処理した
後に Next Monomial によって x 6 が選ばれるが，この表より

FGLM アルゴリズムの計算例 IIIGGGGx 6 = x 5 + 2x 3 − 1 となる．よってこの後の Main Loopにより，次の結果が得られる：
Blex = { 1, x, . . . , x 5 }Glex = { x 6 − x 5 − 2x 3 + 1 }(b) x 6 を処理した後，Glex の元がはじめて得られた．この先頭項は x 6 である．よって，x について 6 以上の次数を持つ単項式は処理から弾かれる．よって，x 6 より大きく，次に処理されるべき単項式は y である．すると，先程の表から
Gy G = x 2 − x G となり，一次従属．よって，Blex は変化せず，Glex = { x 6 − x 5 − 2x 3 + 1, y − x 2 + x } .
(c) 前と同様の議論により，次に選ばれる単項式は z となる．この時，表から z = x 2 なので，Glex = { x 6 − x 5 − 2x 3 + 1, y − x 2 + x, z − x 2 } .

FGLM アルゴリズムの計算例 IV(d) すると，LT(z − x 2 ) = z であり，今計算しているのはz > y > x なる lex 順序であったので，g の先頭単項式は最大の変数となった．よって停止する．
(e) ここでそれぞれ求めた順に g1 , g2 , g3 とおくと，S(g1 , g2 ) = −yx 5 − 2yx 3 + y + x 8 − x 7
S(g1 , g3 ) = −zx 5 − 2zx 3 + z + x 8
S(g2 , g3 ) = −zx 2 + zx + yx 2となる．これらを (g1 , g2 , g3 ) で割った剰余はいずれも 0 となるので，Glex は ⟨Glex ⟩ の lex Gröbner 基底である．特に，Iの生成系はいずれも Glex で割り切れ，Glex の元は G で割り切れるので，I の Gröbner 基底となることもわかる．

アルゴリズムの正当性 I
Th. 4
FGLM アルゴリズムは，零次元イデアル I の適当な単項式順序に関するどんな Gröbner 基底 G を入力としても，必ず停止し，lexに関して Glex は I の Gröbner 基底，Blex は剰余環 k[X]/I のベク
トル空間の基底となる．
観察．Blex に追加される単項式は，lex 順序について真に増加する．同様に Glex = { g1 , . . . , gk } の時 LT(g1 ) <lex · · · <lex LT(gk )となる．また，Main Loop で Glex に gk+1 が追加される時，LT(gk+1 ) は Main Loop の入力単項式になっており，その入力はNext Monomial 手続で生成されるので，LT(gk+1 ) は LT(g1 ), . . . , LT(gk ) のいずれでも割れないが各 k について成立していることに注意する．

(0.1)

アルゴリズムの正当性 II停止性．G が零次元イデアルを生成するならアルゴリズムは必ず停止することを示す．そこで，停止しなかったとして矛盾を導こう．すると，Main Loop の Case (a) または (b) の少なくとも一方が無限回発生するので，どちらが無限回かで場合分けする：
abGlex は無限個の単項式 { LT(g1 ), LT(g2 ) . . . } を含む．そこで，J = ⟨LTgi | i < ω⟩ とおけば，Dickson の補題よりある
N > 0 があって J = ⟨LT(g1 ), . . . , LT(gN )⟩ となる．このとき，LT(gN+1 ) ∈ J なので，LT(gN+1 ) は LT(g1 ), . . . , LT(gN )のいずれかで割り切れることになる．しかし，これは (0.1)に反する．よって Glex は有限個で止まる．
これが無限回繰り返されたとすると，Blex は k[X]/I の一次独立な単項式を無限個含むが，これは I が零次元であることに反する．

アルゴリズムの正当性 III
Glex が lex Gröbner 基底であること．Glex = { g1 , . . . , gk } を出力して停止したとする．すると，停止条件より LT(gk ) = x1a1 である（但し x1 > · · · > xn ）．そこで，Glex が lex に関する Gröbner基底になっていないとして矛盾を導こう．Glex は Gröbner 基底でないので，LT(g ) が LT(g1 ), . . . , LT(gk ) のいずれでも割れないよ
うな g ∈ I を取れる．特に，g は Glex について被約（g = g Glex ）であるとして一般性を失わない．特に，そのような g のうちLT(g ) が最小となるものを取ろう．
LT(g ) が lex 順序について x1a1 よりも大きいとすると，LT(gk ) | LT(g ) となってしまうので，LT(g ) < LT(gk ) である．
特に，アルゴリズムが単項式を lex で小さい方から処理していく
ことから，ある i < k があって LT(gi ) < LT(g ) ≤ LT(gi+1 ) となることがわかる．また，g の非先頭単項式はみな LT(g ) よりも真に小さく，g が被約であることからどんな LT(gj ) j ≤ i でも割り切れない．以上のことから，g の非先頭単項式は，LT(g ) が Next
Monomial で検討されるより以前に Blex に追加されていることがアルゴリズムの正当性 IVわかる．よって，g は gi が Glex に追加された次に Glex に追加されることになる．よって LT(g ) = LT(gi+1 ) となるが，これは gの取り方に反する．よって Glex は I の lex に関する Gröbner 基底である．
Blex が A の基底であること（演習問題 4）．Main Loop より
Blex = { Xα(1) , . . . , Xα(ℓ) } は一次独立である．そこで，更に Xαが Blex と一次独立になったとする．このとき，Xα ≤ X α(ℓ) とす
ると，Xα は Blex に含まれていなくてはいけないので，矛盾である．よって Xα > Xα(ℓ) となる．この時，Xα が A の基底であるGことから，Xα lex = Xα であり，基底は Glex のどの先頭多項式でも割れないので，Xα < LT(gk ) = x1a1 である．よって，Xα はNext Monomial でどこかでリストアップされてなくてはならない
ので矛盾．よって Blex は A の基底である．

関連事項• FGLM アルゴリズムは零次元イデアルに関するアルゴリズム• しかし，Gröbner 基底の元の次数の上界が与えられていれば，正次元のイデアルにも適用出来る．
• これと関連した，斉次イデアルに対する「Hilbert 函数駆動」アルゴリズムもある?

次数の上界がわからない一般のイデアルを変換出来ないか？
⇝ Gröbner Walk（第八章）

FGLM アルゴリズムの一般化 I• FGLM アルゴリズムは異なる文脈にも応用出来る• FGLM アルゴリズムで元の Gröbner 基底 G を使うのは f に対し標準形 fGを求めるときのみ• そこで今までの議論を線型写像を用いて言い換えてみるG• B : G に関する A = k[X]/I の基底, L(f ) = f , V = span(B)とおく．これにより，写像

L : k[X] → Vが得られ，これは ker L = I となるような線型写像である．
これを用いれば，Main Loop は次のように言い換えられる：FGLM アルゴリズムの一般化 II
Main Loop・改

入力：単項式 Xα2 L(Xα ) を計算する．
3 L(Xα ) が Blex の L による像と一次従属か？
1

Case (a) 一次従属の時：
L(Xα ) +∑cj L(Xα(j) ) = 0jとなる線形結合を見付けだす．すると，
I = ker L より
∑cj Xα(j) ∈ I
g = Xα +jである．この g を Glex の末尾に付け加える．
Case (b) 一次独立の時：Xα を Blex に付け加える．

FGLM アルゴリズムの一般化 III⋆ この手続を Termination Check，Next Monomial と組合せれば，今までと同じことが出来る• 更に，L を像が有限次元となるような任意の線型写像とすれば，L の核の Glex が求まる！
• 次回：その応用例