this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, Group Theory and Ramanujan Graphs.

I have heard rumors of a different proof of the main result -- that the Cayley graphs $\Gamma(p,q)$ constructed from $PGL_2(\mathbb{F}_q)$ and a generating set $S_p$ have the Ramanujan bound on their largest real eigenvalue -- which relies on the following series of ideas.

  1. One defines the Ihara Zeta function of the graph, and shows that the expander property for a graph (this is an inequality on its largest real eigenvalue) is equivalent to the Riemann hypothesis for the Ihara Zeta function, i.e. the assertion that it has poles only along $z=q^{1/2}$.

  2. One identifies the Ihara Zeta function for $\Gamma(p,q)$ with the Zeta function for some curve over $\mathbb{F}_q$, presumably it is something double coset space $H\backslash PGL_2(\mathbb{F}_q) / H,$ for some canonical subgroup $H$. Herein lies my question!

  3. One then applies the Weil conjectures/Riemann hypothesis for curves over finite fields, to determine that the $\Gamma(p,q)$ have the claimed Ramanujan property.

The problem is that I can't find a clear exposition anywhere of step 2, i.e. a simple statement of exactly which curve has its Zeta function equal that of the Ihara Zeta function, and how to prove that.

  • $\begingroup$ One might further guess that $H$ has to do with $p$-congruence subgroups in $PGL_2(\mathbb{Z})$, but it's just a guess. $\endgroup$ – David Jordan Mar 3 '14 at 13:54
  • $\begingroup$ Do you know any simple description for the Ihara zeta function of this graph? What is the generating set $S_p$? $\endgroup$ – Will Sawin Mar 3 '14 at 16:54
  • $\begingroup$ I believe all this and more can be found in Descrete Groups, Expanding graphs and invariant measures by Alex Lubotzky. $\endgroup$ – Benjamin Steinberg Mar 3 '14 at 23:50
  • $\begingroup$ Dear Benjamin, thanks for pointing me to that book! Indeed that seems to have the clearest statement of the state of the art, so it was very helpful to find. Unfortunately, he says rather that it would be nice if one could relate the above Cayley graphs to some finite curves, but indicates this isn't known. $\endgroup$ – David Jordan Mar 12 '14 at 8:37
  • $\begingroup$ For Ramanujan graphs coming Cayley graphs I don't know the exact story, but using Brandt matrices you can get Ramanujan graphs out of the dual graphs of certain Shimura curves. Pete Clark has some "rambling notes" on this subject here math.uga.edu/~pete/ramanujanrevisited.pdf and I covered some smaller cases in a course I taught a year ago. $\endgroup$ – stankewicz Mar 12 '14 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.