A Comparison of Degree Polynomials (Note)

Marko Petkovšek

Department of Mathematics, University of Ljubljana Jadranska 19, SI-1000 Ljubljana, Slovenia

                   Marko.Petkovsek@fmf.uni-lj.si

Christian Weixlbaumer

RISC Linz, Johannes Kepler University A-4040 Linz, Austria

             Christian.Weixlbaumer@risc.uni-linz.ac.at

1 Introduction

All known algorithms for finding polynomial solutions of linear difference equations with polynomial coefficients start out by computing a degree bound for such solutions. This bound is obtained as the maximum element of a finite set of integers which includes the integer roots of a certain polynomial, called the degree polynomial of the equation. In this note we compare the various degree bounds and degree polynomials proposed in [1], [3], [2], and [4].

2 Degree bounds

We consider equations of the form

Ly = f  (1)

where L is a linear difference operator with polynomial coefficients, and f is a given polynomial. The variations in degree bounds found in the literature stem from the choice of bases in which to expand L and its coefficients. L is expanded in powers of the forward shift E in [3], while in [1], [2] and [4] it is expanded in powers of the forward difference Δ. The coefficients of L which are polynomials of n are expanded in the power basis ⟨n^{k}⟩_{k=0}^{∞} in [1], [3] and [4], while in [2] they are expanded in the binomial basis ⟨\binom{n}{k}⟩_{k=0}^{∞}. Let

L = ∑_{k=0}^{r} p_{k}(n)E^{k} = ∑_{k=0}^{r} q_{k}(n)Δ^{k}.

Then, as Δ = E − 1 and E = Δ + 1, we have

p_{k}(n) = ∑_{j=k}^{r}(−1)^{j−k}\binom{j}{k}q_{j}(n), q_{k}(n) = ∑_{j=k}^{r} \binom{j}{k}p_{j}(n).  (2)

Denote

b = max_{0≤k≤r} (deg q_{k}(n) − k) ,

d = max_{0≤k≤r} deg p_{k}(n) = max_{0≤k≤r} deg q_{k}(n),

p_{k}(n) = ∑_{j=0}^{d} a_{k,j}n^{d−j}, q_{k}(n) = ∑_{j=0}^{d} c_{j,k}n^{j}.

Let y(n) be a polynomial solution of (1).

a) According to [1] and [4],

deg y ≤ max{M, deg f − b, − b − 1}  (3)

where M is the maximal integer root of the degree polynomial

A(x) = ∑_{k=0}^{r} c_{b+k,k} x\underline{k}.

b) For 0 ≤ j ≤ t define

b_{j}^{(t)} = ∑_{i=0}^{r} a_{i,t−j}i^{j}, D_{t}(x) = ∑_{j=0}^{t} \binom{x}{j}b_{j}^{(t)},

and let

s = min{t ≥ 0; D_{t}(x) ≢ 0}.

Then, by [3],

deg y ≤ max{M, deg f + s − d}  (4)

where M is the maximal integer root of the degree polynomial

D(x) = D_{s}(x) = ∑_{j=0}^{s} \binom{x}{j}b_{j}^{(t)}.

c) Following [2],

deg y ≤ max{M, deg f − b, − b − 1}

where M is the maximal integer root of the degree polynomial

B(x) = ∑_{k=0}^{r} ∑_{j=b+k}^{d} \binom{x + b}{j}\binom{j}{b + k}Δ^{j}q_{k}(a)

where a is arbitrary.

3 Relations among degree polynomials

Theorem 1 (i) s + b = d,

(ii) D(x) = A(x).

Proof: From (2) we read off

a_{k,j} = ∑_{i=k}^{r}(−1)^{i−k}\binom{i}{k}c_{d−j,i}.

Therefore

b_{j}^{(t)} = ∑_{k=0}^{r} ∑_{i=k}^{r}(−1)^{i−k}\binom{i}{k}c_{d−t+j,i}k^{j} = ∑_{i=0}^{r} c_{d−t+j,i} ∑_{k=0}^{i}(−1)^{i−k}\binom{i}{k}k^{j}

= ∑_{i=0}^{r} c_{d−t+j,i}Δ^{i}x^{j}|_{x=0} = ∑_{i=0}^{j} c_{d−t+j,i}Δ^{i}x^{j}|_{x=0}.

