Tag Archive

You are currently browsing the tag archive for the ‘special linear group’ 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 »

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

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

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

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

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

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

Remark 2 For minor technical reasons, it will be convenient later on to allow ${S}$ to contain the identity and to come with multiplicity (i.e. it will be a multiset rather than a set). If one does so, of course, the resulting Cayley graph will now contain some loops and multiple edges.

For the purposes of building expander families, we would of course want the underlying group ${G}$ to be finite. However, it will be convenient at various times to “lift” a finite Cayley graph up to an infinite one, and so we permit ${G}$ to be infinite in our definition of a Cayley graph.

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

Definition 2 (Schreier graph) Let ${G}$ be a finite group that acts (on the left) on a space ${X}$ , thus there is a map ${(g,x) \mapsto gx}$ from ${G \times X}$ to ${X}$ such that ${1x = x}$ and ${(gh)x = g(hx)}$ for all ${g,h \in G}$ and ${x \in X}$ . Let ${S}$ be a symmetric subset of ${G}$ which acts freely on ${X}$ in the sense that ${sx \neq x}$ for all ${s \in S}$ and ${x \in X}$ , and ${sx \neq s'x}$ for all distinct ${s,s' \in S}$ and ${x \in X}$ . Then the Schreier graph ${Sch(X,S)}$ is defined to be the graph with vertex set ${X}$ and edge set ${\{ \{sx,x\}: x \in X, s \in S \}}$ .

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

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

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

Exercise 2 (Qualitative expansion) Let ${Cay(G,S)}$ be a finite Cayley graph.

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

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

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

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

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

of subsets of ${G}$ .

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

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

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

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

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

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

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

where ${\mu}$ is the probability density

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

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

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

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

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

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

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

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

obeys either (2) or (3).

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

Exercise 5 (Random walk description of expansion) Let ${Cay(G_n,S_n)}$ be a family of finite ${k}$ -regular Cayley graphs, and let ${\mu_n}$ be the associated probability density functions. Let ${A > 1/2}$ be a constant.

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

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

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

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

Read the rest of this entry »

	Terence Tao on Multiple recurrence and conver…
	Joel Moreira on Multiple recurrence and conver…
	mathtuition88 on Does one have to be a genius t…
	The Beauty of Bounde… on Simons Lecture I: Structure an…
	The Beauty of Bounde… on Marker lecture III: “Sma…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Anonymous on Notes on the classification of…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	Luqing Ye on 245A, Notes 2: The Lebesgue…
	mixedmath on Multiple recurrence and conver…
	Multiple recurrence… on Open question: best bounds for…
	Multiple recurrence… on The inverse conjecture for the…

Tag Archive

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

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

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”