Set of Poles of Solutions of Linear Difference Equations with Polynomial Coefficients

S. A. Abramov^{∗}

Russian Academy of Sciences, Dorodnicyn Computing Centre,

Vavilova 40, 119991, Moscow GSP-1,

Russia

          abramov@ccas.ru

M. van Hoeij^{†}

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

                                        hoeij@math.fsu.edu

Abstract

We present an approach to sharpen the bounds for the set of poles of meromorphic solutions of difference equations with polynomial coefficients. The desingularization of the operator corresponding to the given equation plays the key role.

Additionally we consider certain problems related to the existence of solutions that are analytic (or r times continuously differentiable, or continuous) everywhere on ℝ.

1 Introduction

Let E be the shift operator defined on functions of x as Ey(x) = y(x + 1). Let L ∈ ℝ[x, E], i.e. L is an operator of the form

a_{d}(x)E^{d} + ⋯ + a_{1}(x)E + a_{0}(x)  (1)

with a_{i}(x) ∈ ℝ[x], i.e. a_{i}(x) is a polynomial in x with coefficients in ℝ. Denote ℝ(x) as the field of quotients of ℝ[x]. An operator T ∈ ℝ[x, E] is right divisible over ℝ(x) by L if there exists an operator G ∈ ℝ(x)[E] such that T = G ∘ L. Here ℝ(x)[E] is the set of all ∑_{i=0}^{m} r_{i}(x)E^{i} with r_{i}(x) ∈ ℝ(x). Suppose that the trailing coefficient a_{0}(x) of L vanishes for some values of x. The following two problems are handled in [1]: (a) Does there exist an operator T ∈ ℝ[x, E] right divisible over ℝ(x) by L such that the set of the roots of the trailing coefficient of T is a proper subset of the set {x | a_{0}(x) = 0}? (It is desirable to eliminate as many of the roots of a_{0}(x) as possible.) (b) If the answer to problem (a) is positive, then how can one compute such an operator T? This elimination process is named the desingularization of L w.r.t. the trailing coefficient. A similar process can be applied to the leading coefficient. The algorithm essentially reduces the aforementioned problems to linear algebra problems. Additionally, the so-called ε-algorithm is used in [1]. This algorithm helps to answer quickly certain questions related to the feasibility of the desingularization without the need to construct the corresponding operators. In Sect. 2 we consider an application of these algorithms in sharpening the bounds for the set of poles of solutions of difference equations with polynomial coefficients.

∗Supported by RFBR grant 01-01-00047.

†Supported by NSF grant 0098034.

Let L be of the form (1). If a solution of the equation LF (x) = 0 is analytic on an interval (A, B), B − A > d = ord L, then, evidently, F (x) is meromorphic on ℝ. In Sect. 3 we describe necessary and sufficient conditions for the analyticity of F (x) everywhere on ℝ. These conditions are represented as a finite set of linear relations among the values of F (x) and some of its derivatives at some points q_{1}, …, q_{τ} ∈ (A, B). These linear relations and the points q_{1}, …, q_{τ} are built beginning with L and A, B, where q_{1}, …, q_{τ} can be selected in any preassigned semi-interval of length d that belongs to (A, B).

We show that the exact evaluation of the values of F (x) at problem points is possible, if the mentioned relations hold. Similar questions related to the differentiability and continuity of F (x) are also considered.

2 Set of Poles

2.1 Supplementary Poles

For a ∈ ℝ, denote by a^{−} the set {a, a − 1, a − 2, …}, and by a^{+} the set {a, a + 1, a + 2, …}. For p(x) ∈ ℝ[x] and c ∈ ℝ, denote

{p(x)}_{c}^{−} = ⋃_{p(a)=0, a≤c} a^{−}, {p(x)}_{c}^{+} = ⋃_{p(a)=0, a≥c} a^{+}.

Let A, B ∈ ℝ, A < B, and V be the interval

(A, B).  (2)

Let L be an operator of the form (1), and F (x) be a meromorphic solution of L, so LF = 0. The poles of F in V can give rise to poles outside V; these poles are in the set

