In the previous set of notes, we introduced the notion of an *ultra approximate group* – an ultraproduct of finite -approximate groups for some independent of , where each -approximate group may lie in a distinct ambient group . Although these objects arise initially from the “finitary” objects , it turns out that ultra approximate groups can be profitably analysed by means of *infinitary* groups (and in particular, locally compact groups or Lie groups ), by means of certain *models* of (or of the group generated by ). We will define precisely what we mean by a model later, but as a first approximation one can view a model as a representation of the ultra approximate group (or of ) that is “macroscopically faithful” in that it accurately describes the “large scale” behaviour of (or equivalently, that the kernel of the representation is “microscopic” in some sense). In the next section we will see how one can use “Gleason lemma” technology to convert this macroscopic control of an ultra approximate group into microscopic control, which will be the key to classifying approximate groups.

Models of ultra approximate groups can be viewed as the multiplicative combinatorics analogue of the more well known concept of an ultralimit of metric spaces, which we briefly review below the fold as motivation.

The crucial observation is that ultra approximate groups enjoy a *local compactness* property which allows them to be usefully modeled by locally compact groups (and hence, through the Gleason-Yamabe theorem from previous notes, by Lie groups also). As per the Heine-Borel theorem, the local compactness will come from a combination of a completeness property and a local total boundedness property. The completeness property turns out to be a direct consequence of the countable saturation property of ultraproducts, thus illustrating one of the key advantages of the ultraproduct setting. The local total boundedness property is more interesting. Roughly speaking, it asserts that “large bounded sets” (such as or ) can be covered by finitely many translates of “small bounded sets” , where “small” is a topological group sense, implying in particular that large powers of lie inside a set such as or . The easiest way to obtain such a property comes from the following lemma of Sanders:

Lemma 1 (Sanders lemma)Let be a finite -approximate group in a (global) group , and let . Then there exists a symmetric subset of with containing the identity such that .

This lemma has an elementary combinatorial proof, and is the key to endowing an ultra approximate group with locally compact structure. There is also a closely related lemma of Croot and Sisask which can achieve similar results, and which will also be discussed below. (The locally compact structure can also be established more abstractly using the much more general methods of definability theory, as was first done by Hrushovski, but we will not discuss this approach here.)

By combining the locally compact structure of ultra approximate groups with the Gleason-Yamabe theorem, one ends up being able to model a large “ultra approximate subgroup” of by a Lie group . Such Lie models serve a number of important purposes in the structure theory of approximate groups. Firstly, as all Lie groups have a dimension which is a natural number, they allow one to assign a natural number “dimension” to ultra approximate groups, which opens up the ability to perform “induction on dimension” arguments. Secondly, Lie groups have an *escape property* (which is in fact equivalent to no small subgroups property): if a group element lies outside of a very small ball , then some power of it will escape a somewhat larger ball . Or equivalently: if a long orbit lies inside the larger ball , one can deduce that the original element lies inside the small ball . Because all Lie groups have this property, we will be able to show that all ultra approximate groups “essentially” have a similar property, in that they are “controlled” by a nearby ultra approximate group which obeys a number of escape-type properties analogous to those enjoyed by small balls in a Lie group, and which we will call a *strong ultra approximate group*. This will be discussed in the next set of notes, where we will also see how these escape-type properties can be exploited to create a metric structure on strong approximate groups analogous to the Gleason metrics studied in previous notes, which can in turn be exploited (together with an induction on dimension argument) to fully classify such approximate groups (in the finite case, at least).

There are some cases where the analysis is particularly simple. For instance, in the bounded torsion case, one can show that the associated Lie model is necessarily zero-dimensional, which allows for a easy classification of approximate groups of bounded torsion.

Some of the material here is drawn from my recent paper with Ben Green and Emmanuel Breuillard, which is in turn inspired by a previous paper of Hrushovski.

** — 1. Ultralimits of metric spaces (Optional) — **

Suppose one has a sequence of metric spaces. Intuitively, there should be a sense in which such a sequence can (in certain circumstances) “converge” to a limit that is another metric space. Some informal examples of this intuition:

- (i) The sets (with the usual metric) should “converge” as to the integers (with the usual metric).
- (ii) The cyclic groups (with the “discrete” metric ) should also “converge” as to the integers (with the usual metric).
- (iii) The sets (with the usual metric) should “converge” as to the interval (with the usual metric).
- (iv) The cyclic groups (with the “bounded” metric ) should “converge” as to the unit circle (with the usual metric).
- (v) A Euclidean circle of radius (such as ) should “converge” as to a Euclidean line (such as ).
Let us now try to formalise this intuition, proceeding in stages. The first attempt to formalise the above concepts is via the Hausdoff distance, which already made an appearance in Notes 4:

**Definition 2 (Hausdorff distance)**Let be a metric space. The*Hausdorff distance*between two non-empty subsets of is defined by the formulaThus, if , then every point in lies within a distance less than of a point in , and every point in lies within a distance less of a point in (thus and , where is the -neighbourhood of ); and conversely, if the latter claim holds, then .

This distance is always symmetric, non-negative, and obeys the triangle inequality. If one restricts attention to non-empty compact sets , then one easily verifies that if and only if , so that the Hausdorff distance becomes a metric. In particular, it becomes meaningful to discuss the concept of a sequence of non-empty compact subsets of converging in the Hausdorff distance to a (unique) limit non-empty compact set . Note that this concept captures the intuitive example (iii) given above, but not any of the others. Nevertheless, we will discuss it first as it is slightly simpler than the more general notions we will be using.

