A Quadrat
email: alban.quadrat@inria.fr.

G Regensburger
email: georg.regensburger@jku.at

Computing Polynomial Solutions and Annihilators of Integro-Differential Operators with Polynomial Coefficients

Keywords: Linear systems theory, rings of integro-differential operators, polynomial solutions, indicial equation, compatibility conditions, computer algebra Théorie des systèmes linéaires, anneaux d'opérateurs intégro-différentiels, solutions polynomiales, équation indicielle, conditions de compatibilité, calcul formel

In this paper, we study algorithmic aspects of the algebra of linear ordinary integro-differential operators with polynomial coefficients. Even though this algebra is not Noetherian and has zero divisors, Bavula recently proved that it is coherent, which allows one to develop an algebraic systems theory over this algebra. For an algorithmic approach to linear systems of integro-differential equations with boundary conditions, computing the kernel of matrices with entries in this algebra is a fundamental task. As a first step, we have to find annihilators of integro-differential operators, which, in turn, is related to the computation of polynomial solutions of such operators. For a class of linear operators including integro-differential operators, we present an algorithmic approach for computing polynomial solutions and the index. A generating set for right annihilators can be constructed in terms of such polynomial solutions. For initial value problems, an involution of the algebra of integro-differential operators then allows us to compute left annihilators, which can be interpreted as compatibility conditions of integro-differential equations with boundary conditions. We illustrate our approach using an implementation in the computer algebra system Maple.

Introduction

Rings of functional operators (e.g., rings of ordinary differential (OD) operators, partial differential (PD) operators, differential time-delay operators, differential difference operators) were recently introduced in mathematical systems theory. Since many control linear systems can be defined by means of a matrix with entries in a skew polynomial ring, in an Ore algebra or in an Ore extension of functional operators (i.e., classes of univariate or multivariate noncommutative polynomial rings) [START_REF] Chyzak | Effective algorithms for parametrizing linear control systems over Ore algebras[END_REF][START_REF] Quadrat | Algebraic analysis for the Ore extension ring of differential time-varying delay operators[END_REF], the classical polynomial approach to linear systems theory can be generalized yielding a module-theoretic approach to linear functional systems [START_REF] Fliess | Some basic structural properties of generalized linear systems[END_REF][START_REF] Oberst | Multidimensional constant linear systems[END_REF][START_REF] Pommaret | A functorial approach to the behaviour of multidimensional control systems[END_REF][START_REF] Robertz | Recent progress in an algebraic analysis approach to linear systems[END_REF][START_REF] Seiler | Algebraic theory of linear systems: a survey[END_REF][START_REF] Wood | Modules and behaviours in nD systems theory[END_REF]. Symbolic computation techniques (e.g., Gröbner basis techniques) and computer algebra systems can then be used to develop dedicated packages for algebraic systems theory [START_REF] Chyzak | OreModules: A symbolic package for the study of multidimensional linear systems[END_REF][START_REF] Levandovskyy | Algebraic systems theory and computer algebraic methods for some classes of linear control systems[END_REF].

Algebras of ordinary integro-differential (ID) operators have recently been studied within an algebraic approach in [START_REF] Bavula | The algebra of integro-differential operators on a polynomial algebra[END_REF][START_REF] Bavula | An analogue of the conjecture of Dixmier is true for the algebra of polynomial integrodifferential operators[END_REF][START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF][START_REF] Bavula | The algebra of polynomial integro-differential operators is a holonomic bimodule over the subalgebra of polynomial differential operators[END_REF] and within an algorithmic approach in [START_REF] Regensburger | A skew polynomial approach to integro-differential operators[END_REF][START_REF] Rosenkranz | Solving and factoring boundary problems for linear ordinary differential equations in differential algebras[END_REF][START_REF] Rosenkranz | Symbolic analysis for boundary problems: From rewriting to parametrized Gröbner bases[END_REF][START_REF] Hossein Poor | Algorithmic operator algebras via normal forms for tensors[END_REF]. The goal of the latter works is to provide an algebraic and algorithmic framework for studying boundary value problems and Green's operators.

The ring of ID and time-delay/dilatation operators was introduced in [START_REF] Quadrat | A constructive algebraic analysis approach to Artstein's reduction of linear time-delay systems[END_REF] to develop a purely algorithmic approach to standard Artstein's transformation of linear differential systems with delayed inputs. This work also advocates for the effective study of the ring of ID time-delay/dilatation operators. The normal forms of elements of this noncommutative algebra will be studied in a future publication based on the new effective techniques introduced in [START_REF] Hossein Poor | Algorithmic operator algebras via normal forms for tensors[END_REF][START_REF] Hossein Poor | Normal forms for operators via Gröbner bases in tensor algebras[END_REF]. In this paper, we focus on its subring of ID operators. We also note that effective computations over ID algebras play an important role in parameter estimation problems as shown in [START_REF] Boulier | On symbolic approaches to integrodifferential equations[END_REF].

Even though linear systems of ID equations play an important role in different domains and applications (e.g., PID controllers), it does not seem that they have been extensively studied by the mathematical systems community. For boundary value systems, we refer to [START_REF] Gohberg | Time varying linear systems with boundary conditions and integral operators. I. The transfer operator and its properties[END_REF][START_REF] Gohberg | Minimality and irreducibility of time-invariant linear boundary value systems[END_REF] and the references therein. The first purpose of this paper is to introduce concepts, techniques, and results developed in the above recents works. In particular, we emphasize that the algebraic structure of the ring of ID operators with polynomial coefficients is much more involved (e.g., zero divisors, non-Noetherianity) than the one of the ring of OD operators with polynomial coefficients (the so-called Weyl algebra). The fundamental issue of computing left/right kernel of a matrix of ID operators has to be solved towards developing a system-theoretic approach to linear ID systems. For more details, see [START_REF] Chyzak | Effective algorithms for parametrizing linear control systems over Ore algebras[END_REF][START_REF] Quadrat | An introduction to constructive algebraic analysis and its applications[END_REF].

The second goal of this paper is to study this problem for a single ID operator, that is, computing its annihilator. Within a representation approach, we show that this problem is related to the computation of polynomial solutions of ID operators, a problem that is also studied in detail. To solve this problem, we introduce the concept of a rational indicial equation for a linear operator acting on the polynomial ring. This approach allows us to find again and generalize standard results on the indicial equation classically used in the theory of linear OD equations [START_REF] Abramov | On polynomial solutions of linear operator equations[END_REF][START_REF] Abramov | Fast algorithms to search for the rational solutions of linear differential equations with polynomial coefficients[END_REF][START_REF] Barkatou | On rational solutions of systems of linear differential equations[END_REF].

This chapter is based on the conference paper [START_REF] Quadrat | Polynomial solutions and annihilators of ordinary integro-differential operators[END_REF]. It includes a self-contained introduction to ordinary integrodifferential operators with polynomial coefficients with several evaluations including normal forms (Sections 2-4). All other sections have been revised and extended.

The ring of Ordinary Integro-Differential Operators with Polynomial Coefficients

Before discussing the ring of ID operators with polynomial coefficients, as an introducing example, we first recall two standard constructions of the ring A of OD operators with polynomial coefficients (also called the Weyl algebra and denoted by A 1 (k), where k is a field). The first construction is as the subalgebra k t, ∂ of all linear maps on the polynomial ring k[t] and the second is by means of generators and relations.

