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)

  • $\begingroup$ 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. $\endgroup$
    – Tom Church
    Jan 8, 2010 at 7:37
  • $\begingroup$ maybe Shalom and Tau's finatary version can be relevant? terrytao.wordpress.com/2009/10/23/… (but these are names you unlikely forget). $\endgroup$
    – Gil Kalai
    Jan 11, 2010 at 7:04
  • 13
    $\begingroup$ I don't know how often my name gets forgotten, but I have some non-trivial lower bounds on how often it gets misspelled. :-) $\endgroup$
    – Terry Tao
    Jan 11, 2010 at 16:49
  • 1
    $\begingroup$ Terry $\implies$ Te$rr$ence, part of the effect is intrinsic...^_^ $\endgroup$
    – Chulumba
    Jan 14, 2012 at 21:12

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

  • 2
    $\begingroup$ That is conjectured to imply virtual nilpotency, but this is still open. The best result in this direction so far is by Sanders, see arxiv.org/abs/0912.0305 , though his result is restricted currently to monomial groups. $\endgroup$
    – Terry Tao
    Jan 12, 2010 at 6:58
  • 5
    $\begingroup$ John Wilson proved that exponential growth is not the same as uniform exponential growth for finitely generated groups. John S. Wilson, On exponential growth and uniformly exponential growth for groups. Invent. Math. 155 (2004), no. 2, 287--303. $\endgroup$ Mar 18, 2010 at 15:19
  • $\begingroup$ I was told it is proved now (?) $\endgroup$ Aug 9, 2011 at 17:36
  • 3
    $\begingroup$ Yes, Ben Green, Emmanuel Breuillard, Tom Sanders, and I are writing up a paper on the classification of finite approximate groups which will include a positive answer to your question. (We're not quite done with it yet though - give it a few more weeks.) $\endgroup$
    – Terry Tao
    Aug 9, 2011 at 20:36
  • 2
    $\begingroup$ Done now: arxiv.org/abs/1110.5008 $\endgroup$
    – Terry Tao
    Nov 13, 2011 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.