La conjetura de Kepler, un problema de optimización del siglo XVII con aplicaciones en el siglo XXI Adolfo Quirós Gracián Departamento de Matemáticas Universidad Autónoma de Madrid [email protected] Getfe, 10-4-2012

EL PROBLEMA •  Se quiere llenar una caja con esferas idénticas (por ejemplo naranjas). •  ¿Cómo hacerlo para que la parte de la caja que queda vacía sea lo menor posible? •  ¿Cómo meter en la caja la mayor cantidad posible de naranjas?

«Le necesitamos. Podemos colocar las naranjas, pero tenemos problemas con las alcachofas.» Mensaje de los agricultores de Ann Arbor a Thomas C. Hales

La mejor solución es la de los fruteros

Solución de los fruteros = empaquetamiento cúbico compacto

ClNa+

Fig. 5.9 Estructura cristalina del cloruro sódico, que corresponde a un empaquetamiento cúbico compacto de aniones.

Traducción del problema a jerga matemática Naranja = Esfera de radio 1 Manera de llenar la caja = Empaquetamiento de esferas Volumen de (todas) las naranjas/Volumen de la caja = Densidad del empaquetamiento El problema = Encontrar un empaquetamiento de densidad máxima (Se puede hacer en cualquier dimensión)

Para simplificar, la caja va a ser “todo el espacio” Modificación técnica, ¡NO LEER! •  Si queremos llenar todo el espacio (R3) de naranjas (esferas de radio 1) •  Llenamos todo y miramos las naranjas que han caido en una caja esférica de radio r (= Bola cerrada de radio r, B(0,r)). •  Tenemos un empaquetamiento de B(0,r), que tendrá densidad d(r) •  La densidad del empaquetamiento de R3 es lim r!" d(r)

Ejemplos Dimensión 2 (R2 )

Dimensión 3 (R3 )

Densidad = #/4$78% Densidad = (4#/3)/8$52%

Densidad = #/2%3$90% Densidad = #/%18$74%

CONJETURA DE KEPLER La densidad del cualquier empaquetamiento es

# " ! 0,7404 18

= densidad del empaquetamiento de los fruteros

Esto lo afirmó Kepler en 1611 y lo ha demostrado Thomas Hales (con Samuel Ferguson) en ¿1998?, ¿2005?

¿A quién le importa? David Hilbert lo menciona al proponer sus 23 «Futuros Problemas de Matemáticas» (2º ICM, Paris, 1900): 18. Teselar el espacio con poliedros [...] Señalo la siguiente cuestión, relacionado con la anterior, importante en teoría de números y quizás útil en física y química: Cómo distribuir en el espacio, del modo más denso, un número infinito de sólidos con una misma forma dada, por ejemplo, esferas de un cierto radio, o tetraedros regulares con lados dados, es decir, ¿cómo organizarlos de manera que la razón entre el volumen que ocupan y el libre sea lo mayor posible? Phillip Griffiths lo destaca en Mathematics at the Turn of the Millenium (American Mathematical Monthly, Enero 2000. Gaceta de la RSME, v. 3, nº 1, Enero-abril 2000) como uno de los más interesantes logros de las Matemáticas del siglo XX. El otro ejemplo que da es el Último Teorema de Fermat.

Aplicaciones • Cómo se empaquetan los átomos determina cómo pueden crecer los cristales. • Conseguir buenos empaquetamientos [en dimensiones superiores] permite aumentar la capacidad de transmitir información [teléfono, internet…] • Los análogos digitales [usando 0 y 1] de los buenos empaquetamientos están detrás de los códigos correctores de errores que hacen que suene bien un CD aunque se raye.

Un problema parecido: El problema del recubrimiento •  ¿Cuál es la manera más eficaz de distribuir esferas de manera que cubran todo el espacio? •  Ejemplo, en dimensión 2

•  Obviamente las esferas tienen que solaparse

Una aplicación del problema del recubrimiento •  ¿Cómo distribuir las antenas de telefonía móvil para que haya siempre cobertura? [Hay una antena en el centro de cada círculo.]

•  Generalización: ¿y si siempre debemos tener cobertura de al menos 2 [ó 3, ó 4, ó…] antenas?

