Erdős Problem #223

FORMAL RESTATEMENT

Erdős #223; reconstruction of the asymptotic diameter bound, 2026-09-23. For $d\geq2$ and $n\geq2$, let $f_d(n)$ be the maximum number of unordered pairs at distance one among $n$ distinct points in $\mathbb R^d$ whose diameter is one. Estimate $f_d(n)$.

QUICK LITERATURE AND CONTEXT CHECK

The known low-dimensional answers are $f_2(n)=n$ for $n\geq3$ and $f_3(n)=2n-2$ for $n\geq4$. The small exceptions are $f_d(2)=1$ and $f_d(3)=3$. For each fixed $d\geq4$, writing $p=\lfloor d/2\rfloor$, the leading asymptotic is $(p-1)n^2/(2p)$. Swanepoel subsequently determined the exact values for all sufficiently large $n$ depending on $d$. This file reconstructs the leading asymptotic and sharp lower-dimensional examples; it uses the established low-dimensional upper bounds as named external inputs rather than reproving them.

OBJECTIVE AND ATTACK PLAN

For the lower bound, use short arcs on circles in orthogonal planes so that every cross-pair is a diameter and no within-circle distance is too large. For the upper bound, show that a certain complete multipartite graph cannot be realized even as a unit-distance graph, and invoke the Erdős--Stone theorem.

WORK

The higher-dimensional construction. For $d\geq4$ let $p=\lfloor d/2\rfloor\geq2$, and choose $p$ mutually orthogonal two-dimensional linear subspaces. In each take a circle centred at zero of radius $1/\sqrt2$. Choose $n_i$ distinct points on an arc of angular length at most $\pi/2$, with $\sum_i n_i=n$ and all $n_i$ differing by at most one. Two points on different circles have squared distance $1/2+1/2=1$. Two points on the same arc have distance at most $2(1/\sqrt2)\sin(\pi/4)=1$. For all sufficiently large $n$ the set therefore has diameter one and at least \[ \sum_{i<j}n_i n_j =\frac12\left(n^2-\sum_i n_i^2\right) =\frac{p-1}{2p}n^2-O_p(1) \tag{1} \] diameter pairs. The short-arc restriction is essential for a diameter problem; arbitrary points on a whole circle could be farther than one apart.

A forbidden multipartite graph. A unit-distance graph in $\mathbb R^d$ cannot contain $K_{p+1}(3)$, the complete $(p+1)$-partite graph with three vertices in each part. Suppose otherwise, with parts $A_1,\ldots,A_{p+1}$. Let $V_i$ be the linear space spanned by differences of points of $A_i$. It has dimension at least two. Indeed any point from another part is at distance one from all three points of $A_i$, and a line intersects a sphere in at most two points; the three points therefore cannot be collinear.

For $a,a'\in A_i$ and $b,b'\in A_j$, $i\ne j$, all four cross-distances are one. Expanding their squared norms and subtracting gives \[ |a-b|^2-|a-b'|^2-|a'-b|^2+|a'-b'|^2 =-2(a-a')\cdot(b-b')=0. \] Hence $V_i\perp V_j$. Mutually orthogonal subspaces have direct sum, so \[ d\geq\sum_{i=1}^{p+1}\dim V_i\geq2(p+1)>d, \] a contradiction.

Declared external graph theorem. Erdős--Stone says that for a fixed graph $F$ of chromatic number $r\geq3$, \[ \operatorname{ex}(n,F) =\left(1-\frac1{r-1}+o(1)\right)\frac{n^2}{2}. \tag{2} \] Apply $2$ to $F=K_{p+1}(3)$, whose chromatic number is $p+1$. The diameter graph of any candidate configuration is a unit-distance graph, and the preceding argument excludes this $F$ as a subgraph, not merely as an induced subgraph. Therefore \[ f_d(n)\leq\frac{p-1}{2p}n^2+o_d(n^2). \tag{3} \] Combining $1$ and $3$ proves the asserted asymptotic for every fixed $d\geq4$.

Low-dimensional sharp examples. In the plane take a point $O$ and $n-1$ distinct points on a unit-circle arc about $O$ whose endpoints make angle $\pi/3$, including both endpoints. For $n\geq3$, all $n-1$ radial pairs have distance one, as does the endpoint pair; every other pair on the arc has smaller distance. This gives exactly $n$ diameter pairs.

In three dimensions take $A=(-1/2,0,0)$ and $B=(1/2,0,0)$. The common intersection of their unit spheres is the circle $x=0$, $y^2+z^2=3/4$. For $n\geq4$ choose $n-2$ distinct points on an arc of this circle whose endpoints have chord length one, including both endpoints. Its angular length is $2\arcsin(1/\sqrt3)<\pi$, so all within-arc distances are at most one, with equality only for the endpoints. All $2(n-2)$ cross-pairs to $A,B$ have distance one, as do $AB$ and the endpoint pair, giving exactly $2n-2$ diameter pairs.

The matching external upper bounds are the planar diameter theorem of Hopf--Pannwitz and the Vázsonyi theorem proved independently by Grünbaum, Heppes, and Straszewicz. Together with these explicit examples they give the exact low-dimensional formulas stated above. For $n=2,3$, a pair and an equilateral triangle attain the trivial upper bound $\binom n2$.

VERIFICATION AND SCOPE

The asymptotic is for fixed $d$ as $n\to\infty$. Its geometric obstruction and lower construction are proved here; Erdős--Stone and the two low-dimensional upper theorems are declared dependencies. No claim is made to derive Swanepoel's sharper exact eventual formulas or all extremal configurations. The requested leading-order estimate and the exact two- and three-dimensional values follow from the stated inputs, with the small-order exceptions handled explicitly.

SOURCES

• Current statement and original attributions: https://www.erdosproblems.com/223.
• K. J. Swanepoel, Unit distances and diameters in Euclidean spaces, Sections 1.1--1.2 and the references there for the original low-dimensional results; the paper also gives the stronger exact eventual results: https://arxiv.org/abs/0707.0213.

CONCLUSION

Attempt status: solved at the stated estimation scope using named external theorems. The higher-dimensional leading asymptotic and the exact low-dimensional values follow. This is a reconstruction of known results, with no novelty claim. Completion rate estimate: 100%.