Additive Energy of Real Point Sets

Over the years, more and more interactions between Discrete Geometry and Additive Combinatorics are being exposed. These include results such as the Green–Tao ordinary lines theorem and Solymosi’s sum-product bound. One reason for this connection is that both fields study the structure and symmetries of various objects (such as sets of points or subsets of additive groups). In this post I will discuss one of the simplest connections between the two fields — studying the additive energy of a set of points in a real space {\mathbb R}^d  . The main goal of the post is to present two open problems that involve the additive energy of such sets. I heard one of these problems from Nets Katz and the other from Ciprian Demeter. In future posts we might discuss more involved interactions between the two fields.

demeterckatz
Ciprian Demeter and Nets Katz.

Continue reading

(More) Local Properties that imply Many Distinct Distances

Last year I wrote a post about a distinct distances problem that involves local properties of the point set. Specifically, let \phi(n,k,l)  denote the minimum number of distinct distances that can be determined by a set {\cal P} \subset {\mathbb R}^2  of n  points, such that any k  points of \cal P  determine at least l  distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances. For more details and examples, see the original post.

A while ago I noticed another nice bound for this set of problems. Unfortunately the proof is very simple, which prevents it from being published in a “decent” journal. I’ve been trying to push it further, so far without success. Perhaps someone else would see how this idea can be extended.

As discussed in the previous post, Fox, Pach, and Suk proved that for every k\ge 6  and \varepsilon>0  , we have

\phi\left(n,k,\binom{k}{2}-k+6\right) = \Omega(n^{8/7-\varepsilon}).

A simple argument shows that for every k\ge 4  we have

\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2\right) = \Omega(n^2).

Our interest in this post lies in between these two bounds. That is, what happens between the values \binom{k}{2}-k+6  and \binom{k}{2}- k/2 +2  . I am only aware of one previous result in thie range: Erdős and Gyárfás showed that \phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +1\right) = \Omega(n^{4/3})  . We will now prove a stronger result.

Theorem 1. For every k\ge 8  that is divisible by four, we have

\phi\left(n,k,\binom{k}{2}- 3k/4 +3\right) = \Omega_k(n^{4/3}).

Continue reading

Distinct Distances for Sets with no Repeated Bisectors

This post is about a distinct distances problem which I think is quite interesting. As we shall see, solving this problem would also lead to significant progress in characterizing point sets with a small number of distinct distances. Recall that a perpendicular bisector of two points p,q\in {\mathbb R}^2  is the line that consists of the points a  satisfying |pa|=|qa|  (where |pa|  is the distance between a  and p  ). For brevity, we will simply refer to these as bisectors.

bisectors

We say that a set {\cal P}  of n  points in {\mathbb R}^2  has no repeated bisectors if for every four distinct points a,b,c,d\in {\cal P}  the bisector of a  and b  is not identical to the bisector of c  and d  (that is, the configuration in the above figure is forbidden).

Conjecture. Let {\cal P}  be a set of n  points in {\mathbb R}^2  with no repeated bisectors. Then for any \varepsilon>0  the points of {\cal P}  determine \Omega(n^{2-\varepsilon})  distinct distances, .

For some initial intuition, consider the point sets that determine a small number of distinct distances. I am only aware of two types of configurations that yield O(n)  distinct distances: the vertices of a regular n  -gon and lattices.

intGridnGon

We can also play a bit with these examples. For example, by taking two regular n  -gons whose vertices are on two concentric circles, or by taking n  evenly spaced points on a line (that is, an n\times 1  lattice). All of these examples have a significantly large amount of repeated bisectors.

So far I only managed to find a set with no repeated bisectors and O(\frac{n^2}{\sqrt{\lg n}})  distinct distances. From the other direction, I can only show that every such set determines \Omega(n)  distinct distances. This is unfortunate, since a stronger bound for this problem would lead to a breakthrough in characterizing planar point sets that determine a small number of distinct distances. Below I describe how this can be done, and also how to obtain simple lower and upper bounds for this problem.

Continue reading

Local Properties that imply Many Distinct Distances

Jacob Fox, Janos Pach, and Andrew Suk just placed this paper on arXiv. The paper seems very nice, but unfortunately for Ben Lund, Frank de Zeeuw, and myself, it contains a result that is almost identical to one that we had but did not yet publish. Instead of sulking alone in the dark, in this post I describe the problem and our result.

JFoxJPachAsuk
Jacob Fox, Janos Pach, and Andrew Suk.

