Ir al contenido

Teorema de Minkowski

De Wikipedia, la enciclopedia libre
Un conjunto en ℝ2 que satisface las hipótesis del teorema de Minkowski

En matemáticas, el teorema de Minkowski[1]​ afirma que cualquier conjunto convexo de ℝn simétrico respecto al origen y con volumen mayor que 2n 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

[editar]

Supóngase que L es un retículo con determinante d(L) en el espacio vectorial real de dimensión n, ℝn, y S es un subconjunto convexo de ℝn 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 2n 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 ±x donde xL \ 0.

Ejemplo

[editar]

El ejemplo más sencillo de un retículo es el conjunto ℤn 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

[editar]

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

Prueba del caso :

Considérese la aplicación

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 p1, p2 en S que f asigna al mismo punto: f (p1) = f (p2).

Debido a la forma en que se definió f, la única forma en que f (p1) puede ser igual a f (p2) es tomar p2 con el fin de igualar p1 + (2i, 2j) 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, p1 también es un punto en S. Dado que S es convexo, el segmento rectilíneo entre p1 y p2 se encuentra completamente en S y, en particular, el punto medio de ese segmento se encuentra en S. En otras palabras,

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 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 es el covolumen de la retícula .
  • Para obtener una demostración para redes generales, basta probar el teorema de Minkowski solo para ; esto se debe a que cada retícula de rango completo se puede escribir como para alguna aplicación lineal , y las propiedades de ser convexo y simétrico con respecto al origen se conservan mediante transformaciones lineales, mientras que el covolumen de es y el volumen de un cuerpo escalado exactamente por bajo una aplicación de .

Aplicaciones

[editar]

Acotación del vector más corto

[editar]

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 una red. Luego hay un con . En particular, por la comparación estándar entre las normas y , .

Demostración
Sea y establézcase que . Entonces . Si , entonces contiene un punto reticular distinto de cero, lo cual es una contradicción. De este modo . Q.E.D.

Observaciones:

  • La constante en el límite se puede mejorar, por ejemplo, tomando la bola abierta de radio como 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 .
  • 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 de base reducida -LLL para tiene la propiedad de que ; 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

[editar]

Números primos que son sumas de dos cuadrados

[editar]

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 se puede escribir como suma de dos cuadrados.

Demostración
Dado que y es un residuo cuadrático módulo primo 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 en ; elíjase uno y selecciónese un representante en para . Considérese la red definida por los vectores y denótese con la matriz asociada. El determinante de esta retícula es , donde el límite de Minkowski permite afirmar que hay un distinto de cero con . Se tiene que y se definen los enteros . El límite de Minkowski asegura que , y mediante aritmética modular simple se demuestra que , por lo que se concluye que . 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 en , la retícula de la prueba, da una descomposición de como una suma de dos cuadrados. Dichos vectores se pueden encontrar de manera eficiente, por ejemplo, utilizando el algoritmo LLL. En particular, si es una base reducida de -LLL, entonces, por la propiedad de que , . Por lo tanto, al ejecutar el algoritmo de reducción de base de retícula LLL con , se obtiene una descomposición de como una suma de cuadrados. Téngase en cuenta que debido a que cada vector en tiene un múltiplo normal al cuadrado de , 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

[editar]

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

[editar]

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

[editar]

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

[editar]

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

[editar]

Referencias

[editar]
  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
  4. 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. 
  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. 
  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. 

Bibliografía

[editar]
  • 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.