\chapter{イデアルの分解}
イデアル $I \subset R=K[X]$ に対し, $I=I_1\cap I_2$ と書ける時, 
$V(I) = V(I_1) \cup V(I_2)$ が成り立つ. すなわち, イデアルの分解
は零点の分解を与える. より詳しく言えば, 零点の分解は radical の
分解に対応する. 零点を可能な限り分解することは, 代数的集合を
既約分解することに対応する. 方程式について言えば, 一般に解の
分解により, より扱いやすい解の表現を与えることができる. 

\section{素イデアル, 準素イデアル, 準素イデアル分解}

以下, $R=K[X]$ を固定して考える. 

\begin{df}
イデアル $I \subset R$ が素イデアル (prime ideal)とは, 
\begin{center}
$ab \in I$ かつ $a\notin I$ ならば $b \in I$
\end{center}
なること. これは $R/I$ が整域となることと同値. 
\end{df}

\begin{df}
イデアル $I \subset R$ が準素イデアル (primary ideal)とは, 
\begin{center}
$ab \in I$ かつ $a\notin I$ ならば $b \in \sqrt{I}$
\end{center}
なること. 
\end{df}

\begin{df}
イデアル $I \subset R$ が $I=\sqrt{I}$ を満たすとき $I$ は radical イデアル
であるという. $\sqrt{I}$ は radical イデアルである. 
\end{df}

\begin{lm}
$\sqrt{I} = \cap_{I\subset P:prime}P$
\end{lm}
\proof $I \subset P$ ならば $\sqrt{I} \subset \sqrt{P}=P$ より
左辺 $\subset$ 右辺. 右辺が左辺を真に含むとすれば, ある
$f \in \cap_{I\subset P:prime}P \setminus \sqrt{I}$ が存在する. このとき, 
$S=\{f,f^2,\cdots,\}$ とおけば, 
$S \cap \sqrt{I} = \emptyset$. 
$F = \{J:$ イデアル $\mid \sqrt{I} \subset J$ かつ $S \cap J = \emptyset \}$ と
おくと, $F \neq \emptyset$ で, 包含関係に関して帰納的. よって極大元 $J_0$
が存在する. 

\noi
\underline{主張\,} $J_0$ は素. 

\noi
\proof $ab\in J_0$ かつ $a, b\notin J_0$ とする. $J_0$ の極大性より, 
$S \cap (J_0+Id(a)) \neq \emptyset$ かつ $S \cap (J_0+Id(b)) \neq \emptyset$.
すなわち, ある自然数 $s,t > 0$, $c,d \in J_0$, $e,f \in R$ が存在して, 
$f^s=c+ae$, $f^t=d+bf$ と書ける. すると $f^{s+t}=abef+cd+aed+cbf \in J_0$
となり矛盾. よって $J_0$ は素. \qed

\noi
この主張により, $f \notin J_0$ かつ $I \subset J_0$ なる素イデアル $J_0$ が
存在する. これは矛盾. \qed

\begin{lm}
イデアル $I \subset R$ が準素ならば, $\sqrt{I}$ は素イデアル.
\end{lm}

\begin{df}
イデアル $I \subset R$ が準素で $\sqrt{I}=P$ のとき, $I$ は $P$-準素という. 
また $P$ を付属素イデアル (associated prime ideal)と呼ぶ. 
\end{df}

\begin{df}
イデアル $I \subset R$ が
\begin{center}
$I = I_1 \cap I_2 \Rightarrow I = I_1$ または $I = I_2$
\end{center}
を満たすとき, $I$ は既約という. 
\end{df}

\begin{lm}
既約イデアルは準素. 
\end{lm}
\proof $I$ が既約とし, $fg \in I$ かつ $f\notin I$ とする. 
$I:g^\infty = I:g^s$ なる $s$ をとると, 
$$I = (I+Id(g^s)) \cap (I+Id(f)).$$
これは, $h = a+bg^s = c+df$ ( $a,c \in I$ ) なる $h$ をとると, 
$$ bg^{s+1} = (c-a)g+dfg \in I \Rightarrow b \in I:g^{s+1}=I:g^s \Rightarrow
bg^s \in I \Rightarrow h \in I$$
からわかる. $I \neq I+Id(f)$ だから $I=I+Id(g^s)$. すなわち $g \in \sqrt{I}$.
\qed

