極小グレブナ基底・簡約グレブナ基底

定義

6.4 (

極小グレブナ基底

,

簡約グレブナ基底

)

イデアル

I ⊂ k[x

1

, x

2

, · · · , x

n

]

のグレブナ基底

G

が次の条件

(1), (2)

を満たすとき、

G

は 極小グレブナ基底 であるという。

(1)

任意の

p ∈ G

について

LC(p) = 1

。

(2)

任意の

p ∈ G

について

deg(p) 6∈ < deg(G − {p})>

。

この

(2)

の代わりに次の

(3)

を満たすなら

G

は 簡約グレブナ基底 であるという。

(3)

任意の

p ∈ G

について

p

のどの単項式の

deg

も

< deg(G − {p})>

に入らない。

補題

6.5

イデアル

I

のグレブナ基底を

G

とするとき、ある

p ∈ G

に対し

deg(p) ∈ < deg(G − {p})>

だとすれば

G − {p}

も

I

のグレブナ基底である。

[

証明

] deg(I) = < deg(G)> = < deg(G − {p})>

より、グレブナ基底の定義から明らか。

¤

定理

6.6 (

極小グレブナ基底の存在

)

任意のイデアル

I ∈ k[x

1

, x

2

, · · · , x

n

]

について

I

の極小グレブナ基底が存在 する。

[

証明

] p ∈ G

に対して

deg(p)

が

deg(G − {p})

のどれかより

≥

なら、

G := G − {p}

として繰り返せばよい。

¤

例

39

例

38

の極小グレブナ基底を求めよ。すなわち、

R = k[x, y]

で

x > y

の

grlex

で考えて

f

1

= x

³

− 2xy, f

2

=

x

²

y − 2y

²

+ x

とするとき、

I = <f

1

, f

2

>

のグレブナ基底を求めると

f

3

= −x

²

, f

4

= −2xy, f

5

= −2y

²

+ x

とし て、

G = (f

1

, f

2

, f

3

, f

4

, f

5

)

であった。これから極小グレブナ基底を求めよ。

6

ブッフベルガーのアルゴリズム

31 [

解

]

ここで

deg(G) = {(3, 0), (2, 1), (2, 0), (1, 1), (0, 2)}

なので、

deg(f

3

) ≤ deg(f

1

), deg(f

4

) ≤ deg(f

2

)

だから、

G = <f

3

, f

4

, f

5

>

はグレブナ基底として十分であり、係 数を直せば

G = (x

²

, xy, y

²

− 1 2 x)

が極小グレブナ基底である。

注

21 x

²

= 2y · xy − 2x · (y

²

−

¹₂

x)

なので、この極小グレブナ基底は基底として冗長性がある。

定理

6.7 (

簡約グレブナ基底の存在

)

簡約グレブナ基底は次のアルゴリズムで得ることができる。

Input: G = (f_1, f_2, ..., f_s): I

の極小グレブナ基底

Output: G~ = (g_1, g_2, ..., g_s) : I

の簡約グレブナ基底

i := 1

G~ := G

WHILE i <= s DO

f_i’ := f mod(G~ - {f_i}) G~ := G~ - {f_i} + {f_i’}

i := i + 1

[

証明

] G

は極小グレブナ基底なので

deg(f

1

) 6∈ < deg(G − {f

1

})>

。よって、割り算アルゴリズムを考えれば

f

₁⁰

= f

1

G−{f1}

に対して

deg(f

₁⁰

) = deg(f

1

)

。ゆえに、

G ˜ = G − {f

1

} ∪ {f

₁⁰

}

とおくと、

deg( ˜ G) = deg(G) · · · (∗)

と なる。また、

f

₁⁰ のどの単項式の

deg

も

deg(G − {f

1

}) = deg( ˜ G − {f

₁⁰

})

のどれとも

≥

となることはない。

f

₁⁰

∈ I

と

(∗)

より

G ˜

はグレブナ基底であり、極小グレブナ基底でもある。

G

から

G ˜

を作ったように、

G ˜

から

G ˜

⁽²⁾を作り、

以下同様に

G ˜

⁽³⁾

, . . . , G ˜

^(s)を作ると、

deg(G) = deg( ˜ G) = · · · = deg( ˜ G

^(s)

)

となる。また、

f

_i⁰

= f

i

G˜⁽ⁱ⁻¹⁾−{fi}

の任 意の単項式の

deg

は

< deg( ˜ G

⁽ⁱ⁻¹⁾

− {f

i

})> = < deg( ˜ G

^(s)

− {f

_i⁰

})>

に属さないので、

G ˜

^(s)

= <f

₁⁰

, f

₂⁰

, · · · , f

_s⁰

>

は簡約グレブナ基底である。

¤

例

40

例

39

の

G = (x

²

, xy, y

²

−

¹₂

x)

は

I = <G>

の簡約グレブナ基底でもある。しかし例えば

G

⁰

= (x

²

+ xy, xy, y

²

−

¹₂

x)

を取ると、これは

I

の極小グレブナ基底だが簡約ではない。

定理

6.8 (

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

)

簡約グレブナ基底は、単項式順序を固定すれば、各イデアルに対して一意に

決まる。

[

証明

] G, G ˜

を簡約グレブナ基底とする。

• G, G ˜

は極小グレブナ基底である。

• G, G ˜

は極小グレブナ基底であることから

deg(G) = deg( ˜ G)

が言える。

[

証明

] p ∈ G

とすれば、

< deg(G)> =

< deg( ˜ G)>

より、ある

p

⁰

∈ G ˜

が存在して

deg(p

⁰

) ≤ deg(p)

