数理解析研究所講究録920 巻 1995 年 125-132

125

14.
Computation of Essentially Different
Puiseux Expansions via Extended
Hensel Construction
椎原浩輔 (筑波大数学系)

14. 1 は$\mathrm{b}^{\backslash ^{\backslash }}$めに

本論文では、 2 変数多項式 $P(x, y)\in \mathrm{C}$ が与えられたとき、 Puiseux 級数として表されるその多項式の解 $y=f.(x),$ $1\leq i\leq\deg_{y}(f)$ の中で本質的に異なる展開 (2 つの Puiseux 級数が相異なる分枝を定めるとき、 それらは本質的に異なると定義する) を効率的に求める算法について述べる。

Puiseux 級数を求める算法としては古典的な Newton 多角形を用いる Newton-Puiseux 法や$\mathrm{T}.\mathrm{C}$.

Kuo による Newton-Puiseux 法の–般化による算法等が、 本質的に異なる Puiseux 級数を求める算法については D.Duval による有理 Puiseux 級数算法などが挙げられるが。 これらはいずれも正確な記号計算を前提としたアルゴリズムであり、与えられた多項式が複雑になるにつれて、 その級数展開の係数も複雑になるのが–般的である。それゆえに著しい効率の低下が起こってしまう。
そこで、 本論では浮動小数演算を導入し、係数を数値的に取り扱って効率の低下を防ぐことを第に考える。上に挙げた各種の算法では、係数に含まれる誤差によって挙動が不安定となる場合がしばしば現れる。そこで我々は佐々木・加古による拡張された Hensel 構成法 (これは係数が数値近似された場合にはこれまでのどの算法よりも安定である) に基づく算法を示す。

126

14.2 拡張された Hensel 構成法
本節では、佐々木加古 [8] によって提案された、拡張された Hensel 構成を用いる Puiseux 展開法

について簡潔に述べる。与えられる多項式を $F(x, y)\in \mathrm{C}[x, y]$ とし、 $F(x, y)$ は既約で、てかつ $F(0, y)=y^{d}$ と仮定して$\mathrm{m}\mathrm{o}\mathrm{n}\mathrm{i}\mathrm{c}_{\backslash }$(これらは–般性を失うことなく仮定できる)、$y$につい原点 $(0,0)$での Puiseux 級数展開を求める。

定義 14.2.1. (Newton 多項式)項式$F^{(0)}$与えられた多項式 $F(x, y)$ に対して、 以下の手順で Newton 多を定める。

1.

各単項式。・ガガに対して $(\deg y, \deg x)-$ 車面に点 $(j, i)$ をプロットする。

2.

点 $(d, 0)$ を通る直線で、すべての点がその直線上あるいはその上側にあるようなもののうち傾きが最小の直線を3.

$L$$L$とする。

上にプロットされているすべての単項式の和を $F^{(0)}(x, y)$ とする。
$\blacksquare$

Newton 多項式は $F(x, y)$ によって–意的に定まる。

注意 14.2.2.

すると Newton 多項式は $(\deg y)/d+(\deg x)/\delta=1$ と書けるから、$y^{d},$$y^{d-2}x2\delta/d,$$y^{d-\iota}x\delta/d,$$\ldots$によって構成される。 また、 正整数$F^{(0)}(1, y)$を$\mathrm{C}$$\hat{\delta},\hat{d}$を$\hat{\delta}/\hat{d}=\delta/d,$$y$$F^{(0)}$を満たすものとする。

$\zeta_{1},$と$x^{\delta/d}$についての斉次多項式だから、$\zeta_{r}\in \mathrm{C}$,for any$\zeta_{\iota}\neq\zeta_{J}$$I_{k}$$\blacksquare$$F^{(0)}(x, y)\in \mathrm{C}[x^{\delta/d}, y]$$\dot{\iota}\neq J$

を(1)と因数分解できる。次にイデアル $I_{k}(k=1,2, \ldots)$ を以下のように定める。

このとは$F^{(0)}(_{X}, y)=(y-\zeta_{1}X\delta/d)m_{1}\ldots(y-\zeta_{r^{X}}/d)\delta m_{r}$$I_{k}$$\delta$$x^{d\delta/d}$$\mathrm{g}\mathrm{c}\mathrm{d}(\dot{\delta},\hat{d})=1$$\ldots,$

はの $\deg x$ 軸との切片を上で以下のように因数分解する。

$F^{(0)}(1, y)=(y-(_{1})^{m_{1}}\cdots(y-\zeta_{r})^{m_{r}},$$F^{(0)}(x, y)$

,

$L$

$=$

$(y^{d}x^{(k+)}0/\dot{d}, y^{d-1}x^{(k}+\dot{\delta})/\dot{d},$$y^{d-2}x^{(}k+2\dot{\delta})/\dot{d},$$y^{0}x^{(+})kd\dot{\delta})/\dot{d}$$\ldots,$

を Hensel 構成の法として用いる。上の因数分解 (1) を次のように書き直す。
$F^{(0)}=G_{1}^{(0})(X, y)\cdots G(0)(rx, y)$,

このとき以下の補題および定理が成立する。

$G^{(0)}.\cdot(x, y)=(y-\zeta_{\mathrm{i}X^{\dot{\delta}/})^{m}}\hat{d}.,$$(i=1, \ldots, r)$127

補題 14.2.3. (Lagrange’s interpolation Polynomials)$\mathit{1}=0,$$\ldots,$$d-1$ に対して

$W_{1}^{(\iota)(}[G_{1}).G^{()}/0..0c^{(0)}]r1+\cdots+W(\iota)[rc_{1}(0)\ldots G_{r}(0)/c_{\Gamma}^{(})]0=yx(\iota\dot{\delta}/\dot{d})(d-1)$$\deg_{yi}(W^{(\iota_{)}}(x, y))<\deg_{y}(G_{i}(x, y))$を満たす多項式集合 $(W_{l}^{(l})(x, y)|i=1,$
定理 1424

任意の正整数$k$$\ldots,$,$(i=1, \ldots, r)$がただ– つ存在する。

$r\}$$\blacksquare$に対して$F(x, y)$$G_{l}^{(k)}(x, y)$$\equiv$$G_{1}^{(k)}(X, y)\cdots G^{(k)}\Gamma(x, y)$$\equiv$$G^{(0)}(|x, y)$(mod$I_{1}$(mod),$I_{k+1}$)$(i=1, \ldots, r)$を満たす $G_{i}^{(k)}(x, y)$ を構成できる。

$\blacksquare$

上の構成は次のようにして行なわれる。 まず、 $G_{i}^{(k-1)}(x, y),$ $(i=1, \ldots, r)$ が求まったとして、$F(x, y)-G_{1}(k-1)(x, y)\cdots G(k-1)r\equiv f_{d-1}\cdot y^{d-1}x^{\dot{\delta}/}\dot{d}+\cdots+fo\cdot yx0d\dot{\delta}/\dot{d}$(mod$I_{k+1}$)を計算し、次式で $G_{l}^{(k)}(x, y)$ を構成すればよい。

$G_{l}^{(k)}(x, y)=^{c_{l}^{()}(x,y)+\sum_{0}^{-}y)f}k-1dl=1W|(\iota)(_{X},((.x),$$(\dot{\iota}=1, \ldots, r)$(2)14.3
本節では、 前節で述べた拡張された Hensel 構成に対する考察を行ない、 本質的に異なる Puiseux

級数展開法の効率化について述べる。
定義 1431. (共役).

次の条件を満たすとき、$\exists\theta\in \mathrm{C}[x^{1}/\dot{d}, y]$$\mathrm{s}$.t.

$G_{1)}G_{2}\in \mathrm{C}[x^{\iota/\dot{d}}, y]$は共役であるという。

$G_{1}(x^{1/\dot{d}}, y)=G_{2}(ex2\pi\cdot\theta/\dot{d}1/\dot{d}, y)$$\blacksquare$

定義 1432.

$\theta,\hat{d}\in \mathrm{Z}$に対して、写像$\pi_{\theta,\dot{d}}$:$\mathrm{C}[x^{1/\dot{d}} , y]arrow \mathrm{C}[x^{1/\dot{d}}, y]$$\pi_{\theta,\dot{d}}(G(X1/\dot{d}, y))=G(e^{2\pi 1}.x^{1}\theta/\dot{d}/\dot{d})y)$,を次のように定める。

$\forall G\in \mathrm{C}[x^{1/\dot{d}}, y]$$\blacksquare$

定義 1433

2 つの級数 $f,$$g\in \mathrm{C}\langle\langle x\rangle\rangle$$\pi_{\alpha,\beta}(f)=g$が本質的に異なるとは、次の条件を満たすときと定める。

を満たすいかなる整数$\alpha,$$\beta$も存在しない

128$\blacksquare$

補題 1434

任意の$k\in \mathrm{Z}^{+}$に対して $c_{1}(k).G\rangle\cdot(k)r\in \mathrm{C}[x, y]$

省略。

証明

補題 1435.

