You are currently browsing the tag archive for the ‘sum-product theorems’ tag.

This is a blog version of a talk I recently gave at the IPAM workshop on “The Kakeya Problem, Restriction Problem, and Sum-product Theory”.

Note: the discussion here will be highly non-rigorous in nature, being extremely loose in particular with asymptotic notation and with the notion of dimension. Caveat emptor.

One of the most infamous unsolved problems at the intersection of geometric measure theory, incidence combinatorics, and real-variable harmonic analysis is the Kakeya set conjecture. We will focus on the following three-dimensional case of the conjecture, stated informally as follows:

Conjecture 1 (Kakeya conjecture) Let ${E}$ be a subset of ${{\bf R}^3}$ that contains a unit line segment in every direction. Then ${\hbox{dim}(E) = 3}$.

This conjecture is not precisely formulated here, because we have not specified exactly what type of set ${E}$ is (e.g. measurable, Borel, compact, etc.) and what notion of dimension we are using. We will deliberately ignore these technical details in this post. It is slightly more convenient for us here to work with lines instead of unit line segments, so we work with the following slight variant of the conjecture (which is essentially equivalent):

Conjecture 2 (Kakeya conjecture, again) Let ${{\cal L}}$ be a family of lines in ${{\bf R}^3}$ that meet ${B(0,1)}$ and contain a line in each direction. Let ${E}$ be the union of the restriction ${\ell \cap B(0,2)}$ to ${B(0,2)}$ of every line ${\ell}$ in ${{\cal L}}$. Then ${\hbox{dim}(E) = 3}$.

As the space of all directions in ${{\bf R}^3}$ is two-dimensional, we thus see that ${{\cal L}}$ is an (at least) two-dimensional subset of the four-dimensional space of lines in ${{\bf R}^3}$ (actually, it lies in a compact subset of this space, since we have constrained the lines to meet ${B(0,1)}$). One could then ask if this is the only property of ${{\cal L}}$ that is needed to establish the Kakeya conjecture, that is to say if any subset of ${B(0,2)}$ which contains a two-dimensional family of lines (restricted to ${B(0,2)}$, and meeting ${B(0,1)}$) is necessarily three-dimensional. Here we have an easy counterexample, namely a plane in ${B(0,2)}$ (passing through the origin), which contains a two-dimensional collection of lines. However, we can exclude this case by adding an additional axiom, leading to what one might call a “strong” Kakeya conjecture:

Conjecture 3 (Strong Kakeya conjecture) Let ${{\cal L}}$ be a two-dimensional family of lines in ${{\bf R}^3}$ that meet ${B(0,1)}$, and assume the Wolff axiom that no (affine) plane contains more than a one-dimensional family of lines in ${{\cal L}}$. Let ${E}$ be the union of the restriction ${\ell \cap B(0,2)}$ of every line ${\ell}$ in ${{\cal L}}$. Then ${\hbox{dim}(E) = 3}$.

Actually, to make things work out we need a more quantitative version of the Wolff axiom in which we constrain the metric entropy (and not just dimension) of lines that lie close to a plane, rather than exactly on the plane. However, for the informal discussion here we will ignore these technical details. Families of lines that lie in different directions will obey the Wolff axiom, but the converse is not true in general.

In 1995, Wolff established the important lower bound ${\hbox{dim}(E) \geq 5/2}$ (for various notions of dimension, e.g. Hausdorff dimension) for sets ${E}$ in Conjecture 3 (and hence also for the other forms of the Kakeya problem). However, there is a key obstruction to going beyond the ${5/2}$ barrier, coming from the possible existence of half-dimensional (approximate) subfields of the reals ${{\bf R}}$. To explain this problem, it easiest to first discuss the complex version of the strong Kakeya conjecture, in which all relevant (real) dimensions are doubled:

Conjecture 4 (Strong Kakeya conjecture over ${{\bf C}}$) Let ${{\cal L}}$ be a four (real) dimensional family of complex lines in ${{\bf C}^3}$ that meet the unit ball ${B(0,1)}$ in ${{\bf C}^3}$, and assume the Wolff axiom that no four (real) dimensional (affine) subspace contains more than a two (real) dimensional family of complex lines in ${{\cal L}}$. Let ${E}$ be the union of the restriction ${\ell \cap B(0,2)}$ of every complex line ${\ell}$ in ${{\cal L}}$. Then ${E}$ has real dimension ${6}$.

