グレブナ基底

$\prec$ を 前節で考えた順序 $\prec_{lex}$ か $\prec_w$ とする. $f_1, \ldots, f_p$ を $n$ 変数多項式環 $S_n = {\bf Q}[x_1, \ldots, x_n]$ に属する多項式としよう. $S_n$ の部分集合

$$I = \langle f_1, \ldots, f_p \rangle := S_n f_1 + \cdots + S_n f_p$$

を考える. $I$ はイデアルである. 多項式の有限集合

$$G = \{ g_1, \ldots, g_m \}$$

が次の二つの条件を満たすときイデアル $I$ の順序 $\prec$ に関する グレブナ基底であるという.

1. $I = \langle g_1, \ldots, g_m \rangle$ ( $g_1, \ldots, g_m$ が $I$ を生成. )
2. ${\rm in}_\prec(I):= \langle {\rm in}_\prec(f) \,\vert\, f \in I \rangle$ が $\langle {\rm in}_\prec (g_1), \ldots, {\rm in}_\prec(g_m) \rangle$ に等しい.

例として, 1 変数多項式で 順序 $1 < x < x^2 < \cdots$ の場合を考える. $f_1, \ldots, f_s$ の GCD を $h$ とすると, $G = \{ h \}$ はグレブナ基底である. グレブナ基底は余分な元をふくんでいてよくて, たとえば, $G = \{ f_1, \ldots, f_p, h \}$ も $I$ のグレブナ基底となる.

問題(代数学既習者向け): ヒルベルトの基底定理を用いてグレブナ基底の存在を証明せよ.

グレブナ基底の構成をおこなうアルゴリズムが Buchberger アルゴリズムである. まず, S 多項式の計算について簡単に説明する. 二つの多項式 $f$, $g$ に対し, $f$, $g$ の initial term をそれぞれ $c_ft_f$, $c_gt_g$ とするとき, $\{f,g\}$ の S 多項式は

$${\rm Spoly}(f,g) = \frac{{\rm LCM}(t_f,t_g)}{c_ft_f} f-\frac{{\rm LCM}(t_f,t_g)}{c_gt_g} g$$

で定義される. ここで $c_f$ は数, $t_f$ は係数 $1$ のモノミアル, ${\rm LCM}$ の意味は下のプログラムから理解頂きたい.

def spolynomial(F,G)
{
  DF = multi_degree(F);
  DG = multi_degree(G);
  Mx = DF[0]>DG[0]?DF[0]:DG[0];
  My = DF[1]>DG[1]?DF[1]:DG[1];
  Mz = DF[2]>DG[2]?DF[2]:DG[2];
  return x^(Mx-DF[0])*y^(My-DF[1])*z^(Mz-DF[2])*F/DF[3]
        -x^(Mx-DG[0])*y^(My-DG[1])*z^(Mz-DG[2])*G/DG[3];
}

このプログラムで A?B:C なる表現があるが, これは, A が 0 なら C を戻し, A が 0 でないならば, B を戻す.

定理 15.1   $I = \langle G \rangle$ とするとき, $G$ が $I$ のグレブナ基底 であることと, $G$ から作られる S 多項式の reduction に よる剰余がすべて 0 になることとは同値である.

この定理の証明は, 例えば [2, 2章6節 定理 6] にある. これよりただちに次の Buchberger アルゴリズムを得る.

1. $G=F$, $D=\{G から作られるペア全体\}$ とする. (初期化)
2. $D$ が空なら $G$ がグレブナ基底.
3. $D$ から 1 つペア $s$ を取り除き, $s$ の S 多項式を $G$ に よる剰余をを $r$ とする.
4. もし $r$ が 0 でなければ, $r$ と $G$ から作られるペアを $D$ に 追加する. さらに, $r$ を $G$ に追加する. (この時点で $s$ の S 多項式の $G$ による剰余は 0 となる. )
5. 2. に戻る.

問題 15.1   このアルゴリズムは有限時間内に停止することを証明せよ. (ヒント: $G$ の各要素の initial term の生成するイデアルを上のアルゴリズム の 2 で考えよ. 停止しないとすると, イデアルの真の無限増大列が作れる.)

グレブナ基底の応用はいろいろなものがあるが, たとえば グレブナ基底により, ある多項式がイデアルに属するかどうか が割算により判定できる.

定理 15.2 (イデアルメンバシップ)   $G$ をイデアル $I$ のグレブナ基底とするとき, $f \in I$ である ことと, $f$ を $G$ で reduction した剰余が 0 になることは 同値である.

イデアルの元を, そのイデアルの基底で reduction した剰余 もやはり同じイデアルの元になる. これとグレブナ基底の定義 により定理が成り立つことがわかる (この定理の詳しい証明については [2, 2章6節 系2] を参照).

さらに, グレブナ基底の重要な性質として, どのように割算を行なっても結果 が一意的である, ということがある. これも, 上の定理によりすぐにわかる であろう.

3 変数の場合の Buchberger アルゴリズムを実行するプログラムを 書いてみる.

プログラム

def buchberger(F)
{
  N = length(F);
  Pairs = [];
  for ( I = N-1; I >= 0; I-- )
    for ( J = N-1; J > I; J-- )
      Pairs = cons([I,J],Pairs);
  G = F;
  while ( Pairs != [] ) {
    P = car(Pairs);
    Pairs = cdr(Pairs);
    Sp = spolynomial(G[P[0]],G[P[1]]);
    Rem = reduction(Sp,G);
    if ( Rem ) {
      G = append(G,[Rem]);
      for ( I = 0; I < N; I++ )
        Pairs = cons([I,N],Pairs);
      N++;
    }
  }
  return G;
}

    

