$SPAD/src/input risch.input

Timothy Daly December 3, 2016

Abstract

Contents

2

1 The Risch Algorithm

The Risch algorithm (see Ris68, Ris69a, Ris69b), named after Robert H. Risch, is an algorithm for the calculus operation of indefinite integration (i.e., finding antiderivatives). The algorithm transforms the problem of integration into a problem in algebra. It is based on the form of the function being integrated and on methods for integrating rational functions, radicals, logarithms, and exponential functions. Risch, who developed the algorithm in 1968, called it a decision procedure, because it is a method for deciding if a function has an elementary function as an indefinite integral, and also, if it does, determining it. The Risch algorithm is described (in more than 100 pages) in “Algorithms for Computer Algebra” by Keith O. Geddes, Stephen R. Czapor and George Labahn (see GCL92). The Risch-Norman algorithm, a faster but less powerful technique, was developed in 1976.

The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometry, and the four arithmetic 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; as a computer program it was finally implemented in the 1960s.

Liouville (see Lio1833a) 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 u_{i} and v the solution of the form

g = v + ∑_{i<n} α_{i} ln(u_{i})

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 fe^{g}, where f and g are differentiable functions, we have

(f · e^{g})′ = (f′ + f · g′) · e^{g},

so if e^{g} were in the result of an indefinite integration, it should be expected to be inside the integral. Also, as

(f · ln^{n} g)′ = f′ ln^{n} g + nf \frac{g′}{g} ln^{n−1} g

then if ln^{n} g were in the result of an integraiton, then only a few powers of the logarithm should be expected.

An important consequence of Risch’s result is that the Gaussian integral

∫_{−∞}^{∞} e^{−x^{2}} dx = \sqrt{π}

has no elementary antiderivative.

1.1 Problem examples

Finding an elementary antiderivative is very sensitive to details. For instance, the following function has an elementary antiderivative:

f(x) = \frac{x}{\sqrt{x^{4} + 10x^{2} − 96x − 71}}

— * —

)set break resume
)sys rm -f risch.output
)spool risch.output
)set message test on
)set message auto off
)clear all
--S 1 of 8
f:=x/(sqrt(x^4+10*x^2-96*x-71))
--R
--R
--R                   x
--R   (1)  -----------------------
--R         +--------------------+
--R         | 4      2
--R        \|x  + 10x  - 96x - 71
--R                                                    Type: Expression(Integer)
--E 1
--S 2 of 8
integrate(f,x)
--R
--R
--R   (2)
--R   -
--R        log
--R                                                    +--------------------+
--R               6      4      3      2               | 4      2                8
--R             (x  + 15x  - 80x  + 27x  - 528x + 781)\|x  + 10x  - 96x - 71  - x
--R           +
--R                  6       5      4        3        2
--R             - 20x  + 128x  - 54x  + 1408x  - 3124x  - 10001
--R     /
--R        8
--R                                         Type: Union(Expression(Integer),...)
--E 2

———-

But if 71 is changed to 72, it is not possible to represent the antiderivative using elementary functions. The reason is that the Galois group of

x^{4} + 10x^{2} − 96x − 71

is D(4), e.g. generated by permutations (1 2 3 4) and (1 3), and contains 8 elements (same as in x^{4} − 2), while the Galois group of

x^{4} + 10x^{2} − 96x − 72

is S(4), e.g. generated by permutations (1 2), (1 3), (1 4), and contains 24 elements.

— * —

--S 3 of 8
g:=x/(sqrt(x^4+10*x^2-96*x-72))
--R
--R
--R                   x
--R   (3)  -----------------------
--R         +--------------------+
--R         | 4      2
--R        \|x  + 10x  - 96x - 72
--R                                                    Type: Expression(Integer)
--E 3
--S 4 of 8
integrate(g,x)
--R
--R
--R           x
--I         ++              %S
--I   (4)   |   -------------------------- d%S
--R        ++    +-----------------------+
--R              |  4       2
--I             \|%S  + 10%S  - 96%S - 72
--R                                         Type: Union(Expression(Integer),...)
--E 4

———-

1.2 Implementation

Transforming the Risch decision procedure into an algorithm that can be executed by a computer is a complex task that requires the use of heuristics and many refinements. No software (as of March 2008) is known to implement the full Risch algorithm, although several computer algebra systems have partial implementations. The only software that claims it has implemented in full the negative part is Axiom (e.g. if Axiom says “no” this means that antiderivative cannot be represented using elementary functions, but in many cases Axiom says “error”).

