Tag Archive

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

Nested approximate subgroups

3 June, 2015 in expository, math.CO, math.GR | Tags: additive combinatorics, approximate groups, Ruzsa calculus | by Terence Tao | 5 comments

Suppose that ${A \subset B}$ are two subgroups of some ambient group ${G}$ , with the index ${K := [B:A]}$ of ${A}$ in ${B}$ being finite. Then ${B}$ is the union of ${K}$ left cosets of ${A}$ , thus ${B = SA}$ for some set ${S \subset B}$ of cardinality ${K}$ . The elements ${s}$ of ${S}$ are not entirely arbitrary with regards to ${A}$ . For instance, if ${A}$ is a normal subgroup of ${B}$ , then for each ${s \in S}$ , the conjugation map ${g \mapsto s^{-1} g s}$ preserves ${A}$ . In particular, if we write ${A^s := s^{-1} A s}$ for the conjugate of ${A}$ by ${s}$ , then

$\displaystyle A = A^s.$

Even if ${A}$ is not normal in ${B}$ , it turns out that the conjugation map ${g \mapsto s^{-1} g s}$ approximately preserves ${A}$ , if ${K}$ is bounded. To quantify this, let us call two subgroups ${A,B}$ ${K}$ -commensurate for some ${K \geq 1}$ if one has

$\displaystyle [A : A \cap B], [B : A \cap B] \leq K.$

Proposition 1 Let ${A \subset B}$ be groups, with finite index ${K = [B:A]}$ . Then for every ${s \in B}$ , the groups ${A}$ and ${A^s}$ are ${K}$ -commensurate, in fact

$\displaystyle [A : A \cap A^s ] = [A^s : A \cap A^s ] \leq K.$

Proof: One can partition ${B}$ into ${K}$ left translates ${xA}$ of ${A}$ , as well as ${K}$ left translates ${yA^s}$ of ${A^s}$ . Combining the partitions, we see that ${B}$ can be partitioned into at most ${K^2}$ non-empty sets of the form ${xA \cap yA^s}$ . Each of these sets is easily seen to be a left translate of the subgroup ${A \cap A^s}$ , thus ${[B: A \cap A^s] \leq K^2}$ . Since

$\displaystyle [B: A \cap A^s] = [B:A] [A: A \cap A^s] = [B:A^s] [A^s: A \cap A^s]$

and ${[B:A] = [B:A^s]=K}$ , we obtain the claim. $\Box$

One can replace the inclusion ${A \subset B}$ by commensurability, at the cost of some worsening of the constants:

Corollary 2 Let ${A, B}$ be ${K}$ -commensurate subgroups of ${G}$ . Then for every ${s \in B}$ , the groups ${A}$ and ${A^s}$ are ${K^2}$ -commensurate.

Proof: Applying the previous proposition with ${A}$ replaced by ${A \cap B}$ , we see that for every ${s \in B}$ , ${A \cap B}$ and ${(A \cap B)^s}$ are ${K}$ -commensurate. Since ${A \cap B}$ and ${(A \cap B)^s}$ have index at most ${K}$ in ${A}$ and ${A^s}$ respectively, the claim follows. $\Box$

It turns out that a similar phenomenon holds for the more general concept of an approximate group, and gives a “classification” of all the approximate groups ${B}$ containing a given approximate group ${A}$ as a “bounded index approximate subgroup”. Recall that a ${K}$ -approximate group ${A}$ in a group ${G}$ for some ${K \geq 1}$ is a symmetric subset of ${G}$ containing the identity, such that the product set ${A^2 := \{ a_1 a_2: a_1,a_2 \in A\}}$ can be covered by at most ${K}$ left translates of ${A}$ (and thus also ${K}$ right translates, by the symmetry of ${A}$ ). For simplicity we will restrict attention to finite approximate groups ${A}$ so that we can use their cardinality ${A}$ as a measure of size. We call finite two approximate groups ${A,B}$ ${K}$ -commensurate if one has

$\displaystyle |A^2 \cap B^2| \geq \frac{1}{K} |A|, \frac{1}{K} |B|;$

note that this is consistent with the previous notion of commensurability for genuine groups.

Theorem 3 Let ${G}$ be a group, and let ${K_1,K_2,K_3 \geq 1}$ be real numbers. Let ${A}$ be a finite ${K_1}$ -approximate group, and let ${B}$ be a symmetric subset of ${G}$ that contains ${A}$ .

