# Find a lattice basis given too many points

Fix a discrete addition subgroup in $$\mathbb{R}^n$$. Given a finite spanning set, how can one find a group basis?

• 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. Commented May 13, 2019 at 21:46
• There will always exist a basis, so it is not clear what is meant by "it might not even be possible". If this is a reference to the problem where the $b$'s must be among the $v$'s, then sure, it can be impossible. There are examples of lattices which have the property that the minimal vectors generate the lattice, but no basis of minimal vectors exist for $L$. Commented May 14, 2019 at 2:36
• 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. Commented May 14, 2019 at 3:19
• Commented May 14, 2019 at 3:39
• Commented Jul 9, 2019 at 7:43

Fix a $$d$$-dimensional discrete addition subgroup $$L\subset \mathbb{R}^n$$. Call the spanning elements $$v_1,\dots, v_k\in L$$ and the matrix whose columns are these $$v$$'s as $$V\in \mathbb{R}^{n\times k}$$. We seek a group basis $$b_1,\dots,b_d\in L$$.

Two solutions. I have tried the first one since it is readily implementable.

The LLL algorithm is strong enough to perform this reduction.

Affix $$I_{k\times k}$$ to the top of $$V\in \mathbb{R}^{n\times k}$$ forming $$V^\ast \in \mathbb{R}^{(n+k)\times k}$$. Run the LLL algorithm on the columns of $$V^\ast$$ using the seminorm that equals the norm of the bottom $$n$$ components. The nonzero last-$$n$$-components of the LLL-reduced vectors will form a basis for the desired subgroup. The first $$k$$ components give coordinates for this basis in terms of input vectors $$V$$.

(Or also, form $$V^\ast$$ by instead affixing $$\varepsilon \cdot I_{k\times k}$$. For $$\varepsilon$$ small enough, the LLL algorithm with the usual norm does the same thing.)

Johannes Buchmann and Michael Pohst. Computing a lattice basis from a system of generating vectors. In European Conference on Computer Algebra, pages 54–63. Springer, 1987.

Run an exhaustive Simultaneous Integer Relations Algorithm on $$V\in \mathbb{R}^{n\times k}$$, the matrix whose columns are $$v_1,\dots, v_k$$. This algorihtm finds a matrix $$R\in \mathbb{Z}^{k\times r}$$ of all, say, $$r$$ independent integer relations for the input vectors, i.e. $$VR=0\in \mathbb{R}^n.$$ Now run the S. I. R. A. on $$R'$$ to find a matrix $$S\in \mathbb{Z}^{k\times r^\ast}$$. Columns of $$VS$$ form the desired basis.