Buchberger アルゴリズムは, イデアルの基底 G に属する 二つの多項式からつくられる S 多項式に対し, reduction 関数により剰余を計算して, G に追加していく.

実行例

[218] F=[x-y*z,y-z*x, z-x*y];        
[219] G=buchberger(F);
[x-z*y,-z*x+y,-y*x+z,-x^2+y^2,
 -y*x^3+y*x,-x^5+x^3,-x^4+x^2,
 x^3-x,-y*x^2+y]
[220] reduction(x^2+y^2+z^2,G);
3*x^2
[221] reduction(x^2+y^2+z^2,
                reverse(G));
3*x^2

この実行例は, 前節で例に用いたイデアルの グレブナ基底を計算してみたものである. 順序を変えて reduction しても, 今度は同じ結果になって いることに注目してほしい.

上のプログラムは Buchberger アルゴリズムのもっともシンプルな 形である. 残念ながら, このままでは, ごく簡単な例しか計算できない. 次のような点から種々の改良が行なわれており, それらを実装して はじめて実用的に使えるものが得られる.

1. Pairs から 1 つペアを選ぶ方法を指定する.
2. Pairs から, あらかじめ不必要なペアを取り除く.
3. 有理数係数の場合には, 分数が現れないような計算の工夫.

これらについては [3] でくわしく解説されている.

Asir に組み込まれている函数 gr は与えらた多項式と順序に対して, グレブナ基底を戻す. もちろん, 上に挙げたようなさまざまな改良が 実装されている. (OpenXM 版でない Asir では, load("gr"); でまずグレブナ基底用のライブラリをロードしておく必要がある.)

gr(イデアルの生成元, 変数, 順序の指定)

例: gr([x^2+y^2-1, x*y-1],[y,x], 2);

順序は 0 が graded reverse lexicographic order, 1 が graded lexicographic order, 2 が lexicographic order である. 行列を用いた一般の順序の指定も可能だが, それはマニュアルを見よ. 上の例では, $x^2+y^2-1$ と $xy-1$ で生成されるイデアルの $y > x$ なる lexicographic order に関するグレブナ基底 を戻す. 答えは,

$$\{ \underline{-x^4}+x^2-1, \underline{y}+x^3-x \}$$

である.

例題 15.1   (大事)

1. $R = {\bf Q}[x,y]/\langle x^2+y^2-1,xy-1 \rangle$ は, ${\bf Q}$ 上のベクトル空間であることを示し, 基底および次元を求めよ. 順序としては $y > x$ なる lexicographic order を用いよ.
2. ${\bf Z}/3{\bf Z}$ の乗法表のような形式で, $R$ の乗法表を作れ. 自分で作成した割算函数を用いてみよ.

まず, ブレブナ基底の initial term が $-x^4$, $y$ なので, これらで割れないモノミアルで係数 1 のものは,

$$1, x, x^2, x^3$$

である. これらが $R$ の ${\bf Q}$ ベクトル空間としての基底になる. したがって, $R$ の${\bf Q}$ ベクトル空間としての次元は $4$ である. つぎに ここでは, Asir に組み込みの割算函数 p_true_nf を用いて 乗法表を作成してみる.

[713] G = gr([x^2+y^2-1,x*y-1],[y,x],2)$
[714] G;
[-x^4+x^2-1,y+x^3-x]
[715] p_true_nf(x^4,G,[y,x],2);
[-x^2+1,-1]
[716] p_true_nf(x^5,G,[y,x],2);
[-x^3+x,-1]
[717] p_true_nf(x^6,G,[y,x],2);
[-1,1]

以上の出力より, $R$ での次の乗法表を得る.

	$1$	$x$	$x^2$	$x^3$
$1$	$1$	$x$	$x^2$	$x^3$
$x$		$x^2$	$x^3$	$x^2-1$
$x^2$			$x^2-1$	$x^3-x$
$x^3$				$-1$

掛け算は可換なので, 下半分は省略してある.

例 15.1   上で書いた buchberger と, Asir の gr の速度比較をして みよう.

[284] F = [-3*x^3+4*y^2+(-2*z-3)*y+3*z^2,(-8*y-4)*x+(2*z+3)*y,
           -2*x^2-3*x-2*y^2+2*z*y-z^2]$
[285] V = [x,y,z]$
[286] cputime(1)$
2.3e-05sec(1.895e-05sec)
[287] buchberger(F)$
10.38sec + gc : 0.6406sec(11.41sec)
[288] gr(F,V,2)$
0.05449sec(0.05687sec)

この例では gr が圧倒的に高速である. しかし, 入力を ほんの少し変更すると次のようなことが起こる.

[289] F = [-3*x^3+4*y^2+(-2*z-3)*y+3*z^2,(-8*y-4)*x^2+(2*z+3)*y,
           -2*x^2-3*x-2*y^2+2*z*y-z^2]$
8.7e-05sec(7.892e-05sec)
[290] buchberger(F)$
49.02sec + gc : 3.573sec(53.4sec)
[291]  gr(F,V,2)$
163.1sec + gc : 4.694sec(168.2sec)
[292]  hgr(F,V,2)$
0.02296sec(0.02374sec)

これでわかるように, gr に実装されている改良も, あらゆる 入力に対して有効なわけではなく, かえって悪影響を及ぼす場合もある. hgr というのは, gr にある前処理, 後処理を付け加えた もので, おおむね安定だが, やはり遅くなる場合もある. 計算効率の 点では, グレブナ基底計算はまだ発展途上であり, 改良や新しい アルゴリズムも発表され続けている.