← All problems

Erdős Problem #1082 — Distinct Distances from Points in General Position

1 year old · traced to

Let A⊂R2A\subset\mathbb R^2 be a finite set of n≥1n\geq 1 distinct points, with no three distinct points of AA collinear. Write

D(A)=∣{ ∣x−y∣:x,y∈A, x≠y }∣D(A)=\bigl|\{\,|x-y|:x,y\in A,\ x\neq y\,\}\bigr|

for the number of distinct distances determined by pairs in AA. The first question is whether every such AA satisfies

D(A)≥⌊n2⌋.D(A)\geq\left\lfloor\frac n2\right\rfloor.

Erdős Problems #1082 Distinct Distances: Open Problems and Current Bounds

A stronger, separate question asks whether every such set with n≥1n\geq1 contains a point aa for which the number of distinct distances from aa to the other points is at least ⌊n/2⌋\lfloor n/2\rfloor. In notation,

δA(a)=∣{ ∣a−b∣:b∈A∖{a} }∣,and the assertion is ∃a∈A: δA(a)≥⌊n2⌋.\delta_A(a)=\bigl|\{\,|a-b|:b\in A\setminus\{a\}\,\}\bigr|,\qquad \text{and the assertion is }\exists a\in A:\ \delta_A(a)\geq\left\lfloor\frac n2\right\rfloor.

This stronger assertion is false. Erdős Problems #1082

Background

The first question is the exact-constant version of asking how many distances must be determined by a planar set in general position with respect to collinearity. Szemerédi conjectured the bound ⌊n/2⌋\lfloor n/2\rfloor and proved a weaker bound with n/2n/2 replaced by n/3n/3; his proof was unpublished but was recorded by Erdős. The single-point question is stronger than the total-distance question, since distances from one point are among the distances determined by the whole set. Erdős Problems #1082 Distinct Distances: Open Problems and Current Bounds

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.