Project topics and materials
Get Complete Project Material File(s) Now! »
Motivation
Since the 1990’s, Zeilberger’s method has been extensively studied in the literature [95, 96, 15, 92, 63, 6, 7, 65, 28, 16]. The main focus of those studies is on the efficiency and termination of creative-telescoping algorithms.
Related to efficiency, progress and improvements have since been made by Abramov [7], Apagodu [16], Chyzak [35, 33], Le [63, 46, 65], Takayama [85], etc. However, very little is known about the complexity of creative-telescoping algorithms. We believe that complexity analysis helps us understand algorithms, and indicates good ways of improving and implementing them.
This is one of the motivations for Chapter 3. The existing algorithms bind the construction of telescopers with certificates. In certain applications, only telescopers are needed. For bivariate rational-function inputs, our complexity analysis shows that the arithmetic size of certificates is asymptotically larger than that of telescopers. So the complexity could be lower if one can avoid the calculations for certificates in certain applications. This motivates us to find a way in which one could choose to compute or not to compute the certificates according to the user requirements.
By the functionality of Zeilberger-style algorithms, their termination is equivalent to the ex-istence of telescopers. In his pioneering work [95], Zeilberger has proved that telescopers exist for holonomic functions. In particular, Wilf and Zeilberger [92] have presented an elementary and constructive proof of the existence of telescopers for proper hyperexponential-hypergeometric functions by basing on ideas of Fasenmyer [40] and Verbaeten [89]. By a proper hyperexponential-hypergeometric function, we mean a function that can be written as a product of a polynomial, exponential functions, power functions, and factorial terms. Properness can be detected from the certificates of a hyperexponential-hypergeometric function. Moreover, Wilf and Zeilberger con-jectured in [92, page 585] that a hyperexponential-hypergeometric function is holonomic if and only if it is proper. If this conjecture were verified, then one could algorithmically detect the holo-nomicity of hyperexponential-hypergeometric functions. In the case of several discrete variables, a slightly modified version of the conjecture has been proved independently by Payne in his Ph.D. thesis [73] and by Abramov and Petkovšek [14]. In particular, the case of two variables has also been shown by Hou [54, 55] and by Abramov and Petkovšek [12]. However, holonomicity is only a sufficient condition for the existence of telescopers. In fact, Chyzak, Kauers, and Salvy [34] have listed certain classes of functions that are not holonomic but still have telescopers. Therefore, the challenge is to find theoretical criteria that enable us to algorithmically detect the existence of telescopers.
In view of the theoretical difficulty, special attention has been focused mainly on the sub-class of hyperexponential-hypergeometric functions. In the continuous case, the works by Bern-stein [17] and Lipshitz [67] show that every hyperexponential function has a telescoper. This implies that Zeilberger’s algorithm always succeeds on those inputs. However, the situation in other cases turns out to be more involved. In the discrete case and its q-analogue, the first complete solution to the termination problem is Abramov and Le’s criterion [64, 9], which decides whether telescopers exist for a given bivariate rational function in the discrete variables m and n. According to their criterion, the rational function has no telescoper. Soon, the criterion was extended to the general case of bivariate hypergeo-metric terms by Abramov [5, 6]. Basically, Abramov proves that a hypergeometric term can be written as a sum of a hypergeometric-summable term and a proper one if it has a telescoper [6, Theorem 10]. Similar results have been obtained in the general q-shift case by Chen, Hou and Mu [28]. These results are fundamental for predicting the termination of Zeilberger’s algorithm.
A continuous-discrete analogue of Zeilberger’s algorithm was presented by Almkvist and Zeilberger [15]. This analogue has been shown to be very useful in the study of orthogonal poly-nomials [60, Chapters 10–13]. In this setting, not all hyperexponential-hypergeometric functions have telescopers. For example, we will show in this thesis that the rather simple rational function in the continuous variable x and the discrete variable n has no telescoper with respect to either the continuous variable x or the discrete variable n.
Therefore, an existence criterion is also needed in this mixed setting.
Main results
For a bivariate rational function, we present a new algorithm to compute its minimal telescoper, which is based on Hermite reduction. We also obtain some improvements over the classical algorithm by Almkvist and Zeilberger by extending the idea of Geddes and Le to general rational-function inputs. Moreover, we give the first proof of a polynomial complexity (in terms of field operations) for creative telescoping on this specific class of inputs. Our algorithms are proved to be faster concerning both theoretical complexity and actual performance.
Motivated by a conjecture of Wilf and Zeilberger [92, page 585], we study the possible form of a multivariate hyperexponential-hypergeometric function. For such a function, we prove a structure theorem for its certificates, which generalizes a recent result by Feng, Singer, and Wu [42, Proposition 5]. Combining our result with the result on multivariate hyperexponential functions in [29, 97] and the Ore-Sato theorem on multivariate hypergeometric terms, we obtain a structure theorem for multivariate hyperexponential-hypergeometric functions, which says that a multivariate hyperexponential-hypergeometric function can be written as a product of a rational function, an exponential function, power functions and factorial terms.
With the help of the result by Feng, Singer, and Wu [42, Proposition 5], we derive two criteria for the existence of telescopers for bivariate hyperexponential-hypergeometric functions. We show that a hyperexponential-hypergeometric function can be written as a sum of a hypergeometric-summable, resp. hyperexponential-integrable, function and a proper one if it has a telescoper with respect to the discrete, resp. continuous, variable. Our criteria are based on standard representations and the two adapted additive decompositions. With them, we can decide in ad-vance the termination of the continuous-discrete analogue of Zeilberger’s algorithm for bivariate hyperexponential-hypergeometric functions.
Outline
In this section, we provide the reader with an outline of this thesis.
Chapter 2. We recall basic notation and facts on differential rings, difference rings and Ore polynomials. Our new algorithm for the construction of minimal telescopers will be based on the Hermite reduction for the integration of the rational function. So we review the classical algo-rithms for rational-function integration, including Hermite reduction, Ostrogradsky–Horowitz’s method, and Rothstein–Trager’s algorithm. We also summarize some complexity results for later use.
Chapter 3. We focus on deriving a fast algorithm for computing minimal telescopers for bi-variate rational functions. First, we present an optimal algorithm for the Hermite reduction over k(x) by fast evaluation-interpolation strategy. Second, we present a new algorithm for com-puting the minimal telescoper of a bivariate rational function, based on a bivariate extension of Hermite reduction. Moreover, some improvements over the classical method by Almkvist and Zeilberger [15] are achieved in this chapter. We also analyze the arithmetic complexity of those algorithms. Third, we adapt and slightly extend the arguments by Lipshitz [67] and by Bostan and others [20] to derive smaller total degree sizes of telescopers. At last, we describe our implementation and show experimental results.
Chapter 4. We first present an algebraic setting for hyperexponential-hypergeometric functions. After that, we review various normal forms of rational functions and introduce a new kind of rational normal forms, which enables us to extend the existing results to multivariate continuous-discrete setting. Our main result is Theorem 4.4.6 on the structure of certificates of a multivariate hyperexponential-hypergeometric function. This result is a generalization of a result by Feng, Singer, and Wu [42, Proposition 5]. At last, we describe a multiplicative form of multivariate hyperexponential-hypergeometric functions.
Chapter 5. We study the existence of telescopers for hyperexponential-hypergeometric functions of one continuous variable and one discrete variable. First, we review the construction of a ring of sequences from [41, 43], which allows us to study the existence problem in an algebraic manner. After that, we introduce standard representations for bivariate hyperexponential-hypergeometric functions and then adapt two additive decompositions [13, 47] to bivariate hyperexponential-hypergeometric functions described by their standard representations. At last, we describe our existence criteria and its algorithmic description with examples.
Table of contents :
1 Introduction
1.1 Motivation
1.2 Main results
1.3 Outline
1.4 Notation
2 Preliminaries
2.1 Differential and difference rings
2.2 Ore polynomials
2.3 Integration of rational functions
2.3.1 Hermite reduction
2.3.2 Ostrogradsky and Horowitz’s method
2.3.3 Residues and Rothstein–Trager resultants
2.4 Background on complexity
3 Hermite Reduction for Rational-Function Telescoping
3.1 Introduction
3.2 Notation and hypotheses
3.3 Hermite reduction for bivariate rational functions
3.3.1 Output size estimates
3.3.2 Algorithm by evaluation and interpolation
3.4 Minimal telescopers for bivariate rational functions
3.4.1 Hermite-reduction based method
3.4.2 Improved Almkvist and Zeilberger’s method
3.5 Non-minimal telescopers for bivariate rational functions
3.6 Implementation and experiments
3.6.1 Implementation and examples
3.6.2 Experimental results
4 Structure of Multivariate Hyperexponential-Hypergeometric Functions
4.1 Introduction
4.2 Algebraic setting
4.2.1 Hyperexponential-hypergeometric functions
4.2.2 First-order fully integrable systems
4.3 Rational normal forms
4.3.1 Differential and shift rational normal forms
4.3.2 Y-rational normal forms
4.4 Structure of compatible rational functions
4.4.1 The Ore-Sato theorem
4.4.2 Alternative proof of multivariate Christopher’s theorem
4.4.3 Multivariate extension of Feng-Singer-Wu’s lemma
4.5 Multiplicative structure
5 Existence of Telescopers for Hyperexponential-Hypergeometric Functions
5.1 Introduction
5.2 Preliminaries
5.2.1 Ring of sequences
5.2.2 Ring of differential-recurrence operators
5.2.3 Split polynomials
5.3 Existence problems
5.4 Standard representations
5.5 Two additive decompositions
5.5.1 Additive decomposition with respect to x
5.5.2 Additive decomposition with respect to n
5.5.3 Applying operators to additive decompositions
5.6 Two existence criteria
5.6.1 Existence of telescopers implies properness
5.6.2 Properness implies the existence of telescopers
5.7 Algorithms and examples
5.7.1 Algorithms
5.7.2 Examples
6 Conclusion and Perspectives
6.1 Extensions of the Hermite-reduction based method
6.2 Existence criteria for telescopers in the q-setting
6.3 Wilf and Zeilberger’s conjecture
