数理解析研究所講究録
第 1652 巻 2009 年 182-191

182

ブール多項式環における消去イデアルの計算について
SHUTARO INOUEAKIRA NAGAI

東京理科大学

理学研究科

東京理科大学

秀太郎

井上

彰

永井

理学研究科

TOKYO UNIVERSITY OF SCIENCE \dag er

TOKYO UNIVERSITY OF SCIENCE*佐藤洋祐

YOSUKE SATO

東京理科大学TOKYO UNIVERSITY OF SCIENCE \d ag er

1

はじめに
グレブナー基底 (Gr\"obner basis) は代数方程式を解く強力なツールになっている. BBuchberger は係数が体における多項式環にグレプナー基底を導入したが, 係数が体でない環におけるグレブナー基底についても多くの研究がある. その中の 1 つとして係数をプール環とする多項式環上のグレブナー基底 (Boolean

Gr\"obner bas 色) が Sakai, K と Sato, Y によってプール方程式を解くために導入され, 非常に優れた特性をもっている. 以下では簡単のために,

プール多項式環,$\overline{A})$に対して,$B(\overline{x},dI)$$I\cap B(\overline{A})$けて 2 つの方法がある.
$\overline{X}>>\beta$$\vec{X}=X_{1},$$\ldots,$$X_{n},\overline{A}=A_{1},$$\ldots,$$A_{m}$と表すことにする.

上における消去イデアル (elimination ideal) とは, 与えられたイデアルで定義される$B(\overline{A})$$I\subset B(\overline{X}$のイデアルである. 消去イデアルを計算するには, 大きく分

1 つは, (純) 辞書式順序 $X_{1}>$. .. $>X_{n}>A_{1}>$ . . . $>A_{m}$ やブロック順序のもとでブーリアン. グレブナー基底を計算する素朴な方法であり, もう 1 つは,$\vec{A}$をパラメータとして包括的ブーリアン. グレブナー基底を計算し, そこから消去イデアルを構成する方法である. 包括的ブーリアン・グレブナー基底を計算する方法としては, 変数 X, 五に対してブロック順序 $X>>B$ のもとでブーリアン・グレブナー基底を計算する方法と, 変数

項式環$(B(\lambda))(X)$$\overline{A}$からなる係数ブール環$B(\overline{A})$をもつブール多上でブーリアン. グレブナー基底を計算する方法がある. 一般的に, 後者は前者よりも理論的に優れているが, 計算効率が悪くメモリの消費も大きいため, 前者よりも効果は期待できない.

本研究では, 後者を求めるアルゴリズムの改良として, プール多項式環 $B(B,\overline{X})$ 上において与えられた
イデアル$I=\langle fi(\lambda,\overline{X}),$$\ldots$,fi$(\lambda,\overline{X})\rangle$

に対し, 変数$\lambda$に $0,1$ のビット列$\overline{c}$を宛がうことで, イデアル全のブーリアング
上のイデアルのみからなるブール多項式環$I\capB(B)$を構成できる新しい方法を提唱した. また, 数式
レブナー基底を計算し, そこから消去イデアル
処理システム RISA $/ASIR$ を用いてこのアルゴリズムを実装し, その有効性を示した.

体ではなく$B(\overline{X})$$\overline{X}$hagaiOmi. kagu. tus. ac.jp\dagger inoueOmi.kagu. tus. ac.jp$\_{y\epsilon atoOmi.hgu}$. tus. ac.jp$(fi(\overline{c},\overline{X}), \ldots, fi(\overline{c},\overline{X}))$

183
2

ブール多項式環

定義 1

単位元 1 をもつ可換環 $B$ が以下の性質を持つとき, これをブール環とよぶ.
$\forall x\in Bx^{2}=x$上の性質から次の性質もすぐに示される.
$\forall x\in Bx+x=0$

証明 $x+x=(x+x)^{2}=x^{2}+x^{2}+x^{2}+x^{2}=x+x+x+x$ となり,
$x+x$ をひく.

$x+x=x+x+x+x$ の両辺から1

このように, ブール環上では $x=-x$ なので一記号を使う必要はないが,の意味を強調したいときにはーを用いることにする. また, ブール環の半順序を表すために記号 を用いる. 例えば, ブール環 $B$ の–$\succeq$

要素 $a,$

に対して,

$b$

$a\succeq b$

は $ab=b$ を意味する。 ブール環の例を以下に挙げる.

例1$B=GF_{2}$ とすると, $B$ はプール環となる.

例2$B=GF_{2}xGF_{2}$ とすると, $B$ はプール環となる.

一般的に $B$ の
例

$k$

個の直積

$B^{k}$

はブール環になる.

$S$

をプール環,

を自然数とする. 直積
は $B$ の要素を取り出して個からなる組を元とした集合であるの要素 $p$ にたいして, $p:\in B$ を $p$ の 番目 $(i=1, \ldots, k)$ の要素を表すのに用いることにする. $p,$ $q\in B^{k}$にたいして, 和と積の演算 $p+q,p\cdot q$ を $(p+q)_{i}=p_{i}+q\iota,p_{i}\cdot q_{i}(i=1, \ldots, k)$ で定義することによって,

$B$

.

$k$

$B^{k}$$B^{k}$$k$$i$$B^{k}$

はプール環になる.
例4集合の族は以下の演算でプール環になる.
$x,y\in B$ とし, $+$ と. を次のように定義する.

x

$+$

y

$=$

$($

あ $\cap y)\cup(x\cap\overline{y}),$ $x\cdot y=x\cap y,$ $1+x=\overline{x}$定義 2プール環 $B$ の
素は$\succeq$

$0$

でない要素

に関して,

$0$

$e$

.

ここで,x-は $x$ の補集合を表す.

が以下の性質を満たすとき,

補題 3$B$ を有限プール環とし,べてのアトミックな要素

$B$

$0$

でない要素

$c$

が存在しない.

が少なくとも 1 つのアトミックな要素を持っているとする. このとき,$e_{1},$$\ldots,$$e_{k}$$B$のすに対して, $eiej=0(i\neq j)$ と $e_{1}+e_{2}+\ldots+ek=1$ が成り立っ.

証明 $eiej=0$ は自明. 最後の等式を示す.
$c$はアトミックであるとよぶ. (アトミックな要でない最小の要素である)$c=e$ の場合を除き, $ce=c$ となる

今$e$とする. っまり,$e_{1}+\ldots+e_{k}+1\neq 0$ とする.
を $e_{1}+\ldots+ek+1\succeq c$ を満たす $B$ の最小要素 (アトミックな要素) とすると, $c(e_{1}+\ldots+e_{k}+1)=c$

これは s$e_{1}+\ldots+e_{k}\neq 1$.

$c(e_{1}+\ldots+e_{k})=0$ を意味する.

が最小要素 (アトミックな要素) であるので, あるて $c=e_{i}$ となり, $e_{i}(e_{1}+\ldots+e_{k})=0$ より $e_{i}=0$ が導かれの定義に矛盾する.
$c$$e_{i}$$e_{i}$

に対し

I

184
定養 4
$B$

をプール環とする. イデアル$\langle X_{1}^{2}-X_{1},$$\ldots,$$X_{n}^{2}-X_{n}\rangle$

による剰余環 $B[X_{1}, \ldots, X_{n}]/\langle X_{1}^{2}-X_{1},$この剰余環をプール多項式環 (boolean polynomial ring) とよび,はプール環になる.

$\ldots,$$X_{n}^{2}-X_{n}\rangle$$B(X_{1}, \ldots, X_{n})$と表記する. また, プール多項式環の要素をプール多項式とよぶ.
プール多項式環は, 一般の体とは異なる性質をもつ. ブール多項式環における任意のイデアルは主イデア

ノレナ $in$ 吻
ついては,i&al になる. つまり,$l$$\langle f1,$$)$

