Math 262A: Lecture 8

Recall from Lecture 7 that the sequence of functions (f_N)_{N=1}^\infty defined on the region

\Omega_{d-1} = \{(y_1,\dots,y_d) \in \mathbb{R}^{d} \colon y_1 > \dots > y_d,\ y_1+\dots+y_d=0\}

by

f_N(y_1,\dots,y_d) = C_N(d) \dim (N+y_1\sqrt{N},\dots,N+y_d\sqrt{N}),

where

C_N(d) = (2\pi)^{\frac{d}{2}} \frac{N^{dN+\frac{d^2}{2}}}{(dN)!e^{dN}},

converges pointwise on \Omega_{d-1}: we have

\lim\limits_{N \to \infty} f_N(y_1,\dots,y_N) = e^{-S(y_1,\dots,y_d)},

where

S(y_1,\dots,y_d) = \frac{1}{2}\sum\limits_{i=1}^d y_i^2-\sum\limits_{1 \leq i< j \leq d} \log(y_i-y_j)

is the potential energy of a system of identical two-dimensional point charges on \mathbb{R} at locations y_1> \dots > y_d.

For arbitrary \beta > 0, define

N!_d^{(\beta)} = \sum\limits_{\lambda \in \mathbf{Y}_d(dN)} (\dim \lambda)^\beta,

the sum being over the set \mathbf{Y}_d(dN) of Young diagrams with dN boxes and at most d rows. According RSK, at \beta=2 this is the number of permutations in \mathrm{S}(N) with no decreasing subsequence of length N+1, and at \beta=1 it is the number of involutions satisfying the same.

We now use our limit theorem for f_N to calculate the asymptotics of N!_d^{(\beta)}. The first step is to rewrite the sum defining N!_d^{(\beta)} so that it is centered on the rectangular diagram R(d,N) \in \mathbf{Y}_d(dN), which as we have discussed in the previous lectures is the canonical self-complementary diagram relative to the twice-longer rectangle R(d,2N) which appear in Conjecture 1 of Lecture 6, which is the statement we are trying to prove. We have

C_N(d)N!_d^{(\beta)} = \sum\limits_{\substack{\frac{(d-1)N}{\sqrt{N}} \geq y_1 \geq \dots \geq y_{d-1} \geq \frac{-N}{\sqrt{N}} \\ y_i \in \frac{1}{\sqrt{N}}\mathbb{Z}}} (f_N(y_1,\dots,y_d))^\beta,

where y_d:=-(y_1+\dots+y_{d-1}). Now, the lattice \left(\frac{1}{\sqrt{N}}\mathbb{Z} \right)^{d-1} partitions \mathbb{R}^{d-1} into cells

\left[\frac{k_1}{\sqrt{N}},\frac{k_1+1}{\sqrt{N}} \right) \times \dots \left[\frac{k_N}{\sqrt{N}},\frac{k_N+1}{\sqrt{N}} \right), \quad k_i \in \mathbb{Z},

of volume \left(\frac{1}{\sqrt{N}} \right)^{d-1}, so that

\left(\frac{1}{\sqrt{N}} \right)^{d-1}C_N(d)N!_d^{(\beta)} = \left(\frac{1}{\sqrt{N}} \right)^{d-1}\sum\limits_{\substack{\frac{(d-1)N}{\sqrt{N}} \geq y_1 \geq \dots \geq y_{d-1} \geq \frac{-N}{\sqrt{N}} \\ y_i \in \frac{1}{\sqrt{N}}\mathbb{Z}}} (f_N(y_1,\dots,y_d))^\beta

is a Riemann sum for the integral

\int\limits_{\Omega_{d-1}} f_N(y_1,\dots,y_N)^\beta \mathrm{d}y_1 \dots \mathrm{d}y_{d-1}.

We thus have that

\lim\limits_{N \to \infty} \left(\frac{1}{\sqrt{N}} \right)^{d-1}C_N(d)N!_d^{(\beta)}\left(\frac{1}{\sqrt{N}} \right)^{d-1} = \int\limits_{\Omega_{d-1}} \lim\limits_{N \to \infty} f_N(y_1,\dots,y_N)^\beta \mathrm{d}y_1 \dots \mathrm{d}y_{d-1}\\ = \int\limits_{\Omega_{d-1}} \lim\limits_{N \to \infty} e^{-\beta S(y_1,\dots,y_d)}\mathrm{d}y_1 \dots \mathrm{d}y_{d-1},

by the dominated convergence theorem. Thus, we have found the N \to infty asymptotics of N!_d^{(\beta)} if we can evaluate the integral on the right, which up to the linear constraint y_1+\dots+y_d=0 is the partition function of the system of the two-dimensional Coulomb gas we have been discussing. This integral is not particularly easy to evaluate, and to compute it one needs to know some version of the Selberg integral formula.

