'A-Team' de matemáticas demuestra un vínculo crítico entre la suma y los conjuntos | Revista Quanta

En un conjunto de números elegidos al azar, la suma puede volverse loca.

Sume todos los pares de dicho conjunto y terminará con una nueva lista que probablemente tendrá muchos más números que los que tenía al principio. Comience con 10 números aleatorios y esta nueva lista (llamada conjunto suma) tendrá alrededor de 50 elementos. Comience con 100 y la suma probablemente tendrá alrededor de 5,000; 1,000 números iniciales aleatorios formarán una suma de 500,000 números.

Pero si su conjunto inicial tiene estructura, el conjunto total puede terminar con menos números que este. Considere otro conjunto de 10 números: todos los números pares del 2 al 20. Debido a que diferentes pares suman el mismo número (10 + 12 es lo mismo que 8 + 14 y 6 + 16), el conjunto suma tiene solo 19 números, no 50. Esta diferencia se vuelve cada vez más profunda a medida que los conjuntos se hacen más grandes. Una lista estructurada de 1,000 números podría tener un conjunto de suma con solo 2,000 números.

En la década de 1960, un matemático llamado Gregorio Freiman Comenzó a investigar conjuntos con sumas pequeñas en un esfuerzo por investigar el vínculo entre la suma y la estructura del conjunto, una conexión crucial que define el campo matemático de la combinatoria aditiva. Freiman hizo avances impresionantes, demostrando que un conjunto con una suma pequeña debe estar contenido por un conjunto más grande cuyos elementos están espaciados en un patrón muy regular. Pero luego el campo se estancó. “La prueba original de Freiman fue extraordinariamente difícil de entender, hasta el punto de que nadie estaba absolutamente seguro de que fuera correcta. Así que realmente no tuvo el impacto que podría haber tenido”, dijo Timothy Gowers, matemático del Collège de France y de la Universidad de Cambridge y medallista Fields. "Pero entonces imre ruzsa irrumpió en escena”.

En una serie de dos papeles En la década de 1990, Ruzsa volvió a demostrar el teorema de Freiman con un nuevo y elegante argumento. Unos años despues, catalina marton, un influyente matemático húngaro que murió en 2019, modificó la cuestión de qué implica una pequeña suma sobre la estructura del conjunto original. Reemplazó los tipos de elementos que aparecían en el conjunto y el tipo de estructura que los matemáticos deberían buscar, pensando que eso les permitiría extraer aún más información. La conjetura de Marton tiene vínculos con los sistemas de prueba, la teoría de la codificación y la criptografía, y ocupa un lugar destacado en la combinatoria aditiva.

Su conjetura “parece realmente una de las cosas más básicas que no entendíamos”, dijo ben verde, matemático de la Universidad de Oxford. "Simplemente sustenta muchas cosas que me importan".

Green unió fuerzas con Gowers, Freddie modales de la Universidad de California, San Diego, y terence tao, medallista Fields de la Universidad de California en Los Ángeles, para formar lo que el matemático y bloguero israelí Gil kalai llamado “Un equipo”de los matemáticos. Demostraron una versión de la conjetura en un artículo. compartido el 9 de noviembre.

Redes Katz, un matemático de la Universidad Rice que no participó en el trabajo, describe la prueba como "maravillosamente sencilla" y "más o menos completamente inesperada".

Luego, Tao inició un esfuerzo por formalizar la prueba en "Lean", un lenguaje de programación que ayuda a los matemáticos a verificar teoremas. En apenas unas semanas, ese esfuerzo tuvo éxito. La madrugada del martes 5 de diciembre de tao anunció que Lean había demostrado la conjetura sin ningún "perdón", la declaración estándar que aparece cuando la computadora no puede verificar un determinado paso. Este es el uso más destacado de este tipo de herramientas de verificación desde 2021, y marca un punto de inflexión en la forma en que los matemáticos escriben pruebas en términos que una computadora puede entender. Si estas herramientas se vuelven lo suficientemente fáciles de usar para los matemáticos, podrían sustituir el proceso de revisión por pares, a menudo prolongado y oneroso, dijo Gowers.

