А generalization of Gromov's theorem on polynomial growth

Question

I was sure it is known, but it appears to be an open problem (see the answer of Terry Tao).

Assume for a group $G$ there is a polynomial $P$ such that given $n\in\mathbb N$ there is set of generators $S=S^{-1}$ such that $$|S^n|\leqslant P(n)\cdot|S|\ \ (\text{or stronger condition}\ |S^k|\leqslant P(k)\cdot|S|\ \text{for all}\ k\le n) .$$ Then $G$ is virtually nilpotent (or equivalently it has polynomial growth).

Comments:

• Note that typically, $|S|\to \infty$ as $n \to\infty$ (otherwise it follows easily from the original Gromov's theorem).

• If it is known, then it would give a group-theoretical proof that manifolds with almost non-negative Ricci curvature have virtually nilpotent fundamental group (see Kapovitch--Wilking, "Structure of fundamental groups..."). This proof would use only one result in diff-geometry: Bishop--Gromov inequality.

Edit: The actual answer is "Done now: arxiv.org/abs/1110.5008" --- it is a comment to the accepted answer. (Published reference: E. Breuillard, B. Green, T. Tao. The structure of approximate groups. Publ. Math. Inst. Hautes Études Sci. 116 (2012), 115–221. Link under Springer paywall)

Answer 1

My paper with Shalom does settle the question when $S = S_n$ is known to have size polynomial in n (and maybe is allowed to grow just a little bit faster than this, something like $n^{(\log \log n)^c}$ or so), but I doubt that the result is known yet if S is allowed to be arbitrarily large.

Note that even the bounded case is nontrivial - it's not obvious why having $|S_n^n| \leq n^{O(1)} |S_n|$ implies polynomial growth. (There is no reason why growth has to be uniform for fixed cardinality of generators; for instance, I believe it is a major open problem (due to Gromov?) as to whether exponential growth is the same as uniform exponential growth for finitely generated groups.)

If we had a good non-commutative Freiman theorem, then one may possibly be able to settle your question affirmatively (note from the pigeonhole principle that if $|S_n^n| \leq n^C |S_n|$ for some large n, then there exists an intermediate $m=m_n$ between 1 and n such that the set $B := S_n^m$ has small doubling, in the sense that $|B^2| = O(|B|)$). The best result in this direction for general groups currently is due to Hrushovski, which does show that sets of small doubling contain some vaguely "virtually nilpotent" structure, but it is not yet enough to give Gromov's theorem, let alone the generalisation you mention above. More is known if one already has some additional structure on the group (e.g. it has a faithful linear representation of bounded dimension, or if it is already known to be virtually solvable).