François Boulier
email: francois.boulier@univ-lille1.fr

Joseph Lallemand
email: joseph.lallemand@ens-cachan.fr

François Lemaire
email: francois.lemaire@univ-lille1.fr

Georg Regensburger
email: georg.regensburger@ricam.oeaw.ac.at

Markus Rosenkranz
email: m.rosenkranz@kent.ac.uk

Additive Normal Forms and Integration of Differential Fractions

Keywords: Differential algebra, differential fraction, integration

This paper presents two new algorithms for integrating fractions of differential polynomials. In a previous work, the authors presented a method for decomposing a fraction as a fraction (the "non integrable part") plus the derivative of another fraction. In this paper, we rigorously formalize this notion of "non integrable part" and introduce a new normal form for decomposing a fraction as a sum of iterated derivations of fractions.

Introduction

This paper defines a new normal form of differential fractions, which are fractions of two differential polynomials, in differential algebra [START_REF] Ritt | Differential Algebra[END_REF][START_REF] Kolchin | Differential Algebra and Algebraic Groups[END_REF]. The differential polynomial ring R considered in this paper is as follows: one of its derivation is denoted δ ; one assumes that there exists an element x of R such that δx = 1 ; and K is its field of constants w.r.t. δ (see Section 2 for the rigorous assumptions on R). A major result of the paper is Proposition 14 which shows that any differential fraction F ∈ S can be decomposed as a sum:

F = P + ∞ i=0 δ i W i , (1)
where P ∈ K [x] is a polynomial, the W i are differential fractions in the set S F ⊂ S of the so-called "functional " fractions, and where only a finite number of W i are nonzero. Moreover, we provide Algorithm IteratedIntegrate for computing [START_REF] Ritt | Differential Algebra[END_REF] and prove in Proposition 14 that Decomposition (1) is unique and additive, i.e. that, if

F = P + ∞ i=0 δ i Wi
is the unique decomposition of some differential fraction F ∈ S then

F + F = (P + P ) + ∞ i=0 δ i (W i + Wi )
is the unique decomposition of F + F . More precisely, in terms of vector spaces, Proposition 14 shows that

S = K [x] ⊕ S F ⊕ δS F ⊕ δ 2 S F ⊕ • • •
where S is seen as a K -vector space. These results improve those of [START_REF] Boulier | On the integration of differential fractions[END_REF] since the decomposition provided in [START_REF] Boulier | On the integration of differential fractions[END_REF] depends on the implementation of Algorithm [3, integrate] and is not additive. Moreover, Algorithm [3, integrate] is flawed since it may not terminate over some inputs (see [START_REF] Boulier | An algorithm for converting nonlinear differential equations to integral equations with an application to parameters estimation from noisy data[END_REF]). Our results also extend [START_REF] Boulier | An algorithm for converting nonlinear differential equations to integral equations with an application to parameters estimation from noisy data[END_REF], which fixes the flaw in [3, integrate] but does not address the additivity property.

Even without the additivity property, algorithms for computing [START_REF] Ritt | Differential Algebra[END_REF] are important: they permit to reduce the size of formulas in the output of differential elimination methods (when polynomials are solved w.r.t their leading derivatives, the left-hand sides become differential fractions), they give more insight to understand the structure of an equation, and they lead to better numerical schemes in the context of parameter estimation problems over noisy data, from the input-output equations, because they permit to replace, at least partially, numerical derivation methods by numerical integration ones. See [START_REF] Boulier | An algorithm for converting nonlinear differential equations to integral equations with an application to parameters estimation from noisy data[END_REF] for details. It is worth mentioning that working with fractions instead of polynomials yield more freedom by adjusting the denominators. Indeed, Decomposition (1) highly depends on the denominator of F , i.e. the decomposition of F/Q, where Q is a polynomial, can be completely different from the decomposition of F . Finding a suitable Q is a difficult task and depends on the application (in the context of [START_REF] Boulier | On the integration of differential fractions[END_REF], the goal was to obtain order zero W i ).

Variants of Decomposition (1) can be easily obtained, e.g. by bounding the value of i. Bounding i by 1, a unique decomposition of a fraction F can be defined by

F = W + δR ( 2
)
where W is a functional fraction, and R is a fraction. Actually, Decomposition [START_REF] Ritt | Differential Algebra[END_REF] is in practice obtained by iterating Decomposition [START_REF] Kolchin | Differential Algebra and Algebraic Groups[END_REF]. Note that Decomposition ( 2) is related to the decomposition of ordinary differential polynomials [START_REF] Gao | Decomposition of ordinary differential polynomials[END_REF][START_REF] Gao | Decomposition of differential polynomials with constant coefficients[END_REF] in the particular case where F is polynomial and W is zero.

The additional additivity property is also very interesting since it provides more intrinsic (i.e. not algorithm dependent) formulas and makes it simpler to study linear dependencies between differential fractions (see Remark 8): given k differential fractions F 1 , F 2 , . . . , F k , how to find k coefficients α 1 , α 2 , . . . , α k in K such that

F = α 1 F 1 + α 2 F 2 + • • • + α k F k
is the derivative δ G of some unknown differential fraction G ? Thanks to the additivity property, it is now sufficient to decompose each F i as W i + δR i as in [START_REF] Kolchin | Differential Algebra and Algebraic Groups[END_REF], and look for coefficients in K such that

α 1 W 1 + α 2 W 2 + • • • + α k W k = 0 .
Suitable techniques for finding linear dependences between fractions is described in [START_REF] Boulier | Finding first integrals using normal forms modulo differential regular chains[END_REF]. Moreover, this might give an alternative for the problems addressed in [START_REF] Raab | Integration of unspecified functions and families of iterated integrals[END_REF].

More generally, the additivity property is a further step towards an algorithmic elimination theory of integro-differential polynomials, as stated in the conclusion of [START_REF] Boulier | On the integration of differential fractions[END_REF].

Finally, all algorithms presented in this paper were implemented in Maple, using the DifferentialAlgebra package [START_REF] Boulier | Help Pages of the DifferentialAlgebra Package[END_REF].

The rest of the paper is organized as follows. Basic notions of differential algebra, the decomposition of a multivariate fraction and a slight variant of the Hermite method for decomposing a fraction in the univariate case are reviewed in Section 2.

Section 3 is mainly a generalization of [START_REF] Bilge | A REDUCE program for the integration of differential polynomials[END_REF] to the context of differential algebra (partial derivations and general rankings are handled). Functional monomials and polynomials are defined. The section finally introduces Algorithm polyIntegrate which performs Decomposition (2) in the polynomial case (i.e. when F is a polynomial in R).

Section 4 provides proofs of the existence and uniqueness of Decomposition (2) for differential fractions, and presents Algorithm Integrate for computing it. As opposed to the polynomial case, the fractional case is surprisingly difficult. Functional fractions are defined in Section 4.1. The term R in (2) is defined up to a constant. In order to make it unique, the notions of polynomial part and constant term of a fraction are introduced in Section 4.2. Algorithm Integrate is presented in Section 4.3, as well as its proof.

Finally, the existence and uniqueness of Decomposition ( 1) is proved in Section 5 (Proposition 14), and Algorithm IteratedIntegrate, which computes it, is presented.

Preliminaries

Differential Algebra Tools

Reference textbooks are [START_REF] Ritt | Differential Algebra[END_REF] and [START_REF] Kolchin | Differential Algebra and Algebraic Groups[END_REF]. A differential ring R is a ring endowed with finitely many, say m, derivations δ 1 , . . . , δ m , i.e., unary operations satisfying the following axioms, for all A, B ∈ R:

δ(A + B) = δ(A) + δ(B) , δ(A B) = δ(A) B + A δ(B) ,
and which commute pairwise. The derivations generate a commutative monoid w.r.t. composition denoted by

Θ = {δ a1 1 • • • δ am m | a 1 , . . . , a m ∈ N} ,
where N stands for the nonnegative integers. The elements of Θ are called derivation operators.

If θ = δ a1 1 • • • δ am m is a derivation operator then ord(θ) = a 1 +• • •+a m denotes
its order, with a i being the order of θ w.r.t. derivation δ i . In order to form differential polynomials, let us introduce a set U = {u 1 , . . . , u n } of n differential indeterminates. The monoid Θ acts on U , giving the infinite set ΘU of derivatives. For readability, we often index derivations by letters like δ x and δ y , denoting also the corresponding derivatives by these subscripts, so u xy denotes δ x δ y u.

