Lattices, also known as Minkowski's theory after Hermann Minkowski, or the geometry of numbers (deprecated!) allows the usage of geometrical tools (i.e. volumes) in number theory.
The intuitive notion of a lattice (perhaps surprisingly) matches its mathematical definition. For example, lattices are formed by
points on an infinite checkerboard;
centers of a hexagonal tessellation;
integers on the real number line.
The last example should hint at how we generalize this concept to arbitrary dimensions. In general, lattices consist of discrete points which appear at "regular intervals."
A lattice is a subgroup of generated by , i.e.
where are linearly independent vectors. Collectively, form a basis of.
We say a set of vectors are linearly independent if the only solution to the equation is when all are zero.
Taking a step back, this definition should resemble that of a vector space, with one exception: scalars are integers! The discrete nature of lattices comes from this restriction.
Some more terminology from linear algebra will be useful. The dimension of a lattice, denoted, is . A lattice is complete if . Note that we can always choose a subspace of such that the lattice is complete, namely the subspace generated by .
The region
is known as the fundamental mesh.
In the image above, we see the points of a lattice in . The red vectors are one set of basis vectors and the shaded region is the corresponding fundamental mesh. The green vectors also form another set of basis vectors with its corresponding fundamental mesh. We see here that the basis vectors and fundamental mesh is not unique to a lattice.
Although the fundamental mesh is not unique, it turns out that the (dimensional) volume of the fundamental mesh is constant for any given lattice. Hence we can define the volume of a lattice as the volume of a fundamental mesh. However this definition can be hard to handle hence we provide an equivalent definition via determinants:
Letbe amatrix whose rows are given by the basis vectors. Then the volume of a fundamental mesh is given by
A subset of is known as centrally symmetric if implies . It is convex if for any , the line joining is contained in , i.e. . Finally we can introduce the most important theorem about lattices, the Minkowski's Lattice Point Theorem:
Let be a complete lattice of dimension and be a centrally symmetric convex set. Suppose
Then contains at least one nonzero point of . This result is primarily used to prove the existence of lattice vectors.
Throughout this section, denotes the norm and denotes the inner product.
This proof is by some sort of a pigeonhole argument on volumes. Consider the set
We have , hence the inclusion cannot be injective, thus we can find some , . Hence is a nontrivial lattice point.
1) Let be the lattice generated by (take the rows as basis vectors).
Compute the volume of this lattice
Show that generates the same lattice
Show that each row in is in the lattice butdoes not generate the lattice. This is one key difference from the case of linear algebra (over fields).
2) Letbe matrices whose row vectors are basis for lattices . Both lattices are the same iff there exists some such that . Find for problem 1. Note that is the group of invertible matrices with integer coefficients, meaning and have integer coefficients.
3) Show that the condition in Minkowski's lattice point theorem is strict, i.e. for any complete latticeof dimension , we can find some centrally symmetric convex setwithbut the only lattice point inis the origin.
4*) Letbe the shortest nonzero vector for some lattice with dimension. Show that