LECTURE NOTES 3 FOR 254A

TERENCE TAO

1. Introduction

In the previous two sets of notes we have been concerned with the size of the sumset

{a + b : (a, b) ∈ A × B}

and difference set

{a − b : (a, b) ∈ A × B}

and how the sizes of these sets were related to each other, and whether they revealed anything about the inner structure of A and B.

However, in many applications we do not have control over the full sumset or full difference set: we merely have control over a “large portion” of the sumset or difference set. In other words, we may only have good control on a set such as

{a + b : (a, b) ∈ G}

or

{a − b : (a, b) ∈ G},

where G is a “large” subset of A×B, and then we are interested in asking the same sorts of questions (how does a partial sumset control a partial difference set? What does this say about the structure of A and B?)

As one can imagine, the results here are more incomplete than in the case of total sumsets and total difference sets. Nevertheless, we still have some important results, notably the Balog-Szemeredi theorem, which asserts that control of partial sumsets can be used to imply control of total sumsets if one passes to a refinement.

To give one indication of how partial sum sets or partial difference sets come up, suppose we have two sets A and B of very different cardinalities, say |A| ≫ |B|, but we know that A is essentially B-invariant, so that |A + B| ∼ |A|. Now we want to say something about A − B. In week 1 notes we know that we can say something if we lose a small power of A and pass to a refinement. Here is another approach. We have a projection π_{+1} : A × B → A + B defined by the addition map π_{+1}(a, b) := a + b. This is a map from a large set (of cardinality |A||B|) to a small set (of cardinality ∼ |A|). This means that there must be substantial failure of injectivity in π_{+1}; more precisely, (see Q1), we must have

|\{(a, b, a′, b′) ∈ A × B × A × B : a + b = a′ + b′\}| ≥ \frac{|A|^{2}|B|^{2}}{|A + B|} ≳ |A||B|^{2}.

Now we use a basic relationship between addition and subtraction: if a+b = a′ +b′, then a − b′ = a′ − b. Thus if one has many sum collisions, then one must also have many difference collisions:

|{(a, b′, a′, b) ∈ A × B × A × B : a − b′ = a′ − b}| ≳ |A||B|^{2}.

Thus, if we define π_{−1} : A×B → A−B to be the subtraction map π_{−1}(a, b) := a−b, then we have

|{(x, x′) ∈ (A × B)^{2} : π_{−1}(x) = π_{−1}(x′)}| ≳ |A||B|^{2}.

To use this, we need a definition. Let us call a difference d ∈ A − B popular if it can be written as a − b in ≳ |B| different ways, i.e.

|{x ∈ A × B : π_{−1}(x) = d}| ≳ |B|.

Note that no difference x can be written in more than |B| ways, since once you choose b there is no choice for a (since a = x + b). So popular differences are ones which can be written in a near-maximal number of ways. Let G be the set of pairs x ∈ A × B for which π_{−1}(x) is popular. If x ∉ G, then there are ≪ |G| elements x′ ∈ A × B for which π_{−1}(x′) = π_{−1}(x). Thus we have

|{(x, x′) ∈ (A × B)^{2} : π_{−1}(x) = π_{−1}(x′), x ∉ G}| ≪ |A × B||B| = |A||B|^{2}.

Thus we must have

|{(x, x′) ∈ (A × B)^{2} : π_{−1}(x) = π_{−1}(x′), x ∈ G}| ≳ |A||B|^{2}.

Since each x ∈ G contributes at most |B| elements to this set, we thus have

|G| ≳ |A||B|,

i.e. G is a refinement of A × B. The set

{a − b : (a, b) ∈ G}

is the set of all popular differences. Since each difference requires ∼ |B| elements from G, we have

|{a − b : (a, b) ∈ G}| ≲ |G|/|B| ≤ |A × B|/|B| = |A|.

To summarize, starting from the hypothesis that all of the sum set A + B had size ∼ |A|, we can conclude that a large portion of the difference set A − B also has size ∼ |A|. (One can weaken the hypothesis, assuming instead that a large portion of {a + b : (a, b) ∈ G′} the sumset has size ∼ |A|, although because at some point we swap (a, b, a′, b′) with (a, b′, a′, b) the set G and G′ are not directly related.)

We would like to then reverse these types of implications, so that if one assumes that a large part of A+B (for instance) is small, then perhaps all of A+B is small. As stated, such a claim is clearly false. For instance, let N be a large number, and let A = B consist of the arithmetic progression {1, 2, …, N}, together with N generic integers. Then |A| = |B| = 2N, and a large portion of A + B is contained inside the small set {2, …, 2N} (indeed, one quarter of A × B projects onto this set), but A + B is huge, of the order of N^{2}. The problem here is that A and B contain a large number of “junk” elements which do not contribute at all to the portion G of A × B which is projecting onto the small set, but which do bloat the size of A + B unnecessarily.

The Balog-Szemerédi theorem [1] asserts that in such situations, one can always trim away the junk and make A + B small again:

Theorem 1.1 (Balog-Szemerédi theorem). Let N be a large integer, and let A and B be finite subsets of an abelian group Z such that |A| ∼ |B| ∼ N. Suppose also that there is a refinement G ⊆ A × B of A × B such that the differences of a − b are small:

|{a − b : (a, b) ∈ G}| ≲ N.

Then we can find refinements A′, B′ of A and B respectively such that

|A′ − B′| ≲ N.

Recall that a set A′ is a refinement of A if A′ ⊆ A and |A′| ∼ |A|. From sumset estimates (see Week 1 notes) we know that once |A′ − B′| ≲ N, we know that A′ and B′ (and even A′ ∪ B′) are essentially closed under addition, subtraction, and any other finite combination of these operations; if we are in a torsion-free group we also know that A′, B′ are a refinement of a generalized arithmetic progression of small rank. IN short, we know just about everything about A′ and B′. So the Balog-Szemerédi theorem says that if most of A − B is small, then A and B both contain large components which are very highly structured. (As mentioned before, the rest of A and B may well be random noise).

