1   Estimating Primes  Theorem   Euler     p 1 p       Proof  Consider p N     p N   1   1 p   1 p 2       1 p N    for N         1   2   3        We have      p N     n   1 N 1 n     n   1 N   1   n n   1 d t t     1 N   1 d t t   log   N   1       On the other hand  using 1   x   e x  so     p N     p   N exp   1 p   1 p 2       1 p N     exp     p   N   1 p   1 p 2       1 p N       exp     p   N   1 p   1 p 2   p       exp   C     p   N 1 p       Comparing these two bounds gives        p   N 1 p   log log   N   1     C       Then letting N     gives the desired result     Theorem   Chebyshev s Theorem          x     c x log x      for x   2  where c is an absolute constant     Proof  Consider     S N   2 N N     2 N       N     2     for N      We have      S N     j   0 2 N 2 N j     1   1   2 N   4 N       On the other hand       S N     p   2 N p   p   N       where   p   N   is the largest j such that p j   2 N N  We have   p   N     1 for p     N   2 N    So       log 4   N     N   p   2 N log p       Take N     x 2    for x   2  Hence        x   p   2 x log p     log 4     x 2     log x     log 4   x 2   log 4   log x       Then       p   x     0   j   log x log 2     log 4   x 2 j   2   log x     telescoping summation  take x 2   x 2 2   x 2 3           log 4   x     log x   2   1     So for x   2 and a suitable large enough constant c    we have        p   x     log 4   x   c     log x   2       Hence       x   log x   2   p   x log p     log 4   x   c     log x   2   log x   log x   2       x         x   log x   2         log 4   x   c     log x   2       x     x   log x   2     log 4   x log x   log x   2   c     log x   2 log x   log x   2     log 4       x log x     for any    as long as x   x         Take     1  Choose c   0 large enough     1 1   Asymptotic Notation  Definition 1 1   Big O and little o notation    Let f   g   h   S      S       Write f   x     O   g   x     if there is c   0 such that   f   x       c   g   x     for all x   S   Write f   x     o   g   x     if for any     0 there is x     0 such that   f   x           g   x     for x   S    x     x     Write f   x     g   x     O   h   x     if f   x     g   x     O   h   x     and write f   x     g   x     o   h   x     if f   x     g   x     o   h   x       Definition 1 2   Vinogradov notation    Let f   g   h   S      S       Write f   x     g   x   or g   x     f   x   if  f   x     O   g   x       Example    log x   1 0 0   exp   log x     x 1 1 0 0  x   1   since lim x       log x   1 0 0 exp   log x     0  lim x     exp   log x   x 1 1 0 0   0   1 0 0 x   1 0 0   x   x 1 0 0  for x   1    e x   1   x   O   x 2   for x       1 0   1 0    since e x   1   x     n   2   x n n       x     x   O   1   for x      since   x       x   1   x      x   1 x   1   o   1    for x   1    Lemma  Let f   g   h   u   S        i  If  f   x     O   g   x     and  g   x     O   h   x      then  f   x     O   h   x      transitivity     ii  If  f   x     O   h   x     and  g   x     O   u   x      then  f   x     g   x     O     h   x         u   x          iii  If  f   x     O   h   x     and  g   x     O   u   x      then  f   x   g   x     O   h   x   u   x       Proof  Follows from the definition in a straightforward way  Example    iii    f   x       c 1   h   x        g   x       c 2   u   x      Then   f   x   g   x       c 1 c 2   h   x   u   x      so  f   x   g   x     O   h   x   u   x         1 2   Partial Summation  Lemma 1 3   Partial Summation    Assuming that     a n   n     are complex numbers  x   y   0  f     y   x       is continuously differentiable  Then        y   n   x a n f   n     A   x   f   x     A   y   f   y       y x A   t   f     t   d t       where for t   1  we define      A   t       n   t a n     n   1   t   a n       Proof  It suffices to prove the y   0 case  since then        y   n   x a n f   n       0   n   x a n f   n       0   n   y a n f   n         Suppose y   0  By the fundamental theorem of calculus          f   n     f   x       n x f     t   d t     0 x f     t       n   x     t   d t       Summing over n   x  we get          n   x a n f   n     A   x   f   x       0 x f     t       n   x     n   x     t   a n   d t   A   x   f   x       0 x f     t   A   t   d t       Lemma  If x   1  then        n   x 1 n   log x       O   1 x         where       is Euler s constant  which is given by     lim N       k   1 N 1 k   log N   Proof  Apply Partial Summation with a n   1  f   t     1 t  y   1 2  Clearly A   t       t    Then        n   x 1 n     x   x     1 x   t   t 2 d t   x   O   1   x     1 x t     t   t 2 d t   1   O   1 x     log x     1 x   t   t 2 d t   1   log x     1     t   t 2 d t   O   1 x       The last equality is true since   x     t   t 2 d t     x   1 t 2 d t   1 x   Let     1     1     t   t 2 d t  Then we have the asymptotic equation as desired   Taking x     in the formula  we see that   is equal to the formula for Euler s constant  as desired     Lemma  For x   1        p   x 1 p     1 x     t   t 2 d t   O   1         Proof  Apply Lemma 1 3 with  a n         n    where   is the set of primes   f   t     1 t  and y   1   We get A   t         t    and then       p   x 1 p       x   x     1 x     t   t 2 d t     1 x     t   t 2 d t   O   1         1 3   Arithmetic Functions and Dirichlet convolution  Definition   Arithmetic function   An arithmetic function  is a function f           Definition   Multiplicative   An arithmetic function  f is multiplicative  if f   1     1 and f   m n     f   m   f   n   whenever m   n     are coprime   Moreover  f  is completely multiplicative  if f   m n     f   m   f   n   for all m   n   Example  f   n     n s for s     is completely multiplicative   M bius function          n       1 n   1     1   k if n is a product of k distinct primes 0 n is divisible by a square of a prime     This is multiplicative    If     m n     0 and m  n are coprime  then we must have had at least one of     m     0 or     n     0   If     m n     1  then say m is a product of k distinct primes and n is a product of l distinct primes  Then     m n         1   k   l       1   k     1   l       m       n         n       n   a b 1  divisor function  and   k   n       n   n 1 n 2   n k 1  generalised divisor function     and   k are multiplicative   On the space of arithmetic functions  we have operations        f   g     n     f   n     g   n     f g     n     f   n   g   n     f   g     n     Dirichlet convolution     Definition   Dirichlet convolution   For f   g          we define        f   g     n       d   n f   d   g   n d         where   d   n means sum over the divisors of n   Lemma 1 4  The space of arithmetic functions with operations       is a commutative ring   Proof  Since arithmetic functions with   form an abelian group  it suffices to show    i    f   g     h   f     g   h     ii  f   g   g   f   iii  f   I   f   iv  f     g   h     f   g   f   h  Proofs    i  Follows from    f   g     n       n   a b f   a   g   b      ii  Follows from    f   g     n       n   a b f   a   g   b      iii  Take      I   n       1 n   1 0 n   0       Then one can check that  f   I   f    iv  From definition     Lemma  The set of arithmetic functions f with f   1     0 form an abelian group with operation      Proof  Need g such that   f   g   I        f   g     1     f   1   g   1     1   g   1     1 f   1         Assume g   m   defined for m   n  We will defined g   n          f   g     n     g   n   f   1       d   n d   1 f   d   g   n d     g   n       1 f   1     d   n d   1 f   d   g   n d       n       Lemma  Multiplicative arithmetic functions form an abelian group with     Moreover  for completely multiplicative f  the Dirichlet inverse is   f   Proof  For the first part  suffices to show closedness  Let f   g         be multiplicative  and m   n coprime   If m n   a b  we can write a   a 1 a 2  b   b 1 b 2 where a 1     a   m    a 2     a   n    b 1     b   m   and b 2     b   n    Therefore we have        f   g     m n       m n   a b f   a   g   b       m   a 1 b 1 n   a 2 b 2 f   a 1 a 2   g   b 1 b 2    above observation      m   a 1 b 1 n   a 2 b 2 f   a 1   f   a 2   g   b 1   g   b 2    by multiplicativity      f   g     m     f   g     n        also need to check that inverses are multiplicative     Now  remains to show that for completely multiplicative  f   f     f   I   Note that  f     f is multiplicative by the first part  So enough to show     f     f     p k     I   p k   for prime powers p k  Calculate      f     f   p     f   p       f   p     f   p     f   p     0   I   p       and for k   2      f     f   p k     f   p k       f   p   f   p k   1     f   p k     f   p   f   p k   1     f   p   k   f   p   f   p   k   1   0   I   p k         Example    k   n       n   n 1   n k 1  Then        k   1   1       1   k times       So    k is multiplicative by the previous result    Definition   von Mangoldt function   The von Mangoldt function            is         n       log p if n   p k for some prime p 0 otherwise     Then  log   1     since      log n   log   p   n p   p   n       p   n   p   n   log p   1       n         Since    is the inverse of 1  we have      log       1               1           I           1 4   Dirichlet Series  For a sequence   a n   n      we want to associate a generating function that gives information of   a n   n      Might consider        a n   n         n   1   a n x n       If we do this  then   p x p is hard to control  So this is not very useful   The following series has nicer number theoretic properties    Definition   Formal series   For f          define a  formal  series      D f   s       n   1   f   n   n   s     for s       Lemma  Assuming that   f         satisfying   f   n       n o   1    Then   D f   s   converges absolutely for Re   s     1 and defines an analytic function for Re   s     1   Proof  Let     0  fixed   n     and Re   s     1   2     Then       n   N     f   n   n   s       n   N     f   n     n   Re   s       n   N   n     Re   s       n   N   n   1       N   1         n   N   1     n   1 n t   1     d t   N   1         N   t   1     d t   N         Hence we have absolute convergence for Re   s     1   2    Also   D f   s   is a uniform limit of the functions   n   1 N f   n   n   s  From complex analysis  a uniform limit of analytic functions is analytic  Hence  D f   s   is analytic for Re   s     1   2     Now let     0     Theorem   Euler product   Assuming that   f         be bounded     f   n       1  and multiplicative  Then      D f   s       p   1   f   p   p 2   f   p 2   p 2 s             for Re   s     1  Furthermore  if f is completely multiplicative  then      D f   s       p   1   f   p   p s     1       for Re   s     1   Proof  Let N      Re   s         1  Let     D f   s   N       p   N   1   f   p   p s   f   p 2   p 2 s             Note that the series defining the factors are absolutely convergent  since        k   1     f   p k       p k s       k   1   1 p k s          geometric series    Therefore  multiplying out       D f   s   N       n   1   a   n   N   f   n   n   s     where      a   n   N         ways to write n as a product of prime powers  where the primes are   N         The fundamental theorem of arithmetic tells us that a   n   N       0   1   and a   n   N     1 for n   N   Now        D f   S     D f   s   N         n   N   1     f   n       n   s       n   N   1   n       N     0      since   n   1   n           Hence   D f   s     lim N     D f   s   N     Finally  for f completely multiplicative  use geometric formula         k   1   f   p   k p k s   1 1   f   p   p s         Lemma  Assuming that   f   g            f   n         g   n       n o   1    Then      D f   g   s     D f   s   D g   s       for Re   s     1   Proof  We know  D f   s   and  D g   s   are absolutely convergent  so can expand out the product      D f   s   D g   s       a   b   1   f   a   g   b     a b     s     n   1     n   a b f   a   g   b   n   s     n   1     f   g     n   n   s   D f   g   s         Definition   Riemann zeta function   For Re   s     1  define          s       n   1   n   s       Example    n   1       n   n s       s   2 for Re   s     1  since       1   1      n   1       n   n s   1     s   for Re   s     1  since    is the Dirichlet inverse of 1  so       1   I          s         n   1   log n n s for Re   s     1  since d d s n   s       log n   n   s  Can differentiate termwise  since if F n analytic and F n   F uniformly  then F is analytic and F n     F    We know that   n   1   f   n   n   s converges uniformly for Re   s     1 if   f   n       n o   1           s       s         n   1       n   n s for Re   s     1  This is because     log     1       see the definition of the von Mangoldt function   Dirichlet hyperbola method  Problem  How many lattice points   a   b       2 satisfy a b   x   Note that this number is    n   x     n       a b   x 1   Dirichlet proved that for x   2        n   x     n     x log x     2     1   x   O   x 1   2       where    is Euler s constant   We will see a proof of this shortly   Conjecture  Can have  O     x 1 4        Current best exponent is 0   3 1 4   First  we prove a lemma   Lemma   Dirichlet hyperbola method   Assuming that   f   g          x   y   1  Then        n   x   f   g     n       d   y f   d     m   x d g   m       m   x y g   m     y   d   x m f   d         Proof    n   x   f   g     n       d m   x f   d   g   m    Split this sum into parts with d   y and d   y to get the conclusion     Theorem 1 5   Dirichlet s divisor problem    For x   2        n   x     n     x log x     2     1   x   O   x 1   2       where    is Euler s constant   Proof  We use the Dirichlet hyperbola method  with y   x 1 2  Note that      1   1  Then        n   x     n       d   x 1 2   m   x d 1     m   x 1 2   x 1 2   d   x m 1     x   x 1 2   x d   O   1         m   x 1 2   x m   x 1 2   O   1       x   d   x 1 2 1 d   x   m   x 1 2 1 m     m   x 1 2 x 1 2   O   x 1 2       Recall from Lecture 2 that        d   y 1 d   log y       O   1 y         Taking y   x 1 2  the previous expression becomes      2     1 2 log x       O   1 x 1 2       x   O   x 1 2     x log x     2     1   x   O   x 1 2