You are currently browsing the category archive for the ‘math.GR’ category.

This is an addendum to last quarter’s course notes on Hilbert’s fifth problem, which I am in the process of reviewing in order to transcribe them into a book (as was done similarly for several other sets of lecture notes on this blog). When reviewing the zeroth set of notes in particular, I found that I had made a claim (Proposition 11 from those notes) which asserted, roughly speaking, that any sufficiently large nilprogression was an approximate group, and promised to prove it later in the course when we had developed the ability to calculate efficiently in nilpotent groups. As it turned out, I managed finish the course without the need to develop these calculations, and so the proposition remained unproven. In order to rectify this, I will use this post to lay out some of the basic algebra of nilpotent groups, and use it to prove the above proposition, which turns out to be a bit tricky. (In my paper with Breuillard and Green, we avoid the need for this proposition by restricting attention to a special type of nilprogression, which we call a nilprogression in -normal form, for which the computations are simpler.)

There are several ways to think about nilpotent groups; for instance one can use the model example of the Heisenberg group

over an arbitrary ring (which need not be commutative), or more generally any matrix group consisting of unipotent upper triangular matrices, and view a general nilpotent group as being an abstract generalisation of such concrete groups. (In the case of nilpotent Lie groups, at least, this is quite an accurate intuition, thanks to Engel’s theorem.) Or, one can adopt a Lie-theoretic viewpoint and try to think of nilpotent groups as somehow arising from nilpotent Lie algebras; this intuition is rigorous when working with nilpotent Lie groups (at least when the characteristic is large, in order to avoid issues coming from the denominators in the Baker-Campbell-Hausdorff formula), but also retains some conceptual value in the non-Lie setting. In particular, nilpotent groups (particularly finitely generated ones) can be viewed in some sense as “nilpotent Lie groups over “, even though Lie theory does not quite work perfectly when the underlying scalars merely form an integral domain instead of a field.

Another point of view, which arises naturally both in analysis and in algebraic geometry, is to view nilpotent groups as modeling “infinitesimal” perturbations of the identity, where the infinitesimals have a certain finite order. For instance, given a (not necessarily commutative) ring without identity (representing all the “small” elements of some larger ring or algebra), we can form the powers for , defined as the ring generated by -fold products of elements in ; this is an ideal of which represents the elements which are “ order” in some sense. If one then formally adjoins an identity onto the ring , then for any , the multiplicative group is a nilpotent group of step at most . For instance, if is the ring of strictly upper matrices (over some base ring), then vanishes and becomes the group of unipotent upper triangular matrices over the same ring, thus recovering the previous matrix-based example. In analysis applications, might be a ring of operators which are somehow of “order” or for some small parameter or , and one wishes to perform Taylor expansions up to order or , thus discarding (i.e. quotienting out) all errors in .

From a dynamical or group-theoretic perspective, one can also view nilpotent groups as towers of central extensions of a trivial group. Finitely generated nilpotent groups can also be profitably viewed as a special type of polycylic group; this is the perspective taken in this previous blog post. Last, but not least, one can view nilpotent groups from a combinatorial group theory perspective, as being words from some set of generators of various “degrees” subject to some commutation relations, with commutators of two low-degree generators being expressed in terms of higher degree objects, and all commutators of a sufficiently high degree vanishing. In particular, generators of a given degree can be moved freely around a word, as long as one is willing to generate commutator errors of higher degree.

With this last perspective, in particular, one can start computing in nilpotent groups by adopting the philosophy that the lowest order terms should be attended to first, without much initial concern for the higher order errors generated in the process of organising the lower order terms. Only after the lower order terms are in place should attention then turn to higher order terms, working successively up the hierarchy of degrees until all terms are dealt with. This turns out to be a relatively straightforward philosophy to implement in many cases (particularly if one is not interested in explicit expressions and constants, being content instead with qualitative expansions of controlled complexity), but the arguments are necessarily recursive in nature and as such can become a bit messy, and require a fair amount of notation to express precisely. So, unfortunately, the arguments here will be somewhat cumbersome and notation-heavy, even if the underlying methods of proof are relatively simple.

In the last three notes, we discussed the Bourgain-Gamburd expansion machine and two of its three ingredients, namely quasirandomness and product theorems, leaving only the non-concentration ingredient to discuss. We can summarise the results of the last three notes, in the case of fields of prime order, as the following theorem.

Theorem 1 (Non-concentration implies expansion in )Let be a prime, let , and let be a symmetric set of elements in of cardinality not containing the identity. Write , and suppose that one has the non-concentration propertyfor some and some even integer . Then is a two-sided -expander for some depending only on .

*Proof:* From (1) we see that is not supported in any proper subgroup of , which implies that generates . The claim now follows from the Bourgain-Gamburd expansion machine (Theorem 2 of Notes 4), the product theorem (Theorem 1 of Notes 5), and quasirandomness (Exercise 8 of Notes 3).

Remark 1The same argument also works if we replace by the field of order for some bounded . However, there is a difficulty in the regime when is unbounded, because the quasirandomness property becomes too weak for the Bourgain-Gamburd expansion machine to be directly applicable. On theother hand, the above type of theorem was generalised to the setting of cyclic groups with square-free by Varju, to arbitrary by Bourgain and Varju, and to more general algebraic groups than and square-free by Salehi Golsefidy and Varju. It may be that some modification of the proof techniques in these papers may also be able to handle the field case with unbounded .

