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}$.

  • $\begingroup$ I think there is some translation to this question, although they also cared about basis size mathoverflow.net/questions/124744/… $\endgroup$ – enthdegree May 13 at 18:12
  • 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 Seysen May 13 at 21:46
  • $\begingroup$ Do you intend the $b$’s to be among the $v$’s, or it doesn’t matter? $\endgroup$ – LSpice May 13 at 22:32
  • 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 Park May 14 at 3:19
  • 1
    $\begingroup$ See also en.wikipedia.org/wiki/Integer_relation_algorithm. $\endgroup$ – Josiah Park May 14 at 3:39

Your Answer

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

Browse other questions tagged or ask your own question.