This fall (starting Monday, September 26), I will be teaching a graduate topics course which I have entitled “Hilbert’s fifth problem and related topics.” The course is going to focus on three related topics:

- Hilbert’s fifth problem on the topological description of Lie groups, as well as the closely related (local) classification of locally compact groups (the Gleason-Yamabe theorem).
- Approximate groups in nonabelian groups, and their classification via the Gleason-Yamabe theorem (this is very recent work of Emmanuel Breuillard, Ben Green, Tom Sanders, and myself, building upon earlier work of Hrushovski);
- Gromov’s theorem on groups of polynomial growth, as proven via the classification of approximate groups (as well as some consequences to fundamental groups of Riemannian manifolds).

I have already blogged about these topics repeatedly in the past (particularly with regard to Hilbert’s fifth problem), and I intend to recycle some of that material in the lecture notes for this course.

The above three families of results exemplify two broad principles (part of what I like to call “the dichotomy between structure and randomness“):

- (Rigidity) If a group-like object exhibits a weak amount of regularity, then it (or a large portion thereof) often automatically exhibits a strong amount of regularity as well;
- (Structure) This strong regularity manifests itself either as Lie type structure (in continuous settings) or nilpotent type structure (in discrete settings). (In some cases, “nilpotent” should be replaced by sister properties such as “abelian“, “solvable“, or “polycyclic“.)

Let me illustrate what I mean by these two principles with two simple examples, one in the continuous setting and one in the discrete setting. We begin with a continuous example. Given an complex matrix , define the matrix exponential of by the formula

which can easily be verified to be an absolutely convergent series.

Exercise 1Show that the map is a real analytic (and even complex analytic) map from to , and obeys the restricted homomorphism property

Proposition 1 (Rigidity and structure of matrix homomorphisms)Let be a natural number. Let be the group of invertible complex matrices. Let be a map obeying two properties:

- (Group-like object) is a homomorphism, thus for all .
- (Weak regularity) The map is continuous.
Then:

- (Strong regularity) The map is smooth (i.e. infinitely differentiable). In fact it is even real analytic.
- (Lie-type structure) There exists a (unique) complex matrix such that for all .

*Proof:* Let be as above. Let be a small number (depending only on ). By the homomorphism property, (where we use here to denote the identity element of ), and so by continuity we may find a small such that for all (we use some arbitrary norm here on the space of matrices, and allow implied constants in the notation to depend on ).

The map is real analytic and (by the inverse function theorem) is a diffeomorphism near . Thus, by the inverse function theorem, we can (if is small enough) find a matrix of size such that . By the homomorphism property and (1), we thus have

On the other hand, by another application of the inverse function theorem we see that the squaring map is a diffeomorphism near in , and thus (if is small enough)

We may iterate this argument (for a fixed, but small, value of ) and conclude that

for all . By the homomorphism property and (1) we thus have

whenever is a dyadic rational, i.e. a rational of the form for some integer and natural number . By continuity we thus have

for all real . Setting we conclude that

for all real , which gives existence of the representation and also real analyticity and smoothness. Finally, uniqueness of the representation follows from the identity

Exercise 2Generalise Proposition 1 by replacing the hypothesis that is continuous with the hypothesis that is Lebesgue measurable (Hint:use the Steinhaus theorem.). Show that the proposition fails (assuming the axiom of choice) if this hypothesis is omitted entirely.

Note how one needs both the group-like structure and the weak regularity in combination in order to ensure the strong regularity; neither is sufficient on its own. We will see variants of the above basic argument throughout the course. Here, the task of obtaining smooth (or real analytic structure) was relatively easy, because we could borrow the smooth (or real analytic) structure of the domain and range ; but, somewhat remarkably, we shall see that one can still build such smooth or analytic structures even when none of the original objects have any such structure to begin with.

Now we turn to a second illustration of the above principles, namely Jordan’s theorem, which uses a discreteness hypothesis to upgrade Lie type structure to nilpotent (and in this case, abelian) structure. We shall formulate Jordan’s theorem in a slightly stilted fashion in order to emphasise the adherence to the above-mentioned principles.

Theorem 2 (Jordan’s theorem)Let be an object with the following properties:

- (Group-like object) is a group.
- (Discreteness) is finite.
- (Lie-type structure) is contained in (the group of unitary matrices) for some .
Then there is a subgroup of such that

- ( is close to ) The index of in is (i.e. bounded by for some quantity depending only on ).
- (Nilpotent-type structure) is abelian.

A key observation in the proof of Jordan’s theorem is that if two unitary elements are close to the identity, then their commutator is even closer to the identity (in, say, the operator norm ). Indeed, since multiplication on the left or right by unitary elements does not affect the operator norm, we have

and so by the triangle inequality

Now we can prove Jordan’s theorem.

*Proof:* We induct on , the case being trivial. Suppose first that contains a central element which is not a multiple of the identity. Then, by definition, is contained in the centraliser of , which by the spectral theorem is isomorphic to a product of smaller unitary groups. Projecting to each of these factor groups and applying the induction hypothesis, we obtain the claim.

Thus we may assume that contains no central elements other than multiples of the identity. Now pick a small (one could take in fact) and consider the subgroup of generated by those elements of that are within of the identity (in the operator norm). By considering a maximal -net of we see that has index at most in . By arguing as before, we may assume that has no central elements other than multiples of the identity.

