Risch algorithm

The Risch algorithm decides whether an elementary function has an elementary antiderivative and computes one when it does^[1]^[5]. An elementary function is built from $x$ and constants by arithmetic, $exp$ , $lo g$ and algebraic operations; the question is whether its integral can be expressed in the same way. Liouville showed in the 1830s that an elementary antiderivative, if it exists, has a restricted form^[6], and Risch turned this into an algorithm in 1968–1970 by working in a tower of field extensions and reducing each step to problems in the field below^[1]. It proves, for example, that $\int e^{x^{2}} d x$ , $\int e^{x} / x d x$ and $\int d x / lo g x$ are not elementary. Its rational-function steps are Hermite reduction and the Rothstein–Trager resultant; its transcendental case is fully algorithmic and is presented in Bronstein's book^[4], while the algebraic case was completed by Davenport, Trager and Bronstein^[3]^[10]^[11].

§ 01

Example

\int x^{3} e^{x^{2}} d x = \frac{1}{2} (x^{2} - 1) e^{x^{2}} \int x^{2} e^{x^{2}} d x is not elementary

The first integral can be found by substitution and parts. For the second, no finite search over candidate formulas could show that none exists; the Risch algorithm proves it by showing that a certain differential equation has no rational solution.

§ 02

Differential fields

The algorithm works algebraically, in differential fields^[2]^[4]. A derivation on a field $K$ is an additive map $D$ satisfying $D (ab) = a D (b) + b D (a)$ ; write $a^{'} = D (a)$ . The constants are the elements with $a^{'} = 0$ . The field $Q (x)$ with $d / d x$ is the base case. An extension $K (t)$ is elementary over $K$ if $t$ is

a logarithm: an exponential: or algebraic over K t^{'} = u^{'} / u, t^{'} = u^{'} t,

for some $u \in K$ , with no new constants. An elementary function is an element of a tower $K_{0} \subset K_{1} \subset \dots \subset K_{n}$ of such extensions starting from $C (x)$ or $Q (x)$ . The derivative of any element is again in the tower, so differentiation is closed-form; the question is only about integration.

§ 03

Liouville's theorem

If $f$ in a differential field $K$ has an elementary antiderivative, then it has one of the form^[6]^[8]

\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 introduce new logarithms with constant coefficients and nothing else: no new exponentials, and no new algebraic functions beyond constants. Rosenlicht gave the purely algebraic proof used today^[8]^[2]. The theorem turns the question of whether an antiderivative exists into the question of whether certain equations have solutions in $K$ .

§ 04

The algorithm

The integrand is written as a rational function of the top variable of a tower. Hermite reduction and the Rothstein–Trager resultant handle its fractional part; the polynomial part leads to integration problems, or a Risch differential equation, one level down.

