🤖 AI

Improved lower bounds for the Shannon capacity of odd cycles

Este artículo presenta límites inferiores mejorados para la capacidad de Shannon de los ciclos impares $C_7$ , $C_{11}$ , $C_{13}$ y $C_{15}$ mediante la construcción de conjuntos independientes más grandes en sus productos fuertes a través de la colaboración iterativa con un Modelo de Lenguaje de Gran Escala.

Autores originales: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

Publicado 2026-07-31

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

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 un canal de walkie-talkie con estática. Cada vez que hablas, la estática podría confundir tus palabras, convirtiendo un "sí" en un "no". En el mundo de la teoría de la información, los científicos se hacen una pregunta muy específica: ¿Cuál es la velocidad máxima a la que podemos enviar mensajes para que el receptor los comprenda perfectamente, con cero errores, sin importar cuánta estática haya en el aire? Este límite se llama la capacidad de Shannon.

Para calcular esto, los matemáticos utilizan una herramienta llamada "grafo", que es simplemente un mapa sofisticado de puntos conectados por líneas. Piensa en los puntos como diferentes mensajes que podrías enviar y las líneas como las similitudes confusas entre ellos. Si dos puntos están conectados, significa que esos dos mensajes podrían mezclarse debido al ruido. El objetivo es elegir un grupo de puntos (mensajes) que no estén conectados entre sí, para que todos sean distintos y estén a salvo de la confusión. Cuanto más grande sea este grupo, más información se puede enviar.

Lo truculento es que podemos combinar estos mapas para crear mapas aún más grandes y complejos. Al apilar estos mapas, a veces podemos encontrar grupos enormes de mensajes seguros que no podíamos ver antes. Para algunas formas, como los anillos de número par, conocemos la respuesta perfectamente. Pero para los anillos de número impar (como una forma de 7 o 11 lados), la respuesta ha sido un misterio obstinado durante décadas. Es como intentar encontrar el mayor número de puntos que no se toquen en una pulsera retorcida y anudada, y nadie ha podido encontrar la mejor disposición absoluta todavía.

Este artículo trata sobre un equipo de investigadores que decidió abordar estos persistentes anillos impares utilizando un ayudante de un tipo muy nuevo: un Modelo de Lenguaje Extenso (LLM), que es el mismo tipo de IA que impulsa a los chatbots inteligentes. En lugar de simplemente escribir código para buscar la respuesta, trataron a la IA como un socio creativo. Le pidieron a la IA que observara las mejores disposiciones conocidas de mensajes seguros para estos anillos impares y luego intentara retocarlas apenas un poco para hacerlas aún más grandes.

Los resultados fueron sorprendentemente exitosos. El equipo, trabajando con la IA, descubrió nuevos y más grandes grupos de mensajes seguros para anillos de 7, 11, 13 y 15 lados. Para el anillo de 7 lados, encontraron un grupo de 134.753 mensajes seguros, lo cual es mayor que el récord anterior de 367. Para el anillo de 11 lados, encontraron 21.909 mensajes seguros. Para el de 13 lados, encontraron 62.530, y para el de 15 lados, un masivo 8.076.974.

Estos números pueden parecer solo una lista de dígitos, pero representan una mejora real en nuestra comprensión de cuánta información se puede enviar sin errores. Al encontrar estos grupos más grandes, los investigadores demostraron que la velocidad máxima para enviar mensajes perfectos a través de estos canales ruidosos específicos es ligeramente mayor de lo que pensábamos antes. Por ejemplo, para el anillo de 7 lados, ahora se sabe que el límite de velocidad es mayor a 3.258020, mientras que antes solo se sabía que era mayor a 3.257865.

Lo que hace que esta historia sea particularmente emocionante no son solo los números, sino cómo se encontraron. Los investigadores probaron métodos de búsqueda computacional tradicionales, como el recocido simulado (que es como agitar una caja de piezas de rompecabezas hasta que encajen), pero esos métodos fallaron al no poder encontrar estos nuevos y más grandes grupos. Incluso los algoritmos de búsqueda local construidos con IA no pudieron alcanzar esas nuevas alturas. Fue solo a través de una conversación de ida y vuelta con la IA, donde los investigadores le daban pistas y la IA sugería modificaciones creativas a los patrones existentes, que se lograron romper estos nuevos récords.

