My Life with Aztec Diamonds

It’s gratifying that a few thousand of you read this blog each month (hi, whoever you are!), but the way to really have an impact in this century is to have a YouTube channel. One mathematician who’s figured this out is Burkard Polster, whose Mathologer channel reaches more than a hundred times as many math-interested folks as my blog. Last month he made a video that was viewed by over 100,000 people just in its first week. I was glad to see it get so many views, both because it’s about a subject close to my heart and because it mentions my name and discusses work I did back in the 1990s. So this month I invite you to watch the video (maybe not all at once though; it’s almost an hour long!) and find out some of the backstory of Aztec diamonds and the arctic circle theorem.

A BOOK THAT CHANGED MY LIFE

My career was made possible by a combination of privilege, talent, luck, and effort, with early success leading to access to opportunities for later success. Someday I may try to tease apart all those strands, but today I’ll just mention a few of them, starting with a book I won as a contest prize in high school: Hardy and Wright’s “An Introduction to the Theory of Numbers”. My favorite chapter was chapter 19, entitled “Partitions”. 

A partition is a way of writing a positive integer as a sum of one or more positive integers, where we list the parts from largest to smallest and we allow repeats. Two examples of partitions of the number 19 are 6 + 5 + 5 + 3 and 4 + 4 + 4 + 3 + 3 + 1. The first partition has exactly 4 parts; the second has largest part 4. There’s a beautiful pictorial way to show that for every n and k, the number of partitions of n with k parts equals the number of partitions of n with largest part k. The proof gives a one-to-one correspondence, or bijection, between the set of partitions of n with k parts and the set of partitions of n with largest part k; see Endnote #1. Although Hardy and Wright’s book is about number theory, this argument is really an example of what nowadays would be called a combinatorial proof, or more specifically, a bijective proof. Early exposure to this kind of argument gave me a love of bijective proofs and pictorial combinatorics.

A TALK THAT CHANGED MY LIFE

Fast forward to my years of graduate study at U. C. Berkeley. I had won a National Science Foundation Graduate Fellowship on the strength of what I’d done in high school and college, and the Fellowship gave me access to travel funds which I dipped into to pay for my participation in the West Coast Number Theory Conference, held each year at the beautiful Asilomar Conference Center. If I hadn’t gotten the Fellowship, I wouldn’t have gone to the conference, and then I wouldn’t have heard Jeff Lagarias talk about his work on tilings with John Conway.

The problem Conway had tackled was, given a triangular array of dots like the one shown below, can you ever cover the dots with line segments that don’t touch each other, where each segment covers three adjacent dots in one of the three directions? 

The picture shows six segments that cover all but three of the points. Is there a way to arrange seven segments that cover all the points? Is there a way to cover all the points if I choose a bigger triangular array of dots? Conway had shown that the answer was “No”, and Lagarias had worked with him to develop the idea further.

As a result of my getting to know Lagarias and corresponding with him by email, I had a chance to read an early version of an article by Bill Thurston presenting his geometrical take on the work of Conway and Lagarias, and this in turn enabled me to wonder, “Hmm, how can I do pictorial combinatorics using Thurston’s approach?” As I’ll explain in an upcoming publication in the Mathematical Intelligencer, pursuing these wonderings led me to look at regions like this:

Nowadays this is called an Aztec diamond of order 3. An Aztec diamond of order n has rows of length 2, 4, 6, …, 2n–2, 2n, 2n, 2n–2, …, 6, 4, 2. Here’s a way of covering the Aztec diamond of order 3 by 1-by-2 and 2-by-1 rectangles:

 

We call these rectangles dominos and we call the configuration of dominos a tiling of the Aztec diamond of order 3.

Drawing lots of pictures, I found that the number of domino tilings of the Aztec diamond of order n (for n = 1, 2, 3, and 4) followed the pattern 2, 8, 64, 1024. These numbers are all powers of 2; specifically they are 21, 23, 26, and 210. And those exponents 1, 3, 6, 10 aren’t just any old numbers; they are the triangle numbers Tn, known to humankind since antiquity and given by the formula Tn = n(n+1)/2. So in 1988 I conjectured that the number of domino tilings of the Aztec diamond of order n is always 2n(n+1)/2.

