Computational methods in algebra and analysis

Bol. Soc. Esp. Mat. Apl. no40(2007), 71–102 COMPUTATIONAL METHODS IN ALGEBRA AND ANALYSIS FRANCISCO J. CASTRO-JIM´ ENEZ Departamento de ´ Algebra, Universidad de Sevilla [email protected] Abstract This paper describes some applications of Computer Algebra to Algebraic Analysis also known as D-module theory, i.e. the algebraic study of the systems of linear partial differential equations. Gr¨obner bases for rings of linear differential operators are the main tools in the field. We start by giving a short review of the problem of solving systems of polynomial equations by symbolic methods. These problems motivate some of the later developed subjects. Key words: Polynomial ring, polynomial system, ring of linear differential operators, differential system, D-module, Gr¨obner basis, division theorem, characteristic variety, irregularity, Bernstein-Sato polynomial, logarithmic Dmodule, projective module, syzygy, free resolution. AMS subject classifications: 68W30 13D02 13Pxx 14Qxx 16S32 16Z05 32C38 33F10. Introduction The nature of this article is somehow mixed. It contains for example some elementary and very well known results on commutative polynomial rings but on the other hand it also contains non trivial results about systems of linear partial differential equations. Nevertheless, anyone with a basic knowledge of ring and module theory could, at least, have a grasp on the referred matter. The interested reader will find in the text precises references for the proofs of the announced results. Computer Algebra,Symbolic Computation (CA/SC in what follows) or Computational Algebra is a relatively new discipline. This new field of research is Fecha de recepci´on: 07/12/2005. Aceptado (en forma revisada): 17/09/2007. The title of this paper coincides with the one of one Special Session of the First Joint Meeting AMS-RSME (June 18-21, Seville, 2003). The Special Session was organized by E. Cattani and the author. This work has been supported by MTM2004-01165 and FQM-333. 71 72 F.J. Castro-Jim´enez called Calcul Formel in French and C´alculo Simb´olico or ´ Algebra Computacional in Spanish. The item ´ Algebra Computacional appears in the Spanish Plan Nacional de Investigaci´on Cient´ıfica, Desarrollo e Innovaci´on Tecnol´ogica 20042007, Programa Nacional de Matem´aticas1, as subsection 3.5. In the Mathematics Subject Classification 2000 (MSC2000) used by Mathematical Reviews and Zentralblatt MATH, CA/SC appears as 68W30 Symbolic computation and algebraic computation [See also 11Yxx, 12Y05, 13Pxx, 14Qxx, 16Z05, 17-08, 33F10], and it provides methods and tools for many Mathematical areas as for example Commutative Algebra Algebraic Geometry Number Theory Algebraic Analysis or D–modules Differential Geometry Associative Algebras Group Theory Algebraic Groups and Lie Algebras Algebraic and Differential Topology Combinatorics Graph Theory Computational Geometry Coding Theory and Cryptography Statistic and Probability Recent CA/SC developments deeply interact with Numerical Analysis. Moreover, the study and analysis of the algorithms arising in CA/SC are also useful in other disciplines especially in Robotics (see e.g. [82, 37]), Computer Vision (see e.g. [27]), Computer Aided Geometric Design (see e.g. [38]), Artificial Intelligence (see e.g. [3]), Chemistry, Physics and Engineering (see e.g. [23] and [1]), Biology (see e.g. [28]), and Statistics and Economics (see e.g. [63] and [77, Chaps. 6,8]). Finally the Journal of Symbolic Computation and Applicable Algebra in Engineering, Communication and Computing are international journals mainly directed to researchers who are interested in symbolic computation and a new section of the Journal of Algebra is titled and devoted to Computational Algebra. Journals as Mathematics of Computation, Journal of Complexity, Computational Complexity, SIAM Journal of Computing, ACM Communications in Computer Algebra publish regularly CA/SC papers. The algorithms described in this paper have been implemented in several Computer Algebra Systems most of them freely available. The following are widely used: Macaulay 2 [35], CoCoA [22], Singular-Plural [36], Risa-Asir [62], kan [62], Bergman [6], Gap [32]. Mathematicar MAGMArMuPADrand Maplerare some commercial Computer Algebra Systems of general purpose containing implementations of some of the algorithms treated in this article. The article is intended to provide a short introduction to the use of some Computer Algebra methods in the algebraic study of linear partial differential systems. Our main tool will be Gr¨obner bases for linear partial differential operators. Some of the algebraic methods developed in this article have been 1National Plan for Scientific Research and Technological Development 2004-2007, National Mathematics Program Computational methods 73 treated by different authors elsewhere. A list of such works should include Ch. Riquier [66] and M. Janet [45] both inspired by the works of E. Cartan. This article does not deal with the general theory of Differential Algebra (see e.g. [67], [48]). The article does not contain proofs but for any of them a reference is given. The structure of the article is as follows: Section 1 is devoted to the description of some problems on systems of polynomial equations and their solutions by using Gr¨obner bases for polynomial rings. In Section 2 we recall the notion of Gr¨obner basis for rings of differential operators and its application to the algebraic study of systems of linear differential equations. We focus on the calculation of the characteristic variety of a linear partial differential system and on the computation of a free resolution of the module associated with the considered system. In Section 3 we sketch some applications of Gr¨obner bases to the computational study of the irregularity of differential systems and to logarithmic D–modules. 1 Getting started 1.1 Polynomial rings and polynomial systems On peut dire que l’origine historique et un des buts essentiels de l’Alg`ebre, depuis les Babyloniens, les Hindous et Diophante jusqu’`a nos jours, est l’´etude des solutions des syst`emes d’´equations polynomiales.2 In this subsection we will describe some problems related to the study of systems of polynomial equations in several variables. Let us denote by R[x1, . . . , xn] the set of polynomials in the variables x1,...,xnand with coefficients in the field of real numbers R. We also write R[x] = R[x1,...,xn] if no confusion arises. The letters f, g, h, . . . or the expressions f(x), g(x), h(x),... (sometimes with subindexes) stand for polynomials. A polynomial in R[x] can be written as a finite sum X α=(α1,...,αn)∈Nn cαxα1 1···xαn n where the coefficients cαare real numbers. To simplify we write xα= xα1 1···xαn n. The degree of f, denoted by deg(f), is the maximum of the integer numbers |α|:= α1+···+αnfor cα6= 0. The set R[x] is a commutative ring with respect to the addition and the product of polynomials. Let us consider a finite system S ≡ {f1(x) = f2(x) = ···=fm(x) = 0}(1) 2Extracted from the Introduction of the book: Grothendieck, A. and Dieudonn´e, J.A. ´ El´ements de g´eom´etrie alg´ebrique I, Springer-Verlag, Berlin, (1971), ISBN:0387051139. 74 F.J. Castro-Jim´enez of polynomial equations. We denote VR(S) = {w= (w1,...,wn)∈Rnsuch that fi(w) = 0, i = 1,...,m} the set of real solutions of the system S. We also write VR(S) = VR(f1,...,fm). The subsets of Rnof type VR(S) for some system S, are called real affine algebraic sets or simply algebraic sets if no confusion is possible. For example, the graph in R2of any polynomial f(x1) in one variable x1is an algebraic set in R2as this graph is the set VR(x2−f(x1)) = {(a1, a2)∈R2|a2=f(a1)}. If f(x1, x2) = a00 +a10x1+a01x2+a11x1x2+a20x2 1+a02x2 2 is a degree 2 polynomial in two variables x1, x2then the set VR(f(x1, x2)) is nothing but a real affine conic which could be degenerate. If each equation in the system Sis linear –i.e. if each polynomial fi(x) has degree 1, then the solution set VR(S) is simply a linear affine variety in Rnand Linear Algebra is devoted to the study of such objects. The first objective of Algebraic Geometry is the study of the properties of algebraic sets V(S) when Sis a general system of polynomial equations. Let us remark that if w= (w1,...,wn) is a real solution of System (1) then wis also a solution of any equation f(x) = 0 deduced from the fi(x) = 0 by a linear combination with polynomial coefficients, i.e. f(w) = 0 for f(x) = Pm i=1 qi(x)fi(x) for any choice of qi(x) in R[x]. The set of such linear combinations is denoted by hf1(x),...,fm(x)iand it’s called an ideal of the ring R[x] (an ideal in a commutative ring Ris an additive subgroup of Rclosed by products with elements in R). Formally, we can also consider non necessarily finite systems of polynomial equations but the Hilbert’s Basissatz (see, e.g. [5, Th. 7.5.]) assures that each system is equivalent to a finite one. More precisely, let us consider a system {f(x) = 0}f(x)∈T of polynomial equations where Tis an arbitrary subset of R[x]. Its solution set is denoted by VR(T). By Hilbert’s Basissatz there is a finite subset {g1(x),...,gr(x)}in Tsuch that VR(T) = VR(g1,...,gr).(2) Moreover, if we denote by hTithe ideal generated by T, i.e. the set of all linear combinations of elements in Twith polynomial coefficients, the Hilbert’s Basissatz states precisely that there is a finite subset {g1(x),...,gr(x)}in T such that hg1(x),...,gr(x)i=hTi(3) and the equality (3) implies the equality (2). A commutative ring in which any ideal is finitely generated is called a Noetherian ring. In what we have done before the field Rcan be replaced by any other field K. Then we can consider the polynomial ring K[x] = K[x1,...,xn] on the variables Computational methods 75 xiand with coefficients in K. In many practical applications Kwill be one of the fields Q,Ror Cwhile finite fields are widely used for example in Coding Theory and Cryptography. So, let us consider a general system of polynomial equations S ≡ {f1(x) = f2(x) = ···=fm(x) = 0}(4) with coefficients if the field Kand let us denote its solution set in the affine space Knby VK(S) = V(f1, . . . , fm) = {w= (w1,...,wn)∈Kn|f1(w) = ···= fm(w) = 0}. A subset Yof the affine space Knis said to be an affine algebraic set or simply an algebraic set if there exists T⊂K[x] such that Y=VK(T). The empty set and Knare algebraic sets. The union of two algebraic sets is an algebraic set. The intersection of an arbitrary family of algebraic sets is also an algebraic set (see e.g. [41]). These last properties of algebraic sets show that they are the closed sets of a topology on Knwhich is called the Zariski topology. Taking the system Sas input we are concerned with the following problems or questions that can be considered as effective problems in polynomial rings. (P1) Describe an algorithm to decide whether the set VK(S) is empty. (P2) If VK(S) is not empty, describe an algorithm to decide whether VK(S) is finite and to compute its cardinal. (P3) If VK(S) is finite, describe an algorithm to compute the elements of VK(S) i.e. to solve the system S. (P4) If VK(S) is not finite, can we describe its elements using parameters? There are no known algorithms for solving Problems P1-P4 with the above generality. For example, if f(x, y)∈Q[x, y] is a cubic (i.e. if deg(f) = 3) then there is no currently known algorithm to decide if VQ(f) is empty; see e.g. [74]. Nevertheless a weaker form of these problems will be solved in Subsection 1.2 by using Gr¨obner bases techniques. In these weaker forms, which will be denoted (P1’), (P2’), (P3’) and (P4’), we will assume that even if the coefficients of Sbelong to the given field K, the solutions of the system VL(S) are to be searched over an algebraically closed3field Lcontaining K(for example Lcould be the algebraic closure Kof K). One of the fundamental problems on effectiveness in polynomial rings is the so called membership problem as defined for example by G. Hermann [42] in 1926. It can be stated as follows: (P0) Given a finite set of polynomials f1(x),...,fm(x) in K[x] describe an algorithm deciding if a given polynomial f(x) belongs to the ideal hf1(x),...,fm(x)i. 3A field Kis algebraically closed if the roots of every polynomial in one variable f(t)∈K[t] are in K. 76 F.J. Castro-Jim´enez To solve this problem G. Hermann gave an upper bound for the degree of the polynomials qi(x) appearing in an expression f(x) = Piqi(x)fi(x) if they exist, and then she used Linear Algebra to algorithmically solve problem P0. The upper bound found by G. Hermann is of type deg(f) + (md)2nwhere dis the maximum of the degrees of the fi. Moreover, as shown in [57], this upper bound is sharp. Hermann’s upper bound is in fact related to the degree of a Gr¨obner basis of the ideal generated by the fi, as we will see in the next section. 1.2 Gr¨obner bases for polynomial rings If f(x1) is a nonzero polynomial in K[x1] then the set VK(f) is nothing but the set of roots of f(x1) = 0 in Kand its cardinal is bounded by the degree deg(f). Moreover, deg(f) equals the dimension of the quotient K–vector space K[x1] hf(x1)i. For a general system Sas (4) we have Proposition 1 (see e.g. [26, Chap. 2, Th. 2.10] or [54, Chap. 2 Prop. 1.4]) Let Sbe the system f1(x) = f2(x) = ···=fm(x) = 0 and let us denote by hSi the ideal in K[x]generated by the fi. If dimK K[x] hSi is finite then #VK(S)≤dimK K[x] hSi . Here #Zdenotes the cardinal of a set Zand K[x] hSi is considered as the quotient vector space of K[x] by the ideal hSi and dimK( ) denotes the vector space dimension. The quotient K[x] hSi also has a natural structure of commutative ring with unit with respect to the addition and the multiplication of classes modulo hSi. The reciprocal of Proposition 1 is false in general. Consider f(x1, x2) = x2 1+x2 2. We have VR(f) = {(0,0)} ⊂ R2but dimR(R[x1,x2] hfi) = +∞. Moreover, in Theorem 3 we will see a more precise result. The computation of the dimension of the vector space K[x]/hSi, even when it is finite, is more complicated than in the one variable case. It is not enough to consider only the degrees deg(fi). To deal with we will start by introducing the notion of monomial order. A total ordering ≺on Nnis a monomial order if 0 = (0,...,0) ≺αfor all α∈Nnand ≺is compatible with the sum (i.e. α≺β implies α+γ≺β+γfor all γ∈Nn). The lexicographical order (denoted by <lex) on Nnis defined as follows: (α1,...,αn)<lex (β1,...,βn) if and only if the first nonzero component of (α1−β1,...,αn−βn) is negative. The total order <lex is a monomial order. The only monomial order in Nis the natural order. We can translate any order ≺in Nnto the set of monomial {xα|α∈Nn} just by writing xα≺xβif and only if α≺β. Once a monomial order has been fixed on Nn, we can associate to each nonzero polynomial f=f(x) = Pαcαxα∈K[x] its privileged exponent exp≺(f) with respect to ≺, defined as the maximum with respect to ≺of the set {α∈Nn|cα6= 0}. We write simply exp(f) is no confusion is possible. One Computational methods 77 has exp(fg) = exp(f)+exp(g) for all nonzero f, g ∈K[x]. If 0 6=f=f(xi) only involves one variable xi, then exp(f) = deg(f)ǫiwhere ǫiis the i-th element in the canonical basis of Nn. For each non empty subset Aof K[x] let us denote by E≺(A) (or simply E(A)) the set E≺(A) = ∪f∈A(exp≺(f) + Nn). It is easy to prove the equality E(A) + Nn=E(A). There exists a finite subset A′⊂Asuch that E(A) = E(A′) (this is a consequence of Dickson’s Lemma; see e.g. [26, p. 12]). We say that E(A) is generated by the set {exp(f)|f∈A′}. So, if A=Iis an ideal of K[x] there exists a finite subset G⊂Isuch that E(I) = E(G) is generated by {exp(g)|g∈G}. Definition 1 Let I⊂K[x]be a nonzero ideal. A finite subset G⊂Iis said to be a Gr¨obner basis of Iwith respect to the fixed monomial order ≺ if E≺(I) = E≺(G). Example 1 a) If the ideal I=hfiis principal and generated by a polynomial f then E(I)is the (hyper)-quadrant generated by exp(f), i.e. E(I) = exp(f)+Nn and then {f}is a Gr¨obner basis of I. b) Let us consider f1=x1−x2, f2=x1+x2and I⊂R[x1, x2]the ideal generated by f1, f2. With respect to the lexicographical order <lex on N2we have exp(f1) = exp(f2) = (1,0) since x2<lex x1. It is easy to prove that E(I) is the union of the quadrants (1,0) + N2and (0,1) + N2. So, {f1, f2}is not a Gr¨obner basis of Iwith respect to <lex. Nevertheless, {f1, x2}is a Gr¨obner basis of I, with respect to <lex. If E⊂Nnwe denote by c(E) = Nn\Eits complement and by K[x]c(E)the vector space of polynomials of type Pβ∈c(E)cβxβ. For the sake of simplicity we denote c≺(I) instead of c(E≺(I)) (or simply c(I) if no confusion is possible). Let us consider a vector (f1,...,fm) of nonzero polynomials in K[x]. The Division Theorem in K[x] is stated as follows: Theorem 2 (e.g. [26, p. 9] or [2, Th. 1.5.9]) For each f∈K[x]there exists a polynomial r∈K[x]c(f1,...,fm)such that f−r=Piqififor some polynomials qi. Here c(f1,...,fm) = c(∪m i=1(exp(fi) + Nn)). The qiand rcan be chosen to be unique if they satisfy certain combinatorial conditions about their supports. The support of a polynomial f=Pαcαxαis the set {α∈Nn|cα6= 0}. There exists an algorithm computing the remainder rand the quotients qistarting from fand the fi(see e.g. [2, Algorithm 1.5.1 ]). If n= 1 the Division Theorem 2 is nothing but the classical Euclidean Division Theorem. As a corollary of Theorem 2 one can prove that any Gr¨obner basis of an ideal I⊂K[x] generates I. A famous algorithm, due to B. Buchberger [12], takes as input a monomial order ≺on Nnand a finite set F={f1(x),...,fm(x)}of polynomials, and 78 F.J. Castro-Jim´enez computes a Gr¨obner basis –with respect to ≺, of the ideal Iof K[x] generated by F. As a consequence one can also compute a finite system of generators of the set E(I). The worst-case complexity of the computation of a Gr¨obner basis is doubly exponential on the degrees of the fias proved in [57]. Nevertheless, despite this theoretical bad behavior lots of invariants can be effectively computed in Algebraic Geometry using Gr¨obner basis theory (see e.g.[7]). The proof of the following Theorem uses some properties of Gr¨obner bases. Recall the notation c(I) = Nn\E(I) for any ideal I⊂K[x] and that #Zis the cardinal of the set Z. The radical √Iof an ideal I⊂K[x] is the ideal of polynomials f∈K[x] such that fe∈Ifor some integer e(which depends on f). Theorem 3 [26, pp. 37-42] Let Kbe a field and {f1=f2=···=fm= 0}a polynomial system. Let I⊂K[x]be the ideal generated by the fi. Then #c(I) = dimK(K[x] I). Moreover, if Kis algebraically closed then 1) #VK(I)<+∞if and only if dimK(K[x] I)<+∞ 2) #VK(I)≤dimK(K[x] I)and equality holds if and only if Iis a radical ideal (i.e. if and only if √I=I). If the ideal I⊂K[x] satisfies dimK(K[x]/I)<+∞we will say that Iis zero dimensional.4 Let us give a solution to problems P0, P1’, P2’, P3’ and P4’ described in Subsection 1.1. Solution to P0.- Although G. Hermann gave a solution to this problem, we can give a new one by using Gr¨obner basis. We first compute –using Buchberger’s algorithm, a Gr¨obner basis {g1,...,gr}of the ideal Igenerated by the fi and then we compute the remainder rof the division of the polynomial fby {g1,...,gr}(see Theorem 2). Then f∈Iif and only if r= 0. Solution to P1’ and P2’.- By Buchberger’s algorithm a finite system of generators of E(I) and dimK K[x] Ican be computed. By Hilbert’s Nullstellensatz (e.g. [50, p. 16]), the set VK(I) is empty if and only if I=K[x] and so, if and only if any Gr¨obner basis of Icontains a nonzero constant polynomial. Here Kis an algebraic closure of K. This result gives the answer to P1’. Moreover, by Theorem 3 we can test the finiteness of VK(I) since dimK(K[x]/K[x]I) = dimK(K[x]/I). To compute the exact number of solutions VK(I) we can apply Theorem 3 again and the fact that √Ican be computed (i.e. a finite system 4The Krull dimension (see e.g. [10, Chap. 8]) of the quotient ring K[x]/I is zero in this case. See Solution to P4’ in Subsection 1.2. Computational methods 79 of generators of the radical ideal √Ican be computed in an effective way,5see e.g. [26, Chap. 2, Prop. 2.7]). This solves problem P2’. As suggested by one referee this can be seen as a generalization of the one variable case. Let Ibe the principal ideal I=ht3i ⊂ C[t] then VC(I) = {0}has only one element but the dimension of the quotient vector space C[t]/I is 3. In this case √I=hti and the dimension of C[t]/√Iis 1. Solution to P3’.- For any field K, if the solution set V:= VK(f1,...,fm) is finite then there is an algorithm based in the elimination principle (see [80]) to compute Vin a finite field extension of the base field K. To have a grasp of how it works, we can show that if we calculate a Gr¨obner basis of the ideal hf1,...,fmiwith respect to an ordering for which xi> xnfor i= 1,...,n−1 —this is a special case of what are called elimination orderings— we obtain a nonzero polynomial g(xn) in the Gr¨obner basis. Once the roots of this polynomial g(xn) are known (maybe in a finite extension K′of the field K) we can substitute them in the original system to obtain (a finite number of) systems in x1,...,xn−1with coefficients in K′. This strategy is a generalization of Gaussian elimination in the linear case. It should be said that an elimination order leads to computations which are very often untractable. To avoid this bottleneck, the so-called FGLM (from J.C. Faug`ere, P. Gianni, D. Lazard and T. Mora) method can be applied in this case [29]. In practical situations a numerical approximation of a real or complex solution of a system is useful and very often even necessary if the results are accurate enough. So, in general, symbolic and numerical methods are combined to solve real or complex polynomial systems. Nevertheless, the eliminationextension methods can produce errors accumulation which are difficult to manage (see e.g. [26, p. 28-34]). To overcome these problems several strategies are used as for example the one based on the computation of the eigenvalues of some matrices attached to our starting system (cf. [26, Chap. 2, Sec. 4]). Solution to P4’.- If V=VK(f1,...,fm) is infinite the previous method using elimination strategy fails. The key idea in this case is to consider some of the variables as “parameters” and to solve the system giving a finite number of solutions as function of these parameters. This is a generalization of what is done when the system has only finitely many solutions. This “parametric” method can be done in a systematic way applying for example Noether’s Normalization Lemma (e.g. [5]) to find an integer r, 1 ≤r≤n and new coordinates y1,...,ynsuch that for each point (a1,...,ar)∈Krthe system defined by {g1(a1,...,ar, yr+1,...,yn),...,gm(a1,...,ar, yr+1,...,yn)} has finitely many solutions and we can apply the previous case to solve it. Here the polynomials gi(y) come from the fj(x) by the variable change. This procedure is also algorithmic and the integer ris called the (Krull) dimension (see e.g. [10, Chap. 8]) of the algebraic set V. (See e.g. [54]). Let us finish this subsection by quoting that the Division Theorem and 5In our case, since dimK(K[x]/I)<+∞, the computation of √Iis much easier than for general ideals. 86 F.J. Castro-Jim´enez o6 : Ideal of QQ [x, y, dx, dy] i7 : J=ideal(dx,dy) o7 = ideal (dx, dy) o7 : Ideal of W i8 : J==I o8 = true Input line i4 defines the operators P1, P2 generating the ideal I(the corresponding definition in Macaulay is the input line i5. The computation of the input line i6: charIdeal I gives the ideal o6: ideal (dy, dx). Notice that as remarked by Macaulay output o6 : Ideal of QQ [x, y, dx, dy] the ideal given by o6: ideal (dy, dx) is in fact an ideal of the ring QQ [x, y, dx, dy] which is considered to be a commutative polynomial ring while Wis the Weyl algebra of order 2. In fact, the last part of the script (from i7 to o8) proves that the ideal I equals the ideal A2(∂1, ∂2). We are using here x=x1,y=x2. In the Weyl algebra Wthe expressions dx, dy stand for ∂1and ∂2while in QQ [x, y, dx, dy] they stand for ξ1and ξ2respectively. The previous computation can be also made by hand although they are not completely obvious. If I=A2(P1, P2) as in Example 2 we have proven that gr(I) = hξ1, ξ2iand then the equality Char(A2/I) = C2×{(0,0)}. Let’s see another example using Macaulay 2. Example 3 The following Macaulay 2 script computes gr(J)for J= A2(Q1, Q2)and Q1=∂2 1−∂2, Q2=x1∂1+ 2x2∂2. i2 : R=QQ[x,y] i3 : W2=makeWA R i4 : Q1=dx^2-dy,Q2=x*dx+2*y*dy o4 = (dx^2 - dy, x*dx + 2y*dy) o4 : Sequence i5 : J = ideal (Q1,Q2) o5 = ideal (dx^2 - dy, x*dx + 2y*dy) o5 : Ideal of W2 i6 : charIdeal J o6 = ideal (dx^2 , x*dx + 2y*dy) o6 : Ideal of QQ [x, y, dx, dy] Computational methods 87 The input J = ideal(Q1, Q2) defines the ideal Jof the Weyl algebra W generated by the linear differential operators Q1, Q2. Then the input i6 : charIdeal J computes the graded ideal gr(J). Then gr(J)is generated by the polynomials ξ2 1, x1ξ1+ 2x2ξ2and the characteristic variety Char(A2/I)is the union of the two planes ξ1=x2= 0 and ξ1=ξ2= 0 in C4. By definition the dimension of a finitely generated nonzero An–module M, denoted by dim(M), is the dimension13 of its characteristic variety dim(vchar(M)) viewed as an algebraic variety in C2n. The modules A2/I and A2/J of Examples 2 and 3 have both dimension 2 since their characteristic varieties are, in the first case, the plane C2×0 in C4and the union of the planes ξ1=x2= 0 and ξ1=ξ2= 0 (again in C4) in the second case. A fundamental result due to I.N. Bernstein [8] says that if M6= 0 then dim(M)≥n. If M=An/I (and more generally if Mis a quotient of a free An–module) the dimension of Mcan be computed using Gr¨obner basis in An. To this end we first notice that dim(An/I) = dim Char(An/I) if the Krull dimension of the quotient ring C[x, ξ]/gr(I) (see e.g. [10, Chap. 8]). We first compute a system of generators of gr(I) –assuming that a system of generators of Iis given– and then, applying again Gr¨obner basis computation, this time in the polynomial ring C[x, ξ], we compute the Krull dimension of C[x, ξ]/gr(I)14. Definition 5 A finitely generated An–module Mis said to be holonomic (or a holonomic system) if either M= (0) or Mis nonzero and dim(M) = n. Holonomic systems generalize the classical notion of maximally overdetermined systems (see [46]). The previous examples A2/I and A2/J are holonomic. Remark 2 If K=AnPis the principal ideal generated by P∈Anand the quotient M=An/K is non zero then Mis holonomic if and only if n= 1. In fact gr(K)is just generated by the principal symbol σ(P)∈C[x, ξ]and the characteristic variety Char(M)is the hypersurface defined by the polynomial σ(P)(x, ξ)in C2n. So dim(M) = 2n−1and dim(M) = nif and only if n= 1. Let I⊂Anbe an ideal. We define, following [70], the holonomic rank of the ideal Ias rank(I) = dimC(x) C(x)[ξ] C(x)[ξ]gr(I) where C(x) is the field of rational functions and gr(I)⊂C[x, ξ] is the graded ideal associated with I. It is easy to see that if An/I is holonomic then rank(I)<+∞and that the converse is not true (see e.g. [70, Prop. 1.4.9]). 13We are considering here the Krull dimension (see e.g. [10, Chap. 8]). 14Actually only a single Gr¨obner basis of Iis needed if the monomial ordering if suitably chosen. 88 F.J. Castro-Jim´enez 2.4 Solutions of a system. Homological algebra over An We start by recalling some basics of homological algebra. A (cochain) complex (V•, d•) of C–vector spaces is a collection of C–vector spaces Vi,i∈Z, and C–linear maps di:Vi→Vi+1 such that di+1 ◦di= 0 for all i(or equivalently if im(di−1)⊂ker(di) for all i). We make analogous definition for complexes of An–modules and morphisms of An–modules. Given a complex (V•, d•) its cohomology in degree i(or its i-th cohomology group) is the quotient ker(di)/im(di−1). Definition 6 A complex (V•, d•)is exact in degree iif im(di−1) = ker(di)and the complex is said to be exact (or an exact sequence) if it is exact in degree i for all i. Let us consider a LPDE P(u) = P(x, ∂)(u) = 0 and suppose we want to compute its solutions in some function space Fwhere Anacts naturally. The space Fshould be then an An–module. Typical examples of such spaces are function spaces (continuos functions, real analytic or holomorphic functions, polynomial functions ...), spaces of multivalued functions and spaces of distributions. A central question in the theory of Differential Equations is to compute the solution set Sol(P;F) = {u∈ F such that P(u) = 0}. Actually, this solution vector space is nothing but the kernel of the morphism P( ) : F → F defined by the action of Pon F. So one has Sol(P;F) = ker(P( )). Notice that as Anis non commutative P( ) is only a C–linear map. Let us denote M=An/AnP. We will see that Sol(P, F) is isomorphic, as vector space, to HomAn(M, F) the space of An-morphisms from Mto F15. Each solution u∈Sol(P;F) determines the morphism (of An–modules) φu:M→ F defined by φu(Q) = Q(u) for Q∈An, where Qstands for the class of Qmodulo the ideal AnP. On the other hand, each An–module morphism φ:M→ F (i.e. each φ∈HomAn(M, F)) determines the solution uφ=φ(1) 15Someway, an analogous situation happens when solving a system Sof complex polynomial equations with only finitely many solutions (that is the set VC(S) is finite). There exists a natural bijection from VC(S) to HomC(C[x]/hSi,C) defined by attaching to each solution a∈ VC(S) the corresponding evaluation homomorphism (g(x)7→ g(a)) Computational methods 89 since P(φ(1)) = φ(P·1) = φ(0) = 0. So the solution space Sol(P;F) is naturally isomorphic to the vector space HomAn(M, F). Similarly we can prove that if I⊂Anis an ideal then the solution space Sol(I;F) = {u∈ F |P(u) = 0,∀P∈I} is naturally isomorphic, as a vector space, to HomAn(An/I, F). Let us return to the case of the complete equation P(u) = vwhere vis in F. The obstruction to solve this equation is given by the vector space F/P(F) = coker(P( )) that is the cokernel of the map P( ) : F → F. That is, for a fixed v∈ F, the equation P(u) = vhas a solution uin Fif and only if v∈P(F) or equivalently if and only if the class of vin the quotient space F/P(F) is zero. More concretely, the complete equation has a solution ufor each vif and only if F=P(F) (or equivalently if and only if F/P (F) = coker(P( )) = (0)). This situation can be interpreted by using a little bit of homological algebra. This homological algebra interpretation can be also considered for more general LPDS. We will see that coker(P( )) is naturally isomorphic, as vector space, to Ext1 An(M, F) the first extension group (in this case it is a vector space) of M by F(see e.g. [68]). First of all, let us consider the natural exact sequence of modules and morphisms 0→An φP −→ An π −→ M=An AnP→0.(10) where the morphism φPis defined by φP(Q) = QP for Q∈Anand πis the natural projection. Then by truncating the previous one we consider the complex (of An-modules) 0→An φP −→ An→0.(11) We then apply to this complex the functor HomAn(−,F) and we get the complex of vector spaces 0→HomAn(An,F)(φP)∗ −→ HomAn(An,F)→0 (12) where (φP)∗(η) = η◦φPfor η∈HomAn(An,F). The vector space HomAn(An,F) has a natural structure of An–module which is in fact isomorphic to F. This is a general fact in ring theory: to each morphism η∈HomAn(An,F) we associate η(1) ∈ F and this correspondence is in fact an isomorphism. Under this isomorphism the last complex can be read as 0→ F P( ) −→ F → 0 Homological algebra tells us that we have natural isomorphisms of vector spaces ker(P( )) ≃HomAn(M, F) = Ext0 An(M, F) and F/P(F) = coker(P( )) ≃Ext1 An(M, F). 90 F.J. Castro-Jim´enez Then the vector spaces Exti An(M, F) for i= 0,1 are called the solutions spaces of the equation P(u) = 0 (or more precisely of the An–module M= An/AnP) in F. In order to generalize this notion of solutions spaces for general systems as (5) we have to consider the corresponding An-module M=Am n/im(P) where im(P) is the submodule of Am ngenerated by the rows of the matrix (Pij)ij (appearing in System (5)). By definition the solutions spaces of Min Fare the vector spaces Exti An(M, F) for i= 0,...,n defined using the right derived functors (see e.g. [68]) of the functor HomAn(−,F). By definition Exti An(M, F) is the i-th cohomology group of the complex HomAn(L•,F) where L•is a free resolution (see Subsection 2.5) of M. For general systems as (5) and general function spaces Fthere is no algorithm to compute the solution spaces Exti An(M, F). Nevertheless, if M=An/I is holonomic (see Definition 5) and F=C[x] there are algorithms computing a basis of Exti An(M, F) for all i, ([61], [81]). As a consequence of Cauchy Theorem (see e.g. [70, Th. 1.4.19]) we have dimCSol(I;OCn(U)) = rank(I) where the system An/I is holonomic and OCn(U) stands for the space of holomorphic functions on an open set U⊂Cn\Zwhere Zis the singular locus of An/I (see Definition 4). This result could be compared with Theorem 3. 2.5 Free resolutions The exact sequence (10) is an example of free resolution of the An–module An/AnP. A free resolution of a finitely generated An–module Mis an exact sequence 0→L−r φ−r −→ L−r+1 φ−r+1 −→ ··· φ−2 −→ L−1 φ−1 −→ L0 φ0 −→ M→0 where each Liis a free An–module of finite rank. As an application of Gr¨obner basis theory over the ring Anone can compute (see e.g. [15], [70]), starting from a system of generators {P1,...,Pℓ}of an ideal I⊂An, a system of generators of the first syzygy module of {P1,...,Pℓ}which is by definition the module Syz(P1,...,Pℓ) := {(Q1,...,Qℓ)∈Aℓ n|X i QiPi= 0}. In fact one can also compute Syz(P1,...,Pℓ) for any finite set of vectors Pi in Am n, for any m. Given M=Am n/hP1,...,Pℓione can consider the exact sequence Aℓ n φ −→ Am n−→ M−→ 0 where φis the map defined by the matrix whose rows are the vectors Piand we have, by definition of syzygy, ker(φ) = Syz(P1,...,Pℓ)⊂Aℓ n. Computational methods 91 One can compute, using Gr¨obner bases, a system of generators {S1,...,Sk} of ker(φ). This leads to a new exact sequence Ak n ψ −→ Aℓ n φ −→ Am n−→ M−→ 0 where ψ(ei) = Si,eibeing the i-th canonical vector in Ak n. Let us rename r0=m, r1=ℓ, r2=k,φ1=φ, φ2=ψ. Restarting with the matrix φ2one can compute, for each i≥0 and by applying the same process, a finite sequence of modules and morphisms Arp n φp −→ ··· −→ Ar2 n φ2 −→ Ar1 n φ1 −→ Ar0 n−→ M→0 which is exact (see Definition 6). One can apply the same argument as in the Syzygies Hilbert Theorem (see e.g. [26, Chap. 6], [15]) to assure that there is an integer psuch that ker(φp) = 0. This process gives up a finite free resolution of the given An–module M. Finite free resolutions are useful to study finitely generated An–modules. As we have seen before, given a system as (5) we consider the associated module M=Am n/hP1,...,Pℓiwhere Pi= (Pi1,...,Pim). The polynomial solutions (u1,...,um) of System (5) can be simply viewed as the vector space HomAn(M, C[x]). If we apply the functor HomAn(−,C[x]) to the complex 0−→ Arp n φp −→ ··· −→ Ar2 n φ2 −→ Ar1 n φ1 −→ Ar0 n−→ 0 and then we compute the cohomology of the resulting complex we get the vector spaces Exti An(M, C[x]) for i= 1,...,nwhich are considered as the higher order polynomial solutions of System (5). As we have said before, if Mis holonomic (see Definition 5) one can effectively compute, using Gr¨obner bases, a generating system for the vector spaces Exti An(M, C[x]) for any i(see [61], [81]). Since these algorithms uses Gr¨obner bases computation in the Weyl algebra Anthey have a high complexity. Syzygies and finite free resolutions are fundamental tools in Computational Algebraic Analysis. They are intensively used in the computation of the four operations –localization, local cohomology, restriction and integration, on differential systems [60] (see also [70]) and in the computation of truncated holomorphic solutions of holonomic systems as shown in [78]. 3 More applications of Gr¨obner bases for LDOs Gr¨obner basis theory is also used in many other situations related to An– modules. Let’s just quote its use in the computational study of projective16 An–modules. In [30] there is an algorithm to compute a basis of a projective 16A module Mis projective provided there is a module Nsuch that the direct sum M⊕N is a free module. 92 F.J. Castro-Jim´enez module over An, if it has one (see [76] for a proof that every projective Anmodule with rank greater than 1 is free). These results are also related to [53] and [43]. In Subsections 3.1 and 3.2 we will sketch two more areas of D-modules where the use of computational methods give significant insights into the theory. 3.1 Regular singular points. Regular D–modules and slopes Let us consider a single equation P(t, d dt)(u) = p0(t) + p1(t)d dt +···+pm(t)dm dtm(u) = 0 (13) of order m≥1 defined on an open disc ∆ ⊂Ccentered at the origin and where each coefficient pi(t) is a holomorphic function on ∆. A point t0∈∆ is said to be singular for P(u) = 0 if pm(t0) = 017. Assume the origin 0 ∈∆ is the only singular point of P(u) = 0 on ∆. In particular the characteristic variety of this linear differential equation is Char(P) = {0}×C∪∆×{0}. By a classical result of Ordinary Linear Differential Equations (cf. [34, 410411]) each multivalued holomorphic solution ϕof P(u) = 0 on ∆∗= ∆ \{0}, can be written as ϕ= ℓ X i=1 ci(t)tαilogνit where αi∈C,νi∈Nand ci(t) is an uniform analytic function on ∆∗. The equation P(u) = 0 has a regular singular point at 0 if for all solutions ϕ multivalued on ∆∗the corresponding analytic functions ci(t) are meromorphic for all i. If some of the ci(t) has an essential singularity at 0 then the origin is said to be an irregular singular point for P(u) = 0. The Maple command DEtools[formal sol] gives the formal series solutions –up to any order, of a given ordinary differential equation at a fixed point. This is the Maple script for the Euler equation which has an irregular singular point at 0. > Eu:=t^2*Dt+1; 2 Eu := t Dt + 1 > sol:=formal_sol(Eu,[Dt,t],S,’terms’=12,t=0); 12 sol := [[exp(1/S) (1 + O(S )), S = t]] 17This notion agrees with the one of singular locus given in Definition 4. Computational methods 93 The classical Gauss hypergeometric equation t(1 −t)d2 dt2+ (γ−t(α+β+ 1)) d dt −αβ(u) = 0 where α, β, γ ∈C, has two regular singular points in the complex line C, namely the points 0,1∈C. The following Maple script gives the two linearly independent formal solutions –up to order 4, of the given Gauss hypergeometric equation for α=β= 1 and γ=i∈C > with(DEtools): > L:=t*(1-t)*Dt^2+(I-3*t)*Dt-1; 2 L := t (1 - t) Dt + (I - 3 t) Dt - 1 > sol:=formal_sol(L,[Dt,t],T,’terms’=4,t=0); 2 3 4 sol := [[1 - I T + (-1 - I) T + (-9/5 - 3/5 I) T + O(T ), T = t], (1 - I) 2 3 4 [T (1 + (2 - I) T + (5/2 - 5/2 I) T + (5/2 - 25/6 I) T + O(T )), T = t]] From the very definition it is difficult to see whether a given point is regular singular. The fundamental theorem of Fuchs (cf. [44, 15.3]) states that the origin is a regular singular point for Equation (13) if and only if the order of the pole at 0 of the meromorphic function pi(t)/pm(t) is less or equal than m−i, i= 0,...,m. This theorem can be restated in terms of the so-called Newton or Newton-Puiseux polygon of the equation P(u) = 0 (see e.g. [51]). The notion of regular singular point for a differential system as (5) in higher dimension –dated only on the last 70’s, is due to several authors, especially to Z. Mebkhout, M. Kashiwara and T. Kawai. This definition of regular singular point of a differential system in dimension nis highly abstract and uses derived categories and functors. To this end Z. Mebkhout introduced the irregularity sheaves of a holonomic module along hypersurfaces [58]. In [51] the notion of slope of a differential system at a point in Cnis introduced. In [52] the authors gave an equivalent definition of regular singular point (or more precisely of regular system) that can be effectively computed starting with a system of differential equations and using again Gr¨obner basis theory, provides the system is holonomic. The key point is the computation of the slopes of a holonomic An–module. A holonomic module Mis said to be regular at a point in Cnif Mhas no slopes at that point. The computation of the slopes can be done by the so-called ACG algorithm [4]. This algorithm uses Gr¨obner bases as a fundamental tool. The works [17], [39, 40], [73] are related to the computation of the slopes for hypergeometric systems18. 18For the theory of hypergeometric systems see [33]. The book [70] deals with the computational treatment of this kind of differential systems. 94 F.J. Castro-Jim´enez 3.2 Bernstein-Sato polynomial Let f∈C[x] = C[x1,...,xn] nonconstant and let sbe a new variable. Consider the Weyl algebra An(C(s)) over the field C(s) of rational functions in sand the An(C(s))–module N=C(s)[x1,...,xn, f−1]·fs, where fsis considered as a formal symbol and the An(C(s))-action on Nis defined by ∂j(fs) = sf−1∂f ∂xj fs the product rule and the formal differentiation of rational functions. Let M=An(C(s))fsbe the submodule of Ngenerated by fs. We can see in [8] that both modules are holonomic (see Definition 5) over An(C(s)), and that Mhas finite length. This means that there exists Q(s)∈An(C(s)) such that fs=Q(s)(fs+1).If b(s) is the common multiple of the denominators of the coefficients of Q(s) and P(s) = b(s)Q(s) we have P(s)(fs+1) = b(s)fs(14) where P(s)∈An[s] and b(s) are not uniquely defined by the functional equation (14). The set of all b(s) satisfying Equation (14) for some P(s) is a nonzero ideal in C[s] whose (monic) generator bf(s) is called the Bernstein-Sato polynomial of for the b-function of f. It was introduced by I.N. Bernstein [8] and by M. Sato [71]. As an example of Bernstein-Sato polynomial, taking f=Pn i=1 x2 ione has the identity n X i=1 ∂2 ∂x2 i(fs+1) = 4b(s)fs, where b(s) = (s+ 1)(s+n 2). It is not difficult to prove that in this case b(s) = bf(s). The Bernstein-Sato polynomial bf(s) is always multiple of (s+ 1) and equality holds if fis smooth. M. Kashiwara proved that its roots are always rational and negative [47]. B. Malgrange pointed out the connection between the singularity structure of f−1(0) and the roots of bf(s) [56]. Until [59] there were not an algorithm for the computation of bf(s). We can use Risa-Asir [62] for example, to compute the b-function of a polynomial. Another interesting information included in bf(s) is related to the module structure of the localization of the ring C[x] by f, noted by C[x]f, that is, the ring of rational functions with poles along f(that is along the hypersurface f= 0) C[x]f=g fm|g∈C[x], m ∈N. C[x]fis a C[x]-module and an An-module in a natural way. Of course if f is not a constant C[x]fis not a finitely generated C[x]-module. We have an analogous situation in the analytic setting, i.e. starting from f∈C{x}, the Computational methods 95 ring of convergent power series around 0, and considering C{x}f, the ring of (germs of) meromorphic functions with poles along f, as a Dn-module, where Dn= Diff(C{x}) is the ring of linear differential operators over C{x}(see Remark 1). One of the main results in D-module theory is the following theorem: Theorem 4 ([8]) For any f∈C[x], the An-module C[x]fis finitely generated. More precisely, there exists a positive integer number αsuch that C[x]fis the An-module generated by the rational function 1 fα. The analogous version for the analytic case was proved in [9]. The main ingredient in the proof of Theorem 4 is the existence of the b-function attached to fand the positive integer postulated is −α0if α0is the smallest integer root of bf(s). So we have the following problem: Problem.- Let f∈C[x]. Give a presentation of C[x]fas a finitely generated An-module. A way to solve the problem is to: Compute bf(s) and α0. As C[x]f≡Anfα0, compute a system of generators of the annihilating ideal annAn(fα0) = {P∈An|P(fα0) = 0}, and then C[x]f≃An annAn(fα0). There are algorithms based in Gr¨obner bases for LDOs to obtain bf(s) (see [59, 60]) and the annihilating ideal of a power of f[60]. Unfortunately, many interesting examples can not be treated due to the size of the intermediate computations. Nonetheless, it is possible to obtain the so called logarithmic D-modules that are natural approximations to C[x]f. 3.3 Logarithmic D-modules The starting point of this approach are the works of K. Saito [69] about logarithmic vector fields and logarithmic differential forms. After [13] the connection with D-modules of this subject became very important. Here we will treat only the global (algebraic) case of logarithmic An-modules to simplify. Let D⊂Cnbe an hypersurface —usually called a divisor in algebraic geometry— defined by f∈C[x]. A vector field with polynomial coefficients δ= n X i=1 ai(x)∂i is said to be logarithmic with respect to Dif δ(f) = af for some a∈C[x]. The C[x]-module of logarithmic vector fields is denoted by Der(−log D). 102 F.J. Castro-Jim´enez [76] J.T. Stafford. Module structure of Weyl algebras. J. London Math. Soc., 18:429–442, 1977. [77] B. Sturmfels. Solving systems of polynomial equations. American Mathematical Society, 2002. [78] N. Takayama. An Algorithm for Constructing Cohomological Series Solutions of Holonomic Systems. Arxiv preprint math.AG/0309378, 2003. [79] T. Torrelli. On meromorphic functions defined by a differential system of order 1. Bull. Soc. Math. France 132(4):591–612, 2004. [80] W. Trinks. ¨ Uber B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu l¨osen. J. Number Theory 10 (1978), no. 4, 475-488. [81] H. Tsai and U. Walther. Computing homomorphisms between holonomic D-modules. J. Symbolic Comput. 32(6):597–617, 2001. [82] W.T. Wu. Mathematics mechanization. Mechanical geometry theoremproving, mechanical geometry problem-solving and polynomial equationssolving. Mathematics and its Applications, 489, Kluwer, 2000. [83] D.C. Youla and P.F. Pickel. The Quillen-Suslin theorem and the structure of n-dimensional elementary polynomial matrices. IEEE Trans. Circuits and Systems, 31(6):513–518, 1984.