Un gran avance en la resolución de la hipótesis de 60 años arroja luz sobre cómo el orden comienza a aparecer en ellos con el crecimiento de sistemas aleatorios
Un equipo de matemáticos e informáticos finalmente demostró progreso en la resolución, a primera vista, de una tarea simple que plagó a los investigadores durante casi seis décadas.
Esta tarea, establecida por los matemáticos Pal Erdös y Richard Rado en 1960, se refiere a la frecuencia con la que se puede esperar la aparición de patrones que se asemejan a un girasol en grandes conjuntos de objetos, por ejemplo, en una gran cantidad de puntos dispersos en un avión. Aunque el
nuevo resultado no resuelve completamente la hipótesis de Erdös y Rado, promueve la comprensión de los matemáticos en la aparición de estructuras sorprendentemente complejas en grupos aleatorios. Con este fin, la tarea se reformuló en términos de una función informática, aprovechando la creciente relación entre la informática teórica y las matemáticas puras.
“En este trabajo, una idea matemática se manifiesta de una manera nueva, que se convertirá en la idea principal de nuestro tiempo. El resultado en sí mismo es sorprendente ”, dijo
Gil Kalai, de la Universidad Hebrea de Jerusalén.
La hipótesis del girasol se refiere a conjuntos o conjuntos de objetos. Es más fácil imaginarse usando el ejemplo de un conjunto de puntos en el plano xy. Primero, seleccione un número fijo de puntos que se incluirán en cada conjunto. Luego dibuje bucles aleatorios para que cada bucle, o conjunto, incluya un número seleccionado de puntos. Los bucles pueden cruzarse, y algunos puntos pueden caer en varios conjuntos, pareciéndose a un diagrama de Venn.
Si dibuja muchos bucles que contienen una gran cantidad de puntos, la mayoría de ellos se cruzarán y se parecerán a las complejidades de las vides. Pero Erdös y Rado predijeron que también se obtendría una estructura refinada: tres o más conjuntos se cruzarían entre sí, dejando el mismo subconjunto de puntos en la intersección, mientras que ninguno de estos conjuntos se cruzaría con ningún otro conjunto.
Si elimina este subconjunto común de puntos, los tres conjuntos se ubicarán alrededor del vacío y se separarán por completo, como pétalos alrededor del centro oscuro del girasol. Se considera que el girasol más simple tiene tres conjuntos que no se cruzan con ningún otro; tales islas se llaman conjuntos disjuntos.
Erdös y Rado sugirieron que a medida que aumenta el número de bucles, inevitablemente aparecerán tales girasoles, ya sea en forma de conjuntos disjuntos, o en forma de conjuntos superpuestos entre sí de la manera indicada. Esta hipótesis del girasol es parte de un área más general de las matemáticas llamada
teoría de Ramsey, que estudia cómo el orden comienza a aparecer en ellos con el aumento del tamaño de los sistemas aleatorios.
"Si tienes un objeto matemático suficientemente grande, una estructura debe estar oculta en él", dijo
Shachar Lovet de la Universidad de California, San Diego, coautor de un nuevo trabajo que también trabajó
Ryan Alweis de la Universidad de Princeton, Keven Wu de la Universidad de Pekín y
Jiapeng Zhang de la Universidad de Harvard.
Erdös y Rado querían saber exactamente cuántos juegos y qué tamaño se necesitan para garantizar un girasol. Dieron el primer paso modesto para resolver el problema definiendo el parámetro w, que denota el número de puntos en cada uno de los conjuntos. Luego demostraron que se necesitan aproximadamente w
w de conjuntos de tamaño w para garantizar que aparezca un girasol que consta de tres conjuntos en ellos. Por lo tanto, si desea utilizar conjuntos de 100 puntos, necesitará entre 100 y
100 conjuntos para garantizar la apariencia de un girasol.
Al mismo tiempo, Erdös y Rado sugirieron que, de hecho, el número de conjuntos que garantizan un girasol es mucho menor que w
w , y más parecido a una constante en grado w (por ejemplo, 3
w u 80
w o 5 000 000
w ). Sin embargo, no pudieron encontrar una manera de demostrar su suposición.
"Dijeron que la tarea parecía extremadamente simple, y se sorprendieron de que no pudieran lograr progreso en ella", dijo Alveys.
Y no estaban solos. En el período desde su primer resultado y este nuevo trabajo, que apareció 60 años después, solo dos matemáticos lograron al menos algún progreso en este tema, y luego fueron gradualmente, dando un paso en 1997 y el
segundo este año .
"Todos ya han probado todas las ideas con las que las personas se sienten cómodas", dijo
Anup Rao de la Universidad de Washington, quien publicó
un trabajo adicional que simplifica los métodos obtenidos en el nuevo resultado. "Y nadie pudo mejorar la línea base establecida por Erds y Rado".
Pero la nueva evidencia hizo un gran avance.
Cuatro investigadores, incluidos matemáticos e informáticos, pudieron hacer esto al dividir la tarea en dos escenarios diferentes. En el primero, más fácil, observaron lo que sucedería cuando los conjuntos se cruzan significativamente entre sí, lo que hace que sea mucho más fácil entender cuándo debería aparecer un girasol allí.
"Cuando tienes un conjunto de elementos que pertenecen a un conjunto más grande de conjuntos, puedes usar esta estructura" para buscar un girasol, dijo Lovet.
Al principio, los investigadores se preguntaron si existe un conjunto de puntos que pertenezcan a una parte suficientemente grande de todos los conjuntos del sistema. Habiendo encontrado tales puntos, en su búsqueda de un girasol, se limitaron solo a esa parte de los conjuntos que contienen este conjunto de puntos. Luego continuaron actuando de la misma manera, refinando la búsqueda, incluyendo cada vez menos conjuntos de sistemas, que tienen cada vez más puntos en común. Esta poda continuó hasta que encontraron su girasol.
En un segundo escenario más complejo, analizan lo que sucederá si los conjuntos no se cruzan fuertemente. En este caso, la forma más probable de obtener un girasol es tomar tres conjuntos disjuntos. Sin embargo, probar que tres conjuntos separados se esconden en conjuntos que se entrecruzan ligeramente no es fácil.
Aquí es donde entra en juego la informática. Dos coautores, Lovet y Zhang, han intentado durante varios años analizar el problema del girasol utilizando las mismas herramientas que usan los científicos informáticos para estudiar las funciones booleanas. Estas funciones realizan operaciones en una secuencia de bits, unos y ceros, y producen un solo bit al final, correspondiente a si una declaración computacional es verdadera o falsa. Por ejemplo, una función booleana se puede programar para devolver 1 si al menos uno de los bits de entrada es 1, y 0 si ninguno de los bits de entrada es 1.
Hace tres años, Lovet y Zhang se dieron cuenta de que podría plantearse la misma pregunta sobre si hay tres conjuntos disjuntos entre un conjunto de conjuntos que no se cruzan fuertemente. Primero, asigne una etiqueta a cada punto del conjunto: 1 si está contenido solo en este conjunto y 0 en otro caso. Una función booleana devuelve 1 (verdadero) si cada punto en la entrada es 1, es decir, cada punto del conjunto existe exclusivamente en este conjunto, lo que hace que este conjunto sea disjunto. El verdadero resultado sugiere que existen condiciones adecuadas para encontrar un girasol.
Para probar estrictamente esta correspondencia, los investigadores utilizaron un amplio conocimiento sobre las funciones booleanas para atacar el problema del girasol, que anteriormente carecía de recursos. Probaron que (log w)
w conjuntos son suficientes para obtener un girasol. Tal resultado no es suficiente para probar la hipótesis de que una cierta constante en grado w es suficiente para obtener un girasol. Pero este es un orden de magnitud mejor resultado que w
w obtenido por Erdös y Rado, y coincide aproximadamente con el número de conjuntos que predijeron.
Después de medio siglo de fracasos, el nuevo trabajo sugiere que pronto veremos una solución completa. También mejora la comprensión de cómo surgen inevitablemente formas especiales en la naturaleza matemática salvaje del azar.