Se trata de un trabajo al que se considera como el mayor avance en la búsqueda de una solución al teorema de Ramsey, formulado en 1930
Ilustración basada en el teorema de Ramsey
Vitória Couto / Revista Pesquisa FAPESP
El 16 de marzo pasado, se impartieron en forma coordinada y casi simultánea tres seminarios sobre el mismo problema matemático en tres centros de estudios. Con su doctorado obtenido menos de una semana antes en el Instituto de Matemática Pura y Aplicada (Impa) de Rio de Janeiro, el paulista Marcelo Campos disertó ante una veintena de personas en el Instituto de Matemática y Estadística de la Universidad de São Paulo (IME-USP). El británico Simon Griffiths, profesor de la Pontificia Universidad Católica de Río de Janeiro (PUC-RJ), realizó una presentación en el Impa, y el canadiense Julian Sahasrabudhe habló sobre el tema en la Facultad de Matemática de la Universidad de Cambridge, en el Reino Unido.
Ese mismo día, una vez finalizados los seminarios, el trío de matemáticos, a los que se sumó otro colega, el británico Rob Morris, investigador del Impa, colgaron un artículo científico redactado a ocho manos en arXiv, un repositorio de preprints, estudios que aún no han sido revisados por pares. Para entonces, parte de la comunidad de investigadores del área de la combinatoria, una rama de la matemática que estudia las propiedades extremas, típicas y estructurales de los objetos finitos, ya estaban al tanto del trabajo. “Básicamente, todos los expertos en combinatoria se han empeñado en responder esta pregunta –incluso yo– y creo hacer justicia al decir que es uno de los dos o tres problemas principales que aún no se han resuelto en la combinatoria extrema, o acaso sea el principal”, tuiteó el británico Timothy Gowers, ganador de la Medalla Fields, uno de los máximos galardones del campo de la matemática, al día siguiente de haber asistido, asombrado, al seminario en Cambridge.
Tal como anunciaba su título, el trabajo del cuarteto suponía “un avance exponencial” al respecto del teorema de Ramsey, representado por la notación R(k). Se trata de un problema cuyo enunciado es muy sencillo, pero para el que desde 1935 no se había logrado ningún progreso realmente significativo en el camino de su dilucidación. “No hemos resuelto el teorema”, explica Campos. “Lo que hicimos fue crear un algoritmo que redujo el valor del límite superior de la respuesta al teorema”.
Puede que parezca poco para alguien ajeno al área, pero el resultado ha sido aclamado en todo el mundo como un hito y el artículo ha sido objeto de informes en los medios de comunicación especializados en ciencia y en la prensa en general. “Quedé atónito”, dijo el matemático Yuval Wigderson, de la Universidad de Tel Aviv [Israel], en una entrevista concedida a la revista en línea Quanta Magazine, al enterarse del trabajo. “Estuve literalmente temblando entre media y una hora”. El investigador Guilherme Mota, del IME-USP, quien organizó el seminario impartido por Campos en la universidad paulista, también quedó asombrado con la contribución que hicieron sus colegas. “Todos los que estudiamos el campo de la combinatoria nos hemos abocado en algún momento a este teorema”, dice Mota, experto en esta disciplina y con trabajos junto a dos de los cuatro autores del nuevo artículo. “Después de tanto tiempo sin grandes avances, nadie esperaba esta noticia”.
El teorema, que lleva el nombre del matemático británico Frank Plumpton Ramsey (1903-1930), quien lo formuló en 1930, es tan simple de entender como difícil de resolver a medida que aumenta el valor del número entero implicado en su planteo. Una adaptación popular de su enunciado formal pone la cuestión en términos cotidianos. ¿Cuál es la cantidad mínima de invitados a una fiesta para que siempre, inexorablemente, exista cierto número de personas que se conozcan mutuamente, o bien que ese mismo número de personas no se conozcan? No es necesario que cumpla las dos condiciones, tan solo basta con una. Esta cifra de invitados misterioso se representa genéricamente con la letra k, la que se utiliza en el enunciado del teorema de Ramsey, el antes mencionado R(k). En este ejemplo, se parte del supuesto de que la relación de conocimiento o desconocimiento es recíproca: si un individuo es amigo de otro, este, por ende, también lo es de aquel.
Rodrigo Cunha / Revista Pesquisa FAPESP
Siempre que k sea un número pequeño, el teorema es sencillo de resolver. Si k fuera 2, la respuesta al problema también es 2. En una fiesta con un par de participantes, los dos invitados son, forzosamente, amigos o desconocidos. No existe una tercera posibilidad. Si k fuera 3, el teorema también puede igualarse en una ecuación. La respuesta es 6. Es algo más trabajoso, pero incluso un lego en el tema puede entender y demostrar que, con media docena de participantes, siempre habrá tres que se conocen o tres desconocidos entre sí. Para un valor de k igual a 4, se necesitan 18 personas.
A partir de un k con valor 5, los matemáticos no tienen una respuesta cabal para el teorema. Solamente pueden afirmar que, en ese caso, la cantidad mínima de invitados es una cifra situada entre las 43 y 48 personas. Por ello, a medida que el valor de k aumenta, todo lo que los expertos en combinatoria son capaces de decir es que la respuesta al problema se ubica entre un límite inferior (en el ejemplo anterior, el número 43) y uno superior (el número 48).
Existen dos fórmulas para calcular cada límite de la respuesta parcial al teorema, el inferior y el superior. Sin embargo, ambas distan mucho de ser precisas y pueden optimizarse. En otras palabras, la ecuación del límite inferior da un resultado mucho menor y la del límite superior, una mucho mayor a la desconocida respuesta exacta al problema. El cuarteto integrado por Campos, Morris, Griffiths y Sahasrabudhe creó un algoritmo que mejoró sustancialmente la fórmula empleada para calcular el límite superior. En lugar de ser 4 elevado a la k (4k), el nuevo trabajo demostró que la ecuación puede reducirse a 3,995 elevado a la k (3,995k). Parece una alteración sutil, pero desde 1935, cuando los matemáticos húngaros Paul Erdös (1913-1996) y George Szekeres (1911-2005) propusieron la fórmula 4k, nadie había conseguido incorporar ningún cambio significativo en la ecuación.
“Introdujimos un apaño matemático y tuvimos suerte”, dice Griffiths, risueño, refiriéndose al planteo empleado por el cuarteto para mejorar la fórmula históricamente utilizada para determinar el límite superior del teorema. “En este primer artículo, que publicaremos en una revista científica, no hemos llevado nuestro planteo hasta el extremo de sus posibilidades. Creemos que todavía es posible reducir un poco más el valor de 3,995 que propusimos en nuestra ecuación”.
La idea de trabajar con el teorema de Ramsey cobró forma en 2018, cuando el canadiense Sahasrabudhe, en la actualidad docente en la Universidad de Cambridge, estaba completando su posdoctorado en el Impa. “Siempre estamos buscando problemas interesantes y complejos”, relata Morris, del Impa. “Nuestra estrategia habitual consiste en pasar algunos días discutiendo un nuevo problema frente a un pizarrón, generando ideas y tratando de entender sus obstáculos principales. Luego de eso, decidimos si tenemos algún planteo que merezca la pena seguir investigando”. La mayoría de las reuniones del grupo tenían lugar en Río de Janeiro, durante el verano, cuando Sahasrabudhe podía ausentarse del Reino Unido y reunirse allí con sus colegas. Durante la pandemia, las reuniones presenciales pasaron a ser virtuales.
Rodrigo Cunha / Revista Pesquisa FAPESP
Aunque llevaban cinco años estudiando posibles avances en la resolución del teorema, la contribución que marcó la diferencia no se produjo sino hasta enero de 2023, cuando modificaron la estrategia para abordar la cuestión. Una vez que encontraron el camino más prometedor, arribaron al resultado en pocos días y enseguida redactaron el artículo con el hallazgo. “Optamos por un método probabilístico, basado en los trabajos de Erdös, que intenta resolver problemas no aleatorios”, dice Campos, quien se sumó al grupo recién en 2021.
El teorema de Ramsey no tiene aplicación en la vida cotidiana, pero su estudio ha tenido y tiene una gran repercusión en el campo de la matemática y otras áreas afines. Se lo considera una de las incógnitas fundamentales de la combinatoria, con implicaciones en disciplinas tales como la computación, la lógica y la física estadística. La llamada teoría de grafos, uno de los componentes esenciales de la combinatoria, está estrechamente relacionada con el teorema.
Un grafo es una representación abstracta de un conjunto de elementos y de las relaciones entre cada subconjunto de esa estructura compuesto por dos de estos objetos. Los elementos se denominan vértices o nodos. Las relaciones están asociadas a aristas, que establecen una conexión entre los pares de objetos. En la analogía social utilizada para explicar el teorema de Ramsey, el grafo de la fiesta está compuesto por vértices (cada persona es uno de ellos) y aristas (la relación entre cada par de invitados, si se conocen o si son completos desconocidos). Las aristas que unen a dos amigos se pintan de un color, normalmente azul, por convención. Las que vinculan a dos extraños suelen pintarse de rojo. Así puede diferenciarse el tipo o calidad de la relación.
El planteo básico del teorema de Ramsey consiste en demostrar que, en cualquier estructura formada por un conjunto de elementos, incluso en las más amplias y aleatorias, siempre existe un subconjunto de esos elementos, una estructura menor, que obedece a un cierto orden. “Incluso en el caos, alguna porción presenta cierta organización”, explica Mota. En el fondo, la respuesta al problema indica cuál es el tamaño mínimo que esta estructura caótica debe tener para que siempre exista en su interior una subestructura que obedezca a algún tipo de patrón.
Vale la pena retrotraernos otra vez al ejemplo de la fiesta para que no queden dudas sobre este punto central. Cuántas personas, conocidas o no entre sí, deben conformar el conjunto de los invitados a la fiesta – por consiguiente, una estructura caótica – para que siempre exista un número k de individuos conocidos entre sí o un número k de desconocidos. En ambos casos, se trata de una subestructura que responde a un orden.
“La importancia de estudiar el teorema de Ramsey radica en que no sabemos hasta qué punto una organización puede ‘esconderse’ detrás de una estructura que, considerando otros aspectos, parece ser aleatoria”, dice Morris. “Esta es una cuestión esencial en el estudio de grandes objetos finitos. Esperamos que el estudio del teorema de Ramsey nos lleve a desarrollar herramientas que puedan aplicarse a muchos otros contextos”.
Un prodigio de Cambridge El matemático británico planteó el teorema cuando tenía 26 años, poco antes de morir
J. M. Keynes Papers Archive / Wikimedia CommonsFrank Plumpton RamseyJ. M. Keynes Papers Archive / Wikimedia Commons
El teorema de Ramsey es posiblemente la contribución científica más conocida del británico Frank Plumpton Ramsey (1903-1930), considerado un genio por sus pares. Sus trabajos se insertan en los campos de la matemática, la filosofía y la economía. Ramsey nació en Cambridge, era hijo de una sufragista y de un profesor de matemática del Magdalene College, una de las facultades de la prestigiosa universidad local, e inició sus estudios superiores a los 17 años. En 1920 ingresó al Trinity College, otra de las facultades de Cambridge, y se graduó en 1923, como el mejor alumno de su promoción en matemática.
Cuando cursaba el segundo año en la facultad, y habiendo dominado en poco tiempo el idioma alemán, comenzó a traducir en inglés el libro Tractatus logico-philosophicus, del filósofo austríaco Ludwig Wittgenstein (1889-1951), miembro del llamado Círculo de Viena. Este grupo estaba integrado por filósofos, matemáticos y pensadores que se reunían periódicamente en la capital austríaca durante los años 1920 para discutir sobre el lenguaje y la metodología científica. Ramsey visitó Viena en 1923 y, al año siguiente, pasó allí seis meses, reuniéndose con Wittgenstein y otros miembros del círculo.
Las ideas en las que se basaba su teorema (y la teoría de grafos) se publicaron en 1930, el año en que el matemático murió, poco antes de cumplir 27 años. Ramsey falleció por causas desconocidas, tras una intervención quirúrgica de urgencia, tal vez debido a posibles problemas renales, ictericia o leptospirosis.
This article may be republished online under the CC-BY-NC-ND Creative Commons license. The Pesquisa FAPESP Digital Content Republishing Policy, specified here, must be followed. In summary, the text must not be edited and the author(s) and source (Pesquisa FAPESP) must be credited. Using the HTML button will ensure that these standards are followed. If reproducing only the text, please consult the Digital Republishing Policy.