$f_{i}=f_{i}\cdot(fi\cup f_{2}\cup\ldots\cup f_{n})$$f_{2}\ldots,$ $f_{n}\rangle=\langle fi\cup f_{2}\cup\ldots\cup f_{n}\rangle$となる.

は明らかである.

$\supseteq$$\subseteq$に

このように, ブーノレ多項式環におけるすべてのイデアル は 1

である.

$|$

つの多項式で生成されるイデアルと一致する.
例5{X, $Y\rangle=\langle XY+X+Y\rangle=\langle X\cup Y\rangle$$B(X_{1}, \ldots,X_{n})$表現される.

$X_{1},$

ギリシャ文字の要素を$\overline{a}$$\alpha,$のプール多項式は, 各変数$\ldots,$$\beta,$$\gamma$$X_{n}$

3$B(\overline{Y})$$Y_{1},$$\ldots,$$Y_{m}$

をベキ等にした $B[X_{1}, \ldots, X_{n}]$ の多項式によって一意的にをそれぞれと表すことにする. また, 単項を表す記号として$\vec{X},\overline{Y}$等を, ブール環 $B$ の要素を表す記号として $a,$ $b,$で表す。 例えば,$(a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{m})$たと$X_{i}$$\vec{a}=(a_{1}, \ldots,a_{n}),\overline{b}=(b_{1}, \ldots, b_{m})$となる. 変数$\vec{X}$と$\overline{Y}$

とし,

$c$

等を, ある $n$ に対して $B$ の $n$ 組$(\overline{a},\overline{b})$は $n+m$ 組の要素からなるからなるブール多項式に対して,$f(\overline{a},\overline{Y})$は$\overline{X}$に$\overline{a}$を代入し上のブール多項式を意味する.

ブーリアングレブナー基底
ブーリアン. グレブナー基底は係数ブール環上の多項式環におけるグレブナー基底から計算可能である.

このセクションでは前半は$B[\overline{X}]$上のグレブナー基底について説明し, 後半部分で,基底 (プーリアングレブナー基底) を説明する. また,$B[X_{1}, \ldots,X_{n}](B[\overline{X}])$$B(\overline{X})$

f-LM $(f)$ を

単項を $LT(f)$ , その係数を $LC(f)$ , 最大の単項式すなわち $LC(f)LT(f)$ を $LM(f)$ ,さらに $LT(F)$ と $LM(F)$ を集合 $\{LT(f)|f\in F\}$ と $\{LM(f)|f\in F\}$ (

で表す.

,

$T(\overline{X})$を変数$\overline{X}$上のグレブナ–の多項式に対して, 最大の$Rd(f^{:})$

は $B[\vec{X}]$ の部分集合)$F$からなる単項を表すために用いる.

定義 5
多項式環
$I$

$B[\overline{X}]$のイデアル $I$ に対して,$I$の有限部分集合 $G$ が $\langle LM(I))=\langle LM(G)\rangle$ を満たすとき,$G$をのグレブナー基底とよぶ.

