A Ramanujan graph is a connected finite graph of valency k whose eigenvalues (apart from k and −k) all have modulus at most 2√(k−1). This interval is the spectrum of the infinite k-valent tree T (regarded as an operator on L2(T)), and so there is a sense in which a Ramanujan graph is a best finite approximation to the tree; these graphs tend to have high girth and very good expansion properties.
In the late 1980s, Lubotzky, Phillips and Sarnak published a construction of Ramanujan graphs, which was a heady mix of number theory, geometry, representation theory, and combinatorics. I liked the paper so much that I gave a seminar to tell my colleagues about it. I will make a few comments here.
Let p and q be two primes congruent to 1 (mod 4). In any expression for p as a sum of four squares, one is odd and the other three even; if we take the first one to be odd and positive, there are just p+1 expressions, by a theorem of Jacobi. We can represent the corresponding 4-tuples as quaternions over GF(q), and indeed (by our condition on q) as 2×2 matrices. The set of matrices is closed under inversion and generates PGL(2,q) or PSL(2,q). Now the Cayley graph is the required Ramanujan graph.
From a higher perspective, what is going on here? Take R to be either the p-adic integers or the formal power series ring over GF(p), and F its field of fractions. Associated with PGL(2,F) and its maximal compact subgroup PGL(2,R) is a building, which in this case is the (p+1)-valent tree; taking the quotient by a cocompact subgroup gives a graph which is finite (since it is compact and discrete). If the subgroup we choose is the congruence subgroup mod q, we get the above construction. Now a theorem of Deligne, off-the-shelf, enables the facts about its spectrum to be proved.
The highlight of yesterday was Alex Lubotzky’s talk. He started out by reminding us of the above. Now he and his colleagues have developed a higher-dimensional version of this. Rather than PGL(2,F), they take an algebraic group of higher rank, so that at the first step they get a building of rank greater than 1. Again, the quotient by a congruence subgroup gives a finite quotient. So far, so standard; but they split the adjacency relation in the building into d “Hecke-like” operators which, although they are not self-adjoint, are normal (commute with their adjoints) and pairwise commuting, hence are simultaneously diagonalisable, by a theorem which I regard as standard linear algebra (but seems to be less well known than it should be). Now the “spectrum” of the building is a subset of d-dimensional space, and contains the essential part of the spectrum of the finite quotient.
They call the resulting object a “Ramanujan complex”. This work was not driven by applications, but for sure applications of such an appealing concept are bound to arise; indeed this process has already started (leaving aside the “building” of that name at IIT Kharagpur in India!)
In the evening, rather than a “conference dinner”, we had a celebration dinner for Péter Pál Pálfy’s birthday. The event began with a concert by a recorder group led by a leading Hungarian musician. They played six pieces, two old (my favourite was Sufi music from Turkey, transcribed in Padova, and now in a manuscript in London), two modern, and two electronic (the first with several mobile phones which had been set to “resonate” with certain notes played by the recorders; in the second, the recorders were not played in the conventional way but controlled the electronics directly). An interesting concert with some really beautiful pieces.
There were many tributes to P-cubed, perhaps my favourite from his supervisor Laci Babai. He explained that Paul Erdős said that, when half your co-authors “leave”, then your time has probably come; but half is measured not by number or even number of papers, but by the “weight” of the work (by which, obviously, he means something different from the number of pages!). For that reason, he (Laci) could not avoid some self-interest in wishing P-cubed a long and prosperous life.