Status
On this page
Status
Topics
Status
On this page
Status
Topics
Is there a set such that
and such that every large integer can be written as for some prime and ?
Can the bound be achieved? Must such an satisfy
Source: erdosproblems.com/32
No claim settles this problem.
Open, the site's label (OPEN; page last edited 23 January 2026),
which attaches to the three questions together. The first two are open: Erdős
[Er54] constructed a set with
such that every large integer is
, improving Lorentz's [Lo54], but no source reaches
, and the question is open even for the almost-all
variant, where Wolke [Wo96] reached , Kolountzakis [Ko96]
and Ruzsa [Ru98c] for any
, with known only when the sumset need have lower
density at least (Ruzsa, Theorem 1). The third question is
answered yes: Theorem 2 of Ruzsa [Ru98c] gives
for
every such , recorded as the accepted partial claim on
Ruzsa's claim page (1998),
settling the part liminf on the refereed publication. The parts existence
and log are unsettled, so the problem stays open. Erdős offered a prize for
the second question, as Guy [Gu04] reports it.