Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Dual lattice
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Construction analogous to that of a dual vector space}} {{for|duals of order-theoretic lattices|Duality (order theory) }} {{Group theory sidebar |Discrete}} In the theory of [[Lattice (group)|lattices]], the '''dual lattice''' is a construction analogous to that of a [[Dual space|dual vector space]]. In certain respects, the geometry of the dual lattice of a lattice <math display = "inline"> L </math> is the reciprocal of the geometry of <math display = "inline"> L </math>, 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 <math display = "inline"> L \subseteq \mathbb{R}^n </math> be a lattice. That is, <math display = "inline"> L = B \mathbb{Z}^n </math> for some matrix <math display = "inline"> B </math>. The dual lattice is the set of [[linear form|linear]] [[Functional (mathematics)|functionals]] on <math display = "inline"> L </math> which take integer values on each point of <math display = "inline"> L </math>: :<math> L^* = \{ f \in (\text{span}(L))^* : \forall x \in L, f(x) \in \mathbb{Z} \}. </math> If <math display = "inline"> (\mathbb{R}^n)^* </math> is identified with <math display = "inline"> \mathbb{R}^n </math> using the [[dot-product]], we can write <math display="inline"> L^* = \{ v \in \text{span}(L) : \forall x \in L, v \cdot x \in \mathbb{Z} \}. </math> It is important to restrict to [[Vector (mathematics and physics)|vector]]s in the [[linear span|span]] of <math display="inline"> L </math>, otherwise the resulting object is not a [[Lattice (group)|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: :<math> L^* = \{ f : L \to \mathbb{Z} : \text{f is a linear function} \} = \text{Hom}_{\text{Ab}}(L, \mathbb{Z}). </math> However, we note that the dual is not considered just as an abstract [[Abelian group]] of functionals, but comes with a natural inner product: <math display="inline"> f \cdot g = \sum_i f(e_i) g(e_i) </math>, where <math display="inline"> e_i </math> is an [[orthonormality|orthonormal]] basis of <math display="inline"> \text{span}(L)</math>. (Equivalently, one can declare that, for an orthonormal basis <math display="inline"> e_i </math> of <math display="inline"> \text{span}(L) </math>, the dual vectors <math display="inline"> e^*_i </math>, defined by <math display="inline"> e_i^*(e_j) = \delta_{ij} </math> 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 <math display = "inline"> B = [b_1, \ldots, b_n] </math> is a matrix giving a basis for the lattice <math display = "inline"> L </math>, then <math display = "inline"> z \in \text{span}(L) </math> satisfies <math display = "inline"> z \in L^* \iff b^T_i z \in \mathbb{Z}, i = 1, \ldots, n \iff B^T z \in \mathbb{Z}^n</math>. * If <math display = "inline"> B </math> is a matrix giving a basis for the lattice <math display = "inline"> L </math>, then <math display = "inline"> B (B^T B)^{-1} </math> gives a basis for the dual lattice. If <math display = "inline"> L </math> is full rank <math display = "inline"> B^{-T} </math> gives a basis for the dual lattice: <math display = "inline"> z \in L^* \iff B^T z \in \mathbb{Z}^n \iff z \in B^{-T} \mathbb{Z}^n </math>. * The previous fact shows that <math display = "inline"> (L^*)^* = L </math>. 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 <math display = "inline"> \mathbb{R}^n </math> with its dual. * Fix two lattices <math display = "inline"> L,M </math>. Then <math display = "inline"> L \subseteq M </math> if and only if <math display = "inline"> L^* \supseteq M^* </math>. * The determinant of a lattice is the reciprocal of the determinant of its dual: <math display = "inline"> \text{det}(L^*) = \frac{1}{\text{det}(L)} </math> * If <math display = "inline"> q </math> is a nonzero scalar, then <math display = "inline"> (qL)^* = \frac{1}{q} L^* </math>. * If <math display = "inline"> R </math> is a rotation matrix, then <math display = "inline"> (RL)^* = R L^* </math>. * A lattice <math display="inline"> L </math> is said to be integral if <math display = "inline"> x \cdot y \in \mathbb{Z} </math> for all <math display="inline"> x,y \in L </math>. Assume that the lattice <math display="inline"> L </math> is full rank. Under the identification of Euclidean space with its dual, we have that <math display="inline"> L \subseteq L^* </math> for integral lattices <math display="inline"> L </math>. Recall that, if <math display="inline"> L' \subseteq L </math> and <math display="inline"> |L/L'| <\infty </math>, then <math display="inline"> \text{det}(L') = \text{det}(L) | L/L'| </math>. From this it follows that for an integral lattice, <math display="inline"> \text{det}(L)^2 = | L^* / L| </math>. * An integral lattice is said to be ''unimodular'' if <math display="inline"> L = L^*</math>, which, by the above, is equivalent to <math display="inline"> \text{det}(L) = 1. </math> ==Examples== Using the properties listed above, the dual of a lattice can be efficiently calculated, by hand or computer. * The dual of <math display="inline"> \mathbb{Z}^n </math> is <math display="inline"> \mathbb{Z}^n </math>. * The dual of <math display="inline"> 2\mathbb{Z} \oplus \mathbb{Z} </math> is <math display="inline"> \frac{1}{2} \mathbb{Z} \oplus \mathbb{Z} </math>. * Let <math display="inline"> L = \{ x \in \mathbb{Z}^n : \sum x_i = 0 \mod 2 \}</math> be the lattice of integer vectors whose coordinates have an even sum. Then <math display="inline"> L^* = \mathbb{Z}^n + (\frac{1}{2}, \ldots, \frac{1}{2}) </math>, that is, the dual is the lattice generated by the integer vectors along with the all <math display="inline"> 1/2 </math>s vector. ==Transference theorems== Each <math display="inline"> f \in L^* \setminus \{0\} </math> partitions <math display="inline"> L </math> according to the level sets corresponding to each of the integer values. Smaller choices of <math display="inline"> f </math> produce level sets with more distance between them; in particular, the distance between the layers is <math display="inline"> 1 / ||f|| </math>. <!--- picture would be great here. ---> Reasoning this way, one can show that finding small vectors in <math display="inline"> L^* </math> provides a lower bound on the largest size of non-overlapping spheres that can be placed around points of <math display="inline"> L </math>. 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 <math display = "inline"> L</math> , let <math display = "inline"> \lambda_i(L) </math> denote the smallest radius ball that contains a set of <math display = "inline"> i </math> linearly independent vectors of <math display = "inline"> L</math>. For instance, <math display = "inline"> \lambda_1(L) </math> is the length of the shortest vector of <math display = "inline"> L</math>. Let <math display = "inline"> \mu(L) = \text{max}_{x \in \mathbb{R}^n } d(x, L) </math> denote the covering radius of <math display = "inline"> L </math>. In this notation, the lower bound mentioned in the introduction to this section states that <math display = "inline"> \mu(L) \geq \frac{1}{2 \lambda_1(L^*)} </math>. {{math theorem |'''Theorem (Banaszczyk)'''<ref name="Banaszczyk 1993 pp. 625–635">{{cite journal | last=Banaszczyk | first=W. | title=New bounds in some transference theorems in the geometry of numbers | journal=Mathematische Annalen | publisher=Springer Science and Business Media LLC | volume=296 | issue=1 | year=1993 | issn=0025-5831 | doi=10.1007/bf01445125 | pages=625–635| s2cid=13921988 }}</ref> |For a lattice <math display = "inline"> L</math>: *:<math> 1 \leq 2 \lambda_1(L) \mu(L^*) \leq n </math> *:<math> 1 \leq \lambda_i(L) \lambda_{n - i + 1}(L^*) \leq n </math> }} 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 <math display="inline"> \lambda_1(L) \geq \frac{1}{\lambda_n(L^*)} </math>, 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 [[Lattice problem#GapSVP|<math display = "inline"> \text{GAPSVP}_n </math> problem]]) is in <math display = "inline"> \text{NP} \cap \text{coNP} </math>.<ref>{{cite journal | last1 = Cai | first1 = Jin-Yi | last2 = Nerurkar | first2 = Ajay | doi = 10.1016/S0020-0190(00)00123-X | issue = 1-2 | journal = Information Processing Letters | mr = 1797563 | pages = 61–66 | title = A note on the non-NP-hardness of approximate lattice problems under general Cook reductions | volume = 76 | year = 2000}}</ref> Other transference theorems: * The relationship <math display = "inline"> \lambda_1(L) \lambda_1(L^*) \leq n </math> follows from [[Minkowski's theorem#Bounding the shortest vector|Minkowski's bound on the shortest vector]]; that is, <math display = "inline"> \lambda_1(L) \leq \sqrt{n} (\text{det}(L)^{1/n}) </math>, and <math display = "inline"> \lambda_1(L^*) \leq \sqrt{n} (\text{det}(L^*)^{1/n}) </math>, from which the claim follows since <math display = "inline"> \text{det}(L) = \frac{1}{\text{det}(L^*)} </math>. ==Poisson summation formula== The dual lattice is used in the statement of a general Poisson summation formula. {{math theorem| '''Theorem (Poisson Summation)'''<ref name="Cohn Kumar Reiher Schürmann 2013">{{cite book | last1=Cohn | first1=Henry | last2=Kumar | first2=Abhinav | last3=Reiher | first3=Christian | last4=Schürmann | first4=Achill | title=Discrete Geometry and Algebraic Combinatorics | chapter=Formal duality and generalizations of the Poisson summation formula | series=Contemporary Mathematics | year=2014 | volume=625 | pages=123–140 | doi=10.1090/conm/625/12495 | isbn=9781470409050 | s2cid=117741906 | arxiv=1306.6796v2 }}</ref> Let <math display = "inline"> f : \mathbb{R}^n \to \mathbb{R} </math> be a [[Pathological (mathematics)|well-behaved]] function, such as a Schwartz function, and let <math display = "inline"> \hat{f} </math> denote its [[Fourier transform]]. Let <math display = "inline"> L \subseteq \mathbb{R}^n </math> be a full rank lattice. Then: :<math> \sum_{x \in L} f(x) = \frac{1}{\det(L)} \sum_{y \in L^*} \hat{f}(y) </math>. }} <!--- let's get a text reference in here, also state more general conditions ---> ==Further reading== * {{cite book | last=Ebeling | first=Wolfgang | title=Advanced Lectures in Mathematics | chapter=Lattices and Codes | publisher=Springer Fachmedien Wiesbaden | location=Wiesbaden | year=2013 | isbn=978-3-658-00359-3 | issn=0932-7134 | doi=10.1007/978-3-658-00360-9}} <!--- {{sfn | Ebeling | 2013 | p=}} ---> ==References== {{reflist}} [[Category:Lattice theory]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:For
(
edit
)
Template:Group theory sidebar
(
edit
)
Template:Math theorem
(
edit
)
Template:Reflist
(
edit
)
Template:Short description
(
edit
)