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+\mathbb{Z}^n$ be all points of the form $s+z$ with $s \in S$ and $z \in \mathbb{Z}^n$. Is there a method known for determining, given $\theta$, whether $S+\mathbb{Z}^n=\mathbb{R}^n$? Is this problem known to be effectively undecidable?

share|improve this question

2 Answers 2

up vote 9 down vote accepted

It is undecidable. If you could solve this, you could also solve Hilbert's 10th problem.

Suppose we have an algorithm solving your problem for all $n$. Given a polynomial $p\in\mathbb[x_1,\dots,x_n]$, let's decide whether it has integer solutions. If $p$ is constant, this is trivial. Otherwise we can find $z_0\in\mathbb Z^n$ such that $|p(x)|>1$ for all $x\in z_0+[0,1]^n$. Let's work with a polynomial $f(x)=p(x+z_0)$ rather than $p$. It satisfies $|f(x)|>1$ for all $x\in[0,1]^n$.

Let $g(x)=x_1(x_1-1)x_2(x_2-1)\dots x_n(x_n-1)$. Apply our algorithm to the inequality $$ r(x):=(f(x)^2-1)\cdot g(x)<0 . $$ If it says that $S+\mathbb Z^n=\mathbb R^n$, then we know that $S$ contains a point from $\mathbb Z^n$, and this point must a root of $f$. If it says that $S+\mathbb Z^n\ne\mathbb R^n$, then we know that there is $c\in\mathbb R^n$ such that $r(c+z)\ge 0$ for all $z\in\mathbb Z^n$.

This $c$ must belong to $\mathbb Z^n$. Indeed, suppose that e.g. $c_1\notin\mathbb Z$. We may assume that all coordinates of $c$ are positive and $0<c_1<1$. Substitute $z=(0,z_2,\dots,z_n)$ where $z_2,\dots,z_n$ are arbitrary positive integers and conclude that $|f(c+z)|\le1$ for all such $z$. It follows that $f$ is constant on the hyperplane $\{x_1=c_1\}$, and the modulus of this constant no greater than 1. This contradicts the fact that $|f|>1$ on $[0,1]^n$.

Thus we know that $c\in\mathbb Z^n$, or, equivalently, that $r(z)\ge 0$ for all $z\in\mathbb Z^n$. This means that $f$ does not have integer roots except possibly at points where one of the coordinates is 0 or 1. Thus we reduced the problem to the case of $n-1$ variables and can solve it by induction.

share|improve this answer

I find this proof (of Sergei Ivanov) quite interesting. Was it cooked up from scratch just to answer the question, or do similar ideas appear in some other context? Any references would be appreciated.

share|improve this answer
    
In my personal opinion, this should have been posted either as a comment to Sergei Ivanov's post, or as a separate question. But perhaps the interface doesn't allow people with "low reputation" to do this? –  Yemon Choi Apr 8 '10 at 5:45
    
I didn't see any comment link on Sergei's answer! –  nivram Apr 8 '10 at 5:56
    
Maybe if you post your question as a separate post, i.e. as a question of your own, you might get responses more quickly. (Personally, your question sounds interesting, but I don't know any helpful answer.) –  Yemon Choi Apr 8 '10 at 8:53

Your Answer

 
discard

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.