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