Category Archive

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

254B, Notes 5: Product theorems, pivot arguments, and the Larsen-Pink non-concentration inequality

5 February, 2012 in 254B - expansion in groups, math.AG, math.CO, math.GR | Tags: Larsen-Pink inequality, product theorems, special linear group, sum-product theorems, ultraproducts | by Terence Tao | 9 comments

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 ${A}$ of a group ${G}$ either exhibits expansion (in the sense that ${A^3}$ , say, is significantly larger than ${A}$ ), or is somehow “close to” or “trapped” by a genuine group.

Theorem 1 (Product theorem in ${SL_d(k)}$ ) Let ${d \geq 2}$ , let ${k}$ be a finite field, and let ${A}$ be a finite subset of ${G := SL_d(k)}$ . Let ${\epsilon >0}$ be sufficiently small depending on ${d}$ . Then at least one of the following statements holds:

(Expansion) One has ${|A^3| \geq |A|^{1+\epsilon}}$ .

(Close to ${G}$ ) One has ${|A| \geq |G|^{1-O_d(\epsilon)}}$ .

(Trapping) ${A}$ is contained in a proper subgroup of ${G}$ .

We will prove this theorem (which was proven first in the ${d=2,3}$ cases for fields ${F}$ of prime order by Helfgott, and then for ${d=2}$ and general ${F}$ by Dinai, and finally to general ${d}$ and ${F}$ 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 ${k}$ is replaced by a cyclic ring ${{\bf Z}/q{\bf Z}}$ (with ${q}$ not necessarily prime); this was achieved first for ${d=2}$ and ${q}$ square-free by Bourgain, Gamburd, and Sarnak, by Varju for general ${d}$ and ${q}$ square-free, and finally by this paper of Bourgain and Varju for arbitrary ${d}$ and ${q}$ .

Exercise 1 (Girth bound) Assuming Theorem 1, show that whenever ${S}$ is a symmetric set of generators of ${SL_d(k)}$ for some finite field ${k}$ and some ${d\geq 2}$ , then any element of ${SL_d(k)}$ can be expressed as the product of ${O_d( \log^{O_d(1)} |k| )}$ elements from ${S}$ . (Equivalently, if we add the identity element to ${S}$ , then ${S^m = SL_d(k)}$ for some ${m = O_d( \log^{O_d(1)} |k| )}$ .) 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 ${d}$ . The methods used to handle the ${SL_d}$ 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_n}$ .

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 ${G}$ :

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

(Expansion) One has ${|A^{-1} A| \geq \frac{3}{2} |A|}$ .

(Close to a subgroup) ${A}$ is contained in a left-coset of a group ${H}$ with ${|H| < \frac{3}{2} |A|}$ .

To prove this theorem, we suppose that the first conclusion does not hold, thus ${|A^{-1} A| <\frac{3}{2} |A|}$ . Our task is then to place ${A}$ inside the left-coset of a fairly small group ${H}$ .

To do this, we take a group element ${g \in G}$ , and consider the intersection ${A\cap gA}$ . A priori, the size of this set could range from anywhere from ${0}$ to ${|A|}$ . However, we can use the hypothesis ${|A^{-1} A| < \frac{3}{2} |A|}$ to obtain an important dichotomy, reminiscent of the classical fact that two cosets ${gH, hH}$ of a subgroup ${H}$ of ${G}$ are either identical or disjoint:

Proposition 3 (Dichotomy) If ${g \in G}$ , then exactly one of the following occurs:

(Non-involved case) ${A \cap gA}$ is empty.

(Involved case) ${|A \cap gA| > \frac{|A|}{2}}$ .

Proof: Suppose we are not in the pivot case, so that ${A \cap gA}$ is non-empty. Let ${a}$ be an element of ${A \cap gA}$ , then ${a}$ and ${g^{-1} a}$ both lie in ${A}$ . The sets ${A^{-1} a}$ and ${A^{-1} g^{-1} a}$ then both lie in ${A^{-1} A}$ . As these sets have cardinality ${|A|}$ and lie in ${A^{-1}A}$ , which has cardinality less than ${\frac{3}{2}|A|}$ , we conclude from the inclusion-exclusion formula that

$\displaystyle |A^{-1} a \cap A^{-1} g^{-1} a| > \frac{|A|}{2}.$

But the left-hand side is equal to ${|A \cap gA|}$ , and the claim follows. $\Box$

