Semidefinite lower bounds for covering codes

Définition du Problème
Le document traite du problème de la détermination de $K_q(n, r)$, défini comme la taille minimale d'un code de couverture $q$-aire de longueur de mot $n$ et de rayon de couverture $r$. Un ensemble de mots-codes $C \subseteq \{0, \dots, q-1\}^n$ a un rayon de couverture $r$ si l'union des boules de Hamming de rayon $r$ centrées sur les mots-codes couvre l'ensemble de l'espace de Hamming. Une instance spécifique de ce problème, $K_3(n, 1)$, est connue sous le nom de « problème des pools de football » (football pool problem), qui cherche le nombre minimal de pronostics requis pour garantir au plus une erreur sur $n$ matchs de football. Alors que les bornes supérieures sont généralement établies par la construction de codes explicites, cet article se concentre sur la dérivation de meilleures bornes inférieures pour $K_q(n, r)$.

Méthodologie
Les auteurs s'appuient sur les travaux de Gijswijt (2005), qui a introduit une borne inférieure par programmation semi-définie (SDP) pour les codes de couverture en utilisant des coupes de matrices. La méthodologie présentée dans cet article renforce cette borne grâce à trois avancées techniques primaires :

1. Contraintes de la hiérarchie de Lasserre : Les auteurs introduisent de nouvelles contraintes semi-définies inspirées de la hiérarchie de Lasserre pour les programmes 0-1. Plus précisément, ils utilisent le deuxième niveau de cette hiérarchie, qui implique l'analyse de la distribution de triplets de mots-codes. Cela conduit à la construction d'une matrice $N$ dérivée du vecteur d'incidence du code, soumise à des inégalités de couverture de la forme $\sum \lambda_i A_i(u) \ge \beta$.
2. Réduction de Symétrie via les Algèbres de Terwilliger : Pour rendre la SDP résultante calculablement traitable, les auteurs emploient une réduction de symétrie. Ils utilisent l'algèbre de Terwilliger du schéma de Hamming (cas binaires et non binaires). En identifiant les orbites de paires et de triplets de mots-codes sous l'action du groupe d'isométrie $Aut(q, n)$ (et de son sous-groupe stabilisateur $Aut_0(q, n)$), ils réduisent la dimensionnalité des variables matricielles.
   • Pour le cas binaire ($q=2$), l'algèbre $A_{2,n}$ est bloc-diagonalisée à l'aide d'un $\ast$-isomorphisme $\phi$ la mappant vers une somme directe de blocs matriciels plus petits, réduisant la complexité de $O(2^n)$ à $O(n^3)$ variables.
   • Pour le cas non binaire ($q \ge 3$), une bloc-diagonalisation similaire est appliquée à l'algèbre $A_{q,n}$, réduisant la complexité à $O(n^4)$ variables.
3. Fonction Objectif Améliorée : Le papier propose une fonction objectif plus puissante. Au lieu de minimiser le terme linéaire standard lié à la taille du code, les auteurs minimisent la trace de la variable matricielle correspondant au troisième moment de la taille du code ($|C|^3$). Ils prouvent que cet objectif cubique produit une borne inférieure strictement plus serrée que les objectifs linéaires ou quadratiques précédemment utilisés.

Contributions Clés

• Cadre Théorique : Le papier établit un cadre de SDP rigoureux pour les codes de couverture qui généralise les bornes de Schrijver pour les codes correcteurs d'erreurs au problème de la couverture. Il dérive formellement les contraintes pour la matrice $N$ et les matrices bordées $R(c, N)$ dans le contexte de la hiérarchie de Lasserre.
• Algorithmes de Réduction de Symétrie : Les auteurs fournissent des formules explicites pour la bloc-diagonalisation des algèbres de Terwilliger pertinentes pour les schémas de Hamming binaires et non binaires. Cela inclut les coefficients combinatoires détaillés ($\eta$ et $\alpha$) nécessaires pour traduire les inégalités de coupe de matrice et les contraintes de Lasserre dans l'espace de variables réduit.
• Implémentation Computationnelle : Les auteurs ont implémenté ces bornes en utilisant l'arithmétique de haute précision (BigFloats à 512 bits) via le langage de programmation Julia et le solveur SDPA-GMP. Ils ont développé un code indépendant pour valider la génération des SDP.

Résultats
Les auteurs présentent de nouvelles bornes inférieures pour $K_q(n, r)$ sur une large gamme de paramètres ($q, n, r$). Ces résultats sont compilés dans les Tables 1, 2 et 3, couvrant les cas binaires ($q=2$), ternaires ($q=3$) et quaternaires/quinaires ($q=4, 5$).

• Cas Binaire : Les nouvelles bornes améliorent les bornes inférieures connues précédemment pour diverses valeurs de $n$ et $r$ (par exemple, $K_2(13, 1)$, $K_2(21, 1)$, $K_2(13, 2)$). Les auteurs notent que bien qu'ils aient initialement trouvé des bornes améliorées pour $K_2(18, 1)$ et $K_2(30, 1)$, ces valeurs spécifiques ont été ultérieurement surpassées par Wu et Chen (2026).
• Cas Non Binaire : Des améliorations significatives sont rapportées pour les codes ternaires (problème des pools de football), tels que $K_3(13, 3)$ et $K_3(14, 4)$, ainsi que pour $q=4$ et $q=5$.
• Échelle de Calcul : Le papier rapporte le nombre de variables et de tailles de blocs pour les SDP réduits par symétrie. Par exemple, pour $n=32$ dans le cas binaire, le SDP réduit implique 1 239 variables avec une somme de carrés des tailles de blocs de 6 545. Les temps de résolution ont varié de quelques secondes à plusieurs jours selon la taille de l'instance et le nombre de coefficients non nuls dans les contraintes d'inégalité.

Signification
Le papier affirme que les techniques proposées mènent à des « bornes inférieures plus nettes » qui établissent de nouveaux records pour une large gamme de paramètres de codes de couverture. En étendant l'approche de la hiérarchie de Lasserre aux codes de couverture et en utilisant efficacement la réduction de symétrie, les auteurs démontrent que l'écart entre les bornes inférieures et supérieures connues peut être réduit. Ce travail fournit une méthode systématique pour calculer ces bornes, offrant une alternative plus puissante aux bornes de programmation linéaire et aux approches SDP précédentes qui n'exploitaient pas pleinement les contraintes de distribution de triplets ou l'optimisation de la fonction objectif spécifique. Les résultats servent de références mises à jour pour le domaine des codes de couverture et le problème des pools de football.