Exact small values of the Erdős–Fishburn equidistant-neighbor function: uniqueness of the extremal 8-point configuration and the value of g(5)

For a finite set P of points in the plane and a point x in P, let m(x) be the largest number of other points of P at any single common distance from x (different points may use different distances). Let f(n) be the maximum, over all n-point planar sets, of the minimum of m(x) over x in P, and let g(k) be the smallest n with f(n) at least k. Erdős and Fishburn (1997) proved g(3)=6 and g(4)=8, constructed a 16-point set showing g(5) at most 16, and conjectured that their 8-point configuration — four equilateral triangles erected on the sides of a square — is the unique realization of g(4)=8 up to similarity. Of the paper's other open questions, the asymptotic conjecture f(n) at most $n^{o(1)}$ was disproved in May 2026 by OpenAI's construction of planar sets with $n^{1+\delta}$ unit distances. Two open questions remain: whether the 8-point configuration is the unique 8-point planar set, up to similarity, in which every point has four equidistant neighbors, and whether $g(5)=16$ — equivalently, whether no planar set of at most 15 points gives every point five equidistant neighbors.

Background

One of the oldest questions of combinatorial geometry, posed by Erdős in 1946, concerns repeated distances: among n points in the plane, how many pairs can lie at one common distance? Writing $\nu(n)$ for the maximum number of such unit-distance pairs over all n-point planar sets, Erdős conjectured $\nu(n)\le n^{1+o(1)}$ and proved via the integer lattice that $\nu(n)\ge n^{1+c/\log\log n}$. The present problem concerns a guaranteed-favorite-distance variant introduced by Erdős and Fishburn in 1997. For a finite planar set P and a point $x\in P$, let $m(x)$ be the largest number of other points of P lying at any single distance d from x — the size of x's largest distance class; different points are allowed to use different distances. Define $f(n)=\max_{|P|=n}\min_{x\in P} m(x)$, the largest k such that some n-point configuration gives every one of its points at least k equidistant neighbors, and its inverse $g(k)=\min\{n: f(n)\ge k\}$, the smallest number of points that forces k equidistant neighbors per point. Erdős conjectured $f(n)<n^{\varepsilon}$ for every $\varepsilon>0$ and all large n — recorded as Problem 92 in the Erdős Problems database with a 500-dollar prize for a proof and a 50-dollar prize for a disproof — which is equivalent to superpolynomial growth of g, i.e. $g(k)>k^{c}$ for every $c>0$ and all large k.

Erdős and Fishburn determined the first exact values: $g(1)=2$, $g(2)=3$, $g(3)=6$, $g(4)=8$, and they constructed a 16-point set showing $g(5)\le 16$. Their determination of $g(4)=8$ classified the 6-point sets realizing $g(3)=6$ and used that classification to rule out 7-point configurations. The 6-point extremal configurations form a one-parameter family: two translates of an equilateral triangle at a suitable offset. The 8-point configuration is, up to similarity (rotation, translation, reflection, and uniform scaling), the set obtained by erecting an equilateral triangle outward on each side of a square; with unit square side it is $\{(\pm 1/2, \pm 1/2)\}\cup\{(0, \pm(1+\sqrt{3})/2)\}\cup\{(\pm(1+\sqrt{3})/2, 0)\}$. Each square vertex has four neighbors at distance 1 (two adjacent vertices and two adjacent triangle apexes), and each apex has four neighbors at distance $\sqrt{2+\sqrt{3}}$. The 16-point construction for $g(5)\le 16$ is the union of this configuration C with a homothetic copy $(1+\sqrt{2})\cdot C$ about the common center (C scaled by the factor $1+\sqrt{2}$ from the shared center): each point keeps its four in-copy neighbors and gains exactly one partner in the other copy at the matching distance. The paper conjectured that the 8-point configuration is the unique realization of $g(4)=8$ up to similarity, and left g(5) open with 16 as the upper bound. On the asymptotic side, the best bounds at the time were $f(n)\ll n^{2/5}$ from the repeated-angles theorem of Pach and Sharir (1992), where $\ll$ suppresses an absolute constant factor, and $f(n)>n^{c/\log\log n}$ from lattice constructions.

