3 ms·

Interesting fact about the Prime Number Theorum. It is NOT an estimate of the number of primes below a certain N but instead it is an upper bound on the number

Interesting fact about the Prime Number Theorum. It is NOT an estimate of the number of primes below a certain N but instead it is an upper bound on the number of primes. The classic formula derived from it, n/log(n), is always above the actual number of primes (except for very small 'n' (<10) where the approximation has significant error). You can compare the actual counts of primes below 10^x (sequence A00688) to the estimates provided by the prime number theorum to see this (sequence A057835) for yourself. Explanation: At the risk of once again proving the Prime Number Theorum we can use a sieve to illustrate the upper bound. Above 2 there's an upper bound of 1/2 numbers possible being prime, since only 1/2 numbers are not a factor of 2. Above 6 there's an upper bound of 1/3 numbers being prime (only 1/3 numbers above 6 are not a factor of 2 or 3) and the cycle of multiples of 2&3 repeats every multiple of 6 so only 2 number remain that aren't a factor of 2 or 3 every multiple of 6. We could say above 30 (which is 2 * 3 * 5) only 8/30 numbers are possibly prime since only 8/30 numbers are not a factor of 2,3 or 5 on a repeating cycle. We could again create a sieve at 2 * 3 * 5 * 7 (210) with a repeating cycle of those factors (with 48/210 numbers remaining that aren't factors). The prime number theorum can be derived from this upper bound. If you're sieving out factors of a prime each time one is discovered you would be checking 1/2 * 2/3 * 4/5 * 6/7 * 10/11... etc. numbers for primality. This is essentially the left hand side of the Euler product formula you can see here - https://en.wikipedia.org/wiki/Proof_of_the_Euler_product_formula_for_the_Riemann_zeta_function#Proof_of_the_Euler_product_formula https://en.wikipedia.org/wiki/Proof_of_the_Euler_product_for... Also see https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler's_product_formula https://en.wikipedia.org/wiki/Euler%27s_totient_function#Eul... Now that same totient function is a good way to derive the prime number theorum - https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_number_theorem_for_arithmetic_progressions https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_num... So the prime number theorum is essentially defining the counts resulting from a sieve of primes. A sieve is an upper bound on the number of primes. Eg. there's numbers of the form 6n+1 or 6n+5 that aren't prime (eg. 25) that won't be filtered by that sieve but also aren't prime and as we've seen the prime number theorum can be dericed from this sieve. This is why the prime number theorum is an upper bound that always overestimates the actual number of primes below a certain number. I suspect there are possibly ways to refine the prime number theorum further so that it's not always over estimating but i don't know how to do this. I can just understand why it's always an overestimate.

aishohqu 6y ago
> The classic formula derived from it, n/log(n), is always above the actual number of primes No? pi(100) = 25, but 100 / log(100) = 21.7 The logarithmic integral is larger than pi for "small" arguments. But there is a pretty famous proof that li(x) - pi(x) changes signs infinitely often.
gjm11 6y ago
I'm afraid there are quite a lot of errors here. (Not everything in the following is pointing out errors, but most of it is.) 1. Yes, the quantity in the PNT is an estimate of the number of primes below a certain N. As usually stated among mathematicians, PNT is the statement that the number of primes up to x is asymptotic to Li(x), the logarithmic integral, and this is known to be sometimes over and sometimes under. 2. If you use x / log x instead of Li(x), then indeed it is known that once x isn't very small this is always an overestimate. But, again, PNT isn't the statement that it's an overestimate, it's the statement that it's a pretty good estimate. If Chebyshev or someone of the sort had proved that x / log x is an overestimate for the number of primes up to x, it would have been hailed as a fine achievement but not as a proof of PNT. 3. But your argument about "sieving out factors of a prime each time one is discovered" is not anywhere near to being a proof of PNT, let alone the stronger theorem that x / log x is an overestimate (which requires some concrete bounds on the error term in the approximation pi(x) ~ Li(x); the way you prove that x / log x is an overestimate is to show that x / log x is bigger than Li(x) by a certain amount, and then show that the difference between pi(x) and Li(x) is smaller than that certain amount; the latter is a strengthened version of the Prime Number Theorem). 4. The Wikipedia link you give is not saying that the Euler totient function is "a good way to derive the prime number theorem". It is stating a nice generalization of the prime number theorem that has the Euler totient function in its statement. 5. When you say "the prime number theorem is essentially defining the counts resulting from a sieve of primes. A sieve is an upper bound on the number of primes. [...] This is why the prime number theorem is an upper bound", I'm afraid this is completely wrong. If there is a proof of the prime number theorem that amounts to saying "look at this sieve, which easily gives an upper bound that's easily seen to be x / log x", then I don't believe anyone's found it yet. 6. It's "theorem", not "theorum".

aishohqu 6y ago

> The classic formula derived from it, n/log(n), is always above the actual number of primes No? pi(100) = 25, but 100 / log(100) = 21.7 The logarithmic integral is larger than pi for "small" arguments. But there is a pretty famous proof that li(x) - pi(x) changes signs infinitely often.

gjm11 6y ago

I'm afraid there are quite a lot of errors here. (Not everything in the following is pointing out errors, but most of it is.) 1. Yes, the quantity in the PNT is an estimate of the number of primes below a certain N. As usually stated among mathematicians, PNT is the statement that the number of primes up to x is asymptotic to Li(x), the logarithmic integral, and this is known to be sometimes over and sometimes under. 2. If you use x / log x instead of Li(x), then indeed it is known that once x isn't very small this is always an overestimate. But, again, PNT isn't the statement that it's an overestimate, it's the statement that it's a pretty good estimate. If Chebyshev or someone of the sort had proved that x / log x is an overestimate for the number of primes up to x, it would have been hailed as a fine achievement but not as a proof of PNT. 3. But your argument about "sieving out factors of a prime each time one is discovered" is not anywhere near to being a proof of PNT, let alone the stronger theorem that x / log x is an overestimate (which requires some concrete bounds on the error term in the approximation pi(x) ~ Li(x); the way you prove that x / log x is an overestimate is to show that x / log x is bigger than Li(x) by a certain amount, and then show that the difference between pi(x) and Li(x) is smaller than that certain amount; the latter is a strengthened version of the Prime Number Theorem). 4. The Wikipedia link you give is not saying that the Euler totient function is "a good way to derive the prime number theorem". It is stating a nice generalization of the prime number theorem that has the Euler totient function in its statement. 5. When you say "the prime number theorem is essentially defining the counts resulting from a sieve of primes. A sieve is an upper bound on the number of primes. [...] This is why the prime number theorem is an upper bound", I'm afraid this is completely wrong. If there is a proof of the prime number theorem that amounts to saying "look at this sieve, which easily gives an upper bound that's easily seen to be x / log x", then I don't believe anyone's found it yet. 6. It's "theorem", not "theorum".