Fachgruppentagung Kassel 2003

Hauptvorträge

Prof. Wolfram Decker (Saarbrücken): Computeralgebramethoden in der algebraischen Geometrie

Algebraische Geometer studieren Kurven, Flächen oder andere geometrische Objekte, die als Lösungsmengen polynomialer Gleichungen auftreten. Ein wichtiges Hilfsmittel ist ein geometrisch-algebraisches Wörterbuch, das geometrische Eigenschaften in algebraische Eigenschaften übersetzt und umgekehrt. Dieses Wörterbuch erlaubt es insbesondere, moderne Computeralgebramethoden zur intensiven Beispielrechnung heranzuziehen. Durch solche Experimente kann man mathematische Zusammenhänge erkennen oder etwa Gegenbeispiele zu Vermutungen finden. In meinem Vortrag spreche ich unter anderem folgende Fragen an: Was kann heute in der algebraischen Geometrie berechnet werden? Welche Computeralgebrasysteme sind für diese Rechnungen geeignet? Was sind typische Anwendungen?

Prof. Bettina Eick (Braunschweig): Algorithmische Gruppentheorie mit dem Computeralgebrasystem GAP

Gruppen spielen eine wichtige Rolle in der Algebra: sie werden verwendet, um die Symmetrien von Objekten zu studieren, und sie haben Anwendungen, die von der Unlösbarkeit von Gleichungen 5. Grades bis hin zur Kristallographie reichen.
Die algorithmische Gruppentheorie ist ein wichtiges Hilfmittel zur Untersuchung und Klassifizierung von Gruppen. So kann man zum Beispiel mit Hilfe von Algorithmen den Rubik’s Cube sehr leicht im Detail studieren; ein Projekt, welches ohne den Einsatz von Computern nicht so einfach ist. Weitere Anwendungen der algorithmischen Gruppentheorie sind in der Untersuchung von kristallographischen Gruppen oder von topologischen Gruppen zu finden.
In der Entwicklung von Algorithmen zur Behandlung von Gruppen spielt die Darstellung der gegebenen Gruppen eine fundamentale Rolle. Daher kann man die algorithmische Gruppentheorie in eine Reihe von Teilgebieten einteilen: sehr bekannt sind hier zum Beispiel Algorithmen für Permutationsgruppen, Algorithmen für Matrixgruppen oder Algorithmen für endlich präsentierte Gruppen. Weniger bekannt, aber trotzdem sehr interessant sind zum Beispiel Methoden zum Rechnen mit freien Gruppen oder mit polyzyklischen Gruppen. In diesem Vortrag soll ein Überblick über verschiedene, aktuelle Teilgebiete und den Stand der Technik in diesen Gebieten gegeben werden.

Dr. Claus Fieker (Sydney): Konstruktive Klassenkörpertheorie in globalen Körpern

Endliche Erweiterungen von Polynomringen über endlichen Körpern haben viele Gemeinsamkeiten mit endlichen Erweiterungen der rationalen Zahlen, speziell sind dies Körper, in denen die Produktformel gilt. Diese Körper heißen “Globale Körper”. Klassenkörpertheorie klassifiziert abelsche Erweiterungen durch Invarianten des Grundkörpers. Die Grundlagen der Theorie sind um 1930 entwickelt worden. Es wurde gezeigt, dass abelsche Erweiterungen durch verallgemeinerte Klassengruppen (Strahlklassengruppen) beschreibbar sind. Es ist jedoch ein offenes Problem, explizite Erzeuger für Klassenkörper zu bestimmen. Nachdem es in den letzten Jahren durch Fortschritte in der konstruktiven Zahlentheorie möglich geworden ist, mit Hilfe von algorithmischen Methoden für abelsche Erweiterungen von Zahlkörpern Erzeuger zu bestimmen, ist es nun an der Zeit, generische Algorithmen für globale Körper zu entwickeln. In diesem Vortrag werde ich erklären, wie die Klassengruppen zu Strahlklassengruppen verallgemeinert werden und wie dies für die Bestimmung expliziter Erzeuger benutzt werden kann. Ich werde sowohl auf die Gemeinsamkeiten als auch auf die Unterschiede der beiden Typen globaler Körper eingehen und damit auch die Grenzen der generisch “globalen” Methoden aufzeigen. Explizite Klassenkörpertheorie für Funktionenkörper hat wichtige Anwendungen in der Kodierungstheorie: viele der derzeit besten Codes korrespondieren direkt zu abelschen Erweiterungen geeigneter Funktionenkörper. Um diese Codes benutzen zu können, ist das Bestimmen expliziter Erzeuger der erste Schritt.

