Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski (Q1332484)

This exciting book marks the genesis of a new field. It is a field in which one passes back and forth at will through the looking glass dividing the discrete from the continuous. For example, the spectral theory of the Laplacian on a Riemannian manifold mirrors the spectral theory of the combinatorial Laplacian \(\Delta = \text{kI} - A\), where \(A\) is the adjacency matrix of a finite \(k\)-regular graph. Group theory binds the two sides of the mirror. The prime example is the group \(\text{SL} (2,F)\) of all \(2\times 2\) matrices of determinant 1 with elements in the field \(F\), where \(F\) can be the field \(\mathbb{R}\) of real numbers, the field \(\mathbb{Q}_p\) of \(p\)-adic numbers, or the finite field \(\mathbb{F}_p\) with \(p\) elements, where \(p\) is a prime. Here we give an outline of the chapters. Chapter 1 includes a survey of expander graphs. A \(k\)-regular graph \(X\) is defined to be a \(c\)-expander for a positive real number \(c\) iff for every subset \(A \subset X\), we have \[ |\partial A |\geq c \left( 1 - {|A|\over |X|} \right)\;|A|,\quad \text{where}\quad \partial A = \{y \in X \mid d(y,A) = 1\}. \] Usually \(k\) and \(c\) are fixed and \(n\) is allowed to approach infinity. The applications of expanders are to computer science. See, for example, \textit{J. Friedman} (Ed.) [Expanding Graphs, DIMACS, Ser. Discret. Math. Theor. Comput. Sci., Vol. 10, (1993; Zbl 0777.00033)] and \textit{M. Klawe} [SIAM J. Comput. 13, 156-166 (1984; Zbl 0537.68068)]. Chapter 2 concerns the Banach-Ruziewicz problem. It begins with the Hausdorff-Banach-Tarski paradox saying that for \(n \geq 2\), the \(n\)- sphere \(S^n\) can be decomposed into finitely many pieces, from which one can reconstruct 2 copies of \(S^n\) using only rotations from \(O(n + 1)\). Chapter 3 introduces Kazhdan's property \(T\). A locally compact group \(G\) has this property iff the trivial representation of \(G\) is isolated in the Fell topology. In Section 3.3, one sees how to construct expander graphs, using a lattice \(\Gamma\) in \(G\); i.e., a discrete subgroup \(\Gamma\) of \(G\) with \(\text{Vol} (G/\Gamma) < \infty\), assuming that \(\Gamma\) has property \(T\). Examples of lattices are considered; e.g., the group \(\text{SL}_n (\mathbb{Z})\) of all \(n \times n\) integer matrices of determinant 1, which has Kazhdan's property \(T\) iff \(n \geq 3\) (or \(n = 1\)). Groups constructed using quaternions are also considered. Chapter 4 involves the Laplacian on a connected Riemannian manifold and the discrete analogue on a finite connected \(k\)-regular graph \((\text{kI} - A)\), where \(A\) is the adjacency operator of the graph. Cheeger's inequality for a manifold has a graph-theoretic analogue which implies that the problem of finding expander graphs is essentially equivalent to bounding the smallest positive eigenvalue of the combinatorial Laplacian from below. Selberg's lower bound on eigenvalues of the Laplacian for congruence subgroups of the modular group is shown to lead to a construction of expander graphs. A \(k\)-regular graph \(X\) is called Ramanujan if for every eigenvalue of the adjacency matrix \(A\) with \(|\lambda |\neq k\), we have \(|\lambda|\leq 2 \sqrt {k - 1}\). Much of the rest of the book is devoted to the construction of infinite families of Ramanujan graphs with bounded degree and which provide better expanders than those constructed using Selberg's theorem or Kazhdan's property \(T\). It is also noted that a \(k\)-regular graph is Ramanujan iff its Ihara zeta function satisfies the analogue of the Riemann hypothesis. For a proof the reader is referred to \textit{T. Sunada} [Lect. Notes Math. 1339, 248-277 (1987; Zbl 0646.58027)] and \textit{K. Hashimoto} [Adv. Stud. Pure Math. 15, 211-280 (1989; Zbl 0709.22005)]. Chapter 5 concerns the representations of \(\text{PGL}_2\) over the real numbers and the \(p\)-adic numbers. Chapter 6 gives an adelic representation theoretic formulation of the Ramanujan conjecture for modular forms. Results of Jacquet and Langlands and Deligne are stated for later use. The chapter refers to \textit{M. F. Vignéras} [Sémin. Delange-Pisot-Poitou (1981/82), Prog. Math. 38, 321-343 (1983; Zbl 0523.10015)] and \textit{I. Gel'fand, M. I. Graev, I. Piatetski-Shapiro} [Representation theory and automorphic functions, Saunders (1969; Zbl 0177.180)], for example. In Chapter 7, we find the solution of the Banach-Ruziewicz problem for \(n = 2,3\) and a construction of Ramanujan graphs. Surprisingly, both problems are solved using the same group \(\Gamma\). The proofs use the work of Deligne and Jacquet and Langlands described in Chapter 6. Chapter 8 shows that every finite simple non-abelian group has a set \(S\) of at most 7 generators such that every element of \(G\) can be written as a word of length \(O(\log |G|)\) with letters from \(S \cup S^{- 1}\). More infinite families of Ramanujan graphs are given (but having unbounded degrees). The short Chapter 9 concerns distributing points on the sphere. Chapter 10 is a list of open problems. To give the flavor, let's list a few of these problems. Problem 10.1.1. asks for the best expansion coefficient for an infinite family of \(k\)-regular graphs. Problem 10.4.4. asks for the extension of the definition of Ramanujan graphs to non- regular graphs. Problem 10.7.1. asks for a clarification of the connection between eigenvalues and girth. To summarize, the book brings together information on many topics that one might at first think are unrelated, from expander graphs to the Banach-Ruziewicz problem of uniqueness of a finitely additive rotation invariant measure on the \(n\)-sphere. The book is a charming combination of topics from group theory (finite and infinite), combinatorics, number theory, harmonic analysis. It is not a self-contained book, however. Missing, for example, is Deligne's proof of the Ramanujan-Petersson conjecture on bounds for Fourier coefficients of modular forms as well as a complete proof of the Jacquet-Langlands correspondence. The appendix by J. D. Rogawski gives an introduction to these subjects. Another useful reference is \textit{P. Diaconis} [Group Representations in Probability and Statistics, Inst. of Math. Statistics, Hayward, CA (1988; Zbl 0695.60012)]. Other references in this area are: \textit{P. Sarnak} [Some Applications of Modular Forms, Cambridge U. Press (1990; Zbl 0721.11015)], \textit{R. Brooks} in [Topology 90, 61-75 (1992; Zbl 0764.58031)], \textit{P. Buser} [Geometry and Spectra of Compact Riemann Surfaces, Birkhäuser (1992; Zbl 0770.53001), Chapter 11], \textit{T. Sunada} [op. cit.] and \textit{J. Angel, S. Poulos}, the reviewer, \textit{C. Trimble} and \textit{E. Velasquez} [Contemp. Math. 173, 15-70 (1994)]. For example, there are relations between the Selberg trace formula for continuous and finite groups. This leads to the finite analogue of Selberg's zeta function, called the Ihara zeta function mentioned above. You also find (in the book of Buser above) Cayley graphs that ultimately led to a solution of a problem of \textit{M. Kac} [Am. Math. Mon. 73, 1-23 (1966; Zbl 0139.056)]. The solution can be found in \textit{C. Gordon, D. Webb} and \textit{S. Wolpert} [Invent. Math. 110, 1-22 (1992; Zbl 0778.58068)].