Random Stories Pictures from IPAM – Part 3

We finished our IPAM semester with a workshop at lake arrowhead. You can find our “graduation pictures” at the IPAM facebook page (just don’t look at my horrible picture…). In honor of this amazing semester, here are some pictures that I have from it. If you have other nice pictures, you’re welcome to send them to me and I’ll place them here.

A farewell party to Micha, just before he was leaving LA.

The notorious reading group, trying to get through Harris’ algebraic geometry book.

Abdul Basit took us to what according to him is the best Pakistani food that he had outside of Pakistan.

Pool party!

Distinct Distances: Open Problems and Current Bounds

If you have been following this blog for a while, you might have noticed that I have been slowly surveying the various open problems that are related to distinct distances, and the best known bounds for them. I think that my survey is now in a decent shape, so I uploaded it on arXiv.

For this occasion, I wish to mention an open problem concerning surfaces in {\mathbb R}^3  . It is far from being one of the main problems of this subfield. However, since currently no non-trivial bounds are known for it, it seems like a good problem for a student or for someone who wishes to start working on distinct distances problems.

Recall that in bipartite distinct distances problems we have two sets of points {\cal P}_1  and {\cal P}_2  , and are interested only in distinct distances that are spanned by pairs of {\cal P}_1\times{\cal P}_2  (i.e., distances between points from different sets). For simplicity, in this post we assume that both sets are of cardinality n  . One example of such a result, by Pach and de Zeeuw, is that if each of the two point sets is on a planar curve that contains no lines or circles, then the number of distinct distances between {\cal P}_1  and {\cal P}_2  is \Omega\left(n^{4/3}\right).

In {\mathbb R}^d  , the similar (yet non-bipartite) case where one point set is placed a curve was studied by Charalambides and by Raz, Sharir, and Solymosi. However, nothing non-trivial is known for point sets on two-dimensional surfaces. That is, consider, in {\mathbb R}^3  , the minimum number of distinct distances between a set {\cal P}_1  of n  points on a two-dimensional surface S_1  , and a set {\cal P}_2  of n  points on a two-dimensional surface S_2  .

Before we properly formulate any questions for this scenario, let us first consider some examples. First, consider the case where S_1  and S_2  are non-parallel planes in {\mathbb R}^3  . In this case there exist two orthogonal lines \ell_1,\ell_2  such that \ell_1 \subset S_1  , \ell_2 \subset S_2  , and \ell_1 \cap \ell_2  is a point on S_1 \cap S_2  . We can place the two sets of points on \ell_1,\ell_2  such that the number of distinct distances between the two sets is \Theta(n)  (e.g., see Section 3 of the survey). The same bound can be obtained between two spheres and between a sphere and a plane (in both cases by placing the points on two parallel circles).

A slightly better bound can be obtained in the case where S_1  and S_2  are parallel planes. In this case we can place a \sqrt{n}\times\sqrt{n} subset of the integer lattice on each of the planes. For example, we may assume that the planes are defined by z=0  and z=1  , and that the points of the two sets are

{\cal P}_1 \cup {\cal P}_2 = \left\{ (x,y,z) | 1 \le x,y \le \sqrt{n} \quad \text{ and } \quad 1 \le z \le 2 \right\}.

A variant of Erdős’ analysis of the planar lattice (e.g., see Section 2 of the survey) implies that the number of distinct distances between the two sets is O(n/\sqrt{\log n})  .

Unlike the planar case, it is not immediately clear whether the above examples are tight. For example, the n^{1/3}\times n^{1/3} \times n^{1/3}  integer lattice determines only O\left(n^{2/3}\right)  distinct distances. This leads to the following conjecture.

Conjecture. Given a set {\cal P}_1  of n  points on a two-dimensional surface S_1  , and a set {\cal P}_2  of n  points on a two-dimensional surface S_2  , both in {\mathbb R}^3  , the number of distinct distances between the two sets is \Omega(n/\sqrt{\log n})  (or at least \Omega(n^{1-\varepsilon})  ?).

Assuming that the conjecture is true, we have the following natural question.

Problem. Characterize which pairs of surfaces S_1,S_2  can yield O(n)  distinct distances. Moreover, provide a lower bound for the minimum number of distinct distances for the case of any other pair of surfaces.

This problem formulation is motivated by aforementioned result of Pach and de Zeeuw for the case of points on two planar curves, where the only “exceptional” cases are when the two curves contain parallel lines or concentric circles, and then the number of distinct distances can be \Theta(n)  . For any other pair of curves, the number of distinct distances is \Omega(n^{4/3})  .

Incidences: Lower Bounds (part 1)

This is the first in a new series of posts, in which I will survey the constructions leading to the best known lower bounds for the various incidence problems. Although recently many improved upper bounds for incidence problems were proven, not much progress was made concerning the lower bounds.

We begin with the case of point-line incidences in the plane. This is of course the matching lower bound for the famous Szemerédi–Trotter Theorem.

Theorem 1 (Szemerédi and Trotter). The maximum number of incidences between a set {\cal P}  of m  points and a set {\cal L}  of n  lines, both in {\mathbb R}^2  , is

I({\cal P},{\cal L})=O\left(m^{2/3}n^{2/3}+m+n\right).

Notice that the linear terms dominate this bound when either m =O(\sqrt{n})  or m =\Omega(n^2)  . Since a point-line configuration with \Omega(m+n)  incidences is easy to construct, we focus on obtaining \Omega(m^{2/3}n^{2/3})  incidences when n^{1/2} \ll m \ll n^2  .

Today the “common” construction for the planar point-line incidence bound is by Elekes. Elekes’ construction will be described in the next post of the series. Before that, in this post we present the original construction of Erdős. While this construction is mentioned in several places (e.g., see here), I could not locate the original paper that describes it. Many years later Edelsbrunner and Welzl rediscovered this construction.

Pach and Tóth use a variant of this construction to obtain the best known constant for the lower bound for the maximum number of point-line incidences. Specifically,

I({\cal P},{\cal L}) \ge 0.42 \cdot m^{2/3}n^{2/3}+m+n.

Recall that our goal is to construct a set of m  points and a set of n  lines, for any n^{1/2} \ll m \ll n^2  . Specifically, we assume that c n^{1/2} \le m  for a sufficiently large constant c  whose value will be determined below. As our point set, we take the following subset of the integer lattice.

{\cal P} = \left\{ (i,j) | 1 \le i \le \sqrt{m} \quad \text{ and } \quad -\frac{\sqrt{m}}{2} \le j \le \frac{\sqrt{m}}{2}\right\}.

Given a pair of relatively prime integers a<b, we define the line set:

{\cal L}_{a,b} = \left\{ y-j = \frac{a}{b}(x-i) | \quad 1 \le i \le b, \quad 1 \le j \le \frac{\sqrt{m}}{4} \right\}.

Notice that |{\cal L}_{a,b}| = b\sqrt{m}/4  . Our set of lines is the union of many sets of the form {\cal L}_{a,b}  . Specifically, we set k = c'n^{1/3}/m^{1/6}  (for a constant c'  that will be set below) and

{\cal L} = \bigcup_{1 \le a < b \le k \atop gcd(a,b)=1} {\cal L}_{a,b}.

The resulting point-line configuration is depicted in the following figure.


Continue reading