In this Lecture we continue the the asymptotic analysis of with arbitrary but fixed. Recall that was defined in Lecture 5 as the number of permutations in which have no increasing subsequence of length
Our starting point is the “gluing” trick we used to recover Knuth’s formula
Based on this, we can hope that the asymptotics of might coincide with the asymptotics of
where is the 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 together with Stirling’s approximation of
Conjecture 1: For any fixed we have
To begin, we write
which is just RSK. We want to compare this sum to using our “gluing” intuition. To do this, let us define the notion of the complement of a diagram This is exactly what you think it is: if , then — draw yourself a picture. The basis of our gluing trick was that in the case every diagram is self complementary: for we have
This is not necessarily true for but for any we certainly have that the set of standard Young tableaux (SYT) of shape is in bijection with the set of pairs of SYT in which the shape of is a diagram and the shape of is the complementary diagram . The bijection is obtained simply by splitting any SYT of shape in half according to the decomposition
of its entries, rotating the half carrying the entries and subtracting from each entry. In formulas, this is
We can now compare and by comparing the above sums. The RSK sum formula for can be decomposed according to whether is contained in or not,
and the first group of terms can be further decomposed into two sum according to whether is self-complementary or not,
Similarly, we have
Now use the second formula to substitute for the first group of terms in the first formula, obtaining
we complete the square to obtain the following.
Proposition 1: We have where the error term is
The error term reflects the two sources of error in the approximation
namely that the right hand side fails to account for diagrams which aren’t self-complementary relative to , or which don’t fit inside In particular, we have that corresponding to Knuth’s theorem, but for Conjecture 1 says that is negligible for large
If is in fact negligible, it must be the case that the main contributions to the sum expressing come from diagrams which are contained in , and are moreover self-complementary relative to this rectangle. The simplest diagram with these features is of course half of i.e. the rectangle So we are hopeful that diagrams in a neighborhood of this rectangle are essentially contributions from a neighborhood of the maximum of just like in Laplace’s method.
To investigate the above, we want to consider the large behavior of the functional
where and is a vector such that
The set is a -dimensional convex subset of , which is in fact a hyperplane slice of the type A Weyl chamber in (you can safely ignore these words if you don’t know what they mean).
Note that we are evaluating at possibly non-integral numbers, so we are in effect taking Frobenius’s formula as a way to extend the domain of just like Euler’s integral extends the domain of to continuous arguments (and actually we’re using Euler’s integral inside the Frobenius formula because it contains factorials). The functional 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 in a neighborhood of its maximum.
Let’s see how behaves as We have
where as we have discussed. We now have to think about the behavior of the various pieces of this formula. The easiest piece is , for which we have
by Stirling’s approximation. Now consider the product in the denominator,
For each factor in this product, we have that
by the usual recurrence for factorials, which follows from Euler’s integral. Thus
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
Now using Stirling’s approximation in the form
the asymptotic form of the above sum is
Nothing for it but to keep hammering away. We have
and the purpose of this step was to allow us the fact that together with the Maclaurin series of to write
which finally gets us to
where, crucially, we used the fact that . Notice that is emerging as the right scaling here — do you see why? Assembling all these calculations into one master estimate, we obtain
There is one more piece of Frobenius’s formula which we still have to estimate, but this one is easy:
At the end of the day (which it is), if we take then we have the following.
Theorem 1: For any fixed and any , we have
The action 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 .