Let n distinct points in the plane be given.prove that fewer than $2n^\frac{3}{2}$ pairs of them are at unit distance apart
Putnam A-6: 1978: Upper bound on number of unit distances
6
$\begingroup$
geometry
combinatorics
contest-math
-
0Eric, in my view the planar question is the most interesting – 2011-07-21
1 Answers
7
There is a rich history for this problem.
Let $U(n)$ denote the number of times a given distance can occur for $n$ points in the plane. In 1946 Erdos showed that $n^{1+\frac{c}{\log \log n}} (Notice the upper bound is what you want to prove) Erdos also conjectured that the upper bound should have the same form as the lower bound.
Szemeredi improved the upper bound to $o\left(n^\frac{3}{2}\right)$ in 1975, and in 1982 Beck and Spencer gave the upper bound of $n^{1.499}$.
The best known result is $U(n)
The link to Erdos paper contains a proof of the question you are asking.
Edit: Here is the more accessible (not JStor) link to Erdos Paper, provided by Aryabhata)
-
1A more relevant blog post with the bound n^{4/3} is here http://gilkalai.wordpress.com/2008/07/17/extermal-combinatorics-ii-some-geometry-and-number-theory/ – 2011-07-21