Desingularization of linear difference operators with polynomial coefficients

Sergei A. Abramov^{∗}

Computer Center of the Russian Academy of Science, Vavilova 40, Moscow 117967, Russia

                              abramov@ccas.ru
                            sabramov@cs.msu.su

Mark van Hoeij^{†}

Department of mathematics Florida State University, Tallahassee, FL 32306-3027, USA

                                                               hoeij@math.fsu.edu

Abstract

We consider the following two problems related to linear difference equations with polynomial coefficients:

1. Let E be the shift operator defined on sequences by E(c_{n}) = c_{n+1} and defined on functions of n as E(f(n)) = f(n + 1). Consider a numeric sequence c = {c_{l}, c_{l+1}, …} where l is an integer. Suppose T_{1}(c) = T_{2}(c) = 0, where T_{1}, T_{2} ∈ C[n, E], and the coefficients of E^{0} in T_{1}, T_{2} do not vanish for n ≥ l − 1. Both T_{1} and T_{2} allow to determine a corresponding value of c_{l−1}. Do the two values equal?

2. Let F ∈ C[n, E] and let its coefficient of E^{0} vanish for some values of n. Does there exist T ∈ C[n, E] right divisible (over C(n), i.e. T = G∘F for some G ∈ C(n)[E]) by F such that its coefficient of E^{0} does not vanish for integer values of n? If so, how can one find it?

Solutions of these and of some more general problems are proposed.

1 Introduction

A recurrence relation is a tool to define sequences. If we have a linear recurrence operator f_{d}(n)E^{d} + ⋯ + f_{1}(n)E + f_{0}(n) and a sequence {c_{l}, c_{l+1}, …, c_{l+d−1}} where l is an integer, then we can try to extend this sequence to an infinite doublesided sequence {…, c_{l−1}, c_{l}, c_{l+1}, …, c_{l+d−1}, c_{l+d}, …}. The integer roots of f_{d}(n) and f_{0}(n) present obstacles to this process.

In this paper an operator F ∈ C[n, E] is called a right divisor of an operator T ∈ C[n, E] if T = V ∘ F for some V ∈ C(n)[E], so we will allow rational functions in n as coefficients for the left hand factor V. If the original operator F is a right divisor of another operator T ∈ C[n, E] such that its coefficient t_{0}(n) of E^{0} has few (ideally: no) common roots with f_{0}(n) then one can use T to determine the next term to the left left at the points where F does not determine the next term. Something similar can be done for extending sequences to the right, then one must consider the roots of f_{d}(n − d) instead of f_{0}(n), c.f. section 6.2. This method of continuing sequences raises the following question: if F is a right-hand factor of two operators T_{1} and T_{2}, and we can not extend the sequence by F but we can extend the sequence by T_{1} and T_{2} (because f_{0}(n) has an integer root at that point but the coefficients of E^{0} of T_{1} and T_{2} do not) will the result be the same if we use T_{1} or T_{2}? The answer to this question is yes (a more general result is given in Corollary 1 in section 3), and furthermore we will give another method for extending this sequence in section 5, which will give the same result as well. Acknowledgment: We would like to thank Ha Q. Le for comments on an earlier draft.

Example 1. Let F = (n−1)E^{2} +(1/2−n^{2})E +n(2n−1)/4 and let c_{1} = 2, c_{2} = 1. Then for c_{0} (take n = 0) we find the equation −c_{2} + \frac{1}{2} ·c_{1} +0·c_{0} = 0 which does not determine c_{0}. For c_{3} (take n = 1) we find the equation 0·c_{3}− \frac{1}{2} ·c2+ \frac{1}{4} ·c_{1} = 0 from which we can not determine c_{3}. Suppose we take for example c_{3} = 0. Even though the recurrence still does not determine c_{0}, given the values of c_{1}, c_{2} and c_{3} there is a canonical way of choosing a value for c_{0}, as follows: F is a right divisor of T = E^{3}−(5/2+n)E^{2}+(3/4+n)E−n/4+1/8, namely T = 1/n · (E − 1/2) ∘ F. This recurrence gives a non-trivial equation for c_{0} in terms of c_{1}, c_{2} and c_{3}. The difference operator T is called a desingularization of F. We find c_{3} − \frac{5}{2} c_{2} + \frac{3}{4} c_{1} + \frac{1}{8} c_{0} = 0 so we find the value 8 for c_{0}, the same value as the ϵ-method in section 5 would give.

2 Matrices related to difference operators

Let

T = t_{m}(n)E^{m} + ⋯ + t_{0}(n)  (1)

belong to C[n, E] and u be a positive integer. Assume t_{m} ≠ 0, so the order of T is m. We define the matrix T^{(u)} as

( \begin{matrix}E^{u−1}t_{m}(n) & … & E^{u−1}t_{0}(n) \\ & E^{u−2}t_{m}(n) & … & E^{u−2}t_{0}(n) \\ & ... & & ... \\ & & t_{m}(n) & … & t_{0}(n) \end{matrix} )

(2)

We will use such matrices as blocks to construct other matrices. The blocks will be arranged vertically, one above the other. If necessary we add columns with zeros on the left of narrower blocks in order to make the widths of all blocks the same:

( \begin{matrix}0 & … & 0 & E^{u−1}t_{m}(n) & … & E^{u−1}t_{0}(n) \\ & & & ... & & ... \\ 0 & … & 0 & & t_{m}(n) & … & t_{0}(n) \end{matrix} )

(3)

∗Supported in part by RFBR under Grant 98-01-00860.

†Supported by NSF grant DMS-9805983.

This construction allows one to define the matrix mat(T_{1}^{(s_{1})}, …, T_{k}^{(s_{k})}):

( T_{1}^{(s_{1})} ; —— ; T_{2}^{(s_{2})} ; —— ; ⋮ ; —— ; T_{k}^{(s_{k})} )  (4)

for T_{1}, …, T_{k} ∈ C[n, E] and positive integers s_{1}, …, s_{k}. Block (2) has m + u columns. For block (3) one has

v − u − m = w,

where v is the total number of columns and w is the number of additional zero columns. If

ord T_{i} = m_{i}, i = 1, …, k,  (5)

and

v = max_{i=1}^{k} (m_{i} + s_{i}),  (6)

then matrix (4) is a polynomial (s_{1} + ⋯ + s_{k}) × v-matrix.

Lemma 1 Let F, T_{1}, …, T_{k} ∈ C[n, E] be such that T_{1}, …, T_{k} are right divisible over C(n) by F. Let M, s_{1}, …, s_{k} be positive integers such that

ord F + M ≥ max_{i=1}^{k} (ord T_{i} + s_{i}).  (7)

Let A = mat(F^{(M)}, T_{1}^{(s_{1})}, …, T_{k}^{(s_{k})}). Then rank_{C(n)} A = M.

Proof: Because of (7) and the right divisibility of T_{1}, …, T_{k} by F any row of A is a C(n)-linear combination over of the first-block rows, which are linearly independent over C(n). □

Recall that by right divisible we mean right divisible over C(n), i.e. the coefficients of the left hand factor are not restricted to C[n] but may be in C(n). If l ∈ ZZ and A is a matrix with elements from C[n] then denote by A|_{n=l} the matrix obtained by substituting l for n in A.

Lemma 2 Let the hypothesis of Lemma 1 hold. Let l ∈ ZZ. Then rankC (A|_{n=l}) ≤ M.

Proof: By Lemma 1 the determinant of any minor of size M + 1 (i.e. a M + 1 by M + 1 submatrix) of A is zero. This still holds after the substitution. □

Definition 1 Let g_{1}, …, g_{u} be elements of a ring, u ≥ 1. The size of the row (g_{1}, …, g_{u}) is the integer number max ({0} ∪ {i | 1 ≤ i ≤ u, g_{i} ≠ 0}).

Definition 2 Let A be a polynomial matrix, l ∈ ZZ and B = A|_{n=l}. A row of B is regular w.r.t. A if it is of the same size as the original row of A.

Theorem 1 Let F, T_{1}, …, T_{k} ∈ C[n, E] be such that T_{1}, …, T_{k} are right divisible by F. Let M and s be positive integers such that

ord F + M ≥ max_{i=1}^{k} ord T_{i} + s.

Let A = mat(F^{(M)}, T_{1}^{(s)}, …, T_{k}^{(s)}). For an integer l ∈ ZZ assume that B = A|_{n=l} contains M rows that are regular w.r.t. A and of pairwise different sizes. Then

i) the set of these rows includes the first M − s rows of B;

ii) the intersection of this set of rows and of the last M columns of B defines a basic minor of B (i.e., a minor, of maximal size, with non-zero determinant).

iii) the sizes of these rows are d + 1, …, d + M.

Proof: There are at most M possibilities for the size of a regular row of B (so they must all occur), namely the sizes of the rows of A. If d = ord F then these are d+1, …, d+M, so iii) follows. Only the first M −s rows of B can be regular rows of sizes d + 1, …, d + M − s, hence i) follows.

The determinant of the minor is nonzero because the minor is a lower triangular matrix with nonzero diagonal elements. By Lemma 2 this minor is of maximal size, so ii) follows. □

3 Extending P -recursive sequences

A sequence

c = {c_{v}, c_{v+1}, …},  (8)

v ∈ ZZ, is P -recursive if it satisfies a linear recurrence R(c) = 0, R ∈ C[n, E]. It is easy to see that sequence (8) satisfies a recurrence R(c) = 0 iff for any ν, ν ≥ ord R + v,

(c_{ν}, c_{ν−1}, …, c_{v})  (9)

satisfies the system of homogeneous linear equations with coefficient matrix R^{(N)}|_{n=v}, where N = ν − v + 1 − ord R.

Theorem 2 Let F, T_{1}, …, T_{k} ∈ C[n, E] be such that T_{1}, …, T_{k} are right divisible by F, d = ord F > 0. Let f_{0}(n), t_{1,0}(n), …, t_{k,0}(n) be the coefficients of E^{0} in, resp., F, T_{1}, …, T_{k} and let l, v ∈ ZZ, l < v, be such that

i) for all α ∈ ZZ, α ≥ v, each of the values f_{0}(α), t_{1,0}(α), …, t_{k,0}(α) is not 0,

ii) for all α ∈ ZZ, l ≤ α < v, at least one of the values f_{0}(α), t_{1,0}(α), …, t_{k,0}(α) is not 0. Let a sequence c of the form (8) satisfy recurrences

F (c) = T_{1}(c) = ⋯ = T_{k}(c) = 0.  (10)

Then the sequence c can be uniquely extended to a sequence

{c_{l}, c_{l+1}, …, c_{v−1}, c_{v}, c_{v+1}, …}  (11)

satisfying recurrences (10).

Proof: Set s = v − l, M = max_{i=1}^{k} ord T_{i} + s − d. Then all the assumptions of Theorem 1 are satisfied. Let the matrix A be as described in Theorem 1. Due to Theorem 1, the system S of homogeneous linear equations with coefficient matrix A|_{n=l} has the following property. We can take the values of the first d = ord F unknowns arbitrarily and then determine (uniquely) the values of the remaining M unknowns using equations corresponding to the chosen M regular rows (whose sizes are pairwise different). In doing so the remaining equations of S are satisfied.

