Shaoshi Chen
email: schen@amss.ac.cn

Frédéric Chyzak
email: frederic.chyzak@inria.fr

Ruyong Feng
email: ryfeng@amss.ac.cn

Guofeng Fu
email: fuguofeng@mmrc.iss.ac.cn

Ziming Li
email: zmli@mmrc.iss.ac.cn

On the Existence of Telescopers for Mixed Hypergeometric Terms

Keywords: Creative telescoping, Zeilberger's algorithms, Existence criteria

We present a criterion for the existence of telescopers for mixed hypergeometric terms, which is based on additive and multiplicative decompositions. The criterion enables us to determine the termination of Zeilberger's algorithms for mixed hypergeometric inputs, and to verify that certain indefinite sums do not satisfy any polynomial differential equation.

Introduction

Given a sum U m := ∞ n=0 u m,n to be computed, creative telescoping is a process that determines a recurrence in m satisfied by the univariate sequence U = (U m ) from a system of recurrences in m and n satisfied by the bivariate summand u = (u m,n ). A natural counterpart exists for integration. Algorithmic research on this topic has been initiated by Zeilberger in the early 1980s, leading in the 1990s to creative-telescoping algorithms for summands and integrands described by first-order linear equations, i.e., for hypergeometric terms and hyperexponential functions (Zeilberger, 1990a[START_REF] Zeilberger | The method of creative telescoping[END_REF][START_REF] Almkvist | The method of differentiating under the integral sign[END_REF].

The termination problem of Zeilberger's algorithms has been extensively studied in the last two decades (Wilf and Zeilberger, 1992b;[START_REF] Abramov | A criterion for the applicability of Zeilberger's algorithm to rational functions[END_REF][START_REF] Abramov | When does Zeilberger's algorithm succeed?[END_REF][START_REF] Chen | Applicability of the q-analogue of Zeilberger's algorithm[END_REF] and can be related to existence problems for other operations, like the computation of diagonals [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]. The main output of creative telescoping is the recurrence on the sum U . It is called a telescoper for u. Zeilberger's algorithms terminate if and only if telescopers exist, whence the interest to discuss their existence. Zeilberger (1990b) shows that holonomicity, a notion borrowed from the theory of D-modules, implies the existence of telescopers. In particular, the fundamental theorem in (Wilf and Zeilberger, 1992a) states that telescopers always exist for proper hypergeometric terms. However, holonomicity is merely a sufficient condition, i.e., there are cases in which the input functions are not holonomic (proper) but Zeilberger's algorithms still terminate, see [START_REF] Chyzak | A non-holonomic systems approach to special function identities[END_REF]. Therefore, a challenging problem is to find a necessary and sufficient condition that enables us to determine the existence of telescopers.

In view of the theoretical difficulty, special attention has been focused on the subclass of hypergeometric terms, hyperexponential functions, and mixed hypergeometric terms (see Definition 2.8). In the continuous case, the results by [START_REF] Bernšteȋn | Modules over a ring of differential operators. An investigation of the fundamental solutions of equations with constant coefficients[END_REF], [START_REF] Kashiwara | On the holonomic systems of linear differential equations[END_REF], [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF] and [START_REF] Takayama | An approach to the zero recognition problem by Buchberger algorithm[END_REF] show that every hyperexponential function has a telescoper. This implies that Zeilberger's algorithm always succeeds on hyperexponential inputs. However, the situation in other cases turns out to be more involved. In the discrete case, the first complete solution to the termination problem has been given by [START_REF] Le | On the q-analogue of Zeilberger's algorithm to rational functions[END_REF] and [START_REF] Abramov | A criterion for the applicability of Zeilberger's algorithm to rational functions[END_REF], by deciding whether there exists a telescoper for a given bivariate rational sequence in the (q)-discrete variables m and n. According to their criterion, the rational sequence 1/(m 2 + n 2 ) m,n∈Z + , has no telescoper. The criterion has been extended to the general case of bivariate hypergeometric terms by [START_REF] Abramov | Applicability of Zeilberger's algorithm to hypergeometric terms[END_REF][START_REF] Abramov | When does Zeilberger's algorithm succeed?[END_REF]. He proved that a hypergeometric term can be written as a sum of a hypergeometric-summable term and a proper one if it has a telescoper, see (Abramov, 2003, Theorem 10). Similar results have been obtained in the q-discrete case by [START_REF] Chen | Applicability of the q-analogue of Zeilberger's algorithm[END_REF].

Almkvist and Zeilberger (1990) presented a continuous-discrete analogue of creative telescoping. This analogue is useful in the study of orthogonal polynomials (Koepf, 1998, Chapters 10-13). In analogy with the discrete case, not all mixed hypergeometric terms have telescopers. Therefore, an Abramov-like criterion is also needed in the mixed case.

In order to unify the various cases of mixed rational terms, Chen and Singer (2012) recently presented a criterion that is based on residue analysis for the existence of telescopers for bivariate rational functions. In the present paper, we give a criterion, Theorem 6.3, on the existence of telescopers for mixed hypergeometric terms, including continuousdiscrete, continuous-q-discrete and discrete-q-discrete terms. The criterion determines whether Zeilberger's algorithms for mixed hypergeometric terms terminate. Moreover, the non-existence of telescopers makes us able to verify that some indefinite sums do not satisfy any polynomial differential equation. See [START_REF] Hardouin | Differential Galois theory of linear difference equations[END_REF][START_REF] Schneider | Parameterized telescoping proves algebraic independence of sums[END_REF] and Example 6.8 in this paper.

The rest of this paper is organized as follows. An algebraic setting for mixed hypergeometric terms is described in Section 2, and the existence problem of telescopers is stated in Section 3. In Section 4, we define the two notions of exact and proper terms, and we describe two kinds of decompositions: additive and structural. These notions and decompositions are crucial for establishing our criterion. A necessary condition on the existence of telescopers is presented in Section 5. The criterion is given in Section 6, which is based on the fundamental theorem in Wilf and Zeilberger (1992a). The appendix contains a detailed proof of the fundamental theorem in the mixed setting (Theorem 6.1).

Choice (θx, θy) Ground field (k(x, y), (θx, θy)) Associated Ore ring k(x, y) ∂x, ∂y (δx, σy) (k(x, y), (δx, σy)) k(x, y) Dx, Sy (δx, τy) (k(x, y), (δx, τy)) k(x, y) Dx, Ty (σx, τy) (k(x, y), (σx, τy)) k(x, y) Sx, Ty

Linear functional operators and compatible rational functions

A first-order mixed linear-functional system is of the form

   θ x (z) = az, θ y (z) = bz, (1)
where (θ x , θ y ) ∈ Θ and a, b ∈ k(x, y). For brevity, we call (1) a first-order mixed system.

Example 2.4. Let (θ x , θ y ) = (δ x , σ y ), a = y/x and b = -x. The system (1) becomes

   δ x (z) = y x z, σ y (z) = -x z.
It is straightforward to verify that the expression (-x) y solves this mixed system. Moreover, this system does not have any nonzero rational solution in k(x, y): if it had, we could write such a solution in the form

z = P Q = p m y m + • • • + p 0 q n y n + • • • + q 0
, where p i and q j are in k(x) with p m q n = 0.

By the equality σ y (z) = -xz, we have σ y (P )Q = -xP σ y (Q). Equating the leading coefficients with respect to y yields p m q n = -xp m q n , which implies that x = -1. This is a contradiction with the assumption that x is transcendental over k.

The example given above shows that solving a mixed system generally requires to extend the field k(x, y). This motivates us to consider ring extensions of k(x, y) endowed with a mixed pair of operators.

Definition 2.5. For a pair (θ x , θ y ) ∈ Θ, we call a tuple R, ( θx , θy ) a ring extension of (k(x, y), (θ x , θ y )) if the following conditions are satisfied.

(i) R is a commutative ring containing k(x, y).

(ii) θx : R → R is an extension of θ x , and θy : R → R is an extension of θ y .

(iii) θx is a derivation on R if θ x = δ x , and it is a monomorphism if θ x = σ x or θ x = τ x .

(iv) θy is a derivation on R if θ y = δ y , and it is a monomorphism if θ y = σ y or θ y = τ y . (v) θx and θy commute. Moreover, such a ring extension is said to be simple if there does not exist any ideal I of R such that θx (I) ⊂ I and θy (I) ⊂ I except for I = R and I = {0}.

Without any possible ambiguity, we denote the operators θx and θy obtained as in the definition given above by θ x and θ y , respectively. The reader may find more general ring extensions endowed with derivations, shift and q-shift operators, potentially with respect to the same variable, in [START_REF] Hardouin | Differential Galois theory of linear difference equations[END_REF].

Let L = i,j a i,j ∂ i x ∂ j y be an Ore polynomial in k(x, y) ∂ x , ∂ y , where k(x, y) is endowed with a mixed pair (θ x , θ y ) of operators. Let (R, (θ x , θ y )) be a ring extension of (k(x, y), (θ x , θ y )). The application of L to an element r ∈ R is defined to be

L(r) = i,j a i,j θ i x • θ j y (r).
So an Ore polynomial can be viewed as a linear functional operator on R. One can verify that multiplication of Ore polynomials and composition of linear functional operators are compatible, that is, (

L 1 L 2 )(r) = L 1 (L 2 (r)) for L 1 , L 2 ∈ k(x, y) ∂ x , ∂ y and r ∈ R.
We are about to define the constants of a given field (k(x, y), (θ x , θ y )), by describing them in a uniform way as the solutions of specific operators. Define

∆ x := ∂ x -∂ x (1) =          D x if θ x = δ x , S x -1 if θ x = σ x , T x -1 if θ x = τ x .
(2)

We define ∆ y similarly by replacing x with y. An element c ∈ R is then called a constant with respect to the pair (θ x , θ y ) if

∆ x (c) = ∆ y (c) = 0.
One can easily verify that c ∈ k(x, y) is a constant with respect to (θ x , θ y ) if and only if c is an element of k.

Given a system of the form (1), a basic question is whether there exists a ring extension (R, (θ x , θ y )) containing a nonzero solution of the system. This question is related to compatibility conditions of [START_REF]Let h be a mixed term over (k(x, y), (θ x , θ y )), where (θ x , θ y ) = (δ x , σ y ) or (θ x , θ y ) = (σ x , δ y ). If its certificate with respect to the shift operator has a split denominator, then h is telescopable of type[END_REF].

Let k(x, y) be endowed with a mixed pair (θ x , θ y ) of operators. If system (1) has a nonzero solution h in a ring extension (R, (θ x , θ y )), then θ y • θ x (h) = θ x • θ y (h) by the commutativity of θ x and θ y . In addition, if θ x , resp. θ y , is a monomorphism, then a, resp. b, is nonzero. So (1) satisfies the following compatibility conditions:

         δx(b) b = σ y (a)
if it has a nonzero solution in a ring extension of (k(x, y), (θ x , θ y )).

Remark 2.6. The compatibility conditions corresponding to the other three mixed pairs of operators in Θ can be obtained by swapping x with y and a with b in (3).

Definition 2.7. Let (a, b) ∈ k(x, y) × k(x, y) and (θ x , θ y ) ∈ Θ. We say that a and b are compatible with respect to (θ x , θ y ) if the compatibility conditions corresponding to (θ x , θ y ) in (3) and Remark 2.6 are satisfied.

A first-order mixed system of the form ( 1) is said to be compatible if its coefficients a and b are compatible with respect to (θ x , θ y ). Conversely, given a compatible mixed system of the form (1), Theorem 2 in [START_REF] Bronstein | Picard-Vessiot extensions for linear functional systems[END_REF] implies that there exists a simple ring extension (R, (θ x , θ y )) of (k(x, y), (θ x , θ y )) containing a nonzero solution of [START_REF]Let h be a mixed term over (k(x, y), (θ x , θ y )), where (θ x , θ y ) = (δ x , σ y ) or (θ x , θ y ) = (σ x , δ y ). If its certificate with respect to the shift operator has a split denominator, then h is telescopable of type[END_REF]. Moreover, under the assumption that k is algebraically closed, R contains no new constant other than the elements of k. Such a simple ring is called a Picard-Vessiot extension associated to [START_REF]Let h be a mixed term over (k(x, y), (θ x , θ y )), where (θ x , θ y ) = (δ x , σ y ) or (θ x , θ y ) = (σ x , δ y ). If its certificate with respect to the shift operator has a split denominator, then h is telescopable of type[END_REF].

Mixed hypergeometric terms

Hypergeometric terms are a common abstraction of geometric terms, factorials, and binomial coefficients. They play an important role in combinatorics. The continuous analogue of hypergeometric terms is hyperexponential functions: they generalize usual exponential functions and simple radicals. In this paper, we will consider a class of functions in x and y that are solutions of first-order mixed systems, and are therefore intermediate objects between hypergeometric terms and hyperexponential functions.

Definition 2.8. Let k(x, y) be a field endowed with a mixed pair (θ x , θ y ) of operators. Assume that (R, (θ x , θ y )) is a simple ring extension of (k(x, y), (θ x , θ y )), and that the set of constants in R is equal to k. A nonzero element h of R is called a mixed hypergeometric term over (k(x, y), (θ x , θ y )) if there exist a, b ∈ k(x, y) such that θ x (h) = ah and θ y (h) = bh.

We call a the certificate of h with respect to θ x , and b the certificate with respect to θ y .

The certificates of a mixed term are compatible rational functions, because θ x and θ y commute. For brevity, a mixed hypergeometric term will be called a mixed term in the sequel. Viewing mixed terms in an abstract ring allows us to compute their sums, products and inverses legitimately. Moreover, we will never encounter any analytic considerations, such as singularities and the regions of definition. This choice will not do any harm, as the problem we are dealing with is purely algebraic.

We recall some basic facts about mixed terms in this ring setting. These facts are scattered in the literature. We summarize them for the convenience of later references.

The first lemma says that all mixed terms form a multiplicative group, and that two mixed terms with the same certificates differ by a multiplicative constant.

Lemma 2.9. Let the ring extension (R, (θ x , θ y )) be given as in Definition 2.8.

(i) The product of mixed terms is a mixed term, and every mixed term is invertible.

(ii) If two mixed terms have the same certificates, then their ratio belongs to k.

Proof. (i) The closure under product follows from simple calculations with certificates. Now, let h be a mixed term in R, and I be the ideal generated by h in R. Then θ x (h) and θ y (h) belong to I. It follows that θ x (I) ⊂ I and θ y (I) ⊂ I. Since R is simple and h is nonzero, I = R, that is, 1 ∈ I. Consequently, h is invertible.

(ii) Let h 1 and h 2 be two mixed terms in R. If they have the same certificates, then h 1 /h 2 is a constant by a straightforward calculation, that is to say, h 1 = ch 2 for some c ∈ k. ✷

By the second assertion of Lemma 2.9, two mixed terms having the same certificates differ by a multiplicative constant. These constants are irrelevant to the main result of this paper. So we introduce a notation to suppress them.

Let h be a mixed term in R with θ x -certificate a and θ y -certificate b. Set

H(a, b) = {ch | c ∈ k}.
The set consists of zero and mixed terms in R whose respective certificates are a and b.

Clearly, H(a, b) is a one-dimensional linear subspace over k. In the sequel, whenever the notation H(a, b) is used, a and b are assumed to be compatible rational functions in k(x, y), and H(a, b) ⊂ R. In particular, for a nonzero rational function f ∈ k(x, y), the set f H(a, b) is a subset of R. Indeed, it is the one-dimensional linear subspace spanned by f h over k. By the definition of certificates, we have Let h ′ be another mixed term in R with θ x -certificate a ′ and θ y -certificate b ′ . Define

H(a, b)H(a ′ , b ′ ) = {gg ′ | g ∈ H(a, b), g ′ ∈ H(a ′ , b ′ )} ,
which is equal to the one-dimensional linear subspace spanned by hh ′ over k.

More rules for manipulating H(a, b) are given below. They are used for computing the certificates of the product of two mixed terms.

Lemma 2.10. For a field (k(x, y), (θ x , θ y )), we let H(a, b) and H(a ′ , b ′ ) be given as above, and let f be a nonzero rational function in k(x, y).

(i

) If θ x = δ x , then f H(a, b) = H a + θ x (f ) f , b θ y (f ) f and H(a, b)H(a ′ , b ′ ) = H(a + a ′ , bb ′ ). (ii) If θ y = δ y , then f H(a, b) = H a θ x (f ) f , b + θ y (f ) f and H(a, b)H(a ′ , b ′ ) = H(aa ′ , b + b ′ ). (iii) If either (θ x , θ y ) = (σ x , τ y ) or (θ x , θ y ) = (τ x , σ y ), then f H(a, b) = H a θ x (f ) f , b θ y (f ) f and H(a, b)H(a ′ , b ′ ) = H(aa ′ , bb ′ ).
Proof. Let h be a mixed term in H(a, b).

(i) Assume that θ x = δ x and θ y ∈ {σ y , τ y }. It is straightforward to verify that the θ xcertificate and θ y -certificate of f h are a + θ x (f )/f and bθ y (f )/f , respectively. Assume further that h ′ ∈ H(a ′ , b ′ ) with hh ′ = 0. Then the θ x -certificate of hh ′ is a + a ′ , and its θ y -certificate is bb ′ . It follows that H(a, b)H(a ′ , b ′ ) ⊂ H(a + a ′ , bb ′ ). Equality is then a consequence of the two sets being one-dimensional vector spaces. This proves part (i). Parts (ii) and (iii) can be proved in a similar way. ✷ Two mixed terms h 1 and h 2 are said to be similar if the ratio h 1 /h 2 is in k(x, y) \ {0}. Similarity is an equivalence relation. When studying the existence of telescopers, we will encounter at most finitely many mixed terms that are dissimilar to each other. These terms can be regarded as elements in a simple ring extension, because a finite number of Picard-Vessiot extensions associated to compatible first-order mixed systems can be embedded into a simple ring (Li et al., 2006, §2.2). From now on, we assume that R is given as in Definition 2.8. It will be sufficient to consider mixed terms in R.

The next lemma shows that the set consisting of zero and mixed terms similar to each other form a linear space over k(x, y), which is closed under the application of every linear functional operator in k(x, y) ∂ x , ∂ y .

Lemma 2.11. Let g and h be two mixed terms over (k(x, y), (θ x , θ y )). If g and h are similar, then (i) g + h is either equal to zero or similar to h;

(ii) for any L ∈ k(x, y) ∂ x , ∂ y , L(h) is either equal to zero or similar to h.

Proof. (i) Let r ∈ k(x, y) be equal to g/h. Then g + h = (r + 1)h.

(ii) Since h is a mixed term, its successive derivatives and (q-)shifts are either equal to zero or similar to h. So L(h) is either equal to zero or similar to h by part (i). ✷ Remark 2.12. Let h, h 1 , h 2 be three mixed terms. If h = h 1 + h 2 , then the three terms are similar, because the sum of two dissimilar mixed terms is not a mixed term.

The next two examples illustrate how a linear differential or recurrence operator applies to mixed terms similar to a given one. The results will be used for establishing our criterion.

Example 2.13. Consider how to apply D i

x to rh, where r is a rational function in k(x, y) and h is a mixed term in H(u, v) for some u, v ∈ k(x, y).

First,

D x (rh) = (δ x (r) + ru) h. Putting L 1 = D x + u, we rewrite the above relation as D x (rh) = L 1 (r)h.
An easy induction shows that

D i x (rh) = L i (r)h, where L i = (D x + u) i ∈ k(x, y) D x
has coefficients whose common denominators divide some power of den(u). Moreover, the denominator of L i (r) divides (den(u)den(r)) i+1 .

Example 2.14. Consider how to apply S i

x to rh, where r and h are the same as those in the above example.

Let

M i = i-1 j=0 σ j x (u) S i x for i > 0.
Then an easy induction shows that S i x (rh) = M i (r)h. A similar result holds when the shift operator S x is replaced by the q-shift operator T x .

Telescopers for mixed hypergeometric terms

The method of creative telescoping was first formulated and popularized in a series of papers by Zeilberger and his collaborators in the early 1990's [START_REF] Almkvist | The method of differentiating under the integral sign[END_REF]Zeilberger, 1990aZeilberger, ,b, 1991;;Wilf and Zeilberger, 1992a). To illustrate the idea of this method, we consider the problem of finding a linear recurrence equation for the integral (if there exists one):

H(x) := +∞ 0 h(x, y) dy,
where h(x, y) is a mixed term over (k(x, y), (σ x , δ y )). Suppose that all integrals occurring in the derivation below are well-defined. The key step of creative telescoping tries to find a nonzero linear recurrence operator L(x, S x ) in k(x) S x such that

L(x, S x )(h) = D y (g), (4)
for some mixed term g over k(x, y).

Applying the integral sign to both sides of (4) yields

L(x, S x )(H(x)) = g(x, +∞) -g(x, 0).
This implies that L(x, S x ) is indeed the recurrence relation satisfied by H(x) under certain nice boundary condition, say g(x, +∞) = g(x, 0). For example, consider the integral

A(x) = +∞ 0 y x-1 exp(-y) dy.
The differential variant of Zeilberger's algorithm in [START_REF] Almkvist | The method of differentiating under the integral sign[END_REF] delivers a pair (L, g) with

L = S x -x and g = -y x exp(-y).
Note that, if x > 0, then g(x, +∞) = g(x, 0) = 0, which implies that

L(A(x)) = A(x + 1) -xA(x) = 0.
So we recognize the solution A(x) = Γ(x) since the initial value A( 1) is equal to 1. For more interesting examples, see the appendix of [START_REF] Almkvist | The method of differentiating under the integral sign[END_REF] or the book by Koepf (1998, Chapters 10-13).

Definition 3.1. Let h be a mixed term over (k(x, y), (θ x , θ y )). A nonzero linear operator

L(x, ∂ x ) ∈ k(x) ∂ x is called a telescoper of type (∂ x , ∂ y ) for h if there exists another mixed term g such that L(x, ∂ x )(h) = ∆ y (g).
(5) Alternatively, the mixed term h is said to be telescopable of type

(∂ x , ∂ y ) if it has a telescoper of type (∂ x , ∂ y ).
For a given mixed term, when does a telescoper of certain type exist? And how can one construct telescopers? These are two basic problems related to the method of creative telescoping. In the subsequent sections, we will answer the first one for the mixed cases. More precisely, we solve the following problem, which is equivalent to the termination problem of creative-telescoping algorithms for mixed inputs.

Existence Problem for Telescopers. For a mixed term h over (k(x, y), (θ x , θ y )), find a necessary and sufficient condition on the existence of telescopers of type (∂ x , ∂ y ) for h.

Remark 3.2. For a mixed term h, the existence of a telescoper of type (∂ x , ∂ y ) does not imply the existence of a telescoper of type (∂ y , ∂ x ) (see Example 6.4).

Remark 3.3. By Lemma 2.11, the mixed term g in ( 5) is similar to h if ∆ y (g) is nonzero. Otherwise, g can be chosen to be 1.

Exact and proper terms

To study the existence problem for telescopers, we need two key notions: exact terms and proper terms. They are related to additive and multiplicative decompositions of mixed terms, respectively. This section contains three subsections. In §4.1, we define the notion of exact terms and describe an additive decomposition of mixed terms, based on the additive decompositions for univariate (q)-hypergeometric terms and hyperexponential functions in (Abramov and Petkovsek, 2002b;[START_REF] Geddes | Differential rational normal forms and a reduction algorithm for hyperexponential functions[END_REF][START_REF] Chen | Applicability of the q-analogue of Zeilberger's algorithm[END_REF]. In §4.2, we recall the notion of split polynomials from [START_REF] Chen | Applications of Differential-Difference Algebra to Creative Telescoping[END_REF]) and that of spread polynomials from [START_REF] Abramov | When does Zeilberger's algorithm succeed?[END_REF], and describe a relation among the two notions and exact terms. In §4.3, we recall a multiplicative decomposition of mixed terms from [START_REF] Chen | On the structure of compatible rational functions[END_REF], define the notion of proper terms, and study how to decide whether a mixed term is proper.

Exact terms amd additive decompostions

For a univariate hypergeometric term H(y), the Gosper algorithm [START_REF] Gosper | Decision procedure for indefinite hypergeometric summation[END_REF] decides whether it is hypergeometric-summable (also known as Gosper-summable) with respect to y, i.e., whether H = (S y -1)(G) for some hypergeometric term G. Based on the Gosper algorithm, Zeilberger (1990a,b) developed his fast version of creative-telescoping algorithms for bivariate hypergeometric terms. [START_REF] Almkvist | The method of differentiating under the integral sign[END_REF] presented a continuous analogue of the Gosper algorithm for deciding the hyperexponential integrability, which leads to a fast algorithm for hyperexponential telescoping. From the viewpoint of creative telescoping, the Gosper algorithm and its continuous analogue decide whether the identity operator, 1, is a telescoper for the inputs.

The following notion of exact terms is motivated in the differential case by the existence of an underlying exact form. This differential-form point of view was taken in (Chen et al., 2012) recently.

Definition 4.1. Let h be a mixed term over (k(x, y), (θ x , θ y )). We say that h is exact with respect to ∂ x if there exists a mixed term g such that h = ∆ x (g), where ∆ x is defined in ( 2). An exact term with respect to ∂ y is defined likewise.

Remark 4.2. In (Abramov and Petkovsek, 2002b) and [START_REF] Geddes | Differential rational normal forms and a reduction algorithm for hyperexponential functions[END_REF], an exact term is traditionally called a (q-)hypergeometric-summable term in the (q-)discrete case, and a hyperexponential-integrable function in the continuous case, respectively. For each choice of ∂ x in {D x , S x , T x }, it is clear that every exact term with respect to ∂ y has a telescoper of type (∂ x , ∂ y ): for instance 1 is such a telescoper.

The next notion to be introduced, related to exact terms, is that of additive decompositions. An algorithm by Abramov and Petkovsek (2002b) decomposes a hypergeometric term H(y) into the sum ∆ y (H 1 ) + H 2 , where H 2 is minimal in some sense. Such a decomposition is called an additive decomposition for H with respect to y. Abramov and Petkovšek's algorithm generalizes the capability of the Gosper algorithm in the sense that H is hypergeometric-summable if and only if H 2 is zero. In the continuous case, an algorithm to decompose a hyperexponential function H(y) as D y (H 1 ) + H 2 , where H 1 and H 2 are either zero or hyperexponential, is part of the proof of Lemma 4.2 in [START_REF] Davenport | The Risch differential equation problem[END_REF]. This remained unknown to [START_REF] Geddes | Differential rational normal forms and a reduction algorithm for hyperexponential functions[END_REF], who later described a similar additive decomposition as a continuous analogue of Abramov and Petkovsek's algorithm, but also prove that H 2 satisfies certain minimality requirements. Based on the continuous analogue, [START_REF] Bostan | Hermite reduction and creative telescoping for hyperexponential functions[END_REF] presented a reduction algorithm that decomposes a hyperexponential function into the sum of an integrable one and a non-integrable one in a unique way. On the other hand, a q-discrete analogue is presented in [START_REF] Chen | Applicability of the q-analogue of Zeilberger's algorithm[END_REF]. When H is a rational function, additive decompositions are more classical; they were presented by [START_REF] Ostrogradskiȋ | De l'intégration des fractions rationnelles[END_REF] and [START_REF] Hermite | Sur l'intégration des fractions rationnelles[END_REF] for the continuous case, and by [START_REF] Abramov | The rational component of the solution of a first order linear recurrence relation with rational right hand side[END_REF][START_REF] Abramov | Indefinite sums of rational functions[END_REF] for the discrete and q-discrete cases.

For a mixed term h over (k(x, y), (θ x , θ y )), we can perform three kinds of additive decompositions with respect to y according to the choice of θ y . We recall now the notions related to additive decompositions. Definition 4.3. Let K be a field of characteristic zero, and a be a nonzero polynomial in K [z]. Denote by δ z , σ z , and τ z the usual derivation, shift and q-shift operators with respect to z on K(z), respectively.

(i) a is said to be δ z -free, or squarefree, if gcd (a, δ z (a)) = 1.

(ii) a is said to be σ z -free, or shift-free, if gcd(a, σ i z (a)) = 1 for every nonzero integer i. (iii) Let a = z m ã with ã ∈ K[z] and z ∤ ã. Then a is said to be τ z -free, or q-shift-free, if gcd ã, τ i z (ã) = 1 for every nonzero integer i. Moreover, let f be a nonzero rational function in K(z). Set a = num(f ) and b = den(f ).

(iv) f is said to be δ z -reduced if gcd(b, a -iδ z (b)) = 1 for all i ∈ Z; (v) f is said to be σ z -reduced if gcd(b, σ i z (a)) = 1 for all i ∈ Z; and (vi) f is said to be τ z -reduced if gcd(b, τ i z (a)) = 1 for all i ∈ Z.
A univariate polynomial is δ z -free if and only if it has no multiple root. It is σ z -free if and only if its distinct roots do not differ by an integer additively; and it is τ z -free if and only if its distinct nonzero roots do not differ by a power of q multiplicatively.

A univariate rational function is δ z -reduced if it has no integral residue at any simple pole by Lemma 2 in [START_REF] Geddes | Differential rational normal forms and a reduction algorithm for hyperexponential functions[END_REF]. It is σ z -reduced (resp. τ z -reduced) if any root of the numerator and any root of the denominator do not differ by an integer additively (resp. a power of q multiplicatively).

For a polynomial p in k[x, y], we say that it is θ y -free when p is θ y -free as a polynomial in y over k(x). The same convention applies to θ y -reduced functions.

Finally, we define an additive decomposition in the setting of mixed terms.

Definition 4.4. Let h be a mixed term over (k(x, y), (θ x , θ y )). Assume that

h = ∆ y (h 1 ) + h 2 (6)
where h 1 is a mixed term, and h 2 is equal to either zero or a mixed term. We call (6) an additive decomposition of h with respect to ∂ y if there exist r ∈ k(x, y) with a θ y -free denominator, and compatible rational functions u, v ∈ k(x, y) with v being θ y -reduced such that

h 2 ∈ rH(u, v). (7)
The additive decomposition with respect to ∂ x is defined likewise.

We remark that the additive decompositions given in Definition 4.4 are more weakly constrained than those in [START_REF] Abramov | Minimal decomposition of indefinite hypergeometric sums[END_REF] and [START_REF] Geddes | Differential rational normal forms and a reduction algorithm for hyperexponential functions[END_REF]. For example, h 2 is not necessarily equal to zero when h is an exact term.

Split and spread polynomials

Split polynomials defined in [START_REF] Chen | Applications of Differential-Difference Algebra to Creative Telescoping[END_REF]) play the same role as integer-linear polynomials in the difference case. A polynomial p ∈ k[x, y] is said to be split if it is of the form p 1 (x)p 2 (y) with p 1 ∈ k[x] and p 2 ∈ k[y]. A rational function r ∈ k(x, y) is said to be split if it is of the form r 1 (x)r 2 (y) with r 1 ∈ k(x) and r 2 ∈ k(y).

A rational function f ∈ k(x, y) can always be decomposed as f 1 (x)f 2 (y)f 3 (x, y), where f 1 ∈ k(x), f 2 ∈ k(y) and neither num(f 3 ) nor den(f 3 ) have split factors except constants. We call f 1 f 2 and f 3 the split and non-split parts of f , respectively. Both are defined up to a nonzero multiplicative constant.

Remark 4.5. For p ∈ k[x, y], one may decide whether it is split by comparing all monic normalized coefficients of p with respect to y. More precisely, p is split if and only if all those are equal. In an implementation, one would abort as soon as a mismatch is found.

Remark 4.6. A nontrivial and nonsplit polynomial p ∈ k[x, y] has at least two terms. Since q is not a root of unity, τ i y (p) and τ j y (p) are coprime for all i, j ∈ Z with i = j if p is irreducible.

The notion of spread polynomials is introduced by [START_REF] Abramov | When does Zeilberger's algorithm succeed?[END_REF] for establishing his criterion on the existence of telescopers for hypergeometric terms. We extend this notion to the mixed setting so as to connect split rational functions with exact terms. Definition 4.7. Let K be a field of characteristic zero, and δ z , σ z , and τ z be the usual derivation, shift and q-shift operators on K[z], respectively. For a polynomial a ∈ K[z] of positive degree, we say that:

(i) a is δ z -spread if every nontrivial irreducible factor of a has multiplicity > 1; (ii) a is σ z -spread if, for every nontrivial irreducible factor b of a, σ i z (b) | a for some nonzero integer i; (iii) a is τ z -spread if, for every nontrivial irreducible factor b of a with z ∤ b, τ i z (b) | a for some nonzero integer i.
Clearly, δ z -spread polynomials are not δ z -free. And there are polynomials that are neither δ z -spread nor δ z -free. The same observations hold for σ z -spread polynomials and for τ z -spread polynomials that have at least two terms.

For a polynomial p in k[x, y] of positive degree in y, we say that it is θ y -spread when p is θ y -spread as a polynomial in y over k(x). Case (iii) of Definition 4.7 restricts the factors b in a way that makes no constraint on the multiplicity of z in a. This is because we shall only consider τ y -spread non-split polynomials in what follows.

Next, we present a mixed analogue of Theorem 8 in [START_REF] Abramov | When does Zeilberger's algorithm succeed?[END_REF], which is the basis of a key argument in the proof of the main conclusion in Section 5.

Proof. Since h is exact, there exists a mixed term g such that h = ∆ y (g). By Remark 3.3, g is similar to h, that is, g ∈ rH(u, v) for some r ∈ k(x, y). Accordingly,

f H(u, v) = ∆ y (rH(u, v)). (8)
Let p be a non-split irreducible factor of w with deg x p > 0 and deg y p > 0.

(i) Assume that θ y = δ y and den(v) is split. By (8), there exists c ∈ k \ {0} such that cf = δ y (r) + rv.

Since den(v) is split and p divides den(f ), p is an irreducible factor of den(r). So there exists an integer i > 1 such that p i | den(δ y (r)) and p i ∤ den(r). Therefore, p i ∤ den(rv). It follows that p i | den(f ), and, thus, p i | w. This proves part (i).

(ii) Assume that θ y = σ y and v is split. By (8), there exists c ∈ k \ {0} such that

cf = vσ y (r) -r. ( 9
)
Since v is split, p | den(r) or p | den(σ y (r)). So, the set

L := {ℓ ∈ Z such that σ ℓ y (p) | den(r)
} is nonempty (consider 0 ∈ L and -1 ∈ L, respectively) and finite. Therefore, there exist i, j ∈ Z with i > j such that i -1 ∈ L, i ∈ L, j -1 ∈ L, j ∈ L, that is σ i y (p) | den(σ y (r)), σ i y (p) ∤ den(r), σ j y (p) ∤ den(σ y (r)), and σ j y (p) | den(r). It follows from ( 9) that both σ i y (p) and σ j y (p) divide den(f ). Since i = j, we can find ℓ = 0 in {i, j}. Then, both p and σ ℓ y (p) divide w. So w is σ y -spread, and part (ii) holds. The case θ y = τ y can be handled in the same vein by Remark 4.6 ✷

Structural decompositions and proper terms

By the Ore-Sato theorem in [START_REF] Ore | Sur la forme des fonctions hypergéométriques de plusieurs variables[END_REF][START_REF] Petkovšek | Theory of prehomogeneous vector spaces (algebraic part)-the English translation of Sato's lecture from Shintani's note[END_REF], every bivariate hypergeometric term is the product of a rational function and a factorial term. Using this multiplicative decomposition, one can define the notion of proper hypergeometric terms. Wilf and Zeilberger (1992a) show that every proper hypergeometric term has a telescoper. In this section, we apply a mixed analogue of the Ore-Sato theorem in [START_REF] Chen | On the structure of compatible rational functions[END_REF] to define the notion of proper mixed terms.

Let (θ x , θ y ) be a mixed pair of operators in Θ. For a pair (a, b) of compatible rational functions in k(x, y) × k(x, y), we obtain the conclusions listed in Table 4.9 by Proposition 6.1 in [START_REF] Chen | On the structure of compatible rational functions[END_REF]. In fact, the conclusions can also be derived from Lemmas 3.1, 3.2 and 3.3 in [START_REF] Chen | On the structure of compatible rational functions[END_REF], because we are only concerned with bivariate mixed terms over (k(x, y), (θ x , θ y )).

Example 4.10. Let h ∈ H(a, b) be a mixed term over (k(x, y), (θ x , θ y )).

If (θ x , θ y ) = (δ x , σ y ), then there exist f ∈ k(x, y), β ∈ k(x), a univariate hyperexponential function E(x), and a univariate hypergeometric term G(y) such that

h = f (x, y)β(x) y E(x)G(y)
by Proposition 6.1 in [START_REF] Chen | On the structure of compatible rational functions[END_REF]. Setting α(x) to be δ x (E)/E and γ(y) to be σ y (G)/G, we see that part 1 in Table 4.9 holds by Lemma 2.10 (i). (θx, θy) = (δx, σy) ∃ f ∈ k(x, y), α, β ∈ k(x), and γ ∈ k(y) such that

H(a, b) = f H y δx(β) β + α, β • γ .

2.

(θx, θy) = (σx, δy) ∃ f ∈ k(x, y), α, β ∈ k(y), and γ ∈ k(x) such that Table 4.9. Multiplicative decompositions of mixed terms

H(a, b) = f H β • γ, x δy (β) β + α .
If (θ x , θ y ) = (σ x , τ y ), then there exist f ∈ k(x, y), α ∈ k(x) and β ∈ k(y) such that a = σ x (f ) f α and b = τ y (f ) f β
by Lemma 3.3 in [START_REF] Chen | On the structure of compatible rational functions[END_REF]. Part 3.3 in Table 4.9 holds by Lemma 2.10 (iii).

The decomposition of sets in Table 4.9 induces a decomposition of mixed terms.

Definition 4.11. Given a mixed term h ∈ H(a, b), the product f h ′ of a rational function f ∈ k(x, y) and a mixed term h ′ is called a structural decomposition of h if h = f h ′ and if h ′ has certificates given by the rational functions α, β, γ in Table 4.9 for the same f .

A mixed term may have more than one structural decompositions, as illustrated below.

Example 4.12. Let h = x(x + y)x y exp(x)Γ(y) be a mixed term over (k(x, y), (δ x , σ y )).

Then the two certificates of h are, respectively,

a := δ x (h) h = x 2 + 2xy + y 2 + 2x + y x(x + y) and b := σ y (h) h = xy(x + y + 1)
x + y .

The mixed term h has at least two structural decompositions h = f i h i with i ∈ {1, 2},

f i ∈ k(x, y) and h i ∈ H y δ x (β i ) β i + α i , β i • γ i ,
where f 1 = x + y, β 1 = x, α 1 = (x + 1)/x, and γ 1 = y; and f 2 = x(x + y), β 2 = x/2, α 2 = 1, and γ 2 = 2y.

The next definition is fundamental for our existence criterion.

Definition 4.13. Let h be a mixed term over (k(x, y), (θ x , θ y )). We say that h is a proper term if there exists a structural decomposition h = f h ′ for which den(f ) is split.

Two questions concern this definition of proper terms. First, defining properness by the existence of some structural decomposition with a prefactor f whose denominator is split raises the question whether any structural decomposition of a given proper h will have the property witnessing properness. In order to derive a properness test, it is indeed of importance to understand if any structural decomposition will do, or if one needs to consider a restricted type of structural decompositions. Second, a decomposition of the form (7) in Definition 4.4 can be computed easily, but it is not necessarily a structural decomposition. This raises a question of algorithmic importance, namely, to what extend one could decide properness without appealing to any structural decomposition.

In the rest of this subsection, we answer these two questions.

Lemma 4.14. Let f and r be two nonzero rational functions in k(x, y).

(i) If the denominator of θ(f )/f is split for some θ ∈ {δ x , δ y }, so is f . (ii) If θ(f )/f is split for some θ ∈ {σ x , σ y , τ x , τ y }, so is f . (iii) If both den(r) and f /r are split, so is den(f ).

Proof. (i) It is immediate from the logarithmic derivative identity.

(ii) Suppose that f is not split. Then there exists a nontrivial non-split irreducible polynomial p dividing den(f )•num(f ). Assume further that σ i x (p) does not divide den(f )•num(f ) for all i > 0. Then σ x (p) is a factor of either the numerator or the denominator of the rational function σ x (f )/f . Thus, σ x (f )/f is not split, a contradiction. The same argument applies to τ x (f )/f by Remark 4.6. Likewise, part (ii) holds for θ ∈ {σ y , τ y }.

(iii) Note that f r = num(f ) • den(r) den(f ) • num(r) .
Suppose for a contradiction that den(f ) has a non-split irreducible factor p. Since f /r is split, p divides num(f ) • den(r). Since den(f ) and num(f ) are coprime, p divides den(r), a contradiction to the assumption that den(r) is split. ✷ Proposition 4.15. Let h be a mixed term over (k(x, y), (θ x , θ y )). Assume h ∈ rH(u, v) for some r, u, v ∈ k(x, y) and that den(r) is split. Then the following statements hold: (i) Assume that θ x = δ x . If den(u) or v is split, then h is proper.

(ii) Assume that θ y = δ y . If u or den(v) is split, then h is proper.

(iii) Assume that (θ x , θ y ) = (σ x , τ y ) or (θ x , θ y ) = (τ x , σ y ). If u or v is split, then h is proper.

Proof. (i) We assume that (θ x , θ y ) = (δ x , σ y ). For any structural decomposition h = f h ′ given by f ∈ k(x, y), α, β ∈ k(x) and γ ∈ k(y) as in part 1 in Table 4.9, Lemma 2.10 (i) implies that

δ x (h) h = δ x (f ) f + y δ x (β) β + α and σ y (h) h = σ y (f ) f βγ.
which, together with the assumption h ∈ rH(u, v), further implies that

δ x (f ) f + y δ x (β) β + α = δ x (r) r + u and σ y (f ) f βγ = σ y (r) r v. ( 10
)
In view of Definition 4.13 and the structural decomposition h = f h ′ , it remains to show that den(f ) is split. It suffices to show that f /r is split by Lemma 4.14 (iii) and by the hypothesis that den(r) is split.

Case 1. Assume that den(u) is split. By the first equality in (10),

δ x (f /r) f /r = u -y δ x (β) β -α,
which, together with the splitness of α, β and den(u), implies that the denominator of δ x (f /r)/(f /r) is split. Thus, f /r is split by Lemma 4.14 (i).

Case 2. Assume that v is split. By the second equality in (10),

σ y (f /r) f /r = v βγ ,
which, together with the splitness of β, γ and v, implies that σ y (f /r)/(f /r) is split. Thus, f /r is split by Lemma 4.14 (ii).

The case (θ x , θ y ) = (δ x , τ y ) can be handled in the same vein by part 3.1 of Table 4.9 and Remark 4.6.

(ii) It can be proved by switching x with y in (i).

(iii) It can be proved by a similar argument used for Case 2 in part (i), because, by parts 3.1 and 3.2 of Table 4.9, (10) becomes

θ x (f ) f α = θ x (r) r u and θ y (f ) f β = θ y (r) r v.
for some α ∈ k(x) and β ∈ k(y). ✷

Remark that Proposition 4.15 assumes h = r h for h ∈ H(u, v) with conditions in each of the cases (i), (ii), and (iii) that are satisfied if h = r h is a structural decomposition. The proof establishes that for any structural decomposition h = f h ′ and f, α, β, γ defined as in the right-hand column of Table 4.9, den(f ) is split whenever den(r) is split. As a consequence, given a mixed term h attested to be proper by a structural decomposition h = f 1 h 1 in which den(f 1 ) is split, then den(f 2 ) is split in any other structural decomposition h = f 2 h 2 . Thus, the notion of proper terms is independent of the structual decomposition under consideration. So Proposition 4.15 answers the first question.

To answer the second question, we connect split polynomials and reduced rational functions via Table 4.9, as done in the next lemma. Observe before the proof that cases (i) and (ii) are not symmetric, owing to the hypothesis on v, and similarly with the two subcases of (iii).

Lemma 4.16. Let u, v ∈ k(x, y) be compatible with respect to a mixed pair (θ x , θ y ) of operators. Assume that v is θ y -reduced.

(i) If θ x = δ x , then both den(u) and v are split. (ii) If θ y = δ y , then both u and den(v) are split. (iii) If (θ x , θ y ) is equal to either (σ x , τ y ) or (τ x , σ y ), then both u and v are split.

Proof. There exist f, u ′ , v ′ ∈ k(x, y) such that H(u, v) = f H(u ′ , v ′ ), ( 11
)
where f ∈ k(x, y), and u ′ , v ′ are given by univariate rational functions α, β, γ in Table 4.9.

(i) First, we set (θ x , θ y ) = (δ x , σ y ). By part 1 of Table 4.9 and Lemma 2.10 (i), ( 11) can be rewritten as

u = δ x (f ) f + y δ x (β) β + α and v = σ y (f ) f βγ. (12)
We claim that f is split. Suppose on the contrary that f is non-split. Then there exists a non-split irreducible polynomial p ∈ k[x, y] dividing den(f ) • num(f ). We only treat the case of p dividing num(f ); the case of p dividing den(f ) would be dealt with similarly. Then there exist two integers i and j with i ≤ j such that both σ i y (p) and σ j y (p) divide num(f ), but σ ℓ y (p) does not divide num(f ) for all ℓ with ℓ < i or ℓ > j. It follows from the second equality in ( 12) and the splitness of βγ that σ i y (p) divides den(v) and σ j+1 y (p) divides num(v). Hence, v is not σ y -reduced, a contradiction. This proves our claim that f is split, which, together with (12), implies that v and den(u) are also split.

Second, we set (θ x , θ y ) = (δ x , τ y ). Then ( 11) becomes

u = δ x (f ) f + α and v = σ y (f ) f β for some f ∈ k(x, y), α ∈ k(x) and β ∈ k(y).
by part 3.1 in Table 4.9 and Lemma 2.10 (i). It follows from the same argument as given above that both den(u) and v are split.

(ii) Set (θ x , θ y ) = (σ x , δ y ). Then (11) becomes

u = σ x (f ) f βγ and v = δ y (f ) f + x δ y (β) β + α (13)
by part 2 of Table 4.9 and Lemma 2.10 (ii). Since v is δ y -reduced, every irreducible factor of den(f ) [START_REF] Geddes | Differential rational normal forms and a reduction algorithm for hyperexponential functions[END_REF]) and the second equality in (13). So f is again split. Both u and den(v) are split by ( 13).

