単項イデアルと 1 変数連立代数方程式系の解法

``ユークリッド整域'' では, 整数のときの互除法アルゴリズムが つかえる. 互除法アルゴリズムを用いることにより, 一変数多項式環のイデアルに関する多くの問題を解くことが可能である.

$f, g \in {\bf Q}[x]$ に対して, 一変数の連立代数方程式

$$f(x) = g(x) = 0$$

の共通根をもとめることを考えよう. (複素)共通根の集合を

$$V(f,g) = \{ a \in {\bf C} \,\vert\, f(a) = g(a) = 0 \}$$

と書くことにする. 私達の考えたい問題は, $V(f,g)$ が空かそれとも何個の元からなっているか? 空でないとして, 根の近似値を求めることである.

この問題を見通しよく考えるには, イデアルの考えをもちいるとよい. $I$ を $f$, $g$ の生成するイデアルとしよう. つまり, ${\bf Q}[x]$ の部分集合

$$I = \langle f, g \rangle = \left\{ p(x) f(x) + q (x) g(x) \,\vert\, p, q \in {\bf Q}[x] \right\}$$

を考える. このとき,

$$V(f,g) = V(I) = \{ a \in {\bf C}\,\vert\, h(a) = 0 \ \mbox{\rm for all }\ h \in I \}$$

である.

さて, $I$ は単項生成なので,

$$I = \langle h \rangle$$

となる生成元 $h$ が存在する. $V(I) = V(h)$ であることが容易に分かるので, $h$ が定数なら, $V(I)$ は空集合であり, そうでないときは, 重複度も込みで, $V(I)$ の個数は, $h$ の次数にほかならない. $h$ は $f$, $g$ のGCD にほかならないことが証明できるので, 結局, 互除法アルゴリズムで $h$ を $f$, $g$ より計算して, それから, $h=0$ を数値的にとけば, $V(f,g)$ を決定できることになる.

以上をプログラムすると以下のようになる. 関数 g_c_d(F,G) は多項式 F と G の 最大公約多項式 (GCD) を求める. 関数 division(F,G) は割算定理をみたす, $q$, $r$ を求めている. variety(F,G) で共通根の計算をおこなう.

次の関数達をすべて含めたファイルが gcd.rr である.

def in(F) {
  D = deg(F,x);
  C = coef(F,D,x);
  return(C*x^D);
}

def division(F,G) {
   Q = 0; R = F;
   while ((R != 0) && (deg(R,x) >= deg(G,x))) {
      D = red(in(R)/in(G));
      Q = Q+D;
      R = R-D*G;
   }
   return([Q,R]);
}

def g_c_d(F,G) {
   if (deg(F,x) > deg(G,x)) {
     S = F; T = G;
   }else {
     S = G; T = F;
   }
   while (T != 0) {
     R = division(S,T)[1];
     S = T;
     T = R;
   }
   return(S);
}

def variety1(F,G) {
   R = g_c_d(F,G);
   if (deg(R,x) == 0) {
     print("No solution.(variety is empty.)");
     return([]);
   }else{
     Ans = pari(roots,R);
     print("The number of solutions is ",0); print(size(Ans)[0]);
     print("The variety consists of  : ",0); print(Ans);
     return(Ans);
   }
}
end$

上のプログラムで利用されている組み込み関数について解説を加えておこう.

1. deg(F,x) : 多項式 F の変数 x についての次数をもどす. たとえば, deg(x^2+x*y+1,x) は 2 を戻す.
2. coef(F,D,x) : 多項式 F の変数 x の D 次 の係数を戻す. すなわち, 多項式 F を変数 x の 1 変数多項式とみた とき x^D の係数を戻す. たとえば coef(x^2+x*y+2*x+1,1,x) は y+2 を戻す.

よりくわしくは, help コマンドでマニュアルを参照してほしい.

例. $x^4-1=0$ と $x^6-1=0$ の共通根の集合, $V(x^4-1,x^6-1)$ の計算をしてみよう.

[346] load("gcd.rr");
1
[352] variety1(x+1,x-1);
No solution.(variety is empty.)
[]
[353] variety1(x^4-1,x^6-1);
The number of solutions is 2
The variety consists of  : [ -1.0000000000000000000 1.0000000000000000000 ]
[ -1.0000000000000000000 1.0000000000000000000 ]
[354]

あとの節でみるように, ユークリッドの互除法は数学において基本的のみならず, RSA 暗号系の基礎としても利用されており, 現代社会の基盤技術としても重要である. 蛇足ながら, こんな八方美人な数学の話はそうめったにないのも 注意しておこう.

問題 14.1   3 つの多項式の共通零点を求めるプログラムを書きなさい.

問題 14.2   多項式環における一次不定方程式

$$p(x) f(x) + q(x) g(x) = d(x)$$

の解を一つ求めるアルゴリズムを考え, そのプログラムを書きなさい. ここで, $f$, $g$, $d$ が与えられた一変数多項式で, $p$, $q$ が未知である.

問題 14.3   来週数学のテスト?! プログラミングなんかしてらんない! ちょっとまった. 数学の教科書をみながら, いろんなプログラミングを 考えてみるのはどうでしょう. この節でみたように, たとえばユークリッド環とそのイデアルについて プログラミングをすれば, 対象の理解がぐんとすすみます. 教科書を読んでわからなかったこともわかるようになるかも.

補足: ここでは, いくつかの一変数多項式が与えられたとき, それらが生成す るイデアルの生成元が互除法で求められることを見た. そこで求めた生成元は, イデアルの中で 0 を除く最低次数のものであり, ある多項式がそのイデアル に属するかどうかは, 求めた生成元による割算の結果で判定できる. 多変数の 場合, 一般にイデアルは単項生成にはならないが, 単項式の中にある種の全順 序を入れることで, 剰余が一意的に計算できるような生成系 (グレブナ基底) を考えることができる. グレブナ基底を求めるアルゴリズムとして Buchberger アルゴリズムがあるが, それは互除法の拡張と思ってよい. グレ ブナ基底は多変数多項式の共通零点を求めるだけでなく, 理論的にも重要な役 割を演じる. 詳しくは, 16 章および [1] または [2] を参照.

Risa/Asir でグレブナ基底を計算するコマンドは, gr か hgr である. グレブナ基底の計算は, 互除法の拡張であるので, gr を用いても GCD を計算できる. x の多項式 F と G の GCD は, 集合 $\{ {\tt F}, {\tt G} \}$ のグレブナ基底であるので, コマンド gr([F,G],[x],0); でも計算できる.