LECTURE NOTES 6 FOR 254A

TERENCE TAO

1. Sums and products

We now leave the topic of arithmetic progressions, and return to topics closer to those studied upon at the beginning of the course, where we studied the relationship between such sets as A + A and A − A. This time, however, we shall look at the sets A + A and A · A, where

A · A = {ab : a, b ∈ A}.

Note that if one wanted to study A · A and A/A (where A does not contain 0, of course), one could just take logarithms and reduce things to a problem and sums and differences. But to study A + A and A · A simultaneously is a different matter, and the theory here is much less well understood.

From Freiman’s theorem we expect |A + A| ∼ |A| only when A resembles an arithmetic progression; similarly we expect |A · A| ∼ |A| only when A resembles a geometric progression. Since arithmetic progressions and geometric progressions do not resemble each other, it thus seems reasonable to expect at least one of |A + A| and |A · A| to be large, at least when A is a subset of R. This is indeed the case; the best known bound on this is Elekes’s theorem max(|A + A|, |A · A|) ≳ |A|^{5/4}, which we shall prove shortly.

Interestingly, the geometry of the plane now begins to play a role. The reason can already be seen in the familiar equation y = mx + b for a line in the plane; this is an equation which involves both multiplication and addition, which is exactly the problem encountered above.

To address the geometry of the plane, we first need to understand the topology of the plane - and in particular, the concept of crossing numbers. This will be handled next.

2. Crossing numbers

Let G = (V, E) be a finite undirected, multiplicity-free graph with a collection V of vertices, and E of edges. A drawing ϕ(G) of G is a map ϕ on (V, E) which maps each vertex v in V to a point ϕ(v) in R^{2}, while mapping each edge e in E, with vertices v_{1} and v_{2}, to an (open) curve ϕ(e) in R^{2} with vertices ϕ(v_{1}) and ϕ(v_{2}). We say that a drawing of G is proper if (a) the points ϕ(v) are all distinct, (b) the (open) curves ϕ(e) are simple and do not pass through any points in ϕ(V), (c) any two distinct open curves ϕ(e), ϕ(e′) only intersect in a finite number of points, (d) any two distinct open curves with a shared endpoint are disjoint. It is clear that every finite graph G has at least one drawing which is proper (map the vertices to randomly selected points, and the edges to line segments). Given any proper drawing ϕ(G) of a graph G, define the crossing number cr(ϕ(G)) to be the number of times the edges ϕ(e), ϕ(e′) cross each other, i.e.

cr(ϕ(G)) = ∑_{{e,e′}∈E×E:e≠e′} |ϕ(e) ∩ ϕ(e′)|.

Thus cr(ϕ(G)) is a non-negative integer. We define the crossing number cr(G) of a graph G to be

cr(G) := inf_{ϕ} cr(ϕ(G)),

i.e. the minimal crossing number over all proper drawings ϕ of G.

We now pursue the question of how to estimate cr(G), especially from below. Clearly we have cr(G′) ≤ cr(G) if G′ is a subgraph of G; we can convert this monotonicity property into a strict monotonicity property if cr(G) is positive.

Lemma 2.1. Let G = (V, E) be a graph such that cr(G) is positive. Then there exists an edge e in E such that cr(G) ≥ cr(G − {e}) + 1.

Proof Let M := inf_{e∈E} cr(G−{e}), and let ϕ be a proper drawing of G. We know that cr(ϕ(G)) is positive; we need to show that it is at least M + 1.

