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:
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:
for all .
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.
and thus (if is sufficiently large depending on )
and in particular
and thus by Young’s inequality
for some . In other words,
If we then set , then
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:
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:
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:
- (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.