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 $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairwise distances are mutually at least $1$ apart, yet $$\mathrm{diam}({\mathcal{X}}_n)\le (1-\frac{1}{{\pi }^2}+o(1))n^2.$$ The construction combines a Singer cyclic difference set with a weighted product of $N=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 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/{\pi }^2<1$.

arXiv comment8 pages, to appear in Discrete & Computational Geometry