多項式環上の素イデアル分解について(数式処理における理論とその応用の研究)

2.

多項式環上の素イデアル分解について

下山武司

野呂正行

横山和弘

(

富士通情報研

)

2.1

素イデアル分解と代数拡大体上の因数分

解

素イデアル分解の流れ

$\mathrm{Q}[x_{1}, \ldots, x_{n}]$

:

有理数体$\mathrm{Q}$ 上の多項式環 ($\mathrm{Q}[X|$ と略記)

$I$ : $\mathrm{Q}[X]$ のイデアル.

一般にイデアル $I$ _の radical の素イデアル分解 (prime decomposition) は, 次の様な流れで行わ

れる. $\mathrm{Q}[X]$ のイデアル $I$ $\Downarrow$ イデアルの 0-次元化 $\Downarrow$ イデアルの radical化 $\Downarrow$ 0-次元radical の素イデアル分解 イデアルの 0-次元化

上の $0$-次元イデアル. 又 $I^{\epsilon c}=I^{\mathrm{e}}\cap \mathrm{Q}1X1$ と置いたときに $\sqrt{I}=\sqrt{I^{\mathrm{e}c}}\cap\sqrt{Id(I,f)}$ を満たす多項式$f$ が求められる. これ以降, 体$\mathrm{K}$ を _{$\mathrm{K}=\mathrm{Q}(U)$} と置いて, イデアルは $\mathrm{K}[x_{1},$ $\ldots,$$X_{r}1=\mathrm{K}[X]$ 上0- 次元の物であると 考える. 0-次元イデアルの radical 化

$\mathrm{K}[x_{1}$,...,$x_{r}]$ 上の $0$-次元イデアル$I$ に対し, 各$i=1,$

$\ldots,$$r$ に付いて $I\cap \mathrm{K}[xi]=Id(f_{i})$ となる$x$

.

の

変数多項式$f_{i}$ を取る. この時, 次が言える.

$I$ が$\mathrm{r}\mathrm{a}\mathrm{d}\mathrm{i}\mathrm{C}\mathrm{a}\mathrm{l}\Leftrightarrow$ 全ての $f_{i}$ が$\mathrm{K}$ 上既約

代数拡大体上の因数分解

$\mathrm{K}$ の successive extension を考える. $\mathcal{K}=\mathrm{K}(\alpha_{1}, \ldots, \alpha_{r})\mathrm{s}.\mathrm{t}$. $p_{1}(\alpha_{1})=0,$ $p_{2}(\alpha_{1}, \alpha_{9})\vee=0,\ldots$, $p_{l}.(\alpha_{1}, \ldots, \alpha_{r})=0$

$\mathcal{K}$ の上で $\mathrm{K}[x]$ の square-free 多項式$f(x)$ を分解することは剰余環

$\mathcal{H}=\mathrm{K}[x_{1} , ..., x_{r}, x]/Id(p\mathrm{l}(x_{1}), \ldots, p_{r}(X_{1}, \ldots, X_{r}), f(X))$

を次の様な体$\mathcal{L}$: への直和分解を与えることと同値である.

(A) $\mathcal{H}=\mathcal{L}_{1}\oplus\cdots\oplus \mathcal{L}_{m}$

ちなみに各体$\mathcal{L}$

:

が$\mathrm{K}\iota X_{1},$

$\ldots,$$X_{r},$$X$]

$/P_{i}$ ($P_{i}$ は maximal ideal) で与えられ,

$\mathrm{K}(x_{1}, \ldots, xT)[x]Pi=Id(f_{i})$

と書けたとき, $\mathrm{K}(x_{1}, \ldots, x_{r})[X1$ の多項式$f_{i}$ \iotaよ,$f$ の素因子で,

$f=f_{1},$.$.f_{m}$.

剰余環の分解 $(A)$ _{は, 最も素朴には Norm を計算し}, _{因数分解すればよい.}

$N_{orm}(f(X-\beta), \alpha 1, \ldots, \alpha_{r})=Id(f(x-\beta),p_{1}, \ldots,p_{r})\cap \mathrm{K}[x]$

ただし, $\beta$ は $\mathcal{K}$ の primitiveelement

0- 次元 radical イデアルの素イデアル分解

これ以降, 月よ $\mathrm{K}[X]$ 上0- 次元 radical イデアルとする.

$I$ の素イデアル分解$P_{1}\cap\ldots\cap P_{r}$ を考える. _ここで,$P$

.

_は, $\mathrm{K}1X$] のmaximal ideal. これは, $\mathrm{K}[X]/I$

の体の分解

を与えることと同値.

式$(\mathrm{A}),(\mathrm{B})$ を見比べる事で,次が言える.

0-次元radical ideal の素イデアル分解

$\Uparrow$ 本質的に同じ 代数拡大体上の因数分解

$\mathrm{K}[x_{1}, \ldots, x_{r}]$ イデアル $I$ _の primitiveelement をそのまま求めるのは非常に重い計算

.

$\Downarrow$

変数 $x_{1},$$\ldots,$$x_{r}$ を代数的数と見なし successivefactorization したほうが計算効率がよい.

Successive

Algebraic

Factorization

の素イデアル分解への応用

$\mathrm{K}[x_{1}, \ldots, x_{r}]$ _の $0$-次元radical ideal $I$ をsuccessive algebraic factorization を応用して次の様な素イ

デアル分解algorithm が考えられる.

(1)$I\cap \mathrm{K}[x_{1}]$ の生成元 $g(x_{1})$ を求める.

(2)$g(x_{1})$ を因数分解し $g=g_{1}\cdots g_{m}$. とする. これより

$I=Id(I, g_{1}(x_{1}))\cap\cdots\cap Id(I, \mathit{9}m(x1))$

.

(3)ここで $Id(I, g_{1}(x_{1}))$ を取る.

$\alpha_{1}$ を $g_{1}(\alpha_{1})=0$ を定義多項式とする代数的数とすると, 次の同型が成り立つ $\mathrm{K}[x_{1}$,...,$x_{r}]/Id(I, g_{1}(x_{1}))=\mathrm{K}(\alpha 1)[x_{2}, \ldots, x\mathcal{T}]/I|_{x_{1}\alpha_{1}}=$.

$I|_{x_{11}}=\circ$ を $I_{1}$ と置き直すと, $I_{1}$ は, $\mathrm{K}(\alpha_{1})[x_{9},, \ldots, x_{r}]$ の0-次元radical イデアルである.

(4)続いて, $I_{1}\cap \mathrm{K}(\alpha_{1})[x_{2}]$ の生成元 $h(x_{2})$ を取る. ($h$ は, $\alpha_{1}$ を係数に持つ

–

変数多項式

.

)

(5)$h(x2)$ を代数拡大体$\mathrm{K}(\alpha_{1})$ 上で因数分解する.

$h(x_{2})$ の素因子$h_{1}\in \mathrm{K}(\alpha_{1})[X2]$ に対し, $h_{\mathit{0}}(\alpha_{2})=0$ を定義多項式に持つ代数的数$\alpha_{2}$ を取ると, 上

と同様に次の同型が成り立つ.

$\mathrm{K}[X_{1}, \ldots, x_{r}]/Id(I, g1(x_{1}),$$h1(X1, X2))=\mathrm{K}(\alpha 1, \alpha_{2})[xs, \ldots, X_{\tau}]/I|_{x_{1}=}\alpha_{1,22}x=\alpha$

.

これを $x_{3},$$\ldots,$$x_{r}$ と繰り返せば, 次の様な剰余環の体への分解が得られる.

$\mathrm{K}[X]/I=\bigoplus_{i=\iota}^{d}\mathrm{K}(\alpha i,1, \ldots, \alpha_{i,r})$

.. ただし, $d=\dim_{\mathrm{K}^{\mathrm{K}[X}}$]$/I$ である. $\mathrm{t}\alpha_{i,1},$ $\ldots,$$\alpha_{i,r}\}_{i1,\ldots,d}=$ の定義多項式より $I$ の素イデアル分解が計算できた

