Rhombus tilings and an over-constrained recurrence October 21, 2009Posted by David Speyer in combinatorics, things I don't understand.
I recently visited Robin Pemantle and his student Peter Du at UPenn. We talked about tilings of planar regions, generating functions and asymptotics. Towards the end, we talked about a bit about a very classical example, which is what I want to tell you about today.
In most planar tiling problems, the goal is an asymptotic analysis for tilings of large regions, because there isn’t enough structure to do better. This is the approach taken in the beautiful work of Kenyon, Okounkov, and collaborators.1, 2, 3 Sometimes, there is enough structure to give exact solutions with explicit generating functions. This is the situation with Aztec Diamonds, fortresses, and other several other examples.4,5 The central name here is Jim Propp 6, 7, who has developed this theory together with many undergraduate and graduate students (including me).
And then there is one case: rhombus tilings of a hexagon. These have almost too much structure; more structures than one would expect to be compatibly possible. In this post, I want to talk about this example. In particular, I want to ask you a question which I thought about a bit on the train ride back and see whether any of you have some thoughts.
A QUICK INTRODUCTION TO RHOMBUS TILINGS
Tile the plane with equilateral triangles, and cut out a hexagonal region where the opposite sides are parallel and of the same length. We’ll call the lengths of the sides , , , , and .This hexagon contains equally many up and down triangles, so we can hope to tile it with unit rhombi, each of which cover two adjacent triangles. We write for the number of such matchings.
If , then the hexagon degenerates to a parallelogram, and there is only one tiling. If , then the horizontal edge has length . In that case, the two types of horizontal rhombi form a path from the bottom of the hexagon to the top (colored blue). It is easy to see that there is one matching for each possible path, so .
If , this turns into the problem of counting noncrossing pairs of paths; by a happy coincidence, this topic was recently discussed on Math Overflow. More generally, you need to count -tuples of noncrossing paths, and you wind up computing determinants. I’m going to skip over these and go straight to a wonderful formula due to MacMahon.
Of course, there is a lot of cancellation here, so this can be rewritten in many ways.
One can also give a bilinear recurrence for , to which we’ll be returning throughout this post.
Starting with the initial condition , we can recursively use to compute for all , then and , then and so forth.
I believe it was Eric Kuo who first realized that has a direct combinatorial meaning.
Each term in this “equation” involves two hexagons, plus some extra rhombi. The meaning is to take all the tilings of the red hexagon, and all the tilings of the blue hexagon, and superimpose them in all possible ways, together with the excess black rhombi. Then every superposition of rhombi appears with the same multiplicity on the left hand side and on the right.
Why is this important? Suppose you wanted to know the expectation of some statistic of a random tiling — for example, the probability that a particular tile would be used. Then you can just take expectations of both sides of Kuo’s relation. Of course, in order to do this, you need to know the relative sizes to the two right hand terms. This is easy, using the explicit formula : of the superpositions come from the first term, and the remaining come from the second.
This gives you a linear recurrence, a reasonably nice generating function and, we hope, a target to which we can apply Robin’s machinery. But that’s not what I want to talk about, because Peter and Robin are already thinking about it. Instead, I want to explain what I meant when I said that this example had more structure than you would think possible.
MUSINGS ABOUT THE RECURRENCE
In most tiling problems, you can’t find a simple recurrence like at all. In the nice examples I talked about earlier, like Aztec diamonds, most of the above ideas work: you can reinterpret matchings as noncrossing paths, get a determinant, get some sort of product formula, and get a recurrence. It’s hard to recommend just one paper on this subject, but I like Greg Kuperberg’s exposition. (See Section 7 for the case considered here.)
But, in our case, overdetermines the number of tilings! More precisely, the entire situation is symmetric in , and . So, as well as , we have the variants of obtained by permuting the coordinates. If we restrict , and to lie between and , this gives variables , subject to relations. If you were handed this set of quadratic equations, without being told where it came from, you would expect there to be no solutions! Similarly, running the trick I described above, we get more linear equations for the probability of using a given tile than we have variables.
For easy reference, I’ll write the variants obtained by permuting the variables:
So, here is my question: What are the other solutions to this trio of recurrences?
I’ve noticed a few easy things. You can rescale by for any . You can translate any
solution through three-space to give another solution. Also, I found one more peculiar solution: .
I currently have no idea how much freedom I have in choosing a solution. Here is a way to make that question precise: Let be the set of nonzero* solutions to these equations, restricted to the range . How does the dimension of grow with ?
So, any ideas?
*I look at nonzero solutions for technical reasons: the variety of all solutions to the equations above has many trivial components, where we take enough of the variables to be zero in order to make all the relations trivially true. By restricting to nonzero solutions, I make sure we are studying the main component.