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?


2 Answers 2


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.

  • 2
    $\begingroup$ nice ! great answer. $\endgroup$ Commented Oct 19, 2010 at 22:08

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.

  • $\begingroup$ the question is: what is the ramanujan conjecture $\endgroup$ Commented Oct 19, 2010 at 21:51
  • $\begingroup$ It is sometimes much better to preserve links when you quote. $\endgroup$ Commented Oct 20, 2010 at 2:21
  • $\begingroup$ Indeed. I underestimated the seriousness of the question. $\endgroup$ Commented Oct 20, 2010 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.