CO 730: Asymptotic Enumeration

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

Organization: This course will meet Monday / Wednesday / Friday from 9:30 - 10:20. The room number and further details can be found on the course outline.

Description: This course presents an introduction to the theory of analytic combinatorics in one and several variables, and computational techniques for enumeration. Depending on student interest, topics may include computer algebra tools for sequences and generating functions; diagonals of multivariate generating functions; data structures for enumeration; effective analytic methods for asymptotics; limit theorems of combinatorial objects; algorithmic transcendence proofs and transcendence of constants vs functions; polynomial amoebas and convergent series expansions; computability and complexity questions in enumeration and connections to formal languages; topological methods for asymptotics.

Assessment: Students will be evaluated on two homework assignments (each 20% of final grade) and a final project (60% 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.

Different families of combinatorial objects naturally lead to different types of generating functions, and the interplay between combinatorial structure, the algebraic nature of a generating function, and asymptotic behaviour is a running theme of the course.

Binary strings with no two consecutive 1s, counted by length: $1,\, 2,\, 3,\, 5,\, 8,\, 13,\, 21,\, 34,\dots$ (the Fibonacci numbers).

Generating function RATIONAL $$F(z) = \frac{1+z}{1-z-z^2},$$ with asymptotic behaviour $f_n \sim \frac{\varphi^{2}}{\sqrt{5}}\, \varphi^{n}$ for the golden ratio $\varphi = \frac{1+\sqrt{5}}{2} = 1.618\dots$

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 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_{n,k} 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_{n,k}$ approaches a normal distribution. In other words, as the degrees of the polynomials approach infinity the number of divisions performed by the Euclidean algorithm satisfies a central limit theorem.

A live count of the number of divisions performed when running the Euclidean algorithm on random pairs of polynomials in $\mathbb{Z}_p[x]$ with the higher degree polynomial monic of degree $n$, compared to the expected distribution from the limit curve. This simulation runs in your browser: pick your own prime and degree above and watch the histogram converge.

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?

Random walks taking North, South, East, and West steps, greyed out once they leave the first quadrant.

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 were 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 JupyterHub 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 and the sage_acsv package.

Binder

You can launch a Jupyter session with the sage_acsv package preinstalled by clicking on the above badge. No account or installation is required (startup can take a minute or two).

Note: The JavaScript elements on this webpage were coded with the help of Claude Fable.