← All problems

Erdős Problem #654 — Many distances in point sets with no four concyclic

39 years old · traced to

Let x1,…,xn∈R2x_1,\ldots,x_n\in \mathbb{R}^2 with no four points on a circle. Must there exist some xix_i with at least (1−o(1))n(1-o(1))n distinct distances to other xix_i?

References

Progress summary

Refreshed
Open · progress reported

A reported construction disproves the strongest version, but it does not settle the general-position question or the weaker bound.

Erdős asked whether some point must determine nearly all distances, and Erdős–Pach separately asked whether one can force a bound exceeding one third of the points under general-position assumptions. The problem remains open in that stronger geometric setting.

Known results

  • The universal trivial bound is f(n)≥(n−1)/3f(n)\geq (n-1)/3.
  • Erdős (1997) proposed the nearly linear bound, while calling it possibly too optimistic.
  • Erdős–Pach (1987, 1990) formulated the general-position version seeking f(n)>(1/3+c)nf(n)>(1/3+c)n for fixed c>0c>0.

Aletheia construction, 2026

The Erdős Problems record credits Aletheia with a construction of nn points having no four concyclic, while every point determines at most 3n/43n/4 distinct distances. Since the points lie on two lines, this refutes the nearly-nn conjecture but neither settles the general-position version nor disproves an improved bound f(n)>(1/3+c)nf(n)>(1/3+c)n.

Current status (as of March 2026): The nearly-linear conjecture is reported false, but the general-position question and the possibility of some fixed improvement over (n−1)/3(n-1)/3 remain open.

Sources

Solutions 1

Claimed by OpenAI. For every fixed epsilon>0, the manuscript claims that all but o(n) points in any n-point planar set determine at least n^(1-epsilon) distinct nonzero distances. This also applies to the page’s sets with no four concyclic points and gives related progress on pinned distances. The exponent bound does not establish the requested (1-o(1))*n distinct distances from a point.See full solutionHide full solution