Given is an integer vector $v$ in $Z^n$. I'm looking for the radius under the $L1$ norm of the smallest ball that can contain a spanning set of integer vectors $u_i$ such that $u_i.v=0$ for $i=1...n$.

In other words: we are looking at integer vectors in a plane orthogonal to $v$. Let us assume that we can enumerate these integer vectors in increasing "length", where the "length" of v is defined as $|v|=\sum_i^n |v_i|$. The first of these vectors to make our set a spanning set of $Z^{n-1}$ has the length I am looking for.

I have tried to use two different formulations to make my problem clear, I hope they are equivalent.

I know that finding the shortest vector in a lattice is a hard problem, however in this case I am only looking for the length of a vector, which is not even the shortest one, and not the vector itself. Does this simplify the problem in any way? Ideally I would like this radius just in terms of $v$. (Probably too much to ask?)


1 Answer 1


This is still the shortest vector problem. The point is that the set of vectors orthogonal to your fixed $v$ make a lattice of rank $n-1.$ You can construct a basis for that lattice one way or another. then you want a shortest vector.

As always, my advice is to make some sample problems in low dimension and solve them completely, see what happens.

Let me add one item. Suppose we are back in Z^3 and have a basis of integer vectors, u,v,w. We get a quadratic form as the squared Euclidean length of $x \vec{u} + y \vec{v} + z \vec{w},$ which will be an integer. Half The Hessian matrix of this form is called the Gram matrix. I answered a question yesterday on lattices, we never got this far...

Example of difficult base for the lattice problems

This one looks good. Look to the right of the screen under "Related"

Finding a basis for the integer lattice points in a subspace


You must log in to answer this question.

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