グレブナー基底(グレブナーきてい、英: Grobner basis)は、多変数多項式の簡約化が一意に行える多項式の集合である。多変数の連立代数方程式の解を求める際などに利用される(#計算例参照)。
グレブナー基底を求めるアルゴリズムとしては、ブッフベルガーアルゴリズム(英: Buchberger's algorithm
)があり、数式処理の分野での連立代数方程式の解法として使われている。また、可換環論、代数幾何、微分方程式論、整数計画問題などに出てくる様々な数学的対象物を構成するための基礎となっている。グレブナー基底の基本的な考え方は、多項式の集合 F を以下の特性を持つ "性質の良い"(グレブナー基底と呼ばれる)多項式の集合 G に変換することである[1]。
F と G は "等価"(つまり同じイデアルを生成する)
さらに、グレブナー基底についての理論から以下のことが分かっている。
グレブナー基底の "性質の良さ" のため、F で解くのが難しい多くの問題をグレブナー基底 G で解くことができる。
任意の F を等価なグレブナー基底 G に変換するアルゴリズム(ブッフベルガーアルゴリズム)が存在する。
G での問題の解法は、多くの場合、簡単に F での問題の解法に変換できる。
例えば、数式処理システムで多変数の連立代数方程式を解く場合、直接解くのは多くの場合難しい。その際に与えられた方程式のグレブナー基底を計算しそれらを解くことで、元の連立代数方程式の解を求めることができる。 多項式環上のグレブナー基底の理論はオーストリアの大学院生であったブルーノ・ブッフベルガー
歴史
F を n 変数の多項式の集合 {f1, f2, ... , fr} とするとき、多項式イデアル ⟨F⟩ = ⟨f1, f2, ... , fr⟩ とは、 h 1 f 1 + h 2 f 2 + ⋯ + h r f r {\displaystyle h_{1}f_{1}+h_{2}f_{2}+\cdots +h_{r}f_{r}}
の形の多項式全体の集合のことである。ここで hi は任意の多項式を表す。このとき F をイデアル ⟨F⟩ の生成系、あるいは基底と呼ぶ。以下では F から生成されるイデアルを Ideal(F) と表現する。 f 1 = 0 , f 2 = 0 , … , f r = 0 {\displaystyle f_{1}=0,f_{2}=0,\ldots ,f_{r}=0}
の解はイデアルの要素全ての共通零点と一致し、イデアルは多変数の連立代数方程式を一般化したものと考えることができる。例えば連立方程式の消去法は与えられた方程式 F のイデアル I から変数の個数が少ないものを選び出す方法と見ることができる。 簡約化とは、直感的には多変数多項式の除算により、より次数の低い "余り" の多項式を求めていくことである。多項式 g を多項式 f で h に簡約化するとは、g 中の単項式 (monomial) から f 中の次数が最高の単項式で割り切れるものを消すことで、 g → f h {\displaystyle g{\underset {f}{{}\rightarrow {}}}h} のように表記する。1 変数の多項式であれば、x5, x4, x3, ... のように簡約化での次数の順序は簡単に決めることができるが、多変数の場合は単純に決めることができない。そのため簡約化の際には何らかの順序(項順序)を決める必要がある。グレブナー基底の理論では任意の順序を使うことができるが、一般的には以下のものが用いられる。 以下では簡約化の例を挙げる。例えば、g = x2y3 + 3xy2 ? 5x, f1 = xy ? 2y, f2 = 2y2 − x2 とする。x2y3, 3xy2, 5x などが単項式である。g を F = {f1, f2} で簡約化する場合を考える。 このとき g を f1 で簡約化した g → f 1 h 1 {\displaystyle g{\underset {f_{1}}{{}\to {}}}h_{1}} は、 h 1 = g − ( x y 2 ) f 1 = − 5 x + 3 x y 2 + 2 x y 3 {\displaystyle h_{1}=g-(xy^{2})f_{1}=-5x+3xy^{2}+2xy^{3}\,} となる。また、f2 で簡約化した g → f 2 h 2 {\displaystyle g{\underset {f_{2}}{{}\to {}}}h_{2}} は、 h 2 = g − ( 1 2 x 2 y ) f 2 = − 5 x + x 4 y 2 + 3 x y 2 {\displaystyle h_{2}=g-\left({\frac {1}{2}}x^{2}y\right)f_{2}=-5x+{\frac {x^{4}y}{2}}+3xy^{2}} となる。このように簡約化には複数のやり方がある。簡約化は有限のステップで必ず終わるが、一般に結果は一意に決まらない。 以下に、簡約化についてのいくつかの表記方法をまとめる。
簡約化
辞書式順序 (lex)
次数付き辞書式順序 (grlex)
次数付き逆辞書式順序 (grevlex)
g が F のある要素 f で h に簡約化されることを g → F h {\displaystyle g{\underset {F}{{}\to {}}}h} で表す。
g が F のある要素 f による簡約化の有限のステップで h に簡約化されることを g → F ∗ h {\displaystyle g{\overset {*}{\underset {F}{{}\to {}}}}h} で表す。