(i) If ${B}$ is a ${K_2}$ -approximate group with ${|B| \leq K_3 |A|}$ , then one has ${B \subset SA}$ for some set ${S}$ of cardinality at most ${K_1 K_2 K_3}$ . Furthermore, for each ${s \in S}$ , the approximate groups ${A}$ and ${A^s}$ are ${K_1 K_2^5 K_3}$ -commensurate.

(ii) Conversely, if ${B \subset SA}$ for some set ${S}$ of cardinality at most ${K_3}$ , and ${A}$ and ${A^s}$ are ${K_2}$ -commensurate for all ${s \in S}$ , then ${|B| \leq K_3 |A|}$ , and ${B}$ is a ${K_1^6 K_2 K_3^2}$ -approximate group.

Informally, the assertion that ${B}$ is an approximate group containing ${A}$ as a “bounded index approximate subgroup” is equivalent to ${B}$ being covered by a bounded number of shifts ${sA}$ of ${A}$ , where ${s}$ approximately normalises ${A^2}$ in the sense that ${A^2}$ and ${(A^2)^s}$ have large intersection. Thus, to classify all such ${B}$ , the problem essentially reduces to that of classifying those ${s}$ that approximately normalise ${A^2}$ .

To prove the theorem, we recall some standard lemmas from arithmetic combinatorics, which are the foundation stones of the “Ruzsa calculus” that we will use to establish our results:

Lemma 4 (Ruzsa covering lemma) If ${A}$ and ${B}$ are finite non-empty subsets of ${G}$ , then one has ${B \subset SAA^{-1}}$ for some set ${S \subset B}$ with cardinality ${|S| \leq \frac{|BA|}{|A|}}$ .

Proof: We take ${S}$ to be a subset of ${B}$ with the property that the translates ${sA, s \in S}$ are disjoint in ${BA}$ , and such that ${S}$ is maximal with respect to set inclusion. The required properties of ${S}$ are then easily verified. $\Box$

Lemma 5 (Ruzsa triangle inequality) If ${A,B,C}$ are finite non-empty subsets of ${G}$ , then

$\displaystyle |A C^{-1}| \leq |A B^{-1}| |B C^{-1}| / |B|.$

Proof: If ${ac^{-1}}$ is an element of ${AC^{-1}}$ with ${a \in A}$ and ${c \in C}$ , then from the identity ${ac^{-1} = (ab^{-1}) (bc^{-1})}$ we see that ${ac^{-1}}$ can be written as the product of an element of ${AB^{-1}}$ and an element of ${BC^{-1}}$ in at least ${|B|}$ distinct ways. The claim follows. $\Box$

Now we can prove (i). By the Ruzsa covering lemma, ${B}$ can be covered by at most

$\displaystyle \frac{|BA|}{|A|} \leq \frac{|B^2|}{|A|} \leq \frac{K_2 |B|}{|A|} \leq K_2 K_3$

left-translates of ${A^2}$ , and hence by at most ${K_1 K_2 K_3}$ left-translates of ${A}$ , thus ${B \subset SA}$ for some ${|S| \leq K_1 K_2 K_3}$ . Since ${sA}$ only intersects ${B}$ if ${s \in BA}$ , we may assume that

$\displaystyle S \subset BA \subset B^2$

and hence for any ${s \in S}$

$\displaystyle |A^s A| \leq |B^2 A B^2 A| \leq |B^6|$

$\displaystyle \leq K_2^5 |B| \leq K_2^5 K_3 |A|.$

By the Ruzsa covering lemma again, this implies that ${A^s}$ can be covered by at most ${K_2^5 K_3}$ left-translates of ${A^2}$ , and hence by at most ${K_1 K_2^5 K_3}$ left-translates of ${A}$ . By the pigeonhole principle, there thus exists a group element ${g}$ with

$\displaystyle |A^s \cap gA| \geq \frac{1}{K_1 K_2^5 K_3} |A|.$

Since

$\displaystyle |A^s \cap gA| \leq | (A^s \cap gA)^{-1} (A^s \cap gA)|$

and

$\displaystyle (A^s \cap gA)^{-1} (A^s \cap gA) \subset A^2 \cap (A^s)^2$

the claim follows.

Now we prove (ii). Clearly

$\displaystyle |B| \leq |S| |A| \leq K_3 |A|.$

Now we control the size of ${B^2 A}$ . We have

$\displaystyle |B^2 A| \leq |SA SA^2| \leq K_3^2 \sup_{s \in S} |A s A^2| = K_3^2 \sup_{s \in S} |A^s A^2|.$

From the Ruzsa triangle inequality and symmetry we have

