6
$\begingroup$

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

  • 1
    Discussion of past Putnam problems may be found at: http://www.artofproblemsolving.com/Forum/viewforum.php?f=802011-07-20
  • 0
    The 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
  • 0
    Eric, in my view the planar question is the most interesting2011-07-21

1 Answers 1

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

  • 1
    A 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
  • 3
    This link to the Erdos paper might be better: http://www.renyi.hu/~p_erdos/1946-03.pdf2011-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
  • 1
    A 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