定藤 6
に対して,

$f\in B[\overline{X}]$$a=LC(f),t=LT(f),$ $h=Rd(f)$ とする.

$f$によるモノミアル

リダクション $arrow f$ を以下で定義する.
尻 $s+parrow f$ (l-a) 尻 $s+absh+p$.

注: $(bts+p)-((l- a)bts+absl+p)=bs(af)$ である.
$s\ovalbox{\tt\small REJECT}hT(\overline{X})$

たいして,

の単項,

$b$

$garrow Fg’\Leftrightarrow$

は $ab\neq 0$ を満たす $B$ の要素,

$p$

が有限で,

列 $g_{1},g_{2},$$\ldots$$arrow F$$B[\overline{X}]$の任意の多項式の場合, 集合$F\subseteq B[\overline{X}]$にある $f\in F$ にたいして $garrow fg’$

定理 7
$F$

は

がネーター的であるとき, 各 i $=$ 1,2.

は存在しない.

. .. にたいして t$g_{i}arrow F$$g_{i+1}$をみたす多項式の無限

185
定理 8
$I$

を多項式環

$0$

は同値である.

$B[\overline{X}]$のイデアルとする.

$I$の有限部分集合 $G$ が$I$のグレブナー基底であることと, $\forall h\in Iarrow G*$

定義 9
グレブナー基底 $G$ にたいし, $G$ の任意の要素 $f$ が自分以外の $G$ の要素によるモノミアルリダクションによって書き換えられないとき, $G$ を既約グレブナー基底とよぶ.
例6$B=GF_{2}\cross$

GF とする. 多項式環 $B[X]$ で, $\{(1,0)X, (0,1)X\}$ と $\{(1,1)X\}$ は同じイデアルの既約グレブ

ナー基底である.

グレブナー基底を一意に求めるために, もう一つ定義を導入する.
定養 10

既約グレブナー基底 $G$ がさらに以下の性質をもつとき $G$ を正規グレブナー基底とよぶ.
$G$の二つの要素で、 最大単項が一致するものはない.

定理 11

正規グレブナー基底はユニークに定まる. すなわち,$\langle G\rangle=(G’\rangle$

なる正規グレブナー基底 $G$ と $G’$ は一致しなければならない.
上の例において,$\{(1,1)X\}$ は正規グレブナー基底であるが,もう一方は正規グレブナー基底ではない.

定鵜 12

多項式 $f$ が, $LC(f)f=f$ をみたすとき, $f$ はプール閉であるという. $lc(f)f$ を $f$ のブーノレ閉包とよび, 加 (f)で表す. (注意 任意の多項式のブール閉包はブール閉である)
定理 13
$G$

をイデアル $I$ のグレブナー基底とする.

このとき,$\{bc(g)|g\in G\}\backslash \{0\}$もまた $I$ のグレブナー基底となる.

体上の多項式環と同様に $S$ 多項式を定義する.
定義 14$a=LC(f),b=LC(g),tr=LT(f),$ $sr=LT(g)$ とし, $GCD(t, s)=1$ をみたす単項
多項式 $f,g$ を $f=atr+f’g=bsr+g’$ とする. つまり,

$bsf+atg=bsf’+atg’$ は

$f$

$t$

と

$s$

$t,$

$s,r$ にたいしては共通の変数をもっていな$V^{a}$. 多項式と $g$ の $S$ 多項式 (S-polynomial) とよび, $S(f,g)$ で表す.

体上の多項式環と同様に次の定理はグレブナー基底の計算に非常に重要である.
定理 15. $G$ をプール閉である多項式の有限集合とする.

任意の多項式$f,$

このとき $G$ がプーリアン. グレブナー基底であることは,$g\in G$ にたいして $S(f\}g)arrow 00*$ が成り立っことと一致する.