Note that the claim would be trivial if the set G contained a large Cartesian product A′ × B′. However, all we know is that G is a large subset of A × B, and this is not enough to obtain a large Cartesian product (see Q3).

We now present a proof by Gowers [4] of the Balog-Szemerédi theorem which gives quite good bounds (the final constants are basically just polynomials of the original constants, as opposed to the exponential (or worse) constants that can come out of things like Freiman’s theorem).

Note: throughout these notes, we shall be using the Cauchy-Schwarz estimate (Q1) and the popularity argument (Q2) quite often.

2. Proof of the Balog-Szeméredi theorem

The basic idea of the proof is as follows. Fix N, A, B, G; clearly we may assume that A and B are disjoint (by translating one set if necessary). We need to find refinements A′ and B′ such that A′ −B′ is very small, of size O(N). Since |A′| ∼ N and |B′| ∼ N, the trivial bound for A′ − B′ is O(N^{2}) - because the differences a − b of A′ − B′ could all be distinct. This is far too weak a bound. However, if we knew that all the differences of A′ − B′ were popular - i.e. for every a − b in A′ − B′, there existed ≳ N other pairs (a′, b′) ∈ A × B for which a − b = a′ − b′ - then this would ensure that A′ − B′ only has cardinality O(N) (because each distinct element A′ − B′ is associated to ≳ N pairs from A × B, and there are only ∼ N^{2} pairs in A × B to go around). So, a naive way to try to prove this theorem is to try to choose A′ and B′ so that all the differences in A′ − B′ are popular. (This is a manifestation of a basic principle: if one wants to make a set (in this case A′ − B′) small, try to make it so that each element of the set consumes a large number of resources (in this case, a large number of differences), and ensure that the total number of resources (in this case, the pairs A × B) is bounded. The main problem is to prevent a proliferation of a large number of elements, each of which consumes very little resources).

Define a (symmetric) relation ∼ on A × B ∪ B × A by setting a ∼ b or b ∼ a if a − b is a popular difference. From the hypothesis on G and the popularity argument in Q2 we see that this relation is quite dense; the set of pairs (a, b) ∈ A × B such that a ∼ b is ≳ N^{2}. We can think of this as a bipartite graph; for sake of analogy, we will think of A, B as distinct sets of people, and think of the relation a ∼ b as saying that person a knows person b. By the resource consumption argument given above, the set

D := {a − b : a ∼ b}

of popular differences is small:

|D| ≲ N.

Unfortunately, even though we have lots of connections (lots of pairs of people know each other), we don’t necessarily have large sets A′, B′ such that all of the people in A′ know all the people in B′ - i.e. we don’t know that we can make A′ and B′ totally connected via the relation ∼. (See Q3; also if you have some experience with Ramsey theory, you know that this is a rather tall order).

The trick is to weaken the relation ∼ by using degrees of separation (as in the infamous “six degrees of separation”). We first set 0 < ε ≤ 1 to be a small parameter (comparable to 1) to be chosen later, and define a (symmetric) relation ∼∼ on B × B by setting b ∼∼ b′ if

|{a′ ∈ A : b ∼ a′ ∼ b′}| ≥ εN.

i.e. two people b, b′ are related by ∼∼ if they are connected by one degree of separation in multiple (≳ N) ways. We will say that b and b′ communicate if they are related by ∼∼ (they don’t directly know each other, but they have a lot of mutual friends). We then define a relation ∼∼∼ on A × B by setting a ∼∼∼ b if

|{b′ ∈ B : a ∼ b′ ∼∼ b}| ≳ N;

roughly speaking, we have a ∼∼∼ b if a and b are connected by three degrees of separation in multiple (≳ N^{2}) ways. We say that a is aware of b if a ∼∼∼ b (they may not directly know each other, but a knows many people who communicate with b). The intuition is that this relation is much weaker than than ∼, and thus it should be easier to find large groups A′, B′ of people which are totally connected by this relation. (There is an analogy here with some arguments in the previous notes, where a set A did not contain a large arithmetic progression, but the variant 2A − 2A did).

First, we check that even though the awareness relation ∼∼∼ is weak, it still consumes enough resources that the difference set is still small:

Lemma 2.1. The set {a − b : a ∼∼∼ b} has cardinality O(N).

Proof Let a ∼∼∼ b. By definition, we can find ≳ εN^{2} pairs (a′, b′) such that a ∼ b′ ∼ a′ ∼ b. From the identity

a − b = (a − b′) − (a′ − b′) + (a′ − b)

we thus see that there are ≳ N^{2} solutions to the equation

a − b = d_{1} − d_{2} + d_{3}; d_{1}, d_{2}, d_{3} ∈ D.

(Note that different pairs (a′, b′) will lead to different triples of popular differences (d_{1}, d_{2}, d_{3})). Thus each difference a − b with a ∼∼∼ b is associated with ≳ N^{2} triples (d_{1}, d_{2}, d_{3}) in D^{3}. But as discussed before D only has cardinality O(N), hence D^{3} has cardinality O(N^{3}); thus there are only at most O(N) possible values for a − b, and the lemma follows.

So the whole problem now is to find large sets A′, B′ which are totally connected by the awareness relation ∼∼∼. An obvious sub-problem here is to find a large set B′ such that the elements of B′ are related to each other by the communication relation ∼∼ quite often.

The first thing to do is to refine B by kicking out all the unfriendly people, as they clearly are not going to be part of the final set B′. Let B_{1} ⊂ B be the set of all the people b in B who know ≳ N people in A:

|{a ∈ A : a ∼ b}| ≳ N for all b ∈ B_{1}.

By the popularity argument we know that

|{(a, b) ∈ A × B_{1} : a ∼ b}| ≳ N^{2}

and in particular that |B_{1}| ∼ N. So even after we remove all the unfriendly people from B, we still have a large group of people B_{1}, and a lot of pairs of people between A and B_{1} who know each other.