Prof. Martin Kreuzer (Dortmund): Effiziente Berechnung von Gröbner-Basen

Viele wichtige Verfahren der Computeralgebra basieren auf der Berechnung von Gröbner-Basen. Deshalb ist es von zentraler Bedeutung, Algorithmen zu finden, die Gröbner-Basen effizient berechnen, sowie bekannte Algorithmen wie den Buchberger-Algorithmus zu optimieren.
Im ersten Teil des Vortrags betrachten wir verschiedene Möglichkeiten zur Optimierung des Buchberger-Algorithmus im homogenen Fall. Ein wesentlicher Aspekt ist dabei die Minimierung der abzuarbeitenden kritischen Paare. Wann man jedoch ein kritisches Paar als überflüssig betrachen kann, hängt vom Kontext der Berechnung ab. Sicherlich kann man sich auf eine Menge von kritischen Paaren beschränken, die ein minimales Erzeugendensystem des Syzygienmoduls der Leitterme der Gröbner-Basis darstellt. Der neue Algorithmus von Caboara-K.-Robbiano zeigt, dass eine derartige minimale Menge kritischer Paare effizient während einer Gröbner-Basisberechnung gefunden werden kann.
Im zweiten Teil des Vortrags behandeln wir einige speziellere Fälle von Gröbner-Basisberechnungen, in denen bessere Methoden als der Buchberger-Algorithmus bekannt sind. Unter Anderem betrachten wir die Frage der Berechnung des Kerns einer K-linearen Abbildung K[[x_1,…,x_n] -> K^s, wenn bekannt ist, dass dieser ein Ideal darstellt. Spezialfälle dieses allgemeinen Problems sind z.B. die multivariate Interpolation, Hermite-Interpolation und homogene Implizitisierung. Wir zeigen verschiedene Versionen des Buchberger-Möller-Algorithmus, die die Aufgabe über verschiedenen Grundkörpern K effizient lösen. Im Fall der Berechnung des homogenen Verschwindungsideals eines projektiven nulldimensionalen Schemas treten weitere Schwierigkeiten auf, weil der Zielvektorraum nicht mehr endlichdimensional ist. Führt man die Endlichkeit dadurch herbei, dass man gradweise vorgeht, so benötigt man ein effizientes Stoppkriterium, wie es z.B. im vorliegenden Fall von Abbott-Bigatti-K.-Robbiano gefunden wurde.

Prof. Tsuyoshi Takagi (Darmstadt): Cryptographical Algorithms

Der Vortrag befasst sich mit beweisbarer sicherer Kryptographie. Die Kryptographie ist die fundamentale Infrastruktur für die sichere Kommunikation über das Internet, nämlich SSL/WTSL, IPSEC, WAP, usw. Um das Sicherheitslevel der Kryptographie korrekt einschätzen zu können, benötigen wir Sicherheitsmodelle. Eines dieser Standardmodelle ist die sog. Semantische Sicherheit. Im Vortrag wird NICE-X präsentiert, das beweisbar sicher in Hinsicht auf semantische Sicherheit ist und auf quadratischen Zahlkörpern beruht.

Weitere Vorträge

Thomas Bayer (TU München): Über konstruktive Invariantentheorie und Stratifizierung von Quotienten.

Es wird ein neuer Algorithmus zur Berechnung von homogenen Invarianten von algebraischen Gruppen, die linear auf einem affinen Raum operieren, vorgestellt. Der Algorithmus kommt ohne Reynolds-Operator aus und läuft schneller als der mit Methoden aus der lineraren Algebra operierende Standard-Algorithmus. Besonders nützlich ist der Algorithmus für kompakte Lie-Gruppen, die zahlreiche Anwendungen in der Physik haben. Weiters wird auf eine Methode zur Stratifikation von Aktionen von kompakten Lie-Gruppen eingegangen, die u.a. zur Modellierung von Symmetriebrechung verwendet werden kann.