Zero counting for a class of univariate Pfaffian functions (Q5964515)

Given an integer polynomial \(\mathrm{F}(X,Y)\), this paper introduces first a new symbolic algorithm to count the number of real zeros in a real interval of \(f(x)=\mathrm{F}(x,\varphi(x))\), where \(\varphi(x)\) is a univariate Pfaffian function of order 1. This algorithm, which is called \texttt{ZeroCounting}, uses Sturm sequences associated to \(f(x)\) and Subresultants as essential tools, and relies on an oracle for sign determination. In some sense, this work is a continuation of \textit{D. Richardson} [in: ISSAC '91. Proceedings of the 1991 international symposium on Symbolic and algebraic computation. Bonn, Germany, July 15--17, 1991. New York, NY: ACM Press. 247--255 (1991; Zbl 0925.65091)], where Sturm sequences of transcendental functions are introduced, and [\textit{A. Maignan}, in: Proceedings of the 1998 international symposium on symbolic and algebraic computation, ISSAC '98, Rostock, Germany, August 13--15, 1998. New York, NY: ACM Press. 215--221 (1998; Zbl 0924.65044)], where the function \(\mathrm{F}(x,e^x)\) is studied. Secondly, in the particular case of \(E\)-polynomials, that is, \(f(x)=\mathrm{F}(x,e^{h(x)})\) with \(h(X)\in \mathbb{Z}[X]\), the algorithm \texttt{ZeroCounting} is modified in order to obtain a zero counting algorithm with no calls to oracles. The complexity analysis of each subroutine used is provided. In addition, an explicit upper bound for the absolute value of the real zeros of an E-polynomial is also presented. Examples are not given.