We can take c_{(M+l)+d−1}, c_{(M+l)+d−2}, …, c_{M+l} as the values of the first d unknowns and then uniquely determine the values of the remaining M unknowns. Denote them as c′_{M+l−1}, c′_{M+l−2}, …, c′_{l}. Then the sequence

{c′_{l}, …, c′_{M+l−1}, c_{M+l}, c_{M+l+1}, …}  (12)

satisfies (10). But due to i) of Theorem 1 we have c′_{M+l−1} = c_{M+l−1}, …, c′_{s+l} = c_{s+l}. Observe finally that s + l = v. So (12) is an extension of (11). Setting c_{l} = c′_{l}, c_{l+1} = c′_{l+1}, …, c_{v−1} = c′_{v−1} we get (11). Let ν ≥ ord T_{i} + l where 1 ≤ i ≤ k. Then

(c_{ν}, c_{ν−1}, …, c_{l})  (13)

satisfies (as we proved immediately above) the last v − l equations of the linear algebraic system whose matrix is T_{i}^{(N)}|_{n=l}, N = ν − l − ord T_{i} + 1. Additionally (13) satisfies the remaining initial equations of the system, since (8) satisfies the recurrence T_{i}(c) = 0. Therefore (11) satisfies the recurrence T_{i}(c) = 0. The recurrence F (c) = 0 can be similarly investigated. □

Corollary 1 Let T_{1}, …, T_{k} ∈ C[n, E]. Let a sequence c = {c_{w}, c_{w+1}, …}, w ∈ ZZ, satisfy recurrences (10). Let l ∈ ZZ ⋃{infty} be such that l < w and the coefficients t_{1,0}(n), …, t_{k,0}(n) of E^{0} in T_{1}, …, T_{k} do not vanish simultaneously for n ≥ l. Then the sequence c can be uniquely extended to a sequence {c_{l}, …, c_{w−1}, c_{w}, c_{w+1}, …} satisfying recurrences (10).

Proof: Denote the greatest common right divisor of a set of operators by GCRD. Let F = GCRD(T_{1}, …, T_{k}) ∈ C[n, E] and let v ≥ w be such that the coefficients of E^{0} in T, F_{1}, …, F_{k} do not vanish for n ≥ v; by Theorem 2 we get what is claimed. □

Example 2. Consider

T_{1} = E^{2}+2E+1 = (\frac{1}{n − 1} E + \frac{1}{n − 1})∘((n − 2)E + (n − 1)) ,

T_{2} = E^{2}+nE+n = (\frac{1}{n − 1} E + \frac{n}{n − 1})∘((n − 2)E + (n − 1)) .

The sequence

c_{n} = (−1)^{n}(n − 2), n = 1, 2, …,

satisfies both recurrences T_{1}(c) = 0, T_{2}(c) = 0. According to Corollary 1 the sequence can be uniquely extended for all n. A direct check shows that the sequence

c_{n} = (−1)^{n}(n − 2), −∞ < n < ∞,  (14)

satisfies T_{1}(c) = 0, T_{2}(c) = 0.

Example 3. Consider the operator

T = (n − 2)E + (n − 1).

Although the coefficient of E^{0} has an integer root, one can still extend sequences using the fact that T is a right divisor of the first operator considered in Example 2.

Example 4. Consider the operator

T = E − n.

The sequence

c_{n} = (n − 1)!, n = 1, 2, …,

satisfies the recurrence T (c) = 0. This sequence can not be extended for n = 0 in such a way that the recurrence would still hold: by T (c) = 0 we would have c_{1} = 0. But c_{1} = 1. So we can conclude that T is not the right divisor of an element of C[n, E] whose coefficient of E^{0} does not vanish for n = 0.

4 Singularities of linear difference operators with polynomial coefficients

Let F ∈ C[n, E]

f_{d}(n)E^{d} + ⋯ + f_{0}(n)  (15)

with f_{0}(n) ≠ 0. Let f_{0}(n) have at least one integer root. Consider the following problem: is there T ∈ C[n, E] of the form (1) which is right divisible by F and such that t_{0}(n) has no integer root? First we give a simple necessary condition.

Definition 3 An operator of the form (15) is bordered if i) f_{d}(n) and f_{0}(n) both have integer roots, ii) the maximal integer root of f_{d}(n) is greater than any

integer root of f_{0}(n).

Lemma 3 Let  F  be  of  the

form (15) with gcd(f_{0}(n), …, f_{d}(n)) = 1. Let f_{0}(n) have at least one integer root. Suppose F is a right divisor of an operator T ∈ C[n, E] whose coefficient of E^{0} has no integer root. Then F is a bordered operator.

Proof: Assume F is not bordered; let l be the maximal integer root of f_{0}(n) and suppose f_{d}(n) ≠ 0 for all n > l. Choose c_{l+1}, …, c_{l+d} ∈ C such that

f_{d}(l)c_{l+d} + ⋯ + f_{1}(l)c_{l+1} ≠ 0.  (16)

Applying the recurrence F (c) = 0 we extend (c_{l+1}, …, c_{l+d}) to an infinite sequence

c = {c_{l+1}, …, c_{l+d}, c_{l+d+1}, …}.

By (16) there is no c_{l} ∈ C such that c′ = {c_{l}, c_{l+1}, …, c_{l+d}, c_{l+d+1}, …} satisfies F (c′) = 0. But due to Theorem 2 this contradicts the existence of T. □