If consists only of multiples of the identity, then we are done. If not, take an element of that is not a multiple of the identity, and which is as close as possible to the identity (here is where we crucially use that is finite). By (2), we see that if is sufficiently small depending on , and if is one of the generators of , then lies in and is closer to the identity than , and is thus a multiple of the identity. On the other hand, has determinant . Given that it is so close to the identity, it must therefore be the identity (if is small enough). In other words, is central in , and is thus a multiple of the identity. But this contradicts the hypothesis that there are no central elements other than multiples of the identity, and we are done.

Commutator estimates such as (2) will play a fundamental role in many of the arguments we will see in this course; as we saw above, such estimates combine very well with a discreteness hypothesis, but will also be very useful in the continuous setting.

Exercise 3Generalise Jordan’s theorem to the case when is a finite subgroup of rather than of . (Hint:The elements of are not necessarily unitary, and thus do not necessarily preserve the standard Hilbert inner product of . However, if one averages that inner product by the finite group , one obtains a new inner product on that is preserved by , which allows one to conjugate to a subgroup of . This averaging trick is (a small) part of Weyl’s unitary trick in representation theory.)

Exercise 4 (Inability to discretise nonabelian Lie groups)Show that if , then the orthogonal group cannot contain arbitrarily dense finite subgroups, in the sense that there exists an depending only on such that for every finite subgroup of , there exists a ball of radius in (with, say, the operator norm metric) that is disjoint from . What happens in the case?

Remark 1More precise classifications of the finite subgroups of are known, particularly in low dimensions. For instance, one can show that the only finite subgroups of (which is a double cover of) are isomorphic to either a cyclic group, a dihedral group, or the symmetry group of one of the Platonic solids.

** — 1. Hilbert’s fifth problem — **

One of the fundamental categories of objects in modern mathematics is the category of Lie groups, which are rich in both algebraic and analytic structure. Let us now briefly recall the precise definition of what a Lie group is.

Definition 3 (Smooth manifold)Let be a natural number. An -dimensional topological manifold is a Hausdorff topological space which islocally Euclidean, thus every point in has a neighbourhood which is homeomorphic to an open subset of .A

smooth atlason an -dimensional topological manifold is a family of homeomorphisms from open subsets of to open subsets of , such that the form an open cover of , and for any , the map is smooth (i.e. infinitely differentiable) on the domain of definition . Two smooth atlases areequivalentif their union is also a smooth atlas; this is easily seen to be an equivalence relation. An equivalence class of smooth atlases is asmooth structure. Asmooth manifoldis a topological manifold equipped with a smooth structure.A map from one smooth manifold to another is said to be smooth if is a smooth function on the domain of definition for any smooth charts in any the smooth atlases of respectively (one easily verifies that this definition is independent of the choice of smooth atlas in the smooth structure).

Note that we do not require manifolds to be connected, nor do we require them to be embeddable inside an ambient Euclidean space such as , although certainly many key examples of manifolds are of this form. The requirement that the manifold be Hausdorff is a technical one, in order to exclude pathological examples such as the line with a doubled point (formally, consider the double line after identifying with for all ), which is locally Euclidean but not Hausdorff. (In some literature, additional technical assumptions such as paracompactness, second countability, or metrisability are imposed to remove pathological examples of topological manifolds such as the long line, but it will not be necessary to do so in this course, because (as we shall see later) we can essentially get such properties “for free” for locally Euclidean groups.)

Remark 2It is a plausible, but non-trivial, fact that a (non-empty) topological manifold can have at most one dimension associated to it; thus a manifold cannot both be locally homeomorphic to and locally homeomorphic to unless . This fact is a consequence of Brouwer’s invariance of domain theorem, which we will discuss in later notes (see also this blog post). (On the other hand, it is an easy consequence of the rank-nullity theorem that asmoothmanifold can have at most one dimension, without the need to invoke invariance of domain; we leave this as an exercise.)

Definition 4 (Lie group)ALie groupis a group which is also a smooth manifold, such that the group operations and are smooth maps. (Note that the Cartesian product of two smooth manifolds can be given the structure of a smooth manifold in the obvious manner.) We will also use additive notation to describe some Lie groups, but only in the case when the Lie group is abelian.

Remark 3In some literature, Lie groups are required to be connected (and occasionally, are even required to be simply connected), but we will not adopt this convention here. One can also define infinite-dimensional Lie groups, but in this course all Lie groups are understood to be finite dimensional.

Example 1Every group can be viewed as a Lie group if given the discrete topology (and the discrete smooth structure). (Note that we are not requiring Lie groups to be connected.)

Example 2Finite-dimensional vector spaces such as are (additive) Lie groups, as are sublattices such as or quotients such as . However, non-closed subgroups such as are not manifolds (at least with the topology induced from ) and are thus not Lie groups; similarly, quotients such as are not Lie groups either (they are not even Hausdorff). Also, infinite-dimensional topological vector spaces (such as with the product topology) will not be Lie groups.

Example 3The general linear group of invertible complex matrices is a Lie group. A theorem of Cartan (which we will prove in later notes) asserts that any closed subgroup of a Lie group is a smooth submanifold of that Lie group and is in particular also a Lie group. In particular, closed linear groups (i.e. closed subgroups of a general linear group) are Lie groups; examples include the real general linear group , the unitary group , the special unitary group , the orthogonal group , the special orthogonal group , and the Heisenberg groupof unipotent upper triangular real matrices. Many Lie groups are isomorphic to closed linear groups; for instance, the additive group can be identified with the closed linear group