In what follows, let k denote a fixed field, which contains Q. Let end k (k[t]) denote the k-algebra formed by all k-linear maps from the polynomial ring k[t] to itself. We consider the k-subalgebra k t, ∂ of end k (k[t]) generated by the following two k-linear maps t : t n -→ t n+1 and ∂ : t n -→ nt n-1 defined on the basis (t n ) n∈N of k[t]. They respectively correspond to the multiplication operator and the derivation on the polynomial ring k[t], namely:

t : k[t] -→ k[t] p -→ t p, and
∂ : k[t] -→ k[t] p -→ d p dt . (1)
One immediately verifies that we have

∀ p ∈ k[t], (∂ • t)(p) = d(t p) dt = t d p dt + p = (t • ∂ + id)(p),
where id (also denoted by 1) is the identity map on k[t]. It shows that the Leibniz rule

∂ • t = t • ∂ + id
holds in the operator algebra k t, ∂ . Using the Leibniz rule, we can define the Weyl algebra also by generators and relations: Let k T, D be the free associative k-algebra on the set {T, D}, that is, the k-vector space with the basis formed by all words over {T, D} and the multiplication of basis elements defined by concatenation. Let now

J = (D T -T D -1) ⊆ k T,
d ≡ ∑ a i j T i D j mod J
with coefficients a i j ∈ k.

To see that the two constructions above are equivalent, one can use the fact that A is a simple ring, that is, its only proper two-sided ideal is the zero ideal (see for example, [START_REF] Coutinho | A primer of algebraic D-modules[END_REF]). Hence every ring homomorphism is injective and so the k-algebra homomorphism A -→ k t, ∂ mapping T + J -→ t and D + J -→ ∂ is an isomorphism. In other words, each d ∈ A can be identified with the following corresponding k-linear map

L d : k[t] -→ k[t], p -→ d(p),
where d(p) denotes the action of d on p.

In the following, we use a similar approach to introduce and study the algebra of ID operators with polynomial coefficients. ID operators with polynomial coefficients were studied in [START_REF] Bavula | The algebra of integro-differential operators on a polynomial algebra[END_REF][START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF] as a generalized Weyl algebra [START_REF] Bavula | Generalized Weyl algebras and their representations[END_REF][START_REF] Bavula | Finite-dimensionality of Ext n and Tor n of simple modules over a class of algebras[END_REF]. See [START_REF] Regensburger | A skew polynomial approach to integro-differential operators[END_REF] for the construction of ordinary ID operators with polynomial coefficients as a factor algebra of a skew polynomial ring (see, e.g., [START_REF] Chyzak | Effective algorithms for parametrizing linear control systems over Ore algebras[END_REF][START_REF] Mcconnell | Noncommutative Noetherian rings[END_REF] and the references therein). For the construction of the algebra of ID operators F Φ ∂ , defined over an ordinary ID algebra F and endowed with a set of characters (that is, multiplicative linear functionals) Φ, we refer to [START_REF] Rosenkranz | Solving and factoring boundary problems for linear ordinary differential equations in differential algebras[END_REF][START_REF] Rosenkranz | Symbolic analysis for boundary problems: From rewriting to parametrized Gröbner bases[END_REF]. This construction is based on a parametrized noncommutative Gröbner basis; see Section 3 for the case of polynomial coefficients. For a basis-free construction using a finite reduction system in tensor algebras, we refer to [START_REF] Hossein Poor | Algorithmic operator algebras via normal forms for tensors[END_REF]. In contrast to [START_REF] Bavula | The algebra of integro-differential operators on a polynomial algebra[END_REF][START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF], the last two approaches allows one to have more than one point evaluation as described in Section 4, which is crucial for the study of boundary problems. Definition 1. The k-algebra of ordinary ID operators with polynomial coefficients is defined as the k-subalgebra

k t, ∂ , ⊆ end k (k[t]),
with the operators t and ∂ defined as in [START_REF] Abramov | On solutions of linear functional systems[END_REF] and

: k[t] -→ k[t] t n -→ t n+1 /(n + 1), defined on the basis (t n ) n∈N of k[t].

Inria

The integral operator corresponds to the usual integral starting at 0:

: k[t] -→ k[t] p -→ t 0 p(s) ds.
One can verify directly that the fundamental theorem of calculus

∂ • = id
holds. Moreover, we see that E = id -• ∂ corresponds to the evaluation at 0:

E : k[t] -→ k[t] p -→ p(0).
Hence, as soon as we have an integral, we also have one evaluation map to the constants k "for free", which allows us to define and study initial value problems in terms of integro-differential operators. Note that the operator E naturally induces the existence of zero divisors. For instance, we have:

E • t = 0.
Based on the basic identities above, we can construct the algebra of integro-differential operators with polynomial coefficients also by generators and relations. Definition 2. We define the k-algebra

I = k T, D, I, E /J,
where J is the two-sided ideal of relations generated by the following elements:

D T -T D -1, D I -1, I D + E -1, E T. (2)
We note by T = T + J (resp., D = D + J, I = I + J, E = E + J) the residue class of T (resp., D, I, E) in I.

Normal Forms

Since we have now four defining identities for I (see ( 2)) instead of one as for the Weyl algebra A, it is more involved to obtain the normal form of an element of I, i.e., its unique expression as a noncommutative polynomial in the operators T, D, I and E modulo the relations [START_REF] Abramov | On polynomial solutions of linear operator equations[END_REF]. In this section, we informally discuss the construction of a noncommutative Gröbner basis for the defining ideal following Buchberger's algorithm. For background on noncommutative Gröbner bases, we refer to [START_REF] Bergman | The diamond lemma for ring theory[END_REF][START_REF] Mora | An introduction to commutative and noncommutative Gröbner bases[END_REF][START_REF] Ufnarovski | Introduction to noncommutative Gröbner bases theory[END_REF][START_REF] Bokut | Gröbner-Shirshov bases and their calculation[END_REF]. In the noncommutative case, note that Buchberger's algorithm does not terminate in general and the property of having a finite Gröbner basis is undecidable. However, in our case we can "guess" a parametrized Gröbner basis from the corresponding S-polynomial computations.

See [START_REF] Rosenkranz | Solving and factoring boundary problems for linear ordinary differential equations in differential algebras[END_REF][START_REF] Rosenkranz | Symbolic analysis for boundary problems: From rewriting to parametrized Gröbner bases[END_REF] for further details on a parametrized Gröbner basis for the defining relations for integro-differential operators over an ordinary ID algebra and the corresponding normal forms. An analogous finite tensor reduction system and the related S-polynomial computations using the package TenRes can be found in [START_REF] Hossein Poor | Algorithmic operator algebras via normal forms for tensors[END_REF][START_REF] Hossein Poor | Normal forms for operators via Gröbner bases in tensor algebras[END_REF].

We denote the S-polynomial between two polynomials of the form U V -P and V W -Q, with "leading terms" U V and V W by: S(U V,V W ) = PW -U Q.

In the following, we consider a graded partial order with D > T and I > T . We first compute the S-polynomial between the polynomials D I -1 and I D + E -1 and obtain:

S(D I, I D) = 1 D -D (1 -E) = D E.
So we need to add the polynomial D E

to the generators of our ideal, which corresponds to the evaluation mapping to k. The S-polynomial between I D + E -1 and the new polynomial gives:

S(I D, D E) = (1 -E) E.
So we obtain E 2 -E, which corresponds to the evaluation acting as a projector onto k. Since

S(I D, D I) = (1 -E) I -I 1 = -E I,
we also have to add the polynomial E I to our generators, which corresponds to the integral t 0 evaluated at 0 being 0. The S-polynomial between

