A Comment on the Prime Number Theorem

(Note: I’m describing here a topic where I can’t personally follow the proofs. Think of this as being a second-hand account)

The prime number theorem states that asymptotically the number of primes less than N is approximately N / \log(N). It is fairly easy to prove that this is true up to a constant, that is, letting \pi(x) denote the number of primes less than x, that

\frac{1}{C} \frac {N} {\log(N)} < \pi(N) < C \frac {N} {\log(N)}

for some constant C. So the interesting thing is the constant factor.

When you think about it, it’s rather strange that the constant factor is exactly one. Consider a similar case: counting the number of twin primes less than a given N. The value is conjectured to be approximately C N / \log(N)^2, where

C = 2 \prod_{p\text{ prime}, p \geq 3} 1 - \frac{1} {(p-1)^2}

This constant C can be generated as follows: We want to determine the probability that q, q+2 are both prime for q < N-2. The probability for q to be prime and for q+2 to be prime are both \frac{1} {\log(N}, so assuming they are independent the probability for both being prime is \frac{1} {\log(N)^2}. However, these probabilities are not independent. For example, assuming q and q+2 are independent would lead to a probability of \frac{1}{4} of them both
being odd, whereas the actual probability is \frac{1}{2}. Taking this into account, the probability estimate should be twice what it was before, up to \frac{2} {\log{N}^2}. Similarly, it is possible to calculate that the probability that a certain prime p \geq 3 divides neither q nor q+2 is different by a factor of 1-1/q^2 than it would under the indepence assumption. Multiplying all these factors out you get the constant C.

You would expect something similar to happen when counting primes: That there should be some constant factor that is some product over all primes, and that by default it would be a fairly random-looking number rather than exactly 1. The naive estimate \pi (N) \approx N \prod_p (1-1/p) = 0 fails. Still, it seems strange that the fact that each prime number is odd, which reduces the frequency of prime by a half, and that they are all 1 or 2 mod 3, which reduces by \frac{2}{3}, and so, all reduce to a constant factor of exactly 1.

The explanation is this: The frequency of the primes is self-adjusting. For instance, in the interval [1, N] there are less primes than there are supposed to be, that would make any number in [N, 2 N] more likely to be prime. Thus facts like how the specific number 2 is prime in the long run make no difference in the density of prime.