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 {K}-approximate groups, in the specific setting of simple and semisimple Lie groups (with some partial results for more general Lie groups). For {K \geq 1}, define a {K}-approximate group to be a finite subset {A} of a group {G} which is a symmetric neighbourhood of the origin (thus {1 \in A} and {A^{-1} := \{a^{-1}: a \in A \}} is equal to {A}), and such that the product set {A \cdot A} is covered by {K} left-translates (or equivalently, {K} right-translates) of {A}. For {K=1}, this is the same concept as a finite subgroup of {G}, but for larger values of {K}, one also gets some interesting objects which are close to, but not exactly groups, such as geometric progressions {\{ g^n: -N \leq n \leq N \}} for some {g \in G} and {N \geq 1}.

The expectation is that {K}-approximate groups are {C_K}-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 {A} {K}-controls another {B} if {A} is at most {K} times larger than {B} in cardinality, and {B} can be covered by at most {K} left translates or right translates of {A}.) 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 {{\mathbb C}}) and Helfgott (over {{\Bbb F}_p}) has established the important special cases of the special linear groups {SL_2(k)} and {SL_3(k)}:

Theorem 1 (Helfgott’s theorem) Let {d = 2,3} and let {k} be either {{\Bbb F}_p} or {{\mathbb C}} for some prime {p}. Let {A} be a {K}-approximate subgroup of {G = SL_d(k)}.

  • If {A} generates the entire group {SL_d(k)} (which is only possible in the finite case {k={\Bbb F}_p}), then {A} is either controlled by the trivial group or the whole group.
  • If {d=2}, then {A} is {K^{O(1)}}-controlled by a solvable {K^{O(1)}}-approximate subgroup {B} of {G}, or by {G} itself. If {k={\mathbb C}}, the latter possibility cannot occur, and {B} must be abelian.

Our main result is an extension of Helfgott’s theorem to {SL_d(k)} for general {d}. 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 {{\mathbb C}}. (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 {k={\mathbb C}}, but there are some technical issues in the finite characteristic case {k = {\Bbb F}_q} that we are currently in the process of resolving.

We remark that a qualitative version of this result (with the polynomial bounds {K^{O(1)}} replaced by an ineffective bound {O_K(1)}) 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 {\xi} in the sum-product case, and tori in the product-conjugation case): ones which interact strongly with the underlying set {A}, 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.)

— 1. The pivot argument —

For simplicity let us work in {SL_2(k)}, which is slightly simpler because all semisimple (which, in this linear context, simply means diagonalisable) elements other than {\pm 1} are regular, which in the case of linear groups just means that the eigenvalues are distinct. Every regular element {a} of the three-dimensional {SL_2(k)} then generates a one-dimensional maximal torus {Z(a)}, which is also the centraliser of {a} (the set of all matrices in {SL_2(k)} that commute with {a}).

Let {A} be a {K}-approximate group that generates {SL_2(k)}, where we think of {K} as being small, say {K=O(1)} to simplify the discussion (of course, in the full argument we will need to track the dependence on {K} and keep it polynomial in nature). We may assume that {A} is not too small (more precisely, {|A| \geq CK^C} for some large {C}). As {A} lives in the three-dimensional group {SL_2(k)}, it is reasonable to expect that the intersection of {A} with a one-dimensional subset, such as a maximal torus, would be of size about {|A|^{1/3}}. And indeed this is true, as was observed by Helfgott:

Lemma 2 (Intersection with torus) If a maximal torus {T} intersects {A^2} (say) outside of {\{-1,+1\}}, then {A^{20} \cap T} (say) has cardinality {\sim |A|^{1/3}}.

For more general Lie groups, one can establish a similar upper bound (for more general algebraic varieties than just a torus) by using the Larsen-Pink inequality, which I discussed in this previous blog post. The lower bound is more important to us; it comes from noting that the conjugacy class {\{ gag^{-1}: g \in A^{20} \}} lies in {A^{41}} and also in a two-dimensional subset {C(a)} of {SL_2(k)}, and so should have cardinality {O(|A|^{2/3})}.

