Dual lattice
In the theory of lattices, the dual lattice is a construction analogous to that of a dual vector space. In certain respects, the geometry of the dual lattice of a lattice formula_1 is the reciprocal of the geometry of formula_1, a perspective which underlies many of its uses. 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. Definition. Let formula_3 be a lattice. That is, formula_4 for some matrix formula_5. The dual lattice is the set of linear functionals on formula_1 which take integer values on each point of formula_1: If formula_9 is identified with formula_10 using the dot-product, we can write formula_11 It is important to restrict to vectors in the span of formula_12, 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: formula_14, where formula_15 is an orthonormal basis of formula_16. (Equivalently, one can declare that, for an orthonormal basis formula_15 of formula_18, the dual vectors formula_19, defined  by formula_20 are 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. Properties. We list some elementary properties of the dual lattice: Examples. Using the properties listed above, the dual of a lattice can be efficiently calculated, by hand or computer. Certain lattices with importance in mathematics and computer science are dual to each other, and we list  some here. q-ary lattices. An important class of examples, particularly in lattice cryptography, are given by the q-ary lattices. For a matrix formula_60 we define formula_61; these are called, respectively, the image and kernel q-ary lattices associated to formula_62. Then, after identifying Euclidean space with its dual, we have that the image and kernel q-ary lattices of a matrix formula_62 are dual, up to a scalar. In particular, formula_64 and formula_65. (The proof can be done as an exercise.) Transference theorems. Each formula_66 partitions formula_12 according to the level sets corresponding to each of the integer  values. Smaller choices of formula_68 produce level sets with more distance between them; in particular, the distance between the layers is formula_69. Reasoning this way, one can show that finding small vectors in formula_70 provides a lower bound on the largest size of non-overlapping spheres that can be placed around points of formula_12. 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 formula_72 , let formula_73 denote the  smallest radius ball that contains a set of formula_74 linearly independent vectors of formula_72. For instance, formula_76 is the length of the shortest vector of formula_72. Let formula_78 denote the covering radius of formula_1. In this notation, the lower bound mentioned in the introduction to this section states that formula_80. 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 formula_81, 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 formula_82 problem) is in formula_83. Other transference theorems: Poisson summation formula. The dual lattice is used in the statement of a general Poisson summation formula.