Solutions of linear differential equations in the class of sparse power series

Sergei A. Abramov^{∗}

Computer Center of the Russian Academy of Science Vavilova 40, Moscow 117967, Russia abramov@ccas.ru, sabramov@cs.msu.su

Abstract

We introduce the notion of the m-sparse power series (e.g. expanding sin x and cos x at x = 0 gives 2-sparse power series: a coefficient a_{n} of the series can be nonzero only if remainder(n, 2) is equal to a fixed number). Then we consider the problem of finding all m-points of a linear ordinary differential equation Ly = 0 with polynomial coefficients (i.e. the points at which the equation has a solution in the form of an m-sparse series). It is easy to find an upper bound for m. We prove that if m is fixed then either there exists a finite number of m-points and all of them can be found or all points are m-points and L can be factored L = L_{1} ∘ C where C is an operator of a special kind with constant coefficients. Additionally we formulate simple necessary and sufficient conditions for the existence of m-points for an irreducible L.

Combining the algorithms described in the paper with Petkovšek-Salvy’s algorithm we find all m-sparse m-hypergeometric solutions of the equation Ly = 0.

Résumé

On introduit la notion de série de puissances m-creuse. (Les dévéloppements de sin x et de cos x autour de x = 0 sont des exemples de séries 2-creuses: on demande que le coefficient a_{n} de la série soit non-nul seulement si n appartient à une classe fixée de residus modulo 2). On considère le problème de déterminer tous les m-points d’une équation différentielle linéaire Ly = 0 à coefficients polynomiaux (i.e. les points où l’équation admet une solution sous forme m-creuse). Il est facile de trouver une borne supérieure pour m. Pour m fixé on démontre qu’ou bien il existe un nombre fini de m-points et on peut les déterminer, ou bien tous les points sont des m-points et L peut se factoriser en L = L_{1} ∘ C où C est un opérateur d’un type particulier à coefficients constants. En plus, on donne des critères nécessaires et suffisants simplespour l’existence de m-points lorsque l’opérateur L est irréductible.

En combinaisant les algorithmes de cet article avec l’algorithme de Petkovšek-Salvy on peut obtenir toutes les solutions m-creuses et m-hypergéométriques de l’équation Ly = 0.

∗Supported in part by the RFBR and INTAS under Grant 95-IN-RU-412.

1 m-Sparse sequences and series

Let C be the set of infinite sequences (c_{0}, c_{1}, …) ∈ C^{|}^{|} ^{∞}, S be the set of formal power series c_{0}+c_{1}x+… with (c_{0}, c_{1}, …) ∈ C and m be an integer ≥ 2. Call c = (c_{0}, c_{1}, …) ∈ C an m-sparse sequence if there exists an integer N such that

(c_{n} ≠ 0) ⇒ (n = N (mod m)).  (1)

Denote by C^{(m)} (resp. S^{(m)}) the set of all m-sparse elements of C (resp. the set of all elements of S, whose sequences of coefficients are in C^{(m)}). Example 1 The series x + x^{4} + x^{7} + … + x^{3n+1} + … is 3-sparse, i.e. belongs to S^{(3)} with N = 1.

It is obvious that

(m_{1}|m_{2}) ⇒ (C^{(m_{2})} ⊂ C^{(m_{1})}, S^{(m_{2})} ⊂ S^{(m_{1})}).

Consider a linear ordinary differential equation Ly = 0 with

L = p_{r}(x)D^{r} + … + p_{1}(x)D + p_{0}(x),  (2)

p_{0}(x), …, p_{r}(x) ∈ C^{|}^{|} [x], p_{r}(x) ≠ 0. Our goal is to find all a ∈ C^{|}^{|} and formal power series solutions

y_{a}(x) = ∑_{n=0}^{∞} c_{n}(x − a)^{n}  (3)

such that

Ly_{a}(x) = 0  (4)

and (c_{0}, c_{1}, …) ∈ C^{(m)}. Observe that y_{a}(x) satisfies (??) iff

y(x) = ∑_{n=0}^{∞} c_{n}x^{n}

satisfies L^{a}y(x) = 0 where

