Algorithms for Indefinite and Definite Integration in Maple K.O. Geddes Symbolic Computation Group D.R. Cheriton School of Computer Science University of Waterloo Waterloo ON N2L 3G1 CANADA http://www.uwaterloo.ca/~kogeddes

For CS 487/687, the relevant section is Risch Algorithm for Elementary Functions.

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 Problem Given a function NiMtJSJmRzYjJSJ4Rw==, determine whether there exists a function NiMtJSJnRzYjJSJ4Rw== such that NiMvLSUlZGlmZkc2JC0lImdHNiMlInhHRiotJSJmR0Yp i.e. determine an indefinite integral, or antiderivative, of NiMtJSJmRzYjJSJ4Rw== . We will write NiMvLSUkaW50RzYkLSUiZkc2IyUieEdGKi0lImdHRik= 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.

restart; 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);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqKkkieEdGJyIiIiwmRipGK0YrRitGKywmKiQpLCYqJilGKiIiI0YrLUkkZXhwR0YkNiMsJComRjNGK0YyRitGK0YrRisqJCktSSNsbkdGJDYjRixGM0YrISIiRjNGK0YrKipGM0YrRipGKy1GNTYjLCQqJiIiJEYrRjJGK0YrRissJkYqRisqJiwqKiZGM0YrKUYqRkRGK0YrRjhGK0YqRitGK0YrRitGO0YrRj5GK0YrRispLCYqJkYsRitGOkYrRisqJiwmKiRGSUYrRisqJEYyRitGK0YrRjRGK0Y+RjNGPkYq

value(%);

LCxJInhHNiIiIiItSSNsbkc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJDYjLCZGI0YlRiVGJSEiIioqLUkkZXhwR0YoNiMqJClGIyIiI0YlRiVGI0YlRiZGJSwmKiZGM0YlLUYwNiMsJComRjRGJUYzRiVGJUYlRiUqJClGJkY0RiVGLUYtRiUqJiNGJUY0RiUtRic2IywmKiZGI0YlRi9GJUYtRiZGJUYlRi0qJkY+RiUtRic2IywmRkJGJUYmRiVGJUYl

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 NiMtJSRpbnRHNiQtJSRleHBHNiMsJCokKSUieEciIiMiIiIhIiJGLA== 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);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLUkkZXhwR0YlNiMsJCokKUkieEdGKCIiIyIiIiEiIkYwLCQqKCNGMkYxRjIpSSNQaUdGJkY2RjItSSRlcmZHRiU2I0YwRjJGMg==

Definition of Elementary Functions Let 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);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQsJiIiIkYsKiQpSSJ4R0YoIiIjRixGLCEiIkYvLUknYXJjdGFuR0YlNiNGLw==

