Algorithms for Indefinite and Definite Integration in MapleK.O. Geddes Symbolic Computation Group Department of Computer Science University of Waterloo Waterloo ON N2L 3G1 CANADA http://www.uwaterloo.ca/~kogeddes

The Risch integration algorithm for computing indefinite integrals (antiderivatives) of transcendental elementary functions is described. Extensions of this algorithm to handle algebraic functions, and to the case of non-elementary special functions, are mentioned briefly with pointers to the relevant literature. On the problem of computing definite integrals in closed form, some practical issues associated with the application of the Fundamental Theorem of Calculus are described. For some particular classes of definite integrals involving special functions, current research work is briefly described in which the approach is to convert the integrand to a Meijer G function representation, to apply known formulas for definite integrals of products of Meijer G functions, and then to convert the result, if possible, to a representation in terms of standard functions.

The ProblemGiven a function NiMtJSJmRzYjJSJ4Rw==, determine whether there exists a function NiMtJSJnRzYjJSJ4Rw== such that NiMvLSUlZGlmZkc2JC0lImdHNiMlInhHRiotJSJmR0Ypi.e. determine an indefinite integral, or antiderivative, of NiMtJSJmRzYjJSJ4Rw== . We will writeNiMvLSUkaW50RzYkLSUiZkc2IyUieEdGKi0lImdHRik=where we do not explicitly write the arbitrary constant of integration.A detailed development of the Risch integration algorithm presented here can be found in the textbook [Geddes92]. Additional material on the Risch algorithm appears in [Bronstein90b], [Bronstein97].In this presentation, examples will be shown using the Maple computer algebra system.

f := x*(x+1)*( (x^2*exp(2*x^2) - ln(x+1)^2)^2 + 2*x*exp(3*x^2)*( x - (2*x^3+2*x^2+x+1)*ln(x+1) )) / ((x+1)*ln(x+1)^2 - (x^3+x^2)*exp(2*x^2) )^2:Int(f,x);value(%);

The Risch integration algorithm is a decision procedure by which we mean that given an integrand NiMtJSJmRzYjJSJ4Rw==, the algorithm will determine:Does there exist a function NiMtJSJnRzYjJSJ4Rw== in a specified class of functions such that NiMvLSUlZGlmZkc2JC0lImdHNiMlInhHRiotJSJmR0Yp ?If yes then determine NiMtJSJnRzYjJSJ4Rw== .If the answer to the existence question is no then the algorithm has constructed a proof of nonexistence.Such a decision procedure is only possible in a context where we have clearly specified the class of functions (the function field) containing NiMtJSJnRzYjJSJ4Rw== . For example, we will consider the field of elementary functions. In this function field, the Risch algorithm will determine that the integral NiMtJSRpbnRHNiQtJSRleHBHNiMsJCokJSJ4RyIiIyEiIkYr does not exist. However, if we allow the question to be expanded beyond the field of elementary functions then this integral can be expressed, as shown below by Maple.Int(exp(-x^2), x) = int(exp(-x^2), x);Definition of Elementary FunctionsLet NiMlIkZH be a differential field (i.e. a function field on which derivation is defined) and let NiMlIkdH be a differential extension field of NiMlIkZH . Let the derivation operation be denoted by prime ( ' ) .For NiMlJnRoZXRhRw== in NiMlIkdH , if there exists NiMlInVH in NiMlIkZH such that NiMvKSUmdGhldGFHJSInRyomKSUidUdGJiIiIkYpISIi then we write NiMvJSZ0aGV0YUctJSRsb2dHNiMlInVH and NiMlJnRoZXRhRw== is called logarithmic over NiMlIkZH .For NiMlJnRoZXRhRw== in NiMlIkdH , if there exists NiMlInVH in NiMlIkZH such that NiMvKiYpJSZ0aGV0YUclIidHIiIiRiYhIiIpJSJ1R0Yn then we write NiMvJSZ0aGV0YUctJSRleHBHNiMlInVH and NiMlJnRoZXRhRw== is called exponential over NiMlIkZH .For NiMlJnRoZXRhRw== in NiMlIkdH , if there exists a polynomial NiMlInBH in NiMlIkZH[NiMlInpH] such that NiMvLSUicEc2IyUmdGhldGFHIiIh then NiMlJnRoZXRhRw== is called algebraic over NiMlIkZH .NiMlJnRoZXRhRw== in NiMlIkdH is transcendental over NiMlIkZH if NiMlJnRoZXRhRw== is not algebraic over NiMlIkZH .NiMlIkdH is called a transcendental elementary extension of NiMlIkZH if NiMvJSJHRy0lIkZHNiUmJSZ0aGV0YUc2IyIiIiUmLn4ufi5HJkYpNiMlIm5H where each NiMmJSZ0aGV0YUc2IyUiaUc= is transcendental and either logarithmic or exponential over the field NiMvJiUiRkc2IywmJSJpRyIiIkYpISIiLUYlNiUmJSZ0aGV0YUc2I0YpJSYufi5+LkcmRi5GJg== .Similarly, NiMlIkdH is an elementary extension of NiMlIkZH if each NiMmJSZ0aGV0YUc2IyUiaUc= is logarithmic, exponential or algebraic over NiMmJSJGRzYjLCYlImlHIiIiRighIiI= .If NiMtJSJLRzYjJSJ4Rw== denotes a differential field of rational functions over a constant field NiMlIktH (a subfield of the complex numbers) and if NiMlIkZH is an elementary extension of NiMtJSJLRzYjJSJ4Rw== then NiMlIkZH is called a field of elementary functions.Similarly, NiMlIkZH is called a field of transcendental elementary functions if NiMlIkZH is a transcendental elementary extension of NiMtJSJLRzYjJSJ4Rw== .

Note that the common notation for elementary functions does not make it clear that an elementary function can be described using only the three types of extensions defined above.

Int(1/(1+x^2), x) = int(1/(1+x^2), x);Int(cos(x), x) = int(cos(x), x);Int(1/sqrt(1-x^2), x) = int(1/sqrt(1-x^2), x);Int(arccosh(x), x) = int(arccosh(x), x);

In the examples above, each integrand and each integral result involves only elementary functions. To see that these functions conform to the definition of elementary functions of the preceding section, we must convert the functions to complex exp-log form.

Int(1/(1+x^2), x) = convert(int(1/(1+x^2), x), 'expln');Int(1/2*exp(I*x) + 1/2*exp(-I*x), x) = int(1/2*exp(I*x) + 1/2*exp(-I*x), x);Int(1/sqrt(1-x^2), x) = convert(int(1/sqrt(1-x^2), x), 'expln');Int(convert(arccosh(x),'expln'), x) = int(convert(arccosh(x),'expln'), x);

We can now see a relationship between the input (the integrand) and the output (the integral result). Namely, the types of functions which can appear in the integral result are the same functions that appear in the integrand plus, in some cases, new log extensions. This fact is known as Liouville's Principle: the only new functions needed are constant multiplies of log extensions.The common notation hides this relationship.

Theorem 1Given NiMtJSJmRzYjJSJ4Rw== in an elementary function field NiMlIkZH , NiMtJSRJbnRHNiQtJSJmRzYjJSJ4R0Yp , if it exists as an elementary function, can be expressed in the formNiMvLSUkSW50RzYkLSUiZkc2IyUieEdGKiwmLSYlInZHNiMiIiFGKSIiIi0lJFN1bUc2JComJiUiY0c2IyUiaUdGMS0lJGxvZ0c2Iy0mRi5GOEYpRjEvRjk7RjElIm1HRjE=with NiMtJiUidkc2IyIiITYjJSJ4Rw== in NiMlIkZH , NiMmJSJjRzYjJSJpRw== constants, and NiMtJiUidkc2IyUiaUc2IyUieEc= in NiMtJSJGRzYlJiUiY0c2IyIiIiUmLn4ufi5HJkYnNiMlIm1H .Note: The constants NiMmJSJjRzYjJSJpRw== may involve new algebraic number extensions.

Given a rational function NiMtJSJmRzYjJSJ4Rw==, Liouville's Principle states that its integral can be expressed as a rational function plus (possibly) some constant multiples of NiMlJGxvZ0c= functions. (Note that Maple's notation for the natural logarithm function is NiMtJSNsbkc2IyUieEc= rather than NiMtJSRsb2dHNiMlInhH .)For the case of rational functions, the integral always exists as an elementary function.

