On 4/15/16, Warren D Smith <warren.wds@gmail.com> wrote:
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.
--Sorry; that proof had a flaw. Just putting new point at a place not on any rings, is not good enough. It also must avoid all bisecting lines for pairs of previous points. Such a line could have cardinality as great as N. However random such lines have cardinality of order 1, and on average of order logN.