Erdős Problem #38 — A non-basis whose single translates always boost density

Erdős Problem $38$ asks whether a set $B$ that is not an additive basis can nevertheless uniformly increase the initial density of every set $A$ by a positive amount after some shift from $B$. The problem was apparently not posed directly by Erdős; related material appears in Problem $35$.

Known results

• Erdős (1936): an additive basis of order $k$ gives an improvement of at least $\alpha(1-\alpha)/(2k)$.
• Landau (1937) replaced $k$ by the mean order $\lambda$; Brauer and Selberg later obtained stronger bounds, with Brauer improving the intermediate range.
• Linnik (1942) constructed the first essential component that is not an additive basis.

Claimed sparse-random solution — date not stated

GPT 5.5 Pro, prompted by gebyjaff, claims a positive answer using a sparse random set $B$, with $f(\alpha)\gg\alpha(1-\alpha)^2$. A related discussion argues that probabilities $p_n=(\log n)^\epsilon/n$ make $B$ too sparse to be an additive basis while still supplying the required shifts. The claim remains unverified; the formalization still contains by sorry.

Current status (as of April 2026): A positive construction is claimed, but no published or formal proof has corroborated it; absent that verification, Problem $38$ remains open.