Teorema de Minkowski

En matemáticas, el teorema de Minkowski^[1] afirma que cualquier conjunto convexo de ℝⁿ simétrico respecto al origen y con volumen mayor que 2ⁿ contiene un punto de retículo no nulo. El teorema fue demostrado por Hermann Minkowski en 1889 y se convirtió en la base de la rama de la teoría de números llamada geometría de números.

Formulación

Supóngase que $L$ es un retículo con determinante d(L) en el espacio vectorial real de dimensión $n$ , ℝⁿ, y $S$ es un subconjunto convexo de ℝⁿ simétrico respecto el origen, es decir, que si $x$ pertenece a $S$ entonces $-x$ también pertenece a $S$ . El teorema de Minkowski declara que si el volumen de $S$ es estrictamente mayor que 2ⁿ $d(L)$ , entonces $S$ contiene al menos otro punto de la retícula además del origen. De hecho, dado que $S$ es simétrico, contendrá al menos tres puntos del retículo: el origen y $\pm x$ donde $x ∈ L \ 0$ .

Ejemplo

El ejemplo más sencillo de un retículo es el conjunto ℤⁿ de todos los puntos con coeficientes enteros; su determinante es 1. Para $n$ = 2, el teorema afirma que una figura convexa en el plano euclideo simétrica respecto el origen y con área mayor que 4 encierra al menos un punto de la retícula además del origen. La cota del área es importante: Si $S$ es el interior del cuadrado con vértices (±1, ±1) entonces S es simétrico, convexo y su área es exactamente 4, pero el único punto de la retícula que contiene es el origen. Esta observación es general para hipercubos de dimensión $n$ .

Demostración

El siguiente argumento permiter probar el teorema de Minkowski para el caso específico de $L = ℤ 2$ .

Prueba del caso ${\textstyle \mathbb {Z} ^{2}}$ :

Considérese la aplicación

f:S\to \mathbb {R} ^{2}/2L,\qquad (x,y)\mapsto (x{\bmod {2}},y{\bmod {2}})

Intuitivamente, esta aplicación corta el plano en cuadrados de 2 por 2, y luego apila los cuadrados uno encima del otro. Claramente, $f (S)$ tiene un área menor o igual a 4, porque este conjunto se encuentra dentro de un cuadrado de 2 por 2. Supóngase que introduciendo una contradicción $f$ podría ser una función inyectiva, lo que significa que las piezas de $S$ recortadas por los cuadrados se apilan sin superponerse. Debido a que $f$ conserva el área localmente, esta propiedad de no superposición haría que conservara el área para todo $S$ , por lo que el área de $f (S)$ sería la misma que la de $S$ , que es mayor que 4. Ese no es el caso, por lo que la suposición debe ser falsa: $f$ no es inyectiva, lo que significa que existen al menos dos puntos distintos $p 1, p 2$ en $S$ que $f$ asigna al mismo punto: $f (p 1) = f (p 2)$ .

Debido a la forma en que se definió $f$ , la única forma en que $f (p 1)$ puede ser igual a $f (p 2)$ es tomar $p 2$ con el fin de igualar $p 1 + (2 i, 2 j)$ para algunos enteros $i$ y $j$ , no ambos cero.

Es decir, las coordenadas de los dos puntos difieren en dos enteros pares.

Como $S$ es simétrico con respecto al origen, $- p 1$ también es un punto en $S$ . Dado que $S$ es convexo, el segmento rectilíneo entre $- p 1$ y $p 2$ se encuentra completamente en $S$ y, en particular, el punto medio de ese segmento se encuentra en $S$ . En otras palabras,

{\tfrac {1}{2}}\left(-p_{1}+p_{2}\right)={\tfrac {1}{2}}\left(-p_{1}+p_{1}+(2i,2j)\right)=(i,j)

es un punto en $S$ . Pero este punto $(i, j)$ es un punto entero y no es el origen ya que $i$ y $j$ no son ambos cero. Por lo tanto, $S$ contiene un punto entero distinto de cero.

Observaciones:

