Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

1 Answer

up vote 7 down vote accepted

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)

share|improve this answer
1  
A more recent result (I haven't read it, though): gilkalai.wordpress.com/2010/11/20/… –  Aryabhata Jul 20 '11 at 21:41
3  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.