Elementary Number Theory, Group Theory and Ramanujan Graphs

Its authors have divided Elementary Number Theory, Group Theory and Ramanujan Graphs into four chapters. The first of these provides background in graph theory, including material on the girth of graphs (the length of the shortest cycle), on graph coloring, and on the use of the probabilistic method to prove the existence of graphs for which both the girth and the number of colors needed are large. 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. Chapter 3 concerns group theory, and in particular the theory of the projective special linear groups ${\displaystyle PSL(2,\mathbb {F} _{q})}$ and projective linear groups ${\displaystyle PGL(2,\mathbb {F} _{q})}$ over the finite fields whose order is a prime number ${\displaystyle q}$, and the representation theory of finite groups.^[3][6]

The final chapter constructs the Ramanujan graph ${\displaystyle X^{p,q}}$ for two prime numbers ${\displaystyle p}$ and ${\displaystyle q}$ as a Cayley graph of the group ${\displaystyle PSL(2,\mathbb {F} _{q})}$ or ${\displaystyle PGL(2,\mathbb {F} _{q})}$ (depending on quadratic reciprocity) with generators defined by taking modulo ${\displaystyle q}$ a set of ${\displaystyle p+1}$ quaternions coming from representations of ${\displaystyle p}$ as a sum of four squares. These graphs are automatically ${\displaystyle (p+1)}$-regular. The chapter provides formulas for their numbers of vertices, and estimates of their girth. While not fully proving that these graphs are Ramanujan graphs, the chapter proves that they are spectral expanders, and describes how the claim that they are Ramanujan graphs follows from Pierre Deligne's proof of the Ramanujan conjecture (the connection to Ramanujan from which the name of these graphs was derived).^[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.^[2]