$\displaystyle |A^s A^2| \leq \frac{ |A^s (A^2 \cap (A^2)^s)| |(A^2 \cap (A^2)^s) A^2|}{|A^2 \cap (A^2)^s|}$

$\displaystyle \leq \frac{ |(A^3)^s| |A^4| }{|A|/K_2}$

$\displaystyle \leq K_2 \frac{ |A^3| |A^4| }{|A|}$

$\displaystyle \leq K_1^5 K_2 |A|$

and thus

$\displaystyle |B^2 A| \leq K_1^5 K_2 K_3^2 |A|.$

By the Ruzsa covering lemma, this implies that ${B^2}$ is covered by at most ${K_1^5 K_2 K_3^2}$ left-translates of ${A^2}$ , hence by at most ${K_1^6 K_2 K_3^2}$ left-translates of ${A}$ . Since ${A \subset B}$ , the claim follows.

We now establish some auxiliary propositions about commensurability of approximate groups. The first claim is that commensurability is approximately transitive:

Proposition 6 Let ${A}$ be a ${K_1}$ -approximate group, ${B}$ be a ${K_2}$ -approximate group, and ${C}$ be a ${K_3}$ -approximate group. If ${A}$ and ${B}$ are ${K_4}$ -commensurate, and ${B}$ and ${C}$ are ${K_5}$ -commensurate, then ${A}$ and ${C}$ are ${K_1^2 K_2^3 K_2^3 K_4 K_5 \max(K_1,K_3)}$ -commensurate.

Proof: From two applications of the Ruzsa triangle inequality we have

$\displaystyle |AC| \leq \frac{|A (A^2 \cap B^2)| |(A^2 \cap B^2) (B^2 \cap C^2)| |(B^2 \cap C^2) C|}{|A^2 \cap B^2| |B^2 \cap C^2|}$

$\displaystyle \leq \frac{|A^3| |B^4| |C^3|}{ (|A|/K_4) (|B|/K_5)}$

$\displaystyle \leq K_4 K_5 \frac{K_1^2 |A| K_2^3 |B| K_3^2 |C|}{ |A| |B| }$

$\displaystyle = K_1^2 K_2^3 K_3^2 K_4 K_5 |C|.$

By the Ruzsa covering lemma, we may thus cover ${A}$ by at most ${K_1^2 K_2^3 K_3^2 K_4 K_5}$ left-translates of ${C^2}$ , and hence by ${K_1^2 K_2^3 K_3^3 K_4 K_5}$ left-translates of ${C}$ . By the pigeonhole principle, there thus exists a group element ${g}$ such that

$\displaystyle |A \cap gC| \geq \frac{1}{K_1^2 K_2^3 K_3^3 K_4 K_5} |A|,$

and so by arguing as in the proof of part (i) of the theorem we have

$\displaystyle |A^2 \cap C^2| \geq \frac{1}{K_1^2 K_2^3 K_3^3 K_4 K_5} |A|$

and similarly

$\displaystyle |A^2 \cap C^2| \geq \frac{1}{K_1^3 K_2^3 K_3^2 K_4 K_5} |C|$

and the claim follows. $\Box$

The next proposition asserts that the union and (modified) intersection of two commensurate approximate groups is again an approximate group:

Proposition 7 Let ${A}$ be a ${K_1}$ -approximate group, ${B}$ be a ${K_2}$ -approximate group, and suppose that ${A}$ and ${B}$ are ${K_3}$ -commensurate. Then ${A \cup B}$ is a ${K_1 + K_2 + K_1^2 K_2^4 K_3 + K_1^4 K_2^2 K_3}$ -approximate subgroup, and ${A^2 \cap B^2}$ is a ${K_1^6 K_2^3 K_3}$ -approximate subgroup.

Using this proposition, one may obtain a variant of the previous theorem where the containment ${A \subset B}$ is replaced by commensurability; we leave the details to the interested reader.

Proof: We begin with ${A \cup B}$ . Clearly ${A \cup B}$ is symmetric and contains the identity. We have ${(A \cup B)^2 = A^2 \cup AB \cup BA \cup B^2}$ . The set ${A^2}$ is already covered by ${K_1}$ left translates of ${A}$ , and hence of ${A \cup B}$ ; similarly ${B^2}$ is covered by ${K_2}$ left translates of ${A \cup B}$ . As for ${AB}$ , we observe from the Ruzsa triangle inequality that

$\displaystyle |AB^2| \leq \frac{|A (A^2 \cap B^2)| |(A^2 \cap B^2) B^2|}{|A^2 \cap B^2|}$