I D -1 + E and D T -T D -1
is given by:

S(I D, D T ) = (1 -E) T -I (T D + 1) = T -E T -I T D -I.
Using the polynomial E T from the original generators, we see that we need to add the polynomial: Collecting all the identities above, one can verify that all parametrized S-polynomials now reduce to zero and we have indeed a Gröbner basis for the defining identities (compare with [START_REF] Rosenkranz | Solving and factoring boundary problems for linear ordinary differential equations in differential algebras[END_REF]Proposition 13] and [START_REF] Hossein Poor | Algorithmic operator algebras via normal forms for tensors[END_REF]Theorem 5

I T D -T + I.
.1]). Inria Theorem 1. The generators D T -T D -1, D I -1, I D + E -1, E T, D E, E 2 -E, E I, IE -T E, I 2 -T I + I T,
and the parametrized generators

∀ n ≥ 1,      I T n D -T n + n I T n-1 , I T n E -T n+1 /(n + 1) E, I T n I -(T n+1 I + I T n+1 )/(n + 1),
form a noncommutative Gröbner basis for the ideal J of I (see Definition 2) with respect to a graded partial order with D > T and I > T .

By the normal form corresponding to the Gröbner basis from Theorem 1, using the notations of Definition 2, each d ∈ I can uniquely be written as a sum

d = d 1 + d 2 + d 3 ,
where

d 1 = ∑ a i j T i D j , d 2 = ∑ b i j T i I T j , d 3 = ∑ f i j T i E D j (3)
are respectively an OD operator, an integral operator, and a boundary operator, with a i j , b i j , and f i j ∈ k, and d 1 , d 2 , and d 3 contain only finitely nonzero summands.

To see that the definition of integro-differential operators via generators and relations and Definition 1 are equivalent, we can use the fact that I is "almost" a simple ring. The only nonzero proper two-sided ideal is the ideal (E) generated by the "evaluation" E. This was first proved by Bavula in [START_REF] Bavula | The algebra of integro-differential operators on a polynomial algebra[END_REF]. Here we give an alternative proof based on the normal forms and direct sum decomposition above, which also generalizes to the more general setting including several evaluations mentioned in the next section.

D T = T D + 1, D I = 1, D E = 0, we can find a k ∈ N such that D k d ∈ A \ {0}
is a nonzero differential operator and the statement follows since A is a simple ring.

Corollary 1. The k-algebra homomorphism χ :

I -→ k t, ∂ , mapping T -→ t, D -→ ∂ , E -→ E, I -→ is an isomorphism.
In other words, we can identify each d ∈ I with the corresponding k-linear map

L d : k[t] -→ k[t], p -→ d(p), (4)
where d(p) denotes the action of d on p. Finally, using (3), up to isomorphism, we have the following direct sum decomposition

I = A ⊕ k[t] k[t] ⊕ (E)
with the two-sided ideal (E) of boundary operators generated by E.

RR n°9002 4 Several Evaluations

For treating boundary problems, we allow additional point evaluations (characters, i.e., multiplicative linear forms) in our operator algebra. We denote the evaluation at α ∈ k by

E α : k[t] -→ k[t] p -→ p(α).
The basic identities for evaluations at α, β ∈ k and the derivation ∂ are

E α • t = α E α , E β • E α = E α , ∂ • E α = 0. Definition 3. Let Φ be a subset of k with 0 ∈ Φ. Identifying E 0 with E = id -• ∂ , we define the k-subalgebra k t, ∂ , , (E α ) α∈Φ of end k (k[t]
) formed by the ordinary ID operators with polynomial coefficients with characters

(E α ) α∈Φ .
Clearly, if Φ = {0}, then k t, ∂ , , (E α ) α∈Φ = I. We now construct the algebra of integro-differential operators with a set of characters (E α ) α∈Φ by generators and relations. Definition 4. We define the k-algebra

I Φ = k T, D, I, (E α ) α∈Φ /J Φ ,
where J Φ is the two-sided ideal generated by:

D T -T D -1, D I -1, I D + E 0 -1, ∀ α, β ∈ Φ,      E α T -αE α , E β E α -E α , D E α . (5)
We note by

T = T + J Φ (resp., D = D + J Φ , I = I + J Φ , E α = E α + J Φ for α ∈ Φ) the residue class of T (resp., D, I, E α ) in I Φ .
For obtaining a Gröbner basis for the ideal of relations J Φ , to the defining relations (5) and the generators from Theorem 1, we have to add the following parametrized generators:

∀ n ≥ 0, α ∈ Φ, I T n E α -T n+1 /(n + 1) E α .
By the corresponding normal forms, every ID operator d ∈ I Φ can be uniquely written as a sum d = d 1 + d 2 + d 3 , with d 1 and d 2 as in (3) and a boundary operator of the form

d 3 = ∑ α∈Φ ∑ f i j T i E α D j + ∑ g i j T i E α I T j , (6)
where f i j and g i j ∈ k and d 3 contains only finitely nonzero summands. Based on the above decomposition, the proof of Proposition 1 can be generalized.

Proposition 2. The only nonzero proper two-sided ideal of I Φ is ({E α } α∈Φ ), simply denoted by (E). Moreover, we have (E) = (E 0 ).

The equality (E) = (E 0 ) comes from the fact that 0 ∈ Φ and, with the notation of ( 6), from the following identity:

d 3 = ∑ α∈Φ ∑ f i j T i E 0 E α D j + ∑ g i j T i E 0 E α I T j ∈ (E 0 ).
Corollary 2. The k-algebra homomorphism

χ : I Φ -→ k t, ∂ , , (E α ) α∈Φ mapping T -→ t, D -→ ∂ , E α -→ E α , for α ∈ Φ, I -→
is an isomorphism.

Inria

So we can identify again each d ∈ I Φ with the corresponding k-linear map L d on the polynomial ring k[t] as in [START_REF] Abramov | Special formal series solutions of linear operator equations[END_REF]. For the rest of the paper, we do this identification and write ∂ , , t, E α for both the linear operators on the polynomial ring k[t] and the corresponding residue classes in I Φ . So the normal form for an ID operators 3) and ( 6) reads as

d = d 1 + d 2 + d 3 ∈ I Φ from equations (
d 1 = ∑ a i j t i ∂ j , d 2 = ∑ b i j t i t j , (7)
and

d 3 = ∑ α∈Φ ∑ f i j t i E α ∂ j + ∑ g i j t i E α t j . (8)
Denoting by ({E α } α∈Φ ) the two-sided ideal of I Φ generated by the E α 's for α ∈ Φ, we then have

({E α } α∈Φ ) = (E),
where (E) denotes the two-sided ideal of I Φ generated by E, and, up to isomorphism, we have the following direct sum decomposition:

I Φ = A ⊕ k[t] k[t] ⊕ (E).
In particular, the normal form tells us that the corresponding linear maps on the polynomial ring are linearly independent. Since we will need it later, we state this explicitly for the linear functionals in the normal form of boundary operators [START_REF] Bavula | The algebra of integro-differential operators on a polynomial algebra[END_REF].

Lemma 1. The k-linear functionals E α ∂ i and E α t i on k[t] for i ∈ N and α ∈ k are k-linearly independent.

Syzygies and Annihilators

In this section, we discuss some important algebraic properties of the algebra I concerning finite generating sets of ideals. First, since the integral operator is a right but not a left inverse of the derivation ∂ , it is known that the algebra I is necessarily non-Noetherian [START_REF] Jacobson | Some remarks on one-sided inverses[END_REF].

More explicitly, if i = • • • denotes the product of i integral operators and 0 = 1, using Theorem 1, one verifies that the following operators

e i j = i E ∂ j : p ∈ k[t] -→ p ( j) (0) t i i! satisfy e i j e lm = i E ∂ j l E ∂ m = δ jl e im , (9)
where δ jl = 1 for j = l, and 0 otherwise; see also [START_REF] Jacobson | Some remarks on one-sided inverses[END_REF] or [START_REF] Lam | A first course in noncommutative rings[END_REF]Ex. 21.26]. In particular, I contains infinitely many orthogonal idempotents e ii for all i ∈ N, i.e., e ii e j j = δ i j for all i, j ∈ N. Let us introduce the following operator:

e k = e 00 + e 11 + • • • + e kk ∈ I.
We note that the operator e k acts on a polynomial p by

e k (p) = k ∑ i=0 p (i) (0) t i i! ,
which corresponds to the first k terms of the Taylor series of p at t = 0. Using (9), we obtain:

∀ 0 ≤ i ≤ k, e ii = e ii e k = e k e ii ,
which yields e i e j = e j e i = e min(i, j) . In particular, we have

e k-1 = e k e k-1 = k-1 ∑ i=0 d i e i e k-1 = k-1 ∑ i=0 d i e i = e k ,
which yields a contradiction since e k (t k ) = 1 and e k-1 (t k ) = 0, and shows that I e k-1 Ie k for all k ∈ N. Similarly, we have e k-1 I e k I. Hence the increasing sequence (I k = I e k ) k≥0 (resp., (I k = e k I) k≥0 ) of principal left (resp., right) ideals of I is not stationary, which proves I is not a left (resp., a right) Noetherian ring.

Even though I is non-Noetherian, Bavula proved the following fundamental result stating that I is a coherent ring.

Theorem 2 ( [START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF]). The ring I is coherent, i.e., for every r ≥ 1, and for all d 1 , . . . , d r ∈ I, the left (resp., right) I-module

S = (c 1 , . . . , c r ) ∈ I 1×r | r ∑ i=1 c i d i = 0 (resp., S = (c 1 , . . . , c r ) T ∈ I r×1 | ∑ r i=1 c i e i = 0
) is finitely generated as a left (resp., right) I-module.

Linear systems are usually described by means of finite matrices with entries in a certain ring of functional operators D. As explained in [START_REF] Quadrat | The fractional representation approach to synthesis problems: an algebraic analysis viewpoint. I. (Weakly) doubly coprime factorizations[END_REF], if D is a coherent ring, an algebraic systems theory can be developed as if D were a Noetherian ring. Hence, Theorem 2 shows that an algebraic systems theory can be developed over I. In particular, basic module-theoretic operations of finitely presented left/right I-modules, namely, left/right I-modules defined by matrices, are finitely presented, and thus, finitely generated. For more details, see, e.g., [START_REF] Lam | A first course in noncommutative rings[END_REF][START_REF] Rotman | An introduction to homological algebra[END_REF]. It is shown in [START_REF] Bavula | The algebra of polynomial integro-differential operators is a holonomic bimodule over the subalgebra of polynomial differential operators[END_REF] that Theorem 2 cannot be generalized for more than one differential operator, i.e., for the algebra I n of integro-partial differential operators with polynomial coefficients defined by the operators x i , ∂ i = ∂ ∂ x i and

x i for i = 1, . . . , n and n > 1.
Based on normal forms for generalized Weyl algebras, it is shown in [START_REF] Bavula | The algebra of integro-differential operators on a polynomial algebra[END_REF] that I admits the involution θ defined by

θ (∂ ) = , θ ( ) = ∂ , θ (t) = t ∂ 2 + ∂ = (t ∂ + 1) ∂ , (10)
i.e., θ is a k-linear anti-automorphism, namely, it satisfies:

∀ d, e ∈ I, θ (d e) = θ (e) θ (d), θ 2 (d) = d.
We note that ∂ = 1 and E = 1 -∂ yield:

θ (1) = θ ( ) θ (∂ ) = ∂ = 1, θ (E) = θ (1) -θ (∂ ) θ ( ) = 1 -∂ = E.
With the notations ( 7) and ( 8), we get:

                   θ (d 1 ) = ∑ a i j θ (∂ ) j θ (t) i = ∑ a i j j ((t ∂ + 1) ∂ ) i , θ (d 2 ) = ∑ b i j θ (t) j θ ( ) θ (t) i = ∑ b i j ((t ∂ + 1) ∂ ) j ∂ ((t ∂ + 1) ∂ ) i , θ (d 3 ) = ∑ α∈Φ ∑ f i j θ (∂ ) j θ (E) θ (t) i = ∑ α∈Φ ∑ f i j j E ((t ∂ + 1) ∂ ) i = ∑ α∈Φ ∑ f i j t j j! E ((t ∂ + 1) ∂ ) i .
In particular, we have θ

((E)) ⊆ (E) and θ (k[t] k[t]) ⊆ A.
Finally, we note that:

θ (t ∂ ) = (t ∂ + 1) ∂ = t ∂ .
As a consequence, many algebraic properties of left I-modules have a right analogue and conversely. Finally, in [START_REF] Bavula | The algebra of integro-differential operators on a polynomial algebra[END_REF][START_REF] Bavula | An analogue of the conjecture of Dixmier is true for the algebra of polynomial integrodifferential operators[END_REF][START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF], various algebraic properties of I and important results are proven amongst them a classification of simple modules, an analogue of Stafford's theorem, and of the first conjecture of Dixmier.

The computation of syzygies, namely, left/right kernel of a matrix with entries in I is a central task towards developing an algorithmic approach to linear systems of ID equations with boundary conditions based on module theory and homological algebra. See [START_REF] Chyzak | Effective algorithms for parametrizing linear control systems over Ore algebras[END_REF][START_REF] Levandovskyy | Algebraic systems theory and computer algebraic methods for some classes of linear control systems[END_REF][START_REF] Quadrat | An introduction to constructive algebraic analysis and its applications[END_REF] and references therein. However, the the proof of Theorem 2 given in [START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF] is non-constructive. As a first step for computing syzygies, we discuss in the following how to find left/right annihilators of elements in I. As we will see, this problem leads, in turn, to computing polynomial solutions of ordinary ID equations with boundary conditions, which we discuss in Section 7. Example 1. We first consider the following trivial example: t 0 y(s) ds = u(t). The compatibility condition u(0) = 0 corresponds to the left annihilator E of , i.e., E = 0 in I. As a nontrivial example, we consider the inhomogeneous ID equation:

t 2 ÿ(t) -2t ẏ(t) + (t + 2) y(t) -(3t/5 + 2) t 0 y(s) ds + 3/5 t 0 s y(s) ds = u(t). (11)
The left annihilator of the following ID operator

d = t 2 ∂ 2 -2t ∂ + (t + 2) -(3t/5 + 2) + 3/5 t ∈ I (12)
yields the compatibility conditions of [START_REF] Bavula | The algebra of polynomial integro-differential operators is a holonomic bimodule over the subalgebra of polynomial differential operators[END_REF]. The compatibility conditions of d will be given in Example 9.

The relation between annihilators and polynomial solutions of ordinary ID equations comes from the fact that we can identify an integro-differential operator d ∈ I with the corresponding linear map L d on the polynomial ring k[t]. Hence, we have the equivalences:

d e = 0 ⇔ L d e = L d • L e = 0 ⇔ im L e ⊆ ker L d . (13)
Suppose that we want to compute the right annihilator of d and assume that L d has a finite dimensional kernel.

Then the image of L e for an e ∈ ann I (d.) has to be finite dimensional and must be contained in ker L d . In other words, we have to compute the polynomial solutions of L d and then find generators for all ID operators e with im L e ⊆ ker L d . After discussing some general properties of Fredholm and finite-rank operators in the next section, we follow this strategy for ID operators including several evaluations in Section 8.

Fredholm and Finite-Rank Operators

Several properties of Fredholm operators can be studied in the purely algebraic setting of linear maps on infinitedimensional vector spaces. In [START_REF] Bavula | The algebra of polynomial integro-differential operators is a holonomic bimodule over the subalgebra of polynomial differential operators[END_REF], such properties are used to investigate I. It turns out that Fredholm operators are also very useful for an algorithmic approach to operator algebras. We review some algebraic properties of Fredholm operators in this section.

Definition 5. A k-linear map f : V -→ W between two k-vector spaces is called Fredholm if it has finite dimensional kernel and cokernel, where coker f = W / im f . The index of a Fredholm operator f is defined by:

ind k f = dim k (ker f ) -dim k (coker f ).
We have the long exact sequence of k-vector spaces ( [START_REF] Rotman | An introduction to homological algebra[END_REF])

0 -→ ker f i -→ V f -→ W p -→ coker f -→ 0,
i.e., i is injective, ker f = im i, ker p = im f , and p is surjective, where p(w) is the residue class of w ∈ W in coker f . Then, dim k (coker f ) gives the number of independent k-linear compatibility conditions g(w) = 0 on w for the solvability of the inhomogeneous linear system f (v) = w (e.g., f is surjective if and only if coker f = 0), while dim k (ker f ) measures the degrees of freedom in a solution (v + u is solution for all u ∈ ker f ).

Example 2. Viewing the basic operators 1, t, ∂ , ∈ I as k-linear maps on V = W = k[t], we get:

ker 1 = kert = ker = 0, ker ∂ = k, im 1 = im ∂ = k[t], imt = im = k[t]t.
Hence, they are also Fredholm with index:

ind k 1 = 0, ind k t = ind k = -1, ind k ∂ = 1.
If V and W are two finite-dimensional k-vector spaces, then

dim k (coker f ) = dim k (W ) -dim k (im f )
and the rank-nullity theorem

yields dim k V = dim k (im f ) + dim k (ker f ), hence ind k f = dim k V -dim k W, (14)
i.e., ind k f depends only on the dimensions of V and W . We also recall the index formula for Fredholm operators.

Proposition 3. Let V f -→ V g
-→ V be k-linear maps between k-vector spaces. If two of the maps f , g, and g • f are Fredholm, then so is the third, and:

ind k (g • f ) = ind k g + ind k f . ( 15
)
Proof. Considering the following commutative square

V f / / V g V g • f / / V ,
we obtain the following commutative exact diagram (see, e.g., [START_REF] Rotman | An introduction to homological algebra[END_REF]):

0 0 ker g 0 / / ker f / / V f / / V g / / coker f / / 0 0 / / ker(g • f ) / / V g • f / / V / / coker(g • f ) / / 0. 0 coker g 0
A chase in the above commutative exact diagram shows that we have the following long exact sequence of finitedimensional k-vector spaces [START_REF] Rotman | An introduction to homological algebra[END_REF]:

0 / / ker f / / ker(g • f ) / / ker g / / coker f / / coker(g • f ) / / coker g / / 0.
Inria Using the Euler-Poincaré characteristic [START_REF] Rotman | An introduction to homological algebra[END_REF], we then get

dim k ker f -dim k ker(g • f ) + dim k ker g -dim k coker f + dim k coker(g • f ) -dim k coker g = 0,
which finally proves [START_REF] Boulier | On symbolic approaches to integrodifferential equations[END_REF]. Definition 6. A k-linear map between two k-vector spaces is called finite-rank if its image is finite-dimensional.

Example 3. Let us consider E = 1 -∂ ∈ I. It has an infinite-dimensional kernel ker k E = k[t]t, but its image im k E = k is one-dimensional.
More generally, every boundary operator d 3 ∈ I Φ is obviously of finite rank since its image is contained in the k-vector space of polynomials with degree less than or equal n, where n is the maximal index i with a nonzero coefficient f i j or g i j in [START_REF] Bavula | The algebra of integro-differential operators on a polynomial algebra[END_REF].

Clearly, composing a finite-rank map with a linear map from either side gives again finite-rank map and Proposition 3 shows that the composition of two Fredholm operators is a Fredholm operator. Proposition 4. Let V be a k-vector space and A a k-subalgebra of end k (V ). Then,

F A = {a ∈ A | a is Fredholm} forms a monoid and C A = {c ∈ A | c is finite-rank} is a two-sided ideal of A .
In particular, we have another interpretation of the only proper two-sided ideal (E) of boundary operators as finite-rank operators. All other ID operators of I Φ \ (E) are Fredholm as we shall see in Proposition 6. More generally, the notion of (strong) compact-Fredholm alternative for an arbitrary k-algebra A was introduced in [START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF].

Polynomial Solutions of Rational Indicial Maps and Polynomial Index

Computing polynomial solutions of linear systems of OD is well-studied in symbolic computation since it appears as a subproblem of many important algorithms. See, for example, [START_REF] Bostan | Fast algorithms for polynomial solutions of linear differential equations[END_REF][START_REF] Abramov | On solutions of linear functional systems[END_REF][START_REF] Abramov | Special formal series solutions of linear operator equations[END_REF][START_REF] Barkatou | On rational solutions of systems of linear differential equations[END_REF][START_REF] Abramov | On polynomial solutions of linear operator equations[END_REF][START_REF] Abramov | Fast algorithms to search for the rational solutions of linear differential equations with polynomial coefficients[END_REF]. In this section, we discuss an algebraic setting and an algorithmic approach for the computation of polynomial solutions (kernel), cokernel, and the "polynomial" index for a general class of linear operators including ID operators.

For computing the kernel and cokernel of a k-linear map L : V -→ V on infinite-dimensional k-vector spaces V and V , we can use the following simple consequence of the snake lemma in homological algebra (see, e.g., [START_REF] Rotman | An introduction to homological algebra[END_REF]).

Lemma 2. Let L : V -→ V be a k-linear map and U ⊆ V , U ⊆ V k-subspaces such that L(U) ⊆ U . Let L = L |U : U -→ U and L : V /U -→ V /U be the induced k-linear map defined by L(π(v)) = π (L(v)) for all v ∈ V , where π : V -→ V /U (resp., π : V -→ V /U
) is the canonical projection onto V /U (resp., V /U ). Then, we have the following commutative exact diagram:

0 / / U L / / V L π / / V /U L / / 0 0 / / U / / V π / / V /U / / 0. ( 16
)
If L is an isomorphism, i.e., V /U ∼ = V /U , then:

ker L = ker L, coker L ∼ = coker L.
Moreover, if U and U are two finite-dimensional k-vector spaces, then L is Fredholm and:

ind k L = dim k U -dim k U .
Proof. Since L is an isomorphism, applying the standard the snake lemma (see, e.g., [START_REF] Rotman | An introduction to homological algebra[END_REF]) to the following commutative exact diagram of k-vector spaces 0

