Finding lattice with short basis-vectors containing given lattice

Question

While working on understanding the space spanned by certain integer relations of real numbers I have come across the following problem. Given $v_1,\dots, v_n \in \mathbb{Z}^m$, I am would like to find $w_1, \ldots w_n \in \mathbb{Z}^m$ such that

1. $\mathbb{Z}v_1+\dots +\mathbb{Z}v_n \ \subseteq \mathbb{Z}w_1 + \dots + \mathbb{Z}w_n$
2. $|w_i|^2$ is small/ small as possible/ a lot smaller that $|v_j|^2$
3. The vector spaces spanned by $\{v_i\}$ and $\{w_i\}$ are identical.

In other words I want that if each $v_i$ satisfies that $v_{i,1}\alpha_i + \dots + v_{i,m}\alpha_m=0$ for a fixed collection of $\alpha_i \in \mathbb{R}$ the same remains true for the $w_i$ (this is of course the real condition I want).

If I wanted the lattices spanned by $v_i$ and $w_i$ to be identical LLL would clearly be the natural approach, but since I am not require this, this seems to not make my $v_i$ nearly as small as I can achieve under these weaker conditions. Does there exists an algorithm, approach, idea which could come up with a such a basis $v_i$ given the $w_i$.

EDIT : I missed the last condition and had some trouble updating correctly. Hope it makes sense and is not completely trivial now.

Answer 1

I think you are asking for a short basis of the direct summand of $\mathbb{Z}^n$ spanned by $v_1,\ldots,v_n$ (The submodule spanned by them need not be a direct summand; so you consider the direct summand W spanned by them. It can be defined as the preimage of the torsion subgroup of $\mathbb{Z}^n/\langle v_1,\ldots,v_n\rangle$).

So the first question arising might be: How large can the smallest (nonzero) vector of $W$ at most be?

A bound can be obtained from Minkowski's theorem. This gives that there has to be a vector $w\in W$ of length $\le 2 (vol(W))^{\frac{1}{rk(W)}}$. The volume of W can be defined as the square root of the determinant of the matrix $(\langle w_i,w_j\rangle)_{i,j}$, where $w_1\ldots,w_{rk(W)}$ is any $\mathbb{Z}$-basis of $W$. Unfortunately the proof of Minkowski's theorem is not constructive and does not yield an algorithm to find a shortest vector. A quick google search let me to the wikipedia page Lattice problem saying that finding a shortest vector in a lattice is NP-hard and giving some names of approximation algorithms.

As far as I know the bound given in Minkowski's theorem is not optimal and can be improved, though this is a hard task.

I see that this still does not answer your question, but it was too long for a comment, so I put it as an answer.