Certifying Galois/monodromy Actions via Homotopy Graphs

1. Problématique

L'article aborde le problème de la détermination de la structure des systèmes d'équations polynomiales paramétrées de la forme $F(x; z) = 0$, où $x$ représente les variables d'inconnue et $z$ les paramètres. Pour des paramètres génériques, ces systèmes possèdent un nombre fini $d$ de solutions isolées complexes.

L'objectif central est de calculer le groupe de Galois géométrique (ou groupe de monodromie) de ce système. Ce groupe décrit comment les $d$ solutions sont permutées lorsque les paramètres $z$ parcourent des boucles dans l'espace des paramètres, évitant le lieu de branchement.

• Défi principal : Les méthodes numériques existantes (suivi de chemin par homotopie) sont rapides mais souffrent d'instabilités numériques (sauts de chemin ou "path jumping"), ce qui peut conduire à des correspondances erronées entre les solutions et donc à un calcul incorrect du groupe.
• Limitation des approches actuelles : La simple certification a posteriori d'une solution approchée (prouver qu'une solution existe près d'un point calculé) est insuffisante pour garantir que le suivi de chemin n'a pas sauté d'une branche à une autre. Il est nécessaire de certifier le processus de suivi lui-même.

2. Méthodologie

Les auteurs proposent un algorithme numérique certifié qui fusionne le suivi de chemin par homotopie avec l'arithmétique d'intervalles et une structure de graphe.

A. Suivi de chemin certifié (Certified Path Tracking)

Au lieu d'utiliser l'arithmétique flottante standard, l'algorithme utilise l'arithmétique d'intervalles pour encadrer rigoureusement les solutions.