0 ker L ker L 0 0 / / U L / / V L π / / V /U L / / 0 0 / / U / / V π / / V /U / / 0, coker L coker L 0 0 0
we obtain the following long exact sequence of k-vector spaces

0 -→ ker L -→ ker L -→ 0 -→ coker L -→ coker L -→ 0,
and the statements about the kernel and cokernel follow. If U and U are two finite-dimensional k-vector spaces, then so are ker L = ker L and coker

L ∼ = coker L and ind k L = ind k L = dim k U -dim k U by (14).
Remark 1. In the language of homological algebra, the fact that L defines an isomorphism in Lemma 2 means that the following chain complex of k-vector spaces

0 / / U L / / V L / / 0 0 / / U / / V / / 0
is a quasi-isomorphism, namely the homologies of the horizontal complexes, i.e., V /U and V /U , are isomorphic.

Hence, the complex 0 / / V L / / V / / 0 of infinite-dimensional k-vector spaces, whose homologies are ker L and coker L, is then reduced to the complex 0 / / U L / / U / / 0 of finite-dimensional k-vector spaces, which homologies, ker L and coker L , are then isomorphic to ker L and coker L.

From an algorithmic point of view, we want to find finite-dimensional k-subspaces U and U , and an algorithmic criterion for L being an isomorphism on the remaining infinite-dimensional parts V /U and V /U .

The cokernel of a k-linear map f : V -→ W between two finite-dimensional k-vector spaces V and W can be characterized as follows. Choosing bases of V and W , there exists a matrix C ∈ k m×n such that f (v) = C v for all v ∈ V ∼ = k n . Computing a basis of the finite-dimensional k-vector space kerC T and stacking the elements of this basis into a matrix D ∈ k l×m , we get kerC T = im D T . Then, coker f ∼ = im D and, more precisely, if π : W -→ coker f is the canonical projection onto coker f , then the k-linear map σ : coker f -→ im D defined by σ (π(w)) = D w for all w ∈ W , is an isomorphism of k-vector spaces.

Let us now study when the k-linear map L : V /U -→ V /U is an isomorphism. In what follows, we shall focus on the polynomial case, namely, V = V = k[t]. To do that, let us introduce the degree filtration of k[t], namely,

k[t] = i∈N k[t] ≤i , k[t] ≤i = i j=0 k t j ,
Inria defined by the finite-dimensional k-vector spaces k[t] ≤i formed by the polynomials of k[t] of degree less than or equal to i (we set k[t] ≤-1 = 0). Note that this filtration is induced by any basis {p i } i∈N of k[t] with deg p i = i for all i ∈ N.

For motivating the following definition, we recall that we defined the multiplication operator, derivation, and integral operator in terms of their action on the basis (t n ) n∈N of k[t]; see Equation ( 1) and Definition 1. More generally, we can easily check that the action of the summands of an ID operator in the normal form [START_REF] Bavula | Generalized Weyl algebras and their representations[END_REF] is respectively given by:

(t i ∂ j )(t n ) = n! (n -j)! t n-j+i , n ≥ j, (t i ∂ j )(t n ) = 0, n < j, (t i t j )(t n ) = 1 n + j + 1 t i+ j+n+1 .
So the action on a basis element t n for n large enough given by a rational function in the exponent n and a shift in the exponent.

Definition 7. A k-linear map L : k[t] -→ k[t]
is called rational indicial if there exist a nonzero rational function q ∈ k(n), an integer s ∈ Z, a bound M ∈ N, and nonzero constants c n ∈ k * such that L(t n ) = c n q(n)t n+s + lower degree terms, for all n ≥ M ≥ -s. Then, we call the pair rsym(L) = (s, q) its rational symbol.

Example 4. The rational symbols of the defining ID operators are:

rsym(1) = (0, 1), rsym(t) = (1, 1), rsym
(∂ ) = (-1, n), rsym( ) = 1, 1 n + 1 .
Operators such as shift and dilation operators on k[t] are also rational indicial. For instance, if a ∈ k \ {0} and χ a is the dilation operator defined by χ a (t n ) = (at) n for all n ≥ 0, then we get c n = a n , q = 1, s = 0, and M = 0.

Example 5. The sum of a rational indicial map and a finite-rank map is also rational indicial with the same symbol for a large enough bound M. For instance, if we consider L 1 = 1+t 3 E 0 , then we have L 1 (1) = t 3 +1 and L 1 (t n ) = t n for n ≥ 1, which shows that M = 1, s = 0, q = 1, and c n = 1 (compare with L 0 = 1 which is such that M = 0, s = 0, c n = 1, and q = 1). Finally, if we consider

L 2 = 1 + t 3 E 0 ∂ 2 , then we have L 2 (1) = 1, L 2 (t) = t, L 2 (t 2 ) = 2t 3 + t 2 ,
and L 2 (t n ) = t n for n ≥ 3, which shows that M = 3, s = 0, q = 1, and c n = 1.

Let us now state a result for the computation of the kernel and cokernel of rational indicial maps (compare with Lemma 6.5. of [START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF]).

Proposition 5. Let L : k[t] -→ k[t] be a k-linear map. Let -1 ≤ N, -(N + 1) ≤ s, U = k[t] ≤N , U = k[t] ≤N+s be such that L(U) ⊆ U . Let L = L |U : U -→ U be the induced map. If deg L(t n ) = n + s for all n ≥ N + 1, then: ker L = ker L, coker L ∼ = coker L.
Moreover, L is a Fredholm operator with ind k L = -s.

Proof. Let V = V = k[t] and π : V -→ V /U (resp., π : V -→ V /U ) be the canonical projection onto V /U (resp., V /U ). Then, L(π(t n )) = π (L(t n )) for all n ∈ N.

Let us note T n = π(t n ) and S n = π (t n ) for all n ≥ 0. Then, we get:

V /U = k[t]/k[t] ≤N = i≥N+1 k T i , V /U = k[t]/k[t] ≤N+s = i≥N+s+1 k S i . Moreover, if p = ∑ N+r i=N+1 p i t i ∈ k[t]
, where p i ∈ k, then we have

L(p) = N+r ∑ i=N+1 p i L(t i ) = N+r ∑ i=N+1 p i (c i q(i)t i+s + . . .) = N+r ∑ i=N+1 p i c i q(i)t i+s + . . . ,
where . . . denotes lower degree terms. Note that we have π(p) = ∑ N+r i=N+1 p i T i and π (L(p)) = ∑ N+r i=N+1 p i c i q(i) S i+s + . . ., which shows that L corresponds to the following linear operator:

L : V /U = i≥N+1 k T i -→ V /U = i≥N+s+1 k S i ∑ N+r i=N+1 p i T i -→ ∑ N+r i=N+1 p i c i q(i) S i+s + . . .
Considering the coefficients of the elements of V /U (resp., V /U ) in the basis {T i } i≥N+1 (resp., {S j } j≥N+s+1 ), up to isomorphism of k-vector spaces, we obtain:

L : i≥N+1 k -→ i≥N+s+1 k (p N+1 , p N+2 , .
. . , p N+r , 0, . . .) -→ (p N+1 c N+1 q(N + 1) + . . . , . . . , p N+r c N+r q(N + r) + . . . , 0, . . .).

We note that L is defined by an upper triangular infinite matrix which determinant is ∏ N+r i=N+1 c i q(i) = 0. Hence, the linear operator L is invertible, and thus defines an isomorphism of k-vector spaces, i.e. V /U ∼ = V /U .

