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

The Schnirelmann density is defined by

d_s(A) = \inf_{N\geq 1}\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N}.

Source: erdosproblems.com/38

Number theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

The site labels the problem PROVED (LEAN). A six-page anonymous manuscript posted on 25 April 2026, credited by the site to GPT 5.5 Pro prompted by a forum user, constructs a set that is not an additive basis and has the shift property with an explicit $f(\alpha)>0$ ; Thomas Bloom, the site's curator, accepted it, Nat Sothanaphan's check of the write-up found no issues, and there is no refereed version. The site's (LEAN) suffix is a catalog label: the linked Lean files are a statement with a placeholder and an unbuilt community proof, described under Formalization. The claim page the 2026 construction records the acceptance.

Er36c: Erdős, P., On the arithmetical density of the sum of two sequences, one of which forms a basis for the integers. Acta Arithmetica 1 (1935), 197–200. DOI: 10.4064/aa-1-2-197-200. The site/archive key labels the scan 1936; its printed received date is 11 March 1935.
Er56: Erdős, P., Problems and results in additive number theory. Colloque sur la Théorie des Nombres, Bruxelles, 1955, 127–137. George Thone, Liège; Masson and Cie, Paris, 1956; the problem is cited there at p. 136.
Li42: Linnik, U. V., On Erdös's theorem on the addition of numerical sequences. Matematicheskii Sbornik 10 (52) (1942), 67–78. The primary twelve-page scan is available from the MathNet record and its full-text PDF at https://www.mathnet.ru/php/getFT.phtml?jrnid=sm&option_lang=eng&paperid=6119&what=fullt.
Sol26: “A resolution of Erdős Problem 38,” six-page manuscript posted in spicylemonade/erdos-38 as 38.pdf, PDF metadata dated 25 April 2026. The announcing forum post credits GPT 5.5 Pro with the solution and Liam Price with the final cleanup of the PDF, and the site's commentary credits GPT 5.5 Pro, prompted by the poster gebyjaff; the PDF itself gives no author.
La37: Landau, E., Über einige neuere Fortschritte der additiven Zahlentheorie. Cambridge Tracts in Mathematics and Mathematical Physics 35, Cambridge University Press, 1937, 94 pp.
Br38: Brauer, A., Über die Dichte der Summe zweier Mengen, deren eine von positiver Dichte ist. Mathematische Zeitschrift 44 (1939), 212–232. DOI: 10.1007/BF01210651. The discussion uses the key Br38; Springer gives publication year 1939.
Se44: Selberg, S., Note on a metrical problem in the additive theory of numbers. Archiv for Matematik og Naturvidenskab 47 (1944), 111–118.
Br55: Brauer, A., On the Schnirelmann density of the sum of two sequences. Mathematische Zeitschrift 63 (1955), 529–541. DOI: 10.1007/BF01187959.

Problem 38

Status

Proof claims

Discussion