9.2. 準素分解の概略 97
[証明]h ∈ 右辺とすると, hfm ∈ I かつ h = a+bfm (a ∈ I) とかける. よって bf2m =hfm−afm ∈I すなわち b∈I :f2m =I :fm これから h∈I. 2
定義 9.17 (extension)
Y ⊂X に対し, Ie =K(Y)[X\Y]I と定義する.
定義 9.18 イデアル dim(I) = d とすると,次元の定義により, |Y|=dなる indepen-dent set Y ⊂X がとれる. これを maximally independent setとよぶ.
補題 9.19 Y が maximally independent setのときIe は K(Y)上 0 次元イデアル.
[証明]定義により,全ての x∈X\Y に対し,I∩K[{x} ∪Y]6= 0 だから,K(Y)上で 考えればx の一変数多項式が Ie 中に存在することになる. よって Ie は0 次元.2 補題 9.20 < を Y <(X\Y) なるblock order とする. G が I の< に関するグレブ ナ基底ならば, G は, Ie の, 同じ orderに関するグレブナ基底.
定義 9.21 (contraction)
イデアルJ ⊂K(Y)[X\Y]に対し,J∩K[X] をJ の contraction とよび,Jc と書く.
命題 9.22 I をイデアル,< をY <(X\Y)なる block order とし, Gを <に関する I のグレブナ基底とする. このとき,
f = LCM{HC(g)|g ∈G}
(ただし, HC(g)は K(Y)[X\Y] の元としてとる)とすれば, Iec =I :f∞
これらと, 後で述べる0次元イデアルの準素分解を用いて, 次のアルゴリズムが得 られる.
アルゴリズム 9.23 [20]
Input : イデアルI ∈R=K[X]
Output : I =∩Qi (I の minimal な準素分解) Pi =√
Qi (Qi の付属素イデアル) Y ←maximally independent set modulo I
∩Q¯i ←Ie (0 次元) の K(Y) 上の準素分解 (f, s)← Iec =I :f∞ =I :fs なる f および s
∩Rj ←I +Id(fs) の準素分解 return ¯Qic∩(∩Rj)
9.3. 0次元イデアルの準素分解 99 I+Id(fs)は I を真に含むから, 停止性は保証される. このアルゴリズムを実現する ためには,
• 0 次元イデアルの準素分解
• maximally independent set の選び方
のアルゴリズムを与える必要がある. この内, maximally independent setに関しては, 次の命題がある.
命題 9.24 I をイデアルとし,MB< を,R/I の,全次数つきorder <に関する mono-mial によるK-基底とする. このとき, dim(I) ==max(|U| |T(U)⊂MB<).
この命題に基づいて,一つのグレブナ基底から, dim(I) を求めるアルゴリズムが構成 できる. 以下で, 0次元イデアルの準素分解について概略を述べる.
9.3 0 次元イデアルの準素分解
I ⊂R=K[X] を 0次元イデアルとする.
定義 9.25 f ∈K[X]が I の separating elementとは, I の K 上の相異る零点 a, bに 対し, f(a)6=f(b)なること.
定義 9.26 f ∈K[X] とする. t /∈X なる不定元をとり,R[t] のイデアルJ =IR[t] + Id(t−f)を考えれば, J も 0次元イデアルより, (I+Id(t−f))∩K[t] = Id(g(t))な るモニックなg ∈K[t] が存在する. g を f の I に関する最小多項式と呼ぶ.
命題 9.27 f を I のseparating elementとし, g を f の最小多項式とする. このとき, g =g1e1· · ·gerr
(gi はK 上既約) と因数分解すれば,
I = (I+g1e1)∩ · · · ∩(I+grer) は I の準素分解で,
√I =qI+g1∩ · · · ∩qI+gr は √
I の素イデアル分解となる. すなわち, √
I+gi はI+giei の付属素イデアル.
イデアルの seratating element は, 直接求めるのは困難である. 定義により, √ I の separating element が I の seratating element となることを用いて, √
I を計算し, separating elementを求めることを考える.
定義 9.28 体 K が完全体とは, 既約多項式が全て分離的であること.
注意 9.29 以下の命題, アルゴリズムでは, 基礎体が完全体であることを要求するも のがいくつかある. 標数 0の体は全て完全体である. また, 有限体も完全体であるが, 有限体上の有理関数体は完全体でない. 準素分解においては基礎体上の有理関数体を 係数とする多項式環での計算を行うため, 基礎体の標数は 0に限られる.
命題 9.30 K が完全体なら,
0 次元イデアルI が radical ⇔I が,各変数について一変数無平方多項式を含む.
命題 9.31 K が完全体とすると, 0次元radicalイデアルIの零点の個数はdimKK[X]/I に等しい.
定義 9.32 多項式 f が f =f1e1· · ·fmem (fi は無平方) と書けたとき, f1· · ·fm を f の 無平方部分と呼ぶ.
系 9.33 I∩K[xi] = Id(fi(xi))とする.
√I =I +Id(h1,· · ·, hn)
(hi は,fi の無平方部分)
radicalイデアルに対しては, separating element の判定は次のように述べられる.
命題 9.34 K を完全体とし,イデアル I が 0 次元 radicalとする. f の最小多項式を g とすると,
f が separating element ⇔ deg(f) = dimKR/I
このようなf は存在する. K が無限体ならば, f としてX の元の線形和から選べる.
以上が, 完全体上の0次元イデアルの準素分解の概略である. 直前の命題に関連して, 次のことが成り立つ.
9.3. 0次元イデアルの準素分解 101 命題 9.35 (shape lemma)
I を完全体 K 上の 0 次元 radical イデアル とし, f を separating element とする.
z << X なる任意の順序のもとで, R[z]のイデアル IR[z] +Id(z−f) は {x1−f1(z),· · ·, xn−fn(z), z−fz(z), m(z)}
という形のグレブナ基底をもつ. この形の基底をshape basis と呼ぶ.
[証明]z の最小多項式 m は f の最小多項式に一致し, その次数はdimKK[X]/I と等 しくなる. z << X なる順序のもとでは, グレブナ基底は m を含み, モノイデアルを 考えれば,m 以外の元の頭項は各変数の1 次式以外ではありえない. 2
shape basisは, 0次元イデアルの零点を数値で求めようとする場合に, 見掛け上有効
な形をしている. 実際,I の零点は, fn(xn) の零点により, {(f1(α),· · ·, fn(α))|m(α) = 0}
と書ける. しかし, 有理数体上で実際にshape basis を求めて見ると,m の係数に比べ てfi の係数が極めて大きくなることが多い. この困難を克服するため, 次の方法が考 案された.
命題 9.36 (rational univariate representation; RUR)
前命題と同じ仮定のもとで,IR[z] +Id(z−f)の基底として, {m0x1−g1(z),· · ·, m0xz−gn(z), m(z)}
という形のものがとれる.
m は shape basisの場合と一致する. この基底によるの零点の表現は,
{(g1(α)
m0(α),· · ·, gn(α)
m0(α))|m(α) = 0}
と書ける. 多くの実例において, gi の各係数が, m の係数と同程度の大きさに押えら れることが分かっており, 0 次元 radicalの零点の表現としては RURによるものが優 れているといってよい. RUR の計算法としては,対称式による方法が最初に提案され ていが, modular change of ordering と同様の手法を適用することもでき, RUR が結 果の大きさ程度で計算できる [34].