On the computation of Bernstein–Sato ideals

On the computation of Bernstein–Sato ideals J.M. Ucha∗,F.J.Castro-Jim´enez Depto. ´Algebra, Universidad de Sevilla, Apdo. 1160, E-41080 Sevilla, Spain Abstract In this paper we compare the approach of Brianc¸onand Maisonobe for computing Bernstein–Sato ideals—based oncomputations in a Poincar´e–Birkhoff–Witt algebra—with the readily available method of Oaku and Takayama. We show that it can deal with interesting examples that have proved intractable so far. Keywords: Bernstein–Sato 1. Introduction Let X=Cnbe the complex affine space of dimension n,Anbe the complex Weyl algebra of order nand (f1,..., fp)be polynomial functions on X,thatis fi∈C[x]= C[x1,...,xn].Letusconsider the algebra An[s1,...,sp]=An⊗CC[s1,...,sp]with the trivial action of the elements of C[s1,...,sp].Wewill write b(s), P(s)for elements b(s1,...,sp), P(s1,...,sp)in C[s]=C[s1,...,sp]and An[s]=An[s1,...,sp] respectively. Let Bbe the Bernstein–Sato ideal of (f1,..., fp)consisting of polynomials b(s)∈ C[s]such that there exists a differential operator P(s)∈An[s]satisfying b(s)fs1 1··· fsp p=P(s)fs1+1 1··· fsp+1 p. In a similar way, other Bernstein–Sato ideals can be defined, namely ∗Corresponding address: Universidad de Sevilla, Algebra Facultad de Matematicas, Apdo. 1160, E-41080 Sevilla, Spain. Tel.: +34-954-55-61-83; fax: +34-954-55-69-38. E-mail address: [email protected] (J.M. Ucha). •Bj={b(s)∈C[s]|b(s)Fs∈An[s]fjFs}for j∈{1,...,p} •BΣ={b(s)∈C[s]|b(s)Fs∈p j=1An[s]fjFs} where Fsdenotes fs1 1··· fsp p.Ifp=1thenB=B1=BΣand the monic generator of the principal ideal Bis called the Bernstein–Sato polynomial, or simply the b-function, associated with f1;seeBernstein (1972). Sabbah proved(see Sabbah,1987)intheanalytic setting that Bis not zero, generalizing previous works of Bernstein (1972)andBj¨ork (1979), both in the algebraic case and for p=1. The explicitcalculation of these ideals is of major interest: many conjecturesabout how the important properties of the case p=1appear in the general case remain open. For example: when are the Bernstein–Sato ideals principal? Also, what can be said about their primary decomposition?(In the case p=1the roots of the Bernstein–Sato polynomialare rational numbers (Kashiwara,1976).) See Maynadier (1997)formoredetails. As far as we know there are three ways of computing Bernstein–Sato ideals in the algebraic case: •The method due to Oaku and Takayama for calculating Bis described in Procedure 2.2. of Oaku and Takayama (1999). It needs the calculation of Gr¨obner bases in a polynomial algebra over a Weyl algebra. •The method proposed by Bahloul in Bahloul (2001). It provides algorithms for computing BΣand Bjfor j∈{1,...,p}by adapting a previous work of Oaku (see Oaku,1997). As it uses Gr¨obner bases with respect to nonwell-ordered cases, the calculations are made in the homogenized Weyl algebra (Castro-Jim´enez and Narv´aez-Macarro,1997). •The method recently proposed by Brianc¸onand Maisonobe in Brianc¸on and Maisonobe (2002)thatcomputes the three types of Bernstein–Sato ideal. Their approach is used to show the constructability of the Bernstein–Sato ideals with respect to the space of parameters. The calculations are made in an intermediate algebra that appears as a natural generalization of the one used by Malgrange and Kashiwara in early works for the case p=1(seeforexample Kashiwara,1976). We will refer to the first method as the OT method and the third one as the BM method. The aim of this paper is to compare the BM method as a computational (not just theoretical) alternative to the Oaku–Takayama algorithm, checking for a selected family of difficult examples in concrete implementations. As we will detail, both methods start with the calculation of the annihilator ideal AnnAn[s](Fs).Wewill provide experimental evidence for the former approach being a better alternative. In many examples the bottleneck of the calculation is not the above-mentioned annihilator but an elimination problem which occurs in a second step in both methods. Anyway, a shortcut to the annihilator leads in practice to the possibility of finding some of the Bernstein–Sato ideals (see the example in 3.4). Moreover, we think that there are interesting advantages of the BM method fromthecomplexity point of view that are not simply related to the number of variables. They need to be brought to light in future works (see the example in 3.3). 2. Preliminaries In this section we will recall the general setting of the PBW algebras and explain how the computation of the Bernstein–Sato ideals can be performed in this context. 2.1. Rn,pas a PBW algebra As in Brianc¸onand Maisonobe (2002), we will work in the non-commutativealgebra Rn,p=An[s1,...,sp,t1,...,tp]=An[s,t], an extension of the Weyl algebra Anwhere the new variables s,tsatisfy the relations [si,tj]=δijti.Aswehavementioned it is, in fact, a ring analogous to the one introduced by Malgrange and Kashiwara for p=1. The elements of Rn,pcan be represented as polynomials in a finite number of variables due to the following lemma: Lemma 2.1. In the algebra Rn,pthe following formulas hold: 1. For the set of variables x1,...,xnand ∂1,...,∂ nwe have ∂β ixα i= β  k=0β k∂k i(xα i)∂β−k i, for i ∈{1,...,n},where∂i(a)stands for the partial derivative of a with respect to xi. 2. For the set of variables s1,...,spand t1,...,tpwe have sλ itµ i= λ  j=0λ jµjtµ isλ−j i, for i ∈{1,...,p}. Proof. The property (1) is very well known as a special case of the Leibnitz formula.The proof of (2) is very easy—by induction taking into account the easier formula sitβ i=tβ isi+βtβ i. Roughly speaking, you can choose a normal form for the elements of Rn,pusing monomials with the x,tvariables to the left and ∂,sto the right, so the set M={xα1 1···xαn n∂β1 1···∂βn ntλ1 1···tλp psµ1 1···sµp p=xα∂βtλsµ |with (α, β,λ,µ)∈N2n+2p} forms a basis of Rn,pas a vector space over C. On the other hand, you can consider the total degree <(the sum of all of the exponents for every variable) in the exponents of the monomials of Mto ensure that xα∂βtλsµ·xα∂βtλsµ=xα+α∂β+βtλ+λsµ+µ+M, where M∈Rn,pis asum of monomials with exponents less than (α +α,β +β, λ+λ,µ+µ)with respect to <. The last two properties—the existence of a C-basis and the good behaviour of the product of monomials—are the conditions needed to define a Poincar´ e–Birkhoff–Witt algebra.Thework(Kandri-Rody and Weispfenning,1990)(seealsoBueso et al.,1998) is a good introduction to the subject of effective calculus in this very general family of rings which contains, for example, the iterated Ore extensions.Inparticular it is proved there that basic topics of computational commutative algebra such as Gr¨obner bases, the Buchberger algorithm and elimination orders can be developed in these PBW algebras. 2.2. AnnAn[s](Fs)and the Bernstein–Sato ideals from Rn,p Let us consider the left An-module M=C[x][s,1 F]Fswhere Fis theproduct of the fi.Mhas a natural structure of a left Rn,p-module where siacts by multiplication and the action of tiis defined by tia(x,s)Fs=−a(x,s−i)si1 FiFs, where a(x,s)is an element of C[x][s,1 F]and iis the ith element of the canonical basis in Np. FollowingBrianc¸onandMaisonobe(2002),andlikeinMalgrange(1975),considering the annihilating ideal of Fsin the ring Rn,pis the main point. It is generated by the family sj+fjtj,∂ i+ l ∂fl ∂xitl i=1,...,n;j=1,...,p. So the annihilator of Fsin An[s]is AnnRn,p(Fs)∩An[s].Onceyou have the annihilator, the Bernstein–Sato ideal Bcan be calculated by eliminating the variables xi,∂ i,tj, i.e. computing B=((AnnRn,p(Fs)∩An[s])+An[s]F)∩C[s].(1) Of course the formulas are analogous for BΣand Bj,j=1,...,p: BΣ=((AnnRn,p(Fs)∩An[s])+An[s] f1,..., fp)∩C[s],(2) Bj=((AnnRn,p(Fs)∩An[s])+An[s] fj)∩C[s].(3) 2.3. The algorithm in Rn,p We have in fact presented the following algorithm in the preceding section. The orderings <t(respectively <s)denote any elimination orderings that consider the variables t (respectively s)greater than the others. INPUT:f1,..., fp∈C[x]. OUTPUT:Theideals B,Band Bjfor j=1,...,p. (Step 1) I:= AnnRn,p(Fs)=sj+fjtj,∂ i+l∂fl ∂xitl,1≤i≤n,1≤j≤p. Compute a Gr¨obner basis Gof Iwith respect to <t. J:= I∩An[s]=G∩An[s]. (Step 2) K:= J+f1··· fp, K:= J+f1,..., fp, Kj:= J+fjfor j=1,...,p. Compute Gr¨obner bases GK,G,G1,...,Gpof K,K,K1,...,Kp with respect to <s. (Step 3) B=K∩C[s]=GK∩C[s], B=K∩C[s]=G∩C[s], Bj=Kj∩C[s]=Gj∩C[s] for j=1,...,p. See Brianc¸onand Maisonobe (2002)tocheck the correctness of the algorithm. To finish this section, we recall how the computation of step 1 of the algorithm presented above is carried out in the Oaku–Takayama method. It needs the Weyl algebra Ap+n= C[t1,...,tp,∂ t1,...,∂ tp,x1,...,xn,∂ 1,...,∂ n]: 1. Compute tj−fj,∂fj ∂xi∂tj+∂i,i=1,...,n,j=1,...,pC[t1∂t1,...,tp∂tp] ×x,∂ x, as explained in Procedure 4.1. of Oaku and Takayama (1999). This elimination uses 2n+4pvariables because it is made in Ap+n[u1,...,up,v 1,...,vp].Theideal considered is the one generated by tj−ujfj, ∂i+ p  l=1 ∂fl ∂xiul∂tl,i=1,...,n, 1−ujvj,j=1,...,p. To obtain the required intersection, eliminate the variables of type u,v. 2. Replace each tj∂tjby −sj−1, for j=1,...,p,inthegenerators obtained. 3. Examples andcomparisons We present in this section examples of annihilators of fsand b-functions that have proved intractable so far (here p=1). We also include a comparison of running times between OT and BM methods computing Bernstein–Sato ideals for two functions. We have used three different implementations to check how good the computations are in Rn,pcompared to the alternative homogenized Weyl algebra: •The software kan/sm1.Itistaken into account that the ring Cs,tis isomorphic to the ring of difference operators Cn,E−1 n,E−1 nn=(n−1)E−1 n by the correspondence t=E−1 n,s=n.E−1 nacts on a space of functions of nvia E−1 n•f(n)=f(n−1).Thesystem kan/sm1 (Takayama,1991)providessome tools for this family of rings. •The package Plural (Levandovskyy,2002), designed by Levandovskyy as a part of the celebrated Singular (Greuel et al.,2001). It provides an excellent setting for non-commutativecalculation of Gr¨obner bases. •Atailored implementation in CLISP designedbytheauthors to compare CPU times of many examples in a not very ambitious environment. The first evidence that we found of the BM method being better was the possibility for our humble system to compute examples intractable to the more powerful programs using the algorithms of Oaku and Takayama. 3.1. Some selected annihilators of f s All the examples in this section have been treated using our CLISP prototype. It is not optimized, so the timing data must be taken into account only in order to compare the different methods. The following table contains five interesting examples with some details of the computation of AnnAn[s](fs),for a polynomial f—namely: CPU time, number of elements (N.E.) in the reduced Gr¨obner basis (before the truncation of the elimination, of course),maximumnumberof monomials(N.M.)intheelementsof the basis and maximum total degree (T.D.) of the elements of the basis. Remark. In all these examples, the ordering used is the following one: to compare two exponents first look at the exponent of the variable t(in order to do theelimination). Second, look at the exponent of the variable s.Tobreak ties, finally use a reverse graded lexicographical ordering with x>∂ x>t>s. fCPU time N.E.N.M.T.D. OT (s) BM (s) OT BM OT BM OT BM x6+y4+z31.21 0.17 15 6 5 4 6 7 (x3+y2)(x2+y3)101.66 9.56 26 15 48 39 13 7 xyz(x+y)(x+z)13248.8 7565.22 76 26 118 150 12 10 x7+y7+x4y4131.22 19.1 27 15 63 43 16 10 x7+y7+z7+x2y2z25514.5 2995.75 46 63 165 139 14 13 The computations of the Bernstein–Sato polynomial for the last two examples have been treated in Brianc¸on et al. (1989)byadifferent method. Here we give generators of AnnAn[s](fs)for two examples from the table. The calculations are rather far from being trivial: the powerful system kan/sm1 cannot manage their calculation using the OT method. The annihilators, however, look harmless: •The non-generic arrangement of hyperplanes (taken from Walther,2002)(f= xyz(x+y)(x+z)=0)⊂C3: AnnA3[s](fs)=−5s+x∂x+y∂y+z∂z,x2∂x+2xz∂x+xy∂y+2yz∂y −4xz∂z−3z2∂z,−2xy∂x+2xz∂x+5xy∂y+3y2∂y +2yz∂y−5xz∂z−2yz∂z−3z2∂z,−4y2z∂x∂y −2xz2∂x∂y−3xy2∂2 y−3y3∂2 y−5xyz∂2 y−y2z∂2 y −2yz2∂2 y+2xz2∂x∂z+4yz2∂x∂z+5xyz∂y∂z+8y2z∂y∂z +5xz2∂y∂z−yz2∂y∂z3z3∂y∂z−2xz2∂2 z−4yz2∂2 z+4xz∂x −2xy∂y−5y2∂y−5xz∂y−6yz∂y−2z2∂y−3xz∂z +z2∂z,−x2y∂y−xy2∂y−2xyz∂y−2y2z∂y+x2z∂z +2xyz∂z+xz2∂z+2yz2∂z. •The semi-quasi-homogeneouscurve (f=x7+y7+x4y4=0)⊂C2: AnnA2[s](fs)=12xy3s−147 4y2s−9 7x2y3∂x−12 7xy4∂y−3 4x4∂y +21 4xy2∂x+21 4y3∂y,12y4s+21x3s−9 7xy4∂x−12 7y5∂y −3x4∂x−3x3y∂y−28 3x4s−49 3y3s+4 3x5∂x+x4y∂y +7 3xy3∂x+7 3y4∂y−28 3x3ys +343 12 x2s+4 3x4y∂x +x3y2∂y+7 12 y4∂x−49 12x3∂x−49 12x2y∂y,768 49 xys2−48s2 −192 49 x2y∂xs−192 49 xy2∂ys+96 7x∂xs+96 7y∂ys−48 7s +576 2401x3y∂2 x+1200 2401x2y2∂x∂y+576 2401xy3∂2 y+576 2401x2y∂x −48 49x2∂2 x+576 2401xy2∂y−96 49xy∂x∂y−48 49 y2∂2 y,4x4y3∂x −4x3y4∂y+7y6∂x−7x6∂y. 3.2. Their b-functions The timing information in this section is taken from a Pentium III, 1 GHz. As farasweknow, none of the available implementations of Oaku’s algorithm can manage the following two examples. However, their b-functions can be obtained in kan/sm1 using the PBW algebra Rn,pand the BM algorithm. Equation b-function Running time (s) xyz(x+y)(x+z)(5s+4)(5s+3)(3s+4)(5s+7)(5s+6)(3s+2)(s+1)313 x7+y7+x4y4(7s+10)(7s+9)(7s+8)(7s+4)(7s+6)(7s+2)(7s+5)504 (7s+3)(s+1)2 3.3. Towards a mathematical explanation: a paradigmatic example There is a whole family of examples that does not appear in the table of the last section: the curves1xa+yb+xyb−1,with b≥a+1≥5: the Reiffen family (Reiffen,1972). These examples defeated our prototype with the Oaku–Takayama method but were easily managed by the Brianc¸on–Maisonobe method. In the case a=4,b=5, for example, thesystem took 139.51 s of CPU time for a basis with ten elements; maximum number of monomials =107. 1Andsurfaces obtained from constructions over the curves. The annihilators corresponding to these curves have been widely studied with the use of Plural.Theresults are summarized in the next table for the case b=5,a=4: fCPU time N.E.N.M. T.D. OT BM OT BM OT BM OT BM x4+y5+xy494 min <1s 33 9 1240 71 15 10 The calculations in the first case have been done with respect to a typical elimination ordering: first give weight 1 to the variables u,v and to break ties use degree reverse lexicographical ordering. In the second case the ordering for BM was simply a lexicographical ordering with s,tgreater than the others. The explanation of the enormous difference between the two methods in this example is not as easy as considering the number of variables, 8 and 6 respectively. More precisely: •The bounds of Grigoriev (see Grigoriev,1991)forthecalculations in the Weyl algebra are applicable to Rn,pbut neither of the two calculations is a worst case (double exponential) in the sense of total degree, the usual measurement of the complexity for Gr¨obner bases. Of course for the general case (more than one function) the difference between 2n+2pand 2n+4pbecomes significant. •Nevertheless, the number of variables is important from the point of view of the number of monomials.Inthis non-commutative setting the ingredients of the Buchberger algorithm—S-polynomials and reductions—produce many more monomials than in the commutative case. As the number of possible monomials of total degree ≤din nvariables is n+d d thecomparison of the two methods relies on the ratio 2n+2p+d d2n+4p+d d. If you reach, say, total degree 15, you could have elements of about 15 +7 7 monomials in the algebra of Oaku and Takayama, but 15 +5 5 in R2,1.Andyou have to consider the total degrees not only in the final result but also in the intermediate calculations! This consideration influences the duration of the calculation as well as the total amount of memory used. •Another important factor is the growth of the coefficients of the monomials. This is avery well known problem in the commutative setting but is a more difficult matter in the Weyl algebra or in Rn,p,because of the binomial coefficients appearing in the Leibnitz rule that is repeatedly applied. Coefficients of more than 30 digits are obtained in the example that we are studying in the case of the Oaku–Takayama method. A lot of computation becomes much slower due to these coefficients. Remark. The ordering selected seems to be the best option for each case. It is a little surprising that the fastest option in the commutative case, elimination orderings like those used in the OT method, defeated the calculations for the BM method. Remark. The annihilator of (xa+yb+xyb−1)sdefeats kan/sm1 and Plural for b≥ a+1>12. It seems that this is a really hard example! 3.4. Bernstein–Sato ideals In this section we compare the OT method to the BM method for the computation of Bernstein–Sato ideals for p=2. We present two examples in kan/sm1. •Take {f1=x3+y2,f2=y3+x2},two transverse cuspids. The table of running times in the computation of BΣis Method Time for the step 1 (s) Time for the step 2 (s) Total (s) OT 2.4 0.022.42 BM 0.03 0.07 0.1 Steps 1 and 2 are the successive eliminations in each method as explained in 2.3. The Bernstein–Sato ideal BΣis as follows: BΣ=s2+1,s1+1∩g, where g=(4s1+6s2+5)(6s1+4s2+5)(6s1+4s2+7)(4s1+6s2+7). The calculation of the ideal Bin this case is rather hard. At the moment it seems to be intractable with any method. It was first proposed in Bahloul (2001). •Take {f1,f2}={x2+y2(1+y), y3+x2}. Method Time for the step 1 (s) Time for the step 2 (s) Total (s) OT 16.4 0.02 16.42 BM 1.78 0.06 1.84 In this case we have BΣ=s2+1,s1+1∩g, where g=(s1+s2+1)(2s1+2s2+3)(4s1+6s2+5)(4s1+6s2+7).