A decision problem concerning Diophantine inequalities

Question

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?

Answer 1

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.