Prime Number Density

For $n \in \mathbb{N}^+$, let $\pi(n)$ be the number of prime numbers that are $\le n$. The prime number theory states that

We show here a weaker version in which

It states that the density of the prime numbers in $[1, n]$ is $\Theta(1 / \log_2 n)$, which is inversely proportional to the number of bits required to represent $n$.

Theorem. For $3 \le n \in \mathbb{N}^+$, it holds that

$$\frac{1}{2 \log_2 n} \le \frac{\pi(n)}{n} \le \frac{2}{\ln n}$$

For the first inequality, we will show that $\forall k \in [n]$,

Roughly speaking, the prime factorization of $\binom{n}{k}$ consists of at most $\pi(n)$ different primes $\le n$. The inequality follows if we can prove that the highest power of a prime in the factorization is at most $n$. We can choose $k = \lfloor n / 2 \rfloor$ to maximize the lower bound.

For the second inequality, we use

for $k \in \mathbb{N}^+$ and upper bound $\binom{ 2k + 1}{ k }$ by $2^{2k}$. We only consider odd numbers $2k + 1$ here because $\pi(2k + 2) = \pi(2k + 1), \forall k \in \mathbb{N}^+$.

Proof of The Theorem, Part 1.

We need a few lemmas for the proof.

Definition. Given a prime number $p$ and $n \in \mathbb{N}^+$, $m_p(n)$ is the number of large integer $k$ such that $p^k$ divides $n$.

Lemma 1.

$$m_p(n!) = \sum_{j = 1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor$$

Proof. We count the number of time $p$ divides $n!$. Each multiple of $p$ that is in $[n]$ contributes a factor. Each multiple of $p^2$ that is in $[n]$ contributes another factor, and so on.

$\square$

Lemma 2.

Let $a, b \in \mathbb{N}^+$, $a > b > 0$. Given a prime $p$ and an integer $k \in \mathbb{N}^+$, if $p^k$ divided $\binom{a}{b}$, then $p^k \le a$.

Proof. Let $k' = m_p(\binom{a}{b})$. It suffices to show that $p^{k'} \le a$.

Each summand is either 1 or 0. Further, when $p^j > a$ (i.e., $j > \log_p a$), the summand is 0. It concludes that $k' \le \log_p a$.

$\square$

Lemma 3.

$$\binom{n}{ \lfloor n / 2 \rfloor} \le n^{ \pi(n) }$$

Proof. Consider the unique prime factorization of $\binom{n }{ \lfloor n / 2 \rfloor}$,

where $p_i \neq p_j$, for $1 \le i < j \le t$. By Lemma 2 we have $\forall i \in [t]$, $p_i^{k_i} \le n$ and $p_i$ is a prime number at most $n$. Hence $t \le \pi(n)$. It follows that

$\square$

Lemma 4.

$$\frac{1}{n + 1} 2^{n} \le \binom{n}{ \lfloor n / 2 \rfloor } \le n^{\pi(n)}$$

Proof. Given $n \in \mathbb{N}^+$, as $\binom{n}{k}$ is maximized when $k = \lfloor n / 2 \rfloor$ for ($k =0, 1, 2, ..., n$), it holds that

This establishes the lower bound.

$\square$

By Lemma 4,

The final inequality holds when $\log (n + 1) \le 0.5 n$. It suffices to take $n \ge 7$, as $\log (7 + 1) = 3 < 3.5$ but $\log (3 + 1) = 2 > 1.5$. When $n < 7$, we can check manually that $\pi(n) / n \ge 0.5 / \log n$ holds.

$\blacksquare$

Proof of The Theorem, Part 2.

Lemma 5.

For $k \in \mathbb{N}^+$,

$$\binom{2k + 1}{ k } \ge \prod_{k + 2 \le p \le 2k + 1 \wedge p \text{ is prime}} p$$

Proof. First,

For a prime $p \in [k + 2, 2k + 1]$, it divides the numerator but not the denominator.

$\square$

We prove that $\pi(n) \le 2 n / \ln n$ by induction. When $n > 2$ is even, $\pi(n) = \pi(n - 1)$. As $2 n / \ln n$ increases with $n$, it suffices to prove this for odd numbers of $n$. Suppose that $n = 2k + 1$ for some $k \in \mathbb{N}^+$, then

Further

Therefore,

By induction on $\pi(k + 1)$, we arrive at

In order that

we need

This holds when $n \ge 107$. It is left to verify manually that $\pi \le 2 n / \ln n$ holds for all $n < 107$.

Reference

[1] Jan-Hendrik, "Chapter 1: Introduction to prime number theory", ANALYTIC NUMBER THEORY