{"id":"arxiv/2605.07784","url":"https://arxiv.org/abs/2605.07784","tags":["cs.DS","cs.CC","cs.SC","math.RA"],"score":0,"title":"Computing bases in Hermite normal form of lattices of integer relations","domain":"cs.DS","source":"arxiv","authors":["George Labahn","Arne Storjohann"],"reviews":0,"subject":"cs.DS","summary":"Given a full column rank $M \\in \\Z^{\\ell \\times m}$ and an $F \\in \\Z^{n \\times m}$ we present an algorithm to compute the $n \\times n$ basis in Hermite form of the integer lattice comprised of all rows $p \\in \\Z^{1 \\times n}$ such that $pF \\in \\Z^{1 \\times m}$ is in the integer lattice generated by the rows of $M$. The algorithm is randomized of the Las Vegas type, that is, it can fail with probability at most $1/2$, but if fail is not returned it guarantees to produce the correct result. When $M$ is square and $F=I_m$, then the computed basis is the Hermite normal form of $M$, and the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-08","reactions":{}}