1
$\begingroup$

Suppose I have a basis $B$ of an $n$-dimensional lattice $L\subseteq\mathbb{Z}^n$ and $B$ has $n$ vectors. Now I take another $v\in \mathbb{Z}^n\setminus L$ and I define a new lattice $L'=L+\mathbb{Z}v$. The set of vectors $B':=B\cup\{v\}$ generates $L'$, but since $L'$ is $n$-dimensional, it's rank is at most $n$, so $B'$ is too big. So there must be some other basis that generates $L'$. How do we produce that from $B'$?

I vaguely recall reading that LLL could do this, but I have no idea how. Can anyone point to reference or give a quick argument/proof?

$\endgroup$
4
  • 1
    $\begingroup$ Rather than break out LLL, compute the Hermite normal form of $B'$ and discard zero vectors. $\endgroup$
    – Daniel S
    Jan 28, 2022 at 16:02
  • $\begingroup$ Thanks! It looks like computing the Hermite normal form efficiently is non-trivial, so I'll take a look through Wikipedia's references. Apparently LLL can compute the Hermite normal form so probably that's what I saw. $\endgroup$
    – Sam Jaques
    Jan 28, 2022 at 16:28
  • $\begingroup$ LLL on B' will reduce the basis. I.e. some output vectors will be zero vectors and can be discarded $\endgroup$
    – Fractalice
    Jan 28, 2022 at 21:41
  • $\begingroup$ Could you post an example as an answer? $\endgroup$
    – kelalaka
    Jan 29, 2022 at 16:05

1 Answer 1

1
$\begingroup$

Writing up an answer so this isn't unanswered, although HNF was mentioned in the comments.

The Hermite Normal Form is the standard way to reduce a generating set to a basis. This means it is the standard way to compute several operations on lattices (that are easily expressed in terms of basis vectors), for example

  • $L+L'$ (which your example is a special case of), or

  • $L\cap L'$ (this is less obvious, and requires duality).

See the easy lattice problems of these notes.

You commented

It looks like computing the Hermite normal form efficiently is non-trivial...

This is (sort of) true, but non-trivial is far from "hard". I quote from the notes

It is not hard to come up with an algorithm that computes the HNF of a matrix performing only a polynomial number of operations. However, a naive solution to this problem may result in superpolynomial running time because the numbers in the intermediate computations can easily get very large.

The linked notes include pseudocode for an HNF implementation that of polynomial running time (by ensuring intermediate values stay bounded). It is perhaps slightly more complex than LLL, but really not by much --- both are algorithms I would expect an junior/senior undergrad to be able to implement without too much effort.

Of course, you can expend more effort to get more practically efficient things. See this paper of Pernet and Stein. As Stein is the founder of the Sage CAS, I imagine this is fairly close to what Sage had implemented, at least circa 2011. This algorithm is perhaps the kind of "non-trivial" algorithm you had in mind. But on the other hand, efficient implementations of LLL similarly get non-trivial (I've heard a few years ago that LLL was simultaneously polynomial time, and perhaps hard to actually run on large lattices, say of dimension 1k+).

It's worth mentioning there does seem to be some work that computes HNFs using LLL as a subroutine, see for example this.

$\endgroup$
1
  • $\begingroup$ Thanks, the uniqueness of the HNF certainly explains how it can reduce a redundant lattice basis. I had gotten stuck on the Havas-Majewski-Matthews paper, where the proof of correctness is "an easy extension of the argument in Section 1", which I have not been able to figure out. $\endgroup$
    – Sam Jaques
    Feb 11, 2022 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.