Incidences: Open Problems (part 1)

The past decade brought us several breakthroughs in the study of geometric incidences. Most importantly, Guth and Katz introduced polynomial partitioning, and this has become the main technique for studying incidences. The recent breakthroughs sometimes leads to a wrong impression about the state of this field. Actually, most of the main incidence problems are still wide open. At least one of the biggest incidence problems has been completely stuck since the early 1980’s.

This leads me to something that has been bothering me for a while (but probably not a single other person in the world…) For some reason, one can find the following statement in the Wikipedia page for the Szemeredi-Trotter theorem.

WikiST

Solymosi and Tao indeed obtained an impressive and near sharp bound for an incidence problem. But it was not a general bound for points and varieties. Most incidence problems involving algebraic varieties in higher dimensions remain wide open. (fixed. Thank you David Eppstein!)

This post is the first of a series which will survey some of the main open problems involving incidence geometry. This series will illustrate how much we do not know about geometric incidences. If you are an outsider, you might start to look down at us incidence researchers. Over 35 years have passed since the Szemeredi-Trotter theorem, and since then we managed to resolve very few other incidence problems.

Problem 1. The unit distances problem

One may say that the main open problem involving geometric incidences is Erdös’s unit distances problem. To quote the book Research Problems in Discrete Geometry, this is

“possibly the best known (and simplest to explain) problem in combinatorial geometry”.

The problem simply asks: In a set of {n} points in {\mathbb{R}^2}, what is the maximum number of pairs of point at a distance of one? For example, {n} equally spaced points on a line span {n-1} unit distances. Using a lattice, one can obtain {n^{1+c/\log\log n}} unit distances, for some constant {c}. The current best upper bound states that every {n} points in the plane span {O(n^{4/3})} unit distances. Even though this is a central problem in Discrete Geometry, with many consequences, the last progress for it was obtained in the early 1980’s. The lower bound has not change since the 1940’s!

The unit distances problem is asymptotically equivalent to finding the maximum number of incidences between {n} points and {n} circles or radius one in {\mathbb{R}^2}. Indeed, consider a set of {n} points in {\mathbb{R}^2}. By placing a circle of radius one around every point, the number of point-circle incidences is twice the number of unit distances. One can move from the incidence problem to the unit distances problem in a similar manner.

Unitcircles

It turns out that the problem significantly changes for different norms:

  • As already stated, for the Euclidean distance norm (the {\ell_2}-norm) this is a long-standing difficult problem.
  • For the {\ell_1}– and {\ell_\infty}-norms, one can easily find {n} points that span {\Theta(n^2)} unit distances.
  • Valtr showed that there is a simply-defined norm for which the answer is {\Theta(n^{4/3})}.
  • Matoušek showed that for a generic norm the maximum number of unit distances is {O(n \log n \log \log n)}.

Note that the conjectured bound {n^{1+c/\log\log n}} for {\ell_2} is different from all of the bounds stated above. In particular, this bound is asymptotically larger than {n \log n \log \log n}. Thus, any solution for the unit distances problem must rely an a property that is almost unique to the Euclidean distance norm. One may say that this problem is about studying properties of the underlying geometry.

The distinct distances problem is another main problem of the field. Guth and Katz almost completely solved this problem, and their work is often considered as the field’s most significant progress in the past decade. One can think of the unit distances problem as more difficult, since a solution to unit distances implies a solution to distinct distances, up to sub-polynomial factors. (For Harmonic Analysis people, the distinct distances problem seemed to have been the more interesting one, due to its connections with the Kakeya conjecture).

Problem 2. Incidences with other algebraic curves in {\mathbb{R}^2}

We know the maximum number of incidences between {m} points and {n} lines in {\mathbb{R}^2}. But what happens when replacing the lines with {n} circles? Parabolas? Arbitrary polynomial curves of degree three? Unfortunately, all of these problems are wide open. If you would now arbitrarily choose another variant, it will most likely also be wide open. The only other cases that are resolved in {\mathbb{R}^2} are a few very specific 2-parameter families of curves. For example, the problem is solved for parabolas of the form {y=x^2+ax+b}, and also for circles incident to the origin.

One can come up with infinitely many incidence problems with algebraic curves in {\mathbb{R}^2}. So what are the main questions? The previous problem already discussed incidences with unit circles. The problem of incidences with arbitrary circles also has many applications. However, the following conjecture is probably considered to be more important than incidences with arbitrary circles.

When discussing a family of algebraic curves, we may consider the number of parameters necessary to define a member of the family. For example, an arbitrary circle can be defined as {(x-a)^2+(y-b)^2=r^2} for parameters {a,b,r}. That is, the set of circles in {\mathbb{R}^2} is a three-parameter family. Similarly, the parabolas defined as {y=ax^2+bx+c} also form a three-parameter family.

Conjecture 1. Let {P} be a set of {m} points and let {\Gamma} be a family of {n} constant-degre algebraic curves defined using {k} parameters, both in {\mathbb{R}^2}. If {n\le m}, then

\displaystyle  I(P,\Gamma)=O_k\left(m^{2/3}n^{2/3}+m+n\right).

It is known that the restriction {n\le m} in the conjecture is necessary. For examples, see this construction for circles and this construction for parabolas. At the moment, the conjecture is open for any family of algebraic curves defined using at least three parameters. The current best bound, by Sharir and Zahl, is stated in the following theorem.

Theorem 2 Let {P} be a set of {m} points and let {\Gamma} be a set of {n} constant-degree algebraic curves defined using at most {k} parameters, both in {\mathbb{R}^2}. Then for any {\varepsilon>0},

\displaystyle  I(P,\Gamma)=O_k\left(m^{\frac{2k}{5k-4}}n^{\frac{5k-6}{5k-4}+\varepsilon}+m^{2/3}n^{2/3}+m+n\right).

Unlike the conjecture, this bound strongly depends on {k}. Sometimes the conjecture is stated with {k} being the degree of the curves, instead of the number of parameters. This is not so different, since the set of algebraic curves of degree at most {k} is defined using {\binom{k+2}{2}} parameters. (Still, the two cases are not quite the same.)

That’s it for now. More problems will appear in the next post of this series.

4 thoughts on “Incidences: Open Problems (part 1)

  1. Pingback: Incidences: Open Problems (part 2) – Some Plane Truths

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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