$\displaystyle \leq \frac{|A^3| |B^4|}{|A|/K_3}$

$\displaystyle \leq K_1^2 K_2^3 K_3 |B|$

and hence by the Ruzsa covering lemma, ${AB}$ is covered by at most ${K_1^2 K_2^3 K_3}$ left translates of ${B^2}$ , and hence by ${K_1^2 K_2^4 K_3}$ left translates of ${B}$ , and hence of ${A \cup B}$ . Similarly ${BA}$ is covered by at most ${K_1^4 K_2^2 K_3}$ left translates of ${B}$ . The claim follows.

Now we consider ${A^2 \cap B^2}$ . Again, this is clearly symmetric and contains the identity. Repeating the previous arguments, we see that ${A}$ is covered by at most ${K_1^2 K_2^3 K_3}$ left-translates of ${B}$ , and hence there exists a group element ${g}$ with

$\displaystyle |A \cap gB| \geq \frac{1}{K_1^2 K_2^3 K_3} |A|.$

Now observe that

$\displaystyle |(A^2 \cap B^2)^2 (A \cap gB)| \leq |A^5| \leq K_1^4 |A|$

and so by the Ruzsa covering lemma, ${(A^2 \cap B^2)^2}$ can be covered by at most ${K_1^6 K_2^3 K_3}$ left-translates of ${(A \cap gB) (A \cap gB)^{-1}}$ . But this latter set is (as observed previously) contained in ${A^2 \cap B^2}$ , and the claim follows. $\Box$

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 | 8 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 »

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 | 24 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).

254A, Notes 6: Ultraproducts as a bridge between hard analysis and soft analysis

15 October, 2011 in 254A - Hilbert's fifth problem, math.GR, math.LO | Tags: approximate groups, countable saturation, Los's theorem, ultrafilters, ultraproducts | by Terence Tao | 20 comments

Roughly speaking, mathematical analysis can be divided into two major styles, namely hard analysis and soft analysis. The precise distinction between the two types of analysis is imprecise (and in some cases one may use a blend the two styles), but some key differences can be listed as follows.

Hard analysis tends to be concerned with quantitative or effective properties such as estimates, upper and lower bounds, convergence rates, and growth rates or decay rates. In contrast, soft analysis tends to be concerned with qualitative or ineffective properties such as existence and uniqueness, finiteness, measurability, continuity, differentiability, connectedness, or compactness.
Hard analysis tends to be focused on finitary, finite-dimensional or discrete objects, such as finite sets, finitely generated groups, finite Boolean combination of boxes or balls, or “finite-complexity” functions, such as polynomials or functions on a finite set. In contrast, soft analysis tends to be focused on infinitary, infinite-dimensional, or continuous objects, such as arbitrary measurable sets or measurable functions, or abstract locally compact groups.
Hard analysis tends to involve explicit use of many parameters such as ${\epsilon}$ , ${\delta}$ , ${N}$ , etc. In contrast, soft analysis tends to rely instead on properties such as continuity, differentiability, compactness, etc., which implicitly are defined using a similar set of parameters, but whose parameters often do not make an explicit appearance in arguments.
In hard analysis, it is often the case that a key lemma in the literature is not quite optimised for the application at hand, and one has to reprove a slight variant of that lemma (using a variant of the proof of the original lemma) in order for it to be suitable for applications. In contrast, in soft analysis, key results can often be used as “black boxes”, without need of further modification or inspection of the proof.
The properties in soft analysis tend to enjoy precise closure properties; for instance, the composition or linear combination of continuous functions is again continuous, and similarly for measurability, differentiability, etc. In contrast, the closure properties in hard analysis tend to be fuzzier, in that the parameters in the conclusion are often different from the parameters in the hypotheses. For instance, the composition of two Lipschitz functions with Lipschitz constant ${K}$ is still Lipschitz, but now with Lipschitz constant ${K^2}$ instead of ${K}$ . These changes in parameters mean that hard analysis arguments often require more “bookkeeping” than their soft analysis counterparts, and are less able to utilise algebraic constructions (e.g. quotient space constructions) that rely heavily on precise closure properties.

In the lectures so far, focusing on the theory surrounding Hilbert’s fifth problem, the results and techniques have fallen well inside the category of soft analysis. However, we will now turn to the theory of approximate groups, which is a topic which is traditionally studied using the methods of hard analysis. (Later we will also study groups of polynomial growth, which lies on an intermediate position in the spectrum between hard and soft analysis, and which can be profitably analysed using both styles of analysis.)

