Why are Ramanujan graphs named after Ramanujan?

Question

I recently taught expanders, and introduced the notion of Ramanujan graphs. Michael Forbes asked why they are called this way, and I had to admit I don't know. Anyone?

Answer 1

To add some content to the answers here, I'll explain briefly what Ramanujan's conjecture is.

First of all, Ramanujan's conjecture is actually a theorem, proved by Eichler and Igusa. Here is one way to state it. Let $r_m(n)$ denote the number of integral solutions to the quadratic equation $x_1^2 + m^2 x_2^2 + m^2 x_3^2 + m^2 x_4^2 = n$. If $m=1$, that $r_m(n) > 0$ was of course proved by Legendre, but Jacobi gave the exact count: $r_1(n) = 8 \sum_{d \mid n, 4 \not \mid d} d$. Nothing similarly exact is known for larger $m$ but Ramanujan conjectured the bound: $r_m(n) = c_m \sum_{d \mid n} d + O(n^{1/2 + \epsilon})$ for every $\epsilon > 0$, where $c_m$ is a constant dependent only on $m$.

Lubtozky, Phillips and Sarnak constructed their expanders based on this result. I'm not familiar with the details of their analysis but the basic idea, I believe, is to construct a Cayley graph of $PSL(2,Z_q)$ for a prime $q$ that $1 \bmod 4$, using generators determined by every sum-of-four-squares decomposition of $p$, where $p$ is a quadratic residue modulo $q$. Then, they relate the eigenvalues of this Cayley graph to $r_{2q}(p^k)$ for integer powers $k$.

A reference, other than the Lubotzky-Phillips-Sarnak paper itself, is Noga Alon's brief description in Tools from Higher Algebra.

Answer 2

Wikipedia delivers this answer rather promptly. Quoting

Constructions of Ramanujan graphs are often algebraic. Lubotzky, Phillips and Sarnak show how to construct an infinite family of $p+1$-regular Ramanujan graphs, whenever $p \equiv 1 \pmod 4$ is a prime. Their proof uses the Ramanujan conjecture, which led to the name of Ramanujan graphs.

The paper referred to is Ramanujan graphs; A. Lubotzky, R. Phillips and P. Sarnak, COMBINATORICA Volume 8, Number 3 (1988), 261-277, DOI: 10.1007/BF02126799.