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

U. Dudley, Elementary Number Theory, Dover, 2008

Infinitude of Primes

71866589