.

参考:

.

Successive

Algebraic factorization は, Anai, H. , Noro M.

,

Yokoyama K. (1995) を参照.

$\circ$有理数雪上のイデアルの最少多項式は “Linear solving and Hensel Lifting” によって効率的に計算.

(

参照

:

野呂正行 $\lceil \mathrm{G}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}$

.

有理数体上代数拡大体上の GCD 計算は, ChineseRemainder を利用すると効率的

2.2

$Id(P, S)$

_{で表されるイデアルの素イデア}

ル分解

背景 : 下山&横山による準素イデアルアルゴリズム Theorem $R$ のイデアル $I$ とその separator 系 $S_{1},$

$\ldots,$$S_{r}$ を取る. 各

$i$ に対し, $\overline{Q}_{i}=IR_{S_{i}}.\cap R$,

$si= \prod_{s\in S}:^{S}$

’

と置き翫を

(I: $s_{i}^{k:}$)_{$=IR_{s_{i}}\cap R$} を満たす自然数とする. _{$I’=Id(I, S_{1}k_{1} , . . . , s_{r}^{k_{f}})$} と

置くと

(C) $I=\overline{Q}_{1}\cap\cdots\cap\overline{Q},$_. $\cap I’$_,

が成り立つ. 更に, $I’=R$ あるいは diln$(I’)<\dim(I)$ のいずれかが成り立つ.

