You are currently browsing the tag archive for the ‘freiman theorems’ tag.

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 |A+A| \leq K|A|.  Then A is contained in an affine subspace of dimension at most {}\lfloor K-1 \rfloor.

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 A \cdot A can be covered by up to K left translates of A.  Then A can be covered by at most K^{2+29K^9} left-translates of a closed connected Lie subgroup of dimension at most K^9.

We remark that our previous paper established a similar result, in which the dimension bound was improved to 6\log_2 K, but at the cost of worsening the covering number to O_K(1), and with a much more complicated proof  (91 pages instead of 8). Furthermore, the bound on O_K(1) 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 A be a finite symmetric subset of a Euclidean space, and let 0 = H_0 \subset H_1 \subset \ldots \subset H_k be a sequence of subspaces in this space, such that the sets 2A \cap H_i are strictly increasing in i for i=0,\ldots,k.  Then |5A| \geq k|A|, where 5A = A+A+A+A+A.

Proof.    By hypothesis, for each i=1,\ldots,k, the projection B_i of 2A \cap H_i to H_i / H_{i-1} is non-trivial, finite, and symmetric.   In particular, since the vector space H_i/H_{i-1} is torsion-free, B_i+B_i is strictly larger than B_i.  Equivalently, one can find a_i in (2A \cap H_i) + (2A \cap H_i) that does not lie in (2A \cap H_i) + H_{i-1}; in particular, a_i \in 4A \cap H_i and a_i+A is disjoint from H_{i-1}+A.  As a consequence, the a_i+A are disjoint and lie in 5A, whence the claim. \Box

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 K^4, 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 G = G_1 \geq G_2 \geq G_3 \geq \ldots of G, and considering the last intersection H \cap G_k 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 H_0 \leq H_1 \leq \ldots \leq H_k of connected Lie subgroups of G, such that the sets A^2 \cap H_i are strictly increasing in i.   Using some Lie group theory and the hypotheses on G, one can deduce that the group \langle A^2 \cap H_{i+1}\rangle generated by A^2 \cap H_{i+1} is much larger than \langle A^2 \cap H_i \rangle, 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.

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “A note on approximate subgroups of {GL_n({\bf C})} and uniformly nonamenable groups“. In this short note, we obtain a new proof of a “noncommutative Freiman” type theorem in linear groups {GL_n({\bf C})}. As discussed in earlier blog posts, a general question in additive (or multiplicative) combinatorics is to understand the structure of approximate groups – subsets {A} of genuine groups {G} which are a symmetric neighbourhood the identity (thus {id \in A} and {a^{-1} \in A} whenever {a \in A}), and such that the product set {A \cdot A := \{ ab: a,b \in A \}} is covered by {K} left (or right) translates of {A} for some bounded {K}. (The case {K=1} corresponds to the case of a genuine group.) Most of the focus in multiplicative combinatorics has been on the “discrete” case when {A} 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 {A} that are controlled by one of the previous examples {B}, in the sense that {A} has comparable cardinality to {B}, and can be covered by boundedly many translates of {B}.

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 {n=O(1)}, then every approximate subgroup of {GL_n({\bf C})} 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 {GL_n({\bf C})} 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 {GL_n({\bf C})} 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 {GL_n({\bf C})} 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 {SL_n({\bf C})}). 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 {GL_n({\bf C})} is either virtually solvable, or contains a copy of a free group on two generators. In other words, if {A} is a finite symmetric neighbourhood of the identity of {GL_n({\bf C})}, then either {A} generates a virtually solvable subgroup, or else some power {A^m} of {A} contains two elements {x,y} that generate a free group. As stated, {m} may depend on {A}. However, the uniform Tits alternative makes the stronger assertion that one can take {m=m(n)} to be uniform in {A}, and depend only on the dimension parameter {n}.

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 {A, B} be finite sets, such that {B} is symmetric and contains two elements {x,y} that generate a free group {F_2}. Then {|A \cdot B| \geq 3 |A|}.

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

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

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

This is an adaptation of a talk I gave recently for a program at IPAM. In this talk, I gave a (very informal and non-rigorous) overview of Hrushovski’s use of model-theoretic techniques to establish new Freiman-type theorems in non-commutative groups, and some recent work in progress of Ben Green, Tom Sanders and myself to establish combinatorial proofs of some of Hrushovski’s results.

Read the rest of this entry »