Int(1/(x^2+2*x+1), x) = int(1/(x^2+2*x+1), x);Remark: No NiMlJGxvZ0c= terms required in the above example.Int(1/(x^3+x), x) = int(1/(x^3+x), x);Remark: No algebraic number extensions required in the above example.Int(1/(x^2-2), x) = `int/risch`(1/(x^2-2), x);Remark: In the latter example, the constant field needed to be extended by the algebraic number NiMtJSVzcXJ0RzYjIiIj .Minimal algebraic extensions are desired for efficiency.For example, from above noting that NiMvLCYqJCUieEciIiQiIiJGJkYoKihGJkYoLCZGJkYoJSJJR0YoRigsJkYmRihGKyEiIkYo would lead to the following representation of the integral:NiMvLSUkSW50RzYkKiYiIiJGKCwmKiQlInhHIiIkRihGK0YoISIiRissKC0lI2xuRzYjRitGKComLUYwNiMsJkYrRiglIklHRihGKCIiI0YtRi0qJi1GMDYjLCZGK0YoRjZGLUYoRjdGLUYt .Goal: Avoid introducing algebraic numbers except when necessary.

We want to reduce the problem as follows:NiMvLSUkSW50RzYkKiYtJSJwRzYjJSJ4RyIiIi0lInFHRiohIiJGKywmKiYtJSJDR0YqRiwtJSJER0YqRi9GLC1GJTYkKiYtJSJBR0YqRiwtJSJCR0YqRi9GK0Yswhere NiMyLSUkZGVnRzYjLSUiQUc2IyUieEctRiU2Iy0lIkJHRik= and where NiMtJSJCRzYjJSJ4Rw== is monic and square-free.Hermite's method is a classical method to achieve this reduction. The reduction is accomplished using basic polynomial operations and without introducing any algebraic number extensions. The method is summarized here.Step 1: Euclidean division with remainder yieldsNiMvLSUkSW50RzYkKiYtJSJwRzYjJSJ4RyIiIi0lInFHRiohIiJGKywmLUYlNiQtJSJQR0YqRitGLC1GJTYkKiYtJSJyR0YqRixGLUYvRitGLA==where NiMvLSUickc2IyUieEciIiE= or NiMyLSUkZGVnRzYjLSUickc2IyUieEctRiU2Iy0lInFHRik= .Step 2: Square-free factorization yieldsNiMvLSUicUc2IyUieEctJShQcm9kdWN0RzYkKS0mRiU2IyUiaUdGJkYvL0YvOyIiIiUia0c=where NiMvLSUkZ2NkRzYkLSYlInFHNiMlImlHNiMlInhHKUYnJSInRyIiIg== for all NiMlImlH ,and where NiMvLSUkZ2NkRzYkLSYlInFHNiMlImlHNiMlInhHLSZGKTYjJSJqR0YsIiIi for NiMwJSJpRyUiakc= .Step 3: Partial fraction expansion yieldsNiMvKiYtJSJyRzYjJSJ4RyIiIi0lInFHRichIiItJSRTdW1HNiQtRi42JComLSZGJjYkJSJpRyUiakdGJ0YpKS0mRis2I0Y2RidGN0YsL0Y3O0YpRjYvRjY7RiklImtHwhere NiMyLSUkZGVnRzYjLSYlInJHNiQlImlHJSJqRzYjJSJ4Ry1GJTYjLSYlInFHNiNGK0Yt .We now haveNiMvLSUkSW50RzYkKiYtJSJyRzYjJSJ4RyIiIi0lInFHRiohIiJGKy0lJFN1bUc2JC1GMTYkLUYlNiQqJi0mRik2JCUiaUclImpHRipGLCktJkYuNiNGO0YqRjxGL0YrL0Y8O0YsRjsvRjs7RiwlImtH .Step 4: Hermite reductions must be applied for each integrand where the denominator is a power NiMlImpH > NiMiIiI= of a square-free factor.After this step, each integral that remains will have a square-free denominator.Consider one integral NiMtJSRJbnRHNiQqJi0mJSJyRzYkJSJpRyUiakc2IyUieEciIiIpLSYlInFHNiNGK0YtRiwhIiJGLg== with NiMlImpH > NiMiIiI= .Apply the Extended Euclidean Algorithm to solve: NiMvLCYqJi0lInNHNiMlInhHIiIiLSYlInFHNiMlImlHRihGKkYqKiYtJSJ0R0YoRiopRislIidHRipGKi0mJSJyRzYkRi8lImpHRig= .This yields NiMvLSUkSW50RzYkKiYtJiUickc2JCUiaUclImpHNiMlInhHIiIiKS0mJSJxRzYjRixGLkYtISIiRi8sJi1GJTYkKiYtJSJzR0YuRjApRjIsJkYtRjBGMEY2RjZGL0YwLUYlNiQqKC0lInRHRi5GMClGMiUiJ0dGMEYxRjZGL0Yw .Integration by parts yieldsNiMvLSUkSW50RzYkKigtJSJ0RzYjJSJ4RyIiIiktJiUicUc2IyUiaUdGKiUiJ0dGLClGLiUiakchIiJGKywmKiZGKEYsKiYsJkY1RixGLEY2RiwpRi5GOkYsRjZGNi1GJTYkKiYpRihGM0YsRjlGNkYrRiw= .Note the contribution to the rational part of the result.Hermite reductions can be continued until only square-free denominators remain.

p := x^6+5*x^5+10*x^4+50*x^3+25*x^2+127*x-1:q := x^4+10*x^2+25:The integral we wish to compute isInt(p/q, x);r := rem(p, q, x, 'P');P;int_P := int(P, x);Euclidean division with remainder has yielded:Int(p/q, x) = int_P + Int(r/q, x);q_sqrfree := convert(q, sqrfree, x);q2 := x^2 + 5;In this case, the square-free factorization of the denominator isNiMvJSJxRyomJkYkNiMiIiJGKCokJkYkNiMiIiNGLEYo with NiMvJiUicUc2IyIiIkYn and NiMvJiUicUc2IyIiIywmKiQlInhHRiciIiIiIiZGKw== .The problem has been reduced toInt(p/q, x) = int_P + Int(r/q2^2, x);Apply Hermite reduction to the remaining integral which is of the form NiMpJiUicUc2IyUiakdGJw== with NiMvJSJqRyIiIw== .The Extended Euclidean Algorithm is invoked as follows.gcdex(q2, diff(q2,x), r, x, 's', 't');s;t;j := 2:The Hermite reduction formula takes the formInt(r/q2^j, x) = -t/((j-1)*q2^(j-1)) + Int((s+diff(t,x)/(j-1))/q2^(j-1), x);and therefore the original integral has been reduced toInt(p/q, x) = int_P + rhs(%);

The problem is to express NiMtJSRJbnRHNiQqJi0lIkFHNiMlInhHIiIiLSUiQkdGKSEiIkYq where NiMyLSUkZGVnRzYjLSUiQUc2IyUieEctRiU2Iy0lIkJHRik= and NiMtJSJCRzYjJSJ4Rw== is square-free.Classical approach: Factor B(x) over its splitting field, and then a partial fraction expansion determines the NiMlJGxvZ0c= terms.But such a factorization may be much more expensive than necessary.Theorem 2 (Rothstein-Trager Theorem)NiMvLSUkSW50RzYkKiYtJSJBRzYjJSJ4RyIiIi0lIkJHRiohIiJGKy0lJFN1bUc2JComJiUiY0c2IyUiaUdGLC0lJGxvZ0c2Iy0mJSJ2R0Y2RipGLC9GNztGLCUibkc=where NiMmJSJjRzYjJSJpRw== are the distinct roots of NiMvLSUiUkc2IyUiekctJSpyZXN1bHRhbnRHNiUsJi0lIkFHNiMlInhHIiIiKiZGJ0YwKS0lIkJHRi4lIidHRjAhIiJGM0Yvand where NiMtJiUidkc2IyUiaUc2IyUieEc= are the polynomials NiMvLSYlInZHNiMlImlHNiMlInhHLSUkZ2NkRzYkLCYtJSJBR0YpIiIiKiYmJSJjR0YnRjEpLSUiQkdGKSUiJ0dGMSEiIkY2 .Moreover, this expresses the integral using the minimal algebraic extension field.Remark: The roots of NiMtJSJSRzYjJSJ6Rw== may introduce new algebraic numbers.

From Example 1.3 the remaining integral isA := -1/10: B := x^2 + 5:Int(A/B, x);R := resultant(A - z*diff(B,x), B, x);(c1,c2) := solve(R=0, z);v1 := gcd(A - c1*diff(B,x), B);v2 := gcd(A - c2*diff(B,x), B);Therefore the integral can be expressed as follows.Int(A/B, x) = c1*log(v1) + c2*log(v2);In this case, the result is identical to that obtained by the "classical approach" where the denominator is completely factored.

