Université du Québec à Montréal

Algorithmic Combinatorics and Symbolic Computation

This course provides an introduction to computational and symbolic combinatorics, focused on effective computation and connections to various areas of mathematics. Topics will be tailored to student interests and include: basics of enumerative combinatorics and computer algebra; computer algebra tools for generating functions; effective analytic methods for asymptotics (residue computations, saddle point integrals, etc.); algorithmic transcendence proofs and transcendence of constants vs functions; rational, algebraic, D-finite, differential-algebraic and hypertranscendental functions, and their algebraic/analytic/arithmetic properties; computability and complexity questions in enumeration and connections to formal languages; Morse-theoretic methods for asymptotics; rigorous numerical analytic continuation of functions.

Familiarity with advanced methods in symbolic computation / computer algebra will not be assumed, however students taking this course for credit will be expected to perform basic coding in a computer algebra system (Maple, Sage, Mathematica, etc.). Evaluation will consist of 2 homework assignments during the semester, together with a final presentation on a research paper.

**Date and Time:** 12:00-1:30pm on Tuesdays and Thursdays in DRL 4C4

**Expected Background:** Students should be comfortable with the basics of real analysis (especially sequences and series), complex analysis (analytic functions, Cauchy residue theorem), and algebra (linear algebra, rings and fields). Exposure to courses in computer science, combinatorics, probability theory, or computer algebra would be beneficial. Interested students unsure of their background should email the instructor for more information.

Class One

Class Two

Class Three

Class Eight

Class Nine

Class Eleven

Binomial Coefficient ODE Analysis (Sage)

Second ODE Analysis (Sage)

Lattice Path ODE Analysis (Sage)

Guessing ODEs (Sage)

The first assignment can be downloaded
HERE .
Assignment 1 was due Thursday February 21.

The secpnd assignment can be downloaded
HERE .
Assignment 2 is due **Thursday April 4**.

Please tell me / meet with me to discuss the topic of your
final project by the week of March 18 (either one of the
papers below, or another related topic if you have one not
on the list in mind). The final project will consist of an
~15 minute presentation to the class about a paper / topic
of your choice, and a short 10-15 page summary. The summary
should give an overview of the main results and
applications, with perhaps a rough idea of how the results
are proved. Pretend you are trying to "sell" the paper and
get the rest of the students in our class interested in what
it's trying to discuss.

Student presentations will take place April 18, 23, 25, and
30 (3 or 4 presentations each day).

The main reference for this class is a manuscript draft which
will be distributed, based on the PhD thesis:

**Analytic Combinatorics in Several Variables: Effective
Asymptotics and Lattice Path Enumeration**

S. Melczer. PhD Thesis, University of Waterloo and ENS Lyon,
2017.

https://arxiv.org/abs/1709.05051

Additional details on certain topics can be found in the
following sources, all of which are freely available.

**Analytic Combinatorics**

P. Flajolet and B. Sedgewick. Cambridge University Press,
2009.

http://ac.cs.princeton.edu/home/

**Generatingfunctionology**

H. Wilf. Academic Press, 1990.

https://www.math.upenn.edu/~wilf/DownldGF.html

**Analytic Combinatorics in Several Variables**

R. Pemantle and M. Wilson. Cambridge University Press, 2013.

https://www.math.upenn.edu/~pemantle/papers/ACSV.pdf

**Algorithmes Efficaces en Calcul Formel [Efficient
Algorithms in Computer Algebra]**

A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B.
Salvy and E. Schost, 2017.

https://hal.archives-ouvertes.fr/AECF/

(In French)

Additional (not freely available) sources:

**Enumerative Combinatorics (volumes 1 and 2)**

R. Stanley. Cambridge University Press, 1986 and 1999.

**Combinatorial Species and Tree-like Structures**

F. Bergeron, G. Labelle, P. Leroux. Cambridge University
Press, 1998.

The final project will consist of a summary of a research
paper / papers together with a 15 minute presentation to the
class. The following list contains papers that would make good
potential projects (in no particular order):

Cyril Banderier and Michael Drmota. Formulae and asymptotics
for coefficients of algebraic functions. Combin. Probab.
Comput., 24(1):1–53, 2015.

**https://lipn.univ-paris13.fr/~banderier/Papers/Alg.pdf**

E.Barcucci, A.DelLungo, A.Frosini, and S.Rinaldi. A technology
for reverse-engineering a combinatorial problem from a
rational generating function. Adv. in Appl. Math., 26(2):129–
153, 2001.

**https://www.sciencedirect.com/science/article/pii/S0196885800907115**

Philippe Flajolet. Analytic models and ambiguity of
context-free languages. Theoret. Comput. Sci.,
49(2-3):283–309, 1987.

**http://www.cs.umd.edu/~gasarch/BLOGPAPERS/ambcfl.pdf**

