🔢 mathematics

Sharper upper bounds for $q$ -ary $B_2$ codes from Toeplitz SDPs

Cet article améliore les bornes supérieures sur le taux des codes $B_2$ $q$ -aires en affinant l'analyse de l'entropie de la différence de variables aléatoires via une optimisation convexe basée sur la structure de Fourier et les programmes semi-définis positifs de Toeplitz.

Auteurs originaux : Stefano Della Fiore

Publié 2026-03-31

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Stefano Della Fiore

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

Imagine que vous êtes un architecte chargé de construire des tours de communication. Votre objectif est de créer le plus grand nombre de tours possible (des codes) sans qu'elles ne s'effondrent ou ne se confondent les unes avec les autres.

Dans le monde des mathématiques et de l'informatique, ces "tours" sont des codes utilisés pour transmettre des informations. Plus précisément, ce papier parle d'un type de code très spécial appelé code B2.

Voici l'explication simple de ce que l'auteur, Stefano Della Fiore, a accompli, en utilisant des analogies du quotidien.

1. Le Problème : Éviter les collisions

Imaginez que vous avez une boîte remplie de balles de couleurs différentes (les chiffres de 0 à $q-1$ ). Vous devez créer des listes de balles (vos codes) pour que, si vous prenez deux listes et que vous les additionnez (balle par balle), le résultat soit toujours unique.

Si la liste A + la liste B donne le même résultat que la liste C + la liste D, alors il y a une collision. C'est comme si deux tours différentes s'effondraient en un seul tas de briques.
Le but est de savoir : Quelle est la taille maximale de ces listes avant qu'on ne soit obligé de commencer à faire des collisions ?

Les mathématiciens cherchent une "limite supérieure" : un plafond théorique au-delà duquel il est impossible de construire plus de tours.

2. L'Ancienne Méthode : Une règle simpliste

Dans un travail précédent (réalisé par l'auteur lui-même), on utilisait une règle très simple pour estimer ce plafond. C'était un peu comme dire : "Si je prends deux listes au hasard, il y a une petite chance qu'elles soient identiques. Si cette chance est trop faible, alors mes listes ne peuvent pas être trop grandes."

C'était une bonne estimation, mais un peu "lourde". On utilisait une règle de base (comme une règle en bois) qui ne mesurait pas les courbes fines de la réalité. On obtenait un plafond, mais il était peut-être un peu trop haut, comme si on disait "Vous pouvez construire jusqu'à 100 étages" alors que la réalité impose 90.

3. La Nouvelle Découverte : La "Danse des Ondes"

Dans ce nouveau papier, l'auteur ne se contente plus de la règle simple. Il regarde la structure interne des listes comme si elles étaient des ondes sonores ou des vagues.

L'analogie de la musique : Imaginez que chaque liste de chiffres est une mélodie. Quand on prend deux listes et qu'on les soustrait (pour voir la différence), on obtient une nouvelle mélodie.
L'auteur a réalisé que cette "mélodie de différence" ne peut pas être n'importe quelle musique. Elle doit respecter une loi physique très stricte : elle doit être toujours positive (comme une onde qui ne descend jamais sous le sol).
En mathématiques, cela s'appelle un polynôme trigonométrique non négatif. C'est un peu comme dire : "Cette mélodie ne peut pas avoir de notes fausses ou de silences interdits par la loi de la nature."

4. La Solution : Le "Scanner de Précision" (SDP)

Pour trouver le vrai plafond, l'auteur a utilisé un outil mathématique très puissant appelé Programmation Semidéfinie (SDP) avec des matrices de Toeplitz.

L'analogie du scanner médical : L'ancienne méthode était comme une radiographie simple (elle voyait les os, mais pas les détails). La nouvelle méthode est comme une IRM 3D de haute précision. Elle scanne chaque détail de la structure des codes.
En utilisant cette "IRM", l'auteur a pu voir que certaines configurations de codes, qui semblaient possibles avec l'ancienne méthode, étaient en fait impossibles car elles violaient la loi des "ondes positives".

5. Le Résultat : Un plafond plus bas (et donc plus précis)

Grâce à ce scanner ultra-précis, l'auteur a pu abaisser le plafond théorique.

Avant : "On peut avoir jusqu'à 57% de remplissage."
Maintenant : "Non, en réalité, la limite est de 55%."

Cela peut sembler une petite différence, mais en informatique, chaque pourcentage compte. Cela signifie que pour les systèmes de communication (comme les transmissions de données sur Internet ou les satellites), on sait maintenant exactement jusqu'où on peut pousser la compression des données sans risque d'erreur.

En résumé

Ce papier est comme une mise à jour du manuel de construction des tours de communication.

L'auteur a arrêté d'utiliser une règle en bois approximative.
Il a utilisé un scanner mathématique sophistiqué basé sur la musique et les ondes.
Il a découvert que les règles de sécurité étaient plus strictes qu'on ne le pensait.
Il a donné de nouvelles limites plus précises pour les codes numériques, ce qui aide les ingénieurs à construire des systèmes plus efficaces et plus sûrs.

C'est une victoire de la précision : passer d'une estimation "à peu près" à une vérité mathématique "très fine".

1. Problématique

L'article s'intéresse aux codes B2 q-aires (ou codes 2-séparables pour $q=2$ ). Un code $C_n \subset \{0, \dots, q-1\}^n$ est dit B2 si toutes les sommes de paires de mots de code (réelles) sont distinctes :
$c_i + c_j \neq c_k + c_l \quad \text{pour } \{i,j\} \neq \{k,l\}$
L'objectif est de déterminer la taux asymptotique (capacité) $R$ de tels codes, définie par :
$R = \limsup_{n \to \infty} \frac{1}{n} \log_q |C_n|$
Des bornes supérieures sur ce taux ont déjà été établies dans la littérature (notamment par Lindström, Della Fiore-Dalai, et Wang) en utilisant des arguments d'entropie appliqués à des paires de mots de code ou de leurs suffixes. Cependant, les bornes existantes pour certaines valeurs de $q$ (notamment $q \in \{9, \dots, 13\}$ ) peuvent être améliorées.

Le point critique de la dérivation de ces bornes réside dans la maximisation de l'entropie de la différence $D = X - Y$ de deux variables aléatoires i.i.d. $X$ et $Y$ à valeurs dans $\{0, \dots, q-1\}$ , sous la contrainte que la probabilité de collision $P(X=Y) \ge 1/q$ . Les travaux précédents ne prenaient en compte que cette contrainte de collision, ce qui conduit à une relaxation trop large.

2. Méthodologie

L'auteur propose une approche raffinée exploitant la structure analytique de Fourier complète de la distribution de la différence $D = X - Y$ .

Représentation de Fourier : La fonction caractéristique de la différence $D$ est le module carré de la fonction caractéristique de $X$ : $\psi_D(\theta) = |\phi(\theta)|^2$ . Par conséquent, la fonction de masse de probabilité (pmf) de $D$ , notée $r$ , est l'autocorrélation d'une pmf sur $\{0, \dots, q-1\}$ .
Polynôme trigonométrique non négatif : La transformée de Fourier de $r$ est un polynôme trigonométrique $R(\theta) = \sum r_k e^{ik\theta}$ qui doit être non négatif pour tout $\theta \in [0, 2\pi]$ .
Relaxation Convexe : Au lieu de maximiser l'entropie $H(D)$ uniquement sous la contrainte $r_0 \ge 1/q$ , l'article formule un problème d'optimisation convexe où l'on maximise l'entropie sous l'ensemble des contraintes suivantes :
1. $r_k \ge 0$ et $\sum r_k = 1$ (définition d'une pmf).
2. Symétrie : $r_{-k} = r_k$ .
3. Contrainte de collision : $r_0 \ge 1/q$ .
4. Contrainte de positivité spectrale : $R(\theta) \ge 0$ pour tout $\theta$ .
Formulation par Programmation Semi-Définie (SDP) : La condition $R(\theta) \ge 0$ est équivalente, d'après les théorèmes classiques (Herglotz, Fejér-Riesz), à l'existence d'une infinité de contraintes de matrices de Toeplitz semi-définies positives (PSD).
Soit $T^{(N)}(r)$ la matrice de Toeplitz construite à partir des coefficients $r_k$ . La condition est équivalente à :
$T^{(N)}(r) \succeq 0 \quad \forall N \ge 1$
L'auteur résout numériquement ce problème en tronquant la contrainte à un ordre $N_{max}$ (ici 100), transformant le problème en un programme SDP concave maximisable.

3. Contributions Clés

Nouvelle Relaxation Spectrale : Introduction d'une relaxation basée sur l'analyse de Fourier pour la distribution de différence i.i.d., exploitant le fait que sa fonction caractéristique est un polynôme trigonométrique non négatif de degré au plus $q-1$ .
Équivalence Toeplitz-SDP : Démonstration explicite que la condition de positivité du polynôme trigonométrique est équivalente à une famille infinie de contraintes de matrices de Toeplitz PSD, reliant ainsi le problème aux résultats classiques de théorie des nombres et d'analyse harmonique.
Amélioration de la Bornes d'Entropie : Dérivation d'une borne supérieure strictement plus faible pour l'entropie maximale $h_q^F$ de la différence $X-Y$ par rapport aux bornes précédentes (qui ignoraient la structure de positivité spectrale).
Application aux Codes B2 : Intégration de cette nouvelle borne d'entropie dans la méthode « préfixe-suffixe » pour obtenir une borne supérieure asymptotique améliorée sur le taux des codes B2 q-aires.
Résultats Numériques : Calcul de nouvelles bornes pour $q \in \{9, 10, 11, 12, 13\}$ qui surpassent les meilleures bornes connues dans la littérature.

4. Résultats Principaux

L'article établit le théorème suivant pour le taux asymptotique $R_b$ des codes B2 q-aires :
$R_b \le \frac{h_q^F}{\log q + h_q^F}$
où $h_q^F$ est la valeur optimale du problème d'optimisation convexe (8) ou de son équivalent SDP tronqué (9).

Les évaluations numériques (Tableau I de l'article) montrent une amélioration significative par rapport aux travaux de Lindström [3], Della Fiore-Dalai [5] et Wang [7] :

$q$	Nouvelle borne ( $R_{new}$ )	Meilleure borne précédente (ex: Wang [7])	Amélioration
9	0.55792	0.55841	Oui
10	0.55611	0.55727	Oui
11	0.55457	0.55626	Oui
12	0.55323	0.55536	Oui
13	0.55206	0.55454	Oui

Pour $q=9$ , la borne passe de $\approx 0.5584$ à $\approx 0.5579$ . L'amélioration est systématique pour les valeurs testées.

5. Signification et Perspectives

Rigueur Théorique : Ce travail démontre que les contraintes de positivité de Toeplitz (issues de la structure d'autocorrélation) sont essentielles pour contraindre efficacement l'entropie des différences, au-delà de la simple probabilité de collision. Il comble un écart entre les méthodes d'information théorique classiques et les outils d'optimisation convexe moderne.
Impact sur les Codes : Bien que l'amélioration des taux soit numériquement modeste (de l'ordre de $10^{-3}$ ), elle représente une avancée théorique importante dans la compréhension des limites fondamentales des codes B2, qui sont cruciaux pour les systèmes de communication sans fil, le codage de canal et les problèmes de reconstruction de signaux.
Ouvertures : L'auteur suggère que cette approche peut être étendue pour :
- Ajouter d'autres contraintes nécessaires aux autocorrélations (moments supplémentaires).
- Adapter la méthode à d'autres familles de codes utilisant des arguments préfixe-suffixe.
- Explorer des relaxations SDP pour des sommes d'ordre supérieur (conditions de type $B_h$ ).

En résumé, cet article utilise la puissance des Semi-Definite Programs (SDP) et de l'analyse de Fourier pour affiner les bornes théoriques de l'information, offrant les meilleures limites connues à ce jour pour les codes B2 q-aires dans une plage de paramètres spécifique.