In fact, we don’t have to evaluate the integral to prove Conjecture 1 if we take advantage of symmetry. Define the sum

S_N(d,\alpha,\beta) = \sum\limits_{\substack{\mu \in \mathbf{Y}_d(dN) \\ \mu \subset R(d,2N)}} (\dim \mu)^\alpha (\dim \mu^*)^{\beta-\alpha},

where 0 \leq \alpha \leq \beta and \mu^* is the complement of \mu \subset R(d,2N). Repeating the argument above essentially verbatim (change variables from \lambda_i \in \mathbb{Z}_{\geq 0} to y_i \in N^{-1/2}\mathbb{Z} in the sum and scale by the mesh volume), we find that

\lim\limits_{N \to \infty} \left(\frac{1}{\sqrt{N}}\right)^{d-1} C_N(d) S_N(d,\alpha,\beta) = \int\limits_{\Omega_{d-1}} e^{-\alpha S(y_1,\dots,y_d)} e^{-(\beta-\alpha)S(-y_d,\dots,-y_1)} \mathrm{d}y_1 \dots \mathrm{d}y_{d-1}.

This integral is even worse than the last one, but we claim that in fact the two are equal:

\int\limits_{\Omega_{d-1}}  e^{-\beta S(y_1,\dots,y_d)}\mathrm{d}y_1 \dots \mathrm{d}y_{d-1} = \int\limits_{\Omega_{d-1}} e^{-\alpha S(y_1,\dots,y_d)} e^{-(\beta-\alpha)S(-y_d,\dots,-y_1)} \mathrm{d}y_1 \dots \mathrm{d}y_{d-1}.

This follows immediately if we can show that the action S has the symmetry

S(y_1,\dots,y_d) = S(-y_d,\dots,-y_1).

This in turn is physically obvious: reflecting each point charge relative the the attractive harmonic potential preserves the distance of each particle to the potential, as well as the distance between every pair of particles, and hence does not change the potential energy of the system (Exercise: prove this algebraically). We have thus proved the following generalization of Conjecture 1 from Lecture 6.

Theorem 1: For any d \in \mathbb{N} and 0 \leq \alpha \leq \beta, we have that

N!_d^{(\beta)} \sim S_N(d,\alpha,\beta)

as N \to \infty. In particular, taking \alpha=1 and \beta =2 we get

N!_d \sim \dim R(d,2N)

as N \to \infty.

The moral of this story is that using physical intuition to guide mathematical reasoning can be quite useful. This is just a small example. For something more challenging, you might try the following exercise suggested by Polya and Szego. Let me know if you solve it.

Exercise 1: Prove the Riemann hypothesis by showing that the imaginary coordinates of the non-trivial zeros of the zeta function are the energy levels of a quantum mechanical system, i.e. the eigenvalues of the selfadjoint operator which is the Hamiltonian of the system.

The fact that we can obtain the N \to \infty asymptotics of N!_d is really a consequence of the fact that we can describe this combinatorial function as a sum over Young diagrams. One could try various other versions of this. For example, let \sigma \in \mathrm{S}(d+1) be any fixed permutation, and define N!_\sigma to the the number of permutations \pi in the symmetric group \mathrm{S}(N) which avoid \sigma, meaning that no subsequence of \pi, when written in one-line notation, is order isomorphic to \sigma. Our exactly solvable function N!_d corresponds to choosing \sigma to be the reverse identity permutation, i.e. the Coxeter element in the Weyl group \mathrm{S}(d+1)=A_d. Not much is known about the N \to \infty asymptotics of the generalized factorial N!_\sigma for other choices of \sigma. The growth of this function is the subject of the Stanley-Wilf ex-conjecture, which asserts that N!_\omega \leq C_\sigma^N where C_\sigma > 0 does not depend on N. Stirling’s formula tells us that this is false for N!, which exhibits super-exponential growth, and the theorem of Regev we have proved over the course of the last few lectures tells us that this is true for N!_d.

The Stanley-Wilf conjecture was proved by Adam Marcus and Gabor Tardos in 2002. Their proof gives a value for C_\sigma which is exponential in d. On the other hand, we know from the asymptotics of N!_d, which we can explicitly compute, that in this case C_\sigma is polynomial in d (Exercise: check this by computing the asymptotics of \dim R(d,2N) using the usual Stirling formula (Hint: this was already suggested as an Exercise in Lecture 5)). For a while, it was believed that C_\sigma should be of polynomial growth for all choices of \sigma. This was disproved by Jacob Fox, who showed that in a certain precise sense C_\sigma is almost always of exponential growth. So N!_d really is special among pattern avoiding generalizations of the factorial function.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s