🔢 mathematics

Lean-verified lower bounds for the Shannon capacity of odd cycles

Este artículo presenta nuevos límites inferiores, totalmente formalizados en Lean, para las capacidades de Shannon de varios ciclos impares pequeños ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ) derivados mediante un procedimiento iterativo basado en métodos recientes de Gao e Itty et al.

Autores originales: Pjotr Buys, Sven Polak, Jeroen Zuiddam

Publicado 2026-08-03

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Pjotr Buys, Sven Polak, Jeroen Zuiddam

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando enviar un mensaje secreto a través de una ciudad ruidosa y caótica. La ciudad está llena de distracciones, y a veces tu señal se mezcla con nombres de calles equivocados. En el mundo de la teoría de la información, este es un problema real: ¿cómo se pueden enviar datos perfectamente sin errores? En la década de 1950, un matemático llamado Claude Shannon descubrió que, si tienes un canal "ruidoso", aún puedes enviar mensajes perfectamente, pero solo si eres hábil al agrupar tus letras. Introdujo un concepto llamado "capacidad de Shannon", que es esencialmente una puntuación que te indica la velocidad máxima a la que puedes enviar mensajes perfectos a través de un tipo específico de red ruidosa.

Para visualizar esto, imagina un juego jugado sobre el mapa de una ciudad. El mapa es un grafo, donde las intersecciones son puntos y las calles son líneas. Algunas calles son "seguras" para viajar en ellas, mientras que otras son peligrosas y causarán un choque si las mezclas. El objetivo es elegir el grupo más grande posible de intersecciones (un "conjunto independiente") que puedas visitar sin tomar nunca una calle peligrosa entre dos de ellas. La "capacidad de Shannon" plantea una pregunta difícil: si juegas este juego no solo una vez, sino apilando múltiples copias del mapa una encima de otra para crear una ciudad gigante y multidimensional, ¿qué tan grande puede volverse tu grupo seguro? Para algunas formas, conocemos la respuesta. Para otras, específicamente los bucles de forma impar (como un pentágono o un heptágono), la respuesta ha sido un misterio durante décadas. Es como conocer el límite de velocidad en una carretera recta pero no tener idea de qué tan rápido puedes ir en una pista sinuosa de siete esquinas.

Este artículo trata de descifrar ese misterio para varias de esas complicadas pistas de siete esquinas (y más grandes). Los autores, un equipo de matemáticos y científicos de la computación, han encontrado formas nuevas y ligeramente más rápidas de enviar mensajes perfectos a través de estos bucles específicos. No solo adivinaron; usaron una receta ingeniosa y paso a paso para construir grupos cada vez más grandes de intersecciones seguras. Para asegurarse de no cometer ni un solo error en su compleja matemática, utilizaron un árbitro digital súper estricto llamado "Lean" para revisar cada paso de su trabajo. ¿El resultado? Han demostrado que, para estos bucles impares específicos, la velocidad máxima de comunicación perfecta es mayor de lo que nadie había calculado anteriormente.

El Juego de las Intersecciones Seguras

Vamos a desglosar lo que los autores hicieron realmente. Estaban analizando grafos que parecen anillos simples con un número impar de puntos: un anillo de 7, un anillo de 11, un anillo de 13, y así sucesivamente. Durante mucho tiempo, los matemáticos supieron el "límite de velocidad" (la capacidad de Shannon) para un anillo de 5 puntos. Pero para los anillos con 7 puntos o más, la respuesta ha estado atrapada en la niebla. Sabíamos que era al menos un cierto número, pero no sabíamos si podía ser mayor.

Los autores utilizaron un método que se siente como una receta mágica para hacer crecer tu grupo seguro. Imagina que tienes un pequeño club de amigos seguros (un conjunto de puntos) en un solo mapa. El artículo describe un "teorema de producto", que es como una máquina que toma dos de estos mapas y los aplasta juntos para crear un nuevo mapa más grande. Si tienes un club seguro en el primer mapa y un club seguro en el segundo, puedes combinarlos para hacer un club seguro en el nuevo mapa más grande. Usualmente, el tamaño de este nuevo club es simplemente el tamaño del primer club multiplicado por el tamaño del segundo. Pero los autores encontraron un "gadget" o truco especial. Al usar un patrón específico de conexiones (llamado "tupla válida"), pudieron hacer que el nuevo club fuera más grande de lo que la simple multiplicación sugeriría.

Piénsalo de esta manera: Si tienes un equipo de 2 personas que pueden trabajar juntas sin pelear, y combinas dos tales equipos, podrías esperar un equipo de 4. Pero con este truco especial, los autores encontraron una manera de combinarlos y obtener un equipo de 5 personas que se llevan perfectamente bien. Al repetir este truco una y otra vez, apilando los mapas cada vez más alto, pudieron hacer crecer estos equipos seguros en grupos masivos.

Los Nuevos Récords