• num(f ) is either in k[x] or in k[y] by Lemma 2 in
Consider the case (θ x , θ y ) = (τ x , δ y ). Then (11) becomes

u = σ x (f ) f α and v = δ y (f ) f + β for some f ∈ k(x, y), α ∈ k(x) and β ∈ k(y).
by part 3.2 of Table 4.9 and Lemma 2.10 (ii). The same argument used in the above case implies that both u and den(v) are split.

(iii) We only treat the case (θ x , θ y ) = (σ x , τ y ); the case (θ x , θ y ) = (τ x , σ y ) would be dealt with similarly. By part 3.3 in Table 4.9 and Lemma 2.10 (iii), (11) becomes

u = σ x (f ) f α and v = τ y (f ) f β. (14)
The lemma follows from a similar argument used for the first case in part (i). ✷

The last proposition answers the second question by providing a properness criterion that requires considering no structural decomposition. Proposition 4.17. Let h be a mixed term over (k(x, y), (θ x , θ y )). Assume h ∈ rH(u, v) for some r, u, v ∈ k(x, y). If den(r) is split and v is θ y -reduced, then h is proper.

Proof. If θ y = δ y , then den(v) is split by Lemma 4.16 (ii). It follows from Proposition 4.15 (ii) that h is proper. If θ y ∈ {σ y , τ y }, then v is split by Lemma 4.16 (i) and (iii). Thus, h is proper by Proposition 4.15 (i) and (iii). ✷ By the above proposition, the mixed term h 2 in the additive decomposition ( 6) is proper if r in (7) has a split denominator.