This lemma gives an important gap property: as soon as a maximal torus encounters just one regular element of {A^2}, it in fact has to absorb quite a lot of elements of the slightly larger set {A^{20}}. It is this gap which we exploit as follows. Let us say that a maximal torus {T} is involved if it intersects {A^2} outside of {\{-1,+1\}}.

Lemma 3 (Pivot rotation lemma) If {T} is an involved torus, then {aTa^{-1}} is also an involved torus for any {a \in A}.

Proof: (Sketch) We conjugate {aTa^{-1}} by a further element {b \in A}, and then multiply it on the left to get a new torus {cbaTa^{-1}b^{-1}}, where {a, b \in A}. On the one hand, we can think of this torus as of the form {xTy}, where {x \in A^3/T} and {y \in T \backslash A^2}. From Lemma 2 we see that there are only {O(|A|^{2/3})} values of {x} and {y}, and so there are {O(|A|^{4/3})} tori here. On the other hand, there are {|A|^2} choices of {b} and {c}. Hence there must be lots of collisions of the form

\displaystyle cbaTa^{-1}b^{-1} = c' b' aTa^{-1} (b')^{-1}.

Taking quotients, we see that

\displaystyle baTa^{-1}b^{-1} = b' aTa^{-1} (b')^{-1}

and thus {b' b^{-1}} lies in the normaliser {N(aTa^{-1})} of {aTa^{-1}}. But this is only twice as large as {aTa^{-1}} (the quotient of {N(aTa^{-1})} by {aTa^{-1}} is the Weyl group of {SL_2}, which in this two-dimensional case has cardinality {2!}.) But because there are so many collisions, it is not hard to use a pigeonhole argument to find a non-trivial pair {b,b'} where {b' b^{-1}} lies in the torus {aTa^{-1}} itself, and is not equal to {\pm 1}. This makes {aTa^{-1}} an involved torus as required. \Box

Now suppose that {A} generates all of {SL_2(k)}, then the set of involved tori is then invariant under conjugation by arbitrary elements of {SL_2(k)}. But all maximal tori in {SL_2} are conjugate to each other, and it is not hard to show that any large {A} must intersect at least one maximal torus non-trivially (using something called an escape from subvarieties argument), and so every maximal torus is an involved torus. But then there are {\sim |SL_2(k)|^{2/3}} such tori; this is only consistent with Lemma 2 if {|A| \sim |SL_2(k)|}, at which point one is done. A slightly more sophisticated version of this argument also works when {A} does not generate all of {SL_2(k)}.

It is instructive to compare the above argument to the analogous sum-product argument. Let {A} be an approximate subring of a field {F} (let us not define this concept precisely here). We say that a non-zero field element {\xi} is involved with {A} if the set of sums {\{ a+\xi b: a, b \in A \}} are not distinct, i.e. {|A + \xi A| < |A|^2}. The analogue of Lemma 2 here is that if {\xi} is involved, then in fact {\xi} must lie in the quotient set {Q := (A-A) / ((A-A) \backslash \{0\})} of {A}, just by using a collision {a+\xi b = c + \xi d} to solving for {\xi}. The analogue of Lemma 3 is then the observation that if {\xi} and {\eta} lie in {Q}, then {\xi+\eta} and {\xi \cdot \eta} are still sufficiently involved with {A} that one can bound {|A + (\xi+\eta) A|} or {|A + \xi \eta A|} to be strictly smaller than {|A|^2}, so that the sum and product of any two involved elements is again involved; this can be deduced from the so-called Katz-Tao lemma, which roughly asserts that if a set {A} is approximately closed under sums and products, then it (or a large portion thereof) is closed under more complicated polynomial and rational operations as well.