Month: August 2013

by

Few distinct distances implies no heavy lines or circles

This post is about another new distinct distances result, which was just uploaded to arXiv. It is a paper by Zahl, de Zeeuw, and myself.

zahl_profile_picdeZeeuw
Joshua Zahl and Frank de Zeeuw.

Let us start by asking what are currently the main challenges in studying distinct distances (you’re welcome to share your thoughts about this in the comments). It seems to me that most people consider the main challenge to be the d -dimensional variant of the distinct distances problem (see the second half of this post for more details). I would like to suggest that another main problem is characterizing the point sets that determine a small number of distinct distances.

I already wrote about the characterization problem in this post, and I will now repeat a few sentences from there. So far, all the known point sets that determine a sublinear number of distinct distances are \sqrt{n}\times\sqrt{n} lattices, possibly with some minor changes. For example, any \sqrt{n}\times\sqrt{n} subset of the integer lattice determines O(n/\sqrt{\log n}) distinct distances, and so does a \sqrt{n}\times\sqrt{n} subset of the following triangular lattice:

\displaystyle \left\{a\cdot (1,0) + b\cdot (1/2, \sqrt{3}/2) \ \mid \mbox{ for any } a,b\in{\mathbb Z} \right\}.

intgrid grid3

Over 25 years ago Erdős asked whether every point set that determines O(n/\sqrt{\log n}) distinct distances “has lattice structure”. However, even after so many years and Guth and Katz’s breakthrough, we still hardly know anything about this problem. A proof by Szemerédi (unpublished and originally described in a 1975 paper by Erdős) implies that for every n -point set \cal P , there exists a line \ell that contains \Omega(\sqrt{\log n}) points of \cal P . It had been conjectured by Erdős that this bound can be improved to \Omega(n^{1/2}) , though no improvement had been discovered in the decades that passed. It is an interesting challenge to prove even the case of \Omega(n^{\varepsilon}) points on a line.

In the new paper, we study the “complementary” problem of proving that there must not be a line with too many points on it.

Theorem 1. (S’, Zahl, and de Zeeuw) Let \cal P be a set of n points that determine o(n) distinct distances. Then no line contains \Omega(n^{7/8}) points of \cal P .

Continue reading →

by

Distinct distances from three points

This post is about the recent paper of Sharir and Solymosi concerning distinct distances from three points.

michasSolymosi

Let {\cal P}_1 and {\cal P}_2 be two sets of points in the plane, and let D({\cal P}_1,{\cal P}_2) denote the number of distinct distances that are determined by a point of {\cal P}_1 and a point of {\cal P}_2 . The case where the points of each set are on a distinct line was considered in this paper by Sharir, Solymosi, and myself, and a generalization to the case where the points are on two general constant-degree curves was recently derived by Pach and de Zeeuw. Instead of restricting the point sets to curves, we now consider the case where {\cal P}_1 contains only a constant number of points (and |{\cal P}_2|=n ).

If {\cal P}_1 contains a single point p , then by putting the points of {\cal P}_2 on a common circle around p , we obtain D({\cal P}_1,{\cal P}_2) = 1 .

OneCenter

Next, consider the case where {\cal P}_1 contains two points p,q . Let D=\{d_1,d_2,\ldots\} be the set of distinct distances between points of {\cal P}_1 and points of {\cal P}_2 . Consider the |D| circles that are centered around p and have a radius from D , and the |D| circles that are centered around q that have a radius from D . Since D consists of all the distances between {\cal P}_1 and {\cal P}_2 , every point of {\cal P}_1 must be contained in an intersection of two circles. Let r be the distance between p and q and let D=\{d_1,d_2,\ldots\} be a set of \sqrt{n} distinct distances, all larger than r and smaller than 2r . In this case, the two sets of circles intersect in exactly 2n points. We can arbitrarily choose n of these intersection points to be the points {\cal P}_2 . This implies that when |{\cal P}_1|=2 it is possible to have D({\cal P}_1,{\cal P}_2) = O(\sqrt{n}) .

TwoCenters

To see that this bound is tight, assume for contradition that D({\cal P}_1,{\cal P}_2) = o(\sqrt{n}) and notice that there are o(n) intersection points between the two sets of circles, which makes it impossible for the n points of {\cal P}_2 to be intersection points. A nice corollary of this is that for every set \cal P of n points in the plane, there exists at most one point p\in{\cal P} such that p determines o(\sqrt{n}) distinct distinct distances with the points of {\cal P}\setminus\{p\} .

The case where {\cal P}_1 contains three points p_1,p_2,p_3 is the first non-trivial case. As before, we can equivalently consider three families of circles, each centered around a different p_i , and find an upper bound for the number of points that are contained in three circles.

Continue reading →

by

Even more new results!

I just wrote about the new distinct distances result of Pach and de Zeeuw, and already two new related papers appeared on arXiv. The rate of new papers that deal with distinct distances and incidence problems (mainly by applying algebraic tools) is becoming a bit crazy.

One of the new arXiv papers is a distinct distances result by Sharir and Solymosi. I plan to write a post about this paper soon. The other paper, which I will describe in this post, is an incidence result by Wang, Yang, and Zhang. Thanks to Joshua Zahl and to Frank de Zeeuw for pointing out these papers out to me (and do tell me about other related results if you happen to notice any! I am planning to set up a webpage that lists all of the papers that are related to the recent polynomial method/algebraic method).

The following theorem is a classic incidence result that was published by Pach and Sharir in 1998.

Theorem 1. Consider a point set \cal P , a set of simlpe curves \Gamma , both in {\mathbb R}^2 , and two constant positive integers k and s , such that

  • For every k points of \cal P there are at most s curves of \Gamma that are incident to each of the k points.
  • Every two curves of \Gamma intersect in at most s points.

