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

and

$\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)}$ ,

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} (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$ .

2 Comments

Pingback: Math 262A: Lecture 7 – Jonathan Novak
Pingback: Math 262A: Lecture 8 – Jonathan Novak

Math 262A: Lecture 6

Published by Jonathan Novak

2 Comments

Leave a Comment Cancel reply

Share this:

Like this:

Published by Jonathan Novak

2 Comments

Leave a Comment Cancel reply