A Decision Problem Concerning Diophantine Inequalities 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: 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.
A: 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. 
