1.1 Additive Properties of Sequences - Theorem 1.1.1 (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 1:  infinite sequence of integers

Let any capital Latin letter (e.g. $A$, $B$, $C$, ...) denote an infinite sequence where each term is distinct and in numerical order with the first term $0$.

For example, $A$ would represent:
$$0,a_1,a_2,a_3, \dots$$
where
$$0 < a_1 < a_2 < a_3 < \dots$$

Definition 2:  number of terms not exceeding $n$

Let $A(n)$ be numerical function on sequences defined as the number of terms not exceeding $n$ so that:
$$A(n) = \sum_{0 < a_i \le n} 1$$

For example:
$$0\le\frac{A(n)}{n}\le1$$

Definition 3:  infinitum (inf)

For a given set $S$, the greatest integer that is less than or equal to all elements in $S$.

Examples:

$$\inf\, \{1,2,3\}=1$$
$$\inf\, \{ x \in \mathbb{Z} : 0 < x < n \} = 1$$

Definition 4:  density of a sequence

The density $d(A)$ of a sequence $A$ is defined as:
$$d(A) = \inf_n \frac{A(n)}{n}$$

Examples:

• if $1 \notin A$, then $d(A)=0$
• $d(A)=1$ if and only if $A$ contains all the positive integers.
• The densities of squares, cubes, and prime numbers equal $0$.
• $\forall{n}\, A(n) \ge n*d(A)$ 

Theorem 1.1.1 (L. G. Shnirelman)

$$d(A+B) \ge d(A) + d(B) - d(A)d(B)$$

Proof:
(1)  Let $C = A+B$ such that $c \in C$ implies $c = a + b$ where $a \in A, b \in B$

(2)  Let $\alpha=d(A), \beta=d(B), \gamma=d(C)$

(3)  There are $A(n)$ numbers in $A$ in the interval $[1,n]$ each of which appears in $C$ since $0 \in B$.

(4)  Let $a_k, a_{k+1}$ be any two adjacent numbers in $A$.

(5)  Let $l_k = a_{k+1}-a_k-1$, so that if $l_k > 0$, we have the following numbers not in $A$:

$$a_k+1, a_k+2, \dots, a_k+l_k = a_{k+1}-1$$
(6)  For a given $a_k,a_{k+1}$, $B(l_k)$ is equal to count of the numbers in between $a_k$ and $a_{k+1}$ that are in $C$ since $1 \le r \le l_k$ and $r \in B$ implies that $a_k + r \in C$.

(7)  From step(6), we have:
$$C(n) \ge A(n) + \sum_{k \le A(n)}{B(l_k)}$$
where each $l_k$ is taken from the intervals between numbers of the form $a_k$ and $a_{k+1}$

(8)  For each $k$, $B(l_k) \ge \beta{l_k}$. [From Definition 4 above]

(9)  So, from step(7), we have:
$$C(n) \ge A(N) + \beta\sum_{k \le A(n)}{l_k} = A(n) + \beta(n - A(n))$$
$$=A(n)(1 - \beta) + \beta{n} \ge \alpha(1 - \beta)n + \beta{n}$$

(10)  For all $n \ge 1$, we have:
$$\gamma=d(A+B)=\inf_n\frac{C(n)}{n} \ge \alpha + \beta - \alpha\beta$$

QED

Corollary:

$$d(A_1 + \dots + A_k) \ge 1 - \prod_{i=1}^k{(1 - d(A_i))}$$

Proof:

(1)  From Theorem 1.1.1 above:
$$1 - d(A+B) \le 1 - d(A) - d(B) + d(A)d(B) = (1 - d(A))(1 - d(B))$$
(2)  So that:
$$d(A+B)-1 \ge -(1-d(A))(1-d(B))$$
(3)  Which shows the case for $k=2$ where:
$$d(A+B) \ge 1 - (1 - d(A))(1 - d(B))$$
(4)  Assume that it is true up to some $k \ge 2$ so that:
$$d(A_1 + \dots + A_k) \ge 1 - \prod_{i=1}^k{(1 - d(A_i))}$$
(5)  Let $B = A_1 + \dots + A_k$

(6)  From step(3) above, we have:
$$d(B + A_{k+1}) \ge 1 - (1 - d(B))(1 - d(A_{k+1}))$$
(7) From step(4), we have:
$$-d(B) \le -1 +\prod_{i=1}^{k}(1 - d(A_i))$$
(8)  Which gives us:
$$1-d(B) \le  \prod_{i=1}^{k}(1 - d(A_i))$$
(9)  Combining step(8) with step(6) gives us:
$$d(A_1 + \dots + A_{k+1}) \ge 1 - \prod_{i=1}^k(1 - d(A_i))(1 - d(A_{k+1}))$$
QED