Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|$.

share|cite|improve this question
-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
@Tom Stephens: I really don't see a problem. Question aligns with both FAQ and a lot of comments in threads you linked to. Few comments above I wrote what I 'have done in this direction', but I don't see why I need to have some decent result to be interested in an answer. I am passionate about math and were thrilled about this side, but this kind of comments make it elitist place and turn people off. Maybe for some people I'm not the audience for this site, but it didn't feel that way after reading what this site should be. – n0vakovic Aug 12 '10 at 19:59
up vote 5 down vote accepted

You might want to read this article.

The abstract of this article says:

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.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.