Open problems of Erdős and Fishburn on the fine structure of the planar few-distance extremal functions $g(k)$ and $f(n)$

In their 1996 paper 'Maximum planar sets that determine k distances', Paul Erdős and Peter Fishburn determined the maximum size $g(k)$ of a planar set determining exactly $k$ distinct interpoint distances for $k \le 5$ ( $g(1)=3$ , $g(2)=5$ , $g(3)=7$ , $g(4)=9$ , $g(5)=12$ ), conjectured that optimal configurations for larger $k$ come from the triangular lattice, and posed a closing list of open problems. One component of that list — the uniqueness of the 12-point five-distance maximum — was resolved affirmatively by Shinohara (2008), and the exact value $g(6)=13$ was proved by Wei (2012); for the at-most- $k$ variant $\tilde{g}(k)$ , the maximum size of a planar set determining at most $k$ distances, Wang (2025) recently established the growth rate up to constants, $k\sqrt{\log k} \lesssim \tilde{g}(k) \lesssim k\log k$ . The surviving open core asks: (i) the exact values of $g(k)$ for $k \ge 7$ and the structure of optimal sets — in particular whether any subset of the triangular lattice determines at most 12 distances with more than 27 points; (ii) whether the extremal function has plateaus $g(k)=g(k+1)$ and whether $g(k+1)-g(k) \to \infty$ ; (iii) whether the minimum-distance function satisfies $f(n+1) \le f(n)+1$ for all $n$ ; (iv) whether regular hexagonal arrays of the triangular lattice are always maximum configurations for the number of distances they determine, and whether they are the unique maxima; and (v) whether every maximum $k$ -distance set has a point incident to all $k$ distances. As of late 2025 all of these remain open; the best known constructions (Ahmed–Snevily 2013, Bao–Yu 2025) still cap 12-distance lattice sets at 27 points, and the community's evidence on the lattice-conjecture is conflicting.

Background

