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

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’énoncé de ce théorème se trouve déjà dans la thèse de Tamari (Paris 1951), employant aussi les mêmes notations, fondamentales introduites dans le paragraphe suivant, mais sans démonstration. Les traits principaux de la démonstration donnée ici en particulier la plupart des lemmes et propositions im- portants, sont essentiellement dus à un travail de Madame Haya Freedman de l’année 1958. Même avec les nouveaux perfectionnements apportés ici, c’est encore une démonstration assez formidable pour un théorème d’une apparence si modeste. Mais il est à espérer, que les notions et méthodes employées ici ont une portée et une signification plus large, et qu’elles se prêtent à des généralisations importantes. Un exemple dans une direction est la géné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
Shared publiclyView activity