# Find a lattice basis given too many points

Fix a $$d$$-dimensional discrete addition subgroup $$L\subset \mathbb{R}^n$$. Given $$v_1,\dots, v_k\in L$$ whose integer combinations span $$L$$, how can one find a group basis $$b_1,\dots,b_d\in L$$?

I suppose this problem is equivalent to designing an $$A\in \mathbb{R}^{n\times d}$$ where the following equation has an integer-matrix solution for $$U$$: $$AU=\begin{bmatrix}v_1,\dots, v_k\end{bmatrix}$$.

I think the following restricted version is easier: say $$k=d+1$$ and $$c_1v_1+\dots + c_k v_k = 0$$ for some $$c_1,\dots,c_k\in \mathbb{Z}$$.

• I think there is some translation to this question, although they also cared about basis size mathoverflow.net/questions/124744/… – enthdegree May 13 at 18:12
• I think a solution to this problem is given in link.springer.com/chapter/10.1007%2F3-540-16078-7_69. But I do not have online access to that paper. – Martin Seysen May 13 at 21:46
• Do you intend the $b$’s to be among the $v$’s, or it doesn’t matter? – LSpice May 13 at 22:32
• Yes, this works in the case when the lattice is an integer lattice. Section 14 of Lenstra's tutorial here: math.leidenuniv.nl/~psh/ANTproc/06hwl.pdf also gives an algorithm for this case. In the general case, an algorithm is given (Edit) in: J. Hastad, B. Just, J.C. Lagarias and C.P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, Proceedings STACS 86. This is the paper mentioned above by @MartinSeysen. – Josiah Park May 14 at 3:19
• – Josiah Park May 14 at 3:39