Polynomially Recursive Relations on Power-Series Roots
Kosaku Nagasaka
Kobe University

nagasaka@main.h.kobe-u.ac.jp

where Pb 6= 0.

ABSTRACTIn the combinatorics and probability theory, there are twoconcepts, diﬀerentiably ﬁnite and polynomially recursive andthey are related each other. Using those well known facts,
we give an algorithm to construct recursive formulas and calculate the power-series roots of bivariate polynomials. The
computational cost of the algorithm is linear w.r.t. the given
cutoﬀ degree. We also show some linear dependent relations
on the coeﬃcients of the power-series roots. By this property, we prove completeness of a bivariate polynomial factorization algorithm using zero-sum relations which is a basealgorithm of a recent approximate factorization method.

1. INTRODUCTION
Stanley wrote a book about enumerative combinatorics [7],in which there are the following concepts: diﬀerentiably ﬁnite and polynomially recursive. We note that we use theirabbreviations, D-ﬁnite and P-recursive, respectively, andour discussion is over C[u] and C[[u]] which are a polynomial ring in u over C and a formal power-series ring in u
over C, the complex ﬁeld, respectively.
Definition 1 (D-finite [7]). For any ϕ(u) ∈ C[[u]],we say ϕ(u) is D-ﬁnite power-series if there exist polynomials p0 (u), . . .,pd (u) ∈ C[u] satisfyingdXpi (u)ϕ(u)(i) = 0,

(1.1)

i=0

where pd (u) 6= 0 and ϕ(u)(i) denotes i-th partial diﬀerential∂ i ϕ(u)/∂ui ∈ C[[u]], of ϕ(u) w.r.t. u.
Definition 2 (P-recursive [7]). A function c : N →C is called P-recursive if for all k ∈ N, there exist polynomials P0 , . . ., Pb ∈ C[k] satisfying
Pb (k)c(k + b) + Pb−1 (k)c(k + b − 1)
+ · · · + P0 (k)c(k) = 0,

(1.2)

The important fact is that algebraic functions are D-ﬁnite
and we can see several examples of D-ﬁnite power-series andP-recursive functions in the book [7]. Benali and Jean-Paul[1] studied some algebraic properties of D-ﬁnite sequences
satisfying additional conditions. Moreover, Lipshitz [2] studied the generalized multivariate D-ﬁnite power-series and Precursive functions. However, we note that there are only
few papers in the algebra while there are several papers
about D-ﬁnite power-series in the combinatorics and probability theory. We try to use those concepts for symbolic
algebraic computations in this paper.
P-recursive functions are similar to linear recurrence functions. We can compute power-series by using P-recursivenessas we can use some linear recurrence relations to computelinear quantities. Our aim is to show such an algorithm.
Generally, computing the power-series roots of polynomials
is done by the symbolic Newton’s method, the generalized
Hensel construction or their variants. Those methods have acharacteristic that computational costs are non-linear w.r.t.
the given cutoﬀ degree bound. On the other hand, a computational cost is linear w.r.t. the given cutoﬀ degree bound
if we use P-recursiveness of D-ﬁnite power-series to computethe power-series roots.
In this paper, we give degree bounds of polynomials p0 (u),. . ., pd (u) in the relation (1.1), and by which we give an algorithm to compute the power-series roots of bivariate polynomials. These discussions also give us an additional property:
linear dependent relations on coeﬃcients of the power-seriesroots of bivariate polynomials. Using these properties, we
also give a proof of completeness of a bivariate factorization
algorithm [5, 4] which are the exact version of approximate
factorization [3] and has not been proved for any polynomial
cutoﬀ degree bounds.
This paper is formed as follows. We review some basic properties of D-ﬁnite power-series and P-recursive sequences inthe section 2. We prepare some degree bounds in the section 3 to show an expansion algorithm in the section 4. In
the section 5, as an application of former sections, we givea proof of completeness of the bivariate factorization algorithm [5, 4]. Finally, we give a conclusion in the section
6.

In this paper, we denote the quotient ﬁeld of C[u] by C(u).
F (u, x) ∈ C[u, x] is the given polynomial in u and the main
variable x and put

Lemma 1. ϕ(i) (u) (i = 1, . . . , n) can be represented as

F (u, x) = fn xn + fn−1 xn−1 + · · · + f1 x + f0 .

where D(u, ϕ), Ni (u, ϕ) (i = 1, . . . , n) ∈ C[u, ϕ] and thesepolynomials satisfy the following degree bounds.

And we suppose that F (u, x) is square-free w.r.t. x and put
n = degx (F ) and e = degu (F ).

ϕ(i) = Ni (u, ϕ)/D(u, ϕ)2i−1 ,degϕ (Ni ) ≤ (2i − 1)n − 2(i − 1),
degu (Ni ) ≤ (2i − 1)e − i,(3.4)

degϕ (D) ≤ n − 1,
degu (D) ≤ e.

2. D-FINITE AND P-RECURSIVEIn this section, we review some useful properties of D-ﬁnite
power-series and D-recursive functions, brieﬂy. We recommend to read the Stanley’s book [7] if you are interested in
the details, especially for their proofs.

Proof. The degree bounds of D follow from the deﬁnition (3.3) hence it is valid. Therefore, we prove the relation(3.4) and the degree bounds of Ni by the mathematical induction.

Proposition 1 (Proposition 6.4.3
P in [7]). Let ϕ(u)be a power-series in u and put ϕ(u) = k≥0 c(k)uk ∈ C[[u]].
Then, ϕ(u) is D-ﬁnite if and only if c(k) is P-recursive.

For i = 1, the lemma is valid by the deﬁnition and the assumption. Suppose that the lemma is valid for i = 1, . . . , κ.
For i = κ + 1, by diﬀerentiating ϕ(κ) , we have(1)

ϕ(κ+1) =Theorem 1 (Theorem 6.4.6 in [7]). For any powerseries roots ϕ(u) ∈ C[[u]] of F (u, x) w.r.t. x, ϕ(u) is D-ﬁnite
and ϕ(u) satisﬁes the relation (1.1) with d = n.
The proposition 1 and the theorem 1 mean that we cancompute the coeﬃcients of the power-series roots of F (u, x)
if we construct a corresponding P-recursive function c(k).
The proofs of the above can be found in the book [7] (Thelatter proof is done by treating C[u, x]/(F (u, x)) as a vector
space whose dimension is equal to or less than n).

3. DEGREE BOUNDS
We only consider the power-series roots of the given polynomial F (u, x) as D-ﬁnite power-series. At ﬁrst, we show
degree bounds of polynomials p0 (u), . . ., pd (u) satisfying therelation (1.1) for the power-series roots of F (u, x). Since, inthe book [7], the theorem 1 is proved by using the total differential of F (u, ϕ(u)) and representing ϕ(1) as an elementin C(u, ϕ), so we treat ϕ(1) as an element in C(u, ϕ), diﬀerentiate it recursively and give degree bounds of polynomials
p0 (u), . . ., pd (u).
The total diﬀerential of F (u, ϕ(u)) is given as follows.
˛˛˛∂F (u, x) ˛˛d(1) ∂F (u, x) ˛0=F (u, ϕ) =
+
ϕ
,
˛
du
∂u
∂x ˛x=ϕx=ϕ(3.1)
where expr(x)|x=ϕ denotes substituting ϕ for x. Since thegiven polynomial F (u, x) is square-free w.r.t. x, we have∂F (u, x)/∂x|x=ϕ 6= 0. Hence, the following relation follows
from the relation (3.1).
˛∂F (u,x) ˛˛∂u˛x=ϕ ∈ C(u, ϕ).
ϕ(1) = −(3.2)∂F (u,x) ˛
˛
∂x
x=ϕ

(1)

This means that ϕ is diﬀerentiable hence we have ϕ(i) (i =0, 1, . . . , n) ∈ C(u, ϕ). In the rest of this paper, we use thefollowing notations for these partial diﬀerentials for simplicity.
˛˛∂F (u, x) ˛˛∂F (u, x) ˛˛
,
D(u,
ϕ)
=
.
N1 (u, ϕ) = −
∂u ˛
∂x ˛
x=ϕ

x=ϕ

(3.3)

Nκ D − (2κ − 1)Nκ D(1)
.
D2κ

(3.5)

(1)

Here, Nκ and D(1) are polynomials in u, ϕ and ϕ(1) . By
(1)substituting the relations (3.2) and (3.3) for ϕ(1) in Nκ and
(1)
(1)
(1)
D , we have Nκ , D ∈ C(u, ϕ).
(1)

Since any denominators of rational expressions in Nκ andD(1) is D or a factor of D, we can reduce denominators of
the numerator of the expression (3.5) to the common denominator D and let the numerator of the numerator beNκ+1 which is formed as
(u,x)
(u,x)
Nκ+1 = (D ∂Nκ∂u|x=ϕ + N1 ∂Nκ∂x|x=ϕ )D∂D(u,x)|x=ϕ ).
− (2κ − 1)Nκ (D ∂u |x=ϕ + N1 ∂D(u,x)∂xHence, the expression (3.5) can be written as
Nκ+1
Nκ+1
= 2(κ+1)−1 , Nκ+1 ∈ C[u, ϕ].
D2κ+1D
Degree bounds of Nκ+1 are bounded as follows.
ϕ(κ+1) =degϕ (Nκ+1 ) ≤==≤=degu (Nκ+1 ) ≤
=
=
≤
=

(1)

max{degϕ (Nκ ) + degϕ (D),degϕ (Nκ ) + degϕ (D(1) )}max{degϕ (Nκ ) + 2degϕ (D),2degϕ (D) + degϕ (Nκ )}degϕ (Nκ ) + 2degϕ (D)(2κ − 1)n − 2(κ − 1) + 2(n − 1)(2(κ + 1) − 1)n − 2((κ + 1) − 1),(1)

max{degu (Nκ ) + degu (D),degu (Nκ ) + degu (D(1) )}max{degu (Nκ ) + 2degu (D) − 1,
2degu (D) − 1 + degu (Nκ )}degu (Nκ ) + 2degu (D) − 1(2κ − 1)e − κ + 2e − 1(2(κ + 1) − 1)e − (κ + 1).

Therefore, the lemma is proved by the mathematical induction.
The polynomials p0 (u), . . ., pn (u) that are considered in thissection satisfy the following equation by the deﬁnition 1 andthe theorem 1.
pn (u)ϕ(u)(n) + pn−1 (u)ϕ(u)(n−1) + · · ·+ p1 (u)ϕ(u)(1) + p0 (u)ϕ(u) = 0.

(3.6)

By multiplicating the least common denominator of ϕ(u)(i)(i = 0, . . . , n), we can rewrite the equation (3.6) as the following linear equation w.r.t. unknown coeﬃcients of polynomials p0 (u), . . ., pn (u).
pn (u)φn (u, ϕ) + pn−1 (u)φn−1 (u, ϕ) + · · ·+ p1 (u)φ1 (u, ϕ) + p0 (u)φ0 (u, ϕ) = 0,

(3.7)

degu (p0 ) = k, degu (p1 ) = k + 1, degu (p2 ) = k + 2, . . .,degu (pn−1 ) = k + n − 1 and degu (pn ) = k + n such thateach products pi (u)Ri (u, ϕ) has the same degree. The system (3.8) has (n + 1)(k + 1) + n(n + 1)/2 unknowns andn(2(n2 − n + 1)e + k + 1) equations, hence the theorem isproved by solving the following inequality w.r.t. k.
n(2(n2 − n + 1)e + k + 1) ≤ (n + 1)(k + 1) + n(n + 1)/2.

where φi (u, ϕ) (i = 0, . . . , n) ∈ C[u, ϕ].
Lemma 2. φ0 , . . . , φn satisfy the following degree bounds.
degϕ (φi ) ≤ 2n2 − 3n + 2,
degu (φi ) ≤ (2n − 1)e − i.
Proof. Since, by the lemma 1, each least common denominators of ϕ(u)(i) is D(u, ϕ)2n−1 or its factor, we canrewrite φi as follows.
D(u, ϕ)2n−1 ϕ(i = 0),φi =D(u, ϕ)2(n−i) Ni (u, ϕ) (i = 1, . . . , n).
Therefore, the lemma is proved by the lemma 1.
We note that we have to discuss all the quantities overC[u, ϕ]/(F (u, ϕ)) to treat the power-series roots of F (u, ϕ)
as D-ﬁnite power-series. We rewrite the system (3.7) as follows.
pn (u)Rn (u, ϕ) + pn−1 (u)Rn−1 (u, ϕ) + · · ·+ p1 (u)R1 (u, ϕ) + p0 (u)R0 (u, ϕ) = 0,

(3.8)

where Ri ∈ C[u, ϕ] (i = 0, . . . , n) are residuals of φi by
F (u, ϕ) w.r.t. ϕ.
Lemma 3. We havedegϕ (Ri ) ≤ n − 1
degu (Ri ) ≤ 2(n2 − n + 1)e − i(i = 0, . . . , n).

Proof. As in the proof of the lemma 2, we can rewrite
φi as follows.
D(u, ϕ)2n−1 ϕ(i = 0),φi =D(u, ϕ)2(n−i) Ni (u, ϕ) (i = 1, . . . , n).
For each divisions by F (u, ϕ), a degree of a residual is increased by e. The lemma follows from a summation of all
the increase degrees.
Theorem 2. The polynomials p0 , . . . , pn satisfy the following degree bounds.
degu (pi ) ≤ di (e),wheredi (e) =1(4en3 − (4e + 1)n2 + (4e − 1)n − 2) + i.
2

Since the degree bounds di (i = 0, . . . , n) are suﬃcient degree bounds, actual degrees of polynomials p0 , . . ., pn are
equal to or smaller than these bounds as in the example in
the next section. We note that these bounds di can be replaced with actual degrees of pi , though all the discussions
in the rest of this paper are based on these suﬃcient degreebounds di .

4.

RECURSIVE ALGORITHM

A formula to compute coeﬃcients c(k) can be derived fromthe relation (1.2) if we have polynomials Pi (k) (i = 0, . . . , b).
However, we do not know those polynomials while we obtained the degree bounds of polynomials p0 , . . . , pn in theprevious section. Therefore, we calculate polynomials p0 ,. . ., pn by solving the system (3.8), and derive a formula
to compute coeﬃcients of the power-series roots of F (u, x)
by the relation (1.1). To do this, we need to 1) solve thesystem (3.8), 2) construct a recursive formula to computecoeﬃcients, and 3) calculate an initial power-series root up
to enough degree. We have several suitable methods to do1) and 3). Hence we derive the recursive formula in thissection.
Lemma 4. Suppose that the power-series root ϕ satisfying
the relation (1.1) is already calculated up to degree k − 1 (≥P i
Ppi,j uj .
n−1) w.r.t. u and put ϕ = kj=0 cj uj and pi = dj=0
Then, ck can be computed as the following formula provided
pn,0 6= 0.
ck = −nXX