L^{a} = p_{r}(x + a)D^{r} + … + p_{1}(x + a)D + p_{0}(x + a).  (5)

We will consider the problem of finding m and a such that the equation L^{a}y = 0 has a solution in S^{(m)}.

2 m-Points

It is well known that the power series coefficients of a solution of a linear differential equation with polynomial coefficients satisfy a linear recurrence (a difference equation) Rc = 0 with polynomial coefficients:

q_{d}(n)c_{n+d} + … + q_{l}(n)c_{n+l} = 0,  (6)

d > ... > l; q_{l}(n), …, q_{d}(n) ∈ C^{|}^{|} [n]; q_{d}(n), q_{l}(n) ≠ 0.

The operator R which is equal to

q_{d}(n)E^{d} + ⋯ + q_{l}(n)E^{l}  (7)

is the R-image of L where R is the isomorphism of C^{|}^{|} [D, x, x^{−1}] onto C^{|}^{|} [E, E^{−1}, n]:

RD = (n + 1)E, Rx = E^{−1}, Rx^{−1} = E;  (8)

resp.

R^{−1}E = x^{−1}, R^{−1}E^{−1} = x, R^{−1}n = xD

(see [?]). Note that it is possible l < 0 in (??),(??). For R of the form (??) we denote ω(R) = d − l. If the coefficient of x^{i} in the polynomial p_{j}(x) is not equal to zero then we write x^{i}D^{j} ∈ L. It is easy to check that if L is of the form (??) and R = RL then

d = max_{x^{i}D^{j}∈L}{j − i}, l = min_{x^{i}D^{j}∈L}{j − i};  (9)

and therefore ω(R) is equal to

max_{x^{i}D^{j}∈L}{j − i} − min_{x^{i}D^{j}∈L}{j − i}.  (10)

Let us define finite m-sparse objects as well. Let (d_{s}, d_{s+1}, …, d_{t}) be an ordered finite set of elements of a ring. Call this set m-sparse if there exists N such that

(d_{j} ≠ 0) ⇒ (j = N (mod m))

for j = s, s + 1, …, t. Call operators of the form (??) and (??) as well as the corresponding equations m-sparse if the sets

(p_{0}(x), …, p_{r}(x))

and

(q_{l}(n), …, q_{d}(n))

are m-sparse.

Let c = (c_{0}, c_{1}, …) ∈ C. Denote by (c, x) the formal series c_{0} + c_{1}x + … and by (c)_{≥k} the sequence (c_{k}, c_{k+1}, ...) ∈ C with c_{k} = c_{k+1} = ⋯ = c_{−1} = 0 if k < 0. It can be shown that if R = RL and R has the form (??) then

L(c, x) = 0 ⇔ R(c)_{≥l} = 0.  (11)

Let R be of the form (??) and r_{0} be the maximal nonnegative integer root of q_{d}(n) if such roots exist, and −1 otherwise. Set

ι^{∗}(R) = d + r_{0}.

If L ∈ C^{|}^{|} [D, x] and R = RL, then we set ι^{∗}(L) = ι^{∗}(R). For any (c_{0}, c_{1}, ...) ∈ C such that L(c, x) = 0 the values c_{0}, ..., c_{ι^{∗}(L)} let one compute (by means of RL) the values c_{ι^{∗}(L)+1}, c_{ι^{∗}(L)+2}, ... (these c_{ι^{∗}(L)+1}, c_{ι^{∗}(L)+2}, ... are uniquely determined because the leading coefficient of the recurrence RL does not vanish when we compute c_{n} with n > ι^{∗}(L)).

We can prove the following lemma on the possible values of m.

Lemma 1 Let L be of the form (??). Let R = RL and Ly = 0 have a non-polynomial solution f(x) = c_{0} + c_{1}x + ⋯ ∈ S^{(m)}. Then m ≤ ω(R).

Proof: If m > ω(R) then there is k > max{ω(R), ι^{∗}(R)} such that c_{k} = ⋯ = c_{k+m−1} = 0. But then c_{n} = 0 for all n ≥ k, i.e. f(x) ∈ C^{|}^{|} [x]. Contradiction. □

