Diophantine equations and Hilbert's 10th Problem, how did MRDP do it?

Question

I'm having a bit of trouble understanding the Wiki explanation of MRDP's (Matiyasevich, Robinson, Davis, Putnam)'s Theorem, which explains that Hilbert's 10th problem is unsolvable.

The MRDP theorem states that a set of integers is Diophantine if and only if it is computably enumerable. A set of integers $S$ is recursively enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of $S$ and runs forever otherwise.

Source: http://en.wikipedia.org/wiki/Diophantine_set

What exactly is the set $S$ in the case of Hilbert's 10th Problem? Is it the set of solutions $n$ for any ${x_1}^n+{x_2}^n+...+{x_{k-1}}^n={x_k}^n$ Diophantine equation?

Also are we assuming that the $x_1,...,x_k$, are unchanging? That is, we choose this list of constants $(x_1,x_2,...,x_k)$, and we look for all the $n$ that make the equation true?

MOST confusing to me: why does it matter if this set is c.e.?

Sorry for so many questions, I've been sifting through Wiki pages and haven't been able to find a clear explanation for this.

Answer 1

Matiyasevich showed that for any recursively enumerable set $S$ of natural numbers, there is a polynomial $P_S(y,x_1,x_2,\cdots,x_k)$ with integer coefficients such that for any non-negative integer $y$, we have $$y\in S \quad\text{if and only if}\quad \exists x_1 \exists x_2\cdots\exists x_k\left(P_S(y,x_1,x_2,\dots, x_k)=0\right) .\tag{1}$$ Here the variables $x_i$ range over the non-negative integers, but one can let them range over the integers.

The polynomial $P_S$ depends on $S$. However, one can show that there is a polynomial $P(e,y,x_1,\dots,x_k)$ such that for any recursively enumerable subset $S$ of the natural numbers, there is a natural number $e_S$ such that $$y\in S \quad\text{if and only if}\quad \exists x_1 \exists x_2\cdots\exists x_k\left(P(e_S, y,x_1,x_2,\dots, x_k)=0\right) .\tag{2}$$

Let $y\in S$. Typically, the $(x_1,x_2,\dots,x_k)$ (there may be many) such that $P_S(y,x_1,\dots,x_k)=0$ will depend on $y$. And there are infinitely many $P_S$ that do the job of "representing" $S$ in the sense of Formula (1).

The condition that $S$ be recursively e numerable is necessary. This is because for any polynomial $P(y,x_1,x_2,\dots,x_k)$ with integer coefficients, the set $$\{y: \exists x_1\cdots \exists x_k(P(y,x_1,\dots,x_k)=0)\}$$ is recursively enumerable.

Remarks: $1.$ Technically, the example $x_1^n+\cdots+x_{k-1}^n=x_k^n$ is not a Diophantine equation in the sense of the theorem, since a variable occurs as an exponent. It is an exponential Diophantine equation. The fact that every recursively enumerable predicate is exponential Diophantine was known before the work of Matiyasevich.

$2.$ It has been known since the time of Godel that there is a recursively enumerable predicate 9set) $S$ which is not recursive. Let $P_S(y,x_1,\dots,x_k)$ be a polynomial that represents this $S$ in the sense of Formula (1). Then there is no algorithm that will determine, given input $y$, whether the equation $P(y,x_1,\dots, x_k)=0$ has a solution in natural numbers. It follows that there is no algorithm for determining, given a Diophantine equation $Q(z_1,\dots,z_n)=0$, whether the equation has a solution in natural numbers. For if there were such an algorithm, it could be used in particular to determine, given $y$, whether $P_S(y,x_1,\dots,x_k)$ has a solution $(x_1,\dots,x_k)$.

Answer 2

Not to be confused fundamentally insoluble algebraic equations of higher degrees with insolubility in general. It is certainly possible to treat everything the same and stop the equation to solve, but we can try to understand what the equations amenable to solution. For an example, the solution in the general form of a quadratic form.

Formula generally look like this: Do not like these formulas. But this does not mean that we should not draw them. To start this equation zayimemsya, well then, and others. $aX^2+bXY+cY^2=jZ^2$

Solutions can be written if even a single root.$\sqrt{j(a+b+c)}$ , $\sqrt{b^2 + 4a(j-c)}$ , $\sqrt{b^2+4c(j-a)}$

Then the solution can be written.

$X=(2j(b+2c)^2-(b^2+4c(j-a))(j\pm\sqrt{j(a+b+c)}))s^2+2(b+2c)(\sqrt{j(a+b+c)}\mp{j})sp+(j\mp \sqrt{j(a+b+c)})p^2$

$Y=(2j(2j-b-2a)(b+2c)-(b^2+4c(j-a))(j\pm\sqrt{j(a+b+c)}))s^2+ +2((2j-2a-b)\sqrt{j(a+b+c)}\mp{j(b+2c)})sp+(j\mp\sqrt{j(a+b+c)})p^2$

$Z=(2j(b+2c)^2-(b^2+4c(j-a))(a+b+c\pm\sqrt{j(a+b+c)}))s^2+ +2(b+2c) ( \sqrt{j(a+b+c)} \mp{j})sp + ( a + b + c \mp \sqrt{j(a+b+c)})p^2 $

In the case when the root $\sqrt{b^2+4c(j-a)}$ whole.