。同様に、ある

p

⁰⁰

∈ G

が存在して

deg(p

⁰⁰

) ≤ deg(p

⁰

) ≤ deg(p)

。もし

p 6= p

⁰⁰なら

p

⁰⁰

∈ G − {p}

なので

deg(p) ∈ < deg(p

⁰⁰

)> ⊂ < deg(G − {p})>

となっ て

G

の極小性と矛盾する。よって

p = p

⁰⁰。従って

deg(p) = deg(p

⁰

) ∈ deg( ˜ G)

。以上より

deg(G) ⊂ deg( ˜ G)

。 同様に逆向きの包含関係も言え、両辺は一致する。

¤

• g ∈ G, ˜ g ∈ G ˜

に対して

deg(g) = deg(˜ g) ⇒ g = ˜ g

。

[

証明

]

式

f

に現れる単項式の集合を

T(f )

と 書くことにする。

g − g ˜ ∈ I

より

g − ˜ g

^G

= 0 · · · (a)

である。一方、

deg(g) = deg(˜ g)

より

T(g − ˜ g) ⊂

T(RT(g)) ∪ T(RT(˜ g)) · · · (b)

。ここで

T(RT(g))

の各元の

deg

は、

≥ deg(g)

とならず、更にまた簡約性よ り

deg(G − {g})

のどれとも

≥

とならないので、

deg(G)

のどれとも

≥

とならない。同様に

T(RT(˜ g))

のど

の元の

deg

も

deg( ˜ G) = deg(G)

のどれとも

≥

とならない。よって

(a)

より

T(g − ˜ g)

の全ての元の

deg

は

deg(G)

のどれとでも

≥

とならない。よって割り算アルゴリズムより、

g − g ˜

^G

= g − ˜ g · · · (c)

である。

(a)

と

(c)

より

g − g ˜ = 0

。

¤

•

以上より

G = ˜ G

が言える。

¤

系

6.9 (

イデアルの同一性判定アルゴリズム

)

２つのイデアルが一致することはそれぞれの簡約グレブナ基底が一致

することと同値である。

33

第 3 章

Groebner _{基底の応用}

§1 計算の実例 1.1 連立１次方程式

次の連立

1

次方程式を考える



 3 −6 −2 0

2 −4 0 4

1 −2 −1 −1







 

 x y z w



 

 = 0. (3.1)

これはイデアル

I = <3x − 6y − 2z, 2x − 4y + 4w, x − 2y − z − w> (3.2)

を考えることと同じ。これのグレブナ基底を定理

6.3

の方法で求める。

グレブナ基底は

(lex

で

)

G = (3x − 6y − 2z, 2x − 4y + 4w, x − 2y − z − w, z + 3w)

である。計算の詳細は以下の通り：

Calculation of Groebner Basis of (lex):

f1 = 3x - 6y - 2z f2 = 2x - 4y + 4w f3 = x - 2y - z - w

---G = (f1, f2, f3)

= (3x - 6y - 2z, 2x - 4y + 4w, x - 2y - z - w) B = {(1, 2), (1, 3), (2, 3)}

Round 1

S(f1, f2) = (1/3) * f1 - (1/2) * f2 = -2/3z - 2w.

(-2/3z - 2w) mod G = -2/3z - 2w.

New Generator: f4 = -2/3z - 2w

---G = (f1, f2, f3, f4)

= (3x - 6y - 2z, 2x - 4y + 4w, x - 2y - z - w, -2/3z - 2w) B = {(1, 3), (2, 3), (1, 4), (2, 4), (3, 4)}

Round 2

S(f1, f3) = (1/3) * f1 - (1) * f3 = 1/3z + w.

(1/3z + w) mod G = 0.

Round 3

S(f2, f3) = (1/2) * f2 - (1) * f3 = z + 3w.

(z + 3w) mod G = 0.

Round 4

S(f1, f4) = (1/3z) * f1 - (-3/2x) * f4 = -3xw - 2yz - 2/3z^2.

(-3xw - 2yz - 2/3z^2) mod G = 0.

Round 5

S(f2, f4) = (1/2z) * f2 - (-3/2x) * f4 = -3xw - 2yz + 2zw.

(-3xw - 2yz + 2zw) mod G = 0.

Round 6

S(f3, f4) = (z) * f3 - (-3/2x) * f4 = -3xw - 2yz - z^2 - zw.

(-3xw - 2yz - z^2 - zw) mod G = 0.

RESULT =================================================================

G = (

f1 = 3x - 6y - 2z, f2 = 2x - 4y + 4w, f3 = x - 2y - z - w, f4 = -2/3z - 2w )

LT(G) = (3x, 2x, x, z)

なので、極小グレブナ基底は

G = (x − 2y − z − w, z + 3w)

x − 2y − z − w

^(z+3w)

= x − 2y + 2w, z + 3w

^{(x−2y−z−w)}

= z + 3w

なので、簡約グレブナ基底は

G = (x − 2y + 2w, z + 3w)

である。

そして、

(1)

極小グレブナ基底を求める

⇐⇒

掃きだし法で次のような階段行列に変形する

:



 1 −2 −1 −1

0 0 1 3

0 0 0 0







 

 x y z w



 

 = 0.

(2)

簡約グレブナ基底を求める

⇐⇒

更に全ての式は他の先頭項による消去がなされている

⇐⇒

掃きだし法で次のような階段行列に変形する

:



 1 −2 0 2

0 0 1 3

0 0 0 0







 

 x y z w



 

 = 0.

ドキュメント内 1 Groebner hara/ (ページ 34-38)