Arithmetic Multivariate Descartes' Rule
Abstract
Description
Let L be any number field or $\mathfrak{p}$-adic field and consider F:=(f_1,...,f_k) where f_i is in L[x_1,...,x_n]\{0} for all i and there are exactly m distinct exponent vectors appearing in f_1,...,f_k. We prove that F has no more than 1+(cmn(m-1)^2 log m)^n geometrically isolated roots in L^n, where c is an explicit and effectively computable constant depending only on L. This gives a significantly sharper arithmetic analogue of Khovanski's Theorem on Fewnomials and a higher-dimensional generalization of an earlier result of Hendrik W. Lenstra, Jr. for the case of a single univariate polynomial. We also present some further refinements of our new bounds and briefly discuss the complexity of finding isolated rational roots.
27 pages, needs svjour.cls and svinvmat.clo (both included) to compile. Maple code to verify computations included. This version removes a factor of n^n from the main bounds and includes extra discussion on additive complexity and the complexity of finding isolated rational roots. Also, more typos are corrected, and the numerical bounds from the examples are improved considerably
27 pages, needs svjour.cls and svinvmat.clo (both included) to compile. Maple code to verify computations included. This version removes a factor of n^n from the main bounds and includes extra discussion on additive complexity and the complexity of finding isolated rational roots. Also, more typos are corrected, and the numerical bounds from the examples are improved considerably