1.1 Additive Properties of Sequences - Theorem 1.1.2 (L. G. Shnirelman)

The details in these notes are taken from A. O. Gelfond & Yu. V. Linnik, elementary methods in analytic number theory, 1965 (translated by Amiel Fienstein/Revised and edited by L. J. Mordell).

Definition 5: Additive Basis

A subset $A \subseteq \mathbb{N}$ with the property that $A + A + \cdots + A = \mathbb{N}$ for a finite sum.

Theorem 1.1.2 (L. G. Shnirelman)  Every sequence with a positive density is a basis for the natural numbers.


Proof:

(1)  Let $A^{(k)} = \underbrace{A + A + \dots + A}_{k\,\text{times}}$

(2)  Using the Corollary from Theorem 1.1.1, we have:
$$d(A^{(k)}) \ge 1 - (1 - d(A))^k$$
(3)  For sufficiently large $k$, we have:
$$d(A^{(k)})>\frac{1}{2}$$
since $0 \le\frac{A(n)}{n}\le 1$ and $d(A)=\inf\limits_{n}\frac{A(N)}{n}$.

(4)  For this $k$, the number of terms of $A^{(k)}$ in the interval $[1,n]$ will be greater than $\frac{n}{2}$.

(5)  If $a_i$ ranges over the terms of $A^{(k)}$ which do not exceed $n$, then there exists $i_1,i_2$ such that:  $a_{i_1} = n - a_{i_2}$.

Note:  If $i_1,i_2$ don't exist, then there are more than $2*(\frac{n}{2}+1)=n+2$ values in $[0,n]$ which is impossible.

(6)  So, there exists $k$ such that for any $n$, there exists $a_{i_1}, a_{i_2} \in A^{(k)}$ such that $n = a_{i_1} + a_{i_2}$.

QED