CO 739: Multivariate Analytic Combinatorics (Fall 2023)

This webpage will not be updated during the term. All course materials will be posted on LEARN.

Organization: This course is currently scheduled to meet Monday / Wednesday / Friday from 10:30 - 11:20 in AL 210.

Assessment: Students will be evaluated on two homework assignments (each 25% of final grade) and a final project (50% of final grade). For the final project students will write a report and make a short presentation to the class about a research paper related to their interests and the course content (other options, like a historical survey or coding project, are also possible). Deadlines for the assignments and project will be posted at the beginning of the semester, and spaced evenly throughout the term.

Prerequisites: This course may be of interest to students in a variety of areas (combinatorics, computer science, pure math, etc.) who will come in with different backgrounds. Students should be comfortable with the basics of real analysis (sequences and series) and ideally will have previous exposure to basic algebra (rings and fields) and complex analysis (analytic functions, Cauchy residue theorem), but these last two topics will not be assumed. Interested students unsure of their background should email the instructor for more information.

References: Our main references are the textbooks

and (for background) the course notes

all of which are freely available online.

A Selection of Course Topics

Some of the topics we will discuss during the semester include the following.

1. Asymptotics of Sequences

At its core, analytic combinatorics is about deriving the asymptotic behaviour of discrete structures. Examples we will see in class include

and more.

2. Limit Laws for Combinatorial Parameters

Instead of simply counting combinatorial objects by size, it is often illuminating to also keep track of different parameters. This is especially useful in the analysis of algorithms and computer algebra, as the number of polynomials of fixed degree whose coefficients come from a finite field (like the integers modulo a prime) form a finite set.

For instance, let $e_{n,k}$ denote the number of pairs of polynomials $(f,g)$ with coefficients in $\mathbb{Z}_p$ such that $f$ is monic, $n = \deg f > \deg g$, and the Euclidean gcd algorithm applied to $(f,g)$ takes $k$ steps to terminate. The Symbolic Method for generating functions shows how to write the bivariate sequence $e_{n,k}$ as the power series coefficients of a rational function (depending on the prime $p$): $$ \sum_{n,k \geq 0} e_{k,n} u^kz^n = \frac{1}{1-pz - p(p-1)uz}. $$ From here, analytic methods imply that for $n$ fixed and large the sequence $e_{k,n}$ approaches a normal distribution. In other words, as the degrees of the polynomials approach infinity the number of divisions performed by the Euclidean algorithm satsifies a central limit theorem.

A running count of the number of divisions performed when running the Euclidean algorithm on pairs of polynomials in $\mathbb{Z}_3[x]$ with the higher degree polynomial monic of degree 500, compared to the expected distribution from the limit curve. Readers can experiment with different primes and polynomial degrees using the interactive link above. This animation resets every 7 seconds. If it does not play in your browser click here.

3. Decidability and Asymptotics

Consider walks on the steps North, South, East, and West, which start at the origin and stay in the quadrant $\mathbb{N}^2$. How many such walks are there on $n$ steps? Equivalently (since there are $4^n$ unrestricted walks) what is the probability that a walk of length $n$ never leaves the first quadrant?

100 random walks of length 300, greyed out once they leave the first quadrant. Of the 100 starting walks, only one stays in the first quadrant after all 300 steps. Readers can generate their own animations using the interactive link above. This animation resets every 7 seconds. If it does not play in your browser click here.

Using tools like creative telescoping, numeric analytic continuation, and singularity analysis we will see, among other things, methods to efficiently compute the number of walks of large size and techniques to determine asymptotic behaviour.

It turns out the probability that a walk of length $n$ stays in $\mathbb{N}^2$ goes to zero like $\frac{4}{\pi n}$, which itself has further implications: for instance, the generating function for the number of walks is transcendental (it cannot be encoded with a polynomial equation) and the collection of walks cannot be recognized by a finite state machine.

Aside from some pathological cases that don’t really arise in combinatorics, asymptotics of sequences with algebraic generating functions can be computed automatically. Many two-dimensional lattice walks in a quadrant have transcendental generating functions lying in a class for which decidability of asymptotics is unknown. Asymptotic conjectures for a family of such models was proved a decade ago using multivariate representations to get around univariate decidability issues.

4. Applications of Techniques from Pure Math

One of the best things about analytic combinatorics in several variables is that it displays the depth and breadth of advanced mathematics. For instance, we will use

I do not expect students to know this material before taking the course (I estimate some students will have seen some of these topics previously, some students will have seen none of these topics, and probably no student will have seen all of these topics). Indeed, analytic combinatorics is one of the best ways to see the full use of these mathematical tools (and be inspired to learn more!).

Computer Algebra Software

Students may be expected to do some basic coding on their assignments. You are free to use any computer algebra system or programming language you wish (SageMath, Maple, Mathematica, Julia, Python, etc.). Because it is free, open source, and even possible to run in your browser with no installation, I recommend using Sage.

A short tutorial for Sage can be run in the browser at this link (after a short load time of up to a minute) or viewed as a static HTML page here.

We will mainly use Sage for examples in class. Possibilities for running Sage yourself include

  1. Installing Sage on your computer from its website (can be surprisingly tricky)
  2. Using Waterloo’s JupyerHub website (Requires Waterloo login)
  3. Signing up for a free account on the online browser-based CoCalc service
  4. Using a public cloud environment (some notebooks will be distributed like this in class)

In addition to the packages that come built-in to Sage, we will also make use of the ore_algebra package, available at this link.