# Infinitude of Primes - via Bertrand's Postulate

There are infinitely many primes.

### Proof

What is known as Bertrand's postulate is the content of the following assertion:

For every $n\ge 1$, there is some prime $p$ with $n\lt p\le 2n$.

It follows that between any two successive terms of the sequence $2, 4, 8, 16, \ldots$ there is at least one prime, and all these primes are necessarily different.

But Bertrand's postulate leads to a by far more subtle [Dudley, p. 80]:

### Theorem

There exists a real number $\theta$ such that $\lfloor 2^\theta\rfloor$, $\lfloor 2^{2^\theta}\rfloor$, $\lfloor 2^{2^{2^\theta}}\rfloor$, ... are all prime.

### Proof

Choose any prime $p_1$, and, for $n=1,2,\ldots$, let $p_{n+1}$ be a prime (that exists due to Bertrand's Postulate) such that

$2^{p_n}\lt p_{n+1}\lt 2^{p_{n}+1}.$

Define also

$u_{n}=\mbox{log}^{(n)}p_{n}$ and $v_{n}=\mbox{log}^{(n)}(p_{n}+1)$,

where $\mbox{log}^{(1)}k=\mbox{log}_{2}k$ and $\mbox{log}^{(n+1)}k=\mbox{log}_{2}(\mbox{log}^{(n)}k)$.

From the definition of $\{p_n\}$,

$p_{n}\lt \mbox{log}_{2}p_{n+1}\lt p_{n}+1$,

and since $p_{n+1}\le 2^{p_{n+1}}$, we have

$p_{n}\lt \mbox{log}^{(1)}p_{n+1}\lt \mbox{log}^{(1)}p_{n}+1\le p_{n}+1$.

If we apply $\mbox{log}_{2}$ to these inequalities $n$ times, we obtain

$u_{n}\lt u_{n+1}\lt v_{n+1}\le v_n$.

It follows that the limits $\displaystyle\theta =\lim_{n\rightarrow\infty}u_{n}$ and $\displaystyle\phi =\lim_{n\rightarrow\infty}v_{n}$ exist. Define $\mbox{exp}^{(1)}k=2^k$ and $\mbox{exp}^{(n+1)}k=2^{\mbox{exp}^{(n)}k}$. Then from $u_{n}\lt\theta\lt v_{n}$, we get $\mbox{exp}^{(n)}u_{n}\lt\mbox{exp}^{(n)}\theta\lt\mbox{exp}^{(n)} v_{n}$, or

$p_{n}\lt \mbox{exp}^{(n)}\theta \lt p_{n}+1$,

implying $\lfloor\mbox{exp}^{(n)}\theta\rfloor=p_n$.

### References

1. U. Dudley, Elementary Number Theory, Dover, 2008