Stephen Melczer

CRM-ISM Postdoctoral Fellow
Laboratoire de Combinatoire et d’informatique Mathématique (LaCIM)
Université du Québec à Montréal

MATH 581 (Spring 2019)
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.


Worksheets

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)


Assignments

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


References

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.


Project Ideas


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.
https://arxiv.org/abs/1806.00968

Alin Bostan and Manuel Kauers. The complete generating function for Gessel walks is algebraic. In: Proc. Amer. Math. Soc. 138.9. 2010
https://arxiv.org/abs/0909.1965

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

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

Joris van der Hoeven. “Fast evaluation of holonomic functions near and in regular singularities”. In: J. Symbolic Comput. 31.6 (2001)
https://www.sciencedirect.com/science/article/pii/S0747717100904747

E. Rannou. “The complexity of stratification computation”. In: Discrete Comput. Geom. 19.1 (1998)
https://link.springer.com/article/10.1007%2FPL00009335

Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behaviour.  S. Melczer and M. Wilson. Submitted 2018.
https://arxiv.org/abs/1810.06170

Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
S. Melczer and B. Salvy. Proceedings of the ACM on ISSAC 201), 333-340, 2016.
http://arxiv.org/abs/1605.00402
(plus forthcoming extension which can be provided)

DeVries, T., van der Hoeven, J. and Pemantle, R. (2011). Automatic asymptotics for coefficients of smooth, bivariate rational functions. Online J. Anal. Comb., vol. 6, 24 pages.
https://www.math.upenn.edu/~pemantle/papers/bivariate.pdf

Baryshnikov, Y. and Pemantle, R. (2011). Asymptotics of multivariate sequences, part III: quadratic points. Adv. Math., vol. 228, pages 3127--3206.
https://www.math.upenn.edu/~pemantle/papers/cones.pdf

(TAKEN)
Pemantle, R. (2012). Hyperbolicity and stable polynomials in combinatorics and probability. In: Current Development in Mathematics, Proceedings of the 2011 conference, pages 57--124.

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