In the rest of the paper, δ is a distinguished derivation. Without loss of generality, we assume that δ = δ 1 . Let us assume there exists an independent variable x such that δx = 1 and δ i x = 0 for all i ≥ 2. We consider the differential ring R = K [{x} ∪ ΘU ] where K is a field containing Q such that δa = 0 for all a in K . Due to axioms of derivations, the derivative δ acts on elements of R in the following way:

δ = ∂ ∂x + w∈ΘU (δw) ∂ ∂w • (3)
A ranking is a total ordering on ΘU that satisfies the two following axioms:

1. v ≤ θv for every v ∈ ΘU and θ ∈ Θ, 2. v < w ⇒ θv < θw for every v, w ∈ ΘU and θ ∈ Θ.

Rankings are well-orderings, i.e., every strictly decreasing sequence of elements of ΘU is finite [2, §I.8]. From now on, we assume a ranking is fixed. In the sequel, it will sometimes be emphasized that some notions are ranking dependent by referring to this fixed ranking. Let P be a differential polynomial in

R \ K [x].
The leading derivative, or leader, of P , denoted ld(P ), is the highest derivative v such that d = deg(P, v) is nonzero. The monomial v d is the rank of P . The leading coefficient of P w.r.t. v is the initial of P , and it is denoted i P . The differential polynomial ∂P/∂v is the separant of P . A rank u d is said to be lower than a rank v e if u < v or both u = v and d < e. The ordering on the ranks is also a well-ordering. Differential fractions are defined as quotients of differential polynomials i.e. elements of S = K ({x} ∪ ΘU ). The leader of a differential fraction F in S \ K (x) is defined as the greatest derivative v such ∂F ∂v = 0. Let F be a polynomial in some variable y. One denotes val(F, y) the valuation of F w.r.t. y i.e. the minimum degree in y of all monomials occurring in F , if F = 0, and ∞ if F = 0. Let F/G be a nonzero fraction and y a variable (in the differential context, a variable is either the independent variable or a derivative). The degree of F/G w.r.t. y is defined by deg(F/G, y) = deg(F, y) -deg(G, y). If the fraction F is zero, then deg(F, y) = -∞. One easily notices that the definition of the degree of a fraction does not depend on the chosen representative of the fraction. Moreover, as in the polynomial case, for any fractions A and B, one has

deg(A + B, y) ≤ max{deg(A, y), deg(B, y)} (4)
with equality if deg(A, y) = deg(B, y). Finally, polynomials and fractions are denoted with uppercase letters (A, B, . . .), and derivatives as well as independent variables are denoted with lowercase letters (u, v, . . . , x, y 1 , . . .).

Multivariate Partial Fraction Decomposition

Since an antiderivative (or primitive) is only defined up to a constant, we introduce the constant term of a multivariate fraction as well as its polynomial part. These notions rely on the generalization to multivariate fractions of the partial fraction decomposition [START_REF] Stoutemyer | Multivariate partial fraction expansion[END_REF]. We present a slight modification of Stoutemyer's multivariate decomposition of a fraction in order to guarantee some uniqueness property. We however do not recall the complete algorithm since we will only need to compute constant terms and polynomial parts of fractions.

Following essentially [START_REF] Stoutemyer | Multivariate partial fraction expansion[END_REF], we consider multivariate partial decompositions for multivariate fractions in the variables y i ordered by y 1 > y 2 > • • • > y s . Accordingly, the main variable of a polynomial p is defined as the highest variable y i such that deg(p, y i ) > 0. In order to completely normalize the representative of a reduced fraction, it suffices to normalize one of its coefficients. This is achieved using the notions of admissible orderings and leading coefficients in the Gröbner basis sense [12, chap. 2].

Definition 1 (Multivariate partial fraction). Consider a field A of characteristic 0 and an admissible ordering. Take an irreducible fraction P/Q in A (y 1 , . . . , y s ) with

Q = Q a1 1 • • • Q ar r
where each Q i is an irreducible factor in A [y 1 , . . . , y s ] and each a i is a positive integer. The fraction P/Q is called a multivariate partial fraction if it satisfies the conditions:

1. i = j implies Q i and Q j have different main variables (for the chosen ordering y 1 > y 2 > • • • > y s ), 2. the leading coefficient of each Q i for the admissible ordering is equal to 1, 3. for each 1 ≤ i ≤ r, one has deg(P, ȳ) < deg(Q i , ȳ) where ȳ is the main variable of Q i .

Lemma 1. Consider a field A of characteristic 0 and an admissible ordering. Any multivariate fraction F of A (y 1 , . . . , y s ) can be written as a unique sum of multivariate partial fractions with pairwise distinct denominators. The sum is called the multivariate partial decomposition of F .

Proof. See [START_REF] Stoutemyer | Multivariate partial fraction expansion[END_REF].

Remark 1. Lemma 1 slightly strengthens [START_REF] Stoutemyer | Multivariate partial fraction expansion[END_REF] by ensuring a unique decomposition as well as making the P and Q unique (thanks to the item 2 of Definition 1).

Remark 2. The condition deg(P, ȳ) < deg(Q i , ȳ) could be relaxed to deg(P, ȳ) < deg(Q ai i , ȳ), following the remark of [11, page 208] stating: "In that case, 'degree of P ' should be replaced with 'degree of P n ' in property b of Definition 1". In practice, this relaxed condition leads to fewer terms in the decomposition.

Example 1 sketches the computation of the decomposition of some fraction.

Example 1. In this example, A = Q and the admissible ordering is the lexicographic ordering given by y 1 > y 2 . The decomposition of

F = y2 (y 2 1 +1)(y1+y2) is F = y 2 (y 1 + y 2 )(y 2 2 + 1) + 1 y 2 1 + 1 + -y 1 y 2 -1 (y 2 1 + 1)(y 2 2 + 1)
• It is obtained by first computing a partial fraction decomposition w.r.t. y 1 yielding

F = y 2 (y 1 + y 2 )(y 2 2 + 1) - (y 1 -y 2 )y 2 (y 2
1 + 1)(y 2 2 + 1) and then computing a partial fraction decomposition w.r.t. y 2 on each term after removing the factor in y 1 in the denominator (i.e. computing a partial fraction decomposition w.r.t. y 2 on y2 y 2 2 +1 and (y1-y2)y2

y 2 2 +1 ).
Remark 3. Please note that unlike in the univariate case, the irreducible factors of the denominators in the decomposition of a fraction F do not necessarily divide the denominator of F . In Example 1 the factor (y 2 2 + 1) in the final decomposition does not divide the denominator of F . Definition 2 (Polynomial part and constant term of a multivariate fraction). Keep the assumptions of Lemma 1 and take F ∈ A (y 1 , . . . , y s ). The unique multivariate partial fraction P/Q of the multivariate decomposition of F satisfying Q = 1 is called the polynomial part of F (it belongs to A [y 1 , . . . , y s ]). The term of degree 0 w.r.t. the y i of the polynomial part of F is called the constant term of F (it belongs to A ). Remark 4. The polynomial part as well as the constant term of a fraction F do not depend on the admissible ordering. However, they depend on the ordering y 1 > • • • > y s . Consider the fraction F whose multivariate decomposition for y 1 > y 2 is

y 1 y 2 + y 2 y 1 + y 2 •
Its polynomial part and its constant term are equal to y 1 y 2 and 0 for y 1 > y 2 . However, the polynomial part and the constant term of the same F for the ordering y 2 > y 1 are y 1 y 2 + 1 and 1 since the decomposition of F for y 2 > y 1 is

y 1 y 2 + 1 - y 1 y 1 + y 2 • Lemma 2.
Consider a field A of characteristic 0 and an admissible ordering. Take two fractions F and G in A (y 1 , . . . , y s ) and consider a linear combination H = αF + βG for some α and β in A . Denote s i=1 F i and t j=1 G i the respective multivariate partial fraction decompositions of F and G. By grouping the F i and G j with the same denominators, the multivariate partial fraction decomposition of H can be obtained from those of F and G as follows:

H = (i,j)∈I F G αFi+βGj =0 (αF i + βG j ) + i∈I F αF i + j∈I G βG j (5)
where

-I F G is the set of couples (i, j) such that F i and G j have the same denomi- nators -I F is the set of the integers 1 ≤ i ≤ s such that (i, j) / ∈ I F G for all 1 ≤ j ≤ t -I G is the set of the integers 1 ≤ j ≤ t such that (i, j) / ∈ I F G for all 1 ≤ i ≤ s.
Proof. By construction of I F G and I F , each integer 1 ≤ i ≤ s is either in the first component of an element of I F G or belongs to I F . With a similar argument on I F G and I G , the right hand side of Equation ( 5) equals αF + βG. It is also clear that each term of the form αF i + βG j is a multivariate partial fraction because F i and G j have the same denominators. Thus Equation ( 5) is the multivariate partial fraction decomposition of H.

