Computing localizations iteratively

arXiv:1110.0182v2 [math.AG] 22 Nov 2011 COMPUTING LOCALIZATIONS ITERATIVELY FRANCISCO-JES´ US CASTRO-JIM´ ENEZ AND ANTON LEYKIN Abstract. Let R=C[x] be a polynomial ring with complex coefficients and DX=Chx,∂ibe the Weyl algebra. Describing the localization Rf=R[f−1] for nonzero f∈Ras a DX-module amounts to computing the annihilator A= Ann(fa)⊂DXof the cyclic generator fafor a suitable negative integer a. We construct an iterative algorithm that uses truncated annihilators to build A for planar curves. Introduction Let f∈R:= C[x1,...,xn] be a nonzero polynomial (nbeing a positive integer) and Rfthe localization of the polynomial ring Rwith respect to f. Elements in Rfare rational functions g fkwith g∈R and k∈N. If fis not a constant, the R–module Rfis not finitely generated. One fundamental result by J. Bernstein states that Rfis finitely generated when considered as a left module over the complex Weyl algebra An:= An(C) of order n(see the needed definitions and precise statements in the next Section). This is a fundamental result in D–module theory (the algebraic theory of systems of linear partial differential equations) which can be considered as part of Singularity Theory. Bernstein’s result states even more: the module Rfis cyclic over An and in fact it is generated by a rational function of the form fafor some negative integer a. That means that Rfcan be described as a quotient An Ann(fa)where Ann(fa) := AnnAn(fa) is the left ideal in Anformed of the linear differential operators annihilating the rational function fa. By [14] (see also [29] and [23]) one can take a=−n+ 1. One main problem in algorithmic D–module theory is to compute a finite system of generators of the annihilating ideal Ann(fa). There are several algorithms solving this problem (see e.g. [19], [21], [20]), F.-J. Castro-Jim´enez. Depto. ´ Algebra. Universidad de Sevilla, Sevilla, Spain([email protected]). Partially supported by MTM2010-19336 and FEDER, FQM-333 and FQM-5849 Junta de Andaluc´ıa. Anton Leykin. School of Mathematics, Georgia Tech, Atlanta GA, USA ([email protected]). Partially supported by NSF grant DMS-0914802. 1 2 FRANCISCO-JES ´ US CASTRO-JIM´ ENEZ AND ANTON LEYKIN which use Gr¨obner bases and elimination theory in the Weyl algebra An. In the worst case, computing Gr¨obner bases has a doubly exponential complexity in both (commutative) polynomial rings and the Weyl algebra (see [1] and [13]); however, in practice, one should expect much longer running times for the latter on the input of the same size. As the Weyl algebra Anis a Noetherian ring, one can associate to the couple (f, a) the smallest integer κ(fa) such that Ann(fa) is generated by operators of order less than or equal to κ(fa). This numerical invariant plays a relevant role in the so called Logarithmic Comparison Problem with respect to the hypersurface defined in the complex affine space Cnby the polynomial equation f= 0 (see e.g. [10], [27]). In this paper we describe a new algorithm computing Ann(f−1) for any reduced complex polynomial f=f(x, y) in two variables. This algorithm uses Gr¨obner bases techniques in both polynomial rings and the Weyl algebra A2, but avoids elimination theory in the latter: our experiments show that the bottleneck of the algorithm is a syzygy module computation over the former. We first compute iteratively, for d= 1,2,..., truncated annihilating ideals Ann(d)(f−1) generated by linear differential operators annihilating f−1and of order less than or equal to d. The ideal Ann(d)(f−1) can be computed by using polynomial Gr¨obner basis. We then compute equations for the characteristic cycle of the ideal Ann(d)(f−1) and compare it with the one of Ann(f−1) which only depends on the multiplicity of the plane curve f= 0 at its singular points; for the beforementioned comparison we only need to localize at each of these singular points. The paper is organized as follows. In the first Section we survey basic results on the Weyl algebra, holonomic D-modules, b-functions (or Bernstein-Sato polynomials) and the annihilating ideal of some rational functions on Cn. In Section 2 we describe the new iterative algorithm, we give a stopping criterion and prove its correctness. We also treat some examples, in particular the so called family of Reiffen’s curves fp,q. Our implementation of the algorithm in Macaulay2 works on larger examples of Reiffen’s curve family than the known general algorithm and our experiment demonstrates an interesting (very simple!) dependence of the order of generation of Ann(d)(f−1 p,q ) on p. In the last Section we conclude the discussion and propose some open questions on the subject. 1. Preliminaries 1.1. Weyl algebra. Let n≥0 be an integer and X=Cnbe the ndimensional complex affine space. Define the n-th Weyl algebra as the COMPUTING LOCALIZATIONS ITERATIVELY 3 associative algebra DX=Chx,∂i=Chx1,...,xn, ∂1,...,∂ni where [∂i, xi] = ∂ixi−xi∂i= 1 and all other pairs of generators commute. The Weyl algebra DXis isomorphic to the algebra of linear differential operators with coefficients in the polynomial ring R=C[x] = C[x1,...,xn]. Every element in DXhas a unique normal form Q=X α,β∈Nn qαβxα∂β, where finitely many of qαβ ∈Care nonzero and where xα∂βstands for xα1 1···xαn n∂β1 1· · · ∂βn n. We denote the n-th Weyl algebra Anif we need to emphasize the dimension of X; throughout this paper DX=A2is used the most. The ring DXis simple: there are only trivial two-sided ideals. All DX-ideals and DX-modules considered in this article are left ideals and modules, respectively. Examples of DX-modules include functional spaces, e.g., polynomial functions C[x] and smooth functions C∞(X), and power series rings C[[x]]. Another example is the localization of the polynomial ring C[x, f−1] where fis a nonzero polynomial with the natural action defined as follows: xi·gf−j=xigf−j, ∂i·gf−j=∂g ∂xi f−jg ∂f ∂xif−j−1, for 1 ≤i≤n,g∈C[x], and j∈N. 1.2. Gr¨obner bases. It is possible to compute in the Weyl algebra DX, since it is Gr¨obner friendly; see e.g. [8, 9], [24] and [15]. Gr¨obner bases can be computed with respect to any w-compatible monomial order, where w= (wx, w∂)∈R2nsatisfies wx+w∂≥0componentwise. This condition, in particular, guarantees that the filtration {Fw i}i∈Zof DX, where Fw i= Span xα∂β:α, β ∈Nn, w ·(α, β)≤i, is preserved under taking the commutator. Therefore, the associated graded algebra grw(DX) is well defined. Note that •if wx+w∂=0then grw(DX) = DX; 4 FRANCISCO-JES ´ US CASTRO-JIM´ ENEZ AND ANTON LEYKIN •if wx+w∂>0componentwise then grw(DX)∼ =C[x,ξ] = C[x1,...,xn, ξ1,...,ξn], a polynomial ring in 2nvariables. The w-order of a nonzero operator Q=Pα,β∈Nnqαβxα∂β∈DX, denoted ordw(Q), is defined as the maximum of w·(α, β) for qαβ 6= 0. The initial part of Qwith respect to wis inw(Q) = X w·(α,β)=ordw(Q) qαβxαξβ∈grw(DX). We simply denote inw(0) = 0. Definition 1. Let Ibe an ideal in DX. The characteristic ideal grw(I) = inw(I)⊂grw(DX) = C[x,ξ], with w= (0, e), i.e.: w(xi) = 0 and w(∂i) = 1 for i= 1,...,n defines the characteristic variety Char(DX/I) = V(grw(I)) ⊂C2n. Here inw(I) stands for the ideal of grw(DX) generated by {inw(Q),|Q∈ I}, the set of the leading forms of the elements of Iwith respect to the weight w. The set V(J), for an ideal Jin C[x,ξ], is the variety in C2n defined by the ideal J. If Mis a nonzero finitely generated DX–module, one can define, following [2], its characteristic variety Char(M)⊂C2nby using any good filtration on M. The set Char(M) is an affine algebraic subset of C2n. In particular one can consider its Krull dimension dim(Char(M)). To each irreducible component Cof Char(M) one can associate its multiplicity mCwhich is a positive integer number. For the definition of the Krull dimension of an affine algebraic set and the multiplicity of its irreducible components one can consult [4]. Theorem 1 (Bernstein’s inequality; [2]).Let Mbe a nonzero, finitely generated DX–module. Then n≤dim(Char(M)) ≤2n. In particular, if I DXis a left ideal, then n≤dim(Char(DX/I)) ≤2n. There is a number of software implementations of D-module algorithms: kan/sm1 [26], risa/asir [18], dmod.lib library [16] in Singular [11], and the Dmodules package [17] in Macaulay2 [12]. The last package hosts our implementations of the algorithms in this article. COMPUTING LOCALIZATIONS ITERATIVELY 5 1.3. Holonomic D-modules. A finitely generated DX-module Mis called holonomic if either M= (0) or the dimension of its characteristic variety equals n(i.e. dim(M) = n). An ideal Iin DXis called holonomic if either I=DXor DX/I is holonomic. The characteristic cycle of a holonomic DX–module Mis by definition the sum CChar(M) := X Cirreducible component of Char(M) mCC viewed as a cycle in the cotangent bundle T∗Cn. Here mCis the multiplicity of Cin Char(M). Holonomic modules are particularly nice from the point of view of computations due to the following fact. Theorem 2 (Stafford [25]).Every holonomic DX-module is cyclic. Every holonomic module Mcan be thought of as M=DX·Q, where Qis a cyclic generator, hence, M∼ =DX/AnnDX(Q). One example of a holonomic module is R=C[x]; it is generated by 1 ∈R. Another is its localization Rf=C[x, f−1], as stated by a theorem by J. Bernstein. Theorem 3 ([2, 3]).Let f∈C[x]be a nonzero polynomial. Then the DX-module Rfis holonomic. Moreover, for some negative integer a the element fa∈Rfgenerates Rfas a DX-module. Computing the annihilator AnnDX(fa) is the main topic of this article. By [2, 3] the largest possible exponent a=a(f) above is equal to the smallest integer root of the Bernstein-Sato polynomial bf(s)∈Q[s], defined as the monic nonzero polynomial b(s) of the smallest possible degree such that b(s)fs=Q(s, x,∂)·fs+1,where Q∈DX[s] := C[s]⊗CDX. The idea of many localization algorithms (first formulated by Oaku [19] in 1996) is simple to state: (1) Compute Ann(fs) as an ideal of DX[s]. (2) Compute bf(s) to determine a=a(f). (3) Specialization: Ann(fs)|s=a. This approach, for example, is implemented in the function Dlocalize of the Dmodules package. The bottlenecks of the algorithm are items 1 and 2 that require an expensive elimination via Gr¨obner bases in the Weyl algebra DX. Step 2 can be avoided by using the following estimate 6 FRANCISCO-JES ´ US CASTRO-JIM´ ENEZ AND ANTON LEYKIN Theorem 4 ([14], see also [29], [23]).Rfis generated by f−n+1. As a corollary, for planar curves f∈C[x, y], localization Rf=DX· f−1=DX/Ann(f−1). Remark 1. Note that one can easily compute the annihilator of a rational function in the the algebra of linear differential operators with rational function coefficients C(x)[∂] = C(x)⊗C[x]DX: the annihilator is a maximal ideal of C(x)[∂], e.g., AnnC(x)[∂](fa) = C(x)⊗AnnDX(fa) = hf∂i−a∂f ∂xi |i= 1,...,ni. 2. Iterative algorithm Our main example will be the family of the so-called Reiffen’s curves; see [22]. f=fp,q =xp+yq+xyq−1= 0, where p≥4, q ≥p+ 1. Example 1. Computing the annihilator (this can be done via AnnFs followed by specialization s=−1), Ann(f−1 4,5) = h4x2∂x+ 5xy∂x+ 3xy∂y+ 4y2∂y+ 16x+ 20y, 16xy2∂x+ 4y3∂x+ 12y3∂y−125xy∂x−4x2∂y+ 5xy∂y−100y2∂y+ 64y2−500y, 16y3∂2 x−16y3∂x∂y+ 125xy∂2 x−35xy∂x∂y+ 100y2∂x∂y+ 12x2∂2 y−2xy∂2 y−24y2∂2 y+ 112xy∂x−36y2∂x+ 84y2∂y−930x∂x+ 625y∂x+ 26x∂y− 893y∂y+ 448y−3720i, we see that it is generated in order 2, i.e., generated by operators of order at most 2. One interesting question is: What is the order of generation of this annihilator for a given pand q? 2.1. Iterative approach. Definition 2. We call Ann(d)(fa) = hQ∈Ann(fa)|ord Q≤di the d-th truncated annihilator of fa. To compute Ann(d)(fa) one may find the R-syzygy module Sdfor the vector of partial derivatives (∂α·fa)αwhere |α| ≤ d. COMPUTING LOCALIZATIONS ITERATIVELY 7 Example 2. To find an element in Ann(1)(f−1)for f=x2−y3consider all partial derivatives of f−1of order at most 1: ∂x·f−1=−2x f−2 ∂y·f−1= 3y2f−2 1·f−1= (x2−y3)f−2 For instance, 3x(−2x) + 2y(3y3) + 6(x2−y3) = 0, hence, 3x∂x+ 2y∂y+ 6 ∈Ann(1)(f−1). In Dmodules the function for computing the truncated annihilator is called kOrderAnnFa: i1 : loadPackage "Dmodules"; i2 : R = QQ[x,y]; i3 : f = x^2-y^3; i4 : A1 = kOrderAnnFa(1,f,-1) 2 3 2 2 o4 = ideal (3x*dx + 2y*dy + 6, 3y dx + 2x*dy, y dy - x dy + 3y ) Note that kOrderAnnFa(d,f,-1) would return the same ideal for all d∈Nas the annihilator for this particular example is generated in order 1. Remark 2. Suppose Sd−1, or in other words Ann(d−1)(fa), is known. Then the computation of Sd, or the d-th truncated annihilator, can be optimized by computing the syzygies modulo Sd−1. In practice, however, it appears that the time of the syzygy computation at order ddominates that for order d−1for all d. In particular, in Experiment 1 for the Reiffen curve of any degree the last step takes more time than all previous steps combined. 2.2. Stopping criterion. The sequence of truncated annihilators stabilizes at some point: Ann(1)(fa)⊆Ann(2)(fa)⊆ · · · ⊆ Ann(d)(fa) = Ann(d+1)(fa) = ··· Definition 3. The smallest dsuch that Ann(d)(fa) = Ann(fa)is denoted by κ(fa)and is called the annihilator order of fa. Note that Ann(d)(fa) = Ann(d−1)(fa) does not imply Ann(d+1)(fa) = Ann(d)(fa). For example, for f=xand a= 3 we have Ann(1) = Ann(2) =Ann(3) =hx∂x−3iand Ann(4) =hx∂x−3, ∂4 xi. 2.3. Annihilator order of a planar curve. In view of Theorem 4, for a planar curve defined by f∈R:= C[x, y] the localization Rfis generated by f−1. We have constructed an algorithm that computes truncated annihilators stopping exactly at the annihilator order of f−1 8 FRANCISCO-JES ´ US CASTRO-JIM´ ENEZ AND ANTON LEYKIN thus producing the whole annihilator Ann(f−1) for a plane curve with at most one singular point, that we can assume to be the origin. Algorithm 1. (d, A) =KappaAndAnnihilator(f) Input: f∈R=C[x, y], a plane curve with at most one singular point, that we can assume to be the origin. Output: d=κ(f−1),A= Ann(f−1). 1: d←0. 2: repeat 3: d←d+ 1. 4: A←Ann(d)(f−1). 5: a←primary component of grw(A)corresponding to the origin. 6: until deg a= (multiplicity of fat the origin)−1 Proof of correctness. We see X=C2as a complex manifold and consider C, the analytic plane curve defined by the polynomial equation f= 0. We assume fto be a reduced polynomial. Denote •by OXthe sheaf of holomorphic functions on X, •by DXthe sheaf of linear partial differential operators on X with holomorphic coefficients, and •by OX[∗C] the sheaf of meromorphic functions on Xwith poles on C. By [14] the sheaf OX[∗C] is a coherent holonomic DX–module. If p∈ X\Cthen OX[∗C]pis just OX,p and if the point p∈Cis a smooth point then the DX,p–module OX[∗C]pis isomorphic to the quotient DX,(0,0) DX,(0,0)(x∂x+ 1, ∂y) (for some choice of local coordinates (x, y)). So, in the neighborhood of a smooth point in C, the characteristic variety of OX[∗C] is just the union of the conormal space to C, say T∗ CXand the zero section T∗ XX. Moreover, the multiplicities of each of these components in the corresponding characteristic cycle is 1. It is well known that (see e.g. [5, Section 6]) in a sufficiently small neighborhood Uof a point p∈C, the characteristic cycle of OU[∗C] is CChar(OU[∗C]) = T∗ UU+T∗ U∩C\{p}U+ (m−1)T∗ pU where T∗ UUis the zero section of the cotangent bundle T∗U,T∗ U∩C\{p}U stands for the closure in T∗Uof the conormal bundle to the smooth part of U∩C,T∗ pUis the conormal bundle to the point pand mis the multiplicity of the plane curve Cat the point p. COMPUTING LOCALIZATIONS ITERATIVELY 9 Let us denote I:= AnnDU(f−1) and for any integer number d≥1, I(d):= Ann(d) DU(f−1) considered as a sheaf of ideals in DU. As fis a global equation for the plane curve C⊂Xwe have I(d) q= DU,qAnnDX(f−1) for any q∈U. We have the following exact sequence of holonomic DU-modules: 0→I I(d)→DU I(d)→DU I→0 and then the following equality of characteristic cycles: CChar DU I(d)= CChar DU I+ CChar I I(d). Denote by m(d)the multiplicity of the irreducible component T∗ pU in CChar DU I(d). As the ideals I(d)and Icoincide on U∩C\ {p}the holonomic DU–module I I(d)is concentrated on p. Then CChar DU I(d)= CChar DU Iif and only m(d)=m−1 (where mis the multiplicity of the plane curve Cat p∈C). We also have I(d)=Iif and only if m(d)=m−1. Once we have a finite set of polynomial equations for the characteristic ideal grw(Ann(d)(f−1)),these equations define the characteristic cycle CChar DU I(d)in the neighborhood Uof any point p∈X. The multiplicity m(d)equals the degree of the primary ideal in the primary decomposition of grw(Ann(d)(f−1)) corresponding to T∗ pU. Remark 3. The multiplicity m(d)can be also obtained as the multiplicity of the (unique) point ˜p∈T∗ pUin the intersection grw(Ann(d)(f−1))∩ Lwhere Lis the defining ideal of a generic 2-plane in the 4-dimensional ambient space. Remark 3 allows us to avoid the expensive primary decomposition step in the Algorithm 1. Assume p= 0 is the only singularity; hence, let U=Xand let S=C[x, y, ξ, η] be the ring of the characteristic ideal grw(Ann(d)(f−1)). In our implementation we set L=hξ−a, η −bi, (a, b)∈C2\{(0,0)}; in practice, aand bare taken to be small integers. The genericity of the plane Lmeans that the point ˜p= (0,0, a, b) does not belong to T∗ U∩C\{p}U. The following algorithm checks the genericity of the choice. Algorithm 2. g=CheckGenericity(f, a, b) Input: f∈R=C[x, y], a plane curve with the unique singular point at the origin. Output: g, a boolean value, whether the genericity condition described in Remark 3 is satisfied.