<p><a href="https://en.wikipedia.org/w/index.php?title=Ramanujan_graph&amp;oldid=383972239" rel="nofollow noreferrer">Wikipedia</a> delivers this answer rather promptly. Quoting</p>
<blockquote>
<p>Constructions of Ramanujan graphs are often algebraic. Lubotzky, Phillips and Sarnak show how to construct an infinite family of <span class="math-container">$p+1$</span>-regular Ramanujan graphs, whenever <span class="math-container">$p \equiv 1 \pmod 4$</span> is a prime. Their proof uses the <a href="https://en.wikipedia.org/wiki/Ramanujan%E2%80%93Petersson_conjecture" rel="nofollow noreferrer">Ramanujan conjecture</a>, which led to the name of Ramanujan graphs.</p>
</blockquote>
<p>The paper referred to is <a href="https://doi.org/10.1007/BF02126799" rel="nofollow noreferrer"><em>Ramanujan graphs</em></a>;
A. Lubotzky, R. Phillips and P. Sarnak, COMBINATORICA Volume 8, Number 3 (1988), 261-277,  DOI: 10.1007/BF02126799.</p>

CC BY-SA 2.5
2010-10-19T21:51:10.830Z
the question is: what is the ramanujan conjecture
Suresh Venkat
CC BY-SA 2.5
2010-10-20T02:21:08.510Z
It is sometimes much better to preserve links when you quote.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-20T13:31:05.077Z
Indeed. I underestimated the seriousness of the question.
Dave Clarke
CC BY-SA 4.0
2010-10-19T20:39:18.847Z
2023-04-26T11:21:58.797Z
2023-04-26T11:21:58.797Z
Dave Clarke
<p>To add some content to the answers here, I'll explain briefly what Ramanujan's conjecture is.</p>

<p>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$.  </p>

<p>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$.  </p>

<p>A reference, other than the Lubotzky-Phillips-Sarnak paper itself, is Noga Alon's brief description in <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5803&amp;rep=rep1&amp;type=pdf">Tools from Higher Algebra</a>.</p>

CC BY-SA 2.5
2010-10-19T22:08:55.940Z
nice ! great answer.
Suresh Venkat
CC BY-SA 2.5
2010-10-19T22:01:13.457Z
2010-10-19T22:01:13.457Z
arnab
<p>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? </p>

<graph-theory><soft-question><ho.history-overview><expanders>
Why are Ramanujan graphs named after Ramanujan?
Dana Moshkovitz
# Why are Ramanujan graphs named after Ramanujan?

(Asked by: username_0 on 2010-10-19)

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?

**Tags:** graph-theory, soft-question, ho.history-overview, expanders


---

## 2 answers

### Answer by username_4 on 2010-10-19. Score: 36 | Accepted answer

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.5803&rep=rep1&type=pdf).

> **Comments:**
> **username_2**: nice ! great answer.  

---

### Answer by username_1 on 2010-10-19. Score: 21

[Wikipedia](https://en.wikipedia.org/w/index.php?title=Ramanujan_graph&oldid=383972239) 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](https://en.wikipedia.org/wiki/Ramanujan%E2%80%93Petersson_conjecture), which led to the name of Ramanujan graphs.

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

> **Comments:**
> **username_2**: the question is: what is the ramanujan conjecture  
> **username_3**: It is sometimes much better to preserve links when you quote.  
> **username_1**: Indeed. I underestimated the seriousness of the question.  

---