Corollary 1. The polynomial part and constant term operations are A -linear.

Proof. This is a direct consequence of Lemma 2.

The Hermite Algorithm

Let us first borrow two definitions from [13, Definition 1.7.

∈ A [y] \ A such that Q 2 divides P in A [y].
Definition 4 (Squarefree factorization). Consider a unique factorization domain A and a polynomial P in A [y]. A squarefree factorization of P is a factorization of the form P = P 1 P 2 2 • • • P t t where each P i is squarefree and gcd(P i , P j ) ∈ A for i = j.

Our integration problem contains as a subproblem the well known problem of integrating a univariate fraction. Indeed, integrating ∂F ∂u w.r.t. u to retrieve F can be done by integrating u x ∂F ∂u w.r.t. x since δF = u x ∂F ∂u . Given a univariate fraction F in the variable u, the Hermite reduction computes two fractions W and R such that F = W + ∂R ∂u , deg(W, u) < 0, and W has a squarefree denominator. See for example the different variants of Algorithm HermiteReduce given in [13, page 40], [13, page 41], and [13, page 44].

In order to ensure the uniqueness of the Hermite reduction (R, W ), we also require that R has a zero constant term w.r.t. the variable u (in the sense of Definition 2). In the univariate case, this last condition is equivalent to the simple condition: if R is a polynomial in u, the term of degree 0 of R is zero ; if R = A/B is a fraction with deg(B, u) > 0, by writing R = P + Ā/B where P and Ā are polynomials such that deg(A, u) < deg(B, u), the term of degree 0 of P is zero.

This paper relies on Algorithm Hermite, based on a slight modification of [START_REF] Bronstein | Symbolic Integration I[END_REF]Algorithm HermiteReduce,page 44]. Algorithm Hermite performs an extra division to ensure that R has a zero constant term, since we could not easily deduce from the code of [13, Algorithm HermiteReduce, page 44] whether this last condition is true or not.

Input: F a univariate fraction in u Output: the unique pair of fractions (W, R) such that F = W + ∂R ∂u , deg(W, u) < 0, the denominator of W is squarefree, and R has a zero constant term.

1 begin 2 compute (W, R) using [13, HermiteReduce, page 44] such that F = W + ∂ R ∂u ;
3 remove from R its constant term (w.r.t u) (e.g. using an Euclidean division) thus obtaining R ;

4 return (W, R) Algorithm 1: Hermite(F, u)
Algorithm Hermite is actually a non differential algorithm, and it will be called later by Integrate with a parameter u which can be either a derivative or the independent variable x. • One easily checks that F = W + ∂R ∂y , deg(W, y) < 0, W has a square free denominator and R (seen as a univariate fraction in y) has a zero constant term.

Polynomial Integration

This section is mainly a generalization of [START_REF] Bilge | A REDUCE program for the integration of differential polynomials[END_REF] to the context of differential algebra. In particular, partial derivations and general rankings are handled.

The differential ring R can be seen as a K -vector space. The set δR is trivially a proper vector subspace of R; it represents the set of all differential polynomials which are derivatives of some differential polynomial.

Suppose we fix a complementary vector space F to δR in order to have R = F ⊕ δR. Then integrating a differential polynomial P can be seen as projecting P on F and δR, yielding a unique decomposition (W, Q) ∈ F × δR such that P = W + Q, where W is the "non integrable" part, and Q is the integrable part. The vector space F is not unique and has to be chosen. In this section, we show that F can be chosen as R F which denotes the set of functional polynomials (see Definition 6). The choice of the letter F in R F comes from the term functional which is used by [START_REF] Bilge | A REDUCE program for the integration of differential polynomials[END_REF] after being introduced by [START_REF] Gel'fand | Fractional powers of operators and hamiltonian systems[END_REF].

Functional and Integrable Monomials

We must distinguish between the integrable and functional (= non integrable) parts of a differential polynomial. In the case of differential polynomials, the most natural way to achieve this is on a monomial-by-monomial basis, guided by the following discussion. Consider a monomial M = x e v d1 1 • • • v ds s where e ≥ 0, s > 0, the d i are positive, the v i are derivatives sorted by

v 1 > v 2 > • • • > v s
for a chosen ranking. Due to the axioms of rankings, δM is equal to

M 2 = d 1 x e (δv 1 )v d1-1 1 v d2 2 • • • v ds
s plus other monomials with leaders strictly less than δv 1 . The monomial M 2 has very special properties. Its leader δv 1 appears with an exponent 1 and it belongs to δ(ΘU ). Moreover, ld M 2 = δv 1 ≥ δv for all derivatives v occurring in M 2 such that v = ld M 2 . This discussion leads naturally to the following definitions.

Definition 5 (Functional and integrable monomials). Consider a ranking. Consider a monomial

M = x e v d1 1 • • • v ds
s where e ≥ 0, the d i are positive, the v i are derivatives sorted by v 1 > v 2 > • • • > v s for the considered ranking. The monomial M is said to be integrable w.r.t. x and the ranking, if

(s = 0) or v 1 ∈ δ(ΘU ) and d 1 = 1 and (s = 1 or δv 2 ≤ v 1 ) , (6)
In the opposite case, that is if

(s ≥ 1) and v 1 / ∈ δ(ΘU ) or d 1 > 1 or (s ≥ 2 and δv 2 > v 1 ) , (7)
M is said to be functional w.r.t. x and the ranking.

Definition 6 (Functional polynomial). Consider a ranking. A differential polynomial P is said to be functional w.r.t. x and the ranking if it can be written as a linear combination over K of functional monomials w.r.t. x and the ranking. The set of functional polynomials is denoted by

R F . Example 3. Consider the ranking u < v < u x < v x < u y < v y < u xx < • • • . The monomials xv, u 2 x u, u x v, v y u y are functional (w.r.t.
x and the ranking). The monomials x, u x u, v x u, u xx v, xv xx u 2

x u are integrable (w.r.t. x and the ranking).

The notion of functional monomial clearly depends on the chosen x and the chosen ranking, so a monomial may be functional for some x and some ranking, but not for another choice of x or another ranking. In the rest of the paper, the dependency w.r.t. x and the ranking will be simply omitted when there is no ambiguity.

The following example gives some insight on how the functional and integral parts of a polynomial will be extracted.

Example 4. Following Example 3, each of the integrable monomials

u x u, v x u, u xx v, v xx u 2
x ux can be rewritten as the derivative of some monomial (times a constant) plus a linear combination of monomials with smaller leaders:

-u x u = 1 2 δ(u 2 ), v x u = δ(vu) -u x v, u xx v = δ(u x v) -v x u x , -xv xx u 2 x u = δ(xv x u 2 x u) -2xv x u xx u x u -xv x u 3 x -v x u 2 x u.
Note that some functional monomials can be written in a similar way. An example is given by:

u x v = δ(uv) -v x u where u x v is functional. However, one has ld(u x v) = u x < v x = ld(v x u).
Continuing the process would lead to an infinite loop since

u x v = δ(uv) -v x u = δ(uv) -(δ(uv) -u x v) = u x v = • • • .
In order to achieve a finite rewriting process (as Algorithm polyIntegrate will do), it is better not to rewrite the functional monomials.

The polyIntegrate

Algorithm Proposition 1. We have R F ∩ δR = {0}.
Proof. Let us assume P ∈ R F ∩ δR and P = 0. We show that P involves at least one integrable monomial. This contradiction with the hypothesis P ∈ R F will prove the proposition. Since P ∈ R F and P = 0, one has P / ∈ K [x] (condition s ≥ 1 in ( 7)). Denote v = ld P . Since P ∈ δR, there exists P with leader v such that P = δ P and, by the axioms of rankings, v = δv. Consider the formula

P = δ P = v ∂ P ∂v + w∈E,w =v (δw) ∂ P ∂w + ∂ P ∂x ( 8
)
where E denotes the set of the derivatives occurring in P . Consider any monomial M occurring in P , such that ld M = v (such a monomial exists since v = ld P ). By the axioms of rankings, M must occur in v ∂ P ∂ v . Thus deg(M, v) = 1. Moreover, any derivative w = v such that deg(M, w) > 0 satisfies w ≤ v hence, by the axioms of rankings, δw ≤ v. The monomial M is thus integrable since all conditions of (6) are fulfilled (v playing the role of v 1 in (6)), contradicting the hypothesis P ∈ R F .