Los ingredientes de la prueba habían estado hirviendo a fuego lento durante décadas. Gowers concibió sus primeros pasos a principios de la década de 2000. Pero se necesitaron 20 años para demostrar lo que Kalai llamó “el santo grial” del campo.

El grupo

Para comprender la conjetura de Marton, es útil estar familiarizado con el concepto de grupo, un objeto matemático que consta de un conjunto y una operación. Piense en los números enteros (un conjunto infinito de números) y la operación de suma. Cada vez que sumas dos números enteros, obtienes otro número entero. La suma también obedece a algunas otras reglas de las operaciones grupales, como la asociatividad, que te permite cambiar el orden de las operaciones: 3 + (5 + 2) = (3 + 5) + 2.

Dentro de un grupo, a veces se pueden encontrar conjuntos más pequeños que satisfacen todas las propiedades del grupo. Por ejemplo, si sumas dos números pares, obtendrás otro número par. Los números pares son un grupo en sí mismos, lo que los convierte en un subgrupo de los números enteros. Los números impares, por el contrario, no son un subgrupo. Si sumas dos números impares, obtienes un número par, que no está en el conjunto original. Pero puedes obtener todos los números impares simplemente sumando 1 a cada número par. Un subgrupo desplazado como este se llama clase lateral. No tiene todas las propiedades de un subgrupo, pero conserva la estructura de su subgrupo de muchas maneras. Por ejemplo, al igual que los números pares, los números impares están todos espaciados uniformemente.

Marton supuso que si tienes un conjunto al que llamaremos A compuesto por elementos de grupo cuya suma no es mucho mayor que A en sí, entonces existe algún subgrupo, llámelo G — con una propiedad especial. Cambio G varias veces para hacer clases laterales, y esas clases laterales, en conjunto, contendrán el conjunto original A. Además, supuso que el número de clases laterales no crece mucho más rápido que el tamaño de la suma; creía que debería estar relacionado mediante un factor polinómico, en lugar de un crecimiento exponencial mucho más rápido.

Esto puede parecer una curiosidad muy técnica. Pero debido a que se trata de una prueba simple: ¿qué sucede cuando agregas solo dos elementos al conjunto? — para la estructura general de un subgrupo, es muy importante para los matemáticos e informáticos. La misma idea general aparece cuando los científicos informáticos intentan cifrar mensajes para que puedas decodificar sólo una parte del mensaje a la vez. También aparece en pruebas comprobables probabilísticamente, una forma de prueba que los informáticos pueden verificar comprobando sólo unos pocos fragmentos aislados de información. En cada uno de estos casos, se trabaja con solo un par de puntos en una estructura (decodificando solo unos pocos bits de un mensaje largo o verificando una pequeña porción de una prueba complicada) y se concluye algo sobre una estructura más grande y de nivel superior.

"Puedes pretender que todo es un subconjunto grande de un grupo", dijo Tom Sanders, un antiguo alumno de Gowers que ahora es colega de Green en Oxford, o puede, “obtener todo lo que quería de la existencia de muchas coincidencias aditivas. Ambas perspectivas son útiles”.

Ruza publicó la conjetura de Marton en 1999, dándole todo el crédito. “Ella llegó a esa conjetura independientemente de Freiman y yo, y probablemente antes que nosotros”, dijo. “Por eso, cuando hablé con ella, decidí llamarlo su conjetura”. Aún así, los matemáticos ahora se refieren a ella como la conjetura polinómica de Freiman-Ruzsa, o PFR.

Ceros y unos

Los grupos, como muchos objetos matemáticos, adoptan muchas formas diferentes. Marton supuso que su conjetura es cierta para todos los grupos. Esto aún no se ha demostrado. El nuevo artículo lo demuestra para un tipo particular de grupo, que toma como elementos listas de números binarios como (0, 1, 1, 1, 0). Debido a que las computadoras funcionan en binario, este grupo es crucial en informática. Pero también ha resultado útil en combinatoria aditiva. "Es como un escenario de juguete en el que puedes jugar y probar cosas", dijo Sanders. "El álgebra es mucho, mucho mejor" que trabajar con números enteros, añadió.