\begin{th}
任意のイデアル $I \subset R$ は有限個の準素イデアルの交わりとして書ける. 
\end{th}
\proof $I$ が有限個の既約イデアルの有限個の交わりで書けることを
いえばよい. $I$ が既約でなければ, $I = I_1 \cap I_2$ と, $I$ を真に
含むイデアルの交わりで書ける. $I_1$ が既約でなければ, $I_1$ は同様の
交わりで書ける. もし, この操作が有限回で終らなければ, イデアルの真の
無限増大列が存在することになり, $R$ の Noether 性に反する. \qed

\begin{df}
イデアル $I$ の準素分解とは, $I=\cap_{i=1}^r Q_i$ ($Q_i$:準素) なる表
示のこと. 各 $Q_i$ を準素成分と呼ぶ. 準素分解が minimal とは, 全ての 
$\sqrt{Q_i}$ が相異なり, $\cap_{j\neq i} Q_j {\not \subset} Q_i$ なる
こと.
\end{df}

\begin{lm}
準素イデアル $I$, $J$ について, $\sqrt{I} = \sqrt{J}$ ならば $I\cap J$ も準素.
\end{lm}
\proof $ab \in I\cap J$ かつ $a\notin I\cap J$ とする. $a\notin I$
のとき, $b \in \sqrt{I}$, $a\notin J$ のとき $b\in \sqrt{J}$ が成り立つ. 
$\sqrt{I\cap J} = \sqrt{I} \cap \sqrt{J}$ より, $b \in \sqrt{I\cap J}$. \qed

\begin{th}
任意のイデアル $I \subset R$ は minimal な準素分解を持つ. 
\end{th}
\proof 補題より, 付属素イデアルが一致する準素成分は交わりをとることに
より一つにまとめることができる. その後, $\cap_{j\neq i} Q_j \subset Q_i$
なる $Q_i$ を取り除いても残りは $I$ の準素分解となるから, これを
繰り返して minimal な準素分解を得る. \qed

\noi
さらに, 次が成り立つ. 
\begin{th}
minimal な準素分解の長さは一意的で, 付属素イデアルは集合として一致する. 
\end{th}

\begin{df}
イデアル $I$ の準素成分 $Q$ の付属素イデアルが極小の時孤立 (isolated) と
いう. そうでないとき埋没 (embedded) という. 
\end{df}

