2   Elementary Estimates for Primes  Recall from Lecture 1      p 1 p      Euler s Theorem        x     x log x  Chebyshev s Theorem    2 1   Merten s Theorems  Theorem 2 1   Merten s Theorem    Assuming that   x   3  Then    i    p   x log p p   log x   O   1     ii    p   x 1 p   log log x   M   O   1 log x    for some M        iii    p   x   1   1 p     c   o   1   log x  for some c   0   Remark   Can show  c   e       Proof   i  Let N     x    Consider N    We have     N N   N N N     N N e   N      the second inequality cn be proved by induction  using   1   1 N   N   e    Let v p   k   be the largest power of p dividing k  Then     N       p   N p v p   N      fundamental theorem of arithmetic    log N       p   N v p   N     log p     We have v p   N         j   1     N p j    Indeed          v p   N         k   1 N v p   k       k   1 N   j   1     v p   k     j     j   1     k   1 N   v p   k     j     j   1     N p j       Now      log N       p   N   N p   log p     p   N   log p     j   2     N p j       p   N   N p   O   1     log p   O     p   N log p p 2   N    geometric series    N   p   N log p p   O     p   N log p         log N       N     N   C h e b y s h e v     O   N    since   p log p p 2         N   p   N log p p   O   N       Combine with  log N     N log N   O   N   to get      N log N   O   N     N   p   N log p p   O   N         Divide by N to get the result    ii  By Partial Summation  this is      1   O   1 log x       2 x   p   t log p p t   log t   2 d t       Writing     t       p   t log p p   log t  we get     1   O   1 log x       2 x d t t log t     2 x     t   t   log t   2 d t   1   O   1 log x     log log x   log log 2     2       t   t   log t   2 d t   O     x         t     t   log t   2 d t       By part  i         x         t     t   log t   2 d t     x   1 t   log t   2 d t   1 log x     Take M   1   log log 2     2       t   t   log t   2 d t    iii  Use Taylor expansion      log   1   y         j   1   y j j     to get     log   p   x   1   1 p       p   x log   1   1 p         p   x 1 p     p   x   j   2   p   j j     Write H     p   j   2   p   j j  We get           p   x 1 p   H   O     p   x   j   2   p   j j     p   2         p   x 1 p   H   O   1 x      ii    log log x   H   O   1 x       Taking exponentials         p   x   1   1 p     c   o   1   log x         2 2   Sieve Methods  General tools for estimating the number of primes  or products of a few primes in a set    Need information on the distribution of the set in residue classes   Definition   Sieve problem   Let P      Let      P   z       p   P p   z p       and let A      Denote      S   A   P   z         n   A     n   P   z       1           Problem  Estimate  S   A   P   z     Note that if A     x 2   x            S   A       x 1 2       A       S   A       x 1 3       A           p 1 p 2   p 1 p 2   x 1 3           Sieve hypothesis   There exists a multiplicative g         0   1   and R d     such that          n   A   n   0   m o d d         g   d     A     R d     for all square free d  no repeated prime factors    Example  A     1   x    P            A d       x d     x d   O   1       Then g   d     1 d     R d     1      S   A       x 1 2         p       p     x 1 2   x             x     O   x 1 2         A     n   n   2     n   x    P      Let d   p 1   p r  where p i are distinct primes  Then       A d         n   x   n   0 or   2   m o d p i     i   r         2 r d x if d odd 2 r   1 d x   O   2 r   if d even      by Chinese Remainder Theorem       S   A         2 x   n 2         p       2 x   1 2   x     p   2               p   x   p   2           O   x 1 2       Here       g   p       1 p p   2 2 p p   2     and R d   O   2 w   d      where w   d   is the number of prime factors of d  distinct    Lemma  We have      S   A   P   z       d   P   z       d     A d         Proof  Recall that           n   1         1     n        since   is the inverse of 1   Hence         S   A   P   z       n   A     n   P   z       1     n   A   d   P   z   d   n     d       d   P   z       a     A d         Example  Let          x   z         n   x     n   P   z       1           Let P      Let A     1   x        Then        A d     x d   O   1         By the previous lemma          x   z     S   A       z       d   P   z       d     x d   O   1       x   d   P   z       d   d   O     d   P   z         d         1     x   d   P   z       d   d   O   2     z     P   z     p 1   p     2     x   p   z   1       p   p     1     O   2     2     fundamental theorem of arithmetic   c   o   1   log z x   O   2 z   Merten s theorem  for some c   0     For 2   z   log x          x   z     c   o   1   log z x       Theorem   Sieve of Erastothenes   Legendre   Assuming that   A     1   x        2   z   x  Assume the Sieve Hypothesis  Then      S   A   P   z       A     p   2 p   P   1   g   p       O   x 1 2   log x   1 2 2   log x 4 log z     d   x d   P   z     R d   2   1 2     A   e log x log z   p   z p   P   1   g   p     e       Proof  Recall from previous lecture that     S   A   P   z       d   P   z   d   x     d     A d    since A d     for d   x       d   P   z   d   x     d   g   d     A     O     d   x d   P   z     R d      sieve hypothesis      A     d   P   z       d   g   d     O     d   x d   P   z     R d       A     d   P   z   d   x g   d         A     p   z p   P   1   g   p       O     d   x d   P   z     R d       A     d   P   z   d   x g   d         We estimate the first error term using Cauchy Schwarz         d   x d   P   z     R d         d   x d   P   z     R d   2   1 2     d   x d   P   z   1   1 2       Note that if d   P   z    d   x 1 2  then         d     log x 1 2 log z            d     number of distinct prime factors of d   since z     d     d   x 1 2   Hence  2     d     2 log x 2 log z  d   P   z    d   x 1 2   Now we get       d   x d   P   z   1   2   log x 2 log z   d   x d   P   z   2     d           d     2   log x 2 log z   d   x     d     2   log x 2 log z x log x      the last step is by Dirichlet s divisor problem     d   x     d       1   o   1       x log x    Substituting this in  the first error term becomes as desired   Now we estimate the second error term  We have       d   P   z   d   x g   d     x   1 log z   d   P   z   g   d   d 1 log z  since d   x in the sum  Rankin s trick    x   1 log z   p   z p   P   1   g   p   p 1 log z     z 1 log z   e     x   1 log z   p   z p   P   1   e g   p       x   1 log z     e   log x log z   p   z p   P   1   g   p     e   1   e y     1   y   e       Combining the error terms  the claim follows     Example  Take A     1   x        P      Then g   d     1 d  R d   O   1    so the sieve gives us     S   A   P   z         x   z       x   O   1       p   z   1   1 p     O   x 1 2   log x   1 2 2   log x 4 log z x 1 2     x   O   1     e   log x log z   p   z   1   1 p   e       By Merten s Theorem        p   z   1   1 p     C   o   1   log z   p   z   1   1 p       p   z   1   1 p     1     1 C   o   1     log z     Hence           x   z     c   o   1   log z   O   x   log x   1 2 2   log x 4 log z   x e   log x log z   log z   e         Hence  for 2   z   exp   log x 1 0 log log x            x   z     c   o   1   log z x       This asymptotic in fact holds for z   x o   1     In particular  the Erastothenes Legendre sieve gives          x         x   z     z   x log x log log x     for z   exp   log x 1 0 log log x    Not quite the Chebyshev bound      x     x log x   2 3   Selberg Sieve  asymptotes   good upper bound for primes   Erastothenes Legendre          Selberg          Theorem 2 2   Selberg sieve    Assuming that   z   2  A     finite  P      Assume the sieve hypothesis  h         0       be the multiplicative function supported on square free numbers  given on the primes by     h   p       g   p   1   g   p   p   P 0 p   P     Then      S   A   P   z       A     d   z h   d       d   z 2 d   P   z     3   d     R d         Sieve hypothesis  There is a multiplicative g         0   1   and R d     such that        A d     g   d     A     R d     for all square free d   1   Proof  Let     d   d     be real numbers with        1   1     d   0   d   z         Then              n   P   z       1       d   n d   P   z     d   2        If   n   P   z       1  get 1     otherwise use 0   x 2    Summing over n   A         S   A   P   z       n   A     n   P   z       1     n   A     d   n d   P   z     d   2     d 1 d 2   P   z     d 1   d 2   n   A   d 1   d 2     n 1     A     d 1   d 2   P   z     d 1   d 2 g     d 1   d 2         d 1   d 2   P   z     d 1   d 2 R   d 1   d 2     E  sieve hypothesis         m   n   means lcm   m   n      We first estimate E      E   max k     k   2   d 1   d 2   P   z     R   d 1   d 2       max k     k   2   d   z k d   P   z     d 1   d 2       d 1   d 2     d   R d     d     d 1   d 2         We have       d 1   d 2     d     d 1   d 2   1     l   z   d 1     d 2       d   l d 1   d 2     d 1     d 2       1 1   l     d 1   d 2     d 1     d 1   l     d 1   d 2     l d 1   d 2         3   d       Therefore      E     d   z z d   P   z     3   d     R d     max k     k   2       Now it suffices to prove that there is a choice of     d   d     satisfying      such that  Claim 1    d 1   d 2   P   z     d 1   d 2 g     d 1   d 2       1   d   z h   d     Claim 2      k     1 for all k       Proof of claim 1   We have  writing k     d 1   d 2    d i     d i k        d 1   d 2   P   z     d 1   d 2 g     d 1   d 2         k   P   z       k   2   d 1     d 2     P   z   k   d 1     d 2       1   k d 1     k d 2   g   k d 1   d 2         k   P   z       k   2 g   k     d 1     d 2     P   z   k   d 1     d 2       1   k d 1     k d 2   g   d 1     g   d 2      multiplicativity      We have             d 1     d 2       1     c   d 1   c   d 2       c        since       1   I  so the previous expression becomes       k   P   z       k   2 g   k     c   P   z   k     c     d 1     d 2     P   z   d 1     0   mod     c   d 2     0   mod c     k d 1     k d 2   g   d 1     g   d 2         k   P   z       k   2 g   k     c   P   z   k     k       d   P   z   k d   0   mod c     2     k   P   z       k   2 g   k     1   c   P   z   k     c       d     P   z   c k   c k d   g   c k d       2     n   z h   m     1     d   P   z   d   0   mod n     d g   d     2      multiplicativity  d   c d    m   c k  d   m d    since  1 h     2 g      check on primes 1 h   p     1 g   p     1    Now we get        d 1   d 2   P   z     d 1   d 2 g     d 1   d 2         m   z h   m     1   m 2     where        m     d   P   z   d   0   mod m     d g   d         Want to minimise this subject to        We need to translate the condition   1   1  Note that          m   z m   0   mod c       m     m     d   P   z     d g   d     m   d c   m     m       m     d c     c       m           d     d   e       e     e g   e       Hence         e       e   g   e     m   2 m   0   mod c       m     m       Now         1   1     m   z     m     m       By Cauchy Schwarz  we then get          m   z h   m     1   m 2       m   z     m   2 h   m           m   z     m     m   2   1       Hence        m   z h   m     1   m 2   1   m   z     m   2 h   m     1   m   z h   m         Equality holds for T m   h   m   G   z    where G   z       m   z h   m    We now check that with these   m    d   0 for d   z   Note that        c       c   g   c   G   z     m   z m     mod c       m   h   m         Hence    c   0 for c   2   This proves Claim 1   Now we prove Claim 2      c     1    Note that any m has at most one representation as m   e m    where e   d    m     d     1  for any d        Now      G   z       c   d   m     z c   m     d     1 h   c m         c   d h   c     m     z c   m     d     1 h   m         c   d h   e     m     z d   m     d     1 h   m         Now         d       d   2 h   d   g   d   G   z     m     z d   m     d     1     m     h   m           Substituting the lower bound for G   z            d     h   d   g   d     c   d h   e     1       since  1   h   h g     Lemma 2 3  Assuming that   z   3  g         0   1   multiplicative  for some K   A     we have        p   z g   p   log p     log z   A       Then      1   m   z h   m     2   p   z 1     e     1     1   g   p           where h is defined in terms of g as in Selberg s sieve   Proof  Note that for any c     0   1          m   z h   m       m   z m   P   z c   h   m     G   z   c         Then       p   z c p   P   1   g   p       1   G   z   c       p   z c p   P   1   h   p         m   z m   P   z c   h   m       m   z m   P   z c   h   m       By Rankin s trick      1     p   z c   1   g   p     G   z   c       p   z c   1   g   p       m   z m   P   z c   h   m       p   z c   1   g   p     z     log z   m   P   z c   h   m   m   log z  for any     0       p   z c   1   g   p     e       p   z c   1   h   p   p   log z     e       p   z c   1   g   p     g   p   p   log z   e     exp     p   z c   p   log z   1         log z   log p   p   log z     exp           log z   p   z c g   p     log p   p   log z     1   t   e t     exp         c e c           e c   A log z       Choose c   1   and     e     1 to get the claim     The Brun Titchmarsh Theorem  Theorem 2 4   Brun Titchmarsh Theorem    Assuming that   x   0  y   2      0 and y is large in terms of    Then          x   y         x       2       y log y       Remark   We expect          x   y         x       n   o   1     y log x     in a wide range of y  e g  y   x   for some     0 fixed   The prime number theorem gives this for  y   x  The Brun Titchmarsh Theorem gives an upper bound of the expected order for y   x     Proof  Apply the Selberg sieve with A     x   x   y        P      Note that for any d   1          a   A   a   0   m o d d       y d   O   1         Hence  the sieve hypothesis holds with g   d     1 d  R d   O   1     Now  the function h in Selberg sieve is given on primes by      h   p     g   p   1   g   p     1 p   1   1     p         where   is the Euler totient function  In general       h   d         d   2   1     d        since   is multiplicative   Now  for any z   2  Selberg sieve yields      S   A       z     y   d   z     d   2     d     O     d   z 2   3   d           By Problem 11 on Example Sheet 1  the error term is O   z 2   log z   2     Take z   y 1 2     1 0  Then      z 2   log z   2     y 1 2     1 0   2   log y   2   y 1     2 0      for y   y 0         We estimate       d   z     d   2     d       d   z     d   2 d d     d       d   z     d   2 d     p   d   1   1 p   1 p 2           p p   1   p     p       n   z 1 n     since any n   z has at least one representation as      n   d p 1 a 1   p k a k       where d   z is square free and p i   d are primes and a 1   0   We have proved        n   z 1 n   log z   O   1       1   1 1 0   log z     for z   z 0         Putting everything together gives us         x   y         x     S   A       z     z   y   1     1 0   log z   z   y 1     2 0     2       y log y     for y   y 0