Dimension-free diameter bounds with separated pair distances
Follow the latest progress by email.
How large must the diameter of n Euclidean points be if the distances associated with distinct unordered pairs differ by at least one? The dimension-free version permits the ambient dimension to grow with n.
Why it matters and what counts as progress
Why it matters: Allowing growing ambient dimension tests whether a geometric distance-separation bound is truly dimension-free.
What counts as progress: Improve a universal diameter lower bound or construct high-dimensional configurations below the proposed bound.
How the problem developed
- 1997 · Conjecture [1]
Paul Erdős Asked in an unsolved-problems collection whether pairwise distances separated by at least one force diameter at least (1+o(1))n², independently of dimension.
Boon Suan Ho, with GPT-5.4 Pro Constructed infinitely many high-dimensional point sets with separated pair distances and diameter at most (1−1/π²+o(1))n²; the proof is formalized in Lean 4.
AI contribution
Erdős's diameter conjecture for separated distances fails in high dimensions
For infinitely many n=q+1 with q a prime power, Ho constructs n points in R^(n²−n) whose distances for distinct pairs differ by at least one but whose diameter is at most (1−1/π²+o(1))n².
Sources
Website timeline
Publication dates and editorial changes.
AI-found construction refutes the dimension-free Erdős diameter bound