El argumento anterior prueba el teorema de que cualquier conjunto de volumen ${\textstyle >\!\det(L)}$ contiene dos puntos distintos que se diferencian por un vector reticular. Este es un caso especial del teorema de Blichfeldt.^[2]
El argumento anterior destaca que el término ${\textstyle 2^{n}\det(L)}$ es el covolumen de la retícula ${\textstyle 2L}$ .
Para obtener una demostración para redes generales, basta probar el teorema de Minkowski solo para ${\textstyle \mathbb {Z} ^{n}}$ ; esto se debe a que cada retícula de rango completo se puede escribir como ${\textstyle B\mathbb {Z} ^{n}}$ para alguna aplicación lineal ${\textstyle B}$ , y las propiedades de ser convexo y simétrico con respecto al origen se conservan mediante transformaciones lineales, mientras que el covolumen de ${\textstyle B\mathbb {Z} ^{n}}$ es ${\textstyle |\!\det(B)|}$ y el volumen de un cuerpo escalado exactamente por ${\textstyle {\frac {1}{\det(B)}}}$ bajo una aplicación de ${\textstyle B^{-1}}$ .

Aplicaciones

Acotación del vector más corto

El teorema de Minkowski da un límite superior para la longitud del vector distinto de cero más corto. Este resultado tiene aplicaciones en criptografía de celosía y teoría de números.

Teorema (cota de Minkowski en el vector más corto): Sea ${\textstyle L}$ una red. Luego hay un ${\textstyle x\in L\setminus \{0\}}$ con ${\textstyle \|x\|_{\infty }\leq \left|\det(L)\right|^{1/n}}$ . En particular, por la comparación estándar entre las normas ${\textstyle l_{2}}$ y ${\textstyle l_{\infty }}$ , ${\textstyle \|x\|_{2}\leq {\sqrt {n}}\,\left|\det(L)\right|^{1/n}}$ .

Demostración
Sea ${\textstyle l=\min\{\\|x\\|_{\infty }:x\in L\setminus \{0\}\}}$ y establézcase que ${\textstyle C=\{y:\\|y\\|_{\infty }<l\}}$ . Entonces ${\textstyle {\text{vol}}(C)=(2l)^{n}}$ . Si ${\textstyle (2l)^{n}>2^{n}\|d(L)\|}$ , entonces ${\textstyle C}$ contiene un punto reticular distinto de cero, lo cual es una contradicción. De este modo ${\textstyle l\leq \|d(L)\|^{1/n}}$ . Q.E.D.

Observaciones:

La constante en el límite ${\textstyle L^{2}}$ se puede mejorar, por ejemplo, tomando la bola abierta de radio ${\textstyle <l}$ como ${\textstyle C}$ en el argumento anterior. La constante óptima se conoce como constante de Hermite.
La cota dada por el teorema puede ser muy flexible, como se puede ver al considerar la red generada por ${\textstyle (1,0),(0,n)}$ .
Aunque el teorema de Minkowski garantiza un vector reticular corto dentro de un cierto límite de magnitud, encontrar este vector es en general un problema computacional difícil. Encontrar el vector dentro de un factor garantizado por el límite de Minkowski es denominado el Problema vectorial de Minkowski (MVP),^[3] y se sabe que la aproximación SVP se reduce a él usando una retícula dual y sus propiedades de transferencia. El problema computacional también se conoce a veces como HermiteSVP.^[4]
El algoritmo de reducción de bases LLL puede verse como una versión algorítmica débil pero eficiente del límite de Minkowski en el vector más corto. Esto se debe a que una ${\textstyle \delta }$ de base reducida ${\textstyle b_{1},\ldots ,b_{n}}$ -LLL para ${\textstyle L}$ tiene la propiedad de que ${\textstyle \|b_{1}\|\leq \left({\frac {1}{\delta -.25}}\right)^{\frac {n-1}{4}}\det(L)^{1/n}}$ ; pueden consultarse estas notas de la conferencia de Micciancio para obtener más información al respecto. Como se explica en el texto titulado The LLL Algorithm^[4] las pruebas de límites en la constante de Hermite contienen algunas de las ideas clave del algoritmo de reducción LLL.

Aplicaciones a la teoría de números

Números primos que son sumas de dos cuadrados

Una implicación difícil del teorema de Fermat sobre la suma de dos cuadrados se puede probar utilizando el límite de Minkowski en el vector más corto.

Teorema: Todo número primo con ${\textstyle p\equiv 1\mod 4}$ se puede escribir como suma de dos cuadrados.

