数理解析研究所講究録
第 1572 巻 2007 年 124-130

124

CGS の canonical form に向けて
鈴木晃
AKIRA SUZUKI*

神戸大学
KOBE UNIVERSITY

1

はじめにCGS(comprehensive Gr\"obner system, 包括グレブナー系) は Weispfennig により導入され [9] たパラメー
タを含んだイデアルに対するグレブナー基底の一種である. これを計算する実装は Redlog[l], DispGB[3, 21,$ACGB[6,7],$ $SimpleCGB[8]$ 等が提唱実装されてきたが, その標準形は未だ定義されていない. 通常のグレブナー基底の場合には簡約グレブナー基底がその標準形として存在し, 例えば同じイデアルかどうか判定するためにはその簡約グレブナー基底が文字列として一致するかを調べれば良い. 一方でパラメータを含んだイデアルに対してはその標準的な表現が存在しないため, 様々な実装による出力の評価や比較が困難であるが, 適切な CGS の標準形を定義できればこのような困難は克服できる. 今回は, CGS の部分的な標準形をそのアルゴリズムと共に提案したと同時に, 本質的な標準形の困難さについて報告した.
なお, 先行研究として Weispfenning の Canonical CGB[10] や Manubens-Montes の Minimal CanonicalCGS[4] があるが, それらは同値類の意味で $r_{canonicalJ}$ であるに過ぎず, それらもまた完全な標準形とは言えない.

2

CGS の定義と例
本報告では $K$ を体, $L$ を $K$ の代数的閉包,とする. また,する. 各$\sigma_{\overline{a}}(f)$上の項全体の集合$\overline{X}$$\overline{a}\in L^{|\lambda|}$と表す. 各と各$T(\overline{X})$に対し,を変数,上の項順序$f(\overline{X},\overline{A})\in K[\overline{X},\overline{A}]$$H\subseteq K[\overline{A}]$$\overline{X}$$<\overline{x}$に対して,$V(H)\subseteq L^{N}$

を$V(H)=\{\overline{a}\in L^{N} :$\overline{A}=\{A_{1}, \ldots, A_{N}\}$を固定する. 同様に$f(\overline{X},\overline{a})\in L[\overline{X}]$$H$

をパラメータとし.\acute

を $f$ の$T(\overline{A})$$\overline{a}$上の項順序$\overline{X}\cap\overline{A}=\emptyset$$<_{\overline{A}}$も固定による specilization と呼ぴにより定義される代数的集合とする. つまり\sigma_{a}(h)=0 (\forall h\in H)\}$とする. なおここでは $V(H)\subseteq L^{N}$ であるのに対して$H\subseteq K[\overline{A}]$である点に注意したい.

先ず CGS と簡約 CGS を定義する.

定義 1(CGS)$\mathcal{G}=\{(S_{1}, G_{1}), \ldots , (S\iota, G_{l})\}$

言う;$\bullet$$S_{1}\cup\cdots\cup S_{t}=L^{N}$$r_{\S akira\Theta kobe- u}$ac.jp

であり,が$F\subseteq K[\overline{X},\overline{A}]$に対する CGS であるとは以下を満たす時に

125

.

各 $i=1,$

また各 $(S_{i}, G_{i})$ を

定義 2と各$l$$\ldots,$$\overline{a}\in S_{l}$に対してが$\langle\sigma_{\overline{a}}[F]\rangle$の$L[\overline{X}]$に於けるグレブナー基底である.の断片と呼ぶ.

$\mathcal{G}$CGS
グレブナー基底である時に言う.

$\{(S_{1}, G_{1}), \ldots, (S_{l}, G_{t})\}$

与えられた$\sigma_{\overline{a}}[G_{i}]$$F\subseteq K[\overline{X},\overline{A}]$が簡約であるとは各 $i=1,$$l$$\ldots,$と各$\overline{a}\in S_{i}$に対して$\sigma_{\tilde{a}}[G_{i}]$が簡約に対する簡約 CGS は一意ではない. そこで更に簡約 CGS $\{(S_{1}, G_{1}), \ldots, (S_{l}, G_{l})\}$が強簡約である事を, 各断片 ( $G$ のの各とに現れる多項式の (の意味での) 先頭係数と定義した. しかし強簡約 CGS ですら一意からはほど遠い事は以下の例かに対して,$\overline{a}\in S$$S_{i},$$c\in K[\overline{A}]$$G$$(K[\overline{A}])[\overline{X}]$$\sigma_{\overline{a}}(c)\neq 0$

らもわかる.

例 3 以下は $a,$$b$

をパラメータとして $x\gg y\gg t$ の時の {bx--y, ay–x, $x+y-t$ } の強簡約 CGS の例である.

.

( $(b+1)$ $(a+\perp)$ $!-0$ $(b*a-1)$( $(b+1)$( $(b+1)$( $(a+1)$$!$

鴎 $0$$!$.

嵩 $02$冨 $0$

鴎 $0$) $[(a+1)*y-t,$ $(a+1)*x-a*t]$$(a+1)$ 藁 $0$ ) $[ti$ $(-b-1)*yix]$$(a+1)$ 富 $0$ ) $[t,$ $x+y]$, $(b+1)=0$ ) $[t.$ $(a+1)*y*x]$( $(b+1)$ $(a+1)$ $(b*a1)$ $!=0$ ) $[(b*a-1)*t,$ $(a+1)*y$ , $(a+1)*x]$

以下は同じパラメトリックイデアルに対する強簡約 CGS であるが, 断片の数が異なる.

$((b+1)(a+1)!-0. (b*a-1)=0)[(a+1)*y-t. (a+1)*x-a*t]$( $(b+1)$

諺 $0$

.

$(a+1)$ 嵩 $0$ ) $[t,x+y]$( $(b+1)(b*a-1)]=0$

or $(a+1)(b*a-1)]=0$ ) $[(b*a-1)*t,y,x]$

以下も同じパラメトリックなイデアルに対する強簡約 CGS の例であるが, 条件部分や基底部分の表現が具なる.

$((a+1)!=0, (b*a-1)=0)[(a+1)*y-t, (a+1)*x-a*t]$$((b+1)\cdot 0.(a+1)\cdot 0)[t_{*}x+y]$$((b*a-1) !\cdot 0)[t.y,x]$

同じパラメトリックイデアルに対する表現であっても無数の表現が存在し得る事は容易にわかる. ただし
上の例の内では一番読みやすいものは 3 番目のものであり, またこれ以上は簡約化できない (読みやすくできない) 事もわかる. 従って, 1 番目の出力や 2 番目の出力が CGS 計算システムから出力されたとしてもそれを 3 番目の出力へ変換するアルゴリズムが望まれる訳である. しかしこのゴールに対しては多くの困難が存在する. 次節以降でそれらの困難及びその解決への方策について触れる.

3

意味のある CGS の標準形とはただ「標準的である」 というだけであるなら定義できる事は次のようにわかる.
先ず簡約 CGS の同値性は計算により判別可能である旨を注記しておく. ここで二つの簡約 CGSが同値であるとは, 任意のうに取った場合に$\overline{a}\in L^{|X|}$$\sigma_{\overline{a}}[G]=\sigma_{\overline{a}}[G’]$

同値性は計算できる:に対し, 各々の断片 $(S, G)\in \mathcal{G}$ と $(S’, G’)\in \mathcal{G}’$ を$\overline{a}\in S\cap S’$を満たす時に言う. この時, 以下のような手順で簡約 CGS 達$\mathcal{G}$$\mathcal{G}$と$\mathcal{G}’$となるよと$\mathcal{G}’$の

126
1. 条件部分の同値性(a) 各$(S, G)\in \mathcal{G},$$(S’, G’)\in \mathcal{G}’$に対して $(S, G)$ を $(S\cap S’, G),$ $(S\backslash S’, G)$ で置きかえ, $(S’, G’)$ を$(S’\cap S, G’),$ $(S’\backslash S, G’)$ で置きかえるという作業を繰り返す(b) この作業により$\mathcal{G}$と$\mathcal{G}’$.の条件分割は一致する.

2. 多項式部分の同値性(a)と $(S, G’)\in \mathcal{G}’$ に対して根基イデアル $I$ を $V(I)$ が $S$ のザリスキー閉包になるもの$(S, G)\in \mathcal{G}$とする.

(b) $g\in G$ と $g’\in G’$ を比較するのであれば,た時に$c\cdot hc_{\overline{A}}(g’)-c’\cdot hc_{\wedge}\iota(g)\in I$$g$のある単項を満たせば$S$の上で$c\cdot t$$g$とに対応する $g’$ の単項をげ.
$g’$$t$としが同値な多項式であると判断できる.

従って 「文字列として最短であると同時に辞書式順序で最初のもの」 などという定義を 「 $CGS$ の標準形」に与える事は理論的には可能であり, この 「標準形」 を出力するアルゴリズムは以下のように与える事ができる. しかしこれは非現実的であると同時にユーザにとっても不便である.

アルゴリズム StupidCanonicalCGS
入力:$F\subseteq K[\overline{X},\overline{A}]$1. $F$ の簡約 CGS

2.

$G_{0}$

有限$G_{0}$をとにかく計算する.

より長くない文字列の範囲内で、 辞書式順序で小さい順から 「 $CGS$ を表現していて$G_{0}$と同値なもの」 を順に調べる.

3. 最初に見つかった$G$を出力する.

少なくとも $G0$ という上限があるので, このアルゴリズムは停止する事がわかる.

実際には, この StupidCanonicalCGS は現実的な時間内で停止しないとともに, 必ずしも数学的に意味のある出力が得られるとは限らない. そこでより妥当性の高い CGS の標準形の定義を与えたいが, ここでは以下のようなポリシーを採用したい.

1. 簡約 CGS を成している
2. 各断片は強簡約されている

3. 断片の数は最小
4. 各断片 $(S, G)$ の条件部分$S$の表現は一意かつ読みやすい

5. 各断片 $(S, G)$ の基底部分$G$の表現は一意かつ読みやすい

6. 計算するための現実的なアルゴリズムが存在する
これらのポリシーの中にはトレードオフの関係にあるものもあるため, どのようにバランスを取るべきなのかも熟慮する必要があろう. 特に条件 3 と条件 4-5 を同時に最適化するのは経験上困難である.
から 「標準また, 種々のアルゴリズムの比較や検証のために用いるためには, 与えられたCGSJ を求められるだけではなく, 既に他の方法で $F$ から計算された CGS を「標準 $CGS$ 」 に変換する方法が望ましいであろう. 更にそれにかかる計算コストが低いのが望ましい. なお, Monte8 達の MCCGS で$F\subseteq K[\overline{X},\overline{A}]$127
は与えられた $F$ から上の $1.\sim 4$ . のみを満たす CGSを与えるアルゴリズムを目指しているが, 一意性は示されておらずあくまでも可能な限り簡約するに留まっている. 但し, 計算された CGS を「$CGS\rfloor$$1.\sim 4$. を満たすに変換する方法についても MCCGS[4] ではよく研究されており, 参考になるであろう.

注 4 これまでに 「 $oenonical$ な $CGS/CGB$」 として ACGB, CCGB,MCCGS 等が提唱されてきたが, いずれも同値類の意味での canonical に留まり, 文字列としての一意性からはほど遠い.

4

断片数最小を目指して強簡約された簡約 CGS $\mathcal{G}=\{(S_{1}, G_{1}), \ldots, (S_{l}, G_{l})\}$ が与えられたとする. その断片 (Si,定した時, 各に対して,\mbox{\boldmath $\sigma$}a-[G,] に含まれる先頭項の集合とした時, 任意のに対してが成り立っ.
よって, 各 $T\in \mathcal{T}_{Q}:=\{ht_{\lambda}[G_{i}]:i=1, \ldots, l\}$ に対して,$\overline{a}\in S_{1}$$ht[\sigma_{\overline{a}}[G_{2}]]$$\overline{a}\in S_{i}$$G_{t}$) を任意に固は一定である. 実際 $T_{i}:=ht_{\lambda}[c_{:}]$$T_{i}=ht[\sigma_{\delta}[G_{i}]]$$\mathcal{G}\tau=\{(S_{i}, G_{i})\in \mathcal{G} :ht_{\overline{A}}[G_{i}]=T,i=1, \ldots, l\}$に含まれる断片達を一つにまとめる事が可能であれば, 強簡約された CGS として断片を最小のものを得る事ができ, これ以上断片の個数を減らす事はできない事がわかる. つまり$\{(S_{T}, G_{T})\}$$(S_{T}, G_{T})$と$\mathcal{G}\tau$を同値にできれば$\{(S_{T}, G_{T}) :T\in \mathcal{T}_{\mathcal{G}}\}$$(S_{T}, G_{T})$をうまく取る事で,は条件 $1.\sim 3$ . を満たす.

しかしそのようながどのような条件下で取れるかは明らかになっていない.

例 5 (Montes 2007) $\{ax+b, cx+d\}$ (媒介変数は $a,$) に対する簡約 CGS の断片の内, 先頭項集合$b,$ $c,$ $d$

として $\{x\}$ のものだけ取り出すと$\{(ad-bc=0,a\neq 0)\{ax+b\}, (a=0, b=0, c\neq 0)\{cx+d\}\}$となるが, これらを一つの断片にまとめるために Motes は(ad-bc $=0\wedge(a\neq 0\vee c\neq 0)$ ) $\{ax+b,cx+d\}$という表現を許容する事を提案している.
但し, このような許容を以ってしても以下の様な例に対処できず, 一つの断片にまとめる事はできない.
例 6 (Wibmer 2006)$\{a^{2}x-a, ax^{2}-x\}$

傑介変数は a) に対する簡約 CGS は{ $(a=0),$$\{x\},$$(a\neq 0)$, {ax-l}}と計算される.

