1.2 Mann's Theorem: Theorem 1.2.1. (H. B. Mann)

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).

Lemma 1.  If $d(A) + d(B) > 1$, we can assume that $\exists A',B'$ such that:

• $d(A') + d(B') = 1$ 
• $A' \subseteq A$
• $B' \subseteq B$

Proof:

(1)  Assume that $d(A) + d(B) > 1$

(2)  There exists $A',B'$ where $A' \subseteq A$ and $B' \subseteq B$ and $d(A')+d(B') \le 1$

(3)  In fact, we can assume $d(A') + d(B')$ is as close to $1$ as we want since:

     (a)  We can assume that $d(B) \le d(A) < 1$.

     Note:  If $d(A)=1$, then we set $B' = B - \{1\}$ to get $d(A)+d(B')=1$

     (b)   Let $\epsilon$ be any number such that $1 > \epsilon > 0$

     (c)  We can assume that $1 - d(A) > \epsilon$

     Note: If not, then we set $B' = B - \{1\}$ to get $\epsilon > 1 - d(A)-d(B')$

     (d)  There exists integers $x,y$ such that $1 - d(A) - \epsilon \le \frac{x}{y} < 1 - d(A)$

     (e)  From the definition of density, we know that $d(B) \le \frac{B(y)}{y}$

     (f)  Using $y$, we can build $B'$ by removing $B(y)-x$ elements from $B$.

     Note 1:   $\frac{x}{y} < d(B) \le \frac{B(y)}{y}$ since $d(A) + d(B) > 1$ but $d(A) + \frac{x}{y} < 1$.

     Note 2:  If for any reason the approach in step 3f doesn't work, we can choose a larger $x'$ so that $x' > x$ and $\frac{x'}{y'} = \frac{x}{y}$

QED

Lemma 2.  if for every $n \ge 1$, there exists $m$ such that $m \in [1,n]$ and $C(n) - C(n-m) \ge [d(A) + d(B)]m$, then $d(C) \ge d(A) + d(B)$.

Proof:

(1)  Assume that for every $n \ge 1$, there exists $m$ such that $m \in [1,n]$ and $C(n) - C(n-m) \ge [d(A) + d(B)]m$.

(2)  Then, for any $n$, we have:
$$C(n) - C(n-m) \ge (d(A) + d(B))m$$
$$C(n-m)-C(n-m-m') \ge (d(A) + d(B))m'$$
$$C(n-m-m')-C(n-m-m-m'') \ge (d(A) + d(B))m''$$
$$\vdots$$
(3)  Adding all of these values up, gets us to:
$$C(n) \ge (d(A)+d(B))(m + m' + m'' + \cdots) = (d(A) + d(B))n$$
(4)  Divide both sides by $n$ to get:
$$\frac{C(n)}{n} \ge d(A)+d(B)$$
(5)  Since this is true for all $n$, using the definition of infimum [see Definition 3, here], it follows that:
$$\inf_n{\frac{C(n)}{n}} \ge d(A)+d(B)$$
(6)  This gets us to:  $d(C) \ge d(A) + d(B)$.  [see Definition 4, here]

QED

Lemma 3.  If $A(n) + B(n) > n-1$, then $n$ occurs in $A+B$

Proof:

(1)  Assume $A(n) + B(n) > n-1$

(2)  Assume $n \notin C = A+B$  [If it is, we are already done.]

(3)  Then: $A(n-1) = A(n)$ and $B(n-1) = B(n)$ so that:
$$A(n-1)+B(n-1)>n-1$$
(4)  Let $a_1,a_2,\cdots,a_r$ and $b_1,b_2\cdots,b_s$ be the numbers of $[1,n-1]$ which appear in $A$ and $B$ respectively.

(5)  So that, $r = A(n-1)$ and $s = B(n-1)$

(6)  Then, the numbers $a_1, a_2, \cdots, a_r$ and $n - b_1, n_b2, \cdots, n - b_s$ are all distinct and belong to $[1,n-1]$

(7)  But by assumption, there are more than $n-1$ of them which is impossible.

(8)  Therefore, we reject our assumption in step #2.

QED

Definition 1:  normal

A system of numbers $H \subset [0,n]$ is normal if for all $f \in [1,n]$; $f' \in [1,n]$; $f \notin H$; $f'\notin H$:
$$f + f' - n \notin H$$
Lemma 4.  If $C$ is normal, then for every $n \ge 1$ one can find $m \in [1,n]$ such that:
$$C(n) - C(n-m) \ge (\alpha + \beta)m$$
where:

• $C=A+B$
• $\alpha = d(A)$
• $\beta = d(B)$

Proof:

(1)  We can assume that $n \notin C$

Note: if $n \in C$, then there is a trivial solution for $m=1$ since:
$$C(n)-C(n-m) = C(n)-C(n-1) = 1 \ge (d(A)+d(B))1$$

(2)  Let $m$ be the least positive integer not belonging to $C$

(3)   It is clear that $m \le n$

(4)  We can assume that $m < n$ since:

    (a)  Assume that $m = n$

    (b)  $C(n) - C(n-m) = C(n) - C(0) = n-1$

   (c)  From Lemma 3 above, $A(n) + B(n) \le n-1$

   (d)  So, it follows that $C(n) - C(0) \ge A(n) + B(n) \ge (d(A) + d(B))n$

(5)  Let $s \in [n-m,n]$ such that $0 < s+m-n < m$

(6)  Now $s \in C$.  If not, then we would have $s \notin C; m \notin C$ and $s+m-n \notin C$ but $s+m-n < m$ which goes against $m$ being the least positive integer not belonging to $C$.

(7)  So, from step #5 and step #6, it follows that $C(n) - C(n-m) = m-1$

(8)  Using Lemma 3 above, since $m \notin C$, it follows that $A(m) + B(m) \le m-1$.

(9)  So, that, we have $C(n) - C(n-m) \ge A(m) + B(m) \ge (d(A) + d(B))m$

QED

Theorem 1.2.1 (H. B. Mann)
$$d(A+B) \ge \min(d(A) + d(B),1)$$