For example, of all known programs, only Axiom can find an elementary antiderivative for the following function.

— * —

)clear all
--S 5 of 8
f:=x/(sqrt(x^4+10*x^2-96*x-71))
--R
--R
--R                   x
--R   (1)  -----------------------
--R         +--------------------+
--R         | 4      2
--R        \|x  + 10x  - 96x - 71
--R                                                    Type: Expression(Integer)
--E 5

———-

The solution returned by Axiom is

\begin{aligned}F (x) & = & −\frac{1}{8} ln ((x^{6} + 15x^{4} − 80x^{3} + 27x^{2} − 528x + 781)\sqrt{(}x^{4} + 10x^{2} − 96x − 71) \\ & & −(x^{8} + 20x^{6} − 128x^{5} + 54x^{4} − 1408x^{3} + 3124x^{2} + 10001)) + C \end{aligned}

— * —

--S 6 of 8
integrate(f,x)
--R
--R
--R   (2)
--R   -
--R        log
--R                                                    +--------------------+
--R               6      4      3      2               | 4      2                8
--R             (x  + 15x  - 80x  + 27x  - 528x + 781)\|x  + 10x  - 96x - 71  - x
--R           +
--R                  6       5      4        3        2
--R             - 20x  + 128x  - 54x  + 1408x  - 3124x  - 10001
--R     /
--R        8
--R                                         Type: Union(Expression(Integer),...)
--E 6

———-

Many programs (including Maple and Mathematica) can find the antiderivative for the above function using non-elementary functions (i.e. elliptic integrals, that is, integrals of the form

f(x) = ∫_{c}^{x} R(t, P (t)) dt

where R is a rational function of its two arguments, P is the square root of a polynomial of degree 3 or 4 with no repeated roots, and c is a constant) (see NIST10, AS64), which are outside the scope of the Risch algorithm).

The following function s a more complex example, which most software cannot find an elementary antiderivative for.

f(x) = \frac{x^{2} + 2x + 1 + (3x + 1)\sqrt{x + ln x}}{x\sqrt{x + ln x}(x + \sqrt{x + ln x})}

— * —

)clear all
--S 7 of 8
f:=(x^2+2*x+1+(3*x+1)*sqrt(x+log(x)))/(x*sqrt(x+log(x))*(x+sqrt(x+log(x))))
--R
--R
--R                 +----------+    2
--R        (3x + 1)\|log(x) + x  + x  + 2x + 1
--R   (1)  -----------------------------------
--R           2 +----------+               2
--R          x \|log(x) + x  + x log(x) + x
--R                                                    Type: Expression(Integer)
--E 7
--S 8 of 8
integrate(f,x)
--R
--R
--RDaly Bug
--R   >> Error detected within library code:
--R   integrate: implementation incomplete (constant residues)
--R
--R   Continuing to read the file...
--R
--E 8
)spool
)lisp (bye)

———- In fact, the antiderivative of this function has a fairly short form

F (x) = 2(\sqrt{x + ln x} + ln(x + \sqrt{x + ln x})) + C

1.3 Decidability

The Risch Algorithm applied to general functions is not an algorithm but a semi-algorithm because it needs as a part to check if some expression is equivalent to zero, (constant problem), in particular in the constant field. For a common meaning of an elementary function it is not known whether such an algorithm exists or not (current computer algebra systems use heuristics), moreover, if one adds the absolute value function to the list of elementary functions, it is known that no such algorithm exists, see Richardson’s theorem (see RF94)

Note that, technically, this issue also arises in the polynomial division algorithm, it will not work correctly if it cannot correctly determine if the coefficients are identically 0. Therefore, the Risch Algorithm requires that the constant field be computable, i.e., that for elements not dependent on x, that the problem of zero-equivalence is decidable.

1.4 License

This information was originally published under Wikipedia under the CC-BY-SA license (

http://creativecommons.org/licenses/by-sa/3.0/) on the page
(http://en.wikipedia.org/w/index.php?title=Risch_algorithm#Implementation)

References

[1] Wikipedia web page

http://en.wikipedia.org/w/index.php?title=Risch_algorithm#Implementation

[2] Creative Common License

http://creativecommons.org/licenses/by-sa/3.0