A necessary condition on the existence of telescopers

In the rest of this paper, we provide a necessary and sufficient condition on the existence of telescopers for mixed terms. Recall that a mixed term is telescopable if it has a telescoper. The goal of this section is to prove that a telescopable term can be written as the sum of an exact term and a proper one. More precisely, we are going to prove Theorem 5.1. Let h be a mixed term over (k(x, y), (θ x , θ y )). Let h = ∆ y (h 1 ) + h 2 be an additive decomposition with respect to ∂ y . If h is telescopable of type (∂ x , ∂ y ), then h 2 is either zero or proper.

As pointed out in Remark 3.2, a telescopable term of type (∂ x , ∂ y ) is not necessarily telescopable of type (∂ y , ∂ x ). So there are six mixed pairs of operators to be considered. We prove Theorem 5.1 for the continuous-discrete and continuous-q-discrete cases in §5.1, and for the discrete-q-discrete case in §5.2.

Owing to the length and case distinction of our proof, we make a notational convention.

Convention 5.2. Assume that h 2 given by the additive decomposition in Theorem 5.1 is nonzero. By Definition 4.4, there exist r, u, v ∈ k(x, y) such that (i) den(r) is θ y -free;

(ii) u and v are compatible with respect to (θ x , θ y ), and

v is θ y -reduced; (iii) h 2 belongs to rH(u, v). (iv) Assume further that L is a telescoper of type (∂ x , ∂ y ) for h. (v) Set L = ρ i=0 e i ∂ i x ∈ k(x) ∂ x
, where e i ∈ k(x) and e ρ = 0, (15)

