Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let . Does there exist a (depending on ) such that, for all sufficiently large , if has then
Let . Does there exist a (depending on ) such that, for all sufficiently large , if with has then
Source: erdosproblems.com/784
An accepted solution exists. The statement is false.
The site labels the problem SOLVED and credits Ruzsa and Weingartner (page last edited 8 April 2026, accessed 2026-09-05 and 2026-10-07; two thread comments, no proof claim). For the corrected Statement the answer is yes for and no for , so the bound fails when it is asked for every , as Erdős expected it to hold. For the union bound leaves at least integers unsifted. Ruzsa (J. Number Theory 14 (1982), a refereed journal) proves , the lower bound answering yes at , and for , so for fixed the unsifted count can be , below every ; Erdős's 1980 survey acknowledges that Ruzsa's construction overturned his expectation. Weingartner (Res. Number Theory 11 (2025), refereed) sharpens this to uniformly for , and Saias (1998) gives the matching upper bound . Claim pages: Ruzsa 1982 and Weingartner 2025 (both accepted). When consists of primes, Erdős and Ruzsa (1980) show a positive proportion of the integers up to is always left unsifted, a restricted variant.
The site's wording fails for every at the set : its reciprocal sum is , every is divisible by , and nothing up to is left unsifted, so the answer is no for a reason that has nothing to do with sieving. The failure was observed in a thread comment by jif of 18 December 2025 (thread), which also noted the union bound for , and the site's commentary records it. The change inserts "with " after "", in the form of the condition that defines the quantity in the problem's own sources. The evidence, strongest first: Erdős and Ruzsa [ErRu80], p. 386, define the least unsifted count for general sets over the subject to and (display (1.5)) and announce for it the limit of that answers this question; in Erdős's own [Er73], p. 135, the question is stated for , and the coprime question printed next to it, display (14.3), takes ; Ruzsa [Ru82] (display (1.3)) and Weingartner [We25] (the paper's condition (3)) define the quantity they estimate with excluded; and the site's commentary defines as the minimum over subsets of and says that the question asks whether . The defect is already in [Er73], whose does not exclude , and the site's wording keeps it; no source states the question as one about sets containing . With excluded the recorded failure is removed, and the answer is decided by Ruzsa's and Weingartner's theorems rather than by the degenerate set. The observation about settles no instance of the corrected Statement and is credited here, not counted.