Erdős Problem #652 — 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 th…

The problem asks whether the constants governing the $k$th-smallest distance count must become unbounded as $k$ grows. Mathialagan’s published work answers this affirmatively, with the sharper order of growth $[1m\alpha_k=\Theta(\sqrt{k})$.[0m

Known results

• Elekes: for each fixed $k$, arbitrarily large configurations satisfy $R(x_k)\ll_k\sqrt n$.
• Mathialagan, 2021: for $2\le k\le n^{1/3}$, some point among any $k$ selected points determines $\gg\sqrt{kn}$ distances to an $n$-point set, yielding $\alpha_k\gg\sqrt k$.
• Mathialagan’s construction gives $\alpha_k=O(\sqrt k)$, so together the bounds imply $\alpha_k=\Theta(\sqrt k)$.

2021 theorem and subsequent confirmation

Theorem 3.6 of Mathialagan’s 2021 paper, published as Theorem 14 in the Electronic Journal of Combinatorics, supplies both the lower-bound mechanism and the matching construction. An associated discussion mentions Gemini Deepthink, but identifies the substantive solution as reliance on Mathialagan’s published theorem rather than a new AI-derived proof.

Current status (as of March 2026): The problem is resolved: $[1m\alpha_k=\Theta(\sqrt{k})$[0m, hence $[1m\alpha_k\to\infty$[0m.