This post is another piece of my project of listing the various applications of incidences bounds. For a couple of previous posts, see here and here. In this post, we consider the

*sum-product problem*. Given two sets of numbers , we respectively denote their

*sumset*and*productset*as

It is not difficult to choose sets such that (e.g., ), or such that (e.g., ). However, it can be shown that for any choice of , either or must be large. The original sum-product conjecture, by Erdős and Szemerédi, considers a slightly more restricted scenario.

**Conjecture (Erdős and Szemerédi `83).**

*For any there exists , such that any set of integers satisfies*

The best known lower bound for was gradually improved in a series of papers (see here and here). In 1997, Elekes obtained a big breakthrough by applying a geometric approach for the problem.

**Theorem 1 (Elekes `97).**

*Let be two sets of real numbers. Then*

*Proof.*Consider the planar point set

Notice that . We also consider the planar set of lines

(where by we refer to the zero set of the polynomial ). Notice that . Moreover, a line that is defined by the equation (where ) contains the points of of the form for every . That is, every line of is incident to points of . Therefore, the number of incidences in is

On the other hand, by applying the Szemerédi–Trotter theorem, we obtain

By combining and , we obtain

or,

which immediately implies the assertion of the theorem.

Elekes’s proof was followed by various improvements and generalizations which also use geometric ideas. Currently, the best known bound for the sum-product problem, by Solymosi, is . The proof of this bound is geometric, but does not rely on incidences. Unlike Elekes’s proof, this bound does not seem to extend to the case of . One example of an extension of Elekes’s ideas that does rely on incidenes is the following theorem by Elekes, Nathansona, and Ruzsa.

**Theorem 2 (Elekes, Nathansona, and Ruzsa `99).**

*Let be a set of real numbers and let be a set of points in . Let be a strictly convex or strictly concave function, and let . Then*

*Proof.*Consider the planar point set

Consider also the set of planar curves

That is, is a set of translations of a strictly convex/concave curve. Notice that any two such translations intersect in at most one point. We recall the incidences theorem of Pach and Sharir (which I already stated recently here and here).

**Theorem 3 (Pach and Sharir `98).**

*Consider a point set , a set of simple curves , both in , and two constant positive integers and , such that*

- For every points of there are at most curves of that are incident to each of the points.

- Every two curves of intersect in at most points.

In our case, applying Theorem 3 with , implies

On the other hand, every curve of contains points of , we have

Combining and implies

This completes the proof of the theorem, since

The general formulation of Theorem 3 allows it to be applied in various scenarios. In a recent work with Joshua Zahl and Frank de Zeeuw, we have applied the theorem to show that a set of points on two orthogonal lines (with sufficiently many points on each of the lines) must yield a large number of distinct distances.

Recent tools, such as the Elekes-Sharir framework and the incidence results of Guth and Katz, prompted additional sum-prodcut-type bounds. For example:

**Theorem 4 (Iosevich, Roche-Newton, and Rudnev `11).**

*Let be a set of real numbers. Then*

There are many other such extensions, and I cannot mention them all here.

Advertisements