# А generalization of Gromov's theorem on polynomial growth

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).

• 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)

• This is not what you're looking for, but just in case it helps: for the usual theorem, you only need the polynomial growth for infinitely many n, not necessarily all of them. This is proved in van den Dries and Wilkie, "Gromov's theorem on polynomial growth and elementary logic". But this is for one fixed generating set, so it doesn't answer your question. – Tom Church Jan 8 '10 at 7:37
• maybe Shalom and Tau's finatary version can be relevant? terrytao.wordpress.com/2009/10/23/… (but these are names you unlikely forget). – Gil Kalai Jan 11 '10 at 7:04
• I don't know how often my name gets forgotten, but I have some non-trivial lower bounds on how often it gets misspelled. :-) – Terry Tao Jan 11 '10 at 16:49
• Terry $\implies$ Te$rr$ence, part of the effect is intrinsic...^_^ – Chulumba Jan 14 '12 at 21:12

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).