the circle can be identified with (or ), and so forth. However, not all Lie groups are isomorphic to closed linear groups. A somewhat trivial example is that of a discrete group with cardinality larger than the continuum, which is simply too large to fit inside any linear group. A less pathological example is provided by the Weil-Heisenberg group

which is isomorphic the image of the Heisenberg group under the Weil representation, or equivalently the group of isometries of generated by translations and modulations. Despite this, though, it is helpful to think of closed linear groups and Lie groups as being almost the same concept as a first approximation. For instance, one can show using Ado’s theorem that every Lie group is

locallyisomorphic to a linearlocalgroup (we will discuss local groups later in this course, and see also this post).An important subclass of the closed linear groups are the linear algebraic groups, in which the group is also a real or complex algebraic variety (or at least an algebraically constructible set). All of the examples of closed linear groups given above are linear algebraic groups, although there exist closed linear groups that are not isomorphic to any algebraic group; see this post.

Hilbert’s fifth problem, like many of Hilbert’s problems, does not have a unique interpretation, but one of the most commonly accepted interpretations of the question posed by Hilbert is to determine if the requirement of smoothness in the definition of a Lie group is redundant. (There is also an analogue of Hilbert’s fifth problem for group *actions*, known as the Hilbert-Smith conjecture, which was discussed at this blog post.) To answer this question, we need to relax the notion of a Lie group to that of a topological group.

Definition 5 (Topological group)Atopological groupis a group that is also a topological space, in such a way that the group operations and are continuous. (As before, we also consider additive topological groups provided that they are abelian.)

Clearly, every Lie group is a topological group if one simply forgets the smooth structure. Furthermore, such topological groups remain locally Euclidean. It was established by Montgomery-Zippin and Gleason in 1952 that the converse statement holds, thus solving at least one formulation of Hilbert’s fifth problem:

Theorem 6 (Hilbert’s fifth problem)Let be an object with the following properties:

- (Group-like object) is a topological group.
- (Weak regularity) is locally Euclidean.
Then

- (Lie-type structure) is isomorphic to a Lie group.

Exercise 5Show that a locally Euclidean topological group is necessarily Hausdorff (without invoking Theorem 6).

As it turns out, Theorem 6 is not directly useful for many applications, because it is often difficult to verify that a given topological group is locally Euclidean. On the other hand, the weaker property of local compactness, which is clearly implied by the locally Euclidean property, is much easier to verify in practice. One can then ask the more general question of whether every locally compact group is isomorphic to a Lie group. Unfortunately, the answer to this question is easily seen to be no, as the following examples show:

Example 4 (Trivial topology)A group equipped with the trivial topology is a compact (hence locally compact) group, but will not be Hausdorff (and thus not Lie) unless the group is also trivial. Of course, this is a rather degenerate counterexample and can be easily eliminated in practice. For instance, we will see later that any topological group can be made Hausdorff by quotienting out the closure of the identity.

Example 5 (Infinite-dimensional torus)The infinite-dimensional torus (with the product topology) is an (additive) topological group, which is compact (and thus locally compact) by Tychonoff’s theorem. However, it is not a Lie group.

Example 6 (-adics)Let be a prime. We define the -adic norm on the integers by defining , where is the largest power of that divides (with the convention ). This is easily verified to generate a metric (and even an ultrametric) on ; the -adic integers are then defined as the metric completion of under this metric. This is easily seen to be a compact (hence locally compact) additive group (topologically, it is homeomorphic to a Cantor set). However, it is not locally Euclidean (or even locally connected), and so is not isomorphic to a Lie group.One can also extend the -adic norm to the ring of rationals of the form for some integers in the obvious manner; the metric completion of this space is then the -adic rationals . This is now a locally compact additive group rather than a compact one ( is a compact open neighbourhood of the identity); it is still not locally connected, so it is still not a Lie group.

One can also define algebraic groups such as over the -adic rationals ; thus for instance is the group of invertible matrices with entries in the -adics. This is still a locally compact group, and is certainly not Lie.

Exercise 6 (Solenoid)Let be a prime. Let be the solenoid group , where is the diagonally embedded copy of the integers in . (Topologically, can be viewed as the set after identifying with for all .) Show that is a compact additive group that is connected but not locally connected (and thus not a Lie group). Thus one cannot eliminate -adic type behaviour from locally compact groups simply by restricting attention to the connected case (although we will see later that one can do so by restricting to thelocallyconnected case).

We have now seen several examples of locally compact groups that are not Lie groups. However, all of these examples are “almost” Lie groups in that they can be turned into Lie groups by quotienting out a small compact normal subgroup. (It is easy to see that the quotient of a locally compact group by a compact normal subgroup is again a locally compact group.) For instance, a group with the trivial topology becomes Lie after quotienting out the entire group (which is “small” in the sense that it is contained in every open neighbourhood of the origin). The infinite-dimensional torus can be quotiented into a finite-dimensional torus (which is of course a Lie group) by quotienting out the compact subgroup ; note from the definition of the product topology that these compact subgroups shrink to zero in the sense that every neighbourhood of the group identity contains at least one (and in fact all but finitely many) of these subgroups. Similarly, with the -adic group , one can quotient out by the compact (and open) subgroups (which also shrink to zero, as discussed above) to obtain the cyclic groups , which are discrete and thus Lie. Quotienting out by the same compact open subgroups also leads to discrete (hence Lie) quotients; similarly for algebraic groups defined over , such as . Finally, with the solenoid group , one can quotient out the copy of in for (which are another sequence of compact subgroups shrinking to zero) to obtain the quotient group , which is isomorphic to a (highly twisted) circle and is thus Lie.

Inspired by these examples, we might be led to the following conjecture: if is a locally compact group, and is a neighbourhood of the identity, then there exists a compact normal subgroup of contained in such that is a Lie group. In the event that is Hausdorff, this is equivalent to asserting that is the projective limit (or *inverse limit*) of Lie groups.

This conjecture is true in several cases; for instance, one can show using the Peter-Weyl theorem (which we will discuss later in this course) that it is true for compact groups, and we will later see that it is also true for connected locally compact groups. However, it is not quite true in general, as the following example shows.

Exercise 7Let be a prime, and let be the automorphism . Let be the semidirect product of and twisted by ; more precisely, is the Cartesian product with the product topology and the group lawShow that is a locally compact group which is not isomorphic to a Lie group, and that is an open neighbourhood of the identity that contains no non-trivial normal subgroups of . Conclude that the conjecture stated above is false.

The difficulty in the above example was that it was not easy to keep a subgroup normal with respect to the entire group . Note however that contains a “large” (and more precisely, *open*) subgroup which *is* the projective limit of Lie groups. So the above examples do not rule out that the conjecture can still be salvaged if one passes from a group to an open subgroup . This is indeed the case:

Theorem 7 (Gleason-Yamabe theorem)Let obey the following hypotheses:

- (Group-like object) is a topological group.
- (Weak regularity) is locally compact.
Then for every open neighbourhood of the identity, there exists a subgroup of and a compact normal subgroup of with the following properties:

- ( is close to ) is an open subgroup of , and is contained in .
- (Lie-type structure) is isomorphic to a Lie group.

We will spend several lectures proving this theorem (due to Gleason and to Yamabe). As stated, may depend on , but one can in fact take the open subgroup to be uniform in the choice of ; we will show this in later notes. Theorem 6 can in fact be deduced from Theorem 7 and some topological arguments involving the invariance of domain theorem; we will see this later in this course (or see this previous blog post).

The Gleason-Yamabe theorem asserts that locally compact groups are “essentially” Lie groups, after ignoring the very large scales (by restricting to an open subgroup) and also ignoring the very small scales (by allowing one to quotient out by a small group). In special cases, the conclusion of the theorem can be simplified. For instance, it is easy to see that an open subgroup of a topological group is also closed (since the complement is a union of cosets of ), and so if is connected, there are no open subgroups other than itself. Thus, in the connected case of Theorem 7, one can take . In a similar spirit, if has the no small subgroups (NSS) property, that is to say that there exists an open neighbourhood of the identity that contains no non-trivial subgroups of , then we can take to be trivial. Thus, as a special case of the Gleason-Yamabe theorem, we see that all connected NSS locally compact groups are Lie; in fact it is not difficult to then conclude that any locally compact NSS group (regardless of connectedness) is Lie. Conversely, this claim turns out to be a key step in the *proof* of Theorem 7, as we shall see later. (It is also not difficult to show that all Lie groups are NSS, as we shall see in the next set of notes.)

The proof of the Gleason-Yamabe theorem (as well as consequences, such as Theorem 6) will occupy a significant fraction of this course. The proof proceeds in a somewhat lengthy series of steps in which the initial regularity (local compactness) on the group is gradually upgraded to increasingly stronger regularity (e.g. metrisability, the NSS property, or the locally Euclidean property) until one eventually obtains Lie structure. A key turning point in the argument will be the construction of a metric (which we call a *Gleason metric*) on (a large portion of) which obeys a commutator estimate similar to (2).

While the Gleason-Yamabe theorem does not completely classify all locally compact groups (as mentioned earlier, it primarily controls the medium-scale behaviour, and not the very fine-scale or very coarse-scale behaviour, of such groups), it is still powerful enough for a number of applications, to which we now turn.

** — 2. Approximate groups — **

Now we turn to what appears at first glance to be an unrelated topic, namely that of additive combinatorics (and its non-commutative counterpart, multiplicative combinatorics). One of the main objects of study in either additive or multiplicative combinatorics are *approximate groups* – sets (typically finite) contained in an additive or multiplicative ambient group that are “almost groups” in the sense that they are “almost” closed under either addition or multiplication. (One can also consider abstract approximate groups that are not contained in an ambient genuine group, but we will not do so here.)

There are several ways to quantify what it means for a set to be “almost” closed under addition or multiplication. Here are some common formulations of this idea (phrased in multiplicative notation, for sake of concreteness):

- (Statistical multiplicative structure) For a “large” proportion of pairs , the product also lies in .
- (Small product set) The “size” of the product set is “comparable” to the “size” of the original set . (For technical reasons, one sometimes uses the triple product instead of the double product.)
- (Covering property) The product set can be covered by a “bounded” number of (left or right) translates of the original set .

Of course, to make these notions precise one would have to precisely quantify the various terms in quotes. Fortunately, the basic theory of additive combinatorics (and multiplicative combinatorics) can be used to show that all these different notions of additive or multiplicative structure are “essentially” equivalent; see Chapter 2 of my book with Van Vu (or this paper of mine in the non-commutative case) for more discussion.