In the remainder of this section we assume

• F to be a bordered operator of the form (15), gcd(f_{0}(n), …, f_{d}(n)) = 1;

• α to be the maximal integer root of f_{d}(n);

• f_{0}(n) to have a nonempty set Z = {l_{1}, …, l_{τ} } of integer roots, l_{1} > ⋯ > l_{τ}; the multiplicities of the integer roots l_{1}, …, l_{τ} are positive integers γ_{1}, …, γ_{τ}.

For a matrix A the matrix A|_{n=l} is A mod (n − l), i.e. A with l substituted for n. More generally, the matrix A mod (n − l)^{γ} where γ is a positive integer is the image of A in the ring of matrices over C[n]/(n − l)^{γ}. An element q ∈ C[n]/(n − l)^{γ} can be represented by a polynomial in n of degree less than γ. In this ring one has q^{γ} = 0 iff q(l) = 0 and q is invertible iff q(l) ≠ 0.

Lemma 4 Let C be the matrix F^{(α−l_{1}+1)}, D = C mod (n − l_{1})^{γ_{1}}. Assume that the last row of D is a C[n]/(n − l_{1})^{γ_{1}} linear combination of the other rows. Then there exists U ∈ C[n, E] such that

i) U is right divisible by F;

ii) order(U) ≤ α − l_{1} + order(F)

iii) The coefficient of E^{0} in U is \frac{f_{0}(n)}{(n−l_{1})^{γ_{1}}} .

Proof We can construct such a nontrivial C[n]/(n − l_{1})^{γ_{1}} linear relation of the rows of D that the coefficient of the last row of D in this relation is 1. If we take this linear relation and replace the coefficients in C[n]/(n − l_{1})^{γ_{1}} by representatives in C[n] of degree < γ_{1} then we find a C[n] linear combination of the rows of C, in which the last row occurs with coefficient 1, and this linear combination is 0 modulo (n − l)_{1}^{γ}, i.e. it is divisible by (n − l)_{1}^{γ}. This linear combination corresponds to an operator V with polynomial coefficients of degree < γ_{1}. The coefficients of operator V ∘F are polynomials divisible by (n − l_{1})^{γ_{1}}. The operator

\frac{1}{(n − l_{1})^{γ_{1}}} V ∘ F

belongs to C[n, E] and its coefficient of E^{0} is equal to f_{0}(n)/(n − l_{1})^{γ_{1}}. □

Lemma 5 Let T ∈ C[n, E] be right divisible by F and let its coefficient of E^{0} have no integer root ≥ l_{1}. Then there exists U ∈ C[n, E] such that i), ii), iii) formulated in Lemma 4 hold.

Proof: Consider the matrix A = mat(F^{(M)}, T^{(1)}) where ord T = m, M = max{α − l_{1} + 1, m − d + 1}. Set B = A mod (n − l_{1})^{γ_{1}}. We will denote elements of B by b_{ij}, i = 1, …, M + 1, j = 1, …, d + M + 1. The rows of B will be denoted by b_{1}, …, b_{M+1}. In both matrices B and A|_{n=l_{1}} the rows with number 1, …, M − 1, M + 1 have sizes d + 1, …, d + M − 1, d + M. It implies in particular that elements b_{1,d+1}, b_{2,d+2}, …, b_{M−1,d+M−1} of B are invertible in C[n]/(n − l_{1})^{γ_{1}}. Using the invertibility we can find (by the Gaussian elimination) λ_{1}, …, λ_{M−1} ∈ C[n]/(n − l_{1})^{γ_{1}} such that

λ_{1}b_{1} + ⋯ + λ_{M−1}b_{M−1} − b_{M}  (17)

is a row of size ≤ ord F. If this size is positive then the matrix B has a minor of size M +1 whose determinant is the product of M invertible elements and a non-zero element of row 17. Hence this determinant is non-zero, but by Lemma 1 the corresponding minor of A has determinant zero, and it remains zero after reducing mod (n − l_{1})^{γ_{1}}. Therefore (17) is the zero row.

If M = α − l_{1} + 1 then we are done, otherwise M > α − l_{1} + 1 and we can apply the following: Since b_{11} is invertible and b_{M1} = 0 we get λ_{1} = 0. Similarly λ_{2} = … = λ_{M−(α−l_{1}+1)} = 0. By Lemma 4 we get what was claimed. □

4.1 Algorithm ds and DS.

How can one determine if there exists T ∈ C[n, E] of the form (1) which is right divisible by F and such that t_{0}(n) has no integer root? And if it exists, how can one find such operator? Using the idea of Lemmas 4, 5 we can give an algorithm that does this step by step. It computes U_{1}, …, U_{τ} such that the coefficient of E^{0} in U_{i} is equal to f_{0}(n)/(n − l_{i})^{γ_{i}}, 1 ≤ i ≤ τ. We call this algorithm ds. If the algorithm fails then such operator T does not exist.

Set

M = α − l_{τ} + 1, C_{0} = F^{(M)}  (18)

and

k_{1} = α − l_{1} + 1, …, k_{τ} = α − l_{τ} + 1.  (19)

Together with the construction of U_{1}, U_{2}, … such that ord U_{j} ≤ d + α − l_{j}, the algorithm ds transforms the matrix C_{0} into C_{1}, C_{2}, … and, resp.,

D_{1} = C_{0} mod (n − l_{τ})^{γ_{1}}, D_{2} = C_{1} mod (n − l_{τ})^{γ_{2}}, …

