AAECC 1, 5-24 (1990)

AAECC

Applicable Algebra in Engineering, Communication and Computing

© Springer-Verlag 1990

A Unification of Liouvillian Extensions Manuel Bronstein IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY 10598, USA

Abstract. We generalize Liouville's theory of elementary functions to a larger class of differential extensions. Elementary, Liouvillian and trigonometric extensions are all special cases of our extensions. In the transcendental case, we show how the rational techniques of integration theory can be applied to our extensions, and we give a unified presentation which does not require separate cases for different monomials. Keywords: Liouvillian functions, Elementary functions, Integration in finite terms, Differential algebra Introduction The publication of Risch's first integration algorithm (Risch, 1969) has generated much research in symbolic integration, and progress has been made in two main directions: 1. The algorithm has been generalized to handle algebraic functions in the integrand (Risch, 1970; Bronstein 1990b), and some classes of special functions both in the integrand and the integral (Cherry, 1985, 1986; Knowles, 1986). 2. Improvements have been found, that make the algorithms perform only rational operations, which made them simpler, easier to implement, and more efficient (Rothstein, 1976; Trager, 1976, 1984; Bronstein, 1990a). Algorithms in both of those directions make extensive use of some key properties of elementary and Liouvillian functions, e.g. the relations between the orders of a function and its derivative at their poles. Those properties are very similar for various cases of functions (rational, logarithmic, exponential.... ) but the minor differences have caused the proofs to be presented separately in each case. Most authors avoid repeating the proofs with statements pointing to the similarity, e.g. • "The proof is then similar to the proof of Proposition 2.13, using Proposition 2.22 instead of 2.11." (Bronstein, 1990b). • "The proofs of the following four lemmas are similar to the corresponding proofs in the previous sections." (Davenport, 1986).

6

M. Bronstein

• "Here the general method is the same as for the K(z) case." and "Here, in distinction to the K(z) case and Case 1, degree(if/)= degree (Pi) so things are slightly different." (Risch, 1969). • "The proof when f e E follows in a similar manner and will be omitted." (Singer, 1988). We describe in this paper a class of ordinary differential extensions where those properties hold, and where most techniques of symbolic integration can be generalized. Elementary and Liouvillian extensions are special cases of our extensions, so the Risch algorithm and its extensions can be presented in a unified form. A traditional problem with those algorithms is that they transform trigonometric functions and their inverses to complex exponentials and logarithms. As pointed out in (Geddes and Stefanus, 1989), this is a source of computational inefficiency and the algorithms return answers in a form unrelated to the user's input. For example, integrating (x - tan (x) )/tan (x) 2 with the Risch algorithm returns

X22

x~/rZ]---

2 xx~-I e2~-~-1 -1

while a real antiderivative is - x / t a n ( x ) - x2/2. Since real elementary extensions (i.e. allowing tangents, arc tangents, hyperbolic tangents, and hyperbolic arc tangents in elementary extensions) are special cases of our extensions, the unified parts of the algorithms are valid for those extensions also. As an application of the results in this paper, we have an integration algorithm for real transcendental elementary functions which does not require trigonometric functions and their inverses to be converted to complex functions. A detailed description of that algorithm will appear in a subsequent paper. 1. Monomial Extensions Definition. A differential field is a field k with a given map a ~ a' from k into k, satisfying (a + b)' = a' + b' and (ab)' -- a'b + ab'. Such a map is called a derivation on k. An element a~k which satisfies a' = 0 is called a constant. The constants of k form a subfield of k. A differential field K is a differential extension of k if k ~=K, and the derivation on K extends the one on k.

Definition 1.1. Let k be a differential field and K be a differential extension of k. x e K is a monomiai over k (with respect to '), if (i) x is transcendental over k, (ii) k(x) and k have the same subfield o f constants, (iii) x' = H(x) for some H ~ k [ x ] . I f x is a monomial over k, then the degree of x is d ( x ) = deg (H), and the leading coefficient of x is lc(x)= coefficient of x dtx) in H. K is a monomial extension of k if there exist x 1. . . . . x m ~ K such that K = k(x x..... xm) and for each i, x i is either aloebraic or a monomial over k(xl ..... xl- 1).

Unification of Liouvillian Extensions

7

Suppose that k is of characteristic p 4: 0, and let x be transcendental over k. Then, xPCk, but x p' = px'x p- 1 = 0, so condition (ii) is not satisfied. Thus, a field of nonzero characteristic does not have any transcendental m o n o m i a l extension, so from n o w on, all our fields will be of characteristic 0. Let x e K be a m o n o m i a l over k, satisfying x' = H(x). We define the associated differential operator ~ by ~(t) = t' - H(t). S i n c e ' can be extended uniquely to any algebraic extension of K, @ is uniquely defined o n / ( ' . L e m m a 1.2. Let x be a monomial over k, and P e k [ x ] . Then P' Ek[x].

Proof. Let P = ~ aixiEk[x]. Then, i=0

P ' = ~ a'ixi+ H(x) ~ iaixi-lEk[x]. i=0

i=1

L e m m a 1.3. Let k be an algebraic closure of k. l f x 6 K is a rnonomial over k, then

x is also a monomial over k. Proof. x is transcendental over k, so it is transcendental over k. Let c~k(x), and suppose that c' = 0. Since k(x) is of transcendence degree 1 over k, k(x, c) is finite algebraic over k(x), so let n = [k(x, c):k(x)] and P(y) = y" + b,_ ly n- 1 + . . . + bo be the minimal polynomial for c over k(x). We have P(c)= 0, so O = ( P ( c ) ) ' = ( c " + b . - l c "-1 + "" + b o ) ' = b ' . - l c "-1 + "" +b'o so b'i = 0 for i = 0... n - 1 by the minimality of P(y). Since k and k(x) have the same constants, b~ek for i = 0--. n - 1, therefore cek, so k(x) and k have the same subfield of constants.

Normality Let k be a differential field of characteristic 0, and x a m o n o m i a l over k. Let ' be the derivation on k(x). Definition 1.4. P ~ k [ x ] is normal with respect to ' /f (P, P ' ) = (1). Otherwise, P is special (with respect to '). A normal polynomial is obviously squarefree. The converse is not necessarily true, so we now attempt to characterize special squarefree polynomials. Theorem 1.5. Let P ~ k [ x ] be squarefree. Then,

P specialc:,3tek

such that

P(t)=0

and

~(t)=0.

