Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bounding pi(n)?

  1. Nov 17, 2005 #1

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I was looking at a paper of Dusart (his 1999 extention of Rosser's Theorem), where the author gives (without proof, but using the results proved in the rest of the paper) bounds for the prime counting function pi(n).
    The minimum was [tex]\frac{x}{\log(x)}\left(1+\frac{0.992}{\log(x)}\right)[/tex] (for x >= 599) and the maximum was [tex]\frac{x}{\log(x)}\left(1+\frac{1.2762}{\log(x)}\right)[/tex] (for x >= 2).

    Does anyone know of a stronger result for the upper bound, perhaps with a stronger restriction? In practice the lower bound sticks much closer to pi(n) than the upper bound. In any case Dusart gives a reference for his method of derivation, but I haven't tracked it down yet.

    Edit: Since the new version of this site, I can't read it with Firefox -- the site crashes my browser.
     
    Last edited: Nov 17, 2005
  2. jcsd
  3. Nov 17, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    I've seen those Dusart bounds mentioned more than once, so I'm thinking they might be the best explicit bounds known but I could easily be wrong. Rosser's papers would be a place to look. You might try emailing Dusart. Do report back if you find something stronger!
     
    Last edited: Nov 17, 2005
  4. Nov 19, 2005 #3

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Well, I did email Dusart, but I've since found an unpublished (as far as I can tell) paper of his with stronger bounds of a different form, valid for larger k.

    If k >= 32299 then [tex]\pi(k)>\frac{k}{\ln k}\left(1+\frac{1}{\ln k}+\frac{1.8}{(\ln k)^2}\right)[/tex].
    If k >= 355991 then [tex]\pi(k)<\frac{k}{\ln k}\left(1+\frac{1}{\ln k}+\frac{2.51}{(\ln k)^2}\right)[/tex].

    These are actually phenomenal bounds.
     
  5. Nov 19, 2005 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    Interesting, thanks. Are those proved with a similar method? Do you have the reference handy?
     
  6. Nov 19, 2005 #5

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I'm actually not sure how to cite it. The paper is just a research report of sorts. I found it on a Columbia professor's page -- I'm not sure where it's actually from. I think it's building on the published paper, since it uses the main result of that paper, but it has one bound strictly worse than one in the paper. It's a little confusing.

    Pierre Dusart, "Sharper bounds for psi, theta, pi, and p_k", http://www.math.columbia.edu/~glass/spring04/chebyshev.pdf, June 1998.
     
  7. Nov 20, 2005 #6

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    That's great, thanks. I don't usually care about explicit bounds, but it's nice to know where they live.
     
  8. Nov 20, 2005 #7

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, but these are killer bounds. I love the fact that both bounds are fairly tight and of the same form -- it made me look at

    [tex](\ln k)^2\left(\frac{\pi(k)\ln k}{k}-1-\frac{1}{\ln k}\right)[/tex]

    for large-ish k to see if it would be reasonable to use a narrower range yet for the constant (now 1.8 to 2.51). Empyrically, it seems that 2 could easily be a lower bound (perhaps even 2.15 or 2.2) for all large k, but that's just conjecture until we know more of the Riemann zeta zeros.

    (I should really look at the form Dusart is using to prove this and see what I can get taking the limit as A -> infinity, the result that could be proved for large enough k assuming the truth of the RH.)
     
  9. Nov 21, 2005 #8

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    At the time that article was written, it was known that the first 1.5 billion were on the critical line. Computations have gone *much* furthur since then, van de Lune hit 10 billion in 2001. The ZetaGrid project claims over 1134 billion and something like a billion per day, though I'm not sure what the most recent published result is.

    At the rate it's increasing some kind of explicit bound as a function of the number of zeros might be interesting.
     
  10. Nov 21, 2005 #9

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    After studying the data, and noticing the reduction in variability as pi(k) is large, I conjecture the following:

    (Edit: well, so much for that conjecture!)

    Now all I have to do is look up Dasart's references and figure out how he does his calculations, then apply it with the known Riemann zeros and check the small values myself. (I presume the method gives a high effective lower bound which must be reduced manually.)
     
    Last edited: Nov 22, 2005
  11. Dec 7, 2005 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I've gotten in touch with Dusart. He sent me his entire thesis... 174 pages long... in French. Wish me luck, I'm diving in!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Bounding pi(n)?
  1. Calculating pi (Replies: 8)

  2. Pi in binary (Replies: 9)

  3. Randomness of pi (Replies: 24)

Loading...