We now introduce Algorithm polyIntegrate and prove its correctness and termination. write iP as iP ≤ + iP > where iP > is the polynomial involving all monomials of iP whose leaders are strictly greater than v ;

12

R := v 0 iP ≤ dv ; 13 return (iP > v, R) + polyIntegrate(P -iP > v -δR) ;
Algorithm 2: polyIntegrate(P ) a polynomial either in K [x] or of strictly smaller rank than that of P . Indeed, the first call at line 8 calls polyIntegrate with P -i P v d . The second call at line 13 calls polyIntegrate with P -i P> v -δR, which is free of v: δR has the form i P ≤ v plus terms with leader strictly smaller than v, thus the term i P v of P is canceled by i P> v + δR.

Proposition 3. Algorithm polyIntegrate computes a pair (W, R) in R F ×R such that P = W + δR, and R (viewed as a polynomial over K ) has no degree zero term.

Proof. The proposition is proven by induction on the rank of P . The proposition holds for any polynomial in K [x]. Assume the proposition holds for any polynomial in K [x] and any polynomial in R whose rank is strictly less than v d . Let us prove it also holds for P ∈ R with rank v d . Suppose that the condition at line 6 is true. Thus, i P v d is a functional polynomial. Denote ( W , R) = polyIntegrate(P -i P v d ), which is properly defined thanks to Proposition 2. By induction, one has P -i P v d = W + δ R where R has no degree zero term. The algorithm returns (i P v d + W , R). Then,

(i P v d + W ) + δ R = i P v d + ( W + δ R) = i P v d + (P -i P v d ) = P . Since
W is a functional polynomial, so is i P v d + W . This concludes the case when the condition at line 6 is true.

Suppose now that the condition at line 6 is not true. Then, the derivative v is well defined at line 10, and the rank of P is v. Denote ( W , R) = polyIntegrate(Pi P> v -δR). By induction, one has P -i P> v -δR = W + δ R where R has no degree zero term. The algorithm returns (i

P> v + W , R + R). Then (i P> v + W ) + δ(R + R) = (i P> v + δR) + ( W + δ R) = (i P> v + δR) + (P -i P> v -δR) = P .
Since i P> v is a functional polynomial, so is i P> v + W . Moreover, R and R have no degree zero terms. This concludes the induction proof.

< v < u x < v x < u y < v y < u xx < v xx < u xy < • • • and take K = Q(a, y). -polyIntegrate(u x v) = (u x v, 0), -polyIntegrate(v x u) = (-u x v, uv), -polyIntegrate(a + x 2 + v xx u + u 2 ) = (-v x u x + u 2 , ax + x 3 /3 + uv x ), -polyIntegrate(u x u + axv x ) = (-av, u 2 /2 + axv), -polyIntegrate(u xy + 2u y ) = (2u y , u x ).

Fraction Integration

The algorithm presented in [START_REF] Boulier | On the integration of differential fractions[END_REF] is not additive, as shown by [START_REF] Boulier | On the integration of differential fractions[END_REF]Example 4]. This issue is solved in this section. The development of this section is similar to that of Section 3. Section 4.1 introduces the so-called functional monomial fractions (resp. the set S F of functional fractions) which are the generalization of the functional monomials (resp. the set R F of functional polynomials) for the differential fractions. After defining the polynomial part, the nondifferential polynomial part and the constant term of a differential fraction, Algorithm Integrate (Algorithm 4) is presented. It is the generalization of polyIntegrate for differential fractions. Anticipating slightly on the definitions, for any fraction F of S , Integrate(F ) returns the unique couple (W, R) such that F = W + δR, W is a functional fraction and R has a zero constant term (to ensure uniqueness of R). The main difficulty was to find a proper definition of functional fractions, as well as the associated algorithm Integrate.

Functional Fractions

Definition 7 (Functional monomial fraction, FMF). Consider a ranking. A (irreducible) fraction M/Q in S where M is a monomial is said to be a functional monomial fraction (FMF in short) w.r.t. x for the ranking if one of the following cases is satisfied:

C1 both M and Q are in K [x], deg(M, x) < deg(Q, x), and Q is squarefree, C2 M is a functional monomial and Q is in K [x], C3 Q is not in K [x] (denote its leader by v), deg(M, v) < deg(Q, v). Moreover,
one of the following subcases is satisfied:

C3.1 M is a functional monomial, C3.2 M is an integrable monomial, M / ∈ K [x]
, ld(M ) = δv and Q is squarefree w.r.t. v, C3.3 M is an integrable monomial and either M ∈ K [x] or ld(M ) < δv.

In this paper, we have chosen not to introduce any logarithm. For this reason, fractions of type C1 are functional.

Example 6. Take the ranking u < v < u x < v x < u y < v y < u xx < v xx < u xy < • • • . The fraction 3x x 2 -

Definition 8 (Functional fraction).

A fraction is said to be functional if it can be written as a linear combination of FMF over K . The set of functional fractions is denoted S F . Remark 5. Functional monomials are special cases of FMF of type C2 (by taking Q ∈ K ). Consequently, the functional polynomials are special cases of functional fractions (i.e. R F ⊂ S F ). Remark 6. Unlike the functional monomials, the FMF are not linearly independent over K , as shown by the following example, involving only FMF of type C2:

0 = u (x -y)(y -z) + u (y -z)(z -x) + u (z -x)(x -y) •
As a consequence, the FMF do not form a K -basis of the functional fractions. However, this does not raise any problem in our paper. Indeed, we are mainly interested in computing functional fractions, but we do not need to decompose those functional fractions in a basis.

Checking that a fraction is functional is not immediate as opposed to the polynomial case, because of Remark 6. To this extent, we will need to rely on Algorithm Integrate and admit for the moment the following consequences of Proposition 13:

for any differential fraction F , Algorithm Integrate computes a couple (W, R) where W and R are differential fractions, F = W + δR, and W is functional a fraction F is functional if and only if Algorithm Integrate returns (F, 0) (i.e. W = F and R = 0)

Example 7. Take the ranking u < v < u x < v x < u y < v y < u xx < v xx < u xy < • • • . The fraction F 1 = u 2 v 2 -v 4 +2uvx u 2 -v 2
is a functional fraction since it is equal to

v 2 + vx u-v + vx u+v , which is a sum of three FMF. The fraction F 2 = vx(u 2 v 2 -v 4 +2u) u 2 -v 2
can be written as v x v 2 + vx u-v + vx u+v • The fraction F 2 is not functional. Indeed Algorithm Integrate rewrites F 2 as F 2 = W + δR where W = vx u-v + vx u+v and R = v 3 3 • Thus F 2 is not functional since R = 0. Example 7 shows that it does not seem straightforward to directly define functional fractions by comparing leading derivatives and degrees as in Definition 7. Indeed, fractions F 1 and F 2 in Example 7 have similar properties in terms of degrees and have the same denominator, but F 1 is functional whereas F 2 is not.

Example 8. Consider the fraction

F = vxx ux+1 + u ux-1 • Algorithm Integrate com- putes F = W + δR, where W = uxxvx (ux+1) 2 + u ux-1 and R = vx ux+1 • Thus, F is not functional since R = 0.
Example 8 shows that FMF cannot be defined by simply assuming that the denominator is squarefree. Even if the FMF do not form a K -basis (see Remark 6), the cancellations that can occur between FMF is not totally random, mainly because of the degree conditions in Definition 7. This statement is made precise in Proposition 7 below. Lemma 3. Consider a FMF F = M/Q ∈ S \ K (x) and take u = ld(F ). Thus F cannot be of type C1 since F / ∈ K (x). Then, denoting d = deg(F, u), exactly one of the two following conditions is satisfied: Lemma 4. Consider a variable y, a polynomial F + in y with val(F + , y) > 0, some element F 0 free of y, and a fraction F -with deg(F -, y) < 0, such that

Case d ≥ 1: u = ld M , deg(M, u) = d and F has the form u d M /Q where M /Q is free of u, Case d < 0: deg(M, u) < deg(Q, u).
F + + F 0 + F -= 0. Then F + = F 0 = F -= 0.
Proof. Assume that F + is non zero. Then its degree is positive. It implies deg(F 0 + F -, y) > 0 which contradicts deg(F 0 + F -, y) ≤ 0 (by Condition ( 4)). Thus, F + is necessarily zero. Assume now that F -is non zero. It implies that the degree of F -is negative and different from -∞, which implies deg(F 0 , y) is not -∞. This contradicts the assumption that deg(F 0 , y) = -∞ since F 0 is free y. Consequently F -is also zero, and F 0 is zero as well.