The steps of constructing D_{1}, C_{1}, U_{1}; D_{2}, C_{2}, U_{2}; … (steps 1, 2, … of ds) are as follows. We find D_{1} and represent its k_{1}-th row as a linear combination over C[n]/(n − l_{τ})^{γ_{1}} of the preceding k_{1} − 1 rows. Let δ_{1}, …, δ_{k_{1}−1} ∈ C[n]/(n−l_{τ})^{γ_{1}} be the coefficients of this combination and let Δ_{1}, …, Δ_{k_{1}−1} ∈ C[n] be such that δ_{i} = Δ_{i} mod (n − l_{τ})^{γ_{1}}, i = 1, …, k_{1} − 1. Then construct the linear combination of the first k_{1} − 1 rows of C_{0} with coefficients Δ_{1}, …, Δ_{k_{1}−1} and subtract it from the k_{1}-th row of this matrix. Now all the polynomials which are the elements of k_{1}-th row are divisible by the polynomial (n−l_{τ})^{γ_{1}}. By taking the quotients we get the matrix C_{1}. Its k_{1}-th row contains (in the first d + k_{1} − 1 positions) the coefficients of E^{M−k_{1}} ∘ U_{1}. Set D_{2} = C_{1} mod (n − l_{τ})^{γ_{2}}. After this we consider the k_{2}-th row of the matrix D_{2} and represent it as a linear combination of the preceding k_{2} − 1 rows and so on. In the end we get the matrix C_{i} whose k_{j}-th row, j = 1, …, i, contains (in the first d + k_{j} − 1 positions) the coefficients of E^{M−k_{j}} ∘ U_{j} and, either i = τ or i < τ and it is not possible to construct the corresponding linear combination of the matrix D_{i} rows. Observe that for D_{i} we actually consider only its first k_{i}

rows, other rows are not involved in the computation.

The algorithm ds can stop after the i-th step, 0 ≤ i ≤ τ, if after constructing D_{i} we are not able to construct the corresponding linear combination of its rows.

Theorem 3 An operator T ∈ C[n, E] right divisible by F and such that its coefficient of E^{0} has no integer root out of the set {l_{i+1}, …, l_{τ} } exists iff the algorithm ds does not stop before D_{i}, C_{i} are completely constructed (i.e., the i-th step of the performance is terminated).

Proof: To prove the necessity we use induction on i. 1. i = 1. This case was considered in Lemma 5.

2. i > 1. The proof is similar to the proof of Lemma 5: we can consider the matrix

A = mat(F^{(M)}, T^{(1)}, (E^{M−k_{1}}∘U_{1})^{(1)}, …, (E^{M−k_{i−1}}∘U_{i−1})^{(1)})

(20)

(instead of mat(F^{(M)}, T^{(1)})).

The proof of the sufficiency is in the description of the process of constructing the matrices D_{1}, C_{1}; D_{2}, C_{2}; … □

Lemma 6 Let l_{1}, …, l_{i} be pairwise different integers, i ≥ 1. Then there exist μ_{1}, …, μ_{i} ∈ C such that the polynomial

∑_{j=1}^{i} μ_{j}(n − l_{1})^{γ_{1}} ⋯ (n − l_{j−1})^{γ_{j−1}}(n − l_{j+1})^{γ_{j+1}} ⋯ (n − l_{i})^{γ_{i}}

(21)

has no integer root. (We assume (21) to be equal to μ_{1} in the case i = 1.)

Proof: The case i = 1 is obvious. Otherwise the roots of

(21) are continuous non-constant functions of μ_{1}, …, μ_{i}. It implies what was claimed. (It is also possible to describe an algorithm to construct suitable μ_{1}, …, μ_{i}.) □

Theorem 4 If the algorithm ds does not stop before the ith step is done then there exists W_{i} ∈ C[n, E], ord W_{i} ≤ d + α − l_{i}, right divisible by F and such that the coefficient of E^{0} has no integer root out of the set {l_{i+1}, …, l_{τ} } .

Proof: Compute U_{1}, …, U_{i} by ds and, additionally μ_{1}, …, μ_{i} ∈ C such that (21) has no integer root. Then the coefficient of E^{0} in the operator μ_{1}U_{1} + ⋯ + μ_{i}U_{i} is equal to

\frac{f_{0}(n)}{(n − l_{1})^{γ_{1}} ⋯ (n − l_{i})^{γ_{i}}} ∑_{j=1}^{i} \frac{μ_{j}}{(n − l_{j})^{γ_{j}}} ∏_{k=1}^{i}(n − l_{k})^{γ_{k}}.

The claim follows from this. □

Factually we have described algorithm DS computing the maximal i, 0 ≤ i ≤ τ, such that there exists W ∈ C[n, E] right divisible by F and whose coefficient of E^{0} has no integer root out of the set {l_{i+1}, …, l_{τ} }. Algorithm DS constructs a concrete W of order ≤ d + α + l_{i} as well. If i = τ then we get W such that its coefficient of E^{0} has no integer root.

Example 5. Let F = (n − 3)(n − 2)E + (n − 1)^{2}n. Then l_{1} = 1, l_{2} = 0, α = 3, M = 4, k_{1} = 3, k_{2} = 4, C_{0} = F^{(4)} =

(\begin{matrix}n(n + 1) & (n + 2)2(n + 3) & 0 & 0 & 0 \\ 0 & (n − 1)n & (n + 1)2(n + 2) & 0 & 0 \\ 0 & 0 & (n − 2)(n − 1) & n2(n + 1) & 0 \\ 0 & 0 & 0 & (n − 3)(n − 2) & (n − 1)2n \end{matrix}) ,

