グレブナー基底

グレブナー基底（グレブナーきてい、英: Gröbner basis）は、多変数多項式の簡約化が一意に行える多項式の集合である。多変数の連立代数方程式の解を求める際などに利用される（#計算例参照）。

グレブナー基底を求めるアルゴリズムとしては、ブッフベルガーアルゴリズム（英: Buchberger's algorithm）があり、数式処理の分野での連立代数方程式の解法として使われている。また、可換環論、代数幾何、微分方程式論、整数計画問題などに出てくる様々な数学的対象物を構成するための基礎となっている。

概要

グレブナー基底の基本的な考え方は、多項式の集合 F を以下の特性を持つ "性質の良い"（グレブナー基底と呼ばれる）多項式の集合 G に変換することである。

• F と G は "等価"（つまり同じイデアルを生成する）

さらに、グレブナー基底についての理論から以下のことが分かっている。

• グレブナー基底の "性質の良さ" のため、F で解くのが難しい多くの問題をグレブナー基底 G で解くことができる。
• 任意の F を等価なグレブナー基底 G に変換するアルゴリズム（ブッフベルガーアルゴリズム）が存在する。
• G での問題の解法は、多くの場合、簡単に F での問題の解法に変換できる。

例えば、数式処理システムで多変数の連立代数方程式を解く場合、直接解くのは多くの場合難しい。その際に与えられた方程式のグレブナー基底を計算しそれらを解くことで、元の連立代数方程式の解を求めることができる。

歴史

多項式環上のグレブナー基底の理論はオーストリアの大学院生であったブルーノ・ブッフベルガーによって1965年に発表され、その当時のブッフベルガーの指導教授ヴォルフガンク・グレブナーの名前からグレブナー基底と名付けられた。これと独立して1964年に局所環上での同様の理論が広中平祐によって発見され、標準基底（standard basis、あるいはHironaka's standard basis）とも呼ばれる。自由リー代数の枠組みでの同様の理論はA. I. Shirshovによって1962年に発見されたが、ソ連の外には広く知られなかった。

定義

イデアル

F を n 変数の多項式の集合 {f₁, f₂, ... , f_r} とするとき、多項式イデアル 〈F〉 = 〈f₁, f₂, ... , f_r〉 とは、

[math]h_1 f_1 + h_2 f_2 + \cdots + h_r f_r[/math]

の形の多項式全体の集合のことである。ここで h_i は任意の多項式を表す。このとき F をイデアル 〈F〉 の生成系、あるいは基底と呼ぶ。以下では F から生成されるイデアルを Ideal(F) と表現する。

[math]f_1 = 0, f_2 = 0, \ldots ,f_r = 0 [/math]

の解はイデアルの要素全ての共通零点と一致し、イデアルは多変数の連立代数方程式を一般化したものと考えることができる。例えば連立方程式の消去法は与えられた方程式 F のイデアル I から変数の個数が少ないものを選び出す方法と見ることができる。

簡約化

簡約化とは、直感的には多変数多項式の除算により、より次数の低い "余り" の多項式を求めていくことである。多項式 g を多項式 f で h に簡約化するとは、g 中の単項式 (monomial) から f 中の次数が最高の単項式で割り切れるものを消すことで、

[math]g \underset{f}{{}\rightarrow{}} h[/math]

のように表記する。1 変数の多項式であれば、x⁵, x⁴, x³, ... のように簡約化での次数の順序は簡単に決めることができるが、多変数の場合は単純に決めることができない。そのため簡約化の際には何らかの順序（項順序）を決める必要がある。グレブナー基底の理論では任意の順序を使うことができるが、一般的には以下のものが用いられる。

• 辞書式順序 (lex)
• 次数付き辞書式順序 (grlex)
• 次数付き逆辞書式順序 (grevlex)

以下では簡約化の例を挙げる。例えば、g = x²y³ + 3xy² + 5x, f₁ = xy + 2y, f₂ = 2y² − x² とする。x²y³, 3xy², 5x などが単項式である。g を F = {f₁, f₂} で簡約化する場合を考える。

このとき g を f₁ で簡約化した [math]g \underset{f_1}{{}\to{}} h_1[/math] は、

[math]h_1 = g - (x y)f_1 = -5 x + 3 x y^2 + 2 x y^3 \,[/math]

となる。また、f₂ で簡約化した [math]g \underset{f_2}{{}\to{}} h_2[/math] は、

[math]h_2 = g - \left( \frac{1}{2} x^2 y \right)f_2 = -5 x + \frac{x^4 y}{2} + 3 x y^2[/math]

となる。このように簡約化には複数のやり方がある。簡約化は有限のステップで必ず終わるが、一般に結果は一意に決まらない。

以下に、簡約化についてのいくつかの表記方法をまとめる。

• g が F のある要素 f で h に簡約化されることを
  [math]g \underset{F}{{}\to{}} h[/math]
  で表す。
• g が F のある要素 f による簡約化の有限のステップで h に簡約化されることを
  [math]g \overset{*}\underset{F}{{}\to{}}h[/math]
  で表す。またこのようにして得られる h のことを
  [math]\underline{h\!}\,_F[/math]
  とも書く。

また、g が F のどの要素でも簡約化できない時、g は F に関する正規形 (normal form) であるといい、簡約によって正規形を得ることを正規化という。

グレブナー基底

グレブナー基底の定義は分野により様々な形で表現されるが、例えば以下のように表現できる。

F がグレブナー基底であるとは、F による正規化が一意、つまり、任意の g について、

[math]g \overset{*}\underset{F}{{}\to{}} \underline{h\!}\,_F \quad\text{and}\quad g \overset{*}\underset{F}{{}\to{}} \underline{k\!}\,_F[/math]

