The Erdős–Fishburn total distance-count problem: the asymptotics of $\Sigma_n$ and the triangular-lattice structure of its minimizers

For a set $X$ of $n$ points in the Euclidean plane, let $d_X(x)$ be the number of distinct distances from $x$ to the other points of $X$, and let $\Sigma_n$ be the minimum of $\sum_{x\in X}d_X(x)$ over all $n$-point sets $X$. Erdős and Fishburn (Discrete Math. 175 (1997) 97-132) determined $(\Sigma_3,\dots,\Sigma_8)=(3,6,10,15,19,24)$, classified the minimizers for $n\le 7$, and proved that every small $n$ except $n\in\{8,9\}$ has a subset of the triangular lattice among its sum-minimizing configurations; the 8-point extremal configuration $H_8$ (a square with equilateral triangles erected inward on its sides, every point at exactly three distances) was attributed to Heiko Harborth, with uniqueness left open. The uniqueness of the 8-point minimizer was later resolved by Fishburn (Discrete Math. 252 (2002) 103-122), where $H_8$ is shown to be uniquely characterized among eight-point configurations and $\Sigma_9=30$ is conjectured; Nozaki and Shinohara (J. Combin. Theory Ser. A 117 (2010) 810-826) reproduce the 8-point results in the language of locally three-distance sets. Two main questions remain open: Erdős's 1975 conjecture that $\Sigma_n\ge c\,n^2/\sqrt{\log n}$ - an averaged strengthening of the distinct distances problem, which Guth and Katz (Ann. of Math. 181 (2015) 155-190) resolved only in the weaker global form $\Omega(n/\log n)$, the best known bound for the pinned single-point variant being $n^{0.864}$ due to Katz and Tardos - and the conjecture that for all sufficiently large $n$ the configurations minimizing $\Sigma_n$ are subsets of the triangular lattice. Neither the lower bound for $\Sigma_n$, the lattice conjecture, nor the value of $\Sigma_9$ has been resolved.

Background

The distinct distances problem of Erdős (1946) asks for $D(n)$, the minimum number of distinct pairwise distances determined by $n$ points in the Euclidean plane. A $\sqrt{n}\times\sqrt{n}$ section of the integer lattice determines $\Theta(n/\sqrt{\log n})$ distinct distances - the number of integers up to $N$ that are sums of two squares is $\Theta(N/\sqrt{\log N})$ by the Landau-Ramanujan theorem, and the analogous statement for the norm form $i^2+ij+j^2$ of the triangular lattice (the quadratic form giving the squared distance between two triangular-lattice points) holds by the same analytic number theory - and Erdős conjectured this to be optimal. Guth and Katz proved $D(n)=\Omega(n/\log n)$, leaving only a $\sqrt{\log n}$ gap in the count; the companion structural question, whether near-extremal configurations must have lattice structure, remains wide open.

This record concerns the per-point refinement introduced by Erdős and Fishburn in 1997. For an $n$-point set $X=\{x_1,\dots,x_n\}$, the distance count of a point $x\in X$, written $d_X(x)$, is the number of distinct distances from $x$ to the other $n-1$ points; writing $f_i=d_X(x_i)$, the nondecreasing rearrangement $f_X=(f_1\le\dots\le f_n)$ is the ordered distance-count vector, and $F_n$ denotes the family of all vectors arising this way. (In later terminology, a set every point of which has distance count at most $k$ is a locally $k$-distance set.) The paper's central quantity is

$$\Sigma_n=\min_{f\in F_n}\sum_{i=1}^n f_i,$$

the minimum total number of distinct distances seen from the points of the set. Erdős had conjectured in 1975 that every $n$-point set satisfies $\sum_{x\in X}d_X(x)\gg n^2/\sqrt{\log n}$, where $\gg$ means 'at least a fixed positive constant multiple of'; since each point of a large triangular-lattice section has distance count $\Theta(n/\sqrt{\log n})$, the conjecture is equivalent to $\Sigma_n=\Theta(n^2/\sqrt{\log n})$, that is, to the statement that lattice sections are asymptotically optimal for $\Sigma_n$. The weaker pinned question - whether some single point must determine $\gg n/\sqrt{\log n}$ distances - is also open, with best bound $n^{0.864\ldots}$ due to Katz and Tardos.