I didn’t know it at the time, but I wasn’t the first to make this conjecture. Physicists Grensing, Carlsen, and Zapp had proposed this formula back in 1980. But they didn’t prove the formula, and more to the point they didn’t think it was worth proving because for their purposes the numbers given by the formula were too small. To explain what I mean by “too small”, let’s switch over to looking at domino tilings of the 2n-by-2n square. In the 1960s physicists Fisher, Kasteleyn, and Temperley had found an exact formula for the number of domino tilings of a 2n-by-2n square and they’d shown that when n is large the number of tilings is close to 1.34 to the power of the area of the square. But for a large Aztec diamond, Grensing, Carlsen, and Zapp’s conjecture implies that the number of tilings is exactly 21/4 (or about 1.19) to the power of the area of the Aztec diamond. The fact that 1.19 is less than 1.34 means that domino tilings of Aztec diamonds are more tightly constrained than domino tilings of squares, and this made the former less relevant to the kinds of questions the physicists were interested in. So although they stated the conjecture, they didn’t spend any effort figuring out how to prove it.

PEOPLE WHO CHANGED MY LIFE

Once I had a conjecture that I couldn’t figure out how to prove on my own, I needed to bring in other people to help me. And here I had another advantage: doing well on the U.S.A. Mathematical Olympiad as a high schooler had given me a chance to spend two summers attending the training program for the U. S. Math Team and to get to know a then-young mathematician named Michael Larsen. When I couldn’t solve the counting problem on my own, I mentioned it to Michael, who mentioned it to an even younger Noam Elkies. Noam found the first proof, and shortly thereafter Michael found the second.

Knowing that Michael and Noam had proved that formula correct settled the question but didn’t end my quest, because different mathematicians are satisfied with different sorts of answers to the question “Yes but why?”, and neither of their proofs was the kind of explanation that satisfied me. I wanted a bijective proof like the proof I mentioned earlier about partitions of numbers, and the fact that my conjecture involved powers of 2 made me convinced that such a proof could be found.

The question “In mathematics, what are there 2N of?” has many correct answers. One answer is “The number of strings of N symbols in which you have 2 choices for each of the N symbols and each symbol can be chosen independently of every other.” You could for instance look at strings of H’s and T’s of length N, corresponding to the 2N different outcomes for an experiment in which you toss a coin N times and keep track of each toss individually. The formula 2n(n+1)/2 suggested that there ought to be a way to encode each and every tiling as a string of 0’s and 1’s of length n(n+1)/2.

Here I had another bit of advantage: I held a National Science Foundation Postdoctoral Fellowship that enabled me to be at Berkeley, which enabled me to get to know Greg Kuperberg and to interest him in the problem. We worked together and came up with domino shuffling, which is the kind of bijection I was looking for, or something close enough.

What is domino shuffling? I won’t tell you, but I will show you. Here are the names of some of Mathologer’s enthusiastic fans, along with links to the implementations of domino shuffling that they created in the 24 hours after Mathologer posted his video about the Aztec diamond:

Now that is some fan-base!

In writing up the work I’d done with Elkies, Kuperberg and Larsen, I dubbed the shapes we’d studied “Aztec diamonds” because the design can be found in much pre-Columbian art.  I tried to figure out if there was a specific group of Native Americans most closely associated with the motif but it seemed to be shared between many nations. I eventually concluded that the Hopi made the most use of it, but “Hopi diamond” didn’t sound as good as “Aztec diamond”, so I chose euphony over ethnographic accuracy.

BEYOND COUNTING

