← All problems

Erdős Problem #95 — The squared multiplicities of planar distances

31 years old · traced to

Let P⊂R2P\subset\mathbb{R}^2 be a set of nn distinct points, and let u1,…,utu_1,\ldots,u_t be the distinct positive distances determined by pairs of points of PP. For each ii, define the multiplicity

si=#{{p,q}⊂P:p≠q, ∣p−q∣=ui},s_i=\#\bigl\{\{p,q\}\subset P: p\ne q,\ |p-q|=u_i\bigr\},

where pairs are unordered. The question is whether, for every fixed ϵ>0\epsilon>0, there are constants CϵC_\epsilon and n0(ϵ)n_0(\epsilon) such that for every n≥n0(ϵ)n\ge n_0(\epsilon) and every such PP,

∑i=1tsi2≤Cϵn3+ϵ.\sum_{i=1}^t s_i^2\le C_\epsilon n^{3+\epsilon}.

Erdős Problem #95

Background

This squared-multiplicity quantity is an equal-distance energy: it counts pairs of point-pairs that realize the same distance. It is closely connected to the classical distinct-distances problem, which asks how few different distances an nn-point planar set can determine. Erdős posed that problem in 1946; the square lattice provides a construction with on the order of n/log⁡nn/\sqrt{\log n} distinct distances, motivating his conjecture that this order is minimal. Distinct Distances: Open Problems and Current Bounds (arXiv:1406.1949)

The connection is made by Cauchy–Schwarz: since ∑isi=(n2)\sum_i s_i=\binom{n}{2}, if D(P)=tD(P)=t is the number of distinct distances, then

D(P)∑i=1tsi2≥(n2)2.D(P)\sum_{i=1}^t s_i^2\ge \binom{n}{2}^2.

Thus an upper bound for the energy yields a lower bound for the number of distinct distances. Conversely, large energy records extensive repetition among distances. On the Erdős distinct distance problem in the plane (arXiv:1011.4105)

References

P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas 2 (1995), 165–186.

Source: P. Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas 2 (1995), 165–186.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.