Elementary Number Theory, Group Theory and Ramanujan Graphs

In graph theory, expander graphs are undirected graphs with high connectivity: every small-enough subset of vertices has many edges connecting it to the remaining parts of the graph. 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. For an ${\displaystyle r}$-regular graph, these are real numbers in the interval ${\displaystyle [-r,r]}$, and the largest eigenvalue (corresponding to the all-1s eigenvector) is exactly ${\displaystyle r}$. 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 ${\displaystyle 2{\sqrt {r-1}}}$. The Ramanujan graphs are defined as the graphs that are optimal from the point of view of spectral expansion: they are ${\displaystyle r}$-regular graphs whose spectral gap is exactly ${\displaystyle 2{\sqrt {r-1}}}$.[3]

Although Ramanujan graphs with high degree, such as the complete graphs, are easy to construct, expander graphs of low degree are needed for the applications of these graphs. 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". Elementary Number Theory, Group Theory and Ramanujan Graphs aims to make as much of this theory accessible at an elementary level as possible.[3]

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]