Int(cos(x), x) = int(cos(x), x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLUkkY29zR0YlNiNJInhHRihGLS1JJHNpbkdGJUYs

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

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQpLCYiIiJGLSokKUkieEdGKCIiI0YtISIiI0YtRjFGMkYwLUknYXJjc2luR0YlNiNGMA==

Int(arccosh(x), x) = int(arccosh(x), x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLUkoYXJjY29zaEdGJTYjSSJ4R0YoRi0sJiomRi0iIiJGKkYwRjAqJiksJkYtRjBGMCEiIiNGMCIiI0YwKSwmRi1GMEYwRjBGNUYwRjQ=

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');

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQsJiIiIkYsKiQpSSJ4R0YoIiIjRixGLCEiIkYvKiYqJiNGLEYwRixeI0YsRixGLCwmLUkjbG5HRiU2IywmRixGLComLCRGNUYsRixGL0YsRjFGLC1GODYjLCZGLEYsKiZGNUYsRi9GLEYsRjFGLA==

Int(1/2*exp(I*x) + 1/2*exp(-I*x), x) = int(1/2*exp(I*x) + 1/2*exp(-I*x), x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLCYqJiMiIiIiIiNGLS1JJGV4cEdGJTYjKiZeI0YtRi1JInhHRihGLUYtRi0qJkYsRi0tRjA2IywkKiYsJEYzRi1GLUY0Ri0hIiJGLUYtRjQsJiomLCQqJkYsRi1GM0YtRi1GLUYvRi1GOyomRj9GLUY2Ri1GLQ==

Int(1/sqrt(1-x^2), x) = convert(int(1/sqrt(1-x^2), x), 'expln');

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQpLCYiIiJGLSokKUkieEdGKCIiI0YtISIiI0YtRjFGMkYwLCQqJiwkXiNGLUYtRi0tSSNsbkdGJTYjLCYqJEYrRi1GLSomRjdGLUYwRi1GLUYtRjI=

Int(convert(arccosh(x),'expln'), x) = int(convert(arccosh(x),'expln'), x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLUkjbG5HRiU2IywmSSJ4R0YoIiIiKiYpLCZGLkYvRi8hIiIjRi8iIiNGLyksJkYuRi9GL0YvRjRGL0YvRi4sJiomRipGL0YuRi9GL0YwRjM=

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 1 Given NiMtJSJmRzYjJSJ4Rw== in an elementary function field NiMlIkZH , NiMtJSRJbnRHNiQtJSJmRzYjJSJ4R0Yp , if it exists as an elementary function, can be expressed in the form NiMvLSUkSW50RzYkLSUiZkc2IyUieEdGKiwmLSYlInZHNiMiIiFGKSIiIi0lJFN1bUc2JComJiUiY0c2IyUiaUdGMS0lJGxvZ0c2Iy0mRi5GOEYpRjEvRjk7RjElIm1HRjE= 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.

restart; Int(1/(x^2+2*x+1), x) = int(1/(x^2+2*x+1), x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQsKCokKUkieEdGKCIiIyIiIkYwKiZGL0YwRi5GMEYwRjBGMCEiIkYuLCQqJCwmRi5GMEYwRjBGMkYy

Remark: No NiMlJGxvZ0c= terms required in the above example. Int(1/(x^3+x), x) = int(1/(x^3+x), x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQsJiokKUkieEdGKCIiJCIiIkYwRi5GMCEiIkYuLCYtSSNsbkdGJTYjRi5GMComI0YwIiIjRjAtRjQ2IywmKiQpRi5GOEYwRjBGMEYwRjBGMQ==

Remark: No algebraic number extensions required in the above example. Int(1/(x^2-2), x) = `int/risch`(1/(x^2-2), x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQsJiokKUkieEdGKCIiIyIiIkYwRi8hIiJGMUYuLCYqKCNGMCIiJUYwKUYvI0YwRi9GMC1JI2xuR0YlNiMsJkYuRjAqJEY2RjBGMUYwRjAqKEY0RjBGNkYwLUY5NiMsJkYuRjBGPEYwRjBGMQ==

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 NiMvLCYqJCklInhHIiIkIiIiRilGJ0YpKihGJ0YpLCZGJ0YpJSJJR0YpRiksJkYnRilGLCEiIkYp would lead to the following representation of the integral: NiMvLSUkSW50RzYkKiYiIiJGKCwmKiQpJSJ4RyIiJEYoRihGLEYoISIiRiwsKC0lI2xuRzYjRixGKComLUYxNiMsJkYsRiglIklHRihGKCIiI0YuRi4qJi1GMTYjLCZGLEYoRjdGLkYoRjhGLkYu . Goal: Avoid introducing algebraic numbers except when necessary.

We want to reduce the problem as follows: NiMvLSUkSW50RzYkKiYtJSJwRzYjJSJ4RyIiIi0lInFHRiohIiJGKywmKiYtJSJDR0YqRiwtJSJER0YqRi9GLC1GJTYkKiYtJSJBR0YqRiwtJSJCR0YqRi9GK0Ys where 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 yields NiMvLSUkSW50RzYkKiYtJSJwRzYjJSJ4RyIiIi0lInFHRiohIiJGKywmLUYlNiQtJSJQR0YqRitGLC1GJTYkKiYtJSJyR0YqRixGLUYvRitGLA== where NiMvLSUickc2IyUieEciIiE= or NiMyLSUkZGVnRzYjLSUickc2IyUieEctRiU2Iy0lInFHRik= . Step 2: Square-free factorization yields NiMvLSUicUc2IyUieEctJShQcm9kdWN0RzYkKS0mRiU2IyUiaUdGJkYvL0YvOyIiIiUia0c= where NiMvLSUkZ2NkRzYkLSYlInFHNiMlImlHNiMlInhHKUYnJSInRyIiIg== for all NiMlImlH , and where NiMvLSUkZ2NkRzYkLSYlInFHNiMlImlHNiMlInhHLSZGKTYjJSJqR0YsIiIi for NiMwJSJpRyUiakc= . Step 3: Partial fraction expansion yields NiMvKiYtJSJyRzYjJSJ4RyIiIi0lInFHRichIiItJSRTdW1HNiQtRi42JComLSZGJjYkJSJpRyUiakdGJ0YpKS0mRis2I0Y2RidGN0YsL0Y3O0YpRjYvRjY7RiklImtH where NiMyLSUkZGVnRzYjLSYlInJHNiQlImlHJSJqRzYjJSJ4Ry1GJTYjLSYlInFHNiNGK0Yt . We now have NiMvLSUkSW50RzYkKiYtJSJyRzYjJSJ4RyIiIi0lInFHRiohIiJGKy0lJFN1bUc2JC1GMTYkLUYlNiQqJi0mRik2JCUiaUclImpHRipGLCktJkYuNiNGO0YqRjxGL0YrL0Y8O0YsRjsvRjs7RiwlImtH . 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 yields NiMvLSUkSW50RzYkKigtJSJ0RzYjJSJ4RyIiIiktJiUicUc2IyUiaUdGKiUiJ0dGLClGLiUiakchIiJGKywmKiZGKEYsKiYsJkY1RixGLEY2RiwpRi5GOkYsRjZGNi1GJTYkKiYpRihGM0YsRjlGNkYrRiw= . 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 is Int(p/q, x);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqJiwwKiQpSSJ4R0YnIiInIiIiRi8qJiIiJkYvKUYtRjFGL0YvKiYiIzVGLylGLSIiJUYvRi8qJiIjXUYvKUYtIiIkRi9GLyomIiNERi8pRi0iIiNGL0YvKiYiJEYiRi9GLUYvRi9GLyEiIkYvLCgqJEY1Ri9GLyomRjRGL0Y9Ri9GL0Y8Ri9GQUYt

r := rem(p, q, x, 'P');

LCYiIiIhIiIqJiIiI0YjSSJ4RzYiRiNGIw==

P;

LCYqJClJInhHNiIiIiMiIiJGKComIiImRihGJUYoRig=

int_P := int(P, x);

LCYqJiMiIiIiIiRGJSlJInhHNiJGJkYlRiUqJiMiIiYiIiNGJSlGKEYtRiVGJQ==

Euclidean division with remainder has yielded: Int(p/q, x) = int_P + Int(r/q, x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsMCokKUkieEdGKCIiJyIiIkYwKiYiIiZGMClGLkYyRjBGMComIiM1RjApRi4iIiVGMEYwKiYiI11GMClGLiIiJEYwRjAqJiIjREYwKUYuIiIjRjBGMComIiRGIkYwRi5GMEYwRjAhIiJGMCwoKiRGNkYwRjAqJkY1RjBGPkYwRjBGPUYwRkJGLiwoKiYjRjBGO0YwRjpGMEYwKiYjRjJGP0YwRj5GMEYwLUYkNiQqJiwmRjBGQiomRj9GMEYuRjBGMEYwRkNGQkYuRjA=

q_sqrfree := convert(q, sqrfree, x);

KiQpLCYqJClJInhHNiIiIiMiIiJGKiIiJkYqRilGKg==

q2 := x^2 + 5;

LCYqJClJInhHNiIiIiMiIiJGKCIiJkYo

In this case, the square-free factorization of the denominator is NiMvJSJxRyomJkYkNiMiIiJGKCokKSZGJDYjIiIjRi1GKEYo with NiMvJiUicUc2IyIiIkYn and NiMvJiUicUc2IyIiIywmKiQpJSJ4R0YnIiIiRiwiIiZGLA== . The problem has been reduced to Int(p/q, x) = int_P + Int(r/q2^2, x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsMCokKUkieEdGKCIiJyIiIkYwKiYiIiZGMClGLkYyRjBGMComIiM1RjApRi4iIiVGMEYwKiYiI11GMClGLiIiJEYwRjAqJiIjREYwKUYuIiIjRjBGMComIiRGIkYwRi5GMEYwRjAhIiJGMCwoKiRGNkYwRjAqJkY1RjBGPkYwRjBGPUYwRkJGLiwoKiYjRjBGO0YwRjpGMEYwKiYjRjJGP0YwRj5GMEYwLUYkNiQqJiwmRjBGQiomRj9GMEYuRjBGMEYwKSwmKiRGPkYwRjBGMkYwRj9GQkYuRjA=

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;

IyEiIiIiJg==

t;

LCYiIiJGIyomI0YjIiM1RiNJInhHNiJGI0Yj

j := 2: The Hermite reduction formula takes the form Int(r/q2^j, x) = -t/((j-1)*q2^(j-1)) + Int((s+diff(t,x)/(j-1))/q2^(j-1), x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsJiIiIiEiIiomIiIjRixJInhHRihGLEYsRiwpLCYqJClGMEYvRixGLCIiJkYsRi9GLUYwLCYqJiwmRixGLComI0YsIiM1RixGMEYsRixGLEYyRi1GLS1GJDYkLCQqJkY6RixGMkYtRi1GMEYs

and therefore the original integral has been reduced to Int(p/q, x) = int_P + rhs(%);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsMCokKUkieEdGKCIiJyIiIkYwKiYiIiZGMClGLkYyRjBGMComIiM1RjApRi4iIiVGMEYwKiYiI11GMClGLiIiJEYwRjAqJiIjREYwKUYuIiIjRjBGMComIiRGIkYwRi5GMEYwRjAhIiJGMCwoKiRGNkYwRjAqJkY1RjBGPkYwRjBGPUYwRkJGLiwqKiYjRjBGO0YwRjpGMEYwKiYjRjJGP0YwRj5GMEYwKiYsJkYwRjAqJiNGMEY1RjBGLkYwRjBGMCwmKiRGPkYwRjBGMkYwRkJGQi1GJDYkLCQqJkZORjBGT0ZCRkJGLkYw

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 NiMvLSUiUkc2IyUiekctJSpyZXN1bHRhbnRHNiUsJi0lIkFHNiMlInhHIiIiKiZGJ0YwKS0lIkJHRi4lIidHRjAhIiJGM0Yv and 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 is A := -1/10: B := x^2 + 5: Int(A/B, x);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQsJComIyIiIiIjNUYsLCYqJClJInhHRiciIiNGLEYsIiImRiwhIiJGNEYx

R := resultant(A - z*diff(B,x), B, x);

LCYqJiIjPyIiIilJInpHNiIiIiNGJUYlI0YlIiQrIkYl

(c1,c2) := solve(R=0, z);

NiQqJiomIyIiIiIkKyJGJl4jRiZGJkYmKSIiJiNGJiIiI0YmLCQqJiwkRiRGJkYmRilGJiEiIg==

v1 := gcd(A - c1*diff(B,x), B);

LCYqJiwkXiMiIiJGJkYmKSIiJiNGJiIiI0YmISIiSSJ4RzYiRiY=

v2 := gcd(A - c2*diff(B,x), B);

LCYqJl4jIiIiRiUpIiImI0YlIiIjRiVGJUkieEc2IkYl

Therefore the integral can be expressed as follows. Int(A/B, x) = c1*log(v1) + c2*log(v2);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLCQqJiMiIiIiIzVGLSwmKiQpSSJ4R0YoIiIjRi1GLSIiJkYtISIiRjVGMiwmKigqJiNGLSIkKyJGLV4jRi1GLUYtKUY0I0YtRjNGLS1JI2xuR0YlNiMsJiomLCRGO0YtRi1GPEYtRjVGMkYtRi1GLSooLCRGOEYtRi1GPEYtLUY/NiMsJiomRjtGLUY8Ri1GLUYyRi1GLUY1

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 is A := 1: B := x^3+x: Int(A/B, x);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqJCwmKiQpSSJ4R0YnIiIkIiIiRi9GLUYvISIiRi0=

R := resultant(A - z*diff(B,x), B, x);

KiYsJiIiIkYkSSJ6RzYiISIiRiQpLCYqJiIiI0YkRiVGJEYkRiRGJEYrRiQ=

solve(R=0, z);

NiUiIiIjISIiIiIjRiQ=

The distinct roots are (c1,c2) := (1,-1/2);

NiQiIiIjISIiIiIj

v1 := gcd(A - c1*diff(B,x), B);

SSJ4RzYi

v2 := gcd(A - c2*diff(B,x), B);

LCYqJClJInhHNiIiIiMiIiJGKEYoRig=

Therefore the integral can be expressed as follows. Int(A/B, x) = c1*log(v1) + c2*log(v2);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQsJiokKUkieEdGKCIiJCIiIkYwRi5GMCEiIkYuLCYtSSNsbkdGJTYjRi5GMComI0YwIiIjRjAtRjQ2IywmKiQpRi5GOEYwRjBGMEYwRjBGMQ==

In contrast, the "classical" approach would require a complete factorization of the denominator factored_B := factor(B,I);

LCQqKEkieEc2IiIiIiwmRiRGJl4jRiZGJkYmLCZGJCEiIkYoRiZGJkYq

integrand := convert(A/factored_B, parfrac, x);

LCgqJiMiIiIiIiNGJSwmSSJ4RzYiRiVeI0YlISIiRitGKyokRihGK0YlKiZGJEYlLCZGKEYlRipGJUYrRis=

from which we see that the integral is Int(A/B, x) = map(`int/risch`, integrand, x);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiQsJiokKUkieEdGKCIiJCIiIkYwRi5GMCEiIkYuLCgqJiNGMCIiI0YwLUkjbG5HRiU2IywmRi5GMF4jRjBGMUYwRjEtRjc2I0YuRjAqJkY0RjAtRjc2IywmRi5GMEY6RjBGMEYx

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 integral restart; Int(1/ln(x), x);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqJC1JI2xuR0YkNiNJInhHRichIiJGLQ==

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 is 1/theta;

KiRJJnRoZXRhRzYiISIi

For the integral Int((x^3+2*x)*cos(x^2)+x*sin(x^2), x);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQsJiomLCYqJClJInhHRiciIiQiIiJGMComIiIjRjBGLkYwRjBGMC1JJGNvc0dGJDYjKiQpRi5GMkYwRjBGMComRi5GMC1JJHNpbkdGJEY1RjBGMEYu

by converting the integrand to complex NiMlJGV4cEc=-NiMlJGxvZ0c= form, the problem can be expressed in the form Int((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);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQsJiooIyIiIiIiI0YsLCYqJClJInhHRiciIiRGLEYsKiZGLUYsRjFGLEYsRiwsJi1JJGV4cEdGJDYjKiZeI0YsRiwpRjFGLUYsRiwtRjY2IywkKiYsJEY5RixGLEY6RiwhIiJGLEYsRiwqKCwkKiZGK0YsRjlGLEYsRixGMUYsLCZGNUYsRjtGQEYsRkBGMQ==

and we can view the integrand as an element of the function field NiMtLSUiUUc2IyUiSUc2JCUieEclJnRoZXRhRw== where NiMvJSZ0aGV0YUctJSRleHBHNiMqJiUiSUciIiIqJCklInhHIiIjRipGKg== . (Note: NiMvJSJJRy0lJXNxcnRHNiMsJCIiIiEiIg== .) In this field the integrand is 1/2*(x^3+2*x)*(theta + 1/theta) - 1/2*I*x*(theta - 1/theta);

LCYqKCMiIiIiIiNGJSwmKiQpSSJ4RzYiIiIkRiVGJSomRiZGJUYqRiVGJUYlLCZJJnRoZXRhR0YrRiUqJEYvISIiRiVGJUYlKigsJComRiRGJV4jRiVGJUYlRiVGKkYlLCZGL0YlRjBGMUYlRjE=

For the integral presented in Example 1.1 Int(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);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqKkkieEdGJyIiIiwmRipGK0YrRitGKywmKiQpLCYqJilGKiIiI0YrLUkkZXhwR0YkNiMsJComRjNGK0YyRitGK0YrRisqJCktSSNsbkdGJDYjRixGM0YrISIiRjNGK0YrKipGM0YrRipGKy1GNTYjLCQqJiIiJEYrRjJGK0YrRissJkYqRisqJiwqKiZGM0YrKUYqRkRGK0YrRjhGK0YqRitGK0YrRitGO0YrRj5GK0YrRispLCYqJkYsRitGOkYrRisqJiwmKiRGSUYrRisqJEYyRitGK0YrRjRGK0Y+RjNGPkYq

we can view the integrand as an element of the function field NiMtJSJRRzYlJSJ4RyYlJnRoZXRhRzYjIiIiJkYoNiMiIiM= where NiMvJiUmdGhldGFHNiMiIiItJSRleHBHNiMqJCklInhHIiIjRic= and NiMvJiUmdGhldGFHNiMiIiMtJSNsbkc2IywmJSJ4RyIiIkYtRi0= . Note that the two exponential terms NiMtJSRleHBHNiMqJiIiIyIiIiokKSUieEdGJ0YoRig= and NiMtJSRleHBHNiMqJiIiJCIiIiokKSUieEciIiNGKEYo cannot be considered as independent extensions because there is an algebraic relationship between them. Rather, we choose to represent these terms in the form NiMqJCktJSRleHBHNiMqJCklInhHIiIjIiIiRitGLA== and NiMqJCktJSRleHBHNiMqJCklInhHIiIjIiIiIiIkRiw= which involves a single transcendental extension NiMvJiUmdGhldGFHNiMiIiItJSRleHBHNiMqJCklInhHIiIjRic= .

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 get NiMvLSUkSW50RzYkKiYtJSJyRzYjJSZ0aGV0YUciIiItJSJiR0YqISIiJSJ4Ry0lJFN1bUc2JC1GMjYkLUYlNiQqJi0mRik2JCUiaUclImpHRipGLCktJkYuNiNGPEYqRj1GL0YwL0Y9O0YsRjwvRjw7RiwlImtH 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);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqJC1JI2xuR0YkNiNJInhHRichIiJGLQ==

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);

KiRJInhHNiIhIiI=

R := resultant(A - z*diff_B, B, theta);

KiYsJkkieEc2IiIiIkkiekdGJSEiIkYmRiRGKA==

The single root of NiMtJSJSRzYjJSJ6Rw== is NiMvJSJ6RyUieEc= which is not a constant. Therefore the original integral is not elementary.

The integral Int(1/(x*ln(x)), x);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqJkkieEdGJyEiIi1JI2xuR0YkNiNGKkYrRio=

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));

LCZJJnRoZXRhRzYiIiIiRiVGJQ==

R := resultant(A - z*diff_B, B, theta);

KiZJInhHNiIiIiIsJkYlISIiSSJ6R0YkRiVGJQ==

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);

IiIi

SSZ0aGV0YUc2Ig==

and the integral is c[1]*ln(v[1]);

LUkjbG5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kmdGhldGFHRic=

In other words, Int(1/(x*ln(x)), x) = subs(theta=ln(x), c[1]*ln(v[1]));

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiZJInhHRighIiItSSNsbkdGJTYjRitGLEYrLUYuNiNGLQ==

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 that NiMvLSUkSW50RzYkLSUicEc2IyUmdGhldGFHJSJ4RywsKiYmJSJCRzYjLCYlImtHIiIiRjNGM0YzKUYqRjFGM0YzKiYmRi82I0YyRjMpRipGMkYzRjMlKn5+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 NiMvLSUkSW50RzYkJSZ0aGV0YUclInhHLCgqJiYlIkJHNiMiIiMiIiIqJClGJ0YuRi9GL0YvKiYmRiw2I0YvRi9GJ0YvRi8pJkYsNiMiIiElIipHRi8= 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 have theta := ln(x): B[2] := 0: B[1] := x: B[0] := -x: Int(theta, x) = B[2]*theta^2 + B[1]*theta + B[0];

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLUkjbG5HRiU2I0kieEdGKEYtLCYqJkYtIiIiRipGMEYwRi0hIiI=

The integral NiMtJSRJbnRHNiQtJSNsbkc2Iy1GJzYjJSJ4R0Yr has integrand NiMvLSUiZkc2IyYlJnRoZXRhRzYjIiIjRic= in the field NiMtJSJRRzYlJSJ4RyYlJnRoZXRhRzYjIiIiJkYoNiMiIiM= where NiMvJiUmdGhldGFHNiMiIiItJSNsbkc2IyUieEc= and NiMvJiUmdGhldGFHNiMiIiMtJSNsbkc2IyZGJTYjIiIi . If the integral is elementary then NiMvLSUkSW50RzYkJiUmdGhldGFHNiMiIiMlInhHLCgqJiYlIkJHRikiIiIqJClGJ0YqRjBGMEYwKiYmRi82I0YwRjBGJ0YwRjApJkYvNiMiIiElIipHRjA= 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 get NiMvLSUkSW50RzYkKiYtJSJyRzYjJSZ0aGV0YUciIiItJSJiR0YqISIiJSJ4Ry0lJFN1bUc2JC1GMjYkLUYlNiQqJi0mRik2JCUiaUclImpHRipGLCktJkYuNiNGPEYqRj1GL0YwL0Y9O0YsRjwvRjw7RiwlImtH 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 NiMvLSUkSW50RzYkKiYtJSJBRzYjJSZ0aGV0YUciIiItJSJCR0YqISIiJSJ4RywmJSJnR0YsLSUkU3VtRzYkKiYmJSJjRzYjJSJpR0YsLSUkbG9nRzYjLSYlInZHRjlGKkYsL0Y6O0YsJSJtR0Ys where 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);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqJiwoKiZJInhHRiciIiItSSRleHBHRiQ2IywkKiYiIiNGLSlGLEYzRi1GLUYtRi0qKiIiKUYtKUYzI0YtRjNGLUYsRi0sJi1GLzYjKiRGNEYtRi1GLUYtRi1GLSomRjNGLUYsRi1GLUYtLCotRi82IywkKiYiIiRGLUY0Ri1GLUYtRi5GLSomRjNGLUY6Ri1GLUYzRi0hIiJGLA==

The integrand is NiMvLSUiZkc2IyUmdGhldGFHKiYsKComJSJ4RyIiIiokKUYnIiIjRixGLEYsKioiIilGLC0lJXNxcnRHNiNGL0YsRitGLCwmRidGLEYsRixGLEYsKiZGL0YsRitGLEYsRiwsKiokKUYnIiIkRixGLEYtRiwqJkYvRixGJ0YsRixGL0YsISIi in the function field NiMtLSUiUUc2Iy0lJXNxcnRHNiMiIiM2JCUieEclJnRoZXRhRw== where NiMvJSZ0aGV0YUctJSRleHBHNiMqJCklInhHIiIjIiIi . A resultant computation (Rothstein-Trager Theorem) is applicable. Keep in mind that NiMvJSZ0aGV0YUctJSRleHBHNiMlInVH where NiMvJSJ1RyokKSUieEciIiMiIiI= . 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));

LCgqKCIiJyIiIilJJnRoZXRhRzYiIiIkRiVJInhHRihGJUYlKigiIiVGJUYqRiUpRiciIiNGJUYlKihGLEYlRipGJUYnRiVGJQ==

R := resultant(A - z*diff_B, B, theta);

LCQqKCIkdyYiIiIpSSJ4RzYiIiIkRiUsLiIiI0YlKiYiIiVGJUkiekdGKEYlRiUqKEYrRiUpRisjRiVGK0YlRi5GJUYlKihGLUYlRjBGJSlGLkYrRiVGJSokRjNGJUYlKiZGK0YlKUYuRilGJUYlRiUhIiI=

solve(R=0, z);

NiUjISIiIiIjLCQqJClGJSMiIiJGJUYqRiRGJg==

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);

LCZJJnRoZXRhRzYiIiIiRiVGJQ==

v[2] := gcd(A - c[2]*diff_B, B);

LCYqJClJJnRoZXRhRzYiIiIjIiIiRihGJ0Yo

The function NiMlImdH appearing in Theorem 6 is g := add(-c[i]*degree(v[i],theta), i=1..2) * u;

KiYsJiMiIiIiIiNGJSomRiZGJSlGJkYkRiVGJUYlKUkieEc2IkYmRiU=

and the desired integral is result := g + add(c[i]*ln(v[i]), i=1..2);

LCgqJiwmIyIiIiIiI0YmKiZGJ0YmKUYnRiVGJkYmRiYpSSJ4RzYiRidGJkYmKiZGJUYmLUkjbG5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHRiw2IywmSSZ0aGV0YUdGLEYmRiZGJkYmISIiKiZGKUYmLUYvNiMsJiokKUY1RidGJkYmRidGJkYmRjY=

In other words, Int(f,x) = subs(theta=exp(u), result);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsKComSSJ4R0YoIiIiLUkkZXhwR0YlNiMsJComIiIjRi4pRi1GNEYuRi5GLkYuKioiIilGLilGNCNGLkY0Ri5GLUYuLCYtRjA2IyokRjVGLkYuRi5GLkYuRi4qJkY0Ri5GLUYuRi5GLiwqLUYwNiMsJComIiIkRi5GNUYuRi5GLkYvRi4qJkY0Ri5GO0YuRi5GNEYuISIiRi0sKComLCZGOUYuKiZGNEYuRjhGLkYuRi5GNUYuRi4qJkY5Ri4tSSNsbkdGJTYjRjpGLkZGKiZGOEYuLUZNNiMsJiokKUY7RjRGLkYuRjRGLkYuRkY=

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 that NiMvLSUkSW50RzYkLSUicEc2IyUmdGhldGFHJSJ4RywmLSUkU3VtRzYkKiYmJSJCRzYjJSJqRyIiIilGKkY0RjUvRjQ7LCQlImtHISIiJSJsR0Y1LUYuNiQqJiYlImNHNiMlImlHRjUtJSRsb2dHNiMmJSJ2R0ZCRjUvRkM7RjUlIm1HRjU= . 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== NiMvJiUiQUc2IyIiISkpJiUiQkdGJiUiKkclIidH where 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 integral restart; Int(exp(-x^2), x);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQtSSRleHBHRiQ2IywkKiQpSSJ4R0YnIiIjIiIiISIiRi8=

has integrand NiMvLSUiZkc2IyUmdGhldGFHRic= in the function field NiMtJSJRRzYkJSJ4RyUmdGhldGFH where NiMvJSZ0aGV0YUctJSRleHBHNiMsJCokKSUieEciIiMiIiIhIiI= . 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 NiMtJSRJbnRHNiQqKCUieEciIiItJSRleHBHNiMtJSVzcXJ0RzYjLCYqJClGJyIiI0YoRihGMkYoRihGLCEiIkYn then the integrand lies in the elementary function field NiMtJSJRRzYlJSJ4RyYlJnRoZXRhRzYjIiIiJkYoNiMiIiM= where NiMvJiUmdGhldGFHNiMiIiItJSVzcXJ0RzYjLCYqJCklInhHIiIjRidGJ0YvRic= 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 NiMtJSRJbnRHNiQtJSRleHBHNiMsJCokKSUieEciIiMiIiIhIiJGLA== 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);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLUkkZXhwR0YlNiMsJCokKUkieEdGKCIiIyIiIiEiIkYwLCQqKCNGMkYxRjIpSSNQaUdGJkY2RjItSSRlcmZHRiU2I0YwRjJGMg==

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);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkLUkjbG5HRiU2Iy1GKzYjSSJ4R0YoRi8sJiomRioiIiJGL0YyRjItSSNFaUdGJTYkRjIsJEYtISIiRjI=

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. NiMvLSUkSW50RzYkKigsJiomIiIkIiIiKiQpJSJ4RyIiJ0YrRitGK0YrRitGKy0lJGV4cEc2IywkKiQpLSUjbG5HNiNGLiIiI0YrISIiRisqJClGLiIiJkYrRjpGLiwmKiotRjE2IyIiJUYrLSUlc3FydEc2IyUjUGlHRistJSRlcmZHNiMsJkY2RitGOUYrRitGOUY6RisqLEYqRistRjE2I0YrRitGQ0YrLUZINiMsJkY2RitGK0Y6RitGOUY6Ris= NiMvLSUkSW50RzYkKiYpJSJ4RyIiJCIiIi0lI2xuRzYjLCYqJClGKSIiI0YrRitGKyEiIkYzRiksJiomLSUjRWlHNiRGKywkRixGM0YrRjJGM0YzKiYtRjc2JEYrLCQqJkYyRitGLEYrRjNGK0YyRjNGMw== 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 integral Int(f, x=0..2);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQtSSNsbkdGJDYjSSJ4R0YnL0YsOyIiISIiIw==