Despite the superficial differences between hard and soft analysis, though, there are a number of important correspondences between results in hard analysis and results in soft analysis. For instance, if one has some sort of uniform quantitative bound on some expression relating to finitary objects, one can often use limiting arguments to then conclude a qualitative bound on analogous expressions on infinitary objects, by viewing the latter objects as some sort of “limit” of the former objects. Conversely, if one has a qualitative bound on infinitary objects, one can often use compactness and contradiction arguments to recover uniform quantitative bounds on finitary objects as a corollary.

Remark 1 Another type of correspondence between hard analysis and soft analysis, which is “syntactical” rather than “semantical” in nature, arises by taking the proofs of a soft analysis result, and translating such a qualitative proof somehow (e.g. by carefully manipulating quantifiers) into a quantitative proof of an analogous hard analysis result. This type of technique is sometimes referred to as proof mining in the proof theory literature, and is discussed in this previous blog post (and its comments). We will however not employ systematic proof mining techniques here, although in later posts we will informally borrow arguments from infinitary settings (such as the methods used to construct Gleason metrics) and adapt them to finitary ones.

Let us illustrate the correspondence between hard and soft analysis results with a simple example.

Proposition 1 Let ${X}$ be a sequentially compact topological space, let ${S}$ be a dense subset of ${X}$ , and let ${f: X \rightarrow [0,+\infty]}$ be a continuous function (giving the extended half-line ${[0,+\infty]}$ the usual order topology). Then the following statements are equivalent:

(i) (Qualitative bound on infinitary objects) For all ${x \in X}$ , one has ${f(x) < +\infty}$ .

(ii) (Quantitative bound on finitary objects) There exists ${M < +\infty}$ such that ${f(x) \leq M}$ for all ${x \in S}$ .

In applications, ${S}$ is typically a (non-compact) set of “finitary” (or “finite complexity”) objects of a certain class, and ${X}$ is some sort of “completion” or “compactification” of ${S}$ which admits additional “infinitary” objects that may be viewed as limits of finitary objects.

Proof: To see that (ii) implies (i), observe from density that every point ${x}$ in ${X}$ is adherent to ${S}$ , and so given any neighbourhood ${U}$ of ${x}$ , there exists ${y \in S \cap U}$ . Since ${f(y) \leq M}$ , we conclude from the continuity of ${f}$ that ${f(x) \leq M}$ also, and the claim follows.

Conversely, to show that (i) implies (ii), we use the “compactness and contradiction” argument. Suppose for sake of contradiction that (ii) failed. Then for any natural number ${n}$ , there exists ${x_n \in S}$ such that ${f(x_n) \geq n}$ . (Here we have used the axiom of choice, which we will assume throughout this course.) Using sequential compactness, and passing to a subsequence if necessary, we may assume that the ${x_n}$ converge to a limit ${x \in X}$ . By continuity of ${f}$ , this implies that ${f(x) = +\infty}$ , contradicting (i). $\Box$

Remark 2 Note that the above deduction of (ii) from (i) is ineffective in that it gives no explicit bound on the uniform bound ${M}$ in (ii). Without any further information on how the qualitative bound (i) is proven, this is the best one can do in general (and this is one of the most significant weaknesses of infinitary methods when used to solve finitary problems); but if one has access to the proof of (i), one can often finitise or proof mine that argument to extract an effective bound for ${M}$ , although often the bound one obtains in the process is quite poor (particularly if the proof of (i) relied extensively on infinitary tools, such as limits). See this blog post for some related discussion.

The above simple example illustrates that in order to get from an “infinitary” statement such as (i) to a “finitary” statement such as (ii), a key step is to be able to take a sequence ${(x_n)_{n \in {\bf N}}}$ (or in some cases, a more general net ${(x_\alpha)_{\alpha \in A}}$ ) of finitary objects and extract a suitable infinitary limit object ${x}$ . In the literature, there are three main ways in which one can extract such a limit:

(Topological limit) If the ${x_n}$ are all elements of some topological space ${S}$ (e.g. an incomplete function space) which has a suitable “compactification” or “completion” ${X}$ (e.g. a Banach space), then (after passing to a subsequence if necessary) one can often ensure the ${x_n}$ converge in a topological sense (or in a metrical sense) to a limit ${x}$ . The use of this type of limit to pass between quantitative/finitary and qualitative/infinitary results is particularly common in the more analytical areas of mathematics (such as ergodic theory, asymptotic combinatorics, or PDE), due to the abundance of useful compactness results in analysis such as the (sequential) Banach-Alaoglu theorem, Prokhorov’s theorem, the Helly selection theorem, the Arzelá-Ascoli theorem, or even the humble Bolzano-Weierstrass theorem. However, one often has to take care with the nature of convergence, as many compactness theorems only guarantee convergence in a weak sense rather than in a strong one.
(Categorical limit) If the ${x_n}$ are all objects in some category (e.g. metric spaces, groups, fields, etc.) with a number of morphisms between the ${x_n}$ (e.g. morphisms from ${x_{n+1}}$ to ${x_n}$ , or vice versa), then one can often form a direct limit ${\lim_{\rightarrow} x_n}$ or inverse limit ${\lim_{\leftarrow} x_n}$ of these objects to form a limiting object ${x}$ . The use of these types of limits to connect quantitative and qualitative results is common in subjects such as algebraic geometry that are particularly amenable to categorical ways of thinking. (We have seen inverse limits appear in the discussion of Hilbert’s fifth problem, although in that context they were not really used to connect quantitative and qualitative results together.)
(Logical limit) If the ${x_n}$ are all distinct spaces (or elements or subsets of distinct spaces), with few morphisms connecting them together, then topological and categorical limits are often unavailable or unhelpful. In such cases, however, one can still tie together such objects using an ultraproduct construction (or similar device) to create a limiting object ${\lim_{n \rightarrow \alpha} x_n}$ or limiting space ${\prod_{n \rightarrow \alpha} x_n}$ that is a logical limit of the ${x_n}$ , in the sense that various properties of the ${x_n}$ (particularly those that can be phrased using the language of first-order logic) are preserved in the limit. As such, logical limits are often very well suited for the task of connecting finitary and infinitary mathematics together. Ultralimit type constructions are of course used extensively in logic (particularly in model theory), but are also popular in metric geometry. They can also be used in many of the previously mentioned areas of mathematics, such as algebraic geometry (as discussed in this previous post).

The three types of limits are analogous in many ways, with a number of connections between them. For instance, in the study of groups of polynomial growth, both topological limits (using the metric notion of Gromov-Hausdorff convergence) and logical limits (using the ultralimit construction) are commonly used, and to some extent the two constructions are at least partially interchangeable in this setting. (See also these previous posts for the use of ultralimits as a substitute for topological limits.) In the theory of approximate groups, though, it was observed by Hrushovski that logical limits (and in particular, ultraproducts) are the most useful type of limit to connect finitary approximate groups to their infinitary counterparts. One reason for this is that one is often interested in obtaining results on approximate groups ${A}$ that are uniform in the choice of ambient group ${G}$ . As such, one often seeks to take a limit of approximate groups ${A_n}$ that lie in completely unrelated ambient groups ${G_n}$ , with no obvious morphisms or metrics tying the ${G_n}$ to each other. As such, the topological and categorical limits are not easily usable, whereas the logical limits can still be employed without much difficulty.

Logical limits are closely tied with non-standard analysis. Indeed, by applying an ultraproduct construction to standard number systems such as the natural numbers ${{\bf N}}$ or the reals ${{\bf R}}$ , one can obtain nonstandard number systems such as the nonstandard natural numbers ${{}^* {\bf N}}$ or the nonstandard real numbers (or hyperreals) ${{}^* {\bf R}}$ . These nonstandard number systems behave very similarly to their standard counterparts, but also enjoy the advantage of containing the standard number systems as proper subsystems (e.g. ${{\bf R}}$ is a subring of ${{}^* {\bf R}}$ ), which allows for some convenient algebraic manipulations (such as the quotient space construction to create spaces such as ${{}^* {\bf R} / {\bf R}}$ ) which are not easily accessible in the purely standard universe. Nonstandard spaces also enjoy a useful completeness property, known as countable saturation, which is analogous to metric completeness (as discussed in this previous blog post) and which will be particularly useful for us in tying together the theory of approximate groups with the theory of Hilbert’s fifth problem. See this previous post for more discussion on ultrafilters and nonstandard analysis.

In these notes, we lay out the basic theory of ultraproducts and ultralimits (in particular, proving Los’s theorem, which roughly speaking asserts that ultralimits are limits in a logical sense, as well as the countable saturation property alluded to earlier). We also lay out some of the basic foundations of nonstandard analysis, although we will not rely too heavily on nonstandard tools in this course. Finally, we apply this general theory to approximate groups, to connect finite approximate groups to an infinitary type of approximate group which we will call an ultra approximate group. We will then study these ultra approximate groups (and models of such groups) in more detail in the next set of notes.

