# Lower bound for a set of distances between pairs of points in a plane

There are $N>1$ points in a plane. Consider the set of all distances between pairs of the points. Let $n$ be the number of elements of this set. We know that $$n \leq {N \choose 2}.$$ What is the lower bound estimate on $n$?

For the sake of clearity, if points are $A_1, A_2, \dots, A_N$, and $S = \{d(A_i, A_j)| 1\leq i < j \leq N \}$, then $n = |S|$.

-
-1: This looks like another olympiad question. It is not clear that you have put any thought into this or truly care about the answer. Please see this meta thread and this one and reconsider your question(s). –  Tom Stephens Aug 12 '10 at 13:49
@Tom Stephens: Falagar's answer is exactly what I needed. I have managed to get only $n \geq \sqrt{N}-1$. I don't understand your negativity. –  n0vakovic Aug 12 '10 at 14:05
This is a beautiful unsolved problem. Why the -1? –  Aryabhata Aug 12 '10 at 17:06
Fair enough, but what has the asker done in this direction? Further, the question is posed in the style of "Prove..."/"Solve..."/etc, and it is not the first one. Considering the rash of these questions recently, I am compelled to respond with the helpful suggestion to see this meta thread and this one, and to reconsider the question. –  Tom Stephens Aug 12 '10 at 17:40
A classical problem in combinatorial geometry is that of determining the minimum number $f(n)$ of different distances determined by $n$ points in the Euclidean plane. In 1952, L. Moser proved that $f(n) > \frac{n^{2/3}}{2\cdot3^{1/3}} - 1$ and this has remained for 30 years as the best lower bound known for f(n). It is shown that $f(n) > cn^{5/7}$ for some fixed constant c.