It thus remains to construct tools that can establish the non-concentration property (1). The situation is particularly simple in , as we have a good understanding of the subgroups of that group. Indeed, from Theorem 14 from Notes 5, we obtain the following corollary to Theorem 1:

Corollary 2 (Non-concentration implies expansion in )Let be a prime, and let be a symmetric set of elements in of cardinality not containing the identity. Write , and suppose that one has the non-concentration propertyfor some and some even integer , where ranges over all Borel subgroups of . Then, if is sufficiently large depending on , is a two-sided -expander for some depending only on .

It turns out (2) can be verified in many cases by exploiting the solvable nature of the Borel subgroups . We give two examples of this in these notes. The first result, due to Bourgain and Gamburd (with earlier partial results by Gamburd and by Shalom) generalises Selberg’s expander construction to the case when generates a thin subgroup of :

Theorem 3 (Expansion in thin subgroups)Let be a symmetric subset of not containing the identity, and suppose that the group generated by is not virtually solvable. Then as ranges over all sufficiently large primes, the Cayley graphs form a two-sided expander family, where is the usual projection.

Remark 2One corollary of Theorem 3 (or of the non-concentration estimate (3) below) is that generates for all sufficiently large , if is not virtually solvable. This is a special case of a much more general result, known as the strong approximation theorem, although this is certainly not the most direct way to prove such a theorem. Conversely, the strong approximation property is used in generalisations of this result to higher rank groups than .

Exercise 1In the converse direction, if is virtually solvable, show that for sufficiently large , fails to generate . (Hint:use Theorem 14 from Notes 5 to prevent from having bounded index solvable subgroups.)

Exercise 2 (Lubotzsky’s 1-2-3 problem)Let .

- (i) Show that generates a free subgroup of . (
Hint:use a ping-pong argument, as in Exercise 23 of Notes 2.)- (ii) Show that if are two distinct elements of the sector , then there os no element for which . (
Hint:this is another ping-pong argument.) Conclude that has infinite index in . (Contrast this with the situation in which the coefficients in are replaced by or , in which case is either all of , or a finite index subgroup, as demonstrated in Exercise 23 of Notes 2).- (iii) Show that for sufficiently large primes form a two-sided expander family.

Remark 3Theorem 3 has been generalised to arbitrary linear groups, and with replaced by for square-free ; see this paper of Salehi Golsefidy and Varju. In this more general setting, the condition of virtual solvability must be replaced by the condition that the connected component of the Zariski closure of is perfect. An effective version of Theorem 3 (with completely explicit constants) was recently obtained by Kowalski.

The second example concerns Cayley graphs constructed using random elements of .

Theorem 4 (Random generators expand)Let be a prime, and let be two elements of chosen uniformly at random. Then with probability , is a two-sided -expander for some absolute constant .

Remark 4As with Theorem 3, Theorem 4 has also been extended to a number of other groups, such as the Suzuki groups (in this paper of Breuillard, Green, and Tao), and more generally to finite simple groups of Lie type of bounded rank (in forthcoming work of Breuillard, Green, Guralnick, and Tao). There are a number of other constructions of expanding Cayley graphs in such groups (and in other interesting groups, such as the alternating groups) beyond those discussed in these notes; see this recent survey of Lubotzky for further discussion. It has been conjectured by Lubotzky and Weiss thatanypair of (say) that generates the group, is a two-sided -expander for an absolute constant : in the case of , this has been established for a density one set of primes by Breuillard and Gamburd.

** — 1. Expansion in thin subgroups — **

We now prove Theorem 3. The first observation is that the expansion property is monotone in the group :

Exercise 3Let be symmetric subsets of not containing the identity, such that . Suppose that is a two-sided expander family for sufficiently large primes . Show that is also a two-sided expander family.

As a consequence, Theorem 3 follows from the following two statments:

Theorem 5 (Tits alternative)Let be a group. Then exactly one of the following statements holds:

- (i) is virtually solvable.
- (ii) contains a copy of the free group of two generators as a subgroup.

Theorem 6 (Expansion in free groups)Let be generators of a free subgroup of . Then as ranges over all sufficiently large primes, the Cayley graphs form a two-sided expander family.

Theorem 5 is a special case of the famous Tits alternative, which among other things allows one to replace by for any and any field of characteristic zero (and fields of positive characteristic are also allowed, if one adds the requirement that be finitely generated). We will not prove the full Tits alternative here, but instead just give an *ad hoc* proof of the special case in Theorem 5 in the following exercise.

Exercise 4Given any matrix , the singular values are and , and we can apply the singular value decomposition to decomposewhere and are orthonormal bases. (When , these bases are uniquely determined up to phase rotation.) We let be the projection of to the projective complex plane, and similarly define .

Let be a subgroup of . Call a pair a

limit pointof if there exists a sequence with and .

