Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose there is a function f(x) which is the "probability" that the integer x is prime. The integer x is prime with probability f(x), and then divides the larger integers with probability 1/x; so as x changes from x to x+1, f(x) changes to (roughly)


How do I show that? I can go on to show

df/dx +f^2/x=0

and thus 1/(logx +c) is solution but I can't show that step on how f(x) changes. please advise

share|improve this question
There are a number of people who have looked at probabilistic models of prime distribution. One of my favorites is the physicist Sanjoy Mahajan, who looked at primes in his Ph.D. thesis. –  Theo Johnson-Freyd Aug 27 '10 at 19:48
Sanjoy Mahajan wrote, in his thesis, about "order-of-magnitude physics", related to the "street-fighting mathematics" course that he's taught. I knew this but didn't realize that his thesis included applications of that sort of methodology to primes! –  Michael Lugo Aug 30 '10 at 19:02

3 Answers 3

up vote 13 down vote accepted

First of all, I assume you understand that this is meant to be a nonrigorous argument, so there will be a limit to how rigorous I can make my answer.

The intuition here is that $n$ is prime if and only if it is not divisible by any prime $<n$. So we "should" have $$f(n) \approx \prod_{p < n} \left( 1-1/p \right).$$ Similarly $$f(n+1) \approx \prod_{p<n+1} \left( 1-1/p \right) = \prod_{p < n} \left( 1-1/p \right) \cdot \left\{ \begin{matrix} \left( 1-1/n \right) \ \mbox{if}\ n\ \mbox{is prime} \\ 1 \ \mbox{if}\ n\ \mbox{is not prime} \end{matrix} \right. \approx f(n) \cdot \left\{ \begin{matrix} \left( 1-1/n \right) \ \mbox{if}\ n\ \mbox{is prime} \\ 1 \ \mbox{if}\ n\ \mbox{is not prime} \end{matrix} \right. .$$ Since $n$ is prime with "probability $f(n)$", we interpolate between the two cases next to the brace by writing: $$f(n+1) \approx f(n) \left( 1-f(n)/n \right).$$ One might argue that it would be better to interpolate with a factor of $(1-1/n)^{f(n)}$, but this will make no difference in the asymptopics as $(1-1/n)^{f(n)} = 1-f(n)/n+O(1/n^2)$.

This argument is famously fishy, because it gives the right answer, but the intermediate point is wrong! The actual asymptopics of $\prod_{p<n} \left( 1-1/p \right)$ do not look like $1/\log n$, but like $e^{-\gamma} /\log n$. I've never seen a good intuitive explanation for why we get the wrong estimate for $\prod_{p<n} \left( 1-1/p \right)$, but the right estimate for the density of the primes.

share|improve this answer
Note that if the bound on the product formula for $f(n)$ is set to $n^{1/2}$ instead of $n$, then the associated constant $2e^{-\gamma}$ is much closer to 1. Not a full explanation, but it shows how the original guess might be off by a constant factor. –  François G. Dorais Aug 27 '10 at 16:48
I have an intuition for why the bound is off by a constant factor, (primes which are too close to $n$ are unlikely to divide $n$, so they shouldn't appear with their full weight.) What I don't understand is why, having gotten this wrong, the constant in the estimate for $\pi(n)$ comes out exactly right. –  David Speyer Aug 27 '10 at 16:51
Wow. Smart guy. Thanks. –  David Willis Aug 27 '10 at 17:12
@David Speyer: There is a survey article by Andrew Granville where he discusses the issue you brought up in your last paragraph. dms.umontreal.ca/~andrew/PDF/cramer.pdf –  Micah Milinovich Aug 27 '10 at 18:39

You might read "Statistical Independence in Probability, Analysis, and Number Theory" by Mark Kac.

Meanwhile, Harald Cramer did a very good job of investigating the consequences of your idea with $f(x) = \frac{1}{\log x}$, which seemed fine, until in 1985 Helmut Maier showed that it gave incorrect estimates for the number of primes in short intervals. The precise nature of the word "incorrect" here is worth a look at the Maiers article, or later summaries.

share|improve this answer
Kac's book is excellent. (And very short!) –  Michael Lugo Aug 27 '10 at 18:48

I came up with this argument before (and I'm sure many other people have, independently). Start like David Speyer does, above, until you get to the equation

$$ f(n+1) \approx f(n) (1 - f(n)/n) $$

Therefore, you have

$$ f(n+1) - f(n) \approx -f(n)^2/n$$

and if we figure that $f$ is a ``nice'' function, then $f(n+1) - f(n) \approx f^\prime(n)$. So $f$ is approximately a solution to

$$ f^\prime(x) \approx -f(x)^2/x $$

where I'm calling the variable $x$ now, instead of $n$, to emphasize the change from discrete to continuous. It's easy to check that $f(x) = 1/\log x$ solves this differential equation.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.