Today I’m making two blog posts about exceptional reviews: one review of a book and one of a paper. This post is about Harald Helfgott‘s review of Terry Tao‘s book, Expansion in finite simple groups of Lie type, published by the AMS. The other post is about Grigor Sargsyan‘s exceptional review of a paper: John Steel‘s chapter, An outline of inner model theory, in the Handbook of Set Theory edited by Matthew Foreman and Akihiro Kanamori [MR2768678].
Before I get going, I should point out that I was involved in the discussion with Tao about publishing some of his blog material as books, a point whose relevance will become clear below. Helfgott’s review has several exceptional characteristics. To begin with, it is thorough – as you might guess at a glance at the length. But it is not just that he says a lot, his discussion is quite thoughtful. As I see in many excellent reviews, Helfgott establishes the context of the work early on in the review. He begins, though, by giving a three-sentence précis of the book, followed by a quick three-sentence assessment of the book. So before you get going, you have a rough idea of what you will be reading. The main body of the review is a mix of telling us what is in the book – the main topics as well as the major theorems – and the reviewer’s comments on them. In the discussion of Chapter 1, Helfgott seems surprised that Tao proves a weak form of the Cheeger-Alon-Milman inequality, when with less fuss a shorter and more natural proof (which he sketches) gives an optimal form of the result. As we continue reading the review, we see several more times where Helfgott wonders about Tao’s choices. There are other instances where the book offers up a weaker form of a result, when the stronger form could be offered without a lot of extra fuss. Helfgott also points out how Tao’s great breadth introduces some shorthands that we mere mortals may need a bit more explanation. One example is in Chapter 3 where Tao quickly skips ahead writing “after regularizing $f_n$ in a standard fashion to make it smooth rather than merely Lipschitz”. An analyst (which is one of Tao’s métiers) will be fine with this, but lots of people interested in expanders in finite groups are not analysts. My experience with Tao’s writing is that he is extremely good at conveying how he thinks about particular problems or entire subjects. This can be great when you are able to keep up. If not, you need to do some extra work – though it is invariably worth the effort. Helfgott concludes his review with two general comments: an excellent blog does not automatically translate into an excellent book, but, at the same time, this book is a very valuable resource.
MR3309986
Tao, Terence
Expansion in finite simple groups of Lie type.
Graduate Studies in Mathematics, 164. American Mathematical Society, Providence, RI, 2015. xiv+303 pp. ISBN: 978-1-4704-2196-0
20D06 (05C25 05C81 11B30 17B20 20F65 20G30 22D10)
This is a book based on the author’s blog. The first half consists of lecture notes for a course taught by the author a few years ago on expansion in Cayley graphs. The second half is much more loosely organized; it is essentially a collection of blog posts having a more or less close link to the subject of the book.
The reviewer has just taught a course using this book as one of his main sources. The first thing to say is that it is undoubtedly a very useful resource. However, whoever uses the book for teaching will be well advised to collect other sources, and to take some time to reflect while reading each chapter, pondering whether matters can be taught in a shorter or cleaner way.
In part because the book’s choice of topics is actually quite good, we shall go over the text in some detail. Before starting, let us recall the different definitions of expansion, the book’s main subject. Let $\Gamma$ be a regular graph, i.e., one in which every vertex has the same degree (“valence”) $d$. A regular graph is an $\epsilon$-expander if it has spectral gap of size $\geq \epsilon$, i.e., if the second largest value of the adjacency matrix is $\leq (1 – \epsilon) d$, or, what is the same, if the second smallest value of the discrete Laplacian is $\geq \epsilon$. There are two slightly different definitions of combinatorial expansion, namely, vertex and edge expansion. A regular graph is an $\epsilon$-edge expander if, for every subset $S$ of the set of vertices $V$ with $|S|\leq |V|/2$, there are $\geq \epsilon d |S|$edges with their tails in $S$ and their heads outside it.
A family of graphs is an expander family if there is an $\epsilon>0$ for which they are all $\epsilon$-expanders. This is of particular interest if the degree of the graphs in the family is constant.
Chapter 1 defines expander graphs in the two senses above. The relation between the two is established, in that the text proves a weak form of the discrete Cheeger(-Alon-Milman) inequality: for every $\epsilon>0$ and every $d\geq 1$ there is a $\delta>0$ such that if a graph of degree $d$ is an $\epsilon$-edge expander, then it is a $\delta$-expander. (The other direction, viz., that an $\epsilon$-expander is an $\epsilon/2$-edge expander, is easy.) Random walks are also mentioned; it is an exercise to show that expansion is equivalent to a very strong form of $\ell_2$ mixing in logarithmic time. Finally, it is shown that, for $d$ large, there is an$\epsilon>0$ such that random graphs of degree $d$ with $n$ vertices are $\epsilon$-expanders with probability tending to $1$ as $n\to \infty$, where a “random graph” is taken with respect to a slightly nonuniform distribution.
A few remarks are in order. The text proves a weak form of the Cheeger-Alon-Milman inequality; as it happens, one can do a little better with less trouble than in the book. To obtain a qualitatively optimal form of the inequality (namely, that an $\epsilon$-edge expander has a spectral gap $\delta \gg \epsilon^2$), one just needs to treat an arbitrary function $\phi\:V\to \Bbb{R}$ by first subtracting its median, and then applying what is essentially edge-expansion plus summation by parts (p. 12) to the part of $\phi$ above the median and the part below the median (as one can, given that each part has support of size $\leq |V|/2$, by the definition of “median”). This is shorter and arguably more natural than the proof in the book.
The proof that random graphs are expanders is also needlessly complicated. If one is going to take a nonuniform distribution anyhow, one can allow one’s graphs to have a few doubled edges or self-loops; one can then fix these without breaking the edge-expansion property.
Chapter 2 starts with the definitions of Cayley and Schreier graphs. It proceeds quite quickly, first defining Kazhdan’s property $(\rm T)$ and using induced representations to show that, given a locally compact group $G$ and a locally compact subgroup $H$ of finite covolume, $G$ has property $(\rm T)$ if and only if $H$ has. The idea of the ping-pong lemma is used to establish that if a probability measure on $\Bbb{R}^2$ is almost-invariant under the action of a compact neighborhood in ${\rm SL}_2(\Bbb{R})$, then it is almost entirely concentrated at the origin; this gives us that the pair $({\rm SL}_2(\Bbb{R}) \ltimes \Bbb{R}^2, \Bbb{R}^2)$ has relative property $(\rm T)$, and a construction based on the Mautner phenomenon (via Moore) is then used to show that this implies that ${\rm SL}_3(\Bbb{R})$ has property $(\rm T)$ (Kazhdan). Since ${\rm SL}_3(\Bbb{Z})$ is of finite covolume in ${\rm SL}_3(\Bbb{R})$, we conclude that ${\rm SL}_3(\Bbb{Z})$ has property $(\rm T)$, and so, given any set of generators $S$ of ${\rm SL}_3(\Bbb{Z})$ and any sequence of finite-index normal subgroups $N_n \triangleleft {\rm SL}_3(\Bbb{Z})$, the Cayley graphs $\{\Gamma({\rm SL}_3(\Bbb{Z})/N_n,S \bmod N_n)\}_n$ of ${\rm SL}_3(\Bbb{Z})/N_n$ with respect to $S \bmod N_n$ form an expander family [G. A. Margulis, Problemy Peredači Informacii 9 (1973), no. 4, 71–80; MR0484767]. In general, while the treatment is standard, this is one of the best parts of the book; the presentation is tight, and explains non-trivial concepts clearly.
The chapter ends with a brief sketch of a proof (following [O. Gabber and Z. Galil, J. Comput. System Sci. 22 (1981), no. 3, 407–420; MR0633542] and [S. Jimbo and A. Maruoka, Combinatorica 7 (1987), no. 4, 343–355; MR0931192], and [S. Hoory, N. Linial and A. Wigderson, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561; MR2247919]) that Schreier graphs associated with ${\rm SL}_2(\Bbb{Z}/n\Bbb{Z}) \ltimes (\Bbb{Z}/ n\Bbb{Z})^2$ form an expander family. This proof skips property $(\rm T)$ and the Mautner phenomenon, and reduces the argument to its essence, viz., the use of the ping-pong lemma as above (applied this time to probability measures on $\Bbb{Z}$) combined with a little Fourier analysis over $(\Bbb{Z}/n\Bbb{Z})^2$. Pedagogically, it might have made more sense to start with this and then introduce property $(\rm T)$ (or just property ($\tau$)) to build matters up to ${\rm SL}_3(\Bbb{Z})$. This can be done quite naturally; one then ends with a proof of property $(\rm T)$ for ${\rm SL}_3(\Bbb{Z})$ that does not go through ${\rm SL}_3(\Bbb{R})$ ([M. Burger, J. Reine Angew. Math. 413(1991), 36–67; MR1089795; Y. Shalom, Inst. Hautes Études Sci. Publ. Math. No. 90 (1999), 145–168 (2001); MR1813225]; see also the expositions in [M. E. B. Bekka, P. de la Harpe and A. Valette, Kazhdan’s property (T), New Math. Monogr., 11, Cambridge Univ. Press, Cambridge, 2008 (§4.2); MR2415834] or [E. Kowalski, The large sieve and its applications, Cambridge Tracts in Math., 175, Cambridge Univ. Press, Cambridge, 2008 (§D.4); MR2426239]). Of course, property$(\rm T)$ for ${\rm SL}_3(\Bbb{R})$ is of interest in itself.
Chapter 3 introduces “quasi-random groups”, meaning groups $G$ that have no non-trivial complex representations of small dimension. (This is, for instance, the case for $G = {\rm SL}_2(\Bbb{F}_p)$, which has no non-trivial complex representations of dimension $<(p-1)/2$ (Frobenius).) In a quasi-random group, the eigenspace of the Laplacian corresponding to a non-trivial eigenvalue cannot have small dimension, since $G$ acts non-trivially on it. This fact is used in two ways. First, it implies that large subsets of $G$ mix very quickly under multiplication (§3.1; see [W. T. Gowers, Combin. Probab. Comput. 17 (2008), no. 3, 363–387;MR2410393; L. Babai, N. V. Nikolov and L. Pyber, in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 248–257, ACM, New York, 2008; MR2485310]). Second, it can be used, as in [P. C. Sarnak and X. X. Xue, Duke Math. J. 64 (1991), no. 1, 207–227; MR1131400], to prove a version of A. Selberg’s spectral gap [in Proc. Sympos. Pure Math., Vol. VIII, 1–15, Amer. Math. Soc., Providence, RI, 1965; MR0182610] (i.e., the fact that the second smallest eigenvalue of the Laplacian on the surface $\Gamma(N)/\Bbb{H}$ is bounded below by a constant). This spectral gap is then used to show (§3.2) that, for any set of generators $S$ of ${\rm SL}_2(\Bbb{Z})$, the Cayley graphs $\Gamma({\rm SL}_2(\Bbb{F}_p), S \bmod p)$ form an expander family (Lubotzky-Phillips-Sarnak, though the reference [A. Lubotzky, R. S. Phillips and P. C. Sarnak, Combinatorica 8 (1988), no. 3, 261–277; MR0963118] given here really treats other groups).
A note on this last implication: The natural thing would be to define a function $f(z)=\eta(d(z,A_i F_1))$, where $\eta$ is a smooth function, $d$ is the hyperbolic distance, $F_1$ is a fundamental domain for ${\rm SL}_2(\Bbb{Z})$, and $A_i$ is a hypothetical set of vertices with small boundary in the Cayley graph. (We want to show that $A_i$ does not exist, i.e., establish edge-expansion.) Here, what is used is essentially the characteristic function of a union of balls around points (this is fine, but does not show the underlying idea most clearly) and the smoothing is left essentially implicit. This is an example of a more general issue: phrases such as “after regularizing $\tilde{f}_n$ in a standard fashion to make it smooth rather than merely Lipschitz” will be clear to analysts (who barely need such an explanation), but other students will find them less helpful; there is also the issue that it could lead them to learn to hand-wave when they do not yet have the necessary acumen to do so safely. It is better to show them how simply a proof like this can be done in full.
The bound on the spectral gap given here is weaker than the one in [P. C. Sarnak and X. X. Xue, op. cit.] or [A. Gamburd, Israel J. Math. 127 (2002), 157–200;MR1900698]. The reason is that the author replaces the kernel used there by the heat kernel. Now, the original kernel is perfectly fine—it is just the convolution of the characteristic function of a (hyperbolic) disc with itself; this is the natural thing to do if one wants positivity on the spectral side. Exchanging this kernel for the heat kernel weakens and arguably also complicates matters slightly for everybody outside the class of readers who are deeply familiar with it.
Chapter 4 covers the Balog-Szemerédi-Gowers lemma and its consequences. This is really a lemma in graph theory, with a very useful implication on groups; as Tao himself showed, this implication (if framed appropriately) is valid for all groups, not just for abelian groups. We also see the result by J. Bourgain and A. Gamburd on how the lemma implies that a group in which sets grow rapidly under multiplication is a group in which measures become rapidly flatter under convolution by themselves. The version of the proof given in the book is particularly brief and elegant.
Chapter 5 is devoted precisely to the proof that, in $G={\rm SL}_n(K)$, $K$ a field, any set $A\subset G$ that generates $G$ grows rapidly: $|A A A|\geq |A|^{1+\delta}$, with $\delta>0$ a constant depending only on $n$, unless $A$ is already almost as large as $G$ itself. First, the sum-product theorem (Bourgain-Katz-Tao, first completed for small sets by Konyagin) is treated. This makes sense: even though it is not actually used in the treatment used here, it was used in the first proof of a result of this kind (due to the reviewer); moreover, some of the ideas in proofs of the sum-product theorem were abstracted from it (a task that started in [H. A. Helfgott, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 3, 761–851; MR2781932], as the author duly notes) and were crucial later. This is, in particular, the case for the “pivoting” argument.
Some special cases of the Larsen-Pink dimension-based estimates on intersections of finite subgroups of ${\rm SL}_2(K)$ with other subgroups of ${\rm SL}_2(K)$ are then proved. As the text again notes, what turned out to be analogues of these estimates were proved in [H. A. Helfgott, Ann. of Math. (2) 167 (2008), no. 2, 601–623; MR2415382] for intersections of generating sets $A$ of ${\rm SL}_2(K)$ with subgroups of ${\rm SL}_2(K)$; it is these analogues that are used in what follows. Section 5.3 contains what is called here a variant of the original argument to prove the growth result in [H. A. Helfgott, op. cit.; MR2415382] for ${\rm SL}_2$. It is indeed a very nice and easily generalizable variant, using the pivoting argument directly.
Sections 5.4 and 5.5 generalize the result to ${\rm SL}_n$, following [L. Pyber and E. Szabó, J. Amer. Math. Soc. 29 (2016), no. 1, 95–146; MR3402696] and [E. Breuillard, B. Green and T. C. Tao, Geom. Funct. Anal. 21 (2011), no. 4, 774–819; MR2827010]. To simply make clear the potential reach of each method, and not as any claim on “credit”: one can prove all the dimensional estimates here using the approach in [H. A. Helfgott, op. cit.; MR2781932], though it is best to systematize it further; as became clear only later, when the Lie algebra is simple, this can be done very cleanly, without algebraic manipulations that can look like ad hoc arguments.
Section 5.5 proves the dimensional estimates in the needed generality. Here the author chooses to use nonstandard analysis, through ultraproducts. This is unnecessary.
Section 6 sketches a proof of a non-concentration estimate needed by Bourgain and Gamburd’s proof [Ann. of Math. (2) 167 (2008), no. 2, 625–642; MR2415383] of expansion for ${\rm SL}_2(K)$ (which they later generalized to other groups). This proof is based on $|A A A|\leq |A|^{1+\delta}$ via flattening of measures, as said above. It is also proved that random generators give a Cayley graph with large girth; large girth is enough for Bourgain and Gamburd’s proof to apply.
Section 7 starts with a concise sketch of the Rosser-Iwaniec $\beta$-sieve (which, strangely, is uncredited here). After a discussion of strong approximation, the text gives a brief treatment of the work by Bourgain, Gamburd and Sarnak (“affine sieve”) [Invent. Math. 179 (2010), no. 3, 559–644; MR2587341], which uses the expansion property to sieve a set by the action of ${\rm SL}_2(\Bbb{Z})$, or other non-abelian groups. (In this framework, a classical sieve is seen to sieve by the action of $\Bbb{Z}$.) This is the end of the first part.
It may be regretted that permutation groups are barely touched upon. This is understandable: while there are many points in common in the study of growth over linear algebraic groups and over permutation groups, the study of the latter has arguably not yet reached quite the same stage of development as the former.
It would also have been desirable for the book to contain more material on random walks. There is only passing mention of mixing times—and short mixing times are one of the main applications of expansion. At the very least, one might have wished for a brief exposition on how diameters, mixing times and spectral gaps relate, in all directions of implication. Whoever uses the book for teaching or self-study would be well advised to supplement it with, say, [P. W. Diaconis and L. Saloff-Coste, Ann. Appl. Probab. 3 (1993), no. 3, 696–730; MR1233621], [L. Babai and M. Szegedy, Combin. Probab. Comput. 1 (1992), no. 1, 1–11; MR1167291], [L. Babai, in Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 822–831, ACM, New York, 2006; MR2368881] and some sections of [D. A. Levin, Y. Peres and E. L. Wilmer, Markov chains and mixing times, Amer. Math. Soc., Providence, RI, 2009; MR2466937].
We come to the second part of the book. The structure here is less tight; the chapters, except for the last two, are not really connected to each other.
Chapter 8 uses Cayley graphs (drawn in many colors) to illustrate group cohomology. This is interesting, but not germane to the topic. The chapter could have easily been omitted.
Chapter 9 proves the Lang-Weil bound on rational points on varieties. This is essentially a consequence of the Hasse-Weil bound on rational points on curves. (In contrast, Deligne’s bounds, which do not seem to be mentioned, are the “true”, and harder, analogue of Hasse-Weil for varieties.) The text gives the Stepanov-Bombieri proof of the Hasse-Weil bound for the special case of a field whose number of elements is a perfect square. The Hasse-Weil bound for arbitrary finite fields can be deduced from this, but the text does not give a proof; the reader is referred instead to another book by the author.
Chapter 10 discusses the spectral theorem. Both the beginning and the end feel a little rushed: there is neither a proof for bounded operators (it is simply mentioned that this is the easier case) nor a full proof for the Laplace-Beltrami operator, even over $\Bbb{H}$. It would have been possible to give a full proof along the lines of, say, [H. Iwaniec, Spectral methods of automorphic forms, second edition, Grad. Stud. Math., 53, Amer. Math. Soc., Providence, RI, 2002 (Chapters 4–5);MR1942691], framing it in terms of the general theory.
Chapters 11 and 12 are entitled “Notes on Lie algebras” and “Notes on Lie type”. The first of these chapters gives a self-contained proof of the classification of simple Lie algebras over $\Bbb{C}$. It is nice to have an exposition of this standard topic written with the author’s usual clarity, but it isn’t needed here. (Moreover, given what the book is about, would it not make sense to at least mention the case of positive characteristic?) Chapter 12 starts by showing that a complex Lie group is simple (in the sense of having only $0$-dimensional proper normal subgroups) if and only if its Lie algebra is simple. It is a pity that the positive-characteristic analogue (which admittedly has exceptions for small characteristic; this was overlooked in [H. A. Helfgott, Bull. Amer. Math. Soc. (N.S.) 52 (2015), no. 3, 357–413 (§5.2); MR3348442]) was not treated here. That analogue is precisely what is needed to give a treatment in full generality of the dimensional estimates from the point of view of Lie algebras. In particular, what Chapter 5 calls “skewness” ([H. A. Helfgott, op. cit.; MR2781932] called this “sticking in different directions”) becomes clear as day in this way.
Chapter 12 concludes with an exposition of Chevalley groups, $(B,N)$ pairs and the Bruhat decomposition. All of this serves to go from the classification of Lie algebras to a classification of Lie groups. The end (§12.3) feels closer to a discussion than to a full treatment, though the case of finite characteristic is taken into account.
{Reviewer remarks: Unfortunately, an excellent blog does not necessarily translate into a uniformly first-rate book, especially when the path from the former to the latter has clearly been very short. A blog has an element of journalism to it, and the standards of journalism and permanent literature are not the same. It is useful to have the present text in a permanent format, but one must ask oneself whether the hard cover is worth the loss (of hyperlinks, say) incurred in the change in format, particularly when little else is added in the process.
{At the same time, this is a very valuable resource, though, as we have seen, there are some particulars in which it could be improved. We can hope that both the book and this review will prove useful to whoever writes a definitive work on the subject.}
Reviewed by Harald A. Helfgott
thanks for the review of a review.
mjk: Thanks for the review of a review of a review!