Proof. Let P e k [ x ] be squarefree. Suppose first that ~ ( t ) = 0 for some t e k such that P(t)= 0. Then, there are a 1. . . . . a, ek such that P = ~ a i ( x - t) ~, so i=l

P' = ~, a'i(x - t)i + (x' - t') ~ iai(x - t) i-1 /=1

i=1

= ~ a'i(x - t) i + (H(x) - H(t)) ~ iai(x - t) i- 1. i=1

i=1

8

M. Bronstein

Substituting x = t, we see that P'(t)= 0, so ( x - t)lP'. Therefore ( x - t)l(P, P') and P is special. Conversely, suppose that P is special, and let tl . . . . . t, be the roots of P in k. Since P is squarefree, ti ~ tj for i ~ j, and P = c ~ (x - ti), where cek. Since P is special, ( x - tio)l P' for some i0. But i= 1 P' = c ' P + c

c,) H

i=1

j~i

- tj)

so (x - tio)[(H(x) - t'io), SO H(tio) -- t'io = 0, SO ~(tio) = O. Corollary 1.6. Let P e k [ x ] be irreducible. Then,

P specialc>(Vtek, P(t) = 0 ~ ( t )

= 0).

Proof. Let P e k [ x ] be irreducible, then P is squarefree. If @(t) = 0 for all the roots of P in k, then P is special by T h e o r e m 1.5. Conversely, suppose that P is special. Then there exists t e e such that P(t)= ~ ( t ) = 0. Let w e e be such that P(w)= O. Then there exists an a u t o m o r p h i s m a of k over k such that w = t °. But then, ~(w) = ~ ( t °) = t °' - n ( t °) = t '° - n(t) ° = ~(t) # = O. Corollary 1.7. Let P e k [ x ] normal,c~(e, H) = (1).

be squarefree, and suppose that k ' = 0 .

Then, P

Proof. Let tek., then t' = 0, so ~(t) = - H(t). F o r a squarefree Pek[x], T h e o r e m 1.5 then states that P is special if and only if P and H have a c o m m o n root in tek, so P is n o r m a l if and only if ( P , H ) = (1). Given Pek[x], we want to separate the special and n o r m a l c o m p o n e n t s of P. The following definition formalizes that separation.

Definition 1.8. Let Pek[x]. A split factorization of P is a factorization of the form P = PsPN where Ps, PNek[x], every irreducible factor of Ps is special, and every irreducible factor of PN is normal. A consequence of Corollary 1.6 is that a split factorization of a split-factorization of P over k. Applying Corollary 1.6, we can factorization of P from a prime factorization of P. Factoring over k however, and we now proceed to show how computing a split similar to computing a squarefree factorization.

P over k is also compute a split is not necessary, factorization is

L e m m a 1.9. Let F be a field, t be transcendental over F, and d be a derivation on

F[t]. Let P1 ..... PmeF[t] be such that

(Pi,

Pj) = (1) for i # j, and P = ~-1 P~' where i=1

the ei's are positive integers. Then,

Proof. Let A, B e F [ t ] and suppose that (A, B ) = (1). Then,

Unification of Liouvillian Extensions

9

(AB, d( AB) ) = (A, d(AB) )(B, d(AB) ) = (A, A(dB) + B(dA))(B, A(dB) + B(dA)) = (A, B(dA))(B, A(dB)) = (A, dA)(B, dB). Therefore, (P, dP)= f l (P~', d(P~')). But, i=1

(P7', d(P7')) = (PT', eiP7'- i d(P,)) = (P7'- 1)(Pi, eid(P~)) = (PT~- x)(P i, d(Pg)) which proves the Lemma. L e m m a 1.10. Let x be a monomial over k, and let P6k[x]. I f all the irreducible factors of P are special, then PIP'.

Proof. Let P = 1~ P7' be the prime factorization of P, and suppose that all the i-1

Pi's are special. Then, (Pg, P'g) = (Pi) for each i. By Lemma 1.9 applied to ', we then have

(

)

g=l

)m

(

g=l

g=l

i

so PIP'. Theorem 1.11.

(i) Let P6k[x], and/5 = g c d (P, P')/gcd (P, •P/3x). Then, P is the product of all the distinct special irreducible factors of P. (ii) Let P6k[x] be squarefree. Then P = PsPN is a split factorization of P, where Ps = g c d (P, P') and PN = P/Ps.

Proof. (i) Let P6k[x], P = PsPN be a split-factorization of P, Ps = f l Sd~ be the prime factorization of Ps, and PN =

l~

j=l N~' be the prime factorization of PN- We

have (Ps, PN)= (1), so by Lemma 1.9 applied to ' and c~/c~x,we have /5 _ gcd (P, P')