\begin{re}
孤立, 埋没という名称は, その variety の様子による. 準素成分 $Q$ の付属
素イデアルを $P$ とする. $Q$ が孤立のとき, $P$ は他の付属素イデアルを
含まないから, variety でみれば, $V(P)$ は他の成分が定義する variety に
含まれない. 一方, $Q$ が埋没ならば, $P$ はある付属素イデアル $P'$ を含
むから, variety でみれば $V(P) \subset V(P')$ すなわち埋没している. 
\end{re}

\section{準素分解の概略}

準素分解のための主な手段は, {\bf イデアル商},
{\bf extension}, {\bf contraction} および多項式の因数分解である. 

\begin{lm}
イデアル $I$, $f \in R \setminus I$ に対し, $I:f^m = I:f^\infty$ なる
$m$ をとれば, 
$$I = I:f^\infty \cap (I+Id(f^m))$$
\end{lm}
\proof $h \in$ 右辺とすると, $hf^m \in I$ かつ $h=a+bf^m$ ($a \in I$)
とかける. よって $bf^{2m} = hf^m-af^m \in I$ すなわち $b \in I:f^{2m}=I:f^m$
これから $h \in I$. \qed

\begin{df}(extension)\\
$Y \subset X$ に対し, $I^e=K(Y)[X\setminus Y]I$ と定義する.
\end{df}

\begin{df}
イデアル $\dim(I)=d$ とすると, 次元の定義により, 
$|Y|=d$ なる independent set $Y \subset X$ がとれる. 
これを maximally independent set とよぶ. 
\end{df}

\begin{lm}
$Y$ が maximally independent set のとき
$I^e$ は $K(Y)$ 上 0 次元イデアル. 
\end{lm}
\proof 定義により, 全ての $x \in X\setminus Y$ に対し, 
$I \cap K[\{x\} \cup Y] \neq 0$ だから, $K(Y)$ 上で考えれば
$x$ の一変数多項式が $I^e$ 中に存在することになる. よって $I^e$ は
0 次元.\qed

\begin{lm}
$<$ を $Y < (X\setminus Y)$ なる block order とする. $G$ が $I$ の
$<$ に関するグレブナ基底ならば, $G$ は, $I^e$ の, 同じ order に
関するグレブナ基底. 
\end{lm}

\begin{df}(contraction)\\
イデアル $J \subset K(Y)[X\setminus Y]$ に対し, $J\cap K[X]$ を
$J$ の contraction とよび, $J^c$ と書く. 
\end{df}

\begin{pr}
$I$ をイデアル, $<$ を $Y < (X\setminus Y)$ なる block order とし, $G$ 
を $<$ に関する $I$ のグレブナ基底とする. このとき, 
$$f = \LCM\{HC(g) \mid g \in G\}$$
(ただし, $HC(g)$ は $K(Y)[X\setminus Y]$ の元としてとる) とすれば, 
$I^{ec} = I:f^\infty$
\end{pr}

これらと, 後で述べる 0 次元イデアルの準素分解を用いて, 次のアルゴリズム
が得られる. 

\begin{al} \cite{GTZ}
\label{gtz}
\begin{tabbing}
Input : イデアル $I \in R=K[X]$\\
Output : \= $I = \cap Q_i$ ($I$ の minimal な準素分解)\\
\> $P_i = \sqrt{Q_i}$ ($Q_i$ の付属素イデアル)\\

$Y \leftarrow$ maximally independent set modulo $I$\\
$\cap \bar{Q_i} \leftarrow I^e$ (0 次元) の $K(Y)$ 上の準素分解\\
$(f,s) \leftarrow$ $I^{ec} = I:f^\infty = I:f^s$ なる $f$ および $s$\\
$\cap R_j \leftarrow I+Id(f^s)$ の準素分解\\
return $\bar{Q_i}^c \cap (\cap R_j)$
\end{tabbing}
\end{al}

\noi
$I+Id(f^s)$ は $I$ を真に含むから, 停止性は保証される. このアルゴリズム
を実現するためには, 

\begin{itemize}
\item 0 次元イデアルの準素分解

\item maximally independent set の選び方
\end{itemize}

\noi
のアルゴリズムを与える必要がある. この内, maximally independent set
に関しては, 次の命題がある. 

\begin{pr}
$I$ をイデアルとし, $MB_<$ を, $R/I$ の,
全次数つき order  $<$ に関する monomial による
$K$-基底とする. 
このとき, $\dim(I) = =max(|U| \mid T(U) \subset MB_<)$.
\end{pr}

\noi
この命題に基づいて, 一つのグレブナ基底から, $\dim(I)$ を求めるアルゴリズム
が構成できる. 以下で, 0 次元イデアルの準素分解について概略を述べる. 

\section{0 次元イデアルの準素分解}

$I \subset R=K[X]$ を 0 次元イデアルとする. 

\begin{df}
$f \in K[X]$ が $I$ の separating element とは, 
$I$ の $\overline{K}$ 上の相異る零点 $a,b$ に対し, $f(a) \neq f(b)$
なること. 
\end{df}

\begin{df}
$f\in K[X]$ とする. $t \notin X$ なる不定元をとり, $R[t]$ のイデアル
$J = IR[t]+Id(t-f)$ を考えれば, $J$ も 0 次元イデアルより, 
$(I+Id(t-f)) \cap K[t] = Id(g(t))$ なるモニックな $g \in K[t]$ が存在する. 
$g$ を $f$ の $I$ に関する最小多項式と呼ぶ. 
\end{df}

\begin{pr}
$f$ を $I$ の separating element とし, $g$ を $f$ の最小多項式とする. 
このとき, 
$$g = g_1^{e_1}\cdots g_r^{e_r}$$
($g_i$ は$K$ 上既約) と因数分解すれば, 
$$I = (I+g_1^{e_1}) \cap \cdots \cap (I+g_r^{e_r})$$
は $I$ の準素分解で, 
$$\sqrt{I} = \sqrt{I+g_1} \cap \cdots \cap \sqrt{I+g_r}$$
は $\sqrt{I}$ の素イデアル分解となる. すなわち, $\sqrt{I+g_i}$ は
$I+g_i^{e_i}$ の付属素イデアル. 
\end{pr}

\noi
イデアルの seratating element は, 直接求めるのは困難である. 定義により, 
$\sqrt{I}$ の separating element が $I$ の seratating element となること
を用いて, $\sqrt{I}$ を計算し, separating element を求めることを考える. 

\begin{df}
体 $K$ が完全体とは, 既約多項式が全て分離的であること. 
\end{df}

\begin{re}
以下の命題, アルゴリズムでは, 基礎体が完全体であることを要求するものが
いくつかある. 標数 0 の体は全て完全体である. また, 有限体も完全体であ
るが, 有限体上の有理関数体は完全体でない. 準素分解においては基礎体上の
有理関数体を係数とする多項式環での計算を行うため, 基礎体の標数は 0
に限られる. 
\end{re}

\begin{pr}
$K$ が完全体なら, 
\begin{center}
0 次元イデアル $I$ が radical $\Leftrightarrow$ $I$ が, 各変数について
一変数無平方多項式を含む. 
\end{center}
\end{pr}

\begin{pr}
$K$ が完全体とすると, 0 次元 radical イデアル $I$ の零点の個数は
$\dim_K K[X]/I$ に等しい. 
\end{pr}

\begin{df}
多項式 $f$ が $f = f_1^{e_1}\cdots f_m^{e_m}$ ($f_i$ は無平方) と書けた
とき, $f_1\cdots f_m$ を $f$ の無平方部分と呼ぶ. 
\end{df}

\begin{co}
$I \cap K[x_i] = Id(f_i(x_i))$ とする. 
$$\sqrt{I} = I+Id(h_1,\cdots,h_n)$$
($h_i$ は, $f_i$ の無平方部分)
\end{co}

\noi
radical イデアルに対しては, separating element の判定は次のように
述べられる. 

\begin{pr}
$K$ を完全体とし, イデアル $I$ が 0 次元 radical とする. $f$ の最小
多項式を $g$ とすると,
\begin{center}
$f$ が separating element $\Leftrightarrow$ $\deg(f)=\dim_K R/I$
\end{center}
このような $f$ は存在する. $K$ が無限体ならば, $f$ として $X$ の元の線
形和から選べる.
\end{pr}

\noi
以上が, 完全体上の 0 次元イデアルの準素分解の概略である. 直前の
命題に関連して, 次のことが成り立つ. 

\begin{pr}(shape lemma)\\
$I$ を完全体 $K$ 上の 0 次元 radical イデアル とし, 
$f$ を separating element とする. 
$z << X$ なる任意の順序のもとで, $R[z]$ のイデアル $IR[z]+Id(z-f)$ は
$$\{x_1-f_1(z),\cdots,x_n-f_n(z),z-f_z(z),m(z)\}$$
という形のグレブナ基底をもつ. この形の基底を shape basis と呼ぶ. 
\end{pr}
\proof $z$ の最小多項式 $m$ は $f$ の最小多項式に一
致し, その次数は $\dim_K K[X]/I$ と等しくなる. $z << X$
なる順序のもとでは, グレブナ基底は $m$ を含み, モノイデアルを
考えれば, $m$ 以外の元の頭項は各変数の 1 次式以外ではありえない. \qed\\
shape basis は, 0 次元イデアルの零点を数値で求めようとする場合に, 
見掛け上有効な形をしている. 実際, $I$ の零点は, $f_n(x_n)$ の零点に
より, 
$$\{(f_1(\alpha),\cdots,f_n(\alpha))\mid m(\alpha) = 0\}$$
と書ける. しかし, 有理数体上で実際に shape basis を求めて見ると, 
$m$ の係数に比べて $f_i$ の係数が極めて大きくなることが
多い. この困難を克服するため, 次の方法が考案された. 

\begin{pr}(rational univariate representation; RUR)\\
\label{RUR}
前命題と同じ仮定のもとで, $IR[z]+Id(z-f)$ の基底として,
$$\{ m'x_1-g_1(z), \cdots, m'x_{z}-g_n(z), m(z)\}$$
という形のものがとれる.
\end{pr}
\noi
$m$ は shape basis の場合と一致する. この基底によるの零点の表現は,
$$\{({g_1(\alpha)\over m'(\alpha)},\cdots,{g_n(\alpha)\over
m'(\alpha)}) \mid m(\alpha)=0\}$$
\noi
と書ける. 多くの実例において, $g_i$ の各係数が, $m$ の係数と同程度の
大きさに押えられることが分かっており, 0 次元 radicalの零点の表現として
は RUR によるものが優れているといってよい. 
RUR の計算法としては, 対称式による方法が最初に提案されていが, 
modular change of ordering と同様の手法を適用することもでき, RUR が
結果の大きさ程度で計算できる \cite{NY2}. 

\section{準素分解の例}
次の例は, symplectic integrator と呼ばれる安定な積分スキームの
数値計算法に関して現れた方程式系である \cite{SYMP}. 

\vskip\baselineskip
{\small
$\left\{
\parbox[c]{6in}{
$d_1+d_2+d_3+d_4=1, c_1+c_2+c_3+c_4=1,$\\
$(6d_1c_2+(6d_1+6d_2)c_3+(6d_1+6d_2+6d_3)c_4)c_1
 +(6d_2c_3+(6d_2+6d_3)c_4)c_2+6d_3c_4c_3=1,$\\
$(3d_1^2+(6d_2+6d_3+6d_4)d_1+3d_2^2+(6d_3+6d_4)d_2+3d_3^2+6d_4d_3+3d_4^2)c_1$\\
$+(3d_2^2+(6d_3+6d_4)d_2+3d_3^2+6d_4d_3+3d_4^2)c_2+(3d_3^2+6d_4d_3+3d_4^2)c_3+3d_4^2c_4=1,$\\
$(3d_1+3d_2+3d_3+3d_4)c_1^2+((6d_2+6d_3+6d_4)c_2+(6d_3+6d_4)c_3+6d_4c_4)c_1$\\
$+(3d_2+3d_3+3d_4)c_2^2+((6d_3+6d_4)c_3+6d_4c_4)c_2+(3d_3+3d_4)c_3^2+6d_4c_4c_3+3d_4c_4^2=1,$\\
$(24d_2d_1c_3+(24d_2+24d_3)d_1c_4)c_2+(24d_3d_1+24d_3d_2)c_4c_3=1,$\\
$(12d_2^2+(24d_3+24d_4)d_2+12d_3^2+24d_4d_3+12d_4^2)d_1c_2
+((12d_3^2+24d_4d_3+12d_4^2)d_1$\\
$+(12d_3^2+24d_4d_3+12d_4^2)d_2)c_3
+(12d_4^2d_1+12d_4^2d_2+12d_4^2d_3)c_4=1,$\\
$4d_1c_2^3+(12d_1c_3+12d_1c_4)c_2^2+(12d_1c_3^2+24d_1c_4c_3
+12d_1c_4^2)c_2+(4d_1+4d_2)c_3^3$\\
$+(12d_1+12d_2)c_4c_3^2+(12d_1+12d_2)c_4^2c_3+(4d_1+4d_2+4d_3)c_4^3=1$
}
\right.$}

\vskip\baselineskip
\noindent
準素分解により, この方程式は以下のように分解されることが分かる. 

\vskip\baselineskip
$\left\{
\parbox[c]{8in}{
$24c_4^2-6c_4+1=0$\\
$c_1=-c_4+{1\over 4}$,
$c_2=-c_4+{1\over 2}$,
$c_3=c_4+{1\over 4}$
$d_1=-2c_4+{1\over 2}$,
$d_2={1\over 2}$,
$d_3=2c_4$,
$d_4=0$}
\right.$

$\left\{
\parbox[c]{8in}{
$6c_4^3-12c_4^2+6c_4-1=0$\\
$c_1=0$,
$c_2=c_4$,
$c_3=-2c_4+1$
$d_1={1\over 2}c_4$,
$d_2=-{1\over 2}c_4+{1\over 2}$,
$d_3=-{1\over 2}c_4+{1\over 2}$,
$d_4={1\over 2}c_4$}
\right.$

$\left\{
\parbox[c]{8in}{
$48c_4^3-48c_4^2+12c_4-1=0$\\
$c_1=c_4$,
$c_2=-c_4+{1\over 2}$,
$c_3=-c_4+{1\over 2}$
$d_1=2c_4$,
$d_2=-4c_4+1$,
$d_3=2c_4$,
$d_4=0$}
\right.$

$\left\{
\parbox[c]{8in}{
$6c_4^2-3c_4+1=0$\\
$c_1=0$,
$c_2=-c_4+{1\over 2}$,
$c_3={1\over 2}$
$d_1=-{1\over 2}c_4+{1\over 4}$,
$d_2=-{1\over 2}c_4+{1\over 2}$,
$d_3={1\over 2}c_4+{1\over 4}$,
$d_4={1\over 2}c_4$}
\right.$