With trepidation, I am attempting to start another series of mathematical blog posts. The goal of this one will be to present random partitions as a toy model for thinking about random dimer configurations. Ideally, these posts will help prepare the reader to take on the ground breaking papers of Kenyon and Okounkov.
I say ideally because I have an infant daughter at home — her name is Josephine, she is adorable and demanding — so the installments of this series may be spaced very far apart. I make no plans to apologize for this. But I’ve been feeling the lack of mathematical blogging the last few months, so I’m giving it a shot.
The motivating question for today’s post will be: For , approximately how many paths are there from
to
, made up of steps in direction
and
?
This may seem like a silly question. The exact number of such paths is . There are
steps,
of which are north and
of which are east. So the count is the binomial coefficient.
If we need an approximation, we can haul out Stirling’s approximation. In a weak form, this says So, after a little work we get
We’ll define , so this says that the number of paths of (taxicab) length
is
. Conceptually, one can think that, for every unit of length of the diagonal, there are
ways to configure that section of the partition.
Even with this crude bound, we can deduce a nonobvious statement: Almost all paths from to
are within
of a straight line path.
“Proof“: Suppose, to the contrary, that there were a positive proportion of paths that passed through a point which was significantly off a straight line. These paths can be divided into two shorter paths, one of size and one of size
, with
and
.
The number of paths of these two types is the product of the number of paths of each type. In other words,
But is easily seen to be concave, so
. Moreover, the only way that
can even be close to
is if
, meaning that the point is on the main diagonal. In other words, if the point is off the straight line route, the number of paths passing through that point is exponentially less then the number of total paths from
to
. So almost all paths in the box stay near the straight line. “QED”
By the way, that is the level of rigor you should expect throughout this series. I want to focus on concepts, not on precise bounds.
Another approach to deriving 
Now, let’s forget binomial coefficients and Stirlings formula. Suppose that we suspected there was a function such that the number of paths was
, but we didn’t know what
was. One can see that
is concave by thinking about concatenating paths, as above. I now explain how, using generating functions, we can understand the properties of
.
Let be the generating function for all north-easterly paths of length
, where we weight a northern step by
and an eastern step by
. Of course,
is simply
. Suppose that we didn’t know this exact formula, but we did know that there was a function
such that
. So
, but we are pretending not to know this. We now have two functions
and
, which we are pretending not to know, and we would like to figure out how they are related.
We can break the generating function up according to how many northern and how many eastern steps we take. So
or
When gets large, only the largest term will contribute to the sum. So we should have
Since is concave, this maximum will be achieved at a unique
. Assuming that
is sufficiently differentiable, this
will obey
. In short we have shown:
If |
The reader may enjoy verifying that our and
do in fact verify this relation. The standard term is that
and
are Legendre dual.
Coloring paths
Let’s do a slightly harder problem. We’ll count paths from to
again only, this time, when we take a step from
to
, and
is even, we can color the step either black or white. Approximately how many such colored paths are there?
This time, there is no simple formula for . But the same method works to obtain a differential equation. The generating function which used to be
would now be
and
would be
. So
is Legendre dual to
— whatever that may be.
Next time
My goal for next time is to derive the shape of a randomly chosen partition of size . See you then!
This looks promising but I got confused by some typos, there is a small s function and a big s function, one s I think should be an r (before “the reader may enjoy”), one g_n became r_n… if you fix these I will try again to read it.
Congratulations on your very young researcher at home!
Several typos fixed. Did I get them all?
Much improved! It is readable to me, I saw just one typo… after “there was a function r(x, y) such that” I guess the next formula should start with g_n.
I see how to compute r from s, in two ways. But how do we compute s from r? Or is that for a future episode?
@Daveagp Let me outline the basics, and point you to the Wikipedia article on Legendre transforms for the rest. To make things confusing, I will do this in multiple variables for concave functions (which will be the relevant set up for us), while Wikipedia does just one variable and does convex functions.
So, let
be a real vector space. Let
be a concave function
defined on some convex subset
of
. For
, define
. Let
be the set of
for which this maximum is finite. Then
is convex and
is concave on
. Moreover, this relation is self-dualizing up to getting signs right: we have
. This is called Legendre duality. In particular, you get
from
in the same way (up to getting signs right) that you get
from
.
In our setup,
, with
being all of
, and
with
being
.
Now, is there a simpler formula for the relation of
to
? Sort of. Consider
as a map
and
as a map
. Then the maps
and
are inverse. See “Another definition” at Wikipedia.
Let’s try using this in our case.
. So
. Inverting
, we get
. Then integrating this should give the stated formula for
, possibly with a sign error.
Of course, actually getting a closed form expression this way usually won’t work. You have to invert a fairly unconstrained function from
, then integrate the resulting
-form. But does this make it clear what you need to do?
As they say, “I see what you did there.” Thanks! I was originally caught off-guard by the fact that the original s and r took a different number of variables, which did not seem to jibe with the wikipedia definition. But I see that r can be thought of a single-input function in the sense that r(x, y)=r(x-y, 0)+y, then I also understand your comment about r of a single variable, and I also see this works in the 2nd setting you introduce at the end. Also, thanks for posting the pair of dual formulas.
The transition between the one variable and the two variable functions is one of these little awkwardnesses that keeps showing up — the two variable version manifests better the symmetries of the problem, but the one variable version makes easier technical statements.
Having just written this out has given me a nicer way to think about it. Forget about going to the one variable case. Look at
, a function on all of
. Then
is the line segment
. Really, it is:
is not finite for any other values of
. So, if you start in the two variable set up, your formula tells you that
should be defined on a one dimensional set.
I’m quite looking forward to the rest of this series! I learned the stuff in this post as “taking the thermodynamic limit”; In a statistical mechanics course, the function s in the first model of counting paths (equivalently, a lattice gas with particles named “North” and “East”) is known as the entropy of mixing http://en.wikipedia.org/wiki/Entropy_of_mixing , and treating x and y as chemical potentials of the two species, r is a grand potential (I think). I’m having more trouble making sense of the second model in these terms, though. My advisor is fond of saying that “Laplace is the same as Legendre”, referring to the relationship between “thermodynamic potentials” r and s (Legendre transform) and the relationship between “partition functions” g and the total number of paths (Laplace transform) in different statistical mechanical ensembles.