スマートフォン用の表示で見る

グレブナー基底

サイエンス

グレブナー基底

ぐれぶなーきてい

誕生

1964年広中平祐1965年にB. Buchbergerによって独立に発見された。広中標準基底とも呼ばれる。B. Buchbergerは指導教授のW. Groebnerの名前を取って、グレブナー基底と名付けた。


概観

グレブナー基底を使うと、「多項式fは多項式g_{1},...,g_{n}によってf=A_{1} g_{1}+...+A_{n}g_{n}(A_{1},...,A_{n}多項式)と多項式和に書けるか?」という問いを、一つのアルゴリズムで回答できる。

解説

上の「一つのアルゴリズム」とは、最高次数の項同士の割り算の繰り返しである。

まず、単純な場合からみてみよう。例えば、f=6x^2-x-1g=x-1g’=3x+1)と置きf=A gおよびf=A’g’と書けるか考えよう。この場合は、グレブナー基底の概念を持ち出す必要はなく、単に上述のアルゴリズムが答えを与える。まず、fの最高次数の元は6 x^2であり、gの最高次数の元はxである。よって、それらの割り算¥frac{6x^2}{x}=6xを使い、f-6 x gとすれば、6 x^2を消せる。実際にf- 6 xg=(6x^2-x-1)- 6x g=-7x-1である。ここで余りの多項式-7x-1の最高次数の元は-7xなので、更に(f- 6x g)-¥frac{-7x}{x}gとすれば、-7xも消える。実際に、(f-6xg)+7g=-7x-1+7(x+1)=6である。ここで、6の最高次数の元は6であり、6からgのどんな多項式倍を引いたとしても、余分なxの多項式倍が出てきてしまうだけで、6自体をgの多項式倍で書けない。よって、f-6xg+7g=6すなわちf=(6x-7)g+6より進まず、fはgの多項式倍で書けない。一方で、上述のアルゴリズムfg_{1}=(3x+1)に対して行うと、今度はぴたりとf=(2x-1)g_{1}と書ける。

次に、少し複雑な例をみてみよう。例えば、f=xy^{2}g_{1}=x^4-xy, g_{2}=x^3 y- y-1と置き、fがf=A_{1} g_{1}+A_{2}g_{2}と書けるか考える。この場合は、上述のアルゴリズムをそのまま使ってしまうと正しい回答を得ない。実際に、y^{2}(x^{4}-x^{2}y)-xy^{2}(x^3 y-xy-1)=xy^2と書けるにも関わらず、g_{1}及びg_{2}はfの最高次数の項xy^{2}より高い次数の項x^4及びx^{3}yを含むので、上述のアルゴリズムは最初からストップする。

しかし、与えられた多項式を対応するグレブナー基底に置き換えると、再び上述のアルゴリズムを生かせる。 まず、数式プログラムのSingularを用いてg_{1}, g_{2}に対応するグレブナー基底を得よう。

> ring r=0,(x,y),lp;
// **ベースとなる環の定義。ここでは、標数が0で2変数の環で、多項式の次数の計算には、辞書式順序を採用している **
> poly g_1=x^4-x*y;
> poly g_2=(x^3)*y-y-1;
// **多項式の定義 **
> ideal I=g_1,g_2;
// **[tex:g_{1},g_{2}]による多項式和全体をIと置く **
> groebner(I);
// **[tex:g_{1},g_{2}]に対応するグレブナー基底の計算 **
_[1]=y2
_[2]=x2y
_[3]=xy
_[4]=y
_[5]=x2
_[6]=x
_[7]=1

g_{1},g_{2}グレブナー基底G=¥{y^{2},x^{2}y,xy,y,x^2,x,1¥}に置き換えてみると、Gにはfの最高次数の元より小さな次数の元xyを含むので、f-¥frac{x y^{2}}{xy}(xy)という操作によりf-y(xy)=0、すなわちf=y(xy)を得る。

発展

多項式が出てくる問題であれば常に役に立ので、代数幾何を初めとした純粋数学に限らず、工業、生物、統計、等々様々な場面での応用がある。上にあげたSingular以外にも国産のRisa/Asirを初め、多くのプログラムで利用できる。


*リスト:リスト::数学関連