Erdős Problem 221

References:

• erdosproblems.com/221
• [Lo54] Lorentz, G. G., On a problem of additive number theory. Proc. Amer. Math. Soc. (1954), 838-841.
• [Ru72] Ruzsa, Jr., I., On a problem of P. Erdős. Canad. Math. Bull. (1972), 309-310.

theorem Erdos221.erdos_221 : True ↔ ∃ (A : Set ℕ), ((fun (N : ℕ) => ↑{a : ℕ | a ∈ A ∧ a ≤ N}.ncard) =O[Filter.atTop] fun (N : ℕ) => ↑N / Real.log ↑N) ∧ ∀ᶠ (N : ℕ) in Filter.atTop, ∃ (k : ℕ) (a : ℕ), 0 ≤ k ∧ a ∈ A ∧ N = 2 ^ k + a

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

Lorentz [Lo54] proved there is such a set with, for all large $N$, [\lvert A\cap{1,\ldots,N}\rvert \ll \frac{\log\log N}{\log N}N] The answer is yes, proved by Ruzsa [Ru72].