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
    Well, you could define $\delta_n$ to be the difference between the $(n-1)$th and the $n$th prime. This can be constructively shown to exist, by virtue of Euclid's argument. So it doesn't really bring you closer to an independent proof, but it still makes it very difficult to maintain the idea that no working $\delta_n$ is even _known_.2012-06-17
  • 0
    This has been answered before: http://math.stackexchange.com/questions/30127/is-there-an-intuitionist-i-e-constructive-proof-of-the-infinitude-of-primes (see especially Bill Dubuque's excellent answer)2012-06-17
  • 3
    By Bertrand's Postulate (which has long been a theorem) there is always a prime between $k$ and $2k$.2012-06-17
  • 1
    However, what if all known proof of Bertrand's Postulate use the fact that there are infinitely many primes...2012-06-17
  • 1
    Even if the proof used Axiom of Choice, and other mysterious things, it would remain the case that the *algorithm* that searches from $p_{n-1}+1$ to $2p_{n-1}$ works.2012-06-17
  • 0
    @GEdgar: they don't. Erdős's proof not only makes no use of that assumption but proves a weak form of the PNT. See http://math.stackexchange.com/questions/50006/different-ways-to-prove-there-are-infinitely-many-primes .2012-06-17
  • 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.