Mathematics Colloquium, Fall 2007

Shuffling the mod p line at infinity and the eigenvibrations of methane

How many times do we need to shuffle a deck of cards? How many turns of Rubik's cube take us to a truly random configuration? The general context of these questions is the mixing rate of random walks on a finite group G, a subject at the confluence of diverse areas such as probability theory, number theory, isoperimetry, abstract harmonic analysis, arithmetic combinatorics; it has also produced profound results used extensively in the theory of computing.

The group G = SL(2,p) of 2 by 2 matrices mod p with determinant 1 is of particular interest because of its phenomenal expansion, exploited in a number of works, including the celebrated construction of "Ramanujan graphs" in the 80s by Margulis, Lubotzky, Phillips, and Sarnak, and a recent breakthrough by Helfgott based on "sum-product estimates," cornerstones of the emerging field of "arithmetic combinatorics" (Bourgain, Katz, Tao, 2004).

Even more recently Tim Gowers added a new twist, linking some of this expansion to a century-old result of Frobenius and a 1930 observation by physicist Eugene Wigner on molecular eigenvibrations, together with the theory of "quasirandomness" in graphs from around 1990. I will illustrate Gowers' trick on a new mixing theorem obtained in joint work with Nikolay Nikolov and Laszlo Pyber.

In spite of all the name-dropping in the abstract, no background beyond a little discrete probability, the concept of a group, and basic linear algebra will be required. Undergraduates are welcome to attend.