One of the integrals from Example 1.2 isA := 1: B := x^3+x:Int(A/B, x);R := resultant(A - z*diff(B,x), B, x);solve(R=0, z);The distinct roots are(c1,c2) := (1,-1/2);v1 := gcd(A - c1*diff(B,x), B);v2 := gcd(A - c2*diff(B,x), B);Therefore the integral can be expressed as follows.Int(A/B, x) = c1*log(v1) + c2*log(v2);In contrast, the "classical" approach would require a complete factorization of the denominatorfactored_B := factor(B,I);integrand := convert(A/factored_B, parfrac, x);from which we see that the integral isInt(A/B, x) = map(`int/risch`, integrand, x);The Rothstein-Trager method avoids introducing the algebraic number extension NiMvJSJJRy0lJXNxcnRHNiMsJCIiIiEiIg== in this example.Computational cost increases significantly with each new algebraic number extension, so it is important to use the minimal number of extensions required by the problem.

Step 1: Determine a description NiMtJSJLRzYmJSJ4RyYlJnRoZXRhRzYjIiIiJSYufi5+LkcmRig2IyUibkc= of a function field containing the integrand NiMlImZH .NiMlIktH is the constant field (we dynamically extend it to include any algebraic numbers which may arise).We must ensure that each NiMmJSZ0aGV0YUc2IyUiaUc= is a new transcendental extension. (This allows the manipulation of the integrand as a rational expression in the independent symbols NiYlInhHJiUmdGhldGFHNiMiIiIlJC4uLkcmRiU2IyUibkc= .)

For the integralInt(1/ln(x), x);the integrand lies in the function field NiMtJSJRRzYkJSJ4RyUmdGhldGFH where NiMvJSZ0aGV0YUctJSNsbkc2IyUieEc= is a logarithmic extension of the rational function field NiMtJSJRRzYjJSJ4Rw== .In this field the integrand is1/theta;

For the integralInt((x^3+2*x)*cos(x^2)+x*sin(x^2), x);by converting the integrand to complex NiMlJGV4cEc=-NiMlJGxvZ0c= form, the problem can be expressed in the formInt((x^3+2*x)*(exp(I*x^2)+exp(-I*x^2))/2 - 1/2*I*x*(exp(I*x^2)-exp(-I*x^2)), x);and we can view the integrand as an element of the function field NiMtLSUiUUc2IyUiSUc2JCUieEclJnRoZXRhRw== where NiMvJSZ0aGV0YUctJSRleHBHNiMqJiUiSUciIiIqJCUieEciIiNGKg== . (Note: NiMvJSJJRy0lJXNxcnRHNiMsJCIiIiEiIg== .)In this field the integrand is1/2*(x^3+2*x)*(theta + 1/theta) - 1/2*I*x*(theta - 1/theta);

For the integral presented in Example 1.1Int(x*(x+1)*( (x^2*exp(2*x^2) - ln(x+1)^2)^2 + 2*x*exp(3*x^2)*( x - (2*x^3+2*x^2+x+1)*ln(x+1) )) / ((x+1)*ln(x+1)^2 - (x^3+x^2)*exp(2*x^2) )^2, x);we can view the integrand as an element of the function field NiMtJSJRRzYlJSJ4RyYlJnRoZXRhRzYjIiIiJkYoNiMiIiM= where NiMvJiUmdGhldGFHNiMiIiItJSRleHBHNiMqJCUieEciIiM= and NiMvJiUmdGhldGFHNiMiIiMtJSNsbkc2IywmJSJ4RyIiIkYtRi0= .Note that the two exponential terms NiMtJSRleHBHNiMqJiIiIyIiIiokJSJ4R0YnRig= and NiMtJSRleHBHNiMqJiIiJCIiIiokJSJ4RyIiI0Yo cannot be considered as independent extensions because there is an algebraic relationship between them. Rather, we choose to represent these terms in the form NiMqJC0lJGV4cEc2IyokJSJ4RyIiI0Yp and NiMqJC0lJGV4cEc2IyokJSJ4RyIiIyIiJA== which involves a single transcendental extension NiMvJiUmdGhldGFHNiMiIiItJSRleHBHNiMqJCUieEciIiM= .

Step 2: Consider the integrand NiMlImZH as a rational expression in the field NiMtJiUiRkc2IywmJSJuRyIiIkYpISIiNiMlJnRoZXRhRw== : NiMvLSUiZkc2IyUmdGhldGFHKiYtJSJhR0YmIiIiLSUiYkdGJiEiIg==where NiMvJSZ0aGV0YUcmRiQ2IyUibkc= denotes the last extension and where NiMvJiUiRkc2IywmJSJuRyIiIkYpISIiLSUiS0c2JiUieEcmJSZ0aGV0YUc2I0YpJSYufi5+LkcmRjBGJg== . In other words, NiMtJSJhRzYjJSZ0aGV0YUc= and NiMtJSJiRzYjJSZ0aGV0YUc= are viewed as polynomials in the domain NiMmJSJGRzYjLCYlIm5HIiIiRighIiI=[NiMlJnRoZXRhRw==] . Normalize NiMtJSJmRzYjJSZ0aGV0YUc= such that NiMvLSUkZ2NkRzYkLSUiYUc2IyUmdGhldGFHLSUiYkdGKSIiIg== and NiMtJSJiRzYjJSZ0aGV0YUc= is monic.The algorithm proceeds in a manner similar to rational function integration; specifically, Hermite reductions followed by the application of a Rothstein-Trager Theorem. In particular, the algorithm will apply polynomial operations. We consider separately the cases where the last extension NiMlJnRoZXRhRw== is a logarithmic extension or an exponential extension.

Suppose that the last extension NiMlJnRoZXRhRw== is a logarithmic extension, i.e. NiMvKSUmdGhldGFHJSInRyomKSUidUdGJiIiIkYpISIi for some function NiMlInVH in NiMmJSJGRzYjLCYlIm5HIiIiRighIiI= . Applying Euclidean division with remainder yields NiMvLSUkSW50RzYkLSUiZkc2IyUmdGhldGFHJSJ4RywmLUYlNiQtJSJwR0YpRisiIiItRiU2JComLSUickdGKUYxLSUiYkdGKSEiIkYrRjE= .We now have two integrals to consider: (1) the integral of the polynomial part; and (2) the integral of the rational part. This time (unlike the case of rational function integration) the integral of the polynomial part is nontrivial; indeed, task (1) is the harder of the two parts. We first consider task (2).

This case mimics the Hermite method for rational functions. Applying square-free factorization of the denominator yields NiMvLSUiYkc2IyUmdGhldGFHLSUoUHJvZHVjdEc2JCktJkYlNiMlImlHRiZGLy9GLzsiIiIlImtH where this means "square-free as a polynomial in NiMlJnRoZXRhRw== ." For application in subsequent steps of the algorithm, we need to know that the following theorem holds.Theorem 3: If NiMtJSJ2RzYjJSZ0aGV0YUc= is a monic polynomial which is square-free as a polynomial in the symbol NiMlJnRoZXRhRw== and if NiMvJSZ0aGV0YUctJSRsb2dHNiMtJSJ1RzYjJSJ4Rw== for some function NiMtJSJ1RzYjJSJ4Rw== then NiMvLSUkZ2NkRzYkLSUidkc2IyUmdGhldGFHKUYnJSInRyIiIg==where the latter differentiation is with respect to NiMlInhH .Then applying partial fraction expansion, we getNiMvLSUkSW50RzYkKiYtJSJyRzYjJSZ0aGV0YUciIiItJSJiR0YqISIiJSJ4Ry0lJFN1bUc2JC1GMjYkLUYlNiQqJi0mRik2JCUiaUclImpHRipGLCktJkYuNiNGPEYqRj1GL0YwL0Y9O0YsRjwvRjw7RiwlImtH where NiMyLSUkZGVnRzYjLSYlInJHNiQlImlHJSJqRzYjJSZ0aGV0YUctRiU2Iy0mJSJiRzYjRitGLQ== .For each integral with a denominator containing a power NiMlImpH > NiMiIiI= , apply the Extended Euclidean Algorithm to solve NiMvLCYqJi0lInNHNiMlJnRoZXRhRyIiIi0mJSJiRzYjJSJpR0YoRipGKiomLSUidEdGKEYqKUYrJSInR0YqRiotJiUickc2JEYvJSJqR0Yo .As in rational function integration, apply integration by parts to obtain the Hermite reduction:NiMvLSUkSW50RzYkKiYtJiUickc2JCUiaUclImpHNiMlJnRoZXRhRyIiIiktJiUiYkc2I0YsRi5GLSEiIiUieEcsJiomLSUidEdGLkYwKiYsJkYtRjBGMEY2RjApRjJGPUYwRjZGNi1GJTYkKiYsJi0lInNHRi5GMComKUY6JSInR0YwRj1GNkYwRjBGPkY2RjdGMA== .Continuing such reductions until no remaining integral has a denominator containing a power NiMlImpH > NiMiIiI= , we reduce the integration problem to one in which the denominator is square-free.

