Erdős Problem a Daythe open tracker

Erdős Problem #652

PROVEDdatabase updated 2026-01-17

The statement as posed is true, and a proof exists.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

The positive constants \(a\) such that, for all sufficiently large \(n\), some set of \(n\) points has at least \(k\) points determining fewer than \(a\sqrt n\) distances to its other points. Counting these points expresses \(R(x_k)<a\sqrt n\) without choosing an ordering.

The infimum of the admissible positive constants for the \(k\)th smallest distance count. An infimum is used because a least constant need not exist for a strict inequality.

Let \(x_1,\ldots,x_n\in \mathbb{R}^2\) and let \(R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}\), where the points are ordered such that \[R(x_1)\leq \cdots \leq R(x_n).\] Let \(\alpha_k\) be minimal such that, for all large enough \(n\), there exists a set of \(n\) points with \(R(x_k)<\alpha_kn^{1/2}\). Is it true that \(\alpha_k\to \infty\) as \(k\to \infty\)? Mathialagan [Ma21] proved that given a set \(P\) of \(k\) points and a set \(Q\) of \(n\) points, with \(2\leq k\leq n^{1/3}\), there exists a point in \(P\) which determines \(\gg (kn)^{1/2}\) distances to points in \(Q\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 6 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/652.
Prizenone
Topicsgeometry, distances
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/652
NOBODY HAS SENT US AN ATTEMPT YET

If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.