Tag Archive

You are currently browsing the tag archive for the ‘Larsen-Pink inequality’ tag.

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 »

Linear approximate groups

27 January, 2010 in math.CO, math.GR, paper | Tags: Ben Green, Emmanuel Breuillard, Helfgott theorem, Larsen-Pink inequality | by Terence Tao | 16 comments

Emmanuel Breuillard, Ben Green, and I have just uploaded to the arXiv our announcement “Linear approximate groups“, submitted to Electronic Research Announcements.

The main result is a step towards the classification of ${K}$ -approximate groups, in the specific setting of simple and semisimple Lie groups (with some partial results for more general Lie groups). For ${K \geq 1}$ , define a ${K}$ -approximate group to be a finite subset ${A}$ of a group ${G}$ which is a symmetric neighbourhood of the origin (thus ${1 \in A}$ and ${A^{-1} := \{a^{-1}: a \in A \}}$ is equal to ${A}$ ), and such that the product set ${A \cdot A}$ is covered by ${K}$ left-translates (or equivalently, ${K}$ right-translates) of ${A}$ . For ${K=1}$ , this is the same concept as a finite subgroup of ${G}$ , but for larger values of ${K}$ , one also gets some interesting objects which are close to, but not exactly groups, such as geometric progressions ${\{ g^n: -N \leq n \leq N \}}$ for some ${g \in G}$ and ${N \geq 1}$ .

The expectation is that ${K}$ -approximate groups are ${C_K}$ -controlled by “structured” objects, such as actual groups and progressions, though the precise formulation of this has not yet been finalised. (We say that one finite set ${A}$ ${K}$ -controls another ${B}$ if ${A}$ is at most ${K}$ times larger than ${B}$ in cardinality, and ${B}$ can be covered by at most ${K}$ left translates or right translates of ${A}$ .) The task of stating and proving this statement is the noncommutative Freiman theorem problem, discussed in these earlier blog posts.

While this problem remains unsolved for general groups, significant progress has been made in special groups, notably abelian, nilpotent, and solvable groups. Furthermore, the work of Chang (over ${{\mathbb C}}$ ) and Helfgott (over ${{\Bbb F}_p}$ ) has established the important special cases of the special linear groups ${SL_2(k)}$ and ${SL_3(k)}$ :

Theorem 1 (Helfgott’s theorem) Let ${d = 2,3}$ and let ${k}$ be either ${{\Bbb F}_p}$ or ${{\mathbb C}}$ for some prime ${p}$ . Let ${A}$ be a ${K}$ -approximate subgroup of ${G = SL_d(k)}$ .

If ${A}$ generates the entire group ${SL_d(k)}$ (which is only possible in the finite case ${k={\Bbb F}_p}$ ), then ${A}$ is either controlled by the trivial group or the whole group.

If ${d=2}$ , then ${A}$ is ${K^{O(1)}}$ -controlled by a solvable ${K^{O(1)}}$ -approximate subgroup ${B}$ of ${G}$ , or by ${G}$ itself. If ${k={\mathbb C}}$ , the latter possibility cannot occur, and ${B}$ must be abelian.

Our main result is an extension of Helfgott’s theorem to ${SL_d(k)}$ for general ${d}$ . In fact, we obtain an analogous result for any simple (or almost simple) Chevalley group over an arbitrary finite field (not necessarily of prime order), or over ${{\mathbb C}}$ . (Standard embedding arguments then allow us to in fact handle arbitrary fields.) The results from simple groups can also be extended to (almost) semisimple Lie groups by an approximate version of Goursat’s lemma. Given that general Lie groups are known to split as extensions of (almost) semisimple Lie groups by solvable Lie groups, and Freiman-type theorems are known for solvable groups also, this in principle gives a Freiman-type theorem for arbitrary Lie groups; we have already established this in the characteristic zero case ${k={\mathbb C}}$ , but there are some technical issues in the finite characteristic case ${k = {\Bbb F}_q}$ that we are currently in the process of resolving.

We remark that a qualitative version of this result (with the polynomial bounds ${K^{O(1)}}$ replaced by an ineffective bound ${O_K(1)}$ ) was also recently obtained by Hrushovski.

Our arguments are based in part on Helfgott’s arguments, in particular maximal tori play a major role in our arguments for much the same reason they do in Helfgott’s arguments. Our main new ingredient is a surprisingly simple argument, which we call the pivot argument, which is an analogue of a corresponding argument of Konyagin and Bourgain-Glibichuk-Konyagin that was used to prove a sum-product estimate. Indeed, it seems that Helfgott-type results in these groups can be viewed as a manifestation of a product-conjugation phenomenon analogous to the sum-product phenomenon. Namely, the sum-product phenomenon asserts that it is difficult for a subset of a field to be simultaneously approximately closed under sums and products, without being close to an actual field; similarly, the product-conjugation phenomenon asserts that it is difficult for a union of (subsets of) tori to be simultaneously approximately closed under products and conjugations, unless it is coming from a genuine group. In both cases, the key is to exploit a sizeable gap between the behaviour of two types of “pivots” (which are scaling parameters ${\xi}$ in the sum-product case, and tori in the product-conjugation case): ones which interact strongly with the underlying set ${A}$ , and ones which do not interact at all. The point is that there is no middle ground of pivots which only interact weakly with the set. This separation between interacting (or “involved”) and non-interacting (or “non-involved”) pivots can then be exploited to bootstrap approximate algebraic structure into exact algebraic structure. (Curiously, a similar argument is used all the time in PDE, where it goes under the name of the “bootstrap argument”.)

Below the fold we give more details of this crucial pivot argument.

One piece of trivia about the writing of this paper: this was the first time any of us had used ~~modern~~ version control software to collaboratively write a paper; specifically, we used Subversion, with the repository being hosted online by xp-dev. (See this post at the Secret Blogging Seminar for how to get started with this software.) There were a certain number of technical glitches in getting everything to install and run smoothly, but once it was set up, it was significantly easier to use than our traditional system of emailing draft versions of the paper back and forth, as one could simply download and upload the most recent versions whenever one wished, with all changes merged successfully. I had a positive impression of this software and am likely to try it again in future collaborations, particularly those involving at least three people. (It would also work well for polymath projects, modulo the technical barrier of every participant having to install some software.)

Read the rest of this entry »

	Multiple recurrence… on Open question: best bounds for…
	Multiple recurrence… on The inverse conjecture for the…
	Multiple recurrence… on An inverse theorem for the uni…
	Multiple recurrence… on 254A, Lecture 16: A Ratner-typ…
	Multiple recurrence… on 254A, Lecture 13: Compact…
	Multiple recurrence… on 254A, Lecture 9: Ergodici…
	Multiple recurrence… on 254A, Lecture 8: The mean ergo…
	Mauricio Calvao on A mathematical formalisation o…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Bisogna essere un ge… on Ask yourself dumb questions –…
	Bisogna essere un ge… on Enjoy your work
	Bisogna essere un ge… on Be sceptical of your own …
	Bisogna essere un ge… on Be patient
	Bisogna essere un ge… on Attend talks and conferences,…
	Bisogna essere un ge… on Don’t be afraid to learn thing…

Tag Archive

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

Linear 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”