Here are two ways to define Hilbert's tenth problem over a ring $R$:

  1. Given a polynomial $p \in \mathbb Z[x_1,\ldots,x_n]$, can one decide whether it has a solution in $R^n$?
  2. Given a polynomial $p \in R[x_1,\ldots,x_n]$, can one decide whether it has a solution in $R^n$?

I am interested in the case where $R$ is the ring of integers of a number field. In Bjorn Poonen's survey, he explains in §10 that he's talking about (1) but all the papers he cites in Theorem 14.1, including his own, discuss (2) and as far as I can tell don't mention (1). So that would seem to imply that (1) and (2) are equivalent in this situation, but I can't find this stated anywhere.

The question: Is it true that (1) and (2) are equivalent when $R$ is the ring of integers of a number field? Is there a reference for this?

Addendum: A sufficient criterion for Hilbert's tenth problem to be undecidable over $R$ is that $\mathbb Z$ is Diophantine over $R$. That is, there is a polynomial $P(x,y_1,\ldots,y_n)$ such that for $x \in R$, \begin{equation} \tag{$*$}\label{thing} \exists y_1,\ldots,y_n \in R\text{ such that }P(x,y_1,\ldots,y_n)=0 \quad \iff \quad x \in \mathbb Z. \end{equation} In fact, every proof of the undecidability of Hilbert's 10th problem over a number ring $R$ uses this idea. So:

Effectively equivalent question: Given a polynomial $P \in R[x,y_1,\ldots,y_n]$ satisfying \eqref{thing}, where $R$ is the ring of integers of a number field, is it always possible to find a polynomial $P \in \mathbb Z[x,y_1,\ldots,y_n]$ (maybe for a different $n$) satisfying \eqref{thing}?

  • 2
    $\begingroup$ If the number field is of finite degree, then the answer is: 1 and 2 are equivalent. Just represent all coefficients and variables as linear combinations of the basis. $\endgroup$
    – markvs
    Commented Mar 17, 2022 at 3:14
  • 1
    $\begingroup$ Hmm, would you be willing to expand this into an answer? I see how to turn a polynomial equation over $R$ into a system of polynomial equations over $\mathbb Z$, but if the variables are interpreted in $R$ then the system may have other solutions that don't obviously correspond back to a solution to the original equation. But maybe I'm just being obtuse. $\endgroup$
    – Fedya
    Commented Mar 17, 2022 at 4:55
  • $\begingroup$ A system of polynomial equations over $\Bbb Z$ is equivalent to one equation. If $z$ is a variable of the original equation, $\alpha,\beta$ is a (integral) basis and you substitute $z=x\alpha+y\beta$, and you find $x,y$, then you find $z=x\alpha+y\beta$. $\endgroup$
    – markvs
    Commented Mar 17, 2022 at 8:57
  • 2
    $\begingroup$ Fix $\xi\in R=O_K$ such that $K=\mathbb Q(\xi)$. Then given a system of polynomials $p\in R[x_1,\dots,x_n]$, introduce a new variable $z$ for $\xi$, write each $p$ as a polynomial in $\mathbb Q[x_1,\dots,x_n,z]$, add to the system the minimal polynomial $f_\xi\in\mathbb Q[z]$ of $\xi$, and multiply each equation by a sufficiently large integer to make it an integer equation. This is solvable over $R$ iff the original system is, as for any $\xi'\in R$ such that $f_\xi(\xi')=0$, there is an automorphism $\sigma$ of $R$ such that $\sigma(\xi')=\xi$. $\endgroup$ Commented Mar 17, 2022 at 10:36
  • 2
    $\begingroup$ I see that you defined the problem only for systems consisting of one equation, but this makes no difference. If $K$ is formally real, you can just take the sum of squares of all the polynomials; in general, there will be a polynomial $f\in\mathbb Z[x,y]$ such that $f(x,y)=0\iff x=y=0$ for any $x,y\in K$, and this can be used to combine multiple equations into one. $\endgroup$ Commented Mar 17, 2022 at 10:45


Your Answer

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