Demostración
Dado que ${\textstyle 4\,\|\,p-1}$ y $a$ es un residuo cuadrático módulo primo ${\textstyle p}$ si y solo si Error al representar (función desconocida «\texto»): a^{\frac{p-1}{2}}= 1~(\texto{mod}~p) (Criterio de Euler), entonces existe una raíz cuadrada de ${\textstyle -1}$ en ${\textstyle \mathbb {Z} /p\mathbb {Z} }$ ; elíjase uno y selecciónese un representante en ${\textstyle \mathbb {Z} }$ para ${\textstyle j}$ . Considérese la red ${\textstyle L}$ definida por los vectores ${\textstyle (1,j),(0,p)}$ y denótese con ${\textstyle B}$ la matriz asociada. El determinante de esta retícula es ${\textstyle p}$ , donde el límite de Minkowski permite afirmar que hay un ${\textstyle x=(x_{1},x_{2})\in \mathbb {Z} ^{2}}$ distinto de cero con ${\textstyle 0<\\|Bx\\|_{2}^{2}<2p}$ . Se tiene que ${\textstyle \\|Bx\\|^{2}=\\|(x_{1},jx_{1}+px_{2})\\|^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}}$ y se definen los enteros ${\textstyle a=x_{1},b=(jx_{1}+px_{2})}$ . El límite de Minkowski asegura que ${\textstyle 0<a^{2}+b^{2}<2p}$ , y mediante aritmética modular simple se demuestra que ${\textstyle a^{2}+b^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}=0\mod p}$ , por lo que se concluye que ${\textstyle a^{2}+b^{2}=p}$ . QED

Además, la perspectiva de la retícula brinda un enfoque computacionalmente eficiente para el teorema de Fermat sobre sumas de cuadrados:

Algoritmo
Primero, debe recordarse que encontrar cualquier vector distinto de cero con una norma menor que ${\textstyle 2p}$ en ${\textstyle L}$ , la retícula de la prueba, da una descomposición de ${\textstyle p}$ como una suma de dos cuadrados. Dichos vectores se pueden encontrar de manera eficiente, por ejemplo, utilizando el algoritmo LLL. En particular, si ${\textstyle b_{1},b_{2}}$ es una base reducida de ${\textstyle 3/4}$ -LLL, entonces, por la propiedad de que ${\textstyle \\|b_{1}\\|\leq ({\frac {1}{\delta -.25}})^{\frac {n-1}{4}}{\text{det}}(B)^{1/n}}$ , ${\textstyle \\|b_{1}\\|^{2}\leq {\sqrt {2}}p<2p}$ . Por lo tanto, al ejecutar el algoritmo de reducción de base de retícula LLL con ${\textstyle \delta =3/4}$ , se obtiene una descomposición de ${\textstyle p}$ como una suma de cuadrados. Téngase en cuenta que debido a que cada vector en ${\textstyle L}$ tiene un múltiplo normal al cuadrado de ${\textstyle p}$ , el vector devuelto por el algoritmo LLL en este caso es, de hecho, el vector más corto.

Teorema de los cuatro cuadrados de Lagrange

El teorema de Minkowski también es útil para probar el teorema de los cuatro cuadrados, que establece que todo número natural se puede escribir como la suma de los cuadrados de cuatro números naturales.

Teorema de Dirichlet sobre aproximación racional simultánea

El teorema de Minkowski se puede utilizar para demostrar Teorema de Dirichlet sobre la aproximación racional simultánea.

Teoría algebraica de números

Otra aplicación del teorema de Minkowski es el resultado de que cada clase en el grupo de clases de ideales de un cuerpo de números algebraicos $K$ contiene un ideal integral de norma que no excede un cierto límite, dependiendo de $K$ , llamado cota de Minkowski: la finitud del número de clases de un cuerpo numérico algebraico se sigue de este hecho inmediatamente.

Teoría de la complejidad

La complejidad de encontrar el punto garantizado por el teorema de Minkowski, o el teorema de Blitchfields estrechamente relacionado con él, se han estudiado desde la perspectiva de los problemas de búsqueda TFNP. En particular, se sabe que un análogo computacional del teorema de Blichfeldt, un corolario de la prueba del teorema de Minkowski, es PPP-completo.^[5] También se sabe que el análogo computacional del teorema de Minkowski está en la clase PPP, y se ha conjeturado que puede ser PPP completo.^[6]

Véase también

Referencias

