# A Diophantine Decision Problem

Let $S$ be a subset of $\mathbb{R}^n$ defined by a system $\theta$ of polynomial inequalities with integer coefficients.

Let's say that $\theta$ has no integer solutions "for trivial reasons" if there is a polynomial $h$ with integer coefficients such that for all $p\in S$, it holds that $0 <h(p) < 1$.

Question: Is it effectively decidable whether a given system $\theta$ has no integer solutions "for trivial reasons"?

• Is there anyway to show that $\neg$( a given system $\theta$ has no integer solution " for trivial reason") except for pointing out a solution? – abcdxyz Apr 12 '10 at 16:53
• This system does not like the "<" sign in math. Surround such formulae by backticks, see hints in the tab on the right – Sergei Ivanov Apr 12 '10 at 16:53
• @anon: I fixed your formula, please do not remove backticks. – Sergei Ivanov Apr 12 '10 at 16:58

Try putting spaces between the relation symbols, otherwise it will look like a malformed HTML tag. As in 0 < h(p) < 1 .

Oh, and I think it is not possible if h has integral coefficients and p also has integer parts.

EDIT: Upon rereading the problem, I see where it is possible that h could exist, however, by scaling, I think it could turn into an undecidable variant of Hilbert's 10th: deciding if 0 < h(p) < 1 may be the same as deciding if 2h(p) has a solution. END EDIT

Gerhard "Ask Me About System Design" Paseman, 2010.04.12