グレブナー基底のソースを表示

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

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

== 概要 ==
グレブナー基底の基本的な考え方は、多項式の集合 ''F'' を以下の特性を持つ "性質の良い"（グレブナー基底と呼ばれる）多項式の集合 ''G'' に変換することである<ref>B. Buchberger, [http://www.risc.uni-linz.ac.at/people/buchberg/papers/2001-02-19-A.pdf Groebner Bases: A Short Introduction for Systems Theorists] in ''Proceedings of EUROCAST 2001''</ref>。
*''F'' と ''G'' は "等価"（つまり同じ[[イデアル]]を生成する）

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

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

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

== 定義 ==
=== イデアル ===
''F'' を ''n'' 変数の多項式の集合 {''f''<sub>1</sub>, ''f''<sub>2</sub>, ... , ''f''<sub>''r''</sub>} とするとき、多項式[[イデアル]] &lang;''F''&rang; = &lang;''f''<sub>1</sub>, ''f''<sub>2</sub>, ... , ''f''<sub>''r''</sub>&rang; とは、
: <math>h_1 f_1 + h_2 f_2 + \cdots + h_r f_r</math> 
の形の多項式全体の集合のことである。ここで ''h''<sub>''i''</sub> は任意の多項式を表す。このとき ''F'' をイデアル &lang;''F''&rang; の生成系、あるいは基底と呼ぶ。以下では ''F'' から生成されるイデアルを Ideal(''F'') と表現する。
:<math>f_1 = 0, f_2 = 0, \ldots ,f_r = 0 </math>
の解はイデアルの要素全ての共通零点と一致し、イデアルは多変数の連立代数方程式を一般化したものと考えることができる。例えば連立方程式の[[ガウスの消去法|消去法]]は与えられた方程式 ''F'' のイデアル ''I'' から変数の個数が少ないものを選び出す方法と見ることができる。

=== 簡約化 ===
''簡約化''とは、直感的には多変数[[多項式]]の除算により、より次数の低い "余り" の多項式を求めていくことである。多項式 ''g'' を多項式 ''f'' で ''h'' に簡約化するとは、''g'' 中の[[単項式]] {{lang|en|(monomial)}} から ''f'' 中の次数が最高の単項式で割り切れるものを消すことで、
:<math>g \underset{f}{{}\rightarrow{}} h</math>

のように表記する。1 変数の多項式であれば、''x''<sup>5</sup>, ''x''<sup>4</sup>, ''x''<sup>3</sup>, ... のように簡約化での次数の順序は簡単に決めることができるが、多変数の場合は単純に決めることができない。そのため簡約化の際には何らかの順序（[[単項式順序|項順序]]）を決める必要がある。グレブナー基底の理論では任意の順序を使うことができるが、一般的には以下のものが用いられる。
*[[辞書式順序]] (lex)
*次数付き辞書式順序 (grlex)
*次数付き逆辞書式順序 (grevlex)

以下では簡約化の例を挙げる。例えば、''g'' = ''x''<sup>2</sup>''y''<sup>3</sup> + 3''xy''<sup>2</sup> − 5''x'', ''f''<sub>1</sub> = ''xy'' − 2''y'', ''f''<sub>2</sub> = 2''y''<sup>2</sup> &minus; ''x''<sup>2</sup> とする。''x''<sup>2</sup>''y''<sup>3</sup>, 3''xy''<sup>2</sup>, 5''x'' などが単項式である。''g'' を ''F'' = {''f''<sub>1</sub>, ''f''<sub>2</sub>} で簡約化する場合を考える。

このとき ''g'' を ''f''<sub>1</sub> で簡約化した <math style="vertical-align: -60%">g \underset{f_1}{{}\to{}} h_1</math> は、
:<math>h_1 = g - (x y^2)f_1 =  -5 x + 3 x y^2 + 2 x y^3 \,</math>
となる。また、''f''<sub>2</sub> で簡約化した <math style="vertical-align: -60%">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'' に簡約化されることを<div style="margin: 1ex auto 1ex 2em;"><math>g \underset{F}{{}\to{}} h</math></div>で表す。
*''g'' が ''F'' のある要素 ''f'' による簡約化の有限のステップで ''h'' に簡約化されることを<div style="margin: 1ex auto 1ex 2em;"><math>g \overset{*}\underset{F}{{}\to{}}h</math></div>で表す。またこのようにして得られる ''h'' のことを<div style="margin: 1ex auto 1ex 2em;"><math>\underline{h\!}\,_F</math></div>とも書く。
また、''g'' が ''F'' のどの要素でも簡約化できない時、''g'' は ''F'' に関する'''正規形''' {{lang|en|(''normal form'')}} であるといい、簡約によって正規形を得ることを正規化という。

=== グレブナー基底 ===
グレブナー基底の定義は分野により様々な形で表現されるが、例えば以下のように表現できる。
:''F'' がグレブナー基底であるとは、''F'' による正規化が一意、つまり、任意の ''g'' について、<div style="margin: 1ex auto 1ex 2em;"><math>g \overset{*}\underset{F}{{}\to{}} \underline{h\!}\,_F \quad\text{and}\quad g \overset{*}\underset{F}{{}\to{}} \underline{k\!}\,_F</math></div>ならば必ず ''h'' = ''k'' が成立することをいう。

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

グレブナー基底には以下の性質がある。
*''F'' がグレブナー基底ならば<div style="margin: 1ex auto 1ex 2em"><math>f \in \text{Ideal}(F) \iff f \overset{*}\underset{F}{{}\to{}} 0.</math></div> 
* ''F'' を ''n''-変数[[多項式環]] ''K''[''x''<sub>1</sub>, ..., ''x''<sub>''n''</sub>] の部分集合、''i'' &le; ''n'' とするとき、<div style="margin: 1ex auto 1ex 2em"><math>\text{Ideal}(F) \cap K[x_1, \dots, x_i] = \text{Ideal}(F \cap K[x_1, \dots, x_i]).</math></div>

== ブッフベルガーアルゴリズム ==
グレブナー基底は'''ブッフベルガーアルゴリズム''' ({{lang-en-short|[[:w:Buchberger's algorithm|Buchberger's algorithm]]}}) と呼ばれるアルゴリズムで計算ができる。これはブッフベルガー ({{lang-en-short|[[:w:Bruno Buchberger|Bruno Buchberger]]}}) により発見された。グレブナー基底の計算は[[ユークリッドの互除法]]を多変数多項式に一般化したようなアルゴリズムになっている。大まかには以下のようになる{{sfn|Cox et al.|2007|p=90}}。

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

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

ここで「S-多項式」は ''f''<sub>1</sub> と ''f''<sub>2</sub> の先頭項（項順序の最も高い項）を相殺させた式で、以下の例のように計算する。この例は[[単項式順序|次数付き逆辞書式順序]]。
:<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''<sub>1</sub>, ''f''<sub>2</sub> 共通の簡約化と見ることができる。この場合の ''f''<sub>1</sub>, ''f''<sub>2</sub> は[[クヌース・ベンディックス完備化アルゴリズム]]での[[クヌース・ベンディックス完備化アルゴリズム#危険対|危険対]] {{lang|en|(critical pair)}} に相当し<ref>
Anne Heyworth, [http://www.cs.le.ac.uk/people/ah83/grobner/ Gröbner Basis Theory] Leicester University, 2001.</ref>、本来は別々の簡約化の流れをS-多項式で合流させていくことで、簡約化の順序によらず結果が一致するという[[合流性]] {{lang|en|(confluence)}} を保証しているととらえられる。

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

== 計算例 ==
次の連立方程式を解くことを考える。
[[Image:Sistemacomcincosoluções.png|right|thumb|300px|連立方程式 ''x''<sup>3</sup> &minus; 3''x''<sup>2</sup> &minus; ''y'' + 1 = 0, &minus;''x''<sup>2</sup> + ''y''<sup>2</sup> &minus; 1 = 0 の解]]
:<math>\begin{cases}
 x^3 - 3x^2 - y + 1 = 0 \\
 -x^2 + y^2 - 1 = 0
\end{cases}</math>
たとえば[[数式処理システム]][[GAP (数式処理システム)|GAP]]では有理数体上の 2 変数多項式環 '''Q'''[''x'', ''y''] におけるイデアル &lang;''x''<sup>3</sup> &minus; 3''x''<sup>2</sup> &minus; ''y'' + 1, &minus;''x''<sup>2</sup> + ''y''<sup>2</sup> &minus; 1&rang; の被約グレブナー基底は次のように計算される<ref>[http://aleph.sagemath.org/?z=eJxtTkEKwjAQvAv9w9JTatND7c3gRYQiKFKvYiGaRRbSRJIKye9t4tW9LDszOzMDbHdwlTNZI7UXApYpViGhR6NwRjeRkTOygUMZykqIYhX_s_HHkkKpk-IWxg4a6NZh3Cw7Qg0thyZdNcSMtff0oTHnna2xE0l9wnBxCh2ZFwscYnbtc09Unyeq3ll8GHR76cmznMdhMcnCA_m3lpH1lfgCydg_ww==&lang=gap 実際の計算]</ref>。
<pre>
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 ]
</pre>
この計算により解の ''y'' 座標の値は ''x'' に依らない代数方程式 ''y''<sup>5</sup> + ''y''<sup>4</sup> &minus; 11''y''<sup>3</sup> &minus; 17''y''<sup>2</sup> + 9''y'' + 17 = 0 の根として計算できる。
''x'' 座標の値は残りの方程式に得られた ''y'' 座標の値を代入すれば得られる。

== 出典 ==
{{reflist}}

== 参考文献 ==
* William W. Adams and Philippe Loustaunau (1994): ''An Introduction to Gröbner Bases'', American Mathematical Society(GSM 3), ISBN 978-1-4704-6981-8.
* {{cite book
|last1      = Cox
|first1     = David
|last2      = Little
|first2     = John
|last3      = O'Shea
|first3     = Donal
|year       = 2007
|title      = Ideals, varieties, and algorithms : an introduction to computational algebraic geometry and commutative algebra
|edition    = Thrid
|series     = Undergraduate texts in mathematics
|url        = {{google books|yCsDO425PC0C|Ideals, varieties, and algorithms : an introduction to computational algebraic geometry and commutative algebra|plainurl=yes}}
|publisher  = Springer
|isbn       = 978-0-387-35650-1
|ref        = {{sfnref|Cox et al.|2007}}
}}
* B. Buchberger (1965). [http://www.ricam.oeaw.ac.at/Groebner-Bases-Bibliography/gbbib_files/publication_706.pdf ''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, [http://www.risc.uni-linz.ac.at/people/buchberg/papers/2001-02-19-A.pdf Groebner Bases: A Short Introduction for Systems Theorists](pdf) in ''Proceedings of EUROCAST 2001''.
* 平林 隆一, 工学基礎 代数系とその応用. 数理工学社, 2006. ISBN 978-4-90168340-1
* Thomas Becker and Volker Weispfenning (1993) : ''Gröbner Bases: A Computational Approach to Commutative Algebra'', Springer(GTM141), ISBN  978-1-4612-0913-3.
* Ralf Fröberg (1997): ''An Introduction to Gröbner Bases'',　John Wiley, ISBN 0-47197442-0.
* Winfried Bruns and Jüren Herzog (1998): ''Cohen-Macaulay Rings''(2nd Ed.), Cambridge Univ. Press, ISBN 978-0-51160868-1.
* Viviane Ene and Jürgen Herzog（2012）: ''Gröbner Bases in Commutative Algebra'', AMS (GSM 130), ISBN 978-0-8218-7287-1.

和書：
* 日比孝之：「可換代数と組合せ論」、シュプリンガー・フェアラーク東京、ISBN 978-4-431-70664-9 (1995年4月14日).
* D.コックス、J.リトル、D.オシー：「グレブナー基底と代数多様体入門 (上)」、シュプリンガー・フェアラーク東京、ISBN 978-4-431-70823-0 (2000年4月1日).
* D.コックス、J.リトル、D.オシー：「グレブナー基底と代数多様体入門 (下)」、シュプリンガー・フェアラーク東京、ISBN 978-4-431-70824-7 (2000年4月1日).
* D.コックス、J.リトル、D.オシー：「グレブナー基底1：代数幾何と可換代数におけるグレブナー基底の有効性」、シュプリンガー・フェアラーク東京、ISBN 4-431-70850-2 (2000年10月11日).
* D.コックス、J.リトル、D.オシー：「グレブナー基底2：代数幾何と可換代数におけるグレブナー基底の有効性」、シュプリンガー・フェアラーク東京、ISBN 4-431-70868-5 (2000年10月11日).
* 丸山正樹：「グレブナー基底とその応用」、共立出版、ISBN 4-320-01693-9 (2002年10月15日).
* 日比孝之：「グレブナー基底」、朝倉書店、ISBN 4-254-11558-X (2003年6月15日).
* 齋藤友克、竹島卓、平野照比古：「グレブナー基底の計算：実践編」、東京大学出版会、ISBN 4-13-061405-3 (2003年6月17日).
* 野呂正行、横山和弘：「グレブナー基底の計算：基礎編」、東京大学出版会、ISBN 4-13-061404-5 (2003年6月18日).
* 日比孝之(編)：「グレブナー基底の現在」、数学書房、ISBN 4-8269-3105-0 (2006年7月1日).
* D.G.Northcott(著)、新妻弘(訳)：「Northcott イデアル論入門」、共立出版、ISBN 978-4-320-01833-4 (2007年3月15日).
* 成田正雄：「復刊 イデアル論入門」、共立出版、ISBN 978-4-320-01891-4 (2009年7月10日).※ 初版1970年4月1日。
* JST CREST 日比チーム(編)：「グレブナー道場」、共立出版、ISBN 978-4-320-01976-8 (2011年9月20日).

== 関連項目 ==
{{div col|cols=2}}
*[[数式処理システム]]
*[[多項式]]
*[[代数方程式]]
*[[ネーター環]]
*[[イデアル]]
*[[単項式順序]]
*[[クヌース・ベンディックス完備化アルゴリズム]]
{{div col end}}

== 外部リンク ==
*[http://www.cs.le.ac.uk/people/ah83/grobner/ Gröbner Basis Theory] Leicester University
*{{MathWorld | urlname=GroebnerBasis | title=Gröbner Basis}}
*[http://math.shinshu-u.ac.jp/~hanaki/dvi/gr.pdf Gröbner基底入門] (pdf) 信州大学講義資料

{{DEFAULTSORT:くれふなあきてい}}
{{Normdaten}}
[[Category:代数幾何学]]
[[Category:環論]]
[[Category:多項式]]
[[Category:形式手法]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]