Solutions have the form.

$X=((2j-b-2c)(8ac+2b(2j-b))-(b^2+4a(j-c))(b+2c\mp\sqrt{b^2+4c(j-a)}))s^2++2(4ac+b(2j-b)\pm{(2j-b-2c)}\sqrt{b^2+4c(j-a)})sp+(b+2c\pm\sqrt{b^2+4c(j-a)})p^2$

$Y=((b+2a)(8ac+2b(2j-b))-(b^2+4a(j-c))(2j-b-2a\mp\sqrt{b^2+4c(j-a)}))s^2++2(4ac+b(2j-b)\pm{(b+2a)}\sqrt{b^2+4c(j-a)})sp+(2j-b-2a\pm\sqrt{b^2+4c(j-a)})p^2$

$Z=((b+2a)(8ac+2b(2j-b))-(b^2+4a(j-c))(b+2c\mp\sqrt{b^2+4c(j-a)}))s^2++2(4ac+b(2j-b)\pm {(b+2a)}\sqrt{b^2+4c(j-a)})sp+(b+2c\pm\sqrt{b^2+4c(j-a)})p^2$

In the case when the root $\sqrt{b^2+4a(j-c)}$ whole.

Solutions have the form.

$X=(2j^2(b+2a)-j(a+b+c)(2j-2c-b\pm\sqrt{b^2+4a(j-c)}))p^2+ +2j(\sqrt{b^2+4a(j-c)}\mp{(b+2a)})ps+(2j-2c-b\mp\sqrt{b^2+4a(j-c)})s^2$

$Y=(2j^2(b+2a)-j(a+b+c)(b+2a\pm\sqrt{b^2+4a(j-c)}))p^2+ +2j(\sqrt{b^2+4a(j-c)}\mp{(b+2a)})ps+(b+2a\mp\sqrt{b^2+4a(j-c)})s^2$

$Z=j(a+b+c)(b+2a\mp\sqrt{b^2+4a(j-c)})p^2+ +2((a+b+c)\sqrt{b^2+4a(j-c)}\mp{j(b+2a)})ps+ (b+2a\mp\sqrt{b^2+4a(j-c)})s^2$

Since these formulas are written in general terms, require a certain specificity calculations.If, after a permutation of the coefficients, no root is not an integer. You need to check whether there is an equivalent quadratic form in which, at least one root of a whole. Is usually sufficient to make the substitution $X\longrightarrow{X+kY}$ or more $Y\longrightarrow{Y+kX}$ In fact, this reduces to determining the existence of solutions in certain Pell's equation. Of course with such an idea can solve more complex equations. If I will not disturb anybody, slowly formula will draw. number $p,s$ integers and set us. I understand that these formulas do not like. And when they draw - or try to ignore or delete.

Formulas but there are no bad or good. They either are or they are not.

In equation $aX^2+bY^2+cZ^2=qXY+dXZ+tYZ$

$a,b,c,q,d,t$ integer coefficients which specify the conditions of the problem.

For a more compact notation, we introduce a replacement.

$k=(q+t)^2-4b(a+c-d)$

$j=(d+t)^2-4c(a+b-q)$

$n=t(2a-t-d-q)+(2b-q)(2c-d)$

Then the formula in the general form is:

$X=(2n(2c-d-t)+j(q+t-2b\pm\sqrt{k}))p^2+2((d+t-2c)\sqrt{k}\mp{n})ps++(2b-q-t\pm\sqrt{k})s^2$

$Y=(2n(2c-d-t)+j(2(a+c-d)-q-t\pm\sqrt{k}))p^2+2((d+t-2c)\sqrt{k}\mp{ n })ps++(q+t+2(d-a-c)\pm\sqrt{k})s^2$

$Z=(j(q+t-2b\pm\sqrt{k})-2n(2(a+b-q)-d-t))p^2+2((2(a+b-q)-d-t)\sqrt{k}\mp{n})ps+(2b-q-t\pm\sqrt{k})s^2$

And more.

$X=(2n(q+t-2b)+k(2c-d-t\pm\sqrt{j}))p^2+2((2b-q-t)\sqrt{j}\mp{n})ps++(d+t-2c\pm\sqrt{j})s^2$

$Y=(2n(2(a+c-d)-q-t)+k(2c-d-t\pm\sqrt{j}))p^2++2((q+t+2(d-a-c))\sqrt{j}\mp{n})ps+(d+t-2c\pm\sqrt{j})s^2$

$Z=(2n(q+t-2b)+k(d+t+2(q-a-b)\pm\sqrt{j}))p^2+2((2b-q-t)\sqrt{j}\mp{n})ps++(2(a+b-q)-d-t\pm\sqrt{j})s^2$

$p,s$ are integers and are given us. Since formulas are written in general terms, in the case where neither the root is not an integer, it is necessary to check whether there is such an equivalent quadratic form in which at least one root of a whole. If not, then the solution in integers of the equation have not.

I noticed that there do not like to write solutions of equations. Billing solutions read bad taste. Although when it, but it should start doing.

There are equations that can be solved, and there are equations that are not amenable to solution. And I think the approach may be different.

Answer 3

For a bit more, you might find some interest in this handout I did for a student reading group: http://www.logicmatters.net/resources/pdfs/MRDP.pdf