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
-
1Discussion of past Putnam problems may be found at: http://www.artofproblemsolving.com/Forum/viewforum.php?f=80 – 2011-07-20
-
0The more interesting question is in $m$ dimensions instead of the plane. – 2011-07-20
-
0@GEdgar-How am i able to find it if i don't know which problem it is? – 2011-07-20
-
0@Victor: It is A-6, 1978. – 2011-07-20
-
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}}
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 recent result (I haven't read it, though): http://gilkalai.wordpress.com/2010/11/20/janos-pach-guth-and-katzs-solution-of-erdos-distinct-distances-problem/ – 2011-07-20
-
3This link to the Erdos paper might be better: http://www.renyi.hu/~p_erdos/1946-03.pdf – 2011-07-20
-
0@Aryabhata: Thanks, I just wrote the wrong thing at the top (not sure why), all the references are correct. – 2011-07-20
-
0@Aryabhata: It does give the theorem two (on the next page). I get the document through my University's subscription so I forget that JStor can be annoying. Your link is definitely better, I'll edit the answer. – 2011-07-20
-
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