Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
Is there anyway to show that $\neg$( a given system $\theta$ has no integer solution " for trivial reason") except for pointing out a solution? –  Tran Chieu Minh 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
add comment

1 Answer 1

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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