A Factorization Algorithm for G-Algebras and Applications Albert Heinle Viktor Levandovskyy DavidR.CheritonSchoolofComputerScience LehrstuhlDfürMathematik UniversityofWaterloo RWTHAachenUniversity 200UniversityAvenueWest Pontdriesch16 Waterloo,ONN2L3G1,Canada 52062Aachen,Germany [email protected] [email protected] 6 1 0 2 ABSTRACT cijxixj +dij: 1 ≤ i < j ≤ n}i is called a G-algebra, if n It has been recently discovered by Bell, Heinle and Levan- {xα11 ·...·xαnn :αi ∈N0} is a K-basis of A. a dovskyythatalargeclass ofalgebras, includingtheubiqui- G-algebras[1,19]arealsoknownasalgebrasofsolvabletype J tous G-algebras, are finite factorization domains (FFD for [18,20]andasPBWalgebras[4,5]. G-algebrasareNoethe- 1 short). rian domains of finite global, Krull and Gel’fand-Kirillov 3 Utilizing this result, we contribute an algorithm to find dimensions. all distinctfactorizations ofagivenelement f ∈G,whereG Weassumethatthereaderisfamiliarwiththebasictermi- ] isanyG-algebra,withminorassumptionsontheunderlying A nology in the area of Gr¨obner bases, both in the commuta- field. tiveaswellasinthenon-commutativecase. Werecommend R Moreover, the property of being an FFD, in combination [3, 5, 19] as literature on thistopic. with the factorization algorithm, enables us to propose an . Recall, that r ∈ R\{0} is called irreducible, if in any h analogous description of the factorized Gr¨obner basis algo- at rithm for G-algebras. This algorithm is useful for various fOatchtoerriwzaisteio,nwerc=allarbreeidtuhceirblae.∈ U(R) or b ∈ U(R) holds. m applications, e.g. in analysis of solution spaces of systems oflinearpartialfunctionalequationswithpolynomialcoeffi- [ Definition 2 (cf. [2]). LetAbea(notnecessarilycom- cients,comingfromG. Additionally,itispossibletoinclude mutative) domain. We say that A is a finite factorization 1 inequality constraints for ideals in theinput. domain (FFD, for short), if every nonzero, non-unit ele- v ment of A has at least one factorization into irreducible el- 6 Keywords ements and there are at most finitely many distinct factor- 9 izations into irreducible elements up to multiplicationof the 2 G-Algebras, Gr¨obner Bases, Factorization irreducible factors by central units in A. 0 0 1. INTRODUCTION 2. MOTIVATIONANDAPPLICATIONS . 2 Notations: ThroughoutthepaperwedenotebyKafield. 0 InthealgorithmicpartwewillassumeKtobeacomputable Problem 1. Let A be a finite factorization domain and 6 1 field. N0 =N∪{0} is the set of natural numbers including a K-algebra. Given f ∈ A\(U(A)∪{0}), compute all its : zero. For a K-algebra R we denote by U(R) the group of factorizations of the form f = c·f1···fn, where c ∈ U(A) v invertible (unit) elements of R, which is nonabelian in gen- and fi ∈A\U(A) are irreducible. i eral. Forf ∈RwedenotebyRf theleftideal,generatedby X f. Themainfocusinthispaperliesinsocalled G-algebras, This paper is devoted in part to the algorithmic solution r which are definedas follows. of Problem 1 for a broad class of G-algebras. With this al- a gorithmonecanapproachanumberofimportantproblems, Definition 1. For n ∈ N and 1 ≤ i < j ≤ n consider which we discussin details. theunitscij ∈K∗ andpolynomialsdij ∈K[x1,...,xn]. Sup- Let A bea K-algebra and 06=L⊂A a finitely generated pose, that there exists a monomial total well-ordering ≺ on left ideal. K[x1,...,xn],suchthatforany1≤i<j ≤neitherdij =0 or the leading monomialof dij issmaller than xixj with re- Problem 2. Compute a proper left ideal N )L. spect to ≺. The K-algebra A := Khx1,...,xn | {xjxi = Unfortunately,itisnotknowningeneral,whethertheprob- lem of left maximality of a given ideal with respect to in- clusionisdecidable. Thereforeweareinterestedinthelocal negative form of it. Namely, if Problem 2 can be solved, Permission tomake digital orhardcopies ofall orpartofthis workfor personalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesare then L is not left maximal. Moreover, for any N as above, notmadeordistributedforprofitorcommercialadvantageandthatcopies we have a surjection from A/L to its proper factor-module bearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,to A/N, in otherwords theexact sequenceof left A-modules republish,topostonserversortoredistributetolists,requirespriorspecific permissionand/orafee. 0→N/L→A/L→A/N →0 ISSAC’16Waterloo,Ontario,Canada Copyright20XXACMX-XXXXX-XX-X/XX/XX...$15.00. whichcontributestotheknowledgeofthestructureofA/L. Supposethatf ∈A\{0},f ∈/ Lhasfinitelymanyfactor- ForageneralS,itisunknown,whetherLS iscomputable. izationsf =gihiuptomultiplicationbycentralunits,where If A is the nth Weyl algebra, S = K[x1,...,xn]\{0} and i∈I,|I|<∞ and gi,hi ∈/ U(A). We donot requirethat gi L⊂Ahasfiniteholonomicrank,thenthereisanalgorithm orhi areirreducible. Suppose,thatL(L+Af (A. Then [24,23]tocomputeLS (knownastheWeyl closure of L). L+Af ⊆ i∈I(L+Ahi),hencethereisanaturalsurjective Thefactorizationcanbeusedintheprocessofcomputing homomorphism of left A-modules LS asfollows. LetAbeanFFD.Givenℓ∈L,onecomputes T A A finitely many factorizations ℓ = aibi,i ∈ I for some finite → →0 indexing set I. Then let J := {j ∈I |(aj,bj)∈S×L}. If L+Af i∈I(L+Ahi) J 6=∅, one has L+{Abj :j ∈J}⊆LS. In such a way one obtains an approximation to LS. Note, that LS =A if and Relations with solutTion spaces: Let F be an arbi- only if L∩S 6=∅. trary (in particular, not necessarily finitely generated) left A-module,whichonecanthinkaboutasofthespaceofsolu- 3. HOWTO FACTORIN G-ALGEBRAS tionsforA-modules. Then,forfixedKandanA-moduleM onedenotesSol(M,F):=HomA(M,F),whichisaK-vector 3.1 General Algorithm space and an EndA(M)-module[22]. ByinvokingtheNoether-Malgrangeisomorphism[22],we In a recent publication [2, Theorem 1.3], it was proven obtain for an thenaturalinjective map of K-vectorspaces that each G-algebra G is a finitefactorization domain. Inthesamepaper,anoutlinewasgivenhowonecouldfind A A 0→Sol ,F →Sol ,F . allpossiblefactorizationsofanelementinG. Inthissection, (cid:18) i∈I(L+Ahi) (cid:19) (cid:18)L+Af (cid:19) we will provide a thorough description of an algorithm to find all possible factorizations of an element in a G-algebra The latter sheTds light on thestructure of thespace of solu- G, up tomultiplication by central units. tions of A/(L+Af). For this, we need to make a further assumption on our Note, that the following version of the left Chinese re- field K, which holdsfor most practical choices of K. mainder theorem for modules holds: Theorem 1. Let A be a K-algebra, I a finite set of in- Assumption: There exists an algorithm to determine if a polynomial p in K[x] has roots in K. If p has roots in K, dices and {Li : i ∈ I} are left ideals in A. Consider the then thisalgorithm can produceall K-roots of p. homomorphism A/ Li −φ→ A/Li, a+ Li 7→(a+L1,...,a+L|I|). Recall,that{xα=xα11·...·xαnn :α∈Nn0}isaK-basisof G. With respect to an admissible monomial ordering ≺ on i\∈I Mi∈I i\∈I G wecan uniquelywrite every g∈G\{0} as g=cαxα+tg Then the following holds with cα ∈ K\{0}. Moreover, either tg = 0 or xβ ≺ xα 1) φ is injective for any summand cβxβ, cβ 6= 0 of tg. Then lm(g) = xα is the leading monomial of g and lc(g) = cα is the leading coefficient of g. A polynomialg6=0 with lc(g)=1is called 2) if ∀i,j ∈I,i6=j holds Li+Lj =A, then φ is surjec- monic. tive. It is important to recall [19], that lm(xα ·xβ) = xα+β Ofcourse,onecanassumethatLiarepropernonzeroideals. holds ∀α,β∈Nn0 in a G-algebra. In the second item of the Theorem 1 one says that the Proof of Algorithm 1. Let us begin with discussing collection {Li : i ∈ I} is left comaximal. Then φ is an the termination. The set M in line 2 is finite, as it is a isomorphism andone hasa finitedirect sum decomposition permutationofafiniteproductofthevariablesinG. SinceG of the module A/ i∈ILi. Hence, there is a direct sum isaG-algebra,thesetoftotalwell-orderingsonit,satisfying decomposition of thesolution spaces the Definition 1, is nonempty. By [4], in this set there is a T weighteddegreetotalordering,say≺w withstrictlypositive weights. Withoutlossofgenerality letusassumethisisthe Sol A/ Li,F =Sol A/Li,F = Sol(A/Li,F). orderingweareworkingwith. Thusforanymonomialthere ! ! i\∈I Mi∈I Mi∈I are only finitely many monomials which are smaller with Note, that the right hand side can be a direct sum even if respect to ≺w. In particular, this applies to lt(a) and lt(b) thecondition (2) is not satisfied, see Example 3. in line 5. The variety V will be a finite set due to the fact Anotherapplication: LetAbeadomainandS ⊂Abe thatGisanFFD.Thus,thesetRinline9willalsobefinite. multiplicativelyclosedOreset. ByOre’sTheoremthelocal- The recursive call will also terminate, since in each step we izationS−1Aexistsandthereisaninjectivehomomorphism either discover that we cannot refine our factorization any A→S−1A [5]. more, or we split a given factor into two factors of strictly AleftidealL⊂AiscalledleftS-closedifLS =L,where smaller degrees. LS := {a ∈ A | ∃s ∈ S sa ∈ L} ⊇ L is the S-closure of For the correctness discussion of our algorithm, we need L. There is another characterization of S-closedness: LS = to show that we can calculate the variety V in line 8. We ker(A→S−1(A/L)),wherethelatterhomomorphismofA- know, since G is an FFD, that the ideal generated by F is modules is a 7→1−1a+S−1L. Then LS/L is the S-torsion either zero-dimensional over K[x] or it is an intersection of submoduleof A/Land A/LS has noS-torsion. suchwithahigher-dimensionalidealH,whereasthevariety of H does not contain points from an affine space over K. Problem 3. Given S ⊂ A an Ore set and L ⊂ A, give Hencewe proceed with thezero-dimensional component F 0 an algorithm to compute LS. of F. Algorithm 1 Factoring an element g in a G-algebra G torizations, namely Input: g∈G\K. p=(e2f +2ef−2eh−e2−4e+f −2h−3)·(e+f) Output: {(g1,...,gm)|m∈N,gi∈G\K for i∈ {1,...,m},g1···gm =g}(up tomultiplication of each and factor bya central unit). p=(e2f +ef2−2eh−e2+f2−3e−f −2h)·(e+1). Assumption: Anadmissible monomial ordering ≺ on G is fixed and g is monic with respect to it. Alltheothercombinationseitherproducethesamefactor- izations or none. 1: R:={} When recursively calling the algorithm for each factor in 2: the found factorizations, we discover that the first two fac- torizations have a reducible factor. In the end, one obtains M :={(p1,...,pν)|ν ∈N,pi∈{x1,...,xn}, the followingtwo distinct factorizations of p into irreducible lm(p1·...·pν)=lm(g)} factors: p=(e2f +ef2−2eh−e2+f2−3e−f −2h)·(e+1) 3: for (p1,...,pν)∈M do =(e+1)·(ef−e+f−2h−3)·(e+f). 4: for i:=1 to ν−1 do 5: Set up an ansatz for the K-coefficients of a·b = g 3.2 Implementation with lt(a)=p1·...·pi and lt(b)=pi+1·...·pν. 6: F := the reduced Gr¨obner basis w.r.t. an elimina- WehavedevelopedanexperimentalimplementationofAl- tion ordering of the ideal generated by the coeffi- gorithm 1 in the computer algebra system Singular [10]. cients of a·b−g. We will make it available as part of ncfactor.lib. Our 7: if F 6={1} then newlyimplementedproceduresfactorizeelementsinanyG- 8: V := Variety of hFi in an affinespace over K. algebra,whosegroundfieldisF(q1,...,qn),whereFiseither 9: R := R∪{(a,b) | a,b ∈ G,a·b = g, where the Q or a finiteprimefield and qi are transcendentaloverF. coefficients of a,b are given by v∈V} Wedesignedthesoftwareinamodularway,sothatduring 10: endif runtimeour function checksif a more efficient factorization 11: end for algorithmisavailableforthespecificgivenG-algebraand/or 12: endfor inputpolynomial. Ifthisisthecase,theinputisre-directed 13: if R={} then to this function. In this way, the user can call the general 14: return {(g)} function to factor elements in any one of the supported G- 15: else algebras,andrunstheavailableoptimizedalgorithms,where 16: Recursively factor a and b for each (a,b)∈R. available, without calling them individually. 17: endif 3.3 PossibleImprovements 18: return R Algorithm1solvestheproblemoffindingallpossiblefac- torizations of an element in a G-algebra, but it will not be veryefficientingeneral. Thisisnotonlyduetothecomplex- Ourassumption abovestatesthatwecanfindallK-roots ity of thenecessary calculation of a Gr¨obner basis [21], but ofaunivariatepolynomial. SinceF iszero-dimensional,for 0 alsothesizeofthesetM isabottleneck. In[12,13],analgo- anyvariablexithereisthecorrespondingunivariatepolyno- rithmforfactoring elementsinthenthWeylalgebraispre- mial,generatingtheprincipalidealF0∩K[xi]. Bybackwards sented,whichissimilartoAlgorithm1. Themaindifference substitution,weobtaintheentireK-varietyoftheidealgen- isthattheZn-gradedstructureisutilized. There,thehomo- erated byF . 0 geneous polynomials of degree zero form a K-algebra A(n0), which is isomorphic to a commutative multivariate polyno- Example 1. Let us consider the universal enveloping al- mial ring. The set of homogeneous polynomials of degree gebra U(sl ) of sl [11], represented by 2 2 z ∈ Zn\{0n} has the structure of a cyclic A(n0)-bimodule. Khe,f,h|fe=ef−h,he=eh+2e,hf =fh−2fi. Hence, factorization of homogeneous polynomials with re- spect to the Zn-grading reduces to factoring commutative In U(sl ), we want to factorize the element 2 polynomials with minoradditional combinatorial steps. An p:=e3f +e2f2−e3+e2f+2ef2−3e2h−2efh−8e2 inhomogeneous polynomial f has now the highest graded part α(f) and the lowest graded part ω(f), both of them +ef+f2−4eh−2fh−7e+f−h. ratherpolynomials thanmonomials. Henceα(f),ω(f)have potentially smaller numbers of different factorizations than We fix the lexicographic ordering on U(sl ), i.e. the leading 2 term of p is e3f. thepermutationsoftheleadingtermcollectedinM inAlgo- rithm 1. Indeed, it suffices to consider firstly factorizations Therefore the set M in line 2 is given as into twopolynomials and for each candidatepair an ansatz M :={(e,e,e,f),(e,e,f,e),(e,f,e,e),(f,e,e,e)}. is made for the graded terms between the highest and the lowestgradedparts. Thismeans,thatthesetM hassmaller When choosing (e,e,e,f), for i = 1 one obtains the fac- sizeingeneralwhenusingthistechnique. Additionally,this torization approach takes the lowest graded part into account, which p=(e+1)·(e2f+ef2−3eh−2fh−e2+f2−7e+f−h). allows to eliminate certain invalid cases beforehand. The performance increase is reflected by the benchmarks pre- By picking (e,e,f,e), for i=3 one obtains two more fac- sented in [12, 17]. Hence, for practical implementations of Algorithm 1, one any of ϕ or ψ would have a non-trivial A factor, we would 0 shouldexamineeachpossibleG-algebraseparatelyandtake obtain again that p is reducible in A . This leaves as only 0 advantage of potential extra structure, like the presence of options p = ef or p = fe = ef −h, as claimed. Thus, nontrivialZn-gradingoranisomorphismtoanalgebrawith we have shown that irreducible elements in A , which are 0 this structure. reducible in A, can be easily identified and factored. We will conclude this section by summarizing the condi- Now consider the same polynomial p as in Example 1. tions that can lead to an improved version of Algorithm 1. With respect to the (1,−1,0)-grading it decomposes into the Let A bea K-algebra, which possesses anontrivial(i.e. not followinggradedparts: α(p)=−e3,ω(p)=f2 (aswesee,in all weight vectors are zero) Zn-(multi)grading. Then one thiscasewehavemonomialsingradedparts,whileingeneral can infer thefollowing additional information: rather polynomials appear) and the intermediate parts are 1. For z ∈Zn, Az :={a∈A:deg(a)=z}∪{0} is a K- e3f −3e2h−8e2+e2f−4eh−7e+ vector space. Moreover, ⊕zAz =A and AiAj ⊆Ai+j deg:2 deg:1 for all i,j ∈Zn. | {z } | {z } +e2f2−2efh+ef−h+2ef2−2fh+f. 2. A0n, the graded part of degree zero, is a K-algebra itself (since A0A0⊆A0). deg:0 deg:−1 3. Forz∈Zn\{0n}, thez-thgraded part Az is anA0n- Among the|factorizat{izons of α(p})=|−e3 a{nzd ω(p)}=f2 into bimodule (sinceA0Az,AzA0 ⊆Az). two factors, consider the case (−e2)·e and f ·f. Thus, we’re looking for a,b ∈ A with α(a) = e2,ω(a) = f and In orderto beuseful for factorizing purpose,thisgrading α(b)=e,ω(b)=f and p=ab holds. In b we have only one should havethe following properties: possible intermediate graded part b (ef,h), namelyof degree 0 0 since degα(b) = 1 and degω(b) = −1. In a we have to 4. The graded part of degree zero, A0n, which is a K- specifythepartsofdegrees1resp. 0,thatisa (ef,h)·eresp. algebra, is additionally an FFD with ”easy” factor- 1 a (ef,h). After the multiplication, we obtain the following ization, preferably the commutative polynomial ring. 0 graded decomposition of intermediate graded terms of ab: Furthermore, for keeping the set M in Algorithm 1 small, it would bedesirable ifin A0n a randomlycho- −e2b0+a1e2+a1eb0+a0e−e2f+ sen polynomial is irreducible with high probability. deg:2 deg:1 5. The irreducible elements in A0n, that are reducible | {z } | {z } +a ef +a b +ef−h+fb +a f. in A, can be identified and factorized in an efficient 1 0 0 0 0 manner. Preferably, one has a finitenumber of monic deg:0 deg:−1 elements of such type. Byfixingthem|aximalp{ozssibledegr}ee o|fa0{,za1,}b0 ∈K[ef,h], 6. Forz∈Zn\{0n},thez-thgradedpartAz isafinitely we can create and solve a system of equations which the co- generatedA0n-bimodule,preferablyacyclicbimodule. efficients of a0,a1,b0 have to satisfy. In this example an ansatzintermsof1,h,ef,i.e. 9unknowncoefficients, leads Then the Algorithm 1 can be modified along the lines of to the system of18 at most quadratic equations, whichleads algorithmsfrom[12,13],whichwehavealsosketchedabove. totheuniquesolution: b (ef,h)=0,a (ef,h)=2ef−2h−3 0 0 Let usillustrate thisapproach by a concrete example. anda (ef,h)=ef−h−2. Substituting the polynomials,we 1 arrive at the followingfactorization with polynomials sorted Example 2. As in Example 1, let A=U(sl2), that is according to the grading: A=Khe,f,h|fe=ef−h,he=eh+2e,hf =fh−2fi. p=(−e2+e2f −2eh−4e+2ef−2h−3+f)·(e+f) Af first, let us determine which gradings are possible. Let ThisisalreadyknowntousfromtheExample1. Inananal- we,wf and wh be the weights of the variables, not all zero. ogous way one can address other factorizations. Note, that The two last relations of A imply that wh = 0, and the in the ansatz we made, significantly less variables for un- first one implies we +wf = wh = 0, that is wf = −we. known coefficients and a system of less equations of smaller Hence a Z-grading (we,wf,wh) = (1,−1,0) is enough for total degree were used, compared to the general Algorithm. our purposes, since A = K[ef,h] is commutative and the 0 z-th graded part is a cyclic A0-bimodule, generated by ez if 4. THEFACTORIZEDGRÖBNERBASISAL- z >0 and by f|z| otherwise. This property guarantees, that GORITHMFORG-ALGEBRAS ∀r∈K[ef,h] and ∀z ∈N there exists q ,q ∈K[ef,h], such 1 2 that rez = ezq and ezr = q ez and the same holds for the In what follows, by the term ideal we always mean a left 1 2 multiplication by fz. Note, that deg(qi)=deg(r). ideal (unless otherwise specified). We claim that the only monic irreducible elements in A0, The factorized Gr¨obner approach has been studied ex- which are reducible in A, are given by ef and ef −h. The tensively for the commutative case [8, 7, 9, 14, 15], and proof to this claim is similar to the one for [13, Lemma implementations are e.g. provided in the computer algebra 2.4], which we outline here: Let p be an irreducible element systems Singular[10] and Reduce[16]. in A0, which reduces into p = ϕ·ψ in A, where ϕ,ψ ∈ The leading motivation is to split a Gr¨obner basis com- A\K are monic. Since A is a domain, the factors ϕ,ψ are putation into smaller pieces with respect to the degrees of homogeneous with deg(ϕ) = k and deg(ψ) = −k for some their generators. The union of the varieties of the ideals k∈Z. If|k|>1ork=0, pwouldbereducibleinA ,which generated by these smaller pieces equals the variety of the 0 violates our assumption. Hence only k = 1 is possible. If initial system. In thecommutativecase, thereis also a way to constrain Algorithm 2 Factorized Gr¨obner bases Algorithm for G- thesolutionspace. Onecanprovideanextrasetofelements, Algebras (FGBG) that should not be reducible by the computed Gr¨obner ba- Input: B:={f ,...,f }⊂G, C :={g ,...,g}⊂G. 1 k 1 l sises. In this way, one excludes certain unwanted solutions, Output: R:={(B˜,C˜)| which is useful in practice. (B˜,C˜) is factorized constrained Gr¨obnertuple} with Thesearchforvarietiesinthecommutativecasetranslates hBi⊆ hB˜i tothesearchforsolutionsinthenon-commutativecase: All (B˜,C˜)∈R Assumption: Allelements in B and C are monic. G-algebras are finite factorization domains and a general T factorization algorithm via Algorithm 1 is given. Many of 1: for i=1 to k do them are abstractions of algebras of operators, and one is 2: if fi is reduciblethen interestedtofindcommonsolutionsofcertainsetsofopera- 3: M := {(f(1),f(2) | f(1),f(2) ∈ G \ K,lc(f(1)) = tors,writtenaspolynomials. Righthandfactorsofelements i i i i i correspond to partial solutions, and hencea split similar to lc(fi(2))=1,fi(1)·fi(2) =fi,fi(1) is irreducible} thecommutativecaseishelpfultorecoverpartialsolutions. 4: if thereexists (a,b),(a˜,˜b)∈M with a˜6=a then Motivatedbythisobservation,weattempttogeneralizethe 5: return factorized Gr¨obnerbasisalgorithm totheG-algebracase in thissection. Ouralgorithmincludesthepossibilitytointro- duceconstraints,similartothemethodsinthecommutative FGBG(B\{fi})∪{b},C∪ {˜b} casUen.fortunately, not all nice properties transfer into the (a,[b)∈M  (a˜,b[˜b6=)∈˜bM    non-commutativecase, as thefollowing example depicts. 6: endif 7: end if Example 3. In the commutative case, one has the prop- 8: endfor erty that the radical of the input ideal will be equal to the 9: P :={(fi,fj)|i,j ∈{1,...,k},i<j} intersection of the radicals of allideals computed by the fac- 10: while P 6=∅ do torized Gr¨obner basis algorithm. 11: Pick (f,g)∈P We will show via a counter-example that we do not have 12: P :=P \{(f,g)} the same property for G-algebras. 13: s:= S-polynomialof f and g Consider 14: h:=NF(s,B) p=(x6+2x4−3x2)∂2−(4x5−4x4−12x2−12x)∂ 15: if h6=0 then 16: if h is reducible then +(6x4−12x3−6x2−24x−12)∈A . 1 17: return FGBG(B∪{h},C) This polynomial appears in [24] and has two different fac- 18: endif torizations, namely 19: P :=P ∪{(h,f)|f ∈B} 20: B:=B∪{h} p=(x4∂−x3∂−3x3+3x2∂+6x2−3x∂−3x+12)· 21: endif (x2∂+x∂−3x−1) 22: if thereexistsi∈{1,...,l}withNF(gi,B)=0then 23: return ∅ =(x4∂+x3∂−4x3+3x2∂−3x2+3x∂−6x−3)· 24: endif (x2∂−x∂−2x+4) 25: end while 26: return {(B,C)} Areduced Gr¨obnerbasisofhx2∂+x∂−3x−1i∩hx2∂−x∂− 2x+4i, computed in Singular [10], is given by {3x5∂2+2x4∂3−x4∂2−12x4∂+x3∂2−2x2∂3+16x3∂ Gr¨obner basis of hBi, and NF(g,B) 6= 0 for every g ∈ C. We call a constrained Gr¨obner tuple factorized, if every +9x2∂2+18x3+4x2∂+4x∂2−42x2−4x∂−12x−12, f ∈ B is either irreducible or has a unique irreducible left 2x4∂4−2x4∂3+11x4∂2+12x3∂3−2x2∂4−2x3∂2 divisor. +10x2∂3−44x3∂−17x2∂2+64x2∂+12x∂2+66x2 Itispossibletostrengthentheassumptionsonafactorized constrainedGr¨obnertuplesbyonlyallowingcompletelyirre- +52x∂+4∂2−168x−16∂−60}. ducibleelementsinB,whichmightbepreferabledepending on the concrete problem. However, in our application, we Hence, one main difference will be that we do not claim allow elements with only one factorization. In this way, we that the union of all solutions of our smaller pieces in the increase the number of solutions we can find for a certain factorizing Gr¨obner basis algorithm will always be equal to system B ⊂ G by using our generalized factorized Gr¨ob- all common solutions of the initial set of polynomials. In ner basis algorithm. This methodology also appears in the general, we will only find a subset of all solutions using our contextofsemifirs,wheretheconceptofsocalledblockfac- method. However,inthisexample,thespaceofholomorphic torizations or cleavages has been introduced to study the solutions of the differential equation associated to p in fact reducibility of a principal ideal [6, Chapter3.5]. coincides with the union of the solution spaces of the two generators of theintersection stated above. Proof of Algorithm 2. Wewillfirstdiscussthetermi- nation aspect of Algorithm 2. SinceM as calculated in line Definition 3. Let B,C be finite subsets in G. We call 3isoffinitecardinality,theexistencecheckinline4can be the tuple (B,C) a constrained Gr¨obner tuple, if B is a done in a finite number of steps. Line 5 consists of a finite number of recursive calls to FGBG. The algorithm reaches respectively thislineifthereisanelementf inB,whichisreducibleand f :=x∂3+x2∂−x∂2+∂3−x2+x∂−2∂2−x+1 has a non-unique irreducible left divisor. In each recursive 2 call, the algorithm is called with an altered version of the =(x∂2+x2+∂2+x−∂−1)·(∂−1) set B, where f is being replaced in B by b ∈ G, where b =(x∂−x+∂−2)·(∂2+x). is chosen such that there exists an irreducible a in G with f = ab. Therefore, after a finite depth of recursion, FGBG Hence, in line 5, FGBG will return two recursive calls of will be called with a set B containing elements that are ei- itself, namely ther irreducible or have an unique irreducible left divisor. • FGBG({∂−1,f },{∂−1,∂3+x∂−∂2−x+1}) We can make this assumption on B when FGBG reaches 2 line 9. Lines 10–25 describe the Buchberger algorithm to • FGBG({∂3+x∂−∂2−x+1,f },C) 2 computea Gr¨obner basis, with two differences: For simplicity, we will ignore the first call, as C contains 1. IfthenormalformhofanS-polynomialwithrespectto ∂−1, which also appears in the generator list. Bisnot0,wecheckhforreducibility. Ifhisreducible, Furthermore, the new element b1 :=∂3+x∂−∂2−x+1 we call FGBG recursively,adding hto B. only has one possible factorization. Therefore, we consider now the factorizations of f . This leads again in line 5 to 2 two recursive calls: 2. Wecheckthesystemforconsistency,i.e. ifthereisan elementinC thatreduceswithrespecttoB,wereturn • FGBG({b ,∂−1},{∂−1,∂2+x}) 1 theempty set. • FGBG({b ,∂2+x},C) 1 Each recursive call will terminate, since we add an element As before, we can ignore the first recursive call. Thus, we to B that will reduce an S-polynomial to zero, which could are left with ({b ,∂2+x},C) to proceed on line 9. not bereduced tozero before. 1 The normal form of the S-polynomial of b and ∂2+x is Forthecorrectnessdiscussion,oneobservesthatlines1–8 1 equal to zero. Further, the normal form of b with respect servethepurposetosplit thecomputation based on there- 1 to h∂2+xi, is equal to zero, i.e. ∂2+x is a right divisor of ducibility of theelementsin theinitial set B. If an element f ∈ B factorizes in more than one way, we recursively call b1. Hence, we can omit b1 and our complete Gr¨obner basis is given by {∂2 +x}. Since NF(∂ −1,h∂2 +xi) 6= 0, our FGBG with (B \{f})∪{b} as the generator set for each algorithm returns {({∂2+x},C)} as final output. maximal right hand factor b of f. Hence,theleft ideal gen- Note,thatifwewouldhavechosenC =∅inthebeginning, eratedby(B\{f})∪{b}willcontainhBi,andthushBiwill the output of our algorithm would have been be contained in theintersection of all of them, as required. Asalready mentionedin thetermination discussion,lines {({∂−1},{b }),({∂2+x},{∂−1})}, 1 10–25 describe the Buchberger algorithm. After computing i.e. we recover hBi=h∂2+xi∩h∂−1i in this case. an S-polynomial h, we check for its reducibility. If there is more than one maximal right factor r of h, we call FGBG Remark 1. Onecanalsoinsertanearlyterminationcri- recursively and add h to our set B. Here, we have again a terion inside Algorithm 2, namely after at least one factor- guarantee that the left ideal generated by B is a subset of ized constrained Gr¨obner tuple has been found. This is in theleft ideal generated byB∪{h}. the commutative case motivated by the fact that in practice Theadditionalconstraints thatweimpose on eachrecur- users are often not interested in all the elements in a vari- sivecallenableustominimizeourcomputations,butdonot ety but would be content with at least one. For example, the violatethesubsetproperty. Intheend,itisensuredthatin computer algebra system Reduce can be instructed to stop allcomputedconstrainedGr¨obnertuples(B˜,C˜),noelement after finding one factorized Gr¨obner basis (see [16]). In the in C lies in the left ideal generated byB˜. non-commutativecase,wecanonlyhopeforpartialsolutions in general, but a mechanism to stop a computation once at Example 4. Let us execute FGBG on an example. Let least one is found is also desirable. B:={∂4+x∂2−2∂3−2x∂+∂2+x+2∂−2, 5. CONCLUSIONS x∂3+x2∂−x∂2+∂3−x2+x∂−2∂2−x+1} Analgorithm for factoring elements in G-algebras, where the underlyingfield K has the property that we are able to be a subset of the first Weyl algebra A1. We assume that extract all possible K-roots of any polynomial in K[x], has C := {∂ −1}, and that our ordering is the degree reverse been shown (Algorithm 1). lexicographic one with ∂ > x. This example is taken from This algorithm and the FFD-property of G-algebras en- the Singularmanual[10](anditisaGr¨obnerbasisforthe ableustoproposeageneralizationofthefactorizedGr¨obner leftidealh∂2+xi∩h∂−1i;hencewewouldexpect theoutput basis algorithm for G-algebras (Algorithm 2). with our chosen C to be h∂2 +xi). Each element factors A future work would be to identify improvements to Al- separately as gorithm 1 for practically interesting G-algebras. This has been studied e.g. for partial q-differential, differential and f1 :=∂4+x∂2−2∂3−2x∂+∂2+x+2∂−2 difference operators in [12, 13], where the Zn graded struc- =(∂3+x∂−∂2−x+2)·(∂−1) ture resp. a certain embedding has been utilized. In the meantime, we haveimplementedtheunimprovedversion in =(∂−1)·(∂3+x∂−∂2−x+1) the Singular library ncfactor.lib, which will be made available shortly. Ourimplementation identifiesbeforehand Symbolic and Algebraic Computation, pages 194–201. ifanimprovedmethodisalreadyincludedinncfactor.lib ACM, 2014. for a specific algebra and, if this is the case, re-directs the [13] M. Giesbrecht, A.Heinle, and V.Levandovskyy. input there. This modular design allows us to update the Factoring linear partial differential operators in n function once an improved algorithm is available for a cer- variables. Journal of Symbolic Computation, pages –, tainG-algebra. Theuseofthefunctionstaysthesameafter 2015. such an update. [14] H.-G.Gr¨abe. On factorized gr¨obner bases. In Another interesting future direction would be to charac- Computer algebra in science and engineering, pages terize further the connection between the solution space of 77–89. World Scientific. Citeseer, 1995. a polynomial system B ⊂ G and the union of the solution [15] H.-G.Gr¨abe. Triangular systems and factorized spaces of the output of Algorithm 2 when called with B. Gr¨obner bases. Springer, 1995. Especially, it would be interesting to identify properties of [16] A.Hearn. Reduceuser’s manual, version 3.8 (2004). G and B, underwhich both spaces coincide. [17] A.Heinle and V.Levandovskyy.Factorization of AnimplementationofAlgorithm2wouldalsobeofprac- Z-homogeneouspolynomials in thefirst (q)-weyl tical interest, which the authors intend to provide in the algebra. arXiv preprint arXiv:1302.5674, 2013. near future. [18] A.Kandri-Rodyand V.Weispfenning. Non-commutativegr¨obnerbasesinalgebras ofsolvable 6. ACKNOWLEDGMENTS type.9(1):1–26, 1990. We thank Eugene Zima, Jason P. Bell and Mark Gies- [19] V.Levandovskyy.Non-commutativecomputeralgebra brecht for insightful discussions we had with them. We are for polynomial algebras: Gr¨obnerbases, applications grateful to Wolfram Koepf for the information on internals and implementation. Doctoral Thesis, Universit¨at of Reduce. Kaiserslautern, 2005. [20] H.Li. Noncommutative Gr¨obner bases and 7. REFERENCES filtered-graded transfer. Springer,2002. [21] E. W. Mayrand A. R.Meyer. The complexity of the [1] J. Apel. Gr¨obnerbasen in nichtkommutativen word problemsfor commutativesemigroups and Algebren undihre Anwendung.Dissertation, polynomial ideals. Advances in mathematics, Universit¨at Leipzig,1988. 46(3):305–329, 1982. [2] J. P. Bell, A.Heinle, and V. Levandovskyy.On [22] W.M. Seiler. Involution. The formal theory of noncommutativefinitefactorization domains. To differential equations and its applications in computer Appear in the Transactions of the American algebra. Algorithms and Computation in Mathematics Mathematical Society; arXiv preprint arXiv:1410.6178, 24. Berlin:Springer, 2010. 2014. [23] H.Tsai. Algorithms for algebraic analysis. PhD thesis, [3] B. Buchberger. Introductionto Gr¨obnerBases. In Universityof California at Berkeley, 2000. Gr¨obner Bases and Applications, pages 3–31. Berlin: [24] H.Tsai. Weylclosure of a linear differential operator. Springer,1997. Journal of Symbolic Computation, 29:747–775, 2000. [4] J. Bueso, J. G´omez-Torrecillas, and F. Lobillo. Re-filteringand exactnessof theGelfand-Kirillov dimension. Bull. Sci. Math.,125(8):689–715, 2001. [5] J. Bueso, J. G´omez-Torrecillas, and A. Verschoren. Algorithmic methods in non-commutative algebra. Applications to quantum groups. Dordrecht: Kluwer AcademicPublishers, 2003. [6] P.M.Cohn.Free ideal rings and localization ingeneral rings, volume3. Cambridge UniversityPress, 2006. [7] S.R. Czapor. Solving algebraic equations: combining buchberger’salgorithm withmultivariatefactorization. Journal of Symbolic Computation, 7(1):49–53, 1989. [8] S.R. Czapor. Solving algebraic equationsvia buchberger’salgorithm. In Eurocal’87, pages 260–269. Springer,1989. [9] J. H. Davenport.Looking at a set of equations. Thechnical report, pages 87–06, 1987. [10] W. Decker,G.-M. Greuel, G. Pfister, and H.Sch¨onemann.Singular4-0-2 — A computer algebra system for polynomial computations. http://www.singular.uni-kl.de,2015. [11] J. Dixmier. Enveloping algebras, volume14. Newnes, 1977. [12] M. Giesbrecht, A.Heinle, and V. Levandovskyy. Factoringlineardifferentialoperatorsinnvariables.In Proceedings of the 39th International Symposium on