Definition 上の分解 (のを pseudo-primary decompsition と呼ぶ. また, 各$\overline{Q}_{i}$ を $I$ _の

pseudo-primary component, $I’$ _を pseudo-primary decomposition _の remaining _{colnponent と呼ぶ}.

Corollary $\sqrt{I’}=\sqrt{Id(P_{1},s_{1})}\cap\cdots\cap\sqrt{Id(P_{l},s_{r})}$.

Theorem pseudo-primary ideal $I$ に対し, $Q$ を $I$ の唯–の isolatcd $pr\cdot irna\prime\prime’ y$ component, $f$ を extractor とする. $k$ を $IR_{f}\cap R=(I : f^{k})$ を満たす自然数, $I’$ _{をイデアル} $Id(I, f^{k})$ _とすると

$Q=IR_{f}\cap R$ であり, つぎが成り立つ.

(D) $I=Q\cap I^{J}$.

更に, $I’=R$ あるいは $\dim(I)>\dim(I’)$ が言える.

Definition $I$ を pseudo-primary ideal, $P$ をその radical とする. 上の Theorem _の decomposition

$(D)$ を $I$ から $Q$ のextraction と呼び, $I’$ _を extraction _の remainingcomponent. _と呼ぶ.

Corollary $\sqrt{I’}=\sqrt{Id(P,f)}$.

Special Prime Decomposition ofRadicals

pseudo-primary decomposition または extraction の入力イデアル$V$ を取る.

radical$\sqrt{V}$ の素イデアル分解は, -つの素イデアル $P$ に–つの要素$f$ を加えたもので生成される

イデアル $Id(P$_,

_{のの素イデアル分解に帰着できる}

.

$\Downarrow$

Procedure (E) PrimaryDecomposition$(I, d)$

Input: A positive integer$d$and an ideal $I$ suchthat _{$\dim(I)\leq d$}.

Output: A set $P\mathcal{L}$ ofisolated prime divisor of$I$with dimension $d$.

begin

$P\mathcal{L}arrow\{\},$ $Jarrow I$

$\mathcal{U}arrow \mathrm{t}\mathrm{h}\mathrm{e}$set ofall maximalstrongly independent sets

modulo $I$with $d$ elements

for all $U$ in$\mathcal{U}$ do

If$U$ is not a strongly independent setmodulo $J$

then continue

$p*arrow \mathrm{t}\mathrm{h}\mathrm{e}$set of allprime divisor of$I$computed in $\mathrm{Q}_{U}$

$P\mathcal{L}arrow\{P^{*}\cap R|P^{*}\in P^{*}\}\cap \mathcal{P}\mathcal{L}$

$Harrow \mathrm{a}$ Gr\"obnerbasis of$I$with respect to ablock

order $U\ll X\backslash U$

$farrow\iota_{Cm}\{Hc_{u}(g)|g\in H\},$ $Jarrow Id(J, f)$

return $P\mathcal{L}$

end

Mathematical Background ofSpecail Procedure

Proposition 素イデアル $P\mathrm{o}$ と $P\mathrm{o}$ に含まれない $R$ の要素 $s$ に対しイデアル $Id(P_{\mathrm{O}}, S)\neq R$ の isolated prime は全て次元が等し$\langle$

$\dim(P_{\mathrm{O}})-1$ である.

Lemma $I$ を $R$ のイデアルとし, $I$ _の isolated prime の中で最大の次元を持つものを $P$ _とする. す

ると, 任意の admissible order $<$ に付いて, 全ての $P$ に関する maximal strongly independent set $U$ は, また $I$ に関する maximal$Strong\iota_{y}$ independent set にもなる.

Remark 次の事柄は, Procedure $(E)$ の効率のよさを示している.

(1) 有理関数体上の $\mathit{0}$-次元イデア)の prime decomposition の回数は, $I$ の isolate\’a$p?\dot{\tau}me$ の個数

で押さえられる.

(2) 有理関数体上の $\mathit{0}$-次元イデアルの

$P^{7}\dot{\eta}rne$ decomposition は, $I$ に対してのみ行われる.

(3) Remainingideal $J$ は, 変数が sirong independent かどうかを確かめるのに用いる. そのチェッ

クには, 任意の order に対する Gr\"obner 基底が使える.

Implememtation ofPrime Decomposition

(F) $\sqrt{Id(I,fg)}=\sqrt{Id(I,f)}\cap\sqrt{Id(I,g)}$

(G) $\sqrt{I}=\sqrt{(IR_{f}\cap R)}\cap\sqrt{Id(I,f)}$

Implementation of the General Procedure

$I$ を $R$の任意の ideal とする. $(Qu:=\mathrm{Q}(U)[X\backslash U].)$

(1)分解式 (F) 及び (G) を用いて, 次の様なイデアル $J_{i}$ を計算する.

(i) $\sqrt{I}=\sqrt{J_{1}}\cap\cdots\cap\sqrt{J_{s}}$,

(ii) $J_{i}$ の Gr\"obner 基底の全ての要素は $R$ 上の多項式として既約である.

(iii) $J\dot{.}$ に関する maximal strongly independent set $U_{i}$ に対して

$J:\mathrm{Q}_{U}:\cap R=J_{i}$

(2) 各 $J_{*}$ に対し, 全ての primecomponent を次の様にして求める.

(2.1) $\mathrm{Q}_{U}$

: の0-次元イデアル $J_{i}\mathrm{Q}_{U}$

: に対しその radical $J_{i}’$ を計算する.

(2.2) $J_{i}’$ の prime decomposition を計算する.

(2.3) 各 $P’.,j$ に対し, $R$への contraction $P_{i,j}(P_{i,j}=P_{i,j^{\cap}}’R)$ を計算する.

. 各 $P_{i,j}$ は, $R$ の素イデアルでかつ$\sqrt$

Ji

$=P_{i,1}\cap\cdots\cap Pi,1:$.

(3)$P_{i,j}$ の中で余分な component を取り除$\langle$. (component

$P_{i,j}$ が余分なものかどうかは, $P_{i,j}$

が別の component$P_{i’,j’}$ を真に含むかどうかで判定できる)

Implementation of the Special Procedure

Procedure をより実用的にするために decomposition (F) を組み込む.

Pre-Procedure: 与えられたイデアル $I$ _に $(\Gamma)$ を適用するために\psi $=\sqrt{I_{1}}\cap\cdots\cap\sqrt{I}$, かつ各 $I_{i}$

の Gr\"obner 基底の全ての要素は $R$ の多項式として既約となるイデアル $I_{i}$ を計算する.

Procedure (PrimeDecomposition$(I)$ (special version))

Input: An ideal $I$such that every isolated prime divisor has thesame dimension.

Output: Aset $P\mathcal{L}$ of all prime divisors of$\sqrt{I}$.

begin

$\mathcal{P}\mathcal{L}arrow\{\},$ $darrow\dim(I)$

$\mathcal{I}$ -the set of all ideals obtained by Pre-Procedure. for each $J$in$\mathcal{I}$

if$\dim(J)\neq d$then continue

if$J$ is prime then $P\mathcal{L}arrow\{J\}\cup P\mathcal{L}$

else $P\mathcal{L}arrow Specia\iota P?^{\urcorner}in\mathrm{z}eDeCompoSiti_{on(}d,$$J$) $\cup P\mathcal{L}$

return $P\mathcal{L}$

end

Remark 経験的には, 非常に多くの例で pre-procedure decomposition ですでに prime

ノレは 1474 固, そのうちの

142

個 (96.6%) がすでに素イデアルであった. すなわち, 多くの場合この procedure は, 初めの素イデアル判定のところで終了する.

参考文献

$[1]\mathrm{A}\mathrm{h}_{0},$ $\mathrm{A}.\mathrm{V}.$, Hopcroft, J.E., Ullman, $\mathrm{J}.\mathrm{D}$. (1974). The Design and Analysis

of

Computer Algo-rithms. Addison-Wesley, Reading, MA.

[$21^{\mathrm{A}\mathrm{n}}\mathrm{a}\mathrm{i}$, H.

,

Noro M.

,

Yokoyama K. (1995). Computation

of

the splitting

fields

and the Galois groups

_of

polynomials. MEGA ’94.

$[3]\mathrm{A}\mathrm{t}\mathrm{i}\mathrm{y}\mathrm{a}\mathrm{h},$ $\mathrm{M}.\mathrm{F}.,$$\mathrm{M}\mathrm{a}\mathrm{C}\mathrm{D}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{d},$$\mathrm{I}.\mathrm{G}$. (1969). Introduction to CommutativeAlgebra. Addison-Weslev, Reading, MA.

$[4]\mathrm{A}1_{\mathrm{o}\mathrm{n}\mathrm{s}}0,$ $\mathrm{M}.\mathrm{E}.$, Mora, T., Raimondo, M. (1990). Local decomposition algorithms. AAECC-8,

Springer LNCS 508, 208-221.

$[5]\mathrm{B}\mathrm{a}\mathrm{c}\mathrm{k}\mathrm{e}\mathrm{l}\mathrm{i}\mathrm{n}$, J., Fr\"oberg, R. (1991). How we prove that there are exactly 924 cyclic 7-roots. Proceedings of ISSAC’91, ACM Press, 103-111.

[$61^{\mathrm{B}}\mathrm{e}\mathrm{C}\mathrm{k}\mathrm{e}\mathrm{r}$, T., Weispfenning, V. (1993). Gr\"obner Bases. Springer-Verlag, New York.

$[7]\mathrm{B}\mathrm{o}\mathrm{e}\mathrm{g}\mathrm{e}$, W., Gebauer, R., $\mathrm{I}\sigma_{\mathrm{r}\mathrm{e}}\mathrm{d}\mathrm{e}1$, H. (1986). Some examples for solving systems of

algebraic

equations by calculating Gr\"obnerbases. J. Symb. Comp. 1, 83-98.

$[8]\mathrm{B}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}$, B. (1965). Ein Algorithmus zum Auffinden der Basiselemente des

Restklassen-ringesnacheinem nulldimensionalenPolynomideal. DoctoralDissertation Math. Inst.

Univer-sity of Innsbruck, Austria.

$[9]\mathrm{B}\mathrm{u}\mathrm{C}\mathrm{h}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{r}$, B. (1985) Gr\"obnerbases: An algorithmicmethod in polynomial ideal theory. In:

Bose, $\mathrm{N}.\mathrm{K}$

.

(ed.), MultidimensionalSystems Theory, Reidel, Dordrecht, 184-232.

$[10]\mathrm{E}\mathrm{i}_{\mathrm{S}\mathrm{e}\mathrm{n}\mathrm{b}}\mathrm{u}\mathrm{d}$, D., Huneke, C., Vasconcelos, W. (1992). Directmethods forprimary decomposition. Inventiones Mathematicae, 110,

207-235.

$[11]\mathrm{G}\mathrm{i}\mathrm{a}\mathrm{n}\mathrm{n}\mathrm{i}$, P., Trager, B., Zacharias,

G.

(1988). Gr\"obner bases and primary decomposition of polynomial ideals. J. Symb. Comp. 6,

149-167.

$[12]\mathrm{G}\mathrm{r}\ddot{\mathrm{a}}\mathrm{b}\mathrm{e}\mathrm{H}.\mathrm{G}$

.

(1994).

On

factorized Gr\"obner bases. To appear in Proc. Computer Algebra in

Scienceand Engineering.

[$131^{\mathrm{G}}\mathrm{r}\ddot{\mathrm{a}}\mathrm{b}\mathrm{e}\mathrm{H}.\mathrm{G}$. (1995). CALI–A REDUCE package for constructive commutative algebra,

Ver-sion 2.2.1. (anonymous ftp from aix550. informatik.$\mathrm{u}\mathrm{n}\mathrm{i}$-leipzig. de)

$1^{14}1^{\mathrm{K}\mathrm{a}\mathrm{l}\mathrm{k}\mathrm{b}\mathrm{r}\mathrm{e}}\mathrm{n}\mathrm{e}\mathrm{r}$, M., Sturmfels,B. (1993). Initial complexes ofprimeideals. To appearin Advances

in Mathematics.

$[16]\mathrm{K}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{e}\mathrm{l}$, H., Weispfenning, V. (1988). Computingdimension and independent sets for polyno-mial ideals. J. Symb. Comp. 6, 231-247.

[$17\mathrm{l}\mathrm{L}\mathrm{a}\mathrm{z}\mathrm{a}\mathrm{r}\mathrm{d}$, D. (1985). Ideal bases and primary decomposition: Case of two variables. J. Symb. Comp. 1, 261-270.

$[18]\mathrm{N}\mathrm{a}\mathrm{g}\mathrm{a}\iota \mathrm{a}$, M. (1962). Local Rings. Tracts in Mathematics Number 13, Interscience Publishers,

New York.

$[19]\mathrm{N}_{\mathrm{o}\mathrm{r}}\mathrm{o}$, M., Takeshima, T. (1992). $\mathrm{R}\mathrm{i}\mathrm{s}\mathrm{a}/\mathrm{A}\mathrm{s}\mathrm{i}\mathrm{r}$– a computer algebra system. Proceedings of

IS-$\mathrm{S}\mathrm{A}\mathrm{C}’ 92$, ACMPress, 387-396. (anonymousftp from (133.12.50. 13) $\mathrm{f}\mathrm{t}\mathrm{p}$

.

mm.sophia.$\mathrm{a}\mathrm{c}$

.

jp,

directory $/\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{r}$)

[$2\mathrm{o}1^{\mathrm{o}_{\mathrm{a}\mathrm{k}\mathrm{u},\mathrm{T}}}$.(1994). Computation of the characteristic variety and the singular locus of a system of differential equations withpolynomial coefficients. Japan J. Indust. Appl. Math. 11, 485-497.

$[21]\mathrm{R}\mathrm{u}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{n},$$\mathrm{E}.\mathrm{w}$. (1992). Gr\"obnerbasesandprimarydecompositionof modules. J. Symb. Comp.

14,483-503.

$[22]\mathrm{s}\mathrm{h}\mathrm{i}\mathrm{m}\mathrm{o}\mathrm{y}\mathrm{a}\mathrm{m}\mathrm{a}$, T.,Yokoyama, K.(1994). Localizationandprimary decompositionof polynomial ideals.

FUJITSU ISIS

Research Report,

ISIS-RR-94-10E.

$[23]\mathrm{w}\mathrm{a}\mathrm{n}\mathrm{g}$, D. (1992). Irreducible decomposition ofalgebraic varieties via characteristic sets alltl

Gr\"obnerbases. Computer Aided Geometric Design 9, 471-484.

[24|Zariski,O., Samuel, P. (1958/60). Commutative Algebra, vols. I, II. Van Nostrand, Princeton,