Proposition 7. Consider a linear combination F = s i=1 α i F i over K , where the F i are FMF. If all F i are of type C1 and F is free of x, then F is zero. Similarly, if all F i are of type C2 or C3 with the same leader v, and F is free of v, then F is zero.

Proof. Assume all F i are of type C1 and F is free of x. Because of the degree condition of C1 in Definition 7 and by Condition (4) of page 5, if F is non zero, then it is necessary a fraction of negative degree in x. This leads to a contradiction since F is free of x, so F has to be zero. Now assume that all F i are of type C2 or C3 and have the same leader v. By viewing the F i as univariate fractions in v (with coefficients in some fraction field), and using Lemma 3, each F i is either a monomial in v with a positive degree or a fraction with a negative degree. Without loss of generality, assume that the t first F i are the monomials in v and the other F i are the fractions in v. Then F - Proposition 8. Take a nonzero fraction F in S F . If F ∈ K (x), then F can be written as a linear combination over K of FMF of type C1. Otherwise, F can be written as a linear combination over K of FMF either in K (x) or with leaders less than or equal to ld(F ).

t i=1 α i F i - s i=t+1 α i F i = 0. By applying Lemma 4 with F + = - t i=1 α i F i , F 0 = F , F -= -
Proof. Take F in K (x) ∩ S F . If F is a linear combination of FMF of type C1 only, then the proof is completed. Otherwise, suppose that F is a linear combination involving at least a FMF of type C2 or C3. Denote v the highest leader of the FMF of type C2 or C3 in the combination. By grouping the FMF with leaders less than v, one has F = F + p i=1 α i F i where F is a fraction free of v, the α i are in K , and where all the F i are FMF of type C2 or C3 with leaders v. Since both F and F are free of v, Proposition 7 ensures that F = F . Consequently, F can be written as a linear combination of FMF in K (x) or with leaders strictly less than v. By an induction argument, since F ∈ K (x), F can be written as a linear combination of FMF of type C1.

A similar induction process can be applied when F / ∈ K (x).

Polynomial Parts and Constant Term of a Differential Fraction

To make the output of Integrate canonical, we ensure that the value of the integrated part has a zero constant term: a notion which needs to be defined for differential fractions.

Definition 9 (polynomial part, nondifferential polynomial part, and constant term of a differential fraction). Consider a ranking. Extend the ranking by taking x smaller than any derivative. Take F ∈ S and consider F as a fraction in x and ΘU over the field K . The polynomial part and constant term of the differential fraction F w.r.t. x and the ranking are defined as in Section 2.2, by taking A = K and Y = {x, ΘU }, and by using the extended ranking mentioned above. They respectively belong to K [x, ΘU ] and K . Moreover, the nondifferential polynomial part of F , denoted nondiffPolyPart(F ), is defined as the zero degree term of the polynomial part of F seen as a polynomial in the ΘU . It belongs to K

[x].
The computation of the nondifferential polynomial part will be needed for ensuring the termination of the iterated integration presented in Section 5 (since a polynomial in x can be integrated infinitely many times). The notions defined in Definition 9 depend on x and the ranking, as the polynomial part and the constant term of a multivariate fraction depend on the ordering (see Remark 4). From now on, this dependency will not be mentioned if there is no possible confusion.

A = u 2 x 2 abu 2 x + u 2 x 2 ab 2 + xbu 2 x + xb 2 + x 3 au 2 x + x 3 ab + b 3 xau 2 x + b 4 xa + abu 2 x + ab 2 + u x xab.
The multivariate partial decomposition of F (w.r.t. x and the ranking) is

F = u 2 x + x 2 b + b 2 + 1 a + 1 x + u x u 2 x + u , the polynomial part is u 2 x + x 2 b + b 2 + 1 a , the nondifferential polynomial part is x 2 b + b 2 + 1 a ,
p =(y 2 + k e ) 2 ÿ + ((k 1 + k 2 ) y 2 + 2 k e (k 1 + k 2 ) y + k 2 e (k 1 + k 2 ) + k e V e ) ẏ+ y k 2 k e V e + y 2 k 2 V e .

Take the fraction

F io = p (y 2 + k e ) 2 . The multivariate decomposition of F io is ÿ + (k 1 + k 2 ) ẏ + k 2 V e - k 2 k e V e y + k e + k e V e ẏ (y + k e ) 2 ,
its polynomial part is ÿ + (k 1 + k 2 ) ẏ + k 2 V e , its nondifferential polynomial part is k 2 V e and its constant term is also k 2 V e .
The nondifferential polynomial part can be computed by Algorithm 3, which avoids computing the multivariate partial fraction decomposition. Indeed, we follow the method from [START_REF] Stoutemyer | Multivariate partial fraction expansion[END_REF], but only compute the polynomial part at each step (using Euclidean division of polynomials), thus ignoring terms with a non constant denominator. be a fraction (with n > 0) where v is a derivative in ΘU such that deg(A, v) = deg(B, v) = 0 (this condition holds in particular if v is strictly greater than all derivatives involved in A and B). Then, the nondifferential polynomial part and the constant term of F are zero.

Input: F a differential fraction Output: the nondifferential polynomial part of F 1 begin 2 G := F ; 3 while denom(G) / ∈ K [x] do
Proof. The hypothesis deg(A, v) = deg(B, v) = 0 ensures that if Q and R are the quotient and remainder of A by B w.r.t. ld(denom(B)), then v n Q and v n R are the quotient and remainder of v n A by B. Following Algorithm 3, the polynomial G after line 6 has the form v n P , where P is a polynomial. Thus, both the nondifferential polynomial part and the constant term are zero. Proof. This is a direct consequence of Lemma 5 and the linearity of the nondifferential polynomial part (see Remark 7).

Corollary 2. If F = d i=1 Ai Bi v i , and if deg(A i , v) = deg(B i , v) = 0 for each 1 ≤ i ≤ d,

Ai

Bi v i has a zero nondifferential polynomial part. If F is zero, the lemma is proven. Now assume F is not zero. Following Algorithm 3 and using the assumption deg(F, v) < 0, the fraction G is zero after the first execution of Line 5. Thus F has a zero nondifferential polynomial part, and the lemma is proven.

The Integrate Algorithm

This section proves that S = S F ⊕ δS . Moreover Algorithm Integrate is presented and proven. Proposition 9. Let G = P Q be a univariate irreducible fraction in A (x) where A is a unique factorization domain and Q satisfies deg(Q, x) > 0. Denote by

Q = A 1 A 2 2 • • • A t t a
Q -P ( dA1 dx Q A1 + 2 dA2 dx Q A2 + • • • + t dAt dx Q At ) Q 2 = dP dx -P ( dA1 dx /A 1 + 2 dA2 dx /A 2 + • • • + t dAt dx /A t ) Q , one has dG dx = P / Q where P = dP dx A 1 • • • A t -P ( dA 1 dx A 2 . . . A t + 2A 1 dA 2 dx A 3 • • • A t + • • • + tA 1 • • • A t-1 dA t dx ) and Q = A 2 1 A 3 2 • • • A t+1 t .
The proof is finished by showing that gcd( P , Q) ∈ A . Since A 1 , . . . , A t come from a squarefree factorization, gcd(A i , A j ) ∈ A when i = j. Thus, it is sufficient to show that gcd( P , A i ) ∈ A for any i. For any i, one has gcd( P

, A i ) = gcd(A 1 • • • A i-1 dAi dx A i+1 • • • A t , A i ) = gcd( dAi dx , A i ). By a classical argument gcd( dAi dx , A i ) ∈ A because A i is squarefree. Consequently, gcd( P , Q) ∈ A . Proposition 10. S F ∩ δS = {0}.
Proof. We consider an irreducible fraction F = δG in S F ∩ δS with F = 0, and prove that it yields a contradiction. Suppose that G ∈ K (x). Then F = δG = ∂G ∂x . Since F is in S F , and using Proposition 8, F can be written as a linear combination over K of FMF of type C1. As a consequence, the denominator of F is squarefree. Since F is nonzero, F necessarily involves x in its denominator. By Proposition 9, the denominator of ∂G ∂x is not squarefree, which yields a contradiction. Thus F = 0. Now suppose that G / ∈ K (x) and denote v = ld(G). Necessarily, F is not in K (x) either, and its leader v = ld(F ) satisfies v = δv, for some derivative v. Then