Las listas tienen longitudes fijas y cada bit puede ser 0 o 1. Se suman sumando cada entrada a su contraparte en otra lista, con la regla de que 1 + 1 = 0. Entonces (0, 1, 1, 1 , 0) + (1, 1, 1, 1, 1) = (1, 0, 0, 0, 1). PFR es un intento de descubrir cómo puede verse un conjunto si no es un subgrupo pero tiene algunas características similares a las de un grupo.

Para que PFR sea preciso, imagine que tiene un conjunto de listas binarias llamadas A. Ahora toma cada par de elementos de A y sumarlos. Las sumas resultantes constituyen la suma de A, lo cual se conoce como A + A. Si los elementos de A se eligen al azar, entonces la mayoría de las sumas son diferentes entre sí. Si hay k elementos en A, eso significa que habrá alrededor k²/2 elementos en la suma. Cuando k es grande (digamos, 1,000) k²/2 es mucho más grande que k. Pero si A es un subgrupo, cada elemento de A + A será en A, significa que A + A es del mismo tamaño que A misma.

PFR considera conjuntos que no son aleatorios, pero tampoco son subgrupos. En estos conjuntos, el número de elementos en A + A es algo pequeño, digamos, 10k, O 100k. "Es realmente útil cuando la noción de estructura es mucho más rica que simplemente ser una estructura algebraica exacta", dijo Shachar Lovett, científico informático de la Universidad de California, San Diego.

Todos los conjuntos que los matemáticos conocían y que obedecían a esta propiedad "están bastante cerca de subgrupos reales", dijo Tao. "Esa fue la intuición, que no había ningún otro tipo de grupos falsos por ahí". Freiman había demostrado una versión de esta afirmación en su trabajo original. En 1999, Ruzsa amplió el teorema de Freiman de los números enteros al establecimiento de listas binarias. El probó que cuando el número de elementos en A + A es un múltiplo constante del tamaño de A, A está contenido dentro de un subgrupo.

Pero el teorema de Ruzsa exigía que el subgrupo fuera enorme. La idea de Marton fue postular que, en lugar de estar contenidos en un subgrupo gigante, A podría estar contenido en un número polinómico de clases laterales de un subgrupo que no es mayor que el conjunto original A.

'Conozco una idea real cuando veo una idea real'

Alrededor del cambio de milenio, Gowers se topó con las demostraciones de Ruzsa del teorema de Freiman mientras estudiaba un problema diferente sobre conjuntos que contienen cadenas de números uniformemente espaciados. "Necesitaba algo como esto, obtener información estructural a partir de información mucho más vaga sobre un determinado conjunto", dijo Gowers. “Tuve mucha suerte de que no mucho antes Ruzsa presentara esta prueba absolutamente magnífica”.

Gowers comenzó a elaborar una posible prueba de la versión polinómica de la conjetura. Su idea era empezar con un set. A cuya suma era relativamente pequeña, luego manipular gradualmente A en un subgrupo. Si pudiera demostrar que el subgrupo resultante era similar al conjunto original A, fácilmente podría concluir que la conjetura era cierta. Gowers compartió sus ideas con sus colegas, pero nadie pudo plasmarlas en una prueba completa. Aunque la estrategia de Gowers tuvo éxito en algunos casos, en otros las manipulaciones tardaron A más lejos de la conclusión deseada de la conjetura polinómica de Freiman-Ruzsa.

Finalmente, el campo siguió adelante. En 2012, Sanders PFR casi probado. Pero el número de subgrupos desplazados que necesitaba estaba por encima del nivel polinomial, aunque sólo por un poquito. “Una vez que hizo eso, significó que se convirtió en algo menos urgente, pero sigue siendo un problema realmente agradable por el que tengo un gran cariño”, dijo Gowers.

Pero las ideas de Gowers perduraron en la memoria y en los discos duros de sus colegas. "Hay una idea real ahí", dijo Green, quien también había sido alumno de Gowers. "Reconozco una idea real cuando la veo". Este verano, Green, Manners y Tao finalmente liberaron las ideas de Gowers de su purgatorio.