Remark 3 Throughout these notes (and in the rest of the course), we will assume the axiom of choice, in order to easily use ultrafilter-based tools. If one really wanted to expend the effort, though, one could eliminate the axiom of choice from the proofs of the final “finitary” results that one is ultimately interested in proving, at the cost of making the proofs significantly lengthier. Indeed, there is a general result of Gödel that any result which can be stated in the language of Peano arithmetic (which, roughly speaking, means that the result is “finitary” in nature), and can be proven in set theory using the axiom of choice (or more precisely, in the ZFC axiom system), can also be proven in set theory without the axiom of choice (i.e. in the ZF system). As this course is not focused on foundations, we shall simply assume the axiom of choice henceforth to avoid further distraction by such issues.

Read the rest of this entry »

254A, Notes 0: Hilbert’s fifth problem and related topics

27 August, 2011 in 254A - Hilbert's fifth problem, admin, math.CO, math.GR, math.LO, math.MG | Tags: approximate groups, Freiman's theorem, Gromov's theorem, Hilbert's fifth problem, nilpotent groups, polynomial growth | by Terence Tao | 30 comments

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}{10n}}$ 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.

Read the rest of this entry »

Approximate subgroups of linear groups

12 May, 2010 in math.AG, math.CO, math.GT, paper | Tags: algebraic groups, approximate groups, Ben Green, Cayley graphs, Emmanuel Breuillard | by Terence Tao | 8 comments

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our paper “Approximate subgroups of linear groups“, submitted to GAFA. This paper contains (the first part) of the results announced previously by us; the second part of these results, concerning expander groups, will appear subsequently. The release of this paper has been coordinated with the release of a parallel paper by Pyber and Szabo (previously announced within an hour(!) of our own announcement).

Our main result describes (with polynomial accuracy) the “sufficiently Zariski dense” approximate subgroups of simple algebraic groups ${{\bf G}(k)}$ , or more precisely absolutely almost simple algebraic groups over ${k}$ , such as ${SL_d(k)}$ . More precisely, define a ${K}$ -approximate subgroup of a genuine group ${G}$ to be a finite symmetric neighbourhood of the identity ${A}$ (thus ${1 \in A}$ and ${A^{-1}=A}$ ) such that the product set ${A \cdot A}$ can be covered by ${K}$ left-translates (and equivalently, ${K}$ right-translates) of ${A}$ .

Let ${k}$ be a field, and let ${\overline{k}}$ be its algebraic closure. For us, an absolutely almost simple algebraic group over ${k}$ is a linear algebraic group ${{\bf G}(k)}$ defined over ${k}$ (i.e. an algebraic subvariety of ${GL_n(k)}$ for some ${n}$ with group operations given by regular maps) which is connected (i.e. irreducible), and such that the completion ${{\bf G}(\overline{k})}$ has no proper normal subgroups of positive dimension (i.e. the only normal subgroups are either finite, or are all of ${{\bf G}(\overline{k})}$ . To avoid degeneracies we also require ${{\bf G}}$ to be non-abelian (i.e. not one-dimensional). These groups can be classified in terms of their associated finite-dimensional simple complex Lie algebra, which of course is determined by its Dynkin diagram, together with a choice of weight lattice (and there are only finitely many such choices once the Lie algebra is fixed). However, the exact classification of these groups is not directly used in our work.

Our first main theorem classifies the approximate subgroups ${A}$ of such a group ${{\bf G}(k)}$ in the model case when ${A}$ generates the entire group ${{\bf G}(k)}$ , and ${k}$ is finite; they are either very small or very large.

Theorem 1 (Approximate groups that generate) Let ${{\bf G}(k)}$ be an absolutely almost simple algebraic group over ${k}$ . If ${k}$ is finite and ${A}$ is a ${K}$ -approximate subgroup of ${{\bf G}(k)}$ that generates ${{\bf G}(k)}$ , then either ${|A| \leq K^{O(1)}}$ or ${|A| \geq K^{-O(1)} |{\bf G}(k)|}$ , where the implied constants depend only on ${{\bf G}}$ .

The hypothesis that ${A}$ generates ${{\bf G}(k)}$ cannot be removed completely, since if ${A}$ was a proper subgroup of ${{\bf G}(k)}$ of size intermediate between that of the trivial group and of ${{\bf G}(k)}$ , then the conclusion would fail (with ${K=O(1)}$ ). However, one can relax the hypothesis of generation to that of being sufficiently Zariski-dense in ${{\bf G}(k)}$ . More precisely, we have

Theorem 2 (Zariski-dense approximate groups) Let ${{\bf G}(k)}$ be an absolutely almost simple algebraic group over ${k}$ . If ${A}$ is a ${K}$ -approximate group) is not contained in any proper algebraic subgroup of ${k}$ of complexity at most ${M}$ (where ${M}$ is sufficiently large depending on ${{\bf G}}$ ), then either ${|A| \leq K^{O(1)}}$ or ${|A| \geq K^{-O(1)} |\langle A \rangle|}$ , where the implied constants depend only on ${{\bf G}}$ and ${\langle A \rangle}$ is the group generated by ${A}$ .

