# Upper Bound on the shortest non-zero non-negative vector in an integer lattice

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}$$

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$$.
• But the lattice $L$ is a sublattice of $\Bbb{Z}^n$ so you cannot divide by large $M$ Commented Nov 17, 2022 at 8:39