- (i) Show that if is infinite, then there is at least one limit point.
- (ii) Show that if is a limit point, then so is .
- (iii) Show that if there are two limit points with , then there exist that generate a free group. (
Hint:Choose close to and close to , and consider the action of and on , and specifically on small neighbourhoods of , and set up a ping-pong type situation.)- (iv) Show that if is hyperbolic (i.e. it has an eigenvalue greater than 1), with eigenvectors , then the projectivisations of form a limit point. Similarly, if is regular parabolic (i.e. it has an eigenvalue at 1, but is not the identity) with eigenvector , show that is a limit point.
- (v) Show that if has no free subgroup of two generators, then all hyperbolic and regular parabolic elements of have a common eigenvector. Conclude that all such elements lie in a solvable subgroup of .
- (vi) Show that if an element is neither hyperbolic nor regular parabolic, and is not a multiple of the identity, then is conjugate to a rotation by (in particular, ).
- (vii) Establish Theorem 5. (
Hint:show that two square roots of in cannot multiply to another square root of .)

Now we prove Theorem 6. Let be a free subgroup of generated by two generators . Let be the probability measure generating a random walk on , thus is the corresponding generator on . By Corollary 2, it thus suffices to show that

for all sufficiently large , some absolute constant , and some even (depending on , of course), where ranges over Borel subgroups.

As is a homomorphism, one has and so it suffices to show that

To deal with the supremum here, we will use an argument of Bourgain and Gamburd, taking advantage of the fact that all Borel groups of obey a common group law, the point being that free groups such as obey such laws only very rarely. More precisely, we use the fact that the Borel groups are solvable of derived length two; in particular we have

for all . Now, is supported on matrices in whose coefficients have size (where we allow the implied constants to depend on the choice of generators ), and so is supported on matrices in whose coefficients also have size . If is less than a sufficiently small multiple of , these coefficients are then less than (say). As such, if lie in the support of and their projections obey the word law (4) in , then the original matrices obey the word law (4) in . (This lifting of identities from the characteristic setting of to the characteristic setting of is a simple example of the “Lefschetz principle”.)

To summarise, if we let be the set of all elements of that lie in the support of , then (4) holds for all . This severely limits the size of to only be of polynomial size, rather than exponential size:

Proposition 7Let be a subset of the support of (thus, consists of words in of length ) such that the law (4) holds for all . Then .

The proof of this proposition is laid out in the exercise below.

Exercise 5Let be a free group generated by two generators . Let be the set of all words of length at most in .

- (i) Show that if commute, then lie in the same cyclic group, thus for some and .
- (ii) Show that if , there are at most elements of that commute with .
- (iii) Show that if , there are at most elements of with .
- (iv) Prove Proposition 7.

Now we can conclude the proof of Theorem 3:

Exercise 6Let be a free group generated by two generators .

- (i) Show that for some absolute constant . (For much more precise information on , see this paper of Kesten.)
- (ii) Conclude the proof of Theorem 3.

** — 2. Random generators expand — **

We now prove Theorem 4. Let be the free group on two formal generators , and let be the generator of the random walk. For any word and any in a group , let be the element of formed by substituting for respectively in the word ; thus can be viewed as a map for any group . Observe that if is drawn randomly using the distribution , and , then is distributed according to the law , where . Applying Corollary 2, it suffices to show that whenever is a large prime and are chosen uniformly and independently at random from , that with probability , one has

for some absolute constant , where ranges over all Borel subgroups of and is drawn from the law for some even natural number .

Let denote the words in of length at most . We may use the law (4) to obtain good bound on the supremum in (5) assuming a certain non-degeneracy property of the word evaluations :

Exercise 7Let be a natural number, and suppose that is such that for . Show thatfor some absolute constant , where is drawn from the law . (

Hint:use (4) and the hypothesis to lift the problem up to , at which point one can use Proposition 7 and Exercise 6.)

In view of this exercise, it suffices to show that with probability , one has for all for some comparable to a small multiple of . As has elements, it thus suffices by the union bound to show that

for some absolute constant , and any of length less than for some sufficiently small absolute constant .

Let us now fix a non-identity word of length less than , and consider as a function from to for an arbitrary field . We can identify with the set . A routine induction then shows that the expression is then a polynomial in the eight variables of degree and coefficients which are integers of size . Let us then make the additional restriction to the case , in which case we can write and . Then is now a rational function of whose numerator is a polynomial of degree and coefficients of size , and the denominator is a monomial of of degree .

We then specialise this rational function to the field . It is conceivable that when one does so, the rational function collapses to the constant polynomial , thus for all with . (For instance, this would be the case if , by Lagrange’s theorem, if it were not for the fact that is far too large here.) But suppose that this rational function does not collapse to the constant rational function. Applying the Schwarz-Zippel lemma (Exercise 23 from Notes 5), we then see that the set of pairs with and is at most ; adding in the and cases, one still obtains a bound of , which is acceptable since and . Thus, the only remaining case to consider is when the rational function is identically on with .

Now we perform another “Lefschetz principle” maneuvre to change the underlying field. Recall that the denominator of rational function is monomial in , and the numerator has coefficients of size . If is less than for a sufficiently small , we conclude in particular (for large enough) that the coefficients all have magnitude less than . As such, the only way that this function can be identically on is if it is identically on for all with , and hence for or also by taking Zariski closures.