The gap between the bases 1.19 and 1.34 told me that domino tilings of Aztec diamonds must exhibit less variety than domino tilings of squares, and suggested that a random domino tiling of a big Aztec diamond would look different from a random domino tiling of a big square. If I wanted to explore this phenomenon experimentally, domino shuffling was precisely the sort of tool I needed: all I had to do was use n(n+1)/2 coin flips (or some computer-generated surrogate) to get a random bit-string of length n(n+1)/2 for some large-ish n and then use the shuffling algorithm to convert the string of bits into a domino tiling of the Aztec diamond of order n.

I didn’t get around to using domino shuffling to study random tilings until I finished my postdoctoral work at Berkeley and joined the MIT math department as an assistant professor. Coming to MIT was a bit of a gamble because at the time MIT was notorious for not giving tenure to assistant professors whose main interest was combinatorics. At times I feel wistful about academic roads not taken; where would I be now – who would I be now – if I’d succumbed to the attractions of liberal arts schools and sought a job at a place like Swarthmore or Williams? But having enjoyed my postdoctoral years at Berkeley and the boon provided by the chance to collaborate with Greg Kuperberg, I thought that being in the Boston area with potential collaborators at MIT and Harvard would prove to be very beneficial for my research. And I was right, though I wouldn’t have guessed just how young many of my future collaborators would be. MIT had a well-established and well-funded program called UROP (Undergraduate Research Opportunities Program) that few of the professors in the math department were taking advantage of, so I mostly had all the bright math undergrads to myself. One such undergrad was Sameera Iyengar; I hired her to implement domino shuffling, and she generated a picture that looked something like this:

A random domino tiling of an Aztec Diamond of order 48. This is the image we put on our research group tee-shirts. The “circle” is a bit lumpy because n=48 is still on the small side.

Grensing, Carlsen, and Zapp had known that domino tilings of Aztec diamonds are more constrained than domino tilings of squares, but hadn’t guessed that these extra constraints make themselves felt in different ways in different parts of the Aztec diamond. Sameera’s pictures made it clear that most of the randomness shows up in the middle. I realized that what I’d been looking at was much more than a fun new kind of counting problem; it was potentially a testbed for studying the ways in which geometrically constrained systems like tilings could exhibit propagation of constraints from the boundary of a system to the deep interior.

To get the beginnings of an understanding of propagation of constraints in tilings, consider the middle cell of the northwest border of an Aztec Diamond of order 5, marked by a question mark in the left panel of this picture.

That cell must either be covered by a horizontal domino that it shares with the square to its right or a vertical domino that it shares with the cell below it. But if the “?”-cell is covered by a horizontal domino, marked “1” in the right panel of the picture, then that forces the placement of a second domino, marked “2”, which in turn forces the placement of a third domino, marked “3”. Likewise, if the “?”-cell is covered by a vertical domino, then that also forces the placement of two more dominos. (You can view this cascade of causation as a metaphor for the way access to opportunities, or lack of access to opportunities, can cascade in one’s professional career. I’ve already described some ways in which I was the beneficiary of a positive cascade effect. Here’s an example of a negative cascade that I fortunately haven’t fallen prey to in my own career: If you don’t publish enough, some universities will give you more courses to teach, which cuts down on how much time you get to spend on research, which makes it hard to write articles for publication.)

