Lindep - LLL algorithm


In this version of the Lindep algorithm we use the lattice basis reduction algorithm of Lenstra-Lentsra-Lovasz (LLL).
This algorithm finds a so called reduced basis of the lattice given by generators. The reduced basis contains an approximation
to the shortest vector in a lattice.

The LLL  lattice basis reduction algorithm first appeared in the following paper:

A. K. Lenstra, H. W. Lenstra, Jr. and L. LovĂ sz, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982)

The following text about the application of the LLL algorithm to find linear integer relations was pulled out from the following paper:
Applications of Integer Relation Algorithms by Jonathan M. Borwein and Petr Lisonek, Discrete Mathematics (Special issue for FPSAC 1997)

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(i) ($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,

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


then

\begin{displaymath}\Big\vert\sum_{i=1}^n w_i a_i'\Big\vert\end{displaymath}


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.
Back to IntegerRelations.


Agnes Szanto

Last modified: Thu May 4 18:48:59 PDT 2000