Acta Mathematica Hungarica General Mathematics

On multiplicities of interpoint distances

F. C. Clemen, A. Dumitrescu, D. Liu
Springer Nature · 2025-10-01 · DOI 10.1007/s10474-025-01562-y

Abstract

Abstract Given a set $$X\subseteq\mathbb{R}^2$$ X ⊆ R 2 of $$n$$ n points and a distance $$d>0$$ d > 0 , the multiplicity of $$d$$ d is the number of times the distance $$d$$ d appears between points in $$X$$ X . Let $$a_1(X) \geq a_2(X) \geq \cdots \geq a_m(X)$$ a 1 ( X ) ≥ a 2 ( X ) ≥ ⋯ ≥ a m ( X ) denote the multiplicities of the $$m$$ m distances determined by $$X$$ X and let $$a(X)=(a_1(X),\dots,a_m(X))$$ a ( X ) = ( a 1 ( X ) , ⋯ , a m ( X ) ) . In this paper, we study several questions from Erdős’s time regarding distance multiplicities. Among other results, we show that: (1) If $$X$$ X is convex or “not too convex”, then there exists a distance other than the diameter that has multiplicity at most $$n$$ n . (2) There exists a set $$X\subseteq\mathbb{R}^2$$ X ⊆ R 2 of $$n$$ n points, such that many distances occur with high multiplicity. In particular, at least $$n^{\Omega(1/\log\log{n})}$$ n Ω ( 1 / log log n ) distances have superlinear multiplicity in $$n$$ n . (3) For any (not necessarily fixed) integer $$1\leq k\leq\log{n}$$ 1 ≤ k ≤ log n , there exists $$ {X\subseteq\mathbb{R}^2 } $$ X ⊆ R 2 of $$n$$ n points, such that the difference between the $$k^{\text{th}}$$ k th and $$(k+1)^{\text{th}}$$ ( k + 1 ) th largest multiplicities is at least $$\Omega(\frac{n\log{n}}{k})$$ Ω ( n log n k ) . Moreover, the distances in $$X$$ X with the largest $$k$$ k multiplicities can be prescribed. (4) For every $$n\in N$$ n ∈ N , there exists $$X\subseteq\mathbb{R}^2$$ X ⊆ R 2 of $$n$$ n points, not all collinear or cocircular, such that $$a(X)= (n-1,n-2,\ldots,1)$$ a ( X ) = ( n - 1 , n - 2 , … , 1 ) . There also exists $$X\subseteq\mathbb{R}^2$$ X ⊆ R 2 of $$n$$ n points with pairwise distinct distance multiplicities and $$a(Y) \neq (n-1,n-2,\ldots,1)$$ a ( Y ) ≠ ( n - 1 , n - 2 , … , 1 ) .

Read at publisher →