# (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}).$

(We ask $k$ to be divisible by four only for simplicity. This restriction can be easily removed.)

Proof. Let $\cal P$ be a set of $n$ points in ${\mathbb R}^2$, such that every $k$ points of $\cal P$ determine at least $\binom{k}{2}- 3k/4 +3$ distinct distances. Let $x$ denote the number of distinct distances that are determined by $\cal P$.

By the pigeonhole principle, there exists a distance $\delta$ that is determined by $\Omega(n^2/x)$ pairs of points of ${\cal P}^2$. Let ${\cal P}'$ be the set of points of ${\cal P}$ that are at a distance of $\delta$ from at least one other point of ${\cal P}$. By the restriction $\phi\left(n,k,\binom{k}{2}- 3k/4 +3\right)$, every point of $p \in {\cal P}$ can be at distance $\delta$ from at most $k/4 -2$ other points of ${\cal P}$. This implies that $|{\cal P}'| =\Omega_k(n^2/x)$.

We claim that every distance, except for $\delta$, is determined by less than $k/4$ pairs of $({\cal P}')^2$. Indeed, assume that that a distance $\delta'$ is determined by $k/4$ such pairs $(a_1,b_1),(a_2,b_2),\ldots,(a_{k/4}, b_{k/4})$. We set ${\cal S} =\{a_1,\ldots,a_{k/4},b_1,\ldots,b_{k/4}\}$. The set ${\cal S}$ is not a multiset. That is, if some of these points are identical, then we add just one copy of each point. We arbitrarily add $|{\cal S}|-k/2$ additional points of ${\cal P}'$ to ${\cal S}$, to obtain $|{\cal S}|=k/2$. Finally, for every element of $p\in {\cal S}$ we add to ${\cal S}$ one of the points of ${\cal P}'$ that are at a distance of $\delta$ from $p$. Once again, if some of these points are identical, then we only add one copy of each point. We then obtain a set ${\cal S}$ of at most $k$ points of ${\cal P}$. There are at least $k/2$ pairs of points of ${\cal S}^2$ are at a distance of $\delta$, and at least $k/4$ pairs are at a distance of $\delta'$. Such a case is depicted in the figure below, where the red lines represent the distance $\delta$ and the blue lines represent the distance $\delta'$ (this figure represents the simplest case, where we did not have identical points that were merged in any of the above steps). This contradicts the assumption of the theorem, and thus every distance repeats less than $k/4$ times in ${\cal P}'$.

Since every distance is determined by points of ${\cal P}'$ fewer than $k/4$ times, we get that the points of ${\cal P}'$ determine $\Omega_k(|{\cal P}'|^2) = \Omega_k(n^4/x^2)$ distinct distances. Since the number of distinct distance that are determined by ${\cal P}$ is $x$ and ${\cal P}' \subset {\cal P}$, we have that $n^4/x^2 = O_k(x)$. Equivalently, we get that $x = \Omega_k(n^{4/3})$, as asserted.      $\Box$

Finally, I would like to thank Alex Mun – I came up with the idea for the above proof while discussing the problem with him.
Advertisements