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
denote the minimum number of distinct distances that can be determined by a set of
points
with the property that any
points of
determine at least
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
is the minimum number of distinct distances that are determined by a set of
points that do not span any isosceles triangles (including degenerate triangles with three collinear vertices). Since no isosceles triangles are allowed, every point determines
distinct distances with the other points of the set, and we thus have
. Erdős observed the following upper bound for
. Behrend proved that there exists a set
of positive integers
, such that no three elements of
determine an arithmetic progression and that
. Therefore, the point set
does not span any isosceles triangles. Since
and
, we have
.
In the same paper, Erdős derived the more general bound
As Fox, Pach, and Suk point out, a result by Sarkozy and Selkow implies the slightly stronger (with
depending on
)
We are now ready to state our result. The result of Fox, Pach, and Suk is identical up to the
being replaced with
. While there are some similarities between the two proofs, they do not seem to be identical.
Theorem 1. For every even
and
, we have
Proof. We begin the proof exactly as in the Elekes-Sharir framework. Consider a set
of
points and let
Let
denote the number of distinct distances that are determined by
, and denote these distances as
. Let
. Since every pair of
is in exactly one
, we have
. By the Cauchy-Schwarz inequality, we get
For a pair of points
we define a point
, and a hypersurface
that is the zero set of
Let
and
, so
. Notice that there is a bijection between the incidences in
and the quadruples
. Thus, to derive an upper bound for
it suffices to obtain an upper bound on
.
Assume that there is a copy of
in the incidence graph of
. This means that there is a set of
points
such that
for every
and
. Thus, if every
points of
determine at least
distances, the incidence graph contains no copy of
. The following is Theorem 1.2 from a paper by Fox, Pach, Suk, Zahl, and myself.
Theorem 2. Let
be a set of
points and let
be a set of
constant-degree algebraic varieties, both in
, such that the incidence graph of
does not contain a copy of
(for constants
). Then for every
, we have
By applying Theorem 2 with
,
,
, and
, we obtain
Combining this with
yields the assertion of the theorem. 
Pingback: (More) Local Properties that imply Many Distinct Distances – Some Plane Truths