The above proposition provides a clear separation between two types of elements ${g \in G}$ : the “non-involved” elements, which have nothing to do with ${A}$ (in the sense that ${A \cap gA = \emptyset}$ , and the “involved” elements, which have a lot to do with ${A}$ (in the sense that ${|A \cap gA| > |A|/2}$ . 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 ${A}$ and ${gA}$ intersect a little but not a lot. It is this gap that will allow us to upgrade approximate structure to exact structure. Namely,

Proposition 4 The set ${H}$ of involved elements is a finite group, and is equal to ${A A^{-1}}$ .

Proof: It is clear that the identity element ${1}$ is involved, and that if ${g}$ is involved then so is ${g^{-1}}$ (since ${A \cap g^{-1} A = g^{-1}(A \cap gA)}$ . Now suppose that ${g, h}$ are both involved. Then ${A \cap gA}$ and ${A\cap hA}$ have cardinality greater than ${|A|/2}$ and are both subsets of ${A}$ , and so have non-empty intersection. In particular, ${gA \cap hA}$ is non-empty, and so ${A \cap g^{-1} hA}$ is non-empty. By Proposition 3, this makes ${g^{-1} h}$ involved. It is then clear that ${H}$ is a group.

If ${g \in A A^{-1}}$ , then ${A \cap gA}$ is non-empty, and so from Proposition 3 ${g}$ is involved. Conversely, if ${g}$ is involved, then ${g \in A A^{-1}}$ . Thus we have ${H = A A^{-1}}$ as claimed. In particular, ${H}$ is finite. $\Box$

Now we can quickly wrap up the proof of Theorem 2. By construction, ${A \cap gA| > |A|/2}$ for all ${g \in H}$ ,which by double counting shows that ${|H| < 2|A|}$ . As ${H = A A^{-1}}$ , we see that ${A}$ is contained in a right coset ${Hg}$ of ${H}$ ; setting ${H' := g^{-1} H g}$ , we conclude that ${A}$ is contained in a left coset ${gH'}$ of ${H'}$ . ${H'}$ is a conjugate of ${H}$ , and so ${|H'| < 2|A|}$ . If ${h \in H'}$ , then ${A}$ and ${Ah}$ both lie in ${H'}$ and have cardinality ${|A|}$ , so must overlap; and so ${h \in A A^{-1}}$ . Thus ${A A^{-1} = H'}$ , and so ${|H'| < \frac{3}{2} |A|}$ , and Theorem 2 follows.

Exercise 2 Show that the constant ${3/2}$ in Theorem 2 cannot be replaced by any larger constant.

Exercise 3 Let ${A \subset G}$ be a finite non-empty set such that ${|A^2| < 2|A|}$ . Show that ${AA^{-1}=A^{-1} A}$ . (Hint: If ${ab^{-1} \in A A^{-1}}$ , show that ${ab^{-1} = c^{-1} d}$ for some ${c,d \in A}$ .)

Exercise 4 Let ${A \subset G}$ be a finite non-empty set such that ${|A^2| < \frac{3}{2} |A|}$ . Show that there is a finite group ${H}$ with ${|H| < \frac{3}{2} |A|}$ and a group element ${g \in G}$ such that ${A \subset Hg \cap gH}$ and ${H = A A^{-1}}$ .

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.

Read the rest of this entry »

A nilpotent Freiman dimension lemma

21 December, 2011 in math.CO, math.GR, paper | Tags: Ben Green, Emmanuel Breuillard, freiman theorems, nilpotent groups | by Terence Tao | 1 comment

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.

254B, Notes 3: Quasirandom groups, expansion, and Selberg’s 3/16 theorem

16 December, 2011 in 254B - expansion in groups, math.AP, math.GR, math.NT, math.RT, math.SP | Tags: eigenfunctions, hyperbolic space, quasirandom groups, random walks | by Terence Tao | 21 comments

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 ${SL_d({\bf Z})}$ or ${SL_d({\bf R})}$ , 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 ${G}$ be a finite group, and let ${D \geq 1}$ . We say that ${G}$ is ${D}$ -quasirandom if all non-trivial unitary representations ${\rho: G \rightarrow U(H)}$ of ${G}$ have dimension at least ${D}$ . (Recall a representation is trivial if ${\rho(g)}$ is the identity for all ${g \in G}$ .)

Exercise 1 Let ${G}$ be a finite group, and let ${D \geq 1}$ . A unitary representation ${\rho: G \rightarrow U(H)}$ is said to be irreducible if ${H}$ has no ${G}$ -invariant subspaces other than ${\{0\}}$ and ${H}$ . Show that ${G}$ is ${D}$ -quasirandom if and only if every non-trivial irreducible representation of ${G}$ has dimension at least ${D}$ .

Remark 1 The 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 ${SL_2({\bf R})}$ to obtain mixing estimates in that group.)

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

Exercise 2 Let ${0 \rightarrow H \rightarrow G \rightarrow K \rightarrow 0}$ be a short exact sequence of finite groups ${H,G,K}$ .

(i) If ${G}$ is ${D}$ -quasirandom, show that ${K}$ is ${D}$ -quasirandom also. (Equivalently: any quotient of a ${D}$ -quasirandom finite group is again a ${D}$ -quasirandom finite group.)

(ii) Conversely, if ${H}$ and ${K}$ are both ${D}$ -quasirandom, show that ${G}$ is ${D}$ -quasirandom also. (In particular, the direct or semidirect product of two ${D}$ -quasirandom finite groups is again a ${D}$ -quasirandom finite group.)

Informally, we will call ${G}$ quasirandom if it is ${D}$ -quasirandom for some “large” ${D}$ , though the precise meaning of “large” will depend on context. For applications to expansion in Cayley graphs, “large” will mean “ ${D \geq |G|^c}$ for some constant ${c>0}$ independent of the size of ${G}$ “, but other regimes of ${D}$ are certainly of interest.

The way we have set things up, the trivial group ${G = \{1\}}$ is infinitely quasirandom (i.e. it is ${D}$ -quasirandom for every ${D}$ ). 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 3 Let ${D \geq 1}$ , and let ${G}$ be a finite ${D}$ -quasirandom group.

(i) Show that if ${G}$ is non-trivial, then ${|G| \geq D+1}$ . (Hint: use the mean zero component ${\tau\downharpoonright_{\ell^2(G)_0}}$ of the regular representation ${\tau: G \rightarrow U(\ell^2(G))}$ .) In particular, non-trivial finite groups cannot be infinitely quasirandom.

(ii) Show that any proper subgroup ${H}$ of ${G}$ has index ${[G:H] \geq D+1}$ . (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 ${G}$ be a finite group.

(i) If ${G}$ is abelian and non-trivial, show that ${G}$ is not ${2}$ -quasirandom. (Hint: use Fourier analysis or the classification of finite abelian groups.)

(ii) Show that ${G}$ is ${2}$ -quasirandom if and only if it is perfect, i.e. the commutator group ${[G,G]}$ is equal to ${G}$ . (Equivalently, ${G}$ is ${2}$ -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 5 Let ${G}$ be a finite ${D}$ -quasirandom group. Show that for any subgroup ${G'}$ of ${G}$ , ${G'}$ is ${D/[G:G']}$ -quasirandom, where ${[G:G'] := |G|/|G'|}$ is the index of ${G'}$ in ${G}$ . (Hint: use induced representations.)

Now we give an example of a more quasirandom group.

Lemma 2 (Frobenius lemma) If ${F_p}$ is a field of some prime order ${p}$ , then ${SL_2(F_p)}$ is ${\frac{p-1}{2}}$ -quasirandom.

This should be compared with the cardinality ${|SL_2(F_p)|}$ of the special linear group, which is easily computed to be ${(p^2-1) \times p = p^3 - p}$ .

Proof: We may of course take ${p}$ to be odd. Suppose for contradiction that we have a non-trivial representation ${\rho: SL_2(F_p) \rightarrow U_d({\bf C})}$ on a unitary group of some dimension ${d}$ with ${d < \frac{p-1}{2}}$ . Set ${a}$ to be the group element

$\displaystyle a := \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix},$

and suppose first that ${\rho(a)}$ is non-trivial. Since ${a^p=1}$ , we have ${\rho(a)^p=1}$ ; thus all the eigenvalues of ${\rho(a)}$ are ${p^{th}}$ roots of unity. On the other hand, by conjugating ${a}$ by diagonal matrices in ${SL_2(F_p)}$ , we see that ${a}$ is conjugate to ${a^m}$ (and hence ${\rho(a)}$ conjugate to ${\rho(a)^m}$ ) whenever ${m}$ is a quadratic residue mod ${p}$ . As such, the eigenvalues of ${\rho(a)}$ must be permuted by the operation ${x \mapsto x^m}$ for any quadratic residue mod ${p}$ . Since ${\rho(a)}$ has at least one non-trivial eigenvalue, and there are ${\frac{p-1}{2}}$ distinct quadratic residues, we conclude that ${\rho(a)}$ has at least ${\frac{p-1}{2}}$ distinct eigenvalues. But ${\rho(a)}$ is a ${d \times d}$ matrix with ${d < \frac{p-1}{2}}$ , a contradiction. Thus ${a}$ lies in the kernel of ${\rho}$ . By conjugation, we then see that this kernel contains all unipotent matrices. But these matrices generate ${SL_2(F_p)}$ (see exercise below), and so ${\rho}$ is trivial, a contradiction. $\Box$

Exercise 6 Show that for any prime ${p}$ , the unipotent matrices
$\displaystyle \begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix}, \begin{pmatrix} 1 & 0 \\ t & 1 \end{pmatrix}$

for ${t}$ ranging over ${F_p}$ generate ${SL_2(F_p)}$ as a group.

Exercise 7 Let ${G}$ be a finite group, and let ${D \geq 1}$ . If ${G}$ is generated by a collection ${G_1,\ldots,G_k}$ of ${D}$ -quasirandom subgroups, show that ${G}$ is itself ${D}$ -quasirandom.

Exercise 8 Show that ${SL_d(F_p)}$ is ${\frac{p-1}{2}}$ -quasirandom for any ${d \geq 2}$ and any prime ${p}$ . (This is not sharp; the optimal bound here is ${\gg_d p^{d-1}}$ , 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 ${PSL_d(F_p)}$ is also ${\frac{p-1}{2}}$ -quasirandom.

Remark 2 One can ask whether the bound ${\frac{p-1}{2}}$ in Lemma 2 is sharp, assuming of course that ${p}$ is odd. Noting that ${SL_2(F_p)}$ acts linearly on the plane ${F_p^2}$ , we see that it also acts projectively on the projective line ${PF_p^1 := (F_p^2 \backslash \{0\}) / F_p^\times}$ , which has ${p+1}$ elements. Thus ${SL_2(F_p)}$ acts via the quasiregular representation on the ${p+1}$ -dimensional space ${\ell^2(PF_p^1)}$ , and also on the ${p}$ -dimensional subspace ${\ell^2(PF_p^1)_0}$ ; this latter representation (known as the Steinberg representation) is irreducible. This shows that the ${\frac{p-1}{2}}$ bound cannot be improved beyond ${p}$ . More generally, given any character ${\chi: F_p^\times \rightarrow S^1}$ , ${SL_2(F_p)}$ acts on the ${p+1}$ -dimensional space ${V_\chi}$ of functions ${f \in \ell^2( F_p^2 \backslash \{0\} )}$ that obey the twisted dilation invariance ${f(tx) = \chi(t) f(x)}$ for all ${t \in F_p^\times}$ and ${x \in F_p^2 \backslash \{0\}}$ ; these are known as the principal series representations. When ${\chi}$ 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 ${\chi}$ is the quadratic representation (thus taking values in ${\{-1,+1\}}$ while being non-trivial), the principal series representation splits into the direct sum of two ${\frac{p+1}{2}}$ -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 ${F_p}$ in a quadratic extension ${F_{p^2}}$ 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 ${\frac{p-1}{2}}$ , 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 9 Let ${p}$ be an odd prime. Show that for any ${n \geq p+2}$ , the alternating group ${A_n}$ is ${p-1}$ -quasirandom. (Hint: show that all cycles of order ${p}$ in ${A_n}$ are conjugate to each other in ${A_n}$ (and not just in ${S_n}$ ); in particular, a cycle is conjugate to its ${j^{th}}$ power for all ${j=1,\ldots,p-1}$ . Also, as ${n \geq 5}$ , ${A_n}$ is simple, and so the cycles of order ${p}$ generate the entire group.)

Remark 3 By 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 ${A_n}$ is ${n-1}$ -quasirandom for ${n \geq 6}$ (but is only ${3}$ -quasirandom for ${n=5}$ due to icosahedral symmetry, and ${1}$ -quasirandom for ${n \leq 4}$ due to lack of perfectness). Using Exercise 3 with the index ${n}$ subgroup ${A_{n-1}}$ , we see that the bound ${n-1}$ cannot be improved. Thus, ${A_n}$ (for large ${n}$ ) is not as quasirandom as the special linear groups ${SL_d(F_p)}$ (for ${p}$ large and ${d}$ 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 ${A_n}$ with the slightly larger symmetric group ${S_n}$ , then quasirandomness is destroyed (since ${S_n}$ , having the abelian quotient ${S_n/A_n}$ , is not perfect); indeed, ${S_n}$ is ${1}$ -quasirandom and no better.

Remark 4 Thanks 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 ${{\bf Z}/p{\bf Z}}$ , an alternating group ${A_n}$ , or is a finite simple group of Lie type such as ${PSL_d(F_p)}$ . (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 ${PSL_d(F_p)}$ is constructed from ${SL_d}$ in characteristic ${p}$ .) In the case of finite simple groups ${G}$ of Lie type with bounded rank ${r=O(1)}$ , it is known from the work of Landazuri and Seitz that such groups are ${\gg |G|^c}$ -quasirandom for some ${c>0}$ 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 ${G}$ is ${|G|^c}$ -quasirandom for some ${c>0}$ and ${|G|}$ is sufficiently large depending on ${c}$ , then ${G}$ is a finite simple group of Lie type with rank ${O_c(1)}$ . 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 ${SL_2({\bf Z}/N{\bf Z})}$ (compare this with the property (T)-based methods in the previous notes, which could construct expander Cayley graphs in ${SL_d({\bf Z}/N{\bf Z})}$ for any fixed ${d \geq 3}$ ).

Read the rest of this entry »

254B, Notes 2: Cayley graphs and Kazhdan’s property (T)

6 December, 2011 in 254B - expansion in groups, math.CA, math.GR, math.RT, math.SP | Tags: Cayley graphs, lattices, Mautner phenomenon, property T, Schreier graphs, special linear group, spectral gap | by Terence Tao | 25 comments

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

Definition 1 (Cayley graph) Let ${G = (G,\cdot)}$ be a group, and let ${S}$ be a finite subset of ${G}$ . We assume that ${S}$ is symmetric (thus ${s^{-1} \in S}$ whenever ${s \in S}$ ) and does not contain the identity ${1}$ (this is to avoid loops). Then the (right-invariant) Cayley graph ${Cay(G,S)}$ is defined to be the graph with vertex set ${G}$ and edge set ${\{ \{sx,x\}: x \in G, s \in S \}}$ , thus each vertex ${x \in G}$ is connected to the ${|S|}$ elements ${sx}$ for ${s \in S}$ , and so ${Cay(G,S)}$ is a ${|S|}$ -regular graph.

Example 1 The graph in Exercise 3 of Notes 1 is the Cayley graph on ${{\bf Z}/N{\bf Z}}$ with generators ${S = \{-1,+1\}}$ .

Remark 1 We call the above Cayley graphs right-invariant because every right translation ${x\mapsto xg}$ on ${G}$ is a graph automorphism of ${Cay(G,S)}$ . 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 ${G}$ , as it “looks the same” from every vertex. One could of course also consider left-invariant Cayley graphs, in which ${x}$ is connected to ${xs}$ rather than ${sx}$ . However, the two such graphs are isomorphic using the inverse map ${x \mapsto x^{-1}}$ , so we may without loss of generality restrict our attention throughout to left Cayley graphs.

Remark 2 For minor technical reasons, it will be convenient later on to allow ${S}$ 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 ${G}$ 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 ${G}$ 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 ${G}$ be a finite group that acts (on the left) on a space ${X}$ , thus there is a map ${(g,x) \mapsto gx}$ from ${G \times X}$ to ${X}$ such that ${1x = x}$ and ${(gh)x = g(hx)}$ for all ${g,h \in G}$ and ${x \in X}$ . Let ${S}$ be a symmetric subset of ${G}$ which acts freely on ${X}$ in the sense that ${sx \neq x}$ for all ${s \in S}$ and ${x \in X}$ , and ${sx \neq s'x}$ for all distinct ${s,s' \in S}$ and ${x \in X}$ . Then the Schreier graph ${Sch(X,S)}$ is defined to be the graph with vertex set ${X}$ and edge set ${\{ \{sx,x\}: x \in X, s \in S \}}$ .

Example 2 Every Cayley graph ${Cay(G,S)}$ is also a Schreier graph ${Sch(G,S)}$ , using the obvious left-action of ${G}$ on itself. The ${k}$ -regular graphs formed from ${l}$ permutations ${\pi_1,\ldots,\pi_l \in S_n}$ that were studied in the previous set of notes is also a Schreier graph provided that ${\pi_i(v) \neq v, \pi_i^{-1}(v), \pi_j(v)}$ for all distinct ${1 \leq i,j \leq l}$ , with the underlying group being the permutation group ${S_n}$ (which acts on the vertex set ${X = \{1,\ldots,n\}}$ in the obvious manner), and ${S := \{\pi_1,\ldots,\pi_l,\pi_1^{-1},\ldots,\pi_l^{-1}\}}$ .

Exercise 1 If ${k}$ is an even integer, show that every ${k}$ -regular graph is a Schreier graph involving a set ${S}$ of generators of cardinality ${k/2}$ . (Hint: first show that every ${k}$ -regular graph can be decomposed into ${k/2}$ 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 ${Cay(G,S)}$ be a finite Cayley graph.

(i) Show that ${Cay(G,S)}$ is a one-sided ${\epsilon}$ -expander for ${G}$ for some ${\epsilon>0}$ if and only if ${S}$ generates ${G}$ .

(ii) Show that ${Cay(G,S)}$ is a two-sided ${\epsilon}$ -expander for ${G}$ for some ${\epsilon>0}$ if and only if ${S}$ generates ${G}$ , and furthermore ${S}$ intersects each index ${2}$ subgroup of ${G}$ .

We will however be interested in more quantitative expansion properties, in which the expansion constant ${\epsilon}$ is independent of the size of the Cayley graph, so that one can construct non-trivial expander families ${Cay(G_n,S_n)}$ 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

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

of subsets of ${G}$ .

Exercise 3 (Combinatorial description of expansion) Let ${Cay(G_n,S_n)}$ be a family of finite ${k}$ -regular Cayley graphs. Show that ${Cay(G_n,S_n)}$ is a one-sided expander family if and only if there is a constant ${c>0}$ independent of ${n}$ such that ${|E_n \cup E_n S_n| \geq (1+c) |E_n|}$ for all sufficiently large ${n}$ and all subsets ${E_n}$ of ${G_n}$ with ${|E_n| \leq |G_n|/2}$ .

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 ${Cay(G_n,S_n)}$ be a family of finite ${k}$ -regular Cayley graphs, with the ${G_n}$ all abelian, and the ${S_n}$ generating ${G_n}$ . Show that ${Cay(G_n,S_n)}$ are a one-sided expander family if and only if the Cayley graphs have bounded cardinality (i.e. ${\sup_n |G_n| < \infty}$ ). (Hint: assume for contradiction that ${Cay(G_n,S_n)}$ is a one-sided expander family with ${|G_n| \rightarrow \infty}$ , and show by two different arguments that ${\sup_n |S_n^m|}$ grows at least exponentially in ${m}$ and also at most polynomially in ${m}$ , 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 ${f, g \in \ell^2(G)}$ , defined by the formula

$\displaystyle f * g(x) := \sum_{y \in G} f(y) g(y^{-1} x) = \sum_{y \in G} f(x y^{-1}) g(y).$

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 ${G}$ is abelian. (If one is more algebraically minded, one can also identify ${\ell^2(G)}$ (when ${G}$ is finite, at least) with the group algebra ${{\bf C} G}$ , in which case convolution is simply the multiplication operation in this algebra.) The adjacency operator ${A}$ on a Cayley graph ${Cay(G,S)}$ can then be viewed as a convolution

$\displaystyle Af = |S| \mu * f,$

where ${\mu}$ is the probability density

$\displaystyle \mu := \frac{1}{|S|} \sum_{s \in S} \delta_s \ \ \ \ \ (1)$

where ${\delta_s}$ is the Kronecker delta function on ${s}$ . Using the spectral definition of expansion, we thus see that ${Cay(G,S)}$ is a one-sided expander if and only if

$\displaystyle \langle f, \mu*f \rangle \leq (1-\epsilon) \|f\|_{\ell^2(G)} \ \ \ \ \ (2)$

whenever ${f \in \ell^2(G)}$ is orthogonal to the constant function ${1}$ , and is a two-sided expander if

$\displaystyle \| \mu*f \|_{\ell^2(G)} \leq (1-\epsilon) \|f\|_{\ell^2(G)} \ \ \ \ \ (3)$

whenever ${f \in \ell^2(G)}$ is orthogonal to the constant function ${1}$ .

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

$\displaystyle \mu := \frac{1}{2l} \sum_{i=1}^l \delta_{s_i} + \delta_{s_i^{-1}}$

obeys either (2) or (3).

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 ${Cay(G_n,S_n)}$ be a family of finite ${k}$ -regular Cayley graphs, and let ${\mu_n}$ be the associated probability density functions. Let ${A > 1/2}$ be a constant.

Show that the ${Cay(G_n,S_n)}$ are a two-sided expander family if and only if there exists a ${C>0}$ such that for all sufficiently large ${n}$ , one has ${\| \mu_n^{*m} - \frac{1}{|G_n|} \|_{\ell^2(G_n)} \leq \frac{1}{|G_n|^A}}$ for some ${m \leq C \log |G_n|}$ , where ${\mu_n^{*m} := \mu_n * \ldots * \mu_n}$ denotes the convolution of ${m}$ copies of ${\mu_n}$ .

Show that the ${Cay(G_n,S_n)}$ are a one-sided expander family if and only if there exists a ${C>0}$ such that for all sufficiently large ${n}$ , one has ${\| (\frac{1}{2} \delta_1 + \frac{1}{2} \mu_n)^{*m} - \frac{1}{|G_n|} \|_{\ell^2(G_n)} \leq \frac{1}{|G_n|^A}}$ for some ${m \leq C \log |G_n|}$ .

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 ${\tau}$ ). 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).

Read the rest of this entry »

Some notes on the Coven-Meyerowitz conjecture

19 November, 2011 in expository, math.CO, math.GR, question | Tags: Coven-Meyerowitz conjecture, Fuglede conjecture, tiling | by Terence Tao | 9 comments

Let ${G = (G,+)}$ be a finite additive group. A tiling pair is a pair of non-empty subsets ${A, B}$ such that every element of ${G}$ can be written in exactly one way as a sum of an element ${a}$ of ${A}$ and an element ${b}$ of ${B}$ , in which case we write ${G = A \oplus B}$ . The sets ${A, B}$ are then called tiles, with ${B}$ being a complementary tile to ${A}$ and vice versa. For instance, every subgroup ${H}$ of ${G}$ is a tile, as one can pick one representative from each coset of ${H}$ to form the complementary tile. Conversely, any set formed by taking one representative from each coset of ${H}$ is also a tile.

Tiles can be quite complicated, particularly when the group ${G}$ is “high-dimensional”. We will therefore restrict to the simple case of a cyclic group ${G = {\bf Z}/N{\bf Z}}$ , and restrict even further to the special case when the modulus ${N}$ 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 ${N}$ be square-free, and let ${A}$ be a tile of ${{\bf Z}/N{\bf Z}}$ . Then there exists a subgroup ${H}$ of ${{\bf Z}/N{\bf Z}}$ such that ${A}$ consists of a single representative from each coset of ${H}$ .

Note that in the square-free case, every subgroup ${H}$ of ${{\bf Z}/N{\bf Z}}$ has a complementary subgroup ${H^\perp}$ (thus ${{\bf Z}/N{\bf Z} = H \oplus H^\perp}$ ). In particular, ${H}$ consists of a single representative from each coset of ${H^\perp}$ , and so the examples of subgroups of ${{\bf Z}/N{\bf Z}}$ 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 ${p}$ is a prime, then the multiples of ${p}$ in ${{\bf Z}/p^2{\bf Z}}$ 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 ${N}$ be a natural number, and let ${A}$ be a tile of ${{\bf Z}/N{\bf Z}}$ . Then there exists a set ${S_A}$ of prime powers with ${|A| = \prod_{p^j \in S_A} p}$ such that the Fourier transform
$\displaystyle \hat 1_A(k) := \sum_{n \in A} e^{2\pi i kn / N}$

vanishes whenever ${k}$ is a non-zero element of ${{\bf Z}/N{\bf Z}}$ whose order is the product of elements of ${S_A}$ that are powers of distinct primes. Equivalently, the generating polynomial ${\sum_{n \in A} x^n}$ is divisible by the cyclotomic polynomials ${\phi_m}$ whenever ${m}$ is the product of elements of ${S_A}$ 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 ${E}$ be a compact subset of ${{\bf R}}$ of positive measure which is a tile (thus ${{\bf R} = E \oplus \Lambda}$ for some set ${\Lambda \subset {\bf R}}$ ). Then ${L^2(E)}$ (with Lebesgue measure) has a spectrum, that is to say an orthogonal set of plane waves ${x \mapsto e^{2\pi i \xi x}}$ .

Indeed, it was shown by Laba that Conjecture 2 implies Conjecture 3 in the case when ${E}$ 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 ${N}$ 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.

Read the rest of this entry »

254A, Notes 9: Applications of the structural theory of approximate groups

13 November, 2011 in 254A - Hilbert's fifth problem, math.GR, math.MG | Tags: approximate groups, Bishop-Gromov inequality, Gromov's theorem, Margulis lemma, nilpotent groups | by Terence Tao | 14 comments

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.

Read the rest of this entry »

254A, Notes 8: The microstructure of approximate groups

6 November, 2011 in 254A - Hilbert's fifth problem, math.CO, math.GR | Tags: approximate groups, Gleason-Yamabe theorem, good models, Lie groups, local groups, nilpotent groups, ultra approximate groups | by Terence Tao | 4 comments

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:

( ${S}$ small) One has
$\displaystyle (S^{A^4})^{1000K^3} \subset A. \ \ \ \ \ (4)$

(First trapping condition) If ${g, g^2, \ldots, g^{1000} \in A^{100}}$ , then ${g \in A}$ .

(Second trapping condition) If ${g, g^2, \ldots, g^{10^6 K^3} \in A}$ , then ${g \in S}$ .

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.

Start with an (ultra) strong approximate group ${A}$ .
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.
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}$ .
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.
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.

Read the rest of this entry »

Associativity of the Baker-Campbell-Hausdorff formula

29 October, 2011 in expository, math.GR, math.RA | Tags: Baker-Campbell-Hausdorff formula, Lie algebras, Lie groups, local Lie groups | by Terence Tao | 5 comments

Let ${{\mathfrak g}}$ be a finite-dimensional Lie algebra (over the reals). Given two sufficiently small elements ${x, y}$ of ${{\mathfrak g}}$ , define the right Baker-Campbell-Hausdorff-Dynkin law

$\displaystyle R_y(x) := x + \int_0^1 F_R( \hbox{Ad}_x \hbox{Ad}_{ty} ) y \ dt \ \ \ \ \ (1)$

where ${\hbox{Ad}_x := \exp(\hbox{ad}_x)}$ , ${\hbox{ad}_x: {\mathfrak g} \rightarrow {\mathfrak g}}$ is the adjoint map ${\hbox{ad}_x(y) := [x,y]}$ , and ${F_R}$ is the function ${F_R(z) := \frac{z \log z}{z-1}}$ , which is analytic for ${z}$ near ${1}$ . Similarly, define the left Baker-Campbell-Hausdorff-Dynkin law

$\displaystyle L_x(y) := y + \int_0^1 F_L( \hbox{Ad}_{tx} \hbox{Ad}_y ) x\ dt \ \ \ \ \ (2)$

where ${F_L(z) := \frac{\log z}{z-1}}$ . One easily verifies that these expressions are well-defined (and depend smoothly on ${x}$ and ${y}$ ) when ${x}$ and ${y}$ are sufficiently small.

We have the famous Baker-Campbell-Hausdoff-Dynkin formula:

Theorem 1 (BCH formula) Let ${G}$ be a finite-dimensional Lie group over the reals with Lie algebra ${{\mathfrak g}}$ . Let ${\log}$ be a local inverse of the exponential map ${\exp: {\mathfrak g} \rightarrow G}$ , defined in a neighbourhood of the identity. Then for sufficiently small ${x, y \in {\mathfrak g}}$ , one has
$\displaystyle \log( \exp(x) \exp(y) ) = R_y(x) = L_x(y).$

See for instance these notes of mine for a proof of this formula (it is for ${R_y}$ , but one easily obtains a similar proof for ${L_x}$ ).

In particular, one can give a neighbourhood of the identity in ${{\mathfrak g}}$ the structure of a local Lie group by defining the group operation ${\ast}$ as

$\displaystyle x \ast y := R_y(x) = L_x(y) \ \ \ \ \ (3)$

for sufficiently small ${x, y}$ , and the inverse operation by ${x^{-1} := -x}$ (one easily verifies that ${R_x(-x) = L_x(-x) = 0}$ for all small ${x}$ ).

It is tempting to reverse the BCH formula and conclude (the local form of) Lie’s third theorem, that every finite-dimensional Lie algebra is isomorphic to the Lie algebra of some local Lie group, by using (3) to define a smooth local group structure on a neighbourhood of the identity. (See this previous post for a definition of a local Lie group.) The main difficulty in doing so is in verifying that the definition (3) is well-defined (i.e. that ${R_y(x)}$ is always equal to ${L_x(y)}$ ) and locally associative. The well-definedness issue can be trivially disposed of by using just one of the expressions ${R_y(x)}$ or ${L_x(y)}$ as the definition of ${\ast}$ (though, as we shall see, it will be very convenient to use both of them simultaneously). However, the associativity is not obvious at all.

With the assistance of Ado’s theorem, which places ${{\mathfrak g}}$ inside the general linear Lie algebra ${\mathfrak{gl}_n({\bf R})}$ for some ${n}$ , one can deduce both the well-definedness and associativity of (3) from the Baker-Campbell-Hausdorff formula for ${\mathfrak{gl}_n({\bf R})}$ . However, Ado’s theorem is rather difficult to prove (see for instance this previous blog post for a proof), and it is natural to ask whether there is a way to establish these facts without Ado’s theorem.

After playing around with this for some time, I managed to extract a direct proof of well-definedness and local associativity of (3), giving a proof of Lie’s third theorem independent of Ado’s theorem. This is not a new result by any means, (indeed, the original proofs of Lie and Cartan of Lie’s third theorem did not use Ado’s theorem), but I found it an instructive exercise to work out the details, and so I am putting it up on this blog in case anyone else is interested (and also because I want to be able to find the argument again if I ever need it in the future).

Read the rest of this entry »

254A, Notes 7: Models of ultra approximate groups

27 October, 2011 in 254A - Hilbert's fifth problem, math.GR, math.LO, math.MG | Tags: approximate groups, Lie groups, ultra approximate groups | by Terence Tao | 14 comments

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

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

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

Lemma 1 (Sanders lemma) Let ${A}$ be a finite ${K}$ -approximate group in a (global) group ${G}$ , and let ${m \geq 1}$ . Then there exists a symmetric subset ${S}$ of ${A^4}$ with ${|S| \gg_{K,m} |A|}$ containing the identity such that ${S^m \subset A^4}$ .

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

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

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

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

Read the rest of this entry »

The structure of approximate groups

24 October, 2011 in math.CO, math.GR, math.MG, paper | Tags: approximate groups, Ben Green, Emmanuel Breuillard, Gromov's theorem, nilpotent groups, noncommutative Freiman theorem, nonstandard analysis | by Terence Tao | 22 comments

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:

(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.)
(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.)
(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}$ .
(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).

	Andrew Sutherland on A truncated elementary Selberg…
	v08ltu on A truncated elementary Selberg…
	Andrew Sutherland on A truncated elementary Selberg…
	Terence Tao on Further analysis of the trunca…
	A truncated elementa… on The elementary Selberg sieve a…
	A truncated elementa… on Estimation of the Type I and T…
	A truncated elementa… on A combinatorial subset sum pro…
	A truncated elementa… on Estimation of the Type III…
	A truncated elementa… on The prime tuples conjecture, s…
	A truncated elementa… on Further analysis of the trunca…
	Anonymous on Estimation of the Type III…
	Anonymous on A combinatorial subset sum pro…
	Gergely Harcos on Further analysis of the trunca…
	Gergely Harcos on Further analysis of the trunca…
	Gergely Harcos on Further analysis of the trunca…

Category Archive

254B, Notes 5: Product theorems, pivot arguments, and the Larsen-Pink non-concentration inequality

A nilpotent Freiman dimension lemma

254B, Notes 3: Quasirandom groups, expansion, and Selberg’s 3/16 theorem

254B, Notes 2: Cayley graphs and Kazhdan’s property (T)

Some notes on the Coven-Meyerowitz conjecture

254A, Notes 9: Applications of the structural theory of approximate groups

254A, Notes 8: The microstructure of approximate groups

Associativity of the Baker-Campbell-Hausdorff formula

254A, Notes 7: Models of ultra approximate groups

The structure of approximate groups

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

Google+ feed

Tags

The Polymath Blog

Mathematics in Australia

For commenters

Follow “What's new”