Let $E$, a $\mathbb{Q}$-affine space of arbitrary dimension included in $\mathbb{Q}^n$. Is it possible to check efficiently if $E \cap \mathbb{Z}^n$ is empty or not?


If is an hard problem could give me the reduction to a well-known hard-problem (or a source that attest the fact: it is a well-known hard problem).



Intersection of a $\mathbb{Q}$-affine space with $\mathbb{Z}^n$
If $E$ is given as $\{ v + Aw : w \in \mathbb Q^m \}$ where $v \in \mathbb Q^n$ and $A \in M\_{n, m}(\mathbb Q)$, then if $B$ is a left-inverse for $A$ we have $E \cap \mathbb Z^n \neq \varnothing \iff (1-AB)v \in (1-AB) \mathbb Z^n$. We can find a basis of this $\mathbb Z$-module and check if the coordinates of $(1-AB) v$ in that basis are integers.


For $\iff$: If we can write $(1-AB)v = (1-AB)x$, then $v + AB(x-v) = x \in E \cap \mathbb Z^n$. Conversely, if $v + Aw = x \in \mathbb Z^n$, then $Bv+w = Bx$. Hence $x = v + Aw = v + A(Bx-Bv)$ so that $(1-AB)v = (1-AB)x$.




---


So, first find a left inverse $B$ for $A$ (through Gaussian elimination). Take an integer $N$ such that $N(1-AB)$ has integer entries. Then find the Smith normal form for $N(1-AB)$, and keep track of the transformation matrices. Say $1-AB = P D Q$ with $D$ diagonal and $P, Q \in GL(n, \mathbb Z)$. Now $(1-AB)v \in (1-AB) \mathbb Z^n$ is equivalent to $ P^{-1}(1-AB)v \in D \mathbb Z^n$. Because $D$ is diagonal, this is easy to check.


As remarked by Emil Jeřábek supports Monica in the comments, this is a polynomial time algorithm.