f = ρ i=0 u i θ i x (r), (16)
where

u i =    the coefficient of D i x in ρ i=0 e i (D x + u) i if θ x = δ x ; e i i-1 j=0 θ j x (u) if θ x = σ x or θ x = τ x .
By Examples 2.13 and 2.14 there exists a mixed term g ∈ H(u, v) such that

L(h 2 ) = f g. (17)
(vi) Set w to be the non-split part of den(f ).

The strategy for our proof is as follows. By the above convention and Proposition 4.17, it suffices to prove that den(r) is split. Suppose on the contrary that den(r) is not split. We show that w is neither in k nor θ y -spread by ( 16) and the θ y -freeness of den(r). On the other hand, the exactness of f g with respect to ∂ y enables us to prove that w is either in k or θ y -spread by the next lemma. This contradiction asserts that den(r) has to be split.

Lemma 5.3. With Convention 5.2, we assume that w is not in k. Then w is θ y -spread.

Proof. Note that f is nonzero, because w is not in k. Hence, f g is nonzero, which, together with Convention 5.2 (iv) and equation ( 17), implies that f g is an exact term.

By Convention 5.2 (ii), v is θ y -reduced. If θ y = δ y , then den(v) is split by Lemma 4.16 (ii). It follows from Proposition 4.8 (i) applied to the exact term f g that w is δ y -spread. If θ y ∈ {σ y , τ y }, then v is split by Lemma 4.16 (i) and (iii). Thus, w is θ y -spread by Proposition 4.8 (ii). ✷ 5.1. Continuous-discrete and continuous-q-discrete cases