If t < d − b then d − t + j > b + j ≥ b + i ≥ deg p_{i} by definition of b, hence c_{d−t+j,i} = 0 for 0 ≤ i ≤ j. So b_{j}^{(t)} = 0 for 0 ≤ j ≤ t and D_{t}(x) ≡ 0. It follows that s ≥ d − b.

On the other hand,

b_{j}^{(d−b)} = ∑_{i=0}^{j} c_{b+j,i}Δ^{i}x^{j}|_{x=0}.

If i < j then b + j > b + i ≥ deg p_{i} by definition of b, hence c_{b+j,i} = 0 for 0 ≤ i < j and so

b_{j}^{(d−b)} = c_{b+j,j}Δ^{j}x^{j}|_{x=0} = j! c_{b+j,j}.

Therefore

D_{d−b}(x) = ∑_{j=0}^{d−b} \binom{x}{j}b_{j}^{(d−b)} = ∑_{j=0}^{d−b} \binom{x}{j}j! c_{b+j,j} = ∑_{j=0}^{d−b} c_{b+j,j}x\underline{j} = A(x) ≢ 0.

It follows that s = d − b and D(x) = A(x) as claimed. □

Theorem 2 B(x) = \{ \begin{matrix}(x + b)\underline{b}A(x), & b ≥ 0, \\ A(x)/x\underline{−b}, & b < 0. \end{matrix}

Proof: If j > b+k then, as b ≥ deg q_{k}−k, we have j > deg q_{k} and consequently Δ^{j}q_{k}(a) = 0. It follows that

B(x) = ∑_{k=0}^{r} ∑_{j=b+k}^{d} \binom{x + b}{j}\binom{j}{b + k}Δ^{j}q_{k}(a) = ∑_{k=0}^{r} \binom{x + b}{b + k}Δ^{b+k}q_{k}(a)

= ∑_{k=0}^{r} \binom{x + b}{b + k}(b + k)! c_{b+k,k} = ∑_{k=0}^{r} c_{b+k,k}(x + b)\underline{b+k}.

If b ≥ 0 then (x + b)\underline{b+k} = (x + b)\underline{b}x\underline{k} and B(x) = (x + b)\underline{b}A(x). If b < 0 then (x + b)\underline{b+k} = x\underline{k}/x\underline{−b} and B(x) = A(x)/x\underline{−b}, as claimed. □

4 Remarks on degree bounds

1. When using degree polynomial A(x) it is not necessary to consider − b − 1 when computing the degree bound (3). This is clear when b ≥ 0. When b < 0 we can write

A(x) = ∑_{k=−b}^{r} c_{b+k,k} x\underline{k},

so A(x) is divisible by x\underline{−b} with roots 0, 1, …, −b−1, implying that M ≥ − b − 1. Thus we can use the same bound deg y ≤ max{M, deg f − b} as in (4) (note that b = d − s and A(x) = D(x)).

2. When b ≥ 0 we have B(x) = (x + b)\underline{b}A(x). Clearly the factor (x + b)\underline{b} can be omitted because its roots − b, − b + 1, …, −1 are all negative. Thus to have a degree polynomial P (x) of least degree we can take

P (x) = \{ \begin{matrix}A(x), & b ≥ 0, \\ A(x)/x\underline{−b}, & b < 0. \end{matrix}

Then we have the bound

deg y ≤ \{ \begin{matrix}max\{M, deg f − b\}, & b ≥ 0, \\ max\{M, deg f − b, − b − 1\}, & b < 0, \end{matrix}

where M is the maximal integer root of P (x).

3. It is worth noting that in fact we know more than just an upper bound on the degrees of polynomial solutions of (1): these degrees must belong to the set consisting of the number deg f −b and the nonnegative integer roots of the degree polynomial A(x).

References

[1] S. A. Abramov: Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations, Moscow Univ. Comput. Math. Cybernet. (1989) no. 3, 63 – 68. Transl. from Vestnik Moskov. Univ. Ser. XV Vychisl. mat. kibernet. (1989) no. 3, 56 – 60.

[2] S. A. Abramov, M. Bronstein and M. Petkovšek: On polynomial solutions of linear operator equations, in: T. Levelt, ed., Proc. ISSAC ’95 (ACM Press, New York, 1995) 290–296.

[3] M. Petkovšek: Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symb. Comp. 14 (1992) 243–264.

[4] M. Petkovšek, H. S. Wilf and D. Zeilberger: A=B, A K Peters, Wellesley MA, 1996.