W = ⋃_{v}{v ± 1, v ± 2, …} \ V,

where v runs through the set of the poles belonging to V.

Additionally, supplementary poles can occur (i.e., the poles, that originate from the operator). The following proposition is well-known.

Proposition 1 Let B − A > d. The poles of F (x) that are not in the set V ∪ W (i.e., the poles supplementary w.r.t. V) belong to the set M_{1} ∪ M_{2} where

M_{1} = {a_{d}(x − d)}_{B}^{+}, M_{2} = {a_{0}(z)}_{A}^{−}.  (3)

2.2 Desingularization and Analysis of Supplementary Poles

Proposition 1 admits a natural generalization as stated in the following theorem.

Theorem 1 Let S, T be operators from ℝ[x, E] right divisible over ℝ(x) by

L = a_{d}(x)E^{d} + ⋯ + a_{0}(x),

ord S = m, ord T = m′. Let t_{0}(x) be the coefficient of E^{0} in T and s_{m}(x) be the coefficient of E^{m} in S. Let F (x) be a meromorphic function such that LF (x) = 0 and V be the interval (A, B). Let B − A > max{m, m′}. Then the set of the poles of F (x), supplementary w.r.t. V, belongs to the set M_{1} ∪ M_{2} where

M_{1} = {s_{m}(x − m)}_{B}^{+}, M_{2} = {t_{0}(x)}_{A}^{−}.  (4)

This theorem allows one to use the desingularization for sharpening the set of poles of solutions of difference equations.

Example 1. As a simple illustration, consider the difference equation

(x − ν) y(x + 1) − x y(x) = 0, ν ∈ ℕ \ {0}.

Set V = (A, B) = (−ν − 1, 0). It follows from Proposition 1 that the supplementary poles belong to the set {ν + 1, ν + 2, …}. However, the εalgorithm [1] confirms the feasibility of the desingularization w.r.t. both the leading and the trailing coefficients, and the corresponding operators are of order ν + 1 (actually, (x − ν)E − x right-divides (E − 1)^{ν+1}). Therefore, by using the idea of desingularization (the ε-algorithm) and by applying Theorem 1 to (x − ν)E − x, we conclude that there exists no pole supplementary w.r.t. V.

3 Analytic, differentiable and continuous solutions

If F (x) satisfies on ℝ an equation LF (x) = 0:

a_{d}(x)F (x + d) + ⋯ + a_{1}(x)F (x + 1) + a_{0}(x)F (x) = 0,  (5)

and F (x) is analytic on V = (A, B) and if, additionally, d < B − A, then, evidently, F (x) is meromorphic on ℝ. The question is, which additional conditions should F (x) satisfy on V in order to be analytic everywhere on ℝ? We describe necessary and sufficient conditions for F (x) to be analytic for x ≥ B; the case x ≤ A can be considered similarly.

3.1 One step computation

Suppose that q is such that q, q + 1, …, q + d − 1 < B, q + d ≥ B. At each of points

q + i, i = 0, 1, …, d − 1,  (6)

there exists the series

∑_{ν=0}^{∞} a_{iν}ε^{ν}, a_{iν} = \frac{F^{(ν)}(q + i)}{ν!},  (7)

for F (q + i + ε) with a non-zero convergence radius. If we know those series for points (6), then, using (5), we can construct the corresponding series (generally speaking, Laurent) for the points q + d, q + d + 1, … To do this, we consider ε as a variable and substitute x + ε for x into (5). We obtain the transformed equation L_{ϵ}F (x + ε) = 0:

a_{d}(x+ε)F (x+d+ε)+⋯+a_{1}(x+ε)F (x+1+ε)+a_{0}(x+ε)F (x+ε) = 0. (8)

The substitution x = q into this equation results in the equation

a_{d}(q + ε)F (q + d + ε) + ⋯ + a_{1}(q + ε)F (q + 1 + ε) + a_{0}(q + ε)F (q + ε) = 0 for the series F (q + d + ε); notice that a_{0}(q + ε), …, a_{d}(q + ε) ∈ ℝ[ε]. We can compute the series