gcd (Ps, P's)

gcd (Sj, S j) j=l

j=l

gcd (PN, P'N)

gcd (Ni, Ng) i=l

g=l

Each N i is normal, so (Ng, N'g)=(Ng,3Ng/t3x)= (1), and each Sj is special and squarefree, so (Sj, S))= (Sj) and (Sj, t3Sj/c~x)= (1). Therefore P=fl

j=l

St

which is the product of all the distinct special irreducible factors of P.

10

M. Bronstein

(ii) Suppose that P e k [ x ] is squarefree, then (P, OP/dx)= (1), so 15= gcd(P, P') is the product of all the distinct special irreducible factors of P. But P is squarefree, so P//5 has no special factor, so P = P(P/P) is a split-factorization of P. T h e o r e m 1.11 gives us two ways of computing a split factorization of PEk[x]: 1. C o m p u t e a squarefree factorization P -- P I P 2 .2. . P m m, and then c o m p u t e Si = gcd (Pi, P'~) and N~ = Pi/S~. By T h e o r e m 1.11 (ii), P = PsPN is a split factorization of P where Ps = $1S22 ""Sinm and PN = N I N2 ""Nm" m N o t e that this also gives us the squarefree factorizations of Ps and PN. 2. C o m p u t e / 5 = gcd(P,P')/gcd(P,t~P/dx), and Q = P//5. If d e g ( / 5 ) = 0 , then P is normal, so return Ps = 1, PN = P. Otherwise, recursively compute a split factorization Q = QsQN and return Ps = Qs/5, PN = Q~. We can now give some examples of m o n o m i a l extensions and use T h e o r e m 1.5 to get explicit descriptions of what normality means in each case.

Liouvillian and Elementary Extensions Let k be a differential field of characteristic 0, and K a differential extension of k.

Definition 1.12. x e K is a Liouvillian monomial over k if x is a monomial over k, and there exists a e k such that either

(i) H(x) = a, in which case we say that x is primitive over k, and write x = S a, or (ii) H ( x ) = ax, in which case we say that x is exponentially primitive over k, and write x = exp (Sa).

Definition 1.13. x e K is an elementary monomial over k if x is a monomial over k, and there exists a e k such that either

(i) H(x) = a'/a, in which case we say that x is logarithmic over k, and write x = log (a), or

(ii) H(x) = a'x, in which case we say that x is exponential over k, and write x = exp (a). Since l o g ( a ) = ~a'/a, and e x p ( a ) = exp(~a'), any elementary m o n o m i a l is also Liouvillian. The following often used complete characterization of special polynomials (e.g. Davenport, 1983; Bronstein, 1990b), is a direct consequence of T h e o r e m 1.5: Corollary 1.14. Let x be a Liouvillian monomial over k, and P ~ k [ x ] be squarefree. Then, (i) I f x is primitive over k, then P is normal. (ii) / f x is exponentially primitive over k, then P n o r m a l c ~ ( P , x ) = (1). Proof. Let P ~ k [ x ] be squarefree.

(i) Let x be primitive over k, then x' = a~k, so ~(t) = t' - a. Let t~k be such that ~(t) = 0, then (x - t)' = x' - t' = a - a = 0, so x - t is a constant which is transcendental over k, in contradiction with x being a m o n o m i a l over k. So ~ has no zero in k, so P is n o r m a l by T h e o r e m 1.5.

Unification of LiouviUian Extensions

11

(ii) Let x be exponentially primitive over k, then x' = a x for a e k . Then ~ ( t ) = t' - at, so N(0) = 0, so x is special, so if P is normal, then (P, x) = (1). Let t e e be such that t # 0 and N ( t ) = 0, then x ' t - x t ' = a x t - x a t = 0, so x / t is a constant which is transcendental over k, in contradiction with x being a m o n o m i a l over k. So N has no zero in k\{0}, so ( P , x ) = (1) implies P n o r m a l by T h e o r e m 1.5.

Real Elementary Extensions Let k be a differential field of characteristic O, and K a differential extension of k. Definition 1.15. x ~ K is a tangent monomial over k if x is a monomial over k, and there exists a e k such that either

(i)

H ( x ) = d x 2 + a', in which case we say that x is a

tangent

over k, and write

x -- tan (a). (ii) H(x) = -- a'x 2 + a', in which case we say that x is an hyperbolic tangent over k, and write x = tanh (a). W e also define the

signature o f

x to be

{1_, a(x)=

1,

/f /f

x=tan(a) x=tanh(a).

Sines, cosines, and their hyperbolic versions can be expressed as elements of tangent extensions with the following well k n o w n formulas: 2 tan (a/2) sin (a) - 1 + tan (a/2) 2'

1 - tan (a/2) 2 cos (a) = 1 + tan (a/2) z

2 tanh (a/2) sinh (a) = 1 - tanh (a/2) 2'

1 + tanh (a/2) 2 cosh (a) = 1 - tanh (a/2) 2"

Theorem 1.5 gives us a complete characterization of special polynomials: Corollary 1.16. L e t x be a tangent monomial over k, and P E k [ x ] be squarefree. Then, (i) I f x is a tangent over k, then P normal<:>(P, 1 + x 2) ~-- (1).

(ii) I f x is an hyperbolic tangent over k, then P n o r m a l ~ ( P , 1 - x 2) = (1). Proof. Let x be a tangent m o n o m i a l over k, then x ' = a ' + ea'x 2 where e = a(x), so ~ ( t ) = t' - a' - ea't 2. Let P e k [ x ] be squarefree, and suppose that P is special. By Theorem 1.5, there exists tEE such that @(t)= P ( t ) = 0. Let then (t-

x)

T, ,

c = (1 + etx) eKtx)"

12

M. Bronstein

We have C p __

(t' -- x')(1 + 5tx) -- e(t - x ) ( t ' x + x't) (1 + ~tx) 2 x) (t + x)(1 -t- f t x ) £al ( t

(x + 5xt 2 + t + etx 2) l

(1 + 5tx) 2

0,

so c is a constant. By L e m m a 1.3, x is a m o n o m i a l over k, so cek, and we have c + 5ctx = t - x, therefore c-t=O 5ct + 1 = 0

so t 2 = - 5 . Since P ( t ) = 0, we have (p, x 2 + ~ ) ¢ (1). Thus, if P is squarefree and (P, x 2 + e) = (1), then P is normal. Conversely, suppose that P is squarefree and normal. Then every irreducible factor of P is normal. We have (x _ ~ - - e ) ' =

a' + 5a'x 2 = a ' ~ ( x - ~ - - ~ ) ( x

+ x//--~--~)

so x ___x / - £ ~ is special, so (P, x 2 + 5) = (1). is an arc tangent monomial over k if x is a monomial over k, and there exists a ~ k such that either

Definition 1.17. x e K

(i) H ( x ) = a'/(1 + a2), in which case we say that x is an arc tangent over k, and write x = arctan (a). (ii) H ( x ) = a'/(1 - a2), in which case we say that x is an hyperbolic arc tangent over k, and write x = arctanh (a). W e also define the signature o f x to be

{1_, a(x)=

1,

/f if

x = arctan(a) x=arctanh(a).

Since an arc tangent m o n o m i a l over k is primitive over k, Corollary 1.14 implies that any squarefree P e k [ x ] is normal.

Definition 1.18. x e K is a real elementary monomial over k if x is a monomial over k and either a looarithm, exponential, tanoent, hyperbolic tangent, arc tangent, or hyperbolic arc tanoent over k. K is a purely transcendental real elementary extension o f k if there exist x l . . . . . x , , ~ K such that K = k(x 1. . . . . Xm) and x i is a real elementary monomial over k ( x l . . . . . x i - 1 ) f o r each i.

Example L e t f = x + sin (log (x)), and consider the field k = Q(x, tl, t2), where x' = 1, t'l = x ' / x , and t~ = t'~/2(t 2 + 1). Then, k is a purely transcendental real elementary extension of Q(x), and f = x + 2t2/(1 + t2)~k.

Unification of Liouvillian Extensions

13

2. The Hermite Reduction The Hermite reduction (Hermite, 1872) is a well known technique for reducing rational functions, which has been generalized to transcendental Liouvillian functions by Rothstein (1976). In this section, we generalize it to transcendental monomial extensions. The main result of this section can be stated for algebraic curves over monomial extensions, and transcendental extensions can then be seen as the projective line case. This has been done for curves over constant fields by Trager (1984), and for curves over elementary extensions by Bronstein (1990b). The required machinery is however more complicated, so we will treat the transcendental case separately.

The Canonical Representation Let k be a differential field of characteristic 0, and x be a monomial over k. We now define a decomposition of the elements of k(x) which generalizes the representations used by Risch (1969) and Davenport (1986). Let f = A / D ~ k ( x ) , where (A,D)=(1), and D is monic. Let D = D s D N be a split-factorization of D (it is unique by Corollary 1.6). We can then compute P, B, C~k[t] such that deg (B) < deg (Ds), deg (C) < deg (DN), and A B C f:D=P+D +G This decomposition is unique, and we call it the canonical representation of f. We also define f , = P (the polynomial part of f), fs = B/Ds (the special part of f), and f , = C/D N (the normal part of f). We now define some terms which will be used in the rest of this paper.

Definition 2.0. Let f¢k(x), and let f = fp + fs + f , be its canonical representation. We say that (i) (ii) (iii) (iv)

f f f f

is simple if f n has a squarefree (hence normal) denominator, is reduced/ff, = 0, is p-speclal/ff. = 0 and deg (fp) = 0, is p-normal if f s = 0 and deg ( f ,) = O.

In the language of poles, f s k ( x ) is simple if it has only simple poles at normal polynomials, reduced if it has no poles at normal polynomials, p-special if all its poles are at special polynomials, and p-normal if all its poles are at normal polynomials.

The Reduction Define the square-free length of Pek[x] to be the maximal exponent appearing in a squarefree factorization of P (this is the same than the maximal multiplicity among the zeros of P in k). For uek(x), we write SFL(u) for the square-free length of the denominator of u.

14

M. Bronstein

Theorem 2.1. Let k be a differential field of characteristic 0, and x be a monomial over k. Let f ~k(x). Using only the extended gcd algorithm, one can find g, h6k(x) such that g is p-normal, h is simple, and f = g' + h. Furthermore, the denominators of g and h divide the denominator off, and either g = 0 or SFL(g) < SFL(f). Proof. Let f = fp + f~ + f , be the canonical decomposition o f f , and write f . = F/C. We proceed by induction on SFL(f,). Let C = C a C 2...r"+1~.+~ be a squarefree decomposition of C. If 0 < SFL(f,) < 1, then n = 0, so either f , = 0 or C is normal, so f is simple, so g = 0 and h = f satisfy the Theorem. Otherwise, assume the Theorem true for 0 < SFL(g,) < n, and let U = C~..- C,",, V = C,+~. We ask whether there exists G, HEk[x], such that deg (G) < deg (V), and

u

+l-

Expanding on both sides and clearing denominators, we get

F = UVG' - nUV'G + VH

(1)

and reducing modulo F, we find

F-

- nUV'G

(mod V).

(2)

V is normal, so (V, V') = (1), so (V, UV') = (1), so UV' is a unit in k[x]/V, and we can find its inverse by the extended Euclidean algorithm. So we can solve Eq. (2) for G, and replacing in Eq. (1), we find H. Applying the T h e o r e m recursively, we find ~, h~k(x) such that ~ is p-normal, h is simple, the denominators of j and divide UV" and H

UV" Also, either ~ = 0, or SFL(O) < n. Let then g = G/vn + ~ and h = fv + f~ + h. We have f = g' + h, g is p-normal, h is simple, and the denominators of g and h divide the d e n o m i n a t o r of f. If g # 0, then SFL(g) < max (n, SFL(O)) < n < SFL(f). We should note at this point that, although h~ = f~, we m a y have h e 4= fp when d(x) > 2. This behavior comes from the fact that, when d(x) > 2, we can have gp = 0 and (g')p # O. Corollary 2.2. Let k be a differential field of characteristic 0, and x be a monomial over k. Let f 6k(x). Using only the extended gcd algorithm, one can find m >=0, h o . . . . . hm~k(x ) such that each h i is simple, the denominator of each h i divides the

denominator off, and f = h o + h'l + ... h~m). Furthermore, h i is p-normal for i > O. Proof. By induction on SFL(f). If 0 _< S F L ( f ) <=l, then f is simple, so m = 0 and h o = f satisfy the corollary. Otherwise, assume the Corollary true for 0 _< SFL(g) < SFL(f). By Theorem 2.1, we can find g, h~k(x) such that f = g ' + h, g is p-normal, and h is simple. If g = 0, then m = 0 and h o = h satisfy the Corollary. Otherwise SFL(g)< SFL(f), so, applying the Corollary recursively, we find r,g o . . . . . gr6k(x) such that each gj is simple, gj is p-normal for j > 0, and g = go + g'~ + "'" g~r). Let go = gop + gos + go.

Unification of Liouvillian Extensions

15

be the c a n o n i c a l r e p r e s e n t a t i o n of go, a n d m = r a n d for 2 < i < m, hi = g i - 1. W e h a v e f = h o + h'l + for i > 1, a n d h o is simple. Also, the d e n o m i n a t o r of of g, a n d the d e n o m i n a t o r s of g a n d h divide d e n o m i n a t o r of hl divide the d e n o m i n a t o r of f.

+ 1,ho = h + 9'% + g'os, hl = go,, ... h im), h/is p - n o r m a l a n d s i m p l e each g1 divides the d e n o m i n a t o r the d e n o m i n a t o r of f , so the

Example Consider x - t a n (x) t a n (x) 2 "

f-

Let k = Q(x), where x' = 1 (that is ' = d/dx), a n d let t be a m o n o m i a l over k, with H(t) = 1 + t 2. T h e n , t = t a n (x), so

x- t A(t) t 2 - D(t) "

f-

W e h a v e t' = 1 + t 2, s o (t, t') -- (1), s o f p = f s = O, f n = f is the c a n o n i c a l r e p r e s e n t a t i o n o f f . W e get U = 1, V = t, a n d n = 1, so Eq. (1) b e c o m e s

x-

t = t G ' - ( t 2 + 1)G + t H

a n d r e d u c i n g m o d u l o t yields x--G

(modt)

so G = - x, a n d H = - tx. Hence,

W e n o t e that hp = - x while f~ = 0. As a c o n s e q u e n c e , we find If-

x t

ix -

x

x 2

t

2

SO

i x - t a n (x) tan(x) 2 dx =

x

x2

t a n (x)

2

3. Valuations and Residues Let k be a differential field of characteristic 0, a n d x be a m o n o m i a l over k. I n this section, we generalize the n o t i o n s of o r d e r a n d residue of a n e l e m e n t of k(x) at a " p o i n t " of k(x). Let P ~ k [ x ] be irreducible. W e recall t h a t the P-valuation is a m a p v e : k ( x ) ~ Z t 3 { + oo} defined by: (i) for Q e k [ x ] \ { O } ,

v p ( Q ) = n > 0 such t h a t P"IQ a n d P"+IXQ,

16

M. Bronstein

(ii) for A, B e k [ x ] \ { O } , vp(A/B) = ve(A) - v(B), (iii) vp(O) = + ~ . Recall also that the ~-valuation is a map v ~ : k ( x ) ~ Z w { + ~ } defined by vow(A/B) = deg(S) - deg(A) for A, B e k [ x ] \ { O } , and v~o(0) = + ~ . It is easily checked that v e and v~ satisfy the following properties: 1. 2. 3. 4. 5. 6. 7. 8.

for for for for for for for for

Qek[x], vp(Q) > O ~ vp(OQ/Ox) = vp(Q) - 1, A, B e k [ x ] \ {0}, vp(gcd (A, B)) = min (v~,(A), vp(B)), f , gEk(x), ve(fg) = vp(f) + vp(g), f , gek(x), ve( f + g) > min (ve(f), vp(g)), and equality holds if ve(f) ~ vp(g). Qek[x], deg(Q) > O=~ v~(~Q/ax) = v~(Q) + 1, A, B e k [ x ] \{0}, v® (gcd (A, B)) > max (v~(A), Vow(B)), f , gek(x), v~(fg) = v®(f) + v®(g), f , gek(x), v~o(f + g) > min (v~(f), v~(g)), and equality holds if v ~ ( f ) ~ v~(g).

Let P be irreducible. If P is normal, then (P, P') = (1), so v~,(P') = 0. Conversely, if vp(P') = 0, then P is normal by L e m m a 1.10. For f ek(x) and P e k [ x ] irreducible, we call re(f) the order of f a t P, and v®(f) the order o f f at infinity. The following result relates the orders o f f and f ' at points of k(x). It generalizes the well known relations for rational functions. Theorem 3.1. Let k be a differential field of characteristic O, and x be a monomial over k. Let f ek(x). (i) Let P e k [ x ] be normal irreducible. I f ve(f)=O , then ve(f')>=O, otherwise ve(f') = ve(f)-- 1. (ii) Let P e k [ x ] be special irreducible, then ve(f') > re(f). (iii) Suppose that d(x) > 2. I f v ~ ( f ) = O, then v~o(f') > 1 - d(x), otherwise vo~(f') = v® (f) + 1 -- d(x). Proof. Let P e k [ x ] be irreducible, and f ek(x). Let g = fP-v~,ty). Then, f , = vv(f)p, pvp~y)- lg + p~v~f)g,. Write g = AID where (A, D) = (1). re(g) = re(f) + re(P-~P¢,0) = 0, so (P, D) = (1). We have g' = (AD' -- A'D)/D 2, so vv(g') > 0 (since (P, D 2) = (1)). Thus, vv(P~P¢I)g') > vv(f). If ve(f) = 0, then f ' = g', so ve(f' ) > O. (i) Suppose that P is normal, and that ve(f) ~ O. P is normal, so ve(P') = 0, so v~,(v~(f)p,p~p~i~-

lg) =

v~,(f)

-

1, s o

v A f ' ) = v~,(f) - 1.

(ii) Suppose that P is special, and that vp(f) ~ O. P is special and irreducible, so P ' = PQ by L e m m a 1.10, so f ' = pvP~Y)(ve(f)Qg + g'). So vv(f' ) = vv(f) + ve(vv(f)Qg + g'). ve(ve(f)Qg) = vv(Q) > O, and we have shown above that ve(g') > O, so ve(f') > re(f). (iii) Suppose that d ( x ) > 2 . Write f = A I D where (A,D)=(1). Then f ' = ( A D ' - A ' D ) / D z, so v ~ ( f ' ) = 2 d e g ( D ) - d e g ( A D ' - A'D). Let a,x" and d,,x m be the leading terms of A and D respectively. Then, Vo~(f)= m - n, and, since d(x)> 2, the leading term of AD' - A'D is a.md,, Ic(x)x" +m+dtx)- 1 __ na,lc(x)d.,x" +m+dtx)- X = Voo(f)a,dmlc(x)x" +m+d~x)- 1.

Unification of Liouvillian Extensions

17

If v ~ ( f ) = 0, then deg (AD' -- A'D) < n + m + d(x) - 1, so v®(f') > m - n + 1 - d(x) = 1 - d(x). If vo~(f) ~ O, then deg (AD' - A'D) = n + m + d(x) - 1, so voo(f') = v ~ ( f ) + 1 -

d(x).

The following e x a m p l e shows that there is no uniform u p p e r b o u n d on ve(f' ) when v v ( f ) = O: let k = Q a n d let x be a m o n o m i a l over k with x ' = 1 (that is '=O/Ox). P = x ~ k [ x ] is n o r m a l a n d irreducible. Let f = x " + l~k(x). Then, ve(f) = 0, b u t f ' = nx"- 1, so vp(f') = n - 1. Let PEk[x] be n o r m a l a n d irreducible. Define the local ring at P to be

(ge = { f ~k(x) such that r e ( f ) > 0}, a n d let

sJ e = ( f ek(x) s.t. ve(f) > - 1} = { f sk(x) s.t. P f e(ge}. (P) is a m a x i m a l ideal of (ge, so (9el(P) is a field. It is i s o m o r p h i c to k(c0 where ~ek, a n d P ( a ) = 0. F o r any f e ( 9 e, we define the value o f f at p to be i m a g e of f under the canonical m a p from (9e o n t o (gp/(P) = k(a), a n d we d e n o t e it v a l e ( f ) . W e note that (gp/(P) is an algebraic extension of k of degree d = deg (P), so v a l e ( f ) has d conjugates in k. However, the results of this section do n o t d e p e n d on which conjugate is selected. If d(x) > 2, we similarly define the local ring at infinity to be

(900 = { f ~k(x) such that voo(f) > 0}, a n d we let

s4oo = { f e k ( x ) s.t. voo(f) > 1 - d(x)} =

f e k ( x ) s.t. xe(X~_ 1

~ -

( x - 1) is a m a x i m a l ideal of (9o0, so (9~/(x- 1) is a field. It is i s o m o r p h i c to k, and, for any f e ( 9 ~ , we define the value of f a t infinity to be the image o f f u n d e r the canonical m a p from (9oo o n t o (9oo/(X-1)= k, a n d we d e n o t e it val~o(f). W e n o t e that if we write f e k ( x ) as a n x n q-- . . . -}- a 0

f =b~x~ + . . _ + b o where ai, bjek, a, ~ O, a n d bm :~ O. Then, if f e ( 9 ~ , m >= n, a n d val~o(f) is given by a,

val~(f) =

if

m = n

if

m>n.

b,,' 0,

Definition 3.2. Let P ~ k [ x ] be normal and irreducible, and define the residue at P to be the map r e : d e ~ Ce/(P) given by r e ( f ) = v a l e ( f PIP'). Since P is n o r m a l , ve(P' ) = 0, so P'6Cp. Also, f P ~ C p whenever f ~ C e , so re is well defined. It is easily checked that for f , g6~¢ e, a n d c~k, we have re(cf + g) =

cze(f) + re(g). D e f i n i t i o n 3.3. Suppose that d ( x ) > 2. Define then the residue at infinity to be the map z ~ :d oo~ (9 00/(x - 1) given by z 00( f ) = val oo( f /lc(x)x d~x~- 1).

18

M. Bronstein

(f/Ic(x)x d(~)- 1)e(9~o whenever f e t i d , so Zoo is well defined. It is easily checked that for f , ged~o, a n d cek, we have zo~(cf + #) = c ~ ( f ) + ~o(9). L e m m a 3.4. (i) Let P~k[x] be normal and irreducible, and f ss~ e. Then, ze(f) ¢O'~ve(f) = - 1. (ii) Suppose that d(x)> 2, and let f edo~. Then, z ~ o ( f ) ¢ O ¢ * , v ~ ( f ) = 1 - d ( x ) .

Proof. (i) S u p p o s e that P is n o r m a l a n d irreducible, fes~cp, so v p ( f ) > - 1. If vp(f) = - 1, then Ve(f(P/P')) = 0, so ze(f) ~ 0. If vp(f) > 0, then vp(f(P/P')) > O, so zp(f) = O. (ii) S u p p o s e that d(x) > 2. f ~ o o , so v ~ ( f ) > 1 - d(x), If v ~ ( f ) = 1 - d(x), then vo~(f /lc(x)xa~X) - 1) = O, so ro~(f) 4: O. If vow(f) > 1 - d(x), then vo~(f/lc(x)x a¢~)- 1) > O, so zoo(f) = O. The next L e m m a generalizes a key p r o p e r t y of the residues of c o m p l e x differentials to m o n o m i a l extensions. L e m m a 3.5. Let u~k(x)\{O}. (i) Let PEk[x] be normal and irreducible. Then, (u'/u)E~cp, and ze(u'/u ) = Vp(U). (ii) Suppose that d(x) > 2. Then, (u'/u)~doo, and zoo(u'/u) = voo(u).

Proof. (i) By T h e o r e m 3.1, ve(u'/u) > - 1, so (u'/u)es¢p. Let w = uP -~'~. T h e n u'

P w' P~P~)w - ve(U)P + -W-

(P~Pt")w)'

u SO Zp

= Vp(U)Zp

"~ Zp

.

Vp(W) = 0, so, by T h e o r e m 3.1, vp(w'/w)> O, so, by L e m m a 3.4, ze(w'/w)= 0. Also, zp(P'/P) = vale(l) = 1, so re(u'/u) = vp(u). (ii) S u p p o s e that d(x)> 2. By T h e o r e m 3.1, v~(u'/u)> 1 - d ( x ) , so ( u ' / u ) e d ~ . Let w = ux ~ 1 . Then,

u' U

SO

zoo

(x V®~Ulw)' -

XV°°(u)w

(Uu)

x' =

= vo~(u)~oo

voo(u)-

X

w' +

+%

-

W

(Ww) •

vow(w) = 0, so, by T h e o r e m 3.1, vo~(w'/w) > 1 - d(x), so, by L e m m a 3.4, ze(w'/w) = O. Also, zo~(x'/x)= val~(x'/lc(x)x d(x)) = 1, so zo~(u'/u)= voo(u). L e m m a 3.6. Let PEk[x] be normal and irreducible, ge(ge, Dek[x], and f = 9/D. I f ve(D) = 1, then zp(f) = vale(o/D' ).

Proof. S u p p o s e that vp(D) = 1. Then, vp(f) = v~,(9) - 1 > -- 1, so f e d e , is defined. Let Q = D/PEk[x], then vp(Q)= 0, a n d Q'P =

D'P - P'D D'P - P'D p2 P p

so zp(f)

Unification of Liouvillian Extensions

We have

P fP'

g-g O'

19

(D ') D'

'

f D ' P - P'D

=gt

~

=g\

~

]

P

"~

f ..,,.

1

"~

gQ'P

D~p,)=gt~"Q-~-'):~ '

Since ve(D) = ve(P) = 1 and P is normal, T h e o r e m 3.1 implies that vp(gQ'P/QD'P' ) = Ve(g) + vp(Q') + 1 > 0, so vale(fP/P') - (g/D') = 0, so vale(fP/P') = vale(g/D'), so

rp(f) = valp(g/D'). As a corollary, we get a way of computing the rp'S at the normal P's, when f is simple. Theorem 3.7. Let f ek(x), and let f = f p + fs + f . be its canonical representation,

where f , = G/D. Let z be an indeterminate over k. Define R6k[z] by: R(z) = resultantx(G - zD', D). I f f is simple, then the roots of R in k are the re(f) (and their conjugates over k) at all the normal irreducible P's in k[x] where f has a pole. Proof. If f = f p +fs + (G/D) is simple, then D is squarefree. F o r any n o r m a l irreducible Pek[x], vp(fp + fs)> O, so re(fp + f s ) = 0, so z e ( f ) = re(G/D), so the normal poles of f are exactly the n o r m a l zeros of D. Let P1 .... , P,, be all the normal irreducible polynomials of k[x] where f has a pole, and let q = re,(f) for i = 1 ..-m. F o r each i, let ~,1 . . . . . ~,n, be the zeros of P~ in k. The ~i,~'s are all distincts since the P~'s are irreducible over k. Let fi,j(f) = T,(. . . . j)(f). Since the f~4's are the conjugates of the q ' s in k over k, we need to prove that the roots of R(z) are the fi,fs. Since D is squarefree, we have hi O

= [I 1-i i=1 j - 1

SO m] hi

R(z) = c

1~ G(~id) -- zD'(~i.J) i=lj=l

where cek\{0}, so the roots of R(z) are

G(o~i,j) = v a l , . . . . j ) ( G ) ziJ - D'(ohj ) D' for i = 1 ...m and j = 1...hi. By L e m m a 3.6, zi4= z(. . . . j)(f,), so the roots of R(z) are the rl,j s.

4. Integration in Closed F o r m

Let k be a differential field of characteristic 0, C be the constant field of k, and x be a m o n o m i a l over k. We apply the results of the previous sections to the p r o b l e m

20

M. Bronstein

of deciding whether an element of k(x) has an integral in an elementary extension of k(x). We present in this section techniques that can be applied to arbitrary monomials, and that can prove, in some cases, that no such integral exists. Let f ~ k(x). F r o m Liouville's theorem (Risch, 1969, p. 171), f has an elementary integral over k(x) if and only if there exist v~k(x), uiECk(x), and ci~C such that

f =v' + ~ ci u;. i= 1

(E 0

Ui

We note that if (E 0 has a solution, then it has one where (c~ .... , cm) are linearly independent over Q. Using Theorem 2.1, we can assume that our integrand f e k ( x ) is simple.

The Resultant Criterion Lemma 4.1. l f f ~k(x) is simple, then v is reduced for any solution of(E1).

Proof. Let f = v' +

ci i be any solution of(E1). Suppose that vi±(v)< 0 for some i=l

Ui

normal irreducible Pek[x]. By Theorem 3.1, vi±(v')= vi,(v ) - 1 < - 1, while vi,(u'i/ui) = vi±(u'i)- ve(ui) > - 1. Hence, vi±(f) = vi,(v') < - 1, in contradiction with f simple. Hence vi,(v) > 0 for any normal irreducible Pek[x], so v is reduced. Lemma 4.2. I f f is simple then for any solution of (El) and any normal irreducible

Pek[x], we have ri,(f)= ~ civi,(ul). i=1

Proof. Let f = v ' + cizi,

ci -~ be any solution of (E0. We have zi,(f)=zi,(v')+

. vi±(v)> 0 by L e m m a 4.1, so vi,(v') > 0 by Theorem 3.1, so zi,(v') = 0 by

i=l

m

Lemma 3.4, and zi,(u'i/ui) = vi,(ui) by L e m m a 3.5. Thus, zi,(f) = ~ ClVl,(Ui). i=1

As a consequence, we get the following generalization of Rothstein's Theorem (1976), which either proves that a simple element of k(x) has no elementary integral over k(x), or gives us all the new logarithms that come from the normal part of the integrand. Theorem 4.3. Let k be a differential field of characteristic O, and x be a monomial

over k. Let f ~k(x) be simple, and let f =fp + fs + f , be its canonical representation, where f . = G/D. Let z be an indeterminate over k, and define Rek[z] by R(z) = resultantx(G - zD', D). If(E1) has a solution, then R(z) = tiP(z) where tick and Pek[z] is monic and has constant coefficients. I f this is the ease, let then g=

~

alog(gcd(G-aD',D)).

R(a) = 0

Then, h = f - y' is reduced. Proof. Suppose that (E 0 has a solution. Then, by L e m m a 4.2, zp(f) is a constant for any normal irreducible P~k[x], so, by Theorem 3.7, the roots of R(z) must be

U n i f i c a t i o n of Liouvillian E x t e n s i o n s

21

all constants, so R(z) = tiP(z), where P(z) = I~ (z - ~) is m o n i c a n d has c o n s t a n t coefficients. R(~)= o Suppose that this is the case, a n d for each r o o t e of R(z) let G, = gcd (G - eD', D)e k[x]. Let then g = ~ elog(G~), a n d h = f - 9 ' . Since e ' = 0, we have R(a) = 0

h=f,+f,+f,-

~,

c~--.

Let P e k [ x ] be n o r m a l irreducible. Then, v~,(f, +fs)>= 0 by definition of the canonical representation, so ze(fp + f s ) = O. S u p p o s e first that PXD. Then, ( P , D ) = (1), so vp(f,)>= O. Let ~ be any r o o t of R(z). Then, (P, G~) = 1, so ve(G'fG~) > O, so vp(h) >__0. Suppose now that PID. Since f is simple, D is squarefree, so vp(D)= 1. But (G,D) = (1) by the definition of the c a n o n i c a l representation, so (P, G ) = (1), so vp(G) = 0, so v p ( f , ) = - 1 , so z e ( f , ) 4 =0, and, by L e m m a 3.6, r e ( f , ) = valp(G/D'). F u r t h e r m o r e , r e ( f ) = - 1 a n d z e ( f ) = ze(f,). By T h e o r e m 3.7 there is a r o o t % of R(z) such that % = z e ( f ) = valp(G/O'). Thus, vale(G - % D ' ) -- 0, so ve(G - % D ' ) > O, so PI(G - % D ' ) , so PIG~o. But D is squarefree, so G~o is squarefree, so ve(G~o ) = 1, so Vp(%G'~o/G~o ) > - 1 , so by L e m m a 3.6, T p ///0 ~ 0 G - 'I~ ° ~ = v a l e

t

a~o)

%

\

= G(O.

a~o)

Let e be a r o o t of R(z), and s u p p o s e that c~4=%. Then, valp(G/D')4=c~, so vale(G - ~D') ¢ 0, so ve(G - eD') = 0, so (P, G - eD') = (1), so (P, 6,) = (1), so

Vp(O~G'~/G~) > O. Thus, vp(g') >= - 1, and rp(g') = % = rp(f). So vp(h) = vp(f - g') > - 1, so h E d p a n d zp(h) = zp(f) - zp(ff') = O, so vp(h) >=O. Hence vp(h) >_ 0 for any n o r m a l irreducible P ~ k [ x ] , so h is reduced.

The Polynomial Reduction Theorem 4.4. Let k be a differential field of characteristic O, and x be a monomial over k such that d ( x ) > 2 . Let P e k [ x ] . Then we can .find Q e k [ x ] such that deg (P - Q') < d(x).

Pro@

Let d = d(x) a n d suppose that d > 2. Let

x' = H(x) = ad xd + ... + al x + ao where aiek, a n d a n = lc(x) 4= O. Let P e k [ x ] . W e p r o c e e d by i n d u c t i o n on n = deg(P). If n < d, then Q = 0 satisfies the Theorem. Otherwise, assume the T h e o r e m true for deg(P) < n, a n d write P = b,x" + ... + bo where blek, a n d b, 4=0. Let b, c--

a n d / 5 = p _ ( c x , - d + 1),. W e have

(n - d + 1)lc(x)

22

M. Bronstein

ff = p _ (Cx,-d+

1),

=

p _ C,x,-d+ 1 + c(n -- d + 1)xn-dH

= b,x" + ... + bo - c'x "-a+ 1 b, (lc(x)x" + aa_l x " - I + "'" + aox"-d). lc(x) Since d > 1, we have d e g ( P ) < n , so we can recursively find Q~k[x] such that d e g ( / ~ - Q ' ) < d . Let then Q = c x "-d+l + 6 . We have P - Q ' = f i - Q ' , so deg(P - Q') < d. Suppose that d(x) > 2 and let f ~ k ( x ) be an integrand. Using Theorems 2.1, 4.3, and 4.4, we can assume that f is reduced and that deg(fp) < d(x). The following are analogues at infinity of Lemmas 4.1 and 4.2. Lemma 4.6. Let f ~k(x) be reduced, and suppose that d e g ( f p ) < d(x). Suppose also that d(x) > 2. Then, v is p-special for any solution of (EO. u'

Proof. Let f = v' +

ci--' be any solution of (El). By L e m m a 4.1, v is reduced. i=1

Ui

Suppose that voo(v) < 0. Then, by Theorem 3.1, voo(v') =voo(v) + 1 - d(x) < - d(x), while voo(u'i/ui) = voo(u'i) - voo(ul) > - d(x). Hence, voo(f) = v~(v') < - d(x). But f = f p + f ~ , and voo(f~)>O by definition of the canonical representation, while - d(x) < voo(fp) = - deg(fv) < 0. Thus voo(f) > - d(x), contradiction. Thus, voo(v) > O, so v is p-special. Lemma 4.7. Let f sk(x) be reduced, and suppose that deg(fp) < d(x). Suppose also

that d(x)> 2. Then, zoo(f)= ~ civoo(ui) for any solution of(E1). i=1

S" c i ui be any solution of (E0. We have zoo(f)= zoo(v')+ Proof. Let f = v' + z., i=1

Ui

clzoo(u'i/ul), voo(v)>O by Lemma 4.6, so v o o ( v ' ) > l - d ( x )

i=l

by Theorem 3.1, so

zoo(v') = 0 by Lemma 3.4, and zoo(u'i/ui) = voo(ui), by L e m m a 3.5. Thus, zoo(f) = c, v oo(u,),

i=

We can now prove an analogue at infinity of the resultant criterion. Theorem 4.8. Let k be a differential field of characteristic 0, and x be a monomial over k such that d(x)>= 2. Let f 6k(x) be reduced, and suppose that d e g ( f p ) < d(x). If(E1) has a solution, then

where b is the coefficient of x dtx)- 1 in f p. Proof. Let f = v'+ ~ ci u~ he any solution of (El). By L e m m a 4.7, zoo(f)= i=1

Ui

i=1

civoo(ul) is a constant. But f = f v + f~, so zoo(f)= zoo(fv)= valoo(fe/Ic(x) xatx~-l) =b/lc(x).

Unification of Liouvillian Extensions

23

As a corollary, an expression of the form

S (f(x) tan (g(x)) + h(x))dx where f, g, h~C(x) is elementary if and only if f = cg' for some cEC in which case the integral is log (1 + tan (g(x)) 2) + ~ h(x)dx = - c log (cos (g(x))) + ~ h(x)dx.

5. Conclusions

We have presented a framework in which most of the literature on symbolic integration can be presented in a unified way, avoiding duplication of cases. Also, working with monomial extensions provides more insight into the special cases, for instance, it justifies why the only ideals to consider separately when bounding degrees in the Risch-Norman algorithm are (x) in the exponential case, and (x z + 1) in the tangent case (Geddes and Stefanus, 1989) (those are the only prime ideals of k[x] generated by special polynomials). An immediate application is the completion of a tangent and arc tangents cases for the Risch algorithms, which will appear in a sequel to this paper. There remains several open questions about monomial extensions, for which answers would allow even more general algorithms, mostly about better characterisations of special monic irreducible polynomials. For example, is there a finite number of them? And, in the affirmative, can we bound their number, and is there a procedure to generate them? This paper answers them only for real elementary extensions. Acknowledgements. I would like to thank John Abbott and Michael Singer for their careful reading of the drafts of this paper. Their numerous corrections and suggestions have contributed greatly to its present form.

References Bronstein, M: The transcendental Risch differential equation. J. Symb. Comput. 9, 49-60 (1990a) Bronstein, M.: Integration of elementary functions. J. Symb. Comput. 9, 117 173 (1990b) Cherry: Integration in finite terms with special functions: the error function. J. Symb. Comput. 1, 283-302 (1985) Cherry: Integration in finite terms with special functions: the logarithmic integral. SIAM J. Comput. 15, 1 21 (1986) Davenport, J. H.: Int6gration formelle. IMAG Research Report No. 375, Grenoble 1983 Davenport, J. H.: The Risch differential equation problem. SIAM J. Computing 15, 903 918 (1986). Also Technical Report 83-4, Department of Computer and Information Sciences, University of Delaware Geddes, K. O., Stefanus, L. Y.: On the Risch Norman integration method and its implementation in MAPLE. In Procedings ISSAC'89, pp. 212 217 (1989) Hermite, E.: Sur l'intggration des fractions rationelles, Nouvelles Ann. Math6matiques 2me S6re ll, 145-148 (1872) Knowles, P.: Symbolic integration in terms of error functions and logarithmic integrals. Ph.D. thesis, North Carolina State University 1986

24

M. Bronstein

Risch, R.: The problem of integration in finite terms. Trans. Am. Math. Soc. 139, 167-189 (1969) Risch, R.: The solution of the problem of integration in finite terms. Bull. Am. Math. Soc. 76, 605-608 (1970) Rosenlicht, M.: Integration in finite terms. Am. Math. Monthly 79, 963-972 (1972) Rothstein, M.: Aspects of symbolic integration and simplification of exponential and primitive functions. Ph.D. thesis, University of Wisconsin, Madison 1976 Singer, M. F.: Liouvillian solutions of linear differential equations with Liouvillian coefficients. J. Symb. Comput. (to appear) 1988 Trager, B: Algebraic factoring and rational function integration. In: Proceedings SYMSAC'76, pp. 219-226 (1976) Trager, B. M.: Integration of algebraic functions. Ph.D. thesis, Department of EECS, Mass. Inst. of Tech. 1984 Received September 27, 1989; revised version February 6, 1990