Sunday, July 13, 2008

Differential equation estimating the distribution of primes

Let me begin with this disclaimer, first: though mathematically trained (physics background), I am not a mathematician. OK, got that out of the way.


I have found a simple way to derive Gauss's estimate of the prime density function using probability heuristics, alone.


Excerpt From MathWorld:

In 1792, when only 15 years old, Gauss proposed that pi(n), the prime density function


Gauss later refined his estimate to



I have not seen a simple derivation for this estimate, and if it exists, I am surprised why it is not more widely used in expositions on the subject of the distribution of primes. What follows is a very short argument based on a probability model. According to this model, we'll find that the distribution of primes is governed by a delay differential equation of the form

Q'(x) = - Q(x) Q( √x ) / x

which has a solution

Q(x) = 1 / 2 ln x

Anyway, to me, what's interesting is how using some specious probability arguments about the distribution primes I was able to set up the equation and try a test function inspired by Gauss's estimate to solve it. This hints at something more meaningful in my Clouseau-esque accident.

The setup

The setup, I have come to find, is similar in spirit to Harald Cramer's probabilistic, heuristic arguments for estimating of the distribution primes (the difference here being that we don't use any other results from number theory). Here it is..

Equ. 1:
The joint probability of a randomly chosen positive number n not
being divisible by two relative primes p and k is (1 - 1/p)(1 - 1/k).

Equ. 2:
Define Q(x) = (1 - 1/p)
taken over all primes px.

Equ. 2a:
The joint probability of a randomly chosen positive number n not being divisible by any prime px is Q(x).

Using Equ. 2a, vigorous hand waving, and a pinch of salt, we can say

Equ. 3:
The probability that a randomly chosen positive number x is a prime is Q( √x ).

What we're saying here is that for x to be prime, it suffices to show that it is not divisible by any prime less than the square root of x. Equ. 3 says that in the neighborhood of x, the 'average' distance between primes is 1 / Q( √x ).

Now the d.d.e. above comes from trying to approximate Q(x) using this probabilistic model. The idea is to use that approximation in order to estimate a prime counting function:

Q (√x) dx

But we don't have an analytic expression that approximates Q, yet. Instead of setting up an integral equation, we try a differential approach. Consider the change in Q as x passes over 2 very large consecutive primes p1 < p2:

ΔQ = -Q(p1) / p2 ~ -Q(x) / x
Δx ~ 1 / Q( √x )

Dividing the top equation by the bottom one, you get

Q'(x) = - Q(x) Q( √x ) / x

the d.d.e. I described above.

The solution

I had read somewhere how the 15 year old Gauss had been able to come up with his logarithmic integral for estimating the number of primes less than n. Was his integral inspired by a similar probabilistic argument? Maybe, but googling it, I couldn't find much. So, I plugged in C / ln x and solved for the constant C (=1/2).

Q(x) = 1 / 2 ln x

Does it mean anything?

I suspect it might, which is why I posted it. I did a bit of cursory reading on the topic, but alas, I'm an amateur. My claim that

Q(x) = ( 1 - 1/p) ~ 1 / 2 ln x

does not agree with Mertens' asymptotic formula (1874)

( 1 - 1/p) ~ exp(-C) / ln x,

where C is Euler's constant.

Still, there's something here that piques my nose. My result, when plugged into the prime counting integral, agrees exactly with Gauss's estimate:

Q (√x) dx ~ (1 / ln x) dx
What do you think? Is this interesting, or is this old?

7-09 Addendum: Interestingly, if we adjusted the model so that
Q'(x) = - Q(x) Q( x1/n ) / x

then Gauss's estimate would still hold for most n. It's as if the forward distribution constrains that back distribution.
Post a Comment