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.

Advertisements

The Baruch Distinguished Mathematics Lecture Series

I am happy to announce the beginning of the Baruch Distinguished Mathematics Lecture Series. In this series we will bring established mathematicians to give talks to a general mathematical audience.

Our first Distinguished Lecture, by Bjorn Poonen, will be “Undecidability in Number Theory”. Click here for the full details. The talk is open to everyone, and includes refreshments. After the talk we will also go to lunch with the speaker.

dls

Incidences in a Recent Work of Walsh

Recently, Miguel Walsh posted a very interesting paper on arXiv. The main purpose of the paper is to study various properties of polynomials and varieties. These properties are related to incidence problems – some originally arose from studying incidences. Walsh also presents new incidence bounds as applications of his results. In this post I’ll briefly discuss the incidence aspects of Walsh’s paper. Since this is a rather specialized post for incidence researchers, it assumes familiarity with the problems and notation.

walsh
Miguel Walsh

It seems to me that Walsh’s paper makes three main contributions to the study of incidence problems. The first two contributions are explicitly stated in the paper:

  • The paper derives a new polynomial partitioning theorem for points on a variety, with a good dependency on the degree of the variety. This was the missing step for removing an extra \varepsilon  in the exponent from most of the existing incidence bounds in {\mathbb R}^d  . For example, it should remove the extra \varepsilon  in the results of several of my papers, such as this one and that one.
  • As an application of his results, Walsh introduces an incidence problem that I did not see before. In this problem we study incidences between points and varieties in {\mathbb R}^d  , but the degrees of the varieties are not constant. That is, the degrees of the varieties are allowed to depend on the number of points and on the number of varieties. It would be interesting to see how this variant develops. For example, what applications in other subfields it might have.

The two above incidence results are definitely interesting, but I suspect that the paper would have a more significant effect on the incidence community in a different way. The paper makes significant progress in our understanding of polynomials and varieties, which directly affect the algebraic methods used to derive incidence bounds. This improved understanding could potentially be what we need to address some of the main problems that we have been trying to solve for a while. Me and other incidences researchers will definitely spend time reading the paper carefully, and think how it might fit with these problems. Walsh also mentions a follow-up paper, and I wonder if he has something similar in mind. I am planning to soon write a post about the current main open problems in incidence theory, and will then mention more clearly what I am referring to.

It might also be worth discussing the lower bounds part of the paper. The paper contains matching lower bounds for some of its incidence results. However, these lower bounds seem to apply specifically to the new variant of incidences with varieties of non-constant degrees. The “standard” problem of incidences with bounded-degree hypersurfaces in {\mathbb R}^d  remains open. In particular, we have matching lower bounds only in some cases. For an up-to-date discussion of the known lower bounds, see for example the relevant part in the introduction of my recent work with Thao Do.

An Uncitable Result?

My colleague Pablo Soberon just showed me an unusually problematic result to cite, and I wanted to share this weird story. If you have other weird citation stories, do tell!

Yes, this is a second silly post in a row. Lately I’m not finding the time to write more serious ones. And the silly stories need to be documented somewhere…

This story begins with a Japanese anime show called The Melancholy of Haruhi Suzumiya. I don’t know much about this show, but apparently there are several different orders in which one can watch the episodes. This led a fan of the show to ask for the minimum number of episodes one needs to watch, so that you saw all the episodes in every possible order. In other words, the minimum sequence of the numbers from \{1,\ldots,n\}  that contains every possible permutation of the numbers. (if I understand correctly, each order has to appear consecutively, with no additional numbers in between). This was on 4chan in 2011. A solution was then offered by an anonymous user, and this disappeared among the other weird anime discussions around the web.

show

It turns out that some people have been studying the above question as a serious math problem, prior to the show and not aware of it. The sequence containing all of the possible permutations is referred to as a superpermutation. See for example here and here. One paper about this was even published in the journal “Discrete Mathematics” in 2013.

Now the people coming from the mathematical angle discovered the original 4chan discussion, and in it the solution to the problem. So can they cite this result? It is by an anonymous person and appeared on an anime fans website. If this is not complicated enough, the relevant website no longer exists. Instead, the original discussion was discovered on a site that archives old online discussions. And it’s unclear how stable this archive site is. Luckily, this is not my problem!

Mathematical Energy: Etymology

This might be the silliest post I’ve written so far (yes – worse than “Was Disney trying to kill mathematicians?”). I urge you to stop reading now unless (i) you are quite familiar with the mathematical notion of energy (e.g., additive energy), and (ii) you have a horrible sense of humor.

The term energy was coined by Tao and Vu. I like “energy” as a name for this object, but I never had a good answer when asked why this is how it’s called. That is, until a referee report provided me with an answer. And this wonderful referee probably didn’t even know it.

In a recent paper, Cosmin Pohoata and I used “color energy”. We have a graph G=(V,E)  with colored edges. Denote the color of an edge (v_1,v_2)  as \chi(v_1,v_2)  . The color energy of G  is

E(G) = \left|\left\{(v_1,v_2,v_3,v_4)\in V^4 :\ \chi(v_1,v_2) = \chi(v_3,v_4) \right\}\right|.

The referee complained about our notation for the multiplicity of a color c  (the number of edge of color c  ), and asked to change it to m_c  . After this change of notation, the energy is defined by the standard formula

E = \sum m_c^2.

NYC Discrete Geometry: Introductory Meeting

I am excited to announce the official start of our new Discrete Geometry group! This event will also be the first meeting of the NYC Geometry Seminar in the CUNY Graduate Center (midtown Manhattan). It will take place at 2pm of Friday August 31st. If you are in the NYC area and interested in Discrete Geometry and related topics – come join us!

The introductory meeting would not consist of the standard seminar presentation. Instead, the purpose of the event is to meet people who are interested in Discrete Geometry, Computational Geometry, and so on (with people coming from NYU, Princeton, various CUNYs, etc). Participants will introduce themselves to the audience and mention the main topics that interest them. You are welcome to either introduce yourself, or just to come listen and have some pastries. If you introduce yourself, you are encouraged to briefly state a major open problem you wish you could solve.

For the exact location, see the event page. Personally, I plan to have more technical math discussions with some participants before and after this meeting.

Opening

Linear Algebra Riddle

I’d like to tell you about a nice riddle, which I heard from Bob Krueger (one of our current REU participants, who already has four papers on arXiv!!). The riddle requires very basic linear algebra and is in the spirit of the previous post.

Riddle. A library has n  books and n+1  subscribers. Each subscriber read at least one book from the library. Prove that there must exist two disjoint sets of subscribers who read exactly the same books (that is, the union of the books read by the subscribers in each set is the same).

Hint: Very basic linear algebra. Try the first thing that comes to mind.

Inside the library of the university of Leuven, Belgium