| |
|
Wolfram Koepf:
Hypergeometric
Summation. An Algorithmic Approach to Summation and
Special Function Identities, Springer
Universitext Series, 2014. XII, 253 pp., ISBN
978-1-4471-6463-0
Modern algorithmic
techniques for summation, most of which were introduced in the
1990s, are developed here and carefully implemented in the
computer algebra system Maple™.
The algorithms of
Fasenmyer, Gosper, Zeilberger, Petkovšek and van Hoeij for
hypergeometric summation and recurrence equations, efficient
multivariate summation as well as q-analogues of the
above algorithms are covered. Similar algorithms concerning
differential equations are considered. An equivalent theory of
hyperexponential integration due to Almkvist and Zeilberger
completes the book.
The combination of these results gives orthogonal polynomials
and (hypergeometric and q-hypergeometric) special
functions a solid algorithmic foundation. Hence, many examples
from this very active field are given.
The materials covered are suitable for an introductory course on
algorithmic summation and will appeal to students and
researchers alike.
Preface:
The first edition of this book appeared in 1998 and was published by Vieweg (Braunschweig/Wiesbaden). Several years later the book was sold out and no longer available. Some time ago I discussed this situation jointly with Ulrike Schmickler-Hirzebruch from Vieweg (which is now Springer-Vieweg) and with Clemens Heine from Springer Germany, and we opted for a second edition published by Springer, this publisher being better linked to the English language market.
The book covers many
algorithms for summation and integration, most of which have not
changed much in the meantime and are still up-to-date.
Fasenmyer’s algorithm for definite summation (Chapter 4) is very
old, nevertheless it is so easy to describe that it must be
included for didactical reasons. Gosper’s algorithm (Chapter 5)
solves the problem of how to find a hypergeometric
antidifference, and it is the starting point of Zeilberger’s
celebrated algorithm for definite summation (Chapter 7). The
book also covers the differential counterpart of Zeilberger’s
summation algorithm (Chapter 10) as well as its integration
counterparts (Chapters 11 and 12), and Gosper’s algorithm is the
driving force for all these algorithms. Therefore its
description remained unchanged. The other mentioned algorithms
are also still up-to-date. Therefore the above chapters have
been updated only cautiously. However, in most chapters, new
developments are cited and suggestions for further reading are
given. As in the first edition, in all chapters an introduction
to the corresponding q-theory is given.
The situation is quite different concerning the following parts of the book. Multivariate hypergeometric summation was still unfeasible when the first edition was written. In the meantime ideas by Wegschaider cleared the way. These newer developments are incorporated and illustrated in Chapter 4, and the corresponding multsum-package is introduced. Furthermore, van Hoeij’s algorithm has dramatically improved the efficiency of finding hypergeometric term solutions of holonomic recurrence equations over Petkovšek’s original approach. Therefore his ideas have been incorporated in Chapter 9 so that the reader gets a clear impression of where the new efficiency comes from. Nevertheless, the presentation of Petkovšek’s original algorithm has not been withdrawn since it is still interesting from a historical point of view. More decisively, the efficiency of van Hoeij’s algorithm can only be understood by comparison with Petkovšek’s approach. The chapter finishes with the Maple package qFPS which contains the q-case of van Hoeij’s algorithm. More details about operator factorization are given in Chapters 9 and 12. Finally there were some new developments on discrete Rodrigues formulas by my PhD student Kornelia Fischer that have been incorporated in Chapter 13.
For the first edition I
had selected Maple as the computer algebra system in which the
algorithms were programmed and demonstrated. Moreover these (and
some more) algorithms were incorporated in the packages hsum
(and qsum for the q-case). This selection has proven
successful, and since the other packages mentioned (multsum and
qFPS) are also written in Maple, Maple is still the best system
to keep the book self-contained.
On the web resource www.hypergeometric-summation.org/ all the Maple packages
• hsum.mpl (programs for hypergeometric
summation)
• qsum.mpl (programs for q-hypergeometric summation)
• multsum.mpl (programs for multiple hypergeometric summation)
• qFPS.mpl (contains the q-Petkovšek-van-Hoeij
algorithm)
and further materials such as the book’s Maple sessions are available. These packages are regularly updated to work with newer versions of Maple.
I would like to thank Mama Foupouagnigni, Jürgen Gerhard, Dieter Schmersau† and Glenn P. Tesler who had read the first edition very carefully and identified several errors that I could correct. Special thanks go to Mark van Hoeij for his warm hospitality when I visited him in November–December 2013 at Florida State University (FSU) in Tallahassee. He gave me important assistance, especially concerning Chapter 9, about his brilliant algorithm. Also special thanks go to Torsten Sprenger who updated the hsum and qsum packages, contributed the multsum (Chapter 4) and qFPS packages (Chaper 9) and incorporated the FormalPowerSeries package, which is mentioned in Chapters 10 and 13, into Maple. Finally I am very grateful to Martin Muldoon who smoothed out the English of the manuscript again.
The finalization of
this project was made possible by a sabbatical from the
University of Kassel, and by the Alexander von Humboldt
Foundation who financed my stay in the USA by awarding an alumni
research scholarship. I am very grateful for this invaluable
support. Last but not least I thank Ulrike Schmickler-Hirzebruch
from Vieweg, Clemens Heine from Springer Germany, and Lynn
Brandon from Springer London, for their good collaboration and
for making this second edition possible.
Contents:
Preface
Introduction
Chapter 1: The
Gamma Function
Chapter 2:
Hypergeometric Identities / q-Hypergeometric Identities
Chapter 3:
Hypergeometric Database / q-Hypergeometric Database
Chapter 4:
Holonomic Recurrence Equations / Multiple Summation / q-Holonomic
Recurrence Equations
Chapter 5:
Gosper's Algorithm / Linearization of Gosper's Algorithm / q-Gosper
Algorithm
Chapter 6: The
Wilf-Zeilberger Method / q-WZ Method
Chapter 7:
Zeilberger's Algorithm / q-Zeilberger Algorithm
Chapter 8:
Extensions of the Algorithms
Chapter 9: Petkovšek's
and Van Hoeij's Algorithm / q-Petkovšek-van-Hoeij
Algorithm
Chapter 10:
Differential Equations for Sums / q-Differential
Equations for Sums
Chapter 11:
Hyperexponential Antiderivatives
Chapter 12:
Holonomic Equations for Integrals
Chapter 13:
Rodrigues Formulas and Generating Functions / q-Rodrigues Formulas
References
Index
Materials for
download:
Installation of the Software:
The programs in this
book are collected in the packages hsum and qsum. The hsum
package for hypergeometric summation is contained in the file
hsum17.mpl and can be read in a Maple session by the command
read "hsum17.mpl";
or, if it resides in
the directory "directory", by
read
"directory/hsum17.mpl";
The qsum package for q-hypergeometric
summation is contained in the file qsum17.mpl and can be read in
a Maple session by
read "qsum17.mpl";
or by
read
"directory/qsum17.mpl";
if the package is located in the directory "directory". They are designed for the Maple version 17, but are also compatible with older versions. Worksheets with the Maple sessions of the book are contained in the archive Sessions-mws.zip (for the classical Maple interface) and Sessions-mw.zip. The functionalities of the hsum package are described in detail in the book. The article Algorithms for q-hypergeometric summation in computer algebra gives a description of the package qsum17.mpl and can be seen as a manual for this package, the file qsum17.mws being its accompanying Maple worksheet.
To have access also to the extensive help facility which is a contribution of Harald Böing, you need also the file hsum.hdb containing the help pages for both the hsum and the qsum packages. To make the help pages accessible, Maple must know where to find this file. Maple searches in the path given by the libname variable. On PC-platforms running Windows the default setting for libname is "C:\\Program Files (x86)\\Maple 17\\lib" or similar (which you can check by asking for libname;). Hence we recommend copying the file hsum.hdb into the directory "C:\\Program Files (x86)\\Maple 17\\lib". If you are not allowed to do so, then copy hsum.hdb in any other directory "directory" and enter
libname:="directory",libname;
in your Maple session
to have access to the help pages. On PC-platforms you should use
the complete path name; use the slash (/) or a duplicated
backslash (\\) instead of the backslash (\).
On UNIX platforms the default library usually is
`/usr/local/maple/update`,`/usr/local/maple/lib`, and you may
ask your SuperUser to install the file hsum.hdb in the directory
`/usr/local/maple/update`. On the other hand (without the
SuperUser), you can also create the file .mapleinit in your home
directory, adding the line
libname:="directory",libname;
if the file hsum.hdb
resides in the directory "directory". Then the information about
the location of the help file is auto-loaded in each session. If
you want to see the programs, you can either browse the files
hsum17.mpl and qsum17.mpl, respectively, or you can make the
code visible in a Maple worksheet by the print command. For this
purpose you have to allow the printing of copyrighted procedures
by the statement
interface(verboseproc=3);
Then print(gosper),
e.g., will print the gosper procedure.
The two packages multsum and qFPS are written in package format and must be loaded by
read "multsum.mpl";
with(multsum);
and
read "qFPS.mpl";
with(qFPS);
The article Algorithmic determination of q-power series for q-holonomic functions gives a description of the qFPS package, there is an accompanying corresponding Maple worksheet, and several demo files. The multsum package is described in Sprenger's diploma thesis Algorithmen für mehrfache Summen.
First Edition, 1998:
Wolfram Koepf:
Hypergeometric Summation. An Algorithmic Approach to Summation
and Special Function Identities, Vieweg Advanced
Lectures in Mathematics:1998. X, 230 pp, DM 72, $ 49, ISBN
3-528-06950-3.
Reviews of First Edition: Computeralgebra-Rundbrief
23 of Fachgruppe Computeralgebra, October
1998, pp. 27-28 (Volker Strehl); Zbl.
Math. 909.33001 (P. W. Karlsson); Newsletter
of the SIAM Activity Group on Orthogonal Polynomials and
Special Functions 9.3, June 1999 (Tom H.
Koornwinder); MR
2000c:33002 (Jiang Zeng).
Preface of First
Edition:
The current book is the result of a lecture course that I gave
at the Free University, Berlin, during the spring semester 1995.
This course was influenced by the remarkable book Concrete
Mathematics by Graham, Knuth and Patashnik, and by the
interesting lecture notes Identities and Their Computer
Proofs by Herbert Wilf. In the meantime these notes
have appeared together with other material in the book A=B
by Petkovšek, Wilf and Zeilberger.
In contrast to the books just mentioned, it is my objective to present the material by giving more detailed advice on implementation. Furthermore, I wished to cover not only material about recurrence equations but also about differential equations, not only about sums but also about integrals, and finally not only the hypergeometric case but also its q-analogue.
In the current book, up-to-date algorithmic techniques for summation are described in detail, and worked out using Maple programs. With Maple release V.4 and higher, some of these tools are available through Maple's sum command and sumtools package, by an implementation that I incorporated in the Maple library prior to my lecture course. In this book, readers are invited to implement the algorithms step by step. This will give them a detailed insight into the structure of the algorithms under consideration, and will enable them to solve quite involved problems.
The book covers Gosper's algorithm for indefinite hypergeometric summation and Zeilberger's algorithm for definite hypergeometric summation, as well as the WZ method and extensions of these algorithms. Petkovšek's decision procedure for hypergeometric term solutions of holonomic recurrence equations completes the picture on the summation topic.
By an analogous technique, differential equations, derivative rules and similar identities for sums can be generated, and a chapter on this topic is included. An equivalent theory of hyperexponential integration, both indefinite and definite, which was given by Almkvist and Zeilberger, completes the book.
The combination of all results considered gives work with orthogonal polynomials and (hypergeometric type) special functions a solid algorithmic foundation. Hence, many examples from this very active field are given.
Although multiple sums are briefly mentioned in Chapter 4, I have not covered the algorithmic theory of multisums, integral sums etc., which was developed by Wilf and Zeilberger. Instead, by many examples I show how the one-dimensional theory can be applied successfully to double sums and integral sums, in particular to sums and integrals involving orthogonal polynomials.
The book contains many worked examples of the algorithms considered, and Maple implementations of them are presented. Furthermore, a lot of exercises encourage the readers to do their own implementations in Maple, and to study the topics included in detail. Exercises that demand Maple implementations are marked by a diamond.
In all chapters, an introduction to the corresponding q-theory is given. Whereas in the hypergeometric case, the algorithms are rigorously presented and detailed proofs of the statements are given, in the q-case we state only the results, indicate their proofs, present Maple implementations, and give examples and exercises.
A basic knowledge of a programming language such as Pascal or C should be sufficient to understand the Maple programs and to solve the corresponding exercises since all major Maple procedures that are used are briefly described. On the other hand, a deeper familiarity with Maple might help the reader to understand the code in more detail. To obtain such a knowledge, the books [I]--[III] on p.223 might be helpful.
I could have presented the algorithms in pseudo code, without giving preference to a particular computer algebra system. On the other hand, an implementation in an existing and widely distributed computer algebra system makes the algorithms ready for execution, and therefore fills them with life. As a result, every student can execute all the examples no matter how complicated they may be.
Hence I had to decide on one of the major systems. Of the most important general purpose systems, Axiom, Macsyma, Maple, Mathematica and REDUCE, undoubtedly Maple and Mathematica have the largest audiences, since they are accessible at most universities and research institutions.
I wished to write my code as near as possible to the mathematical description of the corresponding algorithms, and since the latter depend heavily on the fast symbolic solution of (sometimes very complicated) systems of linear equations, the poor performance of Mathematica's Solve command for linear systems supported my decision to choose Maple. Furthermore Maple is much friendlier with respect to user information (e.g., the infolevel routine).
Readers who use one of these systems can access some of the algorithms considered:
Axiom: The sum command contains an implementation of Gosper's algorithm.
Macsyma: The sum command contains an implementation of Gosper's algorithm, written by Gosper.
Maple: Maple's sum command contains an implementation of Gosper's algorithm, completely rewritten by the author for Maple V.4. There are implementations of Zeilberger and Koornwinder of Zeilberger's algorithm; Almkvist and Zeilberger implemented the continuous version. Maple V.4's sumtools package was written by the author, and contains an implementation of Zeilberger's algorithm. In the present book structured implementations of Gosper's algorithm, Zeilberger's algorithm, Petkovšek's algorithm and their q-analogues are developed. Salvy and Zimmermann's Generating Functions package GFUN and Chyzak's Mgfun package are also strongly connected with the algorithms developed in the current book.
Mathematica: Implementations of Gosper's and Zeilberger's algorithms were done by Paule and Schorn, and Petkovšek implemented his algorithm and the corresponding q-version. Also Paule and Riese implemented the q-analogue of Zeilberger's algorithm. A package on multidimensional summation is due to Wegschaider. (On the web see http://www.math.upenn.edu/~wilf/progs.html and http://www.risc.jku.at/research/combinat/software/.)
REDUCE: Gosper's and Zeilberger's algorithms are accessible by an implementation of Koepf and Stölting. Böing and Koepf implemented the q-analogues of Gosper's and Zeilberger's algorithm.
The Maple programs for the current book are discussed in detail in the text. Some of the implementations are even printed in the book. The programs are collected in the package hsum, and can be obtained from here. Detailed information on how to download and install the software are given in an appendix on p. 214. Worksheets containing the examples given in the text, as well as Maple solutions of the exercises are available at the same URL. The corresponding q-analogues of Gosper's, Zeilberger's and Petkovšek's algorithms are implemented in the package qsum, written by Harald Böing, and can be obtained from the same site.
The present book is designed for use in the framework of a seminar. In seminars at German universities, every participating student is asked to present a lecture about a certain topic. The arrangement of the book makes the division into lectures easy. Each chapter covers a certain subtopic which can be presented by one or two students. Obviously the book is also suitable for a lecture course in this area since it was written in connection with such a course presented by the author. Special notational conventions used in the book are defined at their first occurrence, and are listed in the List of Symbols on page 224.
I would like to thank Peter Deuflhard, who introduced me to the study of this topic, for his support and encouragement. Furthermore, I thank Martin Grötschel, without whose support the final version would not have been possible. Thanks go to Herbert Melenk for his advice on Gröbner bases, and for his excellent REDUCE implementation. Due to his severe bicycling accident, a joint paper on noncommutative factorization is still unfinished. Also, I am very grateful for the warm hospitality of the ETH Zürich, where I visited to install my code in the Maple library, and especially to Mike Monagan, who headed the installation. Furthermore, thanks go to Tom Koornwinder for his implementation zeilb which was the starting point of my Maple implementations, and to Harald Böing who did some extensions of the implementations of this book that are covered in the hsum package as well as the q-implementation under my supervision. A few of the exercises have been collected by Torsten Thiele, and Lisa Temme corrected some of my English language mistakes. I am very grateful to Martin Muldoon who smoothed out the English of the final manuscript and to Harald Böing for the final proofreading. Last but not least I thank Ulrike Schmickler-Hirzebruch from Vieweg as well as the editor of the current book series Martin Aigner for their good collaboration and for making this project happen.
Wolfram Koepf, April
15, 1998