Exact extremal theory of nearly equal distances in separated planar point sets (Erdős-Makai-Pach)

A 1993 theorem of Erdős, Makai, and Pach shows that for every fixed $k$ and every $\varepsilon>0$, a separated set of $n$ points in the plane (all pairwise distances at least 1) determines at most $(n^2/2)(1-1/(k+1)+\varepsilon)$ pairs whose distance falls in the union of $k$ short intervals $[t_i, t_i+w]$ with $w = o(\sqrt n)$, and a construction of $k+1$ vertical columns shows this is asymptotically tight. Later work turned this into an exact extremal theory for few intervals: the maximum equals the Turán number $T(n, k+1)$ for $k \le 3$, and for 'generic' interval positions it drops to $n^2/4 + O(n)$, so the answer is governed by the additive structure of the interval centers $t_i$. What survives open is the exact maximum for $k \ge 4$ intervals -- equivalently the conjecture that the maximum is $T(n, k+1)$ for all large $n$, that is, that a nearly collinear, nearly $k$-distance point set in the plane never has more than $k+1$ points in the limit of vanishing nearness tolerance and flatness angle; the maximum for interval systems of intermediate additive structure (Erdős's original question in this circle, with conjectured value $(n^2/2)(1-1/k)+2n-O_k(1)$); and the sharp interval-width threshold at the $\sqrt n$ scale.

Background

Let $P$ be a set of $n$ points in the plane. Two distances are called nearly the same if they differ by at most some fixed tolerance, and a pair of points determines a nearly equal distance if the distance between the two points falls in a prescribed short interval $[t, t+w]$ rather than equaling one exact value. Counting pairs at nearly equal distances is a quantitative refinement of Paul Erdős's classical question (raised in the 1940s) on the distribution of the $\binom n2$ distances determined by $n$ planar points, of which the unit-distance problem is the most famous instance. The question is only meaningful after normalizing scale, because a tight cluster realizes all of its distances in one short interval; one therefore restricts to separated sets, meaning sets in which every pairwise distance is at least 1.

The answer turns out to be governed by extremal graph theory. Write $T(n, s)$ for the Turán number: the number of edges of the balanced complete $s$-partite graph on $n$ vertices, $T(n,s) = (n^2/2)(1-1/s) + O_s(1)$; by Turán's theorem this is the maximum number of edges of a graph on $n$ vertices containing no complete subgraph on $s{+}1$ vertices. The connection is via cluster constructions: several pairwise far-apart groups of points, with all inter-group distances falling in one of a few short intervals, contribute a complete multipartite graph's worth of nearly equal distances.

Erdős, Makai, Pach, and Spencer (1991) settled the one-interval case: for separated $n$-point sets in $\mathbb R^d$ and any $t \ge 1$, at most $T(n, d)$ pairs have distance in $[t, t+1]$ once $n$ is large (in the plane, $\lfloor n^2/4\rfloor$), the bound persists for intervals of width $c_d n^{1/d}$, and it is attained. Erdős-Makai-Pach (1993) proved the $k$-interval planar counterpart: for every fixed $k$ and $\varepsilon > 0$ there exist $n_{k,\varepsilon}$ and $c_{k,\varepsilon} > 0$ such that no separated $n$-point set in the plane and no reals $t_1, \dots, t_k \ge 1$ admit more than $(n^2/2)(1 - 1/(k+1) + \varepsilon)$ pairs at distance in $\bigcup_{i=1}^k [t_i, t_i + c_{k,\varepsilon}\sqrt n]$; the same bound holds for widths $w(n) \to \infty$ with $w(n) = o(\sqrt n)$. The bound is asymptotically tight: $k{+}1$ vertical columns of about $n/(k{+}1)$ points each, with column $i$ on the line $x = iN$ for $N$ large, realize $(n^2/2)(1 - 1/(k+1) + o(1))$ pairs at distances in $\bigcup_{i=1}^k [iN, iN + 1]$. For $k = 1$ the paper also notes that its constant-width statement fails for width $2\sqrt n$, so the largest admissible width at the $\sqrt n$ scale is itself a sharp unknown constant.

Three later threads made the asymptotics exact and revealed the mechanism.

Exact values for few intervals. The authors' sequel on two nearly equal distances in $\mathbb R^d$ (circulated as a manuscript since the 1990s, posted as arXiv:1901.01055, revised 2025) determines, for $d \ne 4, 5$, the exact two-interval maximum $T(n, m(d{-}1))$ for large $n$, where $m(d{-}1)$ is the largest size of a 2-distance set in $\mathbb R^{d-1}$, i.e. a set determining at most two distinct distances; in the plane $m(1) = 3$, giving $n^2/3 + O(n)$ and removing the $\varepsilon n^2$ error of the 1993 theorem for $k = 2$.

Nearly $k$-distance sets. Frankl and Kupavskii (2023) introduced $\varepsilon$-nearly $k$-distance sets, meaning sets whose pairwise distances all lie in a union $\bigcup_{i=1}^k [t_i, t_i + \varepsilon]$, together with the companion extremal quantity $M_k(d, n)$: the maximum, over separated $n$-point sets in $\mathbb R^d$ and reals $1 \le t_1 \le \dots \le t_k$, of the number of pairs at distance in $\bigcup_i [t_i, t_i + 1]$. They proved the sandwich $T(n, N_k(d)) \le M_k(d, n) \le T(n, N_k(d)) + \gamma n^2$ for every $\gamma > 0$ (also for widths $c\, n^{1/d}$), where $N_k(d)$ is the largest size of a $(d{-}1, \alpha)$-flat nearly $k$-distance set in $\mathbb R^d$ -- flat meaning that, seen from each of its points $p$, all vectors from $p$ to the other points of the set lie within angle $\alpha$ of some hyperplane through $p$ (the hyperplane may depend on $p$) -- the largest size being understood in the uniform sense: realized, for every $\varepsilon, \alpha > 0$, by some $\varepsilon$-nearly $k$-distance set that is $(d{-}1, \alpha)$-flat. They also proved exactness $M_k(d, n) = T(n, m_k(d{-}1))$ for large $n$ whenever $k \le 3$ or $d \ge d(k)$, where $m_k(d{-}1)$ is the largest size of a $k$-distance set in $\mathbb R^{d-1}$ (a set determining at most $k$ distinct distances; on the line, $m_k(1) = k{+}1$), and they conjecture that $N_k(d{+}1) = M_k(d)$ for all but finitely many pairs $(k, d)$, where $M_k(d)$ is the limit, as $\varepsilon \to 0$, of the largest size of an $\varepsilon$-nearly $k$-distance set in $\mathbb R^d$.

Dependence on the interval positions. The authors' second sequel, 'Nearly equal distances in the plane II' (arXiv:2112.08852, revised 2025), showed that the maximum is controlled by the additive structure of the numbers $t_1, \dots, t_k$: if they are generic, in the sense that no $t_{\ell(3)}$ lies within a fixed relative error of $t_{\ell(1)} + t_{\ell(2)}$, then the maximum is only $n^2/4 + C_{k,\delta} n$, sharp up to the value of the constant, while a single exact additive relation such as $t_2 = 2 t_1$ allows $\lfloor n^2/3 \rfloor$ pairs. The heuristic is that many pairs at nearly $k$ distances force ever more additive structure among the $t_i$.

Problem Statement

Throughout, a finite set $P \subset \mathbb R^2$ is separated if every pairwise distance is at least 1, $T(n, s)$ is the Turán number (the number of edges of the balanced complete $s$-partite graph on $n$ vertices), and an $\varepsilon$-nearly $k$-distance set is a set whose pairwise distances all lie in a union $\bigcup_{i=1}^k [t_i, t_i + \varepsilon]$ for some reals $1 \le t_1 \le \dots \le t_k$. For $k, n \ge 1$ and width $w \ge 1$, let $M_k(2, n, w)$ be the maximum, over all separated $n$-point sets $P \subset \mathbb R^2$ and all reals $1 \le t_1 \le \dots \le t_k$ (the intervals may overlap), of the number of unordered pairs $\{p, q\} \subset P$ with $\|p - q\| \in \bigcup_{i=1}^k [t_i, t_i + w]$. The arity of the symbol distinguishes the objects: the one-argument $M_k(d)$ denotes a cardinality, namely the limit, as $\varepsilon \to 0$, of the largest size of an $\varepsilon$-nearly $k$-distance set in $\mathbb R^d$, whereas the two- and three-argument forms $M_k(d, n)$ and $M_k(2, n, w)$ denote pair counts. The problem is to determine this one extremal function, and to characterize its extremal configurations, in the following interlinked regimes, all left open by the source paper and the later literature. The three regimes are independent open problems, and each named conjecture is an open sub-question of the regime in which it is stated.

1. Exact value for many intervals. Determine $M_k(2, n, 1)$ exactly for every fixed $k$ and all sufficiently large $n$. It is known that $M_k(2, n, 1) = T(n, k+1)$ for $k \le 3$ (Frankl-Kupavskii 2023; the cases $k = 1, 2$ earlier), while in general $T(n, N_k(2)) \le M_k(2, n, 1) \le T(n, N_k(2)) + \gamma n^2$ for every $\gamma > 0$, where $N_k(2)$ is the largest cardinality $N$ such that, for every $\varepsilon, \alpha > 0$, there exists a $(1, \alpha)$-flat (nearly collinear, as seen from each of its points) $\varepsilon$-nearly $k$-distance set with $N$ points in the plane; $N_k(2)$ is unknown for $k \ge 4$ (only $N_k(2) = \Theta(k)$ is known, and $N_k(2) \ge k+1$ trivially). Settle, in particular, the conjecture $N_k(2) = k + 1$, which fixes the leading constant of $M_k(2, n, 1)$ at $(1/2)(1 - 1/(k+1))$, together with the exact-maximum conjecture $M_k(2, n, 1) = T(n, k+1)$ for every $k$ and all large $n$ -- the first open case is $k = 4$, with conjectured value $(2/5)n^2 + O(1)$ -- or refute them by constructing, for every $\varepsilon, \alpha > 0$, a $(1, \alpha)$-flat $\varepsilon$-nearly $k$-distance set in the plane with more than $k+1$ points: such a family would show $N_k(2) > k+1$ and change the leading constant. The same questions apply at widths $w = c\sqrt n$ for constants $c$.

2. Dependence on the interval positions. Fix $k \ge 3$ and reals $1 \le t_1 < \dots < t_k$. The known extremes are: for generic systems -- no $t_{\ell(3)}$ in the window $[(1-\delta)(t_{\ell(1)} + t_{\ell(2)}),\ t_{\ell(1)} + t_{\ell(2)} + 2]$ for any $\ell(1) \le \ell(2) < \ell(3)$ and a fixed $\delta \in (0, 1)$ -- at most $n^2/4 + C_{k,\delta} n$ pairs, essentially sharp; and for systems containing an exact additive relation $t_{\ell(3)} = t_{\ell(1)} + t_{\ell(2)}$, as many as $\lfloor n^2/3 \rfloor$ pairs. For systems of intermediate additive structure -- neither generic nor close to an arithmetic progression -- determine the maximum number of pairs asymptotically. In particular, verify or refute Erdős's original conjecture in this circle: the maximum, taken over all separated $n$-point sets and all systems $(t_1, \dots, t_k)$ that are not close to an arithmetic progression $(t, 2t, \dots, kt)$ -- in the sequel's concrete formulation, $|t_\ell / t_1 - \ell| > \delta$ for some $2 \le \ell \le k$ and a fixed $\delta > 0$ -- is $(n^2/2)(1 - 1/k) + 2n - O_k(1)$, attained by $k$ columns; and determine for which hypotheses on the $t_i$ the interpolation values $(n^2/2)(1 - 1/s) + o(n^2)$, $3 \le s \le k-1$, arise.

3. Sharp width threshold. For fixed $k$, call a width function $w(n)$ admissible if for every $\varepsilon > 0$, $M_k(2, n, w(n)) \le (n^2/2)(1 - 1/(k+1) + \varepsilon)$ holds for all sufficiently large $n$. For each $k \ge 1$ (already $k = 1$), determine the sharp threshold constant $c_k^*$ such that $c \sqrt n$ is admissible for every $c < c_k^*$ but for no $c > c_k^*$ (the threshold exists: admissibility is monotone in $c$, the source paper's Theorem 1 gives the exact bound $\lfloor n^2/4 \rfloor$ at some width $c_1 \sqrt n$ and is, in the paper's own words, 'evidently false' at width $2\sqrt n$, and admissibility fails for all large $c$). Also determine the behavior of $M_k(2, n, w)$ for widths growing beyond order $\sqrt n$: some separated $n$-point sets, e.g. a $\sqrt n \times \sqrt n$ grid piece, fit in a disk of diameter $O(\sqrt n)$, and for such a set a single interval $[t, t + C\sqrt n]$ with $C$ large and a suitable $t$ contains all $\binom n2$ distances, so $M_k(2, n, C\sqrt n) = \binom n2$ for every large $C$ and no Turán-type bound can hold for all separated sets at such widths; the generic-position version with widths $f(n) \to \infty$ is Problem 2 of the second sequel.

References

1. P. Erdős, E. Makai, Jr., J. Pach, Nearly equal distances in the plane, Combinatorics, Probability and Computing 2 (1993), no. 4, pp. 401-408. DOI: 10.1017/S0963548300000791, https://doi.org/10.1017/S0963548300000791
2. P. Erdős, E. Makai, Jr., J. Pach, J. Spencer, Gaps in difference sets, and the graph of nearly equal distances, in: Applied Geometry and Discrete Mathematics (The Victor Klee Festschrift), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, AMS-ACM, Providence, RI, 1991, pp. 265-274. DOI: 10.1090/dimacs/004/19, https://doi.org/10.1090/dimacs/004/19
3. E. Makai, Jr., J. Pach, J. Spencer, New results on the distribution of distances determined by separated point sets, in: Paul Erdős and His Mathematics II (eds. G. Halász, L. Lovász, M. Simonovits, V. T. Sós), Bolyai Society Mathematical Studies, vol. 11, János Bolyai Mathematical Society, Budapest / Springer, Berlin, 2002, pp. 499-511, MR 2004a:52026 (no DOI registered for the chapter)
4. P. Erdős, E. Makai, Jr., J. Pach, Two nearly equal distances in R^d, arXiv:1901.01055 (v3, 6 October 2025), https://arxiv.org/abs/1901.01055
5. P. Erdős, E. Makai, Jr., J. Pach, Nearly equal distances in the plane II, arXiv:2112.08852 (v2, 7 October 2025), https://arxiv.org/abs/2112.08852
6. N. Frankl, A. Kupavskii, Nearly k-distance sets, Discrete & Computational Geometry 70 (2023), no. 3, pp. 455-494. DOI: 10.1007/s00454-023-00489-x, https://doi.org/10.1007/s00454-023-00489-x
7. J. Pach, R. Radoičić, J. Vondrák, Nearly equal distances and Szemerédi's regularity lemma, Computational Geometry: Theory and Applications 34 (2006), no. 1, pp. 11-19. DOI: 10.1016/j.comgeo.2005.06.002, https://doi.org/10.1016/j.comgeo.2005.06.002
8. J. Pach, R. Radoičić, J. Vondrák, On the diameter of separated point sets with many nearly equal distances, European Journal of Combinatorics 27 (2006), no. 8, pp. 1321-1332. DOI: 10.1016/j.ejc.2006.05.007, https://doi.org/10.1016/j.ejc.2006.05.007
9. A. Ophir, R. Pinchasi, Nearly equal distances in metric spaces, Discrete Applied Mathematics 174 (2014), pp. 122-127. DOI: 10.1016/j.dam.2014.05.010, https://doi.org/10.1016/j.dam.2014.05.010
10. L. Lichev, T. Mihaylov, Annulus graphs in R^d, Discrete & Computational Geometry 72 (2024), no. 1, pp. 379-401. DOI: 10.1007/s00454-024-00649-7, https://doi.org/10.1007/s00454-024-00649-7
11. B. S. Ho, Erdős's diameter conjecture for separated distances fails in high dimensions, arXiv:2604.15305 (2026), https://arxiv.org/abs/2604.15305