Doble celosía

Estructura algebraica → Teoría de grupos Teoría de grupos
Nociones básicas Subgrupo Subgrupo normal Acción grupal Grupo de cocientes Producto (semi) directo Suma directa Producto gratuito Producto de corona Homomorfismos de grupo núcleo imagen simple finito infinito continuo multiplicativo aditivo cíclico abeliano diedro nilpotente soluble Glosario de teoría de grupos Lista de temas de teoría de grupos
Grupos finitos Cyclic group Zn Symmetric group Sn Alternating group An Dihedral group Dn 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 groups Lattices Integers (${\displaystyle \mathbb {Z} }$) Free group Modular groups PSL(2, ${\displaystyle \mathbb {Z} }$) SL(2, ${\displaystyle \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) G2 F4 E6 E7 E8 Lorentz Poincaré Conformal Diffeomorphism Loop Infinite dimensional Lie group O(∞) SU(∞) Sp(∞)
Algebraic groups Linear algebraic group Reductive group Abelian variety Elliptic curve
v t e

En la teoría de retículas , la retícula dual es una construcción análoga a la de un espacio vectorial dual . En ciertos aspectos, la geometría de la retícula dual de una retícula es la recíproca de la geometría de , una perspectiva que subyace a muchos de sus usos.${\textstyle L}$${\textstyle L}$

Las redes duales tienen muchas aplicaciones en la teoría de redes, la informática teórica, la criptografía y las matemáticas en general. Por ejemplo, se utilizan en la formulación de la fórmula de suma de Poisson , los teoremas de transferencia proporcionan conexiones entre la geometría de una red y la de su dual, y muchos algoritmos de redes explotan la red dual.

Para un artículo que hace hincapié en las aplicaciones de la física y la química, consulte Red recíproca . Este artículo se centra en la noción matemática de red dual.

Sea una red, es decir, para alguna matriz .${\textstyle L\subseteq \mathbb {R} ^{n}}$${\textstyle L=B\mathbb {Z} ^{n}}$${\textstyle B}$

La red dual es el conjunto de funcionales lineales que toman valores enteros en cada punto de :${\textstyle L}$${\textstyle L}$

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

Si se identifica con el uso del producto escalar , podemos escribir Es importante restringir a los vectores en el lapso de , de lo contrario el objeto resultante no es una red .${\textstyle (\mathbb {R} ^{n})^{*}}$${\textstyle \mathbb {R} ^{n}}$${\textstyle L^{*}=\{v\in {\text{span}}(L):\forall x\in L,v\cdot x\in \mathbb {Z} \}.}$${\textstyle L}$

A pesar de esta identificación de espacios euclidianos ambientales, se debe enfatizar que una red y su dual son tipos de objetos fundamentalmente diferentes; uno consiste en vectores en el espacio euclidiano y el otro consiste en un conjunto de funcionales lineales en ese espacio. En esta línea, también se puede dar una definición más abstracta como la siguiente:

${\displaystyle L^{*}=\{f:L\to \mathbb {Z} :{\text{f is a linear function}}\}={\text{Hom}}_{\text{Ab}}(L,\mathbb {Z} ).}$

Sin embargo, observamos que el dual no se considera simplemente como un grupo abeliano abstracto de funcionales, sino que viene con un producto interno natural: , donde es una base ortonormal de . (Equivalentemente, se puede declarar que, para una base ortonormal de , los vectores duales , definidos por son una base ortonormal). Uno de los usos clave de la dualidad en la teoría de retículas es la relación de la geometría de la retícula primaria con la geometría de su dual, para lo cual necesitamos este producto interno. En la descripción concreta dada anteriormente, el producto interno en el dual está generalmente implícito.${\textstyle f\cdot g=\sum _{i}f(e_{i})g(e_{i})}$${\textstyle e_{i}}$${\textstyle {\text{span}}(L)}$${\textstyle e_{i}}$${\textstyle {\text{span}}(L)}$${\textstyle e_{i}^{*}}$${\textstyle e_{i}^{*}(e_{j})=\delta _{ij}}$

Enumeramos algunas propiedades elementales de la red dual:

• Si es una matriz que da una base para la red , entonces satisface .${\textstyle B=[b_{1},\ldots ,b_{n}]}$${\textstyle L}$${\textstyle z\in {\text{span}}(L)}$${\textstyle z\in L^{*}\iff b_{i}^{T}z\in \mathbb {Z} ,i=1,\ldots ,n\iff B^{T}z\in \mathbb {Z} ^{n}}$
• Si es una matriz que da una base para la red , entonces da una base para la red dual. Si es de rango completo da una base para la red dual: .${\textstyle B}$${\textstyle L}$${\textstyle B(B^{T}B)^{-1}}$${\textstyle L}$${\textstyle B^{-T}}$${\textstyle z\in L^{*}\iff B^{T}z\in \mathbb {Z} ^{n}\iff z\in B^{-T}\mathbb {Z} ^{n}}$
• El hecho anterior demuestra que . Esta igualdad se cumple bajo las identificaciones usuales de un espacio vectorial con su doble dual, o en el contexto donde el producto interno se ha identificado con su dual.${\textstyle (L^{*})^{*}=L}$${\textstyle \mathbb {R} ^{n}}$
• Fijemos dos retículos . Entonces, si y solo si .${\textstyle L,M}$${\textstyle L\subseteq M}$${\textstyle L^{*}\supseteq M^{*}}$
• El determinante de una red es el recíproco del determinante de su dual:${\textstyle {\text{det}}(L^{*})={\frac {1}{{\text{det}}(L)}}}$
• Si es un escalar distinto de cero, entonces .${\textstyle q}$${\textstyle (qL)^{*}={\frac {1}{q}}L^{*}}$
• Si es una matriz de rotación, entonces .${\textstyle R}$${\textstyle (RL)^{*}=RL^{*}}$
• Se dice que una red es integral si para todo . Supongamos que la red es de rango completo. Bajo la identificación del espacio euclidiano con su dual, tenemos que para redes integrales . Recordemos que, si y , entonces . De esto se sigue que para una red integral, .${\textstyle L}$${\textstyle x\cdot y\in \mathbb {Z} }$${\textstyle x,y\in L}$${\textstyle L}$${\textstyle L\subseteq L^{*}}$${\textstyle L}$${\textstyle L'\subseteq L}$${\textstyle |L/L'|<\infty }$${\textstyle {\text{det}}(L')={\text{det}}(L)|L/L'|}$${\textstyle {\text{det}}(L)^{2}=|L^{*}/L|}$
• Se dice que una red integral es unimodular si , lo que, por lo anterior, es equivalente a${\textstyle L=L^{*}}$${\textstyle {\text{det}}(L)=1.}$

Utilizando las propiedades enumeradas anteriormente, el dual de una red se puede calcular de manera eficiente, a mano o por computadora.

• El dual de es .${\textstyle \mathbb {Z} ^{n}}$${\textstyle \mathbb {Z} ^{n}}$
• El dual de es .${\textstyle 2\mathbb {Z} \oplus \mathbb {Z} }$${\textstyle {\frac {1}{2}}\mathbb {Z} \oplus \mathbb {Z} }$
• Sea la red de vectores enteros cuyas coordenadas tienen una suma par. Entonces , es decir, el dual es la red generada por los vectores enteros junto con todos los vectores s.${\textstyle L=\{x\in \mathbb {Z} ^{n}:\sum x_{i}=0\mod 2\}}$${\textstyle L^{*}=\mathbb {Z} ^{n}+({\frac {1}{2}},\ldots ,{\frac {1}{2}})}$${\textstyle 1/2}$

Cada partición se realiza de acuerdo con los conjuntos de niveles correspondientes a cada uno de los valores enteros. Las opciones más pequeñas de producen conjuntos de niveles con mayor distancia entre ellos; en particular, la distancia entre las capas es . Razonando de esta manera, se puede demostrar que encontrar vectores pequeños en proporciona un límite inferior para el tamaño más grande de esferas no superpuestas que se pueden colocar alrededor de puntos de . En general, los teoremas que relacionan las propiedades de una red con las propiedades de su dual se conocen como teoremas de transferencia. En esta sección explicamos algunos de ellos, junto con algunas consecuencias para la teoría de la complejidad.${\textstyle f\in L^{*}\setminus \{0\}}$${\textstyle L}$${\textstyle f}$${\textstyle 1/||f||}$${\textstyle L^{*}}$${\textstyle L}$

Recordemos algo de terminología: Para una red , sea la esfera de radio más pequeño que contiene un conjunto de vectores linealmente independientes de . Por ejemplo, es la longitud del vector más corto de . Sea el radio de cobertura de .${\textstyle L}$${\textstyle \lambda _{i}(L)}$${\textstyle i}$${\textstyle L}$${\textstyle \lambda _{1}(L)}$${\textstyle L}$${\textstyle \mu (L)={\text{max}}_{x\in \mathbb {R} ^{n}}d(x,L)}$${\textstyle L}$

En esta notación, el límite inferior mencionado en la introducción de esta sección establece que .${\textstyle \mu (L)\geq {\frac {1}{2\lambda _{1}(L^{*})}}}$

Siempre hay un certificado comprobable de manera eficiente para la afirmación de que una red tiene un vector corto distinto de cero, a saber, el vector mismo. Un corolario importante del teorema de transferencia de Banaszcyk es que , lo que implica que para demostrar que una red no tiene vectores cortos, se puede mostrar una base para la red dual que consiste en vectores cortos. Usando estas ideas se puede mostrar que aproximar el vector más corto de una red dentro de un factor de n (el problema ) está en . ^[2]${\textstyle \lambda _{1}(L)\geq {\frac {1}{\lambda _{n}(L^{*})}}}$${\textstyle {\text{GAPSVP}}_{n}}$${\textstyle {\text{NP}}\cap {\text{coNP}}}$

Otros teoremas de transferencia:

• La relación se sigue del límite de Minkowski en el vector más corto ; es decir, y , de donde se sigue la afirmación ya que .${\textstyle \lambda _{1}(L)\lambda _{1}(L^{*})\leq n}$${\textstyle \lambda _{1}(L)\leq {\sqrt {n}}({\text{det}}(L)^{1/n})}$${\textstyle \lambda _{1}(L^{*})\leq {\sqrt {n}}({\text{det}}(L^{*})^{1/n})}$${\textstyle {\text{det}}(L)={\frac {1}{{\text{det}}(L^{*})}}}$

La red dual se utiliza en el enunciado de una fórmula general de suma de Poisson.

• Ebeling, Wolfgang (2013). "Celosías y Códigos". Conferencias Avanzadas en Matemáticas . Wiesbaden: Springer Fachmedien Wiesbaden. doi :10.1007/978-3-658-00360-9. ISBN 978-3-658-00359-3. ISSN  0932-7134.