Constructing minimal telescopers for rational functions in three discrete variables (Q2168558)

The authors develop a reduction-based creative telescoping algorithm for rational functions in three discrete variables. Such method is able to derive a linear recurrence equation with polynomial coefficients that is satisfied by a given double sum over a trivariate rational function. Its core is a reduction procedure that decomposes a given function into a summable part and a remainder (which is non-summable if it is nonzero). The reason why reduction-based creative telescoping algorithms have been intensively studied in the past few years is the fact that this approach allows one to compute telescopers without having to compute the corresponding certificates, which makes them very interesting from an application point of view. Most of the work so far has been on bivariate problems (i.e., single sums and single integrals), and the present paper is the first attempt on trivariate problems, at least in the discrete (summation) case. The starting point for the algorithm is a reduction method due to Abramov for bivariate rational functions, which the authors extend so that it is applicable in their setting. However, this extended Abramov reduction cannot be used as is, because it lacks an important property: linearity. For constructing telescopers, one has to rely on the fact that the sum of two remainders is again a remainder. This problem is overcome by a process called remainder linearization, which is achieved by choosing a particular representative of the residue class modulo summable rational functions. Now it can be shown that these new remainders behave well with respect to taking linear combinations, which in turn yields the promised reduction-based algorithm to construct telescopers for rational functions in three discrete variables. The termination of the algorithm follows from a previously known existence criterion of telescopers. Several optimizations are described how the efficiency of the basic algorithm can be improved. The paper is concluded by computational experiments carried out in Maple, with an implementation of the algorithm that was produced by the authors themselves. They show an impressive speed-up compared to other computer programs that do not use the reduction-based approach.