{"id":1257,"date":"2016-08-27T16:40:51","date_gmt":"2016-08-27T21:40:51","guid":{"rendered":"http:\/\/blogs.ams.org\/beyondreviews\/?p=1257"},"modified":"2016-08-27T16:57:08","modified_gmt":"2016-08-27T21:57:08","slug":"an-exceptional-review-about-expansion-in-groups","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/beyondreviews\/2016\/08\/27\/an-exceptional-review-about-expansion-in-groups\/","title":{"rendered":"An exceptional review about expansion in groups"},"content":{"rendered":"<p>Today I\u2019m making two blog posts about exceptional reviews: one review of a book and one of a paper. This post is about <a href=\"http:\/\/www.ams.org\/mathscinet\/MRAuthorID\/644718\">Harald Helfgott<\/a>&#8216;s review of <a href=\"http:\/\/www.ams.org\/mathscinet\/MRAuthorID\/361755\">Terry Tao<\/a>&#8216;s book,\u00a0<em>Expansion in finite simple groups of Lie type<\/em>, <a href=\"http:\/\/bookstore.ams.org\/gsm-164\/\">published by the AMS<\/a>. The <a href=\"http:\/\/blogs.ams.org\/beyondreviews\/2016\/08\/27\/an-exceptional-review-about-inner-model-theory\/\">other post<\/a> is about <a href=\"http:\/\/www.ams.org\/mathscinet\/MRAuthorID\/677243\">Grigor Sargsyan<\/a>&#8216;s\u00a0exceptional review of a paper: \u00a0<a href=\"http:\/\/www.ams.org\/mathscinet\/MRAuthorID\/166600\">John Steel<\/a>&#8216;s chapter, An outline of inner model theory, in the <em>Handbook of Set Theory<\/em> edited by <a href=\"http:\/\/www.ams.org\/mathscinet\/MRAuthorID\/194940\">Matthew Foreman<\/a> and <a href=\"http:\/\/www.ams.org\/mathscinet\/MRAuthorID\/97670\">Akihiro Kanamori<\/a> [<a href=\"http:\/\/www.ams.org\/mathscinet-getitem?mr=2768678\">MR2768678<\/a>].<!--more--><\/p>\n<p>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. \u00a0Helfgott&#8217;s review has several exceptional characteristics. \u00a0To begin with, it is thorough &#8211; as you might guess at a glance at the length. \u00a0But it is not just that he says a lot, his discussion is quite thoughtful. \u00a0As I see in many excellent reviews, Helfgott establishes the context of the work early on in the review. \u00a0He begins, though, by giving a three-sentence\u00a0<em>pr\u00e9cis<\/em> of the book, followed by a quick three-sentence assessment of the book. \u00a0So before you get going, you have a rough\u00a0idea of what you will be reading. \u00a0The main body of the review is a mix of telling us what is in the book &#8211; the main topics as well as the major theorems &#8211; and the reviewer&#8217;s comments on them. \u00a0 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. \u00a0As we continue reading the review, we see several more times where Helfgott wonders about Tao&#8217;s choices. \u00a0There 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. \u00a0Helfgott also points out how Tao&#8217;s great breadth introduces some shorthands that we mere mortals may need a bit more explanation. \u00a0One example is in Chapter 3 where Tao quickly skips ahead writing &#8220;after regularizing $f_n$ in a standard fashion to make it smooth rather than merely Lipschitz&#8221;. \u00a0An analyst (which is one of Tao&#8217;s m\u00e9tiers) will be fine with this, but lots of people interested in expanders in finite groups are not analysts. \u00a0My experience with Tao&#8217;s writing is that he is extremely good at conveying how he thinks about particular problems or entire subjects. \u00a0This can be great when you are able to keep up. \u00a0If not, you need to do some extra work &#8211; though it is invariably worth the effort. \u00a0 Helfgott concludes his review with two general comments: \u00a0an excellent blog does not automatically translate into an excellent book, but, at the same time, this\u00a0book is a very valuable\u00a0resource.<\/p>\n<hr \/>\n<p><a href=\"http:\/\/www.ams.org\/mathscinet-getitem?mr=3309986\">MR3309986<\/a><br \/>\n<a href=\"http:\/\/www.ams.org\/mathscinet\/MRAuthorID\/361755\">Tao, Terence<\/a><br \/>\nExpansion in finite simple groups of Lie type.<br \/>\nGraduate Studies in Mathematics, 164. American Mathematical Society, Providence, RI, 2015. xiv+303 pp. ISBN: 978-1-4704-2196-0<br \/>\n<a href=\"http:\/\/www.ams.org\/mathscinet\/search\/mscdoc.html?code=20D06,(05C25,05C81,11B30,17B20,20F65,20G30,22D10)\">20D06 (05C25 05C81 11B30 17B20 20F65 20G30 22D10)<\/a><\/p>\n<p class=\"review\">This is a book based on the author&#8217;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.<\/p>\n<p class=\"review\">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.<\/p>\n<p class=\"review\">In part because the book&#8217;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\u00a0<span class=\"it\">expansion<\/span>, the book&#8217;s main subject. Let <span class=\"MathTeX\">$\\Gamma$<\/span> be a regular graph, i.e., one in which every vertex has the same degree (&#8220;valence&#8221;) <span class=\"MathTeX\">$d$<\/span>. A regular graph is an\u00a0<span class=\"MathTeX\">$\\epsilon$<\/span>-expander if it has spectral gap of size <span class=\"MathTeX\">$\\geq \\epsilon$<\/span>, i.e., if the second largest value of the adjacency matrix is <span class=\"MathTeX\">$\\leq (1 &#8211; \\epsilon) d$<\/span>, or, what is the same, if the second smallest value of the discrete Laplacian is <span class=\"MathTeX\">$\\geq \\epsilon$<\/span>. There are two slightly different definitions of combinatorial expansion, namely, vertex and edge expansion. A regular graph is an <span class=\"MathTeX\">$\\epsilon$<\/span>-edge expander if, for every subset <span class=\"MathTeX\">$S$<\/span> of the set of vertices <span class=\"MathTeX\">$V$<\/span> with <span class=\"MathTeX\">$|S|\\leq |V|\/2$<\/span>, there are <span class=\"MathTeX\">$\\geq \\epsilon d |S|$<\/span>edges with their tails in <span class=\"MathTeX\">$S$<\/span> and their heads outside it.<\/p>\n<p class=\"review\">A family of graphs is an <span class=\"it\">expander family<\/span> if there is an <span class=\"MathTeX\">$\\epsilon&gt;0$<\/span> for which they are all <span class=\"MathTeX\">$\\epsilon$<\/span>-expanders. This is of particular interest if the degree of the graphs in the family is constant.<\/p>\n<p class=\"review\">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 <span class=\"MathTeX\">$\\epsilon&gt;0$<\/span> and every <span class=\"MathTeX\">$d\\geq 1$<\/span> there is a <span class=\"MathTeX\">$\\delta&gt;0$<\/span> such that if a graph of degree <span class=\"MathTeX\">$d$<\/span> is an <span class=\"MathTeX\">$\\epsilon$<\/span>-edge expander, then it is a <span class=\"MathTeX\">$\\delta$<\/span>-expander. (The other direction, viz., that an <span class=\"MathTeX\">$\\epsilon$<\/span>-expander is an <span class=\"MathTeX\">$\\epsilon\/2$<\/span>-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 <span class=\"MathTeX\">$\\ell_2$<\/span> mixing in logarithmic time. Finally, it is shown that, for <span class=\"MathTeX\">$d$<\/span> large, there is an<span class=\"MathTeX\">$\\epsilon&gt;0$<\/span> such that random graphs of degree <span class=\"MathTeX\">$d$<\/span> with <span class=\"MathTeX\">$n$<\/span> vertices are <span class=\"MathTeX\">$\\epsilon$<\/span>-expanders with probability tending to <span class=\"MathTeX\">$1$<\/span> as <span class=\"MathTeX\">$n\\to \\infty$<\/span>, where a &#8220;random graph&#8221; is taken with respect to a slightly nonuniform distribution.<\/p>\n<p class=\"review\">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 <span class=\"MathTeX\">$\\epsilon$<\/span>-edge expander has a spectral gap <span class=\"MathTeX\">$\\delta \\gg \\epsilon^2$<\/span>), one just needs to treat an arbitrary function <span class=\"MathTeX\">$\\phi\\:V\\to \\Bbb{R}$<\/span> by first subtracting its median, and then applying what is essentially edge-expansion plus summation by parts (p. 12) to the part of <span class=\"MathTeX\">$\\phi$<\/span> above the median and the part below the median (as one can, given that each part has support of size <span class=\"MathTeX\">$\\leq |V|\/2$<\/span>, by the definition of &#8220;median&#8221;). This is shorter and arguably more natural than the proof in the book.<\/p>\n<p class=\"review\">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&#8217;s graphs to have a few doubled edges or self-loops; one can then fix these without breaking the edge-expansion property.<\/p>\n<p class=\"review\">Chapter 2 starts with the definitions of Cayley and Schreier graphs. It proceeds quite quickly, first defining Kazhdan&#8217;s property <span class=\"MathTeX\">$(\\rm T)$<\/span> and using induced representations to show that, given a locally compact group <span class=\"MathTeX\">$G$<\/span> and a locally compact subgroup <span class=\"MathTeX\">$H$<\/span> of finite covolume, <span class=\"MathTeX\">$G$<\/span> has property <span class=\"MathTeX\">$(\\rm T)$<\/span> if and only if\u00a0<span class=\"MathTeX\">$H$<\/span> has. The idea of the ping-pong lemma is used to establish that if a probability measure on <span class=\"MathTeX\">$\\Bbb{R}^2$<\/span> is almost-invariant under the action of a compact neighborhood in <span class=\"MathTeX\">${\\rm SL}_2(\\Bbb{R})$<\/span>, then it is almost entirely concentrated at the origin; this gives us that the pair <span class=\"MathTeX\">$({\\rm SL}_2(\\Bbb{R}) \\ltimes \\Bbb{R}^2, \\Bbb{R}^2)$<\/span> has relative property <span class=\"MathTeX\">$(\\rm T)$<\/span>, and a construction based on the Mautner phenomenon (via Moore) is then used to show that this implies that <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{R})$<\/span> has property <span class=\"MathTeX\">$(\\rm T)$<\/span> (Kazhdan). Since <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{Z})$<\/span> is of finite covolume in <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{R})$<\/span>, we conclude that <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{Z})$<\/span> has property <span class=\"MathTeX\">$(\\rm T)$<\/span>, and so, given any set of generators <span class=\"MathTeX\">$S$<\/span> of <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{Z})$<\/span> and any sequence of finite-index normal subgroups\u00a0<span class=\"MathTeX\">$N_n \\triangleleft {\\rm SL}_3(\\Bbb{Z})$<\/span>, the Cayley graphs <span class=\"MathTeX\">$\\{\\Gamma({\\rm SL}_3(\\Bbb{Z})\/N_n,S \\bmod N_n)\\}_n$<\/span> of <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{Z})\/N_n$<\/span> with respect to <span class=\"MathTeX\">$S \\bmod N_n$<\/span> form an expander family [G. A. Margulis, Problemy Pereda\u010di Informacii <span class=\"bf\">9<\/span> (1973), no. 4, 71\u201380; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=484767&amp;loc=fromrevtext\">MR0484767<\/a>]. 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.<\/p>\n<p class=\"review\">The chapter ends with a brief sketch of a proof (following [O. Gabber and Z. Galil, J. Comput. System Sci. <span class=\"bf\">22<\/span> (1981), no. 3, 407\u2013420; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=633542&amp;loc=fromrevtext\">MR0633542<\/a>] and [S. Jimbo and A. Maruoka, Combinatorica <span class=\"bf\">7<\/span> (1987), no. 4, 343\u2013355; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=931192&amp;loc=fromrevtext\">MR0931192<\/a>], <span class=\"it\">and<\/span>\u00a0[S. Hoory, N. Linial and A. Wigderson, Bull. Amer. Math. Soc. (N.S.) <span class=\"bf\">43<\/span> (2006), no. 4, 439\u2013561; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2247919&amp;loc=fromrevtext\">MR2247919<\/a>]) that Schreier graphs associated with <span class=\"MathTeX\">${\\rm SL}_2(\\Bbb{Z}\/n\\Bbb{Z}) \\ltimes (\\Bbb{Z}\/ n\\Bbb{Z})^2$<\/span> form an expander family. This proof skips property <span class=\"MathTeX\">$(\\rm T)$<\/span> 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 <span class=\"MathTeX\">$\\Bbb{Z}$<\/span>) combined with a little Fourier analysis over <span class=\"MathTeX\">$(\\Bbb{Z}\/n\\Bbb{Z})^2$<\/span>. Pedagogically, it might have made more sense to start with this and then introduce property <span class=\"MathTeX\">$(\\rm T)$<\/span> (or just property (<span class=\"MathTeX\">$\\tau$<\/span>)) to build matters up to <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{Z})$<\/span>. This can be done quite naturally; one then ends with a proof of property <span class=\"MathTeX\">$(\\rm T)$<\/span> for <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{Z})$<\/span> that does not go through <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{R})$<\/span> ([M. Burger, J. Reine Angew. Math. <span class=\"bf\">413<\/span>(1991), 36\u201367; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=1089795&amp;loc=fromrevtext\">MR1089795<\/a>; Y. Shalom, Inst. Hautes \u00c9tudes Sci. Publ. Math. No. 90 (1999), 145\u2013168 (2001); <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=1813225&amp;loc=fromrevtext\">MR1813225<\/a>]; see also the expositions in [M. E. B. Bekka, P. de la Harpe and A. Valette, <span class=\"it\">Kazhdan&#8217;s property (T)<\/span>, New Math. Monogr., 11, Cambridge Univ. Press, Cambridge, 2008 (\u00a74.2); <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2415834&amp;loc=fromrevtext\">MR2415834<\/a>] or [E. Kowalski, <span class=\"it\">The large sieve and its applications<\/span>, Cambridge Tracts in Math., 175, Cambridge Univ. Press, Cambridge, 2008 (\u00a7D.4); <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2426239&amp;loc=fromrevtext\">MR2426239<\/a>]). Of course, property<span class=\"MathTeX\">$(\\rm T)$<\/span> for <span class=\"MathTeX\">${\\rm SL}_3(\\Bbb{R})$<\/span> is of interest in itself.<\/p>\n<p class=\"review\">Chapter 3 introduces &#8220;quasi-random groups&#8221;, meaning groups <span class=\"MathTeX\">$G$<\/span> that have no non-trivial complex representations of small dimension. (This is, for instance, the case for <span class=\"MathTeX\">$G = {\\rm SL}_2(\\Bbb{F}_p)$<\/span>, which has no non-trivial complex representations of dimension <span class=\"MathTeX\">$&lt;(p-1)\/2$<\/span> (Frobenius).) In a quasi-random group, the eigenspace of the Laplacian corresponding to a non-trivial eigenvalue cannot have small dimension, since <span class=\"MathTeX\">$G$<\/span> acts non-trivially on it. This fact is used in two ways. First, it implies that large subsets of <span class=\"MathTeX\">$G$<\/span> mix very quickly under multiplication (\u00a73.1; see [W. T. Gowers, Combin. Probab. Comput. <span class=\"bf\">17<\/span> (2008), no. 3, 363\u2013387;<a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2410393&amp;loc=fromrevtext\">MR2410393<\/a>; L. Babai, N. V. Nikolov and L. Pyber, in <span class=\"it\">Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms<\/span>, 248\u2013257, ACM, New York, 2008; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2485310&amp;loc=fromrevtext\">MR2485310<\/a>]). Second, it can be used, as in [P. C. Sarnak and X. X. Xue, Duke Math. J. <span class=\"bf\">64<\/span> (1991), no. 1, 207\u2013227; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=1131400&amp;loc=fromrevtext\">MR1131400<\/a>], to prove a version of A. Selberg&#8217;s spectral gap [in <span class=\"it\">Proc. Sympos. Pure Math., Vol. VIII<\/span>, 1\u201315, Amer. Math. Soc., Providence, RI, 1965; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=182610&amp;loc=fromrevtext\">MR0182610<\/a>] (i.e., the fact that the second smallest eigenvalue of the Laplacian on the surface <span class=\"MathTeX\">$\\Gamma(N)\/\\Bbb{H}$<\/span> is bounded below by a constant). This spectral gap is then used to show (\u00a73.2) that, for any set of generators <span class=\"MathTeX\">$S$<\/span> of <span class=\"MathTeX\">${\\rm SL}_2(\\Bbb{Z})$<\/span>, the Cayley graphs <span class=\"MathTeX\">$\\Gamma({\\rm SL}_2(\\Bbb{F}_p), S \\bmod p)$<\/span> form an expander family (Lubotzky-Phillips-Sarnak, though the reference [A. Lubotzky, R. S. Phillips and P. C. Sarnak, Combinatorica <span class=\"bf\">8<\/span> (1988), no. 3, 261\u2013277; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=963118&amp;loc=fromrevtext\">MR0963118<\/a>] given here really treats other groups).<\/p>\n<p class=\"review\">A note on this last implication: The natural thing would be to define a function <span class=\"MathTeX\">$f(z)=\\eta(d(z,A_i F_1))$<\/span>, where <span class=\"MathTeX\">$\\eta$<\/span> is a smooth function, <span class=\"MathTeX\">$d$<\/span> is the hyperbolic distance, <span class=\"MathTeX\">$F_1$<\/span> is a fundamental domain for <span class=\"MathTeX\">${\\rm SL}_2(\\Bbb{Z})$<\/span>, and <span class=\"MathTeX\">$A_i$<\/span> is a hypothetical set of vertices with small boundary in the Cayley graph. (We want to show that <span class=\"MathTeX\">$A_i$<\/span> 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 &#8220;after regularizing <span class=\"MathTeX\">$\\tilde{f}_n$<\/span> in a standard fashion to make it smooth rather than merely Lipschitz&#8221; 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.<\/p>\n<p class=\"review\">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. <span class=\"bf\">127<\/span> (2002), 157\u2013200;<a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=1900698&amp;loc=fromrevtext\">MR1900698<\/a>]. The reason is that the author replaces the kernel used there by the heat kernel. Now, the original kernel is perfectly fine\u2014it 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.<\/p>\n<p class=\"review\">Chapter 4 covers the Balog-Szemer\u00e9di-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.<\/p>\n<p class=\"review\">Chapter 5 is devoted precisely to the proof that, in <span class=\"MathTeX\">$G={\\rm SL}_n(K)$<\/span>, <span class=\"MathTeX\">$K$<\/span> a field, any set <span class=\"MathTeX\">$A\\subset G$<\/span> that generates <span class=\"MathTeX\">$G$<\/span> grows rapidly: <span class=\"MathTeX\">$|A A A|\\geq |A|^{1+\\delta}$<\/span>, with <span class=\"MathTeX\">$\\delta&gt;0$<\/span> a constant depending only on <span class=\"MathTeX\">$n$<\/span>, unless <span class=\"MathTeX\">$A$<\/span> is already almost as large as <span class=\"MathTeX\">$G$<\/span> 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) <span class=\"bf\">13<\/span> (2011), no. 3, 761\u2013851; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2781932&amp;loc=fromrevtext\">MR2781932<\/a>], as the author duly notes) and were crucial later. This is, in particular, the case for the &#8220;pivoting&#8221; argument.<\/p>\n<p class=\"review\">Some special cases of the Larsen-Pink dimension-based estimates on intersections of finite subgroups of <span class=\"MathTeX\">${\\rm SL}_2(K)$<\/span> with other subgroups of <span class=\"MathTeX\">${\\rm SL}_2(K)$<\/span> 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) <span class=\"bf\">167<\/span> (2008), no. 2, 601\u2013623; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2415382&amp;loc=fromrevtext\">MR2415382<\/a>] for intersections of generating sets <span class=\"MathTeX\">$A$<\/span> of <span class=\"MathTeX\">${\\rm SL}_2(K)$<\/span> with subgroups of <span class=\"MathTeX\">${\\rm SL}_2(K)$<\/span>; 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.; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2415382&amp;loc=fromrevtext\">MR2415382<\/a>] for <span class=\"MathTeX\">${\\rm SL}_2$<\/span>. It is indeed a very nice and easily generalizable variant, using the pivoting argument directly.<\/p>\n<p class=\"review\">Sections 5.4 and 5.5 generalize the result to <span class=\"MathTeX\">${\\rm SL}_n$<\/span>, following [L. Pyber and E. Szab\u00f3, J. Amer. Math. Soc. <span class=\"bf\">29<\/span> (2016), no. 1, 95\u2013146; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=3402696&amp;loc=fromrevtext\">MR3402696<\/a>] and [E. Breuillard, B. Green and T. C. Tao, Geom. Funct. Anal. <span class=\"bf\">21<\/span> (2011), no. 4, 774\u2013819; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2827010&amp;loc=fromrevtext\">MR2827010<\/a>]. To simply make clear the potential reach of each method, and not as any claim on &#8220;credit&#8221;: one can prove all the dimensional estimates here using the approach in [H. A. Helfgott, op. cit.; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2781932&amp;loc=fromrevtext\">MR2781932<\/a>], 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.<\/p>\n<p class=\"review\">Section 5.5 proves the dimensional estimates in the needed generality. Here the author chooses to use nonstandard analysis, through ultraproducts. This is unnecessary.<\/p>\n<p class=\"review\">Section 6 sketches a proof of a non-concentration estimate needed by Bourgain and Gamburd&#8217;s proof [Ann. of Math. (2) <span class=\"bf\">167<\/span> (2008), no. 2, 625\u2013642; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2415383&amp;loc=fromrevtext\">MR2415383<\/a>] of expansion for <span class=\"MathTeX\">${\\rm SL}_2(K)$<\/span> (which they later generalized to other groups). This proof is based on <span class=\"MathTeX\">$|A A A|\\leq |A|^{1+\\delta}$<\/span> 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&#8217;s proof to apply.<\/p>\n<p class=\"review\">Section 7 starts with a concise sketch of the Rosser-Iwaniec <span class=\"MathTeX\">$\\beta$<\/span>-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 (&#8220;affine sieve&#8221;) [Invent. Math. <span class=\"bf\">179<\/span> (2010), no. 3, 559\u2013644; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2587341&amp;loc=fromrevtext\">MR2587341<\/a>], which uses the expansion property to sieve a set by the action of <span class=\"MathTeX\">${\\rm SL}_2(\\Bbb{Z})$<\/span>, or other non-abelian groups. (In this framework, a classical sieve is seen to sieve by the action of <span class=\"MathTeX\">$\\Bbb{Z}$<\/span>.) This is the end of the first part.<\/p>\n<p class=\"review\">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.<\/p>\n<p class=\"review\">It would also have been desirable for the book to contain more material on random walks. There is only passing mention of mixing times\u2014and 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. <span class=\"bf\">3<\/span> (1993), no. 3, 696\u2013730; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=1233621&amp;loc=fromrevtext\">MR1233621<\/a>], [L. Babai and M. Szegedy, Combin. Probab. Comput. <span class=\"bf\">1<\/span> (1992), no. 1, 1\u201311; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=1167291&amp;loc=fromrevtext\">MR1167291<\/a>], [L. Babai, in <span class=\"it\">Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms<\/span>, 822\u2013831, ACM, New York, 2006; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2368881&amp;loc=fromrevtext\">MR2368881<\/a>] and some sections of [D. A. Levin, Y. Peres and E. L. Wilmer, <span class=\"it\">Markov chains and mixing times<\/span>, Amer. Math. Soc., Providence, RI, 2009; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2466937&amp;loc=fromrevtext\">MR2466937<\/a>].<\/p>\n<p class=\"review\">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.<\/p>\n<p class=\"review\">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.<\/p>\n<p class=\"review\">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&#8217;s bounds, which do not seem to be mentioned, are the &#8220;true&#8221;, 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.<\/p>\n<p class=\"review\">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 <span class=\"MathTeX\">$\\Bbb{H}$<\/span>. It would have been possible to give a full proof along the lines of, say, [H. Iwaniec, <span class=\"it\">Spectral methods of automorphic forms<\/span>, second edition, Grad. Stud. Math., 53, Amer. Math. Soc., Providence, RI, 2002 (Chapters 4\u20135);<a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=1942691&amp;loc=fromrevtext\">MR1942691<\/a>], framing it in terms of the general theory.<\/p>\n<p class=\"review\">Chapters 11 and 12 are entitled &#8220;Notes on Lie algebras&#8221; and &#8220;Notes on Lie type&#8221;. The first of these chapters gives a self-contained proof of the classification of simple Lie algebras over <span class=\"MathTeX\">$\\Bbb{C}$<\/span>. It is nice to have an exposition of this standard topic written with the author&#8217;s usual clarity, but it isn&#8217;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 <span class=\"MathTeX\">$0$<\/span>-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.) <span class=\"bf\">52<\/span> (2015), no. 3, 357\u2013413 (\u00a75.2); <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=3348442&amp;loc=fromrevtext\">MR3348442<\/a>]) 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 &#8220;skewness&#8221; ([H. A. Helfgott, op. cit.; <a href=\"http:\/\/www.ams.org\/mathscinet\/search\/publdoc.html?r=1&amp;pg1=MR&amp;s1=2781932&amp;loc=fromrevtext\">MR2781932<\/a>] called this &#8220;sticking in different directions&#8221;) becomes clear as day in this way.<\/p>\n<p class=\"review\">Chapter 12 concludes with an exposition of Chevalley groups, <span class=\"MathTeX\">$(B,N)$<\/span> 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 (\u00a712.3) feels closer to a discussion than to a full treatment, though the case of finite characteristic is taken into account.<\/p>\n<p class=\"review\">{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.<\/p>\n<p class=\"review\">{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.}<\/p>\n<p><span class=\"ReviewedBy\">Reviewed by <a href=\"http:\/\/www.ams.org\/mathscinet\/MRAuthorID\/644718\">Harald A. Helfgott<\/a><\/span><\/p>\n<div style=\"margin-top: 0px; margin-bottom: 0px;\" class=\"sharethis-inline-share-buttons\" ><\/div>","protected":false},"excerpt":{"rendered":"<p>Today I\u2019m making two blog posts about exceptional reviews: one review of a book and one of a paper. This post is about Harald Helfgott&#8216;s review of Terry Tao&#8216;s book,\u00a0Expansion in finite simple groups of Lie type, published by the &hellip; <a href=\"https:\/\/blogs.ams.org\/beyondreviews\/2016\/08\/27\/an-exceptional-review-about-expansion-in-groups\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n<div style=\"margin-top: 0px; margin-bottom: 0px;\" class=\"sharethis-inline-share-buttons\" data-url=https:\/\/blogs.ams.org\/beyondreviews\/2016\/08\/27\/an-exceptional-review-about-expansion-in-groups\/><\/div>\n","protected":false},"author":86,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2],"tags":[],"class_list":["post-1257","post","type-post","status-publish","format-standard","hentry","category-exceptional-reviews"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p6C2KK-kh","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/1257","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/users\/86"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/comments?post=1257"}],"version-history":[{"count":17,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/1257\/revisions"}],"predecessor-version":[{"id":1279,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/1257\/revisions\/1279"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/media?parent=1257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/categories?post=1257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/tags?post=1257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}