Problem 35

Let $B\subseteq\mathbb{N}$ be an additive basis of order $k$ with $0\in B$ . Is it true that for every $A\subseteq\mathbb{N}$ we have

d_s(A+B)\geq \alpha+\frac{\alpha(1-\alpha)}{k},

where $\alpha=d_s(A)$ and

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

is the Schnirelmann density?

Source: erdosproblems.com/35

Number theory
Additive bases

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved by Plünnecke's density bound below, recorded on its claim page (Plünnecke, 1970). The site labels the problem PROVED (LEAN); the Lean proof behind the label is linked from that claim page, carries no formal-verification credit in this corpus, and is qualified below.

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 is Er36c and labels the scan 1936; the printed paper is dated received 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.
Pl70: Plünnecke, H., Eine zahlentheoretische Anwendung der Graphentheorie. Journal für die reine und angewandte Mathematik 243 (1970), 171–183. DOI: 10.1515/crll.1970.243.171. - Jin, Renling, Density Versions of Plünnecke Inequality: Epsilon-Delta Approach. Combinatorial and Additive Number Theory, Springer, 2014, 99–113. DOI: 10.1007/978-1-4939-1601-6_8. The compiled proof follows the separately paginated sixteen-page author manuscript, Theorem 2 and Section 4, pp. 14–15, not the published text.

Problem 35

Status

Proof claims

Discussion