Symbolic Summation in Difference Fields

The algorithmic problem of symbolic summation can be seen as the discrete analogue of the well-known problem of symbolic integration. In other words, instead of simplifying integrals of functions, summation algorithms try to find simple representations of complicated sum expressions. In applications (chemistry, computer science, mathematics, and physics) such sums often arise in combinatorial work related to counting of objects. Historically, the starting point of modern symbolic summation is quite recent, namely Gosper`s algorithm (1978) which constitutes a decision procedure for indefinite hypergeometric summation. Hypergeometric terms describe sequences arising frequently in practical applications. The next major breakthroughs were made by Karr (1981) and Zeilberger (1990). Most recently, in his PhD thesis, Schneider was able to generalize Karr`s theory significantly. In particular, he was able to extend Zeilberger`s paradigm of ``creative telescoping`` for definite hypergeometric sums to sums expressible in very general algebraic domains, so-called difference fields. The proposed research concerns open problems related to Schneider`s difference field approach. The overall objective is to obtain a general algorithmic theory analogous to that of integration. Special emphasize is put on computer algebra implementations that help scientists in practical problem solving.

Manifold aspects of different approaches to symbolic summation have been extended in various directions during the project. Symbolic summation deals with the problem of systematically representing a mathematical expression involving summation quantifiers in terms of an equivalent, but simpler expression, where `simpler` might mean that it involves no summation signs, or at least less such symbols than the original expression, or summation signs that appear in a more appealing arrangement. Ideally, a systematic procedure (i.e., an algorithm) for rewriting sum expressions in this way can be carried out by a computer. Research in symbolic summation combines both theoretical aspects (e.g. finding structure theorems restricting the form of potential closed form solutions) and practical aspects (e.g. actually devising summation algorithms and implementing them on a computer). Several algorithms for symbolic summation have been proposed in the past, and several software implementations are available. In this project, we have mainly focused on extending a summation algorithm given by Karr in 1981. Also new summation algorithms, and algorithms operating on recurrence equations that are closely related to the summation problem, have been developed. The main achievements of the project, documented in more than thirty refereed scientific articles, concern: Algorithms for dealing with nested sums. (E.g., for automatically minimizing the nesting depth of a given sum.) Algorithms for dealing with linear recurrence equations. (E.g., for automatically finding so-called generalized d`Alembertian solutions of such equations.) Algorithms for dealing with nonlinear recurrence equations. (E.g., for automatically finding algebraic relations between solutions of such equations.) Algorithms for dealing with special function inequalities. (E.g., for automatically proving positivity of certain combinatorial sequences.) The significance of our contributions is underlined by the fact that many of our algorithms solve problems that cannot be solved by any other method currently known. The results of the project have immediate impact to classical branches of mathematics such as combinatorics or the theory of special functions. In addition, there are applications to finite elements (numerics), quantum field theory (particle physics), and other disciplines that seem unrelated at first glance. Using the software developed during the project, it was already possible to provide solutions to several open problems that arose in these areas and that are of independent interest.