In the Guth/Katz solution to the Erdos Distance problem on $N$, we have that the minimum distances is given by considering an approximate grid. Let's have $N=n^2$, so the grid is exactly the $n \times n$ grid. I am a little confused why this is the minimum? Doesn't this have at least $\frac{n(n+1)}{2}-1$ distinct distances? That is, the corner point has distinct distances to all points on the diagonal and all points above the diagonal (by symmetry all below have the same distance). I presume this calculation is wrong, because otherwise we clearly get the better solution of just taking regular polygons which have ~$\frac n 2$ distances.
Edit: Internet sources suggest this is $\frac{N}{\sqrt{\log N}}$. I'm not sure if I am reading this right, but Tao's blog says it needs some analytic number theory: http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/
Edit 2: Thinking more about the lattice, the question seems to become, how many of the following are distinct for distinct $i \geq j$ for $i+j \leq n$: $$i^2+j^2$$
That is is to say, maybe on the grid, the distance from the corner to some of the other points eventually becomes equal: i.e. $(23452)^2+(532)^2$ is equal to $(12343)^2+(11568)^2$...obviously, this example doesn't work, and I'm not even sure if there is a (systematic) way to construct numbers that decompose to into distinct sums of squares with the condition described above. So yeah, I'm thinking about it more, and the problem seems to be getting harder, but also cooler.