与えられた有限集合 $F$ にたいして, ブール閉包と $S$ 多項式を計算することで,のグレブナー基底を計算することができる. また, グレブナー基底から正規グレブナー基底を求めることは容易である.
$(F\rangle$

186
アルゴリズム 1$BC$$input:B[\overline{X}]$output:の有限部分集合 $F$$\langle F’\rangle=(F\rangle$

をみたすブール閉な多項式の集合 $F’$

$F’arrow\emptyset$

do
while
select from $F$$F\neq\emptyset$$f$$Farrow F\backslash \{f\}$while $f\neq 0$ do$F’arrow F’\cup\{bc(f)\}$$farrow f-bc(f)$

end

end
アルゴリズム 2
$BG$

basis

$input:B[\overline{X}]$の有限部分集合 $F$ と,output:項順序 $>$ における$\langle F)$$T(\overline{X})$の項順序 $>$のグレブナー基底 $G$$Garrow BC(F)$$Barrow\{\{g_{i},g_{j}\}|g_{i},g_{j}\in Gwithg_{i}\neq g_{j}\}$

whil

do
select $\{g_{i},gj\}$ from $B$$eB\neq\emptyset$$Barrow B\backslash \{\{g_{i},g_{j}\}\}$$S(g_{i},g_{j})arrow ch*$if $h\neq 0$ then$Barrow B\cup\{\{g, h\}|\forall g\in G\}$

$Garrow G\cup BC(\{h\})$end
ここからはブール多項式環におけるグレブナー基底 (ブーリアングレブナー基底) の説明に入る. 読者とはで混乱しないように注意されたし. ブール環の要素はすべてベキ等なので, プール多項式$B[\overline{X}]$$B(\overline{X})$環においても上のアルゴリズムは機能する.
$l_{i}$

が $0$ か 1 であるならば, 項$X_{1^{1}}^{l}\ldots X_{n^{n}}^{l}$

プール多項式環においてもグレブナー基底を定義できる. 各はプール単項 (boolean p

product) という. 変数又からなる上のプール多項式 f(又) は以下のようにユニークに表$\alpha ver$で表す.
すべてのブール単項の集合を$B$
を用いて, $f(X)=b_{1}t_{1}+\ldots+b_{k}t_{k}$ と一意表現できる.と異なるブーノレ単項の要素のは現できる. $b_{1}t_{1}+\ldots+b_{k}t_{k}$ をの標準表現 (canonical representation) とよぶ.
部分集合なので,
は,
におけ
上の項順序
上でも同様に定義できる. 与えられた項順序$BT(\overline{X})$$b_{1},$$B(\overline{X})$$\ldots,b_{k}$$t_{1},$$\ldots,$$t_{k}$$BT(\overline{X})$$f(\overline{X})$$T(\overline{X})$$\geq$$T(\overline{X})$$BT(\overline{X})$$|$$\geq$のなかの最大ブーノレ単項ちを $f$ の先頭ブー’ レ
は $f$ の先単項とよび, $BLT(f)$ で表し, biti を $f$ の先頭プール単項式とよび, 記号 $BLM(f)$ を用いる.
頭プール係数とよび $BLC(f)$ で, $f-BLM(f)$ を $BRd(f)$ で表すことにする. また, プール多項式の集合
るブーノレ多項式 $f=b_{1}t_{1}+\ldots+b_{k}t_{k}$ にたいして,$t_{1},$$\ldots,t_{k}$$b_{i}$$F$にたいして同じ表記 $BLT(F)$ と $BLM(F)$ を用いることにする.

187
定義 16

ブール多項式環 $B$ (刃) のイデアル にたいして,の有限部分集合 $G$ が $\langle BLM(I)\rangle=\langle BLM(G)\rangle$ を満た$G$すとき,を のブーリアン・グレブナー基底とよぶ.
$I$

$I$

$I$

定理 17
$I$

をブール多項式環

ることと,のイデアルとする.
は同値である.

$B(\overline{X})$$\forall h\in Iarrow_{G}0*$$I$の有限部分集合 $G$ が$I$のプーリアン. グレブナー基底であプール多項式環のプール閉包も同様に定義できる.
定義 18(ブーノレ閉) 多項式 $f$ が, $BLC(f)f=f$ をみたすとき, $f$ はブーノレ閉 (boolean dosed) であるという. $BLC(f)f$ を $f$ のブーノレ閉包 (boolean dosure) とよび, $bc(f)$ で表す. である.
定理 19
を $I$ のプーリアン・グレブナー基底とする.

$G$

このとき,

$\{bc(g)|g\in G\}\backslash \{0\}$もまた $I$ のブーリアン・グ

レブナー基底となる.

定義 55 のように, ある項順序においてユニークに定まる正規ブーリアン. グレブナー基底を定義でき

ブーリアングレブナー基底の計算はいたってシンプルである. プール多項式の有限集合が与えられたとする.
においてイデアル $\langle F\cup\{X_{1}^{2}-X_{1}, \ldots, X_{n}^{2}-X_{n}\})$ のグレブナー基底 $G$ を計算する. $G\backslash \{X_{1}^{2}-X_{1}, \ldots,X_{n}^{2}-X_{n}\}$ がにおけるのプーリアン. グレブナー基底である. また.
る.

$F\subseteq B(\overline{X})$$B[\overline{X}]$$B(\overline{X})$$G$

が正規グレブナー基底であるとき,$\langle F\rangle$$G\backslash \{X_{1}^{2}-X_{1}, \ldots, X_{n}^{2}-X_{n}\}$もまた正規ブーリアン・グレブナー基

底である.

をプール環,

を自然数とすると, 直積
はブール環になる.
の要素 にたいして, $p_{i}\in B$ を の 番
目 $(i=1, \ldots, k)$ の要素を表すのに用いることにする.
[又] 上の多項式 f(又) にたいして$ $f_{i}(i=1, \ldots, k)$ を $f$ の係数 を に置き換えることにより得られる $B[X]$ 上の多項式とし, Bk(又) 上の多項式にたいしても f(又) を
$B$

$k$

$B^{k}$$B^{k}$

$p$

$P$

$i$

$B^{k}$$P$$p_{i}$

同様に定義する.
定理 20

多項式環

$B^{k}[\overline{X}]$

において,

$G$

ナー基底であることと, $i=1,$
既約)をブール閉な多項式の有限集合とする. このとき,$\ldots,$

