数理解析研究所講究録
第 1843 巻 2013 年 38-50

38

グレブナー基底候補の正当性検証について
野呂正行
神戸大学大学院理学研究科

noro@math.kobe-u.ac.jp
横山和弘
立教大学理学部

kazuhiro@math.kyushu-u.ac.jp

1

はじめに

グレプナー基底計算の効率化技法として，モジュラー計算法がある．これは，中間計算における係数
膨張を押える効果をねらったもので，近年では，並列計算と組み合わせることで，大幅な計算効率が期待されている．

本諭文では，モジュラー計算法における重要な要素である，lucky prime とモジュラー計算から正しい基底を求める際の計算の正当性について以下の 3 点について報告する．
1. 現在知られている方法を統一的に分類し，計算の正当性がどのように保証されているかを明確にする．

2. 一般の設定では，効率的な正当性の検証法が確立されていないが，それを構成するためのいくつかの試みを報告する．

3. モジュラー計算の連鎖として，正当性を効率良く検証できるイデアルの操作を提案する．

ここでは，まずいくつかの概念 (ludcy phme) を統一し，それらに対応する正当性検証法を紹介することからはじめていく．

問題設定と lucky prime の定義2を有理数体， を整数環とし，Fp を位数 の有限体とする．変数の集合をのイデアルを
をの有限部分集合とする． で生成されるとする．素数$F$$F$$\mathbb{Q}[x1$$\{_{T}^{a}|a,b\in \mathbb{Z},p\parallel b\}$を$\mathbb{Z}_{p}^{0}$

から Fp

を

$\mathbb{Q}[X]$で表す． から Fp の canonical projection をへの写像に拡張する．すなわち，$\phi_{p}(\not\in)=\phi_{p}(a)x\phi_{p}(b)^{-1}$から Fp[X] への projection で多項式の係数にして，$\phi_{p}(S)$$I$$\mathbb{Z}$$\mathbb{Z}_{p}^{0}$

とし，
に対して，

$X=\{x_{1}, \ldots,x_{\mathfrak{n}}\}$$p$$\mathbb{Z}$$\mathbb{Q}$$\phi_{p}$$\phi_{p}$$p$であらわす．さらに，$\phi_{p}$となる．同じ記号で，$\mathbb{Z}_{p}^{0}[X]$を施す写像を表す．また，$\mathbb{Z}_{p}^{0}[X]$

の部分集合

$S$

に対

で $\{\phi_{p}(f)|f\in S\}$ を表す．

以下では， を$I$

$F$

で生成される$\mathbb{Q}[X]$のイデアルとする． が$F$$\mathbb{Z}_{p}^{0}[X]$の部分集合となるとき，$I_{p}(F)$のイデアルを表す． を固定して考え，混乱がない場合には， を略してちとも書く．さらに，とする． と互いに素な整数は $modp$ で可逆であるので，でもあることに注意する．一般にで $\phi_{p}(F)$ で生成される $F_{p}[X]$

$F$

$F$

$I_{p}^{0}=\phi_{p}(I\dot{\cap}\mathbb{Z}_{p}^{0}[X])$$p$$P_{p}=\phi_{p}(I\cap \mathbb{Z}[X])$$I_{p}(F)$欧$P_{p}$

39
であり，$I_{p}(F)$を順序と$I_{p}^{0}$が等しくなるとは限らない． を順序$G$$\prec$に関する$I$の簡約グレブナー基底，$G_{p}$

に関する $I_{p}(F)$ の簡約グレプナー基底とする．

$\prec$記号について : 環 $R$ でのイデアル生成に関しては，$\langle\rangle_{R}$の記号を用いる．混乱がなければ，添字の

$R$

を

または
, を考える．また， で生成され略す．ここでは， として $K[X],$ は係数体でありる係数 1 の単項式全体をとし，項順序 に関して，多項式 $f\in R$ の leading power product (係数, 係数付き先頭項を
1 を, 先頭係数をとおく．混乱がなければ，順序 を略す．
$R$

$K$

$K=\mathbb{Q}$$\mathcal{T}$$l_{P\prec}(f)$$)$$ht_{\prec}(f)$多項式の集合$S$$\{hc_{\prec}(f)|f\in S\}$

$hc_{\prec}(f)$$\prec$に対しては $lp_{\prec}(S)=\{lp\prec(f)|f\in\dot{S}\},$ $ht_{\prec}(S)=\{ht_{\prec}(f)|f\in S\},$ $hc_{\prec}(S)=$とし，イデアル の先頭項より生成されるイデアルを のイニシャルと呼び，で生成されるイデアルもで表す．また，集合 $H$ に対して，
$J$

$J$

$Init_{\prec}(J)=\langle ht_{\prec}(f)|f\in J\rangle$

$I$

が $R$

$l_{P\prec}(H)$で表す．混乱がなければ，順序$Init_{\prec}(H)$$X$$F_{p}$$\prec$$\prec$を略す．

の斉次イデアルのとき，Hilbert function を$HF_{I}$で表す．(通常は $HF_{R/I}$ と書くが，ここでは [1] の記号を用いる．) 本論文で利用する Hilbert function の性質を以下に上げておく．

Lemma 1

(1)

$I$を斉次イデアルとし， を$G$のグレブナー基底とする．このとき，以下が成り立っ．

$I$$HF_{I}=HF_{Init(I)}=HF_{Init(G)}$(2)

を斉次イデアルとし， を

$I$

$F$

$I$

の生成集合とする．また， を素数とする．このとき，以下が成り$p$立つ．
$HF_{I}\leq HF_{I_{p}(F)}$さらに，以下が成り立つ．
$HF_{I}\leq HF_{I_{p}^{0}}\leq HF_{I_{p}(F)}$(3)$I,$ $J$

を斉次イデアルとし，$I\subset J$とする．このとき，以下が成り立っ．

HFI$\geq H$」晴

等号が成り立つときは，$I=J$ である．
(1) は Theorem 6.2.6 in [3] である．(2) の前半は Theorem 5.3 in [1] であり，後半は Exercise 5.1.5 in[3] である．(3) は定義より直接示される．
素数$p$の luckyness

に関しては，以下のような定義が提案されている．([1, 2, 8, 9, 14] を参照)

Deflnition 1 (lucky prime)$F$を$\mathbb{Z}_{p}^{0}[X]$(1) 素数$p$

が $F$ に対して compatible(2) 素数$p$

が $F$ と項順序$\prec$の部分集合とする．

とは，$I_{p}^{0}=I_{p}(F)$のときにいう．

に対して lucky とは， の簡約グレブナー基底 $G$ と$I$$I_{p}$の簡約グレブナー基底に対して，であって，$\phi_{p}(G)=G_{p}$ のときにいう．(簡約を外して，$G$ の各元の先頭係数が で割れないとしてもよい)$G_{p}$$G\subset \mathbb{Z}_{p}^{0}[X]$$p$(3) 素数
$Y)$