Finally, the result follows from Lemma 2 after noting that:

dim k U -dim k U = N + 1 -(N + 1 + s) = -s.
Example 6. Let us consider the Fredholm operator L = t + t. Then, we get L(t n ) = 1 n+1 + 1 n+2 t n+2 for all n ≥ 0, which shows that rsym(L) = 2, 2 n+3 (n+1) (n+2) . Hence, if we consider

N = 0, s = 2, V = V = k[t], U = k, U = k[t] ≤2
, and L = L |U , i.e., L (u) = 3 ut 2 /2 for all u ∈ k, then ker L = 0 and coker L = k[t] ≤2 /(t 2 ) ∼ = k + k t. Let us note T i = π(t i ) and S i = π (t i ) for all i ∈ N. If p = ∑ r i=0 p i t i ∈ k[t], then using that q(i) = 0 for all i ∈ N, we obtain the following isomorphism of k-vector spaces

L : V /U = k[t]/k = i≥1 k T i -→ V /U = k[t]/k[t] ≤2 = i≥3 k S i π(p) = ∑ r i≥1 p i T i -→ π (L(p)) = ∑ r i≥1 p i q(i) S i+2 ,
which, up to isomorphism, corresponds to the isomorphism of k-vector spaces:

(p 1 , . . . , p r , 0, . . .) -→ (p 1 q(1), . . . , p r q(r), 0, . . .).

By Proposition 5, we obtain ker L = ker L = 0 and coker

L ∼ = coker L ∼ = k + k t.
Similarly, we let the reader compute the polynomial solutions of L = 2 3 tt.

Given a rational indicial operator with rational symbol (s, q) and bound M, we obtain a bound N for Proposition 5 by computing the largest nonnegative integer root l of q and taking N = max(l, M). Hence computing the kernel and cokernel of L : k[t] -→ k[t] reduces to the same problem for the k-linear map L = L |U : U -→ U between two finite-dimensional k-vector spaces, which can be solved using basic linear algebra techniques. We have implemented in Maple the computation of kernel and cokernel of rational indicial maps. Corollary 3. A rational indicial operator with rational symbol (s, q) is Fredholm with index -s and its kernel and cokernel can be effectively computed.

We can explicitly compute the rational symbol (s, q) for d ∈ (E) from its normal form. For computing the index of OD equations with analytic coefficients, we have the Komatsu-Malgrange index theorem [START_REF] Komatsu | On the index of ordinary differential operators[END_REF][START_REF] Malgrange | Sur les points singuliers des équations différentielles[END_REF]. The following proposition is a purely algebraic version of an index theorem. Compare with [10, Proposition 6.1]. Inria Proposition 6. Let d = ∑ a i j t i ∂ j + ∑ b i j t i t j + d 3 ∈ I Φ be an ID operator, where d 3 ∈ (E), such that d ∈ (E). Then, the k-linear map L

d : k[t] -→ k[t], p -→ d(p),
is rational indicial with rational symbol (s, q) given by s

= -ind k d = max({i -j | a i j = 0} ∪ {i + j + 1 | b i j = 0}),
and:

q(n) = ∑ i-j=s a i j n! (n -j)! + ∑ i+ j+1=s b i j 1 n + j + 1 .

Polynomial Solutions and Annihilators

In his proof of Theorem 2, stating that I is a coherent ring, Bavula [START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF] uses that the left and right annihilators are finitely generated I-modules, for which a non-constructive argument is given. In this section, we generalize this result to right annihilators of Fredholm operators d ∈ I Φ with several evaluations using a constructive approach. As outlined at the end of Section 5, our approach is based on the fact that we can identify integro-differential operators with the corresponding linear map on the polynomial ring (see Corollary 2). To characterize the right annihilator ann I Φ (d.), we use the equivalences [START_REF] Bokut | Gröbner-Shirshov bases and their calculation[END_REF]. If d is Fredholm, i.e., d ∈ I Φ \ (E), then ker L d is a finite-dimensional k-vector space, and thus, e has to be finite-rank and hence must be a boundary operator e ∈ (E). Thus, we have to compute polynomial solutions of the Fredholm operator d, i.e., ker L d , and then find generators for all the e's satisfying im L e ⊆ ker L d .

We first describe the image of a finite-rank operator L e for a boundary operator e ∈ (E). By ( 8), e is a finite k[t]-linear combination of terms of the form E α ∂ i and E α t i with α ∈ Φ, namely

e = ∑ α∈Φ l ∑ i=0 p α,i E α ∂ i + m ∑ i=0 q α,i E α t i , (17)
where p α,i , q α,i ∈ k[t]. With Lemma 1, we can now apply the following general fact for linear functionals on arbitrary vector spaces; see, e.g., [27, pp. 71-72].

Lemma 3. Let V be a k-vector space and λ 1 , . . . , λ n ∈ V * k-linear functionals. Then, the λ i are k-linearly independent iff there exist v 1 , . . . , v n ∈ V such that:

∀ i, j = 1, . . . , n, λ i (v j ) = δ i j .
Proposition 7. Let e ∈ (E) be as in [START_REF] Chyzak | OreModules: A symbolic package for the study of multidimensional linear systems[END_REF]. Then, we have:

im L e = ∑ α∈Φ l ∑ i=0 k p α,i + ∑ α∈Φ m ∑ i=0 k q α,i .
Proof. The inclusion ⊆ is obvious since E α ∂ i and E α t i are functionals. Let E α ∂ i or E α t i be a linear functional corresponding to a nonzero summand in [START_REF] Chyzak | OreModules: A symbolic package for the study of multidimensional linear systems[END_REF]. Since these linear functional forms are k-linearly independent by Lemma 1, using Lemma 3 with V = k[t], there exists a polynomial p ∈ k[t] such that (E α ∂ i )(p) = 1 (resp., (E α t i )(p) = 1) and (E β ∂ j )(p) = 0 (resp., (E β t j )(p) = 0) for all other functionals corresponding to nonzero summands of [START_REF] Chyzak | OreModules: A symbolic package for the study of multidimensional linear systems[END_REF]. Then, we get L e (p) = e(p) = p α,i or L e (p) = e(p) = q α,i , which proves the reverse inclusion.

ann I Φ (d.) = n ∑ i=1 (r i E) I Φ .
In particular, ann I Φ (d.) is a finitely generated right I Φ -module.

Proof. Since im L r i E = k r i ⊆ ker L d , the inclusion ⊇ follows by [START_REF] Bokut | Gröbner-Shirshov bases and their calculation[END_REF]. Conversely, let e ∈ I Φ as in [START_REF] Chyzak | OreModules: A symbolic package for the study of multidimensional linear systems[END_REF] with d e = 0. Then, by ( 13) and Proposition 7, we have:

im

L e = ∑ α∈Φ l ∑ i=0 k p α,i + ∑ α∈Φ m ∑ i=0 k q α,i ⊆ ker L d = n ∑ i=1 k r i .
Hence, every nonzero p α,i and q α,i can be written as a k-linear combination of the r i 's, i.e., p α,i = ∑ n j=1 u α,i, j r j and q α,i = ∑ n j=1 v α,i, j r j for certain u α,i, j , v α,i, j ∈ k. Using [START_REF] Chyzak | OreModules: A symbolic package for the study of multidimensional linear systems[END_REF] and E E α = E α , we then get where the polynomial ri is defined by substituting t i by i! ∂ i into r i .