Then I({\cal P},\Gamma) = O(|{\cal P}|^{k/(2k-1)}|\Gamma|^{(2k-2)/(2k-1)}+|{\cal P}|+|\Gamma|), where the constant of proportionality depends on k and s .

For example, consider the case where \Gamma is a set of unit circles (i.e., circles with a radius of 1). A pair of points can have at most two common unit circles through them and every two unit circles intersect in at most 2 points. Therefore, by applying Theorem 1 with k=2 and s=2 , we obtain the best known bound I({\cal P},\Gamma) = O(|{\cal P}|^{2/3}|\Gamma|^{2/3}+|{\cal P}|+|\Gamma|). Similarly, for circles with arbitrary radii, we can apply Theorem 1 with k=3 and s=2 .

UnitCircles

To stress how useful Theorem 1 is, notice that it has been used in the new paper of Pach and de Zeeuw, in the new paper of Sharir and solymosi, in the six months old paper by Sharir, Solymosi, and myself, and so on…

What happens if we have less information about \Gamma ? For example, if we know that all of the curves of \Gamma have a degree of at most D , but we are having a hard time determining the value of k ? If the curves are allowed to have common components, then we can have I({\cal P},\Gamma) = \Theta(|{\cal P}| |\Gamma|) when all the points of \cal P are incident to a component that is contained in all of the curves of \Gamma . To make the situation less trivial, assume that no two curves of \Gamma share a common component. In this case, Bézout’s theorem tells us that every two curves of \Gamma can share at most d^2 common points. Therefore, we can apply Theorem 1 with k=d^2+1 and s=d^2 .

Continue reading →

by

Distinct Distances: Open Problems and Current Bounds (part @#%)

This post surveys yet another family of variants of the distinct distances problem, for my survey of open problems and best known bounds. I think that not too many variants are still missing.

Let \phi(n,k,l) denote the minimum number of distinct distances that are determined by a planar set \cal P of n points with the property that any k points of \cal P determine at least l distinct distances (this notation is taken from Chapter 5 of Research Problems in discrete Geometry). That is, by having a local property of every small subset of points, we wish to obtain a global property of the entire point set. The following table lists the best known bounds for most of the problems that are discussed in this post.

Variant Lower Bound Upper Bound
\phi(n,3,2) \Omega(n/\log n) O(n/\sqrt{\log n})
\phi(n,3,3) \Omega(n) n2^{O(\sqrt{\log n})}
\phi(n,4,3) \Omega(n/\log n) O(n/\sqrt{\log n})
\phi(n,4,4) \Omega(n/\log n) n2^{O(\sqrt{\log n})}
\phi(n,4,5) \Omega(n) O(n^2)
\phi(n,5,9) \Omega(n) O(n^2)

The case of k=3

The value of \phi(n,3,2) is the minimum number of distinct distances that are determined by a set of n points that do not span any equilateral triangles. As discussed in a previous post in the series, Erdős noticed that a \sqrt{n}\times\sqrt{n} integer lattice determines \Theta(n/\sqrt{\log n}) distinct distances. It is known that the points of the integer lattice do not determine any equilateral triangles, and thus \phi(n,3,2)= O(n/\sqrt{\log n}) . Guth and Katz’s bound for D(n) (i.e., the general planar distinct distances problem) implies \phi(n,3,2)= \Omega(n/\log n) . Thus, the best known bounds for \phi(n,3,2) are identical to the ones for D(n) .

Problem 1. Find the asymptotic value of \phi(n,3,2) .

The value of \phi(n,3,3) is the minimum number of distinct distances that are determined by a set of n points that do not span any isosceles triangles (here and in the following cases, we also consider degenerate polygons, such as a degenerate isosceles triangle whose three vertices are collinear). Since no isosceles triangles are allowed, every point determines n-1 distinct distances with the other points of the set, and thus we have \phi(n,3,3) = \Omega(n) . Erdős observed the following upper bound for \phi(n,3,3) . Behrend proved that there exists a set A of positive integers a_1<a_2<\cdots<a_n , such that no three elements of A determine an arithmetic progression and that a_n < n2^{O(\sqrt{\log n})} . Therefore, the point set {\cal P}_1 = \{(a_1,0), (a_2,0),\cdots, (a_n,0)\} \subset {\mathbb R}^2 does not span an isosceles triangle. Since {\cal P}_1 \subset {\cal P}_2 = \{(1,0),(2,0),\cdots,(a_n,0) \} and D({\cal P}_2)< n2^{O(\sqrt{\log n})} , we have \phi(n,3,3) < n2^{O(\sqrt{\log n})} . Erdős conjectured that \phi(n,3,3) = \omega(n) .

Problem 2. Find the asymptotic value of \phi(n,3,3) .

The case of k=4

Continue reading →

by

A new result of Pach and de Zeeuw!

An exciting new result by János Pach and Frank de Zeeuw just appeared on arXiv. The new paper derives both an improvement of the results in the recent paper of Marcos Charalambides (though only for the planar case) and a generalization of the results in a recent paper by Sharir, Solymosi, and myself. Specifically the new paper proves:

Theorem 1. Let C be a planar algebraic curve of a constant degree that does not contain any lines or circles. Then any set of n points on C determines \Omega(n^{4/3}) distinct distances.

Theorem 2. Let C_1 and C_2 be two irreducible planar algebraic curves of constant degrees which are not parallel lines, orthogonal lines, or concentric circles. Then for any m points on C_1 and n points on C_2 , the number of distinct distances between the two sets is \Omega(\min\{m^{2/3}n^{2/3},m^2,n^2\} .

I plan to thoroughly go over the paper this week, and perhaps write a more detailed post about it at some point.