Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-26T07:29:21.750Z Has data issue: false hasContentIssue false
  • English
  • Français

Computation of Galois groups of rational polynomials

Part of: Algebraic number theory: global fields Computational number theory Ring extensions and related topics

Published online by Cambridge University Press:  01 May 2014

Claus Fieker  and
Jürgen Klüners
Claus Fieker
Affiliation:
Faculty of Mathematics,  University of Kaiserlautern,  P.O. Box 3049,  D-67653 Kaiserslautern,  Germany email [email protected]
Jürgen Klüners
Affiliation:
Mathematisches Institut der Universität Paderborn,  Warburger Str. 100,  D-33098 Paderborn,  Germany email [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Computational Galois theory, in particular the problem of computing the Galois group of a given polynomial, is a very old problem. Currently, the best algorithmic solution is Stauduhar’s method. Computationally, one of the key challenges in the application of Stauduhar’s method is to find, for a given pair of groups $H<G$, a $G$-relative $H$-invariant, that is a multivariate polynomial $F$ that is $H$-invariant, but not $G$-invariant. While generic, theoretical methods are known to find such $F$, in general they yield impractical answers. We give a general method for computing invariants of large degree which improves on previous known methods, as well as various special invariants that are derived from the structure of the groups. We then apply our new invariants to the task of computing the Galois groups of polynomials over the rational numbers, resulting in the first practical degree independent algorithm.

MSC classification

Secondary: 11R32: Galois theory 13B05: Galois theory 11Y40: Algebraic number theory computations
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Issue 1 , 2014 , pp. 141 - 158
Copyright
© The Author(s) 2014 

References

Abdeljaouad, I., ‘Calculs d’invariants primitifs de groupes finis’, Theor. Inform. Appl. 33 (1999) 59–77.Google Scholar
Bridson, M. and Miller, C., ‘Structure and finiteness properties of subdirect products of groups’, Proc. Lond. Math. Soc. (3) 90 (2009) 631–651.Google Scholar
Casperson, D. and McKay, J., ‘Symmetric functions, m-sets, and Galois groups’, Math. Comput. 63 (1994) 749–757.Google Scholar
Cohen, H., A course in computational algebraic number theory (Springer, Berlin, 1993).CrossRefGoogle Scholar
Conway, J. H., Hulpke, A. and McKay, J., ‘On transitive permutation groups’, LMS J. Comput. Math. 1 (1998) 1–8.Google Scholar
Derksen, H. and Kemper, G., ‘Computational invariant theory’, Encyclopaedia of mathematical sciences. Invariant theory and algebraic transformation groups (Springer, Berlin, 2002).Google Scholar
Dixon, J. and Mortimer, B., Permutation groups (Springer, Berlin-Heidelberg-New York, 1996).Google Scholar
Dokchitser, T. and Dokchitser, V., ‘Identifying Frobenius elements in Galois groups’, Algebra Number Theory 7/6 (2013) 1325–1352.Google Scholar
Eichenlaub, Y., ‘Problèmes effectifs de théorie de Galois en degrés 8 à 11’, Thèse, Université Bordeaux 1, 1996.Google Scholar
Elsenhans, A.-S., ‘Invariants for the computation of intransitive and transitive Galois groups’, J. Symbolic. Comput. 47 (2012) 315–326.CrossRefGoogle Scholar
Geißler, K., ‘Berechnung von Galoisgruppen über Zahl- und Funktionenkörpern’, PhD Thesis, Technische Universität Berlin, 2003.Google Scholar
Geißler, K. and Klüners, J., ‘Galois group computation for rational polynomials’, J. Symbolic. Comput. 30 (2000) 653–674.Google Scholar
Girstmair, K., ‘On the computation of resolvents and Galois groups’, Manuscripta Math. 43 (1983) 289–307.Google Scholar
Girstmair, K., ‘On invariant polynomials and their application in field theory’, Math. Comput. 48 (1987) 781–797.CrossRefGoogle Scholar
van Hoeij, M., Klüners, J. and Novocin, A., ‘Generating subfields’, J. Symbolic. Comput. 52 (2013) 17–34.Google Scholar
Kemper, G. and Steel, A., ‘Some algorithms in invariant theory of finite groups’, Computational Methods for Representations of Groups and Algebras, Euroconference in Essen, April 1–5 1997 , Progress in Mathematics 173 (eds Dräxler, P., Michler, G. O. and Ringel, C. M.; Birkhäuser, 1997).Google Scholar
Klüners, J., ‘Über die Berechnung von Automorphismen und Teilkörpern algebraischer Zahlkörper’, PhD TU-Berlin (1997).Google Scholar
Klüners, J. and Malle, G., ‘Explicit Galois realization of transitive groups of degree up to 15’, J. Symbolic. Comput. 30 (2000) 675–716.Google Scholar
Klüners, J. and Malle, G., ‘A database for field extensions of the rationals’, LMS J. Comput. Math. 4 (2001) 182–196.Google Scholar
Loos, R., ‘Computing in algebraic extensions’, Computer algebra. Symbolic and algebraic computation , Computing Supplementum 4 (eds Buchberger, B., Collins, G. E. and Loos, R.; Springer, Wien, 1982) 173–187.Google Scholar
Schmalz, B., ‘Verwendung von Untergruppenleitern zur Bestimmung von Doppelnebenklassen’, Bayreuther Math. Schriften 31 (1990) 109–143.Google Scholar
Soicher, L., ‘The computation of Galois groups’, M. Comp. Sci. Thesis, Concordia University, Montreal, 1981. http://www.maths.qmul.ac.uk/∼leonard/mcompsc_soicher.pdf.Google Scholar
Stauduhar, R., ‘The determination of Galois groups’, Math. Comput. 27 (1973) 981–996.Google Scholar
Yokoyama, K. and Renault, G., ‘A modular method for computing the splitting field of a polynomial’, ANTS 2006 , Lecture Notes in Computer Science 4076 (Springer, 2006) 124–140.Google Scholar