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
No comments:
Post a Comment