no. 2 · Monday 26 October 2026
Counterexamples to a dimension-free variant of Erdős's diameter conjecture for separated distances
Abstract
Erdős asked about the least possible diameter of an $n$-point set in Euclidean space when any two pairwise distances differ by at least $1$. We consider the uniform-in-dimension variant of his question, in which the dimension $d$ may grow with $n$ and the error term is independent of $d$, and answer it in the negative by an explicit construction. For every prime power $q$, we construct a set $\mathcal X_n$ of $n=q+1$ points in $\mathbb R^{q^2+q}=\mathbb R^{n^2-n}$ such that the $\binom{n}{2}$ pairwise distances are mutually at least $1$ apart, yet $$\operatorname{diam}(\mathcal X_n)\le \Bigl(1-\frac{1}{π^2}+o(1)\Bigr)n^2.$$ The construction combines a Singer cyclic difference set with a weighted product of $N=\binom n2$ regular $m$-gons, where $m=q^2+q+1$. The weights are chosen so that the resulting distances increase while the gaps between consecutive distances decrease. After normalizing the smallest gap to $1$, all distinct pairwise distances are separated by at least $1$, while the diameter has asymptotic constant $1-1/π^2<1$.
- comments
- 8 pages, to appear in Discrete & Computational Geometry
- fields
- Combinatorics, Metric Geometry