A finite set $X$ of points in the Euclidean plane is called a $k$ -distance set if it determines exactly $k$ distinct interpoint distances, i.e. $|D(X)| = k$ where $D(X) = \{\|x-y\| : x,y \in X, x \ne y\}$ . Write $g(k)$ for the maximum size of a planar $k$ -distance set. In the opposite direction, write $f(n)$ for the minimum number of distinct distances determined by $n$ planar points — the subject of the classical Erdős distinct distances problem (Erdős 1946), whose asymptotic order $f(n) = \Omega(n/\log n)$ was resolved by Guth and Katz (2015). Erdős and Fishburn (1996) studied the inverse function $g(k)$ for small $k$ : they proved $g(1)=3$ (equilateral triangle), $g(2)=5$ (the unique maximum being the regular pentagon $R_5$ ), $g(3)=7$ (the regular heptagon $R_7$ or the regular hexagon plus its center $R_6^+$ , and no others), $g(4)=9$ , and $g(5)=12$ , the last realized by a subset of the triangular lattice. Here $R_n$ denotes the vertices of the regular $n$ -gon and $R_n^+$ the $n$ -gon together with its center. The triangular lattice is $L_\triangle = \{a(1,0) + b(1/2, \sqrt{3}/2) : a,b \in \mathbb{Z}\}$ ; the squared distance between two lattice points whose lattice coordinates differ by $(a,b)$ is the Loeschian number $a^2+ab+b^2$ . The hexagonal array $H_s \subset L_\triangle$ is the regular hexagon of lattice points with $s$ points on each side, having $n = 6\binom{s}{2}+1 = 3s(s-1)+1$ points; it determines at most $s^2-1$ distinct distances (a bound rigorously proved as Lemma 3.2 of Balaji et al. 2019), and the exact count $k_s = |D(H_s)|$ equals $s^2-1$ for $s \le 4$ but is smaller from $s = 5$ on (for example $H_5$ determines 23 distances, as Bao and Yu 2025 also record). Erdős and Fishburn conjectured (their Conjecture 2) that for every $k > 3$ some $g(k)$ -point set lies in $L_\triangle$ , and that for $k > 7$ every maximum $k$ -distance set is similar — that is, coincides with one up to translation, rotation, reflection, and scaling — with a subset of $L_\triangle$ ; their numerical tables showed hexagonal lattice arrays determining roughly 26% fewer distances than square arrays of comparable size. Wei (2012) proved the companion conjecture $g(6)=13$ (any 14-point set determines at least 7 distances), with three optimal configurations. Ahmed and Snevily (2013) verified lower bounds by exhaustive search in bounded windows of $L_\triangle$ — the best 11-distance and 12-distance subsets both having 27 points — corrected an error in the 1996 paper's Figure 4, and argued the lattice rigidity conjecture is probably false if $g$ is increasing, exhibiting 'sparse' lattice sets with more than two points per distance. Balaji, Edwards, Loftin, Mcharo, Phillips, Rice and Tsegaye (2019) rigorously verified the 1996 remark that $R_n$ and $R_n^+$ are never optimal for $k \ge 7$ , corrected computational errors in the paper's Table 1, gave asymptotics for lattice disks ( $k \sim (2\sqrt{3}/\pi)c' \cdot n/\sqrt{\log n}$ , with $c' \approx 0.638909$ the Bernays-type constant for integers represented by $x^2+xy+y^2$ ), showed by data that lattice disks overtake hexagonal arrays at large sizes, and conjectured $f(n) \sim c\sqrt{n/\log n}$ with explicit constant $c \approx 0.7045$ built from Landau–Ramanujan-type products over primes $p \equiv 2 \pmod 3$ . Bao and Yu (2025) constructed the best known $m$ -distance lattice sets for $m = 7,\dots,34$ by two methods — maximum cliques (largest sets of points pairwise joined by an allowed edge) in the graph that joins two lattice points when their distance is among the $m$ smallest lattice distances, and equiangular hexagons (lattice hexagons with all angles equal and side lengths alternating between two adjacent values) — and their bounds for $m = 11$ and $m = 12$ both equal 27, so the 27-point threshold of that question still stands. Wang (2025) studied the at-most- $k$ variant $\tilde{g}(k) = \max\{|X| : |D(X)| \le k\}$ and proved $\tilde{g}(k) \ge (\pi/(3C(\Lambda_{\mathrm{hex}}))) \cdot k\sqrt{\log k}\,(1+o(1))$ , where $C(\Lambda_{\mathrm{hex}})$ is an explicit constant of the hexagonal lattice coming from Bernays–Landau asymptotics for the counting function of integers represented by the norm form $x^2+xy+y^2$ , while retaining the $O(k\log k)$ upper bound from Guth–Katz, together with stability theorems for near-optimizers.

Problem Statement

Let $g(k)$ denote the maximum number of points in a planar set determining exactly $k$ distinct interpoint distances; let $f(n)$ denote the minimum number of distinct distances determined by $n$ points in the plane; let $L_\triangle = \{a(1,0) + b(1/2,\sqrt{3}/2) : a,b \in \mathbb{Z}\}$ be the triangular lattice; and let $H_s \subset L_\triangle$ be the regular hexagonal array with $s$ lattice points on each side, which has $3s(s-1)+1$ points and determines $k_s$ distinct distances, where $k_s \le s^2-1$ with equality for $s \le 4$ (so $k_2 = 3$ , $k_3 = 8$ , $k_4 = 15$ ) but $k_5 = 23 < 24$ . The following questions posed by Erdős and Fishburn (1996) remain open. The five questions (1)–(5), and any separately stated sub-question within one (such as the 27-point sub-question in (1), either variant in (2), or the exact- $k_s$ versus at-most- $k_s$ reading in (4)), are independent: resolving any one of them does not settle the others. (1) Determine $g(k)$ for $k \ge 7$ and classify the maximum configurations; in particular, is there a subset of $L_\triangle$ with more than 27 points that determines at most 12 distinct distances? (The best constructions known in 2025 have exactly 27 points for both 11 and 12 distances.) (2) Can $g(k) = g(k+1)$ occur — for some $k$ , or for infinitely many $k$ — and do the differences $g(k+1) - g(k)$ tend to infinity? (3) Does $f(n+1) \le f(n) + 1$ hold for all $n$ ? (4) Is $H_s$ always a maximum configuration for the number $k_s$ of distances it determines — that is, does $g(k_s) = 3s(s-1)+1$ hold, so that no planar set determining exactly $k_s$ distances has more than $3s(s-1)+1$ points (and, in the stronger at-most reading, no planar set determining at most $k_s$ distances does)? And, if so, is $H_s$ the unique maximum $k_s$ -distance set for every $s \ge 3$ ? (5) Does every maximum $k$ -distance set have a point incident to all $k$ of its distances, i.e. a point $x$ such that every distance value in $D(X)$ occurs as $\|x-y\|$ for some $y \in X$ ? A positive or negative resolution of the Erdős–Fishburn triangular-lattice conjecture — that for every $k > 3$ some maximum $k$ -distance set lies in $L_\triangle$ , and that for $k > 7$ every maximum $k$ -distance set is similar (coinciding with a lattice subset up to translation, rotation, reflection, and scaling) to a subset of $L_\triangle$ — would resolve or substantially advance items (1), (4), and (5). Note that the source's companion sub-question on the uniqueness of the 12-point five-distance maximum was resolved affirmatively by Shinohara (2008) and is not part of what is asked here.

References

Paul Erdős and Peter Fishburn, 'Maximum planar sets that determine k distances', Discrete Mathematics 160(1-3) (1996) 115-125. DOI: 10.1016/0012-365X(95)00153-N. https://doi.org/10.1016/0012-365X(95)00153-N
Paul Erdős and Peter Fishburn, 'Distinct distances in finite planar sets', Discrete Mathematics 175(1-3) (1997) 97-132. DOI: 10.1016/S0012-365X(96)00145-8. https://doi.org/10.1016/S0012-365X(96)00145-8
Paul Erdős, 'On sets of distances of $n$ points', The American Mathematical Monthly 53(5) (1946) 248-250. DOI: 10.2307/2305092. https://doi.org/10.2307/2305092
Masashi Shinohara, 'Uniqueness of maximum planar five-distance sets', Discrete Mathematics 308(14) (2008) 3048-3055. DOI: 10.1016/j.disc.2007.08.028. https://doi.org/10.1016/j.disc.2007.08.028
Xianglin Wei, 'A proof of Erdős-Fishburn's conjecture for $g(6)=13$ ', The Electronic Journal of Combinatorics 19(4) (2012) #P38. DOI: 10.37236/2917. https://doi.org/10.37236/2917
Tanbir Ahmed and Hunter Snevily, 'Sparse Distance Sets in the Triangular Lattice', The Electronic Journal of Combinatorics 20(4) (2013) #P33. DOI: 10.37236/3263. https://doi.org/10.37236/3263
Vajresh Balaji, Olivia Edwards, Anne Marie Loftin, Solomon Mcharo, Lo Phillips, Alex Rice and Bineyam Tsegaye, 'Lattice configurations determining few distances', arXiv:1911.11688 (2019, revised 2023). https://arxiv.org/abs/1911.11688
Li-Ren Bao and Wei-Hsuan Yu, 'Constructions of Large $m$ -Distance Sets on Triangular Lattice', arXiv:2509.00880 (2025). https://arxiv.org/abs/2509.00880
Lucas Wang, 'On Few-Distance Sets in the Plane', arXiv:2510.09800 (2025). https://arxiv.org/abs/2510.09800
Larry Guth and Nets Hawk Katz, 'On the Erdős distinct distances problem in the plane', Annals of Mathematics 181(1) (2015) 155-190. DOI: 10.4007/annals.2015.181.1.2. https://doi.org/10.4007/annals.2015.181.1.2 (also arXiv:1011.4105, https://arxiv.org/abs/1011.4105)