Carsten Schneider

Tutorial title: Symbolic Summation in Difference Rings — With Applications in Combinatorics, Numerics, and Physics

Abstract: Symbolic summation deals with the simplification of formulas or with proving identities given in terms of (usually complicated) multiple nested sums. A first breakthrough in this research area was achieved for indefinite single sums over hypergeometric expressions (e.g., single sums over binomial coefficients or factorials). Namely, using Gosper’s telescoping algorithm (1978) one can decide, if such a sum can be written in terms of hypergeometric expressions. Another crucial contribution is Zeilberger’s observation (1991) that Gosper’s algorithm can be extended to creative telescoping. This enables the user to compute linear recurrence relations for definite hypergeometric sums. Finally, Pektovsek’s Hyper algorithm determines all hypergeometric solutions of a given linear recurrence with polynomial coefficients. Combining these algorithms yields a method that decides if a definite hypergeometric sum can be expressed as a linear combination of hypergeometric expressions.

In this tutorial we present a generalization of these summation techniques that work not only for sums over hypergeometric expressions but for sums over indefinite nested multiple sums and products. Here we focus on the following two aspects.

* Indefinite summation: Simplify expressions in terms of indefinite nested sums and products such that the occurring sums are algebraically independent and such the obtained expressions consist of sums that have certain optimality criteria (such as minimal nesting depth or minimal degree in the denominators).

* Definite summation: Compute recurrences (based on the paradigm of Z’s creative telescoping) for definite sums with summands given in terms of indefinite nested sums and products, and solve the derived recurrences in terms of indefinite nested sums and products (also called d’Alembertian solutions, a subclass of Liouvillian solutions). In this way, one can decide (similarly to the hypergeometric case) if such a definite nested sum can be expressed in terms of indefinite nested sums and products.

The algorithmic framework of this approach is based on Karr’s difference fields (1981) and a recent generalization to a difference ring theory. We will work out the underlying ideas and algorithms and present the current developments and improvements in this research topic. Special emphasis will be put on concrete examples arising, e.g., from combinatorial problems and numerics. In particular, we demonstrate how the symbolic summation algorithms can be utilized to evaluate whole classes of Feynman integrals arising in the context of Elementary Quantum Field Theory. The latter examples pop up within an intensive cooperation with the Theory Group (Johannes Blümlein) of the Deutsches Elektronen-Synchrotron DESY, Zeuthen.

Author website: