The goal of this topics course is to introduce you to asymptotic algebraic combinatorics. Each of these words is familiar individually, but when combined in this order the resulting phrase is ambiguous; indeed, looking at the list of lectures from a recent conference dedicated to asymptotic algebraic combinatorics, it is clear that it means different things to different people.
In this course, we will try to get a feeling for what asymptotic algebraic combinatorics is about by going on a quest: we are going to start at Stirling’s approximation, which might be considered the historically first result in asymptotic algebraic combinatorics, and from there forge a path to what physicists simply call “Large N,” which has something to do with quantum field theory. There will be various (hopefully edifying) digressions along the way, sometimes leading to unsolved problems — for example, I hope to discuss the pattern-restricted factorial, for which an analogue of Stirling’s formula is only sometimes known, and the Bhargava factorial, for which no analogue of Stirling’s formula is known at all. Let’s start the quest.
We want to estimate Let’s start by writing down the stupidest thing we can think of — that way, things can only get better.
Proposition 1: We have
Proof: By definition,
On the interval the linear function has a minimum value of at and a maximum value of at
To improve on the shameful bounds in Proposition 1, we can use a multiplicative version of Gauss’s famous “replica trick” for summing consecutive numbers.
Proposition 2: We have
Proof: Take two copies of multiply them together
write the second product backwards,
and interlace the factors of the two products to get
The minimum of the quadratic function
on the interval occurs at with
and the maximum occurs at with
Problem 1: Suppose we use replicas of meaning that we write where may be any permutations. Anything to be gained from this?
The fact that we now have a non-trivial lower bound on has some nice consequences. In particular, let us consider the prime factorization of
where the product is over distinct primes and is the multiplicity of in which is given by Legendre’s formula:
Since floors are lower than chairs and tables, we get the estimate
so that the “isotypic component” of corresponding to the prime is
Now, since we have
which gives us the estimate
with the number of primes less than or equal to In order for this to comport with the lower bound in Proposition 2, we get
which isn’t great from the perspective of actually counting primes, but it does tell you that there are infinitely many.
Another approach to estimating factorials is to use calculus: instead of squaring we take its logarithm and interpret the resulting sum as a Riemann sum.
Proposition 3: We have
where the lower and upper bounds are, respectively, lower and upper Riemann sums for the integral between them. This integral can be evaluated:
The upper bound on the integral thus yields
which is the claimed lower bound on The lower bound on the integral yields
and multiplying through by we get the claimed upper bound on
Problem 2: Which is better — Proposition 2 or Proposition 3?
Instead of comparing to an integral, we can represent it as an integral.
Proposition 4: We have
Proof: This can be proved by induction on For we have
Now, for any integrating by parts we have
Since satisfies and this gives us
The integral representation of given by Proposition 4 was found by Euler, who wanted to define for a complex variable. Indeed, the integral
converges to define a holomorphic function on the half plane so that we have an analytic factorial function on this domain. In some sense, this is the only way to define (precise statements are the Bohr-Mollerup Theorem and Wielandt’s Theorem).
This is not the direction we’re headed. For us, the main significance Euler’s integral representation is that it can be re-written as follows. Making the change of variables we get
where for and for What we want to do is to consider the generalization of the factorial function obtained by considering all integrals of the form with
a given function called the “action.” This term comes from physics, and is related to the fact that is the partition function a zero-dimensional quantum field theory with action We will see that, for drawn from a broad class of functions, the behavior of can be understood in a uniform way using a robust technique known as the Laplace method. Eventually, we will see that all such integrals admit asymptotic expansions whose coefficients can be understood in terms of certain graphs known as Feynman diagrams. Next time, we’ll work out Stirling’s formula from the integral representation of and start developing Laplace’s method in general.