a_{d−1}(q + ε)F (q + d − 1 + ε) + ⋯ + a_{0}(q + ε)F (q + ε)

and multiply it by the series expansion of

−\frac{1}{a_{d}(q + ε)}.

If a_{d}(q) = 0 then the product can involve ε with negative exponents, and the absolute value of the minimal exponent does not exceed the multiplicity μ of the root q of the polynomial a_{d}(x). The coefficients of ε^{−1}, …, ε^{−μ} in the obtained expansion of F at the point q +d, i.e. the expansion of F (q +d+ε) at ε = 0, can be represented as linear combinations of the coefficients

a_{iν}, i = 0, 1, …, d − 1, ν = 0, 1, …, μ − 1,

from (7). Therefore the coefficients of ε^{−1}, ε^{−2}, … vanish iff the values of F (x) and its derivatives F′(x), …, F^{(μ−1)}(x) at points (6) satisfy μ linear conditions that can be derived using the transformed operator L_{ϵ} and q. The coefficients of ε^{n}, n ≥ 0, of the expansion of F (q + d + ε) also can be represented as linear combinations of the values of F (x) and its derivatives at (6). It is easy to see that to obtain the linear conditions that guarantee the analyticity of F (x) at q + d we need only the first μ coefficients of each of these series (not the whole series (7)).

Example 2. Consider the equation xF (x + 2) − (3x − 3)F (x + 1) + (2x − 3)F (x) = 0. Let A = −1, B = 1.5. We obtain the transformed equation (x + ε)F (x + 2 + ε) − (3x − 3 − 3ε)F (x + 1 + ε) + (2x − 3 + 2ε)F (x + ε) = 0. Set q = 0, F (ε) = a_{00} + a_{01}ε + …, F (1 + ε) = a_{10} + a_{11}ε + … Using the transformed equation we obtain

F (2+ε) = ε^{−1}((−3−3ε)(a_{10}+a_{11}ε+…)−(−3+2ε)(a_{00}+a_{01}ε+…)+…) =

(3a_{00} − 3a_{10})ε^{−1} + (−2a_{00} + 3a_{01} − 3a_{10} − 3a_{11})ε^{0} + …

Setting the coefficient of ε^{−1} to 0, we obtain the necessary and sufficient condition of the analyticity in the form

F (0) − F (1) = 0.  (9)

The coefficient of ε^{0} gives the expression for F (2) in the form −2F (0) + 3F′(0) + 3F (1) − 3F′(1), that can be rewritten as F (0) + 3F′(0) − 3F′(1) by (9). Notice that the original equation has analytic solutions, for example F (x) = sin (2πkx) or cos (2πkx) for any integer k; it is easy to see that (9) as well as F (2) = F (0) + 3F′(0) − 3F′(1) are valid for these solutions.

3.2 Classes of roots of the leading coefficient

All roots of the polynomial a_{d}(x) that are greater than or equal to B can be arranged in disjoint maximal classes in such manner that the numbers in each class differ only by integers. Following the reasoning of Sect. 3.1 we get the theorem.

Theorem 2 Let LF (x) = 0 be equation of the form (5). Let {p_{1}, …, p_{l}} be a class of the roots of a_{d}(x) which are greater or equal to B, p_{1} < … < p_{l}, and let μ_{1}, …, μ_{l} be the multiplicities of these roots, m_{i} = μ_{1} + ⋯ + μ_{i}, i = 1, 2, …, l. Let q ∈ (A, B), d < B − A, be such that p_{1} − q ∈ ℤ and q +d−1 < B. Then one can construct matrices M_{1}, …, M_{l} whose sizes are, respectively,

μ_{1} × dm_{1}, …, μ_{l} × dm_{l},

such that a function F (x) which is analytic on (A, B) and satisfies LF (x) = 0 on ℝ is analytic at all x ≥ B for which x − q ∈ ℤ}, iff

M_{i}f_{i} = 0, i = 1, 2, …, l,  (10)

