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"?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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