Loading web-font TeX/Math/Italic

Wednesday, November 27, 2013

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)







No comments:

Post a Comment