🤖 AI

Improved lower bounds for the Shannon capacity of odd cycles

Cet article présente des bornes inférieures améliorées pour la capacité de Shannon des cycles impairs $C_7$ , $C_{11}$ , $C_{13}$ et $C_{15}$ en construisant des ensembles indépendants plus grands dans leurs produits forts grâce à une collaboration itérative avec un grand modèle de langage.

Auteurs originaux : Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

Publié 2026-07-31

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Nathaniel Itty, Christopher D. Rosin, Chase Carstensen, Daniel Reichman

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'envoyer un message secret à travers un canal de talkie-walkie bruyant. Chaque fois que vous parlez, les parasites pourraient brouiller vos mots, transformant un « oui » en un « non ». Dans le monde de la théorie de l'information, les scientifiques posent une question très précise : quelle est la vitesse maximale à laquelle nous pouvons envoyer des messages pour que le destinataire les comprenne parfaitement, avec zéro erreur, peu importe la quantité de statique dans l'air ? Cette limite est appelée la capacité de Shannon.

Pour déterminer cela, les mathématiciens utilisent un outil appelé « graphe », qui est simplement une carte de points reliés par des lignes. Imaginez que les points soient des messages différents que vous pourriez envoyer, et les lignes les similitudes déroutantes entre eux. Si deux points sont connectés, cela signifie que ces deux messages pourraient être confondus par le bruit. L'objectif est de choisir un groupe de points (messages) qui ne sont pas connectés entre eux, afin qu'ils soient tous distincts et à l'abri de toute confusion. Plus ce groupe est grand, plus l'information que l'on peut envoyer est importante.

La partie délicate est que nous pouvons combiner ces cartes pour créer des cartes encore plus grandes et plus complexes. En empilant ces cartes, nous pouvons parfois trouver de vastes groupes de messages sûrs que nous ne pouvions pas voir auparavant. Pour certaines formes, comme les anneaux à nombre pair, nous connaissons la réponse parfaitement. Mais pour les anneaux à nombre impair (comme une forme à 7, 11 ou 13 côtés), la réponse est un mystère tenace depuis des décennies. C'est comme essayer de trouver le plus grand nombre de points non adjacents sur un bracelet torsadé et noué, et personne n'a encore trouvé l'arrangement absolument optimal.

Ce document traite d'une équipe de chercheurs qui a décidé de s'attaquer à ces anneaux impairs tenaces en utilisant un nouvel assistant de type très particulier : un Grand Modèle de Langage (LLM), qui est le même type d'IA qui alimente les agents conversationnels intelligents. Au lieu de simplement écrire du code pour chercher la réponse, ils ont traité l'IA comme un partenaire créatif. Ils ont demandé à l'IA d'examiner les meilleurs arrangements connus de messages sûrs pour ces anneaux impairs, puis de tenter de les modifier très légèrement pour les rendre encore plus grands.

Les résultats ont été étonnamment fructueux. L'équipe, travaillant avec l'IA, a découvert de nouveaux groupes plus larges de messages sûrs pour des anneaux à 7, 11, 13 et 15 côtés. Pour l'anneau à 7 côtés, ils ont trouvé un groupe de 134 753 messages sûrs, ce qui est supérieur au record précédent de 367. Pour l'anneau à 11 côtés, ils ont trouvé 21 909 messages sûrs. Pour celui à 13 côtés, ils ont trouvé 62 530, et pour l'anneau à 15 côtés, ils ont trouvé un massif 8 076 974.

Ces nombres peuvent ressembler à une simple liste de chiffres, mais ils représentent une amélioration réelle de notre compréhension de la quantité d'informations pouvant être transmises sans erreur. En trouvant ces groupes plus grands, les chercheurs ont prouvé que la vitesse maximale d'envoi de messages parfaits sur ces canaux bruyants spécifiques est légèrement plus élevée que ce que nous pensions auparavant. Par exemple, pour l'anneau à 7 côtés, la limite de vitesse est désormais connue comme étant supérieure à 3,258020, alors qu'auparavant, elle était seulement connue comme étant supérieure à 3,257865.