For the purposes of this course, it will be convenient to focus on the use of covering to describe approximate multiplicative structure. More precisely:

Definition 8 (Approximate groups)Let be a multiplicative group, and let be a real number. A-approximate subgroupof , or-approximate groupfor short, is a subset of which contains the identity, is symmetric (thus is equal to ) and is such that can be covered by at most left-translates (or equivalently by symmetry, right translates) of , thus there exists a subset of of cardinality at most such that .

In most combinatorial applications, one only considers approximate groups that are finite sets, but one could certainly also consider countably or uncountably infinite approximate groups also.

Example 7A -approximate subgroup of is the same thing as a genuine subgroup of .

Example 8In the additive group of the integers , the symmetric arithmetic progression is a -approximate group for any . More generally, in any additive group , thesymmetric generalised arithmetic progressionwith and , is a -approximate group.

Exercise 8Let be a convex symmetric subset of . Show that is a -approximate group. (Hint: greedily pack with disjoint translates of .)

Example 9If is an open precompact symmetric neighbourhood of the identity in a locally compact group , then is a -approximate group for some finite . Thus we see some connection between locally compact groups and approximate groups; we will see a deeper connection involving ultraproducts in later notes.

Example 10Let be a -dimensional Lie group. Then is a smooth manifold, and can thus be (non-uniquely) given the structure of a Riemannian manifold. If one does so, then for sufficiently small radii , the ball around the identity will be a -approximate group.

Example 11 (Extensions)Let be a surjective group homomorphism (thus is agroup extensionof by the kernel of ). If is a -approximate subgroup of , then is a -approximate subgroup of . One can think of as an extension of the approximate group by .

The classification of approximate groups is of importance in additive combinatorics, and has connections with number theory, geometric group theory, and the theory of expander graphs. One can ask for a quantitative classification, in which one has explicit dependence of constants on the approximate group parameter , or one can settle for a qualitative classification in which one does not attempt to control this dependence of constants. In this course we will focus on the latter question, as this allows us to bring in qualitative tools such as the Gleason-Yamabe theorem to bear on the problem.

In the abelian case when the ambient group is additive, approximate groups are classified by *Freiman’s theorem for abelian groups*, which was established by Green and Ruzsa. (Freiman himself obtained an analogous classification in the case when was a torsion-free abelian group, such as the integers .) As before, we phrase this theorem in a slightly stilted fashion (and in a qualitative, rather than quantitative, manner) in order to demonstrate its alignment with the general principles stated in the introduction.

Theorem 9 (Freiman’s theorem in an abelian group)Let be an object with the following properties:

- (Group-like object) is a subset of an additive group .
- (Weak regularity) is a -approximate group.
- (Discreteness) is finite.
Then there exists a finite subgroup of , and a subset of , with the following properties:

- ( is close to ) is contained in , where is the quotient map, and .
- (Nilpotent type structure) is a symmetric generalised arithmetic progression of rank (see Example 8).

Informally, this theorem asserts that in the abelian setting, discrete approximate groups are essentially bounded rank symmetric generalised arithmetic progressions, extended by finite groups (such extensions are also known as *coset progressions*). The theorem has a simpler conclusion (and is simpler to prove) in the case when is a torsion-free abelian group (such as ), since in this case is trivial.

We will not discuss Green and Ruzsa’s proof of Theorem 9 here, save to say that it relies heavily on Fourier-analytic methods, and as such, does not seem to easily extend to a general non-abelian setting. To state the non-abelian analogue of Theorem 9, one needs multiplicative analogues of the concept of a generalised arithmetic progression. An ordinary (symmetric) arithmetic progression has an obvious multiplicative analogue, namely a (symmetric) geometric progression for some generator . In a similar vein, if one has *commuting* generators and some dimensions , one can form a symmetric generalised geometric progression

which will still be an -approximate group. However, if the do not commute, then the set defined in (3) is not quite the right concept to use here; for instance, there it is no reason for to be symmetric. However, it can be modified as follows:

Definition 10 (Noncommutative progression)Let be elements of a (not necessarily abelian) group , and let . We define thenoncommutative progressionof rank with generators and dimensions to be the collection of all words composed using the alphabet , such that for each , the total number of occurrences of and combined in is at most .

Example 12consists of the elementswhere each occurrence of can independently be set to or .

Example 13If the commute, then the noncommutative progression simplifies to (3).

Exercise 9Let be the discrete Heisenberg groupbe the two generators of . Let be a sufficiently large natural number. Show that the noncommutative progression contains all the group elements of with and for a sufficiently small absolute constant ; conversely, show that all elements of are of the form with and for some sufficiently large absolute constant . Thus, informally, we have

It is clear that noncommutative progressions are symmetric and contain the identity. However, if the do not have any commutative properties, then the size of these progressions can grow exponentially in and will not be approximate groups with any reasonable parameter . However, the situation changes when the generate a nilpotent group:

Proposition 11Suppose that generate a nilpotent group of step , and suppose that are all sufficiently large depending on . Then is an -approximate group.

We will prove this proposition later in this course (when we review the properties of nilpotent groups).

We can now state the noncommutative analogue of Theorem 9:

Theorem 12 (Freiman’s theorem in an arbitrary group)Let be an object with the following properties:

- (Group-like object) is a subset of an multiplicative group .
- (Weak regularity) is a -approximate group.
- (Discreteness) is finite.
Then there exists a finite subgroup of , and a subset of (where is the normaliser of ), with the following properties:

- ( is close to ) is contained in , where is the quotient map, and .
- (Nilpotent type structure) is a noncommutative progression of rank , whose generators generate a nilpotent group of step .

The proof of this theorem (which is forthcoming work of Emmanuel Breuillard, Ben Green, Tom Sanders and myself, building upon earlier work of Hrushovski) relies on the Gleason-Yamabe theorem. The key connection will take some time to explain properly, but roughly speaking, it comes from the fact that the ultraproduct of a sequence of -approximate groups can be used to generate a locally compact group, to which the Gleason-Yamabe theorem can be applied. This in turn can be used to place a metric on approximate groups that obeys a commutator estimate similar to (2), which allows one to run an argument similar to that used to prove Theorem 2.

** — 3. Gromov’s theorem — **

The final topic of this course will be Gromov’s theorem on groups of polynomial growth. This theorem is analogous to Theorem 7 or Theorem 12, but in the category of *finitely generated groups* rather than locally compact groups or approximate groups.

Let be a group that is generated by a finite set of generators; for notational simplicity we will assume that is symmetric and contains the origin. Then defines a (right-invariant) word metric on , defined by setting for to be the least natural number such that . One easily verifies that this is indeed a metric that is right-invariant (thus for all ). Geometrically, this metric describes the geometry of the Cayley graph on formed by connecting to for each and . (See this previous post for more discussion of using Cayley graphs to study groups geometrically.)

Let us now consider the growth of the balls as . On the one hand, we have the trivial upper bound

that shows that such balls can grow at most exponentially. And for “typical” non-abelian groups, this exponential growth actually occurs; consider the case for instance when consists of the generators of a free group (together with their inverses, and the group identity). However, there are some groups for which the balls grow at a much slower rate. A somewhat trivial example is that of a finite group , since clearly will top out at (when reaches the diameter of the Cayley graph) and stop growing after that point. Another key example is the abelian case:

Exercise 10If is an abelian group generated by a finite symmetric set containing the identity, show thatIn particular, grows at a polynomial rate in .

Let us say that a finitely group is a *group of polynomial growth* if one has for all and some constants .

Exercise 11Show that the notion of a group of polynomial growth (as well as the rate of growth) does not depend on the choice of generators ; thus if is another set of generators for , show that has polynomial growth with respect to with rate if and only if it has polynomial growth with respect to with rate .

Exercise 12Let be a finitely generated group, and let be a finite index subgroup of .

- Show that is also finitely generated. (
Hint:Let be a symmetric set of generators for containing the identity, and locate a finite integer such that . Then show that the set is such that . Conclude that meets every coset of (or equivalently that ), and use this to show that generates .)- Show that has polynomial growth if and only if has polynomial growth.
- More generally, show that any finitely generated subgroup of a group of polynomial growth also has polynomial growth. Conclude in particular that a group of polynomial growth cannot contain the free group on two generators.

From Exercise 9 we see that the discrete Heisenberg group (4) is of polynomial growth. It is in fact not difficult to show that more generally, any nilpotent finitely generated group is of polynomial growth. By Exercise 12, this implies that any virtually nilpotent finitely generated group is of polynomial growth.

Gromov’s theorem asserts the converse statement:

Theorem 13 (Gromov’s theorem)Let be an object with the following properties:

- (Group-like object) is a finitely generated group.
- (Weak regularity) is of polynomial growth.
Then there exists a subgroup of such that

- ( is close to ) The index is finite.
- (Nilpotent type structure) is nilpotent.

More succinctly: a finitely generated group is of polynomial growth if and only if it is virtually nilpotent.

Groups of polynomial growth are related to approximate groups by the following observation.

Exercise 13 (Pigeonhole principle)Let be a finitely generated group, and let be a symmetric set of generators for containing the identity.

- Show that there exists a such that for a sequence of radii going to infinity.
- Show that there exists a such that is a -approximate group for a sequence of radii going to infinity. (
Hint:Argue as in Exercise 8.)

In later notes we will use this connection to deduce Theorem 13 from Theorem 12. From a historical perspective, this was not the first proof of Gromov’s theorem; Gromov’s original proof relied instead on a variant of Theorem 6 (as did some subsequent variants of Gromov’s argument, such as the nonstandard analysis variant of van den Dries and Wilkie), and a subsequent proof of Kleiner went by a rather different route, based on earlier work of Colding and Minicozzi on harmonic functions of polynomial growth. (This latter proof is discussed in these previous blog posts.) The proof we will give in these notes is more recent, based on an argument of Hrushovski. We remark that the strategy used to prove Theorem 12 – namely taking an ultralimit of a sequence of approximate groups – also appears in Gromov’s original argument (strictly speaking, he uses Gromov-Hausdorff limits instead of ultralimits, but the two types of limits are closely related). We will discuss these sorts of limits later in the course, but perhaps an intuitive model to keep in mind is the following: if one takes a discrete group (such as ) and rescales it (say to for a large parameter ), then intuitively this rescaled group “converges” to a continuous group (in this case ). More generally, one can generate locally compact groups (or at least locally compact spaces) out of the limits of (suitably normalised) groups of polynomial growth or approximate groups, which is one of the basic observations that tie the three different topics discussed above together.

