Math 262A: Lecture 6

In this Lecture we continue the the N \to \infty asymptotic analysis of N!_d with d \in \mathbb{N} arbitrary but fixed. Recall that N!_d was defined in Lecture 5 as the number of permutations in \mathrm{S}(N) which have no increasing subsequence of length d+1.

Our starting point is the “gluing” trick we used to recover Knuth’s formula

N!_3 = \frac{1}{N+1}{2N \choose N}.

Based on this, we can hope that the asymptotics of N!_d might coincide with the asymptotics of

\dim R(d, \frac{2N}{d}),

where R(a,b) is the a \times b rectangular Young diagram. This would be excellent, since the asymptotics of the dimension of a very long rectangle of fixed height are easy to deduce from Frobenius’s formula for \dim \lambda together with Stirling’s approximation of N!.

Conjecture 1: For any fixed d \in \mathbb{N}, we have

(dN)!_d =\dim R(d,2N)+o\left(\dim R(d,2N)\right)

as N \to \infty.

To begin, we write

(dN)!_d = \sum\limits_{\lambda \in \mathrm{Y}_d(dN)} (\dim \lambda)^2,

which is just RSK. We want to compare this sum to \dim R(d,2N) using our “gluing” intuition. To do this, let us define the notion of the complement \mu^* of a diagram \mu \subseteq R(d,2N). This is exactly what you think it is: if \mu=(\mu_1,\dots,\mu_d), then \mu^*=(2N-\mu_d,\dots,2N-\mu_1) — draw yourself a picture. The basis of our gluing trick was that in the case d=2, every diagram is self complementary: for \mu \in \mathrm{Y}_2(2N), we have

\mu=(\mu_1,\mu_2) = (\mu_1, 2N-\mu_1)


\mu^*=(2N-(2N-\mu_1),2N-\mu_1) = (\mu_1,2N-\mu_1).

This is not necessarily true for d > 2, but for any d we certainly have that the set of standard Young tableaux (SYT) of shape R(d,2N) is in bijection with the set of pairs (P,Q) of SYT in which the shape of P is a diagram \mu \in \mathrm{Y}_d(dN) and the shape of Q is the complementary diagram \mu^*. The bijection is obtained simply by splitting any SYT of shape R(d,2N) in half according to the decomposition

\{1,\dots,2dN\} = \{1,\dots,dN\} \sqcup \{dN+1,\dots,2dN\}

of its entries, rotating the half carrying the entries \{dN+1,\dots,2dN\}, and subtracting dN from each entry. In formulas, this is

\dim R(d,2N) = \sum\limits_{\mu \in \mathrm{Y}_d(dN)} (\dim \mu)(\dim \mu^*).

We can now compare (dN)!_d and \dim R(d,2N) by comparing the above sums. The RSK sum formula for (dN)!_d can be decomposed according to whether \lambda \in \mathrm{Y}_d(dN) is contained in R(d,2N) or not,

(dN)!_d = \sum\limits_{\substack{\lambda \in \mathrm{Y}_d(dN) \\ \lambda \subseteq R(d,2N)}} (\dim \lambda)^2 + \sum\limits_{\substack{\nu \in \mathrm{Y}_d(dN) \\ \nu_1 > 2N}} (\dim \lambda)^2,

and the first group of terms can be further decomposed into two sum according to whether \lambda \subseteq R(d,2N) is self-complementary or not,

(dN)!_d = \sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu = \mu^*}} (\dim \mu)^2 +\sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu \neq \mu^*}} (\dim \mu)^2 + \sum\limits_{\substack{\nu \in \mathrm{Y}_d(dN) \\ \nu_1 > 2N}} (\dim \nu)^2.

Similarly, we have

\dim R(d,2N) = \sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu = \mu^*}} (\dim \mu)^2 +\sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu \neq \mu^*}} (\dim \mu)(\dim \mu^*).

Now use the second formula to substitute for the first group of terms in the first formula, obtaining

