Dual lattice

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

In lattice theory, the dual lattice L* is a companion to L that plays the role of a reciprocal geometry. If L is a lattice in R^n, the dual is the set of all linear functionals on L that take integer values on every point of L. When we identify functionals with vectors using the dot product, we can write:
L* = { v in span(L) : for all x in L, v · x is an integer }.
We must stay in the span of L, otherwise the result isn’t a lattice. Note that a lattice and its dual are different kinds of objects: L is a set of vectors, while L* is a set of linear functionals.

A convenient inner product on the dual: if e1, e2, … form an orthonormal basis for span(L), then the dual vectors satisfy a natural inner product f · g = sum_i f(e_i) g(e_i).

Why the dual matters: the dual encodes reciprocal geometry. Small vectors in L* give information about how far apart “layers” of L can be, because the level sets {x in span(L) : f · x = k} for k ∈ Z partition L, with spacing about 1/||f||. In general, understanding L* helps bound how tightly L can pack spheres and how its geometry behaves.

Key quantities and transference theorems:
- For L, let λ_i(L) be the smallest radius that contains i linearly independent lattice vectors, so λ1(L) is the length of the shortest nonzero vector.
- Let μ(L) be the covering radius: the largest distance from a point in space to the lattice L.
- A basic transference relation is μ(L) ≥ 1/(2 λ1(L*)). In words, the dual’s shortest nonzero vector gives a lower bound on how well L can cover space.

Big takeaway from transference results (due to Banaszczyk): there is an efficiently verifiable certificate for whether L has a short nonzero vector, namely the vector itself. A common corollary is
λ1(L) ≥ 1/λn(L*),
which says that proving L has no short vectors can be done by showing the dual has short vectors.

Consequences for complexity: these theorems lead to the result that approximating the shortest vector of a lattice within a factor n (the GAPSVP_n problem) lies in NP ∩ coNP.

Poisson summation and beyond: duality also appears in the Poisson summation formula, which relates sums over L to sums over L* through the Fourier transform of a well-behaved function.

Practical note: the dual lattice can be computed efficiently from a given basis for L, so these duality tools are not just theoretical—they are used in algorithms, cryptography, and deeper mathematical applications. If L is given by a basis B, then a common characterization is
L* = { y in span(L) : B^T y ∈ Z^n }.