# Modern Algorithms for Symbolic Summation and Integration (M2, 15 x 2h, 5 ECTS)

**Description: **
Computer Algebra, or Symbolic Computation, consists of representing and
manipulating mathematical objects on a computer in an exact way, in contrast
with the traditional scientific computing. In this course, we present a very
active research topic in Computer Algebra – the development of
*algorithms for symbolic summation and symbolic integration*. The
emergence of these algorithms has put an important family of computational
tools in the hands of discrete mathematicians, and many results that were
unaccessible in other ways have been found and proved by computer methods.
These algorithms are also nowadays unavoidable in physics, for the numerical
evaluation of special functions, and more broadly for the difficult questions
of simplification of formulas.

**Instructors: **
Alin Bostan,
Bruno Salvy,
Gilles Villard.

**Prerequisites: ** No
specialized knowledge is required, however notions on **basic algebraic
objects** (polynomials, matrices, power series) and **basic algebraic
algorithms** (Gaussian elimination, Euclidean algorithm) will be helpful.

**Objective: **
We will explain, among other things, how modern computer algebra answers the
following open problem from the book *The Art of Computer Programming,
Volume 1: Fundamental Algorithms* by Donald E. Knuth, Addison Wesley,
Reading, Massachusetts, 1968:

**[50] Develop computer programs for simplifying sums that
involve binomial coefficients.**
As an example of a recent combinatorial application of the algorithms
presented in this course, we will describe a computer-driven proof of the
following fact: the counting generating function of walks with prescribed
length, with allowed steps in the set X, starting from
the origin and confined to the quarter plane is:

• *algebraic* if X = {E, W, NE, SW} (*Gessel walks*, see figure below);

• *transcendental* if X = {N, S, NE, NW} (*trident walks*).

**Tentative plan: **

- 1- Algebraic algorithms.
- Extended gcd and resultants.
- Polynomial linear algebra.
- Fixed point equations and formal Newton iteration.

- 2- Algorithms for differential and difference equations.
- D-finite functions: closure properties.
- Guessing equations by Hermite-Padé approximation.
- Nth term of a linear recurrent sequence: binary powering and binary splitting.
- Polynomial and rational solutions of linear differential/recurrence equations.

- 3- Algorithms for symbolic summation and integration.
- Gosper's Algorithm for indefinite summation.
- Hermite's algorithm for indefinite integration.
- Sister Celine's algorithm for definite hypergeometric summation.
- Zeilberger's creative telescoping algorithm for definite hypergeometric summation.
- Pektkovsek's algorithm for finding hypergeometric solutions of linear recurrence equations.
- Grobner bases for special functions.
- Chyzak's creative telescoping algorithm for definite summation and integration.
- Creative Telescoping for rational functions using the Griffiths-Dwork method.
- Multiple binomial sums.
- Generalized Hermite reduction, creative telescoping and definite integration of D-finite functions.
- Computer algebra for enumerative combinatorics.

**Validation: ** There will be a homework assignment and a written final exam.

**Bibliography
(click on the title to go to the book's website and to the image to get the pdf)
:**

• M. Petkovsek, W. Wilf, D. Zeilberger, *A=B*, A. K. Peters, 1996.

• A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, É. Schost,
*Algorithmes Efficaces en Calcul Formel*, CreateSpace, 2017.

• J. von zur Gathen, J. Gerhard, *
Modern Computer Algebra*, Cambridge
University Press, 1999.