**Exercise 1 (Hausdorff convergence and connectedness)**Let be a sequence of non-empty compact subsets of a metric space converging to another non-empty compact set .- (i) If the are all connected, show that is connected also.
- (ii) If the are all path-connected, does this imply that is path-connected also? Support your answer with a proof or counterexample.
- (iii) If the are all disconnected, does this imply that is disconnected also? Support your answer with a proof or counterexample.

One of the key properties of Hausdorff distance in a compact set is that it is itself compact:

**Lemma 3 (Compactness of the Hausdorff metric)**Let be a sequence of compact subsets of a compact metric space . Then there is a subsequence of the that is convergent in the Hausdorff metric.The proof of this lemma was set as Exercise 13 of Notes 4. It can be proven by “conventional” means (relying in particular on the Heine-Borel theorem), but we will now sketch how one can establish this result using ultralimits instead. As in the previous set of notes, we fix a standard universe and a non-principal ultrafilter in order to define ultrapowers.

If is a (standard) metric space with metric , then the ultrapower comes with a “nonstandard metric” that extends . (In the previous notes, we referred to this metric as rather than , but here it will be convenient to use a different symbol for this extension of to reduce confusion.) Let us say that two elements of are

*infinitesimally close*if . (The set of points infinitesimally close to a standard point is sometimes known as the monad of , although we will not use this terminology.)**Exercise 2**Let be a (standard) compact metric space. Show that for any nonstandard point there exists a unique standard point which is infinitesimally close to , with**Exercise 3 (Automatic completeness)**Let be a (standard) compact metric space, and let be a nonstandard subset of (i.e. an ultraproduct of standard subsets of ), and let be the standard part function as defined in the previous exercise. Show that is complete (and thus compact, by the Heine-Borel theorem). (*Hint:*take advantage of the countable saturation property from the previous notes.)**Exercise 4**Let be a compact metric space, and let for be a sequence of non-empty compact subsets of . Write for the ultraproduct of the , and let be the standard part function as defined in the previous exercises. Show that is a non-empty compact subset of , and that . Use this to give an alternate proof of Lemma 3.One can extend some of the above theory from compact metric spaces to locally compact metric spaces.

**Exercise 5**Let be a (standard) locally compact metric space. Let denote the set of ultralimits of precompact sequences in .- Show that if and only if is compact.
- Show that there is a unique function such that is infinitesimally close to for all .
- If is a nonstandard subset of , show that is complete.
- Show that if is a compact set and is a (standard) real number, then and for all sufficiently close to .

Now we consider limits of metric spaces that are not necessarily all embedded in a single metric space. We begin by considering the case of bounded metric spaces.

**Definition 4 (Gromov-Hausdorff distance)**The*Gromov-Hausdorff distance*between two bounded metric spaces , is the infimum of the Hausdorff distance , ranging over all isometric embeddings , from respectively to .**Exercise 6**- (i) Show that Gromov-Hausdorff distance is a pseudometric (i.e. symmetric, non-negative, and obeys the triangle inequality). (
*Hint:*to show that , build a metric on the disjoint union which intuitively captures the idea of the shortest path from to via .) - (ii) If is a dense subset of a bounded metric space , show that . In particular, any bounded metric space is at a zero Gromov-Hausdorff distance from its metric completion .
- (iii) Show that if are compact metric spaces, then if and only if and are isometric. (
*Hint:*If , find a sequence of “approximate isometries” from to and from to which almost invert each other. Then adapt the Arzelá-Ascoli theorem to take a limit (or one can use ultralimits and standard parts).)

We say that a sequence of bounded metric spaces

*converges in the Gromov-Hausdorff sense*to another bounded metric space if one has as . This is a more general notion of convergence than Hausdorff convergence, and encompasses examples (iii) and (iv) at the beginning of this section.**Exercise 7**Show that every compact metric space is the limit (in the Gromov-Hausdorff sense) of finite metric spaces.Now we turn to an important compactness result about Gromov-Hausdorff convergence. We say that a sequence of metric spaces is

*uniformly totally bounded*if the diameters of the are bounded, and, for every , there exists such that each can be covered by at most balls of radius in the metric. (Of course, this implies that each is individually totally bounded.)**Proposition 5 (Uniformly total bounded spaces are Gromov-Hausdorff precompact)**Let be a sequence of uniformly totally bounded metric spaces. Then there exists a subsequence which converges in the Gromov-Hausdorff space to a compact limit .We will prove this proposition using ultrafilters. Let be a sequence of uniformly totally bounded metric spaces, which we will assume to be standard (by defining the standard universe in a suitable fashion). Then we can form the ultraproduct and the ultralimit , thus is a nonstandard metric (obeying the nonstandard symmetry, triangle inequality, and positivity properties). As the are uniformly bounded, has bounded range. If we then take the standard part of , then is a pseudometric on (i.e. it obeys all the axioms of a metric except possibly for positivity.) We can then construct a quotient metric space in the usual manner, by declaring two points in to be equivalent, , if (or equivalently if ). The pseudometric then descends to a genuine metric on . The space is known as a metric ultralimit (or

*ultralimit*for short) of the (note that this is a slightly different usage of the term “ultralimit” from what we have been using previously).One can easily establish compactness:

**Exercise 8 (Compactness)**- (i) Show that is totally bounded. (
*Hint:*use the uniform total boundedness of the together with Los’s theorem.) - (ii) Show that is complete. (
*Hint:*use countable saturation).

In particular, by the Heine-Borel theorem, is compact.

Now we establish Gromov-Hausdorff convergence, in the sense that for every standard , one has for all sufficiently close to . From this it is easy to extract a subsequence that converges in the Gromov-Hausdorff sense to as required.

Fix a standard . As is totally bounded, we can cover it by at most balls of radius (say) in the metric for some standard natural number . Lifting back to the ultraproduct , we conclude that we may cover by balls in the nonstandard metric .