Now, we pick a random person a_{0} ∈ A and set B_{2} = B_{2}(a_{0}) ⊆ B_{1} to be all the people that a_{0} knows directly:

B_{2} := {b ∈ B_{1} : b ∼ a_{0}}.

Let us call B_{2}(a_{0}) the friends of a_{0}. The point is that a pair of communicating people b, b′ are much more likely to both be the friends of a_{0}, than a pair of noncommunicating people b, b′ (since they just don’t have that many mutual friends). Inverting this, this should mean that most friends of a_{0} communicate a lot.

Also, while the set B_{2} may occasionally be small (because a_{0} might be particularly unfriendly), it will be large on the average. Indeed, since |{(a, b) ∈ A × B_{1} : a ∼ b}| ∼ N^{2}, we see from the popularity argument (Q2) that |B_{2}| has expectation ∼ N, and in particular we have |B_{2}| ∼ N with probability ∼ 1.

Now let’s condition on the event that |B_{2}| ∼ N; this event has probability ∼ 1 so this conditioning does not significantly distort probabilities. Take two uncommunicative people b, b′ ∈ B_{1}, so that b ≁∼b′. By definition, b and b′ communicate with O(εN) people in A. Thus the probability that these people both lie in B_{2} is O(ε). Summing over all uncommunicative pairs (there are O(N^{2}) of them) and using linearity of expectation, we obtain

E(|{(b, b′) ∈ B_{2} : b ≁∼b′}|) ≲ εN^{2} ≲ ε|B_{2}|^{2}.

Thus on the average, at most O(ε) of the pairs in B_{1} are uncommunicative. By the pigeonhole principle, we may thus find an a_{0} ∈ A such that B_{2} := B_{2}(a_{0}) has size |B_{2}| ∼ N and we have the bound

|{(b, b′) ∈ B_{2} : b ≁∼b′}| ≲ ε|B_{2}|^{2}.

Call an element b ∈ B_{2} uncommunicative if

|{b′ ∈ B_{2} : b ≁∼b′}| ≳ ε^{1/2}|B_{2}|.

Clearly, there are at most O(ε^{1/2}|B_{2}|) uncommunicative elements of B_{2} (this is the popularity argument again!). Thus if we let B_{∗} ⊆ B_{2} be the uncommunicative elements of B_{2}, then B_{∗} is fairly small:

|B_{∗}| ≲ ε^{1/2}|B_{2}|.

By construction of B_{1}, everybody in B_{1} knows ≳ N people in A. Since B_{2} is a subset of B_{1}, we thus have

|{(a, b) ∈ A × B_{2} : a ∼ b}| ≳ N|B_{2}| ≳ N^{2};

thus a lot of people in A know a lot of people in B_{2}. By the popularity argument, there thus exists a refinement A′ of A such that everybody in A′ knows many people from B_{2}:

|{b′ ∈ B_{2} : a ∼ b′}| ≳ N for all a ∈ A′.

We are now ready to define B′: we simply set B′ := B_{2}\B_{∗}, i.e. we choose all the communicative people from B_{2}. Since B_{∗} is so small (if ε is small enough), we have |B′| ∼ N, so that B′ is indeed a refinement of B. We now claim that a ∼∼∼ b for every a ∈ A′, b ∈ B′.

To prove this, fix a ∈ A′ and b ∈ B′. By construction, a knows ≳ N people b′ in B_{2}. Since B_{∗} is so small (if ε is small enough), a must therefore know ≳ N people b′ in B′. Since b is not uncommunicative, it will communicate with all but O(ε^{1/2}N) people in B′. Thus, if ε is small enough, it will communicate with ≳ N of the people b′ mentioned above - and hence a ∼∼∼ b. This, combined with the previous Lemma, shows that |A′ − B′| ≲ N, and the result follows. □

Note how every time we make the relation weaker, we can make it denser. Regarding the original knowledge relation a ∼ b, we could only say things like “people in B_{1} know many (≳ N) people in A”. For the slightly weaker communication relation b ∼∼ b′, we could say things like “people in B’ communicate all but a few (O(ε^{1/2}N)) people in B_{2}”. And finally regarding the weakest notion of awareness a ∼∼∼ b, we can say that “people in A′ are aware of all the people in B′”.

The Balog-Szemerédi theorem can be made a little more quantitative: an inspection of the above proof reveals that the constants only grow polynomially rather than exponentially. More precisely, we have Theorem 2.2 (Quantitative Balog-Szemerédi theorem). Let N be a large integer, and let A and B be finite subsets of an abelian group Z such that |A| = |B| = N. Suppose also that there is a set G ⊆ A × B of A × B with |G| ≥ N^{2}/K such that the differences of a − b are small:

|{a − b : (a, b) ∈ G}| ≤ KN.

Then we can find subsets A′, B′ of A and B respectively such that

|A′|, |B′| ≳ K^{−C}N

and

|A′ − B′| ≲ K^{C}N.

One could even work out these constants C explicitly (they are of the order of 10 or so, depending on how efficiently you run the above argument), but we will not do so here. This quantitative version has applications to arithmetic progressions, as we will see in a later set of notes; for now, however, we shall focus on its application to the Kakeya problem.

3. A variant of the Balog-Szemerédi theorem, and applications to the Kakeya problem

Before we get to the Kakeya problem, we need a variant of the Balog-Szemerédi theorem. To do so, let us first digress on popular rows and columns.

Suppose that A and B are finite sets with cardinality |A| ∼ |B| ∼ N, and let H ⊆ A × B be a large subset of A × B, so that |H| ∼ N^{2}. One can think of A × B as looking roughly like a square, either considered as the union of ∼ N rows of the form A × {b}, or as the union of ∼ N columns of the form {a} × B. Each of these rows and columns contain a certain number of elements from H.

