You are currently browsing the tag archive for the ‘nilpotent groups’ tag.

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 ${C}$-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

$\displaystyle H(R) :=\begin{pmatrix} 1 & R & R \\ 0 & 1 & R\\ 0 & 0 & 1 \end{pmatrix}$

over an arbitrary ring ${R}$ (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 ${{\bf Z}}$“, 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 ${R}$ without identity (representing all the “small” elements of some larger ring or algebra), we can form the powers ${R^j}$ for ${j=1,2,\ldots}$, defined as the ring generated by ${j}$-fold products ${r_1 \ldots r_j}$ of elements ${r_1,\ldots,r_j}$ in ${R}$; this is an ideal of ${R}$ which represents the elements which are “${j^{th}}$ order” in some sense. If one then formally adjoins an identity ${1}$ onto the ring ${R}$, then for any ${s \geq 1}$, the multiplicative group ${G := 1+R \hbox{ mod } R^{s+1}}$ is a nilpotent group of step at most ${s}$. For instance, if ${R}$ is the ring of strictly upper ${s \times s}$ matrices (over some base ring), then ${R^{s+1}}$ vanishes and ${G}$ becomes the group of unipotent upper triangular matrices over the same ring, thus recovering the previous matrix-based example. In analysis applications, ${R}$ might be a ring of operators which are somehow of “order” ${O(\epsilon)}$ or ${O(\hbar)}$ for some small parameter ${\epsilon}$ or ${\hbar}$, and one wishes to perform Taylor expansions up to order ${O(\epsilon^s)}$ or ${O(\hbar^s)}$, thus discarding (i.e. quotienting out) all errors in ${R^{s+1}}$.

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.

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 $|A+A| \leq K|A|$.  Then A is contained in an affine subspace of dimension at most ${}\lfloor K-1 \rfloor$.

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 $A \cdot A$ can be covered by up to K left translates of A.  Then A can be covered by at most $K^{2+29K^9}$ left-translates of a closed connected Lie subgroup of dimension at most $K^9$.

We remark that our previous paper established a similar result, in which the dimension bound was improved to $6\log_2 K$, but at the cost of worsening the covering number to $O_K(1)$, and with a much more complicated proof  (91 pages instead of 8). Furthermore, the bound on $O_K(1)$ 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 $A$ be a finite symmetric subset of a Euclidean space, and let $0 = H_0 \subset H_1 \subset \ldots \subset H_k$ be a sequence of subspaces in this space, such that the sets $2A \cap H_i$ are strictly increasing in i for $i=0,\ldots,k$.  Then $|5A| \geq k|A|$, where $5A = A+A+A+A+A$.

Proof.    By hypothesis, for each $i=1,\ldots,k$, the projection $B_i$ of $2A \cap H_i$ to $H_i / H_{i-1}$ is non-trivial, finite, and symmetric.   In particular, since the vector space $H_i/H_{i-1}$ is torsion-free, $B_i+B_i$ is strictly larger than $B_i$.  Equivalently, one can find $a_i$ in $(2A \cap H_i) + (2A \cap H_i)$ that does not lie in $(2A \cap H_i) + H_{i-1}$; in particular, $a_i \in 4A \cap H_i$ and $a_i+A$ is disjoint from $H_{i-1}+A$.  As a consequence, the $a_i+A$ are disjoint and lie in 5A, whence the claim. $\Box$

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 $K^4$, 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 $G = G_1 \geq G_2 \geq G_3 \geq \ldots$ of G, and considering the last intersection $H \cap G_k$ 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 $H_0 \leq H_1 \leq \ldots \leq H_k$ of connected Lie subgroups of G, such that the sets $A^2 \cap H_i$ are strictly increasing in i.   Using some Lie group theory and the hypotheses on G, one can deduce that the group $\langle A^2 \cap H_{i+1}\rangle$ generated by $A^2 \cap H_{i+1}$ is much larger than $\langle A^2 \cap H_i \rangle$, 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 last set of notes, we obtained the following structural theorem concerning approximate groups:

Theorem 1 Let ${A}$ be a finite ${K}$-approximate group. Then there exists a coset nilprogression ${P}$ of rank and step ${O_K(1)}$ contained in ${A^4}$, such that ${A}$ is covered by ${O_K(1)}$ left-translates of ${P}$ (and hence also by ${O_K(1)}$ right-translates of ${P}$).

Remark 1 Under some mild additional hypotheses (e.g. if the dimensions of ${P}$ are sufficiently large, or if ${P}$ is placed in a certain “normal form”, details of which may be found in this paper), a coset nilprogression ${P}$ of rank and step ${O_K(1)}$ will be an ${O_K(1)}$-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 ${K}$: if ${A}$ is covered by a bounded number of left- and right-translates ${gP, Pg}$ of ${P}$, one needs the group elements ${g}$ to “approximately normalise” ${P}$ in some sense if one wants to then conclude that ${A}$ 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 2 Let ${A}$ be a finite ${K}$-approximate group in an ambient group ${G}$. Then ${A}$ is covered by ${O_K(1)}$ left cosets of a virtually nilpotent subgroup ${G'}$ of ${G}$.

In this final set of notes, we give some applications of the above results. The first application is to replace “${K}$-approximate group” by “sets of bounded doubling”:

Proposition 3 Let ${A}$ be a finite non-empty subset of a (global) group ${G}$ such that ${|A^2| \leq K |A|}$. Then there exists a coset nilprogression ${P}$ of rank and step ${O_K(1)}$ and cardinality ${|P| \gg_K |A|}$ such that ${A}$ can be covered by ${O_K(1)}$ left-translates of ${P}$, and also by ${O_K(1)}$ right-translates of ${P}$.

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 ${\epsilon}$ for some small but fixed ${\epsilon>0}$) and “global” macroscopic scales (scales that are allowed to be larger than a given large absolute constant ${C}$). For instance, given a finite approximate group ${A}$:

• Sets such as ${A^m}$ for some fixed ${m}$ (e.g. ${A^{10}}$) can be considered to be sets at a global macroscopic scale. Sending ${m}$ to infinity, one enters the large-scale regime.
• Sets such as the sets ${S}$ that appear in the Sanders lemma from the previous set of notes (thus ${S^m \subset A^4}$ for some fixed ${m}$, e.g. ${m=100}$) can be considered to be sets at a local macroscopic scale. Sending ${m}$ to infinity, one enters the mesoscopic regime.
• The non-identity element ${u}$ of ${A}$ 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 ${u, u^2, u^3, \ldots}$ 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 ${L(G)}$ 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 ${G}$ be the Heisenberg group

$\displaystyle G := \{ (a,b,c): a,b,c \in {\bf Z} \}$

with group law

$\displaystyle (a,b,c) \ast (a',b',c') := (a+a', b+b', c+c'+ab') \ \ \ \ \ (1)$

and let ${A = \prod_{n \rightarrow \alpha} A_n}$, where ${A_n \subset G}$ is the box

$\displaystyle A_n := \{ (a,b,c) \in G: |a|, |b| \leq n; |c| \leq n^{10} \};$

thus ${A}$ is the nonstandard box

$\displaystyle A := \{ (a,b,c) \in {}^* G: |a|, |b| \leq N; |c| \leq N^{10} \}$

where ${N := \lim_{n \rightarrow \alpha} n}$. As the above exercise establishes, ${A \cup A^{-1}}$ is an ultra approximate group with a Lie model ${\pi: \langle A \rangle \rightarrow {\bf R}^3}$ given by the formula

$\displaystyle \pi( a, b, c ) := ( \hbox{st} \frac{a}{N}, \hbox{st} \frac{b}{N}, \hbox{st} \frac{c}{N^{10}} )$

for ${a,b = O(N)}$ and ${c = O(N^{10})}$. Note how the nonabelian nature of ${G}$ (arising from the ${ab'}$ term in the group law (1)) has been lost in the model ${{\bf R}^3}$, because the effect of that nonabelian term on ${\frac{c}{N^{10}}}$ is only ${O(\frac{N^2}{N^8})}$ which is infinitesimal and thus does not contribute to the standard part. In particular, if we replace ${G}$ with the abelian group ${G' := \{(a,b,c): a,b,c \in {\bf Z} \}}$ with the additive group law

$\displaystyle (a,b,c) \ast' (a',b',c') := (a+a',b+b',c+c')$

and let ${A'}$ and ${\pi'}$ be defined exactly as with ${A}$ and ${\pi}$, but placed inside the group structure of ${G'}$ rather than ${G}$, then ${A \cup A^{-1}}$ and ${A' \cup (A')^{-1}}$ are essentially “indistinguishable” as far as their models by ${{\bf R}^3}$ 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 ${\pi}$ 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 ${d}$ (or equivalently, norms ${\| \|}$) on one’s group, which obeyed useful “Gleason axioms” such as the commutator axiom

$\displaystyle \| [g,h] \| \ll \|g\| \|h\| \ \ \ \ \ (2)$

for sufficiently small ${g,h}$, or the escape axiom

$\displaystyle \| g^n \| \gg |n| \|g\| \ \ \ \ \ (3)$

when ${|n| \|g\|}$ was sufficiently small. Such axioms have important and non-trivial content even in the microscopic regime where ${g}$ or ${h}$ 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 ${G}$ 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 ${G}$, or more precisely a non-identity element of ${G}$ of minimal norm. The key point was that this microscopic element was virtually central in ${G}$, and as such it restricted much of ${G}$ 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 ${A \cup A^{-1}}$ and ${A' \cup (A')^{-1}}$ discussed earlier, the element ${(0,0,1)}$ 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 ${A \cup A^{-1}}$ and ${A'\cup (A')^{-1}}$ 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 ${G}$ 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 ${d( g^n, h^n ) \sim n d(g,h)}$ that allow one to understand the microscopic geometry of points ${g,h}$ close to the identity in terms of the (local) macroscopic geometry of points ${g^n, h^n}$ 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 ${A}$ that obeys the escape and commutator axioms (while being non-degenerate enough to adequately capture the geometry of ${A}$ 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 ${A}$ that only obeys the escape and commutator estimates macroscopically; roughly speaking, this means that one has a macroscopic commutator inequality

$\displaystyle \| [g,h] \| \ll \|g\| \|h\| + o(1)$

and a macroscopic escape property

$\displaystyle \| g^n \| \gg |n| \|g\| - o(|n|)$

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 ${A}$ in a group ${G}$, and an element ${g}$ of ${G}$, we can define the escape norm ${\|g\|_{e,A}}$ of ${g}$ by the formula

$\displaystyle \| g \|_{e,A} := \inf \{ \frac{1}{n+1}: n \in {\bf N}: g, g^2, \ldots, g^n \in A \}.$

Thus, ${\|g\|_{e,A}}$ equals ${1}$ if ${g}$ lies outside of ${A}$, equals ${1/2}$ if ${g}$ lies in ${A}$ but ${g^2}$ lies outside of ${A}$, 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 ${A}$ which we will present shortly. However, it need not actually be a norm; in particular, the triangle inequality

$\displaystyle \|gh\|_{e,A} \leq \|g\|_{e,A} + \|h\|_{e,A}$

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

$\displaystyle \|g_1 \ldots g_k \|_{e,A} \leq C (\|g_1\|_{e,A} + \ldots + \|g_k\|_{e,A}),$

where ${C}$ is a constant independent of ${k}$. 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 ${A}$ 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 ${K \geq 1}$. A strong ${K}$-approximate group is a finite ${K}$-approximate group ${A}$ in a group ${G}$ with a symmetric subset ${S}$ obeying the following axioms:

An ultra strong ${K}$-approximate group is an ultraproduct ${A = \prod_{n \rightarrow \alpha} A_n}$ of strong ${K}$-approximate groups.

The first trapping condition can be rewritten as

$\displaystyle \|g\|_{e,A} \leq 1000 \|g\|_{e,A^{100}}$

and the second trapping condition can similarly be rewritten as

$\displaystyle \|g\|_{e,S} \leq 10^6 K^3 \|g\|_{e,A}.$

This makes the escape norms of ${A, A^{100}}$, and ${S}$ 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 ${N}$ be a large natural number. Then the interval ${A = [-N,N]}$ in the integers is a ${2}$-approximate group, which is also a strong ${2}$-approximate group (setting ${S = [10^{-6} N, 10^{-6} N]}$, for instance). On the other hand, if one places ${A}$ in ${{\bf Z}/5N{\bf Z}}$ rather than in the integers, then the first trapping condition is lost and one is no longer a strong ${2}$-approximate group. Also, if one remains in the integers, but deletes a few elements from ${A}$, e.g. deleting ${\pm \lfloor 10^{-10} N\rfloor}$ from ${A}$), then one is still a ${O(1)}$-approximate group, but is no longer a strong ${O(1)}$-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 ${A}$ be an ultra approximate group with a good Lie model ${\pi: \langle A \rangle \rightarrow L}$, and let ${B}$ be a symmetric convex body (i.e. a convex open bounded subset) in the Lie algebra ${{\mathfrak l}}$. Show that if ${r>0}$ is a sufficiently small standard number, then there exists a strong ultra approximate group ${A'}$ with

$\displaystyle \pi^{-1}(\exp(rB)) \subset A' \subset \pi^{-1}(\exp(1.1 rB)) \subset A,$

and with ${A}$ can be covered by finitely many left translates of ${A'}$. Furthermore, ${\pi}$ is also a good model for ${A'}$.

• (ii) If ${A}$ is a finite ${K}$-approximate group, show that there is a strong ${O_K(1)}$-approximate group ${A'}$ inside ${A^4}$ with the property that ${A}$ can be covered by ${O_K(1)}$ left translates of ${A'}$. (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 ${\exp(rB)}$ will be convenient later, as it allows one to easily use the geometry of ${L}$ 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 ${A}$ be a strong ${K}$-approximate group in a group ${G}$.

• (Symmetry) For any ${g \in G}$, one has ${\|g^{-1}\|_{e,A} = \|g\|_{e,A}}$.
• (Conjugacy bound) For any ${g, h \in A^{10}}$, one has ${\|g^h\|_{e,A} \ll \|g\|_{e,A}}$.
• (Triangle inequality) For any ${g_1,\ldots,g_k \in G}$, one has ${\|g_1 \ldots g_k \|_{e,A} \ll_K (\|g_1\|_{e,A} + \ldots + \|g_k\|_{e,A})}$.
• (Escape property) One has ${\|g^n\|_{e,A} \gg |n| \|g\|_{e,A}}$ whenever ${|n| \|g\|_{e,A} < 1}$.
• (Commutator inequality) For any ${g,h \in A^{10}}$, one has ${\| [g,h] \|_{e,A} \ll_K \|g\|_{e,A} \|h\|_{e,A}}$.

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.

1. Start with an (ultra) strong approximate group ${A}$.
2. From the Gleason lemma, the elements with zero escape norm form a normal subgroup of ${A}$. Quotient these elements out. Show that all non-identity elements will have positive escape norm.
3. Find the non-identity element ${g_1}$ in (the quotient of) ${A}$ of minimal escape norm. Use the commutator estimate (assuming it is inherited by the quotient) to show that ${g_1}$ will centralise (most of) this quotient. In particular, the orbit ${\langle g_1 \rangle}$ is (essentially) a central subgroup of ${\langle A \rangle}$.
4. Quotient this orbit out; then find the next non-identity element ${g_2}$ in this new quotient of ${A}$. Again, show that ${\langle g_2 \rangle}$ is essentially a central subgroup of this quotient.
5. Repeat this process until ${A}$ becomes entirely trivial. Undoing all the quotients, this should demonstrate that ${\langle A \rangle}$ is virtually nilpotent, and that ${A}$ 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 ${A}$ (in the sense that the quotient of ${A}$ 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 ${\langle A \rangle}$ 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 ${O(1)}$-approximate group

$\displaystyle A := \{ a N^{10} + 5 b: |a| \leq N; |b| \leq N^2 \}$

in the integers, where ${N}$ is a large natural number not divisible by ${5}$. As ${{\bf Z}}$ is torsion-free, all non-zero elements of ${A}$ have positive escape norm, and the nonzero element of minimal escape norm here is ${g=5}$ (or ${g=-5}$). But if one quotients by ${\langle g \rangle}$, ${A}$ projects down to ${{\bf Z}/5{\bf Z}}$, 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 ${A}$ with ${\langle g \rangle = 5{\bf Z}}$ 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 ${\langle g \rangle = \{g^n: n \in {\bf Z} \}}$ generated by the element ${g}$ of minimal escape norm, but rather by an arithmetic progression ${P = \{g^n: |n| \leq N\}}$, where ${N}$ is a natural number comparable to the reciprocal ${1/\|g\|_{e,A}}$ 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 ${P}$ 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 ${A}$ is in the global case when ${A}$ 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.

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 ${G}$. 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 ${G = (G,\cdot)}$, a ${K}$-approximate group is a symmetric subset ${A}$ of ${G}$ containing the origin, with the property that the product set ${A \cdot A}$ is covered by ${K}$ left-translates of ${A}$. Examples of ${O(1)}$-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 ${\pi^{-1}(P)}$, where ${\pi: G' \rightarrow N}$ is a homomorphism with finite kernel from a subgroup ${G'}$ of ${G}$ to a nilpotent group ${N}$ of bounded step, and ${P = P(u_1,\ldots,u_r;N_1,\ldots,N_r)}$ is a nilprogression with a bounded number of generators ${u_1,\ldots,u_r}$ in ${N}$ and some lengths ${N_1,\ldots,N_r \gg 1}$, where ${P(u_1,\ldots,u_r;N_1,\ldots,N_r)}$ consists of all the words involving at most ${N_1}$ copies of ${u_1^{\pm 1}}$, ${N_2}$ copies of ${u_2^{\pm 1}}$, and so forth up to ${N_r}$ copies of ${u_r^{\pm 1}}$. One can show (by some nilpotent algebra) that all such coset nilprogressions are ${O(1)}$-approximate groups so long as the step and the rank ${r}$ are bounded (and if ${N_1,\ldots,N_r}$ 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 ${A}$ be a ${K}$-approximate group. Then ${A^4}$ contains a coset nilprogression ${P}$ of rank and step ${O_K(1)}$, such that ${A}$ can be covered by ${O_K(1)}$ left-translates of ${P}$.

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 ${B_S(R)}$ associated to a finite set of generators ${S}$ has polynomial growth, then some simple volume-packing arguments combined with the pigeonhole principle will show that ${B_S(R)}$ will end up being a ${O(1)}$-approximate group for many radii ${R}$. 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 ${A}$ is any ${K}$-approximate group in a finitely generated group ${G}$ that contains ${B_S(R_0)}$ for some set of generators ${S}$ and some ${R_0}$ that is sufficiently large depending on ${K}$, our theorem implies that ${G}$ 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 ${-\epsilon}$ necessarily has a virtually nilpotent fundamental group if ${\epsilon}$ 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 ${X}$ has “bounded packing” (in the sense that any ball of radius (say) ${4}$ is covered by a bounded number of balls of radius ${1}$), and ${\Gamma}$ is a group of isometries on ${X}$ that acts discretely (i.e. every orbit has only finitely many elements (counting multiplicity) in each bounded set), then the near-stabiliser ${\{ \gamma \in \Gamma: d(\gamma x, x) \leq \epsilon \}}$ of a point ${x}$ is virtually nilpotent if ${\epsilon}$ 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 ${O_K(1)}$ to ${O(\log K)}$ (but at the cost of replacing ${A^4}$ in the theorem with ${A^{O(1)}}$).

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:

1. (Hrushovski) Take an arbitrary sequence ${A_n}$ of finite ${K}$-approximate groups, and show that an appropriate limit ${A}$ 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.)
2. (Gleason-Yamabe) The locally compact group can in turn be “modeled” by a Lie group (possibly after shrinking the group, and thus the ultralimit ${A}$, 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.)
3. (Gleason) Using the escape properties of the Lie model, construct a norm ${\| \|}$ (and thus a left-invariant metric ${d}$) on the ultralimit approximate group ${A}$ (and also on the finitary groups ${A_n}$) that obeys a number of good properties, such as a commutator estimate ${\| [g,h]\| \ll \|g\| \|h\|}$. (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 ${A}$ or ${A_n}$.
4. (Jordan-Bieberbach-Frobenius) We now take advantage of the finite nature of the ${A_n}$ by locating the non-trivial element ${e}$ of ${A_n}$ 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 ${A_n}$. One can then quotient out a progression ${P(e;N)}$ 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 ${A_n^4}$. 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 ${\langle e \rangle}$ generated by the element ${e}$ 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 ${A_n}$, 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 ${\langle e \rangle}$ before it escapes ${A_n}$, so that one quotients out by a geometric progression ${P(e;N)}$ rather than the cyclic group. But the operation of quotienting out by a ${P(e;N)}$, 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).

One of the fundamental inequalities in convex geometry is the Brunn-Minkowski inequality, which asserts that if ${A, B}$ are two non-empty bounded open subsets of ${{\bf R}^d}$, then

$\displaystyle \mu(A+B)^{1/d} \geq \mu(A)^{1/d} + \mu(B)^{1/d}, \ \ \ \ \ (1)$

where

$\displaystyle A+B := \{a+b: a \in A, b \in B \}$

is the sumset of ${A}$ and ${B}$, and ${\mu}$ denotes Lebesgue measure. The estimate is sharp, as can be seen by considering the case when ${A, B}$ are convex bodies that are dilates of each other, thus ${A = \lambda B := \{ \lambda b: b \in B \}}$ for some ${\lambda>0}$, since in this case one has ${\mu(A) = \lambda^d \mu(B)}$, ${A+B = (\lambda+1)B}$, and ${\mu(A+B) = (\lambda+1)^d \mu(B)}$.

The Brunn-Minkowski inequality has many applications in convex geometry. To give just one example, if we assume that ${A}$ has a smooth boundary ${\partial A}$, and set ${B}$ equal to a small ball ${B = B(0,\epsilon)}$, then ${\mu(B)^{1/d} = \epsilon \mu(B(0,1))^{1/d}}$, and in the limit ${\epsilon \rightarrow 0}$ one has

$\displaystyle \mu(A+B) = \mu(A) + \epsilon |\partial A| + o(\epsilon)$

where ${|\partial A|}$ is the surface measure of ${A}$; applying the Brunn-Minkowski inequality and performing a Taylor expansion, one soon arrives at the isoperimetric inequality

$\displaystyle |\partial A| \geq d \mu(A)^{1-1/d} \mu(B(0,1))^{1/d}.$

Thus one can view the isoperimetric inequality as an infinitesimal limit of the Brunn-Minkowski inequality.

There are many proofs known of the Brunn-Minkowski inequality. Firstly, the inequality is trivial in one dimension:

Lemma 1 (One-dimensional Brunn-Minkowski) If ${A, B \subset {\bf R}}$ are non-empty measurable sets, then

$\displaystyle \mu(A+B) \geq \mu(A)+\mu(B).$

Proof: By inner regularity we may assume that ${A,B}$ are compact. The claim then follows since ${A+B}$ contains the sets ${\sup(A)+B}$ and ${A+\inf(B)}$, which meet only at a single point ${\sup(A)+\inf(B)}$. $\Box$

For the higher dimensional case, the inequality can be established from the Prékopa-Leindler inequality:

Theorem 2 (Prékopa-Leindler inequality in ${{\bf R}^d}$) Let ${0 < \theta < 1}$, and let ${f, g, h: {\bf R}^d \rightarrow {\bf R}}$ be non-negative measurable functions obeying the inequality

$\displaystyle h(x+y) \geq f(x)^{1-\theta} g(y)^\theta \ \ \ \ \ (2)$

for all ${x,y \in {\bf R}^d}$. Then we have

$\displaystyle \int_{{\bf R}^d} h \geq \frac{1}{(1-\theta)^{d(1-\theta)} \theta^{d\theta}} (\int_{{\bf R}^d} f)^{1-\theta} (\int_{{\bf R}^d} g)^\theta. \ \ \ \ \ (3)$

This inequality is usually stated using ${h((1-\theta)x + \theta y)}$ instead of ${h(x+y)}$ in order to eliminate the ungainly factor ${\frac{1}{(1-\theta)^{d(1-\theta)} \theta^{d\theta}}}$. However, we formulate the inequality in this fashion in order to avoid any reference to the dilation maps ${x \mapsto \lambda x}$; the reason for this will become clearer later.

The Prékopa-Leindler inequality quickly implies the Brunn-Minkowski inequality. Indeed, if we apply it to the indicator functions ${f := 1_A, g := 1_B, h := 1_{A+B}}$ (which certainly obey (2)), then (3) gives

$\displaystyle \mu(A+B)^{1/d} \geq \frac{1}{(1-\theta)^{1-\theta} \theta^{\theta}} \mu(A)^{\frac{1-\theta}{d}} \mu(B)^{\frac{\theta}{d}}$

for any ${0 < \theta < 1}$. We can now optimise in ${\theta}$; the optimal value turns out to be

$\displaystyle \theta := \frac{\mu(B)^{1/d}}{\mu(A)^{1/d}+\mu(B)^{1/d}}$

which yields (1).

To prove the Prékopa-Leindler inequality, we first observe that the inequality tensorises in the sense that if it is true in dimensions ${d_1}$ and ${d_2}$, then it is automatically true in dimension ${d_1+d_2}$. Indeed, if ${f, g, h: {\bf R}^{d_1} \times {\bf R}^{d_2} \rightarrow {\bf R}^+}$ are measurable functions obeying (2) in dimension ${d_1+d_2}$, then for any ${x_1, y_1 \in {\bf R}^{d_1}}$, the functions ${f(x_1,\cdot), g(y_1,\cdot), h(x_1+y_1,\cdot): {\bf R}^{d_2} \rightarrow {\bf R}^+}$ obey (2) in dimension ${d_2}$. Applying the Prékopa-Leindler inequality in dimension ${d_2}$, we conclude that

$\displaystyle H(x_1+y_1) \geq \frac{1}{(1-\theta)^{d_2(1-\theta)} \theta^{d_2\theta}} F(x_1)^{1-\theta} G(y_1)^\theta$

for all ${x_1,y_1 \in {\bf R}^{d_1}}$, where ${F(x_1) := \int_{{\bf R}^{d_2}} f(x_1,x_2)\ dx_2}$ and similarly for ${G, H}$. But then if we apply the Prékopa-Leindler inequality again, this time in dimension ${d_1}$ and to the functions ${F}$, ${G}$, and ${(1-\theta)^{d_2(1-\theta)} \theta^{d_2\theta} H}$, and then use the Fubini-Tonelli theorem, we obtain (3).

From tensorisation, we see that to prove the Prékopa-Leindler inequality it suffices to do so in the one-dimensional case. We can derive this from Lemma 1 by reversing the “Prékopa-Leindler implies Brunn-Minkowski” argument given earlier, as follows. We can normalise ${f,g}$ to have sup norm ${1}$. If (2) holds (in one dimension), then the super-level sets ${\{f>\lambda\}, \{g>\lambda\}, \{h>\lambda\}}$ are related by the set-theoretic inclusion

$\displaystyle \{ h > \lambda \} \supset \{ f > \lambda \} + \{ g > \lambda \}$

and thus by Lemma 1

$\displaystyle \mu(\{ h > \lambda \}) \geq \mu(\{ f > \lambda \}) + \mu(\{ g > \lambda \})$

whenever ${\lambda \leq 1}$. On the other hand, from the Fubini-Tonelli theorem one has the distributional identity

$\displaystyle \int_{\bf R} h = \int_0^\infty \mu(\{h > \lambda\})\ d\lambda$

(and similarly for ${f,g}$, but with ${\lambda}$ restricted to ${(0,1)}$), and thus

$\displaystyle \int_{\bf R} h \geq \int_{\bf R} f + \int_{\bf R} g.$

The claim then follows from the weighted arithmetic mean-geometric mean inequality ${(1-\theta) x + \theta y \geq x^{1-\theta} y^\theta}$.

In this post, I wanted to record the simple observation (which appears in this paper of Leonardi and Mansou in the case of the Heisenberg group, but may have also been stated elsewhere in the literature) that the above argument carries through without much difficulty to the nilpotent setting, to give a nilpotent Brunn-Minkowski inequality:

Theorem 3 (Nilpotent Brunn-Minkowski) Let ${G}$ be a connected, simply connected nilpotent Lie group of (topological) dimension ${d}$, and let ${A, B}$ be bounded open subsets of ${G}$. Let ${\mu}$ be a Haar measure on ${G}$ (note that nilpotent groups are unimodular, so there is no distinction between left and right Haar measure). Then

$\displaystyle \mu(A \cdot B)^{1/d} \geq \mu(A)^{1/d} + \mu(B)^{1/d}. \ \ \ \ \ (4)$

Here of course ${A \cdot B := \{ ab: a \in A, b \in B \}}$ is the product set of ${A}$ and ${B}$.

Indeed, by repeating the previous arguments, the nilpotent Brunn-Minkowski inequality will follow from

Theorem 4 (Nilpotent Prékopa-Leindler inequality) Let ${G}$ be a connected, simply connected nilpotent Lie group of topological dimension ${d}$ with a Haar measure ${\mu}$. Let ${0 < \theta < 1}$, and let ${f, g, h: G \rightarrow {\bf R}}$ be non-negative measurable functions obeying the inequality

$\displaystyle h(xy) \geq f(x)^{1-\theta} g(y)^\theta \ \ \ \ \ (5)$

for all ${x,y \in G}$. Then we have

$\displaystyle \int_G h\ d\mu \geq \frac{1}{(1-\theta)^{d(1-\theta)} \theta^{d\theta}} (\int_G f\ d\mu)^{1-\theta} (\int_G g\ d\mu)^\theta. \ \ \ \ \ (6)$

To prove the nilpotent Prékopa-Leindler inequality, the key observation is that this inequality not only tensorises; it splits with respect to short exact sequences. Indeed, suppose one has a short exact sequence

$\displaystyle 0 \rightarrow K \rightarrow G \rightarrow H \rightarrow 0$

of connected, simply connected nilpotent Lie groups. The adjoint action of the connected group ${G}$ on ${K}$ acts nilpotently on the Lie algebra of ${K}$ and is thus unimodular. Because of this, we can split a Haar measure ${\mu_G}$ on ${G}$ into Haar measures ${\mu_K, \mu_H}$ on ${K, H}$ respectively so that we have the Fubini-Tonelli formula

$\displaystyle \int_G f(g)\ d\mu_G(g) = \int_H F(h)\ d\mu_H(h)$

for any measurable ${f: G \rightarrow {\bf R}^+}$, where ${F(h)}$ is defined by the formula

$\displaystyle F(h) := \int_K f(kg) d\mu_K(k) = \int_K f(gk)\ d\mu_K(k)$

for any coset representative ${g \in G}$ of ${h}$ (the choice of ${g}$ is not important, thanks to unimodularity of the conjugation action). It is then not difficult to repeat the proof of tensorisation (relying heavily on the unimodularity of conjugation) to conclude that the nilpotent Prékopa-Leindler inequality for ${H}$ and ${K}$ implies the Prékopa-Leindler inequality for ${G}$; we leave this as an exercise to the interested reader.

Now if ${G}$ is a connected simply connected Lie group, then the abeliansation ${G/[G,G]}$ is connected and simply connected and thus isomorphic to a vector space. This implies that ${[G,G]}$ is a retract of ${G}$ and is thus also connected and simply connected. From this and an induction of the step of the nilpotent group, we see that the nilpotent Prékopa-Leindler inequality follows from the abelian case, which we have already established in Theorem 2.

Remark 1 Some connected, simply connected nilpotent groups ${G}$ (and specifically, the Carnot groups) can be equipped with a one-parameter family of dilations ${x \mapsto \lambda \cdot x}$, which are a family of automorphisms on ${G}$, which dilate the Haar measure by the formula

$\displaystyle \mu( \lambda \cdot x ) = \lambda^D \mu(x)$

for an integer ${D}$, called the homogeneous dimension of ${G}$, which is typically larger than the topological dimension. For instance, in the case of the Heisenberg group

$\displaystyle G := \begin{pmatrix} 1 & {\bf R} & {\bf R} \\ 0 & 1 & {\bf R} \\ 0 & 0 & 1 \end{pmatrix},$

which has topological dimension ${d=3}$, the natural family of dilations is given by

$\displaystyle \lambda: \begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix} \mapsto \begin{pmatrix} 1 & \lambda x & \lambda^2 z \\ 0 & 1 & \lambda y \\ 0 & 0 & 1 \end{pmatrix}$

with homogeneous dimension ${D=4}$. Because the two notions ${d, D}$ of dimension are usually distinct in the nilpotent case, it is no longer helpful to try to use these dilations to simplify the proof of the Brunn-Minkowski inequality, in contrast to the Euclidean case. This is why we avoided using dilations in the preceding discussion. It is natural to wonder whether one could replace ${d}$ by ${D}$ in (4), but it can be easily shown that the exponent ${d}$ is best possible (an observation that essentially appeared first in this paper of Monti). Indeed, working in the Heisenberg group for sake of concreteness, consider the set

$\displaystyle A := \{ \begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix}: |x|, |y| \leq N, |z| \leq N^{10} \}$

for some large parameter ${N}$. This set has measure ${N^{12}}$ using the standard Haar measure on ${G}$. The product set ${A \cdot A}$ is contained in

$\displaystyle A := \{ \begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix}: |x|, |y| \leq 2N, |z| \leq 2N^{10} + O(N^2) \}$

and thus has measure at most ${8N^{12} + O(N^4)}$. This already shows that the exponent in (4) cannot be improved beyond ${d=3}$; note that the homogeneous dimension ${D=4}$ is making its presence known in the ${O(N^4)}$ term in the measure of ${A \cdot A}$, but this is a lower order term only.

It is somewhat unfortunate that the nilpotent Brunn-Minkowski inequality is adapted to the topological dimension rather than the homogeneous one, because it means that some of the applications of the inequality (such as the application to isoperimetric inequalities mentioned at the start of the post) break down. (Indeed, the topic of isoperimetric inequalities for the Heisenberg group is a subtle one, with many naive formulations of the inequality being false. See the paper of Monti for more discussion.)

Remark 2 The inequality can be extended to non-simply-connected connected nilpotent groups ${G}$, if ${d}$ is now set to the dimension of the largest simply connected quotient of ${G}$. It seems to me that this is the best one can do in general; for instance, if ${G}$ is a torus, then the inequality fails for any ${d>0}$, as can be seen by setting ${A=B=G}$.

Remark 3 Specialising the nilpotent Brunn-Minkowski inequality to the case ${A=B}$, we conclude that

$\displaystyle \mu(A \cdot A) \geq 2^d \mu(A).$

This inequality actually has a much simpler proof (attributed to Tsachik Gelander in this paper of Hrushovski, as pointed out to me by Emmanuel Breuillard): one can show that for a connected, simply connected Lie group ${G}$, the exponential map ${\exp: {\mathfrak g} \rightarrow G}$ is a measure-preserving homeomorphism, for some choice of Haar measure ${\mu_{{\mathfrak g}}}$ on ${{\mathfrak g}}$, so it suffices to show that

$\displaystyle \mu_{{\mathfrak g}}(\log(A \cdot A)) \geq 2^d \mu_{{\mathfrak g}}(\log A).$

But ${A \cdot A}$ contains all the squares ${\{a^2: a \in A \}}$ of ${A}$, so ${\log(A \cdot A)}$ contains the isotropic dilation ${2 \cdot \log A}$, and the claim follows. Note that if we set ${A}$ to be a small ball around the origin, we can modify this argument to give another demonstration of why the topological dimension ${d}$ cannot be replaced with any larger exponent in (4).

One may tentatively conjecture that the inequality ${\mu(A \cdot A) \geq 2^d \mu(A)}$ in fact holds in all unimodular connected, simply connected Lie groups ${G}$, and all bounded open subsets ${A}$ of ${G}$; I do not know if this bound is always true, however.

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

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

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

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

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

Let me illustrate what I mean by these two principles with two simple examples, one in the continuous setting and one in the discrete setting. We begin with a continuous example. Given an ${n \times n}$ complex matrix ${A \in M_n({\bf C})}$, define the matrix exponential ${\exp(A)}$ of ${A}$ by the formula

$\displaystyle \exp(A) := \sum_{k=0}^\infty \frac{A^k}{k!} = 1 + A + \frac{1}{2!} A^2 + \frac{1}{3!} A^3 + \ldots$

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

Exercise 1 Show that the map ${A \mapsto \exp(A)}$ is a real analytic (and even complex analytic) map from ${M_n({\bf C})}$ to ${M_n({\bf C})}$, and obeys the restricted homomorphism property

$\displaystyle \exp(sA) \exp(tA) = \exp((s+t)A) \ \ \ \ \ (1)$

for all ${A \in M_n({\bf C})}$ and ${s,t \in {\bf C}}$.

Proposition 1 (Rigidity and structure of matrix homomorphisms) Let ${n}$ be a natural number. Let ${GL_n({\bf C})}$ be the group of invertible ${n \times n}$ complex matrices. Let ${\Phi: {\bf R} \rightarrow GL_n({\bf C})}$ be a map obeying two properties:

• (Group-like object) ${\Phi}$ is a homomorphism, thus ${\Phi(s) \Phi(t) = \Phi(s+t)}$ for all ${s,t \in {\bf R}}$.
• (Weak regularity) The map ${t \mapsto \Phi(t)}$ is continuous.

Then:

• (Strong regularity) The map ${t \mapsto \Phi(t)}$ is smooth (i.e. infinitely differentiable). In fact it is even real analytic.
• (Lie-type structure) There exists a (unique) complex ${n \times n}$ matrix ${A}$ such that ${\Phi(t) = \exp(tA)}$ for all ${t \in {\bf R}}$.

Proof: Let ${\Phi}$ be as above. Let ${\epsilon > 0}$ be a small number (depending only on ${n}$). By the homomorphism property, ${\Phi(0) = 1}$ (where we use ${1}$ here to denote the identity element of ${GL_n({\bf C})}$), and so by continuity we may find a small ${t_0>0}$ such that ${\Phi(t) = 1 + O(\epsilon)}$ for all ${t \in [-t_0,t_0]}$ (we use some arbitrary norm here on the space of ${n \times n}$ matrices, and allow implied constants in the ${O()}$ notation to depend on ${n}$).

The map ${A \mapsto \exp(A)}$ is real analytic and (by the inverse function theorem) is a diffeomorphism near ${0}$. Thus, by the inverse function theorem, we can (if ${\epsilon}$ is small enough) find a matrix ${B}$ of size ${B = O(\epsilon)}$ such that ${\Phi(t_0) = \exp(B)}$. By the homomorphism property and (1), we thus have

$\displaystyle \Phi(t_0/2)^2 = \Phi(t_0) = \exp(B) = \exp(B/2)^2.$

On the other hand, by another application of the inverse function theorem we see that the squaring map ${A \mapsto A^2}$ is a diffeomorphism near ${1}$ in ${GL_n({\bf C})}$, and thus (if ${\epsilon}$ is small enough)

$\displaystyle \Phi(t_0/2) = \exp(B/2).$

We may iterate this argument (for a fixed, but small, value of ${\epsilon}$) and conclude that

$\displaystyle \Phi(t_0/2^k) = \exp(B/2^k)$

for all ${k = 0,1,2,\ldots}$. By the homomorphism property and (1) we thus have

$\displaystyle \Phi(qt_0) = \exp(qB)$

whenever ${q}$ is a dyadic rational, i.e. a rational of the form ${a/2^k}$ for some integer ${a}$ and natural number ${k}$. By continuity we thus have

$\displaystyle \Phi(st_0) = \exp(sB)$

for all real ${s}$. Setting ${A := B/t_0}$ we conclude that

$\displaystyle \Phi(t) = \exp(tA)$

for all real ${t}$, which gives existence of the representation and also real analyticity and smoothness. Finally, uniqueness of the representation ${\Phi(t) = \exp(tA)}$ follows from the identity

$\displaystyle A = \frac{d}{dt} \exp(tA)|_{t=0}.$

$\Box$

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

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

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

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

• (Group-like object) ${G}$ is a group.
• (Discreteness) ${G}$ is finite.
• (Lie-type structure) ${G}$ is contained in ${U_n({\bf C})}$ (the group of unitary ${n \times n}$ matrices) for some ${n}$.

Then there is a subgroup ${G'}$ of ${G}$ such that

• (${G'}$ is close to ${G}$) The index ${|G/G'|}$ of ${G'}$ in ${G}$ is ${O_n(1)}$ (i.e. bounded by ${C_n}$ for some quantity ${C_n}$ depending only on ${n}$).
• (Nilpotent-type structure) ${G'}$ is abelian.

A key observation in the proof of Jordan’s theorem is that if two unitary elements ${g, h \in U_n({\bf C})}$ are close to the identity, then their commutator ${[g,h] = g^{-1}h^{-1}gh}$ is even closer to the identity (in, say, the operator norm ${\| \|_{op}}$). Indeed, since multiplication on the left or right by unitary elements does not affect the operator norm, we have

$\displaystyle \| [g,h] - 1 \|_{op} = \| gh - hg \|_{op}$

$\displaystyle = \| (g-1)(h-1) - (h-1)(g-1) \|_{op}$

and so by the triangle inequality

$\displaystyle \| [g,h] - 1 \|_{op} \leq 2 \|g-1\|_{op} \|h-1\|_{op}. \ \ \ \ \ (2)$

Now we can prove Jordan’s theorem.

Proof: We induct on ${n}$, the case ${n=1}$ being trivial. Suppose first that ${G}$ contains a central element ${g}$ which is not a multiple of the identity. Then, by definition, ${G}$ is contained in the centraliser ${Z(g)}$ of ${g}$, which by the spectral theorem is isomorphic to a product ${U_{n_1}({\bf C}) \times \ldots \times U_{n_k}({\bf C})}$ of smaller unitary groups. Projecting ${G}$ to each of these factor groups and applying the induction hypothesis, we obtain the claim.

Thus we may assume that ${G}$ contains no central elements other than multiples of the identity. Now pick a small ${\epsilon > 0}$ (one could take ${\epsilon=\frac{1}{10d}}$ in fact) and consider the subgroup ${G'}$ of ${G}$ generated by those elements of ${G}$ that are within ${\epsilon}$ of the identity (in the operator norm). By considering a maximal ${\epsilon}$-net of ${G}$ we see that ${G'}$ has index at most ${O_{n,\epsilon}(1)}$ in ${G}$. By arguing as before, we may assume that ${G'}$ has no central elements other than multiples of the identity.

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

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

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

Exercise 4 (Inability to discretise nonabelian Lie groups) Show that if ${n \geq 3}$, then the orthogonal group ${O_n({\bf R})}$ cannot contain arbitrarily dense finite subgroups, in the sense that there exists an ${\epsilon = \epsilon_n > 0}$ depending only on ${n}$ such that for every finite subgroup ${G}$ of ${O_n({\bf R})}$, there exists a ball of radius ${\epsilon}$ in ${O_n({\bf R})}$ (with, say, the operator norm metric) that is disjoint from ${G}$. What happens in the ${n=2}$ case?

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

A celebrated theorem of Gromov reads:

Theorem 1 Every finitely generated group of polynomial growth is virtually nilpotent.

The original proof of Gromov’s theorem was quite non-elementary, using an infinitary limit and exploiting the work surrounding the solution to Hilbert’s fifth problem. More recently, Kleiner provided a proof which was more elementary (based in large part on an earlier paper of Colding and Minicozzi), though still not entirely so, relying in part on (a weak form of the) Tits alternative and also on an ultrafilter argument of Korevaar-Schoen and Mok. I discuss Kleiner’s argument more in this previous blog post.

Recently, Yehuda Shalom and I established a quantitative version of Gromov’s theorem by making every component of Kleiner’s argument finitary. Technically, this provides a fully elementary proof of Gromov’s theorem (we do use one infinitary limit to simplify the argument a little bit, but this is not truly necessary); however, because we were trying to quantify as much of the result as possible, the argument became quite lengthy.

In this note I want to record a short version of the argument of Yehuda and myself which is not quantitative, but gives a self-contained and largely elementary proof of Gromov’s theorem. The argument is not too far from the Kleiner argument, but has a number of simplifications at various places. In a number of places, there was a choice to take between a short argument that was “inefficient” in the sense that it did not lead to a good quantitative bound, and a lengthier argument which led to better quantitative bounds. I have opted for the former in all such cases.

Yehuda and I plan to write a short paper containing this argument as well as some additional material, but due to some interest in this particular proof, we are detailing it here on this blog in advance of our paper.

Note: this post will assume familiarity with the basic terminology of group theory, and will move somewhat quickly through the technical details.

In mathematics, one frequently starts with some space ${X}$ and wishes to extend it to a larger space ${Y}$. Generally speaking, there are two ways in which one can extend a space ${X}$:

• By embedding ${X}$ into a space ${Y}$ that has ${X}$ (or at least an isomorphic copy of ${X}$) as a subspace.
• By covering ${X}$ by a space ${Y}$ that has ${X}$ (or an isomorphic copy thereof) as a quotient.

For many important categories of interest (such as abelian categories), the former type of extension can be represented by the exact sequence,

$\displaystyle 0 \rightarrow X \rightarrow Y$

and the latter type of extension be represented by the exact sequence

$\displaystyle Y \rightarrow X \rightarrow 0.$

In some cases, ${X}$ can be both embedded in, and covered by, ${Y}$, in a consistent fashion; in such cases we sometimes say that the above exact sequences split.

An analogy would be to that of digital images. When a computer represents an image, it is limited both by the scope of the image (what it is picturing), and by the resolution of an image (how much physical space is represented by a given pixel). To make the image “larger”, one could either embed the image in an image of larger scope but equal resolution (e.g. embedding a picture of a ${200 \times 200}$ pixel image of person’s face into a ${800 \times 800}$ pixel image that covers a region of space that is four times larger in both dimensions, e.g. the person’s upper body) or cover the image with an image of higher resolution but of equal scope (e.g. enhancing a ${200 \times 200}$ pixel picture of a face to a ${800 \times 800}$ pixel of the same face). In the former case, the original image is a sub-image (or cropped image) of the extension, but in the latter case the original image is a quotient (or a pixelation) of the extension. In the former case, each pixel in the original image can be identified with a pixel in the extension, but not every pixel in the extension is covered. In the latter case, every pixel in the original image is covered by several pixels in the extension, but the pixel in the original image is not canonically identified with any particular pixel in the extension that covers it; it “loses its identity” by dispersing into higher resolution pixels.

(Note that “zooming in” the visual representation of an image by making each pixel occupy a larger region of the screen neither increases the scope or the resolution; in this language, a zoomed-in version of an image is merely an isomorphic copy of the original image; it carries the same amount of information as the original image, but has been represented in a new coordinate system which may make it easier to view, especially to the visually impaired.)

In the study of a given category of spaces (e.g. topological spaces, manifolds, groups, fields, etc.), embedding and coverings are both important; this is particularly true in the more topological areas of mathematics, such as manifold theory. But typically, the term extension is reserved for just one of these two operations. For instance, in the category of fields, coverings are quite trivial; if one covers a field ${k}$ by a field ${l}$, the kernel of the covering map ${\pi: l \rightarrow k}$ is necessarily trivial and so ${k, l}$ are in fact isomorphic. So in field theory, a field extension refers to an embedding of a field, rather than a covering of a field. Similarly, in the theory of metric spaces, there are no non-trivial isometric coverings of a metric space, and so the only useful notion of an extension of a metric space is the one given by embedding the original space in the extension.

On the other hand, in group theory (and in group-like theories, such as the theory of dynamical systems, which studies group actions), the term “extension” is reserved for coverings, rather than for embeddings. I think one of the main reasons for this is that coverings of groups automatically generate a special type of embedding (a normal embedding), whereas most embeddings don’t generate coverings. More precisely, given a group extension ${G}$ of a base group ${H}$,

$\displaystyle G \rightarrow H \rightarrow 0,$

one can form the kernel ${K = \hbox{ker}(\phi)}$ of the covering map ${\pi: G \rightarrow H}$, which is a normal subgroup of ${G}$, and we thus can extend the above sequence canonically to a short exact sequence

$\displaystyle 0 \rightarrow K \rightarrow G \rightarrow H \rightarrow 0.$

On the other hand, an embedding of ${K}$ into ${G}$,

$\displaystyle 0 \rightarrow K \rightarrow G$

does not similarly extend to a short exact sequence unless the the embedding is normal.

Another reason for the notion of extension varying between embeddings and coverings from subject to subject is that there are various natural duality operations (and more generally, contravariant functors) which turn embeddings into coverings and vice versa. For instance, an embedding of one vector space ${V}$ into another ${W}$ induces a covering of the dual space ${V^*}$ by the dual space ${W^*}$, and conversely; similarly, an embedding of a locally compact abelian group ${H}$ in another ${G}$ induces a covering of the Pontryagin dual ${\hat H}$ by the Pontryagin dual ${\hat G}$. In the language of images, embedding an image in an image of larger scope is largely equivalent to covering the Fourier transform of that image by a transform of higher resolution, and conversely; this is ultimately a manifestation of the basic fact that frequency is inversely proportional to wavelength.

Similarly, a common duality operation arises in many areas of mathematics by starting with a space ${X}$ and then considering a space ${C(X)}$ of functions on that space (e.g. continuous real-valued functions, if ${X}$ was a topological space, or in more algebraic settings one could consider homomorphisms from ${X}$ to some fixed space). Embedding ${X}$ into ${Y}$ then induces a covering of ${C(X)}$ by ${C(Y)}$, and conversely, a covering of ${X}$ by ${Y}$ induces an embedding of ${C(X)}$ into ${C(Y)}$. Returning again to the analogy with images, if one looks at the collection of all images of a fixed scope and resolution, rather than just a single image, then increasing the available resolution causes an embedding of the space of low-resolution images into the space of high-resolution images (since of course every low-resolution image is an example of a high-resolution image), whereas increasing the available scope causes a covering of the space of narrow-scope images by the space of wide-scope images (since every wide-scope image can be cropped into a narrow-scope image). Note in the case of images, that these extensions can be split: not only can a low-resolution image be viewed as a special case of a high-resolution image, but any high-resolution image can be pixelated into a low-resolution one. Similarly, not only can any wide-scope image be cropped into a narrow-scope one, a narrow-scope image can be extended to a wide-scope one simply by filling in all the new areas of scope with black (or by using more advanced image processing tools to create a more visually pleasing extension). (In the category of sets, the statement that every covering can be split is precisely the axiom of choice.)

I’ve recently found myself having to deal quite a bit with group extensions in my research, so I have decided to make some notes on the basic theory of such extensions here. This is utterly elementary material for a group theorist, but I found this task useful for organising my own thoughts on this topic, and also in pinning down some of the jargon in this field.

In a multiplicative group ${G}$, the commutator of two group elements ${g, h}$ is defined as ${[g,h] := g^{-1}h^{-1}gh}$ (other conventions are also in use, though they are largely equivalent for the purposes of this discussion). A group is said to be nilpotent of step ${s}$ (or more precisely, step ${\leq s}$), if all iterated commutators of order ${s+1}$ or higher necessarily vanish. For instance, a group is nilpotent of order ${1}$ if and only if it is abelian, and it is nilpotent of order ${2}$ if and only if ${[[g_1,g_2],g_3]=id}$ for all ${g_1,g_2,g_3}$ (i.e. all commutator elements ${[g_1,g_2]}$ are central), and so forth. A good example of an ${s}$-step nilpotent group is the group of ${s+1 \times s+1}$ upper-triangular unipotent matrices (i.e. matrices with ${1}$s on the diagonal and zero below the diagonal), and taking values in some ring (e.g. reals, integers, complex numbers, etc.).

Another important example of nilpotent groups arise from operations on polynomials. For instance, if ${V_{\leq s}}$ is the vector space of real polynomials of one variable of degree at most ${s}$, then there are two natural affine actions on ${V_{\leq s}}$. Firstly, every polynomial ${Q}$ in ${V_{\leq s}}$ gives rise to an “vertical” shift ${P \mapsto P+Q}$. Secondly, every ${h \in {\bf R}}$ gives rise to a “horizontal” shift ${P \mapsto P(\cdot+h)}$. The group generated by these two shifts is a nilpotent group of step ${\leq s}$; this reflects the well-known fact that a polynomial of degree ${\leq s}$ vanishes once one differentiates more than ${s}$ times. Because of this link between nilpotentcy and polynomials, one can view nilpotent algebra as a generalisation of polynomial algebra.

Suppose one has a finite number ${g_1,\ldots,g_n}$ of generators. Using abstract algebra, one can then construct the free nilpotent group ${{\mathcal F}_{\leq s}(g_1,\ldots,g_n)}$ of step ${\leq s}$, defined as the group generated by the ${g_1,\ldots,g_n}$ subject to the relations that all commutators of order ${s+1}$ involving the generators are trivial. This is the universal object in the category of nilpotent groups of step ${\leq s}$ with ${n}$ marked elements ${g_1,\ldots,g_n}$. In other words, given any other ${\leq s}$-step nilpotent group ${G'}$ with ${n}$ marked elements ${g'_1,\ldots,g'_n}$, there is a unique homomorphism from the free nilpotent group to ${G'}$ that maps each ${g_j}$ to ${g'_j}$ for ${1 \leq j \leq n}$. In particular, the free nilpotent group is well-defined up to isomorphism in this category.

In many applications, one wants to have a more concrete description of the free nilpotent group, so that one can perform computations more easily (and in particular, be able to tell when two words in the group are equal or not). This is easy for small values of ${s}$. For instance, when ${s=1}$, ${{\mathcal F}_{\leq 1}(g_1,\ldots,g_n)}$ is simply the free abelian group generated by ${g_1,\ldots,g_n}$, and so every element ${g}$ of ${{\mathcal F}_{\leq 1}(g_1,\ldots,g_n)}$ can be described uniquely as

$\displaystyle g = \prod_{j=1}^n g_j^{m_j} := g_1^{m_1} \ldots g_n^{m_n} \ \ \ \ \ (1)$

for some integers ${m_1,\ldots,m_n}$, with the obvious group law. Indeed, to obtain existence of this representation, one starts with any representation of ${g}$ in terms of the generators ${g_1,\ldots,g_n}$, and then uses the abelian property to push the ${g_1}$ factors to the far left, followed by the ${g_2}$ factors, and so forth. To show uniqueness, we observe that the group ${G}$ of formal abelian products ${\{ g_1^{m_1} \ldots g_n^{m_n}: m_1,\ldots,m_n \in {\bf Z} \} \equiv {\bf Z}^k}$ is already a ${\leq 1}$-step nilpotent group with marked elements ${g_1,\ldots,g_n}$, and so there must be a homomorphism from the free group to ${G}$. Since ${G}$ distinguishes all the products ${g_1^{m_1} \ldots g_n^{m_n}}$ from each other, the free group must also.

It is only slightly more tricky to describe the free nilpotent group ${{\mathcal F}_{\leq 2}(g_1,\ldots,g_n)}$ of step ${\leq 2}$. Using the identities

$\displaystyle gh = hg [g,h]; \quad gh^{-1} = ([g,h]^{-1})^{g^{-1}} h^{-1} g; \quad g^{-1} h = h [g,h]^{-1} g^{-1}; \quad g^{-1} h^{-1} := [g,h] g^{-1} h^{-1}$

(where ${g^h := h^{-1} g h}$ is the conjugate of ${g}$ by ${h}$) we see that whenever ${1 \leq i < j \leq n}$, one can push a positive or negative power of ${g_i}$ past a positive or negative power of ${g_j}$, at the cost of creating a positive or negative power of ${[g_i,g_j]}$, or one of its conjugates. Meanwhile, in a ${\leq 2}$-step nilpotent group, all the commutators are central, and one can pull all the commutators out of a word and collect them as in the abelian case. Doing all this, we see that every element ${g}$ of ${{\mathcal F}_{\leq 2}(g_1,\ldots,g_n)}$ has a representation of the form

$\displaystyle g = (\prod_{j=1}^n g_j^{m_j}) (\prod_{1 \leq i < j \leq n} [g_i,g_j]^{m_{[i,j]}}) \ \ \ \ \ (2)$

for some integers ${m_j}$ for ${1 \leq j \leq n}$ and ${m_{[i,j]}}$ for ${1 \leq i < j \leq n}$. Note that we don’t need to consider commutators ${[g_i,g_j]}$ for ${i \geq j}$, since

$\displaystyle [g_i,g_i] = id$

and

$\displaystyle [g_i,g_j] = [g_j,g_i]^{-1}.$

It is possible to show also that this representation is unique, by repeating the previous argument, i.e. by showing that the set of formal products

$\displaystyle G := \{ (\prod_{j=1}^k g_j^{m_j}) (\prod_{1 \leq i < j \leq n} [g_i,g_j]^{m_{[i,j]}}): m_j, m_{[i,j]} \in {\bf Z} \}$

forms a ${\leq 2}$-step nilpotent group, after using the above rules to define the group operations. This can be done, but verifying the group axioms (particularly the associative law) for ${G}$ is unpleasantly tedious.

Once one sees this, one rapidly loses an appetite for trying to obtain a similar explicit description for free nilpotent groups for higher step, especially once one starts seeing that higher commutators obey some non-obvious identities such as the Hall-Witt identity

$\displaystyle [[g, h^{-1}], k]^h\cdot[[h, k^{-1}], g]^k\cdot[[k, g^{-1}], h]^g = 1 \ \ \ \ \ (3)$

(a nonlinear version of the Jacobi identity in the theory of Lie algebras), which make one less certain as to the existence or uniqueness of various proposed generalisations of the representations (1) or (2). For instance, in the free ${\leq 3}$-step nilpotent group, it turns out that for representations of the form

$\displaystyle g = (\prod_{j=1}^n g_j^{m_j}) (\prod_{1 \leq i < j \leq n} [g_i,g_j]^{m_{[i,j]}}) (\prod_{1 \leq i < j < k \leq n} [[g_i,g_j],g_k]^{n_{[[i,j],k]}})$

one has uniqueness but not existence (e.g. even in the simplest case ${n=3}$, there is no place in this representation for, say, ${[[g_1,g_3],g_2]}$ or ${[[g_1,g_2],g_2]}$), but if one tries to insert more triple commutators into the representation to make up for this, one has to be careful not to lose uniqueness due to identities such as (3). One can paste these in by ad hoc means in the ${s=3}$ case, but the ${s=4}$ case looks more fearsome still, especially now that the quadruple commutators split into several distinct-looking species such as ${[[g_i,g_j],[g_k,g_l]]}$ and ${[[[g_i,g_j],g_k],g_l]}$ which are nevertheless still related to each other by identities such as (3). While one can eventually disentangle this mess for any fixed ${n}$ and ${s}$ by a finite amount of combinatorial computation, it is not immediately obvious how to give an explicit description of ${{\mathcal F}_{\leq s}(g_1,\ldots,g_n)}$ uniformly in ${n}$ and ${s}$.

Nevertheless, it turns out that one can give a reasonably tractable description of this group if one takes a polycyclic perspective rather than a nilpotent one – i.e. one views the free nilpotent group as a tower of group extensions of the trivial group by the cyclic group ${{\bf Z}}$. This seems to be a fairly standard observation in group theory – I found it in this book of Magnus, Karrass, and Solitar, via this paper of Leibman – but seems not to be so widely known outside of that field, so I wanted to record it here.

### Recent Comments

 Sean Eberhard on The Erdos-Ulam problem, variet… Sean Eberhard on The Erdos-Ulam problem, variet… Eytan Paldi on Long gaps between primes Eytan Paldi on Long gaps between primes Anthony Quas on 254A, Notes 2: Complex-analyti… Matthew Cory on 254A, Supplement 3: The Gamma… Anthony Quas on 254A, Notes 2: Complex-analyti… Anthony Quas on 254A, Notes 2: Complex-analyti… Anthony Quas on 254A, Notes 2: Complex-analyti… Anthony Quas on 254A, Notes 2: Complex-analyti… Kyle Pratt on Long gaps between primes Matthew Cory on 254A, Supplement 3: The Gamma… Kyle Pratt on Long gaps between primes Fan on Long gaps between primes Eytan Paldi on Long gaps between primes