Green, Tao y Manners trabajaron 37 páginas en profundidad antes de pensar en volver a las ideas de Gowers de hace 20 años. En un 23 de junio , habían utilizado con éxito un concepto de la teoría de la probabilidad llamado variables aleatorias para investigar la estructura de conjuntos con sumas pequeñas. Al hacer este cambio, el grupo podría manipular sus sets con más delicadeza. "Tratar con variables aleatorias es de alguna manera mucho menos rígido que tratar con conjuntos", dijo Manners. Con una variable aleatoria, "puedo modificar una de las probabilidades en una pequeña cantidad, y eso podría darme una mejor variable aleatoria".

Utilizando esta perspectiva probabilística, Green, Manners y Tao pudieron pasar de trabajar con el número de elementos de un conjunto a medir la información contenida en una variable aleatoria, una cantidad llamada entropía. La entropía no era nueva en la combinatoria aditiva. De hecho, Tao había intentado para popularizar el concepto a finales de la década de 2000. Pero nadie había intentado todavía utilizarlo en la conjetura polinómica de Freiman-Ruzsa. Green, Manners y Tao descubrieron que era poderoso. Pero todavía no pudieron probar la conjetura.

Mientras el grupo analizaba sus nuevos resultados, se dieron cuenta de que finalmente habían construido un entorno en el que las ideas latentes de Gowers podían florecer. Si midieran el tamaño de un conjunto utilizando su entropía, en lugar de su número de elementos, los detalles técnicos podrían funcionar mucho mejor. "En algún momento nos dimos cuenta de que estas viejas ideas de Tim de hace 20 años tenían más probabilidades de funcionar que las que estábamos probando", dijo Tao. “Y entonces trajimos a Tim nuevamente al proyecto. Y luego todas las piezas encajan sorprendentemente bien”.

Aún así, había muchos detalles por descubrir antes de reunir una prueba. "Era una especie de tontería que los cuatro estuviéramos increíblemente ocupados con otras cosas", dijo Manners. "Quieres publicar este gran resultado y contárselo al mundo, pero en realidad todavía tienes que escribir tus exámenes parciales". Finalmente, el grupo siguió adelante y el 9 de noviembre publicaron su artículo. Demostraron que si A + A no es más grande que k veces el tamaño de A, entonces A no puede cubrirse más que aproximadamente k¹² desplazamientos de un subgrupo que no es mayor que A. Se trata de un número potencialmente enorme de cambios. Pero es un polinomio, por lo que no crece exponencialmente más rápido como k se hace más grande, como lo haría si k estaban en el exponente.

Unos días después, Tao comenzó a formalizar la prueba. Dirigió el proyecto de formalización de forma colaborativa, utilizando el paquete de control de versiones GitHub para coordinar las contribuciones de 25 voluntarios en todo el mundo. Usaron una herramienta llamada Planos desarrollado por Patricio Massot, matemático de la Universidad Paris-Saclay, para organizar los esfuerzos para traducir lo que Tao , que son “Inglés matemático” en código informático. Blueprint puede, entre otras cosas, crear un gráfico que describe los diversos pasos lógicos involucrados en la prueba. Una vez que todas las burbujas estuvieron cubiertas por lo que Tao llamó un “hermoso tono de verde”, el equipo terminó. Descubrieron algunos errores tipográficos menores en el documento (en una publicación en línea). mensaje, Tao señaló que “las partes matemáticamente más interesantes del proyecto fueron relativamente sencillas de formalizar, pero fueron los pasos técnicos 'obvios' los que tomaron más tiempo”.

Marton murió pocos años antes de que se demostrara su famosa conjetura, pero la prueba se hace eco de ella. el trabajo de la vida sobre entropía y teoría de la información. "Todo funciona mucho mejor cuando lo haces en este marco de entropía que en el marco que yo estaba tratando de hacerlo", dijo Gowers. "A mí todavía me parece algo mágico".

¿Cuánto está realizando una serie de encuestas para servir mejor a nuestra audiencia. Toma nuestro encuesta de lectores de matemáticas y entrarás para ganar gratis ¿Cuánto merchandising