In the theory of lattices, the dual lattice is a construction analogous to that of a dual vector space.
Dual lattices have many applications inside of lattice theory, theoretical computer science, cryptography and mathematics more broadly.
For instance, it is used in the statement of the Poisson summation formula, transference theorems provide connections between the geometry of a lattice and that of its dual, and many lattice algorithms exploit the dual lattice.
For an article with emphasis on the physics / chemistry applications, see Reciprocal lattice.
This article focuses on the mathematical notion of a dual lattice.
The dual lattice is the set of linear functionals on
It is important to restrict to vectors in the span of
, otherwise the resulting object is not a lattice.
Despite this identification of ambient Euclidean spaces, it should be emphasized that a lattice and its dual are fundamentally different kinds of objects; one consists of vectors in Euclidean space, and the other consists of a set of linear functionals on that space.
Along these lines, one can also give a more abstract definition as follows: However, we note that the dual is not considered just as an abstract Abelian group of functionals, but comes with a natural inner product:
(Equivalently, one can declare that, for an orthonormal basis
One of the key uses of duality in lattice theory is the relationship of the geometry of the primal lattice with the geometry of its dual, for which we need this inner product.
In the concrete description given above, the inner product on the dual is generally implicit.
We list some elementary properties of the dual lattice: Using the properties listed above, the dual of a lattice can be efficiently calculated, by hand or computer.
according to the level sets corresponding to each of the integer values.
Reasoning this way, one can show that finding small vectors in
provides a lower bound on the largest size of non-overlapping spheres that can be placed around points of
In general, theorems relating the properties of a lattice with properties of its dual are known as transference theorems.
In this section we explain some of them, along with some consequences for complexity theory.
We recall some terminology: For a lattice
denote the smallest radius ball that contains a set of
linearly independent vectors of
denote the covering radius of
In this notation, the lower bound mentioned in the introduction to this section states that
Theorem (Banaszczyk)[1] — For a lattice
: There always an efficiently checkable certificate for the claim that a lattice has a short nonzero vector, namely the vector itself.
An important corollary of Banaszcyk's transference theorem is that
, which implies that to prove that a lattice has no short vectors, one can show a basis for the dual lattice consisting of short vectors.
Using these ideas one can show that approximating the shortest vector of a lattice to within a factor of n (the
[2] Other transference theorems: The dual lattice is used in the statement of a general Poisson summation formula.