Recall from Lecture 7 that the sequence of functions defined on the region
converges pointwise on : we have
is the potential energy of a system of identical two-dimensional point charges on at locations .
For arbitrary , define
the sum being over the set of Young diagrams with boxes and at most rows. According RSK, at this is the number of permutations in with no decreasing subsequence of length , and at it is the number of involutions satisfying the same.
We now use our limit theorem for to calculate the asymptotics of . The first step is to rewrite the sum defining so that it is centered on the rectangular diagram , which as we have discussed in the previous lectures is the canonical self-complementary diagram relative to the twice-longer rectangle which appear in Conjecture 1 of Lecture 6, which is the statement we are trying to prove. We have
where . Now, the lattice partitions into cells
of volume , so that
is a Riemann sum for the integral
We thus have that
by the dominated convergence theorem. Thus, we have found the asymptotics of if we can evaluate the integral on the right, which up to the linear constraint 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
where and is the complement of . Repeating the argument above essentially verbatim (change variables from to in the sum and scale by the mesh volume), we find that
This integral is even worse than the last one, but we claim that in fact the two are equal:
This follows immediately if we can show that the action has the symmetry
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 and , we have that
as . In particular, taking and we get
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 asymptotics of 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 be any fixed permutation, and define to the the number of permutations in the symmetric group which avoid , meaning that no subsequence of , when written in one-line notation, is order isomorphic to . Our exactly solvable function corresponds to choosing to be the reverse identity permutation, i.e. the Coxeter element in the Weyl group . Not much is known about the asymptotics of the generalized factorial for other choices of . The growth of this function is the subject of the Stanley-Wilf ex-conjecture, which asserts that where does not depend on . Stirling’s formula tells us that this is false for , 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 .
The Stanley-Wilf conjecture was proved by Adam Marcus and Gabor Tardos in 2002. Their proof gives a value for which is exponential in . On the other hand, we know from the asymptotics of , which we can explicitly compute, that in this case is polynomial in (Exercise: check this by computing the asymptotics of using the usual Stirling formula (Hint: this was already suggested as an Exercise in Lecture 5)). For a while, it was believed that should be of polynomial growth for all choices of . This was disproved by Jacob Fox, who showed that in a certain precise sense is almost always of exponential growth. So really is special among pattern avoiding generalizations of the factorial function.