# Tenth Hilbert problem on interval arithmetic

What is the decidability status of Hilbert's Tenth problem interpreted over interval arithmetic?

In details, let $$p\in\mathbb{Q}[x_1,\ldots,x_n]$$ be a Diophantine polynomial. The problem is that of deciding whether there exist $$n$$ intervals $$v_1,\ldots,v_n$$ with bounds in $$\mathbb{N}$$ such that $$0\in p(v_1,\ldots,v_n)$$ (where $$p$$ is evaluated using standard interval arithmetic).

Is the problem decidable?

• Can you edit the question to give the definition of $p(v_1,\dots,v_n)$? Is it $\{p(x_1,\dots,x_n) : x_1 \in v_1, \dots, x_n \in v_n\}$? Or is it the result of formally multiplying and adding intervals as specified by $p$, with the natural definition for multiplication and addition of intervals? These two are not the same.
– D.W.
Feb 9 '21 at 18:42
• It's the second one. I'll try to edit the question! Feb 9 '21 at 18:58
• Surely the following simple algorithm works? Evaluate the polynomial in interval arithmetic wrt the order $\{-\infty\}\cup\mathbb Z\cup\{+\infty\}$ with each $v_i$ given the value $[0,+\infty]$. Accept if the result includes $0$. (The semantics of $+\infty$ here is that if the value of some subpolynomial $f$ is $[a,+\infty]$, it means “for every $b>a$, there is an assignment of finite intervals to $v_1,\dots,v_n$ such that the value of $f$ includes $[a,b]$”, and similarly for $-\infty$.) Feb 9 '21 at 21:23
• I'm not sure I understand your proposal. Can you elaborate? Feb 10 '21 at 8:17
• I’m saying that since interval arithmetic is monotone with respect to inclusion, the problem is decidable by fixing each $v_i$ as the largest interval possible, viz. $[0,+\infty]$, and checking whether the resulting interval $p(v_1,\dots,v_n)$ contains $0$. One can easily show (using continuity of interval arithmetic) that if the answer is positive, $p(v_1,\dots,v_n)$ will also contain $0$ when each $v_i$ is set to any sufficiently large finite interval $[0,b]$, hence the result of the algorithm is valid even if you only allow finite intervals for $v_1,\dots,v_n$. Feb 10 '21 at 13:44