FoCM 2014 conference

Workshop A6 - Real Number Complexity

December 13, 15:00 ~ 15:30 - Room A22

On the number of zeros of $E$-polynomials

Universidad de Buenos Aires - CONICET, Argentina   -   jeronimo@dm.uba.ar

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 \mathbb{Z}[X,Y]$ and $h\in \mathbb{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 $\mathbb{R}$ and in an interval of $\mathbb{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.

Joint work with María Laura Barbagallo (Universidad de Buenos Aires - CONICET), Juan Sabia (Universidad de Buenos Aires - CONICET).