Ce qui rend cette histoire particulièrement passionnante, ce n'est pas seulement les chiffres, mais la manière dont ils ont été trouvés. Les chercheurs ont essayé des méthodes de recherche informatique traditionnelles, comme le recuit simulé (qui consiste à secouer une boîte de pièces de puzzle jusqu'à ce qu'elles s'emboîtent), mais ces méthodes n'ont pas réussi à trouver ces nouveaux groupes plus larges. Même les algorithmes de recherche locale construits avec l'IA n'ont pas pu atteindre ces nouveaux sommets. Ce n'est que grâce à un dialogue de va-et-vient avec l'IA, où les chercheurs lui donnaient des indices et l'IA suggérait des modifications créatives aux modèles existants, que ces nouveaux records ont été battus.

L'article ne prétend pas avoir résolu tout le mystère de la capacité de Shannon pour tous les anneaux impairs ; ce problème reste ouvert. Cependant, il montre qu'en combinant l'intuition mathématique humaine et la puissance de reconnaissance de formes de l'IA moderne, nous pouvons repousser les limites de nos connaissances. Les chercheurs ont vérifié chaque groupe de messages nouvellement découvert pour s'assurer de leur exactitude mathématique, prouvant que l'IA n'a pas simplement deviné, mais a réellement trouvé des solutions valides et plus larges que les experts humains avaient manquées. Cela suggère que l'avenir de la résolution de puzzles mathématiques complexes pourrait impliquer une équipe d'humains et d'IA travaillant ensemble, l'IA agissant comme une étincelle créative qui nous aide à voir la prochaine étape de la danse des nombres.

Résumé Technique : Amélioration des bornes inférieures de la capacité de Shannon des cycles impairs

Énoncé du problème
La capacité de Shannon $\Theta(G)$ d'un graphe $G$ quantifie le taux maximal de communication sans erreur sur un canal bruité défini par $G$ . Elle est définie par $\Theta(G) = \sup_{d \in \mathbb{N}} \alpha(G^d)^{1/d}$ , où $\alpha(G^d)$ est le nombre d'indépendance du $d$ -ième produit fort de $G$ . Alors que $\Theta(C_p) = p/2$ pour les cycles pairs et que $\Theta(C_5) = \sqrt{5}$ , les valeurs pour les cycles impairs $C_{2r+1}$ avec $r > 2$ restent inconnues. Déterminer $\Theta(C_7)$ est un problème ouvert notoirement difficile. L'approche standard pour établir des bornes inférieures consiste à construire de grands ensembles indépendants dans les produits forts $C_k^d$ afin de maximiser la quantité $\alpha(C_k^d)^{1/d}$ .

Méthodologie
Les auteurs emploient une interaction itérative avec un grand modèle de langage (LLM), spécifiquement ChatGPT-5.6 Sol Pro, pour découvrir des constructions combinatoires explicites d'ensembles indépendants. La méthodologie diffère des recherches heuristiques traditionnelles (telles que le recuit simulé ou les algorithmes de recherche locale) que les auteurs notent avoir échoué à atteindre les bornes rapportées malgré des tentatives extensives.

Le processus comprenait :

Prompting (Saisie de commandes) : Les auteurs ont fourni au LLM des paramètres spécifiques : la longueur du cycle ( $k$ ), la dimension du produit ( $d$ ), la meilleure construction existante et une cardinalité cible pour l'amélioration.
Génération et Exécution : Le modèle a généré des programmes de recherche, les a exécutés dans son environnement, et a renvoyé des ensembles indépendants candidats.
Raffinement Itératif : Les auteurs ont engagé des prompts de suivi pour pousser la cardinalité au-delà des résultats initiaux trouvés par le modèle.
Vérification : Tous les ensembles construits ont été rigoureusement vérifiés par les auteurs pour s'assurer qu'ils constituent des ensembles indépendants valides (c'est-à-dire qu'aucun des deux vecteurs ne diffère de plus de 1 dans chaque coordonnée modulo $k$ ).

Contributions Clés et Résultats
L'article présente des améliorations des bornes inférieures de la capacité de Shannon pour quatre cycles impairs spécifiques en construisant des ensembles indépendants plus grands dans leurs produits forts :