ならば必ず h = k が成立することをいう。

任意の多項式の集合について、どのような項順序を選んでもグレブナー基底を計算できる。ただし項順序により簡約化の結果が異なるため、項順序が異なる場合のグレブナー基底が一致するとは限らない。

グレブナー基底には以下の性質がある。

• F がグレブナー基底ならば
  [math]f \in \text{Ideal}(F) \iff f \overset{*}\underset{F}{{}\to{}} 0.[/math]
• F を n-変数多項式環 K[x₁, ..., x_n] の部分集合、i ≤ n とするとき、
  [math]\text{Ideal}(F) \cap K[x_1, \dots, x_i] = \text{Ideal}(F \cap K[x_1, \dots, x_i]).[/math]

ブッフベルガーアルゴリズム

グレブナー基底はブッフベルガーアルゴリズム (英: Buchberger's algorithm) と呼ばれるアルゴリズムで計算ができる。これはブッフベルガー (英: Bruno Buchberger) により発見された。グレブナー基底の計算はユークリッドの互除法を多変数多項式に一般化したようなアルゴリズムになっている。大まかには以下のようになる。

[math]G[/math]  ←  [math]F[/math]
任意の多項式の組 [math]f_1, f_2 \in G[/math] について、
   [math]f_1, f_2[/math] のS-多項式 (S-polynomial) を [math]G[/math] で簡約化したものを [math]h[/math] とする。
   h ≠ 0 ならば [math]G \leftarrow G \cup h[/math]として繰り返し
   h ＝ 0 ならば次の組を処理する 

この操作は有限回で止まり、得られた G は F に同値なグレブナー基底である。

ここで「S-多項式」は f₁ と f₂ の先頭項（項順序の最も高い項）を相殺させた式で、以下の例のように計算する。この例は次数付き逆辞書式順序。

[math]f_1 = xy + 2y, f_2 = 2y^2 + x^2[/math] の場合、先頭項を相殺できるような多項式 [math]y[/math] と [math]\tfrac{1}{2} x[/math] をそれぞれに掛け、

[math]\text{S-polynomial}(f_1,f_2) = y f_1 - \frac{1}{2} x f_2 = -\frac{x^3}{2} + 2y^2[/math]

これは、多項式の先頭項について最小公倍数の多項式を求めそれらを引くことで相殺していることになる。直観的には、S-多項式による計算は f₁, f₂ 共通の簡約化と見ることができる。この場合の f₁, f₂ はクヌース・ベンディックス完備化アルゴリズムでの危険対 (critical pair) に相当し、本来は別々の簡約化の流れをS-多項式で合流させていくことで、簡約化の順序によらず結果が一致するという合流性 (confluence) を保証しているととらえられる。

ただし、ブッフベルガーアルゴリズムで求まるグレブナー基底には冗長な要素が含まれており、そのままでは一意にならない。冗長な要素を取り除き、先頭項の係数を 1 になるようにした基底を被約グレブナー基底 (reduced Gröbner basis) と呼ぶ。被約グレブナー基底は項順序が決まれば一意に決まる。

計算例

次の連立方程式を解くことを考える。

ファイル:Sistemacomcincosoluções.png

連立方程式 x³ − 3x² − y + 1 = 0, −x² + y² − 1 = 0 の解

[math]\begin{cases} x^3 - 3x^2 - y + 1 = 0 \\ -x^2 + y^2 - 1 = 0 \end{cases}[/math]

たとえば数式処理システムGAPでは有理数体上の 2 変数多項式環 Q[x, y] におけるイデアル 〈x³ − 3x² − y + 1, −x² + y² − 1〉 の被約グレブナー基底は次のように計算される。

gap> Q := Rationals;;    
gap> x := Indeterminate(Q, "x");;
gap> y := Indeterminate(Q, "y");;
gap> ideal := [x^3 - 3*x^2 - y + 1, -x^2 + y^2 - 1];;
gap> lex := MonomialLexOrdering(x, y);;
gap> G := ReducedGroebnerBasis(ideal, lex);;
gap> Display(G);
[ y^5+y^4-11*y^3-17*y^2+9*y+17, -y^4+x*y+11*y^2-x+3*y-13, x^2-y^2+1 ]

この計算により解の y 座標の値は x に依らない代数方程式 y⁵ + y⁴ − 11y³ − 17y² + 9y + 17 = 0 の根として計算できる。 x 座標の値は残りの方程式に得られた y 座標の値を代入すれば得られる。

参考文献

• (2007) Ideals, varieties, and algorithms : an introduction to computational algebraic geometry and commutative algebra, Thrid, Undergraduate texts in mathematics, Springer. ISBN 978-0-387-35650-1. 
• B. Buchberger, (1965). An Algorithm for Finding the Basis Elements of the Residue Class Ring of a Zero Dimensional Polynomial Ideal.(pdf)(ドイツ語) Ph.D. dissertation, University of Innsbruck. ( 英訳: Michael Abramson, in Journal of Symbolic Computation 41 (2006): 471-511. )
• B. Buchberger, Groebner Bases: A Short Introduction for Systems Theorists(pdf) in Proceedings of EUROCAST 2001.
• 平林 隆一, 工学基礎 代数系とその応用. 数理工学社, 2006. ISBN 978-4901683401

関連項目

• 数式処理システム
• 多項式
• 代数方程式
• ネーター環
• イデアル
• 単項式順序
• クヌース・ベンディックス完備化アルゴリズム

外部リンク

• Gröbner Basis Theory Leicester University
• Weisstein, Eric W. “Gröbner Basis”. MathWorld（英語）.
• Gröbner基底入門 (pdf) 信州大学講義資料