F = δG = v ∂G ∂v + w∈E,w =v (δw) ∂G ∂w + ∂G ∂x , ( 9
)
where E is the set of derivatives in ΘU occurring in G. Since F is in S F , and using Proposition 8, F can be written as a linear combination F = t i=1 α i F i where the α i are in K , and the F i are FMF either in K (x), or with leaders less than or equal to v. The rest of the proof shows that v ∂G ∂ v can be written as a linear combination of FMF, which in turn yields a contradiction.

Let us group the F i by considering their degrees w.r.t. v. On the one hand, we have

F = i∈I1 α i F i deg(Fi,v)>1 + i∈I2 α i F i deg(Fi,v)=1 + i∈I3 α i F i .
deg(Fi,v)≤0 [START_REF] Bilge | A REDUCE program for the integration of differential polynomials[END_REF] On the other hand, F can be written as

F = v ∂G ∂v + H (11)
with deg(H, v) ≤ 0. By Lemma 3, one has val(F i , v) > 1 for i ∈ I 1 and val

(F i , v) = deg(F i , v) = 1 for i ∈ I 2 .
Since G is free of v (and consequently ∂G ∂ v is free of v) and deg(H, v) ≤ 0, the terms of degree 1 between Equations ( 10) and ( 11) can be identified. This yields

v ∂G ∂v = i∈I2 α i F i .
Each FMF F i , for i ∈ I 2 , can be written as vNi Qi where Ni Qi is free of v. Assume that some Ni Qi involves a derivative strictly greater than v, and denote ṽ the highest derivative occurring in the Ni Qi • The expression v ∂G ∂ v can be decomposed in two sums of FMF

v ∂G ∂v = i∈I4 α i vN i Q i ld(Ni/Qi)=ṽ + i∈I5 α i vN i Q i • Ni/Qi∈K (x) or ld(Ni/Qi)<ṽ

Consider vNi

Qi for some i ∈ I 4 . Either N i or Q i involves ṽ. If Q i involves ṽ, then vNi Qi is necessarily of type C3 and deg(N i , ṽ) < deg(Q i , ṽ). If Q i does not involve ṽ, then N i necessarily does and in that case val(vN i , ṽ) > 0 since vN i is a monomial. Moreover ∂G ∂ v is free of ṽ (since ld(G) = v < ṽ) and the sum i∈I5 α i vNi Qi is also free of ṽ. By Applying Lemma 4 with y = ṽ,

F 0 = -∂G ∂ v + i∈I5 α i vNi
Qi and splitting the sum i∈I4 α i vNi Qi into F + (resp. F -) the sum of the fractions with positive (resp. negative) degree in ṽ, one has F + = F -= 0, which implies that i∈I4 α i vNi Qi = 0. By an easy induction on ṽ, and because rankings are well-orderings, one can assume that v ∂G ∂ v can be written as combinations of vN i /Q i where the N i and Q i do not involve any derivative strictly greater than v:

v ∂G ∂v = i∈I6 α i vN i Q i • Ni/Qi∈K (x) or ld(Ni/Qi)≤v
As a consequence, a monomial vN i when i ∈ I 6 cannot be functional since v = δv, deg(vN i , v) = 1 and N i does not involve a derivative strictly greater than v. This shows that, for i ∈ I 6 , F i cannot be of type C2 or C3.1. Moreover, vN i /Q i when i ∈ I 6 cannot be of type C3.3 since vN i / ∈ K [x] and ld(vN

i ) = v = δv ≥ δ ld(Q i ).
Consequently, v ∂G ∂v is a linear combination of FMF of type C3.2. As a consequence, for each i ∈ I 6 , one has

v = δ ld(Q i ) which implies ld(Q i ) = v. Since ∂G ∂ v is not zero (since ld(G) = v), the sum i∈I6 α i Ni Qi (which is equal to ∂G ∂ v )
is not zero either. Moreover, since each Q i is squarefree, and deg(N i /Q i , v) < 0 for any i ∈ I 6 , the sum i∈I6 α i Ni Qi , seen as a univariate fraction in v, can be written as a nonzero fraction with a negative degree and with a squarefree denominator in v.

Assume the denominator of G does not involve v. Then ∂G ∂ v is a polynomial in v. Applying Lemma 4 with y = v, F -= i∈I6 α i Ni Qi , and writing -∂G ∂ v as F 0 + F + , where F 0 is the zero degree term in v, one has ∂G ∂ v = 0, hence a contradiction. Thus the denominator of G involves v. By Proposition 9, ∂G ∂ v has a non squarefree denominator, which yields a contradiction since the sum i∈I6 α i Ni Qi can be written as a fraction with a squarefree denominator as seen in the paragraph above.

In summary, both cases G ∈ K (x) and G / ∈ K (x) yield a contradiction. As a consequence, the assumption F = 0 yields a contradiction, which proves the proposition.

To help understanding the termination and correctness proofs of Algorithm Integrate (Propositions 11 and 13), let us see the output of Integrate on some examples.

Example 11. Take the ranking u < u x < u y < u xx < u xy < • • • and consider K = Q(y).

Consider F ∈ K (x). Integrate simply behaves as the Algorithm Hermite.

Consider a FMF F of type C2. Integrate returns (F, 0) either at line 9 or at line 14 (because i N ≤ = 0 and i N> = i N ).

Consider F = xux
x+1 which is not a FMF. Lines from 11 to 14 will be executed.

One has v N = u x , v = u, i N = i N ≤ = x and i N> = 0. Then R = xu x+1 . Finally, δR = ux(x 2 +x)+u (x+1) 2 and F -δR -i N> v N /Q = -u (x+1) 2 which is a FMF of type C2. Thus Integrate returns -u (x+1) 2 , xu x+1 . Consider F = x (ux+1) 2 or F = ux (ux+1) 2 .
Then F = A/T and Integrate returns (F, 0) at line 24.

Consider F = u 2 x (u+1) 2 or F = uyy u+1 . Then F = A/T = i A v d
A /T and Integrate returns (F, 0) at line 28.

Consider F = (1+uxx)uxy (u+1) 2 . Then F = A/T with A = (1 + u xx )u xy , T = (u + 1) 2 .
Lines starting from 30 are executed and Integrate returns at line 34. One has Finally consider F = uux (u+2) 2 . Then F = A/T with A = uu x , T = (u + 2) 2 . Lines starting from 30 are executed and Integrate returns at line 37. One has Assume now that Q is not in K [x]. Let us show that the algorithm performs one or two recursive calls, and that in both cases either the leader of the denominator strictly decreases, or it remains the same but the rank of the numerator strictly decreases. This last situation can only occur finitely many times: indeed, the lexicographic order on the Cartesian product of the sets of derivatives by the set of ranks is a well-ordering (because a ranking and the ordering on the ranks are well-orderings). Consequently, the algorithm eventually reaches the case where

v d A = u xy , v = u y , i A = (1 + u xx ), i A ≤ = 1, i A> = u xx . Then R = uy (u+1) 2 . Finally, δR = uxy(u+1)-2uxuy (
v d A = u x , v = u, i A = i A ≤ = u, i A> = 0. Then (W, R) = ( 1 u+2 , 2 u+2 ). Finally, δR = -2ux (u+2) 2 . Consequently (A -i A> v A )/T -δR -W v A = uux (u+2) 2 --2ux (u+2) 2 -ux (u+2) = 0 so Integrate(F ) = ux u+2 , 2 (u+2)
Q is in K [x].
Recursive call at line 22. Since i α Q is free of v Q , the leader of denominator strictly decreases.

Recursive call at line 28. The rank of the numerator obviously strictly decreases in the recursive call. where P denotes v 0 i A ≤ dv. From ld(T ) = v Q and v A > δv Q , and because P involves derivatives smaller than v, the first term S 1 has a leader strictly less than v A . The second term S 2 has a leader equal to v A . One has δP = i A ≤ v A + U with U in K [x] or ld(U ) < v A . Consequently

A -i A> v A T -δR = A -i A v A -U T -δ 1 T P. (12)
From δ 1 T = -δT T 2 , and since δv Q < v A , Equation ( 12) can be written as Ā/T 2 where Ā is free of v A . Consequently, the rank of the numerator has dropped. Please note that in that recursive call, the degree of the denominator in the variable v Q might increase.

Recursive call at line 37. One has v A = δv Q due to the conditions at lines 23 and 32. Since v A = δv, one has v = v Q . Moreover W + ∂R ∂ v = i A ≤ /T . Both R and W involve derivatives less than or equal to v (since i A ≤ /T also involves derivatives less than or equal to v and ld(T ) = v Q = v). Thus, δR = v A ∂R ∂ v + R where R involves derivatives strictly less than v A . It follows that δR

+ W v A = v A ∂R ∂ v + R +W v A = i A ≤ v A /T + R. Consequently (A-i A> v A )/T )-δR -W v A = (A -i A v A )/T -R.
Thus, the rank of the denominator drops since R involves derivatives strictly less than v A .

