Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. The answer to Problem 754 is yes: f(n)≤n2+O(1)f(n)\leq \frac{n}{2}+O(1), and with the lower bound of Avis, Erdős and Pach, f(n)=n2+O(1)f(n)=\frac{n}{2}+O(1). Konrad J. Swanepoel, Favorite distances in high dimensions, in Thirty Essays on Geometric Graph Theory (J. Pach, ed.), Algorithms and Combinatorics 29, Springer, 2013, pp. 499--519; posted as arXiv:1108.4817 on 24 August 2011. For a set SS of nn points in Rd\mathbb{R}^d and a choice r(x)>0r(x)>0 for each x∈Sx\in S, write er(S)e_r(S) for the number of ordered pairs (x,y)(x,y) of points of SS with ∣xy∣=r(x)|xy|=r(x), and fd(n)f_d(n) for the maximum of er(S)e_r(S) over all such SS and rr. The paper's Theorem A determines the error term of fd(n)f_d(n) for d≥4d\geq4:

fd(n)=(1−1⌊d/2⌋)n2+{Θ(n)d even,Θ((n/d)4/3)d odd,f_d(n)=\Bigl(1-\frac{1}{\lfloor d/2\rfloor}\Bigr)n^2+ \begin{cases}\Theta(n)&d\ \text{even},\\ \Theta((n/d)^{4/3})&d\ \text{odd},\end{cases}

with absolute implied constants, derived from the known asymptotics for the maximum number of unit-distance pairs; in dimensions 22 and 33 only bounds are known, which the source card records. For d=4d=4 this is f4(n)=12n2+O(n)f_4(n)=\frac{1}{2}n^2+O(n), the bound the site states. The step to the question is one line: if every xx in an nn-point set A⊂R4A\subset\mathbb{R}^4 has at least f(n)f(n) points of AA at some distance r(x)r(x), then n f(n)≤er(A)≤12n2+O(n)n\,f(n)\leq e_r(A)\leq\frac{1}{2}n^2+O(n), so f(n)≤n2+O(1)f(n)\leq\frac{n}{2}+O(1). Avis, Erdős and Pach had shown n2+2≤f(n)≤(1+o(1))n2\frac{n}{2}+2\leq f(n)\leq(1+o(1))\frac{n}{2}, so the two bounds together give f(n)=n2+O(1)f(n)=\frac{n}{2}+O(1). The paper's Theorems B and C add, for d≥4d\geq4, a stability statement and, for nn large in terms of dd, the extremal configurations: up to scaling, the Lenz constructions that maximize the number of unit-distance pairs, with rr constant and with exceptions in dimension 44. The paper's source card and the card of Avis, Erdős and Pach record the two results.

Acceptance. The site's curator, Thomas Bloom, marks the problem proved and credits Swanepoel's theorem for it: the site's export of 2026-09-04 labels the problem PROVED, and the community database, which follows the site's label, records the status proved (Lean) and links Ren's assembly, described below. The paper appeared as a chapter of an edited Springer volume; no evidence that the volume's chapters were refereed is recorded, so no refereed evidence is listed.

Formalization. Boris Alexeev's repository of Lean proofs of Erdős problems holds a file, linked above at a pinned commit, whose header declares it a Lean formalization of a solution to Problem 754 with Swanepoel as the informal author and the systems Codex and GPT-5.6 Sol as the formal authors; the file was added on 2026-08-17. It defines f(n)f(n) as the problem does, the largest kk such that some nn-point set in R4\mathbb{R}^4 admits a positive distance at each point with at least kk other points of the set at that distance, and its theorem erdos_754 proves f(n)≤n/2+Cf(n)\leq n/2+C for all nn with the explicit constant C=202C=202. The community database's entry for the problem links an AI-assisted development by Collin Yuanjie Ren (prepared, by its own account, with Claude Code (Claude Fable 5.1)) that formalizes the Avis–Erdős–Pach lower bound and assembles the two-sided statement f(n)=n/2+O(1)f(n)=n/2+O(1), reusing Alexeev's file for the upper bound. This corpus has built neither development nor audited their statements, so both are links here and neither is formalized evidence.