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

Multiple binomial sums

Context: This is a research course, labelled CR06, from the Master 2 in Computer Science program, of the Computer Science Department of the Ecole Normale Supérieure in Lyon.
The lectures will be delivered on Mondays and Wednesdays, during the period 7/9/2020 and 2/11/2020.

Instructors: Alin Bostan, Bruno Salvy, Gilles Villard.

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

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).
Gessel Walks


Detailed plan of the lectures:


Validation: There will be a mid-term exam or a homework assignment (We 7/10/2020) and a written final exam (Mo 9/11/2020).

Bibliography:

ARTICLES (click on the title to get the pdf):
• G. Villard: On computing the resultant of generic bivariate polynomials. ISSAC'18, 391‐398, ACM Press, 2018.
• W. Zhou, G. Labahn: Efficient algorithms for order basis computation. J. Symbolic Comput. 47 (2012), no. 7, 793‐819.
• A. Storjohann:High-order lifting and integrality certification. J. Symbolic Comput. 36 (2003), no. 3-4, 613‐648.
• W. Zhou, G. Labahn, A. Storjohann: A deterministic algorithm for inverting a polynomial matrix. J. Complexity 31 (2015), no. 2, 162‐173.
• G. Labahn, V. Neiger, W. Zhou: Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix. J. Complexity 42 (2017), 44‐71.

• A. Benoit, A. Bostan, J. van der Hoeven: Quasi-optimal multiplication of linear differential operators. FOCS 2012, 524‐530, IEEE Computer Soc., 2012.
• A. Bostan, F. Chyzak, Z. Li, B. Salvy: Fast computation of common left multiples of linear ordinary differential operators. ISSAC'12, 99‐106, ACM Press, 2012.
• J. van der Hoeven: On the complexity of skew arithmetic. Appl. Algebra Engrg. Comm. Comput. 27 (2016), no. 2, 105‐122.
• A. Bostan, T. Cluzeau, B. Salvy: Fast algorithms for polynomial solutions of linear differential equations. ISSAC'05, 45‐52, ACM Press, 2005.
• A. Bostan, F. Chyzak, T. Cluzeau, B. Salvy: Low complexity algorithms for linear recurrences. ISSAC'06, 31‐38, ACM Press, 2006.

• F. Chyzak: An extension of Zeilberger's fast algorithm to general holonomic functions. Discrete Math. 217 (2000), no. 1-3, 115‐134.
• A. Bostan, S. Chen, F. Chyzak, Z. Li: Complexity of Creative Telescoping for Bivariate Rational Functions. ISSAC'10, pp. 203‐210, ACM Press, 2010.
• A. Bostan, P. Lairez, B. Salvy: Creative telescoping for rational functions using the Griffiths-Dwork method. ISSAC'13, pp. 93‐100, ACM Press, 2013.
• A. Bostan, P. Lairez, B. Salvy: Multiple binomial sums. J. Symbolic Comput. 80 (2017), part 2, 351‐386.
• A. Bostan, F. Chyzak, P. Lairez, B. Salvy: Generalized Hermite Reduction, Creative Telescoping and Definite Integration of D-Finite Functions. ISSAC'18, pp. 95‐102, ACM Press, 2018.


BOOKS (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. AeqB
• A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, É. Schost, Algorithmes Efficaces en Calcul Formel, CreateSpace, 2017. AECF
• J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 1999. MCA