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)
Dissertation / PhD Thesis

Aachen, Techn. Hochsch., Diss., 2014

Abstract

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.