Complete Reduction for Derivatives in a Transcendental Liouvillian Extension This research was funded in part by the National Key R&D Programs of China (No. 2023YFA1009401), the Natural Science Foundation of China (No. 12271511, No. 12201065, No. 12101105), the Austrian Science Fund (FWF) 10.55776/PAT1332123 and by the Natural Science Foundation of Fujian Province of China (No. 2024J01271). This work was also supported by the International Partnership Program of Chinese Academy of Sciences (Grant No. 167GJHZ2023001FN). Shaoshi Chen, Hao Du, Yiman Gao, Hui Huang, Wenqiao Li, Ziming Li Abstract Transcendental Liouvillian extensions are differential fields, in which one can model poly-logarithmic, hyperexponential, and trigonometric functions, logarithmic integrals, and their (nested) rational expressions. For such an extension ( F , ′ ) (F,\,^{\prime}) with the subfield C C of constants, we construct a complementary subspace W W for the C C -subspace of derivatives in F F , and develop an algorithm that, for every f ∈ F f\in F , computes a pair ( g , r ) ∈ F × W (g,r)\in F\times W such that f = g ′ + r f=g^{\prime}+r . Moreover, f f is a derivative in F F if and only if r = 0 r=0 . The algorithm enables us to determine elementary integrability over F F by computing parametric logarithmic parts, and leads to a reduction-based approach to constructing telescopers for functions that can be represented by elements in F F . a MMRC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing (100190), China b School of Mathematical Sciences, University of Chinese Academy of Sciences, Chinese Academy of Sciences, Beijing (100049), China c School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing (102206), China d Johannes Kepler University Linz, Research Institute for Symbolic Computation (RISC), Altenberger Straße 69, 4040, Linz, Austria e School of Mathematics and Statistics, Fuzhou University, Fuzhou (350108), China Email: schen@amss.ac.cn , haodu@bupt.edu.cn , ymgao@risc.jku.at , huanghui@fzu.edu.cn , liwenqiao@amss.ac.cn , zmli@mmrc.iss.ac.cn Keywords: Additive decomposition, Complete reduction, Creative telescoping, Elementary integration, In-field integration, Liouvillian extension, Risch equation, Symbolic integration 1 Introduction A classical topic of computer algebra is to express indefinite integrals in closed forms. Historical developments and fundamental results on this topic are reviewed in [ 31 ] . On the computational side, the most systematic developments are due to Risch [ 32 , 33 ] and researchers who have clarified, improved, extended and implemented Risch’s algorithm [ 34 , 17 , 36 , 18 , 8 , 9 , 10 , 30 ] . For an elementary function, Risch’s algorithm determines whether it has an elementary integral, and computes such an integral if there exists one. Example 1.1 . Let \displaystyle f(x)=\frac{x\log(x)^{3}+1}{x\log(x)} and \displaystyle g(x)=\dfrac{x\log(x)^{3}+1}{(x+3)\log(x)}. By Risch’s algorithm, \int f=x\log(x)^{2}-2x\log(x)+2x+\log(\log(x))\quad\text{and}\quad\int g=\int\dfrac{x\log(x)^{3}+1}{(x+3)\log(x)}. The algorithm yields an elementary integral of f , and reveals that g has no elementary integral. The most basic routine in Risch’s algorithm is the Hermite-Ostrogradsky reduction for rational functions [ 26 , 29 ] . We refer to [ 10 , Chapter 2] and [ 23 , Chapter 11] for its modern presentations. Example 1.2 . Let C be a field of characteristic zero. For every element f\in C(x) , the Hermite-Ostrogradsky reduction computes g,s\in C(x) such that f=g^{\prime}+s, where ′ stands for the usual derivation d/dx , and s is a proper fraction with a squarefree denominator. Moreover, f\in C(x)^{\prime} if and only if s=0 , where C(x)^{\prime} denotes the set of derivatives in C(x) . Let S_{x} be the set \{s\in C(x)\mid\text{$s$ is proper and has a squarefree denominator}\} . Then S_{x} is a C -linear subspace of C(x) and C(x)=C(x)^{\prime}\oplus S_{x} . The projection from C(x) to S_{x} with respect to the direct sum is a complete reduction for C(x)^{\prime} in C(x) according to [ 27 , Definition 5.67] . In this paper, complete reductions are for images of linear operators. The following definition is equivalent to [ 27 , Definition 5.67] , but more convenient for the present paper. Definition 1.3 . Let U be a C -linear space and \rho be a linear operator on U . Another linear operator \phi on U is called a complete reduction for the pair (U,\rho) if U=\operatorname{im}(\rho)\oplus\operatorname{im}(\phi) and \phi is the projection from U to \operatorname{im}(\phi) with respect to the direct sum. Another equivalent definition is that a linear operator \phi on U is a complete reduction for (U,\rho) if \phi^{2}=\phi and \ker(\phi)=\operatorname{im}(\rho) . The next definition describes how a complete reduction decomposes an element additively. Definition 1.4 . Let \phi be a complete reduction for (U,\rho) and u\in U . We call \phi(u) the remainder of u with respect to \phi . Let v\in U be such that u=\rho(v)+\phi(u) . Then (v,\phi(u)) is called a reduction pair of u with respect to \phi or an R-pair with respect to \phi for brevity. The Hermite-Ostrogradsky reduction not only induces a complete reduction for (C(x),\,^{\prime}) , but also yields an algorithm for computing the corresponding R-pairs. An algorithm based on the reduction is developed in [ 3 ] to construct telescopers for bivariate rational functions. It avoids the costly computation of certificates, and has motivated a rapid development of complete reductions and additive decompositions in various settings. Example 1.5 . Let h be a nonzero rational function in C(x) , and U be the space spanned by the hyperexponential function \exp(\int h) over C(x) . For every element f\in U , the Hermite reduction for hyperexponential functions in [ 4 ] is a complete reduction for (U,\,d/dx) . Recall that a derivation {}^{\prime}:R\rightarrow R on a commutative ring R is an additive map satisfying the usual Leibniz’s rule: (ab)^{\prime}=ba^{\prime}+ab^{\prime} for all a,b\in R . The pair (R,\,^{\prime}) is called a differential ring and a differential field if R is a field. The set \{c\in R\mid c^{\prime}=0\} forms a subring whose elements are called constants . In particular, the subring becomes a subfield if R is a field. Let (R,\,^{\prime}) be a differential ring whose subring C of constants is a field. Then R is a C -linear space. Complete reductions have been established for such differential rings with instances of R including the field of differential fractions [ 6 ] , the field of algebraic functions [ 15 ] , (sub)rings of D-finite functions [ 16 , 37 , 12 ] , exponential towers [ 22 ] and primitive towers [ 20 ] . A complete reduction for the pair (C(x),L) is developed in [ 5 ] , where L denotes a linear differential operator. The reader is referred to [ 7 , 14 ] for complete reductions related to symbolic summation. A complete reduction for (R,\,^{\prime}) decomposes an element f as g^{\prime}+r for some g,r\in R such that r is minimal with respect to a partial ordering defined in [ 22 , Section 1.1] . In particular, f is a derivative in R if and only if r=0 . So a complete reduction for (R,\,^{\prime}) is an additive decomposition in the sense given by [ 13 , 21 ] . It provides us with an alternative and possibly more informative way to express integrals. Example 1.6 . Let f and g be the same as in Example 1.1 . They can be regarded as elements of {\mathbb{Q}}(x,\log(x)) , which is a differential field with derivation {}^{\prime}=d/dx . The complete reduction in [ 20 ] yields f(x)=h(x)^{\prime}+\frac{1}{x\log(x)}\quad\text{and}\quad g(x)=h(x)^{\prime}+\frac{1}{(x+3)\log(x)}-\frac{3\log(x)^{2}}{x+3}, where h(x)=x\log(x)^{2}-2x\log(x)+2x . Note that f(x) is the sum of a derivative in {\mathbb{Q}}(x,\log(x)) and a remainder 1/(x\log(x)) . The remainder has an elementary integral \log(\log(x)) . In general, the elementary integrability of remainders in logarithmic extensions can be determined by computing parametric logarithmic parts by [ 20 , Theorem 5.3] . On the other hand, g(x) is the sum of a derivative in {\mathbb{Q}}(x,\log(x)) and a remainder, which is not elementarily integrable. Unlike in Example 1.1 , the complete reduction renders us a maximal integrable part h(x) of g(x) in {\mathbb{Q}}(x,\log(x)) . The above two decompositions of f and g can also be obtained from the algorithms in [ 13 , 21 ] . Now, let us define transcendental Liouvillian extensions. Such extensions are more general than transcendental elementary extensions (see [ 10 , Definition 5.1.4] ), and do not contain any complicated reduced elements (see [ 10 , Definition 3.5.2] ). Definition 1.7 . Let C be a field of characteristic zero. A differential field C(t_{1},\ldots,t_{n}) with derivation ′ is called a transcendental Liouvillian extension of C if (i) t_{1},\ldots,t_{n} are algebraically independent over C , (ii) either t_{i}^{\prime} or t_{i}^{\prime}/t_{i}\in C(t_{1},\ldots,t_{i-1}) for all i\in\{1,2,\ldots,n\} , (iii) C is the subfield of constants in C(t_{1},\ldots,t_{n}) . Our initial attempts to inductively construct a complete reduction for derivatives in a transcendental Liouvillian extension revealed the necessity of a more general inductive framework (see Example 3.1 ). A similar phenomenon also occurs in the inductive proof of the main theorem in [ 32 ] . In fact, the main theorem has two assertions. The first is of interest in elementary integration, and the second serves to facilitate the proof. In the second assertion, Risch writes down a differential equation y^{\prime}+fy=\sum_{i=1}^{m}c_{i}g_{i}, (1) where f and the g_{i} ’s belong to a differential field F , and the c_{i} ’s are constants of F . The equation has been called the (parametric) Risch differential equation in the literature. To develop complete reductions for symbolic integration, we define Risch operators using the homogeneous part of ( 1 ). Definition 1.8 . Let (F,\,^{\prime}) be a differential field and h\in F . The map \begin{array}[]{cccc}{\mathcal{R}}_{h}:&F&\rightarrow&F\\ &y&\mapsto&y^{\prime}+hy.\end{array} is called the Risch operator associated to h . The letter “ f ” is replaced with “ h ” in the above definition because f usually stands for an arbitrary element of a differential field in this paper. Risch operators are linear over the subfield of constants in F . In particular, {\mathcal{R}}_{0} is the derivation operator on F . Assume that there is a complete reduction \phi_{f} for (F,{\mathcal{R}}_{f}) , where f is given in the left-hand side of ( 1 ). Then each g_{i} in the right-hand side of ( 1 ) has an R-pair (p_{i},q_{i}) with respect to \phi_{f} . Therefore, ( 1 ) can be rewritten as {\mathcal{R}}_{f}(y)=\sum_{i=1}^{m}c_{i}\left({\mathcal{R}}_{f}(p_{i})+q_{i}\right) , which is equivalent to {\mathcal{R}}_{f}\left(y-\sum_{i=1}^{m}c_{i}p_{i}\right)=\sum_{i=1}^{m}c_{i}q_{i}. It follows from Definition 1.3 that there exist y\in F and c_{1},\ldots,c_{m}\in C such that ( 1 ) holds if and only if \sum_{i=1}^{m}c_{i}q_{i}=0 and {\mathcal{R}}_{f}\left(y-\sum_{i=1}^{m}c_{i}p_{i}\right)=0 . The first constraint leads to a linear system over the subfield C of constants in F , and the second amounts to determining the kernel of {\mathcal{R}}_{f} . In other words, the complete reduction finds all solutions of ( 1 ) in F by solving a linear algebraic system over C and y^{\prime}+fy=0 in F . Let F_{n}=C(t_{1},\ldots,t_{n}) be a transcendental Liouvillian extension of C with n>0 , and set F_{0}=C . In this paper, we construct a complete reduction \phi_{n,h} for (F_{n},{\mathcal{R}}_{h}) , where h\in F_{n} , in the sense that we fix a complement of \operatorname{im}({\mathcal{R}}_{h}) in F_{n} with the corresponding projection \phi_{n,h} from F_{n} to the complement, and develop an algorithm for computing R-pairs with respect to \phi_{n,h} . Setting h=0 yields a complete reduction \phi_{n,0} for (F_{n},\,^{\prime}) . In doing so, we generalize the complete reductions in Examples 1.2 , 1.5 , and those in [ 22 , 20 ] in one fell swoop. Our construction is based on the assumption that there is a complete reduction for (F_{n-1},{\mathcal{R}}_{z}) for all z\in F_{n-1} . It proceeds in three steps: Outline 1.9 . 1. Reduce the problem of constructing a complete reduction for (F_{n},{\mathcal{R}}_{h}) to that for (F_{n},{\mathcal{R}}_{\xi}) , where \xi\in F_{n} is t_{n} -normalized (see Proposition 3.3 ). 2. Reduce the problem of constructing a complete reduction for (F_{n},{\mathcal{R}}_{\xi}) to that for (R_{n},{\mathcal{P}}_{\xi}) , where R_{n} is either F_{n-1}[t_{n}] or F_{n-1}[t_{n},t_{n}^{-1}] , and {\mathcal{P}}_{\xi} is the companion operator of {\mathcal{R}}_{\xi} (see Definition 3.4 and Proposition 3.5 ). 3. Construct a complete reduction for (R_{n},{\mathcal{P}}_{\xi}) (see Theorem 7.1 ). The idea for the first two steps can be traced back to [ 18 , Condition b) on page 905] and [ 10 , Section 6.1] , in which the problem of solving Risch differential equations in a monomial extension is transformed to that in its subring of reduced elements. Similar transformations are also given in [ 24 , 11 ] , which can, respectively, be viewed as a differential analogue and a generalization of the minimal decomposition for hypergeometric terms in [ 2 , 1 ] . The idea for step 3 is to construct an auxiliary subspace A_{\xi} such that R_{n}=\operatorname{im}({\mathcal{P}}_{\xi})+A_{\xi} , and compute an echelon basis of \operatorname{im}({\mathcal{P}}_{\xi})\cap A_{\xi} . The basis enables us to construct a complement of \operatorname{im}({\mathcal{P}}_{\xi}) in a dual manner (see Section 2.3 ). Although this idea has appeared in [ 4 , Section 4.1] , [ 22 , Chaper 4] and [ 20 , Section 3] in one form or another, a comprehensive generalization is required, because F_{n} is more involved than the differential fields appearing therein. Step 3 is different from the way to handle elements of R_{n} in Risch’s algorithm. It is also the most technical part in this paper. Applications of the complete reduction in Theorem 7.1 include two algorithms: one is for in-field integration, and the other for elementary integration. In addition, the complete reduction leads to a reduction-based approach to constructing telescopers (up to a given order) for functions that can be interpreted as elements in a transcendental Liouvillian extension. The next example illustrates an application of the complete reduction to in-field integration. Example 1.10 . Let f=\dfrac{x}{1+\exp(x)}\cdot\exp\left(\dfrac{x}{1+\exp(x)}\right), which can be regarded as an element in the transcendental elementary extension {\mathbb{C}}(x,t,y) of {\mathbb{C}} , where t=\exp(x) and y=\exp\left(\dfrac{x}{1+\exp(x)}\right) . In fact, f=\dfrac{xy}{1+\exp(x)} , which belongs to {\mathbb{C}}(x,t) . We determine whether f has an integral in the extension {\mathbb{C}}(x,t,y) . The complete reduction in this paper confirms that f is in-field integrable, and finds that \int f=-\bigl(1+\exp(-x)\bigr)\cdot\exp\left(\dfrac{x}{1+\exp(x)}\right). The int() command (with option method=_RETURNVERBOSE ) in maple 2023 leaves the integral unevaluated, and so does Integrate[] command in mathematica 14.3. Indeed, computing this integral amounts to handling a special case in Risch’s algorithm carefully. It corresponds to Proposition 6.13 (ii). Details are given in Example 7.3 . In [ 30 , Chapters 3 and 4] , Raab provides several building blocks that were either missing or incomplete for the description of Risch’s algorithm in [ 10 ] , and presents a method for computing elementary integrals over an admissible differential field with some mild restrictions. Such fields are more general than transcendental Liouvillian extensions. Raab’s method needs all the ingredients from Risch’s algorithm in the transcendental case. Our algorithm for elementary integration is based on the complete reduction and some special structure of remainders described in Proposition 8.4 . It merely needs to solve the problem of recognizing logarithmic derivatives [ 10 , Section 5.12] and parametric logarithmic derivative problem [ 10 , Section 7.3] . The last example of this section is for definite integration. Example 1.11 . By the complete reduction, we find that (k+1)\sigma_{k}-k is a minimal telescoper for both R(k) and I(k) , where \sigma_{k} stands for the shift operator k\mapsto k+1 , R(k)=\int_{0}^{\frac{\pi}{2}}\cos(2kx)\log(\sin(x))~dx\quad\text{and}\quad I(k)=\int_{0}^{\frac{\pi}{2}}\sin(2kx)\log(\sin(x))~dx. The telescoper, together with the corresponding certificates, yields that R(k+1)-\frac{k}{k+1}R(k)=0\quad\text{and}\quad I(k+1)-\frac{k}{k+1}I(k)=\displaystyle\frac{(-1)^{k}-2k-1}{4k(k+1)^{2}}, which help us express R(k) and I(k) in closed forms. Details are given in Example 8.8 . Preliminary experiments in maple 2021 illustrated that our complete reduction were more efficient than the int() command in maple , when both were applied to the derivatives of elements in some transcendental elementary extension of C(x) . In particular, a significant speed-up was observed when integrands are derivatives of polynomials in the generators of such an extension (see Tables 4 and 6 in Section 9 ). The rest of this paper is organized as follows. In Section 2 , we present basic terminologies in symbolic integration and a dual description of subspaces. Steps 1 and 2 in Outline 1.9 are taken in Section 3 . The induction base and hypothesis are given in Section 4 . Step 3 is carried out in Section 5 for primitive extensions and Section 6 for hyperexponential extensions, respectively. In Section 7 , we complete the induction and present examples for in-field integration. The complete reduction is applied to elementary integration and creative telescoping in Section 8 . Experimental results on the efficiency of the complete reduction are presented in Section 9 . Concluding remarks are given in Section 10 . In the appendix, we present the pseudo-code descriptions of algorithms based on some constructive proofs in Sections 5 and 6 . 2 Preliminaries This section has three parts. First, we present notation to be used in the sequel, and basic terminologies in symbolic integration. Next, some useful properties of residues are recalled for elementary integration. At last, we describe a dual presentation for complementary subspaces, which enables us to compute in subspaces of infinite dimension in Sections 5 and 6 . 2.1 Basic terminologies Besides the usual notation in textbooks, we let {\mathbb{N}} , {\mathbb{N}}_{0} and {\mathbb{N}}^{-} be the sets of positive, nonnegative and negative integers, respectively. Set [n]:=\{1,\ldots,n\} for n\in{\mathbb{N}} , and [n]_{0}:=\{0,1,\ldots,n\} for n\in{\mathbb{N}}_{0} . For an abelian group (G,+,0) , G\setminus\{0\} is denoted by G^{\times} . All the fields are of characteristic zero in the sequel. Let F be a field and p\in F[t]^{\times} . The degree and leading coefficient of p are denoted by \deg_{t}(p) and \operatorname{lc}_{t}(p) , respectively. In addition, \deg_{t}(0):=-\infty and \operatorname{lc}_{t}(0):=0 . We set F[t]_{l} denotes the set of elements in Q whose tail degrees are greater than l . For an element f of F(t) , its numerator and denominator are denoted by \operatorname{num}_{t}(f) and \operatorname{den}_{t}(f) , respectively. Moreover, \operatorname{den}_{t}(f) is set to be monic. We say that f is t -proper if the degree of \operatorname{num}_{t}(f) is less than that of \operatorname{den}_{t}(f) . The subscript t will be omitted for brevity when the indeterminate t is clear from context. Let f\in F(t)^{\times} with a=\operatorname{num}(f) and b=\operatorname{den}(f) . For p\in F[t] with \deg(p)>0 , the order of f at p , denoted by \nu_{p}(f) , is defined to be -m if p is of multiplicity m>0 in b . Otherwise, the order is the multiplicity of p in a . In addition, \nu_{p}(0) is set to be \infty . The order of f at infinity is \deg(b)-\deg(a) and denoted by \nu_{\infty}(f) . Let (F,\,^{\prime}) be a differential field. We denote \{f^{\prime}\mid f\in F\} by F^{\prime} , which is a linear space over the subfield of constants in F . An element of F is called a logarithmic derivative if it is equal to g^{\prime}/g for some g\in F^{\times} . A differential field (E,\,\delta) is called a differential field extension of (F,\,^{\prime}) if F is a subfield of E and \delta|_{F}=\,^{\prime} . The derivation \delta will still be denoted by ′ when there is no confusion arising. Let E be a differential field extension of F and f\in E . Then f is said to be primitive (resp. hyperexponential) over F if f^{\prime}\in F (resp. f\neq 0 and f^{\prime}/f\in F ). An element t in a differential field extension of F is called a monomial over F if t is transcendental over F and t^{\prime}\in F[t] . A monomial t over F is said to be regular if F(t) and F have the same subfield of constants. By Definition 1.7 , a transcendental Liouvillian extension C(t_{1},\ldots,t_{n}) is a differential field extension of C , in which t_{i} is a regular monomial over C(t_{1},\ldots,t_{i-1}) , and is either primitive or hyperexponential over the same field for all i\in[n] . In the rest of this section, we let (F,\,^{\prime}) be a differential field, C be its subfield of constants, and t be a monomial over F . Then F[t] is a differential subring of F(t) . A nonzero polynomial p\in F[t] is said to be normal (resp. special) if \gcd(p,p^{\prime})=1 (resp. \gcd(p,p^{\prime})=p ). Set N_{t} to be the set of all monic, irreducible and normal polynomials of positive degrees. An element of F(t) is t -simple if it is t -proper and has a normal denominator according to [ 13 , Section 1] . All t -simple elements in F(t) form an F -subspace, which is denoted by S_{t} . Let F\langle t\rangle:=\{f\in F(t)\mid\text{$\operatorname{den}(f)$ is special}\}. Then F[t]\subset F\langle t\rangle , and F\langle t\rangle is a differential subring (see [ 10 , Corollary 4.4.1] ). We remark that t -simple elements are not required to be t -proper in [ 10 , Definition 3.5.2] . Our further requirement for t -properness results in S_{t}\cap F\langle t\rangle=\{0\} , which is necessary for the direct sum ( 4 ) in Section 3 . Some basic facts about generators in a transcendental Liouvillian extension are collected in the following lemma for a convenience of later references. Lemma 2.1 . Let t be regular over F , d\in{\mathbb{Z}} , u\in F and p\in F[t] . (i) If d>0 and t is primitive over F , then \left(ut^{d}\right)^{\prime}=u^{\prime}t^{d}+udt^{\prime}t^{d-1} whose degree is equal to d if u is not a constant, and d-1 , otherwise. (ii) If t is hyperexponential over F , then \left(ut^{d}\right)^{\prime}=\left(u^{\prime}+ud(t^{\prime}/t)\right)t^{d} whose head and tail degrees are both equal to d . (iii) If t is primitive over F , then p is normal if and only if p is squarefree. (iv) If t is hyperexponential over F , then p is normal if and only if p is squarefree and t\nmid p . Proof. (i) By Leibniz’s rule, \left(ut^{d}\right)^{\prime}=u^{\prime}t^{d}+udt^{\prime}t^{d-1} . Since t is regular over F , we have that t^{\prime}\in F^{\times} , which implies that the degree of \left(ut^{d}\right)^{\prime} is at least d-1 . (ii) Similarly, Leibniz’s rule implies that \left(ut^{d}\right)^{\prime}=\left(u^{\prime}+ud(t^{\prime}/t)\right)t^{d} , which is nonzero because t is regular. Since t^{\prime}/t\in F , both head and tail degrees of \left(ut^{d}\right)^{\prime} are equal to d . (iii) and (iv) hold by [ 10 , Lemma 3.4.4, Theorems 5.1.1 and 5.1.2] . ∎ We use sequences in algorithmic descriptions in order to avoid clumsy names of list operations. Let L:l_{1},\ldots,l_{k} be a sequence. Then l_{i} is denoted by L[i] for all i\in[k] . The empty sequence is written as nil . The length of L is defined to be k and denoted by \operatorname{len}(L) . In the description of an algorithm, comments are placed between (^{*}{\sl\cdots}^{*}) . 2.2 Residues and elementary integration The reader is referred to [ 10 , Section 4.4] for the definition of residues. Let us mention two well-known facts on residues: First, all residues of an element in F[t] are zero by the definition. Second, all residues of a logarithmic derivative in F(t) are integers by [ 10 , Corollary 4.4.2 (iii)] . The next two lemmas are useful to prove Theorem 8.3 , which enables us to determine elementary integrability of remainders. Lemma 2.2 . Let t be regular over F , p\in F[t]^{\times} with d=\deg(p) and p_{d}=\operatorname{lc}(p) . (i) If t is primitive over F , then p^{\prime}/p=s+p_{d}^{\prime}/p_{d} for some s\in S_{t} . (ii) If t is hyperexponential over F , then p^{\prime}/p=s+p_{d}^{\prime}/p_{d}+dt^{\prime}/t for some s\in S_{t} . (iii) All residues of s appearing in (i) or (ii) are integers. Proof. (i) Let q=p_{d}^{-1}p . Then p^{\prime}/p=p_{d}^{\prime}/p_{d}+q^{\prime}/q by the logarithmic derivative identity in [ 10 , Exercis 3.1] , So q^{\prime}/q\in S_{t} by Lemma 2.1 (i) and (iii). The conclusion holds by setting s:=q^{\prime}/q . (ii) There exists an integer m\in{\mathbb{N}}_{0} and a monic polynomial r\in F[t] with t\nmid r such that p=p_{d}t^{m}r . Again, the logarithmic derivative identity implies that p^{\prime}/p=p_{d}^{\prime}/p_{d}+mt^{\prime}/t+r^{\prime}/r . It follows from t^{\prime}/t\in F , Lemma 2.1 (ii) and (iv) that s:=r^{\prime}/r-(d-m)t^{\prime}/t is an element of S_{t} . Furthermore, p^{\prime}/p=p_{d}^{\prime}/p_{d}+dt^{\prime}/t+s . (iii) The t -simple element s in (i) or (ii) is the difference of p^{\prime}/p and an element in F . Since all residues of a logarithmic derivative are integers, so are the residues of s . ∎ Lemma 2.3 . Let t be regular over F and f\in S_{t}^{\times} . Assume that C is algebraically closed, and that t is either primitive or hyperexponential over F . If all residues of f belong to C , then f has an elementary integral over F . Proof. Let \alpha_{1},\ldots,\alpha_{k} be the distinct roots of \operatorname{den}(f) in the algebraic closure of F . Since all residues of f in \overline{F} are constants, there exist c_{1},\ldots,c_{k}\in C and p\in F[t] such that f=c_{1}\frac{(t-\alpha_{1})^{\prime}}{t-\alpha_{1}}+\cdots+c_{k}\frac{(t-\alpha_{k})^{\prime}}{t-\alpha_{k}}+p by [ 19 , Lemma 3.1 (i)] . If t is primitive over F , then p=0 by f\in S_{t} and Lemma 2.1 (i). If t is hyperexponential over F , then p=ct^{\prime}/t for some c\in C by f\in S_{t} and Lemma 2.1 (ii). Thus, f has an elementary integral over F . ∎ 2.3 A dual presentation for complementary subspaces Let U be a C -linear space. Every subspace of U is the intersection of kernels of some linear functions on U . Such an intersection is understood as a dual presentation of the subspace. For a nonempty subset S of U , \operatorname{span}_{C}(S) stands for the C -subspace spanned by S . In addition, the empty set spans \{0\} . Let \Theta be a basis of U . For \theta\in\Theta , \theta^{*} stands for the linear function on U that maps \theta to 1 and other elements of \Theta to 0 . The basis \Theta is said to be effective if there are two algorithms available: one finds an element \theta\in\Theta such that \theta^{*}({\bf u})\neq 0 for all {\bf u}\in U^{\times} , and the other computes \theta^{*}({\bf v}) for all {\bf v}\in U and \theta\in\Theta (see [ 20 , Section 2.2] ). Definition 2.4 . Let \Theta be given above, V be a subspace of U and {\mathbb{I}}\subset{\mathbb{N}}_{0} . A basis \{{\bf v}_{i}\mid i\in{\mathbb{I}}\} of V is called an echelon basis of V with respect to \Theta if, for each i\in{\mathbb{I}} , there exists an element \theta_{i}\in\Theta such that {\bf v}_{i}\notin\ker(\theta_{i}^{*}) for all i\in{\mathbb{I}} and {\bf v}_{j}\in\ker(\theta_{i}^{*}) for all j\in{\mathbb{I}} with j0 by h\neq 0 and a_{m}=0 . Since a_{m}=0 , we have \ker({\mathcal{L}})=C by ( 5 ). Then the type of I_{h} is set to be 1 . So p_{0}=1 , which implies {\mathcal{P}}_{h}(p_{0})=a . In particular, d_{0} in Corollary 5.18 is equal to \deg(a) . Set the first associated R-pair (\tilde{v},v):=(0,1) , the second pair (\tilde{w},w):=(0,a_{m-1}) , and \theta_{v}:=1 . It suffices to examine whether iv+w is zero for i\in{\mathbb{N}} , since \theta_{v}^{*} is the identity operator on C . Note that iv+w=i+a_{m-1} . An echelon sequence of I_{h} is given by Corollary 5.18 (i) if a_{m-1} is not a negative integer. Otherwise, such a sequence is given by Corollary 5.18 (iii). Pivots in the echelon sequences and bases of the induced complements are listed below. a_{m-1}=-j Pivots in the echelon sequence Basis of the induced complement j\notin{\mathbb{N}}_{0} \begin{array}[]{ll}x^{m-1},&x^{m},x^{m+1},\ldots\end{array} \begin{array}[]{ll}1,x,\ldots,x^{m-2}\end{array} j=0 \begin{array}[]{ll}x^{d_{0}},&x^{m},x^{m+1},\ldots\end{array} \begin{array}[]{ll}1,x,\ldots,x^{d_{0}-1},&x^{d_{0}+1},\ldots,x^{m-1}\end{array} j\in{\mathbb{N}} \begin{array}[]{ll}x^{d},&x^{m-1},x^{m},\ldots,x^{m+j-2},\\ &x^{m+j},x^{m+j+1},\ldots\end{array} \begin{array}[]{lll}1,x,\ldots,x^{d-1},&x^{d+1},\ldots,x^{m-2},&x^{m+j-1}\end{array} The results in the second, third and last row correspond to Cases 2, 3 and 4 in [ 4 , Section 4.1] , respectively. A complementary subspace for \operatorname{im}({\mathcal{P}}_{h}) in F[t] is of finite dimension over C if F=C by Examples 5.16 and 5.19 . But such a subspace is of infinite dimension if \dim_{C}(F)=\infty . Example 5.20 . Let F=C(x) , t=\log(x) and d/dx be the derivation on F(t) . Let h=\dfrac{2x^{2}-2t}{xt^{2}+x}. We determine an echelon sequence of I_{h} with respect to (F[t],{\mathcal{P}}_{h}) and \Gamma , where \Gamma=\{\theta t^{i}\mid\theta\in\Theta,i\in{\mathbb{N}}_{0}\} and \Theta is given by equation (2) in [ 20 ] . By Convention 4.1 , a b m a_{m} b_{m} a_{m-1} b_{m-1} -2x^{-1}t+2x t^{2}+1 2 0 1 -2x^{-1} 0 Since a_{m}=0 , we may further assume that the complete reduction \phi_{0} in Hypothesis 4.2 is induced by the Hermite-Ostrogradsky reduction. Then the auxiliary subspace U_{h} associated to (F[t],{\mathcal{P}}_{h}) is equal to F[t]_{<2}+S_{x}\otimes\left(t^{2}C[t]\right) by Definition 5.3 and \operatorname{im}(\phi_{0})=S_{x} . Note that {\mathcal{L}}=d/dx by a_{2}=0 and b_{2}=1 . Then we can set the type u of I_{h} to be 1 . Then (\tilde{v},v)=\left(0,x^{-1}\right) and (\tilde{w},w)=\left(0,-2x^{-1}\right) by Algorithm A.1 . Since v=x^{-1} , we choose \theta_{v} given before Corollary 5.17 to be x^{-1} . We need Corollary 5.18 (iii) to construct an echelon sequence E , because 2v+w=0 . At first, we compute p_{0} and p_{1} in the standard basis \{p_{i}\}_{i\in{\mathbb{N}}_{0}} of {\mathcal{P}}_{h}^{-1}(I_{h}) . By u=1 , we have that p_{0}=1 . Then {\mathcal{P}}_{h}(p_{0})=-2x^{-1}t+2x . Hence, d_{0}=1 . Choose \theta_{0} to be x^{-1} . Then the second member of E is (p_{0},\,{\mathcal{P}}_{h}(p_{0}),\,\theta_{0}t^{d_{0}})=\left(1,\,-2x^{-1}t+2x,\,x^{-1}t\right). (13) Note that \theta_{0}=\theta_{v} is just a coincidence. By ( 10 ) and \tilde{v}=\tilde{w}=0 , we see that p_{1}=t . Thus, the third member of E is (p_{1},\,{\mathcal{P}}_{h}(p_{1}),\,\theta_{v}t^{2})=\left(t,\,-x^{-1}t^{2}+2xt+x^{-1},\,x^{-1}t^{2}\right). (14) Since 2v+w=0 , we compute the first member of E by p_{2} . By ( 10 ) and Algorithm A.1 , we find that p_{2}:=t^{2}-x^{2} . Then {\mathcal{P}}_{h}(p_{2})=(2x+2x^{-1})t-2x^{3}-2x. Eliminating x^{-1}t from {\mathcal{P}}_{h}(p_{2}) by {\mathcal{P}}_{h}(p_{0}) yields q=t^{2}-x^{2}+1 and {\mathcal{P}}_{h}(q)=2xt-2x^{3}. Choose \theta to be x . Then the first member of the echelon sequence is (q,\,{\mathcal{P}}_{h}(q),\,\theta t)=\left(t^{2}-x^{2}+1,\,2xt-2x^{3},\,xt\right). (15) For k>3 , the k th member of E can be found by ( 10 ), ( 11 ) and Algorithm A.1 . Its pivot is fixed to be x^{-1}t^{k-1} by Corollary 5.18 (iii). We summarize the results in the following table. u (\tilde{v},v) (\tilde{w},w) \theta_{v} j (q,{\mathcal{P}}_{h}(q),\theta t) (p_{0},{\mathcal{P}}_{h}(p_{0}),\theta_{0}t^{d_{0}}) (p_{1},{\mathcal{P}}_{h}(p_{1}),\theta_{v}t^{2}) 1 \left(0,x^{-1}\right) \left(0,-2x^{-1}\right) x^{-1} 2 r.h.s. of ( 15 ) r.h.s. of ( 13 ) r.h.s. of ( 14 ) where j stands for the positive integer with jv+w=0 . We have made three choices for pivots in the above example. Together with ( 10 ) and Algorithm A.1 , these choices determine an echelon sequence of I_{h} uniquely. In the appendix, we introduce the notion of initial sequences in Definition A.2 . Such a sequence is finite and contains all the information to determine a unique echelon sequence. In fact, the last table in Example 5.20 records an initial sequence of I_{h} . Moreover, Algorithm A.3 computes initial sequences, and Algorithm A.4 generates members of the echelon sequence determined by an initial sequence, as many as required. We are ready to present the main result of this section. Theorem 5.21 . With Hypothesis 4.2 , one can construct a complete reduction for (F(t),{\mathcal{R}}_{h}) . Proof. If the type u of I_{h} is zero, then we set W to be the auxiliary subspace U_{h} . Otherwise, let E=\{(q_{i},Q_{i},\gamma_{i})\}_{i\in{\mathbb{N}}} be an echelon sequence of I_{h} , where \gamma_{i} belongs to \{\theta t^{i}\mid\theta\in\Theta,i\in{\mathbb{N}}\} . Moreover, let W be the complement of \operatorname{im}({\mathcal{P}}_{h}) induced by E . Since F[t]=\operatorname{im}({\mathcal{P}}_{h})\oplus W , a complete reduction \Phi_{h} for (F(t),{\mathcal{R}}_{h}) is given by Proposition 3.5 . It remains to describe an algorithm for computing R-pairs with respect to \Phi_{h} . Let \Psi_{h} be the projection from F[t] to W with respect to F[t]=\operatorname{im}({\mathcal{P}}_{h})\oplus W . By Remark 3.6 , it suffices to develop an algorithm for computing R-pairs with respect to \Psi_{h} . For every element p\in F[t] , an auxiliary pair (q,r) of p can be found by Algorithm A.1 . If u=0 , then (q,r) is an R-pair with respect to \Psi_{h} . Otherwise, one can compute \tilde{q}\in F[t] and \tilde{r}\in I_{h} such that \tilde{r}={\mathcal{P}}_{h}(\tilde{q}) and r-\tilde{r}\in\cap_{i\in{\mathbb{N}}}\ker(\gamma_{i}^{*}) by Lemma 2.11 , in which U=F[t] , \rho={\mathcal{P}}_{h} and V=I_{h} . On the other hand, r-\tilde{r}\in U_{h} by r\in U_{h} and \tilde{r}\in U_{h} . Thus, r-\tilde{r}\in W because W is defined by ( 12 ). It follows that \left(q+\tilde{q},\,r-\tilde{r}\right) is an R-pair of p with respect to \Psi_{h} . ∎ At the end of this section, we connect the complete reduction \Phi_{h} for (F(t),{\mathcal{R}}_{h}) in the above theorem with \phi_{h} for (F,{\mathcal{R}}_{h}) in Hypothesis 4.2 when h\in F . Such a connection is important for elementary integration in Section 8 . Corollary 5.22 . Let \Phi_{h} be the complete reduction for (F(t),{\mathcal{R}}_{h}) constructed in the proof of Theorem 5.21 . Assume that h\in F , and that \phi_{h} is the complete reduction for (F,{\mathcal{R}}_{h}) given in Hypothesis 4.2 . Then, for all f\in F , \Phi_{h}(f)=\phi_{h}(f) if I_{h}=\{0\} , and, otherwise, there exists c\in C such that \Phi_{h}(f)=\phi_{h}(f)+c\phi_{h}\left(ut^{\prime}\right), where u is the type of I_{h} . Proof. For every f\in F , its projection to S_{t,h} is zero, where S_{t,h} is given in ( 2 ) and the projection is with respect to the direct sum in Proposition 3.5 . Let (g,r) be an auxiliary pair of f . Then r=\phi_{h}(f) by Corollary 5.7 . If I_{h}=\{0\} , then r=\Phi_{h}(f) . Otherwise, let (\tilde{v},v) be the first R-pair associated to (F(t),{\mathcal{R}}_{h}) , where v=\phi_{h}(ut^{\prime}) by Definition 5.12 . Then an echelon sequence E of I_{h} is given by Corollary 5.17 , in which the first member is (ut-\tilde{v},v,\theta_{v}) . Since \deg(r)\leq 0 and \deg\left(v\right)=0 , the projection of r to the complement induced by E is equal to r+cv , where c=-\theta_{v}^{*}(v)^{-1}\cdot\theta_{v}^{*}\left(r\right) . The corollary holds by noting that \Phi_{h}(f)=r+cv and v=\phi_{h}(ut^{\prime}) . ∎ 6 The hyperexponential case In this section, t is assumed to be hyperexponential. Then F\langle t\rangle=F[t,t^{-1}] . For every integer d , we define two C -linear operators: \begin{array}[]{cccc}{\mathcal{H}}_{d}:&F&\rightarrow&F\\ &z&\mapsto&b_{m}z^{\prime}+\left(a_{m}+db_{m}\dfrac{t^{\prime}}{t}\right)z\end{array}\,\text{and}\,\begin{array}[]{cccc}{\mathcal{T}}_{d}:&F&\rightarrow&F\\ &z&\mapsto&b_{0}z^{\prime}+\left(a_{0}+db_{0}\dfrac{t^{\prime}}{t}\right)z\end{array} (16) to describe the coefficients of the possibly highest and lowest powers in an element of \operatorname{im}({\mathcal{P}}_{h}) . Namely, for an element f\in F[t,t^{-1}]^{\times} with k=\operatorname{hdeg}(f), f_{k}=\operatorname{hc}(f) , l=\operatorname{tdeg}(f) and f_{l}=\operatorname{tc}(f) , {\mathcal{P}}_{h}(f)={\mathcal{H}}_{k}(f_{k})t^{m+k}+\cdots+{\mathcal{T}}_{l}(f_{l})t^{l} (17) by Lemma 2.1 (ii). It follows that {\mathcal{P}}_{h}(f^{+})\in F[t] and {\mathcal{P}}_{h}(f^{-})\in F[t]_{l}. (20) Case 4. Let \nu_{t}(h)\geq 0 and (g_{l},r_{l}) be an R-pair of b_{0}^{-1}f_{l} with respect to \phi_{\mu_{l}} . By Definition 1.4 , we have that b_{0}^{-1}f_{l}={\mathcal{R}}_{\mu_{l}}(g_{l})+r_{l} , which, together with {\mathcal{T}}_{l}=b_{0}{\mathcal{R}}_{\mu_{l}} in Remark 6.1 (iv), implies that f_{l}={\mathcal{T}}_{l}(g_{l})+b_{0}r_{l} . Then f_{l}t^{l}={\mathcal{T}}_{l}(g_{l})t^{l}+(b_{0}r_{l})t^{l} . So f^{-}\equiv{\mathcal{T}}_{l}(g_{l})t^{l}+(b_{0}r_{l})t^{l}\mod F[t]_{l}. It follows from ( 17 ) that f^{-}\equiv{\mathcal{P}}_{h}(g_{l}t^{l})+(b_{0}r_{l})t^{l}\mod F[t]_{l}. (21) This case distinction leads to the notion of auxiliary subspaces in the hyperexponential case. Definition 6.3 . The auxiliary subspace associated to (F[t,t^{-1}],{\mathcal{P}}_{h}) is V_{h}=V_{h}^{+}+F[t]_{l}. Thus, there exists g\in t^{-1}F[t^{-1}] with \operatorname{tdeg}(g)\geq l such that f^{-}\equiv{\mathcal{P}}_{h}(g)\mod V_{h}+t^{-1}F[t^{-1}]_{>l} for all values of \nu_{t}(h) . The conclusion holds by an induction on l . By (i) and (ii), f={\mathcal{P}}_{h}(p+q)+r+s and r+s\in V_{h} . Hence, F[t,t^{-1}]=\operatorname{im}({\mathcal{P}}_{h})+V_{h} . ∎ Definition 6.6 . Let f,p,q,r and s be given in the above proposition. We call (p+q,r+s) an auxiliary pair of f with respect to (F[t,t^{-1}],{\mathcal{P}}_{h}) or an auxiliary pair of f if (F[t,t^{-1}],{\mathcal{P}}_{h}) is clear from context. Auxiliary pairs always exist by Proposition 6.5 . Based on ( 18 ), ( 19 ), ( 20 ) ( 21 ) and the proof of Proposition 6.5 , an algorithm is developed for computing such pairs (see Algorithm A.6 ). Corollary 6.7 . Let f,h\in F and (g,r) be an auxiliary pair of f with respect to (F[t,t^{-1}],{\mathcal{P}}_{h}) . Then (g,r) is an R-pair of f with respect to \phi_{h} , where \phi_{h} is given by Hypothesis 4.2 . Proof. Note that \lambda_{0} defined in Remark 6.1 (ii) is equal to h by h\in F . The rest is similar to the proof of Corollary 5.7 . ∎ 6.2 Determining whether \operatorname{im}({\mathcal{P}}_{h})\cap V_{h} is trivial In the rest of this section, we let J_{h}=\operatorname{im}({\mathcal{P}}_{h})\cap V_{h} . The next two lemmas connect J_{h} with the kernels of {\mathcal{H}}_{d} and {\mathcal{T}}_{d} in ( 16 ). We will prove the second assertions in these two lemmas. Their first assertions can be shown likewise. Lemma 6.8 . Let f\in F[t,t^{-1}]^{\times} , k=\operatorname{hdeg}(f) and l=\operatorname{tdeg}(f) . Assume that {\mathcal{P}}_{h}(f)\in V_{h} . Then (i) \operatorname{hc}(f)\in\ker({\mathcal{H}}_{k}) if k\geq 0 , and (ii) \operatorname{tc}(f)\in\ker({\mathcal{T}}_{l}) if l<0 . Proof. (ii) Let f_{l}=\operatorname{tc}(f) . Suppose on the contrary that {\mathcal{T}}_{l}(f_{l})\neq 0. Then {\mathcal{T}}_{l}(f_{l})t^{l}\in V_{h}^{-} by {\mathcal{P}}_{h}(f)\in V_{h} . In particular, V_{h}^{-}\neq\{0\} . Hence, \nu_{t}(h)\geq 0 and {\mathcal{T}}_{l}(f_{l})\in b_{0}\cdot\operatorname{im}(\phi_{\mu_{l}}) by Definition 6.3 . By Remark 6.1 (iv), {\mathcal{T}}_{l}=b_{0}{\mathcal{R}}_{\mu_{l}} . Thus, {\mathcal{R}}_{\mu_{l}}(f_{l})\in\operatorname{im}(\phi_{\mu_{l}}) . Since \operatorname{im}({\mathcal{R}}_{\mu_{l}})\cap\operatorname{im}(\phi_{\mu_{l}})=\{0\}, we have that {\mathcal{T}}_{l}(f_{l})=0 , a contradiction. ∎ Lemma 6.9 . (i) If \ker({\mathcal{H}}_{k})\neq\{0\} for some k\in{\mathbb{N}}_{0} , then, for all u\in\ker({\mathcal{H}}_{k})^{\times} , there exists p\in F[t] with \operatorname{hdeg}(p)=k and \operatorname{hc}(p)=u such that {\mathcal{P}}_{h}(p)\in V_{h}. Moreover, for every element f\in F[t,t^{-1}] with {\mathcal{P}}_{h}(f)\in V_{h} , there exists an element c\in C such that f-cp\in t^{-1}F[t^{-1}] . (ii) If \ker({\mathcal{T}}_{l})\neq\{0\} for some l\in{\mathbb{N}}^{-} , then, for all v\in\ker({\mathcal{T}}_{l})^{\times} , there exists q\in t^{-1}F[t^{-1}] with \operatorname{tdeg}(q)=l and \operatorname{tc}(q)=v such that {\mathcal{P}}_{h}(q)\in V_{h}. Moreover, for every element f\in F[t,t^{-1}] with {\mathcal{P}}_{h}(f)\in V_{h} , there exists an element c\in C such that f-cq\in F[t] . Proof. (ii) By Remark 6.1 (iii), \nu_{t}(h)\geq 0 . By ( 17 ) and v\in\ker({\mathcal{T}}_{l}) , {\mathcal{P}}_{h}(vt^{l})\in t^{-1}F[t^{-1}]+F[t]_{l and r\in V_{h} by Proposition 6.5 (ii). Set q=vt^{l}-g . Then \operatorname{tdeg}(q)=l, v=\operatorname{tc}(q) and {\mathcal{P}}_{h}(q)\in V_{h}. Assume that f\in F[t,t^{-1}] with d=\operatorname{tdeg}(f) and {\mathcal{P}}_{h}(f)\in V_{h} . If d\geq 0 , then we set c:=0 . Otherwise, \operatorname{tc}(f)\in\ker({\mathcal{T}}_{d}) by Lemma 6.8 (ii). It follows from Lemma 6.2 that d=l . Since \ker({\mathcal{T}}_{l}) is one-dimensional over C , there exists c\in C such that \operatorname{tc}(f)=cv . Then {\mathcal{P}}_{h}(f-cq)\in V_{h} and \operatorname{tdeg}(f-cq)>l . So \operatorname{tdeg}(f-cq)\geq 0 by Lemma 6.8 (ii) and Lemma 6.2 . ∎ A criterion for J_{h}=\{0\} is given below. Proposition 6.10 . J_{h}=\{0\} if and only if one of the following two conditions holds. (i) h\in F , (ii) \ker({\mathcal{H}}_{k})=\{0\} for all k\in{\mathbb{N}}_{0} and \ker({\mathcal{T}}_{l})=\{0\} for all l\in{\mathbb{N}}^{-} . In particular, J_{h}=\{0\} if both \nu_{\infty}(h) and \nu_{t}(h) are negative. Proof. Assume that J_{h}=\{0\} and h\notin F . Suppose on the contrary that \ker({\mathcal{H}}_{k}) is nontrivial for some k\in{\mathbb{N}}_{0} . Then there exists p\in F[t]^{\times} such that {\mathcal{P}}_{h}(p)\in V_{h} by Lemma 6.9 (i). Moreover, {\mathcal{P}}_{h}(p)\neq 0 by Lemma 4.4 . So J_{h} is nontrivial, a contradiction. The same contradiction is reached by Lemma 6.9 (ii) and Lemma 4.4 if \ker({\mathcal{T}}_{l}) is nontrivial for some l\in{\mathbb{N}}^{-} . To show the converse, we let f\in F[t,t^{-1}] with {\mathcal{P}}_{h}(f)\in V_{h} . It suffices to show that {\mathcal{P}}_{h}(f)=0 . First, we consider the case in which h\in F . Then m=0 , b_{0}=1 , \nu_{\infty}(h)\geq 0 and \nu_{t}(h)\geq 0 . It follows from Definition 6.3 that V_{h}=\sum_{i\in{\mathbb{N}}_{0}}\operatorname{im}(\phi_{\lambda_{i}})\cdot t^{i}+\sum_{j\in{\mathbb{N}}^{-}}\operatorname{im}(\phi_{\mu_{j}})\cdot t^{j}, where \lambda_{i}=it^{\prime}/t+a_{0} and \mu_{j}=jt^{\prime}/t+a_{0} by Remark 6.1 (ii) and (iv). Set f=\sum_{i=l}^{k}f_{i}t^{i} with f_{i}\in F . We have {\mathcal{P}}_{h}(f)=\sum_{i=0}^{k}{\mathcal{R}}_{\lambda_{i}}(f_{i})t^{i}+\sum_{j=l}^{-1}{\mathcal{R}}_{\mu_{j}}(f_{j})t^{j} by Lemma 2.1 (ii) and {\mathcal{P}}_{h}(f)=f^{\prime}+a_{0}f . Hence, {\mathcal{R}}_{\lambda_{i}}(f_{i})\in\operatorname{im}(\phi_{\lambda_{i}}) for all i\in{\mathbb{N}}_{0} and {\mathcal{R}}_{\mu_{j}}(f_{j})\in\operatorname{im}(\phi_{\mu_{j}}) for all j\in{\mathbb{N}}^{-} . Thus, {\mathcal{P}}_{h}(f)=0 by \operatorname{im}({\mathcal{R}}_{\lambda_{i}})\cap\operatorname{im}(\phi_{\lambda_{i}})=\{0\} and \operatorname{im}({\mathcal{R}}_{\mu_{j}})\cap\operatorname{im}(\phi_{\mu_{j}})=\{0\} . Next, we assume that \ker({\mathcal{H}}_{k})=\{0\} for all k\in{\mathbb{N}}_{0} and that \ker({\mathcal{T}}_{l})=\{0\} for all l\in{\mathbb{N}}^{-} . Suppose on the contrary that {\mathcal{P}}_{h}(f)\neq 0 . If k=\operatorname{hdeg}(f)\geq 0 , then f_{k}\in\ker({\mathcal{H}}_{k})^{\times} by Lemma 6.8 (i), a contradiction. So f^{+}=0 . Thus, we may further assume that \operatorname{tdeg}(f)=l<0 . It follows from Lemma 6.8 (ii) that f_{l}\in\ker({\mathcal{T}}_{l}) , a contradiction. If both \nu_{\infty}(h) and \nu_{t}(h) are negative, then {\mathcal{H}}_{k} and {\mathcal{T}}_{l} are injective by Remark 6.1 (i) and (iii). So J_{h}=\{0\} by the second condition. ∎ Similar to Definition 5.10 , we define the notion of types as follows. Definition 6.11 . The type of J_{h} is defined to be (i) 0 if either h\in F , or, \ker({\mathcal{H}}_{k})=\{0\} for all k\in{\mathbb{N}}_{0} and \ker({\mathcal{T}}_{l})=\{0\} for all l\in{\mathbb{N}}^{-} , (ii) (k,u) if h\notin F , u\in\ker({\mathcal{H}}_{k})^{\times} for some k\in{\mathbb{N}}_{0} and \ker({\mathcal{T}}_{l})=\{0\} for all l\in{\mathbb{N}}^{-} , (iii) (l,v) if h\notin F , \ker({\mathcal{H}}_{k})=\{0\} for all k\in{\mathbb{N}}_{0} and v\in\ker({\mathcal{T}}_{l})^{\times} for some l\in{\mathbb{N}}^{-} , (iv) (k,u),(l,v) if h\notin F , u\in\ker({\mathcal{H}}_{k})^{\times} for some k\in{\mathbb{N}}_{0} and v\in\ker({\mathcal{T}}_{l})^{\times} for some l\in{\mathbb{N}}^{-} . The type of J_{h} can be computed by an algorithm for solving the parametric logarithmic derivative problem in F (see [ 30 , Section 4.3.1] ). The type is zero if and only if J_{n}=\{0\} by Proposition 6.10 . If it is nonzero, then k,l are unique by Lemma 6.2 , and u,v are unique up to a multiplicative constant in C^{\times} . Similar to the primitive case, the type is fixed once and for all. Example 6.12 . Let F=C , t=\exp(x) and h=-t^{2}/(t^{2}+t+1) . Then m=2 , a_{m}=-1 , b_{m}=1 , a_{0}=0 and b_{0}=1 . It follows from Remark 6.1 (ii) and (iv) that {\mathcal{H}}_{k}(z)=(k-1)z and {\mathcal{T}}_{l}(z)=lz for all k\in{\mathbb{N}}_{0} , l\in{\mathbb{N}}^{-} and z\in F . Hence, the type of J_{h} is equal to (1,1) . 6.3 An echelon sequence of J_{h} Unlike the intersection I_{h} in the primitive case, we have Proposition 6.13 . (i) \dim_{C}(J_{h})=1 if the type of J_{h} is equal to (i,w) for some i\in{\mathbb{Z}} . (ii) \dim_{C}(J_{h})=2 if the type of J_{h} is equal to (k,u),(l,v) for some k\in{\mathbb{N}}_{0} and l\in{\mathbb{N}}^{-} . Proof. Since the type of J_{h} is nonzero, we have that h\in F(t)\setminus F by Proposition 6.10 . Consequently, {\mathcal{P}}_{h} is injective by Lemma 4.4 . (i) Let us consider the case in which i<0 . By Lemma 6.9 (ii), there exists q\in t^{-1}F[t^{-1}] with \operatorname{tdeg}(q)=i such that {\mathcal{P}}_{h}(q)\in V_{h} and that, for every f\in F[t,t^{-1}] with {\mathcal{P}}_{h}(f)\in V_{h} , g:=f-cq\in F[t] for some c\in C . Then {\mathcal{P}}_{h}(g)\in V_{h} by {\mathcal{P}}_{h}(f)\in V_{h} and {\mathcal{P}}_{h}(q)\in V_{h} . Suppose that g\neq 0 . Let k=\operatorname{hdeg}(g) . Then k\geq 0 . By Lemma 6.8 (i), \ker({\mathcal{H}}_{k})\neq\{0\} , a contradiction to the type of J_{h} . Hence, g=0 , and, consequently, {\mathcal{P}}_{h}(f)=c{\mathcal{P}}_{h}(q) . Note that {\mathcal{P}}_{h}(q)\neq 0 by the injectivity of {\mathcal{P}}_{h} . We have that \dim_{C}(J_{h})=1 . Likewise, one shows that \dim_{C}(J_{h})=1 if i\geq 0 . (ii) By Lemma 6.9 , there exist p\in F[t] with \operatorname{hdeg}(p)=k and q\in t^{-1}F[t^{-1}] with \operatorname{tdeg}(q)=l such that {\mathcal{P}}_{h}(p),{\mathcal{P}}_{h}(q)\in V_{h} . Let f\in F[t,t^{-1}] with {\mathcal{P}}_{h}(f)\in V_{h} . Then g:=f-c_{p}p\in t^{-1}F[t^{-1}] for some c_{p}\in C by Lemma 6.9 (i). Moreover, {\mathcal{P}}_{h}(g)\in V_{h} by {\mathcal{P}}_{h}(f)\in V_{h} and {\mathcal{P}}_{h}(p)\in V_{h} . It follows from Lemma 6.9 (ii) that g-c_{q}q\in F[t] for some c_{q}\in C . Then g-c_{q}q=0 because both g and q belong to t^{-1}F[t^{-1}] . Thus, f=c_{p}p+c_{q}q . Consequently, {\mathcal{P}}_{h}(f)=c_{p}{\mathcal{P}}_{h}(p)+c_{q}{\mathcal{P}}_{h}(q) . Since p\in F[t] and q\in t^{-1}F[t^{-1}] , they are linearly independent. So are {\mathcal{P}}_{h}(p) and {\mathcal{P}}_{h}(q) by the injectivity of {\mathcal{P}}_{h} . Thus, \dim_{C}(J_{h})=2 . ∎ Similar to Section 5 , we let \Gamma=\{\theta t^{i}\mid i\in{\mathbb{Z}}\} . It is an effective basis of F[t,t^{-1}] by Convention 4.1 (iv) and [ 20 , Remark 2.7] . Proposition 6.14 . If J_{h} is nontrivial, then one can construct an echelon sequence of J_{h} with respect to \left(F[t,t^{-1}],{\mathcal{P}}_{h}\right) and \Gamma . Proof. Assume that \dim_{C}(J_{h})=1 . Then J_{h}=\operatorname{span}_{C}\{{\mathcal{P}}_{h}(p)\} for some p\in F[t,t^{-1}] . Let d and w be the head degree and head coefficient of {\mathcal{P}}_{h}(p) , respectively. We choose an element \theta\in\Theta such that \theta^{*}(w)\neq 0 . Then \left(p,{\mathcal{P}}_{h}(p),\theta t^{d}\right) is an echelon sequence of J_{h} Otherwise, \dim_{C}(J_{h})=2 by Proposition 6.13 . Then J_{h}=\operatorname{span}_{C}\{{\mathcal{P}}_{h}(p),{\mathcal{P}}_{h}(q)\} for some p,q\in F[t,t^{-1}] . Let d and w be the head degree and head coefficient of {\mathcal{P}}_{h}(p) , respectively, and let \theta_{p}\in\Theta with \theta_{p}^{*}(w)\neq 0 . Set \gamma_{p}:=\theta_{p}t^{d} , c_{p}:=\gamma_{p}^{*}\left({\mathcal{P}}_{h}(p)\right) , c_{q}:=\gamma_{p}^{*}\left({\mathcal{P}}_{h}(q)\right) , and r:=q-c_{p}^{-1}c_{q}p. Then {\mathcal{P}}_{h}(r) belongs to \ker(\gamma_{p}^{*}) and \{{\mathcal{P}}_{h}(p),\,{\mathcal{P}}_{h}(r)\} is also a basis of J_{h} . Let e and z be the head degree and head coefficient of {\mathcal{P}}_{h}(r) , respectively, and choose \theta_{r}\in\Theta with \theta_{r}^{*}(z)\neq 0 . Set \gamma_{r}=\theta_{r}t^{e} . Then \left(r,{\mathcal{P}}_{h}(r),\gamma_{r}\right) , \left(p,{\mathcal{P}}_{h}(p),\gamma_{p}\right) is an echelon sequence of J_{h} . ∎ An algorithm for constructing an echelon sequence of J_{h} can be easily developed according to the proofs of Propositions 6.13 and 6.14 (see Algorithm A.7 in the appendix). For the sake of completeness, the echelon sequence is set to be nil if the type of J_{h} is equal to 0 . Corollary 6.15 . Let E be an echelon sequence of J_{h} . (i) If E is nil , then V_{h} is a complement of \operatorname{im}({\mathcal{P}}_{h}) in F[t,t^{-1}] . (ii) If E is (p,{\mathcal{P}}_{h}(p),\gamma) , then V_{h}\cap\ker(\gamma^{*}) is a complement of \operatorname{im}({\mathcal{P}}_{h}) in F[t,t^{-1}] . (iii) If E is \left(p_{1},{\mathcal{P}}_{h}(p_{1}),\gamma_{1}\right) , \left(p_{2},{\mathcal{P}}_{h}(p_{2}),\gamma_{2}\right) , then V_{h}\cap\ker(\gamma_{1}^{*})\cap\ker(\gamma_{2}^{*}) is a complement of \operatorname{im}({\mathcal{P}}_{h}) in F[t,t^{-1}] . Proof. It is immediate from Proposition 6.5 and Lemma 2.7 . ∎ The complement in the above proposition is also called the complement of \operatorname{im}({\mathcal{P}}_{h}) in F[t,t^{-1}] induced by E . The main result of this section is Theorem 6.16 . With Hypothesis 4.2 , one can construct a complete reduction for (F(t),{\mathcal{R}}_{h}) . Proof. It is similar to the proof of Theorem 5.21 . ∎ Corollary 6.17 . Let h\in F , \Phi_{h} be the complete reduction for (F(t),{\mathcal{R}}_{h}) in Theorem 6.16 , and \phi_{h} be the complete reduction for (F,{\mathcal{R}}_{h}) in Hypothesis 4.2 . Then \Phi_{h}(f)=\phi_{h}(f) for all f\in F . Proof. By Proposition 6.10 and h\in F , we have J_{h}=\{0\} . The corollary follows from Corollary 6.7 and the same argument used for proving that \Phi_{h}(f)=\phi_{h}(f) for all f\in F when I_{h}=\{0\} in Corollary 5.22 . ∎ 7 Completing the induction In this section, we let F_{n}=C(t_{1},\ldots t_{n}) be a transcendental Liouvillian extension given in Definition 1.7 . In addition, F_{0}=C during an induction or a recursion. Theorem 7.1 . For every element h\in F_{n} , one can construct a complete reduction for (F_{n},{\mathcal{R}}_{h}) . Proof. We proceed by induction on n . If n=0 , then the conclusion holds by Example 3.2 . Let n>0 . Assume that, for every z\in F_{n-1} , one can construct a complete reduction \phi_{{n-1},z} for (F_{n-1},{\mathcal{R}}_{z}) , and assume that the map in Hypothesis 4.2 is defined by z\mapsto\phi_{{n-1},z} . For h\in F_{n} , let (\xi,\eta) be the canonical form of h . Then one can construct a complete reduction for (F_{n},{\mathcal{R}}_{\xi}) by either Theorem 5.21 or Theorem 6.16 . It follows from Proposition 3.3 (ii) that a complete reduction \phi_{n,h} for (F_{n},{\mathcal{R}}_{h}) is obtained. The map in Hypothesis 4.2 is then redefined by h\mapsto\phi_{n,h} for all h\in F_{n} . ∎ In practice, we need to maintain some initial data in order to avoid choosing elements from a set in different ways (see [ 20 , Remark 2.5] ). Let \Theta_{0}=\{1\} . For each i\in[n] , we have an effective basis \Theta_{i} of F_{i} described in [ 20 , Section 2.2] . Furthermore, we set up a table {\mathbb{T}} indexed by (i,z) , where i\in[n] and z\in F_{i} is t_{i} -normalized. The value of (i,z) is an initial (resp. echelon) sequence of (i,z) , where i\geq 1 and t_{i} is primitive (resp. hyperexponential). See Definition A.2 for the notion of initial sequences. The table can be understood as the map in Hypothesis 4.2 for each F_{i} with i\in[n] . It is global and will be updated as long as a complete reduction for (F_{i},{\mathcal{R}}_{z}) is constructed. These considerations lead to Outline 7.2 . Given f,h\in F_{n} , we compute an R-pair of f with respect to \phi_{n,h} . 1. (^{*} Base case {}^{*}) If n=0 , then an R-pair of f w.r.t. \phi_{n,h} is (f/h,0) if h\neq 0 , and (0,f) if h=0 . The algorithm terminates. (^{*} See Example 3.2 and 4.3 {}^{*}) 2. (^{*} Preprocessing {}^{*}) (2.1) Find the canonical form (\xi,\eta) of h w.r.t. t_{n} by Algorithm GKS in [ 11 , Section 3.2] . (2.2) Compute (g,r,s)\in F_{n}\times F_{n-1}\langle t_{n}\rangle\times S_{t_{n},\xi} s.t. \eta f={\mathcal{R}}_{\xi}(g)+r/b+s by Algorithm GKSR in [ 11 , Section 3.4] , where b=\operatorname{den}(\xi) and S_{t_{n},\xi} is given in ( 2 ). (^{*} See ( 3 ) ∗ ) (2.3) If r=0 , then an R-pair of f w.r.t. \phi_{n,h} is (\eta^{-1}g,\eta^{-1}s) . The algorithm terminates. (^{*} See Propositions 3.5 and 3.3 {}^{*}) 3. (^{*} Recursion {}^{*}) Assume that t_{n} is primitive (resp. hyperexponential) over F_{n-1} . (3.1) Compute an auxiliary pair (p,q) of r w.r.t. (F_{n-1}\langle t_{n}\rangle,{\mathcal{P}}_{\xi}) by Algorithm A.1 (resp. Algorithm A.6 ); (3.2) If q=0 , an R-pair of f w.r.t. \phi_{n,h} is (\eta^{-1}(g+p),\eta^{-1}s) . The algorithm terminates. (^{*} See Propositions 5.5 , 6.5 and Remark 3.6 {}^{*}). (3.3) (^{*} Updating {\mathbb{T}} {}^{*}) If (n,\xi) is an index of {\mathbb{T}} , then set L to be the value of (n,\xi) . Otherwise, compute an initial sequence L of I_{h} by Algorithm A.3 (resp. an echelon sequence E . of J_{h} by Algorithm A.7 ), and add (n,\xi)=L (resp. (n,\xi)=E ) to {\mathbb{T}} . (3.4) (^{*} trivial intersection {}^{*}) If L= nil or L[1]=0 , then an R-pair of f w.r.t. \phi_{n,h} is \left(\eta^{-1}(g+p),\eta^{-1}\left(q/b+s\right)\right). The algorithm terminates. (^{*} See Propositions 5.9 , 6.10 and Remark 3.6 {}^{*}) (3.5) (^{*} Nontrivial intersection {}^{*}) By Algorithm A.5 (resp. Algorithm A.8 ), compute \tilde{q}\in F_{n-1}\langle t_{n}\rangle and \tilde{r}\in W such that q={\mathcal{P}}_{\xi}(\tilde{q})+\tilde{r} , where W is the complement of \operatorname{im}({\mathcal{P}}_{\xi}) in F_{n-1}\langle t_{n}\rangle induced by L (resp. E ). An R-pair of f w.r.t. \phi_{n,h} is \left(\eta^{-1}(g+p+\tilde{q}),\eta^{-1}\left(\tilde{r}/b+s\right)\right). (^{*} See Theorems 5.21 , 6.16 and Remark 3.6 {}^{*}) In the following two examples, all steps are referred to as those in the above outline. The first example provides details of Example 1.10 . Example 7.3 . Determine whether f=\dfrac{x}{1+\exp(x)}\cdot\exp\left(\dfrac{x}{1+\exp(x)}\right) is a derivative in the transcendental elementary extension \left({\mathbb{C}}(x,t,y),d/dx\right) , where t=\exp(x) and y=\exp\left(\dfrac{x}{1+\exp(x)}\right) . Note that f=gy , where g=\dfrac{x}{1+\exp(x)} . To avoid describing too many recursions, we set h:=y^{\prime}/y , which is equal to g^{\prime} . By the same argument as in Example 3.1 , it suffices to compute an R-pair of g with respect to the complete reduction \phi_{2,h} for ({\mathbb{C}}(x,t),{\mathcal{R}}_{h}) . Initially, we set F_{0}={\mathbb{C}} , F_{1}=F_{0}(x) , F_{2}=F_{1}(t) , and the table {\mathbb{T}} to be empty. Since h is a derivative in F_{2} , it is t -normalized. So (\xi,\eta)=(h,1) in step 2.1. With Convention 4.1 and h=\xi , we have a b m a_{m} b_{m} a_{0} b_{0} 1+(1-x)t (1+t)^{2} 2 0 1 1 1 In step 2.2, we have g=\mathcal{R}_{h}(0)+(r/b)+0 , where r=x+xt . Step 2.3 is skipped. In step 3.1, Algorithm A.6 computes an auxiliary pair (p,q)=\left(0,x+xt\right) of r , where r belongs to the auxiliary subspace V_{h} associated to (F_{1}[t,t^{-1}],{\mathcal{P}}_{h}) . Step 3.2 is skipped since q is nonzero. In step 3.3, we find that (2,h) is not an index of \mathbb{T} . So an echelon sequence of J_{h} is constructed as follows. First, we obtain the type of J_{h} is (0,1),(-1,1) by solving a parametric logarithmic derivative problem, where J_{h}=\operatorname{im}({\mathcal{P}}_{h})\cap V_{h} as in Section 6.2 . Second, Algorithm A.6 computes the auxiliary pairs of \mathcal{P}_{h}(1) and \mathcal{P}_{h}(t^{-1}) , which are (0,-xt+t+1) and (0,-t-1-x) , respectively. Third, choose a pivot xt for \mathcal{P}_{h}(1) and a pivot t for \mathcal{P}_{h}(t^{-1}) , we have an echelon sequence E:\,(t^{-1},-t-1-x,t),\,(1,-xt+t+1,xt) of J_{h} . At last, the entry (2,h)=E is added to \mathbb{T}. Step 3.4 is skipped since E is not nil . In step 3.5, Algorithm A.8 projects q to \operatorname{im}({\mathcal{P}}_{h}) and the complement of \operatorname{im}({\mathcal{P}}_{h}) induced by E . The respective projections are \mathcal{P}_{h}(-1-t^{-1}) and 0 . Then an R-pair of g with respect to \phi_{2,h} is (-1-t^{-1},0) , that is, g=\mathcal{R}_{h}(-1-t^{-1}). It follows from h=y^{\prime}/y and f=gy that f=\bigl(\left(-1-t^{-1}\right)y\bigr)^{\prime}. In functional notation, we have \int f=-\bigl(1+\exp(-x)\bigr)\cdot\exp\left(\dfrac{x}{1+\exp(x)}\right). In the second example, F_{n} is neither a primitive tower nor an exponential one. Example 7.4 . Let t=\log(x) . Determine whether f=\dfrac{(2x^{3}+2x^{2}-1)t-t^{3}-t^{2}-2x^{5}+1}{x^{2}(t^{2}+1)}\cdot\exp\Big(\displaystyle\int\!\dfrac{2x^{2}-2t}{xt^{2}+x}\Big) is a derivative in {\mathbb{Q}}(x,t,f) , where the derivation is d/dx . We rewrite f in another form so as to make intermediate expressions more compact. Let y=\exp\left(\displaystyle\int\dfrac{2x^{2}-2t}{xt^{2}+x}\right) . Then f=gy, where g=\dfrac{(2x^{3}+2x^{2}-1)t-t^{3}-t^{2}-2x^{5}+1}{x^{2}(t^{2}+1)}. Moreover, {\mathbb{Q}}(x,t,f)={\mathbb{Q}}(x,t,y) . It follows from the same reasoning in Example 3.1 that f belongs to {\mathbb{Q}}(x,t,y)^{\prime} if and only if there exists w\in{\mathbb{Q}}(x,t) such that {\mathcal{R}}_{h}(w)=g , where h:=\frac{y^{\prime}}{y}=\frac{2x^{2}-2t}{xt^{2}+x}. Thus, it suffices to compute an R-pair of g with respect to the complete reduction \phi_{2,h} for ({\mathbb{Q}}(x,t),{\mathcal{R}}_{h}) given in the proof of Theorem 7.1 . Let F_{0}={\mathbb{Q}} , F_{1}=F_{0}(x) and F_{2}=F_{1}(t) . Then it is t -normalized by a straightforward verification. So (\xi,\eta)=(h,1) in step 2.1. With Convention 4.1 and \xi=h , we have a b m a_{m} b_{m} a_{0} b_{0} -2x^{-1}t+2x t^{2}+1 2 0 1 2x 1 In step 2.2, we have g=\mathcal{R}_{h}(0)+(r/b) , where r=-x^{-2}t^{3}-x^{-2}t^{2}+(2x+2-x^{-2})t-2x^{3}+x^{-2} . In step 3.1, we compute an auxiliary pair (p,q)=\left(x^{-1}t,2xt-2x^{3}\right) (22) of r with respect to (F_{1}[t],{\mathcal{P}}_{h}) . During the process of the auxiliary reduction, an R-pair of \operatorname{lc}_{t}(r) with respect to \phi_{1,0} is computed. So an entry (1,0)=1,(0,1), (0,0) , 1 is added to {\mathbb{T}} . Note that h is the same as that in Example 5.20 , in which the last table presents an initial sequence L with L[1]=1,L[2]=(0,x^{-1}),L[3]=(0,2x^{-1}),L[4]=x^{-1},L[5]=2, L[6]=\left(t^{2}-x^{2}+1,2xt-2x^{3},xt\right),\,\,L[7]=\left(1,-2x^{-1}t+2x,x^{-1}t\right), and L[8]=\left(t,-x^{-1}t^{2}+2xt+x^{-1},x^{-1}t^{2}\right). Step 3.3 is then completed by adding (2,h)=L to {\mathbb{T}} . Step 3.4 is skipped because L[1]\neq 0 . Let E denote the echelon sequence induced by L . In step 3.5, we project q in ( 22 ) to \operatorname{im}({\mathcal{P}}_{h}) and W , respectively, where W is the complement of \operatorname{im}({\mathcal{P}}_{h}) induced by E . Since \deg_{t}(q)=1 , there is no need to compute more members in E . In fact, q is equal to the second component of L[6] . Then the respective projections of q are {\mathcal{P}}_{h}(t^{2}-x^{2}+1) and 0 . It follows that an R-pair of g with respect to \phi_{2,h} is (x^{-1}t+t^{2}-x^{2}+1,0) . In other words, g={\mathcal{R}}_{h}(x^{-1}t+t^{2}-x^{2}+1) , which implies that f=(gy)^{\prime} . In functional notation, we have \displaystyle\int f=\left(\frac{\log(x)}{x}+\log(x)^{2}-x^{2}+1\right)\cdot\exp\left(\displaystyle\int\dfrac{2x^{2}-2\log(x)}{x\log^{2}(x)+x}\right). The same integral can be computed by the int() command with option method=parallelrisch in maple 2023 and the Integrate[] command in mathematica 14.3. 8 Applications Similar to the previous section, we let n\in{\mathbb{N}} and F_{n}=C(t_{1},\ldots,t_{n}) be a transcendental Liouvillian extension. In addition, C is denoted by F_{0} during an induction or a recursion. For all i\in[n]_{0} , we let \psi_{i} be the complete reduction \phi_{i,0} for (F_{i},\,^{\prime}) given in the proof of Theorem 7.1 . To determine elementary integrability, we need to distinguish primitive generators from hyperexponential ones. Set {\mathbb{P}}:=\{i\in[n]\mid t_{i}^{\prime}\in F_{i-1}\} and {\mathbb{H}}:=[n]\setminus{\mathbb{P}}. Moreover, P:=\operatorname{span}_{C}\{\psi_{i-1}(t_{i}^{\prime})\mid i\in{\mathbb{P}}\}\quad\text{and}\quad H:=\operatorname{span}_{C}\{\psi_{j-1}(t_{j}^{\prime}/t_{j})\mid j\in{\mathbb{H}}\}. The following two technical lemmas present some useful properties of remainders. Lemma 8.1 . For i\in[n]_{0} and f\in F_{i} , \psi_{n}(f)-\psi_{i}(f)\in P. Proof. Let k\geq i . By Example 5.11 and Corollary 5.22 , we have that \psi_{k+1}(f)-\psi_{k}(f)\in P if k+1\in{\mathbb{P}} . By Corollary 6.17 , \psi_{k+1}(f)-\psi_{k}(f)=0 if k+1\in{\mathbb{H}} . It follows from \psi_{n}(f)-\psi_{i}(f)=\sum_{k=i}^{n-1}\left(\psi_{k+1}(f)-\psi_{k}(f)\right) that \psi_{n}(f)-\psi_{i}(f)\in P. ∎ Let S_{i} be the set of t_{i} -simple elements in F_{i-1}(t_{i}) for all i\in[n] , that is, S_{i}:=S_{t_{i}} . Set S:=S_{1}+\cdots+S_{n} . The sum is direct. An element of F_{n} is said to be simple if it belongs to S . Lemma 8.2 . For every element s\in S , s-\psi_{n}(s)\in P . Proof. Let s=\sum_{i\in[n]}s_{i} , where s_{i}\in S_{i} . By Proposition 3.5 and Remark 3.6 , \psi_{i}(s_{i})=s_{i} for all i\in[n] . Then s-\psi_{n}(s)=\sum_{i\in[n]}\left(\psi_{i}(s_{i})-\psi_{n}(s_{i})\right) by \psi_{n}(s)=\sum_{i\in[n]}\psi_{n}(s_{i}) . The lemma follows from Lemma 8.1 . ∎ Next, we define residues of elements in S without referring to a particular generator of F_{n} . For a simple element s , there exists a unique element s_{i}\in S_{i} for each i\in[n] such that s=s_{1}+\cdots+s_{n}. Regarding s_{i} as an element of F_{i-1}(t_{i}) , we say that a residue of s_{i} is a residue of s . We are ready to generalize [ 20 , Theorem 5.3] from primitive towers to F_{n} . Theorem 8.3 . Let C be algebraically closed. Then an element f of F_{n} has an elementary integral over F_{n} if and only if (i) there exists a simple element s such that \psi_{n}(f)\equiv s\mod H+P, and (ii) all residues of s belong to C . Proof. Assume that both (i) and (ii) hold. By (ii) and Lemma 2.3 , s has an elementary integral over F_{n} . By (i), it suffices to show that every element of H+P has an elementary integral over F_{n} . If i\in{\mathbb{H}} , then t_{i}^{\prime}/t_{i}=u_{i}^{\prime}+\psi_{i-1}(t_{i}^{\prime}/t_{i}) for some u_{i}\in F_{i-1} , which implies that \psi_{i-1}(t_{i}^{\prime}/t_{i}) is the derivative of \log(t_{i})-u_{i} . If i\in{\mathbb{P}} , then t_{i}^{\prime}=v_{i}^{\prime}+\psi_{i-1}(t_{i}^{\prime}) for some v_{i}\in F_{i-1} . Therefore, \psi_{i-1}(t_{i}^{\prime})\in F_{n}^{\prime} . Accordingly, \psi_{n}(f) has an elementary integral over F_{n} , and so does f . Conversely, assume that f has an elementary integral over F_{n} . Then there exists a C -linear combination g of logarithmic derivatives in F_{n} such that f\equiv g\mod F_{n}^{\prime} by [ 10 , Theorem 5.5.2] . Since \psi_{n}(F_{n}^{\prime})=\{0\} , we have \psi_{n}(f)=\psi_{n}(g) . It suffices to show that \psi_{n}(g) satisfies (i) and (ii). By Lemma 2.2 and the logarithmic derivative identity, there exists s\in S whose residues are all constants, such that g-s is a C -linear combination of t_{i}^{\prime}/t_{i} for i\in{\mathbb{H}} . Then \psi_{n}(g)-\psi_{n}(s)\in H+P by Lemma 8.1 . So \psi_{n}(g)-s\in H+P by Lemma 8.2 . Both (i) and (ii) hold. ∎ To compute elementary integrals by the above theorem, we set R_{i}:=t_{i}F_{i-1}[t_{i}] if i\in{\mathbb{P}} , and R_{i}:=t_{i}F_{i-1}[t_{i}]+t_{i}^{-1}F_{i-1}[t_{i}^{-1}] if i\in{\mathbb{H}} . Moreover, let R=C+R_{1}+\cdots+R_{n} . This sum is evidently direct, and so is R+S . Proposition 8.4 . With the notation just introduced, we have that \operatorname{im}(\psi_{n})\subset R\oplus S. Proof. We proceed by induction on n . For n=0 , \operatorname{im}(\psi_{0})=C by Example 3.2 . So \operatorname{im}(\psi_{0})\subset R . The conclusion holds. Assume that n>0 and that the conclusion holds for n-1 . We need to consider the cases in which n belongs to either {\mathbb{P}} or {\mathbb{H}} separately. Case 1. Assume n\in{\mathbb{P}} . The auxiliary subspace U_{0} associated to (F_{n-1}[t_{n}],{\mathcal{P}}_{0}) is \operatorname{im}(\psi_{n-1})\otimes C[t] , which is contained in \operatorname{im}(\psi_{n-1})+R_{n} . Since U_{0} contains the complement W of \operatorname{im}({\mathcal{P}}_{0}) induced by an echelon sequence of \operatorname{im}({\mathcal{P}}_{0})\cap U_{0} , we have W\subset\operatorname{im}(\psi_{n-1})+R_{n} . It follows from Remark 3.7 that \operatorname{im}(\psi_{n})=W\oplus S_{n} . So \operatorname{im}(\psi_{n})\subset\operatorname{im}(\psi_{n-1})+R_{n}+S_{n} . Thus, \operatorname{im}(\psi_{n})\subset R+S by the induction hypothesis. Case 2. Assume n\in{\mathbb{H}} . The auxiliary subspace V_{0} associated to (F[t_{n},t_{n}^{-1}],{\mathcal{P}}_{0}) is equal to \sum_{k\in{\mathbb{N}}}\operatorname{im}\left(\phi_{n-1,\lambda_{k}}\right)\cdot t_{n}^{k}+\operatorname{im}\left(\phi_{n-1,\lambda_{0}}\right)+\sum_{j\in{\mathbb{N}}^{-}}\operatorname{im}\left(\phi_{n-1,\mu_{l}}\right)\cdot t_{n}^{l}, where \phi_{n-1,\lambda_{k}},\phi_{n-1,\lambda_{0}} and \phi_{n-1,\mu_{l}} are the complete reductions on F_{n-1} given by Theorem 7.1 . It is contained in \operatorname{im}\left(\phi_{n-1,\lambda_{0}}\right)+R_{n} . Then V_{0} is also a subset of \operatorname{im}(\psi_{n-1})+R_{n} , because \phi_{n-1,\lambda_{0}}=\psi_{n-1} by h=0 . The rest holds by the same argument as in Case 1. ∎ Next, we outline an algorithm for computing elementary integrals over F_{n} . Outline 8.5 . For f\in F_{n} , we proceed as follows. 1. Compute an R-pair (g,\psi_{n}(f)) . If \psi_{n}(f)=0 , then \int f=g and the algorithm terminates. 2. By Proposition 8.4 , we decompose \psi_{n}(f)=r_{f}+s_{f} , \psi_{i-1}(t_{i}^{\prime}/t_{i})=r_{i}+s_{i} if i\in{\mathbb{H}} , and \psi_{i-1}(t_{i}^{\prime})=r_{i}+s_{i} if i\in{\mathbb{P}} , where r_{f},r_{i}\in R and s_{f},s_{i}\in S . 3. Let z_{1},\ldots,z_{n} be constant indeterminates. 3.1. Compute M\in C^{k\times n} and {\bf v}\in C^{k} such that r_{f}-\sum_{i\in[n]}z_{i}r_{i}=0 if and only if the linear system in z_{1} , …, z_{n} given by the augmented matrix (M\mid{\bf v}) is consistent. 3.2. Use [ 20 , Algorithm 2.8] to compute a matrix N\in C^{l\times n} and {\bf w}\in C^{l} such that all residues of s_{f}-\sum_{i\in[n]}z_{i}s_{i} are constants if and only if the linear system in z_{1},\ldots,z_{n} given by (N\mid{\bf w}) is consistent. 3.3. Solve the linear system given by \left(\begin{array}[]{c|c}M&{\bf v}\\ N&{\bf w}\end{array}\right) . If the system has no solution, then f has no elementary integral over F_{n} by Theorem 8.3 and the fact that R+S is direct. The algorithm terminates. 4. Let c_{1},\ldots,c_{n} be a solution of the above system. Set s:=s_{f}-\sum_{i\in[n]}c_{i}s_{i}. Then \displaystyle\psi_{n}(f) \displaystyle=r_{f}+s_{f} \displaystyle=\left(r_{f}-\sum_{i=1}^{n}c_{i}r_{i}\right)+\left(s_{f}-\sum_{i=1}^{n}c_{i}s_{i}\right)+\sum_{j\in{\mathbb{H}}}c_{j}\psi_{j-1}\left(\frac{t_{j}^{\prime}}{t_{j}}\right)+\sum_{k\in{\mathbb{P}}}c_{k}\psi_{k-1}\left(t_{k}^{\prime}\right) \displaystyle=s+\sum_{j\in{\mathbb{H}}}c_{j}\psi_{j-1}\left(\frac{t_{j}^{\prime}}{t_{j}}\right)+\sum_{k\in{\mathbb{P}}}c_{k}\psi_{k-1}(t_{k}^{\prime}). The integral of s is elementary over F_{n} by Lemma 2.3 . Let (q_{j},\psi_{j-1}(t_{j}^{\prime}/t_{j})) be an R-pair of t_{j}^{\prime}/t_{j} for all j\in{\mathbb{H}} , and (q_{k},\psi_{k-1}(t_{k}^{\prime})) be an R-pair of t_{k}^{\prime} for all k\in{\mathbb{P}} . It follows from the proof of Theorem 8.3 that \int f=g+\int s+\sum_{j\in{\mathbb{H}}}c_{j}(\log(t_{j})-q_{j})+\sum_{k\in{\mathbb{P}}}c_{k}(t_{k}-q_{k}), where s is integrated by determining its residues (see [ 10 , Theorem 4.4.3] and [ 19 ] ). Example 8.6 . Let us integrate f:=\dfrac{(\log x+1)\,\operatorname{Li}(x^{\alpha})}{x^{\alpha+1}}, where \alpha is a constant indeterminate, \operatorname{Li}(x) is the logarithmic integral, i.e., \operatorname{Li}(x)^{\prime}=1/\log x, where ′ stands for the usual derivation d/dx . Let C be the algebraic closure of {\mathbb{Q}}(\alpha) , t_{1}=x, t_{2}=x^{\alpha}, t_{3}=\log(x), and t_{4}={\rm Li}(x^{\alpha}). Then t_{1}^{\prime}=1 , t_{2}^{\prime}/t_{2}=\alpha/t_{1}, t_{3}^{\prime}=1/t_{1} , t_{4}^{\prime}=t_{2}/(t_{1}t_{3}), and F_{4}:=C(t_{1},t_{2},t_{3},t_{4}) is a transcendental Liouvillian extension. Moreover, f=(t_{3}t_{4}+t_{4})/(t_{1}t_{2}). 1. By the algorithm in Outline 7.2 , (p,q) is an R-pair of f with respect to \psi_{4} , where p=\dfrac{\alpha t_{2}t_{3}-\alpha t_{3}t_{4}-(\alpha+1)t_{4}}{\alpha^{2}t_{2}}\quad\text{and}\quad q=\dfrac{\alpha+1}{\alpha^{2}t_{1}t_{3}}. 2. Projecting remainders \psi_{4}(f) , \psi_{0}(t_{1}^{\prime}) , \psi_{1}(t_{2}^{\prime}/t_{2}) , \psi_{2}(t_{3}^{\prime}) and \psi_{3}(t_{4}^{\prime}) with respect to R\oplus S , we obtain the following table \psi_{0}(t_{1}^{\prime}) \psi_{1}(t_{2}^{\prime}/t_{2}) \psi_{2}(t_{3}^{\prime}) \psi_{3}(t_{4}^{\prime}) \psi_{4}(f) Proj. in R r_{1}=1 r_{2}=0 r_{3}=0 r_{4}=0 r_{f}=0 Proj. in S s_{1}=0 s_{2}=\alpha/t_{1} s_{3}=1/t_{1} s_{4}=t_{2}/(t_{1}t_{3}) s_{f}=q 3. Let z_{1},z_{2},z_{3} and z_{4} be constant indeterminates. We make two ansatzes: (i) r_{f}=z_{1}r_{1}+z_{2}r_{2}+z_{3}r_{3}+z_{4}r_{4} , and (ii) s_{f}-z_{1}s_{1}-z_{2}s_{2}-z_{3}s_{3}-z_{4}s_{4} has merely constant residues. They lead to the linear system in z_{1} , z_{2} , z_{3} and z_{4} whose augmented matrix is \left(\begin{array}[]{cccc|c}1&0&0&0&0\\ 0&0&0&-\alpha&0\end{array}\right). It has a solution (0,0,0,0). Hence, f has an elementary integral over F_{4}. 4. Computing the residues of s_{f} yields that \int f=\dfrac{1}{\alpha}\log(x)+\dfrac{\alpha+1}{\alpha^{2}}\log(\log(x))-\dfrac{\alpha\log x+(\alpha+1)}{\alpha^{2}x^{\alpha}}\operatorname{Li}(x^{\alpha}). Example 8.7 . Let F_{0}=\mathbb{C} and F_{3}=F_{0}(t_{1},t_{2},t_{3}) , where \dfrac{t_{1}^{\prime}}{t_{1}}=\sqrt{-1},\quad t_{2}^{\prime}=\dfrac{\sqrt{-1}(t_{1}^{2}+1)}{t_{1}^{2}-1}\quad\text{and}\quad\frac{t_{3}^{\prime}}{t_{3}}=\dfrac{t_{2}^{2}-1}{2\sqrt{-1}t_{2}}. Then F_{3} is a transcendental Liouvillian extension, where t_{1} , t_{2} and t_{3} model \exp(\sqrt{-1}x),\quad\log(\sin x)\quad\text{and}\quad\exp\left(\int\frac{\log(\sin x)^{2}-1}{2\sqrt{-1}\log(\sin x)}\right), respectively. Note that any nonzero constant is not a derivative in F_{3} . Let us try to integrate f:=\dfrac{(\sqrt{-1}t_{2}^{2}-\sqrt{-1}t_{1}^{2}t_{2}^{2}-2)t_{3}+\sqrt{-1}t_{1}^{2}t_{2}+3\sqrt{-1}t_{2}-2t_{2}}{2(t_{1}^{2}-1)t_{2}(t_{3}+t_{2})} over F_{3} by the above algorithm. 1. An R-pair of f with respect to \psi_{3} is (0,f) . So \psi_{3}(f)=f and f\notin F_{3}^{\prime} . 2. Projecting the corresponding remainders with respect to R\oplus S yields that \psi_{0}(t_{1}^{\prime}/t_{1}) \psi_{1}(t_{2}^{\prime}) \psi_{2}(t_{3}^{\prime}/t_{3}) \psi_{3}(f) Proj. in R r_{1}=\sqrt{-1} r_{2}=\sqrt{-1} r_{3}=t_{2}/\left(2\sqrt{-1}\right) r_{f} Proj. in S s_{1}=0 s_{2}=2\sqrt{-1}/(t_{1}^{2}-1) s_{3}=-1/\left(2\sqrt{-1}t_{2}\right) s_{f} where r_{f}=\dfrac{t_{2}}{2\sqrt{-1}}\quad\text{and}\quad s_{f}=\dfrac{1}{(1-t_{1}^{2})t_{2}}+\dfrac{\sqrt{-1}(t_{1}^{2}t_{2}^{2}+t_{1}^{2}-t_{2}^{2}+3)}{2(t_{1}^{2}-1)(t_{2}+t_{3})}. 3. Let z_{1},z_{2},z_{3} be three constant indeterminates. Ansatzes similar to those in the third step of the above example lead to the linear system in z_{1} , z_{2} and z_{3} whose augmented matrix is \left(\begin{array}[]{ccc|c}\sqrt{-1}&\sqrt{-1}&0&0\\ 0&0&1&1\\ 0&0&\sqrt{-1}&1\end{array}\right). Since the system is inconsistent, we conclude that f has no elementary integral over F_{3}. Let us consider the case in which an integrand contains a shift variable k . More precisely, let C={\mathbb{C}}(k) , where k is a constant indeterminate. Assume further that the shift operator \sigma:k\mapsto k+1 can be extended to F_{n} , and that the extended operator commutes with the derivation on F_{n} . For every element f\in F_{n} , one can compute an R-pair (g_{i},r_{i}) of \sigma^{i}(f) for every i\in{\mathbb{N}}_{0} with respect to \psi_{n} . Then there exists a recurrence operator {\mathcal{L}}\in C[\sigma]^{\times} of order no more than i such that {\mathcal{L}}(f)\in F_{n}^{\prime} if and only if r_{0},r_{1},\ldots,r_{i} are C -linearly dependent. So we can construct a telescoper for f up to a given order. Unfortunately, we have not found any criterion for the existence of telescopers in such extensions. Discussions related to the construction of telescopers in primitive towers are given in [ 20 , Section 5.2] . At the end of this section, we illustrate how to construct telescopers via the complete reduction in Theorem 7.1 by an example. Example 8.8 . For all k\in{\mathbb{N}} , compute \int_{0}^{\frac{\pi}{2}}\cos(2kx)\log(\sin(x))~dx\quad\text{and}\quad\int_{0}^{\frac{\pi}{2}}\sin(2kx)\log(\sin(x))~dx. Let f(k,x)=\exp(2k\sqrt{-1}x)\log(\sin(x)) and A(k)=\int_{0}^{\frac{\pi}{2}}f(k,x)~dx . The integrand f(k,x) is not a D-finite function over {\mathbb{C}}(k,x) . The two integrals are the real and imaginary parts of A(k) , which are denoted by R(k) and I(k) , respectively. Let F_{0}={\mathbb{C}}(k) and F_{4}=F_{0}(t_{1},t_{2},t_{3},t_{4}) with t_{1}^{\prime}=1,\quad\frac{t_{2}^{\prime}}{t_{2}}=\sqrt{-1},\quad t_{3}^{\prime}=\frac{\sqrt{-1}(t_{2}^{2}+1)}{t_{2}^{2}-1},\quad\text{and}\quad\frac{t_{4}^{\prime}}{t_{4}}=2k\sqrt{-1}. The generators t_{1} t_{2} , t_{3} and t_{4} model x , \exp(\sqrt{-1}x) , \log(\sin(x)) and \exp(2k\sqrt{-1}x) , respectively. Then f(k,x)=t_{3}t_{4} and f(k+1,x)=t_{2}^{2}t_{3}t_{4} . Using \psi_{4} , we find an R-pair (g_{0},r_{0}) of f(k,x) and an R-pair (g_{1},r_{1}) of f(k+1,x) , where (g_{0},r_{0})=\left(-\frac{\sqrt{-1}(2kt_{3}-1)t_{4}}{4k^{2}},\,-\frac{t_{4}}{k(t_{2}^{2}-1)}\right) and (g_{1},r_{1})=\left(-\frac{\sqrt{-1}(2k^{2}t_{2}^{2}t_{3}+2kt_{2}^{2}t_{3}-kt_{2}^{2}-2k-2)t_{4}}{4(k+1)^{2}k},\,-\frac{t_{4}}{(k+1)(t_{2}^{2}-1)}\right). Since (k+1)r_{1}-kr_{0}=0 , we have (k+1)f(k+1,x)-kf(k,x)=(k+1)g_{1}^{\prime}-kg_{0}^{\prime}. (23) Although neither \lim_{x\rightarrow 0^{+}}g_{0} nor \lim_{x\rightarrow 0^{+}}g_{1} exists, \lim_{x\rightarrow 0^{+}}\left((k+1)g_{1}-kg_{0}\right)=\frac{\sqrt{-1}(2k+1)}{4k(k+1)}. Integrating both sides of ( 23 ) from 0 to \pi/2 , we have A(k+1)-\frac{k}{k+1}A(k)=\frac{\sqrt{-1}((-1)^{k}-2k-1)}{4k(k+1)^{2}}. (24) To compute A(k) for all k\in{\mathbb{N}} , we need A(1) , that is, the value of \displaystyle\int_{0}^{\frac{\pi}{2}}\exp(2\sqrt{-1}x)\log(\sin(x))\,dx . Its integrand is represented by t_{2}^{2}t_{3} in F_{3} . Using \psi_{3} , the integrand has an R-pair \left(-\frac{\sqrt{-1}}{2}t_{2}^{2}t_{3}+\frac{\sqrt{-1}}{4}t_{2}^{2}+\frac{\sqrt{-1}}{2}t_{3}-\frac{t_{1}}{2},\,0\right). So the integrand belongs to F_{3}^{\prime} . It follows that A(1)=-\pi/4-\sqrt{-1}/2 . Taking respective real and imaginary parts of both sides in ( 24 ) and A(1) , we have \left\{\begin{array}[]{l}R(k+1)-\displaystyle\frac{k}{k+1}R(k)=0\\ \\ R(1)=\displaystyle-\frac{\pi}{4}\end{array}\right.\quad\text{and}\quad\left\{\begin{array}[]{l}I(k+1)-\displaystyle\frac{k}{k+1}I(k)=\displaystyle\frac{(-1)^{k}-2k-1}{4k(k+1)^{2}}\\ \\ I(1)=\displaystyle-\frac{1}{2}.\end{array}\right. The first recurrence equation and initial value imply that R(k)=-\pi/(4k) . Using the mathematica package Sigma (see [ 35 ] ), we get I(k)=\frac{1-(-1)^{k}}{4k^{2}}-\frac{1}{2k}\left(\sum_{i=1}^{k}\frac{1-(-1)^{i}}{i}\right)+\frac{c}{k} for some c\in{\mathbb{C}} in the setting of R\Pi\Sigma -rings. With I(1)=-1/2 , we find I(k)=\frac{1-(-1)^{k}}{4k^{2}}-\frac{1}{2k}\left(\sum_{i=1}^{k}\frac{1-(-1)^{i}}{i}\right). Remark 8.9 . The result R(k)=-\pi/(4k) is given by Formula 4.384.7 in [ 25 ] . Integrals similar to I(k) are evaluated in [ 28 ] and [ 30 , Chapter 5] . 9 Experiments We present empirical results about in-field integration obtained from the complete reduction ( CR ) in Theorem 7.1 and the command int() in maple without any option. Experiments were carried out with maple 2021 on a computer with iMac CPU 3.6GHZ, Intel Core i9, 16G memory. Derivations acting on the differential fields appearing in this section are all equal to d/dx . An integrand is the derivative of a rational fraction in a transcendental Liouvillian extension {\mathbb{Q}}(t_{1},\ldots,t_{n}) . The numerator and denominator of such a fraction are given by the maple command randpoly([t1, t2, …, tn], degree=d) with option either dense or sparse . All integrands in our experiments are derivatives, because int would try to integrate a non-derivative in other closed forms. For each degree d , five derivatives were integrated. Timings were measured by maple CPU time in seconds. Computation would be aborted if one example took more than 3600 seconds. An entry was marked with “ \int ” if we detected that int returned an unevaluated integrals. In the first suite, we let n=3 , t_{1}=x , t_{2}=\exp(x) and t_{3}=\log(\exp(x)+x) . Rational fractions were dense. The average timings are summarized in Table 1. d 1 2 3 4 5 6 7 8 9 10 CR 0.23 0.01 0.02 0.14 0.62 2.18 7.93 21.97 55.35 > 3600 int 0.04 0.05 0.13 0.36 1.17 3.64 13.49 35.22 98.43 > 3600 Table 1: Dense rational fractions in x , \exp(x) and \log(\exp(x)+x) In the second suite, we let t_{1}=x , t_{2}=\log(x^{2}+1) and t_{3}=\exp(x^{2}/2) . An integrand was generated in the same way as in the first suite. The average timings are given in Table 2. d 1 2 3 4 5 6 7 8 9 10 CR 0.02 0.01 0.03 0.13 0.44 1.61 4.16 12.39 35.62 88.48 int 0.02 0.07 0.14 0.51 1.63 5.74 16.61 44.73 145.48 > 3600 Table 2: Dense rational fractions in x , \log(x^{2}+1) and \exp(x^{2}/2) We let n=4 , t_{1}=x , t_{2}=\log(x^{2}+1) , t_{3}=\exp(x^{2}/2) and t_{4}=\exp(\exp(x^{2}/2)) in the third suite. Rational fractions were sparse. The timings are given in Table 3. d 1 2 3 4 5 6 7 8 9 10 CR 0.02 0.01 0.02 0.04 0.05 0.07 0.15 28.71 4.15 56.03 int 0.04 0.13 0.19 0.28 0.41 0.49 0.61 38.93 16.40 \int Table 3: Sparse rational fractions in x , \log(x^{2}+1) , \exp(x^{2}/2) and \exp(\exp(x^{2}/2)) The timings for d=8 in Table 3 are very different from others. To have more coherent empirical results, we had changed the option from sparse to dense . But both CR and int took more than an hour without any outcome when d>6 . So we integrated the derivative of a polynomial in t_{1},t_{2},t_{3} and t_{4} with the option dense . The timings are given in Table 4. d 10 11 12 13 14 15 16 17 18 19 20 CR 0.19 0.21 0.26 0.35 0.51 0.46 0.58 0.62 0.82 1.05 1.19 int 3.30 4.70 6.65 9.28 12.55 26.36 32.52 39.76 62.94 90.34 86.59 Table 4: Dense polynomials in x , \log(x^{2}+1) , \exp(x^{2}/2) and \exp(\exp(x^{2}/2)) We let n=4 , t_{1}=x , t_{2}=\log(x^{2}+1) , t_{3}=\exp(x^{2}/2) and t_{4}=\exp\left(x\log(x^{2}+1)\right) in the last suite. The timings for sparse fractions and dense polynomials are summarized in Tables 5 and 6, respectively. d 1 2 3 4 5 6 7 8 9 10 CR 0.01 0.01 0.03 0.04 0.08 0.31 1.08 1.64 54.38 74.30 int 0.06 0.19 0.33 0.49 0.51 1.13 1.80 \int \int \int Table 5: Sparse rational fractions in x , \log(x^{2}+1) , \exp(x^{2}/2) and \exp\left(x\log(x^{2}+1)\right) d 10 11 12 13 14 15 16 17 18 19 20 CR 0.31 0.32 0.47 0.67 0.87 1.08 1.05 1.23 1.68 1.85 2.48 int 3.99 5.78 7.94 10.77 15.04 20.71 27.13 35.65 46.04 59.96 82.78 Table 6: Dense polynomials in x , \log(x^{2}+1) , \exp(x^{2}/2) and \exp\left(x\log(x^{2}+1)\right) We did not compare CR with int for computing elementary integrals, because such a comparison would need an algorithm for determining constant residues. Our maple scripts use an evaluation-based algorithm in [ 19 ] . It outperforms resultant-based algorithms developed in 1970’s (see [ 10 , Section 4.4] ). 10 Concluding remarks In this paper, a complete reduction is constructed for (F,{\mathcal{R}}_{h}) , where F is a transcendental Liouvillian extension and {\mathcal{R}}_{h} is the Risch operator associated to an element h of F . The complete reduction yields an algorithm for in-field integration directly, and leads to a new algorithm for computing elementary integrals over F . There are at least two challenging problems concerning complete reductions for symbolic integration. One is to develop a reduction-based algorithm for computing telescopers for elements in F without a given priori order bound. This would require a criterion on the existence of telescopers for elements in F . The other is how to adapt remainders of the complete reduction for algebraic functions in [ 15 ] so as to compute elementary integrals over algebraic-function fields more efficiently. Appendix A Algorithm descriptions This appendix is devoted to algorithmic descriptions of some constructive proofs in Sections 5 and 6 . Convention 4.1 and Hypothesis 4.2 are kept throughout the appendix. For brevity, we use the data in Convention 4.1 instead of F(t) , h , m , a , b , a_{m} , b_{m} , a_{0} and b_{0} in the specification of an algorithm. Furthermore, we abbreviate “with respect to” and “such that” as “w.r.t.” and “s.t.” in pseudo-codes, respectively. A.1 Algorithms in the primitive case In this subsection, t is a regular monomial and is primitive over F , U_{h} is the auxiliary subspace given in Definition 5.3 , and I_{h} denotes the intersection of \operatorname{im}({\mathcal{P}}_{h}) and U_{h} . The first algorithm describes an auxiliary reduction in F[t] . It is based on ( 7 ), ( 8 ) and the proof of Proposition 5.5 . Algorithm A.1 . PrimAuxRed Input: f\in F[t] and the data in Convention 4.1 Output: (g,r) , an auxiliary pair of f w.r.t. (F[t],{\mathcal{P}}_{h}) 1. p\leftarrow f , (g,r)\leftarrow 0,0 , (d,p_{d})\leftarrow\deg(p),\operatorname{lc}(p) 2. while d\geq m do if \nu_{\infty}(h)<0 then (u,v)\leftarrow a_{m}^{-1}p_{d}t^{d-m},\,0 else (g_{d},r_{d})\leftarrow an R-pair of p_{d} w.r.t. \phi_{a_{m}} , (u,v)\leftarrow g_{d}t^{d-m},r_{d}t^{d} (g,r)\leftarrow g+u,r+v , p\leftarrow p-{\mathcal{P}}_{h}(u)-v , (d,p_{d})\leftarrow\deg(p),\operatorname{lc}(p) ( ∗ by ( 7 ) and ( 8 ) ∗ ) 3. return (g,r+p) We are going to define a finite sequence L that determines an echelon sequence of I_{h} uniquely as long as the above algorithm is used for computing auxiliary pairs. Definition A.2 . Let u be the type of I_{h} . If u=0 , then L is set to be 0 . Assume that u\neq 0 . Let (\tilde{v},v) and (\tilde{w},w) be the first and second R-pairs associated to (F[t],{\mathcal{P}}_{h}) , respectively, and we fix an element \theta_{v}\in\Theta such that \theta_{v}^{*}(v)\neq 0 . If h\in F , then L is the sequence consisting of four members: u,(\tilde{v},v),(\tilde{w},w),\theta_{v}. (25) Assume further that h\in F(t)\setminus F . If \theta_{v}^{*}(iv+w)\neq 0 for all i\in{\mathbb{N}} , then L is the sequence consisting of five members: u,\,(\tilde{v},v),\,(\tilde{w},w),\,\theta_{v},\,\left(p_{0},{\mathcal{P}}_{h}(p_{0}),\,\theta_{0}t^{d_{0}}\right), (26) where the last member is given by Corollary 5.18 (i). If \theta_{v}^{*}(jv+w)=0 for some j\in{\mathbb{N}} but jv+w\neq 0 , then L consists of seven members: u,\,(\tilde{v},v),\,(\tilde{w},w),\,\theta_{v},\,j,\,\left(p_{0},{\mathcal{P}}_{h}(p_{0}),\theta_{0}t^{d_{0}}\right),\,\left(p_{j},{\mathcal{P}}_{h}(p_{j}),\theta t^{m+j-1}\right), (27) where the last two members are given by Corollary 5.18 (ii). If jv+w=0 for some j\in{\mathbb{N}} , then L consists of j+6 members: u,\,(\tilde{v},v),\,(\tilde{w},w),\,\theta_{v},\,j, \left(q,{\mathcal{P}}_{h}(q),\theta t^{d}\right),\,\left(p_{0},{\mathcal{P}}_{h}(p_{0}),\theta_{0}t^{d_{0}}\right),\,\left(p_{1},{\mathcal{P}}_{h}(p_{1}),\theta_{v}t^{m}\right),\,\ldots,\,\left(p_{j-1},{\mathcal{P}}_{h}(p_{j-1}),\theta_{v}t^{m+j-2}\right), (28) where the last j+1 members are given by Corollary 5.18 (iii). We call L an initial sequence of I_{h} . An initial sequence L with L\neq 0 determines an echelon sequence E of I_{h} uniquely by ( 10 ) and Algorithm A.1 . Moreover, we do not need to recompute {\mathcal{P}}_{h}(p_{i}) according to ( 11 ). The complement of \operatorname{im}({\mathcal{P}}_{h}) induced by E is also called the complement induced by L . The next algorithm computes initial sequences. Algorithm A.3 . InitSeq Input: the data in Convention 4.1 Output: an initial sequence of I_{h} 1. u\leftarrow the type of I_{h} , if u=0 then return 0 ( ∗ I_{h}=\{0\} ∗ ) 2. (\tilde{v},v)\leftarrow a first R-pair associated to (F[t],{\mathcal{P}}_{h}) (\tilde{w},w)\leftarrow a second R-pair associated to (F[t],{\mathcal{P}}_{h}) \theta_{v}\leftarrow an element of \Theta s.t. \theta^{*}_{v}(v)\neq 0 , L_{0}\leftarrow u,(\tilde{v},v),(\tilde{w},w),\theta_{v} 3. if h\in F then return L_{0} ( ∗ by Corollary 5.17 and ( 25 ) ∗ ) 4. p_{0}\leftarrow u , (d_{0},l_{0})\leftarrow\deg\left({\mathcal{P}}_{h}(p_{0})\right),\operatorname{lc}\left({\mathcal{P}}_{h}(p_{0})\right) \theta_{0}\leftarrow an element of \Theta s.t. \theta^{*}_{0}(l_{0})\neq 0 , \gamma_{0}\leftarrow\theta_{0}t^{d_{0}} , j\leftarrow-\theta_{v}^{*}(w)/\theta^{*}_{v}(v) , k\leftarrow-w/v 5. if j\notin{\mathbb{N}} then return L_{0},\left(p_{0},{\mathcal{P}}_{h}(p_{0}),\gamma_{0}\right) ( ∗ by Corollary 5.18 (i) and ( 26 ) ∗ ) 6. if k\notin{\mathbb{N}} then compute p_{j} and {\mathcal{P}}_{h}(p_{j}) by ( 10 ), ( 11 ) and Algorithm A.1 l\leftarrow \operatorname{lc}\left({\mathcal{P}}_{h}(p_{j})\right) ,   choose an element \theta\in\Theta s.t. \theta^{*}(l)\neq 0 return L_{0},j,\left(p_{0},{\mathcal{P}}_{h}(p_{0}),\gamma_{0}\right),\left(p_{j},{\mathcal{P}}_{h}(p_{j}),\theta t^{m+j-1}\right) ( ∗ by Corollary 5.18 (ii) and ( 27 ) ∗ ) 7. 7.1. compute p_{1},{\mathcal{P}}_{h}(p_{1}),\ldots,p_{j-1},{\mathcal{P}}_{h}(p_{j-1}),p_{j},{\mathcal{P}}(p_{j}) by ( 10 ), ( 11 ) and Algorithm A.1 7.2. (q,Q)\leftarrow p_{j},{\mathcal{P}}_{h}(p_{j}) 7.3. for i from j-1 to 0 by -1 do if i>0 then \gamma_{i}\leftarrow\theta_{v}t^{m+i-1} c\leftarrow\gamma_{i}^{*}\left({\mathcal{P}}_{h}(p_{i})\right)^{-1}\cdot\gamma_{i}^{*}(Q), (q,Q)\leftarrow q-cp_{i},Q-c{\mathcal{P}}_{h}(p_{i}) 7.4. (d,l)\leftarrow\deg(Q),\operatorname{lc}(Q) , choose an element \theta\in\Theta s.t. \theta^{*}(l)\neq 0 7.5. return L_{0},j,\left(q,Q,\theta t^{d}\right),\left(p_{0},{\mathcal{P}}_{h}(p_{0}),\gamma_{0}\right),\left(p_{1},{\mathcal{P}}_{h}(p_{1}),\gamma_{1}\right),\ldots,\left(p_{j-1},{\mathcal{P}}_{h}(p_{j-1}),\gamma_{j-1}\right) ( ∗ by Corollary 5.18 (iii) and ( 28 ) ∗ ) The correctness of this algorithm is direct from the definition of initial sequences and Corollaries 5.17 and 5.18 . Note that j and k in step 4 are equal when both of them are positive integers. So j is used in step 7. Given an initial sequence L with L[1]\neq 0 and a positive integer l , we can compute the first l members of the echelon sequence E by the following algorithm. Algorithm A.4 . PrimEchSeq Input: l\in{\mathbb{N}} , and the data in Convention 4.1 , and an initial sequence L of I_{h} with L[1]\neq 0 output: the first l members of the echelon sequence induced by L remark: In the following pseudo-code, p_{0}=L[1] and p_{i} and {\mathcal{P}}_{h}(p_{i}) are computed by ( 10 ), ( 11 ) and Algorithm A.1 for i>0 . 1. u\leftarrow L[1] , (\tilde{v},v)\leftarrow L[2] , (\tilde{w},w)\leftarrow L[3] , \theta_{v}\leftarrow L[4] 2. if \operatorname{len}(L)=4 then return \left\{\left(p_{i},{\mathcal{P}}_{h}(p_{i}),\theta_{v}t^{i-1}\right)\right\}_{i\in[l]} ( ∗ by Corollary 5.17 and ( 25 ) ∗ ) 3. if \operatorname{len}(L)=5 then return L[5] , \left\{\left(p_{i},{\mathcal{P}}_{h}(p_{i}),\theta_{v}t^{m+i-1}\right)\right\}_{i\in[l-1]} ( ∗ by Corollary 5.18 (i) and ( 26 ) ∗ ) 4. j\leftarrow L[5] 5. if \operatorname{len}(L)=7 and jv+w\neq 0 then (q_{1},Q_{1},\gamma_{1})\leftarrow L[6] for i from 2 to l do if i\neq j+1 then (q_{i},Q_{i},\gamma_{i})\leftarrow p_{i-1},{\mathcal{P}}_{h}(p_{i-1}),\theta_{v}t^{m+i-2} else (q_{i},Q_{i},\gamma_{i})\leftarrow L[7] return (q_{1},Q_{1},\gamma_{1}),(q_{2},Q_{2},\gamma_{2}),\ldots,(q_{l},Q_{l},\gamma_{l}) ( ∗ by Corollary 5.18 (ii) and ( 27 ) ∗ ) 6. 6.1. for i from 1 to j+1 do (q_{i},Q_{i},\gamma_{i})\leftarrow L[5+i] 6.2. for i from j+2 to l do (q_{i},Q_{i},\gamma_{i})\leftarrow p_{i},{\mathcal{P}}_{h}(p_{i-1}),\theta_{v}t^{m+i-2} 6.3. return (q_{1},Q_{1},\gamma_{1}),(q_{2},Q_{2},\gamma_{2}),\ldots,(q_{l},Q_{l},\gamma_{l}) ( ∗ by Corollary 5.18 (iii) and ( 28 ) ∗ ) The following algorithm computes the respective projections of a given element in F[t] to \operatorname{im}({\mathcal{P}}_{h}) and its complement induced by an initial sequence. Algorithm A.5 . PrimProj Input: f\in F[t] , the data in Convention 4.1 , and the initial sequence L of I_{h} output: (g,r)\in F[t]\times W s.t. f={\mathcal{P}}_{h}(g)+r , where W is the complement induced by L 1. u\leftarrow L[1] ( ∗ find the type ∗ ) 2. (g,r)\leftarrow an auxiliary pair of f by Algorithm A.1 ( ∗ auxiliary reduction ∗ ) 3. if u=0 or r=0 then return (g,r) ( ∗ I_{h}=\{0\} or the trivial projection ∗ ) 4. use Algorithm A.4 to compute the first k members (q_{1},Q_{1},\gamma_{1}),\ldots,(q_{k},Q_{k},\gamma_{k}) in the echelon sequence E induced by L s.t. other members in E are of degrees >\deg(r) 5. for i from k to 1 by -1 do c\leftarrow\gamma_{i}^{*}(Q_{i})^{-1}\gamma_{i}^{*}(r) , (g,r)\leftarrow g+cq_{i},r-cQ_{i} ( ∗ elimination ∗ ) 6. return (g,r) The first four steps of the above algorithm are evidently correct. Step 5 is correct by Lemma 2.11 and its proof. In step 6, r belongs to the complement of \operatorname{im}({\mathcal{P}}_{h}) induced by L , because \gamma_{i}^{*}(r)=0 for all i\in[k] and the pivot of the l th member does not appear in r for all l>k due to the choice of k in step 4. A.2 Algorithms in the hyperexponential case In this subsection, t is a regular monomial, and is hyperexponential over F , V_{h} is the auxiliary space given in Definition 6.3 , and J_{h} denotes the intersection of \operatorname{im}({\mathcal{P}}_{h}) and V_{h} . The elements \lambda_{k} and \mu_{l} of F are defined in Remark 6.1 (ii) and (iv), respectively. The first algorithm is for the auxiliary reduction in F[t,t^{-1}] . It is based on ( 18 ), ( 19 ), ( 20 ), ( 21 ) and the proof of Proposition 6.5 . Algorithm A.6 . HyperexpAuxRed Input: f\in F[t,t^{-1}] and the data in Convention 4.1 Output: (g,r) , an auxiliary pair of f w.r.t. (F[t,t^{-1}],{\mathcal{P}}_{h}) 1. p\leftarrow f^{+} , (k,p_{k})\leftarrow\operatorname{hdeg}(p),\operatorname{hc}(p), q\leftarrow f^{-} , (l,q_{l})\leftarrow\operatorname{tdeg}(q),\operatorname{tc}(q) , (g,r)\leftarrow 0,0 2. while k\geq m do if \nu_{\infty}(h)<0 then (u,v)\leftarrow a_{m}^{-1}p_{k}t^{k-m},0 , g\leftarrow g+u else (g_{k},r_{k})\leftarrow an R-pair of p_{k} w.r.t. \phi_{\lambda_{k-m}} , (u,v)\leftarrow g_{k}t^{k-m},r_{k}t^{k} , (g,r)\leftarrow g+u,\,r+v p\leftarrow p-{\mathcal{P}}_{h}(u)-v , (k,p_{k})\leftarrow\operatorname{hdeg}(p),\operatorname{hc}(p) ( ∗ by ( 18 ) and ( 19 ) ∗ ) 3. while l<0 do if \nu_{t}(h)<0 then (u,v)\leftarrow a_{0}^{-1}q_{l}t^{l},0 , g\leftarrow g+u else (g_{l},r_{l})\leftarrow an R-pair of b_{0}^{-1}q_{l} w.r.t. \phi_{\mu_{l}} (u,v)\leftarrow g_{l}t^{l},b_{0}r_{l}t^{l} , (g,r)\leftarrow g+u,r+v q\leftarrow q-{\mathcal{P}}_{h}(u)-v , (l,q_{l})\leftarrow\operatorname{tdeg}(q),\operatorname{tc}(q) ( ∗ by ( 20 ) and ( 21 ) ∗ ) 4. return (g,r+p+q) Next, we determine whether J_{h}=\{0\} , and find an echelon sequence of J_{h} with respect to (F[t,t^{-1}],{\mathcal{P}}_{h}) if J_{h}\neq\{0\} . The next algorithm is based on Propositions 6.13 and 6.14 . Algorithm A.7 . HyperexpEchSeq Input: the data in Convention 4.1 Output: nil if J_{h}=\{0\} , and an echelon sequence of J_{h} , otherwise. 1. M\leftarrow the type of J_{h} 2. if M=0 then return nil ( ∗ J_{n}=\{0\} ∗ ) 3. ( ∗ \dim(J_{h})=1 ∗ ) if \operatorname{len}(M)=1 then (k,u)\leftarrow M[1] ( ∗ find the type ∗ ) (g,r)\leftarrow the auxiliary pair of {\mathcal{P}}_{h}(ut^{k}) by Algorithm A.6 (p,P)\leftarrow ut^{k}-g,r , \theta\leftarrow an element of \Theta s.t. \operatorname{hc}(P)\notin\ker(\theta^{*}) return \left(p,P,\theta t^{\operatorname{hdeg}(P)}\right) ( ∗ by Proposition 6.14 (i) ∗ ) 4. ( ∗ \dim(J_{h})=2 ∗ ) (k,u)\leftarrow M[1] , (l,v)\leftarrow M[2] ( ∗ find the type ∗ ) 4.1. (g_{k},r_{k})\leftarrow the auxiliary pair of \mathcal{P}_{h}(ut^{k}) by Algorithm A.6 (g_{l},r_{l})\leftarrow the auxiliary pair of \mathcal{P}_{h}(vt^{l}) by Algorithm A.6 (p_{k},P_{k})\leftarrow ut^{k}-g_{k},r_{k} , (p_{l},P_{l})\leftarrow vt^{l}-g_{l},r_{l} ( ∗ by Proposition 6.13 (ii) ∗ ) 4.2. d_{k}\leftarrow\operatorname{hdeg}(P_{k}) , \theta_{k}\leftarrow an element of \Theta s.t. \operatorname{hc}(P_{k})\notin\ker(\theta_{k}^{*}) , \gamma_{k}\leftarrow\theta_{k}t^{d_{k}} c\leftarrow\gamma_{k}^{*}(P_{k})^{-1}\gamma_{k}(P_{l}) , (q,Q)\leftarrow p_{l}-cp_{k},P_{l}-cP_{k} , d\leftarrow\operatorname{hdeg}(Q) \theta\leftarrow an element of \Theta s.t. \operatorname{hc}(Q)\notin\ker(\theta) , \gamma\leftarrow\theta t^{d} , return (q,Q,\gamma),(p_{k},P_{k},\gamma_{k}) ( ∗ by Proposition 6.14 (ii) ∗ ) The last algorithm computes the respective projections of an element in F[t,t^{-1}] to \operatorname{im}({\mathcal{P}}_{h}) and the complement induced by an echelon sequence of J_{h} . It is simpler than Algorithm A.5 , because an echelon sequence of J_{h} has at most two members. So we merely provide a specification. Algorithm A.8 . HyperexpProj Input: f\in F[t,t^{-1}] , the data in Convention 4.1 , and an echelon sequence E of J_{h} Output: (g,r)\in F[t,t^{-1}]\times W s.t. f={\mathcal{P}}_{h}(g)+r , where W is the complement induced by E