Initial term の取り出し

この節はイデアルの話題の続きである. 前の節で議論した, GCD を計算するアルゴリズムを 用いると, 1 変数の多項式環の場合, 多項式 $f$ が イデアル $I$ に入っているかどうかを, 計算機を用いて確かめることが可能である. イデアル $I$ が, 多項式 $p$ と $q$ で生成されているとしよう. このとき $h$ を $p$ と $q$ の GCD とすると, $f$ がイデアル $I$ に入っているための必要十分条件は, ${\tt division}(f,h)[1]$ が $0$ を戻すことである. つまり, $f$ が $h$ で割り切れればよい. これは $I = \langle h \rangle$ であることから明らかであろう. まとめると,

1. 入力 $p$, $q$ に対して, 前節の互除法のアルゴリズムによりイデアル の生成元 $h$ を求める.
2. $f \in I$ かどうか判定したい多項式 $f$ の ${\tt division}(f,h)$ を計算して, その第2成分 (割算した余り) が $0$ なら, $f \in I$ と答え, $0$ でないなら $f \not\in I$ と答える.

この判定アルゴリズムをイデアルメンバシップアルゴリズム (ideal membership algorithm) とよぶこともある.

2 変数以上のイデアルは, 単項生成とは限らない. たとえば,

$$I = \langle x^2, xy, y^2 \rangle = {\bf Q}[x,y] x^2 + {\bf Q}[x,y] xy + {\bf Q}[x,y] y^2$$

を考えると $I = \langle h \rangle$ となるような $h$ は存在しない. なぜなら, そのような $h$ があれば, $x^2$, $xy$, $y^2$ を同時に割り切らないといけないが, そのような $h$ は定数のみである. $h$ が定数だと $I$ は ${\bf Q}[x,y]$ に等しくなってしまうが, $\langle x^2, xy, y^2 \rangle$ はたとえば $1$ を含まない (証明せよ). よって $I$ は単項生成でない.

このアルゴリズムは多変数多項式に一般化できる. この一般化されたアルゴリズムの中心部分が Buchberger アルゴリズムである. Buchberger アルゴリズムは, イデアルに入っているかどうかの判定だけでなく, 代数方程式系を解いたり, 環論や代数幾何や多面体や微分方程式論などにでてくる さまざまな数学的対象物を構成するための基礎となっている 重要なアルゴリズムである.

この節では Buchberger アルゴリズム自体の解説は 優れた入門書がたくさんあるので (たとえば [2], [3] など), それらを参照してもらうことにして, Buchberger アルゴリズムの中で重要な役割をはたす割算アルゴリズム (または reduction アルゴリズム) について計算代数システムの内部構造の立場からくわしく考察する. それから Buchberger アルゴリズムと グレブナ基底を簡潔に解説して, イデアルメンバシップアルゴリズムを説明する. 最後にグレブナ基底の別の応用である連立方程式の 求解について簡単にふれる.

イデアルメンバシップアルゴリズムを多変数へ 拡張するには 1 変数の場合と同様にまず initial term を計算する関数を用意しないといけない.

注意すべきは, 2変数以上の場合, さまざまな順序を考えることが可能となることである. 以下 $3$ 変数多項式環 ${\bf Q}[x,y,z]$ で議論する. たとえば $z \succ_{lex} y \succ_{lex} x$ なる辞書式順序 (lexicographic order) は次のように定義する.

$$\begin{eqnarray*} & & P x^a y^b z^c \succ_{lex} P' x^{a'} y^{b'} z^{c'} \\ &\Le... ...ow& \mbox{ $(c-c', b-b', a-a')$\ の最初の $0$\ でない成分が正 } \end{eqnarray*}$$

つまり, まず $z$ の巾で大小を比較して, $z$ の巾が同じなら 次に $y$ の巾で比較し, $y$ の巾も同じなら, $x$ の巾で比較せよという順序である. なおここで $P$, $P'$ は係数であり, 係数は順序の比較に影響しない.

別の順序を考えることも可能である. たとえば, $w=(w_1, w_2, w_3) \in {\bf R}^3$ を $w_i \geq 0$ であるような ベクトルとして,

$$\begin{eqnarray*} & & P x^a y^b z^c \succ_{w} P' x^{a'} y^{b'} z^{c'} \\ &\Left... ...ox{かつ} \ P x^a y^b z^c \succ_{lex} P' x^{a'} y^{b'} z^{c'} ) \end{eqnarray*}$$

と順序 $\succ_w$ を定義する. これを重みベクトル $w$ を辞書式順序で細分して得られた順序という.

あたえられた順序 $\succ$ ($\succ$ は $\succ_{lex}$ か $\succ_w$) と多項式 $f$ に対して, 多項式 $f$ の中の一番大きいモノミアル(単項式)をその多項式の initial term といい ${\rm in}_{\succ}(f)$ と書く.

次の関数 in(F) および in2(F) はそれぞれ, $z > y > x$ および $x > y > z$ なる 辞書式順序 (lexicographic order) で initial term をとりだす関数である.

def in(F) {
   D = deg(F,z);
   F = coef(F,D,z);
   T = z^D;
   D = deg(F,y);
   F = coef(F,D,y);
   T = T*y^D;
   D = deg(F,x);
   F = coef(F,D,x);
   T = T*x^D;
   return [F*T,F,T];
}

        

def in2(F) {
   D = deg(F,x);
   F = coef(F,D,x);
   T = x^D;
   D = deg(F,y);
   F = coef(F,D,y);
   T = T*y^D;
   D = deg(F,z);
   F = coef(F,D,z);
   T = T*z^D;
   return [F*T,F,T];
}

結果はリストで戻しており, リストの先頭要素が多項式 F の initial term, リストの 2 番目の要素が initial term の係数, リストの 3 番目の要素が initial term の係数を除いたモノミアル部である.