Example 2 .

 2 Take F = k 2 k e V e y + k e + k e V e ẏ (y + k e ) 2 seen as a univariate fraction in y. Then Hermite(F, y) = (W, R) where W = k 2 k e V e y + k e and R = -k e V e ẏ y + k e

Proposition 2 . 3 return 5 v 7 // addition is performed componentwise 8 return 9 else 10 let v such that δv = v ; 11

 2357891011 Algorithm polyIntegrate terminates. Proof. The algorithm terminates trivially if P ∈ K [x]. Suppose now that P / ∈ K [x]. Any strictly decreasing sequence of ranks is finite [2, Chapter 0, §17, Lemma 15]. Thus, the algorithm terminates since each recursive call is made on Input: P a differential polynomial in R Output: The unique pair of differential polynomials (W, R) in RF × R such P = W + δR and R (viewed as a polynomial over K ) has no degree zero term. 1 begin 2 if P ∈ K [x] then d := rank P ; 6 if (d > 1) or (v / ∈ δΘU ) then (iP v d , 0) + polyIntegrate(P -iP v d ) ;

Proposition 4 .Proposition 5 .

 45 We have R = R F ⊕ δR.Proof. Proposition 1 shows that R F ∩ δR = {0}. Proposition 3 gives a constructive proof that R = R F + δR. Consequently, R = R F ⊕ δR. Algorithm polyIntegrate is correct.Proof. Proposition 3 shows that P = W + δR. The terms W and δR are unique by Proposition 4. Moreover R is unique since it has no degree zero term.Example 5. Take the ranking u

Proposition 6 .

 6 A FMF satisfies exactly one case among C1, C2 and C3. Moreover, a FMF satisfying C3 satisfies exactly one of the subcases among C3.1, C3.2 and C3.3.Proof. Cases C1 and C3 are independent because of the conditionsQ ∈ K [x] (C1) and Q / ∈ K [x] (C3).The same applies for C2 and C3. Since a functional monomial cannot lie in K [x], cases C1 and C2 are independent. Now consider the subcases for C3. Cases C3.1 and C3.2 are independent because M is functional in C3.1 and is not in C3.2. The same applies for C3.1 and C3.3. Finally cases C3.2 and C3.3 are independent because of the conditions δv = ld(M ) (C3.2) and ld(M ) < δv (C3.3).

Proof.

  First assume that Q is free of u. Then one necessarily has u = ld(M ), deg(F, u) = deg(M, u) = d and F has the form u d M /Q where M /Q is free of u. This shows the case d ≥ 1. Now assume that Q involves u, which implies that ld(Q) = u. By the degree condition of C3, one has deg(M, u) < deg(Q, u) so d = deg(F, u) < 0.

s

  i=t+1 α i F i and y = v, one has F 0 = F = 0 which concludes the proof.

Example 9 .

 9 Take the ranking u < u x < u y < u xx < u xy < • • • and consider K = Q(a, b, y) where a and b are constant w.r.t. δ. Take F = A xab(ux 2 +b) where

Remark 7 .Example 10 .

 710 and the constant term is b 2 + 1 a • Following Corollary 1, the polynomial part, nondifferential polynomial part and constant term operations are K -linear. Consider the ranking y < ẏ < ÿ < • • • (where the dot denotes the derivation) and the input-output equation in[START_REF] Boulier | On the integration of differential fractions[END_REF] Example 5]

4 / 5 G 6 G 7 returnAlgorithm 3 :Lemma 5 .

 456735 / quo(P, Q, x) is the remainder of the Euclidean division of P by Q with respect to variable x := quo(numer(G), denom(G), ld(denom(G))) ; := quo(numer(G), denom(G), x) ; the zero degree term of G viewed as a polynomial in ΘU , with coefficients in K (x); NondifferentialPolynomialPart(F ) Let F = v n A B

  then the nondifferential polynomial part and the constant term of F are zero.

Lemma 6 .Lemma 7 .

 67 If F is a FMF then its nondifferential polynomial part is zero. Proof. It is clear for fractions of type C1 because deg(M, x) < deg(Q, x). If F has type C2, then M depends on at least one derivative of ΘU (see condition (7) of Definition 5) and the proof follows from Corollary 2. Suppose F has type C3. Apply Algorithm 3. The fraction G is zero after only one loop because of the condition deg(M, v) < deg(Q, v). Consider a differential fraction R ∈ S \ K (x) and denote v = ld(R). If R seen as a univariate fraction in v has a zero constant term w.r.t v (in the sense of Definition 2), then R has a zero nondifferential polynomial part. As a consequence, if R has been computed by a call to Algorithm 1, then R has a zero nondifferential polynomial part, hence a zero constant term. Proof. Since R seen as a univariate fraction in v has a zero constant term w.r.t v (in the sense of Definition 2), R can be written in the form d i=1 Ai Bi v i + F , where F is either zero, or a fraction with leader v such that deg(F, v) < 0. By Corollary 2, d i=1

u+1) 3 andF

 3 -δR -i A> v A /T =

• Proposition 11 . 2 writeF 10 else 11 let v such that vN = δv ; 12 write 13 RQIS 1 =Algorithm 4 :

 1121011121314 Integrate terminates.Proof. The algorithm terminates when both N and Q are in K [x] since there is no recursion (line 5). First assume that N / ∈ K [x] and Q ∈ K [x]. Then both recursive calls at lines 9 and 14 are made on a fraction with a denominator in K [x] as well. Moreover, the rank of the numerator is strictly decreasing. Thus Input: F a differential fraction Output: The unique couple of differential fractions (W, R) such that (W, δR) is the decomposition of F on SF ⊕ δS and R has a zero constant term. 1 begin as an irreducible fraction N/Q ;3 if N ∈ K [x] and Q ∈ K [x] then 4 (W, R) := Hermite(F, x) ; 5 return (W, R) ; 6 elif Q ∈ K [x] then 7 v d N := rank(N ) ; 8 if d > 1 or vN / ∈ δΘU then 9 return (iN v d N /Q, 0) + Integrate(F -iN v d N /Q) ; iN as iN ≤ + iN >where iN > is the polynomial involving all monomials of iN whose leaders are strictly greater than v ; := 1/Q v 0 iN ≤ dv ;14 return (iN > vN /Q, R) + Integrate(F -δR -iN > vN /Q) ; 15 else 16 // Q is not in K [x] 17 vQ := ld(Q) ; 18 let S1 (resp. S2) be the quotient (resp. remainder) of a pseudo-division of N by Q w.r.t. vQ ; 19 // thus i α Q N = S1 Q + S2, for some nonnegative integer α ; consequently F = N Q = S 1 Q and deg(S2, vQ) > 0 since N/Q is irreducible 20 compute an irreducible fraction A/T such that A/T = S2/(i α Q Q) ;21 // thus F = S 1 i α Q + A T and ld(T ) = vQ since 0 < deg(S2, vQ) < deg(Q, vQ) 22 Integrate(S1/i α Q ) ; 23 if A ∈ K [x] or ld(A) < δvQ then 24 return IS 1 + (A/T, 0) ; 25 else 26 v d A := rank A ; 27 if (d > 1 or vA / ∈ δΘU ) then 28 return IS 1 + (iAv d A /T, 0) + Integrate((A -iAv d A )/T ) ; 29 else 30 take v s.t. vA = δv ; 31 write iA as iA ≤ + iA > where iA > is the polynomial involving all monomials of iA whose leaders are strictly greater than v ; 32 if vA > δvQ then 33 R := 1/T v 0 iA ≤ dv ; 34 return IS 1 + (iA > vA/T, R) + Integrate((A -iA > vA)/T -δR); 35 else 36 (W, R) := Hermite(iA ≤ /T, v) ; 37 return IS 1 + (W vA + iA > vA/T, R) + Integrate((A -iA > vA)/T -δR -W vA) ; Integrate(F ) the algorithm terminates when the denominator is in K [x]. Indeed, the rank of N trivially decreases at line 9. The term δR only involves derivatives less than or equal to δv = v N , and the subtraction at line 14 of δR + i N> v N /Q cancels the rank i N v N of N (since d = 1), thereby reducing the rank of N .

  Recursive call at line 34. One has

  2 is a FMF of type C1. The fractions

	u 2 x (1+x) 2 and (1+ux) 2 is a FMF of type C3.1. The fraction uxvx (x 2 -2)(1+x) are FMF of type C2. The fraction uxvx uxx 1+u 2 x is a FMF of type C3.2. The fraction vy x 1+u 2 is a FMF of type C3.3.

  squarefree factorization of Q (see Definition 4 in Section 2.3).

	Then dG dx can be written as	P 2 •••A t+1 1 A 3 A 2 t	where gcd( P , A 2 1 A 3 2 • • • A t+1 t	) ∈ A . As a
	consequence dG dx cannot be written as a fraction with a squarefree denominator.
	Proof. From
	dG dx	=	dP dx

