Problem 465

Let $N(X,\delta)$ denote the maximum number of points $P_1,\ldots,P_n$ which can be chosen in a circle of radius $X$ such that

\| \lvert P_i-P_j\rvert \| \geq \delta

for all $1\leq i<j\leq n$ . (Here $\|x\|$ is the distance from $x$ to the nearest integer.)

Is it true that, for any $0<\delta<1/2$ , we have

N(X,\delta)=o(X)?

In fact, is it true that (for any fixed $\delta>0$ )

N(X,\delta)<X^{1/2+o(1)}?

Source: erdosproblems.com/465

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED, the site's label (page last edited 18 January 2026), which credits Sárközy [Sa76] with the first conjecture and Konyagin [Ko01] with the bound of order $X^{1/2}$ . The accepted claim pages are Konyagin 2001, the full claim: for every $\delta>0$ there is $C(\delta)$ with $N(X,\delta)<C(\delta)X^{1/2}$ for all $X\ge1$ (Mat. Zametki 69 (2001), refereed; p. 630), which is $o(X)$ and, for any $\varepsilon>0$ , below $X^{1/2+\varepsilon}$ as soon as $X\ge C(\delta)^{1/\varepsilon}$ , the second question's $N(X,\delta)<X^{1/2+o(1)}$ (an authored one-line remark); and Sárközy 1976, the partial claim that settled the first question earlier: $N(X,\delta)<(4\cdot10^4/\delta^3)\,X/\log\log X$ for $X$ large depending on $\delta$ (Part I, Studia Sci. Math. Hungar. 11 (1976), refereed; p. 38). Each is accepted on its refereed publication and the curator's credit. No exponent below $1/2$ holds for all small $\delta$ : Sárközy's Theorem 1 of Part II gives $N(X,\delta)>X^{1/2-\delta^{1/7}}$ for $0<\delta\le1/(6\cdot8^4)$ and large $X$ (compiled on Problem 466), and the lower exponent $1/2-\delta^{1/7}$ tends to $1/2$ as $\delta\to0$ .

Ko01: Konyagin, S. V., On the distances between points on the plane (in Russian). Mat. Zametki 69 (2001), no. 4, 630--633, DOI 10.4213/mzm691 (received 21 September 2000, revised 5 October 2000); English translation: About distances between points on the plane, Math. Notes 69 (2001), no. 3--4, 578--581, DOI 10.1023/A:1010276601734 (records accessed; the translation is not held). The Theorem, p. 630. Library home: Konyagin 2001.
Sa76: Sárközy, A., On distances near integers. I, II. Studia Sci. Math. Hungar. 11 (1976), 37--50 (received 10 December 1975) and 105--111 (received 11 February 1976). Part I: the Theorem, p. 38; Part II: Theorem 1 and its Corollary, pp. 106--107, and Graham's construction, pp. 105--106. Library homes: Sárközy 1976 and Sárközy 1976 (both in the REAL-J open scan of the whole 1976 volume).
ErGr80: Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28, Université de Genève (1980). Printed pp. 92--93: the passage quoted below. Library home: Erdős and Graham 1980.
Er82e: Erdős, P., Some of my favourite problems which recently have been solved. Proceedings of the International Mathematical Conference (Singapore, 1981), North-Holland Math. Stud. 74 (1982), 59--79. Chapter II, §9, printed pp. 67--68. Library home: Erdős 1982.
Er72: Erdős, P., Extremal problems in number theory. Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, 1972), 80--86. Section IV, printed p. 83; the site keys this paper for Problem 466 only, but the passage reports the upper bound too. Library home: Erdős 1972.
GoMo26: Goenka, R. and Moore, K., Point sets avoiding near-integer distances. arXiv:2605.06621v1 (7 May 2026; abstract accessed). A lead on the higher-dimensional analog, named with its identifier.

Problem 465

Status

Proof claims

Discussion