En la teoría de las celosías , la celosía dual es una construcción análoga a la de un espacio vectorial dual. En ciertos aspectos, la geometría de la celosía dual de una celosía es el recíproco de la geometría de , una perspectiva que subyace a muchos de sus usos.
Las celosías duales tienen muchas aplicaciones dentro de la teoría de celosías, la informática teórica, la criptografía y las matemáticas en general. Por ejemplo, se utiliza en el enunciado de la fórmula de suma de Poisson , los teoremas de transferencia proporcionan conexiones entre la geometría de un retículo y la de su doble, y muchos algoritmos de retículo explotan el retículo dual.
Para obtener un artículo con énfasis en las aplicaciones de física / química, consulte Rejilla recíproca . Este artículo se centra en la noción matemática de una red dual.
Definición
Dejar ser una celosía. Es decir, para alguna matriz .
La celosía dual es el conjunto de funcionales lineales en que toman valores enteros en cada punto de :
Si se identifica con usando el producto escalar , podemos escribirEs importante restringir a los vectores en el lapso de, de lo contrario, el objeto resultante no es una celosía .
A pesar de esta identificación de los espacios ambientales euclidianos, debe enfatizarse que una celosía y su dual son tipos de objetos fundamentalmente diferentes; uno consta de vectores en el espacio euclidiano y el otro consta de un conjunto de funcionales lineales en ese espacio. En este sentido, también se puede dar una definición más abstracta de la siguiente manera:
Sin embargo, observamos que el dual no se considera solo como un grupo abeliano abstracto de funcionales, sino que viene con un producto interno natural:, dónde es una base ortonormal de. (De manera equivalente, se puede declarar que, para una base ortonormal de , los vectores duales , definido por son una base ortonormal.) Uno de los usos clave de la dualidad en la teoría de la celosía es la relación de la geometría de la celosía 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 del dual está generalmente implícito.
Propiedades
Enumeramos algunas propiedades elementales de la red dual:
- Si es una matriz que da una base para la celosía , luego satisface .
- Si es una matriz que da una base para la celosía , luego da una base para la celosía dual. Si es rango completo da una base para la celosía dual: .
- El hecho anterior muestra que . Esta igualdad se mantiene bajo las identificaciones usuales de un espacio vectorial con su doble dual, o en el escenario donde el producto interno ha identificado con su dual.
- Arreglar dos celosías . Luego si y solo si .
- El determinante de una celosía es el recíproco del determinante de su dual:
- Si es un escalar distinto de cero, entonces .
- Si es una matriz de rotación, entonces .
- Una celosía se dice que es integral si para todos . Suponga que la celosíaes rango completo. Bajo la identificación del espacio euclidiano con su dual, tenemos que para celosías integrales . Recuerde que, si y , luego . De esto se sigue que para una celosía integral,.
- Se dice que una celosía integral es unimodular si, que, por lo anterior, es equivalente a
Ejemplos de
Usando las propiedades enumeradas anteriormente, el dual de una celosía se puede calcular de manera eficiente, a mano o por computadora. Ciertas celosías con importancia en matemáticas e informática son duales entre sí, y enumeramos algunas aquí.
Ejemplos elementales
- El dual de es .
- El dual de es .
- Dejar ser la red de vectores enteros cuyas coordenadas tienen una suma par. Luego, es decir, el dual es la red generada por los vectores enteros junto con todos los s vector.
celosías q-arias
Una clase importante de ejemplos, particularmente en la criptografía de celosía, la dan las celosías q-ary. Para una matriz definimos ; estos se denominan, respectivamente, la imagen y las celosías q-arias del núcleo asociadas a. Luego, después de identificar el espacio euclidiano con su dual, tenemos que la imagen y las celosías q-arias del núcleo de una matrizson duales, hasta un escalar. En particular, y . [ cita requerida ] (La prueba se puede hacer como un ejercicio).
Teoremas de transferencia
Cada particiones según los conjuntos de niveles correspondientes a cada uno de los valores enteros. Opciones más pequeñas deproducir conjuntos de niveles con más distancia entre ellos; en particular, la distancia entre las capas es. Razonando de esta manera, se puede demostrar que encontrar pequeños vectores en proporciona un límite inferior en 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.
Recordamos algo de terminología: para una celosía , dejar denotar la bola 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 . Dejar denotar el radio de cobertura de .
En esta notación, el límite inferior mencionado en la introducción de esta sección establece que .
Teorema (Banaszcyk) [1] - Para una celosía:
Siempre existe un certificado comprobable de manera eficiente para la afirmación de que una celosía tiene un vector corto distinto de cero, es decir, el vector en sí. Un corolario importante del teorema de transferencia de Banaszcyk es que, lo que implica que para demostrar que un retículo no tiene vectores cortos, se puede mostrar una base para el retículo dual que consta de vectores cortos. Usando estas ideas, se puede demostrar que al aproximar el vector más corto de una red dentro de un factor de n (elproblema ) está en. [ cita requerida ]
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 desprende la afirmación desde .
Fórmula de suma de Poisson
El enrejado dual se usa en el enunciado de una fórmula general de suma de Poisson.
Teorema - Teorema (suma de Poisson) [2] Seaser una función de buen comportamiento , como una función de Schwartz, y dejardenotar su transformada de Fourier . Dejarser una celosía de rango completo. Luego:
- .
Otras lecturas
- 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 .
Referencias
- ^ Banaszczyk, W. (1993). "Nuevos límites en algunos teoremas de transferencia en la geometría de los números". Mathematische Annalen . Springer Science and Business Media LLC. 296 (1): 625–635. doi : 10.1007 / bf01445125 . ISSN 0025-5831 . S2CID 13921988 .
- ^ Cohn, Henry; Kumar, Abhinav; Reiher, cristiano; Schürmann, Achill (2014). Dualidad formal y generalizaciones de la fórmula de suma de Poisson . Ams Contemporary Mathematics . Matemáticas contemporáneas. 625 . págs. 123-140. arXiv : 1306.6796v2 . doi : 10.1090 / conm / 625/12495 . ISBN 9781470409050. S2CID 117741906 .