D_{1} = C_{0} mod n^{2} = ( \begin{matrix}n & 16n + 12 & 0 & 0 & 0 \\ 0 & −n & 5n + 2 & 0 & 0 \\ 0 & 0 & −3n + 2 & 0 & 0 \\ 0 & 0 & 0 & −5n + 6 & n \end{matrix} ) .

First we represent the third row of D_{1} as a linear combination of the preceding two rows (using the equalities (5n + 2)^{−1} = \frac{1}{4} (−5n + 2), (16n + 12)^{−1} = \frac{1}{144} (−16n + 12) in C[n]/n^{2}). We get the coefficients \frac{n}{12} , 1 − 4n for this linear combination. Then construct the combination of the first two rows of C_{0} with polynomial coefficients \frac{n}{12} , 1 − 4n and subtract it from the third row of this matrix. After division by n^{2} we will get C_{1}:

(\begin{matrix}n(n + 1) & (n + 2)2(n + 3) & 0 & 0 & 0 \\ 0 & (n − 1)n & (n + 1)2(n + 2) & 0 & 0 \\ \frac{−n−1}{12} & \frac{−n2+41n}{12} − \frac{19}{3} & 4n2 + 15n + 17 & n + 1 & 0 \\ 0 & 0 & 0 & (n − 3)(n − 2) & (n − 1)2n \end{matrix})

We compute the operator U_{1} such that the coefficient of E^{i} in E ∘ U_{1} equals the i’th entry in row 3 in C_{1}. So the coefficients of C_{1} are shifts of the entries in this row. This operator

U_{1} = − \frac{n}{12} E^{3} +(− \frac{1}{12} n^{2} + \frac{43}{12} n− \frac{59}{6} )E^{2} +(4n^{2} +7n+6)E +n

(22)

is divisible by F and its coefficient of E^{0} vanishes only at 0. In the next step we compute

D_{2} = C_{1} mod n = ( \begin{matrix}0 & 12 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ − \frac{1}{12} & − \frac{19}{3} & 17 & 1 & 0 \\ 0 & 0 & 0 & 6 & 0 \end{matrix} )

and try to represent the last row of D_{2} as a linear combination over C of the preceding three rows. But such representation is not possible. Thus using algorithm DS we make sure that there is no operator from C[n, E] right divisible by F and whose coefficient of E^{0} has no integer root. We get operator (22) right divisible by F and whose coefficient of E^{0} has the one unique root 0 along with it.

5 The ϵ-criterion

Example 1, continued. Let F_{ϵ} be the operator obtained from the operator F in the example in section 1 by substituting n+ϵ for n. If we compute modulo ϵ then the operator has not changed, but we will compute modulo ϵ^{2}. Expressions modulo ϵ^{2} can be conveniently expressed with the O notation. If we want to extend the sequence c_{3} = 0, c_{2} = 1 to the left then we take c_{3} = 0+O(ϵ^{2}), c_{2} = 1+O(ϵ^{2}) and use with the recurrence operator F_{ϵ} to find c_{1} = 2 + 2ϵ + O(ϵ^{2}) and c_{0} = 8 + O(ϵ) (since we started with accuracy O(ϵ^{2}), and we have to divide by ϵ to find c_{0}, we can only find c_{0} with accuracy O(ϵ), which is sufficient). By substituting ϵ = 0 we find in a natural way, starting with c_{3} = 0, c_{2} = 1, the value 8 for c_{0}, even though the recurrence F does not actually define the value of c_{0}. Theorem 6 below then says that then F can be desingularized. Such a desingularization T is given in the example in section 1. Given c_{3} = 0, c_{2} = 1, we can use F to find c_{1} = 2, and then use T to find c_{0} = 8. So starting from c_{3} = 0, c_{2} = 1, we have two methods to find a value for c_{0}, and both give the same result.

In this section we assume the suppositions about F formulated after Lemma 3. Let

N = α − l_{1} + 1, C = F^{(N)}, D = C mod (n − l_{1})^{γ_{1}}.

Consider the system Cz = 0 of linear equations and investigate when this system has the following property:

P. For any z_{1}, …, z_{d} ∈ C[[n − l_{1}]] there exist z_{d+1}, …, z_{d+N} ∈ C[[n − l_{1}]] such that (z_{1}, …, z_{d+N})^{T} is a solution of Cz = 0.

Lemma 7 The system Cz = 0 has property P iff the last row of D is a linear combination over C[n]/(n − l_{1})^{γ_{1}} of its preceding rows.

Proof: Let z_{1}, …, z_{d} ∈ C[[n − l_{1}]]. The invertibility in C[[n−l_{1}]] of the elements of C with indices (1, d+1), (2, d+ 2), …, (N − 1, d + N − 1) implies that z_{d+1}, …, z_{d+N−1} ∈ C[[n − l_{1}]] are uniquely determined by the first N − 1 equations of the system Cz = 0. If we substitute the z_{1}, …, z_{d+N−1} into the N-th equation then we get the equality

z_{d+N} = \frac{s}{f_{0}(n − l_{1})}  (23)

for some s ∈ C[[n − l_{1}]].

Let the N-th row of D be a linear combination over C[n]/(n − l_{1})^{γ_{1}} of its preceding rows. Then one can substract from the last row in C a C[[n − l_{1}]]-linear combination of the other rows, and obtain a row that is divisible by (n − l_{1})^{γ_{1}}. Dividing this row by (n − l_{1})^{γ_{1}} makes the entry C_{N,d+N} invertible, and so this row allows one to find z_{d+N} ∈ C[[n − l_{1}]]. The converse is proved in a similar way. □

