コックス, リトル＆オシー「グレブナ基底と代数多様体入門」第2版 第2章§7の演習問題

演習問題1

IのGröbner基底F={f₁, f₂, f₃, f₄, f₅}において、

Iの元をFの部分集合で割った余りが0なら、

系2によりFで割った余りも0だから、例1から

S(f₁,f₂)^F=S(f₁,f₃)^F= S(f₁,f₄)^F= S(f₂,f₃)^F=0は既に示されている。

残りの組合せの割り算は、

S(f₁,f₅)=x⁴/2+2xy³=-(x/2)f₁+f₂-y²f₄-f₅よりS(f₁,f₅)^F=0,

S(f₂,f₄)=-2y²+x=f₅よりS(f₂,f₄)^F=0,

S(f₂,f₅)=x³/2-2y³+xy=f₁/2-3f₄/2-yf₅よりS(f₂,f₅)^F=0,

S(f₃,f₄)=0よりS(f₃,f₄)^F=0,

S(f₃,f₅)=x³/2=f₁/2-f₄/2よりS(f₃,f₅)^F=0,

S(f₄,f₅)=x²/2=-f₃/2よりS(f₃,f₅)^F=0。

演習問題2&3

小問a

lex順序:

Maximaで

-----

load(grobner)$

poly_monomial_order: lex;

f1: x^2*y-1;

f2: x*y^2-x;

G: poly_buchberger([f1,f2],[x,y]);

poly_reduction(G,[x,y]);

-----

によりGröbner基底は{x²y-1, xy²-x,x²-y,y²-1}、

簡約Gröbner基底は{x²-y,y²-1}。

grlex順序:

grlex順序の計算は、上のMaximaのコマンドにおいて、2行目を

poly_monomial_order: grlex;

に変えれば良い。

結果的にlex順序と同じGröbner基底、簡約Gröbner基底を得る。

小問b

lex順序:

Maximaで

-----

load(grobner)$

poly_monomial_order: lex;

f1: x^2+y;

f2: x^4+2*x^2*y+y^2+3;

G: poly_buchberger([f1,f2],[x,y]);

poly_reduction(G,[x,y]);

-----

によりGröbner基底は{y+x², x⁴-2x²y+y²+3,1}、

簡約Gröbner基底は{1}。

これよりI=k[x₁,..., x_n]だからV(I)=∅。

grlex順序:

小問aと同様にして結果的に、

lex順序と同じGröbner基底、簡約Gröbner基底を得る。

小問c

lex順序:

Maximaで

-----

load(grobner)$

poly_monomial_order: lex;

f1: x-z^4;

f2: y-z^5;

G: poly_buchberger([f1,f2],[x,y,z]);

poly_reduction(G,[x,y,z]);

-----

によりGröbner基底は{x-z⁴, y-z⁵}で簡約Gröbner基底も同じ。

演習問題4

定理2のアルゴリズムの擬似コードで、最後のUNTIL G=G'をなくして、

REPEATのループがi回回った時のGをG_iとする。

定理2の証明で(1)を導いたのと同様の議論により、i<jならG_i⊂G_jである。

L=⋃_0≤i<∞ G_iとする。<LT(L)>は単項式イデアルなので、

あるA⊂ℤⁿ_≥0が存在して<LT(L)>={x^α: α∈A}。

さらに§4演習問題7によりある有限集合{α(1),...,α(s)}⊂Aが存在して、

任意のα∈Aに対しα=α(k)+γとなるkとγ∈ℤⁿ_≥0が存在する。

G_i⊂LなのでLT(G_i)⊂LT(L)だから、あるA_i⊂Aが存在して<LT(G_i)>={x^α: α∈A_i}。

またi<jとしてG_i⊂G_jよりLT(G_i)⊂LT(G_j)⊂LT(L)。

もしLT(G_i)⊊LT(G_j)なら、あるδ∈A_jが存在してx^δ∉<LT(G_i)>かつx^δ∈LT(G_j)。

x^δ∈LT(L)でもあるから、δ=α(k)+γとなるkとγ∈ℤⁿ_≥0は存在するので、

もしα(k)∈A_iならx^α(k)|x^δだから、§4補題2によりx^δ∈LT(G_i)となり矛盾。

