Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


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.

share|cite|improve this question
The best reference for this is Matiyasevich's book Hilbert's 10th problem. It is fairly accessible, provides complete details, and assumes no prior knowledge from computability theory or logic in general. – Andrés E. Caicedo May 15 '14 at 2:52
up vote 4 down vote accepted

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)$.

share|cite|improve this answer
When you write $P_S(y,x_1,x_2,...,x_k)=0$, what is the role of $y$ in the polynomial? – Bobby Lee May 15 '14 at 0:40
In one sense $y$ is a variable just like the others. But $S$ is the set of values of the parameter $y$ for which the Diophantine equation has a solution $x_1,\dots,x_n$. – André Nicolas May 15 '14 at 0:45
Oh so $y$ is the fixed exponent for each variable $(x_1,x_2,...,x_k)$ in the polynomial $P_S(y,x_1,x_2,...x_k)$? I guess I am asking: what would the polynomial look like with $y=2$ and with variables $(x_1,x_2,...x_k)$? And why is it significant that this all equals $0$? – Bobby Lee May 15 '14 at 1:13
It is not an exponent, it is a parameter, just like in the Pell equation $x^2-dy^2=1$, $d$ is a parameter. For most significant $S$, the associated polynomial $P_S$ is extremely complicated. Some r.e. predicates have a simple representation. for example, the set of perfect squares is the set of all $y$ such that $\exists x(y-x^2=0)$. Equal to $0$ is not important. But every Diophantine equation can be written as $Q(z_1,\dots,z_n)=0$. – André Nicolas May 15 '14 at 1:23

For a bit more, you might find some interest in this handout I did for a student reading group:

share|cite|improve this answer
Very helpful thanks! – Bobby Lee May 15 '14 at 16:58

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.



$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.




Then the formula in the general form is:


$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$


And more.




$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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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