Distribution of pairwise distances

Question

I am seeking results that describe the distribution of the set of Euclidean distances between pairs of $n$ points in a unit square in the plane. For example: All the distances could be short (a tight cluster), but not all the distances could be long (all long distances force some short distances). Are there results of this general form, constraining the possible shapes of the histogram of distances, for large $n$?

---

           
          ^{Distribution of point-to-point distances in a unit square.}

---

My actual application requires some constraints on the lengths of geodesics between points sprinkled on a surface embedded in $\mathbb{R}^3$, a surface homeomorphic to a sphere. I'm hoping the planar case will shed light on geodesic constraints.

Answer 1

Here are three conjectures, in the hopes of showing that we can say something non-trivial.

[UPDATE: This is essentially all in a paper from Erdős, "On Sets of Distances of $n$ Points", from 1946. The conjecture on maxima is in his theorem 3, though he called that part well-known. The conjecture on minima is a later theorem of Harborth, cited here, but the bound in less precise forms is also in Erdős's theorem 3. The conjecture on modes is made after Erdős's theorem 2, in the speculation that $g(n)<n^{1+\epsilon}$, after a proof that $g(n)<n^{3/2}$. Finally Erdős's theorem 1 gives bounds on the number of distinct distances, between $(n-3/4)^{1/2}-1/2$ and $cn/(\log n)^{1/2}$.]

Maxima: Among $n$ points, the maximal distance can be achieved by at most $2n$ ordered pairs. This bound will be achieved when all the points are on a Reuleaux triangle, with the three 60-degree circle arcs centered on three of the points. [Thanks to Yoav Kallus for the idea for this construction.]

Minima: Among $n$ points, the minimal distance can be achieved by at most $6n-2\sqrt{12n-3}$ ordered pairs. This bound will be achieved when $n=3k^2-3k+1$ and the points are in a hexagonal lattice with $k$ points on each side of the hexagon.

Modes: For arbitrarily large $k$ and $n$, there are configurations of $n$ points in which the modal distance is achieved by at least $kn$ ordered pairs. For example, using square lattices:

• If $k=7$, the distance of $\sqrt{5}=\sqrt{2^2+1^2}$ can be achieved by at least $7n$, and almost $8n$ ordered pairs.
• If $k=15$, the distance of $\sqrt{65}=\sqrt{8^2+1^2}=\sqrt{7^2+4^2}$ can be achieved by at least $15n$, and almost $16n$ ordered pairs.
• If $k=23$, the distance of $\sqrt{325}=\sqrt{18^2+1^2}=\sqrt{17^2+6^2}=\sqrt{15^2+10^2}$ can be achieved by at least $23n$, and almost $24n$ ordered pairs.

But the claim would be false if we replaced $kn$ by $kn^{1+\epsilon}$.

Again, these are only conjectures; I'd be happy to see proofs or alternatively configurations where the minimal or maximal or modal distance is achieved more often.

Answer 2

Let A be the measure on R^2 invariant wrt rotations about the origin with total weight at each radius equal to the frequency of that distance in your histogram. This measure is obtained by rotationally averaging the autocorrelation measure. The Fourier transform of the autocorrelation measure is nonnegative. Since the Fourier transform is equivariant under rotation, I believe this means that the Fourier transform of A must also be nonnegative. This yields some strong constraints on the histogram of distances, which are basically the entire theory behind LP bounds.