Math 262A: Lecture 7

We continue with the $N \to \infty$ asymptotic analysis of $N!_d$ , where $d \in \mathbb{N}$ is arbitrary but fixed and $N!_d$ is the number of permutations in the symmetric group $\mathrm{S}(N)$ with no decreasing subsequence of length $d+1$ .

At the end of Lecture 6, we computed the $N \to \infty$ asymptotics of a diagram $\in \mathbf{Y}_d(dN)$ fluctuating around the canonical self-complentary diagram $R(d,N)$ (relative to the twice-larger rectangle $R(d,2N)$ , whose dimension we expect to asymptotically coincide with $(dN)!_d$ ) on a square root scale. Recall that

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

Theorem 1: For any $(y_1,\dots,y_d) \in \Omega_{d-1}$ , we have

$\lim\limits_{N \to \infty} C_d(N) \dim(N+y_1\sqrt{N},\dots,N+y_d\sqrt{N}) = e^{-S(y_1,\dots,y_d)},$

where $C_d(N)$ is

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

and $S$ is

$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).$

At the end of Lecture 5, we indicated that the action $S$ is an important special function which merits further discussion; we will have that discussion now.

What Theorem 1 reveals is the remarkable fact, as $N \to \infty$ , the dimension of a Young diagram with $\lambda \in \mathbb{Y}_d(dN)$ fluctuates on a square root scale, and the fluctuations themselves behave like a 2D Coulomb gas of $d$ identical point charges on a wire at inverse temperature $\beta=1$ and confined by a harmonic potential. Let us unpack this statement.

First, the Weyl chamber

$\mathbb{W}^d = \{(y_1,\dots,y_d) \in \mathbb{R}^d \colon y_1> \dots>y_d\}$

is the configuration space of $d$ hard particles on a wire, labeled from right to left. If $S(y_1,\dots,y_d)$ is the potential energy of this system of particles when it is in a given configuration, then the formalism of statistical mechanics says that the density which determines the probability to observe the system in a given configuration is

$\frac{1}{Z_d(\beta)} e^{-\beta S(y_1,\dots,y_d)},$

where $\beta$ is the inverse temperature and

$Z_d(\beta) = \int_{\mathbb{W}^d} e^{-\beta S(y_1,\dots,y_d)} \mathrm{d}y_1 \dots \mathrm{d}y)_d$

is the partition function which ensures that this is the density of a probability measure. The partition function corresponding to this particular $S$ is a famous integral called Mehta’s integral, and it can be computed exactly using the Selberg integral formula.

What kind of a system has energy functional $S$ as in Theorem 1? According to Coulomb’s law, the repulsive force $F$ between two identical point charges in $\mathbb{R}^n$ is inversely proportional to the distance between them raised to the power $(n-1)$ . So in our usual $n=3$ world, $F$ has an inverse square law, but in an $n=2$ world the repulsion is proportional to the reciprocal of the distance. Since energy is the integral of force, this accounts for the logarithmic terms in $S$ — they represent the electrostatic repulsion between $d$ identical two dimensional point charges confined to a wire. Left to their own devices, these charges would drift infinitely far away from each other on the unbounded wire $\mathbb{R}$ . The quadratic part of $S$ has the meaning of a harmonic potential which attracts each point charge even as they repel one another, leading to the existence of a non-trivial ground state, the minimizer of $S$ .

What configuration minimizes $S$ ? This classical problem in electrostatics was solved by Stieltjes, and the answer is: the roots of the $d$ th Hermite polynomial, aka the matching polynomial of the complete graph on $d$ vertices. Thus fluctuations of Young diagrams have something to do with the roots of Hermite polynomials. On the other hand, the Hermite polynomials themselves are orthogonal polynomials with respect to the Gaussian density, so fluctuations of Young diagrams should somehow be linked to Gaussian objects of some kind. In fact, the right objects are Gaussian random matrices.

Consider the real vector space of $d \times d$ symmetric matrices. This is a Euclidean space when equipped with the standard scalar product $\langle X,Y \rangle = \mathrm{Tr} XY$ , i.e. the scalar product with respect to which the elementary matrices $E_{ij}$ form an orthonormal basis. In particular, one can define the standard Gaussian measure on this Euclidean space by stipulating its density, $e^{-\frac{1}{2} \mathrm{Tr} X^2}$ . A random matrix with this distribution will have Gaussian random variables as its entries, and these variables are independent up to the symmetry constraint, as you can see by canonically identifying such a random matrix with a $d^2$ dimensional random vector and taking its Laplace transform. However, the eigenvalues of $x_1 > \dots > x_d$ of a $d \times d$ Gaussian random symmetric matrix are neither Gaussian nor independent: the distribution of the random vector $(x_1,\dots,x_d)$ in $\mathbb{W}^d$ has density proportional to

$e^{-S(x_1,\dots,x_d)},$

where $S$ is just as in Theorem 1. This is essentially due to a classical result of Hermann Weyl which says that the Euclidean volume of the set of $d \times d$ symmetric matrices with given eigenvalues $x_1 \geq \dots \geq d$ is proportional to the Vandermonde determinant in these eigenvalues,

$\det [x_j^{d-i}]_{1 \leq i,j \leq d} = \prod\limits_{1 \leq i<j \leq d} (x_i-x_j).$

In particular, the volume of the set of symmetric matrices with two or more equal eigenvalues is zero, as it should be, since one can see from the spectral theorem that this is not a full-dimensional subset of the space of symmetric matrices.

Theorem 1 is thus saying that Young diagram fluctuations behave like the eigenvalues $y_1>\dots > y_d$ of the traceless random matrix $Y_d = X_d - \frac{1}{d}(\mathrm{Tr}X_d)I$ . This surprising coincidence of Young diagram formulas and random matrix formulas is just the tip of a huge iceberg linking the two subjects, the culmination of which is the Baik-Deift-Johansson Theorem linking the fluctuations of the length of the longest increasing subsequence in a large random permutation with the eigenvalues of random matrices.

Concerning random matrices, the Coulomb gas with Boltzmann weight $e^{-\beta S(x_1,\dots,x_d)}$ can be interpreted as the spectrum of a $d \times d$ random matrix for all values of the inverse temperature $\beta$ . For $\beta=2,4$ , the relationship is as above: one takes Gaussian complex selfadjoint matrices with entries to get the $\beta=2$ case, and Gaussian quaternion selfadjoint matrices to get the $\beta =4$ case. For the other values of $\beta$ , the random matrix realization of the 2D Coulomb gas confined to a wire is more subtle, and was found by our colleague Ioana Dumitriu together Alan Edelman.

The above was pretty sketchy but also hopefully somewhat interesting. This being a topics course, you may want to take the time to run down some of the details (you can always ask me for further explanation, or pointers to the literature).

In our next lecture, we will complete the derivation of the first-order asymptotics of $N!_d$ . For now, you might want to ask yourself: how is this related to the symmetry

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

of the energy of the Coulomb gas, and why is this symmetry physically obvious? In the next lecture, I will also tell you a bit about the Stanley-Wilf Conjecture (now a theorem of Marcus and Tardos), which is related to the growth of an even more general factorial function $N!_\sigma$ which counts the number of permutations in $\mathrm{S}(N)$ which avoid a fixed permutation $\sigma \in \mathrm{S}(d)$ .

Math 262A: Lecture 7

Published by Jonathan Novak

Leave a Comment Cancel reply

Share this:

Like this:

Published by Jonathan Novak

Leave a Comment Cancel reply