Explizite Methoden in der Galoistheorie
Final Report Abstract
Die Berechnung der Galoisgruppe eines gegebenen Polynoms f ist seit vielen Jahren ein klassisches Problem der algorithmischen Zahlentheorie. Ein erster prinzipieller Algorithmus zur Bestimmung der Galoisgruppe besteht in der Berechnung des Zerfallungskörpers via sukzessivem Faktorisieren von f über geeigneten Erweiterungskörpern. Hiernach können wir die Galoisgruppe als Automorphismengruppe des Zerfallungskörpers bestimmen. Dieser Zugang ist nur dann effizient, wenn der Grad des Zerfallungskörpers nicht allzu groß gegenüber dem Grad von f ist. Erste, nicht triviale Algorithmen wurden in den 70er und 80er Jahren für Polynome mit rationalen Koeffizienten von Stauduhar, McKay und Soicher entwickelt. Insbesondere die Stauduharmethode wurde von vielen Mathematikern immer weiter verfeinert. Eine aktuelle Implementierung von Claus Fieker und Jürgen Klüners im Computeralgebrasystem Magma ist in der Lage, Galoisgruppen von Polynomen beliebigen Grades uber Q, Q(t), Zahlkörpern oder globalen Funktionenkörpern zu bestimmen. In diesem Projekt wurden erstmals nicht triviale Algorithmen zur Bestimmung der Galoisgruppen über p–adischen Körpern entwickelt und in Magma implementiert. Das Hauptproblem im lokalen Fall ist, dass wir außer im Zerfallungskörper keinen Zugriff auf Approximationen der Nullstellen haben. Dies ist eine wesentliche Voraussetzung zur Anwendung der Stauduhar–Methode und zur Darstellung der Galoisgruppe als Permutationsgruppe auf den Nullstellen. Unsere Algorithmen werden die Galoisgruppe als Gruppe mit Erzeugern und Relationen darstellen. Im Falle einer höchstens zahm verzweigten Erweiterung konnen wir die Galoisgruppe in erwarteter polynomieller Laufzeit im Grad von f und log(q) bestimmen, wobei q die Anzahl der Elemente des Restklassenkörpers ist. Im Weiteren konzentrieren sich die Untersuchungen auf die Bestimmung der Galoisgruppen von irreduziblen Eisensteinpolynomen f. Für eine Nullstelle α von f bezeichnen wir das Newtonpolygon von f (αx+α)/αn x als das Verzweigungspolygon von f. Falls dieses Verzweigungspolygon nur aus einem Segment besteht, so können wir die Galoisgruppe auch in polynomieller Laufzeit sehr effizient angeben. Im Fall von mehr als einem Segment bestimmen wir ebenfalls in polynomieller Laufzeit einen höchstens zahm verzweigten Teilkörper T des Zerfallungskorpers N von f , der die Eigenschaft hat, dass die Galoisgruppe von N/T eine p–Gruppe ist. Für 2 Segmente benutzen wir lokale Klassenkörpertheorie und die Bestimmung der kanonischen Klasse, um die Galoisgruppe von f zu bestimmen. Im allgemeinen Fall können wir einen verbesserten Zerfallungskörperalgorithmus anbieten, welcher den einfach zu berechnenden Körper T, sowie weitere strukturelle Informationen benutzt. Im Rahmen dieses Projekt wurde zusammen mit Gunter Malle auch eine Datenbank für Zahlkörper weiterentwickelt. Auf diese kann online unter http://galoisdb.math.uni-paderborn.de/ zugegriffen werden.
Publications
- A Database for Number Fields
- Galoisgruppen von Eisensteinpolynomen über p-adischen Körpern, Doktorarbeit, Universität Paderborn, 2010
C. Greve
- Generating Subfields, in E. Schost, I.Z. Emiris (Eds.), ISSAC ’11, ACM, 2011, 345-352
M. van Hoeij, J. Klüners, A. Novocin
