Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “Approximate subgroups of linear groups“, submitted to GAFA. This paper contains (the first part) of the results announced previously by us; the second part of these results, concerning expander groups, will appear subsequently. The release of this paper has been coordinated with the release of a parallel paper by Pyber and Szabo (previously announced within an hour(!) of our own announcement).

Our main result describes (with polynomial accuracy) the “sufficiently Zariski dense” approximate subgroups of simple algebraic groups {{\bf G}(k)}, or more precisely absolutely almost simple algebraic groups over {k}, such as {SL_d(k)}. More precisely, define a {K}-approximate subgroup of a genuine group {G} to be a finite symmetric neighbourhood of the identity {A} (thus {1 \in A} and {A^{-1}=A}) such that the product set {A \cdot A} can be covered by {K} left-translates (and equivalently, {K} right-translates) of {A}.

Let {k} be a field, and let {\overline{k}} be its algebraic closure. For us, an absolutely almost simple algebraic group over {k} is a linear algebraic group {{\bf G}(k)} defined over {k} (i.e. an algebraic subvariety of {GL_n(k)} for some {n} with group operations given by regular maps) which is connected (i.e. irreducible), and such that the completion {{\bf G}(\overline{k})} has no proper normal subgroups of positive dimension (i.e. the only normal subgroups are either finite, or are all of {{\bf G}(\overline{k})}. To avoid degeneracies we also require {{\bf G}} to be non-abelian (i.e. not one-dimensional). These groups can be classified in terms of their associated finite-dimensional simple complex Lie algebra, which of course is determined by its Dynkin diagram, together with a choice of weight lattice (and there are only finitely many such choices once the Lie algebra is fixed). However, the exact classification of these groups is not directly used in our work.

Our first main theorem classifies the approximate subgroups {A} of such a group {{\bf G}(k)} in the model case when {A} generates the entire group {{\bf G}(k)}, and {k} is finite; they are either very small or very large.

Theorem 1 (Approximate groups that generate) Let {{\bf G}(k)} be an absolutely almost simple algebraic group over {k}. If {k} is finite and {A} is a {K}-approximate subgroup of {{\bf G}(k)} that generates {{\bf G}(k)}, then either {|A| \leq K^{O(1)}} or {|A| \geq K^{-O(1)} |{\bf G}(k)|}, where the implied constants depend only on {{\bf G}}.

The hypothesis that {A} generates {{\bf G}(k)} cannot be removed completely, since if {A} was a proper subgroup of {{\bf G}(k)} of size intermediate between that of the trivial group and of {{\bf G}(k)}, then the conclusion would fail (with {K=O(1)}). However, one can relax the hypothesis of generation to that of being sufficiently Zariski-dense in {{\bf G}(k)}. More precisely, we have

Theorem 2 (Zariski-dense approximate groups) Let {{\bf G}(k)} be an absolutely almost simple algebraic group over {k}. If {A} is a {K}-approximate group) is not contained in any proper algebraic subgroup of {k} of complexity at most {M} (where {M} is sufficiently large depending on {{\bf G}}), then either {|A| \leq K^{O(1)}} or {|A| \geq K^{-O(1)} |\langle A \rangle|}, where the implied constants depend only on {{\bf G}} and {\langle A \rangle} is the group generated by {A}.

Here, we say that an algebraic variety has complexity at most {M} if it can be cut out of an ambient affine or projective space of dimension at most {M} by using at most {M} polynomials, each of degree at most {M}. (Note that this is not an intrinsic notion of complexity, but will depend on how one embeds the algebraic variety into an ambient space; but we are assuming that our algebraic group {{\bf G}(k)} is a linear group and thus comes with such an embedding.)

In the case when {k = {\bf C}}, the second option of this theorem cannot occur since {{\bf G}({\bf C})} is infinite, leading to a satisfactory classification of the Zariski-dense approximate subgroups of almost simple connected algebraic groups over {{\bf C}}. On the other hand, every approximate subgroup of {GL_n({\bf C})} is Zariski-dense in some algebraic subgroup, which can be then split as an extension of a semisimple algebraic quotient group by a solvable algebraic group (the radical of the Zariski closure). Pursuing this idea (and glossing over some annoying technical issues relating to connectedness), together with the Freiman theory for solvable groups over {{\bf C}} due to Breuillard and Green, we obtain our third theorem:

Theorem 3 (Freiman’s theorem in {GL_n({\bf C})}) Let {A} be a {K}-approximate subgroup of {GL_n({\bf C})}. Then there exists a nilpotent {K}-approximate subgroup {B} of size at most {K^{O(1)}|A|}, such that {A} is covered by {K^{O(1)}} translates of {B}.

This can be compared with Gromov’s celebrated theorem that any finitely generated group of polynomial growth is virtually nilpotent. Indeed, the above theorem easily implies Gromov’s theorem in the case of finitely generated subgroups of {GL_n({\bf C})}.

By fairly standard arguments, the above classification theorems for approximate groups can be used to give bounds on the expansion and diameter of Cayley graphs, for instance one can establish a conjecture of Babai and Seress that connected Cayley graphs on absolutely almost simple groups over a finite field have polylogarithmic diameter at most. Applications to expanders include the result on Suzuki groups mentioned in a previous post; further applications will appear in a forthcoming paper.

Apart from the general structural theory of algebraic groups, and some quantitative analogues of the basic theory of algebraic geometry (which we chose to obtain via ultrafilters, as discussed in this post), we rely on two basic tools. Firstly, we use a version of the pivot argument developed first by Konyagin and Bourgain-Glibichuk-Konyagin in the setting of sum-product estimates, and generalised to more non-commutative settings by Helfgott; this is discussed in this previous post. Secondly, we adapt an argument of Larsen and Pink (which we learned from a paper of Hrushovski) to obtain a sharp bound on the extent to which a sufficiently Zariski-dense approximate groups can concentrate in a (bounded complexity) subvariety; this is discussed at the end of this blog post.