In this section, we prove that Theorem 5.1 holds for a mixed pair of operators, in which either θ x = δ x or θ y = δ y . By Convention 5.2 (ii), (iii) and Proposition 4.17, it suffices to show that den(r) is split. 15). The u i in ( 16) have split denominators, because den(u i ) divides a power of den(u), which is split by Lemma 4.16 (i). Moreover, Leibniz's rule for δ x implies that u ρ = e ρ , which is a univariate rational function of x by ( 15).

Case (θ x , θ y ) = (δ x , σ y ). The telescoper L for h is of type (D x , S y ). So ∂ x = D x in (
Suppose for a contradiction that den(r) is not split. Then there exists a non-split irreducible polynomial p ∈ k[x, y] such that p | den(r). Assume that m is the multiplicity of p in den(r). Then the multiplicity of p in den(u i δ i x (r)) is less than or equal to m + i, because den(u i ) is split. In particular, the multiplicity of p in den (u ρ δ ρ x (r)) is equal to m + ρ, because u ρ ∈ k(x). By ( 16), p is an irreducible factor of den(f ). Accordingly, the non-split part w of den(f ) is nontrivial. Since all the den(u i ) are split, w divides a power of den(r) by ( 16). Since den(r) is σ y -free, so is w. Hence, w is neither in k nor σ y -spread, a contradiction to Lemma 5.3. Therefore, den(r) is split.

Case (θ x , θ y ) = (σ x , δ y ). The telescoper L for h is of type (S x , D y ). So ∂ x = S x in (15). The u i in ( 16) are all split, because u is split by Lemma 4.16 (ii). In particular, u ρ is nonzero because e ρ is nonzero.

Suppose for a contradiction that den(r) is not split. Then there exists a non-split irreducible polynomial p ∈ k[x, y] such that p | den(r) and σ i

x (p) ∤ den(r) for all i > 0. Since den(r) is δ y -free, p is a nontrivial simple factor of den(r) in k(x) [y]. Since u ρ is split, σ ρ

x (p) is a simple and irreducible factor of den (u ρ σ ρ x (r)). Since σ i x (p) ∤ den(r) for any i > 0, σ ρ x (p) is not an irreducible factor of den u j σ j x (r) for any j with 0 ≤ j ≤ ρ -1. It follows from ( 16) that σ ρ

x (p) is a simple factor of w. So w is neither in k nor δ y -spread, a contradiction to Lemma 5.3. Therefore, den(r) is split.

By Remark 4.6, we can replace σ x and σ y by τ x and τ y in the above proof, respectively. This completes the proof of Theorem 5.1 in both continuous-discrete and continuous-qdiscrete cases.

Discrete-q-discrete case

For the case in which either (θ x , θ y ) = (σ x , τ y ) or (θ x , θ y ) = (τ x , σ y ), we need not only similar arguments used in §5.1, but also two mixed analogues of the results given by Abramov and Petkovsek (2002a) and by [START_REF] Abramov | When does Zeilberger's algorithm succeed?[END_REF], respectively. Such analogues (i) If ∂ x = T x , and den(r) is σ y -free, then the non-split part of the denominator of L(r) is neither in k nor σ y -spread. (ii) If ∂ x = S x , and den(r) is τ y -free, then the non-split part of the denominator of L(r) is neither in k nor τ y -spread.

Proof. Set a = num(r), b = den(r) and L = ρ i=0 u i ∂ i x , where u 0 , u 1 , . . . , u ρ ∈ k(x, y) are split and u ρ is nonzero.

(i) Applying L to r, we have that

L(r) = ρ i=0 u i τ i x a b . (18)
There exists a non-split and irreducible polynomial p such that p divides b but τ µ x (p) does not divide b for any positive integer µ > 0, because b is not split. It follows that the irreducible polynomial τ ρ

x (p) divides the denominator of τ ρ x (a/b) but does not divide that of τ i x (a/b) for any i with 0 ≤ i ≤ ρ -1. Thus, τ ρ x (p) divides the non-split part B of den(L(r)). In particular, B does not belong to k.

It remains to prove that B is not σ y -spread. Suppose on the contrary that B is σ yspread. Then there exists j 0 ∈ Z with j 0 = 0 such that σ j0 y τ ρ x (p) | B. Furthermore, we have that B | ρ i=0 τ i

x (b) by ( 18) and the splitness of the u i . The two divisibilities and irreducibility of p imply that there exists ℓ 0 in {0, . . . , ρ} such that σ j0 y τ ρ x (p) | τ ℓ0 x (b). Note that ℓ 0 = ρ, for otherwise, σ j0 y (p) would divide b, which, together with p | b, would imply that b is not shift-free, a contradiction. Therefore, ℓ 0 < ρ. Since σ j0 y τ ρ-ℓ0

x (p) | b, there exists a non-negative integer i 0 such that

σ j0 y τ ρ-ℓ0+i0 x (p) | b but σ j0 y τ ρ-ℓ0+i0+µ x (p) ∤ b
for any positive integer µ. It follows from ρ -ℓ 0 > 0 that ρ -ℓ 0 + i 0 > 0.

Repeating the above process for the irreducible factor σ j0 y τ ρ-ℓ0+i0

x (p) instead of the factor p, we can find j 1 ∈ Z with j 1 = 0, i 1 ∈ N and ℓ 1 ∈ {0, . . . , ρ -1} such that ρℓ 1 + i 1 > 0 and

σ j0+•••+jn y τ (ρ-ℓ0+i0)+•••+(ρ-ℓn+in) x (p) = cσ j0+•••+jm y τ (ρ-ℓ0+i0)+•••+(ρ-ℓm+im) x (p)
for some c ∈ k. This implies that Lemma 5.4 (ii), p is split, a contradiction to the assumption that p is non-split.

σ -jn+1-•••-jm y τ -(ρ-ℓn+1+in+1)-•••-(ρ-ℓm+im) x (p) = cp. Note that (ρ -ℓ n+1 + i n+1 ) + • • • + (ρ -ℓ m + i m ) = 0. By
(ii) It follows from the same argument given as above, in which τ x and σ y are replaced by σ x and τ y , respectively. ✷

We are ready to prove that Theorem 5.1 holds for the discrete-q-discrete cases.

Case (θ x , θ y ) = (τ x , σ y ). With Convention 5.2, suppose for a contradiction that den(r) is not split. Note that the u i in ( 16) are split by Lemma 4.16 (iii). Thus, Lemma 5.5 (i) implies that the non-split part w of den(f ) is neither in k nor σ y -spread, a contradiction to Lemma 5.3. We conclude that den(r) is split.

Case (θ x , θ y ) = (σ x , τ y ). The assertion can be proved by a similar argument, in which Lemma 5.5 (ii) is applied instead of Lemma 5.5 (i).

We have completed a proof of Theorem 5.1 for all the six mixed pairs of operators.

Determining the existence of telescopers

In this section, we first establish a criterion on the existence of telescopers for mixed terms in §6.1, then present an algorithm with a few examples in §6.2.

A criterion on the existence of telescopers

In this section, we prove the converse of Theorem 5.1, leading to the criterion of Theorem 6.3. Our proof is based on the following theorem. Theorem 6.1. A proper term over (k(x, y), (θ x , θ y )) is telescopable of type (∂ x , ∂ y ).

In fact, the above theorem is part of the fundamental theorem in (Wilf and Zeilberger, 1992a). In their paper, Wilf and Zeilberger present an elementary proof of the existence of telescopers for proper hypergeometric terms and indicate that their argument should be applicable to the mixed setting. For the sake of completeness, we elaborate a proof of Theorem 6.1 in the appendix of this paper.

Next, we show the converse of Theorem 5.1.

Lemma 6.2. Let h be a mixed term over (k(x, y), (θ x , θ y )). Let h = ∆ y (h 1 ) + h 2 be an additive decomposition with respect to ∂ y . If h 2 is either zero or proper, then h is telescopable of type (∂ x , ∂ y ).

Proof. If h 2 is zero, then 1 is a telescoper of h. Therefore, we assume that h 2 is a proper mixed term. By Theorem 6.1 below, h 2 is telescopable of type (∂ x , ∂ y ). We claim that that so is h, which ends the proof of the lemma.

Because h 2 has a telescoper L of type (∂ x , ∂ y ), there exists indeed a mixed term g such that L(h 2 ) = ∆ y (g). Note that

L∆ y = ∆ y L, because L ∈ k[x] ∂ x and ∆ y ∈ k ∂ y . It follows that L(h) = L∆ y (h 1 ) + L(h 2 ) = ∆ y (L(h 1 )) + ∆ y (g). (19)
If L(h) = 0, then L(h) = ∆ y (1) and L is a telescoper for h; if either ∆ y (L(h 1 )) = 0 or ∆ y (g) = 0, then L is a telescoper for h by (19). Otherwise, the three mixed terms L(h), ∆ y (L(h 1 )) and ∆ y (g) are similar to each other by Remark 2.12. Therefore, L(h 1 ) + g is either a mixed term or zero. Set g ′ to be the sum if it is nonzero. Otherwise, set g

′ = 1. Then L(h) = ∆ y (g ′ ), that is, h is telescopable of type (∂ x , ∂ y ). ✷
As both Theorem 5.1 and its converse Lemma 6.2 hold, we obtain a criterion on the existence of telescopers for mixed terms, which is the main result of this article. Theorem 6.3. Let h be a mixed term over (k(x, y), (θ x , θ y )). Assume that h = ∆ y (h 1 ) + h 2 is an additive decomposition of h. Then h has a telescoper of type (∂ x , ∂ y ) if and only if h 2 is either zero or a proper mixed term.

Algorithm and Examples

For a given mixed term, we can decide the existence of telescopers by Theorem 6.3. First, we use the algorithms in (Abramov and Petkovsek, 2002b), [START_REF] Geddes | Differential rational normal forms and a reduction algorithm for hyperexponential functions[END_REF], and [START_REF] Chen | Applicability of the q-analogue of Zeilberger's algorithm[END_REF] to perform the respective additive decompositions to obtain (6). Second, we test whether the denominator of r in ( 7) is split by Remark 4.5. The decision procedure is given in Table 6.6.

Example 6.4. It is possible that a mixed term has a telescoper of type (S x , D y ) but no telescoper of type (D x , S y ) or (D x , T y ). Consider the rational function

h = 1 (x + y) 2 .
Applying Hermite reduction to h with respect to δ y yields h = D y (-1/(x + y)) , which implies that 1 is a telescoper of type (S x , D y ) for h. Note that h = ∆ y (1) + h is an additive decomposition when θ y = σ y or θ y = τ y , because den(h) = (x + y)2 is both shift-free and q-shift-free with respect to y. But h is not proper, because x + y is not split. Hence, h has no telescoper of type (D x , S y ) and (D x , T y ).

Similarly, consider the rational function

h = 1 (x + y)(x + y + 1)
.

Since h = (S y -1)(-1/(x + y)), 1 is a telescoper of type (D x , S y ) for h. However, h has no telescoper of type (S x , D y ) or (T x , D y ), because (x + y)(x + y + 1) is squarefree with respect to δ y and it is not split.

Example 6.5. 2 Consider the rational function

h = x 5 + 2yx 3 + xy 2 -y (y + x 2 ) 2 y .
An additive decomposition of h with respect to D y is

h = D y 1 y + x 2 + x y .
Since y is split, x/y is proper. So h is telescopable of the type (S x , Dy) by Theorem 6.3. An additive decomposition of h with respect to ∆ y is h = ∆ y (1) + h.

Since the denominator (y +x 2 ) 2 y of h is not split, h is not proper. So h is not telescopable of type (D x , S y ) by Theorem 6.3.

Algorithm IsTelescopable

Input: a mixed term h ∈ H(a, b) over (k(x, y), (θx, θy)).

Output: true, if h has a telescoper of type (θx, θy); false, otherwise.

(1) Compute an additive decomposition of h with respect to θy and get h = ∆y(h1) + rg, where r ∈ k(x, y) and g ∈ H(u, v) are as given by ( 6) and ( 7) in Definition 4.4.

(2) Compute the primitive part p of den(r) with respect to y.

(3) If p is in k[y], then return true, otherwise, return false. As we mentioned before, properness is only a sufficient condition for the existence of telescopers. The following example illustrates this fact.

Example 6.7. Consider the mixed term over (k(x, y), (σ x , δ y ))

h = -y + 2xy + 2x 2 (x + y) 2 x • y x • e -y .
A structural decomposition of h is given by α = -1, β = y, γ = 1, and f = h/(y x e -y ).

Note that the denominator of f is equal to x(x + y) 2 , which is not split. So h is not proper. But h has a telescoper of type (S x , D y ) since it can be decomposed into h = D y 1 y(x + y)

• y x • e -y + y x-1 • e -y , where y x-1 • e -y is proper, because the rational function in the corresponding structural decomposition is 1, and therefore its denominator is split. Similarly, h also has a telescoper of type (T x , D y ).

The last example presents another application of Theorem 6.3.

Example 6.8. Let f = 1/(x + y) s , where s is any fixed positive integer. Note that the denominator of f is non-split and shift-free with respect to σ y . By Theorem 6.3, there is no linear differential operator L(x, D x ) ∈ k(x) D x and g ∈ k(x, y) such that L(x, D x )(f ) = ∆ y (g), which, together with Proposition 3.1 in [START_REF] Hardouin | Differential Galois theory of linear difference equations[END_REF] and the descent argument similar to that given in the proof of Corollary 3.2 in [START_REF] Hardouin | Differential Galois theory of linear difference equations[END_REF] Proof. The proof is reminiscent of the linear algebra argument given by [START_REF] Lipshitz | The diagonal of a D-finite power series is D-finite[END_REF]; however, it is based on linear algebra and filtrations over k(x) instead of k. Let µ be the maximum of the degrees in y of the numerators and denominators of the two certificates of h. Moreover, let a and b be the denominators of the θ x -and θ y -certificates, respectively. Assume that (θ x , θ y ) = (δ x , σ y ). Since θ y is a shift operator, the θ y -certificate of h has a split denominator, that is, b is split. = wh a i j-1 ℓ=0 σ ℓ y (b 2 ) for some w ∈ k(x)[y] with deg y (w) ≤ (i + j)µ.

If i + j ≤ N , then D i x S j y (h) is an element of the k(x)-linear space

W N = span k(x) y m h a N N -1 ℓ=0 σ ℓ y (b 2 ) | m ≤ 2µN . (20)
Accordingly, there is a well-defined k(x)-linear map φ N from

F N = span k(x) {D i x S j y | i + j ≤ N }
to W N that sends L to L(h) for all L ∈ F N . Since the dimension of F N over k(x) is N +2 2 while that of W N is 2µN + 1, the kernel of φ N is nontrivial when N is sufficiently large.

Let A be a nonzero element of ker(φ N ) whose degree in S y is minimal. Since A is free of y, A = L + (S y -1)N for some L ∈ k(x) D x and N ∈ k(x, y) D x , S y . Accordingly, L is nonzero by the same argument used by Graham et al. (1994, §5.8, p. 241) 3 (see also (Petkovšek et al., 1996, §6.2, p. 108)). Since A(h) = 0, L(h) = (S y -1)(N (h)). So L is a telescoper of type (D x , S y ) for h.

For the case (θ x , θ y ) = (σ x , δ y ), we can replace the linear space W N in (20) by

span k(x) y m h b N 2 N -1 ℓ=0 σ ℓ x (a) | m ≤ 2µN ,
and prove that h is telescopable of type (S x , D y ) by a similar argument. ✷ Remark 7.2. With the map from F N to W F , the proof above has obtained, in the terminology of [START_REF] Chyzak | A non-holonomic systems approach to special function identities[END_REF], a polynomial growth of 1 for the ideal of annihilating operators of h, from which the existence of a telescoper follows by Theorem 3 in there.

Next, we prepare for the second step of the proof. The following lemma reflects the intuition that a mixed term H is "free of" y if ∆ y (H) = 0, where ∆ y is defined in (2).

Lemma 7.3. Let H be a mixed term over (k(x, y), (θ x , θ y )). If ∆ y (H) = 0, then its θ x -certificate belongs to k(x) and its θ y -certificate is equal to θ y (1).

Proof. Let the θ x -certificate and θ y -certificate of H be a and b, respectively.

First, assume that θ y = δ y . Then ∆ y = D y . It follows from D y (H) = bH = 0 that b = 0. Consequently, b = δ y [START_REF]Let h be a mixed term over (k(x, y), (θ x , θ y )), where (θ x , θ y ) = (δ x , σ y ) or (θ x , θ y ) = (σ x , δ y ). If its certificate with respect to the shift operator has a split denominator, then h is telescopable of type[END_REF]. It remains to show that a ∈ k(x). If θ x = σ x , then δ y (a)/a = σ x (b) -b by (3) and Remark 2.6. Since b = 0, δ y (a) = 0, that is, a is free of y. Similarly, a is free of y if θ x = τ x .

Second, assume that θ y = τ y . Then ∆ y (H) = 0 implies that τ y (H) = bH = H. It follows that b = 1, that is, b = τ y (1). To show that a ∈ k(x), we make a case distinction.

Case 1. If θ x = δ x , then δ x (b)/b = τ y (a) -a by (3). It follows from b = 1 that τ y (a) = a. Thus, a ∈ k(x) because q is not a root of unity.

Case 2. If θ x = σ x , then σ x (b)/b = τ y (a)/a, which, together with b = 1, implies that τ y (a) = a, and so that a ∈ k(x).

Third, assume that θ y = σ y . Then b = 1 and a ∈ k(x) by a similar argument as in the second case. ✷

  -a and b = 0 if (θ x , θ y ) = (δ x , σ y ), δx(b) b= τ y (a) -a and b = 0 if (θ x , θ y ) = (δ x , τ y ), x , θ y ) = (σ x , τ y ),