Note that is the standard part of , and in particular

Each ball centre is an ultralimit of points in . By Los’s theorem, we conclude that for sufficiently close to , is covered by the balls in the metric , and

for all .

Because of this, we can embed both and in the disjoint union , with a metric extending the metrics on and , with the cross distances between points and defined by the formula

informally, this connects each ball center to its counterpart by a path of length . It is a routine matter to verify that is indeed a metric, and that and are separated by a Hausdorff distance less than in , and the claim follows.

**Exercise 9**Prove Proposition 5 without using ultrafilters.**Exercise 10 (Completeness)**Let be a sequence of bounded metric spaces which is Cauchy in the Gromov-Hausdorff sense (i.e. as ). Show that converges in the Gromov-Hausdorff sense to some limit .Now we generalise Gromov-Hausdorff convergence to the setting of unbounded metric spaces. To motivate the definition, let us first give an equivalent form of Gromov-Hausdorff convergence:

**Exercise 11**Let be a sequence of bounded metric spaces, and let be another bounded metric space. Show that the following are equivalent:- (i) converges in the Gromov-Hausdorff sense to .
- (ii) There exist maps which are asymptotically isometric isomorphisms in the sense that and as .

Define a

*pointed metric space*to be a triplet , where is a metric space and is a point in .**Definition 6 (Pointed Gromov-Hausdorff convergence)**A sequence of pointed metric spaces is said to*converge in the pointed Gromov-Hausdorff sense*to another pointed metric space if there exists a sequence of maps such that- as ;
- (Asymptotic isometry) For each , one has as ;
- (Asymptotic surjectivity) For each , one has as .

**Exercise 12**Verify that all the examples (i)-(v) given at the start of the section are examples of pointed Gromov-Hausdorff convergence, once one selects a suitable point in each space.The above definition is by no means the only definition of pointed Gromov-Hausdorff convergence. Here is another (which is basically the original definition of Gromov):

**Exercise 13**Let be a sequence of pointed metric spaces, and let be another pointed metric space. Show that the following are equivalent:- converges in the pointed Gromov-Hausdorff sense to .
- There exist metrics on the disjoint union extending the metrics such that for some sequence , one has , , and .

Using this equivalence, construct a pseudometric between pointed metric spaces that describes pointwise Gromov-Hausdorff convergence.

**Exercise 14**Let be a sequence of pointed metric spaces which converge in the pointed Gromov-Hausdorff sense to a limit , and also to another limit . Suppose that these two limit spaces are proper, which means that the closed balls and are compact. Show that the two limit spaces are pointedly isometric, thus there is an isometric isomorphism that maps to .In the compact case, Gromov-Hausdorff convergence and pointwise Gromov-Hausdorff convergence are almost equivalent:

**Exercise 15**Let be a sequence of bounded pointed metric spaces, and let be a compact pointed metric space.- (i) Show that if converges in the pointed Gromov-Hausdorff sense to , then converges in the Gromov-Hausdorff sense to .
- (ii) Conversely, if converges in the Gromov-Hausdorff sense to , show that some subsequence converges in the pointed Gromov-Hausdorff sense to for some .

There is a compactness theorem for pointed Gromov-Hausdorff convergence analogous to that for ordinary Gromov-Hausdorff convergence (Proposition 5):

**Proposition 7 (Locally uniformly total bounded spaces are pointed Gromov-Hausdorff precompact)**Let be a sequence of pointed metric spaces such that the balls are uniformly totally bounded in for each fixed . Then there exists a subsequence which converges in the pointed Gromov-Hausdorff space to a limit which is proper (i.e. every closed ball is compact).We sketch a proof of this proposition in the exercise below.

**Exercise 16**Let be as in the above proposition; we assume the to be standard. Let be the ultraproduct of the , and define the ultralimits and . Let be the points in that are a bounded distance from .- (i) Show that is a pseudometric on .
- (ii) Show that the associated quotient space with the quotient metric is a proper metric space.
- (iii) Show that some subsequence of the converge in the pointed Gromov-Hausdorff sense to , where is the image of under the quotient map, thus establishing Proposition 7.

**Exercise 17**Establish Proposition 7 without using ultrafilters.**Exercise 18**Let be a locally compact group with a Gleason metric . Show that the pointed metric spaces converge in the pointed Gromov-Hausdorff sense as to the vector space with the metric and distinguished point , where the norm on was defined in Exercise 7 of Notes 2.**Remark 1**The above exercise suggests that one could attack Hilbert’s fifth problem by somehow “blowing up” the locally compact group around the origin and extracting a Gromov-Hausdorff limit using ultraproducts. This approach can be formalised using the language of nonstandard analysis, and in particular can be used to describe Hirschfeld’s nonstandard solution to Hilbert’s fifth problem, as well as the later work of Goldbring. However, we will not detail this approach extensively here (though, on some level, it contains much the same ingredients as the known “standard” solutions to that problem, such as the one given in previous notes).**— 2. Sanders-Croot-Sisask theory —**We now prove Sanders’ lemma (Lemma 1), which roughly speaking will be needed to establish an important “total boundedness” property of ultra approximate groups, which in turn is necessary to ensure local compactness for models of such groups.

Let be a -approximate group for some , and let be a (large) natural number. Our task is to locate a large set such that the iterated power is contained inside . Sanders’ strategy for doing this is to pick a set that nearly stabilises a set that is comparable in some sense to . More precisely, suppose we have non-empty finite sets and with the property that

for all . Then an easy induction shows that

for all and all . In particular, and are not disjoint whenever , which means that . Thus, to prove Sanders’ lemma, it suffices to find a non-empty set with the property that the set

has cardinality . (Note that this set will automatically be symmetric and contain the origin.)

