I received my copy of Knuth's Art of Computer Programming, Volume 4, Fascicle 0, this week. It contains a long section on median graphs, and coincidentally I had just added a long article on median graphs to Wikipedia, so I've been reading that part with great interest.

One of the exercises, 7.1.1 ex.109, caught my attention. In it, Knuth describes the "binary majorization lattice" in which the elements are the \( n \)-bit binary numbers and in which \( x \) is greater than \( y \) if \( x \) has at least as many nonzeros as \( y \) with \( x \)'s highest order nonzero bit larger than \( y \)'s, \( x \)'s second highest nonzero bit larger than \( y \)'s, and so on. Here it is as drawn by my algorithm for drawing graphs that can be embedded on an integer grid — here the integer grid turns out to be three dimensional, and the awkward folds in the drawing are there because my algorithm doesn't know any better than to put them in.

Binary majorization lattice for n=5

Knuth asks several questions about this lattice, that all become much simpler if one sees its hidden structure: it is really not about binary numbers, but about lower sets in grids, quite like the ones counted by Pascal's triangle but for a triangular grid instead of a rectangular grid. Specifically, this grid:

The grid partial order underlying the binary majorization lattice

As shown in the illustration, each node of the grid is labeled with a Boolean operation on a number \( x \), either setting its lowest order bit to one or flipping two consecutive bits. If you're a mathematician rather than a programmer, the "^=" operation replaces \( x \) by its bitwise exclusive or with the right hand side. Each possible binary number may be formed by choosing a downward-closed subset of this grid, initializing \( x \) to zero, and then applying the operations within that subset. If you perform the operations in bottom-up order you'll get a sequence of increasingly-majorized numbers ending with the one you want, following a path in the graph of the majorization lattice, but because they're just xors you can do the operations in any other order and end up with the same result. With this construction, the majorization order of the binary numbers is exactly the inclusion ordering of downward closed subsets. By Birkhoff's theorem that downward closed sets in any partial order form a distributive lattice (and vice versa), the binary majorization lattice is a distributive lattice (part (d) of the exercise). The greatest lower bounds and least upper bounds in the binary majorization lattices become intersections and unions of downward closed sets (parts b and c). The complement of any number may be formed by the same sequence of operations starting from \( 2^n-1 \) instead of starting from zero; the lattice structure is completely unaffected by this different starting point (part a).

In media theoretic terms, we're analyzing the structure of a partial cube (the graph of the majorization lattice) in terms of the operations used to get from one vertex to another (the xor operations listed in the grid above). The grid contains many operations that look the same as each other in terms of their effects on the binary numbers they operate on, but must be treated differently from each other in axiomatizing this structure as a medium: going from 3 to 5 and from 11 to 13 both involve the same binary operation (xor by 6) but in the first case the xor is shifting the highest order nonzero bit while in the second case it's shifting the second highest order bit, corresponding to the bottom and second-from-bottom xor-by-6 operations in the grid above. As a medium, the binary majorization lattice has pairs of tokens corresponding to each grid node.

Knuth doesn't bother to mention it within the exercise, and it's not set contiguously with the other exercises on median graphs, but: since Birkhoff and Kiss (1947) proved that the graph of any distributive lattice is a median graph, so is the graph of the binary majorization lattice. The median of any three binary numbers \( x \), \( y \), and \( z \) has the median number of nonzeros of the three numbers, the highest order nonzero bit is at the median position of the highest order nonzero bits of \( x \), \( y \), and \( z \), the second highest nonzero bit is at the median position of the second highest nonzero bits of \( x \), \( y \), and \( z \), and so on. In terms of the downward closed grid subsets used to represent \( x \), \( y \), and \( z \), the median is formed by letting these three subsets perform a majority vote on which operations to include.