Elementary Number Theory, Group Theory and Ramanujan Graphs is a book in mathematics whose goal is to make the construction of Ramanujan graphs accessible to undergraduate-level mathematics students.
It was written by Giuliana Davidoff, Peter Sarnak, and Alain Valette, and published in 2003 by the Cambridge University Press, as volume 55 of the London Mathematical Society Student Texts book series.
Sparse expander graphs have many important applications in computer science, including the development of error correcting codes, the design of sorting networks, and the derandomization of randomized algorithms.
For these applications, the graph must be constructed explicitly, rather than merely having its existence proven.
[1][2] One way to show that a graph is an expander is to study the eigenvalues of its adjacency matrix.
The spectral expansion of the graph is defined from the difference between the largest and second-largest eigenvalues, the spectral gap, which controls how quickly a random walk on the graph settles to its stable distribution; this gap can be at most
Several constructions of low-degree Ramanujan graphs are now known, the first of which were by Lubotzky, Phillips & Sarnak (1988) and Margulis (1988).
[3][4][5] Reviewer Jürgen Elstrod writes that "while the description of these graphs is elementary, the proof that they have the desired properties is not".
This provides additional motivation for the construction of Ramanujan graphs, as the ones constructed in the book provide explicit examples of the same phenomenon.
This chapter also provides the expected material on spectral graph theory, needed for the definition of Ramanujan graphs.
[2][3][6] Chapter 2, on number theory, includes the sum of two squares theorem characterizing the positive integers that can be represented as sums of two squares of integers (closely connected to the norms of Gaussian integers), Lagrange's four-square theorem according to which all positive integers can be represented as sums of four squares (proved using the norms of Hurwitz quaternions), and quadratic reciprocity.
over the finite fields whose order is a prime number
[3][6] The final chapter constructs the Ramanujan graph
(depending on quadratic reciprocity) with generators defined by taking modulo
The chapter provides formulas for their numbers of vertices, and estimates of their girth.
[3][6] This book is intended for advanced undergraduates who have already seen some abstract algebra and real analysis.
Reviewer Thomas Shemanske suggests using it as the basis of a senior seminar, as a quick path to many important topics and an interesting example of how these seemingly-separate topics join forces in this application.
[6] On the other hand, Thomas Pfaff thinks it would be difficult going even for most senior-level undergraduates, but could be a good choice for independent study or an elective graduate course.