We can compute the antiderivative F := int(f, x);

LCYqJkkieEc2IiIiIi1JI2xuRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YlNiNGJEYmRiZGJCEiIg==

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);

LCYqJiIiIyIiIi1JI2xuRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiNGJEYlRiVGJCEiIg==

Of course, the integration procedure in Maple will do this computation automatically. int(f, x=0..2);

LCYqJiIiIyIiIi1JI2xuRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiNGJEYlRiVGJCEiIg==

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;

KiYtSSRzaW5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGKCIiIkYqISIi

series(g, x=0);

KytJInhHNiIiIiIiIiEjISIiIiInIiIjI0YlIiQ/IiIiJS1JIk9HJSpwcm90ZWN0ZWRHNiNGJSIiJg==

From the series expansion it is clear what is the limit at NiMvJSJ4RyIiIQ== . Limit(g, x=0) = limit(g, x=0);

Ly1JJkxpbWl0RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqJi1JJHNpbkdGJTYjSSJ4R0YoIiIiRi4hIiIvRi4iIiFGLw==

Another example: g := x^x;

KUkieEc2IkYj

series(g, x=0, 3);

KytJInhHNiIiIiIiIiEtSSNsbkc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJDYjRiNGJSwkKiYjRiUiIiNGJSlGJ0YwRiVGJUYwLUkiT0dGKjYjRiUiIiQ=