El artículo no pretende haber resuelto el misterio completo de la capacidad de Shannon para todos los anillos impares; ese problema sigue abierto. Sin embargo, demuestra que al combinar la intuición matemática humana con el poder de reconocimiento de patrones de la IA moderna, podemos ampliar los límites de lo que sabemos. Los investigadores verificaron cada uno de sus nuevos grupos de mensajes para asegurar que fueran matemáticamente correctos, demostrando que la IA no solo adivinó, sino que realmente encontró soluciones válidas y más grandes que los expertos humanos habían pasado por alto. Esto sugiere que el futuro de la resolución de complejos acertijos matemáticos podría implicar un equipo de humanos e IA trabajando juntos, con la IA actuando como una chispa creativa que nos ayuda a ver el siguiente paso en la danza de los números.

Resumen Técnico: Mejora de los Límites Inferiores para la Capacidad de Shannon de Ciclos Impares

Planteamiento del Problema
La capacidad de Shannon $\Theta(G)$ de un grafo $G$ cuantifica la tasa máxima de comunicación sin error sobre un canal ruidoso definido por $G$ . Se define como $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$ , donde $\alpha(G^d)$ es el número de independencia del $d$ -ésimo producto fuerte de $G$ . Mientras que $\Theta(C_p) = p/2$ para ciclos pares y $\Theta(C_5) = \sqrt{5}$ , los valores para ciclos impares $C_{2r+1}$ con $r > 2$ siguen siendo desconocidos. Determinar $\Theta(C_7)$ es un problema abierto notoriamente difícil. El enfoque estándar para establecer límites inferiores consiste en construir grandes conjuntos independientes en productos fuertes $C_k^d$ para maximizar la cantidad $\alpha(C_k^d)^{1/d}$ .

Metodología
Los autores emplean una interacción iterativa con un Modelo de Lenguaje Extenso (LLM), específicamente ChatGPT-5.6 Sol Pro, para descubrir construcciones combinatorias explícitas de conjuntos independientes. La metodología difiere de las búsquedas heurísticas tradicionales (como el recocido simulado o algoritmos de búsqueda local), las cuales los autores señalan que fallaron en alcanzar los límites reportados a pesar de extensos intentos.

El proceso consistió en:

Prompting: Los autores proporcionaron al LLM parámetros específicos: la longitud del ciclo ( $k$ ), la dimensión del producto ( $d$ ), la mejor construcción existente conocida y una cardinalidad objetivo para la mejora.
Generación y Ejecución: El modelo generó programas de búsqueda, los ejecutó dentro de su entorno y devolvió conjuntos independientes candidatos.
Refinamiento Iterativo: Los autores entablaron prompts de seguimiento para presionar la cardinalidad más allá de los resultados iniciales encontrados por el modelo.
Verificación: Todos los conjuntos construidos fueron rigurosamente verificados por los autores para asegurar que constituyen conjuntos independientes válidos (es decir, que no hay dos vectores que difieran por como máximo 1 en cada coordenada módulo $k$ ).

Contribuciones Clave y Resultados
El artículo presenta límites inferiores mejorados para la capacidad de Shannon de cuatro ciclos impares específicos mediante la construcción de conjuntos independientes más grandes en sus productos fuertes:

