Problem 221

../

claims/: The 2 claim pages of Problem 221, one per claimant's result; the problem's standing derives from them.

---

Statement. Is there a set $A\subset\mathbb{N}$ such that, for all large $N$,

$$\lvert A\cap\{1,\ldots,N\}\rvert \ll N/\log N$$

and such that every large integer can be written as $2^k+a$ for some $k\geq 0$ and $a\in A$?

Status. PROVED (LEAN), the site's label. The standing rests on two accepted claim pages: Ruzsa 1972, the refereed construction with $\ll N/\log N$ elements up to $N$ built from the powers of $5$, and Ruzsa 2001, the refereed exact complement with $\sim N/\log_2 N$ elements, the best possible count. The label's Lean qualification refers to an outside formalization of the 1972 construction linked from its page, which is not part of this repository's audited Lean.

Source. erdosproblems.com/221, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #221, https://www.erdosproblems.com/221.

References.

• [Lo54] Lorentz, G. G., On a problem of additive number theory. Proc. Amer. Math. Soc. (1954), 838-841.
• [Ru01] Ruzsa, Imre Z., Additive completion of lacunary sequences. Combinatorica (2001), 279-291.
• [Ru72] Ruzsa, Jr., I., On a problem of P. Erdős. Canad. Math. Bull. (1972), 309-310.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• erdos_1954_results_additive_number_theory
• erdos_1954_results_additive_number_theory / question_p853
• ruzsajr_1972_problem_p
• ruzsajr_1972_problem_p / theorem_p309
• erdos_1956_problems_results_additive_number_theory
• erdos_1956_problems_results_additive_number_theory / problem_p133