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
as
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
and
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
Observing that
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
,
where
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
.
2 Comments