は

本報告では, これらの例に対する解決案として余剰な媒介変数の導入を提案した. Motens の例に対してを余剰補助変数として,$e$(ad-bc $=0\wedge ea+c\neq 0\wedge(a\neq 0\vee c\neq 0)$ )という一っの断片として, また Wibmer の例に対しては$b$$(ab=0\wedge(a\neq 0\vee b\neq 0))$$\{(ea+c)x+(eb+d)\}$を余剰媒介変数として,$\{(a^{2}+b)x-a\}$という一っの断片として表現できる. ただし, これらの解決案についても (1) CGS の定義を変更する必要がある, (2) 一意性をどう実現するか, などの問題が残されている.

1285

条件部分及び基底部分の表現を一意かつ読みやく
条件部分の表現については 2007 年の RisaCon で提案した方法を用いる事で実現できる. また, それ以外の方法での採用可能であり, どの定義を用いるかだけの問題となる. 従って問題は, 基底部分についても一意かつ読みやすい表現が存在するか否か, そしてもし存在すればそれを計算するにはどうするか, となる.
簡約 CGS の断片 $(S, G)$ が与えられた時, 多項式 $g\in G$ が標準的なものであって欲しい際に最低限満たして欲しい条件として以下を挙げる事ができる. 但し $g=c_{1}t_{1}+\cdots+c_{n}t_{n}(c_{1},$が $S=V(Z)\backslash V(N)$ と書け$t_{1}>\cdots>t$ のと書けているとし, 議論を容易にするために条件部分$\ldots,$$c_{n}\in K[\overline{A}]\backslash \{0\},$ $t_{1},$$\ldots,$$t_{n}\in$$S$$T(\overline{X}),$ていて $Z$ が素イデアルの簡約グレブナー基底であると仮定する.

1. 各 $i=1,$2.

に対して nf $Z($ 亀 $)=c_{i}$ ,$n$$\ldots,$$gcd(c_{1}, \ldots,c_{\mathfrak{n}})=1$.

しかしこれだけでは一意とならない事は以下の例からもわかる.
例 7 $S=V(a^{2}+b)\backslash V(a)$ の上で $f=ax^{2}-(a+b)x$ と $g=x^{2}+(a-1)x$ は同じ多項式を示す. (つまり任意の $(a, b)\in S$ に対して$\sigma_{(a,b)}(f)$を monic 化したものと $\sigma_{(a,b)}(g)$ (を monic 化したもの) は一致する)へ変換したいのだが, これは以下のようなアイディアに基き実現できる. 但し後で述べるように一般の断片に対して適用できない不完全なアイディアである旨
この例ではの方が 「読みやすい」 ので $S$ の上で $f$ を$g$$g$

注記しておく.

である事から a を $gcd_{K[a,b]/(a^{2}+b)}(a,$ $a+$
基本的なアイディアは, $K[a, b]$ に於いて $a+b\equiv a-a^{2}$ modb) のようなものと考え, $f$ の各係数を で「割る」 事で を得るというものである. つまり上記の最低限満たして欲しい条件の 「 $gcd(c_{1}, \ldots, c_{n})=1$ 」 を 「 $gcd_{K[\overline{A}]/(Z\rangle}(c_{1,\ldots,h})=1$ 」 で置き替えられれば良い. 但を定義できるための条件が明らかになっていない点に問題が残されている. どこに集中すれし,$\langle a^{2}+b\rangle$$a$$g$$gcd_{K[\overline{A}]/(Z\rangle}$

ば良いのかという問題提起を以下に記す.

定義 8$I\subseteq K[\overline{A}]$を素イデアル, $a,$$b\in K[\overline{A}]\backslash I$とする. この時因子であるとは、 $a^{l}d-a\in I$ かつ $b’d-b\in I$ となる $a’,$
問題 9 与えられた $I,$ $a,$$b$

注 10
レ$\overline{d}\in D$を{$c\overline{d}\in D$$d\in K[\overline{A}]$となる:$d$は $I$ を法としての $a$ と$c\in K[\overline{A}]\backslash K$

が $UFD$ であれば $gcd(a, b)$ を$K[\overline{A}]/I$$b’\in K[\overline{A}]$が $I$ を法としての$a$と$b$の共通が存在する時に言う.

に対し, (「最大」 とは限らない) 極大共通因子を見つけたい. つまり$D=$とした時に、$d\in K[\overline{A}]$$b$の共通因子}が存在しないように見つけたい.

$K[\overline{A}]/I$で考えればいいが、 一般には

$K[\overline{A}]/I$

は $UFD$ ではな

ただし、 $I$ を素としているので整域ではある。

$a_{o}$

ここで dim(I) $=0$ の時には $I$ は極大イデアルなので $K[\overline{A}]/I$ は体となり,何もする事はない.

またdim(I) $=1$ の時には gcd $K[\lambda]/I(c_{1}, \ldots, c_{n})=1$ とする手続きの候補は以下のように与えられる. 実際, この手続きに従えば例 7 の $f$ は 9 に変換できる事も確認できる.
ここでを与えられた多項式とする. 但しを 1 次元素イデアル,$a_{1}t_{1}+\cdots+a_{\mathfrak{n}}t_{n}\in K[\overline{A},\overline{X}]$$I\subseteq K[\overline{A}]$$a:\in K[\overline{A}]\backslash I,$

1.

$t:\in T(\overline{X})$$\{B\}\subseteq\overline{A}$

2. 各 $i=1,$とする.

を maximally independent modulo$\ldots,$$n$に対して,$I$とする.

129
(a)

$I+\langle a_{i}\rangle$(b)$c_{i}\in K[\overline{A}]$は$0$次元なので $K[B]\cap(I+(a_{i}\rangle)$ の生成元

$b_{i}$を取れて,を $nf_{I}(c_{i}a_{i})=b_{i}$ なるものとする.

3. $c:=1cm(c_{1}, \ldots,c_{n})$ とする.
4. 各 $i=1,$(a)5.

($n$に対して,$d_{i}=nf_{I}((c/q)b_{i})_{B\gg\overline{A}\backslash \{B\}}$とする.

$d:=gcd(d_{1}, \ldots, d_{n})_{K(\overline{A}\backslash \{B\})[B)}$

とおき,

6.

$e_{i}=d_{i}/d\in K[\overline{A}]$7.

$e_{1}t_{1}+\cdots+e_{n}t_{n}\in K[\overline{A},\overline{X}]$

この時. 各$c$$\ldots,$$c_{1}a_{1}b_{i}$$e_{t}/e_{1}$

一果

$i$

に対して

$b_{1}a_{i}$とおく.

$K[\overline{A}]/I$) $=0$ であり,を返す.

にて$I$$c_{1}$

果 $d(a_{1}e_{i}-e_{1}a_{i})=c_{1}h(a_{1}d_{i}-d_{1}a_{i})=c_{1}b(a_{1}(c/b)b:-(c/c_{1})b_{1}a_{i})=$が素である事より$a_{1}e_{1}-e_{1}a_{i}\in I$がわかる. つまり有理関数果/al とは $V(I)$ の上 (の定義される範囲) で一致する.

但しこの手続きを 2 次元以上に拡張する手法については議論の余地が多く残されている.

6

最後に
以上のように canonical な CGS の定義に向けて乗り越えるべき困難は多く残されている. 特に,.

$\bullet$

断片の数を減らす際にどこまで定義の拡張を許すか,基底部分の標準形をヒ $=$ ーリスティックな手法に頼らず得る事ができる力\searrowという二点については互いに影響を与える点もあり, 克服までにはまだ研究が必要であると予想される.

参考文献[1] Dolzmann, A. and Sturm, T. (1997). Redlog: Computer algebra meets computer logic, ACM SIGSAM
Bulletin, 31, 2, 2-9.
[2] Manubens, M. and Montes, A. (2004). Improving DISPGB Algorithm using the discriminant ideal,J. Symb. Comp., 41, 1245-1263.
[3] Montes, A. (2002). A new algorithm for discussing Grobner basis with parameters, J. Symb. Comp.
33, 1-2, 183-208.

[4] Manubens, M. and Montes, A. (2006). Minimal$C$anonical Comprehensive Grobner System, preprint

MA2-IR-06-00015.
[5] Noro, M. and Takeshima, T. (1992). $R\dot oea/Asir-A$ Computer Algebra System. International Symposium on Symbolic and Algebraic Computation (ISSAC 92), Proceedings, 387-396.

[6] Suzuki, A. and Sato, Y. (2002). An Alternative approach to Comprehemsive Gr\"obner Bases. Interna.
tional Symposium on Symbolic and Algebraic Computation (ISSAC 2002), Proceedings, 255-261.
[7] Suzuki, A. and Sato, Y. (2003). An Alternative approach to Comprehensive Grobner Bases. J. Symb.

Comp. $36/3arrow 4,64k667$ .

130[8] Suzuki, A. and Sato. Y. (2006). A Simple Algorithm to Compute Comprehensive Grobner Bases Using
Gr\"obner Bases, International Symposium on Symbolic and Algebraic Computation (ISSAC 2006),
Proceedings, 326-331.
[9] Weispfenning, V. (1992). Comprehensive Gr\"obner bases, J. Symb. Comp. 14/1,1-29.
[10] Weispfenning, V. (2003). Canonical Comprehensive Grobner bases, J. Symb. Comp. 36, 669-683.