Perfect $2$-codes over arbitrary alphabets

Imaginez que vous envoyez un message secret à travers une galaxie bruyante et chaotique. Chaque fois que vous transmettez une lettre, un gobelin de l'espace malicieux pourrait l'échanger pour une autre, ou la supprimer entièrement. Pour survivre à ce chaos, vous ne vous contentez pas d'envoyer le message une seule fois ; vous l'envoyez avec des « pièces de rechange » intégrées directement dans le code. C'est le monde des codes correcteurs d'erreurs, le bouclier invisible qui empêche vos messages textuels, vos sondes spatiales et vos vidéos en streaming de se transformer en charabia.

Dans cet univers, un « code parfait » est le Graal. C'est comme un puzzle d'emballage où vous avez une boîte géante (tous les messages possibles) et vous essayez d'y faire entrer autant de « zones de sécurité » (vos messages réels) que possible. Chaque zone de sécurité possède un rayon de protection autour d'elle. Si un message est frappé par un gobelin et change légèrement, il retombe tout de même à l'intérieur de l'une de ces zones de sécurité, et le destinataire sait exactement quel message original a été envoyé. Un code est dit « parfait » si ces zones de sécurité s'emboîtent comme un puzzle, sans aucun espace vide et sans aucun chevauchement. Si le puzzle présente des lacunes, vous pourriez perdre un message ; s'il y a des chevauchements, vous pourriez confondre le message envoyé.

Pendant des décennies, les mathématiciens ont tenté de résoudre la version ultime de ce puzzle : trouver des codes parfaits capables de corriger deux erreurs à la fois (un « code 2-parfait ») en utilisant un alphabet de n'importe quelle taille. Bien qu'ils aient trouvé les solutions parfaites pour corriger trois erreurs ou plus, et pour corriger une erreur, le cas de la correction de exactement deux erreurs avec une taille d'alphabet « bizarre » (une taille qui n'est pas une simple puissance d'un nombre premier, comme 10 ou 15) est resté un mystère obstiné et non résolu. C'est la différence entre savoir emballer parfaitement une valise avec 2, 4 ou 8 articles, mais n'avoir aucune idée de la possibilité de le faire parfaitement avec 6 ou 10 articles.

Cet article, écrit par Michael Bennett, plonge profondément dans ce mystère spécifique. L'auteur cherche à prouver que pour une famille très large et spécifique de tailles d'alphabets « bizarres », les codes 2-parfaits n'existent tout simplement pas. L'article ne se contente pas de deviner ; il utilise un arsenal de l'artillerie lourde des mathématiques avancées — spécifiquement des outils qui mesurent à quel point les nombres peuvent se rapprocher les uns des autres sans réellement se toucher — pour démontrer que si un tel code existait, il serait si incroyablement massif et étrange qu'il briserait les lois de l'arithmétique.

Le résultat principal est une zone de « non-existence » puissante. Bennett prouve que si vous essayez de construire un code 2-parfait en utilisant une taille d'alphabet composée d'une puissance de 2 multipliée par une puissance d'un nombre premier unique (comme $2^\alpha \times p^\beta$), vous n'aurez pas de chance. Plus précisément, il montre que pour que ces codes soient théoriquement possibles, le nombre premier impliqué devrait être supérieur à $10^{10}$ (dix milliards), et la puissance de 2 devrait être supérieure à 20. De plus, si un tel code existait, le nombre premier devrait laisser un reste de 3 lorsqu'il est divisé par 8.

