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

  • $\begingroup$ 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. $\endgroup$ – Theo Johnson-Freyd Aug 27 '10 at 19:48
  • $\begingroup$ 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! $\endgroup$ – Michael Lugo Aug 30 '10 at 19:02

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.

  • 2
    $\begingroup$ 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. $\endgroup$ – François G. Dorais Aug 27 '10 at 16:48
  • 2
    $\begingroup$ 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. $\endgroup$ – David E Speyer Aug 27 '10 at 16:51
  • 3
    $\begingroup$ @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 $\endgroup$ – 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.

  • $\begingroup$ Kac's book is excellent. (And very short!) $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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