存在すれば、$\blacksquare$$G_{J}^{(0)},$$G_{k}^{(0)}\in \mathrm{C}[x^{\iota/\dot{d}},$$\frac{s}{\hat{d}}+(\frac{\dot{\delta}}{\hat{d}})(d-l)\in \mathrm{Z},$$(J\neq k)$

$y|$

に対して

$(l=0, \ldots, d-1)$)$\pi_{\theta,\dot{d}}(c_{J}^{(0}$となる写像$)=G_{k}^{(0)}$を満たす任意の$s\in \mathrm{Z}^{+}$

が$\pi_{\theta,\dot{d}}$に対して「$\theta,\dot{d}(W_{j}^{(\iota)})=e^{-2\pi i\theta}W^{(^{()}}S/\dot{d}.k$$7$Lagrange の補間多項式の構成方法より、次式を満たすの J(\iota ),証明$\tilde{W}_{k}^{(\iota)},$$(l=0, \ldots, d-1)$ が定まる。
$\tilde{W}_{J}(\mathrm{t})G(0)W_{J}J(+[\iota)G_{1}^{(0})$...

$G_{f}^{()}0/c_{J}^{(0}$)]$=y^{\iota}x^{(}\dot{\delta}/\dot{d}$) $(d-\iota)$

(3)

(4)

$\tilde{W}^{(\iota)}c^{(}+kk0)W(\downarrow)[c(0)k1\ldots G_{\gamma}^{(}0)/^{c]=}(0)ky^{\iota_{X}(}\dot{\delta}/\dot{d})(d-\iota)$(5)
上の (3) 式の両辺にを掛けると,$x^{s/\acute{d}}$$X^{S/\dot{d}}\cdot\tilde{W}_{JJjJ}^{(l)()}G+X^{S}W^{(\mathfrak{l})}0/\dot{d}.[c_{1}(0)\ldots c_{\Gamma}(0)/c(0)]=y^{\mathrm{t}}x^{s/}\dot{d}+(\dot{\delta}/\dot{d})(d-l)$を得る. さらに (6) 式に$e^{2\theta s/\dot{d}}\pi|$.

$x^{s/\dot{d}}$.

$\pi(\tilde{W}_{J}^{(1)})$

したがって両辺を$x^{s/\dot{d}}$.

$\pi:=\pi_{\theta,\dot{d}}$(6)を作用させ、仮定を用いると$G_{k}^{(0)}+e^{2\pi\theta ’s/\dot{d}}$.

$x^{s/\dot{d}}$. $\pi(W_{J}^{(l)})$ .

$[G_{1}^{(0)} .

.

.

.

G_{r}^{(0)}/G_{k}^{(0)}]=y^{l}x^{S}/\dot{d}+(\dot{\delta}/\dot{d})(d-\downarrow)$

で割れば、

.

$e^{2\pi\theta s/\dot{d}}’\cdot T(W_{J}(\downarrow))\cdot c_{k}(0)+e2\pi|.\theta s/\dot{d}$(7)$\pi(W_{j}^{(l)})\cdot[G_{1}^{(0)}\cdots c_{r}(0)/c_{k}(0)]=ylX(\dot{\delta}/\dot{d})(d-l)$(4) 式と (7) 式の左辺第 2 項を比較すると, 補間多項式の–意性より$e^{2\pi 1\theta_{S}/\dot{d}}.$.

$\pi(W_{J}^{(l)}\mathrm{I}=W_{k}^{(1)}$.

が得られる。 よって題意が示された。
定理 1436.

$G_{J}^{(0)},$存在すれば、 任意の$G_{k}^{(0)}\in \mathrm{C}[x^{\iota/}, y]\dot{d}$$s\in \mathrm{Z}^{+}$$\blacksquare$$(j\neq k)$

に対して

に対して
$\pi_{\theta,\dot{d}}(G_{J}^{(^{\mathrm{r}})}.)=G_{k}^{(s)}$が成立する。 すなわち、 次の diagram が可換となる。

$\pi_{\theta,\dot{d}}(c_{J}^{(0}$)$)=G_{k}^{(0)}$となる写像$\pi_{\theta,\dot{d}}$

が

129

$\pi_{\theta,\dot{d}}$$G_{k}^{(0)}$$G_{j}^{(0)}$$|Hens_{in}elLif\iota g$$HenLif\mathrm{f}s_{i}eng\rfloor l$.

.

.

$\pi_{\theta,\dot{d}}$$G_{k}^{(.)}$$G_{j}^{(s)}$

図1

証明

$s$

についての帰納法で示す. $s=0$ のときは、仮定より明らかに成立している. ある $s-1\geq 0$

まで題意が成立していたとする. このとき (2) 式より(8)$G_{J}^{(s)}=^{c_{J}^{(s-1}+\sum^{1}c^{(S)s/\dot{d}}})d-l=0W_{J}^{(\iota_{)}}x|$と書ける. ここで$f_{d-\mathrm{l}}(s)y^{d}-1\dot{\delta}/X\dot{d}+\cdots+f_{0^{s}}^{()}y^{0}Xd\dot{\delta}/\dot{d}\equiv F(x, y)-c_{1}(s)‘$$f_{l}^{(s)}=c_{l}^{(s)s}X/\dot{d}$(9) 式から,$c_{l}^{(_{S)}}\in \mathrm{C}$$\frac{s}{\hat{d}}+(\frac{\dot{\delta}}{\hat{d}})(d-l)\not\in \mathrm{Z}$..

(mod$c_{\Gamma}(S)$$I_{s+1}$)(9)$(l=0, \ldots, d-1)$ .となる $l=0,$$\ldots,$$d-1$ に対して

$G_{J}^{(s)}=c_{j}^{(s-}+1)$である。ゆえに (8) 式は$\text{。_{}l^{\vee}}^{(\cdot)}=0$(10)$W_{J}^{(\iota)}Cx(s)ls/\dot{d}$$\sum_{\downarrow=0,\ldots,d-1}$$s/\dot{d}+(\dot{\delta}/\dot{d})(d-\iota)\in^{\mathrm{Z}}$と書き直すことができる。上式に写像$\pi:=\pi_{\theta,\dot{d}}$を作用させ、仮定および補題 1435

を適用す

ると
$\pi(G_{k)}^{(s)}$$=$$\pi(G_{k}^{(-1)}S)+\sum\pi(W_{k}^{(l)})\cdot c_{l}^{(s)}\cdot\pi(X^{S/})\dot{d}$$=$$c_{J}^{(s-1)}+ \sum\pi(W_{k}^{()})\downarrow\cdot c_{l}^{(s)}\cdot e^{2\pi\theta s/S}’\dot{d}$$=$$G_{J}^{(S-1)}+ \sum e^{2}.\pi\pi’\theta-/\dot{d}.(W_{k}^{(\mathrm{t})})$$=$$c_{J}^{(S}-1)+ \sum W^{(\downarrow)}\cdot\text{。_{}t}J(s)$$=$$G_{J}^{(s)}$.

.

.

$X/\dot{d}$$X^{\cdot}./\dot{d}$$c_{l}^{(.)}\mathrm{Q}.$$x^{-\mathrm{Q}/\dot{d}}$よって題意が示された。
系 14.3.7.

$G_{J}^{(0)},$$\blacksquare$$G_{k}^{(0)}\in \mathrm{C}[x^{1/\dot{d}}, y]$

在すれば、 $y=\chi(x)$ が$G_{J}^{(\infty)}$$(j\neq k)$の根となるときに対して$\pi_{\theta,\dot{d}}(G_{j}^{(0)})=G_{k}^{(0)}$$y=\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{s}\mathrm{t}[\chi(X),$となる写像$x^{1/\dot{d}}arrow e^{2\pi\cdot\theta/}x^{1}]\dot{d}/\dot{d}$は$\pi_{\theta,\dot{d}}$$G_{k}^{(\infty)}$

が存の根130となる。
証明$c_{k}^{(\infty)}(X1/\dot{d}, y)$

を Puisuex 級数柱上で次のように因数分解する。
$c_{k}^{(\infty)}(X^{\mathrm{l}/\dot{d}}, y)=(y-x_{1}\mathrm{t}x))\cdots(y-\chi_{1}(x))$

定理 1436.

より$G_{J}^{(\infty)/\dot{d}}(x^{1}, y)$$c_{k}^{(\infty)}(e^{2}.x^{1}, y)\pi|\theta/\dot{d}/\dot{d}$$=$

subst $[(y-\chi_{1}(x))\cdot$ , .

$=$$(y-\chi_{\mathrm{t}}(x)),$$x^{1/\dot{d}}arrow ex]2\pi l\theta/\dot{d}\mathrm{l}/\dot{d}$$\blacksquare$

系 1438.

$G_{1}^{(0)},$$G_{2}(0),$. .

$G_{\mathrm{t}}^{(0)}$

$‘$

$,$

が次を満たすとする。

$G_{1}^{(0)(0)}G_{2}\cdots G_{\iota}(0)\in \mathrm{C}[x, y]$$($$G_{1}(0)G(20)\ldots c_{\mathrm{t}}^{(0)}$の無平方因子が既紘

このとき、$\#${$G^{(\infty)}|$から生成される Puiseux 級数の中で、 本質的に異なるもの}

$=\#$

証明
\dagger 列{系 1437.

14.3.9.

から生成される Puiseux 級数の中で、 本質的に異なるもの}$G_{1}^{(}\infty)c_{2\mathrm{t}}(\infty)\ldots G(\infty)$より明らか。

$\blacksquare$$F(x, y)=y^{5}+xy^{4}-2xy^{3}-2x^{2}y^{2}+(x^{2}-x^{3})y+x^{3}+x^{10}$とする。 Newton 多項式は$F^{(0)}=y^{5}-2xy^{3}+x^{2}y=y\cdot(y+x^{1/2})^{2}\cdot(y-X1/2)^{2}$となるから、 $G_{1}^{(0)}=y,$ $G_{2}^{(0)}=(y+x^{1/2})^{2},$ $G_{3}^{(0)}=(y-x^{1/2})^{2}$ とおき、 拡張された Hensel 構成を行なうとが得られる。系 1438
$F$

$G_{1}^{(\infty)}$$=$$y+x+\cdots$$G_{2}^{(\infty)}$$=$$(y+x^{\iota})/22-(x^{3/2}y/4+x^{2}/2)+\cdot\cdot \mathrm{Y}$$G_{3}^{(\infty)}$$=$$(y-x)1/223+(xy/2/4-X/22)+\cdots$より$G_{1}^{(\infty)},$$G_{2}^{(\infty)}$から生成される Puiseux 級数のみを調べることによって、の解として得られる Puiseux 級数の中で本質的に異なるものが求まる。 さらに、拡張された Hensel 構成を適用すれば、 次式を得る。
$y$$=$$x+x^{2}+\cdots$

$y$

$=$

$x^{1/2}-x/2+X^{3/2}/8\cdots+$$G_{1}^{(\infty)},$$G_{2}^{(\infty)}$に

131

$y$

$=$

$x^{1/2}+x/2-3x^{3/2}/8\cdots+$$\blacksquare$上の議論で見たように、 Newton 多項式の因子が互いに共役なときは、 Lagrange の補間多項式および Hensel 構成された因子間には非常に密接な関係がある。 このことから、 リーマン面の分岐点での分岐指数が大きいほど、 本算法による効率化がより顕著に現れることが予想される。
最後に、御指導下さった佐々木建昭教授、 北本卓也助手および諸先輩方に深く感謝致します。

参考文献[1] B.Wall, Puiseux expansion : an annotated bibliography. Technical Report, RISC-Linz Series

no. 91-460, October 23, 1991
[2] D. Duval, Rational Puiseux expansions. Compositio Mathematica, 70, pp. 119-154, 1989.
[3]$\mathrm{D}.\mathrm{L}$.Hilliker, An algorithm for computing the values of the ramification index in the puiseux

series expansions of an algebraic function. Pacific Journal of Mathematics, vol. 118, No. 2,1985.
[4] E.Brieskorn and H.Kn\"orrer,Plane Algebraic Curves.

Birkh\"auser Verlag, Basel-Boston-Stuttgart, 1986.
[5] F.Kirwan, Complex Algebraic Curves. London Mathematical Society, Student Texts 23, 1992.
[6]$\mathrm{H}.\mathrm{T}$.Kung and$\mathrm{J}.\mathrm{F}$.Traub, All algebraic functions can be computed fast. J. ACM 25, pp.

245-260) 1978.

[7] T. Kitamoto, F. Kako and T.Sasaki, On numerical power series roots of a multivariate poly-nomial (in Japanese). Presented at RIMS Symposium, Kyoto University, November 1993. 7pages.
[8] T.Sasaki an$\mathrm{d}$F. Kako, Solving multivariate algebraic equ ation by Hensel construction. Preprintof Univ. Tsukuba, January 1993. 22 pages.

[9] T. Sasaki, T. Kitamoto and F. Kako, Error analysis of power series roots of multivariate algebraic

equation, Preprint of Univ. Tsukuba, April 1994, 31 pages.
[10] T.C. Kuo,

Generalized Newton-Puiseux theory and Hensel’s lemma in$\mathrm{C}[x,$$y\mathrm{I}$Can.

$\mathrm{J}$Math., Vol. XLI, No. 6, pp 1101-1116, 1989.

[11] 佐々木建昭, 今井浩, 浅野孝夫, 杉原厚吉著. 計算代数と計算川吐岩波講座応用数学方法 9. 岩波書店, 1993.

132[12] 堀川頴示著. 複素代数幾何学入門. 岩波書店, 1990.