グレブナ基底とは？わかりやすく解説

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

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

概要

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

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

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

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

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

歴史

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