グレブナー基底
簡約化とは、直感的には多変数多項式の除算により、より次数の低い "余り" の多項式を求めていくことである。多項式 g を多項式 f で h に簡約化するとは、g 中の単項式 (monomial) から f 中の次数が最高の単項式で割り切れるものを消すことで、
g → f h {\displaystyle g{\underset {f}{{}\rightarrow {}}}h}
のように表記する。1 変数の多項式であれば、x, x, x, ... のように簡約化での次数の順序は簡単に決めることができるが、多変数の場合は単純に決めることができない。そのため簡約化の際には何らかの順序(項順序)を決める必要がある。グレブナー基底の理論では任意の順序を使うことができるが、一般的には以下のものが用いられる。
辞書式順序 (lex)
次数付き辞書式順序 (grlex)
次数付き逆辞書式順序 (grevlex)
以下では簡約化の例を挙げる。例えば、g = xy + 3xy − 5x, f1 = xy − 2y, f2 = 2y − x とする。xy, 3xy, 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}\,}
グレブナー基底はブッフベルガーアルゴリズム (英: Buchberger's algorithm) と呼ばれるアルゴリズムで計算ができる。これはブッフベルガー (英: Bruno Buchberger) により発見された。グレブナー基底の計算はユークリッドの互除法を多変数多項式に一般化したようなアルゴリズムになっている。大まかには以下のようになる。
この操作は有限回で止まり、得られた G は F に同値なグレブナー基底である。
ここで「S-多項式」は f1 と f2 の先頭項(項順序の最も高い項)を相殺させた式で、以下の例のように計算する。この例は次数付き逆辞書式順序。
f 1 = x y + 2 y , f 2 = 2 y 2 + x 2 {\displaystyle f_{1}=xy+2y,f_{2}=2y^{2}+x^{2}} の場合、先頭項を相殺できるような多項式 y {\displaystyle y} と 1 2 x {\displaystyle {\tfrac {1}{2}}x} をそれぞれに掛け、