**Remark 2**The set (1) is known as a*symmetry set*of and is sometimes denoted . One can also interpret this set as a ball, using the mapping of into to pull back the metric to , in which case is the ball of radius centred at the origin.It remains to find a set for which the set (1) is large. To motivate how we would do this, let us naively try setting . If the set (1) associated to this set is large, we will be done, so let us informally consider the opposite case in which is extremely small; in particular, we have

for “most” choices of . In particular,

Now observe that is contained in , and so

We have thus achieved a dichotomy: either the choice “works”, or else the set is significantly smaller than for some . We can then try to repeat this dichotomy, to show that the choice either “works”, or else the set is significantly smaller than for some . We can keep iterating this dichotomy, creating ever smaller sets of the form ; but on the other hand, these sets should be at least as large as (provided that we choose , , etc. to prevent the sets , etc. from becoming completely empty). So at some point this iteration has to terminate, at which point we should get a set that “works”.

The original paper of Sanders contains a formalisation of the above argument. We present a slightly different arrangement of the argument below, which is focused on making sure that sets such as do not get too small.

For any , define the quantity

Then is a non-decreasing function that takes values between and . By the pigeonhole principle, we can find such that

(The reasons for these particular choices of parameters will become clearer shortly.) Fix this , and let attain the infimum for , thus , , and

(Such an exists since the infimum is only being taken over a finite set.) Set , and let be the set in (1). Observe that if , then

and so by arguing as before we see that

Since and , we thus have

In particular, from (2) and the definition of , we conclude that

So to finish the proof of Sanders’ lemma, it will suffice to obtain a lower bound on the right-hand side of (3). But this can be done by a standard Cauchy-Schwarz argument: starting with the identity

and using the Cauchy-Schwarz inequality and the bound , we conclude that

and thus

By the pigeonhole principle, we may thus find such that

and thus (setting )

Since has cardinality , this forces to exceed for at least values of , and the claim follows.

**Remark 3**The lower bound on obtained by this argument is of the shape . This is not optimal; see Remark 5 below.We now present an alternate approach to Sanders’ lemma, using the Croot-Sisask theory of

*almost periods*. Whereas in the Sanders argument, one selected the set to be the set of group elements that almost stabilised a set , we now select to be the set of group elements that almost stabilise (or are*almost periods*of) the convolutionIt is convenient to work in the metric. Since the function has an norm of and is supported in , which has cardinality at most , we see from Cauchy-Schwarz that

We now set

**Exercise 19**Show that is symmetric, contains the origin, and that .To finish the proof of Sanders’ lemma, it suffices to show that there are lots of almost periods of in the sense that .

The key observation here is that the translates of , as varies in , range in a “totally bounded” set. This in turn comes from a “compactness” property of the convolution operator . when is supported on . Croot and Sisask establish this by using a random sampling argument to approximate this convolution operator by a bounded rank operator. More precisely, let be an integer parameter to be chosen later, and select sample points from independently and uniformly at random (allowing repetitions). We will approximate the operator

for supported on by the operator

The point is that as gets larger, becomes an increasingly good approximation to :

**Exercise 20**Let be a function supported on that is bounded in magnitude by . Show thatand

In particular, with probability at least , one has

Thus, for any , we have

with probability at least . By the pigeonhole principle (or the first moment method), we thus conclude that there exists a choice of sample points for which

Let denote the set of all indicated above. For each , the function is a linear combination of the functions with coefficients between and . Each of these functions has an norm of . Thus, by the pigeonhole principle, one can find a subset of of size such that the functions for all lie within in norm of each other. If is large enough depending on , we then conclude from (4) and the triangle inequality that the functions for all lie within in norm of each other. Translating by some fixed element of , we obtain the claim.

**Remark 4**For future reference, we observe that the above argument did not need the full strength of the hypothesis that was an -approximate group; it would have sufficed for to be finite and non-empty with .**Remark 5**The above version of the Croot-Sisask argument gives a lower bound on of the shape . As was observed by Sanders, by optimising the argument (in particular, replacing with for a large value of , and replacing by ), one can improve this to .**Remark 6**It is also possible to replace the random sampling argument above by a singular value decomposition of (restricted to something like ) to split it as the sum of a bounded rank component and a small operator norm component, after computing the Frobenius norm of in order to limit the number of large singular values. (In the abelian setting, this corresponds to a Fourier decomposition into large and small Fourier coefficients, which is a fundamental tool in additive combinatorics.) We will however not pursue this approach here.As mentioned previously, the Sanders lemma will be useful in building topological group structure on ultra approximate groups (and the group that they generate). The connection can be seen from the simple observation that if is a neighbourhood of the identity in a topological group and , then there exists another neighbourhood of the identity such that . However, in addition to this multiplicative structure, we will also need to impose some conjugacy structure as well. (Strangely, even though the conjugation operation can be defined in terms of the more “primitive” operations of multiplication and inversion , it almost seems to be an independent group operation in some ways, at least for the purposes of studying approximate groups, and the most powerful results tend to come from combining multiplicative structure and conjugation structure together. I do not know a fundamental reason for this “product-conjugation phenomenon” but it does seem to come up a lot in this subject.) Given two non-empty subsets of a group , define

where is the conjugate of by . (Thus, for instance, whenever is a subgroup normalised by .)

We can now establish a stronger version of the Sanders lemma:

**Lemma 8 (Normal Sanders lemma)**Let be a finite -approximate group in a (global) group , let , and let be a symmetric subset of with for some . Then there exists a symmetric subset of with containing the identity such that .Roughly speaking, one can think of the set in Lemma 1 as a “finite index subgroup” of , while the set in Lemma 8 is a “finite index normal subgroup” of . To get from the former to the latter, we will mimic the proof of the following well-known fact:

**Lemma 9**Suppose that is a finite index subgroup of a group . Then there is a finite index normal subgroup of that is contained in .*Proof:*Consider all the conjugates of the finite index subgroup as ranges over . As all the elements from the same right coset give the same conjugate , and is finite index, we see that there are only finitely many such conjugates. Since the intersection of two finite index subgroups is again a finite index subgroup (why?), the intersection is thus a finite index subgroup of . But we have for all , and so is normal as desired.**Remark 7**An inspection of the argument reveals that if had index in , then the normal subgroup has index at most . One can do slightly better than this by looking at the left action of on the -element quotient space , which one can think of as a homomorphism from to the symmetric group of elements. The kernel of this homomorphism is then clearly a normal subgroup of of index at most that is contained in . However, this slightly more efficient argument seems to be more “fragile” than the more robust proof given above, in that it is not obvious (to me, at least) how to adapt it to the approximate group setting of the Sanders lemma. (Thus we see the advantages of knowing multiple proofs for various basic facts in mathematics.)Inspired by the above argument, we now prove Lemma 8. The main difficulty is to find an approximate version of the claim that the intersection of two finite index subgroups is again a finite index subgroup. This is provided by the following lemma:

**Lemma 10**Let be a -approximate group, and let be such that and . Then there exists a subset of with and .*Proof:*Since , we have . It follows that there is some with at least representations as . Let be the set of all values of that appear. Obviously . Suppose that . Then there are such that , and so . Thus lies in as well.Now we prove Lemma 8. By Lemma 1, we may find a symmetric set of containing the identity such that (say) is contained in and . We need the following simple covering lemma:

**Exercise 21 (Ruzsa covering lemma)**Let be finite non-empty subsets of a group such that . Show that can be covered by at most left-translates of for various . (*Hint:*find a maximal disjoint family of with .)From the above lemma we see that can be covered by left translates of . As can be covered by left-translates of , we conclude that can be covered by left-translates of . Since , we conclude that for some and .

The conjugates all lie in . By many applications of Lemma 10, we see that we may find a subset of with such that

for all . In particular, if , then for all , and thus . Thus , and the claim follows.

**Remark 8**The quantitative bounds on given by this argument are quite poor, being of triple exponential type (!) in . It is likely that this can be improved by a more sophisticated argument.**— 3. Locally compact models of ultra approximate groups —**We now use the normal Sanders lemma to place a topology on ultra approximate groups. We first build a “neighbourhood base” associated to an ultra approximate group:

**Exercise 22**Let be an ultra approximate group. Show that there exist a sequence of ultra approximate groupssuch that

for all , and such that can be covered by finitely many left-translates of for each . (

*Hint:*you will need Lemma 8, Lemma 10, Exercise 21, and some sort of recursive construction.)**Remark 9**A simple example to keep in mind here is the nonstandard interval for some unbounded nonstandard natural number , with .This gives a good topology on the group generated by :

**Exercise 23**Let be an ultra approximate group, and let be the group generated by . Let be as in the preceding exercise. Given a subset of , call a point in an*interior point*of if one has for some (standard) . Call*open*if every element of is an interior point.- (i) Show that this defines a topology on .
- (ii) Show that this topology makes into a topological group (i.e. the group operations are continuous).
- (iii) Show that this topology is first countable (and thus pseudo-metrisable by the Birkhoff-Kakutani theorem (see Theorem 6 from Notes 4)).
- (iv) Show that one can build a left-invariant pseudometric on which generates the topology on , with the property that
for all (standard) and some (standard) . (

*Hint:*inspect the proof of the Birkhoff-Kakutani theorem.) - (v) Show that with this pseudometric is complete (i.e. every Cauchy sequence is convergent). (
*Hint:*use the countable saturation property.) - (vi) Show that is totally bounded for each standard (i.e. covered by a finite number of -balls for each ).
- (vii) Show that is locally compact.

With this topology, the group becomes a locally compact topological group. However, in general this group will not be Hausdorff, because the identity need not be closed. Indeed, it is easy to see that the closure of is the set , which is not necessarily trivial. For instance, using the example from Remark 9, is the group , and the closure of the identity is . However, we may quotient out by this closure of the identity to obtain a locally compact

*Hausdorff*group , which is now metrisable (with the metric induced from the pseudometric on ). Let be the quotient homomorphism. This homomorphism obeys a number of good properties, which we formalise as a definition:**Definition 11**Let be an ultra approximate group. A (global)*good model*for is a homomorphism from to a locally compact Hausdorff group that obeys the following axioms:- (Thick image) There exists a neighbourhood of the identity in such that and . (In particular, the kernel of lies in .)
- (Compact image) is precompact.
- (Approximation by nonstandard sets) Suppose that , where is compact and is open. Then there exists a nonstandard finite set (i.e. an ultraproduct of finite sets) such that .

We will often abuse notation and refer to as the good model, rather than . (Actually, to be truly pedantic, it is the ordered pair which is the good model, but we will not use this notation often.)

**Remark 10**In the next set of notes we will also need to consider*local*good models, which only model (say) rather than all of , and in which is a local group rather than a global one. However, for simplicity we will not discuss local good models for the moment.**Remark 11**The thick and compact image axioms imply that the geometry of in some sense corresponds to the geometry of . In particular, if is an element of , then will be “small” (in the sense that it lies in ) if is close to the identity, and “large” (in the sense that it lies outside ) if is far away from the identity. Thus is “faithful” in some “coarse” or “macroscopic” sense. The inclusion is a sort of “local surjectivity” condition, and ensures that does not contain any “excess” or “redundant” components. The approximation by nonstandard set axiom is a technical “measurability” axiom, that ensures that the model of the ultra approximate group actually has something nontrivial to say about the finite approximate groups that were used to build that ultra approximate group (as opposed to being some artefact of the ultrafilter itself).**Example 1**We continue the example from Remark 9. A good model for is provided by the homomorphism given by the formula . The thick image and compact image properties are clear. To illustrate the approximation by nonstandard set property, take and for some (standard) real numbers . The preimages and are not nonstandard finite sets (why? use the least upper bound axiom), but one can find a nonstandard integer such that , and will be a nonstandard finite set between and .The following fundamental observation is essentially due to Hrushovski:

**Exercise 24**Let be an ultra approximate group. Show that has a good model by a locally compact Hausdorff metrisable group, given by the construction discussed previously.**Exercise 25**The purpose of this exercise is to show why it is necessary to model , rather than , in Exercise 24. Let be the field of two elements. For each positive integer , let be a random subset of formed by selecting one element uniformly at random from the set for each , and also selecting the identity . Clearly, is a -approximate group, since is contained in .- (i) Show that almost surely, for all but finitely many , does not contain any set of the form , with . (
*Hint:*use the Borel-Cantelli lemma.) - (ii) Show that almost surely, the ultraproduct cannot be modeled by any locally compact group.

Let us now give some further examples of good models, beyond that given by Example 1.

**Example 2 (Nonstandard finite groups)**Suppose that is a sequence of (standard) finite groups; then the ultraproduct is an ultra approximate group. In this case, is in fact a genuine group, thus . In this case, the trivial homomorphism to the trivial group is a good model of . Conversely, it is easy to see that this is the only case in which is a good model for .**Example 3 (Generalised arithmetic progression)**We still work in the integers , but now take to be the rank two generalised arithmetic progressionThen the ultraproduct is the subset of the nonstandard integers of the form

where is the unbounded natural number . This is an ultra approximate group, with

Then can be modeled by the Euclidean plane , using the model maps defined for each standard by the formula

whenever . The image is then the square for any standard . Note here that while lives in a “one-dimensional” group , the model is “two-dimensional”. This is also reflected in the volume growth of the powers of for small and large , which grow quadratically rather than linearly in . Informally, is “modeled” by the unit square in .

**Exercise 26**With the notation of Example 3, show that cannot be modeled by the one-dimensional Lie group . (*Hint:*If was modeled by , conclude that could be covered by translates of for each standard .)**Exercise 27 (Heisenberg box, I)**We take each to be the “nilbox”Consider the ultraproduct ; this is a subset of the nilpotent (nonstandard) group , consisting of all elements with and , where . Thus

Consider now the map

- (i) Show that is an ultra approximate group.
- (ii) Show that is a good model of .

**Exercise 28 (Heisenberg box, II)**This is a variant of the preceding exercise, in which the is now defined asso that the ultralimit takes the form

and

where . Now consider the map

defined by

- (i) Show that is an ultra approximate group.
- (ii) Show that is a good model of .
- (iii) Show that cannot be modeled by , or by the Heisenberg group.

**Remark 12**Note in the above exercise that the homomorphism is not associated to any exact homomorphisms from to . Instead, it is only associated to*approximate*homomorphismsinto . Such approximate homomorphisms are somewhat less pleasant to work with than genuine homomorphisms; one of the main reasons why we work in the ultraproduct setting is so that we can use genuine group homomorphisms.

We also note the sets for small and large grow cubically in in Exercise 27, and quartically in in Exercise 28. This reflects the corresponding growth rates in and in the Heisenberg group respectively.

Finally, we observe that the nonabelian structure of the ultra approximate group is lost in the model group , because the nonabelianness is “infinitesimal” at the scale of . More generally, good models can capture the “macroscopic” structure of , but do not directly see the “microscopic” structure.

The following exercise demonstrates that model groups need not be simply connected.

**Exercise 29 (Models of Bohr sets)**Let be a standard irrational, let be a standard real number, and let be the setswhere denotes the distance to the nearest integer. Set .

- (i) Show that is an ultra approximate group.
- (ii) Show that is a good model for .
- (iii) Show that is not a good model for . (
*Hint:*consider the growth of , as measured by the number of translates of needed to cover this set.) - (iv) Show that is not a good model for . (
*Hint:*consider the decay of the sets , as measured by the number of translates of this set needed to cover .)

**Exercise 30 (Haar measure)**Let be a good model for an ultra approximate group by a locally compact group . For any continuous compactly supported function , we can define a functional by the formulawhere is the ultralimit of functions , with the nonstandard real and nonstandard natural number defined in the usual fashion as

and

and the infimum is over all for which for all .

- (i) Establish the equivalent formula
where the supremum is over all for which for all .

- (ii) Show that there exists a bi-invariant Haar measure on such that for all continuous compactly supported . (In particular, this shows that is necessarily unimodular.)
- (iii) Show that
whenever , is compact, is open, and is a nonstandard set with

**— 4. Lie models of ultra approximate groups —**In the examples of good models in the previous section, the model group was a Lie group. We give now give some examples to show that the model need not

*initially*be of Lie type, but can then be replaced with a Lie model after some modification.**Example 4 (Nonstandard cyclic group, revisited)**Consider the nonstandard cyclic group . This is a nonstandard finite group and can thus be modeled by the trivial group as discussed in Example 2. However, it can also be modeled by the compact abelian group of -adic integers using the model defined by the formulawhere for each standard natural number , is the remainder of modulo (this is well-defined in ) and the limit is in the -adic metric. Note that the image of is the entire group , and conversely the preimage of in is trivially all of ; as such, one can quotient out in this model and recover the trivial model of .

**Example 5 (Nonstandard abelian -torsion group)**In a similar spirit to the preceding example, the nonstandard -torsion group can be modeled by the compact abelian group by the formulawhere is the obvious projection, and the limit is in the product topology of . As before, we can quotient out and model instead by the trivial group.

**Remark 13**The above two examples can be generalised to model any nonstandard finite group equipped with surjective homomorphisms from to by the inverse limit of the .**Exercise 31 (Lamplighter group)**Let be the field of two elements. be the lamplighter group , where acts on by the shift defined by . Thus the group law in is given byFor each , we then set to be the set

where we identify with the space of elements of such that only for . Let be the ring of formal Laurent series in which all but finitely many of the for negative are zero. We let be the modified lamplighter group , where acts on by the shift . We give a topology by assigning each non-zero Laurent series a norm of , where is the least integer for which ; this induces a topology on via the product topology construction.

We will model the ultraproduct (or more precisely, the set , since is not quite symmetric) by the group

using the map

Roughly speaking, captures the behaviour of at the two “ends” of , where . We give the topology induced from the product topology on .

- (i) Show that is an ultra approximate group.
- (ii) Show that is a good model of .
- (iii) Show that is no longer a good model if one projects to the first or second copy of , or to the base group .
- (iv) Show that does not have a good model by a Lie group . (
*Hint:*does not contain arbitrarily small elements of order two, other than the identity.)

**Remark 14**In the above exercise, one needs a moderately complicated (though still locally compact) group to properly model and its powers . This can also be seen from volume growth considerations: grows like for fixed (large ), which is also the rate of volume growth of in , whereas the volume growth in a single factor would only grow like , and the volume growth in is only linear in . However, if we pass to the large subset of defined by , wherethen is now a nonstandard finite group (isomorphic to the group considered in Example 5) and can be modeled simply by the trivial group . Thus we see that we can sometimes greatly simplify the modeling of an ultra approximate group by passing to a large ultra approximate subgroup.

By using the Gleason-Yamabe theorem, one can formalise these examples. Given two ultra approximate groups , we say that is an

*large ultra approximate subgroup*of if and can be covered by finitely many left-translates of .**Theorem 12 (Hrushovski’s Lie model theorem)**Let be an ultra approximate group. Then there exists a large ultra approximate subgroup of that can be modeled by a connected Lie group .*Proof:*By Exercise 24, we have a good model of by some locally compact group . In particular, there is an open neighbourhood of the identity in such that and .Let be a symmetric precompact neighbourhood of the identity such that . By the Gleason-Yamabe theorem (Theorem 1 of Notes 5), there is an open subgroup of , and a compact normal subgroup of contained in , such that is isomorphic to a connected Lie group . Let be the quotient map.

Write . As is a good model, we can find a nonstandard finite set with

By replacing with if necessary, we may take to be symmetric. As can be covered by finitely many left-translates of , we see that is an ultra approximate group. Since

and can be covered by finitely many left-translates of , we see that is a large ultra approximate subgroup of . It is then a routine matter to verify that is a good model for .

The Lie model need not be unique. For instance, the nonstandard cyclic group can be modeled both by the trivial group and by the unit circle . However, as observed by Hrushovski, it can be shown that after quotienting out the (unique) maximal compact normal subgroup from the Lie model , the resulting quotient group (which is also a Lie group, and in some sense describes the “large scale” structure of ) is unique up to isomorphism. The following exercise fleshes out the details of this observation.

**Exercise 32 (Large-scale uniqueness of the Lie model)**Let be connected Lie groups, and let be an ultra approximate group with good models and .- (i) Show that the centre is an abelian Lie group.
- (ii) Show that the connected component of the identity in is isomorphic to for some .
- (iii) Show that the quotient group is a finitely generated abelian group, and is isomorphic to for some finite group .
- (iv) Show that the torsion points of are contained in a compact subgroup of isomorphic to .
- (v) Show that any finite normal subgroup of is central, and thus lies in the compact subgroup indicated above. (
*Hint:*will act continuously by conjugation on this finite normal subgroup.) - (vi) Show that given any increasing sequence of compact normal subgroups of , the upper bound is also a compact normal subgroup of . (
*Hint:*The dimensions of (which are well-defined by Cartan’s theorem) are monotone increasing but bounded by the dimension of . In particular, the connected components must eventually stabilise. Quotient them out and then use (v).) - (vii) Show that contains a unique maximal compact normal subgroup . Similarly, contains a unique maximal compact normal subgroup . Show that the quotient groups contain no non-trivial compact normal subgroups.
- (viii) Show that . (
*Hint:*if , then iff the group generated by and its conjugates is bounded.) - (ix) Show that is isomorphic to .
- (x) Show that for sufficiently large standard , can be modeled by a Lie group with no non-trivial compact normal subgroups, which is unique up to isomorphism.

To illustrate how this theorem is useful, let us apply it in the bounded torsion case.

**Exercise 33**Let be an ultra approximate group in an -torsion nonstandard group for some standard . Show that contains a nonstandard finite group such that can be covered by finitely many left translates of . (*Hint:*if a Lie group has positive dimension, then it contains elements arbitrarily close to the identity of arbitrarily large order.)Combining this exercise with Proposition 11 from Notes 6, we conclude a finitary consequence, first observed by Hrushovski:

**Corollary 13 (Freiman theorem, bounded torsion case)**Let , and let be a finite -approximate subgroup of an -torsion group . Then contains a finite subgroup such that can be covered by left translates of .**Exercise 34 (Commutator self-containment)**- Show that if is an ultra approximate group, then there exists a large approximate subgroup of such that , where we write , with . (Note that this is slightly different from the group-theoretic convention, when and are subgroups, to define to be the
*group generated by*the commutators with and .) - Show that if is a finite -approximate group, then there exists a symmetric set containing the origin with , , and .

