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$
13
  • $\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$ Mar 28, 2014 at 8:52
  • $\begingroup$ @GeoffRobinson: that is the question, is there a formal proof that it is undecidable? $\endgroup$ Mar 28, 2014 at 8:53
  • 1
    $\begingroup$ Are the primes consecutive or not? (The wording suggests nonconsecutive.) $\endgroup$ Mar 28, 2014 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$ Mar 28, 2014 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$ Mar 28, 2014 at 10:53

1 Answer 1

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$
1
  • $\begingroup$ Minor correction: $\zeta(s)$ also has some trivial zeros. $\endgroup$
    – user25199
    Mar 28, 2014 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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