# 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:
 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). Detailed plan of the lectures:
• 0- Introduction (9/9/2019). Slides.
• 1- Algebraic algorithms.
• Extended gcd and resultants (16/9/2019).
• Polynomial linear algebra I (23/9/2019).
• Polynomial linear algebra II (30/9/2019).
• Guessing equations by Hermite-Padé approximation (7/10/2019).
• 2- Algorithms for recurrence and differential equations.
• P-recursive sequences and D-finite functions: closure properties (14/10/2019). Slides.
• Nth term of a linear recurrent sequence: binary powering and binary splitting (21/10/2019). Slides.
• Algorithmic guessing of algebraic and differential equations (4/11/2019). Slides.
• Polynomial and rational solutions of linear differential/recurrence equations (18/11/2019). Slides.
• 3- Algorithms for symbolic summation and integration.
• Gosper's algorithm for indefinite summation, Zeilberger's algorithm for definite summation (25/11/2019). Demo (pdf); Demo (maple); Exercises.
• Petkovsek's algorithm for finding hypergeometric solutions of linear recurrence equations (2/12/2019). Exercises. Solutions (pdf). Solutions (maple).
• Diagonals and Creative Telescoping — from 1G to 4G algorithms (16/12/2019).
• Computer algebra for enumerative combinatorics (6/1/2020).

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 on 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. 