Exp-log functions f are, roughly speaking, built up from polynomials by algebraic operations, exponentiation, and taking logarithms; therefore, they include reciprocals and radicals. This paper is concerned with roots: points x where f(x)=0, but f(y) ≠ 0 for all y “near” x. The author notes that f(x)=x-√x2=x-exp(½ log x2) has no roots in this sense, even though it is zero for all x > 0. This function is undefined at x=0, since log x2 is undefined, and the author notes that its continuous extension to the whole of the real line is not exp-log, since it is not differentiable at zero. In fact, even f(x) exp(-1/x2), which is apparently defined everywhere, infinitely differentiable, and has no roots for the same reason, is not exp-log, since it is not analytic at zero.
The method relies on the author’s idea of semi-Fourier series, an adaptation of the semi-Budan series [1], and a vast generalization of Sturm sequences used for isolating roots of polynomials. The algorithm relies on being able to test for zero, which is only known to be possible if we assume Schanuel’s conjecture [2], though the author in fact uses a weaker heuristic method that he has never seen fail.
The process seems practicable: sub-second times for all examples from the literature, and only 5.5 seconds for an example with two roots within 10-377 of each other. This is a significant theoretical and practical development, and deservedly won the best paper award at the International Symposium on Symbolic and Algebraic Computation (ISSAC) 2008.