As we shall see in later notes, finitely generated groups arise naturally as the fundamental groups of compact manifolds. Using the tools of Riemannian geometry (such as the Bishop-Gromov inequality), one can relate the growth of such groups to the curvature of a metric on such a manifold. As a consequence, Gromov’s theorem and its variants can lead to some non-trivial conclusions about the relationship between the topology of a manifold and its geometry. The following simple consequence is typical:

Proposition 14Let be a compact Riemannian manifold of non-negative Ricci curvature. Then the fundamental group of is virtually nilpotent.

We will discuss this result and some related results (such as a relaxation of the non-negative curvature hypothesis to an almost non-negative curvature hypothesis) in later notes. We also remark that the above proposition can also be proven (with stronger conclusions) by more geometric means, but there are some results of the above type which currently have no known proof that does not employ some version of Gromov’s theorem at some point.

## 30 comments

Comments feed for this article

28 August, 2011 at 1:42 am

Principles: randomness/structure or emergent from a common cause? | chorasimilarity[…] Terence Tao presented a sketch of his project relating Hilbert’ fifth problem and approximate groups. For me the most interesting part is his Theorem 12 and its relation with Gromov’ theorem on […]

28 August, 2011 at 4:32 am

AnonymousWhen I read this sentence in remark2,

” (non-empty) topological manifold can have at most one dimension”

I think “Are all the non-empty topological manifolds, lines?”

[Clarified, thanks = T.]28 August, 2011 at 8:41 am

Fred LunnonText apparently missing preceding Theorem 13, between

“(when {R} reaches the”

and

“finitely generated group is of polynomial growth.”

Also in following, after

“The proof we will give in these notes is more recent, based on an”

WFL

[Corrected, thanks -T.]28 August, 2011 at 6:37 pm

KLMTerry, how much do you have to spend typing all these? Do you still have time doing research after these expository writing? It is amazing how much you can do in 24hrs.

30 August, 2011 at 6:33 am

Baker-Campbell-Hausdorff polynomials and Menelaus theorem | chorasimilarity[…] will apply sometimes in the future to real combinatorial problems, like the Tao’ project presented here, and also to the problem of understanding curvature (in non-riemannian settings), see a hint here, […]

1 September, 2011 at 6:15 pm

254A, Notes 1: Lie groups, Lie algebras, and the Baker-Campbell-Hausdorff formula « What’s new[…] can be defined efficiently by modifying definition (iv) above, and which was already discussed in the previous set of notes. It is however difficult to use this definition for abstract Lie algebras and Lie groups. The […]

7 September, 2011 at 5:01 am

Weekly Picks « Mathblogging.org — the Blog[…] on the compactness theorem, n-Category Café on Hadwiger’s theorem, Terry Tao starting a series of posts on Hilbert’s fifth problem, and Vismath (in German, translation) and 0xDE on […]

20 September, 2011 at 8:06 am

More on Hilbert’s tenth problem | cartesian product[…] 254A, Notes 0 – Hilbert’s fifth problem and related topics (terrytao.wordpress.com) […]

22 September, 2011 at 11:15 am

Vitali KapovitchProposition 14 is stated incorrectly. The Ricci curvature should be nonnegative rather than nonpositive. Also, you really want to state it for almost nonnegative Ricci curvature rather than for nonnegative Ricci curvature because for nonnegative Ricci curvature the result follows directly from Gromov’s polynomial growth theorem and relative volume comparison. Moreover, compact manifolds of nonnegative Ricci curvature are known to split in a finite cover as a torus times a simply connected manifold by an old result of Cheeger and Gromoll (it’s an easy consequence of the splitting theorem). In particular, their fundamental groups are virtually abelian, not just virtually nilpotent.

[Corrected, thanks. I plan to give a more detailed discussion of the type of geometric consequences of Gromov-type theorems in a later post, with only a brief mention to give the flavour in this introductory post. -T.]26 September, 2011 at 5:03 pm

alingalatanIs it Jordan’s Theorem still true if we replace “finite G” by “every element has finite order, and orders are bounded”?

Because I think that in this case, we can choose an element with minimal distance to 1, as all the possible values for the norm are of the form for n=0,1,…,N and , so they are finite. (where N is the bound for the orders.)

Am I right?

26 September, 2011 at 5:20 pm

Terence TaoI think this works in the unitary case (Theorem 2), but it is not immediately obvious to me that it extends to the general linear case (Exercise 3). (Your hypothesis implies discreteness of the group, which gives finiteness in the unitary case by compactness.)

26 September, 2011 at 5:24 pm

alingalatanIndeed, I didn’t realize that my hypothesis implies finiteness in the unitary case. Thank you.

4 October, 2011 at 8:43 pm

Kevin VentulloDear Alin,

Two things:

1. Your hypothesis implies finiteness in the general linear case: it is a theorem due to Burnside that any subgroup of GLn consisting of elements of bounded order must be finite.

2. Jordan’s theorem actually holds without requiring that the orders of elements be bounded. This theorem is due to Schur, who proved along the way that any such group is conjugate to a unitary group of transformations. See http://en.wikipedia.org/wiki/Jordan%E2%80%93Schur_theorem

-Kevin

27 September, 2011 at 3:30 pm

254A, Notes 3: Haar measure and the Peter-Weyl theorem « What’s new[…] groups after taking inverse limits; consider for instance the solenoid example (Exercise 6 from Notes 0). Share this:PrintEmailMoreDiggTwitterFacebookRedditStumbleUponLike this:LikeBe the first to like […]

29 September, 2011 at 12:01 pm

Nick CookAs we noted in class yesterday, in Example 8 {-N,…,N} is (more specifically) a 2-approximate subgroup of the integers.

[Corrected, thanks – T.]30 September, 2011 at 1:37 pm

alingalatanI have some questions:

1) Is there an analog version of Gromov’s thm. for locally compact groups? I was thinking at something like: If a lc. group G is compactly generated by K, and the measure of K^n grows polynomial in n, does G contain a cocompact nilpotent subgroup? (or something similar?)