Una aplicación (¿no muy útil?) de un análogo del problema del recubrimiento •  Análogo del problema del recubrimiento sobre un alfabeto de tres letras [1,X,2]: si la quiniela tiene n partidos, ¿cuántas columnas hay que completar para estar seguros de acertar (al menos) n-1 resultados? •  El número mínimo se llama K3(n,1) •  Se conoce la respuesta para n=(1,) 2, 3, 4, 5, 13, 40 , 121 , 364 n=2: 32=9 posibles quinielas, K3(2,1)=3 n=3: 33=27 posibles quinielas, K3(3,1)=5 n=13: 313=1.594.323 posibles quinielas, K3(13,1)=310=59.049 •  No se conoce para n=6,…,12;

65!K3(6,1) !73

•  (2009, J. Linderoth-F. Margot-G. Thain)

71!K3(6,1) !73

¿Qué es una conjetura? DRAE: conjetura. (Del lat. coniect"ra). 1. f. Juicio que se forma de las cosas o acaecimientos por indicios y observaciones.

Una parte importante de la investigación en matemáticas consiste en: 1.  Plantear[se] conjeturas interesantes. 2.  Demostrarlas o refutarlas.

¿Demostrar o refutar? L. Carleson (Premio Abel 2006): ¿Converge en casi todo punto la serie de Fourier de una función de L2? «La gran autoridad en esos días era Zygmund y él estaba completamente convencido de que lo que uno tenía que obtener no era una prueba sino un contraejemplo. Cuando yo era un joven estudiante en Estados Unidos, tenía una idea de cómo producir unas funciones muy complicadas para un contraejemplo, encontré a Zygmund y él me animó a hacerlo. Estuve pensando durante unos quince años por aquí y por allá sobre cómo hacer que esos contraejemplos funcionasen y la cosa interesante que sucedió fue que me di cuenta por qué debía haber un contraejemplo y cómo había que construirlo. Pensé que ya había comprendido cuál era la base y entonces para mi sorpresa pude probar que ese contraejemplo “correcto” no podía existir y de repente me di cuenta de que había que intentar lo contrario, había que intentar probar lo que no estaba de moda, es decir, probar la convergencia. El aspecto más importante al resolver un problema matemático es la convicción de cuál es el resultado verdadero. Entonces me llevó dos o tres años, usando las técnicas que habían sido desarrolladas en los veinte años anteriores»

Un Poco de Historia (1) FINALES DEL S. XVI: Sir Walter Raleigh pregunta a Thomas Harriot cómo calcular cuántas balas de cañón se pueden apilar en la cubierta de un barco. Harriot no tiene dificultad en hacerlo, pero no sabe si la manera en que lo hacen los artilleros es óptima. Pregunta a Kepler.

1611: Kepler escribe en El copo de nieve de seis esquinas que, haciendo como los artilleros, «el empaquetamiento será el más apretado posible». ¡SIN DEMOSTRACIÓN!

Un Poco de Historia (2) 1831: Gauss define Retículo [=Red]. Empaquetamiento Reticular = los centros de las esferas forman un retículo. EJEMPLO 1: en R2, el retículo (empaquetamiento) hexagonal

Un Poco de Historia (3) EJEMPLO 2: en R3, el empaquetamiento cúbico compacto (=empaquetamiento de los fruteros o de los artilleros)

$ & % &' $ & % &'

!

(

& x,y,z" Z 3|x+y + z#0mod2 ) = &*

x,y,z" Z 3|x+y + z es par

( & ) &*

Un Poco de Historia (4) 1831: Gauss demuestra que estos dos son los empaquetamientos reticulares más densos en R2 y en R3. ¿Y los empaquetamientos no reticulares? 1892: Thue prueba que ningún empaquetamiento no reticular puede mejorar al hexagonal en R2. (Demostraciones alternativas: Fejes-Toth, 1940. RogersHales, 1998). ¿Y en R3?

Un Poco de Historia (5) 1958: Rogers: máxima densidad de un empaquetamiento en R3 & 0,7796... 1986: Lindsey: ...& 0,7784... 1988: Muder: ...& 0,7783... 1993: Muder: ...& 0,7731... RECORDEMOS: Kepler: ...& 0,7404... 1953: L. Fejes-Tóth reduce la prueba de la Conjetura de Kepler a un enorme cálculo que involucra muchos casos específicos. En 1964 sugiere cómo resolverlos con un ordenador.

Un Poco de Historia (6) Rogers (1958): «La Conjetura de Kepler es un resultado que muchos matemáticos creen y todos los físicos saben.» Milnor (1974): «La situación es escandalosa.» En dimensión n ' 4 todavía hoy no se sabe cuál es la máxima densidad de un empaquetamiento arbitrario, aunque para n & 8 sí se conoce la máxima densidad de empaquetamientos reticulares. [La solución se conoce “casi” también para n=24 (Cohn Kumar, 2004) gracias al retículo de Leech.]

PRIMERA DIFICULTAD Cuidado con hacer demasiadas analogías con dimensiones bajas. ¿Está la bola naranja dentro del cubo negro? (-1,1)

(1,1)

(0,0)

(-1,-1)

(1,-1)

¡Dimensiones más altas! En dimensión n, dentro del “cuadrado” negro,siempre de lado 4, hay 2n bolas verdes, de radio 1, con centros en (±1,.., ±1). Las distancias de estos puntos a C:=(0,…,0) es, por Pitágoras

(±1)

2

( )

+ ... + ±1

2

=

n

Luego el radio de la bola naranja es #n - 1. !

¡Si n>9 este radio supera el (semi)lado del “cuadrado”! (±1,.., ±1)

(±1,.., ±1)

C:=(0,…,0) (±1,.., ±1)

(±1,.., ±1)

SEGUNDA DIFICULTAD

En R3 hay empaquetamientos no reticulares tan densos como el empaquetamiento cúbico compacto En dimensión 1.000 los mejores empaquetamientos conocidos no son reticulares.

Empaquetamientos en R3 Empezamos con el empaquetamiento hexagonal en R2, y luego añadimos naranjas en las posiciones b o c. a

a b

a b

b

a

c

c a

a

a

a b

b c

c

a b

b

a b

c a

c

c a

b c

c a

a

c a

a

b

b

b

a

a

a

Si apilamos de acuerdo con la secuencia abcabcabc... [ó acbacbacb..., que es equivalente], obtenemos el empaquetamiento cúbico compacto a

FCa2+

b

Zn2+ S2-

Fig. 5.10. Estructura cristalina de: (a) fluorita, 8b) blenda de zinc. En el primer caso todos los huecos octaédricos de la estructura cúbica compacta están ocupados (por aniones), mientras que en el segundo caso sólo la mitad de los huecos tetraédricos están ocupados.

Si apilamos de acuerdo con la secuencia abababab... obtenemos el empaquetamiento hexagonal compacto, que no es reticular (es unión de retículos).

Hueco octaédrico

a

b

Hueco tetraédrico

c

Fig. 5.12 Estructura hexagonal compacta (a). En las figuras b y c se muestran los planos con huecos octaédricos y tetraédricos, respectivamente, de la semicelda que se encuentra por encima del plano ecuatorial. Otros planos idénticos existen en la semicelda inferior. En la figura c las flechas muestran la coordinación de uno de los huecos tetraédricos.

Si ocupamos las posiciones a, b, c de manera aleatoria, obtenemos un empaquetamiento aleatorio de la misma densidad.

TERCERA DIFICULTAD LO LOCAL NO SE COMPORTA IGUAL QUE LO GLOBAL Celda de Voronoi de una esfera en un grupo de esferas = {puntos que están más cerca de su centro que de las otras esferas del grupo}

Georgy Feodosevich Voronoy !"#"$"% &'"#()% *'"+",-'.)/, (1868 - 1908)

EN R2 GLOBAL: Para el empaquetamiento hexagonal, los hexágonos circunscritos.

LOCAL: las circunferencias que rodean a una dada

Celda local = Celda global

EN R3 GLOBAL: Para el empaquetamiento cúbico compacto, dodecaedros rómbicos.

LOCAL: a una esfera la rodean 12, que se pueden situar en los vértices de un icosaedro. (Problema de las 13 esferas, Newton – Gregory, (1694)

La celda de Voronoi local es un dodecaedro regular. La celda local no tesela el espacio Celda local ) Celda global

La demostración de Rogers - Hales en R2 Radio inscrito = 1 Radio circunscrito = 2/%3

Densidad del empaquetamiento hexagonal =

área círculo verde " = # 0, 9069 área hexágono 2 3

Hay que ver que cualquier otro empaquetamiento tiene densidad mayor. ! IDEA CLAVE: densidad global & máximo de las densidades locales.

Dado un empaquetamiento cualquiera (círculos de radio 1) …

…rodeamos cada círculo con el de radio 2/%3

Cuando se cortan dos círculos azules construimos triángulos

¡3 círculos azules no se cortan nunca! lado 2

El plano se divide en tres tipos de regiones. En cada una medimos la densidad de círculos verdes 1.  Lo que no está en ningún círculo azul: densidad 0 2.  Lo que está en un círculo azul, pero no en un triángulo: densidad ! #/(4#/3) = 3/4 = 0.75 ! #/2%3

3. Lo que está dentro de un triángulo.

¡Esta transformación cambia las áreas, pero no sus cocientes!: Densidad !

= #/2%3

Brevísimo esquema de la demostración de Hales (y Ferguson) en R3 (1) 1.  Se da una estructura [«topología»] al conjunto de todos los grupos de N esferas (N no es fijo) y se intenta demostrar que el volumen mínimo de las celdas de Voronoi se alcanza para los dodecaedros rómbicos. 2.  La estructura del «espacio de grupos de esferas» es demasiado complicada para minimizar directamente sobre él. Pero se puede asociar a cada grupo de esferas un grafo plano y demostrar que las cotas buscadas dependen sólo de la estructura combinatoria de los grafos.

Brevísimo esquema de la demostración de Hales (y Ferguson) en R3 (2) 3. En la mayoría de los casos estas cotas están por encima del volumen del dodecaedro rómbico, y no hay problema. Los casos en los que SI hay problema se encuentran mediante una búsqueda con ordenador, resultando una lista de unos 5.000 grafos planos. 4. Se analizan estos 5.000 casos individualmente (hay uno especialmente difícil: Tesis Doctoral de Ferguson). Parte de cada problema es no lineal, pero manejable. El grueso del cálculo son problemas de optimización lineal en ~200 variables con ~2.000 restricciones. Hay que resolver ~10.000 de estos problemas.

¿1998? , ¿2005? (1) En 1998 Thomas Hales presentó el trabajo a Annals of Mathematics para su publicación. HALES: «La prueba es larga (282 páginas) y cada aspecto se basa en un cálculo con ordenador todavía más largo.» La demostración incluye 3Gb de archivos de ordenador. Annals asignó un equipo de 12 referees para estudiarlo. Al parecer Annals quería cambiar su política sobre publicación de pruebas asistidas por ordenador.

¿1998?, ¿2005?(2) En enero de 2003, mientras recibía el premio Chauvenet de la MAA, Hales leyó una carta de Robert MacPherson, editor jefe de Annals of Mathematics: «Las noticias de referees son malas….No han sido capaces de certificar que la demostración sea correcta, y no podrán certificarlo en el futuro, puesto que se les ha agotado la energía…. Se podría especular acerca de si el proceso habría convergido a una respuesta concluyente si hubiesen dispuesto desde el principio de un manuscrito más claro, pero eso ya no importa.»

¿1998? , ¿2005?(3) El coordinador de los referees, G. Fejes-Tóth había dicho que estaban seguros al 99% de la corrección de la demostración; que todo lo que habían mirado funcionaba como Hales decía, pero tras 4 años de trabajo no tenían fuerzas para seguir. Alguien ha señalado: «La demostración de Wiles del Último Teorema de Fermat se parece a “Guerra y Paz”, pero la demostración de Hales se parece a la guía telefónica.» Annals proponía publicar el trabajo con una nota diciendo que no se podía garantizar la corrección al 100%. A Hales no le gustó la idea.

¿1998? , ¿2005?(4) Finalmente un nuevo referee consiguió que Hales retocase el manuscrito, y Annals of Mathematics ha publicado la parte teórica, sin notas “explicativas”. Hales, T. C. A proof of the Kepler conjecture. Ann. Of Math (2) 162 (2005), no. 3, 1065-1185.

La parte “de ordenador” ha aparecido en Discrete and Computational Geometry Fejes-Tóth, G.;Lagarias, J.C. Guest editors' foreword [The Kepler conjecture by Thomas C. Hales, with Samuel P. Ferguson]. Discrete Comput. Geom. 36 (2006), no. 1, 1-3. Hales, T. C. Historical overview of the Kepler conjecture. Discrete Comput. Geom. 36 (2006), no. 1, 5-20. Hales, T. C. Ferguson, S. P. A formulation of the Kepler conjecture. Discrete Comput. Geom. 36 (2006), no. 1, 21-69. Hales, T. C. Sphere packings. III. Extremal cases. Discrete Comput. Geom. 36 (2006), no. 1, 71-110. Hales, T. C. Sphere packings. IV. Detailed bounds. Discrete Comput. Geom. 36 (2006), no. 1, 111-166. Ferguson, S. P. Sphere packings. V. Pentahedral prisms. Discrete Comput. Geom. 36 (2006), no. 1, 167--204. Hales, T. C. Sphere packings. VI. Tame graphs and linear programs. Discrete Comput. Geom. 36 (2006), no. 1, 205-265. [Sphere Packings I y II habían aparecido en 1997 también en Discrete and Computational Geometry]

Sobre las demostraciones con ordenador G. H. Hardy: «No queremos muchas “variaciones” en la demostración de un teorema matemático, pues la “enumeración de casos” es una de las formas más aburridas de razonamiento matemático. Una demostración matemática debe parecerse a una constelación simple y claramente delimitada y no a un grupo disperso en la Vía Láctea.» Pierre Deligne: «I believe in a proof if I understand it.» ¿Son las demostraciones basadas en el uso de un ordenador para tratar numerosos casos individuales auténticas demostraciones matemáticas? !

[Nueva] política de los editores de Annals of Mathematics sobre demostraciones que utilizan ordenadores: •  Las demostraciones de teoremas de excepcional importancia matemática que utilicen ordenadores serán tomadas en consideración por Annals. •  La parte humana de la demostración, que reduce el problema matemático inicial a uno tratable por un ordenador, será sometida al proceso habitual. La parte computacional puede no ser comprobada línea a línea, pero se examinara cómo el autor a minimizado o eliminado posibles fuentes de error […]. •  Publicaremos la parte humana del artículo en un número de Annals. El autor proporcionara el código de ordenador, documentación para entenderla, y el resultado de los cálculos, todo lo cuál estará disponible en el sitio web de Annals of Mathematics.

Hales está intentando organizar un proyecto , Flyspeck (FPK=Formal Proof of Kepler), para hacer una comprobación con ordenador de su demostración.

¿Qué más ha hecho Hales durante este tiempo? Demostrar (1999) la “Conjetura de la Colmena”: los hexágonos regulares proporcionan la manera de dividir el plano en regiones de área 1 con el menor perímetro.

•  Esto ya lo había “demostrado” Pappus de Alejandría (290-350). •  Pero partía de la hipótesis de que a las abejas no les gustan las figuras irregulares. •  La demostración de Pappus (y un poco más) la pueden hacer los alumnos. •  En 1943 L. Fejes-Tóth había probado la Conjetura de la Colmena bajo la hipótesis de que todas las regiones son polígonos convexos. •  De nuevo, una dificultad es la diferencia “local-global” o, si se prefiere, “caso finito-caso infinito”.

Soluciones locales

El “problema de la colmena real”

Colmena de abeja

Solución mejor: L. Fejes-Tóth (1964)

¡No se conoce la solución óptima!

Más cosas de Hales… También demostró (1998), con un estudiante de grado, Sean McLaughlin, la Conjetura del Dodecahedro: el volumen de la celda de Voronoi de una esfera en un empaquetamiento de esferas es al menos el volumen de un dodecaedro regular de inradio 1. McLaughlin obtuvo por esto el Premio Morgan de la AMS en 1999, pero el artículo con el resultado, que utiliza ideas similares a las de la demostración de la Conjetura de Kepler no apareció hasta 2010

18 páginas de diagramas de Voronoi

152 páginas con un ejemplo de programación lineal

Kepler y Hales

¡Muchas gracias por vuestra atención!