So if the system has property P then its last equation can be replaced by an equation whose last coefficient does not vanish at n = l_{1} (the process of building such an equation was described in Lemma 4). The new system C′z = 0 allows, starting with z_{1}, …, z_{d} ∈ C[[n − l_{1}]], to determine uniquely the z_{d+1}, …, z_{d+N} as solutions of the system Cz = 0. But now the system with the matrix C′ mod (n − l_{1})^{γ_{1}} allows to find in particular z_{d+N} mod (n − l_{1})^{γ_{1}}. Using this line of reasoning and considering l_{2}, …, l_{τ} we get the following theorem on the system with matrix C_{0} of the form (18) (this theorem is an analogue of Theorem 3):

Theorem 5 The algorithm ds does not stop before D_{i}, C_{i} are completely constructed iff for any z_{1}, …, z_{d} ∈ C[[n − l_{τ}]] there exist z_{d+1}, …, z_{d+α−l_{i}+1} ∈ C[[n − l_{τ}]] such that z_{1}, …, z_{d+α−l_{i}+1} ∈ C[[n − l_{τ}]] satisfy the first α − l_{i} + 1 equations of the system C_{0}z = 0. □

Below we will reformulate this theorem in a more convenient form. First we make two remarks.

R1. It is sufficient to consider the d following possibilities for (z_{1}, …, z_{d}):

(1, 0, …, 0), (0, 1, …, 0), …, (0, 0, …, 1).  (24)

R2. For each vector of (24) the corresponding z_{d+1}, z_{d+2}, … belong to C(n). The solvability of the system C_{0}z = 0 in C[[n − l_{τ}]] is equivalent to the fact that these rational functions do not have a pole at n = l_{τ}.

Consider the algorithm H_{ϵ} which can be applied to F, (z_{1}, …, z_{d}), k, where F is an operator of the form (15), z_{1}, …, z_{d} ∈ C and k is non-negative integer:

1. Construct the operator F_{ϵ} by replacing n by n + ϵ in the coefficients of F (ϵ is an additional variable).

2. Taking c_{α+d} = z_{1}, c_{α+d−1} = z_{2}, …, c_{α+1} = z_{d} and using the recurrence F_{ϵ}(c) = 0 to compute c_{α}, …, c_{α+k−1} ∈ C(ϵ).

Theorem 6 (The ϵ-criterion.) The algorithm ds does not stop before D_{i}, C_{i} are completely constructed (i.e., before the i-th step of the algorithm is terminated) and, as a consequence there exists a right divisible by F operator T ∈ C[n, E] whose coefficient of E^{0} has no integer root out of {l_{i+1}, …, l_{τ} }, iff applying H_{ϵ} to any (z_{1}, …, z_{d}) of the form (24) and to k = α − l_{i} + 1 gives rational functions which do not have poles at ϵ = 0.

Proof: Taking into account remarks R1, R2 we see that this theorem is a reformulation of Theorem 5 when the notation ϵ = n − l_{τ} is used. □

Example 6. Let F = (n − 3)(n − 2)E + n(n − 1). Here d = 1, hence in (24) we have one unique vector with single element 1. F_{ϵ} = (n + ϵ − 3)(n + ϵ − 2)E + (n + ϵ − 1)(n + ϵ), i.e.,

c_{n} = − \frac{(n + ϵ − 3)(n + ϵ − 2)}{(n + ϵ − 1)(n + ϵ)} c_{n+1}.

Setting c_{4} = 1 we get

c_{3} = − \frac{ϵ(ϵ + 1)}{(ϵ + 3)(ϵ + 2)} , c_{2} = \frac{(ϵ − 1)ϵ^{2}}{(ϵ + 2)^{2}(ϵ + 3)} ,

c_{1} = − \frac{(ϵ − 2)(ϵ − 1)^{2}ϵ}{(ϵ + 1)(ϵ + 2)^{2}(ϵ + 3)} , c_{0} = \frac{(ϵ − 3)(ϵ − 2)^{2}(ϵ − 1)}{(ϵ + 1)(ϵ + 2)^{2}(ϵ + 3)} .

We can desingularize F since neither c_{1} nor c_{0} have the pole at ϵ = 0. Using DS we get

W = (n+1)E^{4}+(−17n+29)E^{3}+(−17n−56)E^{2}+(7n−11)E−1.

Example 5, continued. Consider again F from Example 5. Here d = 1, F_{ϵ} = (n + ϵ − 3)(n + ϵ − 2)E + (n + ϵ − 1)^{2}(n + ϵ) and

c_{n} = − \frac{(n + ϵ − 3)(n + ϵ − 2)}{(n + ϵ − 1)^{2}(n + ϵ)} c_{n+1}.

Setting c_{4} = 1 we get

c_{3} = − \frac{ϵ(ϵ + 1)}{(ϵ + 3)(ϵ + 2)^{2}} , c_{2} = \frac{(ϵ − 1)ϵ^{2}}{(ϵ + 1)(ϵ + 2)^{2}(ϵ + 3)} ,

c_{1} = − \frac{(ϵ − 2)(ϵ − 1)^{2}ϵ}{(ϵ + 1)^{2}(ϵ + 2)^{2}(ϵ + 3)} , c_{0} = \frac{(ϵ − 3)(ϵ − 2)^{2}}{ϵ(ϵ + 1)^{2}(ϵ + 2)^{2}(ϵ + 3)} .

We can desingularize F only partially since c_{0} has a pole at ϵ = 0 (as was found before).