2) In the view of Exercise 2, if G is a group with some Borel structure such that multiplication and the inverse functions are Borel, do we get that G is actually a topological group? Or, are measurable morphisms actually continuous?

30 September, 2011 at 1:47 pm

Terence Tao(1) is a great question; I’d say the answer is probably yes, but it is not currently in the literature. Many of the existing proofs of Gromov’s theorem rely at some point or another on the discreteness of the problem, but Gromov’s original argument may possibly be the one with the weakest such reliance. Another possibility (which would be worth exploring in any event) would be to develop a structure theorem for continuous approximate groups along the lines of Theorem 12, which would probably also settle this question. I may pass this question on to one of my graduate students who is looking into these sorts of matters.

(2) Hmm, another good question. Certainly if one places the “wrong” topological structure then the answer is no, e.g. R with the half-open topology has group operations that are Borel but not continuous. But perhaps a measurable group can, under some conditions, be equipped with a natural topology that makes it continuous. For instance, in a compact group G with Haar measure mu, the group G is isomorphic to its image in U(L^2(G)) under the regular representation with the strong operator topology. This suggests for a measurable group equipped with a Haar probability measure to again use the regular representation with the strong operator topology to define the topology on G. I don’t know if this would work in the case when the Haar measure is infinite, though (and also I don’t know how to construct the Haar measure in general without first having a topology).

3 October, 2011 at 4:34 pm

Ben HayesIf G is a standard Borel group which has a Haar measure, then G is Borel isomorphic to a locally compact group, this is known as Weil’s Theorem. I believe this is proved as you said, using the strong operator topology on the left-regular representation of G. Certainly, if G does not have a Haar measure this is false. Take, e.g. a non locally compact Polish group, like U(H) with H a separable infinite dimensional Hilbert space.

3 October, 2011 at 4:38 pm

alingalatanAlso, it seems that the first question also has an answer:

Losert, V, On the structure of groups with polynomial growth II J. London Math. Soc. (2) 63 (2001), no. 3, 640?654.

4 October, 2011 at 2:56 pm

254A, Notes 4: Building metrics on groups, and the Gleason-Yamabe theorem « What’s new[…] this set of notes we will be able to finally prove the Gleason-Yamabe theorem from Notes 0, which we restate here: Theorem 1 (Gleason-Yamabe theorem) Let be a locally compact group. Then, […]

5 October, 2011 at 3:36 pm

The Jordan-Schur theorem « What’s new[…] recently learned (from this comment of Kevin Ventullo) that the finiteness hypothesis on the group in this theorem can be relaxed to […]

8 October, 2011 at 12:58 pm

254A, Notes 5: The structure of locally compact groups, and Hilbert’s fifth problem « What’s new[…] now establish Theorem 5. Let be a locally Euclidean group. By Exercise 5 of Notes 0, is Hausdorff; it is also locally compact and first countable. Thus, by Exercise 4, such a group […]

24 October, 2011 at 6:46 pm

The structure of approximate groups « What’s new[…] to Pub. IHES. We had announced the main results of this paper in various forums (including this blog) for a few months now, but it had taken some time to fully write up the paper and put in various […]

6 November, 2011 at 9:22 am

254A, Notes 8: The microstructure of approximate groups « What’s new[…] to the identity in some suitable metric (cf. the proof of Jordan’s theorem from Notes 0) would be an element associated to the microscopic scale. The orbit starts out at microscopic […]

13 November, 2011 at 5:20 pm

254A, Notes 9: Applications of the structural theory of approximate groups « What’s new[…] 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”) […]

5 February, 2012 at 11:33 am

254B, Notes 5: Product theorems, pivot arguments, and the Larsen-Pink non-concentration inequality « What’s new[…] subgroup of for some , a bounded index subgroup of is abelian. (Jordan’s theorem was discussed further in last quarter’s course.) The finite characteristic case is inherently more complicated though (due in large part to the […]

17 March, 2012 at 9:12 pm

254A, addendum: Some notes on nilprogressions « What’s new[…] (as was done similarly for several other sets of lecture notes on this blog). When reviewing the zeroth set of notes in particular, I found that I had made a claim (Proposition 11 from those notes) which asserted, […]

9 November, 2013 at 1:23 pm

FanIn exercise 6, is (x + 1, 0) identified with (x, 1), or (x + 1, 1) identified with (x, 0)?

[Oops, that was a typo; corrected, thanks – T.]18 April, 2015 at 1:35 am

JialunIn the proof of theorem 2, the $\epsilon$ depends on d, what is $d$? And it is not clear that $O_{n,\epsilon}(1)$ only depends on n.

18 April, 2015 at 6:40 am

JialunIt’s clear, and is just a typo, .

[Corrected, thanks – T.]