Loading ...
Sorry, an error occurred while loading the content.

Approximation of pi(x)

Expand Messages
  • Andrey Kulsha
    Hello! It s known that Li(x)=integral(dt/ln(t),t,0,x) is a good approximation for pi(x), the number of primes less than or equal to x. [Sure, if x 1, we take
    Message 1 of 2 , Apr 7, 2001
    • 0 Attachment
      Hello!

      It's known that

      Li(x)=integral(dt/ln(t),t,0,x)

      is a good approximation for pi(x), the number of primes less
      than or equal to x.
      [Sure, if x>1, we take the mean value of integral, i.e.
      Li(x)=lim(integral(dt/ln(t),t,0,1-eps)+integral(dt/ln(t),t,1+eps,x),eps->0)].

      But Riemann suggested yet better approximation for pi(x):

      R(x)=sum(mu(n)*Li(x^(1/n)/n),n,1,+infinity),

      where mu(n) is Moebius' function.

      R(x) works really good. We can transform it into better
      form, using some series:

      Li(exp(x))=Euler+ln(x)+sum(x^k/k!/k,k,1,+infinity), where
      Euler=0.57721...;
      sum(mu(k)/k^n,k,1,+infinity)=1/zeta(n), where zeta(n) is
      Riemann's zeta-function;
      sum(mu(k)*ln(k)/k,k,1,+infinity)=-1.

      The result is:

      R(x)=1+sum(ln(x)^n/n!/n/zeta(n+1),n,1,+infinity).

      Note that 1 might be expressed as ln(x)^0/0!/0/zeta(1) if
      believed that 0*zeta(1)=1 (so n would run from 0 to
      infinity). Note also that lim(R(eps),eps->0)=0.

      If we look at the difference R(x)-pi(x), we will notice that
      it oscillates around some function with rising amplitude. To
      find this function (which seems to be very close to zero
      point), let consider

      integral(dt*(R(t)-pi(t)/x,t,0,x),

      which gives us the "mean" difference between R(t) and pi(t)
      for 0<t<x. It also oscillates around some function yet
      closer to zero point. We can continue this process (similar
      to finding generalized sum of divergent series), and we'll
      see that it's (heuristically) indeed zero point.

      Note that if we do such process for Li(x)-pi(x), we'll
      obtain something similar to sqrt(x)/ln(x), but not zero
      point.

      Now about amplitude of oscillations of R(x)-pi(x). At the
      beginning amplitude seems to be less than C*sqrt(x)/ln(x)
      for some small positive C. But we know that Li(x) isn't
      always greater than pi(x), hence, C is not always less than
      1, it becomes higher, i.e. C is function.

      Using statistics and assuming that probability of N being
      prime is 1/ln(N), Cramer showed that heuristically

      |Li(x)-pi(x)|<sqrt(2*x*lnln(x)/ln(x)).

      If we replace 1/ln(N)=Li'(N) by

      R'(N)=sum(mu(k)/N^(1-1/k)/k,k,1,+infinity)/ln(N),

      we'll obtain something similar to

      |R(x)-pi(x)|=O(sqrt(x/ln(x))),

      i.e. C=O(sqrt(ln(x))).

      Maybe, this is a good approximation when x is enough big.
      However, for small x (less that 10^16) we can see that C can
      be approximated much better (by a constant); it even goes
      down a bit when x goes up.
      On the other hand, |R(x)-pi(x)| seems to be closely bound by
      some definite function A(x), our C*sqrt(x)/ln(x) being only
      approximation of this function from above. It would be
      useful and interesting to find A(x) more exactly, however,
      even RH (Riemann Hypothesis) gives us only rough
      ceiling-limit O(sqrt(x)*ln(x)). Perhaps, some heuristic
      methods (as Cramer's one) will give some better results?

      Great thanks for any comments,

      Andrey
      --------------------------------------------------
      рТПЖЕУУЙПОБМШОБС ЬМЕЛФТПООБС РПЮФБ РТЕДРТЙСФЙС: SMTP, POP3/IMAP4, Web-Mail;
      ЫЙЖТПЧБОЙЕ, БЧФППФЧЕФЮЙЛ, ЖЙМШФТЩ, УРЙУЛЙ ТБУУЩМПЛ... http://tut.by/services.html
    • Andrey Kulsha
      Hello! ... must be: integral(dt*(R(t)-pi(t))/x,t,0,x). Note that I ve missed a parentheses. Sorry, Andrey ... Профессиональная
      Message 2 of 2 , Apr 8, 2001
      • 0 Attachment
        Hello!

        There was a typo in my posting about pi(x):

        >integral(dt*(R(t)-pi(t)/x,t,0,x),

        must be:

        integral(dt*(R(t)-pi(t))/x,t,0,x).

        Note that I've missed a parentheses.

        Sorry,

        Andrey
        --------------------------------------------------
        рТПЖЕУУЙПОБМШОБС ЬМЕЛФТПООБС РПЮФБ РТЕДРТЙСФЙС: SMTP, POP3/IMAP4, Web-Mail;
        ЫЙЖТПЧБОЙЕ, БЧФППФЧЕФЮЙЛ, ЖЙМШФТЩ, УРЙУЛЙ ТБУУЩМПЛ... http://tut.by/services.html
      Your message has been successfully submitted and would be delivered to recipients shortly.