Oberseminar Komplexität und Algorithmen

Nach der sogenannten Regel von Descartes lässt sich die Anzahl der reellen nichttrivialen Nullstellen (also alle x<>0 mit f(x)=0) eines Polynoms f in einer Unbestimmten nach oben abschätzen durch 2k, wobei k+1 die Anzahl der Terme in f ist.
In der Arbeit "On the factorization of lacunary polynomials" beweist H.W. Lenstra, Jr. ein p-adisches Analogon dieser Regel: Sei p prim, L eine endliche Erweiterung der p-adischen Zahlen und k eine positive ganze Zahl. Dann gibt es eine Konstante B=B(k,L), so dass gilt: Ein Polynom f aus L[T], welches höchstens k+1 (nichtverschwindende) Terme hat, hat höchstens B nichttriviale Nullstellen in L (gezählt mit Vielfachheit).
Aus diesem p-adischen Resultat folgert er noch eine Aussage über beliebige Zahlkörper. Seien m, k und d positive ganze Zahlen. Dann gibt es eine Konstante A=A(m,k,d), so dass für jeden Zahlkörper K vom Grad höchstens m über den rationalen Zahlen gilt: Sei f aus K[T] ein Polynom mit höchstens k+1 (nichtverschwindenden) Termen, das Null nicht als Nullstelle hat, und sei g ein Faktor von f, dessen irreduzible Faktoren höchstens den Grad d haben. Dann ist der Grad von g nach oben beschränkt durch A. (Als Korollar folgt eine Aussage über die Anzahl der Nullstellen von f.)

In dem Vortrag sollen zunächst die p-adischen Zahlen definiert, endliche Erweiterungen davon untersucht und schließlich der vollständige algebraische Abschluss konstruiert werden. Außerdem wird noch das (p-adische) Newton-Polygon (eines Polynoms) definiert und dessen Eigenschaften untersucht. Anschließend soll die Argumentation von Lenstra nachvollzogen und seine (Haupt-)Ergebnisse bewiesen werden.

Der Algorithmus von Schoof aus dem Jahr 1984 lieferte den Durchbruch in der Algorithmik der Primzahltests mit Hilfe elliptischer Kurven über endlichen Körpern. Dieser Polynomialzeitalgorithmus ermöglichte die Entwicklung des sogenannten "Elliptic Curve Primality Proving", wofür der Goldwasser-Kilian-Primzahltest aus dem Jahre 1986 eines der ersten Beispiele darstellt.

Schoofs Algorithmus berechnet die Anzahl Punkte einer elliptischen Kurve E über einem endlichen Körper K in polynomieller Zeit. Die Idee beruht auf der Berechnung der Spur des Frobenius-Endomorphismus' in der l-Torsion der Kurve E für "kleine" Primzahlen l. Das Ergebnis kann mit Hilfe des Chinesischen Restsatzes und der Hasseschranke eindeutig bestimmt werden.

In dem Vortrag wird ein Zusammenhang zwischen magischen Quadraten und bestimmten Invariantenringen hergestellt, so dass man mit Methoden der Invariantentheorie sowohl quantitative als auch qualitative Aussagen über magischen Quadrate herleiten kann.

Zuerst wird eine Bijektion zwischen kombinatorischen Strukturen und Invariantenringen einer gewissen Torusoperation angegeben. Damit kann man dann zuerst die Erzeuger und dann auch die Anzahl der magischen Quadrate bestimmen. Anschliessend wird auf eine Methode eingegangen, mit der es möglich ist, ohne Umweg über die Erzeuger die Anzahl magischer Quadrate zu bestimmen.