Lattice Basis Reduction Methods

By the length of the vector $v\in\mathbb Q^n$ we mean its Euclidean length, that is, $\vert v\vert=\left(\sum_{i=1}^n v_i^2\right)^{1/2}$.

Suppose we have a set of k vectors $B=\{v^{(1)},\ldots,v^{(k)}\}\subset\mathbb Q^n$, linearly independent over $\mathbb Q$. By the lattice spanned by Bwe mean the set

$$L=\left\{ \sum_{i=1}^k r_iv^{(i)} \;\Big\vert\; r_i\in\mathbb Z\right\}\subset \mathbb Q^n.$$

This lattice has dimension n and rank k. The set Bis called a basis of the lattice. The basis of course is not unique, and given a lattice, we may look for bases with some distinguished properties.

The problem of finding the shortest vector in a given lattice Lis believed to be NP-complete [29]. There are, however, approximate solution algorithms for this problem that run in polynomial time, such as the famous LLL lattice basis reduction algorithm [32] which, given a basis for a lattice L, finds a reduced basis for L that is entirely composed of vectors with length at most $2^{n-1}\cdot l$, where l is the length of the shortest vector in L and n is the dimension of L.

Lattice basis reduction algorithms can be employed to search for integer relations in the following way  ([32], p. 535). Suppose that we are given a vector of real numbers $(a_1,\ldots,a_n)$ and let $(a'_1,\ldots,a'_n)$ be a vector of their rational approximations. Let us consider the lattice L spanned by the (n+1)-dimensional vectors v⁽ⁱ⁾ ( $1\le i\le n$) where $v_j^{(i)}=\delta_{i,j}$ (the Kronecker delta) for $1\le i,j\le n$and $v_{n+1}^{(i)}=C\cdot a_i'$ for $1\le i\le n$, where C is a large rational constant. Now, if w is a short vector in a reduced basis for L,

$$w=\Big(w_1,\ldots,w_n,C\sum_{i=1}^n w_i a_i'\Big),$$

then

$$\Big\vert\sum_{i=1}^n w_i a_i'\Big\vert$$

is small and thus $(w_1,\ldots,w_n)$ is a good candidate for an integer relation for the vector $(a_1,\ldots,a_n)$. Of course, with increasing Cwe improve our chances of correctly determining which vectors in the reduced basis correspond to an integer relation for $(a_1,\ldots,a_n)$, and which do not.

In some applications we are looking for integers $(w_1,\ldots,w_n)$ such that $\sum_{i=1}^n w_ia_i$ is non-zero, but small in absolute value. The approach explained in the last paragraph applies to this situation similarly as it applies to the integer relation search. For example, de Weger [36] uses an LLL-type algorithm to look for distinct integers x,y such that (i) x and y are composed exclusively from the given set set of primes, say $\{p_1,\ldots,p_s\}$, and (ii) the value |x-y| is small. Then $x/y=:p_1^{e_1}\cdot\ldots\cdot p_s^{e_s}$ is close to 1 (with $e_1,\ldots,e_s\in\mathbb Z$), and therefore $e_1\log p_1+\cdots+e_s\log p_s$ is small in absolute value (but non-zero).

Finally, a technical detail about the LLL implementations is worth mentioning. Many software systems have LLL-based routines that search for minimal polynomials (Section 2.3) but correspondingly lack a general integer relation routine. It was the purpose of this section to give the reader sufficient insight in the LLL-based integer relation search so that (s)he can adapt the minimal polynomial routine as a general integer relation routine.