Monte-Carlo Irreducibility and Imprimitivity Detection of Polynomials over $\mathbb{Q}$

Résumé technique : Irréductibilité et détection d'imprimitivité par Monte-Carlo de polynômes sur $\mathbb{Q}$

Énoncé du problème
L'article traite de trois problèmes centraux en algèbre computationnelle et en théorie des nombres : la factorisation de polynômes sur les nombres rationnels $\mathbb{Q}$, le test d'irréductibilité des polynômes et la détermination de la structure des groupes de Galois. Bien qu'il existe des algorithmes déterministes avec des bornes théoriques en temps polynomial, ceux-ci deviennent souvent impraticables à des degrés modérés. À l'inverse, les méthodes modulaires standards passent bien à l'échelle mais rejettent généralement les informations issues des essais « infructueux » (où un polynôme se factorise modulo $p$) plutôt que de les agréger. De plus, la détection de l'imprimitivité arithmétique (l'existence de systèmes de blocs non triviaux dans l'action de Galois) pour des degrés élevés manquait d'algorithmes pratiques.

Méthodologie
L'approche proposée repose sur des méthodes de Monte-Carlo qui agrègent les informations issues des factorisations modulaires à travers plusieurs nombres premiers, plutôt que de s'arrêter au premier degré irréductible trouvé.

1. Le critère de somme de sous-ensembles PPR : S'appuyant sur les travaux de Pemantle, Peres et Rivin (PPR), la méthode utilise les degrés des facteurs $(d_i)$ d'un polynôme $f$ modulo un nombre premier $p$. Elle construit un ensemble de sommes de sous-ensembles $S_p$ contenant toutes les sommes possibles $\sum_{i \in I} d_i$. Le principe théorique central est que si $f$ possède un facteur rationnel de degré $d$, alors $d$ doit appartenter à $S_p$ pour tous les nombres premiers « bons ».
2. Test d'irréductibilité probabiliste : L'algorithme intersecte les ensembles de sommes de sous-ensembles $S_p$ à travers une séquence de nombres premiers échantillonnés. Si l'intersection ne contient aucun degré propre (degrés strictement compris entre 1 et $n$), le polynôme est déclaré irréductible.
3. Stratégie hybride : L'algorithme exécute le test basé sur PPR pour un nombre attendu de $O(\log n)$ nombres premiers. Si le test est non concluant, il revient à des tests d'irréductibilité modulaires standards.
4. Détection de l'imprimitivité : La méthode traite l'échec du test de somme de sous-ensembles (où l'intersection reste non vide malgré la certification de l'irréductibilité du polynôme) comme un indicateur structurel. Cela signale une potentielle imprimitivité arithmétique. L'algorithme effectue ensuite une recherche de sous-corps non triviaux au sein du corps de racine $K = \mathbb{Q}(\alpha)$, fournissant des certificats constructifs.
5. Démarrage à chaud (Warm-Start) pour la factorisation : Lorsque l'intersection des sommes de sous-ensembles ne s'effondre pas, les degrés survivants fournissent un ensemble candidat restreint $D$ pour les degrés des facteurs rationnels. Cet ensemble est utilisé pour accélérer les procédures ultérieures de levée de Hensel et de recombinaison.

Contributions clés et résultats

• Test d'irréductibilité probabiliste efficace : Pour des entrées génériques, le temps d'exécution attendu (mesuré en nombre de nombres premiers examinés) est logarithmique par rapport au degré, soit $O(\log n)$. Contrairement aux tests standards qui rejettent les factorisations modulaires infructueuses, cette méthode agrège les informations de tous les essais.
• Détection de l'imprimitivité arithmétique : L'article présente le premier algorithme de Monte-Carlo pratique pour détecter l'imprimitivité arithmétique dans les polynômes de haut degré sur $\mathbb{Q}$. Il identifie l'imprimitivité non pas seulement par des statistiques heuristiques, mais en produisant des certificats algébriques explicites : des sous-corps intermédiaires non triviaux et des équations relativeses définissant le corps de racine sur ces sous-corps.
• Accélération de la factorisation : Les données de somme de sous-ensembles générées lors du test d'irréductibilité servent de « démarrage à chaud » pour la factorisation. En restreignant drastiquement les degrés possibles des facteurs rationnels, la méthode réduit considérablement la complexité combinatoire de la levée et de la recombinaison, évitant ainsi le besoin de nouveaux calculs modulaires.
• Robustesse adverse : Les auteurs démontrent que, bien que les données modulaires locales soient informatives lorsqu'elles sont agrégées, elles sont insuffisantes pour certifier la structure globale à elles seules. Ils construisent des polynômes « jumeaux maléfiques » (evil twins) qui préservent les réductions modulo de petits nombres premiers mais restaurent un comportement de Galois global générique, illustrant la nécessité de combiner les heuristiques probabilistes avec des constructions de théorie des corps explicites.

Signification et revendications
L'article affirme que ces méthodes sont ordres de grandeur plus rapides en pratique que les algorithmes déterministes connus et restent efficaces pour des degrés dépassant largement la portée des techniques déterministes actuelles.

• Praticité : Les algorithmes sont décrits comme pratiques, implémentés et appliqués avec succès à des polynômes de haut degré.
• Optimalité de Pareto : L'approche hybride est présentée comme étant Pareto-optimale ; elle n'est jamais asymptotiquement moins performante que les méthodes de Monte-Carlo existantes et est souvent nettement plus rapide.
• Résultat constructif : Dans le cas de l'imprimitivité, la méthode dépasse la simple détection pour fournir des certificats constructifs (sous-corps et équations relatives), ce qui la distingue des approches purement heuristiques.
• Scalabilité : Le recours au calcul modulaire, aux petits nombres premiers et à l'agrégation d'informations rend ces méthodes particulièrement adaptées au calcul à grande échelle et au calcul parallèle.

L'article conclut que, bien que les données modulaires locales soient hautement informatives lorsqu'elles sont agrégées, la certification efficace de la structure algébrique globale nécessite la combinaison d'heuristiques probabilistes et de constructions explicites de la théorie des corps.