**Knuth's realization of the associahedra as (Tamari) lattices**

Last night I stumbled into a gem of a lecture from 1993, posted on YouTube about a year ago by the "Computer History Museum":

Donald E. Knuth

Computer Musings: The Associative Law, or The Anatomy of Rotations in Binary Trees

https://www.youtube.com/watch?v=Xp7bnx1wDz4

The lecture is all about the so-called "Tamari lattices" (https://en.wikipedia.org/wiki/Tamari_lattice), which are a family of partially ordered sets closely related to the so-called "Stasheff polytopes" or "associahedra" (https://en.wikipedia.org/wiki/Associahedron). The underlying set of elements of the nth Tamari lattice Y_n can be taken as the set of all possible bracketings of a fixed string of n+1 letters (in other words, all possible ways of combining the letters using n "multiplication" operations), ordered by an

*oriented*version of the associative law:

(ab)c <= a(bc)

Equivalently, we can take the elements of Y_n to be binary trees with n internal nodes (and n+1 leaves), ordered by the "right rotation" transformation (https://en.wikipedia.org/wiki/Tree_rotation).

These posets are called "Tamari lattices" because it was Dov Tamari who originally introduced them in his 1951 thesis, and noticed that they are actually lattices, i.e., that each Y_n has all meets and joins. From what I understand of the history (a bit different from what Knuth says in the video, but I might be incorrect/misremembering), Tamari didn't actually give a formal proof of the lattice property in his thesis, which only came later in collaborations with his students: a first proof published in a 1967 joint paper with Haya Friedman, and a second, simpler proof published in a 1972 joint paper with Samuel Huang (with some difficulty, apparently, since it was "just a new proof of an old result") .

In this lecture from 1993, Knuth gives a new proof of the lattice property of Y_n. It's similar in spirit to the proof by Huang and Tamari, but arguably a lot simpler. (Like Knuth, I've tried reading both the Friedman-Tamari and Huang-Tamari papers before and found them a bit difficult to follow.) It also results in a really beautiful realization of the associahedra as geometric lattices: see the example of Y_4 attached!

The high-level idea for proving the lattice property (which was already in Huang and Tamari's paper) is to:

1. define a

*full and faithful embedding*of Y_n into the poset of lists of natural numbers with the pointwise ordering; in other words, represent each x in Y_n by a code c(x) (of length n) in such a way that x <= y (in Y_n) iff c(x)[i] <= c(y)[i] (as natural numbers) for all indices 0 <= i < n.

2. characterize the image of c( ) by certain conditions on a list of natural numbers, and prove that these conditions are preserved under the operation of taking pointwise minimum. Since the latter is the meet operation in the poset of lists of length n, this proves that x /\ y exists for all x,y in Y_n, and is represented by the code c(x) /\ c(y). (To get joins you can either use a dual argument, or use the fact that the Y_n are finite, and a finite poset with all meets also has all joins.)

Knuth's brilliant insight was to find a very simple algorithm for computing the code c(x) of a binary tree x. For fun you can try to guess it from the example diagram, or else listen to Knuth's very entertaining lecture.

**A question for the audience:**Did you already know about this lattice realization of the associahedra?? It reminds me a bit of Loday's realization (https://arxiv.org/abs/math/0212126), but I think it's extremely nice that Knuth's version also captures oriented associativity, and I'm surprised not to have seen it mentioned anywhere. (If you're a more diligent reader of Knuth you might have already known about this, because it's essentially all there in Exercise 27 of Chapter 7 of Volume 4A of

*The Art of Computer Programming*. I assume Knuth is putting off a more thorough writeup of his proof until after the publication of Volumes 4B, 4C, 4D, and 5-7...)

**Addendum.**About the history of the proof of the lattice property, Tamari has this to say at the end of the introduction to a 1964 report (http://www.numdam.org/item?id=ASCFM_1964__24_3_91_0, predating the publication of Friedman-Tamari but with more or less the same content):

*L’énoncé de ce théorème se trouve déjà dans la thèse de Tamari (Paris 1951), employant aussi les mêmes notations, fondamentales introduites dans le paragraphe suivant, mais sans démonstration. Les traits principaux de la démonstration donnée ici en particulier la plupart des lemmes et propositions im- portants, sont essentiellement dus à un travail de Madame Haya Freedman de l’année 1958. Même avec les nouveaux perfectionnements apportés ici, c’est encore une démonstration assez formidable pour un théorème d’une apparence si modeste. Mais il est à espérer, que les notions et méthodes employées ici ont une portée et une signification plus large, et qu’elles se prêtent à des généralisations importantes. Un exemple dans une direction est la généralisation de l’algorithme d’Euclide du dernier paragraphe ; mais il existe certainement aussi d’exemples d’une toute autre nature.*

**Update #2:**I put a slightly more aesthetic version of Knuth's realization of Y_4 here: http://noamz.org/images/knuth-y4k5.png

- You can also associate a matrix to each vertex of the associahedron. I illustrate an example of this in the image below. The right rotation transformation you're talking about corresponds to multiplying by an elementary matrix e_ij. I wrote more about it here:

https://plus.google.com/u/0/+MichaelNelson/posts/CncCqgEthCR

I think I see what the ordering should be in terms of the matrices though. Let A and B be two matrices associated to the vertices of the associahedron. Then A > B whenever A - B is a non-negative matrix.

One more thing I have to mention. There is a natural map from the permutohedron to the associahedron. Check it out:

https://plus.google.com/u/0/photos/photo/101248704507001510520/6376671046013497314?icm=false&iso=trueSep 21, 2017 - that's interesting: if I understand correctly, Knuth's codes c(x) correspond exactly to the
*row sums*of the matrices m(x) - I, where m(x) is your unitriangular matrix assignment and I is the identity matrix. And I believe you are right that two binary trees are related in the Tamari order just in case the difference of their matrices has only non-negative entries.Sep 22, 2017 - The reason why we can use elementary matrices is because the right rotation transformation satisfies the steinberg relation:

(e_ij)(e_jk) = (e_ik)(e_jk)(e_ij) for i not equal to k

This is where the pentagon comes from. There is another transformation on trees you can do and it is related to the symmetric group. This time you label the internal nodes based on the order from top to bottom, and let the symmetric group act on those labels. The symmetric group satisfies the hexagon relation:

(s_i)(s_i+1)(s_i) = (s_i+1)(s_i)(s_i+1) for 0 < i < n-1

It seems so interesting to me that these two very fundamental groups act on these trees in a mixed up way. This is ultimately why we get a map from the permutohedron to the associahedron.Sep 22, 2017 - Thanks for the pointer to Steinberg relations, I didn't know about that connection. I knew about the permutohedra, but I haven't spent much time thinking about them, and I'm definitely interested in getting a better understanding of the interaction between associativity and symmetry.Sep 22, 2017
- That looks VERY interesting. Speaking of Steinberg realions, Kapraon and Saito (Hidden Stasheff polytopes in algebraic K-theory and in the space of Morse functions, in Higher homotopy structure in topology and mathematical physics (Poughkeepsie, N.Y. 1996), volume 227 of Contemporary Mathematics, 191–225,) suggest that the (labelled) Stasheff polytopes have a link with the higher syzygies of the usual presentation of the Steinberg group and via that to classifying spaces for algebraic K-theory.

Loday's paper (Homotopical Syzygies, in Une d ́egustation topologique: Homotopy theory in the Swiss Alps, volume 265 of Contemporary Mathematics, 99 – 127 Syzygies, in Une d ́egustation topologique: Homotopy theory in the Swiss Alps, volume 265 of Contemporary Mathematics, 99 – 127) which led on to his construction of models of the permutohedron etc. was inspired by Kaproanov -Saito paper (as well as the original Brown Huebschmann paper on identities among relations, which leads us back to rewriting!)Sep 23, 2017 - +Timothy Porter That first paper your referenced is very useful! Thanks! If I'm reading it correctly, the permutohedra correspond to the higher syzygies of the braid group and the associahedra correspond to the higher syzygies of the steinberg group, so the natural map from the permutohedra to the associahedra corresponds to a map from syzygies of the braid group to syzygies of the steinberg group. What kind of information does this tell us? I'm guessing it allows us to relate the cohomology of one group to the cohomology of the other group. I need to learn more about this.

I know quite a bit about the combinatorics behind this map from the permutohedra to the associahedra. The combinatorics involved seems to be quite complicated but interesting. For example, there are

(2^26)(3^4)(5^5)(11^2)(13^2)(17)(19)(23)(29)

vertices on the permutohedron of order 15 which collapse to a special vertex on the associahedron K_16. I go into more detail about that here:

https://plus.google.com/u/0/+MichaelNelson/posts/Qg9TCqQwa8a

Given a vertex v on the associahedron K_n, the number of vertices of the permutohedron of order n+1 which collapse to v is given by a recursive formula I found. Here is an example of how it works:

lh3.googleusercontent.comSep 23, 2017 - You attempt to use the syzygies directly will not work like that. Have a glance at some of the books on Combinatorial Group Theory. You should also note that the associahedron etc are labelled by the generators of the group presentation.

You could also glance at computads / polygraphs and see some of the methods used in that sort of thing.Sep 23, 2017 - Oh okay, thanks for the advice.Sep 23, 2017

Add a comment...