Since there are ∼ N rows, and the total number of elements of H is ∼ N^{2}, we see that each row contains ∼ N on the average. However, it is not necessarily the case that every row contains ∼ N elements of H; there might be a few rows which contain far fewer. However, such rows, by definition, do not contain many elements of H. Indeed, by the popularity argument (Q2), if we throw away all the unpopular rows (those rows which only have ≪ N elements of H), then one still retains a large fraction of H (and in particular, we still have ∼ N^{2} elements of H). Since each row can contain at most O(N) elements from H, the number of rows remaining must still be comparable to N. Thus one can always refine things a little bit so that all the rows become popular.

One can similarly throw away the unpopular columns and ensure that all the columns are popular, while still retaining a large fraction of H. Unfortunately, it is not so easy to simultaneously ensure that the rows and columns are popular, because the operation of throwing away unpopular rows may turn previously popular columns unpopular, and vice versa. However, we always have the freedom to make either the rows popular, or the columns popular, depending on which is more convenient at the time.

By doing this, one can modify the previous Balog-Szemerédi argument to retain a large portion of a reference set H:

Theorem 3.1 (Modified Balog-Szemerédi theorem). Let N be a large integer, and let A and B be finite subsets of an abelian group Z such that |A| ∼ |B| ∼ N. Suppose also that there is a refinement G ⊆ A × B of A × B such that the differences of a − b are small:

|{a − b : (a, b) ∈ G}| ≲ N.

Suppose also we have another refinement H ⊆ A × B (so that |H| ∼ N^{2}). Then we can find refinements A′, B′ of A and B respectively such that

|A′ − B′| ≲ N

and also

|H ∩ (A′ × B′)| ∼ N^{2}.

Note that if one sets H := A × B then one gets the ordinary Balog-Szemerédi theorem. The proof of this theorem is almost the same as that of the usual Balog-Szemerédi, however every time one prepares to pass from A or B to a refinement of A or B, one must make sure that either all the columns are popular or all the rows are popular (so that the refinement captures most of H). We leave the actual verification of this modified version to Q4.

A more quantitative version is available. The following bound was proven by Bourgain [2], using the above arguments:

Theorem 3.2. [2] Let N be a large integer, and let A and B be finite subsets of an abelian group Z such that |A| ∼ |B| ∼ N. Suppose also that there is a set H ⊆ A × B of cardinality

|H| ≥ N^{2}/K

whose sum set is small:

|{a + b : (a, b) ∈ H}| ≤ N.

Then we can find subsets A′, B′ of A and B respectively such that

|H ∩ (A′ × B′)| ≳ K^{−9}N^{2}.

and also

|A′ − B′| ≲ K^{13}N^{−1}|H ∩ (A′ × B′)|.

Note that the existence of this set H with small sumset implies the existence of the set G with small difference set, by the argument in the introduction.

Now we apply this Theorem to Kakeya sets. These sets can be studied both in Euclidean space or in finite fields; for simplicity we treat the finite field case (which has fewer technicalities).

Let F be a finite field (e.g. F := Z/pZ for some prime p), and let n ≥ 2 be an integer, thus F^{n} is vector space over F. We think of n as being fixed, but |F | as being large; our implicit constants may depend on n but not on F. A line in F^{n} is any set l of the form

l = {x + tv : t ∈ F }

where x ∈ F^{n} and v ∈ F^{n}\{0}; we refer to v as the direction of l (though this direction is only defined up to scalar multiplication by invertible elements of F, thus there are about |F |^{n−1} possible distinct directions). A Besicovitch set in F^{n} is said to be any set E ⊆ F^{n} which contains a line in every direction.

The finite field Kakeya set conjecture asserts that one has the bound

|E| ≥ c(n, ε)|F |^{n−ε}

for every ε > 0 and some c(n, ε) > 0 independent of |F |; thus Besicovitch sets are conjectured to fill up practically all of F^{n}. This conjecture is known to be true in two dimensions, but is not known in higher dimensions; however, partial bounds exist. For instance, here is an easy estimate:

Proposition 3.3. Every Besicovitch set E in F^{n} has cardinality

|E| ≳ |F |^{(n+1)/2}.

Proof Fix the Besicovitch set E. We may assume that F is large (actually we just need |F | ≥ 4) since the claim is trivial otherwise.

For every t ∈ F, consider the “horizontal plane” F^{n−1} × {t}, and let E_{t} denote the “horizontal slice”

E_{t} := E ∩ (F^{n−1} × {t}).

Clearly we have

∑_{t∈F} |E_{t}| = |E|

so the average size of |E_{t}| is |E|/|F |. Indeed, from Chebyshev’s inequality we have

|{t ∈ F : |E_{t}| ≥ 2|E|/|F |}| ≤ |F |/2

and hence we have at least |F |/2 values of t for which |E_{t}| ≤ 2|E|/|F |. In particular, we have at least two such values of t. By an affine transformation, we may assume those values are 0 and 1, thus

|E_{0}|, |E_{1}| ≤ 2|E|/|F |.

Now consider the lines in E. For every “velocity” w ∈ F^{n−1}, there must be a line l_{w} with direction (1, w) that lies in E. This line must intersect E_{0} at some point a(w) ∈ E_{0}, and intersect E_{1} at some other point b(w) ∈ E_{1}, so that b(w) − a(w) = (1, w). Thus to each w ∈ F^{n−1} we can associate a pair (a(w), b(w)) ∈ E_{0} × E_{1} of points, so that the line between them lies in E and has direction (1, w). But since two points determine at most one line, all these pairs are distinct. Thus if we let H be the set of all such pairs, we have |H| = |F |^{n−1}. But we also have the trivial bound

|H| ≤ |E_{0} × E_{1}| = |E_{0}||E_{1}| ≲ (|E|/|F |)^{2}.

Combining the two bounds we get |E| ≳ |F |^{(n+1)/2} as desired.

We now use Bourgain’s version of the Balog-Szemerédi theorem to improve this a bit for large dimension n, though we will have to assume F has characteristic greater than 2. (The characteristic of a finite field F is the prime p such that px = 0 for all x ∈ F).

Proposition 3.4. Let F have characteristic greater than 2. Every Besicovitch set E in F^{n} has cardinality

|E| ≳ |F |^{(13n+12)/25}.

Proof Again, we take |F | large, and consider the slices E_{t}. By Chebyshev we have

|{t ∈ F : |E_{t}| ≥ 10|E|/|F |}| ≤ |F |/10.

In particular, we can find a non-trivial arithmetic progression a, a + r, a + 2r of length 3 such that |E_{a}|, |E_{a+r}|, |E_{a+2r}| ≤ 10|E|/|F |. (Indeed, we just pick a and r randomly, and we will have this happening with at least a 70% chance). By an affine transformation (using the assumption that the characteristic is greater than 2) we may set a := 0 and r := 1/2. Thus we have |E_{0}|, |E_{1/2}|, |E_{1}| ≤ N, where we set N := 10|E|/|F |.

As before, for every velocity w ∈ F^{n−1} we have a pair (a(w), b(w)) in E_{0} × E_{1}, such that b(w) − a(w) = (1, w) and the line between a(w) and b(w) lies in E. In particular, the midpoint (a(w) + b(w))/2 lies in E_{1/2}. Thus, if we let G ⊆ E_{0} × E_{1} be the set of pairs of the form (a(w), b(w)), then |G| = |F |^{n−1}, and in fact

|{b − a : (a, b) ∈ G}| = |F |^{n−1}

(since all the differences in G are distinct), while

|{b + a : (a, b) ∈ G}| = |E_{1/2}| ≤ N.

Write K := N^{2}/|F |^{n−1}, so that |G| = N^{2}/K. Now we apply Bourgain’s version of the Balog-Szemerédi theorem, with H replaced by G, to obtain sets A′ ⊆ E_{0} and B′ ⊆ E_{1} such that

|A′ − B′| ≲ K^{13}N^{−1}|G ∩ (A′ × B′)|.

However, since all the differences in G are distinct, we have

|G ∩ (A′ × B′)| ≤ |A′ − B′|

which implies that

K^{13}N^{−1} ≲ 1

which (after some algebra) implies that N^{25/13} ≳ |F |^{n−1}, and hence that |E| ≳ |F |^{(13n+12)/25}.

4. Another approach to the Kakeya problem

The material here is only a brief taste of what goes into the Kakeya problem. For a more thorough discussion of the Kakeya problem and its connection to arithmetic combinatorics, see [7].

While the Balog-Szemerédi theorem has many uses (in particular it is used in Gowers proof of Szemerédi’s theorem, to be covered in a later set of notes), it is not the most efficient tool to attack the Kakeya problem. One can improve upon the above result by dealing with the slices E_{t} and the set G directly.

To simplify the discussion, let us assume for the moment that the slices E_{t} are evenly distributed, so each slice has cardinality comparable to its average value N := |E|/|F |. Also write Z := F^{n}. Then, as in the proof of Proposition 3.4, we have a set G ⊆ Z × Z of cardinality |G| = |F |^{n−1} whose differences b − a are all distinct, but whose sums are all small

|{a + b : (a, b) ∈ G}| ≤ |E_{1/2}| ≲ N.

In other words, we have

|π_{+}(G)| ≲ N.

More generally, given any slice E_{t} with t ≠ 0, we have

|{(1 − t)a + tb : (a, b) ∈ G}| ≤ |E_{t}| ≲ N

and so if we define π_{r}(a, b) := a + rb for any r ∈ F, we have

|π_{t/(1−t)}(G)| ≲ N.

Thus almost all of the arithmetic projections of G are small (of size O(N)), except for the projection π_{−1}, which is large, because of the distinct differences property:

|π_{−1}(G)| = |G| = |F |^{n−1}.

Our task is to get a lower bound for |E| in terms of |F |, or - what amounts to the same thing - getting an upper bound for |F | in terms of N. This leads to the following question: if we have upper bounds on various projections π_{r}(G) of a set G, does this imply upper bounds on the size of π_{−1}(G)? Well, have the obvious bound

|π_{−1}(G)| ≤ |G| ≤ |π_{0}(G) × π_{∞}(G)| = |π_{0}(G)||π_{∞}(G)|

where we adopt the convention π_{∞}(a, b) := b. So if we have |π_{0}(G)|, |π_{∞}(G)| ≲ N, then |G| ≲ N^{2}; combining this with the formula N = |E|/|F | we get the bound |E| ≳ N^{(n+1)/2}, which we obtained before.

The argument in Proposition 3.4 implies the following improvement to this trivial bound:

Proposition 4.1. Let G ⊂ Z ×Z be a set such that |π_{0}(G)|, |π_{1}(G)|, |π_{∞}(G)| ≲ N. Then |π_{−1}(G)| ≲ N^{2−1/13}.

This corresponds to the numerology |E| ≳ N^{(13n+12)/25}, as discussed earlier. The proof of this Proposition is almost identical to that in Proposition 3.4 (note that we can assume that π_{−1} is injective on G, by removing redundant elements of G if necessary).

We can improve this bound a bit (at the cost of requiring one more projection), by using a somewhat different argument than that used to prove the Balog-Szemerédi theorem.

Proposition 4.2. [5] Let G ⊂ Z×Z be a set such that |π_{0}(G)|, |π_{1}(G)|, |π_{2}(G)|, |π_{∞}(G)| ≲ N. Then |π_{−1}(G)| ≲ N^{2−1/4}.

This bound then leads to the improved bound |E| ≳ N^{(4n+3)/7} for Besicovitch sets when the characteristic is greater than 3.

Proof We think of G as living on a two-dimensional space Z × Z. We shall construct various geometric objects in this space. We may of course assume that π_{−1} is injective on G, so that we just need to bound |G|.

Define a vertical line segment to be a pair (g, g′) ∈ G × G such that π_{0}(g) = π_{0}(g′); we abuse notation and write write π_{0}((g, g′)) for π_{0}(g) = π_{0}(g′). Let V be the set of all vertical line segments. By Cauchy-Schwarz (Q1) we have

|V | ≳ |G|^{2}/N.  (1)

We define a new relation ∼_{0} by setting v_{1} ∼_{4} v_{2} if v_{1} and v_{2} have the same value of π_{2} ⊗ π_{∞}. By Cauchy-Schwarz (Q1) we have

|{(v_{1}, v_{2}) ∈ V × V : v_{1} ∼_{0} v_{2}}| ≳ |V |^{2}/N^{2} ≳ |G|^{4}/N^{4}

by (1).

We will complement this lower bound with an upper bound

|{(v_{1}, v_{2}) ∈ V × V : v_{1} ∼_{0} v_{2}}| ≲ N^{3}

which will give |G| ≲ N^{2−1/4}. This is better than the trivial bound of N^{4} (which can be obtained, e.g. by specifying four projections of the four vertices of the trapezoid formed by v_{1}, v_{2}. The key is to use the injectivity of π_{−1}, and more precisely the identity

π_{−1}(g′_{2}) = −π_{1}(g′_{1}) + 2π_{1}(g_{2}) − 2π_{∞}(g_{1}).

Thus if one specifies π_{1}(g′_{1}), π_{1}(g_{2}), and π_{∞}(g_{1}), then one also specifies π_{−1}(g′_{2}), hence g′_{2} (by injectivity of π_{−1}), which then together with π_{1}(g_{2}) gives g_{2}, which together with π_{∞}(g_{1}) gives g_{1}, which together with π_{1}(g′_{1}) gives g′_{1}. Thus (v_{1}, v_{2}) is completely determined by the three projections π_{1}(g′_{1}), π_{1}(g_{2}), and π_{∞}(g_{1}), and the upper bound of O(N^{3}) follows.

If we are allowed to use more projections than π_{0}, π_{1}, π_{2}, π_{∞}, then we can improve the gain 1/4 in N^{2−1/4} somewhat; the record to date is N^{2−0.325...}, using a very large number of slices (and requiring the characteristic of F to be large) [6]. If we could get down to N^{1+ε} for any ε then we would have proven the Kakeya conjecture (not just in finite fields, but also in Euclidean space; see Q5).

If one doesn’t wish to involve the projection π_{2}(G), the results we have are weaker:

Proposition 4.3. [5] Let G ⊂ Z ×Z be a set such that |π_{0}(G)|, |π_{1}(G)|, |π_{∞}(G)| ≲ N. Then |π_{−1}(G)| ≲ N^{2−1/6}.

This bound then leads to the improved bound |E| ≳ N^{(6n+5)/11} for Besicovitch sets when the characteristic is greater than 2.

Proof We use the same vertical line segments V as before. Again we assume π_{−1} is injective on G.

Now we define some relations between vertical line segments. If v_{1} = (g_{1}, g′_{1}) and v_{2} = (g_{2}, g′_{2}) are vertical line segments, we set v_{1} ∼_{1} v_{2} if π_{∞}(g_{1}) = π_{∞}(g_{2}) and π_{∞}(g′_{1}) = π_{∞}(g′_{2}) (i.e. v_{1} and v_{2} form a rectangle). Equivalently, v_{1} ∼_{1} v_{2} if v_{1} and v_{2} have the same image under π_{∞} ⊕ π_{∞} : V → π_{∞}(G) × π_{∞}(G).

Similarly, we define a relation ∼_{2} on vertical line segments by setting v_{1} ∼_{2} v_{2} if v_{1} and v_{2} have the same image under π_{1} ⊕ π_{1} (so v_{1} and v_{2} form a parallelogram), and finally define v_{1} ∼_{3} v_{2} if v_{1} and v_{2} have the same inage under π_{1} ⊕ π_{∞} (so v_{1} and v_{2} form a certain type of trapezoid).

Heuristically speaking, given two randomly selected vertical line segments v_{1}, v_{2}, the probability that v_{1} ∼_{1} v_{2} should be about 1/N^{2}, since the image of the map π_{1} ⊕ π_{1} has cardinality O(N^{2}). Similarly for ∼_{2} and ∼_{3}. Thus, if we pick four vertical line segments at random, v_{1}, v_{2}, v_{3}, v_{4}, the probability that

v_{1} ∼_{1} v_{2} ∼_{2} v_{3} ∼_{3} v_{4}

should be about 1/N^{6}, and so the number of such quadruplets should be about |V |^{4}/N^{6}. In general, we have this as a lower bound:

|{(v_{1}, v_{2}, v_{3}, v_{4}) ∈ V^{4} : v_{1} ∼_{1} v_{2} ∼_{2} v_{3} ∼_{3} v_{4}}| ≳ |V |^{4}/N^{6};

this is part of an abstract combinatorial lemma, see Q6.

We now claim an upper bound

|{(v_{1}, v_{2}, v_{3}, v_{4}) ∈ V^{4} : v_{1} ∼_{1} v_{2} ∼_{2} v_{3} ∼_{3} v_{4}}| ≲ |V |N^{2};

combining this with the previous bound and (1) we obtain the desired bound on |G| after some algebra. The point of this upper bound |V |N^{2} is that it improves somewhat on the trivial bound on |V |N^{3} (since one can completely specify a quadruple (v_{1}, v_{2}, v_{3}, v_{4}) in the above set by first specifying v_{1}, then (say) specifying π_{0}(v_{2}), π_{0}(v_{3}), and π_{0}(v_{4})). Of course, to do so we have to use our hypothesis that G has distinct differences (i.e. π_{−1} is injective on G). Basically, the idea is to use this injectivity to cut down the number of degrees of freedom inherent in this system (v_{1}, v_{2}, v_{3}, v_{4}) of vertical line segments.

Write v_{j} = (g_{j}, g′_{j}) for j = 1, 2, 3, 4. There are two observations. The first is that v_{1}, v_{2}, v_{3} all have the same length:

g_{1} − g′_{1} = g_{2} − g′_{2} = g_{3} − g′_{3}.

In particular, if one specifies v_{1}, then this already fixes the length of v_{2} and v_{3}.

The second observation is that the length of v_{3}, combined with the projections π_{0}(v_{3}) and π_{∞}(g_{4}), determines the projection π_{−1}(g′_{4}) by the identity

π_{−1}(g′_{4}) = π_{∞}(g_{4}) − π_{0}(v_{3}) − (g_{3} − g′_{3}).

Thus if one specifies v_{1}, π_{0}(v_{3}), and π_{∞}(g_{4}), this determines π_{−1}(g′_{4}). But since π_{−1} is injective, this determines g′_{4}; this, together with π_{∞}(g_{4}) determines v_{4}. This, together with π_{0}(v_{3}), determines v_{3}; and this together with v_{1} determines v_{2}. Thus (v_{1}, v_{2}, v_{3}, v_{4}) is completely determined by the three parameters v_{1}, π_{0}(v_{3}), π_{∞}(g_{4}), which explains the upper bound of |V |N^{2}.

For future application we note an extension of this Proposition, in which we impose some precise control on the multiplicity of π_{−1}.

Proposition 4.4. [5] Let G ⊂ Z ×Z be a set such that |π_{0}(G)|, |π_{1}(G)|, |π_{∞}(G)| ≲ N. Suppose also that π_{−1} has multiplicity exactly K on G, in the sense that

|{x ∈ G : π_{−1}(G) = y}| = K

for all y ∈ π_{1}(G). Then |π_{−1}(G)| ≲ N^{2−1/6}K^{−5/6}.

We leave the proof of this Proposition (which is a mild generalization of the previous one) to Q9.

There is however a limit as to how far these methods can go if we refuse to admit too many slices. For instance, the following argument of Ruzsa shows that the 1/6 in the above estimate cannot be improved to beyond 0.20824 …:

Proposition 4.5. Let m be a large number, and let N := (27/4)^{m}. There exists a torsion-free abelian group Z and a G ⊆ Z × Z such that

|π_{0}(G)|, |π_{1}(G)|, |π_{2}(G)|, |π_{∞}(G)| ≲ N

but

|π_{−1}(G)| ≳ 27^{m} = N^{log(27)/ log(27/4)} = N^{2−0.20824...}.

Proof Let m be a large integer. We take Z = Z^{3m}, the space of 3m-tuples of integers. Let A ⊂ Z denote the space of 3m-tuples t which consist of 2m zeroes and m ones; clearly

N := |A| = \frac{(3m)!}{m!(2m)!} ≈ (27/4)^{m} = N,

where we have used Stirling’s formula n! ∼ n^{1/2}(n/e)^{n} (see Q8).

Now let G ⊂ A × A denote the space of pairs (t_{1}, t_{2}) of 3m-tuples, such that the m ones in t_{1} occupy a completely disjoint set of co-ordinates than the m ones in t_{2}. Thus

|G| = \frac{(3m)!}{m!m!m!} ≈ (27)^{m} = N^{log(27)/ log(27/4)}.

One can easily check that π_{0}, π_{1}, π_{∞} all map G to a space isomorphic to A, and so we are done.

5. Application to multilinear convolution-type operators

This section is set in the continuous case R, and so we now use |E| to denote Lebesgue measure rather than cardinality of E.

We now present an argument of Michael Christ [3] which uses Proposition 4.4 to give a non-trivial estimate for the multilinear convolution-type operator T, defined by

T (f, g, h)(x) := ∫R f(x + t)g(x − t)h(t) dt,

where f, g, h are functions on the real line. (If we set h(t) := 1/t then this is the famous bilinear Hilbert transform, but the results here will not address this important operator).

To simplify the discussion, let us assume that f, g, h are characteristic functions

f = χ_{F} , g = χ_{G}, h = χ_{H}

and F, G, H have Lebesgue measure O(1). Then the function T (f, g, h)(x) is just

T (f, g, h)(x) = ∫R χ_{F} (x + t)χ_{G}(x − t)χ_{H}(t) dt = |H ∩ (x − G) ∩ (F − x)|.

In particular, T (f, g, h) is non-negative and uniformly bounded. Furthermore, since T (f, g, h) is pointwise dominated by χ_{F} ∗ χ_{G}(2x), it is in L^{1}. In particular, we have the distributional bounds

|{T (f, g, h) ≥ λ}| ≲ λ^{−1}

for 0 < λ ≲ 1.

One can ask the question as to whether these bounds can be improved. Interestingly, one can do so by means of the argument in Proposition 4.4, with the same gain of 1/6:

Proposition 5.1. [3] For 0 < λ ≲ 1, we have

|{T (f, g, h) ≥ λ}| ≲ λ^{−1+1/6}

Fix λ. First of all, we observe by a standard limiting argument that we may assume that F, G, H are all unions of intervals of some very small length 0 < δ ≪ λ. Next, we observe the following continuous version of Proposition 4.4:

Proposition 5.2. [5] Let G ⊂ R × R be a set consisting of unions of δ × δ squares such that |π_{0}(G)|, |π_{1}(G)|, |π_{∞}(G)| ≲ N. Suppose also that π_{−1} has fibers of measure ∼ K on G, in the sense that

|{x ∈ G : π_{−1}(G) = y}| ∼ K

for all y ∈ π_{−1}(G). Then |π_{−1}(G)| ≲ N^{2−1/6}K^{−5/6}.

Indeed, one can rescale δ to be 1 (replacing N by N/δ and K by K/δ, replace the set G with a discretized variant on Z × Z, and apply Proposition 5.2. (We leave this as an exercise).

To apply this lemma, what we do is that we let E be the set

E := {x ∈ R : T (f, g, h) ≥ λ} + O(δ),

and for each x ∈ E we choose a subset T_{x} of H ∩(x−G)∩(F −x)+O(δ) of measure ∼ λ. We then set

G := {(t + x, t − x) : x ∈ E, t ∈ T_{x}}.

Then G is essentially the union of δ × δ-squares, and one has the estimates

|π_{0}(G)|, |π_{1}(G)|, |π_{∞}(G)| ≲ 1

by the hypotheses on F, G, H. Furthermore we have

|{x ∈ G : π_{−1}(G) = y}| ∼ λ

for all y ∈ π_{−1}(G). Thus by Proposition 5.2 we have

|π_{−1}(G)| ≲ λ^{−5/6}

and the claim follows.

One can modify Proposition 4.5 to show that one cannot improve the 1/6 in this estimate to beyond 0.20824 . . .. Also, if one replaces T by the superficially similar operator

T (f, g, h)(x) := ∫R f(x + t)g(x − \sqrt{2}t)h(t) dt,

(or indeed replacing \sqrt{2} by any other irrational number) then there is no improvement over the trivial bound of λ^{−1}). Intuitively, this is because irrational projections cannot be used in arithmetic ways to control the size of rational projections; the actual construction however is a bit complex, and can be found in [3].

6. Exercises

• Q1. Show that if there is a map f : X → Y from one finite non-empty set X to another Y, then we have

|\{(x, x′) ∈ X : f(x) = f(x′)\}| ≥ \frac{|X|^{2}}{|Y |} .

If |X| ≫ |Y |, strengthen this to

|\{(x, x′) ∈ X : f(x) = f(x′) and x ≠ x′\}| ≳ \frac{|X|^{2}}{|Y |} .

We refer to this estimate as the Cauchy-Schwarz estimate.

• Q2. Let f : X → Y be a map from one finite non-empty set to another. Call an element y ∈ Y popular if

|\{x ∈ X : f(x) = y\}| ≥ \frac{1}{2} \frac{|X|}{|Y |},

i.e. y receives at least half of the expected number of points from X. Then show that

|\{x ∈ X : f(x) is popular \}| ≥ \frac{1}{2}|X|.

In other words, over half of the points in X have popular images under f. (We refer to this result as the popularity argument). Can you see how Q2 can be used to imply (a slightly weaker form of) the result in Q1?

• Q3. Let N be a large integer, and let A and B be two sets of cardinality N. Show that there exists a set G ⊂ A × B of cardinality ∼ N^{2} (i.e. a refinement of A × B) which does not contain any Cartesian product of the form A′ × B′ for any refinements A′, B′ of N. (Hint: There are deterministic constructions, but a random construction is simplest: let G be constructed randomly by permitting each pair (a, b) to lie in G with probability 1/2, with all the probabilities being independent. Show that for each A′, B′, the probability that G contains A′ ×B′ is extremely small - of the order of e^{−CN^{2}} or so, while the number of sets A′, B′ are only e^{CN} or so).

• Q4*. Prove the (non-quantitative) modified Balog-Szemerédi theorem.

• Q5*. Let n ≥ 2. A Besicovitch set E in R^{n} is a compact set which contains a unit line segment in every direction; thus for every unit vector ω there exists a line segment l_{ω} in E of length 1 and direction ω. For any δ > 0, let N_{δ}(E) be the δ-neighborhood of E, and let |N_{δ}(E)| be the n-dimensional volume of this δ-neighborhood.

(a) Prove the bound

|N_{δ}(E)| ≥ c(E, n)δ^{(n−1)/2},

where the constant c(E, n) depends on E and n but not δ. (This implies that the Minkowski dimension of E is at least (n + 1)/2).

(b) Use Bourgain’s argument to improve this bound to

|N_{δ}(E)| ≥ c(E, n)δ^{12(n−1)/25}.

(This implies that the Minkowski dimension of E is at least (13n + 12)/25). (c) Use the Katz-Tao argument to improve this to

|N_{δ}(E)| ≥ c(E, n)δ^{4(n−1)/7}.

(This implies that the Minkowski dimension of E is at least (4n + 3)/7).

Q6. Let f_{1} : V → X_{1}, f_{2} : V → X_{2}, f_{3} : V → X_{3} be functions from one finite nonempty set to another. Show that

|\{(v_{1}, v_{2}, v_{3}, v_{4}) ∈ V^{4} : f_{1}(v_{1}) = f_{1}(v_{2}); f_{2}(v_{2}) = f_{2}(v_{3}); f_{3}(v_{3}) = f_{3}(v_{4})\}| ≳ \frac{|V |^{4}}{|X_{1}||X_{2}||X_{3}|}.

Hint: Apply the popularity argument in Q2 three times, each time refining V slightly. Note that the right-hand side is consistent with the probabilistic intuition that two random elements of X_{1} should be equal with probability 1/|X_{1}|, etc.

Q7. Use the Cartesian product trick (cf. the proof of Plünnecke’s theorem in Week 1 notes) to show that the ≲’s in the Katz-Tao estimate can be replaced by ≤’s. More precisely, show that if |π_{0}(G)|, |π_{1}(G)|, |π_{2}(G)|, |π_{∞}(G)| ≤ N, then |π_{−1}(G)| ≤ N^{2−1/4}.

Q8. Prove Stirling’s formula n! ∼ n^{1/2}(n/e)^{n} by comparing the sum ∑_{j=1}^{n} log j with the integral ∫_{1}^{n} log x dx (using for instance the trapezoid rule).

Q9. Prove Proposition 4.4, and then deduce Proposition 5.2.

References

[1] A. Balog, E. Szemerédi, A statistical theorem of set addition, Combinatorica, 14 (1994), 263–268.

[2] J. Bourgain, On the dimension of Kakeya sets and related maximal inequalities, GAFA 9 (1999), 256–282.

[3] M. Christ, On certain elementary trilinear operators, Math. Research Letters, 8 (2001), 43–56.

[4] T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, GAFA 8 (1998), 529–551.

[5] N. Katz, T. Tao, Bounds on arithmetic progressions, and applications to the Kakeya conjecture, Math. Res. Letters 6 (1999), 625–630.

[6] N. Katz, T. Tao, New bounds for Kakeya problems, to appear, J. d’Analyse Jerusalem.

[7] T. Tao, Edinburgh lecture notes on the Kakeya problem, www.math.ucla.edu/∼tao/preprints/Kakeya.html

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu