# Dual lattice

Algebraic structure → Group theory Group theory :
Basic notions
Subgroup
Normal subgroup
Group action
Quotient group
(Semi-)direct product
Direct sum
Free product
Wreath product
Group homomorphisms
kernel
image
simple
finite
infinite
continuous
multiplicative
additive
cyclic
abelian
dihedral
nilpotent
solvable
Glossary of group theory
List of group theory topics :
Finite groups
Cyclic group Z$_n$
Symmetric group S$_n$
Alternating group A$_n$
Dihedral group D$_n$
Quaternion group Q
Cauchy's theorem
Lagrange's theorem
Sylow theorems
Hall's theorem
p-group
Elementary abelian group
Frobenius group
Schur multiplier
Classification of finite simple groups
cyclic
alternating
Lie type
sporadic :
Discrete groupsLattices
Integers ($\mathbb {Z}$)
Free group
Modular groups PSL(2, $\mathbb {Z}$)SL(2, $\mathbb {Z}$)
Arithmetic group
Lattice
Hyperbolic group :
Topological and Lie groups
Solenoid
Circle
General linear GL(n)
Special linear SL(n)
Orthogonal O(n)
Euclidean E(n)
Special orthogonal SO(n)
Unitary U(n)
Special unitary SU(n)
Symplectic Sp(n)
G$_2$
F$_4$
E$_6$
E$_7$
E$_8$
Lorentz
Poincaré
Conformal
Diffeomorphism
Loop
Infinite dimensional Lie group O(∞)SU(∞)Sp(∞) :
Algebraic groups
Linear algebraic group
Reductive group
Abelian variety
Elliptic curve :
vte :
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 L{\textstyle L} is the reciprocal of the geometry of L{\textstyle L}, 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 L⊆R$^n${\textstyle L\subseteq \mathbb {R} ^{n}} be a lattice. That is, L=BZ$^n${\textstyle L=B\mathbb {Z} ^{n}} for some matrix B{\textstyle B}.
The dual lattice is the set of linear functionals on L{\textstyle L} which take integer values on each point of L{\textstyle L}:
    $L^{*}=\{f\in ({\text{span}}(L))^{*}:\forall x\in L,f(x)\in \mathbb {Z} \}.$
If (R$^n$)$^∗${\textstyle (\mathbb {R} ^{n})^{*}} is identified with R$^n${\textstyle \mathbb {R} ^{n}} using the dot-product, we can write L$^∗$={v∈span(L):∀x∈L, v⋅x∈Z}.{\textstyle L^{*}=\{v\in {\text{span}}(L):\forall x\in L, v\cdot x\in \mathbb {Z} \}.} It is important to restrict to vectors in the span of L{\textstyle L}, 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:
    $L^{*}=\{f:L\to \mathbb {Z} :{\text{f is a linear function}}\}={\text{Hom}}_{\text{Ab}}(L,\mathbb {Z} ).$
However, we note that the dual is not considered just as an abstract Abelian group of functionals, but comes with a natural inner product: f⋅g=∑$_i$f(e$_i$)g(e$_i$){\textstyle f\cdot g=\sum _{i}f(e_{i})g(e_{i})}, where e$_i${\textstyle e_{i}} is an orthonormal basis of span(L){\textstyle {\text{span}}(L)}. (Equivalently, one can declare that, for an orthonormal basis e$_i${\textstyle e_{i}} of span(L){\textstyle {\text{span}}(L)}, the dual vectors e$_i$$^∗${\textstyle e_{i}^{*}}, defined by e$_i$$^∗$(e$_j$)=δ$_{ij}${\textstyle e_{i}^{*}(e_{j})=\delta _{ij}} 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:
* If B=[b$_1$, …, b$_n$]{\textstyle B=[b_{1}, \ldots , b_{n}]} is a matrix giving a basis for the lattice L{\textstyle L}, then z∈span(L){\textstyle z\in {\text{span}}(L)} satisfies z∈L$^∗$⟺b$_i$$^T$z∈Z, i=1, …, n⟺B$^T$z∈Z$^n${\textstyle z\in L^{*}\iff b_{i}^{T}z\in \mathbb {Z} , i=1, \ldots , n\iff B^{T}z\in \mathbb {Z} ^{n}}.
* If B{\textstyle B} is a matrix giving a basis for the lattice L{\textstyle L}, then B(B$^T$B)$^{−1}${\textstyle B(B^{T}B)^{-1}} gives a basis for the dual lattice. If L{\textstyle L} is full rank B$^{−T}${\textstyle B^{-T}} gives a basis for the dual lattice: z∈L$^∗$⟺B$^T$z∈Z$^n$⟺z∈B$^{−T}$Z$^n${\textstyle z\in L^{*}\iff B^{T}z\in \mathbb {Z} ^{n}\iff z\in B^{-T}\mathbb {Z} ^{n}}.
* The previous fact shows that (L$^∗$)$^∗$=L{\textstyle (L^{*})^{*}=L}. This equality holds under the usual identifications of a vector space with its double dual, or in the setting where the inner product has identified R$^n${\textstyle \mathbb {R} ^{n}} with its dual.
* Fix two lattices L, M{\textstyle L, M}. Then L⊆M{\textstyle L\subseteq M} if and only if L$^∗$⊇M$^∗${\textstyle L^{*}\supseteq M^{*}}.
* The determinant of a lattice is the reciprocal of the determinant of its dual: det(L$^∗$)=1/det(L) {\textstyle {\text{det}}(L^{*})={\frac {1}{{\text{det}}(L)}}}
* If q{\textstyle q} is a nonzero scalar, then (qL)$^∗$=1/q L$^∗${\textstyle (qL)^{*}={\frac {1}{q}}L^{*}}.
* If R{\textstyle R} is a rotation matrix, then (RL)$^∗$=RL$^∗${\textstyle (RL)^{*}=RL^{*}}.
* A lattice L{\textstyle L} is said to be integral if x⋅y∈Z{\textstyle x\cdot y\in \mathbb {Z} } for all x, y∈L{\textstyle x, y\in L}. Assume that the lattice L{\textstyle L} is full rank. Under the identification of Euclidean space with its dual, we have that L⊆L$^∗${\textstyle L\subseteq L^{*}} for integral lattices L{\textstyle L}. Recall that, if L$^′$⊆L{\textstyle L'\subseteq L} and |L/L$^′$|<∞{\textstyle |L/L'|<\infty }, then det(L$^′$)=det(L)|L/L$^′$|{\textstyle {\text{det}}(L')={\text{det}}(L)|L/L'|}. From this it follows that for an integral lattice, det(L)$^2$=|L$^∗$/L|{\textstyle {\text{det}}(L)^{2}=|L^{*}/L|}.
* An integral lattice is said to be unimodular if L=L$^∗${\textstyle L=L^{*}}, which, by the above, is equivalent to det(L)=1.{\textstyle {\text{det}}(L)=1.}

## Examples

Using the properties listed above, the dual of a lattice can be efficiently calculated, by hand or computer.
* The dual of Z$^n${\textstyle \mathbb {Z} ^{n}} is Z$^n${\textstyle \mathbb {Z} ^{n}}.
* The dual of 2Z⊕Z{\textstyle 2\mathbb {Z} \oplus \mathbb {Z} } is 1/2 Z⊕Z{\textstyle {\frac {1}{2}}\mathbb {Z} \oplus \mathbb {Z} }.
* Let L={x∈Z$^n$:∑x$_i$=0mod2}{\textstyle L=\{x\in \mathbb {Z} ^{n}:\sum x_{i}=0\mod 2\}} be the lattice of integer vectors whose coordinates have an even sum. Then L$^∗$=Z$^n$+(1/2, …, 1/2){\textstyle L^{*}=\mathbb {Z} ^{n}+({\frac {1}{2}}, \ldots , {\frac {1}{2}})}, that is, the dual is the lattice generated by the integer vectors along with the all 1/2{\textstyle 1/2}s vector.

## Transference theorems

Each f∈L$^∗$∖{0}{\textstyle f\in L^{*}\setminus \{0\}} partitions L{\textstyle L} according to the level sets corresponding to each of the integer values. Smaller choices of f{\textstyle f} produce level sets with more distance between them; in particular, the distance between the layers is 1/||f||{\textstyle 1/||f||}. Reasoning this way, one can show that finding small vectors in L$^∗${\textstyle L^{*}} provides a lower bound on the largest size of non-overlapping spheres that can be placed around points of L{\textstyle L}. 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 L{\textstyle L} , let λ$_i$(L){\textstyle \lambda _{i}(L)} denote the smallest radius ball that contains a set of i{\textstyle i} linearly independent vectors of L{\textstyle L}. For instance, λ$_1$(L){\textstyle \lambda _{1}(L)} is the length of the shortest vector of L{\textstyle L}. Let μ(L)=max$_{x∈Rn}$d(x, L){\textstyle \mu (L)={\text{max}}_{x\in \mathbb {R} ^{n}}d(x, L)} denote the covering radius of L{\textstyle L}.
In this notation, the lower bound mentioned in the introduction to this section states that μ(L)≥ 1/2λ$_1$(L$^∗$) {\textstyle \mu (L)\geq {\frac {1}{2\lambda _{1}(L^{*})}}}.
Theorem (Banaszczyk) — For a lattice L{\textstyle L}:
    $1\leq 2\lambda _{1}(L)\mu (L^{*})\leq n$
    $1\leq \lambda _{i}(L)\lambda _{n-i+1}(L^{*})\leq n$
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 λ$_1$(L)≥ 1/λ$_n$(L$^∗$) {\textstyle \lambda _{1}(L)\geq {\frac {1}{\lambda _{n}(L^{*})}}}, 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 GAPSVP$_n${\textstyle {\text{GAPSVP}}_{n}} problem) is in NP∩coNP{\textstyle {\text{NP}}\cap {\text{coNP}}}.
Other transference theorems:
* The relationship λ$_1$(L)λ$_1$(L$^∗$)≤n{\textstyle \lambda _{1}(L)\lambda _{1}(L^{*})\leq n} follows from Minkowski's bound on the shortest vector; that is, λ$_1$(L)≤√n(det(L)$^{1/n}$){\textstyle \lambda _{1}(L)\leq {\sqrt {n}}({\text{det}}(L)^{1/n})}, and λ$_1$(L$^∗$)≤√n(det(L$^∗$)$^{1/n}$){\textstyle \lambda _{1}(L^{*})\leq {\sqrt {n}}({\text{det}}(L^{*})^{1/n})}, from which the claim follows since det(L)=1/det(L$^∗$) {\textstyle {\text{det}}(L)={\frac {1}{{\text{det}}(L^{*})}}}.

## Poisson summation formula

The dual lattice is used in the statement of a general Poisson summation formula.
Theorem —  Theorem (Poisson Summation) Let f:R$^n$→R{\textstyle f:\mathbb {R} ^{n}\to \mathbb {R} } be a well-behaved function, such as a Schwartz function, and let f$^^${\textstyle {\hat {f}}} denote its Fourier transform. Let L⊆R$^n${\textstyle L\subseteq \mathbb {R} ^{n}} be a full rank lattice. Then:
    $\sum _{x\in L}f(x)={\frac {1}{\det(L)}}\sum _{y\in L^{*}}{\hat {f}}(y)$.