In the 1990s I was able to recruit many Boston-area undergrads and graduate students to the study of tilings. Grad student William Jockusch and my former Math Olympiad Program roommate Peter Shor helped me find the first proof of what I called the arctic circle theorem, showing that if you choose a random domino tiling of an Aztec diamond of order n, then with high probability there’ll be four completely nonrandom-looking “frozen regions” in the corners where the tiling looks like brickwork, and a central “temperate” region where the tiling looks fairly random, and the boundary between the frozen regions and the temperate zone converges in shape to a perfect circle as n goes to infinity. (See Endnote #2.)

In math, what makes a question good isn’t always obvious from the question, or even from the answer; it’s about where the question leads, and what kind of story it gives rise to. In later years, many people moved into the study of domino tilings of Aztec diamonds, using tools from a wide variety of mathematical disciplines such as differential equations, random matrix theory, algebraic geometry, integrable systems, and even physics. Just last week, Rick Kenyon told me about a new result about Aztec diamonds he’s obtained in work with Cosmin Pohoata. So the story isn’t over.

LESSONS

Are there lessons in this story for others who seek careers as research mathematicians? I might have thought so before the pandemic hit; now it’s unclear to me what academia is going to look like in the years ahead. Given a choice between a tenure-track job at a good place or a non-tenure-track job at a great place (such as a postdoctoral position or a nominally tenure-track job that in practice might more accurately be described as “tenure-plank”), which should you pick? It’s a tough problem, but I will say that surrounding yourself with smart people is a good recipe for doing your best work.

Speaking of the pandemic: one positive effect of the disappearance of in-person seminars is the burgeoning of online seminars. Attending research talks by top mathematicians is now within the reach of anyone with an internet connection and the time to make use of it. There’s a potential for democratization of doctoral education and math research that I hope will continue even after the pandemic is over. You’ll remember from early in this essay that I benefitted from going to a conference as Asilomar where I got to hear Lagarias talk about his work with Conway. Maybe other young people would have gotten the same inspiration from Jeff’s talk as I did but didn’t get to go to Asilomar. Hopefully in the new world of math research that’s being assembled from the pieces of the pre-pandemic world, more people will get the kind of chance that I got.

Even more important than the talks that I went to were the people I had the chance to collaborate with. There’s a ratchet mechanism at work here: collaborating with good people enables you to do good work, and doing good work gives you access to good collaborators. We need to give more people the opportunity to take advantage of the ratchet. When people want to collaborate with me, I try hard to say “Yes”.

Another lesson is the importance of recognizing opportunities when they come your way. Aztec diamonds weren’t first discovered by me; they were first discovered by physicists who didn’t recognize their lucky find. By being one of the first to jump into the study of Aztec diamonds and related structures, I was able to spend an exciting decade pushing back the frontiers of one corner of mathematics. The mathematician Gian-Carlo Rota (quoting someone else, but I forget whom!) wrote “When pygmies cast such long shadows, it must be very late in the day,” but I like to turn that around and say that short people can cast long shadows if they show up early enough.

I gave a talk at the 11th Gathering 4 Gardner conference called “Conway’s Impact on the Theory of Random Tilings” that covers some of the same ground as this essay. If you look carefully you’ll see that I’m wearing one of my “Random Tilings Research Group” shirts.

One question haunts me from time to time: Where did that three-dots-in-a-line problem Conway worked on come from – the one that shaped my career in such a deep way? I have a hunch it originated with mathematician David Klarner, but I’m not sure. If any of you have information about this, please let me know!

Next month: Thoughts from the Outfield.

ENDNOTES

#1: Here is a partition of the number 19 depicted as what is called a Ferrers diagram:

Reading by rows we get the partition 6+5+5+3, a partition with 4 parts; reading by columns we get the partition 4+4+4+3+3+1, a partition whose largest part is 4. This gives us a bijection between partitions of 19 with 4 parts and partitions of 19 with largest part 4: given some partition with 4 parts, use the part-sizes as the row-sizes of a Ferrers diagram, and then use the column-sizes of that same diagram as the parts in a partition whose largest size is 4. Or if you prefer you can flip the diagram across its diagonal. The same construction gives a bijection between partitions of n with k parts and partitions of n with largest part k, for all positive integers n and k.

#2: The term “arctic circle” is perhaps a little misleading for Earthlings, since on Earth the frozen arctic region is inside the arctic circle while in an Aztec diamond the four frozen regions are outside the arctic circle, but the name has stuck.

It still amazes me that the boundary of the temperate region tends to be circular in the limit as n approaches infinity. Why is it a circle, and not some other curve? I don’t have an intuitive explanation for this.

REFERENCES

J. H. Conway and J. C. Lagarias, Tiling with polyominoes and combinatorial group theory. Journal of Combinatorial Theory Series A, Volume 53 (1990), pp. 183-208.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 1938.

W. Thurston, Conway’s Tiling Groups. The American Mathematical Monthly, Volume 97 (1990), pp. 757-773.

9 thoughts on “My Life with Aztec Diamonds

  1. David Jacobi

    This is a fun piece of mathematics at the intersection of probability and combinatorics. As important as the math is, I enjoyed the social background for the discovery of new mathematics. In contrast to the cult of solitary mathematical genius that we have all read about, you emphasize the role of collaboration in your career.

    I wonder if the ubiquity of prizes, prestige, tenure promotions etc. generate incentives for individuals to puff up their individual achievements, and downplay the collaborations that made them successful.

    You convincingly show the crucial role of working with others. The secret behind your collaborative success is not stated explicitly, but is implicit throughout your entire essay:
    Your scrupulous honesty and humility with which you share credit with others.

    Liked by 2 people

    Reply
  2. nishantchandgotia

    I had a presentation to prepare when I started reading your article (for a small little distraction). Reading and thinking as I went along, I got a bit curious about your video and thought why don’t I listen to him for a bit. 2 videos and 1.5 hours later I am very satisfied (but a little delayed on my own presentation). While I did know a little bit of the mathematics involved, I most certainly did not know the history of the problem and how you got involved in it. This has been very informative. The video by mathloger is really wonderful.

    As David Jacobi points out above, the emphasis on collaboration is one of the many key take aways here which has also played a very important role in my career.

    You spoke about the possible democratisation of mathematics as a result of the pandemic. While on one hand, I have access to way many seminars, talks and resources it becomes a real challenge what you want to choose to listen to. For instance, if I were to go to a conference, I would listen to all the talks whether or not I wanted to listen to them. Occasionally (in fact many times) I gathered ideas from completely different areas. There is a certain advantage of being at the right place at the right time which I see hard to replicate in the COVID world. This has had surprising effects on my mathematical productivity (in fact the research I presented a year ago to you is yet to be polished and published) when in reality I have all the time in the world. Perhaps it is the effect that you describe very well- “Given a choice between a tenure-track job at a good place or a non-tenure-track job at a great place (such as a postdoctoral position or a nominally tenure-track job that in practice might more accurately be described as “tenure-plank”), which should you pick?” One can interact with all the great people in the world online or by visiting them but I guess it is different to be physically there amidst them.

    I am not saying that there is anything bad in all this access; in fact I am inclined towards it and I certainly hope that it will continue. However I can’t wait for regular seminars and interactions to start and (hopefully) motivate me back to real work.

    Liked by 1 person

    Reply
  3. Pingback: Children of the Labyrinth |

    1. jamespropp Post author

      That’s a good question! A concrete but unmotivated answer, using the arrows on the tiles described in the video, is: the northern frozen region consists of every location you can reach from the north corner traveling only between adjoining north-going dominos, and likewise for the other three frozen regions. (Every horizontal domino is either north-going or south-going; every vertical domino is either east-going or west-going.)

      A better-motivated but more technical answer is: the frozen regions consist of all the places in the tiling where vertices are either of maximal height or minimal height. (But you need to understand height-functions for that to make sense.)

      I realize that neither answer is that helpful. If anyone can give a better answer to Jeff’s question, please post it here!

      Like

      Reply
  4. 90s math guy

    Rota was playing on the line from Karl Kraus, “when the sun of culture is low, even dwarfs cast long shadows”. Both Kraus and variants of that quotation are much better known in Germany and Austria than in the English-speaking world, so it was of course a way for Rota to showcase his cultural erudition as he liked to do.

    I very much appreciate you posting the story of how the story developed. I remember the Aztec diamond papers when they appeared on the arxiv, and the impression that they made of a promising, multifaceted area with magical results that had no right to be that nice (compared, e.g., to tilings of rectangles). It’s more than interesting to hear how things unfolded as the discoveries were being made.

    Liked by 1 person

    Reply
  5. jamespropp Post author

    Glad you liked it, 90s math guy! I gather you prefer to keep your identity under wraps, but I’m hoping you’ll DM me so I can find out who you are (I can keep a secret).

    Like

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s