On the other hand, we know that for some choices of , e.g. , contains a copy of the free group on two generators (see e.g. Exercise 23 of Notes 2). As such, it is not possible for any non-identity word to be identically trivial on . Thus this case cannot actually occur, completing the proof of (6) and hence of Theorem 4.

Remark 5We see from the above argument that the existence of subgroups of an algebraic group with good “independence” properties – such as that of generating a free group – can be useful in studying the expansion properties of that algebraic group, even if the field of interest in the latter is distinct from that of the former. For more complicated algebraic groups than , in which laws such as (4) are not always available, it turns out to be useful to place further properties on the subgroup , for instance by requiring that all non-abelian subgroups of that group be Zariski dense (a property which has been calledstrong density), as this turns out to be useful for preventing random walks from concentrating in proper algebraic subgroups. See this paper of Breuillard, Guralnick, Green and Tao for constructions of strongly dense free subgroups of algebraic groups and further discussion.

In the previous set of notes, we saw that one could derive expansion of Cayley graphs from three ingredients: non-concentration, product theorems, and quasirandomness. Quasirandomness was discussed in Notes 3. In the current set of notes, we discuss product theorems. Roughly speaking, these theorems assert that in certain circumstances, a finite subset of a group either exhibits expansion (in the sense that , say, is significantly larger than ), or is somehow “close to” or “trapped” by a genuine group.

Theorem 1 (Product theorem in )Let , let be a finite field, and let be a finite subset of . Let be sufficiently small depending on . Then at least one of the following statements holds:

- (Expansion) One has .
- (Close to ) One has .
- (Trapping) is contained in a proper subgroup of .

We will prove this theorem (which was proven first in the cases for fields of prime order by Helfgott, and then for and general by Dinai, and finally to general and independently by Pyber-Szabo and by Breuillard-Green-Tao) later in this notes. A more qualitative version of this proposition was also previously obtained by Hrushovski. There are also generalisations of the product theorem of importance to number theory, in which the field is replaced by a cyclic ring (with not necessarily prime); this was achieved first for and square-free by Bourgain, Gamburd, and Sarnak, by Varju for general and square-free, and finally by this paper of Bourgain and Varju for arbitrary and .

