Monday, April 27, 2015
The Glass Frieze Game
by Jonathan Kujawa
In 1971 H. S. M. Coxeter introduced a mathematical trifle he called "friezes". At the time they didn't seem like much more than a cute game you can play. In the past decade, however, they've become a central player in a major new area of research. I recently saw an entertaining talk by Peter Jorgensen at the Mittag-Leffler Institute about his work in this area with Christine Bessenrodt and Thorsten Holm. Peter's talk reminded me that I should really tell you the story of friezes. We've all seen friezes such as this one by Caravaggio :
As you can see, a frieze is an array of the counting numbers (1,2,3,4,...) where the top and bottom rows are all ones. The dots on the left and right mean that each row continues forever in both directions. The real mystery is the numbers in the middle rows. There is some sort of pattern and symmetry but I, at least, couldn't quite put my finger on it the first time I saw a frieze. The mysterious missing rule is that each diamond of four numbers:
is required to satisfy the equation:
You can check the diamonds in our example frieze and see that the formula always holds true. Notice, too, we can make diamonds on each edge where we know three out of four of the numbers. Using our formula we can solve for the missing number and so fill in missing numbers on each edge. This observation along with the fact that the top and bottom rows are always one means the frieze really does continue forever in both directions and the Rule for Diamonds tells us how to calculate the missing numbers.
Now that you know the rule it's a fun game to use the Rule for Diamonds to find other friezes. For example, there is a single one-row frieze, what is it ? How about two and three-row friezes? It's like an infinite version of Sudoko ("If this number is a 3, then that one has to be a 1..."). Like Sudoko, once you get the hang of it you start to see patterns. For example, like we saw in the previous paragraph, if you can get chunk of the frieze which goes from top to bottom, then you can use the Rule for Diamonds to build off the edges to get everything else.
If you haven't seen it before, the Rule for Diamonds seems mysterious and arbitrary. If you have seen it before, then you know it's the determinant of a two-by-two matrix. A matrix is a square array of numbers and its determinant is used all the time by every undergraduate who takes math beyond calculus. But that makes it all the more mysterious! Of all the formulas in all the towns in all the world, why the heck should Coxeter use the two-by-two determinant in his friezes?
When developing a new concept in pure math, you don't have the anchor of the real world to guide you . Does this mean it's some sort of post-modern free-for-all where any crack-pot theory is as good as another? Not hardly! In making music you can do what you like, but nobody would argue that all the noises which can be made are musical. And certainly nobody would argue that Miles Davis and Milli Vanilli will have the same enduring value.
In the same way there is a guiding aesthetic in mathematics. You are on to something good if it connects to interesting things we already know about, has a beauty of its own, and it opens new vistas and directions. Miles Davis's Kind of Blue certainly wins on all counts. As we'll see, so does Coxeter's friezes.
In the original paper  Coxeter provides an interesting prehistory to friezes. As we saw last month, in the mid 1800s folks realized you can do perfectly reasonable non-Euclidean geometry. Strange things happen but with a little courage you can do good ol' high school trigonometry on the sphere. In fact, spherical trigonometry was already thought about by the ancient Greeks.
Important for the story of friezes is the Marvelous Merchiston, John Napier. In addition to inventing logarithms and getting people on board with the humble decimal point, Napier made a close study of spherical triangles (triangles on the sphere which have a 90 degree angle). As Coxeter explains in his paper, Gauss's version of Napier's rules for spherical triangles can be encoded as a frieze.
As we talked about last month, the other non-Euclidean geometry is hyperbolic geometry. You can do hyperbolic trigonometry and Lobachevsky discovered the hyperbolic right triangle analogues of Napier's equations. Lo and behold, Coxeter shows us that Lobachevsky's rules can also be encoded as a frieze.
Coxeter was a master geometer and surely knew he was on to something when he realized Napier's and Lobachevsky's rules can each be encoded in a frieze. Coxeter also found connections between friezes and other well studied mathematical objects. As we said above, it's always a good sign when your new idea is a natural outgrowth of things which are already known to be useful, important, and interesting.
Coxeter now knows he's on to something good. The next test is if it has beauty of its own. Coxeter proves several remarkable facts about friezes. The first is that if you take any three adjacent numbers on a diagonal of the frieze, the middle number will always divide the sum of the other two. For example, in our frieze up above we see that 3 divides 2+4 and that 4 divides 1+3. Coxeter shows us that this always happens.
Even more remarkably, Coxeter shows that all friezes have symmetry: as you slide along the frieze it will repeat itself over and over. We can see the beginnings of this in our example, and it becomes even more clear if you use the Rule for Diamonds to extend the edges. Doing those calculations, you might even get a feeling at the edge of your consciousness which tells you this pattern really does repeat over and over. We can imagine Coxeter getting ever more excited as he saw the symmetry happening in frieze after frieze. Coxeter proved this symmetry happens for every frieze. Now we see why Coxeter called his gadgets "friezes".
So, just like in art, every frieze has a repeating pattern. Once you have enough of the frieze to identify the pattern, you know the whole thing. In fact Coxeter does more: he proved a frieze with n rows must repeat itself every time you slide it n+3 steps left or right. This along with the Rule for Diamonds tells us there are only finitely many friezes with a given number of rows!
There are only so many friezes with six rows. How many are there? How do we find them?
Enter the second character in our story: John Conway. John Conway has made important contributions across mathematics and has impeccable taste. No doubt he was immediately interested in Coxeter's friezes. In a pair of papers in 1973 Conway and Coxeter proved that the number of friezes with n rows is given by the n+1 Catalan Number. You can find the formula for the Catalan numbers at the Wikipedia link, but the first few are 1, 1, 2, 5, 14, 42, 132, 429, 1430, and 4862. So there is one frieze with zero rows, two with one row, five with two rows, fourteen with three rows, and so on.
How is it that the Catalan numbers counts the number of friezes? The tongue-in-cheek answer is that everything is counted by Catalan numbers. Richard Stanley famously asks the reader of his book Enumerative Combinatorics to count no less than 68 different kinds of mathematical objects. For every single one of them the answer is the Catalan numbers! If nobody expects the Spanish Inquisition, everyone expects the Catalan numbers.
Of course in reality there is no reason the number of friezes should be given by a nice formula -- never mind something as nice as the Catalan numbers. However, Conway and Coxeter tell us how to count friezes. In fact they do even better: they tell us exactly how to make them all. For example, if you want to make all the three-row friezes, you should start with a hexagon and cut it into triangles by using straight lines to connect corners. This is called a triangulation of the hexagon. They then give a recipe for turning that triangulation of the hexagon into a three-row frieze .
Conway and Coxeter show that their recipe turns every triangulation of an n+3-sided polygon into an n-row frieze and that every frieze comes from such a triangulation by their recipe. So the number of n-row friezes is the same as the number of triangulations of the n+3-sided polygon -- and one of Stanley's exercises is to show that the number of triangulations of a polygon is given by the Catalan numbers.
Coxeter's friezes connects to things we know are interesting, and it sure looks like they are pretty darn interesting their own right, but do they point us to something new? If anything, they seem to be an interesting curiosity and nothing more.
Something quite remarkable happened recently. Remember, the papers of Coxeter and Conway-Coxeter were written in the early 1970's. Numerous papers cite their work, but every single one has appeared in the last thirteen years.
What happened thirteen years ago? That's when Fomin and Zelevinsky introduced a new family of mathematical objects they called "cluster algebras" . They introduced them in the hopes they could be used to solve some extremely difficult open problems in mathematics. Those problems are still open, but Fomin and Zelevinsky's aesthetic sense didn't lead them astray. Cluster algebras turned out to be fundamentally important across a wide spectrum of current math research areas. In the short time they've been around researchers have published an astonishing 1000+ research papers on them.
How do simple little trifles from the 1970's play a role in one of the hottest areas of modern math research? Remarkably, by sheer coincidence the smallest cluster algebras exactly correspond to certain Coxeter-Dynkin diagrams. Like the Catalan numbers, these diagrams show up in the most unlikely of places. Coxeter was definitely ahead of his time! The simplest of these is the diagrams of Type A. There is a recipe which uses cluster algebras of Type A to create (and count) friezes. It turns out Coxeter's friezes are the numerical shadow of a rich world of mathematics we are only now discovering.
There are also cluster algebras for the other types of Coxeter-Dynkin diagrams. Using the same recipe you can make new, more complicated friezes for these other types. People are studying these as well. This fall a very nice paper by Fontaine and Plamondon appeared where they show us how to count these more exotic friezes.
And what about Peter Jorgensen's work with Christine Bessenrodt and Thorsten Holm? They went in a different direction and asked instead what happens if you allow your friezes to be infinite in both the horizontal direction and in the vertical direction. That is, you don't have the bounding top and bottom rows of all ones; you only have the Rule for Diamonds. Unlike Coxeter's friezes, these doubly infinite friezes do not have to repeat themselves. And there are certainly infinitely many of them. Nevertheless, Peter and his coauthors have figured out how to extend the Conway-Coxeter recipe and obtain a beautiful description of these doubly infinite friezes.
There's lots to explore in this new world. It only took thirty plus years to see what Coxeter's friezes were showing us all along.
 The Caravaggios are from the Victoria and Albert Museum collection and used under their Terms of Service for nonprofit use.
 Here and elsewhere, since the top and bottom row are always all ones, I only count the rows in the middle.
 Of course math has its feet in the real world through its close relationship with the other sciences.
 Coxeter's original paper can be found here.
 The recipe is actually pretty straightforward: go around the hexagon clockwise and count how many triangles are at each corner. This gives you a list of six numbers. Repeating this list over and over gives you the first row of your frieze and you can use the Rule of Diamonds to calculate all the remaining rows. The same recipe is used for all the other polygons, too.
 An algebra is a kind of a number system with an addition and multiplication. A cluster algebra is one of these number systems along with a proscribed special collection of numbers called the clusters which can be used to make all other numbers. A bit like how the primes are a special collection of numbers which can be used to make all the other integers.
Posted by Jon Kujawa at 12:55 AM | Permalink