From now on we will deal only with non-polynomial solutions. Polynomial solutions can be found by the algorithm described in [?]. Furthermore we will suppose that L is of the form (??), R = RL is of the form (??) and m is a fixed integer such that

2 ≤ m ≤ ω(R).  (12)

First we discuss the existence in S^{(m)} solutions of Ly = 0 (i.e. L^{0}y = 0). In Section 3 we will consider the search for all a such that the equation L^{a}y = 0 has solutions in S^{(m)}.

Going back to R of the form (??), denote

q_{ij}(n) = \{ \begin{matrix}q_{j}(n) & if j = i + l (mod m) \\ 0 & otherwise, \end{matrix}

i = 0, …, m − 1; j = l, …, d and

R_{j} = q_{id}(n)E^{d} + q_{i,d−1}(n)E^{d−1} + … + q_{il}(n)E^{l},

i = 0, …, m − 1 (it is not guaranteed that q_{id}(n) and q_{il}(n) are nonzero polynomials). Call the set of operators

R_{0}, …, R_{m−1}

the m-splitting of the operator R. It is easy to see that R_{0} + … + R_{m−1} = R.

Lemma 2 Let R be of the form (??) and R_{0}, ..., R_{m−1} be the m-splitting of R. Let c ∈ C^{(m)}. Then

(R(c)_{≥l} = 0) ⇔ (R_{i}(c)_{≥l} = 0, i = 0, …, m − 1).  (13)

Proof: a direct check. □

The lemma lets one write down a necessary condition for the existence in S^{(m)} of solutions of Ly = 0.

Theorem 1 Let R_{0}, ..., R_{m−1} be the m-splitting of R. Let Ly = 0 have a solution in S^{(m)}. Then the right greatest common divisor (GCD) of the operators R_{0}, ..., R_{m−1} has the positive ω:

ω(GCD(R_{0}, ..., R_{m−1})) ≥ 1.  (14)

(We suppose as usual that R has the form (??) and that l is the lowest exponent of E in GCD(R_{0}, ..., R_{m−1}).)

Proof: Due to (??) and Lemma ??. □

The operator V = GCD(R_{0}, ..., R_{m−1}) can be found by the (right) Euclidean algorithm. If we apply the algorithm to m-sparse operators then we obviously obtain again an m-sparse operator. Hence, V is an m-sparse operator. Coefficients of V are in C^{|}^{|} (n). Let ω(V) ≥ 1. For some w(n) ∈ C^{|}^{|} [n] holds

w(n)R = Q ∘ W,

where Q, W ∈ C^{|}^{|} [n, E], W is m-sparse and ω(W) = ω(V) ≥ 1.

It is useful to define ι_{∗} which will work together with ι^{∗}. Let R be of the form (??). Let r_{1} be the maximal nonnegative integer root of q_{l}(n) if such roots exist, and −1 otherwise. Set

ι_{∗}(R) = max{l + r_{1}, −1}.

Let L ∈ C^{|}^{|} [D, x] and R = RL, then we set ι_{∗}(L) = ι_{∗}(R). For any (c_{0}, c_{1}, ...) such that L(c, x) = 0 the values c_{k}, c_{k+1}, ... with k > ι_{∗}(L) + 1 let one compute (by means of RL) the values c_{ι_{∗}(L)+1}, c_{ι_{∗}(L)+2}, ..., c_{k−1} (these c_{ι_{∗}(L)+1}, c_{ι_{∗}(L)+2}, ..., c_{k−1} are uniquely determined because the lowest coefficient of the recurrence RL does not vanish when we compute c_{n} with n > ι_{∗}(L)).

Set

u = max{ι_{∗}(W), ι_{∗}(w(n)R), ι^{∗}(W), ι^{∗}(w(n)R)},
v = u + ω(R) − 1.

Using an algorithm proposed in [?] we can find a basis for the space B of vectors (c_{0}, ..., c_{v}) ∈ C^{|}^{|} ^{v+1} such that an infinite sequence c = (c_{0}, c_{1}, ...) ∈ C satisfies the equality R(c)_{≥l} = 0 iff (c_{0}, ..., c_{v}) ∈ B and all elements c_{n} with n > v are calculated using the recurrence Rc = 0. After a basis d_{0}, ..., d_{w}, w ≤ v for B is found one can check (a linear problem) whether there exist α_{0}, ..., α_{w} ∈ C^{|}^{|} , such that α_{0}d_{0} + ... + α_{w}d_{w} is an m-sparse vector whose the last ω(R)−1 components satisfy recurrence W c = 0. If such α_{0}, ..., α_{w} exist then we can extend the corresponding initial values using the recurrence W c = 0. It will give us an infinite m-sparse sequence c which satisfies R(c)_{≥l} = 0.

Later we will need the following theorem

Theorem 2 Let L have the form (??) and R = RL have the form (??). Let R_{0}, ..., R_{m−1} be the m-splitting of R. Let L_{i} = R^{−1}R_{i}, i = 0, ..., m − 1. Let the equation Ly = 0 have a solution in S^{(m)}. Then

ord GCD(L_{0}, ..., L_{m−1}) ≥ 1.  (15)

Proof: Let f(x) = c_{0} + c_{1}x + ... ∈ S^{(m)}, Lf = 0. Then R(c)_{≥l} = 0 where c = (c_{0}, c_{1}, ...). By Lemma 3 we have R_{i}(c)_{≥l} = 0, i = 0, ..., m − 1. By (??) we get L_{i}f = 0, i = 0, ..., m − 1. □

Now the last remark of this Section. Suppose we know that for a fixed m the equation Ly = 0 has a solution in S^{(m)}. Then the next step could be, for example, the attempt to find an m-sparse series solution which is at the same time m-hypergeometric [?] (a power series is m-hypergeometric if its sequence of coefficients (c_{0}, c_{1}, ...) is m-hypergeometric, i.e. c_{n+m} = r(n)c_{n}, n = 0, 1, ..., for a rational function r(n)). Using an algorithm proposed in [?] we can find all m-hypergeometric solutions of the recurrence V c = 0 and then answer the question about m-hypergeometric m-sparse solutions of the original differential equation.

Note that the mentioned algorithm from [?] lets one find only primitive m-hyperge-ometric solution of a recurrence (an m-hypergeometric sequence (c_{k}, c_{k+1}, ...) is primitive if it satisfies no linear homogeneous recurrence with rational coefficients of order < m). But it is obvious that an m-sparse m-hypergeometric solution having c_{i} ≠ 0 with arbitrary large i is a primitive m-hypergeometric. Thus the algorithm from [?] is sufficient for our goal.

If we are interested only in m-hypergeometric m-sparse series solutions then there is no necessity to compute GCD(R_{0}, ..., R_{m−1}). We can find solutions in the form of m-hypergeometric elements of S and then select m-sparse ones from them. However the usage of (??),(??) is convenient when we solve the problem of searching for the points a at which there exist solutions of the form (??) with (c_{0}, c_{1}, ...) ∈ C^{(m)}. We will call these points the m-points.

3 The search for m-points

Let again Ly = 0 be an equation with operator of the form (??) and m be a non-negative integer such that (??) is satisfied. We formulate the problem of the search for m-points as follows: to find all complex values of a such that the equation L^{a}y = 0, with L^{a} of the form (??), has a solution in S^{(m)}. Consider the operator L^{a} and the equation L^{a}y = 0 regarding a as an indeterminated parameter. Call them the parametrized operator and equation. We can also construct R^{a} = RL^{a} and R_{i}^{a}, i = 0, ..., m − 1 (the m-splitting of R^{a}). Coefficients of the operators

R^{a}, R_{0}^{a}, ..., R_{m−1}^{a}  (16)

are polynomials in n over C^{|}^{|} [a]. We can construct the operators

L_{0}^{a} = R^{−1}R_{0}^{a}, ..., L_{m−1}^{a} = R^{−1}R_{m−1}^{a}.  (17)

If a_{0} is a value of the parameter a then we can consider, on the one hand, L^{a_{0}} and

R^{a_{0}}, R_{0}^{a_{0}}, ..., R_{m−1}^{a_{0}},  (18)

and, on the other hand, the specialization of the operators (??) for a = a_{0}:

R^{a=a_{0}}, R_{0}^{a=a_{0}}, ..., R_{m−1}^{a=a_{0}}  (19)

as the result of the substitution a_{0} in (??) for a. It will be shown below that operators (??) and (??) are equal. This equivalence leads to constructing a set including all m-points. We can gather together all a_{0} such that

ord GCD(R_{0}^{a_{0}}, ..., R_{m−1}^{a_{0}}) ≥ 1.  (20)

Following similar ideas we can gather all a_{0} such that

ord GCD(L_{0}^{a_{0}}, ..., L_{m−1}^{a_{0}}) ≥ 1,  (21)

where L_{i}^{a_{0}} = R^{−1}R_{i}^{a_{0}}, i = 0, ..., m − 1. Observe that (??), (??) are particular versions of (??),(??) with a_{0} = 0.

It will be conveniently to consider (??). Before proceeding further, we investigate the structure of the operators L_{0}^{a}, ..., L_{m−1}^{a}. We consider initialy a specific property of the operators such that it is possible to give very similar proofs for the case L, L_{0}, ..., L_{m−1} and for the case L^{a}, L_{0}^{a}, ..., L_{m−1}^{a}. We consider the first case for simplicity. Recall that L has the form (??), R = RL has the form (??).

We denote by p_{ji} the coefficient of x^{i} in the polynomial p_{j}(x).

Theorem 3 Let R_{0}, ..., R_{m−1} be the m-splitting of R and L_{t} = R^{−1}R_{t}, t = 0, ..., m − 1. Then

L_{t} = ∑_{{x^{i}D^{j} ∈L \atop j−i−l=t (mod m)}} p_{ji}x^{i}D^{j},  (22)

t = 0, ..., m − 1.

Proof: Let x^{i}D^{j} ∈ L then R(p_{ji}x^{i}D^{j}) gives a contribution only to one of operators R_{0}, ..., R_{m−1}, say to R_{t},

j − i − l = t (mod m).  (23)

Since L_{t} = R^{−1}R_{t}, all p_{ji}x^{i}D^{j}, x^{i}D^{j} ∈ L, are distributed among L_{0}, ..., L_{m−1} without any transformation (as among boxes). By (??) formula (??) is satisfied. □

Remark that in the analogous proof of this Theorem for L^{a}, L_{0}^{a}, ..., L_{m−1}^{a} the corresponding p_{ji} would be polynomial in a.

Theorem 4 Let R^{a} = RL^{a}. Let as usual L and R have the form (??) and, resp., (??). Let R^{a} be

g_{d′}(n, a)E^{d′} + ⋯ + g_{l′}(n, a)E^{l′}.  (24)

Then

r = d′ ≥ d, l′ = l, deg_{a} g_{l′}(n, a) = 0,  (25)

i.e. (??) can be written as

g_{r}(n, a)E^{r} + +g_{l+1}(n, a)E^{l+1} + g_{l}(n)E^{l}.  (26)

For any value a_{0} of the parameter a we have

RL^{a_{0}} = g_{r}(n, a_{0})E^{r} + ⋯ + g_{l+1}(n, a_{0})E^{l+1} + g_{l}(n)E^{l}.  (27)

Proof: We prove r = d′ using (??) and x^{0}D^{r} ∈ L^{a}. If x^{0}D^{r} ∈ L then r = d else r > d. The equality deg_{a} g_{l′}(n, a) = 0 (i.e. deg_{a} g_{l}(n, a) = 0) is a consequence of deg_{a} lc_{x} p_{j}(x + a) = 0. The equality l = l′ is obvious. Finaly, (??) is a consequence of the fact that R is a ring-homomorphism. □

Corollary (on the specialization). Operators (??) and (??) are identical.

Now we investigate GCD(L_{0}^{a}, …, L_{m−1}^{a}).

Theorem 5 As usual let L have the form (??) and for some k, 0 ≤ k ≤ r, deg p_{k}(x) be a positive integer s. Let v, 0 ≤ v ≤ m − 1, be such that x^{s}D^{k} ∈ L_{v}. Then

(i) x^{s}D^{k} ∈ L_{v}^{a}, (ii) there exists L_{w}^{a}, w ≠ v, such that x^{s−1}D^{k} ∈ L_{w}^{a}.

Proof: Let p_{k}(x) = p_{ks}x^{s} + p_{k,s−1}x^{s−1} + ⋯ + p_{k0}, s > 0, p_{k,s} ≠ 0. Then p_{k}(x + a) = p_{ks}x^{s} + (p_{ks}sa + p_{k,s−1})x^{s−1} + ⋯ and (i) is obvious. The polynomial in a

p_{ks}sa + p_{k,s−1}

is nonzero. Together with

k − s ≠ k − s + 1 (mod m)

is gives (ii). □

Call a differential operator L of the form (??) primitive if

gcd(p_{0}(x), ..., p_{r}(x)) = 1,  (28)

where gcd denotes the polynomial greatest common divisor. It easy to see that L^{a} and L^{a_{0}} are primitive iff L is primitive.

Theorem 6 Let L be a primitive operator of the form (??). Let there exist at least one polynomial of the degree ≥ 1 among p_{0}(x), ..., p_{r}(x). Then

ord GCD(L_{0}^{a}, ..., L_{m−1}^{a}) < r

(we mean GCD of the operators over C^{|}^{|} (a)(x)).

Proof: Since

L^{a} = L_{0}^{a} + ⋯ L_{m−1}^{a}.  (29)

we have

ord GCD(L_{0}^{a}, ..., L_{m−1}^{a}) = ord GCD(L_{0}^{a}, ..., L_{m−1}^{a}, L^{a}) ≤ ord GCD(L_{w}^{a}, L^{a}),

where L_{w}^{a} is the operator described in Theorem 5. Thanks to a) ord L_{w}^{a} ≤ ord L^{a},

