2.1.3 連立代数方程式

一松 [16] 第3章 6節「連立代数方程式」の写経。

計算機代数の話題はまだ数多くあるが、近年有名になった「グレブナー基底」に ついて略説する。

多変数多項式に関する連立代数方程式を解く問題は良く現れるが、 一般的な解法はほとんどない。理論上ではつぎつぎに消去法によって 変数を消去してゆけば解けるはずだが、それを正直に実行すると、 たちまち大きな係数を持つ高次方程式が現れて、手におえなくなる。

これまでは与えられた方程式を適当に組み合わせて、因数分解できる形に直す方 法が主力だった。しかしこれを下手に実行すると、考察すべき場合の個数が激増 し、解をうまくまとめるのが厄介いになる。

変数に対称性がある場合には、それを生かしてうまく解ける場合もあった。ただ しそれにこだわるのは得策でなく、対称性を無視して消去法を使うほうがよいこ とも多い。

この問題は、一般化すると、多項式イデアルに関する所属判定問題になる。 イデアルとは、歴史的な由来のある述語だが、いくつかの基底要素 $p_1$, $\cdots$, $p_m$ に多項式 $u_1$, $\cdots$, $u_m$ をかけて加えて表わされる

$$I = \{u_1p_1+\cdots+u_mp_m\}$$

という形の多項式の族と考えてよい。

一変数の場合には、このようなイデアルが、$p_1$, $\cdots$, $p_m$ の 最大公因子 $d$ の倍式全体として表される (単項イデアル)。この $d$ は 「よい基底」である。

多変数の場合には、単項でないイデアルがふつうであり、 「よい基底」を求めることが重要である。

連立代数方程式 $p_1=0$, $\cdots$, $p_m=0$ を解くには、 原理的には $p_1$, $\cdots$, $p_m$ の生成するイデアルの 任意の基底の共通零点を求めればよい。 しかし基底が悪いと、この操作が実行困難である。

イデアルに関する所属判定問題とは、 与えられた多項式 $f$ が、 そのイデアル $I$ に含まれるかどうかを判定する算法を問う問題である。 その応用例は後述する。

もし具体的に $u_1$, $\cdots$, $u_m$ を求めて

$$f=u_1p_1+\cdots+u_mp_m$$

と書くことができれば $f$ は $I$ に含まれる、他方もし変数 $x_1$, $\cdots$, $x_n$ にたいして適当な値 $a_1$, $\cdots$, $a_n$ で

$$p_1(a_1,\cdots,a_n)=0,\cdots,p_m(a_1,\cdots,a_n)=0,f(a_1,\cdots,a_n)\ne 0$$

である組がみつかれば、$f$ はイデアル $I$ には含まれない。

その昔、何日も所属問題がうまく解けずに苦しみ、試しに数値を代入したら、 前期のような組がみつかり、$f$ が $I$ に属さないことがわかった、 そして結果的にそれまでの計算はむだだった、という実例がある。 現在でもこのような予備テストは重要である。しかしこのような $a_1$, $\cdots$, $a_n$ の組がみつからない (いつでも $f(a_1,\cdots, a_n)=0$ とな る) とき、$f$ が $I$ に含まれそうだと予想されても証明にはならない。

この判定には $I$ の基底自体が重要である。じっさいに基底のとり方が 悪いと、奇妙な現象が起こる。

例えば変数の個数を $3$ とし、$x_1$, $x_2$, $x_3$ を $x$, $y$, $z$ と書く ことにして、次の基底を考える。

$$p_1=x^3yz-xz^2,\quad p_2=xy^2z-xyz,\quad p_3=x^2y^2-z^2$$

これにたいして $f=x^2yz-z^3$ の所属問題を考えてみよう。

原則として最も高い次数の項を合わせて消去する。 しかし $f$ の主項 $x^2yz$ は、$p_1$, $p_2$, $p_3$ のどれを 使っても、そのままでは簡約できない。この $f$ は $^xp_2+zp_3$ と 表現できるので、イデアルに属する。このことは $x^2y^2z$ という おなじ項を加減して変形すればわかるが、これを機械的に求めることはできない。

この例は $f$ が悪いというよりも、イデアルの基底が不足しているのである。 これにさらに新しい基底を補充して、基底 (base) を固める必要がある。

多項式イデアルの基底を補充して、標準的な基底を整備する理論は、 かなり昔から考えられていた。たとえば広中平祐氏が、 フィールズ賞の対象となった 「特異点の還元」の研究中に、 その種の「標準基底」を扱っている。 したがって、これを「広中基底」とよぶべきかもしれない。

しかしその具体的な構成算法を示したのはブーフバーガーであり、 彼は恩師の名をとって、それをグレブナー基底とよんだ。 今日その名で広く使われているので、以下でもそうよんで論じることにする。

それはある意味では、連立一次方程式を解くガウスの消去法の一般化である。 対称式については基本対称式が 「グレブナー基底」に相当する。一般のグレブナー基底は、 これらの概念の一般化に相当する。