θ

  x (H(a, b)) = aH(a, b) and θ y (H(a, b)) = bH(a, b).

  b) ∈ k(x, y) × k(x, y) compatible w.r.t. (θx, θy) 1.

  θx, θy) = (δx, τy) 3.2. (θx, θy) = (τx, δy) 3.3. (θx, θy) = (σx, τy) 3.4. (θx, θy) = (τx, σy) ∃ f ∈ k(x, y), α ∈ k(x), and β ∈ k(y) such that H(a, b) = f H(α, β).

  | b but σ j0+j1 y τ (ρ-ℓ0+i0)+(ρ-ℓ1+i1)+µ x (p) ∤ b for any positive integer µ. Continuing this process yields a sequence of irreducible factors of b. Since b has only finitely many irreducible factors, there exist m, n ∈ N with n < m such that

  (or Section 1.2.1 of (Di Vizio and Hardouin, 2012)), implies that the incomplete Hurwitz zeta function ζ(x, y, s) := x) s (satisfying S y (F ) -F = f ) satisfies no polynomial differential equation P (x, y, s, F, D x (F ), D 2 x (F ), . . .) = 0.

  So there are b 1 ∈ k[x] and b 2 ∈ k[y] such that b = b 1 b 2 . It follows that p ∈ k(x)[y] with deg y (p) ≤ jµ. Since b 2 is free of x,

