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

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 (Diameter 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^{-1} A}$ . Thus ${A^{-1} A = 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.

— 1. The sum-product theorem —

Consider a finite non-empty subset ${A}$ of a field ${k}$ . Then we may form the sumset

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

and the product set

$\displaystyle A \cdot A := \{ab: ab \in A \}.$

The minimal sizes of such sets are well understood:

Exercise 5 Let ${A}$ be a finite non-empty subset of a field ${k}$ .

(i) Show that ${|A+A| \geq |A|}$ , with equality occuring if and only if ${A}$ is an additive coset ${A = x+H}$ of an finite additive subgroup ${H}$ of ${k}$ with some ${x \in k}$ .

(ii) Show that ${|A\cdot A|\geq |A|}$ , with equality occuring if and only if ${A}$ is either equal to a multiplicative coset ${A = gH}$ of a finite multiplicative subgroup ${H}$ of ${k^\times := k \backslash \{0\}}$ with some ${g \in k^\times}$ , or the set ${\{0\}}$ , or the set ${\{0\} \cup gH}$ where ${gH}$ is a multiplicative coset.

(iii) Show that ${\max(|A+A|, |A\cdot A|\geq |A|}$ , with equality occuring if and only if ${A}$ is either equal to a multiplicative dilate ${A = cF}$ of a finite subfield ${F}$ of ${k}$ with ${c \in k^\times}$ , a singleton set, or an additive subgroup of order ${2}$ .

The sum-product phenomenon is a robust version of the above observation, asserting that one of ${A+A}$ or ${A\cdot A}$ must be significantly larger than ${A}$ if ${A}$ is not somehow “close” to a genuine subfield of ${k}$ . Here is one formulation of this phenomenon:

Theorem 5 (Sum-product theorem) Let ${\epsilon>0}$ be a sufficiently small number. Then for any field ${k}$ and any finite non-empty subset ${A}$ , one of the following statements hold:

(Expansion) ${\max(|A+A|, |A\cdot A|) \geq |A|^{1+\epsilon}}$ .

(Close to a subfield) There is a dilate ${cF}$ of a subfield ${F}$ of ${k}$ with ${|F| \ll |A|^{1+O(\epsilon)}}$ and ${c\neq 0}$ which contains all but ${O(|A|^{O(\epsilon)})}$ elements of ${A}$ .

(Smallness) ${A}$ is an additive subgroup of order ${2}$ .

If ${k}$ has characteristic zero, then the second option here cannot occur, and we conclude that ${\max(|A+A|,|A \cdot A|) \geq |A|^{1+\epsilon}}$ for some absolute constant ${\epsilon>0}$ as soon as ${A}$ contains at least two non-zero elements, a claim first established in ${{\bf R}}$ by Erdos and Szemeredi. When ${k}$ is a finite field of prime order, the second option can only occur when ${F=k}$ , and we conclude that ${\max(|A+A|,|A \cdot A|) \geq |A|^{1+\epsilon}}$ as soon as ${|A| \leq |k|^{1-C\epsilon}}$ whenever ${\epsilon}$ is sufficiently small, ${C}$ is an absolute constant, and ${A}$ has at least two non-zero elements. A preliminary version of this result (which required more size assumptions on ${A}$ , in particular a bound of the shape ${|A| \geq |k|^\delta}$ ) was obtained by Bourgain, Katz, and Tao, with the version stated above first obtained by Bourgain, Glibichuk, and Konyagin. The proof given here is drawn from my book with Van, and was originally inspired by this paper of Bourgain and Konyagin.

Remark 1 There has been a substantial amount of literature on trying to optimise the exponent ${\epsilon}$ in the sum-product theorem. A relatively recent survey of this literature can be found in this paper of mine (and in the references to the other papers cited in this remark). In ${{\bf R}}$ , the best result currently in this direction is by Solymosi, who established that one can take ${\epsilon}$ arbitrarily close to ${1/3}$ ; for ${{\bf C}}$ , the best result currently is by Rudnev, who shows that one can take ${\epsilon}$ arbitrarily close to ${19/69}$ . For fields of prime order, one can take ${\epsilon}$ arbitrarily close to ${1/11}$ , a result of Rudnev; an extension to arbitrary finite fields was then obtained by Li and Roche-Newton.

We now start proving Theorem 5. As with Theorem 2, the engine of the proof is a dichotomy similar to that of Proposition 3. Whilst the former proposition was modeled on the basic group-theoretic assertion that cosets ${gH}$ of a subgroup where either identical or disjoint, this proposition is modeled on the basic linear algebra fact that if ${F}$ is a subfield of ${k}$ and ${\xi \in k}$ , then ${F+\xi F}$ is either of size ${|F|^2}$ , or of size ${|F|}$ .

Lemma 6 (Dichotomy) Let ${k}$ be a field, let ${A}$ be a finite non-empty subset of ${k}$ , and let ${\xi \in k}$ . Then at least one of the following statements hold:

(Non-involved case) ${|A + \xi A| = |A|^2}$ .

(Involved case) ${|A + \xi A| \leq |(A-A) A +(A-A) A|}$ .

Proof: Suppose that we are not in the non-involved case, thus ${|A + \xi A| \neq |A|^2}$ . Then the map ${(a,b) \mapsto a+\xi b}$ from ${A\times A}$ to ${k}$ is not injective, and so there exists ${a,b,c,d \in A}$ with ${(a,b) \neq (c,d)}$ and

$\displaystyle a+\xi b = c+\xi d.$

In particular, ${b \neq d}$ . We then have ${\xi = (a-c)/(d-b)}$ and so

$\displaystyle |A + \xi A| = |(d-b) A + (a-c) A| \leq |(A-A) A +(A-A) A|.$

$\Box$

Remark 2 One can view ${A+\xi A}$ as measuring the extent to which the dilate ${\xi A}$ of ${A}$ is “transverse” to ${A}$ . As the “slope” ${\xi}$ varies, ${\xi A}$ “pivots” around the origin, encountering both the (relatively rare) involved slopes, and the (generic) non-involved slopes. It is this geometric picture which led to the term “pivot argument”, as used in particular by Helfgott (who labeled the non-involved slopes as “pivots”).

This dichotomy becomes useful if there is a significant gap between ${|(A-A) A +(A-A) A|}$ and ${|A|^2}$ . Let’s see how. To prove Theorem 5, we may assume that ${|A|}$ is larger than some large absolute constant ${C}$ , as the claim follows from Exercise 5 otherwise (making ${\epsilon}$ small enough depending on ${C}$ ). by deleting ${0}$ from ${A}$ , and tweaking ${\epsilon}$ , noting that we may then assume that ${A}$ does not contain ${0}$ . We suppose that

$\displaystyle |A+A|, |A\cdot A|\leq K|A|$

for some ${K \leq |A|^{\epsilon_0}}$ and some sufficiently small absolute constant ${\epsilon_0}$ . In particular we see that ${|A|}$ will exceed any quantity of the form ${O(K^{O(1)})}$ if we make ${\epsilon_0}$ small enough and ${C}$ large enough.

We would like to boost this control of sums and products to more complex combinations of ${A}$ . We will need some basic tools from additive combinatorics.

Lemma 7 (Ruzsa triangle inequality) If ${A,B,C}$ are non-empty finite subsets of ${k}$ , then ${|A-C| \leq \frac{|A-B||B-C|}{|B|}}$ .

Proof: This is the additive version of Exercise 4 from Notes 4. $\Box$

Lemma 8 (Ruzsa covering lemma) If ${A, B}$ are non-empty finite subsets of ${k}$ , then ${A}$ can be covered by at most ${\frac{|A+B|}{|B|}}$ translates of ${B-B}$ .

Proof: This is the additive version of Exercise 5 from Notes 4. $\Box$

Exercise 6 (Sum set estimates) If ${A, B}$ are non-empty finite subsets of ${k}$ such that ${|A+B|\leq K |A|^{1/2}|B|^{1/2}}$ , show that ${A}$ and ${B}$ can both be covered by ${O(K^{O(1)})}$ translates of the same ${O(K^{O(1)})}$ -approximate group ${H}$ , with ${|H| \ll K^{O(1)} |A|}$ . Conclude that

$\displaystyle |n_1 A - n_2 A + n_3 B - n_4 B| \ll_{n_1,n_2,n_3,n_4} K^{O(|n_1|+|n_2|+|n_3|+|n_4|)} |A|$

for any natural numbers ${n_1,n_2,n_3,n_4}$ , where ${nA := A+\ldots+A}$ denotes the sum set of ${n}$ copies of ${A}$ . (Hint: use the additive form of Exercise 7 from Notes 4, and the preceding lemmas.)

These lemmas allow us to improve the sum-product properties of ${A}$ by passing to a large subset ${B}$ (cf. the Balog-Szemeredi-Gowers lemma from Notes 4):

Lemma 9 (Katz-Tao lemma) Let ${A}$ be as above. Then there is a subset ${B}$ of ${A}$ with ${|B| \geq |A|/2K}$ such that ${|B^2-B^2| \ll K^{O(1)} |B|}$ .

Proof: The dilates ${aA}$ of ${A}$ with ${a \in A}$ all lie in a set ${A^2}$ of cardinality at most ${K|A|}$ . Intuitively, this should force a lot of collision between the ${aA}$ , which we will exploit using the sum set estimates. More precisely, observe that

$\displaystyle \| \sum_{a \in A} 1_{aA}\|_{\ell^1}= |A|^2$

and hence by Cauchy-Schwarz

$\displaystyle \| \sum_{a \in A} 1_{aA}\|_{\ell^2}^2 \geq |A|^3/K.$

The left-hand side can be written as

$\displaystyle \sum_{b \in A} \sum_{a\in A}|aA\cap bA|$

and so by the pigeonhole principle we can find ${b_0 \in A}$ such that

$\displaystyle \sum_{a\in A}|aA\cap b_0 A| \geq |A|^2/K.$

We apply a dilation to set ${b_0=1}$ (recall that ${A}$ does not contain ${0}$ ). If we set ${B := \{a \in A: |aA\cap A| \geq |A|/2K\}}$ , we conclude that

$\displaystyle \sum_{a \in B}|aA\cap A| \geq |A|^2/2K$

which implies in particular that

$\displaystyle |B|\geq |A|/2K$

If ${a \in B}$ , then

$\displaystyle |aA \cap A| \geq |A|/2K;$

since ${|aA + aA| \leq K|A|}$ we also have

$\displaystyle |aA + (aA \cap A)| \leq K|A|$

and similarly

$\displaystyle |A + (aA \cap A)| \leq K|A|$

and thus by the Ruzsa triangle inequality

$\displaystyle |aA -A| \ll K^{O(1)} |A|$

whenever ${a \in B}$ . Informally, let us call a non-zero element ${a}$ of ${k}$ good if ${|aA - A| \ll K^{O(1)} |A|}$ (but note that this notion of “good” is a bit fuzzy, as it depends on the choice of implied constants in the ${O()}$ notation). Observe that if ${a,a'}$ are good, then

$\displaystyle |aa' A - a A|, |a A - A| \ll K^{O(1)} |A|$

and thus by the Ruzsa triangle inequality

$\displaystyle |aa' A - A| \ll K^{O(1)} |A|,$

thus the product of two good elements are good (with somewhat worse implied constants). Similarly, from the Ruzsa covering lemma we see that ${aA}$ and ${a' A}$ are both covered by ${O(K^{O(1)})}$ translates of ${A-A}$ , and from this and sum set estimates we see that

$\displaystyle |(a+a')A-A| \ll K^{O(1)} |A|$

and so the sum of two good elements is again good. Similarly the difference of good elements is good. Applying all these facts, we conclude that all the elements of ${B^2-B^2}$ are good, thus ${|gA-A| \ll K^{O(1)} |A|}$ for all ${g \in B^2-B^2}$ . In particular, since ${|A|}$ exceeds ${K^{O(1)}}$ , we see from the Cauchy-Schwarz inequality that for each ${g \in B^2-B^2}$ , there are ${\gg |A|^3/K^{O(1)}}$ solutions to the equation ${ga_1-a_2=ga_3-a_4}$ with ${a_1 \neq a_3}$ and ${a_1,a_2,a_3,a_4 \in A}$ . However, there are only ${|A|^4}$ possible choices for ${a_1,a_2,a_3,a_4}$ , and each such choice uniquely determines ${g}$ , so there are at most ${O(K^{O(1)} |A|)}$ possible choices for ${g}$ , and the claim follows. $\Box$

Note that one could replace ${B^2-B^2}$ in the above lemma by any other homogeneous polynomial combination of ${B}$ .

By applying a dilation, we may assume that ${B}$ contains ${1}$ . Applying Proposition 6 to this set ${B}$ (and using sum set estimates), we arrive at the following dichotomy: every field element ${\xi \in k}$ is either “non-involved” in the sense that ${|B+\xi B| = |B|^2}$ , or is “involved” in the sense that ${|B+\xi B| \leq C_1 K^{C_1} |B|}$ for some fixed absolute constant ${C_1}$ . By sum set estimates we have ${|B+BB| \ll K^{O(1)} |B|}$ ; as we can assume that ${|A|}$ , and hence ${|B|}$ , is larger than any quantity of the form ${O(K^{O(1)})}$ , this forces all elements of ${B}$ to be involved.

To exploit this, observe (by repeating the proof of Proposition 6) that if ${\xi_1,\xi_2}$ are involved, then the quantities ${\xi = \xi_1\xi_2, \xi_1+\xi_2, \xi_1-\xi_2}$ are somewhat involved in the sense that

$\displaystyle |B + \xi B|\ll K^{O(1)} |B|$

for those choices of ${\xi}$ (where the implied constants depend on ${C_1}$ ). But as we can assume that ${|A|}$ , and hence ${|B|}$ , is larger than any quantity of the form ${O(K^{O(1)})}$ , we see from Proposition 6 that this forces ${\xi}$ to be involved as well (this is the crucial step at which approximate structure is improved to exact structure). We thus see that the set ${F}$ of all involved elements is closed under multiplication, addition, and subtraction; as it also contains ${0}$ , it is a subring of ${k}$ . Arguing as in the proof of Proposition 6, we have that ${F}$ is finite with ${|F|\ll K^{O(1)} |A|}$ ; in particular, ${F}$ must now be a finite subfield of ${k}$ .

Now we enter the “endgame”, in which we use this ${F}$ to control ${A}$ . By previous discussion, ${F}$ contains ${B}$ , and thus ${|A \cap F| \gg K^{-O(1)} |A|}$ . By the Ruzsa triangle inequality applied to ${A, A \cap F, F}$ , this implies that ${|A+F| \ll K^{O(1)} |F|}$ , and so ${A}$ can be covered by ${O(K^{O(1)})}$ translates of ${F}$ . A similar argument applied multiplicatively shows that ${A}$ can be covered by ${O(K^{O(1)})}$ dilates of ${F}$ . Since a non-trivial translate of ${F}$ and a non-trivial dilate of ${F}$ intersect in at most one point, we conclude that ${A}$ has at most ${O(K^{O(1)})}$ elements outside of ${F}$ , and the claim follows.

Remark 3 One can abstract this argument by replacing the multiplicative structure here by an abelian group action; see this paper of Helfgott for details. The argument can also extend to non-commutative settings, such as division algebras or more generally to arbitrary rings (though in the latter case, the presence of non-trivial zero-divisors becomes a very significant issue); see this paper for details.

— 2. Finite subgroups of ${SL_2}$ —

We will shortly establish Theorem 1, which can be viewed as a way to describe approximate subgroups of ${SL_d(k)}$ . Before we do so, let us first warm up and digress slightly by by studying genuine finite subgroups ${A}$ of ${SL_d(k)}$ , in the model case ${d=2}$ , for which ad hoc explicit calculations are available. In order to make the algebraic geometry of the situation cleaner, it is convenient to embed the field ${k}$ in its algebraic closure ${\overline{k}}$ , and similarly embed ${SL_2(k)}$ in ${SL_2(\overline{k})}$ . This is a group which is also an algebraic variety (identifying the space of ${2 \times 2}$ matrices with coefficients in ${\overline{k}}$ with ${\overline{k}^4}$ ), whose group operations are algebraic (in fact, polynomial) maps; in other words, ${SL_2(\overline{k})}$ is an algebraic group. We now consider the question of what finite subgroups of ${SL_2(\overline{k})}$ can look like. This is a classical question, with a complete classification obtained by Dickson in 1901. The precise classification is somewhat complicated; to give just a taste of this complexity, we observe that the symmetry group of the isocahedron is a finite subgroup of ${SO_3({\bf R})}$ , which can be lifted to the spin group ${Spin_3({\bf R})}$ (giving what is known as the binary isocahedral group, a group of order ${120}$ ), which is a subgroup of ${Spin_3({\bf C})}$ , which can be identified with ${SL_2({\bf C})}$ . Because of this, it is possible for some choices of finite field ${k}$ to embed the binary isocahedral group into ${SL_2(\overline{k})}$ or ${SL_2(k)}$ . Similar considerations obtain for the symmetry group of other Platonic solids. However, if one is willing to settle for a “rough” classification, in which one ignores groups of bounded size (and more generally, is willing just to describe a bounded index subgroup of the group ${A}$ ), the situation becomes much simpler. In the characteristic zero case ${k={\bf C}}$ , for instance, we have Jordan’s theorem, which asserts that given a finite subgroup ${A}$ of ${SL_d({\bf C})}$ for some ${d=O(1)}$ , a bounded index subgroup of ${A}$ is abelian. (Jordan’s theorem was discussed further in last quarter’s course.) The finite characteristic case is inherently more complicated though (due in large part to the proliferation of finite subfields), with a satisfactory rough classification only becoming available for general ${d}$ with the work of Larsen and Pink (published in 2011, but which first appeared as a preprint in 1998). However, the ${d=2}$ case is significantly simpler and can be treated by somewhat ad hoc methods, as we shall now do. The discussion here is loosely based on this paper of Kowalski.

We pause to recall some basic structural facts about ${SL_2(\overline{k})}$ . Elements of this group are ${2 \times 2}$ matrices with determinant one, and thus have two (algebraic, possibly repeated) eigenvalues ${t, t^{-1}}$ for some ${t\in \overline{k}}$ (note here that we are using the algebraically closed nature of ${\overline{k}}$ ). This allows us to classify elements of ${SL_2(\overline{k})}$ into three classes:

The central elements ${\pm 1}$ ;
The regular unipotent elements and their negations, which are non-central elements with a double eigenvalue at ${+1}$ (or a double eigenvalue at ${-1}$ ); and
The regular semisimple elements, which have two distinct eigenvalues.

We collectively refer to regular unipotent elements and their negations as regular projectively unipotent elements.

Remark 4 The presence of the non-identity central element ${-1}$ leads to some slight technical annoyances (for instance, it means that ${SL_2}$ merely an almost simple algebraic group rather than a simple one, in the sense that the only normal algebraic subgroups are finite). One can eliminate this element by working instead with the projective special linear group ${PSL_2:= SL_2/\{\pm 1\}}$ , but we will not do so here. We remark that if one works in ${SL_d}$ for ${d>2}$ then the classification of elements becomes significantly more complicated, for instance there exist elements which are semisimple (i.e. diagonalisable) but neither regular nor central, because some but not all of the eigenvalues may be repeated.

One can distinguish the unipotent elements from the semisimple ones using the trace: unipotent elements have trace ${+2}$ , their negations have trace ${-2}$ , and the semisimple elements have traces distinct from ${\pm 2}$ . The ability to classify elements purely from the trace is a very special fact concerning ${SL_2}$ which breaks down completely for higher rank matrix groups, but we will not hesitate to take advantage of this fact here.

Associated to the above classification are some natural algebraic subgroups of ${SL_2(\overline{k})}$ , including the standard maximal torus

$\displaystyle T(\overline{k}) := \{ \begin{pmatrix} t & 0 \\ 0 & t^{-1} \end{pmatrix}: t \in \overline{k}^\times \},$

the one-dimensional standard unipotent group

$\displaystyle U(\overline{k}) := \{ \begin{pmatrix} 1 & x \\ 0 & 1 \end{pmatrix}: x \in \overline{k} \},$

and the two-dimensional standard Borel subgroup

$\displaystyle B(\overline{k}) := \{ \begin{pmatrix} t & x \\ 0 & t^{-1} \end{pmatrix}: x \in \overline{k}; t \in \overline{k}^\times \}.$

More generally, we define a maximal torus of ${SL_2(\overline{k})}$ to be a conjugate (in ${SL_2(\overline{k})}$ ) of the standard maximal torus, a unipotent group to be a conjugate of the standard unipotent group, and a Borel subgroup to be a conjugate of the standard Borel subgroup. (This is not really the “right” way to define these groups, for the purpose of generalisation to other algebraic groups, but will suffice as long as we are only working with ${SL_2}$ .) Note that one can also think of a Borel subgroup as the stabiliser of a one-dimensional subspace of ${\overline{k}^2}$ (using the obvious action of ${SL_2(\overline{k})}$ on ${\overline{k}^2}$ ). Using the Jordan normal form (again taking advantage of the algebraically closed nature of ${\overline{k}}$ ), we can see how these groups interact with group elements:

The central elements lie in every maximal torus and every Borel subgroup. The identity ${+1}$ lies in every unipotent group, but ${-1}$ lies in none of them.
Every regular unipotent element lies in exactly one unipotent group, which in turn lies in exactly one Borel subgroup (the normaliser of the unipotent group). Conversely, a unipotent group consists entirely of regular unipotent elements and the identity ${+1}$ .
Every regular semisimple element lies in exactly one maximal torus, which in turn lies in exactly two Borel subgroups (the stabiliser of one of the eigenspaces of a regular semisimple element in the torus). Conversely, a maximal torus consists entirely of regular semisimple elements and the central elements ${\pm 1}$ .

Remark 5 If one was working in a non-algebraically closed field ${F}$ instead of in ${\overline{k}}$ , one could subdivide the regular semisimple elements into two classes, the split case when the elements can be diagonalised inside ${F}$ , and the non-split case when they can only be diagonalised in a quadratic extension of ${F}$ . This similarly subdivides maximal tori into two families, the split tori and the non-split tori. In the case when one is working over the field ${{\bf R}}$ , the unipotent, split semisimple, and non-split semisimple elements are referred to as parabolic, hyperbolic, and elliptic elements of ${SL_2({\bf R})}$ respectively. Fortunately, in our applications we can work in algebraically closed fields and avoid these sorts of finer distinctions.

Ignoring the exceptional small examples of subgroups of ${SL_2(\overline{k})}$ , such as the binary isocahedral group mentioned earlier, there are two obvious ways to generate subgroups of ${SL_2(\overline{k})}$ . One is to pass from ${\overline{k}}$ to a subfield ${F}$ , creating “arithmetic” subgroups of the form ${SL_2(F)}$ (or conjugates thereof). The other is to replace ${SL_2}$ with an algebraic subgroup of the three-dimensional group ${SL_2}$ , such as the maximal tori, unipotent groups, and Borel subgroups mentioned earlier. (Actually, these are the only (connected) proper algebraic subgroups of ${SL_2}$ , as can be seen by consideration of the associated Lie algebras.)

Observe that if ${A = SL_2(F)}$ is an arithmetic subgroup, then its intersections ${T(F) := A \cap T(\overline{k})}$ , ${U(F) := A \cap U(\overline{k})}$ , ${B(F) := A \cap B(\overline{k})}$ capture a portion of ${A}$ proportionate to the dimensions involved, or more precisely that

$\displaystyle |A \cap T(\overline{k})| \ll |A|^{1/3}; |A \cap U(\overline{k})| \ll |A|^{1/3}; \quad |A \cap B(\overline{k})| \ll |A|^{2/3}.$

Indeed, it is easy to see that ${|A| = |SL_2(F)| \sim |F|^3}$ , ${|A \cap T(\overline{k})| = |T(F)| \sim |F|}$ , and so forth. An important and general observation of Larsen and Pink is that this sort of behaviour is shared by all other finite subgroups of algebraic groups such as ${SL_2(\overline{k})}$ , as long as these groups are not (mostly) trapped in a proper algebraic subgroup. We first illustrate this phenomenon for the torus groups:

Proposition 10 (Larsen-Pink inequality, special case) Let ${A}$ be a finite subgroup of ${SL_2(\overline{k})}$ . Then one of the following statements hold:

(Non-concentration) For any maximal torus ${T}$ , one has ${|A \cap T| \ll |A|^{1/3}}$ .

(Trapping) There is a Borel subgroup ${B}$ such that ${|A \cap B| \gg |A|}$ .

Proof: Suppose that the trapping hypothesis fails, thus ${|A \cap B| = o(|A|)}$ for all Borel subgroups ${B}$ , where we interpret ${o(|A|)}$ here to mean “less than ${\epsilon |A|}$ for an arbitrarily small constant ${\epsilon>0}$ which we are at liberty to choose”. (If one is uncomfortable with this type of definition, one can instead consider a sequence of potential counterexamples ${A = A_n}$ to the above proposition in various groups ${SL_2(\overline{k_n})}$ , in which ${\sup_B |A \cap B| = o_{n \rightarrow \infty}(|A|)}$ . Alternatively, one can also rephrase this argument if desired in the language of nonstandard analysis.) In particular, we see that any coset of ${B}$ occupies a fraction ${o(1)}$ at most of ${A}$ . Thus, for instance, if we select an element ${\begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ from ${A}$ uniformly at random, then with probability ${1-o(1)}$ , ${b}$ is non-zero, and similarly for ${a,c,d}$ . To put it more informally, the matrix entries of an element of ${A}$ are “generically” non-zero. Similarly if we first conjugate ${A}$ by a fixed group element.

We need to show that ${|A \cap T| \ll |A|^{1/3}}$ for any maximal torus ${T}$ . By conjugation we may take ${T}$ to be the standard maximal torus ${T = T(\overline{k})}$ . Set ${A' := A \cap T(\overline{k})}$ , then ${A'}$ is a subgroup of ${A}$ of the form

$\displaystyle A' := \{ \begin{pmatrix} t & 0 \ & t^{-1} \end{pmatrix}: t\in H \}$

for some finite multiplicative subgroup ${H}$ of ${\overline{k}^\times}$ . We may assume that ${|H|}$ is larger than any given absolute constant, as the claim is trivial otherwise. Our task is to show that ${|H|^3 \ll |A|}$ .

Let ${g = \begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ be a typical element of ${A}$ . By the preceding discussion, we may assume that ${a,b,c,d}$ are all non-zero. Since ${A'}$ is a subgroup of ${A}$ , we have ${A' g A' g A' \subset A}$ , thus

$\displaystyle \begin{pmatrix} t_1 & 0 \\ 0 & t_1^{-1} \end{pmatrix} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} t_2 & 0 \\ 0 & t_2^{-1} \end{pmatrix} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} t_3 & 0 \\ 0 & t_3^{-1} \end{pmatrix} \in A$

for all ${t_1,t_2,t_3 \in H}$ . We evaluate the inner matrix products to obtain that

$\displaystyle \begin{pmatrix} t_1 & 0 \\ 0 & t_1^{-1} \end{pmatrix} \begin{pmatrix} a^2 t_2 + bc t_2^{-1} & ac t_2 + bd t_2^{-1} \\ ac t_2 + cd t_2^{-1} & bc t_2 + d^2 t_2^{-1} \end{pmatrix} \begin{pmatrix} t_3 & 0 \\ 0 & t_3^{-1} \end{pmatrix} \in A$

for ${t_1,t_2,t_3 \in H}$ .

Because ${a,b,c,d}$ are non-zero, we see that for all but ${O(1)}$ values of ${t_2}$ , all four entries of the middle matrix here are non-zero. As a consequence, if one fixes ${t_2}$ and lets ${t_1,t_3}$ vary, all of the triple products given above are distinct. Note that if one takes the above triple product and multiplies the diagonal entries together, the ${t_1, t_3}$ terms cancel and one obtains ${(a^2 t_2 + bc t_2^{-1}) (bc t_2 + d^2 t_2^{-1})}$ . This rational map (as a function of ${t_2}$ ) is at most four-to-one; each value of this map is associated to at most four values of ${t_2}$ . Putting all this together, we conclude that there are ${\gg |H|^3}$ different triple products one can form here as ${t_1,t_2,t_3 \in H}$ vary, and the claim follows. $\Box$

Exercise 7 Establish a variant of Proposition 10 in which the maximal tori are replaced by unipotent groups.

Given a group element ${g \in SL_2(\overline{k})}$ , let ${Conj(g) := \{ hgh^{-1}: h \in SL_2(\overline{k}) \}}$ be the conjugacy class of ${g}$ . The behaviour of this class depends on the nature of ${g}$ :

Exercise 8 Let ${g}$ be an element of ${SL_2(\overline{k})}$ .

(i) If ${g}$ is central, show that ${Conj(g) = \{\pm 1\}}$ .

(ii) If ${g}$ is regular unipotent, show that ${Conj(g)}$ is the space of all regular unipotent elements.

(iii) If ${g}$ is negative of a regular unipotent element, show that ${Conj(g)}$ is the space of all negatives of regular unipotent elements.

(iv) If ${g}$ is regular semisimple, show that ${Conj(g) := \{ g'\in SL_2(\overline{k}): \hbox{tr}(g)= \hbox{tr}(g')\}}$ .

We can “dualise” the upper bound on maximal tori in Proposition 10 into a lower bound on conjugacy classes:

Proposition 11 (Large conjugacy classes) Let ${A}$ be a finite subgroup of ${SL_2(\overline{k})}$ . Then one of the following statements hold:

(Large conjugacy classes) For any regular semisimple or regular projectively unipotent ${g \in A}$ , one has ${|A \cap Conj(g)| \gg |A|^{2/3}}$ .

(Trapping) There is a Borel subgroup ${B}$ such that ${|A \cap B| \gg |A|}$ .

Proof: As before we may assume that ${|A \cap B| =o(|A|)}$ for all Borel subgroups ${B}$ . Let ${g \in A}$ be regular semisimple, and consider the map ${\phi: h \mapsto hgh^{-1}}$ from ${A}$ to ${A \cap Conj(g)}$ . For each ${g' \in A \cap Conj(g)}$ , the preimage of ${g'}$ by ${\phi}$ is contained in a coset of the centraliser ${C(g') := \{ h \in SL_2(\overline{k}): hg'=g'h\}}$ of ${g'}$ . As ${g}$ (and hence ${g'}$ ) is regular semisimple or regular projectively unipotent, this centraliser is a maximal torus or (two copies of) a unipotent group (this can be seen by placing ${g}$ in Jordan normal form). By Proposition 10 or Exercise 7, we conclude that each preimage of ${\phi}$ has cardinality ${O(|A|^{1/3})}$ , which forces the range to have cardinality ${\gg |A|^{2/3}}$ as claimed. $\Box$

We remark that this gives a dichotomy analogous to Lemma 3 or Lemma 6 in the case ${|A\cap B| =o(|A|)}$ . Namely, for any ${g \in SL_2({\overline{k}})}$ , either ${A \cap Conj(g)}$ is empty, or ${|A \cap Conj(g)| \gg |A|^{2/3}}$ . We will take advantage of a dichotomy similar to this (but for tori instead of conjugacy classes) in the next section.

We can match the lower bound in Proposition 11 with an upper bound:

Proposition 12 (Larsen-Pink inequality, another special case) Let ${A}$ be a finite subgroup of ${SL_2(\overline{k})}$ . Then one of the following statements hold:

(Non-concentration) For any regular semisimple ${g \in SL_2(\overline{k})}$ , one has ${|A \cap Conj(g)| \ll |A|^{2/3}}$ .

(Trapping) There is a Borel subgroup ${B}$ such that ${|A \cap B| \gg |A|}$ .

Proof: Again, we may assume that ${|A \cap B| = o(|A|)}$ for all Borel subgroups ${B}$ . In particular, we may take ${|A|}$ larger than any given absolute constant. Let ${g}$ be regular semisimple, and let ${S:= A \cap Conj(g) =\{ s \in A: \hbox{tr}(s) = \hbox{tr}(g)\}}$ ; our task is to show that ${|S| \ll |A|^{2/3}}$ . Note from Exercise 8 that ${g}$ is conjugate to ${g^{-1}}$ , and so ${S}$ is symmetric: ${S = S^{-1}}$ . Also, ${Sa=aS}$ for all ${a \in A}$ .

Observe that whenever ${a, b \in A}$ and ${s \in S \cap a^{-1} S \cap b^{-1} S}$ , then the triple ${(s,as, bs)}$ lies in ${S^3}$ ; conversely, every triple in ${S^3}$ arises in this manner. Thus we have the identity

$\displaystyle |S|^3 = \sum_{a,b \in A} |S \cap a^{-1} S \cap b^{-1} S|.$

We will show that

$\displaystyle \sum_{a,b \in A} |S \cap a^{-1} S \cap b^{-1} S| \ll |A|^2 + |A|^{4/3} |S|, \ \ \ \ \ (1)$

which will give ${|S| \ll |A|^{2/3}}$ as required.

We now establish (1). We divide into several contributions. First suppose that ${a = \pm 1}$ . Then we bound the summand by ${|S|}$ ; there are ${O(|A|)}$ summands here, leading to a total contribution of ${O(|A| |S|)}$ , which is acceptable. Similarly if ${b=\pm 1}$ , or ${a = \pm b}$ , so we may restrict to the remaining cases when ${\pm 1}$ , ${\pm a}$ , ${\pm b}$ are distinct. In particular, ${a, b}$ are now either regular unipotent or regular semisimple.

We now consider the case in which ${1,a,b}$ are linearly dependent (in the space ${M_2(\overline{k})}$ of ${2\times 2}$ matrices). For fixed ${a}$ , this constrains ${b}$ to either a maximal torus or a unipotent group (depending on whether ${a}$ is regular semisimple or regular projectively unipotent); this is easiest to see by placing ${a}$ in Jordan canonical form. By the preceding results, we see that there are ${O(|A|^{1/3})}$ choices of ${b}$ for each ${|A|}$ , leading to a contribution of ${O( |A|^{4/3} |S| )}$ in this case, which is acceptable. So we may now take ${1,a,b}$ to be linearly independent.

The set ${S \cap a^{-1} S \cap b^{-1} S}$ is the intersection of ${A}$ with the affine line

$\displaystyle \ell := \{ s \in M_2(\overline{k}); \hbox{tr}(s) = \hbox{tr}(as) = \hbox{tr}(bs) = \hbox{tr}(g) \};$

this is indeed a line when ${1,a,b}$ are linearly independent. In most cases, this line ${\ell}$ will intersect ${SL_2(\overline{k})}$ (which we can view as a quadric surface in ${M_2(\overline{k})}$ ) in at most two points, leading to a contribution of ${O(|A|^2)}$ for this case, which is acceptable. The only cases left to treat are when the line ${\ell}$ are incident to ${SL_2(\overline{k})}$ . This only occurs when the line ${\ell}$ takes the form ${hU}$ for some ${h \in SL_2(\overline{k})}$ and unipotent group ${U}$ ; this is easiest to see by multiplying ${\ell}$ on the left so that it contains the identity, and then placing another element of the line in Jordan normal form. In that case, we have

$\displaystyle \hbox{tr}(hu) = \hbox{tr}(ahu) = \hbox{tr}(bhu) = \hbox{tr}(g)$

for all ${u \in U}$ . This forces ${h, ah, bh}$ to all lie in the Borel subgroup ${B}$ associated to ${U}$ (this is easiest to see by first conjugating ${U}$ into the standard unipotent group ${U(\overline{k})}$ ). In particular, ${a, b}$ both lie in ${B}$ . Furthermore, if we write ${\hbox{tr}(g) = t + t^{-1}}$ , then the diagonal entries of ${h,ah,bh}$ are ${t,t^{-1}}$ or ${t^{-1},t}$ , and so the diagonal entries of ${a,b}$ are either ${1,1}$ or ${t^{-2},t^2}$ or ${t^2,t^{-2}}$ . In particular, ${U}$ is the stabiliser of one of the eigenvectors of ${a}$ – so for fixed ${a}$ , there are at most two choices for ${U}$ (recall that ${a}$ was regular). Furthermore, for fixed ${a}$ and ${U}$ , ${b}$ is constrained to lie in at most three cosets of ${U}$ . As such, there are only ${O(|A|^{1/3})}$ choices of ${b}$ here for each ${a}$ , giving another contribution of ${O(|A|^{4/3}|S|)}$ , and the claim follows. $\Box$

Exercise 9 Let ${A}$ be a finite subgroup of ${SL_2(\overline{k})}$ , such that ${|A \cap B| = o(|A|)}$ for all Borel subgroups ${B}$ . Show that at most ${O(|A|^{2/3})}$ of the elements of ${A}$ are unipotent.

We can use the upper bound on conjugacy classes to obtain a lower bound on tori:

Proposition 13 (Large tori) Let ${A}$ be a finite subgroup of ${SL_2(\overline{k})}$ . Then one of the following statements hold:

(Large torus) For any regular semisimple ${g \in A}$ , one has ${|A \cap T| \gg |A|^{1/3}}$ , where ${T}$ is the unique maximal torus containing ${g}$ .

(Trapping) There is a Borel subgroup ${B}$ such that ${|A \cap B| \gg |A|}$ .

Proof: We can of course assume that the trapping case does not occur. We consider the map ${\phi: a\mapsto aga^{-1}}$ from ${A}$ to ${A \cap Conj(g)}$ . By Proposition 12, the range of ${\phi}$ has cardinality ${O(|A|^{2/3})}$ , so by the pigeonhole principle, there is a preimage of ${A \cap Conj(g)}$ of cardinality ${\gg |A|^{1/3}}$ . But all preimages are conjugate to each other, so the preimage of ${g}$ has cardinality ${\gg |A|^{1/3}}$ . But this preimage is the intersection of ${A}$ with the centraliser of ${g}$ , which two cosets of ${T}$ , and so ${|A \cap T| \gg |A|^{1/3}}$ as required. $\Box$

Exercise 10 Establish a variant of Proposition 13 in which ${g}$ is regular unipotent instead of regular semisimple, and ${T}$ is replaced with the unique unipotent group containing ${g}$ .

This gives a second (and particularly useful) dichotomy: assuming ${A}$ is not trapped by a Borel subgroup, for a maximal torus ${T}$ , ${|A\cap T|}$ is either at most two, or is comparable to ${|A|^{1/3}}$ .

To exploit this, we use the following counting argument of Larsen and Pink (which is also reminiscent of an old argument of Jordan, used to prove his theorem mentioned previously), followed by some ad hoc arguments specific to ${SL_2}$ . We continue to assume that ${A}$ is not trapped by a Borel subgroup. Let ${Z := A \cap\{+1,-1\}}$ denote the central elements of ${A}$ , thus ${|Z|}$ is either ${1}$ or ${2}$ . Observe that every element in ${A \backslash Z}$ is either regular projectively unipotent or regular semisimple; in the latter case, the element lies in a unique maximal torus, which also contains ${Z}$ . We conclude that

$\displaystyle |A|-|Z| = u + \sum_T (|A \cap T| - |Z|)$

where ${T}$ ranges over all the maximal tori that intersect ${A}$ , and ${u}$ is the number of regular projective unipotents in ${A}$ .

If we conjugate a maximal torus ${T}$ by an element of ${A}$ , we get another maximal torus, or the same maximal torus if the element used to conjugate ${T}$ in was in the normaliser ${N_A(T) := \{ a \in A: a T=Ta\}}$ of ${T}$ . Thus, by the orbit-stabilizer theorem, there are exactly ${|A|/|N_A(T)|}$ tori conjugate to ${T}$ in ${A}$ . We thus see that

$\displaystyle |A|-|Z| = u + \sum_{T \in {\mathcal T}} \frac{|A|}{|N_A(T)|} (|A \cap T| - |Z|)$

where ${{\mathcal T}}$ is a collection of representatives of conjugacy classes of maximal tori intersecting ${A}$ in a regular semisimple element. We rearrange this as

$\displaystyle 1 = \frac{u+|Z|}{|A|} + \sum_{T \in {\mathcal T}} \frac{1}{[N_A(T):A \cap T]} (1 - \frac{|Z|}{|A \cap T|}).$

Note that if ${T}$ is a maximal torus, the normaliser of ${T}$ in ${SL_2(\overline{k})}$ has index ${2}$ . As such, ${A\cap T}$ has index at most two in ${N_A(T)}$ , and so ${\frac{1}{[N_A(T):A \cap T]}}$ is either equal to ${1}$ or ${1/2}$ for each ${T}$ . From the preceding bounds on tori and unipotent elements, we also have ${\frac{|Z|}{|A \cap T|} \sim |A|^{-1/3}}$ and ${\frac{u+|Z|}{|A|} = O( |A|^{-1/3} )}$ . As we are assuming ${|A|}$ to be large, the above equation is only consistent when ${{\mathcal T}}$ has cardinality ${1}$ or ${2}$ , and ${\frac{u+|Z|}{|A|}}$ is comparable to ${|A|^{-1/3}}$ , or equivalently that ${u}$ is comparable to ${|A|^{2/3}}$ . Thus, ${A}$ has plenty of regular projective unipotents (matching the upper bound from Exercise 9); in particular, there is at least one regular unipotent.

Applying a conjugation, we may assume that ${A}$ contains ${e := \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}}$ , thus

$\displaystyle A \cap U(\overline{k}) = \{\begin{pmatrix} 1 & t \\ 0 & 1 \end{pmatrix}: t \in E\}$

for some additive group ${E \subset \overline{k}}$ containing ${1}$ . By Exercise 7, ${|E| \ll |A|^{1/3}}$ ; by Exercise 10, we have ${|E|\gg |A|^{1/3}}$ also.

The map ${a \mapsto a(A \cap U(\overline{k}))a^{-1}}$ maps ${A}$ to unipotent groups that intersect ${A}$ in ${\sim |A|^{1/3}}$ regular unipotents. As there are ${\sim |A|^{2/3}}$ regular unipotent elements in ${A}$ , we see that there are only ${O(|A|^{1/3})}$ such unipotent groups available. From the pigeonhole principle and conjugation, we conclude that the preimage of ${U(\overline{k})}$ in this map has cardinality ${\gg |A|^{2/3}}$ . But this preimage is simply ${A \cap B(\overline{k})}$ . In particular, the quotient ${(A\cap B(\overline{k}))/(A \cap U(\overline{k}))}$ has cardinality ${\gg |A|^{1/3}}$ . Observe that each element of this quotient acts on ${A \cap U(\overline{k})}$ by conjugation, and the corresponding action on ${E}$ is multiplicative (by the square of a diagonal entry of an element in the quotient). As such, if we set

$\displaystyle F := \{ \xi \in \overline{k}: \xi E \subset E\}$

to be the “multiplicative symmetry set” of ${E}$ , then we have ${|F|\gg |A|^{1/3}}$ . As ${E}$ is a finite additive group, ${F}$ is a field of size at most ${|E| \ll|A|^{1/3}}$ , thus ${F}$ is a finite field of cardinality ${|F| \sim |A|^{1/3}}$ . Also, ${E}$ is a vector space over ${F}$ ; as ${E}$ contains ${1}$ and has cardinality ${O(|A|^{1/3})}$ , we see that ${E=F}$ . Thus we have

$\displaystyle A \cap U(\overline{k}) = \begin{pmatrix} 1 & F \\ 0 & 1 \end{pmatrix}. \ \ \ \ \ (2)$

Also, as ${(A\cap B(\overline{k}))/(A \cap U(\overline{k}))}$ has to stabilise ${F}$ , we see that all elements of ${A \cap B(\overline{k})}$ have diagonal elements whose square lies in ${F}$ . Combining this with (2), we see that ${A \cap B(\overline{k})}$ takes the form

$\displaystyle A \cap B(\overline{k}) = \{ \begin{pmatrix} t & f(t) + x \\ 0 & t^{-1} \end{pmatrix}: t \in H, x\in F\} \ \ \ \ \ (3)$

for some multiplicative group ${H}$ of elements whose square lies in ${F^\times}$ (in particular, ${H \cap F^\times}$ has index at most ${2}$ in ${H}$ ), and some function ${f: H \rightarrow \overline{k}}$ ; since ${A \cap B(\overline{k})}$ has cardinality ${\gg |A|^{2/3} \sim |F|^2}$ , ${H}$ must have cardinality ${\sim |F|}$ . By taking the commutators of two matrices in (3), we see that

$\displaystyle f(t) (s-s^{-1}) - f(s) (t-t^{-1}) \in F \ \ \ \ \ (4)$

for all ${s,t \in H}$ .

If we select ${t_0 \in H \cap F^\times}$ such that ${t_0-t_0^{-1}}$ is non-zero, then by conjugating ${A}$ by a suitable element of ${U(\overline{k})}$ (which does not affect any of the previous control established on ${A}$ ) we may normalise ${f(t_0)}$ to be zero. From (4) this makes ${f(t) \in F}$ for all ${t \in H}$ . In particular, ${A \cap B(\overline{k})}$ is almost completely contained in ${B(F)}$ :

$\displaystyle |A \cap B(\overline{k}) \cap B(F)| \geq |A \cap B(\overline{k})|/2. \ \ \ \ \ (5)$

Now for any ${g \in A}$ , the subgroups ${A \cap B(\overline{k})}$ and ${g^{-1} (A \cap B(\overline{k})) g}$ of ${A}$ have index ${O(|A|^{1/3})}$ , so their intersection must have cardinality ${\gg |A|^{1/3} \gg |F|}$ , thus

$\displaystyle |A \cap B(F) \cap g B(F) g^{-1}| \gg |F|.$

In particular, there must exist either a regular unipotent or a regular semisimple element ${h \in A}$ of ${B(F)}$ such that ${ghg^{-1}}$ also lies in ${B(F)}$ . If ${h}$ is regular semisimple in ${B(F)}$ , it has an eigenbasis in ${F^2}$ , and so ${g}$ must map such an eigenbasis to another eigenbasis, and thus lies in ${SL_2(F)}$ . If instead ${h}$ is regular unipotent, it has the line ${\{0\} \times \overline{k}}$ as the unique (geometric) eigenspace; ${g}$ must preserve this eigenspace and thus lies in ${B(\overline{k})}$ , and thus in ${B(F)}$ and therefore in ${SL_2(F)}$ by (5). Combining the cases, we conclude that ${A \subset SL_2(F)}$ . We may therefore summarise our discussion as follows:

Theorem 14 (Rough description of finite subgroups of ${SL_2}$ ) Let ${A}$ be a finite subgroup of ${SL_2(\overline{k})}$ . Then one of the following statements hold:

(Arithmetic subgroup) There is a finite subfield ${F}$ of ${\overline{k}}$ with ${|F| \sim |A|^{1/3}}$ such that ${A}$ is contained in a conjugate of ${SL_2(F)}$ (and is thus a subgroup of that conjugate of index ${O(1)}$ ).

(Trapping) There is a Borel subgroup ${B}$ such that ${|A \cap B| \gg |A|}$ .

In principle, the trapping case can be analysed further (using manipulations similar to those used to reach (5)) but we will not pursue this here. We remark that while these computations were somewhat lengthy (and less elementary and precise than the more classical results of Dickson), they can extend to more complicated algebraic groups, such as ${SL_d(\overline{k})}$ , or more generally to any algebraic group of bounded rank; see this paper of Larsen and Pink for details. In particular, Larsen and Pink were able to use these methods to establish an important subcase of the famous classification of finite simple groups, namely by verifying this classification for sufficiently large subgroups of a linear group of bounded rank over a field of arbitrary characteristic. It is conceivable that these methods may be extended in the future to give an alternate proof of the full classification (for sufficiently large groups, at least).

— 3. The product theorem in ${SL_2(k)}$ —

In this section we prove the ${d=2}$ case of Theorem 1. This result was first established (for fields of prime order) by Helfgott and then in the general case by Dinai; we will present a variant of Helfgott’s original argument which was developed by Breuillard, Green, and Tao and independently by Pyber and Szabo. It is convenient to rephrase Helfgott’s theorem as follows:

Theorem 15 (Product theorem in ${SL_2(k)}$ , alternate form) Let ${k}$ be a finite field, and let ${A}$ be a ${K}$ -approximate group in ${G := SL_2(k)}$ that generates ${G}$ for some ${K \geq 2}$ . Then one of the following holds:

(Close to trivial) One has ${|A| \ll K^{O(1)}}$ .

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

Exercise 11 Show that Theorem 1 follows from Theorem 15. (Hint: if ${|A^3| \leq |A|^{1+\epsilon}}$ , use the multiplicative form of the Rusza triangle and covering lemmas to show that ${(A \cup \{1\} \cup A^{-1})^2}$ is a ${O(|A|^{O(\epsilon)})}$ -approximate group.)

The problem now concerns the behaviour of finite approximate subgroups ${A}$ of ${SL_2(k)}$ . The first step will be to establish analogues of the Larsen-Pink non-concentration inequalities of the preceding section, but for approximate subgroups rather than genuine subgroups. (The observation that these inequalities could be usefully extended to the approximate group setting is due to Hrushovski, although for the specific case of ${SL_2(k)}$ , the most important of these inequalities for the purposes of proving Theorem 15 were first established by Helfgott.) We begin by eliminating concentration in linear subgroups.

Lemma 16 (Escape from subspaces) Let ${A}$ , ${K}$ be as in Theorem 15, and let ${C>0}$ . Then one of the following holds:

(Close to trivial) One has ${|A| \ll_C K^{O_C(1)}}$ .

(Escape) For any ${d=0,1,2,3}$ and any ${d}$ -dimensional subspace ${V}$ of ${\overline{k}^4}$ , such that ${V\cap SL_2(\overline{k})}$ is a subgroup of ${SL_2(\overline{k})}$ , one has ${|A^2 \cap V| \leq K^{-C} |A|}$ .

In practice, we will only apply the escape conclusion for Borel subgroups of ${SL_2(\overline{k})}$ , which are intersections of ${SL_2(\overline{k})}$ with three-dimensional subspaces; however, we need to work with the more general escape construction in the proof of the lemma, for inductive purposes. The claim can in fact be established for any ${d}$ -dimensional subspace ${V}$ , or more generally for bounded complexity ${d}$ -dimensional algebraic varieties; this will be discussed in the next section.

Proof: We induct on ${d}$ . For ${d=0}$ , the claim is trivial, since ${|A^2 \cap V|=1}$ in that case. Now suppose that ${d=1,2,3}$ , and the claim has already been proven for smaller values of ${d}$ .

Let ${V}$ be a ${d}$ -dimensional subspace of ${SL_2(\overline{k})}$ with ${V \cap SL_2(\overline{k})}$ a group, and suppose for contradiction that ${|A^2 \cap V|>K^{-C}|A|}$ . As ${A^2}$ can be covered by ${K}$ copies of ${A}$ , we can find ${a\in A}$ such that

$\displaystyle |aA\cap V| > K^{-C-1} |A|. \ \ \ \ \ (6)$

Suppose that there exists an element ${b}$ of ${A}$ such that ${bVb^{-1} \neq V}$ , so that ${bVb^{-1} \cap V}$ has dimension strictly less than ${V}$ . From (6) we have

$\displaystyle |A^4 \cap bVb^{-1}| \geq |baAb^{-1} \cap bVb^{-1}| > K^{-C-1}|A|.$

Since ${A^4}$ can be covered by ${K^3}$ right translates of ${A}$ , we can find ${g \in A^5}$ such that

$\displaystyle |gA \cap bVb^{-1}| > K^{-C-4}|A|.$

Let ${A_1 :=aA \cap V}$ and ${A_2 := gA \cap bVb^{-1}}$ . Then ${A_1 A_2^{-1}}$ is contained in ${A^7}$ , and so ${1_{A_1} * 1_{A_2^{-1}}}$ is supported on a set of cardinality at most ${K^6 |A|}$ . Since

$\displaystyle \| 1_{A_1} * 1_{A_2^{-1}} \|_{\ell^1} = |A_1||A_2| \geq K^{-2C-5} |A|^2$

we thus see from the pigeonhole principle that

$\displaystyle |1_{A_1} * 1_{A_2^{-1}}(x)| \geq K^{-2C-11} |A|.$

The left-hand side is ${|A_1 \cap x A_2|}$ , and thus

$\displaystyle |(A_1\cap x A_2)^{-1} \cap (A_1 \cap x A_2)| \geq K^{-2C-11}|A|.$

The set in the left-hand side is contained in both ${A^2}$ and in ${V\cap (bVb^{-1})}$ (here we use the group nature of ${V \cap SL_2(\overline{k})}$ ), and so

$\displaystyle |A^2 \cap V\cap (bVb^{-1})| \geq K^{-2C-11} |A|.$

Applying the induction hypothesis, we conclude that ${|A| \leq K^{O_C(1)}}$ , and the claim follows.

The only remaining case is when ${bVb^{-1}=V}$ for all ${b \in A}$ . As ${A}$ generates ${SL_2(k)}$ , this implies that ${V}$ is normalised by ${SL_2(k)}$ . But this is impossible if ${V}$ has dimension ${1,2,3}$ ; see Exercise 12 below. $\Box$

Exercise 12 (Almost simplicity of ${SL_2(k)}$ ) Let ${V}$ be a subspace of ${\overline{k}^4}$ of dimension ${1}$ , ${2}$ , or ${3}$ . Show that the group ${\{ g \in SL_2(k): gVg^{-1} = V\}}$ does not contain all of ${SL_2(k)}$ .

Now we can obtain an approximate version of Proposition 10:

Proposition 17 (Larsen-Pink inequality, special case) Let ${A}$ , ${K}$ be as in Theorem 15. Then for any maximal torus ${T}$ , one has ${|A^2 \cap T| \ll K^{O(1)} |A|^{1/3}}$ .

In the context of ${SL_2}$ , this bound on torus concentration was first established by Helfgott (and extended to ${SL_d}$ in a subsequent paper of Helfgott).

Proof: We may assume that ${|A| \geq K^C}$ for any given constant ${C}$ , as the claim is trivial otherwise. Similarly, by Lemma 16, we may assume that ${|A^2 \cap B|\leq K^{-C}|B|}$ for all Borel subgroups ${B}$ .

We need to show that ${|A^2 \cap T| \ll |A|^{1/3}}$ for any maximal torus ${T}$ . By conjugation we may take ${T}$ to be the standard maximal torus ${T = T(\overline{k})}$ . (This may make ${A}$ generate a conjugate of ${SL_2(k)}$ , rather than ${SL_2(k)}$ itself, but this will not impact our argument). Set ${A' := A^2 \cap T(\overline{k})}$ , then

$\displaystyle A' := \{ \begin{pmatrix} t & 0 \\ 0 & t^{-1} \end{pmatrix}: t\in H \}$

for some finite subset ${H}$ of ${\overline{k}^\times}$ . We may assume that ${|H| \geq K^C}$ , as the claim is trivial otherwise. Our task is to show that ${|H|^3 \ll K^{O(1)} |A|}$ .

As in the proof of Proposition 17, we may find an element ${g = \begin{pmatrix} a & b \\ c & d \end{pmatrix}}$ of ${A^2}$ with ${a,b,c,d}$ all non-zero. Since ${A' g A' g A' \subset A^{10}}$ , thus

for all ${t_1,t_2,t_3 \in H}$ . Arguing as in Proposition 17, we have

$\displaystyle |H|^3\ll |A^{10}|,$

and the claim follows. $\Box$

Exercise 13 Show that if the non-concentration conclusion in Proposition 17 holds, then for every maximal torus ${T}$ and every ${m \geq 1}$ , one has ${|A^m \cap T| \ll_m K^{O_m(1)} |A|^{1/3}}$ .

We can now establish variants of the other Larsen-Pink inequalities from the preceding section:

Exercise 14 Establish a variant of Proposition 17 in which the maximal tori are replaced by unipotent groups.

Exercise 15 (Large conjugacy classes) Let ${A}$ , ${K}$ be as in Theorem 15. Show that for any regular semisimple or regular projectively unipotent ${g \in A}$ , one has ${|A^3 \cap Conj(g)| \gg K^{-O(1)} |A|^{2/3}}$ .

Exercise 16 (Larsen-Pink inequality, another special case) Let ${A}$ , ${K}$ be as in Theorem 15. Show that for any regular semisimple ${g \in SL_2(\overline{k})}$ and any ${m \geq 1}$ , one has ${|A^m \cap Conj(g)| \ll_m K^{O_m(1)} |A|^{2/3}}$ .

Exercise 17 (Unipotent bound) Let ${A}$ , ${K}$ be as in Theorem 15. Show that ${O(K^{O(1)} |A|^{2/3})}$ of the elements of ${A}$ are unipotent.

Exercise 18 (Large tori) Let ${A}$ , ${K}$ be as in Theorem 15. Show that for any regular semisimple ${g \in A^2}$ , one has ${|A^4 \cap T| \gg K^{-O(1)} |A|^{1/3}}$ , where ${T}$ is the unique maximal torus containing ${g}$ . In fact one has ${|A^2 \cap T| \gg K^{-O(1)} |A|^{1/3}}$ . (For the latter claim, cover ${A^4}$ by left translates of ${A}$ .)

We remark that versions of most the results in the above exercises were first obtained in the context of ${SL_2}$ by Helfgott (and extended to ${SL_d}$ in a subsequent paper of Helfgott). However, the lower bound in Exercise 18 was only obtained in those papers for some maximal tori meeting ${A^2}$ non-trivially, rather than for all such tori, leading to some additional technical complications in Helfgott’s proof of Theorem 15.

We now have a dichotomy: given a maximal torus ${T}$ , either ${A^2\cap T}$ has no regular semisimple elements (and thus contains only central elements), or else has cardinality ${\gg K^{-O(1)} |A|^{1/3}}$ . We exploit this dichotomy as follows. Call a maximal torus ${T}$ involved if ${A^2 \cap T}$ contains a regular semisimple element.

Lemma 18 (Key lemma) Let ${A}$ , ${K}$ be as in Theorem 15. Then one of the following statements hold:

(Invariance) If ${T}$ is an involved torus and ${a \in A}$ , then ${aTa^{-1}}$ is an involved torus.

(Close to trivial) One has ${|A| \ll K^{O(1)}}$ .

Proof: Let ${T}$ be an involved torus, then by the preceding exercise we have ${|A^2 \cap T|\gg K^{-O(1)}|A|^{1/3}}$ , and thus ${|A^4 \cap aTa^{-1}| \gg K^{-O(1)}|A|^{1/3}}$ . Thus, one has ${|gA \cap aTa^{-1}| \gg K^{-O(1)} |A|^{1/3}}$ for some ${g \in G}$ , which implies that ${|A^2 \cap aTa^{-1}| \gg K^{-O(1)} |A|^{1/3}}$ . In particular, if ${A}$ is not close to trivial, ${A^2 \cap aTa^{-1}}$ contains a regular semisimple element and so ${aTa^{-1}}$ is involved, as desired. $\Box$

We can now finish the proof of Theorem 15. Suppose ${A}$ is not close to trivial. As there are at most ${O(K^{O(1)}|A|^{2/3})}$ unipotent elements and ${O(1)}$ central elements in ${A}$ , ${A}$ at least one regular semisimple element, and so there is at least one involved torus. By the above lemma, and the fact that ${A}$ generates ${G}$ , we see that the set of involved tori is invariant under conjugation by ${G}$ . As ${G}$ has cardinality ${\gg |k|^3}$ , and its intersection with the stabiliser of a single torus has cardinality ${O(|k|)}$ , we conclude that there are ${\gg |k|^2 \ll |G|^{2/3}}$ involved tori. By Exercise 18, each of these tori contains ${\gg K^{-O(1)} |A|^{1/3}}$ regular semisimple elements of ${A^2}$ . Since each regular semisimple element belongs to a unique maximal torus, we conclude that

$\displaystyle |A^2| \gg |G|^{2/3} K^{-O(1)} |A|^{1/3};$

as ${|A^2| \leq K|A|}$ , we conclude that ${|A|\gg K^{-O(1)} |G|}$ , as claimed.

Exercise 19 Let ${A}$ be a finite ${K}$ -approximate subgroup of ${SL_2(\overline{k})}$ for some algebraically closed field ${\overline{k}}$ . Show that one of the following statements hold:

(Close to group) ${A}$ generates a finite subgroup ${G}$ of ${SL_2(\overline{k})}$ with ${|G| \ll K^{O(1)} |A|}$ .

(Concentrated in Borel) There is a Borel subgroup ${B}$ of ${SL_2(\overline{k})}$ with ${|A \cap B| \gg K^{-O(1)} |B|}$ .

(Hint: this does not follow directly from Theorem 15, but can be established by a modification of the proof of that theorem.)

Note that the above exercise can be combined with Theorem 14 to give a more detailed description of ${A}$ . The Borel group ${B}$ is solvable, and by using tools from additive combinatorics, such as Freiman’s theorem in solvable groups (or the Helfgott-Lindenstrauss conjecture, discussed in the previous quarter’s notes), one can give even more precise descriptions of ${A}$ (at the cost of losing polynomial dependence of the bounds on ${K}$ ), but we will not discuss these topics here.

Exercise 20 Use Exercise 19 to give an alternate proof of Theorem 5. (Hint: there are a number of ways to embed the sum-product problem in a field ${k}$ into a product problem in ${SL_2(k)}$ (or ${SL_2(\overline{k})}$ ). For instance, one consider the tripling properties of sets of the form ${\{ \begin{pmatrix} a & b \\ c & d \end{pmatrix}: a,b,c,d \in A \}}$ in terms of sets such as ${A^2+A^2}$ or ${A^3+A^3+A^3+A^3}$ , and then project this set onto ${SL_2(k)}$ (or ${PSL_2(k)}$ ), and combine this with the Katz-Tao lemma to obtain Theorem 5. More details of this connection can be found in Section 8 of this paper.) This is of course a much more complicated and inefficient way to establish the sum-product theorem, but it does illustrate the link between the two results (beyond the fact that both proofs exploit a dichotomy). Note alsot that the original proof of the product theorem in ${SL_2(F_p)}$ by Helfgott actually used the sum-product theorem in ${F_p}$ as a key tool.

— 4. The product theorem in ${SL_d(k)}$ —

We now discuss the extension of the ${SL_2(k)}$ product theory to the more general groups ${SL_d(k)}$ . Actually, the arguments here will be valid in any almost simple connected algebraic group of bounded rank, but for sake of concreteness we will work with ${SL_d(k)}$ . (This also has the (very) minor advantage that ${SL_d}$ is an affine variety rather than a projective one, so we can work entirely in affine spaces such as ${{\bf A}^{d^2}(\overline{k}) :=\overline{k}^{d^2}}$ ; related to this, the only regular maps we need to consider will be polynomial in nature.) There is also some recent work on product theorems in other algebraic groups than the almost simple ones; see for instance the papers of Pyber-Szabo, Gill-Helfgott, and Breuillard-Green-Tao for some examples of this. It is conceivable that a satisfactory understanding of approximate subgroups of arbitrary algebraic groups of bounded dimension will be available in the near future.

The treatment of the ${d=2}$ case relied on a number of ad hoc computations which were only valid in ${SL_2}$ , and also on the pleasant fact that the only non-regular elements of ${SL_2}$ were the central elements ${\pm 1}$ , which is certainly false for higher values of ${d}$ . In this paper, Helfgott was able to push his original ${d=2}$ arguments to the ${d=3}$ case, but again the arguments were somewhat ad hoc in nature and did not seem to extend to the general setting. However, the arguments based on the Larsen-Pink concentration estimates have proven to be quite general, and in particular can handle the situation of ${SL_d(k)}$ . The one catch is that instead of working with very concrete and explicit subsets of ${SL_2}$ , such as Borel subgroups or other intersections ${SL_2 \cap V}$ with linear spaces ${V}$ , one has to work with more general algebraic subvarieties of ${SL_d}$ . As such, a certain amount of basic algebraic geometry becomes necessary. Also, because we are seeking results with quantitative bounds, we will need to keep some track of the “complexity” of the varieties that one encounters in the course of the argument.

We now very quickly review some algebraic geometry notions, though for reasons of space we will not attempt to develop the full theory of algebraic geometry here, referring instead to standard texts such as Harris, Mumford, or Griffiths-Harris. As usual, algebraic geometry is cleanest when working over an algebraically closed field, so we will work primarily over ${\overline{k}}$ .

Definition 19 (Variety) Let ${M \geq d \geq 0}$ be integers, and let ${\overline{k}}$ be an algebraically closed field. We write ${{\bf A}^d(\overline{k})}$ for the affine space ${\overline{k}^d}$ .

An (affine) variety ${V = V(\overline{k}) \subset {\bf A}^d(\overline{k})}$ of complexity at most ${M}$ is a set of the form
$\displaystyle V = \{ x \in \overline{k}^d: P_1(x) =\ldots = P_m(x) = 0 \},$

where ${0 \leq m \leq M}$ and ${P_1,\ldots,P_m: {\bf A}^d(\overline{k}) \rightarrow\overline{k}}$ are polynomials of degree at most ${M}$ . (Thus the complexity parameter ${M}$ controls the dimension, degree, and number of polynomials needed to cut out the variety. Note that we do not assume our varieties to be irreducible, and as such what we call a variety corresponds to what is sometimes known as an algebraic set in the literature.) Note that the union or intersection of two varieties of complexity at most ${M}$ , is another variety of complexity at most ${O_M(1)}$ .

A variety is irreducible if it cannot be expressed as the union of two proper (i.e. strict) subvarieties.

Thus, for instance, ${SL_d(\overline{k})}$ is a variety of complexity ${O_d(1)}$ in ${{\bf A}^{d^2}(\overline{k})}$ (after identifying this latter affine space with the space of ${d \times d}$ matrices over ${\overline{k}}$ ).

It is known that any variety can be expressed as the union of a finite number of irreducible components, and this decomposition is unique if we require that no component is contained in any other. Furthermore, to each irreducible variety ${V}$ one can assign a dimension ${\hbox{dim}(V)}$ , defined as the maximal integer ${D}$ for which there exists a chain

$\displaystyle \emptyset \neq V_0 \subsetneq \ldots \subsetneq V_D = V$

of irreducible varieties; this will be an integer between ${0}$ and ${D}$ . For instance, it can be shown that ${{\bf A}^d(\overline{k})}$ has dimension ${d}$ (as expected). We define the dimension of a non-irreducible variety ${V}$ to be the least integer ${D}$ such that ${V}$ can be covered by finitely many irreducible varieties of dimension ${D}$ . If a (non-empty) variety ${V}$ can be cut out from an irreducible variety ${W}$ by setting ${m}$ polynomials to zero, then one has ${\hbox{dim}(W) - m \leq \hbox{dim}(V) \leq \hbox{dim}(W)}$ . Since ${SL_d(\overline{k})}$ can be cut out from ${{\bf A}^{d^2}(\overline{k})}$ by a single polynomial, and is not equal to all of ${{\bf A}^{d^2}(\overline{k})}$ , we conclude in particular that ${SL_d(\overline{k})}$ has dimension ${d^2-1}$ .

One can show that the image of a ${D}$ -dimensional variety by a polynomial map ${P: {\bf A}^{d_1}\rightarrow {\bf A}^{d_2}}$ is contained in a variety of dimension at most ${D}$ . One can thus produce upper bounds on the dimension of varieties, by covering them by polynomial images of varieties already known to be bounded by the same dimension.

An algebraic subgroup of ${SL_d(\overline{k})}$ is a subvariety of ${SL_d(\overline{k})}$ which is also a subgroup of ${SL_d(\overline{k})}$ . For instance, the standard maximal torus ${T(\overline{k})}$ , consisting of all the diagonal elements of ${SL_d(\overline{k})}$ , is an algebraic subgroup; more generally, any maximal torus, by which we mean a conjugate of the standard maximal torus, is an algebraic subgroup.

Exercise 21 Show that every maximal torus has dimension ${d-1}$ and complexity ${O_d(1)}$ .

Dual to the maximal tori are the conjugacy classes ${Conj(g) := \{ hgh^{-1}: h \in SL_d(\overline{k})\}}$ of regular semisimple elements. We call a element ${g}$ of ${SL_d(\overline{k})}$ regular semisimple if it has ${d}$ distinct eigenvalues, and is thus diagonalisable. Observe that each regular semisimple element lies in precisely one maximal torus.

Exercise 22 Show that every conjugacy class of a regular semisimple element has dimension ${d^2-d}$ and complexity ${O_d(1)}$ .

If ${F}$ is a finite subfield of ${\overline{k}}$ , then ${SL_d(F)}$ is a finite subgroup of ${SL_d(\overline{k})}$ , and is thus technically a ${0}$ -dimensional algebraic subgroup of ${SL_d(\overline{k})}$ . However, the complexity of this algebraic group is huge (comparable to the cardinality of ${SL_d(F)}$ ). It turns out that ${SL_d(F)}$ is “effectively Zariski-dense” in the sense that it cannot be captured in a low complexity algebraic variety:

Lemma 20 (Schwartz-Zippel lemma for ${SL_d(F)}$ ) Let ${V}$ be a proper subvariety of ${SL_d(\overline{k})}$ of complexity at most ${M}$ . Let ${F}$ be a finite subfield of ${\overline{k}}$ . Then

$\displaystyle |SL_d(F) \cap V| \ll_{M,d} |F|^{d^2-2}.$

Proof: ${SL_d(\overline{k})}$ is the hypersurface in ${{\bf A}^{d^2}(\overline{k})}$ cut out by the determinant polynomial. As ${V}$ is a proper subvariety, we can find a polynomial ${P: \overline{k}^{d^2} \rightarrow \overline{k}}$ which is not a multiple of the determinant polynomial, but which vanishes on ${V}$ ; by the complexity hypothesis we may take ${P}$ to have degree ${O_{M,d}(1)}$ . Our task is then to show that

$\displaystyle |\{ x \in SL_d(F): P(x)=0 \}| \ll_{M,d} |F|^{d^2-2}.$

Let us write the ${d^2}$ coordinates of ${{\bf A}^{d^2}(\overline{k})}$ arbitrarily as ${x_1,\ldots,x_{d^2}}$ . In a given element of ${SL_d(F)}$ , not all of the ${x_i}$ can be zero; thus by symmetry and relabeling if necessary it suffices to show that

$\displaystyle |\{ x \in SL_d(F): P(x)=0; x_{d^2} \neq 0 \}| \ll_{M,d} |F|^{d^2-2}. \ \ \ \ \ (7)$

But then one can express ${x_{d^2}}$ as a rational function of the other ${d^2-1}$ coordinates, and the left-hand side of (7) is contained in a set of the form ${\{ x \in F^{d^2-1}: Q(x)=0\}}$ for some polynomial ${Q}$ of degree ${O_{M,d}(1)}$ that is not identically zero. The claim then follows from the Schwartz-Zippel lemma, which we give as an exercise below. $\Box$

Exercise 23 (Schwartz-Zippel lemma) Let ${F}$ be a finite field, and let ${Q:F^d \rightarrow F}$ be a polynomial of degree ${D}$ that is not identically zero. Show that

$\displaystyle |\{ x \in F^d: Q(x) = 0 \}| \ll_d D |F|^{d-1}.$

For an additional challenge, obtain the sharper bound

$\displaystyle |\{ x \in F^d: Q(x) = 0 \}| \leq D |F|^{d-1}.$

We contrast this with the size of ${SL_d(F)}$ itself:

Exercise 24 Let ${F}$ be a finite field. Show that ${|F|^{d^2-1} \ll_d |SL_d(F)|\ll_d |F|^{d^2-1}}$ .

The key non-concentration inequality we will need is the following.

Proposition 21 (Larsen-Pink inequality) Let ${A}$ be a ${K}$ -approximate subgroup of ${SL_d(\overline{k})}$ for some ${K \geq 2}$ , and let ${V}$ be a subvariety of ${SL_d(\overline{k})}$ of complexity at most ${M}$ . Let ${m \geq 1}$ . Then one of the following is true:

(Non-concentration) One has
$\displaystyle |A^m \cap V| \ll_{M,d,m} K^{O_{M,d,m}(1)} |A|^{dim(V)/dim(SL_d)}. \ \ \ \ \ (8)$

(Trapping) ${A}$ is contained in a proper algebraic subgroup ${H}$ of ${SL_d(\overline{k})}$ of complexity ${O_{M,d,m}(1)}$ .

This inequality subsumes results such as Proposition 17, Exercise 14, and Exercise 16. Note from Lemma 20 (and Exercise 24) that the trapping option of the above proposition cannot occur if ${A}$ generates ${SL_d(F)}$ and ${|F|}$ is sufficiently large depending on ${M, d, m}$ , while the non-concentration claim is trivial when ${|F| = O_{M,d,m}(1)}$ ; thus in this case we have (9) unconditionally.

The proof of Proposition 21 is somewhat complicated and is deferred to the next section. We record some particular consequences of this inequality.

Exercise 25 (Consequences of the non-concentration inequality) Let ${A}$ be a ${K}$ -approximate subgroup of ${SL_d(\overline{k})}$ for some ${K \geq 2}$ , which generates ${SL_d(F)}$ for some finite field ${F}$ .

(i) If ${T}$ is a maximal torus (and thus of dimension ${d-1}$ ), show that ${|A^{10} \cap T| \ll_d K^{O_d(1)} |A|^{\frac{1}{d+1}}}$ .

(ii) If ${T_0}$ denotes the elements of ${T}$ which are not regular semisimple, show that ${|A^{10} \cap T| \ll_d K^{O_d(1)} |A|^{\frac{d-2}{d^2-1}}}$ .

(iii) If ${g \in SL_d(\overline{k})}$ is regular semisimple, show that ${|A^{10} \cap Conj(g)|\ll_d K^{O_d(1)} |A|^{\frac{d}{d+1}}}$ .

(iv) Show that at most ${O_d(K^{O_d(1)} |A|^{\frac{d^2-2}{d^2-1}})}$ of the elements of ${A}$ are not regular semisimple.

(v) For any regular semisimple ${g \in A}$ , show that ${|A^3 \cap Conj(g)| \gg_d K^{-O_d(1)} |A|^{\frac{d}{d+1}}}$ .

(vi) For any regular semisimple ${g \in A}$ , show that ${|A^2 \cap T| \gg_d K^{-O_d(1)} |A|^{\frac{1}{d+1}}}$ .

Exercise 26 By repeating the arguments of the preceding section, establish Theorem 1 for general ${d}$ .

Remark 6 There is an analogue of Exercise 19, in which the role of the Borel subgroups is replaced by proper algebraic subgroups of bounded complexity; see Theorem 5.5 of the paper of Breuillard, Green, and Tao for a more precise statement.

— 5. Proof of the Larsen-Pink inequality (optional) —

We now prove Proposition 21. In order to escape the burden of having to keep track of the complexity of everything, we will use the tool of ultraproducts (which we will phrase in the language of nonstandard analysis). See this previous blog post for a discussion of ultraproducts and how they can be used to turn quantitative (or “hard”) analysis tasks into qualitative (or “soft”) analysis tasks. One can also use the machinery of schemes and inverse limits as a substitute for the ultraproduct formalism; this is the approach taken in the paper of Larsen and Pink. The paper of Breuillard, Green, and Tao has a slightly reduced reliance on ultraproducts, at the cost of more complexity bookkeeping, while the Pyber-Szabo paper avoids ultraproducts altogether but has perhaps the most bookkeeping of all the papers mentioned here (but, by the same token, is the only argument currently known which gives effective bounds). We will thus presume some familiarity both with ultraproducts (and nonstandard analysis) and with algebraic geometry in this section.

As in the previously mentioned blog post, we select a non-principal ultrafilter ${\alpha \in \beta {\bf N} \backslash {\bf N}}$ , and use it to construct ultraproducts and nonstandard objects. (To ensure the existence of such an object, we shall assume the axiom of choice, as we have already been doing implicitly throughout this course.) We also use the usual nonstandard asymptotic notation, thus for instance ${O(1)}$ denotes a nonstandard quantity bounded in magnitude by a standard number.

The quantitative Larsen-Pink inequality (Proposition 21) can then be deduced from the following nonstandard version, in which all references to complexity are now absent:

Proposition 22 (Larsen-Pink inequality) Let ${d \geq 2}$ be standard. Let ${\overline{k} = \prod_{n \rightarrow\alpha} \overline{k_n}}$ be a nonstandard algebraically complete field (i.e. an ultraproduct of standard algebraically complete fields). Let ${K = \lim_{n \rightarrow\alpha} K_n \geq 2}$ be a nonstandard natural number, and let ${A}$ be a nonstandard ${K}$ -approximate subgroup of ${SL_d(\overline{k})}$ (i.e. an ultraproduct ${A = \prod_{n \rightarrow \alpha} A_n}$ of standard ${K_n}$ -approximate subgroups of ${SL_d(\overline{k_n})}$ ), and let ${V}$ be a subvariety of ${SL_d(\overline{k})}$ . Then one of the following is true:

(Non-concentration) One has
$\displaystyle |A^m \cap V| \ll K^{O(1)} |A|^{dim(V)/dim(SL_d)} \ \ \ \ \ (9)$

for all standard ${m \geq 1}$ , where ${|A| := \lim_{n \rightarrow \alpha} |A_n|}$ is the nonstandard cardinality of ${A}$ .

(Trapping) ${A}$ is contained in a proper algebraic subgroup ${H}$ of ${SL_d(\overline{k})}$ .

Let us see why Proposition 22 implies Proposition 21. Suppose for contradiction that Proposition 21 failed. Carefully negating all the quantifiers (and using the axiom of choice), this means that there is a sequence ${\overline{k_n}}$ of standard algebraically closed fields, a sequence ${K_n \ge 2}$ of standard numbers, a sequence ${A_n}$ of ${K_n}$ -approximate subgroups of ${SL_d(\overline{k_n})}$ , and a standard ${M \geq 1}$ , a sequence ${V_n}$ of subvarieties of ${SL_d(\overline{k_n})}$ of complexity at most ${M}$ , and a standard ${m \geq 1}$ , such that for each ${n}$ , ${A_n}$ is not contained in a proper algebraicd subgroup of ${SL_d(\overline{k_n})}$ of complexity ${n}$ or less, and one has

$\displaystyle |A_n^m \cap V_n| \geq n K^n |A|^{dim(V_n)/dim(SL_d)}.$

Now one forms the ultralimit ${K :=\lim_{n \rightarrow\alpha} K_n}$ and the ultraproducts ${\overline{k} := \prod_{n \rightarrow \alpha} \overline{k_n}}$ , ${A := \prod_{n \rightarrow \alpha} A_n}$ , ${V := \prod_{n \rightarrow \alpha} V_n}$ . Then ${\overline{k}}$ is an algebraically closed field, ${A}$ is a nonstandard ${K}$ -approximate subgroup of ${SL_d(\overline{k})}$ , and ${V}$ is an algebraic subvariety of ${SL_d(\overline{k})}$ (here we use the uniform complexity bound). One can also show that ${\hbox{dim}(V) = \lim_{n \rightarrow \alpha}\hbox{dim}(V_n)}$ ; see Lemma 3 of this blog post. As such, we have

$\displaystyle |A^m \cap V| \not \ll K^{O(1)} |A|^{dim(V)/dim(SL_d)},$

so by Proposition 22, ${A}$ is contained in a proper algebraic subgroup ${H}$ of ${SL_d(\overline{k})}$ . By unpacking the coefficients of all the polynomials over ${\overline{k}}$ used to cut out ${H}$ , we see that ${H}$ is itself an ultraproduct ${H = \prod_{n \rightarrow \alpha} H_n}$ of proper algebraic subgroups of ${SL_d(\overline{k_n})}$ , of complexity bounded uniformly in ${n}$ . By Los’s theorem, one has ${A_n \subset H_n}$ for all ${n}$ sufficiently close to ${\alpha}$ , which gives a contradiction for ${n}$ large enough.

It remains to establish Proposition 22. By Los’s theorem, the ultraproduct ${\overline{k}}$ of algebraically closed fields is again algebraically closed, which allows us to use algebraic geometry in the nonstandard field ${\overline{k}}$ without difficulty.

Let ${\langle A\rangle}$ be the group generated by ${A}$ , and consider the Zariski closure ${\overline{\langle A \rangle}}$ of this group, that is to say the intersection of all the varieties containing ${\langle A \rangle}$ . This is again an algebraic variety (here we use the Noetherian property of varieties, that there does not exist any infinite descending chain of varieties), and is also a group (exercise!), and is thus an algebraic subgroup of ${SL_d(\overline{k})}$ . If this subgroup is proper then we have the trapping propertly, so we may assume that the closure is all of ${SL_d(\overline{k})}$ . In other words, ${\langle A\rangle}$ is Zariski dense in ${SL_d(\overline{k})}$ .

For any dimension ${D}$ between ${0}$ and ${\hbox{dim}(SL_d)}$ inclusive, and any standard real ${\sigma}$ , let us call ${\sigma}$ ${D}$ -admissible if one has the bound

$\displaystyle |A^m \cap V| \ll K^{O(1)} |A|^{\sigma}$

whenever ${m\geq 1}$ is standard and ${V}$ is a ${D}$ -dimensional subvariety of ${SL_d(\overline{k})}$ . Our task is to show that ${D/\hbox{dim}(SL_d)}$ is admissible for all ${0 \leq D \leq \hbox{dim}(SL_d)}$ . This claim is trivial at the two endpoints ${D=0}$ and ${D=\hbox{dim}(SL_d)}$ ; the difficulty is to somehow “interpolate” between these two endpoints. We need the following combinatorial observation.

Exercise 27 (Extreme dimensions) Suppose for sake of contradiction that ${D/\hbox{dim}(SL_d)}$ is inadmissible for some ${0 < D< \hbox{dim}(SL_d)}$ . Show that we can find dimensions

$\displaystyle 0 < D_1 \leq D_2 < \hbox{dim}(SL_d)$

and a real number ${\theta \geq 1/\hbox{dim}(SL_d)}$ such that

${D_1 \theta}$ is not ${D_1}$ -admissible;

${D_2 \theta}$ is not ${D_2}$ -admissible;

${D\theta}$ is ${D}$ -admissible whenever ${0 \leq D < D_1}$ or ${D_2 < D \leq \hbox{dim}(SL_d)}$ ;

${(D+1)\theta}$ is ${D}$ -admissible for any ${0 \leq D \leq \hbox{dim}(SL_d)}$ .

Let ${D_1,D_2,\theta}$ be as in the above exercise. By construction, we can then find subvarieties ${V_1, V_2}$ of ${SL_d(\overline{k})}$ of dimension ${D_1,D_2}$ respectively and standard positive integers ${m_1,m_2}$ such that

$\displaystyle |A^{m_1} \cap V_1| \not \ll K^{O(1)} |A|^{\theta D_1} \ \ \ \ \ (10)$

and

$\displaystyle |A^{m_2} \cap V_2| \not \ll K^{O(1)} |A|^{\theta D_2}. \ \ \ \ \ (11)$

On the other hand, we have

$\displaystyle |A^{m} \cap V| \ll K^{O(1)} |A|^{\theta (\hbox{dim}(V)+1)} \ \ \ \ \ (12)$

whenever ${V}$ is a subvariety of ${SL_d(\overline{k})}$ , with the improvement

$\displaystyle |A^{m} \cap V| \ll K^{O(1)} |A|^{\theta \hbox{dim}(V)} \ \ \ \ \ (13)$

whenever ${V}$ has dimension strictly less than ${D_1}$ , or strictly greater than ${D_2}$ .

We can use (12), (13) to show that ${A^{m_1} \times A^{m_2}}$ is “quantitatively Zariski dense” in ${V_1 \times V_2}$ :

Lemma 23 (Quantitative Zariski density) For any proper subvariety ${W}$ of ${V_1 \times V_2}$ , we have

$\displaystyle |(A^{m_1} \times A^{m_2}) \cap W|\ll K^{O(1)} |A|^{\theta (D_1+D_2)}.$

Proof: ${W}$ has dimension at most ${D_1+D_2-1}$ . By standard algebraic geometry, we see that for each ${0\leq D \leq D_1}$ , the set of ${y \in V_2}$ for which the slice ${\{ x \in V_1: (x,y) \in W\}}$ has dimension ${D}$ , has dimension at most ${D_1+D_2-D-1}$ . In particular, if ${D < D_1}$ , then by (12), (13) the contribution of such ${x}$ to ${|(A^{m_1} \times A^{m_2}) \cap W|}$ is at most

$\displaystyle K^{O(1)} \times |A|^{\theta D} \times K^{O(1)} |A|^{\theta (D_1+D_2-D-1+1)}$

while if ${D = D_1}$ , then the contribution is at most

$\displaystyle K^{O(1)} \times |A|^{\theta (D+1)} \times K^{O(1)} |A|^{\theta (D_1+D_2-D-1)}.$

(One may wonder about the question of uniformity in the ${O()}$ notation, but in nonstandard analysis one can automatically gain such uniformity through countable saturation; see Exercise 20 of this blog post.) Summing over all ${D}$ we obtain the claim. $\Box$

We will now use a counting argument (which is, unsurprisingly, related to the counting argument used to establish Proposition 17, or any of the other Larsen-Pink inequalities in preceding sections) to obtain a contradiction from these four estimates.

First, by decomposing ${V_1,V_2}$ into irreducible components (and using (12) to eliminate all lower-dimensional components) we may assume that ${V_1,V_2}$ are both irreducible.

The product ${V_1 \cdot V_2}$ is not necessarily a variety, but it is still a constructible set (i.e. a finite boolean combination of varieties), and can still be assigned a dimension (by equating the dimension of a constructible set with the dimension of its Zariski closure). As it contains a translate of ${V_2}$ , it has dimension at least ${D_2}$ . It would be convenient if ${V_1 \cdot V_2}$ had dimension strictly greater than ${V_2}$ . This is not necessarily the case, but it turns out that it becomes so after a generic conjugation, thanks to the almost simplicity of ${SL_d}$ :

Exercise 28 (Almost simplicity) Show that the only proper normal subgroups of ${SL_d(\overline{k})}$ are those contained in the centre of ${SL_d(\overline{k})}$ , i.e. in the identity matrix multipled by the ${d^{th}}$ roots of unity. (Hint: Let ${G}$ be a normal subgroup of ${SL_d(\overline{k})}$ that contains an element which is not a multiple of the identity. Place that element in Jordan normal form and divide it by one of its conjugates to make it fix a subspace of ${\overline{k}^d}$ ; iterate this procedure until one finds an element in ${G}$ that is the direct sum of the identity in ${SL_{d-2}(\overline{k})}$ and a non-central element of ${SL_2(\overline{k})}$ . Then use this to generate all of ${SL_d(\overline{k})}$ .)

Proposition 24 (Generic skewness) For generic ${g \in SL_d(\overline{k})}$ (i.e. for all ${g}$ in ${SL_d(\overline{k})}$ outside of a lower-dimensional variety), the set ${V_1 \cdot g \cdot V_2}$ has dimension strictly greater than ${D_2}$ .

Proof: Let ${g \in SL_d(\overline{k})}$ , and assume that ${V_1 \cdot g \cdot V_2}$ has dimension exactly ${D_2}$ . This set contains all the translates ${xg V_2}$ with ${x \in V_1}$ , which are each ${D_2}$ -dimensional irreducible varieties. By splitting up ${V_1\cdot g \cdot V_2}$ into components, we conclude that there are only finitely many distinct translates ${xg V_2}$ . If we denote one of these translates as ${W}$ , the set ${\{ x \in SL_d(\overline{k}): xgV_2 = W \}}$ is easily seen to be a variety (as it is the intersection of varieties ${Wy^{-1}g^{-1}}$ for ${y \in V_2}$ ); as a finite number of these sets cover ${V_1}$ , at least one of them has to be all of ${V_1}$ ; thus there is a ${W}$ such that ${xgV_2=W}$ for all ${x \in V_1}$ . In particular, this implies that ${g^{-1} y^{-1} x g V_2 = V_2}$ for all ${x,y \in V_1}$ .

Let ${S := \{ h \in SL_d(\overline{k}): hV_2 = V_2\}}$ . Arguing as before, ${S}$ is a variety, and is also a group; it is thus an algebraic group, and by the preceding discussion we have ${g^{-1} V_1^{-1} V_1 g \subset S}$ .

The set ${\{ g \in SL_d(\overline{k}): g^{-1} V_1^{-1} V_1 g \subset S \}}$ is a variety. If it has dimension strictly less than that of ${SL_d}$ , we are done, so we may assume this set is all of ${SL_d}$ ; thus ${g^{-1} V_1^{-1} V_1 g \subset S}$ for all ${g \in SL_d(\overline{k})}$ . By almost simplicity, the normal subgroup generated by ${V_1^{-1} V_1}$ is all of ${SL_d(\overline{k})}$ ; thus ${S}$ must be all of ${SL_d(\overline{k})}$ , thus ${hV_2 = V_2}$ for all ${h \in SL_d(\overline{k})}$ . But this forces ${V_2 = SL_d(\overline{k})}$ , a contradiction since ${D_2}$ is strictly less than ${\hbox{dim}(SL_d)}$ . $\Box$

Combining this proposition with the Zariski density of ${\langle A\rangle}$ , we see that we can find ${g \in A^m}$ for some standard ${m}$ such that ${V_1 \cdot g \cdot V_2}$ has dimension ${D}$ strictly greater than ${D_2}$ .

Fix this ${g}$ . Let ${\phi: V_1 \times V_2 \rightarrow \overline{V_1 \cdot g \cdot V_2}}$ be the twisted product map ${\phi(x,y) := xgy}$ . We have the double counting identity

$\displaystyle \sum_{z \in A^{m_1+m+m_2} \cap \overline{V_1 \cdot g \cdot V_2}} |A^{m_1}\times A^{m_2} \cap \phi^{-1}(\{z\})| = |A^{m_1} \cap V_1| |A^{m_2} \cap V_2|$

and thus by (10), (11)

$\displaystyle \sum_{z \in A^{m_1+m+m_2} \cap \overline{V_1 \cdot g \cdot V_2}} |A^{m_1}\times A^{m_2} \cap \phi^{-1}(\{z\})| \not \ll K^{O(1)} |A|^{\theta(D_1+D_2)}.$

Now, ${\phi}$ is a map from an irreducible ${D_1+D_2}$ -dimensional variety to a ${D}$ -dimensional variety with Zariski-dense image, and is thus a dominant map. Among other things, this implies that there is a subvariety ${S}$ of ${V_1 \times V_2}$ of dimension at most ${D_1+D_2-1}$ such that for all ${x \in \overline{V_1 \cdot g \cdot V_2}}$ , the set ${\phi^{-1}(\{x\}) \backslash S}$ has dimension ${D_1+D_2-D}$ . By (13), we then have

$\displaystyle |A^{m_1}\times A^{m_2} \cap \phi^{-1}(\{z\}) \backslash S| \ll K^{O(1)} |A|^{\theta(D_1+D_2-D)}$

for all ${z \in A^{m_1+m+m_2} \cap \overline{V_1 \cdot g \cdot V_2}}$ ; by another application of (13), we have

$\displaystyle |A^{m_1+m+m_2} \cap \overline{V_1 \cdot g \cdot V_2}| \ll K^{O(1)} |A|^{\theta D}.$

Combining these estimates we see that

$\displaystyle \sum_{z \in A^{m_1+m+m_2} \cap \overline{V_1 \cdot g \cdot V_2}} |A^{m_1}\times A^{m_2} \cap \phi^{-1}(\{z\}) \cap S| \not \ll K^{O(1)} |A|^{\theta(D_1+D_2)}.$

The left-hand side simplifies to ${|A^{m_1} \times A^{m_2} \cap S|}$ . But this then contradicts Lemma 23.

13 comments

Comments feed for this article

5 February, 2012 at 12:54 pm

Anonymous

I am impressed!

6 February, 2012 at 7:42 am

Misha Rudnev

Dear Terry: small corrections to Remark 1. Solymosi’s sum-products’ epsilon over C is 3/11 [MR2143727 (2006c:11021)]. I’ve recently made some minor improvements to that in arXiv:1111.4977v1. Sorry for being pernickety — this is obviously not the subject of the post, which I will now try to digest with great interest.
Best,
Misha

[Corrected, thanks – T.]

13 February, 2012 at 4:51 pm

254B, Notes 6: Non-concentration in subgroups « What’s new

[…] the last three notes, we discussed the Bourgain-Gamburd expansion machine and two of its three ingredients, namely […]

1 March, 2012 at 5:26 pm

254B, Notes 7: Sieving and expanders « What’s new

[…] see that is multiplicative for such . Finally, from the Schwarz-Zippel lemma (see Exercise 23 from Notes 5) we […]

23 May, 2012 at 3:08 am

Wei Zhou

Dear Prof. Tao,
There are some typo at the end of the paragraph before Exercise. It may be like the following: $g^{-1}A , hg^{-1}A$ are both contained in $H’$, and their joint is not empty, and then the joint of $A, ghg^{-1}A$ is not empty, which implies $ h \in H$.

[Hopefully fixed now – it was a strange LaTeX rendering bug. -T]

6 September, 2012 at 7:37 am

valuevar

Hi Terry –

For what it is worth, much or most of the material in section 2 first appeared in my paper on SL_2. This includes, for instance, Proposition 10 and a slightly weaker version of Proposition 13.

As you know, Larsen-Pink (which predated my work, at least in preprint form) did not make any statements about approximate subgroups or sets of small tripling; it also did not apply such results in this context. I am not , mind you, disputing the importance of their work. For one thing, it showed itself very useful in your generalization (with Breuillard and Green) of my work, in that it strongly suggested what the right strength and degree of generality of these statements should be (and gave alternative ideas to a proof, when seen from the optic of work on approximate groups). At the same time, note that Pyber-Szabo got essentially the same generalization as you did proceeding essentially from what I explained in SL_2 and SL_3.
Especially since you are explaining matters in the case of SL_2, referring and naming this kind of result only after Larsen-Pink looks odd.

Best
Harald

6 September, 2012 at 8:19 am

Terence Tao

Dear Harald,

Section 2 of this post is devoted exclusively to the setting of finite groups, and not more general approximate groups, and is thus covered directly by the results of the Larsen-Pink paper (in particular Proposition 10 and Proposition 13 are special cases of Theorem 4.2 and Theorem 6.2 of Larsen-Pink respectively). On the other hand, Hrushovski (see Section 5 of his paper) observed that the Larsen-Pink arguments carried over without essential difficulty to the setting of approximate groups (well, strictly speaking, he worked with ultraproducts of approximate groups rather than with individual approximate groups, but I view this as a primarily technical distinction).

But you’re certainly right that your papers (which predate Hrushovski’s) were the first to explicitly establish many of the key cases of the Larsen-Pink estimates for approximate groups in the SL_2 and SL_3 cases (though I believe that nobody was aware of the connection of your work with the earlier work of Larsen-Pink at that point). This was already mentioned briefly in the beginning of Section 3 (which, unlike Section 2, is devoted to approximate groups rather than to finite groups), but I will edit things a bit here to further clarify this point.

6 September, 2012 at 8:41 am

valuevar

Dear Terry,

Yes, I see – we would be talking about Proposition 17 and exercise 17-18 instead (for instance).

Just to be precise: as you know, in “Growth in SL_3”, the section dealing with this kind of estimates proves them not just for SL_3, but much more generally – sometimes for all groups of classical type (see, e.g., Corollary 5.4), sometimes for SL_n, but with proofs that work more generally (e.g., Corollary 5.16).

(What I had a bit of trouble making work in general was the pivoting argument – in retrospect, because one of the estimates was not quite strong enough.)

6 September, 2012 at 9:15 am

Terence Tao

The post has now been edited to reflect these statements.

Incidentally, on reading through Hrushovski’s paper again, I now see that the observation on the general applicability of the Larsen-Pink argument was first made in a 2008 paper of Hrushovski and Wagner (this is also mentioned in the “History” section of the Larsen-Pink paper). The situation there, being abstract and model-theoretic in nature, is far more general than the setting of either finite groups or approximate groups, but the specialisation to approximate groups was only made explicitly in the later paper of Hrushovski (and the key cases for the SL_2(F_p) problem are of course in your own 2008 paper).

10 September, 2013 at 8:15 am

Expansion in finite simple groups of Lie type | What's new

[…] out to be an elementary combinatorial one, based on the “pivot” argument discussed in these lecture notes of […]

18 October, 2018 at 2:42 am

Matthew Tointon

Dear Terry,
I think it might be more natural to call Exercise 1 a diameter bound rather than a girth bound.

[Corrected, thanks – T.]

26 August, 2021 at 11:09 pm

Constantin Kogler

I think there is a typo in the penultimate line of the proof of Theorem 2.
As you write for $h \in H'$ it holds that $A$ and $Ah'$ have a non-empty intersection. Yet this implies $H' \subset A^{-1}A$ (and not $\subset AA^{-1}$ )

Furthermore we can show that $|AA^{-1}| = |A^{-1}A|$ and $H' = A^{-1}A$ : As $|AA^{-1}| = |H| = |H'|$ , using the assumption we conclude $|AA^{-1}| \leq |A^{-1}A| < \frac{3}{2}|A|$ . Repeating the same argument with $A^{-1}$ instead of $A$ , it follows that $|AA^{-1}| = |A^{-1}A|$ and $H' = A^{-1}A$ .

I was not able to show that $A^{-1}A = AA^{-1}$ . Do you think this holds in general?

30 August, 2021 at 8:24 am

Terence Tao

Thanks for pointing out the typo, which is now corrected. The argument shows that $H' = A^{-1} A$ and $H = A A^{-1}$ are conjugate groups, but they are not equal in general (consider for instance the case when $A = Hg = gH'$ ).

	Dilip Kulkarni on The inverse theorem for the U^…
	Anonymous on The inverse theorem for the U^…
	Anonymous on The inverse theorem for the U^…
	Anonymous on Using the Smith normal form to…
	Romain Viguier on ICM and IMU award ceremony beg…
	diophantine approxim… on Hilbert’s seventh proble…
	Brief communication… on The International Congress of…
	Michael Barany on Request for comments from the…
	Internet web page fo… on Short communication satellite…
	What is the trace?… on 254A, Notes 5: Free proba…
	Anonymous on Request for comments from the…
	porton on Request for comments from the…
	Aditya Guha Roy on Request for comments from the…
	math postdoc on Request for comments from the…
	Aditya Guha Roy on Request for comments from the…

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

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

13 comments

Leave a Reply Cancel reply

For commenters

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

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

13 comments

Leave a Reply Cancel reply

For commenters