Retícula dual

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

Las redes duales tienen numerosas aplicaciones en la teoría de retículos, la informática teórica, la criptografía y las matemáticas en general. Por ejemplo, se utilizan en el enunciado de la fórmula de sumación de Poisson , los teoremas de transferencia establecen conexiones entre la geometría de una red y la de su dual, y muchos algoritmos de retículos aprovechan la red dual.

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

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

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

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

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

A pesar de esta identificación de espacios euclidianos ambientales, cabe destacar que una retícula y su dual son tipos de objetos fundamentalmente diferentes; una consiste en vectores en el espacio euclidiano y la otra en un conjunto de funcionales lineales sobre ese espacio. En este sentido, también se puede dar una definición más abstracta como la siguiente:

${\displaystyle L^{*}=\{f:L\to \mathbb {Z} :f{\text{ es una función lineal}}\}={\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:${\textstyle f\cdot g=\sum _{i}f(e_{i})g(e_{i})}$, dónde${\textstyle e_{i}}$es una base ortonormal de${\textstyle {\text{span}}(L)}$. (De forma equivalente, se puede afirmar que, para una base ortonormal ${\textstyle e_{i}}$de ${\textstyle {\text{span}}(L)}$, los vectores duales${\textstyle e_{i}^{*}}$, definido por ${\textstyle e_{i}^{*}(e_{j})=\delta _{ij}}$son una base ortonormal.) Uno de los usos clave de la dualidad en la teoría de retículos es la relación de la geometría del retículo primal 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 es generalmente implícito.

Enumeramos algunas propiedades elementales de la red dual:

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

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

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

Cada${\textstyle f\in L^{*}\setminus \{0\}}$particiones${\textstyle L}$de acuerdo con los conjuntos de nivel correspondientes a cada uno de los valores enteros. Opciones más pequeñas de${\textstyle f}$producir conjuntos de nivel con mayor distancia entre ellos; en particular, la distancia entre las capas es${\textstyle 1/||f||}$. Razonando de esta manera, se puede demostrar que encontrar vectores pequeños en${\textstyle L^{*}}$proporciona un límite inferior en el tamaño más grande de esferas no superpuestas que se pueden colocar alrededor de puntos de${\textstyle L}$En general, los teoremas que relacionan las propiedades de un retículo con las 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.

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

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

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

Otros teoremas de transferencia:

• La relación${\textstyle \lambda _{1}(L)\lambda _{1}(L^{*})\leq n}$se deduce de la cota de Minkowski sobre el vector más corto ; es decir,${\textstyle \lambda _{1}(L)\leq {\sqrt {n}}({\text{det}}(L)^{1/n})}$, y${\textstyle \lambda _{1}(L^{*})\leq {\sqrt {n}}({\text{det}}(L^{*})^{1/n})}$, de donde se deduce la afirmación ya que${\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-3ISSN 0932-7134​​