We present efficient methods for calculating linear recurrences of hypergeometric double sums and, more generally, of multiple sums. In particular, we supplement this approach with the algorithmic theory of contiguous relations, which guarantees the applicability of our method for many input sums. In addition, we elaborate new techniques to optimize the underlying key task of our method to compute rational solutions of parameterized linear recurrences.

A non-trivial symbolic machinery is presented that can rephrase algorithmically a finite set of nested hypergeometric products in appropriately designed difference rings. As a consequence, one obtains an alternative representation in terms of one single product defined over a root of unity and nested hypergeometric products which are algebraically independent among each other. In particular, one can solve the zero-recognition problem: the input expression of nested hypergeometric products evaluates to zero if and only if the output expression is the zero expression. Combined with available symbolic summation algorithms in the setting of difference rings, one obtains a general machinery that can represent (and simplify) nested sums defined over nested products.

We present a general framework in the setting of difference ring extensions that enables one to find improved representations of indefinite nested sums such that the arising denominators within the summands have reduced degrees. The underlying (parameterized) telescoping algorithms can be executed in RΠΣ -ring extensions that are built over general ΠΣ -fields. An important application of this toolbox is the simplification of d’Alembertian and Liouvillian solutions coming from recurrence relations where the denominators of the arising sums do not factor nicely.

We introduce a general reduction strategy that enables one to search for solutions of parameterized linear difference equations in difference rings. Here we assume that the ring itself can be decomposed by a direct sum of integral domains (using idempotent elements) that enjoys certain technical features and that the coefficients of the difference equation are not degenerated. Using this mechanism we can reduce the problem to find solutions in a ring (with zero-divisors) to search solutions in several copies of integral domains. Utilizing existing solvers in this integral domain setting, we obtain a general solver where the components of the linear difference equations and the solutions can be taken from difference rings that are built e.g., by RΠΣ-extensions over ΠΣ-fields. This class of difference rings contains, e.g., nested sums and products, products over roots of unity and nested sums defined over such objects.

Symbolic summation started with Abramov (1971) for rational sequences and has been pushed forward by Gosper (1978), Zeilberger (1991), Petkovsek (1992) and Paule (1995) to tackle indefinite and definite sums for hypergeometric expressions. In the last decade the class of input sums has been extended significantly and covers, for instance, hypergeometric multi-sums, holonomic sequences, unspecified sequences, radical expressions, Stirling numbers, etc. In this talk we will focus on a new difference ring approach. The foundation was led by Karr's summation algorithm (1981) which enables one to rephrase indefinite nested sums and products in the setting of difference fields. Many new ideas have been incorporated into a strong summation theory which led to new algorithms for the summation paradigms of telescoping, creative telescoping and recurrence solving. However, this elegant difference field approach has one central drawback. Alternating signs cannot be represented in such a field: zero-divisors are introduced which can be formulated only within a ring. We will present a class of difference rings in which one can represent algorithmically indefinite nested sums and products together with the alternating sign, and more generally products over primitive roots of unity. In this setting we can represent all indefinite nested sums defined over hypergeometric expressions. In particular, this construction produces expressions in terms of sums that are all algebraically independent over each other. As a consequence, the derived output of a nested product-sum expression solves the zero-recognition problem: the computed expression evaluates to the zero-sequence if and only if the expression has been simplified to zero.

A summation framework is developed that enhances Karr's difference field approach. It covers not only indefinite nested sums and products in terms of transcendental extensions, but it can treat, e.g., nested products defined over roots of unity. The theory of the so-called [Formula: see text]-extensions is supplemented by algorithms that support the construction of such difference rings automatically and that assist in the task to tackle symbolic summation problems. Algorithms are presented that solve parameterized telescoping equations, and more generally parameterized first-order difference equations, in the given difference ring. As a consequence, one obtains algorithms for the summation paradigms of telescoping and Zeilberger's creative telescoping. With this difference ring theory one gets a rigorous summation machinery that has been applied to numerous challenging problems coming, e.g., from combinatorics and particle physics.

We continue to investigate which polynomials can possibly occur as factors in the denominators of rational solutions of a given partial linear difference equation. In an earlier article we have introduced the distinction between periodic and aperiodic factors in the denominator, and we have given an algorithm for predicting the aperiodic ones. Now we extend this technique towards the periodic case and present a refined algorithm which also finds most of the periodic factors.

We investigate which polynomials can possibly occur as factors in the denominators of rational solutions of a given partial linear difference equation (PLDE). Two kinds of polynomials are to be distinguished, we call them periodic and aperiodic. The main result is a generalization of a well-known denominator bounding technique for univariate equations to PLDEs. This generalization is able to find all the aperiodic factors of the denominators for a given PLDE.

An extension of Karr’s summation algorithm is presented by which symbolic sums involving radical expressions can be simplified. We discuss the construction of appropriate difference fields as well as algorithms for solving difference equations in these fields. The paper is concluded by a list of identities found with an implementation of our techniques.

We consider symbolic sums which contain subexpressions representing unspecified sequences. Existing symbolic summation technology is extended to sums of this kind. We show how this can be applied in the systematic search for general summation identities. Both, results about the non-existence of identities of a certain form, and examples of general families of identities which we have discovered automatically are included in the paper.

We provide algorithms that find, in case of existence, indefinite nested sum extensions in which a (creative) telescoping solution can be expressed with minimal nested depth.

Abstract. We present a streamlined and refined version of Karr’s summation algorithm. Karr’s original approach constructively decides the telescoping problem in ΠΣ-fields, a very general class of difference fields that can describe rational terms of arbitrarily nested indefinite sums and products. More generally, our new algorithm can decide constructively if there exists a so called single-nested ΠΣ-extension over a given ΠΣ-field in which the telescoping problem for f can be solved in terms that are not more nested than f itself. This allows to eliminate an indefinite sum over f by expressing it in terms of additional sums that are not more nested than f. Moreover, our refined algorithm contributes to definite summation: it can decide constructively if the creative telescoping problem for a fixed order can be solved in single-nested Σ ∗-extensions that are less nested than the definite sum itself. 1.