Since cr(ϕ(G)) is positive, we have distinct edges ϕ(e) and ϕ(e′) which intersect at least 1. But we know that cr(ϕ(G − {e}) intersects at least M times. The claim follows.

Next, we give a simple condition to show when cr(G) is positive.

Lemma 2.2. If |E| > 3|V | − 6, then cr(G) is positive.

Proof Suppose for contradiction that we had a graph G and a drawing ϕ with no crossings, but for which |E| > 3|V |−6. The drawing ϕ(G) subdivides the plane into a collection F of open regions (including one infinite region). By Euler’s formula we have |V | − |E| + |F | = 2. But also, since each edge is adjacent to two faces, and each face is adjacent to at least three edges, we have 3|F | ≤ 2|E|. Combining the two equations we obtain |E| ≤ 3|V | − 6, contradiction.

Combining these two Lemmas together we immediately obtain the bound

cr(G) ≥ max(|E| − 3|V | + 6, 0).

Now we improve this estimate using randomization arguments. Let G = (V, E) be a graph, and let 0 < p < 1 be a parameter to be chosen later. Let G′ = (V′, E′) be the (random) sub-graph of G formed by allowing each vertex v ∈ V to lie in V′ with independent probability p, and let e ∈ E lie in E′ if both its vertices lie in V′ (so each edge has a probability p^{2} of occurring in E′, in particular we have E(|E′|) = p^{2}|E|. Let ϕ(G) be a drawing of G, which of course induces a drawing ϕ(G′) of G′. Each crossing of ϕ(G) requires two distinct edges arising from four distinct points, and thus has a probability p^{4} of also occurring in ϕ(G′). These events are not independent, but expectation is still linear, so we have

E(cr(ϕ(G′)) = p^{4}cr(G).

On the other hand, using the above bound we have

E(cr(ϕ(G′)) ≥ E(|E′| − 3|V | + 6) = E(|E′|) − 3E(|V |) + 6 = p^{2}|E| − 3p|V | + 6.

Thus we have the estimate

cr(G) ≥ \frac{p^{2}|E| − 3p|V | + 6}{p^{4}}.

If |E| ≥ 5|V |, then we can pick p = 4|V |/|E|, and obtain the crossing number bound

cr(G) ≳ |E|^{3}/|V |^{2} when |E| ≥ 5|V |.

This bound is quite sharp (see Q1). It can be rewritten as

|E| ≲ cr(G)^{1/3}|V |^{2/3} + |V |.  (1)

3. The Szemerédi-Trotter theorem

We now use the crossing number estimate to obtain a basic estimate on incidences between points and lines.

Let P be a finite collection of points in the plane, and let L be a finite collection of lines. We consider the quantity I(P, L) := |{(p, l) ∈ P × L : p ∈ l}|, the set of incidences between P and L.

Form the graph G whose vertices V are the set P of points, and whose edges E are the bounded line segments in L formed by any two points in P. Clearly |V | = |P |. As for |E|, note that

|E| = ∑_{l∈L}(|P ∩ l| − 1)_{+} ≥ ∑_{l∈L} |P ∩ l| − |L| = I(P, L) − |L|.

On the other hand, since each two lines in L intersect in at most one point, we have cr(G) ≤ |L|^{2}. Applying (1), we thus see that

I(P, L) ≲ |L|^{2/3}|P |^{2/3} + |P | + |L|.  (2)

This is the Szemerédi-Trotter theorem (which initially had a much longer proof [16]!). This bound is sharp (Q2).

4. Elekes’s theorem

Now we can prove a bound on A + A and A · A, when A is a finite subset of the reals R. Let P be the set

(A + A) × (A · A),

and let L consist of all the lines {(x, y) : y = a(x − a′)} where a, a′ ∈ A. Then |P | = |A+A||A·A| and L = |A|^{2}. Also, each line L is incident to at least |A| points in P (why?), so I(P, L) ≥ |L||A| = |A|^{3}. From the Szemerédi-Trotter theorem we conclude that

|A|^{3} ≲ |A|^{4/3}|P |^{2/3} + |P | + |A|^{2},

from which we conclude (if |A| ≫ 1; the case |A| ≲ 1 can be dealt with manually) that

|P | ≳ |A|^{5/2},

and thus we obtain Elekes’s theorem [7]

max(|A + A|, |A · A|) ≳ |A|^{5/4}.  (3)

It is not known what the best bound on this quantity is; (3) has not been improved despite the argument being remarkably simple. An old conjecture of Erdös and Szemerédi [9] claims that

max(|A + A|, |A · A|) ≳ |A|^{2−ε},

i.e. either A is almost totally non-closed under addition or totally non-closed under multiplication.

5. The finite field case

Elekes’s theorem showed that when A was a finite subset of R, then there was some significant failure of A to be closed under either addition or multiplication. We could ask whether the same is true in finite fields F. Of course, if A is a subfield of F, then A + A and A · A are both equal to A, so in that case there is no failure of closure under either multiplication or addition. (Of course the crossing number argument relied on Euler’s formula, and thus on the topology of the plane, and so does not work in finite fields).

However, suppose F was a prime finite field F := Z/pZ. Then F has no non-trivial subfields, and so the above counterexample does not apply. In this case we can get a small improvement, though not yet on the level of Elekes’s theorem:

Theorem 5.1. [4] Let F be a finite field of prime order, and let A be a subset of F such that |F |^{δ} < |A| < |F |^{1−δ} for some δ > 0. Then we have max(|A+A|, |A·A|) ≳ |A|^{1+ε} for some ε = ε(δ) > 0.

This theorem requires a certain amount of machinery, though fortunately we have already developed most of it. The idea is to prove by contradiction, assuming that |A+A| and |A·A| are close to |A|, and conclude that A is behaving very much like a subfield of F - enough so that one can do some basic linear algebra, and eventually conclude that |F | is a power of |A| (or more precisely |A′| for some variant A′ of A), a contradiction since |F | is prime.

6. First ingredient: Sum-product estimates

Recall the sum-set estimates from week 1 notes, which said (among other things) that if |A + A| ∼ |A|, then in fact |A ± A ± … ± A| ∼ |A|. Exponentiating this, we see that if A does not contain 0 and |A · A| ∼ |A|, then in fact we have the product-set estimates |A · A · . . . · A/(A · . . . · A)| ∼ |A|.

Now suppose that (to prove Theorem 5.1 by contradiction) we knew that we had both |A + A| ∼ |A| and |A · A| ∼ |A|. Then sum estimates and product estimates allow us to control any expression of A which involves just sums and differences, or just products and quotients. But we do not yet know how to control expressions which involve both, e.g. A · A + A · A. However, it turns out that we can do so if we refine A a little:

Lemma 6.1. [11] Let A be a non-empty subset of F such that

|A + A|, |A · A| ≤ K|A|.

We shall use X ⪅ Y to denote the estimate X ≤ CK^{C}Y. Then there is a subset A′ of A with |A′| ⪆ |A| such that

|A′ · A′ − A′ · A′| ⪅ |A′|.

This only controls one joint expression of A′; we shall control all the others as well in the next section.

To prove Lemma 6.1, we recall Gowers’ quantitative formulation [10] of the Balog-Szemeredi lemma [1]:

Theorem 6.2. [10], [3] Let A, B be finite subsets of an additive group with cardinality |A| = |B|, and let G be a subset of A × B with cardinality

|G| ≈ |A||B|

such that we have the bound

|{a + b : (a, b) ∈ G}| ⪅ |A|.

Then there exists subsets A′, B′ of A and B respectively with |A′| ≥ cK^{−C}|A|, |B′| ≥ cK^{−C}|B| such that

|A′ − B′| ⪅ |A|.

Indeed, we have the stronger statement that for every a′ ∈ A and b′ ∈ B, there are ⪆ |A|^{5} solutions to the problem

a′ − b′ = (a_{1} − b_{1}) − (a_{2} − b_{2}) + (a_{3} − b_{3}); a_{1}, a_{2}, a_{3} ∈ A; b_{1}, b_{2}, b_{3} ∈ B.

Proof (Sketch) Call an element d a popular difference if it can be written in the form a − b for ⪆ |A| pairs (a, b) ∈ A × B. The hypotheses on G ensure that there are ⪆ popular differences. Thus by the construction in previous notes, we can find large subsets A′ and B′ of A and B respectively with size ⪆ |A| such that every element a′ of A′ is aware of every element b′ of B′, thus there are ⪆ |A|^{2} solutions to the problem

a′ − b′ = d_{1} − d_{2} + d_{3}

where d_{1}, d_{2}, d_{3} are popular differences. The claim follows.

Now we can prove Lemma 6.1. Without loss of generality we may assume that |A| ≫ 1 is large, and that 0 ≠ A (since removing 0 from A does not significantly affect any of the hypotheses).

We first observe from Theorem 6.2 that we can find subsets C, D of A with |C|, |D| ≈ |A| such that every element in C − D has ⪆ |A|^{5} representations of the form

a_{1} − a_{2} + a_{3} − a_{4} + a_{5} − a_{6}; a_{1}, …, a_{6} ∈ A.

Multiplying this by an arbitrary element of A·A·A/A·A, we see that every element of (C − D) · A · A · A/A · A has ⪆ |A|^{5} representations of the form

b_{1} − b_{2} + b_{3} − b_{4} + b_{5} − b_{6}; b_{1}, …, b_{6} ∈ A · A · A · A/A · A.

However, by the multiplicative form of sumset estimates, the set A · A · A · A/A · A has cardinality ≈ |A|. Thus by Fubini’s theorem we have

|(C − D) · A · A · A/A · A| ⪅ |A|.  (4)

Now we refine C and D. Since |C|, |D| ≈ |A| and |A · A| ≈ |A|, we have |CD| ≈ |C|, |D|, and hence by the multiplicative form of Theorem 6.2, we can find subsets C′, D′ of C, D with |C′|, |D′| ≈ |A| such that every element in C′D′ has ⪆ |A|^{5} representations in the form

\frac{c_{1}d_{1}c_{3}d_{3}}{c_{2}d_{2}} ; c_{1}, c_{2}, c_{3} ∈ C; d_{1}, d_{2}, d_{3} ∈ D.

Now let c, c′ ∈ C′ and d, d′ ∈ D be arbitrary. By the pigeonhole principle there thus exist c_{2} ∈ C, d_{2} ∈ D such that we have ⪆ |A|^{3} solutions to the problem

cd = \frac{c_{1}d_{1}c_{3}d_{3}}{c_{2}d_{2}} ; c_{1}, c_{3} ∈ C; d_{1}, d_{3} ∈ D.

We can rewrite this as

cd − c′d′ = x_{1} − x_{2} + x_{3} + x_{4}

where

x_{1} = \frac{(c_{1} − d′)d_{1}c_{3}d_{3}}{c_{2}d_{2}}
x_{2} = \frac{d′(c′ − d_{1})c_{3}d_{3}}{c_{2}d_{2}}
x_{3} = \frac{d′c′(c_{3} − d_{2})d_{3}}{c_{2}d_{2}}
x_{4} = \frac{d′c′d_{2}(c_{2} − d_{3})}{c_{2}d_{2}}.

For fixed c, d, c′, d′, c_{2}, d_{2}, it is easy to see that the map from (c_{1}, c_{3}, d_{1}, d_{3}) to (x_{1}, x_{2}, x_{3}, x_{4}) is a bijection. Since all the x_{j} lie in (C − D) · A · A · A/A · A, we thus have ⪆ |A|^{3} ways to represent cd − c′d′ in the form x_{1} − x_{2} + x_{3} − x_{4}, where x_{1}, x_{2}, x_{3}, x_{4} all lie in (C − D) · A · A · A/A · A. By (4) and Fubini’s theorem we thus have

|C′D′ − C′D′| ⪅ |A|.

In particular we have |C′D′| ⪅ |A| ⪅ |C′|, which by the multiplicative form of sumset estimates implies |C′/D′| ≈ |C′|. By considering the fibers of the quotient map (x, y) → x/y on C′ × D′ and using the pigeonhole principle, we thus see that there must be a non-zero field element x such that |C′ ∩ D′x| ≈ |A|. If we then set A′ := C′ ∩ D′x we have |A′A′ − A′A′| ⪅ |A| as desired.

7. Second ingredient: Iterated sum and product set estimates

We now prove the following lemma, which is in the spirit of sum-set estimates:

Lemma 7.1. Let A be a non-empty subset of a finite field F, and suppose that we have the bound

|A · A − A · A| ≤ K|A|

for some K ≥ 1. We adopt the normalization that 1 ∈ A. Then for any polynomial P of several variables and integer coefficients, we have

|P (A, A, …, A)| ≤ CK^{C}|A|

where the constants C depend of course on P.

Proof We need some notation. We say that a set A is essentially contained in B, and write A ⋐ B, if we have A ⊆ X + B for some set X of cardinality |X| ≤ CK^{C}.

We have the following simple lemma of Ruzsa [14]:

Lemma 7.2. Let A and B be subsets of F such that |A+B| ≤ CK^{C}|A| or |A−B| ≤ CK^{C}|A|. Then B ⋐ A − A.

Proof By symmetry we may assume that |A+B| ≤ CK^{C}|A|. Let X be a maximal subset of B with the property that the sets {x + A : x ∈ X} are all disjoint. Since the sets x + A all have cardinality |A| and are all contained in A + B, we see from disjointness that |X||A| ≤ |A + B|, and hence |X| ≤ CK^{C}. Since the set X is maximal, we see that for every b ∈ B, the set b + A must intersect x + A for some x ∈ X. Thus b ∈ x + A − A, and hence B ⊆ X + A − A as desired.

Call an element x ∈ F good if we have x · A ⋐ A − A.

Proposition 7.3. The following three statements are true.

• Every element of A is good.

• If x and y are good, then x + y and x − y is good.

• If x and y are good, then xy is good.

(Of course, the implicit constants in “good” vary at each occurence).

Proof Let us first show that every element of A is good. Since 1 ∈ A, we have

|A.A − A| ≤ |A.A − A.A| ≤ K|A|

and hence by Lemma 7.2

A.A ⋐ A − A  (5)

which implies in particular that every element of x is good.

Now suppose that x and y are good, thus x · A ⋐ A − A and y · A ⋐ A − A. Then

(x + y) · A ⊆ x · A + y · A ⋐ A − A + A − A.

On the other hand, since |A − A| ≤ |A.A − A.A| ≤ K|A|, we have from sumset estimates that

|A − A + A − A + A| ≤ CK^{C}|A|

and hence by Lemma 7.2

A − A + A − A ⋐ A − A.  (6)

Thus by transitivity of ⋐ we have (x + y) · A ⋐ A − A and hence x + y is good. A similar argument shows that x − y is good.

Now we need to show that xy is good. Since x · A ⋐ A − A we have

xy · A ⋐ y · A − y · A.

But since y · A ⋐ A − A, we have

xy · A ⋐ A − A − A + A.

By (6) we conclude that xy is good.

By iterating this proposition we see that for any integer polynomial P, every element of P (A, …, A) is good^{1}.

Write A^{2} := A · A, A^{3} := A · A · A, etc. We now claim inductively that A^{k} ⋐ A − A for all k = 0, 1, 2, 3, . . .. The case k = 0, 1 are trivial, and k = 2 has already been covered by (5). Now suppose inductively that k > 2, and that we have already proven that A^{k−1} ⋐ A − A. Thus

A^{k−1} ⊆ X + A − A

for some set X of cardinality |X| ≤ CK^{C}. Clearly we may restrict X to the set A^{k−1} − (A − A). In particular, every element of X is good. We now multiply by A to obtain

A^{k} ⊆ X · A + A · A − A · A.

Since every element of X is good, and |X| ≤ CK^{C}, we see that X · A ⋐ A − A. By (5) we thus have

A^{k} ⋐ A − A + A − A − (A − A).

But by arguing as in the proof of (6) we have

A − A + A − A − (A − A) ⋐ A − A,

and thus we can close the induction.

1An alternate way to proceed at this point is to show that the number of good points is at most ⪅ N; indeed, it is easy to show that any good point is contained inside (A − A + A − A)/(A − A)

if N is sufficiently large, where we exclude 0 from the denominator A − A of course. We omit the details.

Since A^{k} ⋐ A − A for every k, and A − A ± (A − A) ⋐ A − A by (6), we thus see that every integer combination of A^{k} is essentially contained in A−A. In particular P (A, …, A) ⋐ A − A for every integer polynomial A, and the claim follows.

8. Third ingredient: Expanding sum estimates

The third and final ingredient is a statement of the form that |A + B| can become much larger than |A| or |B| separately. We first recall the Cauchy-Davenport inequality

|A + B| ≥ min(|A| + |B| − 1, |F |)  (7)

for any non-empty subsets A, B of F. If we are allowed to arbitrarily dilate one of the sets A, B then we can improve subtantially on this inequality:

Lemma 8.1. Let A, B be finite non-empty subsets of a finite field F, and lte F^{∗} := F − {0} denote the invertible elements of F. Then there exists ξ ∈ F^{∗} such that

|A + Bξ| ≥ min(\frac{1}{2}|A||B|, \frac{1}{10}|F |).  (8)

Proof We may assume without loss of generality that |A||B| ≤ \frac{1}{2}|F |, since if |A||B| > \frac{1}{2}|F | we may remove some elements from A and B without affecting the right-hand side of (8). Let ξ be an element of F^{∗}. We use the inclusion-exclusion principle^{2} and the invertibility of ξ to compute

|A + Bξ| = | ⋃_{a∈A} a + Bξ|

≥ ∑_{a∈A} |a + Bξ| − \frac{1}{2} ∑_{a,a′∈A:a≠a′} |(a + Bξ) ∩ (a′ + Bξ)|

≥ ∑_{a∈A} |B| − \frac{1}{2} ∑_{a,a′∈A:a≠a′} ∑_{b,b′∈B} δ_{a+bξ,a′+b′ξ}

= |A||B| − \frac{1}{2} ∑_{a,a′∈A:a≠a′} ∑_{b,b′∈B:b≠b′} δ_{ξ,(a−a′)/(b−b′)},

2To verify our use of the principle, suppose an element x lies in N of the sets a+Bξ for some N ≥ 1. Then the sum ∑_{a∈A} |a+Bξ| counts x N times, while the sum ∑_{a,a′∈A:a≠a′} |(a+Bξ)∩(a′+Bξ)| counts x N(N − 1) times. Since N − \frac{N(N−1)}{2} is always less than or equal to 1, the claim follows.

An alternate way to obtain this lemma (which gives slightly worse bounds when |A||B| ≪ |F |, but somewhat better bounds when |A||B| ≫ |F |) is by using the Cauchy-Schwarz inequality ∥χ_{A} ∗ χ_{Bξ}∥_{l^{1}}^{2} ≤ ∥χ_{A} ∗ χ_{Bξ}∥_{l^{2}}|A + Bξ| and again randomizing over ξ.

where δ_{i,j} is the Kronecker delta function. If we average this over all ξ ∈ F_{∗} we obtain

\frac{1}{|F_{∗}|} ∑_{ξ∈F_{∗}} |A + Bξ| ≥ |A||B| − \frac{1}{2} ∑_{a,a′∈A:a≠a′} ∑_{b,b′∈B:b≠b′} \frac{1}{|F | − 1}

≥ |A||B| − \frac{1}{2} \frac{|A|^{2}|B|^{2}}{|F | − 1}

≥ \frac{1}{2}|A||B|

by our hypothesis |A||B| ≤ \frac{1}{2}|F |. The claim (8) then follows by the pigeonhole principle.

9. Proof of Theorem 5.1

We now have all the machinery needed to prove Theorem 5.1. We basically follow the Edgar-Miller approach, see [6]. We write F for Z/qZ, and let F^{∗} := F − {0} be the invertible elements of F. Let δ > 0, and let A be a subset of F such that |F |^{δ} < |A| < |F |^{1−δ}.

Let 0 < ε ≪ 1 be a small number depending on δ to be chosen later. In this section we use X ≲ Y to denote the estimate X ≤ C(δ, ε)Y for some C(δ, ε) > 0. Suppose for contradiction that

|A + A|, |A · A| ≲ |A|^{1+ε};

Then by Lemma 6.1, and passing to a refinement of A if necessary, we may assume that

|A · A − A · A| ≲ |A|^{1+Cε}.

We may normalize 1 ∈ A. By Lemma 7.1 we thus have

|P (A, …, A)| ≲ |A|^{1+Cε}  (9)

for any polynomial P with integer coefficients, where the constants C depend of course on P.

Our first objective is to obtain a linear surjection from A^{k} to F for sufficiently large k:

Lemma 9.1. There exists a positive integer k ∼ 1/δ, and invertible field elements ξ_{1}, …, ξ_{k} ∈ F^{∗}, such that

F = Aξ_{1} + ⋯ + Aξ_{k}.

In other words, we have a linear surjection from A^{k} to F.

Proof Iterating Lemma 8.1 about O(1/δ) times, we obtain ξ_{1}, …, ξ_{k} ∈ F^{∗} such that

|Aξ_{1} + ⋯ + Aξ_{k}| ≥ \frac{|F |}{10}.

The lemma then obtains after O(1) applications of the Cauchy-Davenport inequality (7), increasing k as necessary.

Next, we reduce the rank k of this surjection, at the cost of replacing A by a polynomial expression of A.

Lemma 9.2. Let B be a non-empty subset of F, and suppose k > 1 is such that there is a linear surjection from B^{k} to F. Then there is a linear surjection from B̃^{k−1} to F, where B̃ := B · (B − B) + B · (B − B).

Proof By hypothesis, we have a surjection

B^{k} → F : (a_{1}, …, a_{k}) ↦ ∑_{j≤k} a_{j}ξ_{j}

for some ξ_{1}, …, ξ_{k} ∈ F. Our map cannot be one-to-one, since otherwise

|B|^{k} = |F | (contradicting primarily of |F |).

Thus there are (b_{1}, …, b_{k}) ≠ (b′_{1}, … b′_{k}) ∈ B^{k} with

(b_{1} − b′_{1})ξ_{1} + ⋯ + (b_{k} − b′_{k})ξ_{k} = 0.  (10)

Let b_{k} ≠ b′_{k}. By the surjection property

F = Bξ_{1} + … + Bξ_{k};

since F is a field, we thus have

F = Bξ_{1}(b_{k} − b′_{k}) + ⋯ + Bξ_{k}(b_{k} − b′_{k})

and substituting (b_{k} − b′_{k})ξ_{k} from (10)

F = Bξ_{1}(b_{k} − b′_{k}) + ⋯ + Bξ_{k−1}(b_{k} − b′_{k}) − B(b_{1} − b′_{1})ξ_{1} − ⋯ − B(b_{k−1} − b′_{k−1})ξ_{k−1}

⊂ B̃ξ_{1} + ⋯ + B̃ξ_{k−1}

and the claim follows.

Starting with Lemma 9.1 and then iterating Lemma 9.2 k times, we eventually get a linear surjection from a polynomial expression P (A, …, A) of A to F, and thus

|P (A, …, A)| ≥ |F |.

But this contradicts (9), if ε is sufficiently small depending on δ. This contradiction proves Theorem 5.1.

Remark. Suppose the finite field F did not have prime order. Then the analogue of Theorem 5.1 fails, since one can take A to be a subfield G of F, or a large subset of such a subfield G. It turns out that one can adapt the above argument to show that these are in fact the only ways in which Theorem 5.1 can fail (up to dilations, of course):

Theorem 9.3. Let A be a subset of a finite field F such that |A| > |F |^{δ} for some 0 < δ < 1, and suppose that |A + A|, |A · A| ≤ K|A| for some K ≫ 1. Then there exists a subfield G of F of cardinality |G| ≤ K^{C(δ)}|A|, a non-zero field element ξ ∈ F − {0}, and a set X ⊆ F of cardinality |X| ≤ K^{C(δ)} such that A ⊆ ξG ∪ X.

It is interesting to compare the above theorem to Freiman’s theorem which does not assume control on |A · A| but has a dependence on constants which is significantly worse than polynomial. It seems possible that the constant C(δ) can be made independent of δ, but we do not know how to do so.

Proof (Sketch) Of course, we may assume that |F | ≥ K^{C(δ)} for some large C(δ). We repeat the argument used to prove Theorem 5.1. This argument allows us to find a refinement A′ of A with |A′| ≥ K^{−C}A such that |A′ · A′ − A′ · A′| ≤ K^{C}|A|. By dilating A and A′ if necessary we may assume as before that 1 ∈ A′ (as we shall see, this normalization allows us to take ξ = 1 in the conclusion of this theorem). By Lemma 7.1 we thus have |P (A′, …, A′)| ≤ K^{C}|A′| for all integer polynomials P, with the constant C depending on P of course. We may assume 0 ∈ A′ since adding 0 to A′ and A do not significantly affect the above polynomial bounds.

We now claim that A′ is contained in some subfield G of F of cardinality |G| ≤ K^{C(δ)}|A|. The argument in Lemma 9.1 still gives a surjection from (A′)^{k} to F for some k ∼ 1/δ. We then attempt to use Lemma 9.2 to drop the rank of this surjection down to 1. If we can reduce the rank all the way to one, then we have by arguing as before that |F | ≤ K^{C(k)}|A|, so the claim follows by setting G := F. The only time we run into difficulty in this iteration is if we discover a linear surjection from some Ã^{k′} to F with k′ > 1 which is also injective, where Ã is some polynomial expression of P (A′, …, A′). An inspection of the proof of Lemma 9.2, combined with the normalizations 0, 1 ∈ A′, reveals that Ã must contain A′. If we have |Ã + Ã| > |Ã|, then the linear map from (Ã + Ã)^{k′} → F is surjective but not injective, which allows us to continue the iteration of Lemma 9.2. Similarly if |Ã · Ã| > |Ã|. Thus the only remaining case is when |Ã| = |Ã + Ã| = |Ã · Ã|. But this, combined with the fact that 0, 1 ∈ Ã, implies that Ã = Ã + Ã = Ã · Ã, and hence that Ã is a subfield of F. Since |Ã| ≤ K^{C(k)}|A′|, the claim follows. This shows that A′ is a subset of G. Since |A + A′| ≤ K|A|, we see from Lemma 7.2 that A ⋐ A′ − A′, and hence A ⋐ G. Thus there exists a set Y of cardinality |Y | ≤ K^{C(δ)} such that A ⊆ G + Y.

Let y ∈ Y − G. To finish the proof it will suffice to show that |A ∩ (G + y)| ≤ K^{C(δ)} for all such y. But observe that for any two distinct x, x′ ∈ G + y, the sets xG and x′G do not intersect except at the origin (for if xg = x′g′, then g ≠ g′, and hence x = (x′ − x)\frac{g′}{g−g′} ∈ G, contradicting the hypotheses that x ∈ G + y and y ∉ G). In particular, the sets x(A′ − {0}) and x′(A′ − {0}) are disjoint. Thus

K|A| ≥ |A · A| ≥ |A ∩ (G + y)||A′ − {0}| ≥ |A ∩ (G + y)|K^{−C}|A|

and the claim follows.

10. Some basic combinatorics

In later sections we shall use the sum-product estimate in Theorem 5.1 to various combinatorial problems in finite geometries. In doing so we will repeatedly use a number of basic combinatorial tools, which we collect here for reference.

We shall frequently use the following elementary observation: If B is a finite set, and μ : B → R^{+} is a function such that

∑_{b∈B} μ(b) ≥ X,

then we have

∑_{b∈B:μ(b)≥X/2|B|} μ(b) ≥ X/2.

We refer to this as a “popularity” argument, since we are restricting B to the values b which are “popular” in the sense that μ is large.

We shall frequently use the following version of the Cauchy-Schwarz inequality.

Lemma 10.1. Let A, B be finite sets, and let ∼ be a relation connecting pairs (a, b) ∈ A × B such that

|{(a, b) ∈ A × B : a ∼ b}| ≳ X

for some X ≫ |B|. Then

|\{(a, a′, b) ∈ A × A × B : a ≠ a′; a, a′ ∼ b\}| ≳ \frac{X^{2}}{|B|}.

Proof Define for each b ∈ B, define μ(b) := |{a ∈ A : a ∼ b}|. Then by hypothesis we have

∑_{b∈B} μ(b) ≳ X.

In particular, by the popularity argument we have

∑_{b∈B:μ(b)≳X/|B|} μ(b) ≳ X.

By hypothesis, we have X/|B| ≫ 1. From this and the previous, we obtain

∑_{b∈B:μ(b)≳X/|B|} μ(b)(μ(b) − 1) ≳ X(X/|B|)

and the claim follows.

A typical application of the above Lemma is the standard incidence bound on lines in a plane F^{2}, where F is a finite field.

Corollary 10.2. Let F^{2} be a finite plane. For an arbitrarily collection P ⊆ F^{2} of points and L of lines in F^{2}, we have

|{(p, l) ∈ P × L : p ∈ l}| ≲ |P |^{1/2}|L| + |P |  (11)

Proof We may of course assume that the left-hand side of (11) is ≫ |P |, since the claim is trivial otherwise. From Lemma 10.1 we have

|{(p, l, l′) ∈ P × L × L : p ∈ l ∩ l′; l ≠ l′}| ≳ |P |^{−1}|{(p, l) ∈ P × L : p ∈ l}|^{2}.

On the other hand, |l ∩ l′| has cardinality O(1) if l ≠ l′, thus

|{(p, l, l′) ∈ P × L × L : p ∈ l ∩ l′; l ≠ l′}| ≲ |L|^{2}.

Combining the two estimates we obtain the result.

Note that this is markedly inferior to the Szemerédi-Trotter theorem.

11. Application: A Szemerédi-Trotter type theorem in finite fields

We now use the one-dimensional sum-product estimate to obtain a key two-dimensional estimate, namely an incidence bound of Szemerédi-Trotter type.

Let F be a finite field, and consider the projective finite plane P F^{3}, which is the set F^{3} − {(0, 0, 0)} quotiented by dilations. We embed the ordinary plane F^{2} into P F^{3} by identifying (x, y) with the equivalence class of (x, y, 1); P F^{3} is thus F^{2} union the line at infinity. Let 1 ≤ N ≤ |F |^{2} be an integer, and let P be a collection of points and L be a collection of lines in F^{2}. We consider the problem of obtaining an upper bound on the number of incidences

|{(p, l) ∈ P × L : p ∈ l}|.

From Corollary 10.2 and the duality between points and lines in two dimensions we have the easy bounds

|{(p, l) ∈ P × L : p ∈ l}| ≤ min(|P ||L|^{1/2} + |L|, |L||P |^{1/2} + |P |),  (12)

see e.g. [2]. In a sense, this is sharp: if we set N = |F |^{2}, and let P be all the points in F^{2} ⊂ P F^{3} and L be most of the lines in F^{2}, then we have roughly |F |^{3} ∼ N^{3/2} incidences. More generally if G is any subfield of F then one can construct a similar example with N = |G|^{2}, P being all the points in G^{2}, and L being the lines with slope and intercept in G.

We can use the sum-product estimate (Theorem 5.1) to obtain a non-trivial improvement to this:

Theorem 11.1. [4] Let F be the finite field F := Z/qZ for some prime q, and let P and L be points and lines in P F^{3} with cardinality |P |, |L| ≤ N = |F |^{α} for some 0 < α < 2. Then we have

|{(p, l) ∈ P × L : p ∈ l}| ≤ CN^{3/2−ε}

for some ε = ε(α) > 0 depending only on the exponent α.

Proof We may assume that N ≫ 1 is large. By adding dummy points and lines we may assume that |P | = |L| = N.

Fix N = |F |^{α}, and let 0 < ε ≪ 1, be chosen later. Suppose for contradiction that we can find points P and lines L with |P | = |L| = N such that

|{(p, l) ∈ P × L : p ∈ l}| ≳ N^{3/2−ε};

LECTURE NOTES 6 15

we shall use the sum-product estimates to obtain a contradiction if ε is sufficiently small. Our arguments follow those in [11], [17]. We first use the popularity argument to control how many points are incident to a line and vice versa. For each p ∈ P, define the multiplicity μ(p) at p by

μ(p) := |{l ∈ L : p ∈ l}|.

Then by hypothesis

∑_{p∈P} μ(p) ≳ N^{3/2−ε}

and hence by the popularity argument and the hypothesis |P | = N

∑_{p∈P:μ(p)≳N^{1/2−ε}} μ(p) ≳ N^{3/2−ε}.

On the other hand, we observe that

∑_{p∈P:μ(p)≫N^{1/2+ε}} μ(p)^{2} ≪ N^{−1/2−ε} ∑_{p∈P} μ(p)(μ(p) − 1)

≲ N^{−1/2−ε} ∑_{p∈P} |{(l, l′) ∈ L × L : p ∈ l, l′; l ≠ l′}|

= N^{−1/2−ε} ∑_{l,l′∈L:l≠l′} |{p ∈ P : p ∈ l, l′}|

≤ N^{−1/2−ε} ∑_{l,l′∈L:l≠l′} 1

≤ N^{1/2+ε}.

Thus if we set P′ ⊆ P to be the set of all points p in P such that

N^{1/2−ε} ≲ μ(p) ≲ N^{1/2+ε}

then we have

∑_{p∈P′} μ(p) ≳ N^{3/2−ε}.

For each l ∈ L, define the multiplicity λ(l) by

λ(l) := |{p ∈ P′ : p ∈ l}|,

then we can rewrite the previous as

∑_{l∈L} λ(l) ≳ N^{3/2−ε}.

By the popularity argument we thus have

∑_{l∈L:λ(l)≳N^{1/2−ε}} λ(l) ≳ N^{3/2−ε}.

On the other hand, we have

∑_{l∈L:λ(l)≫N^{1/2+ε}} λ(l) ≲ N^{−1/2−ε} ∑_{l∈L} λ(l)(λ(l) − 1)

≲ N^{−1/2−ε} ∑_{l∈L} |{(p, p′) ∈ P′ × P′ : p, p′ ∈ l; p ≠ p′}|

= N^{−1/2−ε} ∑_{p,p′∈P′:p≠p′} |{l ∈ L : p, p′ ∈ l}|

≤ N^{−1/2−ε} ∑_{p,p′∈P′:p≠p′} 1.

Thus if we set L′ ⊂ L to be the set of all lines l in L such that

N^{1/2−ε} ≲ λ(p) ≲ N^{1/2+ε}

then we have

∑_{l∈L′} λ(l) ≳ N^{3/2−ε}.

For each p ∈ P′, let μ′(p) denote the multiplicity

μ′(p) := |{l ∈ L′ : p ∈ l}|;

clearly μ′(p) ≤ μ(p). We can then rewrite the previous estimate as

∑_{p∈P′} μ′(p) ≳ N^{3/2−ε}.

Thus by the popularity argument, if we set P′′ ⊆ P′ to be the set of all points p in P′ such that

μ′(p) ≳ N^{1/2−ε}

then we have

∑_{p∈P′′} μ′(p) ≳ N^{3/2−ε}.

or equivalently

|{(p, l) ∈ P′′ × L′ : p ∈ l}| ≳ C_{0}N^{3/2−ε}.

Since |L′| ≤ N, we have in particular that

|P′′| ≳ N^{1/2−ε}.  (13)

The next step is to capture a large portion of the popular point set P′ inside a Cartesian product A × B, possibly after a projective transformation. The key observation is that such a product arises, modulo projective transformations, whenever one intersects two “bushes” of lines.

Let p_{0} be any point in P′′. Then by construction there are ≳ N^{1/2−ε} lines l in L′ containing p_{0}. Each of these lines l contains ≳ N^{1/2−ε} points p in P′; of course, all but one of these are distinct from p_{0}. Thus we have

|{(p, l) ∈ P′ × L′ : p, p_{0} ∈ l, p ≠ p_{0}}| ≳ N^{1−2ε}.

Let us define a relation ∼ on P by defining p ∼ p′ if p ≠ p′ and there is a line in L′ containing both p and p′. Since two distinct points determine at most one line, we thus have

|{p ∈ P′ : p ∼ p_{0}}| ≳ N^{1−2ε} for all p_{0} ∈ P′′.

Summing this over all p_{0} in P′′, we obtain

|{(p_{0}, p) ∈ P′′ × P′ : p ∼ p′}| ≳ N^{1−2ε}|P′′|.

Since |P′| ≤ N, we thus see by Lemma 10.1 that

|{(p_{0}, p_{1}, p) ∈ P′′ × P′′ × P′ : p ∼ p_{0}, p_{1}; p_{0} ≠ p_{1}}| ≳ N^{1−Cε}|P′′|^{2}.

By the pigeonhole principle, there thus exist distinct points p_{0}, p_{1} ∈ P′′ such that

|{p ∈ P′ : p ∼ p_{0}, p_{1}}| ≳ N^{1−Cε}.  (14)

Fix these p_{0}, p_{1}. By applying a projective linear transformation (which maps lines to lines and preserves incidence) we may assume that p_{0}, p_{1} are both on the line at infinity. Indeed, we may assume that p_{0} = [(1, 0, 0)] and p_{1} = [(0, 1, 0)], where [(x, y, z)] is the equivalence class of (x, y, z) in P F^{3}.

We first eliminate those points p in (14) on the line at infinity. Such points can only occur if the line at infinity is in L′. But then that line contains at most O(N^{1/2+ε}) points in P′, by the definition of L′. Thus if ε is sufficiently small we have

|{p ∈ P′ ∩ F^{2} : p ∼ [(1, 0, 0)], [(0, 1, 0)]}| ≳ N^{1−Cε}.

Consider the lines in L′ which pass through [(1, 0, 0)]. In the plane F^{2}, these lines be horizontal, i.e. they are of the form {(x, y) ∈ F^{2} : y = b} for some b ∈ F. Let B ⊆ F denote the set of all such b. Since each line contains at least cN^{1/2−ε} points in P′, and |P′| ≤ N, we know that |B| ≲ N^{1/2+ε}. Similarly the lines in L′ which pass through [(0, 1, 0)] must in F^{2} be vertical lines of the form {(x, y) ∈ F^{2} : x = a} for a ∈ A, where |A| ≤ CN^{1/2+ε}. We thus have

|P′ ∩ (A × B)| ≳ N^{1−Cε}  (15)

and

|A|, |B| ≤ CN^{1/2+ε}  (16)

Now that we have placed P′ in a Cartesian grid, the next step is to exploit the form y = mx + b of lines in F^{2} to obtain some additive and multiplicative information on A and B.

Define P_{0} := P′ ∩ (A × B). By definition of P′ we have

|{l ∈ L : p ∈ l}| ≳ N^{1/2−ε} for all p ∈ P_{0};

summing over P_{0} using (15) and rearranging, we obtain

|{(p, l) ∈ P_{0} × L : p ∈ l}| ≳ N^{3/2−Cε}.

Let L_{0} be those lines in L which are not horizontal. Since horizontal lines can contribute at most |P_{0}| ≤ N incidences to the above expression, we have (if ε is sufficiently large)

|{(p, l) ∈ P_{0} × L_{0} : p ∈ l}| ≳ N^{3/2−Cε}.

By the popularity argument, if we let L_{1} denote those lines in L_{0} such that

|{p ∈ P_{0} : p ∈ l}| ≳ N^{1/2−Cε}

we thus have

|{(p, l) ∈ P_{0} × L_{1} : p ∈ l}| ≳ N^{3/2−Cε}

if the implicit constants are chosen appropriately.

Define a relation ∼ between B and L_{1} by defining b ∼ l if there is a point p in the row P_{0} ∩ (A × {b}) such that p ∈ l. Note that such a point p is unique since l is not horizontal, and thus

|{(b, l) ∈ B × L_{1} : b ∼ l}| ≳ N^{3/2−Cε}.

By Lemma 10.1, we thus have

|{(b, b′, l) ∈ B × B × L_{1} : b, b′ ∼ l}| ≳ N^{2−Cε}.

By (16) and the pigeonhole principle, we thus conclude that there exists distinct heights b, b′ ∈ B such that

|{l ∈ L_{1} : b, b′ ∼ l}| ≳ N^{1−Cε}.

Fix this b, b′. By an affine transformation of the vertical variable (which does not affect the line at infinity) we may assume that b = 0 and b′ = 1. Since each line l ∈ L_{1} contains ≳ N^{1/2−Cε} points (x, t) in P_{0}, and hence in A × B, and most of these have t ≠ 0, 1 since l is not horizontal, we have

|{(x, t, l) ∈ A × B × L_{1} : 0, 1 ∼ l; (x, t) ∈ l; t ≠ 0, 1}| ≳ N^{3/2−Cε}.

By definition of the relation a ∼ l, we thus have

|{(x, t, l, x_{0}, x_{1}) ∈ A×B×L_{1}×A×A : (x_{0}, 0), (x, t), (x_{1}, 1) ∈ l; t ≠ 0, 1}| ≳ N^{3/2−Cε}.

Since the three points (x_{0}, 0), (x, t), (x_{1}, 1) determine l, and

x = x_{0} + (x_{1} − x_{0})t,

we thus have

|{(t, x_{0}, x_{1}) ∈ B × A × A : (1 − t)x_{0} + tx_{1} ∈ A; t ≠ 0, 1}| ≳ N^{3/2−Cε}. (17)

Note that this is somewhat similar to saying that (1 − B).A + B.A ⊆ A, so we are getting close to being able to apply our sum-product estimate. But first we must perform some Balog-Szemerédi type refinements.

Let A′ ⊆ A denote those x_{1} in A for which

|{(t, x_{0}) ∈ B × A × A : (1 − t)x_{0} + tx_{1} ∈ A; t ≠ 0, 1}| ≳ N^{1−Cε}.

From (16), (17) and the popularity argument we have

|{(t, x_{0}, x_{1}) ∈ B × A × A′ : (1 − t)x_{0} + tx_{1} ∈ A; t ≠ 0, 1}| ≳ N^{3/2−Cε} (18)

if the implicit constants are chosen correctly.

In particular, from (16) again we have

|A′| ≳ N^{3/2−Cε}/|A||B| ≳ N^{1/2−Cε}.  (19)

Also, by (18), the pigeonhole principle and (16) we may find t_{0} ∈ B such that t_{0} ≠ 0, 1 and

|{(x_{0}, x_{1}) ∈ A × A′ : (1 − t_{0})x_{0} + t_{0}x_{1} ∈ A}| ≳ N^{1/2−Cε}

By (16) we have

|{(x_{0}, x_{1}) ∈ A × A′ : (1 − t_{0})x_{0} + t_{0}x_{1} ∈ A}| ≳ N^{−Cε}|A||A′|.

By (19), (16) and Theorem 6.2 applied to the sets (1 − t_{0})A and t_{0}A′, we thus have a subsets (1 − t_{0})Ã of (1 − t_{0})A and t_{0}A′′ of t_{0}A′ with cardinalities at least ≳ N^{1/2−Cε} such that

|(1 − t_{0})Ã + t_{0}A′| ≲ N^{1/2+Cε}.

By (19), (16) and sumset estimates, this implies in particular that

|t_{0}A′ + t_{0}A′| ≲ N^{1/2+Cε}

and hence

|A′ + A′| ≲ N^{1/2+Cε}.  (20)

Now we return to (18). From (16) and the pigeonhole principle we may find an x_{0} ∈ A such that

|{(t, x_{1}) ∈ B × A′ : (1 − t)x_{0} + tx_{1} ∈ A; t ≠ 0, 1}| ≳ N^{1−Cε}.

By a translation in the horizontal variables x_{0}, x_{1}, A, A′ we may assume that x_{0} = 0. Thus

|{(t, x_{1}) ∈ (B\{0}) × (A′\{0}) : tx_{1} ∈ A}| ≳ N^{1−Cε},

since the contribution of 0 is easily controlled by (16). By (16) and the multiplicative form of Theorem 6.2, we can thus find a subset A′′ of A′\{0} with |A′′| ≳ N^{1/2−Cε} and

|A′′ · A′′| ≲ N^{1/2+Cε}.

On the other hand, from (20) we have

|A′′ + A′′| ≲ N^{1/2+Cε}.

But this gives a contradiction to the sum product estimate (Theorem 5.1) if ε is sufficiently small.

12. Application to the distance set problem

We now work in the finite field plane F^{2}. Given any two points (x_{1}, y_{1}), (x_{2}, y_{2}), we define the distance d((x_{1}, y_{1}), (x_{2}, y_{2})) ∈ F by

d((x_{1}, y_{1}), (x_{2}, y_{2})) = (x_{1} − x_{2})^{2} + (y_{1} − y_{2})^{2}

(we omit the square root to avoid some distracting technicalities). Given any collection P of points in F^{2}, we define the distance set Δ(P) ⊆ F by

Δ(P) := {d(p, p′) : p, p′ ∈ P }.

The Erdös distance problem is to obtain the best possible lower bound for |Δ(P)| in terms of |P |. If −1 is a square, thus i^{2} = −1 for some i ∈ F, then the set P := {(x, ix) : x ∈ F } has cardinality |P | = |F | but Δ(P) = {0} has cardinality 1. To avoid this degenerate case^{3} we assume that −1 is not a square, so any two distinct points have a non-zero distance. From the fact that any two “circles” intersect in at most two points, it is possible to use extremal graph theory to obtain the bound

|Δ(P)| ≥ c|P |^{1/2};

see also [8]. This bound is sharp if one takes P = F^{2}, so that Δ(P) is essentially all of F. Similarly if one takes P = G^{2} for any subfield G of F. However, as in the previous section one can hope to improve this bound when no subfields are available.

From the obvious identity

Δ(A × A) = (A − A)^{2} + (A − A)^{2}

it is clear that this problem has some connection to the sum-product estimate. Indeed, any improvement to the trivial bound on |Δ(P)| can be used (in combination with Lemma 6.1 and Lemma 7.1) to obtain a bound of the form in Lemma 5.1. We now present the converse implication, using the sum-product bounds already obtained to derive a new bound on the distance problem.

Theorem 12.1. [4] Let F = Z/pZ for some prime p = 3 mod 4 (so −1 is not a square), and let P be a subset of F^{2} of cardinality |P | = N = |F |^{α} for some 0 < α < 2. Then we have

|Δ(P)| ≳ N^{1/2+ε}

for some ε = ε(α) > 0.

Remark. In the Euclidean analogue to this problem, with N points in R^{2}, it is conjectured [8] that the above estimate is true for all ε < 1/2. Currently, this is known for all ε < \frac{4e}{5e−1} − \frac{1}{2} ≈ 0.364 [15]. However, the Euclidean results depend (among other things) on crossing number technology and thus do not seem to obviously extend to the finite field case.

Proof We shall exploit the Szemerédi-Trotter-type estimate in Theorem 11.1 in much the same way that the actual Szemerédi-Trotter theorem [16] was exploited in [5] for the Euclidean version of Erdös’s distance problem, or how a Furstenburg set estimate was used in [11], [17] to imply a Falconer distance set problem result. The key geometric observation is that the set of points which are equidistant from two fixed points lie on a line (the perpendicular bisector of the two fixed points).

3We thank Alex Iosevich for pointing out the need to exclude this case.

We may assume that |F | and |P | are large; in particular, we may assume that F has characteristic greater than 2. Fix N, and suppose for contradiction that

|Δ(P)| ≲ N^{1/2+ε}

for some small 0 < ε ≪ 1 to be chosen later. For any point p ∈ P, we clearly have the identity

{(p′, r) ∈ P × Δ(P) : d(p, p′) = r}| = |P | = N

so by Lemma 10.1

{(p′, p′′, r) ∈ P × P × Δ(P) : d(p, p′) = d(p, p′′) = r; p′ ≠ p′′}| ≳ N^{3/2−ε}.

We can of course eliminate the r variable:

{(p′, p′′) ∈ P × P : d(p, p′) = d(p, p′′); p′ ≠ p′′}| ≳ N^{3/2−ε}.

Summing this over all p ∈ P and rearranging, we obtain

∑_{p′,p′′∈P:p′≠p′′} |{p ∈ P : d(p, p′) = d(p, p′′)}| ≥ cN^{5/2−ε}.

By the pigeonhole principle, there thus exists p_{0} ∈ P such that

∑_{p′∈P:p′≠p_{0}} |{p ∈ P : d(p, p′) = d(p, p_{0})}| ≥ cN^{3/2−ε}.

By translation invariance we may take p_{0} = (0, 0). Writing p′ = (a, b) and p = (x, y), this becomes

∑_{(a,b)∈P:(a,b)≠(0,0)} |{(x, y) ∈ P : (x − a)^{2} + (y − b)^{2} = x^{2} + y^{2}}| ≥ cN^{3/2−ε}.

Thus if we let l(a, b) denote the perpendicular bisector of (0, 0) and (a, b):

l(a, b) := {(x, y) ∈ F^{2} : (x−a)^{2}+(y−b)^{2} = x^{2}+y^{2}} = {(x, y) ∈ F^{2} : 2ax+2by = a^{2}+b^{2}}

and let L be the collection of lines {l(a, b) : (a, b) ∈ P \{0, 0}}, then we have

{(p, l) ∈ P × L : p ∈ l} ≥ cN^{3/2−ε}.

But since all the lines l(a, b) are distinct, we have |L| = N − 1, while |P | = N. Thus this clearly contradicts Theorem 11.1, and we are done.

The sum-product estimate has a number of other applications, for instance it gives the best known bound on the Kakeya problem for finite fields in three dimensions. We will not detail this here, but refer the interested reader to [4].

13. Exercises

• Q1. Show that (1) is sharp in the following sense: given any |E| ≥ 5|V |, one can find a graph G with cr(G) ∼ |E|^{3}/|V |^{2}. (Hint: consider n equally spaced points in a circle, and consider the drawing formed by connecting only those points which have at most k points between them using straight line segments).

• Q2. Find a set of N^{3} points and N^{3} lines which have N^{4} incidences between them. (Hint: use the grid {1, …, N} × {1, …, N^{2}}). Conclude that the bound (2) is sharp in the case |L| = |P |. (For an additional challenge: can you show it is sharp in the general case?)

References

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

[2] B. Bollobas, Extremal Graph Theory, Academic Press, London 1978.

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

[4] J. Bourgain, N. Katz, T. Tao, A sum-product estimate in finite fields, and applications, to appear, GAFA.

[5] F. Chung, E. Szemerédi, W. T. Trotter Jr., On the number of different distances, Discrete and Computational Geometry 7 (1992), 1–11.

[6] G. A. Edgar, C. Miller, Borel subrings of the reals, Proc. Amer. Math. Soc. 131 (2003), 1121–1129.

[7] G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), 365–367.

[8] P. Erdös, On sets of distances of n points, American Mathematical Monthly, 53 (1946), 248–250.

[9] P. Erdös, E. Szemerédi, On sums and products of integers, Studies in Pure Mathematics, 213–218. Birkhaüser, Basel, 1983.

[10] T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998), no. 3, 529–551.

[11] N. Katz, T. Tao, Some connections between the Falconer and Furstenburg conjectures, New York J. Math., 7 (2001), 148–187.

[12] M. Nathanson, Additive number theory. Inverse problems and the geometry of sumsets. Graduate Texts in Mathematics, 165. Springer-Verlag, New York, 1996.

[13] I. Ruzsa, Sums of finite sets, Number Theory: New York Seminar; Springer-Verlag (1996), D.V. Chudnovsky, G.V. Chudnovsky and M.B. Nathanson editors.

[14] I. Ruzsa, An analog of Freiman’s theorem in groups, Structure theory of set addition, Astérisque No. 258 (1999), 323–326.

[15] J. Solymosi, G. Tardos, C. D. Tóth, Distinct distances in the plane, Discrete Comput. Geom. 25 (4) (2001), 629–634.

[16] E. Szemerédi, W. T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica 3 (1983), 381–392.

[17] T. Tao, Finite field analogues of the Erdös, Falconer, and Furstenburg problems, unpublished.

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

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