Limit(g, x=0) = limit(g, x=0);

Ly1JJkxpbWl0RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQpSSJ4R0YoRisvRisiIiEiIiI=

And another example: g := ln(1-cos(x^2))/(ln(x)*arctan(sqrt(1-x^2)));

KigtSSNsbkc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYjLCYiIiJGKy1JJGNvc0dGJTYjKiQpSSJ4R0YoIiIjRishIiJGKy1GJDYjRjFGMy1JJ2FyY3RhbkdGJTYjKiQpLCZGK0YrRi9GMyNGK0YyRitGMw==

series(g, x=0, 4);

KylJInhHNiIsJCoqIiIlIiIiLCYtSSNsbkc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkdGJDYjIiIjISIiKiZGJ0YoLUYrNiNGI0YoRihGKEYzRjFJI1BpR0YtRjFGKCIiISwkKipGJ0YoLCZGKkYoRjJGMUYoRjNGMSlGNUYwRjFGMUYwLUkiT0dGLTYjRihGJw==

Limit(g, x=0) = limit(g, x=0);

Ly1JJkxpbWl0RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqKC1JI2xuR0YlNiMsJiIiIkYvLUkkY29zR0YlNiMqJClJInhHRigiIiNGLyEiIkYvLUYsNiNGNUY3LUknYXJjdGFuR0YlNiMqJCksJkYvRi9GM0Y3I0YvRjZGL0Y3L0Y1IiIhLCQqJiIjO0YvSSNQaUdGJkY3Ri8=

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 is f := (x^4-3*x^2+6)/(x^6-5*x^4+5*x^2+4): Int(f, x=1..2);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqJiwoKiQpSSJ4R0YnIiIlIiIiRi8qJiIiJEYvKUYtIiIjRi8hIiIiIidGL0YvLCoqJClGLUY1Ri9GLyomIiImRi9GLEYvRjQqJkY6Ri9GMkYvRi9GLkYvRjQvRi07Ri9GMw==

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);

