Lattices
W. Hendrik, Lenstra Jr. · 2008
It occurs frequently in algorithmic number theory that a problem has both a discrete and a continuous component. A typical example is the search for a system of integers that satisfies certain inequalities. A problem of this nature can often be successfully approached by means of the algorithmic theory of lattices, a lattice being a discrete subgroup of a Euclidean vector space. This article provides an introduction to this theory, including a generous sample of applications. A lattice is a discrete subgroup of a Euclidean vector space, and geometry of numbers is the theory that occupies itself with lattices. Since the publication of Hermann Minkowski’s Geometrie der Zahlen in 1896, lattices have become a standard tool in number theory, especially in the areas of diophantine approximation, algebraic number theory, and the arithmetic theory of quadratic forms. The theory of continued fractions, principally developed by Leonhard Euler (1707–1783), is in substance concerned with algorithmic aspects of lattices of rank 2. A significant advance in the algorithmic theory of lattices of general rank occurred in the early 1980’s, with the development of the powerful lattice basis reduction algorithm that came to be called the LLL algorithm [Lenstra et al. 1982]. The LLL algorithm has found numerous applications in both pure and applied mathematics. In algorithmic number theory, geometry of numbers now plays a role that is comparable to the role that linear programming plays in optimization theory, and that linear algebra plays throughout mathematics. This is due to a similar combination of circumstances: good algorithms are available for solving the basic problems, and many commonly encountered problems reduce to those basic problems. Just as a multitude of problems in mathematics can be linearized, so can many others be addressed by the introduction of a suitable lattice. Typically, this applies to problems that have both a discrete and a continuous component, such as the search for a system of integers that satisfies certain inequalities. Algorithmic number theory abounds in such problems.