複素多項式系
はじめに
Mathematica 関数の
Reduce，
Resolve，
FindInstanceを使うと，方程式および不等式で表すことのできる広範な問題を解くことができる．これらの関数では，与えられた問題を，アルゴリズムで解くことのできる問題の列に還元しようと試みるヒューリスティックが使われる．この他にも，特別の性質を満足するクラスの問題に適用可能な多数のアルゴリズムが使われる．このドキュメントでは，複素多項式系として知られる問題のクラスを解くのに使われるアルゴリズムを説明する．また，返された答の構造の特徴を示し，複素多項式系を解く際にさまざまな面で影響を及ぼすオプションについて述べる．
を，下のように論理結合子および量限定子を使って結合したものである．
変数
x が
x
または
x内に現れることを束縛出現，その他の部分に現れることを自由出現という．複素多項式系に変数
x の自由出現がある場合，
x はその系の自由変数という．複素多項式系に量限定子が含まれない場合は，quantifier-freeという．
以下は，自由変数
x，
y，
z を持つ複素多項式系の例である．
Mathematica では量限定子は，関数
Exists (
)および
ForAll (
)を使って表す．
に変換することができる．ここで，それぞれの
Qi は量限定子
または
であり，
(x1, ..., xn;y1, ..., ym)はquantifier-freeである．
quantifier-freeの複素多項式系はすべて，選言標準形に変換することができる．
ここで，それぞれの
i, j は整方程式あるいは不等式である．
Reduce，
Resolve，
FindInstanceは常に複素多項式系を冠頭標準形に，そのquantifier-free部を選言標準形にし，方程式と不等式の両辺を減算して以下の形式にする．
以下のセクションでは，常に系がこの形式に変換されたものと想定する．
Reduce を使うと，任意の複素多項式系を解くことができる．解（
について
を拡張した後）は項の選言で，以下の形式となる．
ここで
x1, ..., xn は系の自由変数，各
gi は多項式，各
ri は根号か
Rootオブジェクトを使って表される代数関数であり，連言項(
2)はない可能性がある．各
ri (x1, ..., xi-1)は正しく定義されている．つまり，
ri の分母および
Rootオブジェクトの主要項は，連言(
2)に先行する項を満足するいかなる
(x1, ..., xi-1)についてもゼロにならないということである．
| Out[1]= |  |
|
Resolveは任意の複素多項式系から量限定子を除去することができる．変数が指定されていなければ，結果は次の項
の論理結合となる（ここで
f と
g は多項式，各
xi は系の自由変数である）．入力で変数が指定されていれば，
Resolveは
Reduceと同じ答を与える．
| Out[2]= |  |
|
FindInstanceは任意の複素多項式系を扱うことができ，複素数解の例，あるいは空リスト（系に解がない場合）を与える．複数の例が要求された場合，例は系のすべての解からランダムに生成されるので，
RandomSeedオプションの値に依存する可能性がある．1つの例が要求された場合は，1つの例だけを生成するより高速なアルゴリズムが使われ，返される例は常に同じものになる．
| Out[3]= |  |
|
複素多項式系を解くときに使われる主なツールは，グレブナー基底アルゴリズム[
1]である．これは
Mathematica では
GroebnerBasis関数として直接利用することができる．
グレブナー基底
理論
このセクションでは，グレブナー基底の理論を簡単に紹介する．ここでは，
Mathematica で複素多項式系を解く場合に使用されるアルゴリズムを説明するのに必要な性質だけを提示する．詳細は[
1,
2]等を参照のこと．[
2]でmonomial（単項式）と呼ばれているものは，[
1]ではterm（項），またその逆となっている点に注意する．このドキュメントでは[
1]で使われている用語を使用する．
x1, ..., xn 中の単項式は，非負の整数
ei を持つ形式
x1e1...xnen の式である．
ここで，
M=M (x1, ..., xn)が
x1, ..., xnの単項式すべての集合であるとする．単項式順序は
M 上では線形順序
であり，すべての
t
M について
1t となる．
t1t2 はすべての
t1, t2, s Mについて
t1st2s となることを示す．
R が体，整数領域，体上の一変数多項式の領域のいずれかであるとする．また，
Quot と
Rem が次のように定義される関数
R2
R であるとする．その定義とは「
R が体であれば，
Quot (a, b)=a/b で
Rem (a, b)=0となる．
R が整数領域であれば，
Quot および
Rem は整数商と
-|b|/2<Rem (a, b)≤|b|/2の剰余関数である．
R が，体の一変数多項式の領域であれば，
Quot および
Rem は多項商と剰余関数である」というものである．
aが
R の非零要素で
m が単項式であるときの積
t=a m は項と呼ばれる．
M 上の単項式順序を
として，
fR[x1, ..., xn]\{0}とする．
f の先頭単項式
LM (f) は
-
fで現れる最大の単項式，
fの主係数
LC (f)は
f の
LM (f)での係数であり，
f の先頭項
LT (f)は積
LC (f)LM (f)となる．
単項式順序
では，
R[x1, ..., xn]のイデアル
I のグレブナー基底は，多項式の有限集合
G である．ここでは，
fI のそれぞれについて，
LT (f)が
LT (g)で割り切れるような
gG が存在する．すべてのイデアル
I はグレブナー基底を持つ（証明は[
1]等を参照のこと）．
pR[x1, ..., xn]\{0}として，
mR[x1, ..., xn]が単項式だとしよう．
m が
LM (p)で割り切れ，
a≠Rem (a, LC (p))ならば，項
t=a m は
p を法として可約である．
t が
p を法として可約ならば，
p を法とする
t の簡約化は多項式
となる．ここで
Rem (a, LC (p))≠0ならば
LT (Red (t, p))=Rem (a, LC (p))mとなり，それ以外の場合は
LM (Red (t, p))mとなる点に注意する．
fR[x1, ..., xn]で，
P が
R[x1, ..., xn]\{0}の順序付き有限部分集合であるとする．
f に
P の要素を法として可約な項が含まれていれば，
f は
P を法として可約である．
P を法とした
f の簡約化
Red (f, P)は次の手順で定義される．
P の要素を法として可約な
f の項の集合
RT が空集合でないときに，
-最大の単項式を持つ項
tRT を取り，
t が
p を法として可約であるような最初の
pP を取り，
f の項
t を
Red (t, p)で置換するのである．この手順の後続するステップで選ばれる項
t の単項式は，
-降鎖を形成し，各単項式は最大
k 回現れる．ここで
k は
P の要素数であるため，手順は終了する．
グレブナー基底
G は，すべての
gGについて
g が
G\{g}を法として可約ではなく，かつ，
R が整数領域
LC (g)>0である場合，半簡約化されているという．
Mathematica 関数の
GroebnerBasisは半簡約化されたグレブナー基底を返す．以下の説明では，グレブナー基底はすべて半簡約化されたものと仮定する．ここでは，基底多項式はモニックである必要はないので，文献で定義されている既約グレブナー基底と同じものではない．単項式順序が固定されているときは，各イデアルが一意の既約グレブナー基底を持つ．ここで定義する半簡約化されたグレブナー基底は，
R の可逆元による乗算までしか一意ではない（
性質 2を参照のこと）．
性質 1：
R[x1, ..., xn]のイデアル
I のグレブナー基底を
G とし，
fR[x1, ..., xn]とする．この場合，
Red (f, G)=0のとき，かつそのときに限り
fI である．
性質 2：同じ単項式順序
でのイデアル
I の2つのグレブナー基底を
G={g1, ...gk}および
H={h1, ...hm}とする．また，
G と
H の要素が先頭単項式によって順序付けられているとする．この場合，
k=m となり，
R が整数領域の場合はすべての
1≤i≤k について
gi=hi となる．それ以外の場合は
R の任意の逆元
ci について
gi=ci hi となる．
証明：
LM (f)=LM (g)ならば，
LT (f)が
g を法として可約であるか，
LT (g)が
f を法として可約であるかのどちらかとなる．よって，グレブナー基底の要素の先頭単項式はすべて異なる．一般性を失わずに
k≤m と仮定する．帰納法を使うために，
j≤k と固定し，すべての
i<j について，
R の可逆元
ci については
gi=ci hi であると仮定する．
R が整数領域ならば，
ci=1である．一般性を失わずに
LM (gj)LM (hj)と仮定する．
gj は
I に属しているので，
LT (gj)が
LT (hi) で割り切れるような
i が存在する．よって
LM (hi)LM (gj)で，
i≤jとなる．
i<jならば，
gj は
hi を法として可約である．また，ここで
gi=ci hi を法とすることもできそうであるが，これはありえない．なぜならば，
G が半簡約化されているからである．従って，
i=j，
LM (gj)=LM (hj)であり，
LT (gj)は
LT (hj)で割り切れる．同様に
LT (hj)は
LT (gj)で割り切れる．よって，
LT (gj)=cjLT (hj)となるような
R の可逆元
cj が存在する．
R が整数領域ならば，
LC (gj)と
LC (hj)は正となり，
cj=1となる．
r=cjhj-gjとしてみよう．ここで
r≠0であると仮定する．
r は
Iに属するので，一部の
i<j について
LT (r)は
LT (gi)で割り切れなければならない．
と
がそれぞれ
LM (r)における
gj および
hjの係数であるとする．
R が体であるなら，
gj の項
LM (r) は
gi を法として可約である．これは
G が半簡約化されているという仮定に反する．
R が体の一変数多項式の領域ならば，
であるので，
gj が
gi を法として可約であるか，
hj が
hi=cigi を法として可約であるかのどちらかとなる．しかし，後者は
G と
H が半簡約化されているという前提に反する．最後に
R を整数領域とする．
gj は
gi を法として可約ではなく，
hj も
hi=giを法として可約ではないので，
-LC (gi)/2<≤LC (gi)/2および
-LC (gi)/2< ≤LC (gi)/2となる．
LT (r)は
LT (gi)で割り切れるので，
-LC (gi)<LC (r)=-<LC (gi)は不可能である．従って
r=0が成り立つので，
gj=cj hjとなる．
j についての帰納法により，すべての
j≤kについて
gj=cj hjが成り立つ．
k<m ならば，
hk+1は
gj（このとき
j≤k）を法として可約であり，
hk+1は
hj=cj-1gjを法として可約である．よって，
k=mとなり，
性質 2が証明される．
性質 3：
I が
R[x1, ..., xn]のイデアルで，
fR[x1, ..., xn]であり，
G が
R[x1, ..., xn, y]のイデアル
<I, 1-y f> のグレブナー基底であるとする．この場合，
R の可逆元
c について
G={c} が成り立つとき，かつそのときに限り
f は
I の基底になる．
イデアルに
R の可逆元が含まれるなら，
GroebnerBasisは常に
{1}を返す．
は，任意の非負の整数
k のときイデアル
J=<I, 1-y f> に属す．ゆえに，
f が
I の基底に属していれば，1は
J に属す．
G は
J のグレブナー基底なので，要素
c の主係数は1を割り切るようなものでなければならない．ゆえに
c は
Rの可逆元である．
G は半簡約化されており，どの項も
c で割り切れるので，
G={c}となる．ここで
R の可逆元
c について
G={c}であると仮定する．1は
J に属するので，
が成り立つ．ここで各
ai は
I に属し，各
bi は
R[x1, ..., xn]に属す．
y のベキ乗での係数を比較することで，
I を法とする方程式
b0
1，
bibi-1f（
1≤i≤m-1のとき），
bm-1f0が導かれる．次に，
bifi（
0≤i≤m-1のとき），
I を法とする
fm0という方程式になる．従って，
f は
Iの基底に属す．これで
性質 3が証明される．
さらに技術的な以下の性質は，複素多項式系を解く際に重要である．
性質 4：
y を含む単項式が
yを含まないものよりも大きくなるような単項式順序での
[x1, ..., xn, y]のイデアル
I のグレブナー基底を
G とする．また，
y について最小の正の次数
d を持つ
G の要素を
h ，
y についての
h の主係数を
c (x1, ..., xn)，
y に依存しない
G の要素すべてを
{h1, ..., hs}とする．ここで，任意の多項式
pI および点
(a1, ..., an, b)について，
c (a1, ..., an)≠0，
hi (a1, ..., an)=0（
1≤i≤sのとき），
h (a1, ..., an, b)= 0ならば，
p (a1, ..., an, b)= 0である．
証明：
p を
h で割ったときの擬剰余
r を
y の多項式と考える．
p と
h は
I に属すので，
r も
I に属す．
性質 1により，
G による
r の簡約はゼロでなければならない．
y についての
r の次数は
d よりも小さいので，
r は
y に依存する
G のどの要素によっても簡約されない．そこで
が成り立ち，
r (a1, ..., an, b)=0も成り立つ．
c (a1, ..., an)≠0なので，(
1)は
p (a1, ..., an, b)= 0であることを示しており，これで
性質 4が証明される．
Mathematica 関数のGroebnerBasis
Mathematica 関数の
GroebnerBasisは，半簡約化されたグレブナー基底を求める．このセクションでは，複素多項式系の解法で使用される
GroebnerBasisのオプションを説明する．
複素多項式系の解法で使われるGroebnerBasisのオプション
CoefficientDomain
このオプションは係数の領域
R を指定する．デフォルトの
Automatic設定では，係数領域は入力に存在する数値係数によって生成された体になる．
CoefficientDomainで使える設定
係数領域
R も
GroebnerBasisの
Modulusオプションの設定に依存する．
Modulus->pという設定では，素数
p についての係数領域は体
p，また，
CoefficientDomain->RationalFunctionsのときは
p 上の有理関数体となる．
Method
デフォルト設定の
Method->Automaticでは，
GroebnerBasisでBuchbergerアルゴリズムの変形が使われる．この他に使えるアルゴリズムはグレブナーウォークで，グレブナー基底をより簡単な単項式順序で計算してから，要求される難しい単項式順序に変換するものである．これは，要求された順序で直接グレブナー基底を計算するよりも速いことが多い．特に入力の多項式が簡単な順序のグレブナー基底であることが分かっている場合に有効である．設定
Method->Automaticでは
GroebnerBasisでデフォルトの
CoefficientDomain->Rationalsおよび
MonomialOrder->Lexicographicのグレブナーウォークが使われる．
| GroebnerBasis[polys,vars,Method->{"GroebnerWalk","InitialMonomialOrder"->order1},MonomialOrder->order2] |
| order1のグレブナーウォークを見付け，それをorder2のグレブナー基底に変換するためにグレブナーウォーク法を使う |
グレブナーウォーク法を使ったグレブナー基底の変換
MonomialOrder
このオプションは，単項式順序を指定する．値は指定された単項式順序のいずれか，あるいは重み行列のどちらかである．以下の表は
x1d1...xndn x1e1...xnenとなる条件を与える．
| Lexicographic | d1=e1...di-1=ei-1 |
| DegreeLexicographic | d1+...+dn<e1+...+en (d1+...+dn=e1+...+end1=e1...di-1=ei-1di<ei) |
| DegreeReverseLexicographic | d1+...+dn<e1+...+en (d1+...+dn=e1+...+endn=en...di+1=ei+1di<ei) |
単項式順序
QE(量限定子除去)では，量限定子変数を含む単項式が含まないものよりも大きくなるような順序が必要である．
Lexicographic順序はこの条件を満足するが，次の
EliminationOrderの方が通常計算が速い．
ここで
d は合計次数，
X は自由変数，
Y は量限定子変数，
mi と
ni は単項式，
DRLは
DegreeReverseLexicographic順序を表している．
EliminationOrderを使うときは，除去変数を指定した
GroebnerBasisシンタックスが必要である．
| GroebnerBasis[polys,xvars,yvars,MonomialOrder->EliminationOrder] |
| EliminationOrderでグレブナー基底を見付ける |
除去順序におけるグレブナー基底
MonomialOrder->EliminationOrderと設定されている
GroebnerBasisでは，デフォルトで
yvars を含む多項式を結果から削除し，
xvarsの基底多項式だけを返す．基底多項式をすべて得るためには，
GroebnerBasisOptionsグループのシステムオプション
EliminateFromGroebnerBasisの値を変更しなければならない（
Mathematica はQE法でこのオプションを局所的に変更する）．オプション値は以下のように変更することができる．
| | |
| "EliminateFromGroebnerBasis" | True | MonomialOrder->EliminationOrderに設定されたGroebnerBasisで除去変数を含む多項式を削除するかどうか |
システムオプションEliminateFromGroebnerBasis
以下により  から y が除去される．答となる多項式は，その零点が，もとの2つの方程式の解集合を (x1, x2)平面上に投影したときのZariski閉包となるようなものである．
| Out[4]= |  |
|
解集合を (x1, x2)平面上へ投影したときの厳密な記述は，すべての基底多項式に依存する． x1あるいは x2がゼロのときは，2番目の基底多項式はゼロにはならないことに注意する．
| Out[6]= |  |
|
Resolveにより (x1, x2)平面上への解集合の投影の正確な記述が得られる．
| Out[8]= |  |
|
決定問題
決定問題とは，すべての変数が存在量化された系である．つまり，以下の形式の系のことである．
ここで
x1, ..., xn はすべて
の変数となっている．決定問題を解くことは，それが
Trueと
Falseのどちらと等価であるかを判定すること，言い換えれば，量限定子を含まない整方程式および不等式の系
(x1, ..., xn)が解を持つかどうかを判定することである．
この決定問題を解くことで，行列式がゼロである2次方程式が2つの異なる根を持つことはないことが証明される．
| Out[9]= |  |
|
を仮定すると，いかなる決定問題を解くことも，以下の形式の有限個の決定問題を解くことに還元できる．
ヒルベルトの零点定理(Nullstellensatz)およびグレブナー基底の
性質 3により，
が{1}と異なるとき，かつ，そのときに限り複素数解を持つ．
| Out[10]= |  |
|
| Out[11]= |  |
|
Mathematica で決定問題を解く場合，
GroebnerBasisの計算で使われる単項式順序は，
{z}が除去変数リストとして指定された
MonomialOrder->EliminationOrderである．この設定は，
z を含む単項式の方が，含まないものよりも大きくなるような単項式順序に相当し，
z を含まない単項式の順序は次数逆辞書式順序になる．不等式条件がない場合は，
z を導入する必要はなく，
Mathematica は
MonomialOrder->DegreeReverseLexicographicという設定を使う．
QE（量限定子除去）
複素多項式系にはどれも，それと等価のquantifier-freeの複素多項式系が存在する．このことは，半代数的構成可能集合（quantifier-freeの整方程式および不等式の系の解集合）の投影が，半代数的構成可能集合であるというシュヴァレー(Chevalley)の定理に従っている（[
3]を参照）．QEは指定された複素多項式系と等価のquantifier-freeの複素多項式系を見付ける手続きである．
Mathematica では，複素多項式系のQEは
Resolveで実行される．また，QEは複素多項式の解法もしくは解の例の探索の第1段階として，
Reduceおよび
FindInstanceでも使われる．
以下の系から量限定子を除去することにより，2次方程式が少なくとも2つの異なる零点を持つための条件が与えられる．
| Out[12]= |  |
|
Mathematica では，複素多項式系に以下のようなQE法が使われる．例えば，次の恒等式があるとする．
どのような複素多項式系から量限定子を除去することも，下の系から単一の存在記号を有限回数除去することに還元される．
(
1)から量限定子を除去するために，
Mathematica ではまず，
y を含む単項式が
y を含まないものよりも大きくなるような単項式順序で，方程式のグレブナー基底
使用される単項式順序は，
EliminationOrderである．ここで
{y}は除去変数リストで指定されており，
すべての基底多項式は維持されている．
G が
y に依存する多項式を含まないならば，(
1)と等価のquantifier-freeの系は，
G のすべての要素をゼロとし，
y の多項式としての
g の係数の少なくとも1つがゼロではないとすることで得ることができる．これ以外の場合は，
y の最低の正の次数
d を持つ
G の要素を
h とし，
y の
h の主係数を
c (x1, ..., xn)とし，
y に依存しない
G の要素すべてを
{h1, ..., hs}とする．これで(
1)は，2つの系の選言
に分割できる．(
2)から量限定子を除去するために，QEが再帰的に呼び出される．
{c, f1, ..., fk}で生成されるイデアルは，
{f1, ..., fk}で生成されるイデアルを厳密に含んでいるので，多項式環がネーターであるという性質により，再帰が有限であると保証される．
c が
{f1, ..., fk}で生成されるイデアルの基底に属すなら（これは厳密に1が
に属すときである），(
3)は
Falseと等価になる．そうでない場合は，
gd を
h で割ったときの擬剰余を
y の多項式として
とする．これで(
3)はquantifier-freeの系
と等価になる．(
3)が(
4)を意味することを示すために，
(a1, ..., an)が(
3)を満足すると仮定する．
c (a1, ..., an)≠ 0となり，
が成り立つような
bが存在する．
{h1, ..., hs}および
h は
{f1, ..., fk}で生成されるイデアルに属すので，
および
h (a1, ..., an, b)=0が成り立つ．従って，
が成り立つ．(
4)が(
3)を意味することを示すために，
(a1, ..., an)が(
4)を満足すると仮定する．すると，
が成り立つ．
h (a1, ..., an, y)は次数
d の多項式で，
r (a1, ..., an, y)は
dより低い次数の非零の多項式なので，
h (a1, ..., an, y)は
(y-b)m で割り切れるが，ある
1≤m≤dについては
r (a1, ..., an, y)は割り切れないような
h (a1, ..., an, y)の根
b がある．
g (a1, ..., an, b)がゼロならば，
g (a1, ..., an, y)dは
(y-b)m で割り切れるだろうが，これは
r (a1, ..., an, y)が
(y-b)mで割り切れるということを意味するので，ありえない．従って，
g (a1, ..., an, b)≠0となる．
性質 4は
pG であるすべての多項式について
p (a1, ..., an, b)= 0であることを示している．
G は
{f1, ..., fk}で生成されるイデアルのグレブナー基底なので，
以下で，  から量限定子を除去する．ここで g=1， h=-y+x1+x2， c=-1である． c は非零の定数なので，( 2)は Falseとなり，等価のquantifier-freeの系は( 4)で与えられる．また， g は非零の定数なので，( 4)は  となる．
| Out[14]= |  |
|
任意の複素多項式系
FindInstance
FindInstanceでは任意の複素多項式系を扱うことができ，複素数解の例，あるいは空リスト（解のない系の場合）を与える．複数の例が要求された場合，例は
Reduceによって与えられた系のすべての解からランダムに生成される．1つの例が要求された場合は，1つの例だけを生成する，より高速なアルゴリズムが使われる．以下に挙げるのは，1つの例だけを見付ける，あるいは系に解がないことを証明するアルゴリズムである．
系に全称記号(
)が含まれる場合，
QEアルゴリズムを使って，系が存在記号(
)だけを含むようになるまで，あるいは系がquantifier-freeになるまで，最内部の量限定子を削除していく．
は，
(x1, ..., xn, y1, ..., ym)に解があるとき，かつ，そのときに限り解を持つ．また，
(x1, ..., xn, y1, ..., ym)の解が
(a1, ..., an, b1, ..., bm)であるならば，(
1)の解は
(b1, ..., bm)である．つまり，存在記号だけを含む系で解の例を見付けるためには，quantifier-freeの系の例が見付かるだけで十分なのである．さらに，
1≤i≤m のときに
(a1, ..., an)が
i (x1, ..., xn)のいずれかの解であるとき，かつ，そのときに限り，
(a1, ..., an)は
の解の例を見付ける方法を示すことで十分なのである．まず，
MonomialOrder->EliminationOrderという設定で
z に依存する多項式を除去し，
{f1, ..., fk, 1-g z}の
GroebnerBasis G を計算する（不等式条件がない場合は，
G は
MonomialOrder->DegreeReverseLexicographicと設定した
{f1, ..., fk}の
GroebnerBasisである）．もし
G に1が含まれる場合，解はない．含まれない場合は，次数逆辞書式順序の
G によって生成されたイデアルを法とする非常に独立な部分集合の中で，最大基数の
{x1, ..., xn}の部分集合
S を計算する（[
1]のセクション9.3を参照のこと）．
S={xn-d+1, ..., xn}となるように
{x1, ..., xn}を並べ替え，
G で生成されたイデアルの辞書式順序
GroebnerBasis H を計算する．
Mathematica では
H を計算するために，
グレブナーウォーク法が使われる．
1≤i≤n-d のときそれぞれの変数
xi について，
xi には依存するが
{x1, ..., xi-1}には依存しない
H の元の中で，最小の先頭単項式を持つ多項式
hiH を選ぶ．
hi の主係数を
xi の多項式
ci とする．
ci が
S にない変数に依存するならば，
H と
ci で生成されたイデアルの辞書式順序グレブナー基底を
H に代入する．以下は，この操作により，
S が
H で生成されるイデアルを法として強く独立であるよう維持されることを示す．従って，
H を有限（多項式環のネーター性による）回拡大した後，
hi の主係数
ci が
1≤i≤n-d ですべて
{xn-d+1, ..., xn}にのみ依存するようになることがある．多項式集合
P について，
P の要素の共通零点集合を
Z (P)とする．
Z (G)と
Z (H)の両方とも次元が
d で，
Z (H)
Z (G)であるため，
Z (H)の
d 次元の既約成分は
Z (G)の成分でもある．
g は
Z (G)のどの既約成分上でもゼロにならないので，
Z (H)の
d 次元既約成分上でもゼロにならない．よって，
H と
g のグレブナー基底には，
{xn-d+1, ..., xn}にのみ依存する多項式
t が含まれる．
p=t c1...cn-dが成り立つとしよう．(
2)の解を求めるために，
p (an-d+1, ..., an)≠0となるような最後の
d 個の座標
{an-d+1, ..., an}を選ぶ．
1≤i≤n-dではすべて，
ci (an-d+1, ..., an)≠0なので，
性質 4により，
i=n-d, ..., 1のとき
ai が
hi (xi, ai+1, ..., an)の最初の根に選ばれるなら，
(a1, ..., an)Z (H)Z (G)である．さらに
g (a1, ..., an)≠0となる．そうでないと，
(a1, ..., an)は
Z (H
{g})に属すことになり，
t (an-d+1, ..., an)= 0を意味する．しかしこのようなことは，
p が
t で割り切れるため，ありえないのである．
前述のアルゴリズムの正確さを証明するためには，
S にない変数に依存する
ci で
H を拡大すると，
H で生成されるイデアルを法とした
S の強い独立性が維持されることを示さなければならない．任意の
1≤i≤n-d で，
ci が
S にない変数に依存すると仮定する．
Ii+1[xi+1, ..., xn]が
H
[xi+1, ..., xn]で生成されたイデアルを表し，
Ji+1[xi+1, ..., xn]が
Ii+1と
ci で生成されたイデアルを表すとする．このとき
Ji+1には
[xn-d+1, ..., xn]の非零要素は含まれない．これを証明するために，
p[xi+1, ..., xn]で
qIi+1のときに
r=p ci+qJi+1[xn-d+1, ..., xn]\{0}であるとする．ここで
degxi (t)<k のとき
hi= cixik+t が成り立ち，
は
H で生成されたイデアルに属し，
gi= r xik+p t も同様である．これは
hi の選択に反する．というのは，
gi の頭単項式は
xi に依存しており，
hi の頭単項式よりも厳密に小さいからである．従って，
Z (Ji+1)の
Ad= (d){xn-d+1, ..., xn}上への投影は
Ad で密である．また，
Z (Ii+1)の次元は
d なので，
ci は，
Ad への投影が
Ad で密であるような
Z (Ii+1)の任意の既約成分
Ci+1上でゼロでなければならない．
Z (Ii+1)は
d 次元集合
Z (H)の投影のZariski閉包なので，
Ci+1は
Z (H)の既約成分
C の投影のZariski閉包に含まれる．
Z (ci)C は
d 次元なので，
ci は
C 上でゼロであり，
C の
Ad への投影は
Ad で密である．これにより，
S が
H と
ci で生成されたイデアルを法として強く独立であることが証明される．
以下は， H を拡大する必要がある例である．ここでは S={x3}， h1= (x2-x3) x1， c1=x2-x3， I2=< (x2-x3)2 (x2-2 x3)>である． c1は I2の2つの1次元成分のうちのどちらかでゼロである．
| Out[16]= |  |
|
H を c1 で拡大すると，すべて {x3}の強い独立性を維持しながら， x3 だけに依存（実際は定数も）する ci となる．
| Out[17]= |  |
|
Reduce
Reduceでは，任意の複素多項式系を解くことができる．第1段階として，
Reduceは
QEアルゴリズムを使って量限定子を除去する．得られたquantifier-freeの系が選言であるならば，選言の各項は別々に解かれ，解は項の解の選言として与えられる．従って，問題は以下の形式
のquantifier-freeの系を解くことに簡約される．まず，変数次数
{z, xn, ..., x1}，
MonomialOrder->Lexicographicで
{f1, ..., fk, 1-g z}の
GroebnerBasis G を計算し，
z に依存しない多項式を選ぶ．すると，
G=0 g (x1, ..., xn)≠0の解集合は(
3)の解集合と等しく，
g は
G の零点集合
Z (G)のどの成分上でも消失しない．
G に1が含まれるならば(
3)には解はない．それ以外の場合は，
j>i のときに
xi には依存するが
xj には依存しない
G の要素の集合
Gi が，空にはならないような各
1≤i≤n について，
xi の最低の正の次元を持つ
Gi の要素
hi を選ぶ．
hi の主係数
ci のうちの1つが
Z (G)上でゼロ，つまり，
G で生成されるイデアルの基底に属すなら，
G を，
G と
ci で生成されるイデアルの辞書式順序グレブナー基底で置換する．ここで，系を
の2つに分割し，選言(
4)の最後の項以外のすべてについて再帰的に解法を呼び出す．代数集合
cij=0G=0は厳密に
G=0に含まれているので，再帰は有限である．
ci と
g すべての積が
G で生成されるイデアルの基底に属すならば，最後の項には解がない．そうでない場合は，
性質 4により，最終項の解集合は
と等しくなる．条件
cij≠0は，
Roots[hij=0, xij]で与えられる解（基底あるいは
Rootオブジェクトとして表される）すべてが正しく定義されていることを保証する．
Reduceは返される不等式条件を簡約するために，複数の因数の削除，前の不等式条件と共通の因数の削除，モジュロ
hij の還元，
Z (G)上で非零の因数の削除等，いくつかの操作を実行する．
オプション
Reduce，Resolve，FindInstanceのオプション
複素多項式系を解くための
Mathematica 関数には，操作方法を制御するオプションが数多く備わっている．このセクションでは，そのようなオプションを要約する．
複素多項式系の動作に影響を与えるReduce，Resolveのオプション
複素多項式系の動作に影響を与えるReduce，Resolve，FindInstanceのオプション
Backsubstitution
Reduceはデフォルトで，変数リストの前の方に現れる変数を使って，それ以降に現れる変数の解を表すことができる．
| Out[18]= |  |
|
Backsubstitution->Trueと設定すると， Reduceは方程式の右辺から変数を除去するために逆置換を使う．
| Out[19]= |  |
|
CubicsとQuartics
Reduceはデフォルトでは，3次および4次方程式を解くのにカルダノの公式を使わない．
| Out[20]= |  |
|
| Out[21]= |  |
|
WorkingPrecision
| Out[22]= |  |
|
ReduceOptionsグループのシステムオプション
ここで挙げるのは，複素多項式系での
Reduce，
Resolve，
FindInstanceの動作に影響を及ぼす
ReduceOptionsグループのシステムオプションである．これらのオプションは以下のように設定する．
オプション FinitePrecisionGBを Trueに設定する． |
以下で FinitePrecisionGBの値をチェックする．
| Out[24]= |  |
|
オプション FinitePrecisionGBをデフォルト値の Falseに戻す． |
複素多項式系でのReduce，Resolve，FindInstanceの動作に影響を及ぼすReduceOptionsグループのオプション
FinitePrecisionGB
| Out[28]= |  |
|
| Out[30]= |  |
|
有限精度を使うと， GroebnerBasisの計算速度が格段に向上することがある．しかし，数値計算は精度の損失のために失敗するか，誤った答を出す可能性がある．数値計算は通常，厳密な GroebnerBasisの計算をしてから数値根の探索をするよりも精度の劣る結果を与える．
| Out[31]= |  |
|
これは，結果がその精度までは等しいことを示している．
| Out[32]= |  |
|
ReorderVariables
Reduceはデフォルトでは，指定された変数の順序を変えることができない．変数リストの前の方に現れる変数は，それより後に現れる変数の解を表すために使うことができるが，その逆はできない．
| Out[34]= |  |
|
システムオプションを "ReorderVariables"->Trueと設定すると， Reduceは方程式が解きやすくなるような変数順序を選ぶことができる．
| Out[35]= |  |
|
参考文献
[1] Becker T. and V. Weispfenning. Gröbner Bases. Springer-Verlag (1993)
[2] Cox D., J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms. Springer-Verlag (1996)
[3] Łojasiewicz S. Introduction to Complex Analytic Geometry. Springer-Verlag (1991)
2 