LCYqJiomIyIiIiIiI0YmXiNGJkYmRiYtSSNsbkc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYjLCoqJClJInhHRi4iIiRGJkYmKiZGKEYmKUYzRidGJkYmKiZGNEYmRjNGJiEiIiomRidGJkYoRiZGOEYmRiYqJiwkRiRGJkYmLUYqNiMsKkYxRiYqJiwkRihGJkYmRjZGJkY4RjdGOEY5RiZGJkY4

That is, Int(f, x) = F;

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsKCokKUkieEdGKCIiJSIiIkYwKiYiIiRGMClGLiIiI0YwISIiIiInRjBGMCwqKiQpRi5GNkYwRjAqJiIiJkYwRi1GMEY1KiZGO0YwRjNGMEYwRi9GMEY1Ri4sJiomKiYjRjBGNEYwXiNGMEYwRjAtSSNsbkdGJTYjLCoqJClGLkYyRjBGMComRkFGMEYzRjBGMComRjJGMEYuRjBGNSomRjRGMEZBRjBGNUYwRjAqJiwkRj9GMEYwLUZDNiMsKkZGRjAqJiwkRkFGMEYwRjNGMEY1RklGNUZKRjBGMEY1

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);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsKCokKUkieEdGKCIiJSIiIkYwKiYiIiRGMClGLiIiI0YwISIiIiInRjBGMCwqKiQpRi5GNkYwRjAqJiIiJkYwRi1GMEY1KiZGO0YwRjNGMEYwRi9GMEY1L0YuO0YwRjQsJiomI0Y7Ri9GMEkjUGlHRiZGMEY1LUknYXJjdGFuR0YlNiMjRjBGNEYw

