グレブナー基底
誕生
1964年に広中平祐、1965年にB. Buchbergerによって独立に発見された。広中標準基底とも呼ばれる。B. Buchbergerは指導教授のW. Groebnerの名前を取って、グレブナー基底と名付けた。
概観
グレブナー基底を使うと、「多項式fは多項式によって
(
は多項式)と多項式和に書けるか？」という問いを、一つのアルゴリズムで回答できる。
解説
上の「一つのアルゴリズム」とは、最高次数の項同士の割り算の繰り返しである。
まず、単純な場合からみてみよう。例えば、、
、
と置き
および
と書けるか考えよう。この場合は、グレブナー基底の概念を持ち出す必要はなく、単に上述のアルゴリズムが答えを与える。まず、fの最高次数の元は
であり、gの最高次数の元は
である。よって、それらの割り算
を使い、
とすれば、
を消せる。実際に
である。ここで余りの多項式-7x-1の最高次数の元は-7xなので、更に
とすれば、
も消える。実際に、
である。ここで、6の最高次数の元は6であり、6からgのどんな多項式倍を引いたとしても、余分なxの多項式倍が出てきてしまうだけで、6自体をgの多項式倍で書けない。よって、
すなわち
より進まず、fはgの多項式倍で書けない。一方で、上述のアルゴリズムを
と
に対して行うと、今度はぴたりと
と書ける。
次に、少し複雑な例をみてみよう。例えば、、
,
と置き、fが
と書けるか考える。この場合は、上述のアルゴリズムをそのまま使ってしまうと正しい回答を得ない。実際に、
と書けるにも関わらず、
及び
はfの最高次数の項
より高い次数の項
及び
を含むので、上述のアルゴリズムは最初からストップする。
しかし、与えられた多項式を対応するグレブナー基底に置き換えると、再び上述のアルゴリズムを生かせる。 まず、数式プログラムのSingularを用いてに対応するグレブナー基底を得よう。
> ring r=0,(x,y),lp;
// **ベースとなる環の定義。ここでは、標数が0で２変数の環で、多項式の次数の計算には、辞書式順序を採用している **
> 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にはfの最高次数の元より小さな次数の元xyを含むので、
という操作により
、すなわち
を得る。
発展
多項式が出てくる問題であれば常に役に立ので、代数幾何を初めとした純粋数学に限らず、工業、生物、統計、等々様々な場面での応用がある。上にあげたSingular以外にも国産のRisa/Asirを初め、多くのプログラムで利用できる。
*リスト：リスト::数学関連
kakuyomu.jp
kakuyomu.jp
kakuyomu.jp
kakuyomu.jp
kakuyomu.jp
togetter.com
ja.wikipedia.org
www004.upp.so-net.ne.jp
twitter.com
