teorema de minkowski

Cada conjunto convexo simétrico en R^n con volumen > 2^n contiene un punto entero distinto de cero

Un conjunto en ℝ ² que satisface las hipótesis del teorema de Minkowski.

En matemáticas , el teorema de Minkowski es la afirmación de que todo conjunto convexo que es simétrico con respecto al origen y que tiene un volumen mayor que contiene un punto entero distinto de cero (es decir, un punto que no es el origen). 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 los números . Se puede extender desde los números enteros a cualquier red y a cualquier conjunto simétrico convexo con volumen mayor que , donde denota el covolumen de la red (el valor absoluto del determinante de cualquiera de sus bases). ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle L}$ ${\displaystyle 2^{n}\,d(L)}$ ${\displaystyle d(L)}$

Formulación

Supongamos que L es una red de determinante d( L ) en el espacio vectorial real n - dimensional y S es un subconjunto convexo que es simétrico con respecto al origen, lo que significa que si x está en S entonces − x también está en S . El teorema de Minkowski establece que si el volumen de S es estrictamente mayor que 2 ⁿ d( L ) , entonces S debe contener al menos un punto de la red distinto del origen. (Dado que el conjunto S es simétrico, entonces contendría al menos tres puntos de la red: el origen 0 y un par de puntos ±  x , donde x ∈ L \ 0 ). ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {R} ^{n}}$

Ejemplo

El ejemplo más simple de una red es la red de números enteros de todos los puntos con coeficientes enteros ; su determinante es 1. Para n = 2 , el teorema afirma que una figura convexa en el plano euclidiano simétrica con respecto al origen y con un área mayor que 4 encierra al menos un punto de la red además del origen. El límite del área es nítido : si S es el interior del cuadrado con vértices (±1, ±1), entonces S es simétrico y convexo, y tiene un área 4, pero el único punto de la red que contiene es el origen. Este ejemplo, que muestra que el límite del teorema es agudo, se generaliza a hipercubos en cada dimensión n . ${\displaystyle \mathbb {Z} ^{n}}$

Prueba

El siguiente argumento prueba el teorema de Minkowski para el caso específico de ${\displaystyle L=\mathbb {Z} ^{2}.}$

Prueba del caso: ${\textstyle \mathbb {Z} ^{2}}$ considere el mapa.

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

Intuitivamente, este mapa corta el avión 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. Supongamos una contradicción que f podría ser inyectiva , lo que significa que las piezas de S cortadas por los cuadrados se apilan sin superponerse. Debido a que f preserva el área localmente, esta propiedad de no superposición haría que preserve 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. Eso no es En este caso, la suposición debe ser falsa: f no es inyectiva, lo que significa que existen al menos dos puntos distintos p ₁ , p ₂ en S que son asignados por f al mismo punto: f  ( p ₁ ) = f  ( p ₂ ) .

Debido a la forma en que se definió f , la única forma en que f  ( p ₁ ) puede ser igual a f  ( p ₂ ) es que p ₂ sea igual a p ₁ + (2 i , 2 j ) para algunos números enteros i y j , no ambos cero . Es decir, las coordenadas de los dos puntos difieren en dos números enteros pares . Dado que S es simétrico con respecto al origen, − p ₁ también es un punto en S . Dado que S es convexo, el segmento de línea entre − p ₁ y p ₂ se encuentra completamente en S y, en particular, el punto medio de ese segmento se encuentra en S. En otras palabras,