evalf(rhs(%));

JCErNEtNak0hIio=

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 is F_continuous := arctan((x^5 - 3*x^3 + x)/2) + arctan(x^3) + arctan(x);

LCgtSSdhcmN0YW5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2IywoKiYjIiIiIiIjRi0pSSJ4R0YoIiImRi1GLSomIyIiJEYuRi0pRjBGNEYtISIiKiZGLEYtRjBGLUYtRi0tRiQ2IyokRjVGLUYtLUYkNiNGMEYt

By differentiating, we see that this is a correct antiderivative of the original integrand NiMlImZH . simplify( diff(F_continuous, x) );

KiYsKCokKUkieEc2IiIiJSIiIkYpKiYiIiRGKSlGJiIiI0YpISIiIiInRilGKSwqKiQpRiZGL0YpRikqJiIiJkYpRiVGKUYuKiZGNEYpRixGKUYpRihGKUYu

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);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsKCokKUkieEdGKCIiJSIiIkYwKiYiIiRGMClGLiIiI0YwISIiIiInRjBGMCwqKiQpRi5GNkYwRjAqJiIiJkYwRi1GMEY1KiZGO0YwRjNGMEYwRi9GMEY1L0YuO0YwRjQsLC1JJ2FyY3RhbkdGJTYjRjtGMC1GQTYjIiIpRjAtRkE2I0Y0RjAtRkE2IyNGMEY0RjAqJkZKRjBJI1BpR0YmRjBGNQ==