• Opérateur de Krawczyk : L'algorithme repose sur l'opérateur de Krawczyk (Théorème 2.1). Pour un système $F$, un point $x$, un rayon $r$ et une matrice $A$ (généralement l'inverse approché de la Jacobienne), l'opérateur $K(F, x, r, A)$ est calculé. Si l'image de cet opérateur est contenue dans une boîte strictement plus petite que la boîte initiale, cela garantit l'existence et l'unicité d'une solution dans cette boîte.
• Algorithme de suivi (Algorithme 3) : Le suivi se fait par étapes discrètes. À chaque étape, un prédicteur (basé sur des modèles de Taylor ou des prédicteurs de Hermite) propose un nouveau point, et un correcteur affine la précision. L'algorithme ajuste dynamiquement la taille du pas de temps et le rayon de certification pour s'assurer que la solution reste unique dans l'encadrement intervalle à chaque étape, empêchant ainsi tout saut de chemin.

B. Graphe d'homotopie (Homotopy Graphs)

Pour reconstruire le groupe de monodromie, les auteurs utilisent un cadre basé sur les graphes (inspiré de [9]) :

1. Construction du graphe : On génère un ensemble de points génériques (sommets) dans l'espace des paramètres. Des arêtes (chemins linéaires ou analytiques) relient ces sommets.
2. Correspondances d'arêtes : En suivant les solutions le long de chaque arête de manière certifiée, on établit une bijection entre les solutions au sommet de départ et celles au sommet d'arrivée.
3. Extraction des permutations :
   • On choisit un sommet de base $z_0$.
   • On construit un arbre couvrant (spanning tree) du graphe.
   • Pour chaque arête non incluse dans l'arbre, elle forme un cycle unique avec l'arbre. Le suivi le long de ce cycle induit une permutation des solutions au-dessus de $z_0$.
   • L'ensemble de ces permutations génère un sous-groupe du groupe de monodromie complet.

C. Stratégie de saturation

L'algorithme itère sur le graphe jusqu'à ce qu'il soit saturé : chaque solution découverte à un sommet a été suivie vers tous les voisins, et vice-versa. Cela maximise les chances de découvrir l'ensemble complet des solutions ($d$ solutions) et de générer le groupe complet.

3. Contributions Clés

1. Certification Rigoureuse : C'est la première approche qui garantit mathématiquement l'absence de saut de chemin lors du calcul de la monodromie, en utilisant l'arithmétique d'intervalles pour encadrer le chemin entier, et non pas seulement les points discrets.
2. Cadre Expérimental Certifié : Contrairement aux méthodes qui tentent de déterminer le groupe complet de manière purement algorithmique (souvent coûteux), cette méthode adopte une approche expérimentale : elle certifie rigoureusement l'action d'un sous-groupe. Même si le groupe complet n'est pas trouvé, les invariants calculés (comme la largeur de Galois) sont rigoureusement prouvés.
3. Générateurs de Groupes via Graphes : L'adaptation de la théorie des graphes (arbres couvrants et cycles fondamentaux) pour extraire systématiquement les générateurs du groupe de permutation à partir des correspondances certifiées.
4. Implémentation en Julia : Développement d'une implémentation performante utilisant la bibliothèque Nemo.jl (basée sur Arb) pour l'arithmétique d'intervalles à précision arbitraire.

4. Résultats Expérimentaux

Les auteurs ont testé leur algorithme sur une variété de problèmes issus de la géométrie algébrique pure et appliquée (vision par ordinateur) :

• Familles univariées : Tests sur des polynômes génériques et symétriques (degré 3 à 8). Les résultats montrent que la probabilité de retrouver le groupe exact augmente avec le nombre de sommets du graphe. Une observation importante est que la largeur de Galois (une mesure de complexité structurelle) est souvent correctement identifiée même lorsque le graphe n'est pas encore saturé ou que toutes les solutions n'ont pas été trouvées.
• Fonction de Belyi (Groupe de Mathieu $M_{23}$) : Certification du groupe de monodromie d'un polynôme de degré 23 associé au groupe sporadique $M_{23}$. L'algorithme a confirmé rigoureusement le résultat sans nécessiter d'estimations de précision a priori, contrairement aux méthodes précédentes.
• 27 lignes sur une surface cubique : Calcul du groupe de monodromie pour les 27 lignes d'une surface cubique symétrique. Le groupe trouvé est $S_2 \times S_2$, agissant de manière intransitive, confirmant la réductibilité de la variété solution.
• Problèmes de vision par ordinateur :
  • Point le plus proche (Nearest point) : Certification du groupe $S_4 \wr S_2$ pour le degré de distance euclidienne 8.
  • P3P (Perspective-3-Point) : Certification du groupe $(S_2 \wr S_4) \cap A_8$.
  • Pose relative 5-points : Renforcement de l'hypothèse que le groupe de monodromie est $(S_2 \wr S_{10}) \cap A_{20}$.

5. Signification et Impact

Cet article représente une avancée significative dans le domaine de la géométrie algébrique numérique :

• Rigueur vs Efficacité : Il résout le compromis traditionnel entre la vitesse des méthodes numériques et la rigueur des preuves mathématiques. Il permet désormais d'obtenir des résultats sur les groupes de Galois qui sont non seulement des conjectures numériques, mais des théorèmes vérifiés par ordinateur.
• Nouvelles Métriques : L'introduction et l'utilisation pratique de la largeur de Galois comme indicateur de complexité, qui peut être certifiée même avec des informations partielles sur le groupe, offre un nouvel outil pour évaluer la difficulté intrinsèque des problèmes d'optimisation et de vision par ordinateur.
• Applicabilité : La méthode est applicable à des problèmes complexes et réels (comme la calibration de caméras), offrant une confiance accrue dans les solutions numériques utilisées dans des contextes critiques.

En résumé, Duff et Lee ont réussi à transformer le calcul de la monodromie d'un processus heuristique en une procédure algorithmique certifiée, ouvrant la voie à une exploration rigoureuse de la structure des systèmes polynomiaux paramétrés.