# Putnam A-6: 1978: Upper bound on number of unit distances

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

-
Discussion of past Putnam problems may be found at: artofproblemsolving.com/Forum/viewforum.php?f=80 – GEdgar Jul 20 '11 at 21:07
The more interesting question is in $m$ dimensions instead of the plane. – Eric Naslund Jul 20 '11 at 21:15
@GEdgar-How am i able to find it if i don't know which problem it is? – Victor Jul 20 '11 at 21:17
@Victor: It is A-6, 1978. – André Nicolas Jul 20 '11 at 21:31
Eric, in my view the planar question is the most interesting – Gil Kalai Jul 21 '11 at 10:29

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}}<U(n)<n^\frac{3}{2}.$$ (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)<cn^\frac{4}{3}$ which was done by Spencer Szemeredi and Trotter in 1984.

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)

-
A more recent result (I haven't read it, though): gilkalai.wordpress.com/2010/11/20/… – Aryabhata Jul 20 '11 at 21:41
This link to the Erdos paper might be better: renyi.hu/~p_erdos/1946-03.pdf – Aryabhata Jul 20 '11 at 21:41
@Aryabhata: Thanks, I just wrote the wrong thing at the top (not sure why), all the references are correct. – Eric Naslund Jul 20 '11 at 21:51
@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. – Eric Naslund Jul 20 '11 at 21:58
A more relevant blog post with the bound n^{4/3} is here gilkalai.wordpress.com/2008/07/17/… – Gil Kalai Jul 21 '11 at 10:34