Starting from the seminal, but for a long time neglected, paper [J. Assoc. Comput. Mach. 28, 305–350 (1981; Zbl 0494.68044)] by M. Karr, the author has been developing over the past several years powerful algorithms for automatic summation (implemented in the Mathematica package Sigma). The setting in which these algorithms work is difference fields. A difference field \((\mathbb F,\sigma)\) is a field \(\mathbb F\) together with a field automorphism \(\sigma:\mathbb F\to\mathbb F\). In the context of summation problems, \(\mathbb F\) contains \(\mathbb Q(k)\) (\(\mathbb Q\) denoting the set of rational numbers, and \(k\) being a variable of which we should think as the summation index) and \(\sigma\) is the shift in \(k\), \(\sigma(k)=k+1\), fixing \(\mathbb Q\). What does this have to do with summation?
The idea is to model terms which appear in summands within a difference field. For example, if we should want to evaluate \(\sum _{k=1} ^{n}H_k\), where \(H_k=\sum _{i=1} ^{k}\frac {1} {i}\) is the \(k\)-th harmonic number, then we construct the difference field \(\mathbb F=\mathbb Q(k)(h)\), where \(\sigma(k)=k+1\), \(\sigma(h)=h+\frac {1} {k+1}\), and \(\sigma(q)=q\) for \(q\in\mathbb Q\). Clearly, \(h\) “models” the sequence \((H_k)_{k\geq1}\). If we are able to find \(g\in\mathbb F\) such that the difference equation \(\sigma(g)-g=h\) holds (and indeed, we are: Schneider’s package Sigma finds \(g=k(h-1)\)), then upon reinterpreting \(g\) and \(h\) as the sequences \(g(k)=k(H_k-1)\) and \(h(k)=H_k\), respectively, and summing the difference equation over \(k=1,2,\dots,n\), we obtain \(\sum_{k=1}^{n}H_k=(n+1)(H_{n+1}-1)\).
Binomial coefficients, \(q\)-binomial coefficients, and more generally hypergeometric and \(q\)-hypergeometric terms, higher order harmonic numbers, but also nested sums and products, can all be modeled within difference fields. Thus, the range of applicability of this idea is wider than that of the Gosper-, Zeilberger-, and the WZ-algorithms (cf. [M. Petkovšek, H. Wilf and D. Zeilberger, A=B, A. K. Peters, Wellesley (1996; Zbl 0848.05002)], and also of the holonomic algorithms (cf. [F. Chyzak, Discrete Math. 217, 115–134 (2000; Zbl 0968.33011)]). The basic problem that one must solve is the problem of solving a parametrized linear differenc equation: given a difference field \((\mathbb F,\sigma)\) with constant field \(\mathbb K\) (that is, \(\mathbb K\) is the subset of elements of \(\mathbb F\) fixed by \(\sigma\)), \(a_1,a_2,\dots,a_m\in\mathbb F\) not all zero, and \(f_1,f_2,\dots,f_n\in\mathbb F\), find all \(g\in\mathbb F\) and \(c_1,c_2,\dots,c_n\in\mathbb K\) such that \[ a_1\sigma^{m-1}(g)+a_2\sigma^{m-2}(g)+\dots+a_mg= c_1f_1+c_2f_2+\dots+c_nf_n. \]
The simple difference equation that we solved in our example was the special case \(\mathbb F=\mathbb Q(k)(h)\), \(m=2\), \(a_1=1\), \(a_2=-1\), \(n=1\), \(c_1=1\), \(f_1=h\). The more general problem must, for instance, be solved to find recurrences for summations or if terms are only implicitly given by a recurrence.
In the paper under review, it is shown how to solve this problem algorithmically in \(\Pi\Sigma\)-fields (roughly speaking, these are difference fields which model nested sums and products). In particular, Karr’s original algorithm is simplified and extended. As the author points out, there are certain subproblems which he is not able to settle in complete generality. These pertain to denominator and degree bounding. However, he presents procedures that approximate these bounds and, thus, allow to search systematically for all solutions by increasing step by step the domain of possible solutions. In particular, he proves that eventually all solutions will be found in that way. Throughout the paper, the theoretical results are accompanied by illustrative examples.