You are currently browsing the yearly archive for 2011.
Let be a natural number, and let be a permutation of , drawn uniformly at random. Using the cycle decomposition, one can view as the disjoint union of cycles of varying lengths (from to ). For each , let denote the number of cycles of of length ; thus the are natural number-valued random variables with the constraint
We let be the number of cycles (of arbitrary length); this is another natural number-valued random variable, of size at most .
I recently had need to understand the distribution of the random variables and . As it turns out this is an extremely classical subject, but as an exercise I worked out what I needed using a quite tedious computation involving generating functions that I will not reproduce here. But the resulting identities I got were so nice, that they strongly suggested the existence of elementary bijective (or “double counting”) proofs, in which the identities are proven with a minimum of computation, by interpreting each side of the identity as the cardinality (or probability) of the same quantity (or event), viewed in two different ways. I then found these bijective proofs, which I found to be rather cute; again, these are all extremely classical (closely related, for instance, to Stirling numbers of the first kind), but I thought some readers might be interested in trying to find these proofs themselves as an exercise (and I also wanted a place to write the identities down so I could retrieve them later), so I have listed the identities I found below.
- For any , one has . In particular, .
- More generally, for any and with , one has .
- More generally still, for any and with , one has
- In particular, we have Cauchy’s formula: if , then the probability that for all is precisely . (This in particular leads to a reasonably tractable formula for the joint generating function of the , which is what I initially used to compute everything that I needed, before finding the slicker bijective proofs.)
- For fixed , converges in distribution as to the Poisson distribution of intensity .
- More generally, for fixed , converge in joint distribution to independent Poisson distributions of intensity respectively. (A more precise version of this claim can be found in this paper of Arratia and Tavaré.)
- One has .
- More generally, one has for all natural numbers .
One of the basic problems in analytic number theory is to estimate sums of the form
as , where ranges over primes and is some explicit function of interest (e.g. a linear phase function for some real number ). This is essentially the same task as obtaining estimates on the sum
where is the von Mangoldt function. If is bounded, , then from the prime number theorem one has the trivial bound
Unfortunately, the connection between (1) and (4) is not particularly tight; roughly speaking, one needs to improve the bounds in (4) (and variants thereof) by about two factors of before one can use identities such as (3) to recover (1). Still, one generally thinks of (1) and (4) as being “morally” equivalent, even if they are not formally equivalent.
When is oscillating in a sufficiently “irrational” way, then one standard way to proceed is the method of Type I and Type II sums, which uses truncated versions of divisor identities such as (3) to expand out either (1) or (4) into linear (Type I) or bilinear sums (Type II) with which one can exploit the oscillation of . For instance, Vaughan’s identity lets one rewrite the sum in (1) as the sum of the Type I sum
the Type I sum
the Type II sum
and the error term , whenever are parameters, and are the sequences
Similarly one can express (4) as the Type I sum
the Type II sum
and the error term , whenever with , and is the sequence
After eliminating troublesome sequences such as via Cauchy-Schwarz or the triangle inequality, one is then faced with the task of estimating Type I sums such as
or Type II sums such as
for various . Here, the trivial bound is , but due to a number of logarithmic inefficiencies in the above method, one has to obtain bounds that are more like for some constant (e.g. ) in order to end up with an asymptotic such as (1) or (4).
However, in a recent paper of Bourgain, Sarnak, and Ziegler, it was observed that as long as one is only seeking the Mobius orthogonality (4) rather than the von Mangoldt orthogonality (1), one can avoid losing any logarithmic factors, and rely purely on qualitative equidistribution properties of . A special case of their orthogonality criterion (which actually dates back to an earlier paper of Katai, as was pointed out to me by Nikos Frantzikinakis) is as follows:
Actually, the Bourgain-Sarnak-Ziegler paper establishes a more quantitative version of this proposition, in which can be replaced by an arbitrary bounded multiplicative function, but we will content ourselves with the above weaker special case. (See also these notes of Harper, which uses the Katai argument to give a slightly weaker quantitative bound in the same spirit.) This criterion can be viewed as a multiplicative variant of the classical van der Corput lemma, which in our notation asserts that if one has for each fixed non-zero .
As a sample application, Proposition 1 easily gives a proof of the asymptotic
for any irrational . (For rational , this is a little trickier, as it is basically equivalent to the prime number theorem in arithmetic progressions.) The paper of Bourgain, Sarnak, and Ziegler also apply this criterion to nilsequences (obtaining a quick proof of a qualitative version of a result of Ben Green and myself, see these notes of Ziegler for details) and to horocycle flows (for which no Möbius orthogonality result was previously known).
Informally, the connection between (5) and (6) comes from the multiplicative nature of the Möbius function. If (6) failed, then exhibits strong correlation with ; by change of variables, we then expect to correlate with and to correlate with , for “typical” at least. On the other hand, since is multiplicative, exhibits strong correlation with . Putting all this together (and pretending correlation is transitive), this would give the claim (in the contrapositive). Of course, correlation is not quite transitive, but it turns out that one can use the Cauchy-Schwarz inequality as a substitute for transitivity of correlation in this case.
I will give a proof of Proposition 1 below the fold (which is not quite based on the argument in the above mentioned paper, but on a variant of that argument communicated to me by Tamar Ziegler, and also independently discovered by Adam Harper). The main idea is to exploit the following observation: if is a “large” but finite set of primes (in the sense that the sum is large), then for a typical large number (much larger than the elements of ), the number of primes in that divide is pretty close to :
In particular, one can sum (7) against and obtain an approximation
that approximates a sum of by a bunch of sparser sums of . Since
we see (heuristically, at least) that in order to establish (4), it would suffice to establish the sparser estimates
for all (or at least for “most” ).
Now we make the change of variables . As the Möbius function is multiplicative, we usually have . (There is an exception when is divisible by , but this will be a rare event and we will be able to ignore it.) So it should suffice to show that
for most . However, by the hypothesis (5), the sequences are asymptotically orthogonal as varies, and this claim will then follow from a Cauchy-Schwarz argument.
Let be a finite additive group. A tiling pair is a pair of non-empty subsets such that every element of can be written in exactly one way as a sum of an element of and an element of , in which case we write . The sets are then called tiles, with being a complementary tile to and vice versa. For instance, every subgroup of is a tile, as one can pick one representative from each coset of to form the complementary tile. Conversely, any set formed by taking one representative from each coset of is also a tile.
Tiles can be quite complicated, particularly when the group is “high-dimensional”. We will therefore restrict to the simple case of a cyclic group , and restrict even further to the special case when the modulus is square-free. Here, the situation should be much simpler. In particular, we have the following conjecture of Coven and Meyerowitz, which asserts that the previous construction of a tile is, in fact, the only such construction:
Conjecture 1 (Coven-Meyerowitz conjecture, square-free case) Let be square-free, and let be a tile of . Then there exists a subgroup of such that consists of a single representative from each coset of .
Note that in the square-free case, every subgroup of has a complementary subgroup (thus ). In particular, consists of a single representative from each coset of , and so the examples of subgroups of are covered by the above conjecture in the square-free case.
In the non-square free case, the above assertion is not true; for instance, if is a prime, then the multiples of in are a tile, but cannot be formed from taking a single representative from all the cosets of a given subgroup. There is a more general conjecture of Coven and Meyerowitz to handle this more general case, although it is more difficult to state:
vanishes whenever is a non-zero element of whose order is the product of elements of that are powers of distinct primes. Equivalently, the generating polynomial is divisible by the cyclotomic polynomials whenever is the product of elements of that are powers of distinct primes.
Conjecture 3 (One-dimensional Fuglede conjecture, tiling to spectral direction) Let be a compact subset of of positive measure which is a tile (thus for some set ). Then (with Lebesgue measure) has a spectrum, that is to say an orthogonal set of plane waves .
Indeed, it was shown by Laba that Conjecture 2 implies Conjecture 3 in the case when is the finite union of unit intervals. Actually, thanks to the more recent work of Farkas, Matolcsi, and Mora we know that Conjecture 2 in fact implies the universal spectrum conjecture of Lagarias and Wang, which in turn was known to imply Conjecture 3 in full generality. (On the other hand, the conjecture fails in four and higher dimensions; see the papers of Kolountzakis-Matolcsi and of Farkas-Revesz.)
Given the simple statement of Conjecture 1, it is perhaps somewhat surprising that it remains open, even in simple cases such as when is the product of just four primes. One reason for this is that some plausible strengthenings of this conjecture (such as the Tijdeman-Sands conjecture) are known to be false, as we will review below. On the other hand, as we shall see, tiling sets have a lot of combinatorial structure, and in principle one should be able to work out a lot of special cases of the conjecture. Given the combinatorial nature of this problem, it may well be quite suitable for a polymath project in fact, if there is sufficient interest.
In the last set of notes, we obtained the following structural theorem concerning approximate groups:
Theorem 1 Let be a finite -approximate group. Then there exists a coset nilprogression of rank and step contained in , such that is covered by left-translates of (and hence also by right-translates of ).
Remark 1 Under some mild additional hypotheses (e.g. if the dimensions of are sufficiently large, or if is placed in a certain “normal form”, details of which may be found in this paper), a coset nilprogression of rank and step will be an -approximate group, thus giving a partial converse to Theorem 1. (It is not quite a full converse though, even if one works qualitatively and forgets how the constants depend on : if is covered by a bounded number of left- and right-translates of , one needs the group elements to “approximately normalise” in some sense if one wants to then conclude that is an approximate group.) The mild hypotheses alluded to above can be enforced in the statement of the theorem, but we will not discuss this technicality here, and refer the reader to the above-mentioned paper for details.
By placing the coset nilprogression in a virtually nilpotent group, we have the following corollary in the global case:
In this final set of notes, we give some applications of the above results. The first application is to replace “-approximate group” by “sets of bounded doubling”:
Proposition 3 Let be a finite non-empty subset of a (global) group such that . Then there exists a coset nilprogression of rank and step and cardinality such that can be covered by left-translates of , and also by right-translates of .
We will also establish (a strengthening of) a well-known theorem of Gromov on groups of polynomial growth, as promised back in Notes 0, as well as a variant result (of a type known as a “generalised Margulis lemma”) controlling the almost stabilisers of discrete actions of isometries.
The material here is largely drawn from my recent paper with Emmanuel Breuillard and Ben Green.
A common theme in mathematical analysis (particularly in analysis of a “geometric” or “statistical” flavour) is the interplay between “macroscopic” and “microscopic” scales. These terms are somewhat vague and imprecise, and their interpretation depends on the context and also on one’s choice of normalisations, but if one uses a “macroscopic” normalisation, “macroscopic” scales correspond to scales that are comparable to unit size (i.e. bounded above and below by absolute constants), while “microscopic” scales are much smaller, being the minimal scale at which nontrivial behaviour occurs. (Other normalisations are possible, e.g. making the microscopic scale a unit scale, and letting the macroscopic scale go off to infinity; for instance, such a normalisation is often used, at least initially, in the study of groups of polynomial growth. However, for the theory of approximate groups, a macroscopic scale normalisation is more convenient.)
One can also consider “mesoscopic” scales which are intermediate between microscopic and macroscopic scales, or large-scale behaviour at scales that go off to infinity (and in particular are larger than the macroscopic range of scales), although the behaviour of these scales will not be the main focus of this post. Finally, one can divide the macroscopic scales into “local” macroscopic scales (less than for some small but fixed ) and “global” macroscopic scales (scales that are allowed to be larger than a given large absolute constant ). For instance, given a finite approximate group :
- Sets such as for some fixed (e.g. ) can be considered to be sets at a global macroscopic scale. Sending to infinity, one enters the large-scale regime.
- Sets such as the sets that appear in the Sanders lemma from the previous set of notes (thus for some fixed , e.g. ) can be considered to be sets at a local macroscopic scale. Sending to infinity, one enters the mesoscopic regime.
- The non-identity element of that is “closest” to the identity in some suitable metric (cf. the proof of Jordan’s theorem from Notes 0) would be an element associated to the microscopic scale. The orbit starts out at microscopic scales, and (assuming some suitable “escape” axioms) will pass through mesoscopic scales and finally entering the macroscopic regime. (Beyond this point, the orbit may exhibit a variety of behaviours, such as periodically returning back to the smaller scales, diverging off to ever larger scales, or filling out a dense subset of some macroscopic set; the escape axioms we will use do not exclude any of these possibilities.)
For comparison, in the theory of locally compact groups, properties about small neighbourhoods of the identity (e.g. local compactness, or the NSS property) would be properties at the local macroscopic scale, whereas the space of one-parameter subgroups can be interpreted as an object at the microscopic scale. The exponential map then provides a bridge connecting the microscopic and macroscopic scales.
We return now to approximate groups. The 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 modeled by a Lie group. This is already an important piece of information about general approximate groups, but it does not directly reveal the full structure of such approximate groups, because these Lie models are unable to see the microscopic behaviour of these approximate groups.
To illustrate this, let us review one of the examples of a Lie model of an ultra approximate group, namely Exercise 28 from Notes 7. In this example one studied a “nilbox” from a Heisenberg group, which we rewrite here in slightly different notation. Specifically, let be the Heisenberg group
and let , where is the box
thus is the nonstandard box
where . As the above exercise establishes, is an ultra approximate group with a Lie model given by the formula
for and . Note how the nonabelian nature of (arising from the term in the group law (1)) has been lost in the model , because the effect of that nonabelian term on is only which is infinitesimal and thus does not contribute to the standard part. In particular, if we replace with the abelian group with the additive group law
and let and be defined exactly as with and , but placed inside the group structure of rather than , then and are essentially “indistinguishable” as far as their models by are concerned, even though the latter approximate group is abelian and the former is not. The problem is that the nonabelian-ness in the former example is so microscopic that it falls entirely inside the kernel of and is thus not detected at all by the model.
The problem of not being able to “see” the microscopic structure of a group (or approximate group) also was a key difficulty in the theory surrounding Hilbert’s fifth problem that was discussed in previous notes. A key tool in being able to resolve such structure was to build left-invariant metrics (or equivalently, norms ) on one’s group, which obeyed useful “Gleason axioms” such as the commutator axiom
when was sufficiently small. Such axioms have important and non-trivial content even in the microscopic regime where or are extremely close to the identity. For instance, in the proof of Jordan’s theorem from Notes 0, which showed that any finite unitary group was boundedly virtually abelian, a key step was to apply the commutator axiom (2) (for the distance to the identity in operator norm) to the most “microscopic” element of , or more precisely a non-identity element of of minimal norm. The key point was that this microscopic element was virtually central in , and as such it restricted much of to a lower-dimensional subgroup of the unitary group, at which point one could argue using an induction-on-dimension argument. As we shall see, a similar argument can be used to place “virtually nilpotent” structure on finite approximate groups. For instance, in the Heisenberg-type approximate groups and discussed earlier, the element will be “closest to the origin” in a suitable sense to be defined later, and is centralised by both approximate groups; quotienting out (the orbit of) that central element and iterating the process two more times, we shall see that one can express both and as a tower of central cyclic extensions, which in particular establishes the nilpotency of both groups.
The escape axiom (3) is a particularly important axiom in connecting the microscopic structure of a group to its macroscopic structure; for instance, as shown in Notes 2, this axiom (in conjunction with the closely related commutator axiom) tends to imply dilation estimates such as that allow one to understand the microscopic geometry of points close to the identity in terms of the (local) macroscopic geometry of points that are significantly further away from the identity.
It is thus of interest to build some notion of a norm (or left-invariant metrics) on an approximate group that obeys the escape and commutator axioms (while being non-degenerate enough to adequately capture the geometry of in some sense), in a fashion analogous to the Gleason metrics that played such a key role in the theory of Hilbert’s fifth problem. It is tempting to use the Lie model theorem to do this, since Lie groups certainly come with Gleason metrics. However, if one does this, one ends up, roughly speaking, with a norm on that only obeys the escape and commutator estimates macroscopically; roughly speaking, this means that one has a macroscopic commutator inequality
and a macroscopic escape property
but such axioms are too weak for analysis at the microscopic scale, and in particular in establishing centrality of the element closest to the identity.
Another way to proceed is to build a norm that is specifically designed to obey the crucial escape property. Given an approximate group in a group , and an element of , we can define the escape norm of by the formula
Thus, equals if lies outside of , equals if lies in but lies outside of , and so forth. Such norms had already appeared in Notes 4, in the context of analysing NSS groups.
As it turns out, this expression will obey an escape axiom, as long as we place some additional hypotheses on which we will present shortly. However, it need not actually be a norm; in particular, the triangle inequality
is not necessarily true. Fortunately, it turns out that by a (slightly more complicated) version of the Gleason machinery from Notes 4 we can establish a usable substitute for this inequality, namely the quasi-triangle inequality
where is a constant independent of . As we shall see, these estimates can then be used to obtain a commutator estimate (2).
However, to do all this, it is not enough for to be an approximate group; it must obey two additional “trapping” axioms that improve the properties of the escape norm. We formalise these axioms (somewhat arbitrarily) as follows:
Definition 1 (Strong approximate group) Let . A strong -approximate group is a finite -approximate group in a group with a symmetric subset obeying the following axioms:
An ultra strong -approximate group is an ultraproduct of strong -approximate groups.
The first trapping condition can be rewritten as
and the second trapping condition can similarly be rewritten as
This makes the escape norms of , and comparable to each other, which will be needed for a number of reasons (and in particular to close a certain bootstrap argument properly). Compare this with equation (12) from Notes 4, which used the NSS hypothesis to obtain similar conclusions. Thus, one can view the strong approximate group axioms as being a sort of proxy for the NSS property.
Example 1 Let be a large natural number. Then the interval in the integers is a -approximate group, which is also a strong -approximate group (setting , for instance). On the other hand, if one places in rather than in the integers, then the first trapping condition is lost and one is no longer a strong -approximate group. Also, if one remains in the integers, but deletes a few elements from , e.g. deleting from ), then one is still a -approximate group, but is no longer a strong -approximate group, again because the first trapping condition is lost.
A key consequence of the Hrushovski Lie model theorem is that it allows one to replace approximate groups by strong approximate groups:
- (i) Let be an ultra approximate group with a good Lie model , and let be a symmetric convex body (i.e. a convex open bounded subset) in the Lie algebra . Show that if is a sufficiently small standard number, then there exists a strong ultra approximate group with
and with can be covered by finitely many left translates of . Furthermore, is also a good model for .
- (ii) If is a finite -approximate group, show that there is a strong -approximate group inside with the property that can be covered by left translates of . (Hint: use (i), Hrushovski’s Lie model theorem, and a compactness and contradiction argument.)
The need to compare the strong approximate group to an exponentiated small ball will be convenient later, as it allows one to easily use the geometry of to track various aspects of the strong approximate group.
As mentioned previously, strong approximate groups exhibit some of the features of NSS locally compact groups. In Notes 4, we saw that the escape norm for NSS locally compact groups was comparable to a Gleason metric. The following theorem is an analogue of that result:
- (Symmetry) For any , one has .
- (Conjugacy bound) For any , one has .
- (Triangle inequality) For any , one has .
- (Escape property) One has whenever .
- (Commutator inequality) For any , one has .
The proof of this theorem will occupy a large part of the current set of notes. We then aim to use this theorem to classify strong approximate groups. The basic strategy (temporarily ignoring a key technical issue) follows the Bieberbach-Frobenius proof of Jordan’s theorem, as given in Notes 0, is as follows.
- Start with an (ultra) strong approximate group .
- From the Gleason lemma, the elements with zero escape norm form a normal subgroup of . Quotient these elements out. Show that all non-identity elements will have positive escape norm.
- Find the non-identity element in (the quotient of) of minimal escape norm. Use the commutator estimate (assuming it is inherited by the quotient) to show that will centralise (most of) this quotient. In particular, the orbit is (essentially) a central subgroup of .
- Quotient this orbit out; then find the next non-identity element in this new quotient of . Again, show that is essentially a central subgroup of this quotient.
- Repeat this process until becomes entirely trivial. Undoing all the quotients, this should demonstrate that is virtually nilpotent, and that is essentially a coset nilprogression.
There are two main technical issues to resolve to make this strategy work. The first is to show that the iterative step in the argument terminates in finite time. This we do by returning to the Lie model theorem. It turns out that each time one quotients out by an orbit of an element that escapes, the dimension of the Lie model drops by at least one. This will ensure termination of the argument in finite time.
The other technical issue is that while the quotienting out all the elements of zero escape norm eliminates all “torsion” from (in the sense that the quotient of has no non-trivial elements of zero escape norm), further quotienting operations can inadvertently re-introduce such torsion. This torsion can be re-eradicated by further quotienting, but the price one pays for this is that the final structural description of is no longer as strong as “virtually nilpotent”, but is instead a more complicated tower alternating between (ultra) finite extensions and central extensions.
Example 2 Consider the strong -approximate group
in the integers, where is a large natural number not divisible by . As is torsion-free, all non-zero elements of have positive escape norm, and the nonzero element of minimal escape norm here is (or ). But if one quotients by , projects down to , which now has torsion (and all elements in this quotient have zero escape norm). Thus torsion has been re-introduced by the quotienting operation. (A related observation is that the intersection of with is not a simple progression, but is a more complicated object, namely a generalised arithmetic progression of rank two.)
To deal with this issue, we will not quotient out by the entire cyclic group generated by the element of minimal escape norm, but rather by an arithmetic progression , where is a natural number comparable to the reciprocal of the escape norm, as this will be enough to cut the dimension of the Lie model down by one without introducing any further torsion. Of course, this cannot be done in the category of global groups, since the arithmetic progression will not, in general, be a group. However, it is still a local group, and it turns out that there is an analogue of the quotient space construction in local groups. This fixes the problem, but at a cost: in order to make the inductive portion of the argument work smoothly, it is now more natural to place the entire argument inside the category of local groups rather than global groups, even though the primary interest in approximate groups is in the global case when lies inside a global group. This necessitates some technical modification to some of the preceding discussion (for instance, the Gleason-Yamabe theorem must be replaced by the local version of this theorem, due to Goldbring); details can be found in this recent paper of Emmanuel Breuillard, Ben Green, and myself, but will only be sketched here.
where . One easily verifies that these expressions are well-defined (and depend smoothly on and ) when and are sufficiently small.
We have the famous Baker-Campbell-Hausdoff-Dynkin formula:
Theorem 1 (BCH formula) Let be a finite-dimensional Lie group over the reals with Lie algebra . Let be a local inverse of the exponential map , defined in a neighbourhood of the identity. Then for sufficiently small , one has
See for instance these notes of mine for a proof of this formula (it is for , but one easily obtains a similar proof for ).
for sufficiently small , and the inverse operation by (one easily verifies that for all small ).
It is tempting to reverse the BCH formula and conclude (the local form of) Lie’s third theorem, that every finite-dimensional Lie algebra is isomorphic to the Lie algebra of some local Lie group, by using (3) to define a smooth local group structure on a neighbourhood of the identity. (See this previous post for a definition of a local Lie group.) The main difficulty in doing so is in verifying that the definition (3) is well-defined (i.e. that is always equal to ) and locally associative. The well-definedness issue can be trivially disposed of by using just one of the expressions or as the definition of (though, as we shall see, it will be very convenient to use both of them simultaneously). However, the associativity is not obvious at all.
With the assistance of Ado’s theorem, which places inside the general linear Lie algebra for some , one can deduce both the well-definedness and associativity of (3) from the Baker-Campbell-Hausdorff formula for . However, Ado’s theorem is rather difficult to prove (see for instance this previous blog post for a proof), and it is natural to ask whether there is a way to establish these facts without Ado’s theorem.
After playing around with this for some time, I managed to extract a direct proof of well-definedness and local associativity of (3), giving a proof of Lie’s third theorem independent of Ado’s theorem. This is not a new result by any means, (indeed, the original proofs of Lie and Cartan of Lie’s third theorem did not use Ado’s theorem), but I found it an instructive exercise to work out the details, and so I am putting it up on this blog in case anyone else is interested (and also because I want to be able to find the argument again if I ever need it in the future).
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:
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.
Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “The structure of approximate groups“, submitted to Pub. IHES. We had announced the main results of this paper in various forums (including this blog) for a few months now, but it had taken some time to fully write up the paper and put in various refinements and applications.
As announced previously, the main result of this paper is what is a (virtually, qualitatively) complete description of finite approximate groups in an arbitrary (local or global) group . For simplicity let us work in the much more familiar setting of global groups, although our results also apply (but are a bit more technical to state) in the local group setting.
Recall that in a global group , a -approximate group is a symmetric subset of containing the origin, with the property that the product set is covered by left-translates of . Examples of -approximate groups include genuine groups, convex bodies in a bounded dimensional vector space, small balls in a bounded dimensional Lie group, large balls in a discrete nilpotent group of bounded rank or step, or generalised arithmetic progressions (or more generally, coset progressions) of bounded rank in an abelian group. Specialising now to finite approximate groups, a key example of such a group is what we call a coset nilprogression: a set of the form , where is a homomorphism with finite kernel from a subgroup of to a nilpotent group of bounded step, and is a nilprogression with a bounded number of generators in and some lengths , where consists of all the words involving at most copies of , copies of , and so forth up to copies of . One can show (by some nilpotent algebra) that all such coset nilprogressions are -approximate groups so long as the step and the rank are bounded (and if are sufficiently large).
Our main theorem (which was essentially conjectured independently by Helfgott and by Lindenstrauss) asserts, roughly speaking, that coset nilprogressions are essentially the only examples of approximate groups.
Theorem 1 Let be a -approximate group. Then contains a coset nilprogression of rank and step , such that can be covered by left-translates of .
In the torsion-free abelian case, this result is essentially Freiman’s theorem (with an alternate proof by Ruzsa); for general abelian case, it is due to Green and Ruzsa. Various partial results in this direction for some other groups (e.g. free groups, nilpotent groups, solvable groups, or simple groups of Lie type) are also known; see these previous blog posts for a summary of several of these results.
This result has a number of applications to geometric growth theory, and in particular to variants of Gromov’s theorem of groups of polynomial growth, which asserts that a finitely generated group is of polynomial growth if and only if it is virtually nilpotent. The connection lies in the fact that if the balls associated to a finite set of generators has polynomial growth, then some simple volume-packing arguments combined with the pigeonhole principle will show that will end up being a -approximate group for many radii . In fact, since our theorem only needs a single approximate group to obtain virtually nilpotent structure, we are able to obtain some new strengthenings of Gromov’s theorem. For instance, if is any -approximate group in a finitely generated group that contains for some set of generators and some that is sufficiently large depending on , our theorem implies that is virtually nilpotent, answering a question of Petrunin. Among other things, this gives an alternate proof of a recent result of Kapovitch and Wilking (see also this previous paper of Cheeger and Colding) that a compact manifold of bounded diameter and Ricci curvature at least necessarily has a virtually nilpotent fundamental group if is sufficiently small (depending only on dimension). The main point here is that no lower bound on the injectivity radius is required. Another application is a “Margulis-type lemma”, which asserts that if a metric space has “bounded packing” (in the sense that any ball of radius (say) is covered by a bounded number of balls of radius ), and is a group of isometries on that acts discretely (i.e. every orbit has only finitely many elements (counting multiplicity) in each bounded set), then the near-stabiliser of a point is virtually nilpotent if is small enough depending on the packing constant.
There are also some variants and refinements to the main theorem proved in the paper, such as an extension to local groups, and also an improvement on the bound on the rank and step from to (but at the cost of replacing in the theorem with ).
I’ll be discussing the proof of the main theorem in detail in the next few lecture notes of my current graduate course. The full proof is somewhat lengthy (occupying about 50 pages of the 90-page paper), but can be summarised in the following steps:
- (Hrushovski) Take an arbitrary sequence of finite -approximate groups, and show that an appropriate limit of such groups can be “modeled” in some sense by an open bounded subset of a locally compact group. (The precise definition of “model” is technical, but “macroscopically faithful representation” is a good first approximation.) As discussed in the previous lecture notes, we use an ultralimit for this purpose; the paper of Hrushovski where this strategy was first employed also considered more sophisticated model-theoretic limits. To build a locally compact topology, Hrushovski used some tools from definability theory; in our paper, we instead use a combinatorial lemma of Sanders (closely related to a similar result of Croot and Sisask.)
- (Gleason-Yamabe) The locally compact group can in turn be “modeled” by a Lie group (possibly after shrinking the group, and thus the ultralimit , slightly). (This result arose from the solution to Hilbert’s fifth problem, as discussed here. For our extension to local groups, we use a recent local version of the Gleason-Yamabe theorem, due to Goldbring.)
- (Gleason) Using the escape properties of the Lie model, construct a norm (and thus a left-invariant metric ) on the ultralimit approximate group (and also on the finitary groups ) that obeys a number of good properties, such as a commutator estimate . (This is modeled on an analogous construction used in the theory of Hilbert’s fifth problem, as discussed in this previous set of lecture notes.) This norm is essentially an escape norm associated to (a slight modification) of or .
- (Jordan-Bieberbach-Frobenius) We now take advantage of the finite nature of the by locating the non-trivial element of with minimal escape norm (but one has to first quotient out the elements of zero escape norm first). The commutator estimate mentioned previously ensures that this element is essentially “central” in . One can then quotient out a progression generated by this central element (reducing the dimension of the Lie model by one in the process) and iterates the process until the dimension of the model drops to zero. Reversing the process, this constructs a coset nilprogression inside . This argument is based on the classic proof of Jordan’s theorem due to Bieberbach and Frobenius, as discussed in this blog post.
One quirk of the argument is that it requires one to work in the category of local groups rather than global groups. (This is somewhat analogous to how, in the standard proofs of Freiman’s theorem, one needs to work with the category of Freiman homomorphisms, rather than group homomorphisms.) The reason for this arises when performing the quotienting step in the Jordan-Bieberbach-Frobenius leg of the argument. The obvious way to perform this step (and the thing that we tried first) would be to quotient out by the entire cyclic group generated by the element of minimal escape norm. However, it turns out that this doesn’t work too well, because the group quotiented out is so “large” that it can create a lot of torsion in the quotient. In particular, elements which used to have positive escape norm, can now become trapped in the quotient of , thus sending their escape norm to zero. This leads to an inferior conclusion (in which a coset nilprogression is replaced by a more complicated tower of alternating extensions between central progressions and finite groups, similar to the towers encountered in my previous paper on this topic). To prevent this unwanted creation of torsion, one has to truncate the cyclic group before it escapes , so that one quotients out by a geometric progression rather than the cyclic group. But the operation of quotienting out by a , which is a local group rather than a global one, cannot be formalised in the category of global groups, but only in the category of local groups. Because of this, we were forced to carry out the entire argument using the language of local groups. As it turns out, the arguments are ultimately more natural in this setting, although there is an initial investment of notation required, given that global group theory is much more familiar and well-developed than local group theory.
One interesting feature of the argument is that it does not use much of the existing theory of Freiman-type theorems, instead building the coset nilprogression directly from the geometric properties of the approximate group. In particular, our argument gives a new proof of Freiman’s theorem in the abelian case, which largely avoids Fourier analysis (except through the use of the theory of Hilbert’s fifth problem, which uses the Peter-Weyl theorem (or, in the abelian case, Pontryagin duality), which is basically a version of Fourier analysis).
Roughly speaking, mathematical analysis can be divided into two major styles, namely hard analysis and soft analysis. The precise distinction between the two types of analysis is imprecise (and in some cases one may use a blend the two styles), but some key differences can be listed as follows.
- Hard analysis tends to be concerned with quantitative or effective properties such as estimates, upper and lower bounds, convergence rates, and growth rates or decay rates. In contrast, soft analysis tends to be concerned with qualitative or ineffective properties such as existence and uniqueness, finiteness, measurability, continuity, differentiability, connectedness, or compactness.
- Hard analysis tends to be focused on finitary, finite-dimensional or discrete objects, such as finite sets, finitely generated groups, finite Boolean combination of boxes or balls, or “finite-complexity” functions, such as polynomials or functions on a finite set. In contrast, soft analysis tends to be focused on infinitary, infinite-dimensional, or continuous objects, such as arbitrary measurable sets or measurable functions, or abstract locally compact groups.
- Hard analysis tends to involve explicit use of many parameters such as , , , etc. In contrast, soft analysis tends to rely instead on properties such as continuity, differentiability, compactness, etc., which implicitly are defined using a similar set of parameters, but whose parameters often do not make an explicit appearance in arguments.
- In hard analysis, it is often the case that a key lemma in the literature is not quite optimised for the application at hand, and one has to reprove a slight variant of that lemma (using a variant of the proof of the original lemma) in order for it to be suitable for applications. In contrast, in soft analysis, key results can often be used as “black boxes”, without need of further modification or inspection of the proof.
- The properties in soft analysis tend to enjoy precise closure properties; for instance, the composition or linear combination of continuous functions is again continuous, and similarly for measurability, differentiability, etc. In contrast, the closure properties in hard analysis tend to be fuzzier, in that the parameters in the conclusion are often different from the parameters in the hypotheses. For instance, the composition of two Lipschitz functions with Lipschitz constant is still Lipschitz, but now with Lipschitz constant instead of . These changes in parameters mean that hard analysis arguments often require more “bookkeeping” than their soft analysis counterparts, and are less able to utilise algebraic constructions (e.g. quotient space constructions) that rely heavily on precise closure properties.
In the lectures so far, focusing on the theory surrounding Hilbert’s fifth problem, the results and techniques have fallen well inside the category of soft analysis. However, we will now turn to the theory of approximate groups, which is a topic which is traditionally studied using the methods of hard analysis. (Later we will also study groups of polynomial growth, which lies on an intermediate position in the spectrum between hard and soft analysis, and which can be profitably analysed using both styles of analysis.)
Despite the superficial differences between hard and soft analysis, though, there are a number of important correspondences between results in hard analysis and results in soft analysis. For instance, if one has some sort of uniform quantitative bound on some expression relating to finitary objects, one can often use limiting arguments to then conclude a qualitative bound on analogous expressions on infinitary objects, by viewing the latter objects as some sort of “limit” of the former objects. Conversely, if one has a qualitative bound on infinitary objects, one can often use compactness and contradiction arguments to recover uniform quantitative bounds on finitary objects as a corollary.
Remark 1 Another type of correspondence between hard analysis and soft analysis, which is “syntactical” rather than “semantical” in nature, arises by taking the proofs of a soft analysis result, and translating such a qualitative proof somehow (e.g. by carefully manipulating quantifiers) into a quantitative proof of an analogous hard analysis result. This type of technique is sometimes referred to as proof mining in the proof theory literature, and is discussed in this previous blog post (and its comments). We will however not employ systematic proof mining techniques here, although in later posts we will informally borrow arguments from infinitary settings (such as the methods used to construct Gleason metrics) and adapt them to finitary ones.
Let us illustrate the correspondence between hard and soft analysis results with a simple example.
Proposition 1 Let be a sequentially compact topological space, let be a dense subset of , and let be a continuous function (giving the extended half-line the usual order topology). Then the following statements are equivalent:
- (i) (Qualitative bound on infinitary objects) For all , one has .
- (ii) (Quantitative bound on finitary objects) There exists such that for all .
In applications, is typically a (non-compact) set of “finitary” (or “finite complexity”) objects of a certain class, and is some sort of “completion” or “compactification” of which admits additional “infinitary” objects that may be viewed as limits of finitary objects.
Proof: To see that (ii) implies (i), observe from density that every point in is adherent to , and so given any neighbourhood of , there exists . Since , we conclude from the continuity of that also, and the claim follows.
Conversely, to show that (i) implies (ii), we use the “compactness and contradiction” argument. Suppose for sake of contradiction that (ii) failed. Then for any natural number , there exists such that . (Here we have used the axiom of choice, which we will assume throughout this course.) Using sequential compactness, and passing to a subsequence if necessary, we may assume that the converge to a limit . By continuity of , this implies that , contradicting (i).
Remark 2 Note that the above deduction of (ii) from (i) is ineffective in that it gives no explicit bound on the uniform bound in (ii). Without any further information on how the qualitative bound (i) is proven, this is the best one can do in general (and this is one of the most significant weaknesses of infinitary methods when used to solve finitary problems); but if one has access to the proof of (i), one can often finitise or proof mine that argument to extract an effective bound for , although often the bound one obtains in the process is quite poor (particularly if the proof of (i) relied extensively on infinitary tools, such as limits). See this blog post for some related discussion.
The above simple example illustrates that in order to get from an “infinitary” statement such as (i) to a “finitary” statement such as (ii), a key step is to be able to take a sequence (or in some cases, a more general net ) of finitary objects and extract a suitable infinitary limit object . In the literature, there are three main ways in which one can extract such a limit:
- (Topological limit) If the are all elements of some topological space (e.g. an incomplete function space) which has a suitable “compactification” or “completion” (e.g. a Banach space), then (after passing to a subsequence if necessary) one can often ensure the converge in a topological sense (or in a metrical sense) to a limit . The use of this type of limit to pass between quantitative/finitary and qualitative/infinitary results is particularly common in the more analytical areas of mathematics (such as ergodic theory, asymptotic combinatorics, or PDE), due to the abundance of useful compactness results in analysis such as the (sequential) Banach-Alaoglu theorem, Prokhorov’s theorem, the Helly selection theorem, the Arzelá-Ascoli theorem, or even the humble Bolzano-Weierstrass theorem. However, one often has to take care with the nature of convergence, as many compactness theorems only guarantee convergence in a weak sense rather than in a strong one.
- (Categorical limit) If the are all objects in some category (e.g. metric spaces, groups, fields, etc.) with a number of morphisms between the (e.g. morphisms from to , or vice versa), then one can often form a direct limit or inverse limit of these objects to form a limiting object . The use of these types of limits to connect quantitative and qualitative results is common in subjects such as algebraic geometry that are particularly amenable to categorical ways of thinking. (We have seen inverse limits appear in the discussion of Hilbert’s fifth problem, although in that context they were not really used to connect quantitative and qualitative results together.)
- (Logical limit) If the are all distinct spaces (or elements or subsets of distinct spaces), with few morphisms connecting them together, then topological and categorical limits are often unavailable or unhelpful. In such cases, however, one can still tie together such objects using an ultraproduct construction (or similar device) to create a limiting object or limiting space that is a logical limit of the , in the sense that various properties of the (particularly those that can be phrased using the language of first-order logic) are preserved in the limit. As such, logical limits are often very well suited for the task of connecting finitary and infinitary mathematics together. Ultralimit type constructions are of course used extensively in logic (particularly in model theory), but are also popular in metric geometry. They can also be used in many of the previously mentioned areas of mathematics, such as algebraic geometry (as discussed in this previous post).
The three types of limits are analogous in many ways, with a number of connections between them. For instance, in the study of groups of polynomial growth, both topological limits (using the metric notion of Gromov-Hausdorff convergence) and logical limits (using the ultralimit construction) are commonly used, and to some extent the two constructions are at least partially interchangeable in this setting. (See also these previous posts for the use of ultralimits as a substitute for topological limits.) In the theory of approximate groups, though, it was observed by Hrushovski that logical limits (and in particular, ultraproducts) are the most useful type of limit to connect finitary approximate groups to their infinitary counterparts. One reason for this is that one is often interested in obtaining results on approximate groups that are uniform in the choice of ambient group . As such, one often seeks to take a limit of approximate groups that lie in completely unrelated ambient groups , with no obvious morphisms or metrics tying the to each other. As such, the topological and categorical limits are not easily usable, whereas the logical limits can still be employed without much difficulty.
Logical limits are closely tied with non-standard analysis. Indeed, by applying an ultraproduct construction to standard number systems such as the natural numbers or the reals , one can obtain nonstandard number systems such as the nonstandard natural numbers or the nonstandard real numbers (or hyperreals) . These nonstandard number systems behave very similarly to their standard counterparts, but also enjoy the advantage of containing the standard number systems as proper subsystems (e.g. is a subring of ), which allows for some convenient algebraic manipulations (such as the quotient space construction to create spaces such as ) which are not easily accessible in the purely standard universe. Nonstandard spaces also enjoy a useful completeness property, known as countable saturation, which is analogous to metric completeness (as discussed in this previous blog post) and which will be particularly useful for us in tying together the theory of approximate groups with the theory of Hilbert’s fifth problem. See this previous post for more discussion on ultrafilters and nonstandard analysis.
In these notes, we lay out the basic theory of ultraproducts and ultralimits (in particular, proving Los’s theorem, which roughly speaking asserts that ultralimits are limits in a logical sense, as well as the countable saturation property alluded to earlier). We also lay out some of the basic foundations of nonstandard analysis, although we will not rely too heavily on nonstandard tools in this course. Finally, we apply this general theory to approximate groups, to connect finite approximate groups to an infinitary type of approximate group which we will call an ultra approximate group. We will then study these ultra approximate groups (and models of such groups) in more detail in the next set of notes.
Remark 3 Throughout these notes (and in the rest of the course), we will assume the axiom of choice, in order to easily use ultrafilter-based tools. If one really wanted to expend the effort, though, one could eliminate the axiom of choice from the proofs of the final “finitary” results that one is ultimately interested in proving, at the cost of making the proofs significantly lengthier. Indeed, there is a general result of Gödel that any result which can be stated in the language of Peano arithmetic (which, roughly speaking, means that the result is “finitary” in nature), and can be proven in set theory using the axiom of choice (or more precisely, in the ZFC axiom system), can also be proven in set theory without the axiom of choice (i.e. in the ZF system). As this course is not focused on foundations, we shall simply assume the axiom of choice henceforth to avoid further distraction by such issues.