,

$p$

が $F$ と項順序$\prec$に対して strongly$\phi_{p}(Init_{\prec}(I)\cap \mathbb{Z}_{p}^{0}[X])=Init_{\prec}(I_{p}(F))$(4) 斉次イデアルの場合に，素数$p$mpatible とは， が $F$ に対して compatible であ$\omega$$P$のときにいう．

が $F$ に対して Hilbert luckyとは，$HF_{I}=HF_{I_{p}(F)}$ のときにいう．

40
2.1

種々の luckyness の間の関係

これらの ‘lucky” に関する定義に関して，次の関係がある．

Lemma 2 以下では
(1)

$F$

$F$

を

$\mathbb{Z}_{p}^{0}[X]$の部分集合とする．

のある順序に関するグレブナー基底で， の元の先頭係数が で割れなければ， は

が $I$

$F$

$p$

$p$

$F$

に対して compatible である．

(2) 素数$p$

が $F$ と項順序$\prec$に対して ludcy であれば，素数$p$は $F$ に対して compatible である．すなわち，$I_{p}(F)=$ 窄である．
(3) 素数が $F$ と項順序$p$$\prec$に対して lu&y であることと，strongly compatible であることは同値である．

(4) 斉次イデアルの場合では，素数 が $F$ に対して Hilbert lucky であれば， は $F$ に関して
$I_{p}(F)=$ 蓼である．)
compatible である．(すなわち，
$P$

$P$

(5) 斉次イデアルの場合では，素数て Hilbert lucky である．

が $F$ と項順序

$P$$\prec$に対して luck

であれば，素数$p$は $F$ に対し

定義より，生成集合 と項順序 に対して lucky でない素数 (unlucky ともいう) は簡約グレブ
ナー基底の先頭係数の約数となるため，有限個である．Lemma 2 より，斉次多項式の生成集合 に対して Hilbert lucky でない素数は lucky でない素数となるため，その個数も有限個となる．また，一般
と項順序
の生成集合
に対して，strong compatible でない素数は lucky でない素数であるので，
これも有限個となる．さらに， に対して mpatible でない素数も有限個であることがわかる．
$F$$\prec$$F$$F$$\prec$$F$$\omega$Lemma 3 (lucky prime の個数の有限性) 生成集合 と項順序 に対して ludy でない素数の個数は有限個である．また，strong mpatible でない素数も有限個であり， に対して compatible でな
い素数も有限個である．斉次多項式の生成集合 に対して Hilbert lucl でない素数も有限個である．
$F$$\prec$$F$$\infty$$F$

3

種々の正当性判定法

本節では，グレブナー基底候補の正当性判定について，Amold[1] の結果や Noro-Yokqyama [8] の結果などを合わせて得られる方法，およびそれらが使えない状況での方法について述べる．
グレプナー基底の候補についていくつか定義を与える．

Definition 2 以下では，

$G$

(1)

$G_{can}$

が $F$ と項順序

頭係数

$P$

$\prec$

$n$
。

を

で割れず，

$\phi_{p}(G_{can})$$I$$\prec$

一般には，$I_{p}(F)$candidateの部分集合とし， を順序とする．
$\prec$に関する先の各元のGr\"obner basis candidate とは $G$
が $I_{p}(F)$ のに関するグレプナー基底であるときにいう．

に対する(2) $G_{can}$ がイデアル と項順序
元のに関する先頭係数は基底であるときにいう．

$G_{can}$$I\cap \mathbb{Z}_{p}^{0}[X]$$\prec$$\gamma$$n$。

$\prec$compatible Gr\"obner basis candidate とは$\prec$

に対する

$P$

で割れず，

$\mu$

$\phi_{p}(G$

$n)$

。

が

$\phi_{p}(I\cap \mathbb{Z}_{p}^{0}[X])$の$\prec$

$G$

$n$
。

の各

に関するグレブナーと噌は等しくないので，上の 2 つの定義は異なるものを与える．p-Gr6bner basis
7 ナー基底のときは， は と に対して lu&y であり，$I_{P}(F)=$ 瑠でが $I$ のグレ

$P$

$F$

$\prec$ある．(Lemma 2)

modular 計算法で結果を保証するアプローチとして，大きく以下の 2 つに分類でぎる．

41(1) compatibility と$G_{can}\subset I$(2) Hilbert luckyness と3.1を利用するアプローチ$\langle G_{can}\rangle\supset I$を利用するアプローチ

compatible 型の結果

Proposition 4 (Theorem 2.6 嘉$n[8]$ )がとに対するか compatible グレブナー基底ではのグレブナー基底である．
あって，
ならば，
$G_{can}$$G_{can}\subset I$$I$$\prec$$I$$G_{can}$compatible Gr\"obner basis candidate の重要な部分は compatiblity にある．また，これより，$G_{can}$
が自分自身が生成するイデアルのグレブナー基底であることをチェックする必要がない．
$\psi$$\langle G_{can}\rangle$

がとCorollary 1
に対する -Gr\"obner basis candidate であって，がはのグレブナー基底である．
とき， comptatible であれば，$G_{can}$$I$$\prec$とする．この$I$$G_{can}$$p$$G_{can}$$G_{can}\subset I$$P$

が $I$ の別の順序のグレブナー基底であって，その元の先頭係数が $P$ で割れなれば，$P$ は compatibleであるので，以下を得る．

Corollary 2 の別の順序に関するグレブナー基底 $G’$ がの部分集合であり，$G’$ の元の先$G’$
頭係数は で割れないとする．(つまり， がとに対して lucky とする．) このとき，がとに対する -Grobner basis candidate であって，はのグレブナー基底ならば，$I$$\prec’$$\mathbb{Z}_{p}^{0}[X]$

$p$

$p$

$\prec’$$G_{can}$$G_{can}\subset I$$p-$$\prec$$G_{can}$

$I$

$I$

である．
$I$

$G_{can}\subset I$のグレブナー基底 $G’$ が分かっているので，$G_{can}$ の各元の $G’$ に関する正規の検証は，形計算で確かめることができる．

3.1.1

応用例

compatibility の応用による Syzygy 計算アルゴリズムを示す．
Algorithm 1 (Algorithm 15 in [7])入力 : $F=(fi, ., . , f_{\epsilon}),$ $fi,$の項順序
出力 :syz $(F)$ の $(POT, \prec)$ に関するグレブナー基底 $S$のに関するグレプナー基底 $G=(g_{1}, \ldots,g_{t})$$tG=C\cdot tF$ を満たす $(t, s)$ -行列 $C$$\ldots,$$\langle F\rangle$$f_{\delta}\in \mathbb{Z}[X]^{l};R^{\iota}$$\prec$$\prec$$m_{i}arrow(f_{i}, e_{i})\in R^{l}\oplus R^{S}=R^{l+s};Marrow\langle m_{1},$$\ldots,$$m_{s}\rangle$

restart:$parrow m_{i},$ $\ldots$if$G_{\dot{c}an}$,m、の $(POT, \prec)$ に関する先頭係数を割らない素数をみたす -Gr\"obner candidateが存在しない then goto restart$G_{can}arrow M$の，$\langle G_{can}\rangle\subset M$$p$$Sarrow\{h\in R^{s}|(0, h)\in G_{can}\}$$Garrow\{g\in R^{l}|g\neq 0$$Carrow$第$i$and $(g, h)\in G_{can}$ for some $h\in R^{S}\}$

行が $(g_{i}, h_{i})\in G_{can}$ に対する醗である $(t, s)$ -行列

retum $(S, G, C)$

42
部分が順序がで生成される加群 $M$ のグレブナー基底を，ゐ部分より下の $POT$ 順序で計算することで，syz $(F)$ のグレブナー基底， のグレブナー基底および $F$ からグ

このアルゴリズムは，$(f_{i},e_{i})$$e_{i}$$\langle F\rangle$が，レブナー基底を生成する関係式をまとめて計算するアルゴリズムに基づく．ここで，の先頭部分が轟より順序が上の $POT$ 順序に関して既にグレブナー基底になっていて，しかも$n\subset M$ をみたすものがあ$(POT, \prec)$ に射する
Gr\"obner candidate で係数が 1 であることから，
れば compatibihty により $M$ のグレブナー基底となる．
$(m_{1}, \ldots,m_{\epsilon})$$e$$e_{i}$

$G$

$\mu$

。

Hilbert ludcy 型の結果

3.2

まず，斉次多項式の場合に HUbert lucky を考える． が始めから斉次である場合には，以下の Amold$F$の結果がある．
をと順序 に対する p-Gr\"obner
Proposition 5 (Arnold の主定理: $Th\infty rem7.1$ in [1])はかつcandidate であって，のグレブナー基底とする．このとき， は の$G_{\infty n}$$G_{can}$$n\rangle\supset I$$\langle G$。

$\langle G$$F$$\prec$$G$$n\rangle$$I$。

グレブナー基底である．

$p$が $F$ に関して Hilbert lucky であることが分かつている場合には，Lemm 2 (4) より $P$ は $F$ に関して

mpatible になるので，Corollary 1 より，以下の形のものが得られる．

$\infty$に対する p-Gr\"obner
を $F$ と順序
Lemma 6 が $F$ に関して Hilbert lucky であるとし，
candidate であって，とする．このとき， は のグレブナー基底である．
$G$

$P$

$G$

$\langle G_{can}\rangle\subset I$$\prec$

$n$
。

$I$

Remark lComplete intersection の場合のように，予め Hilbert function の値が分かつている場合には，計算した により， が Hilbert lu&y であるかどうかが判定できる．また， の計算が degree$G_{p}$$G_{p}$$p$の低い順に計算されるため，Hilbert lucky でない場合には，その計算途中で判定ができる．
3.2.1

非斉次の場合次に， が斉次でない場合に Amold の結果をどのように適応できるかを考える．そのために，いく$F$

つかの概念を用意する．

Deflnition 3 $K$ を係数体とする多項式環 $K[X]$ を考え、 $KtX$ ] の元入して，斉次化 (homogenization) したものを$f^{h}$とする．
$f$