b) L^{a} is primitive,

c) there exist s, k such that x^{s}D^{k} ∈ L^{a} and xs̃D^{k} ∉ L_{w}^{a} for any s̃, we obtain ord GCD(L_{w}^{a}, L^{a}) < ord L^{a}. □

Lemma 3 Let L and R have the form (??), (??) and R = RL. Let R be an m-sparse and 0 be a non-singular point of L (i.e. p_{r}(0) ≠ 0). Then the equation Ly = 0 has r = ord L linearly independent solutions in S^{(m)}.

Proof: At a non-singular point, any r initial coefficients c_{0}, …, c_{r−1} determine a series which satisfies the equation L(y) = 0. Obviously, it is possible to construct such a basis for the space of vectors (c_{0}, …, c_{r−1}) ∈ C^{|}^{|} ^{r} which contains only m-sparse vectors: we can take c_{i} = δ_{ij} in the j-th element of the basis, j = 0, ..., r − 1. Let us extend every element of the basis by elements c_{−1} = 0, …, c_{l} = 0. All the extended vectors are m-sparse. Applying m-sparse recurrence to an m-sparse vector of initial elements, we obtain an infinite m-sparse sequence. □

Lemma 4 Let Ly = 0 be a differential equation with constant coefficients. Then either L = L_{1} ∘ L_{2} where L_{1}, L_{2}, have constant coefficients and L_{2} is m-sparse (in such a case all points are m-points), or there are no m-points at all.

