Consider the lattice $\mathbb{Z}^n$ and a real matrix $A\in \mathbb{R}^{m\times n}$ ($m<n$) with orthonormal rows. Let $y\in A\mathbb{Z}^n\setminus\{0\}$ and consider the equation $Ax=y$. Is there a (good) upper bound on the smallest norm of such $x$ in terms of norms of $y$? I am hoping an upper bound of $n^c\y\$ for some $c > 1$ but $c^n\y\$ would be bad.
When $m \geq 1$, there is no universal bound of the form $c(n) y$ for the smallest norm of such an $x$. To see this, let $X$ be the $\frac{1}{2}m(2n1m)$dimensional manifold of real $m \times n$ matrices $A$ with orthonormal rows. Let $Z$ be the subset of matrices which have a rational entry in the first column, or which have a row with entries linearly dependent over $\mathbb{Q}$. Since $Z$ lies in a countable union of hypersurfaces of $X$, it has dense complement in $X$. In particular, there is a sequence $(A_k)_k \subset X \setminus Z$ such that $y_k = A_k e_1 \rightarrow 0$. But for each $k$, the vector $e_1$ is the unique $x \in \mathbb{Z}^n$ such that $A_k x = y_k$.

$\begingroup$ Thanks! How about a upper bound of form $c(n)\max\{\y\,1\}$? $\endgroup$ – user58955 Sep 13 '16 at 15:05

$\begingroup$ Neither. Just replace $y_k$ by $\lfloor  y_k^{1} \rfloor y_k$ and $e_1$ by $\lfloor  y_k^{1} \rfloor e_1$ in my answer. $\endgroup$ – js21 Sep 14 '16 at 6:58