が $K[X]$$f$に対して，変数の元であれば，$f^{h}$

$t$

を新たに導

は $K[X,t]$ の元となる．逆に斉次多項式んに対して に 1 を代入したものを非斉次化 (dehomogenization) といい，が同様に定$h(X, 1)$ をん $=1$ またはと書く．$K[X,t]$ の部分集合 $T$ に対しても，$T|_{t=1}$ または
$t$

$|$

,

$T^{d}$$h^{d}$

義される．
$K[X]$ のイデアル $L$に対して， で生成される $K[X, t]$ のイデアル$L$で表す．イデアルの生成元 $S$ に対して，$\langle f^{h}|f\in L\rangle_{K[X,t]}$のとき， をを $L$ の斉次に対して，ここでは $home\succ$ compatible と呼ぶことにする．(このような生成集合を Macauley base と呼ぶ．[6] を参照)の上$X$ で生成される項全体冗の上の項順序に対して，$X^{h}=X\cup\{t\}$ で生成される項全体

化イデアルと呼び$L^{h}$$L$$\langle S^{h}\rangle=L^{h}$

$S$

$L$

$\mathcal{T}^{h}$$\prec$を次のように定義する．
の項順序
の2元
に対して，
$\prec h$$\mathcal{T}^{h}$$X^{\alpha}t^{a},$$X^{\beta}t^{b}$(1) $a+|\alpha|>b+|\beta|$ または，(2)$X^{\alpha}t^{a}\prec hX^{\beta}t^{b}$$a+|\alpha|=b+|\beta|$

であるとは，次のいずれかを満たすときにいう．

かつ，$X^{\alpha}\prec X^{\beta}$

である．

