Showing the density of primes around $n$ is approximately $1/\ln(n)$

392 Views Asked by At

The following shows the density of primes around $x$ is approximately $1/\ln(x)$. The argument, although based on approximation, benefits from being simple enough for those without advanced mathematics to understand.

Question - is the argument valid? Are there errors in the logic?


Step 1

We start by examining the prime factors of $n!$.

Multiples of prime $p$ contribute $\lfloor n/p \rfloor$ factors, multiples of $p^2$ contribute $\lfloor n/p^2 \rfloor$, and so on.

Therefore the number of prime factors $p$ of $n!$, written $\nu_p(n!)$ is:

$$\nu_{p}(n!)=\sum_{k}\left\lfloor \frac{n}{p^{k}}\right\rfloor $$

Like any integer, $n!$ is a product of all its prime factors:

$$ n! = \prod_{p\leq n} p^{\nu_p(n!)}$$

We can take the logarithm to turn the product into a sum:

$$ \sum_{k \leq n} \ln(k) = \sum_{p \leq n} \nu_p(n!) \ln(p)$$

We'll example the LHS and RHS of this expression.


Step 2

We can approximate the LHS sum with an integral.

$$ \begin{align} \sum_{k \leq n} \ln(k) &\approx \int_2^n ln(x)\;dx \\ \\ &\approx n\left(\ln(n)-1\right) -2\left(\ln2-1\right) \\ \\ &\approx n\left(\ln(n)-1\right) \end{align}$$

We've discarded the constant $2(\ln2-1)$ as it is small compared to large $n$. Similarly, the upper limit of the integral is $n$ and not $n+1$ because for large $n$, $\ln(n+1)\approx\ln(n)$.


Step 3

The RHS can be simplified if we can find an easier approximation for $\nu_p(n!)$. We do this by considering lower and upper bounds for it.

Let's compare $\nu_p(n!)$ to the first expression in its expansion.

$$ \nu_{p}(n!)\geq\left\lfloor \frac{n}{p}\right\rfloor >\frac{n}{p}-1 $$

Let's now consider the expansion of $\nu_p(n!)$ but with each term without the floor operator $\lfloor \rfloor$ applied.

$$ \nu_{p}(n!)\leq\sum_{k}\frac{n}{p^{k}}=\frac{n}{p}\frac{1}{1-1/p}=\frac{n}{p-1} $$

We can combine these lower and upper bounds.

$$ \frac{n}{p}-1 < \nu_p(n!) \leq \frac{n}{p-1} $$

For large $n$, we can approximate

$$\nu_p(n!) \approx n/p$$


Step 4

Let's remind ourselves of the key equality before we apply these approximations.

$$ \sum_{k \leq n} \ln(k) = \sum_{p \leq n} \nu_p(n!) \ln(p)$$

Replacing the LHS and RHS with our approximations.

$$ \begin{align} n\left(\ln(n)-1\right) &\approx \sum_{p \leq n} \frac{n}{p} \ln(p) \\ \\ \ln(n)-1 & \approx \sum_{p \leq n} \frac{\ln(p)}{p}\end{align} $$

If we now think about the rate of change of both sides with respect to $n$, that is, the derivative $d/dn$.

$$ \frac{1}{n} \approx \rho(n) \frac{\ln(n)}{n} $$

Here $\rho(n)$ is the the density of primes around $n$. The rationale for it is that the sum increases when $n$ is a prime, and this happens at a rate of $\rho(n)$ by definition of $\rho(n)$.

Rearranging gives us our desired result.

$$ \boxed{ \rho(n) \approx \frac{1}{\ln(n)} } $$


The approach here is inspired by this YouTube video [link].