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 2¹, 2³, 2⁶, and 2¹⁰. And those exponents 1, 3, 6, 10 aren’t just any old numbers; they are the triangle numbers T_n, known to humankind since antiquity and given by the formula T_n = n(n+1)/2. So in 1988 I conjectured that the number of domino tilings of the Aztec diamond of order n is always 2^n(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 2^1/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 2^N 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 2^N different outcomes for an experiment in which you toss a coin N times and keep track of each toss individually. The formula 2^n(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:

Dmytro Fedoriaka: http://fedimser.github.io/adt/adt.html

Philip Smolen: https://tradeideasphilip.github.io/aztec-tiles/

Bjarne Fich: http://rednebula.com/html/arcticcircle.html

chrideedee:  https://chridd.nfshost.com/tilings/diamond

The Coding Fox: https://www.thecodingfox.com/interactive/arctic-circle/

WaltherSolis: https://wrsp8.github.io/ArcticCircle/index.html

ky lan: https://editor.p5js.org/kaschatz/sketches/GHCkS-FyN

Jacob Parish: https://jacobparish.github.io/arctic-circle/

 

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.