Math 262A: Lecture 2

We continue with the estimation of N! for large N via Euler’s integral,

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

As at the end of Lecture 1, we make the substitution t=Nx, thereby obtaining

N! = \int_0^\infty (Nx)^N e^{-Nx} N\mathrm{d}x = N^{N+1} \int_0^\infty e^{-N(x-\log x)} \mathrm{d}x.

Now, one way to characterize an algebraic combinatorialist is to say that such a person loathes \log x, this being some horrible transcendental thing, but loves \log(1+x), this being an exponential generating function for cyclic permutations:

\log(1+x) = \sum\limits_{d=1}^\infty (-1)^{d-1} (d-1)! \frac{x^d}{d!} = \sum\limits_{d=1}^\infty (-1)^{d-1} \frac{x^d}{d}.

Accordingly, we make the further change of variables x=1+w, which gets us to the formula

N!= \frac{N^{N+1}}{e^N} \int_{-1}^\infty e^{-N(w-\log (1+w))} \mathrm{d}w.

We now focus on the problem of determining the N \to \infty asymptotics of

I_N = \int_{-1}^\infty e^{-NS(w)} \mathrm{d}w,

where the “action” S(w) = w-\log(1+w) is a smooth function on (-1,\infty), the Maclaurin series of which is

S(w) = \frac{w^2}{2} - \frac{w^3}{3} + \frac{w^4}{4} - \dots.

Exercise 1: What is the radius of convergence of this series?

Having solved Exercise 1 (which is singularly easy), you know that the series expansion of S(w) is only valid in a neighborhood of w=0, so ostensibly is not of any help in the estimation of I_N, since the integrand involves S(w) with arbitrarily large inputs w. On the other hand, we’re trying to work out an approximation, not perform an exact evaluation, so perhaps we can get away with something local. Indeed, the shape of S indicates that this might well be the case. Since

S'(w) = 1- \frac{1}{1+w},

our action S has a unique stationary point at w=0, and the value S(0)=0 is the global minimum of S on its domain of definition, (-1,\infty).

Plot of S(w) near w=0.

This means that e^{-NS(0)}=1 is the global maximum of e^{-NS(w)}, the integrand of I_N: we have

0 < e^{-NS(w)} < 1 \quad \forall w \in (-1,\infty)-\{0\},

In particular the integrand of I_N is exponentially smaller than 1 for all w \neq 0. This means that the integrand of I_N is sharply peaked at the unique minimizer w=0 of the action S(w), and the larger N is, the more exaggerated this effect becomes, as in the plots below.

Plot of e^{-10S(w)} near w=0.
Plot of e^{-1000S(w)} near w=0.

Accordingly, we expect that as N \to \infty the integral I_N “localizes” at the stationary point of the action meaning that

I_N \approx e^{-NS(0)}

might not be such a bad approximation. Let us investigate this more closely: we fix \varepsilon >0, and seek to estimate the integral

\int_{-\varepsilon}^{+\varepsilon} e^{-NS(w)} \mathrm{d}w.

Being combinatorialists, we will count the complement, meaning that we will try to estimate the above integral by instead estimating

\int_{-1}^{-\varepsilon} e^{-NS(w)} \mathrm{d}w \quad\text{ and }\quad \int_{+\varepsilon}^{+\infty} e^{-NS(w)} \mathrm{d}w.

To estimate the left integral, observe that left of zero we have

S(w) > \frac{w^2}{2},

and hence

\int_{-1}^{-\varepsilon} e^{-NS(w)} \mathrm{d}w < \int_{-1}^{-\varepsilon} e^{-\frac{N}{2}w^2} \mathrm{d}w < \int_{-\infty}^{-\varepsilon} e^{-\frac{N}{2}w^2} \mathrm{d}w,

where the rightmost integral is convergent (say, by comparison with \int_{-\infty}^{-\varepsilon} e^{-\frac{N}{2}w} \mathrm{d}w). To control the rightmost integral, we can observe that

e^{-\frac{N}{2}w^2} = e^{-\frac{N}{4}w^2}e^{-\frac{N}{4}w^2} \leq e^{-\frac{N}{4}\varepsilon^2}e^{-\frac{N}{4}w^2}

for w \in (-\infty,-\varepsilon), so that we have the bound

\int_{-1}^{-\varepsilon} e^{-NS(w)} \mathrm{d}w < C_ Ne^{-\frac{N}{4}\varepsilon^2}

where

C_N = \int_{-\infty}^{-\varepsilon} e^{-\frac{N}{4}w^2} \mathrm{d}w < \infty

satisfies

\lim\limits_{N \to \infty} C_N=0

by the Bounded Convergence Theorem. In particular, we can conclude that

\int_{-1}^{-\varepsilon} e^{-NS(w)} \mathrm{d}w = O(e^{-\varepsilon N}).

Now we estimate the \int_{+\varepsilon}^{+\infty}-integral using a similar strategy Since S(w) is strictly increasing for w>0, we have

