# 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.