where

f_{i} = (F (q), …, F^{(m_{i})}(q), …, F (q + d − 1), …, F^{(m_{i})}(q + d − 1))^{T}.

Additionally one can construct matrices (rows) S_{1}, …, S_{l}, whose sizes are, respectively, 1 × dm_{1}, …, 1 × dm_{l} such that if conditions (10) are satisfied, then the values F (p_{1}), …, F (p_{l}) are, respectively, equal to

S_{1}f_{1}, …, S_{l}f_{l}.  (11)

Considering all classes of the roots of a_{d}(x) we obtain necessary and sufficient conditions of the analyticity of F (x). For the case where F (x) is analytic we obtain also an algorithm to compute F (x) at the problem points, i.e. at the points that are of the form either t−d, where a_{q}(t) = 0, t−d ≥ B, or s, where a_{0}(s) = 0, s ≤ A (the direct use of equation (5) does not work to compute F (x) at those points).

We can consider continuous differentiability (say, r times) of F (x) instead of analyticity. Then we will use expressions of the form ∑_{ν=0}^{r+m_{l}} a_{ν}ε^{ν} + o(ε^{r+m_{l}}) instead of series (7), and the conditions formulated in Theorem 2 become necessary and sufficient conditions for a function F (x) (r +m_{l} times continuously differentiable on (A, B)) to be at least r times continuously differentiable at all points of the set p_{1}^{+} = {p_{1}, p_{1} + 1, …}. If r = 0, we get conditions for continuity.

Example 3. Let

L = 2(x − 2)(x − 3)E^{2} − (3x + 7)(x − 3)E + (x + 3)(x + 1).

Let F (x) be a solution of L, so LF (x) = 0. Assume that F (x) is at least twice continuously differentiable at x = 0 and x = 1. Then we can write

F (0 + ε) = a_{00} + a_{01}ε + a_{02}ε^{2} + o(ε^{2}),
F (1 + ε) = a_{10} + a_{11}ε + a_{12}ε^{2} + o(ε^{2}).

Using the transformed equation we can now calculate similar expansions at x = 2, 3, … and at x = −1, −2, … However, although we have the values of F, F′, F′′ at 0 and 1 (i.e. we have the ε^{ν} terms for ν = 0, 1, 2 at x = 0, 1) we can not compute as many terms at other points, because each time we divide by ε we will lose some terms. In the expansions given below, we will only give those terms for which we know in advance that they can be expressed in terms of a_{iν}, i = 0, 1, ν = 0, 1, 2.

F (2 + ε) = −\frac{1}{4} a_{00} − \frac{7}{4} a_{10} + (−\frac{13}{24} a_{00} − \frac{13}{8} a_{10} − \frac{1}{4} a_{01} − \frac{7}{4} a_{11}) ε
+ (−\frac{71}{144} a_{00} − \frac{13}{24} a_{01} − \frac{13}{16} a_{10} − \frac{1}{4} a_{02} − \frac{13}{8} a_{11} − \frac{7}{4} a_{12}) ε^{2}
+ o(ε^{2}),
F (3 + ε) = \frac{27}{4} a_{10} + \frac{5}{4} a_{00} + (15 a_{10} + \frac{27}{4} a_{11} + \frac{13}{3} a_{00} + \frac{5}{4} a_{01}) ε
+ (\frac{27}{4} a_{12} + \frac{13}{3} a_{01} + 20 a_{10} + \frac{5}{4} a_{02} + 15 a_{11} + \frac{137}{18} a_{00}) ε^{2}
+ o(ε^{2}),
F (4 + ε) = (\frac{123}{4} a_{10} + \frac{25}{4} a_{00}) ε^{−1} + \frac{1205}{16} a_{10} + \frac{123}{4} a_{11} + \frac{1109}{48} a_{00} + \frac{25}{4} a_{01}
+ (\frac{123}{4} a_{12} + \frac{1109}{48} a_{01} + \frac{3415}{32} a_{10} + \frac{25}{4} a_{02} + \frac{1205}{16} a_{11} + \frac{12397}{288} a_{00}) ε

