Some applications of differential-difference algebra to creative telescoping

Some applications of differential-difference algebra to creative telescoping

 Differential and difference rings 

Let R be a commutative ring. A map δ : R → R is said to be a derivation on R if δ(a + b) = δ(a) + δ(b), δ(ab) = δ(a)b + aδ(b) for all a, b ∈ R. The pair (R, δ) is called a differential ring. Moreover, if R is a field, R is called a differential field. An element c ∈ R is called a constant with respect to δ if δ(c) = 0. All constants with respect to δ form a subring of R, denoted by Cδ,R. If R is a field, Cδ,R is also a field. Some basic facts concerning derivations are collected in the next lemma whose proof can be found in any book about differential algebra, e.g. [21] Lemma 2.1.1. Let (R, δ) be a differential ring For a, b ∈ R and n ∈ N, we have (i) δ(1) = 0; (ii) δ(a n ) = nan−1 δ(a); (iii) If b is invertible, then δ a b  = δ(a)b − aδ(b) b 2 . 15 (iv) Logarithmic derivative identity: if a and b are invertible, then δ(a mb n ) amb n = m δ(a) a + n δ(b) b for all m, n ∈ Z. Let σ : R → R be a monomorphism on R. Then the pair (R, σ) is called a difference ring. Moreover, if R is a field, R is called a difference field. An element c ∈ R is called a constant with respect to σ if σ(c) = c. All constants with respect to σ form a subring of R, denoted by Cσ,R. If R is a field, Cσ,R is also a field. The triple (R, δ, σ) is called a differential-difference ring. (R, δ, σ) is said to be orthogonal [62] if the derivation δ commutes with the monomorphism σ. Unless otherwise specified, all fields in the thesis are of characteristic zero and all differentialdifference rings are orthogonal. 

Ore polynomials 

Ore polynomials are a common abstraction for linear differential operators, linear difference operators, shifts, and q-shifts [70, 23]. Let (F, δ, σ) be a differential-difference field. The ring of Ore polynomials F[x; δ, σ] over F is the univariate polynomial ring with indeterminate x, addition defined as usual, and multiplication being associative, distributive, and satisfying the commutation rule: xf = σ(f)x + δ(f), for any f ∈ F. (2.1) By the commutation rule (2.1), the product of two polynomials in F[x; δ, σ] can be decided by association and distribution. Example 2.2.1. Let F(t) be the univariate rational-function field in t over F. (i) The usual polynomial ring F(t)[x] on which δ is the zero map and σ is the identity map. (ii) The ring of differential operators F(t)[x; d/dt, 1], where 1 is the identical map. (iii) The ring of recurrence operators F(t)[x; 0, σ], where σ(f(t)) = f(t + 1) for any f ∈ F(t). (iv) The ring of difference operators F(t)[x; ∆, σ], where ∆ = σ − 1. In this thesis, we also denote the ring of differential operators over F(t) by F(t)hDti and the ring of difference operators over F(t) by F(t)hSti. 16 If σ is an automorphism, we can perform both left and right Euclidean division on the ring F[x; δ, σ] [70], that is, for any f, g ∈ F[x; δ, σ], there exist q, r ∈ F[x; δ, σ] such that f = qg+r or f = gq + r, where deg(r) < deg(g). This implies that F[x; δ, σ] is a left and right principal ideal domain. A multivariate extension of Ore polynomials is studied in [35, 32, 93].

 Integration of rational functions 

Symbolic evaluation of integrals is an active research domain of computer algebra, which revives the study of the integration problems from the algorithmic point of view. The first landmark algorithm, designed by Risch [77, 78] in the late 1960’s, can decide whether indefinite integrals of elementary functions are elementary or not. State of the art about integrating transcendental functions has been presented in Bronstein’s book [21]. For later use, we review some basic methods for rational-function integration. For more intensive presentations, see the books [21, Chapter 2], [45, Chapter 11], and [90, Chapter 22]. In this section, let F be a field of characteristic zero and F(x) be the rational-function field in x over F. On the field F(x), the derivation δ is defined by setting δ(x) = 1 and δ(c) = 0 for all c ∈ F. In most undergraduate calculus textbooks, we can find that any rational function f ∈ C(x) over the field C of complex numbers has an elementary integral of the form Z f dx = g + Xn i=1 βi log(x − αi) (2.2) where g ∈ C(x) and αi , βi ∈ C for i = 1, . . . , n. Here, we call g the rational part of the integral and the sum of logarithms the logarithmic part of the integral. In this analytic setting when the ground field is the algebraically closed field C, the problem of rational function integration is well-understood. However, the algorithmic question becomes more involved when the ground field is not algebraically closed. Over an arbitrary field F, one may need to compute objects over an algebraic extension of F. In this case, the method in calculus books has many practical difficulties. For any rational function f ∈ F(x), it has been shown by Hermite [52] that the rational part of the integral R f dx still lies in F(x) and he presented a method to compute this part without introducing any algebraic extension of F. His method is named Hermite reduction in [21, 45, 90]. For the logarithmic part, in general it is required to introduce algebraic extensions of F and then the question is how to compute the minimal algebraic extension of F that is 17 sufficient to express the integral. This question has been independently solved by Trager [87] and Rothstein [80].

Hermite reduction

Hermite reduction is a practical method for computing the rational part, which uses the method of integration by parts in order to reduce the denominator of the integrand to a square-free polynomial. More explicitly, Hermite reduction decomposes f ∈ F(x) into f = δ(g) + a b , (2.3) where g ∈ F(x) and a, b ∈ F[x] with deg(a) < deg(b) and b squarefree. Such a pair (g, a/b) in (2.3) is called an additive decomposition for f (with respect to x). The rational functions g and a/b are called the rational and logarithmic parts of f, respectively. We summarize the idea of Hermite reduction following the treatment in [21, Chapter 2.2]. Write the integrand as f = A/D with A, D ∈ F[x] and gcd(A, D) = 1. Let D = D1D2 2 . . . Dn n be the squarefree factorization of D. By computing the partial fraction decomposition for f, we have f = P + Xn i=1 Ai Di i (2.4) where P and the Ai ’s are in F[x] and deg(Ai) < deg(Di i ) for each i. By the linearity of δ, it is sufficient to consider the same decomposition problem for any fraction of the form P Qm ∈ F[x], with m > 1, deg(P) < m deg(Q) and Q squarefree. The square-freeness of Q implies the existence of a Bézout relation Sδ(Q) + T Q = 1, (2.5) where S, T ∈ F[x] can be obtained by the extended Euclidean algorithm. Furthermore, upon multiplication and division with remainder, we get P = SP δ(Q) + T P Q = (GQ + B)δ(Q) + T P Q = Bδ(Q) + CQ (2.6) where C = Gδ(Q) + T P with deg(C) < (m − 1) deg(Q). Now, integration by parts yields P Qm = Bδ(Q) + CQ Qm = δ  −(m − 1)−1B Qm−1  + C + (m − 1)−1 δ(B) Qm−1 (2.7) 18 where deg(C + (m − 1)−1 δ(B)) < (m − 1) deg(Q) since deg(B) < deg(Q) and deg(C) < (m − 1) deg(Q). This process is repeated until the denominator is square-free. In 1975, Mack [69] introduced a variant of Hermite reduction that requires neither partial fraction decomposition nor squarefree factorization, but only extended GCD computation. The following lemma due to Ostrogradsky [71] shows the uniqueness (up to an additive constant) of additive decompositions. For proofs, one can follow the argument in [45, Theorem 11.4]. Lemma 2.3.1. Let f = a/b be a nonzero rational function in F(x) such that a, b ∈ F[x], gcd(a, b) = 1, deg(a) < deg(b), and b is squarefree. Then there is no g ∈ F(x) such that f = δ(g). Corollary 2.3.2. Let f be a rational function in F(x). Then the pair (g, a/b) satisfying (2.3) for f is unique up to adding a constant to g. Proof. Assume that (g1, a1/b1) and (g2, a2/b2) are two additive decompositions for f with a1/b1 6= a2/b2. The difference of logarithmic parts can be written as 0 6= a1/b1 − a2/b2 = A B , where A, B ∈ F[x], gcd(A, B) = 1, and deg(A) < deg(B). Since both b1 and b2 are squarefree and B divides lcm(b1, b2), B is also squarefree. However, A B = δ(g2 − g1), which contradicts Lemma 2.3.1. So a1/b1 equals a2/b2 and then g1 and g2 differ by an additive constant. For later use, we recall a fact on the logarithmic derivatives of rational functions. Lemma 2.3.3. Let f = a/b ∈ F(x) be such that a, b ∈ F[x] and gcd(a, b) = 1, then δf f = p a ∗b ∗ , where a ∗ and b ∗ are, respectively, the squarefree parts of a and b, and p ∈ F[x] with deg(p) < deg(a ∗ b ∗ ) and gcd(p, a∗ b ∗ ) = 1. 19 Proof. Let a = a1a 2 2 · · · a m m and b = b1b 2 2 · · · b n n be the squarefree factorizations of a and b, respectively. Then a ∗ = a1a2 · · · am and b ∗ = b1b2 · · · bn. By Lemma 2.1.1 (iv), we have δf f = p a ∗b ∗ , where p = b ∗Xm i=1 iδ(ai)a ∗ ai − a ∗Xn j=1 jδ(bj )b ∗ bi ∈ F[x]. It is easy to see that deg(p) < deg(a ∗ b ∗ ). Since the ai ’s and bj ’s are squarefree and pairwise coprime, we have gcd a ∗ , Xm i=1 iδ(ai)a ∗ ai ! = gcd  b ∗ , Xn j=1 jδ(bj )b ∗ bi   = 1, which further implies gcd(p, a∗ b ∗ ) = 1. This completes the proof. The following lemma will be useful to verify uniqueness properties, in particular, in the proofs of Theorem 4.4.4 and Lemma 4.3.10. Lemma 2.3.4. Assume that f is a rational function in F(x), p1, . . . , pn are pairwise coprime polynomials in F[x], and c1, . . . , cn are constants in F. If δ(f) = Xn i=1 ci δ(pi) pi , then f ∈ F and either ci = 0 or pi ∈ F for all i such that 1 ≤ i ≤ n. Proof. Let p ∗ i be the squarefree part of pi for all i such that 1 ≤ i ≤ n. By Lemma 2.3.3, we have Xn i=1 ci δ(pi) pi = Xn i=1 ci qi p ∗ i =: a b , where a, b ∈ F[x] with gcd(a, b) = 1 and the qi ’s are polynomials in F[x] with gcd(qi , p∗ i ) = 1 and deg(qi) < deg(p ∗ i ). Since the pi ’s are pairwise coprime, so are the p ∗ i ’s. Hence, the denominator b is squarefree and deg(a) < deg(b). By Lemma 2.3.1, a/b must be equal to zero and then f ∈ F. By the uniqueness of squarefree partial fraction decomposition, all the fractions ciqi/p∗ i are equal to zero. This implies that either ci = 0 or pi ∈ F for each i such that 1 ≤ i ≤ n. Corollary 2.3.5. Let c1, . . . , cn ∈ F be linearly independent over Z. If there exist rational functions f1, . . . , fn ∈ F(x) such that Xn i=1 ci δ(fi) fi = 0, then f1, . . . , fn belong to F. 20 Proof. Since every element of F is a constant with respect to δ, we may suppose that none of f1, . . . , fn belongs to F, and look for a contradiction. Under this assumption, the sum can be rewritten as Xm j=1 c¯j δ(pj ) pj = 0 where c¯j is a Z-linear combination of c1, . . . , cn, and the pj ’s are nontrivial distinct irreducible factors of the denominators of the δ(fi)/fi . Since every c¯j is nonzero, Lemma 2.3.4 implies that every pj is in F, which is a contradiction.

