0
$\begingroup$

Suppose we have an integer lattice of full rank $L\subseteq\Bbb{Z}^n$, say of determinant $D$.

Do we have a nice bound on the smallest non-zero vector $x\in L$ s.t. $x_i\geq0$ for all $i$? Perhaps using the determinant?

From Minkowski's theorem, we know that there is an $x\in L$ s.t. $||x||_\infty \leq D^{1/n}$, but $x$ might not be non-negative.

My best guess would be that there is a constant $c\geq 1$ (that might depend on $n$) s.t. $||x||_\infty \leq cD^{1/n}$, here is an example of a heuristic I cannot make formal:

Let $B=[0,cD^{1/n}]^n$, since $B$'s volume is greater than that of the fundamental parallelogram of $L$ we need at least two of them to cover $B$. Hence there are two fundamental parallelograms of $L$ that intersect inside $B$ and so there must be a non-zero element $x\in L\cap B$ so $||x||_\infty \leq cD^{1/n}$

$\endgroup$

1 Answer 1

1
$\begingroup$

The answer is no, which we can see already for $n=2$. Let $v_1=(1,1)$ and $v_2=(1,-1)$ (so that $v_1 \perp v_2$), and consider the lattice spanned by $Mv_1$ and $v_2$, where $M$ is a large positive integer. This lattice has determinant $2M$, but the shortest vector nonzero vector in the positive quadrant is $Mv_1$ itself which has infinity-norm equal to $M$.

depiction of lattice

$\endgroup$
2
  • $\begingroup$ But the lattice $L$ is a sublattice of $\Bbb{Z}^n$ so you cannot divide by large $M$ $\endgroup$
    – yotam maoz
    Commented Nov 17, 2022 at 8:39
  • $\begingroup$ Thanks for pointing out that I misread the problem. I'll update my answer now. $\endgroup$ Commented Nov 17, 2022 at 17:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .