GREYC

GREYC

La réduction des réseaux et les présentations de $GL_n(\mathbb {Z})$.

C'est une approche originale d'envisager les problèmes algorithmiques au sein des réseaux. Un algorithme de réduction est aussi un algorithme de décomposition d'une matrice unimodulaire, selon certaines règles.

Le problème des présentations du groupe des matrices unimodulaires de rang $n$ (et de certains de ses groupes quotients) a été déjà considéré par NIELSEN en 1924 (les automorphismes du groupe libre) et par MAGNUS en 1933 (les automorphismes du groupe à $n$ générateurs avec comme seuls relateurs la commutativité entre les générateurs).

Par ailleurs, les générateurs de $GL_n(\mathbb {Z})$ sont plus ou moins les transformations élémentaires qui interviennent dans les différents processus de réduction des réseaux. Comme ces algorithmes sont tous déterministes et qu'ils finissent tous, on peut alors penser qu'ils résolvent le problème de mots dans certains ensembles (groupes?) quotients de $GL_n(\mathbb {Z})$.

à mon avis, il est très intéressant d'identifier clairement ces groupes quotient (à chaque réduction, son groupe quotient). Ce serait tout d'abord une façon élégante de classer les différentes réductions.

Considérant ensuite, les algorithmes de réduction comme des systèmes de réécriture, on pourrait essayer d'identifier les règles qui les commandent.

Ce point de vue permettrait, au moins intuitivement, de mettre en évidence pour chaque dimension, les bases qui exigent le plus d'étapes pour être réduites et d'exhiber ainsi les bornes optimales pour la complexité dans le pire des cas des différents algorithmes de réduction. On pourrait peut-être distinguer ces algorithmes par leurs complexités dans le pire des cas. Cette approche pourrait également apporter des éléments de réponse à la question de la dépendance précise en la dimension du réseau, de la complexité des algorithmes de réduction, pour les valeurs optimales du paramètre d'approximation.

Cette approche est concluante en dimension $2$, mais n'apporte aucun résultat nouveau, puisque des méthodes plus directes permettent d'analyser précisément l'algorithme de Gauss (les travaux de Brigitte VALLÉE). Je reste conscient que le problème est intrinsèquement plus difficile pour les dimensions supérieures.