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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
-
$\begingroup$ Thanks! How about a upper bound of form $c(n)\max\{\|y\|,1\}$? $\endgroup$ Commented Sep 13, 2016 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$– js21Commented Sep 14, 2016 at 6:58