+ o(ε),
F (5 + ε) = \frac{165 a_{10} + 35 a_{00}}{ε} + \frac{2159}{8} a_{10} + 165 a_{11} + \frac{2423}{24} a_{00} + 35 a_{01} + o(1).

Using the transformed equation in the opposite direction we find

F (−1 + ε) = \frac{−8 a_{00} − 12 a_{10}}{ε} + 13 a_{10} − 8 a_{01} − 12 a_{11}
+ (\frac{3}{2} a_{00} − \frac{15}{2} a_{10} − 8 a_{02} + 13 a_{11} − 12 a_{12}) ε + o(ε),
F (−2 + ε) = \frac{−40 a_{00} − 60 a_{10}}{ε} − 40 a_{01} − 72 a_{00} − 60 a_{11} − 103 a_{10}
+ (−60 a_{12} + \frac{241}{2} a_{10} − 72 a_{01} − \frac{53}{2} a_{00} − 103 a_{11} − 40 a_{02}) ε
+ o(ε),
F (−3 + ε) = \frac{540 a_{10} + 120 a_{00}}{ε} − 1773 a_{10} − 404 a_{00} + 120 a_{01} + 540 a_{11}
+ o(1).

Note that computing truncated power series at each point in this way is used in [2] for computing hypergeometric solutions.

Because we only started with coefficients up to ε^{2}, after a division by ε the coefficients of ε^{2} can no longer be determined. Two divisions by ε were needed to reach x = −3 and x = 5, that is why the coefficient of ε^{1} is not given at those points.

Divisions by ε take place at the following points: x = 4, x = 5, x = −1, x = −3. If we want F (x) to be continuous at those points then we get the following linear conditions:

\frac{123}{4} a_{10} + \frac{25}{4} a_{00} = 165 a_{10} +35 a_{00} = −8 a_{00} −12 a_{10} = −40 a_{00} −60 a_{10} = 0.

After Gaussian elimination one finds that this system is equivalent to a_{00} = a_{10} = 0. So it turns out that there are no conditions on a_{iν} when ν = 1 or ν = 2. In general such conditions do occur. We conclude: If F (x) is twice continuously differentiable at x = 0 and x = 1, and LF (x) = 0, then F is continuous at all integers iff F (0) = F (1) = 0. In that case, the values of F (x) at integer points can be expressed in terms of the a_{iν} by substituting ε = 0 in the expansions given above. The substitution gives, e.g., F (−3) = 120F′(0) + 540F′(1). If, in addition, F (x) is continuous on some interval of length > 2 then F (x) will be continuous on ℝ.

Example 4. Let

L = x^{2}E^{2} + (1 + x^{2})E − x

and let F (x) be a solution of L. Assume again that F (x) is at least two times continuously differentiable at x = 0 and x = 1, and write

F (0 + ε) = a_{00} + a_{01}ε + a_{02}ε^{2} + o(ε^{2}),
F (1 + ε) = a_{10} + a_{11}ε + a_{12}ε^{2} + o(ε^{2}).

We calculate:

F (2 + ε) = −\frac{a_{10}}{ε^{2}} + \frac{−a_{11} + a_{00}}{ε} − a_{10} − a_{12} + a_{01} + o(1).

One sees that if F is analytic at 0 and 1 then F is analytic at all integer points iff F (1) = 0 and F′(1) = F (0). In that case, e.g., one gets F (2) = F′(0)−F′′(1). It is easy to verify that (x−1)cos (πx) is an analytic solution, and that it satisfies this condition.

Acknowledgment

We would like to thank H. Le and S.Yu. Slavyanov who provided us with useful comments on an earlier draft.

References

[1] Abramov S.A, van Hoeij M. Desingularization of linear difference operators with polynomial coefficients// Proc. ISSAC’99. Vancouver. 1999. P. 269–275.

[2] van Hoeij M. Finite singularities and hypergeometric solutions of linear recurrence equations// J. Pure Appl. Algebra. 1999. V. 139. P. 109–131.