The triangular lattice $L_\Delta$ is the set of integer linear combinations of $(1,0)$ and $(1/2,\sqrt{3}/2)$, the vertex set of the regular tiling by equilateral triangles. Erdős and Fishburn proved $(\Sigma_3,\dots,\Sigma_8)=(3,6,10,15,19,24)$; for each $n\le 7$ they determined all minimizing configurations up to similarity (that is, modulo rotations, reflections, translations, and dilations of the plane), with uniqueness exactly for $n\in\{3,4,7\}$. The 8-point extremal configuration, attributed to Heiko Harborth and denoted $H_8$, is obtained from a square by erecting an equilateral triangle inward on each of the four sides; the four square vertices together with the four triangle apexes give eight points, each at exactly three distinct distances from the others, so its distance-count vector is $(3,3,3,3,3,3,3,3)$ and its total is $24$. They further observed that every small $n$ except $n\in\{8,9\}$ has a subset of $L_\Delta$ among its sum-minimizing configurations. On this evidence the paper left open: (i) Erdős's 1975 lower-bound conjecture $\Sigma_n\ge c\,n^2/\sqrt{\log n}$; (ii) the conjecture that for all sufficiently large $n$ the configurations that minimize $\Sigma_n$ are subsets of $L_\Delta$; and (iii) the uniqueness of the 8-point minimizer, which the paper reduced to two technical geometric subclaims and left unproved.

Problem Statement

Determine the minimum total distance count $\Sigma_n$ and the structure of its minimizers, in the precise form left open by Erdős-Fishburn (1997) and still unresolved.

Definitions. Throughout, $X$ ranges over sets of $n$ distinct points in the Euclidean plane $\mathbb{R}^2$; $d_X(x)$ is the number of distinct distances from $x\in X$ to the other points of $X$; the ordered distance-count vector of $X$ is the nondecreasing rearrangement of the values $d_X(x)$, $x\in X$; $\Sigma_n$ is the minimum of $\sum_{x\in X}d_X(x)$ over all $n$-point sets $X$; and $L_\Delta$, the triangular lattice, is the set of integer linear combinations of $(1,0)$ and $(1/2,\sqrt{3}/2)$.

(1) Asymptotics (Erdős 1975, restated in the source paper). Prove or refute: there exists a constant $c>0$ such that, for every integer $n\ge 2$ and every $n$-point set $X\subset\mathbb{R}^2$,

$$\sum_{x\in X}d_X(x)\;\ge\;c\,\frac{n^2}{\sqrt{\log n}};$$

equivalently, since triangular-lattice sections give $\Sigma_n\le C\,n^2/\sqrt{\log n}$, prove or refute $\Sigma_n=\Theta(n^2/\sqrt{\log n})$.

(2) Lattice structure of minimizers. Prove or refute: there exists $N_0$ such that, for every $n\ge N_0$, every configuration of $n$ points attaining $\Sigma_n$ is, up to similarity (a rotation, reflection, translation, or dilation of the plane), a subset of the triangular lattice $L_\Delta$. The only known departures from the pattern that a lattice subset attains the minimum are $n=8$ and $n=9$.

(3) Exact small values and complete classification. Continue the exact determination of $\Sigma_n$ and of all minimizing configurations: in particular determine $\Sigma_9$ - Fishburn (2002) conjectured $\Sigma_9=30$, attained by a configuration with ordered distance-count vector $(3,3,3,3,3,3,4,4,4)$ - and, as optional extensions beyond the required boundary, further exact values $\Sigma_{10},\Sigma_{11},\dots$ with full minimizer lists.

Items (1) and (2) are the core conjectures; item (3) is the finite initial segment of the same determination, whose first open case is $n=9$.

References