故にα(k)∉A_i。同様に§4補題2によりα(k)∈A_j。

従って、LT(G_i)⊂LT(G_j)が真の増加列なら、

{α(1),...,α(s)}のある元がLT(G_i)に追加されるが、

{α(1),...,α(s)}は有限集合だからこの追加は有限回で終了するので、

あるN≥1が存在して、j≥0ならLT(G_N)=LT(G_N+j)=LT(L)となる。

すなわち定理2の証明での議論と同様にG_N=G_N+1となるから、

定理2のアルゴリズムの擬似コードで、最後のUNTIL G=G'があると、

アルゴリズムは高々N+1回のステップで終了する。

なんかまどろっこしい・・・。

演習問題5

仮定により定義4の(i)は常に満たされている。

IのGröbner基底Gが極小Gröbner基底なら、定義4(ii)により、

g∈Gに対しLT(g)∉<LT(G-{g})>で、LT(g)∈<LT(I)>なのだから、

<LT(G-{g})>⊊<LT(I)>となるから、G-{g}はIのGröbner基底でない。

g∈Gは任意だから、Gのどんな真部分集合もIのGröbner基底でない。

逆にIのGröbner基底Gのどんな真部分集合も、

IのGröbner基底でないとすると、

任意のg∈Gについて<LT(G-{g})>⊊<LT(I)>。

LT(g)∈<LT(G-{g})>と仮定すると、

補題3によりG-{g}がIのGröbner基底となり仮定に反する。

したがってLT(g)∉<LT(G-{g})>だから定義4(ii)によりGはIの極小Gröbner基底。

演習問題6

GはIのGröbner基底なので<LT(I)>=<LT(G)>。

ここで定義4の(i)は常に満たされているとして一般性を失わないから、

IのGröbner基底Gが極小Gröbner基底であることと、

g∈Gに対しLT(g)∉<LT(G-{g})>は同値。

さらに<LT(G-{g})>は単項式イデアルなので、

§4補題2により<LT(G-{g})>のどの元もLT(g)を割らないことと同値だから、

<LT(I)>=<LT(G)>より<LT(G)>が<LT(I)>の極小基底であることと同値。

演習問題7

小問a

HTMLの制限により\tilde(G)をGで表す。

G,GはともにIのGröbner基底だから<LT(G)>=<LT(G)>=<LT(I)>。

LT(G)≠LT(G)と仮定すると、

LT(G)⊊LT(G)なら、Gの真部分集合がIのGröbner基底Gになるので、

演習問題5と矛盾。LT(G)⊋LT(G)でも同様に矛盾。よってLT(G)=LT(G)。

小問b

LT(G)=LT(G)により明らか。

演習問題8

Input: G=(g₁,...,g_s)

Output: reduced Groebner basis G_red

G_min:=G

FOR each pair (p,q) in G

              if p∈G_min and q∈G_min

                            if LM(p)|LM(q) G_min:=G_min-{q}

if LM(q)|LM(p) G_min:=G_min-{p}

G_red:=G_min

FOR each p in G_min

              p':=p^{G_min -{p}}

              if p'≠p THEN G_red:=(G_red-{p})⋃{p'}

命題6の証明から、一度p∈G_redがFORループ内でp':=p^G-{p}と簡約されれば、

その後元が入れ替わる各ステップのG_redにおいても

常にp'は簡約された元なので、p^G-{p}は一度計算するだけで良い。

演習問題9

小問a

f₁=3x-6y-2z, f₂=2x-4y+4w, f₃=x-2y-z-wとして、

lex順序x>y>z>wにおけるBuchbergerアルゴリズムを用いる。

すなわちMaximaで

-----

load(grobner)$

poly_monomial_order: lex;

f1:3*x-6*y-2*z;

f2: 2*x-4*y+4*w;

f3: x-2*y-z-w;

G:poly_buchberger([f1,f2,f3],[x,y,z,w]);

-----

により、f₄=z+3wとしてIのGröbner基底は{f₁,f₂,f₃,f₄}。

これより極小Gröbner基底は、先頭係数が1で、

先頭項が互いに他を割らない組として例えば{f₃,f₄}を得るから、

