0
$\begingroup$

Let us consider the strong twin conjecture:

For all positive integer $n$ there exist a prime $p$ such that $$n+4<p<2^n2^4$$ and $p$ is a prime and $p+2$ is a prime

Since the inequalities and the set of primes are both Diophantine, we can construct a polynomial $P(X)$ such that the strong twin conjecture is equivalent to the following statement:

For all positive integer $n$ there exist a prime $p$ such that $P(X)=0$ where $X$ is a vector of several variables.

Now, in a book by Matiyasevich's: https://mitpress.mit.edu/books/hilberts-10th-problem

The author claim that the strong twin conjecture can be transformed into the unsolvability of a particular Diophantine equation.

Then my question is: How one can find this Diophantine equation or I am asking about a reference containing this equation.

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ I think the book itself explains how to transform any algorithm with bounded running time into a Diophantine equation which is solvable if and only if that algorithm accepts for some integer $n$. Then take the algorithm which searches the numbers between $n+4$ and $2^n 2^4$ for a twin prime, and accepts if none is found. $\endgroup$
    – Will Sawin
    Commented Nov 15, 2021 at 13:49
  • 3
    $\begingroup$ I strongly doubt anyone has bothered to write down the equation you are after, but the procedure for generating the equation from the algorithm is, in principle, completely effective. $\endgroup$
    – Wojowu
    Commented Nov 15, 2021 at 14:00
  • 1
    $\begingroup$ This should be pretty straightforward. There's an explicit Diophantine equation with 26 variables for when a number is prime and getting one for powers of 2 comes pretty easily from the material in the book, and should have 4 variables. You can combine Diophantine equations using the squaring trick. This should give you a Diophantine equation with 26 + 26 + 2+4 = 58 variables. $\endgroup$
    – JoshuaZ
    Commented Nov 15, 2021 at 15:04
  • $\begingroup$ @Wojowu: Can you explain to me in few words how one can find that equation. $\endgroup$
    – Safwane
    Commented Nov 15, 2021 at 15:13
  • 5
    $\begingroup$ No, I can't. A complete explanation is the length of a book, and indeed the book you mention contains such an explanation. $\endgroup$
    – Wojowu
    Commented Nov 15, 2021 at 15:29

0

Reset to default

You must log in to answer this question.