Proximity Gaps Conjecture Fails Near Capacity over Prime Fields

Ce rapport démontre que pour une famille spécifique de codes de Reed-Solomon, la conjecture des écarts de proximité échoue à des rayons situés à $O(1/\log n)$ en dessous du taux de capacité sur les corps premiers.

L'essentiel

Imaginez que vous êtes un architecte chargé de construire des ponts très résistants (ce sont les codes de Reed-Solomon, utilisés pour protéger les données sur votre disque dur ou dans les transmissions spatiales).

L'objectif de ce rapport, écrit par Antonio Kambir´e en 2026, est de démontrer qu'il existe un "trou" dans la sécurité de certains de ces ponts, un trou que l'on pensait impossible à trouver.

Voici l'explication simple, étape par étape, avec des analogies du quotidien.

1. Le Contexte : La "Règle du Pont" (La Conjecture des Gaps de Proximité)

Imaginez que vous avez une ligne droite imaginaire dans l'espace. Sur cette ligne, vous placez des points.

• La règle habituelle : Si vous trouvez beaucoup de points sur cette ligne qui sont très proches d'un "pont parfait" (un code valide), alors la ligne entière doit être une version un peu tordue de ce pont. En d'autres termes, si la majorité des points sont "presque bons", alors toute la ligne est "presque bonne". C'est ce qu'on appelle la conjecture des gaps de proximité.
• La limite de sécurité : Jusqu'à présent, les mathématiciens savaient que cette règle fonctionnait très bien tant que les points n'étaient pas trop loin du pont parfait (jusqu'à une certaine limite appelée "borne de Johnson").

2. La Découverte : Le Pont qui s'effondre près de la Capacité Maximale

Le rapport de Kambir´e dit : "Attendez une minute ! Si on pousse le pont à sa limite absolue de capacité (quand on essaie de transporter le maximum de données possible), cette règle ne fonctionne plus."

Il a construit un exemple précis où :

1. On prend une ligne droite.
2. On y place énormément de points qui sont très, très proches d'un pont valide (à une distance infime).
3. Pourtant, la ligne entière n'est pas du tout proche d'un pont valide.

C'est comme si vous regardiez une rangée de 100 chaises. 99 d'entre elles sont parfaitement alignées avec le mur. Vous vous attendez à ce que la 100ème le soit aussi, ou que toute la rangée soit juste un peu décalée. Mais ici, la rangée entière est en fait tordue de manière chaotique, même si presque toutes les chaises semblent bien alignées individuellement.

3. Comment ont-ils fait ? (L'Analogie du "Jeu de Mots")

Pour prouver cela, l'auteur utilise deux ingrédients magiques :

A. L'ingrédient Mathématique (Le "Lego")
Il utilise une structure très précise basée sur des nombres spéciaux (des racines de l'unité). Imaginez que vous avez un ensemble de briques Lego. Il montre que si vous combinez certaines briques spécifiques (des sommes de nombres), vous pouvez créer des formes qui ressemblent presque à un château parfait, mais qui ne le sont pas tout à fait.

B. L'ingrédient Numérique (Le "Magicien des Nombres Premiers")
C'est ici que ça devient fascinant. Pour que son exemple fonctionne, il a besoin de trouver un nombre premier (un nombre comme 7, 13, 17...) qui agit comme un "filtre" parfait.

• Il utilise un théorème ancien (le théorème de Linnik) pour dire : "Il existe toujours un nombre premier caché quelque part dans une grande boîte de nombres, qui permet à toutes nos combinaisons de rester distinctes."
• C'est comme chercher une aiguille dans une botte de foin, mais le théorème garantit que l'aiguille est là, et qu'elle est la bonne pour faire fonctionner le tour de magie.

4. Pourquoi est-ce important ?

Dans le monde réel, les ingénieurs utilisent ces codes pour envoyer des données. Ils pensent : "Si on peut corriger les erreurs jusqu'à une certaine limite, tout va bien."

Ce rapport dit : "Attention ! Si vous poussez votre système à sa limite théorique maximale (la capacité), vous pourriez penser que tout est sécurisé parce que la plupart des points semblent corrects, alors qu'en réalité, le système entier est corrompu."

C'est une mise en garde cruciale pour les futurs systèmes de communication : ne soyez pas trop confiants lorsque vous êtes juste en dessous de la limite maximale.

En résumé

Ce papier est comme un test de crash d'une voiture de course.

• La conjecture disait : "Si les pneus avant sont bons, la voiture roule bien."
• L'auteur a construit une voiture où les pneus avant sont presque parfaits, mais où le châssis entier est brisé.
• Il a utilisé des mathématiques très pointues (théorie des nombres) pour prouver que ce cas de figure est possible, non pas dans un laboratoire imaginaire, mais dans les systèmes réels utilisés sur les champs de nombres premiers.

C'est une preuve élégante que la nature a parfois des surprises, même là où l'on croyait avoir tout compris.

Résumé technique

1. Problématique et Contexte

Le rapport s'attaque à la conjecture des écarts de proximité (proximity gaps conjecture), introduite initialement dans la littérature récente (référence [2] du texte). Cette conjecture postule un phénomène de corrélation fort dans les codes de Reed-Solomon (RS) : si un grand nombre de points sur une droite affine $f + zg$ sont chacun proches d'un code de Reed-Solomon $C$, alors la droite entière doit être « expliquée » par une paire de mots de code voisins. Formellement, cela signifie que la paire $(f, g)$ doit être proche du code entrelacé $C^2$, une condition appelée accord corrélé (correlated agreement).

Bien que ce phénomène soit bien compris jusqu'à la borne de Johnson, son comportement au-delà de cette borne, et particulièrement près de la capacité informationnelle du code (le taux $1 - k/n$), reste une zone de recherche active.

L'objectif principal de ce papier est de démontrer que la conjecture des écarts de proximité échoue pour une famille spécifique de codes de Reed-Solomon sur des corps premiers, à des rayons de distance qui sont $O(1/\log n)$ en dessous de la capacité théorique.

2. Méthodologie

La preuve, qui développe une ébauche initiale de Krachun et Kazanin [4], repose sur une construction explicite combinant deux domaines distincts :

A. Argument de Théorie des Codes (Construction du Contre-exemple)

Les auteurs construisent une droite affine $L = \{f + \lambda g \mid \lambda \in \mathbb{F}_p\}$ dans l'espace des mots $D^p$ telle que :

1. Proximité individuelle : Pour de nombreuses valeurs de $\lambda$, le mot $f + \lambda g$ est très proche du code $C$ (distance de Hamming $\le \delta$).
2. Absence d'accord corrélé : La paire $(f, g)$ n'est pas proche du code entrelacé $C^2$ à la même distance.

La construction utilise une structure algébrique basée sur des sous-groupes multiplicatifs et des sommes d'ensembles (sumsets) :

• Soit $H$ un sous-groupe multiplicatif de $\mathbb{F}_p^*$.
• On définit $f = X^{rm}$ et $g = X^{(r-1)m}$.
• On considère les sommes de $r$ éléments distincts de $H$. Pour tout $\lambda$ formé par une telle somme, on montre que le polynôme $X^{rm} - \lambda X^{(r-1)m}$ coïncide avec un polynôme de degré inférieur ou égal à $k$ sur un sous-ensemble de taille $(1-\delta)n$.
• Par contradiction, on démontre que si un accord corrélé existait, cela impliquerait qu'un polynôme de degré $k$ aurait trop de racines, ce qui est impossible.

B. Argument de Théorie des Nombres (Existence des Paramètres)

Pour garantir l'existence d'un nombre polynomial de tels paramètres $\lambda$ (et donc de points proches), les auteurs doivent s'assurer que les sommes d'éléments distincts de $H$ sont toutes distinctes dans le corps fini $\mathbb{F}_p$.

• Ils utilisent une version quantitative du théorème de Linnik pour prouver l'existence de nombres premiers $p$ dans un intervalle spécifique $[4s, 8s]$ tels que $p \equiv 1 \pmod n$.
• Ils effectuent un dénombrement des « mauvais » nombres premiers (ceux qui provoquent des collisions de sommes via le résultant de polynômes) et montrent que, pour des paramètres bien choisis, il existe toujours un « bon » nombre premier $p$ qui préserve la distinctivité des sommes.

3. Résultats Principaux

Le théorème principal (Théorème 1) établit que pour toute constante $C > 0$ et tout taux $\rho \in (0, 1/2)$, il existe une infinité de longueurs de bloc $n$ et de dimensions $k$ telles que :

• Distance d'échec : La conjecture échoue pour un rayon de distance $\delta = (1 - k/n) - \Omega(1/\log n)$. Autrement dit, la distance est très proche de la capacité $1 - \rho$.
• Existence de la droite : Il existe un corps premier $\mathbb{F}_p$ (avec $p < n^A$) et un code de Reed-Solomon $C = RS[\mathbb{F}_p, D, k]$ tels qu'il existe des mots $f, g$ formant une droite $L$.
• Quantité de points proches : Il y a au moins $n^C$ scalaires distincts $z \in \mathbb{F}_p$ pour lesquels la distance de Hamming $\Delta(f + zg, C) \le \delta$.
• Échec de l'accord corrélé : Simultanément, la distance de la paire à l'entrelacé est strictement supérieure : $\Delta((f, g), C^2) > \delta$.

Les paramètres sont construits de manière explicite :

• $n = s \cdot m$ et $k = (r-2)m$.
• Le paramètre $s$ est choisi comme une puissance de 2 dépendant de $\rho$ et $C$.
• La preuve montre que le nombre de sommes distinctes croît comme $n^{\rho K \log(1/(2\rho))}$, ce qui permet de satisfaire la condition de quantité $n^C$.

4. Contributions Clés

1. Réfutation explicite près de la capacité : Le papier fournit la première preuve détaillée et auto-contenue montrant que la conjecture des écarts de proximité ne tient pas à des distances $O(1/\log n)$ de la capacité, brisant ainsi l'hypothèse que le phénomène pourrait s'étendre jusqu'à la limite informationnelle.
2. Construction paramétrée : Contrairement à des preuves d'existence non constructives, les auteurs donnent des choix de paramètres explicites (taille du corps, dimension du code, distance) reliant la théorie des codes à la théorie analytique des nombres.
3. Lien avec la décodabilité : En référence au travail concurrent (Appendice A.5 de [3]), ce résultat est crucial pour formaliser des conjectures sur les propriétés de décodage en liste et de décodage par courbes des codes de Reed-Solomon sur les corps premiers, suggérant des limites fondamentales à l'information théorique.

5. Signification et Impact

Ce travail a des implications profondes pour la théorie du codage et la cryptographie :

• Limites des algorithmes de décodage : Il indique que les algorithmes qui reposent sur l'hypothèse d'accord corrélé (souvent utilisés pour le décodage au-delà de la borne de Johnson) ne peuvent pas garantir un succès jusqu'à la capacité informationnelle pour les codes de Reed-Solomon sur les corps premiers.
• Complexité de la décodage en liste : Cela suggère que la décodabilité en liste (list-decodability) des codes RS sur les corps premiers pourrait être plus complexe que prévu, avec des limites potentielles avant d'atteindre la borne de capacité.
• Sécurité cryptographique : Étant donné que les codes de Reed-Solomon sont utilisés dans divers schémas cryptographiques (comme les preuves à divulgation nulle de connaissance ou les codes correcteurs d'erreurs dans les systèmes de stockage), comprendre ces échecs de proximité est essentiel pour évaluer la robustesse de ces systèmes face à des attaques basées sur la décodabilité.

En résumé, ce rapport démontre rigoureusement que la structure géométrique des codes de Reed-Solomon sur les corps premiers présente des « trous » (gaps) significatifs près de la capacité, empêchant l'extension de la propriété d'accord corrélé jusqu'à la limite informationnelle.