$C_7$ (Cycle de 7) : Les auteurs ont construit un ensemble indépendant de taille 134 753 dans le 10-ième produit fort $C_7^{10}$ . Cela améliore la meilleure borne précédente de $367^{1/5}$ (provenant d'un ensemble indépendant de taille 367 dans $C_7^5$ ).
- Nouvelle borne inférieure : $\Theta(C_7) \geq 134753^{1/10} > 3,258020$ (précédemment $> 3,257865$ ).
- Stratégie de construction : L'ensemble a été dérivé en modifiant l'ensemble connu de taille 367 $R$ de Polak et Schrijver. Les auteurs ont supprimé des vecteurs spécifiques de $R$ pour former un sous-ensemble $B$ , puis ont construit l'ensemble final $I$ en utilisant le produit cartésien $B \times B$ augmenté de vecteurs supplémentaires dérivés de $R$ et de transformations spécifiques.
$C_{11}$ (Cycle de 11) : Un ensemble indépendant de taille 21 909 a été trouvé dans $C_{11}^6$ .
- Nouvelle borne inférieure : $\Theta(C_{11}) \geq 21909^{1/6} > 5,289773$ (précédemment $148^{1/3} > 5,289572$ ).
- Stratégie de construction : En partant de l'ensemble de taille 148 dans $C_{11}^3$ , les auteurs ont défini des sous-ensembles spécifiques ($DL, DR, BL, BR$) et des ensembles de vecteurs auxiliaires ( $F_A, F_B, \dots$ ) pour construire l'ensemble dans le 6-ième produit.
$C_{13}$ (Cycle de 13) : Un ensemble indépendant de taille 62 530 a été trouvé dans $C_{13}^6$ .
- Nouvelle borne inférieure : $\Theta(C_{13}) \geq 62530^{1/6} > 6,300109$ (précédemment $247^{1/3} > 6,274305$ ).
- Stratégie de construction : Le LLM a implémenté une recherche locale randomisée sur un graphe auxiliaire $G_A$ (avec 134 sommets) pour trouver un grand ensemble indépendant $S$ de 370 vecteurs dans $\mathbb{Z}_{13}^4$ . L'ensemble final $I$ est défini comme $\{x \in \mathbb{Z}_{13}^6 : Ax \in S\}$ .
$C_{15}$ (Cycle de 15) : Un ensemble indépendant de taille 8 076 974 a été trouvé dans $C_{15}^8$ .
- Nouvelle borne inférieure : $\Theta(C_{15}) \geq 8076974^{1/8} > 7,301399$ (précédemment $2842^{1/4} > 7,301397$ ).
- Stratégie de construction : En partant de l'ensemble de taille 2842 dans $C_{15}^4$ , les auteurs ont supprimé des vecteurs spécifiques et en ont ajouté d'autres pour former un ensemble de base $R$ . L'ensemble final a été formé par $B \times B$ (où $B \subset R$ ) augmenté de vecteurs déterminés par des tables de recherche ( $W_0, W_1$ ) basées sur des conditions d'adjacence.

De plus, l'article rapporte des améliorations des bornes inférieures sur les nombres d'indépendance de plusieurs produits forts individuels qui n'améliorent pas directement les bornes de la capacité de Shannon (par exemple, $\alpha(C_{11}^4) \geq 766$ , $\alpha(C_{15}^3) \geq 383$ ).

Signification et Revendications
L'article affirme que ces résultats représentent des améliorations modestes des bornes inférieures connues pour $\Theta(C_7)$ , $\Theta(C_{11})$ et $\Theta(C_{15})$ , et une amélioration plus significative pour $\Theta(C_{13})$ .

La principale signification du travail réside dans la méthodologie :

Efficacité des LLM : Les constructions ont été découvertes grâce à une interaction itérative avec un LLM, qui a produit des ensembles indépendants que les heuristiques de recherche manuelle (incluant le recuit simulé et les algorithmes de recherche locale construits par IA) n'avaient pas réussi à trouver malgré des mois d'efforts.
Rôle de la Connaissance : Les auteurs suggèrent que le succès du LLM peut provenir de sa capacité à exploiter les connaissances mathématiques existantes et à modifier des ensembles indépendants connus par de "petits" changements, soulignant le potentiel des LLM pour trouver des constructions combinatoires explicites.
Direction Future : L'article pose comme hypothèse que l'étude des mécanismes permettant aux LLM de surpasser les heuristiques de recherche traditionnelles dans la recherche d'ensembles indépendants est une direction de recherche future précieuse.

Les auteurs restent modestes quant à l'ampleur des améliorations numériques (par exemple, l'augmentation de $\Theta(C_{15})$ est à la sixième décimale) mais insistent sur la nouveauté du processus de découverte. Toutes les constructions et le code sont rendus disponibles dans un dépôt public.

Articles similaires