Here, we say that an algebraic variety has complexity at most ${M}$ if it can be cut out of an ambient affine or projective space of dimension at most ${M}$ by using at most ${M}$ polynomials, each of degree at most ${M}$ . (Note that this is not an intrinsic notion of complexity, but will depend on how one embeds the algebraic variety into an ambient space; but we are assuming that our algebraic group ${{\bf G}(k)}$ is a linear group and thus comes with such an embedding.)

In the case when ${k = {\bf C}}$ , the second option of this theorem cannot occur since ${{\bf G}({\bf C})}$ is infinite, leading to a satisfactory classification of the Zariski-dense approximate subgroups of almost simple connected algebraic groups over ${{\bf C}}$ . On the other hand, every approximate subgroup of ${GL_n({\bf C})}$ is Zariski-dense in some algebraic subgroup, which can be then split as an extension of a semisimple algebraic quotient group by a solvable algebraic group (the radical of the Zariski closure). Pursuing this idea (and glossing over some annoying technical issues relating to connectedness), together with the Freiman theory for solvable groups over ${{\bf C}}$ due to Breuillard and Green, we obtain our third theorem:

Theorem 3 (Freiman’s theorem in ${GL_n({\bf C})}$ ) Let ${A}$ be a ${K}$ -approximate subgroup of ${GL_n({\bf C})}$ . Then there exists a nilpotent ${K}$ -approximate subgroup ${B}$ of size at most ${K^{O(1)}|A|}$ , such that ${A}$ is covered by ${K^{O(1)}}$ translates of ${B}$ .

This can be compared with Gromov’s celebrated theorem that any finitely generated group of polynomial growth is virtually nilpotent. Indeed, the above theorem easily implies Gromov’s theorem in the case of finitely generated subgroups of ${GL_n({\bf C})}$ .

By fairly standard arguments, the above classification theorems for approximate groups can be used to give bounds on the expansion and diameter of Cayley graphs, for instance one can establish a conjecture of Babai and Seress that connected Cayley graphs on absolutely almost simple groups over a finite field have polylogarithmic diameter at most. Applications to expanders include the result on Suzuki groups mentioned in a previous post; further applications will appear in a forthcoming paper.

Apart from the general structural theory of algebraic groups, and some quantitative analogues of the basic theory of algebraic geometry (which we chose to obtain via ultrafilters, as discussed in this post), we rely on two basic tools. Firstly, we use a version of the pivot argument developed first by Konyagin and Bourgain-Glibichuk-Konyagin in the setting of sum-product estimates, and generalised to more non-commutative settings by Helfgott; this is discussed in this previous post. Secondly, we adapt an argument of Larsen and Pink (which we learned from a paper of Hrushovski) to obtain a sharp bound on the extent to which a sufficiently Zariski-dense approximate groups can concentrate in a (bounded complexity) subvariety; this is discussed at the end of this blog post.

	tt on A Host–Kra F^omega_2-sys…
	Joe Smith on Mathematics for Humanity initi…
	Michael Ruxton on A counterexample to the period…
	KEW on Equidistribution of Syracuse r…
	a on A Host–Kra F^omega_2-sys…
	Alison Playle on A new proof of the density Hal…
	Alison Playle on A new proof of the density Hal…
	Anonymous on A new proof of the density Hal…
	Anonymous on A new proof of the density Hal…
	a on A Host–Kra F^omega_2-sys…
	Anonymous on A Host–Kra F^omega_2-sys…
	Arman on A Host–Kra F^omega_2-sys…
	Solomon Ucko on There’s more to mathematics th…
	Eric Naslund on Density Hales-Jewett and Moser…
	Eric Naslund on Density Hales-Jewett and Moser…

Tag Archive

Nested approximate subgroups

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

254A, Notes 8: The microstructure of approximate groups

254A, Notes 7: Models of ultra approximate groups

The structure of approximate groups

254A, Notes 6: Ultraproducts as a bridge between hard analysis and soft analysis

254A, Notes 0: Hilbert’s fifth problem and related topics

Approximate subgroups of linear groups

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

For commenters