Mills' Theorem

From ProofWiki
Jump to: navigation, search


Theorem

There exists a real number $A$ such that $\left\lfloor{A^{3^n} }\right\rfloor$ is a prime number for all $n \in \N_{>0}$, where:

$\left\lfloor{x}\right\rfloor$ denotes the floor function of $x$
$\N$ denotes the set of all natural numbers.


Proof

We define $f \left({x}\right)$ as a prime-representing function if and only if:

$\forall x \in \N: f \left({x}\right) \in \Bbb P$

where:

$\N$ denotes the set of all natural numbers
$\Bbb P$ denotes the set of all prime numbers.

Let $p_n$ be the $n$th prime number.

From Difference between Consecutive Primes:

$p_{n+1} - p_n < K p_n^{5/8}$

where $K$ is an unknown but fixed positive integer.


Lemma 1

$\forall N > K^8 \in \Z: \exists p \in \Bbb P: N^3 < p < \left({N + 1}\right)^3 - 1$


Proof

Let $p_n$ be the greatest prime less than $N^3$.

\(\displaystyle N^3\) \(<\) \(\displaystyle p_{n+1}\) because $p_n$ is the greatest prime less than $N^3$
\(\displaystyle \) \(<\) \(\displaystyle p_n + K {p_n}^{\frac 5 8}\) Difference between Consecutive Primes
\(\displaystyle \) \(<\) \(\displaystyle N^3 + K N^{\frac {15} 8}\) because $p_n < N^3$
\(\displaystyle \) \(<\) \(\displaystyle N^3 + N^2\) because $N > K^8$
\(\displaystyle \) \(<\) \(\displaystyle N^3 + 3N^2 + 3N\)
\(\displaystyle \) \(=\) \(\displaystyle \left({N + 1}\right)^3 - 1\)

Therefore:

$N^3 < p_{n+1} < \left({N + 1}\right)^3 - 1$

$\Box$


Let $P_0 > K^8$ be a prime number.

By Lemma 1, there exists an infinite sequence of primes:

$P_0, P_1, P_2, \ldots$

such that:

$\forall n \in \N_{>0}: {P_n}^3 < P_{n+1} < \left({P_n + 1}\right)^3 - 1$

Then we define two functions $u, v: \N \to \Bbb P$:

$\forall n \in \N: u \left({n}\right) = {P_n}^{3^{-n} }$
$\forall n \in \N: v \left({n}\right) = \left({P_n + 1}\right)^{3^{-n} }$


It is trivial that $v \left({n}\right) > u \left({n}\right)$.


Lemma 2

$\forall n \in \N_{>0}: u \left({n + 1}\right) > u \left({n}\right)$


Proof

\(\displaystyle u \left({n + 1}\right)\) \(=\) \(\displaystyle {P_{n+1} }^{3^{-\left({n+1}\right)} }\)
\(\displaystyle \) \(>\) \(\displaystyle \left({P_n^3}\right)^{3^{-n-1} }\) because $P_{n+1} > {P_n}^3$
\(\displaystyle \) \(=\) \(\displaystyle {P_n}^{3 \times 3^{-n-1} }\)
\(\displaystyle \) \(=\) \(\displaystyle {P_n}^{3^{-n} }\)
\(\displaystyle \) \(=\) \(\displaystyle u \left({n}\right)\)

$\Box$


Lemma 3

$\forall n \in \N_{>0}: v \left({n + 1}\right) < v \left({n}\right)$


Proof

\(\displaystyle v \left({n + 1}\right)\) \(=\) \(\displaystyle \left({P_{n+1} + 1}\right)^{3^{-\left({n+1}\right)} }\)
\(\displaystyle \) \(<\) \(\displaystyle \left({\left({\left({P_n + 1}\right)^3 - 1}\right) + 1}\right)^{3^{-n-1} }\) because $P_{n+1} < \left({P_n + 1}\right)^3 - 1$
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({P_n + 1}\right)^3}\right)^{3^{-n-1} }\)
\(\displaystyle \) \(=\) \(\displaystyle \left({P_n + 1}\right)^ {3^{-n} }\)
\(\displaystyle \) \(=\) \(\displaystyle v \left({n}\right)\)

$\Box$


It follows trivially that $u \left({n}\right)$ is bounded and strictly monotone.

Therefore, there exists a number $A$ which is defined as:

$A := \lim_{n \mathop \to \infty} u \left({n}\right)$

From Lemma 2 and Lemma 3, we have:

$u \left({n}\right) < A < v \left({n}\right)$
\(\displaystyle u \left({n}\right)\) \(<\) \(\displaystyle A\) \(\displaystyle <\) \(\displaystyle \left({n}\right)\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle {P_n}^{3^{-n} }\) \(<\) \(\displaystyle A\) \(\displaystyle <\) \(\displaystyle \left({P_n + 1}\right)^{3^{-n} }\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle P_n\) \(<\) \(\displaystyle A^{3^n}\) \(\displaystyle <\) \(\displaystyle P_n + 1\)

The result follows.

$\blacksquare$


Source of Name

This entry was named for William H. Mills.


Sources