SOLVED (LEAN)
This has been resolved in some other way than a proof or disproof, and that resolution verified in Lean.
Let $f(m)$ be such that if $A\subseteq \{1,\ldots,N\}$ has $\lvert A\rvert=m$ then every interval in $[1,\infty)$ of length $2N$ contains $\geq f(m)$ many distinct integers $b_1,\ldots,b_r$ where each $b_i$ is divisible by some $a_i\in A$, where $a_1,\ldots,a_r$ are distinct.
Estimate $f(m)$. In particular is it true that $f(m)\leq \sqrt{m}$?
Erdős and Surányi
[ErSu59] proved that $f(m)\geq\sqrt{m}$. Erdős and Selfridge proved (see
[Er78] and
[Er86c]) that $f(m^2)\leq 2m$, which implies $f(m)\leq 2\lceil \sqrt{m}\rceil$ for all $m$. It is unclear exactly what bound he was asking for in
[Er95c], but in general some improvement of this bound.
GPT 5.4 Pro (prompted by He, Li, and Tang) proved $f(m)\leq \lceil 2\sqrt{m}\rceil$. A corresponding lower bound was given by GPT 5.4 Pro and Aristotle; it is now known (see the paper of van Doorn, Li, and Tang
[VLT26]) that\[f(m) = \min(m, \lceil 2\sqrt{m}\rceil)\]for all $m$.
View the LaTeX source
This page was last edited 02 April 2026. View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Quanyu Tang, Terence Tao, and Wouter van Doorn
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #650, https://www.erdosproblems.com/650, accessed 2026-04-11