Proof. By Theorem 4, we have ann I Φ (θ (d).) = ∑ n i=1 (r i E) I Φ . Applying θ to r i E, we get θ (r i E) = θ (E) θ (r i ) = E r i ((t ∂ + 1) ∂ ). We have θ (r i E) d = θ (θ (d) r i E) = θ (0) = 0, which proves the inclusion ⊇. Conversely, if e ∈ ann I Φ (.d), i.e., e d = 0, then θ (d) θ (e) = 0, and thus θ (e) = ∑ n i=1 r i E d i for certain d i ∈ I Φ , which yields e = θ 2 (e) = ∑ n i=1 θ (d i ) E θ (r i ), which proves the inclusion ⊆ and the first equality. Finally, we note that E θ (t) j = E ((t ∂ + 1) ∂ ) j = j! E ∂ j for j ∈ N, and thus E ∑ r j=0 s j θ (t) j = E ∑ r j=0 s j j! ∂ j , where s j ∈ k, which proves the second equality. for [START_REF] Bavula | The algebra of polynomial integro-differential operators is a holonomic bimodule over the subalgebra of polynomial differential operators[END_REF], which correspond to the following compatibility conditions: 2 ü(0) + 3/5 u(0) = 0, u(0) + 1/2 u(0) = 0.

  D denote the two-sided ideal generated by D T -T D -1 and define the k-algebra: A = k T, D /J. By definition, the Leibniz rule D T ≡ T D + 1 mod J holds in A. Using this identity, each element of d ∈ A can uniquely be written as a finite sum

  This gives rise to new S-polynomials with D T -T D -1 and one sees inductively that we need to add the family ∀ n ≥ 1, I T n D -T n + n I T n-1 to our generators, corresponding to integration by parts. Computing the S-polynomials with this family and D E, we then obtain IE -T E, and ∀ n ≥ 1, I T n E -T n+1 /(n + 1) E which corresponds to the k-linearity of the integral. Finally, the S-polynomial between I T D -T + I and D I -1 is given by: S(I T D, D I) = (T -I) I -I T. So we obtain the polynomial I 2 -T I + I T, allowing to reduce an iterated integral to a sum of two single integrals. Again, this identity gives rise to an infinite family ∀ n ≥ 1, I T n I -(T n+1 I + I T n+1 )/(n + 1) of new generators.

Proposition 1 .

 1 The only nonzero proper two-sided ideal of I is (E). Proof. Let d ∈ I \ (E) with d ≡ d 1 + d 2 + d 3 as in (3) and d 1 + d 2 = 0 by assumption. Using the identities

  e k-1 e k = e k e k-1 = e k-1 , which shows that I e k-1 ⊆ I e k and e k-1 I ⊆ e k I. Since e k is an idempotent of I, i.e. e 2 k = e k , if we have e k ∈ I e k-1 , i.e. e k = ∑ k-1 i=0 d i e i for certain d i ∈ I, then we get

Inria

  The left annihilator of d ∈ I is defined by ann I (.d) := {e ∈ I | e d = 0}, and, analogously, the right annihilator is defined by: ann I (d.) := {e ∈ I | d e = 0}. The left annihilator can be interpreted as compatibility conditions of the inhomogeneous ID equation d y(t) = u(t). Indeed, for e ∈ ann I (.d), we have: e u(t) = e d y(t) = 0. If d is not a zero divisor, then d y = u does not admit compatibility condition of the form e u = 0, where e ∈ I.

Theorem 3 (

 3 [START_REF] Bavula | The algebra of integro-differential operators on an affine line and its modules[END_REF]). Let d ∈ I. Then, the left (resp., right) annihilator ann I (.d) (resp., ann I (d.)) of d is a finitely generated left (resp., right) I-module.

Theorem 4 .

 4 Let Φ be a subset of k with 0 ∈ Φ. Let d ∈ I Φ be Fredholm with ker L d = n ∑ i=1 k r i , where r i ∈ k[t]. Then, we have:

Example 7 .Corollary 4 .

 74 i, j r j E α ∂ i + m ∑ i=0 v α,i, j r j E α t i i, j r j E E α ∂ i + m ∑ i=0 v α,i, j r j E E α t i i, j E α ∂ i + ∑ α∈Φ m ∑ i=0 u α,i, j E α t i ∈ n ∑ j=1 (r j E) I Φ ,which proves the reverse inclusion ⊆ and thus the result. If d = ∂ 2 , then we have kerL d = k + k t, which shows that ann I Φ (∂ 2 .) = E I Φ + t E I Φ . We can check again that ∂ 2 (t E) = (t ∂ 2 + 2 ∂ ) E = 0. Lemma 4 (Corollary 3.2 of [10]). If d ∈ I is Fredholm, then so is θ (d).Proof. Let d ∈ I be Fredholm, i.e., d ∈ I \ (E). Suppose that θ (d) ∈ (E). At the end of Section 5, we show that θ ((E)) ⊂ (E). Thus, d = θ (θ (d)) ∈ (E), which is a contradiction and proves that θ (d) ∈ I \ (E), i.e., θ (d) is Fredohlm.The following corollary ofTheorem 4 gives a way to compute a set of generators of the left annihilator ann I (.d). Let Φ be a subset of k with 0 ∈ Φ. Let d ∈ I Φ be Fredholm with ker L θ (d) = ∑ n i=1 k r i , where r i ∈ k[t]. Then, we have ann I Φ (.d) = n ∑ i=1 I Φ E r i ((t ∂ + 1) ∂ ) = n ∑ i=1 I Φ E ri (∂ ),

Example 8 .Example 9 .

 89 If d = 2 , then θ (d ) = ∂ 2 and using Example 7, we obtain ann I Φ (∂ 2 .) = E I Φ + t E I Φ , which showsthat ann I Φ ( 2 .) = I Φ E + I Φ E (t ∂ + 1) ∂ = I Φ E + I Φ E ∂ . We can check again that E (t ∂ + 1) ∂ 2 = E (t ∂ + 1) = E (t + ) = 0.Finally, according to the comments above Example 1, we obtain that the compatibility conditions of the inhomogeneous equation t 0 τ 0 y(x) dx dτ = u(t), where u is a fixed enough regular function, are generated by u(0) = 0 and (t ü(t) + u(t))(0) = u(0) = 0.Similarly, we let the reader check that we have annI Φ (.(t ∂ -1) ∂ 2 ) = E ∂ .All necessary steps for computing right and left annihilators have been implemented based on the Maple package IntDiffOp[START_REF] Korporal | Symbolic computation for ordinary boundary problems in Maple[END_REF] for ID operators and boundary problems. Let us compute the compatibility conditions of[START_REF] Bavula | The algebra of polynomial integro-differential operators is a holonomic bimodule over the subalgebra of polynomial differential operators[END_REF]. Note that rsym(θ (d)) = (0, n 2 -3 n + 2), where:θ (d) = (t 2 + t -3/5) ∂ 2 -(2t + 1) ∂ + 2.The largest nonnegative integer root of q is 2. With this bound N for Proposition 5, we get for the following kernel:ker L θ (d) = k (t 2 + 3/5) + k (t + 1/2).By Theorem 4, we obtain: annI (θ (d).) = ((t 2 + 3/5) E) I + ((t + 1/2) E) I.Computing the involution of these generators yield the left annihilator ann I (.d) = I (2 E ∂ 2 + 3/5 E) + I (E ∂ + 1/2 E)

RR n°9002

was supported by the Austrian Science Fund (FWF): P27229.