Heuristic Derivation of Prime Number Theorem

The Prime Number theorem says that the probability P(x) that a large integer x is prime is about 1/log x. At about age 16 Gauss apparently conjectured this estimate after studying tables of primes. Hugh Bray via Greg Martin suggested to me the following heuristic way to approach the same conjecture, which appeared in my Math Chat column on August 19, 1999:

Suppose that there is a nice probability function P(x) that a large integer x is prime. As x increases by \Delta x = 1, the new potential divisor x is prime with probability P(x) and divides future numbers with probability 1/x. Hence P gets multiplied by (1-P/x),\Delta P = -P^2/x, or roughly

P' = -P^2/x.

The general solution to this differential equation is P(x) = 1/log cx.

3 Comments

  1. Statistical Modeling, Causal Inference, and Social Science:

    Heuristic Derivation of Prime Number Theorem …

    Here’s something else from Frank Morgan: The Prime Number theorem says that the probability P(x) that a large integer x is prime is about 1/log x. At about age 16 Gauss apparently conjectured this estimate after studying tables of primes…….

  2. Joe Shipman:

    Here’s another easy heuristic derivation of PNT. Consider the binomial coefficient (2n!)/(n!n!). Which primes divide this? The ones between n and 2n, obviously; but also the ones between (n/2) and (2n/3) because they will appear twice in the denominator and 3 times in the numerator. Also the ones between (n/3) and (2n/5), which occur 5 times in the numerator and 4 times in the denominator. So the length of the union of subintervals of (0,2n) which can contain primes dividing the coefficient is 2n(1 – 1/2 + 1/3 – 1/4 + 1/5 – …) = 2n log 2. But the log of the binomial coefficient is about 2n log 2, and each prime is contributing about log n to the log of the binomial coefficient so there’s better be about one for every log n integers. (It is very easy to convert this to a proof that IF the limit of pi(x)log(x)/x exists then the limit must be 1, the hard part is showing the limit exists.)

  3. D Sullivan:

    A paper from A. Peterman [1] used a Renormalization Group (RG) approach from condensed matter & particle physics (a la Ken Wilson) to yield the same heuristic differential equation. An interesting interpretation of the PNT is that the prime-number density, unlike the density of the integers, is not scale invariant, but rather is approximately scale invariant so as long as one expresses the variation of the density at a high scale in terms of the density near that scale (instead of the density at a lower scale).

    For example, we can express P(x) in terms of P(s), the PN density at scale x=s (which amounts to interpreting the constant “c” in the original post)

    P(x, P(s)) = P(s) / ( 1 + P(s) log(x/s))

    Note that P(x, P(y, P(z))) = P(z) / ( 1 + P(z) log (z/x) ) which follows from the RG assumptions stated in the paper.

    Further, if we heuristically argue that P(s) is small for x near s, we can use perturbation theory to derive the next order of approximation to the solution to P’ = -P^2/ ( x – P); namely, if we denote this next functional approximation by PP,

    PP(x, P(s)) = P(s) / ( 1 + P(s) log(x/s) * ( 1 + P(s) * loglog(x/s) ) )

    is the solution to P’ = -P^2/x – P^3/x^x.

    [1] A. Petermann, “The so-called renormalization group method applied to the specific prime number logarithmic decrease”, Euro. Phys. J. C, 17, p367 (2000).DOI 10.1007/s100520000469. First page. Preprint.

Leave a Reply

Your email address will not be published. Required fields are marked *