Teorema de Minkowski

ImprimirCitar

Cada convex simétrico establecido en R^n con volumen 2^n contiene un punto entero no cero

Un juego

R 2

satisfaciendo las hipótesis del teorema de Minkowski.

En matemáticas, Teorema de Minkowski es la declaración de que cada convexo establecido en $mathbb {R} ^{n}$ que es simétrico con respecto al origen y que tiene volumen mayor que $2^{n}$ contiene un punto entero no cero (que significa un punto en $mathbb{Z } ^{n}$ que no es el origen). El teorema fue probado por Hermann Minkowski en 1889 y se convirtió en la base de la rama de la teoría del número llamada la geometría de los números. Puede ser extendido de los enteros a cualquier celo $L$ y a cualquier convexo simétrico con volumen mayor que ${displaystyle 2^{n},d(L)}$ , donde ${displaystyle d(L)}$ denota el covolumen de la celosía (el valor absoluto del determinante de cualquiera de sus bases).

Formulación

Supongamos que $L$ es una red de determinante $d(L)$ en el espacio vectorial real $n$ -dimensional $ℝ n$ y $S$ es un subconjunto convexo de $ℝ n$ que es simétrica 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 n d(L)$ , entonces $S$ debe contener en menos un punto de red que no sea el origen. (Dado que el conjunto $S$ es simétrico, entonces contendría al menos tres puntos de red: el origen 0 y un par de puntos $\pm x$ , donde $x \in L 0$ .)

Ejemplo

El ejemplo más simple de una red es la red de enteros $ℤ 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 euclidiano simétrica con respecto al origen y con un área mayor que 4 encierra al menos un punto de red además del origen. El límite del área es nítido: si $S$ es el interior del cuadrado con vértices $(\pm1, \pm1)$ entonces $S$ es simétrico y convexo, y tiene área 4, pero el único punto de red que contiene es el origen. Este ejemplo, que muestra que el límite del teorema es nítido, se generaliza a hipercubos en todas las dimensiones $n$ .

Prueba

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

Prueba de la ${textstyle mathbb {Z} ^{2}}$ Caso: Considerar el mapa

{displaystyle f:Sto mathbb {R} ^{2}/2L,qquad (x,y)mapsto (x{bmod {2}},y{bmod {2}})}

Intuitivamente, este mapa 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. Asumir por una contradicción que $f$ podría ser inyectiva, lo que significa que las piezas de $S$ cortado por los cuadrados apilados de forma que no se superpongan. Debido a que $f$ preserva el área localmente, esta propiedad que no se superpone haría que preservara el área para todo $S$ , por lo que el área de $f (S)$ sería la misma como el de $S$ , que es mayor que 4. Ese no es el caso, por lo que la suposición debe ser falsa: <span class="texhtml" f no es inyectiva, lo que significa que existen al menos dos puntos distintos $p 1, p 2$ en $S$ que son asignados por $f$ 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 para $p 2$ para 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. Dado que $S$ es simétrico con respecto al origen, $- p 1$ también es un punto en $S$ . Dado que $S$ es convexo, el segmento de línea 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,

{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 demuestra el teorema que cualquier conjunto de volumen $!det(L)}" xmlns="http://www.w3.org/1998/Math/MathML">■Det()L){textstyle }det(L)}!det(L)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de95913c129d0d20f1caa2190fb8773f202d161f" style="vertical-align: -0.838ex; width:8.688ex; height:2.843ex;"/>$ contiene dos puntos distintos que difieren por un vector de celo. Este es un caso especial del teorema de Blichfeldt.
El argumento anterior pone de relieve que el término ${textstyle 2^{n}det(L)}$ es el covolumen de la celosa ${textstyle 2L}$ .
Para obtener una prueba de vestimentas generales, basta probar el teorema de Minkowski sólo para ${textstyle mathbb {Z} ^{n}}$ ; esto es porque todas las ropas de corcheo pueden ser escritas como ${textstyle Bmathbb {Z} ^{n}}$ para alguna transformación lineal ${textstyle B}$ , y las propiedades de ser convexa y simétrica sobre el origen se conservan por transformaciones lineales, mientras que el covolumen de ${textstyle Bmathbb {Z} ^{n}}$ es ${textstyle |!det(B)|}$ y volumen de una escala corporal por exactamente ${textstyle {frac {1}{det(B)}}}$ en virtud de una solicitud ${textstyle B^{-1}}$ .

