Does there exist a set A⊆N such that, as N→∞, the counting function | A capa∈N:a≤ N| is O(N/log N), and such that for all sufficiently large N∈N there exist k,a∈N with 0≤ k, a∈ A, and N=2^k+a?

Erdős Problem #221 — Sparse bases for powers of two

About 72 years old · traced to 1954

Does there exist a set $A\subseteq\mathbb{N}$ such that, as $N\to\infty$ , the counting function $\lvert A\cap\{a\in\mathbb{N}:a\le N\}\rvert$ is $O(N/\log N)$ , and such that for all sufficiently large $N\in\mathbb{N}$ there exist $k,a\in\mathbb{N}$ with $0\le k$ , $a\in A$ , and $N=2^k+a$ ?

References

Primary source

The Formal Conjectures Authors, Formal Conjectures (2025); independently edited from the pinned source file.

Additional references

Pinned Formal Conjectures source, Apache-2.0.

additive-basis number-theory

InErdős Problems

Posted 2 months ago · edited 3 weeks ago

Progress summary

Refreshed 1 month ago

Claimed solved

The answer is yes: Ruzsa constructed a sufficiently sparse set whose translates by powers of two cover all sufficiently large integers.

Erdős posed this as a $10$ -dollar problem. Ruzsa answered it affirmatively; the retrieved sources do not specify the year of his result.

Known results

Ruzsa: $A=\{5^n m:m\ge 1,\ 5^n\ge C\log m\}+\{0,1\}$ , for sufficiently small $C>0$ , satisfies $|A\cap[1,N]|\ll N/\log N$ and covers every sufficiently large integer as $2^k+a$ ; the proof uses that $2$ is a primitive root modulo $5^n$ .

Lean verification

The Erdős Problems record also reports that this affirmative proof has been formally verified in Lean.

Current status (as of March 2026): Ruzsa's construction proves the assertion, so the problem is resolved.

Sources

No solutions have been posted yet.