導入
数学では、多項式環のイデアルIのグレブナー基底(または標準基底、またはブッフベルガー基底)
$$ {K[X_1,\dots, X_n]} $$
は、この理想のジェネレーターのセットであり、特定の追加プロパティを検証します。この概念は 1960 年代に広中平介とブルーノ ブッフベルガーによって独自に導入され、博士論文指導教授ヴォルフガング グレブナーにちなんで名付けられました。グレブナー基底には、多項式イデアルの研究を、より理解しやすい単項イデアル (つまり、単項式で構成される) の研究に戻すという大きな利点があります。
興味
K を(可換) フィールドとする。
単一の変数をもつ多項式の場合に少しの間戻ってみましょう。リングK [ X ] はユークリッドであり、 K [ X ]の理想的なI はその主生成器によって自然に表現されます。さらに良いのは、 Euclidのアルゴリズムを使用すると、有限ファミリーの生成器からこれを決定できるため、 Iに対する多項式のメンバーシップをテストしたり、 K [ X ]/ Iの要素の正準表現を計算したりすることができます。
指輪
$$ {K[X_1, \dots, X_n]} $$
一方、 は階乗およびネーター関数ですが、主関数ではありません。具体的には、多項式のユークリッド除算を 1 つの変数に「自然に」拡張することはできません。それにもかかわらず、グレブナー基底を使用すると、理想値を法として計算することができます。
$$ {K[X_1, \dots, X_n]} $$
、特に- 理想かどうかを決める$$ {K[X_1, \dots, X_n]} $$任意の整数 (つまり、幾何学的な観点から、 Kの代数閉包における多様体が空である場合、または与えられた多項式系が少なくとも 1 つの解を許容する場合でも)。
- 多項式がイデアルに属するか、その根号に属するか、つまり多項式関数が多様体でゼロであるかどうかを決定します。
- 商代数の要素の正準表現を見つけ、イデアルを法とする代数計算を実行します。
- 等次元多様体の次元と次数（より一般的には、任意の多様体の最大次元の等次元成分の次元と次数の合計）を決定します。
より一般的には、グレブナー基底を使用すると、段階モジュールの関数とヒルベルト多項式を計算できます。また、2 つの理想の交差点を決定する手段も提供します。
計算
グレブナー基底を計算するアルゴリズムがあります。非常に簡単に説明すると、最初で最もよく知られている Buchberger アルゴリズムは、 Bendixと少し似たように、ベースに多項式を追加して主張3 と矛盾する重要なペアを徐々に排除することによって進められます。また、最小グレブナー基底の計算方法も知っています。
これらのアルゴリズムは最悪の場合には非常に非効率的であり、より有利な場合についてはあまり知られていません。
Dで囲まれた合計次数のn 個の変数を持つ多項式のイデアルの場合、最大で でグレブナー基底を計算する方法がわかります。
$$ {D^{2^{O(n)}}} $$
ベース本体での操作。 エルンスト マイヤーとアルバート マイヤーは、この巨大な上限に到達する可能性があり、したがって最適であることを示しました。すべてのグレブナー基底が考慮される理想が存在します。 $$ {2^{2^{\Omega(n)}}} $$
要素自体、 nの二重指数次数です。ただし、すべてが失われたわけではありません。実際、実験的には、この目的のために構築された例でのみこの制限に達します。有限数の複素解を持つ有理系の場合、 Daniel Lazard は時間D O ( n )で計算が実行可能であることを確立しました。わずかに異なる仮説の下で、 Jean-Charles Faugère はO ( D 4.3 n )の限界を与えます。しかし、一般に、通常の場合のグレブナー基底の計算の複雑さはあまり理解されていません。