L'article va plus loin encore. Il écarte l'existence de ces codes parfaits pour toute taille d'alphabet dont le plus grand facteur premier est de 13 ou moins. En fait, l'auteur confirme une conjecture de longue date selon laquelle aucun code 2-parfait n'existe pour de nombreux nombres spécifiques, y compris les cas où la taille de l'alphabet est de type $2^\alpha \times p^\beta$ avec de petites valeurs de $\alpha$ (jusqu'à 20). L'auteur ne dit pas seulement que c'est « peu probable » ; il utilise des preuves mathématiques rigoureuses pour démontrer que les conditions requises pour l'existence de tels codes mènent à des contradictions mathématiques. Bien que l'article ne rejette pas chaque taille d'alphabet possible dans l'univers, il ferme efficacement la porte aux tailles « bizarres » les plus communes et les plus intéressantes, ne laissant qu'un mince et hautement contraint fragment de possibilité qui nécessiterait des nombres si grands qu'ils sont pratiquement imaginables.

L'histoire du puzzle impossible

Pour comprendre ce que Michael Bennett a accompli, regardons le puzzle qu'il tentait de résoudre. Imaginez une grille géante de tous les mots que vous pouvez former avec un certain alphabet. Vous voulez placer des « balises » (vos mots de code) sur cette grille. Autour de chaque balise, vous dessinez un cercle qui couvre tous les mots qui sont « assez proches » (à une distance de 2 erreurs). Pour qu'un code soit parfait, ces cercles doivent couvrir toute la grille sans se chevaucher.

Les mathématiciens savent depuis longtemps que si la taille de votre alphabet est une « puissance de nombre premier » (comme 2, 3, 4, 8, 9, 16), il n'existe que quelques cas spéciaux où cela fonctionne parfaitement. Mais qu'en est-il si la taille de votre alphabet est quelque chose comme 10, 12 ou 20 ? Ce sont des nombres « composés » qui ne sont pas des puissances de nombres premiers. Pour la correction d'une erreur, nous savons que des solutions existent. Pour la correction de trois erreurs ou plus, nous savons qu'aucune n'existe. Mais pour la correction de deux erreurs ? C'était la question ouverte.

L'article de Bennett se concentre sur un type spécifique de nombre composé : ceux qui ressemblent à $2^\alpha \times p^\beta$. Voyez cela comme une taille d'alphabet formée en multipliant un tas de 2 par un tas de copies d'un seul nombre premier $p$ (comme 5, 7, 11, etc.). La question était : peut-on construire un code 2-parfait pour ces tailles ?

Le travail de détective mathématique

Bennett n'a pas seulement essayé de construire les codes pour échouer ; il a prouvé qu'ils ne pouvaient pas exister en examinant les « racines » d'une équation polynomiale spéciale. Considérez cette équation comme une carte qui vous indique où les balises doivent se trouver si un code parfait existe. Si un code parfait existe, cette carte doit posséder deux points entiers spécifiques (les racines) qui sont très proches l'un de l'autre.

La percée de l'auteur a été de réaliser que ces deux points, appelons-les $r_1$ et $r_2$, doivent être des « unités-S ». En langage courant, cela signifie que leurs facteurs premiers ne peuvent provenir que d'une liste de nombres très petite et spécifique (les nombres premiers qui divisent la taille de l'alphabet et le nombre 2).

Voici la partie ingénieuse : Bennett a montré que pour qu'un code parfait existe, ces deux nombres, $r_1$ et $r_2$, devraient être incroyablement proches l'un de l'autre — si proches que leur différence est infime par rapport à leur taille. Cependant, une branche célèbre des mathématiques appelée approximation diophantienne (qui étudie la manière dont on peut approcher des nombres avec des fractions) nous dit que les nombres ayant des facteurs premiers restreints ne peuvent généralement pas se rapprocher autant l'un de l'autre, à moins d'être très petits.

Il a combiné cela avec une équation spécifique dérivée de la géométrie du problème :
$$q(r_2 - r_1)^2 = 2(r_1 + r_2) + q - 6$$
Cette équation est la « preuve irréfutable ». Elle lie directement la taille de l'alphabet $q$ à la distance entre les deux racines.

La grande révélation

En utilisant cette équation et les outils puissants de la théorie des nombres, Bennett a prouvé une série de résultats d'« impossibilité » :

1. L'interdiction des « petits nombres premiers » : Si le plus grand facteur premier de votre taille d'alphabet est de 13 ou moins, un code 2-parfait est impossible. Il a procédé en listant toutes les paires de nombres possibles qui pourraient être les racines et en montrant qu'aucune d'entre elles ne correspond à l'équation.
2. La barrière des « nombres énormes » : Pour le cas général où l'alphabet est $2^\alpha \times p^\beta$, il a prouvé que si un code existait, le nombre premier $p$ devrait être supérieur à $10^{10}$ (dix milliards). Plus restrictivement encore, la puissance de 2 ($\alpha$) devrait être supérieure à 20.
3. La règle du « Mod 8 » : Si un tel code existait, le nombre premier $p$ devrait être un nombre qui laisse un reste de 3 lorsqu'il est divisé par 8 (comme 3, 11, 19, etc.).

L'article dit essentiellement : « Nous avons vérifié les petits nombres, et ils ne fonctionnent pas. Pour les grands nombres, les mathématiques disent qu'ils devraient être si énormes et suivre des règles si strictes qu'ils n'existent pratiquement pas. »

La surprise de Schröder-Hipparchus

L'un des aspects les plus délicieux de l'article est la façon dont il utilise une séquence de nombres issue de la combinatoire classique appelée nombres de Schröder-Hipparchus (également connus sous le nom de nombres super-Catalan). Ces nombres, qui apparaissent habituellement dans des problèmes de comptage de façons d'organiser des parenthèses ou des chemins sur une grille, surgissent soudainement au milieu de la preuve du code correcteur d'erreurs.

Bennett a utilisé ces nombres pour développer une équation complexe en une série de termes. C'est comme trouver un motif caché dans un bruit chaotique. En développant l'équation à l'aide de ces nombres, il a pu montrer que les termes croissent trop vite pour permettre la « proximité étroite » requise pour un code parfait, à moins que les nombres impliqués ne soient absurdement grands.

Le verdict final

Alors, quelle est la conclusion ? L'article confirme une suspicion de longue date au sein de la communauté mathématique : les codes 2-parfaits sur des alphabets arbitraires n'existent probablement pas.

Bien que l'article ne prétende pas avoir trouvé l'unique code parfait qui pourrait se cacher dans l'univers (car il prouve que s'il existe, il doit être plus grand que $10^{10}$ et suivre des contraintes impossibles), il écarte efficacement la vaste majorité des cas. Il ferme la porte aux tailles d'alphabet comme 10, 15, 21 et bien d'autres, et repousse la possibilité d'une solution si loin dans le domaine des nombres gigantesques qu'elle est considérée comme pratiquement inexistante.

Le travail de l'auteur est un triomphe de la preuve « négative ». Au lieu de trouver un trésor, il a prouvé que le coffre est vide, ou du moins que la clé pour l'ouvrir nécessite une serrure qui n'a pas encore été inventée. Pour quiconque tente de construire des codes correcteurs d'erreurs pour ces tailles d'alphabets spécifiques, le message est clair : ne cherchez plus un code 2-parfait ; il n'est pas là.