Scott Garrabrant and Igor Pak. Pattern avoidance is not
p-recursive. 2015.

**https://arxiv.org/abs/1505.06508**

Charlotte Hardouin. Galoisian approach to differential
transcendence. In Galois theories of linear difference
equations: an introduction, volume 211 of Math. Surveys
Monogr.

**http://www.math.univ-toulouse.fr/~hardouin/notescolombiacharlotte.pdf**

Marc Mezzarobba. Rigorous multiple-precision evaluation of
D-finite functions in SageMath.

**https://arxiv.org/abs/1607.01967**

Marc Mezzarobba and BrunoSalvy. Effective bounds for
P-recursive sequences. J.Symbolic Comput., 45(10):1075–1096,
2010.

**https://arxiv.org/abs/0904.2452**

Joël Ouaknine and James Worrell. Positivity problems for
low-order linear recurrence sequences. In Proceedings of the
Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 366–379. ACM, New York, 2014.

**http://www.cs.ox.ac.uk/james.worrell/soda_final.pdf**

Joël Ouaknine and James Worrell. Ultimate positivity is
decidable for simple linear recurrence sequences. In Automata,
languages, and programming. Part II, volume 8573 of Lecture
Notes in Comput. Sci., pages 330–341. Springer, Heidelberg,
2014.

**http://www.cs.ox.ac.uk/james.worrell/ultimate4.pdf**

(TAKEN)

Herbert S. Wilf and Doron Zeilberger. Rational functions
certify combinatorial identities. J. Amer. Math. Soc.,
3(1):147–158, 1990.

**http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/rational.pdf**

Boris Adamczewski and Jason P. Bell. Diagonalization and
rationalization of algebraic Laurent series. Ann. Sci. Éc.
Norm. Supér. (4), 46(6):963–1004, 2013.

**http://adamczewski.perso.math.cnrs.fr/Diagonals_Final.pdf**

Alin Bostan, Louis Dumont, and Bruno Salvy. Algebraic
diagonals and walks: algorithms, bounds, complexity. J.
Symbolic Comput., 83:68–92, 2017.

**https://www.lptmc.jussieu.fr/files/ABDELAZIZ/Dumont2.pdf**

Alin Bostan, Pierre Lairez, and Bruno Salvy. Multiple binomial
sums. J. Symbolic Comput., 80(part 3):351–386, 2017.

**https://arxiv.org/abs/1510.07487**

Scott Garrabrant and Igor Pak. Counting with irrational tiles.
ArXiv e-prints, 2014.

**https://arxiv.org/abs/1407.8222**

Maxim Kontsevich and Don Zagier. Periods. In Mathematics
unlimited—2001 and beyond, pages 771–808. Springer, Berlin,
2001.

**https://www.maths.ed.ac.uk/~v1ranick/papers/kontzagi.pdf**

Pierre Lairez. Computing periods of rational integrals. Math.
Comp., 85(300):1719–1752, 2016.

**https://arxiv.org/abs/1404.5069**

Robin Pemantle and Mark C. Wilson. Twenty combinatorial
examples of asymptotics derived from multivariate generating
functions. SIAM Rev., 50(2):199–272, 2008.

**https://arxiv.org/abs/math/0512548**

Alfred van der Poorten. A proof that Euler missed...Apéry’s
proof of the irrationality of ζ(3). Math. Intelligencer,
1(4):195–203, 1978/79

**http://pracownicy.uksw.edu.pl/mwolf/Poorten_MI_195_0.pdf
**Alin Bostan, Mireille Bousquet-Mélou, and Stephen
Melczer. Walks with large steps in an orthant. Submitted 2018.

Alin Bostan and Manuel Kauers. The complete generating function for Gessel walks is algebraic. In: Proc. Amer. Math. Soc. 138.9. 2010

Alin Bostan, Kilian Raschel, and Bruno Salvy. “Non-D-finite excursions in the quarter plane”. In: J. Combin. Theory Ser. A 121 (2014)

Stéphane Fischler and Tanguy Rivoal. “On the values of G-functions”. In: Comment. Math. Helv. 89.2 (2014)

Joris van der Hoeven. “Fast evaluation of holonomic functions near and in regular singularities”. In: J. Symbolic Comput. 31.6 (2001)

E. Rannou. “The complexity of stratification computation”. In: Discrete Comput. Geom. 19.1 (1998)

Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behaviour. S. Melczer and M. Wilson. Submitted 2018.

S. Melczer and B. Salvy. Proceedings of the ACM on ISSAC 201), 333-340, 2016.

http://arxiv.org/abs/1605.00402

https://www.math.upenn.edu/~pemantle/papers/bivariate.pdf

https://www.math.upenn.edu/~pemantle/papers/hyperbolic.pdf