In May 2026 the asymptotic picture changed abruptly. A team at OpenAI constructed, for infinitely many n, planar point sets with at least $n^{1+\delta}$ unit distances for some $\delta>0$, disproving Erdős's unit-distance conjecture; Sawin made the exponent concrete ($n^{1.014}$), and Alon, Bloom, Gowers, Litt, Sawin, Shankar, Tsimerman, Wang, and Wood published a human-verified digest of the argument, which rests on number-theoretic constructions (infinite towers of algebraic number fields — chains in which each field extends the previous one without any prime ramifying — whose root discriminant, the field discriminant normalized per unit degree, stays bounded). Because a unit-distance graph with average degree at least 2k contains a subgraph of minimum degree at least k, the same construction disproves the Erdős–Fishburn prediction $f(n)\le n^{o(1)}$: in fact $f(n)\ge n^{c}$ for infinitely many n, so $g(k)\le k^{O(1)}$. In the other direction, an observation recorded on the Erdős Problems #92 page (by Zach Hunter) derives $f(n)\ll n^{4/11}$ from the point–circle incidence bounds of Janzer, Janzer, Methuku, and Tardos (2024), so $g(k)\gg k^{11/4}$. The growth of g is thus now known to be polynomially bounded on both sides, with the exact exponent open, and the exact small values $g(3)=6$, $g(4)=8$, and the unresolved $g(5)$ anchor this finite regime. None of the 2026 developments, however, touches the paper's two finite questions, which remain exactly as posed.

Problem Statement

Determine the exact small-value structure of the Erdős–Fishburn equidistant-neighbor function $g(k)=\min\{n: f(n)\ge k\}$, where $f(n)$ is the largest k such that some set of n points in the plane gives every point at least k other points at a single common distance (the distance may differ from point to point). Concretely, resolve the two questions left open by Erdős and Fishburn (1997):

(1) Uniqueness at k=4. Is the 8-point configuration — up to similarity (rotation, translation, reflection, and uniform scaling), $\{(\pm 1/2, \pm 1/2)\}\cup\{(0, \pm(1+\sqrt{3})/2)\}\cup\{(\pm(1+\sqrt{3})/2, 0)\}$, four equilateral triangles erected outward on the sides of a square — the unique 8-point planar set in which every point has at least four equidistant neighbors? Answering this requires classifying all such 8-point sets up to similarity and deciding whether the classification consists of this single similarity class.

(2) The value of $g(5)$. Does $g(5)=16$, or could a smaller number of points suffice? Prove that no planar set of at most 15 points gives every point five equidistant neighbors — which, together with the known 16-point construction, establishes $g(5)=16$ — or exhibit such a set of at most 15 points, showing that a smaller number of points suffices.

These two questions share one objective, the exact finite structure of g, and are linked: the known 16-point upper-bound construction is two nested copies of the 8-point configuration in (1).

References

1. Paul Erdős and Peter Fishburn, 'Minimum planar sets with maximum equidistance counts', Computational Geometry 7(4):207–218, 1997. DOI: 10.1016/0925-7721(95)00050-X, https://doi.org/10.1016/0925-7721(95)00050-X
2. OpenAI, 'Planar Point Sets with Many Unit Distances', technical report, May 2026. https://cdn.openai.com/pdf/74c24085-19b0-4534-9c90-465b8e29ad73/unit-distance-proof.pdf (no arXiv or journal counterpart as of September 2026)
3. Will Sawin, 'An explicit lower bound for the unit distance problem', arXiv:2605.20579, 2026. https://arxiv.org/abs/2605.20579
4. Noga Alon, Thomas F. Bloom, W. T. Gowers, Daniel Litt, Will Sawin, Arul Shankar, Jacob Tsimerman, Victor Wang, Melanie Matchett Wood, 'Remarks on the disproof of the unit distance conjecture', arXiv:2605.20695, 2026. https://arxiv.org/abs/2605.20695
5. János Pach and Micha Sharir, 'Repeated angles in the plane and related problems', Journal of Combinatorial Theory, Series A 59(1):12–22, 1992. DOI: 10.1016/0097-3165(92)90094-B, https://doi.org/10.1016/0097-3165(92)90094-B
6. P. Erdős, 'On Sets of Distances of n Points', The American Mathematical Monthly 53(5):248, 1946. DOI: 10.2307/2305092, https://doi.org/10.2307/2305092
7. Wenhua Lan, Xianglin Wei, Ren Ding, 'On 5-isosceles sets in the plane, with linear restriction', Journal of Applied Mathematics and Computing 28(1–2):381–390, 2008. DOI: 10.1007/s12190-008-0112-x, https://doi.org/10.1007/s12190-008-0112-x
8. Vojtech Bálint, 'Some Famous Problems of Discrete Geometry', Acta Mathematica Nitriensia 1(1):24–43, 2015. DOI: 10.17846/amn.2015.1.1.24-43, https://doi.org/10.17846/amn.2015.1.1.24-43
9. Barnabás Janzer, Oliver Janzer, Abhishek Methuku, Gábor Tardos, 'Tight bounds for intersection-reverse sequences, edge-ordered graphs and applications', arXiv:2411.07188, 2024. https://arxiv.org/abs/2411.07188
10. Erdős Problems database (curated by Thomas Bloom), Problem 92: favorite distances / equidistant neighbors, with a 500-dollar prize. https://www.erdosproblems.com/92
11. Erdős Problems database (curated by Thomas Bloom), Problem 90: unit distances. https://www.erdosproblems.com/90