1. Paul Erdős and Peter Fishburn, Distinct distances in finite planar sets, Discrete Mathematics 175 (1997) 97-132. DOI 10.1016/S0012-365X(96)00145-8. https://doi.org/10.1016/S0012-365X(96)00145-8. [Introduces the distance-count vector $f_X$, the quantity $\Sigma_n$, the exact values $(\Sigma_3,\dots,\Sigma_8)=(3,6,10,15,19,24)$, and the minimizer classifications for $n\le 7$.]
2. Peter C. Fishburn, A remarkable eight-point planar configuration, Discrete Mathematics 252 (2002) 103-122. DOI 10.1016/S0012-365X(01)00134-0. https://doi.org/10.1016/S0012-365X(01)00134-0. [Resolves the uniqueness of the 8-point minimizer $H_8$ and conjectures $\Sigma_9=30$ with ordered distance-count vector $(3,3,3,3,3,3,4,4,4)$.]
3. Hiroshi Nozaki and Masashi Shinohara, On a generalization of distance sets, Journal of Combinatorial Theory, Series A 117 (2010) 810-826. DOI 10.1016/j.jcta.2009.11.001, arXiv:0906.0199. https://arxiv.org/abs/0906.0199. [Proposition 4.18 restates the 8-point minimum total 24 and the unique locally three-distance set; introduces the locally $k$-distance set framework.]
4. Adam Sheffer, Distinct Distances: Open Problems and Current Bounds, arXiv:1406.1949 (2014, revised 2018). https://arxiv.org/abs/1406.1949. [States that little is known about the lattice structure of near-optimal sets and notes the companion Erdős-Fishburn lattice conjecture for the number of distinct distances; does not list the $\Sigma_n$ problem.]
5. Larry Guth and Nets Hawk Katz, On the Erdős distinct distances problem in the plane, Annals of Mathematics 181 (2015) 155-190. DOI 10.4007/annals.2015.181.1.2, arXiv:1011.4105. https://doi.org/10.4007/annals.2015.181.1.2. [Supplies the global $\Omega(n/\log n)$ bound that leaves the averaged sum conjecture open.]
6. Nets Hawk Katz and Gábor Tardos, A new entropy inequality for the Erdős distance problem, in: Towards a Theory of Geometric Graphs, Contemporary Mathematics 342, American Mathematical Society, Providence (2004) 119-126. DOI 10.1090/conm/342/06136. https://doi.org/10.1090/conm/342/06136. [Best known pinned-distance bound $n^{0.864\ldots}$.]
7. Paul Erdős, On some problems of elementary and combinatorial geometry, Annali di Matematica Pura ed Applicata (4) 103 (1975) 99-108. DOI 10.1007/BF02414146. https://doi.org/10.1007/BF02414146. [Origin of the sum conjecture $\sum_{x\in A}d(x)\gg n^2/\sqrt{\log n}$.]
8. Paul Erdős and Peter Fishburn, Maximum planar sets that determine k distances, Discrete Mathematics 160 (1996) 115-125. DOI 10.1016/0012-365X(95)00153-N. https://doi.org/10.1016/0012-365X(95)00153-N. [Companion paper whose lattice conjecture for maximal $k$-distance sets is the structural sibling of the $\Sigma_n$ lattice conjecture.]
9. 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). https://arxiv.org/abs/1911.11688. [Computational study of remarks of Erdős-Fishburn 1996 on maximal few-distance sets; does not address $\Sigma_n$.]
10. Vojtech Bálint, Some Famous Problems of Discrete Geometry, Acta Mathematica Nitriensia 1 (2015) 24-43. DOI 10.17846/AMN.2015.1.1.24-43. https://doi.org/10.17846/AMN.2015.1.1.24-43. [Cites the 1997 paper among minimum-distance problems.]
11. Erdős Problems (erdosproblems.com), entry #604, Pinned distances, https://www.erdosproblems.com/604, and entry #89, https://www.erdosproblems.com/89. [Entry #604 records Erdős's averaged sum conjecture $\sum_{x\in A}d(x)\gg n^2/\sqrt{\log n}$ as open, with best pinned bound $n^{0.864\ldots}$ due to Katz and Tardos; entry #89 records the global distinct-distances problem as nearly solved by Guth and Katz.]