As illustrated in example 1 continued, one can also compute modulo ϵ^{a+1} where a is the number of times we have to divide by ϵ. This is usually more efficient. Note that the ϵ-method of extending sequences is used in [2] to determine pole orders of rational solutions. It is used in [3] to determine valuation growths and extension maps E_{p,r} which can be used for computing hypergeometric solutions.

6 Extended algorithms

6.1 Decreasing of the root multiplicity

If it is impossible to eliminate an integer root of the coefficient of E^{0} in a given operator F, then one can try to decrease the multiplicity (in case it is > 1). Actually if the corresponding linear algebra problem is not solvable modulo (n − l)^{γ} then it is still possible that the problem is solvable modulo (n − l)^{γ′}, γ′ < γ. Hence the algorithms ds, DS can be extended in such a way that in case if it is impossible to perform the next-in-turn step and, this step is connected with computations modulo (n−l)^{γ} then we try to perform it modulo (n−l)^{γ−1} and so on. Only after this additional step the running of extended versions of ds, DS are terminated. One can observe the following. The proof of Lemma 3 shows that if F is bordered then the decreasing of the multiplicity of l_{1} is possible iff any sequence {c_{l_{1}+1}, c_{l_{1}+2}, …} satisfying the equation F (y) = 0 can be extended by an element c_{l_{1}} so that {c_{l_{1}}, c_{l_{1}+1}, c_{l_{1}+2}, …} satisfies the same equation.

6.2 Roots of the leading coefficient

The desingularization problem can be considered as being applied to the leading coefficient of the operator F. We will use analogous (with respect to the already considered problem) algorithms if F = f_{0}(n)+f_{−1}(n)E^{−1} +⋯+f_{−d}(n)E^{−d} and we are looking for an operator of the form

S = s_{0}(n) + s_{−1}(n)E^{−1} + ⋯ + s_{−m}(n)E^{−m}  (25)

which is right divisible by F and such that s_{0}(n) has, say, no integer root (the only distinction is that we have to consider integer roots in increasing order). However if S has the form (25) then T = E^{m} ∘ S has the form (1). If F has the form (15) we can consider the integer roots l_{1} < … < l_{τ} (with multiplicities γ_{1}, …, γ_{τ}) of the polynomial f_{d}(n − d); it is possible to describe the algorithm ds^{+} that constructs operators T_{1}, …, T_{i} right divisible by F such that T_{j} = t_{j,m_{j}} (n)E^{m_{j}} + … + t_{j,0}(n) and

t_{j,m_{j}} (n − m_{j}) = \frac{f_{d}(n − d)}{(n − l_{j})^{γ_{j}}} ,

j = 1, …, i, for the largest possible i < τ. Similarly we can describe DS^{+} which constructs T of the form (1) such that t_{m}(n − m) has no integer root out of the set {l_{i+1}, …, l_{τ} }.

6.3 Non-integer roots

The described algorithms can be applied to eliminate noninteger roots. Instead of ZZ we can consider an arbitrary set c + ZZ where c is a fixed complex number. The idea of the greatest factorial factorization [5] is quite convenient for this. This, combined with corollary 1, can be used for bounding the set of poles of rational solutions (c.f. [1, 2]) of systems of linear difference equations.

In conclusion of this section remark that the ϵ-criterion can be extended for all the cases considered in subsections 6.1, 6.2, 6.3.

7 An application

We call the order of a P -recursive sequence (8) the order of the minimal operator which annihilates a sequence c′ = {c_{N}, c_{N+1}, …} where N is an integer ≥ v. For example, the order of any hypergeometric sequence is equal to 1. Let T of the form (1) have solution c of order d and F of the form (15) be the corresponding minimal annihilator. If we want to know a concrete N for the sequence c′ satisfying both equalities T (c′) = 0, F (c′) = 0 we at the first glance should take into account the form of F. But by Corollary 1 we can clam that the equation T (y) = 0 has a solution of order d with N = n_{0} +1, where n_{0} is the largest integer root of t_{0}(n) if such roots exist and n_{0} = −∞ otherwise. Furthemore, let F be the minimal annihilator for a sequence c of the form (8) and as before F be a right divisor of T. Then there exists a sequence d = {d_{n_{0}+1}, d_{n_{0}+2}, …} satisfying T (d) = F (d) = 0 such that c_{i} = d_{i} for all i ≥ max{n_{0} + 1, v}.

Example 7. Going back to Example 2 we see that T = T_{1} is right divisible by F = (n − 2)E + (n − 1). Let c_{n} = (−1)^{n+1}(n − 2) for n = 2, 3, … Then defining additionally c_{0}, c_{1} as, resp.,

c_{0} = c_{1} = 0; c_{0} = 2, c_{1} = −1; c_{0} = −2, c_{1} = 1

we get three sequences of first order c′, c′′, c′′′ that satisfy the equation F (y) = 0. At the same time the sequence c of the form (14) satisfies the equation T (y) = 0 and this sequence coincides with the sequences c′, c′′′ for n ≥ 2 and coincides with c′′ for n ≥ 0.

References

[1] S.A. Abramov, M.A. Barkatou (1998): Rational solutions of first order difference systems. Proc. ISSAC’98, 124–131.

[2] M. van Hoeij (1998): Rational solutions of linear difference equations. Proc. ISSAC’98, 120–123.

[3] M. van Hoeij (1999): Finite singularities and hypergeometric solutions of linear recurrence equations. to appear in Journal of Pure and Applied Algebra.

[4] N.E. Nörlund (1929): Leçons sur les equations linéaires aux différences finies. Gauthiers Villars et Cie, Paris.

[5] P. Paule (1995): Greatest factorial factorization and symbolic summation. Journal of Symbolic Computation 20, 235–268.