This is another one of my favourite open problems, falling under the heading of inverse theorems in arithmetic combinatorics. “Direct” theorems in arithmetic combinatorics take a finite set A in a group or ring and study things like the size of its sum set A+A := \{ a+b: a,b \in A \} or product set A \cdot A := \{ ab: a,b \in A \}. For example, a typical result in this area is the sum-product theorem, which asserts that whenever A \subset {\Bbb F}_p is a subset of a finite field of prime order with 1 \leq |A| \leq p^{1-\delta}, then

\max( |A+A|, |A \cdot A| ) \geq |A|^{1+\epsilon}

for some \epsilon = \epsilon(\delta) > 0. (This particular theorem was first proven here, with an earlier partial result here; more recent and elementary proofs with civilised bounds can be found here, here or here. It has a number of applications.)

In contrast, inverse theorems in this subject start with a hypothesis that, say, the sum set A+A of an unknown set A is small, and try to deduce structural information about A. A typical goal is to completely classify all sets A for which A+A has comparable size with A. In the case of finite subsets of integers, this is Freiman’s theorem, which roughly speaking asserts that if |A+A| = O(|A|), if and only if A is a dense subset of a generalised arithmetic progression P of rank O(1), where we say that A is a dense subset of B if A \subset B and |B| = O(|A|). (The “if and only if” has to be interpreted properly; in either the “if” or the “only if” direction, the implicit constants in the conclusion depends on the implicit constants in the hypothesis, but these dependencies are not inverses of each other.) In the case of finite subsets A of an arbitrary abelian group, we have the Freiman-Green-Ruzsa theorem, which asserts that |A+A| = O(|A|) if and only if A is a dense subset of a sum P+H of a finite subgroup H and a generalised arithmetic progression P of rank O(1).


One can view these theorems as a “robust” or “rigid” analogue of the classification of finite abelian groups. It is well known that finite abelian groups are direct sums of cyclic groups; the above results basically assert that finite sets that are “nearly groups” in that their sum set is not much larger than the set itself, are (dense subsets of) the direct sums of cyclic groups and a handful of arithmetic progressions.

The open question is to formulate an analogous conjectural classification in the non-abelian setting, thus to conjecture a reasonable classification of finite sets A in a multiplicative group G for which |A \cdot A| = O(|A|). Actually for technical reasons it may be better to use |A \cdot A \cdot A| = O(|A|); I refer to this condition by saying that A has small tripling. (Note for instance that if H is a subgroup and x is not in the normaliser of H, then H \cup \{x\} has small doubling but not small tripling. On the other hand, small tripling is known to imply small quadrupling, etc., see e.g. my book with Van Vu.) Note that I am not asking for a theorem here – just even stating the right conjecture would be major progress! An if and only if statement might be too ambitious initially: a first step would be to obtain a slightly looser equivalence, creating for each group G and fixed \epsilon > 0 a class ??? of sets for which the following two statements are true:

  1. If A is a finite subset of G with small tripling, then A is a dense subset of O(|A|^\epsilon) left- or right- translates of a set P of the form ???.
  2. If P is a set of the form ???, then there exists a dense subset A of P with small tripling (possibly with a loss of O(|A|^\epsilon) in the tripling constant).

An obvious candidate for ??? is the inverse image in N(H) of a generalised geometric progression of rank O(1) in an abelian subgroup of N(H)/H, where H is a finite subgroup of G and N(H) is the normaliser of H; note that property (2) is then easy to verify. Let us call this the standard candidate. I do not expect this standard candidate to fully suffice, though I do not know at present of a counterexample. (Update, Mar 5: Now I do – a discrete ball in a nilpotent group.) But it seems to be a reasonably good candidate nevertheless. In this direction, some partial results are known:

  • For abelian groups G, from the Freiman-Green-Ruzsa theorem, we know that the standard candidate suffices.
  • For G = SL_2({\Bbb C}), we know from work of Elekes and Király and Chang that the standard candidate suffices.
  • For G = SL_2({\Bbb F}_p), there is a partial result of Helfgott, which (roughly speaking) asserts that if A has small tripling, then either A is a dense subset of all of G, or is contained in a proper subgroup of G. It is likely that by pushing this analysis further one would obtain a candidate for ??? in this case.
  • For G = SL_3({\Bbb Z}), there is a partial result of Chang, which asserts that if A has small tripling, then it is contained in a nilpotent subgroup of G.
  • For the lamplighter group G = {\Bbb Z}/2{\Bbb Z} \wr {\Bbb Z}, there is a partial result of Lindenstrauss which (roughly speaking) asserts that if A has small tripling, then A cannot be nearly invariant under a small number of shifts. It is also likely that by pushing the analysis further here one would get a good candidate for ???.
  • For a free non-abelian group, we know (since the free group embeds into SL_2({\Bbb C})) that the standard candidate suffices; a much stronger estimate in this direction was recently obtained by Razborov.
  • For a Heisenberg group G of step 2, there is a partial result of myself, which shows that sets of small tripling also have small tripling in the abelianisation of G, and are also essentially closed under the antisymmetric form that defines G. This, in conjunction with the Freiman-Green-Ruzsa theorem, gives a characterisation, at least in principle, but it is not particularly explicit, and it may be of interest to work it out further.
  • For G torsion-free, there is a partial result of Hamidoune, Lladó, and Serra, which asserts that |A \cdot A| \geq 2|A|-1, and that if |A \cdot A| \leq 2|A| then A is a geometric progression with at most one element removed; in particular, the standard candidate suffices in this case.

These examples do not seem to conclusively suggest what the full classification should be. Based on analogy with the classification of finite simple groups, one might expect the full classification to be complicated, and enormously difficult to prove; on the other hand, the fact that we are in a setting where we are allowed to lose factors of O(1) may mean that the problem is in fact significantly less difficult than that classification. (For instance, all the sporadic simple groups have size O(1) and so even the monster group is “negligible”.) Nevertheless, it seems possible to make progress on explicit groups, in particular refining the partial results already obtained for the specific groups mentioned above. (Update, Mar 5: Via Akshay Venkatesh and Elon Lindenstrauss, I learnt that perhaps the closer analogy is with Gromov’s theorem, rather than the classification of finite simple groups. Which makes things slightly more hopeful… nevertheless, the question of revisiting the classification from a “O(1) perspective” may still be interesting.)