$k$

$G$

が $I$ の (既約) グレブ

にたいして $G_{i}=\{g_{i}|g\in G\}\backslash \{0\}$ が $I_{j}=\{f_{\dot{*}}|f\in I\}(\subseteq B[\overline{X}])$ の (グレブナーであることは同値である.

系 21

ブール多項式環をブール閉なブール多項式の有限集合とする. このとき, $G$ が $I$ の(既約) グレブナー基底であることと, $i=1,$, にたいして $G_{i}=\{g_{i}|g\in G\}\backslash \{0\}$ が $I_{i}=\{f_{i}|f\in$の (既約) グレブナーであることは同値である.
$B^{k}(\overline{X})$

において,

$G$

$\ldots$$k$$I\}(\subseteq B(\overline{X}))$

4

包括的ブーリアン・グレブナー基底
このセクションでは,単のために, 又 $=X_{1},$いるものとする.

包括的ブーリアン・グレブナー基底を計算する素朴な方法を紹介する. 以下では簡$\ldots,$$X_{n}.\lambda=A_{1},$$\ldots,$$A_{m}$と表すことにする. また,$T(\overline{X})$上に項順序が与えられて

188
定養 22
$F=\{f_{i}(\lambda, X), \ldots, fi (dI, X)\}$

分集合

環 B’ の任意の要素$B’(\overline{X})$がプール多項式環 $B(f,$ 叉 の有限部分集合であるとする.

$\overline{a}$の有限部の包括的ブーリアン グレブナー基底であるとは, $B$ の拡大ブール$)$$G=\{g_{1}(\lambda,\overline{X}), \ldots, g_{k}(\lambda,\overline{X})\}$

にたいして,が$F$$G(\overline{a})=\{g_{1}(a,\overline{X}), \ldots,g_{k}(\overline{a},\overline{X})\}\backslash \{0\}$が$B(\overline{A}, X)$$\langle F(\overline{a})\rangle=\langle f_{1}(\overline{a},X),$$\ldots$, fi$(\overline{a},\overline{X})\rangle\subseteq$のブーリアングレブナー基底になっていることをいう. ここで, B’ は $B$ を部分環とするブール環と $a=(a_{1}, \ldots, a_{m})\in B^{\prime m}$ である. また, 任意の $a=(a_{1}, \ldots, a_{m})\in B^{\prime m}$ にたいして,が正規ブーリア$G(\overline{a})$ングレブナー基底であるとき $G$ を正規包括的ブーリアングレブナー基底とよぶ.

定理 23の有限部分集合であるとする.
がを係数にもつ多項式環 $(B(\lambda))(X)$ とみなし, $G=\{g_{1}(B,$ 愛$F=\{f1(\lambda,\overline{X}), \ldots, fi(\lambda,\overline{X})\}$ノレ環$B(\lambda)$規

5$B(\overline{A},X)$$), ...,g_{k}(\lambda,\overline{X})\}$

けるイデアル ($)$

がプール多項式環$F\rangle$の(正規) ブーリアングレブナー基底になっているとする.

をプ$B(\lambda,\vec{X})$$(B(\lrcorner 4))(\overline{X})$

このとき,

$G$

は

$F$

の

$arrow$-にお(正

包括的プーリアングレブナー基底になる.

消去イデアルを求める新しいアルゴリズム$B(\overline{X})$上のプー ylx 多項式$fi(\overline{X}),$ $f_{2}(\overline{X}),$$\ldots$, fi$(\overline{X})$を生成元とするイデアル$I=\langle fi(\overline{X}),$ $f_{2}(\overline{X}),$$\ldots$, fi$(\overline{X})\rangle$の正規ブーリアングレブナー基底を計算することによって以下の連立方程式を解くことができる.

...

$\{\begin{array}{l}f_{1}(X_{1},X_{2}, \ldots,X_{n})=0:f_{t}(X_{1},X_{2}, \ldots,X_{n})=0\end{array}$(1)

他にも正規ブーリアングレブナー基底を計算することで多くのことを解決できる. 例としてはイデアル所とイデアル にたいしてであるか否かを判定できる$f_{2}(X),$
今の場合では, $(fi(\overline{X}), f_{2}(\overline{X}), \ldots, fi(X))$ と, fi (X),の正規プーリアン. グレブ
ナー基底をそれぞれ計算して両者を比較し一致するかをみればよい. もしくはの正規形 (normal form)$G$を求めればよく,を計算しての正規ブーリアングレブナー
であるか否かをみればよい.

属問題があり, 与えられたプール多項式$I$$h(\overline{X})$$h(\overline{X})\in I$$\langle fi(\overline{X}),$$\ldots$$h(\overline{X}))$$h(\overline{X})$$I$$h(\overline{X})arrow c^{0}r$が (1) のすべての解でになるかどうかも今の方法で硝かめることができる. 他の問題についても正規ブーリアングレブナーを計算することさえできれば, その問題を解くができる. しかし残念ながまた$h(\overline{X})$$0$

ら, 変数が多い場合グレブナー基底の計算は困難である.

いとする.

このとき, 消去イデアル$\langle fi(\overline{X}),$ $f_{2}(\overline{X}),$$\ldots$, fi

今, (1) の 3 変数 $X_{1},X_{2},$$(\overline{X})\rangle\cap B(X_{1},X_{2}, X_{S})$$X_{3}$

だけの解を知りたのプーリアン・グレブナ$\check$-

基底が必要であり, イデアル $I$ 全体のブーリアングレブナー基底は必ずしも必要ではない. また, 3 変
数 $X_{1},$ $X_{2},$$X_{3}$からなる多項式 $h(X_{1},X_{2}, X_{3})$ が (1) の解で$0$になるかの判定に必要なものも, イデアル $I$ 全

体のブーリアン・グレブナー基底ではなく, 上の消去イデアルのブーリアン・グレブナー基底が必要である.

消去イデアルを求める一般的な方法は (純) 辞書式順序 $X_{n}>$$X_{n},$$\ldots,X_{4}>>X_{3},$$X_{2},$ $X_{1}$... $>X_{4}>X_{3}>X_{2}>X_{1}$ やブロック順序のもとでイデアル全体のブーリアングレブナー基底を計算することである.

このセクションでは, イデアル全体のプーリアングレブナー基底を計算せずに, 消去イデアルのブーリ
アン.

グレブナー基底を計算するアルゴリズムを説明する.

補題 24
$I$

を変数

$\lambda$$(B(B)(\vec{X}))$と$\overline{X}$からなるブール多項式環$B(\lambda,\overline{X})$のイデアルとし $G$ を $T(X)$ のある項順序のもとにおける $I$ の正規プーリアングレブナー基底とする. このとき, $G\cap B(B)$ は空集合か $B(A)$ のブール多項式 1 つからなる集合 th $(B)I$ である. 後者の場合, 消去イデアル $I\cap B(\lambda)$ はそうでない場合は消去イデアルは $\{0\}$ となる.

$’$$\langle h(\lambda)\rangle$

と一致し

189
補題 25
ブール多項式環 $B(A_{1}, \ldots, A_{m})$ は直積$1,$$\ldots,$$2^{m}$と $i-1$ の 2 進数表現$B^{2^{m}}$$c_{1}^{\dot{\iota}}\ldots c_{m}^{i}$と同型である. $B(A_{1}, \ldots, A_{m})$ から$B^{2^{m}}$への同型写像$\phi$

は $i=$

を用いて次のように与えられる.

$\phi(f(A_{1}, \ldots,A_{m}))_{i}=f(c:, \ldots,c_{m}^{:})=$

果の逆写像 -1 は$\phi$$\phi$$\phi^{-1}((a_{1}, a_{2}, \ldots,a_{2^{m}}))=\sum_{:=1}^{2^{m}}a_{i}(A_{1}+ci+1)(A_{2}+c_{2}^{:}+1)\cdots(A_{m}+c_{m}^{i}+1)$となる. ( $c_{k}^{1}=0$ のとき $c_{k}^{i}+1=1$ となり, $c_{k}^{i}=1$ のとき $c_{k}^{i}+1=0$ となる)

この補題と系 513 によって新しいアルゴリズムを記述できる.
アルゴリズム 3

ElimBGB$input:B(A,\overline{x})$の有限部分集合 $F$ , パラメーター

output 順順序$>$における消去イデアルの項順序 $>$のグレブナー基底 $G$$\overline{A}_{1}T(\overline{A})$$\langle F\rangle\cap B(B)$$F’arrow\{\phi(f)|f\in F\}$
$iarrow 1$

while $i\leq 2^{m}$ do
項順序 $>$ における $F_{1}’=\{f_{1}\in B(\lambda)|f\in F’\}$ の正規ブーリアン. グレブナー基底$G_{i}$

を計算$iIG_{i}\cap B\neq\emptyset$

elsethen $b_{i}arrow G_{i}\cap B$ の要素$b_{:}arrow 0$$iarrow i+1$

end
$Garrow\langle\phi^{-1}((b_{1},b_{2}, \ldots,b_{2^{n}}))$

アルゴリズム中のら$B^{2^{m}}(\overline{X})$$\phi$のブーリアン. グレブナー基底は補題 72 で定義された同型写像の拡張として得られた$(B(A_{1}, \ldots,A_{m}))(\overline{X})$への同型写像である.

例7$F=\{f_{1}(\overline{X}), f_{2}(\overline{X}), \ldots,f_{18}(\overline{X})\}$$f_{1}(X)=X_{1}X_{3}X_{18}+\{d,p\}X_{4}X_{18}X_{20}+X_{11}X_{1S}+\{a,d\}X_{6}X_{10}+X_{5}X_{18}+X_{4}$,,$f_{2}(\overline{X})=X_{2}X_{6}+X_{4}X_{5}+\{k,q\}X_{6}X_{8}+X_{1}X_{26}X_{27}+\{c, k\}X_{4}X_{8}+X_{10}+X_{6}X_{10}$$f_{3}(\overline{X})=X_{1}X_{2}X_{4}+X_{3}X_{6}X_{10}+\{d,i\}X_{11}+X_{1}+X_{6}+X_{12}X_{24}X_{28}$,$f_{4}(\overline{X})=X_{2}X_{4}+\{e,g\}X_{3}X_{4}+X_{1}X_{12}+X_{12}X_{15}+X_{5}X_{10}X_{12}+X_{3}X_{11}$,$f_{6}(\overline{X})=X_{1}X_{3}+X_{1}X_{6}+\{j,l\}X_{2}X_{6}X_{16}+X_{11}X_{12}+X_{11}X_{23}+X_{16}+1$$f_{6}(\overline{X})=X_{6}X_{17}+X_{6}X\mathfrak{g}X_{30}+\{a,c\}X_{S}X_{10}+X_{1}X_{12}+X_{2b}X_{29}$,,$f_{7}(\overline{X})=X_{1}X_{11}+X_{12}+X_{2}X_{8}+X_{3}X_{11}X_{12}+X_{11}X_{12}+X_{4}X_{6}+\{b,e\}$,fs $(\overline{X})=X_{2}+X_{4}X_{7}+\{c, f\}X_{12}X_{17}X_{21}+X_{2}X_{3}X_{12}+X_{6}X_{7}+X_{12}+X_{4}X_{25}+X_{1}X_{11}$ ,,(刃) $=X_{1}+\{g,i\}X_{4}X_{6}X_{11}+\{m,r\}X_{1}X_{9}X_{11}+X_{2}X_{6}+X_{11}+1$ ,$f_{9}(\vec{X})=Xs+X_{S}X_{4}+\{k,m\}X_{1}Xs+X_{5}X_{6}+\{h,i\}X_{7}X_{24}$$f_{10}$,$fi_{1}(\overline{X})=X_{3}X_{20}+X_{6}+X_{6}X\tau+X_{11}+\{l,0,s\}X_{1\theta}Xso+X_{11}X_{\iota s}X_{23}$か190$f_{12}(\overline{X})=X_{3}X_{14}+\{f,n,t\}X_{1}X_{2}+X_{2}+X_{11}+X_{11}X_{15}+X_{19}X_{22}$$fi_{3}(\overline{X})=X_{2}X_{7}+\{f,j\}X_{11}+X_{2}X_{3}+X_{11}X_{12}+X_{9}X_{13}+X_{13}$,,$f_{14}(X)=X_{3}X_{7}+X_{8}+\{d, 0\}X_{8}X_{13}+\{c,t\}X_{2}X_{23}+X_{3}X_{20}X_{22}+1$ ,$f_{16}(\overline{X})=X_{4}X_{9}+X_{7}X_{20}+\{b,l\}X_{8}X_{19}+X_{20}$,$f_{16}(\overline{X})=\{a,e,n\}X_{7}X_{9}+X_{3}X_{6}+X_{6}X_{22}+\{e,r\}X_{1S}X_{29}+X_{19}X_{21}$$f_{17}(\overline{X})=X_{\theta}+X_{14}+X_{17}X_{1S}+X_{3}X_{4}X_{19}$,,$f_{18}(\overline{X})=X_{7}+X_{7}X_{21}+X_{2S}X_{24}\}$$B(X_{1},X_{2}, X_{3})$ から

B8 への同型写像$\phi$

は $\phi(f(X_{1},X_{2},X_{3})=(f(0,0,0),$ $f(0,0,1),$ $f(O, 1,0),$ $f(0,1,1)$ ,$f(1,0,0),$ $f(1,0,1),$ $f(1,1,0),$ $f(1,1,1))$ となる. 今の場合

$F_{:}’$

は以下のとおり.

$F_{1}’=\{fi(0,0,0,X_{4}, \ldots,X_{\theta 0}), \ldots, fi_{8}(0,0,0,X_{4}, \ldots,X_{30})\}$$F_{2}’=\{fi(0,0,1,X_{4}, \ldots,X_{\theta 0}), \ldots,fi_{8}(0,0,1,X_{4}, \ldots,X_{30})\}$$F_{8}’=\{f_{1} (1, 1, 1, X_{4}, ...,X_{30}), \ldots, f_{18}(1,1,1,X_{4}, \ldots,X_{30})\}$の正規ブーリアングレブナー基底を計算すると,$F_{i}’$$b_{1}=0,b_{2}=\{i\},b_{3}=\{k, q\},b_{4}=0,b_{6}=0,b_{6}=0,b_{7}=0,b_{8}=0$$\phi^{-1}((0, \{i\}, \{k, q\},0,0,0,0))=\{i\}(X_{1}+1)(X_{2}+1)X_{3}+\{k,q\}(X_{1}+1)X_{2}(X_{3}+1)$

求めたかった正規ブーリアングレブナー基底は,$G=\{\{i, k,q\}X_{1}X_{2}X_{3}+\{i,k, q\}X_{2}X_{3}+\{i\}X_{1}X_{3}+\{i\}X_{3}+\{k, q\}X_{1}X_{2}+\{k,q\}X_{2}\}$

実装は, 数式処理システム RISA $/ASIR$ を用いた. 計算時間については 1. $6GHZ$ Intel Core Duo CPU と$2560MB$ の SDRAM の PC を用いて 160 秒であった.

$X_{1},X_{2},X_{3}$グレブナー基底の計算に 2 時間費やしても計算は終わらなかった.

をパラメータとする包括的ブーリアン.
また, 辞書式順序などでプーリアン・グ

レブナー基底を計算してもこれも 2 時間では計算が止まらなかった.
この消去イデアルを求める新しいアルゴリズムはに適切な項順序を与えることで, 他の消去イデ$>X_{6}>X_{6}>\lambda_{4}’$ルを計算できる. たとえば,の代わりに $G_{i}\cap B(X_{4},X_{6})$ と (純) 辞書式順序 $X_{n}>$$T(\overline{X})$$\ovalbox{\tt\small REJECT}$...

$b_{i}$

を用いて, 消去イデアル $\langle F\rangle\cap B(X_{1}, \ldots, X_{6})$ を計算することが可能である.

このときのブーリアン. グレ

ブナー基底は $G=\{\{s,b,i, k,c,e, f,t,m,l\}X_{3}X_{4}X\epsilon+\{i\}X_{4}Xs+\{s,b, k,c,e, f,t,m,l\}X_{3}X_{6}$$+\{s,b,i,k,c,e, f,t,m,l\}X_{3}X_{4}+\{i\}X_{4}+\{s, b,i, k,c,e, f,t,m,l\}$,$\{0\}X_{6}X_{4}+\{0\}X_{3}X_{6}+\{0\}X_{4}+\{0\}X_{3}$,$(1+\{s,b,i, k,c, h, e, f,t,m,l\})X_{3}X_{4}+(1+\{s,b,i, k,c, h,e, f,t,m,l\})X_{3}\}$

となる.

6

結論
EhmBG が計算しているものは, 五をパラメータとする

る.

$(F\rangle$の包括的ブーリアングレブナー基底であ実際パラメータの値は $0,1$ だけでなく, $B$ のすべての要素が考えられる. 前のセクションを例に用い

ると, 各パラメータ $X_{1},X_{2},X_{3}$ の値は $\{a,b,c, \ldots, s,t\}$ の部分集合とそれらの補集合の可能性がある. つまり, $(2^{21})^{3}=2^{63}$ もの代入がありえるが,た,

このアルゴリズムは$2^{m}$

このアルゴリズムでは $0,1$ の代入を 8 通り調べるだけでよい.

ま個のブーリアングレブナー基底を計算する必要があるので, $m$ がある程度小191
さいときに有効であることがわかる. 今後の課題としては, 分散計算を実装することでより効率的に消去
イデアルを求めることがあげられる.

参考文献[1] Buchberger,B.(1965).Ein Algorithms zum Auffinden der Basiselemente des Restklassenringsbacheinem nulldimensionalen Polynomial.Doctoral Dissertation Math. Inst.University of Innsbruck, Austria.

[2] Kapur,D.(1995).An Approach for Solving Systems of Parametric Polynomial Equations. in Principles
and Practices of Constraint Programming.(eds. Saraswat and Van Hentenryck),MIT Press, 217-244.
[3] $Men|u$ , S., Sakai, K., Sato,Y. and Aiba,A. $(1993).A$ Study on Boolean Constraint Solvers. $Constrain\uparrow$
Logic Programming Selected Research The MIT Press, pp253-267.

[4] Montes, A.(2002) A new algorithm for discussing Gr\"obner bases with parameters. J.Symb. Comp.
33/2, 183208.
[5] Manubens, M. and Montes,A. (2006).Improving DISPGB algorithm using the discriminant ideal.
J.Symb. Comp. 41, 1245-1263.
[6] Rudeanu, S. Boolean functions and equations. North-Holland Publishing Co., AmsterdamLondon;American Elsevier Publishing Co., Inc., New York, 1974.
[7] Sakai,K. and Sato, Y.(1988).Boolean Gr\"obner bases. ICOT Technical Momorandum 488.

[8] Sakai,K. and Sato, Y. and Menju, S. (1991). Boolean Gr\"obner bases(revised). ICOT Technical Report613.

[9] Sato,Y.(1996).Set
Constraint Solvers(Prolog Virsion).
$//www$
http:icot. or.$jp/ARCHNE/Museum/FUNDING/funding- 96\cdot E$ html.

.

[10] Sato,Y.(1998).Set
Solvers(KLIC
Constraint
Virsion).
http: $//www$ .icot. or.iP/ARCHIVE/Museum/FUND] NG $/f\iota mding- 98\cdot E$ . html[11] Sato,Y. $(1998).A$ new type of canonical Groebner bases in polynomial rings over Von Neumam regularrings. Proceedings of ISSAC $1998_{I}ACM$ Press,317-32[12] Sato,Y. and Inoue,S.On the Construction of Comprehensive Boolean Gr\"obner Bases. Proceedings of

the Seventh Asian Symposium on Computer Mathematics ASCM $2005),pp$ 145.148,2005.
$($[13] Suzuki, A and Sato, Y.(2003). An Altemative approach to Comprehensive Gr\"obner Bases. J. Symb.
Comp. 36/34, 649-667.
[14] Suzuki, A and Sato, Y.(2006). A Simple Algorithm to Compute Comprehensive Grobner Bases

Using Grobner Bases. Intemational Symposium on Symbolic and Algebraic Computation (ISSAC
2006),Proceedings, 326-331.

[15] Weispfenning,V.(1989).Gr\"obner Bases in polynomial ideals over commmutative regular rings. In
Davenport Ed,editer,EUROCAL’87,336-347.Springer LNCS 378[16] Weispfenning,V.(1992). Comorehensive Gr\"obner Bases,J.Symbolic Computation(1992) 14,1-29