Ostrogradsky and Horowitz’s method

Ostrogradsky and Horowitz’s method [71, 53] computes the additive decomposition of a rational function by solving a linear system. Although this method has asymptotically higher complexity than that of Hermite reduction [90, Section 22.2], it is useful for our complexity analyses in the sequel. Let f = P/Q ∈ F(x) be such that P, Q ∈ F[x] and gcd(P, Q) = 1. After reading out the polynomial part of f, we further assume that deg(P) < deg(Q). Let Q∗ be the squarefree part of Q and Q− = Q/Q∗ . Denote d ∗ x = degx (Q∗ ) and d − x = degx (Q−). According to the functionality of Hermite reduction, one can find two unique polynomials A and a in F[x] with degx A < deg(Q−) and degx a < deg(Q∗ ) such that P Q = δ  A Q−  + a Q∗ . (2.8) Note that A and a satisfy (2.8) if and only if they satisfy the equation P = δ(A)Q ∗ − AQe + aQ−, (2.9) where Qe = Q∗ δ(Q−)/Q− is a polynomial in F[x] of degree deg(Q∗ ) − 1. Now, equation (2.9) can be solved by the method of undetermined coefficients. Write P = Pd ∗ x+d − x −1 l=0 Plx l and set A = Pd − x −1 i=0 Aix i , a = Pd ∗ x−1 j=0 ajx j with undetermined coefficients Ai and aj . Then (2.9) holds if and only if  Ad − x −1 , . . . , A0, ad ∗ x−1, . . . , a0  M =  Pd ∗ x+d − x −1 , . . . , P0  , (2.10) where M is a deg(Q) × deg(Q) matrix over F obtained by equating the likewise powers of x 21 in (2.9). By the uniqueness of A/Q− and a/Q∗ , the system (2.10) has a unique solution, which leads to the following lemma. Lemma 2.3.6. The matrix M in (2.10) is invertible over F. We call the linear system (2.10) the Ostrogradsky–Horowitz system and M the Ostrogradsky– Horowitz matrix associated with Q. Note that M is uniquely determined by Q. So we denote this matrix by M(Q). 2.3.3 Residues and Rothstein–Trager resultants After additive decomposition, the integration problem of rational functions is reduced to computing the integrals of the form Z a b dx, where a, b ∈ F[x] with gcd(a, b) = 1, deg(a) < deg(b) and b squarefree. (2.11) Over the algebraic closure F of F, the rational function a/b above decomposes into a b = Xn i=1 βi x − αi , where αi , βi ∈ F and b(αi) = 0 for 1 ≤ i ≤ n. Consequently, the integral of a/b can be expressed by Z a b dx = Xn i=1 βi log(x − αi). By convention, the value βi is called the residue of a/b at the point x = αi . According to the Lagrange formula ([44, page 38] or [45, Exercise 11.8]), the residue of a/b at αi is βi = a δ(b) (αi) ∈ F(αi). (2.12) So we can always express the integrals in (2.11) over the splitting field of the denominator b. However, it is not necessary to compute splitting fields for obtaining the integrals. For instance, the integral below can be expressed without any algebraic extension: Z 2x x 2 − 2 dx = log(x + √ 2) + log(x − √ 2) = log(x 2 − 2). In fact, Rothstein [80] and Trager [87] have shown that the minimal algebraic extension of F for expressing the integrals is the splitting field of the following polynomial R(z) = resultantx(b, a − z · δ(b)) ∈ F[z].

Télécharger le document complet