Counting solutions of algebraic systems via triangular decomposition

Bächler, Thomas; Plesken, Wilhelm

doi:urn:nbn:de:hbz:82-opus-51041

Counting solutions of algebraic systems via triangular decomposition = Zählen von Lösungen algebraischer Systeme mittels Dreieckszerlegung

Bächler, Thomas (Author)

2014

Verantwortlichkeitsangabevorgelegt von Thomas Martin Bächler

ImpressumAachen 2014

Umfang136 S.

Aachen, Techn. Hochsch., Diss., 2014

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Plesken, Wilhelm (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2014-07-04

Online
URN: urn:nbn:de:hbz:82-opus-51041
URL: https://publications.rwth-aachen.de/record/444946/files/5104.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Nichtlineares Gleichungssystem (Genormte SW) ; Elimination (Genormte SW) ; Resultante (Genormte SW) ; Diskriminante (Genormte SW) ; Zählen (Genormte SW) ; Mathematik (frei) ; elimination (frei) ; discriminant (frei) ; resultant (frei) ; counting (frei) ; polynomial system (frei)

Thematische Einordnung (Klassifikation)
DDC: 510
msc: 13P15

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.

The goal of this thesis is to analyze the solution sets of systems of polynomial equations and inequations over algebraically closed fields algorithmically. In order to give a measure for the size of such a set, we define a polynomial called the counting polynomial, which we use as a generalization of the cardinality of a finite set. The computation of the counting polynomial requires a decomposition of the solution set into pairwise disjoint subsets defined by a special kind of triangular polynomial systems called simple systems. These simple systems have interesting properties themselves, which we study as well. Most importantly, due to their triangular structure, they can be solved iteratively, giving a clear description of their solution set. We will use simple systems and counting polynomials to study algebraic varieties and constructible sets. Finally, we will use the counting polynomial to count the number of solutions of certain polynomial systems over finite fields. Triangular systems are commonly used to solve systems of equations iteratively. Since arbitrary non-linear systems can in general not be transformed into triangular systems, it is necessary to decompose the solution set into smaller subsets represented by triangular systems. Such a decomposition is called a triangular decomposition. In the 1930s, Joseph Miller Thomas described a method for performing a decomposition into simple systems. This method distinguishes different cases precisely by introducing inequations. This has the side-effect that the original set is decomposed into pairwise disjoint subsets. His method is very elementary and requires no advanced knowledge of the theory of rings and ideals. The Thomas decomposition is the only known method to compute the counting polynomial of the solution set of an arbitrary polynomial system. If a set is finite, its counting polynomial equals its cardinality. For an infinite set, the counting polynomial encodes some information about the fibration structure of the set as imposed by the choice and the order of the indeterminates. It helps deciding equality of sets and contains information about the structure of the solution set, such as its dimension. In some cases, it can be used to count the number of solutions of a polynomial system over a finite field. In this thesis, we define the counting polynomial axiomatically and discuss its most important properties. We give a generalization of the counting polynomial called the counting tree. We then introduce a new algorithm for computing a Thomas decomposition over arbitrary fields. In particular, our algorithm is the first one that can compute this decomposition over fields of positive characteristic. We provide an implementation of this algorithm in the computer algebra system Maple, for the case where the ground field is either finite or a finitely generated extension of the field of rational numbers. We analyze the behaviour of counting polynomials and counting trees under transformations of the underlying polynomial systems. We give a connection between simple system and embeddings of affine or projective varieties into affine or projective space, respectively, by assigning an ideal to each simple system. This connection is discussed in more detail for the case of normal toric varieties. Finally, we apply the Thomas decomposition and counting polynomials to the study of rational maps and to counting the number of solutions of certain systems of equations and inequations over finite fields.

Fulltext:
PDF