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 1Let 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:

- (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.)
- (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.)
- (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 . - (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).

## 22 comments

Comments feed for this article

24 October, 2011 at 10:58 pm

Proof mining and approximate groups, announcement | chorasimilarity[...] 25.10: Today a new post of Tao announces the submission on arxiv of the paper by him, Emmanuel Breuillard and Ben Green, [...]

25 October, 2011 at 1:22 am

AnonymousThe link to the “result of Kapovitch and Wilking” points to the paper you uploaded.

[Corrected, thanks - T.]25 October, 2011 at 5:43 am

Colin ReidWhat results are there like this when A is infinite? I am wondering if approximate group theory can be used to prove any interesting statements about how a commensurated (‘approximately normal’) subgroup H of an infinite group G is related to the normal closure of H in G, or about the ‘group-like’ structure of G/H.

25 October, 2011 at 7:49 am

Terence TaoFor infinite approximate groups (such as open precompact approximate groups in a locally compact group) some of the machinery indicated above seems to go through (in particular, the “Hrushovski”, “Gleason-Yamabe”, and “Gleason” components of the argument look likely to extend to this setting). However, the final step of the argument (what I called the “Jordan-Bieberbach-Frobenius” step) relies crucially on finiteness at this point. One of my students is looking at the extent to which these arguments can be carried over to the infinite setting though.

Your question about commensurated subgroups is an interesting one. At first glance, there does not seem to be an easy way to insert approximate groups into the situation: even if all conjugates gHg^{-1} are boundedly commensurate with H, this does not seem to imply that the union has good doubling properties (and in any event A could be huge relative to H). The general principle in this theory is that approximate closure by conjugation, by itself, is not enough to get the strongest structural properties; one also needs approximate closure by products as well. (This “product-conjugation” phenomenon comes up in the theory of approximate linear groups, particularly in the work of Helfgott, Pyber-Szabo, and Ben, Emmanuel, and myself, and also (in a somewhat different way) in the work of Larsen and Pink.) But this could be an artificial problem, caused by the limitations of our current methods, rather than by what types of theorems in this area are actually true.

31 October, 2011 at 5:09 am

valuevarHi Terry –

Congratulations on a nice result. As should be clear from my remarks in section 1 of http://arxiv.org/abs/0807.2027 , my “conjecture” (“It is tempting to guess that…”) involved a rather stronger statement on the rate of growth of sets A. In your terms – in theorem 1, I really hope that, where you have O_K(1), one should have K^O(1).

Now, it is true that (as Pyber showed, and as again I said in math:0807.2027) this stronger conjecture is not true in the symmetric group or in Lie groups of unbounded rank. Still, I feel that

(a) one should be able to prove this in all subgroups of SL_n(K), K a field,

(b) one should be able to prove slightly qualified versions of the K^O(1) statement in greater generality.

Thus I must say I still regard the conjecture as open. It is my understanding that there are people working on (a).

What do you think about (b), in full generality? I’ve developed by now some intuition for both linear algebraic groups and permutation groups, but funny things might in principle happen when many groups are put together, for example.

31 October, 2011 at 9:08 am

Terence TaoI agree that (a) (assuming n bounded, of course) should definitely be true, and should appear at some point (though I am not directly working on this problem). I don’t yet have enough intuition to make a guess about (b), other than to say that the permutation group case needs to be studied much more intensively to see how to obtain polynomially strong positive results in the absence of algebraic group theory (and in particular, without the very convenient maximal tori lying around to cleanly slice up approximate groups). Certainly the methods in this paper completely fail to give polynomial bounds; even ignoring all the ultrafilters, the very first step in the program (using the Sanders lemma) already concedes an exponential in the doubling constant which should not be present (indeed, if one combines (b) with a (presumably true) nilpotent version of Sanders’ Freiman-Bogulybov theorem, this loss should be quasipolynomial at worst). On the other hand, the final part of the argument (involving what we call “strong approximate groups”) is somewhat polynomially quantitative, and it may be able to obtain a version of (b) for strong approximate groups. But we have no idea how to reduce from approximate groups to strong approximate groups without using the whole Hilbert’s 5th problem machinery.

Another possibility is to replace the doubling, tripling, or approximate group condition by a stronger polynomial growth condition, something like |A^k| \leq k^{log K} |A|, pushing the problem much closer to the situation of Gromov’s theorem so that geometric group theory techniques become available (e.g. harmonic functions, a la Kleiner). Indeed, this is how Ben and I initially thought that the approximate groups conjecture would be solved (instead, we obtained polynomial growth of (a large chunk of) approximate groups as a corollary of the main theorem, rather than a key component of the proof).

31 October, 2011 at 10:32 am

valuevarI wouldn’t say that maximal tori are exactly what is missing. Rather, what we don’t have in permutation groups yet is any sort of dimensional analysis – how do we stick three copies of a centraliser in different directions, say?

As you may know, centralisers do play a role in my proof with Akos on permutation groups. (The approximate version of the orbit-stabiliser theorem is valid for any action of any group.) It is just that we were forced to arrange matters so that we obtained a reduction to a trivial centraliser – that is, the centraliser of a set of elements generating a doubly transitive group. (Such a centraliser contains only the identity.)

3 November, 2011 at 8:51 am

Marius BuligaI have a question: once you proved theorem 1, import a Carnot-Caratheodory type metric (from the nilpotent group) on the coset nilprogression (it makes sense because the CC metric is intimately related to the generating set of the nilprogression). The question is: does this (quasi)-metric have a meaning in terms of the approximate group?

3 November, 2011 at 9:40 am

Terence TaoIf one gives each generator in the coset nilprogression a “norm” of (and each element in the torsion group H a norm of 0) and uses this to define a weighted word metric (which is a discrete counterpart to the Carnot-Caratheodory metric), then the approximate group A is essentially the unit ball in this metric, and A^m is essentially the ball of radius m. So this metric would play a role in the geometric structure of A^m in the limit .

But when studying the internal structure of an approximate group A (rather than the growth properties of the iterated product sets ), the weighted word metric is comparable to the naive Euclidean metric (viewing elements of the nilprogression in “exponential coordinates of the second kind” (assuming that the generators obey a certain technical closure condition with respect to commutators, analogous to that used to define a Malcev basis, see our paper for details), and coordinatising such an element by the r-tuple ), or to the metric given by the escape norm. This is analogous to how the Carnot-Caratheodory metric on a Lie group (using a spanning set of vector fields) is comparable to the Riemannian metric at small scales.

In our arguments, it is the internal structure which is far more important than the asymptotic structure (and this is the main reason why we are able to extend our analysis to the local group case); the asymptotic structure is only obtained as a corollary once the internal structure is understood. It is conceivable that there is another approach to the classification of approximate groups that proceeds via studying the asymptotic structure first; the paper of Green and Ruzsa handling the abelian case is an instance of this, but it relies very much on the abelian fact that for an abelian approximate group A, the iterates A^m grow polynomially in m rather than exponentially. Such a statement is now known to be true in the nonabelian case too (after first passing from A to a dense subset) by means of our structure theorem, but we do not know of a direct way to establish this fact.

3 November, 2011 at 11:39 am

Marius BuligaThank you for the answer, very interesting! A Gleason metric is a CC metric if and only if the nilpotent group is abelian, because of the commutator estimate.

Concerning local groups, they are natural objects since Lie. I used them for dilatation structures (or dilation structures) and noticed (very roughly) that they seem strange to westerners and well-known to easterners (but see Olver as counterexample). There was a gap in the proof of one result, where I used for local groups a Siebert result which characterizes connected contractive groups. Glad to see later that Van den Dries and Goldbring paper “Locally compact contractive local groups” arxiv:0909.4565 provides Siebert theorem for local groups.

4 November, 2011 at 7:23 am

touDear Professor Tao.

Congratulations for this nice result.Looks like you have completed some major projects of yours. If it is possible, could you say something about your major future plans please?

13 November, 2011 at 5:20 pm

254A, Notes 9: Applications of the structural theory of approximate groups « What’s new[...] large, or if is placed in a certain “normal form”, details of which may be found in this paper), a coset nilprogression of rank and step will be an -approximate group, thus giving a partial [...]

