Expansion in finite simple groups of Lie type

Emmanuel Breuillard, Ben Green, Bob Guralnick, and I have just uploaded to the arXiv our joint paper “Expansion in finite simple groups of Lie type“. This long-delayed paper (announced way back in 2010!) is a followup to our previous paper in which we showed that, with one possible exception, generic pairs of elements of a simple algebraic group (over an uncountable field) generated a free group which was strongly dense in the sense that any nonabelian subgroup of this group was Zariski dense. The main result of this paper is to establish the analogous result for finite simple groups of Lie type (as defined in the previous blog post) and bounded rank, namely that almost all pairs of elements of such a group generate a Cayley graph which is a (two-sided) expander, with expansion constant bounded below by a quantity depending on the rank of the group. (Informally, this means that the random walk generated by spreads out in logarithmic time to be essentially uniformly distributed across the group, as opposed for instance to being largely trapped in an algebraic subgroup. Thus if generic elements did not generate a strongly dense group, one would probably expect expansion to fail.)

There are also some related results established in the paper. Firstly, as we discovered after writing our first paper, there was one class of algebraic groups for which our demonstration of strongly dense subgroups broke down, namely the groups in characteristic three. In the current paper we provide in a pair of appendices a new argument that covers this case (or more generally, in odd characteristic), by first reducing to the case of affine groups (which can be found inside as a subgroup) and then using a ping-pong argument (in a p-adic metric) in the latter context.

Secondly, we show that the distinction between one-sided expansion and two-sided expansion (see this set of lecture notes of mine for definitions) is erased in the context of Cayley graphs of bounded degree, in the sense that such graphs are one-sided expanders if and only if they are two-sided expanders (perhaps with slightly different expansion constants). The argument turns out to be an elementary combinatorial one, based on the “pivot” argument discussed in these lecture notes of mine.

Now to the main result of the paper, namely the expansion of random Cayley graphs. This result had previously been established for by Bourgain and Gamburd, and Ben, Emmanuel and I had used the Bourgain-Gamburd method to achieve the same result for Suzuki groups. For the other finite simple groups of Lie type, expander graphs had been constructed by Kassabov, Lubotzky, and Nikolov, but they required more than two generators, which were placed deterministically rather than randomly. (Here, I am skipping over a large number of other results on expanding Cayley graphs; see this survey of Lubotzsky for a fairly recent summary of developments.) The current paper also uses the “Bourgain-Gamburd machine”, as discussed in these lecture notes of mine, to demonstrate expansion. This machine shows how expansion of a Cayley graph follows from three basic ingredients, which we state informally as follows:

• Non-concentration (A random walk in this graph does not concentrate in a proper subgroup);
• Product theorem (A medium-sized subset of this group which is not trapped in a proper subgroup will expand under multiplication); and
• Quasirandomness (The group has no small non-trivial linear representations).

Quasirandomness of arbitrary finite simple groups of Lie type was established many years ago (predating, in fact, the introduction of the term “quasirandomness” by Gowers for this property) by Landazuri-Seitz and Seitz-Zalesskii, and the product theorem was already established by Pyber-Szabo and independently by Breuillard, Green, and myself. So the main problem is to establish non-concentration: that for a random Cayley graph on a finite simple group of Lie type, random walks did not concentrate in proper subgroups.

The first step was to classify the proper subgroups of . Fortunately, these are all known; in particular, such groups are either contained in proper algebraic subgroups of the algebraic group containing (or a bounded cover thereof) with bounded complexity, or are else arising (up to conjugacy) from a version of the same group associated to a proper subfield of the field respectively; this follows for instance from the work of Larsen and Pink, but also can be deduced using the classification of finite simple groups, together with some work of Aschbacher, Liebeck-Seitz, and Nori. We refer to the two types of subgroups here as “structural subgroups” and “subfield subgroups”.

To preclude concentration in a structural subgroup, we use our previous result that generic elements of an algebraic group generate a strongly dense subgroup, and so do not concentrate in any algebraic subgroup. To translate this result from the algebraic group setting to the finite group setting, we need a Schwarz-Zippel lemma for finite simple groups of Lie type. This is straightforward for Chevalley groups, but turns out to be a bit trickier for the Steinberg and Suzuki-Ree groups, and we have to go back to the Chevalley-type parameterisation of such groups in terms of (twisted) one-parameter subgroups, that can be found for instance in the text of Carter; this “twisted Schwartz-Zippel lemma” may possibly have further application to analysis on twisted simple groups of Lie type. Unfortunately, the Schwartz-Zippel estimate becomes weaker in twisted settings, and particularly in the case of triality groups , which require a somewhat ad hoc additional treatment that relies on passing to a simpler subgroup present in a triality group, namely a central product of two different ‘s.

