Distinct distances in finite planar sets (Q1377750): Difference between revisions

For each \(n\geq 3\) let \(F_n\) be the set of all integer vectors \(f=(f_1, \dots, f_n)\) which \(1\leq f_1 \leq \cdots \leq f_n\leq n-1\) for which there exists a set \(\{x_1, \dots, x_n\}\) of \(n\) points in the plane such that each \(x_i\) has exactly \(f_i\) different distances to the other \(n-1\) points. For example, \(F_3= \{(1,1,1), (1,2,2), (2,2,2)\}\). There are many questions about specific features of \(F_n\) for \(n=3,4, \dots\), but few answers. Questions referring to this are discussed by Erdős and other authors. [See also \textit{H. T. Croft}, \textit{K. J. Falconer} and \textit{R. K. Guy}, `Unsolved problems in geometry' (1991; Zbl 0748.52001); \textit{V. Klee} and \textit{S. Wagon}, `Old and new unsolved problems in plane geometry and number theory' (1991; Zbl 0784.51002) and in particular \textit{R. L. Graham} and \textit{J. Nesetril}, `The mathematics of Paul Erdős. Vol. I, II. (1997; Zbl 0857.00027, Zbl 0855.00014).] In this paper a concern is \(\Sigma_n: =\min \{\sum^n_{i=1} f_i: f\in F_n\}\) and configurations of \(n\) points that attain \(\Sigma_n\) for small \(n\). A summary of the main results is the following theorem: \((\Sigma_3, \Sigma_4, \Sigma_5, \Sigma_6, \Sigma_7, \Sigma_8) =(3,6,10,15,19,24)\). For each \(n\in \{3,4,7\}\) there are only one configuration that attain \(\Sigma_n\). For that purpose the authors prove a lot of lemmas and theorems and give a lot of instructive figures of configurations. Many different cases are discussed in detail. The authors note that every small \(n\) except \(n\in \{8,9\}\) has a subset of the triangular lattice among its sum-minimizing configurations. Parallel results for count sum minimization when the \(n\) points are the vertices of a convex polygon are given by \textit{R. Fishburn} [Algorithms Comb. 14, 284-293 (1997; Zbl 0872.52008)].