t=0 i+j=k−t, i,j≥0, j6=k

j!(k − n)! pn−t,i cj.
(j − n + t)!k! pn,0

Proof. Since the power-series root ϕ is D-ﬁnite, it satisﬁes the relation (1.1). By extracting coeﬃcients of terms
whose degree is k − n w.r.t. u from the expression (1.1), we
have
n
X

X

t=0 i+j=k−t, i,j≥0j!
pn−t,i cj = 0.
(j − n + t)!

Solving the above equation w.r.t. ck gives us the following
solution.
Pn P
j!
t=0
i+j=k−t, i,j≥0, j6=k (j−n+t)! pn−t,i cj
ck = −.
k!
p
k−n! n,0
The lemma follows from simplifying the above solution.

Proof. The linear equation (3.8) must have non-trivial
solutions by the theorem 1. Therefore, the theorem follows from letting the degrees of pi such that the numberof unknowns is larger than the number of equations: put

Corollary 1. If the power-series root ϕ is calculated up
to degree k − 1 (≥ dn − 1) w.r.t. u, and pn,0 6= 0, then wehave the following formula to compute ck .
!
Pn Pdn−t (k−i−t)!
i=0 (k−i−n)! pn−t,i ck−t−it=1
P n (k−i)!
+ di=1p c(k−i−n)! n,i k−i
ck = −.
k!
p(k−n)! n,0

