Trees, Point Counting Beyond Fields, and Root Separation
Yuyu Zhu · OakTrust (Texas A&M University Libraries) · 2020
Counting the solutions to systems of polynomial equations over finite fields is a central problem in number theory, as well as computer algebra. In this work, we discuss its applications to the problems of computing the dimension of an algebraic set over the complex numbers, and point counting over prime power rings. Given a polynomial system with integer coefficients, we show that, under plausible conjectures on the distribution of primes, we can efficiently determine the dimension of its complex zero set. This result softens the assumption of the Generalized Riemann Hypothesis in an earlier algorithm of Koiran. On the other hand, we give a Las Vegas randomized polynomial-time algorithm that computes the number of roots of a univariate polynomial f in prime power ring via a recursive tree structure. A special case of the problem when f is sparse is also explored. More specifically, via Hensel’s Lemma and root counting over prime power ring, we prove a complexity chasm, separating the trinomial and tetranomial cases, for solving univariate sparse polynomial equations over the p-adic field: complex p-adic roots are well-separated for trinomials, but can be exponentially closed for tetranomials. In particular, we give a unified family of tetranomials that one needs exponentially many digits to distinguish the base-p expansions of its p-adic roots in the worst case. We also extend of our root counting algorithm to higher dimensions by generalize its underlying recursive formula and tree structures. In particular, for some infinite families of curves, we can compute its number of solutions over prime power rings in randomized polynomial time.