Dual lattice

Last updated October 05, 2024

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 ${\textstyle L}$ is the reciprocal of the geometry of ${\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 ${\textstyle L\subseteq \mathbb {R} ^{n}}$ be a lattice. That is, ${\textstyle L=B\mathbb {Z} ^{n}}$ for some matrix ${\textstyle B}$ .

The dual lattice is the set of linear functionals on ${\textstyle L}$ which take integer values on each point of ${\textstyle L}$ :

L^{*}=\{f\in ({\text{span}}(L))^{*}:\forall x\in L,f(x)\in \mathbb {Z} \}.

If ${\textstyle (\mathbb {R} ^{n})^{*}}$ is identified with ${\textstyle \mathbb {R} ^{n}}$ using the dot-product, we can write ${\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 ${\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

However, we note that the dual is not considered just as an abstract Abelian group of functionals, but comes with a natural inner product: ${\textstyle f\cdot g=\sum _{i}f(e_{i})g(e_{i})}$ , where ${\textstyle e_{i}}$ is an orthonormal basis of ${\textstyle {\text{span}}(L)}$ . (Equivalently, one can declare that, for an orthonormal basis ${\textstyle e_{i}}$ of ${\textstyle {\text{span}}(L)}$ , the dual vectors ${\textstyle e_{i}^{*}}$ , defined by ${\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 ${\textstyle B=[b_{1},\ldots ,b_{n}]}$ is a matrix giving a basis for the lattice ${\textstyle L}$ , then ${\textstyle z\in {\text{span}}(L)}$ satisfies ${\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 ${\textstyle B}$ is a matrix giving a basis for the lattice ${\textstyle L}$ , then ${\textstyle B(B^{T}B)^{-1}}$ gives a basis for the dual lattice. If ${\textstyle L}$ is full rank ${\textstyle B^{-T}}$ gives a basis for the dual lattice: ${\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 ${\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 ${\textstyle \mathbb {R} ^{n}}$ with its dual.
Fix two lattices ${\textstyle L,M}$ . Then ${\textstyle L\subseteq M}$ if and only if ${\textstyle L^{*}\supseteq M^{*}}$ .
The determinant of a lattice is the reciprocal of the determinant of its dual: ${\textstyle {\text{det}}(L^{*})={\frac {1}{{\text{det}}(L)}}}$
If ${\textstyle q}$ is a nonzero scalar, then ${\textstyle (qL)^{*}={\frac {1}{q}}L^{*}}$ .
If ${\textstyle R}$ is a rotation matrix, then ${\textstyle (RL)^{*}=RL^{*}}$ .
A lattice ${\textstyle L}$ is said to be integral if ${\textstyle x\cdot y\in \mathbb {Z} }$ for all ${\textstyle x,y\in L}$ . Assume that the lattice ${\textstyle L}$ is full rank. Under the identification of Euclidean space with its dual, we have that ${\textstyle L\subseteq L^{*}}$ for integral lattices ${\textstyle L}$ . Recall that, if ${\textstyle L'\subseteq L}$ and ${\textstyle |L/L'|<\infty }$ , then ${\textstyle {\text{det}}(L')={\text{det}}(L)|L/L'|}$ . From this it follows that for an integral lattice, ${\textstyle {\text{det}}(L)^{2}=|L^{*}/L|}$ .
An integral lattice is said to be unimodular if ${\textstyle L=L^{*}}$ , which, by the above, is equivalent to ${\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 ${\textstyle \mathbb {Z} ^{n}}$ is ${\textstyle \mathbb {Z} ^{n}}$ .
The dual of ${\textstyle 2\mathbb {Z} \oplus \mathbb {Z} }$ is ${\textstyle {\frac {1}{2}}\mathbb {Z} \oplus \mathbb {Z} }$ .
Let ${\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 ${\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 ${\textstyle 1/2}$ s vector.

Transference theorems

Each ${\textstyle f\in L^{*}\setminus \{0\}}$ partitions ${\textstyle L}$ according to the level sets corresponding to each of the integer values. Smaller choices of ${\textstyle f}$ produce level sets with more distance between them; in particular, the distance between the layers is ${\textstyle 1/||f||}$ . Reasoning this way, one can show that finding small vectors in ${\textstyle L^{*}}$ provides a lower bound on the largest size of non-overlapping spheres that can be placed around points of ${\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 ${\textstyle L}$ , let ${\textstyle \lambda _{i}(L)}$ denote the smallest radius ball that contains a set of ${\textstyle i}$ linearly independent vectors of ${\textstyle L}$ . For instance, ${\textstyle \lambda _{1}(L)}$ is the length of the shortest vector of ${\textstyle L}$ . Let ${\textstyle \mu (L)={\text{max}}_{x\in \mathbb {R} ^{n}}d(x,L)}$ denote the covering radius of ${\textstyle L}$ .

In this notation, the lower bound mentioned in the introduction to this section states that ${\textstyle \mu (L)\geq {\frac {1}{2\lambda _{1}(L^{*})}}}$ .

Theorem (Banaszczyk)^[1] — For a lattice ${\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 ${\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 ${\textstyle {\text{GAPSVP}}_{n}}$ problem) is in ${\textstyle {\text{NP}}\cap {\text{coNP}}}$ .^[2]

Other transference theorems:

The relationship ${\textstyle \lambda _{1}(L)\lambda _{1}(L^{*})\leq n}$ follows from Minkowski's bound on the shortest vector; that is, ${\textstyle \lambda _{1}(L)\leq {\sqrt {n}}({\text{det}}(L)^{1/n})}$ , and ${\textstyle \lambda _{1}(L^{*})\leq {\sqrt {n}}({\text{det}}(L^{*})^{1/n})}$ , from which the claim follows since ${\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)^[3] Let ${\textstyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ be a well-behaved function, such as a Schwartz function, and let ${\textstyle {\hat {f}}}$ denote its Fourier transform. Let ${\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)

.

Related Research Articles

<span class="mw-page-title-main">Minkowski's theorem</span> Every symmetric convex set in R^n with volume > 2^n contains a non-zero integer point

In mathematics, Minkowski's theorem is the statement that every convex set in $which is symmetric with respect to the origin and which has volume greater than contains a non-zero integer point. The theorem was proved by Hermann Minkowski in 1889 and became the foundation of the branch of number theory called the geometry of numbers. It can be extended from the integers to any lattice and to any symmetric convex set with volume greater than, where denotes the covolume of the lattice.$

In mathematics, a self-adjoint operator on a complex vector space V with inner product $is a linear map A that is its own adjoint. If V is finite-dimensional with a given orthonormal basis, this is equivalent to the condition that the matrix of A is a Hermitian matrix, i.e., equal to its conjugate transpose A * . By the finite-dimensional spectral theorem, V has an orthonormal basis such that the matrix of A relative to this basis is a diagonal matrix with entries in the real numbers. This article deals with applying generalizations of this concept to operators on Hilbert spaces of arbitrary dimension.$

In mathematics, specifically functional analysis, a trace-class operator is a linear operator for which a trace may be defined, such that the trace is a finite number independent of the choice of basis used to compute the trace. This trace of trace-class operators generalizes the trace of matrices studied in linear algebra. All trace-class operators are compact operators.

In vector calculus, Green's theorem relates a line integral around a simple closed curve $C$ to a double integral over the plane region $D$ bounded by $C$ . It is the two-dimensional special case of Stokes' theorem. In one dimension, it is equivalent to the fundamental theorem of calculus. In three dimensions, it is equivalent to the divergence theorem.

In mathematics, the uniform boundedness principle or Banach–Steinhaus theorem is one of the fundamental results in functional analysis. Together with the Hahn–Banach theorem and the open mapping theorem, it is considered one of the cornerstones of the field. In its basic form, it asserts that for a family of continuous linear operators whose domain is a Banach space, pointwise boundedness is equivalent to uniform boundedness in operator norm.

In mathematics, a modular form is a (complex) analytic function on the upper half-plane, $, that satisfies:$

In mathematics, the Hodge star operator or Hodge star is a linear map defined on the exterior algebra of a finite-dimensional oriented vector space endowed with a nondegenerate symmetric bilinear form. Applying the operator to an element of the algebra produces the Hodge dual of the element. This map was introduced by W. V. D. Hodge.

In geometry, the cross-ratio, also called the double ratio and anharmonic ratio, is a number associated with a list of four collinear points, particularly points on a projective line. Given four points $A$ , $B$ , $C$ , $D$ on a line, their cross ratio is defined as

In mathematics, the Poisson summation formula is an equation that relates the Fourier series coefficients of the periodic summation of a function to values of the function's continuous Fourier transform. Consequently, the periodic summation of a function is completely defined by discrete samples of the original function's Fourier transform. And conversely, the periodic summation of a function's Fourier transform is completely defined by discrete samples of the original function. The Poisson summation formula was discovered by Siméon Denis Poisson and is sometimes called Poisson resummation.

In functional analysis and related branches of mathematics, the Banach–Alaoglu theorem states that the closed unit ball of the dual space of a normed vector space is compact in the weak* topology. A common proof identifies the unit ball with the weak-* topology as a closed subset of a product of compact sets with the product topology. As a consequence of Tychonoff's theorem, this product, and hence the unit ball within, is compact.

In linear algebra and functional analysis, the min-max theorem, or variational theorem, or Courant–Fischer–Weyl min-max principle, is a result that gives a variational characterization of eigenvalues of compact Hermitian operators on Hilbert spaces. It can be viewed as the starting point of many results of similar nature.

In mathematics, particularly in operator theory and C*-algebra theory, the continuous functional calculus is a functional calculus which allows the application of a continuous function to normal elements of a C*-algebra.

In mathematics, a complex torus is a particular kind of complex manifold M whose underlying smooth manifold is a torus in the usual sense. Here N must be the even number 2n, where n is the complex dimension of M.

In mathematics, a $π$ -system on a set $is a collection of certain subsets of such that$

In linear algebra, a frame of an inner product space is a generalization of a basis of a vector space to sets that may be linearly dependent. In the terminology of signal processing, a frame provides a redundant, stable way of representing a signal. Frames are used in error detection and correction and the design and analysis of filter banks and more generally in applied mathematics, computer science, and engineering.

In mathematics, the Brunn–Minkowski theorem is an inequality relating the volumes of compact subsets of Euclidean space. The original version of the Brunn–Minkowski theorem applied to convex sets; the generalization to compact nonconvex sets stated here is due to Lazar Lyusternik (1935).

In mathematics, an ordered vector space or partially ordered vector space is a vector space equipped with a partial order that is compatible with the vector space operations.

In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line $which consists of the real numbers and$

In the geometry of numbers, the Klein polyhedron, named after Felix Klein, is used to generalize the concept of continued fractions to higher dimensions.

In mathematics, Minkowski's second theorem is a result in the geometry of numbers about the values taken by a norm on a lattice and the volume of its fundamental cell.

References

↑ Banaszczyk, W. (1993). "New bounds in some transference theorems in the geometry of numbers". Mathematische Annalen. 296 (1). Springer Science and Business Media LLC: 625–635. doi:10.1007/bf01445125. ISSN 0025-5831. S2CID 13921988.
↑ Cai, Jin-Yi; Nerurkar, Ajay (2000). "A note on the non-NP-hardness of approximate lattice problems under general Cook reductions". Information Processing Letters. 76 (1–2): 61–66. doi:10.1016/S0020-0190(00)00123-X. MR 1797563.
↑ Cohn, Henry; Kumar, Abhinav; Reiher, Christian; Schürmann, Achill (2014). "Formal duality and generalizations of the Poisson summation formula". Discrete Geometry and Algebraic Combinatorics. Contemporary Mathematics. Vol. 625. pp. 123–140. arXiv: 1306.6796v2 . doi:10.1090/conm/625/12495. ISBN 9781470409050. S2CID 117741906.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Banaszczyk_1993_pp._625–635-1] Banaszczyk, W. (1993). "New bounds in some transference theorems in the geometry of numbers". Mathematische Annalen. 296 (1). Springer Science and Business Media LLC: 625–635. doi:10.1007/bf01445125. ISSN 0025-5831. S2CID 13921988.

[2] Cai, Jin-Yi; Nerurkar, Ajay (2000). "A note on the non-NP-hardness of approximate lattice problems under general Cook reductions". Information Processing Letters. 76 (1–2): 61–66. doi:10.1016/S0020-0190(00)00123-X. MR 1797563.

[Cohn_Kumar_Reiher_Schürmann_2013-3] Cohn, Henry; Kumar, Abhinav; Reiher, Christian; Schürmann, Achill (2014). "Formal duality and generalizations of the Poisson summation formula". Discrete Geometry and Algebraic Combinatorics. Contemporary Mathematics. Vol. 625. pp. 123–140. arXiv: 1306.6796v2 . doi:10.1090/conm/625/12495. ISBN 9781470409050. S2CID 117741906.

[1]

[2]

[3]