**Remark 15**I do not know of any proof of Exercise 34 that does not go through the Gleason-Yamabe theorem (or some other comparably deep fragment of the theory of Hilbert’s fifth problem).The following result of Hrushovski is a significant strengthening of the preceding exercise:

**Exercise 35 (Hrushovski’s structure theorem)**Let be a finite -approximate group, and let be a function. Show that there exist natural numbers with and , and nested setswith the following properties:

- (i) For each , is symmetric;
- (ii) For each , ;
- (iii) For each , is contained in left-translates of ;
- (iv) For with , one has ;
- (v) can be covered by left-translates of .

(

*Hint:*first find and prove an analogous statement for ultra approximate groups, in which the function is not present.)There is a finitary formulation of Theorem 12, but it takes some effort to state. Let be a connected Lie group, with Lie algebra which we identify using some coordinate basis with , thus giving a Euclidean norm on . We say that with this basis has

*complexity at most*for some if- The dimension of is at most ;
- The exponential map is injective on the ball ;
- One has for all .

We then define “balls” on by the formula

**Exercise 36 (Hrushovski’s Lie model theorem, finitary version)**Let be a function, and let be a finite -approximate group. Show that there exists a natural number , a connected Lie group of complexity at most , a symmetric set containing the identity with , and a map obeying the following properties:- (i) (Large subgroup) can be covered by left-translates of .
- (ii) (Approximate homomorphism) One has , and for all with , one has
- (iii) (Thick image) If and , then . Conversely, if , then intersects .
- (iv) (Compact image) One has .

(

*Hint:*One needs to argue by compactness and contradiction,*carefully*negating all the quantifiers in the above claim, and then use Theorem 12.)**Exercise 37**In the converse direction, show that Theorem 12 can be deduced from Exercise 36. (*Hint:*to get started, one needs a statement to the effect that if an ultra approximate group is unable to be modeled by some Lie group of complexity at most , then there is also some for which cannot be “approximately modeled up to error ” in some sense by such a Lie group. Once one has such a statement (provable via a compactness or ultralimit argument), one can use this to build a suitable function which which to apply Exercise 36.

## 14 comments

Comments feed for this article

28 October, 2011 at 12:01 am

bengreenThese are excellent notes.

30 October, 2011 at 3:12 pm

David RobertsThird paragraph has broken link syntax:

http://en.wikipedia.org/wiki/Non-standard_analysis#.CE.BA-saturation{countable saturation}

Some bounding box errors, but not sure what you can do about them

Example 1 under remark 10

Exercise 27

Exercise 31

[(Mostly) corrected, thanks - T.]2 November, 2011 at 5:40 am

Olof SisaskHi Terry,

About Remark 4, I believe the -almost-periodicity lemma naturally gives a bound of the form for the S with . (This is Theorem 1.6 in the paper with Ernie.) But as Tom very nicely pointed out in his Bogolyubov paper, if one applies the result (with ) to instead of the result to , one naturally gets (even in the non-abelian setting).

Thanks for these very interesting posts.

2 November, 2011 at 7:46 am

Terence TaoThanks for the correction and reference! I did not realise that this portion of Tom’s paper worked in the nonabelian case also.

It makes me wonder if one can use this trick to similarly improve upon the “normal” version of Tom’s lemma (Lemma 8 in the above notes). The argument given above basically concedes one more exponential on top of what one has for the ordinary version, but perhaps with similar tricks to the above, that can be dealt with.

6 November, 2011 at 9:22 am

254A, Notes 8: The microstructure of approximate groups « What’s new[...] macroscopic structure of these objects is well described by the Hrushovski Lie model theorem from the previous set of notes, which informally asserts that the macroscopic structure of an (ultra) approximate group can be [...]

13 November, 2011 at 5:20 pm

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

13 November, 2011 at 9:53 pm

Ben HayesShould the in the displayed equation on part (iv) of Exercise 23 be a displayed Otherwise this part doesn’t seem as helpful.

[Oops, corrected, thanks - T.]14 November, 2011 at 4:33 pm

Ben HayesIn Exercise 31 should there be a somewhere? I think, e.g. you may want I’m having difficulty showing that contains the inverse image of an open neighborhood of the identity in

14 November, 2011 at 7:44 pm

Terence TaoOops, there were several things wrong with that exercise; I’ve had to rewrite it a bit to address the issues you found. Hopefully it is now ok…

28 November, 2011 at 3:46 pm

Nick CookIn the proof of the Normal Sanders Lemma, doesn’t application of the Rusza covering lemma give that is covered by left translates of , not ? Everything still works if we take such that is contained in at the start – I just want to check my understanding that the Rusza covering lemma converts statements like to statements about being covered by translates of rather than .

28 November, 2011 at 3:53 pm

Nick CookSome small typos: in Lemma 10 do you want as in the proof?

Exercise 29 – should be in the definition of .

Exercise 31, part (iii) – I think should be project to one of the two factors , rather than two factors of .

28 November, 2011 at 5:03 pm

Terence TaoThanks for the corrections!

8 February, 2012 at 11:36 am

Lou van den DriesSome typos in the proof of Sanders’ Lemma:

. Two displays later, (1/m)|A^2| should be

(1/m)|A’A|, and the right hand sides in the next two displays should be

(1-(1/m)) |A’A| and (1-(1/m))f(t)|A|. In the subsequent two displays

the right hand side is missing a factor |A|.

[Corrected, thanks - T.]8 February, 2012 at 11:39 am

Lou van den DriesThe “less than” sign in (2) in the proof of Sanders’ lemma should be a

“greater than” sign, I think.

[Corrected, thanks - T.]