Proof: It is obvious that if L is an operator with constant coefficients then either every point is an m-point, or there is no m-point. It is enough to investigate the point 0. It is easy to see that L_{0}, ..., L_{m−1} are m-sparse operators with constant coefficients. The operator S = GCD(L_{0}, ..., L_{m−1}) is either a constant or an m-sparse operator with constant coefficients, ord S ≥ 1 (due to the Euclidean algorithm). In the last case the difference operator RS is m-sparse. By Lemma ?? the point 0 will be an m-point of Ly = 0. □

Using the (right) Euclidean algorithm and, for instance, the differential resultant and subresultants [?] we can construct a differential operator S_{m}(L) over C^{|}^{|} [a, x] and a finite set T_{m}(L) ⊂ C^{|}^{|} (the set of distinctive values of the parameter a) such that the substitution of any a_{0} ∉ T_{m}(L) into S_{m}(L) for a gives the operator S^{a_{0}} = GCD(L_{0}^{a_{0}}, ..., L_{m−1}^{a_{0}}) with ord S^{a_{0}} = ord S_{m}(L). If a_{0} ∈ T_{m}(L) then either S^{a_{0}} ≠ GCD(L_{0}^{a_{0}}, ..., L_{m−1}^{a_{0}}) or the leading coefficient of S_{m}(L) vanichs if a = a_{0}. If L is irreducible then ord S_{m}(L) = 0 due to (??).