Aplicaciones

Acotando el vector más corto

El teorema de Minkowski proporciona 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.

Theorem (Minkowski está ligado al vector más corto): Vamos ${textstyle L}$ Sé una celosa. Entonces hay un ${textstyle xin Lsetminus {0}}$ con ${textstyle |x|_{infty }leq left|det(L)right|^{1/n}}$ . En particular, por la comparación estándar entre ${textstyle l_{2}}$ y ${textstyle l_{infty }}$ normas, ${textstyle |x|_{2}leq {sqrt {n}},left|det(L)right|^{1/n}}$ .

Prueba

Vamos ${textstyle l=min{|x|_{infty }:xin Lsetminus {0}}}$ , y conjunto $<math alttext="{textstyle C={y:|y|_{infty }C={}Sí.:.. Sí... JUEGO JUEGO .l}{textstyle C={y:h:fnMientras, 'infty'<img alt="{textstyle C={y:|y|_{infty }$ . Entonces... ${textstyle {text{vol}}(C)=(2l)^{n}}$ . Si $2^{n}|d(L)|}" xmlns="http://www.w3.org/1998/Math/MathML">()2l)n■2nSilenciod()L)Silencio{textstyle (2l)^{n} confía2^{n}2^{n}|d(L)|}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f6b6b0b31d3af405b3d0020a2684b6ac6aeb3c05" style="vertical-align: -0.838ex; width:16.265ex; height:2.843ex;"/>$ , entonces ${textstyle C}$ contiene un punto de celo no cero, que es una contradicción. Así ${textstyle lleq |d(L)|^{1/n}}$ . Q.E.D.

Observaciones:

La constante en ${textstyle L^{2}}$ límite se puede mejorar, por ejemplo, tomando la bola abierta del radio $<math alttext="{textstyle .l{textstyle } <img alt="{textstyle$ como ${textstyle C}$ en el argumento anterior. La constante óptima se conoce como la constante hermita.
El atado dado por el teorema puede ser muy flojo, como se puede ver considerando la celosía generada por ${textstyle (1,0),(0,n)}$ .
Aunque el teorema de Minkowski garantiza un corto vector de celos dentro de un determinado límite de magnitud, encontrar este vector es en general un problema computacional duro. Encontrar el vector dentro de un factor garantizado por el límite de Minkowski se conoce como Problema Vector de Minkowski (MVP), y se sabe que la aproximación SVP se reduce a él utilizando propiedades de transferencia de la estructura dual. El problema computacional también se conoce a veces como HermiteSVP.
El algoritmo de reducción de LLL-basis se puede ver como una versión débil pero eficientemente algorítmica del límite de Minkowski en el vector más corto. Esto es porque un ${textstyle delta }$ - Base reducida ${textstyle b_{1},ldotsb_{n}}$ para ${textstyle L}$ tiene la propiedad ${textstyle |b_{1}|leq left({frac {1}{delta -.25}}right)^{frac {n-1}{4}}det(L)^{1/n}}$ ; ver estas notas de conferencias de Micciancio para más sobre esto. Como se explica en, las pruebas de límites en la constante Hermite contienen algunas de las ideas clave en el algoritmo de reducción LLL.

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 las sumas de dos cuadrados se puede demostrar usando el límite de Minkowski en el vector más corto.

Teorema: Cada primo con ${textstyle pequiv 1mod 4}$ puede ser escrito como una suma de dos cuadrados.

Prueba

Desde ${textstyle 4,|,p-1}$ y $a$ es un modulo de residuos cuadráticos ${textstyle p}$ si $a^{frac {p-1}{2}}=1~({text{mod}}~p)$ Hay una raíz cuadrada ${textstyle -1}$ dentro ${textstyle mathbb {Z} /pmathbb {Z} }$ ; elegir uno y llamar a un representante ${textstyle mathbb {Z} }$ para ello ${textstyle j}$ . Considere la ropa ${textstyle L}$ definido por los vectores ${textstyle (1,j),(0,p)}$ , y dejar ${textstyle B}$ denota la matriz asociada. El determinante de esta celosa es ${textstyle p}$ , cuando el límite de Minkowski nos dice que hay un no cero ${textstyle x=(x_{1},x_{2})in mathbb {Z} ^{2}}$ con $<math alttext="{textstyle 0<|Bx|_{2}^{2}0... Bx.. 22.2p{textstyle 0 0 0 0 "Principal"<img alt="{textstyle 0<|Bx|_{2}^{2}$ . Tenemos ${textstyle |Bx|^{2}=|(x_{1},jx_{1}+px_{2})|^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}}$ y definimos los enteros ${textstyle a=x_{1},b=(jx_{1}+px_{2})}$ . El límite de Minkowski nos dice que $<math alttext="{textstyle 0<a^{2}+b^{2}0.a2+b2.2p{textstyle 0 realizadasa^{2}+b^{2}<img alt="{textstyle 0<a^{2}+b^{2}$ , y simple aritmética modular muestra que ${textstyle a^{2}+b^{2}=x_{1}^{2}+(jx_{1}+px_{2})^{2}=0mod p}$ , y así concluimos que ${textstyle a^{2}+b^{2}=p}$ . Q.E.D.

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

Algoritm
Primero, recuerde que encontrar cualquier vector no cero con norma menos que ${textstyle 2p}$ dentro ${textstyle L}$ , la celosía de la prueba, da una descomposición de ${textstyle p}$ como una suma de dos cuadrados. Estos vectores se pueden encontrar eficientemente, por ejemplo usando LLL-algorithm. En particular, si ${textstyle b_{1},b_{2}}$ es un ${textstyle 3/4}$ - LL reducida base, entonces, por la propiedad que ${textstyle \|b_{1}\|leq ({frac {1}{delta -.25}})^{frac {n-1}{4}}{text{det}}(B)^{1/n}}$ , $<math alttext="{textstyle \|b_{1}\|^{2}leq {sqrt {2}}p.. b1.. 2≤ ≤ 2p.2p{fnMicrosoft {fnK}p1}p2p}p1}p}p}<img alt="{textstyle \|b_{1}\|^{2}leq {sqrt {2}}p$ . Por lo tanto, al ejecutar el algoritmo de reducción de la base LLL-lattice con ${textstyle delta =3/4}$ , obtenemos una descomposición de ${textstyle p}$ como una suma de cuadrados. Note que porque cada vector en ${textstyle L}$ tiene norma cuadrada un múltiplo de ${textstyle p}$ , el vector devuelto por el LLL-algorithm en este caso es de hecho un vector más corto.

Algoritm

Primero, recuerde que encontrar cualquier vector no cero con norma menos que

{textstyle 2p}

dentro

{textstyle L}

, la celosía de la prueba, da una descomposición de

{textstyle p}

como una suma de dos cuadrados. Estos vectores se pueden encontrar eficientemente, por ejemplo usando LLL-algorithm. En particular, si

{textstyle b_{1},b_{2}}

es un

{textstyle 3/4}

- LL reducida base, entonces, por la propiedad que

{textstyle |b_{1}|leq ({frac {1}{delta -.25}})^{frac {n-1}{4}}{text{det}}(B)^{1/n}}

<math alttext="{textstyle |b_{1}|^{2}leq {sqrt {2}}p.. b1.. 2≤ ≤ 2p.2p{fnMicrosoft {fnK}p1}p2p}p1}p}p}<img alt="{textstyle |b_{1}|^{2}leq {sqrt {2}}p

. Por lo tanto, al ejecutar el algoritmo de reducción de la base LLL-lattice con

{textstyle delta =3/4}

, obtenemos una descomposición de

{textstyle p}

como una suma de cuadrados. Note que porque cada vector en

{textstyle L}

tiene norma cuadrada un múltiplo de

{textstyle p}

, el vector devuelto por el LLL-algorithm en este caso es de hecho un vector más corto.

Teorema de cuatro cuadras 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 la aproximación racional simultánea

El teorema de Minkowski se puede utilizar para demostrar el teorema de Dirichlet en 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 ideal de un campo numérico $K$ contiene una integral ideal 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 número algebraico campo 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 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. También se sabe que el análogo computacional del teorema de Minkowski está en la clase PPP, y se conjeturó que es PPP completo.

Contenido relacionado

Más resultados...