← All problems

Erdős Problem #756 — Rich Distances in Planar Point Sets

1 year old · traced to

For a finite set A⊂R2A\subset\mathbb R^2, let D(A)D(A) be the set of distances between distinct points of AA, and for d∈D(A)d\in D(A) define its multiplicity by

mA(d)=∣{{x,y}⊂A:x≠y, ∣x−y∣=d}∣.m_A(d)=\bigl|\{\{x,y\}\subset A:x\ne y,\ |x-y|=d\}\bigr|.

For each positive integer nn, let

R(n)=max⁡∣A∣=n∣{d∈D(A):mA(d)≥n+1}∣,R(n)=\max_{|A|=n}\bigl|\{d\in D(A):m_A(d)\ge n+1\}\bigr|,

where the maximum is over all nn-point subsets of the plane. Is there a constant C>0C>0 and an integer NN such that n≤CR(n)n\le C R(n) for every n≥Nn\ge N? Equivalently, can an nn-point planar set determine at least cnc n distinct distances, each occurring for more than nn unordered pairs, for some constant c>0c>0 and all sufficiently large nn? Erdős Problems #756 Bhowmick, A problem of Erdős about rich distances

Background

Erdős posed the question in 1997. An earlier, stronger question of Erdős and Pach asked whether all distances other than the largest could occur more than nn times. The largest distance cannot do so: Hopf and Pannowitz proved that it occurs at most nn times. The related question of whether a second-largest distance must occur more than nn times is distinct from the linear-count question formulated here. Erdős Problems #756 Bhowmick, A problem of Erdős about rich distances

References

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.