evalf(rhs(%));

JCIrKjRVKT5HISIq

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;

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsKCokKUkieEdGKCIiJSIiIkYwKiYiIiRGMClGLiIiI0YwISIiIiInRjBGMCwqKiQpRi5GNkYwRjAqJiIiJkYwRi1GMEY1KiZGO0YwRjNGMEYwRi9GMEY1Ri4sJiomKiYjRjBGNEYwXiNGMEYwRjAtSSNsbkdGJTYjLCoqJClGLkYyRjBGMComRkFGMEYzRjBGMComRjJGMEYuRjBGNSomRjRGMEZBRjBGNUYwRjAqJiwkRj9GMEYwLUZDNiMsKkZGRjAqJiwkRkFGMEYwRjNGMEY1RklGNUZKRjBGMEY1

In Maple, the following command will determine the points of discontinuity over the whole real line. discont(F, x);

PCQtSSdSb290T2ZHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2JCwmIiIjISIiKiQpSSNfWkdGJUYrIiIiRjAkIStpTkA5OSEiKi1GJDYkRiokIitpTkA5OUYz

allvalues(%);

PCQqJCkiIiMjIiIiRiVGJywkRiMhIiI=

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);

KiQpIiIjIyIiIkYkRiY=

and the endpoints of integration are a := 1; b := 2;

IiIi

IiIj

The correct value of the definite integral on NiMtJSFHNiQlImFHJSJiRw== can therefore be computed by using the fact that NiMvLSUkSW50RzYkLSUiZkc2IyUieEcvRio7JSJhRyUiYkcsJi1GJTYkRicvRio7Ri0lImNHIiIiLUYlNiRGJy9GKjtGNEYuRjU= 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);

