Risch algorithm

Remarks

The procedure works down the tower. It writes $f$ in terms of the last generator $t_m$ and uses Liouville's theorem to predict the form of a possible antiderivative. This reduces the problem to integration and to differential equations in the smaller field $C(x)(t_1, \dots, t_{m-1})$. The cases of logarithms and exponentials (the transcendental case) are simpler than the algebraic case.

Example: for $F = \Q(x, e^x)$ and $f = x e^x$, the procedure looks for $g = q e^x$ with $q \in \Q(x)$ and $q' + q = x$, finds $q = x - 1$, and returns $g = (x - 1) e^x$.

Example: for $F = \Q(x, e^{x^2})$ and $f = e^{x^2}$, the same reduction asks for $q \in \Q(x)$ with $q' + 2x q = 1$; there is none, so the procedure reports that $e^{x^2}$ has no elementary antiderivative.

Non-example: a table of integrals finds many antiderivatives, but it fails clause 2, because it cannot certify that an integral not in the table is not elementary.

The algorithm needs a way to decide whether a constant expression equals $0$. For constants built from $\pi$, $e$ and other transcendental numbers this is a hard problem, so in practice the algorithm is only as complete as the zero test for constants.