Counting solutions of algebraic systems via triangular decomposition

• Zählen von Lösungen algebraischer Systeme mittels Dreieckszerlegung

Bächler, Thomas; Plesken, Wilhelm (Thesis advisor)

Aachen (2014)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2014

Kurzfassung

Das Ziel dieser Dissertation ist die algorithmische Analyse von Lösungsmengen polynomieller Gleichungs- und Ungleichungssysteme. Um ein Maß für die Größe einer solchen Menge anzugeben, definieren wir das Zählpolynom, welches wir als Verallgemeinerung für die Kardinalität einer endlichen Menge verwenden. Die Berechnung des Zählpolynoms erfordert die Zerlegung der Lösungsmenge in paarweise disjunkte Teilmengen, die durch eine spezielle Art polynomieller Dreieckssysteme, genannt einfach Systeme, gegeben sind. Diese einfachen Systeme haben auch für sich gesehen interessante Eigenschaften, welche wir ebenfalls studieren. Insbesondere kann man sie, wegen ihrer Dreiecksstruktur, iterativ lösen und so eine klare Beschreibung ihrer Lösungsmenge erhalten. Wir werden einfach Systeme und Zählpolynome verwenden um algebraische Varietäten und konstruierbare Mengen zu studieren. Schließlich werden wir das Zählpolynom benutzen um die Anzahl der Lösungen bestimmter polynomieller Systeme über endlichen Körpern zu bestimmen. Dreieckssysteme werden häufig verwendet um Gleichungssysteme iterativ zu lösen. Da beliebige nicht-lineare Systeme im Allgemeinen nicht in Dreieckssysteme überführt werden können, ist es nötig die Lösungsmengen in kleinere Teilmengen zu zerlegen, welche durch Dreieckssysteme gegeben sind. Eine solche Zerlegung heißt Dreieckszerlegung. In den 1930ern hat Joseph Miller Thomas eine Methode zur Zerlegung in einfache Systeme eingeführt. Diese Methode unterscheidet unterschiedliche Fälle exakt durch die Einführung von Ungleichungen. Dies hat den Nebeneffekt, dass die ursprüngliche Menge in paarweise disjunkte Teilmengen zerlegt wird. Seine Methode ist sehr elementar und benötigt keine fortgeschrittenen Kenntnisse der Theorie von Ringen und Idealen. Die Thomas-Zerlegung ist die einzige bekannte Methode zur Berechnung des Zählpolynoms der Lösungsmenge eines beliebigen Polynomsystems. Falls eine Menge endlich ist, so entspricht ihr Zählpolynom ihrer Kardinalität. Für eine unendliche Menge kodiert das Zählpolynom Informationen über die Faserungsstruktur der Menge, die durch die Wahl und die Reihenfolge der unbestimmten festgelegt wird. Es hilft dabei, die Gleichheit von Mengen zu entscheiden und enthält Informationen über die Lösungsmenge, wie zum Beispiel ihre Dimension. In einigen Fällen kann es benutzt werden, um die Anzahl der Lösungen eines polynomiellen Systems über einem endlichen Körper zu zählen. In dieser Dissertation definieren wir das Zählpolynom axiomatisch und diskutieren seine wichtigsten Eigenschaften. Wir geben eine Verallgemeinerung des Zählpolynoms an, genannt der Zählbaum. Wir präsentieren einen neuen Algorithmus zur Berechnung der Thomas-Zerlegung über beliebigen Körpern. Insbesondere ist unser Algorithmus der erste, der diese Zerlegung über Körpern positiver Charakteristik berechnen kann. Wir stellen eine Implementierung dieses Algorithmus im Computeralgebrasystem Maple bereit, welche die Zerlegung über endlichen Körpern und über endlich erzeugten Erweiterungen der rationalen Zahlen durchführen kann. Wir analysieren das Verhalten von Zählpolynomen und Zählbäumen unter Transformationen des zugrundeliegenden Polynomsystems. Wir stellen eine Verbindung zwischen einfachen Systemen und Einbettungen affiner oder projektiver Varietäten in den affinen respektive den projektiven Raum her, indem wir jedem einfachen System ein Ideal zuordnen. Diese Verbindung wird für den Fall normaler torischer Varietäten ausführlich diskutiert. Schließlich wenden wir die Thomas-Zerlegung und Zählpolynome auf das Studium rationaler Abbildungen und auf die Bestimmung der Anzahl von Lösungen bestimmter Gleichungs- und Ungleichungssysteme über endlichen Körpern an.