The argument of Wolff can be adapted to the complex case to show that all sets ${E}$ occuring in Conjecture 4 have real dimension at least ${5}$. Unfortunately, this is sharp, due to the following fundamental counterexample:

Proposition 5 (Heisenberg group counterexample) Let ${H \subset {\bf C}^3}$ be the Heisenberg group

$\displaystyle H = \{ (z_1,z_2,z_3) \in {\bf C}^3: \hbox{Im}(z_1) = \hbox{Im}(z_2 \overline{z_3}) \}$

and let ${{\cal L}}$ be the family of complex lines

$\displaystyle \ell_{s,t,\alpha} := \{ (\overline{\alpha} z + t, z, sz + \alpha): z \in {\bf C} \}$

with ${s,t \in {\bf R}}$ and ${\alpha \in {\bf C}}$. Then ${H}$ is a five (real) dimensional subset of ${{\bf C}^3}$ that contains every line in the four (real) dimensional set ${{\cal L}}$; however each four real dimensional (affine) subspace contains at most a two (real) dimensional set of lines in ${{\cal L}}$. In particular, the strong Kakeya conjecture over the complex numbers is false.

This proposition is proven by a routine computation, which we omit here. The group structure on ${H}$ is given by the group law

$\displaystyle (z_1,z_2,z_3) \cdot (w_1,w_2,w_3) = (z_1 + w_1 + z_2 \overline{w_3} - z_3 \overline{w_2}, z_2 +w_2, z_3+w_3),$

giving ${E}$ the structure of a ${2}$-step simply-connected nilpotent Lie group, isomorphic to the usual Heisenberg group over ${{\bf R}^2}$. Note that while the Heisenberg group is a counterexample to the complex strong Kakeya conjecture, it is not a counterexample to the complex form of the original Kakeya conjecture, because the complex lines ${{\cal L}}$ in the Heisenberg counterexample do not point in distinct directions, but instead only point in a three (real) dimensional subset of the four (real) dimensional space of available directions for complex lines. For instance, one has the one real-dimensional family of parallel lines

$\displaystyle \ell_{0,t,0} = \{ (t, z, 0): z \in {\bf C}\}$

with ${t \in {\bf R}}$; multiplying this family of lines on the right by a group element in ${H}$ gives other families of parallel lines, which in fact sweep out all of ${{\cal L}}$.

The Heisenberg counterexample ultimately arises from the “half-dimensional” (and hence degree two) subfield ${{\bf R}}$ of ${{\bf C}}$, which induces an involution ${z \mapsto \overline{z}}$ which can then be used to define the Heisenberg group ${H}$ through the formula

$\displaystyle H = \{ (z_1,z_2,z_3) \in {\bf C}^3: z_1 - \overline{z_1} = z_2 \overline{z_3} - z_3 \overline{z_2} \}.$

Analogous Heisenberg counterexamples can also be constructed if one works over finite fields ${{\bf F}_{q^2}}$ that contain a “half-dimensional” subfield ${{\bf F}_q}$; we leave the details to the interested reader. Morally speaking, if ${{\bf R}}$ in turn contained a subfield of dimension ${1/2}$ (or even a subring or “approximate subring”), then one ought to be able to use this field to generate a counterexample to the strong Kakeya conjecture over the reals. Fortunately, such subfields do not exist; this was a conjecture of Erdos and Volkmann that was proven by Edgar and Miller, and more quantitatively by Bourgain (answering a question of Nets Katz and myself). However, this fact is not entirely trivial to prove, being a key example of the sum-product phenomenon.

We thus see that to go beyond the ${5/2}$ dimension bound of Wolff for the 3D Kakeya problem over the reals, one must do at least one of two things:

• (a) Exploit the distinct directions of the lines in ${{\mathcal L}}$ in a way that goes beyond the Wolff axiom; or
• (b) Exploit the fact that ${{\bf R}}$ does not contain half-dimensional subfields (or more generally, intermediate-dimensional approximate subrings).

(The situation is more complicated in higher dimensions, as there are more obstructions than the Heisenberg group; for instance, in four dimensions quadric surfaces are an important obstruction, as discussed in this paper of mine.)

