la versión original de esta historia apareció en Revista Cuanta.
Lo que va de año, cuantos ha narrado tres avances importantes en la teoría de Ramsey, el estudio de cómo evitar la creación de patrones matemáticos. El primer resultado puso un nuevo límite a lo grande que puede ser un conjunto de enteros sin contener tres números espaciados uniformemente, como 2, 4, 6 o 21, 31, 41. De manera similar, el segundo y el tercero imponen nuevos límites al tamaño de las redes sin grupos de puntos que están todos conectados o todos aislados entre sí.
Las pruebas abordan lo que sucede cuando los números involucrados crecen infinitamente. Paradójicamente, esto a veces puede ser más fácil que lidiar con molestas cantidades del mundo real.
Por ejemplo, considera dos preguntas sobre una fracción con un denominador muy grande. Podría preguntar cuál es la expansión decimal de, digamos, 1/42503312127361. O podría preguntar si este número se acercará a cero a medida que crece el denominador. La primera pregunta es una pregunta específica sobre una cantidad del mundo real, y es más difícil de calcular que la segunda, que pregunta cómo la cantidad 1/norte cambiará “asintóticamente” como norte crece (Se acerca cada vez más a 0.)
“Este es un problema que afecta a toda la teoría de Ramsey”, dijo William Gasarch, científico informático de la Universidad de Maryland. «La teoría de Ramsey es conocida por tener asintóticamente muy buenos resultados». Pero analizar números que son más pequeños que el infinito requiere una caja de herramientas matemáticas completamente diferente.
Gasarch ha estudiado preguntas en la teoría de Ramsey que involucran números finitos que son demasiado grandes para que el problema se resuelva por la fuerza bruta. En un proyecto, asumió la versión finita del primero de los avances de este año: un artículo de febrero de Zander Kelley, un estudiante graduado de la Universidad de Illinois, Urbana-Champaign, y Raghu Meka de la Universidad de California, Los Ángeles. Kelley y Meka encontraron un nuevo límite superior sobre cuántos enteros entre 1 y norte puede poner en un conjunto evitando progresiones de tres términos o patrones de números espaciados uniformemente.
Aunque el resultado de Kelley y Meka se aplica incluso si norte es relativamente pequeño, no da un límite particularmente útil en ese caso. Para valores muy pequeños de norte, es mejor que te apegues a métodos muy simples. Si norte es, digamos, 5, basta con mirar todos los posibles conjuntos de números entre 1 y nortey elija el más grande sin progresión: 1, 2, 4, 5.
Pero el número de diferentes respuestas posibles crece muy rápidamente y hace demasiado difícil emplear una estrategia tan simple. Hay más de 1 millón de conjuntos que consisten en números entre 1 y 20. Hay más de 1060 utilizando números entre 1 y 200. Encontrar el mejor conjunto sin progresión para estos casos requiere una gran dosis de potencia informática, incluso con estrategias de mejora de la eficiencia. “Tienes que poder sacar mucho rendimiento de las cosas”, dijo James Glenn, científico informático de la Universidad de Yale. En 2008, Gasarch, Glenn y Clyde Kruskal de la Universidad de Maryland escribieron un programa para encontrar las configuraciones más grandes sin progresión hasta un norte de 187. (El trabajo anterior había obtenido las respuestas hasta 150, así como para 157). A pesar de una lista de trucos, su programa tardó meses en terminar, dijo Glenn.