Incidences: Open Problems (part 2)

We now continue our journey of seeing how we still don’t know much about geometric incidences. So far, we looked at two main problems concerning incidences with curves in the plane (see the first post of the series). It might make sense to move to study incidences in higher dimensions. Instead, we are now regressing to discuss a problem about incidences with lines in the plane.

Problem 3. Structure for point-line incidences.

The exact asymptotic bound for point-line incidences in {\mathbb R}^2  was derived in the early 1980’s. Although several decades have passed, we still know relatively little about the point-line configurations that lead to many incidences. This is the structural problem: characterizing the point-line configurations that achieve the asymptotically maximal number of incidences.

It is not surprising that we do not know much about the structural problem, since this is the case for most problems in this part of discrete geometry – even after the extremal bound is obtained, we are not able say much about the structure of the extremal solutions. The major exception that comes to mind is the Green-Tao structural result for ordinary lines.

Back to point-line incidences in {\mathbb R}^2  , consider the case of n  points and n  lines. The Szemerédi–Trotter theorem states that the maximum number of incidences in this case is \Theta(n^{4/3})  . We have two constructions that achieve this bound: The original construction of Erdős and a simplified construction by Elekes. The points of the first construction are a \sqrt{n}\times \sqrt{n}  section of the integer lattice {\mathbb Z}^2  . The points in the second construction are an n^{1/3}\times n^{2/3}  section of {\mathbb Z}^2  (see figure below). One can further play with these constructions by applying projective transformations and taking subsets of the lattice.


Here are some structural question one might ask about point-line configurations with \Theta(n^{4/3})  incidences:

  • Are \sqrt{n}\times \sqrt{n}  and n^{1/3}\times n^{2/3}  the only lattice sizes that can achieve \Theta(n^{4/3})  incidences? For example, can we use an n^{2/5}\times n^{3/5}  section of {\mathbb Z}^2  ? Is there a continuous spectrum of lattice sizes or are there only a few sporadic sizes?
  • Must there always be a line that contains \sqrt{n}  of the points? (not necessarily a line from the set of n  lines). It is easy to show that there must exist a line containing n^{1/3}  points. I am not aware of any stronger bound for this problem.
  • Must we rely on a section of {\mathbb Z}^2  ? (possibly with a projective transformation and removing some points) Are there other lattices that work? Are there constructions that do not come from lattices?

As you can see, we do not know much. So what do we know? The main piece of information that we have comes from a work of Solymosi.

Theorem (Solymosi). For every constant integer k  , the following holds for every sufficiently large n  . Let {\mathcal P}  be a set of n  points and let {\mathcal L}  be a set of n  lines, both in {\mathbb R}^2  , such that there are \Theta(n^{4/3})  incidences in {\mathcal P}\times {\mathcal L}  . Then there exists a set of k  of the points, no three on a line, such that there is a line passing through each of the \binom{k}{2}  point pairs.

(Cosmin Pohoata wrote a detailed blog post about this result.)

A useful observation. We now discuss another reason for why the structural problem is hard: One can show that the points in a configuration with many incidences may not even contain a small lattice as a subset. I heard this argument from Esther Ezra and Boris Aronov.


The following is just a sketch, and skips several standard probabilistic method arguments. We start with the incidence construction of Erdős, involving a \sqrt{n}\times \sqrt{n}  section of the integer lattice {\mathbb Z}^2  . We independently keep each point with a probability of 0.1  . This should not change the number of incidences asymptotically.

Let k  be a quantity depending on n  . The number of axis parallel k\times k  lattices contained in the original construction is \binom{n}{k} \cdot \binom{n}{k} =O(n^{2k}k^{-2k})  . Since the number of directions spanned by two lattice points is O(n)  , we get a total of O(n^{2k+1}k^{-2k})  lattices of size k\times k  in any direction. Each of those lattices survives the pruning of the points with probability 10^{-k^2}  . Thus, the expected number of surviving k\times k  lattices is

O\left(\frac{n^{2k+1}}{k^{2k}}\cdot \frac{1}{10^{k^2}}\right).

When k=\Omega(\log n)  , the above expectation is smaller than 1. Thus, by using the probabilistic method with alternations, we obtain a configuration with \Theta(n^{4/3})  incidences and no \log n\times \log n  lattice. QED.

A similar argument can be used for the structure described in Solymosi’s theorem. Thus, while it is possible that Solymosi’s theorem could be strengthened, it could not be improved to a number of points larger than \log n  .

It might just be me, but the above reminds me of common themes in additive combinatorics. There, one uses the Balog-Szemerédi-Gowers theorem to claim that a set with a large additive energy contains a large subset with structure, possibly with some additional noise. In the incidence case, we would like to say that a set with many incidence contains a large structured subset, possibly with some additional noise. That is, we are looking for an incidence variant of the Balog-Szemerédi-Gowers theorem. (And also for an incidence variant of Freiman’s theorem).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s