🔢 mathematics

New lower bounds for constant-weight codes via seeded bit-swap tabu search

Cet article présente 124 nouvelles constructions de codes binaires à poids constant utilisant une recherche tabou par permutation de bits amorcée, qui améliorent les bornes inférieures existantes pour $A(n,d,w)$ et, par conséquent, améliorent les bornes inférieures des nombres de kissing pour les dimensions 32, 33, 34 et 37.

Auteurs originaux : William Echols

Publié 2026-08-17

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : William Echols

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 de boucler une valise pour un voyage, mais avec une règle très étrange : chaque article que vous y mettez doit être exactement de la même taille, et aucun des articles ne peut être trop similaire aux autres. S'ils sont trop semblables, ils pourraient s'embrouiller dans l'obscurité, provoquant le chaos. Dans le monde de la communication numérique, cette « valise » est un message, les « articles » sont des motifs de zéros et de uns (des bits), et la « taille » est le nombre de uns présents dans le motif. C'est le casse-tête des codes à poids constant. Les scientifiques utilisent ces codes pour envoyer des données de manière fiable sur des canaux bruyants, comme le Wi-Fi ou la radio de l'espace profond, garantissant que même si quelques bits sont brouillés, le récepteur peut toujours comprendre ce qui a été envoyé. L'objectif est simple mais incroyablement difficile : faire entrer autant d'articles uniques et distincts que possible dans la valise sans qu'ils ne se cognent les uns les autres. Plus la valise est grande (plus vous pouvez de codes), plus vous pouvez envoyer d'informations à la fois.

Entrez William Echols, qui a décidé de s'attaquer à ce problème de rangement avec une touche d'ingéniosité. Au lieu de commencer avec une valise vide et d'y jeter des articles au hasard, en espérant qu'ils rentrent, il a utilisé une approche « ensemencée ». Pensez-y de cette façon : si vous voulez construire un meilleur château en Lego, vous ne partez pas de zéro ; vous prenez un excellent château existant, vous retirez quelques briques et vous les échangez pour voir si vous pouvez en faire un plus grand ou plus solide. Echols a utilisé une méthode informatique appelée recherche tabou, qui est comme un explorateur très têtu qui refuse de refaire ses pas (pour éviter de tourner en rond) et continue de tester de nouveaux chemins. En « ensemençant » cet explorateur avec des conceptions de codes existantes de haute qualité, il a réussi à trouver 124 nouveaux arrangements de rangement plus grands qui n'avaient jamais été découverts auparavant. Ces nouveaux arrangements améliorent les limites inférieures de la quantité de messages que nous pouvons envoyer, et ils nous aident même à comprendre combien de sphères peuvent toucher une sphère centrale dans un espace de grande dimension — un concept connu sous le nom de « nombres de baisers » (kissing numbers).

Le casse-tête du rangement et la graine magique

Dans le monde numérique, les données ne sont que de longues chaînes de zéros et de uns. Parfois, pour rendre les choses robustes, nous n'autorisons que des chaînes qui possèdent un nombre spécifique de uns. Par exemple, si nous disons que le « poids » est de 5, chaque chaîne doit contenir exactement cinq uns et le reste des zéros. Maintenant, imaginez que vous avez une collection de ces chaînes. Pour éviter les erreurs, chaque chaîne de votre collection doit être suffisamment différente de toutes les autres. Si deux chaînes sont trop similaires, un peu de bruit pourrait transformer l'une en l'autre, et le récepteur serait confus. La « distance » entre elles se mesure par le nombre d'emplacements où elles diffèrent.

La grande question dans ce domaine est la suivante : Quel est le nombre maximum de chaînes que vous pouvez faire entrer dans votre collection ? Ce nombre maximum est appelé $A(n, d, w)$ , où $n$ est la longueur de la chaîne, $d$ est la distance minimale requise, et $w$ est le nombre de uns. Pendant des décennies, des mathématiciens et des informaticiens ont tenté de trouver les plus grandes collections possibles pour diverses configurations. Ils ont trouvé de très bonnes collections, mais ils ne savent souvent pas s'ils ont trouvé la plus grande possible. Ils savent simplement qu'ils ne peuvent pas faire mieux qu'un certain nombre.

La stratégie « ensemencée »

Les tentatives précédentes pour trouver ces nombres maximums à l'aide de recherches informatiques ressemblaient souvent à une errance dans une forêt obscure. Les ordinateurs partaient de suppositions aléatoires et, bien qu'ils trouvent parfois de bons chemins, ils restaient souvent coincés dans des clairières locales qui ressemblaient au sommet d'une montagne, mais qui n'en étaient pas une. Ils s'arrêtaient là, pensant avoir trouvé le meilleur code possible, alors qu'un bien plus grand se trouvait juste derrière la prochaine colline.

Echols a réalisé que la clé était d'arrêter de partir de zéro. Il a utilisé une technique d'initialisation par ensemencement. Au lieu de générer un point de départ aléatoire, il a pris un code existant de haute qualité (une « graine ») et l'a utilisé pour lancer la recherche.

Il a procédé de deux manières ludiques :

Ensemencement direct : Il a pris un code existant et lui a ajouté un mot supplémentaire, choisi avec soin pour causer le moins de « problèmes » possible (déficits de distance). Cela a créé un point de départ légèrement plus grand et légèrement désordonné.
Ensemencement par voisinage : Il a regardé des codes pour des problèmes légèrement différents. Par exemple, s'il voulait un code de longueur 30, il pouvait prendre un excellent code de longueur 29, ajouter un zéro à chaque mot pour les rendre de longueur 30, puis l'utiliser comme point de départ. Ou encore, il pouvait prendre un code de longueur 31, en retirer un zéro, et l'utiliser.

Une fois qu'il a obtenu ces points de départ « ensemencés », il a lancé sa recherche tabou par échange de bits. Imaginez cette recherche comme un jeu de chaises musicales où les chaises sont les positions des uns dans les chaînes. L'algorithme échange les bits, essayant de rendre les chaînes plus distinctes. La partie « tabou » signifie que l'algorithme garde en mémoire les mouvements qu'il vient de faire et refuse de les annuler immédiatement, ce qui le force à explorer de nouveaux territoires plutôt que de tourner en rond.

Les résultats : 124 nouvelles découvertes

En utilisant cette stratégie intelligente d'ensemencement, Echols a trouvé 124 nouvelles constructions qui ont battu les records précédemment connus. Il ne s'agit pas seulement de petites améliorations ; certaines sont des bonds massifs.

Par exemple :

Pour un code de longueur 39 avec des contraintes spécifiques, l'ancien record était de 1 014 mots. La nouvelle méthode a trouvé 1 118 mots. Un gain de 104 !
Pour la longueur 40, le record est passé de 1 170 à 1 230.
Pour la longueur 56, le nombre est passé de 2 414 à 2 477.

Ces chiffres représentent le nombre maximum de messages uniques que nous pouvons désormais garantir d'envoyer sans confusion pour ces paramètres spécifiques. L'article ne prétend pas que ce sont les absolus maximums possibles (la véritable limite mathématique), mais il prouve que nous pouvons certainement faire mieux que ce que nous pensions. Cela pousse la « limite inférieure » plus haut, ce qui signifie que nous savons avec certitude que nous pouvons faire entrer au moins ce nombre d'articles dans la valise.

Nombres de baisers : un effet secondaire surprenant

C'est ici que l'histoire devient encore plus intéressante. L'article aborde également un concept appelé nombres de baisers (kissing numbers). Imaginez que vous avez une énorme balle au milieu d'une pièce. Combien d'autres balles de la même taille pouvez-vous placer autour d'elle de sorte qu'elles touchent toutes la balle centrale sans se chevaucher ? Dans un espace à 3 dimensions, la réponse est 12. Mais dans des dimensions supérieures (comme 32 ou 33 dimensions), la réponse est beaucoup plus difficile à trouver.

Les mathématiques de ces nombres de baisers sont profondément liées aux codes à poids constant qu'Echols a trouvés. Parce qu'il a amélioré les codes pour des paramètres spécifiques (notamment $A(n, 8, 8)$ ), il a automatiquement amélioré les limites inférieures des nombres de baisers pour les dimensions 32, 33, 34 et 37.

Par exemple, pour la dimension 32 ( $\tau_{32}$ ), l'estimation précédente était qu'au moins 345 408 balles pouvaient toucher la balle centrale. Avec les nouveaux codes, ce nombre passe à 346 432. C'est une augmentation en pourcentage assez faible, mais dans le monde de la géométrie de haute dimension, trouver ne serait-ce qu'une balle supplémentaire qui s'insère est une victoire significative.

Ce qu'il faut retenir

William Echols n'a pas seulement trouvé de meilleurs codes ; il a montré qu'en étant intelligent sur la manière de commencer votre recherche — en utilisant des « graines » issues des connaissances existantes plutôt qu'en partant de zéro — vous pouvez trouver de bien meilleures solutions. L'article prouve que 124 améliorations spécifiques sont possibles, et il nous donne un nouveau plancher plus élevé pour la quantité de données que nous pouvons emballer de manière fiable dans ces chaînes numériques. C'est un rappel que, parfois, la meilleure façon d'avancer est de s'appuyer sur ce que nous savons déjà, plutôt que d'essayer de tout reconstruire à partir de rien.

Résumé Technique : Nouvelles bornes inférieures pour les codes à poids constant via une recherche tabou par permutation de bits avec amorçage

Énoncé du problème
L'article traite de la construction de codes binaires à poids constant, définis comme des ensembles de mots binaires de longueur $n$ où chaque mot possède un poids de Hamming fixe $w$ et une distance de Hamming minimale par paire $d$ . L'objectif central est de déterminer $A(n, d, w)$ , la taille maximale d'un tel code. Bien que des efforts computationnels importants aient précédemment établi des bornes inférieures pour divers ensembles de paramètres, la recherche de bornes plus fortes demeure un problème d'optimisation combinatoire difficile. Les approches métaheuristiques existantes, y compris la recherche tabou standard, ont historiquement produit des résultats plus faibles que les bornes connues ou d'autres algorithmes.

