5
$\begingroup$

There are infinitely many prime numbers. Euclides gave a constructive proof as follows.

For any set of prime numbers $\{p_1,\ldots,p_n\}$, the prime factors of $p_1\cdot \ldots \cdot p_n +1$ do not belong to the set $\{p_1,\ldots,p_n\}$.

I'm wondering if the following can be made into a constructive proof too.

Let $p_1 = 2$. Then, for $n\geq 2$, define $p_n$ to be a prime number in the interval $(p_{n-1},p_{n-1} + \delta_n]$, where $\delta_n$ is a real number depending only on $n$. Is such a $\delta_n$ known?

Note that this would be a constructive proof once we find a $\delta_n$ because finding a prime number in $(p_{n-1},p_{n-1}+\delta]$ can be done in finite time algorithmically.

For some reason I believe such a $\delta_n$ is not known. In this spirit, is it known that we can't take $\delta_n = 10n$ for example?

  • 0
    @Fredrik, Bill's answer to the other question says nothing about the question here, which is about $\delta_n$.2012-06-17

1 Answers 1

5

As noted in the comments, we can take $\delta_n=p_{n-1}$. In fact, there are improvements on that in the literature. But if you want something really easy to prove, you can take $\delta_n$ to be the factorial of $p_{n-1}$, since that gives you an interval which includes Euclid's $p_1\times p_2\times\cdots\times p_{n-1}+1$ and therefore includes a new prime.