Here is a different proof that N^(2/3-o(1)) points are achievable: point-adding algorithm. Simply add points to our set one at a time, totally arbitrarily so long as the new point does not cause a distance repetition. Suppose we have a point set with P points and no repeated distances. In that case, there are (P-1)*P/2 used (and hence forbidden for further use) distances. Each current point can be regarded as having "rings" (concentric circles) drawn around it, at forbidden distances. All points we add in the future must NOT lie on any of those rings. The cardinality of any one ring is N^o(1). The total number of forbidden points at a moment when current set has P points, is therefore <=P^3 * N^o(1). So we can keep adding points until P^3 * N^o(1) >= N^2 - P. Hence we can, and always will, achieve P = N^(2/3-o(1)). QED. There is tremendous (indeed total) freedom of choice in this method. The question is how best to exploit it to do better, and how much better is possible. For example, you could in this way get a set with N^0.666 points, then do it again to get a DISJOINT set with N^0.666 points, and so on, thus obtaining N^1.333 disjoint subsets of the NxN grid, each with N^0.666 points, with each subset by itself having no repeated distances (for any large-enough N). Another example: One could in this way get a set with N^0.666 points, with no repeated distances, and also no short distances (less than N^0.666), and also forbidding the N^0.666 distances whose squares have the most representations as sums of two squares. Here is a 1-dimensional problem which might have some relevance: What is the largest subset of {1,2,3,...,N} such that all pairwise differences, are prime? (Might make a good programming contest...) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)