Erdős Problem #38

Does there exist \(B \subset \mathbb{N}\) which is not an additive basis, but is such that for every set \(A \subseteq \mathbb{N}\) of Schnirelmann density \(\alpha\) and every \(N\) there exists \(b \in B\) such that \[ \lvert (A \cup (A+b)) \cap \{1, \ldots, N\} \rvert \geq (\alpha + f(\alpha)) N \] where \(f(\alpha) > 0\) for \(0 < \alpha < 1\)? Note: here Erdős seems to use a slightly weaker notion of an additive basis (see [Er56] at the top of page 135). In particular, for this problem, a set is an additive basis of order \(k\) if every natural number can be written as a sum of _at most_ \(k\) elements of the set, rather than as a sum of _precisely_ \(k\) elements. A positive [solution](https://github.com/spicylemonade/erdos-38) was given by GPT 5.5 Pro (prompted by gebyjaff, cleanup by Liam Price); in fact a sparse random set \(B\) has this property, with \(f(\alpha)\gg \alpha (1-\alpha)^2\).