Risch algorithm

A decision procedure for integration in finite terms: given an elementary function, it either finds an elementary antiderivative or proves that none exists. It rests on Liouville's theorem, which fixes the form any elementary antiderivative must have, and works through a tower of logarithmic and exponential extensions of the rational functions.

An elementary function is built from $x$ and constants by arithmetic, $exp$ , $lo g$ and algebraic operations. Liouville's theorem: if $f$ in a differential field $K$ has an elementary antiderivative, then it has one of the form

\int f = v_{0} + i = 1 \sum n c_{i} lo g v_{i}, v_{i} \in K, c_{i} constant

with the $c_{i}$ algebraic over the constants of $K$ . An antiderivative can add new logarithms with constant coefficients and nothing else, which turns the question of whether one exists into the question of whether certain equations have solutions in $K$ .

The algorithm writes $f$ in a tower $C (x) (t_{1}) \dots (t_{n})$ , each $t_{i}$ the logarithm or exponential of an element below it, and integrates with respect to the top variable $t = t_{n}$ , treating $f$ as a rational function of $t$ over the field below. Hermite reduction removes the repeated factors of the denominator. For the remaining part $A / D$ with $D$ squarefree, the coefficients of the logarithms are the roots of a resultant (Rothstein–Trager):

c_{i} \in {z : res_{t} (D, A - z D^{'}) = 0}

and they must be constants, or there is no elementary antiderivative. When $t = e^{u}$ , the polynomial part leads to the Risch differential equation $y^{'} + f y = g$ , to be solved for $y$ in the field below.^[1]

Take $\int e^{x^{2}} d x$ . With $t = e^{x^{2}}$ , Liouville's theorem forces any elementary antiderivative to be $y t$ plus a constant, for some $y \in C (x)$ . Differentiating,

(y e^{x^{2}})^{'} = (y^{'} + 2 x y) e^{x^{2}} = e^{x^{2}} ⟺ y^{'} + 2 x y = 1

If $y$ had a pole of order $k$ at some point, $y^{'}$ would have one of order $k + 1$ there that no other term can cancel, so $y$ is a polynomial. A nonzero polynomial of degree $n$ makes $y^{'} + 2 x y$ a polynomial of degree $n + 1 \geq 1$ , never the constant 1, and $y = 0$ gives 0. So there is no solution, and $e^{x^{2}}$ has no elementary antiderivative. With right-hand side $x$ instead of 1 the equation has the solution $y = \frac{1}{2}$ , which is $\int x e^{x^{2}} d x = \frac{1}{2} e^{x^{2}}$ .

The transcendental case, towers of exponentials and logarithms over $C (x)$ , is completely algorithmic. The algebraic case, extensions by roots of polynomials, was completed later by Trager and Bronstein^[3] and is rarely implemented in full. Either way the algorithm needs to decide whether a constant is zero, which is undecidable for general elementary constants, so it is a decision procedure relative to a constant field where equality can be decided.