10
$\begingroup$

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) $$f(x)\left(1-f(x)/{x} \right).$$ How do I show that? I can go on to show

$$\frac{df}{dx} + \frac{f^2}{x}=0$$

and thus $\frac{1}{\log{x}} + c$ is solution but I can't show that step on how $f(x)$ changes. please advise

$\endgroup$
2
  • $\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$ Aug 27, 2010 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$ Aug 30, 2010 at 19:02

4 Answers 4

22
$\begingroup$

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.

$\endgroup$
3
  • 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$ Aug 27, 2010 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$ Aug 27, 2010 at 16:51
  • 4
    $\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$ Aug 27, 2010 at 18:39
11
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Kac's book is excellent. (And very short!) $\endgroup$ Aug 27, 2010 at 18:48
8
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Another way to obtain OP's differential equation is as follows: $$f(x) \approx \prod_{p < x} \left( 1-1/p \right) \approx \exp( - \sum_{p<x} 1/p) \approx \exp( -\int_{1}^{x} \frac{f(t) dt}{t}).$$ Taking logarithms and differentiating w.r.t $x$, we obtain the desired ODE (of course, the argument is completely informal).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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