Using Gröbner bases for finding the logarithmic part of the integral of transcendental functions (Q432759)

Symbolic integration is one of the most famous problems of symbolic computation, as well as a major driver of the development of computer algebra systems. As the antiderivative of an elementary function \(f\) must exist in a logarithmic extension of the differential field containing \(f\), the question of computing the logarithmic part of the integral is of fundamental importance. An early approach to this problem was discovered independently by \textit{M. Rothstein} [Aspects of symbolic integration and simplification of exponential and primitive functions. PhD Thesis, University of Wisconsin-Madison (1976)] and \textit{B. M. Trager} [in: Proceedings of the 1976 ACM Symposium on symbolic and algebraic computation, Yorktown Heights/N.Y.. 219--226 (1976; Zbl 0498.12005)]. This requires computing an algebraic extension of the differential field. Later, \textit{D. Lazard} and \textit{R. Rioboo} published a method that uses subresultants to avoid algebraic extensions when one is working with a rational function [J. Symb. Comput. 9, No. 2, 113--115 (1990; Zbl 0723.68053)]; \textit{M. Bronstein} showed that this method could be extended to certain transcendental functions [Symbolic integration I: Transcendental functions. Berlin: Springer (2005; Zbl 1059.12002)]. More recent work of \textit{G. Czichowski} showed that one could also avoid algebraic extensions through the use of Gröbner bases [J. Symb. Comput. 20, No. 2, 163--167 (1995; Zbl 0844.13017)]. Like the work of Lazard and Rioboo, the technique was limited to rational functions. This article generalizes Czichowski's result for the same class of transcendental functions for which Bronstein generalized Lazard and Rioboo's. This requires the correction and strengthening of a theorem in Bronstein's book, and the generalization of three lemmas of Czichowski. The main new result, Theorem 8, outlines a new algorithm that constructs one Gröbner basis that satisfies a ``structure theorem'' due to Lazard, then converts it to a new ordering using the FGLM algorithm. This second basis is used to build the desired function. An analysis of the algorithmic efficiency follows. Aside from a complexity analysis which shows that the new algorithm is as efficient as the approach of Lazard and Rioboo, the author explains how to shorten the FGLM phase, and how to detect that no elementary integral exists. The article concludes with three examples. The second illustrates how the new algorithm successfully integrates expressions that Mathematica, Maple, and Maxima could not then solve. While the algorithm does not succeed at computing the third integral, it does detect that this requires the computation of \(\int 1/\log(x) dx\), which is not elementary. The article is pleasant to read; the author's comments lend insight, and the examples are genuinely interesting.