Introducción
A mediados de octubre justin gilmer voló de California a Nueva York para asistir a la boda de un amigo. Mientras estaba en la costa este, visitó a su antiguo asesor, michael saks, matemático de la Universidad de Rutgers, donde Gilmer se había doctorado siete años antes.
Saks y Gilmer se pusieron al día durante el almuerzo, pero no hablaron de matemáticas. De hecho, Gilmer no había pensado seriamente en las matemáticas desde que terminó en Rutgers en 2015. Fue entonces cuando decidió que no quería una carrera académica y, en cambio, comenzó a aprender a programar por sí mismo. Mientras él y Saks comían, Gilmer le contó a su antiguo mentor sobre su trabajo en Google, donde trabaja en aprendizaje automático e inteligencia artificial.
Hacía sol el día que Gilmer visitó Rutgers. Mientras caminaba, recordó cómo en 2013 había pasado la mayor parte del año caminando por los mismos senderos del campus, pensando en un problema llamado la conjetura de unión cerrada. Había sido una fijación, aunque infructuosa: a pesar de todo su esfuerzo, Gilmer solo había logrado aprender por sí mismo por qué el problema aparentemente simple de los conjuntos de números era tan difícil de resolver.
“Creo que mucha gente piensa en el problema hasta que se convence de que entiende por qué es difícil. Probablemente pasé más tiempo en eso que la mayoría de la gente”, dijo Gilmer.
Después de su visita de octubre, sucedió algo inesperado: se le ocurrió una nueva idea. Gilmer comenzó a pensar en formas de aplicar técnicas de la teoría de la información para resolver la conjetura de unión cerrada. Persiguió la idea durante un mes, a cada paso esperando que fracasara. Pero en lugar de eso, el camino hacia una prueba seguía abriéndose. Finalmente, el 16 de noviembre publicó un resultado único en su tipo eso hace que los matemáticos avancen mucho hacia la demostración de la conjetura completa.
El documento desencadenó una serie de trabajos de seguimiento. Los matemáticos de la Universidad de Oxford, el Instituto de Tecnología de Massachusetts y el Instituto de Estudios Avanzados, entre otras instituciones, se basaron rápidamente en los métodos novedosos de Gilmer. Pero antes de que lo hicieran, hicieron una pregunta propia: ¿Quién es este tipo?
Medio lleno
La conjetura de unión cerrada se trata de conjuntos de números llamados conjuntos, como {1, 2} y {2, 3, 4}. Puede realizar operaciones en conjuntos, incluso tomar su unión, lo que significa combinarlos. Por ejemplo, la unión de {1, 2} y {2, 3, 4} es {1, 2, 3, 4}.
Una colección, o familia, de conjuntos se considera "unión cerrada" si la unión de dos conjuntos en la familia es igual a cualquier conjunto existente en la familia. Por ejemplo, considere esta familia de cuatro conjuntos:
{1}, {1, 2}, {2, 3, 4}, {1, 2, 3, 4}.
Combine cualquier par y obtendrá un conjunto que ya está en la familia, lo que hace que la unión familiar sea cerrada.
Los matemáticos hablaron sobre versiones de la conjetura de unión cerrada desde la década de 1960, pero recibió su primera declaración formal en 1979, en un artículo de peter frankl, un matemático húngaro que emigró a Japón en la década de 1980 y que cuenta con la actuación callejera entre sus actividades.
Frankl conjeturó que si una familia de conjuntos es de unión cerrada, debe tener al menos un elemento (o número) que aparezca en al menos la mitad de los conjuntos. Era un umbral natural por dos razones.
Primero, hay ejemplos fácilmente disponibles de familias cerradas por unión en las que todos los elementos aparecen exactamente en el 50% de los conjuntos. Como todos los diferentes conjuntos que puedes hacer desde los números del 1 al 10, por ejemplo. Hay 1,024 conjuntos de este tipo, que forman una familia cerrada por unión, y cada uno de los 10 elementos aparece en 512 de ellos. Y en segundo lugar, en el momento en que Frankl hizo la conjetura, nadie había producido nunca un ejemplo de una familia cerrada por unión en la que la conjetura no se cumpliera.
Así que el 50% parecía la predicción correcta.
Eso no significaba que fuera fácil de probar. En los años transcurridos desde el artículo de Frankl, ha habido pocos resultados. Antes del trabajo de Gilmer, esos documentos solo lograban establecer umbrales que variaban con el número de juegos en la familia (en lugar de ser el mismo umbral del 50 % para familias de juegos de todos los tamaños).
"Parece que debería ser fácil, y es similar a muchos problemas que son fáciles, pero ha resistido los ataques", dijo. Will Sawin de la Universidad de Columbia.
La falta de progreso reflejaba tanto la naturaleza engañosa del problema como el hecho de que muchos matemáticos preferían no pensar en ello; les preocupaba perder años de sus carreras persiguiendo un problema seductor que era imposible de resolver. Gilmer recuerda un día en 2013 cuando fue a la oficina de Saks y mencionó la conjetura de cierre del sindicato. Su asesor, que en el pasado había luchado con el problema él mismo, casi lo echa de la habitación.
“Mike dijo: 'Justin, vas a hacer que vuelva a pensar en este problema y no quiero hacer eso'”, dijo Gilmer.
Una mirada a la incertidumbre
Después de su visita a Rutgers, Gilmer le dio vueltas al problema en su mente, tratando de entender por qué era tan difícil. Se impulsó con un dato básico: si tienes una familia de 100 juegos, hay 4,950 formas diferentes de elegir dos y llevar su unión. Luego se preguntó: ¿Cómo es posible que 4,950 uniones diferentes se mapeen en solo 100 conjuntos si ningún elemento aparece en esas uniones con al menos cierta frecuencia?
Incluso en ese momento estaba en camino a una prueba, aunque todavía no lo sabía. Las técnicas de la teoría de la información, que brindan una forma rigurosa de pensar sobre qué esperar cuando sacas un par de objetos al azar, lo llevarían allí.
La teoría de la información se desarrolló en la primera mitad del siglo XX, sobre todo con el artículo de Claude Shannon de 20, “Una teoría matemática de la comunicación..” El documento proporcionó una forma precisa de calcular la cantidad de información necesaria para enviar un mensaje, en función de la cantidad de incertidumbre sobre lo que diría exactamente el mensaje. Este enlace - entre la información y la incertidumbre — fue la notable y fundamental intuición de Shannon.
Para tomar un ejemplo de juguete, imagine que tiro una moneda cinco veces y le envío la secuencia resultante. Si es una moneda normal, se necesitan cinco bits de información para transmitir. Pero si se trata de una moneda cargada, digamos, con un 99 % de probabilidades de caer en cara, se necesita mucho menos. Por ejemplo, podríamos acordar de antemano que le enviaré un 1 (un solo bit de información) si la moneda cargada sale cara las cinco veces, lo cual es muy probable que suceda. Hay más sorpresa en el resultado de un lanzamiento justo de una moneda que en uno sesgado y, por lo tanto, más información.
El mismo pensamiento se aplica a la información contenida en conjuntos de números. Si tengo una familia de conjuntos cerrados por unión, digamos los 1,024 conjuntos formados por los números del 1 al 10, podría elegir dos conjuntos al azar. Entonces podría comunicarte los elementos de cada conjunto. La cantidad de información que se necesita para enviar ese mensaje refleja la cantidad de incertidumbre en torno a cuáles son esos elementos: hay un 50% de probabilidad, por ejemplo, de que el primer elemento en el primer conjunto sea un 1 (porque 1 aparece en la mitad de los conjuntos en la familia), al igual que hay un 50% de probabilidad de que el primer resultado en una secuencia de lanzamientos de monedas justos sea cara.
La teoría de la información aparece a menudo en la combinatoria, un área de las matemáticas relacionada con el conteo de objetos, que es lo que Gilmer había estudiado como estudiante de posgrado. Pero mientras volaba de regreso a su casa en California, le preocupaba que la forma en que pensaba conectar la teoría de la información con la conjetura de la unión cerrada fuera la ingenua percepción de un aficionado: seguramente los matemáticos en activo se habían topado con este objeto brillante antes y lo reconocieron como oro de los tontos. .
“Para ser honesto, estoy un poco sorprendido de que nadie haya pensado en esto antes”, dijo Gilmer. “Pero tal vez no debería sorprenderme, porque yo mismo lo había pensado durante un año y conocía la teoría de la información”.
Más probable que no
Gilmer trabajó en el problema por la noche, después de terminar su trabajo en Google, y los fines de semana durante la segunda quincena de octubre y principios de noviembre. Le animaron las ideas que un grupo de matemáticos había explorado años antes en un colaboración abierta en el blog de un destacado matemático llamado Tim Gowers. También trabajó con un libro de texto a su lado para poder buscar fórmulas que había olvidado.
“Uno pensaría que alguien que obtiene un gran resultado no debería tener que consultar el Capítulo 2 de Elementos de la teoría de la información, pero lo hice”, dijo Gilmer.
La estrategia de Gilmer fue imaginar una familia cerrada por unión en la que ningún elemento apareciera ni siquiera en el 1% de todos los conjuntos, un contraejemplo que, si realmente existiera, falsearía la conjetura de Frankl.
Digamos que elige dos conjuntos, A y B, de esta familia al azar y considera los elementos que podrían estar en esos conjuntos, uno a la vez. Ahora pregunte: ¿Cuáles son las probabilidades de que el conjunto A contenga el número 1? ¿Y el conjunto B? Dado que cada elemento tiene un poco menos del 1% de posibilidades de aparecer en un conjunto dado, no esperaría que A o B contuvieran 1. Lo que significa que hay poca sorpresa, y poca información obtenida, si se entera de que ninguno de los dos de hecho lo hace.
Luego, piensa en la probabilidad de que la unión de A y B contenga 1. Todavía es poco probable, pero es más probable que las probabilidades de que aparezca en cualquiera de los conjuntos individuales. Es la suma de la probabilidad de que aparezca en A y la probabilidad de que aparezca en B menos la probabilidad de que aparezca en ambos. Entonces, tal vez un poco menos del 2%.
Esto sigue siendo bajo, pero está más cerca de una propuesta 50-50. Eso significa que se necesita más información para compartir el resultado. Es decir, si hay una familia cerrada por unión en la que no aparece ningún elemento en al menos el 1% de todos los conjuntos, hay más información en la unión de dos conjuntos que en cualquiera de los conjuntos en sí.
“La idea de revelar cosas elemento por elemento y mirar la cantidad de información que aprendes es extremadamente inteligente. Esa es la idea principal de la prueba”, dijo ryan alweiss de la Universidad de Princeton.
En este punto, Gilmer comenzaba a acercarse a la conjetura de Frankl. Esto se debe a que es fácil demostrar que en una familia de unión cerrada, la unión de dos conjuntos contiene necesariamente menos información que los conjuntos mismos, no más.
Para ver por qué, piensa en esa familia cerrada por unión que contiene los 1,024 conjuntos diferentes que puedes hacer con los números del 1 al 10. Si eliges dos de esos conjuntos al azar, en promedio terminarás con conjuntos que contienen cinco elementos. (De esos 1,024 conjuntos, 252 contienen cinco elementos, lo que hace que sea el tamaño de conjunto más común). También es probable que termine con una unión que contenga alrededor de siete elementos. Pero solo hay 120 formas diferentes de hacer conjuntos que contengan siete elementos.
El punto es que hay más incertidumbre sobre los contenidos de dos conjuntos elegidos al azar que sobre su unión. La unión sesga hacia conjuntos más grandes con más elementos, para los que hay menos posibilidades. Cuando tomas la unión de dos conjuntos en una familia cerrada por unión, sabes lo que vas a obtener, como cuando lanzas una moneda sesgada, lo que significa que la unión contiene menos información que los conjuntos que la componen.
Con eso, Gilmer tenía una prueba. Sabía que si ningún elemento aparece incluso en el 1% de los conjuntos, el sindicato se ve obligado a contener más información. Pero el sindicato debe contener menos información. Por tanto debe haber al menos un elemento que aparezca en al menos el 1% de los conjuntos.
El empujón a los 50
Cuando Gilmer publicó su prueba el 16 de noviembre, incluyó una nota en la que decía que pensaba que era posible usar su método para acercarse aún más a una prueba de la conjetura completa, elevando potencialmente el umbral al 38 %.
Cinco días después Tres una experiencia diferente grupos de los matemáticos publicaron documentos con horas de diferencia que se basaron en el trabajo de Gilmer para hacer precisamente eso. Adicionales papeles seguido, pero el estallido inicial parece haber llevado los métodos de Gilmer hasta el límite; llegar al 50% probablemente requerirá nuevas ideas adicionales.
Aún así, para algunos de los autores de los artículos de seguimiento, llegar al 38% fue relativamente sencillo, y se preguntaron por qué Gilmer no lo hizo él mismo. La explicación más simple resultó ser la correcta: después de más de media década fuera de las matemáticas, Gilmer simplemente no sabía cómo hacer parte del trabajo analítico técnico requerido para lograrlo.
“Estaba un poco oxidado y, para ser honesto, estaba atascado”, dijo Gilmer. “Pero estaba ansioso por ver a dónde lo llevaría la comunidad”.
Sin embargo, Gilmer piensa que las mismas circunstancias que lo dejaron fuera de la práctica probablemente hicieron posible su prueba en primer lugar.
“Es la única forma en que puedo explicar por qué pensé en el problema durante un año en la escuela de posgrado y no progresé. Dejé las matemáticas durante seis años, luego volví al problema e hice este gran avance”, dijo. "No sé cómo explicarlo, aparte de que estar en el aprendizaje automático sesgó mi pensamiento".
Corrección: Enero 3, 2023
El titular original se refería a Gilmer como un "ingeniero de Google". De hecho, es un investigador.