(dN)!_d = \dim R(d,2N)+\sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu \neq \mu^*}} (\dim \mu)^2 - \sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu \neq \mu^*}} (\dim \mu)(\dim \mu^*)+ \sum\limits_{\substack{\nu \in \mathrm{Y}_d(dN) \\ \nu_1 > 2N}} (\dim \nu)^2.

Observing that

\sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu \neq \mu^*}} (\dim \mu)^2 = \sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu \neq \mu^*}} (\dim \mu^*)^2,

we complete the square to obtain the following.

Proposition 1: We have (dN)!_d = \dim R(d,2N) + E_d(N), where the error term is

E_d(N) = \frac{1}{2} \sum\limits_{\substack{\mu \in \mathrm{Y}_d(dN) \\ \mu \subseteq R(d,2N) \\ \mu \neq \mu^*}} (\dim \mu-\dim \mu^*)^2 + \sum\limits_{\substack{\nu \in \mathrm{Y}_d(dN) \\ \nu_1 > 2N}} (\dim \nu)^2.

The error term E_d(N) reflects the two sources of error in the approximation

(dN)!_d \approx \dim R(d,2N),

namely that the right hand side fails to account for diagrams which aren’t self-complementary relative to R(d,2N), or which don’t fit inside R(d,2N). In particular, we have that E_2(N)=0, corresponding to Knuth’s theorem, but E_d(N)>0 for d>2. Conjecture 1 says that E_d(N) is negligible for large N.

If E_d(N) is in fact negligible, it must be the case that the main contributions to the sum expressing (dN)!_d come from diagrams \lambda \in \mathrm{Y}_d(dN) which are contained in R(d,2N), and are moreover self-complementary relative to this rectangle. The simplest diagram with these features is of course half of R(d,2N), i.e. the rectangle R(d,N). So we are hopeful that diagrams in a neighborhood of this rectangle are essentially contributions from a neighborhood of the maximum of \dim \lambda, just like in Laplace’s method.

To investigate the above, we want to consider the large N behavior of the functional

f_N(y_1,\dots,y_N;\varepsilon) =\dim (N+y_1N^\varepsilon, \dots, N+y_dN^\varepsilon),

where \varepsilon \in (0,1) and (y_1,\dots,y_d) \in \mathbb{R}^d is a vector such that

y_1 > \dots > y_d \quad\text{ and }\quad y_1+\dots+y_d=0.

The set \Omega_{d-1} is a (d-1)-dimensional convex subset of \mathbb{R}^d, which is in fact a hyperplane slice of the type A Weyl chamber in \mathbb{R}^d (you can safely ignore these words if you don’t know what they mean).

Note that we are evaluating \dim at possibly non-integral numbers, so we are in effect taking Frobenius’s formula as a way to extend the domain of \dim, just like Euler’s integral extends the domain of N! to continuous arguments (and actually we’re using Euler’s integral inside the Frobenius formula because it contains factorials). The functional f_N is capturing the behavior of the dimension function in a neighborhood of the suspected maximizer, which to compare with Laplace’s method is like looking at the Taylor expansion of the e^{-NS(x)} in a neighborhood of its maximum.

Let’s see how f_N(\cdot;\varepsilon) behaves as N \to \infty. We have

f_N(y_1,\dots,y_N) = \frac{(dN)!}{\prod_{i=1}^d(N+y_iN^\varepsilon + d-i)!}\prod\limits_{1 \leq i<j \leq d} \left((y_i-y_j)N^{\varepsilon} + j-i \right),

where x! = \int_0^\infty t^x e^{-t} \mathrm{d}t as we have discussed. We now have to think about the N \to \infty behavior of the various pieces of this formula. The easiest piece is (dN)!, for which we have

(dN)! \sim \sqrt{2\pi} \frac{(dN)^{dN+\frac{1}{2}}}{e^{dN}}

by Stirling’s approximation. Now consider the product in the denominator,

\prod\limits_{i=1}^d(N+y_iN^\varepsilon + d-i)!.

For each factor in this product, we have that

