One way of stating the Prime Number Theorem is that the "probability" that a large number near x is prime is 1/log(x). (Here, as always, all logs are natural.)
A heuristic derivation of the prime number theorem, Frank Morgan, via Andrew Gelman, with some embellishment by me: let P(x) be the "probability" that a large integer x is prime. Then how do P(x+1) and P(x) compare? Say x is prime, which it is with "probability" P(x); it "divides" x+1 (and all larger numbers) with probability 1/x. (Of course, this doesn't actually make sense; the idea is that we're modeling the numbers divisible by x as a random set with density 1/x, which should have the same large-scale properties.) Other than this, x and x+1 are equally "likely" to be prime. So the function P satisfies
(*) P(x+1) = P(x) [P(x) (1 - 1/x)] + (1 - P(x)) P(x)
since x+1 is "prime" with probability P(x) (1-1/x) if x is "prime", and P(x) otherwise. Divide through by P(x) to get
P(x+1)/P(x) = P(x) (1-1/x) + (1-P(x))
P(x+1)/P(x) = 1 - P(x)/x.
Now, P(x+1) can be approximated by P(x) + P'(x), so we have
1 + P'(x)/P(x) = 1 - P(x)/x
P'(x)/P(x) = -P(x)/x
which has the general solution P(x) = 1/(C + log x).
This is a bit of a lie. For one thing, the difference equation (*) actually seems to have solutions that differ from those of the differential equation by a constant factor, which seems to depend on the initial conditions. (This amounts to changing the base.) For another thing, the assumption that x+1 might be divisible by x is, um, stupid if we're actually talking about prime numbers. (It's probably possible to rephrase this heuristic derivation as a rigorous result about random sets, though.) Still, it gets the prime number theorem to within a constant factor, which isn't bad for such a simple argument.
Subscribe to:
Post Comments (Atom)
5 comments:
Interesting!
Do you know the following heuristic argument, which tells you that the constant C should be zero?
The zeta function is defined by
zeta(s) = sum_n 1/n^s
and obeys the Euler product formula
zeta(s) =
prod_p 1/(1-p^{-s}).
Taking the logarithmic derivative of the latter formula, we get
zeta'(s)/zeta(s) =
(sum_p (log p)p^{-s} )
+O(1)
where O(1) is an analytic function of s that remains bounded as s -> 1.
Now, by approximation by an integral,
zeta(s) = 1/(s-1)+O(1)
so zeta'(s)/zeta(s)=
1/(s-1)+O(1)
and we deduce that
sum_p log p/p^s =
sum_n 1/n^s + O(1) (*)
Approximating both sides of equation (*) by integrals, we have
int P(x) log x dx/x^s = int dx x^{-s}+O(1).
Now, that tells you P(x) = 1/log(X) + e(X) where e is an error term small enough that
int e(x) log x dx/x^s
remains bounded as s -> 1.
Intuitively, this shows that
e(x) = o(1/(log x)^2).
If you can make that rigorous, you have a new proof of the prime number theorem. But this really can be turned into a proof that, if e(X) = A/(log x)^2
+ o(1/(log x)^2)
then A is zero. In particular,
1/(C + log X) =
1/log X - C/(log X)^2 + o(1/(log x)^2)
so, if your heuristic is correct, then C=0.
You can push this argument further by taking d derivatives of equation (*) with respect to s. This gives
sum (log p)^{d+1}/p^s =
sum (log n)^d/n^s+O(1).
(Here we need to know that O(1) is analytic in s, so that we know each derivatives stay bounded as well.)
Running through the same approximation by integrals heuristic, you get that
int e(x) (log x)^{d+1}
*dx/x^s
remains bounded as s -> 1 for any d. Heuristically, this tells you that
e(x) =
o(1/(log x)^{d+1})
and rigorously it tells you that you can't have
e(X) = A/(log x)^{d+1}
+ o(1/(log x)^{d+1})
In the same vein, what about the Legendre's conjecture, saying that there is at least one prime between n^2 and (n+1)^2? Among 2n+1 consecutive numbers, 1/2 are odd, among these 2/3 aren't divisible by 3, etc., (p-1)/p aren't divisible by p. Taking all the primes up to n+1 and multiplying all these factors together, and then by 2n+1, we get the value more than 2, so the Legendre's conjecture is plausible.
pawan drop ping webct exciting btinternet booths mcgill expert hallsumit verkhovna
servimundos melifermuly
hydrants coated touch isolation dysphagia grunge iiianupama resignation gabon channelled stationary
servimundos melifermuly
Post a Comment