43
ここで，
とする．ここでであって， はを表し，である． が degree compatible な順序であれば，$\alpha=(\alpha_{1}, \ldots, \alpha_{n})\in \mathbb{Z}\geq 0^{n}$

$($

への制限

$\mathbb{Z}\geq 0=\{n\in \mathbb{Z}|n\geq 0\}$は$\prec h|\tau$$X^{\alpha}$$\prec$$|\alpha|=\alpha_{1}+\alpha_{2}+\cdots+\alpha_{n}$$x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}}$$)$$\prec$$\prec h$の$\mathcal{T}$に一致する．

よく知られた事実として以下がある．(Proposition 4.3.18, 4.3.21, Corollary 4.3.8, Tutoria153 in [6]などを参照)

Lemma 7 以下では， を
$L$

(1)

(2)

が $L$ の$G$$\prec$$G^{h}$らに，はを$L^{h}$の$G’$$\mathbb{Q}[X]$のイデアルとし， を degree compatible な順序とする．
$\prec$に関するグレブナー基底であれば， は に対して homo-compatible である．さのに関するグレブナー基底となる． が簡約であれば， も簡約である．
$G$$L^{h}$$\prec h$$G$$\prec h$$G’|_{t=1}$

ナー基底である． が簡約であれば，$L^{h}=(\langle F^{h}\rangle :t^{\infty})$

Lemma
な順序

$G’|_{t=1}$

を $L$ の生成集合とする．

十分条件は$G^{h}$