Let \phi(n,k,l)  denote the minimum number of distinct distances that can be determined by a set of n  points {\cal P} \subset {\mathbb R}^2  with the property that any k  points of \cal P  determine at least l  distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances.

For example, 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 (including degenerate triangles with three collinear vertices). Since no isosceles triangles are allowed, every point determines n-1  distinct distances with the other points of the set, and we thus 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),\ldots, (a_n,0)\}  does not span any isosceles triangles. Since {\cal P}_1 \subset {\cal P}_2 = \{(1,0),(2,0),\ldots,(a_n,0) \}  and D({\cal P}_2)< n2^{O(\sqrt{\log n})}  , we have \phi(n,3,3) < n2^{O(\sqrt{\log n})}  .

In the same paper, Erdős derived the more general bound

\phi\left(n,k,\binom{k}{2}-k+3\right) = \Omega(n).

As Fox, Pach, and Suk point out, a result by Sarkozy and Selkow implies the slightly stronger (with \varepsilon  depending on k  )

\phi\left(n,k,\binom{k}{2}-k+4+\log k\right) = \Omega(n^{1+\varepsilon}).

We are now ready to state our result. The result of Fox, Pach, and Suk is identical up to the +5  being replaced with +6  . While there are some similarities between the two proofs, they do not seem to be identical.

Theorem 1. For every even k\ge 6  and \varepsilon>0  , we have

\phi\left(n,k,\binom{k}{2}-k+5\right) = \Omega(n^{8/7-\varepsilon}).

Continue reading

Point Sets with Few Distinct Distances

Ben Lund and I were sitting in a small Korean restaurant and discussing an old conjecture of Erdős. Erdős suggested that if a set of n  points in {\mathbb R}^2  spans O(n/\sqrt{\log n})  distinct distances, then the vertices of this set must span either a square or an equilateral triangle. Presumably, this conjecture was made because the two best-known examples of sets with O(n/\sqrt{\log n})  distinct distances are n\times n  subsets of the integer lattice and of the triangular lattice. (By the triangular lattice, I mean the vertices of a tiling of the plane with equilateral triangles.)

intGrid grid3
A subset of the integer lattice and a subset of the triangular lattice.

A subset of the integer lattice spans many squares and no equilateral triangles, while a subset of the triangular lattice spans many equilateral triangles and no squares. We can create various similar configurations by taking one of these two configurations and then applying rotations, uniform scaling, and taking subsets. Such configurations still contain squares or equilateral triangles. Ben and I were wondering whether we can find additional configurations, which are not “related” to the integer lattice or to the triangular lattice. Surprisingly, we managed to find a large family of other configurations. Moreover, many of these configurations do not span any squares or triangles, disproving Erdős’ conjecture. We then discovered that these configurations were already known, and appeared in a paper by Moree and Osburn. I guess that this is another case of lack of communication between different mathematical communities…

Continue reading

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})  .

The limitations of the Elekes-Sharir framework

In a previous series of posts, we discussed the Elekes-Sharir(-Guth-Katz) framework. By using this framework, Guth and Katz derived the bound D(n)=\Omega(n/\log n)  for the Erdős distinct distances problem (where D({\cal P})  denotes the number of distinct distances that are determined by pairs of points from \cal P  , and D(n) = \min_{|{\cal P}|=n}D({\cal P})  ). The best known upper bound is D(n)=O(n/\sqrt{\log n})  , which leaves a gap of \Theta(\sqrt{\log n})  . The common belief is that D(n)=\Theta(n/\sqrt{\log n})  , and thus, that there should exist a way to strengthen the analysis of the lower bound.

In this post we briefly discuss the existence of point sets that determine \Theta(n/\sqrt{\log n})  distinct distances, for which the Elekes-Sharir framework can only yield a bound of \Omega(n/\log n)  . Such configurations imply that to improve the Guth-Katz lower bound while by relying on the Elekes-Sharir framework, one either has to make a drastic change in the framework, or to separately handle the family of “problematic” point configurations. This observation is one of the results in a recent paper by Javier Cilleruelo, Micha Sharir, and myself. Embarrassingly, I did not notice that a similar result was added to the third version of Guth and Katz’s paper. The aforementioned paper still contains other interesting results.

JavierCilSharir2
Javier Cilleruelo and Micha Sharir.

Let us first recall the lower bound construction of Erdős. This construction relies on the following theorem from number theory.

Continue reading