A heuristic approach to the Prime number theorem

514 Views Asked by At

Let us consider the Sieve of Eratosthenes and the rough probability $(1-1/p)$ that a natural number $n \in \mathbb{N}$ is not divisible by a prime number $p<n$. If we assume that the conditions of non-divisibility are independent, the probability that $n$ is prime, i.e., it is not divisible by any prime number less than $n$, has the naive estimate $P(n)=\prod_{p < n}(1- 1/p)$.

But can we obtain a similar result by considering the sieve process and attaching a weight function $P: \mathbb{N} \rightarrow \mathbb{Q}$ of a number being prime to every integer less than $n \in \mathbb{N}$ in the following way: $P(n)=\prod_{x=2}^{n-1}(1- P(x)/x)$ ? That is, we sieve with the both prime and non-prime integers and simply add a weight to what degree/fraction an integer is prime. This should give roughly the same naive estimate as if we sieve only with primes $p < n$ and have $P(p)=1$.

If all that makes sense and we may assume that there exists a suitable probabilistic function $P$, we also have $P(n+1)=P(n)(1- P(n)/n)$. Now, if $n$ is very large integer, the change from $n$ to $n+1$ becomes infinitesimally small. This motivates to consider a differentiable weight function $P: \mathbb{R}^{+} \rightarrow \mathbb{R}$, so that we have an approximation $P(n+1) \approx P(n)+P'(n)\cdot 1$, and thus we end up with a differential equation $P'(n)=-P^2(n)/n$. The general solution $P(n)=1/{\ln(Cn)}$ can be empirically fixed to agree with our specific problem if we set $C=1$. Moreover, by weighting the "primeness" of every integer, we may estimate the prime-counting function, i.e., $$\pi(n) \sim \sum_{x=2}^{n}P(x)=\sum_{x=2}^{n}\frac{1}{\ln(x)} \sim \int_{2}^{n} \frac{dx}{\ln(x)}.$$


EDIT: This approach is already well-known, see https://sites.williams.edu/Morgan/2008/10/11/heuristic-derivation-of-prime-number-theorem/ https://maa.org/sites/default/files/pdf/upload_library/2/Marshall-MathMag-2014.pdf

The latter reference considers a more accurate estimation, and here we may offer a slightly different presentation. That is, we need to sieve only up to $p = \sqrt{n}$ since a prime number $\sqrt{n} < p < n$ can't divide $n$ if we already assume that $n$ is not divisible by a prime number $2 \leqq p \leqq \sqrt{n}$. Thus, we have a better estimate $P(n)=\prod_{p < \sqrt{n}}(1- 1/p)$. Via a change of variable $n \rightarrow n^2$, we have $P(n^2)=\prod_{p < n}(1- 1/p)$.

Next we reproduce our previous argument:

$P(n^2)=\prod_{x=2}^{n-1}(1- P(x)/x);$

$P((n+1)^2)=P(n^2)(1- P(n)/n);$

$P((n+1)^2) \approx P(n^2)+ P'(n^2)\cdot 2n \cdot 1.$

We end up with a differential equation $P'(n^2)= -P(n^2)P(n)/(2n^2),$ and via a change of variable $n^2 \rightarrow n$, we have

$$P'(n)=-\frac{P(n)P(\sqrt{n})}{2n}.$$

This equation is not easy to solve, but we can check that $P(n)=1/\ln(n)$ is a solution. The equation was found by G. Hoffman de Visme, see the reference above.

1

There are 1 best solutions below

0
On

I am not sure what your question is, and this might not be an answer but maybe you are interested in this

Improved sieve for primes and prime twins?

where we try to improve the sieve.

It depends alot if you accept using primes to sieve or not.

Also some sieves or methods could work better for some intervals but worse for others.

For instance for $y$ between $20$ and $200$ the number of primes between $2$ and $y$ are close to

$$x(2 + 1/x)(3/2 + 1/x)(5/4 + 1/x)... = y$$

where we solve for $x$.

For instance

$$x(2 + 1/x)(3/2 + 1/x)(5/4 + 1/x)... = 101$$

gives $x = 24.915$

pretty close.

The power of your approximation relates to the amount of ideas you allow. Such as a list of small primes, small diophantines to solve, mod arithmetic etc