(3)の行列表示を得る。

小問b

命題6の方法に従って簡約Gröbner基底は{x-2y+2w,f₄}となり、

(4)の行列表示を得る。

Maximaでは小問aのあとに

-----

R:poly_reduction(G,[x,y,z,w]);

-----

とすればよい。

演習問題10

小問a

x=^t(x₁,...,x_m), f=^t(f₁,...,f_n)とすれば、f=Axである。

このとき体k上の行列Aの行変形は、

LM(f_i)=LM(f_i)なるf_i,f_j (i<j)について、

LC(f_i)≠1ならf_iをf_i/ LC(f_i)で置き換えて先頭係数を1にしてから、

S(f_i,f_j)=f_i-f_j/LC(f_j)を作り、

f_jをS(f_i,f_j)で置き換える操作と等価である。

するとf_j=LC(f_j)(f_i-S(f_i,f_j))だから、S(f_i,f_j)≠0なら

I=< f₁,..., f_i,..., f_j-1, f_j, f_j+1,...,f_n>=< f₁,..., f_i,..., f_j-1,S(f_i,f_j), f_j+1,...,f_n>、

またS(f_i,f_j)=0ならI=< f₁,..., f_i,..., f_j-1, f_j, f_j+1,...,f_n>=< f₁,..., f_i,..., f_j-1, f_j+1,...,f_n>なので、

Aの行変形操作によってIは変化しない。

したがって、行変形によって最終的に得られる<g₁,...,g_t>=I。

小問b

§6定理6（BuhbergerのSペア判定条件）の証明は、

(6)式が満たされれば成立するから、

判定条件はS(g_i,g_j)をGで割った余りが0であることというより、

すべてのi≠jなるS(g_i,g_j)を(6)の形に書けること、

すなわちすべてのS(g_i,g_j)∈<g₁,..., g_t>でありさえすればよく、

割り算アルゴリズムにおけるG内のg₁,..., g_tの順序はあまり関係がない。

すべてのi≠jについて、ヒントにあるようにg_i=x_k+a, g_j=x_l+bとおけば、

S(g_i,g_j)=x_la-x_kb=-bg_i+ag_j∈<g₁,..., g_t>だから、

上で示したことにより{g₁,..., g_t}はIのGröbner基底である。

小問c

G={g₁,..., g_t}とする。

Bは簡約された行階段形行列だから、任意のg_i∈Gについて

LT(g_i)=LM(g_i)はi≠jなるどのg_jの項の単項式にもならない。

g_iのある項の単項式が<LT(G-{g_i})>にもし含まれるなら、

あるg_mが存在してLT(g_m)がi≠mなるg_iの項の単項式となって矛盾。

故にg_iのどの項の単項式も<LT(G-{g_i})>に含まれないので、

GはIの簡約Gröbner基底。

演習問題11

d=gcd(f,g)をEuclidのアルゴリズムで得られる、fとgのGCDとする。

またdeg(f)≥deg(g)を仮定し、さらにLC(d)≠1なら、

新たにd/LC(d)をGCDとしてLC(d)=1としても、一般性を失わない。

kは体だからLC(f),LC(g)はk[x]の単数なので、

f=gq+r (deg(r)<deg(g))となるq,r∈k[x]が存在するから、<f,g>=<g,r>。

Euclidのアルゴリズムではこの操作をr=0となるまで繰り返すから、

GCDとしてdを得るので<f,g>=<d>なので、dは<f,g>の生成元。。

k[x]は第1章§5系4によりPIDだから

§5演習問題10により{d}は<f,g>のGröbner基底。

LC(d)=1と、<LT({d}-{d}>=∅よりdのどの項の単項式も<LT({d}-{d}>の元でないから、

定義5により{d}は<f,g>の簡約Gröbner基底。

f=gq+rなるq,r∈k[x]を見つけるための、

通常の1変数多項式の割り算アルゴリズムの各ステップは、

gと、fから始まる中間被除数とのS多項式を求めているので、

Buchbergerアルゴリズムの特別な場合である。

また、rが求まると<f,g>=<f,g,r>=<g,r>によって、

極小Gröbner基底を求めている。