To rule out concentration in a conjugate of a subfield group, we repeat an argument we introduced in our Suzuki paper and pass to a matrix model and analyse the coefficients of the characteristic polynomial of words in this Cayley graph, to prevent them from concentrating in a subfield. (Note that these coefficients are conjugation-invariant.)

A nilpotent Freiman dimension lemma

Emmanuel Breuillard, Ben Green and I have just uploaded to the arXiv the short paper “A nilpotent Freiman dimension lemma“, submitted to the special volume of the European Journal of Combinatorics in honour of Yahya Ould Hamidoune.  This paper is a nonabelian (or more precisely, nilpotent) variant of the following additive combinatorics lemma of Freiman:

Freiman’s lemma.  Let A be a finite subset of a Euclidean space with .  Then A is contained in an affine subspace of dimension at most .

This can be viewed as a “cheap” version of the more well known theorem of Freiman that places sets of small doubling in a torsion-free abelian group inside a generalised arithmetic progression.  The advantage here is that the bound on the dimension is extremely explicit.

Our main result is

Theorem.  Let A be a finite subset of a simply-connected nilpotent Lie group G which is a K-approximate group (i.e. A is symmetric, contains the identity, and can be covered by up to K left translates of A.  Then A can be covered by at most left-translates of a closed connected Lie subgroup of dimension at most .

We remark that our previous paper established a similar result, in which the dimension bound was improved to , but at the cost of worsening the covering number to , and with a much more complicated proof  (91 pages instead of 8). Furthermore, the bound on is ineffective, due to the use of ultraproducts in the argument (though it is likely that some extremely lousy explicit bound could eventually be squeezed out of the argument by finitising everything).  Note that the step of the ambient nilpotent group G does not influence the final bounds in the theorem, although we do of course need this step to be finite.  A simple quotienting argument allows one to deduce a corollary of the above theorem in which the ambient group is assumed to be residually torsion-free nilpotent instead of being a simply connected nilpotent Lie group, but we omit the statement of this corollary here.

To motivate the proof of this theorem, let us first show a simple case of an argument of Gleason, which is very much in the spirit of Freiman’s lemma:

Gleason Lemma (special case).  Let be a finite symmetric subset of a Euclidean space, and let be a sequence of subspaces in this space, such that the sets are strictly increasing in i for .  Then , where .

Proof.    By hypothesis, for each , the projection of to is non-trivial, finite, and symmetric.   In particular, since the vector space is torsion-free, is strictly larger than .  Equivalently, one can find  in that does not lie in ; in particular, and is disjoint from .  As a consequence, the are disjoint and lie in 5A, whence the claim.

Note that by combining the contrapositive of this lemma with a greedy algorithm, one can show that any K-approximate group in a Euclidean space is contained in a subspace of dimension at most , which is a weak version of Freiman’s lemma.

To extend the argument to the nilpotent setting we use the following idea.  Observe that any non-trivial genuine subgroup H of a nilpotent group G will contain at least one non-trivial central element; indeed, by intersecting H with the lower central series of G, and considering the last intersection which is non-trivial, one obtains the claim.  It turns out that one can adapt this argument to approximate groups, so that any sufficiently large K-approximate subgroup A of G will contain a non-trivial element that centralises a large fraction of A.  Passing to this large fraction and quotienting out the central element, we obtain a new approximate group.    If, after a bounded number of steps, this procedure gives an approximate group of bounded size, we are basically done.  If, however, the process continues, then by using some Lie group theory, one can find a long sequence of connected Lie subgroups of G, such that the sets are strictly increasing in i.   Using some Lie group theory and the hypotheses on G, one can deduce that the group generated by is much larger than , in the sense that the latter group has infinite index in the former.   It then turns out that the Gleason argument mentioned above can be adapted to this setting.

The structure of approximate groups

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “The structure of approximate groups“, submitted to Pub. IHES. We had announced the main results of this paper in various forums (including this blog) for a few months now, but it had taken some time to fully write up the paper and put in various refinements and applications.

As announced previously, the main result of this paper is what is a (virtually, qualitatively) complete description of finite approximate groups in an arbitrary (local or global) group . For simplicity let us work in the much more familiar setting of global groups, although our results also apply (but are a bit more technical to state) in the local group setting.

Recall that in a global group , a -approximate group is a symmetric subset of containing the origin, with the property that the product set is covered by left-translates of . Examples of -approximate groups include genuine groups, convex bodies in a bounded dimensional vector space, small balls in a bounded dimensional Lie group, large balls in a discrete nilpotent group of bounded rank or step, or generalised arithmetic progressions (or more generally, coset progressions) of bounded rank in an abelian group. Specialising now to finite approximate groups, a key example of such a group is what we call a coset nilprogression: a set of the form , where is a homomorphism with finite kernel from a subgroup of to a nilpotent group of bounded step, and is a nilprogression with a bounded number of generators in and some lengths , where consists of all the words involving at most copies of , copies of , and so forth up to copies of . One can show (by some nilpotent algebra) that all such coset nilprogressions are -approximate groups so long as the step and the rank are bounded (and if are sufficiently large).

Our main theorem (which was essentially conjectured independently by Helfgott and by Lindenstrauss) asserts, roughly speaking, that coset nilprogressions are essentially the only examples of approximate groups.

Theorem 1 Let be a -approximate group. Then contains a coset nilprogression of rank and step , such that can be covered by left-translates of .

In the torsion-free abelian case, this result is essentially Freiman’s theorem (with an alternate proof by Ruzsa); for general abelian case, it is due to Green and Ruzsa. Various partial results in this direction for some other groups (e.g. free groups, nilpotent groups, solvable groups, or simple groups of Lie type) are also known; see these previous blog posts for a summary of several of these results.

This result has a number of applications to geometric growth theory, and in particular to variants of Gromov’s theorem of groups of polynomial growth, which asserts that a finitely generated group is of polynomial growth if and only if it is virtually nilpotent. The connection lies in the fact that if the balls associated to a finite set of generators has polynomial growth, then some simple volume-packing arguments combined with the pigeonhole principle will show that will end up being a -approximate group for many radii . In fact, since our theorem only needs a single approximate group to obtain virtually nilpotent structure, we are able to obtain some new strengthenings of Gromov’s theorem. For instance, if is any -approximate group in a finitely generated group that contains for some set of generators and some that is sufficiently large depending on , our theorem implies that is virtually nilpotent, answering a question of Petrunin. Among other things, this gives an alternate proof of a recent result of Kapovitch and Wilking (see also this previous paper of Cheeger and Colding) that a compact manifold of bounded diameter and Ricci curvature at least necessarily has a virtually nilpotent fundamental group if is sufficiently small (depending only on dimension). The main point here is that no lower bound on the injectivity radius is required. Another application is a “Margulis-type lemma”, which asserts that if a metric space has “bounded packing” (in the sense that any ball of radius (say) is covered by a bounded number of balls of radius ), and is a group of isometries on that acts discretely (i.e. every orbit has only finitely many elements (counting multiplicity) in each bounded set), then the near-stabiliser of a point is virtually nilpotent if is small enough depending on the packing constant.

There are also some variants and refinements to the main theorem proved in the paper, such as an extension to local groups, and also an improvement on the bound on the rank and step from to (but at the cost of replacing in the theorem with ).

I’ll be discussing the proof of the main theorem in detail in the next few lecture notes of my current graduate course. The full proof is somewhat lengthy (occupying about 50 pages of the 90-page paper), but can be summarised in the following steps:

1. (Hrushovski) Take an arbitrary sequence of finite -approximate groups, and show that an appropriate limit of such groups can be “modeled” in some sense by an open bounded subset of a locally compact group. (The precise definition of “model” is technical, but “macroscopically faithful representation” is a good first approximation.) As discussed in the previous lecture notes, we use an ultralimit for this purpose; the paper of Hrushovski where this strategy was first employed also considered more sophisticated model-theoretic limits. To build a locally compact topology, Hrushovski used some tools from definability theory; in our paper, we instead use a combinatorial lemma of Sanders (closely related to a similar result of Croot and Sisask.)
2. (Gleason-Yamabe) The locally compact group can in turn be “modeled” by a Lie group (possibly after shrinking the group, and thus the ultralimit , slightly). (This result arose from the solution to Hilbert’s fifth problem, as discussed here. For our extension to local groups, we use a recent local version of the Gleason-Yamabe theorem, due to Goldbring.)
3. (Gleason) Using the escape properties of the Lie model, construct a norm (and thus a left-invariant metric ) on the ultralimit approximate group (and also on the finitary groups ) that obeys a number of good properties, such as a commutator estimate . (This is modeled on an analogous construction used in the theory of Hilbert’s fifth problem, as discussed in this previous set of lecture notes.) This norm is essentially an escape norm associated to (a slight modification) of or .
4. (Jordan-Bieberbach-Frobenius) We now take advantage of the finite nature of the by locating the non-trivial element of with minimal escape norm (but one has to first quotient out the elements of zero escape norm first). The commutator estimate mentioned previously ensures that this element is essentially “central” in . One can then quotient out a progression generated by this central element (reducing the dimension of the Lie model by one in the process) and iterates the process until the dimension of the model drops to zero. Reversing the process, this constructs a coset nilprogression inside . This argument is based on the classic proof of Jordan’s theorem due to Bieberbach and Frobenius, as discussed in this blog post.

One quirk of the argument is that it requires one to work in the category of local groups rather than global groups. (This is somewhat analogous to how, in the standard proofs of Freiman’s theorem, one needs to work with the category of Freiman homomorphisms, rather than group homomorphisms.) The reason for this arises when performing the quotienting step in the Jordan-Bieberbach-Frobenius leg of the argument. The obvious way to perform this step (and the thing that we tried first) would be to quotient out by the entire cyclic group generated by the element of minimal escape norm. However, it turns out that this doesn’t work too well, because the group quotiented out is so “large” that it can create a lot of torsion in the quotient. In particular, elements which used to have positive escape norm, can now become trapped in the quotient of , thus sending their escape norm to zero. This leads to an inferior conclusion (in which a coset nilprogression is replaced by a more complicated tower of alternating extensions between central progressions and finite groups, similar to the towers encountered in my previous paper on this topic). To prevent this unwanted creation of torsion, one has to truncate the cyclic group before it escapes , so that one quotients out by a geometric progression rather than the cyclic group. But the operation of quotienting out by a , which is a local group rather than a global one, cannot be formalised in the category of global groups, but only in the category of local groups. Because of this, we were forced to carry out the entire argument using the language of local groups. As it turns out, the arguments are ultimately more natural in this setting, although there is an initial investment of notation required, given that global group theory is much more familiar and well-developed than local group theory.

One interesting feature of the argument is that it does not use much of the existing theory of Freiman-type theorems, instead building the coset nilprogression directly from the geometric properties of the approximate group. In particular, our argument gives a new proof of Freiman’s theorem in the abelian case, which largely avoids Fourier analysis (except through the use of the theory of Hilbert’s fifth problem, which uses the Peter-Weyl theorem (or, in the abelian case, Pontryagin duality), which is basically a version of Fourier analysis).

An erratum to “Strongly dense free subgroups of semisimple Lie groups”

Last year, Emmanuel Breuillard, Ben Green, Bob Guralnick, and I wrote a paper entitled “Strongly dense free subgroups of semisimple Lie groups“. The main theorem in that paper asserted that given any semisimple algebraic group over an uncountable algebraically closed field , there existed a free subgroup which was strongly dense in the sense that any non-abelian subgroup of was Zariski dense in . This type of result is useful for establishing expansion in finite simple groups of Lie type, as we will discuss in a subsequent paper.

An essentially equivalent formulation of the main result is that if are two non-commuting elements of the free group on two generators, and is a generic pair of elements in , then and are not contained in any proper closed algebraic subgroup of . Here, “generic” means “outside of at most countably many proper subvarieties”. In most cases, one expects that if are generically drawn from , then will also be generically drawn from , but this is not always the case, which is a key source of difficulty in the paper. For instance, if is conjugate to in , then and must be conjugate in and so the pair lie in a proper subvariety of . It is currently an open question to determine all the pairs of words for which is not generic for generic (or equivalently, the double word map is not dominant).

The main strategy of proof was as follows. It is not difficult to reduce to the case when is simple. Suppose for contradiction that we could find two non-commuting words such that were generically trapped in a proper closed algebraic subgroup. As it turns out, there are only finitely many conjugacy classes of such groups, and so one can assume that were generically trapped in a conjugate of a fixed proper closed algebraic subgroup . One can show that , , and are generically regular semisimple, which implies that is a maximal rank semisimple subgroup. The key step was then to find another proper semisimple subgroup of which was not a degeneration of , by which we mean that there did not exist a pair in the Zariski closure of the products of conjugates of , such that generated a Zariski-dense subgroup of . This is enough to establish the theorem, because we could use an induction hypothesis to find in (and hence in such that generated a Zariski-dense subgroup of , which contradicts the hypothesis that was trapped in for generic (and hence in for all .

To illustrate the concept of a degeneration, take and let be the stabiliser of a non-degenerate -space in . All other stabilisers of non-degenerate -spaces are conjugate to . However, stabilisers of degenerate -spaces are not conjugate to , but are still degenerations of . For instance, the stabiliser of a totally singular -space (which is isomorphic to the affine group on , extended by ) is a degeneration of .

A significant portion of the paper was then devoted to verifying that for each simple algebraic group , and each maximal rank proper semisimple subgroup of , one could find another proper semisimple subgroup which was not a degeneration of ; roughly speaking, this means that is so “different” from that no conjugate of can come close to covering . This required using the standard classification of algebraic groups via Dynkin diagrams, and knowledge of the various semisimple subgroups of these groups and their representations (as we used the latter as obstructions to degeneration, for instance one can show that a reducible representation cannot degenerate to an irreducible one).

During the refereeing process for this paper, we discovered that there was precisely one family of simple algebraic groups for which this strategy did not actually work, namely the group (or the group that is double-covered by this group) in characteristic . This group (which has Dynkin diagram , as discussed in this previous post) has one maximal rank proper semisimple subgroup up to conjugacy, namely , which is the stabiliser of a line in . To find a proper semisimple group that is not a degeneration of this group, we basically need to find a subgroup that does not stabilise any line in . In characteristic larger than three (or characteristic zero), one can proceed by using the action of on the five-dimensional space of homogeneous degree four polynomials on , which preserves a non-degenerate symmetric form (the four-fold tensor power of the area form on ) and thus embeds into ; as no polynomial is fixed by all of , we see that this copy of is not a degeneration of .

Unfortunately, in characteristics two and three, the symmetric form on degenerates, and this embedding is lost. In the characteristic two case, one can proceed by using the characteristic fact that is isomorphic to (because in characteristic two, the space of null vectors is a hyperplane, and the symmetric form becomes symplectic on this hyperplane), and thus has an additional maximal rank proper semisimple subgroup which is not conjugate to the subgroup. But in characteristic three, it turns out that there are no further semisimple subgroups of that are not already contained in a conjugate of the . (This is not a difficulty for larger groups such as or , where there are plenty of other semisimple groups to utilise; it is only this smallish group that has the misfortune of having exactly one maximal rank proper semisimple group to play with, and not enough other semisimples lying around in characteristic three.)

As a consequence of this issue, our argument does not actually work in the case when the characteristic is three and the semisimple group contains a copy of (or ), and we have had to modify our paper to delete this case from our results. We believe that such groups still do contain strongly dense free subgroups, but this appears to be just out of reach of our current method.

One thing that this experience has taught me is that algebraic groups behave somewhat pathologically in low characteristic; in particular, intuition coming from the characteristic zero case can become unreliable in characteristic two or three.

A note on approximate subgroups of GL_n(C) and uniformly nonamenable groups

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “A note on approximate subgroups of and uniformly nonamenable groups“. In this short note, we obtain a new proof of a “noncommutative Freiman” type theorem in linear groups . As discussed in earlier blog posts, a general question in additive (or multiplicative) combinatorics is to understand the structure of approximate groups – subsets of genuine groups which are a symmetric neighbourhood the identity (thus and whenever ), and such that the product set is covered by left (or right) translates of for some bounded . (The case corresponds to the case of a genuine group.) Most of the focus in multiplicative combinatorics has been on the “discrete” case when is a finite set, though continuous cases are also of interest (for instance, small balls around the identity in a Lie group are approximate groups).

In the discrete case, examples of approximate groups include:

• Finite groups;
• Balls in a discrete abelian group, or more generally a discrete nilpotent group, with boundedly many generators;
• Extensions of the latter type of balls by finite groups;
• Approximate groups that are controlled by one of the previous examples , in the sense that has comparable cardinality to , and can be covered by boundedly many translates of .

It was conjectured independently by Helfgott and Lindenstrauss (private communication) that these are in fact the only examples of finite approximate groups. This conjecture is not yet settled in general (although we, with Tom Sanders, are making progress on this problem that we hope to be able to report on soon). However, many partial results are known. In particular, as part of the recent paper of Hrushovski in which model-theoretic techniques were introduced to study approximate groups, the following result was established:

Theorem 1 If , then every approximate subgroup of is controlled by a nilpotent approximate subgroup.

This result can be compared with Jordan’s theorem (discussed earlier on this blog) that every finite subgroup of is virtually abelian (with a uniform bound on the index of the abelian subgroup), or the special case of Gromov’s theorem for linear groups (which follows easily from the Tits alternative and the work of Milnor and of Wolf) that every finitely generated subgroup in of polynomial growth is virtually nilpotent.

Hrushovski’s proof of the above argument was quite sophisticated; one first transplants the problem using model-theoretic techniques to an infinitary setting, in which the approximate group induces a locally compact topological group structure, which can be played off against the Lie group structure of using the machinery of a paper of Larsen and Pink, as discussed in this previous blog article.

Two further proofs of this theorem were obtained by ourselves, as well as in the most recent version of a similar preprint by Pyber and Szabo. The arguments used here are variants of those used in earlier papers of Helfgott, and are based on establishing expansion of sets that generated Zariski-dense subgroups of various Lie groups (such as ). Again, the machinery of Larsen and Pink (which controls how such approximate subgroups intersect with algebraic subgroups) plays a central role.

In this note we give a new proof of this theorem, based primarily on a different tool, namely the uniform Tits alternative of Breuillard. Recall that the Tits alternative asserts that a finitely generated subgroup of is either virtually solvable, or contains a copy of a free group on two generators. In other words, if is a finite symmetric neighbourhood of the identity of , then either generates a virtually solvable subgroup, or else some power of contains two elements that generate a free group. As stated, may depend on . However, the uniform Tits alternative makes the stronger assertion that one can take to be uniform in , and depend only on the dimension parameter .

To use this alternative, we have the following simple observation, that asserts that multiplication by two elements that generate a free group forces a small amount of expansion:

Lemma 2 Let be finite sets, such that is symmetric and contains two elements that generate a free group . Then .

We remark that this lemma immediately establishes the classical fact that any group that contains a copy of is not amenable, an observation initially made by von Neumann.

Proof: By foliating into cosets of and translating, we may assume without loss of generality that . Observe that for every element in , at least three of the four elements has a longer word length than , while lying in . Furthermore, all such elements generated in this fashion are distinct (as one can recover the initial word from the longer word by truncation). The claim follows.

This can be combined with a lemma of Sanders (also independently established by Croot and Sisask), that asserts that for any approximate group , and any , one can find a smaller version of – also a symmetric neighbourhood of the identity – with the property that , while remains of comparable size to . (One should think of as being like a ball of some radius , in which case is analogous to a ball of radius ). In particular, still has size comparable to . Inspecting the size of the sets , we conclude (if is large enough) from the above lemma that cannot contain two elements that generate a free group. Indeed, a slight modification of this argument shows that for any , if we take sufficiently large depending on , that does not contain two elements that generate a free group. Applying the uniform Tits alternative, this shows that generates a virtually solvable subgroup of . From the known product theory for such groups (due to Breuillard and Green), (and hence ) is therefore controlled by a virtually nilpotent group, as desired.

Approximate subgroups of linear groups

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 , or more precisely absolutely almost simple algebraic groups over , such as . More precisely, define a -approximate subgroup of a genuine group to be a finite symmetric neighbourhood of the identity (thus and ) such that the product set can be covered by left-translates (and equivalently, right-translates) of .

Let be a field, and let be its algebraic closure. For us, an absolutely almost simple algebraic group over is a linear algebraic group defined over (i.e. an algebraic subvariety of for some with group operations given by regular maps) which is connected (i.e. irreducible), and such that the completion has no proper normal subgroups of positive dimension (i.e. the only normal subgroups are either finite, or are all of . To avoid degeneracies we also require 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 of such a group in the model case when generates the entire group , and is finite; they are either very small or very large.

Theorem 1 (Approximate groups that generate) Let be an absolutely almost simple algebraic group over . If is finite and is a -approximate subgroup of that generates , then either or , where the implied constants depend only on .

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

Theorem 2 (Zariski-dense approximate groups) Let be an absolutely almost simple algebraic group over . If is a -approximate group) is not contained in any proper algebraic subgroup of of complexity at most (where is sufficiently large depending on ), then either or , where the implied constants depend only on and is the group generated by .

Here, we say that an algebraic variety has complexity at most if it can be cut out of an ambient affine or projective space of dimension at most by using at most polynomials, each of degree at most . (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 is a linear group and thus comes with such an embedding.)

In the case when , the second option of this theorem cannot occur since is infinite, leading to a satisfactory classification of the Zariski-dense approximate subgroups of almost simple connected algebraic groups over . On the other hand, every approximate subgroup of 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 due to Breuillard and Green, we obtain our third theorem:

Theorem 3 (Freiman’s theorem in ) Let be a -approximate subgroup of . Then there exists a nilpotent -approximate subgroup of size at most , such that is covered by translates of .

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 .

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.

Suzuki groups as expanders

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv the paper “Suzuki groups as expanders“, to be submitted. The purpose of this paper is to finish off the last case of the following theorem:

Theorem 1 (All finite simple groups have expanders) For every finite simple non-abelian group , there exists a set of generators of cardinality bounded uniformly in , such that the Cayley graph on generated by (i.e. the graph that connects with for all and ) has expansion constant bounded away from zero uniformly in , or equivalently that for all with and some independent of .

To put in an essentially equivalent way, one can quickly generate a random element of a finite simple group with a near-uniform distribution by multiplying together a few (, to be more precise) randomly chosen elements of a fixed set . (The most well-known instance of this phenomenon is the famous result of Bayer and Diaconis that one can shuffle a 52-card deck reasonably well after seven riffle shuffles, and almost perfectly after ten.) Note that the abelian simple groups do not support expanders due to the slow mixing time of random walks in the abelian setting.

The first step in proving this theorem is, naturally enough, the classification of finite simple groups. The sporadic groups have bounded cardinality and are a trivial case of this theorem, so one only has to deal with the seventeen infinite families of finite non-abelian simple groups. With one exception, the groups in all of these families contain a copy of for some that goes to infinity as . Using this and several other non-trivial tools (such as Kazhdan’s property (T) and a deep model-theoretic result of Hrushovski and Pillay), the above theorem was proven for all groups outside of this exceptional family by a series of works culminating in the paper of Kassabov, Lubotzky, and Nikolov.

The exceptional family is the family of Suzuki groups , where is an odd power of . The Suzuki group can be viewed explicitly as a subgroup of the symplectic group and has cardinality . This cardinality is not divisible by , whereas all groups of the form have cardinality divisible by ; thus Suzuki groups do not contain copies of and the Kassabov-Lubotsky-Nikolov argument does not apply.

Our main result is that the Suzuki groups also support expanders, thus completing the last case of the above theorem. In fact we can pick just two random elements of the Suzuki group, and with probability , the Cayley graph generated by will be an expander uniformly in . (As stated in the paper of Kassabov-Lubotsky-Nikolov, the methods in that paper should give an upper bound on which they conservatively estimate to be .)

Our methods are different, instead following closely the arguments of Bourgain and Gamburd, which established the analogue of our result (i.e. that two random elements generate an expander graph) for the family of groups ( a large prime); the arguments there have since been generalised to several other major families of groups, and our result here can thus be viewed as one further such generalisation. Roughly speaking, the strategy is as follows. Let be the uniform probability measure on the randomly chosen set of generators , and let be the -fold convolution. We need to converge rapidly to the uniform measure on (with a mixing time of ). There are three steps to obtain this mixing:

• (Early period) When for some small , one wants to spread out a little bit in the sense that no individual element of is assigned a mass of any more than for some fixed . More generally, no proper subgroup of should be assigned a mass of more than .
• (Middle period) Once is somewhat spread out, one should be able to convolve this measure with itself a bounded number of times and conclude that the measure for some suitable is reasonably spread out in the sense that its norm is comparable (up to powers of for some small ) to the norm of the uniform distribution.
• (Late period) Once is reasonably spread out, a few more convolutions should make it extremely close to uniform (e.g. within in the norm).

The late period claim is easy to establish from Gowers’ theory of quasirandom groups, the key point being that (like all other finite simple nonabelian groups), the Suzuki groups do not admit any non-trivial low-dimensional irreducible representations (we can for instance use a precise lower bound of , due to Landazuri and Seitz). (One can also proceed here using a trace formula argument of Sarnak and Xue; the two approaches are basically equivalent.) The middle period reduces, by a variant of the Balog-Szemerédi-Gowers lemma, to a product estimate in which was recently established by Pyber-Szábo and can also be obtained by the methods of proof of the results announced by ourselves. (These arguments are in turn based on an earlier result of Helfgott establishing the analogous claim for .) This requires checking that is a “sufficiently Zariski dense” subgroup of the finite Lie group , but this can be done using an explicit description of the Suzuki group and the Schwartz-Zippel lemma.

The main difficulty is then to deal with the early period, obtaining some initial non-concentration in the random walk associated to away from subgroups of . These subgroups have been classified for some time (see e.g. the book of Wilson); they split into two families, the algebraic subgroups, which in the Suzuki case turn out to be solvable of derived length at most three, and the arithmetic subgroups, which are conjugate to , where is a subfield of .

In the algebraic case, one can prevent concentration using a lower bound on the girth of random Cayley graphs due to Gamburd, Hoory, Shahshahani, Shalev, and Virág (and we also provide an independent proof of this fact for completeness, which fortunately is able to avoid any really deep technology, such as Lang-Weil estimates); this follows an analogous argument of Bourgain-Gamburd in the case fairly closely, and is ultimately based on the fact that all the algebraic subgroups obey a fixed law (in this case, the law arises from the solvability). In the arithmetic case, the main task is to show that the coefficients of the characteristic polynomial of a typical word in does not fall into a proper subfield of , but this can be accomplished by a variant of the Schwartz-Zippel lemma.

Linear approximate groups

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our announcement “Linear approximate groups“, submitted to Electronic Research Announcements.

The main result is a step towards the classification of -approximate groups, in the specific setting of simple and semisimple Lie groups (with some partial results for more general Lie groups). For , define a -approximate group to be a finite subset of a group which is a symmetric neighbourhood of the origin (thus and is equal to ), and such that the product set is covered by left-translates (or equivalently, right-translates) of . For , this is the same concept as a finite subgroup of , but for larger values of , one also gets some interesting objects which are close to, but not exactly groups, such as geometric progressions for some and .

The expectation is that -approximate groups are -controlled by “structured” objects, such as actual groups and progressions, though the precise formulation of this has not yet been finalised. (We say that one finite set -controls another if is at most times larger than in cardinality, and can be covered by at most left translates or right translates of .) The task of stating and proving this statement is the noncommutative Freiman theorem problem, discussed in these earlier blog posts.

While this problem remains unsolved for general groups, significant progress has been made in special groups, notably abelian, nilpotent, and solvable groups. Furthermore, the work of Chang (over ) and Helfgott (over ) has established the important special cases of the special linear groups and :

Theorem 1 (Helfgott’s theorem) Let and let be either or for some prime . Let be a -approximate subgroup of .

• If generates the entire group (which is only possible in the finite case ), then is either controlled by the trivial group or the whole group.
• If , then is -controlled by a solvable -approximate subgroup of , or by itself. If , the latter possibility cannot occur, and must be abelian.

Our main result is an extension of Helfgott’s theorem to for general . In fact, we obtain an analogous result for any simple (or almost simple) Chevalley group over an arbitrary finite field (not necessarily of prime order), or over . (Standard embedding arguments then allow us to in fact handle arbitrary fields.) The results from simple groups can also be extended to (almost) semisimple Lie groups by an approximate version of Goursat’s lemma. Given that general Lie groups are known to split as extensions of (almost) semisimple Lie groups by solvable Lie groups, and Freiman-type theorems are known for solvable groups also, this in principle gives a Freiman-type theorem for arbitrary Lie groups; we have already established this in the characteristic zero case , but there are some technical issues in the finite characteristic case that we are currently in the process of resolving.

We remark that a qualitative version of this result (with the polynomial bounds replaced by an ineffective bound ) was also recently obtained by Hrushovski.

Our arguments are based in part on Helfgott’s arguments, in particular maximal tori play a major role in our arguments for much the same reason they do in Helfgott’s arguments. Our main new ingredient is a surprisingly simple argument, which we call the pivot argument, which is an analogue of a corresponding argument of Konyagin and Bourgain-Glibichuk-Konyagin that was used to prove a sum-product estimate. Indeed, it seems that Helfgott-type results in these groups can be viewed as a manifestation of a product-conjugation phenomenon analogous to the sum-product phenomenon. Namely, the sum-product phenomenon asserts that it is difficult for a subset of a field to be simultaneously approximately closed under sums and products, without being close to an actual field; similarly, the product-conjugation phenomenon asserts that it is difficult for a union of (subsets of) tori to be simultaneously approximately closed under products and conjugations, unless it is coming from a genuine group. In both cases, the key is to exploit a sizeable gap between the behaviour of two types of “pivots” (which are scaling parameters in the sum-product case, and tori in the product-conjugation case): ones which interact strongly with the underlying set , and ones which do not interact at all. The point is that there is no middle ground of pivots which only interact weakly with the set. This separation between interacting (or “involved”) and non-interacting (or “non-involved”) pivots can then be exploited to bootstrap approximate algebraic structure into exact algebraic structure. (Curiously, a similar argument is used all the time in PDE, where it goes under the name of the “bootstrap argument”.)

Below the fold we give more details of this crucial pivot argument.

One piece of trivia about the writing of this paper: this was the first time any of us had used modern version control software to collaboratively write a paper; specifically, we used Subversion, with the repository being hosted online by xp-dev. (See this post at the Secret Blogging Seminar for how to get started with this software.) There were a certain number of technical glitches in getting everything to install and run smoothly, but once it was set up, it was significantly easier to use than our traditional system of emailing draft versions of the paper back and forth, as one could simply download and upload the most recent versions whenever one wished, with all changes merged successfully. I had a positive impression of this software and am likely to try it again in future collaborations, particularly those involving at least three people. (It would also work well for polymath projects, modulo the technical barrier of every participant having to install some software.)