MÉLANGER LES MESSAGES BAT LE ROUTAGE, APRÈS 22 ANS DE DOUTE

Imaginez un réseau de câbles dans lequel plusieurs expéditeurs veulent chacun joindre leur propre destinataire. L’approche classique est le routage : chaque message voyage comme un colis le long d’un ou plusieurs chemins, et le trafic peut même être réparti entre de nombreux chemins dans n’importe quelle proportion. Le codage réseau ajoute une liberté : les nœuds intermédiaires peuvent combiner les messages qu’ils reçoivent — par exemple en les additionnant — au lieu de seulement les retransmettre.

La question est de savoir si cette liberté permet un jour de faire passer davantage de données. L’article porte sur les réseaux non orientés, où un câble peut transporter des données dans un sens ou dans l’autre, mais où les deux sens se partagent une seule capacité.

Une conjecture confirmée cas après cas

En 2004, Li et Li ont conjecturé que, dans ce cadre, le codage n’apporte aucun avantage sur le routage fractionnaire ; Harvey, Kleinberg et Rasala Lehman ont formulé la même conjecture indépendamment. Pendant deux décennies, elle a été confirmée pour une classe de réseaux après l’autre — deux sessions, certains réseaux planaires, les réseaux à six nœuds de codage au plus, et d’autres — sans jamais être tranchée en général. D’autres résultats de théorie de la complexité, comme des bornes inférieures pour le tri d’entiers en mémoire externe ou pour les circuits de multiplication, avaient même été démontrés en la supposant vraie.

La théorie connue limitait déjà l’enjeu : le codage ne peut battre le routage que d’un facteur logarithmique au plus. Et un résultat de 2017 de Braverman, Garg et Schvartzman montrait qu’un seul réseau présentant un avantage strict du codage pourrait être amplifié en un écart bien plus grand. Tout se ramenait à trouver un exemple fini.

Additionner suffit

L’annexe décrit le gadget de base, qui montre pourquoi le mélange peut aider. Placez plusieurs sources autour d’un nœud central v, leurs destinataires autour d’un autre nœud w, et reliez v et w par un câble. Chaque source a aussi de petits chemins latéraux vers les autres destinataires. En trois tours, le câble du milieu transporte la somme de tous les messages ; chaque destinataire reçoit cette somme plus les autres messages par les chemins latéraux, et retrouve le sien par soustraction. Sans le câble du milieu, chaque source est à cinq sauts de son destinataire.

Ce gadget, tiré de travaux antérieurs de Haeupler, Wajc et Zuzic, rend le codage plus rapide, mais ne lui permet pas à lui seul de transporter plus : un long chemin peut toujours faire tourner un flux à haut débit.

Un circuit transformé en réseau

Xindan Zhang et Baochun Li, de l’université de Toronto, et Zongpeng Li, de l’université Tsinghua, ont trouvé l’étape manquante. Ils transforment un code court en calcul réversible — un circuit d’additions entières inversibles qui calcule, copie le résultat, puis défait son travail intermédiaire. Ils construisent ensuite un nouveau réseau dont les câbles physiques sont les fils de ce circuit, et donnent à chaque registre du calcul, y compris les registres de brouillon, sa propre demande expéditeur–destinataire.

Une comptabilité soigneuse du « temps » le long des fils fait le reste. Additionnées sur tous les fils, les longueurs égalent exactement les distances minimales que les demandes doivent parcourir. Mais les demandes désignées ne peuvent pas éviter certaines portes qui coûtent deux unités de plus. Le routage reste donc strictement en dessous du plein débit, tandis que le code utilise chaque câble exactement une fois et, enchaîné sur de nombreux blocs, approche un débit de un.

Ce qui est démontré

• Un réseau fini et connexe, où chaque nœud est relié à trois autres au plus et chaque câble a une capacité unitaire, sur lequel un simple code linéaire binaire bat le meilleur routage fractionnaire possible. La conjecture de 2004 est fausse.
• La même construction entière fonctionne sur tout corps fini et tout groupe abélien fini non trivial à la fois.
• En combinant des copies de façon répétée, les auteurs construisent des familles infinies de réseaux où le codage approche le plein débit tandis que le routage chute comme une puissance de 1/log n — un avantage polylogarithmique.

L’article ne donne pas le nombre de nœuds de son contre-exemple. Sa seule brique de départ est un code qui dure 13 122 tours.

Vérifié par machine

Le contre-exemple fini comme le théorème sur les familles sont formalisés dans l’assistant de preuve Lean. Selon les auteurs, un audit de 2 472 déclarations et 1 755 théorèmes montre que les preuves n’utilisent que les trois axiomes standard de Lean, sans preuve incomplète ; une revérification indépendante dans un environnement neuf a aussi réussi, mais avec le même noyau Lean.

Ce qui reste ouvert

Les auteurs listent trois questions : la vraie taille de l’avantage sur leur exemple fini, si le plafond logarithmique connu est réellement atteint, et s’il existe un petit contre-exemple. Leur dernière phrase résume la situation : « le codage aide bel et bien dans les réseaux non orientés ; reste à savoir jusqu’à quel point ».

Usage d’IA déclaré. Une note de bas de page indique que GPT-6 Astra, d’OpenAI, a aidé à développer les preuves et le code Lean.