$C_7$ (Ciclo de 7): Los autores construyeron un conjunto independiente de tamaño 134,753 en el 10-producto fuerte $C_7^{10}$ . Esto mejora el límite anterior de $367^{1/5}$ (proveniente de un conjunto independiente de tamaño 367 en $C_7^5$ ).
- Nuevo Límite Inferior: $\Theta(C_7) \geq 134753^{1/10} > 3.258020$ (anteriormente $> 3.257865$ ).
- Estrategia de Construcción: El conjunto fue derivado modificando el conjunto conocido de tamaño 367 $R$ de Polak y Schrijver. Los autores eliminaron vectores específicos de $R$ para formar un subconjunto $B$ , luego construyeron el conjunto final $I$ usando el producto cartesiano $B \times B$ aumentado con vectores adicionales derivados de $R$ y transformaciones específicas.
$C_{11}$ (Ciclo de 11): Se encontró un conjunto independiente de tamaño 21,909 en $C_{11}^6$ .
- Nuevo Límite Inferior: $\Theta(C_{11}) \geq 21909^{1/6} > 5.289773$ (anteriormente $148^{1/3} > 5.289572$ ).
- Estrategia de Construcción: Partiendo del conjunto de tamaño 148 en $C_{11}^3$ , los autores definieron subconjuntos específicos ($DL, DR, BL, BR$) y conjuntos de vectores auxiliares ( $F_A, F_B, \dots$ ) para construir el conjunto en el 6-producto.
$C_{13}$ (Ciclo de 13): Se encontró un conjunto independiente de tamaño 62,530 en $C_{13}^6$ .
- Nuevo Límite Inferior: $\Theta(C_{13}) \geq 62530^{1/6} > 6.300109$ (anteriormente $247^{1/3} > 6.274305$ ).
- Estrategia de Construcción: El LLM implementó una búsqueda local aleatoria en un grafo auxiliar $G_A$ (con 134 vértices) para encontrar un gran conjunto independiente $S$ de 370 vectores en $\mathbb{Z}_{13}^4$ . El conjunto final $I$ se definió como $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$ .
$C_{15}$ (Ciclo de 15): Se encontró un conjunto independiente de tamaño 8,076,974 en $C_{15}^8$ .
- Nuevo Límite Inferior: $\Theta(C_{15}) \geq 8076974^{1/8} > 7.301399$ (anteriormente $2842^{1/4} > 7.301397$ ).
- Estrategia de Construcción: Partiendo del conjunto de tamaño 2842 en $C_{15}^4$ , los autores eliminaron vectores específicos y añadieron otros para formar un conjunto base $R$ . El conjunto final se formó mediante $B \times B$ (donde $B \subset R$ ) aumentado con vectores determinados por tablas de consulta ( $W_0, W_1$ ) basadas en condiciones de adyacencia.

Adicionalmente, el artículo reporta límites inferiores mejorados sobre los números de independencia de varios productos fuertes individuales que no mejoran directamente los límites de la capacidad de Shannon (por ejemplo, $\alpha(C_{11}^4) \geq 766$ , $\alpha(C_{15}^3) \geq 383$ ).

Significancia y Reclamaciones
El artículo afirma que estos resultados representan mejoras modestas a los límites inferiores conocidos para $\Theta(C_7)$ , $\Theta(C_{11})$ y $\Theta(C_{15})$ , y una mejora más significativa para $\Theta(C_{13})$ .

La principal significancia del trabajo reside en la metodología:

Eficacia de los LLM: Las construcciones fueron descubiertas mediante la interacción iterativa con un LLM, el cual produjo conjuntos independientes que las búsquedas heurísticas manuales (incluyendo el recocido simulado y algoritmos de búsqueda local construidos por IA) no lograron encontrar a pesar de meses de esfuerzo.
Rol del Conocimiento: Los autores sugieren que el éxito del LLM puede provenir de su capacidad para aprovechar el conocimiento matemático existente y modificar conjuntos independientes conocidos mediante cambios "pequeños", resaltando el potencial de los LLM para encontrar construcciones combinatorias explícitas.
Dirección Futura: El artículo postula que estudiar los mecanismos que permiten a los LLM superar las heurísticas de búsqueda tradicionales en la búsqueda de conjuntos independientes es una dirección de investigación futura valiosa.

Los autores mantienen la modestia respecto a la magnitud de las mejoras numéricas (por ejemplo, el incremento en $\Theta(C_{15})$ es en el sexto decimal) pero enfatizan la novedad del proceso de descubrimiento. Todas las construcciones y el código están disponibles en un repositorio público.

Más como este