↑ Jiri Matousek (2013). Lectures on Discrete Geometry. Springer Science & Business Media. pp. 17 de 486. ISBN 9781461300397. Consultado el 22 de octubre de 2022.
↑ Olds, C. D.; Lax, Anneli; Davidoff, Giuliana P. (2000). «Chapter 9: A new principle in the geometry of numbers». The Geometry of Numbers. Anneli Lax New Mathematical Library 41. Mathematical Association of America, Washington, DC. p. 120. ISBN 0-88385-643-3. MR 1817689.
↑ UCSD
↑ ^a ^b Nguyen, Phong Q. (2009). «Hermite’s Constant and Lattice Algorithms». The LLL Algorithm. Information Security and Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 19-69. ISBN 978-3-642-02294-4. ISSN 1619-7100. doi:10.1007/978-3-642-02295-1_2.
↑ «PPP-Completeness with Connections to Cryptography». Cryptology ePrint Archive: Report 2018/778. 15 de agosto de 2018. Consultado el 13 de septiembre de 2020.
↑ Ban, Frank; Jain, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad (1 de mayo de 2019). «Reductions in PPP». Information Processing Letters 145: 48-52. ISSN 0020-0190. S2CID 71715876. doi:10.1016/j.ipl.2018.12.009. Consultado el 13 de septiembre de 2020.

Bibliografía

Enrico Bombieri y Walter Gubler (2006). Heights in Diophantine Geometry. Cambridge U. P.
J. W. S. Cassels. Una Introducción a la Geometría de Números. Salmer Classics en Matemáticas, Salmer-Verlag, 1997 (reimpresión de 1959 y 1971, Salmer-Verlag ediciones).
John Horton Conway y N. J. Un. Sloane, Esfera Packings, Enrejados y Grupos, Salmer-Verlag, NY, 3.ª ed., 1998.
Hancock, Harris (1939). Development of the Minkowski Geometry of Numbers. Macmillan. (republicada en 1964 por Dover).
Hazewinkel, Michiel, ed. (2001), "Hazewinkel, Michiel, ed. (2001), «Teorema de Minkowski», Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 ."
Edmund Hlawka, Johannes Schoißengeier, Rudolf Taschner. Número geométrico y Analítico Teoría. Universitext. Salmer-Verlag, 1991.
C. G. Lekkerkerker. Geometría de Números. Wolters-Noordhoff, Holanda Del norte, Wiley. 1969.
Wolfgang M. Schmidt. Diophantine Aproximación. Notas de conferencia en Matemáticas 785. Salmer. (1980 [1996 con correcciones menores]).
Wolfgang M. Schmidt.Diophantine Aproximaciones y Diophantine ecuaciones, Notas de Conferencia en Matemáticas, Salmer Verlag, 2000.
Siegel, Carl Ludwig (1989). Lectures on the Geometry of Numbers. Springer-Verlag.
Rolf Schneider, cuerpos Convexos: el Brunn-Minkowski teoría, Cambridge Prensa Universitaria, Cambridge, 1993.
«El teorema de Minkowski». Minkowski's theorem en PlanetMath.
Stevenhagen, Peter. Anillos de número.
Malyshev, Un.V. (2001), "Malyshev, A.V. (2001), «Teorema de Minkowski», en Hazewinkel, Michiel, ed., Encyclopaedia of Mathematics (en inglés), Springer, ISBN 978-1556080104 .", en Hazewinkel, Michiel.

Datos: Q1097021

[JM-1] Jiri Matousek (2013). Lectures on Discrete Geometry. Springer Science & Business Media. pp. 17 de 486. ISBN 9781461300397. Consultado el 22 de octubre de 2022.

[2] Olds, C. D.; Lax, Anneli; Davidoff, Giuliana P. (2000). «Chapter 9: A new principle in the geometry of numbers». The Geometry of Numbers. Anneli Lax New Mathematical Library 41. Mathematical Association of America, Washington, DC. p. 120. ISBN 0-88385-643-3. MR 1817689.

[3] UCSD

[Nguyen_2009_pp._19–69-4] Nguyen, Phong Q. (2009). «Hermite’s Constant and Lattice Algorithms». The LLL Algorithm. Information Security and Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 19-69. ISBN 978-3-642-02294-4. ISSN 1619-7100. doi:10.1007/978-3-642-02295-1_2.

[Cryptology_ePrint_Archive:_Report_2018/778_2018-5] «PPP-Completeness with Connections to Cryptography». Cryptology ePrint Archive: Report 2018/778. 15 de agosto de 2018. Consultado el 13 de septiembre de 2020.

[Information_Processing_Letters_2019_pp._48–52-6] Ban, Frank; Jain, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad (1 de mayo de 2019). «Reductions in PPP». Information Processing Letters 145: 48-52. ISSN 0020-0190. S2CID 71715876. doi:10.1016/j.ipl.2018.12.009. Consultado el 13 de septiembre de 2020.

[1]

[2]

[3]

[4]

[5]

[6]