We presented in this paper a new normal form for differential fractions. The integration w.r.t. general differential operators (linear combinations of partial derivations for example) instead of simply δ could be investigated. We also hope that the normal form presented will be an ingredient for constructing an elimination method for integro-differential polynomials or fractions.

Proposition 12. Integrate(F ) computes a couple (W, R) in S F × S such that F = W + δR. If F ∈ K (x), then W and R are also in K (x). Otherwise, if F / ∈ K (x), W is either in K (x) or satisfies ld(W ) ≤ ld(F ), and R is either in K (x) or satisfies δ ld(R) ≤ ld(F ).

Proof. The conditions on the leaders of W and R, and the fact that F = W +δR are immediate to prove. The main issue consists in proving that W is indeed a functional fraction.

The term W computed at line 4 is a linear combination of FMF of type C1 because of the specification of Algorithm 1. The contribution i N v d N /Q at line 9 is a linear combination of FMF of type C2 since d > 1 or v N / ∈ δΘU . The contribution i N> v N /Q at line 14 is also a linear combination of FMF of type C2, since all monomials of i N> involve derivative ṽ such that δṽ > v N . The contribution A/T at line 24 is a linear combination of FMF of type C3.1 or C3.3. The contribution i A v d A /T at line 28 is a linear combination of FMF of type C3.1. The contribution i A> v A /T at line 34 is a linear combination of FMF of type C3.1. Finally, if the term W computed at line 36 is not zero, it is necessarily a fraction with a squarefree denominator whose leader is v Q . Moreover, the leader of W cannot be greater than v Q since ld(i

All contributions to W were discussed. This shows that W is a functional fraction, which ends the proof.

Proposition 13. Integrate is correct.

Proof. Together, Propositions 10 and 12 show that S = S F ⊕ δS . It only remains to prove that the couple (W, R) returned by Integrate is uniquely defined and that the fraction R computed by Integrate has a zero constant term.

We first prove that the fraction R computed by Integrate has a zero constant term. It is true for line 5 thanks to the specification of Algorithm 1. The contribution for R is zero at lines 9, 24 and 28. The contributions for R at lines 14 and 34 have a zero constant term thanks to Corollary 2. The contribution for R at line 37 has a zero constant term by Lemma 7. Let us now prove that (W, R) is uniquely defined. From S = S F ⊕ δS , it is clear that W and δR are uniquely defined. Assume a fraction F is written as

If both R and R have zero constant terms, then R -R is necessarily zero, so R = R and R is uniquely defined.

Remark 8 (Finding "exact" derivatives). Suppose one has a (possibly infinite) family of fractions F i and that one looks for a fraction F = α i F i (i.e. a linear combination over K ) such that F = δG for some fraction G. One can proceed in the following manner: compute (W i , R i ) = Integrate(F i ) and look for a linear combination

5 Iterated Integration [START_REF] Boulier | On the integration of differential fractions[END_REF]Algorithm 4] presents an algorithm which roughly speaking iterates the integration until one gets a coefficient as defined in [START_REF] Boulier | On the integration of differential fractions[END_REF] (i.e. a fraction free of ΘU ). [START_REF] Boulier | On the integration of differential fractions[END_REF]Algorithm 4] takes as an input a fraction F 0 and returns a decomposition

where all W i are also fractions (satisfying some further properties). [START_REF] Boulier | On the integration of differential fractions[END_REF]Algorithm 4] is not additive as shown by the simple following example ; it decomposes x into x, u x into 0 + δu, but u x + x into 0 + δ(u + x 2 /2). On this example, the problem comes from the polynomial x which can be integrated infinitely many times.

We prevent this problem by isolating the nondifferential polynomial part in x at each step.

Proposition 14 (Iterated integration decomposition). Let F be a differential fraction. Then F can be written in a unique way as

Please note that in the special case where F is in K [x], then the iterated integration decomposition of F is F itself (i.e. all the W i are zero).

Proof. Let us first admit the existence of such a decomposition which is proven in Proposition 16 based on Algorithm 5. Let us now prove the uniqueness by considering two decompositions of the same fraction

Wi . Since both decompositions involve a finite number of terms, and by subtracting the two decompositions, 0 = P + W 0 + δW 1 + • • • + δ t W t for some t ≥ 0, where P = P -P is in K [x] and the W i = Ŵi -Wi are in S F . Let us now prove that all W i are zero. Since P is in K [x], it also belongs to δS , and P = δP 1 for some polynomial

Since S F ∩ δS = {0}, one has W 0 = 0. Since we assumed in the paper that δa = 0 for all a ∈ K , there exists a constant c 1 in K , such that c

By an induction process, all W i are zero, and consequently P = 0. Thus, both decompositions of F are equal.

It remains to prove that Suppose that the algorithm does not terminate. If G is not initially in K (x), then the leader of G decreases at each loop using Proposition 12. Since the leader of G cannot decrease infinitely many times, G eventually lies in K (x). At this point, each call to Integrate is a call to Hermite. Each call to Hermite reduces the degree of the denominator (see [13, last formulae of page 39]). For this reason, G must eventually become a polynomial. When G becomes a polynomial of K [x], it must be equal to its polynomial part, and thus must be zero, thanks to the loop invariant. This leads to a contradiction, so the algorithm terminates.

Proposition 16. For any fraction F , Algorithm IteratedIntegrate computes a pair (P, [W 0 , . . . , W t ]) such that

, the W i are functional fractions, and W t = 0 when the list [W 0 , . . . , W t ] is not empty. Proof. All the W i are in S F since they are computed by Integrate. The polynomial P is an element of K [x] by construction. Finally, let us prove the following loop invariant:

The invariant is true when entering the loop since F = P + G and i = 0. Suppose the invariant is true at some step.

After line 7, one has G = W i + δR and P = nondiffPolyPart(R). Thus

Consequently the invariant is true after line 10 (i.e. after updating the values of P , G and i). By Proposition 15, IteratedIntegrate terminates and the invariant plus the property G = 0 imply F = P + t j=0 δ j W j .

Proposition 17. Algorithm IteratedIntegrate is correct.

Proof. This is a direct consequence of Propositions 14 and 16.

Example 12. The iterated integration of F io (see Example 10)

, and W 2 = y. This decomposition is almost the same as in [START_REF] Boulier | On the integration of differential fractions[END_REF] except the constant term k 2 V e has been isolated. At first sight, one could believe that W

is not a functional fraction because the degree in y of the numerator is 2, and the one of the denominator is 1. However, it is a functional fraction since W 1 = (k 1 + k 2 )y -keVe y+ke (where y and 1 y+ke are FMF).

Remark 9. At first, the authors had tried to collect from the beginning the nondifferential part of F , hoping that all following calls to Integrate would return a pair (W, R) where R would have a zero nondifferential polynomial part. However, this does not work because taking the nondifferential polynomial part and applying δ do not commute. For example, take F = u+uxx ux , and G = δF . The nondifferential polynomial part of F is zero. However the nondifferential polynomial part of G = δF is 1 and not 0, since δF = 1 + uxxx ux -uxx(uxx-u) u 2

x

• This shows the calls to NondifferentialPolynomialPart at line 7 are needed.

Remark 10. The iterated integration decomposition can lead to some variants. For example, a nonnegative integer t can be fixed and the infinite sum in Proposition 14 can be replaced by t i=0 δ i W i . In that case, the condition 3 can obviously be discarded, and the condition 2 needs to be replaced by "W t , δW t , . . . , δ t-1 W t have a zero constant term and W i is a functional fraction for any 0 ≤ i ≤ t -1". By fixing t = 1, Algorithm Integrate is obtained.

Remark 11. Remark 8 can be generalized to find a linear combination F = α i F i such that F = δ 2 G for some fraction G. By using t = 2 in Remark 10, and by using IteratedIntegrate, it suffices to cancel both the W 0 and W 1 parts of the F i .