# The diophantine problem for $R[T]$ is solvable iff the diophantine problem for $R$ is solvable

One part of the paper that I am reading is the following:

Let $R$ be a commutative ring with unity and let $R'$ be a subring of $R$.

We say that the diophantine problem for $R$ with coefficients in $R'$ is unsolvable (solvable) if there exists no (an) algorithm to decide whether or not a polynomial equation (in several variables) with coefficients in $R'$ has a solution in $R$.

$$\dots \dots \dots \dots \dots$$

Theorem.

Let $R$ be an integral domain of characteristic zero; then the diophantine problem for $R[T]$ with coefficients in $\mathbb{Z}[T]$ is unsolvable.

($R[T]$ denotes the ring of polynomials over $R$, in one variable $T$.)

$$\dots \dots \dots \dots \dots$$

It is obvious that the diophantine problem for $R[T]$ with coefficients in $\mathbb{Z}$ is solvable if and only if the diophantine problem for $R$ with coefficients in $\mathbb{Z}$ is solvable.



Could you explain to me the last sentence?

Why does this stand?

Does the direction $\Leftarrow$ stand because of the following?

We know that there is an algorithm that decides whether or not an equation with coefficients in $\mathbb{Z}$ has a solution in $R$.

We consider this equation as the constant term of a polynomial equation, so there is an algorithm that decides whether or not an equation with coefficients in $\mathbb{Z}$ has a solution in $R[T]$.

Is the justification of this direction correct?

• And why should there be one variable? Can lead as an example, at least one algorithm? Aug 9, 2015 at 16:39
• It is from the paper: ams.org/journals/tran/1978-242-00/S0002-9947-1978-0491583-7/… at the second page (392). @individ Aug 9, 2015 at 16:42
• So they prove theorems. These fantasies to the solution of Diophantine equations and for finding the desired polynomial generally has no relation. In practice we often need to solve the inverse problem. The solvability of the equation depends not only on the coefficients and the unknown number and its type. That is how they are connected to each other and what relationship. For a particular equation is a formula of the solution not affected by any factors. Aug 9, 2015 at 16:59

The polynomial equation $$P(x_1,\dots,x_n)=0,\tag{1}$$ where $P$ has integer coefficients, has a solution in $R[T]$ if and only if it has a solution in $R$.

For one direction, note that any solution of (1) in $R$ is in particular a solution in $R[T]$.

For the other direction, suppose that the ordered $n$-tuple $(Q_1(T), \dots, Q_n(T))$ of polynomials is a solution of (1) in $R[T]$. Then the ordered $n$-tuple $(Q_1(0),\dots,Q_n(0))$ is a solution of (1) in $R$.

Thus any algorithm for determining solvability in one of the rings $R$ or $R[T]$ automatically determines solvability in the other.

• At the part when we suppose that the ordered $n$-tuple $(Q_1(T), \dots, Q_n(T))$ of polynomials is a solution of (1) in $R[T]$ and we say that the ordered $n$-tuple $(Q_1(0),\dots,Q_n(0))$ is a solution of (1) in $R$, could we have taken any ordered $n$-tuple $(Q_1(x),\dots,Q_n(x))$ where $x\in R$ instead of $(Q_1(0),\dots,Q_n(0))$ ? Or is there a specific reason to take $T=0$ ? Aug 9, 2015 at 17:16
• I chose $0$ for simplicity. For our purposes we can use any $x\in R$ to evaluate at. Aug 9, 2015 at 17:27
• I see... Thanks for the explanation!! :-)  I have also an other question... In the paper that I am reading there appears often the term "elementary theory". Is this the same as "existential theory" ? Aug 9, 2015 at 17:33
• Not the same at all, unless language is being used in a weird way. The elementary theory of groups, the elementary theory of fields, the elementary theory of real-closed fields, the elementary theory of algebraically closed fields of characteristic $0$, and so on have well-established technical meanings that have no connection with existential theory. Aug 9, 2015 at 17:46
• The existential theory of the ring $R$ in $L$ is decidable if there is an algorithm which, given any existential sentence (a sentence that is of the form: existential quantifiers in front, no logical connecties other than $\land$, $\lor$, negation and implication inside) of $L$, decides whether or not that is true or false in $R$, right? What does it mean that the elementary theory is decidable or undecidable? Aug 9, 2015 at 17:56