The problem is to express NiMtJSRJbnRHNiQqJi0lIkFHNiMlJnRoZXRhRyIiIi0lIkJHRikhIiIlInhH where NiMyLSUkZGVnRzYjLSUiQUc2IyUmdGhldGFHLUYlNiMtJSJCR0Yp , NiMtJSJCRzYjJSZ0aGV0YUc= is square-free, and where NiMvJSZ0aGV0YUctJSRsb2dHNiMlInVH is a logarithmic extension.Theorem 4 (Rothstein-Trager Theorem: log extension)(i) NiMtJSRJbnRHNiQqJi0lIkFHNiMlJnRoZXRhRyIiIi0lIkJHRikhIiIlInhH is elementary if and only if all of the roots of NiMvLSUiUkc2IyUiekctJSpyZXN1bHRhbnRHNiUsJi0lIkFHNiMlJnRoZXRhRyIiIiomRidGMCktJSJCR0YuJSInR0YwISIiRjNGLw==are constants. In other words, the primitive part of NiMtJSJSRzYjJSJ6Rw== with respect to the variable NiMlInpH must have constant coefficients.(ii) If NiMtJSRJbnRHNiQqJi0lIkFHNiMlJnRoZXRhRyIiIi0lIkJHRikhIiIlInhH is elementary then NiMvLSUkSW50RzYkKiYtJSJBRzYjJSZ0aGV0YUciIiItJSJCR0YqISIiJSJ4Ry0lJFN1bUc2JComJiUiY0c2IyUiaUdGLC0lJGxvZ0c2Iy0mJSJ2R0Y3RipGLC9GODtGLCUibUc=where NiMmJSJjRzYjJSJpRw== are the distinct roots of NiMtJSJSRzYjJSJ6Rw== and where NiMtJiUidkc2IyUiaUc2IyUmdGhldGFH are defined by NiMvLSYlInZHNiMlImlHNiMlJnRoZXRhRy0lJGdjZEc2JCwmLSUiQUdGKSIiIiomJiUiY0dGJ0YxKS0lIkJHRiklIidHRjEhIiJGNg== .Moreover, this expresses the integral using the minimal algebraic extension field.

Consider the following integral.Int(1/ln(x), x);The integrand is NiMvLSUiZkc2IyUmdGhldGFHKiYiIiJGKUYnISIi in the function field NiMtJSJRRzYkJSJ4RyUmdGhldGFH where NiMvJSZ0aGV0YUctJSNsbkc2IyUieEc= .A resultant computation (Rothstein-Trager Theorem) is applicable.A := 1: B := theta:diff_B := diff(ln(x), x);R := resultant(A - z*diff_B, B, theta);The single root of NiMtJSJSRzYjJSJ6Rw== is NiMvJSJ6RyUieEc= which is not a constant.Therefore the original integral is not elementary.

The integralInt(1/(x*ln(x)), x);has integrand NiMvLSUiZkc2IyUmdGhldGFHKiYiIiJGKSomJSJ4R0YpRidGKSEiIg== in the function field NiMtJSJRRzYkJSJ4RyUmdGhldGFH where NiMvJSZ0aGV0YUctJSNsbkc2IyUieEc= .This time, the resultant computation is as follows.A := 1: B := x*theta:diff_B := subs(ln(x)=theta, diff(subs(theta=ln(x), B), x));R := resultant(A - z*diff_B, B, theta);The single root of NiMtJSJSRzYjJSJ6Rw== is NiMvJSJ6RyIiIg== and the integral is elementary. Specifically,c[1] := 1; v[1] := gcd(A - c[1]*diff_B, B);and the integral isc[1]*ln(v[1]);In other words,Int(1/(x*ln(x)), x) = subs(theta=ln(x), c[1]*ln(v[1]));

For the integration of the "polynomial part", the integrand is a polynomial in the log extension NiMlJnRoZXRhRw== : NiMvLSUicEc2IyUmdGhldGFHLCoqJiYlIkFHNiMlImtHIiIiKUYnRi1GLkYuKiYmRis2IywmRi1GLkYuISIiRi4pRidGM0YuRi4lKn5+Ln4ufi5+fkdGLiZGKzYjIiIhRi4=with NiMmJSJBRzYjJSJpRw== in NiMmJSJGRzYjLCYlIm5HIiIiRighIiI= and we can conclude thatNiMvLSUkSW50RzYkLSUicEc2IyUmdGhldGFHJSJ4RywsKiYmJSJCRzYjLCYlImtHIiIiRjNGM0YzKUYqRjFGM0YzKiYmRi82I0YyRjMpRipGMkYzRjMlKn5+Ln4ufi5+fkdGMyZGLzYjIiIhRjMtJSRTdW1HNiQqJiYlImNHNiMlImlHRjMtJSRsb2dHNiMmJSJ2R0ZDRjMvRkQ7RjMlIm1HRjM= .Note that the last term indicates that some new log extensions may arise.Differentiating and equating coefficients of powers of the transcendental symbol NiMlJnRoZXRhRw== , we get: NiMvIiIhKSYlIkJHNiMsJiUia0ciIiJGK0YrJSInRw== NiMvJiUiQUc2IyUia0csJiooLCZGJyIiIkYrRitGKyYlIkJHNiNGKkYrKSUmdGhldGFHJSInR0YrRispJkYtRiZGMUYr NiMvJiUiQUc2IywmJSJrRyIiIkYpISIiLCYqKEYoRikmJSJCRzYjRihGKSklJnRoZXRhRyUiJ0dGKUYpKSZGLkYmRjJGKQ== . . . . . . NiMvJiUiQUc2IyIiIiwmKigiIiNGJyYlIkJHNiNGKkYnKSUmdGhldGFHJSInR0YnRicpJkYsRiZGMEYn NiMvJiUiQUc2IyIiISwmKiYmJSJCRzYjIiIiRi0pJSZ0aGV0YUclIidHRi1GLSkpJkYrRiYlIipHRjBGLQ==where NiMvKSYlIkJHNiMiIiElIipHLCZGJSIiIi0lJFN1bUc2JComJiUiY0c2IyUiaUdGKy0lJGxvZ0c2IyYlInZHRjJGKy9GMztGKyUibUdGKw== .We can solve these equations successively, from the top down. At each step there is an integration operation which requires a recursive invocation of the Risch algorithm. This works because the integrand lies in the field NiMmJSJGRzYjLCYlIm5HIiIiRighIiI= involving one less extension. At any step, if the integral to be computed is not elementary then the algorithm halts with the conclusion that the original integral is not elementary. Moreover, at any step except the last step, if the result of the recursive integration introduces one or more new log extensions then the algorithm halts with the conclusion that the original integral is not elementary. At the last step, new log extensions may appear.

