8
$\begingroup$

I've always wondered if it has something to do with the idea that the probability that an integer is divisible by a prime $p$ is $1/p$.

$\endgroup$
5
  • 2
    $\begingroup$ One would be surprised by an unnatural logarithm! $\endgroup$ Jul 16, 2018 at 20:24
  • $\begingroup$ Could you expand "PNT"? What is PNT? $\endgroup$ Jul 16, 2018 at 20:26
  • 1
    $\begingroup$ @RolazaroAzeveires Presumably it's the Prime Number Theorem, the fact that the number of primes below any positive number $x$ is approximately $x/\ln(x)$. $\endgroup$
    – Arthur
    Jul 16, 2018 at 20:27
  • $\begingroup$ math.stackexchange.com/questions/2144940/… $\endgroup$
    – Alex R.
    Jul 16, 2018 at 20:28
  • 1
    $\begingroup$ In Granville's "WHAT IS THE BEST APPROACH TO COUNTING PRIMES?", p. 8 , he shows that if $π(x) \sim c x / \log(x)$ then $c = 1$. See also p. 81 (end of §4) of Chandrasekharan - Introduction to Analytic Number theory. In other words, if PNT is related to some logarithm, then it must be a natural logarithm. $\endgroup$
    – Watson
    Jan 28, 2020 at 21:08

1 Answer 1

13
$\begingroup$

Here is a heuristic argument. As you say, heuristically the probability that an integer is divisible by a prime $p$ is $\frac{1}{p}$, hence the probability that it's not divisible by $p$ is $1 - \frac{1}{p}$. Making the simplifying assumption that these events are independent, we get that the probability that an integer $n$ is prime is the probability that it isn't divisible by any smaller primes, hence is

$$\prod_{p < n} \left( 1 - \frac{1}{p} \right).$$

So we want to explain why this grows like $\frac{1}{\ln n}$. Well, let's invert it, getting

$$\prod_{p < n} \frac{1}{1 - \frac{1}{p}} = \prod_{p < n} \left( 1 + \frac{1}{p} + \frac{1}{p^2} + \dots \right).$$

Expanding this out produces a sum over terms of the form $\frac{1}{k}$ where $k$ ranges over all positive integers whose prime divisors are all less than $n$. (This is closely related to the Euler product factorization of the Riemann zeta function.) The bulk of this sum is

$$\sum_{k < n} \frac{1}{k} \sim \ln n$$

by the usual Riemann sum argument, and we are going to blithely ignore the rest of the sum (this can be done a bit more carefully but eh). Done!

$\endgroup$
5
  • $\begingroup$ This was exactly what I was looking for! Can you say a little more about what happens to the rest of the sum? $\endgroup$ Jul 17, 2018 at 10:52
  • $\begingroup$ Is this a proof of the Prime Number theorem? $\endgroup$
    – Ryder Rude
    Mar 2, 2019 at 11:54
  • $\begingroup$ @Ryder: no, not even close. You can approach the PNT by estimating an expression that looks like this one, but actually proving that the estimate is what you want it to be is very hard. This is, as stated in the first sentence, just a heuristic argument; it's the sort of thing you might write down in order to conjecture the PNT if you didn't know it already. $\endgroup$ Mar 2, 2019 at 17:12
  • $\begingroup$ But I think you just proved it. What steps is your argument are not rigorous enough? $\endgroup$
    – Ryder Rude
    Mar 3, 2019 at 10:33
  • $\begingroup$ 1) The first expression is not actually the probability that $n$ is prime, it's an approximation and I didn't bother to quantify how accurate the approximation is. 2) Then I estimated this expression and didn't bother to quantify how accurate the estimate is. So I've lost error terms twice and I need to be much more careful with these error terms to prove the PNT, which involves much more work than I've done so far. $\endgroup$ Mar 3, 2019 at 17:02

Not the answer you're looking for? Browse other questions tagged .