Various partial or complete results on the Kakeya problem over various fields have been obtained through route (a) or route (b). For instance, in 2000, Nets Katz, Izabella Laba and myself used route (a) to improve Wolff’s lower bound of ${5/2}$ for Kakeya sets very slightly to ${5/2+10^{-10}}$ (for a weak notion of dimension, namely upper Minkowski dimension). In 2004, Bourgain, Katz, and myself established a sum-product estimate which (among other things) ruled out approximate intermediate-dimensional subrings of ${{\bf F}_p}$, and then pursued route (b) to obtain a corresponding improvement ${5/2+\epsilon}$ to the Kakeya conjecture over finite fields of prime order. The analogous (discretised) sum-product estimate over the reals was established by Bourgain in 2003, which in principle would allow one to extend the result of Katz, Laba and myself to the strong Kakeya setting, but this has not been carried out in the literature. Finally, in 2009, Dvir used route (a) and introduced the polynomial method (as discussed previously here) to completely settle the Kakeya conjecture in finite fields.

Below the fold, I present a heuristic argument of Nets Katz and myself, which in principle would use route (b) to establish the full (strong) Kakeya conjecture. In broad terms, the strategy is as follows:

1. Assume that the (strong) Kakeya conjecture fails, so that there are sets ${E}$ of the form in Conjecture 3 of dimension ${3-\sigma}$ for some ${\sigma>0}$. Assume that ${E}$ is “optimal”, in the sense that ${\sigma}$ is as large as possible.
2. Use the optimality of ${E}$ (and suitable non-isotropic rescalings) to establish strong forms of standard structural properties expected of such sets ${E}$, namely “stickiness”, “planiness”, “local graininess” and “global graininess” (we will roughly describe these properties below). Heuristically, these properties are constraining ${E}$ to “behave like” a putative Heisenberg group counterexample.
3. By playing all these structural properties off of each other, show that ${E}$ can be parameterised locally by a one-dimensional set which generates a counterexample to Bourgain’s sum-product theorem. This contradiction establishes the Kakeya conjecture.

Nets and I have had an informal version of argument for many years, but were never able to make a satisfactory theorem (or even a partial Kakeya result) out of it, because we could not rigorously establish anywhere near enough of the necessary structural properties (stickiness, planiness, etc.) on the optimal set ${E}$ for a large number of reasons (one of which being that we did not have a good notion of dimension that did everything that we wished to demand of it). However, there is beginning to be movement in these directions (e.g. in this recent result of Guth using the polynomial method obtaining a weak version of local graininess on certain Kakeya sets). In view of this (and given that neither Nets or I have been actively working in this direction for some time now, due to many other projects), we’ve decided to distribute these ideas more widely than before, and in particular on this blog.

In the previous set of notes, we saw that one could derive expansion of Cayley graphs from three ingredients: non-concentration, product theorems, and quasirandomness. Quasirandomness was discussed in Notes 3. In the current set of notes, we discuss product theorems. Roughly speaking, these theorems assert that in certain circumstances, a finite subset ${A}$ of a group ${G}$ either exhibits expansion (in the sense that ${A^3}$, say, is significantly larger than ${A}$), or is somehow “close to” or “trapped” by a genuine group.

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

• (Expansion) One has ${|A^3| \geq |A|^{1+\epsilon}}$.
• (Close to ${G}$) One has ${|A| \geq |G|^{1-O_d(\epsilon)}}$.
• (Trapping) ${A}$ is contained in a proper subgroup of ${G}$.

We will prove this theorem (which was proven first in the ${d=2,3}$ cases for fields ${F}$ of prime order by Helfgott, and then for ${d=2}$ and general ${F}$ by Dinai, and finally to general ${d}$ and ${F}$ independently by Pyber-Szabo and by Breuillard-Green-Tao) later in this notes. A more qualitative version of this proposition was also previously obtained by Hrushovski. There are also generalisations of the product theorem of importance to number theory, in which the field ${k}$ is replaced by a cyclic ring ${{\bf Z}/q{\bf Z}}$ (with ${q}$ not necessarily prime); this was achieved first for ${d=2}$ and ${q}$ square-free by Bourgain, Gamburd, and Sarnak, by Varju for general ${d}$ and ${q}$ square-free, and finally by this paper of Bourgain and Varju for arbitrary ${d}$ and ${q}$.