The algorithm writes $f$ in a tower $K (t)$ , with $t$ the last logarithm or exponential adjoined, and integrates it as a rational function of $t$ whose coefficients lie in $K$ . The derivation extends to polynomials in $t$ through $t^{'}$ , and the rational function algorithms carry over^[4]:

Hermite reduction in $t$ removes the repeated factors of the denominator. For the remaining fraction $A / D$ with $D$ square-free, the coefficients of the logarithms must be the roots of the Rothstein–Trager resultant

R (z) = res_{t} (D, A - z D^{'})

and by Liouville's theorem they must be constants. If some root is not constant, there is no elementary antiderivative; otherwise the logarithmic part is $\sum c_{i} lo g g cd (D, A - c_{i} D^{'})$ . The polynomial part in $t$ is handled coefficient by coefficient, which leads to problems in $K$ , solved recursively.

Logarithmic extensions

For $\int d x / (x lo g x)$ , take $K = Q (x)$ and $t = lo g x$ , so the integrand is $A / D$ with $A = 1/ x$ , $D = t$ and $D^{'} = t^{'} = 1/ x$ . Then $R (z) = (1 - z) / x$ has the constant root $z = 1$ , and the integral is $lo g t = lo g lo g x$ . For $\int d x / lo g x$ , $A = 1$ and $R (z) = 1 - z / x$ , whose root $z = x$ is not constant, so the logarithmic integral $li (x)$ is not elementary.

A polynomial $\sum a_{i} t^{i}$ in a logarithm integrates to a polynomial of degree at most one higher, and comparing coefficients from the top gives a sequence of integration problems in $K$ , each of which may itself introduce the logarithm $t$ with a constant coefficient^[4]^[12].

Exponential extensions

If $t = e^{u}$ , then $(y t^{i})^{'} = (y^{'} + i u^{'} y) t^{i}$ , so the term $a_{i} t^{i}$ of the polynomial part, for $i \neq = 0$ , has an integral $y_{i} t^{i}$ exactly when

y_{i}^{'} + i u^{'} y_{i} = a_{i}

has a solution $y_{i} \in K$ . This is the Risch differential equation. The term $a_{0}$ is integrated in $K$ recursively.

§ 05

The Risch differential equation

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 Q (x)$ . Differentiating,

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

so $y^{'} + 2 x y = 1$ must hold. 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 same two arguments decide $y^{'} + f y = g$ over $Q (x)$ whenever $f$ is a nonzero polynomial. The pole argument bounds the denominator of $y$ by $g cd (E, E^{'})$ for the denominator $E$ of $g$ , and comparing degrees at infinity bounds its numerator; the numerator's coefficients then satisfy a linear system^[4]. In general $f$ and $g$ lie in a tower, and bounding the denominator and degree is the hard part of the transcendental case, including cancellation cases where the leading terms of $y^{'}$ and $f y$ can cancel^[4].

The Risch differential equation over ℚ(x) for a polynomial f, which decides whether ∫ g·e^q is elementary for rational g and polynomial q.

(* y' + f y = gn/ge. A pole of y of order k gives y' a pole of order k + 1
   that f y cannot cancel, so the denominator of y divides gcd(ge, ge'),
   and comparing degrees at infinity bounds its numerator. *)
let solve_rde (f : t) (gn : t) (ge : t) =
  let h = gcd gn ge in
  let gn = quo gn h and ge = quo ge h in
  if is_zero gn then Some ([||], one)
  else begin
    let t = gcd ge (deriv ge) in
    let n = deg gn - deg ge - deg f + deg t in
    if n < 0 then None
    else begin
      (* multiply through by t^2 ge: (Y' t - Y t') ge + f Y t ge = gn t^2 *)
      let op yv = add (mul (sub (mul (deriv yv) t) (mul yv (deriv t))) ge) (mul f (mul yv (mul t ge))) in
      let cols = Array.init (n + 1) (fun i -> op (pow x i)) in
      match solve_linear cols (mul gn (mul t t)) with
      | None -> None
      | Some ys ->
          let yn = normalize ys in
          let g = gcd yn t in
          Some (quo yn g, quo t g)
    end
  end

Integrals of x^k e^(x²) and others.

open Qpoly

Running it.

x^k e^(x^2):
  integral of e^(x^2)                      is not elementary
  integral of x e^(x^2)                  = (1/2) e^(x^2)
  integral of x^2 e^(x^2)                  is not elementary
  integral of x^3 e^(x^2)                = ((1/2)x^2 - 1/2) e^(x^2)
  integral of x^4 e^(x^2)                  is not elementary
  integral of x^5 e^(x^2)                = ((1/2)x^4 - x^2 + 1) e^(x^2)
other exponents:
  integral of (2x^2 + 1) e^(x^2)         = x e^(x^2)
  integral of x^3 e^(x)                  = (x^3 - 3x^2 + 6x - 6) e^(x)
  integral of e^(x^3)                      is not elementary
  integral of (3x^3 + 1) e^(x^3)         = x e^(x^3)

For $x^{k} e^{x^{2}}$ the degree argument settles everything: $y^{'} + 2 x y = x^{k}$ needs $de g y = k - 1$ , and the coefficients of $y^{'} + 2 x y$ alternate in parity, so a solution exists exactly when $k$ is odd.

Rational multiples of exponentials, including the exponential integral.

open Qpoly

Running it.

integral of (1/x) e^(x)                    is not elementary
integral of ((x - 1)/x^2) e^(x)          = (1/x) e^(x)
integral of (x/(x^2 + 2x + 1)) e^(x)     = (1/(x + 1)) e^(x)
integral of (1/x^2) e^(x)                  is not elementary
integral of ((2x^2 - 1)/x^2) e^(x^2)     = (1/x) e^(x^2)

The first and fourth are the exponential integral $Ei (x)$ and $Ei (x) - e^{x} / x$ : the equation $y^{'} + y = 1/ x$ would need a pole of order 0 in $y$ , so $y$ is a polynomial and $y^{'} + y$ is too.

§ 06

The algebraic case and constants

When the tower contains algebraic extensions, such as $x^{3} + 1$ , the Liouville form still holds but the logarithmic part may require the arguments $v_{i}$ to be algebraic functions, and deciding whether they exist involves the arithmetic of divisors on an algebraic curve, including whether a divisor has finite order. Risch sketched this case^[5]; Davenport gave an algorithm for purely algebraic integrands^[10], Trager a complete treatment of them^[3], and Bronstein extended it to mixed towers^[11]. The algebraic case is rarely implemented in full.

Every step needs to decide whether a constant is zero: whether $R (z)$ has constant roots, whether a leading coefficient vanishes, whether a new extension adds new constants. For constants built from $π$ , $e$ and elementary functions this is not known to be decidable, and Richardson showed that related problems for elementary functions of a real variable are undecidable^[9]. The Risch algorithm is therefore a decision procedure relative to a constant field in which equality can be decided, such as $Q$ or a number field.

§ 07

Implementations

Computer algebra systems combine parts of the algorithm with heuristics, pattern matching and table lookup^[12]. Bronstein implemented large parts of the transcendental and algebraic cases in the Axiom system, whose integrator lives on in FriCAS. SymPy's risch_integrate implements the transcendental case for towers of exponentials and logarithms and can return a proof of non-elementarity as an unevaluated NonElementaryIntegral. The rational-function steps are implemented everywhere.

§ 08

History

Liouville developed the theory of integration in finite terms between 1833 and 1841, proving among other results that $\int e^{x^{2}} d x$ and $\int e^{x} / x d x$ are not elementary^[6]. Ritt's 1948 book presented Liouville's theory in modern form^[7], and Rosenlicht gave the algebraic proof of Liouville's theorem in 1968^[8]. Risch published the decision procedure for the transcendental case in 1969 and announced the algebraic case in 1970^[1]^[5]. The rational steps were improved by Rothstein and Trager's resultant in 1976 and Lazard and Rioboo's subresultant method in 1990. Davenport in 1981 and Trager in 1984 made the algebraic case algorithmic^[10]^[3], and Bronstein's work in the 1990s, collected in his book, gave the transcendental case its present form^[4]^[11].