The integral NiMtJSRJbnRHNiQtJSNsbkc2IyUieEdGKQ==has integrand NiMvLSUiZkc2IyUmdGhldGFHRic= in the field NiMtJSJRRzYkJSJ4RyUmdGhldGFH where NiMvJSZ0aGV0YUctJSNsbkc2IyUieEc= . If the integral is elementary then NiMvLSUkSW50RzYkJSZ0aGV0YUclInhHLCgqJiYlIkJHNiMiIiMiIiIqJEYnRi5GL0YvKiYmRiw2I0YvRi9GJ0YvRi8pJkYsNiMiIiElIipHRi8=where the equations to be satisfied are NiMvIiIhKSYlIkJHNiMiIiMlIidH NiMvIiIiLCYqKCIiI0YkJiUiQkc2I0YnRiQpJSZ0aGV0YUclIidHRiRGJCkmRik2I0YkRi1GJA== NiMvIiIhLCYqJiYlIkJHNiMiIiJGKiklJnRoZXRhRyUiJ0dGKkYqKSkmRig2I0YkJSIqR0YtRio= .From the first equation we conclude that NiMvJiUiQkc2IyIiIyYlImJHRiY= , an arbitrary constant of integration. Plugging this into the second equation and integrating both sides yields NiMvLSUkSW50RzYkIiIiJSJ4RywmKigiIiNGJyYlImJHNiNGK0YnJSZ0aGV0YUdGJ0YnJiUiQkc2I0YnRic=or NiMvLCYlInhHIiIiJiUiYkc2I0YmRiYsJiooIiIjRiYmRig2I0YsRiYlJnRoZXRhR0YmRiYmJSJCR0YpRiY=where NiMmJSJiRzYjIiIi is an arbitrary constant of integration. Equating coefficients of NiMlJnRoZXRhRw== on both sides of the equation, we conclude that NiMvJiUiYkc2IyIiIyIiIQ== and NiMvJiUiQkc2IyIiIiwmJSJ4R0YnJiUiYkdGJkYn.The last equation now becomes NiMvIiIhLCYqJiwmJSJ4RyIiIiYlImJHNiNGKUYpRikpJSZ0aGV0YUclIidHRilGKSkpJiUiQkc2I0YkJSIqR0YvRik=or rearranging (we always leave the term NiMqKCUiaUciIiImJSJiRzYjRiRGJSklJnRoZXRhRyUiJ0dGJQ== on the right hand side since integration of this term is trivial): NiMvLCQqJiUieEciIiIpJSZ0aGV0YUclIidHRichIiIsJiomJiUiYkc2I0YnRidGKEYnRicpKSYlIkJHNiMiIiElIipHRipGJw== .At this point we use the fact that NiMvJSZ0aGV0YUctJSNsbkc2IyUieEc= (i.e. NiMvKSUmdGhldGFHJSInRyomIiIiRiglInhHISIi ) on the left hand side, and integrate both sides to get NiMvLSUkSW50RzYkLCQiIiIhIiIlInhHLCYqJiYlImJHNiNGKEYoJSZ0aGV0YUdGKEYoKSYlIkJHNiMiIiElIipHRig=from which we conclude (by equating coefficients of NiMlJnRoZXRhRw== on both sides of the equation) that NiMvJiUiYkc2IyIiIiIiIQ== and NiMvKSYlIkJHNiMiIiElIipHLCQlInhHISIi , ignoring the arbitrary constant of integration in this final step. Putting it all together we havetheta := ln(x):B[2] := 0: B[1] := x: B[0] := -x:Int(theta, x) = B[2]*theta^2 + B[1]*theta + B[0];

The integral NiMtJSRJbnRHNiQtJSNsbkc2Iy1GJzYjJSJ4R0Yrhas integrand NiMvLSUiZkc2IyYlJnRoZXRhRzYjIiIjRic= in the field NiMtJSJRRzYlJSJ4RyYlJnRoZXRhRzYjIiIiJkYoNiMiIiM= where NiMvJiUmdGhldGFHNiMiIiItJSNsbkc2IyUieEc= and NiMvJiUmdGhldGFHNiMiIiMtJSNsbkc2IyZGJTYjIiIi . If the integral is elementary then NiMvLSUkSW50RzYkJiUmdGhldGFHNiMiIiMlInhHLCgqJiYlIkJHRikiIiIqJEYnRipGMEYwKiYmRi82I0YwRjBGJ0YwRjApJkYvNiMiIiElIipHRjA=where the equations to be satisfied are NiMvIiIhKSYlIkJHNiMiIiMlIidH NiMvIiIiLCYqKCIiI0YkJiUiQkc2I0YnRiQpJiUmdGhldGFHRiolIidHRiRGJCkmRik2I0YkRi5GJA== NiMvIiIhLCYqJiYlIkJHNiMiIiJGKikmJSZ0aGV0YUc2IyIiIyUiJ0dGKkYqKSkmRig2I0YkJSIqR0YwRio= .From the first equation we conclude that NiMvJiUiQkc2IyIiIyYlImJHRiY= , an arbitrary constant of integration. Plugging this into the second equation and integrating both sides yields NiMvLSUkSW50RzYkIiIiJSJ4RywmKigiIiNGJyYlImJHNiNGK0YnJiUmdGhldGFHRi5GJ0YnJiUiQkc2I0YnRic=or NiMvLCYlInhHIiIiJiUiYkc2I0YmRiYsJiooIiIjRiYmRig2I0YsRiYmJSZ0aGV0YUdGLkYmRiYmJSJCR0YpRiY=where NiMmJSJiRzYjIiIi is an arbitrary constant of integration. Equating coefficients of NiMmJSZ0aGV0YUc2IyIiIw== on both sides of the equation, we conclude that NiMvJiUiYkc2IyIiIyIiIQ== and NiMvJiUiQkc2IyIiIiwmJSJ4R0YnJiUiYkdGJkYn . The last equation now becomes NiMvIiIhLCYqJiwmJSJ4RyIiIiYlImJHNiNGKUYpRikpJiUmdGhldGFHNiMiIiMlIidHRilGKSkpJiUiQkc2I0YkJSIqR0YyRik=or rearranging: NiMvLCQqJiUieEciIiIpJiUmdGhldGFHNiMiIiMlIidHRichIiIsJiomJiUiYkc2I0YnRidGKEYnRicpKSYlIkJHNiMiIiElIipHRi1GJw== .Since NiMvKSYlJnRoZXRhRzYjIiIjJSInRyomKSZGJjYjIiIiRilGLkYsISIi , i.e. NiMvKSYlJnRoZXRhRzYjIiIjJSInRyomIiIiRisqJiUieEdGKy0lI2xuRzYjRi1GKyEiIg== , substituting for NiMpJiUmdGhldGFHNiMiIiMlIidH on the left hand side and integrating yields NiMvLSUkSW50RzYkLCQqJiIiIkYpLSUjbG5HNiMlInhHISIiRi5GLSwmKiYmJSJiRzYjRilGKSYlJnRoZXRhRzYjIiIjRilGKSkmJSJCRzYjIiIhJSIqR0Yp .From Example 1.9 we know that the integral appearing here is not elementary. Hence we conclude that NiMtJSRJbnRHNiQtJSNsbkc2Iy1GJzYjJSJ4R0Yr is not elementary.

Suppose that the last extension NiMlJnRoZXRhRw== is an exponential extension, i.e. NiMvKiYpJSZ0aGV0YUclIidHIiIiRiYhIiIpJSJ1R0Yn for some function NiMlInVH in NiMmJSJGRzYjLCYlIm5HIiIiRighIiI= . Applying Euclidean division with remainder yields NiMvLSUkSW50RzYkLSUiZkc2IyUmdGhldGFHJSJ4RywmLUYlNiQtJSJwR0YpRisiIiItRiU2JComLSUickdGKUYxLSUiYkdGKSEiIkYrRjE= .Unlike the logarithmic case, we must remove any power of NiMlJnRoZXRhRw== from the denominator on the right hand side, and incorporate it into the new "polynomial part": NiMvLSUicEc2IyUmdGhldGFHLSUkU3VtRzYkKiYmRiU2IyUiakciIiIpRidGLkYvL0YuOywkJSJrRyEiIiUibEc= . (This can be done.)We now have two integrals to consider: (1) the integral of the polynomial part; and (2) the integral of the rational part. Again, task (1) is the harder of the two parts. We first consider task (2).

This case is very similar to the logarithmic case. Applying square-free factorization of the denominator yields NiMvLSUiYkc2IyUmdGhldGFHLSUoUHJvZHVjdEc2JCktJkYlNiMlImlHRiZGLy9GLzsiIiIlImtH where this means "square-free as a polynomial in NiMlJnRoZXRhRw== ." For application in subsequent steps of the algorithm, we need to know that the following theorem holds.Theorem 5: If NiMtJSJ2RzYjJSZ0aGV0YUc= is a monic polynomial which is square-free as a polynomial in the symbol NiMlJnRoZXRhRw== and if NiMvJSZ0aGV0YUctJSRleHBHNiMtJSJ1RzYjJSJ4Rw== for some function NiMtJSJ1RzYjJSJ4Rw== then NiMvLSUkZ2NkRzYkLSUidkc2IyUmdGhldGFHKUYnJSInRyIiIg==where the latter differentiation is with respect to NiMlInhH, provided that NiMlJnRoZXRhRw== does not divide NiMtJSJ2RzYjJSZ0aGV0YUc= .Then, exactly as in the logarithmic case, applying partial fraction expansion we getNiMvLSUkSW50RzYkKiYtJSJyRzYjJSZ0aGV0YUciIiItJSJiR0YqISIiJSJ4Ry0lJFN1bUc2JC1GMjYkLUYlNiQqJi0mRik2JCUiaUclImpHRipGLCktJkYuNiNGPEYqRj1GL0YwL0Y9O0YsRjwvRjw7RiwlImtH where NiMyLSUkZGVnRzYjLSYlInJHNiQlImlHJSJqRzYjJSZ0aGV0YUctRiU2Iy0mJSJiRzYjRitGLQ== .For each integral with a denominator containing a power NiMlImpH > NiMiIiI= , apply the Extended Euclidean Algorithm to solve NiMvLCYqJi0lInNHNiMlJnRoZXRhRyIiIi0mJSJiRzYjJSJpR0YoRipGKiomLSUidEdGKEYqKUYrJSInR0YqRiotJiUickc2JEYvJSJqR0Yo .As before, apply integration by parts to obtain the Hermite reduction:NiMvLSUkSW50RzYkKiYtJiUickc2JCUiaUclImpHNiMlJnRoZXRhRyIiIiktJiUiYkc2I0YsRi5GLSEiIiUieEcsJiomLSUidEdGLkYwKiYsJkYtRjBGMEY2RjApRjJGPUYwRjZGNi1GJTYkKiYsJi0lInNHRi5GMComKUY6JSInR0YwRj1GNkYwRjBGPkY2RjdGMA== .Continuing such reductions until no remaining integral has a denominator containing a power NiMlImpH > NiMiIiI= , we reduce the integration problem to one in which the denominator is square-free.