Theorem 7 Let L be a primitive differential operator. Then either the equation Ly = 0 has only finite set of m-points or L = L_{1} ∘ L_{2} where L_{2} is an m-sparse operator with constant coefficients.

Proof: Let

S = S_{m}(L), T = T_{m}(L).

If there exists only a finite set of a_{0} which satisfy (??) (i.e. ord S = 0) then there is nothing to prove. Due to Theorem ?? ord S = r iff L is an m-sparse operator with constant coefficients. In such a case the theorem is true. Let

1 ≤ ord S < r.  (30)

Use induction on r.

1. r = 1. The statement is true because (??) is not possible.

2. r > 1. Since L^{a} = L_{0}^{a}+...+L_{m−1}^{a} then L^{a} = U∘S, where U is a differential operator with coefficients in C^{|}^{|} (x, a). If a_{0} ∉ T then by Corollary on the specialization we have that GCD(L_{0}^{a_{0}}, ..., L_{m−1}^{a_{0}}) is equal to the operator S^{a_{0}} which is the result of the substitution of a_{0} in S for a. It means that if the equation L^{a_{0}}y = 0 has a solution in S^{(m)} then the equation S^{a_{0}}y = 0 will have the same solution. We can divide the equation by the polynomial h(x) which is equal to gcd of the coefficients of the equation. We obtain the equation S′y = 0, where S′ is a primitive operator with polynomial coefficients such that ord S′ < r. By the inductive hypothesis the statement of the theorem is true for this last equation. If the equation has a finite set of m-points {α_{0}, β_{0}, ..., γ_{0}} then due to L^{a} is equal to (??), all m-points of the original equation are in

