0

Given that the upper bound on the number of unit distances determined by n points in a real space is $ cn^\frac{4}{3} $

Give a lower bound on the min. number of unique distances.

I am really struggling with this, any thoughts appreciated. Thanks

Attempt 1:

I know that the total distances = $n^2$

Let

$$ T = Total \space Distance = n^2$$ $$ U = Unit \space Distance \le cn^\frac{4}{3} $$ $$ K = Distinct \space Distances $$

So, $\space $ T = U + K

$$ T - K \le cn^\frac{4}{3}$$ $$ n^2 - K \le cn^\frac{4}{3}$$

Therefore

$$ K \ge n^2(1-cn^\frac{2}{3}) $$

Is this correct? The big question is does the equation T = U + K hold?

Navy Seal
  • 187
  • No, it does not hold: if there are three unit distances and seven distances of length $2$, then $T = 10$ and $U = 3$, but $K = 2$. – Erick Wong Mar 15 '17 at 23:34
  • The idea here is that the unit distance bound also gives you a bound on the number of repeated distances of any fixed length (can you see why?). – Erick Wong Mar 15 '17 at 23:35
  • Assuming you mean $n^{-2/3}$, your purported lower bound is $\Omega(n^2)$. Just take $n$ equally spaced points on a line to see why this cannot possibly be a correct lower bound. – Erick Wong Mar 15 '17 at 23:39
  • I can see why the equation is wrong, but I dont know how else to approach this. – Navy Seal Mar 16 '17 at 00:14
  • My second comment above is already a hint for how to approach this. – Erick Wong Mar 16 '17 at 00:24

0 Answers0