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.

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

Proof.     We begin the proof exactly as in the Elekes-Sharir framework. Consider a set \cal P  of n  points and let

Q = \left\{ (a,p,b,q)\in {\cal P}^4 : |ap| = |bq|>0 \right\}.

Let x  denote the number of distinct distances that are determined by \cal P  , and denote these distances as \delta_1,\ldots,\delta_x  . Let E_i = \{(a,b)\in {\cal P}^2 \mid |ab|=\delta_i \}  . Since every pair of {\cal P}^2  is in exactly one E_i  , we have \sum_{i=1}^x |E_i| = n^2  . By the Cauchy-Schwarz inequality, we get

|Q|=2\sum_{i=1}^x\binom{|E_i|}{2} \ge \sum_{i=1}^x \left(|E_i|-1 \right)^2=\Omega\left(\frac{n^4}{x}\right).\qquad \qquad (1)

For a pair of points p,q\in {\cal P}  we define a point v_{p,q}= (p_x,p_y,q_x,q_y)\in {\mathbb R}^4  , and a hypersurface S_{p,q} \subset {\mathbb R}^4  that is the zero set of

(x_1-p_x)^2+ (x_2-p_y)^2 - (x_3-q_x)^2- (x_4-q_y)^2.

Let {\cal P}_4 = \{v_{p,q} : p,q\in {\cal P} \}  and {\cal S} = \{S_{p,q} : p,q\in {\cal P} \}  , so |{\cal P}_4|=|{\cal S}| = n^2  . Notice that there is a bijection between the incidences in {\cal P}_4 \times {\cal S}  and the quadruples (a,p,b,q)\in Q  . Thus, to derive an upper bound for Q  it suffices to obtain an upper bound on I({\cal P}_4,{\cal S})  .

Assume that there is a copy of K_{2,k-4}  in the incidence graph of {\cal P}_4 \times {\cal S}  . This means that there is a set of k  points \{a_1,b_1,a_2,b_2, p_1,q_1,\ldots,p_{(k-4)/2},q_{(k-4)/2}\}\subset {\cal P}  such that |a_ip_j| = |b_iq_j|  for every 1 \le i \le 2  and 1 \le j \le (k-4)/2  . Thus, if every k  points of \cal P  determine at least \binom{k}{2}-k+5  distances, the incidence graph contains no copy of K_{2,k-4}  . The following is Theorem 1.2 from a paper by Fox, Pach, Suk, Zahl, and myself.

Theorem 2. Let \cal P  be a set of m  points and let \cal V  be a set of n  constant-degree algebraic varieties, both in {\mathbb R}^d  , such that the incidence graph of {\cal P}\times{\cal V}  does not contain a copy of K_{s,t}  (for constants s,t  ). Then for every \varepsilon>0  , we have

I({\cal P},{\cal V}) = O\left(m^{\frac{(d-1)s}{ds-1}+\varepsilon}n^{\frac{d(s-1)}{ds-1}}+m+n\right).

By applying Theorem 2 with d=4  , s=2  , t=k-4  , and m=n  , we obtain

I({\cal P}_4,{\cal S}) = O\left((n^2)^{6/7+\varepsilon}(n^2)^{4/7}+n^2\right) = O\left(n^{20/7+\varepsilon}\right).

Combining this with (1)  yields the assertion of the theorem.     \Box


One thought on “Local Properties that imply Many Distinct Distances

  1. Pingback: (More) Local Properties that imply Many Distinct Distances – 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 )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s