On the number of zeros of E-polynomials

GABRIELA JERONIMO

Montevideo

Conferencia; Foundations of Computational Mathematics (FoCM'14) Conference; 2014

Foundations of Computational Mathematics

An E-polynomial in a single variable with integer coefficients is a real function of the form P(x, e^{h(x)}), where P(X,Y) in Z[X,Y] and h in Z[X]. These functions form a particular subclass of the so-called Pfaffian functions introduced by Khovanskii in the 70's. As proved by Vorobjov in 1992, the consistency problem  for (multivariate) E-polynomials is algorithmically decidable. We will present an algorithm for the computation of the number of zeros of an E-polynomial in t and in an interval of R. Our algorithm is inspired in the well-known Sturm's Theorem for real univariate polynomials. It relies on the construction, from the polynomials P and h, of adequate sequences of E-polynomials and the sign determination of their evaluation at algebraic real numbers. We prove that the number of real zeros of P(x, e^{h(x)}) can be computed from the number of sign changes of these sequences evaluated at finitely many points that are obtained throughout the construction.In order to determine sign changes, we also develop an algorithmic procedure to compute the sign of an E-polynomial evaluated at an algebraic real number given by its Thom encoding.