Background literature on growth and expanders

The material in here is fairly comprehensive. Comments in red describe the sources that I suggest you start with. Back to main seminars page.

Background on expanders:

On the sum-product phenomenon. The basic text is Tao and Vu “Additive Combinatorics”. Here are a few other links:

  • Green, Sum-product over F_p. This is a survey article.
  • Green, Sum-product over the complexes. This focusses on Solymosi’s result.
  • Bourgain, Katz, Tao, Sum-product over F_p. This is the first proof of sum-product over F_p. However it is difficult so I wouldn’t recommend it as a first read. Plus it is not completely general (it doesn’t work for very small sets). On the plus side it very clearly demonstrates the connection between sum-product phenomena and Szemeredi-Trotter theorems. So it’s worth looking at for this reason.
  • Helfgott, Growth in SL_3. Section 3 of this paper is devoted to a generalization of the idea of the sum-product theorem. It is based on the Glibichuk-Konyagin sum-product theorem over F_p (which works for small sets so improves the work of BKT mentioned above), but is couched in much more general terms; the statement involves one group acting upon another. This is the key statement of the sum-product phenomenon for our purposes; the exposition is excellent.
  • Tao and Vu, Additive Combinatorics. To get a taste of how incidence theorems are related to the sum-product phenomenon read Sections 8.1-8.3.

On growth in non-abelian groups:

  • Helfgott, Growth in SL_3. This paper is central. It includes a discussion of key ideas including escape, non-singularity, sticking subgroups in different directions, bounds on torus intersection, bounds on conjugacy classes, use of incidence theorems etc. The statement of Theorem 1.1 is “ideal” (as this is currently understood); it reduces questions of growth to the nilpotent setting.

    Sections 4 and 5 of this paper are particularly vital. Subsequent sections of the paper use incidence theorems; we will be able to go to the full result more directly.

  • Breuillard, Green, Tao, Growth in Chevalley groups. This is an announcement of the general result which focusses on the pivot argument. A full proof of this result does not yet exist in the literature. So for now the best exposition of the result is this blog entry of Tao (see also the subsequent discussion, especially the simplifications described by Helfgott).
  • Pyber, Szabo, Growth in groups of Lie type. The methods in this paper are similar to those of the previous link. However the statement is more general (it holds for twisted groups). In addition examples are given that justify the dependency of the constant epsilon on the rank.
  • Larsen, Pink, Subgroups of algebraic groups. This paper contains material that was central to adapting Helfgott’s work to the general setting (a la the previous two points).

Expanders from groups:

  • Bourgain, Gamburd, Expanders in SL_2(p). This uses Helfgott’s result on growth in SL_2(p) to generate expanders. These two clever people have a couple of other papers that are also of interest:
    • J. Bourgain and A. Gamburd, Expansion and random walks in
      SLd (Z/pn Z):I, J. Eur. Math. Soc. 10 (2008), 987-1011.

    • J. Bourgain and A. Gamburd,
      SLd (Z/pn Z):II, preprint
  • Varju, Expansion in SL_d This generalizes some of the work of Bourgain and Gamburd.
  • Kassabov, Nikolov, Lubotzky, Finite simple groups as expanders. An entirely different set of techniques.
  • Kassabov, Symmetric groups as expanders. Another entirely different set of techniques.

Sieving:

Property T: The first construction of expander graphs was by Margulis and used property T, a representation theoretic property that holds for certain discrete groups (SL_d(Z) with d>2 for instance).

  • Wikipedia gives a definition of Property T.
  • A. Lubotzky. Discrete groups, expanding graphs and invariant measures, volume 125 of Progress in Mathematics. This book outlines (amongst other things) the connection between Property T and expansion properties.

One thought on “Background literature on growth and expanders

  1. Pingback: Expanders and growth in groups | Nick Gill

Comments are closed.