T ∪ {α_{0} − a_{0}, β_{0} − a_{0}, ..., γ_{0} − a_{0}}.  (31)

In the case when S′ has a right m-sparse factor C with constant coefficients (i.e. S′ = S′′ ∘ C) the original operator L has the same factor. Indeed, denote by U^{a_{0}} the result of the substitution of a_{0} into U for a. Then

L^{a_{0}} = U^{a_{0}} ∘ h ∘ S′ = U^{a_{0}} ∘ h ∘ S′′ ∘ C,

and L^{a_{0}} = V ∘ C, where V is an operator with polynomial coefficients. Let the substitution of x − a_{0} for x into V gives V′. Then L = V′ ∘ C.

□

This last Theorem provides us with an algorithm to find all m-points of the given equation. The process which was described recursively in the last Theorem gives either an m-sparse operator C with constant coefficients (then all points are m-points) or a finite set of candidates (each of them can be investigated by the approach described in Section 2). Note that in the first case it is possible to obtain, together with C, a finite set of distinctive values collected on all the levels of the recursive process (shifted like we demonstrated in (??). If the set is not empty then its elements are of special interest because the number of m-sparse linearly independent solutions can increase at those points.

Algorithm Input: a differential operator L; Output: a finite set of points M and an m-sparse operator C with constant coeffi-

cients; 1. If ord L = 0 then return

theemptyset, L;

2. S = S_{m}(L), T = T_{m}(L);

3. If ord S = ord L then return

T, L;

4. Pick up a point a_{0} ∉ T; construct S′ which is the result of dividing S^{a_{0}} by the greatest common divisor of its coefficients; 5. Apply the algorithm recursvely to S′, let

{α, β, ..., γ}, C

be the result of the recursive call;

6. Return

T ∪ {α_{0} − a_{0}, β_{0} − a_{0}, ..., γ_{0} − a_{0}}, C
□

After this algorithm was applied we get a finite set of point M and an m-sparse linear differential operator C with constant coefficinets (it is possible that ord C = 0, i.e. C = 1). All the point belonging to M must be investigated by the approach described in Section 2.

An irreducible operator L can not have a right factor S with (??) and due to Theorems ??, ?? we deduce the following Theorem.

Theorem 8 Let L be a primitive irreducible operator of the form (??), and there is i, 0 ≤ i ≤ r, such that deg p_{i}(x) > 0. Let p_{s_{1}}(x), ..., p_{s_{k}}(x) be all nonzero coefficients of L and let t_{1}, ..., t_{k} be their degrees. Let t = deg p_{r}(x) and u_{ji}(a) be the coefficient of x^{i}D^{j} in L^{a}. Then we have the following necessary conditions.

1. If there exists an m-point of Ly = 0 then s_{1} − t_{1} = ... = s_{k} − t_{k} (mod m).

2. If 0 is an m-point of Ly = 0 then

∀_{i,j}((x^{i}D^{j} ∈ L) ⇒ (j − i = r − t (mod m))).

3. If a_{0} is an m-point of Ly = 0 then

∀_{i,j}((x^{i}D^{j} ∈ L^{a}, j − i ≠ r − t (mod m)) ⇒ (u_{ji}(a_{0}) = 0)).

If 0 or a_{0} are non-singular points of the equation Ly = 0 then the two last conditions are also sufficient conditions.

Proof: Since L is irreducible, it can not have a factor S such that (??) holds. Therefore if a_{0} is an m-point then GCD(L_{0}^{a_{0}}, ..., L_{m−1}^{a_{0}}) = L^{a_{0}}. In the case of a primitive L it is possible only if one of L_{0}^{a_{0}}, ..., L_{m−1}^{a_{0}} is equal to L^{a_{0}} and all others are equal to zero. Then RL^{a_{0}} is m-sparse. This prove the necessity of condition 2, 3. In turn to prove the necessity of condition 1 we have additionaly to take into account that the leading coefficients of all polynomial coefficient of L^{a_{0}} do not depend on the value of a_{0}. The suffciency of conditions 2, 3 in the case of ordinary point a_{0} follows from Lemma ??. □

Example 2. y′′ + (x − 1)y = 0. We have 2 ≤ m ≤ 3. The operator L = D^{2} + (x − 1) is irreducible over C^{|}^{|} (x); L^{a} = D^{2} + (x − a − 1).

m = 2. The first of the necessary conditions formulated in Theorem 8 is not satisfied: 2 − 0 ≠ 0 − 1 (mod 2). The equation has no 2-points.

m = 3. the first the necessary conditions formulated in Theorem 8 is satisfied: 2 − 0 = 0 − 1 (mod 3); 0 is not an m-point because 2 − 0 ≠ 0 − 0 (mod 3). By the third condition a_{0} = 1. This is a non-singular point, hence it is a 3-point.

By Lemma (??) the given equation has two linearly independent 3-sparse solutions. In this case they can be taken as 3-hypergeometric:

1 + ∑_{n=1}^{∞} \frac{(−1)^{n}(x − 1)^{3n}}{2 · 3 · 5 · 6 … (3n − 1) · 3n},

(x − 1) + ∑_{n=1}^{∞} \frac{(−1)^{n}(x − 1)^{3n+1}}{3 · 4 · 6 · 7 … 3n · (3n + 1)}.

References

[1] S. Abramov, M. Bronstein, M. Petkovšek (1995): On Polynomial Solutions of Linear Operator Equations. Proc. ISSAC’95, 290-296.

[2] S. Abramov, M. Petkovšek (1996): Special Power Series Solutions of Linear Differential Equation. Proc. FPSAC’96, 1-10.

[3] S. Abramov, M. Petkovšek, A. Ryabenko (1996): Special Formal Series Solutions of Linear Operator Equations. Submitted to Discret Math.

[4] M. Chardin (1991): Differential Resultants and Subresultants. Lecture notes in computer science, 529.

[5] M. Petkovšek, B. Salvy (1993): Finding All Hypergeometric Solutions of Linear Differential Equations. Proc. ISSAC’93, 27-33.