Lattice in Wonderland: an LLL Optimization Problem

If you take a basis for a ℝ-vector space of dimension n, and consider only linear combinations of the basis vectors with integer coefficients, this defines what is called a lattice of dimension n. Lattices are connected to topics in Number Theory, Harmonic Analysis, Fractal Geometry, and Crystallography. An important aspect of Lattice theory is something called basis reduction, which has played an important role in areas such as the theory of integer programming, simultaneous Diophantine approximation, and knapsack cryptosystems. In general, a basis for a lattice consists of "long" vectors, but what we want is a basis consisting of "short" vectors. This is the fundamental problem of lattice basis reduction that can be solved using the LLL algorithm.

Upon input of a basis for some lattice, the LLL algorithm returns a new reduced basis, which depends on some parameter α, with 1/4 < α < 1 called the reduction parameter. The main goal of this project will be to address the question as to which numbers α give the bases with the "shortest" vectors. We also investigate the behavior of this optimal α as the dimension of the lattice grows to infinity. We will spend the first few weeks learning to both understand, and implement the LLL algorithm. We will then investigate whether or not there is a "best" reduction parameter α. Time permitting, we will investigate the additional problem of whether or not the algorithm terminates in polynomial time when α = 1. This project will expose students to aspects of numerical linear algebra, number theory, and will give them an opportunity to practice both linear algebra computer programming.