Exercise 1 (Girth bound)Assuming Theorem 1, show that whenever is a symmetric set of generators of for some finite field and some , then any element of can be expressed as the product of elements from . (Equivalently, if we add the identity element to , then for some .) This is a special case of a conjecture of Babai and Seress, who conjectured that the bound should hold uniformly for all finite simple groups (in particular, the implied constants here should not actually depend on . The methods used to handle the case can handle other finite groups of Lie type of bounded rank, but at present we do not have bounds that are independent of the rank. On the other hand, a recent paper of Helfgott and Seress has almost resolved the conjecture for the permutation groups .

A key tool to establish product theorems is an argument which is sometimes referred to as the *pivot argument*. To illustrate this argument, let us first discuss a much simpler (and older) theorem, essentially due to Freiman, which has a much weaker conclusion but is valid in any group :

Theorem 2 (Baby product theorem)Let be a group, and let be a finite non-empty subset of . Then one of the following statements hold:

- (Expansion) One has .
- (Close to a subgroup) is contained in a left-coset of a group with .

To prove this theorem, we suppose that the first conclusion does not hold, thus . Our task is then to place inside the left-coset of a fairly small group .

To do this, we take a group element , and consider the intersection . *A priori*, the size of this set could range from anywhere from to . However, we can use the hypothesis to obtain an important dichotomy, reminiscent of the classical fact that two cosets of a subgroup of are either identical or disjoint:

Proposition 3 (Dichotomy)If , then exactly one of the following occurs:

- (Non-involved case) is empty.
- (Involved case) .

*Proof:* Suppose we are not in the pivot case, so that is non-empty. Let be an element of , then and both lie in . The sets and then both lie in . As these sets have cardinality and lie in , which has cardinality less than , we conclude from the inclusion-exclusion formula that

But the left-hand side is equal to , and the claim follows.

The above proposition provides a clear separation between two types of elements : the “non-involved” elements, which have nothing to do with (in the sense that , and the “involved” elements, which have a lot to do with (in the sense that . The key point is that there is a significant “gap” between the non-involved and involved elements; there are no elements that are only “slightly involved”, in that and intersect a little but not a lot. It is this gap that will allow us to upgrade approximate structure to exact structure. Namely,

Proposition 4The set of involved elements is a finite group, and is equal to .

*Proof:* It is clear that the identity element is involved, and that if is involved then so is (since . Now suppose that are both involved. Then and have cardinality greater than and are both subsets of , and so have non-empty intersection. In particular, is non-empty, and so is non-empty. By Proposition 3, this makes involved. It is then clear that is a group.

If , then is non-empty, and so from Proposition 3 is involved. Conversely, if is involved, then . Thus we have as claimed. In particular, is finite.

Now we can quickly wrap up the proof of Theorem 2. By construction, for all ,which by double counting shows that . As , we see that is contained in a right coset of ; setting , we conclude that is contained in a left coset of . is a conjugate of , and so . If , then and both lie in and have cardinality , so must overlap; and so . Thus , and so , and Theorem 2 follows.

Exercise 2Show that the constant in Theorem 2 cannot be replaced by any larger constant.

Exercise 3Let be a finite non-empty set such that . Show that . (Hint:If , show that for some .)

Exercise 4Let be a finite non-empty set such that . Show that there is a finite group with and a group element such that and .

Below the fold, we give further examples of the pivot argument in other group-like situations, including Theorem 2 and also the “sum-product theorem” of Bourgain-Katz-Tao and Bourgain-Glibichuk-Konyagin.

Emmanuel Breuillard, Ben Green and I have just uploaded to the arXiv the short paper “A nilpotent Freiman dimension lemma“, submitted to the special volume of the European Journal of Combinatorics in honour of Yahya Ould Hamidoune. This paper is a nonabelian (or more precisely, nilpotent) variant of the following additive combinatorics lemma of Freiman:

Freiman’s lemma.Let A be a finite subset of a Euclidean space with . Then A is contained in an affine subspace of dimension at most .

This can be viewed as a “cheap” version of the more well known theorem of Freiman that places sets of small doubling in a torsion-free abelian group inside a generalised arithmetic progression. The advantage here is that the bound on the dimension is extremely explicit.

Our main result is

Theorem.Let A be a finite subset of a simply-connected nilpotent Lie group G which is a K-approximate group (i.e. A is symmetric, contains the identity, and can be covered by up to K left translates of A. Then A can be covered by at most left-translates of a closed connected Lie subgroup of dimension at most .

We remark that our previous paper established a similar result, in which the dimension bound was improved to , but at the cost of worsening the covering number to , and with a much more complicated proof (91 pages instead of 8). Furthermore, the bound on is ineffective, due to the use of ultraproducts in the argument (though it is likely that some extremely lousy explicit bound could eventually be squeezed out of the argument by finitising everything). Note that the step of the ambient nilpotent group G does not influence the final bounds in the theorem, although we do of course need this step to be finite. A simple quotienting argument allows one to deduce a corollary of the above theorem in which the ambient group is assumed to be residually torsion-free nilpotent instead of being a simply connected nilpotent Lie group, but we omit the statement of this corollary here.

To motivate the proof of this theorem, let us first show a simple case of an argument of Gleason, which is very much in the spirit of Freiman’s lemma:

Gleason Lemma (special case).Let be a finite symmetric subset of a Euclidean space, and let be a sequence of subspaces in this space, such that the sets are strictly increasing in i for . Then , where .

**Proof.** By hypothesis, for each , the projection of to is non-trivial, finite, and symmetric. In particular, since the vector space is torsion-free, is strictly larger than . Equivalently, one can find in that does not lie in ; in particular, and is disjoint from . As a consequence, the are disjoint and lie in 5A, whence the claim.

Note that by combining the contrapositive of this lemma with a greedy algorithm, one can show that any K-approximate group in a Euclidean space is contained in a subspace of dimension at most , which is a weak version of Freiman’s lemma.

To extend the argument to the nilpotent setting we use the following idea. Observe that any non-trivial genuine subgroup H of a nilpotent group G will contain at least one non-trivial central element; indeed, by intersecting H with the lower central series of G, and considering the last intersection which is non-trivial, one obtains the claim. It turns out that one can adapt this argument to approximate groups, so that any sufficiently large K-approximate subgroup A of G will contain a non-trivial element that centralises a large fraction of A. Passing to this large fraction and quotienting out the central element, we obtain a new approximate group. If, after a bounded number of steps, this procedure gives an approximate group of bounded size, we are basically done. If, however, the process continues, then by using some Lie group theory, one can find a long sequence of connected Lie subgroups of G, such that the sets are strictly increasing in i. Using some Lie group theory and the hypotheses on G, one can deduce that the group generated by is much larger than , in the sense that the latter group has infinite index in the former. It then turns out that the Gleason argument mentioned above can be adapted to this setting.

In the previous set of notes we saw how a representation-theoretic property of groups, namely Kazhdan’s property (T), could be used to demonstrate expansion in Cayley graphs. In this set of notes we discuss a different representation-theoretic property of groups, namely *quasirandomness*, which is also useful for demonstrating expansion in Cayley graphs, though in a somewhat different way to property (T). For instance, whereas property (T), being qualitative in nature, is only interesting for infinite groups such as or , and only creates Cayley graphs after passing to a finite quotient, quasirandomness is a quantitative property which is directly applicable to finite groups, and is able to deduce expansion in a Cayley graph, provided that random walks in that graph are known to become sufficiently “flat” in a certain sense.

The definition of quasirandomness is easy enough to state:

Definition 1 (Quasirandom groups)Let be a finite group, and let . We say that is-quasirandomif all non-trivial unitary representations of have dimension at least . (Recall a representation istrivialif is the identity for all .)

Exercise 1Let be a finite group, and let . A unitary representation is said to beirreducibleif has no -invariant subspaces other than and . Show that is -quasirandom if and only if every non-trivial irreducible representation of has dimension at least .

Remark 1The terminology “quasirandom group” was introduced explicitly (though with slightly different notational conventions) by Gowers in 2008 in his detailed study of the concept; the name arises because dense Cayley graphs in quasirandom groups are quasirandom graphs in the sense of Chung, Graham, and Wilson, as we shall see below. This property had already been used implicitly to construct expander graphs by Sarnak and Xue in 1991, and more recently by Gamburd in 2002 and by Bourgain and Gamburd in 2008. One can of course define quasirandomness for more general locally compact groups than the finite ones, but we will only need this concept in the finite case. (A paper of Kunze and Stein from 1960, for instance, exploits the quasirandomness properties of the locally compact group to obtain mixing estimates in that group.)

Quasirandomness behaves fairly well with respect to quotients and short exact sequences:

Exercise 2Let be a short exact sequence of finite groups .

- (i) If is -quasirandom, show that is -quasirandom also. (Equivalently: any quotient of a -quasirandom finite group is again a -quasirandom finite group.)
- (ii) Conversely, if and are both -quasirandom, show that is -quasirandom also. (In particular, the direct or semidirect product of two -quasirandom finite groups is again a -quasirandom finite group.)

Informally, we will call *quasirandom* if it is -quasirandom for some “large” , though the precise meaning of “large” will depend on context. For applications to expansion in Cayley graphs, “large” will mean “ for some constant independent of the size of “, but other regimes of are certainly of interest.

The way we have set things up, the trivial group is infinitely quasirandom (i.e. it is -quasirandom for every ). This is however a degenerate case and will not be discussed further here. In the non-trivial case, a finite group can only be quasirandom if it is large and has no large subgroups:

Exercise 3Let , and let be a finite -quasirandom group.

- (i) Show that if is non-trivial, then . (
Hint:use the mean zero component of the regular representation .) In particular, non-trivial finite groups cannot be infinitely quasirandom.- (ii) Show that any proper subgroup of has index . (
Hint:use the mean zero component of the quasiregular representation.)

The following exercise shows that quasirandom groups have to be quite non-abelian, and in particular perfect:

Exercise 4 (Quasirandomness, abelianness, and perfection)Let be a finite group.

- (i) If is abelian and non-trivial, show that is not -quasirandom. (
Hint:use Fourier analysis or the classification of finite abelian groups.)- (ii) Show that is -quasirandom if and only if it is perfect, i.e. the commutator group is equal to . (Equivalently, is -quasirandom if and only if it has no non-trivial abelian quotients.)

Later on we shall see that there is a converse to the above two exercises; any non-trivial perfect finite group with no large subgroups will be quasirandom.

Exercise 5Let be a finite -quasirandom group. Show that for any subgroup of , is -quasirandom, where is the index of in . (Hint:use induced representations.)

Now we give an example of a more quasirandom group.

Lemma 2 (Frobenius lemma)If is a field of some prime order , then is -quasirandom.

This should be compared with the cardinality of the special linear group, which is easily computed to be .

*Proof:* We may of course take to be odd. Suppose for contradiction that we have a non-trivial representation on a unitary group of some dimension with . Set to be the group element

and suppose first that is non-trivial. Since , we have ; thus all the eigenvalues of are roots of unity. On the other hand, by conjugating by diagonal matrices in , we see that is conjugate to (and hence conjugate to ) whenever is a quadratic residue mod . As such, the eigenvalues of must be permuted by the operation for any quadratic residue mod . Since has at least one non-trivial eigenvalue, and there are distinct quadratic residues, we conclude that has at least distinct eigenvalues. But is a matrix with , a contradiction. Thus lies in the kernel of . By conjugation, we then see that this kernel contains all unipotent matrices. But these matrices generate (see exercise below), and so is trivial, a contradiction.

Exercise 6Show that for any prime , the unipotent matricesfor ranging over generate as a group.

Exercise 7Let be a finite group, and let . If is generated by a collection of -quasirandom subgroups, show that is itself -quasirandom.

Exercise 8Show that is -quasirandom for any and any prime . (This is not sharp; the optimal bound here is , which follows from the results of Landazuri and Seitz.)

As a corollary of the above results and Exercise 2, we see that the projective special linear group is also -quasirandom.

Remark 2One can ask whether the bound in Lemma 2 is sharp, assuming of course that is odd. Noting that acts linearly on the plane , we see that it also acts projectively on the projective line , which has elements. Thus acts via the quasiregular representation on the -dimensional space , and also on the -dimensional subspace ; this latter representation (known as the Steinberg representation) is irreducible. This shows that the bound cannot be improved beyond . More generally, given any character , acts on the -dimensional space of functions that obey the twisted dilation invariance for all and ; these are known as the principal series representations. When is the trivial character, this is the quasiregular representation discussed earlier. For most other characters, this is an irreducible representation, but it turns out that when is the quadratic representation (thus taking values in while being non-trivial), the principal series representation splits into the direct sum of two -dimensional representations, which comes very close to matching the bound in Lemma 2. There is a parallel series of representations to the principal series (known as the discrete series) which is more complicated to describe (roughly speaking, one has to embed in a quadratic extension and then use a rotated version of the above construction, to change a split torus into a non-split torus), but can generate irreducible representations of dimension , showing that the bound in Lemma 2 is in fact exactly sharp. These constructions can be generalised to arbitrary finite groups of Lie type using Deligne-Luzstig theory, but this is beyond the scope of this course (and of my own knowledge in the subject).

Exercise 9Let be an odd prime. Show that for any , the alternating group is -quasirandom. (Hint:show that all cycles of order in are conjugate to each other in (and not just in ); in particular, a cycle is conjugate to its power for all . Also, as , is simple, and so the cycles of order generate the entire group.)

Remark 3By using more precise information on the representations of the alternating group (using the theory of Specht modules and Young tableaux), one can show the slightly sharper statement that is -quasirandom for (but is only -quasirandom for due to icosahedral symmetry, and -quasirandom for due to lack of perfectness). Using Exercise 3 with the index subgroup , we see that the bound cannot be improved. Thus, (for large ) is not as quasirandom as the special linear groups (for large and bounded), because in the latter case the quasirandomness is as strong as a power of the size of the group, whereas in the former case it is only logarithmic in size.If one replaces the alternating group with the slightly larger symmetric group , then quasirandomness is destroyed (since , having the abelian quotient , is not perfect); indeed, is -quasirandom and no better.

Remark 4Thanks to the monumental achievement of the classification of finite simple groups, we know that apart from a finite number (26, to be precise) of sporadic exceptions, all finite simple groups (up to isomorphism) are either a cyclic group , an alternating group , or is a finite simple group of Lie type such as . (We will define the concept of a finite simple group of Lie type more precisely in later notes, but suffice to say for now that such groups are constructed from reductive algebraic groups, for instance is constructed from in characteristic .) In the case of finite simple groups of Lie type with bounded rank , it is known from the work of Landazuri and Seitz that such groups are -quasirandom for some depending only on the rank. On the other hand, by the previous remark, the large alternating groups do not have this property, and one can show that the finite simple groups of Lie type with large rank also do not have this property. Thus, we see using the classification that if a finite simple group is -quasirandom for some and is sufficiently large depending on , then is a finite simple group of Lie type with rank . It would be of interest to see if there was an alternate way to establish this fact that did not rely on the classification, as it may lead to an alternate approach to proving the classification (or perhaps a weakened version thereof).

A key reason why quasirandomness is desirable for the purposes of demonstrating expansion is that quasirandom groups happen to be rapidly mixing at large scales, as we shall see below the fold. As such, quasirandomness is an important tool for demonstrating expansion in Cayley graphs, though because expansion is a phenomenon that must hold at all scales, one needs to supplement quasirandomness with some additional input that creates mixing at small or medium scales also before one can deduce expansion. As an example of this technique of combining quasirandomness with mixing at small and medium scales, we present a proof (due to Sarnak-Xue, and simplified by Gamburd) of a weak version of the famous “3/16 theorem” of Selberg on the least non-trivial eigenvalue of the Laplacian on a modular curve, which among other things can be used to construct a family of expander Cayley graphs in (compare this with the property (T)-based methods in the previous notes, which could construct expander Cayley graphs in for any fixed ).

In the previous set of notes we introduced the notion of expansion in arbitrary -regular graphs. For the rest of the course, we will now focus attention primarily to a special type of -regular graph, namely a Cayley graph.

Definition 1 (Cayley graph)Let be a group, and let be a finite subset of . We assume that is symmetric (thus whenever ) and does not contain the identity (this is to avoid loops). Then the (right-invariant)Cayley graphis defined to be the graph with vertex set and edge set , thus each vertex is connected to the elements for , and so is a -regular graph.

Example 1The graph in Exercise 3 of Notes 1 is the Cayley graph on with generators .

Remark 1We call the above Cayley graphs right-invariant because every right translation on is a graph automorphism of . This group of automorphisms acts transitively on the vertex set of the Cayley graph. One can thus view a Cayley graph as a homogeneous space of , as it “looks the same” from every vertex. One could of course also considerleft-invariant Cayley graphs, in which is connected to rather than . However, the two such graphs are isomorphic using the inverse map , so we may without loss of generality restrict our attention throughout to left Cayley graphs.

Remark 2For minor technical reasons, it will be convenient later on to allow to contain the identity and to come with multiplicity (i.e. it will be a multiset rather than a set). If one does so, of course, the resulting Cayley graph will now contain some loops and multiple edges.For the purposes of building expander families, we would of course want the underlying group to be finite. However, it will be convenient at various times to “lift” a finite Cayley graph up to an infinite one, and so we permit to be infinite in our definition of a Cayley graph.

We will also sometimes consider a generalisation of a Cayley graph, known as a Schreier graph:

Definition 2 (Schreier graph)Let be a finite group that acts (on the left) on a space , thus there is a map from to such that and for all and . Let be a symmetric subset of which acts freely on in the sense that for all and , and for all distinct and . Then theSchreier graphis defined to be the graph with vertex set and edge set .

Example 2Every Cayley graph is also a Schreier graph , using the obvious left-action of on itself. The -regular graphs formed from permutations that were studied in the previous set of notes is also a Schreier graph provided that for all distinct , with the underlying group being the permutation group (which acts on the vertex set in the obvious manner), and .

Exercise 1If is an even integer, show that every -regular graph is a Schreier graph involving a set of generators of cardinality . (Hint:first show that every -regular graph can be decomposed into unions of cycles, each of which partition the vertex set, then use the previous example.

We return now to Cayley graphs. It is easy to characterise qualitative expansion properties of Cayley graphs:

Exercise 2 (Qualitative expansion)Let be a finite Cayley graph.

- (i) Show that is a one-sided -expander for for some if and only if generates .
- (ii) Show that is a two-sided -expander for for some if and only if generates , and furthermore intersects each index subgroup of .

We will however be interested in more quantitative expansion properties, in which the expansion constant is independent of the size of the Cayley graph, so that one can construct non-trivial expander families of Cayley graphs.

One can analyse the expansion of Cayley graphs in a number of ways. For instance, by taking the edge expansion viewpoint, one can study Cayley graphs combinatorially, using the product set operation

of subsets of .

Exercise 3 (Combinatorial description of expansion)Let be a family of finite -regular Cayley graphs. Show that is a one-sided expander family if and only if there is a constant independent of such that for all sufficiently large and all subsets of with .

One can also give a combinatorial description of two-sided expansion, but it is more complicated and we will not use it here.

Exercise 4 (Abelian groups do not expand)Let be a family of finite -regular Cayley graphs, with the all abelian, and the generating . Show that are a one-sided expander family if and only if the Cayley graphs have bounded cardinality (i.e. ). (Hint:assume for contradiction that is a one-sided expander family with , and show by two different arguments that grows at least exponentially in and also at most polynomially in , giving the desired contradiction.)

The left-invariant nature of Cayley graphs also suggests that such graphs can be profitably analysed using some sort of Fourier analysis; as the underlying symmetry group is not necessarily abelian, one should use the Fourier analysis of non-abelian groups, which is better known as (unitary) representation theory. The Fourier-analytic nature of Cayley graphs can be highlighted by recalling the operation of convolution of two functions , defined by the formula

This convolution operation is bilinear and associative (at least when one imposes a suitable decay condition on the functions, such as compact support), but is not commutative unless is abelian. (If one is more algebraically minded, one can also identify (when is finite, at least) with the group algebra , in which case convolution is simply the multiplication operation in this algebra.) The adjacency operator on a Cayley graph can then be viewed as a convolution

where is the probability density

where is the Kronecker delta function on . Using the spectral definition of expansion, we thus see that is a one-sided expander if and only if

whenever is orthogonal to the constant function , and is a two-sided expander if

whenever is orthogonal to the constant function .

We remark that the above spectral definition of expansion can be easily extended to symmetric sets which contain the identity or have multiplicity (i.e. are multisets). (We retain symmetry, though, in order to keep the operation of convolution by self-adjoint.) In particular, one can say (with some slight abuse of notation) that a set of elements of (possibly with repetition, and possibly with some elements equalling the identity) generates a one-sided or two-sided -expander if the associated symmetric probability density

We saw in the last set of notes that expansion can be characterised in terms of random walks. One can of course specialise this characterisation to the Cayley graph case:

Exercise 5 (Random walk description of expansion)Let be a family of finite -regular Cayley graphs, and let be the associated probability density functions. Let be a constant.

- Show that the are a two-sided expander family if and only if there exists a such that for all sufficiently large , one has for some , where denotes the convolution of copies of .
- Show that the are a one-sided expander family if and only if there exists a such that for all sufficiently large , one has for some .

In this set of notes, we will connect expansion of Cayley graphs to an important property of certain infinite groups, known as Kazhdan’s property (T) (or property (T) for short). In 1973, Margulis exploited this property to create the first known *explicit* and deterministic examples of expanding Cayley graphs. As it turns out, property (T) is somewhat overpowered for this purpose; in particular, we now know that there are many families of Cayley graphs for which the associated infinite group does not obey property (T) (or weaker variants of this property, such as property ). In later notes we will therefore turn to other methods of creating Cayley graphs that do not rely on property (T). Nevertheless, property (T) is of substantial intrinsic interest, and also has many connections to other parts of mathematics than the theory of expander graphs, so it is worth spending some time to discuss it here.

The material here is based in part on this recent text on property (T) by Bekka, de la Harpe, and Valette (available online here).

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:

Conjecture 2 (Coven-Meyerowitz conjecture, general case)Let be a natural number, and let be a tile of . Then there exists a set of prime powers with such that the Fourier transformvanishes 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.

It can be shown (with a modest amount of effort) that Conjecture 2 implies Conjecture 1, but we will not do so here, focusing instead exclusively on the square-free case for simplicity.

It was observed by Laba that Conjecture 2 is connected to the following well-known conjecture of Fuglede:

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 1Let 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 1Under 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:

Corollary 2Let be a finite -approximate group in an ambient group . Then is covered by left cosets of a virtually nilpotent subgroup of .

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 3Let 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

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

for sufficiently small , or the escape 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 . Astrong -approximate groupis a finite -approximate group in a group with a symmetric subset obeying the following axioms:An

ultra strong -approximate groupis 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 1Let 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:

Exercise 1 (Finding 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:

Theorem 2 (Gleason lemma)Let be a strong -approximate group in a group .

- (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 2Consider the strong -approximate groupin 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.

## Recent Comments