(N+y_iN^\varepsilon + d-i)! \sim N^{d-i+1} (N+y_iN^\varepsilon-1)!

by the usual recurrence x!=x(x-1)! for factorials, which follows from Euler’s integral. Thus

\prod\limits_{i=1}^d(N+y_iN^\varepsilon + d-i)! \sim N^{1+2+\dots+d}\prod\limits_{i=1}^d(N+y_iN^\varepsilon-1)! \\= N^{\frac{d(d+1)}{2}}\prod\limits_{i=1}^d(N+y_iN^\varepsilon-1)!

To estimate the remaining simplified product, let’s take a logarithm; this will convert a product of big numbers into a sum of smaller numbers, which ought to be easier to understand. We obtain

\log \prod\limits_{i=1}^d(N+y_iN^\varepsilon-1)! = \sum\limits_{i=1}^d \log (N+y_iN^\varepsilon-1)!

Now using Stirling’s approximation in the form

\log (N-1)! \sim \frac{1}{2}\log 2\pi + (N-\frac{1}{2})\log N-N,

the asymptotic form of the above sum is

\sum\limits_{i=1}^d \log (N+y_iN^\varepsilon-1)!\sim \frac{d}{2} \log 2\pi -dN + \sum\limits_{i=1}^d \left(N+y_iN^\varepsilon - \frac{1}{2} \right)\log \left( N+y_iN^\varepsilon\right).

Nothing for it but to keep hammering away. We have

\sum\limits_{i=1}^d \left(N+y_iN^\varepsilon - \frac{1}{2} \right)\log \left( N+y_iN^\varepsilon\right) = dN\log N - \frac{d}{2} \log N + \sum\limits_{i=1}^d \left(N+y_iN^\varepsilon - \frac{1}{2} \right)\log \left( 1+y_iN^{\varepsilon-1}\right),

and the purpose of this step was to allow us the fact that \varepsilon <1 together with the Maclaurin series of \log(1+x) to write

\log \left( 1+y_iN^{\varepsilon-1}\right) = y_iN^{\varepsilon-1} - \frac{1}{2} y_i^2N^{2\varepsilon-2} + O(N^{3\varepsilon-3}),

which finally gets us to

\sum\limits_{i=1}^d \left(N+y_iN^\varepsilon - \frac{1}{2} \right)\log \left( 1+y_iN^{\varepsilon-1}\right) \sim \frac{N^{2\varepsilon-1}}{2} \sum\limits_{i=1}^d y_i^2,

where, crucially, we used the fact that y_1+\dots+y_d=0. Notice that \varepsilon = \frac{1}{2} is emerging as the right scaling here — do you see why? Assembling all these calculations into one master estimate, we obtain

\frac{(dN)!}{\prod_{i=1}^d(N+y_iN^\varepsilon + d-i)!} \sim \frac{e^{dN}}{(2\pi)^{\frac{d}{2}}N^{dN+\frac{d^2}{2}}} e^{-\frac{N^{2\varepsilon-1}}{2} \sum_{i=1}^d y_i^2}.

There is one more piece of Frobenius’s formula which we still have to estimate, but this one is easy:

\prod\limits_{1 \leq i<j \leq d} \left((y_i-y_j)N^{\varepsilon} + j-i \right) \sim N^{\varepsilon \frac{d(d-1)}{2}} \prod\limits_{1 \leq i<j \leq d} (y_i-y_j).

At the end of the day (which it is), if we take \varepsilon = \frac{1}{2} then we have the following.

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

\dim\left(N+y_1\sqrt{N},\dots,N+y_d\sqrt{N} \right) \sim \frac{(dN)!e^{dN}}{(2\pi)^{\frac{d}{2}} N^{dN+\frac{d^2}{2}}}e^{-S(y_1,\dots,y_d)},


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} (y_i-y_j).

The action S which has emerged from this herculean computation is an extremely interesting and important special function. We will discuss this further next lecture, and complete our analogue of Stirling’s approximation for N!_d.


Leave a Reply