Problem 221

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

Source: erdosproblems.com/221

Number theory
Additive bases

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

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.

Problem 221

Status

Proof claims

Discussion