---

Claim. For every $\delta>0$ there is a number $C(\delta)$ such that

$$N(X,\delta)<C(\delta)\,X^{1/2}\qquad\text{for all }X\ge1,$$

where $N(X,\delta)$ is the largest number of points in a disc of radius $X$ whose pairwise distances all lie at distance at least $\delta$ from the nearest integer, as Problem 465 defines it. This is the Theorem of Konyagin's paper (p. 630), translated from the Russian statement as the result page theorem translates it; the digest is on the source card konyagin_2001_distances_between_points_plane.

What it settles. Both questions of the problem. The bound is $o(X)$, which is the first question. For the second, given $\varepsilon>0$ one has $C(\delta)X^{1/2}\le X^{1/2+\varepsilon}$ as soon as $X\ge C(\delta)^{1/\varepsilon}$, so $N(X,\delta)<X^{1/2+\varepsilon}$ for all large $X$, which is what $N(X,\delta)<X^{1/2+o(1)}$ asks (an authored one-line remark). Konyagin's introduction states the question of Erdős and Graham in exactly this form and names a positive answer as the paper's aim. No exponent below $1/2$ holds for all small $\delta$: Sárközy's Theorem 1 of 1976 gives $N(X,\delta)>X^{1/2-\delta^{1/7}}$, compiled on Problem 466, and the lower exponent $1/2-\delta^{1/7}$ tends to $1/2$ as $\delta\to0$. The first question had been settled in 1976 by Sárközy's bound of order $X/\log\log X$, the accepted partial claim beside this page.

Argument, in outline. Exponential sums $A_k(\varphi)=\sum_je(k(x_j\cos\varphi+y_j\sin\varphi))$ averaged over the direction $\varphi$; the inequality $\sum_kd_k\int_0^{2\pi}|A_k(\varphi)|^2\,d\varphi\ge0$ for nonnegative weights; Bessel's identity, which turns each cross term into $2\pi J_0(2\pi k\,d(P_i,P_j))$; the asymptotic expansion of $J_0$; Lemma 1 (p. 632), a cosine polynomial with nonnegative coefficients that is negative together with the absolute value of its conjugate on $[2\pi\delta,2\pi(1-\delta)]$; and weights $d_k=(k/2)^{1/2}c_k$ that make the off-diagonal contribution at most $-A(2X)^{-1/2}n^2$ against error terms $O(n)$, whence $n=O(X^{1/2})$. The proof (pp. 630--633) is not checked here.

Acceptance. Refereed: S. V. Konyagin, On the distances between points on the plane (in Russian), Mat. Zametki 69 (2001), no. 4, 630--633, Brief Communications, received 21 September 2000 and revised 5 October 2000; English translation, About distances between points on the plane, Math. Notes 69 (2001), no. 3--4, 578--581 (not held). Reviewed: the site's curator, Thomas F. Bloom, marks Problem 465 PROVED and credits this paper with the bound of order $X^{1/2}$ in the problem's commentary (page last edited 18 January 2026); the curator neither wrote nor submitted the result. Not formalized: no Lean statement of the problem exists in formal-conjectures, as the problem page records, and nothing was built or audited here. The page is dated by the issue, no. 4 of the January--June volume, taken as April 2001, since the records give no finer posting date.