Ultrametric Fewnomial Theory
MetadataShow full item record
An ultrametric field is a field that is locally compact as a metric space with respect to a non-archimedean absolute value. The main topic of this dissertation is to study roots of polynomials over such fields. If we have a univariate polynomial with coefficients in an ultrametric field and non-vanishing discriminant, then there is a bijection between the set of roots of the polynomial and classes of roots of the same polynomial in a finite ring. As a consequence, there is a ball in the polynomial space where all polynomials in it have the same number of roots. If a univariate polynomial satisfies certain generic conditions, then we can efficiently compute the exact number of roots in the field. We do that by using Hensel's lemma and some properties of Newton's polygon. In the multivariate case, if we have a square system of polynomials, we consider the tropical set which is the intersection of the tropical varieties of its polynomials. The tropical set contains the set of valuations of the roots, and for every point in the tropical set, there is a corresponding system of lower polynomials. If the system satisfies some generic conditions, then for each point w in the tropical set the number of roots of valuation w equals the number roots of valuation w of the lower system. The last result enables us to compute the exact number of roots of a polynomial system where the tropical set is finite and the lower system consists of binomials. This algorithmic method can be performed in polynomial-time if we fix the number of variables. We conclude the dissertation with a discussion of the feasibility problem. We consider the problem of the p-adic feasibility of polynomials with integral coefficients with the prime number p as a part of the input. We prove this problem can be solved in nondeterministic polynomial-time. Furthermore, we show that any problem, which can be solved in nondeterministic polynomial-time, can be reduced to this feasibility problem in randomized polynomial-time.
Ibrahim Abdelhalim, Ashraf (2009). Ultrametric Fewnomial Theory. Doctoral dissertation, Texas A&M University. Available electronically from