Erdős problem #1083 — wave 8d report
Date of audit: 2026-07-28 (UTC)
This report gives two concrete outputs. First, it proves an elementary,
dimension-uniform finite regime:
\[ f_d(n)=1\quad(2\leq n\leq d+1),\qquad f_d(n)=2\quad\left(d+2\leq n\leq {d+1\choose2}\right) \tag{1} \]for every \(d\geq3\). Second, published few-distance classifications,
combined with exact-arithmetic witnesses checked here from scratch, give
all the values of \(f_3(n)\) through \(n=21\) and of \(f_4(n)\) through
\(n=25\). These are finite results and do not settle the fixed-\(d\),
\(n\to\infty\) question.
The labels used throughout are:
- (a) elementary-rigorous: a proof is included and does not use an
external theorem;
- (b) rigorous-modulo-named-theorem: the precise external theorem is
named and linked;
- (c) plausible/structural-unverified: a search result, diagnosis, or
proposed route that is not a theorem;
- (d) computational-only: established by the supplied computation,
with its scope stated explicitly.
0. Mandatory live-page audit
I fetched both the live page, its
LaTeX view, and its
through a Bright Data browser session on 2026-07-28. Direct page status
and metadata below are live-page observations, not mathematical
inferences.
Verbatim current statement
> Let $d\geq 3$, and let $f_d(n)$ be the minimal $m$ such that every set of $n$ points in $\mathbb{R}^d$ determines at least $m$ distinct distances. Estimate $f_d(n)$ - in particular, is it true that\[f_d(n)=n^{\frac{2}{d}-o(1)}?\]
Everything currently listed on the page
- Status: OPEN. The page was last edited 16 October 2025.
- Erdős is credited with
\[ n^{1/d}\ll_d f_d(n)\ll_d n^{2/d}, \]
with the upper bound supplied by lattice points.
- Clarkson, Edelsbrunner, Gubias, Sharir, and Welzl are credited with
\(f_3(n)\gg n^{1/2}\).
- Aronov, Pach, Sharir, and Tardos are credited with
\[ f_d(n)\gg n^{1/(d-90/77)-o(1)} \]
for \(d\geq3\), including exponent \(0.546\) for \(d=3\).
- Solymosi and Vu are credited with \(f_3(n)\gg n^{3/5}\) and
\[ f_d(n)\gg_d n^{2/d-c/d^2}\qquad(d\geq4) \]
for some \(c>0\). The page explicitly says that its displayed
three-dimensional consequence combines their recursion with the
Guth–Katz planar result and is slightly stronger than the result
printed in their paper.
- The page states the inverse relation
\(g_d(n)>m\) iff \(f_d(m) #1089, and emphasizes fixed \(d\) with \(n\to\infty\). collaborating”, “Currently working on this problem”, both difficulty votes, and both formalisation-work markers are all None. “Slight typo, Gubias should be spelled Guibas.” Thus the requested collision/claimed-proof stop rule did not trigger. (b) Solymosi and Vu, *Near optimal bounds for the Erdős distinct distances problem in high dimensions*, Combinatorica 28 (2008), 113–125 (author PDF, DOI), really does state in its abstract and Corollary 1.4 for \(d\geq4\). This verifies the paper and the \(2/d-O(d^{-2})\) form cited by the live page; the live page's \(d=3\) update is recorded above exactly as the page states it. (b) Bardwell-Evans and Sheffer, *A Reduction for the Distinct Distances Problem in \(\mathbb R^d\)*, arXiv:1705.10963v2, J. Combin. Theory Ser. A 166 (2019), 171–225 (DOI), supplies the sharpest concrete reduction I found. Its exact bottleneck is recorded in Section 4 below. There are two easy-to-find preprints whose abstracts appear to close the problem; neither provides a usable solution. arXiv:2002.01248, claimed \(\Omega(n^{2/d})\) for \(d\geq3\), but the authoritative arXiv record is withdrawn and says: “the proof of Theorem 1.2 is not correct.” It is therefore not evidence that #1083 is solved. arXiv:2002.00502v10, last revised 6 May 2026, is not withdrawn and claims \(\gg n^{2/k-o(1)}\). The claimed conclusion does not follow from its proof for elementary quantifier reasons: 1. Problem #1083 asks for a lower bound for every \(n\)-point configuration. The proofs of Theorems 3.1 and 3.2 instead begin “carefully choose \(n\) points” and conclude only for that chosen construction. An existential construction can upper-bound \(f_d(n)\); it cannot supply the required lower bound. 2. In the proof of Theorem 3.2, the summation is restricted by \(d_i\ne d_j\) before the number of distinct gaps has been proved. This assumes the distinctness that the argument is meant to establish. 3. The unit-distance proof at one point takes the cardinality of a set of numerical distances all constrained to equal \(1\). Such a set has cardinality at most one; it is not the number of ordered or unordered point pairs at unit distance. Any one of (1)–(3) blocks the claimed application. This is a direct logical audit of the current v10 text, not an appeal to reputation or citation counts. (c) I searched exact-title, exponent, incidence, and higher- dimensional-distinct-distance queries through July 2026. I found special-configuration results (curves, surfaces, other norms), the two claims audited above, and the 2019 reduction, but no verified unconditional improvement beyond the live page's displayed Solymosi–Vu/Guth–Katz consequences for arbitrary Euclidean point sets. This is an honest search miss, not a theorem that no such paper exists. It agrees with the live page's current OPEN status and displayed best bounds. For \(s\geq0\), define Lemma (a). If \(M_d(s-1) \(Y\subset\mathbb R^d\), \(N\geq n\), having at most \(s\) distances, then \(f_d(n)=s\). Proof. An \(n\)-point set with at most \(s-1\) distances would contradict \(n>M_d(s-1)\), so every \(n\)-point set has at least \(s\) distances. Any \(n\)-point subset of \(Y\) has at most \(s\) distances. The two inequalities give equality. \(\square\) (a) At most \(d+1\) points in \(\mathbb R^d\) can be equidistant. Indeed, after choosing one point as the origin, the \(r\) difference vectors of an equilateral \((r+1)\)-point set have Gram matrix with diagonal \(\lambda^2\) and off-diagonal \(\lambda^2/2\). Its eigenvalues are positive, so it has rank \(r\), whence \(r\leq d\). The \(d+1\) standard basis vectors in their \(d\)-dimensional affine hull attain the bound. Consequently, (a) Now take the Johnson configuration \(\sum x_i=2\). Its affine dimension is \(d\): relative to \(e_0+e_1\), the vectors are \(d\) independent differences. Two distinct two-element supports intersect in zero or one element, so their squared distance is, respectively, \(4\) or \(2\). Both cases occur because \(d+1\geq4\). Applying the lemma proves (1) for every \(d\geq3\). The following are theorem inputs, not conclusions of the supplied checker. | input | exact value | source and scope | |---|---:|---| | \(M_3(2)\) | 6 | (b) Nozaki–Shinohara's table of known optimal two-distance sets, arXiv:0906.0199, citing the Croft and Einhorn–Schoenberg classifications | | \(M_4(2)\) | 10 | (b) the same table, citing the four-dimensional classification and Lisoněk's construction | | \(M_3(3)\) | 12 | (b) Shinohara, arXiv:1309.2047, and the independent verification in Szöllősi–Östergård, Theorem 4.5 | | \(M_3(4)\) | 13 | (b) Szöllősi–Östergård, Theorem 4.3 | | \(M_4(3)\) | 16 | (b) Szöllősi–Östergård, Theorem 4.4 | | \(M_3(5)\) | 20 | (b) Nozaki–Shinohara, Theorem 1.2, arXiv:2009.13111 | The Szöllősi–Östergård source is *Constructions of maximum few-distance sets in Euclidean spaces*, arXiv:1804.06040, Electronic Journal of Combinatorics 27(1) (2020), P1.23 (DOI). Its classification proofs use isomorph-free graph generation and Gröbner bases. I treat those published classification theorems as named inputs (b); I do not pretend that the small verifier below reproduces their exhaustive searches. Since the maxima for fewer distances in each row are strictly smaller, the cited “exactly \(s\)-distance” classifications give the displayed “at most \(s\)” values. Put \(\phi=(1+\sqrt5)/2\). The three-dimensional coordinate families used are: All signs in a displayed family vary independently. In dimension four, the witnesses are the five standard basis vectors in their affine hull, \(J(5,2)\), the rational squared-distance matrix \(G_{16}(1,2,3)\) printed in the verifier, and the 24-cell The complete exact profiles are: | ambient dimension | witness | size | distinct squared distances | |---:|---|---:|---| | 3 | \(T\) | 4 | \(\{8\}\) | | 3 | \(O\) | 6 | \(\{2,4\}\) | | 3 | \(I\) | 12 | \(\{4,6+2\sqrt5,10+2\sqrt5\}\) | | 3 | \(I\cup\{0\}\) | 13 | previous set plus \(\{(5+\sqrt5)/2\}\) | | 3 | \(D\) | 20 | \(\{4,6-2\sqrt5,6+2\sqrt5,8,12\}\) | | 3 | \(D\cup\{0\}\) | 21 | previous set plus \(\{3\}\) | | 4 | regular 4-simplex | 5 | \(\{2\}\) | | 4 | \(J(5,2)\) | 10 | \(\{2,4\}\) | | 4 | \(G_{16}(1,2,3)\) | 16 | \(\{1,2,3\}\) | | 4 | \(C_{24}\cup\{0\}\) | 25 | \(\{2,4,6,8\}\) | The coordinate identities in this table are (a): they are direct algebra in \(\mathbb Q(\sqrt5)\). The \(G_{16}\) realization is additionally checked (d) as follows. Anchor its sixteenth point at zero and form twice the \(15\times15\) Gram matrix Exact rational symmetric Schur-complement elimination finds \(C\) positive semidefinite of rank \(4\), and reconstructs every entry of the prescribed distance matrix. Thus it is an exact Euclidean distance matrix for 16 distinct points in \(\mathbb R^4\), with no floating-point tolerance. Combining the bridge lemma, the named maximum theorems, and arbitrary subsets of the witnesses gives: | dimension | exact values | |---:|---| | 3 | (b) \(f_3(n)=1\) for \(2\leq n\leq4\); \(=2\) for \(5\leq n\leq6\); \(=3\) for \(7\leq n\leq12\); \(=4\) for \(n=13\); \(=5\) for \(14\leq n\leq20\); \(=6\) for \(n=21\) | | 4 | (b) \(f_4(n)=1\) for \(2\leq n\leq5\); \(=2\) for \(6\leq n\leq10\); \(=3\) for \(11\leq n\leq16\); \(=4\) for \(17\leq n\leq25\) | For \(n=1\), the natural convention gives \(f_d(1)=0\) (a). The verifier is It uses only the Python standard library. It performs exact arithmetic in \(\mathbb Q(\sqrt5)\) or \(\mathbb Q\), checks distinctness, all pairwise squared-distance multiplicities, affine dimensions, the \(G_{16}\) Gram certificate, the interval bookkeeping, and a regression sample of the dimension-uniform Johnson construction. It explicitly prints the classification values as theorem inputs rather than silently assuming that it proved them. Run: The 2026-07-28 run ended: The fact that this particular execution passed is (d). Every coordinate identity checked by it can also be read as the finite exact algebra described above; no randomized search or numerical solver is used. Here \(N\) denotes the number of flats, to avoid confusing it with a point-set size elsewhere. (b) Bardwell-Evans–Sheffer Theorem 1.2 reduces the desired \(\Omega(n^{2/d})\) lower bound to this rich-point problem. Given \(N\) distinct \((d-1)\)-flats in \(\mathbb R^{2d-1}\), assume: 1. every two flats meet in at most one point; 2. every point is incident to \(O(\sqrt N)\) flats; and 3. every hyperplane contains \(O(\sqrt N)\) of the flats. For \(2\leq k=O(N^{1/d+\varepsilon})\), proving for the specially structured flats produced by their reduction would give the conjectured \(\Omega(n^{2/d})\) distinct-distance bound. The word “specially” is essential. The paper explicitly says that (2) is false for arbitrary flats even under the three displayed conditions; further restrictions inherited from its \(\operatorname{Spun}(d)\)/Lie-group construction must be used. Polynomial partitioning handles the analogous \((d-1)\)-flat problem in \(\mathbb R^{2d-2}\), while \(\mathbb R^{2d-1}\) is described there as just beyond the method's capabilities. For \(d=3\), the paper isolates an even more concrete possible missing lemma: a sufficiently strong distinct-distance theorem for points on an arbitrary constant-degree surface in \(\mathbb R^3\). At the time of that paper, the requisite form was available for planes, spheres, and two-sheeted hyperboloids, but not arbitrary constant-degree surfaces. Thus a legitimate asymptotic advance must either: satisfied by the \(\operatorname{Spun}(d)\) flats; or codimension-one incidence loss (and, for \(d=3\), the general-surface obstruction). Merely proving an incidence statement for arbitrary flats cannot work, because the cited paper gives counterexamples to that formulation. This is the exact missing structural lemma exposed by the strongest verified reduction found in this audit. (c) Extending the three-dimensional table by the same method would require either a 22-point six-distance witness or a proof/classification of \(M_3(6)\). I did not locate such a classification in the audited few-distance literature. (a) A deliberately naive labeled search for a 22-point six-distance set starts with six colors on the \({22\choose2}=231\) edges: assignments. Even at the unrealistically generous rate of \(10^9\) assignments per core-second, this is about \(10^{167.197}\) core-hours (a). At an assumed \(10^5\) exact Gram/rank checks per core-second (c), it would be about \(10^{171.197}\) core-hours (a). The verifier independently prints both orders of magnitude (d). These figures are only the raw-space cost, not a complexity lower bound: isomorph-free generation, distance-color permutations, forbidden minors, and incremental rank/Gröbner constraints can prune enormously. A credible next computation would have to implement all of those ideas; blind enumeration is not a few-CPU-minute experiment. Finally, no finite list of exact values supplies the uniform \(n\to\infty\) step. The results in Section 2 are genuine exact progress, but the incidence estimate (2), or an equally strong replacement, remains necessary for the question on the live page. PARTIAL: Exact values (modulo named published few-distance classifications) are established for \(f_3(n)\) through \(n=21\) and \(f_4(n)\) through \(n=25\), with an elementary all-\(d\) two-distance interval and exact-arithmetic witnesses; the asymptotic conjecture remains at the structured rich-flat incidence bottleneck.
1. Primary-source literature audit
Verified asymptotic sources
Auditing papers that claim the full exponent
2. Exact finite progress
The bridge from few-distance sets to \(f_d\)
A dimension-uniform elementary interval
Named classification inputs
Explicit witnesses and exact distance checks
Resulting exact table
3. Standalone reproducibility
runs/erdos1083_wave8d_reverify.py.python runs/erdos1083_wave8d_reverify.py
PASS G16 distance matrix: 16 distinct abstract points, squared distances {1,2,3}, exact Gram PSD rank 4
...
ALL EXACT-ARITHMETIC CHECKS PASSED
4. What remains asymptotically: a precise incidence wall
5. The next finite wall and its cost