余りが割る順番で変わる……グレブナー基底と Buchberger アルゴリズム

1 変数の多項式なら、割り算の余りは 1 つに決まります。多変数では決まりません。同じ多項式を同じ集合で割っても、割る順番を変えると別の余りが出る。

この不都合を消すために選ぶ生成系がグレブナー基底です^[1]。余りが 1 つに定まり、イデアルに入るかどうかが割り算だけで判定できるようになります。

余りが割る順番で変わる

$G=\{x^2+y^2-1,xy-2\}$ で $f=2x^3-x^{2}y+y^3+3y$ を割ります^[4]。

どちらの元から使うかで結果が変わります。一方の道すじでは $y^3-y$、別の道すじでは $2x+2y^3-2y$ が残る。

余りが $0$ でないからといって、$f$ がイデアルに入らないとは言えません。判定の道具として使えない状態です。

まず順序を決める

多変数では、どの項を先頭と見るかが自明ではありません。$x^2$ と $y^3$ のどちらが大きいか、決めておく必要があります。

単項式順序は、全順序であって掛け算と両立し、$1$ が最小になるもの^[1]。代表的なものが 3 つあります。

計算の速さは順序で大きく変わります。次数付き逆辞書式がいちばん軽く、辞書式は重い^[4]。

その代わり辞書式には、変数を消す力があります。目的によって選び分けることになる。

先頭項イデアルで定義する

イデアル $I$ の元すべてについて、先頭項を集めてイデアルを作ります。これを $\mathrm{LT}(I)$ と書く。

生成系 $G=\{g_1,\dots ,g_s\}$ をとったとき、$\mathrm{LT}(g_i)$ たちが $\mathrm{LT}(I)$ を生成するとはかぎりません。ここにずれがあると余りが定まらない。

この条件が満たされると、割り算の余りが一意に決まります^[3]。$f\in I$ と「$G$ で割った余りが $0$」が同値になる。

商環 $k[x_1,\dots ,x_n]/I$ の基底も見えます。$G$ で割り切れない単項式が、そのまま $k$ 上の基底になる。

S 多項式で先頭項を消す

グレブナー基底かどうかを、有限回で確かめる方法があります。2 つずつ組にして、先頭項を打ち消した式を作る。

$$S(f,g)=\frac{\mathrm{lcm}}{\mathrm{LT}(f)}f-\frac{\mathrm{lcm}}{\mathrm{LT}(g)}g$$

$\mathrm{lcm}$ は 2 つの先頭単項式の最小公倍元です。作り方から、先頭項がちょうど相殺されます^[2]。

Buchberger の判定法はこうです。すべての組の S 多項式が $G$ で割って $0$ になるなら、$G$ はグレブナー基底^[2]。

先頭項がそろわない組は、わざわざ調べなくても済みます。2 つの先頭単項式が共通の変数を持たなければ、S 多項式は必ず $0$ に落ちる^[4]。

Buchberger のアルゴリズム

判定法をそのまま手順に直したものが、Buchberger のアルゴリズムです^[2]。1965 年の学位論文で導入され、名前は指導教員だった Gröbner から来ています^[1]。

必ず終わります。生成元を足すたびに先頭項イデアルが真に大きくなり、そういう増加列は Dickson の補題で必ず止まるためです^[2]。

計算量は厳しい。変数の本数に対して二重指数で増える上界が知られています^[4]。最悪の例は珍しく、実際の入力ではもっと軽く済みます。

例：ねじれ 3 次曲線

$I=(x^2-y,x^3-z)$ を辞書式順序 $x>y>z$ で扱います。曲線 $(t,t^2,t^3)$ の定義イデアルです。

$S$ 多項式を作ると $x(x^2-y)-(x^3-z)=-xy+z$。符号を整えて $xy-z$ を足します。

次の組から $y^2-xz$ が出ます。さらに進めると $y^3-z^2$ が現れる。

$$G=\{x^2-y,xy-z,xz-y^2,y^3-z^2\}$$

ここで打ち止めです。残りの組はすべて $0$ に落ちます。もとの生成元 2 個が 4 個に増えました。

簡約すると一意に決まる

グレブナー基底のとり方は 1 通りではありません。余計な元を足しても条件は保たれます。

そこで条件を足します。各元が単項化されていて、ほかの元で割り切れない形にする。これを簡約グレブナー基底と呼びます。

順序を決めれば、簡約グレブナー基底はイデアルごとに一意に決まります^[4]。

一意なので、イデアルが等しいかどうかの判定にも使えます。2 つの簡約グレブナー基底を比べるだけ。

変数を消す

辞書式順序には特別な性質があります。消したい変数を優先度の高いほうに置く。

グレブナー基底 $G$ をとると、$G$ のうち残したい変数だけで書ける元が、消去イデアルのグレブナー基底になります^[1]。

$$G\cap k[y_1,\dots ,y_m]\text{ が }I\cap k[y_1,\dots ,y_m]\text{ の基底}$$

終結式が 1 変数ずつしか消せないのに対し、こちらは一度に整理できます。余分な因子も付きません。

例：媒介変数を消す

曲線が $x=t$、$y=t^2$、$z=t^3$ で与えられているとします。$t$ を消して方程式の形にしたい。

イデアル $(x-t,y-t^2,z-t^3)$ を作り、$t$ を最優先にした辞書式順序でグレブナー基底を求めます。

$t$ を含まない元だけを拾うと、さきほどの 4 本が出てきます。媒介変数表示から陰関数表示へ移れました。

実際の計算では

素朴な Buchberger のアルゴリズムは、そのままでは重すぎます。組の個数が急に増えるためです。

現在の計算機代数システムは F4 や F5 を使います^[4]。S 多項式の簡約を、大きな行列の掃き出しにまとめて処理する方式です。

辞書式が必要なときも、まず軽い順序で求めてから順序を変換します。FGLM やグレブナー walk と呼ばれる手順です。

余りを一意にする。この 1 点のために順序を決め、S 多項式で足りない先頭項を補っていきます。

出典