Upper Bounds for Prime Numbers

Theorem

Let $p: \N \to \N$ be the prime enumeration function.

Then $\forall n \in \N$, the value of $p \left({n}\right)$ is bounded above.

In particular:

• $\forall n \in \N: p \left({n}\right) \le 2^{2^{n-1}}$
• $\forall n \in \N: p \left({n}\right) \le \left({p \left({n - 1}\right)}\right)^{n-1} + 1$
• $\forall n \in \N: p \left({n}\right) < 2^n$.

Proof

Let us write $p_n = p \left({n}\right)$.

Proof of First Assertion

• First we show that $p \left({n}\right) \le 2^{2^{n-1}}$.

For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition $p \left({n}\right) \le 2^{2^{n-1}}$.

Basis for the Induction

• $P(1)$ is true, as this just says $2 \le 2^{2^0} = 2$.

This is our basis for the induction.

Induction Hypothesis

• Now we assume that, for some $k \in \N$, each of $P \left({1}\right), P \left({2}\right), \ldots, P \left({k}\right)$ is true. We need to show that it logically follows that $P \left({k+1}\right)$ is true.

That is, that:

$p \left({k+1}\right) \le 2^{2^k}$.

Induction Step

This is our induction step:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle p \left({k+1}\right)\)	\(=\)	\(\displaystyle p_1 p_2 \cdots p_k + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Euclid's Theorem
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle 2 \times 2^2 \times 2^{2^2} \times \cdots \times 2^{2^{k-1} } + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by the induction hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^{1 + 2 + 2^2 + 2^3 + \cdots + 2^{k-1} } + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Exponent Combination Laws
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^{2^k - 1} + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Sum of Geometric Progression
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle 2^{2^k - 1} + 2^{2^k - 1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	since $1 \le 2^{2^k - 1}$ for all $k$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^{2^k}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

The result follows by the Second Principle of Mathematical Induction.

$\blacksquare$

Proof of Second Assertion

• Next we show $\forall n \in \N: p \left({n}\right) \le \left({p \left({n - 1}\right)}\right)^{n-1} + 1$.

Let us take $N = p_1 p_2 \cdots p_n + 1$.

By the same argument as in Euclid's Theorem, we have that either $N$ is prime, or it is not.

If $N$ is prime, then either $N = p_{n+1}$ or not, in which case $N > p_{n+1}$.

In the second case, $N$ has a prime factor not in $\left\{{p_1, p_2, \ldots, p_n}\right\}$, so it must have a prime factor greater than any of $\left\{{p_1, p_2, \ldots, p_n}\right\}$.

In any case, the next prime after $p_n$ can be no greater than $p_1 p_2 \cdots p_n + 1$.

Hence the result.

$\blacksquare$

Proof of Third Assertion

We have from Bertrand's Conjecture that for each $n \ge 2$, there exists a prime $p$ such that $n < p < 2 n$.

For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition $p_n < 2^n$.

Basis for the Induction

• $P(2)$ is true, as this just says $p_2 = 3 < 2^2 = 4$.

This is our basis for the induction.

Induction Hypothesis

• Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

$p_k < 2^k$.

Then we need to show:

$p_{k+1} < 2^{k+1}$.

Induction Step

This is our induction step:

Suppose that $p_k < 2^k$ for some $k \ge 2$.

By Bertrand's Conjecture, there exists a prime $q$ such that $2^k < q < 2^{k+1}$.

So we have $p < 2^k < q < 2^{k+1}$.

But as $q$ is a prime exceeding $p_k$, it means $p_{k+1} \le q < 2^{k+1}$.

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore $\forall n \in \N: p \left({n}\right) < 2^n$.

$\blacksquare$

Note

In the first two cases it can be seen that the limit found is wildly extravagantly large. However, they are results that are easily established, and they have their uses.