1.2. Mann's Theorem - Canonical Extension

 Definition 1:  Base of the Canonical Extension : $\beta_0$

If a sequence of integers $C$ does not possess the property of normality (see Definition 1, here), then there exists $c,c'$ in the interval $(0,n)$ such that $c\notin C,c'\notin C$, $c + c' - n = a + b$ where $C = A+B$ and $a\in A$ and $b\in B$

Let $\beta_0\in B$ be the least number $b$ for which $c + c' - n = a + b$


Definition 2:  Canonical Extension of the set $C$ : $C_1$

The equation $c + c' - n = a + \beta_0$ has a solution in the numbers $c$, $c'$, $a$ where $c\notin C$, $c'\notin C$; $a\in A$; $c$, $c'$, $a \in (0,n)$.

Let $C^{*}$ be the set of all numbers $c,c'$ included in the above solution so that $C\cap C^{*}$ is the empty set.

We will call $C_1 = C \cup C^{*}$ the "canonical extension" of the set $C$.


Definition 3:  Canonical Extension of the set $B$ : $B_1$

Let $B^{*}$ be the set of all values $\beta_0 + n - c$ where $c\in C^{*}$

Each number $b*\in B^{*}$ can be written in the form $c' - a$ where $c' \in C^{*}$ and $a \in A$ [Since $\beta_0+n- c = c' - a$ from the equation $c + c' - n = a + \beta_0$ above]

Since $b*$ has the form $\beta_0+n-c$, it follows that $b* \ge \beta_0 \ge 0$

Since $b* = c' - a$, $b* \le c' \le n$

So, all numbers $b*\in B^{*}$ lie in the interval $(0,n)$.

For all numbers $b*\in B^{*}$, $b*\notin B$ since otherwise, $b* = c' - a$ would imply that since $c' = b* + a$, $c' \in C$ which is false.

We will call $B_1 = B\cup B^{*}$ the "canonical extension" of the set $B$.


Lemma 1:  $A + B_1 = C_1$

Proof:

(1)  Either $b_1\in B$ or $b_1\in B^{*}$

(2)  If $b_1 \in B$, then $a + b_1 \in C \subseteq C_1$

(3)  If $b_1 \in B^{*}$, then $b_1 = \beta_0 + n - c'$ where $c' \notin C$

(4)  Since $c + c' - n = a + \beta_0$, $b_1 = c - a$


QED

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

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

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