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 formula
Thus, 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 convolution
It 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 that
and
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
for at least
choices of
.
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 groups
such 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 progression
Then 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 as
so 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 homomorphisms
into
. 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 sets
where
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 formula
where
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 formula
where 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 formula
where
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 by
For 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
, where
then
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 sets
with 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.
- (i) If the
14 comments
Comments feed for this article
28 October, 2011 at 12:01 am
bengreen
These are excellent notes.
30 October, 2011 at 3:12 pm
David Roberts
Third 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 Sisask
Hi 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 Tao
Thanks 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 Hayes
Should 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 Hayes
In 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 Tao
Oops, 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 Cook
In 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 Cook
Some 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 Tao
Thanks for the corrections!
8 February, 2012 at 11:36 am
Lou van den Dries
Some 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 Dries
The “less than” sign in (2) in the proof of Sanders’ lemma should be a
“greater than” sign, I think.
[Corrected, thanks – T.]