Table 2 .

 2 3. Ground fields and rings of Ore polynomials

  Table 6.6. Algorithms for deciding the existence of telescopers

Proposition 4.8. Let h be a mixed term over (k(x, y), (θ x , θ y )), and assume h ∈ f H(u, v), where f, u, v ∈ k(x, y). Let w be the non-split part of den(f ). Assume that h is exact with respect to ∂ y , and that w is not in k.(i) If θ y = δ y and den(v) is split, then w is δ y -spread. (ii) If θ y ∈ {σ y , τ y } and v is split, then w is θ y -spread.

This example was proposed by an anonymous referee.

This section is not part of the first edition.

Acknowledgement. The authors would like to thank the anonymous referees for their constructive and helpful comments, which have significantly improved the presentation of this paper.

1 In this work, S. Chen was supported by the NSF grant CCF-1017217 and NSFC No. 60821002/F02. F. Chyzak was supported in part by the Microsoft Research-INRIA Joint Centre. G. Fu, R. Feng and Z. Li were supported in part by NKBRPC (2011CB302400) and two grants of NSFC No. 60821002/F02 and No. 10901156.

are not necessary for the proof in the continuous-discrete case, because a power of a σ y -free polynomial is again σ y -free, and the least common multiple of finitely many δ yfree polynomials is again δ y -free. Unfortunately, similar situations do not occur in the discrete-q-discrete case.

The first lemma is a mixed analogue of Theorem 7 in (Abramov and Petkovsek, 2002a).

Lemma 5.4. Let p be an irreducible polynomial in k [x, y]. Assume that σ i x τ j y (p) = cp for some i, j ∈ Z and c ∈ k.

Proof. (i) Assume that there exist i, j ∈ Z with i = 0 and c ∈ k such that σ i x τ j y (p) = cp. We consider two cases. First, if τ j y (p) = p, then σ i x (p) = cp, so that c = 1 by comparing the leading coefficients with respect to x. Thus, p is free of x since i = 0.

Second, assume that τ j y (p) = p. Then d = deg y (p) > 0 and j = 0. Write

where p 0 , . . . , p ∈ k[x] and p d = 0. Then

By the equality σ i x τ j y (p) = cp, we have that p ℓ (x + i)q jℓ = cp ℓ (x) for all ℓ with 0 ≤ ℓ ≤ d.

Assume that ℓ is an integer in {0, . . . , d} such that p ℓ (x) = 0. Then c = q jℓ by considering leading coefficients with respect to x in the above equation. This implies that p ℓ (x + i) = p ℓ (x). It follows from i = 0 that p ℓ belongs to k. Thus, p is again free of x.

(ii) First, we show that σ i x (p) = p and τ j y (p) = cp. If i = 0, then there is nothing to prove. Otherwise, p belongs to k[y] by (i). So σ i

x (p) = p. The result follows from σ x •τ y = τ y •σ x . Second, we show that p is a monomial in y over k [x]. Suppose that there are d 1 and d 2 in N with d 1 > d 2 such that p = p d1 y d1 + p d2 y d2 + terms of lower degree in y, where p d1 , p d2 ∈ k[x] and p d1 p d2 = 0. Applying τ j y to p yields τ j y (p) = p d1 q jd1 y d1 + p d2 q jd2 y d2 + lower terms in y. The equality τ j y (p) = cp implies that c = q jd1 and c = q jd2 . Hence, q j(d1-d2) = 1, a contradiction to the assumption that q is not a root of unity. So p is a monomial in y.

Set p = λy s for some λ ∈ k[x] and s ∈ N. Since p is irreducible, s is equal to 0 or 1. If s = 0, then p is an irreducible polynomial in k[x]. If s = 1, then λ belongs to k, again because p is irreducible. Part (ii) of the lemma holds. ✷

The next lemma is a mixed analogue of Theorem 9 in [START_REF] Abramov | When does Zeilberger's algorithm succeed?[END_REF]. Its proof is also similar to that in [START_REF] Abramov | When does Zeilberger's algorithm succeed?[END_REF].

Lemma 5.5. Let r ∈ k(x, y) be a nonzero rational function whose denominator is not split. Let L be a nonzero element in k(x, y) ∂ x whose coefficients are all split. Then the following statements hold.

Lemma 7.4. Let h and H be two mixed terms over (k(x, y), (θ x , θ y )) with ∆ y (H) = 0. If h is telescopable of type (∂ x , ∂ y ), so is Hh.

Proof. Assume that H ∈ H(a, b). A straightforward induction shows that, for all i ∈ N,

where

, where e ρ , e ρ-1 , . . . , e 0 are in k(x) with e ρ = 0. Since L(h) = ∆ y (g) for some mixed term g,

Therefore, M is a telescoper for Hh. ✷ Lemma 7.5. Similar and telescopable terms of type (∂ x , ∂ y ), together with zero, form a linear space over k(x), which is closed under ∆ y .

Proof. Let h be a telescopable term of type (∂ x , ∂ y ). Set V h = {g | g is similar to h and telescopable of the same type} ∪ {0}.

For two telescopable terms in V h , a common left multiple of their telescopers is a telescoper of the sum whenever the sum is nonzero. Then V h is a linear space over k(x) by Lemma 7.4. The space is closed under ∆ y , because ∆ y commutes with every element of k(x) ∂ x . ✷

We are ready to show Theorem 6.1, which states that every proper term is telescopable.

Proof of Theorem 6.1. Assume that h is a proper term over (k(x, y), (θ x , θ y )). By Definition 4.13, a structural decomposition of h is of the form h = (u/v)g and g ∈ H(a, b), where u ∈ k(x)[y], v ∈ k[y], and H(a, b) are given by α, β and γ in Table 4.9. In particular, the denominators of a and b are split by their expressions in the table. By Lemma 2.10, we can move the univariate polynomial v(y) into H(a, b), yielding h = uG and G ∈ H(a, B), where B has a split denominator.

Write u = m i=0 u i y i , where u 0 , u 1 , . . . , u m ∈ k(x), and set G i = y i G. Again by Lemma 2.10, G i ∈ H(a, B i ) for some B i ∈ k(x, y) whose denominator is split. Since h is equal to m i=0 u i G i and the G i are similar to each other, by Lemma 7.5 it suffices to prove that G i is telescopable of type (∂ x , ∂ y ) for all i with 0 ≤ i ≤ m.

In the continuous-discrete case, G i is telescopable by Lemma 7.1, because both a and B i have split denominators.

In the continuous-q-discrete and discrete-q-discrete cases, a ∈ k(x) and b ∈ k(y) by part 3 of Table 4.9. Therefore, B i ∈ k(y) by Lemma 2.10. It follows again from Lemma 2.10 that H(a, B i ) = H (a, c ′ ) H (c ′′ , B i ), where c ′ = 0 and c ′′ = 1 if θ y = δ y , c ′ = 1 and c ′′ = 0 if θ x = δ x , and, otherwise, c ′ = c ′′ = 1. Accordingly, G i = G ′ i G ′′ i for some G ′ i in H (a, c ′ ) and G ′′ i in H (c ′′ , B i ). It follows that ∆ y (G ′ i ) = 0 and ∆ x (G ′′ i ) = 0.

The second equality implies that G ′′ i is telescopable of type (∂ x , ∂ y ), which, together with the first equality and Lemma 7.4, implies that G i is telescopable of type (∂ x , ∂ y ). The proof of Theorem 6.1 is completed.


Yérom-David Bromberg

Floréal Morandat

Laurent Réveillère

Gaël Thomas

EZ: towards efficient asynchronous protocol gateway construction

Over the past decade, we have witnessed the emergence of a bulk set of devices, from very different application domains interconnected via Internet to form what is commonly named Internet of Things (IoT). The IoT vision is grounded in the belief that all devices are able to interact seamlessly with each other anytime, anyplace, anywhere. However, devices communicate via a multitude of incompatible protocols, and consequently drastically slow down the IoT vision adoption. Gateways, that are able to translate one protocol to another, appear to be a key enabler of the future of IoT but present a cumbersome challenge for many developers. In this paper, we are providing a framework called EZ that enables to generate gateways for either C or Java platform without requiring from developers any substantial understanding of either relevant protocols or low-level network programming.

Introduction

