3
$\begingroup$

Is the following problem undecidable?

Given a sequence of $n$ gaps $d_1,d_2,...,d_n$, does there exist a sequence of $n+1$ primes $p_1,p_2,...,p_{n+1}$ such that $p_{i+1} - p_i = d_i$ ?

If not, is the problem still undecidable if we pick a fixed $n$, e.g. only one gap (n=1), or only two gaps (n=2).

With undecidable I mean that you cannot build a Turing machine that given the sequence $d_1,...,d_n$ as input always halts and gives the correct answer.

$\endgroup$
  • $\begingroup$ Suppose that there are no primes $p_{1},p_{2}$ with $p_{2}-p_{1} = d_{1}.$ How would your Turing machine know this? $\endgroup$ – Geoff Robinson Mar 28 '14 at 8:52
  • $\begingroup$ @GeoffRobinson: that is the question, is there a formal proof that it is undecidable? $\endgroup$ – Marzio De Biasi Mar 28 '14 at 8:53
  • 1
    $\begingroup$ Are the primes consecutive or not? (The wording suggests nonconsecutive.) $\endgroup$ – The Masked Avenger Mar 28 '14 at 9:12
  • 2
    $\begingroup$ The prime k-tuples conjecture implies that the question is decidable. Current technology can only decide if a gap sequence is admissible, and can only say yes it is realized in finite time. $\endgroup$ – The Masked Avenger Mar 28 '14 at 9:26
  • 6
    $\begingroup$ Harvey Friedman has suggested that the 1-gap case may be an example of a c.e. problem that is not decidable and also not equivalent to the halting problem. If this were true, it would be an instance of the long-sought natural examples of intermediate Turing degrees between $0$ and $0'$. $\endgroup$ – Joel David Hamkins Mar 28 '14 at 10:53
6
$\begingroup$

This is probably unknown. The problem is that we know very little about the distribution of prime numbers. In general, decidability questions only become interesting when we "have a good grasp" about the object we are manipulating. It is easy to generate decidability questions which are only hard because of our limited knowledge. Here are a few examples:

  • Given two rationals $a<b$, can one decide whether there a zero of Reimann's zeta function whose real part belongs to $(a,b)$?
  • Given a finite sequence of digits $w$, can one decide whether $w$ appears in the decimal expansion of $\pi$?
  • Given an integer $n$, can one decide whether the Collatz sequence starting at $n$ eventually reaches $1$?

In all three cases, the answer is assumed to be positive for a trivial reason (in the first case, by simply checking whether $a<1/2<b$ or whether $a<-2n<b$ for some nonnegative integer $n$, in the second and third case by answering `yes' all the time) but proving this does not appear to be simpler than the general conjecture. I feel like your problem somewhat falls into this category.

$\endgroup$
  • $\begingroup$ Minor correction: $\zeta(s)$ also has some trivial zeros. $\endgroup$ – user25199 Mar 28 '14 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.