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