The problem is to express NiMtJSRJbnRHNiQqJi0lIkFHNiMlJnRoZXRhRyIiIi0lIkJHRikhIiIlInhH where NiMyLSUkZGVnRzYjLSUiQUc2IyUmdGhldGFHLUYlNiMtJSJCR0Yp , NiMtJSJCRzYjJSZ0aGV0YUc= is square-free, and where NiMvJSZ0aGV0YUctJSRleHBHNiMlInVH is an exponential extension.Theorem 6 (Rothstein-Trager Theorem: exp extension)(i) NiMtJSRJbnRHNiQqJi0lIkFHNiMlJnRoZXRhRyIiIi0lIkJHRikhIiIlInhH is elementary if and only if all of the roots of NiMvLSUiUkc2IyUiekctJSpyZXN1bHRhbnRHNiUsJi0lIkFHNiMlJnRoZXRhRyIiIiomRidGMCktJSJCR0YuJSInR0YwISIiRjNGLw==are constants. In other words, the primitive part of NiMtJSJSRzYjJSJ6Rw== with respect to the variable NiMlInpH must have constant coefficients.(ii) If NiMtJSRJbnRHNiQqJi0lIkFHNiMlJnRoZXRhRyIiIi0lIkJHRikhIiIlInhH is elementary then NiMvLSUkSW50RzYkKiYtJSJBRzYjJSZ0aGV0YUciIiItJSJCR0YqISIiJSJ4RywmJSJnR0YsLSUkU3VtRzYkKiYmJSJjRzYjJSJpR0YsLSUkbG9nRzYjLSYlInZHRjlGKkYsL0Y6O0YsJSJtR0Yswhere NiMmJSJjRzYjJSJpRw== are the distinct roots of NiMtJSJSRzYjJSJ6Rw== , NiMtJiUidkc2IyUiaUc2IyUmdGhldGFH are defined by NiMvLSYlInZHNiMlImlHNiMlJnRoZXRhRy0lJGdjZEc2JCwmLSUiQUdGKSIiIiomJiUiY0dGJ0YxKS0lIkJHRiklIidHRjEhIiJGNg==and where NiMvJSJnRywkKiYtJSRTdW1HNiQqJiYlImNHNiMlImlHIiIiLSUkZGVnRzYjLSYlInZHRi02IyUmdGhldGFHRi8vRi47Ri8lIm1HRi8lInVHRi8hIiI= .Moreover, this expresses the integral using the minimal algebraic extension field.

Consider the following integral.restart;f := (x*exp(2*x^2)+8*sqrt(2)*x*(exp(x^2)+1)+2*x)/ (exp(3*x^2)+exp(2*x^2)+2*exp(x^2)+2):Int(f,x);The integrand is NiMvLSUiZkc2IyUmdGhldGFHKiYsKComJSJ4RyIiIiokRiciIiNGLEYsKioiIilGLC0lJXNxcnRHNiNGLkYsRitGLCwmRidGLEYsRixGLEYsKiZGLkYsRitGLEYsRiwsKiokRiciIiRGLEYtRiwqJkYuRixGJ0YsRixGLkYsISIi in the function field NiMtLSUiUUc2Iy0lJXNxcnRHNiMiIiM2JCUieEclJnRoZXRhRw== where NiMvJSZ0aGV0YUctJSRleHBHNiMqJCUieEciIiM= .A resultant computation (Rothstein-Trager Theorem) is applicable.Keep in mind that NiMvJSZ0aGV0YUctJSRleHBHNiMlInVH where NiMvJSJ1RyokJSJ4RyIiIw== .u := x^2:A := x*theta^2 + 8*sqrt(2)*x*(theta+1) + 2*x:B := theta^3 + theta^2 + 2*theta + 2:diff_B := subs(exp(u)=theta, diff(subs(theta=exp(u), B), x));R := resultant(A - z*diff_B, B, theta);solve(R=0, z);The distinct roots of NiMtJSJSRzYjJSJ6Rw== are NiMvJSJ6RywkKiYiIiJGJyIiIyEiIkYp and NiMvJSJ6RywkLSUlc3FydEc2IyIiIyEiIg== and the integral is elementary. Specifically,c[1] := -1/2: c[2] := -sqrt(2):v[1] := gcd(A - c[1]*diff_B, B);v[2] := gcd(A - c[2]*diff_B, B);The function NiMlImdH appearing in Theorem 6 isg := add(-c[i]*degree(v[i],theta), i=1..2) * u;and the desired integral isresult := g + add(c[i]*ln(v[i]), i=1..2);In other words,Int(f,x) = subs(theta=exp(u), result);

For the integration of the "polynomial part", the integrand is of the form NiMvLSUicEc2IyUmdGhldGFHLSUkU3VtRzYkKiYmJSJBRzYjJSJqRyIiIilGJ0YvRjAvRi87LCQlImtHISIiJSJsRw== with NiMmJSJBRzYjJSJqRw== in NiMmJSJGRzYjLCYlIm5HIiIiRighIiI= , where NiMvJSZ0aGV0YUctJSRleHBHNiMlInVH is an exponential extension. We can conclude thatNiMvLSUkSW50RzYkLSUicEc2IyUmdGhldGFHJSJ4RywmLSUkU3VtRzYkKiYmJSJCRzYjJSJqRyIiIilGKkY0RjUvRjQ7LCQlImtHISIiJSJsR0Y1LUYuNiQqJiYlImNHNiMlImlHRjUtJSRsb2dHNiMmJSJ2R0ZCRjUvRkM7RjUlIm1HRjU= .Note that the latter summation indicates that some new log extensions may arise.Differentiating and equating coefficients of powers of the transcendental symbol NiMlJnRoZXRhRw== , we get: NiMvJiUiQUc2IyUiakcsJikmJSJCR0YmJSInRyIiIiooRidGLSklInVHRixGLUYqRi1GLQ== , for NiMwJSJqRyIiIQ== NiMvJiUiQUc2IyIiISkpJiUiQkdGJiUiKkclIidHwhere NiMvKSYlIkJHNiMiIiElIipHLCZGJSIiIi0lJFN1bUc2JComJiUiY0c2IyUiaUdGKy0lJGxvZ0c2IyYlInZHRjJGKy9GMztGKyUibUdGKw== .Solving the latter equation for NiMpJiUiQkc2IyIiISUiKkc= requires a recursive integration: NiMvKSYlIkJHNiMiIiElIipHLSUkSW50RzYkJiUiQUdGJyUieEc= where the integrand lies in the field NiMmJSJGRzYjLCYlIm5HIiIiRighIiI= . For the general case, NiMwJSJqRyIiIQ== , the equation to be solved for NiMmJSJCRzYjJSJqRw== is known as a Risch differential equation. This may sound like a backwards step to have reduced an integration problem to the solution of a differential equation! However, the problem can be solved because we must look for a solution in the field NiMmJSJGRzYjLCYlIm5HIiIiRighIiI= only. Nonetheless, this is a difficult problem, in general, for which a complete solution was presented in [Bronstein90a]. See also [Bronstein97].

