Erdős Problem #333 — Thin Additive Bases for Density-Zero Sets

The problem asks whether every density-zero set $A\subseteq\mathbb N$ can be covered by sums from a set $B$ with $|B\cap[1,N]|=o(N^{1/2})$. It is cited as an Erdős--Graham problem from 1980.

Known results

• Erdős and Newman, 1977: the assertion holds when $A$ is the set of squares.
• Erdős and Newman, 1977: for almost all suitable finite sets $A\subseteq[N]$, every additive cover $B$ satisfies $|B|\ge\min(n/\log N,N^{1/2}/2)$.
• Alon, Bukh, and Sudakov resolved the related finite problem with a matching-order upper bound.

2026 counterexample

A 2026 arXiv case study applies the Erdős--Newman lower bound to rapidly separated dyadic blocks, producing a density-zero union $A$ for which no $B$ has $A\subseteq B+B$ and $|B\cap[1,N]|=o(N^{1/2})$. This establishes a negative answer. The associated AI publicity was corrected: GPT-5.2 Pro reproduced an existing literature argument rather than discovering a new theorem.

Current status (as of January 2026): The general assertion is settled negatively; the squares remain a positive special case.