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?



A Decision Problem Concerning Diophantine Inequalities
It is undecidable. If you could solve this, you could also solve [Hilbert's 10th problem](http://en.wikipedia.org/wiki/Hilbert%2527s_tenth_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.