Exercise 1 (Girth bound) Assuming Theorem 1, show that whenever ${S}$ is a symmetric set of generators of ${SL_d(k)}$ for some finite field ${k}$ and some ${d\geq 2}$, then any element of ${SL_d(k)}$ can be expressed as the product of ${O_d( \log^{O_d(1)} |k| )}$ elements from ${S}$. (Equivalently, if we add the identity element to ${S}$, then ${S^m = SL_d(k)}$ for some ${m = O_d( \log^{O_d(1)} |k| )}$.) This is a special case of a conjecture of Babai and Seress, who conjectured that the bound should hold uniformly for all finite simple groups (in particular, the implied constants here should not actually depend on ${d}$. The methods used to handle the ${SL_d}$ case can handle other finite groups of Lie type of bounded rank, but at present we do not have bounds that are independent of the rank. On the other hand, a recent paper of Helfgott and Seress has almost resolved the conjecture for the permutation groups ${A_n}$.

A key tool to establish product theorems is an argument which is sometimes referred to as the pivot argument. To illustrate this argument, let us first discuss a much simpler (and older) theorem, essentially due to Freiman, which has a much weaker conclusion but is valid in any group ${G}$:

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

• (Expansion) One has ${|A^{-1} A| \geq \frac{3}{2} |A|}$.
• (Close to a subgroup) ${A}$ is contained in a left-coset of a group ${H}$ with ${|H| < \frac{3}{2} |A|}$.

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

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

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

• (Non-involved case) ${A \cap gA}$ is empty.
• (Involved case) ${|A \cap gA| > \frac{|A|}{2}}$.

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

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

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

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

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

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

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

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

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

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

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

Below the fold, we give further examples of the pivot argument in other group-like situations, including Theorem 2 and also the “sum-product theorem” of Bourgain-Katz-Tao and Bourgain-Glibichuk-Konyagin.

I’ve uploaded a new paper to the arXiv entitled “The sum-product phenomenon in arbitrary rings“, and submitted to Contributions to Discrete Mathematics. The sum-product phenomenon asserts, very roughly speaking, that given a finite non-empty set A in a ring R, then either the sum set $A+A := \{ a+b: a, b \in A \}$ or the product set $A \cdot A := \{ ab: a, b \in A \}$ will be significantly larger than A, unless A is somehow very close to being a subring of R, or if A is highly degenerate (for instance, containing a lot of zero divisors). For instance, in the case of the integers $R = {\Bbb Z}$, which has no non-trivial finite subrings, a long-standing conjecture of Erdös and Szemerédi asserts that $|A+A| + |A \cdot A| \gg_\varepsilon |A|^{2-\varepsilon}$ for every finite non-empty $A \subset {\Bbb Z}$ and every $\varepsilon > 0$. (The current best result on this problem is a very recent result of Solymosi, who shows that the conjecture holds for any $\varepsilon$ greater than 2/3.) In recent years, many other special rings have been studied intensively, most notably finite fields and cyclic groups, but also the complex numbers, quaternions, and other division algebras, and continuous counterparts in which A is now (for instance) a collection of intervals on the real line. I will not try to summarise all the work on sum-product estimates and their applications (which range from number theory to graph theory to ergodic theory to computer science) here, but I discuss this in the introduction to my paper, which has over 50 references to this literature (and I am probably still missing out on a few).

I was recently asked the question as to what could be said about the sum-product phenomenon in an arbitrary ring R, which need not be commutative or contain a multiplicative identity. Once one makes some assumptions to avoid the degenerate case when A (or related sets, such as A-A) are full of zero-divisors, it turns out that there is in fact quite a bit one can say, using only elementary methods from additive combinatorics (in particular, the Plünnecke-Ruzsa sum set theory). Roughly speaking, the main results of the paper assert that in an arbitrary ring, a set A which is non-degenerate and has small sum set and product set must be mostly contained inside a subring of R of comparable size to A, or a dilate of such a subring, though in the absence of invertible elements one sometimes has to enlarge the ambient ring R slightly before one can find the subring. At the end of the paper I specialise these results to specific rings, such as division algebras or products of division algebras, cyclic groups, or finite-dimensional algebras over fields. Generally speaking, the methods here give very good results when the set of zero divisors is sparse and easily describable, but poor results otherwise. (In particular, the sum-product theory in cyclic groups, as worked out by Bourgain and coauthors, is only recovered for groups which are the product of a bounded number of primes; the case of cyclic groups whose order has many factors seems to require a more multi-scale analysis which I did not attempt to perform in this paper.)
Read the rest of this entry »