In the new era of the Internet Of Thing (IoT), interoperability is a key challenge. Over the last years, a promising solution that gained success to address interoperability issues is to use gateways that translate back and forth messages among heterogeneous protocols [START_REF] Bromberg | INDISS: Interoperable discovery system for networked services[END_REF][START_REF] Bromberg | Automatic generation of network protocol gateways[END_REF][START_REF] Bromberg | Starlink: Runtime interoperability between heterogeneous middleware protocols[END_REF][START_REF] Issarny | Middleware-layer connector synthesis: Beyond state of the art in middleware interoperability[END_REF][START_REF] Rodrigues | Zigzag: A middleware for service discovery in future internet[END_REF]. The design of such gateways [START_REF] Bromberg | INDISS: Interoperable discovery system for networked services[END_REF][START_REF] Bromberg | Automatic generation of network protocol gateways[END_REF][START_REF] Bromberg | Starlink: Runtime interoperability between heterogeneous middleware protocols[END_REF][START_REF] Issarny | Middleware-layer connector synthesis: Beyond state of the art in middleware interoperability[END_REF][START_REF] Rodrigues | Zigzag: A middleware for service discovery in future internet[END_REF] does not take as a first class priority the specific needs of the IoT context. First, gateways must scale in the large, i.e., they must efficiently manage both bulk sets of messages and simultaneous message translation processes. Second, gateways need to be as pervasive as possible: they must run on highly heterogeneous software environments. Current gateways only target low-level C code and are not adequate in the IoT context where Java is also a mainstream language.

In this paper, we propose EZ a new gateway compiler for the z2z language [2] that relies on the event paradigm. We choose the z2z language as it has already proven to be adequate to describe gateways. To solve performance issues EZ defines a workflow of handlers, which communicate with events. Further, to take into account software heterogeneity, EZ is able to compile the z2z language to both C and Java code, ready to be plugged into respective runtimes.

The remainder of this paper is structured as follows. Section 2 introduces our approach to generate from high level specifications our next generation gateways for either C or Java environment. Section 2.2 is focused on the internal design of our next generation gateways. In particular, it presents our new asynchronous runtime system for building scalable gateways in either C or Java along with EZ. Section 3 presents the performance evaluation of our asynchronous gateways. Finally, Section 4 reviews related research works and Section 5 concludes the paper with a discussion of future research directions.

EZ approach

In a way similar to z2z, zebu [START_REF] Bromberg | Automatic generation of network protocol gateways[END_REF][START_REF] Burgy | Zebu: A language-based approach for network protocol message processing[END_REF], our approach is based on generative programming. More specifically, EZ reuses the z2z domain specific language to specify generated gateways (Figure 1, ❶). However, EZ introduces a new compiler enabling the generation of asynchronous code in either C or Java to be linked into an adequate and efficient event-based oriented runtime system (Figure 1,❷,❸) that fulfills the requirements of IoT. In other terms, developers only have to replace the z2z compiler by the EZ one to generate event-based gateways. These gateways use exclusively non-blocking system calls to perform asynchronous I/O network operations. Fig. 1. EZ approach to generate asynchronous multi-platform gateway.

Z2z domain specific language

Our EZ approach has been design especially to be fully compliant with the z2z language that has been proved to be adequate to describe gateways in high level manner by hiding to developers low-level network and system codes.

Z2z language. The z2z language provides facilities for defining three types of modules: the Protocol Specification (PS) modules used to describe the network protocol behaviors, the Message Specification (MS) modules used to describe message structures, and the Message Translation (MT) modules used to describe the message translation logic. More precisely, a PS module provides information about various properties of the interaction with the network, such as the transport protocol used, whether requests are sent in unicast or multicast, and whether responses are received synchronously or asynchronously. It also specifies how to dispatch a received request to a specific handler for processing. A MS module defines the useful information to be extracted from incoming messages, i.e., message views. It also defines the structure of new messages to be created, i.e., message templates. A template contains a message view that describes "holes" to be filled by the translation logic when creating a new message. Finally, a MT module is specified using a dedicated C-like syntax and consists of a set of handlers, one for each kind of relevant incoming requests, as indicated by the protocol specification. It provides domain-specific operators for manipulating and constructing messages, for sending requests and returning responses, and for managing session state across requests.

Z2z front-end compiler. Our new EZ compiler reuses the z2z front-end that deals with the scanning and the parsing of the language and performs consistency checks across the PS, MS and MT modules. For instance, the front-end checks that the MT module defines a handler for each kind of message that should be handled by the gateway and that each handler has an appropriate return type according to the PS module. It guaranties that all fields and values have been appropriately initialized and used across the different modules. Further, the front-end compiler performs as well a data-flow analysis of the message translation code to detect erroneous specifications and ensure the generation of safe code.

Asynchronous EZ runtime

One key contribution of the EZ approach is to be able to generate in a transparent manner either C or Java gateways. Specifically, both C and Java based gateways use runtimes implemented with an event-based programming paradigm built on top of the libasync [START_REF] Mazières | A toolkit for user-level file systems[END_REF] event-driven library for the C version and the new NIO.2 API provided by the JDK7 for the Java version.

Event bus

Main thread loop

1 2 3 2 1

Fig. 2. Event-based processing chain

Gateways are decomposed into key functional building blocks, such as message extraction, processing, and generation. Each of these building blocks registers their interests into network I/O events (See Figure 2,❶,❷,❸). Further, each building block may additionally interact with each other via the use of events that they can generate by themselves. For instance, events for either notifying the arrival of a recognized and fully parsed message, for indicating that no data can be read anymore, or for notifying network I/O error, are asynchronously dispatch to the building blocks that have declared their interest in these events. Incoming messages that traverse the event-based processing chain are then decomposed into multiple events that are serially dispatched one at a time by a main thread loop. As a consequence, the pipeline, contrary to our previous work [START_REF] Bromberg | INDISS: Interoperable discovery system for networked services[END_REF][START_REF] Bromberg | Automatic generation of network protocol gateways[END_REF][START_REF] Bromberg | Starlink: Runtime interoperability between heterogeneous middleware protocols[END_REF][START_REF] Issarny | Middleware-layer connector synthesis: Beyond state of the art in middleware interoperability[END_REF][START_REF] Rodrigues | Zigzag: A middleware for service discovery in future internet[END_REF], is not anymore shared among a pool of threads avoiding so mutex lock contentions and increasing inherently performances.

Event-based message processing. As opposed to z2z for instance, EZ treats each operation performed by the translation logic, that leads to an I/O access, as an asynchronous call and thus is compiled by the EZ compiler so as to produce a continuation. When the operation is completed, an event is generated and caught by the runtime system that resumes the associated continuation to resume the processing. This strategy results in the creation of many continuations for a handler.

Event-based message extraction. In contrast to the thread model that accumulate data to reconstruct the corresponding message before processing it, EZ processes messages even if there are not yet fully parsed. When no more data can be read, because of message fragmentation for example, the parser is paused, the current state is saved and a callback is attached to the availability of new data. When the associated event occurs, the callback is invoked and execution continues in the previously saved state. A soon as a fragment or a message field is recognized by the parser an event is immediately triggered. This event is then stored in the message view to be processed by the other building blocks such as the message processing one. With EZ, message parsing drastically limits memory consumption because a message does not need to be entirely saved in memory before starting its parsing. Instead, in C based version of the runtime, two contiguous memory pages are used as a circular buffer, accounting for about 8KB of memory, whereas in the Java version of the runtime two buffers are used and flipped when the first one is exhausted. This only works thanks to the scattered read facility of Java network API. In the either C or Java runtimes, dynamic memory allocation is only required for filling values of the message view when fields are recognized.

Event based error management. When an event occurs, the associated callback function is executed by the runtime system. However, events corresponding to I/O operations may never occur if the underlying operation fails to complete, leading thus to memory leaks difficult to address. To overcome this issue, C and Java EZ runtimes attach timeout on each event. If the corresponding timer expires before the occurrence of the event, the runtime frees associated resources to prevent memory leaks.

• • • • • • • • • • • • • • EZ-C EZ-Java z2z direct

Related Work

There have been a bulk set of different approaches to protocol interoperability, for instance to name a few, ReMMoC [START_REF] Grace | A reflective framework for discovery and interaction in heterogeneous mobile environments[END_REF], RUNES [START_REF] Costa | Reconfigurable component-based middleware for networked embedded systems[END_REF], MUSDAC [START_REF] Raverdy | A multi-protocol approach to service discovery and access in pervasive environments[END_REF], BASE [START_REF] Becker | Base: A micro-broker-based middleware for pervasive computing[END_REF], INDISS [START_REF] Bromberg | INDISS: Interoperable discovery system for networked services[END_REF], Starlink [START_REF] Bromberg | Starlink: Runtime interoperability between heterogeneous middleware protocols[END_REF] and Enterprise Service Buses [START_REF] Chappell | Enterprise Service Bus[END_REF]. Compared to EZ, these approaches have three major weak points: neither they address the difficulty of gateway development nor they tackle the scalability issue, and nor they target both C and Java environment. The closest approach to ours is z2z [START_REF] Bromberg | Automatic generation of network protocol gateways[END_REF], which constitutes the first generative approach for building gateways. However, z2z generated gateways exhibit poor scalability in the face of the increasing load generated by clients and the increasing size of messages. Furthermore, z2z only targets C environment and is therefore less pervasive than a Java based version. Scalability has been a major concern in the field of Web servers as these systems must efficiently operate on thousands of files and connections. However, Web servers are CPU intensive oriented while gateways are I/O intensive. Thus experiences on Web server architecture should not be granted for gateways.

Network protocol gateways are a key enabler of the future of IoT but present a cumbersome challenge for developers. In particular there are three main challenges that need to be overcome to build gateways: (i) providing an easy way to build gateways by hiding to developers intricacies of low-level network and system code, (ii) tackling the scalability issue,(iii) beeing pervasive, i.e. multi-platform compliant (i.e. C or Java based). As a future direction, multicore architectures are today a reality in all kinds of computing systems, ranging from powerful servers to desktop environments and embedded systems. However current systems and applications are unable to fully exploit these new architectures. Taking advantage of multicore hardware is thus today one of the most important scientific challenges in the systems domain. We are investigating the extension of EZ to support multicore architectures. Another potential research direction is to raise on our ongoing research work on hardware accelerated parsers to speed up drastically messages processing in embedded platforms [START_REF] Mercadal | Zebra: Building efficient network message parsers for embedded systems[END_REF].

Fig. 3 .

 3 Fig. 3. Time to send 1000 message of 10kB by N clients.

  For our experiments, a given number of simultaneous clients (up to 30) send 1000 messages of 10KB in a closed loop 1 to a SMTP server through a tunneling application. Figure3shows the response time for each gateway, as well as the native protocol communication costs (direct). Since gateways are I/O intensive, a certain amount of clients are required to get satisfying throughput. The event-based gateways (EZ-C and EZ-Java) clearly outperform the thread-based gateways (z2z).

	To assess the scalability of z2z and
	EZ gateways, we have implemented
	the SMTP/HTTP and HTTP/STMP
	gateways described previously. Our
	performance experiments are carried
	out on a Dell Intel R Xeon R server
	powered by 4 processors of 8 hyper-
	threaded cores clocked at 2.2 GHz.
	We use the multi-threaded SMTP test
	client and server distributed with Post-
	fix to stress the generated gateways. C
	code is compiled using gcc 4.7.2 and
	Java code executes on HotSpot server
	1.7.

A client sends a new message only when it receives an acknowledgement from the server for the reception of the previous message.