1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Prime number inequality

  1. Feb 6, 2017 #1
    I believe this is probably a high level undergraduate question, but i could easily be underestimating it and it's actually quite a bit higher than that.

    I'm reading the Prime number theorem wikipedia page and i'm in part 4 under Proof sketch where sometime down they give in inequality:

    x is a natural number, p is for prime's obviously: ##\sum_{x^{1-\epsilon }\geq p\geq x}^{} \log p \geq \sum_{p\leq x}^{} logx##

    Where epsilon is any value greater than O. (O is some special value that they use in computer science a lot apparently, I might need to understand this value better to understand this inequality, i'm not sure.

    Can somebody help me understand this inequality? C'mon I know there are some really smart people here!
     
  2. jcsd
  3. Feb 7, 2017 #2

    Buzz Bloom

    User Avatar
    Gold Member

    Hi PsychonautQQ:

    I am not into number theory, but I am almost certain that the "O" is zero, i.e., "0".

    Regards,
    Buzz
     
  4. Feb 7, 2017 #3

    fresh_42

    User Avatar
    2017 Award

    Staff: Mentor

    My guess is ##O(something)##, e.g. ##O(1)\, , \,O(\log x) \, , \, O(\log \log x)## or even ##o(1)##. In any case I assume there is more than one typo in it, e.g. the ##\log x## in a summation over ##p## looks suspicious.
     
  5. Feb 7, 2017 #4

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    Here is a link to the article, the inequality discussed is the 6th formula in this section.
    "for any ε > 0" is a comparison with the number 0. The big O notation (with the letter O) is mentioned because it is used later in the same line.
     
  6. Feb 7, 2017 #5

    Buzz Bloom

    User Avatar
    Gold Member

    I found the equation in post #1 in the the linked article, although the post #1 version seems to have omitted a detail. It seems clear that the intent is
    ε > zero​
    and
    O(x1-ε)​
    is using the "big O" notation.

    Regards,
    Buzz
     
    Last edited: Feb 7, 2017
  7. Feb 7, 2017 #6

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    I thought it is the 6th formula there, but the right hand side is not identical.
     
  8. Feb 7, 2017 #7
    Wow, I am so smart for confusing 0 and O haha.

    I still don't understand the inequality though, can somebody explain why it makes sense intuitively or link a proof to me?
     
  9. Feb 8, 2017 #8

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    With the correct inequality from the Wikipedia article: We know ##x^{1-\epsilon} < p##. Take the logarithm on both sides and you get the inequality used in the article.
     
  10. Feb 8, 2017 #9
    And we know that x^(1-epsilon) < p because of the domain which is being summed over? p is required to be bigger?
     
  11. Feb 8, 2017 #10

    mfb

    User Avatar
    2017 Award

    Staff: Mentor

    We know it because the sum only runs over p satisfying this condition, right.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Loading...