に対するグレブナー基底とする．このとき，$G’$$(3\rangle F$$L$$\prec$に対するグレブも簡約である．

である． が homo-compatible であるための必要$F$$(\langle F^{h}\rangle:t^{\infty})=\langle F^{h}\rangle$

が degree compatible な順序であって，$8\prec$

は $L$ の$F\subset \mathbb{Z}_{p}^{0}[X]$

が $I$ のある別の degree compatibleに関するグレブナー基底であり，さらに， の各元の先頭係数は で割れないとする．こはに対してもcompatible でのとき， は に対して homo-compatible であり，$F$$\prec’$

$F$

$I$

$p$

$I_{p}(F)$$\phi_{p}(F)$$hom\triangleright$

ある．
をと degree compatible な項順序にLemma 9 (Theorem 2.4 in [4] の修正版その 1)
対する rGr\"obner candidate であって，かつはのグレブナー基底とする．こ$I_{p}(F)$ に対して homo-compatible ならばがはのとき，のグレプナー基底である．実際に，$F$$G_{\infty n}$$\prec$$G_{can}$$\langle G_{can}\rangle\supset I$$\langle G_{can}\rangle$$G$$\phi_{p}(F)$$I$homo-compatible であるかどうかは，$(\langle\phi_{p}(F)^{h}\rangle:t^{\infty})=\langle\phi_{p}(F)^{h}\rangle$

であるかどうかで判定できる．

Lemma 9 より，change of order 型のものとして以下力城り立つ．
$F$ はが degree compatible な順序であって，Corollary 3 (Theorem 2.4 in [4] の修正版その )のある別の degree compatible な順序の部分集合に関するグレブナー基底であり，$F$ は$F$ の各元のに対する先頭係数は で割れないとする．
を $F$ と degree compatible な順で，序に対する -Gr\"obner candidate であって，かつはのグレブナー基底と$2$$I$$\prec$$\prec’$$\prec’$$\prec$$\mathbb{Z}_{p}^{0}[X]$$G_{can}$$p$$\langle G_{can}\rangle\supset I$$P$

する．このとき $G$ は次に，$\phi_{p}(F)$$I$$G_{can}$$\langle G_{can}\rangle$のグレブナー基底である．

が $I_{p}(F)$ に対して homo-compatible でない場合を考える．順序$\prec$は degree-compatibleとしておく．このとき，次の分解を考える．
$\langle\phi_{p}(F^{h})\rangle=(\langle\phi_{p}(F^{h})\rangle:t^{\infty})\cap\langle\phi_{p}(F^{h})\cup\{t^{k}\}\rangle,$

ここで $k$ は $(\langle\phi_{p}(F^{h})\rangle:t^{k})=(\langle\phi_{p}(F^{h})\rangle:t^{\infty})$となる正整数とする．

り，

は $I_{p}(F)^{h}$ のグレブナー基底である．

$G_{p}$

を $I_{p}(F)$ のグレブナー基底とすると，$G_{p}^{h}$$(\langle\phi_{p}(F^{h})\rangle:t^{\infty})=I_{p}(F)^{h}$

ここで，次の補題を用意する．(証明は Lemma 5.3.11 と Exercise 5.3.8 in [3] による．)

であ44$X$ を変数の集合とする．
Lemma 10 $K$ を体とし，$A,$ $B$

を $K[X]$ の斉次イデアルとする．このとき，$HF_{A\cap B}+HF_{A+B}=HF_{A}+HF_{B}$ となる．

以下，

$G$

$n$
。

を

$p$

$G$
-Gr\"obner candidate とする．すなわち，$n\subset \mathbb{Z}_{p}^{0}[X]$

。

であって，

$\phi_{p}(G_{\infty n})=G_{p}$とのする．さらに，に対する簡約グレブナー基底を計算し，それを $H$ とする．このとのグレブナー
は斉次イデアルであるので，Propoeition 5 が使えて， の効果で
き，
$k=1$
のように
基底計算より効率がよいと予想される．特に，が非常に小さいときには，の各は実質のグレブナー基底計算が効率的であることが期待される．$k=1$ であれば，の斉次イデアルのグレブナー基底計算になる．
元の次数最大部分だけからなるイデアルであり，$\langle F^{h}\cup\{t^{k}\}\rangle$$\prec h$$t^{k}$$\langle F^{h}\cup\{t^{k}\}\rangle$$\langle F^{h}\rangle$$k$$\langle F^{h}\cup\{t^{k}\}\rangle$$F$$\langle F^{h}\cup\{t\}\rangle$$\mathbb{Q}[X]$Lemma 10 により，以下の定理が得られる．
Theorem 1 (Theorem 2.4 in [4] の修正版その 4)のグレブナー基底であり，$I\subset\langle G$$\langle G_{can}\rangle$

ち$H\subset \mathbb{Z}_{p}^{0}[X]$
$,$

であって，

$\phi_{p}(H)$は$n\rangle$。

$\langle\phi_{p}(H)\rangle$

$G$

$n$
。

を

$G_{can}$ は-Gr\"obner candidate とし，$\triangleright$とする．さらに， は $H$ に対して lucky とする．(すなわ$P$のグレブナー基底である．) このとき，$G_{\infty n}\ovalbox{\tt\small REJECT} aI$のグレ

ブナー基底である．

3.3

グレブナー基底候補に対する生成関係式による検証$F=\{fi, \ldots,f_{m}\}\subset \mathbb{Q}[X],$ものとする．

$\langle\phi_{p}(F)^{h}\rangle$を$G_{can}$$I=\langle F\rangle$のグレプナー基底候補で，$I\subset\langle G_{\infty n}\rangle$のグレプナー基底が計算できる場合には，前節の方法により

$G$

を満たす

$n\subset I$。

のチェックが可能であるが，この計算ができない場合には，各 $g\in G_{can}$ に対する生成関係式，すなわち$g=h_{1}fi+\cdots+h_{m}f_{m}(F=\{fi, \ldots,f_{m}\})$ なる表示を作るという方法が考えられる．

生成関係式をつくる方法としては，有限体上の生成関係式から CRT あるいは Hensel で構成する方法が提案されている．この方法で必要となる有限体上の生成関係式は，Buchberger アルゴリズムを実行中に剰余だけでなく商も記録しておくことにより得られるが，一般には冗長な項を多数含み，項CRT,
Hensel数が巨大になるため，そのまま構成を適用するのは効率がよくない．よって，次の方法に$h_{i}$

より項数を減らすことが考えられる．

1. $g\in G_{can}$ に対し，生成関係式 $\phi_{p}(g)=h_{1}\phi_{p}(fi)+\cdots+h_{m}\phi_{p}(f_{m})$ を作る．
2.

$h_{i}$の係数を未定係数に置き換えた$H_{i}$

に対し $g=H_{1}fi+\cdots+H_{m}f_{m}$ を満たす未定係数の値が存在することを示す．

3. 一旦有限体上で解いて，0 にしてよい係数を 0 にしてから有理数体上で解く．
この方法により有限体上の生成関係式の項数を減らすことができるが，0 にできる係数の選び方に任意性があるため，残った未定係数に対する方程式を実際に招く懸念もある．もし，鋤

$z(\phi_{p}(F))$

にこれを

$S$

で割った剰余上で解く際に，不必要な係数膨張を$(h_{1}, \ldots, h_{m})$ の代わりのグレブナー基底 $S$ が分かっていれば，$(r_{1}, \ldots,r_{m})$$\phi_{p}(g)=r_{1}\phi_{p}(fi)+\cdots+r_{m}\phi_{p}(f_{m})$$\mathbb{Q}$を使うことができる． に関して簡約な$S$を満たすものは一意的である．よって$(r_{1}, \ldots,r_{m})$$(r_{1}, \ldots,r_{m})$でを使うことは，上で述べた，方程式を解いて冗長係数を 0 にするのと同じ効果をもつ．

3.3.1

計算例 1 :cyclic-7 の場合$p=$ 31991 に対を， (cyclic-7) の全次数逆辞書式順序グレブナー基底の中のある元とする．
$\phi_{p}(g)=h_{1}\phi_{p}(fi)+\cdots+h_{7}\phi_{p}(f_{7})$ を満たす
を，し，を，計算履歴から求める．
$g$$C_{7}$$h_{1},$$\ldots,$$h_{7}$$(r_{1}, \ldots, r_{7})$45$(h_{1}, \ldots, h_{7})$を $syz(C_{7})$ のグレブナー基底で割った剰余とする．このとき，それぞれから未定係数の値を求める過程の内訳は次の通りとな

$b$

る．

表が示すように，この例では，syzyy は方程式のサイズ縮小にのみ有効であった．

3.3.2

計算例 2 :Romanovski の例

V. G. Romanovski et al. [10] で扱われているイデァル

成を持つ．この例については$I\subset\langle G_{can}\rangle$$I$は，8 変数で 10 桁程度の係数の非斉次な生なるグレブナー基底候補 $G_{can}$ の計算は modular 計算により容易にできる．実際，数個程度の素数で CRT での結果が stable になる．また，得られた$J=\langle G_{can}\rangle$

に対し， はきれいな形の素分解を持つので，護も同様であると期待できる．しかし， の$\sqrt{J}$$I$$\mathbb{Q}$上のグレブナー基底計算は，どの、ような方法でも容易ではない．さらに，斉次化すると，有限体でもグレブナー基底が終わらない．

実験の結果，候補$G_{can}$の元のうち二つを $I$ に添加すれば Buchberger アルゴリズムに$\grave{}$$(g_{1}, g_{2})$よりグレブナー基底 $G_{can}$ を得ることが分かった．

$g_{1},$$g_{2}$

はほとんど support が同じなので，取りあえず一つ選んで生成関係式を作る実験を行っている．有限体上での syzygy 計算が困難のため，先に述べた，計算履歴から作った未定係数の方程式を有限体上で解いて，0 にできそうな係数を 0 にしてから改めて方程式を解く，という方法を適用した．最初に得られる線形方程式を表す行列のサイズは$(1.6\cross 10^{5})\cross(3.5\cross 10^{5})$程度で，未定係数のうち$2.2\cross 10^{\’{o}}$

個を

$0$

とした残りの変数 $(l.3\cross 10^{5}$ 個 に$)$関する線形方程式を得た．これを 2012 年 9 月から 上でのガウス消去により計算している．2013 年
3 月現在まだ終了していないが，CRT および並列計算による計算が有効であろう．これは今後の課題で$\mathbb{Q}$ある．

4

実際の構成法について

modular 法を利用したグレブナー基底計算は以下の 3 通りが考えられている．これらは，グレブナー
基底計算途中の係数膨張や項の膨張，余計な計算 (簡約操作など) を押えることをねらいとしている．
(1) Chinese Remainder Theorem(CRT) 型(2) Hensel Lifting 型(3) 混在型 (主に Buchberger 計算法ベース)(1) CRT 型: この方法の利点は，並列計算化が可能であり，unludcy prime の処理にも優れている．また，modp での計算には， が効率的に使える利点もある，問題点は，優れた係数評価法がないため，どこまで mod us(法) を上げればが求まるかが不明であり，modulus の設定 (失敗した場合の次の modulus の取り方も含む) に heuristic が入る．実際的な実装には，この設定が重要である．
$F_{4}$$\omega$$G_{can}$

46
LUCKY, UNLUCKY の判定 : 複数の素数$\ovalbox{\tt\small REJECT}$$p_{1},$ $\ldots,p_{k}$こ対してを計算するが，正しい結果を得るに$G_{p}$

は，すべてが lucky でなくてはならない．change-of-order 型のように，lucky な素数が予め分かっている場合には問題ない．

一方，一般の場合，すなわち， の特別な情報を持っていない場合，には計算した中からより分ける必
$I$

要がある．
(同値類) に分ける．すなわち，$\mathcal{G}=\{lp(G_{p_{1}}), \ldots,lp(G_{p_{k}})\}$を計算した結果とするとき， をに対して，$lp(G_{p})$$\mathcal{G}$が一致する部分集合
により定義する関$G_{p}\cong G_{q}\Leftrightarrow lp(G_{p})=lp(G_{q})$$G_{p},G_{q}\in \mathcal{G}$係は同値関係となる．そこで，この同値関係による類別を$\mathcal{G}=\mathcal{G}_{1}\cup\cdots\cup \mathcal{G}\ell$とする．この中から正しい. を選択する必要がある．Lemma 3 より lucky. でない素数は有限個しか$\mathcal{G}_{*}$

ないので，heuristic な方法としては，各のうちで一番要素数 (cardinality) が多いものが選択される．(DELETEUNLUCKYPRIMESSB in [4] などを参照)
より精密な評価法として以下をあげておく．

(1)

$I$

$\mathcal{G}_{i}$が斉次イデアルの場合には，Hilbert fimction を比べ，他より真に大きいものは unlucky であり，捨てることになる．

(2)

$I$

が一般のイデアルの場合には，各 : の中から代表をとり，斉次化イデアル$\mathcal{G}$のグレブナー基底を計算して，その$H$$\langle F^{h}\rangle$に対する $lp(F^{h})$皿 bert function を求め，他より大きいものは unlucky と見なす．

(2) Hensel Lifting 型: この方法は多項式の因数分解には効果的であったが，グレプナー基底の持ち上げには，グレブナー基底の各元の元の生成集合による表現が必要であり，ここに問題がある．また，
CRT 同様に優れた係数評価が重要であり，特に，結果の正当性評価をするためには，どこまで血舳 ing
するかを決める必要があり，ここには，精度の高い係数評価が必要になる．この設定にも，heuristic が入ることになるが，u 回 ud 素数を選んでしまった場合の処理が無駄になる．
$\mathfrak{h}$(3) 混在型 : 混在型には，グレブナー trace 法 [12] や Hilbert driven 法 [13] がある．以下では，イデア
ルとする．
の生成集合を $F$ とし，項順序を$I$$\prec$グレブナー TRACE 法: グレブナー基底計算において，modp で簡約されるものとみなしてグレブナー基底の候補

レブナー基底であることを確認することで，$G_{can}$

方法である．これは，$\phi_{p}(G_{can})$$G_{can}$

は

$F$

と

$\prec$

これに対して

( -1)
$T$

$p$

$G_{can}$$0$に簡約されるものは

をつくり，

$G$

が正しい

$I$

が $I_{p}(F)$ のグレブナー基底$n\supset I$。

と$G_{can}$$\mathbb{Q}$が上でも$\langle G_{\infty n}\rangle$

$0$

に

のグ

のグレブナー基底であることを保証する$G_{p}$に一致することを意味し，結果としてに対して rGr\"obner basis candidate であることに注意する．

mpatible 型の方法を適用することで，以下の改良が可能となる．

$\infty$$G_{can}$ がが予め compatible であれば，Corollary 1 より，$\langle G$$n\rangle$。

のグレブナー基底である検査

を $\phi_{p}(G_{can})$ が $I_{p}(F)$ のグレブナー基底であることの検査に置き換えることができる． mpatible$\infty$の条件は，例えば，Corollary 2 のように， がある別の項順序での場合，つまり chmge of order 型の場合に適用できる．
$F$

HILBERT DRIVEN 法: $F$ を斉次イデアルとし，項順序場合に，各非負整数 に対する$\prec$$I$のグレプナー基底であったを考える．Hilbert function$s$$HF_{l}(s)=\dim_{Q}(\mathbb{Q}[X][s]/I[s])=dimQ\mathbb{Q}[X][s]-\dim_{Q}I[s]$$HF_{I}$

が既知の

47
は
上の次数 の斉次式全の情報を用いてグレブナー基底を計算する方法である．ここで，を表すものとする．([1] の記号を使う．) 想定される場合は change of
体を表し，$\mathbb{Q}[X][s]$$s$$\mathbb{Q}$$I[s]=-I\cap \mathbb{Q}[X][s]$order 型の場合である．まず比較的計算しやすい順序でグレブナー基底 を計算しておけば，
が
に対して
なら
な素数
lucky
計算でき，(さらに，Hilbert lucky である．)
法を応用して
ここでも，traceを利用することができる．すなわち， の luckyness を計算途中で判定しながらすすめる．$HF_{I}\leq HF_{I_{p}(F)}$ , つまり dimq $I[s]\geq\dim_{F_{p}}I_{p}(F)[s]$ であるので，以下を行う
ことができる．(Traverso [13] とは若干異なる形で書く．)
$G$

$G$

$p$

$p$

( -1) trace 法での計算中の$H$$HF_{I}$$p$

次の元の導出において，丁度 dimq $I[s]$ 個現れなければ は Hilbert
unlucky となる．( $modp$ で に簡約された中に， にならないものがある．) この場合に， を
$s$

$P$

$0$

$0$

$p$

動的に取り換える． はいままでの計算途中で現れた多項式の先頭係数を割らないものとする．
$p$( -2) さらに計算された次数 の元の個数が dimq $I[s]$ に一致した時点で，今後の次数を導出する計算を止めることができる．
$H$

$s$

$s$

の可能な元

さらに，Lemma 6 を使うことで以下を使うこともできる．
( -3) 最後まで計算できた場合に，$H$$\phi_{p}(G$

$n)$

。

ブナー基底になる．(つまり，Gcan がが $I_{p}(F)$ のグレブナー基底であれば，$G_{can}$ は $I$ のグレ$\langle G_{can}\rangle$のグレブナー基底であること，$\langle G_{can}\rangle\supset I$の確認は不要となる．)

Lemma 11 ( -3) が正しいこと．すなわち，最後まで計算できた場合に， ( 。an) が $I_{p}(F)$ のグレブ
はのグレブナー基底になる．
ナー基底であれば，$H$$\phi_{p}$$G_{can}$

5

$G$

$I$

さらなる計算における luckyness の応用重要なイデアルの操作においても modular 計算が有効に適用できることを示す．ここでは，イデア

ル商売，saturation, 根基計算を取り上げる．これらは，イデァル分解に重要な役割を果たすもので，これらを有機的に組み合わせることで，イデアル分解の効率化が期待される．

5.1

イデアル商と saturation への応用

まず最初に，イデアル商計算における luckyness について考える．(Theorem 2.8 in [8] を復習する．)
ここで， の生成集合 と compatible な素数 の組が必要になるが， を項順序 に対する のになるような を取ればよい．
簡約グレブナー基底であって，
$F$

$I$

$F$

$p$

$F\subset \mathbb{Z}_{p}^{0}[X]$$p$

Lemma 12 (Theorem 2.8 in [8])をイデアル の生成集合とし，素数mpatible とする．(項順序を固定して lucky としてもよい．) さらに，多項式 は$I$$F\subset \mathbb{Q}[X]$$\infty$$f$$\phi_{p}(f)\neq 0$$\phi_{p}(H)$とする．多項式集合$H\subset \mathbb{Z}_{p}^{0}[X]$$I$$\prec$で $H$ の各元の項順序$\prec$$p$

は $F$ に対して$\mathbb{Z}_{p}^{0}[X]$に関する主係数が

$p$

の要素で

で割れず，

が $(I_{p}^{0}:\phi_{p}(f))$ のに関するグレブナー基底であり，$H$ は $(I:f)$ のグ$H\subset(I:f)$ であれば，レブナー基底である．
$\phi_{p}(H)$ が$(I:f)$ のグレブナー基底の候補 $H$ として，$(\langle\phi_{p}(F)\rangle:\phi_{p}(f))$のグレブナー基底であるも$H\subset(I:f)$ をチェックし，これがのがあったとする．(CRT などで構成すると仮定する) このとき，$OK$ であれば $H$ が$H$ の各元$(I:f)$ のグレブナー基底であることが保証される．このチェックは，$NF_{F}(hf)=0$ となるかどうかのみを調べればよい．
対して，

$h$

に

48
イデアル商 $(I :f)$ の計算はの計算に帰着されるが，この計算に対して，同様の方法が適用$I\cap\langle f\rangle$

できる．

Lemma 13の生成集合とし，素数 は に対して compatible とする．(ははの要素でのグレブナー基底としてもよい．) さらに，多項式$F\subset \mathbb{Q}[X]$

じめから $F$ を$I$$\prec$

$I$

$F$

$P$

$f$

とする．多項式集合
順序

をイデアル

$H\subset \mathbb{Z}_{p}^{0}[X]$

で $H$ の各元の主係数が $p$

に関するグレブナー基底であり，$H\subset I\cap\langle f\rangle$

で割れず，

が

$\phi_{p}(H)$

であれば，

は

$H$

$\phi_{p}(f)\neq 0$$\mathbb{Z}_{p}^{0}[X]$$I\cap\langle f\rangle$$\langle\phi_{p}(F)\rangle\cap\langle\phi_{p}(f)\rangle$の項のグレブナー基底である．

イデアル商を繰り返す操作により saturation が計算できるので，上の補題は saturation に関して拡張される．(直接証明もできる．)

Lemma 14

$F\subset \mathbb{Q}[X]$

らに，多項式

$f$

$H$

は

をイデアル

$p$

で割れず，

$\phi_{p}(H)$であれば， は$H$

$H\subset(I:f^{\infty})$$P$

は $F$ に対して compatibleの要素で $\phi_{p}(f)\neq 0$ とする．多項式集合$\mathbb{Z}_{p}^{0}[X]$の各元の主係数がの生成集合とし，素数$I$$(I:f^{\infty})$が$(\langle\phi_{p}(F)\rangle:\phi_{p}(f)^{\infty})$の$H\subset \mathbb{Z}_{p}^{0}[X]$$\prec$

で項順序

とする．さ
$\prec$に関するに関するグレブナー基底であり，のグレブナー基底である．

Remark 2. CRT 型の場合には，ここでの modular 計算が有効に働くことが予期される．( : f) の計の中, や $(I:f^{\infty})$ の計算においては，slack variable を導入して，算，すなわちのや
ehmination
で elimination orderの下で，それぞれ$yF=\{yf|f\in
F\}$
とする．)
を
の生成集合とし，
ideal のグレブナー基底の計算を行う．(ここで，$F_{p}[X]$ での elmination ideal のLemma 12, 13, 14 では， 上での計算では，
で計算し，
$I$

$\mathbb{Q}[X\cup\{y\}]$$y$$I\cap\langle f\rangle$$X\prec\prec y$$F$$H_{p}$$I$$\mathbb{F}_{p}[X\cup\{y\}]$$F_{p}$

グレブナー基底として$\langle F\cup\{yf-1\}\rangle$$\langle yF\cup\{(1-y)f\rangle$を計算するが， 上で構成する$\mathbb{Q}$$H_{can}$においては，$\mathbb{Q}[X\cup\{y\}]$での対応するグレブナー基底を構成するわけではなく， に対応するものだけである．これは，次に説明するイ$H_{p}$

デアルの和 (Lemma 15) においても同様である．

5.2

イデアルの交わりへの応用

イデアルの交わりへの応用を 2 種類与える．つまり，(1), 2 つのイデアル $A,$ $B$ が与えられたときに $I=A\cap B$ のグレブナー基底を計算する場合(2) イデアル$I$が与えられ，$I=A\cap B$ となるとき，$A,$ $B$のグレブナー基底を計算する場合を考える．(1) は Lemma 13 の一般形といえるものであり，compatible 型で示される．
Lemma 15

る．素数

$p$

$F_{A}\subset \mathbb{Q}[X]$

は $F_{A},$$F_{B}$

をイデアル $A$ の生成集合とし，$F_{B}\subset \mathbb{Q}[X]$をイデアル $B$ の生成集合とすに対して compatible とする．(はじめから，は $A,$ $B$ のある項順序に関$F_{A},$ $F_{B}$するグレブナー基底としておいてもよい．)$\phi_{p}(H)$が$\langle\phi_{p}(F_{A})\rangle\cap\langle\phi_{p}(F_{B})\rangle$の項順序$\prec$に関するグレ$H\subset A\cap B$のグレブナー基底である．(ここで，ブナー基底であり，であれば，の判定には，
がそれぞれのグレブナー基底であれば，それらに関する正規形を計算するこ とで$H\subset A\cap B$$H$

は $A\cap B$$F_{A},$ $F_{B}$$\acute{}$判定できる．)
次に (2) の場合を示す．イデアルる場合に，その成分砺，$B_{p}$$I$

が $modp$ において 2 つのイデアルに対応するイデアル $A,B$

証するものである．応用として，$A_{p},$ $B_{p}$が存在した場合に，$I=$ $(I:f^{\infty})\cap(I+\langle f^{k}\rangle)$の交わりになっていとなることを保$I=A\cap B$の分解が想定される．

49
Lemma 16

$G\subset \mathbb{Q}[X]$

であって，

$G$

$G\subset \mathbb{Z}_{p}^{0}[X]$をイデアル $I$ の項順序の$\prec$に関するグレブナー基底を$\prec$る先頭係数は$p$に対する先頭係数$G_{A},$ $G_{B}$

$P$

とし，

で割れないとする．つまり，$P$$\phi_{p}(G_{A})$は$\phi_{p}(A\cap \mathbb{Z}_{p}^{0}[X])$

ナー基底である．)

5.3

$p$

として，

で割れないものとする．2 つのイデアル $A,B$ の$G_{A},$ $G_{B}\subset \mathbb{Z}_{p}^{0}[X]$

であって，

の各元の

$G_{A},$ $G_{B}$$\prec$に対すは $G,$ $G_{A},$ $G_{B}$ に対して lucky$\langle\phi_{p}(G)\rangle=\phi_{p}(I\cap \mathbb{Z}_{p}^{0}[X])=\langle\phi_{p}(G_{A})\rangle\cap\langle\phi_{p}(G_{B})\rangle$

る．(ここで，に対するグレブナー基底とし，素数$\prec$であって，$I\subset A\cap B$のグレブナー基底であり，$\phi_{p}(G_{B})$であるとする．さらに，とするとき，$I=A\cap B$ であは$\phi_{p}(B\cap \mathbb{Z}_{p}^{0}[X])$のグレブ

根基計算への応用
で生成されるイデアル

$F$

$I$

の根基

$\sqrt{I}$の計算に modular 法を導入する．一般の方法では，斉次元成分に分割し，0 次元化して各変数の最小多項式を計算し，それを無平方分解することが基本である．
ここでは，このアプローチとは別に，modular での根基計算を利用した方法を のグレブナー基底がすでに求まっている場合に与える．そこで，各素数 として と項順序 に対して lucky な
$I$

$G$

$P$

ものをとり，modular 法により，各有限体$H_{can}\subset \mathbb{Z}_{p}^{0}[X]$を計算する．

$(\phi_{p}(H_{can})=H_{p}$Lemma 17 (cf. Theorem 5.5 in [5])なわち，

$H_{can}$り，$H_{can}$は$F_{p}$の各元$\sqrt{I}$

$h$

$G$

$\prec$

上で $\sqrt{I_{p}(G)}$ のグレブナー基底$H_{p}$

を計算し，これから

となる．
$)$

$J=\langle H_{can}\rangle$

とおく．さらに，$NF_{G}(h^{k})=0$ となるに対して，$H_{can}\subset\sqrt{I}$$k$であるとする．す$J=\sqrt{I}$ であが存在するとする．このとき，のグレブナー基底となる．

参考文献[1] E.Arnold, Modular algorithms for computing $Gr6bner$ bases, J.Symb.Comp. 35, $403\cdot 419$ , 2003.

[2]
[3]

$H$

.-G. Gr\"abe, On lucky primes, J.Symb.Comp. 15, 199-209, 1993.

.-M.Greuel, G.Pfister, A Singular Introduction to Commutative Algebra, Second Edition,
Springer-Verlag, Heidelberg, 2008.
$G$[4] N.Idrees, G.Pfister, S.Steidel, Parallelization of modular algorithms, J.Symb.Comp.46, 672-684,$201i.$[5] 門田めぐみ，modular 計算による多項式イデァルの分解アルゴリズム，神戸大学大学院理学研究科

修士論文，2009.
[6] M.Kreuzer, L.Robbiano, Computational Commutative Algebra 2, Springer-Verlag, Heidelberg,

2005.
[7] M. Noro, Modular Algorithms for Computing a Generating Set of the Syzygy Module, Proc.

CASC2009, LNCS 5743, Springer, 259-268 (2009).
[8] M.Noro, K.Yokoyama,
modular method to compute the rational univariate representation,
J.Symb.Comp.28, 243-263, 1999.
$A$[9] F.Pauer, On lucky ideals for $Gr6bner$ bases computation, J.Symb.Comp.14, 471-482, 1992.

50[10] V. G. Romanovski, X. Chen, Z. Hu, Linearizability of linear systems perturbed by fifth degree
homogeneous polynomials, J. Phys : Math. Theor. 40, 5905-5919, 2007.
$A$[11] V.G.Romnovski, M.Presern, An approach to solving systems of polynomials via modular arithmetics with applications, J. Computational and Applied Mathematics 236, 196-208, 2011.
[12] C.Raverso, Gr\"obner trace algorithms, ISSAC ‘S8, LNCS 358, 125-138, 1989.
[13] C.Ttaverso, Hilbert functions and the Buchberger algorithm, J.Symb.Comp.22, 355-376, 1997.

[14] F.Winkler, $Ap$-adic approach to the computation of Gr\"obner bases, J.Symb.Comp.6, 287-304,

1988.