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.



shortest lattice point solution to a linear system
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(2n-1-m)$-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$.


