The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometry, and the four operations (+ − × ÷). Laplace solved this problem for the case of rational functions, as he showed that the indefinite integral of a rational function is a rational function and a finite number of constant multiples of logarithms of rational functions. The algorithm suggested by Laplace is usually described in calculus textbooks but was only implemented in the 1960s.
Liouville formulated the problem solved by the Risch algorithm. Liouville proved by analytical means that if there is an elementary solution g to the equation g ′ = f then for constants αi and elementary functions ui and v the solution is of the form
Risch developed a method that allows one to only consider a finite set of elementary functions of Liouville's form.
The intuition for the Risch algorithm comes from the behavior of the exponential and logarithm functions under differentiation. For the function f eg, where f and g are differentiable functions, we have
so if eg were in the result of an indefinite integration, it should be expected to be inside the integral. Also, as
then if lnng were in the result of an integration, then only a few powers of the logarithm should be expected.
An important consequence of Risch's result is that the Gaussian integral has no elementary antiderivative.
Finding an elementary antiderivative is very sensitive to details. For instance, the following function has an elementary antiderivative:
But if you will change 71 to 72, it will not be possible to represent the antiderivative using elementary functions. The reason is that the Galois group of
is D(4), e.g. generated by permutations (1 2 3 4) and (1 3), and contains 8 elements (same as in ), while the Galois group of
is S(4), e.g. generated by permutations (1 2), (1 3), (1 4), and contains 24 elements.
For example, all known programs (except Axiom) cannot find the antiderivative for
Axiom can solve the above case, the result being:
Note that a lot of programs (including Maple and Mathematica) can find the antiderivative for the above function using non-elementary functions (which is not the topic for Risch algorithm).
The following is a more complex example, which no software (as of March 2008) is known to find an antiderivative for:
While the antiderivative for the above has a short form:
Also, the Risch algorithm is not an "algorithm" literally, because it needs as a part to check if some expression is equivalent to zero. And for a common meaning of what an "elementary function" is it's not known whether such an algorithm exists or not (so current computer algebra systems use heuristics); moreover, if one will add abs(x) to the list of elementary functions, it is known that no such algorithm exists, see Richardson's theorem.