${\displaystyle {\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 contiene dos puntos distintos que se diferencian por un vector reticular. Este es un caso especial del teorema de Blichfeldt . ^[1] ${\textstyle >\!\det(L)}$
• El argumento anterior destaca que el término es el covolumen de la red . ${\textstyle 2^{n}\det(L)}$ ${\textstyle 2L}$
• Para obtener una prueba para redes generales, basta demostrar el teorema de Minkowski sólo para ; esto se debe a que cada red de rango completo se puede escribir como para alguna transformació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 is y el volumen de un cuerpo escalan exactamente bajo una aplicación. de . ${\textstyle \mathbb {Z} ^{n}}$ ${\textstyle B\mathbb {Z} ^{n}}$ ${\textstyle B}$ ${\textstyle B\mathbb {Z} ^{n}}$ ${\textstyle |\!\det(B)|}$ ${\textstyle {\frac {1}{\det(B)}}}$ ${\textstyle B^{-1}}$

Aplicaciones

Delimitando el vector más corto

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

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

Prueba

Deja y fija . Entonces . Si , entonces contiene un punto de red distinto de cero, lo cual es una contradicción. De este modo . QED ${\textstyle l=\min\{\|x\|_{\infty }:x\in L\setminus \{0\}\}}$ ${\textstyle C=\{y:\|y\|_{\infty }<l\}}$ ${\textstyle {\text{vol}}(C)=(2l)^{n}}$ ${\textstyle (2l)^{n}>2^{n}|d(L)|}$ ${\textstyle C}$ ${\textstyle l\leq |d(L)|^{1/n}}$

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 . ${\textstyle L^{2}}$ ${\textstyle <l}$ ${\textstyle C}$
• La cota dada por el teorema puede ser muy vaga, como se puede ver al considerar la red generada por . Pero no se puede mejorar más en el sentido de que exista una constante global tal que exista una red dimensional que satisfaga a todos . Además, dicha red puede ser autodual. ^[2] ${\textstyle (1,0),(0,n)}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle \|x\|_{2}\geq c{\sqrt {n}}\cdot \left|\det(L)\right|^{1/n}}$ ${\displaystyle x\in L\setminus \{0\}}$
• 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 se conoce como problema del vector de Minkowski (MVP), y se sabe que la aproximación SVP se reduce utilizando las propiedades de transferencia de la red dual. El problema computacional también se denomina a veces HermiteSVP. ^[3]
• El algoritmo de reducción de base 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 base reducida -LLL tiene la propiedad de que ; consulte estas notas de conferencias de Micciancio para obtener más información sobre esto. Como se explica en ^[3] las pruebas de límites de la constante de Hermite contienen algunas de las ideas clave del algoritmo de reducción LLL. ${\textstyle \delta }$ ${\textstyle b_{1},\ldots ,b_{n}}$ ${\textstyle L}$ ${\textstyle \|b_{1}\|\leq \left({\frac {1}{\delta -.25}}\right)^{\frac {n-1}{4}}\det(L)^{1/n}}$

Aplicaciones a la teoría de números

Primos que son sumas de dos cuadrados

La difícil implicación del teorema de Fermat sobre la suma de dos cuadrados se puede demostrar utilizando la cota de Minkowski en el vector más corto.

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

Prueba

Dado que y es un residuo cuadrático módulo primo si y sólo si (Criterio de Euler) hay una raíz cuadrada de in ; Elija uno y llame a un representante . Considere la red definida por los vectores y denotemos la matriz asociada . El determinante de esta red es , de donde el límite de Minkowski nos dice que hay un valor distinto de cero con . Tenemos y definimos los números enteros . La cota de Minkowski nos dice eso , y la aritmética modular simple lo muestra , y por lo tanto concluimos que . QED ${\textstyle 4\,|\,p-1}$ $a$ ${\textstyle p}$ $a^{\frac {p-1}{2}}=1~({\text{mod}}~p)$ ${\textstyle -1}$ ${\textstyle \mathbb {Z} /p\mathbb {Z} }$ ${\textstyle \mathbb {Z} }$ ${\textstyle j}$ ${\textstyle L}$ ${\textstyle (1,j),(0,p)}$ ${\textstyle B}$ ${\textstyle p}$ ${\textstyle x=(x_{1},x_{2})\in \mathbb {Z} ^{2}}$ ${\textstyle 0<\|Bx\|_{2}^{2}<2p}$ ${\textstyle \|Bx\|^{2}=\|(x_{1},jx_{1}+px_{2})\|^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}}$ ${\textstyle a=x_{1},b=(jx_{1}+px_{2})}$ ${\textstyle 0<a^{2}+b^{2}<2p}$ ${\textstyle a^{2}+b^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}=0\mod p}$ ${\textstyle a^{2}+b^{2}=p}$

Además, la perspectiva reticular ofrece un enfoque computacionalmente eficiente del teorema de Fermat sobre sumas de cuadrados:

Teorema de los cuatro cuadrados de Lagrange

El teorema de Minkowski también es útil para demostrar el teorema de los cuatro cuadrados de Lagrange , 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 el teorema de Dirichlet en una 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 ideal de un cuerpo numérico K contiene un ideal integral de norma que no excede un cierto límite, dependiendo de K , llamado límite de Minkowski : la finitud del número de clase de un campo numérico algebraico. El campo numérico sigue inmediatamente.