The integralInt(exp(-x^2), x);has integrand NiMvLSUiZkc2IyUmdGhldGFHRic= in the function field NiMtJSJRRzYkJSJ4RyUmdGhldGFH where NiMvJSZ0aGV0YUctJSRleHBHNiMsJCokJSJ4RyIiIyEiIg== .The solution must take the form NiMvLSUkSW50RzYkJSZ0aGV0YUclInhHKiYmJSJCRzYjIiIiRi1GJ0Yt where NiMmJSJCRzYjIiIi in NiMtJSJRRzYjJSJ4Rw== is a solution of the Risch differential equation NiMvLCYpJiUiQkc2IyIiIiUiJ0dGKSooIiIjRiklInhHRilGJkYpISIiRik= .Since NiMmJSJCRzYjIiIi must be a rational function in NiMlInhH , one first argues that it must be a polynomial in NiMlInhH . This follows because if NiMmJSJCRzYjIiIi had a nontrivial denominator then NiMpJiUiQkc2IyIiIiUiJ0c= would have a higher-degree denominator and these denominators could not cancel out to correspond to the right hand side of the differential equation which is the constant 1 . So assume that NiMmJSJCRzYjIiIi is a nonzero polynomial in NiMlInhH with NiMvLSUkZGVnRzYjJiUiQkc2IyIiIiUibkc= where NiMxIiIhJSJuRw== . But then taking the degree of each side of the differential equation, we get NiMvLCYlIm5HIiIiRiZGJiIiIQ== which is a contradiction. Hence the given Risch differential equation has no solution in the field NiMtJSJRRzYjJSJ4Rw== from which we conclude that the original integral is not elementary.

In the algorithm presented above we considered only transcendental elementary functions. The Risch algorithm for elementary functions also deals with algebraic extensions. For example, if the integral to be computed is NiMtJSRJbnRHNiQqKCUieEciIiItJSRleHBHNiMtJSVzcXJ0RzYjLCYqJEYnIiIjRihGMUYoRihGLCEiIkYn then the integrand lies in the elementary function field NiMtJSJRRzYlJSJ4RyYlJnRoZXRhRzYjIiIiJkYoNiMiIiM= where NiMvJiUmdGhldGFHNiMiIiItJSVzcXJ0RzYjLCYqJCUieEciIiNGJ0YuRic= is an algebraic extension of NiMtJSJRRzYjJSJ4Rw== and NiMvJiUmdGhldGFHNiMiIiMtJSRleHBHNiMmRiU2IyIiIg== is a transcendental extension of NiMtJSJRRzYkJSJ4RyYlJnRoZXRhRzYjIiIi . The Risch algorithm proceeds generally in the same manner as discussed above except that there are some different technical details (some of them involving concepts from advanced algebra) for algebraic extensions in the most general case. Some references which discuss the integration of elementary functions for the case of algebraic extensions, and mixed transcendental and algebraic extensions, are [Trager84] and [Bronstein90b].

The power of the Risch algorithm to determine conclusively whether or not a given elementary function has an elementary antiderivative is impressive, in principle. However in most practical problems where the operation of integration arises, it is quite unsatisfactory to receive as a result: "the integral cannot be expressed in elementary terms". For example, the Risch algorithm proves that NiMtJSRJbnRHNiQtJSRleHBHNiMsJCokJSJ4RyIiIyEiIkYr cannot be expressed as an elementary function (see Example 1.14) but in a larger function field the integral can be expressed:Int(exp(-x^2), x) = int(exp(-x^2), x);where a special function, the error function, arises. Another case is the following integral which in Example 1.12 was proved to be non-elementary:Int(ln(ln(x)), x) = int(ln(ln(x)), x);where another special function, the exponential integral, arises.It would be ideal if we could extend the elementary function field by an arbitrary number of special functions, as new transcendental extensions, and have a corresponding extended Risch algorithm as a decision procedure for the extended field. At the present time, decision procedures have not been developed for integration in function fields containing many of the commonly-used special functions. However, decision procedures have been developed for some special functions. Early work in this regard is reported in [Cherry85], [Cherry86] where decision procedures are developed for the error function and the logarithmic integral. Additional examples of integrals which can be computed in this context are the following two integrals.NiMvLSUkSW50RzYkKigsJiomIiIkIiIiKiQlInhHIiInRitGK0YrRitGKy0lJGV4cEc2IywkKiQtJSNsbkc2I0YtIiIjISIiRisqJEYtIiImRjhGLSwmKiotRjA2IyIiJUYrLSUlc3FydEc2IyUjUGlHRistJSRlcmZHNiMsJkY0RitGN0YrRitGN0Y4RisqLEYqRistRjA2I0YrRitGQEYrLUZFNiMsJkY0RitGK0Y4RitGN0Y4Ris=NiMvLSUkSW50RzYkKiYlInhHIiIkLSUjbG5HNiMsJiokRigiIiMiIiJGMCEiIkYxRigsJiomLSUjRWlHNiRGMCwkRipGMUYwRi9GMUYxKiYtRjU2JEYwLCQqJkYvRjBGKkYwRjFGMEYvRjFGMQ==See [Bronstein97] for a presentation of the state-of-the-art of integration algorithms for transcendental functions.

We turn now to the problem of computing a definite integral in closed form. The first concept is that if we are able to express the indefinite integral (antiderivative) then the Fundamental Theorem of Calculus can be applied (under appropriate conditions) to compute the value of the definite integral. In it simplest form, if NiMtJSJmRzYjJSJ4Rw== has antiderivative NiMtJSJGRzYjJSJ4Rw== then NiMvLSUkSW50RzYkLSUiZkc2IyUieEcvRio7JSJhRyUiYkcsJi0lIkZHNiNGLiIiIi1GMTYjRi0hIiI= .The first problem we encounter with this formula for the value of the definite integral is that it may not be possible to evaluate directly NiMtJSJGRzYjJSJhRw== or NiMtJSJGRzYjJSJiRw==, but rather it is the limit (an appropriate one-sided limit) which must be computed at each endpoint. Specifically, the formula becomes (suppose that NiMyJSJhRyUiYkc= ) :NiMvLSUkSW50RzYkLSUiZkc2IyUieEcvRio7JSJhRyUiYkcsJi0lJmxpbWl0RzYlLSUiRkdGKS9GKkYuJSVsZWZ0RyIiIi1GMTYlRjMvRipGLSUmcmlnaHRHISIi .

restart;f := ln(x):We wish to compute the definite integralInt(f, x=0..2);We can compute the antiderivativeF := int(f, x);but direct evaluation of the antiderivative at NiMvJSJ4RyIiIQ== encounters a logarithmic singularity. However, by taking limits we can compute the result as follows.limit(F, x=2, left) - limit(F, x=0, right);Of course, the integration procedure in Maple will do this computation automatically.int(f, x=0..2);

We see that the computation of definite integrals requires the ability to compute limits. In general, computing limits is a nontrivial task. Fortunately, very powerful algorithms are now known for computing limits based on the expansion of functions in generalized series. Once we have expressed a function in a generalized series expansion then the limit can be determined from the leading term of the expansion.

g := sin(x)/x;series(g, x=0);From the series expansion it is clear what is the limit at NiMvJSJ4RyIiIQ== .Limit(g, x=0) = limit(g, x=0);Another example:g := x^x;series(g, x=0, 3);Limit(g, x=0) = limit(g, x=0);And another example:g := ln(1-cos(x^2))/(ln(x)*arctan(sqrt(1-x^2)));series(g, x=0, 4);Limit(g, x=0) = limit(g, x=0);

The computation of generalized series expansions, and the computation of limits, requires very sophisticated techniques in the most general case. Some work on this problem was reported in [GeddesGonnet89]. More recent work which develops the theoretical foundation and presents practical algorithms can be found in [Salvy91], [Salvy92], [Richardson96].A difficult problem which arises in the computation of definite integrals is that the Fundamental Theorem of Calculus can be applied in the manner discussed above only if the integrand NiMtJSJmRzYjJSJ4Rw== and its antiderivative NiMtJSJGRzYjJSJ4Rw== are continuous on the interval NiMtJSFHNiQlImFHJSJiRw== . Since the form of antiderivative computed by the Risch integration algorithm can contain logarithmic functions, without special care the condition of continuity may be violated as discussed in [Bronstein97]. See also [Jeffrey93], [Jeffrey97] on the problem of computing continuous antiderivatives.