Méthodologie
L'auteur propose une modification de l'algorithme de recherche tabou par permutation de bits de Rosin [8] en introduisant une stratégie d'amorçage par semence (seeded initialization). Plutôt que d'initialiser la recherche avec des mots générés aléatoirement, la méthode utilise un « démarrage à chaud » (warm-start) en utilisant des mots-codes issus de codes existants ayant les mêmes paramètres ou des paramètres voisins.

La méthodologie comprend deux techniques d'amorçage principales :

Amorçage Direct : Pour un $(n, d, w)$ cible, l'algorithme utilise un code $S$ existant de mêmes paramètres. Il construit une bibliothèque d'ensembles d'initialisation en ajoutant un mot $v$ à $S$ qui minimise la « pénalité de déficit de distance » agrégée (la somme des violations de la contrainte de distance minimale). La recherche tabou par permutation de bits est ensuite exécutée plusieurs fois (jusqu'à $4|E|$ , où $E$ est l'ensemble des mots à déficit minimal) en utilisant des échantillons aléatoires de cette bibliothèque. Crucialement, le mécanisme de redémarrage est omis pour préserver la semence fournie.
Amorçage par Voisinage : Cette technique exploite des codes provenant d'ensembles de paramètres adjacents pour renforcer les certificats.
- Allongement : Un certificat existant pour $A(n-1, d, w)$ est étendu à une longueur $n$ .
- Raccourcissement : Un certificat pour $A(n+1, d, w)$ est raccourci par la suppression d'une coordonnée (tranche zéro) pour former des mots de longueur $n$ .
- Puisque ces codes intermédiaires sont souvent plus petits que la taille cible $s$ , l'algorithme les complète avec des mots choisis aléatoirement présentant un déficit minimal. Bien que cela viole temporairement la propriété de distance minimale, la recherche tabou par permutation de bits consécutive répare l'ensemble pour former un code valide.
  L'implémentation évite l'intensité computationnelle du recalcul de l'ensemble de déficit minimal $E$ après chaque insertion ; au lieu de cela, elle calcule $E$ initialement et effectue un échantillonnage uniforme avec remise. L'algorithme est conçu pour être appliqué successivement à sa propre sortie, en variant les méthodes d'amorçage entre les itérations pour échapper aux optima locaux.

Contributions Clés et Résultats
La principale contribution de ce travail est la découverte de 124 nouvelles constructions qui améliorent les bornes inférieures existantes pour $A(n, d, w)$ . Ces résultats sont vérifiés par rapport à la table en ligne de Brouwer [2].

Codes à poids constant : Le Tableau 1 de l'article détaille les améliorations pour une large gamme de paramètres. Les gains notables incluent :
- $A(39, 8, 7)$ amélioré de 1014 à 1118 (+104).
- $A(40, 8, 7)$ amélioré de 1170 à 1230 (+60).
- $A(56, 6, 5)$ amélioré de 2414 à 2477 (+63).
- Des améliorations significatives sont également observées pour les paramètres impliquant $d=10$ et divers poids.
Nombres de Kissing (Kissing Numbers) : En tant que corollaire direct des améliorations des bornes sur $A(n, 8, 8)$ $A (n, 8, 8)$ pour $n \in \{32, 33, 34, 37\}$ $n \in {32, 33, 34, 37}$ , l'article dérive des bornes inférieures améliorées pour les nombres de Kissing $\tau_n$ $τ_{n}$ . Spécifiquement :
- $\tau_{32}$ est amélioré de 345 408 à 346 432 (+1 024).
- $\tau_{33}$ est amélioré de 360 640 à 362 048 (+1 408).
- $\tau_{34}$ est amélioré de 380 868 à 381 124 (+256).
- $\tau_{37}$ est amélioré de 494 312 à 496 232 (+1 920).

Signification et Revendications
L'article affirme que la méthode d'amorçage par semence proposée surmonte efficacement les limitations des implémentations précédentes de la recherche tabou, qui avaient auparavant produit des bornes plus faibles. En utilisant des informations provenant d'ensembles de paramètres équivalents et voisins, la méthode parvient à naviguer dans l'espace de recherche pour trouver des bornes inférieures plus fortes là où l'initialisation aléatoire avait échoué. Ce travail sert de démonstration pratique du fait que le « démarrage à chaud » des métaheuristiques avec des semences de haute qualité dérivées de problèmes de codage connexes peut produire des améliorations immédiates et vérifiables en théorie du codage combinatoire. L'auteur rend les codes générés publics afin de faciliter toute vérification et recherche ultérieures.

Le casse-tête du rangement et la graine magique

La stratégie « ensemencée »

Les résultats : 124 nouvelles découvertes

Nombres de baisers : un effet secondaire surprenant

Ce qu'il faut retenir

Articles similaires