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 1If , 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 2Let 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.

## 2 comments

Comments feed for this article

2 June, 2011 at 10:08 am

MRFProf. Tao,

Is it true that if A is a K-approximate group of fixed density d in a finite abelian group then there is a non-zero r such that the Fourier coefficient of 1_A at r has modulus bounded below in terms of d and K only? This seems to be true for all examples I can think of, including sumsets and Bohr sets, and it seems intuitively clear that if only K shifts of A are needed to cover A+A then A cannot be very randomlike.

In anticipation, thank you for your time.

2 June, 2011 at 10:19 am

Terence TaoWell, first of all the claim as stated is false for d=1 (take A to be the entire group G). But it is probably false in general also. Consider for instance a random subset A of Z/2NZ formed by selecting one element at random from {2n,2n+1} for each n=1,…,N. Then A and A+1 will cover Z/2NZ and will thus certainly cover A+A, on the other hand A will be very Fourier uniform. (This is not a symmetric set, but it is easy enough to modify this construction to make it symmetric and contain the origin.)

What is true, though, is that if A is dense and Fourier uniform, then A+A will occupy almost all of the group, and A+A+A will occupy all of the group. This is a standard application of Fourier-analytic methods (covered for instance in my book with Van). So one has a dichotomy for dense sets A; either there is a large Fourier coefficient, or A+A and A+A+A are very large.