El equipo aplicó esta receta a siete anillos impares diferentes: aquellos con 7, la de 11, 13, 15, 19, 21 y 23 puntos. Para cada uno, comenzaron con un grupo seguro conocido y pasaron su máquina de "apilamiento" muchas veces. El resultado fue un nuevo límite inferior más alto para la capacidad de Shannon.

Aquí está lo que encontraron, con los números exactamente como los calcularon:

Para el anillo de 7 puntos, demostraron que la capacidad es al menos 3.258805369885. Esto es un poquito más alto que la mejor suposición anterior.
Para el anillo de 11 puntos, el nuevo suelo es 5.294502522149.
Para el anilla de 13 puntos, empujaron el límite a 6.302455083464.
Para el anillo de 15 puntos, el número es 7.301600534487.
Para el anillo de 19 puntos, alcanzaron 9.357192705918.
Para el anillo de 21 puntos, el límite es 10.342455853338.
Y para el anillo de 23 puntos, encontraron una capacidad de al menos 11.328224257774.

Estos números pueden parecer una cadena de dígitos aleatorios, pero en el mundo de la teoría de la información, representan una mejora concreta. Significan que, para estas redes específicas, ahora sabemos con certeza que podemos enviar mensajes un poco más rápido de lo que creíamos posible antes.

El Árbitro Digital

Lo que hace que este artículo sea especial no son solo los números, sino cómo obtuvieron los resultados. La matemática involucrada es increíblemente compleja, implicando conjuntos de datos enormes y miles de pasos. Es el tipo de trabajo donde un humano podría cometer fácilmente un pequeño error. Para resolver esto, los autores escribieron toda su prueba en un lenguaje de computadora llamado Lean.

Piensa en Lean como un árbitro digital hiperestricto que no acepta un "creo que esto es correcto" o "se ve bien para mí". Exige una prueba lógica absoluta para cada uno de los pasos. Si los autores cometieron un error en su lógica, Lean se detendría y diría: "No, eso no se sigue". El hecho de que el artículo esté "verificado por Lean" significa que una computadora ha revisado cada línea de su razonamiento y ha confirmado que sus nuevos límites son matemáticamente sólidos. No solo simularon los resultados; probaron formalmente.

Los autores también mencionan que utilizaron modelos de lenguaje de gran tamaño (como los chatbots de IA avanzados) para ayudarlos a encontrar los patrones iniciales y las recetas para estos grupos seguros. Es un poco como tener un asistente creativo que sugiere una idea salvaje, y luego los matemáticos usan sus herramientas rigurosas para probar si esa idea realmente se sostiene. En este caso, la IA sugirió un camino, y el equipo de humano-matemático-IA recorrió todo el camino hasta una meta verificada.

Por Qué Importa

Podrías preguntarte: "¿Y qué? Solo sabemos que el número es un poco más alto". La respuesta reside en la naturaleza del problema. Durante décadas, la capacidad de estos anillos impares ha sido una pregunta abierta. Sabíamos que la respuesta estaba en algún lugar entre un límite inferior y un límite superior (el límite de Lovász), pero no podíamos determinarla con precisión. Cada vez que empujamos el límite inferior hacia arriba, incluso por una fracción mínima, estrechamos la brecha. Nos estamos acercando a la respuesta verdadera.

Este trabajo muestra que, incluso para problemas que han estado estancados durante mucho tiempo, todavía hay margen de mejora si tienes las herramientas adecuadas y la paciencia para verificar tu trabajo con los estándares más rigurosos posibles. Los autores no han resuelto el misterio completo de la capacidad de Shannon para todos los anillos impares, pero han despejado algunos rincones nublados más, demostrando que para los anillos de 7, 11, 13, 15, 19, 21 y 23, podemos comunicarnos un poco más rápido de lo que creíamos anteriormente.

Resumen Técnico: Cotas Inferiores Verificadas con Lean para la Capacidad de Shannon de Ciclos Impares

Planteamiento del Problema
El artículo aborda el problema abierto de larga data de determinar la capacidad de Shannon, $\Theta(G)$ , para ciclos impares $C_n$ donde $n \geq 7$ . La capacidad de Shannon se define como $\Theta(G) := \sup_{d \geq 1} \alpha(G^{\boxtimes d})^{1/d}$ , donde $\alpha$ es el número de independencia y $\boxtimes$ es el producto fuerte de grafos. Mientras que Lovász determinó que $\Theta(C_5) = \sqrt{5}$ utilizando la función theta $\vartheta(G)$ , las capacidades exactas para todos los ciclos impares de longitud siete o mayor siguen siendo desconocidas. El desafío principal radica en encontrar conjuntos independientes más grandes en potencias fuertes superiores de estos ciclos para mejorar las cotas inferiores conocidas.

Metodología
Los autores emplean un procedimiento iterativo basado en una "construcción de gadget" y un "lema de producto" propuesto recientemente por Gao (2026), el cual se basa a su vez en los métodos de Itty, Rosin, Carstensen y Reichman (2026). El núcleo de la metodología involucra:

Tuplas Válidas: Para un grafo $G$ , se define una tupla válida $\tau = (I, S, f_0, f_1, X)$ , donde $I$ es un conjunto independiente, $S \subseteq I$ , y $f_0, f_1$ son mapeos específicos que satisfacen restricciones de vecindad estrictas. Esta tupla genera un "perfil" $\Pi(\tau) = (|I|, |S|, |X|, |X \setminus (N_G[f_0(S)] \cup N_G[f_1(S)])|)$ .
Operación de Producto: Se define una operación binaria $\star$ sobre los perfiles. El Teorema 1 establece que, si $\tau$ y $\tau'$ son tuplas válidas para los grafos $G$ y $H$ , existe una tupla válida para el producto fuerte $G \boxtimes H$ cuyo perfil es el producto $\star$ de los perfiles individuales.
Construcción Iterativa: Partiendo de una tupla válida descubierta computacionalmente en una potencia específica de un ciclo impar, los autores aplican iterativamente el producto $\star$ para generar perfiles para potencias superiores. Este proceso construye conjuntos independientes en potencias fuertes $C_n^{\boxtimes d}$ que son más grandes de lo que se obtendría mediante productos cartesianos simples de los conjuntos independientes base.
Verificación Formal: Un componente crítico de la metodología es la formalización completa de estas cotas en el asistente de pruebas Lean. Las tuplas base (conjuntos $I, S, X$ y mapeos $f_0, f_1$ ) se codifican como literales explícitos, y su validez es verificada mecánicamente dentro del entorno de Lean.

Contribuciones Clave y Resultados
El artículo presenta nuevas cotas inferiores mejoradas para siete ciclos impares pequeños ( $C_7, C_{11}, C_{13}, C_{15}, C_{19}, C_{21}, C_{23}$ ). Estas cotas se derivan de la identificación de tuplas válidas base específicas y la aplicación del procedimiento de producto iterativo. Los resultados son:

$\Theta(C_7)$ : Mejorada a $\geq 3.258805369885\dots$ (previamente $3.2587891\dots$ por Gao 2026). La construcción utiliza una tupla base en $C_7^{\boxtimes 5}$ iterada a la potencia 200.
$\Theta(C_{11})$ : Mejorada a $\geq 5.294502522149\dots$ (previamente $5.2897736\dots$ por Itty et al. 2026). La tupla base está en $C_{11}^{\boxtimes 3}$ , iterada a la potencia 174.
$\Theta(C_{13})$ : Mejorada a $\geq 6.302455083464\dots$ (previamente $6.3001091\dots$ por Itty et al. 2026). La tupla base está en $C_{13}^{\boxtimes 6}$ , iterada a la potencia 432.
$\Theta(C_{15})$ : Mejorada a $\geq 7.301600534487\dots$ (previamente $7.3013990\dots$ por Itty et al. 2026). La tupla base está en $C_{15}^{\boxtimes 4}$ , iterada a la potencia 4096.
$\Theta(C_{19})$ : Mejorada a $\geq 9.357192705918\dots$ (previamente $9.3571200\dots$ por Baumert et al. 1971). La tupla base está en $C_{19}^{\boxtimes 4}$ , iterada a la potencia 16384.
$\Theta(C_{21})$ : Mejorada a $\geq 10.342455853338\dots$ (previamente $10.3422729\dots$ por Baumert et al. 1971). La tupla base está en $C_{21}^{\boxtimes 4}$ , iterada a la potencia 4096.
$\Theta(C_{23})$ : Mejorada a $\geq 11.328224257774\dots$ (previamente $11.3278379\dots$ por Baumert et al. 1971). La tupla base está en $C_{23}^{\boxtimes 4}$ , iterada a la potencia 2048.

Las mejoras, aunque numéricamente pequeñas (en el rango de $10^{-5}$ a $10^{-3}$ ), representan el estado del arte actual para estos ciclos específicos.

Significancia y Reivindicaciones
El artículo reivindica su significancia principalmente a través de la verificación rigurosa de estos resultados. Al formalizar toda la construcción y las cotas resultantes en Lean, los autores aseguran que los complejos argumentos combinatorios y las construcciones de conjuntos específicas estén libres de errores humanos. El trabajo sigue la trayectoria de la investigación reciente que utiliza modelos de lenguaje extensos (LLM) para descubrir construcciones iniciales (como se ve en [IRCR26] y [Gao26]), pero se distingue al proporcionar una prueba totalmente formalizada y verificada por máquina de la validez de las tuplas base y la corrección de la aplicación del lema de producto de Gao. Los autores no pretenden haber resuelto el problema general de la capacidad de Shannon para los ciclos impares, ni proponen nuevos marcos teóricos más allá de la aplicación del lema de producto existente de Gao; más bien, proporcionan las mejores cotas inferiores numéricas conocidas actualmente para estos casos específicos, verificadas con certeza matemática.

El Juego de las Intersecciones Seguras

Los Nuevos Récords

El Árbitro Digital

Por Qué Importa

Más como este