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 \ \text{is small/ small as possible/ a lot smaller that $|v_j|^2$}$$

$$ 3.) \ \ \ \ \ \ \text{The vectorspaces 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.

  • 4
    $\begingroup$ Is there a further condition that would prevent you from just letting $w_i$ be the $i$-th unit vector? $\endgroup$ Jan 16 '12 at 21:16
  • $\begingroup$ what do you expect the volume of the fundamental domain of this lattice to be, compared to 1? If it's large then as Henrik pointed out the problem seems quite hard, but if it's small then there are only a small number of lattices it could be, and you could check those. $\endgroup$
    – Will Sawin
    Jan 17 '12 at 3:57

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.