Ly1JJEludEc2JCUqcHJvdGVjdGVkR0koX3N5c2xpYkc2IjYkKiYsKCokKUkieEdGKCIiJSIiIkYwKiYiIiRGMClGLiIiI0YwISIiIiInRjBGMCwqKiQpRi5GNkYwRjAqJiIiJkYwRi1GMEY1KiZGO0YwRjNGMEYwRi9GMEY1L0YuO0YwRjQsJiomI0YyRi9GMEkjUGlHRiZGMEYwLUknYXJjdGFuR0YlNiMjRjBGNEYw

evalf(rhs(%));

JCIrKjRVKT5HISIq

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; assume(c::real); interface(showassumed=0): f1 := x^(s-1)*exp(-p*x^4)*erfi(c*x)*erf(c*x): Int(f1, x=0..infinity);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqKilJInhHRicsJkkic0dGJyIiIkYuISIiRi4tSSRleHBHRiQ2IywkKiZJInBHRidGLilGKyIiJUYuRi9GLi1JJWVyZmlHRiQ2IyomSSNjfGlyR0YnRi5GK0YuRi4tSSRlcmZHRiRGOkYuL0YrOyIiIUkpaW5maW5pdHlHRiU=

result1 := value(%);

KiwpSSJwRzYiLCYqJiMiIiIiIiVGKUkic0dGJUYpISIiI0YpIiIjRixGKUkjUGlHJSpwcm90ZWN0ZWRHRiwpSSNjfGlyR0YlRi5GKS1JKmh5cGVyZ2VvbUdJKF9zeXNsaWJHRiU2JTclRi1GKSwmRi1GKUYnRik3JSMiIiRGKiMiIiZGKiNGO0YuLCQqKEYoRikpRjJGKkYpRiRGLEYpRiktSSZHQU1NQUc2JEYwRjU2I0Y4Rik=

The method used was first to convert the integrand into NiMlKE1laWplckdH form. f1new := convert(f1, MeijerG, x);

LCQqLiwkXiMiIiJGJkYmKUkieEc2IiwmSSJzR0YpRiZGJiEiIkYmLUkkZXhwRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YpNiMsJComSSJwR0YpRiYpRigiIiVGJkYsRiZJI1BpR0YwRiwtSShNZWlqZXJHR0YvNiU3JDcjRiY3IjckNyMjRiYiIiM3IyIiISwkKiYpSSNjfGlyR0YpRkJGJilGKEZCRiZGLEYmLUY6NiVGPEY/RkZGJkYs

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);

KiwpSSJwRzYiLCYqJiMiIiIiIiVGKUkic0dGJUYpISIiI0YpIiIjRixGKUkjUGlHJSpwcm90ZWN0ZWRHRiwpSSNjfGlyR0YlRi5GKS1JKmh5cGVyZ2VvbUdJKF9zeXNsaWJHRiU2JTclRi1GKSwmRi1GKUYnRik3JSMiIiRGKiMiIiZGKiNGO0YuLCQqKEYoRikpRjJGKkYpRiRGLEYpRiktSSZHQU1NQUc2JEYwRjU2I0Y4Rik=

which is equal to NiMlKHJlc3VsdDFH . simplify(% - result1);

IiIh

Of course, for particular values of the parameters we may compute a numerical value. eval(result1, {s=4, p=1, c=1});

LCQqKCMiIiIiIiNGJSlJI1BpRyUqcHJvdGVjdGVkR0YkISIiLUkqaHlwZXJnZW9tR0koX3N5c2xpYkc2IjYlNyRGJEYlNyQjIiIkIiIlIyIiJkY0I0YlRjRGJUYl

evalf(%);

JCIrXVthTkshIzU=

restart; assume(b>0, y>0); interface(showassumed=0): f2 := x^v/(x^2+y^2)*BesselK(v,b*x): Int(f2, x=0..infinity);

LUkkSW50RzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiQqKClJInhHRidJInZHRiciIiIsJiokKUYrIiIjRi1GLSokKUkjeXxpckdGJ0YxRi1GLSEiIi1JKEJlc3NlbEtHRiQ2JEYsKiZJI2J8aXJHRidGLUYrRi1GLS9GKzsiIiFJKWluZmluaXR5R0Yl

result2 := value(%);

LCQqKCMiIiIiIiVGJSlJI3l8aXJHNiIsJkkidkdGKUYlRiUhIiJGJSwmKigpSSNQaUclKnByb3RlY3RlZEciIiNGJS1JKEJlc3NlbFlHNiRGMUkoX3N5c2xpYkdGKTYkLCRGK0YsKiZJI2J8aXJHRilGJUYoRiVGJS1JJHNlY0dGNTYjKiZGMEYlRitGJUYlRiwqKEYvRiUtSShTdHJ1dmVIR0Y1RjdGJUY7RiVGJUYlRiU=

Note that the result of converting the integrand into NiMlKE1laWplckdH form is as follows. f2new := convert(f2, MeijerG, x);

LCQqKiMiIiIiIiNGJSlJInhHNiJJInZHRilGJSwmKiQpRihGJkYlRiUqJClJI3l8aXJHRilGJkYlRiUhIiItSShNZWlqZXJHRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliR0YpNiU3JDciRjk3JDckLCQqJkYkRiVGKkYlRiUsJEY9RjFGOSwkKigjRiUiIiVGJSlJI2J8aXJHRilGJkYlRi1GJUYlRiVGJQ==

int(f2new, x=0..infinity);

LCQqKCMiIiIiIiVGJSlJI3l8aXJHNiIsJkkidkdGKUYlRiUhIiJGJSwmKigpSSNQaUclKnByb3RlY3RlZEciIiNGJS1JKEJlc3NlbFlHNiRGMUkoX3N5c2xpYkdGKTYkLCRGK0YsKiZJI2J8aXJHRilGJUYoRiVGJS1JJHNlY0dGNTYjKiZGMEYlRitGJUYlRiwqKEYvRiUtSShTdHJ1dmVIR0Y1RjdGJUY7RiVGJUYlRiU=

which is equal to LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEocmVzdWx0MkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJw== . simplify(% - result2);

IiIh

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.