Problem 650

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}$ ?

Source: erdosproblems.com/650

Number theory

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

Solved, in the site's label, which attaches to the estimate: $f(m)=\min(m,\lceil2\sqrt m\rceil)$ for every $m\ge1$ , and $f(m)=\lceil2\sqrt m\rceil$ for $m\ge4$ (van Doorn, Li and Tang, Theorem 2.1 and Remark 2.2, arXiv:2603.28636v1, 30 March 2026). Consequently the displayed question is answered no: $f(m)>\sqrt m$ for every $m\ge2$ ( $f(m)=m$ for $m\le4$ and $\lceil2\sqrt m\rceil>\sqrt m$ after), with equality only at $m=1$ ; the negative answer is recorded here. The status-defining source is an arXiv preprint with no journal record found in the search; the site accepted it (SOLVED (LEAN), 2 April 2026), and an external Lean formalization accompanies it. The paper declares that its proof strategy was proposed by ChatGPT (GPT-5.4 Pro) and that Aristotle, Harmonic's automated theorem-proving system, completed and formally verified the argument, with the exposition human-written; the site's commentary credits the upper bound to GPT 5.4 Pro, prompted by He, Li and Tang, and the lower bound to GPT 5.4 Pro and Aristotle, before citing the paper. The classical bounds are Erdős and Surányi's $f(m)\ge\sqrt m$ (1959) and Erdős and Selfridge's $f(k^2)\le2k$ , hence $f(m)\le2\lceil\sqrt m\rceil$ (1978 and 1986). The site's label carries the suffix (Lean), a catalog label explained under Formalization and the Lean label, and no local kernel credit is claimed. The claim page van Doorn, Li and Tang 2026 records the acceptance with its preprint qualification, and the frontmatter standing derives from it.

VLT26: van Doorn, W., Li, Y. and Tang, Q., Optimal bounds for an Erdős problem on matching integers to distinct multiples. arXiv:2603.28636v1 (30 March 2026; the only version; no journal reference), 8 pages; Theorem 2.1 and Remark 2.2, pp. 2--3; Theorem 3.1, p. 4; Theorem 4.1, p. 5; Section 5, p. 7. Library home: Doorn 2026; result pages Theorem 2.1, Theorem 3.1 and Theorem 4.1; the definitions are on the source digest.
ErSu59: Erdős, P. and Surányi, J., Megjegyzések egy versenyfeladathoz. Mat. Lapok 10 (1959), 39--48; Section 11, printed pp. 45--46, and the German summary, p. 48. Library home: Erdős and Surányi 1959; result page Section 11.
Er86c: Erdős, P., Some problems on number theory. Analytic and Elementary Number Theory (Marseille, 1983), Publ. Math. Orsay 86-1 (1986), 53--67 (venue per the Erdős archive's list, entry 1986-15, and zbMATH Zbl 0584.10002; the scan carries no journal header); the theorem with Selfridge stated on printed p. 60 and proved on pp. 60--62. Library home: Erdős 1986; result page the Erdős–Selfridge theorem (p. 60).
Er78: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), Congressus Numerantium XXI (1978), 29--40; Section 6, Theorem 1, printed p. 36, proof on pp. 36--38. Library home: Erdős 1978 (the card's row for this problem carries the same locator).
Er95c: Erdős, P., Some problems in number theory. Octogon Math. Mag. 3 (1995), 3--5; the site cites p. 5. Not held; no open copy is known; its passage is paraphrased below from the site curator's transcription in the thread (7 March 2026).
OEIS: Speed, S., Sequence A027434, The On-Line Encyclopedia of Integer Sequences (1999): the sequence with successive run lengths $1,1,2,2,3,3,\ldots$ , which the thread identifies with $f$ after a shift and a change to the first few terms.

Problem 650

Status

Proof claims

Discussion