This month's topics:
Enumerative combinatorics in the news
Two recent achievements in enumerative combinatorics were recently publicized on the two sides of the Atlantic.
* On February 8, 2011 Davide Castelvecchi posted an article on the Scientific American website (to appear in the April issue): "Mathematics' Nearly Century-Old Partitions Enigma Spawns Fractals Solution," subtitle: "Newly discovered counting patterns explain and elaborate cryptic claims made by the self-taught mathematician Srinivasa Ramanujan in 1919." Castelvecchi describes very recent work, by Ken Ono (Emory) and collaborators: the determination of an explicit formula for the number p(n) of partitions of n (different ways of expressing a positive integer n as the sum of positive integers), and the study of patterns in the variation of p(n) with n.
These Ferrers diagrams show the partitions of the positive integers 1 (pink) through 8 (dark blue). Each cluster represents a partition; each row is one of the numbers in the partition; the length of the row is the size of the number. For example, the pea-green clusters represent the 5 partitions of 4: clockwise, 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1. Flipping a cluster about the diagonal gives another partition of the same integer; in this display, the partitions are arranged to manifest that relation. Note (for reference below) that the clusters which lie along the diagonal, and only those, are symmetric with respect to the flip. Image from Wikipedia commons.
"Nearly Century-old" refers to conjectures of Ramanujan about the behavior of p(n), but the mystery is much older. Euler made discoveries in this direction around 1750, and would certainly be amazed and pleased to know how things turned out. Ramanujan noticed, as Castelvecchi tells us, "that p(9) = 30, p(9 + 5) = 135, p(9 + 10) = 490, p(9 + 15) = 1,575 and so on are all divisible by 5 ... and posited that this pattern should go on forever, and that similar patterns exist when 5 is replaced by 7 or 11 --there are infinite sequences of p(n) that are all divisible by 7 or 11, or, as mathematicians say, in which the 'moduli' are 7 or 11." Ramanujan made other equally precise and equally mysterious predictions, all of which have been verified by this recent work. What he did not predict, but what has now been shown, is the fractal-like behavior of prime moduli beyond 11: "For example, take the next prime up, 13, and the sequence p(6), p(6 + 13), p(6 + 13 + 13) and so on. Ono's formulas link these values with those of p(1,007), p(1,007 + 132), p(1007 + 132 + 132) and so on. The same formulas link the latter sequence with one where the n's come at intervals of 133 --and so on for larger and larger exponents."
* On February 4, 2011 Maurice Mashaal posted an article on the website of Pour la Science, the French equivalent of Scientific American, "A theorem on stackings of cubes." The theorem in question is in fact about plane partitions, the 2-dimensional generalization of the cluster representation of the p(n) described above.
An example of a totally symmetric plane partition, in this case of n = 142. That number of unit cubes are stacked over integer-coordinate points (i,j) in the positive quadrant, so that the height of the stacks is constant or decreases as i or j increase. This would be a plane partition of 142. Totally symmetric means that when the resulting solid is rotated 120° about the main diagonal in 3D, or flipped by exchanging two of the coordinate axes, it coincides with its original shape.
In the theorem, proved by Chrisoph Koutschan, Manuel Kauers, and Doron Zeilberger (published in the PNAS) the number of planar stackings is counted in a different way. Let's call P(N) the number of totally symmetric planar stackings with greatest height N. (i.e. fitting inside the NxNxN cube in the upper right octant). A formula for P(N) had been known since 1995; but a more refined statement, conjectured independently around 1983 by George Andrews and David Robbins, had "until now resisted the efforts of the greatest minds in enumerative combinatorics" as the authors put it. The statement involves looking at orbits (each orbit consits of a cube together the other cubes in the partition that it can reach by rotation or reflection; the figure highlights three of the orbits in that particular partition) and at the number of distinct orbits in a given totally symmetric plane partition. As Mashaal explains it, the Andrews-Robbins conjecture (now a theorem), is that for any prime q, if a certain universal expression E(q, N) is written as a sum of powers of q, the coefficient of qm is the number of totally symmetric plane partitions, of height at most N, with exactly m orbits.
The proof uses computers in a very intensive and creative way. The authors refer to Paul Erdős' belief that "every short and elegant mathematical statement has a short and elegant 'proof from the book,' and if humans tried hard enough, they would eventually find it." They conclude: "we believe that our general approach, and our way of taming the computer to prove something that seemed intractable with today's hardware and software are very elegant, and deserve to be included in the book."
The shape of musical chords
The February 9, 2011 issue of the Princeton Alumni Weekly features Steve Olson's "A Grand Unified Theory of Music," on the work of Princeton Professor Dmitri Tymoczko. (Tymoczko's 2006 article in Science was picked up in this column). In A Geometry of Music: Harmony and Counterpoint in the Extended Common Practice, coming out next month from Oxford University Press, he "uses the connection between music and geometry to analyze the music of the last millennium and position modern composers in a new landscape." In particular, as he says in his preface, "classical music, jazz, and rock all fit together," built on the same handful of principles. Olson summarizes Tymoczko's basic principles: "First, melodies tend to move short distances from note to note --a characteristic known in music theory as "efficient voice leading." Next "For reasons that aren't entirely clear, humans (including infants) tend to prefer certain kinds of chords to other kinds of chords. Echoing the findings of Pythagoras, we tend to like chords that divide the octave almost, but not completely, evenly." ... "These two properties may seem to be unrelated. But the 'amazing and mysterious' thing about music, Tymoczko says, is that each requires the other." A quote from the author: "Miraculously, the chords that sound good together and the ones that produce efficient voice leading are the same."
"Tymoczko and other music theorists knew that these observations must have a mathematical representation, and previous theorists had captured some of these properties using geometric ideas." Tymoczko was led to the theory of orbifolds, spaces with corner-like singularities, to model musical space. Orbifolds "explained his earlier observations about efficient voice leading and euphonious chords. When orbifolds are used to represent musical sounds, the chords that most evenly divide the octave reside in the central regions of the space." ... "Composers can move from one euphonious chord to another while moving short distances in the central region of a musical space. Movements of short distances correspond to notes that are close together, producing singable melodies." To show us how this looks, Olsen reproduces one of Tymoczko's images of musical space:
Four-note chords as part of an orbifold: "collections of notes form a tetrahedron, with the colors indicating the spacing between the individual notes in a sequence. In the blue spheres, the notes are clustered; in the warmer colors, they are farther apart. The red ball at the top of the pyramid is the diminished seventh chord. Near it are all the most familiar chords of Western music." Click to expand. Image courtesy of Dmitri Tymoczko.
Comments: Email Webmaster