lo.logic - A Decision Problem Concerning Diophantine Inequalities

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 $pinmathbb[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_0inmathbb Z^n$ such that $|p(x)|>1$ for all $xin 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 $xin[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^nnemathbb R^n$, then we know that there is $cinmathbb R^n$ such that $r(c+z)ge 0$ for all $zinmathbb Z^n$.

This $c$ must belong to $mathbb Z^n$. Indeed, suppose that e.g. $c_1notinmathbb 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 $cinmathbb Z^n$, or, equivalently, that $r(z)ge 0$ for all $zinmathbb 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.

• Next big list - What are the worst notations, in your opinion ?
• Previous gr.group theory - Hausdorff dimension of products of normal subgroups