In the last set of notes, we obtained the following structural theorem concerning approximate groups:
Theorem 1 Let be a finite -approximate group. Then there exists a coset nilprogression of rank and step contained in , such that is covered by left-translates of (and hence also by right-translates of ).
Remark 1 Under some mild additional hypotheses (e.g. if the dimensions of are sufficiently large, or if is placed in a certain “normal form”, details of which may be found in this paper), a coset nilprogression of rank and step will be an -approximate group, thus giving a partial converse to Theorem 1. (It is not quite a full converse though, even if one works qualitatively and forgets how the constants depend on : if is covered by a bounded number of left- and right-translates of , one needs the group elements to “approximately normalise” in some sense if one wants to then conclude that is an approximate group.) The mild hypotheses alluded to above can be enforced in the statement of the theorem, but we will not discuss this technicality here, and refer the reader to the above-mentioned paper for details.
By placing the coset nilprogression in a virtually nilpotent group, we have the following corollary in the global case:
Corollary 2 Let be a finite -approximate group in an ambient group . Then is covered by left cosets of a virtually nilpotent subgroup of .
In this final set of notes, we give some applications of the above results. The first application is to replace “-approximate group” by “sets of bounded doubling”:
Proposition 3 Let be a finite non-empty subset of a (global) group such that . Then there exists a coset nilprogression of rank and step and cardinality such that can be covered by left-translates of , and also by right-translates of .
We will also establish (a strengthening of) a well-known theorem of Gromov on groups of polynomial growth, as promised back in Notes 0, as well as a variant result (of a type known as a “generalised Margulis lemma”) controlling the almost stabilisers of discrete actions of isometries.
The material here is largely drawn from my recent paper with Emmanuel Breuillard and Ben Green.
— 1. Sets of bounded doubling —
In this section we will deduce Proposition 3 from Theorem 1. This can be done using the general (non-abelian) additive combinatorics machinery from this paper of mine, but we will give here an alternate argument relying on a version of the Croot-Sisask lemma used in Notes 7 which is a little weaker with regards to quantitative bounds, but is slightly simpler technically (once one has the Croot-Sisask lemma).
We recall the Croot-Sisask lemma:
Lemma 4 (Croot-Sisask) Let be a non-empty finite subset of a group such that . Then any , there is a symmetric set containing the origin with such that
for all .
Let be as in Proposition 3. We apply Lemma 4 with some large depending on to be chosen later. Then for any one has
Since has an norm of and is supported on the set , which has cardinality at most , we see from Cauchy-Schwarz that
and hence (if is large enough depending on )
In particular, we have , thus every element of has representations of the form with . As there are at most pairs with , we conclude that . In particular, by the Ruzsa covering lemma (Exercise 21 from Notes 7) we see that can be covered by left-translates of , and hence is a -approximate group.
In view of Theorem 1, we thus see that to conclude the proof of Proposition 3, it suffices to show that can be covered by left-translates (or right-translates) of if is sufficiently large depending on .
We will just prove the claim for left-translates, as the claim for right-translates is similar. We will need the following useful inequality:
Lemma 5 (Ruzsa triangle inequality) Let be finite non-empty subsets of a group . Then .
Proof: Observe that if is an element of , so that for some and , then has at least representations of the form with and , since for all . As there are only possible pairs that could form such representations, the claim follows.
Now we return to the proof of Proposition 3. From (1) and Minkowski’s inequality we see that
and thus (if is sufficiently large depending on )
and in particular
and thus by Young’s inequality
and so
for some . In other words,
If we then set , then
and
and hence by the Ruzsa triangle inequality
By the Ruzsa covering lemma, this implies that can be covered by left-translates of , as required. This proves Proposition 3. By placing the coset nilprogression in a virtually nilpotent group, we obtain a strengthening of Corollary 2:
Corollary 6 Let be a finite non-empty subset of an ambient group such that . Then is covered by left cosets (and also by right-cosets) of a virtually nilpotent subgroup of .
We remark that there is also an “off-diagonal” version of Proposition 3:
Proposition 7 Let be finite non-empty subsets of a (global) group such that . Then there exists a coset nilprogression of rank and step and cardinality such that can be covered by left-translates of , and can be covered by right-translates of .
This is a consequence of Theorem 1 combined with Theorem 4.6 from this paper of mine; we omit the details. There is also a “statistical” variant (using instead Theorem 5.4 from this paper of mine), based on an additional tool, the (non-abelian) Balog-Szemerédi-Gowers theorem, which will not be discussed in detail here:
Proposition 8 Let be finite non-empty subsets of a (global) group such that
Then there exists a coset nilprogression of rank and step and cardinality such that intersects a left-translate of in a set of cardinality , and intersects a right-translate of in a set of cardinality .
— 2. Polynomial growth —
The above results show that finite approximate groups (as well as related objects, such as finite sets of bounded doubling) can be efficiently covered by virtually nilpotent groups. However, they do not place all of inside a virtually nilpotent group. Indeed, this is not possible in general:
Exercise 1 Let be the “ group”, that is to say the group of all affine transformations on the real line, with and . Show that there exists an absolute constant and arbitrarily large finite -approximate groups in that are not contained in any virtually nilpotent group. (Hint: build a set which is very “long” in the direction and very “thin” in the direction.)
Such counterexamples have the feature of being “thin” in at least one of the directions of . However, this can be fixed by adding a “thickness” assumption to the approximate group. In particular, we have the following result:
Theorem 9 (Thick sets of bounded doubling are virtually nilpotent) For every there exists such that the following statement holds: whenever is a group, is a finite symmetric subset of containing the identity, and is a finite set containing such that , then generates a virtually nilpotent group.
Proof: Fix , and let be a sufficiently large natural number depending on to be chosen later. Let be as in the theorem. By Proposition 3, there exists a virtually nilpotent group such that is covered by left-cosets of . In particular, consists of left-cosets of for all . On the other hand, as contains the identity, is nondecreasing in . If is large enough, then by the pigeonhole principle we may thus find some such that . By induction this implies that for all ; we conclude that
In particular, has finite index in . Since is virtually nilpotent, we conclude that is virtually nilpotent also.
This theorem leads to the following Gromov-type theorem:
Exercise 2 (Gromov-type theorem) Show that for every there exists such that the following statement holds: whenever is a group generated by a finite symmetric set of generators containing the identity, and for some , then is virtually nilpotent.
Note that this implies as a corollary the original theorem of Gromov that every finitely generated group of polynomial growth is virtually nilpotent, but it is stronger because (a) one only needs a polynomial growth bound at a single scale , rather than at all scales, and (b) the lower bound required on does not depend on the size of the generating set . (A previous result in this direction, which obtained (a) but not (b), was established by myself and Yehuda Shalom, by a rather different argument based on this paper of Kleiner. The original proof of Gromov of his theorem had some features in common with the arguments given here, in particular using the machinery of Gromov-Hausdorff limits as well as some of the theory surrounding Hilbert’s fifth problem, and was also amenable to nonstandard analysis methods as demonstrated by van den Dries and Wilkie, but differed in a number of technical details.)
Remark 2 By inspecting the arguments carefully, one can obtain a slightly sharper description of the group in Exercise 2, namely that contains a normal subgroup of index which is the extension of a finitely nilpotent group of step and rank by a finite group contained in . See this paper for details.
Exercise 3 (Gap between polynomial and non-polynomial growth) Show that there exists a function which grows faster than any polynomial (i.e. as for any ), with the property that whenever is any finitely generated group that is not virtually nilpotent, and is any symmetric set of generators of that contains the identity.
Remark 3 No effective bound for the function in this exercise is explicitly known, though in principle one could eventually extract such a bound by painstakingly finitising the proof of the structure theorem for approximate groups. If one restricts the size of to be bounded, then one can take to be for some and sufficiently large depending on the size of , by the result of my paper with Shalom, but this is unlikely to be best possible. (In the converse direction, Grigorchuk’s construction of a group of intermediate growth shows that cannot grow faster than for some absolute constant (and it is believed that one can take ).)
Exercise 4 (Infinite groups have at least linear growth) If is an infinite group generated by a finite symmetric set containing the identity, show that for all .
Exercise 5 (Linear growth implies virtually cyclic) Let be an infinite group generated by a finite symmetric set containing the identity. Suppose that is of linear growth, in the sense that for all and some finite .
- (i) Place a left-invariant metric on by defining to be the least natural number for which . Define a geodesic to be a finite or infinite sequence indexed by some discrete interval such that for all . Show that there exist arbitrarily long finite geodesics.
- (ii) Show that there exists a doubly infinite geodesic with . (Hint: use (i) and a compactness argument.)
- (iii) Show that for all . (Hint: study the balls of radius centred at and .) More generally, show that for all .
- (iv) Show that converges to a finite non-zero limit as , thus for all , where denotes a quantity which, when divided by , goes to zero as .
- (v) Show that for all , then all elements of lie within a distance at most of the geodesic . (Hint: first show that all but at most elements of lie within this distance, using (iv) and the argument used to prove (iii).)
- (vi) Show that for sufficiently large , lies within distance of .
- (vii) Show that for sufficiently large , lies within distance of .
- (viii) Show that is virtually cyclic (i.e. it has a cyclic subgroup of finite index).
Exercise 6 (Nilpotent groups have polynomial growth) Let be a finite symmetric subset of a nilpotent group containing the identity.
- (i) Let be an element of that is not the identity, and let be the minimal symmetric set containing that is closed under the operations . Show that is also a finite symmetric subset of containing the identity, and that every element of can be written in the form for some and , where the implied constant can depend on , .
- (ii) Show that for all and some depending on (i.e. is of polynomial growth).
- (iii) Show that every virtually nilpotent group is of polynomial growth.
— 3. Fundamental groups of compact manifolds (optional) —
This section presupposes some familiarity with Riemannian geometry. In these notes, Riemannian manifolds are always understood to be complete and without boundary.
We now apply the above theory to establish some relationships between the topology (and more precisely, the fundamental group) of a compact Riemannian manifold, and the curvature of such manifolds. A basic theme in this subject is that lower bounds on curvature tend to give somewhat restrictive control on the topology of a manifold. Consider for instance Myers’ theorem, which among other things tells us that a connected Riemannian manifold with a uniform positive lower bound on the Ricci curvature is necessarily compact (with an explicit upper bound on the diameter). In a similar vein we have the splitting theorem, which asserts that if a connected Riemannian manifold has everywhere non-negative Ricci curvature, then it splits as the product of a Euclidean space and a manifold without straight lines (i.e. embedded copises of ).
To analyse the fundamental group of a connected Riemannian manifold , it is convenient to work with its universal cover:
Exercise 7 Let be a connected Riemannian manifold.
- (i) (Existence of universal cover) Show that there exists a simply connected Riemannian manifold with the same dimension as with a smooth surjective map which is a local diffeomorphism and a Riemannian isometry (i.e. the metric tensors are preserved); such a manifold (or more precisely, the pair ) is known as a universal cover of . (Hint: take to be the space of all paths from a fixed base point in , quotiented out by homotopies fixing the endpoints. Once is constructed, pull back the smooth and Riemannian structures.)
- (ii) (Universality) Show that if is any smooth connected manifold with a smooth surjective map that is a local diffeomorphism and Riemannian isometry, and are point such that , then there exists a unique smooth map with that makes a universal cover of also.
- (iii) (Uniqueness) Show that a universal cover is unique up to isometric isomorphism.
- (iv) (Covering space) Show that for every there exists a neighbourhood of such that is isometric (as a Riemannian manifold) to , where we give the fundamental group the discrete topology. In particular, the fibres of a point are discrete and can be placed in bijection with .
- (v) (Deck transformations) Show that acts freely and isometrically on , in such a way that the orbits of are the fibres of . Conversely, show that every isometry on that preserves the fibres of arises from an element of .
- (vi) (Cocompactness) if is compact, and is a fibre of , show that every element of lies a distance at most from an element of the fibre .
- (vii) (Finite generation) If is compact and , show that the set is finite and generates . (Hint: if is further than from , use (vi) to find a factorisation such that is closer to or than is to .)
- (viii) (Polynomial growth) If is compact, show that the group is of polynomial growth (thus for some generating set , some , and all ) if and only if the universal cover is of polynomial growth (thus for some base point , some , and all ).
The above exercise thus links polynomial growth of groups to polynomial growth of manifolds. To control the latter, a useful tool is the Bishop-Gromov inequality:
Proposition 10 (Bishop-Gromov inequality) Let be a Riemannian manifold whose Ricci curvature is everywhere bounded below by some constant . Let be the simply connected Riemannian manifold of constant curvature and the same dimension as (this will be a Euclidean space for , a sphere for , and hyperbolic space for ). Let be a point in and be a point in . Then the expression
is monotone non-increasing in .
We will not prove this proposition here (as it requires, among other things, a definition of Ricci curvature, which would be beyond the scope of these notes); but see for instance this previous blog post of mine for a proof. This inequality is consistent with the geometric intuition that an increase in curvature on a manifold should correspond to a stunting of the growth of the volume of balls. For instance, in the positively curved spheres, the volume of balls eventually stabilises as a constant; in the zero curvature Euclidean spaces, the volume of balls grows polynomially; and in the negative curvature hyperbolic spaces, the volume of balls grows exponentially.
Informally, the balls in cannot grow any faster than the balls in . Setting , we conclude in particular that if has non-negative Ricci curvature and dimension , then is non-decreasing in ; in particular, any manifold of non-negative Ricci curvature is of polynomial growth. Applying Exercise 7 and Gromov’s theorem, we conclude that any manifold of non-negative Ricci curvature has a fundamental group which is virtually nilpotent. (In fact, such fundametal groups can be shown, using the splitting theorem, to be virtually abelian; see this paper of Cheeger and Gromoll. However, this improvement seems to be beyond the combinatorial methods used here.)
The above monotonicity also shows that whenever has Ricci curvature at least zero, we have the doubling bound
A continuity argument then shows that for every and , there exists such that if has Ricci curvature at least , then one has
for all .
Exercise 8 By using the above observation combined with Exercise 7 and Exercise 2, show that for every dimension there exists such that if is any compact Riemannian manifold of diameter at most and Ricci curvature at least everywhere, then is virtually nilpotent.
Remark 4 This result was first conjectured by Gromov, and was proven by Cheeger-Colding and Kapovitch-Wilking using deep Riemannian geometry tools (beyond just the Bishop-Gromov inequality). (See also this paper of Kapovitch-Petrunin-Tuschmann that established the analogous result assuming a lower bound on sectional curvature rather than Ricci curvature.)
The arguments in these papers in fact give more precise information on the fundamental group , namely that there is a nilpotent subgroup of step and rank and index . The methods here (based purely on controlling the growth of balls in ) can give the step and rank bounds, but appear to be insufficient to obtain the index bound. The exercise cannot be immediately obtained via a compactness-and-contradiction argument from the (easier) case mentioned previously, because of the problem of collapsing: there is no lower bound assumed on the injectivity radius of , and as such the space of all manifolds with the indicated diameter is non-compact even if one bounds the derivatives of the metric to all orders. (An equivalent way of phrasing the problem is that the orbits of in the universal cover may be arbitrarily dense, and so a ball of bounded radius in may correspond to an arbitrarily large subset of the fundamental group. For this application it is thus of importance that there is no upper bound on the size of the sets or assumed in Exercise 2.)
Remark 5 One way to view the above results is as an assertion that it is quite rare for a compact manifold to be equippable with a Riemannian metric with (almost) non-negative Ricci curvature. Indeed, an application of van Kampen’s theorem shows that every fundamental group of a compact manifold is finitely presented, and conversely a gluing argument for four-manifolds shows that every finitely presented group is the fundamental group of some (four-dimensional) manifold. Intuitively, “most” finitely presented groups are not virtually nilpotent, and so “most” compact manifolds cannot have metrics with almost non-negative Ricci curvature.
— 4. A Margulis-type lemma —
In Exercise 7 we saw that the fundamental group of a connected Riemannian manifold can be viewed as a discrete group of isometries acting on a Riemannian manifold . The curvature properties of then give doubling properties of the balls in , and hence of , allowing one to use tools such as Exercise 2.
It turns out that one can abstract this process by replacing the universal cover by a more general metric space :
Lemma 11 (Margulis-type lemma) Let . Let be a metric space, with the property that every ball of radius can be covered by balls of radius . Let be a group of isometries of , which acts discretely in the sense that is finite for every and every bounded set . Then if and is sufficiently small depending on , the set generates a virtually nilpotent group.
Proof: We can can cover by balls . If and , then (by the isometric action of ) we see that . We conclude that can be covered by right-translates of . Since and for all , the claim then follows from Exercise 2.
Roughly speaking, the above lemma asserts that for discrete actions of isometries on “spaces of bounded doubling”, the “almost stabiliser” of a point is “virtually nilpotent”. In the case when is a Riemannian manifold with a lower bound on curvature, this result was established by Cheeger-Colding and Kapovitch-Wilking (and, as mentioned in the previous section, stronger control on was established). The original lemma of Margulis addressed the case when was a hyperbolic space, and relied on commutator estimates not unrelated to the commutator estimates of Gleason metrics and of strong approximate groups that were used in previous notes.
14 comments
Comments feed for this article
13 November, 2011 at 6:30 pm
yan
Hi Dr Tao
I am a Chinese student, and i am now a graduate student in university of oklahoma studying math. and this is my first year.
i never learn logic classes before in China, and i even do not know what is vaculously true~but i think i can do math
but these days I meet a lot of confusing logic and i have a strong feeling that if i can not solve them at first, i can not do math, and math seems meaningless to me~
some of my problems are
G is a group, what does it mean? what I learned before is, every narrative sentence can be written as if,,,,then,,,,,so i can write it as if U is G, then U is a group. or does it mean that there exist a group, and we denote it by symbol G?
for every x in R, f(x)=f(-x), i usually think it as “if x in R, then f(x)=f(-x)” but if i think it in this way when i take negation or contraposition of this statement i may face problem~
the most confusing problem is now I do not know when we can take and when we can assume there is an element, because sometimes it is an “if” there, sometimes there is not an “if” there, for example when we proof H from G to M is a homomorphism, the definition is for every a,b in G, H(ab)=H(a)H(b), does this definition mean that “if a,b in G, then…” so whenever I do this proof I do not need to worry about if G is empty or not ,because we assume that , but i see some logic book it says that for every is quantifiers may be it doesn’t mean if.
i went to ask my professor, he said that i need not worry much about those things, i need to use common sense, but to me, common sense does not work!!! am i too stupid to understand? but my math is excellent at middel school and university. because i do not notice those things before, but when I notice them, i really feel so confused! what should I do now? i even want to drop school~
I really love math, but now i really confused by those problems and i feel i can not do math anymore, i think it is time for me to learn some logic right now, can you give me some advices and introduce some logic book to me, which can explain my question very clearly in it and easy to read?
thanks very much Dr Tao
9 December, 2011 at 4:05 am
shillo
Actually, there -are- specific rules for this stuff. First, it’s not really true that every mathematical sentence can be written only as ‘if… then…’ – you also need quantifiers. In your example, ‘Let G be a group. Then…’ actually means ‘For every group G, …’ or equivalently, ‘For every unspecified mathematical object G, if G is a group, then …’
In mathematical logic, ‘for every’ does not imply ‘there exists’. So you do always need to assume or prove that you are not dealing with empty sets. The reason why this is required are deMorgan laws for quantifiers. 1st de Morgan law: FOR ALL x.P(x) NOT EXISTS x.NOT P(x) In other words, ‘every group G has unit element’ is equivalent to saying ‘there is no group G such that is does not have a unit element’. But for this to hold, ‘every group G has unit element’ has to be true even if groups didn’t actually exist, because in that case, ‘there is no group G such that…’ would automatically be true.
14 November, 2011 at 9:49 am
tanaka
yan, I think, “group” means all the sets
that permits group operations and group axioms .
Therefore, “empty-group” is not a group.
15 November, 2011 at 5:32 am
valuevar
Does Hrushovski’s work already give by itself an alternative proof of Gromov?
15 November, 2011 at 5:39 am
Ben Green
Harald: yes it does, and in fact of a generalisation (as we remark in the paper). All of these arguments are fairly related to one another, and indeed to Gromov’s original argument.
15 November, 2011 at 8:05 am
Terence Tao
In a bit more detail: given a group G of polynomial growth, Hrushovski shows that large balls in G can be (virtually) modeled by some Lie group L, which gives a homomorphism from (a finite index subgroup of) G into L. This homomorphism may initially be trivial (or have finite image), but by precomposing with a suitable (nonstandard) inner automorphism of G first, we can force it to have infinite image (unless all conjugacy classes are bounded, but in that case it is easy to show that G is virtually abelian). Then, by applying Gromov’s theorem for finitely generated subgroups of Lie groups (which can be established in a number of ways, e.g. Tits alternative) the image of G in L must be virtually nilpotent, which by standard arguments shows that (a finite index subgroup of) G has an infinite abelianisation. Passing to the commutator subgroup, we obtain a group of lower growth (or, alternatively, a group that is asymptotically modeled by a Lie group of smaller dimension) and one can then continue by induction (similarly to the induction on dimension in our result classifying approximate groups). (But one needs to also know something like Gromov’s theorem for solvable groups (i.e. the Milnor-Wolf theorem) to pass back from the commutator subgroup back to the original group.)
Gromov’s original proof is very similar to this, but models large balls by a finite-dimensional metric space, and has a homomorphism from G to the isometry group of that space.
15 November, 2011 at 9:45 am
valuevar
– but the bit where you look at the Cayley graph from very far away disappears, I take, being replaced by Hrushovski’s argument. Or can Hrushovski’s argument also be understood in these terms?
15 November, 2011 at 10:36 am
Terence Tao
It’s very similar. Gromov is studying the asymptotic structure of a large ball in the Cayley graph, viewed as a metric space with a rescaled metric (so that the ball becomes of bounded radius). Hrushovski is studying the asymptotic structure of a large ball in the Cayley graph, viewed as an approximate group – so the focus is on the group structure rather than the metric structure. One could carry both the metric structure and the group structure over to the ultralimit, which would lead to a hybrid between the Hrushovski and Gromov arguments which would be slightly simpler than either argument separately (one would not need things like the Sanders lemma to get the local compactness of the relevant group models, because one already has a lot of small balls available to substitute for this lemma). But then it would be more difficult to get the strengthening of Gromov’s theorem that Hrushovski gives in his paper, in which he considers more general sets than large balls.
16 November, 2011 at 12:50 am
Marius Buliga
There is no difference between metric (on the Cayley graph) and algebraic structure of the group.
Question: is there any correspondence between these terms:
– classification of approximate groups up to rough equivalence
– classification of (Cayley graphs of) groups up to quasi-isometry?
I think it’s the same problem, only the tools differ.
16 November, 2011 at 8:17 am
Terence Tao
Actually, I believe the metric problem is much harder. For instance, it is still an open question whether two non-commensurable finitely generated torsion-free nilpotent groups can be quasi-isometric. (A well-known modification of Pansu’s argument shows that such groups must have the same asymptotic Carnot group, but this does not fully determine the group structure.) In contrast, the approximate groups in torsion-free nilpotent groups have been completely classified by Breuillard and Green.
The problem is that one needs to know the entire metric structure exactly (at both micro and macro scales) to reconstruct the group structure (and vice versa). Knowing the metric structure up to quasi-isometry is not obviously sufficient to reconstruct the group structure, even approximately.
17 November, 2011 at 7:42 am
Marius Buliga
Question (please erase if not appropriate): as a metric space is just a particular example of a normed groupoid, could you point me to papers where “approximate groupoids” are studied? For starters, something like an extension of your paper “Product set estimates for non-commutative groups”, along the lines in the introduction “one also consider partial sum sets …”, could be relevant, but I am unable to locate any. Following your proofs could be straightforward, but lengthy. Has this been done?
For example, a approximate groupoid of a groupoid (where denotes the set of arrows) could be a
(i)- symmetric subset of : , for any and
(ii)- there is another, symmetric subset such that for any there are such that
,
(iii)- for any we have .
One may replace the cardinal, as you did, by a measure (or random walk kernel, etc), or even by a norm.
5 February, 2012 at 12:16 pm
254B, Notes 5: Product theorems, pivot arguments, and the Larsen-Pink non-concentration inequality « What’s new
[…] theorem in solvable groups (or the Helfgott-Lindenstrauss conjecture, discussed in the previous quarter’s notes), one can give even more precise descriptions of (at the cost of losing polynomial dependence of […]
11 July, 2012 at 1:31 am
Approximate groupoids may be useful | chorasimilarity
[…] I just remembered a comment that I have made last november on the blog of Tao, where I proposed to study “approximate […]
11 September, 2012 at 4:25 am
chorasimilarity
Maybe this is the good place to ask the following question. Background first: the computational complexity of (running time of an algorithm for) multiplication in a Lie group varies wildly with the group, for example from the case when the group is abelian, to the case of a general linear group.
For approximate groups, your result with Breuillard and Green gives models which are noncomutative progressions in nilpotent groups.
My question is: can we deduce from your result some estimates for the computational complexity of the multiplication operation in an approximate group?
As a starting point I asked this question at mathoverflow. See also (edit if spam, please) this half-joking post which asks for a positional number system (hence an efficient algorithm for multiplication) in a Carnot group, by using its intrinsic self-similarity.