1 December, 2011 at 7:58 am

254A, Notes 8: The microstructure of approximate groups « What’s new[...] must be replaced by the local version of this theorem, due to Goldbring); details can be found in this recent paper of Emmanuel Breuillard, Ben Green, and myself, but will only be sketched [...]

9 December, 2011 at 7:52 am

Approximate algebraic structures, emergent algebras | chorasimilarity[...] algebra can also be seen as an approximate algebraic structure! But in a different sense than approximate groups. The operations themselves are approximately associative, for [...]

21 December, 2011 at 4:24 pm

A nilpotent Freiman dimension lemma « What’s new[...] remark that our previous paper established a similar result, in which the dimension bound was improved to , but at the cost of [...]

21 December, 2011 at 4:50 pm

A nilpotent Freiman dimension lemma | t1u[...] remark that our previous paper established a similar result, in which the dimension bound was improved to , but at the cost of [...]

17 March, 2012 at 9:12 pm

254A, addendum: Some notes on nilprogressions « What’s new[...] groups, and use it to prove the above proposition, which turns out to be a bit tricky. (In my paper with Breuillard and Green, we avoid the need for this proposition by restricting attention to a special type of [...]

9 April, 2012 at 3:57 am

mac özetiThank you for the answer, very interesting! A Gleason metric is a CC metric if and only if the nilpotent group is abelian, because of the commutator estimate.

20 May, 2012 at 3:13 am

A geometric viewpoint on computation? | chorasimilarity[...] the profound resemblance between geometrical results of Gromov on groups with polynomial growth and combinatorial results of Breuillard, Gree, Tao on approximate groups? In both cases a nilpotent structure emerges from considering larger and larger scales. The word [...]

4 January, 2013 at 7:05 am

Approximate groupoids again « chorasimilarity[...] Here is the path I would like to pursue further. The notion of approximate groupoid (see here for the definition) is not complete, because it is flattened, i.e. the set of arrows should be seen as a set of variables. What I think is that the correct notion of approximate groupoid is a polynomial functor over groupoids (precisely a specific family of such functors). The category Grpd is cartesian closed, so it has an associated model of (typed) lambda calculus. By using this observation I could apply emergent algebra techniques (under the form of my graphic lambda calculus, which was developed with — and partially funded by – this application in mind) to approximate groupoids and hope to obtain streamlined proofs of Breuillard-Green-Tao type results. [...]

1 February, 2013 at 10:19 am

Small doubling in groups « What’s new[...] have Lie structure; this connection was first observed and exploited by Hrushovski, and then used by Breuillard, Green, and myself to obtain the analogue of Freiman’s theorem for an arbitrary nonabelian [...]

21 April, 2013 at 12:13 am

Carry propagation-free number systems and a kind of approximate groups (I) | chorasimilarity[...] (that’s what qualifies as a kind of an approximate group). [...]