Keith F. Lynch <kfl at KeithLynch.net> wrote: How large a subset of the N^2 points on an N-by-N square grid can there be with none of the distances between the points in the subset being equal? WDS: Let F(N) denote this quantity. UPPER BOUND: F(N) < 2*N. Proof: The squared distances are each integers which are at least 1 and at most 2*(N-1)^2 and there are (F-1)*F/2 of them. Therefore 2*F <= sqrt(16*N^2-32*N+17) + 1 hence F(N) < 2*N. STRONGER UPPER BOUND: F(N) < 1.4702214*N / (lnN)^1/4 for all large enough N. Because: The fraction of integers in {1,2,...,Y} which are representable as a sum of two squares, goes to 0. More precisely, x is representable as x=a^2+b^2 only if the squarefree part of x contains no prime factor p with p=3(mod 4). This fraction is asymptotic to K/ln(Y)^(1/2) with K=0.764223653, see http://mathworld.wolfram.com/Landau-RamanujanConstant.html Only the representable ones can arise as a squared distance. So we find the claim with the constant 2*K^(1/2)/2^(1/4)<1.4702214. LOWER BOUND: F(N) > N^(2/3 - o(1)). Proof sketch: Chose P points at random form the grid. The expected number of repeated distances among the binomial( (P-1)*P/2, 2 ) point-pairs, is <= binomial( (P-1)*P/2, 2 ) / N^(2-o(1)) using the fact (consequence of a theorem by Severin Wigert 1907) that the number of ways to represent Y as a sum of two squares is Y^o(1) at most. Indeed Y^( [ln(2)+o(1)] / lnln(Y) ) at most. If we choose P so this expected number is below P/2, then we may remove P/2 points to make the number of repeated distances zero. A configuration must exist achieving expectation or below. P = N^(2/3 - o(1)) works. CONJECTURAL STRONGER LOWER BOUND: F(N) > N^(1-o(1)). Incomplete Proof: The first idea is to take the cartesian product of two (1 dimensional) "Singer difference sets." A Singer difference set (Singer 1938) is a subset of Z mod N such that every difference occurs exactly once. Singer sets have q+1 elements where N=q^2+q+1 and q is any prime power. So this cartesian product would have (q+1)^2 elements which equals N to within error of order sqrt(N). However, this does not quite work because each distance d could be repeated up to r2(d^2) times, where r2(x) is the number of ways to represent x as a sum of two squares. Namely x=a^2+b^2 where a and b are differences in each 1dimensional Singer set. Second idea is to use the fact r2(x) always is small, indeed it is x^o(1) as a consequence of 1907 theorem by Severin Wigert. What actually matters is its mean squared order, which appears not to have been studied, so I am using its maximum order, which weakens me. OK, so the third idea is going to be to make each point in the Singer difference set cartesian product actually be a blob of N^o(1) nearby points of which we only employ one. [Weakening the Singer construction by factor N^o(1).] Then if you try to get a repeated distance d by using distance A in horizontal Singer set, distance B in vertical, and d^2=A^2+B^2, representable in N^o(1) ways, then that will not work because I will choose the perturbations of the 1D Singer points, each within its allowed blob, randomly to throw off the few exact equalities. This is sort of like a graph coloring problem. The perturbations of the points are the "colors." The colors need to obey the condition that two distances which would be equal in the unperturbed problem, after coloring are unequal. It seems "obvious" that few colors are needed by the optimum coloring. We keep re-perturbing (randomly) the points, accepting a perturbation if it decreases the number of repeated distances. Hopefully if we do this eventually only a constant fraction of the points will be bad (at most) at which point we can afford just to eliminate them. The reason this is not a proof is that we perhaps could get stuck; no perturbation will be possible that causes a decrease. Intuitively it seems like that cannot happen... This argument is quite similar to the "Rodl nibble" and a Spencer "random greedy" argument but seems not quite the same, so as yet I haven't managed to make it work. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)