e^{-NS(w)} = e^{-\frac{N}{2}S(w)}e^{-\frac{N}{2}S(w)} \leq e^{-\frac{N}{2}S(\varepsilon)}e^{-\frac{N}{2}S(w)}

for w \in (\epsilon,\infty). Consequently, we have the bound

\int_{+\varepsilon}^{+\infty} e^{-NS(w)} \mathrm{d}w < C_N(\varepsilon)e^{-\frac{N}{2}S(\varepsilon)},

where

C_N(\varepsilon) = \int_{+\varepsilon}^{+\infty} e^{-\frac{N}{2}S(w)} \mathrm{d}w <\infty

is a convergent integral, and moreover

\lim\limits_{N \to \infty} C_N(\varepsilon) = 0

by the Bounded Convergence Theorem. So we similarly have that

\int_{+\varepsilon}^\infty e^{-NS(w)} \mathrm{d}w = O(e^{-\frac{S(\varepsilon}{2} N}).

We thus conclude that

I_N = \int_{-\varepsilon}^{+\varepsilon} e^{-NS(w)} \mathrm{d}w + \text{exponentially decaying error in }N.

Just to remind ourselves where we are vis-a-vis our principal goal of approximation N!, we have arrived at the estimate

N! = \frac{N^{N+1}}{e^N}\left( \int_{-\varepsilon}^{+\varepsilon} e^{-NS(w)} \mathrm{d}w + \text{exponentially decaying error in }N\right).

It remains to estimate the \int_{-\varepsilon}^{+\varepsilon} integral. This is ostensibly more difficult than what we did above, since it apparently requires some actual insight into the behavior of S(w). On the other hand, we are now reduced to considering the behavior of the action on a small interval where we can represent it as a series: we have that

\int_{-\varepsilon}^{+\varepsilon} e^{-NS(w)} \mathrm{d}w = \int_{-\varepsilon}^{+\varepsilon} e^{-N\sum_{d=2}^\infty (-1)^d \frac{w^d}{d}} \mathrm{d}w

for all \varepsilon sufficiently small. Now, since

S(w) = \frac{w^2}{2} + O(w^3) \quad\text{ as }w \rightarrow 0,

we expect a further approximation of the form

\int_{-\varepsilon}^{+\varepsilon} e^{-NS(w)} \mathrm{d}w \approx \int_{-\varepsilon}^{+\varepsilon} e^{-\frac{N}{2}w^2} \mathrm{d}w.

Of course, such an approximation is not exactly true, and we have to understand how accurate it actually is in order to proceed rigorously. For now, however, let us see what would happen if we had the exact identity

\int_{-\varepsilon}^{+\varepsilon} e^{-NS(w)} \mathrm{d}w ``="\int_{-\varepsilon}^{+\varepsilon} e^{-\frac{N}{2}w^2} \mathrm{d}w,

where the quotes are meant to indicate that we are considering a hypothetical truth which we know to be false, but might still be conceptually useful.

Consider the integral

\int_{-\varepsilon}^{+\varepsilon} e^{-\frac{N}{2}w^2} \mathrm{d}w,

which we would like to approximate. An ideal outcome would be that we could exactly evaluate it. Unfortunately, even though the integrand here doesn’t look so bad, trying to compute the indefinite integral

\int e^{-\frac{w^2}{2}} \mathrm{d}w

is a fool’s errand, being in some sense analogous to trying to solve the quintic. On the other hand, by the same sort of rough estimates we have been using so far in this lecture, we have

\int_{-\varepsilon}^{+\varepsilon} e^{-\frac{N}{2}w^2} \mathrm{d}w =\int_{-\infty}^{+\infty} e^{-\frac{N}{2}w^2} \mathrm{d}w + \text{exponentially decaying error in }N.

The integral

\int_\mathbb{R} e^{-x^2} \mathrm{d}x,

which is known as the Gaussian integral, can in fact be exactly evaluated — not using the Fundamental Theorem of Calculus, but by exploiting symmetry. The answer is

\int_\mathbb{R} e^{-x^2} \mathrm{d}x = \sqrt{\pi},

a remarkable formula which is the basis of various amusing proclamations, including Lord Kelvin‘s assertion that “a mathematician is one to whom this is as obvious as that twice two makes four is to you.” I leave you to either try the derivation of this formula on your own, or look it up somewhere.

Changing variables in the Gaussian integral, we get the evaluation we actually need:

\int_{-\infty}^{+\infty} e^{-\frac{N}{2}w^2} \mathrm{d}w = \sqrt{\frac{2\pi}{N}}.

Following through on our thought experiment, this would imply the approximation

N! = \sqrt{2\pi}\frac{N^{N+\frac{1}{2}}}{e^N}\left(1 + \text{exponentially decaying error in }N\right).

The meat of this formula is correct, but the error term is the result of our wishful thinking, and it is false — we will correct it in Lecture 3.

Published by Jonathan Novak

Mathematician and Cormac McCarthy enthusiast.

3 Comments

Leave a Reply