The following example is discussed in [Bronstein97]. Suppose that the integral to be computed isf := (x^4-3*x^2+6)/(x^6-5*x^4+5*x^2+4):Int(f, x=1..2);It can be verified that the integrand is continuous and positive on the real line, and hence the value of the definite integral must be a positive real number. Applying the integration algorithm in the form discussed in this presentation, the indefinite integral gets expressed in the following form.F := I/2*ln(x^3+I*x^2-3*x-2*I) - I/2*ln(x^3-I*x^2-3*x+2*I);That is,Int(f, x) = F;It can easily be verified that the derivative of NiMlIkZH is the integrand NiMlImZH and therefore this is a correct formal antiderivative. However, the differential algebra point of view used in developing the integration algorithm takes no account of the analytic concept of branch cuts of logarithmic functions. In this particular example, if we blindly apply the Fundamental Theorem of Calculus we get the following incorrect result for the definite integral.Int(f, x=1..2) = limit(F, x=2, left) - limit(F, x=1, right);evalf(rhs(%));This has yielded a value for the integral which is real, but negative, whereas we know that the correct answer must be positive. The presentation in [Bronstein97] shows how to ensure that the integration algorithm computes a continuous antiderivative for this type of problem. In this case, a continuous antiderivative isF_continuous := arctan((x^5 - 3*x^3 + x)/2) + arctan(x^3) + arctan(x);By differentiating, we see that this is a correct antiderivative of the original integrand NiMlImZH .simplify( diff(F_continuous, x) );This time, direct application of the Fundamental Theorem of Calculus is valid and we obtain the following result for the definite integral.Int(f, x=1..2) = limit(F_continuous, x=2, left) - limit(F_continuous, x=1, right);evalf(rhs(%));

A general technique which can be applied when the antiderivative is not guaranteed to be continuous is to find the points of discontinuity of the antiderivative and then to express the integral separately on each subinterval where it is continuous. By computing the appropriate one-sided limits on each subinterval, the correct definite integral is obtained.

In Example 2.3 we had the following discontinuous antiderivative.Int(f, x) = F;In Maple, the following command will determine the points of discontinuity over the whole real line.discont(F, x);allvalues(%);The above notation is expressing the fact that there are two points of discontinuity which are the two roots of a quadratic polynomial. Since we are interested in the definite integral over the interval NiMtJSFHNiQiIiIiIiM= there is just one relevant point of discontinuity:c := sqrt(2);and the endpoints of integration area := 1; b := 2;The correct value of the definite integral on NiMtJSFHNiQlImFHJSJiRw== can therefore be computed by using the fact thatNiMvLSUkSW50RzYkLSUiZkc2IyUieEcvRio7JSJhRyUiYkcsJi1GJTYkRicvRio7Ri0lImNHIiIiLUYlNiRGJy9GKjtGNEYuRjU=and noting that the antiderivative NiMlIkZH is continuous on each of the two subintervals.This leads to the following limit computations for the definite integral.Int(f, x=a..b) = limit(F, x=c, left) - limit(F, x=a, right) + limit(F, x=b, left) - limit(F, x=c, right);evalf(rhs(%));

Many non-elementary functions appear in the literature of the mathematical sciences, with names such as Bessel functions, Legendre functions, exponential integrals, elliptic integrals, et cetera. The list of such special functions is quite long. For classes of functions where we have no Risch-like algorithm to compute the indefinite integral, how can we compute integrals that involve such functions which arise in practical problems (assuming that we wish to obtain a closed-form symbolic result if possible)?Various special formulas can be programmed into a computer algebra system for integrals which appear in the literature. A particular approach discussed in [Geddes90] derives classes of integral formulas by applying differentiation to the integral definition of various special functions. A more general technique which is capable of obtaining results for a large number of integrals, most often definite integrals on the interval NiMtJSFHNiQiIiElKWluZmluaXR5Rw== , is to convert the integrand into one of the higher functions: the generalized hypergeometric function or the Meijer G function. We do not have space here to go into details about these functions or about this approach to computing integrals, but we show some examples to illustrate the concept.The generalized hypergeometric function and the Meijer G function are discussed in [PBM90]. The same series of books presents a large number of integral formulas involving special functions which computer algebra systems should know how to compute. At the present time, computer algebra systems cannot compute many of the integrals found in these books.The general approach being illustrated here to compute a special class of integrals is as follows.Convert the integrand to a representation in terms of Meijer G functions.Apply a formula to express the integral in terms of higher functions.Convert the result from a representation in terms of higher functions to a representation in terms of more standard functions (if possible).Note that for definite integrals on NiMtJSFHNiQiIiElKWluZmluaXR5Rw== where the integrand involves a product of Meijer G functions, various formulas are available to express the integral. For the problem of converting from a representation in terms of higher functions to a representation in terms of more standard functions (elementary functions and special functions), see [Roach96], [Roach97].

restart;f1 := x^(s-1)*exp(-p*x^4)*erfi(c*x)*erf(c*x):Int(f1, x=0..infinity);result1 := value(%);The method used was first to convert the integrand into NiMlKE1laWplckdH form.f1new := convert(f1, MeijerG, x);Now when we apply the NiMlJGludEc= command, it uses a known formula to express such a definite integral involving the product of two NiMlKE1laWplckdH functions.int(f1new, x=0..infinity);which is equal to NiMlKHJlc3VsdDFH .Of course, for particular values of the parameters we may compute a numerical value.eval(result1, {s=4, p=1, c=1});evalf(%);

f2 := x^v/(x^2+z^2)*BesselK(v,b*x):Int(f2, x=0..infinity);value(%);Note that the result of converting the integrand into NiMlKE1laWplckdH form is as follows.convert(f2, MeijerG, x);

Research work is continuing with the goal of bringing the knowledge about integral formulas known in the mathematical literature, into computer algebra systems. We anticipate that a large class of integrals appearing in the book [PBM90], for example, can be computed by the approach discussed above; namely, conversion of the integrand to a Meijer G function representation followed by application of general formulas for the integration of products of Meijer G functions.

[Bronstein90a] M. Bronstein, The transcendental Risch differential equation. Journal of Symbolic Computation 9, 1990, pp. 49-60.[Bronstein90b] M. Bronstein, On the integration of elementary functions. Journal of Symbolic Computation 9, 1990, pp. 117-173.[Bronstein97] M. Bronstein, Symbolic Integration I: Transcendental Functions. Springer-Verlag, Berlin, 1997.[Cherry85] G. Cherry, Integration in Finite Terms with Special Functions: the Error Function. Journal of Symbolic Computation 1, 1985, pp. 283-302.[Cherry86] G. Cherry, Integration in Finite Terms with Special Functions: the Logarithmic Integral. SIAM Journal on Computing 15, 1986, pp. 1-21.[Geddes90] K.O. Geddes, M.L. Glasser, R.A. Moore and T.C. Scott, Evaluation of classes of definite integrals involving elementary functions via differentiation of special functions. Applicable Algebra in Engineering, Communication and Computing 1 (2), 1990, pp. 149-165.[Geddes92] K.O. Geddes, S.R. Czapor and G. Labahn, Algorithms for Computer Algebra. Kluwer Academic Publishers, Boston, 1992.[GeddesGonnet89] K.O. Geddes and G.H. Gonnet, A new algorithm for computing symbolic limits using hierarchical series. Appears in Symbolic and Algebraic Computation, P. Gianni (ed.), Lecture Notes in Computer Science, No. 358, Springer-Verlag, Berlin, 1989, pp. 490-495.[Jeffrey93] D.J. Jeffrey, Integration to obtain expressions valid on domains of maximum extent. Proceedings of ISSAC'93, M. Bronstein (ed.), ACM Press, New York, 1993, pp. 34-41.[Jeffrey97] D.J. Jeffrey, Rectifying transformations for the integration of rational trigonometric functions. Journal of Symbolic Computation 24, 1997, pp. 563-573.[PBM90] A.P. Prudnikov, Y. Brychkov and O. Marichev, Integrals and Series, Volume 3: More Special Functions. Gordon and Breach Science Publishers, 1990.[Richardson96] D. Richardson, B. Salvy, J. Shackell and J. Van derHoeven, Asymptotic expansions of exp-log functions. Proceedings of ISSAC'96, Y.N. Lakshman (ed.), ACM Press, New York, 1996, pp. 309-313.[Roach96] K.B. Roach, Hypergeometric Function Representations. Proceedings of ISSAC '96, Y.N. Lakshman (ed.), ACM Press, New York, 1996, pp 301-308.[Roach97] K.B. Roach, Meijer G Function Representations. Proceedings of ISSAC '97, W.W. Kuechlin (ed.), ACM Press, New York, 1997, pp. 205-211. [Salvy91] B. Salvy, Examples of automatic asymptotic expansions. SIGSAM Bulletin 25 (2), 1991, pp. 4-17.[Salvy92] B. Salvy, General asymptotic scales and computer algebra. Appears in Asymptotic and Numerical Methods for Partial Differential Equations, Critical Parameters and Domain Decomposition, H. Kaper and M. Garbey (ed.), Kluwer Academic Publishers, 1992, pp. 255-266.[Trager84] B.M. Trager, On the integration of algebraic functions. Ph.D. Thesis, Computer Science, MIT, 1984.