• 12D05 Polynomials: factorization
• 12E10 Special polynomials
• 12F10 Separable extensions, Galois theory
• 12Y05 Computational aspects of field theory and polynomials
• 13P05 Polynomials, factorization, See also {12Y05}
• 68Q40 Symbolic computation, algebraic computation, See Also {11Yxx, 12Y05, 13Pxx, 14Qxx, 16-08, 17-08}

  Code(s) de Classification CR: I.1.2-Algorithms---Algebraic-algorithms;F.2.1-Numerical-Algorithms-and-Problems---Computations-on-polynomials

Résumé:

La théorie de Galois effective cherche à déterminer, à conjugaison près, le groupe de Galois d'un polynôme f. Cette recherche peut se faire à partir de la factorisation de polynômes déduits du polynôme f, les résolvantes de Lagrange, qui ont même corps des coefficients que le polynôme f. Les degrés des facteurs de résolvantes bien choisies, ainsi que les propriétés des groupes de Galois de ces facteurs, permettent de toujours déterminer le groupe de Galois du polynôme f parmi les groupes possibles. Ils sont connus par une classification des sous-groupes du groupe symétrique qui, à ce jour, a été effectuée jusqu'à l'ordre 31. Le calcul efficace de résolvantes de Lagrange intéressantes et la factorisation de ces résolvantes constituent les points clefs de la recherche du groupe de Galois par les résolvantes. Les méthodes de calcul de résolvantes de Lagrange par l'élimination (le résultant) engendrent des facteurs et des puissances parasites. La théorie des groupes fournit des informations sur les degrés possibles, qui ne sont donc pas quelconques, des facteurs des résolvantes. Notre travail améliore deux méthodes de calcul symbolique des résolvantes, basées sur le résultant, qui suppriment facteurs et puissances parasites. Nous montrons aussi comment adapter les algorithmes de la factorisation des polynômes pour utiliser les informations connues a priori sur les résolvantes. La factorisation étant pour nous un moyen et non un but, nous introduisons le concept de factorisation interactive pour rendre immédiatement accessibles les nouvelles informations sur la factorisation des résolvantes trouvées au cours du processus de factorisation. Ce concept n'est pas spécifique à la factorisation de résolvantes en théorie de Galois effective. Il peut être utilisé pour toute factorisation de polynômes lorsque l'information cherchée ne demande pas forcément une factorisation complète.

Abstract:

Computational Galois theory aims at determination, up to conjugation, of the Galois group of a polynomial f. This computation may be performed from the factorization of polynomials, depending on the polynomial f, which have same coefficient field as the polynomial f : Lagrange resolvents. Degrees of factors of well chosen resolvents and properties of their Galois groups ensure to always determine Galois group of polynomial f among all possible groups. They are known from the classification of sub-groups of the symmetric group which has been performed, currently, up to order 31. Efficient computation of interesting Lagrange resolvents and factorization of these resolvents are key points in determination of Galois group by resolvents. The methods for computing Lagrange resolvents which are based on elimination (resultant) generate parasitic factors and powers. Group theory gives some information on possible degrees of factors of resolvents as they are not random. Our work improves two methods for symbolic computation of resolvents which are based on resultant and remove parasitic factors and degrees. We also show how to adapt polynomial factorization algorithms in order to take into account information known in advance on resolvents. Factorization being for us a tool more than a goal, we introduce the concept of interactive factorization in order to make quickly available any new information on factorization found along the factorization process. This concept is not specific to resolvent factorization in computational Galois theory. It may be used for any problem of factorization for which is required less than a complete factorization.