Fix a discrete addition subgroup in $\mathbb{R}^n$. Given a finite spanning set, how can one find a group basis?
$\begingroup$
$\endgroup$
10
-
1$\begingroup$ 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. $\endgroup$– Martin SeysenCommented May 13, 2019 at 21:46
-
1$\begingroup$ 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$. $\endgroup$– Josiah ParkCommented May 14, 2019 at 2:36
-
1$\begingroup$ 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. $\endgroup$– Josiah ParkCommented May 14, 2019 at 3:19
-
1$\begingroup$ See also en.wikipedia.org/wiki/Integer_relation_algorithm. $\endgroup$– Josiah ParkCommented May 14, 2019 at 3:39
-
1$\begingroup$ See also en.wikipedia.org/wiki/Hermite_normal_form $\endgroup$– Wilberd van der KallenCommented Jul 9, 2019 at 7:43
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
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.