We note that the above formula is corresponding to a quotient of the expression in the deﬁnition 2 by Pb (k), since theformula for ck in the corollary 1 is a linear sum of productsof functions in k and ci (i < k).
We simplify the formula in the corollary 1 as the following expression (4.1), and give an algorithm to compute thepower-series roots.
P
Pdn−t (k−i−t)! (k−n)!
1− pn,0( npn−t,i ck−t−ii=0 (k−i−n)!
t=1
k!
(4.1)
Pdn (k−i)! (k−n)!
+ i=1 (k−i−n)! k! pn,i ck−i ).
Algorithm 1. (D-ﬁnite Power-Series Roots Expansion)
Input :a polynomial F (u, x) and a cutoﬀ degree E

Output :the power-series roots of F (u, x) up to E

Step 1 Solve the system (3.8), calculate p0 , . . ., pn , andconstruct a recursive formula (4.1).
Step 2 Expand the power-series roots by the conventional
methods up to actual degree (dn − 1) w.r.t. u.
Step 3 While k ≤ E, for each power-series roots, computeck by the formula (4.1) and let k = k + 1.
Step 4 Output the computed power-series roots and ﬁnish
the algorithm.
We note that the computational cost of each coeﬃcientsis O(en5 ) complexity over C at worst. This cost does notdepend on the cutoﬀ degree or iteration index k while theconventional methods do. Hence the total computational
cost of the step 3 is linear w.r.t. cutoﬀ degree bound E.
Corollary 2. The coeﬃcient ck of terms whose degree
is k (≥ dn ), of the power-series root ϕ of F (u, x), does notdepend on coeﬃcients: c0 , c1 , . . ., ck−dn −1 .

Example 1. We give an example of the algorithm 1 forthe simple bivariate polynomial F (u, x) = x2 − u − 1.
As the initialization step, We compute degree bounds ofpolynomials p0 , p1 and p2 . These bounds are d0 = 8, d1 = 9
and d2 = 10 since we have n = 2 and e = 1.
In the step 1, we solve the system (3.8), calculate p0 , . . .,pn , and construct a recursive formula (4.1). At ﬁrst, we
diﬀerentiate the power-series root ϕ as follows.
ϕ(1)
ϕ(2)

=
=

1
,
2ϕ
− 4ϕ1 3 .

The least common denominator of the above derivatives is
4ϕ3 . Hence we have the following system.
p2 R2 + p1 R1 + p0 R0 = 0,
R2 = −1, R1 = 2 + 2u, R2 = 4 + 8u + 4u2 .
According to the above system, we reﬁne the degree bounds
as d0 = 0, d1 = 1 and d2 = 2, and we have the following
solution (we note that there are other solutions).
p0 = −1, p1 = 3 + 3u, p2 = 2 + 4u + 2u2 .
Therefore, we have the following recursive formula of ck .
55− 2)ck−1 + (− 1)ck−2 .
2k
2kIn the step 2, we calculate the power-series roots ϕ1 (u) andϕ2 (u) up to degree dn − 1 = 1 as follows.
ck = (

ϕ1
ϕ2==−1 − 1/2u,
1 + 1/2u.

In the step 3, we compute coeﬃcients of the power-seriesroots, using the above recursive formula.
→ {−1, −1/2, 1/8, −1/16, 5/128, −7/256, . . .},→ {1, 1/2, −1/8, 1/16, −5/128, 7/256, . . .}.

ϕ1
ϕ2

In this case, by solving the above recursive formula, we canderive the following general expression for all the coeﬃcients.
` ´(−4)−k 2kkck = ±.
1 − 2kExample 2. We give another example of a recursive formula for the following bivariate polynomial which is reducible and monic w.r.t. x.
F (u, x) = x5 − (u − 1)x3 − (u + 1)x2 + u2 − 1.
We have the following recursive formula for F (u, x).
ck=

Corollary 3. Each the power-series roots of F (u, x) has
the same P-recursive relation and can be computed by thesame formula.

1
− 6k
ck−1
−984+2170k−1853k2 +767k3 −154k4 +12k5+
ck−2
12k(24−50k+35k2 −10k3 +k4 )2

335352−30990k+8994k −864k+ 10368k(24−50k+35k
2 −10k3 +k4 ) ck−321276−607k+72k+ 10368k(24−50k+35k
2 −10k3 +k4 ) ck−4
2

176−65k+6k+ 10368k(24−50k+35k
2 −10k3 +k4 ) ck−5 .

In the Stanley’s book [7], the given polynomial is supposed
to be irreducible, and there is not any notes for reducible
polynomials. If the given polynomial is reducible, the powerseries roots of F (u, x) also satisfy the all of the above expressions corresponding to polynomial factors of F (u, x), which
has the root.

Moreover, the above polynomial is factorized as F (u, x) =(x3 − u − 1)(x2 − u + 1), and we have the following recursive
formulas for x3 − u − 1 and x2 − u + 1, respectively.
ck
ck

=
=

4−3k
1
ck−1 − k(k−1)
ck−2 + 3k(k10−3k
2 −3k+2) ck−3 ,
3k
2k−5
2k−5
ck−1 + 2k(k−1) ck−2 .
2kRemark 1. As in the previous and this sections, we canalso calculate degree bounds of polynomials P0 , . . . , Pb andgive an alternative algorithm to construct the recursive formula (4.1) directly, using the relation (1.2). However, thisidea is not eﬃcient because we have to solve a linear systemover C even if the given polynomial is over R or Q.

the following alternative theorem 4 to use the exact versionof algorithm because the algorithm ﬁnds those linear dependent relations in the theorem 4 instead of the relationsin the theorem 3, indirectly. The theorem 4 has not been
proved for any polynomial cutoﬀ degree E, even though thetheorem has been proved [5] for inﬁnite cutoﬀ degree E by
the Galois theory.

5. APPLICATIONAs shown in the previous sections, considering the powerseries roots as D-ﬁnite power-series gives us useful properties. Especially the corollaries 2 and 3 are useful for discussions about some theories using the power-series roots. In
this section, we give such an application of the properties.
Recently, we have several approximate factorization algorithms, moreover, one algorithm using zero-sum relations ispractical, which is studied by Sasaki [3]. One may think to
use the zero-sum relations for exact ones. In fact, Sasaki andet al. [5, 6, 4] studied such an exact factorization algorithm.
However, they have not done the proof of completeness ofthe main theorem which is a key of their algorithm. We givethe proof by the properties of D-ﬁnite power-series in thissection, even though a bivariate case only.

5.1 Known Theorem To Be Proved
We use the following notations.
• dF ea = the sum of terms of total-degrees ≤ a, of F ;• bF cb = the sum of terms of total-degrees ≥ b, of F ;• [F ]ab = dbF cb ea ;Theorem 4 (Theorem 5.3 in [5]). For each j in {1,. . . , n}, let λj ∈ C, hj (u) ∈ C[u] and degu (hj ) ≤ jē. Let thepower-series roots ϕ1 (u), . . . , ϕn (u) of F (u, x) satisfy (someof λ1 , . . . , λn may be 0)8
λ1 d(fn ϕ1 )1 eE + · · · + λn d(fn ϕn )1 eE = h1 (u),>><λ1 d(fn ϕ1 )2 eE + · · · + λn d(fn ϕn )2 eE = h2 (u),
· · ·
···
>
>
:
λ1 d(fn ϕ1 )n eE + · · · + λn d(fn ϕn )n eE = hn (u).
This system holds iﬀ, among the elements of {λ1 , . . . , λn },all the elements that correspond to the roots of each irreducible factor in C[u, x], of F (u, x) are the same.
The above theorem 4 for a polynomial cutoﬀ degree E guarantees that the exact version of the zero-sum factorization
algorithm can ﬁnd correct factors. We give the proof forcertain ﬁnite cutoﬀ degrees in the next subsection.
Remark 2. Sasaki’s approximate factorization method [3]uses some sub-routines to ﬁnd linear dependent relations.
We note that there might exist another way to prove completeness of the algorithm.

5.2
Let the truncated power-series roots of F (u, x) w.r.t. themain variable x be ϕ1 (u), . . . , ϕn (u) and the cutoﬀ degree
be E, satisfying
F (u, x) ≡ fn (u)(x − ϕ1 (u)) · · · (x − ϕn (u))(mod uE+1 ).

We suppose that F (0, x) is square-free w.r.t. x and put
degu (fi ) = ei (i = n, n − 1, . . . , 0) hence max{en , . . . , e0 } =e = degu (F ).
Definition 3. Let H be a two-dimensional convex hullsuch that points (0, 0), (0, e0 ), (1, e1 ), . . ., (n, en ) and (n, 0)
are on H. We deﬁne a number ē such that a point (n − 1, ē)
is on the upper edges of H.
Theorem 3 (Theorem 1 in [3]). Let the cutoﬀ degree
E = nē and h1 (u), . . . , hm (u) ∈ C[u], and suppose that wehave the relations
8
1
1
nē
degu (h1 ) ≤ 1ē,>< dfn · (ϕ1 + · · · + ϕm )e = h1 (u),
..
..
.
.
>
:
m nē
dfnm · (ϕm= hm (u), degu (hm ) ≤ mē.
1 + · · · + ϕm )eThen, P = fn · (x − ϕ1 ) · · · (x − ϕm ) is a polynomial factor
of fn F (u, x), and vice versa.
Although the theorem 3 has been proved and the approximate factorization method [3] is practical, we need to prove

Proof Of The Theorem 4

The theorem 4 was proved by Sasaki et al. [5] with E → ∞using the Galois theory. Hence, in this section, we provethat a polynomial cutoﬀ degree case can be treated as sameas the case E → ∞. We use the following useful lemmas(the latter lemma 6 is proved by Sasaki et al. [4]).
Lemma 5 (Newton’s formula). Let Si (X1 , . . . , Xm )and Pi (X1 , . . . , Xm ) (i = 1, . . . , m) be deﬁned as follows (Siis the elementary symmetric polynomial of degree i).
8
S1 (X1 , . . . , Xm ) = X1 + X2 + · · · + Xm ,
>
>
>
>
S
>
< 2 (X1 , . . . , Xm ) = X1 X2 + · · · + X1 Xm+ · · · + Xm−1 Xm ,
>
..
>
>
>
.
>
:
Sm (X1 , . . . , Xm ) = X1 X2 · · · Xm−1 Xm ,8
P1 (X1 , . . . , Xm )>>>< P2 (X1 , . . . , Xm )= X1 + X2 + · · · + Xm ,2
= X12 + X22 + · · · + Xm
,
..
>
>
.
>
:
m
Pm (X1 , . . . , Xm ) = X1m + X2m + · · · + Xm.
Then, for any integer i, 1 ≤ i ≤ m, we havePi − Pi−1 S1 + Pi−2 S2 − · · · + (−1)i−1 P1 Si−1 + (−1)i iSi = 0.
Lemma 6. Assume that the polynomial factor G(u, x) of
fn F (u, x) is given asG(u, x) = fn · (x − ϕ1 ) · · · (x − ϕm ).

Then, we have the following degree bounds for the sum of
powers of roots.
degu ( (fn ϕ1 )i + · · · + (fn ϕm )i ) ≤ iē (i = 1, . . . , m).

Lipshitz [2]. In fact, we have a result similar to the bivariate case though it is complicated. These results will be
published in the future.

7.
We consider the polynomials Fi (u, x) of degree n w.r.t. x,
whose roots are ϕi1 ,. . .,ϕin . Substituting X1 = fn ϕ1 , . . .,Xn = fn ϕn and Xn+1 = 0, . . ., Xn2 = 0 in the lemma 5, wehave the following degree bounds by the lemma 6.
degu ( (fn ϕ1 ) + · · · + (fn ϕn ) ) ≤ jē (j = 1, . . . , n ).
jj

2

By the lemma 5, we also havedegu (Fi (u, x)) ≤ niē, Fi (u, x) = fni (x − ϕi1 ) · · · (x − ϕin ).
By applying the corollaries 2 and 3 to Fi (u, x), we have thatcoeﬃcients of terms whose degrees are equal to or larger
than dn (niē) + nē does not depend on coeﬃcients of terms
whose degrees are equal to or less than nē, and coeﬃcients ofterms whose degrees are equal to or larger than dn (niē)+nē,of the power-series roots, have the same linear dependent
relations for coeﬃcients of terms whose degrees are less thandn (niē)+nē and equal to or larger than nē. Therefore, there
must not exist any other linear independent relations on
coeﬃcients of powers of the power-series roots if we calculate
the power-series roots up to the following degree.
dn (niē)+nē = 2iēn4 −2iēn3 +(4iē − 1) 2 (2ē − 1)n +n+i−1.
2
2

We use the largest degree dn (n2 ē) + nē as the cutoﬀ degree.
This means that the theorem 4 is equal to the theorem with
E → ∞. Therefore, the theorem 4 is proved for the polynomial cutoﬀ degree E as follows.
(2ē + 1)
1
dn (n2 ē) + nē = 2ēn5 − 2ēn4 + 2ēn3 − n2 +n − 1.
2
2
We note that we can decrease the cutoﬀ degree dn (n2 ē)by O(en4 ) if the given polynomial is monic w.r.t. x, sinceD(u, ϕ) becomes a monic polynomial w.r.t. ϕ and leading
terms w.r.t. degree bounds, of Ni (u, ϕ) are 0.

6. CONCLUSION
Applying concepts, D-ﬁnite power-series and P-recursive sequences, to the power-series roots of bivariate polynomials,
give us new polynomially recursive algorithm to computethe power-series roots. Although the new algorithm has aweak point that we have to calculate a polynomially recursive formula (4.1) by diﬀerentiating and solving the system(3.8) as initial computations, its computational cost is linear w.r.t. the given cutoﬀ degree. The algorithm is useful
to compute the power-series roots up to higher degrees thann, the degree of the given polynomial w.r.t. the main variable. For some cases, we can construct general expressionsof coeﬃcients of power-series roots from recursive formulas.
Moreover, these discussions also give us useful properties ofthe power-series roots. The proof in the section 5 is such an
application use.
We can expand the D-ﬁnite power-series roots to multivariate polynomials and derive similar degree bounds and a multivariate version of the algorithm, using deﬁnitions of multivariate D-ﬁnite power-series and P-recursive functions by

REFERENCES[1] B. Benzaghou and J.-P. Bézivin. Propriétés algébriquesde suites diﬀérentiellement ﬁnies. Bull. Soc. Math.
France, 120(3):327–346, 1992.
[2] L. Lipshitz. D-ﬁnite power series. J. Algebra,
122:353–373, 1989.
[3] T. Sasaki. Approximate multivariate polynomial
factorization based on zero-sum relations. In
Proceedings of the 2001 International Symposium on
Symbolic and Algebraic Computation, ISSAC 2001,
pages 284–291, 2001.
[4] T. Sasaki and K. Nagasaka. Approximate multivariate
factorization and its time complexity. preprint, 1998.
[5] T. Sasaki, T. Saito, and T. Hilano. Analysis ofapproximate factorization algorithm I. Japan J. Indust.
Appl. Math., 9:351–368, 1992.
[6] T. Sasaki and M. Sasaki. A uniﬁed method for
multivariate polynomial factorizations. Japan J. Indust.
Appl. Math., 10:21–39, 1993.
[7] R. P. Stanley. Enumerative Combinatorics Volume 2,
Cambridge Studies in Advanced Mathematics 62.
Cambridge University Press, Cambridge, 1997.