Math 262A: Lecture 1

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 N!. Let’s start by writing down the stupidest thing we can think of — that way, things can only get better.

Proposition 1: We have

1 \leq N! \leq N^N.

Proof: By definition,

N! = \prod\limits_{x=1}^N x.

On the interval [1,N], the linear function l(x) = x has a minimum value of 1 at x=1, and a maximum value of N at x=N.

— Q.E.D.

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

N^{N/2} \leq N! \leq \left(\frac{N+1}{2} \right)^N.

Proof: Take two copies of N!, multiply them together

N! \cdot N! = \prod\limits_{x=1}^Nx \cdot \prod\limits_{x=1}^N x,

write the second product backwards,

N! \cdot N! = \prod\limits_{x=1}^Nx \cdot \prod\limits_{x=1}^N (N-x+1),

and interlace the factors of the two products to get

(N!)^2 = \prod\limits_{x=1}^N x(N-x+1).

The minimum of the quadratic function

q(x) = x(N-x+1) = -(x-\frac{1}{2}(N+1))^2 +\frac{1}{4}(N+1)^2

on the interval [1,N] occurs at x=1, with

q(1) = N,

and the maximum occurs at x=\frac{1}{2}(N+1), with


— Q.E.D.

Problem 1: Suppose we use k replicas of N!, meaning that we write (N!)^k = \prod\limits_{x=1}^N \prod\limits_{j=1}^k\pi_j(x), where \pi_1,\dots,\pi_k \in \mathrm{S}(N) may be any permutations. Anything to be gained from this?

The fact that we now have a non-trivial lower bound on N! has some nice consequences. In particular, let us consider the prime factorization of N!,

N! = \prod\limits_p p^{e_p(N!)},

where the product is over distinct primes p and e_p(N!) is the multiplicity of p in N!, which is given by Legendre’s formula:

e_p(N!) = \sum\limits_{k=0}^\infty \lfloor \frac{N}{p^k} \rfloor.

Since floors are lower than chairs and tables, we get the estimate

e_p(N!) < \sum\limits_{k=0}^\infty \frac{N}{p^k}=\frac{N}{p-1},

so that the “isotypic component” of N! corresponding to the prime p is

p^{e_p(N!)} < p^{\frac{N}{p-1}}.

Now, since p \leq 2^{p-1}, we have

p^{e_p(N!)} < 2^N,

which gives us the estimate

N! < 2^{N\pi(N)}

with \pi(N) the number of primes less than or equal to N. In order for this to comport with the lower bound in Proposition 2, we get

\pi(N) > \frac{1}{2} \log_2 N,

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 N!, we take its logarithm and interpret the resulting sum as a Riemann sum.

Proposition 3: We have

e\left(\frac{N}{e}\right)^N \leq N! \leq eN\left(\frac{N}{e}\right)^N.

Proof: Write

\sum\limits_{x=1}^{N-1} \log(x) \leq \int\limits_1^N \log(x) \mathrm{d}x \leq \sum\limits_{x=1}^{N} \log(x),

where the lower and upper bounds are, respectively, lower and upper Riemann sums for the integral between them. This integral can be evaluated:

\int\limits_1^N \log(x) \mathrm{d}x = N \log N - N +1.

The upper bound on the integral thus yields

e^{N \log N - N +1} \leq N!,

which is the claimed lower bound on N!. The lower bound on the integral yields

(N-1)! \leq e^{N \log N - N +1},

and multiplying through by N we get the claimed upper bound on N!.

— Q.E.D.

Problem 2: Which is better — Proposition 2 or Proposition 3?

Instead of comparing N! to an integral, we can represent it as an integral.

Proposition 4: We have

N! = \int_0^\infty t^N e^{-t} \mathrm{d}t.

Proof: This can be proved by induction on N. For N=0, we have

\int_0^\infty e^{-t} \mathrm{d}t = -e^{-t}|_{t=0}^{t=\infty}=1 = 0!.

Now, for any N \in \mathbb{N}, integrating by parts we have

\int t^N e^{-t} \mathrm{d}t = -t^Ne^{-t} - N\int t^{N-1} e^{-t}\mathrm{d}t.

Since f(t)=z^Ne^{-t} satisfies f(0)=0 and \lim_{t \to \infty} f(t) =0, this gives us

\int_0^\infty t^N e^{-t} \mathrm{d}x = N\int_H t^{N-1} e^{-t} \mathrm{d}t = N(N-1)! = N!.

— Q.E.D.

The integral representation of N! given by Proposition 4 was found by Euler, who wanted to define z! for z a complex variable. Indeed, the integral

z! := \int_0^\infty t^z e^{-t} \mathrm{d}t

converges to define a holomorphic function on the half plane H=\{ z\in \mathbb{C} \colon \Re z >0\}, so that we have an analytic factorial function on this domain. In some sense, this is the only way to define z! (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 x=\frac{1}{N}t, we get

N! = N^{N+1} \mathcal{Z}_N(S),


Z_N(S) = \int_\mathbb{R} e^{-NS(x)} \mathrm{d}x,

where S(x) = x - \log x for x>0 and S(x)=\infty for x \leq 0. What we want to do is to consider the generalization of the factorial function obtained by considering all integrals of the form Z_N(S) with

S \colon \mathbb{R} \to \mathbb{R}.

a given function called the “action.” This term comes from physics, and is related to the fact that Z_N(S) is the partition function a zero-dimensional quantum field theory with action S. We will see that, for S drawn from a broad class of functions, the N \to \infty behavior of Z_N(S) 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 N!, and start developing Laplace’s method in general.


Leave a Reply