# 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  (, p. 535). Suppose that we are given a vector of real numbers and let be a vector of their rational approximations. Let us consider the lattice L spanned by the (n+1)-dimensional vectors v(i) ( ) where (the Kronecker delta) for and for , where C is a large rational constant. Now, if w is a short vector in a reduced basis for L, then is small and thus is a good candidate for an integer relation for the vector . Of course, with increasing Cwe improve our chances of correctly determining which vectors in the reduced basis correspond to an integer relation for , and which do not.
Back to IntegerRelations.

Agnes Szanto