Teoría de la complejidad

La complejidad de encontrar el punto garantizado por el teorema de Minkowski, o el teorema de Blichfeldt, estrechamente relacionado, se ha estudiado desde la perspectiva de los problemas de búsqueda de TFNP . En particular, se sabe que un análogo computacional del teorema de Blichfeldt, un corolario de la demostración del teorema de Minkowski, es PPP completo. ^[4] También se sabe que el análogo computacional del teorema de Minkowski está en la clase PPP, y se conjeturó que era PPP completo. ^[5]

Ver también

• conjunto de bailarines
• teorema de pick
• Teorema unitario de Dirichlet
• El segundo teorema de Minkowski
• La conjetura del volumen de Ehrhart

Otras lecturas

• Bombieri, Enrico ; Gubler, Walter (2006). Alturas en Geometría Diofántica. Prensa de la Universidad de Cambridge. ISBN 9780521712293.
• Cassels, JWS (2012) [1959]. Introducción a la geometría de los números. Clásicos en Matemáticas. Saltador. ISBN 978-3-642-62035-5.
• Conway, Juan ; Sloane, Neil JA (29 de junio de 2013) [1998]. Empaquetaduras de esferas, celosías y grupos (3ª ed.). Saltador. ISBN 978-1-4757-6568-7.
• Hancock, Harris (2005) [1939]. Desarrollo de la Geometría de Números de Minkowski . Publicaciones de Dover. ISBN 9780486446400.
• Hlawka, Edmundo ; Schoißengeier, Johannes; Taschner, Rudolf (2012) [1991]. Teoría de números geométrica y analítica. Saltador. ISBN 978-3-642-75306-0.
• Lekkerkerker, CG (2014) [1969]. Geometría de números. Elsevier. ISBN 978-1-4832-5927-7.
• Schmidt, Wolfgang M. (1980). Aproximación Diofántica . Apuntes de conferencias de matemáticas. vol. 785. Saltador. doi :10.1007/978-3-540-38645-2. ISBN 978-3-540-38645-2.([1996 con correcciones menores])
• Wolfgang M. Schmidt . Aproximaciones diofánticas y ecuaciones diofánticas , Lecture Notes in Mathematics, Springer Verlag 2000.
• Siegel, Carl Ludwig (2013) [1989]. Conferencias sobre la geometría de los números. Springer-Verlag. ISBN 9783662082874.
• Schneider, Rolf (1993). Cuerpos convexos: la teoría de Brunn-Minkowski . Prensa de la Universidad de Cambridge. ISBN 978-0-521-35220-8.

enlaces externos

• Stevenhagen, Peter. Anillos numéricos.
• Malyshev, AV (2001) [1994], "Teorema de Minkowski", Enciclopedia de Matemáticas , EMS Press
• "Geometría de números", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]

Referencias

1. Viejos, CD ; Lax, Anneli ; Davidoff, Giuliana P. (2000). "Capítulo 9: Un nuevo principio en la geometría de los números". La geometría de los números . Nueva Biblioteca Matemática Anneli Lax. vol. 41. Asociación Matemática de América, Washington, DC. pag. 120.ISBN​ 0-88385-643-3. SEÑOR  1817689.
2. Milnor, Juan; Husemoller, Dale (1973). Formas bilineales simétricas. pag. 46.doi :10.1007/978-3-642-88330-9 . ISBN 978-3-642-88332-3.
3. Nguyen, Phong Q. (2009). "Algoritmos de celosía y constante de Hermite". El algoritmo LLL . Seguridad de la Información y Criptografía. Berlín, Heidelberg: Springer Berlín Heidelberg. págs. 19–69. doi :10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN  1619-7100.
4. "PPP-integridad con conexiones a la criptografía". Archivo ePrint de criptología: Informe 2018/778 . 2018-08-15 . Consultado el 13 de septiembre de 2020 .
5. Prohibición, Frank; Jainista, Kamal; Papadimitriou, Christos H.; Psomas, Christos-Alexandros; Rubinstein, Aviad (1 de mayo de 2019). "Reducciones de PPA". Cartas de procesamiento de información . 145 : 48–52. doi :10.1016/j.ipl.2018.12.009. ISSN  0020-0190. S2CID  71715876 . Consultado el 13 de septiembre de 2020 .